A generic list package (long)

[Florian Weimer <fw@deneb.enyo.de>]

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