A.18.6 The Generic Package Containers.Ordered_Maps
Static Semantics
{
AI95-00302-03}
The generic library package Containers.Ordered_Maps
has the following declaration:
{
AI05-0084-1}
{
AI05-0212-1}
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);
function Equivalent_Keys (Left, Right : Key_Type) return Boolean;
{
AI05-0212-1}
type Map is tagged private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type;
pragma Preelaborable_Initialization(Map);
type Cursor is private;
pragma Preelaborable_Initialization(Cursor);
Empty_Map : constant Map;
No_Element : constant Cursor;
{
AI05-0212-1}
function Has_Element (Position : Cursor) return Boolean;
{
AI05-0212-1}
package Map_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
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));
{
AI05-0212-1}
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;
{
AI05-0212-1}
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;
{
AI05-0212-1}
function Constant_Reference (Container : aliased in Map;
Position : in Cursor)
return Constant_Reference_Type;
{
AI05-0212-1}
function Reference (Container : aliased in out Map;
Position : in Cursor)
return Reference_Type;
{
AI05-0212-1}
function Constant_Reference (Container : aliased in Map;
Key : in Key_Type)
return Constant_Reference_Type;
{
AI05-0212-1}
function Reference (Container : aliased in out Map;
Key : in Key_Type)
return Reference_Type;
{
AI05-0001-1}
procedure Assign (Target : in out Map; Source : in Map);
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;
This paragraph
was deleted. {
AI05-0212-1}
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));
{
AI05-0212-1}
function Iterate (Container : in Map)
return Map_Iterator_Interfaces.Reversible_Iterator'Class;
{
AI05-0262-1}
function Iterate (Container : in Map; Start : in Cursor)
return Map_Iterator_Interfaces.Reversible_Iterator'Class;
private
... -- not specified by the language
end Ada.Containers.Ordered_Maps;
{
AI95-00302-03}
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}
{
AI05-0044-1}
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),
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.
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.
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}
{
AI05-0262-1}
The
first node 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 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 successor of a node is the node with the smallest key that is larger than the key
of the given node. The predecessor 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.
function Copy (Source : Map) return Map;
{
AI05-0001-1}
Returns a map whose keys and elements are initialized
from the corresponding keys and elements of Source.
procedure Delete_First (Container : in out Map);
{
AI95-00302-03}
{
AI05-0264-1}
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}
{
AI05-0264-1}
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}
{
AI05-0262-1}
If Position equals No_Element, then Previous returns
No_Element. Otherwise, Previous returns a cursor designating the predecessor
node of 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}
{
AI05-0264-1}
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}
{
AI05-0264-1}
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}
{
AI05-0212-1}
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.
function Iterate (Container : in Map)
return Map_Iterator_Interfaces.Reversible_Iterator'Class;
{
AI05-0212-1}
{
AI05-0265-1}
{
AI05-0269-1}
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.
function Iterate (Container : in Map; Start : in Cursor)
return Map_Iterator_Interfaces.Reversible_Iterator'Class;
{
AI05-0262-1}
{
AI05-0265-1}
{
AI05-0269-1}
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.
Discussion:
Exits are allowed from the loops created using the iterator objects.
In particular, to stop the iteration at a particular cursor, just add
exit when Cur = Stop;
in
the body of the loop (assuming that Cur is the loop parameter
and Stop is the cursor that you want to stop at).
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}
The generic package Containers.Ordered_Maps
is new.
Incompatibilities With Ada 2005
{
AI05-0001-1}
Subprograms Assign and Copy
are added to Containers.Ordered_Maps. If an instance of Containers.Ordered_Maps
is referenced in a use_clause,
and an entity E with the same defining_identifier
as a new entity in Containers.Ordered_Maps is defined in a package that
is also referenced in a use_clause,
the entity E may no longer be use-visible, resulting in errors.
This should be rare and is easily fixed if it does occur.
Extensions to Ada 2005
{
AI05-0212-1}
Added iterator and indexing
support to make ordered map containers more convenient to use.
Wording Changes from Ada 2005
{
AI05-0044-1}
Correction: Redefined "<" actuals
to require a strict weak ordering; the old definition allowed indeterminant
comparisons that would not have worked in a container.
{
AI05-0084-1}
Correction: Added a pragma Remote_Types
so that containers can be used in distributed programs.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe