A generic list package (long)

A generic list package (long)

[Florian Weimer]

I'm currently working on a general-purpose low-level list package.
The existing approaches were either too heavy-weight, too limited, or
covered by an unacceptable license.

What do you think about the approach documented below?

BTW: Could you suggest a better name than 'ADT' (meaning:
'imlementations of abstract data types') for this sub-hierarchy?
What about 'Generics'?  Some day, this hierarchy will provide
implementations of several different data structures, in a few
different flavors, at least I hope so. ;-)


The Generic Package `ADT.Lists.Intrusive'
-----------------------------------------

   This generic package provides a very simple list type which has the
following characteristics:

   - The list is intrusive, i.e. an element can be contained in at most
     one list at a time, and the each element must provide a reference
     to the following element (this reference is accessed via `Next_Of'
     and `Set_Next').

   - This package can be used as a mixin to add list capabilities to
     another type.

   - The list implementation itself does not need any additional memory
     (except for storing the root of the list).

   - The list implementation is rather compact.  Most of the more
     complex subprograms are generics themselves and do not contribute
     to the code footprint of a simple instantiation of the package.

   - The implementation does not use tagged types.  The generic does
     not need to be instanced at library level.

   - All operations are not task safe.  Two tasks may not operate on
     the same list object.

   In this section, time is measured by counting the simple operations
(such as assignments of `Item_Access' values) and the number of
`Next_Of', `Set_Next', `"="', and `Free' subprogram invocations for
`Item_Access' objects.

   Assigning objects of type `List_Type' does not copy the elements of
the list.  Operations which change the list root (see below) render such
copies invalid.

Code example
------------

     declare
        type Integer_Item;
        type Integer_Item_Access is access Integer_Item;
        type Integer_Item is record
           Value : Integer;
           Next  : Integer_Item_Access;
        end record;
     
        function Next_Of
           (Item : Integer_Item_Acces)
            return Integer_Item_Access
        is
        begin
           return Item.Next;
        end Next_Of;
     
        procedure Set_Next (Item, Next : Integer_Item_Access) is
        begin
           Item.Next := Next;
        end Set_Next;
     
        package Integer_Lists is
           new ADT.Lists.Intrusive (Integer_Item_Access, null);
        use List_Type;
     
        A_List : List_Type;
        package My_Append is new Generic_Append (A_List);
     
        Iter : Integer_Item_Access;
     
     begin
        --  Append the numbers from 1 to 10 to A_List.
        for J in 1 .. 10 loop
           My_Append.Append (new Integer_Item (J, null));
        end loop;
     
        --  Print out the items in A_List.
        --  (We could use a suitable For_Each instance instead.)
        Iter := First_Item (A_List);
        while not Is_Done (Iter) loop
           Put(Iter.Value);
           New_Line;
           Advance (Iter);
        end loop;
     end;

Formal parameters of the generic
--------------------------------

   The caller has to provide the following information when
instantiating the generic:

  generic
     type Item_Access is private;

     Conceptually, this is a pointer to the actual item.  Copying
     `Item_Access' values shall have no side effects, and it is assumed
     that such copy operations are not expensive in terms of CPU cycles.

  No_Item : Item_Access;

     An `Item_Access' value which is different from all values which
     denote actual objects.  It is used to signal special conditions,
     much like a `null' access value.

  with function "=" (Left, Right : Item_Access) return Boolean is <>;

     Compares two `Item_Access' values, _and not the objects they refer
     to_.  In particular, `No_Item = No_Item' must be true, and if `X =
     No_Item' is true, `X' is `No_Item'.

  with function Next_Of (Item : Item_Access) return Item_Access is <>;

     Returns the value of the `next element' field of ITEM (this value
     is stored in the object itself, not in the reference).

  with procedure Set_Next
     (Item : in Item_Access;
      Next : in Item_Access) is <>;

     Changes the `next element' field.  This sets the return value of
     future calls to `Next_Of'.

  with procedure Free (Item : in out Item_Access) is <>;

     Deallocates ITEM and sets the variable to `No_Item'.

Facilities provided by an instantiation
---------------------------------------

   An instantation of the generic provides the following facilities:

  type List_Type is private;

     The type of the list.  Conceptually, this is a refernce to the
     first element of the list.  A list is initially empty.

  procedure Free (List : in out List_Type);

     Calls `Free (Item : in out Item_Access)' for each item in LIST and
     makes LIST empty.  (Changes root of LIST.)

  generic
     with function Clone_Item (Item : Item_Access) return Item_Access;
  procedure Clone (Source : in List_Type; Target : out List_Type);

     Creates a copy of the elements of SOURCE in TARGET.  Before the
     cloning operation, all elements of TARGET are removed.  `Clone' is
     called for each element in SOURCE, and these new elements are
     added to TARGET.  SOURCE and TARGET have to be differnt.  `Clone'
     changes the root of TARGET.

     If CLONE_ITEM returns `No_Item', the corresponding item of SOURCE
     is not included in `Target'.  Using this convention, it is
     possible to filter the list while cloning it.

  procedure Transfer (Source, Target : in out List_Type);

     Frees TARGET, copies the SOURCE list to TARGET, and sets SOURCE to
     the empty list.

  function First_Item (List : List_Type) return Item_Access;

     Returns the first element of LIST, or `No_Item' if LIST is empty.
     Conceptually, the returned value is an iterator, see `Advance' and
     `Is_Done'.  (Requires constant time.)

  function Last_Item (List : List_Type) return Item_Access;

     Returns the last element of LIST, or `No_Item' if LIST is empty.
     (Requires time proportional to the list length.)

  function Nth_Item
    (List : List_Type; Nth : Positive)
    return Item_Access;

     Returns the element which is at position NTH in LIST.  The first
     element has the number 1.  Raises `Index_Error' if LIST contains
     fewer elements than indicated by NTH.  (Requires time
     proportionally to NTH.)

  procedure Advance (Item : in out Item_Access);

     Advances the iterator ITEM to the element after the old value of
     ITEM, or to `No_Item' if there is no following element.  (Requires
     constant time.)

  function Is_Done (Item : Item_Access) return Boolean;

     Returns true if ITEM is equal to `No_Item', false otherwise.
     (Requires constant time.)

  function Is_Last (Item : Item_Access) return Boolean;

     Returns true if ITEM is the last element in the list, i.e. if
     `Is_Done (Next_Of (Item))' is true.  If ITEM equals `No_Item',
     `Index_Error' is raised.  (Requires constant time.)

  procedure Advance_To_Last (Item : in out Item_Access);

     Advances the iterator ITEM multiple times until `Is_Last (Item)'
     is true.  Raises `Index_Error' if ITEM equals `No_Item'.
     (Requires time proportional to the tail of the list starting at
     ITEM.)

  procedure Add_At_Front
    (List : in out List_Type;
     Item : in Item_Access);

     Inserts ITEM at the beginning of LIST.  ITEM becomes the new first
     element of LIST, and the position (see `Nth') of the following
     elements increases by 1.  (Requires constant time, changes root of
     LIST.)

  procedure Add_After
     (List  : in out List_Type;
      After : in     Item_Access;
      Item  : in     Item_Access);

     Adds ITEM to LIST after item AFTER, and the position (see `Nth')
     of the following elements increases by 1.  ITEM most not equal
     `No_Item', and AFTER must be part of LIST.  (Requires constant
     time.)

  procedure Append (List : in out List_Type; Item : in Item_Access);

     Appends ITEM to LIST. making ITEM the last element of LIST.  ITEM
     must not be `No_Item'.  (Requires time proportional to the length
     of LIST, changes root of LIST if was empty.)

  procedure Append_List (First_List, Second_List : in out List_Type);

     Appends SECOND_LIST to FIRST_LIST and sets SECOND_LIST to the
     empty list.  After this operation, FIRST_LIST contains the all the
     items it contained before, followed by the items of SECOND_LIST,
     in order. (Requires time proportional to the length of LIST,
     changes root of LIST if was empty.)

  type Append_Cache is limited private;


  procedure Append
    (List  : in out List_Type;
     Item  : in     Item_Access;
     Cache : in out Append_Cache);
  procedure Append_List
    (First_List, Second_List : in out List_Type;
     First_Cache             : in out Append_Cache);
  procedure Reset_Cache (Cache : out Append_Cache);

     These procedures are very similar to the ones above, but speed up
     repeated appends using a cache value for the list end.  Each list
     to which items are appended requires a different cache.  Between
     the calls to `Append' and `Append_List', elements may be added to
     the list, but no elements must be removed (unless `Reset_Cache' is
     called after items were removed).  (If the cache is up to date
     (i.e. no elements were added by other means than `Append'),
     `Append' requires constant time after the first call.  The first
     call of `Append' after a reset requires time proportional to the
     length of the list. A call to `Append_List' requires constant
     time, too, if the cache is up to date, but updating the cache in
     the next call to `Append' or `Append_List' requires time
     proportional to the length of SECOND_LIST.)

  generic
     List : in out List_Type;
  package Generic_Append is
     procedure Append (Item : in Item_Access);
     procedure Append_List (Second_List : in out List_Type);
     procedure Reset_Cache;
     procedure Free;
  end Generic_Append;

     This package wraps the `Append', `Append_List' `Reset_Cache'
     procedures above, together with an implicit cache.  The same
     restrictions for removing elements apply.  For convenience, you
     can clear the list by calling `Free'.

  procedure Remove_First (List : in out List_Type);

     Removes the first element of LIST and performs `Free' on it.
     Raises `Index_Error' if LIST is empty.  (Requires constant time,
     changes root of LIST.)

  procedure Remove
    (List : in out List_Type;
     Item : in out Item_Access);

     Removes an arbitrary element ITEM from LIST and performs `Free' on
     it.  Raises `Index_Error' if ITEM cannot be found in LIST.
     (Requires time proportional to the length of LIST, changes root of
     LIST.)

  function Is_Empty (List : List_Type) return Boolean;

     Returns true if LIST contains no elements, otherwise false.
     (Requires constant time.)

  function Length (List : List_Type) return Natural;

     Returns the number of elements contained in LIST.  (Requires time
     proportional to the length of LIST.)

  generic
     type Item_Access_Index is range <>;
     type Item_Access_Array is array (Item_Access_Index range <>)
       of Item_Access;
  function To_Array (List : List_Type) return Item_Access_Array;

     Returns an array of all elements contained in LIST, preserving the
     order of elements.  ITEM_ACCESS_INDEX must include the range from
     1 to `Length (List)' (otherwise, `Constraint_Error' is raised).

  generic
     type Item_Access_Index is range <>;
     type Item_Access_Array is array (Item_Access_Index range <>)
       of Item_Access;
  procedure To_List
     (Source : in     Item_Access_Array;
      Target : in out List_Type);

     Removes all elements from TARGET and replaces them with the
     elements in SOURCE, preserving order.  (Changes root of TARGET.)

  generic
     with procedure Action (Item : Item_Access);
  procedure For_Each (List : List_Type);

     Iterates over LIST, i.e. calls ACTION for each element in LIST,
     obeying the order of elements.  ACTION may destroy or otherwise
     modify ITEM, or destroy elements before ITEM in LIST.

  generic
     with function Predicate (Item : Item_Access) return Boolean;
  procedure Filter_In_Place (List : in out List_Type);

     Removes all elements from LIST (using `Remove') for which
     PREDICATE is false.  The calls to PREDICATE are performed in the
     order the elements are stored in `List'.  (Changes root of LIST.)

     See the `Clone' subprogram if you need a filtered copy of a list
     (which leaves the source list unaffected), or use the following
     subprogram.

  generic
     with function Predicate (Item : Item_Access) return Boolean;
     type Item_Access_Index is range <>;
     type Item_Access_Array is array (Item_Access_Index range <>)
        of Item_Access;
  function Filter (List : List_Type) return Item_Access_Array;

     Returns an array of all elements in LIST for which PREDICATE is
     true, preserving the order of elements.  ITEM_ACCESS_INDEX must
     include the range from 1 to `Length (List)' (otherwise,
     `Constraint_Error' is raised).  Internally, `Filter' creates an
     array with `Length (List)' elements.  Therefore, if you want to
     select a few elements of a large list, you should probably use
     `Clone'.

  generic
     with function Predicate (Item : Item_Access) return Boolean;
  function First_That (List : List_Type) return Item_Access;

     Returns the first element of LIST for which PREDICATE is true, or
     `No_Item' if there is no such element.

  generic
     with function Predicate (Item : Item_Access) return Boolean;
  procedure Next_That (Item : in out Item_Access);

     Sets ITEM to the next element in the list after the old ITEM for
     which PREDICATE is true, or to `No_Item' if there is no such
     element.

  generic
     with function Predicate (Item : Item_Access) return Boolean;
  function Last_That (List : List_Type) return Item_Access;

     Returns the last element of LIST for which PREDICATE is true, or
     `No_Item' if there is no such element.

  procedure Split
    (Source             : in out List_Type;
     Target_1, Target_2 : in out List_Type);

     Splits SOURCE to TARGET_1 and TARGET_2.  The old lists TARGET_1
     and TARGET_2 are deallocated.  After a `Split' operation, SOURCE
     is empty, and TARGET_1 and TARGET_2 contain all elements of
     SOURCE, and the length difference between TARGET_1 and TARGET_2 is
     at most 1.  TARGET_1 and TARGET_2 have to be different lists.
     SOURCE, TARGET_1 and TARGET_2 have to refer to different lists.
     (Changes root of SOURCE, TARGET_1 and TARGET_2.)

  generic
     with function "<="
       (Left, Right : Item_Access)
       return Boolean is <>;
  procedure Merge
    (Source_1, Source_2 : in out List_Type;
     Target             : in out List_Type);

     Merges SOURCE_1 and SOURCE_2 and stores the result in TARGET.  In
     this case, "merging" means that if both source lists are sorted
     according to the "<=" predicate, TARGET will be sorted as well.
     All three lists have to be distinct.  Note that the order in which
     equal elements are taken from SOURCE_1 and SOURCE_2 and put into
     TARGET is not defined, so it is not possible to construct a stable
     sorting procedure based on this routine.  SOURCE_1, SOURCE_2 and
     TARGET have to denote different lists. (Changes root of SOURCE_1,
     SOURCE_2 and TARGET.)

  generic
     with function "<="
       (Left, Right : Item_Access)
       return Boolean is <>;
  procedure Sort (List : in out List_Type);

     Sorts LIST according to the "<=" predicate, in place.  The sort
     operation is _not_ stable. (Changes root of LIST.)

Re: A generic list package (long)

[Stephen Leake]

Florian Weimer <fw@deneb.enyo.de> writes:

> I'm currently working on a general-purpose low-level list package.
> The existing approaches were either too heavy-weight, too limited, or
> covered by an unacceptable license.
> 
> What do you think about the approach documented below?

I've written a list package with similar goals; see
http://users.erols.com/leakstan/Stephe/Ada/sal.html. In particular,
see SAL.Gen.Lists.Double. I've found few uses for a singly linked
list, so my generic is a double linked list. 

I have far fewer operations in my list package. I would separate out
the "convert to array", and "filter" operations into child packages;
I've never used such operations on lists. I also split the "for each"
and "find" operations into separate packages. For "for each", I
provide an Iterators child. For "find", I use an algorithms package
approach, as the C++ STL does; see SAL.Gen.Alg.Find_Linear.

I find it curious that you expect the client to provide the "next"
field/operation, rather than declaring a Node_Type containing the
user's type and a Next field. Can you elaborate on this? Hmm, maybe
because of Controlled types? I did have to provide some auxiliary
packages to make it easier to instantiate my list package for simple
types, but complex types need the full power I provide. Your approach
leaves everything up to the user; mine ensures that garbage is
collected appropriately, when necessary; the user only needs to provide
the appropriate 'free' operation.

> 
> 
> BTW: Could you suggest a better name than 'ADT' (meaning:
> 'imlementations of abstract data types') for this sub-hierarchy?
> What about 'Generics'? Some day, this hierarchy will provide
> implementations of several different data structures, in a few
> different flavors, at least I hope so. ;-)
> 
> 
> The Generic Package `ADT.Lists.Intrusive'
> -----------------------------------------
> 
>    This generic package provides a very simple list type which has the
> following characteristics:
> 
>    - The list is intrusive, i.e. an element can be contained in at most
>      one list at a time, and the each element must provide a reference
>      to the following element (this reference is accessed via `Next_Of'
>      and `Set_Next').
> 
>    - This package can be used as a mixin to add list capabilities to
>      another type.
> 
>    - The list implementation itself does not need any additional memory
>      (except for storing the root of the list).
> 
>    - The list implementation is rather compact.  Most of the more
>      complex subprograms are generics themselves and do not contribute
>      to the code footprint of a simple instantiation of the package.
> 
>    - The implementation does not use tagged types.  The generic does
>      not need to be instanced at library level.
> 
>    - All operations are not task safe.  Two tasks may not operate on
>      the same list object.
> 
>    In this section, time is measured by counting the simple operations
> (such as assignments of `Item_Access' values) and the number of
> `Next_Of', `Set_Next', `"="', and `Free' subprogram invocations for
> `Item_Access' objects.
> 
>    Assigning objects of type `List_Type' does not copy the elements of
> the list.  Operations which change the list root (see below) render such
> copies invalid.
> 
> Code example
> ------------
> 
>      declare
>         type Integer_Item;
>         type Integer_Item_Access is access Integer_Item;
>         type Integer_Item is record
>            Value : Integer;
>            Next  : Integer_Item_Access;
>         end record;
>      
>         function Next_Of
>            (Item : Integer_Item_Acces)
>             return Integer_Item_Access
>         is
>         begin
>            return Item.Next;
>         end Next_Of;
>      
>         procedure Set_Next (Item, Next : Integer_Item_Access) is
>         begin
>            Item.Next := Next;
>         end Set_Next;
>      
>         package Integer_Lists is
>            new ADT.Lists.Intrusive (Integer_Item_Access, null);
>         use List_Type;
>      
>         A_List : List_Type;
>         package My_Append is new Generic_Append (A_List);
>      
>         Iter : Integer_Item_Access;
>      
>      begin
>         --  Append the numbers from 1 to 10 to A_List.
>         for J in 1 .. 10 loop
>            My_Append.Append (new Integer_Item (J, null));
>         end loop;
>      
>         --  Print out the items in A_List.
>         --  (We could use a suitable For_Each instance instead.)
>         Iter := First_Item (A_List);
>         while not Is_Done (Iter) loop
>            Put(Iter.Value);
>            New_Line;
>            Advance (Iter);
>         end loop;
>      end;
> 
> Formal parameters of the generic
> --------------------------------
> 
>    The caller has to provide the following information when
> instantiating the generic:
> 
>   generic
>      type Item_Access is private;
> 
>      Conceptually, this is a pointer to the actual item.  Copying
>      `Item_Access' values shall have no side effects, and it is assumed
>      that such copy operations are not expensive in terms of CPU cycles.
> 
>   No_Item : Item_Access;
> 
>      An `Item_Access' value which is different from all values which
>      denote actual objects.  It is used to signal special conditions,
>      much like a `null' access value.
> 
>   with function "=" (Left, Right : Item_Access) return Boolean is <>;
> 
>      Compares two `Item_Access' values, _and not the objects they refer
>      to_.  In particular, `No_Item = No_Item' must be true, and if `X =
>      No_Item' is true, `X' is `No_Item'.
> 
>   with function Next_Of (Item : Item_Access) return Item_Access is <>;
> 
>      Returns the value of the `next element' field of ITEM (this value
>      is stored in the object itself, not in the reference).
> 
>   with procedure Set_Next
>      (Item : in Item_Access;
>       Next : in Item_Access) is <>;
> 
>      Changes the `next element' field.  This sets the return value of
>      future calls to `Next_Of'.
> 
>   with procedure Free (Item : in out Item_Access) is <>;
> 
>      Deallocates ITEM and sets the variable to `No_Item'.
> 
> Facilities provided by an instantiation
> ---------------------------------------
> 
>    An instantation of the generic provides the following facilities:
> 
>   type List_Type is private;
> 
>      The type of the list.  Conceptually, this is a refernce to the
>      first element of the list.  A list is initially empty.
> 
>   procedure Free (List : in out List_Type);
> 
>      Calls `Free (Item : in out Item_Access)' for each item in LIST and
>      makes LIST empty.  (Changes root of LIST.)
> 
>   generic
>      with function Clone_Item (Item : Item_Access) return Item_Access;
>   procedure Clone (Source : in List_Type; Target : out List_Type);
> 
>      Creates a copy of the elements of SOURCE in TARGET.  Before the
>      cloning operation, all elements of TARGET are removed.  `Clone' is
>      called for each element in SOURCE, and these new elements are
>      added to TARGET.  SOURCE and TARGET have to be differnt.  `Clone'
>      changes the root of TARGET.
> 
>      If CLONE_ITEM returns `No_Item', the corresponding item of SOURCE
>      is not included in `Target'.  Using this convention, it is
>      possible to filter the list while cloning it.
> 
>   procedure Transfer (Source, Target : in out List_Type);
> 
>      Frees TARGET, copies the SOURCE list to TARGET, and sets SOURCE to
>      the empty list.
> 
>   function First_Item (List : List_Type) return Item_Access;
> 
>      Returns the first element of LIST, or `No_Item' if LIST is empty.
>      Conceptually, the returned value is an iterator, see `Advance' and
>      `Is_Done'.  (Requires constant time.)
> 
>   function Last_Item (List : List_Type) return Item_Access;
> 
>      Returns the last element of LIST, or `No_Item' if LIST is empty.
>      (Requires time proportional to the list length.)
> 
>   function Nth_Item
>     (List : List_Type; Nth : Positive)
>     return Item_Access;
> 
>      Returns the element which is at position NTH in LIST.  The first
>      element has the number 1.  Raises `Index_Error' if LIST contains
>      fewer elements than indicated by NTH.  (Requires time
>      proportionally to NTH.)
> 
>   procedure Advance (Item : in out Item_Access);
> 
>      Advances the iterator ITEM to the element after the old value of
>      ITEM, or to `No_Item' if there is no following element.  (Requires
>      constant time.)
> 
>   function Is_Done (Item : Item_Access) return Boolean;
> 
>      Returns true if ITEM is equal to `No_Item', false otherwise.
>      (Requires constant time.)
> 
>   function Is_Last (Item : Item_Access) return Boolean;
> 
>      Returns true if ITEM is the last element in the list, i.e. if
>      `Is_Done (Next_Of (Item))' is true.  If ITEM equals `No_Item',
>      `Index_Error' is raised.  (Requires constant time.)
> 
>   procedure Advance_To_Last (Item : in out Item_Access);
> 
>      Advances the iterator ITEM multiple times until `Is_Last (Item)'
>      is true.  Raises `Index_Error' if ITEM equals `No_Item'.
>      (Requires time proportional to the tail of the list starting at
>      ITEM.)
> 
>   procedure Add_At_Front
>     (List : in out List_Type;
>      Item : in Item_Access);
> 
>      Inserts ITEM at the beginning of LIST.  ITEM becomes the new first
>      element of LIST, and the position (see `Nth') of the following
>      elements increases by 1.  (Requires constant time, changes root of
>      LIST.)
> 
>   procedure Add_After
>      (List  : in out List_Type;
>       After : in     Item_Access;
>       Item  : in     Item_Access);
> 
>      Adds ITEM to LIST after item AFTER, and the position (see `Nth')
>      of the following elements increases by 1.  ITEM most not equal
>      `No_Item', and AFTER must be part of LIST.  (Requires constant
>      time.)
> 
>   procedure Append (List : in out List_Type; Item : in Item_Access);
> 
>      Appends ITEM to LIST. making ITEM the last element of LIST.  ITEM
>      must not be `No_Item'.  (Requires time proportional to the length
>      of LIST, changes root of LIST if was empty.)
> 
>   procedure Append_List (First_List, Second_List : in out List_Type);
> 
>      Appends SECOND_LIST to FIRST_LIST and sets SECOND_LIST to the
>      empty list.  After this operation, FIRST_LIST contains the all the
>      items it contained before, followed by the items of SECOND_LIST,
>      in order. (Requires time proportional to the length of LIST,
>      changes root of LIST if was empty.)
> 
>   type Append_Cache is limited private;
> 
> 
>   procedure Append
>     (List  : in out List_Type;
>      Item  : in     Item_Access;
>      Cache : in out Append_Cache);
>   procedure Append_List
>     (First_List, Second_List : in out List_Type;
>      First_Cache             : in out Append_Cache);
>   procedure Reset_Cache (Cache : out Append_Cache);
> 
>      These procedures are very similar to the ones above, but speed up
>      repeated appends using a cache value for the list end.  Each list
>      to which items are appended requires a different cache.  Between
>      the calls to `Append' and `Append_List', elements may be added to
>      the list, but no elements must be removed (unless `Reset_Cache' is
>      called after items were removed).  (If the cache is up to date
>      (i.e. no elements were added by other means than `Append'),
>      `Append' requires constant time after the first call.  The first
>      call of `Append' after a reset requires time proportional to the
>      length of the list. A call to `Append_List' requires constant
>      time, too, if the cache is up to date, but updating the cache in
>      the next call to `Append' or `Append_List' requires time
>      proportional to the length of SECOND_LIST.)
> 
>   generic
>      List : in out List_Type;
>   package Generic_Append is
>      procedure Append (Item : in Item_Access);
>      procedure Append_List (Second_List : in out List_Type);
>      procedure Reset_Cache;
>      procedure Free;
>   end Generic_Append;
> 
>      This package wraps the `Append', `Append_List' `Reset_Cache'
>      procedures above, together with an implicit cache.  The same
>      restrictions for removing elements apply.  For convenience, you
>      can clear the list by calling `Free'.
> 
>   procedure Remove_First (List : in out List_Type);
> 
>      Removes the first element of LIST and performs `Free' on it.
>      Raises `Index_Error' if LIST is empty.  (Requires constant time,
>      changes root of LIST.)
> 
>   procedure Remove
>     (List : in out List_Type;
>      Item : in out Item_Access);
> 
>      Removes an arbitrary element ITEM from LIST and performs `Free' on
>      it.  Raises `Index_Error' if ITEM cannot be found in LIST.
>      (Requires time proportional to the length of LIST, changes root of
>      LIST.)
> 
>   function Is_Empty (List : List_Type) return Boolean;
> 
>      Returns true if LIST contains no elements, otherwise false.
>      (Requires constant time.)
> 
>   function Length (List : List_Type) return Natural;
> 
>      Returns the number of elements contained in LIST.  (Requires time
>      proportional to the length of LIST.)
> 
>   generic
>      type Item_Access_Index is range <>;
>      type Item_Access_Array is array (Item_Access_Index range <>)
>        of Item_Access;
>   function To_Array (List : List_Type) return Item_Access_Array;
> 
>      Returns an array of all elements contained in LIST, preserving the
>      order of elements.  ITEM_ACCESS_INDEX must include the range from
>      1 to `Length (List)' (otherwise, `Constraint_Error' is raised).
> 
>   generic
>      type Item_Access_Index is range <>;
>      type Item_Access_Array is array (Item_Access_Index range <>)
>        of Item_Access;
>   procedure To_List
>      (Source : in     Item_Access_Array;
>       Target : in out List_Type);
> 
>      Removes all elements from TARGET and replaces them with the
>      elements in SOURCE, preserving order.  (Changes root of TARGET.)
> 
>   generic
>      with procedure Action (Item : Item_Access);
>   procedure For_Each (List : List_Type);
> 
>      Iterates over LIST, i.e. calls ACTION for each element in LIST,
>      obeying the order of elements.  ACTION may destroy or otherwise
>      modify ITEM, or destroy elements before ITEM in LIST.
> 
>   generic
>      with function Predicate (Item : Item_Access) return Boolean;
>   procedure Filter_In_Place (List : in out List_Type);
> 
>      Removes all elements from LIST (using `Remove') for which
>      PREDICATE is false.  The calls to PREDICATE are performed in the
>      order the elements are stored in `List'.  (Changes root of LIST.)
> 
>      See the `Clone' subprogram if you need a filtered copy of a list
>      (which leaves the source list unaffected), or use the following
>      subprogram.
> 
>   generic
>      with function Predicate (Item : Item_Access) return Boolean;
>      type Item_Access_Index is range <>;
>      type Item_Access_Array is array (Item_Access_Index range <>)
>         of Item_Access;
>   function Filter (List : List_Type) return Item_Access_Array;
> 
>      Returns an array of all elements in LIST for which PREDICATE is
>      true, preserving the order of elements.  ITEM_ACCESS_INDEX must
>      include the range from 1 to `Length (List)' (otherwise,
>      `Constraint_Error' is raised).  Internally, `Filter' creates an
>      array with `Length (List)' elements.  Therefore, if you want to
>      select a few elements of a large list, you should probably use
>      `Clone'.
> 
>   generic
>      with function Predicate (Item : Item_Access) return Boolean;
>   function First_That (List : List_Type) return Item_Access;
> 
>      Returns the first element of LIST for which PREDICATE is true, or
>      `No_Item' if there is no such element.
> 
>   generic
>      with function Predicate (Item : Item_Access) return Boolean;
>   procedure Next_That (Item : in out Item_Access);
> 
>      Sets ITEM to the next element in the list after the old ITEM for
>      which PREDICATE is true, or to `No_Item' if there is no such
>      element.
> 
>   generic
>      with function Predicate (Item : Item_Access) return Boolean;
>   function Last_That (List : List_Type) return Item_Access;
> 
>      Returns the last element of LIST for which PREDICATE is true, or
>      `No_Item' if there is no such element.
> 
>   procedure Split
>     (Source             : in out List_Type;
>      Target_1, Target_2 : in out List_Type);
> 
>      Splits SOURCE to TARGET_1 and TARGET_2.  The old lists TARGET_1
>      and TARGET_2 are deallocated.  After a `Split' operation, SOURCE
>      is empty, and TARGET_1 and TARGET_2 contain all elements of
>      SOURCE, and the length difference between TARGET_1 and TARGET_2 is
>      at most 1.  TARGET_1 and TARGET_2 have to be different lists.
>      SOURCE, TARGET_1 and TARGET_2 have to refer to different lists.
>      (Changes root of SOURCE, TARGET_1 and TARGET_2.)
> 
>   generic
>      with function "<="
>        (Left, Right : Item_Access)
>        return Boolean is <>;
>   procedure Merge
>     (Source_1, Source_2 : in out List_Type;
>      Target             : in out List_Type);
> 
>      Merges SOURCE_1 and SOURCE_2 and stores the result in TARGET.  In
>      this case, "merging" means that if both source lists are sorted
>      according to the "<=" predicate, TARGET will be sorted as well.
>      All three lists have to be distinct.  Note that the order in which
>      equal elements are taken from SOURCE_1 and SOURCE_2 and put into
>      TARGET is not defined, so it is not possible to construct a stable
>      sorting procedure based on this routine.  SOURCE_1, SOURCE_2 and
>      TARGET have to denote different lists. (Changes root of SOURCE_1,
>      SOURCE_2 and TARGET.)
> 
>   generic
>      with function "<="
>        (Left, Right : Item_Access)
>        return Boolean is <>;
>   procedure Sort (List : in out List_Type);
> 
>      Sorts LIST according to the "<=" predicate, in place.  The sort
>      operation is _not_ stable. (Changes root of LIST.)

-- 
-- Stephe

Re: A generic list package (long)

[Florian Weimer]

Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:

>> I'm currently working on a general-purpose low-level list package.
>> The existing approaches were either too heavy-weight, too limited, or
>> covered by an unacceptable license.
>>
>> What do you think about the approach documented below?
>
> I've written a list package with similar goals; see
> http://users.erols.com/leakstan/Stephe/Ada/sal.html.

Thanks.  Your collection looks quite nice.

> I find it curious that you expect the client to provide the "next"
> field/operation, rather than declaring a Node_Type containing the
> user's type and a Next field. Can you elaborate on this?

Using this approach, you can save one indirection in the case of
indefinite types.  (The redirection seems necessary as well if you
need a non-constant view of the actual data.)  In such cases, your
approach seems to result in the following:

                                    +-------------- ...
       +------------------+         |
       |         o========#=======>>| actual data
       |                  |         |
       | fields specific  |         +-------------- ...
       | to the container |
       +------------------+


The getter/setter aproach permits the following:

       +------------------+
       | fields specific  |
       | to the container |
       |                  |
       |    actual data   |
       .                  .
       :                  :


And it is still possible to obtain a non-constant view of the actual
data.

> Your approach leaves everything up to the user; mine ensures that
> garbage is collected appropriately, when necessary; the user only
> needs to provide the appropriate 'free' operation.

I think our approaches are not much different in this regard; if an
element is removed, it is 

Re: A generic list package

[Florian Weimer]

Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:

>> I'm currently working on a general-purpose low-level list package.
>> The existing approaches were either too heavy-weight, too limited, or
>> covered by an unacceptable license.
>>
>> What do you think about the approach documented below?
>
> I've written a list package with similar goals; see
> http://users.erols.com/leakstan/Stephe/Ada/sal.html.

Thanks.  Your collection looks quite nice.

> I find it curious that you expect the client to provide the "next"
> field/operation, rather than declaring a Node_Type containing the
> user's type and a Next field. Can you elaborate on this?

Using this approach, you can save one indirection in the case of
indefinite types.  (The redirection seems necessary as well if you
need a non-constant view of the actual data.)  In such cases, your
approach seems to result in the following:

                                    +-------------- ...
       +------------------+         |
       |         o========#=======>>| actual data
       |                  |         |
       | fields specific  |         +-------------- ...
       | to the container |
       +------------------+


The getter/setter aproach permits the following:

       +------------------+
       | fields specific  |
       | to the container |
       |                  |
       |    actual data   |
       .                  .
       :                  :


And it is still possible to obtain a non-constant view of the actual
data.

> Your approach leaves everything up to the user; mine ensures that
> garbage is collected appropriately, when necessary; the user only
> needs to provide the appropriate 'free' operation.

I think our approaches are not much different in this regard; if an
element is removed from a list, it is also freed by my implementation.

Re: A generic list package

[Jeffrey Carter]

Florian Weimer wrote:
> 
> Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:
> 
> > I find it curious that you expect the client to provide the "next"
> > field/operation, rather than declaring a Node_Type containing the
> > user's type and a Next field. Can you elaborate on this?

I would say that this approach does not qualify as an ADT. The client
must understand the internal representation to be used in the list and
declare a set of types and operations appropriately. That does not seem
"abstract".

-- 
Jeff Carter
"If you think you got a nasty taunting this time,
you ain't heard nothing yet!"
Monty Python and the Holy Grail

Re: A generic list package

[Florian Weimer]

Jeffrey Carter <jrcarter@acm.org> writes:

>> > I find it curious that you expect the client to provide the "next"
>> > field/operation, rather than declaring a Node_Type containing the
>> > user's type and a Next field. Can you elaborate on this?
>
> I would say that this approach does not qualify as an ADT. The client
> must understand the internal representation to be used in the list and
> declare a set of types and operations appropriately. That does not seem
> "abstract".

All the data types you can express in Ada cannot qualify as abstract
data types. ;-)

