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 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-09-02 15:40:49 PST Path: archiver1.google.com!newsfeed.google.com!newsfeed.stanford.edu!canoe.uoregon.edu!hammer.uoregon.edu!skates!not-for-mail From: Stephen Leake Newsgroups: comp.lang.ada Subject: Re: A generic list package (long) Date: 02 Sep 2001 18:29:47 -0400 Organization: NASA Goddard Space Flight Center Message-ID: References: <87ae0dp7gn.fsf@deneb.enyo.de> NNTP-Posting-Host: anarres.gsfc.nasa.gov Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: skates.gsfc.nasa.gov 999469843 8081 128.183.220.71 (2 Sep 2001 22:30:42 GMT) X-Complaints-To: dscoggin@cne-odin.gsfc.nasa.gov NNTP-Posting-Date: 2 Sep 2001 22:30:42 GMT User-Agent: Gnus/5.0808 (Gnus v5.8.8) Emacs/20.7 Xref: archiver1.google.com comp.lang.ada:12644 Date: 2001-09-02T22:30:42+00:00 List-Id: Florian Weimer 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