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

A.18.6 The Generic Package Containers.Ordered_Maps

Static Semantics

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

   pragma Preelaborate(Ordered_Maps);
   pragma Remote_Types(Ordered_Maps);
3/5
{AI12-0112-1}    function Equivalent_Keys (Left, Right : Key_Type) return Boolean
      is (not ((Left < Right) or (Right < Left)));
4/5
{AI05-0212-1} {AI12-0111-1} {AI12-0112-1} {AI12-0212-1} {AI12-0339-1}    type Map is tagged private
      with Constant_Indexing => Constant_Reference,
           Variable_Indexing => Reference,
           Default_Iterator  => Iterate,
           Iterator_Element  => Element_Type,
           Iterator_View     => Stable.Map,
           Aggregate         => (Empty     => Empty,
                                 Add_Named => Insert),
           Stable_Properties => (Length,
                                 Tampering_With_Cursors_Prohibited,
                                 Tampering_With_Elements_Prohibited),
           Default_Initial_Condition =>
              Length (Map) = 0 and then
              (not Tampering_With_Cursors_Prohibited (Map)) and then
              (not Tampering_With_Elements_Prohibited (Map))
;
   pragma Preelaborable_Initialization(Map);
5/2
   type Cursor is private;
   pragma Preelaborable_Initialization(Cursor);
6/2
   Empty_Map : constant Map;
7/2
   No_Element : constant Cursor;
7.1/5
{AI12-0112-1}    function Equal_Element (Left, Right : Element_Type)
      return Boolean renames "=";
7.2/5
{AI12-0112-1}    function Less_Key (Left, Right : Key_Type)
      return Boolean renames "<";
7.3/5
{AI05-0212-1} {AI12-0112-1}    function Has_Element (Position : Cursor) return Boolean
      with Nonblocking, Global => in access Map
;
7.4/5
{AI12-0112-1}    function Has_Element (Container : Map; Position : Cursor)
      return Boolean
      with Nonblocking, Global => null;
7.5/5
{AI05-0212-1}    package Map_Iterator_Interfaces is new
       Ada.Iterator_Interfaces (Cursor, Has_Element);
8/2
   function "=" (Left, Right : Map) return Boolean;
8.1/5
{AI12-0112-1}    function Tampering_With_Cursors_Prohibited
      (Container : Map) return Boolean
      with Nonblocking, Global => null;
8.2/5
{AI12-0112-1}    function Tampering_With_Elements_Prohibited
      (Container : Map) return Boolean
      with Nonblocking, Global => null;