Ada can only provide implementations of abstract data types, and in
the implementation process, some abstraction is always lost.  However,
I agree that the Next_Of/Set_Next interface as at a very low
abstraction level, and it does not represent an implementation of the
usual 'list' ADT (but of another ADT).

Re: A generic list package

[Stephen Leake]

Florian Weimer <Florian.Weimer@RUS.Uni-Stuttgart.DE> writes:

> Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:
> 
> <snip>
> 
> > I find it curious that you expect the client to provide the "next"
> > field/operation, rather than declaring a Node_Type containing the
> > user's type and a Next field. Can you elaborate on this?
> 
> Using this approach, you can save one indirection in the case of
> indefinite types.  (The redirection seems necessary as well if you
> need a non-constant view of the actual data.)  In such cases, your
> approach seems to result in the following:
> 
>                                     +-------------- ...
>        +------------------+         |
>        |         o========#=======>>| actual data
>        |                  |         |
>        | fields specific  |         +-------------- ...
>        | to the container |
>        +------------------+
> 
> 
> The getter/setter aproach permits the following:
> 
>        +------------------+
>        | fields specific  |
>        | to the container |
>        |                  |
>        |    actual data   |
>        .                  .
>        :                  :
> 
> 
> And it is still possible to obtain a non-constant view of the actual
> data.

Yes. I have an indirection and cleaner abstraction; you have less
clean abstraction and no indirection. I guess that's a useful
tradeoff. 

> > Your approach leaves everything up to the user; mine ensures that
> > garbage is collected appropriately, when necessary; the user only
> > needs to provide the appropriate 'free' operation.
> 
> I think our approaches are not much different in this regard; if an
> element is removed from a list, it is also freed by my implementation.

Ok, guess I missed that in your comments.

-- 
-- Stephe

Re: A generic list package

[Lutz Donnerhacke]

* Florian Weimer wrote:
>The getter/setter aproach permits the following:
>
>       +------------------+
>       | fields specific  |
>       | to the container |
>       |                  |
>       |    actual data   |
>       .                  .
>       :                  :

I prefer this the other way around:

        +------------------+
        |    actual data   |
        |                  |
        | fields specific  |
        | to the container |

This allows me to cast pointers ;-)


http://www.iks-jena.de/mitarb/lutz/ada/types/



-- 
   Mailbox der letzten vier Wochen kommentarlos in den Orkus getreten.
   Wichtige Anfragen bitte nochmal senden. Unter Angabe von Msg-ID oder
   markanten Suchworten, kann ich die Mails jedoch heraussuchen.

Re: A generic list package

[Simon Wright]

