The Generic Package Containers.Hashed

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);

��type�Set�is�tagged�private
��with�Constant_Indexing�=>�Constant_Reference,
��Default_Iterator��=>�Iterate,
��Iterator_Element��=>�Element_Type;
��pragma�Preelaborable_Initialization(Set);

��type�Cursor�is�private;
��pragma�Preelaborable_Initialization(Cursor);

��Empty_Set�:�constant�Set;

��No_Element�:�constant�Cursor;

��function�Has_Element�(Position�:�Cursor)�return�Boolean;

��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;

��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));

��type�Constant_Reference_Type
��(Element�:�not�null�access�constant�Element_Type)�is�private
��with�Implicit_Dereference�=>�Element;

��function�Constant_Reference�(Container�:�aliased�in�Set;
��Position��:�in�Cursor)
��return�Constant_Reference_Type;

��procedure�Assign�(Target�:�in�out�Set;�Source�:�in�Set);

��function�Copy�(Source�:�Set;�Capacity�:�Count_Type�:=�0)�return�Set;

��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;

This paragraph was deleted.

��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));

��function�Iterate�(Container�:�in�Set)
��return�Set_Iterator_Interfaces.Forward_Iterator'Class;

��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));

��type�Reference_Type
��(Element�:�not�null�access�Element_Type)�is�private
��with�Implicit_Dereference�=>�Element;

��function�Reference_Preserving_Key�(Container�:�aliased�in�out�Set;
��Position��:�in�Cursor)
��return�Reference_Type;

��function�Constant_Reference�(Container�:�aliased�in�Set;
��Key��:�in�Key_Type)
��return�Constant_Reference_Type;

��function�Reference_Preserving_Key�(Container�:�aliased�in�out�Set;
��Key��:�in�Key_Type)
��return�Reference_Type;

��end�Generic_Keys;

��...�--�not�specified�by�the�language

end�Ada.Containers.Hashed_Sets;

�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.

�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.

�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.

��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.

�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.

�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�Capacity�(Container�:�Set)�return�Count_Type;

procedure�Reserve_Capacity�(Container�:�in�out�Set;
��Capacity��:�in��Count_Type);

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.

procedure�Clear�(Container�:�in�out�Set);

procedure�Assign�(Target�:�in�out�Set;�Source�:�in�Set);

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;

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.

procedure�Insert�(Container�:�in�out�Set;
��New_Item��:�in��Element_Type;
��Position��:��out�Cursor;
��Inserted��:��out�Boolean);

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;

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;

function�Equivalent_Elements�(Left��:�Cursor;
��Right�:�Element_Type)�return�Boolean;

function�Equivalent_Elements�(Left��:�Element_Type;
��Right�:�Cursor)�return�Boolean;

function�Iterate�(Container�:�in�Set)
��return�Set_Iterator_Interfaces.Forward_Iterator'Class;

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. 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.

�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.

�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

�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).�

A.18.8 The Generic Package Containers.Hashed_Sets

Static Semantics

Implementation Advice