A.18.4 Maps
{
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)}
{
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
{
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]} 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 "=").
{
AI95-00302-03}
The type Map is used to represent maps. The type Map needs finalization
(see
7.6).
{
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)}
{
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.
{
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.]
{
AI95-00302-03}
{tamper with cursors (of a map)}
A subprogram is said to
tamper with cursors
of a map object
M if:
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
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.
it finalizes M; or
it calls the Move procedure with M as a
parameter; or
it calls one of the operations defined to tamper
with the cursors of M.
Ramification: Replace only modifies a
key and element rather than rehashing, so it does not tamper with cursors.
{
AI95-00302-03}
{tamper with elements (of a map)}
A subprogram is said to
tamper with elements
of a map object
M if:
it tampers with cursors of M; or
it replaces one or more elements of M, that
is, it calls the Replace or Replace_Element procedures with M
as a parameter.
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.
{
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.
{
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.
{
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.
{
AI95-00302-03}
Execution of the default implementation of the Input, Output, Read, or
Write attribute of type Cursor raises Program_Error.
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.
function "=" (Left, Right : Map) return Boolean;
{
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:
a key equivalent to K is not present
in Right; or
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).
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.
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.
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;
{
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.
function Element (Position : Cursor) return Element_Type;
{
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.
procedure Replace_Element (Container : in out Map;
Position : in Cursor;
New_Item : in Element_Type);
{
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.
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Key : in Key_Type;
Element : in Element_Type));
{
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.
procedure Update_Element
(Container : in out Map;
Position : in Cursor;
Process : not null access procedure (Key : in Key_Type;
Element : in out Element_Type));
{
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.
If Element_Type
is unconstrained and definite, then the actual Element parameter of Process.all
shall be unconstrained.
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.
procedure Move (Target : in out Map;
Source : in out Map);
{
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.
procedure Insert (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
{
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.
procedure Insert (Container : in out Map;
Key : in Key_Type;
Position : out Cursor;
Inserted : out Boolean);
{
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.
procedure Insert (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);
{
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.
Ramification:
This is equivalent to:
declare
Inserted : Boolean; C : Cursor;
begin
Insert (Container, Key, New_Item, C, Inserted);
if not Inserted then
raise Constraint_Error;
end if;
end;
but doesn't require the hassle of out
parameters.
procedure Include (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);
{
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.
Ramification:
This is equivalent to:
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;
but this avoids doing the search twice.
procedure Replace (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);
{
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.
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).
procedure Exclude (Container : in out Map;
Key : in Key_Type);
{
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.
Ramification: Exclude should work on
an empty map; nothing happens in that case.
procedure Delete (Container : in out Map;
Key : in Key_Type);
{
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.
procedure Delete (Container : in out Map;
Position : in out Cursor);
{
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.
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).
function First (Container : Map) return Cursor;
{
AI95-00302-03}
If Length (Container) = 0, then First returns No_Element. Otherwise,
First returns a cursor that designates the first node in Container.
function Next (Position : Cursor) return Cursor;
{
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.
procedure Next (Position : in out Cursor);
function Find (Container : Map;
Key : Key_Type) return Cursor;
{
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.
function Element (Container : Map;
Key : Key_Type) return Element_Type;
function Contains (Container : Map;
Key : Key_Type) return Boolean;
{
AI95-00302-03}
Equivalent to Find (Container, Key) /= No_Element.
function Has_Element (Position : Cursor) return Boolean;
{
AI95-00302-03}
Returns True if Position designates a node, and returns False otherwise.
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).
procedure Iterate
(Container : in Map;
Process : not null access procedure (Position : in Cursor));
{
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.
Implementation Note: The “tamper
with cursors” check takes place when the operations that insert
or delete elements, and so on, are called.
See Iterate for vectors (
A.18.2)
for a suggested implementation of the check.
Erroneous Execution
{
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]} The map that contains the node it designates has
been finalized;
The map that contains the node it designates has
been used as the Source or Target of a call to Move; or
The node it designates has been deleted from the
map.
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]} 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.
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
{
AI95-00302-03}
No storage associated with a Map object shall be lost upon assignment
or scope exit.
{
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.
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
{
AI95-00302-03}
Move should not copy elements, and should minimize copying of internal
data structures.
Implementation Advice: Move for a map
should not copy elements, and should minimize copying of internal data
structures.
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.
{
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.
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.
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
{
AI95-00302-03}
This description of maps is new; the extensions are documented with the
specific packages.
Sponsored by Ada-Europe