CVS difference for ais/ai-20302.txt
--- ais/ai-20302.txt 2005/04/15 04:31:23 1.19
+++ ais/ai-20302.txt 2005/05/15 23:43:07 1.20
@@ -1,4 +1,4 @@
-!standard A.18 (00) 05-04-14 AI95-00302-03/12
+!standard A.18 (00) 05-05-13 AI95-00302-03/13
!standard A.18.1 (00)
!standard A.18.2 (00)
!standard A.18.3 (00)
@@ -588,8 +588,17 @@
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
- procedure Generic_Sort (Container : in Vector);
+ package Generic_Sorting is
+ function Is_Sorted (Container : Vector) return Boolean;
+
+ procedure Sort (Container : in out Vector);
+
+ procedure Merge (Target : in out Vector;
+ Source : in out Vector);
+
+ end Generic_Sorting;
+
function Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'First)
@@ -674,17 +683,22 @@
* it finalizes V; or
* it calls the Move procedure with V as a parameter.
-Some operations are assumed to not change elements. For such an operation, a
+ AARM Note:
+ Swap, Sort, and Merge copy elements rather than reordering them, so
+ they do not tamper with cursors.
+
+Some operations are assumed to not replace elements. For such an operation, a
subprogram is said to *tamper with elements* of a vector object V if:
* it tampers with cursors of V; or
- * it modifies one or more elements of V, that is, it calls the
- Replace_Element, Update_Element, or Swap procedures or an
- instance of Generic_Sort with V as a parameter.
-
- AARM Note:
- Swap and Generic_Sort copy elements rather than reordering them, so
- they can be allowed for Iterate.
+ * it replaces one or more elements of V, that is, it calls the
+ Replace_Element or Swap procedures or the Sort or Merge procedures of an
+ instance of Generic_Sorting with V as a parameter.
+
+ AARM Note: Complete replacement of an element can cause its
+ memory to be deallocated while another operation is holding onto a reference
+ to it. That can't be allowed. However, a simple modification of (part of) an
+ element is not a problem, so Update_Element does not cause a problem.
function To_Vector (Length : Count_Type) return Vector;
@@ -950,9 +964,9 @@
Before : in Cursor;
New_Item : in Vector);
-Program_Error is propagated unless Before is equal to No_Element or
-designates an element in Container. Otherwise, if Length(New_Item) is 0, then
-Insert does nothing.
+If Before is not No_Element, and does not designate an element in
+Target, then Program_Error is propagated.
+Otherwise, if Length(New_Item) is 0, then Insert does nothing.
If Before is No_Element, then the call is equivalent to Insert (Container,
Last_Index (Container) + 1), New_Item); otherwise the call is
equivalent to Insert (Container, To_Index (Before), New_Item);
@@ -969,8 +983,8 @@
New_Item : in Vector;
Position : out Cursor);
-Program_Error is propagated unless Before is equal to No_Element or
-designates an element in Container.
+If Before is not No_Element, and does not designate an element in
+Target, then Program_Error is propagated.
If Before equals No_Element, then
let T be Last_Index (Container) + 1; otherwise, let T be To_Index (Before).
Insert (Container, T, New_Item) is called, and then Position is set to
@@ -1046,8 +1060,8 @@
Position : out Cursor;
Count : in Count_Type := 1);
-Program_Error is propagated unless Before is equal to No_Element or
-designates an element in Container.
+If Before is not No_Element, and does not designate an element in
+Target, then Program_Error is propagated.
If Before equals No_Element, then let T be Last_Index (Container) + 1;
otherwise, let T be To_Index (Before). Insert_Space (Container, T, Count) is
called, and then Position is set to To_Cursor (Container, T).
@@ -1059,18 +1073,19 @@
Reserve_Capacity (Container, Length), then sets the length of the
Container to Length. If Length is greater than the original length of
Container, empty elements are added to Container; otherwise elements are
-are removed from Container.
+removed from Container.
AARM Ramification: No elements are moved by this operation; any new empty
elements are added at the end. This follows from the rules that a cursor
-continues to designate the same element unless the the routine is defined
+continues to designate the same element unless the routine is defined
to make the cursor ambiguous or invalid; this operation does not do that.
procedure Delete (Container : in out Vector;
Index : in Extended_Index;
Count : in Count_Type := 1);
-If Index is not in the range First_Index (Container) .. Last_Index (Container),
+If Index is not in the range First_Index (Container) ..
+Last_Index (Container) + 1,
then Constraint_Error is propagated. If Count is 0, Delete has no effect.
Otherwise Delete slides the elements (if any) starting at position Index +
Count down to Index. Any exception raised during element assignment is
@@ -1157,13 +1172,17 @@
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);
+function Is_Sorted (Container : Vector) return Boolean;
+
+Returns True if the elements are sorted smallest first as determined by the
+generic formal "<" operator; otherwise, Is_Sorted returns False.
+Any exception raised during evaluation of "<" is propagated.
+procedure Sort (Container : in out Vector);
+
Reorders the elements of Container such that the elements are
sorted smallest first as determined by the generic formal "<" operator
-provided. Any exception raised during evalution of "<" is propagated.
+provided. Any exception raised during evaluation of "<" is propagated.
AARM Notes:
This implies swapping the elements, usually including an intermediate copy.
@@ -1180,6 +1199,30 @@
is something already in the element that provides the needed stability.
End AARM Notes
+procedure Merge (Target : in out Vector;
+ Source : in out Vector);
+
+Merge removes elements from Source and inserts them into Target; afterwards,
+Target contains the union of the elements that were initially
+in Source and Target; Source is left empty.
+If Target and Source are initially sorted smallest first, then Target is
+ordered smallest first as determined by the generic formal "<" operator;
+otherwise, the order of elements in Target is unspecified.
+Any exception raised during evaluation of "<" is propagated.
+
+AARM Notes:
+It is a bounded error if either of the vectors is unsorted, see below. The
+bounded error can be recovered by sorting Target after the merge call, or
+the vectors can be pretested with Is_Sorted.
+
+The Merge operation will usually require copying almost all of the elements.
+One implementation strategy would be to extend Target to the appropriate
+length, then copying elements from the back of the vectors working towards the
+front. An alternative approach would be to allocate a new internal data array
+of the appropriate length, copy the elements into it in an appropriate order,
+and then replacing the data array in Target with the temporary.
+End AARM Notes.
+
function Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'First)
@@ -1291,8 +1334,6 @@
If the counter is nonzero when an operation that inserts or deletes is called,
Finalize is called, or one of the other operations in the list occurs,
Program_Error is raised.
-
-Swap and Generic_Sort are not included here, as they only copy elements.
End AARM Notes.
procedure Reverse_Iterate
@@ -1319,10 +1360,10 @@
Bounded (Run-Time) Errors
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.
+Update_Element, Swap, Is_Sorted, Sort, Merge, "=", Find, or Reverse_Find is a
+bounded error. The implementation may treat the element as having any valid
+value of the element type, or raise Constraint_Error or Program_Error before
+modifying the vector.
AARM Notes: For instance, a default initialized element could be returned. Or
some previous value of an element. But returning random junk is not allowed
@@ -1337,6 +1378,11 @@
above.
End AARM Notes.
+Calling Merge in an instance of Generic_Sorting with either Source or Target
+not ordered smallest first using the provided generic formal "<" operator
+is a bounded error. Either Program_Error is raised after Target is updated
+as described for Merge, or the operation works as defined.
+
A Cursor value is *ambiguous* if any of the following have occurred since it
was created:
* Insert, Insert_Space, or Delete has been called on the vector that contains
@@ -1344,8 +1390,8 @@
cursor designates with an index value (or a cursor designating an element at
such an index value) less than or equal to the index value of the element
designated by the cursor; or
- * The vector that contains the element it designates has been passed to an
- instance of Generic_Sort.
+ * The vector that contains the element it designates has been passed to the
+ Sort or Merge procedures of an instance of Generic_Sorting.
It is a bounded error to call any subprogram other than "=" or Has_Element
declared in Containers.Vectors with an ambiguous (but not invalid, see below)
@@ -1413,15 +1459,17 @@
the proportionality constant and caching effects are likely to be larger than
the log factor, and we don't want to discourage innovative implementations.
-The worst-case time complexity of a call on an instantiation of
-Containers.Vectors.Generic_Sort should be O(N**2), and
-the average time complexity should be better than O(N**2).
+The worst-case time complexity of a call on procedure Sort of an instantiation
+of Containers.Vectors.Generic_Sorting should be O(N**2), and the average time
+complexity should be better than O(N**2).
AARM Note
In other words, we're requiring the use of a better than O(N**2) sorting
algorithm, such as Quicksort. No Bubble sorts allowed!
-Containers.Vectors.Generic_Sort should minimize copying of elements.
+Containers.Vectors.Generic_Sorting.Sort and
+Containers.Vectors.Generic_Sorting.Merge
+should minimize copying of elements.
AARM Note - To Be Honest
We do not mean "absolutely minimize" here; we're not intending to require a
@@ -1434,8 +1482,15 @@
AARM Note: Usually that can be accomplished simply by moving the pointer(s) to
the internal data structures from the Source vector to the Target vector.
+
+If an exception is propagated from a vector operation, no storage should be
+lost, nor any elements removed from a vector unless specified by the operation.
+
+AARM Note: This is important so that programs can recover from errors.
+But we don't want to require heroic efforts, so we just require documentation
+of cases where this can't be accomplished.
-NOTE:
+NOTES:
All elements of a vector occupy locations in the internal array.
If a sparse container is required, a Hashed_Map should be used rather than a
vector.
@@ -1549,14 +1604,17 @@
generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
- procedure Generic_Sort (Container : in out List);
+ package Generic_Sorting is
- generic
- with function "<" (Left, Right : Element_Type)
- return Boolean is <>;
- procedure Generic_Merge (Target : in out List;
- Source : in out List);
+ function Is_Sorted (Container : List) return Boolean;
+
+ procedure Sort (Container : in out List);
+
+ procedure Merge (Target : in out List;
+ Source : in out List);
+ end Generic_Sorting;
+
procedure Reverse_List (Container : in out List);
procedure Swap (I, J : in Cursor);
@@ -1570,12 +1628,12 @@
procedure Splice (Target : in out List;
Before : in Cursor;
- Position : in Cursor);
+ Source : in out List;
+ Position : in out Cursor);
- procedure Splice (Target : in out List;
+ procedure Splice (Container: in out List;
Before : in Cursor;
- Source : in out List;
- Position : in Cursor);
+ Position : in out Cursor);
function First (Container : List) return Cursor;
@@ -1648,22 +1706,28 @@
which call one of these as part of their definition are included.
* it reorders the elements of L, that is, it calls the Splice,
- Swap_Links, or Reverse_List procedures or an instance of Generic_Sort or
- Generic_Merge with L as a parameter; or
+ Swap_Links, or Reverse_List procedures or the Sort or Merge procedures
+ from an instance of Generic_Sorting with L as a parameter; or
* it finalizes L; or
* it calls the Move procedure with L as a parameter.
-Some operations are assumed to not change elements. For such an operation, a
+ AARM Note:
+ Swap copies elements rather than reordering them, so it doesn't tamper
+ with cursors.
+
+Some operations are assumed to not replace elements. For such an operation, a
subprogram is said to *tamper with elements* of a list object L if:
* it tampers with cursors of L; or
- * it modifies one or more elements of L, that is, it calls the
- Replace_Element, Update_Element, or Swap procedures with L as a parameter.
+ * it replaces one or more elements of L, that is, it calls the
+ Replace_Element or Swap procedures with L as a parameter.
AARM Note:
- Swap copies elements rather than reordering them, so it can be allowed
- for Iterate.
+ Complete replacement of an element can cause its memory to be deallocated
+ while another operation is holding onto a reference to it. That can't be
+ allowed. However, a simple modification of (part of) an element is not a
+ problem, so Update_Element does not cause a problem.
function "=" (Left, Right : List) return Boolean;
@@ -1751,8 +1815,8 @@
New_Item : in Element_Type;
Count : in Count_Type := 1);
-Program_Error is propagated unless Before is equal to No_Element or
-designates an element in Container.
+If Before is not No_Element, and does not designate an element in
+Target, then Program_Error is propagated.
Otherwise, Insert inserts Count copies of
New_Item prior to the element designated by Before. If Before equals
No_Element, the new elements are inserted after the last node (if any). Any
@@ -1772,8 +1836,8 @@
Position : out Cursor;
Count : in Count_Type := 1);
-Program_Error is propagated unless Before is equal to No_Element or
-designates an element in Container.
+If Before is not No_Element, and does not designate an element in
+Target, then Program_Error is propagated.
Otherwise, Insert allocates Count copies of
New_Item, and inserts them prior to the element designated by Before. If Before
equals No_Element, the new elements are inserted after the last element (if
@@ -1786,8 +1850,8 @@
Position : out Cursor;
Count : in Count_Type := 1);
-Program_Error is propagated unless Before is equal to No_Element or
-designates an element in Container.
+If Before is not No_Element, and does not designate an element in
+Target, then Program_Error is propagated.
Otherwise, Insert inserts Count new elements
prior to the element designated by Before. If Before equals No_Element, the new
elements are inserted after the last node (if any). The new elements are
@@ -1817,13 +1881,17 @@
If Length (Container) <= Count then Delete_Last is equivalent to Clear
(Container). Otherwise it removes the last Count nodes from Container.
-generic
- with function "<" (Left, Right : Element_Type) return Boolean is <>;
-procedure Generic_Sort (Container : in out List);
+function Is_Sorted (Container : List) return Boolean;
+
+Returns True if the elements are sorted smallest first as determined by the
+generic formal "<" operator; otherwise, Is_Sorted returns False.
+Any exception raised during evaluation of "<" is propagated.
+procedure Sort (Container : in out List);
+
Reorders the nodes of Container such that the elements are
sorted smallest first as determined by the generic formal "<" operator
-provided. The sort must be stable. Any exception raised during evaluation of
+provided. The sort is stable. Any exception raised during evaluation of
"<" is propagated.
AARM Notes
@@ -1836,25 +1904,21 @@
that are reordered.
End AARM Notes
-generic
- with function "<" (Left, Right : Element_Type) return Boolean is <>;
-procedure Generic_Merge (Target : in out List;
- Source : in out List);
+procedure Merge (Target : in out List;
+ Source : in out List);
-Generic_Merge removes elements from Source and inserts them into Target so that
-Target be sorted smallest first as determined by the generic formal "<"
-operator.
-
-Any exception raised during evaluation of "<" is propagated. If Target and
-Source are not sorted smallest first, then Program_Error is propagated. In
-these cases, Target is left in an unspecified order, but contains the union of
-the elements that were initially in Source and Target; Source is left empty.
+Merge removes elements from Source and inserts them into Target; afterwards,
+Target contains the union of the elements that were initially
+in Source and Target; Source is left empty.
+If Target and Source are initially sorted smallest first, then Target is ordered
+smallest first as determined by the generic formal "<" operator; otherwise,
+the order of elements in Target is unspecified.
+Any exception raised during evaluation of "<" is propagated.
AARM Note:
-If Program_Error is propagated by Generic_Merge because one of the lists was
-unsorted, it is possible to recover by sorting Target. If Source and Target
-designate the same object, Generic_Merge is essentially a no-op, but it still
-has to check that the list is sorted.
+It is a bounded error if either of the lists is unsorted, see below. The
+bounded error can be recovered by sorting Target after the merge call, or
+the lists can be pretested with Is_Sorted.
procedure Reverse_List (Container : in out List);
@@ -1891,8 +1955,8 @@
Before : in Cursor;
Source : in out List);
-Program_Error is propagated unless Before is equal to No_Element or
-designates an element in Target. Otherwise, if Source denotes the
+If Before is not No_Element, and does not designate an element in Target,
+then Program_Error is propagated. Otherwise, if Source denotes the
same object as Target, the
operation has no effect. Otherwise, Splice reorders elements such that they are
removed from Source and moved to Target, immediately prior to Before. If Before
@@ -1902,30 +1966,28 @@
procedure Splice (Target : in out List;
Before : in Cursor;
- Position : in Cursor);
-
-If either of Before or Position is not No_Element, and does not designate an
-element in Target, then Program_Error is propagated. If Position equals
-No_Element, or if Position equals Before, or if the successor of Position
-equals Before, the operation has no effect. Otherwise the element designated by
-Position is moved immediately prior to Before, or, if Before equals No_Element,
-after the last element.
-
-procedure Splice (Target : in out List;
- Before : in Cursor;
Source : in out List;
- Position : in Cursor);
+ Position : in out Cursor);
If Position is No_Element then Constraint_Error is propagated. If Before does
not equal No_Element, and does not designate an element in Target, then
Program_Error is propagated. If Position does not equal No_Element, and does
not designate a node in Source, then Program_Error is propagated. If Source
-denotes the same object as Target, then Splice is equivalent to Splice (Target,
-Before, Position). Otherwise the element designated by Position is removed from
-Source and moved to Target, immediately prior to Before, or, if Before equals
-No_Element, after the last element of Target. The length of Target is
-incremented, and the length of Source is decremented.
+denotes the same object as Target, then there is no effect if Position equals
+Before, else the element designated by Position is moved immediately prior to
+Before, or, if Before equals No_Element, after the last element. Otherwise the
+element designated by Position is removed from Source and moved to Target,
+immediately prior to Before, or, if Before equals No_Element, after the last
+element of Target. The length of Target is incremented, the length of Source is
+decremented, and Position is updated to represent an element in Target.
+
+procedure Splice (Container: in out List;
+ Before : in Cursor;
+ Position : in out Cursor);
+Equivalent to Splice (Target => Container, Before => Before,
+Source => Container, Position => Position);
+
function First (Container : List) return Cursor;
If Container is empty, First returns the value No_Element. Otherwise it returns
@@ -2032,6 +2094,13 @@
traversed in reverse order, starting with the last node and moving the cursor
as per the Previous function.
+Bounded Error
+
+Calling Merge in an instance of Generic_Sorting with either Source or Target
+not ordered smallest first using the provided generic formal "<" operator
+is a bounded error. Either Program_Error is raised after Target is updated
+as described for Merge, or the operation works as defined.
+
Erroneous Execution
A Cursor value is *invalid* if any of the following have occurred since it was
@@ -2076,8 +2145,8 @@
proportionality constant and caching effects are likely to be larger than the
log factor, and we don't want to discourage innovative implementations.
-The worst-case time complexity of a call on an instantiation of
-Containers.Doubly_Linked_Lists.Generic_Sort should be O(N**2), and
+The worst-case time complexity of a call on procedure Sort of an instantiation
+of Containers.Doubly_Linked_Lists.Generic_Sorting should be O(N**2), and
the average time complexity should be better than O(N**2).
AARM Note
@@ -2090,6 +2159,14 @@
AARM Note: Usually that can be accomplished simply by moving the pointer(s) to
the internal data structures from the Source container to the Target container.
+If an exception is propagated from a list operation, no storage should be
+lost, nor any elements removed from a list unless specified by the operation.
+
+AARM Note: This is important so that programs can recover from errors.
+But we don't want to require heroic efforts, so we just require documentation
+of cases where this can't be accomplished.
+
+
NOTE
Sorting a list never copies elements, and is a stable sort (equal elements
remain in the original order). This is different than sorting an array or
@@ -2143,18 +2220,24 @@
* it finalizes M; or
* it calls the Move procedure with M as a parameter; or
* it calls one of the operations defined to tamper with the cursors of M.
+
+ AARM Note:
+ Replace only modifies a key and element rather than rehashing, so it does
+ not tamper with cursors.
-Some operations are assumed to not change elements. For such an operation, a
+Some operations are assumed to not replace elements. For such an operation, a
subprogram is said to *tamper with elements* of a map object M if:
* it tampers with cursors of M; or
- * it modifies one or more elements of M, that is, it calls the
- Replace, Replace_Element, or Update_Element procedures with M as a
+ * it replaces one or more elements of M, that is, it calls the
+ Replace or Replace_Element procedures with M as a
parameter.
AARM Note:
- Replace only modifies a key and element rather than rehashing, so it can be
- allowed for Iterate.
+ Complete replacement of an element can cause its memory to be deallocated
+ while another operation is holding onto a reference to it. That can't be
+ allowed. However, a simple modification of (part of) an element is not a
+ problem, so Update_Element does not cause a problem.
Empty_Map represents the empty Map object. It has a length of 0. If an object
of type Map is not otherwise initialized, it is initialized to the same
@@ -2442,6 +2525,13 @@
AARM Note: Usually that can be accomplished simply by moving the pointer(s) to
the internal data structures from the Source container to the Target container.
+If an exception is propagated from a map operation, no storage should be
+lost, nor any elements removed from a map unless specified by the operation.
+
+AARM Note: This is important so that programs can recover from errors.
+But we don't want to require heroic efforts, so we just require documentation
+of cases where this can't be accomplished.
+
A.18.5 The Package Containers.Hashed_Maps
Static Semantics
@@ -3158,14 +3248,20 @@
* it calls the Move procedure with S as a parameter; or
* it calls one of the operations defined to tamper with cursors of S.
-Some operations are assumed to not change elements. For such an operation, a
+Some operations are assumed to not replace elements. For such an operation, a
subprogram is said to *tamper with elements* of a set object S if:
* it tampers with cursors of S; or
- * it modifies one or more elements of S, that is, it calls the
- Replace or Update_Element_Preserving_Key procedures with S as a
+ * it replaces one or more elements of S, that is, it calls the
+ Replace or Replace_Element procedures with S as a
parameter.
+ AARM Note:
+ Complete replacement of an element can cause its memory to be deallocated
+ while another operation is holding onto a reference to it. That can't be
+ allowed. However, a simple modification of (part of) an element is not a
+ problem, so Update_Element_Preserving_Key does not cause a problem.
+
Empty_Set represents the empty Set object. It has a length of 0. If an object
of type Set is not otherwise initialized, it is initialized to the same
value as Empty_Set.
@@ -3526,6 +3622,13 @@
AARM Note: Usually that can be accomplished simply by moving the pointer(s) to
the internal data structures from the Source container to the Target container.
+If an exception is propagated from a set operation, no storage should be
+lost, nor any elements removed from a set unless specified by the operation.
+
+AARM Note: This is important so that programs can recover from errors.
+But we don't want to require heroic efforts, so we just require documentation
+of cases where this can't be accomplished.
+
A.18.8 The Package Containers.Hashed_Sets
Static Semantics
@@ -6531,9 +6634,18 @@
@b<generic>
@b<with function> "<" (Left, Right : Element_Type)
- @b<return> Boolean @b<is> <@>;
- @b<procedure> Generic_Sort (Container : @b<in> Vector);
+ @b<return> Boolean is <@>;
+ @b<package> Generic_Sorting @b<is>
+
+ @b<function> Is_Sorted (Container : Vector) @b<return> Boolean;
+ @b<procedure> Sort (Container : @b<in out> Vector);
+
+ @b<procedure> Merge (Target : @b<in out> Vector;
+ Source : @b<in out> Vector);
+
+ @b<end> Generic_Sorting;
+
@b<function> Find_Index (Container : Vector;
Item : Element_Type;
Index : Index_Type := Index_Type'First)
@@ -6611,13 +6723,13 @@
@xbullet<it calls the Move procedure with @i<V> as
a parameter.>
-Some operations are assumed to not change elements. For such an operation, a
+Some operations are assumed to not replace elements. For such an operation, a
subprogram is said to @i<tamper with elements> of a vector object @i<V> if:
@xbullet<it tampers with cursors of @i<V>; or>
-@xbullet<it modifies one or more elements of @i<V>, that is, it calls the
-Replace_Element, Update_Element, or Swap procedures or an
-instance of Generic_Sort with @i<V> as a parameter.>
+@xbullet<it replaces one or more elements of @i<V>, that is, it calls the
+Replace_Element or Swap procedures or the Sort or Merge procedures of an
+instance of Generic_Sorting with @i<V> as a parameter.>
@xcode<@b<function> To_Vector (Length : Count_Type) @b<return> Vector;>
@@ -6822,9 +6934,9 @@
Before : @b<in> Cursor;
New_Item : @b<in> Vector);>
-@xindent<Program_Error is propagated unless Before is equal to No_Element or
-designates an element in Target. Otherwise, if Length(New_Item) is 0,
-then Insert does nothing.
+@xindent<If Before is not No_Element, and does not designate an element in
+Container, then Program_Error is propagated. Otherwise, if Length(New_Item)
+is 0, then Insert does nothing.
If Before is No_Element, then the call is equivalent to Insert (Container,
Last_Index (Container) + 1), New_Item); otherwise the call is
equivalent to Insert (Container, To_Index (Before), New_Item);>
@@ -6834,8 +6946,8 @@
New_Item : @b<in> Vector;
Position : @b<out> Cursor);>
-@xindent<Program_Error is propagated unless Before is equal to No_Element or
-designates an element in Target.
+@xindent<If Before is not No_Element, and does not designate an element in
+Container, then Program_Error is propagated.
If Before equals No_Element, then
let @i<T> be Last_Index (Container) + 1; otherwise, let @i<T> be
To_Index (Before). Insert (Container, @i<T>, New_Item) is called, and then
@@ -6907,8 +7019,8 @@
Position : @b<out> Cursor;
Count : @b<in> Count_Type := 1);>
-@xindent<Program_Error is propagated unless Before is equal to No_Element or
-designates an element in Target.
+@xindent<If Before is not No_Element, and does not designate an element in
+Container, then Program_Error is propagated.
If Before equals No_Element, then let @i<T> be Last_Index (Container) + 1;
otherwise, let @i<T> be To_Index (Before). Insert_Space (Container, @i<T>, Count) is
called, and then Position is set to To_Cursor (Container, @i<T>).>
@@ -6920,7 +7032,7 @@
Reserve_Capacity (Container, Length), then sets the length of the
Container to Length. If Length is greater than the original length of
Container, empty elements are added to Container; otherwise elements are
-are removed from Container.>
+removed from Container.>
@xcode<@b<procedure> Delete (Container : @b<in out> Vector;
Index : @b<in> Extended_Index;
@@ -6992,13 +7104,27 @@
designate elements in different containers, then Program_Error is propagated.
Otherwise Swap exchanges the values of the elements designated by I and J.>
-@xcode<@b<generic>
- @b<with function> "<" (Left, Right : Element_Type) @b<return> Boolean is <@>;
-@b<procedure> Generic_Sort (Container : @b<in> Vector);>
+@xcode<@b<function> Is_Sorted (Container : Vector) @b<return> Boolean;>
+
+@xindent<Returns True if the elements are sorted smallest first as determined
+by the generic formal "<" operator; otherwise, Is_Sorted returns False.
+Any exception raised during evaluation of "<" is propagated.>
+@xcode<@b<procedure> Sort (Container : @b<in out> Vector);>
+
@xindent<Reorders the elements of Container such that the elements are
sorted smallest first as determined by the generic formal "<" operator
-provided. Any exception raised during evalution of "<" is propagated.>
+provided. Any exception raised during evaluation of "<" is propagated.>
+
+@xcode<@b<procedure> Merge (Target : @b<in out> Vector;
+ Source : @b<in out> Vector);>
+
+@xindent<Merge removes elements from Source and inserts them into Target;
+afterwards, Target contains the union of the elements that were initially in
+Source and Target; Source is left empty. If Target and Source are initially
+sorted smallest first, then Target is ordered smallest first as determined by
+the generic formal "<" operator; otherwise, the order of elements in Target is
+unspecified. Any exception raised during evaluation of "<" is propagated.>
@xcode<@b<function> Find_Index (Container : Vector;
Item : Element_Type;
@@ -7100,10 +7226,15 @@
@i<@s8<Bounded (Run-Time) Errors>>
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.
+Update_Element, Swap, Is_Sorted, Sort, Merge, "=", Find, or Reverse_Find is
+a bounded error. The implementation may treat the element as having any valid
+value of the element type, or raise Constraint_Error or Program_Error before
+modifying the vector.
+
+Calling Merge in an instance of Generic_Sorting with either Source or Target
+not ordered smallest first using the provided generic formal "<" operator
+is a bounded error. Either Program_Error is raised after Target is updated
+as described for Merge, or the operation works as defined.
A Cursor value is @i<ambiguous> if any of the following have occurred since it
was created:
@@ -7114,7 +7245,7 @@
such an index value) less than or equal to the index value of the element
designated by the cursor; or>
@xbullet<The vector that contains the element it designates has been passed
-to an instance of Generic_Sort.>
+to the Sort or Merge procedures of an instance of Generic_Sorting.>
It is a bounded error to call any subprogram other than "=" or Has_Element
declared in Containers.Vectors with an ambiguous (but not invalid, see below)
@@ -7155,15 +7286,19 @@
@xbullet<the worst-case time complexity of Prepend with Count=1 and Delete_First
with Count=1 should be O(@i<N> log @i<N>).>
-The worst-case time complexity of a call on an instantiation of
-Containers.Vectors.Generic_Sort should be O(@i<N>**2), and
+The worst-case time complexity of a call on procedure Sort of an instantiation
+of Containers.Vectors.Generic_Sorting should be O(@i<N>**2), and
the average time complexity should be better than O(@i<N>**2).
-Containers.Vectors.Generic_Sort should minimize copying of elements.
+Containers.Vectors.Generic_Sorting.Sort and Containers.Vectors.Generic_Sorting.Merge
+should minimize copying of elements.
Move should not copy elements, and should minimize copying of internal
data structures.
+If an exception is propagated from a vector operation, no storage should be
+lost, nor any elements removed from a vector unless specified by the operation.
+
@xindent<@s9<NOTES:@hr
41 All elements of a vector occupy locations in the internal array.
If a sparse container is required, a Hashed_Map should be used rather than a
@@ -7275,14 +7410,17 @@
@b<generic>
@b<with function> "<" (Left, Right : Element_Type)
@b<return> Boolean is <@>;
- @b<procedure> Generic_Sort (Container : @b<in out> List);
+ @b<package> Generic_Sorting @b<is>
- @b<generic>
- @b<with function> "<" (Left, Right : Element_Type)
- @b<return> Boolean @b<is> <@>;
- @b<procedure> Generic_Merge (Target : @b<in out> List;
- Source : @b<in out> List);
+ @b<function> Is_Sorted (Container : List) @b<return> Boolean;
+
+ @b<procedure> Sort (Container : @b<in out> List);
+
+ @b<procedure> Merge (Target : @b<in out> List;
+ Source : @b<in out> List);
+ @b<end> Generic_Sorting;
+
@b<procedure> Reverse_List (Container : @b<in out> List);
@b<procedure> Swap (I, J : @b<in> Cursor);
@@ -7296,12 +7434,12 @@
@b<procedure> Splice (Target : @b<in out> List;
Before : @b<in> Cursor;
- Position : @b<in> Cursor);
+ Source : @b<in out> List;
+ Position : @b<in out> Cursor);
- @b<procedure> Splice (Target : @b<in out> List;
+ @b<procedure> Splice (Container: @b<in out> List;
Before : @b<in> Cursor;
- Source : @b<in out> List;
- Position : @b<in> Cursor);
+ Position : @b<in out> Cursor);
@b<function> First (Container : List) @b<return> Cursor;
@@ -7369,18 +7507,18 @@
Clear, Delete, or Delete_Last procedures with @i<L> as a parameter; or>
@xbullet<it reorders the elements of @i<L>, that is, it calls the Splice,
-Swap_Links, or Reverse_List procedures or an instance of Generic_Sort or
-Generic_Merge with @i<L> as a parameter; or>
+Swap_Links, or Reverse_List procedures or the Sort or Merge procedures of
+an instance of Generic_Sorting with @i<L> as a parameter; or>
@xbullet<it finalizes @i<L>; or>
@xbullet<it calls the Move procedure with @i<L> as a parameter.>
-Some operations are assumed to not change elements. For such an operation, a
+Some operations are assumed to not replace elements. For such an operation, a
subprogram is said to @i<tamper with elements> of a list object @i<L> if:
@xbullet<it tampers with cursors of @i<L>; or>
-@xbullet<it modifies one or more elements of @i<L>, that is, it calls the
-Replace_Element, Update_Element, or Swap procedures with @i<L> as a parameter.>
+@xbullet<it replaces one or more elements of @i<L>, that is, it calls the
+Replace_Element or Swap procedures with @i<L> as a parameter.>
@xcode<@b<function> "=" (Left, Right : List) @b<return> Boolean;>
@@ -7462,8 +7600,8 @@
New_Item : @b<in> Element_Type;
Count : @b<in> Count_Type := 1);>
-@xindent<Program_Error is propagated unless Before is equal to No_Element or
-designates an element in Container.
+@xindent<If Before is not No_Element, and does not designate an element in
+Container, then Program_Error is propagated.
Otherwise, Insert inserts Count copies of
New_Item prior to the element designated by Before. If Before equals
No_Element, the new elements are inserted after the last node (if any). Any
@@ -7476,8 +7614,8 @@
Position : @b<out> Cursor;
Count : @b<in> Count_Type := 1);>
-@xindent<Program_Error is propagated unless Before is equal to No_Element or
-designates an element in Container.
+@xindent<If Before is not No_Element, and does not designate an element in
+Container, then Program_Error is propagated.
Otherwise, Insert allocates Count copies of
New_Item, and inserts them prior to the element designated by Before. If Before
equals No_Element, the new elements are inserted after the last element (if
@@ -7490,8 +7628,8 @@
Position : @b<out> Cursor;
Count : @b<in> Count_Type := 1);>
-@xindent<Program_Error is propagated unless Before is equal to No_Element or
-designates an element in Container.
+@xindent<If Before is not No_Element, and does not designate an element in
+Target, then Program_Error is propagated.
Otherwise, Insert inserts Count new elements
prior to the element designated by Before. If Before equals No_Element, the new
elements are inserted after the last node (if any). The new elements are
@@ -7521,28 +7659,29 @@
@xindent<If Length (Container) <= Count then Delete_Last is equivalent to Clear
(Container). Otherwise it removes the last Count nodes from Container.>
-@xcode<@b<generic>
- @b<with function> "<" (Left, Right : Element_Type) @b<return> Boolean @b<is> <@>;
-@b<procedure> Generic_Sort (Container : @b<in out> List);>
+@xcode<@b<function> Is_Sorted (Container : List) @b<return> Boolean;>
+
+@xindent<Returns True if the elements are sorted smallest first as determined by the
+generic formal "<" operator; otherwise, Is_Sorted returns False.
+Any exception raised during evaluation of "<" is propagated.>
+@xcode<@b<procedure> Sort (Container : @b<in out> List);>
+
@xindent<Reorders the nodes of Container such that the elements are
sorted smallest first as determined by the generic formal "<" operator
-provided. The sort must be stable. Any exception raised during evaluation of
+provided. The sort is stable. Any exception raised during evaluation of
"<" is propagated.>
-@xcode<@b<generic>
- @b<with function> "<" (Left, Right : Element_Type) @b<return> Boolean @b<is> <@>;
-@b<procedure> Generic_Merge (Target : @b<in out> List;
- Source : @b<in out> List);>
+@xcode<@b<procedure> Merge (Target : @b<in out> List;
+ Source : @b<in out> List);>
-@xindent<Generic_Merge removes elements from Source and inserts them into Target so that
-Target be sorted smallest first as determined by the generic formal "<"
-operator.>
-
-@xindent<Any exception raised during evaluation of "<" is propagated. If Target and
-Source are not sorted smallest first, then Program_Error is propagated. In
-these cases, Target is left in an unspecified order, but contains the union of
-the elements that were initially in Source and Target; Source is left empty.>
+@xindent<Merge removes elements from Source and inserts them into Target;
+afterwards, Target contains the union of the elements that were initially
+in Source and Target; Source is left empty.
+If Target and Source are initially sorted smallest first, then Target is
+ordered smallest first as determined by the generic formal "<" operator;
+otherwise, the order of elements in Target is unspecified.
+Any exception raised during evaluation of "<" is propagated.>
@xcode<@b<procedure> Reverse_List (Container : @b<in out> List);>
@@ -7565,8 +7704,8 @@
Before : @b<in> Cursor;
Source : @b<in out> List);>
-@xindent<Program_Error is propagated unless Before is equal to No_Element or
-designates an element in Target. Otherwise, if Source denotes the
+@xindent<If Before is not No_Element, and does not designate an element in
+Target, then Program_Error is propagated. Otherwise, if Source denotes the
same object as Target, the
operation has no effect. Otherwise, Splice reorders elements such that they are
removed from Source and moved to Target, immediately prior to Before. If Before
@@ -7576,8 +7715,26 @@
@xcode<@b<procedure> Splice (Target : @b<in out> List;
Before : @b<in> Cursor;
- Position : @b<in> Cursor);>
+ Source : @b<in out> List;
+ Position : @b<in out> Cursor);>
+@xindent<If Position is No_Element then Constraint_Error is propagated. If
+Before does not equal No_Element, and does not designate an element in Target,
+then Program_Error is propagated. If Position does not equal No_Element, and
+does not designate a node in Source, then Program_Error is propagated. If
+Source denotes the same object as Target, then there is no effect if Position
+equals Before, else the element designated by
+Position is moved immediately prior to Before, or, if Before equals No_Element,
+after the last element. Otherwise the element designated by Position is removed
+from Source and moved to Target, immediately prior to Before, or, if Before
+equals No_Element, after the last element of Target. The length of Target is
+incremented, the length of Source is decremented, and Position is updated to
+represent an element in Target.>
+
+@xcode<@b<procedure> Splice (Container : @b<in out> List;
+ Before : @b<in> Cursor;
+ Position : @b<in out> Cursor);>
+
@xindent<If either of Before or Position is not No_Element, and does not designate an
element in Target, then Program_Error is propagated. If Position equals
No_Element, or if Position equals Before, or if the successor of Position
@@ -7585,21 +7742,6 @@
Position is moved immediately prior to Before, or, if Before equals No_Element,
after the last element.>
-@xcode<@b<procedure> Splice (Target : @b<in out> List;
- Before : @b<in> Cursor;
- Source : @b<in out> List;
- Position : @b<in> Cursor);>
-
-@xindent<If Position is No_Element then Constraint_Error is propagated. If Before does
-not equal No_Element, and does not designate an element in Target, then
-Program_Error is propagated. If Position does not equal No_Element, and does
-not designate a node in Source, then Program_Error is propagated. If Source
-denotes the same object as Target, then Splice is equivalent to Splice (Target,
-Before, Position). Otherwise the element designated by Position is removed from
-Source and moved to Target, immediately prior to Before, or, if Before equals
-No_Element, after the last element of Target. The length of Target is
-incremented, and the length of Source is decremented.>
-
@xcode<@b<function> First (Container : List) @b<return> Cursor;>
@xindent<If Container is empty, First returns the value No_Element. Otherwise it returns
@@ -7691,6 +7833,13 @@
traversed in reverse order, starting with the last node and moving the cursor
as per the Previous function.>
+@i<@s8<Bounded Errors>>
+
+Calling Merge in an instance of Generic_Sorting with either Source or Target
+not ordered smallest first using the provided generic formal "<" operator
+is a bounded error. Either Program_Error is raised after Target is updated
+as described for Merge, or the operation works as defined.
+
@i<@s8<Erroneous Execution>>
A Cursor value is @i<invalid> if any of the following have occurred since it was
@@ -7716,13 +7865,16 @@
complexity of Element, Insert with Count=1, and Delete with Count=1 should be
O(log @i<N>).
-The worst-case time complexity of a call on an instantiation of
-Containers.Doubly_Linked_Lists.Generic_Sort should be O(@i<N>**2), and
+The worst-case time complexity of a call on procedure Sort of an instantiation
+Containers.Doubly_Linked_Lists.Generic_Sorting should be O(@i<N>**2), and
the average time complexity should be better than O(@i<N>**2).
Move should not copy elements, and should minimize copying of internal
data structures.
+If an exception is propagated from a list operation, no storage should be
+lost, nor any elements removed from a list unless specified by the operation.
+
@xindent<@s9<NOTES:@hr
43 Sorting a list never copies elements, and is a stable sort (equal elements
remain in the original order). This is different than sorting an array or
@@ -7775,14 +7927,13 @@
@xbullet<it calls one of the operations defined to tamper with the cursors of @i<M>.>
-Some operations are assumed to not change elements. For such an operation, a
+Some operations are assumed to not replace elements. For such an operation, a
subprogram is said to @i<tamper with elements> of a map object @i<M> if:
@xbullet<it tampers with cursors of @i<M>; or>
-@xbullet<it modifies one or more elements of @i<M>, that is, it calls the
-Replace, Replace_Element, or Update_Element procedures with @i<M> as a
-parameter.>
+@xbullet<it replaces one or more elements of @i<M>, that is, it calls the
+Replace or Replace_Element procedures with @i<M> as a parameter.>
Empty_Map represents the empty Map object. It has a length of 0. If an object
of type Map is not otherwise initialized, it is initialized to the same
@@ -8011,6 +8162,9 @@
Move should not copy elements, and should minimize copying of internal
data structures.
+If an exception is propagated from a map operation, no storage should be
+lost, nor any elements removed from a map unless specified by the operation.
+
!corrigendum A.18.5
@dinsc
@@ -8554,13 +8708,13 @@
@xbullet<it calls one of the operations defined to tamper with cursors of @i<S>.>
-Some operations are assumed to not change elements. For such an operation, a
+Some operations are assumed to not replace elements. For such an operation, a
subprogram is said to @i<tamper with elements> of a set object @i<S> if:
@xbullet<it tampers with cursors of @i<S>; or>
-@xbullet<it modifies one or more elements of @i<S>, that is, it calls the
-Replace or Update_Element_Preserving_Key procedures with @i<S> as a
+@xbullet<it replaces one or more elements of @i<S>, that is, it calls the
+Replace or Replace_Element procedures with @i<S> as a
parameter.>
Empty_Set represents the empty Set object. It has a length of 0. If an object
@@ -8866,6 +9020,9 @@
Move should not copy elements, and should minimize copying of internal
data structures.
+If an exception is propagated from a set operation, no storage should be
+lost, nor any elements removed from a set unless specified by the operation.
+
!corrigendum A.18.8
@dinsc
@@ -10643,528 +10800,6 @@
string comparison is a similar thing: compilers have to recognize that
frog, Frog, and FROG are the same identifier, but are (were) not
required to make such comparisons available to users.
-
-****************************************************************
-
-From: Jeffrey Carter
-Sent: Thursday, February 5, 2004 11:38 AM
-
-Tucker Taft wrote:
-
-> The term "vector" for extensible array is used in Java
-> as well. I think we should strive to use terminology
-> that has become widely used in the programming community.
-
-I disagree, even though I know that's dangerous when discussing Ada with
-STT. An application that uses both extensible arrays and mathematical
-vectors will be very confusing if both are called vectors. Since an
-explicit design goal of Ada is to emphasize ease of reading, calling an
-extensible array a vector seems inappropriate.
-
-> I personally consider an extensible array (i.e. a vector) a useful and
-> important standard container. I don't feel the same way about a linked
-> list, because it is so easy to implement what you want, and there
-> are so many options when it comes to how to link the objects
-> together that having a standard container for that hardly
-> seems worthwhile (IMHO).
-
-I have no objections to an extensible array, provided it's clearly
-identified as such. I think it should look different from the proposal,
-but that's mainly a taste issue. I'd want direct analogs to indexing,
-both LHS and RHS (Put and Get?); slices, both LHS and RHS (Replace_Slice
-and Slice?); and 'First, 'Last, and 'Length (though 'First is a constant
-for an EA). An equivalent to 'range would be nice, but impossible. The
-only difference to a normal array would be that Put and Replace_Slice
-can accept indices not in First .. Last. I haven't given it a great deal
-of thought, so I'm sure I'm missing some subtleties, but I don't see a
-need for Front, Back, Insert, Delete, and so on.
-
-The proposal says that containers "that are relatively easy to code,
-redundant, or rarely used are omitted". It also says that lists are
-difficult to implement correctly. Given a list, structures such as
-deques, stacks, and especially queues are easy to implement. Since
-queues are common structures and not redundant (none of the proposed
-containers provides an efficient implementation of a queue), the
-proposal itself seems to argue that lists should be provided, since they
-are not easy to code correctly, and provide a basis for the user to
-easily code queues.
-
-> So we settled on Vector, Map, and Set as three basic yet
-> important abstractions that will help lift the level of
-> programming above arrays and records. In my experience
-> with using languages that have large container libraries,
-> it is these three that are used more widely than all
-> the others combined.
-
-There was an article by Mills [Harlan D. Mills, Richard C. Linger: Data
-Structured Programming: Program Design without Arrays and Pointers. IEEE
-Trans. Software Eng. 12(2): 192-197 (1986)] that proposed that
-applications only use queues, stacks, and sets (real sets, with union,
-intersection, and such operations). It's an interesting concept, and I
-agree with the aim of programs using appropriate abstractions and hiding
-lower level implementation details, especially use of pointers.
-
-****************************************************************
-
-From: Alexandre E. Kopilovitch
-Sent: Thursday, February 5, 2004 9:04 AM
-
-Tucker Taft wrote:
-
-> The term "vector" for extensible array is used in Java
-> as well. I think we should strive to use terminology
-> that has become widely used in the programming community.
-
-So call it Java_Vector - that will be at least consistent.
-
-Do you think that Java meaning for "vector" is more significant for Ada than
-mathematical meaning of this term (which never implied extensibility) ?
-
-Why not call that thing Flexible_Array (after Algol-68, I think) - this name
-will directly reflect the essense.
-
-****************************************************************
-
-From: Robert A. Duff
-Sent: Thursday, February 5, 2004 1:37 PM
-
-Bill Wulf and other professors at CMU circa late 1970's were using the
-term "vector" to mean "array" (not necessarily extensible); that's the
-first time *I* heard it. So it's not a Java-ism.
-
-I think this meaning of "vector" derives from the maths meaning,
-even if it's not precisely the same thing.
-
-****************************************************************
-
-From: Stephen Leake
-Sent: Thursday, February 5, 2004 2:18 PM
-
-Jeffrey Carter <jrcarter@acm.org> writes:
-
-> Tucker Taft wrote:
->
-> > The term "vector" for extensible array is used in Java
-> > as well. I think we should strive to use terminology
-> > that has become widely used in the programming community.
->
-> I disagree, even though I know that's dangerous when discussing Ada
-> with STT. An application that uses both extensible arrays and
-> mathematical vectors will be very confusing if both are called
-> vectors. Since an explicit design goal of Ada is to emphasize ease of
-> reading, calling an extensible array a vector seems inappropriate.
-
-I agree with Tucker. I have code that uses both Cartesian vectors and
-extensible arrays. One is SAL.Math_Double.DOF_3.Cart_Vector_Type, the
-other is SAL.Poly.Unbounded_Arrays. Obviously, I have different names
-for them, as Carter wants. But if I called them
-SAL.Math_Double.DOF_3.Vector and SAL.Poly.Vector, I would have no
-chance of confusion. That's what package hierarchies are for.
-
-Since both Java and C++ use the term "vector" for an extensible array,
-I think Ada should also. Part of the point of the OY revision is to
-make the language more attractive to current users of other languages.
-This is an easy way to do that.
-
-> (Replace_Slice and Slice?); and 'First, 'Last, and 'Length (though
-> 'First is a constant for an EA).
-
-'First is not constant for SAL.Poly.Unbounded_Arrays; I provide both
-Append and Prepend operations. I don't think I've ever used Prepend,
-though; it was really just an exercise in what was possible.
-
-> .. I don't see
-> a need for Front, Back, Insert, Delete, and so on.
-
-I use Insert and Delete in real applications.
-
-> The proposal says that containers "that are relatively easy to code,
-> redundant, or rarely used are omitted". It also says that lists are
-> difficult to implement correctly. Given a list, structures such as
-> deques, stacks, and especially queues are easy to implement. Since
-> queues are common structures and not redundant (none of the proposed
-> containers provides an efficient implementation of a queue), the
-> proposal itself seems to argue that lists should be provided, since
-> they are not easy to code correctly, and provide a basis for the
-> user to easily code queues.
-
-I agree. A lists package would be nice.
-
-But I also agree with Tucker, that it is difficult to come up with one
-list package that really meets a wide range of needs.
-
-Perhaps one list package, that meets a narrow range of needs, would
-still be useful. It would set a style standard for other list packages.
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Thursday, February 5, 2004 2:48 PM
-
-Alexandre E. Kopilovitch wrote:
-
-> So call it Java_Vector - that will be at least consistent.
->
-> Do you think that Java meaning for "vector" is more significant for Ada than
-> mathematical meaning of this term (which never implied extensibility) ?
->
-> Why not call that thing Flexible_Array (after Algol-68, I think) - this name
-> will directly reflect the essense.
-
-Tucker T. and Bob D. are both correct: the container is a "vector."
-
-Alexandre K. and Jeff C. are both incorrect. The container is not a
-list, not a Java_Vector, not an Extensible_Array, and not a Flexible_Array.
-
-It is a vector. It has the same semantics as the identically-named
-container in the STL. The one named "vector."
-
-The container whose name is vector does not have array semantics. There
-is no slicing for example.
-
-The container whose name is vector has the following important properties:
-
-o inserting at the back end is amortized constant time
-o supports random access of elements, in constant time
-
-Yes, internally a vector is implemented as an array. The Size function
-returns the length of this internal array, and Resize can be used to
-expand its length.
-
-But it is not an array. It is a container. Whose name is "vector".
-Just like the one in the STL.
-
-****************************************************************
-
-From: Alexandre E. Kopilovitch
-Sent: Thursday, February 5, 2004 3:46 PM
-
-No problem with all that if another term was chosen. Now, with "vector", this
-is name squatting (well, participation in name squatting in Ada case), which
-is fully appropriate for Java, somehow understandable for C++, but seems
-(still) inappropriate for Ada, especially taking into account that the involved
-term belongs to some Ada-friendly domain.
-
-****************************************************************
-
-From: Robert A. Duff
-Sent: Thursday, February 5, 2004 3:38 PM
-
-I wrote:
-
-> Bill Wulf and other professors at CMU circa late 1970's were using the
-> term "vector" to mean "array" (not necessarily extensible); that's the
-> first time *I* heard it. So it's not a Java-ism.
-
-Actually, the meaning was "one-dimensional array". But there was no
-implication that they could grow.
-
-> I think this meaning of "vector" derives from the maths meaning,
-> even if it's not precisely the same thing.
-
-I mean, what's a vector in 3-space? Basically, a one-dimensional array
-of 3 real numbers -- the X, Y, and Z coordinates.
-
-Matt wrote:
-
-> It is a vector. It has the same semantics as the identically-named
-> container in the STL. The one named "vector."
-
-This stuff comes from the C++ STL. I think gratuitous differences from
-that are unhelpful. (But I admit that I was one of the folks pushing
-for "cursor" instead of "iterator".)
-
-> The container whose name is vector does not have array semantics. There
-> is no slicing for example.
-
-Well, "no slicing" is hardly fundamental. It could be added, or
-programmed by the client.
-
-> The container whose name is vector has the following important properties:
->
-> o inserting at the back end is amortized constant time
-> o supports random access of elements, in constant time
-
-I think "random access" is the essence of array semantics. After all,
-anything you can do with an array you can do with a linked list, and
-vice versa -- the only fundamental difference is the efficiency
-properties.
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Thursday, February 5, 2004 9:31 AM
-
-Robert A Duff wrote:
-
-> This stuff comes from the C++ STL. I think gratuitous differences from
-> that are unhelpful. (But I admit that I was one of the folks pushing
-> for "cursor" instead of "iterator".)
-
-Yes. The world has settled on the name "vector." Let's use the terms
-everyone else is using, unless we have a good reason not to.
-
-(BTW, that's also why I used the name "Iterator_Type". But I have no
-issues with the name "Cursor_Type".)
-
-
-> I think "random access" is the essence of array semantics. After all,
-> anything you can do with an array you can do with a linked list, and
-> vice versa -- the only fundamental difference is the efficiency
-> properties.
-
-But that's the essence of the argument!
-
-Yes, it's *possible* to seek to specific elements in a linked list, but
-I would hardly call that "random access."
-
-If you need fast random access to the elements in a container, and the
-number of elements in the container is large, then you can effectively
-rule out using a linked list as the container.
-
-Of course you could make the argument the other way. If you need
-constant-time insertion of elements at any position, then that
-effectively rules out a vector, in favor of a list.
-
-****************************************************************
-
-From: Alexandre E. Kopilovitch
-Sent: Thursday, February 5, 2004 3:21 PM
-
-Robert A Duff wrote:
-
-> Bill Wulf and other professors at CMU circa late 1970's were using the
-> term "vector" to mean "array" (not necessarily extensible); that's the
-> first time *I* heard it.
-
-Yes, CMU always was (as far as I know) primarily engineering educational
-facility, and I know well that engineers (not software engineers, but rather
-general kind of engineers) often called "vector" any column or row of numbers.
-(not bothering themselves with the question how the components of that "vector"
-transform with a change of coordinate system). But apparently they never used
-this term for arrays of any other objects, and I almost never seen a case
-(even in engineering) where "vector" was used for extensible array - except
-Java and perhaps some C++ libraries.
-
-A notable exception is APL, in which "vector" is the basic term, and that
-"vector" is extensible. But in APL that "vector" is equipped with vast
-nomenclature of functions, many of them associated with genuine mathematical
-vectors, so the entire balance for the term was acceptable.
-
-> So it's not a Java-ism.
-
-Yes, not exactly - there were other precedents of sloppy usage of this term.
-But nevertheless a strong impression remains that it is exactly Java, which
-is a real reason, ground and reference for proposing this term for extensible
-arrays *now and for Ada0Y*.
-
-> I think this meaning of "vector" derives from the maths meaning,
-> even if it's not precisely the same thing.
-
-No, not at all - it lacks the primary mathematical meaning of it, and adds
-the primary feature, which meaning is totally non-mathematical (that is, there
-is no attempt to bring any mathematical meaning to it... and it will not be
-simple, if attempted).
-
-****************************************************************
-
-From: Matthew Heaney
-Sent: Thursday, February 5, 2004 5:11 PM
-
-
-
-Jeffrey Carter wrote:
-
-> The actual algorithm produces 8-bit hash values, which may no longer be
-> considered adequate, given
->
->> Hash_Type'Modulus shall be at least as large as the smaller of
->> System.Max_Binary_Modulus and 2**32.
-
-In Charles I copied the hash function from GNAT. I figure if it's good
-enough for Robert Dewar it's good enough for me...
-
-
-
-> Vector should have an iterator, in addition to allowing the user to
-> explicitly iterate over the structure.
-
-No. Vector iterators are fragile, and hence very error prone.
-
-They are fragile because the (logical) internal array gets thrown away
-during expansion, which invalidates the iterator. It's too hard to keep
-track of whether a vector iterator is still valid, and most of the time
-you end up with a dangling reference.
-
-The STL has vector iterators in order to provide the infrastructure
-necessary to support generic algorithms.
-
-In Ada they are not necessary, because you can use locally-declared
-subprograms to fit within such a framework.
-
-
-
-
->> Open issue: This function returns a value that doesn't depend on it's
->> parameter. It possibility could be removed in favor of just saying
->> Index_Type'Pred(Index_Type'First) appropriately. Committee discussion
->> with the original proposal's author was inconclusive.
->
->
-> I'd say that it should be a constant, not a function. The same seems to
-> hold for First.
-
-Front can probably go away. First is there for consistency with other
-containers.
-
-
-
-> Given that Back is defined as Index_Type'Succ (Last (Vector) ), and Last
-> (Vector) could be Index_Type'Last, there seems to be a problem. There
-> should be an assertion that Index_Type'Base'Last > Index_Type'Last.
-
-That's not really possible for generic actual index types such as
-Natural or Positive.
-
-We could get rid of the assertion, but this would impact implementors.
-That's why it's still an open issue.
-
-In my reference implementation, I don't think the generic actual type
-has to have IT'Base'First < IT'First, since internally I use Integer
-subtypes for everything.
-
-http://home.earthlink.net/~matthewjheaney/charles/ai302-20040205.zip
-
-
-
-> All the problems with Index_Type disappear with a general list, which
-> would use a cursor.
-
-The original proposal included list containers, but they were not
-included in the subcommittee report, in order to keep the size of the
-report more manageable.
-
-
-
-> An important thing about maps is that they provide fast searching,
-> typically based on a lower-level structure such as a hash table or
-> balanced tree.
-
-My original proposal had both sorted and hashed maps, but in order to
-keep the subcommittee report small support for sorted maps was removed.
-
-
-> Such structures have uses of their own in addition to
-> creating maps, and independent of the key/value concept of a map. For
-> example, an application may collect a number of values and then need to
-> quickly determine if a value is in that collection, and a searchable
- > structure with a Get_First operation can be used for a priority queue.
-
-That's what the sorted set is for.
-
-
-> None of these applications use key/value pairs.
-
-So use the sorted set.
-
-
-> Therefore, I think it's
-> important to provide the underlying searchable structure to users.
-
-Just use the sorted set container. If guarantees that searches only
-take O (log N) even in the worst case.
-
-
-> (Indeed, given the ease with which a user can wrap a key/value pair in a
-> record, define comparison operations for that record that only use the
-> key part, and create a map structure, given the existence of a
-> searchable structure, it could be argued, since the proposal states that
-> easily implemented structures should not be part of the library, that
-> the library should only supply searchable structures, and not maps.)
-
-The (hashed) map stores the key and element as separate components of
-the internal node of storage.
-
-If you have a record like that, containing a key-part component, then
-use the sorted set, and instantiate the nested generic package Generic_Keys.
-
-
-> Do we really need Maps.[Wide_]Strings, given that an Unbounded_String
-> can be used for the key type, and that this library should not be used
-> for applications in which the use of Unbounded_Strings is not acceptable?
-
-Yes, we really need string-key maps.
-
-
-> The Sets package is mostly incomprehensible. Sets deal with elements,
-> and operations must include testing if an element is in a set, creating
-> a set from a list of elements (set "literals"), and set union,
-> intersection, difference, and symmetric difference. Except for the
-> membership test, these are missing from the package, so I don't see what
-> it has to do with sets. It appears to be a searchable structure, not a
-> set. This is corroborated by the package Generic_Keys, which allows the
-> structure to be used as a map.
-
-A "set" is really any sorted sequence of items. If you want set
-intersection, symmetric difference, etc, then just use a generic
-algorithm. See the Charles library for such algorithms.
-
-Of course, if you want target of a set union operation to be the set
-itself, then just use Insert to insert the items.
-
-The subcommittee report has several examples of how sets are used, and
-there's at least one example showing how to use the nested generic package.
-
-See the last two slides in my AE-2003 paper presentation for an example
-of how to take the union of a set and a (sorted) list:
-
-http://home.earthlink.net/~matthewjheaney/charles/charlesppt.htm
-
-My original proposal has the same example at the very end:
-
-http://home.earthlink.net/~matthewjheaney/charles/ai302.txt
-
-
-
-> "Sans" is a French word. Since the ARM is in English, we should use the
-> English "without" instead. "No" might also be acceptable.
-
-Je crois que non. C'est une bonne idea.
-
-The name for Delete_Sans_Increment comes from Emacs lisp, which has the
-functions file-name-sans-extension and file-name-sans-versions.
-
-It was also in homage to Ada's French history, given that her original
-designer was French, and worked for a French company.
-
-Why do you think "rendevous" was named that way?
-
-
-
-> I'd like to thank the select committee for their work. No library will
-> completely please everyone. I will welcome any standard container
-> library in Ada 0X.
-
-If you don't immediately grok how vectors and sets and maps work, then I
-suggest familiarizing yourself with the STL. There are lots of tutorials
-on the WWW.
-
-I also recommend Stanley Lippman's little book Essential C++. That was
-my introduction to the STL, and what originally convinced me that
-Stepanov's approach was the correct one.
-
-You might also like Accelerated C++ by Andrew Koenig and Barbara Moo,
-which uses the STL as a basis for teaching C++.
-
-****************************************************************
-
-From: Randy Brukardt
-Sent: Thursday, February 5, 2004 5:49 PM
-
-Matt's too modest. The tutorial that makes up the !example section is
-actually quite good. I learned a lot about how the packages work (and how to
-use them) from reading it carefully, and I recommend that everyone do that
-to better understand Matt's work.
****************************************************************
Questions? Ask the ACAA Technical Agent