A.18.7 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.
The type Set is used to represent sets. The type
Set needs finalization
(see
7.6).
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 of these generic packages have access-to-subprogram
parameters. To ensure such operations are well-defined, they guard against
certain actions by the designated subprogram. In particular, some operations
check for “tampering with cursors” of a container because
they depend on the set of elements of the container remaining constant,
and others check for “tampering with elements” of a container
because they depend on elements of the container not being replaced.
A
subprogram is said to
tamper with cursors of a set object
S
if:
it inserts or deletes elements of S, that
is, it calls the Insert, Include, Clear, Delete, Exclude, or Replace_Element
procedures with S as a parameter; or
it finalizes S; or
it calls the Assign procedure with S as
the Target parameter; or
it calls the Move procedure with S as a
parameter; or
it calls one of the operations defined to tamper
with cursors of S.
A
subprogram is said to
tamper with elements of a set object
S
if:
it tampers with cursors of S.
When tampering
with cursors is
prohibited for a particular set object
S,
Program_Error is propagated by a call of any language-defined subprogram
that is defined to tamper with the cursors of
S, leaving
S
unmodified. Similarly, when tampering with elements is
prohibited
for a particular set object
S, Program_Error is propagated by
a call of any language-defined subprogram that is defined to tamper with
the elements of
S (or tamper with the cursors of
S), leaving
S unmodified. These checks are made before any other defined behavior
of the body of the language-defined subprogram.
Empty_Set represents the empty Set object. It has
a length of 0. If an object of type Set is not otherwise initialized,
it is initialized to the same value as Empty_Set.
No_Element represents a cursor that designates no
element. If an object of type Cursor is not otherwise initialized, it
is initialized to the same value as No_Element.
The predefined "=" operator for type Cursor
returns True if both cursors are No_Element, or designate the same element
in the same container.
Execution of the default implementation of the Input,
Output, Read, or Write attribute of type Cursor raises Program_Error.
Set'Write for a Set object S writes Length(S)
elements of the set to the stream. It also may write additional information
about the set.
Set'Read reads the representation of a set from
the stream, and assigns to Item a set with the same length and
elements as was written by Set'Write.
function Has_Element (Position : Cursor) return Boolean;
Returns True if
Position designates an element, and returns False otherwise.
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 To_Set (New_Item : Element_Type) return Set;
Returns a set containing
the single element New_Item.
function Length (Container : Set) return Count_Type;
Returns the number
of elements in Container.
function Is_Empty (Container : Set) return Boolean;
Equivalent to Length
(Container) = 0.
procedure Clear (Container : in out Set);
Removes all the
elements from Container.
function Element (Position : Cursor) return Element_Type;
If Position equals
No_Element, then Constraint_Error is propagated. Otherwise, Element returns
the element designated by Position.
procedure Replace_Element (Container : in out Set;
Position : in Cursor;
New_Item : in Element_Type);
If Position equals
No_Element, then Constraint_Error is propagated; if Position does not
designate an element in Container, then Program_Error is propagated.
If an element equivalent to New_Item is already present in Container
at a position other than Position, Program_Error is propagated. Otherwise,
Replace_Element assigns New_Item to the element designated by Position.
Any exception raised by the assignment is propagated.
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
If Position equals
No_Element, then Constraint_Error is propagated. Otherwise, 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.
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;
The type Constant_Reference_Type
needs finalization.
The default initialization of an object of type
Constant_Reference_Type propagates Program_Error.
function Constant_Reference (Container : aliased in Set;
Position : in Cursor)
return Constant_Reference_Type;
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.
If Position equals No_Element, then Constraint_Error
is propagated; if Position does not designate an element in Container,
then Program_Error is propagated. Otherwise, Constant_Reference returns
an object whose discriminant is an access value that designates the element
designated by Position. Tampering with the elements 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);
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);
If Target denotes
the same object as Source, then the operation has no effect. Otherwise,
the operation is equivalent to Assign (Target, Source) followed by Clear
(Source).
procedure Insert (Container : in out Set;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
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);
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);
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);
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);
Exclude checks if
an element equivalent to Item is present in Container. If a match is
found, Exclude removes the element from the set.
procedure Delete (Container : in out Set;
Item : in Element_Type);
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);
If Position equals
No_Element, then Constraint_Error is propagated. If Position does not
designate an element in Container, then Program_Error is propagated.
Otherwise, Delete removes the element designated by Position from the
set. Position is set to No_Element on return.
procedure Union (Target : in out Set;
Source : in Set);
Union inserts into
Target the elements of Source that are not equivalent to some element
already in Target.
function Union (Left, Right : Set) return Set;
Returns a set comprising
all of the elements of Left, and the elements of Right that are not equivalent
to some element of Left.
procedure Intersection (Target : in out Set;
Source : in Set);
Intersection deletes
from Target the elements of Target that are not equivalent to some element
of Source.
function Intersection (Left, Right : Set) return Set;
Returns a set comprising
all the elements of Left that are equivalent to the some element of Right.
procedure Difference (Target : in out Set;
Source : in Set);
If Target denotes
the same object as Source, then Difference clears Target. Otherwise,
it deletes from Target the elements that are equivalent to some element
of Source.
function Difference (Left, Right : Set) return Set;
Returns a set comprising
the elements of Left that are not equivalent to some element of Right.
procedure Symmetric_Difference (Target : in out Set;
Source : in Set);
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;
Returns a set comprising
the elements of Left that are not equivalent to some element of Right,
and the elements of Right that are not equivalent to some element of
Left.
function Overlap (Left, Right : Set) return Boolean;
If an element of
Left is equivalent to some element of Right, then Overlap returns True.
Otherwise, it returns False.
function Is_Subset (Subset : Set;
Of_Set : Set) return Boolean;
If an element of
Subset is not equivalent to some element of Of_Set, then Is_Subset returns
False. Otherwise, it returns True.
function First (Container : Set) return Cursor;
If Length (Container)
= 0, then First returns No_Element. Otherwise, First returns a cursor
that designates the first element in Container.
function Next (Position : Cursor) return Cursor;
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.
procedure Next (Position : in out Cursor);
Equivalent to Position
:= Next (Position).
This paragraph
was deleted.
function Find (Container : Set;
Item : Element_Type) return Cursor;
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;
Equivalent to Find
(Container, Item) /= No_Element.
Paragraphs 83
and 84 were moved above.
procedure Iterate
(Container : in Set;
Process : not null access procedure (Position : in Cursor));
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;
Equivalent to Key
(Element (Position)).
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);
Equivalent to Replace_Element
(Container, Find (Container, Key), New_Item).
procedure Update_Element_Preserving_Key
(Container : in out Set;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type));
If Position equals No_Element, then Constraint_Error
is propagated; if Position does not designate an element in Container,
then Program_Error is propagated. Otherwise, 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 elements 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.
If Element_Type
is unconstrained and definite, then the actual Element parameter of Process.all
shall be unconstrained.
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;
The type Reference_Type
needs finalization.
The default initialization of an object of type
Reference_Type propagates Program_Error.
function Reference_Preserving_Key (Container : aliased in out Set;
Position : in Cursor)
return Reference_Type;
This function (combined
with the Implicit_Dereference aspect) provides a convenient way to gain
read and write access to an individual element of a set given a cursor.
If Position equals No_Element, then Constraint_Error
is propagated; if Position does not designate an element in Container,
then Program_Error is propagated. Otherwise, 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 elements 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;
This function (combined
with the Implicit_Dereference aspect) provides a convenient way to gain
read access to an individual element of a set given a key value.
Equivalent to Constant_Reference (Container, Find
(Container, Key)).
function Reference_Preserving_Key (Container : aliased in out Set;
Key : in Key_Type)
return Reference_Type;
This function (combined
with the Implicit_Dereference aspect) provides a convenient way to gain
read and write access to an individual element of a set given a key value.
Equivalent to Reference_Preserving_Key (Container,
Find (Container, Key)).
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; or
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.
Implementation Requirements
No storage associated with a Set object shall be
lost upon assignment or scope exit.
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.
Implementation Advice
Move should not copy elements, and should minimize
copying of internal data structures.
If an exception is propagated from a set operation,
no storage should be lost, nor any elements removed from a set unless
specified by the operation.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
