CVS difference for ais/ai-20302.txt
--- ais/ai-20302.txt 2004/07/31 04:19:42 1.8
+++ ais/ai-20302.txt 2004/09/04 00:48:21 1.9
@@ -1,6 +1,5 @@
-!standard A.17 04-07-30 AI95-00302-03/05
+!standard A.17 04-08-31 AI95-00302-03/06
!class amendment 04-01-14
-!comment Date is provisional.
!status work item 04-01-14
!status received 04-01-14
!priority Medium
@@ -10,11 +9,11 @@
!summary
The following API describes a standard container library for Ada. The library
-comprises sequence containers (vectors), for inserting elements at specified
-positions, and associative containers (sets and maps), which position elements
-in order by key. The library is general, flexible, and efficient, and its
-design has been guided by the philosophy that a library should stay out of the
-programmer's way.
+comprises sequence containers (vectors and lists), for inserting elements at
+specified positions, and associative containers (sets and maps), which position
+elements in order by key. The library is general, flexible, and efficient, and
+its design has been guided by the philosophy that a library should stay out of
+the programmer's way.
!problem
@@ -102,9 +101,10 @@
itself.
The hashed map associative containers scatter keys in the container according
-to a hash function. The hash table is automatically resized when the
-number of elements equals the number of buckets. Insertions and
-searches therefore have a time complexity of O(1) on average.
+to a hash function. The size of the hash table is automatically increased when
+the length of the container equals its capacity (which specifies the length
+before which it is guaranteed that no automatic hash table resizing occurs),
+thus preserving constant time complexity for insertions.
The set associative container maintains elements in sort order. Insertions
and searches have O(log N) time complexity even in the worst case.
@@ -205,12 +205,12 @@
The following major non-limited containers are provided:
* (Expandable) Vectors of any non-limited type;
* Doubly-linked Lists of any non-limited type;
- * Ordered Sets of any non-limited type;
* Hashed Maps keyed by any non-limited type containing any
-non-limited type.
+non-limited type;
+ * Ordered Sets of any non-limited type.
-Separate versions for definite element types are provided, as those can be
-implemented more efficiently.
+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
a container. Cursors generally remain valid as long as the container exists and
@@ -250,7 +250,7 @@
If a container's element type is controlled, the point at which the element
is finalized will depend on the implementation of the container. We do not
-specify precisely where this will happen (it will happen no latter than the
+specify precisely where this will happen (it will happen no later than the
finalization of the container, of course) in order to give implementation's
flexibility to cache, block, or split the nodes of the container. In particular,
Delete does not necessarily finalize the element; the implementation may (or
@@ -307,14 +307,14 @@
The language-defined package Containers.Vectors provides a private type Vector
and a set of operations. A vector container allows insertion and deletion at
any position, but it is specifically optimized for insertion and deletion at
-the back end of the container. A vector container also provides random access
-to its elements.
+the high end (the end with the higher index) of the container. A vector
+container also provides random access to its elements.
A vector container object manages an unconstrained internal array, which
-expands as necessary as items are inserted. The *capacity* of a vector
-corresponds to the total length of the internal array, and the *length*
-of a vector corresponds to the number of active elements in the internal
-array.
+expands as necessary as items are inserted. The *length* of a vector is
+the number of elements that the vector contains. The *capacity* of a vector
+corresponds to the number of elements that can be stored in the internal array,
+and will always be no less than the length of the vector.
A vector container may contain *empty elements*. Empty elements do not have a
specified value.
@@ -326,8 +326,8 @@
when they need sparse structures (there is a Note to this effect at the
end of this subclause).
-The internal array is a virtual structure. There is no requirement for the
-implementation to be a single contiguous array.
+The internal array is a conceptual model of a vector. There is no requirement
+for an implementation to be a single contiguous array.
End AARM Notes.
Static Semantics
@@ -348,6 +348,13 @@
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 Index_Subtype is Index_Type;
type Vector is tagged private;
@@ -358,11 +365,11 @@
No_Element : constant Cursor;
- function To_Vector (Count : Count_Type) return Vector;
+ function To_Vector (Length : Count_Type) return Vector;
function To_Vector
(New_Item : Element_Type;
- Count : Count_Type) return Vector;
+ Length : Count_Type) return Vector;
function "&" (Left, Right : Vector) return Vector;
@@ -379,7 +386,7 @@
function Capacity (Container : Vector) return Count_Type;
procedure Set_Capacity (Container : in out Vector;
- Count : in Count_Type);
+ Capacity : in Count_Type);
function Length (Container : Vector) return Count_Type;
@@ -398,6 +405,15 @@
function Element (Position : Cursor) return Element_Type;
+ procedure Query_Element
+ (Container : in Vector;
+ Index : in Index_Type'Base;
+ Process : not null access procedure (Element : in Element_Type));
+
+ procedure Query_Element
+ (Position : in Cursor;
+ Process : not null access procedure (Element : in Element_Type));
+
procedure Update_Element
(Container : in Vector;
Index : in Index_Type'Base;
@@ -503,20 +519,19 @@
function Last_Element (Container : Vector)
return Element_Type;
- procedure Swap (Container : in Vector;
- I, J : in Index_Type'Base);
+ procedure Swap_Elements (Container : in Vector;
+ I, J : in Index_Type'Base);
- procedure Swap (Container : in out Vector;
- I, J : in Cursor);
+ procedure Swap_Elements (I, J : in Cursor);
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
- procedure Generic_Sort (Container : in Vector);
+ procedure Generic_Sort (Container : in Vector'Class);
- function Find (Container : Vector;
- Item : Element_Type;
- Index : Index_Type'Base := Index_Type'First)
+ function Find_Index (Container : Vector;
+ Item : Element_Type;
+ Index : Index_Type'Base := Index_Type'First)
return Index_Type'Base;
function Find (Container : Vector;
@@ -524,9 +539,9 @@
Position : Cursor := No_Element)
return Cursor;
- function Reverse_Find (Container : Vector;
- Item : Element_Type;
- Index : Index_Type'Base := Index_Type'Last)
+ function Reverse_Find_Index (Container : Vector;
+ Item : Element_Type;
+ Index : Index_Type'Base := Index_Type'Last)
return Index_Type'Base;
function Reverse_Find (Container : Vector;
@@ -534,9 +549,8 @@
Position : Cursor := No_Element)
return Cursor;
- function Is_In (Item : Element_Type;
- Container : Vector)
- return Boolean;
+ function Contains (Container : Vector;
+ Item : Element_Type) return Boolean;
function Next (Position : Cursor) return Cursor;
@@ -549,13 +563,13 @@
function Has_Element (Position : Cursor) return Boolean;
- procedure Iteration
+ procedure Iterate
(Container : in Vector;
- Process : not null access procedure (Element : in out Element_Type));
+ Process : not null access procedure (Position : in Cursor));
- procedure Reverse_Iteration
+ procedure Reverse_Iterate
(Container : in Vector;
- Process : not null access procedure (Element : in out Element_Type));
+ Process : not null access procedure (Position : in Cursor));
private
@@ -574,17 +588,17 @@
Cursor is not otherwise initialized, it will be initialized to the same
value as No_Element.
-function To_Vector (Count : Count_Type) return Vector;
+function To_Vector (Length : Count_Type) return Vector;
-Returns a vector with a length of Count. The vector is filled with empty
+Returns a vector with a length of Length. The vector is filled with empty
elements.
function To_Vector
(New_Item : Element_Type;
- Count : Count_Type) return Vector;
+ Length : Count_Type) return Vector;
-Returns a vector with a length of Count, and elements initialized to the
+Returns a vector with a length of Length, and elements initialized to the
value New_Item.
@@ -615,8 +629,8 @@
function returns False. Otherwise, it compares each element in Left to
the corresponding element in Right using the generic formal equality
operator. If element equality returns False, then this function returns
-False; otherwise, this function returns True. Any exceptions raised
-during evaluation of element equality are propagated.
+False; otherwise, this function returns True. Any exception raised
+during evaluation of element equality is propagated.
function Capacity (Container : Vector) return Count_Type;
@@ -625,15 +639,15 @@
procedure Set_Capacity (Container : in out Vector;
- Count : in Count_Type);
+ Capacity : in Count_Type);
-If Length (Container) > Count, Constraint_Error is raised. Otherwise,
+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 Count, expanding (or contracting) the internal array to hold at least
-Count 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.
+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.
AARM Notes
@@ -707,6 +721,24 @@
Returns the element designated by Position. If Position equals No_Element,
then Constraint_Error is propagated.
+procedure Query_Element
+ (Container : in Vector;
+ Index : in Index_Type'Base;
+ Process : not null access procedure (Element : in Element_Type));
+
+If Index is not in the range First_Index (Container) .. Last_Index (Container),
+then Constraint_Error is propagated. Otherwise, it calls Process.all with the
+element at position Index as the parameter. Any exception raised by Process
+is propagated.
+
+procedure Query_Element
+ (Position : in Cursor;
+ Process : not null access procedure (Element : in Element_Type));
+
+Calls Process.all 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.
+
procedure Update_Element
(Container : in Vector;
Index : in Index_Type'Base;
@@ -714,11 +746,11 @@
If Index is not in the range First_Index (Container) .. Last_Index (Container),
then Constraint_Error is propagated. Otherwise, it calls Process.all with the
-element at position Index as the parameter. Any exceptions raised by Process
-are propagated.
+element at position Index as the parameter. Any exception raised by Process
+is propagated.
If Element_Type is unconstrained and definite, then the Element parameter
-shall be unconstrained.
+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
@@ -740,7 +772,7 @@
raised by Process are propagated.
If Element_Type is unconstrained and definite, then the Element parameter
-shall be unconstrained.
+of Process.all shall be unconstrained.
The element designated by Position is not an empty element after successful
completion of this operation.
@@ -760,7 +792,7 @@
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
+Any exception raised during the assignment is propagated. The element
designated by Position is not an empty element after successful completion of
this operation.
@@ -775,8 +807,8 @@
effect. Otherwise, Assign first calls Clear (Target), then
Set_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 exceptions raised during element
-assignment are propagated.
+of Target to the length of Source. Any exception raised during element
+assignment is propagated.
procedure Move (Target : in out Vector;
@@ -806,14 +838,14 @@
the new length *NL* as the sum of the current length and Length (New_Item); if
the value of Last appropriate for length NL would be greater than
Index_Type'Last then Constraint_Error is propagated. If the value of Before is
-not in the range First_Index (Container) .. Index_Type'Succ (Last_Index
-(Container)), then Constraint_Error is propagated.
+not in the range First_Index (Container) .. Last_Index (Container) + 1, then
+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
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 exceptions raised during the copying are
+positions starting at Before. Any exception raised during the copying is
propagated.
AARM Note
@@ -829,8 +861,9 @@
Before : in Cursor;
New_Item : in Vector);
+If Length(New_Item) is 0, then Insert does nothing.
If Before is No_Element, then is equivalent to Insert (Container,
-Index_Type'Succ (Last_Index (Container)), New_Item); otherwise is
+Last_Index (Container) + 1), New_Item); otherwise is
equivalent to Insert (Container, To_Index (Before), New_Item);
@@ -839,9 +872,10 @@
New_Item : in Vector;
Position : out Cursor);
-Create a temporary (call it Temp_Index) and set it to Index_Type'Succ
-(Last_Index (Container)) if Before equals No_Element, and To_Index (Before)
-otherwise. Then Insert (Container, Before, New_Item) is called, and finally
+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 To_Index (Before) otherwise. Then
+Insert (Container, Before, New_Item) is called, and finally
Position is set to To_Cursor (Container, Temp_Index).
AARM Note: The messy wording because Before is invalidated by Insert, and we
@@ -891,16 +925,14 @@
procedure Append (Container : in out Vector;
New_Item : in Vector);
-Equivalent to Insert (Container, Index_Type'Succ (Last_Index (Container)),
-New_Item).
+Equivalent to Insert (Container, Last_Index (Container) + 1, New_Item).
procedure Append (Container : in out Vector;
New_Item : in Element_Type;
Count : in Count_Type := 1);
-Equivalent to Insert (Container, Index_Type'Succ (Last_Index (Container)),
-New_Item, Count).
+Equivalent to Insert (Container, Last_Index (Container) + 1, New_Item, Count).
procedure Insert_Space (Container : in out Vector;
@@ -916,8 +948,9 @@
Position : out Cursor;
Count : in Count_Type := 1);
-Create a temporary (call it Temp_Index) and set it to
-Index_Type'Succ (Last_Index (Container)) if Before equals No_Element, and
+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
To_Index (Before) otherwise. Then Insert_Space (Container, Temp_Index,
Count) is called, and finally Position is set to To_Cursor (Container,
Temp_Index).
@@ -941,8 +974,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).
+AARM Note: If Index + Count >= Last_Index(Container), this effectively
+truncates the vector (setting Last_Index to Index - 1 and consequently
+setting Length to Index - Index_Type'First).
procedure Delete (Container : in out Vector;
Position : in out Cursor;
@@ -957,11 +991,10 @@
Equivalent to Delete (Container, Index_Type'First, Count).
procedure Delete_Last (Container : in out Vector;
- Count : in Count_Type := 1);
+ Count : in Count_Type := 1);
-If Length (Container) < Count then is equivalent to
-Delete (Container, Index_Type'First, Count); otherwise
-is equivalent to Delete (Container,
+If Length (Container) <= Count then is equivalent to
+Clear (Container); otherwise is equivalent to Delete (Container,
Index_Type'Val(Index_Type'Pos(Last_Index(Container)) - Count + 1), Count).
@@ -984,7 +1017,8 @@
function Last_Index (Container : Vector) return Index_Type'Base;
-Returns the position of the last element in Container.
+If Container is empty, returns Index_Type'First - 1;
+otherwise, returns the position of the last element in Container.
function Last (Container : Vector) return Cursor;
@@ -998,36 +1032,46 @@
Equivalent to Element (Container, Last_Index (Container)).
-procedure Swap (Container : in Vector;
- I, J : in Index_Type'Base);
+procedure Swap_Elements (Container : in Vector;
+ I, J : in Index_Type'Base);
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
-exchanges the values of the elements at positions I and J.
+Last_Index (Container), then Constraint_Error is propagated. Otherwise
+Swap_Elements exchanges the values of the elements at positions I and J.
-AARM Note: To Be Honest: The implementation is not required to actually
+AARM Notes: To Be Honest: The implementation is not required to actually
copy the elements if it can do the swap some other way. But it is allowed
to copy the elements if needed.
-procedure Swap (Container : in Vector;
- I, J : in Cursor);
+procedure Swap_Elements (I, J : in Cursor);
-Equivalent to Swap (Container, To_Index (I), To_Index (J)).
+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.
+AARM Notes:
+After a call to Swap_Elements, I designates the element value previously
+designated by J, and J designates the element value previously
+designated by I. The cursors do not become ambiguous from this operation.
+To Be Honest: The implementation is not required to actually
+copy the elements if it can do the swap some other way. But it is allowed
+to copy the elements if needed.
+End AARM Notes.
+
generic
with function "<" (Left, Right : Element_Type) return Boolean is <>;
-procedure Generic_Sort (Container : in Vector);
+procedure Generic_Sort (Container : in Vector'Class);
Reorders the elements of Container such that the elements are
sorted smallest first as determined by the generic formal "<" operator
-provided. Any exceptions raised during evalution of "<" are propagated.
+provided. Any exception raised during evalution of "<" is propagated.
AARM Notes
This implies swapping the elements, usually including an intermediate copy.
-This of course means that the elements will be copied. Since the elements are
-non-limited, this usually will not be a problem. Note that there is
-Implementation Advice below that the implementation should use
+This means that the elements will usually be copied. (As with Swap_Elements,
+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
a sort that minimizes copying of elements.
The sort is not required to be stable (and the fast algorithm required will
@@ -1036,17 +1080,23 @@
implementation to do that, but it is mostly extra overhead -- usually there
is something already in the element that provides the needed stability.
-function Find (Container : Vector;
- Item : Element_Type;
- Index : Index_Type'Base := Index_Type'First)
+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;
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
-range Index .. Last_Index (Container) equal to Item, then Find returns
-Index_Type'Succ (Last_Index (Container)). Otherwise, it returns the index of
-the matching element.
+range Index .. Last_Index (Container) equal to Item, then Find_Index returns
+Last_Index (Container) + 1. Otherwise, it returns the index of the matching
+element.
function Find (Container : Vector;
Item : Element_Type;
@@ -1060,16 +1110,16 @@
cursor designating the first element found equal to Item. If no such item is
found, it returns No_Element.
-function Reverse_Find (Container : Vector;
- Item : Element_Type;
- Index : Index_Type'Base := Index_Type'Las))
+function Reverse_Find_Index (Container : Vector;
+ Item : Element_Type;
+ Index : Index_Type'Base := Index_Type'Last)
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 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)).
+to Item, then Reverse_Find_Index returns Last_Index (Container) + 1.
Otherwise, it returns the index of the matching element.
function Reverse_Find (Container : Vector;
@@ -1085,9 +1135,8 @@
found, it returns No_Element.
-function Is_In (Item : Element_Type;
- Container : Vector)
- return Boolean;
+function Contains (Container : Vector;
+ Item : Element_Type return Boolean;
Equivalent to Has_Element (Find (Container, Item)).
@@ -1096,14 +1145,14 @@
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
+designates the element with index To_Index (Position) + 1 in the
same vector as Position.
function Previous (Position : Cursor) return Cursor;
If Position equals No_Element or designates the first element of the container,
then Previous returns the value No_Element. Otherwise, returns a cursor that
-designates the element with index Index_Type'Pred (To_Index (Position)) in the
+designates the element with index (To_Index (Position) - 1) in the
same vector as Position.
The procedure Next is equivalent to Position := Next (Position).
@@ -1118,18 +1167,18 @@
designate deleted elements; such cursors are invalid (see below) and any
use of them (including in this routine) is erroneous.
-procedure Iteration
+procedure Iterate
(Container : in Vector;
- Process : not null access procedure (Element : in out Element_Type));
+ Process : not null access procedure (Position : in Cursor));
Invokes Process.all with a cursor that designates each element in Container, in
-index order. Any exceptions raised during Process are propagated.
+index order. Any exception raised by Process is propagated.
-procedure Reverse_Iteration
+procedure Reverse_Iterate
(Container : in Vector;
- Process : not null access procedure (Element : in out Element_Type));
+ Process : not null access procedure (Position : in Cursor));
-Iterates over the nodes in Container as per Iteration, except
+Iterates over the nodes in Container as per Iterate, except
that elements are traversed in reverse order.
@@ -1148,9 +1197,9 @@
Bounded (Run-Time) Errors
-Reading the value of an empty element by calling Element, Update_Element,
-Generic_Sort, "=", Find, or Reverse_Find is a bounded error. The
-implementation may treat the element as having any valid value of the
+Reading the value of an empty element by calling Element, Query_Element,
+Update_Element, Generic_Sort, "=", Find, or Reverse_Find is a bounded error.
+The implementation may treat the element as having any valid value of the
element type, or raise Constraint_Error or Program_Error before modifying the
vector.
@@ -1310,6 +1359,10 @@
function Element (Position : Cursor)
return Element_Type;
+ procedure Query_Element
+ (Position : in Cursor;
+ Process : not null access procedure (Element : in Element_Type));
+
procedure Update_Element
(Position : in Cursor;
Process : not null access procedure (Element : in out Element_Type));
@@ -1357,13 +1410,13 @@
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
- procedure Generic_Sort (Container : in out List);
+ procedure Generic_Sort (Container : in out List'Class);
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
- procedure Generic_Merge (Target : in out List;
- Source : in out List);
+ procedure Generic_Merge (Target : in out List'Class;
+ Source : in out List'Class);
procedure Reverse_List (Container : in out List);
@@ -1393,8 +1446,8 @@
function Last_Element (Container : List)
return Element_Type;
- function Is_In (Item : Element_Type;
- Container : List) return Boolean;
+ function Contains (Container : List;
+ Item : Element_Type) return Boolean;
function Find (Container : List;
Item : Element_Type;
@@ -1416,13 +1469,13 @@
function Has_Element (Position : Cursor) return Boolean;
- procedure Iteration
+ procedure Iterate
(Container : in List;
- Process : not null access procedure (Element : in out Element_Type));
+ Process : not null access procedure (Position : in Cursor));
- procedure Reverse_Iteration
+ procedure Reverse_Iterate
(Container : in List;
- Process : not null access procedure (Element : in out Element_Type));
+ Process : not null access procedure (Position : in Cursor));
private
@@ -1448,8 +1501,8 @@
function returns False. Otherwise, it compares each element in Left to
the corresponding element in Right using the generic formal equality
operator. If element equality returns False, then this function returns
-False; otherwise, this function returns True. Any exceptions raised
-during evaluation of element equality are propagated.
+False; otherwise, this function returns True. Any exception raised
+during evaluation of element equality is propagated.
The function Length returns the number of elements in Container.
@@ -1463,6 +1516,14 @@
Returns the element stored on the node designated by Position. If
Position equals No_Element, then Constraint_Error is propagated.
+procedure Query_Element
+ (Position : in Cursor;
+ Process : not null access procedure (Element : in Element_Type));
+
+If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
+Query_Element invokes Process.all with the element on node designated by
+Position as the argument.
+
procedure Update_Element
(Position : in Cursor;
Process : not null access procedure (Element : in out Element_Type));
@@ -1472,7 +1533,7 @@
Position as the argument.
If Element_Type is unconstrained and definite, then the Element parameter
-shall be unconstrained.
+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
@@ -1505,9 +1566,9 @@
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 node is inserted immediately
-following the last node (if any). Any exceptions raised during allocation of
-internal storage are propagated, and Container is not modified.
+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.
procedure Insert (Container : in out List;
Before : in Cursor;
@@ -1517,10 +1578,10 @@
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 node is inserted immediately
+Before equals No_Element, the new nodes are 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.
+newly-inserted node. Any exception raised during allocation of
+internal storage is propagated, and Container is not modified.
procedure Insert (Container : in out List;
Before : in Cursor;
@@ -1532,7 +1593,7 @@
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
+node. Any exception raised during allocation of internal storage is
propagated, and Container is not modified.
procedure Delete (Container : in out List;
@@ -1542,8 +1603,8 @@
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 exceptions raised during deallocation of internal
-storage are propagated.
+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);
@@ -1561,12 +1622,12 @@
generic
with function "<" (Left, Right : Element_Type) return Boolean is <>;
-procedure Generic_Sort (Container : in out List);
+procedure Generic_Sort (Container : in out List'Class);
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 evaluation of
-"<" are propagated.
+provided. The sort must be stable. Any exception raised during evaluation of
+"<" is propagated.
AARM Notes
Unlike array sorts, we do require stable sorts here. That's because
@@ -1590,8 +1651,8 @@
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.
+after the elements already in Target. Any exception raised during evaluation
+of "<" is propagated, immediately terminating the merge operation.
procedure Reverse_List (Container : in out List);
@@ -1602,6 +1663,14 @@
Swap exchanges the nodes designated by I and J.
+AARM Note: Unlike Swap_Elements for vectors, 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.
+
procedure Splice (Target : in out List;
Before : in Cursor;
Source : in out List);
@@ -1619,7 +1688,7 @@
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 is becomes the predecessor of Before.
+Otherwise the node designated by Position becomes the predecessor of Before.
If Before equals No_Element, then Position is moved after the last node.
procedure Splice (Target : in out List;
@@ -1632,7 +1701,7 @@
equals No_Element, the operation has no effect. Otherwise the node
designated by Position is removed from Source and moved to Target, immediately
prior to Before. If Before equals No_Element, then Position is moved after the
-last node of Container. The length of Target is incremented, and the length of
+last node of Target. The length of Target is incremented, and the length of
Source is decremented.
function First (Container : List) return Cursor;
@@ -1655,8 +1724,8 @@
If Container is empty, then Constraint_Error is propagated. Otherwise,
it returns Element (Last (Container)).
-function Is_In (Item : Element_Type;
- Container : List) return Boolean;
+function Contains (Container : List;
+ Item : Element_Type) return Boolean;
Equivalent to Find (Container, Item) /= No_Element.
@@ -1705,18 +1774,18 @@
designate deleted elements; such cursors are invalid (see below) and any
use of them (including in this routine) is erroneous.
-procedure Iteration
+procedure Iterate
(Container : in List;
- Process : not null access procedure (Element : in out Element_Type));
+ Process : not null access procedure (Position : in Cursor));
Invokes Process.all with a cursor that designates each node in Container. Any
exceptions raised during Process are propagated.
-procedure Reverse_Iteration
+procedure Reverse_Iterate
(Container : in List;
- Process : not null access procedure (Element : in out Element_Type));
+ Process : not null access procedure (Position : in Cursor));
-Iterates over the nodes in Container as per Iteration, except
+Iterates over the nodes in Container as per Iterate, except
that elements are traversed in reverse order.
Erroneous Execution
@@ -1786,7 +1855,7 @@
element associated with that key.
AARM Note: The name is "Hashed_Maps" to allow for a secondary standard
-to include "Sorted_Maps".
+to include "Ordered_Maps".
Static Semantics
@@ -1832,6 +1901,10 @@
function Element (Position : Cursor)
return Element_Type;
+ procedure Query_Element
+ (Position : in Cursor;
+ Process : not null access procedure (Element : in Element_Type));
+
procedure Update_Element
(Position : in Cursor;
Process : not null access procedure (Element : in out Element_Type));
@@ -1846,16 +1919,16 @@
Key : in Key_Type;
New_Item : in Element_Type;
Position : out Cursor;
- Success : out Boolean);
+ Inserted : out Boolean);
- procedure Replace (Container : in out Map;
- Key : in Key_Type;
- New_Item : in Element_Type);
+ 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;
Position : out Cursor;
- Success : out Boolean);
+ Inserted : out Boolean);
procedure Delete (Container : in out Map;
Key : in Key_Type);
@@ -1863,9 +1936,8 @@
procedure Delete (Container : in out Map;
Position : in out Cursor);
- function Is_In (Key : Key_Type;
- Container : Map)
- return Boolean;
+ function Contains (Container : Map;
+ Key : Key_Type) return Boolean;
function Find (Container : Map;
Key : Key_Type)
@@ -1878,7 +1950,7 @@
function Capacity (Container : Map) return Count_Type;
procedure Set_Capacity (Container : in out Map;
- Capacity : in Count_Type);
+ Capacity : in Count_Type);
function First (Container : Map)
return Cursor;
@@ -1902,9 +1974,9 @@
Right : Cursor)
return Boolean;
- procedure Iteration
+ procedure Iterate
(Container : in Map;
- Process : not null access procedure (Element : in out Element_Type));
+ Process : not null access procedure (Position : in Cursor));
private
@@ -1955,17 +2027,52 @@
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.
+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.
+
+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.
+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
+generic formal equality operator give different results, the behavior of this
+package is unspecified.
+
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.
+The implementation is not required to protect against changes to key values
+other than via the operations declared in the Hashed_Maps package.
+
+To see how this could happen, imagine an instantiation of Hashed_Maps where
+the key type is an access-to-variable type and Hash returns a value derived
+from the components of the designated object. Then, any operation that has a
+key value could modify those components and change the hash value:
+ Key (Map).Some_Component := New_Value;
+
+This is really a design error on the part of the user of the map; it shouldn't
+be possible to modify keys stored in a map. But we can't prevent this error
+anymore than we can prevent someone passing as Hash a random number generator.
End AARM Notes
@@ -1997,7 +2104,7 @@
The function Is_Empty is equivalent to Length (Container) = 0.
Clear removes all the elements from Map. The capacity of Map is not affected.
-Any exceptions raised during deallocation of storage propagated.
+Any exception raised during deallocation of storage is propagated.
function Element (Position : Cursor) return Element_Type;
@@ -2005,6 +2112,14 @@
If Position equals No_Element, then Constraint_Error is propagated.
Otherwise, this operation returns the element designated by Position.
+procedure Query_Element
+ (Position : in Cursor;
+ Process : not null access procedure (Element : in Element_Type));
+
+If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
+Query_Element invokes Process.all with the element on node designated by
+Position as the argument.
+
procedure Update_Element
(Position : in Cursor;
Process : not null access procedure (Element : in out Element_Type));
@@ -2013,6 +2128,13 @@
Update_Element invokes Process.all with the element designated by Position as
the argument.
+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.
+
procedure Replace_Element (Position : in Cursor;
By : in Element_Type);
@@ -2034,20 +2156,19 @@
Key : in Key_Type;
New_Item : in Element_Type;
Position : out Cursor;
- Success : out Boolean);
+ 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
-Container. If a key matches, Success returns False and Position designates the
+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. Success returns
-True and Position designates the newly-inserted node. Any exceptions raised
-during allocation are propagated and Container is not modified.
+initializes it to Key and New_Item, and adds it to Container. Inserted returns
+True and Position designates the newly-inserted node. Any exception raised
+during allocation is propagated and Container is not modified.
AARM Notes:
-Insert should only compare elements that hash to the same bucket in the hash
-table.
+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
expansion operations (which are potentially expensive). Moreover, expansion can
@@ -2056,22 +2177,33 @@
next expansion, not later ones.
End AARM Notes.
-procedure Replace (Container : in out Map;
- Key : in Key_Type;
- New_Item : in Element_Type);
+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.
-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.
+AARM Note: This is equivalent to:
+ declare
+ Inserted : Boolean; C : Cursor;
+ begin
+ Insert (Container, Key, New_Item, Inserted => Inserted, Position => C);
+ if not Inserted then
+ Replace_Element (Container, C, New_Item);
+ end if;
+ end;
+but is much more convinient, as there are no out parameters to deal with.
procedure Insert (Container : in out Map;
Key : in Key_Type;
Position : out Cursor;
- Success : out Boolean);
+ Inserted : out Boolean);
Inserts Key into Container as per Insert (Container, Key, New_Item,
-Position, Success), with the difference that an object initialized with any
+Position, Inserted), 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.
@@ -2083,7 +2215,7 @@
deallocates the node.
AARM Notes:
-Delete should only compare elements that hash to the same bucket in the hash
+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.
procedure Delete (Container : in out Map;
@@ -2103,21 +2235,20 @@
returns No_Element.
AARM Note:
-Find should only compare elements that hash to the same bucket in the hash
-table.
+Find should only compare keys that hash to the same bucket in the hash table.
-The function Is_In is equivalent to Find (Container, Key) /= No_Element.
+The function Contains is equivalent to Find (Container, Key) /= No_Element.
The function Element is equivalent to Element (Find (Container, Key)).
The function Capacity returns the capacity of Container.
procedure Set_Capacity (Container : in out Map;
- Count : in Count_Type);
+ Capacity : in Count_Type);
-If Length (Container) > Count, then Constraint_Error is propogated.
-Otherwise, it allocates a new hash table such that the length of the
-resulting map can become at least the value Count without requiring an
+If Capacity < Length (Container), Constraint_Error is raised. Otherwise,
+Set_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
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
@@ -2138,7 +2269,7 @@
function First (Container : Map) return Cursor;
If Length (Container) = 0, then First returns No_Element. Otherwise,
-it returns a cursor that designates the first hashed node in Container.
+First returns a cursor that designates the first hashed node in Container.
AARM Note:
In a typical implementation, this will be the first node in the lowest numbered
@@ -2147,8 +2278,8 @@
function Next (Position : Cursor) return Cursor;
Returns a cursor that designates the node that immediately follows
-Position. If there are no more nodes in the map identified by Position, it
-returns No_Element. If Position equals No_Element, then No_Element
+Position. If there are no more nodes in the map identified by Position, then
+No_Element is returned. If Position equals No_Element, then No_Element
is returned.
If there are no other intervening operations, calling Next in a loop
@@ -2191,19 +2322,12 @@
equivalent to Is_Equal_Key (Left, Key (Right)).
-procedure Iteration
+procedure Iterate
(Container : in Map;
- Process : not null access procedure (Element : in out Element_Type));
+ Process : not null access procedure (Position : in Cursor));
-Iteration calls Process.all with a cursor that designates each node
-in the Container. Any exceptions raised during 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.
+Iterate calls Process.all with a cursor that designates each node
+in the Container. Any exception raised by Process is propagated.
Legality Rules
@@ -2307,14 +2431,21 @@
function Element (Position : Cursor) return Element_Type;
+ procedure Query_Element
+ (Position : in Cursor;
+ Process : not null access procedure (Element : in Element_Type));
+
procedure Move (Target : in out Set;
Source : in out Set);
procedure Insert (Container : in out Set;
New_Item : in Element_Type;
Position : out Cursor;
- Success : out Boolean);
+ Inserted : out Boolean);
+ procedure Insert (Container : in out Set;
+ New_Item : in Element_Type);
+
procedure Delete (Container : in out Set;
Item : in Element_Type);
@@ -2354,17 +2485,13 @@
function "xor" (Left, Right : Set) return Set renames
Symmetric_Difference;
- function Is_Subset (Item : Set;
- Container : Set)
- return Boolean;
+ function Is_Disjoint (Left, Right : Set) return Boolean;
- function Is_Disjoint (Item : Set;
- Container : Set)
- return Boolean;
+ function Is_Subset (Subset : Set;
+ Of_Set : Set) return Boolean;
- function Is_In (Item : Element_Type;
- Container : Set)
- return Boolean;
+ function Contains (Container : Set;
+ Item : Element_Type) return Boolean;
function Find (Container : Set;
Item : Element_Type)
@@ -2372,11 +2499,11 @@
function Floor (Container : Set;
Item : Element_Type)
- return Cursor_Type;
+ return Cursor;
function Ceiling (Container : Set;
Item : Element_Type)
- return Cursor_Type;
+ return Cursor;
function First (Container : Set) return Cursor;
@@ -2412,13 +2539,13 @@
function ">" (Left : Element_Type; Right : Cursor)
return Boolean;
- procedure Iteration
+ procedure Iterate
(Container : in Set;
- Process : not null access procedure (Element : in out Element_Type));
+ Process : not null access procedure (Position : in Cursor));
- procedure Reverse_Iteration
+ procedure Reverse_Iterate
(Container : in Set;
- Process : not null access procedure (Element : in out Element_Type));
+ Process : not null access procedure (Position : in Cursor));
generic
@@ -2434,9 +2561,8 @@
package Generic_Keys is
- function Is_In (Key : Key_Type;
- Container : Set)
- return Boolean;
+ function Contains (Container : Set;
+ Key : Key_Type) return Boolean;
function Find (Container : Set;
Key : Key_Type)
@@ -2444,11 +2570,13 @@
function Floor (Container : Set;
Item : Key_Type)
- return Cursor_Type;
+ return Cursor;
function Ceiling (Container : Set;
Item : Key_Type)
- return Cursor_Type;
+ return Cursor;
+
+ function Key (Position : Cursor) return Key_Type;
function Element (Container : Set;
Key : Key_Type)
@@ -2469,9 +2597,10 @@
function ">" (Left : Key_Type; Right : Cursor)
return Boolean;
- procedure Update_Element
- (Position : in Cursor;
- Process : not null access procedure (Element : in out Element_Type));
+ procedure Checked_Update_Element
+ (Container : in out Set;
+ Position : in Cursor;
+ Process : not null access procedure (Element : in out Element_Type));
end Generic_Keys;
@@ -2505,7 +2634,28 @@
logically pure functions), or the behavior is unspecified.
End AARM Notes
+If the value of an element stored in a set is changed other than by an
+operation in this package such that at least one of "<" or "=" give different
+results, the behavior of this package is unspecified.
+
+AARM Notes
+The implementation is not required to protect against changes to element values
+other than via the operations declared in the Ordered_Sets package.
+
+To see how this could happen, imagine an instantiation of Ordered_Sets package
+where the element type is an access-to-variable type and "<" returns a value
+derived from comparing the components of the designated objects. Then, any
+operation that has a element value (even if the element value is constant)
+could modify those components and change the result of "<":
+ Element (Set).Some_Component := New_Value;
+
+This is really a design error on the part of the user of the set; it shouldn't
+be possible to modify elements stored in a set such that "<" changes. But we
+can't prevent this error anymore than we can prevent someone passing as "<"
+a routine that produces random answers.
+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.
@@ -2536,6 +2686,14 @@
If Position equals No_Element, then Constraint_Error is propagated.
Otherwise, it returns the element designated by Position.
+procedure Query_Element
+ (Position : in Cursor;
+ Process : not null access procedure (Element : in Element_Type));
+
+If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
+Query_Element invokes Process.all with the element on node designated by
+Position as the argument.
+
procedure Move (Target : in out Set;
Source : in out Set);
@@ -2547,15 +2705,24 @@
procedure Insert (Container : in out Set;
New_Item : in Element_Type;
Position : out Cursor;
- Success : out Boolean);
+ Inserted : out Boolean);
+
+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, Inserted is False and Position designates the element.
+Otherwise, it allocates a new element which is initialized to New_Item.
+Inserted returns True and Position designates the newly-inserted element. Any
+exception raised during allocation and initialization is propagated and
+Container is not modified.
-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, Success is False and Position
-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.
+procedure Insert (Container : in out Set;
+ New_Item : in Element_Type);
+
+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
+allocation and initialization is propagated and Container is not modified.
procedure Delete (Container : in out Set;
@@ -2648,22 +2815,23 @@
not equivalent to the corresponding elements of Left.
-function Is_Subset (Item : Set;
- Container : Set)
- return Boolean;
+function Is_Disjoint (Left, Right : Set) return Boolean;
-If an element of Item is not equivalent to some element of
-Container, the function returns False. Otherwise it returns True.
+If an element of Left is equivalent to some element of Right, then
+Is_Disjoint returns False. Otherwise it returns True.
+AARM Note: This operation is communitive.
-function Is_Disjoint (Item : Set;
- Container : Set)
- return Boolean;
+function Is_Subset (Subset : Set;
+ Of_Set : Set) return Boolean;
-If an element of Item is equivalent to some element of Container, then
-Is_Disjoint returns False. Otherwise it returns True.
+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
+make it clear in named notation which set is which.
+
function Find (Container : Set;
Item : Element_Type) return Cursor;
@@ -2671,11 +2839,11 @@
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.
+The function Contains is equivalent to Find (Set, Item) /= No_Element.
function Floor (Container : Set;
Item : Element_Type)
- return Cursor_Type;
+ return Cursor;
The Floor operation searches for the largest element not greater than Item,
using the generic formal less-than operator for elements. If there is an
@@ -2684,7 +2852,7 @@
function Ceiling (Container : Set;
Item : Element_Type)
- return Cursor_Type;
+ return Cursor;
The Ceiling operation searches for the smallest element not less
than Item, using the generic formal less-than operator for elements. If there
@@ -2751,17 +2919,17 @@
The function ">" (Left : Element_Type; Right : Cursor) is
equivalent to Element (Right) < Left.
-procedure Iteration
+procedure Iterate
(Container : in Set;
- Process : not null access procedure (Element : in out Element_Type));
+ Process : not null access procedure (Position : in Cursor));
Invokes Process.all with a cursor that designates each element in Container.
-procedure Reverse_Iteration
+procedure Reverse_Iterate
(Container : in Set;
- Process : not null access procedure (Element : in out Element_Type));
+ Process : not null access procedure (Position : in Cursor));
-Iterates over the elements in Container as per Iteration, with the
+Iterates over the elements in Container as per Iterate, with the
difference that the nodes are traversed in reverse order.
The package Generic_Keys provides operations that allow set manipulation
@@ -2778,23 +2946,30 @@
the package is not required to do anything that makes sense.
-The operations in package Generic_Keys named Is_In, Find, Floor, Ceiling,
+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
Generic_Keys generic formal relational operators.
-procedure Update_Element
- (Position : in Cursor;
- Process : not null access procedure (Element : in out Element_Type));
+function Key (Position : Cursor) return Key_Type;
+If Position equals No_Element, then Constraint_Error is propagated.
+Otherwise, this operation returns the key obtained by calling the generic
+formal Key operation on the element designated by Position.
+
+procedure Checked_Update_Element
+ (Container : in out Set;
+ Position : in Cursor;
+ Process : not null access procedure (Element : in out Element_Type));
+
If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
-Update_Element uses Key to save the key value (KB) of the element.
-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.
+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.
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
@@ -2803,6 +2978,13 @@
expensive and defeat the purpose of this routine (which is cheap, in-place
modifications).
+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.
+
Legality Rules
An instantiation of Containers.Ordered_Sets shall be at the library level.
@@ -2940,7 +3122,7 @@
procedure Insert (Container : in out Map;
Key : in Key_Type;
Position : out Cursor;
- Success : out Boolean);
+ Inserted : out Boolean);
is omitted.
AARM Note: This procedure is omitted because there is no way to create a
@@ -2970,8 +3152,9 @@
* The generic formal Element_Type is indefinite.
- * The Element parameter of access subprogram Process of Update_Element
- may be constrained even if Element_Type is unconstrained.
+ * The Element parameter of access subprogram Process of
+ Checked_Update_Element may be constrained even if Element_Type is
+ unconstrained.
A.17.10 Array Sorting
@@ -2979,6 +3162,7 @@
The language-defined procedures Containers.Generic_Array_Sort and
Containers.Generic_Constrained_Array_Sort provide sorting on
arbitrary array types.
+
Static Semantics
The procedure Containers.Generic_Array_Sort has the following declaration:
@@ -2990,10 +3174,11 @@
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
procedure Ada.Containers.Generic_Array_Sort (Container : in out Array_Type);
+ pragma Pure (Ada.Containers.Generic_Array_Sort);
Reorders the elements of Container such that the elements are
sorted smallest first as determined by the generic formal less-than operator
-provided. Any exceptions raised during evaluation of less-than are propagated.
+provided. Any exception raised during evaluation of less-than is propagated.
AARM Notes
This implies swapping the elements, usually including an intermediate copy.
@@ -3019,10 +3204,11 @@
return Boolean is <>;
procedure Ada.Containers.Generic_Constrained_Array_Sort
(Container : in out Array_Type);
+ pragma Pure (Ada.Containers.Generic_Constrained_Array_Sort);
Reorders the elements of Container such that the elements are
sorted smallest first as determined by the generic formal less-than operator
-provided. Any exceptions raised during evaluation of less-than are propagated.
+provided. Any exception raised during evaluation of less-than is propagated.
Implementation Advice
@@ -3054,7 +3240,7 @@
procedure Copy (A : Array_Subtype) is
V : Vector;
begin
- Set_Capacity (V, Count => A'Length);
+ Set_Capacity (V, Capacity => A'Length);
for I in A'Range loop
Append (V, New_Item => A (I));
@@ -3070,6 +3256,30 @@
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
+is to declare the vector object with the requisite length immediately:
+
+ procedure Copy (A : Array_Subtype) is
+ V : Vector := To_Vector (Count => A'Length);
+ J : Index_Subtype'Base := Index_Subtype'First;
+ begin
+ for I in A'Range loop
+ Replace_Element (V, Index => J, By => A (I));
+ J := J + 1;
+ end loop;
+ ...
+ end Copy;
+
+Here the elements of the vector are initialized to an "empty" value.
+When the element value is replaced using Replace_Element, the state of
+the element changes from empty to non-empty.
+
+The procedure Set_Length can be used to change the length of a vector
+outside of a declarative region. (One could use To_Vector too, of
+course, but it's more efficient to use Set_Length, since that operation
+allocates a new array only if the capacity of the existing array is too
+small.)
+
You can use a vector to implement a stack in the traditional way:
package Stacks is new Ada.Containers.Vectors (ET);
@@ -3154,22 +3364,6 @@
The internal array that belonged to V is deallocated, and the null (or
otherwise small) array of V2 is moved into V.
-Similarly, if for whatever reason you want more efficient use of
-storage, you can use Move to allocate an array having the minimum capacity
-necessary to store the active elements:
-
- procedure Reclaim_Storage (V : in out Vector) is
- Temp : Vector := V;
- begin
- Clear (V);
- Move (Target => V, Source => Temp);
- end;
-
-This operation first copies all active elements in V to the temporary
-vector object Temp, which is allocated using a smaller internal array
-(presumably the smallest capacity necessary to store the elements, according
-to whatever algorithm the implementor has chosen). The new, smaller
-array from Temp is then moved into V.
These, however, are exceptional cases. Usually it is best to ignore the
existence of the internal array altogther, and just let the container
@@ -3220,6 +3414,7 @@
begin
while Has_Element (I) loop
Process (E => Element (I));
+ Next (I);
end loop;
end Op;
@@ -3235,7 +3430,7 @@
end;
begin
- Iteration (V, Process'Access);
+ Iterate (V, Process'Access);
end Op;
The Update_Element operation is very important, as it allows
@@ -3257,35 +3452,7 @@
Update_Element (V, Index => I, Process => Process'Access);
end;
-It's often the case that during an insertion you don't have an item
-value to assign to the new element, and instead you want simply to
-reserve space for an element and then modify it directly. For example:
-
- procedure Op (V : in out Vector) is
- procedure Process (E : in out ET) is
- begin
- ... -- manipulate E as appropriate
- end;
-
- C : Cursor;
- Empty : ET; -- A default-initialized object of ET.
- begin
- Insert -- Allocate the element
- (Container => V,
- Before => No_Element, -- Insert at back end
- New_Item => Empty,
- Position => C); -- Return value
-
- Update_Element (Position => C, Process => Process'Access);
- -- Give element a value
- end Op;
-
-We insert a default-initialized object so that the initial state of the
-item is known. If we didn't need that, we could have used Insert_Space and
-Replace_Element instead.
-
-
If we have a container whose elements are vectors, we can use
Update_Element in combination with Move to insert a vector onto the
container without actually copying the vector. (Actually, this is true
@@ -3301,12 +3468,14 @@
Move (Target => E, Source => V);
end;
- C : Cursor;
begin
Append (V, New_Item => E);
... -- populate vector some more
- Insert (L, Before => No_Element, New_Item => Empty_Vector, Position => C);
- Update_Element (C, Move_V'Access); -- Move V to position C of list L
+
+ Append (L, New_Item => Empty_Vector);
+
+ -- Move (don't copy) vector V onto list L:
+ Update_Element (Last (L), Move_V'Access);
end;
A new, default-initialized vector element is appended to L by
@@ -3340,7 +3509,7 @@
having to allocate a new one. This is exactly how Assign works.
-A.17.3 The Package Containers.Doubly_Linked_List
+A.17.3 The Package Containers.Doubly_Linked_Lists
You can use a doubly-linked list to implement a queue in the traditional
way:
@@ -3392,6 +3561,7 @@
of the list, at which point the cursor assumes the distinguished value
No_Element, and Has_Element returns False.
+
All of the containers have an operation to swap a pair of elements in
the container:
@@ -3399,7 +3569,7 @@
(V : in out Vector_Of_Lists.Vector;
I, J : in Index_Type'Base) is
begin
- Swap (V, I, J); -- vector operation
+ Vector_Of_Lists.Swap (V, I, J); -- vector operation
end;
For the definite form (the case here), this will make a copy of the
@@ -3431,7 +3601,7 @@
end Swap;
To do the swap, we need direct visibility to both objects, so nested
-instantiations are required. We first move the list element at index I
+process procedures are required. We first move the list element at index I
of the vector into a temporary. This allows another vector to by copied
into that index position. We do that, moving the list element at index
J into (empty) list element at index I. We then move the temporary
@@ -3439,6 +3609,30 @@
index position J.
+It's often the case that during an insertion you don't have an item
+value to assign to the new element, and instead you want simply to
+insert a new element (initialized to the default value for its type, if
+applicable) and then modify it directly. For example:
+
+ procedure Op (L : in out List) is
+
+ procedure Process (E : in out ET) is
+ begin
+ ... -- manipulate E as appropriate
+ end;
+
+ C : Cursor;
+ begin
+ Insert -- Allocate new element
+ (Container => L,
+ Before => No_Element, -- Insert at back end
+ Position => C); -- Return value
+
+ -- Modify default-initialized value:
+ Update_Element (C, Process'Access);
+ end Op;
+
+
A.17.4 The Package Containers.Hashed_Maps
It's often the case that you know apriori the total number of elements
@@ -3452,9 +3646,9 @@
M : Map_Types.Map; -- Capacity = 0 (or small)
Position : Map_Types.Cursor;
- Success : Boolean;
+ Inserted : Boolean;
begin
- Set_Capacity (M, Count => N); -- Capacity >= N
+ Set_Capacity (M, Capacity => N); -- Capacity >= N
for I in 1 .. N loop
Insert -- no expansion and rehashing will occur
@@ -3462,23 +3656,13 @@
Key => New_Key (I),
New_Item => New_Element (I),
Position => Position,
- Success => Success);
+ Inserted => Inserted);
end loop;
...
end Op;
Note that Clear doesn't delete the internal hash table -- it just
-deletes the nodes hanging off the hash table. Neither does
-Set_Capacity (Map, 0), as that is defined as specifying a lower bound for the
-capacity. If you want to delete the internal hash table too (thus setting the
-map's capacity to 0), then you can use Move with a temporary map object:
-
- procedure Clear_And_Deallocate (M : in out Map) is
- Temp : Map;
- begin
- Clear (M);
- Move (Target => M, Source => Temp);
- end;
+deletes the nodes hanging off the hash table.
The simplest and fastest way to iterate over all the elements in the map
is to use a passive iterator:
@@ -3493,7 +3677,7 @@
end;
begin
- Iteration (M, Process'Access);
+ Iterate (M, Process'Access);
end;
You could of course implement this function yourself, by iterating over
@@ -3629,7 +3813,7 @@
Session : constant Session_Access := new Session_Type;
Position : FD_Map_Types.Cursor;
- Success : Boolean;
+ Inserted : Boolean;
begin
Open (Session.Socket, ...);
@@ -3638,7 +3822,7 @@
Key => FD (Session.Socket),
New_Item => Session,
Position => Position,
- Success => Success);
+ Inserted => Inserted);
...
return Session;
end;
@@ -3672,7 +3856,7 @@
new Ada.Containers.Indefinite_Hashed_Maps
(Key_Type => String,
Element_Type => Natural,
- Hash => Ada.Strings.Hash_String); -- case-sensitive
+ Hash => Ada.Strings.Hash); -- case-sensitive
Wordcount_Map : Wordcount_Maps.Map;
@@ -3714,7 +3898,7 @@
end;
Position : Wordcount_Maps.Cursor;
- Success : Boolean;
+ Inserted : Boolean;
begin -- Insert
@@ -3723,7 +3907,7 @@
Key => To_Lower (Word),
New_Item => 0, -- yes
Position => Position,
- Success => Success);
+ Inserted => Inserted);
Update_Element (Position, Increment'Access);
@@ -3736,7 +3920,7 @@
This is deliberate. What happens is that if the word is already in the
map, then the insertion "fails" in the sense that no new node is
allocated. Rather, Insert reports the fact that the key was already in
-the map (by returning the value False for Success), and a cursor that
+the map (by returning the value False for Inserted), and a cursor that
designates the node with the matching key.
But not inserting a new node is exactly the behavior we want. In the
@@ -3767,7 +3951,7 @@
Put (Key (C)); Put (':'); Put (Element (C)); New_Line;
end;
begin
- Iteration (Map, Process'Access);
+ Iterate (Map, Process'Access);
end;
This would display the words in their order in the hashed map. That's
@@ -3793,7 +3977,7 @@
begin -- Print_Results
- Iteration (Histogram, Process'Access); -- Populate array
+ Iterate (Histogram, Process'Access); -- Populate array
... -- see below
@@ -3802,8 +3986,7 @@
Here we use the passive iterator for maps to populate the array. As
with all containers, it's usually simpler and more efficient to use a
passive iterator if you're going to traverse all the elements in the
-container. The library is often used by making a lot of little
-on-the-fly passive-iterator instantiations, as above.
+container.
We now need to sort the array of cursors, and to do that we need an
order relation for cursors. We want to sort the elements in reverse
@@ -3906,7 +4089,7 @@
Position : File_Cache_Types.Cursor :=
Find (File_Cache, Key => Name);
- Success : Boolean;
+ Inserted : Boolean;
Context : Context_Access;
begin -- Setup
@@ -3922,7 +4105,7 @@
Key => Name,
New_Item => Context,
Position => Cursor,
- Success => Success);
+ Inserted => Inserted);
else
@@ -3952,7 +4135,7 @@
Key => Name,
New_Item => null, -- yes
Position => Position,
- Success => Not_In_Cache);
+ Inserted => Not_In_Cache);
if Not_In_Cache then
@@ -4039,7 +4222,7 @@
new Ada.Containers.Indefinite_Hashed_Maps
(Key_Type => String,
Element_Type => Session_Access,
- Hash => Ada.Strings.Hash_String); -- case-sensitive
+ Hash => Ada.Strings.Hash); -- case-sensitive
Id_Map : Id_Maps.Map;
use Id_Maps;
@@ -4051,7 +4234,7 @@
Session : constant Session_Access := new Session_Type;
Position : Id_Map_Types.Cursor;
- Success : Boolean;
+ Inserted : Boolean;
begin
Generate_Id (Session.Id);
@@ -4060,7 +4243,7 @@
Key => Session.Id,
New_Item => Session,
Position => Position,
- Success => Success);
+ Inserted => Inserted);
...
return Session;
end;
@@ -4112,7 +4295,7 @@
function Setup_Session return Session_Access is
Session : constant Session_Access := new Session_Type;
- Success : Boolean;
+ Inserted : Boolean;
begin
Generate_Id (Session.Id);
@@ -4121,9 +4304,9 @@
Key => Session.Id,
New_Item => Session,
Position => Session.Id_Map_Position,
- Success => Success);
+ Inserted => Inserted);
- pragma Assert (Success);
+ pragma Assert (Inserted);
pragma Assert (Key (Session.Id_Map_Position) = Session.Id);
pragma Assert (Element (Session.Id_Map_Position) = Session);
...
@@ -4170,7 +4353,7 @@
begin -- Shutdown_Sessions
- Iteration (Id_Map, Process'Access); -- Free all sessions.
+ Iterate (Id_Map, Process'Access); -- Free all sessions.
Clear (Id_Map);
@@ -4181,6 +4364,82 @@
which sets its length to 0.
+In other examples, we have been silent about the operation of
+Generate_Id, which makes a session id for us comprising a sequence of 8
+random characters. One of our requirements for a session id is that it
+must be unique among all the sessions currently being streamed by this
+server.
+
+Even if we use a random number generator to synthesize characters, we
+still must check to ensure that this session id is unique. The obvious
+way is to use Find to see if it's in the map already:
+
+ procedure Generate_Id (Id : out Id_Subtype) is
+ Position : Id_Maps.Cursor;
+ begin
+ loop
+ Synthesize_Random_String (Id);
+ Position := Find (Id_Map, Key => Id);
+ exit when Position = No_Element; -- good: not found
+ end loop;
+ end Generate_Id;
+
+The constructor for session objects generates a unique session id, and
+then uses the id as the key when inserting the new session object:
+
+ function Setup_Session return Session_Access is
+
+ I : Id_Maps.Cursor;
+ B : Boolean;
+
+ Session : Session_Access := new Session_Type;
+ begin
+ Generate_Id (Session.Id); -- Id is guaranteed to be unique
+
+ Insert
+ (Container => Id_Map,
+ Key => Session.Id,
+ Element => Session,
+ Position => I,
+ Inserted => B);
+ ...
+ end Setup_Session;
+
+One issue with this algorithm is that Insert duplicates the work done
+just earlier by Find, when checking the newly-synthesized id for
+uniqueness. A simpler way to efficiently generate a unique session id
+and insert it into the map is to just check whether the insertion
+succeeded:
+
+ function Setup_Session return Session_Access is
+
+ Position : Id_Maps.Cursor;
+ Inserted : Boolean;
+
+ Id : Id_Subtype;
+
+ begin -- Setup_Session
+
+ loop
+
+ Generate_Id (Id);
+
+ Insert
+ (Container => Id_Map,
+ Key => Id,
+ Position => Position,
+ Inserted => Inserted);
+
+ exit when Inserted;
+
+ end loop;
+ ...
+ end Setup_Session;
+
+Here we don't need a separate call to Find, because the regular Insert
+operation does a search anyway.
+
+
A.17.5 The Package Containers.Ordered_Sets
Suppose we have a set and want to copy the elements from the set into an
@@ -4238,7 +4497,7 @@
end;
begin
- Iteration (S, Fill_Element_of_A'Access);
+ Iterate (S, Fill_Element_of_A'Access);
...
end Op;
@@ -4283,13 +4542,13 @@
new Connect_Type;
Position : Connection_Sets.Cursor;
- Success : Boolean;
+ Inserted : Boolean;
begin
Insert
(Container => Connection_Set,
New_Item => Connection,
Position => Position,
- Success => Success);
+ Inserted => Inserted);
...
return Connection;
end;
@@ -4329,99 +4588,22 @@
Another technique would be to use an active iterator, like this:
procedure Shutdown_Connections is
- I : Cursor := First (Connection_Set);
+ I : Cursor;
X : Connection_Access;
begin
- while Has_Element (I) loop
+ while not Is_Empty (Connection_Set) loop
+ I := First (Connect_Set);
X := Element (I);
- Delete (Connection_Set, Position => I); --increments I
+ Delete (Connection_Set, Position => I);
Free (X);
end loop;
end Shutdown_Connections;
-Here we use the cursor-form of Delete. Delete returns the successor of
-the cursor deleted, so eventually the loop terminates. (There is also a
-Delete_Sans_Increment operation, that does not increment the cursor.
-This is more efficient since it doesn't perform the tree traversal that
-would be necessary to find the successor. In this example, however, the
-loop depends on the cursor being incremented, so we use the canonical
-form of Delete.)
+Here we use the cursor-form of Delete. This is probably more efficient
+than using the item-form of Delete, since the cursor-form doesn't have
+to search for the item.
-In other examples, we have been silent about the operation of
-Generate_Id, which makes a session id for us comprising a sequence of 8
-random characters. One of our requirements for a session id is that it
-must be unique among all the sessions currently being streamed by this
-server.
-
-Even if we use a random number generator to synthesize characters, we
-still must check to ensure that this session id is unique. The obvious
-way is to use Find to see if it's in the already:
-
- procedure Generate_Id (Id : out Id_Subtype) is
- Position : Id_Maps.Cursor;
- begin
- loop
- Synthesize_Random_String (Id);
- Position := Find (Id_Map, Key => Id);
- exit when Position = No_Element; -- good: not found
- end loop;
- end Generate_Id;
-
-The constructor for session objects generates a unique session id, and
-then uses the id as the key when inserting the new session object:
-
- function Setup_Session return Session_Access is
-
- I : Id_Maps.Cursor;
- B : Boolean;
-
- Id : Id_Subtype;
- begin
- Generate_Id (Id); -- Id is guaranteed to be unique
-
- Insert
- (Container => Id_Map,
- Key => Id,
- Position => I,
- Success => B);
- ...
- end Setup_Session;
-One issue with this algorithm is that Insert duplicates the work done
-just earlier by Find, when checking the newly-synthesized id for
-uniqueness. A simple way to efficiently generate a unique session id
-and insert it into the map is to just check whether the insertion
-succeeded:
-
- function Setup_Session return Session_Access is
-
- Position : Id_Maps.Cursor;
- Success : Boolean;
-
- Id : Id_Subtype;
-
- begin -- Setup_Session
-
- loop
-
- Generate_Id (Id);
-
- Insert
- (Container => Id_Map,
- Key => Id,
- Position => Position,
- Success => Success);
-
- exit when Success;
-
- end loop;
- ...
- end Setup_Session;
-
-Here we don't need a separate call to Find, because the regular Insert
-operation does a search anyway.
-
-
One of the canonical container examples is the set-of-employees.
Suppose we have an employee type defined this way:
@@ -4457,12 +4639,12 @@
Employee : Employee_Type;
Position : Employee_Sets.Cursor;
- Success : Boolean;
+ Inserted : Boolean;
begin
Employee.SSN := SSN;
Employee.Name := Name;
...
- Insert (Employees, Employee, Position, Success);
+ Insert (Employees, Employee, Position, Inserted);
end;
Now let's suppose that we need to modify some information for an
@@ -4493,7 +4675,8 @@
But this is kind of a hack. I don't really want to make a dummy element
just to look up the real element. For many types synthesizing a dummy
-object this way might not even be possible.
+object this way might not even be possible (say, because the type is private
+and you only have visibility to the partial view of the type).
A much more elegant technique is to use the nested generic package
Generic_Keys, which allows you to explicitly name the key-part of the
@@ -4513,8 +4696,14 @@
return Employee.SSN > SSN;
end;
+ function SSN (Employee : Employee_Type) return SSN_Type is
+ begin
+ return Employee.SSN;
+ end;
+
package SSN_Keys is
- new Employee_Sets.Generic_Keys (SSN_Type); --accept defaults
+ new Employee_Sets.Generic_Keys (SSN_Type, Key => SSN);
+ -- Use defaults for other parameters
With this new package we can now look up the employee by his SSN
directly:
@@ -4528,31 +4717,132 @@
if Has_Element (Position) then ...;
end;
+To actually change the employee's address in the example above, we use
+the special element modifier operation:
+
+ procedure Change_Address
+ (SSN : SSN_Type;
+ New_Home : Home_Address_Type) is
+
+ procedure Set_Home
+ (Employee : in out Employee_Type) is
+ begin
+ Employee.Home := New_Home;
+ end;
+
+ Position : Cursor := Find (Employees, Key => SSN);
+ begin
+ if Has_Element (Position) then
+ SSN_Keys.Checked_Update_Element
+ (Position => Position,
+ Process => Set_Home'Address);
+ ...
+ end if;
+ end Change_Address;
+
+Modifying a set element requires special handling, since a set orders
+its elements by key. Indiscriminate changes to element values are
+therefore not allowed, as this would break the set abstraction if the
+order relation were changed. The operation Checked_Update_Element
+allows the element to be modified, but it checks to determine whether
+the key has changed, and if so it moves the element to a new position
+that preserves the order relation among existing elements. In this
+example we only modify the Home component of the Element_Type record, so
+Checked_Update_Element would not need to take any further action.
+
+
Now let's say that the employee's wallet was stolen, which contained his
social security card. In order to prevent identity theft, he needs to
apply for a new social security number, and then change his entry in the
database.
-We need to copy him out of the set, change the value of the SSN field,
-and then (re)insert him:
+One way to do this would be to first copy the employee object and remove
+it from the set, then change the value of its SSN field, and finally
+(re)insert the element:
procedure Change_SSN
(Old_SSN : SSN_Type;
New_SSN : SSN_Type) is
- Position : Cursor := Find (Employees, Key => Old_SSN);
- Success : Boolean;
+ Old_Position, New_Position : Cursor;
+ Inserted : Boolean;
begin
- if Has_Element (Position) then
- declare
- Employee : Employee_Type := Element (Position);
+ if New_SSN = Old_SSN then
+ return;
+ end if;
+
+ Old_Position := Find (Employees, Key => Old_SSN);
+
+ if not Has_Element (Old_Position) then
+ return;
+ end if;
+
+ New_Position := Find (Employees, Key => New_SSN);
+
+ if Has_Element (New_Position) then
+ raise Duplicate_SSN;
+ end if;
+
+ declare
+ Employee : Employee_Type := Element (Old_Position);
+ begin
+ Delete (Employees, Old_Position);
+
+ Employee.SSN := New_SSN;
+
+ Insert (Employees, Employee, New_Position, Inserted);
+ pragma Assert (Inserted);
+ end;
+ end Change_SSN;
+
+
+Another technique is to use Checked_Update_Element, which allows the
+element's key to be modified, and then moves then element to its new
+relative location in the set:
+
+ procedure Change_SSN
+ (Old_SSN : SSN_Type;
+ New_SSN : SSN_Type) is
+
+ Old_Position, New_Position : Cursor;
+ Inserted : Boolean;
+ begin
+ if New_SSN = Old_SSN then
+ return;
+ end if;
+
+ Old_Position := Find (Employees, Key => Old_SSN);
+
+ if not Has_Element (Old_Position) then
+ return;
+ end if;
+
+ New_Position := Find (Employees, Key => New_SSN);
+
+ if Has_Element (New_Position) then
+ raise Duplicate_SSN;
+ end if;
+
+ declare
+ procedure Set_SSN (Employee : in out Employee_Type) is
begin
Employee.SSN := New_SSN;
- Insert (Employees, Employee, Position, Success);
end;
- end if;
+ begin
+ SSN_Keys.Checked_Update_Element
+ (Position => Old_Position,
+ Process => Set_SSN'Access);
+ end;
end Change_SSN;
+Changing the key this way is probably more efficient than deleting and
+then immediately re-inserting the element, since the element doesn't
+need to be copied, and there is no deallocation and re-allocation of the
+element's internal node. When it detects that the element's key has
+been changed, Checked_Update_Element works by first removing the node
+from the tree and then inserting the same node back into the tree.
+
+
Suppose now we want a list all the employees in the firm. One way to do
it is like this:
@@ -4568,11 +4858,11 @@
end;
begin
- Update_Element (Position => I, Process => Do_Print'Access);
+ Query_Element (Position => I, Process => Do_Print'Access);
end;
begin
- Iteration (Employees, Print'Access);
+ Iterate (Employees, Print'Access);
end;
However, this will list employees in order of their social security
@@ -4602,11 +4892,11 @@
end;
begin
- Update_Element (R, Process_RE'Access);
+ Query_Element (R, Process_RE'Access);
end Process_LE;
begin
- Update_Element (L, Process_LE'Access);
+ Query_Element (L, Process_LE'Access);
return Result;
end;
@@ -4641,7 +4931,7 @@
for Index in Cursors'Range loop
C := Cursors (Index);
- Update_Element (Position => C, Process => Do_Print'Access);
+ Query_Element (Position => C, Process => Do_Print'Access);
end loop;
end Display_Employees_In_Name_Order;
@@ -4654,7 +4944,7 @@
Implementing the sort order relation turns out to slightly tricky,
because we don't want to make a copy of the employee just do get its
-name. We use nested process routines for Update_Element to create a
+name. We use nested process routines for Query_Element to create a
context in which both employee objects are directly visible, and then
compare employee names by querying the employee elements directly.
@@ -4696,8 +4986,13 @@
return Session.Id > Id;
end;
+ function Id (Session : Session_Access) return String is
+ begin
+ return Session.Id;
+ end;
+
package Id_Keys is
- new Session_Set_Types.Generic_Keys (String);
+ new Session_Set_Types.Generic_Keys (String, Key => Id);
This lets us perform session lookups based on the session identifier:
@@ -4728,7 +5023,7 @@
Session : constant Session_Access := new Session_Type; -- allocate
Position : Session_Set_Types.Cursor;
- Success : Boolean;
+ Inserted : Boolean;
begin
Generate_Id (Session.Id);
@@ -4736,7 +5031,7 @@
(Container => Sessions_Set,
New_Item => Session, -- element, has its own key
Position => Position,
- Success => Success);
+ Inserted => Inserted);
...
return Session;
end;
@@ -7687,6 +7982,414 @@
I don't think that the above buy enough to change Matt's choices (except for
a couple obvious mistakes, already fixed).
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Friday, September 3, 2004 7:43 PM
+
+This document lists significant changes between AI-302-3/05 (which for the
+most part reflects the Palma meetings conclusions) and AI-302-3/06 (which
+reflects more recent e-mail discussions and experience). Simple typos aren't
+listed. I've numbered the changes for easy reference. Most of these require
+no discussion. A few questions about issues that require some discussion are
+at the end.
+
+ 1) !summary: Changed (vectors) => (vectors and lists) to reflect both kinds
+of sequence containers.
+
+ 2) !proposal: The summary of the semantics of hashed containers is
+simplified to be less precise (it was too specific to a particular
+implementation).
+
+ 3) The name of the Count parameter of To_Vector was changed to Length,
+given that that is what it signifies.
+
+ 4) The name of the Count parameter of Set_Capacity for Vectors was changed
+to Capacity, given that that is what it signifies. (Note that the Map one
+already called it Capacity in the spec., so there also was a consistency
+issue.)
+
+ 5) The container to Generic_Sort has been made class-wide. Generic units
+are not primitive operations, and it is usually a mistake to use specific
+tagged types in non-primitive operations. By making it class-wide,
+instantiations are directly usable by any extensions. Note that
+implementations should take care not to dispatch to primitive operations of
+Vectors and Lists in the implementations of these routines; the routines are
+defined in terms of semantics, not primitive routines, and thus any
+overridings could have the wrong semantics.
+
+ 6) For vectors, the two Find operations could be ambiguous if the default
+parameters are used. For instance:
+ Op (Find (V, E)); -- index-based or cursor-based Find?
+Therefore, the index-returning Find was renamed to Find_Index. This is
+similar to the way the ambiguity was handled for First and Last. A similar
+change was made for Reverse_Find. (Note: We change the index version, so
+that the cursor-based version has the same name and profile for all of the
+containers.)
+
+ 7) function Is_In (Item : Element_Type;
+ Container : Vector) return Boolean;
+was replaced by
+ function Contains (Container : Vector; Item : Element_Type) return
+Boolean;
+This new profile allows users to use prefix notation on calls:
+ if Obj.Contains (Element) then ...
+This was discussed on Ada-Comment; the only advantage of the first profile
+is that it is similar to that used in Ada.Strings. But most people thought
+"Contains" sounds more natural, and they want to be able to use prefix
+notation.
+
+ 8) The names Iteration and Reverse_Iteration were changed to Iterate and
+Reverse_Iterate; they should be a verb. The process routines should have a
+parameter of Cursor. The latter was purely a cut-and-paste error (repeated
+everywhere). Similarly, the text about Elements following Iteration for maps
+should be after Update_Element for maps.
+
+ 9) Added text to insure that inserting a null vector into a vector never
+raises an exception. This is needed to insure that all of the inserts are
+consistent on this point. (The base Insert already has this wording.)
+Otherwise, the shorter Inserts
+would raise an exception for an index out of range, and the basic one would
+not. This behavior is needed so that inserting a empty vector into another
+empty vector does not fail (we don't want to have to require testing for
+non-empty before doing an Insert).
+
+10) The description of Delete_Last for Vector was simplified to use Clear
+instead of Delete when everything will be deleted.
+
+11) The AARM note after Delete for Vector was corrected to use Last_Index
+rather than length; the note as written presumed that First_Index = 1 (the
+classic incorrect Ada assumption about arrays).
+
+12) Added wording to say that Last_Index returns Index_Type'First - 1 if the
+container is empty. That makes it clear what the result is, as the position
+of the last element isn't defined in that case (since there are no elements
+in the container).
+
+13) Insert for lists had a wording correction to plural so that it is
+obvious that multiple elements can be inserted (the wording originally was
+copied from the single element version, which was dropped in favor of a
+default parameter of 1 for the Count).
+
+14) Corrected AARM notes for Insert, Delete, Find for Hash to say "should
+only compare keys" instead of "should only compare elements", as it is the
+keys that are compared, not the elements.
+
+15) function Key (Position : Cursor) return Key_Type was added to the
+specification
+of Generic_Keys inside of Ordered_Sets. This operation matches one declared
+in Hashed_Maps, and we want these containers to be as similar as possible.
+The operation was originally omitted because there was no key read function
+in the generic spec; now that one has been added, there is no reason to omit
+this function.
+
+16) Added wording so that if something outside of the package Hashed_Maps
+changes a
+key value, the behavior of the package is unspecified. If a key includes an
+access-to-variable component, and the designated object of the access
+component takes part in hashing or equality, then it is impossible to
+guarantee the behavior of the package. The key could be changed even without
+any call into the package at all (if a copy of the access is saved
+somewhere).
+
+This really is a user error, similar to passing in a hash function that
+doesn't provide the same results when called with the same key. Moreover,
+implementations can't protect against it even if they wanted to, since it
+can happen without any access to the Hashed_Maps package.
+
+Similar wording was added to Ordered_Sets, as elements could have similar
+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
+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:
+ Obj.Is_Subset (Of_Set => Obj2);
+which is crystal-clear which is being tested to be a subset of which set.
+(This operation is not common enough for readers of code to "know" which
+operand is which.)
+
+18) Pragma Pure was added to the array sort subprograms.
+
+19) Matt made a number of improvements to the !examples section, adding and
+reordering examples.
+
+20) The following was added to all of the containers:
+ procedure Query_Element
+ (Position : in Cursor;
+ Process : not null access procedure (Element : in Element_Type));
+This is valuable for reading large elements without copying them. For Sets,
+this also avoids the need to check if the key was modified (meaning it can
+be used even without defining a key). Since the key check could be
+expensive, this is a significant savings. The routine was added to all of
+the containers for consistency.
+
+21) Nick Roberts points out that now that Index_Type is an integer type, it
+is a lot simpler and clearer to say Index_Type'First-1 rather than
+Index_Type'Pred(Index_Type'First). I've made this change generally.
+
+22) Nick also pointed out that "any exceptions raised ... are propagated"
+should be singular, as only one exception can be raised by a routine.
+(Unless, of course, there are multiple operations in the "...").
+
+23) Nick asked for an AARM note to clarify the purpose of the pragma Assert
+in the
+Vectors package. This was added.
+
+24) Nick asked for the introductory description of length and capacity for
+vectors to
+be clarified (as it used "length" in the description of capacity, among
+other sins).
+
+25) Nick asked that the list of containers in Language Design Principles be
+put in the order that they're defined in the text. He also asked that the
+statement about
+separate definite and indefinite versions be stated more clearly.
+
+26) Update_Element for Sets has been renamed Checked_Update_Element, as it
+is different from the other Update_Elements both in profile (the Set is
+included in the
+call) and in semantics. This is necessary because the routine may be forced
+to delete the element and raise Constraint_Error if it is modified to match
+an existing key. In that case, the set itself will need to be modified;
+potentially including pointers in the implementation such as First or Last.
+Thus the profile must be different.
+
+27) At Palma, we decided that Swap should always swap elements, not nodes.
+(Thus, the cursors would point at the changed elements afterwards). However,
+this suffers from two major problems: First, it isn't necessarily possible
+for indefinite types. It is not possible to copy the elements between nodes
+(because they are potentially different shapes or even types), and it is
+possible (although one would have to leave Ada to do it) to put the elements
+directly in the nodes. Second, the purpose of the swap operations is to
+provide better performance than the user can get from manually copying the
+elements. But, that clearly requires swapping the nodes for a list. Only a
+novice programmer would write a list swap that *copied* the designated
+objects.
+
+Similarly, if there is inherent indirectness in a container implementation,
+we want to allow Swap to take advantage of it.
+
+Therefore, we didn't change the semantics of Swap for lists. Rather, because
+the vector operation is different, we renamed it to Swap_Elements. This will
+prevent problems if a container is switched from a vector to a list or vice
+versa.
+
+I added some AARM notes to explain the difference and the reasons.
+
+Matt pointed out that the Container parameter to Swap_Elements for cursors
+is unnecessary; it violates our meta-rule that Container parameters are only
+included on cursor operations if the cardinality of the Container may
+change. It was removed, since there is no longer a need to be the same as
+the list Swap.
+
+28) The Success parameter of Insert for Maps and Sets was changed to
+Inserted. Success is a boolean parameter, and Success = False implies some
+sort of failure or error. But it is not an error (necessarily) for Insert to
+return this value; it just means that the item was previously in the Map or
+Set. The caller of Insert must decide if Inserted = False is an error
+(failure) or if it is intended behavior. Thus we select a name that doesn't
+have a strong connotation.
+
+29) The Replace operation of Maps was renamed Insert_Or_Replace. This
+operation has insertion semantics (if the key is not in the map) or
+replacement semantics otherwise. Thus the name change; it's confusing
+without it. (The suggestion of renaming it to Insert has the same problem,
+in the other direction). It's a useful shorthand, especially as it does not
+have the Out parameters of regular Insert. If all you need to do is stick
+something into the map, and only care that it ends up there, this is the
+operation to use.
+
+A similar operation was defined for Sets. This operation is named Insert,
+because it has no replacement function (the element is unchanged if it is
+already in the map). Again, it is useful if you want to add an element to a
+Set, and have no need to worry about whether it is already there or where it
+ended up. (This operation was requested by users on Ada-Comment, noting that
+defining 'dead' objects to receive return values that they don't care about
+is ugly and possibly dangerous.) For more on this subject, see Question Q5.
+
+
+Questions:
+
+Q1) Find_Index returns Last_Index (Container) + 1 if the element is not
+found. This seems consistent to me (it's past the end of the container in a
+forward search), but Matt worries that First_Index (Container) - 1 might be
+thought of as better. The trouble with First_Index (Container - 1 is that
+you can't put it into an object:
+
+ declare
+ I : Index_Type := Index_Type'First;
+ begin
+ I := Find_Index (Vect, Item, I);
+ while I <= Last_Index (Vect) loop
+ -- Do something to the element I.
+ I := Find_Index (Vect, Item, I+1);
+ end loop;
+ end;
+
+If Find_Index returned Index_Type'First - 1, saving the result of Find_Index
+would raise Constraint_Error if the item is not found. That's not what we
+want, I think.
+
+Q2) The parameters to Generic_Merge have not been made class-wide (even
+though the comments about non-primitive operations with specific tagged
+parameters mentioned for Generic_Sort hold here, too). That's because both
+parameters need to be the same type. An alternative would be to make them
+class-wide, and then have a runtime check (of the actual tags) that they
+actually are the same type. But that is not very O-O. A third possibility
+would be to repeat the type in the generic spec:
+ generic
+ type List_Type is new List with private;
+ with function "<" (Left, Right : Element_Type)
+ return Boolean is <>;
+ procedure Generic_Merge (Target : in out List_Type;
+ Source : in out List_Type);
+
+But that is not very consistent with the rest of the specification. Some
+guidance would be helpful here.
+
+
+Q3) The generic formal part for maps has:
+ with function "=" (Left, Right : Key_Type)
+ return Boolean is <>;
+ with function Is_Equal_Key (Left, Right : Key_Type)
+ return Boolean is "=";
+Matt wonders why both operations are needed; his reference implementation
+never uses "=". This came from the Palma meeting; it's mentioned explicitly
+in the meeting minutes. The intent is that Map equality use "=" rather than
+Is_Equal_Key. The idea is that Maps that compare equal have no visible
+differences. Consider a map with keys that are strings representing numbers.
+Is_Equal_Key probably would compare the 'Values of the keys (so "0046" and
+"46" would be the same), but "=" would just compare the strings.
+
+The other reason is that Is_Equal_Key often will not be native equality (as
+in the example above). But it will be often enough that we want to be able
+to provide "=" as a result.
+
+However, Map equality is not an important operation; it exists simply
+because the type is non-limited and thus we have to define it. Arguably, the
+extra operation doesn't buy much. It doesn't cost much, either, as it will
+never need to be specified in an instantiation as long as named notation is
+used.
+
+Matt points out that the reason this operation is called "Is_Equal_Key" is
+that otherwise there would be two "=" operators in the formal part, and that
+would prevent using named notation for either. Moreover, it is not
+unreasonable (see above) for the user to override the key equality. So, if
+one is dropped, it would have to be the "=" operation.
+
+I did add some text specifying the required relationship between "=" and
+Is_Equal_Key: if "=" returns True for some operands, then Is_Equal_Key also
+returns True for those operands. I also added some text about the design
+need to give key equality a different name than "=" in order to allow named
+notation in instantiations.
+
+
+Q4) Set_Capacity is defined to raise Constraint_Error if Length (Container)
+> Count. Matt would prefer that this case is not separately handled. He
+would like
+ Set_Capacity (M, 0)
+to be a shorthand for setting the Map or Vector to the smallest reasonable
+size. (I find this a bit odd, as Matt never wanted this routine to even
+allow smaller values. But whatever.) Note that just dropping the check would
+not be enough; we'd have to redo the description of the operation to say
+that the capacity is set to at least Count_Type'Max (Count, Length
+(Container)) -- because we don't want this operation to drop elements. I'm
+unsure that the benefit is worth the change, and it seems like a bug to me
+to try to set the capacity of a container to be smaller than the number of
+elements it holds.
+
+
+Q5) There is a lot of confusion about the meaning of the Insert operations
+for maps and sets. The changes outlined in (29) above should help.
+
+However, the semantics of the Insert that does not return an Inserted value
+remain controversial. Five possible behaviors were identified for Maps:
+ 1) Insert raises an exception when the key is already in the map;
+ 2) Insert does nothing when the key is already in the map;
+ 3) Insert replaces the existing element when the key is already in the
+map;
+ 4) Replace raises an exception when the key is not already in the map;
+ 5) Replace does nothing when the key is not already in the map.
+(One could imagine a Replace that inserts when not found, but that is just
+choice 3.)
+
+Convincing examples were shown for virtually all of these semantics. Note
+that replacement semantics (choices 3 through 5) make less sense for Sets,
+as you would be replacing an equivalent element. However, since it certainly
+possible for an element to have components that do not participate in the
+equivalence test, it is easy to imagine examples where such replacements
+make sense.
+
+It was suggested to provide all of these operations with different names,
+but that requires coming up with five sets of names, with the resultant
+clutter and confusion. (And this is on top of the Insert that returns a
+Position and Inserted result.) Moreover, all of these routines can be
+written using other primitives. We therefore decided to provide (3) for Maps
+and (2) for Sets.
+
+Another suggestion was to use an enumeration similar to the ones in
+Ada.Strings. Then we'd have:
+
+type Exists_Action is (Error, Ignore, Replace);
+
+procedure Insert (Container : in out Map;
+ Key : in Key_Type;
+ New_Item : in Element_Type;
+ If_Exists : in Exists_Action := Error);
+
+type Nonexistent_Action is (Error, Ignore, Insert);
+
+procedure Replace (Container : in out Map;
+ Key : in Key_Type;
+ New_Item : in Element_Type;
+ If_Nonexistent : in Nonexistent_Action := Error);
+
+The objections to this idea boiled down to two: this is control-coupling,
+and that some people hate the design of Ada.Strings; they find it hard to
+find or remember the names of the parameters.
+
+Several people suggested that control-coupling was preferable to a forest of
+routines, or one routine with non-intutive semantics. Moreover,
+control-coupling is mainly a problem for the implementer of a routine; it is
+not bad for the user of a routine, and make in fact increase the options
+available to them.
+
+I personally am in favor of this sort of solution, because (1) it allows
+using simple names for the routines, without surprise semantics; (2) it
+allows dodgy cases to be errors by default, while allowing the specification
+of other behaviors when needed (which is makes using the library safer, by
+cutting surprise behavior); (3) it doesn't force users into using the
+Position-returning Insert when they don't need the Position for a later
+operation.
+
+However, it does slightly complicate the specifications of the packages, and
+it only got lukewarm support, so the decision has been left to the ARG.
+
+
+Q6) Tucker has mentioned that he often has components in the key of a map
+beyond the actual key participating ones. (This is similar to the behavior
+of a set; if we had a Hashed_Set this probably would be less of an issue.)
+For that to be effective, it would be necessary to change a key that is
+already in a map. Currently, neither Replace_Element nor Insert_or_Replace
+change the value of a key that is in the map; only the element is changed.
+
+In order to get the sort of semantics that Tucker seems to be suggesting,
+we'd need a way to change the value of a key. But such an operation would
+potentially change the location of the element, so it could be fairly
+expensive. Moreover, it would likely require allocation even if the hash
+didn't change for the indefinite form of the container.
+
+Finally, whether or not the key is replaced would seem to be another
+(orthogonal) option for the Insert routine "6) Insert replaces the key and
+the element when the key is already in the map; 7) Insert replaces the key,
+leaving the element unchanged when the key is already in the map".
+
+This complication doesn't seem worth it to me, but as it came up very late,
+the entire ARG needs to discuss the issue.
****************************************************************
Questions? Ask the ACAA Technical Agent