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,ce0900b60ca3f616 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-11-07 15:46:15 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!isdnet!newsfeed.icl.net!newspeer.clara.net!news.clara.net!news5-gui.server.ntli.net!ntli.net!news6-win.server.ntlworld.com.POSTED!tinuviel!ramint From: ramatthews@tinuviel.com Newsgroups: comp.lang.ada Subject: Re: List container strawman References: <3BE29AF4.80804@telepath.com><3BE29BD4.10401@telepath.com><3BE2DB99.B707D409@boeing.com><3BE32A18.18404AD1@boeing.com><3BE443DE.574D669C@acm.org><3BE58FDD.E1FB1815@san.rr.com> X-Newsreader: Pan 0.7.6 Message-ID: Date: Wed, 07 Nov 2001 19:07:05 +0000 NNTP-Posting-Host: 62.252.8.130 X-Complaints-To: abuse@ntlworld.com X-Trace: news6-win.server.ntlworld.com 1005176461 62.252.8.130 (Wed, 07 Nov 2001 23:41:01 GMT) NNTP-Posting-Date: Wed, 07 Nov 2001 23:41:01 GMT Organization: ntlworld News Service Xref: archiver1.google.com comp.lang.ada:16025 Date: 2001-11-07T19:07:05+00:00 List-Id: In article , Kilgallen@SpamCop.net (Larry Kilgallen) wrote: > In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New writes: > >> If you really want it to be foolproof, > > Yes please. While I see a foolproof list does not have universal appeal I have been successfully using one for some time so I thought its specification would help discussions. Robert Matthews ----------------------------------------------------- with Ada.Finalization; with Ada.IO_Exceptions; with Ada.Streams; with Ada.Tags; generic type Data_Type (<>) is private; package Containers.Lists.Unbounded is -- This package provides facilities for manipulating simple list structures. -- -- A list is an ordered sequence of data elements. It can also be empty, -- containing no data elements. -- -- Client software creates an empty list by declaring a variable of type -- List_Type. Data elements can then be added to the list via the subprograms -- Prepend and Append. Note that data is copied into the list - pointers are not -- retained to the original data. -- -- All data elements can be removed from a list via subprogram Delete_All. -- Applying this subprogram to an already empty list will have no effect. -- -- When applied to an empty list, Is_Empty will return True, otherwise it will -- return False. -- -- A list can be assigned to another. The target list will be emptied then loaded with -- a copy of each data element in the source list. The copying will be done such that -- the ordering of the data elements in each list will be the same. -- Note that if the source list is empty, then the target will be set empty. -- -- Two lists can be compared for equality. To be equal they must have equal data elements -- at corresponding positions. Two empty lists are considered equal. -- -- The elements in a list can be accessed via an enumerator: the client software -- declares a variable of type Enumerator_Type which it then attaches to a list via -- the function New_Enumerator. -- -- At any one time an enumerator denotes a single element in its associated list. This -- element is termed the "current" element. Initially current will be set to the first -- element in the list; the following subprograms allow current to move to a different -- element: Goto_Next, Goto_Previous, Goto_First, Goto_Last. -- -- The following subprograms allow an enumerator's current element to be retrieved, -- changed, or deleted: Current, Update, Delete. Note that after Delete, current -- still denotes the same point in the list, even though the associated data -- element no longer exists. -- -- The subprogram Insert allows a new data element to be added to the list either -- before or after the current element. Note that if the list is empty then this -- subprogram will still insert the data even though current does not exist. -- Alternatively if current has been deleted then Insert will insert the data at -- the point in the list from which current was deleted. -- After the insertion, current will be set to the new data element. -- -- When current is at the start of a list, Is_First will return True, -- otherwise it will return False. -- When current is at the end of a list, Is_Last will return True, -- otherwise it will return False. -- -- If current exists Current_Exists will return True, otherwise it will return False -- (current will not exist if the element denoted by current has been deleted, or if -- the associated list is empty). -- -- If the list associated with an enumerator exists List_Exists will return True, otherwise -- it will return False (a list can cease to exist if the list's variable goes out of scope). -- -- An enumerator can be assigned to another enumerator. The target enumerator will then -- be associated with the same list and denote the same current element. Note that -- if the source enumerator's list and/or current do not exist then these characteristics -- will be transferred to the target enumerator. -- -- Two enumerators can be compared for equality. They must be associated with the same -- list and their current elements must be the same element. Note that two enumerators whose -- lists do not exist are deemed equal. Also two enumerators whose lists exist but whose current -- elements do not, are deemed equal if: -- 1) the lists are the same and empty; or -- 2) the lists are the same and non-empty, and each current denotes the same point in the list. -- -- Note that two or more enumerators can change the same list; changes made via one enumerator -- will be visible to the other enumerators. Similarly changes made directly to a list will be -- visible to its enumerators. However, concurrent access from more than one task is not supported; -- concurrent access may well lead to list and enumerator corruption. -- -- Note also that the storage associated with lists and enumerators is automatically deallocated -- when their variables go out of scope. -- -- Stream input/output can be used with lists via the stream oriented attributes List_Type'Write -- and List_Type'Read. -- For the Write attribute, each data element in the list is sent to the stream via -- Data_Type'Output. -- For the Read attribute, data elements are extracted from the stream (via Data_Type'Input) -- and inserted into the list. Note that any data elements previously in the list will be deleted. -- Note also that an empty list will be suitably flagged in the stream data, and so will be -- correctly handled when read back in. -- -- -- When applied to an empty list, the following will raise No_Data: -- Goto_First, Goto_Last, Goto_Next, Goto_Previous, Is_First, Is_Last. -- -- When current is the last data element in a list, Goto_Next will raise No_Data. -- When current is the first data element in a list, Goto_Previous will raise No_Data. -- -- When current does not exist, the following will raise No_Data: -- Delete, Current, Update. -- -- When an enumerator's list does not exist, the following will raise No_List: -- Insert, Delete, Current, Update, Goto_First, Goto_Last, Goto_Next, Goto_Previous, -- Is_First, Is_Last, Current_Exists, Is_Empty[Enumerator_Type]. -- -- When the stream I/O attributes are used, the following exceptions may be raised: -- Device_Error, Data_Error, Constraint_Error, Tag_Error, End_Error and Mode_Error. -- See the Ada Reference Manual for details. -- ------------------------------------------------------------------------------------------------ type List_Type is tagged private; type Enumerator_Type is private; -- Subprograms for directly dealing with lists... procedure Prepend (List : in out List_Type; Data : in Data_Type); -- Insert data at start of list. procedure Append (List : in out List_Type; Data : in Data_Type); -- Insert data at end of list. procedure Delete_All (List : in out List_Type); -- Delete all data from list. function Is_Empty (List : in List_Type) return Boolean; function "=" (Left : in List_Type; -- Check lists have equal. Right : in List_Type) return Boolean; -- elements at matching positions. function New_Enumerator (List : in List_Type'Class) return Enumerator_Type; -- Enumerator will denote the list and its current will be the first in the list. -- Note: can also assign list to list: target list will contain a copy of all the elements in the source -- list, with each element and its copy having the same position in their respective lists. ---------------------------------------------------------------------- -- Subprograms for dealing with the current element of an enumerator... type Position_Type is (Before_Current, After_Current); procedure Insert (Enumerator : in out Enumerator_Type; Data : in Data_Type; Position : in Position_Type); procedure Delete (Enumerator : in Enumerator_Type); function Current (Enumerator : in Enumerator_Type) return Data_Type; procedure Update (Enumerator : in out Enumerator_Type; Data : in Data_Type); -- Update current element. -- Note that if new data is larger, then new data will be loaded into a new element that replaces -- the old in the list. The location in the list will not have changed but current will now denote -- that new data element - hence the in out mode. procedure Goto_First (Enumerator : in out Enumerator_Type); procedure Goto_Last (Enumerator : in out Enumerator_Type); procedure Goto_Next (Enumerator : in out Enumerator_Type); procedure Goto_Previous (Enumerator : in out Enumerator_Type); function Is_First (Enumerator : in Enumerator_Type) return Boolean; function Is_Last (Enumerator : in Enumerator_Type) return Boolean; function Current_Exists (Enumerator : in Enumerator_Type) return Boolean; function List_Exists (Enumerator : in Enumerator_Type) return Boolean; function Is_Empty (Enumerator : in Enumerator_Type) return Boolean; -- Is the associated list empty. function "=" (Left : in Enumerator_Type; Right : in Enumerator_Type) return Boolean; -- Note: can also assign enumerator to enumerator: target will denote same list -- and have same current as source. -------------------------------------------------------- -- The subprograms can raise the following exceptions: No_Data : exception; No_List : exception; -- And for stream I/O... Device_Error : exception renames Ada.IO_Exceptions.Device_Error; Data_Error : exception renames Ada.IO_Exceptions.Data_Error; End_Error : exception renames Ada.IO_Exceptions.End_Error; Mode_Error : exception renames Ada.IO_Exceptions.Mode_Error; Tag_Error : exception renames Ada.Tags.Tag_Error; -- Also Constraint_Error may be raised. --------------------------------------------------- private type Data_Access_Type is access Data_Type; type Data_Envelope_Type; type Data_Envelope_Access_Type is access Data_Envelope_Type; type Enumerator_Envelope_Type; type Enumerator_Envelope_Access_Type is access Enumerator_Envelope_Type; type List_Header_Type; type List_Header_Access_Type is access List_Header_Type; type Data_Envelope_Type is record Data : Data_Access_Type; Next : Data_Envelope_Access_Type; Previous : Data_Envelope_Access_Type; end record; type List_Header_Type is record First : Data_Envelope_Access_Type; Last : Data_Envelope_Access_Type; Enumerators : Enumerator_Envelope_Access_Type; -- Sub-list of enumerators attached to this List. end record; type List_Type is new Ada.Finalization.Controlled with record Header : List_Header_Access_Type; end record; procedure Initialize (List : in out List_Type); procedure Adjust (List : in out List_Type); procedure Finalize (List : in out List_Type); procedure List_Write (Stream : access Ada.Streams.Root_Stream_Type'Class; Item : in List_Type); for List_Type'Write use List_Write; procedure List_Read (Stream : access Ada.Streams.Root_Stream_Type'Class; Item : out List_Type); for List_Type'Read use List_Read; type Enumerator_Envelope_Type is record List_Header : List_Header_Access_Type; -- List that Enumerator applies to. Current : Data_Envelope_Access_Type; -- List element that Enumerator denotes. Next_Enumerator : Enumerator_Envelope_Access_Type; -- Enumerators are linked in their own sub-list, Previous_Enumerator : Enumerator_Envelope_Access_Type; -- within the relevant List. Next_Data : Data_Envelope_Access_Type; -- List element that follows current. Previous_Data : Data_Envelope_Access_Type; -- List element that precedes current. end record; -- Note that in the above record, components Next_Data and Previous_Data duplicate the Next and Previous -- components of the record referenced by Current. This duplication is necessary for the case when Current -- is Null (ie. the corresponding data element has been deleted), Next_Data and Previous_Data then indicate -- where in the list the enumerator is. type Enumerator_Type is new Ada.Finalization.Controlled with record Header : Enumerator_Envelope_Access_Type; end record; procedure Initialize (Enumerator : in out Enumerator_Type); procedure Adjust (Enumerator : in out Enumerator_Type); procedure Finalize (Enumerator : in out Enumerator_Type); end Containers.Lists.Unbounded; -------------------------------------------------------------