!standard A.4.9(8/2) 09-10-15 AI05-0001-1/09
!standard A.4.9(11/2)
!standard A.4.10(0)
!standard A.18(4/2)
!standard A.18.1(5/2)
!standard A.18.2(34/2)
!standard A.18.2(88/2)
!standard A.18.2(89/2)
!standard A.18.2(93/2)
!standard A.18.2(115/2)
!standard A.18.2(147/2)
!standard A.18.2(149/2)
!standard A.18.3(17/2)
!standard A.18.3(60/2)
!standard A.18.3(65/2)
!standard A.18.3(86/2)
!standard A.18.3(88/2)
!standard A.18.4(10/2)
!standard A.18.4(19/2)
!standard A.18.4(41/2)
!standard A.18.4(43/2)
!standard A.18.5(17/2)
!standard A.18.5(53/2)
!standard A.18.6(16/2)
!standard A.18.6(58/2)
!standard A.18.7(10/2)
!standard A.18.7(18/2)
!standard A.18.7(36/2)
!standard A.18.7(38/2)
!standard A.18.8(17/2)
!standard A.18.8(75/2)
!standard A.18.9(16/2)
!standard A.18.9(81/2)
!standard A.18.16(0)
!standard A.18.17(0)
!standard A.18.18(0)
!standard A.18.19(0)
!standard A.18.20(0)
!standard A.18.21(0)
!standard A.18.22(0)
!standard A.18.23(1/2)
!standard A.18.23(9/2)
!class Amendment 05-10-24
!status Amendment 201Z 09-06-26
!status ARG Approved 7-0-0 09-06-12
!status work item 06-03-15
!status received 05-10-02
!priority Medium
!difficulty Hard
!subject Bounded containers and other container issues
!summary
Bounded forms for all of the containers are added to Ada. We also add
generalized sorting and case-insensitive comparison and hashing operations.
!problem
The Ada 2005 containers were intended to provide the needs of most common uses
(often estimated as 80%). What about the other 20%?
In particular, better control over storage management is needed for high-integrity
and hard real-time systems.
!proposal
(See summary.)
!wording
A.4.9 String Hashing
Modify A.4.9(8/2):
[Strings.Bounded.Hash is equivalent to the function call]{Equivalent to}
Strings.Hash (Bounded.To_String (Key));
[Editor's note: This makes the style consistent with A.4.3(84), A.18.2(186/2),
and many other paragraphs. In any case, a function cannot be equivalent to a
call of a function, so the current wording is misleading.]
Modify A.4.9(11/2):
[Strings.Unbounded.Hash is equivalent to the function call]{Equivalent to}
Strings.Hash (To_String (Key));
Add the following declarations after A.4.9(11/2):
The library function Strings.Hash_Case_Insensitive has the following
declaration:
with Ada.Containers;
function Ada.Strings.Hash_Case_Insensitive
(Key : String) return Containers.Hash_Type;
pragma Pure (Hash_Case_Insensitive);
Returns an implementation-defined value which is a function of the value
of Key, converted to lower case. If A and B are strings such that
Strings.Equal_Case_Insensitive (A, B) (see A.4.10) is
True, then Hash_Case_Insensitive(A) equals Hash_Case_Insensitive(B).
The library function Strings.Fixed.Hash_Case_Insensitive has the
following declaration:
with Ada.Containers, Ada.Strings.Hash_Case_Insensitive;
function Ada.Strings.Fixed.Hash_Case_Insensitive (Key : String)
return Containers.Hash_Type renames Ada.Strings.Hash_Case_Insensitive;
pragma Pure(Hash_Case_Insensitive);
The generic library function Strings.Bounded.Hash_Case_Insensitive has
the following declaration:
with Ada.Containers;
generic
with package Bounded is
new Ada.Strings.Bounded.Generic_Bounded_Length (<>);
function Ada.Strings.Bounded.Hash_Case_Insensitive
(Key : Bounded.Bounded_String) return Containers.Hash_Type;
pragma Preelaborate(Hash_Case_Insensitive);
Equivalent to
Strings.Hash_Case_Insensitive (Bounded.To_String (Key));
The library function Strings.Unbounded.Hash_Case_Insensitive has the
following declaration:
with Ada.Containers;
function Ada.Strings.Unbounded.Hash_Case_Insensitive
(Key : Unbounded_String) return Containers.Hash_Type;
pragma Preelaborate(Hash_Case_Insensitive);
Equivalent to
Strings.Hash_Case_Insensitive (To_String (Key));
A.4.10 String Comparison (new)
Static Semantics
The library function Strings.Equal_Case_Insensitive has the following
declaration:
function Ada.Strings.Equal_Case_Insensitive
(Left, Right : String) return Boolean;
pragma Pure (Equal_Case_Insensitive);
Compares strings Left and Right, converted to lower case, for equality.
The library function Strings.Fixed.Equal_Case_Insensitive has the
following declaration:
with Ada.Containers, Ada.Strings.Equal_Case_Insensitive;
function Ada.Strings.Fixed.Equal_Case_Insensitive
(Left, Right : String) return Boolean
renames Ada.Strings.Equal_Case_Insensitive;
pragma Pure(Equal_Case_Insensitive);
The generic library function Strings.Bounded.Equal_Case_Insensitive has
the following declaration:
with Ada.Containers;
generic
with package Bounded is
new Ada.Strings.Bounded.Generic_Bounded_Length (<>);
function Ada.Strings.Bounded.Equal_Case_Insensitive
(Left, Right : Bounded.Bounded_String) return Boolean;
pragma Preelaborate(Equal_Case_Insensitive);
Equivalent to Strings.Equal_Case_Insensitive (Bounded.To_String (Key));
The library function Strings.Unbounded.Equal_Case_Insensitive has the
following declaration:
with Ada.Containers;
function Ada.Strings.Unbounded.Equal_Case_Insensitive
(Left, Right : Unbounded_String) return Boolean;
pragma Preelaborate(Equal_Case_Insensitive);
Equivalent to Strings.Equal_Case_Insensitive (To_String (Key));
The library function Strings.Less_Case_Insensitive has the following
declaration:
function Ada.Strings.Less_Case_Insensitive
(Left, Right : String) return Boolean;
pragma Pure (Less_Case_Insensitive);
Performs a lexicographic comparison of strings Left and Right, converted to
lower case.
The library function Strings.Fixed.Less_Case_Insensitive has the
following declaration:
with Ada.Containers, Ada.Strings.Less_Case_Insensitive;
function Ada.Strings.Fixed.Less_Case_Insensitive
(Left, Right : String) return Boolean
renames Ada.Strings.Less_Case_Insensitive;
pragma Pure(Less_Case_Insensitive);
The generic library function Strings.Bounded.Less_Case_Insensitive has
the following declaration:
with Ada.Containers;
generic
with package Bounded is
new Ada.Strings.Bounded.Generic_Bounded_Length (<>);
function Ada.Strings.Bounded.Less_Case_Insensitive
(Left, Right : Bounded.Bounded_String) return Boolean;
pragma Preelaborate(Less_Case_Insensitive);
Equivalent to Strings.Less_Case_Insensitive (Bounded.To_String (Key));
The library function Strings.Unbounded.Less_Case_Insensitive has the
following declaration:
with Ada.Containers;
function Ada.Strings.Unbounded.Less_Case_Insensitive
(Left, Right : Unbounded_String) return Boolean;
pragma Preelaborate(Less_Case_Insensitive);
Equivalent to Strings.Less_Case_Insensitive (To_String (Key));
A.18 Containers
Generalize A.18(4.1/3) [added by AI05-0044-1]
When a formal [operator "<"]{function} is used to provide an ordering for a
container, it is generally required to define a strict weak ordering. [An operator]{A
function} "<" defines a strict weak ordering if it is irreflexive, asymmetric,
transitive, and in addition, if x < y for any values x and y, then for all other values z,
(x < z) or (z < y).
A.18.1 Package Containers
Add the following after A.18.1(5/2):
Capacity_Error : exception;
A.18.2 Package Containers.Vectors
Add the following declarations after A.18.2(34/2):
procedure Assign (Target : in out Vector; Source : in Vector);
function Copy (Source : Vector; Capacity : Count_Type := 0)
return Vector;
Add the following after A.18.2(88/2):
Vector'Write writes the length of Vector elements to the stream.
Vector'Read reads the length of Vector elements from the stream.
AARM Implementation Note: We require streaming of containers to work
(see 13.13.2). In particular, we do not want all of the elements that
make up the capacity of the vector streamed, as those beyond the length
of the container have undefined contents. This will require a custom
stream attribute implementation; the language-defined default implementation
will not work (even for a bounded form, as that would most likely
stream the entire capacity of the vector).
Add the following after A.18.2(89/2):
If an operation attempts to modify the vector such that the position
of the last element would be greater than Index_Type'Last, then the
operation propagates Constraint_Error.
Add the following after A.18.2(93/2):
* it calls the Assign procedure with V as the Target parameter; or
Modify A.18.2(115/2):
{If the capacity of Container is already greater than or equal to
Capacity then Reserve_Capacity has no effect. Otherwise, }
Reserve_Capacity allocates [new internal data structures such]
{additional storage as necessary to ensure} that the length of the
resulting vector can become at least the value Capacity without
requiring an additional call to Reserve_Capacity, and is large enough
to hold the current length of Container. Reserve_Capacity then
[copies the] {, as necessary, moves} elements into the new [data
structures] {storage} and deallocates [the old data structures] {any
storage no longer needed}. Any exception raised during allocation is
propagated and Container is not modified.
Add the following after A.18.2(147/2):
procedure Assign (Target : in out Vector; Source : in Vector);
If Target denotes the same object as Source, the operation has no
effect. If the length of Source is greater than the capacity of Target,
Reserve_Capacity is called with the length of Source as the capacity.
Each element of Source is assigned to the corresponding element of Target.
function Copy (Source : Vector; Capacity : Count_Type := 0)
return Vector;
Returns a vector whose elements are initialized from the corresponding
elements of Source. If Capacity is 0, then the vector capacity is the
length of Source; if Capacity is equal to or greater than
the length of Source, the vector capacity is at least the specified value.
Otherwise, the operation propagates Capacity_Error.
A.18.2(149/2) is replaced by the following:
If Target denotes the same object as Source, then Move has no
effect. Otherwise, Move first calls Reserve_Capacity (Target, Length (Source))
and then Clear (Target); then, each element from Source
is removed from Source and inserted into Target in the original
order. The length of Source is 0 after a successful call to Move.
A.18.3 Package Containers.Doubly_Linked_Lists
Add the following declarations after A.18.3(17/2):
procedure Assign (Target : in out List; Source : in List);
function Copy (Source : List) return List;
Add the following after A.18.3(60/2):
List'Write writes the length of List elements to the stream.
List'Read reads the length of List elements from the stream.
Add the following after A.18.3(65/2):
* it calls the Assign procedure with L as the Target parameter; or
Add the following after A.18.3(86/2):
procedure Assign (Target : in out List; Source : in List);
If Target denotes the same object as Source, the operation has no
effect. Otherwise, it clears Target, and each element of Source is
assigned to the corresponding element of Target.
function Copy (Source : List) return List;
Returns a list whose elements match the elements of Source.
The description of Move in A.18.3(88/2) is replaced with:
If Target denotes the same object as Source, then Move has no effect. Otherwise,
equivalent to Assign (Target, Source) followed by Clear (Source).
A.18.4 Maps
Add the following after A.18.4(10/2):
* it calls the Assign procedure with M as the Target parameter; or
Add the following after A.18.4(19/2):
Map'Write writes the length of Map elements to the stream.
Map'Read reads the length of Map elements from the stream.
Add the following after A.18.4(41/2):
procedure Assign (Target : in out Map; Source : in Map);
If Target denotes the same object as Source, the operation has no
effect. Otherwise, each key/element pair of Source is assigned to
the corresponding key/element pair of Target.
The description of Move in A.18.4(43/2) is replaced with:
If Target denotes the same object as Source, then Move has no effect. Otherwise,
equivalent to Assign (Target, Source) followed by Clear (Source).
A.18.5 Containers.Hashed_Maps
Add the following declarations after A.18.5(17/2):
procedure Assign (Target : in out Map; Source : in Map);
function Copy (Source : Map; Capacity : Count_Type := 0) return Map;
Add the following after A.18.5(53/2):
procedure Assign (Target : in out Map; Source : in Map);
In addition to the semantics described in A.18.4, if the length of Source is
greater than the capacity of Target, Reserve_Capacity is called with the
length of Source as the capacity before assigning any elements.
function Copy (Source : Map; Capacity : Count_Type := 0) return Map;
Returns a map whose keys and elements are initialized from the keys
and elements of Source. If Capacity is 0, then the map capacity is the
length of Source; if Capacity is equal to or greater than
the length of Source, the map capacity is at least the specified value.
Otherwise, the operation propagates Capacity_Error.
A.18.6 Containers.Ordered_Maps
Add the following declarations after A.18.6(16/2):
procedure Assign (Target : in out Map; Source : in Map);
function Copy (Source : Map) return Map;
Add the following after A.18.6(58/2):
function Copy (Source : Map) return Map;
Returns a map whose keys and elements are initialized from the
corresponding keys and elements of Source.
A.18.7 Sets
Add the following after A.18.7(10/2):
* it calls the Assign procedure with S as the Target parameter; or
Add the following after A.18.7(18/2):
Set'Write writes the length of Set elements to the stream.
Set'Read reads the length of Set elements from the stream.
Add after A.18.7(36/2):
procedure Assign (Target : in out Set; Source : in Set);
If Target denotes the same object as Source, the operation has no
effect. Otherwise, each element of Source is assigned to the
corresponding element of Target.
The description of Move in A.18.7(38/2) is replaced with:
If Target denotes the same object as Source, then Move has no effect. Otherwise,
equivalent to Assign (Target, Source) followed by Clear (Source).
A.18.8 Containers.Hashed_Sets
Add the following declarations after A.18.8(17/2):
procedure Assign (Target : in out Set; Source : in Set);
function Copy (Source : Set; Capacity : Count_Type := 0) return Set;
Add the following after A.18.8(75/2):
procedure Assign (Target : in out Set; Source : in Set);
In addition to the semantics described in A.18.7, if the length of Source is
greater than the capacity of Target, Reserve_Capacity is called with the length
of Source as the capacity before assigning any elements.
function Copy (Source : Set; Capacity : Count_Type := 0) return Set;
Returns a set whose elements are initialized from the elements of
Source. If Capacity is 0, then the set capacity is the
length of Source; if Capacity is equal to or greater than
the length of Source, the set capacity is at least the specified value.
Otherwise, the operation propagates Capacity_Error.
A.18.9 Containers.Ordered_Sets
Add the following declarations after A.18.9(16/2):
procedure Assign (Target : in out Set; Source : in Set);
function Copy (Source : Set) return Set;
Add the following after A.18.9(81/2):
function Copy (Source : Set) return Set;
Returns a set whose elements are initialized from the corresponding
elements of Source.
A.18.16 Containers.Indefinite_Holders (see AI05-0069-1)
Add the following declarations after A.18.16(15/3): [Before Move]
procedure Assign (Target : in out Holder; Source : in Holder);
function Copy (Source : Holder) return Holder;
Add the following after A.18.16(44/3):
procedure Assign (Target : in out Holder; Source : in Holder);
If Target denotes the same object as Source, the operation has no
effect. If Source is empty, Clear (Target) is called. Otherwise,
Replace_Element (Target, Element (Source)) is called.
function Copy (Source : Holder) return Holder;
If Source is empty, returns an empty holder; otherwise, returns
To_Holder (Element (Source)).
A.18.17 The Package Containers.Bounded_Vectors (new)
The language-defined generic package Containers.Bounded_Vectors
provides a private type Vector and a set of operations. It provides
the same operations as the package Containers.Vectors (see A.18.2),
with the difference that the maximum storage is bounded.
Static Semantics
The declaration of the generic library package
Containers.Bounded_Vectors has the same contents and semantics as
Containers.Vectors except:
* The pragma Preelaborate is replaced with pragma Pure.
AARM implementation note: Package Containers.Bounded_Vectors
cannot depend on package Ada.Finalization (because that package
has Preelaborate categorization).
* The type Vector is declared with a discriminant that specifies
the capacity:
type Vector (Capacity : Count_Type) is tagged private;
* The type Vector needs finalization if and only if type
Element_Type needs finalization.
* In function Copy, if the Capacity parameter is equal to or
greater than the length of Source, the vector capacity exactly equals
the value of the Capacity parameter.
* The description of Reserve_Capacity is replaced with:
If the specified Capacity is larger than the capacity of Container,
then Reserve_Capacity propagates Capacity_Error. Otherwise, the
operation has no effect.
Implementation Advice
Bounded vector objects should be implemented without implicit pointers or
dynamic allocation.
The implementation advice for procedure Move to minimize copying does not
apply.
A.18.18 Package Containers.Bounded_Doubly_Linked_Lists (new)
The language-defined generic package
Containers.Bounded_Doubly_Linked_Lists provides a private type List
and a set of operations. It provides the same operations as the
package Containers.Doubly_Linked_Lists (see A.18.3), with the
difference that the maximum storage is bounded.
Static Semantics
The declaration of the generic library package
Containers.Bounded_Doubly_Linked_Lists has the same contents and
semantics as Containers.Doubly_Linked_Lists except:
* The pragma Preelaborate is replaced with pragma Pure.
AARM implementation note: Package
Containers.Bounded_Doubly_Linked_Lists cannot depend on
package Ada.Finalization (because that package has Preelaborate
categorization).
* The type List is declared with a discriminant that specifies the
capacity (maximum number of elements) as follows:
type List (Capacity : Count_Type) is tagged private;
* The type List needs finalization if and only if type
Element_Type needs finalization.
* The allocation of internal storage includes a check that the
capacity is not exceeded, and Capacity_Error is raised if this
check fails.
* In procedure Assign, if Source length is greater than Target
capacity, then Capacity_Error is propagated.
* The function Copy is replaced with:
function Copy (Source : List; Capacity : Count_Type := 0)
return List;
If Capacity is 0, then the list capacity is the length of
Source; if Capacity is equal to or greater than the length of
Source, the list capacity equals the value of the Capacity parameter;
otherwise, the operation propagates Capacity_Error.
* In the three-parameter procedure Splice whose Source has type List,
if the sum of the length of Target and the length of Source is greater
than the capacity of Target, then Splice propagates Capacity_Error.
[Editor's note: This is referring to A.18.3(112/2), but of
course we can't say that.]
* In the four-parameter procedure Splice, if the length of Target
equals the capacity of Target, then Splice propagates Capacity_Error.
[Editor's note: This is referring to A.18.3(114/2).]
Implementation Advice
Bounded list objects should be implemented without implicit pointers or
dynamic allocation.
The implementation advice for procedure Move to minimize copying does not
apply.
A.18.19 Package Containers.Bounded_Hashed_Maps (new)
The language-defined generic package Containers.Bounded_Hashed_Maps
provides a private type Map and a set of operations. It provides the
same operations as the package Containers.Hashed_Maps (see A.18.5),
with the difference that the maximum storage is bounded.
Static Semantics
The declaration of the generic library package
Containers.Bounded_Hashed_Maps has the same contents and semantics as
Containers.Hashed_Maps except:
* The pragma Preelaborate is replaced with pragma Pure.
AARM implementation note: Package Containers.Bounded_Hashed_Maps
cannot depend on package Ada.Finalization (because that package
has Preelaborate categorization).
* The type Map is declared with discriminants that specify both
the capacity (number of elements) and modulus (number of
distinct hash values) of the hash table as follows:
type Map (Capacity : Count_Type;
Modulus : Hash_Type) is tagged private;
* The type Map needs finalization if and only if type
Key_Type or type Element_Type needs finalization.
* The description of Reserve_Capacity is replaced with:
If the specified Capacity is larger than the capacity of Container,
then Reserve_Capacity propagates Capacity_Error. Otherwise, the
operation has no effect.
* An additional operation is added immediately following Reserve_Capacity:
function Default_Modulus (Capacity : Count_Type) return Hash_Type;
Default_Modulus returns an implementation-defined value for the number
of distinct hash values to be used for the given capacity (maximum
number of elements).
* The function Copy is replaced with:
function Copy (Source : Map;
Capacity : Count_Type := 0;
Modulus : Hash_Type := 0) return Map;
Returns a map with key/element pairs initialized from the values
in Source. If Capacity is 0, then the map capacity is the
length of Source; if Capacity is equal to or greater than
the length of Source, the map capacity is the value of the Capacity
parameter; otherwise, the operation propagates Capacity_Error. If
the Modulus argument is 0, then the map modulus is the value
returned by a call to Default_Modulus with the map capacity as
its argument; otherwise the map modulus is the value of the
Modulus parameter.
Implementation Advice
Bounded map objects should be implemented without implicit pointers or
dynamic allocation.
The implementation advice for procedure Move to minimize copying does not
apply.
A.18.20 Package Containers.Bounded_Ordered_Maps (new)
The language-defined generic package Containers.Bounded_Ordered_Maps
provides a private type Map and a set of operations. It provides the
same operations as the package Containers.Ordered_Maps (see A.18.6),
with the difference that the maximum storage is bounded.
Static Semantics
The declaration of the generic library package
Containers.Bounded_Ordered_Maps has the same contents and semantics as
Containers.Ordered_Maps except:
* The pragma Preelaborate is replaced with pragma Pure.
AARM implementation note: Package Containers.Bounded_Ordered_Maps
cannot depend on package Ada.Finalization (because that package
has Preelaborate categorization).
* The type Map is declared with a discriminant that specifies the
capacity (maximum number of elements) as follows:
type Map (Capacity : Count_Type) is tagged private;
* The type Map needs finalization if and only if type
Key_Type or type Element_Type needs finalization.
* The allocation of a new node includes a check that the
capacity is not exceeded, and Capacity_Error is raised if this
check fails.
* In procedure Assign, if Source length is greater than Target
capacity, then Capacity_Error is propagated.
* The function Copy is replaced with:
function Copy (Source : Map;
Capacity : Count_Type := 0) return Map;
Returns a map with key/element pairs initialized from the values
in Source. If Capacity is 0, then the map capacity is the
length of Source; if Capacity is equal to or greater than
the length of Source, the map capacity is the specified value;
otherwise, the operation propagates Capacity_Error.
Implementation Advice
Bounded map objects should be implemented without implicit pointers or
dynamic allocation.
The implementation advice for procedure Move to minimize copying does not
apply.
A.18.21 Package Containers.Bounded_Hashed_Sets (new)
The language-defined generic package Containers.Bounded_Hashed_Sets
provides a private type Set and a set of operations. It provides the
same operations as the package Containers.Hashed_Sets (see A.18.8),
with the difference that the maximum storage is bounded.
Static Semantics
The declaration of the generic library package
Containers.Bounded_Hashed_Sets has the same contents and semantics as
Containers.Hashed_Sets except:
* The pragma Preelaborate is replaced with pragma Pure.
AARM implementation note: Package Containers.Bounded_Hashed_Sets
cannot depend on package Ada.Finalization (because that package
has Preelaborate categorization).
* The type Set is declared with discriminants that specify both
the capacity (number of elements) and modulus (number of
distinct hash values) of the hash table as follows:
type Set (Capacity : Count_Type;
Modulus : Hash_Type) is tagged private;
* The type Set needs finalization if and only if type
Element_Type needs finalization.
* The description of Reserve_Capacity is replaced with:
If the specified Capacity is larger than the capacity of Container,
then Reserve_Capacity propagates Capacity_Error. Otherwise, the
operation has no effect.
* An additional operation is added immediately following Reserve_Capacity:
function Default_Modulus (Capacity : Count_Type) return Hash_Type;
Default_Modulus returns an implementation-defined value for the number
of distinct hash values to be used for the given capacity (maximum
number of elements).
* The function Copy is replaced with:
function Copy (Source : Set;
Capacity : Count_Type := 0;
Modulus : Hash_Type := 0) return Set;
Returns a set whose elements are initialized from the values in
Source. If Capacity is 0, then the set capacity is the length
of Source; if Capacity is equal to or greater than the length
of Source, the set capacity is the value of the Capacity
parameter; otherwise, the operation propagates Capacity_Error. If
the Modulus argument is 0, then the set modulus is the value
returned by a call to Default_Modulus with the set capacity as
its argument; otherwise the set modulus is the value of the
Modulus parameter.
Implementation Advice
Bounded set objects should be implemented without implicit pointers or
dynamic allocation.
The implementation advice for procedure Move to minimize copying does not
apply.
A.18.22 Containers.Bounded_Ordered_Sets (new)
The language-defined generic package Containers.Bounded_Ordered_Sets
provides a private type Set and a set of operations. It provides the
same operations as the package Containers.Ordered_Sets (see A.18.9),
with the difference that the maximum storage is bounded.
Static Semantics
The declaration of the generic library package
Containers.Bounded_Ordered_Sets has the same contents and semantics as
Containers.Ordered_Sets except:
* The pragma Preelaborate is replaced with pragma Pure
AARM implementation note: package Containers.Bounded_Ordered_Sets
cannot depend on package Ada.Finalization (because that package
has Preelaborate categorization).
* The type Set is declared with a discriminant that specifies the
capacity (maximum number of elements) as follows:
type Set (Capacity : Count_Type) is tagged private;
* The type Set needs finalization if and only if type
Element_Type needs finalization.
* If Insert (or Include) adds an element, a check is made that the
capacity is not exceeded, and Capacity_Error is raised if this
check fails.
* In procedure Assign, if Source length is greater than Target
capacity, then Capacity_Error is propagated.
* The function Copy is replaced with:
function Copy (Source : Set;
Capacity : Count_Type := 0) return Set;
Returns a set whose elements are initialized from the values in
Source. If Capacity is 0, then the set capacity is the length
of Source; if Capacity is equal to or greater than
the length of Source, the set capacity is the specified value;
otherwise, the operation propagates Capacity_Error.
Implementation Advice
Bounded set objects should be implemented without implicit pointers or
dynamic allocation.
The implementation advice for procedure Move to minimize copying does not
apply.
A.18.23 Array Sorting
[Note: This was A.18.16 in Ada 2005; we're moving it.]
A.18.23 (1/2) is replaced by the following:
The language-defined generic procedures Containers.Generic_Array_Sort,
Containers.Generic_Constrained_Array_Sort, and Containers.Generic_Sort
provide sorting on arbitrary array types.
Add the following after A.18.23 (9/2):
The generic library procedure Containers.Generic_Sort has the following declaration:
generic
type Index_Type is (<>);
with function Before (Left, Right : Index_Type) return Boolean;
with procedure Swap (Left, Right : Index_Type);
procedure Ada.Containers.Generic_Sort (First, Last : Index_Type'Base);
pragma Pure (Ada.Containers.Generic_Sort);
Reorders the elements of an indexable structure, over the range First
.. Last, such that the elements are sorted in the ordering determined by
the generic formal function Before. The generic formal Before compares
the elements having the given indices, and the generic formal Swap
exchanges the values of the indicated elements. Any exception raised
during evaluation of Before or Swap is propagated.
The actual function for the generic formal function Before of
Generic_Sort is expected to return the same value each time it is
called with index values that identify a particular pair of element values.
It should define a strict weak ordering relationship (see A.18); it should
not modify the elements. The actual function for the generic formal Swap
should exchange the values of the indicated elements. If the actual for
either Before or Swap behaves in some other manner, the behavior of
Generic_Sort is unspecified. How many times the Generic_Sort calls Before
or Swap is unspecified.
!discussion
The forms added were decided at the September subcommittee meeting in New York;
see the minutes of that meeting for details (it is found in the !appendix
section of this AI).
See also AI05-0069-1 (Indefinite_Holder), AI05-0136-1 (Multiway_Trees), and
AI05-0159-1 (Queues).
---
Bounded forms
The bounded forms are intended to bring determinism to the storage requirements
of the various container forms. To this end, each bounded form includes
Implementation Advice that no dynamic allocation or pointers are used to implement
them. Thus, the bounded forms should be usable even in high-integrity contexts
where dynamic allocation is forbidden.
An alternative considered was to allow specifying the storage pool that the
containers used. However, that does not work as well as the simpler bounded forms:
* allocators still would be used, which would violate the rules of some
high-integrity systems;
* the memory use by the allocators used by each container would have to be
defined, potentially preventing innovative implementations of the containers;
* the storage pool would most likely have to be customized for each container
usage in order to have the effect of "no dynamic allocation".
The usage would thus be quite complicated and quite possibly not portable. The
bounded forms are easier to understand and are obviously portable.
The Assign and Copy subprograms are needed for the bounded forms in order that
containers with different capacities can be assigned or copied. The built-in assignment
would raise Constraint_Error if the capacities were different. In order to keep the
unbounded and bounded forms as similar as possible (to allow almost painless
switching between forms), these subprograms were added to all of the existing
containers.
---
Case insensitive functions
We added case insensitive subprograms as the most common real-world uses of strings
are case insensitive. That means that most of the uses of containers with strings for
keys are also case insensitive. It makes sense to provide the operations needed for
75% of string keys in a convinient form. The provided hashing and comparison operations
can directly be used in instances of the Map and Set containers. While it isn't hard
to write the needed operations, it's silly to make everyone write those operations
repeatedly.
Note that there are no Wide and Wide_Wide versions of these functions. Having them
would require defining case equivalence rules for the entire Unicode character set,
something we have not done so far. Case equivalence is not a 1-to-1 mapping for
Unicode. For example, German ß is one character, the upper case is two characters
"SS". Unicode documents say that it is possible to have 1 to 3 and 3 to 1
conversions! Note that the wide character mappings are specifically defined be
identity functions for non-Latin-1 characters (A.4.7(46.1/2)).
!example
!corrigendum A.4.9(8/2)
@drepl
@xindent
@dby
@xindent
!corrigendum A.4.9(11/2)
@drepl
@xindent
@dby
@xindent
The library function Strings.Hash_Case_Insensitive has the following
declaration:
@xcode<@b Ada.Containers;
@b Ada.Strings.Hash_Case_Insensitive (Key : String)
@b Containers.Hash_Type;
@b Pure(Hash_Case_Insensitive);>
@xindent
The library function Strings.Fixed.Hash_Case_Insensitive has the
following declaration:
@xcode<@b Ada.Containers, Ada.Strings.Hash_Case_Insensitive;
@b Ada.Strings.Fixed.Hash_Case_Insensitive (Key : String)
@b Containers.Hash_Type @b Ada.Strings.Hash_Case_Insensitive;
@b Pure(Hash_Case_Insensitive);>
The generic library function Strings.Bounded.Hash_Case_Insensitive has
the following declaration:
@xcode
@b Bounded @b
@b Ada.Strings.Bounded.Generic_Bounded_Length (<@>);
@b Ada.Strings.Bounded.Hash_Case_Insensitive
(Key : Bounded.Bounded_String) @b Containers.Hash_Type;
@b Preelaborate(Hash_Case_Insensitive);>
@xindent
The library function Strings.Unbounded.Hash_Case_Insensitive has the
following declaration:
@xcode<@b Ada.Containers;
@b Ada.Strings.Unbounded.Hash_Case_Insensitive
(Key : Unbounded_String) @b Containers.Hash_Type;
@b Preelaborate(Hash_Case_Insensitive);>
@xindent
!corrigendum A.4.10(0)
@dinsc
@s8<@i>
The library function Strings.Equal_Case_Insensitive has the following
declaration:
@xcode<@b Ada.Strings.Equal_Case_Insensitive (Left, Right : String)
@b Boolean;
@b Pure(Equal_Case_Insensitive);>
@xindent
The library function Strings.Fixed.Equal_Case_Insensitive has the
following declaration:
@xcode<@b Ada.Containers, Ada.Strings.Equal_Case_Insensitive;
@b Ada.Strings.Fixed.Equal_Case_Insensitive
(Left, Right : String) @b Boolean
@b Ada.Strings.Equal_Case_Insensitive;
@b Pure(Equal_Case_Insensitive);>
The generic library function Strings.Bounded.Equal_Case_Insensitive has
the following declaration:
@xcode<@b Ada.Containers;
@b
@b Bounded @b
@b Ada.Strings.Bounded.Generic_Bounded_Length (<@>);
@b Ada.Strings.Bounded.Equal_Case_Insensitive
(Left, Right : Bounded.Bounded_String) @b Boolean;
@b Preelaborate(Equal_Case_Insensitive);>
@xindent
The library function Strings.Unbounded.Equal_Case_Insensitive has the
following declaration:
@xcode<@b Ada.Containers;
@b Ada.Strings.Unbounded.Equal_Case_Insensitive
(Left, Right : Unbounded_String) @b Boolean;
@b Preelaborate(Equal_Case_Insensitive);>
@xindent
The library function Strings.Less_Case_Insensitive has the following
declaration:
@xcode<@b Ada.Strings.Less_Case_Insensitive (Left, Right : String)
@b Boolean;
@b Pure(Less_Case_Insensitive);>
@xindent
The library function Strings.Fixed.Less_Case_Insensitive has the
following declaration:
@xcode<@b Ada.Containers, Ada.Strings.Less_Case_Insensitive;
@b Ada.Strings.Fixed.Less_Case_Insensitive
(Left, Right : String) @b Boolean
@b Ada.Strings.Less_Case_Insensitive;
@b Pure(Less_Case_Insensitive);>
The generic library function Strings.Bounded.Less_Case_Insensitive has
the following declaration:
@xcode<@b Ada.Containers;
@b
@b Bounded @b
@b Ada.Strings.Bounded.Generic_Bounded_Length (<@>);
@b Ada.Strings.Bounded.Less_Case_Insensitive
(Left, Right : Bounded.Bounded_String) @b Boolean;
@b Preelaborate(Less_Case_Insensitive);>
@xindent
The library function Strings.Unbounded.Less_Case_Insensitive has the
following declaration:
@xcode<@b Ada.Containers;
@b Ada.Strings.Unbounded.Less_Case_Insensitive
(Left, Right : Unbounded_String) @b Boolean;
@b Preelaborate(Less_Case_Insensitive);>
@xindent
!corrigendum A.18(4/2)
@dinsa
If the advice suggests that the complexity should be less than @i(f(N)),
then for any arbitrarily small positive real D, there should exist a positive
integer M such that for all N > M, t(N)/f(N) < D.
@dinst
When a formal function is used to provide an ordering for a container,
it is generally required to define a strict weak ordering. A function "<"
defines a @i if it is irreflexive,
asymmetric, transitive, and in addition, if @i < @i for
any values @i and @i, then for all other values @i,
(@i < @i) or (@i < @i).
!corrigendum A.18.1(5/2)
@dinsa
@xcode< @b Count_Type @b 0 .. @ft<@i>;>
@dinst
@xcode< Capacity_Error : @b;>
!corrigendum A.18.2(34/2)
@dinsa
@xcode< @b Update_Element
(Container : @b Vector;
Position : @b Cursor;
Process : @b
(Element : @b Element_Type));>
@dinss
@xcode< @b Assign (Target : @b Vector; Source : @b Vector);>
@xcode< @b Copy (Source : Vector; Capacity : Count_Type := 0)
@b Vector;>
!corrigendum A.18.2(88/2)
@dinsa
Execution of the default implementation of the Input, Output, Read, or Write attribute
of type Cursor raises Program_Error.
@dinst
Vector'Write writes the length of Vector elements to the stream.
Vector'Read reads the length of Vector elements from the stream.
!corrigendum A.18.2(89/2)
@dinsa
No_Index represents a position that does not correspond to any element. The subtype
Extended_Index includes the indices covered by Index_Type plus the value No_Index and,
if it exists, the successor to the Index_Type'Last.
@dinst
If an operation attempts to modify the vector such that the position
of the last element would be greater than Index_Type'Last, then the
operation propagates Constraint_Error.
!corrigendum A.18.2(93/2)
@dinsa
@xbullet; or>
@dinst
@xbullet as the Target parameter; or>
!corrigendum A.18.2(115/2)
@drepl
Reserve_Capacity allocates new internal data structures such that the length of the
resulting vector can become at least the value Capacity without requiring an additional
call to Reserve_Capacity, and is large enough to hold the current length of Container.
Reserve_Capacity then copies the elements into the new data structures and deallocates
the old data structures. Any exception raised during allocation is propagated and
Container is not modified.
@dby
If the capacity of Container is already greater than or equal to
Capacity then Reserve_Capacity has no effect. Otherwise,
Reserve_Capacity allocates additional storage as necessary to ensure that the
length of the resulting vector can become at least the value Capacity without
requiring an additional call to Reserve_Capacity, and is large enough
to hold the current length of Container. Reserve_Capacity then, as necessary,
moves elements into the new storage and deallocates any storage no longer needed.
Any exception raised during allocation is propagated and Container is not modified.
!corrigendum A.18.2(147/2)
@dinsa
@xindent
@dinss
@xcode<@b Assign (Target : @b Vector; Source : @b Vector);>
@xindent
@xcode<@b Copy (Source : Vector; Capacity : Count_Type := 0)
@b Vector;>
@xindent
!corrigendum A.18.2(149/2)
@drepl
If Target denotes the same object as Source, then Move has no effect. Otherwise,
Move first calls Clear (Target); then, each element from Source is removed from
Source and inserted into Target in the original order. The length of Source
is 0 after a successful call to Move.
@dby
If Target denotes the same object as Source, then Move has no
effect. Otherwise, Move first calls Reserve_Capacity (Target, Length (Source))
and then Clear (Target); then, each element from Source
is removed from Source and inserted into Target in the original
order. The length of Source is 0 after a successful call to Move.
!corrigendum A.18.3(17/2)
@dinsa
@xcode< @b Update_Element
(Container : @b List;
Position : @b Cursor;
Process : @b
(Element : @b Element_Type));>
@dinss
@xcode< @b Assign (Target : @b List; Source : @b List);>
@xcode< @b Copy (Source : List) @b List;>
!corrigendum A.18.3(60/2)
@dinsa
Execution of the default implementation of the Input, Output, Read, or Write attribute of
type Cursor raises Program_Error.
@dinst
List'Write writes the length of List elements to the stream.
List'Read reads the length of List elements from the stream.
!corrigendum A.18.3(65/2)
@dinsa
@xbullet; or>
@dinst
@xbullet as the Target parameter; or>
!corrigendum A.18.3(86/2)
@dinsa
@xindent shall be unconstrained.>
@dinss
@xcode<@b Assign (Target : @b List; Source : @b List);>
@xindent
@xcode<@b Copy (Source : List) @b List;>
@xindent
!corrigendum A.18.3(88/2)
@drepl
@xindent
@dby
@xindent
!corrigendum A.18.4(10/2)
@dinsa
@xbullet; or>
@dinst
@xbullet as the Target parameter; or>
!corrigendum A.18.4(19/2)
@dinsa
Execution of the default implementation of the Input, Output, Read, or Write
attribute of type Cursor raises Program_Error.
@dinst
Map'Write writes the length of Map elements to the stream.
Map'Read reads the length of Map elements from the stream.
!corrigendum A.18.4(41/2)
@dinsa
@xindent shall be unconstrained.>
@dinst
@xcode<@b Assign (Target : @b Map; Source : @b Map);>
@xindent
!corrigendum A.18.4(43/2)
@drepl
@xindent
@dby
@xindent
!corrigendum A.18.5(17/2)
@dinsa
@xcode< @b Update_Element
(Container : @b Map;
Position : @b Cursor;
Process : @b
(Key : @b Key_Type;
Element : @b Element_Type));>
@dinss
@xcode< @b Assign (Target : @b Map; Source : @b Map);>
@xcode< @b Copy (Source : Map; Capacity : Count_Type := 0) @b Map;>
!corrigendum A.18.5(53/2)
@dinsa
In addition to the semantics described in A.18.4, Clear does not affect the capacity
of Container.
@dinst
@xcode<@b Assign (Target : @b Map; Source : @b Map);>
@xindent
@xcode<@b Copy (Source : Map; Capacity : Count_Type := 0) @b Map;>
@xindent
!corrigendum A.18.6(16/2)
@dinsa
@xcode< @b Update_Element
(Container : @b Map;
Position : @b Cursor;
Process : @b
(Key : @b Key_Type;
Element : @b Element_Type));>
@dinss
@xcode< @b Assign (Target : @b Map; Source : @b Map);>
@xcode< @b Copy (Source : Map) @b Map;>
!corrigendum A.18.6(58/2)
@dinsa
The first node of a nonempty map is the one whose key is less than the key of
all the other nodes in the map. The last node of a nonempty map is the one
whose key is greater than the key of all the other elements in the map. The
successor of a node is the node with the smallest key that is larger than the
key of the given node. The predecessor of a node is the node with the largest
key that is smaller than the key of the given node. All comparisons are done
using the generic formal "<" operator for keys.
@dinss
@xcode<@b Copy (Source : Map) @b Map;>
@xindent
!corrigendum A.18.7(10/2)
@dinsa
@xbullet; or>
@dinst
@xbullet as the Target parameter; or>
!corrigendum A.18.7(18/2)
@dinsa
Execution of the default implementation of the Input, Output, Read, or Write
attribute of type Cursor raises Program_Error.
@dinst
Set'Write writes the length of Set elements to the stream.
Set'Read reads the length of Set elements from the stream.
!corrigendum A.18.7(36/2)
@dinsa
@xindent with the element designated by
Position as the argument. Program_Error is propagated if Process.@b
tampers with the elements of Container. Any exception raised by
Process.@b is propagated.>
@dinss
@xcode<@b Assign (Target : @b Set; Source : @b Set);>
@xindent
!corrigendum A.18.7(38/2)
@drepl
@xindent
@dby
@xindent
!corrigendum A.18.8(17/2)
@dinsa
@xcode< @b Query_Element
(Position : @b Cursor;
Process : @b (Element : @b Element_Type));>
@dinss
@xcode< @b Assign (Target : @b Set; Source : @b Set);>
@xcode< @b Copy (Source : Set; Capacity : Count_Type := 0) @b Set;>
!corrigendum A.18.8(75/2)
@dinsa
In addition to the semantics described in A.18.7, Clear does not affect the capacity
of Container.
@dinst
@xcode<@b Assign (Target : @b Set; Source : @b Set);>
@xindent
@xcode<@b Copy (Source : Set; Capacity : Count_Type := 0) @b Set;>
@xindent
!corrigendum A.18.9(16/2)
@dinsa
@xcode< @b Query_Element
(Position : @b Cursor;
Process : @b (Element : @b Element_Type));>
@dinss
@xcode< @b Assign (Target : @b Set; Source : @b Set);>
@xcode< @b Copy (Source : Set) @b Set;>
!corrigendum A.18.9(81/2)
@dinsa
The first element of a nonempty set is the one which is less than all the other elements in the
set. The last element of a nonempty set is the one which is greater than all the other elements
in the set. The successor of an element is the smallest element that is larger than the given
element. The predecessor of an element is the largest element that is smaller than the given
element. All comparisons are done using the generic formal "<" operator for elements.
@dinss
@xcode<@b Copy (Source : Set) @b Set;>
@xindent
!corrigendum A.18.16
!comment This is intended to force a conflict. The fully formatted text is in the conflict file.
@dinsc
The language-defined generic package Containers.Indefinite_Holders provides a private type
Holder and a set of operations for that type. A holder container holds a single element
of an indefinite type.
!corrigendum A.18.17
@dinsc
The language-defined generic package Containers.Bounded_Vectors
provides a private type Vector and a set of operations. It provides
the same operations as the package Containers.Vectors (see A.18.2),
with the difference that the maximum storage is bounded.
@s8<@i>
The declaration of the generic library package
Containers.Bounded_Vectors has the same contents and semantics as
Containers.Vectors except:
@xbullet Preelaborate is replaced with @fa Pure.>
@xbullet
@xcode< @b Vector (Capacity : Count_Type) @b;>
@xbullet
@xbullet
@xbullet
@xindent
@s8<@i>
Bounded vector objects should be implemented without implicit pointers or
dynamic allocation.
The implementation advice for procedure Move to minimize copying does not
apply.
!corrigendum A.18.18(0)
@dinsc
The language-defined generic package
Containers.Bounded_Doubly_Linked_Lists provides a private type List
and a set of operations. It provides the same operations as the
package Containers.Doubly_Linked_Lists (see A.18.3), with the
difference that the maximum storage is bounded.
@s8<@i>
The declaration of the generic library package
Containers.Bounded_Doubly_Linked_Lists has the same contents and
semantics as Containers.Doubly_Linked_Lists except:
@xbullet Preelaborate is replaced with @fa Pure.>
@xbullet
@xcode< @b List (Capacity : Count_Type) @b;>
@xbullet
@xbullet
@xbullet
@xbullet
@xcode< @b Copy (Source : List; Capacity : Count_Type := 0)
@b List;>
@xindent
@xbullet
@xbullet
@s8<@i>
Bounded list objects should be implemented without implicit pointers or
dynamic allocation.
The implementation advice for procedure Move to minimize copying does not
apply.
!corrigendum A.18.19(0)
@dinsc
The language-defined generic package Containers.Bounded_Hashed_Maps
provides a private type Map and a set of operations. It provides the
same operations as the package Containers.Hashed_Maps (see A.18.5),
with the difference that the maximum storage is bounded.
@s8<@i>
The declaration of the generic library package
Containers.Bounded_Hashed_Maps has the same contents and semantics as
Containers.Hashed_Maps except:
@xbullet Preelaborate is replaced with @fa Pure.>
@xbullet
@xcode< @b Map (Capacity : Count_Type;
Modulus : Hash_Type) @b;>
@xbullet
@xbullet
@xindent
@xbullet
@xcode< @b Default_Modulus (Capacity : Count_Type) @b Hash_Type;>
@xindent
@xbullet
@xcode< @b Copy (Source : Map;
Capacity : Count_Type := 0;
Modulus : Hash_Type := 0) @b Map;>
@xindent
@s8<@i