A.18.8 The Package Containers.Hashed_Sets
Static Semantics
{
AI95-00302-03}
The generic library package Containers.Hashed_Sets has the following
declaration:
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);
type Set
is tagged private;
pragma Preelaborable_Initialization(Set);
type Cursor
is private;
pragma Preelaborable_Initialization(Cursor);
Empty_Set :
constant Set;
No_Element :
constant Cursor;
function "=" (Left, Right : Set) return Boolean;
function Equivalent_Sets (Left, Right : Set)
return Boolean;
function To_Set (New_Item : Element_Type)
return Set;
function Capacity (Container : Set)
return Count_Type;
procedure Reserve_Capacity (Container :
in out Set;
Capacity :
in Count_Type);
function Length (Container : Set)
return Count_Type;
function Is_Empty (Container : Set)
return Boolean;
procedure Clear (Container :
in out Set);
function Element (Position : Cursor)
return Element_Type;
procedure Replace_Element (Container :
in out Set;
Position :
in Cursor;
New_Item :
in Element_Type);
procedure Query_Element
(Position :
in Cursor;
Process :
not null access procedure (Element :
in Element_Type));
procedure Move (Target :
in out Set;
Source :
in out Set);
procedure Insert (Container :
in out Set;
New_Item :
in Element_Type;
Position :
out Cursor;
Inserted :
out Boolean);
procedure Insert (Container :
in out Set;
New_Item :
in Element_Type);
procedure Include (Container :
in out Set;
New_Item :
in Element_Type);
procedure Replace (Container :
in out Set;
New_Item :
in Element_Type);
procedure Exclude (Container :
in out Set;
Item :
in Element_Type);
procedure Delete (Container :
in out Set;
Item :
in Element_Type);
procedure Delete (Container :
in out Set;
Position :
in out Cursor);
procedure Union (Target :
in out Set;
Source :
in Set);
function Union (Left, Right : Set)
return Set;
function "or" (Left, Right : Set) return Set renames Union;
procedure Intersection (Target :
in out Set;
Source :
in Set);
function Intersection (Left, Right : Set)
return Set;
function "and" (Left, Right : Set) return Set renames Intersection;
procedure Difference (Target :
in out Set;
Source :
in Set);
function Difference (Left, Right : Set)
return Set;
function "-" (Left, Right : Set) return Set renames Difference;
procedure Symmetric_Difference (Target :
in out Set;
Source :
in Set);
function Symmetric_Difference (Left, Right : Set)
return Set;
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;
function First (Container : Set)
return Cursor;
function Next (Position : Cursor)
return Cursor;
procedure Next (Position :
in out Cursor);
function Find (Container : Set;
Item : Element_Type)
return Cursor;
function Contains (Container : Set;
Item : Element_Type)
return Boolean;
function Has_Element (Position : Cursor)
return Boolean;
function Equivalent_Elements (Left, Right : Cursor)
return Boolean;
function Equivalent_Elements (Left : Cursor;
Right : Element_Type)
return Boolean;
function Equivalent_Elements (Left : Element_Type;
Right : Cursor)
return Boolean;
procedure Iterate
(Container :
in Set;
Process :
not null access procedure (Position :
in Cursor));
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
function Key (Position : Cursor)
return Key_Type;
function Element (Container : Set;
Key : Key_Type)
return Element_Type;
procedure Replace (Container :
in out Set;
Key :
in Key_Type;
New_Item :
in Element_Type);
procedure Exclude (Container :
in out Set;
Key :
in Key_Type);
procedure Delete (Container :
in out Set;
Key :
in Key_Type);
function Find (Container : Set;
Key : Key_Type)
return Cursor;
function Contains (Container : Set;
Key : Key_Type)
return Boolean;
procedure Update_Element_Preserving_Key
(Container :
in out Set;
Position :
in Cursor;
Process :
not null access procedure
(Element :
in out Element_Type));
end Generic_Keys;
private
... -- not specified by the language
end Ada.Containers.Hashed_Sets;
{
AI95-00302-03}
{capacity (of a hashed set)}
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}
{equivalent element (of a hashed set)}
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.
{unspecified
[partial]} {
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.
{unspecified
[partial]} {
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.
{unspecified
[partial]} Discussion: See
A.18.5,
“
The 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}
{first element (of a hashed set)}
{last element (of
a hashed set)} {successor
element (of a hashed set)} 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.
{unspecified
[partial]} function Capacity (Container : Set) return Count_Type;
procedure Reserve_Capacity (Container : in out Set;
Capacity : in Count_Type);
{
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.
Reserve_Capacity
tampers with the cursors of Container.
Reason: Reserve_Capacity
tampers with the cursors, as rehashing probably will change the relationships
of the elements in Container.
procedure Clear (Container : in out Set);
{
AI95-00302-03}
In addition to the semantics described in
A.18.7,
Clear does not affect the capacity of Container.
procedure Insert (Container : in out Set;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
{
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.
function Equivalent_Elements (Left, Right : Cursor)
return Boolean;
{
AI95-00302-03}
Equivalent to Equivalent_Elements (Element (Left), Element (Right)).
function Equivalent_Elements (Left : Cursor;
Right : Element_Type) return Boolean;
{
AI95-00302-03}
Equivalent to Equivalent_Elements (Element (Left), Right).
function Equivalent_Elements (Left : Element_Type;
Right : Cursor) return Boolean;
{
AI95-00302-03}
Equivalent to Equivalent_Elements (Left, Element (Right)).
{
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.
{unspecified
[partial]} {
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.
{unspecified
[partial]} 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}
{
extensions to Ada 95}
The generic package
Containers.Hashed_Sets is new.
Sponsored by Ada-Europe