Sets

The language-defined generic packages Containers.Hashed_Sets and Containers.Ordered_Sets provide private types Set and Cursor, and a set of operations for each type. A set container allows elements of an arbitrary type to be stored without duplication. A hashed set uses a hash function to organize elements, while an ordered set orders its element per a specified relation.

This subclause describes the declarations that are common to both kinds of sets. See A.18.8 for a description of the semantics specific to Containers.Hashed_Sets and A.18.9 for a description of the semantics specific to Containers.Ordered_Sets.

Static Semantics

The actual function for the generic formal function "=" on Element_Type values is expected to define a reflexive and symmetric relationship and return the same result value each time it is called with a particular pair of values. If it behaves in some other manner, the function "=" on set values returns an unspecified value. The exact arguments and number of calls of this generic formal function by the function "=" on set values are unspecified.

A set contains elements. Set cursors designate elements. There exists an equivalence relation on elements, whose definition is different for hashed sets and ordered sets. A set never contains two or more equivalent elements. The length of a set is the number of elements it contains.

Each nonempty set has two particular elements called the first element and the last element (which may be the same). Each element except for the last element has a successor element. If there are no other intervening operations, starting with the first element and repeatedly going to the successor element will visit each element in the set exactly once until the last element is reached. The exact definition of these terms is different for hashed sets and ordered sets.

Some operations check for “tampering with cursors” of a container because they depend on the set of elements of the container remaining constant and on elements of the container not being replaced. When tampering with cursors is prohibited for a particular set object S, Program_Error is propagated by the finalization of S, as well as by a call that passes S to certain of the operations of this package, as indicated by the precondition of such an operation.

function Has_Element (Position : Cursor) return Boolean
with Nonblocking, Global => in all, Use_Formal => null;

function Has_Element (Container : Set; Position : Cursor)
return Boolean
with Nonblocking, Global => null, Use_Formal => null;

function "=" (Left, Right : Set) return Boolean;

If Left and Right denote the same set object, then the function returns True. If Left and Right have different lengths, then the function returns False. Otherwise, for each element E in Left, the function returns False if an element equal to E (using the generic formal equality operator) is not present in Right. If the function has not returned a result after checking all of the elements, it returns True. Any exception raised during evaluation of element equality is propagated.

function Equivalent_Sets (Left, Right : Set) return Boolean;

If Left and Right denote the same set object, then the function returns True. If Left and Right have different lengths, then the function returns False. Otherwise, for each element E in Left, the function returns False if an element equivalent to E is not present in Right. If the function has not returned a result after checking all of the elements, it returns True. Any exception raised during evaluation of element equivalence is propagated.

function Tampering_With_Cursors_Prohibited
(Container : Set) return Boolean
with Nonblocking, Global => null, Use_Formal => null;

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

function Length (Container : Set) return Count_Type
with Nonblocking, Global => null, Use_Formal => null;

function Is_Empty (Container : Set) return Boolean
with Nonblocking, Global => null, Use_Formal => null,
Post => Is_Empty'Result = (Length (Container) = 0);

procedure Clear (Container : in out Set)
   with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error,
        Post => Length (Container) = 0;

function Element (Position : Cursor) return Element_Type
with Pre => Position /= No_Element or else raise Constraint_Error,
Nonblocking, Global => in all, Use_Formal => Element_Type;

function Element (Container : Set;
                  Position  : Cursor) return Element_Type
   with Pre  => (Position /= No_Element
                    or else raise Constraint_Error) and then
                (Has_Element (Container, Position)
                   or else raise Program_Error),
        Nonblocking, Global => null, Use_Formal => Element_Type;

procedure Replace_Element (Container : in out Set;
                           Position  : in     Cursor;
                           New_item  : in     Element_Type)
   with Pre  => (not Tampering_With_Elements_Prohibited (Container)
                   or else raise Program_Error) and then
                (Position /= No_Element
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position)
                   or else raise Program_Error);

Replace_Element assigns New_Item to the element designated by Position. Any exception raised by the assignment is propagated. For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object (including itself).

procedure Query_Element
  (Position : in Cursor;
   Process  : not null access procedure (Element : in Element_Type))
   with Pre  => Position /= No_Element
                   or else raise Constraint_Error,
        Global => in all;

Query_Element calls Process.all with the element designated by Position as the argument. Tampering with the elements of the set that contains the element designated by Position is prohibited during the execution of the call on Process.all. Any exception raised by Process.all is propagated.