lutz@iks-jena.de (Lutz Donnerhacke) writes:

> * Florian Weimer wrote:
> >The getter/setter aproach permits the following:
> >
> >       +------------------+
> >       | fields specific  |
> >       | to the container |
> >       |                  |
> >       |    actual data   |
> >       .                  .
> >       :                  :
> 
> I prefer this the other way around:
> 
>         +------------------+
>         |    actual data   |
>         |                  |
>         | fields specific  |
>         | to the container |
> 
> This allows me to cast pointers ;-)

Eeww.

I hope you put representation clauses on your records, then.

Re: A generic list package

[Lutz Donnerhacke]

* Simon Wright wrote:
>lutz@iks-jena.de (Lutz Donnerhacke) writes:
>> I prefer this the other way around:
>> 
>>         +------------------+
>>         |    actual data   |
>>         |                  |
>>         | fields specific  |
>>         | to the container |
>> 
>> This allows me to cast pointers ;-)
>
>Eeww.
>
>I hope you put representation clauses on your records, then.

Not necessary.


-- 
   Mailbox der letzten vier Wochen kommentarlos in den Orkus getreten.
   Wichtige Anfragen bitte nochmal senden. Unter Angabe von Msg-ID oder
   markanten Suchworten, kann ich die Mails jedoch heraussuchen.