8.3/5
{AI12-0339-1}    function Empty return Map
      is (Empty_Map)
      with Post =>
         not Tampering_With_Elements_Prohibited (Empty'Result) and then
         not Tampering_With_Cursors_Prohibited (Empty'Result) and then
         Length (Empty'Result) = 0;
9/5
{AI12-0112-1}    function Length (Container : Map) return Count_Type
      with Nonblocking, Global => null
;
10/5
{AI12-0112-1}    function Is_Empty (Container : Map) return Boolean
      with Nonblocking, Global => null,
           Post => Is_Empty'Result = (Length (Container) = 0)
;
11/5
{AI12-0112-1}    procedure Clear (Container : in out Map)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                       then raise Program_Error),
           Post => Length (Container) = 0
;
12/5
{AI12-0112-1}    function Key (Position : Cursor) return Key_Type
      with Pre  => (if Position = No_Element then raise Constraint_Error),
           Nonblocking => Key_Type'Nonblocking,
           Global => in access Map & Key_Type'Global
;
12.1/5
{AI12-0112-1}    function Key (Container : Map;
                 Position : Cursor) return Key_Type
      with Pre  => (if Position = No_Element then raise Constraint_Error
                   elsif not Has_Element (Container, Position)
                      then raise Program_Error),
           Nonblocking => Key_Type'Nonblocking,
           Global => Key_Type'Global;
13/5
{AI12-0112-1}    function Element (Position : Cursor) return Element_Type
      with Pre  => (if Position = No_Element then raise Constraint_Error),
           Nonblocking => Element_Type'Nonblocking,
           Global => in access Map & Element_Type'Global
;
13.1/5
{AI12-0112-1}    function Element (Container : Map;
                     Position  : Cursor) return Element_Type
      with Pre => (if Position = No_Element then raise Constraint_Error
                   elsif not Has_Element (Container, Position)
                      then raise Program_Error),
           Nonblocking => Element_Type'Nonblocking,
           Global => Element_Type'Global;
14/5
{AI12-0112-1}    procedure Replace_Element (Container : in out Map;
                              Position  : in     Cursor;
                              New_item  : in     Element_Type)
      with Pre  => (if Tampering_With_Elements_Prohibited (Container)
                    then raise Program_Error) and then
                   (if Position = No_Element then raise Constraint_Error
                    elsif not Has_Element (Container, Position)
                       then raise Program_Error)
;
15/5
{AI12-0112-1}    procedure Query_Element
     (Position : in Cursor;
      Process  : not null access procedure (Key     : in Key_Type;
                                            Element : in Element_Type))
      with Pre  => (if Position = No_Element then raise Constraint_Error),
           Global => in access Map & Element_Type'Global
;
15.1/5
{AI12-0112-1}    procedure Query_Element
     (Container : in Map;
      Position  : in Cursor;
      Process   : not null access procedure (Key     : in Key_Type;
                                             Element : in Element_Type))
      with Pre  => (if Position = No_Element then raise Constraint_Error
                    elsif not Has_Element (Container, Position)
                    then raise Program_Error),
           Global => Element_Type'Global;
16/5
{AI12-0112-1}    procedure Update_Element
     (Container : in out Map;
      Position  : in     Cursor;
      Process   : not null access procedure
                      (Key     : in     Key_Type;
                       Element : in out Element_Type))
      with Pre  => (if Position = No_Element then raise Constraint_Error
                    elsif not Has_Element (Container, Position)
                       then raise Program_Error)
;
16.1/5
{AI05-0212-1} {AI12-0112-1}    type Constant_Reference_Type
         (Element : not null access constant Element_Type) is private
      with Implicit_Dereference => Element,
           Global => synchronized in out access Map,
           Nonblocking => True,
           Default_Initial_Condition => (raise Program_Error)
;
16.2/5
{AI05-0212-1} {AI12-0112-1}    type Reference_Type (Element : not null access Element_Type) is private
      with Implicit_Dereference => Element,
           Global => synchronized in out access Map,
           Nonblocking => True,
           Default_Initial_Condition => (raise Program_Error)
;
16.3/5
{AI05-0212-1} {AI12-0112-1}    function Constant_Reference (Container : aliased in Map;
                                Position  : in Cursor)
      return Constant_Reference_Type
      with Pre  => (if Position = No_Element then raise Constraint_Error
                    elsif not Has_Element (Container, Position)
                       then raise Program_Error),
           Post => Tampering_With_Cursors_Prohibited (Container),
           Nonblocking, Global => null
;
16.4/5
{AI05-0212-1} {AI12-0112-1}    function Reference (Container : aliased in out Map;
                       Position  : in Cursor)
      return Reference_Type
      with Pre  => (if Position = No_Element then raise Constraint_Error
                    elsif not Has_Element (Container, Position)
                       then raise Program_Error),
           Post => Tampering_With_Cursors_Prohibited (Container),
           Nonblocking, Global => null
;
16.5/5
{AI05-0212-1} {AI12-0112-1}    function Constant_Reference (Container : aliased in Map;
                                Key       : in Key_Type)
      return Constant_Reference_Type
      with Pre  => (if Find (Container, Key) = No_Element
                    then raise Constraint_Error),
           Post => Tampering_With_Cursors_Prohibited (Container),
           Nonblocking, Global => null
;
16.6/5
{AI05-0212-1} {AI12-0112-1}    function Reference (Container : aliased in out Map;
                       Key       : in Key_Type)
      return Reference_Type
      with Pre  => (if Find (Container, Key) = No_Element
                    then raise Constraint_Error),
           Post => Tampering_With_Cursors_Prohibited (Container),
           Nonblocking, Global => null
;
16.7/5
{AI05-0001-1} {AI12-0112-1}    procedure Assign (Target : in out Map; Source : in Map)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Target)
                    then raise Program_Error),
           Post => Length (Source) = Length (Target) and then
                   Capacity (Target) >= Length (Source)
