Re: List container strawman

[Jeffrey Carter <jeffrey.carter@boeing.com>]

Ted Dennison wrote:
> 
> Even if it isn't as nice as the passive iterator, I think it is still needed, as
> that is how Insert and Remove (your middle of the list operations) are
> performed.

OK. Then this isn't really an iterator type; it's the "Position" type
that indicates where in the list you're operating. Now this is starting
to look like a list, except I expect to see the general operations
(obtain a Position for a list and operate on a specific Position within
a list) first, with the bells and whistles later.

> 
> >This is simple to enforce. See PragmARC.List_Unbounded_Unprotected for
> >an example.
> 
> Hmmm. Yeah, I guess one could keep a copy of the address of the list around,
> assuming that it is implemented in a way in which that makes sense. That still
> doesn't prevent further operations from invalidating your iterator. To detect
> that, you'd need to somehow keep track of every iterator issued along with the
> list (in a little mini-list inside it) %-( .

The technique used by PragmARC.List_Unbounded_Unprotected is that the
list object contains a pointer to a "mini-node" (a node with no data
stored in it). This makes insertions and deletions at the beginning and
end of the list look exactly the same as insertions and deletions in the
middle, but it also follows that the value of this pointer is unique to
the list object. Call this value the list ID. Every node in the list
contains a copy of this ID, as does every Position value generated for
the list. An operation is not permitted unless the IDs for the list,
position, and node match. When a node is deleted, its ID is invalidated
(set to null), and the position used to delete the node is similarly
invalidated (both its ID and pointer are set to null). If a client makes
a copy of a Position and uses one to delete a node, he cannot then
manipulate the deallocated node through the other since it has an
invalid ID. Easy to implement and fairly foolproof.

> 
> >
> >>    procedure Remove   (Subject : in out List; Location : Iterator);
> >
> >Using a given Iterator value, what is the value of Next or Previous
> >after Remove? How about Item? What about when you remove the first or
> >last Elements in the dequeue?
> 
> Yet another good catch (one would think you've done this before ;-) ). I'd say
> that:
> 
> o  The mode for "Location" should be "in out" so it won't be invalid afterwards.
> o  If Location=First, then Location will be set to the new First.
> o  If Location=Last, then Location will be set to Done_Iterating.
> o  If Location=Done_Iterating, then No_Item will be raised.
> o  otherwise, Location will be set to what Next was previously (the next element
> after the removal).

Now that I know that this is standard list manipulation, not iteration,
I'd recommend calling it Delete. It's also a lot simpler to make
Location in out and invalidate it.

There should probably be an Update procedure that changes the Element
stored at a location.

> >>    -----------------------------------------------------------------------------
> >>    -- Sorting routine.
> >>    -- To sort in increasing order, use the ">" routine for the Reverse_Order
> >>    -- parameter. To sort in decreasing order, substitute your "<" routine for
> >>    -- the Reverse_Order parameter. :-)
> >>    -----------------------------------------------------------------------------
> >
> >This seems ugly and easy to get wrong. Why not import "<" and specify
> >that after calling Sort, the Elements in Subject will be in order
> >according to "<"? Then the meaning of the imported function is clear
> >without such a comment.
> 
> I started with that, but it wasn't clear to *me* when I read it back to myself.
> (Hint: which end of the list is on the "left"?) Admittedly, I'm not always the
> perfect judge of such things though. Does anyone else think that would be
> clearer?

A list is a sequence; it has a first Element, a second Element, and so
on. The postcondition here is that for any 2 valid locations L1 and L2
such that L1 /= L2 and L2 = Next (L1),

not (Item (L2) < Item (L1) ).

-- 
Jeffrey Carter