Re: A generic list package

[Simon Wright]

lutz@iks-jena.de (Lutz Donnerhacke) writes:

> * Simon Wright wrote:
> >lutz@iks-jena.de (Lutz Donnerhacke) writes:
> >> I prefer this the other way around:
> >> 
> >>         +------------------+
> >>         |    actual data   |
> >>         |                  |
> >>         | fields specific  |
> >>         | to the container |
> >> 
> >> This allows me to cast pointers ;-)
> >
> >Eeww.
> >
> >I hope you put representation clauses on your records, then.
> 
> Not necessary.

What makes you think that the order the compiler lays out the record
is the same as the order you wrote the components in?

Re: A generic list package

[Lutz Donnerhacke]

* Simon Wright wrote:
>lutz@iks-jena.de (Lutz Donnerhacke) writes:
>> >lutz@iks-jena.de (Lutz Donnerhacke) writes:
>> >> I prefer this the other way around:
>> >> 
>> >>         +------------------+
>> >>         |    actual data   |
>> >>         |                  |
>> >>         | fields specific  |
>> >>         | to the container |
>> >> 
>> >> This allows me to cast pointers ;-)
>
>What makes you think that the order the compiler lays out the record
>is the same as the order you wrote the components in?

The tagged record type to be extened is already finalized. I do not care how
the compiler adds the data structure componds, but (automatic) type
conversions between parent and derivated types become very difficult if the
extension fields are mixed with the parent ones.

In conclusion: I program unportable unless I find the rule in the RM.

-- 
   Mailbox der letzten vier Wochen kommentarlos in den Orkus getreten.
   Wichtige Anfragen bitte nochmal senden. Unter Angabe von Msg-ID oder
   markanten Suchworten, kann ich die Mails jedoch heraussuchen.