;
16.8/5
{AI05-0001-1} {AI12-0112-1}    function Copy (Source : Map)
      return Map
      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)
;
17/5
{AI12-0112-1}    procedure Move (Target : in out Map;
                   Source : in out Map)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Target)
                    then raise Program_Error) and then
                   (if Tampering_With_Cursors_Prohibited (Source)
                    then 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 Map;
                     Key       : in     Key_Type;
                     New_Item  : in     Element_Type;
                     Position  :    out Cursor;
                     Inserted  :    out Boolean)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                    then raise Program_Error) and then
                   (if Length (Container) > Count_Type'Last - 1
                    then 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 Map;
                     Key       : in     Key_Type;
                     Position  :    out Cursor;
                     Inserted  :    out Boolean)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                    then raise Program_Error) and then
                   (if Length (Container) > Count_Type'Last - 1
                    then 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))
;
20/5
{AI12-0112-1}    procedure Insert (Container : in out Map;
                     Key       : in     Key_Type;
                     New_Item  : in     Element_Type)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                    then raise Program_Error) and then
                   (if Length (Container) > Count_Type'Last - 1
                    then raise Constraint_Error),
           Post => Length (Container) = Length (Container)'Old + 1
;
21/5
{AI12-0112-1}    procedure Include (Container : in out Map;
                      Key       : in     Key_Type;
                      New_Item  : in     Element_Type)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                    then raise Program_Error) and then
                   (if Length (Container) > Count_Type'Last - 1
                    then raise Constraint_Error),
           Post => (declare
                      Original_Length : constant Count_Type :=
                         Length (Container)'Old;
                    begin
                      Length (Container)
                         in Original_Length | Original_Length + 1)
;
22/5
{AI12-0112-1}    procedure Replace (Container : in out Map;
                      Key       : in     Key_Type;
                      New_Item  : in     Element_Type)
      with Pre  => (if Tampering_With_Elements_Prohibited (Container)
                    then raise Program_Error),
           Post => Length (Container) = Length (Container)'Old
;
23/5
{AI12-0112-1}    procedure Exclude (Container : in out Map;
                      Key       : in     Key_Type)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                    then raise Program_Error),
           Post => (declare
                      Original_Length : constant Count_Type :=
                         Length (Container)'Old;
                    begin
                      Length (Container)
                         in Original_Length - 1 | Original_Length)
;
24/5
{AI12-0112-1}    procedure Delete (Container : in out Map;
                     Key       : in     Key_Type)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                    then raise Program_Error),
           Post => Length (Container) = Length (Container)'Old - 1
;
25/5
{AI12-0112-1}    procedure Delete (Container : in out Map;
                     Position  : in out Cursor)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                    then raise Program_Error) and then
                   (if Position /= No_Element and then
                       (not Has_Element (Container, Position))
                    then raise Program_Error),
           Post => Length (Container) = Length (Container)'Old - 1 and then
                   Position = No_Element
