Re: List container strawman

[Ted Dennison<dennison@telepath.com>]

In article <3BE2DB99.B707D409@boeing.com>, Jeffrey Carter says...
>
>Ted Dennison wrote:
>> 
>> -- This file contains a proposal for a standard Ada list package.
>
>This is NOT a list. A list allows insertions at any point in the
>sequence. This is a dequeue.

Ahhh. I *knew* I forgot a routine. :-) I'll add Insert next to Remove.


>This either needs to be limited private or a controlled type. Since this
>is an unbounded dequeue, assignment of one dequeue to another will
>result in sharing the internal structure implementing the source
>dequeue.

Right again.

>What are the time/space implications for the operations. For example, is
>Size O(1) or O(N)?

That's something we should most certianly discuss (for all these ops). I'd be
for specifying that Size *should* be O(1), which implies that it will be kept
with the main list structure rather than calculated at every Size call.

>I suggest Make rather than Construct.

Fair enough. I'm used to seeing "make" in terms of GNU make, but the term
"Construct" has a fair bit of baggage too. Do we have a second on this motion?

>What happens if you Pop from an empty list?

Good catch. I'll add an exception for that.

(talking about the Closure_Operation generic's Operation procedure parameter)
>They are global to Operation, but they are no more global to the client
>code than are any variables used in the "do stuff" part of your examples
>below.

True. I'm so used to avioding using globals in routines that its tough to
retrain my thinking in this case. But I guess its OK, since you can instantiate
this generic at any level you choose. Thus it could still be data local to the
calling subroutine, but "global" to Operation.

>>    generic
>>       with procedure Operation (Target : in out Element);
>>    procedure Closure_Operation (Target : in out List);
>
>This is an iterator and should be so named ("Iterate"). I recommend
>adding a Quit or Continue out Boolean parameter to Operation to allow
>the client to terminate the iteration early.

Both seem like good suggestions. I'll work on it.

>>    -- Iteration routines. Next and Previous raise No_More if there is no 
>This is really ugly. Why should the client have to include all this
>framing code every time he uses an iterator? The passive iterator
>(generic) given above does the same thing without all this extra client
>code, and allows the value stored in the dequeue to be changed as well.

I messed that interface up a bit, so I'd appreciate it if you would look over
the next version and reconsider your comment. It does clean it up a bit. Also
note that to use the passive iterator, you need a generic instantiation and a
custom Operation routine, both of which this solution does not require. I think
most folks would at least find it a wash.

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.

>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) %-( .

>
>>    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).



>
>> 
>>    -----------------------------------------------------------------------------
>>    -- 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?

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html

No trees were killed in the sending of this message. 
However a large number of electrons were terribly inconvenienced.