!standard A.4.9(11/2) 09-07-03 AI05-0001-1/07
!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(148/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
(See proposal.)
!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 real-time
systems. Some users have indicated that access to a single container by multiple
tasks is needed.
!proposal
Bounded forms for all of the containers are added to Ada. We also add
generalized sorting and case-insensitive comparison and hashing operations.
!wording
A.4.9 String Hashing
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, folded to lower case. If A and B are strings such that A equals
B, 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);
Strings.Bounded.Hash_Case_Insensitive is equivalent to the function call
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);
Strings.Unbounded.Hash_Case_Insensitive is equivalent to the function
call 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, folded 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 : Bounded.Bounded_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);
Strings.Bounded.Equal_Case_Insensitive is equivalent to the function call
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);
Strings.Unbounded.Equal_Case_Insensitive is equivalent to the function
call 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, folded 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 : Bounded.Bounded_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);
Strings.Bounded.Less_Case_Insensitive is equivalent to the function call
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);
Strings.Unbounded.Less_Case_Insensitive is equivalent to the function
call 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 any other value 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 Vector.Length elements to the stream.
Vector'Read reads Vector.Length 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
would 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 raises Constraint_Error.
Add the following after A.18.2(93/2):
* it calls Assign 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 Source length is greater than Target capacity,
Reserve_Capacity is called with the Source length as the capacity.
Each element of Source is assigned to the corresponding elements 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
Source.Length, the vector capacity is at least the specified value.
Otherwise, the operation raises Capacity_Error.
A.18.2(148/2) is replaced by the following:
If Target denotes the same object as Source, then Move has no
effect. Otherwise, Move first calls Target.Reserve_Capacity
(Source.Length) and then Target.Clear; 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 List.Length elements to the stream.
List'Read reads List.Length elements from the stream.
Add the following after A.18.3(65/2):
* it calls Assign 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 elements 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 Target.Assign (Source) followed by Source.Clear.
A.18.4 Maps
Add the following after A.18.4(10/2):
* it calls Assign with M as the Target parameter; or
Add the following after A.18.4(19/2):
Map'Write writes Map.Length elements to the stream.
Map'Read reads Map.Length 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 pairs 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 Target.Assign (Source) followed by Source.Clear.
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 Source.Length is
greater than Target.Capacity, Reserve_Capacity is called with Source.Length
as the capacity before assigning 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
Source.Length, the map capacity is at least the specified value.
Otherwise, the operation raises 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 Assign with S as the Target parameter; or
Add the following after A.18.7(18/2):
Set'Write writes Set.Length elements to the stream.
Set'Read reads Set.Length 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 Target.Assign (Source) followed by Source.Clear.
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 Source.Length is
greater than Target.Capacity, Reserve_Capacity is called with Source.Length
as the capacity before assigning 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
Source.Length, the set capacity is at least the specified value.
Otherwise, the operation raises 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:
* 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 Source.Length, the vector capacity exactly equals
the value of the Capacity parameter.
* The description of Reserve_Capacity is replaced by:
If the specified Capacity is larger than the Container.Capacity,
then Reserve_Capacity raises 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:
* 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 raised.
* Function Copy is declared as follows:
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 Source.Length,
the list capacity equals the value of the Capacity parameter;
otherwise, the operation raises Capacity_Error.
* In the three-parameter procedure Splice whose Source has type List,
if the sum of Target.Length and Source.Length is greater than
Target.Capacity, then Splice raises 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 Target.Length
equals Target.Capacity, then Splice raises 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:
* 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
by:
If the specified Capacity is larger than the Container.Capacity,
then Reserve_Capacity raises 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
Source.Length, the map capacity is the value of the Capacity
parameter; otherwise, the operation raises 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:
* 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 raised.
* 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
Source.Length, the map capacity is the specified value;
otherwise, the operation raises 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:
* 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 by:
If the specified Capacity is larger than the Container.Capacity,
then Reserve_Capacity raises 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
Source.Length, the set capacity is the value of the Capacity
parameter; otherwise, the operation raises 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:
* 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 raised.
* 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
Source.Length, the set capacity is the specified value;
otherwise, the operation raises 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 Before function. 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 also AI05-0069-1 (Indefinite_Holder), AI05-0136-1 (Multiway_Trees), and
AI05-0159-1 (Queues).
---
Case insensitive functions
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(11/2)
@dinsa
@xindent
@dinss
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 Vector.Length elements to the stream.
Vector'Read reads Vector.Length 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 raises 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(148/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 Target.Reserve_Capacity
(Source.Length) and then Target.Clear; 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 List.Length elements to the stream. List'Read reads List.Length 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 Map.Length elements to the stream.
Map'Read reads Map.Length 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 procedure
(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 procedure
(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 Set.Length elements to the stream.
Set'Read reads Set.Length 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.all 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 procedure (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 procedure (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<@fa 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<@fa 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<@fa 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>
Bounded map 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.20(0)
@dinsc
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.
@s8<@i>
The declaration of the generic library package
Containers.Bounded_Ordered_Maps has the same contents and semantics as
Containers.Ordered_Maps except:
@xbullet<@fa Preelaborate is replaced with @fa Pure.>
@xbullet