Ada Conformity Assessment Authority      Home Conformity Assessment   Test Suite ARGAda Standard
 
Annotated Ada Reference Manual (Ada 202x Draft 25)Legal Information
Contents   Index   References   Search   Previous   Next 

A.18.9 The Generic Package Containers.Ordered_Sets

Static Semantics

1/2
{AI95-00302-03} The generic library package Containers.Ordered_Sets has the following declaration: 
2/5
{AI05-0084-1} {AI05-0212-1} {AI12-0112-1} with Ada.Iterator_Interfaces;
generic
   type Element_Type is private;
   with function "<" (Left, Right : Element_Type) return Boolean is <>;
   with function "=" (Left, Right : Element_Type) return Boolean is <>;
package Ada.Containers.Ordered_Sets is
   with Preelaborate, Remote_Types,
        Nonblocking, Global => null is

   pragma Preelaborate(Ordered_Sets);
   pragma Remote_Types(Ordered_Sets);
2.a/5
Discussion: {AI12-0112-1} For discussion on the reasons and meaning of the specifications of the Global and Nonblocking aspects in this generic package, see the notes on the equivalent operations in the specification of the Containers.Vectors package (see A.18.2).
3/2
   function Equivalent_Elements (Left, Right : Element_Type) return Boolean;
4/5
{AI05-0212-1} {AI12-0111-1} {AI12-0112-1} {AI12-0212-1} {AI12-0339-1}    type Set is tagged private
      with Constant_Indexing => Constant_Reference,
           Default_Iterator  => Iterate,
           Iterator_Element  => Element_Type,
           Iterator_View     => Stable.Set,
           Aggregate         => (Empty       => Empty,
                                 Add_Unnamed => Include),
           Stable_Properties => (Length,
                                 Tampering_With_Cursors_Prohibited),
           Default_Initial_Condition =>
              Length (Set) = 0 and then
              (not Tampering_With_Cursors_Prohibited (Set))
;
   pragma Preelaborable_Initialization(Set);
5/2
   type Cursor is private;
   pragma Preelaborable_Initialization(Cursor);
6/2
   Empty_Set : constant Set;
7/2
   No_Element : constant Cursor;
7.1/5
{AI05-0212-1} {AI12-0112-1}    function Has_Element (Position : Cursor) return Boolean
      with Nonblocking, Global => (in alluse null)
;
7.2/5
{AI12-0112-1}    function Has_Element (Container : Set; Position : Cursor)
      return Boolean
      with Nonblocking, Global => (nulluse null);
7.3/3
{AI05-0212-1}    package Set_Iterator_Interfaces is new
       Ada.Iterator_Interfaces (Cursor, Has_Element);
8/2
   function "=" (Left, Right : Set) return Boolean;
9/2
   function Equivalent_Sets (Left, Right : Set) return Boolean;
9.1/5
{AI12-0112-1}    function Tampering_With_Cursors_Prohibited
      (Container : Set) return Boolean
      with Nonblocking, Global => (nulluse null);
