CVS difference for ais/ai-20302.txt
--- ais/ai-20302.txt 2004/04/23 03:50:22 1.4
+++ ais/ai-20302.txt 2004/04/30 02:32:16 1.5
@@ -1,4 +1,4 @@
-!standard A.17 04-04-12 AI95-00302-03/03E
+!standard A.17 04-04-29 AI95-00302-03/03
!class amendment 04-01-14
!status work item 04-01-14
!status received 04-01-14
@@ -148,18 +148,13 @@
function Ada.Strings.Hash (Key : String) return Containers.Hash_Type;
pragma Pure (Ada.Strings.Hash);
-with Ada.Containers;
-function Ada.Strings.Unbounded.Hash (Key : Unbounded_String) return
- Containers.Hash_Type;
-pragma Pure (Ada.Strings.Unbounded.Hash);
-
-function Ada.Strings.Hash (Key : String) return Containers.Hash_Type;
-
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).
+with Ada.Containers;
function Ada.Strings.Unbounded.Hash (Key : Unbounded_String) return
Containers.Hash_Type;
+pragma Pure (Ada.Strings.Unbounded.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).
@@ -176,6 +171,22 @@
several child packages, which provide facilities for storing collections
of elements.
+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.
+
+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).
+
+If the advice suggests that the complexity should be less than
+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.
+
AARM Text
Language Design Principles
@@ -301,11 +312,11 @@
A vector container object manages an unconstrained internal array, which
expands as necessary as items are inserted. The *size* of a vector
corresponds to the total length of the internal array, and the *length*
-of a vector corresponds to the number active elements in the internal
+of a vector corresponds to the number of active elements in the internal
array.
A vector container may contain *empty elements*. Empty elements do not have a
-defined value.
+specified value.
AARM Notes:
@@ -360,6 +371,8 @@
function "&" (Left : Element_Type;
Right : Vector) return Vector;
+ function "&" (Left, Right : Element_Type) return Vector;
+
function "=" (Left, Right : Vector) return Boolean;
function Size (Container : Vector) return Size_Type;
@@ -378,6 +391,28 @@
function To_Index (Position : Cursor) return Index_Type'Base;
+ function Element (Container : Vector;
+ Index : Index_Type'Base)
+ return Element_Type;
+
+ function Element (Position : Cursor) return Element_Type;
+
+ generic
+ with procedure Process (Element : in out Element_Type) is <>;
+ procedure Generic_Update_by_Index (Container : in Vector;
+ Index : in Index_Type'Base);
+
+ generic
+ with procedure Process (Element : in out Element_Type) is <>;
+ procedure Generic_Update (Position : in Cursor);
+
+ procedure Replace_Element (Container : in Vector;
+ Index : in Index_Type'Base;
+ By : in Element_Type);
+
+ procedure Replace_Element (Position : in Cursor;
+ By : in Element_Type);
+
procedure Assign (Target : in out Vector;
Source : in Vector);
@@ -467,28 +502,6 @@
function Last_Element (Container : Vector)
return Element_Type;
- function Element (Container : Vector;
- Index : Index_Type'Base)
- return Element_Type;
-
- function Element (Position : Cursor) return Element_Type;
-
- generic
- with procedure Process (Element : in out Element_Type) is <>;
- procedure Generic_Update_by_Index (Container : in Vector;
- Index : in Index_Type'Base);
-
- generic
- with procedure Process (Element : in out Element_Type) is <>;
- procedure Generic_Update (Position : in Cursor);
-
- procedure Replace_Element (Container : in Vector;
- Index : in Index_Type'Base;
- By : in Element_Type);
-
- procedure Replace_Element (Position : in Cursor;
- By : in Element_Type);
-
procedure Swap (Container : in Vector;
I, J : in Index_Type'Base);
@@ -512,8 +525,7 @@
function Reverse_Find (Container : Vector;
Item : Element_Type;
- Index : Index_Type'Base :=
- Index_Type'Pred (Index_Type'First))
+ Index : Index_Type'Base := Index_Type'Last)
return Index_Type'Base;
function Reverse_Find (Container : Vector;
@@ -575,22 +587,24 @@
function "&" (Left, Right : Vector) return Vector;
-Returns a vector comprising the elements of Right appended to the
-elements of Left.
+Returns a vector comprising the elements of Right appended in their
+original order to the vector Left.
function "&" (Left : Vector;
Right : Element_Type) return Vector;
-Returns a vector comprising the element Right appended to the elements
-of Left.
+Returns a vector comprising the element Right appended to the vector Left.
function "&" (Left : Element_Type;
Right : Vector) return Vector;
+
+Returns a vector comprising the element Left prepended to the vector Right.
-Returns a vector comprising the element Right prepended to the elements
-of Left.
+function "&" (Left, Right : Element_Type) return Vector;
+Returns a vector comprising the element Left followed by the element Right.
+
function "=" (Left, Right : Vector) return Boolean;
If Left denotes the same object as Right, then this function returns
@@ -607,7 +621,7 @@
Returns the length of the internal array.
-procedure Resize (Container : in out Vector;
+procedure Resize (Container : in out Vector;
Size : in Size_Type);
If Size (Container) is equal to or greater than Size, the operation does
@@ -629,7 +643,8 @@
size such that future Inserts do not require memory allocation overhead.
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 the memory is needed.
+waiting until the memory is needed. This doesn't apply to the indefinite
+element container, because elements will have to be allocated individually.
End AARM Notes
@@ -652,8 +667,8 @@
Index : Index_Type'Base) return Cursor;
If the value of Index is not in the range First_Index (Container) .. Last_Index
-(Container), then Constraint_Error is propagated. Otherwise, a cursor
-designating the element currently at Index in Container is returned.
+(Container), then No_Element is returned. Otherwise, a cursor designating the
+element currently at Index in Container is returned.
function To_Index (Position : Cursor) return Index_Type'Base;
@@ -667,9 +682,85 @@
containing an access to the vector container and a index value. This does
constrain implementations, but it also allows all of the cursor operations
to be defined in terms of the corresponding index operation (which should be
-primary for a vector). [Anyone that wants to change this is invited to rewrite
-this section first - ED]
+primary for a vector).
+
+
+function Element (Container : Vector;
+ Index : Index_Type'Base)
+ return Element_Type;
+
+If Index is not in the range First_Index (Container) .. Last_Index (Container),
+then Constraint_Error is propagated. Otherwise this function returns the
+element at position Index.
+
+
+function Element (Position : Cursor) return Element_Type;
+
+Returns the element designated by Position. If Position equals No_Element,
+then Constraint_Error is propagated.
+
+generic
+ with procedure Process (Element : in out Element_Type) is <>;
+procedure Generic_Update_by_Index (Container : in Vector;
+ Index : in Index_Type'Base);
+
+If Index is not in the range First_Index (Container) .. Last_Index (Container),
+then Constraint_Error is propagated. Otherwise, it calls the generic actual
+bound to Process with the element at position Index as the parameter. Any
+exceptions raised by Process are propagated.
+
+If Element_Type is unconstrained and definite, then the Element parameter
+shall be unconstrained.
+
+AARM Note: This means that the elements cannot be aliased nor directly
+allocated from the heap; it must be possible to change the discriminants
+of the element in place.
+
+The element at position Index is not an empty element after successful
+completion of this operation.
+
+AARM Note: Since reading an empty element is a bounded error, attempting to
+use this procedure to replace empty elements may fail. Use Replace_Element
+to do that reliably.
+
+generic
+ with procedure Process (Element : in out Element_Type) is <>;
+procedure Generic_Update (Position : in Cursor);
+
+Calls the generic actual bound to Process with the element designated by
+Position as the parameter. If Position equals No_Element, then
+Constraint_Error is propagated. Any exceptions raised by Process are
+propagated.
+
+If Element_Type is unconstrained and definite, then the Element parameter
+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'Base;
+ By : in Element_Type);
+
+If Index does not specify a value in the range First_Index (Container) ..
+Last_Index (Container), then Constraint_Error is propagated. Otherwise this
+function assigns the value By to the element at position Index. Any exceptions
+raised during the assignment are propagated. The element at position Index is
+not an empty element after successful completion of this operation.
+
+procedure Replace_Element (Position : in Cursor;
+ By : in Element_Type);
+
+This function assigns the value By to the element designated by Position.
+If Position equals No_Element, then Constraint_Error is propagated.
+Any exceptions raised during the assignment are propagated. The element
+designated by Position is not an empty element after successful completion of
+this operation.
+
+AARM Note: Replace_Element, Generic_Update, and Generic_Update_by_Index are
+only ways that an element can change from empty to non-empty.
+
procedure Assign (Target : in out Vector;
Source : in Vector);
@@ -841,6 +932,9 @@
elements (if any) starting Index plus Count down to Index. Any
exceptions raised during element assignment are propagated.
+AARM Note: If Index + Count > Length(Container), this effectively truncates
+the vector at Index-1 (setting Length to Index-1).
+
procedure Delete (Container : in out Vector;
Position : in out Cursor;
Count : in Size_Type := 1);
@@ -856,11 +950,12 @@
procedure Delete_Last (Container : in out Vector;
Count : in Size_Type := 1);
-Equivalent to Delete (Container, Last_Index (Container), Count).
+If Length (Container) < Count then is equivalent to
+Delete (Container, Index_Type'First, Count); otherwise
+is equivalent to Delete (Container,
+Index_Type'Val(Index_Type'Pos(Last_Index(Container)) - Count + 1), Count).
-function First_Index (Container : Vector) return Index_Type;
-
Returns the value Index_Type'First.
AARM Note: We'd rather call this "First", but then calling most routines in
@@ -892,81 +987,6 @@
Equivalent to Element (Container, Last_Index (Container)).
-function Element (Container : Vector;
- Index : Index_Type'Base)
- return Element_Type;
-
-If Index is not in the range First_Index (Container) .. Last_Index (Container),
-then Constraint_Error is propagated. Otherwise this function returns the
-element at position Index.
-
-
-function Element (Position : Cursor) return Element_Type;
-
-Returns the element designated by Position. If Position equals No_Element,
-then Constraint_Error is propagated.
-
-generic
- with procedure Process (Element : in out Element_Type) is <>;
-procedure Generic_Update_by_Index (Container : in Vector;
- Index : in Index_Type'Base);
-
-If Index is not in the range First_Index (Container) .. Last_Index (Container),
-then Constraint_Error is propagated. Otherwise, it calls the generic actual
-bound to Process with the element at position Index as the parameter. Any
-exceptions raised by Process are propagated.
-
-If Element_Type is unconstrained and definite, then the Element parameter
-shall be unconstrained.
-
-AARM Note: This means that the elements cannot be aliased nor directly
-allocated from the heap; it must be possible to change the discriminants
-of the element in place.
-
-The element at position Index is not an empty element after successful
-completion of this operation.
-
-AARM Note: Since reading an empty element is a bounded error, attempting to
-use this procedure to replace empty elements may fail. Use Replace_Element
-to do that reliably.
-
-generic
- with procedure Process (Element : in out Element_Type) is <>;
-procedure Generic_Update (Position : in Cursor);
-
-Calls the generic actual bound to Process with the element designated by
-Position as the parameter. If Position equals No_Element, then
-Constraint_Error is propagated. Any exceptions raised by Process are
-propagated.
-
-If Element_Type is unconstrained and definite, then the Element parameter
-shall be unconstrained.
-
-The element at position Index is not an empty element after successful
-completion of this operation.
-
-procedure Replace_Element (Container : in Vector;
- Index : in Index_Type'Base;
- By : in Element_Type);
-
-If Index does not specify a value in the range First_Index (Container) ..
-Last_Index (Container), then Constraint_Error is propagated. Otherwise this
-function assigns the value By to the element at position Index. Any exceptions
-raised during the assignment are propagated. The element at position Index is
-not an empty element after successful completion of this operation.
-
-procedure Replace_Element (Position : in Cursor;
- By : in Element_Type);
-
-This function assigns the value By to the element designated by Position.
-If Position equals No_Element, then Constraint_Error is propagated.
-Any exceptions raised during the assignment are propagated. The element
-designated by Position is not an empty element after successful completion of
-this operation.
-
-AARM Note: Replace_Element, Generic_Update, and Generic_Update_by_Index are
-only ways that an element can change from empty to non-empty.
-
procedure Swap (Container : in Vector;
I, J : in Index_Type'Base);
@@ -989,8 +1009,8 @@
procedure Generic_Sort (Container : in Vector);
Reorders the elements of Vector such that the elements are
-sorted per the order specified as the generic formal less-than operator.
-Any exceptions raised during evalution of less-than are propagated.
+sorted smallest first as determined by the generic formal "<" operator
+provided. Any exceptions raised during evalution of "<" are propagated.
AARM Notes
This implies swapping the elements, usually including an intermediate copy.
@@ -1031,14 +1051,12 @@
function Reverse_Find (Container : Vector;
Item : Element_Type;
- Index : Index_Type'Base :=
- Index_Type'Pred (Index_Type'First))
+ Index : Index_Type'Base := Index_Type'Las))
return Index_Type'Base;
Searches the elements of Container in reverse for an element equal to
Item, starting at position Index. If Index is greater than Last_Index
-(Container), then Constraint_Error is propagated. If Index is less than
-Index_Type'First, then the search begins at position Last_Index (Container).
+(Container), then the search begins at position Last_Index (Container).
If there are no elements in the range Index_Type'First .. Index equal
to Item, then Reverse_Find returns Index_Type'Succ (Last_Index (Container)).
Otherwise, it returns the index of the matching element.
@@ -1060,23 +1078,21 @@
Container : Vector)
return Boolean;
-Equivalent to Find (Container, Item).
+Equivalent to Has_Element (Find (Container, Item)).
function Next (Position : Cursor) return Cursor;
-If Position equals No_Element, then Next returns the value
-No_Element. If Position designates the last element of the container,
-then Next returns No_Element. Otherwise, returns a cursor that designates
-the element with index Index_Type'Succ (To_Index (Position)) in the
+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 Index_Type'Succ (To_Index (Position)) in the
same vector as Position.
function Previous (Position : Cursor) return Cursor;
-If Position equals No_Element, then Previous returns the value No_Element. If
- Position designates the first element of the container, then Previous returns
-No_Element. Otherwise, returns a cursor that designates
-the element with index Index_Type'Pred (To_Index (Position)) in the
+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 Index_Type'Pred (To_Index (Position)) in the
same vector as Position.
The procedure Next is equivalent to Position := Next (Position).
@@ -1087,7 +1103,7 @@
Returns True if Position designates an element, and returns False otherwise.
-AARM Note: To Be Honset: This function is may not detect cursors that
+AARM Note: To Be Honest: This function is may not detect cursors that
designate deleted elements; such cursors are invalid (see below) and any
use of them (including in this routine) is erroneous.
@@ -1096,8 +1112,8 @@
procedure Generic_Iteration (Container : in Vector);
Invokes the actual subprogram bound to Process with a cursor that
-designates each node element Container. Any exceptions raised during Process
-are propagated.
+designates each element in Container, in index order. Any exceptions raised
+during Process are propagated.
generic
with procedure Process (Position : in Cursor) is <>;
@@ -1130,7 +1146,7 @@
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
-if the type has if the type has default initial value(s).
+if the type has default initial value(s).
Assignment and streaming of empty elements are NOT bounded errors.
This is consistent with regular composite types, for which assignment and
@@ -1141,8 +1157,8 @@
above.
End AARM Notes.
-A Cursor value is *dubious* if any of the following have occurred since it was
-created:
+A Cursor value is *ambiguous* if any of the following have occurred since it
+was created:
* Insert or Delete has been called on the vector that contains the element the
cursor designates with a index value (or a cursor designating an element at
such an index value) less than or equal to the index value of the element
@@ -1151,19 +1167,19 @@
instance of Generic_Sort.
It is a bounded error to call any subprogram other than "=" or Has_Element
-declared in Containers.Vectors with a dubious (but not invalid, see below)
+declared in Containers.Vectors with a ambiguous (but not invalid, see below)
cursor parameter. Possible results are:
* The cursor may be treated as if it was No_Element;
* The cursor may designate some element in the vector (but not necessarily
- the element that it designates);
+ the element that it originally designated);
* Constraint_Error may be raised; or
* Program_Error may be raised.
-AARM Note: Cursors are invalidated if an Insert or Delete occurs that moves
-the elements in the internal array including the designated ones. After such
-an operation, the cursor probably still designates an element (although it
-might not after a deletion), but it is is a *different* element.
-That violates the definition of cursor -- it designates a particular element.
+AARM Note: Cursors are made ambiguous if an Insert or Delete occurs that moves
+the elements in the internal array including the designated ones. After such an
+operation, the cursor probably still designates an element (although it might
+not after a deletion), but it is is a *different* element. That violates the
+definition of cursor -- it designates a particular element.
For "=" or Has_Element, the cursor works normally (it would not be No_Element).
We don't want to trigger an exception simply for comparing a bad cursor.
@@ -1204,11 +1220,10 @@
Containers.Vectors should be implemented similarly to an array. In particular,
if the length of a vector is *N*, then
- * the time taken by Append with Count=1 and Element should take time no
- worse than roughly proportional to the log (base 2) of N;
- * the time taken by Prepend with Count=1 or Delete_First with Count=1 of
- the vector should take time no worse than roughly proportional to
- N * log (base 2) of N.
+ * the worst-case time complexity of Append with Count=1 and Element should
+ be O(log N);
+ * the worst-case time complexity of Prepend with Count=1 or Delete_First
+ with Count=1 of the vector should be O(N log N).
AARM Note
We do not mean to overly constrain implementation stratgies here. However, it
@@ -1219,10 +1234,9 @@
the proportionality constant and caching effects are likely to be larger than
the log factor, and we don't want to discourage innovative implementations.
-A call on an instantiation of Containers.Vectors.Generic_Sort should take no
-worse than a time proportional to the square of the number of items in the
-vector, and on average a time better than proportional to the square of the
-number of items in the vector.
+The worst-case time complexity of a call on an instantiation of
+Containers.Vectors.Generic_Sort should be O(N**2), and
+the average time complexity should be better than O(N**2).
AARM Note
In other words, we're requiring the use of a better than O(N**2) sorting
@@ -1252,9 +1266,6 @@
next (successor) and previous (predecessor) internal nodes. A cursor
is used to specify positions of particular storage nodes within a list.
-A list container may contain *empty elements*. Empty elements do not have a
-defined value.
-
Static Semantics
The library package Containers.Doubly_Linked_Lists has the following
@@ -1286,6 +1297,16 @@
procedure Clear (Container : in out List);
+ function Element (Position : Cursor)
+ return Element_Type;
+
+ generic
+ with procedure Process (Element : in out Element_Type) is <>;
+ procedure Generic_Update (Position : in Cursor);
+
+ procedure Replace_Element (Position : in Cursor;
+ By : in Element_Type);
+
procedure Move (Target : in out List;
Source : in out List);
@@ -1308,10 +1329,10 @@
Position : out Cursor;
Count : in Size_Type := 1);
- procedure Insert_Space (Container : in out List;
- Before : in Cursor;
- Position : out Cursor;
- Count : in Size_Type := 1);
+ procedure Insert (Container : in out List;
+ Before : in Cursor;
+ Position : out Cursor;
+ Count : in Size_Type := 1);
procedure Delete (Container : in out List;
Position : in out Cursor;
@@ -1370,16 +1391,6 @@
function Last_Element (Container : List)
return Element_Type;
- function Element (Position : Cursor)
- return Element_Type;
-
- generic
- with procedure Process (Element : in out Element_Type) is <>;
- procedure Generic_Update (Position : in Cursor);
-
- procedure Replace_Element (Position : in Cursor;
- By : in Element_Type);
-
function Is_In (Item : Element_Type;
Container : List) return Boolean;
@@ -1457,6 +1468,33 @@
Clear removes all the nodes in Container, and sets the length to 0. Any
exceptions raised during deallocation of storage are propagated.
+function Element (Position : Cursor) return Element_Type;
+
+Returns the element stored on the node designated by Cursor. If
+Position equals No_Element, then Constraint_Error is propagated.
+
+generic
+ with procedure Process (Element : in out Element_Type) is <>;
+procedure Generic_Update (Position : in Cursor);
+
+If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
+Generic_Update invokes the generic actual procedure bound to Process
+with the element on node designated by Position as the argument.
+
+If Element_Type is unconstrained and definite, then the Element parameter
+shall be unconstrained.
+
+AARM Note: This means that the elements cannot be aliased nor directly
+allocated from the heap; it must be possible to change the discriminants
+of the element in place.
+
+procedure Replace_Element (Position : Cursor;
+ By : Element_Type);
+
+Assigns the value By to the element stored on the node designated by
+Position. If Position equals No_Element, then Constraint_Error is
+propagated.
+
procedure Move (Target : in out List;
Source : in out List);
@@ -1494,17 +1532,18 @@
newly-inserted node. Any exceptions raised during allocation of
internal storage are propagated, and Container is not modified.
-procedure Insert_Space (Container : in out List;
- Before : in Cursor;
- Position : out Cursor;
- Count : in Size_Type := 1);
+procedure Insert (Container : in out List;
+ Before : in Cursor;
+ Position : out Cursor;
+ Count : in Size_Type := 1);
-Insert_Space allocates Count new nodes whose elements are empty, and
-inserts them prior to the node designated by Before. If
-Before equals No_Element, the new node is inserted immediately
-following the last node (if any). Position designates the
-first newly-inserted node. Any exceptions raised during allocation of
-internal storage are propagated, and Container is not modified.
+Allocates Count new nodes with elements initialized with any implicit initial
+values for any part (as for an object_declaration with no initialization
+expression - see 3.3.1), and inserts them prior to the node designated by
+Before. If Before equals No_Element, the new node is inserted immediately
+following the last node (if any). Position designates the first newly-inserted
+node. Any exceptions raised during allocation of internal storage are
+propagated, and Container is not modified.
procedure Delete (Container : in out List;
Position : in out Cursor;
@@ -1548,15 +1587,15 @@
with function "<" (Left, Right : Element_Type) return Boolean is <>;
procedure Generic_Sort (Container : in out List);
-Reorders the nodes of Container such that the elements are sorted per the
-order specified as the generic formal less-than operator. The sort must be
-stable. Any exceptions raised during evalution of less-than are propagated,
-immediately terminating the sort operation.
+Reorders the nodes of Container such that the elements are
+sorted smallest first as determined by the generic formal "<" operator
+provided. The sort must be stable. Any exceptions raised during evalution of
+"<" are propagated.
AARM Notes
Unlike array sorts, we do require stable sorts here. That's because
-algorithms in the merge sort family (as described byt Knuth) can be both
-fast and stable. That's because we can use the extra memory as offered by
+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,
@@ -1570,14 +1609,13 @@
If Source denotes the same object as Target, the operation has no
effect. Otherwise this operation reorders nodes such that they are
-removed from Source and moved to Target. Target and Source are
-assumed to be sorted in the order specified as the generic formal. The
-nodes in Source containing elements that are less than elements in
-Target are spliced in before the elements already in Target. The
-nodes in Source container elements that are equal to or greater than
-elements in Target are spliced in after the elements already in
-Target. Any exceptions raised during evaluation of less-than are
-propagated, immediately terminating the merge operation.
+removed from Source and moved to Target. Target and Source are assumed to be
+sorted smallest first as determined by the generic formal "<" operator. The
+nodes in Source containing elements that are less than elements in Target are
+spliced in before the elements already in Target. The nodes in Source container
+elements that are equal to or greater than elements in Target are spliced in
+after the elements already in Target. Any exceptions raised during evaluation
+of "<" are propagated, immediately terminating the merge operation.
procedure Reverse_List (Container : in out List);
@@ -1641,44 +1679,6 @@
If Container is empty, then Constraint_Error is propagated. Otherwise,
it returns Element (Last (Container)).
-function Element (Position : Cursor) return Element_Type;
-
-Returns the element stored on the node designated by Cursor. If
-Position equals No_Element, then Constraint_Error is propagated.
-
-generic
- with procedure Process (Element : in out Element_Type) is <>;
-procedure Generic_Update (Position : in Cursor);
-
-If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
-Generic_Update invokes the generic actual procedure bound to Process
-with the element on node designated by Position as the argument.
-
-If Element_Type is unconstrained and definite, then the Element parameter
-shall be unconstrained.
-
-AARM Note: This means that the elements cannot be aliased nor directly
-allocated from the heap; it must be possible to change the discriminants
-of the element in place.
-
-The element designated by Position is not an empty element after successful
-completion of this operation.
-
-AARM Note: Since reading an empty element is a bounded error, attempting to
-use this procedure to replace empty elements may fail. Use Replace_Element
-to do that reliably.
-
-procedure Replace_Element (Position : Cursor;
- By : Element_Type);
-
-Assigns the value By to the element stored on the node designated by
-Position. If Position equals No_Element, then Constraint_Error is
-propagated. The element designated by Position is not an empty element after
-successful completion of this operation.
-
-AARM Note: Replace_Element and Generic_Update are only ways that an element
-can change from empty to non-empty.
-
function Is_In (Item : Element_Type;
Container : List) return Boolean;
@@ -1734,17 +1734,15 @@
function Next (Position : Cursor) return Cursor;
-Returns a cursor that designates the successor of the node designated by
-Position. If Position equals No_Element, then Next returns the value
-No_Element. If Position designates the last node of the container,
-then Next returns No_Element.
+If Position equals No_Element or designates the last node of the container,
+then Next returns the value No_Element. Otherwise, returns a cursor that
+designates the successor of the node designated by Position.
function Previous (Position : Cursor) return Cursor;
-Returns a cursor that designates the predecessor of the node designated
-by Position. If Position equals No_Element, then Previous returns the
-value No_Element. If Position designates the first node of the
-container, then Previous returns No_Element.
+If Position equals No_Element or designates the first node of the container,
+then Previous returns the value No_Element. Otherwise, returns a cursor that
+designates the predecessor of the node designated by Position.
The procedure Next is equivalent to Position := Next (Position).
@@ -1754,7 +1752,7 @@
Returns True if Position designates an element, and returns False otherwise.
-AARM Note: To Be Honset: This function is may not detect cursors that
+AARM Note: To Be Honest: This function is may not detect cursors that
designate deleted elements; such cursors are invalid (see below) and any
use of them (including in this routine) is erroneous.
@@ -1773,27 +1771,6 @@
Iterates over the nodes in Container as per Generic_Iteration, except
that elements are traversed in reverse order.
-Bounded (Run-Time) Errors
-
-Reading the value of an empty element by calling Element, Generic_Update,
-Generic_Sort, Generic_Merge, "=", Find, Reverse_Find, Generic_Find,
-Generic_Reverse_Find, Generic_Iteration, or Generic_Reverse_Iteration
-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.
-
-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
-if the type has if the type has default initial value(s).
-
-Assignment and streaming of empty elements are NOT bounded errors.
-This is consistent with regular composite types, for which assignment and
-streaming of uninitialized components do not cause a bounded error, but reading
-the uninitialized component does cause a bounded error.
-
-There are other operations which are defined in terms of the operations listed
-above.
-End AARM Notes.
-
Erroneous Execution
A Cursor value is *invalid* if any of the following have occurred since it was
@@ -1826,10 +1803,10 @@
Implementation Advice
-Containers.Doubly_Linked_Lists should be implemented similarly to a linked list.
-In particular, the time taken by Element, Insert with Count=1, and Delete with
-Count=1 should take time no worse than roughly proportional to the log (base 2)
-of the length of the list.
+Containers.Doubly_Linked_Lists should be implemented similarly to a linked
+list. In particular, if *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 N).
AARM Note
We do not mean to overly constrain implementation stratgies here. However, it
@@ -1840,10 +1817,9 @@
proportionality constant and caching effects are likely to be larger than the
log factor, and we don't want to discourage innovative implementations.
-A call on an instantiation of Containers.Doubly_Linked_Lists.Generic_Sort
-should take no worse than a time proportional to the square of the number of
-items in the list, and on average a time better than proportional to the
-square of the number of items in the list.
+The worst-case time complexity of a call on an instantiation of
+Containers.Doubly_Linked_Lists.Generic_Sort should be O(N**2), and
+the average time complexity should be better than O(N**2).
AARM Note
In other words, we're requiring the use of a better than O(N**2) sorting
@@ -1903,6 +1879,16 @@
procedure Clear (Container : in out Map);
+ function Element (Position : Cursor)
+ return Element_Type;
+
+ generic
+ with procedure Process (Element : in out Element_Type) is <>;
+ procedure Generic_Update (Position : in Cursor);
+
+ procedure Replace_Element (Position : in Cursor;
+ By : in Element_Type);
+
procedure Move (Target : in out Map;
Source : in out Map);
@@ -1966,16 +1952,6 @@
Right : Cursor)
return Boolean;
- function Element (Position : Cursor)
- return Element_Type;
-
- generic
- with procedure Process (Element : in out Element_Type) is <>;
- procedure Generic_Update (Position : in Cursor);
-
- procedure Replace_Element (Position : in Cursor;
- By : in Element_Type);
-
generic
with procedure Process (Position : in Cursor) is <>;
procedure Generic_Iteration (Container : in Map);
@@ -1986,31 +1962,62 @@
end Ada.Containers.Hashed_Maps;
-A object of type Map contains a hash table, which is used to provide
-direct access to elements. The *size* of an object of type Map is the
-number of hash table entries it contains. The *length* of an object of type Map
+An object of type Map contains an expandable hash table, which is used to
+provide direct access to elements. The *size* of an object of type Map is the
+maximum number of elements that can be inserted into the hash table prior to it
+being automatically expanded ("resized"). The *length* of an object of type Map
object is the number of elements it contains. If an object of type Map is not
otherwise initialized, it will be initialized with a length of 0.
-AARM Note
+A map contains pairs of keys and elements, called a *node*. Map cursors
+designate nodes, but also can be thought of as designating an element (the
+element contained in the node) for consistency with the other containers.
+
+
+AARM Notes
The expected implementation for a Map uses a hash table which is grown when
it is too small, with linked lists hanging off of each bucket.
Note that in that implementation a cursor needs a back pointer to the Map
-object to implement iteration; that could either be in the nodes, or in the
-cursor object.
+object to implement iteration; that could either be in the nodes, or
+in the cursor object. To provide an average O(1) access time, size would
+typically equal the number of buckets in such an implementation, so
+hat the average bucket linked list length would be no more than 1.0.
+
+There is no defined relationship between elements in a map. Typically,
+iteration will return elements in the order that they are hashed in.
+End AARM Notes
Function Hash is expected to return the same result value each time it is
called with a particular key value. For any two key values for which
Is_Equal_Key returns True, Hash should return the same result 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 Hash,
+is unspecified.
-AARM Note
-There is no defined relationship between nodes in a map. Typically, iteration
-will return nodes in the order that they are hashed in.
+AARM Notes
+The implementation is not required to protect against Hash raising an exception,
+or returning random numbers, or any other "bad" behavior. It's not practical to
+do so, and a broken Hash function makes the container unusable.
+
+The implementation can call Hash whenever it is needed; we don't want to
+specify how often that happens. The result must remain the same (this is
+logically a pure function), or the behavior is unspecified.
+End AARM Notes
+
+Function Is_Equal_Key is expected to return the same result value each time
+it is called with a particular pair of key values. If Is_Equal_Key
+behaves in some other manner, the behavior of this package is unspecified.
+Which subprograms of this package call Is_Equal_Key, and how many times they
+call Is_Equal_Key, is unspecified.
-A map container may contain *empty elements*. Empty elements do not have a
-defined value.
+AARM Notes
+As with Hash, the implementation is not required to protect against Is_Equal_Key
+raising an exception or returning random results. Similarly, the implementation
+can call Is_Equal_Key whenever it is needed. The result must remain the same
+(this is logically a pure function), or the behavior is unspecified.
+End AARM Notes
+
Empty_Map represents the empty Map object. It has a length of 0. If an object
of type Map is not otherwise initialized, it will be initialized to the same
value as Empty_Map.
@@ -2035,9 +2042,32 @@
Clear removes all the elements from Map. The size of Map is not affected. Any
exceptions raised during deallocation of storage propagated.
+
+function Element (Position : Cursor) return Element_Type;
+
+If Position equals No_Element, then Constraint_Error is propagated.
+Otherwise, this operation returns the element designated by Position.
+
+generic
+ with procedure Process (Element : in out Element_Type) is <>;
+procedure Generic_Update (Position : in Cursor);
+
+If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
+Generic_Update invokes the generic actual procedure bound to Process
+with the element designated by Position as the argument.
+
+procedure Replace_Element (Position : in Cursor;
+ By : in Element_Type);
+
+If Position equals No_Element, then Constraint_Error is propagated.
+Otherwise this operation assigns By to the element of the node designated by
+Position.
+
+
procedure Move (Target : in out Map;
Source : in out Map);
+If Target denotes the same object as Source, then this operation has no effect.
If the length of Target is greater than 0, then Move raises Constraint_Error.
Otherwise, the internal hash table of Target is deallocated; then the internal
hash table is removed from Source and moved to Target. Source has size 0 after
@@ -2050,20 +2080,25 @@
Success : out Boolean);
If Length (Container) equals Size (Container), then Insert calls Resize to
-resize Container to some larger value. Insert then calls Hash to compute the
-hash value of Key; any exceptions raised by Hash are propagated. It then uses
-Is_Equal_Key to check if Key is already present in Container; any exceptions
-raised by Is_Equal_Key are propagated. If a key matches, Success returns False
-and Position designates the node with the matching key. Otherwise, Insert
-allocates a new node initialized to Key and New_Item and adds the node to
-Container. Success returns True and Position designates the newly-inserted
-node. Any exceptions raised during allocation are propagated and Container is
-not modified.
+resize Container to some larger value. Insert then uses Hash and Is_Equal_Key
+to check if Key is already present in Container. If a key matches, Success
+returns False and Position designates the element with the matching key.
+Otherwise, Insert allocates a new node, initializes it to Key and New_Item, and
+adds it to Container. Success returns True and Position designates the
+newly-inserted node. Any exceptions raised during allocation are propagated
+and Container is not modified.
-AARM Note:
+AARM Notes:
Insert should only compare elements that hash to the same bucket in the hash
table.
+We specify when Resize is called to bound the overhead of resize operations
+(which are potentially expensive). Moreover, expansion can be predicted by
+comparing Size(Map) to Length(Map). Since we don't specify by how much the hash
+table is expanded, this only can be used to predict the next expansion, not
+later ones.
+End AARM Notes.
+
procedure Replace (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);
@@ -2071,8 +2106,7 @@
Replace inserts Key and New_Item as per Insert, with the difference that
if Key is already in the map, then this operation assigns New_Item to
the element associated with Key. Any exceptions raised during assignment
-are propagated. The element associated with Key is not an empty element after
-successful completion of this operation.
+are propagated.
procedure Insert (Container : in out Map;
Key : in Key_Type;
@@ -2080,41 +2114,36 @@
Success : out Boolean);
Inserts Key into Container as per Insert (Container, Key, New_Item,
-Position, Success), with the difference that an empty element is inserted.
+Position, Success), with the difference that an object initialized with any
+implicit initial values for any part (as for an object_declaration with no
+initialization expression - see 3.3.1) is inserted.
procedure Delete (Container : in out Map;
Key : in Key_Type);
-If Length (Container) equals 0, then this operation has no effect. Otherwise,
-it calls Hash to compute the hash value of Key; any exceptions raised by Hash
-are propagated. It then uses Is_Equal_Key to check if Key is present in
-Container; any exceptions raised by Is_Equal_Key are propagated. If Key matches
-the key of a node, Delete removes the node from the map and then deallocates
-the node. Any exceptions raised during deallocation of storage are propagated.
+It uses Hash and Is_Equal_Key to check if Key is present in Container. If Key
+matches the key of a node, Delete removes the node from the map and then
+deallocates the node.
-AARM Note:
+AARM Notes:
Delete should only compare elements that hash to the same bucket in the hash
-table.
+table. Delete should work on an empty map; nothing happens in that case.
procedure Delete (Container : in out Map;
Position : in out Cursor);
If Position equals No_Element, this operation has no effect.
-Otherwise, it calls Hash to compute the hash value of the key of the node
-designated by Position; any exceptions raised by Hash are propagated. Delete
-then removes the node from the map and deallocates the node. Any exceptions
-raised during deallocation of storage are propagated. Position is set to
-No_Element on return.
+Otherwise, Delete removes the node from the map and deallocates the node.
+Position is set to No_Element on return.
function Find (Container : Map;
Key : Key_Type) return Cursor;
If Length (Container) equals 0, then this function returns
-No_Element. Otherwise, it calls Hash to compute the hash value of Key;
-any exceptions raised by Hash are propagated. It then uses Is_Equal_Key
-to check if Key is present in Container; any exceptions raised by Is_Equal_Key
-are propagated. If Key is present in Container, it returns a cursor designating
-the node with the matching key; otherwise, it returns No_Element.
+No_Element. Otherwise, it uses Hash and Is_Equal_Key to check if Key is
+present in Container. If Key is present in Container, it
+returns a cursor designating the node with the matching key; otherwise, it
+returns No_Element.
AARM Note:
Find should only compare elements that hash to the same bucket in the hash
@@ -2130,13 +2159,18 @@
Size : in Size_Type);
If Size (Container) is equal to or greater than Size, this operation has no
-effect. Otherwise, it allocates a new hash table whose length is at least the
-value Size. If the allocation fails, the exception is propagated and Container
-is not modified. It then rehashes the nodes in Container onto the new hash
-table. Any exception raised by Hash is propagated and the nodes that were moved
-onto the new hash table are lost. It replaces the old hash table with the new
-hash table, and then deallocates the old hash table. Any exceptions raised
-during deallocation are propagated.
+effect. Otherwise, it allocates a new hash table such that the length of the
+resulting map can become at least the value Size without requiring an
+additional Resize operation. If the allocation fails, the exception is
+propagated and Container is not modified. It 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.
+
+AARM Note: This routine is used to preallocate the internal hash table to the
+specified size 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.
function First (Container : Map) return Cursor;
@@ -2173,14 +2207,14 @@
Returns True if Position designates an element, and returns False otherwise.
-AARM Note: To Be Honset: This function is may not detect cursors that
+AARM Note: To Be Honest: This function is may not detect cursors that
designate deleted elements; such cursors are invalid (see below) and any
use of them (including in this routine) is erroneous.
function Key (Position : Cursor) return Key_Type;
If Position equals No_Element, then Constraint_Error is propagated.
-Otherwise, this operation returns the key component of node designated
+Otherwise, this operation returns the key component of the node designated
by Position.
@@ -2194,39 +2228,6 @@
equivalent to Is_Equal_Key (Left, Key (Right)).
-function Element (Position : Cursor) return Element_Type;
-
-If Position equals No_Element, then Constraint_Error is propagated.
-Otherwise, this operation returns the element component of the node
-designated by Position.
-
-generic
- with procedure Process (Element : in out Element_Type) is <>;
-procedure Generic_Update (Position : in Cursor);
-
-If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
-Generic_Update invokes the generic actual procedure bound to Process
-with the element on node designated by Position as the argument.
-
-The element designated by Position is not an empty element after successful
-completion of this operation.
-
-AARM Note: Since reading an empty element is a bounded error, attempting to
-use this procedure to replace empty elements may fail. Use Replace_Element
-to do that reliably.
-
-procedure Replace_Element (Position : in Cursor;
- By : in Element_Type);
-
-If Position equals No_Element, then Constraint_Error is propagated.
-Otherwise this operation assigns By to the element on the node designed by
-Position. The element designated by Position is not an empty element after
-successful completion of this operation.
-
-AARM Note: Replace, Replace_Element, and Generic_Update are only ways that an
-element can change from empty to non-empty.
-
-
generic
with procedure Process (Position : in Cursor) is <>;
procedure Generic_Iteration (Container : in Map);
@@ -2255,26 +2256,6 @@
be dropped if AI-344 or some other solution to nested controlled types is
adopted.
-Bounded (Run-Time) Errors
-
-Reading the value of an empty element by calling Element, Generic_Update,
-"=", or Generic_Iteration 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.
-
-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
-if the type has if the type has default initial value(s).
-
-Assignment and streaming of empty elements are NOT bounded errors.
-This is consistent with regular composite types, for which assignment and
-streaming of uninitialized components do not cause a bounded error, but reading
-the uninitialized component does cause a bounded error.
-
-There are other operations which are defined in terms of the operations listed
-above.
-End AARM Notes.
-
Erroneous Execution
A Cursor value is *invalid* if any of the following have occurred since it was
@@ -2307,18 +2288,17 @@
Implementation Advice
-The time taken by Insert and Find should take time on average
-roughly proportional to the log (base 2) of the length of the map.
+If *N* is the length of a map, the average time complexity of Element,
+Insert, and Find should be O(log N).
AARM Note
We do not mean to overly constrain implementation stratgies here. However, it
is important for portability that the performance of large containers has
-roughly the same factors on different implementations. If a program is moved
-to an implementation that take time proportional to the length of the map
-to find elements, that program could be unusable when the maps are large.
-We allow O(log N) access because the proportionality constant and caching
-*effects are likely to be larger than the log factor, and we don't want to
-discourage innovative implementations.
+roughly the same factors on different implementations. If a program is moved to
+an implementation for which Find is O(N), that program could be unusable when
+the maps are large. We allow O(log N) access because the proportionality
+constant and caching *effects are likely to be larger than the log factor, and
+we don't want to discourage innovative implementations.
A.17.5 The Package Containers.Ordered_Sets
@@ -2356,20 +2336,18 @@
function "=" (Left, Right : Set) return Boolean;
- function "<" (Left, Right : Set) return Boolean;
-
- function "<=" (Left, Right : Set) return Boolean;
-
- function ">" (Left, Right : Set) return Boolean;
-
- function ">=" (Left, Right : Set) return Boolean;
-
function Length (Container : Set) return Size_Type;
function Is_Empty (Container : Set) return Boolean;
procedure Clear (Container : in out Set);
+ function Element (Position : Cursor) return Element_Type;
+
+ generic
+ with procedure Process (Element : in out Element_Type) is <>;
+ procedure Generic_Update (Position : in Cursor);
+
procedure Move (Target : in out Set;
Source : in out Set);
@@ -2384,9 +2362,6 @@
procedure Delete (Container : in out Set;
Position : in out Cursor);
- procedure Delete_Sans_Increment (Container : in out Set;
- Position : in out Cursor);
-
procedure Delete_First (Container : in out Set);
procedure Delete_Last (Container : in out Set);
@@ -2394,9 +2369,6 @@
procedure Union (Target : in out Set;
Source : in Set);
- procedure Union (Target : in out Set;
- Left, Right : in Set);
-
function Union (Left, Right : Set) return Set;
function "or" (Left, Right : Set) return Set renames Union;
@@ -2404,9 +2376,6 @@
procedure Intersection (Target : in out Set;
Source : in Set);
- procedure Intersection (Target : in out Set;
- Left, Right : in Set);
-
function Intersection (Left, Right : Set) return Set;
function "and" (Left, Right : Set) return Set renames Intersection;
@@ -2414,9 +2383,6 @@
procedure Difference (Target : in out Set;
Source : in Set);
- procedure Difference (Target : in out Set;
- Left, Right : in Set);
-
function Difference (Left, Right : Set) return Set;
function "-" (Left, Right : Set) return Set renames Difference;
@@ -2424,9 +2390,6 @@
procedure Symmetric_Difference (Target : in out Set;
Source : in Set);
- procedure Symmetric_Difference (Target : in out Set;
- Left, Right : in Set);
-
function Symmetric_Difference (Left, Right : Set) return Set;
function "xor" (Left, Right : Set) return Set renames
@@ -2482,12 +2445,6 @@
function ">" (Left : Element_Type; Right : Cursor)
return Boolean;
- function Element (Position : Cursor) return Element_Type;
-
- generic
- with procedure Process (Element : in out Element_Type) is <>;
- procedure Generic_Update (Position : in Cursor);
-
generic
with procedure Process (Position : in Cursor) is <>;
procedure Generic_Iteration (Container : in Set);
@@ -2554,6 +2511,29 @@
end Ada.Containers.Ordered_Sets;
+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 should also return True. If A < B
+returns True, then B < A should return False. 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 the functions are called, is
+unspecified.
+
+Two elements are *equivalent* if the function "=" returns True when called
+with the elements as parameters.
+
+AARM Notes
+The implementation is not required to protect against "<" or "=" 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
+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.
+End AARM Notes
+
+
Empty_Set represents the empty ordered set. If an object of type Set is
not otherwise initialized, it will be initialized to the same value as
Empty_Set.
@@ -2572,38 +2552,31 @@
corresponding pair of elements compare False, the function returns
False. Otherwise if all corresponding elements compare True, the
function returns True.
-
-function "<" (Left, Right : Set) return Boolean;
-If Left denotes the same object as Right, then the function returns
-False. Otherwise, it compares elements in sequential order using the
-generic formal less-than operator for elements. Any exception raised
-during evaluation of less-than is propagated. If an element in Left
-compares less than a corresponding element in Right, the function
-returns True. If there are no more elements in Left, then if there are
-more elements in Right, then the function returns True; otherwise if
-there no more elements in Right, then it returns False. If there are
-more elements in Left but none remaining in Right, then the function
-returns False.
+The function Length returns the number of elements in Container.
-The function "<=" is equivalent to not (Left > Right).
+The function Is_Empty is equivalent to Length (Container) = 0.
-The function ">" is equivalent to Right < Left.
+Clear removes all the elements in Set, and sets the length to 0.
-The function ">=" is equivalent to not (Left < Right).
+function Element (Position : Cursor) return Element_Type;
-The function Length returns the number of elements in Container.
+If Position equals No_Element, then Constraint_Error is propagated.
+Otherwise, it returns the element designated by Position.
-The function Is_Empty is equivalent to Length (Container) = 0.
+generic
+ with procedure Process (Element : in out Element_Type) is <>;
+procedure Generic_Update (Position : in Cursor);
-Clear removes all the nodes in Set, and sets the length to 0. Any
-exceptions raised during deallocation of storage are propagated.
+If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
+Generic_Update invokes the generic actual procedure bound to Process
+with the element designated by Position as the argument.
procedure Move (Target : in out Set;
Source : in out Set);
If the length of Target is greater than 0, then Move raises
-Constraint_Error. Otherwise, the internal nodes of Source are removed and
+Constraint_Error. Otherwise, the elements are removed from Source and
moved to Target. The length of Source is 0 after a sucessful call to Move.
@@ -2616,9 +2589,9 @@
formal less-than operator for elements. Any exceptions raised by the
less-than operator are propagated. If an element equivalent (see below)
to New_Item is already in Container, Success is False and Position
-designates the node containing the element. Otherwise, it allocates a
-new node whose element is initialized to New_Item. Success returns True
-and Position designates the newly-inserted node. Any exceptions raised
+designates the element. Otherwise, it allocates a
+new element which is initialized to New_Item. Success returns True
+and Position designates the newly-inserted element. Any exceptions raised
during allocation are propagated and Container is not modified.
The equality operator for elements is not used by this operation.
@@ -2632,53 +2605,38 @@
Delete searches Container for an element equivalent to Item, using the
generic formal less-than operator for elements. Any exceptions raised by
less-than are propagated. If there is an element in Container equivalent
-to Item, the node containing the element is removed from Container. Any
-exceptions raised during deallocation of storage (if any) are propagated.
+to Item, the element is removed from Container.
-AARM Note: The node may be deallocated now, or it may be saved and reused
-later.
+AARM Note: The internal node containing the element may be deallocated now,
+or it may be saved and reused later.
procedure Delete (Container : in out Set;
Position : in out Cursor);
If Position equals No_Element, the operation has no effect. Otherwise, Delete
-removes the node designated by Position from Container. Any exception raised
-during deallocation of storage (if any) is propagated.
-The cursor value returned designates the successor of the node deleted.
-
-
-procedure Delete_Sans_Increment (Container : in out Set;
- Position : in out Cursor);
-
-Equivalent to Delete (Container, Position), with the difference that the
-cursor value returned equals No_Element.
+removes the element designated by Position from Container. Position is set to
+No_Element on return.
procedure Delete_First (Container : in out Set);
-If Container is empty, the operation has no effect. Otherwise the node
-designated by First (Container) is removed from Container. Any exception
-raised during deallocation of storage (if any) is propagated.
+If Container is empty, the operation has no effect. Otherwise the element
+designated by First (Container) is removed from Container.
procedure Delete_Last (Container : in out Set);
-If Container is empty, the operation has no effect. Otherwise the node
-designated by Last (Container) is removed from Container. Any exception
-raised during deallocation of storage (if any) is propagated.
+If Container is empty, the operation has no effect. Otherwise the element
+designated by Last (Container) is removed from Container.
procedure Union (Target : in out Set;
Source : in Set);
-If Target denotes the same object as Source, the operation has no
-effect. Otherwise, the elements of Source that are not equivalent to
-items already in Target are inserted into Target.
+The elements of Source that are not equivalent to items already in Target are
+inserted into Target.
+AARM Note: If the objects are the same, the result is the same as the
+original object. The implementation needs to take care so that aliasing effects
+do not make the result trash; Union (S, S); must work.
-procedure Union (Target : in out Set;
- Left, Right : in Set);
-
-Equivalent to Target := Union (Left, Right).
-
-
function Union (Left, Right : Set) return Set;
Returns a set comprising all of the elements of Left, and the elements
@@ -2687,18 +2645,15 @@
procedure Intersection (Target : in out Set;
Source : in Set);
-
-If Target denotes the same object as Source, the operation has no
-effect. Otherwise, it deletes all the elements of Target that are
-not equivalent to the corresponding elements of Source.
+All the elements of Target that are not equivalent to the corresponding
+elements of Source are deleted from Target.
-procedure Intersection (Target : in out Set;
- Left, Right : in Set);
+AARM Note: If the objects are the same, the result is the same as the
+original object. The implementation needs to take care so that aliasing effects
+do not make the result trash; Intersection (S, S); must work.
-Equivalent to Target := Intersection (Left, Right).
-
function Intersection (Left, Right : Set) return Set;
Returns a set comprising all the elements of Left that are equivalent to
@@ -2713,12 +2668,6 @@
are equivalent to elements of Source.
-procedure Difference (Target : in out Set;
- Left, Right : in Set);
-
-Equivalent to Target := Difference (Left, Right).
-
-
function Difference (Left, Right : Set) return Set;
Returns a set comprising the elements of Left that are not equivalent to
@@ -2735,12 +2684,6 @@
Target.
-procedure Symmetric_Difference (Target : in out Set;
- Left, Right : in Set);
-
-Equivalent to Target := Symmetric_Difference (Left, Right).
-
-
function Symmetric_Difference (Left, Right : Set) return Set;
Returns a set comprising the elements of Left that are not equivalent to
@@ -2752,9 +2695,7 @@
Container : Set)
return Boolean;
-If Item denotes the same object as Container, then Is_Subset returns
-True. If Length (Item) is greater than Length (Container), then it
-returns False. If an element of Item is not equivalent to an element of
+If an element of Item is not equivalent to some element of
Container, the function returns False. Otherwise it returns True.
@@ -2762,50 +2703,48 @@
Container : Set)
return Boolean;
-If an element of Item is equivalent to an element of Container, then
+If an element of Item is equivalent to some element of Container, then
Is_Disjoint returns False. Otherwise it returns True.
function Find (Container : Set;
Item : Element_Type) return Cursor;
-The Find operation searches for the element equivalent to Item, using
-the generic formal less-than operator for elements. Any exception
-raised by less-than is propagated. If it finds an equivalent element,
-it returns a cursor designating the node that contains the element.
-Otherwise it returns No_Element.
+The Find operation searches for the element equivalent to Item. If it finds
+an equivalent element, it returns a cursor designating the element. Otherwise
+it returns No_Element.
The function Is_In is equivalent to Find (Set, Item) /= No_Element.
function First (Container : Set) return Cursor;
-Returns a cursor that designates the node containing the smallest
-element. If Container is empty, it returns No_Element.
+Returns a cursor that designates the smallest element. If Container is empty,
+it returns No_Element.
function First_Element (Container : Set) return Element_Type;
If Container is empty, then Constraint_Error is propagated. Otherwise,
-it returns the element on the node designated by First (Container).
+it returns the element designated by First (Container).
function Last (Container : Set) return Cursor;
-Returns a cursor that designates the node containing the greatest
-element. If Container is empty, it returns No_Element.
+Returns a cursor that designates the greatest element. If Container is empty,
+it returns No_Element.
function Last_Element (Container : Set) return Element_Type;
-If Container is empty, then Constraint_Error is propagated. Otherwise,
-it returns the element on the node designated by Last (Container).
+If Container is empty, then Constraint_Error is propagated. Otherwise, it
+returns the element designated by Last (Container).
function Next (Position : Cursor) return Cursor;
If Position equals No_Element, then No_Element is returned. Otherwise
-it returns the successor of the node designated by Position.
+it returns the successor of the element designated by Position.
function Previous (Position : Cursor) return Cursor;
If Position equals No_Element, then No_Element is returned. Otherwise
-it returns the predecessor of the node designated by Position.
+it returns the predecessor of the element designated by Position.
The procedure Next is equivalent to Position := Next (Position).
@@ -2815,7 +2754,7 @@
Returns True if Position designates an element, and returns False otherwise.
-AARM Note: To Be Honset: This function is may not detect cursors that
+AARM Note: To Be Honest: This function might not detect cursors that
designate deleted elements; such cursors are invalid (see below) and any
use of them (including in this routine) is erroneous.
@@ -2837,30 +2776,17 @@
The function ">" (Left : Element_Type; Right : Cursor) is
equivalent to Element (Right) < Left.
-function Element (Position : Cursor) return Element_Type;
-
-If Position equals No_Element, then Constraint_Error is propagated.
-Otherwise, it returns the element on the node designated by Position.
-
generic
- with procedure Process (Element : in out Element_Type) is <>;
-procedure Generic_Update (Position : in Cursor);
-
-If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
-Generic_Update invokes the generic actual procedure bound to Process
-with the element on node designated by Position as the argument.
-
-generic
with procedure Process (Position : in Cursor) is <>;
procedure Generic_Iteration (Container : in Set);
-Invokes Process with a cursor that designates each node in Container.
+Invokes Process with a cursor that designates each element in Container.
generic
with procedure Process (Position : in Cursor) is <>;
procedure Generic_Reverse_Iteration (Container : in Set);
-Iterates over the nodes in Container as per Generic_Iteration, with the
+Iterates over the elements in Container as per Generic_Iteration, with the
difference that the nodes are traversed in reverse order.
The package Generic_Keys provides operations that allow set manipulation
@@ -2882,13 +2808,13 @@
the Generic_Keys generic formal relational operators for keys and
elements. Any exceptions raised by less-than are propagated. If an
element equivalent to Key is already in Container, Success is False and
-Position designates the node containing the element equivalent to Key.
-Otherwise, it allocates a new node and then calls Set_Key with the
-element of the node and Key as the parameters. Any exceptions raised
+Position designates the element equivalent to Key.
+Otherwise, it allocates a new element and then calls Set_Key with the
+element and Key as the parameters. Any exceptions raised
during allocation are propagated. If Set_Key raises an exception, Insert
-deallocates the node and then propagates the exception. Otherwise, it
-inserts the node into the Container. Success returns True and Position
-designates the newly-inserted node.
+deallocates the element and then propagates the exception. Otherwise, it
+inserts the element into the Container. Success returns True and Position
+designates the newly-inserted element.
Legality Rules
@@ -2920,7 +2846,7 @@
AARM Notes: The list above is intended to be exhaustive. In other cases, a
cursor value continues to designate its original element. For instance,
-cursor values survive the insertion and deletion of other nodes.
+cursor values survive the insertion and deletion of other elements.
While it is possible to check for these cases, in many cases the overhead
necessary to make the check is substantial in time or space. Implementations
@@ -2946,8 +2872,10 @@
Implementation Advice
-The time taken by Insert and Find should take time better than
-roughly proportional to the length of the set.
+If *N* is the length of a set, then:
+ * The worst-case time complexity of Insert and Find should be O((log N)**2)
+ or better;
+ * the worst-case time complexity of Element should be O(log N) or better.
AARM Note
A balanced (red-black) tree for keys has O(log N) worst-case performance. Note
@@ -2955,10 +2883,10 @@
We do not mean to overly constrain implementation stratgies here. However, it
is important for portability that the performance of large containers has
roughly the same factors on different implementations. If a program is moved
-to an implementation that takes O(N log N) to find elements, that program could
-be unusable when the sets are large. We allow <O(N) access because the
-proportionality constant and caching effects are likely to be larger than the
-log factor, and we don't want to discourage innovative implementations.
+to an implementation that takes O(N) to find elements, that program could
+be unusable when the sets are large. We allow the extra log N factors because
+the proportionality constant and caching effects are likely to be larger than
+the log factor, and we don't want to discourage innovative implementations.
A.17.6 The Package Containers.Indefinite_Vectors
@@ -2996,6 +2924,22 @@
* The generic formal Element_Type is indefinite.
+ * The procedure with the profile:
+ procedure Insert (Container : in out List;
+ Before : in Cursor;
+ Position : out Cursor;
+ Count : in Size_Type := 1);
+ is omitted.
+
+AARM Note: This procedure is omitted because there is no way to create a
+default-initialized object of an indefinite type. We considered having this
+routine insert an empty element similar to the empty elements of a vector,
+but rejected this possibility because the semantics are fairly complex and
+very different from the existing case. That would make it more error-prone
+to convert a container from a definite type to an indefinite type; by
+omitting the routine completely, any problems will be diagnosed by the
+compiler.
+
* The Element parameter of formal subprogram Process of Generic_Update
may be constrained even if Element_Type is unconstrained.
@@ -3017,6 +2961,22 @@
* The generic formal Element_Type is indefinite.
+ * The procedure with the profile:
+ procedure Insert (Container : in out Map;
+ Key : in Key_Type;
+ Position : out Cursor;
+ Success : out Boolean);
+ is omitted.
+
+AARM Note: This procedure is omitted because there is no way to create a
+default-initialized object of an indefinite type. We considered having this
+routine insert an empty element similar to the empty elements of a vector,
+but rejected this possibility because the semantics are fairly complex and
+very different from the existing case. That would make it more error-prone
+to convert a container from a definite type to an indefinite type; by
+omitting the routine completely, any problems will be diagnosed by the
+compiler.
+
* The Element parameter of formal subprogram Process of Generic_Update
may be constrained even if Element_Type is unconstrained.
@@ -3062,8 +3022,8 @@
procedure Ada.Containers.Generic_Array_Sort (Container : in out Array_Type);
Reorders the elements of Container such that the elements are
-sorted per the order specified as the generic formal less-than operator.
-Any exceptions raised during evalution of less-than are propagated.
+sorted smallest first as determined by the generic formal less-than operator
+provided. Any exceptions raised during evalution of less-than are propagated.
AARM Notes
This implies swapping the elements, usually including an intermediate copy.
@@ -3091,16 +3051,15 @@
(Container : in out Array_Type);
Reorders the elements of Container such that the elements are
-sorted per the order specified as the generic formal less-than operator.
-Any exceptions raised during evalution of less-than are propagated.
+sorted smallest first as determined by the generic formal less-than operator
+provided. Any exceptions raised during evalution of less-than are propagated.
Implementation Advice
-A call on an instantiation of Containers.Generic_Array_Sort or
-Containers.Generic_Constrained_Array_Sort should take no worse than a time
-proportional to the square of the number of items in the array, and
-on average a time better than proportional to the square of the number of
-items in the array.
+The worst-case time complexity of a call on an instantiation 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).
AARM Note
In other words, we're requiring the use of a sorting algorithm better than
Questions? Ask the ACAA Technical Agent