;
26/5
{AI12-0112-1}    procedure Delete_First (Container : in out Map)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                    then 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 Delete_Last (Container : in out Map)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                    then 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))
;
28/5
{AI12-0112-1}    function First (Container : Map) return Cursor
      with Nonblocking, Global => null,
           Post => (if not Is_Empty (Container)
                    then Has_Element (Container, First'Result)
                    else First'Result = No_Element)
;
29/5
{AI12-0112-1}    function First_Element (Container : Map)
      return Element_Type
      with Pre => (if Is_Empty (Container) then raise Constraint_Error)
;
30/5
{AI12-0112-1}    function First_Key (Container : Map)
      return Key_Type
      with Pre => (if Is_Empty (Container) then raise Constraint_Error)
;
31/5
{AI12-0112-1}    function Last (Container : Map) return Cursor
      with Nonblocking, Global => null,
           Post => (if not Is_Empty (Container)
                    then Has_Element (Container, Last'Result)
                    else Last'Result = No_Element)
;
32/5
{AI12-0112-1}    function Last_Element (Container : Map)
      return Element_Type
      with Pre => (if Is_Empty (Container) then raise Constraint_Error)
;
33/5
{AI12-0112-1}    function Last_Key (Container : Map)
      return Key_Type
      with Pre => (if Is_Empty (Container) then raise Constraint_Error)
;
34/5
{AI12-0112-1}    function Next (Position : Cursor) return Cursor
      with Global => in access Map,
           Nonblocking => True,
           Post => (if Position = No_Element then Next'Result = No_Element
                    else True)
;
34.1/5
{AI12-0112-1}    function Next (Container : Map;
                  Position : Cursor) return Cursor
      with Nonblocking, Global => null,
           Pre  => (if Position /= No_Element and then
                       (not Has_Element (Container, Position))
                    then 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));
35/5
{AI12-0112-1}    procedure Next (Position : in out Cursor)
      with Global => in access Map,
           Nonblocking => True
;
35.1/5
{AI12-0112-1}    procedure Next (Container : in     Map;
                   Position  : in out Cursor)
      with Nonblocking, Global => null,
           Pre  => (if Position /= No_Element and then
                       (not Has_Element (Container, Position))
                    then raise Program_Error),
           Post => (if Position /= No_Element
                    then Has_Element (Container, Position));
36/5
{AI12-0112-1}    function Previous (Position : Cursor) return Cursor
      with Global => in access Map,
           Nonblocking => True,
           Post => (if Position = No_Element then
                       Previous'Result = No_Element
                    else True)
;
36.1/5
{AI12-0112-1}    function Previous (Container : Map;
                      Position  : Cursor) return Cursor
      with Nonblocking, Global => null,
           Pre  => (if Position /= No_Element and then
                       (not Has_Element (Container, Position))
                    then 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));
37/5
{AI12-0112-1}    procedure Previous (Position : in out Cursor)
      with Global => in access Map,
           Nonblocking => True
;
37.1/5
{AI12-0112-1}    procedure Previous (Container : in     Map;
                       Position  : in out Cursor)
      with Nonblocking, Global => null,
           Pre  => (if Position /= No_Element and then
                       (not Has_Element (Container, Position))
                    then raise Program_Error),
           Post => (if Position /= No_Element
                    then Has_Element (Container, Position));
38/5
{AI12-0112-1}    function Find (Container : Map;
                  Key       : Key_Type) return Cursor
      with Post => (if Find'Result = No_Element then True
                    else Has_Element (Container, Find'Result))
;
39/2
   function Element (Container : Map;
                     Key       : Key_Type) return Element_Type;
40/5
{AI12-0112-1}    function Floor (Container : Map;
                   Key       : Key_Type) return Cursor
      with Post => (if Floor'Result = No_Element then True
                    else Has_Element (Container, Floor'Result))
;
41/5
{AI12-0112-1}    function Ceiling (Container : Map;
                     Key       : Key_Type) return Cursor
      with Post => (if Ceiling'Result = No_Element then True
                    else Has_Element (Container, Ceiling'Result))
;
42/2
   function Contains (Container : Map;
                      Key       : Key_Type) return Boolean;
43/3
This paragraph was deleted.{AI05-0212-1}
44/5
{AI12-0112-1}    function "<" (Left, Right : Cursor) return Boolean
      with Pre    => (if Left = No_Element or else Right = No_Element
                      then raise Constraint_Error),
           Nonblocking => Key_Type'Nonblocking and Less_Key'Nonblocking,
           Global => in access Map & Key_Type'Global & Less_Key'Global
;
45/5
{AI12-0112-1}    function ">" (Left, Right : Cursor) return Boolean
      with Pre    => (if Left = No_Element or else Right = No_Element
                      then raise Constraint_Error),
           Nonblocking => Key_Type'Nonblocking and Less_Key'Nonblocking,
           Global => in access Map & Key_Type'Global & Less_Key'Global
;
46/5
{AI12-0112-1}    function "<" (Left : Cursor; Right : Key_Type) return Boolean
      with Pre    => (if Left = No_Element then raise Constraint_Error),
           Nonblocking => Key_Type'Nonblocking and Less_Key'Nonblocking,
           Global => in access Map & Key_Type'Global & Less_Key'Global
;
47/5
{AI12-0112-1}    function ">" (Left : Cursor; Right : Key_Type) return Boolean
      with Pre    => (if Left = No_Element then raise Constraint_Error),
           Nonblocking => Key_Type'Nonblocking and Less_Key'Nonblocking,
           Global => in access Map & Key_Type'Global & Less_Key'Global
;
48/5
{AI12-0112-1}    function "<" (Left : Key_Type; Right : Cursor) return Boolean
      with Pre    => (if Right = No_Element then raise Constraint_Error),
           Nonblocking => Key_Type'Nonblocking and Less_Key'Nonblocking,
           Global => in access Map & Key_Type'Global & Less_Key'Global
;
49/5
{AI12-0112-1}    function ">" (Left : Key_Type; Right : Cursor) return Boolean
      with Pre    => (if Right = No_Element then raise Constraint_Error),
           Nonblocking => Key_Type'Nonblocking and Less_Key'Nonblocking,
           Global => in access Map & Key_Type'Global & Less_Key'Global
;
50/5
{AI12-0112-1}    procedure  Iterate
     (Container : in Map;
      Process   : not null access procedure (Position : in Cursor))
      with Allows_Exit
;
51/5
{AI12-0112-1}    procedure Reverse_Iterate
     (Container : in Map;
      Process   : not null access procedure (Position : in Cursor))
      with Allows_Exit
;
51.1/5
{AI05-0212-1} {AI12-0112-1} {AI12-0266-1}    function Iterate (Container : in Map)
      return Map_Iterator_Interfaces.Parallel_Reversible_Iterator Reversible_Iterator'Class
      with Post => Tampering_With_Cursors_Prohibited (Container)
;
51.2/5
{AI05-0262-1} {AI12-0112-1}    function Iterate (Container : in Map; Start : in Cursor)
      return Map_Iterator_Interfaces.Reversible_Iterator'Class
      with Pre  => (if Start = No_Element
                          then raise Constraint_Error) and then
                      (if not Has_Element (Container, Start)
                       then raise Program_Error),
           Post => Tampering_With_Cursors_Prohibited (Container)
;
51.3/5
{AI05-0111-1}    package Stable is
51.4/5
{AI05-0111-1} {AI05-0339-1}       type Map (Base : not null access Ordered_Maps.Map) is
         tagged limited private
         with Constant_Indexing => Constant_Reference,
              Variable_Indexing => Reference,
              Default_Iterator  => Iterate,
              Iterator_Element  => Element_Type,
              Aggregate         => (Empty      => Empty,
                                    Add_Named  => Insert),
              Stable_Properties => (Length),
              Global => (in Map.Base.allsynchronized out Map.Base.all),
              Default_Initial_Condition => Length (Map) = 0;
      pragma Preelaborable_Initialization(Map);
51.5/5
{AI05-0111-1}       type Cursor is private;
      pragma Preelaborable_Initialization(Cursor);
51.6/5
{AI05-0111-1}       Empty_Map : constant Map;
51.7/5
{AI05-0111-1}       No_Element : constant Cursor;
51.8/5
{AI05-0111-1}       function Has_Element (Position : Cursor) return Boolean
         with Nonblocking, Global => in access Map;
51.9/5
{AI05-0111-1}       package Map_Iterator_Interfaces is new
         Ada.Iterator_Interfaces (Cursor, Has_Element);
51.10/5
{AI05-0111-1}       procedure Assign (Target : in out Ordered_Maps.Map;
                        Source : in Map)
         with Post => Length (Source) = Length (Target);
51.11/5
{AI05-0111-1}       function Copy (Source : Ordered_Maps.Map) return Map
         with Post => Length (Copy'Result) = Length (Source);
51.12/5
{AI05-0111-1}       type Constant_Reference_Type
            (Element : not null access constant Element_Type) is private
         with Implicit_Dereference => Element,
              Global => null,
              Nonblocking => null,
              Default_Initial_Condition => (raise Program_Error);
51.13/5
{AI05-0111-1}       type Reference_Type
            (Element : not null access Element_Type) is private
         with Implicit_Dereference => Element,
              Global => null,
              Nonblocking => null,
              Default_Initial_Condition => (raise Program_Error);
51.14/5
{AI05-0111-1}       -- Additional subprograms as described in the text
      -- are declared here.
51.15/5
{AI05-0111-1}    private
51.16/5
{AI05-0111-1}       ... -- not specified by the language
51.17/5
{AI05-0111-1}    end Stable;
52/2
private
53/2
   ... -- not specified by the language
54/2
end Ada.Containers.Ordered_Maps;
55/2
{AI95-00302-03} Two keys K1 and K2 are equivalent if both K1 < K2 and K2 < K1 return False, using the generic formal "<" operator for keys. Function Equivalent_Keys returns True if Left and Right are equivalent, and False otherwise.
56/3
{AI95-00302-03} {AI05-0044-1} The actual function for the generic formal function "<" on Key_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.
56.a/2
Implementation Note: The implementation is not required to protect against "<" raising an exception, or returning random results, or any other “bad” behavior. It's not practical to do so, and a broken "<" function makes the container unusable.
56.b/2
The implementation can call "<" whenever it is needed; we don't want to specify how often that happens. The result must remain the same (this is a logically pure function), or the behavior is unspecified. 
57/2
{AI95-00302-03} If the value of a key stored in a map 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.
57.a/2
Implementation Note: The implementation is not required to protect against changes to key values other than via the operations declared in the Ordered_Maps package.
57.b/2
To see how this could happen, imagine an instance of Ordered_Maps package where the key type is an access-to-variable type and "<" returns a value derived from comparing the components of the designated objects. Then, any operation that has a key value (even if the key value is constant) could modify those components and change the result of "<":
57.c/2
Key (Map).Some_Component := New_Value;
57.d/2
This is really a design error on the part of the user of the map; it shouldn't be possible to modify keys stored in a map such that "<" changes. But we can't prevent this error anymore than we can prevent someone passing as "<" a routine that produces random answers. 
58/3
{AI95-00302-03} {AI05-0262-1} The first node of a nonempty map is the one whose key is less than the key of all the other nodes in the map. The last node of a nonempty map is the one whose key is greater than the key of all the other elements in the map. The successor of a node is the node with the smallest key that is larger than the key of the given node. The predecessor of a node is the node with the largest key that is smaller than the key of the given node. All comparisons are done using the generic formal "<" operator for keys.
58.1/5
{AI12-0112-1} function Copy (Source : Map)
   return Map
   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)
;
58.2/3
{AI05-0001-1} Returns a map whose keys and elements are initialized from the corresponding keys and elements of Source.
59/5
{AI12-0112-1} procedure Delete_First (Container : in out Map)
   with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                 then 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))
;
60/3
{AI95-00302-03} {AI05-0264-1} If Container is empty, Delete_First has no effect. Otherwise, the node designated by First (Container) is removed from Container. Delete_First tampers with the cursors of Container.
61/5
{AI12-0112-1} procedure Delete_Last (Container : in out Map)
   with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                 then 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))
;
62/3
{AI95-00302-03} {AI05-0264-1} If Container is empty, Delete_Last has no effect. Otherwise, the node designated by Last (Container) is removed from Container. Delete_Last tampers with the cursors of Container.
63/5
{AI12-0112-1} function First_Element (Container : Map)
   return Element_Type
   with Pre => (if Is_Empty (Container) then raise Constraint_Error)
;
64/2
{AI95-00302-03} Equivalent to Element (First (Container)).
65/5
{AI12-0112-1} function First_Key (Container : Map)
   return Key_Type
   with Pre => (if Is_Empty (Container) then raise Constraint_Error)
;
66/2
{AI95-00302-03} Equivalent to Key (First (Container)).
67/5
{AI12-0112-1} function Last (Container : Map) return Cursor
   with Nonblocking, Global => null,
        Post => (if not Is_Empty (Container)
                 then Has_Element (Container, Last'Result)
                 else Last'Result = No_Element)
;
68/2
{AI95-00302-03} Returns a cursor that designates the last node in Container. If Container is empty, returns No_Element.
69/5
{AI12-0112-1} function Last_Element (Container : Map)
   return Element_Type
   with Pre => (if Is_Empty (Container) then raise Constraint_Error)
;
70/2
{AI95-00302-03} Equivalent to Element (Last (Container)).
71/5
{AI12-0112-1} function Last_Key (Container : Map)
   return Key_Type
   with Pre => (if Is_Empty (Container) then raise Constraint_Error)
;
72/2
{AI95-00302-03} Equivalent to Key (Last (Container)).
73/5
{AI12-0112-1} function Previous (Position : Cursor) return Cursor
   with Global => in access Map,
        Nonblocking => True,
        Post => (if Position = No_Element then
                    Previous'Result = No_Element
                 else True)
;
74/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 node of the one designated by Position. If Position designates the first element, then Previous returns No_Element.
74.1/5
function Previous (Container : Map;
                   Position : Cursor) return Cursor
   with Nonblocking, Global => null,
        Pre  => (if Position /= No_Element and then
                    (not Has_Element (Container, Position))
                 then 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));
74.2/5
{AI12-0112-1} Returns a cursor designating the predecessor of the node designated by Position in Container, if any.
75/5
{AI12-0112-1} procedure Previous (Position : in out Cursor)
   with Global => in access Map,
        Nonblocking => True
;
76/2
{AI95-00302-03} Equivalent to Position := Previous (Position).
76.1/5
procedure Previous (Container : in     Map;
                    Position  : in out Cursor)
   with Nonblocking, Global => null,
        Pre  => (if Position /= No_Element and then
                    (not Has_Element (Container, Position))
                 then raise Program_Error),
        Post => (if Position /= No_Element
                 then Has_Element (Container, Position));
76.2/5
{AI12-0112-1} Equivalent to Position := Previous (Container, Position).
77/5
{AI12-0112-1} function Floor (Container : Map;
                Key       : Key_Type) return Cursor
   with Post => (if Floor'Result = No_Element then True
                 else Has_Element (Container, Floor'Result))
;
78/3
{AI95-00302-03} {AI05-0264-1} Floor searches for the last node whose key is not greater than Key, using the generic formal "<" operator for keys. If such a node is found, a cursor that designates it is returned. Otherwise, No_Element is returned.
79/5
{AI12-0112-1} function Ceiling (Container : Map;
                  Key       : Key_Type) return Cursor
   with Post => (if Ceiling'Result = No_Element then True
                 else Has_Element (Container, Ceiling'Result))
;
80/3
{AI95-00302-03} {AI05-0264-1} Ceiling searches for the first node whose key is not less than Key, using the generic formal "<" operator for keys. If such a node is found, a cursor that designates it is returned. Otherwise, No_Element is returned.
81/5
{AI12-0112-1} function "<" (Left, Right : Cursor) return Boolean
   with Pre    => (if Left = No_Element or else Right = No_Element
                   then raise Constraint_Error),
        Nonblocking => Key_Type'Nonblocking and Less_Key'Nonblocking,
        Global => in access Map & Key_Type'Global & Less_Key'Global
;
82/2
{AI95-00302-03} Equivalent to Key (Left) < Key (Right).
83/5
{AI12-0112-1} function ">" (Left, Right : Cursor) return Boolean
   with Pre    => (if Left = No_Element or else Right = No_Element
                   then raise Constraint_Error),
        Nonblocking => Key_Type'Nonblocking and Less_Key'Nonblocking,
        Global => in access Map & Key_Type'Global & Less_Key'Global
;
84/2
{AI95-00302-03} Equivalent to Key (Right) < Key (Left).
85/5
{AI12-0112-1} function "<" (Left : Cursor; Right : Key_Type) return Boolean
   with Pre    => (if Left = No_Element then raise Constraint_Error),
        Nonblocking => Key_Type'Nonblocking and Less_Key'Nonblocking,
        Global => in access Map & Key_Type'Global & Less_Key'Global
;
86/2
{AI95-00302-03} Equivalent to Key (Left) < Right.
87/5
{AI12-0112-1} function ">" (Left : Cursor; Right : Key_Type) return Boolean
      with Pre    => (if Left = No_Element then raise Constraint_Error),
           Nonblocking => Key_Type'Nonblocking and Less_Key'Nonblocking,
           Global => in access Map & Key_Type'Global & Less_Key'Global
;
88/2
{AI95-00302-03} Equivalent to Right < Key (Left).
89/5
{AI12-0112-1} function "<" (Left : Key_Type; Right : Cursor) return Boolean
      with Pre    => (if Right = No_Element then raise Constraint_Error),
           Nonblocking => Key_Type'Nonblocking and Less_Key'Nonblocking,
           Global => in access Map & Key_Type'Global & Less_Key'Global
;
90/2
{AI95-00302-03} Equivalent to Left < Key (Right).
91/5
{AI12-0112-1} function ">" (Left : Key_Type; Right : Cursor) return Boolean
      with Pre    => (if Right = No_Element then raise Constraint_Error),
           Nonblocking => Key_Type'Nonblocking and Less_Key'Nonblocking,
           Global => in access Map & Key_Type'Global & Less_Key'Global
;
92/2
{AI95-00302-03} Equivalent to Key (Right) < Left.
93/5
{AI12-0112-1} procedure Reverse_Iterate
  (Container : in Map;
   Process   : not null access procedure (Position : in Cursor))
   with Allows_Exit
;
94/3
{AI95-00302-03} {AI05-0212-1} Iterates over the nodes in Container as per procedure Iterate, with the difference that the nodes are traversed in predecessor order, starting with the last node.
94.1/5
{AI12-0112-1} {AI12-0266-1} function Iterate (Container : in Map)
   return Map_Iterator_Interfaces.Parallel_Reversible_Iterator Reversible_Iterator'Class
   with Post => Tampering_With_Cursors_Prohibited (Container)
;
94.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 node in Container, starting with the first node and moving the cursor according to the successor relation when used as a forward iterator, and starting with the last node 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.
94.3/5
function Iterate (Container : in Map; Start : in Cursor)
   return Map_Iterator_Interfaces.Reversible_Iterator'Class
   with Pre  => (if Start = No_Element
                       then raise Constraint_Error) and then
                   (if not Has_Element (Container, Start)
                    then raise Program_Error),
        Post => Tampering_With_Cursors_Prohibited (Container)
;
94.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 node in Container, starting with the node 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.
94.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
94.b/3
exit when Cur = Stop;
94.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). 

Implementation Advice

95/2
{AI95-00302-03} If N is the length of a map, then the worst-case time complexity of the Element, Insert, Include, Replace, Delete, Exclude and Find operations that take a key 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). 
95.a/2
Implementation Advice: The worst-case time complexity of Element, Insert, Include, Replace, Delete, Exclude and Find operations that take a key parameter for Containers.Ordered_Maps should be O((log N)**2) or better. The worst-case time complexity of the subprograms of Containers.Ordered_Maps that take a cursor parameter should be O(1).
95.b/2
Implementation Note: A balanced (red-black) tree for keys has O(log N) worst-case performance. Note that a O(N) worst-case implementation (like a list) would be wrong. 
95.c/2
Reason: We do not mean to overly constrain implementation strategies here. However, it is important for portability that the performance of large containers has roughly the same factors on different implementations. If a program is moved to an implementation that takes O(N) to find elements, that program could be unusable when the maps are large. We allow the extra log N factors because the proportionality constant and caching effects are likely to be larger than the log factor, and we don't want to discourage innovative implementations. 

Extensions to Ada 95

95.d/2
{AI95-00302-03} The generic package Containers.Ordered_Maps is new.

Incompatibilities With Ada 2005

95.e/3
{AI05-0001-1} Subprograms Assign and Copy are added to Containers.Ordered_Maps. If an instance of Containers.Ordered_Maps is referenced in a use_clause, and an entity E with the same defining_identifier as a new entity in Containers.Ordered_Maps 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

95.f/3
{AI05-0212-1} Added iterator and indexing support to make ordered map containers more convenient to use. 

Wording Changes from Ada 2005

95.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.
95.h/3
{AI05-0084-1} Correction: Added a pragma Remote_Types so that containers can be used in distributed programs. 

Incompatibilities With Ada 2012

95.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_Maps to better support contracts and stable views. If an instance of Containers.Ordered_Maps is referenced in a use_clause, and an entity E with the same defining_identifier as a new entity in Containers.Ordered_Maps 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

95.j/5
{AI12-0212-1} Maps now support named container aggregates, so aggregate syntax can be used to create Maps.
95.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

95.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