--- ai05s/ai05-0001-1.txt 2009/06/08 06:51:58 1.8 +++ ai05s/ai05-0001-1.txt 2009/07/07 04:30:45 1.9 @@ -1,5 +1,47 @@ -!standard A.18(0/2) 09-06-03 AI05-0001-1/05 +!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 @@ -22,8 +64,7 @@ !proposal Bounded forms for all of the containers are added to Ada. We also add -task-safe queues, generalized sorting, and case-insensitive comparison -and hashing operations. +generalized sorting and case-insensitive comparison and hashing operations. !wording @@ -37,7 +78,7 @@ with Ada.Containers; function Ada.Strings.Hash_Case_Insensitive (Key : String) return Containers.Hash_Type; -pragma Pure (Ada.Strings.Hash_Case_Insensitive); +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 @@ -77,14 +118,16 @@ call Strings.Hash_Case_Insensitive (To_String (Key)); -A.4.10 String Comparison +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 (Ada.Strings.Equal_Case_Insensitive); +pragma Pure (Equal_Case_Insensitive); Compares strings Left and Right, folded to lower case, for equality. @@ -92,8 +135,9 @@ following declaration: with Ada.Containers, Ada.Strings.Equal_Case_Insensitive; -function Ada.Strings.Fixed.Equal_Case_Insensitive (Key : String) - return Boolean renames 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 @@ -128,7 +172,7 @@ function Ada.Strings.Less_Case_Insensitive (Left, Right : String) return Boolean; -pragma Pure (Ada.Strings.Less_Case_Insensitive); +pragma Pure (Less_Case_Insensitive); Performs a lexicographic comparison of strings Left and Right, folded to lower case. @@ -138,8 +182,9 @@ following declaration: with Ada.Containers, Ada.Strings.Less_Case_Insensitive; -function Ada.Strings.Fixed.Less_Case_Insensitive (Key : String) - return Boolean renames 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); @@ -164,12 +209,23 @@ with Ada.Containers; function Ada.Strings.Unbounded.Less_Case_Insensitive (Left, Right : Unbounded_String) return Boolean; -pragma Preelaborate(Equal_Case_Insensitive); +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): @@ -181,29 +237,23 @@ Add the following declarations after A.18.2(34/2): - procedure Assign (Target : in out Vector; Source : Vector); + 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(147/2): - procedure Assign (Target : in out Vector; Source : 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. +Add the following after A.18.2(88/2): - function Copy (Source : Vector; Capacity : Count_Type := 0) - return Vector; +Vector'Write writes Vector.Length elements to the stream. +Vector'Read reads Vector.Length elements from the stream. -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. +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): @@ -211,6 +261,10 @@ 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, } @@ -224,6 +278,25 @@ 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 @@ -232,26 +305,27 @@ is removed from Source and inserted into Target in the original order. The length of Source is 0 after a successful call to Move. -Add the following after A.18.2(93/2): - - * it calls Assign with V as the Target parameter; or - 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 : List); + 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 : List); + 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 @@ -263,7 +337,8 @@ The description of Move in A.18.3(88/2) is replaced with: -Equivalent to Target.Assign (Source) followed by Source.Clear. +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 @@ -272,67 +347,60 @@ * it calls Assign with M as the Target parameter; or -The description of Move in A.18.4(43/2) is replaced with: +Add the following after A.18.4(19/2): -Equivalent to Target.Assign (Source) followed by Source.Clear. +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); -A.18.5 Containers.Hashed_Maps +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. -Add the following declarations after A.18.5(17/2): +The description of Move in A.18.4(43/2) is replaced with: - procedure Assign (Target : in out Map; Source : Map); +If Target denotes the same object as Source, then Move has no effect. Otherwise, +equivalent to Target.Assign (Source) followed by Source.Clear. - function Copy (Source : Map) return Map; -[ARG] -Does the unbounded form of hashed map (or hashed set) have additional -parameters for Copy? +A.18.5 Containers.Hashed_Maps -[END ARG] +Add the following declarations after A.18.5(17/2): -Add the following declaration after A.18.5(37/2): + procedure Assign (Target : in out Map; Source : in Map); - function Default_Modulus (Capacity : Count_Type) return Hash_Type; + function Copy (Source : Map; Capacity : Count_Type := 0) return Map; -Add the following after A.18.2(61/2): +Add the following after A.18.5(53/2): - procedure Assign (Target : in out Map; Source : Map); + procedure Assign (Target : in out Map; Source : in Map); -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 then inserted into Target. +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) return Map; + 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. - - 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). +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 : Map); + procedure Assign (Target : in out Map; Source : in Map); function Copy (Source : Map) return Map; Add the following after A.18.6(58/2): - procedure Assign (Target : in out Map; Source : Map); - -If Target denotes the same object as Source, the operation has no -effect. Each key/element pair of Source is assigned to the -corresponding key/element pairs of Target. - function Copy (Source : Map) return Map; Returns a map whose keys and elements are initialized from the @@ -344,111 +412,76 @@ * it calls Assign with S as the Target parameter; or -The description of Move in A.18.7(38/2) is replaced with: +Add the following after A.18.7(18/2): -Equivalent to Target.Assign (Source) followed by Source.Clear. +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): -A.18.8 Containers.Hashed_Sets + procedure Assign (Target : in out Set; Source : in Set); -Add the following declarations after A.18.8(17/2): +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. - procedure Assign (Target : in out Set; Source : Set); +The description of Move in A.18.7(38/2) is replaced with: - function Copy (Source : Set) return Set; +If Target denotes the same object as Source, then Move has no effect. Otherwise, +equivalent to Target.Assign (Source) followed by Source.Clear. -Add the following declaration after A.18.8(49/2): - function Default_Modulus (Capacity : Count_Type) return Hash_Type; +A.18.8 Containers.Hashed_Sets -Add the following after A.18.8(87/2): +Add the following declarations after A.18.8(17/2): - procedure Assign (Target : in out Set; Source : Set); + procedure Assign (Target : in out Set; Source : in Set); -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 then inserted into Target. + function Copy (Source : Set; Capacity : Count_Type := 0) return Set; - function Copy (Source : Set) return Set; +Add the following after A.18.8(75/2): -Returns a set whose elements are initialized from the elements of -Source. + procedure Assign (Target : in out Set; Source : in Set); - function Default_Modulus (Capacity : Count_Type) return Hash_Type; +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. -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). + 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 : Set); + procedure Assign (Target : in out Set; Source : in Set); function Copy (Source : Set) return Set; Add the following after A.18.9(81/2): - procedure Assign (Target : in out Set; Source : 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. - function Copy (Source : Set) return Set; Returns a set whose elements are initialized from the corresponding elements of Source. - -A.18.16 Array Sorting - -A.18.16 (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 declarations after A.18.16 (9/2): +A.18.16 Containers.Indefinite_Holders (see AI05-0069-1) -generic - type Index_Type is (<>); - with function Before (Left, Right : Index_Type) return Boolean; - with procedure Swap (Left, Right : Index_Type); +Add the following declarations after A.18.16(15/3): [Before Move] -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 smallest first as -determined by the generic formal Before function provided. Generic -formal Before compares the elements having the given indices, and -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 a particular pair of element values. It should define a -strict weak ordering relationship (see A.18); it should not modify the -elements. If the actual for Before behaves in some other manner, the -behavior of Generic_Sort is unspecified. How many times the -Generic_Sort calls Before or Swap is unspecified. + procedure Assign (Target : in out Holder; Source : in Holder); - -A.18.17 Containers.Indefinite_Holders (see AI05-0069-1) - -Add the following declarations after A.18.17(15/3): [Before Move] - - procedure Assign (Target : in out Holder; Source : Holder); - function Copy (Source : Holder) return Holder; -Add the following after A.18.17(44/3): +Add the following after A.18.16(44/3): - procedure Assign (Target : in out Holder; Source : Holder); + 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, @@ -459,7 +492,7 @@ If Source is empty, returns an empty holder; otherwise, returns To_Holder (Element (Source)). -A.18.18 The Package Containers.Bounded_Vectors +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 @@ -472,7 +505,7 @@ Containers.Bounded_Vectors has the same contents and semantics as Containers.Vectors except: - * pragma Preelaborate is replaced with pragma Pure + * pragma Preelaborate is replaced with pragma Pure. AARM implementation note: Package Containers.Bounded_Vectors cannot depend on package Ada.Finalization (because that package @@ -483,8 +516,8 @@ type Vector (Capacity : Count_Type) is tagged private; - * The type Vector does not need finalization if and only type - Element_Type does not need finalization. + * 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 @@ -495,23 +528,17 @@ If the specified Capacity is larger than the Container.Capacity, then Reserve_Capacity raises Capacity_Error. Otherwise, the operation has no effect. + +Implementation Advice - * The implementation advice for procedure Move does not apply. +Bounded vector objects should be implemented without implicit pointers or +dynamic allocation. -[Editor's note: Matt had "The implementation advice in A.18.2(261/2) -does not apply", but of course wording cannot refer to paragraph numbers -(the ISO version doesn't have them). I made the above replacement, -but I'm not happy with it - 262/2 applies to Move and we don't want -to eliminate it.]. - - * The implementation advice includes an additional item, stating - that bounded vector objects should not be implemented by - implicit pointers or dynamic allocation. +The implementation advice for procedure Move to minimize copying does not +apply. - * Vector'Write writes only Vector.Length elements to the stream. - Vector'Read reads only Vector.Length elements from the stream. -A.18.19 Package Containers.Bounded_Doubly_Linked_Lists +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 @@ -525,7 +552,7 @@ Containers.Bounded_Doubly_Linked_Lists has the same contents and semantics as Containers.Doubly_Linked_Lists except: - * pragma Preelaborate is replaced with pragma Pure + * pragma Preelaborate is replaced with pragma Pure. AARM implementation note: Package Containers.Bounded_Doubly_Linked_Lists cannot depend on @@ -533,12 +560,12 @@ categorization). * The type List is declared with a discriminant that specifies the - capacity: + capacity (maximum number of elements) as follows: type List (Capacity : Count_Type) is tagged private; - * The type List does not need finalization if and only type - Element_Type does not need finalization. + * 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 @@ -557,26 +584,28 @@ the list capacity equals the value of the Capacity parameter; otherwise, the operation raises Capacity_Error. - * The implementation advice for procedure Move does not apply. + * 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. - * In three-parameter procedure Splice whose Source has type List, - if the sum of the Target length and Source - length is greater than the 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 four-parameter procedure Splice, if the - Target length equals the Target capacity, then Splice raises - Capacity_Error. + * 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. - * List'Write writes only List.Length elements to the stream. - List'Read reads only List.Length elements from the stream. -A.18.20 Containers.Bounded_Hashed_Maps +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 @@ -589,21 +618,21 @@ Containers.Bounded_Hashed_Maps has the same contents and semantics as Containers.Hashed_Maps except: - * pragma Preelaborate is replaced with pragma Pure + * 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 a discriminant that specifies both + * 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 does not need finalization if and only type - Key_Type or type Element_Type does not need finalization. + * 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: @@ -612,6 +641,13 @@ 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; @@ -628,14 +664,17 @@ its argument; otherwise the map modulus is the value of the Modulus parameter. - * The implementation advice for procedure Move does not apply. +Implementation Advice - * Map'Write writes only Map.Length elements to the stream. - Map'Read reads only Map.Length elements from the stream. +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 Containers.Bounded_Ordered_Maps +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), @@ -647,7 +686,7 @@ Containers.Bounded_Ordered_Maps has the same contents and semantics as Containers.Ordered_Maps except: - * pragma Preelaborate is replaced with pragma Pure + * pragma Preelaborate is replaced with pragma Pure. AARM implementation note: Package Containers.Bounded_Ordered_Maps cannot depend on package Ada.Finalization (because that package @@ -658,8 +697,12 @@ type Map (Capacity : Count_Type) is tagged private; - * The type Map does not need finalization if and only type - Key_Type or type Element_Type does not need finalization. + * 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. @@ -674,14 +717,17 @@ 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 - * The implementation advice for procedure Move does not apply. +Bounded map objects should be implemented without implicit pointers or +dynamic allocation. - * Map'Write writes only Map.Length elements to the stream. - Map'Read reads only Map.Length elements from the stream. +The implementation advice for procedure Move to minimize copying does not +apply. -A.18.22 Containers.Bounded_Hashed_Sets +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 @@ -694,21 +740,21 @@ Containers.Bounded_Hashed_Sets has the same contents and semantics as Containers.Hashed_Sets except: - * pragma Preelaborate is replaced with pragma Pure + * 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 a discriminant that specifies both + * 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 does not need finalization if and only type - Element_Type does not need finalization. + * The type Set needs finalization if and only if type + Element_Type needs finalization. * The description of Reserve_Capacity is replaced by: @@ -716,6 +762,13 @@ 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; @@ -731,14 +784,17 @@ 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 - * The implementation advice for procedure Move does not apply. +Bounded set objects should be implemented without implicit pointers or +dynamic allocation. - * Set'Write writes only Set.Length elements to the stream. - Set'Read reads only Set.Length elements from the stream. +The implementation advice for procedure Move to minimize copying does not +apply. -A.18.23 Containers.Bounded_Ordered_Sets +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 @@ -762,9 +818,13 @@ type Set (Capacity : Count_Type) is tagged private; - * The type Set does not need finalization if and only type - Element_Type does not need finalization. + * 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. @@ -778,25 +838,987 @@ 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 does not apply. +The implementation advice for procedure Move to minimize copying does not +apply. - * Set'Write writes only Set.Length elements to the stream. - Set'Read reads only Set.Length elements from the stream. +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) +AI05-0159-1 (Queues). + +--- -We need to copy some info from the notes from that meeting here to justify -these choices better. +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<Strings.Unbounded.Hash is equivalent to the function call +Strings.Hash (To_String (Key));> +@dinss +The library function Strings.Hash_Case_Insensitive has the following +declaration: + +@xcode<@b<with> Ada.Containers; +@b<function> Ada.Strings.Hash_Case_Insensitive (Key : String) + @b<return> Containers.Hash_Type; +@b<pragma> Pure(Hash_Case_Insensitive);> + +@xindent<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: + +@xcode<@b<with> Ada.Containers, Ada.Strings.Hash_Case_Insensitive; +@b<function> Ada.Strings.Fixed.Hash_Case_Insensitive (Key : String) + @b<return> Containers.Hash_Type @b<renames> Ada.Strings.Hash_Case_Insensitive; +@b<pragma> Pure(Hash_Case_Insensitive);> + +The generic library function Strings.Bounded.Hash_Case_Insensitive has +the following declaration: + +@xcode<with Ada.Containers; +@b<generic> + @b<with package> Bounded @b<is> + @b<new> Ada.Strings.Bounded.Generic_Bounded_Length (<@>); +@b<function> Ada.Strings.Bounded.Hash_Case_Insensitive + (Key : Bounded.Bounded_String) @b<return> Containers.Hash_Type; +@b<pragma> Preelaborate(Hash_Case_Insensitive);> + +@xindent<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: + +@xcode<@b<with> Ada.Containers; +@b<function> Ada.Strings.Unbounded.Hash_Case_Insensitive + (Key : Unbounded_String) @b<return> Containers.Hash_Type; +@b<pragma> Preelaborate(Hash_Case_Insensitive);> + +@xindent<Strings.Unbounded.Hash_Case_Insensitive is equivalent to the function +call Strings.Hash_Case_Insensitive (To_String (Key));> + + +!corrigendum A.4.10(0) + +@dinsc + +@s8<@i<Static Semantics>> + +The library function Strings.Equal_Case_Insensitive has the following +declaration: + +@xcode<@b<function> Ada.Strings.Equal_Case_Insensitive (Left, Right : String) + @b<return> Boolean; +@b<pragma> Pure(Equal_Case_Insensitive);> + +@xindent<Compares strings Left and Right, folded to lower case, for equality.> + +The library function Strings.Fixed.Equal_Case_Insensitive has the +following declaration: + +@xcode<@b<with> Ada.Containers, Ada.Strings.Equal_Case_Insensitive; +@b<function> Ada.Strings.Fixed.Equal_Case_Insensitive + (Left, Right : String) @b<return> Boolean + @b<renames> Ada.Strings.Equal_Case_Insensitive; +@b<pragma> Pure(Equal_Case_Insensitive);> + +The generic library function Strings.Bounded.Equal_Case_Insensitive has +the following declaration: + +@xcode<@b<with> Ada.Containers; +@b<generic> + @b<with package> Bounded @b<is> + @b<new> Ada.Strings.Bounded.Generic_Bounded_Length (<@>); +@b<function> Ada.Strings.Bounded.Equal_Case_Insensitive + (Left, Right : Bounded.Bounded_String) @b<return> Boolean; +@b<pragma> Preelaborate(Equal_Case_Insensitive);> + +@xindent<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: + +@xcode<@b<with> Ada.Containers; +@b<function> Ada.Strings.Unbounded.Equal_Case_Insensitive + (Left, Right : Unbounded_String) @b<return> Boolean; +@b<pragma> Preelaborate(Equal_Case_Insensitive);> + +@xindent<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: + +@xcode<@b<function> Ada.Strings.Less_Case_Insensitive (Left, Right : String) + @b<return> Boolean; +@b<pragma> Pure(Less_Case_Insensitive);> + +@xindent<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: + +@xcode<@b<with> Ada.Containers, Ada.Strings.Less_Case_Insensitive; +@b<function> Ada.Strings.Fixed.Less_Case_Insensitive + (Left, Right : String) @b<return> Boolean + @b<renames> Ada.Strings.Less_Case_Insensitive; +@b<pragma> Pure(Less_Case_Insensitive);> + +The generic library function Strings.Bounded.Less_Case_Insensitive has +the following declaration: + +@xcode<@b<with> Ada.Containers; +@b<generic> + @b<with package> Bounded @b<is> + @b<new> Ada.Strings.Bounded.Generic_Bounded_Length (<@>); +@b<function> Ada.Strings.Bounded.Less_Case_Insensitive + (Left, Right : Bounded.Bounded_String) @b<return> Boolean; +@b<pragma> Preelaborate(Less_Case_Insensitive);> + +@xindent<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: + +@xcode<@b<with> Ada.Containers; +@b<function> Ada.Strings.Unbounded.Less_Case_Insensitive + (Left, Right : Unbounded_String) @b<return> Boolean; +@b<pragma> Preelaborate(Less_Case_Insensitive);> + +@xindent<Strings.Unbounded.Less_Case_Insensitive is equivalent to the function +call Strings.Less_Case_Insensitive (To_String (Key));> + + +!corrigendum A.18(4/2) + +@dinsa +If the advice suggests that the complexity should be less than @i<O>(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<strict weak ordering> if it is irreflexive, +asymmetric, transitive, and in addition, if @i<x> < @i<y> for +any values @i<x> and @i<y>, then for all other values @i<z>, +(@i<x> < @i<z>) or (@i<z> < @i<y>). + +!corrigendum A.18.1(5/2) + +@dinsa +@xcode< @b<type> Count_Type @b<is range> 0 .. @ft<@i<implementation-defined>>;> +@dinst +@xcode< Capacity_Error : @b<exception>;> + +!corrigendum A.18.2(34/2) + +@dinsa +@xcode< @b<procedure> Update_Element + (Container : @b<in out> Vector; + Position : @b<in> Cursor; + Process : @b<not null access procedure> + (Element : @b<in out> Element_Type));> +@dinss +@xcode< @b<procedure> Assign (Target : @b<in out> Vector; Source : @b<in> Vector);> + +@xcode< @b<function> Copy (Source : Vector; Capacity : Count_Type := 0) + @b<return> 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<it finalizes @i<V>; or> +@dinst +@xbullet<it calls Assign with @i<V> 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<The element designated by Position is not an empty element after successful +completion of this operation.> +@dinss +@xcode<@b<procedure> Assign (Target : @b<in out> Vector; Source : @b<in> Vector);> + +@xindent<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.> + +@xcode<@b<function> Copy (Source : Vector; Capacity : Count_Type := 0) + @b<return> Vector;> + +@xindent<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.> + +!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<procedure> Update_Element + (Container : @b<in out> List; + Position : @b<in> Cursor; + Process : @b<not null access procedure> + (Element : @b<in out> Element_Type));> +@dinss +@xcode< @b<procedure> Assign (Target : @b<in out> List; Source : @b<in> List);> + +@xcode< @b<function> Copy (Source : List) @b<return> 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<it finalizes @i<L>; or> +@dinst +@xbullet<it calls Assign with @i<L> as the Target parameter; or> + +!corrigendum A.18.3(86/2) + +@dinsa +@xindent<If Element_Type is unconstrained and definite, then the actual Element parameter of +Process.@b<all> shall be unconstrained.> +@dinss +@xcode<@b<procedure> Assign (Target : @b<in out> List; Source : @b<in> List);> + +@xindent<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.> + +@xcode<@b<function> Copy (Source : List) @b<return> List;> + +@xindent<Returns a list whose elements match the elements of Source.> + +!corrigendum A.18.3(88/2) + +@drepl +@xindent<If Target denotes the same object as Source, then Move has no effect. Otherwise, +Move first calls Clear (Target). Then, the nodes in Source are moved to Target (in the +original order). The length of Target is set to the length of Source, and the length of +Source is set to 0.> +@dby +@xindent<If Target denotes the same object as Source, then Move has no effect. Otherwise, +equivalent to Target.Assign (Source) followed by Source.Clear.> + +!corrigendum A.18.4(10/2) + +@dinsa +@xbullet<it finalizes @i<M>; or> +@dinst +@xbullet<it calls Assign with @i<M> 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<If Element_Type is unconstrained and definite, then the actual Element parameter of +Process.@b<all> shall be unconstrained.> +@dinst +@xcode<@b<procedure> Assign (Target : @b<in out> Map; Source : @b<in> Map);> + +@xindent<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.> + +!corrigendum A.18.4(43/2) + +@drepl +@xindent<If Target denotes the same object as Source, then Move has no effect. Otherwise, Move first +calls Clear (Target). Then, each node from Source is removed from Source and inserted into +Target. The length of Source is 0 after a successful call to Move.> +@dby +@xindent<If Target denotes the same object as Source, then Move has no effect. Otherwise, +equivalent to Target.Assign (Source) followed by Source.Clear.> + +!corrigendum A.18.5(17/2) + +@dinsa +@xcode< @b<procedure> Update_Element + (Container : @b<in out> Map; + Position : @b<in> Cursor; + Process : @b<not null access> procedure + (Key : @b<in> Key_Type; + Element : @b<in out> Element_Type));> +@dinss +@xcode< @b<procedure> Assign (Target : @b<in out> Map; Source : @b<in> Map);> + +@xcode< @b<function> Copy (Source : Map; Capacity : Count_Type := 0) @b<return> 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<procedure> Assign (Target : @b<in out> Map; Source : @b<in> Map);> + +@xindent<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.> + +@xcode<@b<function> Copy (Source : Map; Capacity : Count_Type := 0) @b<return> Map;> + +@xindent<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.> + +!corrigendum A.18.6(16/2) + +@dinsa +@xcode< @b<procedure> Update_Element + (Container : @b<in out> Map; + Position : @b<in> Cursor; + Process : @b<not null access> procedure + (Key : @b<in> Key_Type; + Element : @b<in out> Element_Type));> +@dinss +@xcode< @b<procedure> Assign (Target : @b<in out> Map; Source : @b<in> Map);> + +@xcode< @b<function> Copy (Source : Map) @b<return> 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<function> Copy (Source : Map) @b<return> Map;> + +@xindent<Returns a map whose keys and elements are initialized from the +corresponding keys and elements of Source.> + +!corrigendum A.18.7(10/2) + +@dinsa +@xbullet<it finalizes @i<S>; or> +@dinst +@xbullet<it calls Assign with @i<S> 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<If Position equals No_Element, then Constraint_Error is propagated. +Otherwise, Query_Element calls Process.@b<all> with the element designated by +Position as the argument. Program_Error is propagated if Process.@b<all> +tampers with the elements of Container. Any exception raised by Process.all is propagated.> +@dinss +@xcode<@b<procedure> Assign (Target : @b<in out> Set; Source : @b<in> Set);> + +@xindent<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.> + +!corrigendum A.18.7(38/2) + +@drepl +@xindent<If Target denotes the same object as Source, then Move has no effect. Otherwise, +Move first clears Target. Then, each element from Source is removed from Source +and inserted into Target. The length of Source is 0 after a successful call to Move.> +@dby +@xindent<If Target denotes the same object as Source, then Move has no effect. Otherwise, +equivalent to Target.Assign (Source) followed by Source.Clear.> + +!corrigendum A.18.8(17/2) + +@dinsa +@xcode< @b<procedure> Query_Element + (Position : @b<in> Cursor; + Process : @b<not null access> procedure (Element : @b<in> Element_Type));> +@dinss +@xcode< @b<procedure> Assign (Target : @b<in out> Set; Source : @b<in> Set);> + +@xcode< @b<function> Copy (Source : Set; Capacity : Count_Type := 0) @b<return> 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<procedure> Assign (Target : @b<in out> Set; Source : @b<in> Set);> + +@xindent<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.> + +@xcode<@b<function> Copy (Source : Set; Capacity : Count_Type := 0) @b<return> Set;> + +@xindent<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.> + +!corrigendum A.18.9(16/2) + +@dinsa +@xcode< @b<procedure> Query_Element + (Position : @b<in> Cursor; + Process : @b<not null access> procedure (Element : @b<in> Element_Type));> +@dinss +@xcode< @b<procedure> Assign (Target : @b<in out> Set; Source : @b<in> Set);> + +@xcode< @b<function> Copy (Source : Set) @b<return> 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<function> Copy (Source : Set) @b<return> Set;> + +@xindent<Returns a set whose elements are initialized from the corresponding elements of Source.> + + +!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<Static Semantics>> + +The declaration of the generic library package +Containers.Bounded_Vectors has the same contents and semantics as +Containers.Vectors except: + +@xbullet<@fa<Pragma> Preelaborate is replaced with @fa<pragma> Pure.> + +@xbullet<The type Vector is declared with a discriminant that specifies +the capacity:> + +@xcode< @b<type> Vector (Capacity : Count_Type) @b<is tagged private>;> + +@xbullet<The type Vector needs finalization if and only if type +Element_Type needs finalization.> + +@xbullet<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.> + +@xbullet<The description of Reserve_Capacity is replaced by:> + +@xindent<If the specified Capacity is larger than the Container.Capacity, +then Reserve_Capacity raises Capacity_Error. Otherwise, the operation has no effect.> + +@s8<@i<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. + +!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<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: + +@xbullet<@fa<Pragma> Preelaborate is replaced with @fa<pragma> Pure.> + +@xbullet<The type List is declared with a discriminant that specifies +the capacity (maximum number of elements) as follows:> + +@xcode< @b<type> List (Capacity : Count_Type) @b<is tagged private>;> + +@xbullet<The type List needs finalization if and only if type +Element_Type needs finalization.> + +@xbullet<The allocation of internal storage includes a check that the +capacity is not exceeded, and Capacity_Error is raised if this +check fails.> + +@xbullet<In procedure Assign, if Source length is greater than Target +capacity, then Capacity_Error is raised.> + +@xbullet<Function Copy is declared as follows:> + +@xcode< @b<function> Copy (Source : List; Capacity : Count_Type := 0) + @b<return> List;> + +@xindent<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.> + +@xbullet<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.> + +@xbullet<In the four-parameter procedure Splice, if Target.Length +equals Target.Capacity, then Splice raises Capacity_Error.> + +@s8<@i<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. + + +!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<Static Semantics>> + +The declaration of the generic library package +Containers.Bounded_Hashed_Maps has the same contents and semantics as +Containers.Hashed_Maps except: + +@xbullet<@fa<Pragma> Preelaborate is replaced with @fa<pragma> Pure.> + +@xbullet<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:> + +@xcode< @b<type> Map (Capacity : Count_Type; + Modulus : Hash_Type) @b<is tagged private>;> + +@xbullet<The type Map needs finalization if and only if type +Key_Type or type Element_Type needs finalization.> + +@xbullet<The description of Reserve_Capacity is replaced by:> + +@xindent<If the specified Capacity is larger than the Container.Capacity, +then Reserve_Capacity raises Capacity_Error. Otherwise, the operation has no effect.> + +@xbullet<An additional operation is added immediately following Reserve_Capacity:> + +@xcode< @b<function> Default_Modulus (Capacity : Count_Type) @b<return> Hash_Type;> + +@xindent<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).> + +@xbullet<The function Copy is replaced with:> + +@xcode< @b<function> Copy (Source : Map; + Capacity : Count_Type := 0; + Modulus : Hash_Type := 0) @b<return> Map;> + +@xindent<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.> + +@s8<@i<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. + + +!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<Static Semantics>> + +The declaration of the generic library package +Containers.Bounded_Ordered_Maps has the same contents and semantics as +Containers.Ordered_Maps except: + +@xbullet<@fa<Pragma> Preelaborate is replaced with @fa<pragma> Pure.> + +@xbullet<The type Map is declared with a discriminant that specifies +the capacity (maximum number of elements) as follows:> + +@xcode< @b<type> Map (Capacity : Count_Type) @b<is tagged private>;> + +@xbullet<The type Map needs finalization if and only if type +Key_Type or type Element_Type needs finalization.> + +@xbullet<The allocation of a new node includes a check that the +capacity is not exceeded, and Capacity_Error is raised if this +check fails.> + +@xbullet<In procedure Assign, if Source length is greater than Target +capacity, then Capacity_Error is raised.> + +@xbullet<The function Copy is replaced with:> + +@xcode< @b<function> Copy (Source : Map; + Capacity : Count_Type := 0) @b<return> Map;> + +@xindent<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.> + +@s8<@i<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. + + +!corrigendum A.18.21(0) + +@dinsc + +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. + +@s8<@i<Static Semantics>> + +The declaration of the generic library package +Containers.Bounded_Hashed_Sets has the same contents and semantics as +Containers.Hashed_Sets except: + +@xbullet<@fa<Pragma> Preelaborate is replaced with @fa<pragma> Pure.> + +@xbullet<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:> + +@xcode< @b<type> Set (Capacity : Count_Type; + Modulus : Hash_Type) @b<is tagged private>;> + +@xbullet<The type Set needs finalization if and only if type +Key_Type or type Element_Type needs finalization.> + +@xbullet<The description of Reserve_Capacity is replaced by:> + +@xindent<If the specified Capacity is larger than the Container.Capacity, +then Reserve_Capacity raises Capacity_Error. Otherwise, the operation has no effect.> + +@xbullet<An additional operation is added immediately following Reserve_Capacity:> + +@xcode< @b<function> Default_Modulus (Capacity : Count_Type) @b<return> Hash_Type;> + +@xindent<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).> + +@xbullet<The function Copy is replaced with:> + +@xcode< @b<function> Copy (Source : Set; + Capacity : Count_Type := 0; + Modulus : Hash_Type := 0) @b<return> Map;> + +@xindent<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.> + +@s8<@i<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. + + +!corrigendum A.18.22(0) + +@dinsc + +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. + +@s8<@i<Static Semantics>> + +The declaration of the generic library package +Containers.Bounded_Ordered_Sets has the same contents and semantics as +Containers.Ordered_Sets except: + +@xbullet<@fa<Pragma> Preelaborate is replaced with @fa<pragma> Pure.> + +@xbullet<The type Set is declared with a discriminant that specifies +the capacity (maximum number of elements) as follows:> + +@xcode< @b<type> Set (Capacity : Count_Type) @b<is tagged private>;> + +@xbullet<The type Set needs finalization if and only if type +Element_Type needs finalization.> + +@xbullet<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.> + +@xbullet<In procedure Assign, if Source length is greater than Target +capacity, then Capacity_Error is raised.> + +@xbullet<The function Copy is replaced with:> + +@xcode< @b<function> Copy (Source : Map; + Capacity : Count_Type := 0) @b<return> Map;> + +@xindent<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.> + +@s8<@i<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. + + +!corrigendum A.18.23(1/2) + +@drepl +The language-defined generic procedures Containers.Generic_Array_Sort +and Containers.Generic_Constrained_Array_Sort +provide sorting on arbitrary array types. +@dby +The language-defined generic procedures Containers.Generic_Array_Sort, +Containers.Generic_Constrained_Array_Sort, and Containers.Generic_Sort +provide sorting on arbitrary array types. + +!corrigendum A.18.23(9/2) + +@dinsa +@xindent<The actual function for the generic formal function "<" of Generic_Constrained_Array_Sort +is expected to return the same value each time it is called with a particular pair +of element values. It should define a strict ordering relationship, that is, +be irreflexive, asymmetric, and transitive; it should not modify Container. +If the actual for "<" behaves in some other manner, the behavior of the instance +of Generic_Constrained_Array_Sort is unspecified. How many times +Generic_Constrained_Array_Sort calls "<" is unspecified.> +@dinss +The generic library procedure Containers.Generic_Sort has the following declaration: + +@xcode<generic + @b<type> Index_Type is (<@>); + @b<with function> Before (Left, Right : Index_Type) @b<return> Boolean; + @b<with procedure> Swap (Left, Right : Index_Type); +@b<procedure> Ada.Containers.Generic_Sort (First, Last : Index_Type'Base); +@b<pragma> Pure (Ada.Containers.Generic_Sort);> + +@xindent<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.> + +@xindent<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.> + + !ACATS test +ACATS C-Tests are required for these new packages. + !appendix From: Martin Dowie @@ -3666,3 +4688,76 @@ "need finalization." **************************************************************** + +From: Randy Brukardt +Sent: Friday, July 3, 2009 8:25 PM + +Having finished the minutes draft, I've moved back to inserting the new text +of AI05-0001-1 into the consolidated RM. That process of course forces me +to re-read the AI very carefully, and bugs pop up. + +One of the changes is (A.18.3(88/2), procedure Move): + +Replace: + +If Target denotes the same object as Source, then Move has no effect. Otherwise, +Move first calls Clear (Target). Then, the nodes in Source are moved to Target +(in the original order). The length of Target is set to the length of Source, +and the length of Source is set to 0. + +By: + +Equivalent to Target.Assign (Source) followed by Source.Clear. + + +But this replacement is clearly wrong. If Target and Source are the same object, +this new wording would have the effect of clearing the object, while the old wording +does nothing to the object. + +We need to say something like: + +If Target denotes the same object as Source, then Move has no effect. Otherwise, +equivalent to Target.Assign (Source) followed by Source.Clear. + +We need to make similar changes for A.18.4(43/2) and A.18.7(38/2). + +**************************************************************** + +From: Randy Brukardt +Sent: Monday, July 6, 2009 9:06 PM + +There is no wording in Bounded_Ordered_Maps or Bounded_Ordered_Sets to check for +reaching the capacity of the container. (We don't need such wording for the Hashed +forms, as the Reserve_Capacity call does the dirty work.) + +For lists, we added the following for this case: + +* The allocation of internal storage includes a check that the + capacity is not exceeded, and Capacity_Error is raised if this + check fails. + +"Allocates a new node" is the wording of A.18.4(45/2) defining what Insert does, +the other insertions are defined by difference from this one. So, for ordered maps, +we should have the following: + +* The allocation of a new node includes a check that the + capacity is not exceeded, and Capacity_Error is raised if this + check fails. + + +The wording of ordered sets is different. "Otherwise, Insert adds New_Item to +Container..." I think "adds" is too vague to use in this technical manner, so I +think we need wording like: + +* 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. + +[I can't find any routines other than Insert or Include that can add an element. +Did I miss any?] + +Any comments? + +**************************************************************** + +

Questions? Ask the ACAA Technical Agent