From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,2510538eb4348710,start X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-09-02 14:53:26 PST Path: archiver1.google.com!newsfeed.google.com!newsfeed.stanford.edu!news.tele.dk!small.news.tele.dk!193.174.75.178!news-fra1.dfn.de!news-koe1.dfn.de!news-han1.dfn.de!news.fh-hannover.de!news.cid.net!news.enyo.de!news1.enyo.de!not-for-mail From: Florian Weimer Newsgroups: comp.lang.ada Subject: A generic list package (long) Date: Mon, 03 Sep 2001 00:13:12 +0200 Organization: Enyo's not your organization Message-ID: <87ae0dp7gn.fsf@deneb.enyo.de> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Xref: archiver1.google.com comp.lang.ada:12642 Date: 2001-09-03T00:13:12+02:00 List-Id: 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.)