A.18.9 The Generic Package Containers.Ordered_Sets
Static Semantics
1/2
{
AI95-00302-03}
The generic library package Containers.Ordered_Sets
has the following declaration: 2/3
{
AI05-0084-1}
{
AI05-0212-1}
with Ada.Iterator_Interfaces;
generic
type Element_Type is private;
with function "<" (Left, Right : Element_Type) return Boolean is <>;
with function "=" (Left, Right : Element_Type) return Boolean is <>;
package Ada.Containers.Ordered_Sets is
pragma Preelaborate(Ordered_Sets);
pragma Remote_Types(Ordered_Sets);3/2
function Equivalent_Elements (Left, Right : Element_Type) return Boolean;
4/3
{
AI05-0212-1}
type Set is tagged private
with Constant_Indexing => Constant_Reference,
Default_Iterator => Iterate,
Iterator_Element => Element_Type;
pragma Preelaborable_Initialization(Set);5/2
type Cursor is private;
pragma Preelaborable_Initialization(Cursor);
6/2
Empty_Set : constant Set;
7/2
No_Element : constant Cursor;
7.1/3
{
AI05-0212-1}
function Has_Element (Position : Cursor) return Boolean;7.2/3
{
AI05-0212-1}
package Set_Iterator_Interfaces is new
Ada.Iterator_Interfaces (Cursor, Has_Element);8/2
function "=" (Left, Right : Set) return Boolean;
9/2
function Equivalent_Sets (Left, Right : Set) return Boolean;
10/2
function To_Set (New_Item : Element_Type) return Set;
11/2
function Length (Container : Set) return Count_Type;
12/2
function Is_Empty (Container : Set) return Boolean;
13/2
procedure Clear (Container : in out Set);
14/2
function Element (Position : Cursor) return Element_Type;
15/2
procedure Replace_Element (Container : in out Set;
Position : in Cursor;
New_Item : in Element_Type);
16/2
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
16.1/3
{
AI05-0212-1}
type Constant_Reference_Type
(Element : not null access constant Element_Type) is private
with Implicit_Dereference => Element;16.2/3
{
AI05-0212-1}
function Constant_Reference (Container : aliased in Set;
Position : in Cursor)
return Constant_Reference_Type;16.3/3
{
AI05-0001-1}
procedure Assign (Target : in out Set; Source : in Set);16.4/3
17/2
procedure Move (Target : in out Set;
Source : in out Set);
18/2
procedure Insert (Container : in out Set;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
19/2
procedure Insert (Container : in out Set;
New_Item : in Element_Type);
20/2
procedure Include (Container : in out Set;
New_Item : in Element_Type);
21/2
procedure Replace (Container : in out Set;
New_Item : in Element_Type);
22/2
procedure Exclude (Container : in out Set;
Item : in Element_Type);
23/2
procedure Delete (Container : in out Set;
Item : in Element_Type);
24/2
procedure Delete (Container : in out Set;
Position : in out Cursor);
25/2
procedure Delete_First (Container : in out Set);
26/2
procedure Delete_Last (Container : in out Set);
27/2
procedure Union (Target : in out Set;
Source : in Set);
28/2
function Union (Left, Right : Set) return Set;
29/2
function "or" (Left, Right : Set) return Set renames Union;
30/2
procedure Intersection (Target : in out Set;
Source : in Set);
31/2
function Intersection (Left, Right : Set) return Set;
32/2
function "and" (Left, Right : Set) return Set renames Intersection;
33/2
procedure Difference (Target : in out Set;
Source : in Set);
34/2
function Difference (Left, Right : Set) return Set;
35/2
function "-" (Left, Right : Set) return Set renames Difference;
36/2
procedure Symmetric_Difference (Target : in out Set;
Source : in Set);
37/2
function Symmetric_Difference (Left, Right : Set) return Set;
38/2
function "xor" (Left, Right : Set) return Set renames
Symmetric_Difference;
39/2
function Overlap (Left, Right : Set) return Boolean;
40/2
function Is_Subset (Subset : Set;
Of_Set : Set) return Boolean;
41/2
function First (Container : Set) return Cursor;
42/2
function First_Element (Container : Set) return Element_Type;
43/2
function Last (Container : Set) return Cursor;
44/2
function Last_Element (Container : Set) return Element_Type;
45/2
function Next (Position : Cursor) return Cursor;
46/2
procedure Next (Position : in out Cursor);
47/2
function Previous (Position : Cursor) return Cursor;
48/2
procedure Previous (Position : in out Cursor);
49/2
function Find (Container : Set;
Item : Element_Type)
return Cursor;
50/2
function Floor (Container : Set;
Item : Element_Type)
return Cursor;
51/2
function Ceiling (Container : Set;
Item : Element_Type)
return Cursor;
52/2
function Contains (Container : Set;
Item : Element_Type) return Boolean;
53/3
This paragraph
was deleted. {
AI05-0212-1}
function Has_Element (Position : Cursor) return Boolean;
54/2
function "<" (Left, Right : Cursor) return Boolean;
55/2
function ">" (Left, Right : Cursor) return Boolean;
56/2
function "<" (Left : Cursor; Right : Element_Type)
return Boolean;
57/2
function ">" (Left : Cursor; Right : Element_Type)
return Boolean;
58/2
function "<" (Left : Element_Type; Right : Cursor)
return Boolean;
59/2
function ">" (Left : Element_Type; Right : Cursor)
return Boolean;
60/2
procedure Iterate
(Container : in Set;
Process : not null access procedure (Position : in Cursor));
61/2
procedure Reverse_Iterate
(Container : in Set;
Process : not null access procedure (Position : in Cursor));
61.1/3
{
AI05-0212-1}
function Iterate (Container : in Set)
return Set_Iterator_Interfaces.Reversible_Iterator'Class;62/2
generic
type Key_Type (<>) is private;
with function Key (Element : Element_Type) return Key_Type;
with function "<" (Left, Right : Key_Type)
return Boolean is <>;
package Generic_Keys is
63/2
function Equivalent_Keys (Left, Right : Key_Type)
return Boolean;
64/2
function Key (Position : Cursor) return Key_Type;
65/2
function Element (Container : Set;
Key : Key_Type)
return Element_Type;
66/2
procedure Replace (Container : in out Set;
Key : in Key_Type;
New_Item : in Element_Type);
67/2
procedure Exclude (Container : in out Set;
Key : in Key_Type);
68/2
procedure Delete (Container : in out Set;
Key : in Key_Type);
69/2
function Find (Container : Set;
Key : Key_Type)
return Cursor;
70/2
function Floor (Container : Set;
Key : Key_Type)
return Cursor;
71/2
function Ceiling (Container : Set;
Key : Key_Type)
return Cursor;
72/2
function Contains (Container : Set;
Key : Key_Type) return Boolean;
73/2
procedure Update_Element_Preserving_Key
(Container : in out Set;
Position : in Cursor;
Process : not null access procedure
(Element : in out Element_Type));
73.1/3
{
AI05-0212-1}
type Reference_Type (Element : not null access Element_Type) is private
with Implicit_Dereference => Element;73.2/3
{
AI05-0212-1}
function Reference_Preserving_Key (Container : aliased in out Set;
Position : in Cursor)
return Reference_Type;73.3/3
{
AI05-0212-1}
function Constant_Reference (Container : aliased in Set;
Key : in Key_Type)
return Constant_Reference_Type;73.4/3
{
AI05-0212-1}
function Reference_Preserving_Key (Container : aliased in out Set;
Key : in Key_Type)
return Reference_Type;74/2
end Generic_Keys;
75/2
private
76/2
... -- not specified by the language
77/2
end Ada.Containers.Ordered_Sets;
78/2
{
AI95-00302-03}
Two elements E1 and E2 are equivalent
if both E1 < E2 and E2 < E1 return
False, using the generic formal "<" operator for elements.
Function Equivalent_Elements returns True if Left and Right are equivalent,
and False otherwise.79/3
{
AI95-00302-03}
{
AI05-0044-1}
The actual function for the generic formal function
"<" on Element_Type values is expected to return the same
value each time it is called with a particular pair of key values. It
should define a strict weak ordering
relationship (see A.18),
that is, be irreflexive, asymmetric, and transitive.
If the actual for "<" behaves in some other manner, the
behavior of this package is unspecified. Which subprograms of this package
call "<" and how many times they call it, is unspecified.79.1/3
{
AI05-0044-1}
If the actual function for the generic formal function
"=" returns True for any pair of non-equivalent elements, then
the behavior of the container function "=" is unspecified.80/2
{
AI95-00302-03}
If the value of an element stored in a set is changed
other than by an operation in this package such that at least one of
"<" or "=" give different results, the behavior
of this package is unspecified.80.a/2
81/3
{
AI95-00302-03}
{
AI05-0262-1}
The
first element first
element of a nonempty set is the
one which is less than all the other elements in the set. The last
element last
element of a nonempty set is the
one which is greater than all the other elements in the set. The successor successor of an element is the smallest element that is larger than the given element.
The predecessor predecessor of an element is the largest element that is smaller than the given element.
All comparisons are done using the generic formal "<" operator
for elements.81.1/3
function Copy (Source : Set) return Set;
81.2/3
{
AI05-0001-1}
Returns a set whose elements are initialized from
the corresponding elements of Source.82/2
procedure Delete_First (Container : in out Set);
83/3
{
AI95-00302-03}
{
AI05-0264-1}
If Container is empty, Delete_First has no effect.
Otherwise, the element designated by First (Container) is removed from Container.
Delete_First tampers with the cursors of Container.84/2
procedure Delete_Last (Container : in out Set);
85/3
{
AI95-00302-03}
{
AI05-0264-1}
If Container is empty, Delete_Last has no effect.
Otherwise, the element designated by Last (Container) is removed from Container.
Delete_Last tampers with the cursors of Container.86/2
function First_Element (Container : Set) return Element_Type;
87/2
88/2
function Last (Container : Set) return Cursor;
89/2
{
AI95-00302-03}
Returns a cursor that designates the last element
in Container. If Container is empty, returns No_Element.90/2
function Last_Element (Container : Set) return Element_Type;
91/2
92/2
function Previous (Position : Cursor) return Cursor;
93/3
{
AI95-00302-03}
{
AI05-0262-1}
If Position equals No_Element, then Previous returns
No_Element. Otherwise, Previous returns a cursor designating the predecessor
element of that
precedes the one designated by Position.
If Position designates the first element, then Previous returns No_Element.94/2
procedure Previous (Position : in out Cursor);
95/2
96/2
function Floor (Container : Set;
Item : Element_Type) return Cursor;
97/3
{
AI95-00302-03}
{
AI05-0264-1}
Floor searches for the last element which is not
greater than Item. If such an element is found, a cursor that designates
it is returned. Otherwise, No_Element is returned.98/2
function Ceiling (Container : Set;
Item : Element_Type) return Cursor;
99/3
{
AI95-00302-03}
{
AI05-0264-1}
Ceiling searches for the first element which is
not less than Item. If such an element is found, a cursor that designates
it is returned. Otherwise, No_Element is returned.100/2
function "<" (Left, Right : Cursor) return Boolean;
101/2
102/2
function ">" (Left, Right : Cursor) return Boolean;
103/2
104/2
function "<" (Left : Cursor; Right : Element_Type) return Boolean;
105/2
106/2
function ">" (Left : Cursor; Right : Element_Type) return Boolean;
107/2
108/2
function "<" (Left : Element_Type; Right : Cursor) return Boolean;
109/2
110/2
function ">" (Left : Element_Type; Right : Cursor) return Boolean;
111/2
112/2
procedure Reverse_Iterate
(Container : in Set;
Process : not null access procedure (Position : in Cursor));
113/3
{
AI95-00302-03}
{
AI05-0212-1}
Iterates over the elements in Container as per
procedure Iterate,
with the difference that the elements are traversed in predecessor order,
starting with the last element.113.1/3
function Iterate (Container : in Set)
return Set_Iterator_Interfaces.Reversible_Iterator'Class;
113.2/3
{
AI05-0212-1}
{
AI05-0265-1}
Iterate returns a reversible iterator object that
will generate a value for the loop parameter designating each element
in Container, starting with the first element and moving the cursor according
to the successor relation when used as a forward iterator, and starting
with the last element and moving the cursor according to the predecessor
relation when used as a reverse iterator. Tampering with the cursors
of Container is prohibited while the iterator object exists (in particular,
in the sequence_of_statements
of the loop_statement
whose iterator_specification
denotes this object). The iterator object needs finalization.114/2
{
AI95-00302-03}
For any two elements E1 and E2, the
boolean values (E1 < E2) and (Key(E1) < Key(E2))
are expected to be equal. If the actuals for Key or Generic_Keys."<"
behave in some other manner, the behavior of this package is unspecified.
Which subprograms of this package call Key and Generic_Keys."<",
and how many times the functions are called, is unspecified.115/2
{
AI95-00302-03}
In addition to the semantics described in A.18.7,
the subprograms in package Generic_Keys named Floor and Ceiling, are
equivalent to the corresponding subprograms in the parent package, with
the difference that the Key subprogram parameter is compared to elements
in the container using the Key and "<" generic formal functions.
The function named Equivalent_Keys in package Generic_Keys returns True
if both Left < Right and Right < Left return False using the generic
formal "<" operator, and returns True otherwise.Implementation Advice
116/2
{
AI95-00302-03}
If N is the length of a set, then the worst-case
time complexity of the Insert, Include, Replace, Delete, Exclude and
Find operations that take an element parameter should be O((log
N)**2) or better. The worst-case time complexity of the subprograms
that take a cursor parameter should be O(1). 116.a/2
Implementation Advice:
The worst-case time complexity of the
Insert, Include, Replace, Delete, Exclude and Find operations of Containers.Ordered_Sets
that take an element parameter should be O((log N)**2).
The worst-case time complexity of the subprograms of Containers.Ordered_Sets
that take a cursor parameter should be O(1).
116.b/2
Extensions to Ada 95
116.c/2
{
AI95-00302-03}
The generic package Containers.Ordered_Sets
is new. Incompatibilities With Ada 2005
116.d/3
{
AI05-0001-1}
Subprograms Assign and Copy
are newly added to Containers.Ordered_Sets. If an instance of Containers.Ordered_Sets
is referenced in a use_clause,
and an entity E with the same defining_identifier
as a new entity in Containers.Ordered_Sets is defined in a package that
is also referenced in a use_clause,
the entity E may no longer be use-visible, resulting in errors.
This should be rare and is easily fixed if it does occur. Extensions to Ada 2005
116.e/3
{
AI05-0212-1}
Added iterator and indexing
support to make ordered set containers more convenient to use.
Wording Changes from Ada 2005
116.f/3
{
AI05-0044-1}
Correction: Added wording to require the
formal function be such that equal elements are also equivalent.116.g/3
{
AI05-0044-1}
Correction: Redefined "<" actuals
to require a strict weak ordering; the old definition allowed indeterminant
comparisons that would not have worked in a container.116.h/3
{
AI05-0084-1}
Correction: Added a pragma Remote_Types
so that containers can be used in distributed programs.
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
