CVS difference for ais/ai-20302.txt
--- ais/ai-20302.txt 2004/09/04 00:48:21 1.9
+++ ais/ai-20302.txt 2004/10/05 22:49:23 1.10
@@ -1,4 +1,4 @@
-!standard A.17 04-08-31 AI95-00302-03/06
+!standard A.17 04-10-04 AI95-00302-03/07
!class amendment 04-01-14
!status work item 04-01-14
!status received 04-01-14
@@ -90,11 +90,11 @@
previous pointers, and thus supports both forward and reverse iteration.
All of the containers specify positions using a cursor,
-which is similar to an access type in that it designates an element. It
-is not (necessarily) implemented as an access type, so access to the element
-is through a selector function. Many cursor operations are common to all
-containers. Containers also support operations specific to that container;
-for instance, vectors also specify positions via an integer index subtype.
+which is similar to an access type in that it designates an element.
+Selector functions and procedures allow access to the element. Many cursor
+operations are common to all containers. Containers also support operations
+specific to that container; for instance, vectors also specify positions via an
+integer index subtype.
The associative containers order their elements by key. A map has an
explicit key type, but with a set the key is implicit in the element
@@ -155,7 +155,7 @@
with Ada.Containers;
function Ada.Strings.Unbounded.Hash (Key : Unbounded_String) return
Containers.Hash_Type;
-pragma Pure (Ada.Strings.Unbounded.Hash);
+pragma Preelaborate (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).
@@ -172,6 +172,10 @@
several child packages, which provide facilities for storing collections
of elements.
+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.
+
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.
@@ -212,7 +216,7 @@
Separate versions for definite and indefinite element types are provided, as
those for definite types can be implemented more efficiently.
-Each container includes a *cursor*, which is a reference to an element within
+Each container includes a cursor, which is a reference to an element within
a container. Cursors generally remain valid as long as the container exists and
the element referenced is not deleted. Many operations on cursors are common to
all of the containers. This makes it possible to write generic algorithms that
@@ -268,9 +272,30 @@
The use of controlled type also brings up the possibility of failure of
finalization (and thus deallocation) of an element. This is a "serious bug",
as AI-179 puts it, so we don't try to specify what happens in that case.
-The implementation should propagate the exception, and should not damage
-the container (so that it can continue to be used without further error).
+The implementation should propagate the exception.
+
+It is expected that exceptions propagated from these operations do not
+damage containers. That is, if Storage_Error is propagated because of an
+allocation failure, or Constraint_Error is propagated by the assignment of
+elements, the container can continue to be used without further exceptions.
+The intent is that it should be possible to recover from errors without
+losing data. We don't try to state this formally in most cases, because it is
+hard to define precisely what is and is not allowed behavior.
+
+
+When this clause says that the behavior of something is unspecified, we
+really mean that any result of executing Ada code short of erroneous
+execution is allowed. We do not mean that memory not belonging to the
+parameters of the operation can be trashed. When we mean to allow erroneous
+behavior, we specifically say that execution is erroneous. All this means
+if the containers are written in Ada is that checks should not be suppressed
+or removed assuming some behavior of other code, and that the implementation
+should take care to avoid creating internal dangling accesses by assuming
+behavior from generic formals that can't be guaranteed. We don't
+try to say this normatively because it would be fairly complex, and
+implementers are unlikely to increase their support costs by fielding
+implementations that are unstable if given buggy hash functions, et. al.
End AARM Text
A.17.1 The Package Containers
@@ -345,15 +370,11 @@
package Ada.Containers.Vectors is
pragma Preelaborate (Vectors);
-
- pragma Assert (Index_Type'Base'First < Index_Type'First);
- AARM Note:
- This pragma insures that Last_Index is always able to return a valid
- value, even for an empty vector. It would not be able to this if
- Index_Type'Base'First = Index_Type'First, so this pragma serves as
- documentation of the requirement on Index_Type.
- End AARM Note.
+ subtype Extended_Index is
+ Index_Type'Base range Index_Type'First-1 .. Index_Type'Last +
+ Boolean'Pos (Index_Type'Base'Last > Index_Type'Last);
+ No_Index : constant Extended_Index := Extended_Index'First;
subtype Index_Subtype is Index_Type;
@@ -385,8 +406,8 @@
function Capacity (Container : Vector) return Count_Type;
- procedure Set_Capacity (Container : in out Vector;
- Capacity : in Count_Type);
+ procedure Reserve_Capacity (Container : in out Vector;
+ Capacity : in Count_Type);
function Length (Container : Vector) return Count_Type;
@@ -395,19 +416,19 @@
procedure Clear (Container : in out Vector);
function To_Cursor (Container : Vector;
- Index : Index_Type'Base) return Cursor;
+ Index : Extended_Index) return Cursor;
- function To_Index (Position : Cursor) return Index_Type'Base;
+ function To_Index (Position : Cursor) return Extended_Index;
function Element (Container : Vector;
- Index : Index_Type'Base)
+ Index : Index_Type)
return Element_Type;
function Element (Position : Cursor) return Element_Type;
procedure Query_Element
(Container : in Vector;
- Index : in Index_Type'Base;
+ Index : in Index_Type;
Process : not null access procedure (Element : in Element_Type));
procedure Query_Element
@@ -416,7 +437,7 @@
procedure Update_Element
(Container : in Vector;
- Index : in Index_Type'Base;
+ Index : in Index_Type;
Process : not null access procedure (Element : in out Element_Type));
procedure Update_Element
@@ -424,7 +445,7 @@
Process : not null access procedure (Element : in out Element_Type));
procedure Replace_Element (Container : in Vector;
- Index : in Index_Type'Base;
+ Index : in Index_Type;
By : in Element_Type);
procedure Replace_Element (Position : in Cursor;
@@ -437,7 +458,7 @@
Source : in out Vector);
procedure Insert (Container : in out Vector;
- Before : in Index_Type'Base;
+ Before : in Extended_Index;
New_Item : in Vector);
procedure Insert (Container : in out Vector;
@@ -450,7 +471,7 @@
Position : out Cursor);
procedure Insert (Container : in out Vector;
- Before : in Index_Type'Base;
+ Before : in Extended_Index;
New_Item : in Element_Type;
Count : in Count_Type := 1);
@@ -480,7 +501,7 @@
Count : in Count_Type := 1);
procedure Insert_Space (Container : in out Vector;
- Before : in Index_Type'Base;
+ Before : in Extended_Index;
Count : in Count_Type := 1);
procedure Insert_Space (Container : in out Vector;
@@ -492,7 +513,7 @@
Length : in Count_Type);
procedure Delete (Container : in out Vector;
- Index : in Index_Type'Base;
+ Index : in Extended_Index;
Count : in Count_Type := 1);
procedure Delete (Container : in out Vector;
@@ -512,27 +533,27 @@
function First_Element (Container : Vector)
return Element_Type;
- function Last_Index (Container : Vector) return Index_Type'Base;
+ function Last_Index (Container : Vector) return Extended_Index;
function Last (Container : Vector) return Cursor;
function Last_Element (Container : Vector)
return Element_Type;
- procedure Swap_Elements (Container : in Vector;
- I, J : in Index_Type'Base);
+ procedure Swap (Container : in Vector;
+ I, J : in Index_Type);
- procedure Swap_Elements (I, J : in Cursor);
+ procedure Swap (I, J : in Cursor);
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
- procedure Generic_Sort (Container : in Vector'Class);
+ procedure Generic_Sort (Container : in Vector);
function Find_Index (Container : Vector;
Item : Element_Type;
- Index : Index_Type'Base := Index_Type'First)
- return Index_Type'Base;
+ Index : Index_Type := Index_Type'First)
+ return Extended_Index;
function Find (Container : Vector;
Item : Element_Type;
@@ -541,8 +562,8 @@
function Reverse_Find_Index (Container : Vector;
Item : Element_Type;
- Index : Index_Type'Base := Index_Type'Last)
- return Index_Type'Base;
+ Index : Index_Type := Index_Type'Last)
+ return Extended_Index;
function Reverse_Find (Container : Vector;
Item : Element_Type;
@@ -563,7 +584,7 @@
function Has_Element (Position : Cursor) return Boolean;
- procedure Iterate
+ procedure Iterate
(Container : in Vector;
Process : not null access procedure (Position : in Cursor));
@@ -588,6 +609,16 @@
Cursor is not otherwise initialized, it will be initialized to the same
value as No_Element.
+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.
+
+AARM Note: We require the existence of Index_Type'First - 1, so that No_Index
+and Last_Index of an empty vector is well-defined. We don't require the
+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).
+
function To_Vector (Length : Count_Type) return Vector;
Returns a vector with a length of Length. The vector is filled with empty
@@ -638,23 +669,22 @@
Returns the length of the internal array.
-procedure Set_Capacity (Container : in out Vector;
- Capacity : in Count_Type);
+procedure Reserve_Capacity (Container : in out Vector;
+ Capacity : in Count_Type);
-If Capacity < Length (Container), Constraint_Error is raised. Otherwise,
-Set_Capacity sets the capacity of Container to a value which is at least the
-value Capacity, expanding (or contracting) the internal array to hold at least
-Capacity elements. Expansion or contraction will require allocation, and
-possibly copying and deallocation of elements. Any exceptions raised by these
-operations are propagated, leaving the container with at least the original
-Length and elements.
+Reserve_Capacity sets the capacity of Container to a value which is at least the
+value Capacity and which is greater than the length of Container, expanding (or
+contracting) the internal array to hold at least Capacity elements. Expansion
+or contraction will require allocation, and possibly copying and deallocation
+of elements. Any exceptions raised by these operations are propagated, leaving
+the container with at least the original length and elements.
AARM Notes
Expanding the internal array can be done by allocating a new, longer array,
copying the elements, and deallocating the original array. This may raise
Storage_Error, or cause an exception from a controlled subprogram. We require
-that a failed Set_Capacity does not lose any elements if an exception occurs,
+that a failed Reserve_Capacity does not lose any elements if an exception occurs,
but we do not require a specific order of evaluations or copying.
This routine is used to preallocate the internal array to the specified
@@ -686,16 +716,16 @@
function To_Cursor (Container : Vector;
- Index : Index_Type'Base) return Cursor;
+ Index : Extended_Index) return Cursor;
If the value of Index is not in the range First_Index (Container) .. Last_Index
(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;
+function To_Index (Position : Cursor) return Extended_Index;
-If Position is No_Element, Constraint_Error is propagated. Otherwise, the
+If Position is No_Element, No_Index is returned. Otherwise, the
index (within its containing vector) of the element designated by Cursor is
returned.
@@ -708,7 +738,7 @@
function Element (Container : Vector;
- Index : Index_Type'Base)
+ Index : Index_Type)
return Element_Type;
If Index is not in the range First_Index (Container) .. Last_Index (Container),
@@ -723,7 +753,7 @@
procedure Query_Element
(Container : in Vector;
- Index : in Index_Type'Base;
+ Index : in Index_Type;
Process : not null access procedure (Element : in Element_Type));
If Index is not in the range First_Index (Container) .. Last_Index (Container),
@@ -741,7 +771,7 @@
procedure Update_Element
(Container : in Vector;
- Index : in Index_Type'Base;
+ 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),
@@ -752,9 +782,9 @@
If Element_Type is unconstrained and definite, then the Element parameter
of Process.all 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.
+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.
The element at position Index is not an empty element after successful
completion of this operation.
@@ -778,7 +808,7 @@
completion of this operation.
procedure Replace_Element (Container : in Vector;
- Index : in Index_Type'Base;
+ Index : in Index_Type;
By : in Element_Type);
If Index does not specify a value in the range First_Index (Container) ..
@@ -805,7 +835,7 @@
If Target denotes the same object as Source, then the operation has no
effect. Otherwise, Assign first calls Clear (Target), then
-Set_Capacity (Target, Length (Source)). It then assigns the active elements
+Reserve_Capacity (Target, Length (Source)). It then assigns the active elements
of Source to the corresponding positions in Target, and then sets the length
of Target to the length of Source. Any exception raised during element
assignment is propagated.
@@ -831,7 +861,7 @@
procedure Insert (Container : in out Vector;
- Before : in Index_Type'Base;
+ Before : in Extended_Index;
New_Item : in Vector);
If Length(New_Item) is 0, then Insert does nothing. Otherwise, it calculates
@@ -842,37 +872,47 @@
Constraint_Error is propagated.
If the current vector capacity is less than or equal to the new length,
-Set_Capacity (Container, NL) is called to increase the vector capacity. Then
+Reserve_Capacity (Container, NL) is called to increase the vector capacity. Then
Insert slides the elements in the range Before .. Last_Index (Container) up by
Length(New_Item) positions, and then copies the elements of New_Item to the
positions starting at Before. Any exception raised during the copying is
propagated.
-AARM Note
+AARM Note:
Moving the elements does not necessarily involve copying. Similarly, since
-Set_Capacity does not require the copying of elements, it does not need to be
+Reserve_Capacity does not require the copying of elements, it does not need to be
explicitly called (the implementation can combine the operations if it wishes
to). [Note to reviewers: I didn't want to duplicate the messy wording and notes
about exceptions not losing anything.]
+End AARM Note.
-
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Vector);
+If Before is not No_Element, and does not designate an element in Container,
+then Program_Error is propagated.
If Length(New_Item) is 0, then Insert does nothing.
If Before is No_Element, then is equivalent to Insert (Container,
Last_Index (Container) + 1), New_Item); otherwise is
equivalent to Insert (Container, To_Index (Before), New_Item);
+AARM Note: The check on Before checks that the cursor does not belong to some
+other Container. This check implies that a reference to the container is
+included in the cursor value. This wording is not meant to require detection of
+dangling cursors; such cursors are defined to be invalid, which means that
+execution is erroneous, and any result is allowed (including not raising an
+exception).
procedure Insert (Container : in out Vector;
Before : in Cursor;
New_Item : in Vector;
Position : out Cursor);
-If Length(New_Item) is 0, then Insert does nothing. Otherwise,
+If Before is not No_Element, and does not designate an element in Container,
+then Program_Error is propagated.
+If Length(New_Item) is 0, then Insert sets Position to Before. Otherwise,
create a temporary (call it Temp_Index) and set it to Last_Index (Container) + 1
if Before equals No_Element, and To_Index (Before) otherwise. Then
Insert (Container, Before, New_Item) is called, and finally
@@ -884,7 +924,7 @@
procedure Insert (Container : in out Vector;
- Before : in Index_Type'Base;
+ Before : in Extended_Index;
New_Item : in Element_Type;
Count : in Count_Type := 1);
@@ -936,7 +976,7 @@
procedure Insert_Space (Container : in out Vector;
- Before : in Index_Type'Base;
+ Before : in Extended_Index;
Count : in Count_Type := 1);
Equivalent to Insert (Container, Before, New_Item, Count), with the
@@ -948,6 +988,8 @@
Position : out Cursor;
Count : in Count_Type := 1);
+If Before is not No_Element, and does not designate an element in Container,
+then Program_Error is propagated.
If Length(New_Item) is 0, then Insert does nothing. Otherwise,
create a temporary (call it Temp_Index) and set it to
Last_Index (Container) + 1 if Before equals No_Element, and
@@ -959,13 +1001,14 @@
procedure Set_Length (Container : in out Vector;
Length : in Count_Type);
-Calls Set_Capacity (Container, Length), then sets the length of the Container
-to Length. If Length is greater than the original length of Container, the
-added elements are empty elements.
+If Length is larger than the capacity of Container, calls
+Reserve_Capacity (Container, Length), then sets the length of the
+Container to Length. If Length is greater than the original length of
+Container, the added elements are empty elements.
procedure Delete (Container : in out Vector;
- Index : in Index_Type'Base;
+ Index : in Extended_Index;
Count : in Count_Type := 1);
If Count is 0, the operation has no effect. If Index does not specify a
@@ -982,7 +1025,9 @@
Position : in out Cursor;
Count : in Count_Type := 1);
-If Count is 0, the operation has no effect. Otherwise is equivalent to
+If Position is No_Element, this operation has no effect.
+If Position does not designate an element in Container, then Program_Error is
+raised. If Count is 0, the operation has no effect. Otherwise is equivalent to
Delete (Container, To_Index (Position), Count).
procedure Delete_First (Container : in out Vector;
@@ -998,7 +1043,7 @@
Index_Type'Val(Index_Type'Pos(Last_Index(Container)) - Count + 1), Count).
-function First_Index (Container : Vector) return Index_Type'Base;
+function First_Index (Container : Vector) return Index_Type;
Returns the value Index_Type'First.
@@ -1015,9 +1060,9 @@
Equivalent to Element (Container, First_Index (Container)).
-function Last_Index (Container : Vector) return Index_Type'Base;
+function Last_Index (Container : Vector) return Extended_Index;
-If Container is empty, returns Index_Type'First - 1;
+If Container is empty, returns No_Index;
otherwise, returns the position of the last element in Container.
@@ -1032,24 +1077,25 @@
Equivalent to Element (Container, Last_Index (Container)).
-procedure Swap_Elements (Container : in Vector;
- I, J : in Index_Type'Base);
+procedure Swap (Container : in Vector;
+ I, J : in Index_Type);
If I or J does not specify a value in the range First_Index (Container) ..
Last_Index (Container), then Constraint_Error is propagated. Otherwise
-Swap_Elements exchanges the values of the elements at positions I and J.
+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_Elements (I, J : in Cursor);
+procedure Swap (I, J : in Cursor);
-If either I or J is No_Element, then Constraint_Error is propagated. Otherwise
-Swap_Elements exchanges the values of the elements designated by I and J.
+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_Elements, I designates the element value previously
+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.
@@ -1060,15 +1106,15 @@
generic
with function "<" (Left, Right : Element_Type) return Boolean is <>;
-procedure Generic_Sort (Container : in Vector'Class);
+procedure Generic_Sort (Container : in 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 evalution of "<" is propagated.
-AARM Notes
+AARM Notes:
This implies swapping the elements, usually including an intermediate copy.
-This means that the elements will usually be copied. (As with Swap_Elements,
+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 non-limited, this usually will not be a problem. Note that
there is Implementation Advice below that the implementation should use
@@ -1079,23 +1125,17 @@
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.
-
-If this operation calls primitive operations of Vector, it should take care
-that they are not dispatching - overridden routines will not necessarily have
-the required semantics. (Note that this routine is not defined in terms of
-any primitive routines.)
End AARM Notes
function Find_Index (Container : Vector;
Item : Element_Type;
- Index : Index_Type'Base := Index_Type'First)
- return Index_Type'Base;
+ Index : Index_Type := Index_Type'First)
+ return Extended_Index;
Searches the elements of Container for an element equal to Item,
-starting at position Index. If Index is less than Index_Type'First,
-then Constraint_Error is propagated. If there are no elements in the
+starting at position Index. If there are no elements in the
range Index .. Last_Index (Container) equal to Item, then Find_Index returns
-Last_Index (Container) + 1. Otherwise, it returns the index of the matching
+No_Index. Otherwise, it returns the index of the matching
element.
function Find (Container : Vector;
@@ -1103,6 +1143,8 @@
Position : Cursor := No_Element)
return Cursor;
+If Position is not No_Element, and does not designate an element in Container,
+then Program_Error is propagated.
Searches the elements of Container for an element equal to Item,
starting at the first element if Cursor equals No_Element, and at
the element designated by Cursor otherwise, and searching to the last
@@ -1112,14 +1154,14 @@
function Reverse_Find_Index (Container : Vector;
Item : Element_Type;
- Index : Index_Type'Base := Index_Type'Last)
- return Index_Type'Base;
+ Index : Index_Type := Index_Type'Last)
+ return Extended_Index;
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 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_Index returns Last_Index (Container) + 1.
+to Item, then Reverse_Find_Index returns No_Index.
Otherwise, it returns the index of the matching element.
function Reverse_Find (Container : Vector;
@@ -1127,6 +1169,8 @@
Position : Cursor := No_Element)
return Cursor;
+If Position is not No_Element, and does not designate an element in Container,
+then Program_Error is propagated.
Searches the elements of Container for an element equal to Item,
starting at the last element if Cursor equals No_Element, and at
the element designated by Cursor otherwise, and searching backwards to the
@@ -1136,7 +1180,7 @@
function Contains (Container : Vector;
- Item : Element_Type return Boolean;
+ Item : Element_Type) return Boolean;
Equivalent to Has_Element (Find (Container, Item)).
@@ -1173,7 +1217,25 @@
Invokes Process.all with a cursor that designates each element in Container, in
index order. Any exception raised by Process is propagated.
+Program_Error is propagated if:
+ * Process.all attempts to insert or delete elements from Container; or
+ * Process.all finalizes Container; or
+ * Process.all calls Move with Container as a parameter.
+AARM Note:
+This check takes place when the operations that insert or delete elements, etc.
+are called. There is no check needed if an attempt is made to insert or delete
+nothing (that is, Count = 0 or Length(Item) = 0).
+
+The check is easy to implement: each container needs a counter. The counter
+is incremented when Iterate is called, and decremented when Iterate completes.
+If the counter is nonzero when an operation that inserts or deletes is called,
+Finalize is called, or one of the other operations in the list occurs,
+Program_Error is raised.
+
+Swap and Generic_Sort are not included here, as they only copy elements.
+End AARM Notes.
+
procedure Reverse_Iterate
(Container : in Vector;
Process : not null access procedure (Position : in Cursor));
@@ -1260,9 +1322,12 @@
The result of "=" or Has_Element is unspecified if it is called with an
invalid cursor parameter. Execution is erroneous if any other subprogram
-declared in Containers.Vectors is called with an invalid cursor parameter, or
-if the cursor designates an element in a different vector object than the
-appropriate one specified in the call.
+declared in Containers.Vectors is called with an invalid cursor parameter.
+
+Execution also is erroneous if the called Process procedure of a call to
+Query_Element or Update_Element executes an operation that causes the Position
+cursor or To_Cursor of the Index parameter of Query_Element or Update_Element
+to become invalid or ambiguous.
AARM Notes: The list above (combined with the bounded error cases) is intended
to be exhaustive. In other cases, a cursor value continues to designate its
@@ -1314,6 +1379,16 @@
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
+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.
+
+AARM Note: This property is the main reason why only integer types (as opposed
+to any discrete type) are allowed as the index type of a vector. An enumeration
+or modular type would require a subtype in order to meet this requirement.
+
+
A.17.3 The Package Containers.Doubly_Linked_Lists
The language-defined package Containers.Doubly_Linked_Lists provides
@@ -1323,7 +1398,7 @@
A doubly-linked list container object manages a linked list of internal
storage nodes, each of which contains an element and pointers to the
next (successor) and previous (predecessor) internal nodes. A cursor
-is used to specify positions of particular storage nodes within a list.
+designates particular storage nodes (and thus elements) within a list.
Static Semantics
@@ -1344,7 +1419,6 @@
type Cursor is private;
Empty_List : constant List;
- --NOTE: function or deferred constant?
No_Element : constant Cursor;
@@ -1410,18 +1484,20 @@
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
- procedure Generic_Sort (Container : in out List'Class);
+ procedure Generic_Sort (Container : in out List);
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
- procedure Generic_Merge (Target : in out List'Class;
- Source : in out List'Class);
+ procedure Generic_Merge (Target : in out List;
+ Source : in out List);
procedure Reverse_List (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);
procedure Splice (Target : in out List;
Before : in Cursor;
@@ -1535,9 +1611,9 @@
If Element_Type is unconstrained and definite, then the Element parameter
of Process.all 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.
+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);
@@ -1564,11 +1640,19 @@
New_Item : in Element_Type;
Count : in Count_Type := 1);
+If Before is not No_Element, and does not designate an element in Container,
+then Program_Error is propagated.
Insert allocates Count new nodes whose element is initialized to the value
New_Item, and inserts them prior to the node designated by Before. If
Before equals No_Element, the new nodes are inserted immediately
-following the last node (if any). Any exception raised during allocation of
-internal storage is propagated, and Container is not modified.
+following the last node (if any).
+
+AARM Note: The check on Before checks that the cursor does not belong to some
+other Container. This check implies that a reference to the container is
+included in the cursor value. This wording is not meant to require detection of
+dangling cursors; such cursors are defined to be invalid, which means that
+execution is erroneous, and any result is allowed (including not raising an
+exception).
procedure Insert (Container : in out List;
Before : in Cursor;
@@ -1576,6 +1660,8 @@
Position : out Cursor;
Count : in Count_Type := 1);
+If Before is not No_Element, and does not designate an element in Container,
+then Program_Error is propagated.
Insert allocates Count new nodes whose element is initialized to the value
New_Item, and inserts them prior to the node designated by Before. If
Before equals No_Element, the new nodes are inserted immediately
@@ -1588,6 +1674,8 @@
Position : out Cursor;
Count : in Count_Type := 1);
+If Before is not No_Element, and does not designate an element in Container,
+then Program_Error is propagated.
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
@@ -1600,11 +1688,12 @@
Position : in out Cursor;
Count : in Count_Type := 1);
-If Position equals No_Element, the operation has no effect. Otherwise
-Delete removes Count nodes starting at the node designated by Position
-from Container (or all of the nodes if there are less than Count nodes
-starting at Position). Any exception raised during deallocation of internal
-storage is propagated.
+If Position equals No_Element, this operation has no effect. If Position does
+not designate an element in Container, then Program_Error is propagated. Otherwise
+Delete removes Count nodes starting at the node designated by Position from
+Container (or all of the nodes if there are less than Count nodes starting at
+Position). Any exception raised during deallocation of internal storage is
+propagated.
procedure Delete_First (Container : in out List;
Count : in Count_Type := 1);
@@ -1622,7 +1711,7 @@
generic
with function "<" (Left, Right : Element_Type) return Boolean is <>;
-procedure Generic_Sort (Container : in out List'Class);
+procedure Generic_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
@@ -1657,24 +1746,40 @@
procedure Reverse_List (Container : in out List);
Reorders the nodes 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.
-procedure Swap (Container : in out List;
- I, J : in Cursor);
+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_Links (Container : in out List;
+ I, J : in Cursor);
-Swap exchanges the nodes designated by I and J.
+If either I or J is No_Element, then Constraint_Error is propagated. If I or J
+do not designate an element in Container, then Program_Error is propagated.
+Otherwise, Swap_Links exchanges the nodes designated by I and J.
-AARM Note: Unlike Swap_Elements for vectors, this exchanges the nodes, not the
+AARM Note: Unlike Swap, this exchanges the nodes, not the
elements. No copying is performed. I and J designate the same elements after
-this call as they did before it. This is important, as this operation is
-provided as it can provide better performance than a straight copying swap. The
-programmer can writing a copying swap if they need one. This difference in
-semantics is the reason that this operations have different names in the List
-and Vector containers.
+this call as they did before it. This operation can provide better performance
+than Swap if the element size is large.
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List);
+If Before is not No_Element, and does not designate an element in Target,
+then Program_Error is propagated.
If Source denotes the same object as Target, the operation has no
effect. Otherwise, Splice reorders nodes such that they are removed from
Source and moved to Target, just prior to Before. If Before equals
@@ -1686,6 +1791,8 @@
Before : in Cursor;
Position : in Cursor);
+If either of Before or Position is not No_Element, and does not designate an
+element in Target, then Program_Error is propagated.
If Position equals No_Element, or if Position equals Before, or if the
successor of Position equals Before, the operation has no effect.
Otherwise the node designated by Position becomes the predecessor of Before.
@@ -1696,6 +1803,10 @@
Source : in out List;
Position : in Cursor);
+If Before does not equal No_Element, and does not designate a node in
+Target, then Program_Error is propagated. If Position does not equal
+No_Element, and does not designate a node in Source, then Program_Error
+is propagated.
If Source denotes the same object as Target, then Splice is
equivalent to the Splice operation sans Source parameter. If Position
equals No_Element, the operation has no effect. Otherwise the node
@@ -1734,6 +1845,8 @@
Position : Cursor := No_Element)
return Cursor;
+If Position is not No_Element, and does not designate an element
+in Container, then Program_Error is propagated.
Searches the nodes of Container for an element equal to Item. The
search starts at the node designated by Position. If Position equals
No_Element, then the search begins at the first node. If no element is
@@ -1744,6 +1857,8 @@
Position : Cursor := No_Element)
return Cursor;
+If Position is not No_Element, and does not designate an element
+in Container, then Program_Error is propagated.
Searches the nodes of Container in reverse for an element equal to Item.
The search starts at the node designated by Position. If Position
equals No_Element, then the search begins at the last node. If no
@@ -1780,7 +1895,23 @@
Invokes Process.all with a cursor that designates each node in Container. Any
exceptions raised during Process are propagated.
+Program_Error is propagated if:
+ * Process.all attempts to insert or delete elements from Container; or
+ * Process.all calls a routine that reorders the elements of Container
+ (Swap_Links, Splice, Generic_Sort, or Generic_Merge); or
+ * Process.all finalizes Container; or
+ * Process.all calls Move with Container as a parameter.
+AARM Note:
+This check takes place when the operations that insert or delete elements, etc.
+are called. There is no check needed if an attempt is made to insert or delete
+nothing (that is, Count = 0).
+
+See Iterate for vectors for a suggested implementation of the check.
+
+Swap is not included here, as it only copies elements.
+End AARM Notes.
+
procedure Reverse_Iterate
(Container : in List;
Process : not null access procedure (Position : in Cursor));
@@ -1799,9 +1930,11 @@
The result of "=" or Has_Element is unspecified if it is called with an invalid
cursor parameter. Execution is erroneous if any other subprogram declared in
-Containers.Doubly_Linked_Lists is called with an invalid cursor parameter, or
-if the cursor designates an element in a different list object than the
-appropriate one specified in the call.
+Containers.Doubly_Linked_Lists is called with an invalid cursor parameter.
+
+Execution also is erroneous if the called Process procedure of a call to
+Query_Element or Update_Element executes an operation that causes the Position
+cursor of Query_Element or Update_Element to become invalid.
AARM Notes: The list above is intended to be exhaustive. In other cases, a
cursor value continues to designate its original element. For instance,
@@ -1870,11 +2003,8 @@
with function Hash (Key : Key_Type) return Hash_Type;
- with function "=" (Left, Right : Key_Type)
- return Boolean is <>;
-
- with function Is_Equal_Key (Left, Right : Key_Type)
- return Boolean is "=";
+ with function Equivalent_Keys (Left, Right : Key_Type)
+ return Boolean;
with function "=" (Left, Right : Element_Type)
return Boolean is <>;
@@ -1903,11 +2033,13 @@
procedure Query_Element
(Position : in Cursor;
- Process : not null access procedure (Element : in Element_Type));
+ Process : not null access procedure (Key : in Key_Type;
+ Element : in Element_Type));
procedure Update_Element
(Position : in Cursor;
- Process : not null access procedure (Element : in out Element_Type));
+ Process : not null access procedure (Key : in Key_Type;
+ Element : in out Element_Type));
procedure Replace_Element (Position : in Cursor;
By : in Element_Type);
@@ -1921,9 +2053,17 @@
Position : out Cursor;
Inserted : out Boolean);
- procedure Insert_Or_Replace (Container : in out Map;
- Key : in Key_Type;
- New_Item : in Element_Type);
+ procedure Insert (Container : in out Map;
+ Key : in Key_Type;
+ New_Item : in Element_Type);
+
+ procedure Include (Container : in out Map;
+ Key : in Key_Type;
+ New_Item : in Element_Type);
+
+ procedure Replace (Container : in out Map;
+ Key : in Key_Type;
+ New_Item : in Element_Type);
procedure Insert (Container : in out Map;
Key : in Key_Type;
@@ -1933,6 +2073,9 @@
procedure Delete (Container : in out Map;
Key : in Key_Type);
+ procedure Exclude (Container : in out Map;
+ Key : in Key_Type);
+
procedure Delete (Container : in out Map;
Position : in out Cursor);
@@ -1949,8 +2092,8 @@
function Capacity (Container : Map) return Count_Type;
- procedure Set_Capacity (Container : in out Map;
- Capacity : in Count_Type);
+ procedure Reserve_Capacity (Container : in out Map;
+ Capacity : in Count_Type);
function First (Container : Map)
return Cursor;
@@ -1963,15 +2106,15 @@
function Key (Position : Cursor) return Key_Type;
- function Is_Equal_Key (Left, Right : Cursor)
+ function Equivalent_Keys (Left, Right : Cursor)
return Boolean;
- function Is_Equal_Key (Left : Cursor;
- Right : Key_Type)
+ function Equivalent_Keys (Left : Cursor;
+ Right : Key_Type)
return Boolean;
- function Is_Equal_Key (Left : Key_Type;
- Right : Cursor)
+ function Equivalent_Keys (Left : Key_Type;
+ Right : Cursor)
return Boolean;
procedure Iterate
@@ -2012,7 +2155,7 @@
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
+Equivalent_Keys 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.
@@ -2027,36 +2170,29 @@
logically a pure function), or the behavior is unspecified.
End AARM Notes
-Function Is_Equal_Key and the generic formal equality operator for keys are
-expected to return the same result value each time either is called with a
-particular pair of key values. If the generic formal equality operator returns
-True for a particular pair of key values, then the formal function Is_Equal_Key
-is expected to return True for the same pair of key values. If Is_Equal_Key
-or the generic formal equality operator for keys behaves in some other manner,
-the behavior of this package is unspecified. Which subprograms of this package
-call Is_Equal_Key or the generic formal equality operator for keys, and how
-many times they call Is_Equal_Key or the generic formal equality operator
-for keys, is unspecified.
+Function Equivalent_Keys is expected to return the same result value each time
+it is called with a particular pair of key values. 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
+Equivalent_Keys, is unspecified.
AARM Notes
As with Hash, the implementation is not required to protect against
-Is_Equal_Key or the generic formal equality operator for keys raising an
-exception or returning random results. Similarly, the implementation can call
-either of these operations whenever they are needed. The result must remain the
-same (these are logically pure functions), or the behavior is unspecified.
-
-The generic equality operation for keys is not expected to be explicitly
-specified in instantiations; the default equality is good enough. Key equality
-for a map is named Is_Equal_Key in order that named notation can be used in
-an instantiation. Otherwise, there would be two parameters named "=", and named
-notation could not be used. This generic has too many formal parameters to
-allow confortable use of positional notation; named notation is required.
-Since key equality is likely to be overridden and needs to be frequently
-referenced in the wording, it is given the explicit name.
+Equivalent_Keysraising an exception or returning random results. Similarly, the
+implementation can call this operation whenever it is needed. The result must
+remain the same (this is a logically pure function), or the behavior is
+unspecified.
+
+Key equality for a map is named Equivalent_Keys in order that named notation
+can be used in an instantiation. Otherwise, there would be two parameters named
+"=", and named notation could not be used. This generic has too many formal
+parameters to allow confortable use of positional notation; named notation is
+required. Since key equality is likely to be overridden and needs to be
+frequently referenced in the wording, it is given the explicit name.
End AARM Notes
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, Is_Equal_Key, or the
+operation in this package such that at least one of Hash, Equivalent_Keys, or the
generic formal equality operator give different results, the behavior of this
package is unspecified.
@@ -2090,14 +2226,14 @@
immediately the value True. If Left and Right have different lengths, then the
function returns the value False. Otherwise, for each key K in Left, the
function returns False if:
- * K is not present in Right (using the generic formal equality operator for
- keys); or
+ * a key equivalent to K is not present in Right (using the generic formal
+ Equivalent_Keys function); or
* the element associated with K in Left is not equivalent to the element
associated with K in Right (using the generic formal equality operator for
elements).
If the function has not returned a result after checking all of the keys, the
-function returns True. Any exception raised during evaluation of key or element
-equality is propagated.
+function returns True. Any exception raised during evaluation of key
+equivalence or element equality is propagated.
The function Length returns the number of key/element pairs in Map.
@@ -2114,26 +2250,28 @@
procedure Query_Element
(Position : in Cursor;
- Process : not null access procedure (Element : in Element_Type));
+ Process : not null access procedure (Key : in Key_Type;
+ Element : in Element_Type));
If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
-Query_Element invokes Process.all with the element on node designated by
-Position as the argument.
+Query_Element invokes Process.all with the key and element from the node
+designated by Position as the arguments.
procedure Update_Element
(Position : in Cursor;
- Process : not null access procedure (Element : in out Element_Type));
+ 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 invokes Process.all with the element designated by Position as
-the argument.
+Update_Element invokes Process.all with the key and element from the node
+designated by Position as the arguments.
If Element_Type is unconstrained and definite, then the Element parameter
of Process.all 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.
+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);
@@ -2159,8 +2297,8 @@
Inserted : out Boolean);
If Length (Container) equals Capacity (Container), then Insert calls
-Set_Capacity to increase the capacity of Container to some larger value. Insert
-then uses Hash and Is_Equal_Key to check if Key is already present in
+Reserve_Capacity to increase the capacity of Container to some larger value.
+Insert then uses Hash and Equivalent_Keys to check if Key is already present in
Container. If a key matches, Inserted 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. Inserted returns
@@ -2170,33 +2308,68 @@
AARM Notes:
Insert should only compare keys that hash to the same bucket in the hash table.
-We specify when Set_Capacity is called to bound the overhead of capacity
+We specify when Reserve_Capacity is called to bound the overhead of capacity
expansion operations (which are potentially expensive). Moreover, expansion can
be predicted by comparing Capacity(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 Insert_Or_Replace (Container : in out Map;
- Key : in Key_Type;
- New_Item : in Element_Type);
-
-Insert_Or_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 exception raised during assignment
-is propagated.
+procedure Insert (Container : in out Map;
+ Key : in Key_Type;
+ New_Item : in Element_Type);
+Insert inserts Key and New_Item as per the five parameter Insert, with the
+difference that if Key is already in the map, then Constraint_Error is
+propagated.
+
AARM Note: This is equivalent to:
declare
Inserted : Boolean; C : Cursor;
begin
- Insert (Container, Key, New_Item, Inserted => Inserted, Position => C);
+ Insert (Container, Key, New_Item, C, Inserted);
if not Inserted then
- Replace_Element (Container, C, New_Item);
+ raise Constraint_Error;
+ end if;
+ end;
+but doesn't require the hastle of out parameters.
+
+procedure Replace (Container : in out Map;
+ Key : in Key_Type;
+ New_Item : in Element_Type);
+
+If Length (Container) equals 0, then Contraint_Error is propagated. Otherwise, it
+uses Hash and Equivalent_Keys to check if Key is present in Container. If Key
+is present in Container, assigns Key and New_Item to the
+node associated with Key; otherwise, it raises Constraint_Error.
+
+AARM Note: We update the key as well as the element, as the key might include
+additional information that does not participate in equivalence. If only the
+element needs to be updated, use
+Replace_Element (Find (Container, Key), New_Element).
+
+procedure Include (Container : in out Map;
+ Key : in Key_Type;
+ New_Item : in Element_Type);
+
+Insert inserts Key and New_Item as per Insert, with the difference
+that if Key is already in the map, then this operation assigns Key and New_Item
+to the node associated with Key. Any exception raised during assignment is
+propagated.
+
+AARM Note: This is equivalent to:
+ declare
+ C : Cursor := Find (Container, Key);
+ begin
+ if C = No_Element then
+ Insert (Container, Key, New_Item);
+ else
+ Replace (Container, Key, New_Item);
end if;
end;
-but is much more convinient, as there are no out parameters to deal with.
+but this avoids doing the search twice.
+
procedure Insert (Container : in out Map;
Key : in Key_Type;
Position : out Cursor;
@@ -2210,26 +2383,46 @@
procedure Delete (Container : in out Map;
Key : in Key_Type);
-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.
+It uses Hash and Equivalent_Keys to check if Key is present in Container.
+If Key matches the key of a node, Delete removes the node from the map;
+otherwise, Delete raises Constraint_Error.
AARM Notes:
Delete should only compare keys that hash to the same bucket in the hash
-table. Delete should work on an empty map; nothing happens in that case.
+table. The node containing the element may be deallocated now,
+or it may be saved and reused later.
+procedure Exclude (Container : in out Map;
+ Key : in Key_Type);
+
+It uses Hash and Equivalent_Keys to check if Key is present in Container. If Key
+matches the key of a node, Exclude removes the node from the map and then
+deallocates the node.
+
+AARM Notes:
+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.
+
procedure Delete (Container : in out Map;
Position : in out Cursor);
-If Position equals No_Element, this operation has no effect.
-Otherwise, Delete removes the node from the map and deallocates the node.
-Position is set to No_Element on return.
+If Position equals No_Element, this operation 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 map. Position is set
+to No_Element on return.
+
+AARM Note: The check on Position checks that the cursor does not belong to some
+other Container. This check implies that a reference to the container is
+included in the cursor value. This wording is not meant to require detection of
+dangling cursors; such cursors are defined to be invalid, which means that
+execution is erroneous, and any result is allowed (including not raising an
+exception).
function Find (Container : Map;
Key : Key_Type) return Cursor;
If Length (Container) equals 0, then this function returns
-No_Element. Otherwise, it uses Hash and Is_Equal_Key to check if Key is
+No_Element. Otherwise, it uses Hash and Equivalent_Keys 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.
@@ -2243,13 +2436,13 @@
The function Capacity returns the capacity of Container.
-procedure Set_Capacity (Container : in out Map;
- Capacity : in Count_Type);
+procedure Reserve_Capacity (Container : in out Map;
+ Capacity : in Count_Type);
-If Capacity < Length (Container), Constraint_Error is raised. Otherwise,
-Set_Capacity allocates a new hash table such that the length of the
+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 Set_Capacity operation. If the allocation fails, the exception is
+additional Reserve_Capacity operation and is large enough to hold the current
+length of Map. 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.
@@ -2260,7 +2453,7 @@
make that true at this point, even though the visible semantics could be
preserved by waiting until enough elements are inserted.
-While Set_Capacity can be used to reduce the capacity of a map, we do not
+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.
@@ -2312,14 +2505,14 @@
by Position.
-The function Is_Equal_Key (Left, Right : Cursor) is equivalent to
-Is_Equal_Key (Key (Left), Key (Right)).
+The function Equivalent_Keys (Left, Right : Cursor) is equivalent to
+Equivalent_Keys (Key (Left), Key (Right)).
-The function Is_Equal_Key (Left : Cursor; Right : Key_Type) is
-equivalent to Is_Equal_Key (Key (Left), Right).
+The function Equivalent_Keys (Left : Cursor; Right : Key_Type) is
+equivalent to Equivalent_Keys (Key (Left), Right).
-The function Is_Equal_Key (Left : Key_Type; Right : Cursor) is
-equivalent to Is_Equal_Key (Left, Key (Right)).
+The function Equivalent_Keys (Left : Key_Type; Right : Cursor) is
+equivalent to Equivalent_Keys (Left, Key (Right)).
procedure Iterate
@@ -2328,8 +2521,22 @@
Iterate calls Process.all with a cursor that designates each node
in the Container. Any exception raised by Process is propagated.
+Program_Error is propagated if:
+ * Process.all attempts to insert or delete elements from Container; or
+ * Process.all calls Reserve_Capacity; or
+ * Process.all finalizes Container; or
+ * Process.all calls Move with Container as a parameter.
+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.
+We have to include Reserve_Capacity here, as rehashing probably will change
+the order that elements are stored in the map.
+End AARM Notes.
+
Legality Rules
An instantiation of Containers.Hashed_Maps shall be at the library level.
@@ -2354,9 +2561,11 @@
The result of "=" or Has_Element is unspecified if it is called with an invalid
cursor parameter. Execution is erroneous if any other subprogram declared in
-Containers.Hashed_Maps is called with an invalid cursor parameter, or if the
-cursor designates an element in a different map object than the appropriate one
-specified in the call.
+Containers.Hashed_Maps is called with an invalid cursor parameter.
+
+Execution also is erroneous if the called Process procedure of a call to
+Query_Element or Update_Element executes an operation that causes the Position
+cursor of Query_Element or Update_Element to become invalid.
AARM Notes: The list above is intended to be exhaustive. In other cases, a
cursor value continues to designate its original element. For instance,
@@ -2446,9 +2655,18 @@
procedure Insert (Container : in out Set;
New_Item : in Element_Type);
+ procedure Include (Container : in out Set;
+ New_Item : in Element_Type);
+
+ 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;
Position : in out Cursor);
@@ -2456,6 +2674,10 @@
procedure Delete_Last (Container : in out Set);
+ procedure Replace (Container : in Set;
+ Position : in Cursor;
+ By : in Element_Type);
+
procedure Union (Target : in out Set;
Source : in Set);
@@ -2485,7 +2707,7 @@
function "xor" (Left, Right : Set) return Set renames
Symmetric_Difference;
- function Is_Disjoint (Left, Right : Set) return Boolean;
+ function Overlap (Left, Right : Set) return Boolean;
function Is_Subset (Subset : Set;
Of_Set : Set) return Boolean;
@@ -2582,9 +2804,16 @@
Key : Key_Type)
return Element_Type;
+ procedure Replace (Container : in out Set;
+ 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;
@@ -2720,27 +2949,60 @@
Insert compares New_Item to the elements in Container using the generic formal
less-than operator for elements. If an element equivalent to New_Item is
-already in Container, Insert does nothing. Otherwise, it allocates a new
-element which is initialized to New_Item. Any exception raised during
+already in Container, Insert raises Constraint_Error. Otherwise, it allocates a
+new element which is initialized to New_Item. Any exception raised during
allocation and initialization is propagated and Container is not modified.
+procedure Include (Container : in out Set;
+ New_Item : in Element_Type);
+
+Include compares New_Item to the elements in Container using the generic formal
+less-than operator for elements. If an element equivalent to New_Item is
+already in Container, Include assigns New_Item to the equivalent element.
+Otherwise, it allocates a new element which is initialized to New_Item. Any
+exception raised during allocation and initialization is propagated and
+Container is not modified.
+
+procedure Replace (Container : in out Set;
+ New_Item : in Element_Type);
+
+Replace compares New_Item to the elements in Container using the generic formal
+less-than operator for elements. If an element equivalent to New_Item is
+already in Container, Replace assigns New_Item to the equivalent element.
+Otherwise, Constraint_Error is propagated.
+
procedure Delete (Container : in out Set;
Item : in Element_Type);
Delete searches Container for an element equivalent to Item. If there is an
element in Container equivalent to Item, the element is removed from Container.
+Otherwise, Constraint_Error is propagated.
AARM Note: The internal node containing the element may be deallocated now,
or it may be saved and reused later.
+procedure Exclude (Container : in out Set;
+ Item : in Element_Type);
+
+Exclude searches Container for an element equivalent to Item. If there is an
+element in Container equivalent to Item, the element is removed from Container.
+
procedure Delete (Container : in out Set;
Position : in out Cursor);
-If Position equals No_Element, the operation has no effect. Otherwise, Delete
-removes the element designated by Position from Container. Position is set to
-No_Element on return.
+If Position equals No_Element, this operation has no effect. If Position does
+not designate an element in Container, then Program_Error is propagated. Otherwise,
+Delete removes the element designated by Position from Container.
+Position is set to No_Element on return.
+AARM Note: The check on Position checks that the cursor does not belong to some
+other Container. This check implies that a reference to the container is
+included in the cursor value. This wording is not meant to require detection of
+dangling cursors; such cursors are defined to be invalid, which means that
+execution is erroneous, and any result is allowed (including not raising an
+exception).
+
procedure Delete_First (Container : in out Set);
If Container is empty, the operation has no effect. Otherwise the element
@@ -2751,6 +3013,19 @@
If Container is empty, the operation has no effect. Otherwise the element
designated by Last (Container) is removed from Container.
+procedure Replace (Container : in Set;
+ Position : in Cursor;
+ By : in Element_Type);
+
+If Position equals No_Element, then Constraint_Error is propagated.
+If Positiond oes not designate an element in Container, then Program_Error
+is propagated. Otherwise, Replace compares By to the element
+designated by Position using the generic formal less-than operator for
+elements. If the element designated by Position is equivalent to By, Replace
+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 Union (Target : in out Set;
Source : in Set);
@@ -2815,12 +3090,13 @@
not equivalent to the corresponding elements of Left.
-function Is_Disjoint (Left, Right : Set) return Boolean;
+function Overlap (Left, Right : Set) return Boolean;
If an element of Left is equivalent to some element of Right, then
-Is_Disjoint returns False. Otherwise it returns True.
+Overlap returns True. Otherwise it returns False.
-AARM Note: This operation is communitive.
+AARM Notes: This operation is communative. If Overlap returns False, the
+two sets are disjoint.
function Is_Subset (Subset : Set;
Of_Set : Set) return Boolean;
@@ -2828,7 +3104,7 @@
If an element of Subset is not equivalent to some element of
Of_Set, the function returns False. Otherwise it returns True.
-AARM Note: This operation is not communitive, so we use parameter names that
+AARM Note: This operation is not communative, so we use parameter names that
make it clear in named notation which set is which.
@@ -2924,7 +3200,19 @@
Process : not null access procedure (Position : in Cursor));
Invokes Process.all with a cursor that designates each element in Container.
+Program_Error is propagated if:
+ * Process.all attempts to insert or delete elements from Container; or
+ * Process.all finalizes Container; or
+ * Process.all calls Move with Container as a parameter.
+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 Reverse_Iterate
(Container : in Set;
Process : not null access procedure (Position : in Cursor));
@@ -2947,11 +3235,17 @@
The operations in package Generic_Keys named Contains, Find, Floor, Ceiling,
-Element, Delete, and operators designated "<" and ">", are equivalent to the
-corresponding operations in the parent package, with the difference that the
-Key subprogram parameter is compared to elements in the container using the
+Element, Delete, Exclude, and operators designated "<" and ">", are equivalent
+to the corresponding operations 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.
+procedure Replace (Container : in out Set;
+ Key : in Key_Type;
+ New_Item : in Element_Type);
+
+Equivalent to Replace (Container, Find (Container, Key), New_Item).
+
function Key (Position : Cursor) return Key_Type;
If Position equals No_Element, then Constraint_Error is propagated.
@@ -2963,13 +3257,15 @@
Position : in Cursor;
Process : not null access procedure (Element : in out Element_Type));
-If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
+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,
Checked_Update_Element uses Key to save the key value (KB) of the element.
Checked_Update_Element then invokes Process.all with the element designated
by Position as the argument. The key KB is compared to the new element value
using the generic formal less-than and greater-than operators; if either
returns True, the element is removed from the set, then is inserted back into
-the set. If the insertion fails, Constraint_Error is raised.
+the set. If the insertion fails, Program_Error is propagated.
AARM Note: The key check insures that the invariants of the set are
preserved by the modification. If not, we try to re-insert the element at
@@ -2981,9 +3277,9 @@
If Element_Type is unconstrained and definite, then the Element parameter
of Process.all 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.
+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.
Legality Rules
@@ -3005,13 +3301,15 @@
* The set that contains the element it designates has been finalized;
* The set that contains the element it designates has been used as the
Source or Target of a call to Move;
- * The element it designates has been deleted from the set
+ * The element it designates has been deleted from the set.
The result of "=" or Has_Element is unspecified if it is called with an invalid
cursor parameter. Execution is erroneous if any other subprogram declared in
-Containers.Ordered_Sets is called with an invalid cursor parameter, or
-if the cursor designates an element in a different set object than the
-appropriate one specified in the call.
+Containers.Ordered_Sets is called with an invalid cursor parameter.
+
+Execution also is erroneous if the called Process procedure of a call to
+Query_Element or Checked_Update_Element executes an operation that causes the
+Position cursor of Query_Element or Checked_Update_Element to become invalid.
AARM Notes: The list above is intended to be exhaustive. In other cases, a
cursor value continues to designate its original element. For instance,
@@ -3240,7 +3538,7 @@
procedure Copy (A : Array_Subtype) is
V : Vector;
begin
- Set_Capacity (V, Capacity => A'Length);
+ Reserve_Capacity (V, Capacity => A'Length);
for I in A'Range loop
Append (V, New_Item => A (I));
@@ -3248,15 +3546,15 @@
...
end Copy;
-The Set_Capacity operation tells the vector object to preallocate an internal
+The Reserve_Capacity operation tells the vector object to preallocate an internal
array having at least the capacity specified. If you need to perform many
repeated insertions, then if you know the ultimate length apriori you
-should always call Set_Capacity beforehand. This is more efficient because it
+should always call Reserve_Capacity beforehand. This is more efficient because it
allocates the internal array once, and therefore avoids the repeated
reallocation, copying, and deallocation cycles that might be necessary
otherwise as the array is expanded.
-Instead appending new items to the back of the vector, another technique
+Instead of appending new items to the back of the vector, another technique
is to declare the vector object with the requisite length immediately:
procedure Copy (A : Array_Subtype) is
@@ -3311,9 +3609,9 @@
procedure Copy
(A : in Array_Subtype;
V : in out Vector;
- I : in Index_Type'Base) is
+ I : in Extended_Index) is
- J : Index_Type'Base := I;
+ J : Extended_Index := I;
begin
Insert_Space (V, Before => I, Count => A'Length); -- dig the hole
@@ -3349,7 +3647,7 @@
The internal array is managed by the implementation, and there is no
requirement that it has any particular capacity; the only requirement is that
the actual capacity is the same or larger than the most recent call to
-Set_Capacity. Thus Set_Capacity (V, 0) might, but might not, deallocate the
+Reserve_Capacity. Thus Reserve_Capacity (V, 0) might, but might not, deallocate the
internal array. If you want to clear the vector and also deallocate the
internal array, you can use Move:
@@ -3440,7 +3738,7 @@
procedure Append
(V : Vector_of_Lists.Vector;
- I : Index_Type'Base;
+ I : Index_Subtype;
E : Element_Subtype) is
procedure Process (L : in out List) is
@@ -3567,7 +3865,7 @@
procedure Swap
(V : in out Vector_Of_Lists.Vector;
- I, J : in Index_Type'Base) is
+ I, J : in Extended_Index) is
begin
Vector_Of_Lists.Swap (V, I, J); -- vector operation
end;
@@ -3580,7 +3878,7 @@
procedure Swap
(V : in out Vector_Of_Lists.Vector;
- I, J : in Index_Type'Base) is
+ I, J : in Extended_Index) is
procedure Process_I (IE : in out List) is
@@ -3637,7 +3935,7 @@
It's often the case that you know apriori the total number of elements
you intend to insert into the map. Under these circumstances you should
-always Set_Capacity the map first (similar to a vector container), and then
+always Reserve_Capacity the map first (similar to a vector container), and then
perform the insertions. This preallocates a hash table that has the proper
capacity, and thus avoids the automatic rehashing that occurs
during normal insertion to preserve the load factor. For example:
@@ -3648,7 +3946,7 @@
Position : Map_Types.Cursor;
Inserted : Boolean;
begin
- Set_Capacity (M, Capacity => N); -- Capacity >= N
+ Reserve_Capacity (M, Capacity => N); -- Capacity >= N
for I in 1 .. N loop
Insert -- no expansion and rehashing will occur
@@ -3795,9 +4093,10 @@
package FD_Map_Types is
new Ada.Containers.Hashed_Maps
- (Key_Type => C.int,
- Element_Type => Session_Access,
- Hash => Hash_FD);
+ (Key_Type => C.int,
+ Element_Type => Session_Access,
+ Hash => Hash_FD,
+ Equivalent_Keys => C."=");
Now I can declare a map object in the body:
@@ -3854,9 +4153,10 @@
package Wordcount_Maps is
new Ada.Containers.Indefinite_Hashed_Maps
- (Key_Type => String,
- Element_Type => Natural,
- Hash => Ada.Strings.Hash); -- case-sensitive
+ (Key_Type => String,
+ Element_Type => Natural,
+ Hash => Ada.Strings.Hash, -- case-sensitive
+ Equivalent_Keys => "="); -- case-sensitive);
Wordcount_Map : Wordcount_Maps.Map;
@@ -3892,7 +4192,8 @@
procedure Insert (Word : String) is
- procedure Increment (Count : in out Natural) is
+ procedure Increment (Word : in String;
+ Count : in out Natural) is
begin
Count := Count + 1;
end;
@@ -3914,7 +4215,7 @@
end Insert;
Map (and set) insertion works conditionally. It searches the container
-to determine whether there is an equal key already in the map.
+to determine whether there is an equivalent key already in the map.
Note that in the example above, the New_Item parameter has the value 0.
This is deliberate. What happens is that if the word is already in the
@@ -4075,10 +4376,10 @@
package File_Cache_Types is
new Ada.Containers.Indefinite_Hashed_Maps
- (Key_Type => String,
- Element_Type => Context_Access,
- Hash => Hash_String_Case_Insensitive,
- Is_Equal_Key => Equal_String_Case_Insensitive);
+ (Key_Type => String,
+ Element_Type => Context_Access,
+ Hash => Hash_String_Case_Insensitive,
+ Equivalent_Keys => Equal_String_Case_Insensitive);
File_Cache : File_Cache_Types.Map;
@@ -4220,10 +4521,10 @@
package Id_Maps is
new Ada.Containers.Indefinite_Hashed_Maps
- (Key_Type => String,
- Element_Type => Session_Access,
- Hash => Ada.Strings.Hash); -- case-sensitive
-
+ (Key_Type => String,
+ Element_Type => Session_Access,
+ Hash => Ada.Strings.Hash, -- case-sensitive
+ Equivalent_Keys => "="); -- case-sensitive
Id_Map : Id_Maps.Map;
use Id_Maps;
@@ -4603,7 +4904,19 @@
than using the item-form of Delete, since the cursor-form doesn't have
to search for the item.
+There are special set operations to operate on the first element. Using those
+would simplify this example:
+ procedure Shutdown_Connections is
+ X : Connection_Access;
+ begin
+ while not Is_Empty (Connection_Set) loop
+ X := First_Element (Connect_Set);
+ Delete_First (Connection_Set);
+ Free (X);
+ end loop;
+ end Shutdown_Connections;
+
One of the canonical container examples is the set-of-employees.
Suppose we have an employee type defined this way:
@@ -4734,7 +5047,8 @@
begin
if Has_Element (Position) then
SSN_Keys.Checked_Update_Element
- (Position => Position,
+ (Container => Employees,
+ Position => Position,
Process => Set_Home'Address);
...
end if;
@@ -4830,7 +5144,8 @@
end;
begin
SSN_Keys.Checked_Update_Element
- (Position => Old_Position,
+ (Container => Employees,
+ Position => Old_Position,
Process => Set_SSN'Access);
end;
end Change_SSN;
@@ -4850,7 +5165,7 @@
procedure Print (I : in Employee_Sets.Cursor) is
- procedure Do_Print (E : in out Employee_Type) is
+ procedure Do_Print (E : in Employee_Type) is
begin
Put ("Name: "); Put (E.Name);
Put ("SSN: "); Put (E.SSN);
@@ -4884,9 +5199,9 @@
Result : Boolean;
- procedure Process_LE (LE : in out Employee_Type) is
+ procedure Process_LE (LE : in Employee_Type) is
- procedure Process_RE (RE : in out Employee_Type) is
+ procedure Process_RE (RE : in Employee_Type) is
begin
Result := LE.Name < RE.Name;
end;
@@ -4906,7 +5221,7 @@
procedure Sort is
new Generic_Array_Sort (Count_Type, Cursor, Cursor_Array);
- procedure Do_Print (E : in out Employee_Type) is
+ procedure Do_Print (E : in Employee_Type) is
begin
Put ("Name: "); Put (E.Name);
Put ("SSN: "); Put (E.SSN);
@@ -5002,7 +5317,7 @@
RTSP_Status : out RTSP_Status_Type) is
Position : constant Session_Set_Types.Cursor :=
- Find (Session_Set, Key => Session_Id);
+ Id_Keys.Find (Session_Set, Key => Session_Id);
Session : Session_Access;
begin
@@ -8102,8 +8417,8 @@
problems.
17) Changed the name of the parameters of Is_Disjoint to Left and Right.
-This operation is communitive, and might was well have parameter names
-similar to Union and Intersection. OTOH, Is_Subset is neither communitive
+This operation is communative, and might was well have parameter names
+similar to Union and Intersection. OTOH, Is_Subset is neither communative
nor "common knowledge". Thus, its parameters were named "Subset" and
"Of_Set", so it is clear which is the subset that is being tested. This is
clearly preferable in named prefix calls:
@@ -8390,6 +8705,241 @@
This complication doesn't seem worth it to me, but as it came up very late,
the entire ARG needs to discuss the issue.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Monday, October 3, 2004 xx:xx PM
+
+Here is a listing of the AI-302 updates that I made beyond those discussed at the meeting. These mostly have come up in more recent e-mail discussions.
+
+1) Moved the AARM noted describing the now removed Assert to a (user) "Note".
+ The fact that instantiating Ada.Containers.Vectors with a type for which
+ Index_Type'Base'First = Index_Type'First will raise Constraint_Error is
+ obvious from reading the spec. carefully -- but it seems to me few users
+ will read that carefully. The note reads:
+
+ If Index_Type'Base'First = Index_Type'First an instantiation 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.
+
+2) Matt pointed out that Insert expects to be passed Index_Type'Last + 1 in
+ some circumstances. In particular, inserting nothing into a full vector is
+ not expected to raise an exception (to be similar to similar array
+ operations). We want to include that value in Extended_Index as long as it
+ actually exists. (Unlike the lower bound, we don't want to insist that this
+ value exists, because if we did, we wouldn't be able to instantiate this
+ generic with Positive or Natural.) So, we changed the declaration of
+ Extended_Index to:
+
+ subtype Extended_Index is
+ Index_Type'Base range Index_Type'First-1 .. Index_Type'Last +
+ Boolean'Pos (Index_Type'Base'Last > Index_Type'Last);
+
+ This declaration allows both special values (if they exist) and no others.
+
+
+3) Replace and Exclude operations matching the ones in the Ordered_Sets were
+ added to the Generic_Keys generic, as it is odd that Delete was in there and
+ not the others. (The intent is that this package closely match Hashed_Maps
+ [and Ordered_Maps, if it ever is defined] - as many operations on keys in
+ Hashed_Maps should be represented here as possible.) Insert and Include were
+ omitted, as there could be no guarentee that the Key passed in matches the
+ one in the Element passed in. (We could check, of course, but that seems
+ like going too far; moreover, it's hard to imagine how these could be used.)
+ Replace simply doesn't worry about it; it is defined in terms of Replace
+ (see below), replacing the element referred to by the Key. Thus it works
+ similarly to Checked_Update_Element.
+
+ Replace (Container, Cursor, New_Item) also has been added to the Set itself,
+ as there is not a Replace_Element for a set. This tries to replace in place,
+ but will do an insert/delete if necessary.
+
+
+4) The definition of *cursor* was buried in the introductory AARM text. I moved
+ that into the introductory paragraphs of A.17, so that it appears in the
+ normative text. Readers of the standard should be presented the basic model
+ of the containers.
+
+5) The index forms of Element, Replace_Element, Query_Element, and
+ Update_Element took Index_Type'Base for some reason, but passing No_Index
+ raises Constraint_Error. So I changed these to Index_Type, so that the
+ specification doesn't allow No_Index to be passed.
+
+6) Added an erroneous case for abuse of the Process procedure of Query_Element
+ and Update_Element. This usually looks like:
+
+ Execution also is erroneous if the called Process procedure of a call to
+ Query_Element or Update_Element executes an operation that causes the
+ Position cursor of Query_Element or Update_Element to become invalid.
+
+For lists, maps, and sets, the only problem occurs if the element is deleted
+directly, or if the container is finalized (via Unchecked_Deallocation).
+Insertions and other Deletions don't matter, as the nodes are logically
+separate.
+
+For vectors, the rule also includes ambiguous cursors. An insert or delete to
+the left of the cursor will move the elements; if the element is passed by
+reference, that will clobber the element being operated on with unknown
+effects. We don't want to require that optimization is off in Process
+subprograms! The vector version also requires wording to cover the index
+version of the routines.
+
+I'd like to suggest that we consider adding a check that the element being
+processed is not deleted by the Process procedure. This check requires only a
+bit per node (or a short list of elements in process), and covers all of the
+new dangerous cases for most of the containers. (Bad use of
+Unchecked_Deallocation is hardly new to the containers, and Move will not
+actually cause problems in practice, as the nodes are not changed, just the
+container that they belong to.) Deleting yourself requires contortions (the
+Process routine does not have a cursor to use for this operation), and, since
+it damages the element parameter, the effects could be widespread. The check
+also would prevent calling Update_Element on the same element again, which
+would have different results depending on the parameter passing mode (and which
+makes the check cheaper). The overhead of the check would only apply to the
+various Deletes and Update_Element; no other routines would need to check. The
+text would be:
+
+ If the Process procedure deletes the element designated by Cursor, or calls
+ Update_Element on Cursor, Program_Error is raised.
+
+ AARM Note: This check has to be done in the code for Delete and Update_Element,
+ of course.
+
+Making vector Update_Element safe would also require checking for any
+operations that would make the cursor ambigious. (That's a bounded error in
+other cases.)
+
+7) Matt had previous made a number of suggestions about improving/correcting
+ the examples. These have been integrated.
+
+8) Delete for cursors does nothing if the cursor is No_Element for Lists, Maps,
+ and Sets. (Matt says this was intended to model the effect of
+ Unchecked_Deallocation.) Delete for cursors in Vectors, on the other hand,
+ raised Constraint_Error in this case. I changed the wording for Delete for
+ cursors in Vectors to be consistent with the other three.
+
+(Note, however, that Delete for Keys is now defined to raise an exception if
+the key is not found; the routine Exclude is defined not to raise an exception.
+Thus, this is a bit inconsistent. It would be more consistent if Delete for
+cursors for all containers raised an exception when given No_Element. This
+doesn't seem particularly important to change, but it should be considered.)
+
+9) Nick pointed out that Insert for Vectors was leaving the Out parameter
+ Position undefined if the length of the insertion was 0. I fixed that
+ wording to make it equal to Before.
+
+10) Added an AARM note to the effect that when we say "unspecified" in this
+clause (A.17), we don't mean "erroneous". If we meant "erroneous", we said
+that. And included some ramifications of that (checking must not be suppressed;
+don't create dangling pointers by assuming behavior of generic formals).
+
+This intent should be written down somewhere, even if it is too complex and
+error-prone to try to do so normatively.
+
+11) Removed some implementation details from the !proposal section, which
+ should be a high-level description. (Thanks to Matt for picking those up.)
+
+12) Ada.Strings.Unbounded.Hash needs to be Preelaborated, not Pure, as its
+ parent is only Preelaborated (not Pure).
+
+13) Changed Set_Length's wording to:
+ If Length is larger than the capacity of Container, calls
+ Reserve_Capacity (Container, Length), then sets the length of the
+ Container to Length. If Length is greater than the original length of
+ Container, the added elements are empty elements.
+so that this operation doesn't shrink the capacity of a vector. (It wasn't
+right in the previous version, either, as it would have raised Constraint_Error
+in that case.)
+
+14) Changed the name of Ensure_Capacity to Reserve_Capacity, as "Reserve" is
+ the name the STL uses, and it seems more descriptive. (See e-mail.)
+
+15) Wording was added to Iterate for each container to say that Program_Error
+is raised if the Process routine calls an operation that will modify or reorder
+the container. Each container needs slightly different wording for various
+reasons (nodes can be reordered in Lists; rehashing in a Map would change the
+order).
+
+This decision grew out of a discussion between Matt and me as to what exactly
+the passive iterator should allow.
+
+We both agreed that trying to implement a passive iterator that could stand
+insertions and deletions of elements was hard. Morevoer, if the user needs to
+do that, they can use an active iterator (that is, a loop with explicit
+cursors) to do so. So, we agreed that inserting or deleting elements from
+within a passive iterator was bad, and there is no need or intent support it.
+
+The main undecided issue is what to do if the user does indeed make a mistake
+and insert or delete an element from the container during a passive iterator.
+There seem to be 4 possibilities:
+
+1) Specified results (it works in some specified way);
+2) Unspecified results (it works, but what it does isn't specified);
+3) Erroneous (anything goes);
+4) Check for bad cases and raise an exception.
+
+(1) is clearly too burdensome on the implementation, and besides, we don't
+ want it.
+(2) would insure that the program wouldn't crash, but otherwise the results
+ wouldn't be portable.
+(3) would allow anything, implementers could ignore the possibility.
+(4) would be the most portable, but there are concerns about overhead.
+
+I originally wrote (2) using the wording: "Which cursors are presented to
+Process is unspecified if..." But that seems to be a burden on implementations
+for little benefit.
+
+I object to (3), because users *will* make this mistake, and likely
+implementations of the iterators would have very bad effects. If the node that
+the iterator was holding onto was deleted, it probably would be
+Unchecked_Deallocated, the memory might be reused, and when the pointers are
+walked, just about anything could happen.
+
+(4) seemed to have too much overhead, but once we stopped trying to support any
+insertion or deletion into the container, the cost became quite reasonable. All
+the implementation of the check would need is a counter (8 bits probably is
+enough) in each container. When an Iterate starts, the counter is incremented;
+when it completes, the counter is decremented. Each of the operations on the
+list of problem operations check that the counter is zero, raising
+Program_Error if the counter is nonzero.
+
+(We don't have to worry about tasking issues, as the container object is inside
+of the Iterate call the entire time. If some other task makes a call during
+that time, we have bad use of shared variables, and we don't care what happens.
+In fact, what will happen is that Program_Error would be raised, which is
+probably a good thing.)
+
+That has very little overhead, because virtually all of the operations in
+question allocate or deallocate memory, and thus are expensive anyway, an
+additional compare and branch will have no visible impact on performance.
+(Sorting and Merging are also expensive; Swap_Links and Splice are the only
+exceptions.) Operations that don't modify the container don't need to make any
+check.
+
+This has the advantage of making passive iterators completely safe against
+problems caused by what container operations are invoked in Process. (Yes,
+calling Unchecked_Deallocation on the container could still cause problems, but
+that is covered by other rules of the language -- and even it would raise
+Program_Error.) It also means that uses of passive iterators are safely
+portable (whereas active iterators could have problems if a dangling cursor was
+used) -- which gives them a clear advantage.
+
+This check is another one that could be dropped in an "unchecked" container.
+
+Thus, I've worded this check into all of the passive iterators.
+
+The wording enumerates the reasons that a check is needed:
+"if Process attempts to insert or delete elements into Container; or"
+
+"modifies Container" would be too broad, as it could include replacing the
+value of an element.
+
+We need also to talk about finalization and about calling Move, as the current
+wording only talks about cursors being passed to operations, not something that
+happens *during* an operation. Moreover, once we decide to have a check,
+including that check in the body of Finalize and Move is not difficult.
****************************************************************
Questions? Ask the ACAA Technical Agent