A.18.6 The Package Containers.Ordered_Maps
Static Semantics
{
AI95-00302-03}
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;
{
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.
{
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]} 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.
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.
{
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]} 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.
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 "<":
Key (Map).Some_Component := New_Value;
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.
{
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.
procedure Delete_First (Container : in out Map);
{
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.
procedure Delete_Last (Container : in out Map);
{
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.
function First_Element (Container : Map) return Element_Type;
function First_Key (Container : Map) return Key_Type;
function Last (Container : Map) return Cursor;
{
AI95-00302-03}
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;
function Last_Key (Container : Map) return Key_Type;
function Previous (Position : Cursor) return Cursor;
{
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.
procedure Previous (Position : in out Cursor);
function Floor (Container : Map;
Key : Key_Type) return Cursor;
{
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.
function Ceiling (Container : Map;
Key : Key_Type) return Cursor;
{
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.
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 Reverse_Iterate
(Container : in Map;
Process : not null access procedure (Position : in Cursor));
{
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
{
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).
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).
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.
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
{
AI95-00302-03}
{
extensions to Ada 95}
The generic package
Containers.Ordered_Maps is new.
Sponsored by Ada-Europe