CVS difference for ais/ai-20302.txt
--- ais/ai-20302.txt 2005/06/16 23:47:50 1.21
+++ ais/ai-20302.txt 2005/08/21 06:00:46 1.22
@@ -1,4 +1,4 @@
-!standard A.18 (00) 05-05-13 AI95-00302-03/13
+!standard A.18 (00) 05-07-26 AI95-00302-03/14
!standard A.18.1 (00)
!standard A.18.2 (00)
!standard A.18.3 (00)
@@ -128,7 +128,7 @@
thus preserving constant time complexity for insertions.
The ordered map associative containers maintains the keys in sort order.
-Insertions and searches have O(log N) time complexity even inthe worst case.
+Insertions and searches have O(log N) time complexity even in the worst case.
The hashed set associative containers scatter elements in the container
according to a hash function. The size of the hash table is automatically
@@ -167,7 +167,8 @@
!wording
-Add Ada.Strings.Hash and Ada.Strings.Unbounded.Hash to A.4.7(1) and A.4.7(29).
+Add Ada.Strings.Hash, Ada.Strings.Fixed.Hash, Ada.Strings.Bounded.Hash, and
+Ada.Strings.Unbounded.Hash to A.4.7(1) and A.4.7(29).
[This gives us Wide_ versions of these functions.]
@@ -180,24 +181,44 @@
with Ada.Containers;
function Ada.Strings.Hash (Key : String) return Containers.Hash_Type;
-pragma Pure (Ada.Strings.Hash);
+pragma Pure (Hash);
-Return an implementation-defined value which is a function of the value of Key.
+Returns an implementation-defined value which is a function of the value of Key.
If A and B are strings such that A equals B, Hash(A) equals Hash(B).
+The library function Strings.Fixed.Hash has the following declaration:
+
+with Ada.Containers, Ada.Strings.Hash;
+function Ada.Strings.Fixed.Hash (Key : String) return Containers.Hash_Type
+ renames Ada.Strings.Hash;
+pragma Pure (Hash);
+
+The generic library function Strings.Bounded.Hash has the following declaration:
+
+with Ada.Containers;
+generic
+ with package Bounded is
+ new Ada.Strings.Bounded.Generic_Bounded_Length (<>);
+function Ada.Strings.Bounded.Hash (Key : Bounded.Bounded_String)
+ return Containers.Hash_Type;
+pragma Preelaborate (Hash);
+
+Strings.Bounded.Hash is equivalent to the function call
+Strings.Hash (Bounded.To_String (Key));
+
The library function Strings.Unbounded.Hash has the following declaration:
with Ada.Containers;
-function Ada.Strings.Unbounded.Hash (Key : Unbounded_String) return
- Containers.Hash_Type;
-pragma Preelaborate (Ada.Strings.Unbounded.Hash);
+function Ada.Strings.Unbounded.Hash (Key : Unbounded_String)
+ return Containers.Hash_Type;
+pragma Preelaborate (Hash);
-Return an implementation-defined value which is a function of the value of Key.
-If A and B are unbounded strings such that A equals B, Hash(A) equals Hash(B).
+Strings.Unbounded.Hash is equivalent to the function call
+Strings.Hash (To_String (Key));
Implementation Advice
-The various Hash functions should be good hash functions, returning
+The Hash functions should be good hash functions, returning
a wide spread of values for different string values. It should be unlikely
for similar strings to return the same value.
@@ -209,15 +230,18 @@
A variety of sequence and associative containers are provided. Each container
includes a *cursor* type. A cursor is a reference to an element within a
-container. Many operations on cursors are common to all of the containers.
+container. Many operations on cursors are common to all of the containers. A
+cursor referencing an element in a container is considered to be overlapping
+with the container object itself.
Within this clause we provide Implementation Advice for the desired
average or worst case time complexity of certain operations on a
-container. This advice is expressed using a big-O notation.
-A complexity of O(f(N)), presuming f is some function of a
+container. This advice is expressed using the Landau symbol O(X).
+Presuming f is some function of a
length parameter N and t(N) is the time the operation takes
-(on average or worst case, as specified) for the length N,
-means that there exists a finite A such that for any N, t(N)/f(N) < A.
+(on average or worst case, as specified) for the length N, a
+complexity of O(f(N)) means that there exists a finite A such
+that for any N, t(N)/f(N) < A.
AARM Note: Of course, an implementation can do better than a specified
O(f(N)): for example, O(1) meets the requirements for O(log N).
@@ -382,6 +406,10 @@
elements that can be inserted into the vector prior to it being automatically
expanded.
+Elements in a vector container can be refered to by an index value of a
+generic formal type. The first element of a vector always has its index
+value equal to the lower bound of the formal type.
+
A vector container may contain *empty elements*. Empty elements do not have a
specified value.
@@ -414,8 +442,6 @@
Index_Type'Min (Index_Type'Base'Last - 1, Index_Type'Last) + 1;
No_Index : constant Extended_Index := Extended_Index'First;
- subtype Index_Subtype is Index_Type;
-
type Vector is tagged private;
pragma Preelaborable_Initialization(Vector);
@@ -426,6 +452,8 @@
No_Element : constant Cursor;
+ function "=" (Left, Right : Vector) return Boolean;
+
function To_Vector (Length : Count_Type) return Vector;
function To_Vector
@@ -442,8 +470,6 @@
function "&" (Left, Right : Element_Type) return Vector;
- function "=" (Left, Right : Vector) return Boolean;
-
function Capacity (Container : Vector) return Count_Type;
procedure Reserve_Capacity (Container : in out Vector;
@@ -451,6 +477,9 @@
function Length (Container : Vector) return Count_Type;
+ procedure Set_Length (Container : in out Vector;
+ Length : in Count_Type);
+
function Is_Empty (Container : Vector) return Boolean;
procedure Clear (Container : in out Vector);
@@ -466,6 +495,14 @@
function Element (Position : Cursor) return Element_Type;
+ procedure Replace_Element (Container : in out Vector;
+ Index : in Index_Type;
+ New_Item : in Element_Type);
+
+ procedure Replace_Element (Container : in out Vector;
+ Position : in Cursor;
+ New_Item : in Element_Type);
+
procedure Query_Element
(Container : in Vector;
Index : in Index_Type;
@@ -476,23 +513,14 @@
Process : not null access procedure (Element : in Element_Type));
procedure Update_Element
- (Container : in Vector;
- Index : in Index_Type;
+ (Container : in out Vector;
+ Index : in Index_Type;
Process : not null access procedure (Element : in out Element_Type));
procedure Update_Element
- (Position : in Cursor;
- Process : not null access procedure (Element : in out Element_Type));
-
- procedure Replace_Element (Container : in Vector;
- Index : in Index_Type;
- By : in Element_Type);
-
- procedure Replace_Element (Position : in Cursor;
- By : in Element_Type);
-
- procedure Assign (Target : in out Vector;
- Source : in Vector);
+ (Container : in out Vector;
+ Position : in Cursor;
+ Process : not null access procedure (Element : in out Element_Type));
procedure Move (Target : in out Vector;
Source : in out Vector);
@@ -526,6 +554,15 @@
Position : out Cursor;
Count : in Count_Type := 1);
+ procedure Insert (Container : in out Vector;
+ Before : in Extended_Index;
+ Count : in Count_Type := 1);
+
+ procedure Insert (Container : in out Vector;
+ Before : in Cursor;
+ Position : out Cursor;
+ Count : in Count_Type := 1);
+
procedure Prepend (Container : in out Vector;
New_Item : in Vector);
@@ -549,9 +586,6 @@
Position : out Cursor;
Count : in Count_Type := 1);
- procedure Set_Length (Container : in out Vector;
- Length : in Count_Type);
-
procedure Delete (Container : in out Vector;
Index : in Extended_Index;
Count : in Count_Type := 1);
@@ -566,6 +600,14 @@
procedure Delete_Last (Container : in out Vector;
Count : in Count_Type := 1);
+ procedure Reverse_Elements (Container : in out Vector);
+
+ procedure Swap (Container : in out Vector;
+ I, J : in Index_Type);
+
+ procedure Swap (Container : in out Vector;
+ I, J : in Cursor);
+
function First_Index (Container : Vector) return Index_Type;
function First (Container : Vector) return Cursor;
@@ -580,24 +622,13 @@
function Last_Element (Container : Vector)
return Element_Type;
- procedure Swap (Container : in Vector;
- I, J : in Index_Type);
-
- procedure Swap (I, J : in Cursor);
-
- generic
- with function "<" (Left, Right : Element_Type)
- return Boolean is <>;
- package Generic_Sorting is
-
- function Is_Sorted (Container : Vector) return Boolean;
+ function Next (Position : Cursor) return Cursor;
- procedure Sort (Container : in out Vector);
+ procedure Next (Position : in out Cursor);
- procedure Merge (Target : in out Vector;
- Source : in out Vector);
+ function Previous (Position : Cursor) return Cursor;
- end Generic_Sorting;
+ procedure Previous (Position : in out Cursor);
function Find_Index (Container : Vector;
Item : Element_Type;
@@ -622,15 +653,6 @@
function Contains (Container : Vector;
Item : Element_Type) return Boolean;
-
- function Next (Position : Cursor) return Cursor;
-
- function Previous (Position : Cursor) return Cursor;
-
- procedure Next (Position : in out Cursor);
-
- procedure Previous (Position : in out Cursor);
-
function Has_Element (Position : Cursor) return Boolean;
procedure Iterate
@@ -641,6 +663,20 @@
(Container : in Vector;
Process : not null access procedure (Position : in Cursor));
+ generic
+ with function "<" (Left, Right : Element_Type)
+ return Boolean is <>;
+ package Generic_Sorting is
+
+ function Is_Sorted (Container : Vector) return Boolean;
+
+ procedure Sort (Container : in out Vector);
+
+ procedure Merge (Target : in out Vector;
+ Source : in out Vector);
+
+ end Generic_Sorting;
+
private
... -- not specified by the language
@@ -648,6 +684,26 @@
end Ada.Containers.Vectors;
+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 functions defined to use it return an
+unspecified value. The exact arguments and number of calls of this generic
+formal function by the functions defined to use it are unspecified.
+
+ AARM Note: The "functions defined to use it" are Find, Find_Index,
+ Reverse_Find, Reverse_Find_Index, and "=" for Vectors.
+
+ If the actual function for "=" is not symmetric
+ and consistent, the result returned by the listed functions 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 results of the functions defined
+ to use "=" are unspecified; other subprograms are not allowed to break
+ if "=" is bad.
+ End AARM Note.
+
The type Vector is used to represent vectors. The type Vector needs finalization
(see 7.6).
@@ -659,6 +715,12 @@
Cursor is not otherwise initialized, it is initialized to the same value as
No_Element.
+The predefined "=" operator for type Cursor should return True if both cursors
+or No_Element, or designate the same element in the same container.
+
+Execution of the default implementation of the Input, Output, Read, or Write
+attribute of type Cursor raises Program_Error.
+
No_Index represents a position that does not correspond to any element. The
subtype Extended_Index includes the indices covered by Index_Type plus the
value No_Index and, if it exists, the successor to the Index_Type'Last.
@@ -668,9 +730,9 @@
existence of Index_Type'Last + 1, as it is only used as the position of
insertions (and needs to be allowed only when inserting an empty vector).
-Some operations are assumed to work on a constant set of elements. For such
-an operation, a subprogram is said to *tamper with cursors* of a vector
-object V if:
+Some operations are assumed to work on a constant set of elements. During
+execution of such an operation, a subprogram is said to *tamper with cursors*
+of a vector object V if:
* it inserts or deletes elements of V, that is, it calls the Insert,
Insert_Space, Clear, Delete, or Set_Length procedures with V
@@ -687,19 +749,29 @@
Swap, Sort, and Merge copy elements rather than reordering them, so
they do not tamper with cursors.
-Some operations are assumed to not replace elements. For such an operation, a
+Some operations are assumed to not replace elements. During the execution of such an operation, a
subprogram is said to *tamper with elements* of a vector object V if:
* it tampers with cursors of V; or
* it replaces one or more elements of V, that is, it calls the
- Replace_Element or Swap procedures or the Sort or Merge procedures of an
- instance of Generic_Sorting with V as a parameter.
+ Replace_Element, Reverse_Elements, or Swap procedures or the Sort or
+ Merge procedures of an instance of Generic_Sorting with V as a parameter.
AARM Note: 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 does not cause a problem.
+function "=" (Left, Right : Vector) return Boolean;
+
+If Left and Right denote the same vector object, then the function returns
+True. If Left and Right have different lengths, then the function returns
+False. Otherwise, it compares each element in Left to the corresponding element
+in Right using the generic formal equality operator; if element equality
+returns False, then the function returns False. 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.
+
function To_Vector (Length : Count_Type) return Vector;
Returns a vector with a length of Length, filled with empty elements.
@@ -730,16 +802,6 @@
Returns a vector comprising the element Left followed by the element Right.
-function "=" (Left, Right : Vector) return Boolean;
-
-If Left and Right denote the same vector object, then the function returns
-True. If Left and Right have different lengths, then the function returns
-False. Otherwise, it compares each element in Left to the corresponding element
-in Right using the generic formal equality operator; if element equality
-returns False, then the function returns False. 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.
-
function Capacity (Container : Vector) return Count_Type;
Returns the capacity of Container.
@@ -779,6 +841,20 @@
Returns the number of elements in Container.
+procedure Set_Length (Container : in out Vector;
+ Length : in Count_Type);
+
+If Length is larger than the capacity of Container, Set_Length calls
+Reserve_Capacity (Container, Length), then sets the length of the
+Container to Length. If Length is greater than the original length of
+Container, empty elements are added to Container; otherwise elements are
+removed from Container.
+
+AARM Ramification: No elements are moved by this operation; any new empty
+elements are added at the end. This follows from the rules that a cursor
+continues to designate the same element unless the routine is defined
+to make the cursor ambiguous or invalid; this operation does not do that.
+
function Is_Empty (Container : Vector) return Boolean;
Equivalent to Length (Container) = 0.
@@ -822,6 +898,30 @@
If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
Element returns the element designated by Position.
+procedure Replace_Element (Container : in out Vector;
+ Index : in Index_Type;
+ New_Item : in Element_Type);
+
+If Index is not in the range First_Index (Container) .. Last_Index (Container),
+then Constraint_Error is propagated. Otherwise Replace_Element assigns the
+value New_Item to the element at position Index. Any exception raised during
+the assignment is propagated. The element at position Index is not an empty
+element after successful call to Replace_Element.
+
+procedure Replace_Element (Container : in out Vector;
+ Position : in Cursor;
+ New_Item : in Element_Type);
+
+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
+Replace_Element assigns New_Item to the element designated by Position. Any
+exception raised during the assignment is propagated. The element at Position
+is not an empty element after successful call to Replace_Element.
+
+AARM Note: Replace_Element and Update_Element are the only ways that an element
+can change from empty to non-empty.
+
procedure Query_Element
(Container : in Vector;
Index : in Index_Type;
@@ -849,8 +949,8 @@
an indefinite container).
procedure Update_Element
- (Container : in Vector;
- Index : in Index_Type;
+ (Container : in out Vector;
+ Index : in Index_Type;
Process : not null access procedure (Element : in out Element_Type));
If Index is not in the range First_Index (Container) .. Last_Index (Container),
@@ -859,8 +959,8 @@
if Process.all tampers with the elements of Container. Any exception raised by
Process.all is propagated.
-If Element_Type is unconstrained and definite, then the Element parameter
-of Process.all shall be unconstrained.
+If Element_Type is unconstrained and definite, then the actual Element
+parameter of Process.all shall be unconstrained.
AARM Note: This means that the elements cannot be directly allocated from the
heap (nor aliased unless AI-363 is included in the Amendment); it must be
@@ -874,50 +974,23 @@
to do that reliably.
procedure Update_Element
- (Position : in Cursor;
- Process : not null access procedure (Element : in out Element_Type));
+ (Container : in out Vector;
+ Position : in Cursor;
+ Process : not null access procedure (Element : in out Element_Type));
-If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
-Update_Element calls Process.all with the element designated by Position as the
-argument. Program_Error is propagated if Process.all tampers with the elements
-of Container. Any exception raised by Process.all is propagated.
+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 calls Process.all with the element designated
+by Position as the argument. Program_Error is propagated if Process.all tampers
+with the elements of Container. Any exception raised by Process.all is
+propagated.
-If Element_Type is unconstrained and definite, then the Element parameter
+If Element_Type is unconstrained and definite, then the actual Element parameter
of Process.all shall be unconstrained.
The element designated by Position is not an empty element after successful
completion of this operation.
-procedure Replace_Element (Container : in Vector;
- Index : in Index_Type;
- By : in Element_Type);
-
-If Index is not in the range First_Index (Container) .. Last_Index (Container),
-then Constraint_Error is propagated. Otherwise Replace_Element assigns the
-value By to the element at position Index. Any exception raised during the
-assignment is propagated. The element at position Index is not an empty element
-after successful call to Replace_Element.
-
-procedure Replace_Element (Position : in Cursor;
- By : in Element_Type);
-
-If Position equals No_Element, then Constraint_Error is propagated. Otherwise
-Replace_Element assigns By to the element designated by Position. Any exception
-raised during the assignment is propagated. The element at Position is
-not an empty element after successful call to Replace_Element.
-
-AARM Note: Replace_Element and Update_Element are the only ways that an element
-can change from empty to non-empty.
-
-procedure Assign (Target : in out Vector;
- Source : in Vector);
-
-If Target denotes the same object as Source, then the operation has no effect.
-Otherwise, Assign first calls Clear (Target), then Reserve_Capacity (Target,
-Length (Source)). It then assigns the elements of Source to the corresponding
-positions in Target, and sets the length of Target to the length of Source.
-Any exception raised during element assignment is propagated.
-
procedure Move (Target : in out Vector;
Source : in out Vector);
@@ -1016,17 +1089,44 @@
Equivalent to Insert (Container, Before, To_Vector (New_Item, Count), Position);
+procedure Insert (Container : in out Vector;
+ Before : in Extended_Index;
+ Count : in Count_Type := 1);
+
+If Before is not in the range First_Index (Container) .. Last_Index (Container)
++ 1, then Constraint_Error is propagated. If Count is 0, then Insert_Space does
+nothing. Otherwise, it computes the new length *NL* as the sum of the current
+length and Count; if the value of Last appropriate for length NL would be
+greater than Index_Type'Last then Constraint_Error is propagated.
+
+If the current vector capacity is less than or equal to NL,
+Reserve_Capacity (Container, NL) is called to increase the vector capacity.
+Then Insert_Space slides the elements in the range Before .. Last_Index
+(Container) up by Count positions, and then inserts elements that
+are initialized by default (see 3.3.1) in the positions starting at Before.
+
+procedure Insert (Container : in out Vector;
+ Before : in Cursor;
+ Position : out Cursor;
+ Count : in Count_Type := 1);
+
+If Before is not No_Element, and does not designate an element in
+Target, then Program_Error is propagated.
+If Before equals No_Element, then let T be Last_Index (Container) + 1;
+otherwise, let T be To_Index (Before). Insert (Container, T, Count) is
+called, and then Position is set to To_Cursor (Container, T).
+
procedure Prepend (Container : in out Vector;
New_Item : in Vector;
Count : in Count_Type := 1);
-Equivalent to Insert (Container, Index_Type'First, New_Item).
+Equivalent to Insert (Container, First_Index (Container), New_Item).
procedure Prepend (Container : in out Vector;
New_Item : in Element_Type;
Count : in Count_Type := 1);
-Equivalent to Insert (Container, Index_Type'First, New_Item, Count).
+Equivalent to Insert (Container, First_Index (Container), New_Item, Count).
procedure Append (Container : in out Vector;
New_Item : in Vector);
@@ -1066,20 +1166,6 @@
otherwise, let T be To_Index (Before). Insert_Space (Container, T, Count) is
called, and then Position is set to To_Cursor (Container, T).
-procedure Set_Length (Container : in out Vector;
- Length : in Count_Type);
-
-If Length is larger than the capacity of Container, Set_Length calls
-Reserve_Capacity (Container, Length), then sets the length of the
-Container to Length. If Length is greater than the original length of
-Container, empty elements are added to Container; otherwise elements are
-removed from Container.
-
-AARM Ramification: No elements are moved by this operation; any new empty
-elements are added at the end. This follows from the rules that a cursor
-continues to designate the same element unless the routine is defined
-to make the cursor ambiguous or invalid; this operation does not do that.
-
procedure Delete (Container : in out Vector;
Index : in Extended_Index;
Count : in Count_Type := 1);
@@ -1101,12 +1187,13 @@
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 (Container, To_Index (Position), Count) is called.
+Otherwise, Delete (Container, To_Index (Position), Count) is called, and
+then Position is set to No_Element.
procedure Delete_First (Container : in out Vector;
Count : in Count_Type := 1);
-Equivalent to Delete (Container, Index_Type'First, Count).
+Equivalent to Delete (Container, First_Index (Container), Count).
procedure Delete_Last (Container : in out Vector;
Count : in Count_Type := 1);
@@ -1115,6 +1202,39 @@
Clear (Container). Otherwise it is equivalent to Delete (Container,
Index_Type'Val(Index_Type'Pos(Last_Index(Container)) - Count + 1), Count).
+procedure Reverse_Elements (Container : in out Vector);
+
+Reorders the elements of Container in reverse order.
+
+procedure Swap (Container : in out Vector;
+ I, J : in Index_Type);
+
+If I or J is not in the range First_Index (Container) .. Last_Index (Container),
+then Constraint_Error is propagated. Otherwise, Swap exchanges the values of
+the elements at positions I and J.
+
+AARM Notes: To Be Honest: The implementation is not required to actually
+copy the elements if it can do the swap some other way. But it is allowed
+to copy the elements if needed.
+
+procedure Swap (Container : in out Vector;
+ I, J : in Cursor);
+
+If either I or J is No_Element, then Constraint_Error is propagated. If either
+I or J do not designate an element in Container, then Program_Error is
+propagated. Otherwise Swap exchanges the values of the elements designated by I
+and J.
+
+AARM Notes:
+After a call to Swap, I designates the element value previously
+designated by J, and J designates the element value previously
+designated by I. The cursors do not become ambiguous from this operation.
+
+To Be Honest: The implementation is not required to actually
+copy the elements if it can do the swap some other way. But it is allowed
+to copy the elements if needed.
+End AARM Notes.
+
function First_Index (Container : Vector) return Index_Type;
Returns the value Index_Type'First.
@@ -1145,95 +1265,39 @@
Equivalent to Element (Container, Last_Index (Container)).
-procedure Swap (Container : in Vector;
- I, J : in Index_Type);
+function Next (Position : Cursor) return Cursor;
-If I or J is not in the range First_Index (Container) .. Last_Index (Container),
-then Constraint_Error is propagated. Otherwise, Swap exchanges the values of
-the elements at positions I and J.
+If Position equals No_Element or designates the last element of the container,
+then Next returns the value No_Element. Otherwise, returns a cursor that
+designates the element with index To_Index (Position) + 1 in the same vector as
+Position.
-AARM Notes: To Be Honest: The implementation is not required to actually
-copy the elements if it can do the swap some other way. But it is allowed
-to copy the elements if needed.
+procedure Next (Position : in out Cursor);
-procedure Swap (I, J : in Cursor);
+Equivalent to Position := Next (Position).
-If either I or J is No_Element, then Constraint_Error is propagated. If I and J
-designate elements in different containers, then Program_Error is propagated.
-Otherwise Swap exchanges the values of the elements designated by I and J.
+function Previous (Position : Cursor) return Cursor;
-AARM Notes:
-After a call to Swap, I designates the element value previously
-designated by J, and J designates the element value previously
-designated by I. The cursors do not become ambiguous from this operation.
+If Position equals No_Element or designates the first element of the container,
+then Previous returns the value No_Element. Otherwise, returns a cursor that
+designates the element with index (To_Index (Position) - 1) in the same vector
+as Position.
-To Be Honest: The implementation is not required to actually
-copy the elements if it can do the swap some other way. But it is allowed
-to copy the elements if needed.
-End AARM Notes.
+procedure Previous (Position : in out Cursor);
-function Is_Sorted (Container : Vector) return Boolean;
+Equivalent to Position := Previous (Position).
-Returns True if the elements are sorted smallest first as determined by the
-generic formal "<" operator; otherwise, Is_Sorted returns False.
-Any exception raised during evaluation of "<" is propagated.
+function Find_Index (Container : Vector;
+ Item : Element_Type;
+ Index : Index_Type := Index_Type'First)
+ return Extended_Index;
-procedure Sort (Container : in out Vector);
+Searches the elements of Container for an element equal to Item (in the sense
+of the generic formal equality operator). The search starts at position Index
+and proceeds towards Last_Index (Container). If no equal element is found, then
+Find_Index returns No_Index. Otherwise, it returns the index of the first equal
+element encountered.
-Reorders the elements of Container such that the elements are
-sorted smallest first as determined by the generic formal "<" operator
-provided. Any exception raised during evaluation of "<" is propagated.
-
-AARM Notes:
-This implies swapping the elements, usually including an intermediate copy.
-This means that the elements will usually be copied. (As with Swap,
-if the implementation can do this some other way, it is allowed to.) Since
-the elements are nonlimited, this usually will not be a problem. Note that
-there is Implementation Advice below that the implementation should use
-a sort that minimizes copying of elements.
-
-The sort is not required to be stable (and the fast algorithm required will
-not be stable). If a stable sort is needed, the user can include the original
-location of the element as an extra "sort key". We considered requiring the
-implementation to do that, but it is mostly extra overhead -- usually there
-is something already in the element that provides the needed stability.
-End AARM Notes
-
-procedure Merge (Target : in out Vector;
- Source : in out Vector);
-
-Merge removes elements from Source and inserts them into Target; afterwards,
-Target contains the union of the elements that were initially
-in Source and Target; Source is left empty.
-If Target and Source are initially sorted smallest first, then Target is
-ordered smallest first as determined by the generic formal "<" operator;
-otherwise, the order of elements in Target is unspecified.
-Any exception raised during evaluation of "<" is propagated.
-
-AARM Notes:
-It is a bounded error if either of the vectors is unsorted, see below. The
-bounded error can be recovered by sorting Target after the merge call, or
-the vectors can be pretested with Is_Sorted.
-
-The Merge operation will usually require copying almost all of the elements.
-One implementation strategy would be to extend Target to the appropriate
-length, then copying elements from the back of the vectors working towards the
-front. An alternative approach would be to allocate a new internal data array
-of the appropriate length, copy the elements into it in an appropriate order,
-and then replacing the data array in Target with the temporary.
-End AARM Notes.
-
-function Find_Index (Container : Vector;
- Item : Element_Type;
- Index : Index_Type := Index_Type'First)
- return Extended_Index;
-
-Searches the elements of Container for an element equal to Item (in the sense
-of the generic formal equality operator). The search starts at position Index
-and proceeds towards Last_Index (Container). If no equal element is found, then
-Find_Index returns No_Index. Otherwise, it returns the index of the first equal
-element encountered.
-
function Find (Container : Vector;
Item : Element_Type;
Position : Cursor := No_Element)
@@ -1245,7 +1309,7 @@
equality operator). The search starts at the first element if Cursor equals
No_Element, and at the element designated by Cursor otherwise. It proceeds
towards the last element of Container. If no equal element is found, then
-Find returns No_Cursor. Otherwise, it returns a cursor designating the first
+Find returns No_Element. Otherwise, it returns a cursor designating the first
equal element encountered.
function Reverse_Find_Index (Container : Vector;
@@ -1271,7 +1335,7 @@
equality operator). The search starts at the last element if Cursor equals
No_Element, and at the element designated by Cursor otherwise. It proceeds
towards the first element of Container. If no equal element is found, then
-Reverse_Find returns No_Cursor. Otherwise, it returns a cursor designating
+Reverse_Find returns No_Element. Otherwise, it returns a cursor designating
the first equal element encountered.
function Contains (Container : Vector;
@@ -1279,28 +1343,6 @@
Equivalent to Has_Element (Find (Container, Item)).
-function Next (Position : Cursor) return Cursor;
-
-If Position equals No_Element or designates the last element of the container,
-then Next returns the value No_Element. Otherwise, returns a cursor that
-designates the element with index To_Index (Position) + 1 in the same vector as
-Position.
-
-function Previous (Position : Cursor) return Cursor;
-
-If Position equals No_Element or designates the first element of the container,
-then Previous returns the value No_Element. Otherwise, returns a cursor that
-designates the element with index (To_Index (Position) - 1) in the same vector
-as Position.
-
-procedure Next (Position : in out Cursor);
-
-Equivalent to Position := Next (Position).
-
-procedure Previous (Position : in out Cursor);
-
-Equivalent to Position := Previous (Position).
-
function Has_Element (Position : Cursor) return Boolean;
Returns True if Position designates an element, and returns False otherwise.
@@ -1340,8 +1382,67 @@
(Container : in Vector;
Process : not null access procedure (Position : in Cursor));
-Iterates over the nodes in Container as per Iterate, except that elements are
-traversed in reverse index order.
+Iterates over the elements in Container as per Iterate, except that elements
+are traversed in reverse index order.
+
+The actual function for the generic formal function "<" of Generic_Sorting is
+expected to return the same value each time it is called with a particular pair
+of element values. It should define a strict ordering relationship, that is, be
+irreflexive, asymmetric, and transitive; it should not modify Container. If the
+actual for "<" behaves in some other manner, the behavior of the subprograms of
+Generic_Sorting are unspecified. How many times the subprograms of
+Generic_Sorting call "<" is unspecified.
+
+function Is_Sorted (Container : Vector) return Boolean;
+
+Returns True if the elements are sorted smallest first as determined by the
+generic formal "<" operator; otherwise, Is_Sorted returns False.
+Any exception raised during evaluation of "<" is propagated.
+
+procedure Sort (Container : in out Vector);
+
+Reorders the elements of Container such that the elements are
+sorted smallest first as determined by the generic formal "<" operator
+provided. Any exception raised during evaluation of "<" is propagated.
+
+AARM Notes:
+This implies swapping the elements, usually including an intermediate copy.
+This means that the elements will usually be copied. (As with Swap,
+if the implementation can do this some other way, it is allowed to.) Since
+the elements are nonlimited, this usually will not be a problem. Note that
+there is Implementation Advice below that the implementation should use
+a sort that minimizes copying of elements.
+
+The sort is not required to be stable (and the fast algorithm required will
+not be stable). If a stable sort is needed, the user can include the original
+location of the element as an extra "sort key". We considered requiring the
+implementation to do that, but it is mostly extra overhead -- usually there
+is something already in the element that provides the needed stability.
+End AARM Notes
+
+procedure Merge (Target : in out Vector;
+ Source : in out Vector);
+
+Merge removes elements from Source and inserts them into Target; afterwards,
+Target contains the union of the elements that were initially
+in Source and Target; Source is left empty.
+If Target and Source are initially sorted smallest first, then Target is
+ordered smallest first as determined by the generic formal "<" operator;
+otherwise, the order of elements in Target is unspecified.
+Any exception raised during evaluation of "<" is propagated.
+
+AARM Notes:
+It is a bounded error if either of the vectors is unsorted, see below. The
+bounded error can be recovered by sorting Target after the merge call, or
+the vectors can be pretested with Is_Sorted.
+
+The Merge operation will usually require copying almost all of the elements.
+One implementation strategy would be to extend Target to the appropriate
+length, then copying elements from the back of the vectors working towards the
+front. An alternative approach would be to allocate a new internal data array
+of the appropriate length, copy the elements into it in an appropriate order,
+and then replacing the data array in Target with the temporary.
+End AARM Notes.
Legality Rules
@@ -1361,9 +1462,9 @@
Reading the value of an empty element by calling Element, Query_Element,
Update_Element, Swap, Is_Sorted, Sort, Merge, "=", Find, or Reverse_Find is a
-bounded error. The implementation may treat the element as having any valid
-value of the element type, or raise Constraint_Error or Program_Error before
-modifying the vector.
+bounded error. The implementation may treat the element as having any normal
+value (see 13.9.1) of the element type, or raise Constraint_Error or
+Program_Error before modifying the vector.
AARM Notes: For instance, a default initialized element could be returned. Or
some previous value of an element. But returning random junk is not allowed
@@ -1391,7 +1492,8 @@
such an index value) less than or equal to the index value of the element
designated by the cursor; or
* The vector that contains the element it designates has been passed to the
- Sort or Merge procedures of an instance of Generic_Sorting.
+ Sort or Merge procedures of an instance of Generic_Sorting, or to the
+ Reverse_Elements procedure.
It is a bounded error to call any subprogram other than "=" or Has_Element
declared in Containers.Vectors with an ambiguous (but not invalid, see below)
@@ -1441,12 +1543,25 @@
No storage associated with a vector object shall be lost upon assignment or
scope exit.
+The execution of an assignment_statement for a vector shall have the
+effect of copying the elements from the source vector object to the target
+vector object.
+
+AARM Note:
+An assignment of a Vector 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.
+End AARM Note.
+
Implementation Advice
Containers.Vectors should be implemented similarly to an array. In particular,
if the length of a vector is *N*, then
- * the worst-case time complexity of Append with Count=1 and Element should
- be O(log N); and
+ * the worst-case time complexity of Element should be O(log N);
+ * the worst-case time complexity of Append with Count=1 when
+ N is less than the capacity of the vector should be O(log N); and
* the worst-case time complexity of Prepend with Count=1 and Delete_First
with Count=1 should be O(N log N).
@@ -1495,7 +1610,7 @@
If a sparse container is required, a Hashed_Map should be used rather than a
vector.
-If Index_Type'Base'First = Index_Type'First an instantiation of
+If Index_Type'Base'First = Index_Type'First an instance of
Ada.Containers.Vectors will raise Constraint_Error. A value below
Index_Type'First is required so that an empty vector has a meaningful
value of Last_Index.
@@ -1553,28 +1668,22 @@
function Element (Position : Cursor)
return Element_Type;
+ procedure Replace_Element (Container : in out List;
+ Position : in Cursor;
+ New_Item : in Element_Type);
+
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
procedure Update_Element
- (Position : in Cursor;
- Process : not null access procedure (Element : in out Element_Type));
-
- procedure Replace_Element (Position : in Cursor;
- By : in Element_Type);
+ (Container : in out List;
+ Position : in Cursor;
+ Process : not null access procedure (Element : in out Element_Type));
procedure Move (Target : in out List;
Source : in out List);
- procedure Prepend (Container : in out List;
- New_Item : in Element_Type;
- Count : in Count_Type := 1);
-
- procedure Append (Container : in out List;
- New_Item : in Element_Type;
- Count : in Count_Type := 1);
-
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
@@ -1591,6 +1700,14 @@
Position : out Cursor;
Count : in Count_Type := 1);
+ procedure Prepend (Container : in out List;
+ New_Item : in Element_Type;
+ Count : in Count_Type := 1);
+
+ procedure Append (Container : in out List;
+ New_Item : in Element_Type;
+ Count : in Count_Type := 1);
+
procedure Delete (Container : in out List;
Position : in out Cursor;
Count : in Count_Type := 1);
@@ -1600,24 +1717,11 @@
procedure Delete_Last (Container : in out List;
Count : in Count_Type := 1);
-
- generic
- with function "<" (Left, Right : Element_Type)
- return Boolean is <>;
- package Generic_Sorting is
-
- function Is_Sorted (Container : List) return Boolean;
-
- procedure Sort (Container : in out List);
-
- procedure Merge (Target : in out List;
- Source : in out List);
-
- end Generic_Sorting;
- procedure Reverse_List (Container : in out List);
+ procedure Reverse_Elements (Container : in out List);
- procedure Swap (I, J : in Cursor);
+ procedure Swap (Container : in out List;
+ I, J : in Cursor);
procedure Swap_Links (Container : in out List;
I, J : in Cursor);
@@ -1645,8 +1749,13 @@
function Last_Element (Container : List)
return Element_Type;
- function Contains (Container : List;
- Item : Element_Type) return Boolean;
+ function Next (Position : Cursor) return Cursor;
+
+ procedure Next (Position : in out Cursor);
+
+ function Previous (Position : Cursor) return Cursor;
+
+ procedure Previous (Position : in out Cursor);
function Find (Container : List;
Item : Element_Type;
@@ -1657,14 +1766,9 @@
Item : Element_Type;
Position : Cursor := No_Element)
return Cursor;
-
- function Next (Position : Cursor) return Cursor;
-
- function Previous (Position : Cursor) return Cursor;
-
- procedure Next (Position : in out Cursor);
- procedure Previous (Position : in out Cursor);
+ function Contains (Container : List;
+ Item : Element_Type) return Boolean;
function Has_Element (Position : Cursor) return Boolean;
@@ -1676,6 +1780,20 @@
(Container : in List;
Process : not null access procedure (Position : in Cursor));
+ generic
+ with function "<" (Left, Right : Element_Type)
+ return Boolean is <>;
+ package Generic_Sorting is
+
+ function Is_Sorted (Container : List) return Boolean;
+
+ procedure Sort (Container : in out List);
+
+ procedure Merge (Target : in out List;
+ Source : in out List);
+
+ end Generic_Sorting;
+
private
... -- not specified by the language
@@ -1683,6 +1801,23 @@
end Ada.Containers.Doubly_Linked_Lists;
+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 functions Find, Reverse_Find, and "=" on
+list values return an unspecified value. The exact arguments and number of
+calls of this generic formal function by the functions Find, Reverse_Find, and
+"=" on list values are unspecified.
+
+ AARM Note: If the actual function for "=" is not symmetric
+ and consistent, the result returned by the listed functions cannot be
+ predicted. The implementation is not required to protect
+ against "=" raising an exception, or returning random results, or any
+ other @lquotes@;bad@rquotes behavior. And it can call "=" in whatever
+ manner makes sense. But note that only the results of Find, Reverse_Find,
+ and List "=" are unspecified; other subprograms are not allowed to break
+ if "=" is bad (they aren't expected to use "=").
+
The type List is used to represent lists. The type List needs finalization (see
7.6).
@@ -1693,11 +1828,17 @@
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.
+
+The predefined "=" operator for type Cursor should return True if both cursors
+or No_Element, or designate the same element in the same container.
-Some operations are assumed to work on a constant set of elements. For such
-an operation, a subprogram is said to *tamper with cursors* of a list object L
-if:
+Execution of the default implementation of the Input, Output, Read, or Write
+attribute of type Cursor raises Program_Error.
+Some operations are assumed to work on a constant set of elements. During
+execution of such an operation, a subprogram is said to *tamper with cursors*
+of a list object L if:
+
* it inserts or deletes elements of L, that is, it calls the Insert,
Clear, Delete, or Delete_Last procedures with L as a parameter; or
@@ -1706,7 +1847,7 @@
which call one of these as part of their definition are included.
* it reorders the elements of L, that is, it calls the Splice,
- Swap_Links, or Reverse_List procedures or the Sort or Merge procedures
+ Swap_Links, or Reverse_Elements procedures or the Sort or Merge procedures
from an instance of Generic_Sorting with L as a parameter; or
* it finalizes L; or
@@ -1716,7 +1857,7 @@
Swap copies elements rather than reordering them, so it doesn't tamper
with cursors.
-Some operations are assumed to not replace elements. For such an operation, a
+Some operations are assumed to not replace elements. During the execution of such an operation, a
subprogram is said to *tamper with elements* of a list object L if:
* it tampers with cursors of L; or
@@ -1756,40 +1897,44 @@
If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
Element returns the element designated by Position.
+procedure Replace_Element (Container : in out List;
+ Position : in Cursor;
+ New_Item : in Element_Type);
+
+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 Replace_Element assigns the value New_Item to the
+element designated by Position.
+
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
-Query_Element calls Process.all with the element on node designated by
+Query_Element calls Process.all with the element designated by
Position as the argument. Program_Error is propagated if Process.all tampers
with the elements of Container. Any exception raised by Process.all is
propagated.
procedure Update_Element
- (Position : in Cursor;
- Process : not null access procedure (Element : in out Element_Type));
+ (Container : in out List;
+ Position : in Cursor;
+ Process : not null access procedure (Element : in out Element_Type));
-If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
-Update_Element calls Process.all with the element on node designated by
-Position as the argument. Program_Error is propagated if Process.all tampers
-with the elements of Container. Any exceptions raised by Process.all are
-propagated.
+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 calls Process.all with the element
+designated by Position as the argument. Program_Error is propagated if
+Process.all tampers with the elements of Container. Any exception raised by
+Process.all is propagated.
-If Element_Type is unconstrained and definite, then the Element parameter
+If Element_Type is unconstrained and definite, then the actual Element parameter
of Process.all shall be unconstrained.
AARM Note: This means that the elements cannot be directly allocated from the
heap (nor aliased unless AI-363 is included in the Amendment); it must be
possible to change the discriminants of the element in place.
-procedure Replace_Element (Position : Cursor;
- By : Element_Type);
-
-If Position equals No_Element, then Constraint_Error is propagated. Otherwise
-Replace_Element assigns the value By to the element designated by
-Position.
-
procedure Move (Target : in out List;
Source : in out List);
@@ -1798,18 +1943,6 @@
are moved to Target (in the original order). The length of Target is set to the
length of Source, and the length of Source is set to 0.
-procedure Prepend (Container : in out List;
- New_Item : in Element_Type;
- Count : in Count_Type := 1);
-
-Equivalent to Insert (Container, First (Container), New_Item, Count).
-
-procedure Append (Container : in out List;
- New_Item : in Element_Type;
- Count : in Count_Type := 1);
-
-Equivalent to Insert (Container, No_Element, New_Item, Count).
-
procedure Insert (Container : in out List;
Before : in Cursor;
New_Item : in Element_Type;
@@ -1855,11 +1988,21 @@
Otherwise, Insert inserts Count new elements
prior to the element designated by Before. If Before equals No_Element, the new
elements are inserted after the last node (if any). The new elements are
-initialized with any implicit initial value for any part (as for an
-object_declaration with no initialization expression - see 3.3.1). Any
-exception raised during allocation of internal storage is propagated, and
-Container is not modified.
+initialized by default (see 3.3.1). Any exception raised during allocation of
+internal storage is propagated, and Container is not modified.
+procedure Prepend (Container : in out List;
+ New_Item : in Element_Type;
+ Count : in Count_Type := 1);
+
+Equivalent to Insert (Container, First (Container), New_Item, Count).
+
+procedure Append (Container : in out List;
+ New_Item : in Element_Type;
+ Count : in Count_Type := 1);
+
+Equivalent to Insert (Container, No_Element, New_Item, Count).
+
procedure Delete (Container : in out List;
Position : in out Cursor;
Count : in Count_Type := 1);
@@ -1868,7 +2011,8 @@
does not designate an element in Container, then Program_Error is propagated.
Otherwise Delete removes (from Container) Count elements starting at the
element designated by Position (or all of the elements starting at Position if
-there are fewer than Count elements starting at Position).
+there are fewer than Count elements starting at Position). Finally, Position
+is set to No_Element.
procedure Delete_First (Container : in out List;
Count : in Count_Type := 1);
@@ -1881,60 +2025,23 @@
If Length (Container) <= Count then Delete_Last is equivalent to Clear
(Container). Otherwise it removes the last Count nodes from Container.
-function Is_Sorted (Container : List) return Boolean;
+procedure Reverse_Elements (Container : in out List);
-Returns True if the elements are sorted smallest first as determined by the
-generic formal "<" operator; otherwise, Is_Sorted returns False.
-Any exception raised during evaluation of "<" is propagated.
+Reorders the elements of Container in reverse order.
-procedure Sort (Container : in out List);
+procedure Swap (Container : in out List;
+ I, J : in Cursor);
-Reorders the nodes of Container such that the elements are
-sorted smallest first as determined by the generic formal "<" operator
-provided. The sort is stable. Any exception raised during evaluation of
-"<" is propagated.
+If either I or J is No_Element, then Constraint_Error is propagated. If either
+I or J do not designate an element in Container, then Program_Error is
+propagated. Otherwise Swap exchanges the values of the elements designated by
+I and J.
-AARM Notes
-Unlike array sorts, we do require stable sorts here. That's because
-algorithms in the merge sort family (as described by Knuth) can be both
-fast and stable. Such sorts use the extra memory as offered by
-the links to provide better performance.
+AARM Notes:
+After a call to Swap, I designates the element value previously
+designated by J, and J designates the element value previously
+designated by I. The cursors do not become ambiguous from this operation.
-Note that list sorts never copy elements; it is the nodes, not the elements,
-that are reordered.
-End AARM Notes
-
-procedure Merge (Target : in out List;
- Source : in out List);
-
-Merge removes elements from Source and inserts them into Target; afterwards,
-Target contains the union of the elements that were initially
-in Source and Target; Source is left empty.
-If Target and Source are initially sorted smallest first, then Target is ordered
-smallest first as determined by the generic formal "<" operator; otherwise,
-the order of elements in Target is unspecified.
-Any exception raised during evaluation of "<" is propagated.
-
-AARM Note:
-It is a bounded error if either of the lists is unsorted, see below. The
-bounded error can be recovered by sorting Target after the merge call, or
-the lists can be pretested with Is_Sorted.
-
-procedure Reverse_List (Container : in out List);
-
-Reorders the elements of Container in reverse order.
-
-procedure Swap (I, J : in Cursor);
-
-If either I or J is No_Element, then Constraint_Error is propagated. If I and J
-designate elements in different containers, then Program_Error is propagated.
-Otherwise Swap exchanges the values of the elements designated by I and J.
-
-AARM Notes:
-After a call to Swap, I designates the element value previously
-designated by J, and J designates the element value previously
-designated by I. The cursors do not become ambiguous from this operation.
-
AARM Notes: To Be Honest: The implementation is not required to actually
copy the elements if it can do the swap some other way. But it is allowed
to copy the elements if needed.
@@ -2006,11 +2113,26 @@
Equivalent to Element (Last (Container)).
-function Contains (Container : List;
- Item : Element_Type) return Boolean;
+function Next (Position : Cursor) return Cursor;
-Equivalent to Find (Container, Item) /= No_Element.
+If Position equals No_Element or designates the last element of the container,
+then Next returns the value No_Element. Otherwise, it returns a cursor that
+designates the successor of the element designated by Position.
+
+procedure Next (Position : in out Cursor);
+
+Equivalent to Position := Next (Position).
+
+function Previous (Position : Cursor) return Cursor;
+
+If Position equals No_Element or designates the first element of the container,
+then Previous returns the value No_Element. Otherwise, it returns a cursor that
+designates the predecessor of the element designated by Position.
+
+procedure Previous (Position : in out Cursor);
+Equivalent to Position := Previous (Position).
+
function Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
@@ -2033,30 +2155,15 @@
in Container, then Program_Error is propagated. Find searches the elements of
Container for an element equal to Item (in the sense of the generic formal
equality operator). The search starts at the element designated by Position, or
-at the lastelement if Position equals No_Element. It proceeds towards First
+at the last element if Position equals No_Element. It proceeds towards First
(Container). If no equal element is found, then Reverse_Find returns
No_Element. Otherwise, it returns a cursor designating the first equal element
encountered.
-
-function Next (Position : Cursor) return Cursor;
-
-If Position equals No_Element or designates the last element of the container,
-then Next returns the value No_Element. Otherwise, it returns a cursor that
-designates the successor of the element designated by Position.
-
-function Previous (Position : Cursor) return Cursor;
-
-If Position equals No_Element or designates the first element of the container,
-then Previous returns the value No_Element. Otherwise, it returns a cursor that
-designates the predecessor of the element designated by Position.
-
-procedure Next (Position : in out Cursor);
-Equivalent to Position := Next (Position).
-
-procedure Previous (Position : in out Cursor);
+function Contains (Container : List;
+ Item : Element_Type) return Boolean;
-Equivalent to Position := Previous (Position).
+Equivalent to Find (Container, Item) /= No_Element.
function Has_Element (Position : Cursor) return Boolean;
@@ -2093,8 +2200,55 @@
Iterates over the nodes in Container as per Iterate, except that elements are
traversed in reverse order, starting with the last node and moving the cursor
as per the Previous function.
+
+The actual function for the generic formal function "<" of Generic_Sorting is
+expected to return the same value each time it is called with a particular pair
+of element values. It should define a strict ordering relationship, that is, be
+irreflexive, asymmetric, and transitive; it should not modify Container. If the
+actual for "<" behaves in some other manner, the behavior of the subprograms of
+Generic_Sorting are unspecified. How many times the subprograms of
+Generic_Sorting call "<" is unspecified.
+
+function Is_Sorted (Container : List) return Boolean;
+
+Returns True if the elements are sorted smallest first as determined by the
+generic formal "<" operator; otherwise, Is_Sorted returns False.
+Any exception raised during evaluation of "<" is propagated.
+
+procedure Sort (Container : in out List);
+
+Reorders the nodes of Container such that the elements are
+sorted smallest first as determined by the generic formal "<" operator
+provided. The sort is stable. Any exception raised during evaluation of
+"<" is propagated.
+
+AARM Notes
+Unlike array sorts, we do require stable sorts here. That's because
+algorithms in the merge sort family (as described by Knuth) can be both
+fast and stable. Such sorts use the extra memory as offered by
+the links to provide better performance.
+
+Note that list sorts never copy elements; it is the nodes, not the elements,
+that are reordered.
+End AARM Notes
+
+procedure Merge (Target : in out List;
+ Source : in out List);
+
+Merge removes elements from Source and inserts them into Target; afterwards,
+Target contains the union of the elements that were initially
+in Source and Target; Source is left empty.
+If Target and Source are initially sorted smallest first, then Target is ordered
+smallest first as determined by the generic formal "<" operator; otherwise,
+the order of elements in Target is unspecified.
+Any exception raised during evaluation of "<" is propagated.
+
+AARM Note:
+It is a bounded error if either of the lists is unsorted, see below. The
+bounded error can be recovered by sorting Target after the merge call, or
+the lists can be pretested with Is_Sorted.
-Bounded Error
+Bounded Errors
Calling Merge in an instance of Generic_Sorting with either Source or Target
not ordered smallest first using the provided generic formal "<" operator
@@ -2129,6 +2283,18 @@
No storage associated with a doubly-linked List object shall be lost
upon assignment or scope exit.
+The execution of an assignment_statement for a list shall have the
+effect of copying the elements from the source list object to the target
+list object.
+
+AARM Note:
+An assignment of a List 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.
+End AARM Note.
+
Implementation Advice
Containers.Doubly_Linked_Lists should be implemented similarly to a linked
@@ -2189,6 +2355,24 @@
Static Semantics
+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
+map values returns an unspecified value. The exact arguments and number of
+calls of this generic formal function by the function "=" on map values are
+unspecified.
+
+ AARM Note: If the actual function for "=" is not symmetric
+ and consistent, the result returned by Map "=" cannot be
+ predicted. The implementation is not required to protect
+ against "=" raising an exception, or returning random results, or any
+ other @lquotes@;bad@rquotes behavior. And it can call "=" in whatever
+ manner makes sense. But note that only the results of Map "=" is unspecified;
+ other subprograms are not allowed to break
+ if "=" is bad (they aren't expected to use "=").
+
+
The type Map is used to represent maps. The type Map needs finalization (see
7.6).
@@ -2206,9 +2390,9 @@
in the map exactly once until the last node is reached. The exact definition of
these terms is different for hashed maps and ordered maps.
-Some operations are assumed to work on a constant set of elements. For such
-an operation, a subprogram is said to *tamper with cursors* of a map object M
-if:
+Some operations are assumed to work on a constant set of elements. During
+execution of such an operation, a subprogram is said to *tamper with cursors*
+of a map object M if:
* it inserts or deletes elements of M, that is, it calls the Insert,
Include, Clear, Delete, or Exclude procedures with M as a parameter; or
@@ -2225,7 +2409,7 @@
Replace only modifies a key and element rather than rehashing, so it does
not tamper with cursors.
-Some operations are assumed to not replace elements. For such an operation, a
+Some operations are assumed to not replace elements. During the execution of such an operation, a
subprogram is said to *tamper with elements* of a map object M if:
* it tampers with cursors of M; or
@@ -2247,6 +2431,12 @@
Cursor is not otherwise initialized, it is initialized to the same
value as No_Element.
+The predefined "=" operator for type Cursor should return True if both cursors
+or No_Element, or designate the same element in the same container.
+
+Execution of the default implementation of the Input, Output, Read, or Write
+attribute of type Cursor raises Program_Error.
+
function "=" (Left, Right : Map) return Boolean;
If Left and Right denote the same map object, then the function returns True. If
@@ -2283,6 +2473,15 @@
If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
Element returns the element component of the node designated by Position.
+procedure Replace_Element (Container : in out Map;
+ Position : in Cursor;
+ New_Item : in Element_Type);
+
+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 Replace_Element assigns New_Item to the element of the node
+designated by Position.
+
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Key : in Key_Type;
@@ -2291,34 +2490,29 @@
If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
Query_Element calls Process.all with the key and element from the node
designated by Position as the arguments. Program_Error is propagated if
-Process.all tampers with the elements of Container. Any exceptions raised by
-Process.all are propagated.
+Process.all tampers with the elements of Container. Any exception raised by
+Process.all is propagated.
procedure Update_Element
- (Position : in Cursor;
- Process : not null access procedure (Key : in Key_Type;
- Element : in out Element_Type));
+ (Container : in out Map;
+ Position : in Cursor;
+ Process : not null access procedure (Key : in Key_Type;
+ Element : in out Element_Type));
-If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
-Update_Element calls Process.all with the key and element from the node
-designated by Position as the arguments. Program_Error is propagated if
-Process.all tampers with the elements of Container. Any exceptions raised
-by Process.all are propagated.
+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 calls Process.all with the key and element
+from the node designated by Position as the arguments. Program_Error is
+propagated if Process.all tampers with the elements of Container. Any
+exceptions raised by Process.all are propagated.
-If Element_Type is unconstrained and definite, then the Element parameter
+If Element_Type is unconstrained and definite, then the actual Element parameter
of Process.all shall be unconstrained.
AARM Note: This means that the elements cannot be directly allocated from the
heap (nor aliased unless AI-363 is included in the Amendment); it must be
possible to change the discriminants of the element in place.
-procedure Replace_Element (Position : in Cursor;
- By : in Element_Type);
-
-If Position equals No_Element, then Constraint_Error is propagated.
-Otherwise Replace_Element assigns By to the element of the node designated by
-Position.
-
procedure Move (Target : in out Map;
Source : in out Map);
@@ -2346,9 +2540,7 @@
Inserted : out Boolean);
Insert inserts Key into Container as per the five-parameter Insert, with the
-difference that an element initialized with any implicit initial values for any
-part (as for an object_declaration with no initialization expression - see
-3.3.1) is inserted.
+difference that an element initialized by default (see 3.3.1) is inserted.
procedure Insert (Container : in out Map;
Key : in Key_Type;
@@ -2403,6 +2595,12 @@
element needs to be updated, use
Replace_Element (Find (Container, Key), New_Element).
+procedure Exclude (Container : in out Map;
+ Key : in Key_Type);
+
+Exclude checks if a node with a key equivalent to Key is present in Container.
+If a match is found, Exclude removes the node from the map.
+
procedure Delete (Container : in out Map;
Key : in Key_Type);
@@ -2424,17 +2622,20 @@
cursors; such cursors are defined to be invalid, which means that execution is
erroneous, and any result is allowed (including not raising an exception).
-procedure Exclude (Container : in out Map;
- Key : in Key_Type);
+function First (Container : Map) return Cursor;
-Exclude checks if a node with a key equivalent to Key is present in Container.
-If a match is found, Exclude removes the node from the map and then
-deallocates the node.
+If Length (Container) = 0, then First returns No_Element. Otherwise,
+First returns a cursor that designates the first node in Container.
-function Contains (Container : Map;
- Key : Key_Type) return Boolean;
+function Next (Position : Cursor) return Cursor;
-Equivalent to Find (Container, Key) /= No_Element.
+Returns a cursor that designates the successor of the node designated by
+Position. If Position designates the last node, then No_Element is returned. If
+Position equals No_Element, then No_Element is returned.
+
+procedure Next (Position : in out Cursor);
+
+Equivalent to Position := Next (Position).
function Find (Container : Map;
Key : Key_Type) return Cursor;
@@ -2448,21 +2649,11 @@
Key : Key_Type) return Element_Type;
Equivalent to Element (Find (Container, Key)).
-
-function First (Container : Map) return Cursor;
-
-If Length (Container) = 0, then First returns No_Element. Otherwise,
-First returns a cursor that designates the first node in Container.
-function Next (Position : Cursor) return Cursor;
-
-Returns a cursor that designates the successor of the node designated by
-Position. If Position designates the last node, then No_Element is returned. If
-Position equals No_Element, then No_Element is returned.
-
-procedure Next (Position : in out Cursor);
+function Contains (Container : Map;
+ Key : Key_Type) return Boolean;
-Equivalent to Position := Next (Position).
+Equivalent to Find (Container, Key) /= No_Element.
function Has_Element (Position : Cursor) return Boolean;
@@ -2478,7 +2669,7 @@
Iterate calls Process.all with a cursor that designates each node in Container,
starting with the first node and moving the cursor according to the successor
-relation. Program_Error is propagated if Process.all tampers with the elements
+relation. Program_Error is propagated if Process.all tampers with the cursors
of Container. Any exception raised by Process.all is propagated.
AARM Note:
@@ -2517,6 +2708,18 @@
No storage associated with a Map object shall be lost upon assignment or
scope exit.
+The execution of an assignment_statement for a map shall have the
+effect of copying the elements from the source map object to the target
+map object.
+
+AARM Note:
+An assignment of a Map 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.
+End AARM Note.
+
Implementation Advice
Move should not copy elements, and should minimize copying of internal
@@ -2562,6 +2765,11 @@
function "=" (Left, Right : Map) return Boolean;
+ function Capacity (Container : Map) return Count_Type;
+
+ procedure Reserve_Capacity (Container : in out Map;
+ Capacity : in Count_Type);
+
function Length (Container : Map) return Count_Type;
function Is_Empty (Container : Map) return Boolean;
@@ -2572,18 +2780,20 @@
function Element (Position : Cursor) return Element_Type;
+ procedure Replace_Element (Container : in out Map;
+ Position : in Cursor;
+ New_Item : in Element_Type);
+
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Key : in Key_Type;
Element : in Element_Type));
procedure Update_Element
- (Position : in Cursor;
- Process : not null access procedure (Key : in Key_Type;
- Element : in out Element_Type));
-
- procedure Replace_Element (Position : in Cursor;
- By : in Element_Type);
+ (Container : in out Map;
+ Position : in Cursor;
+ Process : not null access procedure (Key : in Key_Type;
+ Element : in out Element_Type));
procedure Move (Target : in out Map;
Source : in out Map);
@@ -2611,33 +2821,33 @@
Key : in Key_Type;
New_Item : in Element_Type);
+ procedure Exclude (Container : in out Map;
+ Key : in Key_Type);
+
procedure Delete (Container : in out Map;
Key : in Key_Type);
procedure Delete (Container : in out Map;
Position : in out Cursor);
- procedure Exclude (Container : in out Map;
- Key : in Key_Type);
+ function First (Container : Map)
+ return Cursor;
- function Contains (Container : Map;
- Key : Key_Type) return Boolean;
+ function Next (Position : Cursor) return Cursor;
+
+ procedure Next (Position : in out Cursor);
function Find (Container : Map;
Key : Key_Type)
return Cursor;
+ function Contains (Container : Map;
+ Key : Key_Type) return Boolean;
+
function Element (Container : Map;
Key : Key_Type)
return Element_Type;
- function First (Container : Map)
- return Cursor;
-
- function Next (Position : Cursor) return Cursor;
-
- procedure Next (Position : in out Cursor);
-
function Has_Element (Position : Cursor) return Boolean;
function Equivalent_Keys (Left, Right : Cursor)
@@ -2655,11 +2865,6 @@
(Container : in Map;
Process : not null access procedure (Position : in Cursor));
- function Capacity (Container : Map) return Count_Type;
-
- procedure Reserve_Capacity (Container : in out Map;
- Capacity : in Count_Type);
-
private
... -- not specified by the language
@@ -2687,11 +2892,12 @@
Two keys K1 and K2 are defined to be *equivalent* if Equivalent_Keys (K1, K2)
returns True.
-Function Hash is expected to return the same value each time it is called with a
-particular key value. For any two equivalent key values, Hash is expected to
-return the same value. If Hash behaves in some other manner, the behavior of
-this package is unspecified. Which subprograms of this package call Hash, and
-how many times they call it, is unspecified.
+The actual function for the generic formal function Hash is expected to return the same
+value each time it is called with a particular key value. For any two
+equivalent key values, Hash is expected to return the same value. If Hash
+behaves in some other manner, the behavior of this package is unspecified.
+Which subprograms of this package call Hash, and how many times they call it,
+is unspecified.
AARM Notes
The implementation is not required to protect against Hash raising an exception,
@@ -2703,12 +2909,13 @@
logically a pure function), or the behavior is unspecified.
End AARM Notes
-Function Equivalent_Keys is expected to return the same value each time it is
-called with a particular pair of key values. For any two keys K1 and K2, the
-boolean values Equivalent_Keys (K1, K2) and Equivalent_Key (K2, K1) are expected
-to be equal. If Equivalent_Keys behaves in some other manner, the behavior of
-this package is unspecified. Which subprograms of this package call
-Equivalent_Keys, and how many times they call it, is unspecified.
+The actual function for the generic formal function Equivalent_Keys on Key_Type values
+is expected to return the same value each time it is called with a particular
+pair of key values. It must define an equivalence relationship, that is, be
+reflexive, symmetric, and transitive. If the actual for Equivalent_Keys behaves
+in some other manner, the behavior of this package is unspecified. Which
+subprograms of this package call Equivalent_Keys, and how many times they call
+it, is unspecified.
AARM Note
As with Hash, the implementation is not required to protect against
@@ -2725,7 +2932,7 @@
The implementation is not required to protect against changes to key values
other than via the operations declared in the Hashed_Maps package.
-To see how this could happen, imagine an instantiation of Hashed_Maps where
+To see how this could happen, imagine an instance of Hashed_Maps where
the key type is an access-to-variable type and Hash returns a value derived
from the components of the designated object. Then, any operation that has a
key value could modify those components and change the hash value:
@@ -2746,6 +2953,38 @@
obtained by following the collision list, and going to the next bucket at the
end of each bucket.
+function Capacity (Container : Map) return Count_Type;
+
+Returns the capacity of Container.
+
+procedure Reserve_Capacity (Container : in out Map;
+ Capacity : in Count_Type);
+
+Reserve_Capacity allocates a new hash table such that the length of the
+resulting map can become at least the value Capacity without requiring an
+additional call to Reserve_Capacity, and is large enough to hold the current
+length of Container. Reserve_Capacity then rehashes the nodes in Container onto
+the new hash table. It replaces the old hash table with the new hash table, and
+then deallocates the old hash table. Any exception raised during allocation is
+propagated and Container is not modified.
+
+Reserve_Capacity tampers with the cursors of Container.
+
+AARM Notes: This routine is used to preallocate the internal hash table to the
+specified capacity such that future Inserts do not require expansion of the
+hash table. Therefore, the implementation should allocate the needed memory to
+make that true at this point, even though the visible semantics could be
+preserved by waiting until enough elements are inserted.
+
+While Reserve_Capacity can be used to reduce the capacity of a map, we do not
+specify whether an implementation actually supports reduction of the capacity.
+Since the actual capacity can be anything greater than or equal to Count, an
+implementation never has to reduce the capacity.
+
+Reserve_Capacity tampers with the cursors, as rehashing probably will change
+the order that elements are stored in the map.
+End AARM Notes
+
procedure Clear (Container : in out Map);
In addition to the semantics described in A.18.4, Clear does not affect the
@@ -2781,6 +3020,14 @@
End AARM Notes.
AARM Notes:
+procedure Exclude (Container : in out Map;
+ Key : in Key_Type);
+
+Exclude should only compare keys that hash to the same bucket in the hash
+table. Exclude should work on an empty map; nothing happens in that case.
+End AARM Notes.
+
+AARM Notes:
procedure Delete (Container : in out Map;
Key : in Key_Type);
@@ -2789,21 +3036,6 @@
or it may be saved and reused later.
End AARM Notes.
-AARM Notes:
-procedure Exclude (Container : in out Map;
- Key : in Key_Type);
-
-Exclude should only compare keys that hash to the same bucket in the hash
-table. Exclude should work on an empty map; nothing happens in that case.
-End AARM Notes.
-
-AARM Note:
-function Find (Container : Map;
- Key : Key_Type) return Cursor;
-
-Find should only compare keys that hash to the same bucket in the hash table.
-End AARM Notes.
-
AARM Note:
function First (Container : Map) return Cursor;
@@ -2822,6 +3054,13 @@
in the cursor in order to implement this function.
End AARM Note.
+AARM Note:
+function Find (Container : Map;
+ Key : Key_Type) return Cursor;
+
+Find should only compare keys that hash to the same bucket in the hash table.
+End AARM Notes.
+
function Equivalent_Keys (Left, Right : Cursor)
return Boolean;
@@ -2837,38 +3076,6 @@
Equivalent to Equivalent_Keys (Left, Key (Right)).
-function Capacity (Container : Map) return Count_Type;
-
-Returns the capacity of Container.
-
-procedure Reserve_Capacity (Container : in out Map;
- Capacity : in Count_Type);
-
-Reserve_Capacity allocates a new hash table such that the length of the
-resulting map can become at least the value Capacity without requiring an
-additional call to Reserve_Capacity, and is large enough to hold the current
-length of Container. Reserve_Capacity then rehashes the nodes in Container onto
-the new hash table. It replaces the old hash table with the new hash table, and
-then deallocates the old hash table. Any exception raised during allocation is
-propagated and Container is not modified.
-
-Reserve_Capacity tampers with the cursors of Container.
-
-AARM Notes: This routine is used to preallocate the internal hash table to the
-specified capacity such that future Inserts do not require expansion of the
-hash table. Therefore, the implementation should allocate the needed memory to
-make that true at this point, even though the visible semantics could be
-preserved by waiting until enough elements are inserted.
-
-While Reserve_Capacity can be used to reduce the capacity of a map, we do not
-specify whether an implementation actually supports reduction of the capacity.
-Since the actual capacity can be anything greater than or equal to Count, an
-implementation never has to reduce the capacity.
-
-Reserve_Capacity tampers with the cursors, as rehashing probably will change
-the order that elements are stored in the map.
-End AARM Notes
-
Implementation Advice
If *N* is the length of a map, the average time complexity of the subprograms
@@ -2902,6 +3109,8 @@
package Ada.Containers.Ordered_Maps is
pragma Preelaborate (Ordered_Maps);
+ function Equivalent_Keys (Left, Right : Key_Type) return Boolean;
+
type Map is tagged private;
pragma Preelaborable_Initialization(Map);
@@ -2924,19 +3133,21 @@
function Element (Position : Cursor) return Element_Type;
+ procedure Replace_Element (Container : in out Map;
+ Position : in Cursor;
+ New_Item : in Element_Type);
+
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Key : in Key_Type;
Element : in Element_Type));
procedure Update_Element
- (Position : in Cursor;
- Process : not null access procedure (Key : in Key_Type;
+ (Container : in out Map;
+ Position : in Cursor;
+ Process : not null access procedure (Key : in Key_Type;
Element : in out Element_Type));
- procedure Replace_Element (Position : in Cursor;
- By : in Element_Type);
-
procedure Move (Target : in out Map;
Source : in out Map);
@@ -2963,6 +3174,9 @@
Key : in Key_Type;
New_Item : in Element_Type);
+ procedure Exclude (Container : in out Map;
+ Key : in Key_Type);
+
procedure Delete (Container : in out Map;
Key : in Key_Type);
@@ -2973,36 +3187,18 @@
procedure Delete_Last (Container : in out Map);
- procedure Exclude (Container : in out Map;
- Key : in Key_Type);
-
- function Contains (Container : Map;
- Key : Key_Type) return Boolean;
-
- function Find (Container : Map;
- Key : Key_Type) return Cursor;
-
- function Element (Container : Map;
- Key : Key_Type) return Element_Type;
-
- function Floor (Container : Map;
- Key : Key_Type) return Cursor;
-
- function Ceiling (Container : Map;
- Key : Key_Type) return Cursor;
-
function First (Container : Map) return Cursor;
- function First_Key (Container : Map) return Key_Type;
-
function First_Element (Container : Map) return Element_Type;
- function Last (Container : Map) return Cursor;
+ function First_Key (Container : Map) return Key_Type;
- function Last_Key (Container : Map) return Key_Type;
+ function Last (Container : Map) return Cursor;
function Last_Element (Container : Map) return Element_Type;
+ function Last_Key (Container : Map) return Key_Type;
+
function Next (Position : Cursor) return Cursor;
procedure Next (Position : in out Cursor);
@@ -3011,6 +3207,21 @@
procedure Previous (Position : in out Cursor);
+ function Find (Container : Map;
+ Key : Key_Type) return Cursor;
+
+ function Element (Container : Map;
+ Key : Key_Type) return Element_Type;
+
+ function Floor (Container : Map;
+ Key : Key_Type) return Cursor;
+
+ function Ceiling (Container : Map;
+ Key : Key_Type) return Cursor;
+
+ function Contains (Container : Map;
+ Key : Key_Type) return Boolean;
+
function Has_Element (Position : Cursor) return Boolean;
function "<" (Left, Right : Cursor) return Boolean;
@@ -3040,25 +3251,25 @@
end Ada.Containers.Ordered_Maps;
Two keys K1 and K2 are *equivalent* if both K1 < K2 and K2 < K1 return False,
-using the generic formal "<" operator for keys.
+using the generic formal "<" operator for keys. Function Equivalent_Keys
+returns True if Left and Right are equivalent, and False otherwise.
-Functions "<" and "=" on Key_Type values are expected to return the same result
-value each time they are called with a particular pair of key values. If A = B
-returns True, then B = A is expected to also return True. If A < B returns
-True, then B < A is expected to return False. For any two equivalent elements,
-"=" is expected to return True. If "<" or "=" behaves in some other manner, the
-behavior of this package is unspecified. Which subprograms of this package call
-"<" and "=", and how many times these functions are called, is unspecified.
+The actual function for the generic formal function "<" on Key_Type values is expected
+to return the same value each time it is called with a particular pair of key
+values. It must define a strict ordering relationship, 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.
AARM Notes
-The implementation is not required to protect against "<" or "=" raising an
+The implementation is not required to protect against "<" raising an
exception, or returning random results, or any other "bad" behavior. It's not
-practical to do so, and a broken "<" or "=" function makes the container
+practical to do so, and a broken "<" function makes the container
unusable.
-The implementation can call "<" and "=" whenever it is needed; we don't want to
-specify how often that happens. The result must remain the same (these are
-logically pure functions), or the behavior is unspecified.
+The implementation can call "<" whenever it is needed; we don't want to
+specify how often that happens. The result must remain the same (this is a
+logically pure function), or the behavior is unspecified.
End AARM Notes
If the value of a key stored in a map is changed other than by an operation in
@@ -3069,7 +3280,7 @@
The implementation is not required to protect against changes to key values
other than via the operations declared in the Ordered_Maps package.
-To see how this could happen, imagine an instantiation of Ordered_Maps package
+To see how this could happen, imagine an instance of Ordered_Maps package
where the key type is an access-to-variable type and "<" returns a value
derived from comparing the components of the designated objects. Then, any
operation that has a key value (even if the key value is constant) could modify
@@ -3101,42 +3312,28 @@
If Container is empty, Delete_Last has no effect. Otherwise the node designated
by Last (Container) is removed from Container. Delete_Last tampers with
the cursors of Container.
-
-function Floor (Container : Map;
- Key : Key_Type) return Cursor;
-
-Floor searches for the last node whose key is not greater than Key. If such a
-node is found, a cursor that designates it is returned. Otherwise No_Element is
-returned.
-function Ceiling (Container : Map;
- Key : Key_Type) return Cursor;
+function First_Element (Container : Map) return Element_Type;
-Ceiling searches for the first node whose key is not less than Key, using the
-generic formal "<" operator for keys. If such a node is found, a cursor
-that designates it is returned. Otherwise No_Element is returned.
+Equivalent to Element (First (Container)).
function First_Key (Container : Map) return Key_Type;
Equivalent to Key (First (Container)).
-function First_Element (Container : Map) return Element_Type;
-
-Equivalent to Element (First (Container)).
-
function Last (Container : Map) return Cursor;
Returns a cursor that designates the last node in Container. If Container is
empty, returns No_Element.
-function Last_Key (Container : Map) return Key_Type;
-
-Equivalent to Key (Last (Container)).
-
function Last_Element (Container : Map) return Element_Type;
Equivalent to Element (Last (Container)).
+function Last_Key (Container : Map) return Key_Type;
+
+Equivalent to Key (Last (Container)).
+
function Previous (Position : Cursor) return Cursor;
If Position equals No_Element, then Previous returns No_Element. Otherwise
@@ -3148,6 +3345,20 @@
Equivalent to Position := Previous (Position).
+function Floor (Container : Map;
+ Key : Key_Type) return Cursor;
+
+Floor searches for the last node whose key is not greater than Key, using the
+generic formal "<" operator for keys. If such a node is found, a cursor that
+designates it is returned. Otherwise No_Element is returned.
+
+function Ceiling (Container : Map;
+ Key : Key_Type) return Cursor;
+
+Ceiling searches for the first node whose key is not less than Key, using the
+generic formal "<" operator for keys. If such a node is found, a cursor
+that designates it is returned. Otherwise No_Element is returned.
+
function "<" (Left, Right : Cursor) return Boolean;
Equivalent to Key (Left) < Key (Right).
@@ -3213,6 +3424,23 @@
Static Semantics
+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.
+
+ AARM Note: If the actual function for "=" is not symmetric
+ and consistent, the result returned by Set "=" 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 results of Set "=" is unspecified;
+ other subprograms are not allowed to break
+ if "=" is bad (they aren't expected to use "=").
+
The type Set is used to represent sets. The type Set needs finalization (see
7.6).
@@ -3225,13 +3453,13 @@
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 map exactly once until 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.
-Some operations are assumed to work on a constant set of elements. For such
-an operation, a subprogram is said to *tamper with cursors* of a set object S
-if:
+Some operations are assumed to work on a constant set of elements. During
+execution of such an operation, a subprogram is said to *tamper with cursors*
+of a set object S if:
* it inserts or deletes elements of S, that is, it calls the Insert,
Include, Clear, Delete, Exclude, or Replace_Element procedures with S as
@@ -3242,26 +3470,33 @@
which call one of these as part of their definition are included.
AARM Disucssion: We have to include Replace_Element here because it might
- delete and reinsert the element if it moves in the set.
+ delete and reinsert the element if it moves in the set. That could change
+ the order of iteration, which is what this check is intended to prevent.
+ Also notice that Replace is covered, as it is defined in terms of
+ Replace_Element.
* it finalizes S; or
* it calls the Move procedure with S as a parameter; or
* it calls one of the operations defined to tamper with cursors of S.
-Some operations are assumed to not replace elements. For such an operation, a
+Some operations are assumed to not replace elements. During the execution of such an operation, a
subprogram is said to *tamper with elements* of a set object S if:
- * it tampers with cursors of S; or
- * it replaces one or more elements of S, that is, it calls the
- Replace or Replace_Element procedures with S as a
- parameter.
+ * it tampers with cursors of S.
- AARM Note:
+ AARM Notes:
Complete replacement of an element can cause its memory to be deallocated
while another operation is holding onto a reference to it. That can't be
allowed. However, a simple modification of (part of) an element is not a
problem, so Update_Element_Preserving_Key does not cause a problem.
+ We don't need to include Replace and Replace_Element, as they are included
+ in "tamper with cursors". That means that for Sets, "tamper with cursors"
+ and "tamper with elements" are the same. We leave both terms so that
+ the rules for routines like Query_Element and Iterate are consistent
+ across all containers.
+ End AARM Notes.
+
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.
@@ -3270,6 +3505,12 @@
Cursor is not otherwise initialized, it is initialized to the same
value as No_Element.
+The predefined "=" operator for type Cursor should return True if both cursors
+or No_Element, or designate the same element in the same container.
+
+Execution of the default implementation of the Input, Output, Read, or Write
+attribute of type Cursor raises Program_Error.
+
function "=" (Left, Right : Set) return Boolean;
If Left and Right denote the same set object, then the function returns True.
@@ -3306,6 +3547,25 @@
If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
Element returns the element designated by Position.
+procedure Replace_Element (Container : in out Set;
+ Position : in Cursor;
+ New_Item : in Element_Type);
+
+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.
+
+AARM Note: The final assignment may require that 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.
+
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
@@ -3314,20 +3574,8 @@
Query_Element calls Process.all with the element designated by Position as the
argument. Program_Error is propagated if Process.all tampers with the
elements of Container.
-Any exceptions raised by Process.all are propagated.
+Any exception raised by Process.all is propagated.
-procedure Replace_Element (Container : in Set;
- Position : in Cursor;
- By : in Element_Type);
-
-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, the element designated by Position is tested for
-equivalence to By; if they are found to be equivalent, Replace_Element assigns
-By to the element designated by Position. Otherwise, the element designated by
-Position is removed from the container, then By is inserted into the container.
-If the insertion fails, Program_Error is propagated.
-
procedure Move (Target : in out Set;
Source : in out Set);
@@ -3379,6 +3627,12 @@
match is found, that element is replaced with New_Item; otherwise,
Constraint_Error is propagated.
+procedure Exclude (Container : in out Set;
+ Item : in Element_Type);
+
+Exclude checks if an element equivalent to Item is present in Container. If a
+match is found, Exclude removes the element from the set.
+
procedure Delete (Container : in out Set;
Item : in Element_Type);
@@ -3389,10 +3643,10 @@
procedure Delete (Container : in out Set;
Position : in out Cursor);
-If Position equals No_Element, Delete has no effect. If Position does not
-designate an element in Container, then Program_Error is propagated. Otherwise,
-Delete removes the node designated by Position from the set. Position is set to
-No_Element on return.
+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.
AARM Note: 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
@@ -3400,64 +3654,6 @@
cursors; such cursors are defined to be invalid, which means that execution is
erroneous, and any result is allowed (including not raising an exception).
-procedure Exclude (Container : in out Set;
- Item : in Element_Type);
-
-Exclude checks if an element equivalent to Item is present in Container. If a
-match is found, Exclude removes the element from the set.
-
-function Contains (Container : Set;
- Item : Element_Type) return Boolean;
-
-Equivalent to Find (Container, Item) /= No_Element.
-
-function Find (Container : Set;
- Item : Element_Type) return Cursor;
-
-If Length (Container) equals 0, then Find returns No_Element. Otherwise, Find
-checks if an element equivalent to Item is present in Container. If a match is
-found, a cursor designating the matching element is returned; otherwise,
-No_Element is returned.
-
-function First (Container : Set) return Cursor;
-
-If Length (Container) = 0, then First returns No_Element. Otherwise, First
-returns a cursor that designates the first node in Container.
-
-function Next (Position : Cursor) return Cursor;
-
-Returns a cursor that designates the successor of the element designated by
-Position. If Position designates the last element, then No_Element is returned.
-If Position equals No_Element, then No_Element is returned.
-
-procedure Next (Position : in out Cursor);
-
-Equivalent to Position := Next (Position).
-
-function Has_Element (Position : Cursor) return Boolean;
-
-Returns True if Position designates an element, and returns False otherwise.
-
-AARM Note: To Be Honest: This function may not detect cursors that designate
-deleted elements; such cursors are invalid (see below); the result of
-Has_Element for invalid cursors is unspecified (but not erroneous).
-
-procedure Iterate
- (Container : in Set;
- Process : not null access procedure (Position : in Cursor));
-
-Iterate calls Process.all with a cursor that designates each element in
-Container, starting with the first node and moving the cursor according to the
-successor relation. Program_Error is propagated if Process.all tampers with
-the elements of Container. Any exception raised by Process.all is propagated.
-
-AARM Note:
-This check takes place when the operations that insert or delete elements, etc.
-are called.
-
-See Iterate for vectors for a suggested implementation of the check.
-End AARM Notes.
-
procedure Union (Target : in out Set;
Source : in Set);
@@ -3531,43 +3727,96 @@
AARM Note: This operation is not commutative, so we use parameter names that
make it clear in named notation which set is which.
+function First (Container : Set) return Cursor;
-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.
+If Length (Container) = 0, then First returns No_Element. Otherwise, First
+returns a cursor that designates the first element in Container.
-A key is expected to unambiguously determine one equivalence class for elements.
-The behavior of Generic_Keys is unspecified if the formal parameters of this
-package behave in some other manner.
+function Next (Position : Cursor) return Cursor;
-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 locate an element
-in the set.
+Returns a cursor that designates the successor of the element designated by
+Position. If Position designates the last element, then No_Element is returned.
+If Position equals No_Element, then No_Element is returned.
-procedure Replace (Container : in out Set;
- Key : in Key_Type;
- New_Item : in Element_Type);
+procedure Next (Position : in out Cursor);
-Equivalent to Replace_Element (Container, Find (Container, Key), New_Item).
+Equivalent to Position := Next (Position).
-function Key (Position : Cursor) return Key_Type;
+function Find (Container : Set;
+ Item : Element_Type) return Cursor;
-Equivalent to Key (Element (Position)).
+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.
-procedure Update_Element_Preserving_Key
- (Container : in out Set;
- Position : in Cursor;
- Process : not null access procedure (Element : in out Element_Type));
+function Contains (Container : Set;
+ Item : Element_Type) return Boolean;
-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
+Equivalent to Find (Container, Item) /= No_Element.
+
+function Has_Element (Position : Cursor) return Boolean;
+
+Returns True if Position designates an element, and returns False otherwise.
+
+AARM Note: To Be Honest: This function may not detect cursors that designate
+deleted elements; such cursors are invalid (see below); the result of
+Has_Element for invalid cursors is unspecified (but not erroneous).
+
+procedure Iterate
+ (Container : in Set;
+ Process : not null access procedure (Position : in Cursor));
+
+Iterate calls Process.all with a cursor that designates each element in
+Container, starting with the first element and moving the cursor according to
+the successor relation. Program_Error is propagated if Process.all tampers with
+the cursors of Container. Any exception raised by Process.all is propagated.
+
+AARM Note:
+This check takes place when the operations that insert or delete elements, etc.
+are called.
+
+See Iterate for vectors for a suggested implementation of the check.
+End AARM Notes.
+
+
+
+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.
+
+A key is expected to unambiguously determine one equivalence class for elements.
+The behavior of Generic_Keys is unspecified if the formal parameters of this
+package behave in some other manner.
+
+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 locate an element
+in the set.
+
+procedure Replace (Container : in out Set;
+ Key : in Key_Type;
+ New_Item : in Element_Type);
+
+Equivalent to Replace_Element (Container, Find (Container, Key), New_Item).
+
+function Key (Position : Cursor) return Key_Type;
+
+Equivalent to Key (Element (Position)).
+
+procedure Update_Element_Preserving_Key
+ (Container : in out Set;
+ Position : in Cursor;
+ Process : not null access procedure (Element : in out Element_Type));
+
+If Position equals No_Element, then Constraint_Error is propagated; if Position
+does not designate an element in Container, then Program_Error is propagated.
+Otherwise, Update_Element_Preserving_Key uses Key to save the key value K of the
+element designated by Position. Update_Element_Preserving_Key then calls
Process.all with that element as the argument. Program_Error is propagated
if Process.all tampers with the elements of Container. Any exception raised by
Process.all is propagated. After Process.all returns,
@@ -3578,7 +3827,7 @@
AARM Note: The key check insures that the invariants of the set are preserved
by the modification.
-If Element_Type is unconstrained and definite, then the Element parameter
+If Element_Type is unconstrained and definite, then the actual Element parameter
of Process.all shall be unconstrained.
AARM Note: This means that the elements cannot be directly allocated from the
@@ -3614,6 +3863,18 @@
No storage associated with a Set object shall be lost upon assignment or scope
exit.
+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.
+
+AARM 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.
+End AARM Note.
+
Implementation Advice
Move should not copy elements, and should minimize copying of internal
@@ -3659,6 +3920,11 @@
function Equivalent_Sets (Left, Right : Set) return Boolean;
+ function Capacity (Container : Set) return Count_Type;
+
+ procedure Reserve_Capacity (Container : in out Set;
+ Capacity : in Count_Type);
+
function Length (Container : Set) return Count_Type;
function Is_Empty (Container : Set) return Boolean;
@@ -3667,14 +3933,14 @@
function Element (Position : Cursor) return Element_Type;
+ procedure Replace_Element (Container : in out Set;
+ Position : in Cursor;
+ New_Item : in Element_Type);
+
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
- procedure Replace_Element (Container : in Set;
- Position : in Cursor;
- By : in Element_Type);
-
procedure Move (Target : in out Set;
Source : in out Set);
@@ -3692,44 +3958,15 @@
procedure Replace (Container : in out Set;
New_Item : in Element_Type);
+ procedure Exclude (Container : in out Set;
+ Item : in Element_Type);
+
procedure Delete (Container : in out Set;
Item : in Element_Type);
procedure Delete (Container : in out Set;
Position : in out Cursor);
- procedure Exclude (Container : in out Set;
- Item : in Element_Type);
-
- function Contains (Container : Set;
- Item : Element_Type) return Boolean;
-
- function Find (Container : Set;
- Item : Element_Type) return Cursor;
-
- function First (Container : Set) return Cursor;
-
- function Next (Position : Cursor) return Cursor;
-
- procedure Next (Position : in out Cursor);
-
- function Has_Element (Position : Cursor) return Boolean;
-
- function Equivalent_Elements (Left, Right : Cursor)
- return Boolean;
-
- function Equivalent_Elements (Left : Cursor;
- Right : Element_Type)
- return Boolean;
-
- function Equivalent_Elements (Left : Element_Type;
- Right : Cursor)
- return Boolean;
-
- procedure Iterate
- (Container : in Set;
- Process : not null access procedure (Position : in Cursor));
-
procedure Union (Target : in out Set;
Source : in Set);
@@ -3764,27 +4001,42 @@
function Is_Subset (Subset : Set;
Of_Set : Set) return Boolean;
- function Capacity (Container : Set) return Count_Type;
+ function First (Container : Set) return Cursor;
- procedure Reserve_Capacity (Container : in out Set;
- Capacity : in Count_Type);
+ function Next (Position : Cursor) return Cursor;
+
+ procedure Next (Position : in out Cursor);
+
+ function Find (Container : Set;
+ Item : Element_Type) return Cursor;
+
+ function Contains (Container : Set;
+ Item : Element_Type) return Boolean;
+
+ function Has_Element (Position : Cursor) return Boolean;
+ function Equivalent_Elements (Left, Right : Cursor)
+ return Boolean;
+
+ function Equivalent_Elements (Left : Cursor;
+ Right : Element_Type)
+ return Boolean;
+
+ function Equivalent_Elements (Left : Element_Type;
+ Right : Cursor)
+ return Boolean;
+
+ procedure Iterate
+ (Container : in Set;
+ Process : not null access procedure (Position : in Cursor));
+
generic
- type Key_Type (<>) is limited private;
- with function Key (Element : in Element_Type) return Key_Type;
+ type Key_Type (<>) is private;
+ with function Key (Element : Element_Type) return Key_Type;
with function Hash (Key : Key_Type) return Hash_Type;
- with function Equivalent_Keys (Left : Key_Type; Right : Element_Type)
- return Boolean;
+ with function Equivalent_Keys (Left, Right : Key_Type) return Boolean;
package Generic_Keys is
- function Contains (Container : Set;
- Key : Key_Type)
- return Boolean;
-
- function Find (Container : Set;
- Key : Key_Type)
- return Cursor;
-
function Key (Position : Cursor) return Key_Type;
function Element (Container : Set;
@@ -3795,25 +4047,25 @@
Key : in Key_Type;
New_Item : in Element_Type);
+ procedure Exclude (Container : in out Set;
+ Key : in Key_Type);
+
procedure Delete (Container : in out Set;
Key : in Key_Type);
- procedure Exclude (Container : in out Set;
- Key : in Key_Type);
+ function Find (Container : Set;
+ Key : Key_Type)
+ return Cursor;
+ function Contains (Container : Set;
+ Key : Key_Type)
+ return Boolean;
+
procedure Update_Element_Preserving_Key
(Container : in out Set;
Position : in Cursor;
Process : not null access procedure (Element : in out Element_Type));
- function Equivalent_Keys (Left : Cursor;
- Right : Key_Type)
- return Boolean;
-
- function Equivalent_Keys (Left : Key_Type;
- Right : Cursor)
- return Boolean;
-
end Generic_Keys;
private
@@ -3829,20 +4081,21 @@
Two elements E1 and E2 are defined to be *equivalent* if Equivalent_Elements
(E1, E2) returns True.
-
-Function Hash is expected to return the same value each time it is called with
-a particular element value. For any two equivalent elements, Hash is expected
-to return the same value. If Hash behaves in some other manner, the behavior of
-this package is unspecified. Which subprograms of this package call Hash, and
-how many times they call it, is unspecified.
-Function Equivalent_Elements is expected to return the same value each time
-it is called with a particular pair of element values. For any two elements E1
-and E2, the boolean values Equivalent_Elements (E1, E2) and
-Equivalent_Elements (E2, E1) are expected to be equal. If Equivalent_Elements
-behaves in some other manner, the behavior of this package is unspecified.
-Which subprograms of this package call Equivalent_Elements, and how many times
-they call it, is unspecified.
+The actual function for the generic formal function Hash is expected to return the same
+value each time it is called with a particular element value. For any two
+equivalent elements, the actual for Hash is expected to return the same value.
+If the actual for Hash behaves in some other manner, the behavior of this
+package is unspecified. Which subprograms of this package call Hash, and how
+many times they call it, is unspecified.
+
+The actual function for the generic formal function Equivalent_Elements is expected to
+return the same value each time it is called with a particular pair of Element
+values. It must define an equivalence relationship, that is, be reflexive,
+symmetric, and transitive. If the actual for Equivalent_Elements behaves in
+some other manner, the behavior of this package is unspecified. Which
+subprograms of this package call Equivalent_Elements, and how many times they
+call it, is unspecified.
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 Hash or Equivalent_Elements
@@ -3857,6 +4110,27 @@
element is the successor of a given element, are unspecified, other than the
general semantics described in A.18.7.
+function Capacity (Container : Set) return Count_Type;
+
+Returns the capacity of Container.
+
+procedure Reserve_Capacity (Container : in out Set;
+ Capacity : in Count_Type);
+
+Reserve_Capacity allocates a new hash table such that the length of the
+resulting set can become at least the value Capacity without requiring an
+additional call to Reserve_Capacity, and is large enough to hold the current
+length of Container. Reserve_Capacity then rehashes the elements in Container
+onto the new hash table. It replaces the old hash table with the new hash
+table, and then deallocates the old hash table. Any exception raised during
+allocation is propagated and Container is not modified.
+
+Reserve_Capacity tampers with the cursors of Container.
+
+AARM Note:
+Reserve_Capacity tampers with the cursors, as rehashing probably will change
+the relationships of the elements in Container.
+
procedure Clear (Container : in out Set);
In addition to the semantics described in A.18.7, Clear does not affect the
@@ -3890,50 +4164,18 @@
Right : Cursor) return Boolean;
Equivalent to Equivalent_Elements (Left, Element (Right)).
-
-function Capacity (Container : Set) return Count_Type;
-
-Returns the capacity of Container.
-
-procedure Reserve_Capacity (Container : in out Set;
- Capacity : in Count_Type);
-
-Reserve_Capacity allocates a new hash table such that the length of the
-resulting set can become at least the value Capacity without requiring an
-additional call to Reserve_Capacity, and is large enough to hold the current
-length of Container. Reserve_Capacity then rehashes the elements in Container
-onto the new hash table. It replaces the old hash table with the new hash
-table, and then deallocates the old hash table. Any exception raised during
-allocation is propagated and Container is not modified.
-
-Reserve_Capacity tampers with the cursors of Container.
-
-AARM Note:
-Reserve_Capacity tampers with the cursors, as rehashing probably will change
-the relationships of the elements in Container.
-
-For any element E, the function Generic_Keys.Hash must be such that Hash (E) =
-Generic_Keys.Hash (Key (E)). If Key or Generic_Keys.Hash behave in some other
-manner, the behavior of Generic_Keys is unspecified. Which subprograms of
-Generic_Keys call Generic_Keys.Hash, and how many times they call it, is
-unspecified.
-
-For any two elements E1 and E2, the boolean values Equivalent_Element (E1, E2),
-Equivalent_Keys (Key (E1), E2), and Equivalent_Keys (Key (E2), E1) are all
-expected to be equal. If Key or Equivalent behave in some other manner, the
-behavior of Generic_Keys is unspecified. Which subprograms of Generic_Keys call
-Equivalent, and how many times they call it, is unspecified.
-
-function Equivalent_Keys (Left : Cursor;
- Right : Key_Type) return Boolean;
-
-Equivalent to Equivalent_Keys (Key (Left), Right).
-function Equivalent_Keys (Left : Key_Type;
- Right : Cursor) return Boolean;
-
-Equivalent to Equivalent_Keys (Left, Key (Right)).
-
+For any element E, the actual function for the generic formal function Generic_Keys.Hash
+must be such that Hash (E) = Generic_Keys.Hash (Key (E)). If the actuals for
+Key or Generic_Keys.Hash behave in some other manner, the behavior of
+Generic_Keys is unspecified. Which subprograms of Generic_Keys call
+Generic_Keys.Hash, and how many times they call it, is unspecified.
+
+For any two elements E1 and E2, the boolean values Equivalent_Element (E1, E2)
+and Equivalent_Keys (Key (E1), Key (E2)) are expected to be equal. If the
+actuals for Key or Equivalent_Keys behave in some other manner, the behavior of
+Generic_Keys is unspecified. Which subprograms of Generic_Keys call
+Equivalent_Keys, and how many times they call it, is unspecified.
Implementation Advice
@@ -3962,6 +4204,9 @@
package Ada.Containers.Ordered_Sets is
pragma Preelaborate (Ordered_Sets);
+ function Equivalent_Elements (Left, Right : Element_Type)
+ return Boolean;
+
type Set is tagged private;
pragma Preelaborable_Initialization(Set);
@@ -3984,14 +4229,14 @@
function Element (Position : Cursor) return Element_Type;
+ procedure Replace_Element (Container : in out Set;
+ Position : in Cursor;
+ New_Item : in Element_Type);
+
procedure Query_Element
(Position : in Cursor;
Process : not null access procedure (Element : in Element_Type));
- procedure Replace_Element (Container : in Set;
- Position : in Cursor;
- By : in Element_Type);
-
procedure Move (Target : in out Set;
Source : in out Set);
@@ -4009,13 +4254,13 @@
procedure Replace (Container : in out Set;
New_Item : in Element_Type);
- procedure Delete (Container : in out Set;
- Item : in Element_Type);
-
procedure Exclude (Container : in out Set;
Item : in Element_Type);
procedure Delete (Container : in out Set;
+ Item : in Element_Type);
+
+ procedure Delete (Container : in out Set;
Position : in out Cursor);
procedure Delete_First (Container : in out Set);
@@ -4056,21 +4301,6 @@
function Is_Subset (Subset : Set;
Of_Set : Set) return Boolean;
- function Contains (Container : Set;
- Item : Element_Type) return Boolean;
-
- function Find (Container : Set;
- Item : Element_Type)
- return Cursor;
-
- function Floor (Container : Set;
- Item : Element_Type)
- return Cursor;
-
- function Ceiling (Container : Set;
- Item : Element_Type)
- return Cursor;
-
function First (Container : Set) return Cursor;
function First_Element (Container : Set) return Element_Type;
@@ -4087,6 +4317,21 @@
procedure Previous (Position : in out Cursor);
+ function Find (Container : Set;
+ Item : Element_Type)
+ return Cursor;
+
+ function Floor (Container : Set;
+ Item : Element_Type)
+ return Cursor;
+
+ function Ceiling (Container : Set;
+ Item : Element_Type)
+ return Cursor;
+
+ function Contains (Container : Set;
+ Item : Element_Type) return Boolean;
+
function Has_Element (Position : Cursor) return Boolean;
function "<" (Left, Right : Cursor) return Boolean;
@@ -4114,29 +4359,15 @@
Process : not null access procedure (Position : in Cursor));
generic
- type Key_Type (<>) is limited private;
+ type Key_Type (<>) is private;
with function Key (Element : Element_Type) return Key_Type;
- with function "<" (Left : Key_Type; Right : Element_Type)
+ with function "<" (Left, Right : Key_Type)
return Boolean is <>;
- with function ">" (Left : Key_Type; Right : Element_Type)
- return Boolean is <>;
package Generic_Keys is
-
- function Contains (Container : Set;
- Key : Key_Type) return Boolean;
-
- function Find (Container : Set;
- Key : Key_Type)
- return Cursor;
-
- function Floor (Container : Set;
- Item : Key_Type)
- return Cursor;
-
- function Ceiling (Container : Set;
- Item : Key_Type)
- return Cursor;
+ function Equivalent_Keys (Left, Right : Key_Type)
+ return Boolean;
+
function Key (Position : Cursor) return Key_Type;
function Element (Container : Set;
@@ -4147,23 +4378,26 @@
Key : in Key_Type;
New_Item : in Element_Type);
- procedure Delete (Container : in out Set;
- Key : in Key_Type);
-
procedure Exclude (Container : in out Set;
Key : in Key_Type);
- function "<" (Left : Cursor; Right : Key_Type)
- return Boolean;
+ procedure Delete (Container : in out Set;
+ Key : in Key_Type);
- function ">" (Left : Cursor; Right : Key_Type)
- return Boolean;
+ function Find (Container : Set;
+ Key : Key_Type)
+ return Cursor;
- function "<" (Left : Key_Type; Right : Cursor)
- return Boolean;
+ function Floor (Container : Set;
+ Key : Key_Type)
+ return Cursor;
- function ">" (Left : Key_Type; Right : Cursor)
- return Boolean;
+ function Ceiling (Container : Set;
+ Key : Key_Type)
+ return Cursor;
+
+ function Contains (Container : Set;
+ Key : Key_Type) return Boolean;
procedure Update_Element_Preserving_Key
(Container : in out Set;
@@ -4181,15 +4415,15 @@
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.
-Functions "<" and "=" on Element_Type values are expected to return the same
-result value each time they are called with a particular pair of element values.
-If A = B returns True, then B = A is expected to also return True. If A < B
-returns True, then B < A is expected to return False. For any two equivalent
-elements, "=" is expected to return True. If "<" or "=" behaves in some other
-manner, the behavior of this package is unspecified. Which subprograms of this
-package call "<" and "=", and how many times these functions are called, is
-unspecified.
+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 must define a strict ordering relationship, 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.
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
@@ -4219,27 +4453,13 @@
designated by Last (Container) is removed from Container. Delete_Last
tampers with the cursors of Container.
-function Floor (Container : Set;
- Item : Element_Type) return Cursor;
-
-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.
-
-function Ceiling (Container : Set;
- Item : Element_Type) return Cursor;
-
-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.
-
function First_Element (Container : Set) return Element_Type;
Equivalent to Element (First (Container)).
function Last (Container : Set) return Cursor;
-Returns a cursor that designates the last node in Container. If Container is
+Returns a cursor that designates the last element in Container. If Container is
empty, returns No_Element.
function Last_Element (Container : Set) return Element_Type;
@@ -4257,6 +4477,20 @@
Equivalent to Position := Previous (Position).
+function Floor (Container : Set;
+ Item : Element_Type) return Cursor;
+
+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.
+
+function Ceiling (Container : Set;
+ Item : Element_Type) return Cursor;
+
+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.
+
function "<" (Left, Right : Cursor) return Boolean;
Equivalent to Element (Left) < Element (Right).
@@ -4287,20 +4521,22 @@
Iterates over the elements in Container as per Iterate, with the difference
that the elements are traversed in predecessor order, starting with the last
-node.
+element.
-For any two elements E1 and E2, the boolean values (E1 < E2), (Key(E1) < E2),
-and (Key(E2) > E1) are all expected to be equal. If Key, Generic_Keys."<", or
-Generic_Keys.">" behave in some other manner, the behavior of this package is
-unspecified. Which subprograms of this package call Key, Generic_Keys."<" and
-Generic_Keys.">", and how many times the functions are called, is unspecified.
+For any two elements E1 and E2, the boolean values (E1 < E2) and
+(Key(E1) < Key(E2)) are expected to be equal. If the actual for Key or
+Generic_Keys."<" behave in some other manner, the behavior of this package is
+unspecified. Which subprograms of this package call Key or Generic_Keys."<",
+and how many times the functions are called, is unspecified.
In addition to the semantics described in A.18.7, the subprograms in package
-Generic_Keys named Floor, Ceiling, "<", and ">", are equivalent to the
+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
-Generic_Keys generic formal relational operators.
+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
@@ -4326,11 +4562,27 @@
The declaration of the generic library package Containers.Indefinite_Vectors
has the same contents as Containers.Vectors except:
+
+ * The generic formal Element_Type is indefinite.
+
+ * The procedures with the profiles:
+ procedure Insert (Container : in out Vector;
+ Before : in Extended_Index;
+ Count : in Count_Type := 1);
+ procedure Insert (Container : in out Vector;
+ Before : in Cursor;
+ Position : out Cursor;
+ Count : in Count_Type := 1);
+ are omitted.
- * The generic formal Element_Type is indefinite.
+AARM Note: These procedures are omitted because there is no
+way to create a default-initialized object of an indefinite type. Note that
+Insert_Space can be used instead of this routine in most cases. Omitting
+the routine completely allows any problems to be be diagnosed by
+the compiler when converting from a definite to indefinite vector.
- * The Element parameter of access subprogram Process of Update_Element
- may be constrained even if Element_Type is unconstrained.
+ * The actual Element parameter of access subprogram Process of Update_Element
+ may be constrained even if Element_Type is unconstrained.
A.18.11 The Package Containers.Indefinite_Doubly_Linked_Lists
@@ -4366,7 +4618,7 @@
omitting the routine completely, any problems will be diagnosed by the
compiler.
- * The Element parameter of access subprogram Process of Update_Element
+ * The actual Element parameter of access subprogram Process of Update_Element
may be constrained even if Element_Type is unconstrained.
@@ -4403,7 +4655,7 @@
omitting the routine completely, any problems will be diagnosed by the
compiler.
- * The Element parameter of access subprogram Process of Update_Element
+ * The actual Element parameter of access subprogram Process of Update_Element
may be constrained even if Element_Type is unconstrained.
@@ -4441,7 +4693,7 @@
omitting the routine completely, any problems will be diagnosed by the
compiler.
- * The Element parameter of access subprogram Process of Update_Element
+ * The actual Element parameter of access subprogram Process of Update_Element
may be constrained even if Element_Type is unconstrained.
@@ -4459,7 +4711,7 @@
* The generic formal Element_Type is indefinite.
- * The Element parameter of access subprogram Process of
+ * The actual Element parameter of access subprogram Process of
Update_Element_Preserving_Key may be constrained even if Element_Type is
unconstrained.
@@ -4479,7 +4731,7 @@
* The generic formal Element_Type is indefinite.
- * The Element parameter of access subprogram Process of
+ * The actual Element parameter of access subprogram Process of
Update_Element_Preserving_Key may be constrained even if Element_Type is
unconstrained.
@@ -4508,6 +4760,14 @@
sorted smallest first as determined by the generic formal "<" operator
provided. Any exception raised during evaluation of "<" is propagated.
+The actual function for the generic formal function "<" of Generic_Array_Sort
+is expected to return the same value each time it is called with a particular
+pair of element values. It should define a strict ordering relationship, that
+is, be irreflexive, asymmetric, and transitive; it should not modify Container.
+If the actual for "<" behaves in some other manner, the behavior of the
+instance of Generic_Array_Sort is unspecified. How many times
+Generic_Array_Sort calls "<" is unspecified.
+
AARM Notes
This implies swapping the elements, usually including an intermediate copy.
This of course means that the elements will be copied. Since the elements are
@@ -4538,9 +4798,18 @@
sorted smallest first as determined by the generic formal "<" operator
provided. Any exception raised during evaluation of "<" is propagated.
+The actual function for the generic formal function "<" of
+Generic_Constrained_Array_Sort is expected to return the same value each time
+it is called with a particular pair of element values. It should define a
+strict ordering relationship, that is, be irreflexive, asymmetric, and
+transitive; it should not modify Container. If the actual for "<" behaves in
+some other manner, the behavior of the instance of
+Generic_Constrained_Array_Sort is unspecified. How many times
+Generic_Constrained_Array_Sort calls "<" is unspecified.
+
Implementation Advice
-The worst-case time complexity of a call on an instantiation of
+The worst-case time complexity of a call on an instance of
Containers.Generic_Array_Sort or Containers.Generic_Constrained_Array_Sort
should be O(N**2) or better, and the average time complexity should be better
than O(N**2), where *N* is the length of the Container parameter.
@@ -4589,10 +4858,10 @@
procedure Copy (A : Array_Subtype) is
V : Vector := To_Vector (Count => A'Length);
- J : Index_Subtype'Base := Index_Subtype'First;
+ J : Extended_Index'Base := Extended_Index'First+1;
begin
for I in A'Range loop
- Replace_Element (V, Index => J, By => A (I));
+ Replace_Element (V, Index => J, New_Item => A (I));
J := J + 1;
end loop;
...
@@ -4646,7 +4915,7 @@
Insert_Space (V, Before => I, Count => A'Length); -- dig the hole
for Index in A'Range loop
- Replace_Element (V, J, By => A (Index)); -- fill the hole
+ Replace_Element (V, J, New_Item => A (Index)); -- fill the hole
J := J + 1;
end loop;
...
@@ -4725,7 +4994,7 @@
by the language:
procedure Op (V : in Vector) is
- procedure Process (E : in Element_Subtype) is ...;
+ procedure Process (E : in Element_Type) is ...;
begin
for I in First_Index (V) .. Last_Index (V) loop
Process (E => Element (V, I));
@@ -4736,7 +5005,7 @@
We could also use the cursor-based operations to do the same thing.
procedure Op (V : in Vector) is
- procedure Process (E : in Element_Subtype) is ...;
+ procedure Process (E : in Element_Type) is ...;
I : Cursor := First (V);
begin
@@ -4750,7 +5019,7 @@
use a passive iterator:
procedure Op (V : in Vector) is
- procedure Process (E : in Element_Subtype) is ...;
+ procedure Process (E : in Element_Type) is ...;
procedure Process (I : in Cursor) is
begin
@@ -4768,8 +5037,8 @@
procedure Append
(V : Vector_of_Lists.Vector;
- I : Index_Subtype;
- E : Element_Subtype) is
+ I : Index_Type;
+ E : Element_Type) is
procedure Process (L : in out List) is
begin
@@ -4803,7 +5072,7 @@
Append (L, New_Item => Empty_Vector);
-- Move (don't copy) vector V onto list L:
- Update_Element (Last (L), Move_V'Access);
+ Update_Element (L, Last (L), Move_V'Access);
end;
A new, default-initialized vector element is appended to L, and then
@@ -4814,12 +5083,12 @@
allows array-like modification of vector elements:
procedure Op (V : in out Vector) is
- I : Index_Subtype := ...;
- E : Element_Subtype := ...;
+ I : Index_Type := ...;
+ E : Element_Type := ...;
begin
Insert (V, Before => I, New_Item => E);
... -- modify E some more
- Replace_Element (V, Index => I, By => E); -- aka V(I) := E;
+ Replace_Element (V, Index => I, New_Item => E); -- aka V(I) := E;
end;
All containers are nonlimited, and hence allow ordinary assignment. In
@@ -4930,7 +5199,7 @@
Position => C); -- Return value
-- Modify default-initialized value:
- Update_Element (C, Process'Access);
+ Update_Element (L, C, Process'Access);
end Op;
@@ -4972,7 +5241,7 @@
procedure Process (C : in Map_Types.Cursor) is
K : Key_Subtype := Key (C);
- E : Element_Subtype := Element (C);
+ E : Element_Type := Element (C);
begin
... -- do whatever
end;
@@ -5213,7 +5482,7 @@
Position => Position,
Inserted => Inserted);
- Update_Element (Position, Increment'Access);
+ Update_Element (Wordcount_Map, Position, Increment'Access);
end Insert;
@@ -5449,7 +5718,7 @@
Context.Ref_Count := 0;
... -- init context
- Replace_Element (Position, By => Context);
+ Replace_Element (File_Cache, Position, New_Item => Context);
else
@@ -5652,7 +5921,7 @@
procedure Process (C : in Id_Map_Types.Cursor) is
begin
- Update_Element (C, Free'Access); -- Free a session.
+ Update_Element (Id_Map, C, Free'Access); -- Free a session.
end;
begin -- Shutdown_Sessions
@@ -5998,27 +6267,13 @@
Generic_Keys, which allows you to explicitly name the key-part of the
element. We can instantiate that package like this:
- function "<"
- (Employee : Employee_Type;
- SSN : SSN_Type) return Boolean is
- begin
- return Employee.SSN < SSN;
- end;
-
- function ">"
- (Employee : Employee_Type;
- SSN : SSN_Type) return Boolean is
- begin
- return Employee.SSN > SSN;
- end;
-
function SSN (Employee : Employee_Type) return SSN_Type is
begin
return Employee.SSN;
end;
package SSN_Keys is
- new Employee_Sets.Generic_Keys (SSN_Type, Key => SSN);
+ new Employee_Sets.Generic_Keys (SSN_Type, Key => SSN, "<" => "<");
-- Use defaults for other parameters
With this new package we can now look up the employee by his SSN
@@ -6241,20 +6496,6 @@
-- instead of Id_Map, use a set to store sessions:
Session_Set : Session_Set_Types.Set;
- function "<"
- (Session : Session_Access;
- Id : String) return Boolean is
- begin
- return Session.Id < Id;
- end;
-
- function ">"
- (Session : Session_Access;
- Id : String) return Boolean is
- begin
- return Session.Id > Id;
- end;
-
function Id (Session : Session_Access) return String is
begin
return Session.Id;
@@ -6324,9 +6565,10 @@
Facilities for handling strings of Wide_Character elements are found in the
packages Strings.Wide_Maps, Strings.Wide_Fixed, Strings.Wide_Bounded,
Strings.Wide_Unbounded, and Strings.Wide_Maps.Wide_Constants, and in the
-functions Strings.Wide_Hash and Strings.Wide_Unbounded.Wide_Hash. They provide
-the same string-handling operations as the corresponding packages and functions
-for strings of Character elements.
+functions Strings.Wide_Hash, Strings.Wide_Fixed.Wide_Hash,
+Strings.Wide_Bounded.Wide_Hash, and Strings.Wide_Unbounded.Wide_Hash.
+They provide the same string-handling operations as the corresponding packages
+and functions for strings of Character elements.
!corrigendum A.4.7(29)
@@ -6337,8 +6579,8 @@
contents except that
@dby
For each of the packages Strings.Fixed, Strings.Bounded, Strings.Unbounded, and
-Strings.Maps.Constants, and for functions Strings.Hash and
-Strings.Unbounded.Hash, the
+Strings.Maps.Constants, and for functions Strings.Hash, Strings.Fixed.Hash,
+Strings.Bounded.Hash, and Strings.Unbounded.Hash, the
corresponding wide string package has the same contents except that
@@ -6352,26 +6594,45 @@
@xcode<@b<with> Ada.Containers;
@b<function> Ada.Strings.Hash (Key : String) @b<return> Containers.Hash_Type;
-@b<pragma> Pure (Ada.Strings.Hash);>
+@b<pragma> Pure (Hash);>
+
+@xindent<Returns an implementation-defined value which is a function of the
+value of Key. If @i<A> and @i<B> are strings such that @i<A> equals @i<B>,
+Hash(@i<A>) equals Hash(@i<B>).>
+
+The library function Strings.Fixed.Hash has the following declaration:
+
+@xcode<@b<with> Ada.Containers, Ada.Strings.Hash;
+@b<function> Ada.Strings.Fixed.Hash (Key : String) @b<return> Containers.Hash_Type
+ @b<renames> Ada.Strings.Hash;
+@b<pragma> Pure (Hash);>
+
+The generic library function Strings.Bounded.Hash has the following declaration:
+
+@xcode<@b<with> Ada.Containers;
+@b<generic>
+ @b<with package> Bounded @b<is>
+ @b<new> Ada.Strings.Bounded.Generic_Bounded_Length (<@>);
+@b<function> Ada.Strings.Bounded.Hash (Key : Bounded.Bounded_String)
+ @b<return> Containers.Hash_Type;
+@b<pragma> Pure (Hash);>
-@xindent<Return an implementation-defined value which is a function of the
-value of Key. If A and B are strings such that A equals B, Hash(A) equals
-Hash(B).>
+Strings.Bounded.Hash is equivalent to the function call
+Strings.Hash (Bounded.To_String (Key));
The library function Strings.Unbounded.Hash has the following declaration:
@xcode<@b<with> Ada.Containers;
-@b<function> Ada.Strings.Unbounded.Hash (Key : Unbounded_String) @b<return>
- Containers.Hash_Type;
-@b<pragma> Preelaborate (Ada.Strings.Unbounded.Hash);>
-
-@xindent<Return an implementation-defined value which is a function of the
-value of Key. If A and B are unbounded strings such that A equals B, Hash(A)
-equals Hash(B).>
+@b<function> Ada.Strings.Unbounded.Hash (Key : Unbounded_String)
+ @b<return> Containers.Hash_Type;
+@b<pragma> Pure (Hash);>
+Strings.Unbounded.Hash is equivalent to the function call
+Strings.Hash (To_String (Key));
+
@i<@s8<Implementation Advice>>
-The various Hash functions should be good hash functions, returning
+The Hash functions should be good hash functions, returning
a wide spread of values for different string values. It should be unlikely
for similar strings to return the same value.
@@ -6384,18 +6645,20 @@
A variety of sequence and associative containers are provided. Each container
includes a @i<cursor> type. A cursor is a reference to an element within a
-container. Many operations on cursors are common to all of the containers.
+container. Many operations on cursors are common to all of the containers. A
+cursor referencing an element in a container is considered to be overlapping
+with the container object itself.
Within this clause we provide Implementation Advice for the desired
average or worst case time complexity of certain operations on a
-container. This advice is expressed using a big-O notation.
-A complexity of O(f(N)), presuming f is some function of a
-length parameter N and t(N) is the time the operation takes
-(on average or worst case, as specified) for the length N,
-means that there exists a finite A such that for any N, t(N)/f(N) < A.
+container. This advice is expressed using the Landau symbol @i<O>(X).
+Presuming f is some function of a length parameter N and t(N) is the time the
+operation takes (on average or worst case, as specified) for the length N,
+a complexity of @i<O>(f(N)) means that there exists a finite A such that for
+any N, t(N)/f(N) < A.
If the advice suggests that the complexity should be less than
-O(f(N)), then for any arbitrarily small positive real D, there
+@i<O>(f(N)), then for any arbitrarily small positive real D, there
should exist a positive integer M such that for all N > M,
t(N)/f(N) < D.
@@ -6440,6 +6703,10 @@
elements that can be inserted into the vector prior to it being automatically
expanded.
+Elements in a vector container can be refered to by an index value of a
+generic formal type. The first element of a vector always has its index
+value equal to the lower bound of the formal type.
+
A vector container may contain @i<empty elements>. Empty elements do not have a
specified value.
@@ -6461,8 +6728,6 @@
Index_Type'Min (Index_Type'Base'Last - 1, Index_Type'Last) + 1;
No_Index : @b<constant> Extended_Index := Extended_Index'First;
- @b<subtype> Index_Subtype @b<is> Index_Type;
-
@b<type> Vector @b<is tagged private>;
@b<pragma> Preelaborable_Initialization(Vector);
@@ -6473,6 +6738,8 @@
No_Element : @b<constant> Cursor;
+ @b<function> "=" (Left, Right : Vector) @b<return> Boolean;
+
@b<function> To_Vector (Length : Count_Type) @b<return> Vector;
@b<function> To_Vector
@@ -6489,8 +6756,6 @@
@b<function> "&" (Left, Right : Element_Type) @b<return> Vector;
- @b<function> "=" (Left, Right : Vector) @b<return> Boolean;
-
@b<function> Capacity (Container : Vector) @b<return> Count_Type;
@b<procedure> Reserve_Capacity (Container : @b<in out> Vector;
@@ -6498,6 +6763,9 @@
@b<function> Length (Container : Vector) @b<return> Count_Type;
+ @b<procedure> Set_Length (Container : @b<in out> Vector;
+ Length : @b<in> Count_Type);
+
@b<function> Is_Empty (Container : Vector) @b<return> Boolean;
@b<procedure> Clear (Container : @b<in out> Vector);
@@ -6513,6 +6781,14 @@
@b<function> Element (Position : Cursor) @b<return> Element_Type;
+ @b<procedure> Replace_Element (Container : @b<in out> Vector;
+ Index : @b<in> Index_Type;
+ New_Item : @b<in> Element_Type);
+
+ @b<procedure> Replace_Element (Container : @b<in out> Vector;
+ Position : @b<in> Cursor;
+ New_Item : @b<in> Element_Type);
+
@b<procedure> Query_Element
(Container : @b<in> Vector;
Index : @b<in> Index_Type;
@@ -6523,20 +6799,14 @@
Process : @b<not null access procedure> (Element : @b<in> Element_Type));
@b<procedure> Update_Element
- (Container : @b<in> Vector;
- Index : @b<in> Index_Type;
+ (Container : @b<in out> Vector;
+ Index : @b<in> Index_Type;
Process : @b<not null access procedure> (Element : @b<in out> Element_Type));
@b<procedure> Update_Element
- (Position : @b<in> Cursor;
- Process : @b<not null access procedure> (Element : @b<in out> Element_Type));
-
- @b<procedure> Replace_Element (Container : @b<in> Vector;
- Index : @b<in> Index_Type;
- By : @b<in> Element_Type);
-
- @b<procedure> Replace_Element (Position : @b<in> Cursor;
- By : @b<in> Element_Type);
+ (Container : @b<in out> Vector;
+ Position : @b<in> Cursor;
+ Process : @b<not null access procedure> (Element : @b<in out> Element_Type));
@b<procedure> Assign (Target : @b<in out> Vector;
Source : @b<in> Vector);
@@ -6573,6 +6843,15 @@
Position : @b<out> Cursor;
Count : @b<in> Count_Type := 1);
+ @b<procedure> Insert (Container : @b<in out> Vector;
+ Before : @b<in> Extended_Index;
+ Count : @b<in> Count_Type := 1);
+
+ @b<procedure> Insert (Container : @b<in out> Vector;
+ Before : @b<in> Cursor;
+ Position : @b<out> Cursor;
+ Count : @b<in> Count_Type := 1);
+
@b<procedure> Prepend (Container : @b<in out> Vector;
New_Item : @b<in> Vector);
@@ -6596,9 +6875,6 @@
Position : @b<out> Cursor;
Count : @b<in> Count_Type := 1);
- @b<procedure> Set_Length (Container : @b<in out> Vector;
- Length : @b<in> Count_Type);
-
@b<procedure> Delete (Container : @b<in out> Vector;
Index : @b<in> Extended_Index;
Count : @b<in> Count_Type := 1);
@@ -6613,6 +6889,14 @@
@b<procedure> Delete_Last (Container : @b<in out> Vector;
Count : @b<in> Count_Type := 1);
+ @b<procedure> Reverse_Elements (Container : @b<in out> Vector);
+
+ @b<procedure> Swap (Container : @b<in out> Vector;
+ I, J : @b<in> Index_Type);
+
+ @b<procedure> Swap (Container : @b<in out> Vector;
+ I, J : @b<in> Cursor);
+
@b<function> First_Index (Container : Vector) @b<return> Index_Type;
@b<function> First (Container : Vector) @b<return> Cursor;
@@ -6626,25 +6910,14 @@
@b<function> Last_Element (Container : Vector)
@b<return> Element_Type;
-
- @b<procedure> Swap (Container : @b<in> Vector;
- I, J : @b<in> Index_Type);
-
- @b<procedure> Swap (I, J : @b<in> Cursor);
-
- @b<generic>
- @b<with function> "<" (Left, Right : Element_Type)
- @b<return> Boolean is <@>;
- @b<package> Generic_Sorting @b<is>
- @b<function> Is_Sorted (Container : Vector) @b<return> Boolean;
+ @b<function> Next (Position : Cursor) @b<return> Cursor;
- @b<procedure> Sort (Container : @b<in out> Vector);
+ @b<procedure> Next (Position : @b<in out> Cursor);
- @b<procedure> Merge (Target : @b<in out> Vector;
- Source : @b<in out> Vector);
+ @b<function> Previous (Position : Cursor) @b<return> Cursor;
- @b<end> Generic_Sorting;
+ @b<procedure> Previous (Position : @b<in out> Cursor);
@b<function> Find_Index (Container : Vector;
Item : Element_Type;
@@ -6670,14 +6943,6 @@
Item : Element_Type) @b<return> Boolean;
- @b<function> Next (Position : Cursor) @b<return> Cursor;
-
- @b<function> Previous (Position : Cursor) @b<return> Cursor;
-
- @b<procedure> Next (Position : @b<in out> Cursor);
-
- @b<procedure> Previous (Position : @b<in out> Cursor);
-
@b<function> Has_Element (Position : Cursor) @b<return> Boolean;
@b<procedure> Iterate
@@ -6688,6 +6953,20 @@
(Container : @b<in> Vector;
Process : @b<not null access procedure> (Position : @b<in> Cursor));
+ @b<generic>
+ @b<with function> "<" (Left, Right : Element_Type)
+ @b<return> Boolean is <@>;
+ @b<package> Generic_Sorting @b<is>
+
+ @b<function> Is_Sorted (Container : Vector) @b<return> Boolean;
+
+ @b<procedure> Sort (Container : @b<in out> Vector);
+
+ @b<procedure> Merge (Target : @b<in out> Vector;
+ Source : @b<in out> Vector);
+
+ @b<end> Generic_Sorting;
+
@b<private>
... -- @ft<@i<not specified by the language>>
@@ -6695,6 +6974,13 @@
@b<end> Ada.Containers.Vectors;>
+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 functions defined to use it return an
+unspecified value. The exact arguments and number of calls of this generic
+formal function by the functions defined to use it are unspecified.
+
The type Vector is used to represent vectors. The type Vector needs finalization
(see 7.6).
@@ -6706,13 +6992,19 @@
Cursor is not otherwise initialized, it is initialized to the same value as
No_Element.
+The predefined "=" operator for type Cursor should return True if both cursors
+or No_Element, or designate the same element in the same container.
+
+Execution of the default implementation of the Input, Output, Read, or Write
+attribute of type Cursor raises Program_Error.
+
No_Index represents a position that does not correspond to any element. The
subtype Extended_Index includes the indices covered by Index_Type plus the
value No_Index and, if it exists, the successor to the Index_Type'Last.
-Some operations are assumed to work on a constant set of elements. For such
-an operation, a subprogram is said to @i<tamper with cursors> of a vector
-object @i<V> if:
+Some operations are assumed to work on a constant set of elements. During
+execution of such an operation, a subprogram is said to @i<tamper with cursors>
+of a vector object @i<V> if:
@xbullet<it inserts or deletes elements of @i<V>, that is, it calls the Insert,
Insert_Space, Clear, Delete, or Set_Length procedures with @i<V> as a
@@ -6723,13 +7015,23 @@
@xbullet<it calls the Move procedure with @i<V> as
a parameter.>
-Some operations are assumed to not replace elements. For such an operation, a
+Some operations are assumed to not replace elements. During the execution of such an operation, a
subprogram is said to @i<tamper with elements> of a vector object @i<V> if:
@xbullet<it tampers with cursors of @i<V>; or>
@xbullet<it replaces one or more elements of @i<V>, that is, it calls the
-Replace_Element or Swap procedures or the Sort or Merge procedures of an
-instance of Generic_Sorting with @i<V> as a parameter.>
+Replace_Element, Reverse_Elements, or Swap procedures or the Sort or Merge
+procedures of an instance of Generic_Sorting with @i<V> as a parameter.>
+
+@xcode<@b<function> "=" (Left, Right : Vector) @b<return> Boolean;>
+
+@xindent<If Left and Right denote the same vector object, then the function returns
+True. If Left and Right have different lengths, then the function returns
+False. Otherwise, it compares each element in Left to the corresponding element
+in Right using the generic formal equality operator; if element equality
+returns False, then the function returns False. 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.>
@xcode<@b<function> To_Vector (Length : Count_Type) @b<return> Vector;>
@@ -6762,16 +7064,6 @@
@xindent<Returns a vector comprising the element Left followed by the element Right.>
-@xcode<@b<function> "=" (Left, Right : Vector) @b<return> Boolean;>
-
-@xindent<If Left and Right denote the same vector object, then the function returns
-True. If Left and Right have different lengths, then the function returns
-False. Otherwise, it compares each element in Left to the corresponding element
-in Right using the generic formal equality operator; if element equality
-returns False, then the function returns False. 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.>
-
@xcode<@b<function> Capacity (Container : Vector) @b<return> Count_Type;>
@xindent<Returns the capacity of Container.>
@@ -6790,6 +7082,15 @@
@xindent<Returns the number of elements in Container.>
+@xcode<@b<procedure> Set_Length (Container : @b<in out> Vector;
+ Length : @b<in> Count_Type);>
+
+@xindent<If Length is larger than the capacity of Container, Set_Length calls
+Reserve_Capacity (Container, Length), then sets the length of the
+Container to Length. If Length is greater than the original length of
+Container, empty elements are added to Container; otherwise elements are
+removed from Container.>
+
@xcode<@b<function> Is_Empty (Container : Vector) @b<return> Boolean;>
@xindent<Equivalent to Length (Container) = 0.>
@@ -6825,6 +7126,27 @@
@xindent<If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
Element returns the element designated by Position.>
+@xcode<@b<procedure> Replace_Element (Container : @b<in out> Vector;
+ Index : @b<in> Index_Type;
+ New_Item : @b<in> Element_Type);>
+
+@xindent<If Index is not in the range First_Index (Container) .. Last_Index (Container),
+then Constraint_Error is propagated. Otherwise Replace_Element assigns the
+value New_Item to the element at position Index. Any exception raised during the
+assignment is propagated. The element at position Index is not an empty element
+after successful call to Replace_Element.>
+
+@xcode<@b<procedure> Replace_Element (Container : @b<in out> Vector;
+ Position : @b<in> Cursor;
+ New_Item : @b<in> Element_Type);>
+
+@xindent<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 Replace_Element assigns New_Item to the element
+designated by Position. Any exception raised during the assignment is
+propagated. The element at Position is not an empty element after successful
+call to Replace_Element.>
+
@xcode<@b<procedure> Query_Element
(Container : @b<in> Vector;
Index : @b<in> Index_Type;
@@ -6846,8 +7168,8 @@
elements of Container. Any exception raised by Process.@b<all> is propagated.>
@xcode<@b<procedure> Update_Element
- (Container : @b<in> Vector;
- Index : @b<in> Index_Type;
+ (Container : @b<in out> Vector;
+ Index : @b<in> Index_Type;
Process : @b<not null access> @b<procedure> (Element : @b<in out> Element_Type));>
@xindent<If Index is not in the range First_Index (Container) .. Last_Index (Container),
@@ -6856,45 +7178,30 @@
if Process.@b<all> tampers with the elements of Container. Any exception raised by
Process.@b<all> is propagated.>
-@xindent<If Element_Type is unconstrained and definite, then the Element parameter
+@xindent<If Element_Type is unconstrained and definite, then the actual Element parameter
of Process.@b<all> shall be unconstrained.>
@xindent<The element at position Index is not an empty element after successful
completion of this operation.>
@xcode<@b<procedure> Update_Element
- (Position : @b<in> Cursor;
- Process : @b<not null access> @b<procedure> (Element : @b<in out> Element_Type));>
+ (Container : @b<in out> Vector;
+ Position : @b<in> Cursor;
+ Process : @b<not null access> @b<procedure> (Element : @b<in out> Element_Type));>
-@xindent<If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
-Update_Element calls Process.@b<all> with the element designated by Position as the
-argument. Program_Error is propagated if Process.@b<all> tampers with the
-elements of Container. Any exception raised by Process.@b<all> is propagated.>
+@xindent<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 calls Process.@b<all> with the element
+designated by Position as the argument. Program_Error is propagated if
+Process.@b<all> tampers with the elements of Container. Any exception raised by
+Process.@b<all> is propagated.>
-@xindent<If Element_Type is unconstrained and definite, then the Element parameter
+@xindent<If Element_Type is unconstrained and definite, then the actual Element parameter
of Process.@b<all> shall be unconstrained.>
@xindent<The element designated by Position is not an empty element after successful
completion of this operation.>
-@xcode<@b<procedure> Replace_Element (Container : @b<in> Vector;
- Index : @b<in> Index_Type;
- By : @b<in> Element_Type);>
-
-@xindent<If Index is not in the range First_Index (Container) .. Last_Index (Container),
-then Constraint_Error is propagated. Otherwise Replace_Element assigns the
-value By to the element at position Index. Any exception raised during the
-assignment is propagated. The element at position Index is not an empty element
-after successful call to Replace_Element.>
-
-@xcode<@b<procedure> Replace_Element (Position : @b<in> Cursor;
- By : @b<in> Element_Type);>
-
-@xindent<If Position equals No_Element, then Constraint_Error is propagated. Otherwise
-Replace_Element assigns By to the element designated by Position. Any exception
-raised during the assignment is propagated. The element at Position is
-not an empty element after successful call to Replace_Element.>
-
@xcode<@b<procedure> Assign (Target : @b<in out> Vector;
Source : @b<in> Vector);>
@@ -6975,17 +7282,44 @@
@xindent<Equivalent to Insert (Container, Before, To_Vector (New_Item, Count), Position);>
+@xcode<@b<procedure> Insert (Container : @b<in out> Vector;
+ Before : @b<in> Extended_Index;
+ Count : @b<in> Count_Type := 1);>
+
+@xindent<If Before is not in the range First_Index (Container) .. Last_Index (Container)
++ 1, then Constraint_Error is propagated. If Count is 0, then Insert_Space does
+nothing. Otherwise, it computes the new length @i<NL> as the sum of the current
+length and Count; if the value of Last appropriate for length @i<NL> would be
+greater than Index_Type'Last then Constraint_Error is propagated.>
+
+@xindent<If the current vector capacity is less than or equal to @i<NL>,
+Reserve_Capacity (Container, @i<NL>) is called to increase the vector capacity.
+Then Insert_Space slides the elements in the range Before .. Last_Index
+(Container) up by Count positions, and then inserts elements that are
+initialized by default (see 3.3.1) in the positions starting at Before.>
+
+@xcode<@b<procedure> Insert (Container : @b<in out> Vector;
+ Before : @b<in> Cursor;
+ Position : @b<out> Cursor;
+ Count : @b<in> Count_Type := 1);>
+
+@xindent<If Before is not No_Element, and does not designate an element in
+Container, then Program_Error is propagated.
+If Before equals No_Element, then let @i<T> be Last_Index (Container) + 1;
+otherwise, let @i<T> be To_Index (Before). Insert (Container, @i<T>, Count) is
+called, and then Position is set to To_Cursor (Container, @i<T>).>
+
@xcode<@b<procedure> Prepend (Container : @b<in out> Vector;
New_Item : @b<in> Vector;
Count : @b<in> Count_Type := 1);>
-@xindent<Equivalent to Insert (Container, Index_Type'First, New_Item).>
+@xindent<Equivalent to Insert (Container, First_Index (Container), New_Item).>
@xcode<@b<procedure> Prepend (Container : @b<in out> Vector;
New_Item : @b<in> Element_Type;
Count : @b<in> Count_Type := 1);>
-@xindent<Equivalent to Insert (Container, Index_Type'First, New_Item, Count).>
+@xindent<Equivalent to Insert (Container, First_Index (Container), New_Item, Count).>
@xcode<@b<procedure> Append (Container : @b<in out> Vector;
New_Item : @b<in> Vector);>
@@ -7025,15 +7359,6 @@
otherwise, let @i<T> be To_Index (Before). Insert_Space (Container, @i<T>, Count) is
called, and then Position is set to To_Cursor (Container, @i<T>).>
-@xcode<@b<procedure> Set_Length (Container : @b<in out> Vector;
- Length : @b<in> Count_Type);>
-
-@xindent<If Length is larger than the capacity of Container, Set_Length calls
-Reserve_Capacity (Container, Length), then sets the length of the
-Container to Length. If Length is greater than the original length of
-Container, empty elements are added to Container; otherwise elements are
-removed from Container.>
-
@xcode<@b<procedure> Delete (Container : @b<in out> Vector;
Index : @b<in> Extended_Index;
Count : @b<in> Count_Type := 1);>
@@ -7050,12 +7375,13 @@
@xindent<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 (Container, To_Index (Position), Count) is called.>
+Otherwise, Delete (Container, To_Index (Position), Count) is called, and
+then Position is set to No_Element.>
@xcode<@b<procedure> Delete_First (Container : @b<in out> Vector;
Count : @b<in> Count_Type := 1);>
-@xindent<Equivalent to Delete (Container, Index_Type'First, Count).>
+@xindent<Equivalent to Delete (Container, First_Index (Container), Count).>
@xcode<@b<procedure> Delete_Last (Container : @b<in out> Vector;
Count : @b<in> Count_Type := 1);>
@@ -7064,6 +7390,25 @@
Clear (Container). Otherwise it is equivalent to Delete (Container,
Index_Type'Val(Index_Type'Pos(Last_Index(Container)) @endash Count + 1), Count).>
+@xcode<@b<procedure> Reverse_Elements (Container : @b<in out> Vector);>
+
+@xindent<Reorders the elements of Container in reverse order.>
+
+@xcode<@b<procedure> Swap (Container : @b<in out> Vector;
+ I, J : @b<in> Index_Type);>
+
+@xindent<If I or J is not in the range First_Index (Container) .. Last_Index (Container),
+then Constraint_Error is propagated. Otherwise, Swap exchanges the values of
+the elements at positions I and J.>
+
+@xcode<@b<procedure> Swap (Container : @b<in out> Vector;
+ I, J : @b<in> Cursor);>
+
+@xindent<If either I or J is No_Element, then Constraint_Error is propagated.
+If either I or J do not designate an element in Container, then Program_Error
+is propagated. Otherwise Swap exchanges the values of the elements designated
+by I and J.>
+
@xcode<@b<function> First_Index (Container : Vector) @b<return> Index_Type;>
@xindent<Returns the value Index_Type'First.>
@@ -7088,43 +7433,30 @@
that designates the last element in Container.>
@xcode<@b<function> Last_Element (Container : Vector) @b<return> Element_Type;>
-
-@xindent<Equivalent to Element (Container, Last_Index (Container)).>
-
-@xcode<@b<procedure> Swap (Container : @b<in> Vector;
- I, J : @b<in> Index_Type);>
-@xindent<If I or J is not in the range First_Index (Container) .. Last_Index (Container),
-then Constraint_Error is propagated. Otherwise, Swap exchanges the values of
-the elements at positions I and J.>
+@xindent<Equivalent to Element (Container, Last_Index (Container)).>
-@xcode<@b<procedure> Swap (I, J : @b<in> Cursor);>
+@xcode<@b<function> Next (Position : Cursor) @b<return> Cursor;>
-@xindent<If either I or J is No_Element, then Constraint_Error is propagated. If I and J
-designate elements in different containers, then Program_Error is propagated.
-Otherwise Swap exchanges the values of the elements designated by I and J.>
+@xindent<If Position equals No_Element or designates the last element of the container,
+then Next returns the value No_Element. Otherwise, returns a cursor that
+designates the element with index To_Index (Position) + 1 in the same vector as
+Position.>
-@xcode<@b<function> Is_Sorted (Container : Vector) @b<return> Boolean;>
+@xcode<@b<procedure> Next (Position : @b<in out> Cursor);>
-@xindent<Returns True if the elements are sorted smallest first as determined
-by the generic formal "<" operator; otherwise, Is_Sorted returns False.
-Any exception raised during evaluation of "<" is propagated.>
+@xindent<Equivalent to Position := Next (Position).>
-@xcode<@b<procedure> Sort (Container : @b<in out> Vector);>
+@xcode<@b<function> Previous (Position : Cursor) @b<return> Cursor;>
-@xindent<Reorders the elements of Container such that the elements are
-sorted smallest first as determined by the generic formal "<" operator
-provided. Any exception raised during evaluation of "<" is propagated.>
+@xindent<If Position equals No_Element or designates the first element of the container,
+then Previous returns the value No_Element. Otherwise, returns a cursor that
+designates the element with index (To_Index (Position) @endash 1) in the same
+vector as Position.>
-@xcode<@b<procedure> Merge (Target : @b<in out> Vector;
- Source : @b<in out> Vector);>
+@xcode<@b<procedure> Previous (Position : @b<in out> Cursor);>
-@xindent<Merge removes elements from Source and inserts them into Target;
-afterwards, Target contains the union of the elements that were initially in
-Source and Target; Source is left empty. If Target and Source are initially
-sorted smallest first, then Target is ordered smallest first as determined by
-the generic formal "<" operator; otherwise, the order of elements in Target is
-unspecified. Any exception raised during evaluation of "<" is propagated.>
+@xindent<Equivalent to Position := Previous (Position).>
@xcode<@b<function> Find_Index (Container : Vector;
Item : Element_Type;
@@ -7148,7 +7480,7 @@
equality operator). The search starts at the first element if Cursor equals
No_Element, and at the element designated by Cursor otherwise. It proceeds
towards the last element of Container. If no equal element is found, then
-Find returns No_Cursor. Otherwise, it returns a cursor designating the first
+Find returns No_Element. Otherwise, it returns a cursor designating the first
equal element encountered.>
@xcode<@b<function> Reverse_Find_Index (Container : Vector;
@@ -7174,7 +7506,7 @@
equality operator). The search starts at the last element if Cursor equals
No_Element, and at the element designated by Cursor otherwise. It proceeds
towards the first element of Container. If no equal element is found, then
-Reverse_Find returns No_Cursor. Otherwise, it returns a cursor designating
+Reverse_Find returns No_Element. Otherwise, it returns a cursor designating
the first equal element encountered.>
@xcode<@b<function> Contains (Container : Vector;
@@ -7182,28 +7514,6 @@
@xindent<Equivalent to Has_Element (Find (Container, Item)).>
-@xcode<@b<function> Next (Position : Cursor) @b<return> Cursor;>
-
-@xindent<If Position equals No_Element or designates the last element of the container,
-then Next returns the value No_Element. Otherwise, returns a cursor that
-designates the element with index To_Index (Position) + 1 in the same vector as
-Position.>
-
-@xcode<@b<function> Previous (Position : Cursor) @b<return> Cursor;>
-
-@xindent<If Position equals No_Element or designates the first element of the container,
-then Previous returns the value No_Element. Otherwise, returns a cursor that
-designates the element with index (To_Index (Position) @endash 1) in the same
-vector as Position.>
-
-@xcode<@b<procedure> Next (Position : @b<in out> Cursor);>
-
-@xindent<Equivalent to Position := Next (Position).>
-
-@xcode<@b<procedure> Previous (Position : @b<in out> Cursor);>
-
-@xindent<Equivalent to Position := Previous (Position).>
-
@xcode<@b<function> Has_Element (Position : Cursor) @b<return> Boolean;>
@xindent<Returns True if Position designates an element, and returns False otherwise.>
@@ -7220,16 +7530,46 @@
(Container : @b<in> Vector;
Process : @b<not null access> @b<procedure> (Position : @b<in> Cursor));>
-@xindent<Iterates over the nodes in Container as per Iterate, except that elements are
-traversed in reverse index order.>
+@xindent<Iterates over the elements in Container as per Iterate, except that
+elements are traversed in reverse index order.>
+
+The actual function for the generic formal function "<" of Generic_Sorting is
+expected to return the same value each time it is called with a particular pair
+of element values. It should define a strict ordering relationship, that is, be
+irreflexive, asymmetric, and transitive; it should not modify Container. If the
+actual for "<" behaves in some other manner, the behavior of the subprograms of
+Generic_Sorting are unspecified. How many times the subprograms of
+Generic_Sorting call "<" is unspecified.
+
+@xcode<@b<function> Is_Sorted (Container : Vector) @b<return> Boolean;>
+
+@xindent<Returns True if the elements are sorted smallest first as determined
+by the generic formal "<" operator; otherwise, Is_Sorted returns False.
+Any exception raised during evaluation of "<" is propagated.>
+@xcode<@b<procedure> Sort (Container : @b<in out> Vector);>
+
+@xindent<Reorders the elements of Container such that the elements are
+sorted smallest first as determined by the generic formal "<" operator
+provided. Any exception raised during evaluation of "<" is propagated.>
+
+@xcode<@b<procedure> Merge (Target : @b<in out> Vector;
+ Source : @b<in out> Vector);>
+
+@xindent<Merge removes elements from Source and inserts them into Target;
+afterwards, Target contains the union of the elements that were initially in
+Source and Target; Source is left empty. If Target and Source are initially
+sorted smallest first, then Target is ordered smallest first as determined by
+the generic formal "<" operator; otherwise, the order of elements in Target is
+unspecified. Any exception raised during evaluation of "<" is propagated.>
+
@i<@s8<Bounded (Run-Time) Errors>>
Reading the value of an empty element by calling Element, Query_Element,
Update_Element, Swap, Is_Sorted, Sort, Merge, "=", Find, or Reverse_Find is
-a bounded error. The implementation may treat the element as having any valid
-value of the element type, or raise Constraint_Error or Program_Error before
-modifying the vector.
+a bounded error. The implementation may treat the element as having any normal
+value (see 13.9.1) of the element type, or raise Constraint_Error or
+Program_Error before modifying the vector.
Calling Merge in an instance of Generic_Sorting with either Source or Target
not ordered smallest first using the provided generic formal "<" operator
@@ -7245,7 +7585,8 @@
such an index value) less than or equal to the index value of the element
designated by the cursor; or>
@xbullet<The vector that contains the element it designates has been passed
-to the Sort or Merge procedures of an instance of Generic_Sorting.>
+to the Sort or Merge procedures of an instance of Generic_Sorting, or to the
+Reverse_Elements procedure.>
It is a bounded error to call any subprogram other than "=" or Has_Element
declared in Containers.Vectors with an ambiguous (but not invalid, see below)
@@ -7276,19 +7617,24 @@
No storage associated with a vector object shall be lost upon assignment or
scope exit.
+The execution of an @fa<assignment_statement> for a vector shall have the
+effect of copying the elements from the source vector object to the target
+vector object.
+
@i<@s8<Implementation Advice>>
Containers.Vectors should be implemented similarly to an array. In particular,
if the length of a vector is @i<N>, then
-@xbullet<the worst-case time complexity of Append with Count=1 and Element
-should be O(log @i<N>); and>
+@xbullet<the worst-case time complexity of Element should be @i<O>(log @i<N>);>
+@xbullet<the worst-case time complexity of Append with Count=1 when
+@i<N> is less than the capacity of the vector should be @i<O>(log @i<N>); and>
@xbullet<the worst-case time complexity of Prepend with Count=1 and Delete_First
-with Count=1 should be O(@i<N> log @i<N>).>
+with Count=1 should be @i<O>(@i<N> log @i<N>).>
The worst-case time complexity of a call on procedure Sort of an instantiation
-of Containers.Vectors.Generic_Sorting should be O(@i<N>**2), and
-the average time complexity should be better than O(@i<N>**2).
+of Containers.Vectors.Generic_Sorting should be @i<O>(@i<N>**2), and
+the average time complexity should be better than @i<O>(@i<N>**2).
Containers.Vectors.Generic_Sorting.Sort and Containers.Vectors.Generic_Sorting.Merge
should minimize copying of elements.
@@ -7304,7 +7650,7 @@
If a sparse container is required, a Hashed_Map should be used rather than a
vector.
@hr
-42 If Index_Type'Base'First = Index_Type'First an instantiation of
+42 If Index_Type'Base'First = Index_Type'First an instance of
Ada.Containers.Vectors will raise Constraint_Error. A value below
Index_Type'First is required so that an empty vector has a meaningful
value of Last_Index.>>
@@ -7359,28 +7705,22 @@
@b<function> Element (Position : Cursor)
@b<return> Element_Type;
+ @b<procedure> Replace_Element (Container : @b<in out> List;
+ Position : @b<in> Cursor;
+ New_Item : @b<in> Element_Type);
+
@b<procedure> Query_Element
(Position : @b<in> Cursor;
Process : @b<not null access procedure> (Element : @b<in> Element_Type));
@b<procedure> Update_Element
- (Position : @b<in> Cursor;
- Process : @b<not null access procedure> (Element : @b<in out> Element_Type));
-
- @b<procedure> Replace_Element (Position : @b<in> Cursor;
- By : @b<in> Element_Type);
+ (Container : @b<in out> List;
+ Position : @b<in> Cursor;
+ Process : @b<not null access procedure> (Element : @b<in out> Element_Type));
@b<procedure> Move (Target : @b<in out> List;
Source : @b<in out> List);
- @b<procedure> Prepend (Container : @b<in out> List;
- New_Item : @b<in> Element_Type;
- Count : @b<in> Count_Type := 1);
-
- @b<procedure> Append (Container : @b<in out> List;
- New_Item : @b<in> Element_Type;
- Count : @b<in> Count_Type := 1);
-
@b<procedure> Insert (Container : @b<in out> List;
Before : @b<in> Cursor;
New_Item : @b<in> Element_Type;
@@ -7397,6 +7737,14 @@
Position : @b<out> Cursor;
Count : @b<in> Count_Type := 1);
+ @b<procedure> Prepend (Container : @b<in out> List;
+ New_Item : @b<in> Element_Type;
+ Count : @b<in> Count_Type := 1);
+
+ @b<procedure> Append (Container : @b<in out> List;
+ New_Item : @b<in> Element_Type;
+ Count : @b<in> Count_Type := 1);
+
@b<procedure> Delete (Container : @b<in out> List;
Position : @b<in out> Cursor;
Count : @b<in> Count_Type := 1);
@@ -7406,24 +7754,11 @@
@b<procedure> Delete_Last (Container : @b<in out> List;
Count : @b<in> Count_Type := 1);
-
- @b<generic>
- @b<with function> "<" (Left, Right : Element_Type)
- @b<return> Boolean is <@>;
- @b<package> Generic_Sorting @b<is>
-
- @b<function> Is_Sorted (Container : List) @b<return> Boolean;
-
- @b<procedure> Sort (Container : @b<in out> List);
-
- @b<procedure> Merge (Target : @b<in out> List;
- Source : @b<in out> List);
-
- @b<end> Generic_Sorting;
- @b<procedure> Reverse_List (Container : @b<in out> List);
+ @b<procedure> Reverse_Elements (Container : @b<in out> List);
- @b<procedure> Swap (I, J : @b<in> Cursor);
+ @b<procedure> Swap (Container : @b<in out> List;
+ I, J : @b<in> Cursor);
@b<procedure> Swap_Links (Container : @b<in out> List;
I, J : @b<in> Cursor);
@@ -7451,9 +7786,14 @@
@b<function> Last_Element (Container : List)
@b<return> Element_Type;
- @b<function> Contains (Container : List;
- Item : Element_Type) @b<return> Boolean;
+ @b<function> Next (Position : Cursor) @b<return> Cursor;
+
+ @b<procedure> Next (Position : @b<in out> Cursor);
+ @b<function> Previous (Position : Cursor) @b<return> Cursor;
+
+ @b<procedure> Previous (Position : @b<in out> Cursor);
+
@b<function> Find (Container : List;
Item : Element_Type;
Position : Cursor := No_Element)
@@ -7463,14 +7803,9 @@
Item : Element_Type;
Position : Cursor := No_Element)
@b<return> Cursor;
-
- @b<function> Next (Position : Cursor) @b<return> Cursor;
-
- @b<function> Previous (Position : Cursor) @b<return> Cursor;
- @b<procedure> Next (Position : @b<in out> Cursor);
-
- @b<procedure> Previous (Position : @b<in out> Cursor);
+ @b<function> Contains (Container : List;
+ Item : Element_Type) @b<return> Boolean;
@b<function> Has_Element (Position : Cursor) @b<return> Boolean;
@@ -7482,12 +7817,34 @@
(Container : @b<in> List;
Process : @b<not null access procedure> (Position : @b<in> Cursor));
+ @b<generic>
+ @b<with function> "<" (Left, Right : Element_Type)
+ @b<return> Boolean is <@>;
+ @b<package> Generic_Sorting @b<is>
+
+ @b<function> Is_Sorted (Container : List) @b<return> Boolean;
+
+ @b<procedure> Sort (Container : @b<in out> List);
+
+ @b<procedure> Merge (Target : @b<in out> List;
+ Source : @b<in out> List);
+
+ @b<end> Generic_Sorting;
+
@b<private>
... -- @ft<@i<not specified by the language>>
@b<end> Ada.Containers.Doubly_Linked_Lists;>
+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 functions Find, Reverse_Find, and "=" on
+list values return an unspecified value. The exact arguments and number of
+calls of this generic formal function by the functions Find, Reverse_Find, and
+"=" on list values are unspecified.
+
The type List is used to represent lists. The type List needs finalization (see
7.6).
@@ -7499,21 +7856,27 @@
Cursor is not otherwise initialized, it is initialized to the same value as
No_Element.
-Some operations are assumed to work on a constant set of elements. For such
-an operation, a subprogram is said to @i<tamper with cursors> of a list object
-@i<L> if:
+The predefined "=" operator for type Cursor should return True if both cursors
+or No_Element, or designate the same element in the same container.
+Execution of the default implementation of the Input, Output, Read, or Write
+attribute of type Cursor raises Program_Error.
+
+Some operations are assumed to work on a constant set of elements. During
+execution of such an operation, a subprogram is said to @i<tamper with cursors>
+of a list object @i<L> if:
+
@xbullet<it inserts or deletes elements of @i<L>, that is, it calls the Insert,
Clear, Delete, or Delete_Last procedures with @i<L> as a parameter; or>
@xbullet<it reorders the elements of @i<L>, that is, it calls the Splice,
-Swap_Links, or Reverse_List procedures or the Sort or Merge procedures of
+Swap_Links, or Reverse_Elements procedures or the Sort or Merge procedures of
an instance of Generic_Sorting with @i<L> as a parameter; or>
@xbullet<it finalizes @i<L>; or>
@xbullet<it calls the Move procedure with @i<L> as a parameter.>
-Some operations are assumed to not replace elements. For such an operation, a
+Some operations are assumed to not replace elements. During the execution of such an operation, a
subprogram is said to @i<tamper with elements> of a list object @i<L> if:
@xbullet<it tampers with cursors of @i<L>; or>
@@ -7547,34 +7910,39 @@
@xindent<If Position equals No_Element, then Constraint_Error is propagated.
Otherwise, Element returns the element designated by Position.>
+@xcode<@b<procedure> Replace_Element (Container : @b<in out> List;
+ Position : @b<in> Cursor;
+ New_Item : @b<in> Element_Type);>
+
+@xindent<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 Replace_Element assigns the value New_Item to the element
+designated by Position.>
+
@xcode<@b<procedure> Query_Element
(Position : @b<in> Cursor;
Process : @b<not null access procedure> (Element : @b<in> Element_Type));>
@xindent<If Position equals No_Element, then Constraint_Error is propagated.
-Otherwise, Query_Element calls Process.@b<all> with the element on node designated by
+Otherwise, Query_Element calls Process.@b<all> with the element designated by
Position as the argument. Program_Error is propagated if Process.@b<all> tampers
with the elements of Container. Any exception raised by Process.@b<all> is propagated.>
@xcode<@b<procedure> Update_Element
- (Position : @b<in> Cursor;
- Process : @b<not null access procedure> (Element : @b<in out> Element_Type));>
+ (Container : @b<in out> List;
+ Position : @b<in> Cursor;
+ Process : @b<not null access procedure> (Element : @b<in out> Element_Type));>
-@xindent<If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
-Update_Element calls Process.@b<all> with the element on node designated by
-Position as the argument. Program_Error is propagated if Process.@b<all> tampers
-with the elements of Container. Any exceptions raised by Process.@b<all> are propagated.>
+@xindent<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 calls Process.@b<all> with the element
+designated by Position as the argument. Program_Error is propagated if
+Process.@b<all> tampers with the elements of Container. Any exception raised
+by Process.@b<all> is propagated.>
-@xindent<If Element_Type is unconstrained and definite, then the Element parameter
+@xindent<If Element_Type is unconstrained and definite, then the actual Element parameter
of Process.@b<all> shall be unconstrained.>
-@xcode<@b<procedure> Replace_Element (Position : Cursor;
- By : Element_Type);>
-
-@xindent<If Position equals No_Element, then Constraint_Error is propagated. Otherwise
-Replace_Element assigns the value By to the element designated by
-Position.>
-
@xcode<@b<procedure> Move (Target : @b<in out> List;
Source : @b<in out> List);>
@@ -7583,18 +7951,6 @@
are moved to Target (in the original order). The length of Target is set to the
length of Source, and the length of Source is set to 0.>
-@xcode<@b<procedure> Prepend (Container : @b<in out> List;
- New_Item : @b<in> Element_Type;
- Count : @b<in> Count_Type := 1);>
-
-@xindent<Equivalent to Insert (Container, First (Container), New_Item, Count).>
-
-@xcode<@b<procedure> Append (Container : @b<in out> List;
- New_Item : @b<in> Element_Type;
- Count : @b<in> Count_Type := 1);>
-
-@xindent<Equivalent to Insert (Container, No_Element, New_Item, Count).>
-
@xcode<@b<procedure> Insert (Container : @b<in out> List;
Before : @b<in> Cursor;
New_Item : @b<in> Element_Type;
@@ -7633,11 +7989,22 @@
Otherwise, Insert inserts Count new elements
prior to the element designated by Before. If Before equals No_Element, the new
elements are inserted after the last node (if any). The new elements are
-initialized with any implicit initial value for any part (as for an
-@fa<object_declaration> with no initialization expression @emdash see 3.3.1).
+initialized by default (see 3.3.1).
Any exception raised during allocation of internal storage is propagated, and
Container is not modified.>
+@xcode<@b<procedure> Prepend (Container : @b<in out> List;
+ New_Item : @b<in> Element_Type;
+ Count : @b<in> Count_Type := 1);>
+
+@xindent<Equivalent to Insert (Container, First (Container), New_Item, Count).>
+
+@xcode<@b<procedure> Append (Container : @b<in out> List;
+ New_Item : @b<in> Element_Type;
+ Count : @b<in> Count_Type := 1);>
+
+@xindent<Equivalent to Insert (Container, No_Element, New_Item, Count).>
+
@xcode<@b<procedure> Delete (Container : @b<in out> List;
Position : @b<in out> Cursor;
Count : @b<in> Count_Type := 1);>
@@ -7646,7 +8013,8 @@
does not designate an element in Container, then Program_Error is propagated.
Otherwise Delete removes (from Container) Count elements starting at the
element designated by Position (or all of the elements starting at Position
-if there are fewer than Count elements starting at Position).>
+if there are fewer than Count elements starting at Position).
+Finally, Position is set to No_Element.>
@xcode<@b<procedure> Delete_First (Container : @b<in out> List;
Count : @b<in> Count_Type := 1);>
@@ -7658,40 +8026,18 @@
@xindent<If Length (Container) <= Count then Delete_Last is equivalent to Clear
(Container). Otherwise it removes the last Count nodes from Container.>
-
-@xcode<@b<function> Is_Sorted (Container : List) @b<return> Boolean;>
-
-@xindent<Returns True if the elements are sorted smallest first as determined by the
-generic formal "<" operator; otherwise, Is_Sorted returns False.
-Any exception raised during evaluation of "<" is propagated.>
-@xcode<@b<procedure> Sort (Container : @b<in out> List);>
-
-@xindent<Reorders the nodes of Container such that the elements are
-sorted smallest first as determined by the generic formal "<" operator
-provided. The sort is stable. Any exception raised during evaluation of
-"<" is propagated.>
-
-@xcode<@b<procedure> Merge (Target : @b<in out> List;
- Source : @b<in out> List);>
-
-@xindent<Merge removes elements from Source and inserts them into Target;
-afterwards, Target contains the union of the elements that were initially
-in Source and Target; Source is left empty.
-If Target and Source are initially sorted smallest first, then Target is
-ordered smallest first as determined by the generic formal "<" operator;
-otherwise, the order of elements in Target is unspecified.
-Any exception raised during evaluation of "<" is propagated.>
-
-@xcode<@b<procedure> Reverse_List (Container : @b<in out> List);>
+@xcode<@b<procedure> Reverse_Elements (Container : @b<in out> List);>
@xindent<Reorders the elements of Container in reverse order.>
-@xcode<@b<procedure> Swap (I, J : @b<in> Cursor);>
+@xcode<@b<procedure> Swap (Container : @b<in out> List;
+ I, J : @b<in> Cursor);>
-@xindent<If either I or J is No_Element, then Constraint_Error is propagated. If I and J
-designate elements in different containers, then Program_Error is propagated.
-Otherwise Swap exchanges the values of the elements designated by I and J.>
+@xindent<If either I or J is No_Element, then Constraint_Error is propagated.
+If either I or J do not designate an element in Container, then Program_Error
+is propagated. Otherwise Swap exchanges the values of the elements designated
+by I and J.>
@xcode<@b<procedure> Swap_Links (Container : @b<in out> List;
I, J : @b<in> Cursor);>
@@ -7760,10 +8106,25 @@
@xindent<Equivalent to Element (Last (Container)).>
-@xcode<@b<function> Contains (Container : List;
- Item : Element_Type) @b<return> Boolean;>
+@xcode<@b<function> Next (Position : Cursor) @b<return> Cursor;>
-@xindent<Equivalent to Find (Container, Item) /= No_Element.>
+@xindent<If Position equals No_Element or designates the last element of the container,
+then Next returns the value No_Element. Otherwise, it returns a cursor that
+designates the successor of the element designated by Position.>
+
+@xcode<@b<procedure> Next (Position : @b<in out> Cursor);>
+
+@xindent<Equivalent to Position := Next (Position).>
+
+@xcode<@b<function> Previous (Position : Cursor) @b<return> Cursor;>
+
+@xindent<If Position equals No_Element or designates the first element of the container,
+then Previous returns the value No_Element. Otherwise, it returns a cursor that
+designates the predecessor of the element designated by Position.>
+
+@xcode<@b<procedure> Previous (Position : @b<in out> Cursor);>
+
+@xindent<Equivalent to Position := Previous (Position).>
@xcode<@b<function> Find (Container : List;
Item : Element_Type;
@@ -7777,40 +8138,25 @@
at the first element if Position equals No_Element. It proceeds towards Last
(Container). If no equal element is found, then Find returns No_Element.
Otherwise, it returns a cursor designating the first equal element encountered.>
-
-@xcode<@b<function> Reverse_Find (Container : List;
- Item : Element_Type;
- Position : Cursor := No_Element)
- @b<return> Cursor;>
-
-@xindent<If Position is not No_Element, and does not designate an element
-in Container, then Program_Error is propagated. Find searches the elements of
-Container for an element equal to Item (in the sense of the generic formal
-equality operator). The search starts at the element designated by Position, or
-at the lastelement if Position equals No_Element. It proceeds towards First
-(Container). If no equal element is found, then Reverse_Find returns
-No_Element. Otherwise, it returns a cursor designating the first equal element
-encountered.>
-
-@xcode<@b<function> Next (Position : Cursor) @b<return> Cursor;>
-
-@xindent<If Position equals No_Element or designates the last element of the container,
-then Next returns the value No_Element. Otherwise, it returns a cursor that
-designates the successor of the element designated by Position.>
-
-@xcode<@b<function> Previous (Position : Cursor) @b<return> Cursor;>
-
-@xindent<If Position equals No_Element or designates the first element of the container,
-then Previous returns the value No_Element. Otherwise, it returns a cursor that
-designates the predecessor of the element designated by Position.>
-@xcode<@b<procedure> Next (Position : @b<in out> Cursor);>
+@xcode<@b<function> Reverse_Find (Container : List;
+ Item : Element_Type;
+ Position : Cursor := No_Element)
+ @b<return> Cursor;>
-@xindent<Equivalent to Position := Next (Position).>
+@xindent<If Position is not No_Element, and does not designate an element
+in Container, then Program_Error is propagated. Find searches the elements of
+Container for an element equal to Item (in the sense of the generic formal
+equality operator). The search starts at the element designated by Position, or
+at the last element if Position equals No_Element. It proceeds towards First
+(Container). If no equal element is found, then Reverse_Find returns
+No_Element. Otherwise, it returns a cursor designating the first equal element
+encountered.>
-@xcode<@b<procedure> Previous (Position : @b<in out> Cursor);>
+@xcode<@b<function> Contains (Container : List;
+ Item : Element_Type) @b<return> Boolean;>
-@xindent<Equivalent to Position := Previous (Position).>
+@xindent<Equivalent to Find (Container, Item) /= No_Element.>
@xcode<@b<function> Has_Element (Position : Cursor) @b<return> Boolean;>
@@ -7833,6 +8179,38 @@
traversed in reverse order, starting with the last node and moving the cursor
as per the Previous function.>
+The actual function for the generic formal function "<" of Generic_Sorting is
+expected to return the same value each time it is called with a particular pair
+of element values. It should define a strict ordering relationship, that is, be
+irreflexive, asymmetric, and transitive; if should not modify Container. If the
+actual for "<" behaves in some other manner, the behavior of the subprograms of
+Generic_Sorting are unspecified. How many times the subprograms of
+Generic_Sorting call "<" is unspecified.
+
+@xcode<@b<function> Is_Sorted (Container : List) @b<return> Boolean;>
+
+@xindent<Returns True if the elements are sorted smallest first as determined by the
+generic formal "<" operator; otherwise, Is_Sorted returns False.
+Any exception raised during evaluation of "<" is propagated.>
+
+@xcode<@b<procedure> Sort (Container : @b<in out> List);>
+
+@xindent<Reorders the nodes of Container such that the elements are
+sorted smallest first as determined by the generic formal "<" operator
+provided. The sort is stable. Any exception raised during evaluation of
+"<" is propagated.>
+
+@xcode<@b<procedure> Merge (Target : @b<in out> List;
+ Source : @b<in out> List);>
+
+@xindent<Merge removes elements from Source and inserts them into Target;
+afterwards, Target contains the union of the elements that were initially
+in Source and Target; Source is left empty.
+If Target and Source are initially sorted smallest first, then Target is
+ordered smallest first as determined by the generic formal "<" operator;
+otherwise, the order of elements in Target is unspecified.
+Any exception raised during evaluation of "<" is propagated.>
+
@i<@s8<Bounded Errors>>
Calling Merge in an instance of Generic_Sorting with either Source or Target
@@ -7858,16 +8236,20 @@
No storage associated with a doubly-linked List object shall be lost
upon assignment or scope exit.
+The execution of an @fa<assignment_statement> for a list shall have the
+effect of copying the elements from the source list object to the target
+list object.
+
@i<@s8<Implementation Advice>>
Containers.Doubly_Linked_Lists should be implemented similarly to a linked
list. In particular, if @i<N> is the length of a list, then the worst-case time
complexity of Element, Insert with Count=1, and Delete with Count=1 should be
-O(log @i<N>).
+@i<O>(log @i<N>).
The worst-case time complexity of a call on procedure Sort of an instantiation
-Containers.Doubly_Linked_Lists.Generic_Sorting should be O(@i<N>**2), and
-the average time complexity should be better than O(@i<N>**2).
+Containers.Doubly_Linked_Lists.Generic_Sorting should be @i<O>(@i<N>**2), and
+the average time complexity should be better than @i<O>(@i<N>**2).
Move should not copy elements, and should minimize copying of internal
data structures.
@@ -7897,6 +8279,14 @@
@i<@s8<Static Semantics>>
+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
+map values returns an unspecified value. The exact arguments and number of
+calls of this generic formal function by the function "=" on map values are
+unspecified.
+
The type Map is used to represent maps. The type Map needs finalization (see
7.6).
@@ -7914,9 +8304,9 @@
in the map exactly once until the last node is reached. The exact definition of
these terms is different for hashed maps and ordered maps.
-Some operations are assumed to work on a constant set of elements. For such
-an operation, a subprogram is said to @i<tamper with cursors> of a map object @i<M>
-if:
+Some operations are assumed to work on a constant set of elements. During
+execution of such an operation, a subprogram is said to @i<tamper with cursors>
+of a map object @i<M> if:
@xbullet<it inserts or deletes elements of @i<M>, that is, it calls the Insert,
Include, Clear, Delete, or Exclude procedures with @i<M> as a parameter; or>
@@ -7927,7 +8317,7 @@
@xbullet<it calls one of the operations defined to tamper with the cursors of @i<M>.>
-Some operations are assumed to not replace elements. For such an operation, a
+Some operations are assumed to not replace elements. During the execution of such an operation, a
subprogram is said to @i<tamper with elements> of a map object @i<M> if:
@xbullet<it tampers with cursors of @i<M>; or>
@@ -7943,6 +8333,12 @@
Cursor is not otherwise initialized, it is initialized to the same
value as No_Element.
+The predefined "=" operator for type Cursor should return True if both cursors
+or No_Element, or designate the same element in the same container.
+
+Execution of the default implementation of the Input, Output, Read, or Write
+attribute of type Cursor raises Program_Error.
+
@xcode<@b<function> "=" (Left, Right : Map) @b<return> Boolean;>
@xindent<If Left and Right denote the same map object, then the function returns True. If
@@ -7981,6 +8377,15 @@
@xindent<If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
Element returns the element component of the node designated by Position.>
+@xcode<@b<procedure> Replace_Element (Container : @b<in out> Map;
+ Position : @b<in> Cursor;
+ New_Item : @b<in> Element_Type);>
+
+@xindent<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 Replace_Element assigns New_Item to the element of the
+node designated by Position.>
+
@xcode<@b<procedure> Query_Element
(Position : @b<in> Cursor;
Process : @b<not null access procedure> (Key : @b<in> Key_Type;
@@ -7989,30 +8394,25 @@
@xindent<If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
Query_Element calls Process.@b<all> with the key and element from the node
designated by Position as the arguments. Program_Error is propagated if
-Process.@b<all> tampers with the elements of Container. Any exceptions raised by
-Process.@b<all> are propagated.>
+Process.@b<all> tampers with the elements of Container. Any exception raised by
+Process.@b<all> is propagated.>
@xcode<@b<procedure> Update_Element
- (Position : @b<in> Cursor;
- Process : @b<not null access procedure> (Key : @b<in> Key_Type;
- Element : @b<in out> Element_Type));>
+ (Container : @b<in out> Map;
+ Position : @b<in> Cursor;
+ Process : @b<not null access procedure> (Key : @b<in> Key_Type;
+ Element : @b<in out> Element_Type));>
-@xindent<If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
-Update_Element calls Process.@b<all> with the key and element from the node
-designated by Position as the arguments. Program_Error is propagated if
-Process.@b<all> tampers with the elements of Container. Any exceptions raised
-by Process.@b<all> are propagated.>
+@xindent<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 calls Process.@b<all> with the key and
+element from the node designated by Position as the arguments. Program_Error is
+propagated if Process.@b<all> tampers with the elements of Container. Any
+exception raised by Process.@b<all> is propagated.>
-@xindent<If Element_Type is unconstrained and definite, then the Element parameter
+@xindent<If Element_Type is unconstrained and definite, then the actual Element parameter
of Process.@b<all> shall be unconstrained.>
-@xcode<@b<procedure> Replace_Element (Position : @b<in> Cursor;
- By : @b<in> Element_Type);>
-
-@xindent<If Position equals No_Element, then Constraint_Error is propagated.
-Otherwise Replace_Element assigns By to the element of the node designated by
-Position.>
-
@xcode<@b<procedure> Move (Target : @b<in out> Map;
Source : @b<in out> Map);>
@@ -8040,9 +8440,7 @@
Inserted : @b<out> Boolean);>
@xindent<Insert inserts Key into Container as per the five-parameter Insert, with the
-difference that an element initialized with any implicit initial values for any
-part (as for an @fa<object_declaration> with no initialization expression @emdash
-see 3.3.1) is inserted.>
+difference that an element initialized by default (see 3.3.1) is inserted.>
@xcode<@b<procedure> Insert (Container : @b<in out> Map;
Key : @b<in> Key_Type;
@@ -8069,6 +8467,12 @@
If a match is found, Replace assigns Key and New_Item to the matching node;
otherwise, Constraint_Error is propagated.>
+@xcode<@b<procedure> Exclude (Container : @b<in out> Map;
+ Key : @b<in> Key_Type);>
+
+@xindent<Exclude checks if a node with a key equivalent to Key is present in Container.
+If a match is found, Exclude removes the node from the map.>
+
@xcode<@b<procedure> Delete (Container : @b<in out> Map;
Key : @b<in> Key_Type);>
@@ -8084,18 +8488,21 @@
Otherwise, Delete removes the node designated by Position from the map.
Position is set to No_Element on return.>
-@xcode<@b<procedure> Exclude (Container : @b<in out> Map;
- Key : @b<in> Key_Type);>
+@xcode<@b<function> First (Container : Map) @b<return> Cursor;>
-@xindent<Exclude checks if a node with a key equivalent to Key is present in Container.
-If a match is found, Exclude removes the node from the map and then
-deallocates the node.>
+@xindent<If Length (Container) = 0, then First returns No_Element. Otherwise,
+First returns a cursor that designates the first node in Container.>
-@xcode<@b<function> Contains (Container : Map;
- Key : Key_Type) @b<return> Boolean;>
+@xcode<@b<function> Next (Position : Cursor) @b<return> Cursor;>
-@xindent<Equivalent to Find (Container, Key) /= No_Element.>
+@xindent<Returns a cursor that designates the successor of the node designated by
+Position. If Position designates the last node, then No_Element is returned. If
+Position equals No_Element, then No_Element is returned.>
+
+@xcode<@b<procedure> Next (Position : @b<in out> Cursor);>
+@xindent<Equivalent to Position := Next (Position).>
+
@xcode<@b<function> Find (Container : Map;
Key : Key_Type) @b<return> Cursor;>
@@ -8108,21 +8515,11 @@
Key : Key_Type) @b<return> Element_Type;>
@xindent<Equivalent to Element (Find (Container, Key)).>
-
-@xcode<@b<function> First (Container : Map) @b<return> Cursor;>
-
-@xindent<If Length (Container) = 0, then First returns No_Element. Otherwise,
-First returns a cursor that designates the first node in Container.>
-
-@xcode<@b<function> Next (Position : Cursor) @b<return> Cursor;>
-
-@xindent<Returns a cursor that designates the successor of the node designated by
-Position. If Position designates the last node, then No_Element is returned. If
-Position equals No_Element, then No_Element is returned.>
-@xcode<@b<procedure> Next (Position : @b<in out> Cursor);>
+@xcode<@b<function> Contains (Container : Map;
+ Key : Key_Type) @b<return> Boolean;>
-@xindent<Equivalent to Position := Next (Position).>
+@xindent<Equivalent to Find (Container, Key) /= No_Element.>
@xcode<@b<function> Has_Element (Position : Cursor) @b<return> Boolean;>
@@ -8135,7 +8532,7 @@
@xindent<Iterate calls Process.@b<all> with a cursor that designates each node
in Container, starting with the first node and moving the cursor according to
the successor relation. Program_Error is propagated if Process.@b<all> tampers
-with the elements of Container. Any exception raised by Process.@b<all> is
+with the cursors of Container. Any exception raised by Process.@b<all> is
propagated.>
@i<@s8<Erroneous Execution>>
@@ -8157,6 +8554,10 @@
No storage associated with a Map object shall be lost upon assignment or
scope exit.
+The execution of an @fa<assignment_statement> for a map shall have the
+effect of copying the elements from the source map object to the target
+map object.
+
@i<@s8<Implementation Advice>>
Move should not copy elements, and should minimize copying of internal
@@ -8197,6 +8598,11 @@
@b<function> "=" (Left, Right : Map) @b<return> Boolean;
+ @b<function> Capacity (Container : Map) @b<return> Count_Type;
+
+ @b<procedure> Reserve_Capacity (Container : @b<in out> Map;
+ Capacity : @b<in> Count_Type);
+
@b<function> Length (Container : Map) @b<return> Count_Type;
@b<function> Is_Empty (Container : Map) @b<return> Boolean;
@@ -8207,19 +8613,21 @@
@b<function> Element (Position : Cursor) @b<return> Element_Type;
+ @b<procedure> Replace_Element (Container : @b<in out> Map;
+ Position : @b<in> Cursor;
+ New_Item : @b<in> Element_Type);
+
@b<procedure> Query_Element
(Position : @b<in> Cursor;
Process : @b<not null access procedure> (Key : @b<in> Key_Type;
Element : @b<in> Element_Type));
@b<procedure> Update_Element
- (Position : @b<in> Cursor;
- Process : @b<not null access procedure> (Key : @b<in> Key_Type;
+ (Container : @b<in out> Map;
+ Position : @b<in> Cursor;
+ Process : @b<not null access procedure> (Key : @b<in> Key_Type;
Element : @b<in out> Element_Type));
- @b<procedure> Replace_Element (Position : @b<in> Cursor;
- By : @b<in> Element_Type);
-
@b<procedure> Move (Target : @b<in out> Map;
Source : @b<in out> Map);
@@ -8246,17 +8654,21 @@
Key : @b<in> Key_Type;
New_Item : @b<in> Element_Type);
+ @b<procedure> Exclude (Container : @b<in out> Map;
+ Key : @b<in> Key_Type);
+
@b<procedure> Delete (Container : @b<in out> Map;
Key : @b<in> Key_Type);
@b<procedure> Delete (Container : @b<in out> Map;
Position : @b<in out> Cursor);
- @b<procedure> Exclude (Container : @b<in out> Map;
- Key : @b<in> Key_Type);
+ @b<function> First (Container : Map)
+ @b<return> Cursor;
- @b<function> Contains (Container : Map;
- Key : Key_Type) @b<return> Boolean;
+ @b<function> Next (Position : Cursor) @b<return> Cursor;
+
+ @b<procedure> Next (Position : @b<in out> Cursor);
@b<function> Find (Container : Map;
Key : Key_Type)
@@ -8265,13 +8677,9 @@
@b<function> Element (Container : Map;
Key : Key_Type)
@b<return> Element_Type;
-
- @b<function> First (Container : Map)
- @b<return> Cursor;
-
- @b<function> Next (Position : Cursor) @b<return> Cursor;
- @b<procedure> Next (Position : @b<in out> Cursor);
+ @b<function> Contains (Container : Map;
+ Key : Key_Type) @b<return> Boolean;
@b<function> Has_Element (Position : Cursor) @b<return> Boolean;
@@ -8290,11 +8698,6 @@
(Container : @b<in> Map;
Process : @b<not null access procedure> (Position : @b<in> Cursor));
- @b<function> Capacity (Container : Map) @b<return> Count_Type;
-
- @b<procedure> Reserve_Capacity (Container : @b<in out> Map;
- Capacity : @b<in> Count_Type);
-
@b<private>
... -- @ft<@i<not specified by the language>>
@@ -8309,18 +8712,20 @@
Two keys @i<K1> and @i<K2> are defined to be @i<equivalent> if
Equivalent_Keys (@i<K1>, @i<K2>) returns True.
-Function Hash is expected to return the same value each time it is called with a
-particular key value. For any two equivalent key values, Hash is expected to
-return the same value. If Hash behaves in some other manner, the behavior of
+The actual function for the generic formal function Hash is expected to return the same
+value each time it is called with a particular key value. For any two
+equivalent key values, the actual for Hash is expected to return the same
+value. If the actual for Hash behaves in some other manner, the behavior of
this package is unspecified. Which subprograms of this package call Hash, and
how many times they call it, is unspecified.
-Function Equivalent_Keys is expected to return the same value each time it is
-called with a particular pair of key values. For any two keys @i<K1> and @i<K2>, the
-boolean values Equivalent_Keys (@i<K1>, @i<K2>) and Equivalent_Key (@i<K2>, @i<K1>)
-are expected to be equal. If Equivalent_Keys behaves in some other manner, the
-behavior of this package is unspecified. Which subprograms of this package call
-Equivalent_Keys, and how many times they call it, is unspecified.
+The actual function for the generic formal function Equivalent_Keys on Key_Type values
+is expected to return the same value each time it is called with a particular
+pair of key values. It must define an equivalence relationship, that is, be
+reflexive, symmetric, and transitive. If the actual for Equivalent_Keys behaves
+in some other manner, the behavior of this package is unspecified. Which
+subprograms of this package call Equivalent_Keys, and how many times they call
+it, is unspecified.
If the value of a key stored in a node of a map is changed other than by an
operation in this package such that at least one of Hash or Equivalent_Keys
@@ -8330,6 +8735,23 @@
successor of a given node, are unspecified, other than the general semantics
described in A.18.4.
+@xcode<@b<function> Capacity (Container : Map) @b<return> Count_Type;>
+
+@xindent<Returns the capacity of Container.>
+
+@xcode<@b<procedure> Reserve_Capacity (Container : @b<in out> Map;
+ Capacity : @b<in> Count_Type);>
+
+@xindent<Reserve_Capacity allocates a new hash table such that the length of the
+resulting map can become at least the value Capacity without requiring an
+additional call to Reserve_Capacity, and is large enough to hold the current
+length of Container. Reserve_Capacity then rehashes the nodes in Container onto
+the new hash table. It replaces the old hash table with the new hash table, and
+then deallocates the old hash table. Any exception raised during allocation is
+propagated and Container is not modified.>
+
+@xindent<Reserve_Capacity tampers with the cursors of Container.>
+
@xcode<@b<procedure> Clear (Container : @b<in out> Map);>
@xindent<In addition to the semantics described in A.18.4, Clear does not
@@ -8360,30 +8782,13 @@
@xindent<Equivalent to Equivalent_Keys (Left, Key (Right)).>
-@xcode<@b<function> Capacity (Container : Map) @b<return> Count_Type;>
-
-@xindent<Returns the capacity of Container.>
-
-@xcode<@b<procedure> Reserve_Capacity (Container : @b<in out> Map;
- Capacity : @b<in> Count_Type);>
-
-@xindent<Reserve_Capacity allocates a new hash table such that the length of the
-resulting map can become at least the value Capacity without requiring an
-additional call to Reserve_Capacity, and is large enough to hold the current
-length of Container. Reserve_Capacity then rehashes the nodes in Container onto
-the new hash table. It replaces the old hash table with the new hash table, and
-then deallocates the old hash table. Any exception raised during allocation is
-propagated and Container is not modified.>
-
-@xindent<Reserve_Capacity tampers with the cursors of Container.>
-
@i<@s8<Implementation Advice>>
If @i<N> is the length of a map, the average time complexity of the subprograms
Element, Insert, Include, Replace, Delete, Exclude and Find that take a key
-parameter should be O(log @i<N>). The average time complexity of the
-subprograms that take a cursor parameter should be O(1). The average time
-complexity of Reserve_Capacity should be O(@i<N>).
+parameter should be @i<O>(log @i<N>). The average time complexity of the
+subprograms that take a cursor parameter should be @i<O>(1). The average time
+complexity of Reserve_Capacity should be @i<O>(@i<N>).
!corrigendum A.18.6
@@ -8402,6 +8807,8 @@
@b<package> Ada.Containers.Ordered_Maps @b<is>
@b<pragma> Preelaborate (Ordered_Maps);
+ @b<function> Equivalent_Keys (Left, Right : Key_Type) @b<return> Boolean;
+
@b<type> Map @b<is tagged private>;
@b<pragma> Preelaborable_Initialization(Map);
@@ -8424,19 +8831,21 @@
@b<function> Element (Position : Cursor) @b<return> Element_Type;
+ @b<procedure> Replace_Element (Container : @b<in out> Map;
+ Position : @b<in> Cursor;
+ New_Item : @b<in> Element_Type);
+
@b<procedure> Query_Element
(Position : @b<in> Cursor;
Process : @b<not null access procedure> (Key : @b<in> Key_Type;
Element : @b<in> Element_Type));
@b<procedure> Update_Element
- (Position : @b<in> Cursor;
- Process : @b<not null access procedure> (Key : @b<in> Key_Type;
+ (Container : @b<in out> Map;
+ Position : @b<in> Cursor;
+ Process : @b<not null access procedure> (Key : @b<in> Key_Type;
Element : @b<in out> Element_Type));
- @b<procedure> Replace_Element (Position : @b<in> Cursor;
- By : @b<in> Element_Type);
-
@b<procedure> Move (Target : @b<in out> Map;
Source : @b<in out> Map);
@@ -8463,6 +8872,9 @@
Key : @b<in> Key_Type;
New_Item : @b<in> Element_Type);
+ @b<procedure> Exclude (Container : @b<in out> Map;
+ Key : @b<in> Key_Type);
+
@b<procedure> Delete (Container : @b<in out> Map;
Key : @b<in> Key_Type);
@@ -8473,36 +8885,18 @@
@b<procedure> Delete_Last (Container : @b<in out> Map);
- @b<procedure> Exclude (Container : @b<in out> Map;
- Key : @b<in> Key_Type);
-
- @b<function> Contains (Container : Map;
- Key : Key_Type) @b<return> Boolean;
-
- @b<function> Find (Container : Map;
- Key : Key_Type) @b<return> Cursor;
-
- @b<function> Element (Container : Map;
- Key : Key_Type) @b<return> Element_Type;
-
- @b<function> Floor (Container : Map;
- Key : Key_Type) @b<return> Cursor;
-
- @b<function> Ceiling (Container : Map;
- Key : Key_Type) @b<return> Cursor;
-
@b<function> First (Container : Map) @b<return> Cursor;
- @b<function> First_Key (Container : Map) @b<return> Key_Type;
-
@b<function> First_Element (Container : Map) @b<return> Element_Type;
- @b<function> Last (Container : Map) @b<return> Cursor;
+ @b<function> First_Key (Container : Map) @b<return> Key_Type;
- @b<function> Last_Key (Container : Map) @b<return> Key_Type;
+ @b<function> Last (Container : Map) @b<return> Cursor;
@b<function> Last_Element (Container : Map) @b<return> Element_Type;
+ @b<function> Last_Key (Container : Map) @b<return> Key_Type;
+
@b<function> Next (Position : Cursor) @b<return> Cursor;
@b<procedure> Next (Position : @b<in out> Cursor);
@@ -8511,6 +8905,21 @@
@b<procedure> Previous (Position : @b<in out> Cursor);
+ @b<function> Find (Container : Map;
+ Key : Key_Type) @b<return> Cursor;
+
+ @b<function> Element (Container : Map;
+ Key : Key_Type) @b<return> Element_Type;
+
+ @b<function> Floor (Container : Map;
+ Key : Key_Type) @b<return> Cursor;
+
+ @b<function> Ceiling (Container : Map;
+ Key : Key_Type) @b<return> Cursor;
+
+ @b<function> Contains (Container : Map;
+ Key : Key_Type) @b<return> Boolean;
+
@b<function> Has_Element (Position : Cursor) @b<return> Boolean;
@b<function> "<" (Left, Right : Cursor) @b<return> Boolean;
@@ -8541,16 +8950,15 @@
Two keys @i<K1> and @i<K2> are @i<equivalent> if both @i<K1> < @i<K2> and
@i<K2> < @i<K1> return False, using the generic formal "<" operator for
-keys.
+keys. Function Equivalent_Keys returns True if Left and Right are equivalent,
+and False otherwise.
-Functions "<" and "=" on Key_Type values are expected to return the same result
-value each time they are called with a particular pair of key values. If @i<A> = @i<B>
-returns True, then @i<B> = @i<A> is expected to also return True. If @i<A> < @i<B>
-returns True, then @i<B> < @i<A> is expected to return False. For any two
-equivalent elements, "=" is expected to return True. If "<" or "=" behaves in
-some other manner, the behavior of this package is unspecified. Which
-subprograms of this package call "<" and "=", and how many times these
-functions are called, is unspecified.
+The actual function for the generic formal function "<" on Key_Type values is expected
+to return the same value each time it is called with a particular pair of key
+values. It must define a strict ordering relationship, 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.
If the value of a key stored in a map is changed other than by an operation in
this package such that at least one of "<" or "=" give different results, the
@@ -8575,42 +8983,28 @@
@xindent<If Container is empty, Delete_Last has no effect. Otherwise the node designated
by Last (Container) is removed from Container. Delete_Last tampers with
the cursors of Container.>
-
-@xcode<@b<function> Floor (Container : Map;
- Key : Key_Type) @b<return> Cursor;>
-
-@xindent<Floor searches for the last node whose key is not greater than Key. If such a
-node is found, a cursor that designates it is returned. Otherwise No_Element is
-returned.>
-@xcode<@b<function> Ceiling (Container : Map;
- Key : Key_Type) @b<return> Cursor;>
+@xcode<@b<function> First_Element (Container : Map) @b<return> Element_Type;>
-@xindent<Ceiling searches for the first node whose key is not less than Key,
-using the generic formal "<" operator for keys. If such a node is found,
-a cursor that designates it is returned. Otherwise No_Element is returned.>
+@xindent<Equivalent to Element (First (Container)).>
@xcode<@b<function> First_Key (Container : Map) @b<return> Key_Type;>
@xindent<Equivalent to Key (First (Container)).>
-@xcode<@b<function> First_Element (Container : Map) @b<return> Element_Type;>
-
-@xindent<Equivalent to Element (First (Container)).>
-
@xcode<@b<function> Last (Container : Map) @b<return> Cursor;>
@xindent<Returns a cursor that designates the last node in Container. If Container is
empty, returns No_Element.>
-@xcode<@b<function> Last_Key (Container : Map) @b<return> Key_Type;>
-
-@xindent<Equivalent to Key (Last (Container)).>
-
@xcode<@b<function> Last_Element (Container : Map) @b<return> Element_Type;>
@xindent<Equivalent to Element (Last (Container)).>
+@xcode<@b<function> Last_Key (Container : Map) @b<return> Key_Type;>
+
+@xindent<Equivalent to Key (Last (Container)).>
+
@xcode<@b<function> Previous (Position : Cursor) @b<return> Cursor;>
@xindent<If Position equals No_Element, then Previous returns No_Element. Otherwise
@@ -8619,8 +9013,22 @@
returns No_Element.>
@xcode<@b<procedure> Previous (Position : @b<in out> Cursor);>
+
+@xindent<Equivalent to Position := Previous (Position).>
+
+@xcode<@b<function> Floor (Container : Map;
+ Key : Key_Type) @b<return> Cursor;>
+
+@xindent<Floor searches for the last node whose key is not greater than Key,
+using the generic formal "<" operator for keys. If such a node is found, a
+cursor that designates it is returned. Otherwise No_Element is returned.>
+
+@xcode<@b<function> Ceiling (Container : Map;
+ Key : Key_Type) @b<return> Cursor;>
-@xindent<Equivalent to Position := Previous (Position).>
+@xindent<Ceiling searches for the first node whose key is not less than Key,
+using the generic formal "<" operator for keys. If such a node is found,
+a cursor that designates it is returned. Otherwise No_Element is returned.>
@xcode<@b<function> "<" (Left, Right : Cursor) @b<return> Boolean;>
@@ -8658,8 +9066,8 @@
If @i<N> is the length of a map, then the worst-case time complexity of the
Element, Insert, Include, Replace, Delete, Exclude and Find operations that
-take a key parameter should be O((log @i<N>)**2) or better. The worst-case
-time complexity of the subprograms that take a cursor parameter should be O(1).
+take a key parameter should be @i<O>((log @i<N>)**2) or better. The worst-case
+time complexity of the subprograms that take a cursor parameter should be @i<O>(1).
!corrigendum A.18.7
@@ -8678,6 +9086,14 @@
@i<@s8<Static Semantics>>
+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.
+
The type Set is used to represent sets. The type Set needs finalization (see
7.6).
@@ -8690,13 +9106,13 @@
the @i<last element> (which may be the same). Each element except for the last
element has a @i<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 map exactly once until 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.
-Some operations are assumed to work on a constant set of elements. For such
-an operation, a subprogram is said to @i<tamper with cursors> of a set object
-@i<S> if:
+Some operations are assumed to work on a constant set of elements. During
+execution of such an operation, a subprogram is said to @i<tamper with cursors>
+of a set object @i<S> if:
@xbullet<it inserts or deletes elements of @i<S>, that is, it calls the Insert,
Include, Clear, Delete, Exclude, or Replace_Element procedures with @i<S> as
@@ -8708,15 +9124,11 @@
@xbullet<it calls one of the operations defined to tamper with cursors of @i<S>.>
-Some operations are assumed to not replace elements. For such an operation, a
+Some operations are assumed to not replace elements. During the execution of such an operation, a
subprogram is said to @i<tamper with elements> of a set object @i<S> if:
-@xbullet<it tampers with cursors of @i<S>; or>
+@xbullet<it tampers with cursors of @i<S>.>
-@xbullet<it replaces one or more elements of @i<S>, that is, it calls the
-Replace or Replace_Element procedures with @i<S> as a
-parameter.>
-
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.
@@ -8725,6 +9137,12 @@
Cursor is not otherwise initialized, it is initialized to the same
value as No_Element.
+The predefined "=" operator for type Cursor should return True if both cursors
+or No_Element, or designate the same element in the same container.
+
+Execution of the default implementation of the Input, Output, Read, or Write
+attribute of type Cursor raises Program_Error.
+
@xcode<@b<function> "=" (Left, Right : Set) @b<return> Boolean;>
@xindent<If Left and Right denote the same set object, then the function returns True.
@@ -8762,6 +9180,17 @@
@xindent<If Position equals No_Element, then Constraint_Error is propagated.
Otherwise, Element returns the element designated by Position.>
+@xcode<@b<procedure> Replace_Element (Container : @b<in out> Set;
+ Position : @b<in> Cursor;
+ New_Item : @b<in> Element_Type);>
+
+@xindent<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.>
+
@xcode<@b<procedure> Query_Element
(Position : @b<in> Cursor;
Process : @b<not null access procedure> (Element : @b<in> Element_Type));>
@@ -8769,20 +9198,8 @@
@xindent<If Position equals No_Element, then Constraint_Error is propagated.
Otherwise, Query_Element calls Process.@b<all> with the element designated by
Position as the argument. Program_Error is propagated if Process.@b<all>
-tampers with the elements of Container. Any exceptions raised by
-Process.@b<all> are propagated.>
-
-@xcode<@b<procedure> Replace_Element (Container : @b<in> Set;
- Position : @b<in> Cursor;
- By : @b<in> Element_Type);>
-
-@xindent<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, the element designated by Position is tested for
-equivalence to By; if they are found to be equivalent, Replace_Element assigns
-By to the element designated by Position. Otherwise, the element designated by
-Position is removed from the container, then By is inserted into the container.
-If the insertion fails, Program_Error is propagated.>
+tampers with the elements of Container. Any exception raised by
+Process.@b<all> is propagated.>
@xcode<@b<procedure> Move (Target : @b<in out> Set;
Source : @b<in out> Set);>
@@ -8826,6 +9243,12 @@
set. If a match is found, that element is replaced with New_Item; otherwise,
Constraint_Error is propagated.>
+@xcode<@b<procedure> Exclude (Container : @b<in out> Set;
+ Item : @b<in> Element_Type);>
+
+@xindent<Exclude checks if an element equivalent to Item is present in
+Container. If a match is found, Exclude removes the element from the set.>
+
@xcode<@b<procedure> Delete (Container : @b<in out> Set;
Item : @b<in> Element_Type);>
@@ -8835,60 +9258,11 @@
@xcode<@b<procedure> Delete (Container : @b<in out> Set;
Position : @b<in out> Cursor);>
-
-@xindent<If Position equals No_Element, Delete has no effect. If Position does
-not designate an element in Container, then Program_Error is propagated.
-Otherwise, Delete removes the node designated by Position from the set.
-Position is set to No_Element on return.>
-
-@xcode<@b<procedure> Exclude (Container : @b<in out> Set;
- Item : @b<in> Element_Type);>
-
-@xindent<Exclude checks if an element equivalent to Item is present in
-Container. If a match is found, Exclude removes the element from the set.>
-
-@xcode<@b<function> Contains (Container : Set;
- Item : Element_Type) @b<return> Boolean;>
-
-@xindent<Equivalent to Find (Container, Item) /= No_Element.>
-
-@xcode<@b<function> Find (Container : Set;
- Item : Element_Type) @b<return> Cursor;>
-
-@xindent<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.>
-
-@xcode<@b<function> First (Container : Set) @b<return> Cursor;>
-
-@xindent<If Length (Container) = 0, then First returns No_Element. Otherwise, First
-returns a cursor that designates the first node in Container.>
-
-@xcode<@b<function> Next (Position : Cursor) @b<return> Cursor;>
-
-@xindent<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.>
-
-@xcode<@b<procedure> Next (Position : @b<in out> Cursor);>
-
-@xindent<Equivalent to Position := Next (Position).>
-
-@xcode<@b<function> Has_Element (Position : Cursor) @b<return> Boolean;>
-
-@xindent<Returns True if Position designates an element, and returns False otherwise.>
-
-@xcode<@b<procedure> Iterate
- (Container : @b<in> Set;
- Process : @b<not null access procedure> (Position : @b<in> Cursor));>
-@xindent<Iterate calls Process.@b<all> with a cursor that designates each
-element in Container, starting with the first node and moving the cursor
-according to the successor relation. Program_Error is propagated if
-Process.@b<all> tampers with the elements of Container. Any exception raised by
-Process.@b<all> is propagated.>
+@xindent<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.>
@xcode<@b<procedure> Union (Target : @b<in out> Set;
Source : @b<in> Set);>
@@ -8949,6 +9323,49 @@
@xindent<If an element of Subset is not equivalent to some element of Of_Set,
then Is_Subset returns False. Otherwise it returns True.>
+@xcode<@b<function> First (Container : Set) @b<return> Cursor;>
+
+@xindent<If Length (Container) = 0, then First returns No_Element. Otherwise, First
+returns a cursor that designates the first element in Container.>
+
+@xcode<@b<function> Next (Position : Cursor) @b<return> Cursor;>
+
+@xindent<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.>
+
+@xcode<@b<procedure> Next (Position : @b<in out> Cursor);>
+
+@xindent<Equivalent to Position := Next (Position).>
+
+@xcode<@b<function> Find (Container : Set;
+ Item : Element_Type) @b<return> Cursor;>
+
+@xindent<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.>
+
+@xcode<@b<function> Contains (Container : Set;
+ Item : Element_Type) @b<return> Boolean;>
+
+@xindent<Equivalent to Find (Container, Item) /= No_Element.>
+
+@xcode<@b<function> Has_Element (Position : Cursor) @b<return> Boolean;>
+
+@xindent<Returns True if Position designates an element, and returns False otherwise.>
+
+@xcode<@b<procedure> Iterate
+ (Container : @b<in> Set;
+ Process : @b<not null access procedure> (Position : @b<in> Cursor));>
+
+@xindent<Iterate calls Process.@b<all> with a cursor that designates each
+element in Container, starting with the first element and moving the cursor
+according to the successor relation. Program_Error is propagated if
+Process.@b<all> tampers with the cursors of Container. Any exception raised by
+Process.@b<all> is propagated.>
+
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
@@ -8982,7 +9399,7 @@
Process : @b<not null access procedure>
(Element : @b<in out> Element_Type));>
-@xindent<If Position equals No_Element, then Constraint_Error is propagated. If
+@xindent<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 @i<K> of the element designated by Position. Update_Element_Preserving_Key
@@ -9015,6 +9432,10 @@
No storage associated with a Set object shall be lost upon assignment or scope
exit.
+The execution of an @fa<assignment_statement> for a set shall have the
+effect of copying the elements from the source set object to the target
+set object.
+
@i<@s8<Implementation Advice>>
Move should not copy elements, and should minimize copying of internal
@@ -9055,6 +9476,11 @@
@b<function> Equivalent_Sets (Left, Right : Set) @b<return> Boolean;
+ @b<function> Capacity (Container : Set) @b<return> Count_Type;
+
+ @b<procedure> Reserve_Capacity (Container : @b<in out> Set;
+ Capacity : @b<in> Count_Type);
+
@b<function> Length (Container : Set) @b<return> Count_Type;
@b<function> Is_Empty (Container : Set) @b<return> Boolean;
@@ -9063,14 +9489,14 @@
@b<function> Element (Position : Cursor) @b<return> Element_Type;
+ @b<procedure> Replace_Element (Container : @b<in out> Set;
+ Position : @b<in> Cursor;
+ New_Item : @b<in> Element_Type);
+
@b<procedure> Query_Element
(Position : @b<in> Cursor;
Process : @b<not null access procedure> (Element : @b<in> Element_Type));
- @b<procedure> Replace_Element (Container : @b<in> Set;
- Position : @b<in> Cursor;
- By : @b<in> Element_Type);
-
@b<procedure> Move (Target : @b<in out> Set;
Source : @b<in out> Set);
@@ -9088,44 +9514,15 @@
@b<procedure> Replace (Container : @b<in out> Set;
New_Item : @b<in> Element_Type);
+ @b<procedure> Exclude (Container : @b<in out> Set;
+ Item : @b<in> Element_Type);
+
@b<procedure> Delete (Container : @b<in out> Set;
Item : @b<in> Element_Type);
@b<procedure> Delete (Container : @b<in out> Set;
Position : @b<in out> Cursor);
- @b<procedure> Exclude (Container : @b<in out> Set;
- Item : @b<in> Element_Type);
-
- @b<function> Contains (Container : Set;
- Item : Element_Type) @b<return> Boolean;
-
- @b<function> Find (Container : Set;
- Item : Element_Type) @b<return> Cursor;
-
- @b<function> First (Container : Set) @b<return> Cursor;
-
- @b<function> Next (Position : Cursor) @b<return> Cursor;
-
- @b<procedure> Next (Position : @b<in out> Cursor);
-
- @b<function> Has_Element (Position : Cursor) @b<return> Boolean;
-
- @b<function> Equivalent_Elements (Left, Right : Cursor)
- @b<return> Boolean;
-
- @b<function> Equivalent_Elements (Left : Cursor;
- Right : Element_Type)
- @b<return> Boolean;
-
- @b<function> Equivalent_Elements (Left : Element_Type;
- Right : Cursor)
- @b<return> Boolean;
-
- @b<procedure> Iterate
- (Container : @b<in> Set;
- Process : @b<not null access procedure> (Position : @b<in> Cursor));
-
@b<procedure> Union (Target : @b<in out> Set;
Source : @b<in> Set);
@@ -9160,27 +9557,42 @@
@b<function> Is_Subset (Subset : Set;
Of_Set : Set) @b<return> Boolean;
- @b<function> Capacity (Container : Set) @b<return> Count_Type;
+ @b<function> First (Container : Set) @b<return> Cursor;
- @b<procedure> Reserve_Capacity (Container : @b<in out> Set;
- Capacity : @b<in> Count_Type);
+ @b<function> Next (Position : Cursor) @b<return> Cursor;
+
+ @b<procedure> Next (Position : @b<in out> Cursor);
+
+ @b<function> Find (Container : Set;
+ Item : Element_Type) @b<return> Cursor;
+
+ @b<function> Contains (Container : Set;
+ Item : Element_Type) @b<return> Boolean;
+
+ @b<function> Has_Element (Position : Cursor) @b<return> Boolean;
+
+ @b<function> Equivalent_Elements (Left, Right : Cursor)
+ @b<return> Boolean;
+
+ @b<function> Equivalent_Elements (Left : Cursor;
+ Right : Element_Type)
+ @b<return> Boolean;
+ @b<function> Equivalent_Elements (Left : Element_Type;
+ Right : Cursor)
+ @b<return> Boolean;
+
+ @b<procedure> Iterate
+ (Container : @b<in> Set;
+ Process : @b<not null access procedure> (Position : @b<in> Cursor));
+
@b<generic>
- @b<type> Key_Type (<@>) @b<is limited private>;
- @b<with function> Key (Element : @b<in> Element_Type) @b<return> Key_Type;
+ @b<type> Key_Type (<@>) @b<is private>;
+ @b<with function> Key (Element : Element_Type) @b<return> Key_Type;
@b<with function> Hash (Key : Key_Type) @b<return> Hash_Type;
- @b<with function> Equivalent_Keys (Left : Key_Type; Right : Element_Type)
- @b<return> Boolean;
+ @b<with function> Equivalent_Keys (Left, Right : Key_Type) @b<return> Boolean;
@b<package> Generic_Keys @b<is>
- @b<function> Contains (Container : Set;
- Key : Key_Type)
- @b<return> Boolean;
-
- @b<function> Find (Container : Set;
- Key : Key_Type)
- @b<return> Cursor;
-
@b<function> Key (Position : Cursor) @b<return> Key_Type;
@b<function> Element (Container : Set;
@@ -9191,11 +9603,19 @@
Key : @b<in> Key_Type;
New_Item : @b<in> Element_Type);
+ @b<procedure> Exclude (Container : @b<in out> Set;
+ Key : @b<in> Key_Type);
+
@b<procedure> Delete (Container : @b<in out> Set;
Key : @b<in> Key_Type);
- @b<procedure> Exclude (Container : @b<in out> Set;
- Key : @b<in> Key_Type);
+ @b<function> Find (Container : Set;
+ Key : Key_Type)
+ @b<return> Cursor;
+
+ @b<function> Contains (Container : Set;
+ Key : Key_Type)
+ @b<return> Boolean;
@b<procedure> Update_Element_Preserving_Key
(Container : @b<in out> Set;
@@ -9203,14 +9623,6 @@
Process : @b<not null access procedure>
(Element : @b<in out> Element_Type));
- @b<function> Equivalent_Keys (Left : Cursor;
- Right : Key_Type)
- @b<return> Boolean;
-
- @b<function> Equivalent_Keys (Left : Key_Type;
- Right : Cursor)
- @b<return> Boolean;
-
@b<end> Generic_Keys;
@b<private>
@@ -9227,19 +9639,20 @@
Two elements @i<E1> and @i<E2> are defined to be @i<equivalent> if
Equivalent_Elements (@i<E1>, @i<E2>) returns True.
-Function Hash is expected to return the same value each time it is called with
-a particular element value. For any two equivalent elements, Hash is expected
-to return the same value. If Hash behaves in some other manner, the behavior of
+The actual function for the generic formal function Hash is expected to return
+the same value each time it is called with a particular element value. For any
+two equivalent elements, the actual for Hash is expected to return the same
+value. If the actual for Hash behaves in some other manner, the behavior of
this package is unspecified. Which subprograms of this package call Hash, and
how many times they call it, is unspecified.
-Function Equivalent_Elements is expected to return the same value each time
-it is called with a particular pair of element values. For any two elements @i<E1>
-and @i<E2>, the boolean values Equivalent_Elements (@i<E1>, @i<E2>) and
-Equivalent_Elements (@i<E2>, @i<E1>)
-are expected to be equal. If Equivalent_Elements behaves in some other manner,
-the behavior of this package is unspecified. Which subprograms of this package
-call Equivalent_Elements, and how many times they call it, is unspecified.
+The actual function for the generic formal function Equivalent_Elements is
+expected to return the same value each time it is called with a particular pair
+of Element values. It must define an equivalence relationship, that is, be
+reflexive, symmetric, and transitive. If the actual for Equivalent_Elements
+behaves in some other manner, the behavior of this package is unspecified.
+Which subprograms of this package call Equivalent_Elements, and how many times
+they call it, is unspecified.
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 Hash or Equivalent_Elements
@@ -9249,6 +9662,23 @@
element is the successor of a given element, are unspecified, other than the
general semantics described in A.18.7.
+@xcode<@b<function> Capacity (Container : Set) @b<return> Count_Type;>
+
+@xindent<Returns the capacity of Container.>
+
+@xcode<@b<procedure> Reserve_Capacity (Container : @b<in out> Set;
+ Capacity : @b<in> Count_Type);>
+
+@xindent<Reserve_Capacity allocates a new hash table such that the length of the
+resulting set can become at least the value Capacity without requiring an
+additional call to Reserve_Capacity, and is large enough to hold the current
+length of Container. Reserve_Capacity then rehashes the elements in Container
+onto the new hash table. It replaces the old hash table with the new hash
+table, and then deallocates the old hash table. Any exception raised during
+allocation is propagated and Container is not modified.>
+
+@xindent<Reserve_Capacity tampers with the cursors of Container.>
+
@xcode<@b<procedure> Clear (Container : @b<in out> Set);>
@xindent<In addition to the semantics described in A.18.7, Clear does not
@@ -9275,61 +9705,33 @@
@xcode<@b<function> Equivalent_Elements (Left : Cursor;
Right : Element_Type) @b<return> Boolean;>
-
-@xindent<Equivalent to Equivalent_Elements (Element (Left), Right).>
-
-@xcode<@b<function> Equivalent_Elements (Left : Element_Type;
- Right : Cursor) @b<return> Boolean;>
-
-@xindent<Equivalent to Equivalent_Elements (Left, Element (Right)).>
-
-@xcode<@b<function> Capacity (Container : Set) @b<return> Count_Type;>
-
-@xindent<Returns the capacity of Container.>
-
-@xcode<@b<procedure> Reserve_Capacity (Container : @b<in out> Set;
- Capacity : @b<in> Count_Type);>
-
-@xindent<Reserve_Capacity allocates a new hash table such that the length of the
-resulting set can become at least the value Capacity without requiring an
-additional call to Reserve_Capacity, and is large enough to hold the current
-length of Container. Reserve_Capacity then rehashes the elements in Container
-onto the new hash table. It replaces the old hash table with the new hash
-table, and then deallocates the old hash table. Any exception raised during
-allocation is propagated and Container is not modified.>
-
-@xindent<Reserve_Capacity tampers with the cursors of Container.>
-
-For any element @i<E>, the function Generic_Keys.Hash must be such that
-Hash (@i<E>) = Generic_Keys.Hash (Key (@i<E>)). If Key or Generic_Keys.Hash
-behave in some other manner, the behavior of Generic_Keys is unspecified. Which
-subprograms of Generic_Keys call Generic_Keys.Hash, and how many times they
-call it, is unspecified.
-
-For any two elements @i<E1> and @i<E2>, the boolean values
-Equivalent_Element (@i<E1>, @i<E2>), Equivalent_Keys (Key (@i<E1>), @i<E2>),
-and Equivalent_Keys (Key (@i<E2>), @i<E1>) are all expected to be equal. If Key
-or Equivalent behave in some other manner, the behavior of Generic_Keys is
-unspecified. Which subprograms of Generic_Keys call Equivalent, and how many
-times they call it, is unspecified.
-@xcode<@b<function> Equivalent_Keys (Left : Cursor;
- Right : Key_Type) @b<return> Boolean;>
+@xindent<Equivalent to Equivalent_Elements (Element (Left), Right).>
-@xindent<Equivalent to Equivalent_Keys (Key (Left), Right).>
+@xcode<@b<function> Equivalent_Elements (Left : Element_Type;
+ Right : Cursor) @b<return> Boolean;>
-@xcode<@b<function> Equivalent_Keys (Left : Key_Type;
- Right : Cursor) @b<return> Boolean;>
+@xindent<Equivalent to Equivalent_Elements (Left, Element (Right)).>
-@xindent<Equivalent to Equivalent_Keys (Left, Key (Right)).>
+For any element @i<E>, the actual for the generic formal function
+Generic_Keys.Hash must be such that Hash (@i<E>) = Generic_Keys.Hash (Key
+(@i<E>)). If the actuals for Key or Generic_Keys.Hash behave in some other manner, the behavior
+of Generic_Keys is unspecified. Which subprograms of Generic_Keys call
+Generic_Keys.Hash, and how many times they call it, is unspecified.
+
+For any two elements @i<E1> and @i<E2>, the boolean values Equivalent_Element
+(@i<E1>, @i<E2>) and Equivalent_Keys (Key (@i<E1>), Key (@i<E2>)) are
+expected to be equal. If the actuals for Key or Equivalent_Keys behave in some other manner,
+the behavior of Generic_Keys is unspecified. Which subprograms of Generic_Keys
+call Equivalent_Keys, and how many times they call it, is unspecified.
@i<@s8<Implementation Advice>>
If @i<N> is the length of a set, the average time complexity of the subprograms
Insert, Include, Replace, Delete, Exclude and Find that take an element
-parameter should be O(log @i<N>). The average time complexity of the
-subprograms that take a cursor parameter should be O(1). The average time
-complexity of Reserve_Capacity should be O(@i<N>).
+parameter should be @i<O>(log @i<N>). The average time complexity of the
+subprograms that take a cursor parameter should be @i<O>(1). The average time
+complexity of Reserve_Capacity should be @i<O>(@i<N>).
!corrigendum A.18.9
@@ -9347,6 +9749,8 @@
@b<package> Ada.Containers.Ordered_Sets @b<is>
@b<pragma> Preelaborate (Ordered_Sets);
+ @b<function> Equivalent_Elements (Left, Right : Element_Type) @b<return> Boolean;
+
@b<type> Set @b<is tagged private>;
@b<pragma> Preelaborable_Initialization(Set);
@@ -9369,14 +9773,14 @@
@b<function> Element (Position : Cursor) @b<return> Element_Type;
+ @b<procedure> Replace_Element (Container : @b<in out> Set;
+ Position : @b<in> Cursor;
+ New_Item : @b<in> Element_Type);
+
@b<procedure> Query_Element
(Position : @b<in> Cursor;
Process : @b<not null access procedure> (Element : @b<in> Element_Type));
- @b<procedure> Replace_Element (Container : @b<in> Set;
- Position : @b<in> Cursor;
- By : @b<in> Element_Type);
-
@b<procedure> Move (Target : @b<in out> Set;
Source : @b<in out> Set);
@@ -9394,13 +9798,13 @@
@b<procedure> Replace (Container : @b<in out> Set;
New_Item : @b<in> Element_Type);
- @b<procedure> Delete (Container : @b<in out> Set;
- Item : @b<in> Element_Type);
-
@b<procedure> Exclude (Container : @b<in out> Set;
Item : @b<in> Element_Type);
@b<procedure> Delete (Container : @b<in out> Set;
+ Item : @b<in> Element_Type);
+
+ @b<procedure> Delete (Container : @b<in out> Set;
Position : @b<in out> Cursor);
@b<procedure> Delete_First (Container : @b<in out> Set);
@@ -9441,21 +9845,6 @@
@b<function> Is_Subset (Subset : Set;
Of_Set : Set) @b<return> Boolean;
- @b<function> Contains (Container : Set;
- Item : Element_Type) @b<return> Boolean;
-
- @b<function> Find (Container : Set;
- Item : Element_Type)
- @b<return> Cursor;
-
- @b<function> Floor (Container : Set;
- Item : Element_Type)
- @b<return> Cursor;
-
- @b<function> Ceiling (Container : Set;
- Item : Element_Type)
- @b<return> Cursor;
-
@b<function> First (Container : Set) @b<return> Cursor;
@b<function> First_Element (Container : Set) @b<return> Element_Type;
@@ -9472,6 +9861,21 @@
@b<procedure> Previous (Position : @b<in out> Cursor);
+ @b<function> Find (Container : Set;
+ Item : Element_Type)
+ @b<return> Cursor;
+
+ @b<function> Floor (Container : Set;
+ Item : Element_Type)
+ @b<return> Cursor;
+
+ @b<function> Ceiling (Container : Set;
+ Item : Element_Type)
+ @b<return> Cursor;
+
+ @b<function> Contains (Container : Set;
+ Item : Element_Type) @b<return> Boolean;
+
@b<function> Has_Element (Position : Cursor) @b<return> Boolean;
@b<function> "<" (Left, Right : Cursor) @b<return> Boolean;
@@ -9499,28 +9903,14 @@
Process : @b<not null access procedure> (Position : @b<in> Cursor));
@b<generic>
- @b<type> Key_Type (<@>) @b<is limited private>;
+ @b<type> Key_Type (<@>) @b<is private>;
@b<with function> Key (Element : Element_Type) @b<return> Key_Type;
- @b<with function> "<" (Left : Key_Type; Right : Element_Type)
- @b<return> Boolean @b<is> <@>;
- @b<with function> "@>" (Left : Key_Type; Right : Element_Type)
+ @b<with function> "<" (Left, Right : Key_Type)
@b<return> Boolean @b<is> <@>;
@b<package> Generic_Keys @b<is>
- @b<function> Contains (Container : Set;
- Key : Key_Type) @b<return> Boolean;
-
- @b<function> Find (Container : Set;
- Key : Key_Type)
- @b<return> Cursor;
-
- @b<function> Floor (Container : Set;
- Item : Key_Type)
- @b<return> Cursor;
-
- @b<function> Ceiling (Container : Set;
- Item : Key_Type)
- @b<return> Cursor;
+ @b<function> Equivalent_Keys (Left, Right : Key_Type)
+ @b<return> Boolean;
@b<function> Key (Position : Cursor) @b<return> Key_Type;
@@ -9532,23 +9922,26 @@
Key : @b<in> Key_Type;
New_Item : @b<in> Element_Type);
- @b<procedure> Delete (Container : @b<in out> Set;
- Key : @b<in> Key_Type);
-
@b<procedure> Exclude (Container : @b<in out> Set;
Key : @b<in> Key_Type);
- @b<function> "<" (Left : Cursor; Right : Key_Type)
- @b<return> Boolean;
+ @b<procedure> Delete (Container : @b<in out> Set;
+ Key : @b<in> Key_Type);
- @b<function> "@>" (Left : Cursor; Right : Key_Type)
- @b<return> Boolean;
+ @b<function> Find (Container : Set;
+ Key : Key_Type)
+ @b<return> Cursor;
- @b<function> "<" (Left : Key_Type; Right : Cursor)
- @b<return> Boolean;
+ @b<function> Floor (Container : Set;
+ Key : Key_Type)
+ @b<return> Cursor;
- @b<function> "@>" (Left : Key_Type; Right : Cursor)
- @b<return> Boolean;
+ @b<function> Ceiling (Container : Set;
+ Key : Key_Type)
+ @b<return> Cursor;
+
+ @b<function> Contains (Container : Set;
+ Key : Key_Type) @b<return> Boolean;
@b<procedure> Update_Element_Preserving_Key
(Container : @b<in out> Set;
@@ -9566,16 +9959,15 @@
Two elements @i<E1> and @i<E2> are @i<equivalent> if both @i<E1> < @i<E2> and
@i<E2> < @i<E1> return False, using the generic formal "<" operator for
-elements.
+elements. Function Equivalent_Keys returns True if Left and Right are equivalent,
+and False otherwise.
-Functions "<" and "=" on Element_Type values are expected to return the same
-result value each time they are called with a particular pair of element values.
-If @i<A> = @i<B> returns True, then @i<B> = @i<A> is expected to also return
-True. If @i<A> < @i<B> returns True, then @i<B> < @i<A> is expected to return
-False. For any two equivalent elements, "=" is expected to return True. If "<"
-or "=" behaves in some other manner, the behavior of this package is
-unspecified. Which subprograms of this package call "<" and "=", and how many
-times these functions are called, is unspecified.
+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 must define a strict ordering relationship, 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.
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
@@ -9600,28 +9992,14 @@
element designated by Last (Container) is removed from Container. Delete_Last
tampers with the cursors of Container.>
-@xcode<@b<function> Floor (Container : Set;
- Item : Element_Type) @b<return> Cursor;>
-
-@xindent<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.>
-
-@xcode<@b<function> Ceiling (Container : Set;
- Item : Element_Type) @b<return> Cursor;>
-
-@xindent<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.>
-
@xcode<@b<function> First_Element (Container : Set) @b<return> Element_Type;>
@xindent<Equivalent to Element (First (Container)).>
@xcode<@b<function> Last (Container : Set) @b<return> Cursor;>
-@xindent<Returns a cursor that designates the last node in Container. If Container is
-empty, returns No_Element.>
+@xindent<Returns a cursor that designates the last element in Container. If
+Container is empty, returns No_Element.>
@xcode<@b<function> Last_Element (Container : Set) @b<return> Element_Type;>
@@ -9638,6 +10016,20 @@
@xindent<Equivalent to Position := Previous (Position).>
+@xcode<@b<function> Floor (Container : Set;
+ Item : Element_Type) @b<return> Cursor;>
+
+@xindent<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.>
+
+@xcode<@b<function> Ceiling (Container : Set;
+ Item : Element_Type) @b<return> Cursor;>
+
+@xindent<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.>
+
@xcode<@b<function> "<" (Left, Right : Cursor) @b<return> Boolean;>
@xindent<Equivalent to Element (Left) < Element (Right).>
@@ -9668,27 +10060,29 @@
@xindent<Iterates over the elements in Container as per Iterate, with the
difference that the elements are traversed in predecessor order, starting with
-the last node.>
+the last element.>
-For any two elements @i<E1> and @i<E2>, the boolean values (@i<E1> < @i<E2>),
-(Key(@i<E1>) < @i<E2>), and (Key(@i<E2>) > @i<E1>) are all expected to be equal.
-If Key, Generic_Keys."<", or Generic_Keys.">" behave in some other manner, the
+For any two elements @i<E1> and @i<E2>, the boolean values (@i<E1> < @i<E2>)
+and (Key(@i<E1>) < Key(@i<E2>)) are expected to be equal.
+If Key or Generic_Keys."<" behave in some other manner, the
behavior of this package is unspecified. Which subprograms of this package
-call Key, Generic_Keys."<" and Generic_Keys.">", and how many times the
+call Key and Generic_Keys."<", and how many times the
functions are called, is unspecified.
In addition to the semantics described in A.18.7, the subprograms in package
-Generic_Keys named Floor, Ceiling, "<", and ">", are equivalent to the
+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
-Generic_Keys generic formal relational operators.
+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.
@i<@s8<Implementation Advice>>
If @i<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 @i<N>)**2) or better. The worst-case time
-complexity of the subprograms that take a cursor parameter should be O(1).
+element parameter should be @i<O>((log @i<N>)**2) or better. The worst-case time
+complexity of the subprograms that take a cursor parameter should be @i<O>(1).
!corrigendum A.18.10
@@ -9705,8 +10099,19 @@
has the same contents as Containers.Vectors except:
@xbullet<The generic formal Element_Type is indefinite.>
+
+@xbullet<The procedures with the profiles:>
+@xcode< @b<procedure> Insert (Container : @b<in out> Vector;
+ Before : @b<in> Extended_Index;
+ Count : @b<in> Count_Type := 1);>
+
+@xcode< @b<procedure> Insert (Container : @b<in out> Vector;
+ Before : @b<in> Cursor;
+ Position : @b<out> Cursor;
+ Count : @b<in> Count_Type := 1);>
+@xindent<are omitted.>
-@xbullet<The Element parameter of access subprogram Process of Update_Element
+@xbullet<The actual Element parameter of access subprogram Process of Update_Element
may be constrained even if Element_Type is unconstrained.>
!corrigendum A.18.11
@@ -9734,7 +10139,7 @@
Count : @b<in> Count_Type := 1);>
@xindent<is omitted.>
-@xbullet<The Element parameter of access subprogram Process of Update_Element
+@xbullet<The actual Element parameter of access subprogram Process of Update_Element
may be constrained even if Element_Type is unconstrained.>
!corrigendum A.18.12
@@ -9762,7 +10167,7 @@
Inserted : @b<out> Boolean);>
@xindent<is omitted.>
-@xbullet<The Element parameter of access subprogram Process of Update_Element
+@xbullet<The actual Element parameter of access subprogram Process of Update_Element
may be constrained even if Element_Type is unconstrained.>
!corrigendum A.18.13
@@ -9791,7 +10196,7 @@
Inserted : @b<out> Boolean);>
@xindent<is omitted.>
-@xbullet<The Element parameter of access subprogram Process of Update_Element
+@xbullet<The actual Element parameter of access subprogram Process of Update_Element
may be constrained even if Element_Type is unconstrained.>
!corrigendum A.18.14
@@ -9811,7 +10216,7 @@
@xbullet<The generic formal Element_Type is indefinite.>
-@xbullet<The Element parameter of access subprogram Process of
+@xbullet<The actual Element parameter of access subprogram Process of
Update_Element_Preserving_Key may be constrained even if Element_Type is
unconstrained.>
@@ -9832,7 +10237,7 @@
@xbullet<The generic formal Element_Type is indefinite.>
-@xbullet<The Element parameter of access subprogram Process of
+@xbullet<The actual Element parameter of access subprogram Process of
Update_Element_Preserving_Key may be constrained even if Element_Type is
unconstrained.>
@@ -9858,9 +10263,17 @@
@b<procedure> Ada.Containers.Generic_Array_Sort (Container : @b<in out> Array_Type);
@b<pragma> Pure (Ada.Containers.Generic_Array_Sort);>
-@xindent<Reorders the elements of Container such that the elements are
-sorted smallest first as determined by the generic formal "<" operator
-provided. Any exception raised during evaluation of "<" is propagated.>
+@xindent<Reorders the elements of Container such that the elements are sorted
+smallest first as determined by the generic formal "<" operator provided. Any
+exception raised during evaluation of "<" is propagated.>
+
+@xindent<The actual function for the generic formal function "<" of
+Generic_Array_Sort is expected to return the same value each time it is called
+with a particular pair of element values. It should define a strict ordering
+relationship, that is, be irreflexive, asymmetric, and transitive; it should
+not modify Container. If the actual for "<" behaves in some other manner, the
+behavior of the instance of Generic_Array_Sort is unspecified. How many times
+Generic_Array_Sort calls "<" is unspecified.>
The generic library procedure Containers.Generic_Constrained_Array_Sort has the
following declaration:
@@ -9875,16 +10288,25 @@
(Container : @b<in out> Array_Type);
@b<pragma> Pure (Ada.Containers.Generic_Constrained_Array_Sort);>
-@xindent<Reorders the elements of Container such that the elements are
-sorted smallest first as determined by the generic formal "<" operator
-provided. Any exception raised during evaluation of "<" is propagated.>
+@xindent<Reorders the elements of Container such that the elements are sorted
+smallest first as determined by the generic formal "<" operator provided. Any
+exception raised during evaluation of "<" is propagated.>
+
+@xindent<The actual function for the generic formal function "<" of
+Generic_Constrained_Array_Sort is expected to return the same value each time
+it is called with a particular pair of element values. It should define a
+strict ordering relationship, that is, be irreflexive, asymmetric, and
+transitive; it should not modify Container. If the actual for "<" behaves in
+some other manner, the behavior of the instance of
+Generic_Constrained_Array_Sort is unspecified. How many times
+Generic_Constrained_Array_Sort calls "<" is unspecified.>
@i<@s8<Implementation Advice>>
-The worst-case time complexity of a call on an instantiation of
+The worst-case time complexity of a call on an instance of
Containers.Generic_Array_Sort or Containers.Generic_Constrained_Array_Sort
-should be O(@i<N>**2) or better, and the average time complexity should be better
-than O(@i<N>**2), where @i<N> is the length of the Container parameter.
+should be @i<O>(@i<N>**2) or better, and the average time complexity should be better
+than @i<O>(@i<N>**2), where @i<N> is the length of the Container parameter.
Containers.Generic_Array_Sort and Containers.Generic_Constrained_Array_Sort
should minimize copying of elements.
@@ -10166,640 +10588,6 @@
generic subprogram parameter not have a 'Stop : out Boolean'
parameter? To allow early exit of the iteration, without
having to raise exceptions?
-
-****************************************************************
-
-From: Martin Dowie
-Sent: Wednesday, February 4, 2004 8:21 AM
-
-Is package Ada.Containers.Maps.Strings[ACMS] really what is
-intended, as Ada.Containers.Maps[ACM] is generic this means
-to use ACMS a user must first instantiate ACM and then
-instantiate ACMS.
-
-Charles didn't suffer from this problem as Unbounded maps (~ACM)
-and String Maps (~ACMS) were siblings not parent/child.
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Wednesday, February 4, 2004 8:57 AM
-
->2) For routines like 'Generic_Iteration' shouldn't the 'Process'
-> generic subprogram parameter not have a 'Stop : out Boolean'
-> parameter? To allow early exit of the iteration, without
-> having to raise exceptions?
-
-Just use an active iterator.
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Wednesday, February 4, 2004 9:52 AM
-
-Note that that's not really the correct mode anyway: it should be inout,
-not just out, like this:
-
- generic
- with procedure Process
- (Cursor : in Cursor_Type;
- Done : in out Boolean) is <>;
- procedure Generic_Iteration (Map : in out Map_Type);
-
-The problem with just out-mode is that you always have to give the
-parameter a value. But this is wrong, since you shouldn't be compelled
-to say anything if you merely want to continue. You should only have
-say something when you want to stop.
-
-If you only want to visit some of the items, then just use an active
-iterator, and exit the loop when you need to:
-
- declare
- I : Cursor_Type := First (M);
- J : constant Cursor_Type := Back (M);
- begin
- while I /= J loop
- declare
- E : Element_Type := Element (I);
- begin
- --do something with E
- exit when Predicate (E);
- end;
-
- Increment (I);
- end loop;
- end;
-
-****************************************************************
-
-From: Martin Dowie
-Sent: Wednesday, February 4, 2004 10:06 AM
-
-
-[snip]
-> If you only want to visit some of the items, then just use an active
-> iterator, and exit the loop when you need to:
-[snip]
-
-I could but wasn't part of the purpose of the library to allow us to
-do common things more easily? And I'd have to say I'd use a 'Quit'
-version a _lot_ more than the current process everything,
-every time one.
-
-I'd be delighted if both versions could be included! :-)
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Wednesday, February 4, 2004 11:16 AM
-
-Dowie, Martin (UK) wrote:
-> I could but wasn't part of the purpose of the library to allow us to
-> do common things more easily? And I'd have to say I'd use a 'Quit'
-> version a _lot_ more than the current process everything,
-> every time one.
-
-It would be helpful if you could be specific about what kind of
-container you were using.
-
-The vector has neither active nor passive iterators, which means that
-for a vector you have to use a loop anyway.
-
-For the hashed map, I would find it very odd if you needed to traverse
-only some of its elements, since elements are stored in hash order.
-What would be the nature of the predicate?
-
-The sorted set is the borderline case.
-
-****************************************************************
-
-From: Peter Hermann
-Sent: Wednesday, February 4, 2004 5:57 AM
-
-> package Ada.Strings.Case_Insensitive is
-
-indeed useful.
-expected to be overloaded for fixed and (un)bounded strings.
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Wednesday, February 4, 2004 9:02 AM
-
->Is package Ada.Containers.Maps.Strings[ACMS] really what is
->intended, as Ada.Containers.Maps[ACM] is generic this means
->to use ACMS a user must first instantiate ACM and then
->instantiate ACMS.
-
-That's definitely a bug in the report. The string-key map is not a
-child of a generic. Maybe we should do this:
-
-package Ada.Containers.Maps
-package Ada.Containers.String_Maps
-
-****************************************************************
-
-From: Marius Amado Alves
-Sent: Wednesday, February 4, 2004 9:07 AM
-
-Yes, please change that. There is a steady requirement that a single
-instantiation must be enough to get a container.
-
-****************************************************************
-
-From: Pascal Obry
-Sent: Wednesday, February 4, 2004 10:10 AM
-
-> The problem with just out-mode is that you always have to give the
-> parameter a value. But this is wrong, since you shouldn't be compelled
-> to say anything if you merely want to continue. You should only have
-> say something when you want to stop.
-
-Agreed, this is the way iterators are designed in the POSIX 1003.5 standard
-for example.
-
-****************************************************************
-
-From: Marius Amado Alves
-Sent: Wednesday, February 4, 2004 9:02 AM
-
-> 2) For routines like 'Generic_Iteration' shouldn't the 'Process'
-> generic subprogram parameter not have a 'Stop : out Boolean'
-> parameter? To allow early exit of the iteration, without
-> having to raise exceptions?
-
-Indeed some people ban the use of exceptions for control flow. I guess they
-are not a majority in the committee. Fortunately ;-)
-
-/* However to take the exception route the exception should be defined.
-(Exit/Terminate_Immediately, _Now, _Prematurely?) Or a specification be made
-of what exceptions the iterator is guaranteed to propagate. Simply "all"
-would do. Maybe this is already there. I'm sorry, I didn't had time to read
-the AI fully yet. */
-
-****************************************************************
-
-From: Randy Brukardt
-Sent: Wednesday, February 4, 2004 8:55 PM
-
-Marius Amado Alves wrote:
-
-> Sorry for my poor knowledge of ARG procedure.
-> Does this step mean the library is secured for Ada 2005?
-
-What it means is that the study committee has issued a report. No more, and
-no less. I would hope that we know more after the March ARG meeting, but
-there is no guarantee that we'll work on it (we never seem to get to
-everything on the agenda - we didn't work on AI-351, Time Ops in San Diego,
-for instance).
-
-Primarily, we just "cleaned up" Matt Heaney's proposal. We didn't change (as
-opposed to remove) functionality, with the exception of the Map container
-(where we reverted to a design more like the one Charles actually uses -
-with Matt's input). So the vast majority of design decisions are Matt's --
-we'd prefer to avoid design-by-committee.
-
-Martin Dowie wrote:
-
-> Is package Ada.Containers.Maps.Strings[ACMS] really what is
-> intended, as Ada.Containers.Maps[ACM] is generic this means
-> to use ACMS a user must first instantiate ACM and then
-> instantiate ACMS.
-
-Nope, that's clearly a bug. String_Maps ought to be usable by itself (it
-doesn't depend on the other package at all). (And this one is my fault, for
-not noticing the effect of the change.)
-
-And later, replying to Matt:
-
->[snip]
->> If you only want to visit some of the items, then just use an active
->> iterator, and exit the loop when you need to:
->[snip]
-
->I could but wasn't part of the purpose of the library to allow us to
->do common things more easily? And I'd have to say I'd use a 'Quit'
->version a _lot_ more than the current process everything,
->every time one.
-
-My understanding of Matt's design is that you use the passive iterator when
-you want to process everything (which is by far the most common), and you
-use an active iterator when you want to process part of the items. You might
-use an exception to terminate iteration in an error case, but not if you
-intended only to process part of the items. (Of course, there is no law
-requiring that, so YMMV!)
-
-I hadn't noticed that there is no passive iterator for vectors until Matt
-pointed it out last night (about 20 minutes before we released the report!).
-Consistency would suggest that there should be one, but note that it is
-easier to write an active iterator for a vector than it is to write a
-passive one:
-
- for I in First(Vect) .. Last(Vect) loop
- -- Do whatever.
- end loop;
-
-versus
-
- declare
- procedure Process (I : in Index_Subtype) is
- begin
- -- Do whatever.
- end Process;
- procedure Do_It_All is new Generic_Iterator (Process);
- begin
- Do_It_All (Vect);
- end;
-
-Besides being longer and harder to read, you have to know or look up the
-index subtype for the vector in order to write this. So we reached no
-conclusion about that in the 20 minutes we had to think about it.
-
-Marius Amado Alves wrote:
-
-> /* However to take the exception route the exception should be defined.
-> (Exit/Terminate_Immediately, _Now, _Prematurely?) Or a specification be
-made
-> of what exceptions the iterator is guaranteed to propagate. Simply "all"
-> would do. Maybe this is already there. I'm sorry, I didn't had time to
-read
-> the AI fully yet. */
-
-The wording for Generic_Iteration for a Map says:
-
-Generic_Iteration calls Process with a cursor that designates each
-node in the Map. Any exceptions raised during Process are propagated.
-
-So it's covered. This is important, because it means that the implementation
-must be able to clean itself up (if any is needed) when an exception
-propagates - it can't leave the Map in an unstable state.
-
-****************************************************************
-
-From: Jeffrey Carter
-Sent: Wednesday, February 4, 2004 8:53 PM
-
-AI-302-03 asks
-
-> Anybody got better wording [for the quality of the String hashing
-> function]? Matt was nice enough to ignore these definitions
-> completely!
-
-See
-
-P. K. Pearson, "Fast Hashing of Variable-Length Text Strings," Comm.
-ACM, 1990 Jun
-
-It describes a "hashing function specifically tailored to
-variable-length text strings." It says that "similar strings are not
-likely to collide." (An implementation can be found in
-PragmARC.Hash_Fast_Variable_Length.) Perhaps you might think this last
-quote is "better wording".
-
-The actual algorithm produces 8-bit hash values, which may no longer be
-considered adequate, given
-
-> Hash_Type'Modulus shall be at least as large as the smaller of
-> System.Max_Binary_Modulus and 2**32.
-
-I have some comments on the proposal:
-
-The proposal has a structure called a "Vector" which is actually a list,
-which is a sequence that allows insertions and deletions at any point.
-"Vector" refers to a mathematical concept related to matrices to most
-software engineers. It may be that the STL refers to lists as vectors,
-but I hope we do not have to follow C++'s mistakes.
-
-Further, the proposal requires an inefficient array implementation, and
-several of the operations refer to this implementation. I think this is
-a mistake. Specify an general, unbounded list and let the implementor
-choose the implementation (which could be an array). As the proposal
-points out, correctly implementing a general list is not trivial, so it
-makes sense for a standard library to provide a list.
-
-Maps and sets also specify a specific implementation.
-
-If the intention is to have an extensible array structure, then I
-suggest that they be called Extensible_Arrays.
-
-Vector should have an iterator, in addition to allowing the user to
-explicitly iterate over the structure.
-
-> Open issue: This function returns a value that doesn't depend on it's
-> parameter. It possibility could be removed in favor of just saying
-> Index_Type'Pred(Index_Type'First) appropriately. Committee discussion
-> with the original proposal's author was inconclusive.
-
-I'd say that it should be a constant, not a function. The same seems to
-hold for First.
-
-Given that Back is defined as Index_Type'Succ (Last (Vector) ), and Last
-(Vector) could be Index_Type'Last, there seems to be a problem. There
-should be an assertion that Index_Type'Base'Last > Index_Type'Last.
-
-All the problems with Index_Type disappear with a general list, which
-would use a cursor.
-
-I would propose that the sort algorithm be made available to users for
-normal array types as well as for vectors. That would involve putting it
-in its own library unit and refering to that unit in Vectors.
-
-The Map structure is required to be implemented with a hash table. If
-we're going to have such a requirement, it should at least be named
-Hashed_Maps.
-
-An important thing about maps is that they provide fast searching,
-typically based on a lower-level structure such as a hash table or
-balanced tree. Such structures have uses of their own in addition to
-creating maps, and independent of the key/value concept of a map. For
-example, an application may collect a number of values and then need to
-quickly determine if a value is in that collection, and a searchable
-structure with a Get_First operation can be used for a priority queue.
-None of these applications use key/value pairs. Therefore, I think it's
-important to provide the underlying searchable structure to users.
-(Indeed, given the ease with which a user can wrap a key/value pair in a
-record, define comparison operations for that record that only use the
-key part, and create a map structure, given the existence of a
-searchable structure, it could be argued, since the proposal states that
-easily implemented structures should not be part of the library, that
-the library should only supply searchable structures, and not maps.)
-
-Do we really need Maps.[Wide_]Strings, given that an Unbounded_String
-can be used for the key type, and that this library should not be used
-for applications in which the use of Unbounded_Strings is not acceptable?
-
-The Sets package is mostly incomprehensible. Sets deal with elements,
-and operations must include testing if an element is in a set, creating
-a set from a list of elements (set "literals"), and set union,
-intersection, difference, and symmetric difference. Except for the
-membership test, these are missing from the package, so I don't see what
-it has to do with sets. It appears to be a searchable structure, not a
-set. This is corroborated by the package Generic_Keys, which allows the
-structure to be used as a map.
-
-The discussion of the package begins by talking about nodes, which is an
-undefined term. The reader has no idea what it has to do with the
-package, which is not specified in terms of nodes.
-
-"Sans" is a French word. Since the ARM is in English, we should use the
-English "without" instead. "No" might also be acceptable.
-
-I'd like to thank the select committee for their work. No library will
-completely please everyone. I will welcome any standard container
-library in Ada 0X.
-
-****************************************************************
-
-From: Tucker Taft
-Sent: Wednesday, February 4, 2004 9:24 PM
-
-The term "vector" for extensible array is used in Java
-as well. I think we should strive to use terminology
-that has become widely used in the programming community.
-
-I personally consider an extensible array (i.e. a vector) a useful and
-important standard container. I don't feel the same way about a linked
-list, because it is so easy to implement what you want, and there
-are so many options when it comes to how to link the objects
-together that having a standard container for that hardly
-seems worthwhile (IMHO).
-
-So we settled on Vector, Map, and Set as three basic yet
-important abstractions that will help lift the level of
-programming above arrays and records. In my experience
-with using languages that have large container libraries,
-it is these three that are used more widely than all
-the others combined.
-
-****************************************************************
-
-From: Randy Brukardt
-Sent: Wednesday, February 4, 2004 9:29 PM
-
-I agree with one caveat: we're already adding something else called "Vector"
-to the standard (see AI-296), and two might just be too confusing.
-
-But, the container vector is more useful than the list container (because of
-the calculated O(1) access to elements). And they're too similar to support
-both when we're trying to support something managable.
-
-****************************************************************
-
-From: Randy Brukardt
-Sent: Wednesday, February 4, 2004 9:39 PM
-
-Jeffrey Carter said:
-...
-> Further, the proposal requires an inefficient array implementation, and
-> several of the operations refer to this implementation. I think this is
-> a mistake. Specify an general, unbounded list and let the implementor
-> choose the implementation (which could be an array). As the proposal
-> points out, correctly implementing a general list is not trivial, so it
-> makes sense for a standard library to provide a list.
->
-> Maps and sets also specify a specific implementation.
-
-No, an implementation is suggested (in AARM notes), as are performance
-characteristics. That was one of the larger changes to Matt's original
-proposal. If we made that change incompletely somewhere, that needs to be
-fixed.
-
-That said, the most important thing is that all implementations have
-consistent performance characteristics (so that porting a program from GNAT
-to ObjectAda doesn't fail for performance reasons). If GNAT used an array
-implementation and ObjectAda used a list implementation for a Vector, access
-to elements (which would be O(N) on the imagined OA implementation) could be
-too slow for the port to be viable. That needs to be avoided. OTOH,
-specifying too much about the implementation would prevent using a better
-one -- in that case, we might as well just specify the source code of the
-entire library (including the bodies!), and we don't need all of this
-wording!
-
-> I would propose that the sort algorithm be made available to users for
-> normal array types as well as for vectors. That would involve putting it
-> in its own library unit and refering to that unit in Vectors.
-
-Bad idea. To do that, you'd need provide generic formal accessor functions;
-that would have a huge overhead of function calls for both Vectors and
-Arrays. On a code shared implementation like Janus/Ada, it probably would
-run ten times slower than the specified one.
-
-If we want an array sort, we should declare one:
-
- generic
- type Index_Type is (<>);
- type Element_Type is private;
- function "<" (Left, Right : Element_Type) return Boolean is <>;
- type Array_Type is array (Index_Type) of Element_Type;
- procedure Ada.Generic_Sort (Arr : in out Array_Type);
-
-(We'd need an unconstrained version, too.) But keep it separate from the
-Vector one (or any List one, for that matter).
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Thursday, February 5, 2004 9:31 AM
-
-I have hosted a reference implementation at my Earthlink home page:
-
-<http://home.earthlink.net/~matthewjheaney/charles/ai302-20040205.zip>
-
-For now it only includes the vector. There's a test_sort program in
-there too, so you have something you can run.
-
-I'll have the set and maps done in a few days.
-
-****************************************************************
-
-From: Robart A. Duff
-Sent: Thursday, February 5, 2004 10:13 AM
-
-Thanks, Matt!
-
-****************************************************************
-
-From: Jeffery Carter
-Sent: Thursday, February 5, 2004 10:58 AM
-
-Randy Brukardt wrote:
-
-> No, an implementation is suggested (in AARM notes), as are performance
-> characteristics. That was one of the larger changes to Matt's original
-> proposal. If we made that change incompletely somewhere, that needs to be
-> fixed.
-
-The normative text for vectors says
-
-"A vector container object manages an unconstrained internal array"
-
-That specifies an array implementation.
-
-> Bad idea. To do that, you'd need provide generic formal accessor functions;
-> that would have a huge overhead of function calls for both Vectors and
-> Arrays. On a code shared implementation like Janus/Ada, it probably would
-> run ten times slower than the specified one.
-
-Given that an array implementation is specified, there is no need for
-formal accessor functions. The vector can simply call an instantiation
-of the sort with the appropriate slice of its internal array. Since we
-require such an algorithm to exist, and it is useful to many users, it
-makes sense for it to be available outside the vector package.
-
-> If we want an array sort, we should declare one:
->
-> generic
-> type Index_Type is (<>);
-> type Element_Type is private;
-> function "<" (Left, Right : Element_Type) return Boolean is <>;
-> type Array_Type is array (Index_Type) of Element_Type;
-> procedure Ada.Generic_Sort (Arr : in out Array_Type);
->
-> (We'd need an unconstrained version, too.) But keep it separate from the
-> Vector one (or any List one, for that matter).
-
-If we only have one, I'd prefer it to be unconstrained. That allows
-operations such as the vector sort discussed above, where the size of
-the slice may change from call to call, without repeated instantiations.
-
-Sort for a list is a different creature. Merge sort is a good choice
-there, since a list already has the O(N) additional space that merge
-sort requires for array sorting (in the links), provided you have access
-to the list internals. Thus you get O(N log N) time in all cases and
-O(1) space.
-
-****************************************************************
-
-From: Randy Brukardt
-Sent: Thursday, February 5, 2004 3:23 PM
-
-Jeff Carter wrote:
-
-> The normative text for vectors says
->
-> "A vector container object manages an unconstrained internal array"
->
-> That specifies an array implementation.
-
-Precisely my point. That is intended to say that there is a logical array in
-the container, but not necessarly an actual one. Matt's descriptions were
-too implementation-specific, and we moved most of that. But I'm not
-surprised that some was missed.
-
-...
-> Given that an array implementation is specified, there is no need for
-> formal accessor functions. The vector can simply call an instantiation
-> of the sort with the appropriate slice of its internal array. Since we
-> require such an algorithm to exist, and it is useful to many users, it
-> makes sense for it to be available outside the vector package.
-
-There is no intent that an array implementation is specified (it certainly
-won't be implemented that way on Janus/Ada); only that the performance
-characteristics are similar (or better) than that of an array
-implementation.
-
-In any case, I have no idea how an external generic would be able to mess
-around with the internal array - it certainly can't see it! You'd have to
-put the sort into the spec in order to do that -- and that's whats proposed
-and what you're objecting to.
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Thursday, February 5, 2004 3:40 PM
-
-Randy Brukardt wrote:
-
-> Precisely my point. That is intended to say that there is a logical array in
-> the container, but not necessarly an actual one.
-
-Yes, exactly. This allows the implementor to leave the type system in
-order choose the optimal implementation for the vector container.
-
-An implementor can use any implementation that satisfies the property
-that insertion at the back end is (amortized) constant time, and the
-property that random access is constant time.
-
-****************************************************************
-
-From: Jeffrey Carter
-Sent: Thursday, February 5, 2004 6:52 PM
-
-Randy Brukardt wrote:
-
->>The normative text for vectors says
->>
->>"A vector container object manages an unconstrained internal array"
->>
->>That specifies an array implementation.
->
-> Precisely my point. That is intended to say that there is a logical array in
-> the container, but not necessarly an actual one. Matt's descriptions were
-> too implementation-specific, and we moved most of that. But I'm not
-> surprised that some was missed.
-
-I read it as specifying an implementation. I suggest the wording be
-revised to make it clear that the discussion is of a logical array, not
-a requirement for an actual array.
-
-> In any case, I have no idea how an external generic would be able to mess
-> around with the internal array - it certainly can't see it! You'd have to
-> put the sort into the spec in order to do that -- and that's whats proposed
-> and what you're objecting to.
-
-I guess I wasn't clear. You would provide the external sort, and also
-specify the sort in the spec, with wording that the sort has the same
-characteristics as the external sort. This is based on the assumption
-that an array implementation is specified, so the sort algorithm, useful
-on arrays, must exist anyway.
-
-I'm reminded of my surprise that Ada-83 compilers had to support
-inifinte-precision arithmetic, but the language did not require that it
-made available to users. If the compiler writers have to implement the
-functionality, why not make it available to users? Case-insensitive
-string comparison is a similar thing: compilers have to recognize that
-frog, Frog, and FROG are the same identifier, but are (were) not
-required to make such comparisons available to users.
****************************************************************
Questions? Ask the ACAA Technical Agent