Ada Reference Manual (Ada 2022) — Legal Information
Contents   Index   References   Search   Previous   Next 

A.18.3 The Generic Package Containers.Doubly_Linked_Lists

1/2
The language-defined generic package Containers.Doubly_Linked_Lists provides private types List and Cursor, and a set of operations for each type. A list container is optimized for insertion and deletion at any position.
2/2
A doubly-linked list container object manages a linked list of internal nodes, each of which contains an element and pointers to the next (successor) and previous (predecessor) internal nodes. A cursor designates a particular node within a list (and by extension the element contained in that node). A cursor keeps designating the same node (and element) as long as the node is part of the container, even if the node is moved in the container.
3/2
The length of a list is the number of elements it contains. 

Static Semantics

4/2
The generic library package Containers.Doubly_Linked_Lists has the following declaration:
5/5
with Ada.Iterator_Interfaces;
generic
   type Element_Type is private;
   with function "=" (Left, Right : Element_Type)
      return Boolean is <>;
package Ada.Containers.Doubly_Linked_Lists
   with Preelaborate, Remote_Types,
        Nonblocking, Global => in out synchronized is
6/5
   type List is tagged private
      with Constant_Indexing => Constant_Reference,
           Variable_Indexing => Reference,
           Default_Iterator  => Iterate,
           Iterator_Element  => Element_Type,
           Iterator_View     => Stable.List,
           Aggregate         => (Empty       => Empty,
                                 Add_Unnamed => Append),
           Stable_Properties => (Length,
                                 Tampering_With_Cursors_Prohibited,
                                 Tampering_With_Elements_Prohibited),
           Default_Initial_Condition =>
              Length (List) = 0 and then
              (not Tampering_With_Cursors_Prohibited (List)) and then
              (not Tampering_With_Elements_Prohibited (List)),
           Preelaborable_Initialization;
7/5
   type Cursor is private
      with Preelaborable_Initialization;
8/2
   Empty_List : constant List;
9/2
   No_Element : constant Cursor;
9.1/5
   function Has_Element (Position : Cursor) return Boolean
      with Nonblocking, Global => in all, Use_Formal => null;
9.2/5
   function Has_Element (Container : List; Position : Cursor)
      return Boolean
      with Nonblocking, Global => null, Use_Formal => null;
9.3/3
   package List_Iterator_Interfaces is new
       Ada.Iterator_Interfaces (Cursor, Has_Element);
10/2
   function "=" (Left, Right : List) return Boolean;
10.1/5
   function Tampering_With_Cursors_Prohibited
      (Container : List) return Boolean
      with Nonblocking, Global => null, Use_Formal => null;
10.2/5
   function Tampering_With_Elements_Prohibited
      (Container : List) return Boolean
      with Nonblocking, Global => null, Use_Formal => null;
10.3/5
   function Empty return List
      is (Empty_List)
      with Post =>
             not Tampering_With_Elements_Prohibited (Empty'Result) and then
             not Tampering_With_Cursors_Prohibited (Empty'Result) and then
             Length (Empty'Result) = 0;
11/5
   function Length (Container : List) return Count_Type
      with Nonblocking, Global => null, Use_Formal => null;
12/5
   function Is_Empty (Container : List) return Boolean
      with Nonblocking, Global => null, Use_Formal => null,
           Post => Is_Empty'Result = (Length (Container) = 0);
13/5
   procedure Clear (Container : in out List)
      with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error,
           Post => Length (Container) = 0;
14/5
   function Element (Position : Cursor) return Element_Type
      with Pre  => Position /= No_Element or else raise Constraint_Error,
           Nonblocking, Global => in all, Use_Formal => Element_Type;
14.1/5
   function Element (Container : List;
                     Position  : Cursor) return Element_Type
      with Pre => (Position /= No_Element or else
                      raise Constraint_Error) and then
                   (Has_Element (Container, Position) 
                      or else raise Program_Error),
           Nonblocking, Global => null, Use_Formal => Element_Type;
15/5
   procedure Replace_Element (Container : in out List;
                              Position  : in     Cursor;
                              New_item  : in     Element_Type)
      with Pre  => (not Tampering_With_Elements_Prohibited (Container)
                      or else raise Program_Error) and then
                   (Position /= No_Element
                      or else raise Constraint_Error) and then
                   (Has_Element (Container, Position) 
                      or else raise Program_Error);
16/5
   procedure Query_Element
     (Position : in Cursor;
      Process  : not null access procedure (Element : in Element_Type))
      with Pre  => Position /= No_Element or else raise Constraint_Error,
           Global => in all;
16.1/5
   procedure Query_Element
     (Container : in List;
      Position  : in Cursor;
      Process   : not null access procedure (Element : in Element_Type))
      with Pre  => (Position /= No_Element
                       or else raise Constraint_Error) and then
                    (Has_Element (Container, Position)
                       or else raise Program_Error);
17/5
   procedure Update_Element
     (Container : in out List;
      Position  : in     Cursor;
      Process   : not null access procedure
                      (Element : in out Element_Type))
      with Pre  => (Position /= No_Element 
                       or else raise Constraint_Error) and then
                    (Has_Element (Container, Position) 
                       or else raise Program_Error);
17.1/5
   type Constant_Reference_Type
         (Element : not null access constant Element_Type) is private
      with Implicit_Dereference => Element,
           Nonblocking, Global => in out synchronized,
           Default_Initial_Condition => (raise Program_Error);
17.2/5
   type Reference_Type (Element : not null access Element_Type) is private
      with Implicit_Dereference => Element,
           Nonblocking, Global => in out synchronized,
           Default_Initial_Condition => (raise Program_Error);
17.3/5
   function Constant_Reference (Container : aliased in List;
                                Position  : in Cursor)
      return Constant_Reference_Type
      with Pre  => (Position /= No_Element or else
                       raise Constraint_Error) and then
                    (Has_Element (Container, Position) or else
                       raise Program_Error),
           Post   => Tampering_With_Cursors_Prohibited (Container),
           Nonblocking, Global => null, Use_Formal => null;
17.4/5
   function Reference (Container : aliased in out List;
                       Position  : in Cursor)
      return Reference_Type
      with Pre  => (Position /= No_Element or else
                       raise Constraint_Error) and then
                    (Has_Element (Container, Position) or else
                       raise Program_Error),
           Post   => Tampering_With_Cursors_Prohibited (Container),
           Nonblocking, Global => null, Use_Formal => null;
17.5/5
   procedure Assign (Target : in out List; Source : in List)
      with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                      or else raise Program_Error,
           Post => Length (Source) = Length (Target);
17.6/5
   function Copy (Source : List)
      return List
      with Post => 
              Length (Copy'Result) = Length (Source) and then
              not Tampering_With_Elements_Prohibited (Copy'Result) and then
              not Tampering_With_Cursors_Prohibited (Copy'Result);
18/5
   procedure Move (Target : in out List;
                   Source : in out List)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                      or else raise Program_Error) and then
                   (not Tampering_With_Cursors_Prohibited (Source)
                      or else raise Program_Error),
            Post => (if not Target'Has_Same_Storage (Source) then
                      Length (Target) = Length (Source'Old) and then
                      Length (Source) = 0);
19/5
   procedure Insert (Container : in out List;
                     Before    : in     Cursor;
                     New_Item  : in     Element_Type;
                     Count     : in     Count_Type := 1)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error) and then
                   (Before = No_Element or else
                    Has_Element (Container, Before)
                      or else raise Program_Error) and then
                   (Length (Container) <= Count_Type'Last - Count
                      or else raise Constraint_Error),
           Post => Length (Container)'Old + Count = Length (Container);
20/5
   procedure Insert (Container : in out List;
                     Before    : in     Cursor;
                     New_Item  : in     Element_Type;
                     Position  :    out Cursor;
                     Count     : in     Count_Type := 1)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error) and then
                   (Before = No_Element or else
                    Has_Element (Container, Before)
                      or else raise Program_Error) and then
                   (Length (Container) <= Count_Type'Last - Count
                      or else raise Constraint_Error),
           Post => Length (Container)'Old + Count = Length (Container)
                   and then Has_Element (Container, Position);
21/5
   procedure Insert (Container : in out List;
                     Before    : in     Cursor;
                     Position  :    out Cursor;
                     Count     : in     Count_Type := 1)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error) and then
                   (Before = No_Element or else
                    Has_Element (Container, Before)
                      or else raise Program_Error) and then
                   (Length (Container) <= Count_Type'Last - Count
                      or else raise Constraint_Error),
           Post => Length (Container)'Old + Count = Length (Container)
                   and then Has_Element (Container, Position);
22/5
   procedure Prepend (Container : in out List;
                      New_Item  : in     Element_Type;
                      Count     : in     Count_Type := 1)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                       or else raise Program_Error) and then
                    (Length (Container) <= Count_Type'Last - Count
                       or else raise Constraint_Error),
           Post => Length (Container)'Old + Count = Length (Container);
23/5
   procedure Append (Container : in out List;
                     New_Item  : in     Element_Type;
                     Count     : in     Count_Type)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                       or else raise Program_Error) and then
                   (Length (Container) <= Count_Type'Last - Count
                       or else raise Constraint_Error),
           Post => Length (Container)'Old + Count = Length (Container);
23.1/5
   procedure Append (Container : in out List;
                     New_Item  : in     Element_Type)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                       or else raise Program_Error) and then
                   (Length (Container) <= Count_Type'Last - 1
                       or else raise Constraint_Error),
           Post => Length (Container)'Old + 1 = Length (Container);