procedure Query_Element
  (Container : in Set;
   Position  : in Cursor;
   Process  : not null access procedure (Element : in Element_Type))
   with Pre  => (Position /= No_Element
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position)
                   or else raise Program_Error);

Query_Element calls Process.all with the key and element from the node designated by Position as the arguments. Tampering with the elements of Container is prohibited during the execution of the call on Process.all. Any exception raised by Process.all is propagated.

type Constant_Reference_Type
      (Element : not null access constant Element_Type) is private
   with Implicit_Dereference => Element,
        Nonblocking, Global => in out synchronized,
        Default_Initial_Condition => (raise Program_Error);

function Constant_Reference (Container : aliased in Set;
                             Position  : in Cursor)
   return Constant_Reference_Type
   with Pre  => (Position /= No_Element
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position)
                   or else raise Program_Error),
        Post => Tampering_With_Cursors_Prohibited (Container),
        Nonblocking, Global => null, Use_Formal => null;

This function (combined with the Constant_Indexing and Implicit_Dereference aspects) provides a convenient way to gain read access to an individual element of a set given a cursor.

Constant_Reference returns an object whose discriminant is an access value that designates the element designated by Position. Tampering with the cursors of Container is prohibited while the object returned by Constant_Reference exists and has not been finalized.

procedure Assign (Target : in out Set; Source : in Set)
   with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                   or else raise Program_Error,
        Post => Length (Source) = Length (Target);

If Target denotes the same object as Source, the operation has no effect. Otherwise, the elements of Source are copied to Target as for an assignment_statement assigning Source to Target.

procedure Move (Target : in out Set;
                Source : in out Set)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                    or else raise Program_Error) and then
                (not Tampering_With_Cursors_Prohibited (Source)
                    or else raise Program_Error),
        Post => (if not Target'Has_Same_Storage (Source) then
                    Length (Target) = Length (Source'Old) and then
                    Length (Source) = 0);

procedure Insert (Container : in out Set;
                  New_Item  : in     Element_Type;
                  Position  :    out Cursor;
                  Inserted  :    out Boolean)
   with Pre  => (not Tampering_With_Elements_Prohibited (Container)
                   or else raise Program_Error) and then
                (Length (Container) <= Count_Type'Last - 1
                    or else 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));

Insert checks if an element equivalent to New_Item is already present in Container. If a match is found, Inserted is set to False and Position designates the matching element. Otherwise, Insert adds New_Item to Container; Inserted is set to True and Position designates the newly-inserted element. Any exception raised during allocation is propagated and Container is not modified.

procedure Insert (Container : in out Set;
                  New_Item  : in     Element_Type)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error) and then
                (Length (Container) <= Count_Type'Last - 1
                    or else raise Constraint_Error),
        Post => Length (Container) = Length (Container)'Old + 1;

Insert inserts New_Item into Container as per the four-parameter Insert, with the difference that if an element equivalent to New_Item is already in the set, then Constraint_Error is propagated.

procedure Include (Container : in out Set;
                   New_Item  : in     Element_Type)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error) and then
                (Length (Container) <= Count_Type'Last - 1
                    or else raise Constraint_Error),
        Post => (declare
                   Original_Length : constant Count_Type :=
                      Length (Container)'Old;
                 begin
                   Length (Container)
                      in Original_Length | Original_Length + 1);

Include inserts New_Item into Container as per the four-parameter Insert, with the difference that if an element equivalent to New_Item is already in the set, then it is replaced. Any exception raised during assignment is propagated.

procedure Replace (Container : in out Set;
                   New_Item  : in     Element_Type)
   with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error,
        Post => Length (Container) = Length (Container)'Old;

Replace checks if an element equivalent to New_Item is already in the set. If a match is found, that element is replaced with New_Item; otherwise, Constraint_Error is propagated.

procedure Exclude (Container : in out Set;
                   Item       : in     Element_Type)
   with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error,
        Post => (declare
                   Original_Length : constant Count_Type :=
                      Length (Container)'Old;
                 begin
                   Length (Container) in
                      Original_Length - 1 | Original_Length);

procedure Delete (Container : in out Set;
                  Item       : in     Element_Type)
   with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error,
        Post => Length (Container) = Length (Container)'Old - 1;

Delete checks if an element equivalent to Item is present in Container. If a match is found, Delete removes the element from the set; otherwise, Constraint_Error is propagated.

procedure Delete (Container : in out Set;
                  Position  : in out Cursor)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error) and then
                (Position /= No_Element
                    or else raise Constraint_Error) and then
                (Has_Element (Container, Position)
                   or else raise Program_Error),
        Post => Length (Container) = Length (Container)'Old - 1 and then
                Position = No_Element;

