Re: A generic list package (long)

[Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov>]

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