A.18.7 Sets
{
AI95-00302-03}
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.
{set
container} {container
(set)} {
AI95-00302-03}
This section 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
{
AI95-00302-03}
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.
{unspecified
[partial]} Ramification: If the actual function
for "=" is not symmetric and consistent, the result returned
by the "=" for Set objects cannot be predicted. The implementation
is not required to protect against "=" raising an exception,
or returning random results, or any other “bad” behavior.
And it can call "=" in whatever manner makes sense. But note
that only the result of "=" for Set objects is unspecified;
other subprograms are not allowed to break if "=" is bad (they
aren't expected to use "=").
{
AI95-00302-03}
The type Set is used to represent sets. The type Set needs finalization
(see
7.6).
{
AI95-00302-03}
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.
{length
(of a set)} {
AI95-00302-03}
{first element (of a set)}
{last element (of
a set)} {successor
element (of a set)} 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.
{
AI95-00302-03}
[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.]
{
AI95-00302-03}
{tamper with cursors (of a set)}
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
To be honest: Operations which are defined
to be equivalent to a call on one of these operations also are included.
Similarly, operations which call one of these as part of their definition
are included.
Discussion: We have to include Replace_Element
here because it might delete and reinsert the element if it moves in
the set. That could change the order of iteration, which is what this
check is designed to prevent. Replace is also included, as it is defined
in terms of Replace_Element.
it finalizes S; 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.
{
AI95-00302-03}
{tamper with elements (of a set)}
A subprogram is said to
tamper with elements
of a set object
S if:
it tampers with cursors of S.
Reason: Complete replacement of an element
can cause its memory to be deallocated while another operation is holding
onto a reference to it. That can't be allowed. However, a simple modification
of (part of) an element is not a problem, so Update_Element_Preserving_Key
does not cause a problem.
We don't need to list Replace and Replace_Element
here because they are covered by “tamper with cursors”. For
Set, “tamper with cursors” and “tamper with elements”
are the same. We leave both terms so that the rules for routines like
Iterate and Query_Element are consistent across all containers.
{
AI95-00302-03}
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.
{
AI95-00302-03}
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.
{
AI95-00302-03}
The predefined "=" operator for type Cursor returns True if
both cursors are No_Element, or designate the same element in the same
container.
{
AI95-00302-03}
Execution of the default implementation of the Input, Output, Read, or
Write attribute of type Cursor raises Program_Error.
Reason: A cursor will probably be implemented
in terms of one or more access values, and the effects of streaming access
values is unspecified. Rather than letting the user stream junk by accident,
we mandate that streaming of cursors raise Program_Error by default.
The attributes can always be specified if there is a need to support
streaming.
function "=" (Left, Right : Set) return Boolean;
{
AI95-00302-03}
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.
Implementation Note: This wording describes
the canonical semantics. However, the order and number of calls on the
formal equality function is unspecified for all of the operations that
use it in this package, so an implementation can call it as many or as
few times as it needs to get the correct answer. Specifically, there
is no requirement to call the formal equality additional times once the
answer has been determined.
function Equivalent_Sets (Left, Right : Set) return Boolean;
{
AI95-00302-03}
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;
{
AI95-00302-03}
Returns a set containing the single element New_Item.
function Length (Container : Set) return Count_Type;
function Is_Empty (Container : Set) return Boolean;
procedure Clear (Container : in out Set);
function Element (Position : Cursor) return Element_Type;
{
AI95-00302-03}
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);
{
AI95-00302-03}
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.
Implementation Note: The final assignment
may require that the node of the element be moved in the Set's data structures.
That could mean that implementing this operation exactly as worded above
could require the overhead of searching twice. Implementations are encouraged
to avoid this extra overhead when possible, by prechecking if the old
element is equivalent to the new one, by inserting a placeholder node
while checking for an equivalent element, and similar optimizations.
The cursor still designates the same element
after this operation; only the value of that element has changed. Cursors
cannot include information about the relative position of an element
in a Set (as they must survive insertions and deletions of other elements),
so this should not pose an implementation hardship.
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
{
AI95-00302-03}
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. Program_Error is propagated if Process.
all
tampers with the elements of Container. Any exception raised by Process.
all
is propagated.
procedure Move (Target : in out Set;
Source : in out Set);
{
AI95-00302-03}
If Target denotes the same object as Source, then Move has no effect.
Otherwise, Move first clears Target. Then, each element from Source is
removed from Source and inserted into Target. The length of Source is
0 after a successful call to Move.
procedure Insert (Container : in out Set;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
{
AI95-00302-03}
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);
{
AI95-00302-03}
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.
Discussion:
This is equivalent to:
declare
Inserted : Boolean; C : Cursor;
begin
Insert (Container, New_Item, C, Inserted);
if not Inserted then
raise Constraint_Error;
end if;
end;
but doesn't require the hassle of out
parameters.
procedure Include (Container : in out Set;
New_Item : in Element_Type);
{
AI95-00302-03}
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);
{
AI95-00302-03}
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);
{
AI95-00302-03}
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);
{
AI95-00302-03}
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);
{
AI95-00302-03}
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.
Ramification: The check on Position checks
that the cursor does not belong to some other set. This check implies
that a reference to the set is included in the cursor value. This wording
is not meant to require detection of dangling cursors; such cursors are
defined to be invalid, which means that execution is erroneous, and any
result is allowed (including not raising an exception).
procedure Union (Target : in out Set;
Source : in Set);
{
AI95-00302-03}
Union inserts into Target the elements of Source that are not equivalent
to some element already in Target.
Implementation Note: If the objects are
the same, the result is the same as the original object. The implementation
needs to take care so that aliasing effects do not make the result trash;
Union (S, S); must work.
function Union (Left, Right : Set) return Set;
{
AI95-00302-03}
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);
{
AI95-00302-03}
Union deletes from Target the elements of Target that are not equivalent
to some element of Source.
Implementation Note: If the objects are
the same, the result is the same as the original object. The implementation
needs to take care so that aliasing effects do not make the result trash;
Intersection (S, S); must work.
function Intersection (Left, Right : Set) return Set;
{
AI95-00302-03}
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);
{
AI95-00302-03}
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;
{
AI95-00302-03}
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);
{
AI95-00302-03}
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;
{
AI95-00302-03}
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;
{
AI95-00302-03}
If an element of Left is equivalent to some element of Right, then Overlap
returns True. Otherwise it returns False.
Discussion: This operation is commutative.
If Overlap returns False, the two sets are disjoint.
function Is_Subset (Subset : Set;
Of_Set : Set) return Boolean;
{
AI95-00302-03}
If an element of Subset is not equivalent to some element of Of_Set,
then Is_Subset returns False. Otherwise it returns True.
Discussion: This operation is not commutative,
so we use parameter names that make it clear in named notation which
set is which.
function First (Container : Set) return Cursor;
{
AI95-00302-03}
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;
{
AI95-00302-03}
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);
{
AI95-00302-03}
Equivalent to Find (Container, Item) /= No_Element.
function Find (Container : Set;
Item : Element_Type) return Cursor;
{
AI95-00302-03}
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;
function Has_Element (Position : Cursor) return Boolean;
{
AI95-00302-03}
Returns True if Position designates an element, and returns False otherwise.
To be honest: This function may not detect
cursors that designate deleted elements; such cursors are invalid (see
below); the result of Has_Element for invalid cursors is unspecified
(but not erroneous).
procedure Iterate
(Container : in Set;
Process : not null access procedure (Position : in Cursor));
{
AI95-00302-03}
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. Program_Error is propagated if Process.
all
tampers with the cursors of Container. Any exception raised by Process.
all
is propagated.
Implementation Note: The “tamper
with cursors” check takes place when the operations that insert
or delete elements, and so on are called.
See Iterate for vectors (
A.18.2)
for a suggested implementation of the check.
{
AI95-00302-03}
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.
{unspecified
[partial]} {
AI95-00302-03}
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.
{unspecified
[partial]} function Key (Position : Cursor) return Key_Type;
{
AI95-00302-03}
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);
{
AI95-00302-03}
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));
{
AI95-00302-03}
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. Program_Error
is propagated if Process.
all tampers with the elements of Container.
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.
Reason: The key check ensures that the
invariants of the set are preserved by the modification. The “tampers
with the elements” check prevents data loss (if Element_Type is
by-copy) or erroneous execution (if element type is unconstrained and
indefinite).
If Element_Type
is unconstrained and definite, then the actual Element parameter of Process.all
shall be unconstrained.
Ramification: This means that the elements
cannot be directly allocated from the heap; it must be possible to change
the discriminants of the element in place.
Erroneous Execution
{
AI95-00302-03}
A Cursor value is
invalid if any of the following have occurred
since it was created:
{invalid cursor
(of a set)} {cursor
(invalid) [partial]} The set that contains the element it designates
has been finalized;
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 deleted from
the set.
{
AI95-00302-03}
The result of "=" or Has_Element is unspecified if these functions
are called with an invalid cursor parameter.
{unspecified
[partial]} Execution is erroneous if any
other subprogram declared in Containers.Hashed_Sets or Containers.Ordered_Sets
is called with an invalid cursor parameter.
{erroneous
execution (cause) [partial]} Discussion: The list above is intended
to be exhaustive. In other cases, a cursor value continues to designate
its original element. For instance, cursor values survive the insertion
and deletion of other elements.
While it is possible to check for these cases,
in many cases the overhead necessary to make the check is substantial
in time or space. Implementations are encouraged to check for as many
of these cases as possible and raise Program_Error if detected.
Implementation Requirements
{
AI95-00302-03}
No storage associated with a Set object shall be lost upon assignment
or scope exit.
{
AI95-00302-03}
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.
Implementation Note: An assignment of
a Set is a “deep” copy; that is the elements are copied as
well as the data structures. We say “effect of” in order
to allow the implementation to avoid copying elements immediately if
it wishes. For instance, an implementation that avoided copying until
one of the containers is modified would be allowed.
Implementation Advice
{
AI95-00302-03}
Move should not copy elements, and should minimize copying of internal
data structures.
Implementation Advice: Move for sets
should not copy elements, and should minimize copying of internal data
structures.
Implementation Note: Usually that can
be accomplished simply by moving the pointer(s) to the internal data
structures from the Source container to the Target container.
{
AI95-00302-03}
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.
Implementation Advice: 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.
Reason: This is important so that programs
can recover from errors. But we don't want to require heroic efforts,
so we just require documentation of cases where this can't be accomplished.
Wording Changes from Ada 95
{
AI95-00302-03}
This description of sets is new; the extensions are documented with the
specific packages.
Sponsored by Ada-Europe