procedure Union (Target : in out Set;
                 Source : in     Set)
   with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                   or else raise Program_Error,
        Post => Length (Target) <= Length (Target)'Old + Length (Source);

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

procedure Intersection (Target : in out Set;
                        Source : in     Set)
   with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                   or else raise Program_Error,
        Post => Length (Target) <= Length (Target)'Old + Length (Source);

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

procedure Difference (Target : in out Set;
                      Source : in     Set)
   with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                   or else raise Program_Error,
        Post => Length (Target) <= Length (Target)'Old + Length (Source);

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

procedure Symmetric_Difference (Target : in out Set;
                                Source : in     Set)
   with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                   or else raise Program_Error,
        Post => Length (Target) <= Length (Target)'Old + Length (Source);

If Target denotes the same object as Source, then Symmetric_Difference clears Target. Otherwise, it deletes from Target the elements that are equivalent to some element of Source, and inserts into Target the elements of Source that are not equivalent to some element of Target.

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

function Overlap (Left, Right : Set) return Boolean;

function Is_Subset (Subset : Set;
Of_Set : Set) return Boolean;

function First (Container : Set) return Cursor
   with Nonblocking, Global => null, Use_Formal => null,
        Post => (if not Is_Empty (Container)
                 then Has_Element (Container, First'Result)
                 else First'Result = No_Element);

function Next (Position : Cursor) return Cursor
with Nonblocking, Global => in all, Use_Formal => null,
Post => (if Position = No_Element then Next'Result = No_Element);

Returns a cursor that designates the successor of the element designated by Position. If Position designates the last element, then No_Element is returned. If Position equals No_Element, then No_Element is returned.

function Next (Container : Set;
               Position  : Cursor) return Cursor
   with Nonblocking, Global => null, Use_Formal => null,
        Pre  => Position = No_Element or else
                Has_Element (Container, Position)
                   or else 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));

procedure Next (Position : in out Cursor)
with Nonblocking, Global => in all, Use_Formal => null;

procedure Next (Container : in     Set;
                Position  : in out Cursor)
   with Nonblocking, Global => null, Use_Formal => null,
        Pre  => Position = No_Element or else
                Has_Element (Container, Position)
                   or else raise Program_Error,
        Post => (if Position /= No_Element
                 then Has_Element (Container, Position));

function Find (Container : Set;
               Item      : Element_Type) return Cursor
      with Post => (if Find'Result /= No_Element
                    then Has_Element (Container, Find'Result));

If Length (Container) equals 0, then Find returns No_Element. Otherwise, Find checks if an element equivalent to Item is present in Container. If a match is found, a cursor designating the matching element is returned; otherwise, No_Element is returned.

function Contains (Container : Set;
Item : Element_Type) return Boolean;

procedure Iterate
  (Container : in Set;
   Process   : not null access procedure (Position : in Cursor))
   with Allows_Exit;

Iterate calls Process.all with a cursor that designates 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 during the execution of a call on Process.all. Any exception raised by Process.all is propagated.

Both Containers.Hashed_Set and Containers.Ordered_Set declare a nested generic package Generic_Keys, which provides operations that allow set manipulation in terms of a key (typically, a portion of an element) instead of a complete element. The formal function Key of Generic_Keys extracts a key value from an element. It is expected to return the same value each time it is called with a particular element. The behavior of Generic_Keys is unspecified if Key behaves in some other manner.

A key is expected to unambiguously determine a single equivalence class for elements. The behavior of Generic_Keys is unspecified if the formal parameters of this package behave in some other manner.

function Key (Position : Cursor) return Key_Type
with Pre => Position /= No_Element or else raise Constraint_Error,
Global => in all;

function Key (Container : Set;
              Position : Cursor) return Key_Type
   with Pre  => (Position /= No_Element
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position)
                   or else raise Program_Error);

The subprograms in package Generic_Keys named Contains, Find, Element, Delete, and Exclude, are equivalent to the corresponding subprograms in the parent package, with the difference that the Key parameter is used to locate an element in the set.

procedure Replace (Container : in out Set;
                   Key       : in     Key_Type;
                   New_Item  : in     Element_Type)
   with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error,
        Post => Length (Container) = Length (Container)'Old;

procedure Update_Element_Preserving_Key
  (Container : in out Set;
   Position  : in     Cursor;
   Process   : not null access procedure
                                 (Element : in out Element_Type))
   with Pre  => (Position /= No_Element
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position)
                   or else raise Program_Error);

Update_Element_Preserving_Key uses Key to save the key value K of the element designated by Position. Update_Element_Preserving_Key then calls Process.all with that element as the argument. Tampering with the cursors of Container is prohibited during the execution of the call on Process.all. Any exception raised by Process.all is propagated. After Process.all returns, Update_Element_Preserving_Key checks if K determines the same equivalence class as that for the new element; if not, the element is removed from the set and Program_Error is propagated.

type Reference_Type (Element : not null access Element_Type) is private
   with Implicit_Dereference => Element,
        Nonblocking, Global => in out synchronized,
        Default_Initial_Condition => (raise Program_Error);

function Reference_Preserving_Key (Container : aliased in out Set;
                                   Position  : in Cursor)
   return Reference_Type
   with Pre  => (Position /= No_Element
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position)
                   or else raise Program_Error),
        Post => Tampering_With_Cursors_Prohibited (Container);

