A.18.4 Maps
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.
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
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.
The type Map is used to represent maps. The type
Map needs finalization (see
7.6).
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.
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.
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.
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
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.
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.
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.
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.
The predefined "=" operator for type Cursor
returns True if both cursors are No_Element, or designate the same element
in the same container.
Execution of the default implementation of the Input,
Output, Read, or Write attribute of type Cursor raises Program_Error.
function "=" (Left, Right : Map) return Boolean;
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.
function Length (Container : Map) return Count_Type;
Returns the number
of nodes in Container.
function Is_Empty (Container : Map) return Boolean;
Equivalent to Length
(Container) = 0.
procedure Clear (Container : in out Map);
Removes all the
nodes from Container.
function Key (Position : Cursor) return Key_Type;
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;
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);
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));
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));
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.
procedure Move (Target : in out Map;
Source : in out Map);
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);
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);
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);
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.
procedure Include (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);
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.
procedure Replace (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);
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.
procedure Exclude (Container : in out Map;
Key : in Key_Type);
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.
procedure Delete (Container : in out Map;
Key : in Key_Type);
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);
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.
function First (Container : Map) return Cursor;
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;
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);
Equivalent to Position
:= Next (Position).
function Find (Container : Map;
Key : Key_Type) return Cursor;
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;
Equivalent to Element
(Find (Container, Key)).
function Contains (Container : Map;
Key : Key_Type) return Boolean;
Equivalent to Find
(Container, Key) /= No_Element.
function Has_Element (Position : Cursor) return Boolean;
Returns True if
Position designates a node, and returns False otherwise.
procedure Iterate
(Container : in Map;
Process : not null access procedure (Position : in Cursor));
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.
Erroneous Execution
A Cursor value is
invalid
if any of the following have occurred since it was created:
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.
Execution is erroneous if any other subprogram declared in Containers.Hashed_Maps
or Containers.Ordered_Maps is called with an invalid cursor parameter.
Implementation Requirements
No storage associated with a Map object shall be
lost upon assignment or scope exit.
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 Advice
Move should not copy elements, and should minimize
copying of internal data structures.
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.
Sponsored by Ada-Europe