Next: , Previous: A.18.5, Up: A.18


A.18.6 The Package Containers.Ordered_Maps

Static Semantics

1/2
{20302AI95−00302−03} The generic library package Containers.Ordered_Maps has the following declaration:

2/2

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

3/2

        function Equivalent_Keys (Left, Right Key_Type) return Boolean;

4/2

        type Map is tagged private;
        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;

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

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

        function Has_Element (Position Cursor) return Boolean;

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

52/2

     private

53/2

        ... −− not specified by the language

54/2

     end Ada.Containers.Ordered_Maps;

55/2
{20302AI95−00302−03} {equivalent key (of an ordered map)} 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/2
{20302AI95−00302−03} 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 ordering relationship, that is, be irreflexive, asymmetric, and transitive. 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.{unspecified [partial]} 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
{20302AI95−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.{unspecified [partial]} 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/2
{20302AI95−00302−03} {first node (of an ordered map)} {last node (of an ordered map)} {successor node (of an ordered map)} 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.

59/2

     procedure Delete_First (Container in out Map);

60/2

{20302AI95−00302−03} 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/2

{20302AI95−00302−03} 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

{20302AI95−00302−03} Equivalent to Element (First (Container)).

65/2

     function First_Key (Container Map) return Key_Type;

66/2

{20302AI95−00302−03} Equivalent to Key (First (Container)).

67/2

     function Last (Container Map) return Cursor;

68/2

{20302AI95−00302−03} 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

{20302AI95−00302−03} Equivalent to Element (Last (Container)).

71/2

     function Last_Key (Container Map) return Key_Type;

72/2

{20302AI95−00302−03} Equivalent to Key (Last (Container)).

73/2

     function Previous (Position Cursor) return Cursor;

74/2

{20302AI95−00302−03} If Position equals No_Element, then Previous returns No_Element. Otherwise Previous returns a cursor designating the node that precedes 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

{20302AI95−00302−03} Equivalent to Position := Previous (Position).

77/2

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

78/2

{20302AI95−00302−03} 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/2

{20302AI95−00302−03} 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

{20302AI95−00302−03} Equivalent to Key (Left) < Key (Right).

83/2

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

84/2

{20302AI95−00302−03} Equivalent to Key (Right) < Key (Left).

85/2

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

86/2

{20302AI95−00302−03} Equivalent to Key (Left) < Right.

87/2

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

88/2

{20302AI95−00302−03} Equivalent to Right < Key (Left).

89/2

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

90/2

{20302AI95−00302−03} Equivalent to Left < Key (Right).

91/2

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

92/2

{20302AI95−00302−03} Equivalent to Key (Right) < Left.

93/2

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

94/2

{20302AI95−00302−03} Iterates over the nodes in Container as per Iterate, with the difference that the nodes are traversed in predecessor order, starting with the last node.
Implementation Advice

95/2
{20302AI95−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

{20302AI95−00302−03} {extensions to Ada 95} The generic package Containers.Ordered_Maps is new.