Re: list strawman

[Thomas Wolf <t_wolf@angelfire.com>]

dennison@telepath.com wrote:
> In article <uwuys1qun.fsf@gsfc.nasa.gov>, Stephen Leake says...
> >
> >Ted Dennison<dennison@telepath.com> writes:
> >> Its there, it just hasn't been very well advertised.
> >
> >We need to add a explicit visible "=" to make it do what you want; in
> >my implementation, the default "=" does not.
> 
> You don't have to override "=" in the public part of a spec, so I usually don't.
> With the strawmen I took the principle that only the public part of the spec was
> presented, along with some extra stuff in the private part to get it to compile.
> Perhaps in this case I took the principle too far...
> 
> I should shoulder the blame for any confusion this "implicit requirement" has
> caused, since I left it implicit. But nits aside, it should be clear that "=" is
> available, for Lists and Iterators, and thus implementors must make them both do
> the sensible thing. Leaving them available but doing useless things is obviously
> not good design. I might accept it for a package internal to a project, but
> certianly not for something that is supposed to be standard.

Some comments on that Strawman 1.4 interface:

1. Generic formals
------------------

   generic
      type Element is private;
   package Containers.Lists.Unbounded is

I'd prefer

   generic
      type Element is private;
      with function "=" (Left, Right : Element) return Boolean is <>;
   package Containers.Lists.Unbounded is

This allows users who have unconventional ideas of equality to provide
their own routine, without requiring "normal" users to specify the
equality function explicitly.

2. Element Arrays
-----------------

      type Element_Array is array (Natural range <>) of Element;
      
Why "Natural range <>"? I'd prefer "Positive range <>" similar to the
string packages. Note that you can still return an empty array for an
empty list by returning Element_Array (2 .. 1).

3. Naming issues
----------------

      function To   (Source : Element_Array) return List;
      function From (Source : List) return Element_Array;

I'd call these 'To_List' and 'To_Array', respectively. Maybe provide
these as renamings?

      function Singleton (Initial_Element : Element) return List;

I realize there's already been quite some discussion on that name. I
side with the "don't like" camp; I'd call this 'To_List', too.

4. Removing from a list end
---------------------------

      procedure Remove
        (Target      : in out List;
         Old_Element :    out Element;
         List_End    : in     Direction);

You don't always want to get the old element when you remove an item
from the list. Hence I'd add the following:

      procedure Remove
        (Target   : in out List;
         List_End : in     Direction);

5. Generic iterator
-------------------

      generic
         with procedure Operation (Target : in out Element; 
                                   Quit   :    out Boolean);
      procedure Passive_Iterator (Target : in out List);

Two things: first, 'Quit' must be an "in out"-parameter, and second,
in *my* terminology, this is an *active* iterator. After all, it
iterates on its own, so it's active, whereas the positions provided
by the type 'Iterator' do not move by themselves but have to be
advanced explicitly by the client code. Or did I get my nomenclature
mixed up?

Oh yes, and another thing: the list is an "in out" parameter, probably
to indicate that 'Operation' may change the elements (although the list
structure, i.e. the node chain, remains unchanged). A second variant

      generic
         with procedure Inspect (Target : in     Element; 
                                 Quit   : in out Boolean);
      procedure Read_Only_Iterator (Target : in List);

might be useful, too.

6. Inserting at a given location
--------------------------------

      procedure Insert (New_Item : in Element;
                        Location : in Iterator;
                        Side     : in Direction := Head);
      procedure Insert (New_Items : in List;
                        Location  : in Iterator;
                        Side      : in Direction := Head);

For completeness, the following is missing:

      procedure Insert (New_Items : in Element_Array;
                        Location  : in Iterator;
                        Side      : in Direction := Head);

In the two latter cases, nothing happens if 'New_Items' is empty.

7. Modifying an element at a given location
-------------------------------------------

      procedure Modify (Subject   : in out List; 
                        Location  : in     Iterator;
                        New_Value : in     Element);

Why is the subject list passed along? To be consistent with the
other operations on locations, it should be omitted.

8. Operations requiring a "<" on elements
-----------------------------------------

      generic
         with function Reverse_Order (First, Second : in Element)
                 return Boolean;
         From : in Direction;
      package Sorting is

Why this somewhat unusual (at least in my perception) interface?
Why not simply

      generic
         with function "<" (Left, Right : Element) return Boolean is <>;
      package Ordered is

and define e.g. Sort to sort the list into ascending order according to
the given "<" routine. (Or if you like, replace "<" by ">", it doesn't
matter.)

If you still want the ability to do both ascending and descending sorts
with the same instantiation, change 'Sort' to something like

         procedure Sort (Subject   : in out List;
                         Ascending : in     Boolean := True);

Furthermore, you could also provide lexicographical comparisons in this
nested package.

9. Equality
-----------

Both lists and iterators need meaningful equality operations. For lists,
return True if they both contain equal elements in the same order; for
iterators, return True if they both are null or else both point to the
same list node.

Is there any harm done by putting them explicitly in the public part?
This would make it absolutely clear for anybody that sensible 
implementations have to be provided for these operations. Furthermore,
it'd define a convenient place to put a comment explaining under what
conditions these operators return True.

10. Stream Attributes
---------------------

There's no need at all to make 'Stream_Read' and 'Stream_Write' public.
I'd put them into the private part.

-- 
-----------------------------------------------------------------
Thomas Wolf                          e-mail: t_wolf@angelfire.com