Re: List container: Insert and Delete

["Nick Roberts" <nickroberts@adaos.worldonline.co.uk>]

I'm not qoting your reply, I'll just say I find it pretty persuasive. (And
very well argued.)

I have actually e-mailed my proposal based on indexed positioning; hopefully
Ted will put it up on the web site soon. Do have a look at it.

My most solidified idea regarding an alternative way of indicating positions
was based on 'markers' which marked items in the list (rather than being
notionally inserted inbetween two adjacent items). Is it really better to
have starkly inter-item positioning, or would it actually be better to say
that if item X is marked, "delete forward" means delete the item X, whereas
"delete backward" means delete the item preceding X? This would be analogous
to the way the cursor in most word processors deletes characters. The
procedures could be named to reflect this model, e.g.:

   procedure Delete_from_Marker (
      Marker: in out Unbounded_Marker;
      Count:  in     Natural := 1);

   procedure Delete_Before_Marker (
      Marker: in out Unbounded_Marker;
      Count:  in     Natural := 1);

The idea was to be able to set a marker to any item in a list. The marker
could then be advanced up or retired down the list. The item it marks can be
retrieved for inspection. The item at the marker can be deleted or replaced,
but ONLY if there are no other markers set on it. This means having a
counter in each node (but that's okay), but it does provide a rudimentary
form of locking (handy for some algorithms); a basic implementation would
raise an exception on breach of this locking, but a multi-tasking
alternative could perform a wait. Insert and append operations would need to
have versions that return a marker. There would need to be a few extra
operations (e.g. "copy marker").

These operations would be efficient for a linked-list implementation, but
not for a array-based one (for long lists). Again, that's okay (just not
ideal).

Do you like this idea? Shall I work up a new proposal based on this? Would
it be worth having both approaches (both index-based and marker-based)? (I
quite favour having both. Students should be taught to use the markers.)

--
Best wishes,
Nick Roberts