9.2/5
{AI12-0339-1}    function Empty return Set
      is (Empty_Set)
      with Post =>
         not Tampering_With_Cursors_Prohibited (Empty'Result) and then
         Length (Empty'Result) = 0;
10/5
{AI12-0112-1}    function To_Set (New_Item : Element_Type) return Set
      with Post => Length (To_Set'Result) = 1 and then
                 not Tampering_with_Cursors_Prohibited (To_Set'Result)
;
11/5
{AI12-0112-1}    function Length (Container : Set) return Count_Type
      with Nonblocking, Global => (nulluse null)
;
12/5
{AI12-0112-1}    function Is_Empty (Container : Set) return Boolean
      with Nonblocking, Global => (nulluse null),
           Post => Is_Empty'Result = (Length (Container) = 0)
;
13/5
{AI12-0112-1}    procedure Clear (Container : in out Set)
      with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                       or else raise Program_Error,
           Post => Length (Container) = 0
;
14/5
{AI12-0112-1}    function Element (Position : Cursor) return Element_Type
      with Pre  => Position /= No_Element or else raise Constraint_Error,
           Nonblocking => Element_Type'Nonblocking,
           Global => (in alluse Element_Type)
;
14.1/5
{AI12-0112-1}    function Element (Container : Set;
                     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 => Element_Type'Nonblocking,
           Global => (nulluse Element_Type);
15/5
{AI12-0112-1}    procedure Replace_Element (Container : in out Set;
                              Position  : in     Cursor;
                              New_item  : in     Element_Type)
      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)
;
16/5
{AI12-0112-1}    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
{AI12-0112-1}    procedure Query_Element
     (Container : in Set;
      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);
16.2/5
{AI05-0212-1} {AI12-0112-1}    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)
;
16.3/5
{AI05-0212-1} {AI12-0112-1}    function Constant_Reference (Container : aliased in Set;
                                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 => (nulluse null)
;
16.4/5
{AI05-0001-1} {AI12-0112-1}    procedure Assign (Target : in out Set; Source : in Set)
      with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                      or else raise Program_Error,
           Post => Length (Source) = Length (Target)
;
16.5/5
{AI05-0001-1} {AI12-0112-1}    function Copy (Source : Set) return Set
      with Post => Length (Copy'Result) = Length (Source) and then
                   not Tampering_With_Cursors_Prohibited (Copy'Result)
;
17/5
{AI12-0112-1}    procedure Move (Target : in out Set;
                   Source : in out Set)
      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 Target = Source then True
                    else
                       Length (Target) = Length (Source'Old) and then
                       Length (Source) = 0)
;
18/5
{AI12-0112-1}    procedure Insert (Container : in out Set;
                     New_Item  : in     Element_Type;
                     Position  :    out Cursor;
                     Inserted  :    out Boolean)
      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 => (declare
                      Original_Length : constant Count_Type :=
                         Length (Container)'Old;
                    begin
                      Has_Element (Container, Position) and then
                     (if Inserted then
                        Length (Container) = Original_Length + 1
                      else
                        Length (Container) = Original_Length))
;
19/5
{AI12-0112-1}    procedure Insert (Container : in out Set;
                     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) = Length (Container)'Old + 1
;
20/5
{AI12-0112-1}    procedure Include (Container : in out Set;
                      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 => (declare
                      Original_Length : constant Count_Type :=
                         Length (Container)'Old;
                    begin
                      Length (Container)
                         in Original_Length | Original_Length + 1)
;
21/5
{AI12-0112-1}    procedure Replace (Container : in out Set;
                      New_Item  : in     Element_Type)
      with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error,
           Post => Length (Container) = Length (Container)'Old
;
22/5
{AI12-0112-1}    procedure Exclude (Container : in out Set;
                      Item      : in     Element_Type)
      with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error,
           Post => (declare
                      Original_Length : constant Count_Type :=
                         Length (Container)'Old;
                    begin
                      Length (Container)
                         in Original_Length - 1 | Original_Length)
;
23/5
{AI12-0112-1}    procedure Delete (Container : in out Set;
                     Item      : in     Element_Type)
      with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error,
           Post => Length (Container) = Length (Container)'Old - 1
;
24/5
{AI12-0112-1}    procedure Delete (Container : in out Set;
                     Position  : in out 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),
           Post => Length (Container) = Length (Container)'Old - 1 and then
                   Position = No_Element
;
25/5
{AI12-0112-1}    procedure Delete_First (Container : in out Set)
      with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error,
           Post => (declare
                      Original_Length : constant Count_Type :=
                         Length (Container)'Old;
                    begin
                      (if Original_Length = 0 then Length (Container) = 0
                       else Length (Container) = Original_Length - 1))
;
26/5
{AI12-0112-1}    procedure Delete_Last (Container : in out Set)
      with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                      or else raise Program_Error,
           Post => (declare
                      Original_Length : constant Count_Type :=
                         Length (Container)'Old;
                    begin
                      (if Original_Length = 0 then Length (Container) = 0
                       else Length (Container) = Original_Length - 1))
;
27/5
{AI12-0112-1}    procedure Union (Target : in out Set;
                    Source : in     Set)
      with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                      or else raise Program_Error,
           Post => Length (Target) <= Length (Target)'Old + Length (Source)
;
28/5
{AI12-0112-1}    function Union (Left, Right : Set) return Set
      with Post => Length (Union'Result) <= Length (Left) + Length (Right) and then
                   not Tampering_With_Cursors_Prohibited (Union'Result)
;
29/2
   function "or" (Left, Right : Set) return Set renames Union;
30/5
{AI12-0112-1}    procedure Intersection (Target : in out Set;
                           Source : in     Set)
      with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                      or else raise Program_Error,
           Post => Length (Target) <= Length (Target)'Old + Length (Source)
;
31/5
{AI12-0112-1}    function Intersection (Left, Right : Set) return Set
      with Post => Length (Intersection'Result) <= Length (Left) + Length (Right) and then
                   not Tampering_With_Cursors_Prohibited (Intersection'Result)
;
32/2
   function "and" (Left, Right : Set) return Set renames Intersection;
33/5
{AI12-0112-1}    procedure Difference (Target : in out Set;
                         Source : in     Set)
      with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                      or else raise Program_Error,
           Post => Length (Target) <= Length (Target)'Old + Length (Source)
;
34/5
{AI12-0112-1}    function Difference (Left, Right : Set) return Set
      with Post => Length (Difference'Result) <= Length (Left) + Length (Right) and then
                   not Tampering_With_Cursors_Prohibited (Difference'Result)
;
35/2
   function "-" (Left, Right : Set) return Set renames Difference;
36/5
{AI12-0112-1}    procedure Symmetric_Difference (Target : in out Set;
                                   Source : in     Set)
      with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                      or else raise Program_Error,
           Post => Length (Target) <= Length (Target)'Old + Length (Source)
;
37/5
{AI12-0112-1}    function Symmetric_Difference (Left, Right : Set) return Set
      with Post => Length (Symmetric_Difference'Result) <= Length (Left) + Length (Right) and then
                   not Tampering_With_Cursors_Prohibited (Symmetric_Difference'Result)
;
38/2
   function "xor" (Left, Right : Set) return Set renames
      Symmetric_Difference;
39/2
   function Overlap (Left, Right : Set) return Boolean;
40/2
   function Is_Subset (Subset : Set;
                       Of_Set : Set) return Boolean;
41/5
{AI12-0112-1}    function First (Container : Set) return Cursor
      with Nonblocking, Global => (nulluse null),
           Post => (if not Is_Empty (Container)
                    then Has_Element (Container, First'Result)
                    else First'Result = No_Element)
;
42/5
{AI12-0112-1}    function First_Element (Container : Set)
      return Element_Type
      with Pre => (if Is_Empty (Container) then raise Constraint_Error)
;
43/5
{AI12-0112-1}    function Last (Container : Set) return Cursor
      with Nonblocking, Global => (nulluse null),
           Post => (if not Is_Empty (Container)
                    then Has_Element (Container, Last'Result)
                    else Last'Result = No_Element)
;
44/5
{AI12-0112-1}    function Last_Element (Container : Set)
      return Element_Type
      with Pre => (if Is_Empty (Container) then raise Constraint_Error)
;
45/5
{AI12-0112-1}    function Next (Position : Cursor) return Cursor
      with Nonblocking, Global => (in alluse null),
           Post => (if Position = No_Element then Next'Result = No_Element
                    else True)
;
45.1/5
{AI12-0112-1}    function Next (Container : Set;
                  Position : Cursor) return Cursor
      with Nonblocking, Global => (nulluse 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));
46/5
{AI12-0112-1}    procedure Next (Position : in out Cursor)
      with Nonblocking, Global => (in alluse null)
;
46.1/5
{AI12-0112-1}    procedure Next (Container : in     Set;
                   Position  : in out Cursor)
      with Nonblocking, Global => (nulluse 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));
47/5
{AI12-0112-1}    function Previous (Position : Cursor) return Cursor
      with Nonblocking, Global => (in alluse null),
           Post => (if Position = No_Element then
                       Previous'Result = No_Element
                    else True)
;
47.1/5
{AI12-0112-1}    function Previous (Container : Set;
                      Position  : Cursor) return Cursor
      with Nonblocking, Global => (nulluse 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));
48/5
{AI12-0112-1}    procedure Previous (Position : in out Cursor)
      with Global => (in alluse null),
           Nonblocking => True
;
48.1/5
{AI12-0112-1}    procedure Previous (Container : in     Set;
                       Position  : in out Cursor)
      with Nonblocking, Global => (nulluse 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));
49/5
{AI12-0112-1}    function Find (Container : Set;
                  Item      : Element_Type) return Cursor
      with Post => (if Find'Result = No_Element then True
                    else Has_Element (Container, Find'Result))
;
50/2
   function Floor (Container : Set;
                   Item      : Element_Type) return Cursor
      with Post => (if Floor'Result = No_Element then True
                    else Has_Element (Container, Floor'Result))
;
51/2
   function Ceiling (Container : Set;
                     Item      : Element_Type) return Cursor
      with Post => (if Ceiling'Result = No_Element then True
                    else Has_Element (Container, Ceiling'Result))
;
52/2
   function Contains (Container : Set;
                      Item      : Element_Type) return Boolean;
53/3
This paragraph was deleted.{AI05-0212-1}
54/5
{AI12-0112-1}    function "<" (Left, Right : Cursor) return Boolean
      with Pre    => (Left /= No_Element and then Right /= No_Element)
                         or else raise Constraint_Error,
           Global => in all
;
55/5
{AI12-0112-1}    function ">" (Left, Right : Cursor) return Boolean
      with Pre    => (Left /= No_Element and then Right /= No_Element)
                         or else raise Constraint_Error,
           Global => in all
;
56/5
{AI12-0112-1}    function "<" (Left : Cursor; Right : Element_Type) return Boolean
      with Pre    => Left /= No_Element or else raise Constraint_Error,
           Global => in all
;
57/5
{AI12-0112-1}    function ">" (Left : Cursor; Right : Element_Type) return Boolean
      with Pre    => Left /= No_Element or else raise Constraint_Error,
           Global => in all
;
58/5
{AI12-0112-1}    function "<" (Left : Element_Type; Right : Cursor) return Boolean
      with Pre    => Right /= No_Element or else raise Constraint_Error,
           Global => in all
;
59/5
{AI12-0112-1}    function ">" (Left : Element_Type; Right : Cursor) return Boolean
      with Pre    => Right /= No_Element or else raise Constraint_Error,
           Global => in all
;
60/5
{AI12-0112-1}    procedure  Iterate
     (Container : in Set;
      Process   : not null access procedure (Position : in Cursor))
      with Allows_Exit
;
61/5
{AI12-0112-1}    procedure Reverse_Iterate
     (Container : in Set;
      Process   : not null access procedure (Position : in Cursor))
      with Allows_Exit
;
61.1/5
{AI05-0212-1} {AI12-0112-1} {AI12-0266-1}    function Iterate (Container : in Set)
      return Set_Iterator_Interfaces.Parallel_Reversible_Iterator Reversible_Iterator'Class
      with Post => Tampering_With_Cursors_Prohibited (Container)
;
61.2/5
{AI05-0262-1} {AI12-0112-1}    function Iterate (Container : in Set; Start : in Cursor)
      return Set_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)
;
62/5
{AI12-0112-1}    generic
      type Key_Type (<>) is private;
      with function Key (Element : Element_Type) return Key_Type;
      with function "<" (Left, Right : Key_Type)
         return Boolean is <>;
   package Generic_Keys
   with Nonblocking, Global => null
 is
63/2
       function Equivalent_Keys (Left, Right : Key_Type)
          return Boolean;
64/5
{AI12-0112-1}       function Key (Position : Cursor) return Key_Type
         with Pre  => Position /= No_Element or else raise Constraint_Error,
              Global => in all
;
64.1/5
{AI12-0112-1}       function Key (Container : Set;
                    Position : Cursor) return Key_Type
         with Pre  => (Position /= No_Element 
                         or else raise Constraint_Error) and then
                      (Has_Element (Container, Position)
                         or else raise Program_Error);
65/2
       function Element (Container : Set;
                         Key       : Key_Type)
          return Element_Type;
66/5
{AI12-0112-1}       procedure Replace (Container : in out Set;
                         Key       : in     Key_Type;
                         New_Item  : in     Element_Type)
         with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                           or else raise Program_Error,
              Post => Length (Container) = Length (Container)'Old
;
67/5
{AI12-0112-1}       procedure Exclude (Container : in out Set;
                         Key       : in     Key_Type)
         with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                           or else raise Program_Error,
              Post => (declare
                         Original_Length : constant Count_Type :=
                            Length (Container)'Old;
                       begin
                         Length (Container) in Original_Length - 1 | Original_Length)
;
68/5
{AI12-0112-1}       procedure Delete (Container : in out Set;
                        Key       : in     Key_Type)
         with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                           or else raise Program_Error,
              Post => Length (Container) = Length (Container)'Old - 1
;
69/5
{AI12-0112-1}       function Find (Container : Set;
                     Key       : Key_Type)
         return Cursor
         with Post => (if Find'Result = No_Element then True
                       else Has_Element (Container, Find'Result))
;
70/5
{AI12-0112-1}        function Floor (Container : Set;
                       Key       : Key_Type)
         return Cursor
         with Post => (if Floor'Result = No_Element then True
                       else Has_Element (Container, Floor'Result))
;
71/5
{AI12-0112-1}        function Ceiling (Container : Set;
                         Key       : Key_Type)
         return Cursor
         with Post => (if Ceiling'Result = No_Element then True
                       else Has_Element (Container, Ceiling'Result))
;
72/2
       function Contains (Container : Set;
                          Key       : Key_Type) return Boolean;
73/5
{AI12-0112-1}       procedure Update_Element_Preserving_Key
        (Container : in out Set;
         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)
;
73.1/5
{AI05-0212-1} {AI12-0112-1}       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)
;
73.2/5
{AI05-0212-1} {AI12-0112-1}       function Reference_Preserving_Key (Container : aliased in out Set;
                                         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)
;
73.3/5
{AI05-0212-1} {AI12-0112-1}       function Constant_Reference (Container : aliased in Set;
                                   Key       : in Key_Type)
         return Constant_Reference_Type
         with Pre  => Find (Container, Key) /= No_Element or else
                         raise Constraint_Error,
              Post => Tampering_With_Cursors_Prohibited (Container)
;
73.4/5
{AI05-0212-1} {AI12-0112-1}       function Reference_Preserving_Key (Container : aliased in out Set;
                                         Key       : in Key_Type)
         return Reference_Type
         with Pre  => Find (Container, Key) /= No_Element or else
                         raise Constraint_Error,
              Post => Tampering_With_Cursors_Prohibited (Container)
;
74/2
   end Generic_Keys;
74.1/5
{AI05-0111-1}    package Stable is
74.2/5
{AI05-0111-1} {AI12-0339-1}       type Set (Base : not null access Hashed_Sets.Set) is
         tagged limited private
         with Constant_Indexing => Constant_Reference,
              Default_Iterator  => Iterate,
              Iterator_Element  => Element_Type,
              Aggregate         => (Empty       => Empty,
                                    Add_Unnamed => Include),
              Stable_Properties => (Length),
              Global            => null,
              Default_Initial_Condition => Length (Set) = 0;
      pragma Preelaborable_Initialization(Set);
74.3/5
{AI05-0111-1}       type Cursor is private;
      pragma Preelaborable_Initialization(Cursor);
74.4/5
{AI05-0111-1}       Empty_Set : constant Set;
74.5/5
{AI05-0111-1}       No_Element : constant Cursor;
74.6/5
{AI05-0111-1}       function Has_Element (Position : Cursor) return Boolean
         with Nonblocking, Global => (in alluse null);
74.7/5
{AI05-0111-1}       package Set_Iterator_Interfaces is new
         Ada.Iterator_Interfaces (Cursor, Has_Element);
74.8/5
{AI05-0111-1}       procedure Assign (Target : in out Hashed_Sets.Set;
                        Source : in Set)
         with Post => Length (Source) = Length (Target);
74.9/5
{AI05-0111-1}       function Copy (Source : Hashed_Sets.Set) return Set
         with Post => Length (Copy'Result) = Length (Source);
74.10/5
{AI05-0111-1}       type Constant_Reference_Type
            (Element : not null access constant Element_Type) is private
         with Implicit_Dereference => Element,
              Nonblocking, Global => (nulluse null),
              Default_Initial_Condition => (raise Program_Error);
74.11/5
{AI05-0111-1}       -- Additional subprograms as described in the text
      -- are declared here.
74.12/5
{AI05-0111-1}    private
74.13/5
{AI05-0111-1}       ... -- not specified by the language
74.14/5
{AI05-0111-1}    end Stable;
75/2
private
76/2
   ... -- not specified by the language
77/2
end Ada.Containers.Ordered_Sets;
78/2
{AI95-00302-03} Two elements E1 and E2 are equivalent if both E1 < E2 and E2 < E1 return False, using the generic formal "<" operator for elements. Function Equivalent_Elements returns True if Left and Right are equivalent, and False otherwise.
79/3
{AI95-00302-03} {AI05-0044-1} The actual function for the generic formal function "<" on Element_Type values is expected to return the same value each time it is called with a particular pair of key values. It should define a strict weak ordering relationship (see A.18). If the actual for "<" behaves in some other manner, the behavior of this package is unspecified. Which subprograms of this package call "<" and how many times they call it, is unspecified.
79.1/3
  {AI05-0044-1} If the actual function for the generic formal function "=" returns True for any pair of nonequivalent elements, then the behavior of the container function "=" is unspecified.
80/2
{AI95-00302-03} If the value of an element stored in a set is changed other than by an operation in this package such that at least one of "<" or "=" give different results, the behavior of this package is unspecified.
80.a/2
Discussion: See A.18.6, “The Generic Package Containers.Ordered_Maps” for a suggested implementation, and for justification of the restrictions regarding "<" and "=". Note that sets only need to store elements, not key/element pairs. 
81/3
{AI95-00302-03} {AI05-0262-1} The first element of a nonempty set is the one which is less than all the other elements in the set. The last element of a nonempty set is the one which is greater than all the other elements in the set. The successor of an element is the smallest element that is larger than the given element. The predecessor of an element is the largest element that is smaller than the given element. All comparisons are done using the generic formal "<" operator for elements.
81.1/5
{AI12-0112-1} function Copy (Source : Set) return Set
   with Post => Length (Copy'Result) = Length (Source) and then
                not Tampering_With_Cursors_Prohibited (Copy'Result)
;
81.2/3
{AI05-0001-1} Returns a set whose elements are initialized from the corresponding elements of Source.
82/5
{AI12-0112-1} procedure Delete_First (Container : in out Set)
   with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error,
        Post => (declare
                   Original_Length : constant Count_Type :=
                      Length (Container)'Old;
                 begin
                   (if Original_Length = 0 then Length (Container) = 0
                    else Length (Container) = Original_Length - 1))
;
83/3
{AI95-00302-03} {AI05-0264-1} If Container is empty, Delete_First has no effect. Otherwise, the element designated by First (Container) is removed from Container. Delete_First tampers with the cursors of Container.
84/5
{AI12-0112-1} procedure Delete_Last (Container : in out Set)
   with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error,
        Post => (declare
                   Original_Length : constant Count_Type :=
                      Length (Container)'Old;
                 begin
                   (if Original_Length = 0 then Length (Container) = 0
                    else Length (Container) = Original_Length - 1))
;
85/3
{AI95-00302-03} {AI05-0264-1} If Container is empty, Delete_Last has no effect. Otherwise, the element designated by Last (Container) is removed from Container. Delete_Last tampers with the cursors of Container.
86/5
{AI12-0112-1} function First_Element (Container : Set)
   return Element_Type
   with Pre => (if Is_Empty (Container) then raise Constraint_Error)
;
87/2
{AI95-00302-03} Equivalent to Element (First (Container)).
88/5
{AI12-0112-1} function Last (Container : Set) return Cursor
   with Nonblocking, Global => (nulluse null),
        Post => (if not Is_Empty (Container)
                 then Has_Element (Container, Last'Result)
                 else Last'Result = No_Element)
;
89/2
{AI95-00302-03} Returns a cursor that designates the last element in Container. If Container is empty, returns No_Element.
90/5
{AI12-0112-1} function Last_Element (Container : Set)
   return Element_Type
   with Pre => (if Is_Empty (Container) then raise Constraint_Error)
;
91/2
{AI95-00302-03} Equivalent to Element (Last (Container)).
92/5
{AI12-0112-1} function Previous (Position : Cursor) return Cursor
   with Nonblocking, Global => (in alluse null),
        Post => (if Position = No_Element then
                    Previous'Result = No_Element
                 else True)
;
93/3
{AI95-00302-03} {AI05-0262-1} If Position equals No_Element, then Previous returns No_Element. Otherwise, Previous returns a cursor designating the predecessor element of the one designated by Position. If Position designates the first element, then Previous returns No_Element.
93.1/5
function Previous (Container : Set;
                   Position : Cursor) return Cursor
   with Nonblocking, Global => (nulluse 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));
93.2/5
{AI12-0112-1} Returns a cursor designating the predecessor of the node designated by Position in Container, if any.
94/5
{AI12-0112-1} procedure Previous (Position : in out Cursor)
   with Nonblocking, Global => (in alluse null)
;
95/2
{AI95-00302-03} Equivalent to Position := Previous (Position).
95.1/5
procedure Previous (Container : in     Set;
                    Position  : in out Cursor)
   with Nonblocking, Global => (nulluse 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));
95.2/5
{AI12-0112-1} Equivalent to Position := Previous (Container, Position).
96/5
{AI12-0112-1} function Floor (Container : Set;
                Item      : Element_Type) return Cursor
   with Post => (if Floor'Result = No_Element then True
                 else Has_Element (Container, Floor'Result))
;
97/3
{AI95-00302-03} {AI05-0264-1} Floor searches for the last element which is not greater than Item. If such an element is found, a cursor that designates it is returned. Otherwise, No_Element is returned.
98/5
{AI12-0112-1} function Ceiling (Container : Set;
                  Item      : Element_Type) return Cursor
   with Post => (if Ceiling'Result = No_Element then True
                 else Has_Element (Container, Ceiling'Result))
;
99/3
{AI95-00302-03} {AI05-0264-1} Ceiling searches for the first element which is not less than Item. If such an element is found, a cursor that designates it is returned. Otherwise, No_Element is returned.
100/5
{AI12-0112-1} function "<" (Left, Right : Cursor) return Boolean
   with Pre    => (Left /= No_Element and then Right /= No_Element)
                      or else raise Constraint_Error,
        Global => in all
;
101/2
{AI95-00302-03} Equivalent to Element (Left) < Element (Right).
102/5
{AI12-0112-1} function ">" (Left, Right : Cursor) return Boolean
   with Pre    => (Left /= No_Element and then Right /= No_Element)
                      or else raise Constraint_Error,
        Global => in all
;
103/2
{AI95-00302-03} Equivalent to Element (Right) < Element (Left).
104/5
{AI12-0112-1} function "<" (Left : Cursor; Right : Element_Type) return Boolean
   with Pre    => Left /= No_Element or else raise Constraint_Error,
        Global => in all
;
105/2
{AI95-00302-03} Equivalent to Element (Left) < Right.
106/5
{AI12-0112-1} function ">" (Left : Cursor; Right : Element_Type) return Boolean
   with Pre    => Left /= No_Element or else raise Constraint_Error,
           Global => in all
;
107/2
{AI95-00302-03} Equivalent to Right < Element (Left).
108/5
{AI12-0112-1} function "<" (Left : Element_Type; Right : Cursor) return Boolean
   with Pre    => Right /= No_Element or else raise Constraint_Error,
           Global => in all
;
109/2
{AI95-00302-03} Equivalent to Left < Element (Right).
110/5
{AI12-0112-1} function ">" (Left : Element_Type; Right : Cursor) return Boolean
   with Pre    => Right /= No_Element or else raise Constraint_Error,
           Global => in all
;
111/2
{AI95-00302-03} Equivalent to Element (Right) < Left.
112/5
{AI12-0112-1} procedure Reverse_Iterate
  (Container : in Set;
   Process   : not null access procedure (Position : in Cursor))
   with Allows_Exit
;
113/3
{AI95-00302-03} {AI05-0212-1} Iterates over the elements in Container as per procedure Iterate, with the difference that the elements are traversed in predecessor order, starting with the last element.
113.1/5
{AI12-0112-1} {AI12-0266-1} function Iterate (Container : in Set)
   return Set_Iterator_Interfaces.Parallel_Reversible_Iterator Reversible_Iterator'Class
   with Post => Tampering_With_Cursors_Prohibited (Container)
;
113.2/5
{AI05-0212-1} {AI05-0265-1} {AI05-0269-1} {AI12-0266-1} Iterate returns an a reversible iterator object (see 5.5.1) that will generate a value for a loop parameter (see 5.5.2) designating each element in Container, starting with the first element and moving the cursor according to the successor relation when used as a forward iterator, and starting with the last element and moving the cursor according to the predecessor relation 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.
113.3/5
function Iterate (Container : in Set; Start : in Cursor)
   return Set_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)
;
113.4/5
{AI05-0262-1} {AI05-0265-1} {AI05-0269-1} {AI12-0112-1} If Start is not No_Element and does not designate an item in Container, then Program_Error is propagated. If Start is No_Element, then Constraint_Error is propagated. Otherwise, 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 element in Container, starting with the element designated by Start and moving the cursor according to the successor relation when used as a forward iterator, or moving the cursor according to the predecessor relation 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.
113.a/3
Discussion: Exits are allowed from the loops created using the iterator objects. In particular, to stop the iteration at a particular cursor, just add
113.b/3
exit when Cur = Stop;
113.c/3
in the body of the loop (assuming that Cur is the loop parameter and Stop is the cursor that you want to stop at). 
114/2
 {AI95-00302-03} For any two elements E1 and E2, the boolean values (E1 < E2) and (Key(E1) < Key(E2)) are expected to be equal. If the actuals for Key or Generic_Keys."<" behave in some other manner, the behavior of this package is unspecified. Which subprograms of this package call Key and Generic_Keys."<", and how many times the functions are called, is unspecified.
115/2
 {AI95-00302-03} In addition to the semantics described in A.18.7, the subprograms in package Generic_Keys named Floor and Ceiling, are equivalent to the corresponding subprograms in the parent package, with the difference that the Key subprogram parameter is compared to elements in the container using the Key and "<" generic formal functions. The function named Equivalent_Keys in package Generic_Keys returns True if both Left < Right and Right < Left return False using the generic formal "<" operator, and returns True otherwise.

Implementation Advice

116/2
 {AI95-00302-03} If N is the length of a set, then the worst-case time complexity of the Insert, Include, Replace, Delete, Exclude and Find operations that take an element parameter should be O((log N)**2) or better. The worst-case time complexity of the subprograms that take a cursor parameter should be O(1). 
116.a/2
Implementation Advice: The worst-case time complexity of the Insert, Include, Replace, Delete, Exclude and Find operations of Containers.Ordered_Sets that take an element parameter should be O((log N)**2). The worst-case time complexity of the subprograms of Containers.Ordered_Sets that take a cursor parameter should be O(1).
116.b/2
Implementation Note: {AI95-00302-03} See A.18.6, “The Generic Package Containers.Ordered_Maps” for implementation notes regarding some of the operations of this package. 

Extensions to Ada 95

116.c/2
{AI95-00302-03} The generic package Containers.Ordered_Sets is new.

Incompatibilities With Ada 2005

116.d/3
{AI05-0001-1} Subprograms Assign and Copy are added to Containers.Ordered_Sets. If an instance of Containers.Ordered_Sets is referenced in a use_clause, and an entity E with the same defining_identifier as a new entity in Containers.Ordered_Sets is defined in a package that is also referenced in a use_clause, the entity E may no longer be use-visible, resulting in errors. This should be rare and is easily fixed if it does occur. 

Extensions to Ada 2005

116.e/3
{AI05-0212-1} Added iterator and indexing support to make ordered set containers more convenient to use. 

Wording Changes from Ada 2005

116.f/3
{AI05-0044-1} Correction: Added wording to require the formal function be such that equal elements are also equivalent.
116.g/3
{AI05-0044-1} Correction: Redefined "<" actuals to require a strict weak ordering; the old definition allowed indeterminant comparisons that would not have worked in a container.
116.h/3
{AI05-0084-1} Correction: Added a pragma Remote_Types so that containers can be used in distributed programs. 

Incompatibilities With Ada 2012

116.i/5
{AI12-0111-1} {AI12-0112-1} {AI12-0339-1} A number of new subprograms, types, and even a nested package were added to Containers.Ordered_Sets to better support contracts and stable views. If an instance of Containers.Ordered_Sets is referenced in a use_clause, and an entity E with the same defining_identifier as a new entity in Containers.Ordered_Sets is defined in a package that is also referenced in a use_clause, the entity E may no longer be use-visible, resulting in errors. This should be rare and is easily fixed if it does occur. 

Extensions to Ada 2012

116.j/5
{AI12-0212-1} Sets now support positional container aggregates, so aggregate syntax can be used to create Sets.
116.k/5
{AI12-0266-1} The iterator for the entire container now can return a parallel iterator which can be used to process the container in parallel.

Wording Changes from Ada 2012

116.l/5
{AI12-0112-1} Added contracts to this container. This includes describing some of the semantics with pre- and postconditions, rather than English text. Note that the preconditions can be Suppressed (see 11.5). 

Contents   Index   References   Search   Previous   Next 
Ada-Europe Ada 2005 and 2012 Editions sponsored in part by Ada-Europe