CVS difference for ais/ai-00302.txt

Differences between 1.2 and version 1.3
Log of other versions for file ais/ai-00302.txt

--- ais/ai-00302.txt	2002/10/01 03:08:54	1.2
+++ ais/ai-00302.txt	2002/10/04 23:11:06	1.3
@@ -1,4 +1,4 @@
-!standard A.16                                      02-06-13  AI95-00302/01
+!standard A.16                                      02-10-04  AI95-00302/02
 !class amendment 02-06-13
 !status work item 02-06-13
 !status received 02-06-10
@@ -27,35 +27,35 @@
 
 !proposal
 
-The data structure components of the PragmAda Reusable Components should
-be adopted as the basis for a standard data structure library.
+Data structure components similar to those of the PragmAda Reusable
+Components are proposed as a standard data structure library.
 
 !wording
 
 A.X Data Structures
 
-This clause presents the specifications of the package Something and
+This clause presents the specifications of the package Ada.Containers and
 several child packages, which provide abstract data types representing
 basic, common data structures. Lists, queues, stacks, bags, and skip
 lists are supported.
 
-A.X.1 The Package Something
+A.X.1 The Package Ada.Containers
 
-The package Something provides declarations common to the
+The package Ada.Containers provides declarations common to the
 data-structures packages.
 
 Static Semantics
 
-The library package Something has the following declaration:
+The library package Ada.Containers has the following declaration:
 
-package Something is
+package Ada.Containers is
     pragma Pure;
 
     Empty_Structure_Error    : exception;
     Full_Structure_Error     : exception;
     Storage_Exhaustion_Error : exception;
     Too_Short_Error          : exception;
-end Something;
+end Ada.Containers;
 
 The exception Empty_Structure_Error is raised by operations when an
 attempt is made to access data in an empty structure.
@@ -71,9 +71,558 @@
 bounded structures if the destination structure does not have a large
 enough maximum size to hold the data in the source structure.
 
+A.X.2 Unprotected Bounded-Length List Handling
+
+The language-defined package Ada.Containers.List_Bounded_Unprotected provides
+a generic package each of whose instances yields a limited private type
+Handle, a private type Position, and a set of operations. An object of a
+particular List_Bounded_Unprotected Handle type represents a list whose
+length can vary conceptually between 0 and a maximum size established at
+the declaration of the object. Object of type Position are used to
+indicate values of type Element stored in a list.
+
+Static Semantics
+
+The library package Ada.Containers.List_Bounded_Unprotected has the following
+declaration:
+
+generic -- Ada.Containers.List_Bounded_Unprotected
+    type Element is limited private;
+
+    with procedure Assign (To   :    out Element;
+                           From : in     Element) is <>;
+package Ada.Containers.List_Bounded_Unprotected is
+    pragma Preelaborate;
+
+    type Handle (Max_Size : Positive) is limited private;
+
+    type Position is private;
+
+    Position_Error : exception;
+
+    procedure Assign (To : out Handle; From : in Handle);
+
+    procedure Clear (List : in out Handle);
+
+    -- Operations to obtain valid positions for lists:
+    function First    (List : Handle) return Position;
+    function Last     (List : Handle) return Position;
+    function Off_List (List : Handle) return Position;
+
+    -- Operations to obtain valid positions from valid positions:
+    function Next (Pos : Position; List : Handle) return Position;
+    function Prev (Pos : Position; List : Handle) return Position;
+
+    -- Operations to manipulate lists
+    procedure Insert (Into    : in out Handle;
+                      Item    : in     Element;
+                      Before  : in     Position;
+                      New_Pos :    out Position);
+
+    procedure Append (Into    : in out Handle;
+                      Item    : in     Element;
+                      After   : in     Position;
+                      New_Pos :    out Position);
+
+    procedure Delete (From : in out Handle;
+                      Pos  : in out Position);
+
+    function Get (From : Handle; Pos : Position) return Element;
+
+    procedure Put (Into : in out Handle;
+                   Pos  : in     Position;
+                   Item : in     Element);
+
+    function Is_Empty (List : Handle) return Boolean;
+
+    function Is_Full (List : Handle) return Boolean;
+
+    function Length (List : Handle) return Natural;
+
+    generic -- Iterate
+       type Context_Data (<>) is limited private;
+
+       with procedure Action (Item     : in out Element;
+                              Context  : in out Context_Data;
+                              Pos      : in     Position;
+                              Continue :    out Boolean);
+    procedure Iterate (Over    : in out Handle;
+                       Context : in out Context_Data);
+private -- Ada.Containers.List_Bounded_Unprotected
+    -- not specified by the language
+end Ada.Containers.List_Bounded_Unprotected;
+
+A list is a sequence of Elements. Each Element in the sequence may be
+accessed through a Position; we say that the Position indicates the
+Element. Elements may be added to, deleted from, accessed, or modified
+in a list at any position. Using First and Next, a list may be traversed
+from the first Element to the last; using Last and Prev, from the last
+Element to the first.
+
+An object of type Handle is initially empty. An object of type Position
+is initially invalid. Handle's discriminant, Max_Size, is the maximum
+number of Elements that may be stored in a list.
+
+    procedure Assign (To : out Handle; From : in Handle);
+
+If To and From are the same list, Assign has no effect.
+
+If To.Max_Size <= Length (From), Ada.Containers.Too_Short_Error is propagated.
+
+Otherwise, To is cleared and made into a copy of From.
+
+Precondition:  To.Max_Size <= Length (From)
+Postcondition: Length (To) = Length (From)
+
+    procedure Clear (List : in out Handle);
+
+This procedure makes List empty.
+
+Postcondition: Is_Empty (List)
+               Length (List) = 0
+
+Note: Clear effectively deletes all nodes in a list. Therefore, Position_Error
+is propagated if a Position, obtained before Clear is called, is used to
+access the list after Clear is called.
+
+    function First (List : Handle) return Position;
+
+This function returns a Position indicating the first Element in List.
+If List is empty, this is the same as Off_List (List).
+
+    function Last (List : Handle) return Position;
+
+This function returns a Position indicating the last Element in List. If
+List is empty, this is the same as Off_List (List).
+
+    function Off_List (List : Handle) return Position;
+
+This function returns a Position that is valid for List but indicates no
+Element in List. This is the same Position returned by Next (Last
+(List), List) and by Prev (First (List), List).
+
+    function Next (Pos : Position; List : Handle) return Position;
+
+If Pos is not a valid Position for List, Position_Error is propagated.
+
+If Pos = Last (List), this function returns Off_List (List).
+If Pos = Off_List (List), this function returns First (List).
+
+Otherwise, this function returns a Position that indicates the next
+Element in List after the Element indicated by Pos.
+
+    function Prev (Pos : Position; List : Handle) return Position;
+
+If Pos is not a valid Position for List, Position_Error is propagated.
+
+If Pos = First (List), this function returns Off_List (List).
+If Pos = Off_List (List), this function returns Last (List).
+
+Otherwise, this function returns a Position that indicates the previous
+Element in List before the Element indicated by Pos.
+
+    procedure Insert (Into    : in out Handle;
+                      Item    : in     Element;
+                      Before  : in     Position;
+                      New_Pos :    out Position);
+
+If Into is full, Ada.Containers.Full_Structure_Error is propagated.
+
+If Before is not a valid Position for Into, Position_Error is propagated.
+
+If Into is empty and Before /= Off_List (Into), Position_Error is
+propagated.
+
+If Before = Off_List (List), Item is added as the last Element in Into.
+
+Otherwise, Item is inserted into Into before the Element indicated by
+Before.
+
+New_Pos becomes a valid Position for Into that indicates Item.
+
+Precondition:  not Is_Full (Into)
+Postcondition: Prev (Before, Into) = New_Pos
+
+    procedure Append (Into    : in out Handle;
+                      Item    : in     Element;
+                      After   : in     Position;
+                      New_Pos :    out Position);
+
+If Into is full, Ada.Containers.Full_Structure_Error is propagated.
+
+If After is not a valid Position for Into, Position_Error is propagated.
+
+If Into is empty and After /= Off_List (Into), Position_Error is propagated.
+
+If After = Off_List (List), Item is added as the first Element in Into.
+
+Otherwise, Item is inserted into Into after the Element indicated by After.
+
+New_Pos becomes a valid Position for Into that indicates Item.
+
+Precondition:  not Is_Full (Into)
+Postcondition: Next (After, Into) = New_Pos
+
+    procedure Delete (From : in out Handle;
+                      Pos  : in out Position);
+
+If From is empty, Ada.Containers.Empty_Structure_Error is propagated.
+
+If Pos is not a valid Position for From or Pos = Off_List (From),
+Position_Error is propagated.
+
+Otherwise, the Element indicated by Pos is removed from From. Pos is
+made invalid.
+
+Elements are stored in "nodes" in a list. A Position indicates an
+Element by indicating its node. One Position may indicate a node that
+has been deleted through another Position. Position_Error is propagated
+if such a Position is subsequently used to access the list.
+
+Precondition:  not Is_Empty (From)
+Postcondition: not Is_Full (From)
+
+    function Get (From : Handle; Pos : Position) return Element;
+
+If From is empty, Ada.Containers.Empty_Structure_Error is propagated.
+
+If Pos is not a valid Position for From or Pos = Off_List (From),
+Position_Error is propagated.
+
+Otherwise, this function returns the Element in From indicated by Pos.
+
+Precondition: not Is_Empty (From)
+
+    procedure Put (Into : in out Handle;
+                   Pos  : in     Position;
+                   Item : in     Element);
+
+If Into is empty, Ada.Containers.Empty_Structure_Error is propagated.
+
+If Pos is not a valid Position for Into or Pos = Off_List (Into),
+Position_Error is propagated.
+
+Otherwise, the Element in Into indicated by Pos is made to be Item.
+
+Precondition: not Is_Empty (Into)
+
+    function Is_Empty (List : Handle) return Boolean;
+
+This function returns True if List is empty and False otherwise.
+
+    function Is_Full (List : Handle) return Boolean;
+
+This function returns True if List is full and False otherwise.
+
+    function Length (List : Handle) return Natural;
+
+This function returns the number of Elements stored in List.
+
+    generic -- Iterate
+       type Context_Data (<>) is limited private;
+
+       with procedure Action (Item     : in out Element;
+                              Context  : in out Context_Data;
+                              Pos      : in     Position;
+                              Continue :    out Boolean);
+    procedure Iterate (Over    : in out Handle;
+                       Context : in out Context_Data);
+
+An instance of this procedure applies Action to each Element stored in
+Over and its Position in turn, from first to last. If Action sets
+Continue to False, this procedure returns immediately, without
+processing any remaining Elements in Over. Context is passed to Action
+to represent any context data that Action needs to access or modify.
+
+It is a bounded error to modify a list while iterating over it. Possible
+consequences are: propagating Position_Error, propagating
+Constraint_Error, not processing some of the Elements stored in Over,
+processing some of the Elements twice, and normal processing.
+
+Implementation Permission
+
+An implementation may reuse deleted nodes, even if that means it cannot
+guarantee that Position_Error will be propagated when a Position that
+indicates a deleted node is used to access the list.
+
+A.X.3 Unprotected Unbounded-Length List Handling
+
+The language-defined package Ada.Containers.List_Unbounded_Unprotected
+provides a generic package each of whose instances yields a limited
+private type Handle, a private type Position, and a set of operations.
+An object of a particular List_Bounded_Unprotected Handle type
+represents a list whose length can vary conceptually between 0 and a
+maximum size established by available storage. Objects of type Position
+are used to indicate values of type Element stored in a list. The
+subprograms for bounded lists are overloaded for unbounded lists, except
+Is_Full.
+
+Static Semantics
+
+The library package Ada.Containers.List_Unbounded_Unprotected has the
+following declaration:
+
+generic -- Ada.Containers.List_Unbounded_Unprotected
+    type Element is limited private;
+
+    with procedure Assign (To   :    out Element;
+                           From : in     Element) is <>;
+package Ada.Containers.List_Unbounded_Unprotected is
+    pragma Preelaborate;
+
+    type Handle is limited private;
+
+    type Position is private;
+
+    Position_Error : exception;
+
+    procedure Assign (To : out Handle; From : in Handle);
+
+    procedure Clear (List : in out Handle);
+
+    -- Operations to obtain valid positions for lists:
+    function First    (List : Handle) return Position;
+    function Last     (List : Handle) return Position;
+    function Off_List (List : Handle) return Position;
+
+    -- Operations to obtain valid positions from valid positions:
+    function Next (Pos : Position; List : Handle) return Position;
+    function Prev (Pos : Position; List : Handle) return Position;
+
+    -- Operations to manipulate lists
+    procedure Insert (Into    : in out Handle;
+                      Item    : in     Element;
+                      Before  : in     Position;
+                      New_Pos :    out Position);
+
+    procedure Append (Into    : in out Handle;
+                      Item    : in     Element;
+                      After   : in     Position;
+                      New_Pos :    out Position);
+
+    procedure Delete (From : in out Handle;
+                      Pos  : in out Position);
+
+    function Get (From : Handle; Pos : Position) return Element;
+
+    procedure Put (Into : in out Handle;
+                   Pos  : in     Position;
+                   Item : in     Element);
+
+    function Is_Empty (List : Handle) return Boolean;
+
+    function Length (List : Handle) return Natural;
+
+    generic -- Iterate
+       type Context_Data (<>) is limited private;
+
+       with procedure Action (Item     : in out Element;
+                              Context  : in out Context_Data;
+                              Pos      : in     Position;
+                              Continue :    out Boolean);
+    procedure Iterate (Over    : in out Handle;
+                       Context : in out Context_Data);
+private -- Ada.Containers.List_Unbounded_Unprotected
+    -- not specified by the language
+end Ada.Containers.List_Unbounded_Unprotected;
+
+A list is a sequence of Elements. Each Element in the sequence may be
+accessed through a Position; we say that the Position indicates the
+Element. Elements may be added to, deleted from, accessed, or modified
+in a list at any position. Using First and Next, a list may be traversed
+from the first Element to the last; using Last and Prev, from the last
+Element to the first.
+
+An object of type Handle is initially empty. An object of type Position
+is initially invalid.
+
+    procedure Assign (To : out Handle; From : in Handle);
+
+If To and From are the same list, Assign has no effect.
+
+Otherwise, To is cleared and made into a copy of From.
 
