A.18.6 The Package Containers.Ordered_Maps
Static Semantics
The generic library
package Containers.Ordered_Maps has the following declaration:
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);
function Equivalent_Keys (Left, Right : Key_Type)
return Boolean;
type Map
is tagged private;
pragma Preelaborable_Initialization(Map);
type Cursor
is private;
pragma Preelaborable_Initialization(Cursor);
Empty_Map :
constant Map;
No_Element :
constant Cursor;
function "=" (Left, Right : Map) return Boolean;
function Length (Container : Map)
return Count_Type;
function Is_Empty (Container : Map)
return Boolean;
procedure Clear (Container :
in out Map);
function Key (Position : Cursor)
return Key_Type;
function Element (Position : Cursor)
return Element_Type;
procedure Replace_Element (Container :
in out Map;
Position :
in Cursor;
New_Item :
in Element_Type);
procedure Query_Element
(Position :
in Cursor;
Process :
not null access procedure (Key :
in Key_Type;
Element :
in Element_Type));
procedure Update_Element
(Container :
in out Map;
Position :
in Cursor;
Process :
not null access procedure
(Key :
in Key_Type;
Element :
in out Element_Type));
procedure Move (Target :
in out Map;
Source :
in out Map);
procedure Insert (Container :
in out Map;
Key :
in Key_Type;
New_Item :
in Element_Type;
Position :
out Cursor;
Inserted :
out Boolean);
procedure Insert (Container :
in out Map;
Key :
in Key_Type;
Position :
out Cursor;
Inserted :
out Boolean);
procedure Insert (Container :
in out Map;
Key :
in Key_Type;
New_Item :
in Element_Type);
procedure Include (Container :
in out Map;
Key :
in Key_Type;
New_Item :
in Element_Type);
procedure Replace (Container :
in out Map;
Key :
in Key_Type;
New_Item :
in Element_Type);
procedure Exclude (Container :
in out Map;
Key :
in Key_Type);
procedure Delete (Container :
in out Map;
Key :
in Key_Type);
procedure Delete (Container :
in out Map;
Position :
in out Cursor);
procedure Delete_First (Container :
in out Map);
procedure Delete_Last (Container :
in out Map);
function First (Container : Map)
return Cursor;
function First_Element (Container : Map)
return Element_Type;
function First_Key (Container : Map)
return Key_Type;
function Last (Container : Map)
return Cursor;
function Last_Element (Container : Map)
return Element_Type;
function Last_Key (Container : Map)
return Key_Type;
function Next (Position : Cursor)
return Cursor;
procedure Next (Position :
in out Cursor);
function Previous (Position : Cursor)
return Cursor;
procedure Previous (Position :
in out Cursor);
function Find (Container : Map;
Key : Key_Type)
return Cursor;
function Element (Container : Map;
Key : Key_Type)
return Element_Type;
function Floor (Container : Map;
Key : Key_Type)
return Cursor;
function Ceiling (Container : Map;
Key : Key_Type)
return Cursor;
function Contains (Container : Map;
Key : Key_Type)
return Boolean;
function Has_Element (Position : Cursor)
return Boolean;
function "<" (Left, Right : Cursor) return Boolean;
function ">" (Left, Right : Cursor) return Boolean;
function "<" (Left : Cursor; Right : Key_Type) return Boolean;
function ">" (Left : Cursor; Right : Key_Type) return Boolean;
function "<" (Left : Key_Type; Right : Cursor) return Boolean;
function ">" (Left : Key_Type; Right : Cursor) return Boolean;
procedure Iterate
(Container :
in Map;
Process :
not null access procedure (Position :
in Cursor));
procedure Reverse_Iterate
(Container :
in Map;
Process :
not null access procedure (Position :
in Cursor));
private
... -- not specified by the language
end Ada.Containers.Ordered_Maps;
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.
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.
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.
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.
procedure Delete_First (Container : in out Map);
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.
procedure Delete_Last (Container : in out Map);
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.
function First_Element (Container : Map) return Element_Type;
Equivalent to Element
(First (Container)).
function First_Key (Container : Map) return Key_Type;
Equivalent to Key
(First (Container)).
function Last (Container : Map) return Cursor;
Returns a cursor
that designates the last node in Container. If Container is empty, returns
No_Element.
function Last_Element (Container : Map) return Element_Type;
Equivalent to Element
(Last (Container)).
function Last_Key (Container : Map) return Key_Type;
Equivalent to Key
(Last (Container)).
function Previous (Position : Cursor) return Cursor;
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.
procedure Previous (Position : in out Cursor);
Equivalent to Position
:= Previous (Position).
function Floor (Container : Map;
Key : Key_Type) return Cursor;
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.
function Ceiling (Container : Map;
Key : Key_Type) return Cursor;
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.
function "<" (Left, Right : Cursor) return Boolean;
Equivalent to Key
(Left) < Key (Right).
function ">" (Left, Right : Cursor) return Boolean;
Equivalent to Key
(Right) < Key (Left).
function "<" (Left : Cursor; Right : Key_Type) return Boolean;
Equivalent to Key
(Left) < Right.
function ">" (Left : Cursor; Right : Key_Type) return Boolean;
Equivalent to Right
< Key (Left).
function "<" (Left : Key_Type; Right : Cursor) return Boolean;
Equivalent to Left
< Key (Right).
function ">" (Left : Key_Type; Right : Cursor) return Boolean;
Equivalent to Key
(Right) < Left.
procedure Reverse_Iterate
(Container : in Map;
Process : not null access procedure (Position : in Cursor));
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
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).
Sponsored by Ada-Europe