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 subclause 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
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.
When tampering with cursors is
prohibited
for a particular map object
M, Program_Error
is propagated by the finalization of
M, as well as by a call that
passes
M to certain of the operations of this package, as indicated
by the precondition of such an operation. Similarly, when tampering with
elements is
prohibited for
M, Program_Error is propagated
by a call that passes
M to certain of the other operations of
this package, as indicated by the precondition of such an operation.
Paragraphs 8 through
15 are removed as preconditions now describe these rules.
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 primitive "=" 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.
Map'Write for a Map object M writes Length(M)
elements of the map to the stream. It may also write additional information
about the map.
Map'Read reads the representation of a map from
the stream, and assigns to Item a map with the same length and
elements as was written by Map'Write.
function Has_Element (Position : Cursor) return Boolean
with Nonblocking, Global => in all, Use_Formal => null;
Returns True if
Position designates an element, and returns False otherwise.
function Has_Element (Container : Map; Position : Cursor)
return Boolean
with Nonblocking, Global => null, Use_Formal => null;
Returns True if
Position designates an element in Container, and returns False otherwise.
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 Tampering_With_Cursors_Prohibited
(Container : Map) return Boolean
with Nonblocking, Global => null, Use_Formal => null;
Returns True if
tampering with cursors or tampering with elements is currently prohibited
for Container, and returns False otherwise.
function Tampering_With_Elements_Prohibited
(Container : Map) return Boolean
with Nonblocking, Global => null, Use_Formal => null;
Always returns False,
regardless of whether tampering with elements is prohibited.
function Length (Container : Map) return Count_Type
with Nonblocking, Global => null, Use_Formal => null;
Returns the number
of nodes in Container.
function Is_Empty (Container : Map) return Boolean
with Nonblocking, Global => null, Use_Formal => null,
Post => Is_Empty'Result = (Length (Container) = 0);
Returns True if
Container is empty.
procedure Clear (Container : in out Map)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = 0;
Removes all the
nodes from Container.
function Key (Position : Cursor) return Key_Type
with Pre => Position /= No_Element
or else raise Constraint_Error,
Nonblocking, Global => in all, Use_Formal => Key_Type;
Key returns the
key component of the node designated by Position.
function Key (Container : Map;
Position : Cursor) return Key_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Nonblocking, Global => null, Use_Formal => Key_Type;
Key returns the
key component of the node designated by Position.
function Element (Position : Cursor) return Element_Type
with Pre => Position /= No_Element
or else raise Constraint_Error,
Nonblocking, Global => in all, Use_Formal => Element_Type;
Element returns
the element component of the node designated by Position.
function Element (Container : Map;
Position : Cursor) return Element_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Nonblocking, Global => null, Use_Formal => Element_Type;
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)
with Pre => (not Tampering_With_Elements_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
Replace_Element
assigns New_Item to the element of the node designated by Position. For
the purposes of determining whether the parameters overlap in a call
to Replace_Element, the Container parameter is not considered to overlap
with any object (including itself).
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Key : in Key_Type;
Element : in Element_Type))
with Pre => Position /= No_Element
or else raise Constraint_Error,
Global => in all;
Query_Element calls
Process.all with the key and element from the node designated
by Position as the arguments. Tampering with the elements of the map
that contains the element designated by Position is prohibited during
the execution of the call on Process.all. Any exception raised
by Process.all is propagated.
procedure Query_Element
(Container : in Map;
Position : in Cursor;
Process : not null access procedure (Key : in Key_Type;
Element : in Element_Type))
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
Query_Element calls
Process.all with the key and element from the node designated
by Position as the arguments. Tampering with the elements of Container
is prohibited during the execution of the call on Process.all.
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))
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error);
Update_Element calls Process.all with the
key and element from the node designated by Position as the arguments.
Tampering with the elements of Container is prohibited during the execution
of the call on Process.all. 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.
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global =>in out synchronized,
Default_Initial_Condition => (raise Program_Error);
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element,
Nonblocking, Global => in out synchronized,
Default_Initial_Condition => (raise Program_Error);
The types Constant_Reference_Type
and Reference_Type need finalization.
This paragraph
was deleted.
function Constant_Reference (Container : aliased in Map;
Position : in Cursor)
return Constant_Reference_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
This function (combined
with the Constant_Indexing and Implicit_Dereference aspects) provides
a convenient way to gain read access to an individual element of a Map
given a cursor.
Constant_Reference returns an object whose discriminant
is an access value that designates the element designated by Position.
Tampering with the elements of Container is prohibited while the object
returned by Constant_Reference exists and has not been finalized.
function Reference (Container : aliased in out Map;
Position : in Cursor)
return Reference_Type
with Pre => (Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
This function (combined
with the Variable_Indexing and Implicit_Dereference aspects) provides
a convenient way to gain read and write access to an individual element
of a Map given a cursor.
Reference returns an object whose discriminant
is an access value that designates the element designated by Position.
Tampering with the elements of Container is prohibited while the object
returned by Reference exists and has not been finalized.
function Constant_Reference (Container : aliased in Map;
Key : in Key_Type)
return Constant_Reference_Type
with Pre => Find (Container, Key) /= No_Element
or else raise Constraint_Error,
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
This function (combined
with the Constant_Indexing and Implicit_Dereference aspects) provides
a convenient way to gain read access to an individual element of a map
given a key value.
Equivalent to Constant_Reference (Container, Find
(Container, Key)).
function Reference (Container : aliased in out Map;
Key : in Key_Type)
return Reference_Type
with Pre => Find (Container, Key) /= No_Element
or else raise Constraint_Error,
Post => Tampering_With_Cursors_Prohibited (Container),
Nonblocking, Global => null, Use_Formal => null;
This function (combined
with the Variable_Indexing and Implicit_Dereference aspects) provides
a convenient way to gain read and write access to an individual element
of a map given a key value.
Equivalent to Reference (Container, Find (Container,
Key)).
procedure Assign (Target : in out Map; Source : in Map)
with Pre => not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error,
Post => Length (Source) = Length (Target);
If Target denotes
the same object as Source, the operation has no effect. Otherwise, the
key/element pairs of Source are copied to Target as for an
assignment_statement
assigning Source to Target.
procedure Move (Target : in out Map;
Source : in out Map)
with Pre => (not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error) and then
(not Tampering_With_Cursors_Prohibited (Source)
or else raise Program_Error),
Post => (if not Target'Has_Same_Storage (Source) then
Length (Target) = Length (Source'Old) and then
Length (Source) = 0);
If Target denotes
the same object as Source, then the operation has no effect. Otherwise,
the operation is equivalent to Assign (Target, Source) followed by Clear
(Source).
procedure Insert (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - 1
or else raise Constraint_Error),
Post => (declare
Original_Length : constant Count_Type :=
Length (Container)'Old;
begin
Has_Element (Container, Position) and then
(if Inserted then
Length (Container) = Original_Length + 1
else
Length (Container) = Original_Length));
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)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - 1
or else raise Constraint_Error),
Post => (declare
Original_Length : constant Count_Type :=
Length (Container)'Old;
begin
Has_Element (Container, Position) and then
(if Inserted then
Length (Container) = Original_Length + 1
else
Length (Container) = Original_Length));
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)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - 1
or else raise Constraint_Error),
Post => Length (Container) = Length (Container)'Old + 1;
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)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Length (Container) <= Count_Type'Last - 1
or else raise Constraint_Error),
Post => (declare
Original_Length : constant Count_Type :=
Length (Container)'Old;
begin
Length (Container)
in Original_Length | Original_Length + 1);
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)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = Length (Container)'Old;
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)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => (declare
Original_Length : constant Count_Type :=
Length (Container)'Old;
begin
Length (Container)
in Original_Length - 1 | Original_Length);
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)
with Pre => not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = Length (Container)'Old - 1;
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)
with Pre => (not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error) and then
(Position /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Position)
or else raise Program_Error),
Post => Length (Container) = Length (Container)'Old - 1 and then
Position = No_Element;
Delete removes the
node designated by Position from the map.
function First (Container : Map) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Post => (if not Is_Empty (Container)
then Has_Element (Container, First'Result)
else First'Result = No_Element);
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
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element then Next'Result = No_Element);
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.
function Next (Container : Map;
Position : Cursor) return Cursor
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position = No_Element then Next'Result = No_Element
elsif Next'Result = No_Element then
Position = Last (Container)
else Has_Element (Container, Next'Result));
Returns a cursor
designating the successor of the node designated by Position in Container.
procedure Next (Position : in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;
Equivalent to Position
:= Next (Position).
procedure Next (Container : in Map;
Position : in out Cursor)
with Nonblocking, Global => null, Use_Formal => null,
Pre => Position = No_Element or else
Has_Element (Container, Position)
or else raise Program_Error,
Post => (if Position /= No_Element
then Has_Element (Container, Position));
Equivalent to Position
:= Next (Container, Position).
function Find (Container : Map;
Key : Key_Type) return Cursor
with Post => (if Find'Result = No_Element
then Has_Element (Container, Find'Result));
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.
Paragraphs 72
and 73 were moved above.
procedure Iterate
(Container : in Map;
Process : not null access procedure (Position : in Cursor))
with Allows_Exit;
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.
Tampering with the cursors of Container is prohibited during the execution
of a call on Process.all. Any exception raised by Process.all
is propagated.
The nested package Stable provides a type Stable.Map
that represents a
stable map,
which is one
that cannot grow and shrink. Such a map can be created by calling the
Copy function, or by establishing a
stabilized view of an ordinary
map.
The subprograms of
the map package that have a parameter or result of type Map are included
in the nested package Stable with the same specification, except that
the following are omitted:
Tampering_With_Cursors_Prohibited, Tampering_With_Elements_Prohibited,
Assign, Move, Insert, Include, Clear, Delete, Exclude, (for Ordered_Maps)
Delete_First and Delete_Last, and (for Hashed_Maps) Reserve_Capacity
The operations of this package are equivalent to
those for ordinary maps, except that the calls to Tampering_With_Cursors_Prohibited
and Tampering_With_Elements_Prohibited that occur in preconditions are
replaced by False, and any that occur in postconditions are replaced
by True.
If a stable map is declared with the Base discriminant
designating a pre-existing ordinary map, the stable map represents a
stabilized view of the underlying ordinary map, and any operation on
the stable map is reflected on the underlying ordinary map. While a stabilized
view exists, any operation that tampers with elements performed on the
underlying map is prohibited. The finalization of a stable map that provides
such a view removes this restriction on the underlying ordinary map (though
some other restriction can exist due to other concurrent iterations or
stabilized views).
If a stable map is declared without specifying
Base, the object is necessarily initialized. The initializing expression
of the stable map, typically a call on Copy, determines the Length of
the map. The Length of a stable map never changes after initialization.
Bounded (Run-Time) Errors
It is a bounded error for the
actual function associated with a generic formal subprogram, when called
as part of an operation of a map package, to tamper with elements of
any map parameter of the operation. Either Program_Error is raised, or
the operation works as defined on the value of the map either prior to,
or subsequent to, some or all of the modifications to the map.
It is a bounded error to call
any subprogram declared in the visible part of a map package when the
associated container has been finalized. If the operation takes Container
as an
in out parameter, then it raises Constraint_Error or Program_Error.
Otherwise, the operation either proceeds as it would for an empty container,
or it raises Constraint_Error
or Program_Error.
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 Target of a call to Assign, or as the target of an
assignment_statement;
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 removed from the
map that previously contained the node.
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.
Execution is erroneous if the map associated with
the result of a call to Reference or Constant_Reference is finalized
before the result object returned by the call to Reference or Constant_Reference
is finalized.
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 and changing the length of the target
object to that of the source 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.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