+If, after clearing To, there is insufficient storage to allocate list
+nodes for copies of all the Elements in From, Storage_Exhaustion_Error
+is propagated.
 
+Postcondition: Length (To) = Length (From)
 
+    procedure Clear (List : in out Handle);
+
+This procedure makes List empty.
+
+Postcondition: Is_Empty (List)
+                Length (List) = 0
+
+    function First (List : Handle) return Position;
+
+This function returns a Position indicating the first Element in List.
+If List is empty, this is the same as Off_List (List).
+
+    function Last (List : Handle) return Position;
+
+This function returns a Position indicating the last Element in List. If
+List is empty, this is the same as Off_List (List).
+
+    function Off_List (List : Handle) return Position;
+
+This function returns a Position that is valid for List but indicates no
+Element in List. This is the same Position returned by Next (Last
+(List), List) and by Prev (First (List), List).
+
+    function Next (Pos : Position; List : Handle) return Position;
+
+If Pos is not a valid Position for List, Position_Error is propagated.
+
+If Pos = Last (List), this function returns Off_List (List).
+
+If Pos = Off_List (List), this function returns First (List).
+
+Otherwise, this function returns a Position that indicates the next
+Element in List after the Element indicated by Pos.
+
+    function Prev (Pos : Position; List : Handle) return Position;
+
+If Pos is not a valid Position for List, Position_Error is propagated.
+
+If Pos = First (List), this function returns Off_List (List).
+
+If Pos = Off_List (List), this function returns Last (List).
+
+Otherwise, this function returns a Position that indicates the previous
+Element in List before the Element indicated by Pos.
+
+    procedure Insert (Into    : in out Handle;
+                      Item    : in     Element;
+                      Before  : in     Position;
+                      New_Pos :    out Position);
+
+If Before is not a valid Position for Into, Position_Error is propagated.
+
+If Into is empty and Before /= Off_List (Into), Position_Error is
+propagated.
+
+If there is insufficient storage to allocate a new list node,
+Storage_Exhaustion_Error is propagated.
+
+If Before = Off_List (List), Item is added as the last Element in Into.
+
+Otherwise, Item is inserted into Into before the Element indicated by
+Before.
+
+New_Pos becomes a valid Position for Into that indicates Item.
+
+Postcondition: Prev (Before, Into) = New_Pos
+
+    procedure Append (Into    : in out Handle;
+                      Item    : in     Element;
+                      After   : in     Position;
+                      New_Pos :    out Position);
+
+If After is not a valid Position for Into, Position_Error is propagated.
+
+If Into is empty and After /= Off_List (Into), Position_Error is propagated.
+
+If there is insufficient storage to allocate a new list node,
+Storage_Exhaustion_Error is propagated.
+
+If After = Off_List (List), Item is added as the first Element in Into.
+
+Otherwise, Item is inserted into Into after the Element indicated by After.
+
+New_Pos becomes a valid Position for Into that indicates Item.
+
+Postcondition: Next (After, Into) = New_Pos
+
+    procedure Delete (From : in out Handle;
+                      Pos  : in out Position);
+
+If From is empty, Ada.Containers.Empty_Structure_Error is propagated.
+
+If Pos is not a valid Position for From or Pos = Off_List (From),
+Position_Error is propagated.
+
+Otherwise, the Element indicated by Pos is removed from From. Pos is
+made invalid.
+
+Elements are stored in "nodes" in a list. A Position indicates an
+Element by indicating its node. One Position may indicate a node that
+has been deleted through another Position. Position_Error is propagated
+if such a Position is subsequently used to access the list.
+
+Clear effectively deletes all nodes in a list. Therefore, Position_Error
+is propagated if a Position, obtained before Clear is called, is used to
+access the list after Clear is called.
+
+Precondition:  not Is_Empty (From)
+
+    function Get (From : Handle; Pos : Position) return Element;
+
+If Pos is not a valid Position for From or Pos = Off_List (From),
+Position_Error is propagated.
+
+Otherwise, this function returns the Element in From indicated by Pos.
+
+Precondition: not Is_Empty (From)
+
+    procedure Put (Into : in out Handle;
+                   Pos  : in     Position;
+                   Item : in     Element);
+
+If Into is empty, Ada.Containers.Empty_Structure_Error is propagated.
+
+If Pos is not a valid Position for Into or Pos = Off_List (Into),
+Position_Error is propagated.
+
+Otherwise, the Element in Into indicated by Pos is made to be Item.
+
+Precondition: not Is_Empty (Into)
+
+    function Is_Empty (List : Handle) return Boolean;
+
+This function returns True if List is empty and False otherwise.
+
+    function Length (List : Handle) return Natural;
+
+This function returns the number of Elements stored in List.
+
+    generic -- Iterate
+       type Context_Data (<>) is limited private;
+
+       with procedure Action (Item     : in out Element;
+                              Context  : in out Context_Data;
+                              Pos      : in     Position;
+                              Continue :    out Boolean);
+    procedure Iterate (Over    : in out Handle;
+                       Context : in out Context_Data);
+
+An instance of this procedure applies Action to each Element stored in
+Over and its Position in turn, from first to last. If Action sets
+Continue to False, this procedure returns immediately, without
+processing any remaining Elements in Over. Context is passed to Action
+to represent any context data that Action needs to access or modify.
+
+It is a bounded error to modify a list while iterating over it. Possible
+consequences are: propagating Position_Error, propagating
+Constraint_Error, not processing some of the Elements stored in Over,
+processing some of the Elements twice, and normal processing.
+
+Implementation Permission
+
+An implementation may reuse deleted nodes, even if that means it cannot
+guarantee that Position_Error will be propagated when a Position that
+indicates a deleted node is used to access the list.
+
+Implementation Requirements
+
+No storage associated with a Handle object shall be lost upon scope
+exit, a call to Clear or Delete, or being associated with the parameter
+To of a call to Assign.
+
+
+
+
 [For other package specifications in this set, refer to the PragmARCs.
 The PragmARCs may be obtained from
 
@@ -102,25 +651,15 @@
 rather than separately as in the ARM. These should serve as a good
 starting point for creating the desired ARM wording.]
 
