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}
{
AI12-0112-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
with Preelaborate, Remote_Types,
Nonblocking, Global =>
in out synchronized isDiscussion: {
AI12-0112-1}
For discussion on the reasons and meaning of the specifications of the
Global and Nonblocking aspects in this generic package, see the notes
on the equivalent operations in the specification of the Containers.Vectors
package (see
A.18.2).
{
AI12-0112-1}
function Equivalent_Keys (Left, Right : Key_Type)
return Boolean
is (
not ((Left < Right)
or (Right < Left)));
{
AI05-0212-1}
{
AI12-0111-1}
{
AI12-0112-1}
{
AI12-0212-1}
{
AI12-0339-1}
{
AI12-0399-1}
type Map
is tagged private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Iterator_View => Stable.Map,
Aggregate => (Empty => Empty,
Add_Named => Insert),
Stable_Properties => (Length,
Tampering_With_Cursors_Prohibited,
Tampering_With_Elements_Prohibited),
Default_Initial_Condition =>
Length (Map) = 0
and then
(
not Tampering_With_Cursors_Prohibited (Map))
and then
(
not Tampering_With_Elements_Prohibited (Map)),
Preelaborable_Initialization;
{
AI12-0399-1}
type Cursor
is private
with Preelaborable_Initialization;
Empty_Map :
constant Map;
No_Element :
constant Cursor;
{
AI05-0212-1}
{
AI12-0112-1}
function Has_Element (Position : Cursor)
return Boolean
with Nonblocking, Global =>
in all, Use_Formal =>
null;
{
AI12-0112-1}
function Has_Element (Container : Map; Position : Cursor)
return Boolean
with Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI05-0212-1}
package Map_Iterator_Interfaces
is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
function "=" (Left, Right : Map) return Boolean;
{
AI12-0112-1}
function Tampering_With_Cursors_Prohibited
(Container : Map)
return Boolean
with Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI12-0112-1}
function Tampering_With_Elements_Prohibited
(Container : Map)
return Boolean
with Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI12-0339-1}
function Empty
return Map
is (Empty_Map)
with Post =>
not Tampering_With_Elements_Prohibited (Empty'Result)
and then
not Tampering_With_Cursors_Prohibited (Empty'Result)
and then
Length (Empty'Result) = 0;
{
AI12-0112-1}
function Length (Container : Map)
return Count_Type
with Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI12-0112-1}
function Is_Empty (Container : Map)
return Boolean
with Nonblocking, Global =>
null, Use_Formal =>
null,
Post => Is_Empty'Result = (Length (Container) = 0);
{
AI12-0112-1}
procedure Clear (Container :
in out Map)
with Pre =>
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Length (Container) = 0;
{
AI12-0112-1}
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;
{
AI12-0112-1}
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;
{
AI12-0112-1}
function Element (Position : Cursor)
return Element_Type
with Pre => Position /= No_Element
or else raise Constraint_Error,
Nonblocking, Global =>
null, Use_Formal => Element_Type;
{
AI12-0112-1}
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;
{
AI12-0112-1}
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);
{
AI12-0112-1}
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;
{
AI12-0112-1}
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);
{
AI12-0112-1}
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);
{
AI05-0212-1}
{
AI12-0112-1}
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);
{
AI05-0212-1}
{
AI12-0112-1}
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);
{
AI05-0212-1}
{
AI12-0112-1}
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;
{
AI05-0212-1}
{
AI12-0112-1}
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;
{
AI05-0212-1}
{
AI12-0112-1}
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;
{
AI05-0212-1}
{
AI12-0112-1}
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;
{
AI05-0001-1}
{
AI12-0112-1}
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);
{
AI05-0001-1}
{
AI12-0112-1}
function Copy (Source : Map)
return Map
with Post =>
Length (Copy'Result) = Length (Source)
and then
not Tampering_With_Elements_Prohibited (Copy'Result)
and then
not Tampering_With_Cursors_Prohibited (Copy'Result);
{
AI12-0112-1}
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);
{
AI12-0112-1}
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));
{
AI12-0112-1}
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));
{
AI12-0112-1}
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;
{
AI12-0112-1}
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);
{
AI12-0112-1}
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;
{
AI12-0112-1}
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);
{
AI12-0112-1}
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;
{
AI12-0112-1}
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;
{
AI12-0112-1}
procedure Delete_First (Container :
in out Map)
with Pre =>
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => (
declare
Original_Length :
constant Count_Type :=
Length (Container)'Old;
begin
(
if Original_Length = 0
then Length (Container) = 0
else Length (Container) = Original_Length - 1));
{
AI12-0112-1}
procedure Delete_Last (Container :
in out Map)
with Pre =>
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => (
declare
Original_Length :
constant Count_Type :=
Length (Container)'Old;
begin
(
if Original_Length = 0
then Length (Container) = 0
else Length (Container) = Original_Length - 1));
{
AI12-0112-1}
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);
{
AI12-0112-1}
function First_Element (Container : Map)
return Element_Type
with Pre => (
not Is_Empty (Container)
or else raise Constraint_Error);
{
AI12-0112-1}
function First_Key (Container : Map)
return Key_Type
with Pre => (
not Is_Empty (Container)
or else raise Constraint_Error);
{
AI12-0112-1}
function Last (Container : Map)
return Cursor
with Nonblocking, Global =>
null, Use_Formal =>
null,
Post => (
if not Is_Empty (Container)
then Has_Element (Container, Last'Result)
else Last'Result = No_Element);
{
AI12-0112-1}
function Last_Element (Container : Map)
return Element_Type
with Pre => (
not Is_Empty (Container)
or else raise Constraint_Error);
{
AI12-0112-1}
function Last_Key (Container : Map)
return Key_Type
with Pre => (
not Is_Empty (Container)
or else raise Constraint_Error);
{
AI12-0112-1}
function Next (Position : Cursor)
return Cursor
with Nonblocking, Global =>
in all, Use_Formal =>
null,
Post => (
if Position = No_Element
then Next'Result = No_Element);
{
AI12-0112-1}
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));
{
AI12-0112-1}
procedure Next (Position :
in out Cursor)
with Nonblocking, Global =>
in all, Use_Formal =>
null;
{
AI12-0112-1}
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));
{
AI12-0112-1}
function Previous (Position : Cursor)
return Cursor
with Nonblocking, Global =>
in all, Use_Formal =>
null,
Post => (
if Position = No_Element
then
Previous'Result = No_Element);
{
AI12-0112-1}
function Previous (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
Previous'Result = No_Element
elsif Previous'Result = No_Element
then
Position = First (Container)
else Has_Element (Container, Previous'Result));
{
AI12-0112-1}
procedure Previous (Position :
in out Cursor)
with Nonblocking, Global =>
in all, Use_Formal =>
null;
{
AI12-0112-1}
procedure Previous (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));
{
AI12-0112-1}
function Find (Container : Map;
Key : Key_Type)
return Cursor
with Post => (
if Find'Result /= No_Element
then Has_Element (Container, Find'Result));
function Element (Container : Map;
Key : Key_Type)
return Element_Type;
{
AI12-0112-1}
function Floor (Container : Map;
Key : Key_Type)
return Cursor
with Post => (
if Floor'Result /= No_Element
then Has_Element (Container, Floor'Result));
{
AI12-0112-1}
function Ceiling (Container : Map;
Key : Key_Type)
return Cursor
with Post => (
if Ceiling'Result /= No_Element
then Has_Element (Container, Ceiling'Result));
function Contains (Container : Map;
Key : Key_Type)
return Boolean;
{
AI12-0112-1}
function "<" (Left, Right : Cursor)
return Boolean
with Pre => (Left /= No_Element
and then Right /= No_Element)
or else raise Constraint_Error,
Global =>
in all;
{
AI12-0112-1}
function ">" (Left, Right : Cursor)
return Boolean
with Pre => (Left /= No_Element
and then Right /= No_Element)
or else raise Constraint_Error,
Global =>
in all;
{
AI12-0112-1}
function "<" (Left : Cursor; Right : Key_Type)
return Boolean
with Pre => Left /= No_Element
or else raise Constraint_Error,
Global =>
in all;
{
AI12-0112-1}
function ">" (Left : Cursor; Right : Key_Type)
return Boolean
with Pre => Left /= No_Element
or else raise Constraint_Error,
Global =>
in all;
{
AI12-0112-1}
function "<" (Left : Key_Type; Right : Cursor)
return Boolean
with Pre => Right /= No_Element
or else raise Constraint_Error,
Global =>
in all;
{
AI12-0112-1}
function ">" (Left : Key_Type; Right : Cursor)
return Boolean
with Pre => Right /= No_Element
or else raise Constraint_Error,
Global =>
in all;
{
AI12-0112-1}
procedure Iterate
(Container :
in Map;
Process :
not null access procedure (Position :
in Cursor))
with Allows_Exit;
{
AI12-0112-1}
procedure Reverse_Iterate
(Container :
in Map;
Process :
not null access procedure (Position :
in Cursor))
with Allows_Exit;
{
AI05-0212-1}
{
AI12-0112-1}
{
AI12-0266-1}
function Iterate (Container :
in Map)
return Map_Iterator_Interfaces.Parallel_Reversible_Iterator'Class
with Post => Tampering_With_Cursors_Prohibited (Container);
{
AI05-0262-1}
{
AI12-0112-1}
function Iterate (Container :
in Map; Start :
in Cursor)
return Map_Iterator_Interfaces.Reversible_Iterator'Class
with Pre => (Start /= No_Element
or else raise Constraint_Error)
and then
(Has_Element (Container, Start)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);
{
AI12-0111-1}
{
AI12-0339-1}
{
AI12-0399-1}
{
AI12-0407-1}
type Map (Base :
not null access Ordered_Maps.Map)
is
tagged limited private
with Constant_Indexing => Constant_Reference,
Variable_Indexing => Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Stable_Properties => (Length),
Global =>
null,
Default_Initial_Condition => Length (Map) = 0,
Preelaborable_Initialization;
{
AI12-0111-1}
function Has_Element (Position : Cursor)
return Boolean
with Nonblocking, Global =>
in all, Use_Formal =>
null;
{
AI12-0111-1}
package Map_Iterator_Interfaces
is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
{
AI12-0111-1}
procedure Assign (Target :
in out Ordered_Maps.Map;
Source :
in Map)
with Post => Length (Source) = Length (Target);
{
AI12-0111-1}
function Copy (Source : Ordered_Maps.Map)
return Map
with Post => Length (Copy'Result) = Length (Source);
{
AI12-0111-1}
type Constant_Reference_Type
(Element :
not null access constant Element_Type)
is private
with Implicit_Dereference => Element,
Nonblocking, Global =>
null, Use_Formal =>
null,
Default_Initial_Condition => (
raise Program_Error);
{
AI12-0111-1}
type Reference_Type
(Element :
not null access Element_Type)
is private
with Implicit_Dereference => Element,
Nonblocking, Global =>
null, Use_Formal =>
null,
Default_Initial_Condition => (
raise Program_Error);
{
AI12-0111-1}
--
Additional subprograms as described in the text
--
are declared here.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). 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 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 of a
nonempty map is the one whose key is greater than the key of all the
other elements in the map. The
successor of a node is the node
with the smallest key that is larger than the key of the given node.
The
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.
{
AI12-0112-1}
function Copy (Source : Map)
return Map
with Post =>
Length (Copy'Result) = Length (Source)
and then
not Tampering_With_Elements_Prohibited (Copy'Result)
and then
not Tampering_With_Cursors_Prohibited (Copy'Result);
{
AI05-0001-1}
Returns a map whose keys and elements are initialized from the corresponding
keys and elements of Source.
{
AI12-0112-1}
procedure Delete_First (Container :
in out Map)
with Pre =>
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => (
declare
Original_Length :
constant Count_Type :=
Length (Container)'Old;
begin
(
if Original_Length = 0
then Length (Container) = 0
else Length (Container) = Original_Length - 1));
{
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.
{
AI12-0112-1}
procedure Delete_Last (Container :
in out Map)
with Pre =>
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => (
declare
Original_Length :
constant Count_Type :=
Length (Container)'Old;
begin
(
if Original_Length = 0
then Length (Container) = 0
else Length (Container) = Original_Length - 1));
{
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.
{
AI12-0112-1}
function First_Element (Container : Map)
return Element_Type
with Pre => (
not Is_Empty (Container)
or else raise Constraint_Error);
{
AI12-0112-1}
function First_Key (Container : Map)
return Key_Type
with Pre => (
not Is_Empty (Container)
or else raise Constraint_Error);
{
AI12-0112-1}
function Last (Container : Map)
return Cursor
with Nonblocking, Global =>
null, Use_Formal =>
null,
Post => (
if not Is_Empty (Container)
then Has_Element (Container, Last'Result)
else Last'Result = No_Element);
{
AI95-00302-03}
Returns a cursor that designates the last node in Container. If Container
is empty, returns No_Element.
{
AI12-0112-1}
function Last_Element (Container : Map)
return Element_Type
with Pre => (
not Is_Empty (Container)
or else raise Constraint_Error);
{
AI12-0112-1}
function Last_Key (Container : Map)
return Key_Type
with Pre => (
not Is_Empty (Container)
or else raise Constraint_Error);
{
AI12-0112-1}
function Previous (Position : Cursor)
return Cursor
with Nonblocking, Global =>
in all, Use_Formal =>
null,
Post => (
if Position = No_Element
then
Previous'Result = No_Element);
{
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 the one
designated by Position. If Position designates the first element, then
Previous returns No_Element.
function Previous (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
Previous'Result = No_Element
elsif Previous'Result = No_Element then
Position = First (Container)
else Has_Element (Container, Previous'Result));
{
AI12-0112-1}
Returns a cursor designating the predecessor of the node designated by
Position in Container, if any.
{
AI12-0112-1}
procedure Previous (Position :
in out Cursor)
with Nonblocking, Global =>
in all, Use_Formal =>
null;
procedure Previous (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));
{
AI12-0112-1}
Equivalent to Position := Previous (Container, Position).
{
AI12-0112-1}
function Floor (Container : Map;
Key : Key_Type)
return Cursor
with Post => (
if Floor'Result /= No_Element
then Has_Element (Container, Floor'Result));
{
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.
{
AI12-0112-1}
function Ceiling (Container : Map;
Key : Key_Type)
return Cursor
with Post => (
if Ceiling'Result /= No_Element
then Has_Element (Container, Ceiling'Result));
{
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.
{
AI12-0112-1}
function "<" (Left, Right : Cursor)
return Boolean
with Pre => (Left /= No_Element
and then Right /= No_Element)
or else raise Constraint_Error,
Global =>
in all;
{
AI12-0112-1}
function ">" (Left, Right : Cursor)
return Boolean
with Pre => (Left /= No_Element
and then Right /= No_Element)
or else raise Constraint_Error,
Global =>
in all;
{
AI12-0112-1}
function "<" (Left : Cursor; Right : Key_Type)
return Boolean
with Pre => Left /= No_Element
or else raise Constraint_Error,
Global =>
in all;
{
AI12-0112-1}
function ">" (Left : Cursor; Right : Key_Type)
return Boolean
with Pre => Left /= No_Element
or else raise Constraint_Error,
Global =>
in all;
{
AI12-0112-1}
function "<" (Left : Key_Type; Right : Cursor)
return Boolean
with Pre => Right /= No_Element
or else raise Constraint_Error,
Global =>
in all;
{
AI12-0112-1}
function ">" (Left : Key_Type; Right : Cursor)
return Boolean
with Pre => Right /= No_Element
or else raise Constraint_Error,
Global =>
in all;
{
AI12-0112-1}
procedure Reverse_Iterate
(Container :
in Map;
Process :
not null access procedure (Position :
in Cursor))
with Allows_Exit;
{
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.
{
AI12-0112-1}
{
AI12-0266-1}
function Iterate (Container :
in Map)
return Map_Iterator_Interfaces.Parallel_Reversible_Iterator'Class
with Post => Tampering_With_Cursors_Prohibited (Container);
{
AI05-0212-1}
{
AI05-0265-1}
{
AI05-0269-1}
{
AI12-0266-1}
Iterate returns an 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,
and processing all nodes concurrently when used as a parallel 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
with Pre => (Start /= No_Element
or else raise Constraint_Error) and then
(Has_Element (Container, Start)
or else raise Program_Error),
Post => Tampering_With_Cursors_Prohibited (Container);
{
AI05-0262-1}
{
AI05-0265-1}
{
AI05-0269-1}
{
AI12-0112-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 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.
Incompatibilities With Ada 2012
{
AI12-0111-1}
{
AI12-0112-1}
{
AI12-0339-1}
A number of new subprograms, types, and even a nested
package were added to Containers.Ordered_Maps to better support contracts
and stable views. Therefore, a use clause conflict is possible; see the
introduction of
Annex A for more on this topic.
Extensions to Ada 2012
{
AI12-0212-1}
Maps now support named container aggregates, so
aggregate
syntax can be used to create Maps.
{
AI12-0266-1}
The iterator for the entire container now can return a parallel iterator
which can be used to process the container in parallel.
Wording Changes from Ada 2012
{
AI12-0112-1}
Added contracts to this container. This includes describing some of the
semantics with pre- and postconditions, rather than English text. Note
that the preconditions can be Suppressed (see
11.5).
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
