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.

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

A Cursor value is invalid if any of the following have occurred since it was created:

• The set that contains the element it designates has been finalized.
• The set that contains the element it designates has been used as the Target of a call to Assign, or as the target of an assignment_statement.
• The set that contains the element it designates has been used as the Source or Target of a call to Move.
• The element it designates has been removed from the set that previously contained the element.

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.

Hashed Sets

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, Global => in out synchronized is

   type Set    is tagged private;
   type Cursor is        private;

   Empty_Set : constant Set;
   No_Element: constant Cursor;

   function Has_Element(                Position: Cursor) return Boolean;
   function Has_Element(Container: Set; 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 Tampering_With_Cursors_Prohibited (Container: Set) return Boolean;
   function Empty(Capacity: Count_Type := <implementation-defined>) return Set;
   function To_Set(New_Item: Element_Type) return Set;
   function Capacity(Container: Set) return Count_Type;

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

   function Length  (Container: Set) return Count_Type;
   function Is_Empty(Container: Set) return Boolean;

   function Element(                Position: Cursor) return Element_Type;
   function Element(Container: Set; Position: Cursor) return Element_Type;
   procedure Replace_Element(Container: in out Set; Position: Cursor; New_item: Element_Type);
   procedure Query_Element(Position: Cursor; Process: not null access procedure(Element: Element_Type));
   procedure Query_Element(Container: Set;
                           Position : Cursor;
                           Process  : not null access procedure(Element: Element_Type));

   type Constant_Reference_Type(Element: not null access constant Element_Type) is private;

   function Constant_Reference(Container: aliased Set; Position: Cursor) return Constant_Reference_Type;
   function Copy(Source: Set; Capacity: Count_Type := 0) return Set;

   procedure Assign(Target: in out Set; Source:        Set);
   procedure Move  (Target: in out Set; Source: in out Set);
   procedure Insert(Container: in out Set;
                    New_Item : Element_Type;
                    Position : out Cursor;
                    Inserted : out Boolean);
   procedure Insert (Container: in out Set; New_Item: Element_Type);
   procedure Include(Container: in out Set; New_Item: Element_Type);
   procedure Replace(Container: in out Set; New_Item: Element_Type);
   procedure Exclude(Container: in out Set; Item    : Element_Type);
   procedure Delete (Container: in out Set; Item    : Element_Type);
   procedure Delete (Container: in out Set; Position: in out Cursor);

   procedure Union               (Target: in out Set; Source: Set);
   procedure Intersection        (Target: in out Set; Source: Set);
   procedure Difference          (Target: in out Set; Source: Set);
   procedure Symmetric_Difference(Target: in out Set; Source: Set);

   function Union               (Left, Right: Set) return Set;
   function Intersection        (Left, Right: Set) return Set;
   function Difference          (Left, Right: Set) return Set;
   function Symmetric_Difference(Left, Right: Set) return Set;
   function Overlap             (Left, Right: Set) return Boolean;
   function Is_Subset(Subset: Set; Of_Set: Set) return Boolean;

   function "or" (Left, Right: Set) return Set renames Union;
   function "and"(Left, Right: Set) return Set renames Intersection;
   function "xor"(Left, Right: Set) return Set renames Symmetric_Difference;
   function "-"  (Left, Right: Set) return Set renames Difference;

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

   function  Next(                Position:        Cursor) return Cursor;
   function  Next(Container: Set; Position:        Cursor) return Cursor;
   procedure Next(                Position: in out Cursor);
   procedure Next(Container: Set; Position: in out Cursor);

   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: Set; Process: not null access procedure(Position: Cursor));
   function  Iterate(Container: Set) return Set_Iterator_Interfaces.Parallel_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
      with Nonblocking, Global => null is

      function Key(                Position: Cursor) return Key_Type;
      function Key(Container: Set; Position: Cursor) return Key_Type;

      function  Element (Container:        Set; Key: Key_Type) return Element_Type;
      procedure Replace (Container: in out Set; Key: Key_Type; New_Item: Element_Type);
      procedure Exclude (Container: in out Set; Key: Key_Type);
      procedure Delete  (Container: in out Set; Key: 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 : Cursor;
                                              Process  : not null access procedure(Element: in out Element_Type));

      type Reference_Type(Element: not null access Element_Type) is private;
      
      function Reference_Preserving_Key(Container: aliased in out Set; Position: Cursor) return Reference_Type;
      function Constant_Reference      (Container: aliased        Set; Key: Key_Type)    return Constant_Reference_Type;
      function Reference_Preserving_Key(Container: aliased in out Set; Key: Key_Type)    return Reference_Type;
   end Generic_Keys;

   package Stable is
      type Set(Base: not null access Hashed_Sets.Set) is tagged limited private;
      type Cursor is private;

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

      procedure Assign(Target: in out Hashed_Sets.Set; Source: Set);

      function Copy(Source: Hashed_Sets.Set) return Set;

      type Constant_Reference_Type(Element: not null access constant Element_Type) is private;
   end Stable;