-!example
-
-[This section does not seem relevant for such a proposal, given the very
-general nature of the problem. Providing examples of the use of each
-data structure would be very lengthy, and would not seem to add much to
-the proposal.]
-
 !discussion
 
-Package Something contains the declarations of exceptions common to many
-of the data-structures packages.
-
 This package is based on the PragmAda Reusable Components, which declare
 an exception named Storage_Exhausted. This exception is used rather than
 propagating Storage_Error primarily to allow a client to easily
 distinguish between memory problems with the PragmARCs (fairly rare) and
 memory problems with the client's code (more likely).
 Storage_Exhaustion_Error is the equivalent exception in package
-Something. It may be desirable to eliminate this distinction for
+Ada.Containers. It may be desirable to eliminate this distinction for
 standard components and simply propagate Storage_Error.
 
 The PragmARCs have been designed to be useful on real world problems. As
@@ -132,7 +671,7 @@
 this decision is that it allows structures of structures, something that
 has been needed by users of the PragmARCs.
 
-Some ramifications of this design decision are:
+A ramification of this design decision is:
 
 Many clients need to instantiate these packages with Element
 types for which Assign would simply be an assignment statement. Having
@@ -140,19 +679,204 @@
 best addressed in Ada by a generic. An instantiation of procedure
 PragmARC.Assignment creates the required Assign procedure.
 
-ARM 6.4.1 seems to imply that a check may be made of the value of a
-scalar parameter of mode "in out" before it is copied in. Since the data
-structures will declare uninitialized variables of the Element type and
-pass them as the To parameter of Assign, this check could fail if
-Element is a scalar subtype. To
-avoid this requires that the client create a record type with a single
-component of the scalar subtype, and create an Assign procedure for this
-record type. Again, this is repetitive. An instantiation of
-PragmARC.Scalar_Wrapping creates the record type and the Assign
-procedure. It would be nice if my interpretation of the ARM is
-incorrect, and this extra step is unnecessary. Luckily, structures of
-scalars seem to be rare in real world projects.
 
