RE: List container: Insert and Delete

["Steven Deller" <deller@smsail.com>]

> (a) What if I do "delete preceding item" twice? Does it
> delete two items (the preceding one and the one before that)? 
> [In which case, at what position do I end up?]  Does it raise 
> an exception (Item_Already_Deleted)? [In which case, how do I 
> delete backwards twice?] Does it just delete one item (the 
> second delete being effectively ignored)? One of these 
> semantics can be chosen, but I don't think it's obvious 
> which. Poor confused user. On the other hand, I think an 
> operation such as "delete the third item" is pretty obvious 
> and unambiguous.

That's a pretty hard stretch to suggest the semantics are confusing.
  H - 1 - 2 - 3 - T
            ^       position after 2, before 3
  Delete Preceding
  H - 1 - 3 - T
        ^           position after 1, before 3
  Delete Preceding
  H - 3 - T
    ^               position after H, before 3

The semantics are "obvious" as long as positions are "between" elements
and not "on" elements. 

Delete 3rd item is just as "confusing" (No, I don't think it is
confusing, just "as confusing" as you make out for position semantics).
Once I delete the 3rd item, what if I delete the 3rd again.  Does it
raise an exception (Item_Already_Deleted) [In which case, how do I
delete the next item?] ...

As I said, if you speak in terms of pointing "between" elements, the
semantics for position operations are straightforward for all
operations.

Personally, numbering items in a list seems inappropriate to me.  I've
always thought of associating "positional names" with elements as
something other than lists -- arrays perhaps :-).

If I do "insert item before item names '1'", do I get an item named '0'?
Or do the names of ALL other items in the list change?  Yuk.  I
fundamentally object to something that changes the "name" of EVERY other
list item.  That just seems to be ripe for erroneous use.

> (b) For a list based on an array, the operation: "delete the
> third item" is easy to implement, and fairly efficient for 
> short lists; "insert before the third item" is ditto; and 
> "replace the third item" is both easy and efficient (for any 
> length of list). For a list based on a linked-list, the 
> implementations of these operations are easy, and pretty 
> efficient for short lists and for operations near to either 
> end of the list.

Delete preceding and delete succeeding for position operations are easy
too.  As is insert before or insert after position.  

Trying to keep number references straight in "user code" for a list as
inserts/deletes happen would lead (easily) to application errors by less
expert users. Off-by-one errors are quite frequent in such situations.
 
> So I think the design based on indexed positioning wins 'on
> points', as it were.

Only when you are adding up the points :-).  I have seen both semantics,
and there are times I'd prefer one or the other.  But when I want
"names" for elements, I use arrays, in which I can't *delete* an item or
a name, only make it have a different value.  Names (numbers) are
constant for arrays once they are created.

The numbering approach also has the problem of "dynamic constraints" for
index numbers.  What happens if I reference List(13) when there are only
12 items in the list?

The "position" approach is able to provide "split list" into two parts
-- head and tail -- with little effort and with clear semantics (with a
"between items" pointer).

With numbers, the semantics of split list become consufing :-) -- does
"split list at 3rd item" leave the 3rd item in the head or the tail?
The semantics are not obvious and I do agree that users need "models"
from which semantics are obvious, not an arbitrary list of operational
semantics that have to be remembered each on its own.

Either approach is simple to implement in terms of the other. The
"numbering" semantics require O(N) time in the general case.  That, in
my mind, is the strongest argument against providing "numbering" of
lists.  Naïve users typically program as if primitive operations are
O(1) in time. 

So I think a design based on indexed positioning can lead to impractical
(or erroneous) applications from naïve users -- primitive operations
ought to be more "user proof".

Regards,
Steve