24/5
   procedure Delete (Container : in out List;
                     Position  : in out Cursor;
                     Count     : in     Count_Type := 1)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error) and then
                   (Position /= No_Element
                      or else raise Constraint_Error) and then
                   (Has_Element (Container, Position)
                      or else raise Program_Error),
           Post => Length (Container)'Old - Count <= Length (Container)
                   and then Position = No_Element;
25/5
   procedure Delete_First (Container : in out List;
                           Count     : in     Count_Type := 1)
      with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                       or else raise Program_Error,
           Post => Length (Container)'Old - Count <= Length (Container);
26/5
   procedure Delete_Last (Container : in out List;
                          Count     : in     Count_Type := 1)
      with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                       or else raise Program_Error,
           Post => Length (Container)'Old - Count <= Length (Container);
27/5
   procedure Reverse_Elements (Container : in out List)
      with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                       or else raise Program_Error;
28/5
   procedure Swap (Container : in out List;
                   I, J      : in     Cursor)
      with Pre  => (not Tampering_With_Elements_Prohibited (Container)
                      or else raise Program_Error) and then
                   (I /= No_Element or else Constraint_Error) and then
                   (J /= No_Element or else Constraint_Error) and then
                   (Has_Element (Container, I)
                      or else raise Program_Error) and then
                   (Has_Element (Container, J)
                      or else raise Program_Error);
29/5
   procedure Swap_Links (Container : in out List;
                         I, J      : in     Cursor)
      with Pre  => (not Tampering_With_Elements_Prohibited (Container)
                       or else raise Program_Error) and then
                   (I /= No_Element or else Constraint_Error) and then
                   (J /= No_Element or else Constraint_Error) and then
                   (Has_Element (Container, I)
                       or else raise Program_Error) and then
                   (Has_Element (Container, J)
                       or else raise Program_Error);
30/5
   procedure Splice (Target   : in out List;
                     Before   : in     Cursor;
                     Source   : in out List)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                      or else raise Program_Error) and then
                   (not Tampering_With_Cursors_Prohibited (Source)
                      or else raise Program_Error) and then
                   (Before = No_Element or else
                    Has_Element (Target, Before)
                      or else raise Program_Error) and then
                   (Target'Has_Same_Storage (Source) or else
                    Length (Target) <= Count_Type'Last - Length (Source)
                      or else raise Constraint_Error),
           Post => (if not Target'Has_Same_Storage (Source) then
                      (declare
                         Result_Length : constant Count_Type :=
                            Length (Source)'Old + Length (Target)'Old;
                       begin
                         Length (Source) = 0 and then
                         Length (Target) = Result_Length));
31/5
   procedure Splice (Target   : in out List;
                     Before   : in     Cursor;
                     Source   : in out List;
                     Position : in out Cursor)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                      or else raise Program_Error) and then
                   (not Tampering_With_Cursors_Prohibited (Source)
                      or else raise Program_Error) and then
                   (Position /= No_Element
                      or else raise Constraint_Error) and then
                   (Has_Element (Source, Position)
                      or else raise Program_Error) and then
                   (Before = No_Element or else
                    Has_Element (Target, Before)
                      or else raise Program_Error) and then
                   (Target'Has_Same_Storage (Source) or else
                    Length (Target) <= Count_Type'Last - 1
                      or else raise Constraint_Error),
           Post => (declare
                      Org_Target_Length : constant Count_Type :=
                         Length (Target)'Old;
                      Org_Source_Length : constant Count_Type :=
                         Length (Source)'Old;
                    begin
                       (if Target'Has_Same_Storage (Source) then
                           Position = Position'Old
                        else 
                           Length (Source) = Org_Source_Length - 1 and then
                           Length (Target) = Org_Target_Length + 1 and then
                           Has_Element (Target, Position)));