+A.X.1 Package Ada.Containers
+
+Package Ada.Containers contains the declarations of exceptions common to many
+of the data-structures packages.
+
+A.X.2 Unprotected Bounded-Length List Handling
+
+Protected lists may not be a very high priority, but one very useful
+component for concurrent programs is a protected queue. This proposal
+does present concurrent queue components, so the distinction is
+preserved for all structures.
+
+Given a type such as Handle, it is clear that the use of controlled
+types does not allow assignment between objects with different maximum
+sizes, even when the logical value to be assigned will fit in the
+destination object. This requires that assignment be performed by a
+procedure. To allow creating structures of structures, this dictates the
+form of the generic formal part.
+
+Procedure Assign needs to be able to check that its parameters are not
+the same list; otherwise, the result could be an empty list, rather than
+the original list. In the reference implementation, this is done by
+comparing list IDs. Since this involves reading the value of To, it
+would be more accurate for To to have mode "in out". However, the
+imported Assign procedure has To of mode "out", rather than "in out", to
+allow scalars to be used without problems with passing an uninitialized
+variable to To and having it fail constraint checks. To allow structures
+of structures, Assign for Handle needs To to be mode "out" as well. The
+reference implementation uses the rules for parameter passing for mode
+"out" to insure that the ID can be read.
+
+The intended behavior of Position checking is: Each list has a unique
+ID. The ID type includes a value that is invalid. Each Position contains
+the ID of the list it references; an uninitialized Position contains the
+invalid ID. This implies that each list has a unique Off_List Position.
+Each node in the list contains the list's ID. A node which is not part
+of the logical value of a list contains the invalid ID and is considered
+an invalid node. Delete invalidates both the node and the position used
+to delete it. All operations involving Positions check that the ID in
+the Position matches the ID of the list involved. When a node is also
+involved, the operation also checks the ID of the node. If a check
+fails, Position_Error is propagated. This is what's intended by saying
+that Position_Error is propagated when a Position that indicates a
+deleted node is used.
+
+These checks detect and prevent the most common user errors when using
+lists, without the overhead in time and space required to detect all
+possible errors. This seems like a reasonable compromise between
+completely safe and complex at one extreme and unsafe and simple at the
+other.
+
+It is probably a good idea to protect the source of list IDs so that
+multiple tasks may elaborate objects of type Handle at the same time.
+The reference implementation does this.
+
+The reference implementation initializes a free list of unused nodes.
+Handle is a controlled type to achieve this.
+
+The reference implementation of Ada.Containers.List_Bounded_Unprotected is
+PragmARC.List_Bounded_Unprotected; it differs only in its name and the
+names of the exceptions.
+
+A.X.3 Unprotected Unbounded-Length List Handling
+
+Unbounded lists have the same interface as bounded lists, except for the
+absence of Is_Full and the propagating of Storage_Exhaustion_Error
+rather than Full_Structure_Error.
+
+The intended behavior of Position checking is the same as for bounded
+lists. In the reference implementation, there is an explicit off-list
+node for each list (without space for an Element). The access value
+designating this node is used as the list ID.
+
+The reference implementation of Ada.Containers.List_Unbounded_Unprotected is
+PragmARC.List_Unbounded_Unprotected; it differs in its name and the
+names of the exceptions. It also has a Sort procedure not specified
+here. Type Handle is a controlled type in the reference implementation.
+
+The example below is identical to the bounded list example, except for
+the name of the generic package and the absence of a discriminant on Handle.
+
+!examples
+
+A.X.2 Unprotected Bounded-Length List Handling
+
+Given that Input is an Ada.Text_IO.File_Type that has been opened and
+contains 1,000 or fewer integers, one per line, read all of the values
+in Input and store them in a list in the order read. Once the entire
+file has been read, output the number of values read followed by all the
+values, in order, to the standard output.
+
+declare
+    procedure Assign (To : out Integer; From : in Integer) is
+       -- null;
+    begin -- Assign
+       To := From;
+    end Assign;
+
+    package Integer_List is new Ada.Containers.List_Bounded_Unprotected
+       (Element => Integer);
+
+    procedure Put (I        : in out Integer;
+                   Context  : in out Boolean;
+                   Pos      : in     Integer_List.Position;
+                   Continue :    out Boolean) is
+    begin -- Put
+       Ada.Text_IO.Put_Line (Item => Integer'Image (I) );
+       Continue := True;
+    end Put;
+
+    procedure Put_All is new Integer_List.Iterate
+       (Context_Data => Boolean, Action => Put);
+
+    I     : Integer;
+    Dummy : Boolean := False;
+    List  : Integer_List.Handle (Max_Size => 1_000);
+    Pos   : Integer_List.Position;
+
+    Off_List : constant Integer_List.Position :=
+       Integer_List.Off_List (List);
+
+    use Integer_List;
+begin
+    Read_All : loop
+       exit Read_All when Ada.Text_IO.End_Of_File (Input);
+
+       Ada.Integer_Text_IO.Get (File => Input, Item => I);
+       Insert (Into    => List,
+               Before  => Off_List,
+               Item    => I,
+               New_Pos => Pos);
+    end loop Read_All;
+
+    Ada.Text_IO.Put_Line
+       (Item => "Number of values read is" &
+        Integer'Image (Length (List) ) );
+    Put_All (Over => List, Context => Dummy);
+end;
+
+A.X.3 Unprotected Unbounded-Length List Handling
+
+Given that Input is an Ada.Text_IO.File_Type that has been opened and
+contains 1,000 or fewer integers, one per line, read all of the values
+in Input and store them in a list in the order read. Once the entire
+file has been read, output the number of values read followed by all the
+values, in order, to the standard output.
+
+declare
+    procedure Assign (To : out Integer; From : in Integer) is
+       -- null;
+    begin -- Assign
+       To := From;
+    end Assign;
+
+    package Integer_List is new Ada.Containers.List_Unbounded_Unprotected
+       (Element => Integer);
+
+    procedure Put (I        : in out Integer;
+                   Context  : in out Boolean;
+                   Pos      : in     Integer_List.Position;
+                   Continue :    out Boolean)
+    is
+       -- null;
+    begin -- Put
+       Ada.Text_IO.Put_Line (Item => Integer'Image (I) );
+       Continue := True;
+    end Put;
+
+    procedure Put_All is new Integer_List.Iterate
+       (Context_Data => Boolean, Action => Put);
+
+    I     : Integer;
+    Dummy : Boolean := False;
+    List  : Integer_List.Handle;
+    Pos   : Integer_List.Position;
+
+    Off_List : constant Integer_List.Position :=
+       Integer_List.Off_List (List);
+
+    use Integer_List;
+begin
+    Read_All : loop
+       exit Read_All when Ada.Text_IO.End_Of_File (Input);
+
+       Ada.Integer_Text_IO.Get (File => Input, Item => I);
+       Insert (Into    => List,
+               Before  => Off_List,
+               Item    => I,
+               New_Pos => Pos);
+     end loop Read_All;
+
+     Ada.Text_IO.Put_Line
+        (Item => "Number of values read is" &
+                 Integer'Image (Length (List) ) );
+     Put_All (Over => List, Context => Dummy);
+end;
+
 !ACATS Test
 
 ACATS test(s) need to be created.
@@ -365,3 +1089,1337 @@
 standard components and simply propagate Storage_Error.
 
 ****************************************************************
+
+From: Jeffrey Carter
+Sent: Monday, September 30, 2002  11:44 PM
+
+!wording
+
+A.X.2 Unprotected Bounded-Length List Handling
+
+The language-defined package Something.List_Bounded_Unprotected provides
+a generic package each of whose instances yields a limited private type
+Handle, a private type Position, and a set of operations. An object of a
+particular List_Bounded_Unprotected Handle type represents a list whose
+length can vary conceptually between 0 and a maximum size established at
+the declaration of the object. Object of type Position are used to
+indicate values of type Element stored in a list.
+
+Static Semantics
+
+The library package Something.List_Bounded_Unprotected has the following
+declaration:
+
+generic -- Something.List_Bounded_Unprotected
+            type Element is limited private;
+
+            with procedure Assign (To   :    out Element;
+                                   From : in     Element) is <>;
+package Something.List_Bounded_Unprotected is
+            pragma Preelaborate;
+
+            type Handle (Max_Size : Positive) is limited private;
+
+            type Position is private;
+
+            Position_Error : exception;
+
+            procedure Assign (To : out Handle; From : in Handle);
+
+            procedure Clear (List : in out Handle);
+
+            -- Operations to obtain valid positions for lists:
+            function First    (List : Handle) return Position;
+            function Last     (List : Handle) return Position;
+            function Off_List (List : Handle) return Position;
+
+            -- Operations to obtain valid positions from valid positions:
+            function Next (Pos : Position; List : Handle) return Position;
+            function Prev (Pos : Position; List : Handle) return Position;
+
+            -- Operations to manipulate lists
+            procedure Insert (Into    : in out Handle;
+                              Item    : in     Element;
+                              Before  : in     Position;
+                              New_Pos :    out Position);
+
+            procedure Append (Into    : in out Handle;
+                              Item    : in     Element;
+                              After   : in     Position;
+                              New_Pos :    out Position);
+
+            procedure Delete (From : in out Handle;
+                              Pos  : in out Position);
+
+            function Get (From : Handle; Pos : Position) return Element;
+
+            procedure Put (Into : in out Handle;
+                           Pos  : in     Position;
+                           Item : in     Element);
+
+            function Is_Empty (List : Handle) return Boolean;
+
+            function Is_Full (List : Handle) return Boolean;
+
+            function Length (List : Handle) return Natural;
+
+            generic -- Iterate
+               type Context_Data (<>) is limited private;
+
+               with procedure Action (Item     : in out Element;
+                                      Context  : in out Context_Data;
+                                      Pos      : in     Position;
+                                      Continue :    out Boolean);
+            procedure Iterate (Over    : in out Handle;
+                               Context : in out Context_Data);
+private -- Something.List_Bounded_Unprotected
+            -- not specified by the language
+end Something.List_Bounded_Unprotected;
+
+A list is a sequence of Elements. Each Element in the sequence may be
+accessed through a Position; we say that the Position indicates the
+Element. Elements may be added to, deleted from, accessed, or modified
+in a list at any position. Using First and Next, a list may be traversed
+from the first Element to the last; using Last and Prev, from the last
+Element to the first.
+
+An object of type Handle is initially empty. An object of type Position
+is initially invalid. Handle's discriminant, Max_Size, is the maximum
+number of Elements that may be stored in a list.
+
+            procedure Assign (To : out Handle; From : in Handle);
+
+If To and From are the same list, Assign has no effect.
+
+If To.Max_Size <= Length (From), Something.Too_Short_Error is propagated.
+
+Otherwise, To is cleared and made into a copy of From.
+
+Precondition:  To.Max_Size <= Length (From)
+Postcondition: Length (To) = Length (From)
+
+            procedure Clear (List : in out Handle);
+
+This procedure makes List empty.
+
+Postcondition: Is_Empty (List)
+                   Length (List) = 0
+
+            function First (List : Handle) return Position;
+
+This function returns a Position indicating the first Element in List.
+If List is empty, this is the same as Off_List (List).
+
+            function Last (List : Handle) return Position;
+
+This function returns a Position indicating the last Element in List. If
+List is empty, this is the same as Off_List (List).
+
+            function Off_List (List : Handle) return Position;
+
+This function returns a Position that is valid for List but indicates no
+Element in List. This is the same Position returned by Next (Last
+(List), List) and by Prev (First (List), List).
+
+            function Next (Pos : Position; List : Handle) return Position;
+
+If Pos is not a valid Position for List, Position_Error is propagated.
+
+If Pos = Last (List), this function returns Off_List (List).
+
+Otherwise, this function returns a Position that indicates the next
+Element in List after the Element indicated by Pos.
+
+            function Prev (Pos : Position; List : Handle) return Position;
+
+If Pos is not a valid Position for List, Position_Error is propagated.
+
+If Pos = First (List), this function returns Off_List (List).
+
+Otherwise, this function returns a Position that indicates the previous
+Element in List before the Element indicated by Pos.
+
+            procedure Insert (Into    : in out Handle;
+                              Item    : in     Element;
+                              Before  : in     Position;
+                              New_Pos :    out Position);
+
+If Into is full, Something.Full_Structure_Error is propagated.
+
+If Before is not a valid Position for Into, Position_Error is propagated.
+
+If Into is empty and Before /= Off_List (Into), Position_Error is
+propagated.
+
+If Before = Off_List (List), Item is added as the last Element in Into.
+
+Otherwise, Item is inserted into Into before the Element indicated by
+Before.
+
+New_Pos becomes a valid Position for Into that indicates Item.
+
+Precondition:  not Is_Full (Into)
+Postcondition: Prev (Before, Into) = New_Pos
+
+            procedure Append (Into    : in out Handle;
+                              Item    : in     Element;
+                              After   : in     Position;
+                              New_Pos :    out Position);
+
+If Into is full, Something.Full_Structure_Error is propagated.
+
+If After is not a valid Position for Into, Position_Error is propagated.
+
+If Into is empty and After /= Off_List (Into), Position_Error is propagated.
+
+If After = Off_List (List), Item is added as the first Element in Into.
+
+Otherwise, Item is inserted into Into after the Element indicated by After.
+
+New_Pos becomes a valid Position for Into that indicates Item.
+
+Precondition:  not Is_Full (Into)
+Postcondition: Next (After, Into) = New_Pos
+
+            procedure Delete (From : in out Handle;
+                              Pos  : in out Position);
+
+If From is empty, Something.Empty_Structure_Error is propagated.
+
+If Pos is not a valid Position for From or Pos = Off_List (From),
+Position_Error is propagated.
+
+Otherwise, the Element indicated by Pos is removed from From. Pos is
+made invalid.
+
+Elements are stored in "nodes" in a list. A Position indicates an
+Element by indicating its node. One Position may indicate a node that
+has been deleted through another Position. Position_Error is propagated
+if such a Position is subsequently used to access the list.
+
+Clear effectively deletes all nodes in a list. Therefore, Position_Error
+is propagated if a Position, obtained before Clear is called, is used to
+access the list after Clear is called.
+
+Precondition:  not Is_Empty (From)
+Postcondition: not Is_Full (From)
+
+            function Get (From : Handle; Pos : Position) return Element;
+
+If From is empty, Something.Empty_Structure_Error is propagated.
+
+If Pos is not a valid Position for From or Pos = Off_List (From),
+Position_Error is propagated.
+
+Otherwise, this function returns the Element in From indicated by Pos.
+
+Precondition: not Is_Empty (From)
+
+            procedure Put (Into : in out Handle;
+                           Pos  : in     Position;
+                           Item : in     Element);
+
+If Into is empty, Something.Empty_Structure_Error is propagated.
+
+If Pos is not a valid Position for Into or Pos = Off_List (Into),
+Position_Error is propagated.
+
+Otherwise, the Element in Into indicated by Pos is made to be Item.
+
+Precondition: not Is_Empty (Into)
+
+            function Is_Empty (List : Handle) return Boolean;
+
+This function returns True if List is empty and False otherwise.
+
+            function Is_Full (List : Handle) return Boolean;
+
+This function returns True if List is full and False otherwise.
+
+            function Length (List : Handle) return Natural;
+
+This function returns the number of Elements stored in List.
+
+            generic -- Iterate
+               type Context_Data (<>) is limited private;
+
+               with procedure Action (Item     : in out Element;
+                                      Context  : in out Context_Data;
+                                      Pos      : in     Position;
+                                      Continue :    out Boolean);
+            procedure Iterate (Over    : in out Handle;
+                               Context : in out Context_Data);
+
+An instance of this procedure applies Action to each Element stored in
+Over and its Position in turn, from first to last. If Action sets
+Continue to False, this procedure returns immediately, without
+processing any remaining Elements in Over. Context is passed to Action
+to represent any context data that Action needs to access or modify.
+
+It is a bounded error to modify a list while iterating over it. Possible
+consequences are: propagating Position_Error, propagating
+Constraint_Error, not processing some of the Elements stored in Over,
+processing some of the Elements twice, and normal processing.
+
+Implementation Permission
+
+An implementation may reuse deleted nodes, even if that means it cannot
+guarantee that Position_Error will be propagated when a Position that
+indicates a deleted node is used to access the list.
+
+!discussion
+
+Protected lists may not be a very high priority, but one very useful
+component for concurrent programs is a protected queue. This proposal
+does present concurrent queue components, so the distinction is
+preserved for all structures.
+
+Given a type such as Handle, it is clear that the use of controlled
+types does not allow assignment between objects with different maximum
+sizes, even when the logical value to be assigned will fit in the
+destination object. This requires that assignment be performed by a
+procedure. To allow creating structures of structures, this dictates the
+form of the generic formal part.
+
+Procedure Assign needs to be able to check that its parameters are not
+the same list; otherwise, the result could be an empty list, rather than
+the original list. In the reference implementation, this is done by
+comparing list IDs. Since this involves reading the value of To, it
+would be more accurate for To to have mode "in out". However, the
+imported Assign procedure has To of mode "out", rather than "in out", to
+allow scalars to be used without problems with passing an uninitialized
+variable to To and having it fail constraint checks. To allow structures
+of structures, Assign for Handle needs To to be mode "out" as well. The
+reference implementation uses the rules for parameter passing for mode
+"out" to insure that the ID can be read.
+
+The intended behavior of Position checking is: Each list has a unique
+ID. The ID type includes a value that is invalid. Each Position contains
+the ID of the list it references; an uninitialized Position contains the
+invalid ID. This implies that each list has a unique Off_List Position.
+Each node in the list contains the list's ID. A node which is not part
+of the logical value of a list contains the invalid ID and is considered
+an invalid node. Delete invalidates both the node and the position used
+to delete it. All operations involving Positions check that the ID in
+the Position matches the ID of the list involved. When a node is also
+involved, the operation also checks the ID of the node. If a check
+fails, Position_Error is propagated. This is what's intended by saying
+that Position_Error is propagated when a Position that indicates a
+deleted node is used.
+
+These checks detect and prevent the most common user errors when using
+lists, without the overhead in time and space required to detect all
+possible errors. This seems like a reasonable compromise between
+completely safe and complex at one extreme and unsafe and simple at the
+other.
+
+It is probably a good idea to protect the source of list IDs so that
+multiple tasks may elaborate objects of type Handle at the same time.
+The reference implementation does this.
+
+The reference implementation initializes a free list of unused nodes.
+Handle is a controlled type to achieve this.
+
+The reference implementation of Something.List_Bounded_Unprotected is
+PragmARC.List_Bounded_Unprotected; it differs only in its name and the
+names of the exceptions.
+
+!example
+
+Given that Input is an Ada.Text_IO.File_Type that has been opened and
+contains 1,000 or fewer integers, one per line, read all of the values
+in Input and store them in a list in the order read. Once the entire
+file has been read, output the number of values read followed by all the
+values, in order, to the standard output.
+
+declare
+        procedure Assign (To : out Integer; From : in Integer) is
+           -- null;
+        begin -- Assign
+           To := From;
+        end Assign;
+
+        package Integer_List is new Something.List_Bounded_Unprotected
+           (Element => Integer);
+
+        procedure Put (I        : in out Integer;
+                       Context  : in out Boolean;
+                       Pos      : in     Integer_List.Position;
+                       Continue :    out Boolean)
+        is
+           -- null;
+        begin -- Put
+           Ada.Text_IO.Put_Line (Item => Integer'Image (I) );
+           Continue := True;
+        end Put;
+
+        procedure Put_All is new Integer_List.Iterate
+           (Context_Data => Boolean, Action => Put);
+
+        I     : Integer;
+        Dummy : Boolean := False;
+        List  : Integer_List.Handle (Max_Size => 1_000);
+        Pos   : Integer_List.Position;
+
+        Off_List : constant Integer_List.Position :=
+           Integer_List.Off_List (List);
+
+        use Integer_List;
+begin
+        Read_All : loop
+           exit Read_All when Ada.Text_IO.End_Of_File (Input);
+
+           Ada.Integer_Text_IO.Get (File => Input, Item => I);
+           Insert (Into    => List,
+                   Before  => Off_List,
+                   Item    => I,
+                   New_Pos => Pos);
+        end loop Read_All;
+
+        Ada.Text_IO.Put_Line
+           (Item => "Number of values read is" &
+            Integer'Image (Length (List) ) );
+        Put_All (Over => List, Context => Dummy);
+end;
+
+****************************************************************
+
+From: Christoph Grein
+Sent: Tuesday, October 1, 2002  1:35 AM
+
+>             function Next (Pos : Position; List : Handle) return Position;
+>
+> If Pos is not a valid Position for List, Position_Error is propagated.
+>
+> If Pos = Last (List), this function returns Off_List (List).
+
+What if Pos = Off_List? Off_List is a valid value. Probably it should return
+Off_List.
+
+>             function Prev (Pos : Position; List : Handle) return Position;
+
+Like for Next.
+
+>             procedure Insert (Into    : in out Handle;
+>                               Item    : in     Element;
+>                               Before  : in     Position;
+>                               New_Pos :    out Position);
+>             procedure Append (Into    : in out Handle;
+>                               Item    : in     Element;
+>                               After   : in     Position;
+>                               New_Pos :    out Position);
+
+The discription is contrary to the (or my?) intuitive feeling that Insert at
+Off_List inserts before the start, Append at Off_List appends after the end.
+
+Insert should perhaps be called Prepend.
+
+> Clear effectively deletes all nodes in a list. Therefore, Position_Error
+> is propagated if a Position, obtained before Clear is called, is used to
+> access the list after Clear is called.
+>
+> Precondition:  not Is_Empty (From)
+> Postcondition: not Is_Full (From)
+
+Is this a precondition for Clear? Clear on empty list just should do nothing.
+
+****************************************************************
+
+From: Christoph Grein
+Sent: Tuesday, October 1, 2002  1:35 AM
+
+To elaborate a bit further the contra-intuitive meaning:
+
+If you want to fill a list in sequential order, the design seems to be to use
+
+  loop
+    get (Item);
+    Append (List, Item, After => Last (List), New_Pos => ...);
+  end loop;
+
+If you however do
+
+  loop
+    Get (Item);
+    Append (List, Item, After => Off_List (List), New_Pos => ...);
+  end list;
+
+which seems most obvious, you get, contrary to intuition, the list in reverse
+order! :-(
+Yuck!
+
+****************************************************************
+
+From: Jeffrey Carter
+Sent: Tuesday, October 1, 2002  1:38 PM
+
+>>            function Next (Pos : Position; List : Handle) return Position;
+>>
+>>If Pos is not a valid Position for List, Position_Error is propagated.
+>>
+>>If Pos = Last (List), this function returns Off_List (List).
+>
+>
+> What if Pos = Off_List? Off_List is a valid value. Probably it should return
+> Off_List.
+>
+>
+>>            function Prev (Pos : Position; List : Handle) return Position;
+>
+>
+> Like for Next.
+
+Good points. The idea is that Next (Last) = Off_List, Next (Off_List) =
+First, Prev (First) = Off_List, & Prev (Off_List) = Last.
+
+Please add to the wording for Next:
+
+If Pos = Off_List (List), this function returns First (List).
+
+Add to the wording for Prev:
+
+If Pos = Off_List (List), this function returns Last (List).
+
+
+>>            procedure Insert (Into    : in out Handle;
+>>                              Item    : in     Element;
+>>                              Before  : in     Position;
+>>                              New_Pos :    out Position);
+>>            procedure Append (Into    : in out Handle;
+>>                              Item    : in     Element;
+>>                              After   : in     Position;
+>>                              New_Pos :    out Position);
+>
+>
+> The discription is contrary to the (or my?) intuitive feeling that Insert at
+> Off_List inserts before the start, Append at Off_List appends after the end.
+
+I hope the additional rules given above clarify this. If you like, you
+may consider the ends of the list curving towards each other, with
+Off_List between them. It should be clear that before Off_List is after
+Last, and after Off_List is before First.
+
+>>Clear effectively deletes all nodes in a list. Therefore, Position_Error
+>>is propagated if a Position, obtained before Clear is called, is used to
+>>access the list after Clear is called.
+>>
+>>Precondition:  not Is_Empty (From)
+>>Postcondition: not Is_Full (From)
+>
+>
+> Is this a precondition for Clear? Clear on empty list just should do nothing.
+
+The conditions for Clear are given after Clear. These are clearly the
+conditions for Delete.
+
+The discussion of propagating Position_Error when using a Position that
+indicates a deleted node applies to both Clear and Delete. This seemed
+like the best place to put that discussion, after both Clear and Delete
+have been described. Perhaps there is a better location; I am certainly
+open to suggestions.
+
+Thanks for your comments.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Tuesday, October 1, 2002  5:06 PM
+
+>>Clear effectively deletes all nodes in a list. Therefore, Position_Error
+>>is propagated if a Position, obtained before Clear is called, is used to
+>>access the list after Clear is called.
+
+> The discussion of propagating Position_Error when using a Position that
+> indicates a deleted node applies to both Clear and Delete. This seemed
+> like the best place to put that discussion, after both Clear and Delete
+> have been described. Perhaps there is a better location; I am certainly
+> open to suggestions.
+
+This paragraph seems to be a note about Clear. It isn't even a rule (it follows
+from other rules), and it certainly doesn't have anything to do with Delete.
+I'd suggest putting it with Clear, or possibly in the Notes section at the end
+of the whole subclause.
+
+****************************************************************
+
+From: Michael Erdman
+Sent: Tuesday, October 1, 2002  12:56 PM
+
+>            function Off_List (List : Handle) return Position;
+>
+> This function returns a Position that is valid for List but indicates no
+> Element in List. This is the same Position returned by Next (Last
+> (List), List) and by Prev (First (List), List).
+
+I am realy wondering what is the gain of this function?
+
+****************************************************************
+
+From: Jeffrey Carter
+Sent: Tuesday, October 1, 2002  1:48 PM
+
+It allows the client to know when he has reached the end of a list using
+Next or Prev. It can also be used to eliminate a recurring function call
+when adding elements to the ends of the list, as in the example. Some
+value has to be available for at least the first of these. Perhaps you
+would like to suggest a different name for the function.
+
+****************************************************************
+
+From: Michael Erdman
+Sent: Tuesday, October 1, 2002  12:56 PM
+
+I am realy wondering if a Off_List is realy a position since it is
+outside! Under this point of view the different behaviour of
+
+    Append (List, Item, After => Last (List), New_Pos => ...);
+
+and
+
+    Append (List, Item, After => Off_List (List), New_Pos => ...);
+
+are not understandable. From my understanding, the last construct should cause
+an exception, because you append something after nowhere?!!
+
+My personal feeling is that last, first are sufficient and off_list is not
+realy required?!
+
+The reat of the AI is fine for me since it lines up with most of the list
+packages i am using.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Tuesday, October 1, 2002  5:29 PM
+
+> I am realy wondering if a Off_List is realy a position since it is
+> outside! Under this point of view the different behaviour  of
+>
+>     Append (List, Item, After => Last (List), New_Pos => ...);
+>
+> and
+>
+>     Append (List, Item, After => Off_List (List), New_Pos => ...);
+>
+> are not understandable. From my understanding, the last construct should
+cause
+> an exception, because you append something after nowhere?!!
+
+I tend to agree with Michael here.
+
+It's also annoying that you have to specify the location to Append. It is
+unfortunate that that parameter cannot default to the end of the list,
+because that is what is most commonly needed.
+
+> My personal feeling is that last, first are sufficient and off_list is not
+> realy required?!
+
+I think that Jeffrey is using Off_List when using Next to iterate over a
+list.
+
+Having First, Last, Next, and Prev raising an exception at the end of the
+list would complicate that code.
+
+You want a loop something like:
+
+    declare
+        Pos : Position := First(List);
+    begin
+        while Pos /= Off_List(List) loop
+           -- Processing here.
+           Pos := Next(Pos, List);
+        end loop;
+    end loop;
+
+You could rewrite the loop to avoid Off_List, but that would require
+pre-testing for an empty loop (because First would raise an exception in
+that case):
+
+    if not Is_Empty(List) then
+        declare
+            Pos : Position := First(List);
+        begin
+            loop
+                -- Processing here.
+                exit when Pos = Last(List);
+                Pos := Next(Pos, List);
+            end loop;
+        end;
+    end if;
+
+And you have an exit-in-the-middle loop, which really annoys some pedants.
+(It doesn't bother me in the least; "while" loops tend to bother me more
+because they are hard to modify.)
+
+****************************************************************
+
+From: Robert I. Eachus
+Sent: Tuesday, October 1, 2002  7:15 PM
+
+  I see several problems here.   The first is that Append should never
+take a position parameter.  The regular, usual, use of Append will be to
+insert at the end of the list.  Make that interface and code as
+efficient as possible.  It should work on an empty list of course, and
+raise an exception if the list is alread full, but outside of that, why
+make the usual case (append at the end) share code with the unusual case
+(insert in the middle of the list).  As for Insert, in that case Insert
+before an invalid position should insert at the end of the list, and for
+Insert, a Position parameter makes sense.
+
+Next, some nomenclature.  Get rid of Handle as a type name.  It may
+actually reflect some implementations,  but it won't be correct for all
+implementations, and if for example, small lists are implemented on the
+stack, asssignment really should copy the whole list.  (You can take
+'Access if you want to avoid copy semantics.)  The list should be List,
+or List_Type.  If you prefer the later, the name of the parameters can
+stay as list.
+
+Similarly Off_List has the semantics of a value but is only available as
+a function,.  If you really need to have a named value, call it Invalid,
+and make it a constant.  All lists created from a single instance of the
+package should have the same value for this in any case, since the idea
+of having different Off_List values for different lists seems very error
+prone.  A farily straightforward implementation has Off_List always
+returning 0 (zero).
+
+There are too many exceptions in the discussion.  It makes a great deal
+of sense to declare the exceptions in the parent package, but there
+should only be one or two.  If two, you should have Position_Error and
+Full_Structure_Error.  Empty_Structure_Error seems to be recreating the
+Constraint_Error/Numeric_Error problems, again for no good reason.  But
+I personally think that Full_Structure_Error is still one too many.  I
+can see some advantages to having Position_Error separate from
+Constraint_Error, but Full_Structure_Error looks to me an awful lot like
+Constraint_Error.
+
+Finally, I see no reason to approve half a loaf.  If (minimally
+protected) unprotected lists like this exist, go the extra mile to
+define the semantics and interface for protected lists.  Actually it
+looks to me like only a few extra yards.  Protected lists should  be
+protected on a per list basis, instantiating an iterator should lock the
+list against writing by other tasks/threads while the iterator exists,
+and you need an additional generic:
+
+       generic --  Transaction
+          type Context_Data (<>) is limited private;
+          with procedure Action (List: in out Handle;
+                                 Context  : in out Context_Data;
+                                 Pos      : in out Position);
+       procedure Transaction (List    : in out Handle;
+                          Context : in out Context_Data;
+                           Pos: in out Position);
+
+In effect this wraps the Action in a P,V pair, but of course it will
+probably be implemented with a protected list object.  All the rest of
+the semantics of  protected list objects can be described in terms of
+this generic and the unprotected list type, even if they are not
+implemented that way.
+
+****************************************************************
+
+From: Jeffery Carter
+Sent: Tuesday, October 1, 2002  3:57 PM
+
+!wording
+
+A.X.3 Unprotected Unbounded-Length List Handling
+
+The language-defined package Something.List_Unbounded_Unprotected
+provides a generic package each of whose instances yields a limited
+private type Handle, a private type Position, and a set of operations.
+An object of a particular List_Bounded_Unprotected Handle type
+represents a list whose length can vary conceptually between 0 and a
+maximum size established by available storage. Objects of type Position
+are used to indicate values of type Element stored in a list. The
+subprograms for bounded lists are overloaded for unbounded lists, except
+Is_Full.
+
+Static Semantics
+
+The library package Something.List_Unbounded_Unprotected has the
+following declaration:
+
+generic -- Something.List_Unbounded_Unprotected
+    type Element is limited private;
+
+    with procedure Assign (To   :    out Element;
+                           From : in     Element) is <>;
+package Something.List_Unbounded_Unprotected is
+    pragma Preelaborate;
+
+    type Handle is limited private;
+
+    type Position is private;
+
+    Position_Error : exception;
+
+    procedure Assign (To : out Handle; From : in Handle);
+
+    procedure Clear (List : in out Handle);
+
+    -- Operations to obtain valid positions for lists:
+    function First    (List : Handle) return Position;
+    function Last     (List : Handle) return Position;
+    function Off_List (List : Handle) return Position;
+
+    -- Operations to obtain valid positions from valid positions:
+    function Next (Pos : Position; List : Handle) return Position;
+    function Prev (Pos : Position; List : Handle) return Position;
+
+    -- Operations to manipulate lists
+    procedure Insert (Into    : in out Handle;
+                      Item    : in     Element;
+                      Before  : in     Position;
+                      New_Pos :    out Position);
+
+    procedure Append (Into    : in out Handle;
+                      Item    : in     Element;
+                      After   : in     Position;
+                      New_Pos :    out Position);
+
+    procedure Delete (From : in out Handle;
+                      Pos  : in out Position);
+
+    function Get (From : Handle; Pos : Position) return Element;
+
+    procedure Put (Into : in out Handle;
+                   Pos  : in     Position;
+                   Item : in     Element);
+
+    function Is_Empty (List : Handle) return Boolean;
+
+    function Length (List : Handle) return Natural;
+
+    generic -- Iterate
+       type Context_Data (<>) is limited private;
+
+       with procedure Action (Item     : in out Element;
+                              Context  : in out Context_Data;
+                              Pos      : in     Position;
+                              Continue :    out Boolean);
+    procedure Iterate (Over    : in out Handle;
+                       Context : in out Context_Data);
+private -- Something.List_Unbounded_Unprotected
+    -- not specified by the language
+end Something.List_Unbounded_Unprotected;
+
+A list is a sequence of Elements. Each Element in the sequence may be
+accessed through a Position; we say that the Position indicates the
+Element. Elements may be added to, deleted from, accessed, or modified
+in a list at any position. Using First and Next, a list may be traversed
+from the first Element to the last; using Last and Prev, from the last
+Element to the first.
+
+An object of type Handle is initially empty. An object of type Position
+is initially invalid.
+
+    procedure Assign (To : out Handle; From : in Handle);
+
+If To and From are the same list, Assign has no effect.
+
+Otherwise, To is cleared and made into a copy of From.
+
+If, after clearing To, there is insufficient storage to allocate list
+nodes for copies of all the Elements in From, Storage_Exhaustion_Error
+is propagated.
+
+Postcondition: Length (To) = Length (From)
+
+    procedure Clear (List : in out Handle);
+
+This procedure makes List empty.
+
+Postcondition: Is_Empty (List)
+                Length (List) = 0
+
+    function First (List : Handle) return Position;
+
+This function returns a Position indicating the first Element in List.
+If List is empty, this is the same as Off_List (List).
+
+    function Last (List : Handle) return Position;
+
+This function returns a Position indicating the last Element in List. If
+List is empty, this is the same as Off_List (List).
+
+    function Off_List (List : Handle) return Position;
+
+This function returns a Position that is valid for List but indicates no
+Element in List. This is the same Position returned by Next (Last
+(List), List) and by Prev (First (List), List).
+
+    function Next (Pos : Position; List : Handle) return Position;
+
+If Pos is not a valid Position for List, Position_Error is propagated.
+
+If Pos = Last (List), this function returns Off_List (List).
+
+If Pos = Off_List (List), this function returns First (List).
+
+Otherwise, this function returns a Position that indicates the next
+Element in List after the Element indicated by Pos.
+
+    function Prev (Pos : Position; List : Handle) return Position;
+
+If Pos is not a valid Position for List, Position_Error is propagated.
+
+If Pos = First (List), this function returns Off_List (List).
+
+If Pos = Off_List (List), this function returns Last (List).
+
+Otherwise, this function returns a Position that indicates the previous
+Element in List before the Element indicated by Pos.
+
+    procedure Insert (Into    : in out Handle;
+                      Item    : in     Element;
+                      Before  : in     Position;
+                      New_Pos :    out Position);
+
+If Before is not a valid Position for Into, Position_Error is propagated.
+
+If Into is empty and Before /= Off_List (Into), Position_Error is
+propagated.
+
+If there is insufficient storage to allocate a new list node,
+Storage_Exhaustion_Error is propagated.
+
+If Before = Off_List (List), Item is added as the last Element in Into.
+
+Otherwise, Item is inserted into Into before the Element indicated by
+Before.
+
+New_Pos becomes a valid Position for Into that indicates Item.
+
+Postcondition: Prev (Before, Into) = New_Pos
+
+    procedure Append (Into    : in out Handle;
+                      Item    : in     Element;
+                      After   : in     Position;
+                      New_Pos :    out Position);
+
+If After is not a valid Position for Into, Position_Error is propagated.
+
+If Into is empty and After /= Off_List (Into), Position_Error is propagated.
+
+If there is insufficient storage to allocate a new list node,
+Storage_Exhaustion_Error is propagated.
+
+If After = Off_List (List), Item is added as the first Element in Into.
+
+Otherwise, Item is inserted into Into after the Element indicated by After.
+
+New_Pos becomes a valid Position for Into that indicates Item.
+
+Postcondition: Next (After, Into) = New_Pos
+
+    procedure Delete (From : in out Handle;
+                      Pos  : in out Position);
+
+If From is empty, Something.Empty_Structure_Error is propagated.
+
+If Pos is not a valid Position for From or Pos = Off_List (From),
+Position_Error is propagated.
+
+Otherwise, the Element indicated by Pos is removed from From. Pos is
+made invalid.
+
+Elements are stored in "nodes" in a list. A Position indicates an
+Element by indicating its node. One Position may indicate a node that
+has been deleted through another Position. Position_Error is propagated
+if such a Position is subsequently used to access the list.
+
+Clear effectively deletes all nodes in a list. Therefore, Position_Error
+is propagated if a Position, obtained before Clear is called, is used to
+access the list after Clear is called.
+
+Precondition:  not Is_Empty (From)
+
+    function Get (From : Handle; Pos : Position) return Element;
+
+If Pos is not a valid Position for From or Pos = Off_List (From),
+Position_Error is propagated.
+
+Otherwise, this function returns the Element in From indicated by Pos.
+
+Precondition: not Is_Empty (From)
+
+    procedure Put (Into : in out Handle;
+                   Pos  : in     Position;
+                   Item : in     Element);
+
+If Into is empty, Something.Empty_Structure_Error is propagated.
+
+If Pos is not a valid Position for Into or Pos = Off_List (Into),
+Position_Error is propagated.
+
+Otherwise, the Element in Into indicated by Pos is made to be Item.
+
+Precondition: not Is_Empty (Into)
+
+    function Is_Empty (List : Handle) return Boolean;
+
+This function returns True if List is empty and False otherwise.
+
+    function Length (List : Handle) return Natural;
+
+This function returns the number of Elements stored in List.
+
+    generic -- Iterate
+       type Context_Data (<>) is limited private;
+
+       with procedure Action (Item     : in out Element;
+                              Context  : in out Context_Data;
+                              Pos      : in     Position;
+                              Continue :    out Boolean);
+    procedure Iterate (Over    : in out Handle;
+                       Context : in out Context_Data);
+
+An instance of this procedure applies Action to each Element stored in
+Over and its Position in turn, from first to last. If Action sets
+Continue to False, this procedure returns immediately, without
+processing any remaining Elements in Over. Context is passed to Action
+to represent any context data that Action needs to access or modify.
+
+It is a bounded error to modify a list while iterating over it. Possible
+consequences are: propagating Position_Error, propagating
+Constraint_Error, not processing some of the Elements stored in Over,
+processing some of the Elements twice, and normal processing.
+
+Implementation Permission
+
+An implementation may reuse deleted nodes, even if that means it cannot
+guarantee that Position_Error will be propagated when a Position that
+indicates a deleted node is used to access the list.
+
+Implementation Requirements
+
+No storage associated with a Handle object shall be lost upon scope
+exit, a call to Clear or Delete, or being associated with the parameter
+To of a call to Assign.
+
+!discussion
+
+Unbounded lists have the same interface as bounded lists, except for the
+absence of Is_Full and the propagating of Storage_Exhaustion_Error
+rather than Full_Structure_Error.
+
+The intended behavior of Position checking is the same as for bounded
+lists. In the reference implementation, there is an explicit off-list
+node for each list (without space for an Element). The access value
+designating this node is used as the list ID.
+
+The reference implementation of Something.List_Unbounded_Unprotected is
+PragmARC.List_Unbounded_Unprotected; it differs in its name and the
+names of the exceptions. It also has a Sort procedure not specified
+here. Type Handle is a controlled type in the reference implementation.
+
+The example below is identical to the bounded list example, except for
+the name of the generic package and the absence of a discriminant on Handle.
+
+!example
+
+Given that Input is an Ada.Text_IO.File_Type that has been opened and
+contains 1,000 or fewer integers, one per line, read all of the values
+in Input and store them in a list in the order read. Once the entire
+file has been read, output the number of values read followed by all the
+values, in order, to the standard output.
+
+declare
+    procedure Assign (To : out Integer; From : in Integer) is
+       -- null;
+    begin -- Assign
+       To := From;
+    end Assign;
+
+    package Integer_List is new Something.List_Unbounded_Unprotected
+       (Element => Integer);
+
+    procedure Put (I        : in out Integer;
+                   Context  : in out Boolean;
+                   Pos      : in     Integer_List.Position;
+                   Continue :    out Boolean)
+    is
+       -- null;
+    begin -- Put
+       Ada.Text_IO.Put_Line (Item => Integer'Image (I) );
+       Continue := True;
+    end Put;
+
+    procedure Put_All is new Integer_List.Iterate
+       (Context_Data => Boolean, Action => Put);
+
+    I     : Integer;
+    Dummy : Boolean := False;
+    List  : Integer_List.Handle;
+    Pos   : Integer_List.Position;
+
+    Off_List : constant Integer_List.Position :=
+       Integer_List.Off_List (List);
+
+    use Integer_List;
+begin
+    Read_All : loop
+       exit Read_All when Ada.Text_IO.End_Of_File (Input);
+
+       Ada.Integer_Text_IO.Get (File => Input, Item => I);
+       Insert (Into    => List,
+               Before  => Off_List,
+               Item    => I,
+               New_Pos => Pos);
+     end loop Read_All;
+
+     Ada.Text_IO.Put_Line
+        (Item => "Number of values read is" &
+                 Integer'Image (Length (List) ) );
+     Put_All (Over => List, Context => Dummy);
+end;
+
+****************************************************************
+
+From: Christoph Grein
+Sent: Wednesday, October 2, 2002  1:51 AM
+
+> A.X.3 Unprotected Unbounded-Length List Handling
+
+My comments for Unprotected Bounded-Length List about being counter-intuitive
+also apply to this unbounded variant.
+
+  loop
+    Get (Item);
+    Append (List, Item, After => Off_List (List), New_Pos => ...);
+  end list;
+
+which seems most obvious, you get, contrary to intuition, the list in reverse
+order! :-(
+Yuck!
+
+I can see the intent with wrapping around via Off_List, but I strongly dislike
+the consequence of counter-intuition :-(
+
+I do think (like Robert I. Eachus) that Append should have no After and simply
+add at the end. It's the most common use of a list.
+
+Insert has a Before and thus can do everything you want:
+
+Insert Before First creates a list in inverse order;
+Insert Before Off_List inserts at the end, i.e. in natural order (i.e. the same
+as the simplified Append).
+
+The idea of wrapping round via Off_List for iterators is good and unaffected by
+the proposed change to Append.
+
+****************************************************************
+
+From: Robert I. Eachus
+Sent: Wednesday, October 2, 2002  1:00 PM
+
+Jeffrey Carter wrote:
+
+> The language-defined package Something.List_Unbounded_Unprotected
+> provides a generic package each of whose instances yields a limited
+> private type Handle, a private type Position, and a set of operations....
+
+
+I am going to stick my neck out here and suggest that the parent package
+be Ada.Lists.  Ada.Lists should contain the declarations of all
+necessary exceptions.  The problem with putting exceptions in generics
+is that each instance of the generic creates a new exception, so it is
+better to declare the exceptions elsewhere, and if necessary use
+renaming for visibility.  (In this case, I don't see any need for the
+renamings, but I don't feel too strongly one way or the other.)
+
+Ada.Lists should be the parent of four generic packages:  Bounded,
+Unbounded, Bounded_Protected, and Unbounded_Protected.  I don't like
+putting Unprotected in the name, as it implies things that are not
+necessarily true.  (Either the usage of the "unprotected" lists may be
+totally free of tasking issues, or the implementation may do the minimal
+protection necessary (creation of new lists) for safety in a particular
+program.
+
+Also for political reasons.  Look at all the troubles caused by the name
+of Unchecked_Deallocation, even though most uses are carefully validated
+by the programmer.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Wednesday, October 2, 2002  1:29 PM
+
+The Charles library has the kind of structure you're suggesting:
+
+charles.lists.unbounded
+
+Eventually there'll be another one:
+
+charles.lists.bounded
+
+http://home.earthlink.net/~matthewjheaney/charles/index.html
+
+I wouldn't bother with protected forms, for the same reasons you didn't try to protect the random number generator type.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Wednesday, October 2, 2002  2:14 PM
+
+Oops -- I meant:
+
+charles.lists.single.unbounded
+charles.lists.double.unbounded
+
+****************************************************************
+
+From: Jeffery Carter
+Sent: Wednesday, October 2, 2002  1:53 PM
+
+Robert I. Eachus wrote:
+> I am going to stick my neck out here and suggest that the parent package
+> be Ada.Lists.  Ada.Lists should contain the declarations of all
+> necessary exceptions.  The problem with putting exceptions in generics
+> is that each instance of the generic creates a new exception, so it is
+> better to declare the exceptions elsewhere, and if necessary use
+> renaming for visibility.  (In this case, I don't see any need for the
+> renamings, but I don't feel too strongly one way or the other.)
+
+The names of the packages, it seems to me, should be up to the ARG.
+Clearly the hierarchy should not be named Something.
+
+Only lists have positions, so it did not seem like a good idea to put
+Position_Error in Something with the other exceptions. It may be a good
+idea to put it outside the list packages, though.
+
+I intend to propose queues, stacks, bags, and skip lists as well as
+lists, so Ada.Lists might not be the best name for the parent package
+unless the ARG decides to only include lists.
+
+****************************************************************
+
+From: Matthew Heaney
+Sent: Wednesday, October 2, 2002  2:18 PM
+
+All you need is another intermediate package, ie
+
+ada.containers.lists...
+ada.containers.maps...
+
+****************************************************************
+
+From: Simon J. Wright
+Sent: Thursday, October 3, 2002  10:37 AM
+
+If there is any chance of different sorts of container, then you would
+want something more like
+
+  Ada.Containers.Lists
+  Ada.Containers.Maps
+
+and then the exceptions would be in one of
+
+  Ada.Containers             (where the Booch Components put them)
+  Ada.Containers.Exceptions
+  Ada.Container_Exceptions   (like IO_Exceptions)
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Thursday, October 3, 2002  12:40 PM
+
+This does look like a reasonable organization, and
+I would put the exceptions in the parent package,
+Ada.Containers, so there is no temptation to do
+the tedious renaming that all the various IO packages
+ended up doing.
+
+****************************************************************
+
+From: Jeffery Carter
+Sent: Thursday, October 3, 2002  1:46 PM
+
+I would think that exceptions specific to one branch of this tree should
+go lower down. For example, Position_Error only applies to lists, and so
+would go into Ada.Data_Structures.Lists.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Friday, October 4, 2002  5:37 PM
+
+Jeffery Carter wrote:
+> The names of the packages, it seems to me, should be up to the ARG.
+> Clearly the hierarchy should not be named Something.
+
+That's not quite the right attitude. You're making a proposal, and that
+clearly should include the name of the hierarchy and its position. Pick
+something (I prefer Ada.Containers of the suggestions I've seen) and stick
+with it.
+
+After all, the ARG can change anything about any proposal. But we don't have
+the time to spend sitting around thinking up the best names for things. I
+can easily image us sitting around for hours arguing about the name of this
+hierarchy -- I'd rather not have to go there.
+
+****************************************************************
+
+From: Robert Dewar
+Sent: Wednesday, October 2, 2002  1:38 AM
+
+ I think it would be useful to have a focused discussion on whether such
+a package is appropriate at all to a new standard. Failing agreement on
+this issue, there is not much point in discussing details of a particular
+design. In fact I would say that we should have a high level discussion and
+list of all desirable package additions before any detailed design is done.
+Otherwise you get a disorganized process in which everyone submits their
+fabvorite packages (for a collection of our favorites, see GNAT.xxx :-)
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Wednesday, October 2, 2002  6:25 PM
+
+Robert wrote:
+> I think it would be useful to have a focused discussion on whether such
+> a package is appropriate at all to a new standard. Failing agreement on
+> this issue, there is not much point in discussing details of a particular
+> design.
+
+We discussed container libraries (AI-302) briefly in Vienna. No one objected
+to the general idea.
+
+> In fact I would say that we should have a high level discussion and
+> list of all desirable package additions before any detailed design is
+done.
+
+This was done quite a few meetings back. The ARG essentially decided that it
+did not have enough information to decide on which packages are appropriate
+to add. And we definitely do not want to be in the business of designing
+packages. Rather, we decided to ask the community to propose packages. This
+was in the call for APIs (http://www.adaic.org/news/call4apis.html).
+
+> Otherwise you get a disorganized process in which everyone submits their
+> favorite packages (for a collection of our favorites, see GNAT.xxx :-)
+
+Well, that has not happened to date. That's because a submission of a
+serious proposal requires RM-style wording, and that's a lot of work. A
+proposal containing only the specs and comments from several GNAT packages
+would be round-filed. OTOH, proper proposals based on GNAT packages would be
+looked at seriously, as they clearly meet the goal of "available for years".
+
+****************************************************************
+
+From: Ehud Lamm
+Sent: Thursday, October 3, 2002  9:32 AM
+
+> Well, that has not happened to date. That's because a submission of a
+> serious proposal requires RM-style wording, and that's a lot
+> of work.
+
+A few of us are working toward that goal. The group started following the
+Ada-Europe workshop concerning a standard container library for Ada.
+I created a mailing list for our discussions, so as not to disturb the
+discussions on Ada-Comment.
+When we have a decent AI to propose, we will of course submit it.
+
+If anyone is interested in  joing the mailing list, let me know.
+
+****************************************************************
+

Questions? Ask the ACAA Technical Agent