Ada Conformity Assessment Authority      Home Conformity Assessment   Test Suite ARGAda Standard
 
Annotated Ada Reference Manual (Ada 202x Draft 25)Legal Information
Contents   Index   References   Search   Previous   Next 

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/3
{AI95-00302-03} {AI05-0299-1} 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

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/5
{AI95-00302-03} {AI12-0111-1} {AI12-0112-1} [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 , and others check for “tampering with elements” of a container because they depend on elements of the container not being replaced.] When tampering with cursors is prohibited for a particular set object M, Program_Error is propagated by the finalization of M[, as well as by a call that passes M to certain of the operations of this package, as indicated by the precondition of such an operation].
7.a/5
Discussion: {AI12-0112-1} Note that Replace_Element tampers with cursors 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 also tampers with cursors, as it is defined in terms of Replace_Element.
7.b/5
{AI12-0112-1} These inclusions mean that there are no operations that would tamper with elements that do not tamper with cursors. As such, we do not define tampering with elements at all for set containers. Earlier versions of Ada did so just so the description of subprograms are the same between containers, but since we've changed those to pre- and postconditions which are necessarily specific to each container, there no longer seems to be any reason to define tampering with elements for sets. 
Paragraphs 8 through 14 are removed as preconditions now describe these rules.
8/5
{AI95-00302-03} {AI12-0111-1} {AI12-0112-1} A subprogram is said to tamper with cursors of a set object S if: 
9/5
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/5
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/5
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/5
it finalizes S; or
10.1/5
{AI05-0001-1} it calls the Assign procedure with S as the Target parameter; or
10.a/3
Ramification: We don't need to explicitly mention assignment_statement, because that finalizes the target object as part of the operation, and finalization of an object is already defined as tampering with cursors.
11/5
it calls the Move procedure with S as a parameter; or
12/5
it calls one of the operations defined to tamper with the cursors of S.
13/5
{AI95-00302-03} {AI12-0111-1} {AI12-0112-1} A subprogram is said to tamper with elements of a set object S if:
14/5
it tampers with cursors of S.
14.a/5
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/5
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/5
  {AI05-0265-1} {AI12-0110-1} {AI12-0111-1} {AI12-0112-1} 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.
14.c/5
Proof: Tampering with elements includes tampering with cursors, so we mention it only from completeness in the second sentence. 
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 for a Set object S writes Length(S) elements of the set to the stream. It also may write additional information about the set.
18.2/3
  {AI05-0001-1} {AI05-0262-1} 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.
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.3/5
{AI12-0112-1} function Has_Element (Position : Cursor) return Boolean
   with Nonblocking, Global => (in alluse null)
;
18.4/3
{AI05-0212-1} Returns True if Position designates an element, and returns False otherwise.
18.c/3
To be honest: {AI05-0005-1} {AI05-0212-1} This function might 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). 
18.5/5
{AI12-0112-1} function Has_Element (Container : Set; Position : Cursor)
   return Boolean
   with Nonblocking, Global => (nulluse null);
18.6/5
{AI12-0112-1} Returns True if Position designates an element in Container, and returns False otherwise.
18.d/5
Ramification: {AI12-0112-1} If Position is No_Element, Has_Element returns False. 
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.
22.1/5
function Tampering_With_Cursors_Prohibited
   (Container : Set) return Boolean
   with Nonblocking, Global => (nulluse null);
