A.18.6 The Package Containers.Ordered_Maps
Static Semantics
1/2
{
AI95-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
{
AI95-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
{
AI95-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
{
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.{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
{
AI95-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
{
AI95-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
{
AI95-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
65/2
function First_Key (Container : Map) return Key_Type;
66/2
67/2
function Last (Container : Map) return Cursor;
68/2
{
AI95-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
71/2
function Last_Key (Container : Map) return Key_Type;
72/2
73/2
function Previous (Position : Cursor) return Cursor;
74/2
{
AI95-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
77/2
function Floor (Container : Map;
Key : Key_Type) return Cursor;
78/2
{
AI95-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
{
AI95-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
83/2
function ">" (Left, Right : Cursor) return Boolean;
84/2
85/2
function "<" (Left : Cursor; Right : Key_Type) return Boolean;
86/2
87/2
function ">" (Left : Cursor; Right : Key_Type) return Boolean;
88/2
89/2
function "<" (Left : Key_Type; Right : Cursor) return Boolean;
90/2
91/2
function ">" (Left : Key_Type; Right : Cursor) return Boolean;
92/2
93/2
procedure Reverse_Iterate
(Container : in Map;
Process : not null access procedure (Position : in Cursor));
94/2
{
AI95-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
{
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}
{extensions to Ada 95} The
generic package Containers.Ordered_Maps is new.
Sponsored by Ada-Europe