Re: List container strawman

[ramatthews@tinuviel.com]

In article <bgR13FMw5mIK@eisner.encompasserve.org>, Kilgallen@SpamCop.net (Larry Kilgallen) wrote:
> In article <3BE58FDD.E1FB1815@san.rr.com>, Darren New <dnew@san.rr.com> 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;
-------------------------------------------------------------