22.2/5
{AI12-0112-1} Returns True if tampering with cursors is currently prohibited for Container, and returns False otherwise.
22.a/5
Implementation Note: {AI12-0112-1} Various contracts elsewhere in this specification require that this function is implemented with synchronized data. Moreover, it is possible for tampering to be prohibited by multiple operations (sequentiually or in parallel). Therefore, tampering needs to be implemented with an atomic or protected counter. The counter is initialized to zero, and is incremented when tampering is prohibited, and decremented when leaving an area that prohibited tampering. Function Tampering_With_Cursors_Prohibited returns True if the counter is nonzero. (Note that any case where the result is not well-defined for one task is incorrect use of shared variables and would be erroneous by the rules of 9.10, so no special protection is needed to read the counter.) 
23/5
{AI12-0112-1} function To_Set (New_Item : Element_Type) return Set
   with Post => Length (To_Set'Result) = 1 and then
              not Tampering_with_Cursors_Prohibited (To_Set'Result)
;
24/2
{AI95-00302-03} Returns a set containing the single element New_Item.
25/5
{AI12-0112-1} function Length (Container : Set) return Count_Type
   with Nonblocking, Global => (nulluse null)
;
26/2
{AI95-00302-03} Returns the number of elements in Container.
27/5
function Is_Empty (Container : Set) return Boolean
   with Nonblocking, Global => (nulluse null),
        Post => Is_Empty'Result = (Length (Container) = 0)
;
28/5
{AI95-00302-03} {AI12-0112-1} Returns True if Container is empty Equivalent to Length (Container) = 0.
29/5
{AI12-0112-1} procedure Clear (Container : in out Set)
   with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error,
        Post => Length (Container) = 0
;
30/2
{AI95-00302-03} Removes all the elements from Container.
31/5
function Element (Position : Cursor) return Element_Type
   with Pre  => Position /= No_Element or else raise Constraint_Error,
        Nonblocking => Element_Type'Nonblocking,
        Global => (in alluse Element_Type)
;
32/5
{AI95-00302-03} {AI12-0112-1} If Position equals No_Element, then Constraint_Error is propagated. Otherwise, Element returns the element designated by Position.
32.1/5
function Element (Container : Set;
                  Position  : Cursor) return Element_Type
   with Pre  => (Position /= No_Element
                    or else raise Constraint_Error) and then
                (Has_Element (Container, Position)
                    or else raise Program_Error),
        Nonblocking => Element_Type'Nonblocking,
        Global => (nulluse Element_Type);
32.2/5
{AI12-0112-1} Element returns the element designated by Position.
33/5
procedure Replace_Element (Container : in out Set;
                           Position  : in     Cursor;
                           New_item  : in     Element_Type)
   with Pre  => (not Tampering_With_Elements_Prohibited (Container)
                   or else raise Program_Error) and then
                (Position /= No_Element 
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position) or else raise Program_Error)
;
34/5
{AI95-00302-03} {AI12-0112-1} {AI12-0196-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. 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. For the purposes of determining whether the parameters overlap in a call to Replace_Element, the Container parameter is not considered to overlap with any object [(including itself)].
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/5
procedure Query_Element
  (Position : in Cursor;
   Process  : not null access procedure (Element : in Element_Type))
   with Pre  => Position /= No_Element or else raise Constraint_Error,
        Global => in all
;
36/5
{AI95-00302-03} {AI05-0021-1} {AI05-0265-1} {AI12-0112-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 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.
36.1/5
procedure Query_Element
  (Container : in Set;
   Position  : in Cursor;
   Process  : not null access procedure (Element : in Element_Type))
   with Pre  => (Position /= No_Element 
                    or else raise Constraint_Error) and then
                 (Has_Element (Container, Position) 
                    or else raise Program_Error);
36.2/5
{AI12-0112-1} Query_Element calls Process.all with the key and element from the node designated by Position as the arguments. 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.
36.3/5
{AI12-0112-1} type Constant_Reference_Type
      (Element : not null access constant Element_Type) is private
   with Implicit_Dereference => Element,
        Nonblocking, Global => in out synchronized,
        Default_Initial_Condition => (raise Program_Error)
;
36.4/3
{AI05-0212-1} The type Constant_Reference_Type needs finalization.
36.5/5
This paragraph was deleted.{AI12-0112-1} 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.6/5
{AI12-0112-1} function Constant_Reference (Container : aliased in Set;
                             Position  : in Cursor)
   return Constant_Reference_Type
   with Pre  => (Position /= No_Element
                    or else raise Constraint_Error) and then
                (Has_Element (Container, Position)
                    or else raise Program_Error),
        Nonblocking, Global => (nulluse null)
;
36.7/3
{AI05-0212-1} {AI05-0269-1} 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.
36.8/5
{AI05-0212-1} {AI05-0265-1} {AI12-0112-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 cursors elements of Container is prohibited while the object returned by Constant_Reference exists and has not been finalized.
36.9/5
{AI12-0112-1} procedure Assign (Target : in out Set; Source : in Set)
   with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                   or else raise Program_Error,
        Post => Length (Source) = Length (Target)
;
36.10/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/5
{AI12-0112-1} procedure Move (Target : in out Set;
                Source : in out Set)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Target)
                    or else raise Program_Error) and then
                (not Tampering_With_Cursors_Prohibited (Source)
                    or else raise Program_Error),
        Post => (if Target = Source then True
                 else
                    Length (Target) = Length (Source'Old) and then
                    Length (Source) = 0)
;
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 has no effect. Otherwise, the operation is equivalent to Assign (Target, Source) followed by Clear (Source).
39/5
{AI12-0112-1} procedure Insert (Container : in out Set;
                  New_Item  : in     Element_Type;
                  Position  :    out Cursor;
                  Inserted  :    out Boolean)
   with Pre  => (not Tampering_With_Elements_Prohibited (Container)
                   or else raise Program_Error) and then
                (Length (Container) <= Count_Type'Last - 1
                    or else raise Constraint_Error),
        Post => (declare
                   Original_Length : constant Count_Type :=
                      Length (Container)'Old;
                 begin
                   Has_Element (Container, Position) and then
                  (if Inserted then
                     Length (Container) = Original_Length + 1
                   else
                     Length (Container) = Original_Length))
;
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/5
{AI12-0112-1} procedure Insert (Container : in out Set;
                  New_Item  : in     Element_Type)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error) and then
                (Length (Container) <= Count_Type'Last - 1
                    or else raise Constraint_Error),
        Post => Length (Container) = Length (Container)'Old + 1
;
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/5
{AI12-0112-1} procedure Include (Container : in out Set;
                   New_Item  : in     Element_Type)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error) and then
                (Length (Container) <= Count_Type'Last - 1
                    or else raise Constraint_Error),
        Post => (declare
                   Original_Length : constant Count_Type :=
                      Length (Container)'Old;
                 begin
                   Length (Container)
                      in Original_Length | Original_Length + 1)
;
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/5
{AI12-0112-1} procedure Replace (Container : in out Set;
                   New_Item  : in     Element_Type)
   with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error,
        Post => Length (Container) = Length (Container)'Old
;
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/5
{AI12-0112-1} procedure Exclude (Container : in out Set;
                   Item       : in     Element_Type)
   with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error,
        Post => (declare
                   Original_Length : constant Count_Type :=
                      Length (Container)'Old;
                 begin
                   Length (Container) in
                      Original_Length - 1 | Original_Length)
;
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/5
{AI12-0112-1} procedure Delete (Container : in out Set;
                  Item       : in     Element_Type)
   with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error,
        Post => Length (Container) = Length (Container)'Old - 1
;
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/5
procedure Delete (Container : in out Set;
                  Position  : in out Cursor)
   with Pre  => (not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error) and then
                (Position /= No_Element 
                    or else raise Constraint_Error) and then
                (Has_Element (Container, Position)
                    or else raise Program_Error),
        Post => Length (Container) = Length (Container)'Old - 1 and then
                Position = No_Element
;
52/5
{AI95-00302-03} {AI12-0112-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, 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/5
{AI12-0112-1} procedure Union (Target : in out Set;
                 Source : in     Set)
   with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                    or else raise Program_Error,
        Post => Length (Target) <= Length (Target)'Old + Length (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
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/5
{AI12-0112-1} function Union (Left, Right : Set) return Set
   with Post => Length (Union'Result) <= Length (Left) + Length (Right) and then
                not Tampering_With_Cursors_Prohibited (Union'Result)
;
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/5
{AI12-0112-1} procedure Intersection (Target : in out Set;
                        Source : in     Set)
   with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                    or else raise Program_Error,
        Post => Length (Target) <= Length (Target)'Old + Length (Source)
;
58/3
{AI95-00302-03} {AI05-0004-1} Intersection 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/5
{AI12-0112-1} function Intersection (Left, Right : Set) return Set
   with Post => Length (Intersection'Result) <= Length (Left) + Length (Right) and then
                not Tampering_With_Cursors_Prohibited (Intersection'Result)
;
60/2
{AI95-00302-03} Returns a set comprising all the elements of Left that are equivalent to the some element of Right.
61/5
{AI12-0112-1} procedure Difference (Target : in out Set;
                      Source : in     Set)
   with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                    or else raise Program_Error,
        Post => Length (Target) <= Length (Target)'Old + Length (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/5
{AI12-0112-1} function Difference (Left, Right : Set) return Set
   with Post => Length (Difference'Result) <= Length (Left) + Length (Right) and then
                not Tampering_With_Cursors_Prohibited (Difference'Result)
;
64/2
{AI95-00302-03} Returns a set comprising the elements of Left that are not equivalent to some element of Right.
65/5
{AI12-0112-1} procedure Symmetric_Difference (Target : in out Set;
                                Source : in     Set)
   with Pre  => not Tampering_With_Cursors_Prohibited (Target)
                    or else raise Program_Error,
        Post => Length (Target) <= Length (Target)'Old + Length (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/5
{AI12-0112-1} function Symmetric_Difference (Left, Right : Set) return Set
   with Post => Length (Symmetric_Difference'Result) <= Length (Left) + Length (Right) and then
                not Tampering_With_Cursors_Prohibited (Symmetric_Difference'Result)
;
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/5
{AI12-0112-1} function First (Container : Set) return Cursor
   with Nonblocking, Global => (nulluse null),
        Post => (if not Is_Empty (Container)
                 then Has_Element (Container, First'Result)
                 else First'Result = No_Element)
;
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/5
{AI12-0112-1} function Next (Position : Cursor) return Cursor
   with Nonblocking, Global => (in alluse null),
        Post => (if Position = No_Element then Next'Result = No_Element
                 else True)
;
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.
76.1/5
function Next (Container : Set;
               Position  : Cursor) return Cursor
   with Nonblocking, Global => (nulluse null),
        Pre  => Position = No_Element or else
                Has_Element (Container, Position)
                    or else raise Program_Error,
        Post => (if Position = No_Element then Next'Result = No_Element
                 elsif Next'Result = No_Element then
                    Position = Last (Container)
                 else Has_Element (Container, Next'Result));
76.2/5
{AI12-0112-1} Returns a cursor designating the successor of the node designated by Position in Container.
77/5
{AI12-0112-1} procedure Next (Position : in out Cursor)
   with Nonblocking, Global => (in alluse null)
;
78/2
{AI95-00302-03} Equivalent to Position := Next (Position).
78.1/5
procedure Next (Container : in     Set;
                Position  : in out Cursor)
   with Nonblocking, Global => (nulluse null),
        Pre  => Position = No_Element or else
                Has_Element (Container, Position)
                    or else raise Program_Error,
        Post => (if Position /= No_Element
                 then Has_Element (Container, Position));
78.2/5
{AI12-0112-1} Equivalent to Position := Next (Container, Position).
79/3
This paragraph was deleted.{AI95-00302-03} {AI05-0004-1}
80/5
{AI12-0112-1} function Find (Container : Set;
               Item      : Element_Type) return Cursor
      with Post => (if Find'Result = No_Element then True
                    else Has_Element (Container, Find'Result))
;
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
84/3
{AI95-00302-03} {AI05-0212-1}
84.a/3
{AI05-0212-1}
Paragraphs 83 and 84 were moved above. 
85/5
{AI12-0112-1} procedure Iterate
  (Container : in Set;
   Process   : not null access procedure (Position : in Cursor))
   with Allows_Exit
;
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 with the cursors of Container is prohibited during the execution of a call on 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/5
{AI12-0112-1} function Key (Position : Cursor) return Key_Type
   with Pre  => Position /= No_Element or else raise Constraint_Error,
        Global => in all
;
90/2
{AI95-00302-03} Equivalent to Key (Element (Position)).
90.1/5
function Key (Container : Set;
              Position : Cursor) return Key_Type
   with Pre  => (Position /= No_Element 
                   or else raise Constraint_Error) and then
                (Has_Element (Container, Position)
                   or else raise Program_Error);
90.2/5
{AI12-0112-1} Equivalent to Key (Element (Container, 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/5
{AI12-0112-1} procedure Replace (Container : in out Set;
                   Key       : in     Key_Type;
                   New_Item  : in     Element_Type)
   with Pre  => not Tampering_With_Cursors_Prohibited (Container)
                    or else raise Program_Error,
        Post => Length (Container) = Length (Container)'Old
;
93/2
{AI95-00302-03} Equivalent to Replace_Element (Container, Find (Container, Key), New_Item).
94/5
procedure Update_Element_Preserving_Key
  (Container : in out Set;
   Position  : in     Cursor;
   Process   : not null access procedure
                                 (Element : in out Element_Type))
   with Pre  => (Position /= No_Element 
                    or else raise Constraint_Error) and then
                 (Has_Element (Container, Position) 
                    or else raise Program_Error)
;
95/5
{AI95-00302-03} {AI05-0265-1} {AI12-0112-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 with the cursors 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.
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/5
{AI12-0112-1} type Reference_Type (Element : not null access Element_Type) is private
   with Implicit_Dereference => Element,
        Nonblocking, Global => in out synchronized,
        Default_Initial_Condition => (raise Program_Error)
;
96.2/3
{AI05-0212-1} The type Reference_Type needs finalization.
96.3/5
This paragraph was deleted.{AI12-0112-1} The default initialization of an object of type Reference_Type propagates Program_Error.
96.4/5
{AI12-0112-1} function Reference_Preserving_Key (Container : aliased in out Set;
                                   Position  : in Cursor)
   return Reference_Type
   with Pre  => (Position /= No_Element
                    or else raise Constraint_Error) and then
                (Has_Element (Container, Position)
                    or else raise Program_Error),
        Post => Tampering_With_Cursors_Prohibited (Container)
;
96.5/3
{AI05-0212-1} {AI05-0269-1} 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.
96.6/5
{AI05-0212-1} {AI05-0265-1} {AI12-0112-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 cursors 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/5
{AI12-0112-1} function Constant_Reference (Container : aliased in Set;
                             Key       : in Key_Type)
   return Constant_Reference_Type
   with Pre  => Find (Container, Key) /= No_Element or else raise Constraint_Error,
        Post => Tampering_With_Cursors_Prohibited (Container)
;
96.8/3
{AI05-0212-1} {AI05-0269-1} 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.
96.9/3
Equivalent to Constant_Reference (Container, Find (Container, Key)).
96.10/5
{AI12-0112-1} function Reference_Preserving_Key (Container : aliased in out Set;
                                   Key       : in Key_Type)
   return Reference_Type
   with Pre  => Find (Container, Key) /= No_Element or else raise Constraint_Error,
        Post => Tampering_With_Cursors_Prohibited (Container)
;
96.11/3
{AI05-0212-1} {AI05-0269-1} 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.
96.12/3
Equivalent to Reference_Preserving_Key (Container, Find (Container, Key)). 
96.13/5
   {AI12-0111-1} The nested package Stable provides a type Stable.Set that represents a stable set, which is one that cannot grow and shrink. Such a list can be created by calling the Copy function, or by establishing a stabilized view of a regular set.
96.14/5
   {AI12-0111-1} The subprograms of the set package that have a parameter or result of type Set are included in the nested package Stable with the same specification, except that the following are omitted:
96.15/5
Tampering_With_Cursors_Prohibited, Assign, Move, Insert, Include, Clear, Delete, Exclude, Replace, Replace_Element, procedures Union, Intersection, Difference, and Symmetric_Difference, (for Ordered_sets) Delete_First and Delete_Last, and (for Hashed_sets) Reserve_Capacity 
96.a.1/5
Discussion: The Generic_Keys package is not included in the Stable package. The functions Union, Intersection, Difference, and Symmetric_Difference are included in the Stable package. 
96.a.2/5
Ramification: The names Set and Cursor mean the types declared in the nested package in these subprogram specifications. 
96.a.3/5
Reason: The omitted routines are those that tamper with cursors (or test that state). The model is that it is impossible to tamper with cursors of a stable view since no such operations are included. Thus tampering checks are not needed for a stable view, and we omit the operations associated with those checks. 
96.16/5
   {AI12-0111-1} The operations of this package are equivalent to those for regular sets, except that the calls to Tampering_With_Cursors_Prohibited that occur in preconditions are replaced by False, and any that occur in postconditions are replaced by True.
96.17/5
   {AI12-0111-1} If a stable set is declared with the Base discriminant designating a pre-existing regular set, the stable set represents a stabilized view of the underlying regular set, and any operation on the stable set is reflected on the underlying regular set. While a stabilized view exists, any operation that tampers with cursors performed on the underlying set is prohibited. The finalization of a stable set that provides such a view removes this restriction on the underlying regular set [(though some other restriction might exist due to other concurrent iterations or stabilized views)].
96.18/5
   {AI12-0111-1} If a stable set is declared without specifying Base, the object must be initialized. The initializing expression of the stable set, [typically a call on Copy], determines the Length of the set. The Length of a stable set never changes after initialization.

Bounded (Run-Time) Errors

96.19/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.20/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 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 nonexistent 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/3
Implementation Note: {AI05-0298-1} 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. (Note that this implementation would require care, see A.18.2 for more.)

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.

Inconsistencies With Ada 2012

105.k/5
{AI12-0111-1} Procedures Union, Intersection, Difference, and Symmeteric_Difference are now defined to tamper with the cursors of the Target parameter. A program which attempts to use one of these operations while tampering is prohibited will raise Program_Error. However, since the operations do modify the container, the effects would have been unpredictable, so this change will likely fix bugs.

Extensions to Ada 2012

105.l/5
{AI12-0196-1} Correction: Replace_Element is now defined such that it can be used concurrently so long as it operates on different elements. This allows some container operations to be used in parallel without separate synchronization. 

Wording Changes from Ada 2012

105.m/4
{AI12-0110-1} Corrigendum: Clarified that tampering checks precede all other checks made by a subprogram (but come after those associated with the call).
105.n/5
{AI12-0112-1} Added contracts to this container. This includes describing some of the semantics with pre- and postconditions, rather than English text. Note that the preconditions can be Suppressed (see 11.5). 

Contents   Index   References   Search   Previous   Next 
Ada-Europe Ada 2005 and 2012 Editions sponsored in part by Ada-Europe