A.18.8 The Generic Package Containers.Hashed_Sets
Static Semantics
1/2
{
AI95-00302-03}
The generic library package Containers.Hashed_Sets
has the following declaration: 2/3
{
AI05-0084-1}
{
AI05-0212-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 is
pragma Preelaborate(Hashed_Sets);
pragma Remote_Types(Hashed_Sets);3/3
{
AI05-0212-1}
type Set is tagged private
with Constant_Indexing => Constant_Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type;
pragma Preelaborable_Initialization(Set);4/2
type Cursor is private;
pragma Preelaborable_Initialization(Cursor);
5/2
Empty_Set : constant Set;
6/2
No_Element : constant Cursor;
6.1/3
{
AI05-0212-1}
function Has_Element (Position : Cursor) return Boolean;6.2/3
{
AI05-0212-1}
package Set_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);7/2
function "=" (Left, Right : Set) return Boolean;
8/2
function Equivalent_Sets (Left, Right : Set) return Boolean;
9/2
function To_Set (New_Item : Element_Type) return Set;
10/2
function Capacity (Container : Set) return Count_Type;
11/2
procedure Reserve_Capacity (Container : in out Set;
Capacity : in Count_Type);
12/2
function Length (Container : Set) return Count_Type;
13/2
function Is_Empty (Container : Set) return Boolean;
14/2
procedure Clear (Container : in out Set);
15/2
function Element (Position : Cursor) return Element_Type;
16/2
procedure Replace_Element (Container : in out Set;
Position : in Cursor;
New_Item : in Element_Type);
17/2
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
17.1/3
{
AI05-0212-1}
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;17.2/3
{
AI05-0212-1}
function Constant_Reference (Container : aliased in Set;
Position : in Cursor)
return Constant_Reference_Type;17.3/3
{
AI05-0001-1}
procedure Assign (Target : in out Set; Source : in Set);17.4/3
{
AI05-0001-1}
function Copy (Source : Set; Capacity : Count_Type := 0) return Set;18/2
procedure Move (Target : in out Set;
Source : in out Set);
19/2
procedure Insert (Container : in out Set;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
20/2
procedure Insert (Container : in out Set;
New_Item : in Element_Type);
21/2
procedure Include (Container : in out Set;
New_Item : in Element_Type);
22/2
procedure Replace (Container : in out Set;
New_Item : in Element_Type);
23/2
procedure Exclude (Container : in out Set;
Item : in Element_Type);
24/2
procedure Delete (Container : in out Set;
Item : in Element_Type);
25/2
procedure Delete (Container : in out Set;
Position : in out Cursor);
26/2
procedure Union (Target : in out Set;
Source : in Set);
27/2
function Union (Left, Right : Set) return Set;
28/2
function "or" (Left, Right : Set) return Set renames Union;
29/2
procedure Intersection (Target : in out Set;
Source : in Set);
30/2
function Intersection (Left, Right : Set) return Set;
31/2
function "and" (Left, Right : Set) return Set renames Intersection;
32/2
procedure Difference (Target : in out Set;
Source : in Set);
33/2
function Difference (Left, Right : Set) return Set;
34/2
function "-" (Left, Right : Set) return Set renames Difference;
35/2
procedure Symmetric_Difference (Target : in out Set;
Source : in Set);
36/2
function Symmetric_Difference (Left, Right : Set) return Set;
37/2
function "xor" (Left, Right : Set) return Set
renames Symmetric_Difference;
38/2
function Overlap (Left, Right : Set) return Boolean;
39/2
function Is_Subset (Subset : Set;
Of_Set : Set) return Boolean;
40/2
function First (Container : Set) return Cursor;
41/2
function Next (Position : Cursor) return Cursor;
42/2
procedure Next (Position : in out Cursor);
43/2
function Find (Container : Set;
Item : Element_Type) return Cursor;
44/2
function Contains (Container : Set;
Item : Element_Type) return Boolean;
45/3
This paragraph
was deleted. {
AI05-0212-1}
function Has_Element (Position : Cursor) return Boolean;
46/2
function Equivalent_Elements (Left, Right : Cursor)
return Boolean;
47/2
function Equivalent_Elements (Left : Cursor;
Right : Element_Type)
return Boolean;
48/2
function Equivalent_Elements (Left : Element_Type;
Right : Cursor)
return Boolean;
49/2
procedure Iterate
(Container : in Set;
Process : not null access procedure (Position : in Cursor));
49.1/3
{
AI05-0212-1}
function Iterate (Container : in Set)
return Set_Iterator_Interfaces.Forward_Iterator'Class;50/2
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 is
51/2
function Key (Position : Cursor) return Key_Type;
52/2
function Element (Container : Set;
Key : Key_Type)
return Element_Type;
53/2
procedure Replace (Container : in out Set;
Key : in Key_Type;
New_Item : in Element_Type);
54/2
procedure Exclude (Container : in out Set;
Key : in Key_Type);
55/2
procedure Delete (Container : in out Set;
Key : in Key_Type);
56/2
function Find (Container : Set;
Key : Key_Type)
return Cursor;
57/2
function Contains (Container : Set;
Key : Key_Type)
return Boolean;
58/2
procedure Update_Element_Preserving_Key
(Container : in out Set;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type));
58.1/3
{
AI05-0212-1}
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;58.2/3
{
AI05-0212-1}
function Reference_Preserving_Key (Container : aliased in out Set;
Position : in Cursor)
return Reference_Type;58.3/3
{
AI05-0212-1}
function Constant_Reference (Container : aliased in Set;
Key : in Key_Type)
return Constant_Reference_Type;58.4/3
{
AI05-0212-1}
function Reference_Preserving_Key (Container : aliased in out Set;
Key : in Key_Type)
return Reference_Type;59/2
end Generic_Keys;
60/2
private
61/2
... -- not specified by the language
62/2
end Ada.Containers.Hashed_Sets;
63/2
{
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.64/2
{
AI95-00302-03}
Two elements E1 and
E2 are defined to be equivalent if Equivalent_Elements
(E1, E2) returns True.65/2
{
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.66/2
{
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.66.1/3
{
AI05-0044-1}
If the actual function for the generic formal function
"=" returns True for any pair of non-equivalent elements, then
the behavior of the container function "=" is unspecified.67/2
{
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.67.a/2
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.
68/2
{
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.69/2
function Capacity (Container : Set) return Count_Type;
70/2
71/2
procedure Reserve_Capacity (Container : in out Set;
Capacity : in Count_Type);
72/2
{
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.73/2
Reserve_Capacity
tampers with the cursors of Container.
73.a/2
Reason:
Reserve_Capacity tampers with the cursors, as rehashing probably
will change the relationships of the elements in Container.
74/2
procedure Clear (Container : in out Set);
75/2
{
AI95-00302-03}
In addition to the semantics described in A.18.7,
Clear does not affect the capacity of Container.75.1/3
procedure Assign (Target : in out Set; Source : in Set);
75.2/3
{
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.75.3/3
function Copy (Source : Set; Capacity : Count_Type := 0) return Set;
75.4/3
{
AI05-0001-1}
Returns a set whose elements are initialized from
the elements of Source. If Capacity is 0, then the set capacity is the
length of Source; if Capacity is equal to or greater than the length
of Source, the set capacity is at least the specified value. Otherwise,
the operation propagates Capacity_Error.76/2
procedure Insert (Container : in out Set;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
77/2
{
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.78/2
function First (Container : Set) return Cursor;
79/2
{
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.80/2
function Equivalent_Elements (Left, Right : Cursor)
return Boolean;
81/2
{
AI95-00302-03}
Equivalent to Equivalent_Elements (Element (Left),
Element (Right)).82/2
function Equivalent_Elements (Left : Cursor;
Right : Element_Type) return Boolean;
83/2
{
AI95-00302-03}
Equivalent to Equivalent_Elements (Element (Left),
Right).84/2
function Equivalent_Elements (Left : Element_Type;
Right : Cursor) return Boolean;
85/2
{
AI95-00302-03}
Equivalent to Equivalent_Elements (Left, Element
(Right)).85.1/3
function Iterate (Container : in Set)
return Set_Iterator_Interfaces.Forward_Iterator'Class;
85.2/3
{
AI05-0212-1}
{
AI05-0265-1}
Iterate returns an iterator object that will generate
a value for the loop parameter designating each element in Container,
starting with the first element and moving the cursor according to the
successor relation. 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.86/2
{
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.87/2
{
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
88/2
{
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). 88.a/2
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).
88.b/2
Extensions to Ada 95
88.c/2
{
AI95-00302-03}
The generic package Containers.Hashed_Sets
is new. Incompatibilities With Ada 2005
88.d/3
{
AI05-0001-1}
Subprograms Assign and Copy
are newly 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
88.e/3
{
AI05-0212-1}
Added iterator and indexing
support to make hashed set containers more convenient to use.
Wording Changes from Ada 2005
88.f/3
{
AI05-0044-1}
Correction: Added wording to require the
formal function be such that equal elements are also equivalent.88.g/3
{
AI05-0084-1}
Correction: Added a pragma Remote_Types
so that containers can be used in distributed programs.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
