A.18.4 Maps
1/2
{
AI95-00302-03}
The language-defined generic packages Containers.Hashed_Maps
and Containers.Ordered_Maps provide private types Map and Cursor, and
a set of operations for each type. A map container allows an arbitrary
type to be used as a key to find the element associated with that key.
A hashed map uses a hash function to organize the keys, while an ordered
map orders the keys per a specified relation. {map
container} {container
(map)} 2/2
{
AI95-00302-03}
This section describes the declarations that are
common to both kinds of maps. See A.18.5
for a description of the semantics specific to Containers.Hashed_Maps
and A.18.6 for a description of the semantics
specific to Containers.Ordered_Maps. Static Semantics
3/2
{
AI95-00302-03}
The actual function for the generic formal function
"=" on Element_Type values is expected to define a reflexive
and symmetric relationship and return the same result value each time
it is called with a particular pair of values. If it behaves in some
other manner, the function "=" on map values returns an unspecified
value. The exact arguments and number of calls of this generic formal
function by the function "=" on map values are unspecified.{unspecified
[partial]} 3.a/2
Ramification: If
the actual function for "=" is not symmetric and consistent,
the result returned by "=" for Map objects cannot be predicted.
The implementation is not required to protect against "=" raising
an exception, or returning random results, or any other “bad”
behavior. And it can call "=" in whatever manner makes sense.
But note that only the result of "=" for Map objects is unspecified;
other subprograms are not allowed to break if "=" is bad (they
aren't expected to use "=").
4/2
{
AI95-00302-03}
The type Map is used to represent maps. The type
Map needs finalization (see 7.6).5/2
{
AI95-00302-03}
{node (of a map)}
A map contains pairs of keys and elements, called
nodes. Map cursors designate nodes, but also can be thought of
as designating an element (the element contained in the node) for consistency
with the other containers. There exists an equivalence relation on keys,
whose definition is different for hashed maps and ordered maps. A map
never contains two or more nodes with equivalent keys. The length
of a map is the number of nodes it contains.{length
(of a map)} 6/2
{
AI95-00302-03}
{first node (of
a map)} {last
node (of a map)} {successor
node (of a map)} Each nonempty map has
two particular nodes called the first node and the last node
(which may be the same). Each node except for the last node has a successor
node. If there are no other intervening operations, starting with
the first node and repeatedly going to the successor node will visit
each node in the map exactly once until the last node is reached. The
exact definition of these terms is different for hashed maps and ordered
maps.7/2
{
AI95-00302-03}
[Some operations of these generic packages have
access-to-subprogram parameters. To ensure such operations are well-defined,
they guard against certain actions by the designated subprogram. In particular,
some operations check for “tampering with cursors” of a container
because they depend on the set of elements of the container remaining
constant, and others check for “tampering with elements”
of a container because they depend on elements of the container not being
replaced.]8/2
{
AI95-00302-03}
{tamper with cursors
(of a map)} A subprogram is said to tamper
with cursors of a map object M if:9/2
- it inserts or
deletes elements of M, that is, it calls the Insert, Include,
Clear, Delete, or Exclude procedures with M as a parameter; or
9.a/2
To be honest: Operations
which are defined to be equivalent to a call on one of these operations
also are included. Similarly, operations which call one of these as part
of their definition are included.
10/2
11/2
- it calls the
Move procedure with M as a parameter; or
12/2
- it calls one
of the operations defined to tamper with the cursors of M.
12.a/2
Ramification: Replace
only modifies a key and element rather than rehashing, so it does not
tamper with cursors.
13/2
{
AI95-00302-03}
{tamper with elements
(of a map)} A subprogram is said to tamper
with elements of a map object M if:14/2
- it tampers with
cursors of M; or
15/2
- it replaces
one or more elements of M, that is, it calls the Replace or Replace_Element
procedures with M as a parameter.
15.a/2
Reason: Complete
replacement of an element can cause its memory to be deallocated while
another operation is holding onto a reference to it. That can't be allowed.
However, a simple modification of (part of) an element is not a problem,
so Update_Element does not cause a problem.
16/2
{
AI95-00302-03}
Empty_Map represents the empty Map object. It has
a length of 0. If an object of type Map is not otherwise initialized,
it is initialized to the same value as Empty_Map.17/2
{
AI95-00302-03}
No_Element represents a cursor that designates
no node. If an object of type Cursor is not otherwise initialized, it
is initialized to the same value as No_Element.18/2
{
AI95-00302-03}
The predefined "=" operator for type
Cursor returns True if both cursors are No_Element, or designate the
same element in the same container.19/2
{
AI95-00302-03}
Execution of the default implementation of the
Input, Output, Read, or Write attribute of type Cursor raises Program_Error.19.a/2
Reason: A cursor
will probably be implemented in terms of one or more access values, and
the effects of streaming access values is unspecified. Rather than letting
the user stream junk by accident, we mandate that streaming of cursors
raise Program_Error by default. The attributes can always be specified
if there is a need to support streaming.
20/2
function "=" (Left, Right : Map) return Boolean;
21/2
{
AI95-00302-03}
If Left and Right denote the same map object, then
the function returns True. If Left and Right have different lengths,
then the function returns False. Otherwise, for each key K in
Left, the function returns False if:22/2
- a
key equivalent to K is not present in Right; or
23/2
- the
element associated with K in Left is not equal to the element
associated with K in Right (using the generic formal equality
operator for elements).
24/2
If
the function has not returned a result after checking all of the keys,
it returns True. Any exception raised during evaluation of key equivalence
or element equality is propagated.
24.a/2
Implementation Note:
This wording describes the canonical semantics. However, the order
and number of calls on the formal equality function is unspecified for
all of the operations that use it in this package, so an implementation
can call it as many or as few times as it needs to get the correct answer.
Specifically, there is no requirement to call the formal equality additional
times once the answer has been determined.
25/2
function Length (Container : Map) return Count_Type;
26/2
27/2
function Is_Empty (Container : Map) return Boolean;
28/2
29/2
procedure Clear (Container : in out Map);
30/2
31/2
function Key (Position : Cursor) return Key_Type;
32/2
{
AI95-00302-03}
If Position equals No_Element, then Constraint_Error
is propagated. Otherwise, Key returns the key component of the node designated
by Position.33/2
function Element (Position : Cursor) return Element_Type;
34/2
{
AI95-00302-03}
If Position equals No_Element, then Constraint_Error
is propagated. Otherwise, Element returns the element component of the
node designated by Position.35/2
procedure Replace_Element (Container : in out Map;
Position : in Cursor;
New_Item : in Element_Type);
36/2
{
AI95-00302-03}
If Position equals No_Element, then Constraint_Error
is propagated; if Position does not designate an element in Container,
then Program_Error is propagated. Otherwise Replace_Element assigns New_Item
to the element of the node designated by Position.37/2
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Key : in Key_Type;
Element : in Element_Type));
38/2
{
AI95-00302-03}
If Position equals No_Element, then Constraint_Error
is propagated. Otherwise, Query_Element calls Process.all with
the key and element from the node designated by Position as the arguments.
Program_Error is propagated if Process.all tampers with the elements
of Container. Any exception raised by Process.all is propagated.39/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));
40/2
{
AI95-00302-03}
If Position equals No_Element, then Constraint_Error
is propagated; if Position does not designate an element in Container,
then Program_Error is propagated. Otherwise Update_Element calls Process.all
with the key and element from the node designated by Position as the
arguments. Program_Error is propagated if Process.all tampers
with the elements of Container. Any exception raised by Process.all
is propagated.41/2
If
Element_Type is unconstrained and definite, then the actual Element parameter
of Process.all shall be unconstrained.
41.a/2
Ramification: This
means that the elements cannot be directly allocated from the heap; it
must be possible to change the discriminants of the element in place.
42/2
procedure Move (Target : in out Map;
Source : in out Map);
43/2
{
AI95-00302-03}
If Target denotes the same object as Source, then
Move has no effect. Otherwise, Move first calls Clear (Target). Then,
each node from Source is removed from Source and inserted into Target.
The length of Source is 0 after a successful call to Move.44/2
procedure Insert (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
45/2
{
AI95-00302-03}
Insert checks if a node with a key equivalent to
Key is already present in Container. If a match is found, Inserted is
set to False and Position designates the element with the matching key.
Otherwise, Insert allocates a new node, initializes it to Key and New_Item,
and adds it to Container; Inserted is set to True and Position designates
the newly-inserted node. Any exception raised during allocation is propagated
and Container is not modified.46/2
procedure Insert (Container : in out Map;
Key : in Key_Type;
Position : out Cursor;
Inserted : out Boolean);
47/2
{
AI95-00302-03}
Insert inserts Key into Container as per the five-parameter
Insert, with the difference that an element initialized by default (see
3.3.1) is inserted.48/2
procedure Insert (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);
49/2
{
AI95-00302-03}
Insert inserts Key and New_Item into Container
as per the five-parameter Insert, with the difference that if a node
with a key equivalent to Key is already in the map, then Constraint_Error
is propagated.49.a/2
Ramification:
This is equivalent to:
49.b/2
declare
Inserted : Boolean; C : Cursor;
begin
Insert (Container, Key, New_Item, C, Inserted);
if not Inserted then
raise Constraint_Error;
end if;
end;
49.c/2
but doesn't require the
hassle of out parameters.
50/2
procedure Include (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);
51/2
{
AI95-00302-03}
Include inserts Key and New_Item into Container
as per the five-parameter Insert, with the difference that if a node
with a key equivalent to Key is already in the map, then this operation
assigns Key and New_Item to the matching node. Any exception raised during
assignment is propagated.51.a/2
Ramification:
This is equivalent to:
51.b/2
declare
C : Cursor := Find (Container, Key);
begin
if C = No_Element then
Insert (Container, Key, New_Item);
else
Replace (Container, Key, New_Item);
end if;
end;
51.c/2
but this avoids doing
the search twice.
52/2
procedure Replace (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);
53/2
{
AI95-00302-03}
Replace checks if a node with a key equivalent
to Key is present in Container. If a match is found, Replace assigns
Key and New_Item to the matching node; otherwise, Constraint_Error is
propagated.53.a/2
Discussion: We
update the key as well as the element, as the key might include additional
information that does not participate in equivalence. If only the element
needs to be updated, use Replace_Element (Find (Container, Key), New_Element).
54/2
procedure Exclude (Container : in out Map;
Key : in Key_Type);
55/2
{
AI95-00302-03}
Exclude checks if a node with a key equivalent
to Key is present in Container. If a match is found, Exclude removes
the node from the map.55.a/2
Ramification: Exclude
should work on an empty map; nothing happens in that case.
56/2
procedure Delete (Container : in out Map;
Key : in Key_Type);
57/2
{
AI95-00302-03}
Delete checks if a node with a key equivalent to
Key is present in Container. If a match is found, Delete removes the
node from the map; otherwise, Constraint_Error is propagated.58/2
procedure Delete (Container : in out Map;
Position : in out Cursor);
59/2
{
AI95-00302-03}
If Position equals No_Element, then Constraint_Error
is propagated. If Position does not designate an element in Container,
then Program_Error is propagated. Otherwise, Delete removes the node
designated by Position from the map. Position is set to No_Element on
return.59.a/2
Ramification: The
check on Position checks that the cursor does not belong to some other
map. This check implies that a reference to the map is included in the
cursor value. This wording is not meant to require detection of dangling
cursors; such cursors are defined to be invalid, which means that execution
is erroneous, and any result is allowed (including not raising an exception).
60/2
function First (Container : Map) return Cursor;
61/2
{
AI95-00302-03}
If Length (Container) = 0, then First returns No_Element.
Otherwise, First returns a cursor that designates the first node in Container.62/2
function Next (Position : Cursor) return Cursor;
63/2
{
AI95-00302-03}
Returns a cursor that designates the successor
of the node designated by Position. If Position designates the last node,
then No_Element is returned. If Position equals No_Element, then No_Element
is returned.64/2
procedure Next (Position : in out Cursor);
65/2
66/2
function Find (Container : Map;
Key : Key_Type) return Cursor;
67/2
{
AI95-00302-03}
If Length (Container) equals 0, then Find returns
No_Element. Otherwise, Find checks if a node with a key equivalent to
Key is present in Container. If a match is found, a cursor designating
the matching node is returned; otherwise, No_Element is returned.68/2
function Element (Container : Map;
Key : Key_Type) return Element_Type;
69/2
70/2
function Contains (Container : Map;
Key : Key_Type) return Boolean;
71/2
{
AI95-00302-03}
Equivalent to Find (Container, Key) /= No_Element.72/2
function Has_Element (Position : Cursor) return Boolean;
73/2
{
AI95-00302-03}
Returns True if Position designates a node, and
returns False otherwise.73.a/2
To be honest: This
function may not detect cursors that designate deleted elements; such
cursors are invalid (see below); the result of Has_Element for invalid
cursors is unspecified (but not erroneous).
74/2
procedure Iterate
(Container : in Map;
Process : not null access procedure (Position : in Cursor));
75/2
{
AI95-00302-03}
Iterate calls Process.all with a cursor
that designates each node in Container, starting with the first node
and moving the cursor according to the successor relation. Program_Error
is propagated if Process.all tampers with the cursors of Container.
Any exception raised by Process.all is propagated.75.a/2
Implementation Note:
The “tamper with cursors” check takes place when the
operations that insert or delete elements, and so on, are called.
75.b/2
See Iterate for vectors
(A.18.2) for a suggested implementation
of the check.
Erroneous Execution
76/2
{
AI95-00302-03}
A Cursor value is invalid if any of the
following have occurred since it was created:{invalid
cursor (of a map)} {cursor
(invalid) [partial]} 77/2
- The map that
contains the node it designates has been finalized;
78/2
- The map that
contains the node it designates has been used as the Source or Target
of a call to Move; or
79/2
- The node it
designates has been deleted from the map.
80/2
The result of "="
or Has_Element is unspecified if these functions are called with an invalid
cursor parameter.{unspecified [partial]}
Execution is erroneous if any other subprogram declared
in Containers.Hashed_Maps or Containers.Ordered_Maps is called with an
invalid cursor parameter.{erroneous execution
(cause) [partial]}
80.a/2
Discussion: The
list above is intended to be exhaustive. In other cases, a cursor value
continues to designate its original element. For instance, cursor values
survive the insertion and deletion of other nodes.
80.b/2
While it is possible to
check for these cases, in many cases the overhead necessary to make the
check is substantial in time or space. Implementations are encouraged
to check for as many of these cases as possible and raise Program_Error
if detected.
Implementation Requirements
81/2
{
AI95-00302-03}
No storage associated with a Map object shall be
lost upon assignment or scope exit.82/2
{
AI95-00302-03}
The execution of an assignment_statement
for a map shall have the effect of copying the elements from the source
map object to the target map object.82.a/2
Implementation Note:
An assignment of a Map is a “deep” copy; that is the
elements are copied as well as the data structures. We say “effect
of” in order to allow the implementation to avoid copying elements
immediately if it wishes. For instance, an implementation that avoided
copying until one of the containers is modified would be allowed.
Implementation Advice
83/2
{
AI95-00302-03}
Move should not copy elements, and should minimize
copying of internal data structures. 83.a/2
Implementation Advice:
Move for a map should not copy elements,
and should minimize copying of internal data structures.
83.b/2
Implementation Note:
Usually that can be accomplished simply by moving the pointer(s)
to the internal data structures from the Source container to the Target
container.
84/2
{
AI95-00302-03}
If an exception is propagated from a map operation,
no storage should be lost, nor any elements removed from a map unless
specified by the operation. 84.a/2
Implementation Advice:
If an exception is propagated from a
map operation, no storage should be lost, nor any elements removed from
a map unless specified by the operation.
84.b/2
Reason: This is
important so that programs can recover from errors. But we don't want
to require heroic efforts, so we just require documentation of cases
where this can't be accomplished.
Wording Changes from Ada 95
84.c/2
{
AI95-00302-03}
This description of maps is new; the extensions
are documented with the specific packages.
Sponsored by Ada-Europe