Ada Reference Manual — Legal Information

A.18.6 The Generic Package Containers.Ordered_Maps

Static Semantics

1/2

The generic library package Containers.Ordered_Maps has the following declaration:

2/3

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
   pragma Preelaborate(Ordered_Maps);
   pragma Remote_Types(Ordered_Maps);

3/2

function Equivalent_Keys (Left, Right : Key_Type) return Boolean;

4/3

   type Map is tagged private
      with Constant_Indexing => Constant_Reference,
           Variable_Indexing => Reference,
           Default_Iterator  => Iterate,
           Iterator_Element  => Element_Type;
   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/3

function Has_Element (Position : Cursor) return Boolean;

7.2/3

package Map_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);

8/2

function "=" (Left, Right : Map) return Boolean;

9/2

function Length (Container : Map) return Count_Type;

10/2

function Is_Empty (Container : Map) return Boolean;

11/2

procedure Clear (Container : in out Map);

12/2

function Key (Position : Cursor) return Key_Type;

13/2

function Element (Position : Cursor) return Element_Type;

14/2

   procedure Replace_Element (Container : in out Map;
                              Position  : in     Cursor;
                              New_Item  : in     Element_Type);

15/2

   procedure Query_Element
     (Position : in Cursor;
      Process  : not null access procedure (Key     : in Key_Type;
                                            Element : in Element_Type));

16/2

   procedure Update_Element
     (Container : in out Map;
      Position  : in     Cursor;
      Process   : not null access procedure
                      (Key     : in     Key_Type;
                       Element : in out Element_Type));

16.1/3

   type Constant_Reference_Type
         (Element : not null access constant Element_Type) is private
      with Implicit_Dereference => Element;

16.2/3

type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;

16.3/3

   function Constant_Reference (Container : aliased in Map;
                                Position  : in Cursor)
      return Constant_Reference_Type;

16.4/3

   function Reference (Container : aliased in out Map;
                       Position  : in Cursor)
      return Reference_Type;

16.5/3

   function Constant_Reference (Container : aliased in Map;
                                Key       : in Key_Type)
      return Constant_Reference_Type;

16.6/3

   function Reference (Container : aliased in out Map;
                       Key       : in Key_Type)
      return Reference_Type;

16.7/3

procedure Assign (Target : in out Map; Source : in Map);

16.8/3

function Copy (Source : Map) return Map;

17/2

procedure Move (Target : in out Map;
Source : in out Map);

18/2

   procedure Insert (Container : in out Map;
                     Key       : in     Key_Type;
                     New_Item  : in     Element_Type;
                     Position  :    out Cursor;
                     Inserted  :    out Boolean);

19/2

   procedure Insert (Container : in out Map;
                     Key       : in     Key_Type;
                     Position  :    out Cursor;
                     Inserted  :    out Boolean);

20/2

   procedure Insert (Container : in out Map;
                     Key       : in     Key_Type;
                     New_Item  : in     Element_Type);

21/2

   procedure Include (Container : in out Map;
                      Key       : in     Key_Type;
                      New_Item  : in     Element_Type);

22/2

   procedure Replace (Container : in out Map;
                      Key       : in     Key_Type;
                      New_Item  : in     Element_Type);

23/2

procedure Exclude (Container : in out Map;
Key : in Key_Type);

24/2

procedure Delete (Container : in out Map;
Key : in Key_Type);

25/2

procedure Delete (Container : in out Map;
Position : in out Cursor);

26/2

procedure Delete_First (Container : in out Map);

27/2

procedure Delete_Last (Container : in out Map);

28/2

function First (Container : Map) return Cursor;

29/2

function First_Element (Container : Map) return Element_Type;

30/2

function First_Key (Container : Map) return Key_Type;

31/2

function Last (Container : Map) return Cursor;

32/2

function Last_Element (Container : Map) return Element_Type;

33/2

function Last_Key (Container : Map) return Key_Type;

34/2

function Next (Position : Cursor) return Cursor;

35/2

procedure Next (Position : in out Cursor);

36/2

function Previous (Position : Cursor) return Cursor;

37/2

procedure Previous (Position : in out Cursor);

38/2

function Find (Container : Map;
Key : Key_Type) return Cursor;

39/2

function Element (Container : Map;
Key : Key_Type) return Element_Type;

40/2

function Floor (Container : Map;
Key : Key_Type) return Cursor;

41/2

function Ceiling (Container : Map;
Key : Key_Type) return Cursor;

42/2

function Contains (Container : Map;
Key : Key_Type) return Boolean;

43/3

This paragraph was deleted.

44/2

function "<" (Left, Right : Cursor) return Boolean;

45/2

function ">" (Left, Right : Cursor) return Boolean;

46/2

function "<" (Left : Cursor; Right : Key_Type) return Boolean;

47/2

function ">" (Left : Cursor; Right : Key_Type) return Boolean;

48/2

function "<" (Left : Key_Type; Right : Cursor) return Boolean;

49/2

function ">" (Left : Key_Type; Right : Cursor) return Boolean;

50/2

   procedure Iterate
     (Container : in Map;
      Process   : not null access procedure (Position : in Cursor));

51/2

   procedure Reverse_Iterate
     (Container : in Map;
      Process   : not null access procedure (Position : in Cursor));

51.1/3

function Iterate (Container : in Map)
return Map_Iterator_Interfaces.Reversible_Iterator'Class;

51.2/3

function Iterate (Container : in Map; Start : in Cursor)
return Map_Iterator_Interfaces.Reversible_Iterator'Class;

52/2

private

53/2

... -- not specified by the language

54/2

end Ada.Containers.Ordered_Maps;

55/2

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

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.

57/2

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.

58/3

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/3

function Copy (Source : Map) return Map;

58.2/3

Returns a map whose keys and elements are initialized from the corresponding keys and elements of Source.

59/2

procedure Delete_First (Container : in out Map);

60/3

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/2

procedure Delete_Last (Container : in out Map);

62/3

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/2

function First_Element (Container : Map) return Element_Type;

64/2

Equivalent to Element (First (Container)).

65/2

function First_Key (Container : Map) return Key_Type;

66/2

Equivalent to Key (First (Container)).

67/2

function Last (Container : Map) return Cursor;

68/2

Returns a cursor that designates the last node in Container. If Container is empty, returns No_Element.

69/2

function Last_Element (Container : Map) return Element_Type;

70/2

Equivalent to Element (Last (Container)).

71/2

function Last_Key (Container : Map) return Key_Type;

72/2

Equivalent to Key (Last (Container)).

73/2

function Previous (Position : Cursor) return Cursor;

74/3

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.

75/2

procedure Previous (Position : in out Cursor);

76/2

Equivalent to Position := Previous (Position).

77/2

function Floor (Container : Map;
Key : Key_Type) return Cursor;

78/3

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/2

function Ceiling (Container : Map;
Key : Key_Type) return Cursor;

80/3

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/2

function "<" (Left, Right : Cursor) return Boolean;

82/2

Equivalent to Key (Left) < Key (Right).

83/2

function ">" (Left, Right : Cursor) return Boolean;

84/2

Equivalent to Key (Right) < Key (Left).

85/2

function "<" (Left : Cursor; Right : Key_Type) return Boolean;

86/2

Equivalent to Key (Left) < Right.

87/2

function ">" (Left : Cursor; Right : Key_Type) return Boolean;

88/2

Equivalent to Right < Key (Left).

89/2

function "<" (Left : Key_Type; Right : Cursor) return Boolean;

90/2

Equivalent to Left < Key (Right).

91/2

function ">" (Left : Key_Type; Right : Cursor) return Boolean;

92/2

Equivalent to Key (Right) < Left.

93/2

procedure Reverse_Iterate
(Container : in Map;
Process : not null access procedure (Position : in Cursor));

94/3

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/3

function Iterate (Container : in Map)
return Map_Iterator_Interfaces.Reversible_Iterator'Class;

94.2/3

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 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. 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/3

function Iterate (Container : in Map; Start : in Cursor)
return Map_Iterator_Interfaces.Reversible_Iterator'Class;

94.4/3

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.

Implementation Advice

95/2

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

Ada 2005 and 2012 Editions sponsored in part by Ada-Europe