end Ada.Containers.Hashed_Sets;

Ordered Sets

with Ada.Iterator_Interfaces;

generic
   type Element_Type is private;
   with function "<"(Left, Right: Element_Type) return Boolean is <>;
   with function "="(Left, Right: Element_Type) return Boolean is <>;
package Ada.Containers.Ordered_Sets
   with Preelaborate, Remote_Types, Nonblocking, Global => in out synchronized is

   function Equivalent_Elements(Left, Right: Element_Type) return Boolean;

   type Set    is tagged private;
   type Cursor is        private;

   Empty_Set : constant Set;
   No_Element: constant Cursor;

   function Has_Element(                Position: Cursor) return Boolean;
   function Has_Element(Container: Set; 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 Tampering_With_Cursors_Prohibited(Container: Set) return Boolean;

   function To_Set(New_Item: Element_Type) return Set;
   function Empty return Set is
      (Empty_Set);

   function Length  (Container: Set) return Count_Type;
   function Is_Empty(Container: Set) return Boolean;

   function Element(                Position: Cursor) return Element_Type;
   function Element(Container: Set; Position: Cursor) return Element_Type;

   procedure Clear          (Container: in out Set);
   procedure Replace_Element(Container: in out Set; Position: Cursor; New_item: Element_Type);

   procedure Query_Element(Position: Cursor; Process: not null access procedure(Element: Element_Type));
   procedure Query_Element(Container: Set;
                           Position : Cursor;
                           Process  : not null access procedure(Element: Element_Type));

   type Constant_Reference_Type(Element: not null access constant Element_Type) is private;

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

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

   function  Copy(Source: Set) return Set;
   procedure Insert(Container: in out Set;
                    New_Item : Element_Type;
                    Position : out Cursor;
                    Inserted : out Boolean);
   procedure Insert (Container: in out Set; New_Item: Element_Type);
   procedure Include(Container: in out Set; New_Item: Element_Type);
   procedure Replace(Container: in out Set; New_Item: Element_Type);
   procedure Exclude(Container: in out Set; Item: Element_Type);
   procedure Delete (Container: in out Set; Item: Element_Type);
   procedure Delete (Container: in out Set; Position: in out Cursor);
   procedure Delete_First(Container: in out Set);
   procedure Delete_Last (Container: in out Set);

   procedure Union               (Target: in out Set; Source: Set);
   procedure Intersection        (Target: in out Set; Source: Set);
   procedure Difference          (Target: in out Set; Source: Set);
   procedure Symmetric_Difference(Target: in out Set; Source: Set);
   function  Union              (Left, Right: Set) return Set;
   function  Intersection       (Left, Right: Set) return Set;
   function  Difference         (Left, Right: Set) return Set;
   function Symmetric_Difference(Left, Right: Set) return Set;

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

   function First        (Container: Set) return Cursor;
   function First_Element(Container: Set) return Element_Type;
   function Last         (Container: Set) return Cursor;
   function Last_Element (Container: Set) return Element_Type;

   function  Next(Position:        Cursor) return Cursor;
   procedure Next(Position: in out Cursor);
   function  Next(Container: Set; Position:        Cursor) return Cursor;
   procedure Next(Container: Set; Position: in out Cursor);

   function  Previous(Position:        Cursor) return Cursor;
   procedure Previous(Position: in out Cursor);
   function  Previous(Container: Set; Position:        Cursor) return Cursor;
   procedure Previous(Container: Set; Position: in out Cursor);

   function Find    (Container: Set; Item: Element_Type) return Cursor;
   function Floor   (Container: Set; Item: Element_Type) return Cursor;
   function Ceiling (Container: Set; Item: Element_Type) return Cursor;
   function Contains(Container: Set; Item: Element_Type) return Boolean;

   function "or" (Left, Right: Set) return Set renames Union;
   function "and"(Left, Right: Set) return Set renames Intersection;
   function "xor"(Left, Right: Set) return Set renames Symmetric_Difference;
   function "-"  (Left, Right: Set) return Set renames Difference;

   function "<"(Left, Right: Cursor)               return Boolean;
   function ">"(Left, Right: Cursor)               return Boolean;
   function "<"(Left: Cursor; Right: Element_Type) return Boolean;
   function ">"(Left: Cursor; Right: Element_Type) return Boolean;
   function "<"(Left: Element_Type; Right: Cursor) return Boolean;
   function ">"(Left: Element_Type; Right: Cursor) return Boolean;

   procedure Iterate        (Container: Set; Process: not null access procedure(Position: Cursor));
   procedure Reverse_Iterate(Container: Set; Process: not null access procedure(Position: Cursor));
   function Iterate(Container: Set) return Set_Iterator_Interfaces.Parallel_Reversible_Iterator'Class;
   function Iterate(Container: Set; Start: Cursor) return Set_Iterator_Interfaces.Reversible_Iterator'Class;

   generic
      type Key_Type (<>) is private;
      with function Key(Element: Element_Type) return Key_Type;
      with function "<"(Left, Right: Key_Type) return Boolean is <>;
   package Generic_Keys
      with Nonblocking, Global => null is

      function Equivalent_Keys(Left, Right: Key_Type) return Boolean;
      function Key(                Position: Cursor)  return Key_Type;
      function Key(Container: Set; Position: Cursor)  return Key_Type;
      function Element(Container: Set; Key: Key_Type) return Element_Type;

      procedure Replace(Container: in out Set; Key: Key_Type; New_Item: Element_Type);
      procedure Exclude(Container: in out Set; Key: Key_Type);
      procedure Delete (Container: in out Set; Key: Key_Type);

      function Find    (Container: Set; Key: Key_Type) return Cursor;
      function Floor   (Container: Set; Key: Key_Type) return Cursor;
      function Ceiling (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 : Cursor;
                                              Process  : not null access procedure(Element: in out Element_Type));

      type Reference_Type(Element: not null access Element_Type) is private;

      function Reference_Preserving_Key(Container: aliased in out Set; Position: Cursor) return Reference_Type;
      function Reference_Preserving_Key(Container: aliased in out Set; Key: Key_Type)    return Reference_Type;
      function Constant_Reference      (Container: aliased        Set; Key: Key_Type)    return Constant_Reference_Type;
   end Generic_Keys;

   package Stable is
      type Set(Base: not null access Ordered_Sets.Set) is tagged limited private;
      type Cursor is private;

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

      procedure Assign(Target: in out Ordered_Sets.Set; Source: Set);
      function Copy(Source: Ordered_Sets.Set) return Set;

      type Constant_Reference_Type(Element: not null access constant Element_Type) is private;
   end Stable;
end Ada.Containers.Ordered_Sets;

Bounded Ordered Sets

The language-defined generic package Containers.Bounded_Ordered_Sets provides a private type Set and a set of operations. It provides the same operations as the package Containers.Ordered_Sets (see A.18.9), with the difference that the maximum storage is bounded.

Containers.Bounded_Ordered_Sets

type Set(Capacity: Count_Type) is tagged private;

Bounded (Run-Time) Errors

It is a bounded error to assign from a bounded set object while tampering with elements [or cursors] of that object is prohibited. Either Program_Error is raised by the assignment, execution proceeds with the target object prohibiting tampering with elements [or cursors], or execution proceeds normally.

Erroneous Execution

When a bounded set object S is finalized, if tampering with cursors is prohibited for S other than due to an assignment from another set, then execution is erroneous.

Bounded Hash Sets

The language-defined generic package Containers.Bounded_Hashed_Sets provides a private type Set and a set of operations. It provides the same operations as the package Containers.Hashed_Sets (see A.18.8), with the difference that the maximum storage is bounded.

Containers.Bounded_Hashed_Sets

type Set(Capacity: Count_Type; Modulus: Hash_Type) is tagged private;
-- ...

Bounded (Run-Time) Errors

It is a bounded error to assign from a bounded set object while tampering with elements [or cursors] of that object is prohibited. Either Program_Error is raised by the assignment, execution proceeds with the target object prohibiting tampering with elements [or cursors], or execution proceeds normally.

Erroneous Execution

When a bounded set object S is finalized, if tampering with cursors is prohibited for S other than due to an assignment from another set, then execution is erroneous.

Indefinite Hashed Sets

The language-defined generic package Containers.Indefinite_Hashed_Sets provides a set with the same operations as the package Containers.Hashed_Sets (see A.18.8), with the difference that the generic formal type Element_Type is indefinite.

Indefinite Ordered Sets

The language-defined generic package Containers.Indefinite_Ordered_Sets provides a set with the same operations as the package Containers.Ordered_Sets (see A.18.9), with the difference that the generic formal type Element_Type is indefinite.