Reference_Preserving_Key uses Key to save the key value K; then returns an object whose discriminant is an access value that designates the element designated by Position. Tampering with the cursors of Container is prohibited while the object returned by Reference_Preserving_Key exists and has not been finalized. When the object returned by Reference_Preserving_Key is finalized, a check is made if K determines the same equivalence class as that for the new element; if not, the element is removed from the set and Program_Error is propagated.

function Constant_Reference (Container : aliased in Set;
                             Key       : in Key_Type)
   return Constant_Reference_Type
   with Pre  => Find (Container, Key) /= No_Element
                   or else raise Constraint_Error,
        Post => Tampering_With_Cursors_Prohibited (Container);

function Reference_Preserving_Key (Container : aliased in out Set;
                                   Key       : in Key_Type)
   return Reference_Type
   with Pre  => Find (Container, Key) /= No_Element
                   or else raise Constraint_Error,
        Post => Tampering_With_Cursors_Prohibited (Container);

The nested package Stable provides a type Stable.Set that represents a stable set, which is one that cannot grow and shrink. Such a set can be created by calling the Copy function, or by establishing a stabilized view of an ordinary set.

The subprograms of the set package that have a parameter or result of type Set are included in the nested package Stable with the same specification, except that the following are omitted:

Tampering_With_Cursors_Prohibited, Assign, Move, Insert, Include, Clear, Delete, Exclude, Replace, Replace_Element, procedures Union, Intersection, Difference, and Symmetric_Difference, (for Ordered_sets) Delete_First and Delete_Last, and (for Hashed_sets) Reserve_Capacity

The operations of this package are equivalent to those for ordinary sets, except that the calls to Tampering_With_Cursors_Prohibited that occur in preconditions are replaced by False, and any that occur in postconditions are replaced by True.

If a stable set is declared with the Base discriminant designating a pre-existing ordinary set, the stable set represents a stabilized view of the underlying ordinary set, and any operation on the stable set is reflected on the underlying ordinary set. While a stabilized view exists, any operation that tampers with cursors performed on the underlying set is prohibited. The finalization of a stable set that provides such a view removes this restriction on the underlying ordinary set (though some other restriction can exist due to other concurrent iterations or stabilized views).

If a stable set is declared without specifying Base, the object is necessarily initialized. The initializing expression of the stable set, typically a call on Copy, determines the Length of the set. The Length of a stable set never changes after initialization.

Bounded (Run-Time) Errors

It is a bounded error for the actual function associated with a generic formal subprogram, when called as part of an operation of a set package, to tamper with elements of any set parameter of the operation. Either Program_Error is raised, or the operation works as defined on the value of the set either prior to, or subsequent to, some or all of the modifications to the set.

It is a bounded error to call any subprogram declared in the visible part of a set package when the associated container has been finalized. If the operation takes Container as an in out parameter, then it raises Constraint_Error or Program_Error. Otherwise, the operation either proceeds as it would for an empty container, or it raises Constraint_Error or Program_Error.

Erroneous Execution

The result of "=" or Has_Element is unspecified if these functions are called with an invalid cursor parameter. Execution is erroneous if any other subprogram declared in Containers.Hashed_Sets or Containers.Ordered_Sets is called with an invalid cursor parameter.

Execution is erroneous if the set associated with the result of a call to Reference or Constant_Reference is finalized before the result object returned by the call to Reference or Constant_Reference is finalized.

Implementation Requirements

The execution of an assignment_statement for a set shall have the effect of copying the elements from the source set object to the target set object and changing the length of the target object to that of the source object.

A.18.7 Sets

Static Semantics

Bounded (Run-Time) Errors

Erroneous Execution

Implementation Requirements

Implementation Advice