1/2

{*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)*}

2/2

{*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.

3/2

{*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]}

3.a/2

4/2

{*AI95-00302-03*}
The type Set is used to represent sets. The type
Set needs finalization (see 7.6).

5/2

{*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)*}

6/2

{*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.

7/2

{*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.]

8/2

{*AI95-00302-03*}
{*tamper with cursors
(of a set)*} A subprogram is said to *tamper
with cursors* of a set object *S* if:

9/2

- 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

9.a/2

9.b/2

10/2

- it finalizes
*S*; or

11/2

- it calls the
Move procedure with
*S*as a parameter; or

12/2

- it calls one
of the operations defined to tamper with cursors of
*S*.

13/2

{*AI95-00302-03*}
{*tamper with elements
(of a set)*} A subprogram is said to *tamper
with elements* of a set object *S* if:

14/2

- it tampers with
cursors of
*S*.

14.a/2

14.b/2

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.

15/2

{*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.

16/2

{*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.

17/2

{*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.

18/2

{*AI95-00302-03*}
Execution of the default implementation of the
Input, Output, Read, or Write attribute of type Cursor raises Program_Error.

18.a/2

19/2

20/2

{*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.

20.a/2

21/2

22/2

{*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.

23/2

24/2

{*AI95-00302-03*}
Returns a set containing the single element New_Item.

25/2

26/2

{*AI95-00302-03*}
Returns the number of elements in Container.

27/2

28/2

{*AI95-00302-03*}
Equivalent to Length (Container) = 0.

29/2

30/2

{*AI95-00302-03*}
Removes all the elements from Container.

31/2

32/2

{*AI95-00302-03*}
If Position equals No_Element, then Constraint_Error
is propagated. Otherwise, Element returns the element designated by Position.

33/2

Position :

New_Item :

34/2

{*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.

34.a/2

34.b/2

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.

35/2

(Position :

Process :

36/2

{*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.

37/2

Source :

38/2

{*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.

39/2

New_Item :

Position :

Inserted :

40/2

{*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.

41/2

New_Item :

42/2

{*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.

42.a/2

42.b/2

Inserted : Boolean; C : Cursor;

Insert (Container, New_Item, C, Inserted);

42.c/2

but doesn't require the
hassle of **out** parameters.

43/2

New_Item :

44/2

{*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.

45/2

New_Item :

46/2

{*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.

47/2

Item :

48/2

{*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.

49/2

Item :

50/2

{*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.

51/2

Position :

52/2

{*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.

52.a/2

53/2

Source :

54/2

{*AI95-00302-03*}
Union inserts into Target the elements of Source
that are not equivalent to some element already in Target.

54.a/2

55/2

56/2

{*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.

57/2

Source :

58/2

{*AI95-00302-03*}
Union deletes from Target the elements of Target
that are not equivalent to some element of Source.

58.a/2

59/2

60/2

{*AI95-00302-03*}
Returns a set comprising all the elements of Left
that are equivalent to the some element of Right.

61/2

Source :

62/2

{*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.

63/2

64/2

{*AI95-00302-03*}
Returns a set comprising the elements of Left that
are not equivalent to some element of Right.

65/2

Source :

66/2

{*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.

67/2

68/2

{*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.

69/2

70/2

{*AI95-00302-03*}
If an element of Left is equivalent to some element
of Right, then Overlap returns True. Otherwise it returns False.

70.a/2

71/2

Of_Set : Set)

72/2

{*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.

72.a/2

73/2

74/2

{*AI95-00302-03*}
If Length (Container) = 0, then First returns No_Element.
Otherwise, First returns a cursor that designates the first element in
Container.

75/2

76/2

{*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.

77/2

78/2

{*AI95-00302-03*}
Equivalent to Position := Next (Position).

79/2

{*AI95-00302-03*}
Equivalent to Find (Container, Item) /= No_Element.

80/2

Item : Element_Type)

81/2

{*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.

82/2

Item : Element_Type)

83/2

84/2

{*AI95-00302-03*}
Returns True if Position designates an element,
and returns False otherwise.

84.a/2

85/2

(Container :

Process :

86/2

{*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.

86.a/2

86.b/2

See Iterate for vectors
(A.18.2) for a suggested implementation
of the check.

87/2

{*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]}

88/2

{*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]}

89/2

90/2

{*AI95-00302-03*}
Equivalent to Key (Element (Position)).

91/2

{*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.

92/2

Key :

New_Item :

93/2

{*AI95-00302-03*}
Equivalent to Replace_Element (Container, Find
(Container, Key), New_Item).

94/2

(Container :

Position :

Process :

(Element :

95/2

{*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.

95.a/2

96/2

If
Element_Type is unconstrained and definite, then the actual Element parameter
of Process.**all** shall be unconstrained.

96.a/2

97/2

{*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]}

98/2

- The set that contains the element it designates has been finalized;

99/2

- The set that contains the element it designates has been used as the Source or Target of a call to Move; or

100/2

- The element it designates has been deleted from the set.

101/2

{*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]}

101.a/2

101.b/2

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.

102/2

{*AI95-00302-03*}
No storage associated with a Set object shall be
lost upon assignment or scope exit.

103/2

{*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.

103.a/2

104/2

{*AI95-00302-03*}
Move should not copy elements, and should minimize
copying of internal data structures.

104.a/2

104.b/2

105/2

{*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.

105.a/2

105.b/2

105.c/2

{*AI95-00302-03*}
This description of sets is new; the extensions
are documented with the specific packages.

Sponsored by **Ada-Europe**