32/2
   procedure Splice (Container: in out List;
                     Before   : in     Cursor;
                     Position : in     Cursor)
      with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error) and then
                   (Position /= No_Element
                      or else raise Constraint_Error) and then
                   (Has_Element (Container, Position)
                      or else raise Program_Error) and then
                   (Before = No_Element or else
                    Has_Element (Container, Before)
                      or else raise Program_Error),
           Post =>  Length (Container) = Length (Container)'Old;
33/5
   function First (Container : List) return Cursor
      with Nonblocking, Global => null, Use_Formal => null,
           Post => (if not Is_Empty (Container)
                    then Has_Element (Container, First'Result)
                    else First'Result = No_Element);
34/5
   function First_Element (Container : List)
      return Element_Type
      with Pre => (not Is_Empty (Container) 
                      or else raise Constraint_Error);
35/5
   function Last (Container : List) return Cursor
      with Nonblocking, Global => null, Use_Formal => null,
           Post => (if not Is_Empty (Container)
                    then Has_Element (Container, Last'Result)
                    else Last'Result = No_Element);
36/5
   function Last_Element (Container : List)
      return Element_Type
      with Pre => (not Is_Empty (Container) 
                      or else raise Constraint_Error);
37/5
   function Next (Position : Cursor) return Cursor
      with Nonblocking, Global => in all, Use_Formal => null,
           Post => (if Position = No_Element then Next'Result = No_Element);
37.1/5
   function Next (Container : List;
                  Position : Cursor) return Cursor
      with Nonblocking, Global => null, Use_Formal => null,
           Pre  => Position = No_Element or else
                   Has_Element (Container, Position)
                      or else raise Program_Error,
           Post => (if Position = No_Element then Next'Result = No_Element
                    elsif Next'Result = No_Element then
                      Position = Last (Container)
                    else Has_Element (Container, Next'Result));
38/5
   function Previous (Position : Cursor) return Cursor
      with Nonblocking, Global => in all, Use_Formal => null,
           Post => (if Position = No_Element then 
                      Previous'Result = No_Element);
38.1/5
   function Previous (Container : List;
                      Position  : Cursor) return Cursor
      with Nonblocking, Global => null, Use_Formal => null,
           Pre  => Position = No_Element or else
                   Has_Element (Container, Position)
                      or else raise Program_Error,
           Post => (if Position = No_Element then 
                      Previous'Result = No_Element
                    elsif Previous'Result = No_Element then
                      Position = First (Container)
                    else Has_Element (Container, Previous'Result));
39/5
   procedure Next (Position : in out Cursor)
      with Nonblocking, Global => in all, Use_Formal => null;
39.1/5
   procedure Next (Container : in     List;
                   Position  : in out Cursor)
      with Nonblocking, Global => null, Use_Formal => null,
           Pre  => Position = No_Element or else
                   Has_Element (Container, Position)
                      or else raise Program_Error,
           Post => (if Position /= No_Element
                    then Has_Element (Container, Position));
40/5
   procedure Previous (Position : in out Cursor)
      with Nonblocking, Global => in all, Use_Formal => null;
40.1/5
   procedure Previous (Container : in     List;
                       Position  : in out Cursor)
      with Nonblocking, Global => null, Use_Formal => null,
           Pre  => Position = No_Element or else
                   Has_Element (Container, Position)
                      or else raise Program_Error,
           Post => (if Position /= No_Element then 
                      Has_Element (Container, Position));
41/5
   function Find (Container : List;
                  Item      : Element_Type;
                  Position  : Cursor := No_Element)
      return Cursor
      with Pre  => Position = No_Element or else
                   Has_Element (Container, Position)
                      or else raise Program_Error,
           Post => (if Find'Result /= No_Element
                    then Has_Element (Container, Find'Result));
42/5
   function Reverse_Find (Container : List;
                          Item      : Element_Type;
                          Position  : Cursor := No_Element)
      return Cursor
      with Pre  => Position = No_Element or else
                   Has_Element (Container, Position)
                      or else raise Program_Error,
           Post => (if Reverse_Find'Result /= No_Element
                    then Has_Element (Container, Reverse_Find'Result));
43/2
   function Contains (Container : List;
                      Item      : Element_Type) return Boolean;
44/3
This paragraph was deleted.
45/5
   procedure  Iterate
     (Container : in List;
      Process   : not null access procedure (Position : in Cursor))
      with Allows_Exit;
46/5
   procedure Reverse_Iterate
     (Container : in List;
      Process   : not null access procedure (Position : in Cursor))
      with Allows_Exit;
46.1/5
   function Iterate (Container : in List)
      return List_Iterator_Interfaces.Parallel_Reversible_Iterator'Class
      with Post   => Tampering_With_Cursors_Prohibited (Container);
46.2/5
   function Iterate (Container : in List; Start : in Cursor)
      return List_Iterator_Interfaces.Reversible_Iterator'Class
      with Pre    => (Start /= No_Element
                        or else raise Constraint_Error) and then
                     (Has_Element (Container, Start)
                        or else raise Program_Error),
           Post   => Tampering_With_Cursors_Prohibited (Container);
47/5
   generic
      with function "<" (Left, Right : Element_Type)
         return Boolean is <>;
   package Generic_Sorting
   with Nonblocking, Global => null is
48/2
      function Is_Sorted (Container : List) return Boolean;
49/5
      procedure Sort (Container : in out List)
         with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                          or else raise Program_Error;
50/5
      procedure Merge (Target  : in out List;
                       Source  : in out List)
         with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                         or else raise Program_Error) and then
                      (not Tampering_With_Elements_Prohibited (Source)
                         or else raise Program_Error) and then
                      (Length (Target) <= Count_Type'Last - Length (Source)
                         or else raise Constraint_Error) and then
                      ((Length (Source) = 0 or else
                         not Target'Has_Same_Storage (Source))
                         or else raise Constraint_Error),
              Post => (declare
                         Result_Length : constant Count_Type :=
                            Length (Source)'Old + Length (Target)'Old;
                       begin
                         (Length (Source) = 0 and then
                          Length (Target) = Result_Length));
51/2
   end Generic_Sorting;
51.1/5
   package Stable is
51.2/5
      type List (Base : not null access Doubly_Linked_Lists.List) is
         tagged limited private
         with Constant_Indexing => Constant_Reference,
              Variable_Indexing => Reference,
              Default_Iterator  => Iterate,
              Iterator_Element  => Element_Type,
              Stable_Properties => (Length),
              Global => null,
              Default_Initial_Condition => Length (List) = 0,
              Preelaborable_Initialization;
51.3/5
      type Cursor is private
         with Preelaborable_Initialization;
51.4/5
      Empty_List : constant List;
51.5/5
      No_Element : constant Cursor;
51.6/5
      function Has_Element (Position : Cursor) return Boolean
         with Nonblocking, Global => in all, Use_Formal => null;
51.7/5
      package List_Iterator_Interfaces is new
         Ada.Iterator_Interfaces (Cursor, Has_Element);
51.8/5
      procedure Assign (Target : in out Doubly_Linked_Lists.List;
                        Source : in List)
         with Post => Length (Source) = Length (Target);
51.9/5
      function Copy (Source : Doubly_Linked_Lists.List) return List
         with Post => Length (Copy'Result) = Length (Source);
51.10/5
      type Constant_Reference_Type
            (Element : not null access constant Element_Type) is private
         with Implicit_Dereference => Element,
              Nonblocking, Global => null, Use_Formal => null,
              Default_Initial_Condition => (raise Program_Error);
51.11/5
      type Reference_Type
            (Element : not null access Element_Type) is private
         with Implicit_Dereference => Element,
              Nonblocking, Global => null, Use_Formal => null,
              Default_Initial_Condition => (raise Program_Error);
51.12/5
      -- Additional subprograms as described in the text
      -- are declared here.
51.13/5
   private
51.14/5
      ... -- not specified by the language
51.15/5
   end Stable;
52/2
private
53/2
   ... -- not specified by the language
54/2
end Ada.Containers.Doubly_Linked_Lists;
55/2
The actual function for the generic formal function "=" on Element_Type values is expected to define a reflexive and symmetric relationship and return the same result value each time it is called with a particular pair of values. If it behaves in some other manner, the functions Find, Reverse_Find, and "=" on list values return an unspecified value. The exact arguments and number of calls of this generic formal function by the functions Find, Reverse_Find, and "=" on list values are unspecified.
56/2
The type List is used to represent lists. The type List needs finalization (see 7.6).
57/2
Empty_List represents the empty List object. It has a length of 0. If an object of type List is not otherwise initialized, it is initialized to the same value as Empty_List.
58/2
No_Element represents a cursor that designates no element. If an object of type Cursor is not otherwise initialized, it is initialized to the same value as No_Element.
59/5
The primitive "=" operator for type Cursor returns True if both cursors are No_Element, or designate the same element in the same container.
60/2
Execution of the default implementation of the Input, Output, Read, or Write attribute of type Cursor raises Program_Error.
60.1/5
  List'Write for a List object L writes Length(L) elements of the list to the stream. It may also write additional information about the list.
60.2/3
  List'Read reads the representation of a list from the stream, and assigns to Item a list with the same length and elements as was written by List'Write.
61/5
Some operations check for “tampering with cursors” of a container because they depend on the set of elements of the container remaining constant, and others check for “tampering with elements” of a container because they depend on elements of the container not being replaced. When tampering with cursors is prohibited for a particular list object L, Program_Error is propagated by the finalization of L, as well as by a call that passes L to certain of the operations of this package, as indicated by the precondition of such an operation. Similarly, when tampering with elements is prohibited for L, Program_Error is propagated by a call that passes L to certain of the other operations of this package, as indicated by the precondition of such an operation.
Paragraphs 62 through 69 are removed as preconditions now describe these rules.
69.2/5
function Has_Element (Position : Cursor) return Boolean
   with Nonblocking, Global => in all, Use_Formal => null;
69.3/3
Returns True if Position designates an element, and returns False otherwise.
69.4/5
function Has_Element (Container : List; Position : Cursor)
   return Boolean
   with Nonblocking, Global => null, Use_Formal => null;
69.5/5
Returns True if Position designates an element in Container, and returns False otherwise.
70/2
function "=" (Left, Right : List) return Boolean;
71/3
If Left and Right denote the same list object, then the function returns True. If Left and Right have different lengths, then the function returns False. Otherwise, it compares each element in Left to the corresponding element in Right using the generic formal equality operator. If any such comparison returns False, the function returns False; otherwise, it returns True. Any exception raised during evaluation of element equality is propagated. 
71.1/5
function Tampering_With_Cursors_Prohibited
   (Container : List) return Boolean
   with Nonblocking, Global => null, Use_Formal => null;
71.2/5
Returns True if tampering with cursors or tampering with elements is currently prohibited for Container, and returns False otherwise.
71.3/5
function Tampering_With_Elements_Prohibited
   (Container : List) return Boolean
   with Nonblocking, Global => null, Use_Formal => null;
71.4/5
Always returns False, regardless of whether tampering with elements is prohibited.
72/5
function Length (Container : List) return Count_Type
   with Nonblocking, Global => null, Use_Formal => null;
73/2
Returns the number of elements in Container.
74/5
function Is_Empty (Container : List) return Boolean
   with Nonblocking, Global => null, Use_Formal => null,
        Post => Is_Empty'Result = (Length (Container) = 0);
75/5
Returns True if Container is empty.
76/5
procedure Clear (Container : in out List)
   with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error,
        Post => Length (Container) = 0;
77/2
Removes all the elements from Container.
78/5
function Element (Position : Cursor) return Element_Type
   with Pre  => Position /= No_Element or else raise Constraint_Error,
        Nonblocking, Global => in all, Use_Formal => Element_Type;
79/5
Element returns the element designated by Position.
79.1/5
function Element (Container : List;
                  Position  : Cursor) return Element_Type
   with Pre => (Position /= No_Element or else
                   raise Constraint_Error) and then
                (Has_Element (Container, Position) 
                   or else raise Program_Error),
        Nonblocking, Global => null, Use_Formal => Element_Type;
79.2/5
Element returns the element designated by Position in Container.
80/5
procedure Replace_Element (Container : in out List;
                           Position  : in     Cursor;
                           New_item  : in     Element_Type)
   with Pre  => (not Tampering_With_Elements_Prohibited (Container)
                   or else raise Program_Error) and then
                (Position /= No_Element
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position) 
                   or else raise Program_Error);
81/5
Replace_Element assigns the value New_Item to the element designated by Position. For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object (including itself).
82/5
procedure Query_Element
  (Position : in Cursor;
   Process  : not null access procedure (Element : in Element_Type))
   with Pre  => Position /= No_Element or else raise Constraint_Error,
        Global => in all;
83/5
Query_Element calls Process.all with the element designated by Position as the argument. Tampering with the elements of the list that contains the element designated by Position is prohibited during the execution of the call on Process.all. Any exception raised by Process.all is propagated.
83.1/5
procedure Query_Element
  (Container : in List;
   Position  : in Cursor;
   Process   : not null access procedure (Element : in Element_Type))
   with Pre  => (Position /= No_Element
                    or else raise Constraint_Error) and then
                 (Has_Element (Container, Position)
                    or else raise Program_Error);
83.2/5
Query_Element calls Process.all with the element designated by Position as the argument. Tampering with the elements of Container is prohibited during the execution of the call on Process.all. Any exception raised by Process.all is propagated.
84/5
procedure Update_Element
  (Container : in out List;
   Position  : in     Cursor;
   Process   : not null access procedure
                   (Element : in out Element_Type))
   with Pre  => (Position /= No_Element 
                    or else raise Constraint_Error) and then
                 (Has_Element (Container, Position) 
                    or else raise Program_Error);
85/5
Update_Element calls Process.all with the element designated by Position as the argument. Tampering with the elements of Container is prohibited during the execution of the call on Process.all. Any exception raised by Process.all is propagated.
86/2
If Element_Type is unconstrained and definite, then the actual Element parameter of Process.all shall be unconstrained.
86.1/5
type Constant_Reference_Type
      (Element : not null access constant Element_Type) is private
   with Implicit_Dereference => Element,
        Nonblocking, Global => in out synchronized,
        Default_Initial_Condition => (raise Program_Error);
86.2/5
type Reference_Type (Element : not null access Element_Type) is private
   with Implicit_Dereference => Element,
        Nonblocking, Global => in out synchronized,
        Default_Initial_Condition => (raise Program_Error);
86.3/3
The types Constant_Reference_Type and Reference_Type need finalization.
86.4/5
This paragraph was deleted.
86.5/5
function Constant_Reference (Container : aliased in List;
                             Position  : in Cursor)
   return Constant_Reference_Type
   with Pre  => (Position /= No_Element or else
                    raise Constraint_Error) and then
                 (Has_Element (Container, Position) or else
                    raise Program_Error),
        Post   => Tampering_With_Cursors_Prohibited (Container),
        Nonblocking, Global => null, Use_Formal => null;
86.6/3
This function (combined with the Constant_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read access to an individual element of a list given a cursor.
86.7/5
Constant_Reference returns an object whose discriminant is an access value that designates the element designated by Position. Tampering with the elements of Container is prohibited while the object returned by Constant_Reference exists and has not been finalized.
86.8/5
function Reference (Container : aliased in out List;
                    Position  : in Cursor)
   return Reference_Type
   with Pre  => (Position /= No_Element or else
                    raise Constraint_Error) and then
                 (Has_Element (Container, Position) or else 
                    raise Program_Error),
        Post   => Tampering_With_Cursors_Prohibited (Container),
        Nonblocking, Global => null, Use_Formal => null;
86.9/3
This function (combined with the Variable_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read and write access to an individual element of a list given a cursor.
86.10/5
Reference returns an object whose discriminant is an access value that designates the element designated by Position. Tampering with the elements of Container is prohibited while the object returned by Reference exists and has not been finalized.
86.11/5
procedure Assign (Target : in out List; Source : in List)
   with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                   or else raise Program_Error,
        Post => Length (Source) = Length (Target);
86.12/3
If Target denotes the same object as Source, the operation has no effect. Otherwise, the elements of Source are copied to Target as for an assignment_statement assigning Source to Target. 
86.13/5
function Copy (Source : List)
   return List
   with Post => 
           Length (Copy'Result) = Length (Source) and then
           not Tampering_With_Elements_Prohibited (Copy'Result) and then
           not Tampering_With_Cursors_Prohibited (Copy'Result);
86.14/3
Returns a list whose elements match the elements of Source.
87/5
procedure Move (Target : in out List;
                Source : in out List)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                    or else raise Program_Error) and then
                (not Tampering_With_Cursors_Prohibited (Source)
                    or else raise Program_Error),
        Post => (if not Target'Has_Same_Storage (Source) then
                    Length (Target) = Length (Source'Old) and then
                    Length (Source) = 0);
88/3
If Target denotes the same object as Source, then the operation has no effect. Otherwise, the operation is equivalent to Assign (Target, Source) followed by Clear (Source).
89/5
procedure Insert (Container : in out List;
                  Before    : in     Cursor;
                  New_Item  : in     Element_Type;
                  Count     : in     Count_Type := 1)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (Before = No_Element or else
                 Has_Element (Container, Before)
                   or else raise Program_Error) and then
                (Length (Container) <= Count_Type'Last - Count
                   or else raise Constraint_Error),
        Post => Length (Container)'Old + Count = Length (Container);
90/5
Insert inserts Count copies of New_Item prior to the element designated by Before. If Before equals No_Element, the new elements are inserted after the last node (if any). Any exception raised during allocation of internal storage is propagated, and Container is not modified.
91/5
procedure Insert (Container : in out List;
                  Before    : in     Cursor;
                  New_Item  : in     Element_Type;
                  Position  :    out Cursor;
                  Count     : in     Count_Type := 1)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (Before = No_Element or else
                 Has_Element (Container, Before)
                   or else raise Program_Error) and then
                (Length (Container) <= Count_Type'Last - Count
                   or else raise Constraint_Error),
        Post => Length (Container)'Old + Count = Length (Container)
                and then Has_Element (Container, Position);
92/5
Insert allocates Count copies of New_Item, and inserts them prior to the element designated by Before. If Before equals No_Element, the new elements are inserted after the last element (if any). Position designates the first newly-inserted element, or if Count equals 0, then Position is assigned the value of Before. Any exception raised during allocation of internal storage is propagated, and Container is not modified.
93/5
procedure Insert (Container : in out List;
                  Before    : in     Cursor;
                  Position  :    out Cursor;
                  Count     : in     Count_Type := 1)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (Before = No_Element or else
                 Has_Element (Container, Before)
                   or else raise Program_Error) and then
                (Length (Container) <= Count_Type'Last - Count
                   or else raise Constraint_Error),
        Post => Length (Container)'Old + Count = Length (Container)
                and then Has_Element (Container, Position);
94/5
Insert inserts Count new elements prior to the element designated by Before. If Before equals No_Element, the new elements are inserted after the last node (if any). The new elements are initialized by default (see 3.3.1). Position designates the first newly-inserted element, or if Count equals 0, then Position is assigned the value of Before. Any exception raised during allocation of internal storage is propagated, and Container is not modified.
95/5
procedure Prepend (Container : in out List;
                   New_Item  : in     Element_Type;
                   Count     : in     Count_Type := 1)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (Length (Container) <= Count_Type'Last - Count
                   or else raise Constraint_Error),
        Post => Length (Container)'Old + Count = Length (Container);
96/2
Equivalent to Insert (Container, First (Container), New_Item, Count).
97/5
procedure Append (Container : in out List;
                  New_Item  : in     Element_Type;
                  Count     : in     Count_Type)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (Length (Container) <= Count_Type'Last - Count
                   or else raise Constraint_Error),
        Post => Length (Container)'Old + Count = Length (Container);
98/2
Equivalent to Insert (Container, No_Element, New_Item, Count).
98.1/5
procedure Append (Container : in out List;
                  New_Item  : in     Element_Type)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (Length (Container) <= Count_Type'Last - 1
                   or else raise Constraint_Error),
        Post => Length (Container)'Old + 1 = Length (Container);
98.2/5
Equivalent to Insert (Container, No_Element, New_Item, 1).
99/5
procedure Delete (Container : in out List;
                  Position  : in out Cursor;
                  Count     : in     Count_Type := 1)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (Position /= No_Element
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position)
                   or else raise Program_Error),
        Post => Length (Container)'Old - Count <= Length (Container)
                and then Position = No_Element;
100/5
Delete removes (from Container) Count elements starting at the element designated by Position (or all of the elements starting at Position if there are fewer than Count elements starting at Position). Finally, Position is set to No_Element.
101/5
procedure Delete_First (Container : in out List;
                        Count     : in     Count_Type := 1)
   with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error,
        Post => Length (Container)'Old - Count <= Length (Container);
102/3
If Length (Container) <= Count, then Delete_First is equivalent to Clear (Container). Otherwise, it removes the first Count nodes from Container.
103/5
procedure Delete_Last (Container : in out List;
                       Count     : in     Count_Type := 1)
   with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error,
        Post => Length (Container)'Old - Count <= Length (Container);
104/3
If Length (Container) <= Count, then Delete_Last is equivalent to Clear (Container). Otherwise, it removes the last Count nodes from Container.
105/5
procedure Reverse_Elements (Container : in out List)
   with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error;
106/2
Reorders the elements of Container in reverse order.
107/5
procedure Swap (Container : in out List;
                I, J      : in     Cursor)
   with Pre  => (not Tampering_With_Elements_Prohibited (Container)
                   or else raise Program_Error) and then
                (I /= No_Element or else Constraint_Error) and then
                (J /= No_Element or else Constraint_Error) and then
                (Has_Element (Container, I)
                   or else raise Program_Error) and then
                (Has_Element (Container, J)
                   or else raise Program_Error);
108/5
Swap exchanges the values of the elements designated by I and J.
109/5
procedure Swap_Links (Container : in out List;
                      I, J      : in     Cursor)
   with Pre  => (not Tampering_With_Elements_Prohibited (Container)
                   or else raise Program_Error) and then
                (I /= No_Element or else Constraint_Error) and then
                (J /= No_Element or else Constraint_Error) and then
                (Has_Element (Container, I)
                   or else raise Program_Error) and then
                (Has_Element (Container, J)
                   or else raise Program_Error);
110/5
Swap_Links exchanges the nodes designated by I and J.
111/5
procedure Splice (Target   : in out List;
                  Before   : in     Cursor;
                  Source   : in out List)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                   or else raise Program_Error) and then
                (not Tampering_With_Cursors_Prohibited (Source)
                   or else raise Program_Error) and then
                (Before = No_Element or else
                 Has_Element (Target, Before)
                   or else raise Program_Error) and then
                (Target'Has_Same_Storage (Source) or else
                 Length (Target) <= Count_Type'Last - Length (Source)
                   or else raise Constraint_Error),
        Post => (if not Target'Has_Same_Storage (Source) then
                   (declare
                      Result_Length : constant Count_Type :=
                         Length (Source)'Old + Length (Target)'Old;
                    begin
                      Length (Source) = 0 and then
                      Length (Target) = Result_Length));
112/5
If Source denotes the same object as Target, the operation has no effect. Otherwise, Splice reorders elements such that they are removed from Source and moved to Target, immediately prior to Before. If Before equals No_Element, the nodes of Source are spliced after the last node of Target.
113/5
procedure Splice (Target   : in out List;
                  Before   : in     Cursor;
                  Source   : in out List;
                  Position : in out Cursor)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                   or else raise Program_Error) and then
                (not Tampering_With_Cursors_Prohibited (Source)
                   or else raise Program_Error) and then
                (Position /= No_Element
                   or else raise Constraint_Error) and then
                (Has_Element (Source, Position)
                   or else raise Program_Error) and then
                (Before = No_Element or else
                 Has_Element (Target, Before)
                   or else raise Program_Error) and then
                (Target'Has_Same_Storage (Source) or else
                 Length (Target) <= Count_Type'Last - 1
                   or else raise Constraint_Error),
        Post => (declare
                   Org_Target_Length : constant Count_Type :=
                      Length (Target)'Old;
                   Org_Source_Length : constant Count_Type :=
                      Length (Source)'Old;
                 begin
                    (if Target'Has_Same_Storage (Source) then
                        Position = Position'Old
                     else Length (Source) = Org_Source_Length - 1 and then
                        Length (Target) = Org_Target_Length + 1 and then
                        Has_Element (Target, Position)));
114/5
If Source denotes the same object as Target, then there is no effect if Position equals Before, else the element designated by Position is moved immediately prior to Before, or, if Before equals No_Element, after the last element. Otherwise, the element designated by Position is removed from Source and moved to Target, immediately prior to Before, or, if Before equals No_Element, after the last element of Target. Position is updated to represent an element in Target. 
115/5
procedure Splice (Container: in out List;
                  Before   : in     Cursor;
                  Position : in     Cursor)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                   or else raise Program_Error) and then
                (Position /= No_Element
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position)
                   or else raise Program_Error) and then
                (Before = No_Element or else
                 Has_Element (Container, Before)
                   or else raise Program_Error),
        Post =>  Length (Container) = Length (Container)'Old;
116/5
If Position equals Before there is no effect. Otherwise, the element designated by Position is moved immediately prior to Before, or, if Before equals No_Element, after the last element.
117/5
function First (Container : List) return Cursor
   with Nonblocking, Global => null, Use_Formal => null,
        Post => (if not Is_Empty (Container)
                 then Has_Element (Container, First'Result)
                 else First'Result = No_Element);
118/2
If Container is empty, First returns No_Element. Otherwise, it returns a cursor that designates the first node in Container.
119/5
function First_Element (Container : List)
   return Element_Type
   with Pre => (not Is_Empty (Container) 
                   or else raise Constraint_Error);
120/2
Equivalent to Element (Container, First_Index (Container)).
121/5
function Last (Container : List) return Cursor
   with Nonblocking, Global => null, Use_Formal => null,
        Post => (if not Is_Empty (Container)
                 then Has_Element (Container, Last'Result)
                 else Last'Result = No_Element);
122/2
If Container is empty, Last returns No_Element. Otherwise, it returns a cursor that designates the last node in Container.
123/5
function Last_Element (Container : List)
   return Element_Type
   with Pre => (not Is_Empty (Container) 
                   or else raise Constraint_Error);
124/2
Equivalent to Element (Last (Container)).
125/5
function Next (Position : Cursor) return Cursor
   with Nonblocking, Global => in all, Use_Formal => null,
        Post => (if Position = No_Element then Next'Result = No_Element);
126/2
If Position equals No_Element or designates the last element of the container, then Next returns the value No_Element. Otherwise, it returns a cursor that designates the successor of the element designated by Position.
126.1/5
function Next (Container : List;
               Position  : Cursor) return Cursor
   with Nonblocking, Global => null, Use_Formal => null,
        Pre  => Position = No_Element or else
                Has_Element (Container, Position)
                   or else raise Program_Error,
        Post => (if Position = No_Element then Next'Result = No_Element
                 elsif Next'Result = No_Element then
                   Position = Last (Container)
                 else Has_Element (Container, Next'Result));
126.2/5
Returns a cursor designating the successor of the element designated by Position in Container.
127/5
function Previous (Position : Cursor) return Cursor
   with Nonblocking, Global => in all, Use_Formal => null,
        Post => (if Position = No_Element then 
                   Previous'Result = No_Element);
128/2
If Position equals No_Element or designates the first element of the container, then Previous returns the value No_Element. Otherwise, it returns a cursor that designates the predecessor of the element designated by Position.
128.1/5
function Previous (Container : List;
                   Position : Cursor) return Cursor
   with Nonblocking, Global => null, Use_Formal => null,
        Pre  => Position = No_Element or else
                Has_Element (Container, Position)
                   or else raise Program_Error,
        Post => (if Position = No_Element then 
                   Previous'Result = No_Element
                 elsif Previous'Result = No_Element then
                   Position = First (Container)
                 else Has_Element (Container, Previous'Result));
128.2/5
Returns a cursor designating the predecessor of the element designated by Position in Container, if any.
129/5
procedure Next (Position : in out Cursor)
   with Nonblocking, Global => in all, Use_Formal => null;
130/2
Equivalent to Position := Next (Position).
130.1/5
procedure Next (Container : in     List;
                Position  : in out Cursor)
   with Nonblocking, Global => null, Use_Formal => null,
        Pre  => Position = No_Element or else
                Has_Element (Container, Position)
                   or else raise Program_Error,
        Post => (if Position /= No_Element
                 then Has_Element (Container, Position));
130.2/5
Equivalent to Position := Next (Container, Position).
131/5
procedure Previous (Position : in out Cursor)
   with Nonblocking, Global => in all, Use_Formal => null;
132/2
Equivalent to Position := Previous (Position).
132.1/5
procedure Previous (Container : in     List;
                    Position  : in out Cursor)
   with Nonblocking, Global => null, Use_Formal => null,
        Pre  => Position = No_Element or else
                Has_Element (Container, Position)
                   or else raise Program_Error,
        Post => (if Position /= No_Element
                 then Has_Element (Container, Position));
132.2/5
Equivalent to Position := Previous (Container, Position).
133/5
function Find (Container : List;
               Item      : Element_Type;
               Position  : Cursor := No_Element)
   return Cursor
   with Pre  => Position = No_Element or else
                Has_Element (Container, Position)
                   or else raise Program_Error,
        Post => (if Find'Result /= No_Element
                 then Has_Element (Container, Find'Result));
134/5
Find searches the elements of Container for an element equal to Item (using the generic formal equality operator). The search starts at the element designated by Position, or at the first element if Position equals No_Element. It proceeds towards Last (Container). If no equal element is found, then Find returns No_Element. Otherwise, it returns a cursor designating the first equal element encountered.
135/5
function Reverse_Find (Container : List;
                       Item      : Element_Type;
                       Position  : Cursor := No_Element)
   return Cursor
   with Pre  => Position = No_Element or else
                Has_Element (Container, Position)
                   or else raise Program_Error,
        Post => (if Reverse_Find'Result /= No_Element
                 then Has_Element (Container, Reverse_Find'Result));
136/5
Find searches the elements of Container for an element equal to Item (using the generic formal equality operator). The search starts at the element designated by Position, or at the last element if Position equals No_Element. It proceeds towards First (Container). If no equal element is found, then Reverse_Find returns No_Element. Otherwise, it returns a cursor designating the first equal element encountered.
137/2
function Contains (Container : List;
                   Item      : Element_Type) return Boolean;
138/2
Equivalent to Find (Container, Item) /= No_Element.
Paragraphs 139 and 140 were moved above. 
141/5
procedure Iterate
  (Container : in List;
   Process   : not null access procedure (Position : in Cursor))
   with Allows_Exit;
142/3
Iterate calls Process.all with a cursor that designates each node in Container, starting with the first node and moving the cursor as per the Next function. Tampering with the cursors of Container is prohibited during the execution of a call on Process.all. Any exception raised by Process.all is propagated.
143/5
procedure Reverse_Iterate
  (Container : in List;
   Process   : not null access procedure (Position : in Cursor))
   with Allows_Exit;
144/3
Iterates over the nodes in Container as per procedure Iterate, except that elements are traversed in reverse order, starting with the last node and moving the cursor as per the Previous function.
144.1/5
function Iterate (Container : in List)
   return List_Iterator_Interfaces.Parallel_Reversible_Iterator'Class
   with Post   => Tampering_With_Cursors_Prohibited (Container);
144.2/5
Iterate returns an iterator object (see 5.5.1) that will generate a value for a loop parameter (see 5.5.2) designating each node in Container, starting with the first node and moving the cursor as per the Next function when used as a forward iterator, and starting with the last node and moving the cursor as per the Previous function when used as a reverse iterator, and processing all nodes concurrently when used as a parallel iterator. Tampering with the cursors of Container is prohibited while the iterator object exists (in particular, in the sequence_of_statements of the loop_statement whose iterator_specification denotes this object). The iterator object needs finalization.
144.3/5
function Iterate (Container : in List; Start : in Cursor)
   return List_Iterator_Interfaces.Reversible_Iterator'Class
   with Pre    => (Start /= No_Element
                        or else raise Constraint_Error) and then
                     (Has_Element (Container, Start)
                        or else raise Program_Error),
        Post   => Tampering_With_Cursors_Prohibited (Container);
144.4/5
Iterate returns a reversible iterator object (see 5.5.1) that will generate a value for a loop parameter (see 5.5.2) designating each node in Container, starting with the node designated by Start and moving the cursor as per the Next function when used as a forward iterator, or moving the cursor as per the Previous function when used as a reverse iterator. Tampering with the cursors of Container is prohibited while the iterator object exists (in particular, in the sequence_of_statements of the loop_statement whose iterator_specification denotes this object). The iterator object needs finalization.
145/3
 The actual function for the generic formal function "<" of Generic_Sorting is expected to return the same value each time it is called with a particular pair of element values. It should define a strict weak ordering relationship (see A.18); it should not modify Container. If the actual for "<" behaves in some other manner, the behavior of the subprograms of Generic_Sorting are unspecified. The number of times the subprograms of Generic_Sorting call "<" is unspecified.
146/2
function Is_Sorted (Container : List) return Boolean;
147/2
Returns True if the elements are sorted smallest first as determined by the generic formal "<" operator; otherwise, Is_Sorted returns False. Any exception raised during evaluation of "<" is propagated.
148/5
procedure Sort (Container : in out List)
   with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error;
149/2
Reorders the nodes of Container such that the elements are sorted smallest first as determined by the generic formal "<" operator provided. The sort is stable. Any exception raised during evaluation of "<" is propagated.
150/5
procedure Merge (Target  : in out List;
                 Source  : in out List)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                   or else raise Program_Error) and then
                (not Tampering_With_Elements_Prohibited (Source)
                   or else raise Program_Error) and then
                (Length (Target) <= Count_Type'Last - Length (Source)
                   or else raise Constraint_Error) and then
                ((Length (Source) = 0 or else
                   not Target'Has_Same_Storage (Source))
                   or else raise Constraint_Error),
        Post => (declare
                   Result_Length : constant Count_Type :=
                      Length (Source)'Old + Length (Target)'Old;
                 begin
                   (Length (Source) = 0 and then
                    Length (Target) = Result_Length));
151/5
Merge removes elements from Source and inserts them into Target; afterwards, Target contains the union of the elements that were initially in Source and Target; Source is left empty. If Target and Source are initially sorted smallest first, then Target is ordered smallest first as determined by the generic formal "<" operator; otherwise, the order of elements in Target is unspecified. Any exception raised during evaluation of "<" is propagated.
151.1/5
   The nested package Doubly_Linked_Lists.Stable provides a type Stable.List that represents a stable list, which is one that cannot grow and shrink. Such a list can be created by calling the Copy function, or by establishing a stabilized view of an ordinary list.
151.2/5
   The subprograms of package Containers.Doubly_Linked_Lists that have a parameter or result of type List are included in the nested package Stable with the same specification, except that the following are omitted:
151.3/5
Tampering_With_Cursors_Prohibited, Tampering_With_Elements_Prohibited, Assign, Move, Insert, Append, Prepend, Clear, Delete, Delete_First, Delete_Last, Splice, Swap_Links, and Reverse_Elements 
151.4/5
   The operations of this package are equivalent to those for ordinary lists, except that the calls to Tampering_With_Cursors_Prohibited and Tampering_With_Elements_Prohibited that occur in preconditions are replaced by False, and any that occur in postconditions are replaced by True.
151.5/5
   If a stable list is declared with the Base discriminant designating a pre-existing ordinary list, the stable list represents a stabilized view of the underlying ordinary list, and any operation on the stable list is reflected on the underlying ordinary list. While a stabilized view exists, any operation that tampers with elements performed on the underlying list is prohibited. The finalization of a stable list that provides such a view removes this restriction on the underlying ordinary list (though some other restriction can exist due to other concurrent iterations or stabilized views).
151.6/5
   If a stable list is declared without specifying Base, the object is necessarily initialized. The initializing expression of the stable list, typically a call on Copy, determines the Length of the list. The Length of a stable list never changes after initialization.

Bounded (Run-Time) Errors

152/2
 Calling Merge in an instance of Generic_Sorting with either Source or Target not ordered smallest first using the provided generic formal "<" operator is a bounded error. Either Program_Error is raised after Target is updated as described for Merge, or the operation works as defined.
152.1/3
   It is a bounded error for the actual function associated with a generic formal subprogram, when called as part of an operation of this package, to tamper with elements of any List parameter of the operation. Either Program_Error is raised, or the operation works as defined on the value of the List either prior to, or subsequent to, some or all of the modifications to the List.
152.2/3
   It is a bounded error to call any subprogram declared in the visible part of Containers.Doubly_Linked_Lists when the associated container has been finalized. If the operation takes Container as an in out parameter, then it raises Constraint_Error or Program_Error. Otherwise, the operation either proceeds as it would for an empty container, or it raises Constraint_Error or Program_Error. 

Erroneous Execution

153/2
 A Cursor value is invalid if any of the following have occurred since it was created:
154/2
The list that contains the element it designates has been finalized;
154.1/3
The list that contains the element it designates has been used as the Target of a call to Assign, or as the target of an assignment_statement;
155/2
The list that contains the element it designates has been used as the Source or Target of a call to Move; or 
156/3
The element it designates has been removed from the list that previously contained the element. 
157/2
 The result of "=" or Has_Element is unspecified if it is called with an invalid cursor parameter. Execution is erroneous if any other subprogram declared in Containers.Doubly_Linked_Lists is called with an invalid cursor parameter.
157.1/3
   Execution is erroneous if the list associated with the result of a call to Reference or Constant_Reference is finalized before the result object returned by the call to Reference or Constant_Reference is finalized. 

Implementation Requirements

158/5
 No storage associated with a doubly-linked list object shall be lost upon assignment or scope exit.
159/3
 The execution of an assignment_statement for a list shall have the effect of copying the elements from the source list object to the target list object and changing the length of the target object to that of the source object.

Implementation Advice

160/2
 Containers.Doubly_Linked_Lists should be implemented similarly to a linked list. In particular, if N is the length of a list, then the worst-case time complexity of Element, Insert with Count=1, and Delete with Count=1 should be O(log N). 
161/2
 The worst-case time complexity of a call on procedure Sort of an instance of Containers.Doubly_Linked_Lists.Generic_Sorting should be O(N**2), and the average time complexity should be better than O(N**2). 
162/2
 Move should not copy elements, and should minimize copying of internal data structures. 
163/2
 If an exception is propagated from a list operation, no storage should be lost, nor any elements removed from a list unless specified by the operation. 
164/5
NOTE   Sorting a list never copies elements, and is a stable sort (equal elements remain in the original order). This is different than sorting an array or vector, which will often copy elements, and hence is probably not a stable sort. 
Contents   Index   References   Search   Previous   Next 
Ada-Europe Ada 2005 and 2012 Editions sponsored in part by Ada-Europe