Next: , Previous: A.18.7, Up: A.18


A.18.8 The Package Containers.Hashed_Sets

Static Semantics

1/2
The generic library package Containers.Hashed_Sets has the following declaration:

2/2

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

3/2

        type Set is tagged private;
        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;

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

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/2

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

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

59/2

        end Generic_Keys;

60/2

     private

61/2

        ... −− not specified by the language

62/2

     end Ada.Containers.Hashed_Sets;

63/2
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
Two elements E1 and E2 are defined to be equivalent if Equivalent_Elements (E1, E2) returns True.

65/2
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
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.67/2
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.68/2
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

Returns the capacity of Container.

71/2

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

72/2

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.

74/2

     procedure Clear (Container in out Set);

75/2

In addition to the semantics described in A.18.7, Clear does not affect the capacity of Container.

76/2

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

77/2

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

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

Equivalent to Equivalent_Elements (Element (Left), Element (Right)).

82/2

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

83/2

Equivalent to Equivalent_Elements (Element (Left), Right).

84/2

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

85/2

Equivalent to Equivalent_Elements (Left, Element (Right)).

86/2
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
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
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).