Ada Conformity Assessment Authority      Home Conformity Assessment   Test Suite ARGAda Standard
 
Annotated Ada Reference Manual (Ada 202x Draft 22)Legal Information
Contents   Index   References   Search   Previous   Next 

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/5
{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 is
   with Preelaborate, Remote_Types,
        Nonblocking => Element_Type'Nonblocking and Hash'Nonblocking and
                       Equivalent_Elements'Nonblocking and
                       Equal_Element'Nonblocking,
        Global => synchronized in out Ada.Containers.Hashed_Sets &
                  Element_Type'Global & Hash'Global &
                  Equivalent_Elements'Global &
                  Equal_Element'Global is

   pragma Preelaborate(Hashed_Sets);
   pragma Remote_Types(Hashed_Sets);
3/5
{AI05-0212-1} {AI12-0111-1} {AI12-0112-1} {AI12-0212-1} {AI12-0339-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))
;
   pragma Preelaborable_Initialization(Set);
3.a/5
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. 
4/2
   type Cursor is private;
   pragma Preelaborable_Initialization(Cursor);
5/2
   Empty_Set : constant Set;
6/2
   No_Element : constant Cursor;
6.1/5
{AI12-0112-1}    function Equal_Element (Left, Right : Element_Type)
      return Boolean renames "=";
6.2/5
{AI05-0212-1} {AI12-0112-1}    function Has_Element (Position : Cursor) return Boolean
      with Nonblocking, Global => in access Set
;
6.3/5
{AI12-0112-1}    function Has_Element (Container : Set; Position : Cursor)
      return Boolean
      with Nonblocking, Global => null;
6.4/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;
8.1/5
{AI12-0112-1}    function Tampering_With_Cursors_Prohibited
      (Container : Set) return Boolean
      with Nonblocking, Global => null;
8.2/5
{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;
9/5
{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)
;
10/5
{AI12-0112-1}    function Capacity (Container : Set) return Count_Type
      with Nonblocking, Global => null
;
11/5
{AI12-0112-1}    procedure Reserve_Capacity (Container : in out Set;
                               Capacity  : in     Count_Type)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                    then raise Program_Error),
           Post => Container.Capacity >= Capacity
;
12/5
{AI12-0112-1}    function Length (Container : Set) return Count_Type
      with Nonblocking, Global => null
;
13/5
{AI12-0112-1}    function Is_Empty (Container : Set) return Boolean
      with Nonblocking, Global => null,
           Post => Is_Empty'Result = (Length (Container) = 0)
;
14/5
{AI12-0112-1}    procedure Clear (Container : in out Set)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                       then raise Program_Error),
           Post => Capacity (Container) = Capacity (Container)'Old and then
                   Length (Container) = 0
;
15/5
{AI12-0112-1}    function Element (Position : Cursor) return Element_Type
      with Pre  => (if Position = No_Element then raise Constraint_Error),
           Nonblocking => Element_Type'Nonblocking,
           Global => in access Set & Element_Type'Global
;
15.1/5
{AI12-0112-1}    function Element (Container : Set;
                     Position  : Cursor) return Element_Type
      with Pre => (if Position = No_Element then raise Constraint_Error
                   elsif not Has_Element (Container, Position)
                      then raise Program_Error),
           Nonblocking => Element_Type'Nonblocking,
           Global => Element_Type'Global;
16/5
{AI12-0112-1}    procedure Replace_Element (Container : in out Set;
                              Position  : in     Cursor;
                              New_item  : in     Element_Type)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                    then raise Program_Error) and then
                   (if Position = No_Element then raise Constraint_Error
                    elsif not Has_Element (Container, Position)
                       then raise Program_Error)
;
17/5
{AI12-0112-1}    procedure Query_Element
     (Position : in Cursor;
      Process  : not null access procedure (Element : in Element_Type))
      with Pre  => (if Position = No_Element then raise Constraint_Error),
           Global => in access Set & Element_Type'Global
;
17.1/5
{AI12-0112-1}    procedure Query_Element
     (Container : in Set;
      Position  : in Cursor;
      Process   : not null access procedure (Element : in Element_Type))
      with Pre  => (if Position = No_Element then raise Constraint_Error
                    elsif not Has_Element (Container, Position)
                    then raise Program_Error),
           Global => Element_Type'Global;
