CVS difference for ais/ai-20302.txt
--- ais/ai-20302.txt 2004/02/06 05:01:50 1.2
+++ ais/ai-20302.txt 2004/02/21 03:07:27 1.3
@@ -1,4 +1,4 @@
-!standard A.17 04-02-05 AI95-00302-03/02
+!standard A.17 04-02-18 AI95-00302-03/02
!class amendment 04-01-14
!status work item 04-01-14
!status received 04-01-14
@@ -47,8 +47,8 @@
Many existing container libraries are either badly designed or difficult
to use. One issue is that it should be simple and easy to instantiate a
component. If it requires more than a single instantiation to create a
-useable container, then it's too much pain and no developer will bother.
-Or if he does bother his experience will be unpleasant. Programming is
+useable container, then it's too much pain and few developers will bother.
+If he does bother his experience will be unpleasant. Programming is
work, but it should be fun work, not drudgery.
Libraries often have the problem that they are not sufficiently general,
@@ -95,7 +95,7 @@
explicit key type, but with a set the key is implicit in the element
itself.
-The map associative containers scatter keys in the container according
+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.
@@ -111,6 +111,12 @@
There is also a package of routines for managing case-insensitive strings,
and library-level subprograms for returning the hash value of strings.
+The design of these packages follow the principle that they can be implemented
+in Ada without any special implementation-specific magic. This is important,
+as we do not want to burden implementers with special purpose requirements.
+We also want to follow the principle that any capability used for the
+implementation of the language is made available to users.
+
This API is based on an existing container library called Charles. The
source code itself and a couple of papers about the design of Charles
can be found at:
@@ -135,7 +141,7 @@
The following library-level subprograms and packages are defined:
-[Question: Should Ada.Strings.Hash and Ada.Strings.Case_Insensitive be
+[Open Issues: Should Ada.Strings.Hash and Ada.Strings.Case_Insensitive be
Ada.Strings.Fixed.Hash and Ada.Strings.Fixed.Case_Insensitive instead?
Should there be a Ada.Strings.Unbounded.Case_Insensitive?
Should there be Ada.Strings.Bounded.Hash and Ada.Strings.Bounded.Case_Insensitive?
@@ -164,6 +170,12 @@
function Hash (Key : String) return Containers.Hash_Type;
end Ada.Strings.Case_Insensitive;
+[Open Issue: Matt points out that a naive user might with and use this package
+expecting to get these operations. But of course, the ones in Standard will
+still be used. (Of course, dot notation will work, but no one *wants* to do
+that for operator calls). Do we have to give these names rather than operator
+symbols as they're not primitive for the type?]
+
function Ada.Strings.Hash (Key : String) return Containers.Hash_Type;
Return an implementation-defined value which is a function of the value of Key.
@@ -186,11 +198,9 @@
Implementation Advice
The various Hash functions should be good hash functions, returning
-a wide spread of values for different string values.
+a wide spread of values for different string values. It should be unlikely
+for similar strings to return the same value.
-[Query: Anybody got better wording? Matt was nice enough to ignore these
-definitions completely!]
-
A.17 Containers
This clause presents the specifications of the package Containers and
@@ -252,10 +262,15 @@
package Ada.Containers is
pragma Pure;
+
type Hash_Type is mod <Implementation-Defined>;
+
+ type Size_Type is range 0 .. <implementation-defined>;
+
end Ada.Containers;
-Hash_Type represents the range of the result of a hash function.
+Hash_Type represents the range of the result of a hash function. Size_Type
+represents the (potential or actual) size (number of elements) of a container.
Implementation Requirements
@@ -264,7 +279,15 @@
[Open Issue: Is this OK? We can't just say 2**32, as that might be a bad
choice for the target (esp. a 24 bit machine!). And we don't want to insist
-on System.Max_Binary_Modulus on 64-bit machines -- that seems to be overkill.]
+on System.Max_Binary_Modulus on 64-bit machines -- that seems to be overkill.
+But we do want to give the user some guidance as to the range of this type.]
+
+Size_Type'Last shall be at least as large as the smaller of
+System.Max_Int and (2**31)-1.
+
+[Open Issue: Or we could just say
+Size_Type'Last shall be at least as large as Integer'Last.
+But that isn't quite as strong as the above.]
A.17.2 The Package Containers.Vectors
@@ -280,6 +303,13 @@
of a vector corresponds to the number "active" elements in the internal
array.
+AARM Note:
+
+Vectors are not intended to be sparse (that is, there are elements at all
+defined positions). If a sparse data structure is needed, use a Map.
+
+[Open Issue: Should the above be a Note in the Standard?]
+
Static Semantics
The library package Containers.Vectors has the following
@@ -287,7 +317,7 @@
generic
- type Index_Type is (<>);
+ type Index_Type is range <>;
type Element_Type is private;
@@ -306,7 +336,7 @@
function "=" (Left, Right : Vector_Type) return Boolean;
- function Length (Vector : Vector_Type) return Natural;
+ function Length (Vector : Vector_Type) return Size_Type;
function Is_Empty (Vector : Vector_Type) return Boolean;
@@ -322,30 +352,28 @@
New_Item : in Element_Type);
procedure Insert (Vector : in out Vector_Type;
- Before : in Index_Type'Base);
-
- procedure Insert_N (Vector : in out Vector_Type;
- Before : in Index_Type'Base;
- Count : in Natural;
- New_Item : in Element_Type);
+ Before : in Index_Type'Base;
+ New_Item : in Element_Type;
+ Count : in Size_Type);
- procedure Insert_N (Vector : in out Vector_Type;
+ procedure Insert_Empty_Space
+ (Vector : in out Vector_Type;
Before : in Index_Type'Base;
- Count : in Natural);
+ Count : in Size_Type);
procedure Delete (Vector : in out Vector_Type;
- Index : in Index_Type'Base);
+ Index : in Index_Type'Base);
procedure Delete_Last (Vector : in out Vector_Type);
- procedure Delete_N (Vector : in out Vector_Type;
- First : in Index_Type'Base;
- Count : in Natural);
+ procedure Delete (Vector : in out Vector_Type;
+ First : in Index_Type'Base;
+ Count : in Size_Type);
- function Size (Vector : Vector_Type) return Natural;
+ function Size (Vector : Vector_Type) return Size_Type;
procedure Resize (Vector : in out Vector_Type;
- Size : in Natural);
+ Size : in Size_Type);
function Front (Vector : Vector_Type) return Index_Type'Base;
@@ -386,12 +414,51 @@
end Ada.Containers.Vectors;
-[Open issue: Should Index_Type be "range <>" instead of "(<>)"? The
-Assert will fail for enumeration and modular types (subtypes may work),
-so they're annoying at best. The Assert is needed as operations like
+[Open issue: Should Index_Type be "(<>)" instead of "range <>"? The
+current version will not allow enumeration and modular index subtypes.
+Note that the assert will fail for enumeration and modular types (subtypes
+may work), so they're annoying at best. The Assert is needed as operations like
Front and the value of Last for an empty Vector return
-Index_Type'Pred(Index_Type'First).]
+Index_Type'Pred(Index_Type'First). Also note that this is not intended to be
+a sparse vector, so such types are less useful; if a sparse data structure is
+needed, use a map.]
+
+[Slightly Open issue: Several reviewers have complained about the use of
+the "_Type" suffix on the type names. That was originally retained when the
+names were changed because of all of the conflicts with parameter names.
+Of course, that can be easily worked around. However, there would also
+be a conflict with the functions Element and Key. Since these are going to
+be very common, we want a short, descriptive name for them, not something
+long-winded. OTOH, the formal parameter names will be used rarely, if at all.
+And we definitely can't use the same name for both (it's illegal). Thus, it is
+better to use the short names on the functions, and thus the "_Type" suffix
+is needed on at least the generic formal types.]
+
+[Open Issue: Should a vector have passive iterator(s), and if so, what should
+they look like? Note that for a vector, it is easier to write a for loop than
+a passive iterator instantiation, so these would mainly be for consistency.
+
+Matt suggested 4 (!) iterators of the form:
+ generic
+ with procedure Process (Element : in out Element_Type) is <>;
+ procedure Generic_Iteration (Vector : in Vector_Type);
+
+with constant (Process has an 'in' parameter), variable (like this), and
+reverse forms.
+
+But these are not consistent with the other containers, which use Cursor_Type
+as the parameter to Process. To be consistent, we'd have to use:
+
+ generic
+ with procedure Process (Index : in Index_Type) is <>;
+ procedure Generic_Iteration (Vector : in Vector_Type);
+which seems pretty silly. Or we could change all of the iterators to a form
+more like the one proposed above.
+
+While a number of people are in favor of passive iterators, it's not clear
+that anyone had thought of the exact forms.]
+
If an object of type Vector_Type is not otherwise initialized, it
will initialized with a size (internal array length) of 0.
@@ -406,7 +473,7 @@
False; otherwise, this function returns True. Any exceptions raised
during evaluation of element equality are propagated.
-function Length (Vector : Vector_Type) return Natural;
+function Length (Vector : Vector_Type) return Size_Type;
The Length function returns the number of active elements in Vector.
@@ -438,23 +505,16 @@
Before : in Index_Type'Base;
New_Item : in Element_Type);
-Equivalent to Insert_N (Vector, Before, 1, New_Item).
+Equivalent to Insert (Vector, Before, New_Item, 1).
procedure Insert
- (Vector : in out Vector_Type;
- Before : in Index_Type'Base);
-
-Equivalent to Insert_N (Vector, Before, 1).
-
-
-procedure Insert_N
(Vector : in out Vector_Type;
Before : in Index_Type'Base;
- Count : in Natural;
- New_Item : in Element_Type);
+ New_Item : in Element_Type;
+ Count : in Size_Type);
-If Count has the value 0, then Insert_N does nothing. Otherwise, it
+If Count has the value 0, then Insert does nothing. Otherwise, it
calculates the new length as the sum of the current length and the value
of Count; if the new value of Last would be greater than Index_Type'Last
then Constraint_Error is propagated. If the value of Before is not in
@@ -462,28 +522,35 @@
is propagated.
If the current vector size is greater than or equal to the new length,
-then Insert_N slides the elements in the range Before .. Last
+then Insert slides the elements in the range Before .. Last
(Vector) up by Count positions, and it assigns the value New_Item to
the elements in the Count positions starting at Before. Any exceptions
raised during the assignment are propagated.
Otherwise if the current vector size is less than the new length,
-Insert_N allocates a new internal array, whose elements are initialized
+Insert allocates a new internal array, whose elements are initialized
from New_Item and the active elements in Vector. Any exceptions are
-propagated and Vector is not modified. Insert_N then replaces the
+propagated and Vector is not modified. Insert then replaces the
old internal array by the new array, and then deallocates the old array.
Any exceptions raised during deallocation are propagated.
-procedure Insert_N
+procedure Insert_Empty_Space
(Vector : in out Vector_Type;
Before : in Index_Type'Base;
- Count : in Natural);
+ Count : in Size_Type);
-Equivalent to Insert_N (Vector, Before, Count, New_Item), with the
+Equivalent to Insert (Vector, Before, New_Item, Count), with the
difference that the elements in the Count positions starting at Before
are not assigned.
+[Open Issue: Is this a good idea? For a container with indefinite components,
+this would leave holes in the structure (since we wouldn't have any default
+value to fill in). Then we have to define what hitting a hole means. In
+general, Vectors are not intended to be sparse (use a Map if you want sparse),
+so that's just extra complication. A better way (but more expensive) to do this
+is to use the Insert with a Count to insert an appropriate "empty" value enough
+times. If we add array operations, we also would have them to fill this need.]
procedure Delete
(Vector : in out Vector_Type;
@@ -500,26 +567,35 @@
Equivalent to Delete (Vector, Last (Vector)).
-procedure Delete_N
+procedure Delete
(Vector : in out Vector_Type;
First : in Index_Type'Base;
- Count : in Natural);
+ Count : in Size_Type);
If Count is 0, the operation has no effect. If First does not specify a
value in the range First (Vector) .. Last (Vector), then
-Constraint_Error is propagated. Otherwise Delete_N slides the active
+Constraint_Error is propagated. Otherwise Delete slides the active
elements (if any) starting First plus Count down to First. Any
exceptions raised during element assignment are propagated.
+[Open Issue: Matt now thinks that this should be
+procedure Delete
+ (Vector : in out Vector_Type;
+ First : in Index_Type'Base;
+ Through: in Index_Type'Base);
+in order to more closely match Ada.Strings.Unbounded. But the definition of
+Delete in Ada.Strings.Unbounded has proven to be messy to use in practice
+(it is common to have a start and a length, calculating an end and verifying
+that it isn't past the end is messy and requires a if). Which should it be?]
-function Size (Vector : Vector_Type) return Natural;
+function Size (Vector : Vector_Type) return Size_Type;
Returns the length of the internal array.
procedure Resize
(Vector : in out Vector_Type;
- Size : in Natural);
+ Size : in Size_Type);
If Size (Vector) is equal to or greater than Size, the operation does
nothing. Otherwise Resize allocates a new internal array whose length
@@ -537,7 +613,10 @@
[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.]
+original proposal's author was inconclusive. Note that this function is mainly
+useful by analogy with other container packages; a For loop makes a better
+iterator for the Vector container. We could completely do without Front and
+Back for Vectors.]
function First (Vector : Vector_Type) return Index_Type;
@@ -583,6 +662,13 @@
Constraint_Error is propagated. Otherwise this function returns an
access value that designates a variable view of the element at Index.
+[Open Issue: This function requires that the internal elements of Element_Type
+are aliased. However, Ada 95 makes such items constrained, which is a problem
+if Element_Type is mutable (has defaulted discriminants). We either would have
+to declare such elements as not supported (which is really ugly) or remove
+this function (meaning that no update-in-place is possible for elements - a
+real issue for large/expensive-to-copy element types). Luckily, AI-363
+provides a solution - but if that is not adopted, we'll need to revisit this.]
procedure Replace_Element (Vector : in Vector_Type;
Index : in Index_Type'Base;
@@ -637,12 +723,9 @@
Containers.Vectors should be implemented similarly to an array. In particular,
the time taken by Append and Element should not depend on the number of
items in the Vector, and the time taken by Insert or Delete at First of the
-vector should take time roughly proportional to the number of elements in the
-vector.
+vector should take time no worse than roughly proportional to the number of
+elements in the vector.
-[Open issue: We should say that Containers.Vectors.Generic_Sort is O(N log N)
-on average,
-
AARM Note
We do not mean to overly constrain implementation stratgies here. However, it
is important for portability that the performance of large containers has
@@ -652,7 +735,7 @@
A call on an instantiation of Containers.Vectors.Generic_Sort should take on
average a time proportional to the log (base 2) of the number of items times
-the number of itmes in the vector.
+the number of items in the vector.
AARM Note
In other words, we're requiring the use of an O(N log N) sorting algorithm,
@@ -666,17 +749,50 @@
algorithm chosen is one that does not copy items unnecessarily. Bubble sort
would not meet this advice, for instance.
+[Open Issue: Should we also define "indefinite Element_Type" versions of these
+packages? They would allow String and T'Class containers to be used, at the
+cost of more memory allocation overhead. The wording cost is about one
+paragraph per package, with wording similar to that used for Wide_String
+versions of packages.
+
+There also is some sentiment for an indefinite Key_Type form of the Hashed_Map
+container. If we added that, we could eliminate the specific String version
+(or replace it by a language-defined instantiation).]
+
+[Open issue: Several reviewers complained about the lack of support for
+aggregate operations. Should there be operations to operate on slices of
+Vectors? These would take ranges similarly to Unbounded_Strings. Similarly,
+should there be operations to combine Vectors (such as an Insert of another
+Vector)?
+
+Another option to supporting more aggregate operations would be to define
+an array type for the package:
+ type Vector_Elements is array (Index_Type range <>) of Element_Type;
+and then provide operations going to and from this type. But note that this
+doesn't work for indefinite elements.
+
+See Matt's design note in the !appendix for more ideas in both of these veins.]
+
+[Open Issue: After indefinite elements, the number one complaint of reviewers
+was the removal of the List sequence container. While it doesn't have any
+additional operations over a Vector, it does have different performance
+characteristics (particularly for insertion at the front {O(1) instead of O(N)}
+and for arbitrary element access {O(N) instead of O(1), because a search is
+needed to find the element). Should this container be reintroduced?]
-A.17.3 The Package Containers.Maps
+A.17.3 The Package Containers.Hashed_Maps
-The language-defined package Containers.Maps provides
+The language-defined package Containers.Hashed_Maps provides
private types Map_Type and Cursor_Type, and a set of operations
for each type. A hashed map container allows an arbitrary type to be
used as a key to find the element associated with that key.
+AARM Note: The name is "Hashed_Maps" to allow for a secondary standard
+to include "Sorted_Maps".
+
Static Semantics
-The library package Containers.Maps has the following
+The library package Containers.Hashed_Maps has the following
declaration:
generic
@@ -694,7 +810,7 @@
with function "=" (Left, Right : Element_Type)
return Boolean is <>;
-package Ada.Containers.Maps is
+package Ada.Containers.Hashed_Maps is
pragma Preelaborate;
@@ -706,7 +822,7 @@
function "=" (Left, Right : Map_Type) return Boolean;
- function Length (Map : Map_Type) return Natural;
+ function Length (Map : Map_Type) return Size_Type;
function Is_Empty (Map : Map_Type) return Boolean;
@@ -747,10 +863,10 @@
Key : Key_Type)
return Element_Type;
- function Size (Map : Map_Type) return Hash_Type;
+ function Size (Map : Map_Type) return Size_Type;
procedure Resize (Map : in out Map_Type;
- Size : in Hash_Type);
+ Size : in Size_Type);
function First (Map : Map_Type)
return Cursor_Type;
@@ -758,9 +874,11 @@
function Back (Map : Map_Type)
return Cursor_Type;
- function Succ (Cursor : Cursor_Type) return Cursor_Type;
+ function Succ (Map : Map_Type;
+ Cursor : Cursor_Type) return Cursor_Type;
- procedure Increment (Cursor : in out Cursor_Type);
+ procedure Increment (Map : in Map_Type;
+ Cursor : in out Cursor_Type);
function Key (Cursor : Cursor_Type) return Key_Type;
@@ -798,7 +916,7 @@
... -- not specified by the language
-end Ada.Containers.Maps;
+end Ada.Containers.Hashed_Maps;
A object of type Map_Type contains a hash table, which is used
to provide direct access to elements. The *size* of an object of type Map_Type
@@ -925,17 +1043,20 @@
Key : Key_Type) return Cursor_Type;
If Length (Map) equals 0, then this function returns
-Null_Cursor. Otherwise, it calls Hash to compute the hash value of
-Key; any exceptions raised by Hash are propagated. It then uses Is_Equal_Key
-to check if Key is present in Map; any exceptions raised by Is_Equal_Key are
-propagated. If Key is present in Map, it returns an
-cursor designating the node with the matching key; otherwise, it
-returns Null_Cursor.
+Null_Cursor. Otherwise, it calls Hash to compute the hash value of Key;
+any exceptions raised by Hash are propagated. It then uses Is_Equal_Key
+to check if Key is present in Map; any exceptions raised by Is_Equal_Key
+are propagated. If Key is present in Map, it returns an cursor
+designating the node with the matching key; otherwise, it returns
+Null_Cursor.
-AARM Note:
+AARM Notes:
Find should only compare elements that hash to the same bucket in the hash
table.
+Null_Cursor is the same as Back (Map); it's possible to compare against Back
+for consistency with other containers.
+
The function Is_In is equivalent to Find (Map, Key) /= Null_Cursor.
The function Element is equivalent to Element (Find (Map, Key)).
@@ -943,7 +1064,7 @@
The function Size returns the size of Map.
procedure Resize (Map : in out Map_Type;
- Size : in Hash_Type);
+ Size : in Size_Type);
If Size (Map) is equal to or greater than Size, this operation has
no effect. Otherwise, it allocates a new hash table whose length is
@@ -978,13 +1099,13 @@
while I /= The_End loop
E := Element (I);
-- do something with E
- Increment (I);
+ Increment (M, I);
end loop;
end;
-[Open issue: This implies that Vectors ought to have Increment and Decrement
-procedures.]
+[Open issue: This implies that Vectors ought to have an Increment procedure.]
-function Succ (Cursor : Cursor_Type) return Cursor_Type;
+function Succ (Map : Map_Type;
+ Cursor : Cursor_Type) return Cursor_Type;
If Cursor equals Null_Cursor, then Constraint_Error is propagated.
Otherwise, Succ returns a cursor that designates the next node in Map.
@@ -999,7 +1120,7 @@
Cursor is the last node in a bucket, this will return the first node in the
next non-empty bucket.
-The procedure Increment is equivalent to Cursor := Succ (Cursor).
+The procedure Increment is equivalent to Cursor := Succ (Map, Cursor).
function Key (Cursor : Cursor_Type) return Key_Type;
@@ -1062,7 +1183,7 @@
Legality Rules
-An instantiation of Containers.Maps shall be at the library level.
+An instantiation of Containers.Hashed_Maps shall be at the library level.
AARM Note
A implementation will typically need to use controlled types to insure that
@@ -1084,34 +1205,45 @@
by a call on these routines should not increase significantly as the length of
the map increases.
-A.17.4 The Package Containers.String_Maps
+[Open Issue: A sorted version of the container also is typical (with parameters
+similar to the ones of the Sorted_Set). This was left out to keep the size
+of the containers library manageable. Should it be reintroduced?
+One presumes it would be included in the secondary standard if it is not
+included here.]
-The package Containers.String_Maps provides private
+A.17.4 The Package Containers.String_Hashed_Maps
+
+The package Containers.String_Hashed_Maps provides private
types Map_Type and Cursor_Type, and a set of operations for each
type. It provides the same hashed map operations as the package
-Containers.Maps does, with the difference that
+Containers.Hashed_Maps does, with the difference that
predefined type String is the key.
Static Semantics
The declaration of the library package
-Containers.String_Maps has the same contents as Containers.Maps except:
+Containers.String_Hashed_Maps has the same contents as
+Containers.Hashed_Maps except:
* There is no generic formal Key_Type. Everywhere the formal type Key_Type
is specified, it is systematically replaced by type String.
+ * The generic formal function Hash has a named default, the function
+ Ada.Strings.Hash.
* The Generic_Key function is omitted.
-A.17.5 The Package Containers.Wide_String_Maps
+A.17.5 The Package Containers.Wide_String_Hashed_Maps
Static Semantics
-The declaration of the library package
-Containers.Wide_String_Maps has the same contents as Containers.String_Maps
-except that everywhere the formal type String is specified, it is
-systematically replaced by type Wide_String.
+The declaration of the library package Containers.Wide_String_Hashed_Maps has
+the same contents as Containers.String_Hashed_Maps except that everywhere the
+formal type String is specified, it is systematically replaced by type
+Wide_String. The named default for generic formal function Hash is replaced
+by Ada.Strings.Wide_Hash.
+
A.17.6 The Package Containers.Sorted_Sets
The language-defined package Containers.Sorted_Sets provides
@@ -1154,7 +1286,7 @@
function ">=" (Left, Right : Set_Type) return Boolean;
- function Length (Set : Set_Type) return Natural;
+ function Length (Set : Set_Type) return Size_Type;
function Is_Empty (Set : Set_Type) return Boolean;
@@ -1247,16 +1379,14 @@
type Key_Type (<>) is limited private;
- with function "<" (Left : Element_Type; Right : Key_Type)
+ with function "<" (Left : Key_Type; Right : Element_Type)
return Boolean is <>;
- with function "<" (Left : Key_Type; Right : Element_Type)
+ with function ">" (Left : Key_Type; Right : Element_Type)
return Boolean is <>;
package Generic_Keys is
- pragma Preelaborate;
-
function Is_In (Key : Key_Type;
Container : Set_Type)
return Boolean;
@@ -1450,9 +1580,9 @@
the generic formal less-than operator for elements. Any exception
raised by less-than is propagated. If it finds an equivalent element,
it returns a cursor designating the node that contains the element.
-Otherwise it returns Null_Cursor.
+Otherwise it returns Back (Set).
-The function Is_In is equivalent to Find (Set, Item) /= Null_Cursor.
+The function Is_In is equivalent to Find (Set, Item) /= Back (Set).
function Lower_Bound (Set : Set_Type;
Item : Element_Type) return Cursor_Type;
@@ -1535,17 +1665,17 @@
function Element (Cursor : Cursor_Type) return Element_Type;
-If Cursor equals Null_Cursor, then Constraint_Error is propagated.
+If Cursor equals Null_Cursor or Back (Set), then Constraint_Error is propagated.
Otherwise, it returns the element on the node designated by Cursor.
generic
- type Element_Access is access constant Element_Type;
+ type Element_Access is access Element_Type;
function Generic_Element (Cursor : Cursor_Type)
return Element_Access;
-If Cursor equals Null_Cursor, then Constraint_Error is propagated.
-Otherwise, it returns an access value that designates a constant view of
-the the element on the node designated by Cursor.
+If Cursor equals Null_Cursor or Back (Set), then Constraint_Error is
+propagated. Otherwise, it returns an access value that designates a constant
+view of the the element on the node designated by Cursor.
generic
with procedure Process (Cursor : in Cursor_Type) is <>;
@@ -1614,6 +1744,13 @@
be dropped if AI-344 or some other solution to nested controlled types is
adopted.
+Erroneous Execution
+
+Execution is erroneous if the access returned by an instantiation of
+Generic_Element changes the element so that the either of the formal
+subprograms "<" and "=" could give different results than before the
+modification.
+
Implementation Advice
Insertions and searches in a Sorted_Set should take no longer than a time
@@ -1622,6 +1759,12 @@
AARM Note
This can be accomplished with a balanced (red-black) tree for keys.
+[Open Issue: A hashed version of this container also is typical (with
+parameters similar to the ones of the Hashed_Map). This was left out to keep
+the size of the containers library manageable. Should it be reintroduced?
+One presumes it would be included in the secondary standard if it is not
+included here.]
+
!example
A.17.2 The Package Containers.Vectors
@@ -1673,8 +1816,8 @@
Note that we can't use the front end as the top of the stack, because
there's no Delete_First.
-The Insert_N operation essentially opens up a "hole" in the middle of
-the internal array. It's more efficient to do it this way than
+The Insert_Empty_Space operation essentially opens up a "hole" in the
+middle of the internal array. It's more efficient to do it this way than
inserting items one-at-a-time, because the sliding is done only once.
For example, we can copy an array (or any other container) into a vector
at some arbitary position like this:
@@ -1686,7 +1829,7 @@
J : Index_Type'Base := I;
begin
- Insert_N (V, Before => I, Count => A'Length); -- dig the hole
+ Insert_Empty_Space (V, Before => I, Count => A'Length); -- dig the hole
for Index in A'Range loop
Replace_Element (V, J, By => A (Index)); -- fill the hole
@@ -1838,7 +1981,7 @@
procedure Op (V : in out Vector_Type) is
begin
- Insert (V, Before => Back (V)); -- no item
+ Insert_Empty_Space (V, Before => Back (V), Count => 1); -- no item
declare
E : Element_Subtype renames To_Access (V, Last (V)).all;
@@ -1870,7 +2013,7 @@
begin
Append (L, New_Item => E);
... -- populate vector some more
- Insert (V, Before => Back (V)); -- create a new element in V
+ Insert_Empty_Space (V, Before => Back (V), Count => 1); -- create a new element in V
Swap (V, Last (V), L); -- swap new element in V with L
end;
@@ -2025,7 +2168,7 @@
active iterator can be the same for all of the containers.
-A.17.3 The Package Containers.Maps
+A.17.3 The Package Containers.Hashed_Maps
It's often the case that you know apriori the total number of elements
you intend to insert into the map. Under these circumstances you should
@@ -2034,7 +2177,7 @@
properly sized, and thus avoids the automatic rehashing that occurs
during normal insertion to preserve the load factor. For example:
- procedure Op (N : Natural) is
+ procedure Op (N : Size_Type) is
Map : Map_Types.Map_Type; -- Size = 0
Cursor : Map_Types.Cursor_Type;
@@ -2091,7 +2234,7 @@
while I /= Null_Cursor loop
Process (I);
- Increment (I);
+ Increment (Map, I);
end loop;
end Op;
@@ -2132,6 +2275,11 @@
procedure Process (Cursor : Cursor_Type) is ...;
+ function Succ (C : Cursor_Type) return Cursor_Type is
+ begin
+ return Succ (Map, C);
+ end;
+
procedure Algorithm is
new Generic_Algorithm (Cursor_Type); -- accept defaults
@@ -2188,7 +2336,7 @@
new Ada.Containers.Generic_Hash_Discrete (C.int); -- or whatever
package FD_Map_Types is
- new Ada.Containers.Maps
+ new Ada.Containers.Hashed_Maps
(Key_Type => C.int,
Element_Type => Session_Access,
Hash => Hash_FD);
@@ -2237,7 +2385,7 @@
and then the session object reacts to the I/O completion accordingly.
-A.17.4 The Package Containers.String_Maps
+A.17.4 The Package Containers.String_Hashed_Maps
Hashed maps with type String as the key are nearly ubiquitous. The
canonical example is of course the word-frequency problem, in which
@@ -2250,7 +2398,7 @@
with Ada.Strings.Hash_String;
package Wordcount_Maps is
- new Ada.Containers.String_Maps
+ new Ada.Containers.String_Hashed_Maps
(Element_Type => Natural,
Hash => Ada.Strings.Hash_String); -- case-sensitive
@@ -2409,7 +2557,7 @@
Our cache is just a map, indexed by file name:
package File_Cache_Types is
- new Ada.Containers.String_Maps
+ new Ada.Containers.String_Hashed_Maps
(Element_Type => Context_Access,
Hash => Ada.Strings.Hash_String_Case_Insensitive,
Is_Equal_Key => Ada.Containers.Equal_String_Case_Insensitive);
@@ -2554,7 +2702,7 @@
as the key, and a Session_Access as the element, like this:
package Id_Maps is
- new Ada.Containers.String_Maps
+ new Ada.Containers.String_Hashed_Maps
(Element_Type => Session_Access,
Hash => Ada.Strings.Hash_String); -- case-sensitive
@@ -5072,63 +5220,1299 @@
****************************************************************
-From: Matthew Heaney
-Sent: Thursday, February 5, 2004 9:31 AM
+From: Jeffery Carter
+Sent: Friday, February 6, 2004 1:05 PM
+A comment on type names.
+
+Ada 83, with the unfortunate* exception of File_Type, did not use
+"_Type" on the end of predefined type names. We have Address and Count,
+not Address_Type and Count_Type. Ada 95 adhered to this principle, so we
+have Storage_Element and Unbounded_String, not Storage_Element_Type and
+Unbounded_String_Type.
+
+For consistency, I think the Ada-0X process should also adhere to this
+principle. The use of "_Type" on type names in the proposal should be
+eliminated. This takes some time and thought to do well; I am willing to
+volunteer for the effort if the Committee cannot spare the time and
+cannot find anyone preferable.
+
+This is a matter of consistently. While it is not my style, and not
+recommended by the Quality and Style Guide, I have used libraries that
+use the "_Type" convention without problem. I am concerned that the ARM
+be consistent far more than I am about what convention the ARM uses.
+
+*"Unfortunate" because it is inconsistent.
+
****************************************************************
From: Matthew Heaney
-Sent: Thursday, February 5, 2004 9:31 AM
+Sent: Friday, February 6, 2004 9:33 AM
+I have updated the reference implementation, which now has the sorted
+set container, too.
+
+There's also a test_sets.adb, so you have something to run. You can
+pass a seed on the command line.
+
+<http://home.earthlink.net/~matthewjheaney/charles/ai302-20040206.zip>
+
+I'll take care of the hashed map containers this weekend, and post Mon AM.
+
****************************************************************
From: Matthew Heaney
-Sent: Thursday, February 5, 2004 9:31 AM
+Sent: Friday, February 6, 2004 3:36 PM
+
+Martin Dowie wrote:
+
+> I was thinking, primarily, of a project that used single (bounded) lists to
+> hold commands (a basic, domain-specific, scripting language I guess),
+> one of which was 'stop this sequence of commands'.
+
+It sounds like you have a sequence container, that you traverse from
+front to back.
+
+The only sequence container in the proposal is a vector, which doesn't
+have a passive iterator. Again, I recommend just using a loop:
+
+ for Index in First (V) .. Last (V) loop
+ declare
+ Command : Command_Type := Element (V, Index);
+ begin
+ exit when Is_Stop (Command);
+ -- process command
+ end;
+ end loop;
+
+
+If these are commands that have an order (say, each command has a
+timestamp, and commands are executed in timestamp order), then you can
+use the sorted set. Again, an explicit loop is appropriate:
+
+declare
+ I : Cursor_Type := First (S);
+ J : constant Cursor_Type := Back (S);
+begin
+ while I /= J loop
+ declare
+ Command : Command_Type := Element (I);
+ begin
+ exit when Is_Stop (Command);
+ -- process command
+ end;
+
+ Increment (I);
+ end loop;
+end;
****************************************************************
-From: Matthew Heaney
-Sent: Thursday, February 5, 2004 9:31 AM
+From: Alexandre E. Kopilovitch
+Sent: Friday, February 6, 2004 4:24 PM
+
+> The only sequence container in the proposal is a vector,
+Ah, yes, it's Sequence - quite right name for that container (and not Vector).
+
****************************************************************
-From: Matthew Heaney
-Sent: Thursday, February 5, 2004 9:31 AM
+From: Jeffrey Carter
+Sent: Friday, February 6, 2004 7:17 PM
+Randy Brukardt wrote:
+
+> Let's see:
+> - direct analogs to indexing, both LHS and RHS (Element, Replace_Element);
+> - slices (nope);
+> - 'First (First), 'Last (Last), 'Length (Length);
+>
+> Looks like pretty much everything is in there. And slicing will be expensive
+> if the implementation is not a straight array, so it's somewhat dubious.
+> Insert and Delete provide easier ways of adding or removing items than
+> slices - and how often do you use a slice of a non-string type for something
+> other than inserting or deleting elements anyway??
+
+Slicing isn't included because C++ doesn't have slices, so it's a
+foreign concept to its library and users. If we want to attract users of
+inferior languages to Ada, it should be because Ada is better. Ada's
+slices are a way that Ada is better; Ada's standard extensible array
+component should be better than its competition by also offering them. I
+do not see mimicking C++'s shortcomings as advisable.
+
+Insertion and deletion are basic operations of lists, but not of arrays.
+That's why the list and vector components had the same set of
+operations: they both specify lists with different implementations.
+
+Since String is an array, and [Un]Bounded_String is an extensible array,
+and we're now told the correct name is Vector, shouldn't these be
+renamed to something like Character_Vector?
+
+> Ada doesn't (and isn't) going to support user-defined indexing or
+> user-defined attributes, so this is about the best you can do. So what's the
+> complaint (other than the name)??
+
+I don't expect user-defined indexing, slices, or attributes, which is
+why I talked about "analogs" to them. Missing slices is one complaint.
+And, yes, the name is unarguably wrong.
+
+In the C family of languages, users are accustomed to having to look at
+implementations in order to understand how to use something. Subprogram
+"prototypes" (yet another misused term to add to the collection) are
+generally insufficient, and appropriate comments are often lacking. So
+it comes as no surprise to me that C++ expects newcomers to its library,
+looking for an extensible array, and not finding anothing with an
+appropriate name, to have to look at the operations of the components to
+find that the inappropriately named "vector" is really an extensible array.
+
+However, this is not the Ada way, and I think it completely
+inappropriate to mimick this mistake. Looking at other languages'
+library to select useful components is fine; insisting that an Ada
+version must be identical to that of another language, including
+mistakes, is not.
+
+> The user can easily code a queue in terms of a Vector (that's one of the
+> uses of Insert!). We dropped the list component because it had an identical
+> interface to the Vector component, but was less flexible (no computed O(1)
+> access).
+
+The perfomance of a queue based on an extensible array is likely to be
+just as objectionable as extracting an element from an extensible array
+based on a list. That the vector and list components both had the same
+interface is further evidence that mimicking the STL is a bad idea.
+Insert and delete are as foreign to an extensible array as indexing and
+slicing should be to a list.
+
+> In my view, it is a mistake for projects to depend on standard containers
+> where there are critical performance requirements (not just time, but also
+> space as well). In that case, you really have to have control of the
+> implementation -- you really need *all* of the source code. You can't trust
+> something provided by the standard (or your compiler vendor) in those cases.
+
+I agree. That doesn't mean that the standard shouldn't provide a basis
+for queues with performance characteristics suitable for performance
+non-critical applications, which an extensible array does not provide.
+
****************************************************************
-From: Matthew Heaney
-Sent: Thursday, February 5, 2004 9:31 AM
+From: Randy Brukardt
+Sent: Friday, February 6, 2004 8:24 PM
+Jeff Carter wrote:
+
+...
+> I agree. That doesn't mean that the standard shouldn't provide a basis
+> for queues with performance characteristics suitable for performance
+> non-critical applications, which an extensible array does not provide.
+
+Huh? You've said, in effect, that the performance isn't good enough for
+applications where the performance doesn't matter. That's a pretty goofy
+statement!
+
+My opinion has not changed: if you care about performance *at all*, you
+*cannot* depend on *any* standard containers. But usually the performance
+does not matter at all (or so little as to be equivalent to not at all): the
+number of elements in the container is small (which would be true for
+virtually all queues), and/or it is used infrequently, and/or the
+application is a throw-away.
+
+Otherwise, if you are writing portable code, you shouldn't use a predefined
+container library at all -- the performance is likely to vary much more
+across implementations than code you write yourself. For instance, on
+Janus/Ada, any generic list container is going run 2-5 times slower than the
+same list created yourself -- that's just the effect of the extra call
+overhead and the shared body (which means the elements will be dynamically
+allocated - separately - in any case - at least doubling the allocation
+overhead). I'd expeect that effect to be much less on GNAT, for example,
+because they don't share generic bodies and thus don't have the double
+allocation overhead.
+
+If your application doesn't care about the component being 5 times slower,
+then it is highly unlikely that it is going to care about whether the
+Vector/Sequence/List component is implemented as an array, as a list, as a
+tree, as a hash table, or as something else.
+
+My preference with these components would be to say absolutely nothing about
+performance or implementation (because anything said is as meaningless as
+real-time metrics are). But others believe that that would cause real
+portability problems, and I'm willing to go along with that.
+
+The problem I see is a lot of people are looking far too closely at tiny
+pieces of abstractions. You might have a queue or a list as part of a large
+abstraction, but they're pretty much useless by themselves. And given that
+creating a queue or stack (both of which have only two operations, both
+trivial!) would take 3 minutes max, it makes no sense to use a complex (and
+necessarily slow) container library for just that -- indeed, it probably
+would be more work to use a container than the 3 minutes.
+
+I much prefer the vision of this containers library, where the only
+containers included are those that are large, complex, multi-purpose, and
+have a clear abstraction.
+
****************************************************************
-From: Matthew Heaney
-Sent: Thursday, February 5, 2004 9:31 AM
+From: Jeffrey Carter
+Sent: Friday, February 6, 2004 7:39 PM
+
+Matthew Heaney wrote:
+
+> No. Vector iterators are fragile, and hence very error prone.
+
+Modifying a structure from an iterator should be a bounded error.
+
+> 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.
+
+You can only talk about what happens internally during an operation if a
+specific implementation is required, which Randy assures us is not the case.
+
+> 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.
+I've used sets for decades, in discrete math, in specification languages
+such as Z, and in programming. A set is an unordered collection of
+elements from a universe that provides operations such as membership,
+union, intersection, and the like, represented by mathematical symbols
+that I can't reliably represent in an e-mail.
+
+An implementation of a set may be sorted to speed up operations, but
+that's a feature of the implementation, not of the concept implemented.
+That's a distinction that many users of C-family languages seem unable
+to make, but that I expect from those who embrace Ada.
+
+> The name for Delete_Sans_Increment comes from Emacs lisp, which has the
+> functions file-name-sans-extension and file-name-sans-versions.
+
+Yet another case of mimicking others' errors.
+
+> 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?
+
+"Rendezvous" is not a predefined indentifier in the ARM. It was chosen
+because no English word has the precise meaning intended, and Ada's
+designers understood the importance of precise terminology.
+
+> 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've been using arrays, including extensible arrays, sets, and maps for
+decades. I've also been using vectors for decades, having done a lot of
+scientific programming that required matrix math. I doubt that a study
+of C++ mistakes would have any effect besides raising my blood pressure.
+
****************************************************************
-From: Matthew Heaney
-Sent: Thursday, February 5, 2004 9:31 AM
+From: Jeffrey Carter
+Sent: Friday, February 6, 2004 7:22 PM
+
+Randy Brukardt wrote:
+> Precisely my point. That is intended to say that there is a logical array in
+> the container, but not necessarly an actual one. Matt's descriptions were
+> too implementation-specific, and we moved most of that. But I'm not
+> surprised that some was missed.
+
+On closer inspection, the Size and Resize operations certainly imply an
+array implementation; they are meaningless otherwise.
+
****************************************************************
-From: Matthew Heaney
-Sent: Thursday, February 5, 2004 9:31 AM
+From: Randy Brukardt
+Sent: Friday, February 6, 2004 9:09 PM
+
+Huh? Resize tells the container a reasonable size to use; what the container
+does with that information is up to it. Size simply returns that
+information.
+
+That's no different than many of the attributes in Ada, which (if set),
+always return the values that they were set to. But what the compiler does
+with those values is (almost) completely implementation-defined.
+
+The only real requirement here is O(1) element access (which prevents the
+use of a straight linked list).
+
+Janus/Ada will probably use an array of pointers (or possibly array of
+arrays of pointers); we're going to be (implicitly) allocating the elements
+anyway, we might as well do it explicitly and take advantage of that to make
+Insert/Delete/Sort (and any expansions) much cheaper (presuming the elements
+are bigger than scalar types). An array of arrays of pointers is even
+better, because insertion cost is bounded by the maximum size of an array
+chunk -- but there is more overhead and complexity, so I'd like to see some
+real uses before deciding on an implementation.
+
+Note that a pure list component has no real opportunity for "better"
+implementations, and indeed, any implementation on Janus/Ada would suffer
+from "double" allocation.
****************************************************************
-From: Matthew Heaney
-Sent: Thursday, February 5, 2004 9:31 AM
+From: Martin Dowie
+Sent: Saturday, February 7, 2004 4:02 AM
+> We dropped the passive iterator from the Ada.Directories package precisely
+> because even ARG members were confused about how it worked. Even though it
+> was a classic passive iterator with a Quit parameter. Perhaps the confusion
+> really was the Quit parameter (I thought it was the whole idea), but in any
+> case, you've got to keep them simple.
+
+I didn't find it confusing so I provided an extra child
+Ada.Directories.Iterate - and I've used it repeatedly!
+
+> > This pattern has since shown itself to be quite common in embedded
+> > systems - for either domain-specific scripting languages or graphics.
+> >
+> > There is the other idiom where one is processing an iteration of items
+> > and an external event occurs that stops the processing - e.g. the 'stop'
+> > button is pushed on a GUI-search window, but it could equally be a
+> > 50Hz message over a 1553.
+>
+> It seems to me that an abort situation is best handled by propagating an
+> exception. Otherwise, you end up distributing termination code/flags
+> everywhere in the application. But YMMV.
+
+I have tended to work in deeply enbedded systems, where exceptions (in
+any language!) are at best frowned upon and quite often forbidden! :-(
+
****************************************************************
-From: Matthew Heaney
-Sent: Thursday, February 5, 2004 9:31 AM
+From: Martin Dowie
+Sent: Saturday, February 7, 2004 4:25 AM
+
+> > I was thinking, primarily, of a project that used single (bounded) lists to
+> > hold commands (a basic, domain-specific, scripting language I guess),
+> > one of which was 'stop this sequence of commands'.
+>
+> It sounds like you have a sequence container, that you traverse from
+> front to back.
+
+Pretty much, although we also read in where each 'First' is as the whole
+contained many 'subroutines'.
+
+
+> The only sequence container in the proposal is a vector, which doesn't
+> have a passive iterator. Again, I recommend just using a loop:
+
+I suspect the first thing I will do is add an extra child generic subprogram
+Ada.Containers.Vectors.Iterate! :-)
****************************************************************
-From: Matthew Heaney
-Sent: Thursday, February 5, 2004 9:31 AM
+From: Martin Krischik
+Sent: Saturday, February 7, 2004 6:16 AM
+
+> I suspect the first thing I will do is add an extra child generic
+> subprogram Ada.Containers.Vectors.Iterate! :-)
+
+Well, guess don't use GNAT. GNAT gets quite upset if you try to add something
+to the Ada packages.
+
+****************************************************************
+
+From: Marius Amado Alves
+Sent: Saturday, February 7, 2004 7:45 PM
+
+I'd expect *any* compiler to get really upset with this ;-)
+
+****************************************************************
+
+From: Martin Dowie
+Sent: Sunday, February 8, 2004 2:08 AM
+
+"gcc -gnatg" or "gnatmake -a" will stop any warnings :-)
+
+****************************************************************
+
+From: Martin Krischik
+Sent: Saturday, February 7, 2004 5:09 AM
+
+> Jeffrey Carter wrote:
+
+> > 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.
+
+> The user can easily code a queue in terms of a Vector (that's one of the
+> uses of Insert!). We dropped the list component because it had an identical
+> interface to the Vector component, but was less flexible (no computed O(1)
+> access).
+
+True enough. But if you wanted a build generic queue on top of the vector the
+tag should not be hidden from view. Otherwise one need to repeat all the
+access methods instead of just renaming the one provided from the parent
+package.
+
+In fact the hidden tag is the one feature which I realey dislike in charles.
+
+****************************************************************
+
+From: Stephen Leake
+Sent: Saturday, February 7, 2004 8:40 AM
+
+"Randy Brukardt" <randy@rrsoftware.com> writes:
+
+> Report of the ARG Select Committee on Containers
+> February 3, 2004
+
+Thanks for the committee's hard work on this.
+
+What is the rationale for making the Map Key_Type definite, as opposed
+to indefinite? Since an indefinite Key_Type is required for
+Containers.Maps.Strings, why not make that capability available to the
+users?
+
+I don't see a discussion of this in AI-302-03/01.
+
+
+Another point: Containers.Vectors.Size should return Index_Type'Base,
+and the Size parameter in Resize should also be Index_Type'Base. It's
+confusing to have different types for Size and Index.
+
+There's also a problem if Natural'Last < Index_Type'Last; you
+can't have a vector that contains every index!
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Saturday, February 7, 2004 6:03 PM
+
+> What is the rationale for making the Map Key_Type definite, as opposed
+> to indefinite?
+
+The 'committee' primarily adopted the existing proposal submitted by Matt
+Heaney. We decided not to change any of the major design decisions of that
+proposal - because no package will suit everyone or every need, and we felt
+it was more important to standardize something coherently designed for most
+needs than to fiddle endlessly with it and risk introducing serious bugs.
+
+Which is to say, I don't know. :-)
+
+> Since an indefinite Key_Type is required for
+> Containers.Maps.Strings, why not make that capability available to the
+> users?
+
+We definitely expect that the strings container will use a purpose-built
+data structure for storing strings, not some general indefinite item
+capability. Ways to compactly and efficiently store sets of varying size
+strings are well known and commonly used.
+
+Such algorithms could be extended to a general "unconstrained array of
+elementary", but that hardly seems to be a worthwhile definition for keys.
+
+...
+> Another point: Containers.Vectors.Size should return Index_Type'Base,
+> and the Size parameter in Resize should also be Index_Type'Base. It's
+> confusing to have different types for Size and Index.
+>
+> There's also a problem if Natural'Last < Index_Type'Last; you
+> can't have a vector that contains every index!
+
+Yes, that's a serious problem on Janus/Ada (Integer is 16-bit). However, you
+want the Size and Resize operations to take a numeric type that contains
+zero -- and certainly Index_Type is not that. Index_Type could be a subtype
+of an enumeration type or a subtype of a modular type (neither of which can
+contain zero) or a subtype of an integer type not containing zero.
+
+We had a short, inconclusive discussion about whether the index type ought
+to be range <> rather than (<>) (because enumeration and modular types fail
+the assertion and thus aren't directly usable), but that still doesn't
+guarantee a zero. Moreover, if the integer type has negative numbers, then
+the Length of the vector could be larger than Index_Type'Last.
+
+So I don't see a great solution. I wondered about using "Hash_Type" here (it
+has the correct properties), but that seems like a misuse of the type (and a
+bad idea in a library that most Ada programmers will read - you want to show
+them good style in standard libraries).
+
+****************************************************************
+
+From: Martin Krischik
+Sent: Saturday, February 7, 2004 5:15 AM
+
+> The perfomance of a queue based on an extensible array is likely to be
+> just as objectionable as extracting an element from an extensible array
+> based on a list. That the vector and list components both had the same
+> interface is further evidence that mimicking the STL is a bad idea.
+> Insert and delete are as foreign to an extensible array as indexing and
+> slicing should be to a list.
+
+Well, depends. Most queues are not supposed to grow indefinetly so an using a
+vector with an modular type as index will give you good perfomace. Every Ada
+tutorial contains a expample on how to do it.
+
+****************************************************************
+
+From: Martin Krischik
+Sent: Saturday, February 7, 2004 6:14 AM
+
+> The committee selected the second proposal as a starting point for a
+> standard containers library, with a number of simple changes. The
+> changes were simple enough that we produced a version of the library with
+> the changes made (AI-00302-3/01).
+
+Any place where I can actualy read the draft?
+
+Anyway, looking at the reference impementation vom Matthew Heaney (thanks for
+the quick responce) I have an improvements to suggest:
+
+type Element_Type is private;
+
+I said this bevore that is too limiting. With that signature you can't even
+store strings. And more important you cant store Element'Class. In fact I
+predict that with that signature 80% of all data stored will be "access to
+something".
+
+I have often heard Ada does not need garbage collection since a good container
+library should take care of memory management - and now I ready to follow
+that point. But taking that argument, vector is not a good container.
+
+Since vector will need heap storrage anyway and performace is only a minor
+issue I suggest:
+
+type Element_Type (<>) is private;
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Saturday, February 7, 2004 6:05 PM
+
+> Any place where I can actualy read the draft?
+
+The same place that you can read any other AI: www.ada-auth.org.
+
+****************************************************************
+
+From: Martin Krischik
+Sent: Sunday, February 8, 2004 4:58 AM
+
+I looked there but I only found a very long discussion but not the
+actual concluding decision.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Monday, February 9, 2004 6:03 PM
+
+Don't know what you're looking for, but certainly the entire AI is posted
+there. As with all AIs, the !wording section is what goes into the standard.
+
+****************************************************************
+
+From: Martin Krischik
+Sent: Saturday, February 7, 2004 6:24 AM
+
+> > The only sequence container in the proposal is a vector,
+>
+> Ah, yes, it's Sequence - quite right name for that container (and not
+> Vector).
+
+No, in my book elements in a Sequence have only a relative positions, or at
+least the relative position is the primary position and absolut position is
+only the secondary.
+
+That is: Get_Next (V); is faster or as fast as Get (V, 5);
+
+****************************************************************
+
+From: Martin Krischik
+Sent: Saturday, February 7, 2004 6:32 AM
+
+> My understanding of the model is that passive iterators are only for cases
+> where you want to iterate over the entire container.
+
+Yes.
+
+> Indeed, given the iteration model of packages,
+> there's hardly any reason to use a passive iterator.
+
+Passive Iterators should allways provide the fastes mean to iterate over the
+hole container. They should do so by knowing the internals of the container.
+
+Of course it only matters in advanced container with B-Trees or AVL-Trees as
+as internal structure. But I have only seen those in IBM's Open Class Library
+(which is far better the the STL).
+
+But there are no advanced containers in AI 302.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Saturday, February 7, 2004 6:21 PM
+
+> Passive Iterators should allways provide the fastes mean to iterate over the
+> hole container. They should do so by knowing the internals of the
+> container.
+
+That might be true in a language with a built-in iterator construct, but it
+is certainly not true in Ada because of the overhead of calling the generic
+formal subprogram for each element. In Janus/Ada, the overhead of calling a
+formal subprogram is at least double of a normal subprogram (we have to save
+and restore display information, because you could be calling into a more
+nested scope than the generic body -- something that normally isn't possible
+in Ada).
+
+Other compilers may not have that overhead, but they'll certainly have call
+overhead. Whereas, the explicit loop iterator for Vectors only needs to call
+Element. So the call overhead is at best a wash, and at worst much worse for
+the passive iterator. Moreover, the compiler is a lot more likely to be able
+to in-line the call to Element (which likely has a pretty simple
+implementation and thus will meet the in-lining qualifications), than the
+bunch of arbitrary code in the Process formal routine.
+
+So, a passive iterator will only be faster in complex containers (where you
+have to separate the Element and Successor functions). For a Vector (where
+the language already has the needed iteration mechanism built-in), it's
+going to be slower (or, if you're really lucky, the same speed) and it
+certainly is a lot harder to write.
+
+So I think having it on Vector would simply be for consistency; you'd never
+actually use it if you know you're dealing with a Vector.
+
+****************************************************************
+
+From: Robert A. Duff
+Sent: Saturday, February 7, 2004 7:22 PM
+
+> Other compilers may not have that overhead, but they'll certainly have call
+> overhead. Whereas, the explicit loop iterator for Vectors only needs to call
+> Element. So the call overhead is at best a wash, and at worst much worse for
+> the passive iterator. Moreover, the compiler is a lot more likely to be able
+> to in-line the call to Element (which likely has a pretty simple
+> implementation and thus will meet the in-lining qualifications), than the
+> bunch of arbitrary code in the Process formal routine.
+
+I don't see why the compiler shouldn't inline the Process routine,
+assuming the compiler isn't doing shared generics. They're usually
+small, but anyway, the Process routine is typically called exactly
+once, so it shouldn't matter how big it is.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Saturday, February 7, 2004 7:33 PM
+
+Most compilers have limitations on what can be inlined; Process (which
+contains arbitrary code) is far more likely to violate one of those
+limitations than Element (which never changes and is likely to be very
+simple). In addition, many compilers only inline when you give pragma
+Inline, and you can't do that on a generic formal.
+
+****************************************************************
+
+From: Robert A. Duff
+Sent: Saturday, February 7, 2004 7:43 PM
+
+If Process violates whatever these arbitrary restrictions are, then
+sure, you can't get it inlined. But typically Process is very simple --
+often just one line of code that calls some other procedure to do the
+real work, passing some additional parameters. Process isn't a "real"
+procedure, conceptually -- it's just the body of a loop.
+
+In my current project, we make heavy use of the generic iterator
+pattern, and I think that in many many cases, Process is just
+a line or two of code. (And if it's more, inlining is relatively
+less important.)
+
+>... In addition, many compilers only inline when you give pragma
+> Inline, and you can't do that on a generic formal.
+
+You give the inline on the actual. In non-sharing implementations,
+that should apply inside the instance. And the iterator procedure
+itself can be inlined, too.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Saturday, February 7, 2004 8:04 PM
+
+Certainly it's not real (which is one thing I dislike about passive
+iterators in Ada - but we've discussed that before), but if it is very short
+(or the bodies of your loops are typically very short), then you're
+programming style must be very different from mine. The only loops that I
+write that are very short are those that I probably shouldn't have written
+in the first place (like the one finding the last '.' in a string) --
+there's a routine somewhere in Ada.Strings that will do the job, but looking
+it up is more work than writing the loop. (And a lot of them would be
+replaced by a Vector/List/Sequence container if I had one.)
+
+But just looking at the spam filter I'm working on at this moment: The
+average loop length is about 25 lines, the mean is around 8 lines. (There
+are more short loops than I would have guessed. But most of them wouldn't
+exist if I had a container to use instead - most of them are insert-at-end
+or delete-specific-item from a list.)
+
+...
+> You give the inline on the actual. In non-sharing implementations,
+> that should apply inside the instance. And the iterator procedure
+> itself can be inlined, too.
+
+At which point, you *equal* the performance of the active iterator. And only
+if *everything* goes right. The OP claimed that the passive iterator would
+always have better performance, and that's certainly not true for the vector
+container. I doubt that it would be true for the Map container, either. It
+could be true for a complex container, but those aren't commonly used.
+
+****************************************************************
+
+From: Alexandre E. Kopilovitch
+Sent: Saturday, February 7, 2004 7:55 PM
+
+Martin Krischik wrote:
+
+> > > The only sequence container in the proposal is a vector,
+> >
+> > Ah, yes, it's Sequence - quite right name for that container (and not Vector).
+>
+> No, in my book elements in a Sequence have only a relative positions, or at
+> least the relative position is the primary position and absolut position is
+> only the secondary.
+
+I don't know in which domain your book was grown up, but I can assure you that
+in mathematics (and by extension in physics and other natural sciences as they
+use mathematical apparatus) elements of a sequence are commonly indexed, and
+those indices are always treated as absolute position (which may be zero or
+even negative). By the way, your book is also certainly not from Biology/Genetics,
+where term "sequence" is used heavily, and they often speak about both absolute
+and relative positions in sequences.
+
+We have clearly different usage of terms "vector" and "sequence": substantial
+part of today's software engineering (tools and books) use them one way, while
+mathematics (and all natural sciences that use it heavily) always use them another
+way.
+
+So all the argument here about Vector/Sequence here is about Ada's choice of
+preference: will Ada choose software engineering (effectively, Java and C++
+libraries) side or mathematical/scientific side on this issue.
+
+I suppose (or hope) that the thesis "Ada is for problem space, not for solution
+space" implies the latter.
+
+****************************************************************
+
+From: Martin Krischik
+Sent: Sunday, February 8, 2004 11:40 AM
+
+> I don't know in which domain your book was grown up, but I can assure you
+
+It's the english dictornary: "Aufeinanderfolge, Reihenfolge, Szene,
+Zeitfolge". Ah, you don't speak german. Well let's look for "Reihenfolge" in
+a rushian dictornary (and have a fight with my wives rushian keyboard):
+"???????????".
+
+Asking my wives what it means she said "one after the other, queue".
+
+> that in mathematics (and by extension in physics and other natural sciences
+> as they use mathematical apparatus) elements of a sequence are commonly
+> indexed, and those indices are always treated as absolute position (which
+> may be zero or even negative). By the way, your book is also certainly not
+> from Biology/Genetics, where term "sequence" is used heavily, and they
+> often speak about both absolute and relative positions in sequences.
+
+I have spend 4 years in Great Britain I am shure if I ask anyone on the street
+there "what is a sequence" he or she will answer somthing like "one after the
+other" - and that is relativ positioning.
+
+> We have clearly different usage of terms "vector" and "sequence":
+> substantial part of today's software engineering (tools and books) use them
+> one way, while mathematics (and all natural sciences that use it heavily)
+> always use them another way.
+
+Even when it comes done to software engineering: IBM's Open Class Library has
+a Sequence - for relativ positioning getFirst, getNext, insertAfter. Usualy
+used to fill listboxes.
+
+> So all the argument here about Vector/Sequence here is about Ada's choice
+> of preference: will Ada choose software engineering (effectively, Java and
+> C++ libraries) side or mathematical/scientific side on this issue.
+
+I don't like the STL that much. So I am not realy defending "vector".
+
+> I suppose (or hope) that the thesis "Ada is for problem space, not for
+> solution space" implies the latter.
+
+I agree with you on that too.
+
+But I think we are off topic here.
+
+****************************************************************
+
+From: Marius Amado Alves
+Sent: Saturday, February 7, 2004 8:41 PM
+
+Randy Brukardt wrote:
+
+>The 'committee' primarily adopted the existing proposal submitted by Matt
+>Heaney. We decided not to change any of the major design decisions of that
+>proposal - because no package will suit everyone or every need, and we felt
+>it was more important to standardize something coherently designed for most
+>needs than to fiddle endlessly with it and risk introducing serious bugs.
+>
+>Which is to say, I don't know. :-)
+
+I do: there is none (except perhaps the implicit one: ease of
+implementation). On the other hand, there is a rationale for indefinite
+elements. This requirement has been largely felt and voiced since ever,
+and I included it in my Bases document (I think stored in alternative
+1), and even formulated it as an Annex (stored in alternative 2 but
+applicable to any alternative). But I've always seemed to feel some
+resistance from Matt and the ARG. Which resistance I find inexplicable.
+I really don't see how making the element type indefinite may
+"compromise coherence" or "introduce bugs". Sure it complicates the
+implementation. But the increase in power for the user is a quantum
+leap, as it frees him from doing tricky memory management in many
+situations. In my proposed Annex I included this passage from someone
+who should be dear to at least one person in that group--perhaps in the
+hope of making those strange walls of resistance just shiver a bit:
+
+<<If I ask a student whether her design is as good as Chartres, she often smiles tolerantly
+at me as if to say, "Of course not, that isnt't what I am trying to do.... I could never do
+that." Then, I express my disagreement, and tell her: "That standard *must* be our
+standard. If you are going to be a builder, no other standard is worthwhile.">>
+ -- Cristopher Alexander, Foreword to [Gabriel 1996]
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Saturday, February 7, 2004 9:20 PM
+
+> I do: there is none (except perhaps the implicit one: ease of
+> implementation). On the other hand, there is a rationale for indefinite
+> elements.
+
+Perhaps. But that wasn't the question. The question was why aren't there
+indefinite *keys*.
+
+...
+> But I've always seemed to feel some
+> resistance from Matt and the ARG.
+
+Given that the "ARG" (other than the subcommittee) has not yet looked at
+these proposals, that's a pretty bizarre statement.
+
+...
+> I really don't see how making the element type indefinite may
+> "compromise coherence" or "introduce bugs". Sure it complicates the
+> implementation.
+
+And, on most implementations, I would expect it to make it *many* times
+slower. (It wouldn't have any effect on Janus/Ada, I don't think, because we
+already have to allocate an element at a time anyway.) I would guess that it
+is that efficiency concern that Matt is responding to. But I'll let him
+respond himself...
+
+****************************************************************
+
+From: Marius Amado Alves
+Sent: Sunday, February 8, 2004 6:26 AM
+
+>... that wasn't the question. The question was why aren't there
+>indefinite *keys*.
+>
+Oops... sorry.
+
+Curiously enough if you have indefinite elements the requirement for
+indefinite keys looses strength: you can then use elementary containers
+or indefinite element positions as keys.
+
+>...
+>
+>>But I've always seemed to feel some
+>>resistance from Matt and the ARG.
+>
+>Given that the "ARG" (other than the subcommittee) has not yet looked at
+>these proposals, that's a pretty bizarre statement.
+
+Just a feeling. The proposals are there in the AI, and there was some
+discussion.
+
+>>I really don't see how making the element type indefinite may
+>>"compromise coherence" or "introduce bugs". Sure it complicates the
+>>implementation.
+>
+>And, on most implementations, I would expect it to make it *many* times
+>slower....
+
+No. The system should chose at compile time a specific body according to
+the 'Definite attribute of the actual element type.
+
+Aside. Of course there is still no standard means to do this, but it
+would be a nice extension. Conditional compilation of generic bodies
+based on instantiation properties. Variant units :-)
+ generic
+ type T is private;
+ ...
+ package G is
+ when T'Definite =>
+ ...;
+ when others =>
+ ...;
+ end;
+(On the subject of conditional compilation, see also the recent Ada
+Preprocessor thread on CLA.)
+In the meanwhile, there is no requirement that Ada.Containers be
+implemented strictly in Ada, is there? I doubt any Ada 95 container
+(arrays, files) is.
+End of aside.
+
+So no coherence problem, nor bugs, nor efficiency problem :-)
+
+****************************************************************
+
+[Editor's note: For continuing mail on this AI, see AI-00302-04.]
+
+****************************************************************
+
+Possible improvements from the original author (Matt Heaney), February 18, 2004
+
+o The vector container declares a subtype of its generic formal index type:
+
+ subtype Index_Subtype is Index_Type;
+
+This turns out to be very useful when you need to keep track of what is
+the range of the vector container index type. I had a real headache
+when writing an app when I switched from Positive to Natural, and it's
+because I didn't use an index subtype.
+
+We could generalize this for all the containers. For example the map
+container would look like this:
+
+ subtype Key_Subtype is Key_Type;
+ subtype Element_Subtype is Element_Type;
+
+This turns out to be useful when you need to instantiate the
+Generic_Element function, which you can do using just the subtypes:
+
+ type Element_Access is
+ access all XXX_Maps.Element_Subtype;
+
+ function To_Access is
+ new XXX_Maps.Generic_Element (Element_Access);
+
+
+o There is an open issue about what value Sorted_Sets.Find should return
+if Find fails to find the search item. It could either be Null_Cursor
+or it could be the value Back (Set). (The API now says that it's the
+value Null_Cursor.)
+
+The benefit of Null_Cursor is that detecting accidental deferences of
+the return value of a failed search is easy, since the internal access
+object is null. However, that breaks symmetry with searches over a
+sequence, which fall off the end onto Back when the search fails.
+
+If we were interested in trying to prevent any dereference of the Back
+sentinel node of a set, one possibility would be to give the sentinel
+node a special color (assuming that the set is implemented as a
+red-black tree, of course), and then test that in the dereference
+operations Element and Generic_Element.
+
+But this might be too paranoid, and there are probably many wrong ways
+to dereference a cursor that I can't even imagine. And an implementor
+might use some other data structure that makes the detection difficult
+or impossible.
+
+So we could just return Back and not worry about accidental
+dereferences. (I don't have any data to suggest that accidental
+deferences would even be a problem.) I'm beginning to think that I was
+being a too conservative when I said Find should return Null_Cursor
+instead of Back, and I'm concerned now about the inconsistency.
+
+
+o This also illustrates the fact that support for aggregate-style
+operations in the current spec is weak, mostly supporting manipulation
+of elements one-at-a-time.
+
+If we are interesting in a vector being a component for manipulation of
+unbounded arrays then there are operations in Ada.Strings.Unbounded that
+might be useful, such as Replace_Slice and Overwrite.
+
+One of the errors in Ada.Strings.Unbounded was that to insert an
+aggregate of elements (characters) into the string you have to insert an
+array type. But suppose you only have another Unbounded_String? We can
+generalize insert to allow insertion of a vector or a vector slice into
+another vector, like this:
+
+ procedure Insert (Vector : in out Vector_Type;
+ Before : in Index_Type'Base;
+ New_Item : in Vector_Type);
+
+ procedure Insert (Vector : in out Vector_Type;
+ Before : in Index_Type'Base;
+ New_Item : in Vector_Type;
+ First : in Index_Type'Base;
+ Last : in Index_Type'Base);
+
+That's just insertion. Slice assignment could be done using:
+
+ procedure Replace_Elements (Vector : in Vector_Type;
+ Low : in Index_Type'Base;
+ High : in Index_Type'Base;
+ By : in Element_Type);
+
+which provides the vector analog of
+
+ V (I .. J) := (others => E);
+
+We have also discussed assignment operations. A vector is non-limited
+so of course you can say:
+
+ V1 := V2;
+
+This replaces the target with the entire range of source. Another
+possibility is to assign to the target just a slice of the source:
+
+ V1 := V2 (I .. J);
+
+Both of these operations would look like this:
+
+ procedure Assign (Target : in out Vector_Type;
+ Source : in Vector_Type);
+
+ procedure Assign (Target : in out Vector_Type;
+ Source : in Vector_Type;
+ Low : in Index_Type'Base;
+ High : in Index_Type'Base);
+
+We could generalize further still. The operation
+
+ procedure Assign (Target : in out Vector_Type;
+ Source : in Element_Type;
+ Count : in Element_Count);
+
+is the vector analog of
+
+ subtype Array_Subtype is Array_Type (1 .. Count);
+
+ V1 := Array_Subtype'(others => Source);
+
+
+Assign operations might also be more efficient than constructor
+functions, since the target can be built in place, without any
+controlled finalization and adjustment.
+
+Assignment operations are probably more efficient but it might make
+sense to have constructor functions too:
+
+ function To_Vector (Length : Element_Count)
+ return Vector_Type;
+
+ function To_Vector (Source : Vector_Type;
+ Low : Index_Type'Base;
+ High : Index_Type'Base)
+ return Vector_Type;
+
+ function To_Vector (Source : Element_Type;
+ Count : Element_Count)
+ return Vector_Type;
+
+Another possibility is to provide concatenation operators, too.
+
+
+o The aggregate Delete operation looks like this:
+
+ procedure Delete (Vector : in out Vector_Type;
+ First : in Index_Type'Base;
+ Count : in Natural);
+
+But this also feels wrong, since it specifies the first index and a
+count. Count should probably be reserved for aggregate-style
+insertions. The analog in Ada.Strings.Unbounded is declared like this:
+
+ procedure Delete (Vector : in out Vector_Type;
+ From : in Index_Type'Base;
+ Through : in Index_Type'Base);
+
+This seems better since it specifies the range using a more traditional
+Ada closed-range style.
+
+
+o The Resize operation is the analog of the reserve() operation in the
+STL std::vector class. However, there is no real analog of the resize()
+operation in std::vector, a member function which expands the internal
+array as necessary, and sets the number of elements to the specified
+value.
+
+You can do this using other operations but its awkward. It might be
+better to provide an operation like:
+
+ procedure Set_Length
+ (Vector : in out Vector_Type;
+ Length : in Element_Count);
+
+which sets the length directly.
+
+Randy asked whether this would leave "holes" in the vector. But there
+are no real wholes, since it's just a contiguous array under the hood
+and so the normal initialization rules for array components apply.
+
+
+o There has been interest in passive iterators for the vector. We
+should probably include them. Here's what they look like:
+
+ generic
+ with procedure Process
+ (Element : in Element_Type) is <>;
+ procedure Generic_Constant_Iteration
+ (Vector : in Vector_Type);
+
+ generic
+ with procedure Process
+ (Element : in out Element_Type) is <>;
+ procedure Generic_Iteration
+ (Vector : in Vector_Type);
+
+ generic
+ with procedure Process
+ (Element : in Element_Type) is <>;
+ procedure Generic_Constant_Reverse_Iteration
+ (Vector : in Vector_Type);
+
+ generic
+ with procedure Process
+ (Element : in out Element_Type) is <>;
+ procedure Generic_Reverse_Iteration
+ (Vector : in Vector_Type);
+
+
+o I discussed aggregate-style operations for vectors above. Another
+possibility is to declare an array type, and provide operations that
+operation that have an array parameter. Something like:
+
+ type Vector_Elements is
+ array (Index_Type range <>) of aliased Element_Type;
+
+[Editor's note: This only works for definite elements, of course.]
+
+and then provide operations like:
+
+ function To_Vector (Source : Vector_Elements)
+ return Vector_Type;
+
+ function To_Array (Source : Vector_Type)
+ return Vector_Elements;
+
+ function Slice (Vector : Vector_Type;
+ Low : Index_Type'Base;
+ High : Index_Type'Base)
+ return Array_Type;
+
+ procedure Assign (Target : in out Vector_Type;
+ Source : in Array_Type);
+
+ procedure Copy (Source : in Vector_Type;
+ Target : out Array_Type;
+ Last : out Index_Type'Base);
+
+etc.
+
+Yet another possibility is to declare a nested generic that declares a
+generic formal array type, so the user can specify his own array type:
+
+ generic
+
+ type Array_Type is
+ array (Index_Type range <>) of Element_Type;
+
+ package Generic_Arrays is
+
+ function To_Vector (Source : Array_Type)
+ return Vector_Type;
+
+ function To_Array (Source : Vector_Type)
+ return Array_Type;
+ ...
+ end Generic_Arrays;
+
+
+o There is still some debate about the exact nature and purpose of the
+vector container. My model (and I think Bob Duff's model) is that a
+vector is implemented internally using an unconstrained array. A vector
+allows insertion at any position, but it is specifically optimized for
+insertion at the back end.
+
+One of the benefits of the STL std::vector is that you can do this:
+
+ vector<HANDLE> v;
+
+ v.push_back(h1);
+ v.push_back(h2);
+
+ const HANDLE* const ph = &v[0];
+ const DWORD n = v.size();
+
+ WaitForMultipleObjects(n, ph, INFINITE);
+
+In other words under the hood a vector is just a normal C-style array.
+You're allowed to take the address of a vector element and the language
+guarantees that the elements are in contiguous memory, as if they had
+been declared as elements of a plain array.
+
+The Ada vector container should follow the same model. It doesn't make
+any sense to try to improve (say) insertions in the middle of a vector,
+since there are other perfectly-good containers for that (like a list).
+
+
+o There was some discussion about providing a stable sort, too. We
+could even provide a partial sort.
+
+
+o There seems to be interest in being able to sort arrays, too. A
+generic operation for sorting an array would look like:
+
+generic
+
+ type Index_Type is (<>);
+
+ type Element_Type is private;
+
+ type Array_Type is array (Index_Type range <>) of Element_Type;
+
+ with function "<" (Left, Right : Element_Type)
+ return Boolean is <>;
+
+procedure Ada.Containers.Generic_Sort_Unconstrained_Array
+ (Source : in out Array_Type);
+
+pragma Pure (Ada.Containers.Generic_Sort_Unconstrained_Array);
+
+
+There would be an analogous operation for sorting a constrained array.
+You could generalize further still, and provide an operation for sorting
+any container having a cursor with the requisite properties (such as a
+difference operator, etc).
+
+
+o We could generalize the vector sort by allowing the user to pass in a
+Swap operation for vector elements. The generic operation could have a
+named default (that does swapping using normal assignment):
+
+ procedure Swap
+ (Vector : in Vector_Type;
+ I, J : in Index_Type'Base);
+
+ generic
+
+ with function "<" (Left, Right : Element_Type)
+ return Boolean is <>;
+
+ with procedure Swap
+ (Vector : in Vector_Type;
+ I, J : in Index_Type'Base) is Vectors.Swap;
+
+ procedure Generic_Sort (Vector : in Vector_Type);
+
+This would be useful for elements that are expensive to copy, say that
+are implemented as a controlled type that contains a value by
+reference. The swap for that element could then just swap the pointers,
+instead of finalizing and then adjusting controlled objects.
****************************************************************
Questions? Ask the ACAA Technical Agent