A.18.8 The Generic Package Containers.Hashed_Sets
Static Semantics
{
AI95-00302-03}
The generic library package Containers.Hashed_Sets has the following
declaration:
{
AI05-0084-1}
{
AI05-0212-1}
{
AI12-0112-1}
with Ada.Iterator_Interfaces;
generic
type Element_Type
is private;
with function Hash (Element : Element_Type)
return Hash_Type;
with function Equivalent_Elements (Left, Right : Element_Type)
return Boolean;
with function "=" (Left, Right : Element_Type)
return Boolean
is <>;
package Ada.Containers.Hashed_Sets
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).
{
AI05-0212-1}
{
AI12-0111-1}
{
AI12-0112-1}
{
AI12-0212-1}
{
AI12-0339-1}
{
AI12-0399-1}
type Set
is tagged private
with Constant_Indexing => Constant_Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Iterator_View => Stable.Set,
Aggregate => (Empty => Empty,
Add_Unnamed => Include),
Stable_Properties => (Length,
Tampering_With_Cursors_Prohibited),
Default_Initial_Condition =>
Length (Set) = 0
and then
(
not Tampering_With_Cursors_Prohibited (Set)),
Preelaborable_Initialization;
Discussion: {
AI12-0112-1}
Unlike a Vector, the Stable_Properties of a Hashed_Set do not include
the Capacity. If we had included it, some of the otherwise shared definitions
would need different postconditions for Hashed_Sets and Ordered_Sets.
If we were starting these containers from scratch, we probably would
have approached the sharing of definitions differently so that we could
avoid issues like this, but a major reorganization of this existing material
would be too much change.
{
AI12-0399-1}
type Cursor
is private
with Preelaborable_Initialization;
Empty_Set :
constant Set;
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 : Set; Position : Cursor)
return Boolean
with Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI05-0212-1}
package Set_Iterator_Interfaces
is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
function "=" (Left, Right : Set) return Boolean;
function Equivalent_Sets (Left, Right : Set)
return Boolean;
{
AI12-0112-1}
function Tampering_With_Cursors_Prohibited
(Container : Set)
return Boolean
with Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI12-0339-1}
function Empty (Capacity : Count_Type :=
implementation-defined)
return Set
with Post =>
Capacity (Empty'Result) >= Capacity
and then
not Tampering_With_Cursors_Prohibited (Empty'Result)
and then
Length (Empty'Result) = 0;
{
AI12-0112-1}
function To_Set (New_Item : Element_Type)
return Set
with Post => Length (To_Set'Result) = 1
and then
not Tampering_with_Cursors_Prohibited (To_Set'Result);
{
AI12-0112-1}
function Capacity (Container : Set)
return Count_Type
with Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI12-0112-1}
procedure Reserve_Capacity (Container :
in out Set;
Capacity :
in Count_Type)
with Pre =>
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Container.Capacity >= Capacity;
{
AI12-0112-1}
function Length (Container : Set)
return Count_Type
with Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI12-0112-1}
function Is_Empty (Container : Set)
return Boolean
with Nonblocking, Global =>
null, Use_Formal =>
null,
Post => Is_Empty'Result = (Length (Container) = 0);
{
AI12-0112-1}
procedure Clear (Container :
in out Set)
with Pre =>
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Capacity (Container) = Capacity (Container)'Old
and then
Length (Container) = 0;
{
AI12-0112-1}
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;
{
AI12-0112-1}
function Element (Container : Set;
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 Set;
Position :
in Cursor;
New_item :
in Element_Type)
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);
{
AI12-0112-1}
procedure Query_Element
(Position :
in Cursor;
Process :
not null access procedure (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 Set;
Position :
in Cursor;
Process :
not null access procedure (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);
{
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}
function Constant_Reference (Container :
aliased in Set;
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-0001-1}
{
AI12-0112-1}
procedure Assign (Target :
in out Set; Source :
in Set)
with Pre =>
not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error,
Post => Length (Source) = Length (Target)
and then
Capacity (Target) >= Length (Source);
{
AI05-0001-1}
{
AI12-0112-1}
function Copy (Source : Set; Capacity : Count_Type := 0)
return Set
with Pre => Capacity = 0
or else Capacity >= Length (Source)
or else raise Capacity_Error,
Post =>
Length (Copy'Result) = Length (Source)
and then
not Tampering_With_Cursors_Prohibited (Copy'Result)
and then
Copy'Result.Capacity = (
if Capacity = 0
then
Length (Source)
else Capacity);
{
AI12-0112-1}
procedure Move (Target :
in out Set;
Source :
in out Set)
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 Set;
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))
and then
Capacity (Container) >= Length (Container);
{
AI12-0112-1}
procedure Insert (Container :
in out Set;
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
and then
Capacity (Container) >= Length (Container);
{
AI12-0112-1}
procedure Include (Container :
in out Set;
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)
and then
Capacity (Container) >= Length (Container);
{
AI12-0112-1}
procedure Replace (Container :
in out Set;
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 Set;
Item :
in Element_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 Set;
Item :
in Element_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 Set;
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 Union (Target :
in out Set;
Source :
in Set)
with Pre =>
not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error,
Post => Length (Target) <= Length (Target)'Old + Length (Source);
{
AI12-0112-1}
function Union (Left, Right : Set)
return Set
with Post => Length (Union'Result) <=
Length (Left) + Length (Right)
and then
not Tampering_With_Cursors_Prohibited (Union'Result);
function "or" (Left, Right : Set) return Set renames Union;
{
AI12-0112-1}
procedure Intersection (Target :
in out Set;
Source :
in Set)
with Pre =>
not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error,
Post => Length (Target) <= Length (Target)'Old + Length (Source);
{
AI12-0112-1}
function Intersection (Left, Right : Set)
return Set
with Post =>
Length (Intersection'Result) <=
Length (Left) + Length (Right)
and then
not Tampering_With_Cursors_Prohibited (Intersection'Result);
function "and" (Left, Right : Set) return Set renames Intersection;
{
AI12-0112-1}
procedure Difference (Target :
in out Set;
Source :
in Set)
with Pre =>
not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error,
Post => Length (Target) <= Length (Target)'Old + Length (Source);
{
AI12-0112-1}
function Difference (Left, Right : Set)
return Set
with Post =>
Length (Difference'Result) <=
Length (Left) + Length (Right)
and then
not Tampering_With_Cursors_Prohibited (Difference'Result);
function "-" (Left, Right : Set) return Set renames Difference;
{
AI12-0112-1}
procedure Symmetric_Difference (Target :
in out Set;
Source :
in Set)
with Pre =>
not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error,
Post => Length (Target) <= Length (Target)'Old + Length (Source);
{
AI12-0112-1}
function Symmetric_Difference (Left, Right : Set)
return Set
with Post =>
Length (Symmetric_Difference'Result) <=
Length (Left) + Length (Right)
and then
not Tampering_With_Cursors_Prohibited (
Symmetric_Difference'Result);
function "xor" (Left, Right : Set) return Set
renames Symmetric_Difference;
function Overlap (Left, Right : Set)
return Boolean;
function Is_Subset (Subset : Set;
Of_Set : Set)
return Boolean;
{
AI12-0112-1}
function First (Container : Set)
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 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 : Set;
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 Set;
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 : Set;
Item : Element_Type)
return Cursor
with Post => (
if Find'Result /= No_Element
then Has_Element (Container, Find'Result));
function Contains (Container : Set;
Item : Element_Type)
return Boolean;
{
AI12-0112-1}
function Equivalent_Elements (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 Equivalent_Elements (Left : Cursor;
Right : Element_Type)
return Boolean
with Pre => Left /= No_Element
or else raise Constraint_Error,
Global =>
in all;
{
AI12-0112-1}
function Equivalent_Elements (Left : Element_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 Set;
Process :
not null access procedure (Position :
in Cursor))
with Allows_Exit;
{
AI05-0212-1}
{
AI12-0112-1}
{
AI12-0266-1}
function Iterate (Container :
in Set)
return Set_Iterator_Interfaces.Parallel_Iterator'Class
with Post => Tampering_With_Cursors_Prohibited (Container);
{
AI12-0112-1}
generic
type Key_Type (<>)
is private;
with function Key (Element : Element_Type)
return Key_Type;
with function Hash (Key : Key_Type)
return Hash_Type;
with function Equivalent_Keys (Left, Right : Key_Type)
return Boolean;
package Generic_Keys
with Nonblocking, Global =>
null is{
AI12-0112-1}
function Key (Position : Cursor)
return Key_Type
with Pre => Position /= No_Element
or else raise Constraint_Error,
Global =>
in all;
{
AI12-0112-1}
function Key (Container : Set;
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);
function Element (Container : Set;
Key : Key_Type)
return Element_Type;
{
AI12-0112-1}
procedure Replace (Container :
in out Set;
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 Set;
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 Set;
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}
function Find (Container : Set;
Key : Key_Type)
return Cursor
with Post => (
if Find'Result = No_Element
then Has_Element (Container, Find'Result));
function Contains (Container : Set;
Key : Key_Type)
return Boolean;
{
AI12-0112-1}
procedure Update_Element_Preserving_Key
(Container :
in out Set;
Position :
in Cursor;
Process :
not null access procedure
(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 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 Reference_Preserving_Key (Container :
aliased in out Set;
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);
{
AI05-0212-1}
{
AI12-0112-1}
function Constant_Reference (Container :
aliased in Set;
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);
{
AI05-0212-1}
{
AI12-0112-1}
function Reference_Preserving_Key (Container :
aliased in out Set;
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);
end Generic_Keys;
{
AI12-0111-1}
{
AI12-0339-1}
{
AI12-0399-1}
{
AI12-0407-1}
type Set (Base :
not null access Hashed_Sets.Set)
is
tagged limited private
with Constant_Indexing => Constant_Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type,
Stable_Properties => (Length),
Global =>
null,
Default_Initial_Condition => Length (Set) = 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 Set_Iterator_Interfaces
is new
Ada.Iterator_Interfaces (Cursor, Has_Element);
{
AI12-0111-1}
procedure Assign (Target :
in out Hashed_Sets.Set;
Source :
in Set)
with Post => Length (Source) = Length (Target);
{
AI12-0111-1}
function Copy (Source : Hashed_Sets.Set)
return Set
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}
--
Additional subprograms as described in the text
--
are declared here.private
... -- not specified by the language
end Ada.Containers.Hashed_Sets;
{
AI95-00302-03}
An object of type Set contains an expandable hash
table, which is used to provide direct access to elements. The
capacity
of an object of type Set is the maximum number of elements that can be
inserted into the hash table prior to it being automatically expanded.
{
AI95-00302-03}
Two elements
E1 and
E2 are defined
to be
equivalent if Equivalent_Elements (
E1,
E2)
returns True.
{
AI95-00302-03}
The actual function for the generic formal function Hash is expected
to return the same value each time it is called with a particular element
value. For any two equivalent elements, the actual for Hash is expected
to return the same value. If the actual for Hash behaves in some other
manner, the behavior of this package is unspecified. Which subprograms
of this package call Hash, and how many times they call it, is unspecified.
{
AI95-00302-03}
The actual function for the generic formal function Equivalent_Elements
is expected to return the same value each time it is called with a particular
pair of Element values. It should define an equivalence relationship,
that is, be reflexive, symmetric, and transitive. If the actual for Equivalent_Elements
behaves in some other manner, the behavior of this package is unspecified.
Which subprograms of this package call Equivalent_Elements, and how many
times they call it, is unspecified.
{
AI05-0044-1}
If the actual function for the generic formal function "="
returns True for any pair of nonequivalent elements, then the behavior
of the container function "=" is unspecified.
{
AI95-00302-03}
If the value of an element stored in a set is changed other than by an
operation in this package such that at least one of Hash or Equivalent_Elements
give different results, the behavior of this package is unspecified.
Discussion: See
A.18.5,
“
The Generic Package Containers.Hashed_Maps”
for a suggested implementation, and for justification of the restrictions
regarding Hash and Equivalent_Elements. Note that sets only need to store
elements, not key/element pairs.
{
AI95-00302-03}
Which elements
are the first element and the last element of a set, and which element
is the successor of a given element, are unspecified, other than the
general semantics described in
A.18.7.
function Empty (Capacity : Count_Type := implementation-defined)
return Set
with Post =>
Capacity (Empty'Result) >= Capacity and then
not Tampering_With_Cursors_Prohibited (Empty'Result) and then
Length (Empty'Result) = 0;
{
AI12-0112-1}
function Capacity (Container : Set)
return Count_Type
with Nonblocking, Global =>
null, Use_Formal =>
null;
{
AI12-0112-1}
procedure Reserve_Capacity (Container :
in out Set;
Capacity :
in Count_Type)
with Pre =>
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Container.Capacity >= Capacity;
{
AI95-00302-03}
Reserve_Capacity allocates a new hash table such that the length of the
resulting set can become at least the value Capacity without requiring
an additional call to Reserve_Capacity, and is large enough to hold the
current length of Container. Reserve_Capacity then rehashes the elements
in Container onto the new hash table. It replaces the old hash table
with the new hash table, and then deallocates the old hash table. Any
exception raised during allocation is propagated and Container is not
modified.
Reason: Reserve_Capacity
tampers with the cursors, as rehashing probably will change the relationships
of the elements in Container.
{
AI12-0112-1}
procedure Clear (Container :
in out Set)
with Pre =>
not Tampering_With_Cursors_Prohibited (Container)
or else raise Program_Error,
Post => Capacity (Container) = Capacity (Container)'Old
and then
Length (Container) = 0;
{
AI95-00302-03}
In addition to the semantics described in
A.18.7,
Clear does not affect the capacity of Container.
{
AI12-0112-1}
procedure Assign (Target :
in out Set; Source :
in Set)
with Pre =>
not Tampering_With_Cursors_Prohibited (Target)
or else raise Program_Error,
Post => Length (Source) = Length (Target)
and then
Capacity (Target) >= Length (Source);
{
AI05-0001-1}
{
AI05-0248-1}
In addition to the semantics described in
A.18.7,
if the length of Source is greater than the capacity of Target, Reserve_Capacity
(Target, Length (Source)) is called before assigning any elements.
function Copy (Source : Set; Capacity : Count_Type := 0)
return Set
with Pre => Capacity = 0 or else Capacity >= Length (Source)
or else raise Capacity_Error,
Post =>
Length (Copy'Result) = Length (Source) and then
not Tampering_With_Cursors_Prohibited (Copy'Result) and then
Copy'Result.Capacity = (if Capacity = 0 then
Length (Source) else Capacity);
{
AI12-0112-1}
procedure Insert (Container :
in out Set;
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))
and then
Capacity (Container) >= Length (Container);
{
AI95-00302-03}
In addition to the semantics described in
A.18.7,
if Length (Container) equals Capacity (Container), then Insert first
calls Reserve_Capacity to increase the capacity of Container to some
larger value.
function First (Container : Set) return Cursor;
{
AI95-00302-03}
If Length (Container) = 0, then First returns No_Element. Otherwise,
First returns a cursor that designates the first hashed element in Container.
{
AI12-0112-1}
function Equivalent_Elements (Left, Right : Cursor)
return Boolean
with Pre => (Left /= No_Element
and then Right /= No_Element)
or else raise Constraint_Error,
Global =>
in all;
{
AI95-00302-03}
Equivalent to Equivalent_Elements (Element (Left), Element (Right)).
{
AI12-0112-1}
function Equivalent_Elements (Left : Cursor;
Right : Element_Type)
return Boolean
with Pre => Left /= No_Element
or else raise Constraint_Error,
Global =>
in all;
{
AI95-00302-03}
Equivalent to Equivalent_Elements (Element (Left), Right).
{
AI12-0112-1}
function Equivalent_Elements (Left : Element_Type;
Right : Cursor)
return Boolean
with Pre => Right /= No_Element
or else raise Constraint_Error,
Global =>
in all;
{
AI95-00302-03}
Equivalent to Equivalent_Elements (Left, Element (Right)).
{
AI12-0112-1}
{
AI12-0266-1}
function Iterate (Container :
in Set)
return Set_Iterator_Interfaces.Parallel_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 element in Container, starting with the first element
and moving the cursor according to the successor relation when used as
a forward 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.
{
AI95-00302-03}
For any element
E, the actual function for the generic formal
function Generic_Keys.Hash is expected to be such that Hash (
E)
= Generic_Keys.Hash (Key (
E)). If the actuals for Key or Generic_Keys.Hash
behave in some other manner, the behavior of Generic_Keys is unspecified.
Which subprograms of Generic_Keys call Generic_Keys.Hash, and how many
times they call it, is unspecified.
{
AI95-00302-03}
For any two elements
E1 and
E2, the boolean values Equivalent_Elements
(
E1,
E2) and Equivalent_Keys (Key (
E1), Key (
E2))
are expected to be equal. If the actuals for Key or Equivalent_Keys behave
in some other manner, the behavior of Generic_Keys is unspecified. Which
subprograms of Generic_Keys call Equivalent_Keys, and how many times
they call it, is unspecified.
Implementation Advice
{
AI95-00302-03}
If
N is the length of a set, the average time complexity of the
subprograms Insert, Include, Replace, Delete, Exclude, and Find that
take an element parameter should be
O(log
N). The average
time complexity of the subprograms that take a cursor parameter should
be
O(1). The average time complexity of Reserve_Capacity should
be
O(
N).
Implementation Advice: The average time
complexity of the Insert, Include, Replace, Delete, Exclude, and Find
operations of Containers.Hashed_Sets that take an element parameter should
be O(log N). The average time complexity of the subprograms
of Containers.Hashed_Sets that take a cursor parameter should be O(1).
The average time complexity of Containers.Hashed_Sets.Reserve_Capacity
should be O(N).
Extensions to Ada 95
{
AI95-00302-03}
The generic package Containers.Hashed_Sets is new.
Incompatibilities With Ada 2005
{
AI05-0001-1}
Subprograms Assign and Copy are added to Containers.Hashed_Sets.
If an instance of Containers.Hashed_Sets is referenced in a
use_clause,
and an entity
E with the same
defining_identifier
as a new entity in Containers.Hashed_Sets 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 hashed
set containers more convenient to use.
Wording Changes from Ada 2005
{
AI05-0044-1}
Correction: Added wording to require the formal function be such
that equal elements are also equivalent.
{
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.Hashed_Sets 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}
Sets now support positional container aggregates,
so
aggregate
syntax can be used to create Sets.
{
AI12-0266-1}
The iterator for the 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
