A.18.7 Sets
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. 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. Static Semantics
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.3.a/2
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 "=").
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.6/2
{
AI95-00302-03}
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}
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
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.
9.b/2
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.
10/2
it finalizes S; or
10.1/3
{
AI05-0001-1}
it calls the Assign procedure with S as
the Target parameter; or11/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}
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
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.
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.
14.1/3
{
AI05-0265-1}
If tampering
with cursors is prohibited for a particular set object S,
Program_Error is propagated by any language-defined subprogram that is
defined to tamper with the cursors of S. Similarly, if tampering
with elements is prohibited for a particular set object S,
Program_Error is propagated by any language-defined subprogram that is
defined to tamper with the elements of S.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
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.
18.1/3
{
AI05-0001-1}
{
AI05-0262-1}
Set'Write writes exactly Length(Set) elements of
the set to the stream. It may write additional information about the
set as well. Set'Read reads exactly Length(Set) elements of Set from
the stream and consumes any additional information written by Set'Write.18.b/3
Ramification: Streaming
more elements than the container length is wrong. For implementation
implications of this rule, see the Implementation Note in A.18.2.
18.2/3
function Has_Element (Position : Cursor) return Boolean;
18.3/3
{
AI05-0212-1}
Returns True if Position designates an element,
and returns False otherwise.18.c/3
To be honest: This
function may not detect cursors that designate deleted elements; such
cursors are invalid (see below) and the result of calling Has_Element
with an invalid cursor is unspecified (but not erroneous).
19/2
function "=" (Left, Right : Set) return Boolean;
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
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.
21/2
function Equivalent_Sets (Left, Right : Set) return Boolean;
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
function To_Set (New_Item : Element_Type) return Set;
24/2
{
AI95-00302-03}
Returns a set containing the single element New_Item.25/2
function Length (Container : Set) return Count_Type;
26/2
27/2
function Is_Empty (Container : Set) return Boolean;
28/2
29/2
procedure Clear (Container : in out Set);
30/2
31/2
function Element (Position : Cursor) return Element_Type;
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
procedure Replace_Element (Container : in out Set;
Position : in Cursor;
New_Item : in Element_Type);
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
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.
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
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
36/3
{
AI95-00302-03}
{
AI05-0021-1}
{
AI05-0265-1}
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 Program_Error
is propagated if Process.all tampers with the elements of the set that contains
the element designated by Position is prohibited during the execution
of Process.all Container.
Any exception raised by Process.all is propagated.36.1/3
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;
36.2/3
{
AI05-0212-1}
The type Constant_Reference_Type needs finalization.36.3/3
The default initialization
of an object of type Constant_Reference_Type propagates Program_Error.
36.a/3
Reason: It is expected
that Constant_Reference_Type will be a controlled type, for which finalization
will have some action to terminate the tampering check for the associated
container. If the object is created by default, however, there is no
associated container. Since this is useless, and supporting this case
would take extra work, we define it to raise an exception.
36.4/3
function Constant_Reference (Container : aliased in Set;
Position : in Cursor)
return Constant_Reference_Type;
36.5/3
{
AI05-0212-1}
This function (combined with the Constant_Indexing
and Implicit_Dereference aspects) provides a convenient way to gain read
access to the individual elements of a container starting with a cursor.36.6/3
{
AI05-0212-1}
{
AI05-0265-1}
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.36.7/3
procedure Assign (Target : in out Set; Source : in Set);
36.8/3
{
AI05-0001-1}
{
AI05-0248-1}
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. 36.b/3
Discussion: {
AI05-0005-1}
This routine exists for compatibility with the
bounded set containers. For an unbounded set, Assign(A, B) and
A := B behave identically. For a bounded set, := will raise
an exception if the container capacities are different, while Assign
will not raise an exception if there is enough room in the target.
37/2
procedure Move (Target : in out Set;
Source : in out Set);
38/3
{
AI95-00302-03}
{
AI05-0001-1}
{
AI05-0248-1}
{
AI05-0262-1}
If Target denotes the same object as Source, then
the operation Move has no effect. Otherwise, the operation
is equivalent to Assign (Target, Source) followed by Clear (Source) 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
procedure Insert (Container : in out Set;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
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
procedure Insert (Container : in out Set;
New_Item : in Element_Type);
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
Discussion:
This is equivalent to:
42.b/2
declare
Inserted : Boolean; C : Cursor;
begin
Insert (Container, New_Item, C, Inserted);
if not Inserted then
raise Constraint_Error;
end if;
end;
42.c/2
but doesn't require the
hassle of out parameters.
43/2
procedure Include (Container : in out Set;
New_Item : in Element_Type);
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
procedure Replace (Container : in out Set;
New_Item : in Element_Type);
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
procedure Exclude (Container : in out Set;
Item : in Element_Type);
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
procedure Delete (Container : in out Set;
Item : in Element_Type);
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
procedure Delete (Container : in out Set;
Position : in out Cursor);
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
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).
53/2
procedure Union (Target : in out Set;
Source : in Set);
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
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.
55/2
function Union (Left, Right : Set) return Set;
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
procedure Intersection (Target : in out Set;
Source : in Set);
58/3
{
AI95-00302-03}
{
AI05-0004-1}
Intersection Union deletes from Target the elements of Target that are not equivalent to
some element of Source.58.a/2
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.
59/2
function Intersection (Left, Right : Set) return Set;
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
procedure Difference (Target : in out Set;
Source : in Set);
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
function Difference (Left, Right : Set) return Set;
64/2
{
AI95-00302-03}
Returns a set comprising the elements of Left that
are not equivalent to some element of Right.65/2
procedure Symmetric_Difference (Target : in out Set;
Source : in Set);
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
function Symmetric_Difference (Left, Right : Set) return Set;
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
function Overlap (Left, Right : Set) return Boolean;
70/3
{
AI95-00302-03}
{
AI05-0264-1}
If an element of Left is equivalent to some element
of Right, then Overlap returns True. Otherwise, it returns False.70.a/2
Discussion: This
operation is commutative. If Overlap returns False, the two sets are
disjoint.
71/2
function Is_Subset (Subset : Set;
Of_Set : Set) return Boolean;
72/3
{
AI95-00302-03}
{
AI05-0264-1}
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
Discussion: This
operation is not commutative, so we use parameter names that make it
clear in named notation which set is which.
73/2
function First (Container : Set) return Cursor;
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
function Next (Position : Cursor) return Cursor;
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
procedure Next (Position : in out Cursor);
78/2
79/3
80/2
function Find (Container : Set;
Item : Element_Type) return Cursor;
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
function Contains (Container : Set;
Item : Element_Type) return Boolean;
82.1/3
{
AI05-0004-1}
Equivalent to Find (Container, Item) /= No_Element.83/3
function Has_Element (Position : Cursor) return Boolean;
84/3
84.a/3
To be honest: {
AI05-0212-1}
This
function may not detect cursors that designate deleted elements; such
cursors are invalid (see below) and the result of calling Has_Element
with an invalid cursor is unspecified (but not erroneous).
Paragraphs
83 and 84 were moved above.
85/2
procedure Iterate
(Container : in Set;
Process : not null access procedure (Position : in Cursor));
86/3
{
AI95-00302-03}
{
AI05-0265-1}
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 Program_Error
is propagated if Process.all tampers with the cursors of Container is prohibited
during the execution of Process.all.
Any exception raised by Process.all is propagated.86.a/2
Implementation Note:
The “tamper with cursors” check takes place when the
operations that insert or delete elements, and so on are called.
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.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.89/2
function Key (Position : Cursor) return Key_Type;
90/2
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
procedure Replace (Container : in out Set;
Key : in Key_Type;
New_Item : in Element_Type);
93/2
{
AI95-00302-03}
Equivalent to Replace_Element (Container, Find
(Container, Key), New_Item).94/2
procedure Update_Element_Preserving_Key
(Container : in out Set;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type));
95/3
{
AI95-00302-03}
{
AI05-0265-1}
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 Program_Error
is propagated if Process.all tampers with the elements of Container is prohibited
during the execution of 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.95.a/2
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).
96/2
If
Element_Type is unconstrained and definite, then the actual Element parameter
of Process.all shall be unconstrained.
96.a/2
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.
96.1/3
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;
96.2/3
{
AI05-0212-1}
The type Reference_Type needs finalization.96.3/3
The default initialization
of an object of type Reference_Type propagates Program_Error.
96.4/3
function Reference_Preserving_Key (Container : aliased in out Set;
Position : in Cursor)
return Reference_Type;
96.5/3
{
AI05-0212-1}
This function (combined with the Implicit_Dereference
aspect) provides a convenient way to gain read and write access to the
individual elements of a container starting with a cursor.96.6/3
{
AI05-0212-1}
{
AI05-0265-1}
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.96.7/3
function Constant_Reference (Container : aliased in Set;
Key : in Key_Type)
return Constant_Reference_Type;
96.8/3
{
AI05-0212-1}
This function (combined with the Implicit_Dereference
aspect) provides a convenient way to gain read access to the individual
elements of a container starting with a key value.96.9/3
Equivalent to Constant_Reference
(Container, Find (Container, Key)).
96.10/3
function Reference_Preserving_Key (Container : aliased in out Set;
Key : in Key_Type)
return Reference_Type;
96.11/3
{
AI05-0212-1}
This function (combined with the Implicit_Dereference
aspect) provides a convenient way to gain read and write access to the
individual elements of a container starting with a key value.96.12/3
Equivalent to Reference_Preserving_Key
(Container, Find (Container, Key)).
Bounded (Run-Time) Errors
96.13/3
{
AI05-0022-1}
{
AI05-0248-1}
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.96.14/3
{
AI05-0027-1}
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
97/2
{
AI95-00302-03}
A Cursor value is invalid if any of the
following have occurred since it was created: 98/2
The set that contains the
element it designates has been finalized;
98.1/3
{
AI05-0160-1}
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;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/3
{
AI05-0160-1}
{
AI05-0262-1}
The element it designates has been removed deleted from the set that previously contained the
element. 100.a/3
Ramification: {
AI05-0160-1}
This can happen directly via calls to Clear, Exclude,
Delete, and Update_Element_Preserving_Key, and indirectly via calls to
procedures Intersection, Difference, and Symmetric_Difference.
101/2
{
AI95-00302-03}
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.101.a/2
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.
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.
101.1/3
{
AI05-0212-1}
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. 101.c/3
Reason: Each object
of Reference_Type and Constant_Reference_Type probably contains some
reference to the originating container. If that container is prematurely
finalized (which is only possible via Unchecked_Deallocation, as accessibility
checks prevent passing a container to Reference that will not live as
long as the result), the finalization of the object of Reference_Type
will try to access a non-existent object. This is a normal case of a
dangling pointer created by Unchecked_Deallocation; we have to explicitly
mention it here as the pointer in question is not visible in the specification
of the type. (This is the same reason we have to say this for invalid
cursors.)
Implementation Requirements
102/2
{
AI95-00302-03}
No storage associated with a Set object shall be
lost upon assignment or scope exit.103/3
{
AI95-00302-03}
{
AI05-0262-1}
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.103.a/2
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
104/2
{
AI95-00302-03}
Move should not copy elements, and should minimize
copying of internal data structures. 104.a/2
Implementation Advice:
Move for sets should not copy elements,
and should minimize copying of internal data structures.
104.b/2
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.
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
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.
105.b/2
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
105.c/2
{
AI95-00302-03}
This description of sets is new; the extensions
are documented with the specific packages. Extensions to Ada 2005
105.d/3
{
AI05-0212-1}
Added reference support to
make set containers more convenient to use. Wording Changes from Ada 2005
105.e/3
{
AI05-0001-1}
Added procedure Assign; the extension and incompatibility
is documented with the specific packages.105.f/3
{
AI05-0001-1}
Generalized the definition of Move. Specified which
elements are read/written by stream attributes.105.g/3
{
AI05-0022-1}
Correction: Added a Bounded (Run-Time) Error
to cover tampering by generic actual subprograms.105.h/3
{
AI05-0027-1}
Correction: Added a Bounded (Run-Time) Error
to cover access to finalized set containers.105.i/3
{
AI05-0160-1}
Correction: Revised the definition of invalid
cursors to cover missing (and new) cases.105.j/3
{
AI05-0265-1}
Correction: Defined when a container prohibits
tampering in order to more clearly define where the check is made and
the exception raised.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
