Re: List container strawman

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

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.

> --
> -- version - Strawman 1.0
> -------------------------------------------------------------------------------
> generic
>    type Element is private;

This specifies that the package requires "=" for Element. I see no need
for "=" in implementing a dequeue. The generic formal part is improperly
specified.

> package Containers.Lists.Unbounded is
> 
>    -----------------------------------------------------------------------------
>    -- The list type. I know the name's a bit redundant, but it doesn't look too
>    -- bad, and any fully-named use will have to have a different name for the
>    -- package anyway.
>    -----------------------------------------------------------------------------
>    type List is private;

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.

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

> 
>    -----------------------------------------------------------------------------
>    -- List construction operations. The returned list will contain *copies* of
>    -- all the elements in the source lists, so these routines could get
>    -- time-consuming. However, they should be useful for Lisp-like processing.
>    --
>    -- I considered using unary minus ("-") for the "Construct" routine, but
>    -- that's not a common idiom right now.
>    -----------------------------------------------------------------------------
>    function "&" (Left, Right : Element) return List;
>    function "&" (Left : Element; Right : List) return List;
>    function "&" (Left : List; Right : Element) return List;
>    function "&" (Left, Right : List) return List;
>    function Construct (Initial_Element : Element) return List;

I suggest Make rather than Construct.

> 
>    -----------------------------------------------------------------------------
>    -- "push" and "pop" operations.
>    -----------------------------------------------------------------------------
>    procedure Push_Front (Target : in out List; New_Element : in     Element);
>    procedure Pop_Front  (Target : in out List; Old_Element :    out Element);
>    procedure Push_Back  (Target : in out List; New_Element : in     Element);
>    procedure Pop_Back   (Target : in out List; Old_Element :    out Element);

What happens if you Pop from an empty list?

> 
>    -----------------------------------------------------------------------------
>    -- Non-modifying query operations.
>    -----------------------------------------------------------------------------
>    function Is_Empty (Subject : List) return Boolean;
>    function Size     (Subject : List) return Natural;
>    function Front    (Subject : List) return Element;
>    function Back     (Subject : List) return Element;
> 
>    -----------------------------------------------------------------------------
>    -- I'm not too sure how useful these are, since they have to work on global
>    -- data.

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.

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

> 
>    -----------------------------------------------------------------------------
>    -- Iteration routines. Next and Previous raise No_More if there is no item in
>    -- the given direction. For an empty list, First = Last. As written, a
>    -- typical iteration idiom would look like:
>    --
>    --    i := My_Lists.First (My_List);
>    --    loop
>    --       do stuff with My_Lists.Item(i);
>    --       exit when i = My_Lists.Last (My_List);
>    --       i := My_Lists.Next (i);
>    --    end loop;
>    --
>    -- Another alternative using exception handling would be:
>    --
>    --    declare
>    --       i := My_Lists.First (My_List);
>    --    begin
>    --       loop
>    --          do stuff with My_Lists.Item(i);
>    --          i := My_Lists.Next (i);
>    --       end loop;
>    --    exception
>    --       when My_Lists.No_More =>
>    --          null;
>    --    end;
>    --
>    -- A third alternative using "Size" would be:
>    --
>    --  i := My_Lists.First (My_List);
>    --  for iteration_count in 1..My_Lists.Size (My_List) loop
>    --    do stuff with My_Lists.Item (i);
>    --    i := My_Lists.Next (i);
>    --  end loop;
>    --
>    -----------------------------------------------------------------------------

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.

>    type Iterator is private;
>    No_More : exception;
> 
>    function First    (Subject : List)      return Iterator;
>    function Last     (Subject : List)      return Iterator;
>    function Next     (Location : Iterator) return Iterator;
>    function Previous (Location : Iterator) return Iterator;
>    function Item     (Location : Iterator) return Element;
> 
>    -- Ideally this routine would verify that Location was issued for the Subject
>    -- list and is still valid, but that would be tough to enforce. Better to call
>    -- such misuse a "bounded error", or somesuch.

This is simple to enforce. See PragmARC.List_Unbounded_Unprotected for
an example.

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

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

>    generic
>       with function Reverse_Order (Left, Right : in Element) return Boolean;
>    procedure Sort (Subject : in out List);
> 
> private
>    -- Placebo entries to make the compiler happy (so I know the syntax above is correct)
>    type List is new Boolean;
>    type Iterator is new Boolean;
> 
> end Containers.Lists.Unbounded;

-- 
Jeffrey Carter