17.2/5
{AI05-0212-1} {AI12-0112-1}    type Constant_Reference_Type
         (Element : not null access constant Element_Type) is private
      with Implicit_Dereference => Element,
           Global => synchronized in out access Set,
           Nonblocking => True,
           Default_Initial_Condition => (raise Program_Error)
;
17.3/5
{AI05-0212-1} {AI12-0112-1}    function Constant_Reference (Container : aliased in Set;
                                Position  : in Cursor)
      return Constant_Reference_Type
      with Pre  => (if Position = No_Element then raise Constraint_Error
                    elsif not Has_Element (Container, Position)
                       then raise Program_Error),
           Post => Tampering_With_Cursors_Prohibited (Container),
           Nonblocking, Global => null
;
17.4/5
{AI05-0001-1} {AI12-0112-1}    procedure Assign (Target : in out Set; Source : in Set)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Target)
                    then raise Program_Error),
           Post => Length (Source) = Length (Target) and then
                   Capacity (Target) >= Length (Source)
;
17.5/5
{AI05-0001-1} {AI12-0112-1}    function Copy (Source : Set; Capacity : Count_Type := 0)
      return Set
      with Pre  => (if Capacity /= 0 and then Capacity < Length (Source)
                    then 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)
;
18/5
{AI12-0112-1}    procedure Move (Target : in out Set;
                   Source : in out Set)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Target)
                    then raise Program_Error) and then
                   (if Tampering_With_Cursors_Prohibited (Source)
                    then raise Program_Error),
           Post => (if Target = Source then True
                    else
                       Length (Target) = Length (Source'Old) and then
                       Length (Source) = 0)
;
19/5
{AI12-0112-1}    procedure Insert (Container : in out Set;
                     New_Item  : in     Element_Type;
                     Position  :    out Cursor;
                     Inserted  :    out Boolean)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                    then raise Program_Error) and then
                   (if Length (Container) > Count_Type'Last - 1
                    then 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)
;
20/5
{AI12-0112-1}    procedure Insert (Container : in out Set;
                     New_Item  : in     Element_Type)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                    then raise Program_Error) and then
                   (if Length (Container) > Count_Type'Last - 1
                    then raise Constraint_Error),
           Post => Length (Container) = Length (Container)'Old + 1 and then
                   Capacity (Container) >= Length (Container)
;
21/5
{AI12-0112-1}    procedure Include (Container : in out Set;
                      New_Item  : in     Element_Type)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                    then raise Program_Error) and then
                   (if Length (Container) > Count_Type'Last - 1
                    then 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)
;
22/5
{AI12-0112-1}    procedure Replace (Container : in out Set;
                      New_Item  : in     Element_Type)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                    then raise Program_Error),
           Post => Length (Container) = Length (Container)'Old
;
23/5
{AI12-0112-1}    procedure Exclude (Container : in out Set;
                      Item      : in     Element_Type)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                    then raise Program_Error),
           Post => (declare
                      Original_Length : constant Count_Type :=
                         Length (Container)'Old;
                    begin
                      Length (Container) in
                         Original_Length - 1 | Original_Length)
;
24/5
{AI12-0112-1}    procedure Delete (Container : in out Set;
                     Position  : in out Cursor)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                    then raise Program_Error) and then
                   (if Position /= No_Element and then
                       (not Has_Element (Container, Position))
                    then raise Program_Error),
           Post => Length (Container) = Length (Container)'Old - 1 and then
                   Position = No_Element
;
25/2
   procedure Delete (Container : in out Set;
                     Position  : in out Cursor);
26/5
{AI12-0112-1}    procedure Union (Target : in out Set;
                    Source : in     Set)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Target)
                    then raise Program_Error),
           Post => Length (Target) <= Length (Target)'Old + Length (Source)
;
27/5
{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)
;
28/2
   function "or" (Left, Right : Set) return Set renames Union;
29/5
{AI12-0112-1}    procedure Intersection (Target : in out Set;
                           Source : in     Set)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Target)
                    then raise Program_Error),
           Post => Length (Target) <= Length (Target)'Old + Length (Source)
;
30/5
{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)
;
31/2
   function "and" (Left, Right : Set) return Set renames Intersection;
32/5
{AI12-0112-1}    procedure Difference (Target : in out Set;
                         Source : in     Set)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Target)
                    then raise Program_Error),
           Post => Length (Target) <= Length (Target)'Old + Length (Source)
;
33/5
{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)
;
34/2
   function "-" (Left, Right : Set) return Set renames Difference;
35/5
{AI12-0112-1}    procedure Symmetric_Difference (Target : in out Set;
                                   Source : in     Set)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Target)
                    then raise Program_Error),
           Post => Length (Target) <= Length (Target)'Old + Length (Source)
;
36/5
{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)
;
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/5
{AI12-0112-1}    function First (Container : Set) return Cursor
      with Nonblocking, Global => null,
           Post => (if not Is_Empty (Container)
                    then Has_Element (Container, First'Result)
                    else First'Result = No_Element)
;
41/5
{AI12-0112-1}    function Next (Position : Cursor) return Cursor
      with Global => in access Set,
           Nonblocking => True,
           Post => (if Position = No_Element then Next'Result = No_Element
                    else True)
;
41.1/5
{AI12-0112-1}    function Next (Container : Set;
                  Position : Cursor) return Cursor
      with Nonblocking, Global => null,
           Pre  => (if Position /= No_Element and then
                       (not Has_Element (Container, Position))
                    then 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));
42/5
{AI12-0112-1}    procedure Next (Position : in out Cursor)
      with Global => in access Set,
           Nonblocking => True
;
42.1/5
{AI12-0112-1}    procedure Next (Container : in     Set;
                   Position  : in out Cursor)
      with Nonblocking, Global => null,
           Pre  => (if Position /= No_Element and then
                       (not Has_Element (Container, Position))
                    then raise Program_Error),
           Post => (if Position /= No_Element
                    then Has_Element (Container, Position));
43/5
{AI12-0112-1}    function Find (Container : Set;
                  Item      : Element_Type)
      return Cursor
      with Post => (if Find'Result = No_Element then True
                    else Has_Element (Container, Find'Result))
;
44/2
   function Contains (Container : Set;
                      Item      : Element_Type) return Boolean;
45/3
This paragraph was deleted.{AI05-0212-1}
46/5
{AI12-0112-1}    function Equivalent_Elements (Left, Right : Cursor)
      return Boolean
      with Pre    => (if Left = No_Element or else Right = No_Element
                      then raise Constraint_Error),
           Global => in access Set & Ada.Containers.Hashed_Sets'Global
;
47/5
{AI12-0112-1}    function Equivalent_Elements (Left  : Cursor;
                                 Right : Element_Type)
      return Boolean
      with Pre    => (if Left = No_Element then raise Constraint_Error),
           Global => in access Set & Ada.Containers.Hashed_Sets'Global
;
48/5
{AI12-0112-1}    function Equivalent_Elements (Left  : Element_Type;
                                 Right : Cursor)
      return Boolean
      with Pre    => (if Right = No_Element then raise Constraint_Error),
           Global => in access Set & Ada.Containers.Hashed_Sets'Global
;
49/5
{AI12-0112-1}    procedure Iterate
     (Container : in Set;
      Process   : not null access procedure (Position : in Cursor))
      with Allows_Exit
;
49.1/5
{AI05-0212-1} {AI12-0112-1} {AI12-0266-1}    function Iterate (Container : in Set)
      return Set_Iterator_Interfaces.Parallel_Iterator Forward_Iterator'Class
      with Post => Tampering_With_Cursors_Prohibited (Container)
;
50/5
{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 => Hashed_Sets'Nonblocking and Key_Type'Nonblocking and
                       Key'Nonblocking and Hash'Nonblocking and
                       Equivalent_Keys'Nonblocking,
        Global => Hashed_Sets'Global & Key_Type'Global & Key'Global &
                  Hash'Global & Equivalent_Keys'Global
 is
51/5
{AI12-0112-1}       function Key (Position : Cursor) return Key_Type
         with Pre  => (if Position = No_Element then raise Constraint_Error),
              Global => in access Set & Generic_Keys'Global
;
51.1/5
{AI12-0112-1}       function Key (Container : Set;
                    Position : Cursor) return Key_Type
         with Pre  => (if Position = No_Element then raise Constraint_Error
                      elsif not Has_Element (Container, Position)
                         then raise Program_Error);
52/2
      function Element (Container : Set;
                        Key       : Key_Type)
        return Element_Type;
53/5
{AI12-0112-1}       procedure Replace (Container : in out Set;
                         Key       : in     Key_Type;
                         New_Item  : in     Element_Type)
         with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                       then raise Program_Error),
              Post => Length (Container) = Length (Container)'Old
;
54/5
{AI12-0112-1}       procedure Exclude (Container : in out Set;
                         Key       : in     Key_Type)
         with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                       then raise Program_Error),
              Post => (declare
                         Original_Length : constant Count_Type :=
                            Length (Container)'Old;
                       begin
                         Length (Container)
                            in Original_Length - 1 | Original_Length)
;
55/5
{AI12-0112-1}       procedure Delete (Container : in out Set;
                        Key       : in     Key_Type)
         with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                       then raise Program_Error),
              Post => Length (Container) = Length (Container)'Old - 1
;
56/5
{AI12-0112-1}       function Find (Container : Set;
                     Key       : Key_Type)
         return Cursor
         with Post => (if Find'Result = No_Element then True
                       else Has_Element (Container, Find'Result))
;
57/2
      function Contains (Container : Set;
                         Key       : Key_Type)
         return Boolean;
58/5
{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  => (if Position = No_Element then raise Constraint_Error
                       elsif not Has_Element (Container, Position)
                          then raise Program_Error)
;
58.1/5
{AI05-0212-1} {AI12-0112-1}       type Reference_Type
            (Element : not null access Element_Type) is private
         with Implicit_Dereference => Element,
              Global => synchronized in out access Set,
              Nonblocking => True,
              Default_Initial_Condition => (raise Program_Error)
;
58.2/5
{AI05-0212-1} {AI12-0112-1}       function Reference_Preserving_Key (Container : aliased in out Set;
                                         Position  : in Cursor)
         return Reference_Type
         with Pre  => (if Position = No_Element then raise Constraint_Error
                       elsif not Has_Element (Container, Position)
                          then raise Program_Error),
              Post => Tampering_With_Cursors_Prohibited (Container)
;
58.3/5
{AI05-0212-1} {AI12-0112-1}       function Constant_Reference (Container : aliased in Set;
                                   Key       : in Key_Type)
         return Constant_Reference_Type
         with Pre  => (if Find (Container, Key) = No_Element
                       then raise Constraint_Error),
              Post => Tampering_With_Cursors_Prohibited (Container)
;
58.4/5
{AI05-0212-1} {AI12-0112-1}       function Reference_Preserving_Key (Container : aliased in out Set;
                                         Key       : in Key_Type)
         return Reference_Type
         with Pre  => (if Find (Container, Key) = No_Element
                       then raise Constraint_Error),
              Post => Tampering_With_Cursors_Prohibited (Container)
;
59/2
   end Generic_Keys;
59.1/5
{AI05-0111-1}    package Stable is
59.2/5
{AI05-0111-1} {AI05-0339-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,
              Aggregate         => (Empty       => Empty,
                                    Add_Unnamed => Include),
              Stable_Properties => (Length),
              Global => (in Set.Base.allsynchronized out Set.Base.all),
              Default_Initial_Condition => Length (Set) = 0;
      pragma Preelaborable_Initialization(Set);
59.3/5
{AI05-0111-1}       type Cursor is private;
      pragma Preelaborable_Initialization(Cursor);
59.4/5
{AI05-0111-1}       Empty_Set : constant Set;
59.5/5
{AI05-0111-1}       No_Element : constant Cursor;
59.6/5
{AI05-0111-1}       function Has_Element (Position : Cursor) return Boolean
         with Nonblocking, Global => in access Set;
59.7/5
{AI05-0111-1}       package Set_Iterator_Interfaces is new
         Ada.Iterator_Interfaces (Cursor, Has_Element);
59.8/5
{AI05-0111-1}       procedure Assign (Target : in out Hashed_Sets.Set;
                        Source : in Set)
         with Post => Length (Source) = Length (Target);
59.9/5
{AI05-0111-1}       function Copy (Source : Hashed_Sets.Set) return Set
         with Post => Length (Copy'Result) = Length (Source);
59.10/5
{AI05-0111-1}       type Constant_Reference_Type
            (Element : not null access constant Element_Type) is private
         with Implicit_Dereference => Element,
              Global => null,
              Nonblocking => null,
              Default_Initial_Condition => (raise Program_Error);
59.11/5
{AI05-0111-1}       -- Additional subprograms as described in the text
      -- are declared here.
59.12/5
{AI05-0111-1}    private
59.13/5
{AI05-0111-1}       ... -- not specified by the language
59.14/5
{AI05-0111-1}    end Stable;
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 nonequivalent 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.
68.1/5
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;
68.2/2
{AI12-0339-1} Returns an empty set.
69/5
{AI12-0112-1} function Capacity (Container : Set) return Count_Type
   with Nonblocking, Global => null
;
70/2
{AI95-00302-03} Returns the capacity of Container.
71/5
{AI12-0112-1} procedure Reserve_Capacity (Container : in out Set;
                            Capacity  : in     Count_Type)
   with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                 then raise Program_Error),
        Post => Container.Capacity >= Capacity
;
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/5
This paragraph was deleted.{AI12-0112-1} 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/5
{AI12-0112-1} procedure Clear (Container : in out Set)
   with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                    then raise Program_Error),
        Post => Capacity (Container) = Capacity (Container)'Old and then
                Length (Container) = 0
;
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/5
{AI12-0112-1} procedure Assign (Target : in out Set; Source : in Set)
      with Pre  => (if Tampering_With_Cursors_Prohibited (Target)
                    then raise Program_Error),
           Post => Length (Source) = Length (Target) and then
                   Capacity (Target) >= Length (Source)
;
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/5
function Copy (Source : Set; Capacity : Count_Type := 0)
   return Set
   with Pre  => (if Capacity /= 0 and then Capacity < Length (Source)
                 then 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)
;
75.4/5
{AI05-0001-1} {AI12-0112-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/5
{AI12-0112-1} procedure Insert (Container : in out Set;
                  New_Item  : in     Element_Type;
                  Position  :    out Cursor;
                  Inserted  :    out Boolean)
   with Pre  => (if Tampering_With_Cursors_Prohibited (Container)
                 then raise Program_Error) and then
                (if Length (Container) > Count_Type'Last - 1
                 then 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)
;
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/5
{AI12-0112-1} function Equivalent_Elements (Left, Right : Cursor)
   return Boolean
   with Pre    => (if Left = No_Element or else Right = No_Element
                   then raise Constraint_Error),
        Global => in access Set & Ada.Containers.Hashed_Sets'Global
;
81/2
{AI95-00302-03} Equivalent to Equivalent_Elements (Element (Left), Element (Right)).
82/5
{AI12-0112-1} function Equivalent_Elements (Left  : Cursor;
                              Right : Element_Type) return Boolean
   with Pre    => (if Left = No_Element then raise Constraint_Error),
        Global => in access Set & Ada.Containers.Hashed_Sets'Global
;
83/2
{AI95-00302-03} Equivalent to Equivalent_Elements (Element (Left), Right).
84/5
{AI12-0112-1} function Equivalent_Elements (Left  : Element_Type;
                              Right : Cursor) return Boolean
   with Pre    => (if Right = No_Element then raise Constraint_Error),
        Global => in access Set & Ada.Containers.Hashed_Sets'Global
;
85/2
{AI95-00302-03} Equivalent to Equivalent_Elements (Left, Element (Right)).
85.1/5
{AI12-0112-1} {AI12-0266-1} function Iterate (Container : in Set)
   return Set_Iterator_Interfaces.Parallel_Iterator Forward_Iterator'Class
   with Post => Tampering_With_Cursors_Prohibited (Container)
;
85.2/5
{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.
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
Implementation Note: {AI95-00302-03} See A.18.5, “The Generic Package Containers.Hashed_Maps” for implementation notes regarding some of the operations of this package. 

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

Incompatibilities With Ada 2012

88.h/5
{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. 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 2012

88.i/5
{AI12-0212-1} Sets now support positional container aggregates, so aggregate syntax can be used to create Sets.
88.j/5
{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

88.k/5
{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). 

Contents   Index   References   Search   Previous   Next 
Ada-Europe Ada 2005 and 2012 Editions sponsored in part by Ada-Europe