--- ai05s/ai05-0001-1.txt 2008/12/02 06:01:19 1.5 +++ ai05s/ai05-0001-1.txt 2009/02/13 07:13:55 1.6 @@ -1,4 +1,4 @@ -!standard A.18(0/2) 08-10-23 AI05-0001-1/02 +!standard A.18(0/2) 09-02-12 AI05-0001-1/03 !class Amendment 05-10-24 !status work item 06-03-15 !status received 05-10-02 @@ -27,199 +27,327 @@ !wording +Package Containers + +The library package Containers has the following additional declaration: + + Capacity_Error : exception; + + Bounded Vector + +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 internal storage is allocated statically. -The bounded vector differs from the unbounded vector as follows: +[ARG] -The package is named Ada.Containers.Bounded_Vectors. +Is that last sentence OK? +[END ARG] + +Static Semantics + +The declaration of the generic library package +Containers.Bounded_Vectors has the same contents as Containers.Vectors +except: + The package has Pure categorization. The container type is declared with a discriminant that specifies the -capacity, as follows: +capacity: type Vector (Capacity : Count_Type) is tagged private; -[ARG] We agreed during the meeting on 2008/09/22 that the bounded forms -would not be controlled. Do we need to say that? One consequence is -this is that we cannot detect finalization of the container when it's in -a tampering state, e.g. - - declare - V : Vector_Access := new Vector (42); - - procedure Process (E : ET) is - begin - Free (V); - end; - begin - V.Query_Element (1, Process'Access); - end; - -How should be handle this case? - -We also have the problem of assignment during a tampering context: - - declare - V1, V2 : Vector (42); - - procedure Process (E : ET) is - begin - V2 = V1; - end; - begin - V1.Query_Element (1, Process'Access); -- (1) - V2.Delete_First; -- (2) - end; - -Here the tampering bit gets set on V1 when we enter Query_Element (1), -and it get copied to V2. In principle the deletion (2) should work, but -unless we do something special it would incorrectly raise Program_Error. -It think we agreed in NYC that such pathological assignments would be -considered a bounded error, but we need a definitive confirmation. -[END ARG] +[ARG] + +I think Assign is going to be declared for the unbounded forms. -Immediately following the declaration of operation Clear, the following pair of -operations are declared: +In the case of Assign, we could prefer to preserve the existing +internal array. If the source length is equal or less than target +capacity, there's nothing special to do; however, if source length is +greater than target capacity, then we must reserve capacity. + +Are we over-specifying if we say what the final capacity should be? +Do we allow the capacity to shrink (as in does when the assignment +operator is used) in the unbounded form? Or do we require that the +unbounded and bounded forms behave identically wrt storage semantics? +[END ARG] + 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 then assigned to the matching element of +Target. + +[ARG] + +We need to make Copy work for the unbounded form too. + +[END ARG] + function Copy (Source : Vector; Capacity : Count_Type := 0) return Vector; -The semantics of Assign are as follows. If Target denotes the same -object as Source, the operation does nothing. If Source length is -greater than Target capacity, then the operation raises Storage_Error. -Otherwise, it clears Target and appends each element in Source to -Target. +Returns a vector whose elements match the active 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. + +[ARG] -[ARG]: We need to decide what exception to raise if Source.Length is -greater then Target.Capacity. I think Storage_Error makes the most -sense, but a case could be made for Constraint_Error. Also, we need to -decide whether the check precedes the clear (which would prevent -side-effect if check fails). - -The semantics of Copy is as follows. The function declares a bounded -vector object (call it the Target) whose capacity is the maximum of -Source.Length and the Capacity argument, then appends each element of -Source to Target, and finally returns the Target object. - -[ARG]: Is this over-specified? - -[ARG]: Should append Append, Insert, etc, say what happens if vector -length equals vector capacity? - -[ARG]: Is there anything we want to say about the relationship between -the range of Index_Type and vector capacity? It's possible to declare a -vector object with a capacity smaller than the range of the index -subtype (and this makes sense for types as Positive, etc), but it's also -possible to declare a vector object with a capacity larger than the -range -- but we could never even add those elements, since the maximum -vector length is determined by the range of the index subtype. Should -we allow this? [END ARG] - -The semantics of Move are as follows. If Target denotes the same object -as Source, the operation does nothing. If Source is busy, then it raises -Program_Error. If Source.Length is greater than Target.Capacity, then -it raises Storage_Error. Otherwise, the operation clears Target, then -copies (not moves -- which is not possible for a bounded form) elements -from Source to Target, and finally clears Source. - -[ARG]: What exception when Src.Len > Tgt.Cap? - -[ARG]: For Vector'Read, do we need to specify what happens if the number -of elements in the stream is larger than the capacity of the vector -object? I explicitly check, the same as for Insert et al. - -The semantics of Reserve_Capacity is as follows. If the specified -Capacity is larger than the Container.Capacity, then it raises -Storage_Error. Otherwise, the operation does nothing. - -[ARG]: Is this the correct exception? - -The semantics of Set_Length are as follows. If Length is greater than -the Container.Capacity, then it raises Storage_Error. If Container is -busy, then it raises Program_Error. Otherwise it sets the container -length to the specified value. - -[ARG] What exception when Len > Container.Cap? Also, do we need a check -to ensure that the new length (really, the value returned by Last_Index) -is within the range of the index subtype? (This also applies to -To_Vector.) +OK to say above "...who elements match the active elements of Source"? +[END ARG] -Bounded Doubly-Linked List +[ARG] + +DO WE ADD ASSIGN AND COPY OPS TO UNBOUNDED FORM? +(see above - I think yes) + +If Assign and Copy really are new operations for the unbounded (and +bounded) forms, then where do these descriptions go: A.18 or somewhere +else? + +[END ARG] + +[ARG] + +FOR BOUNDED FORM: DECLARE A CAPACITY_SUBTYPE FOR BOUNDED VECTOR +FOR UNBOUNDED CASE TOO + +USE SUBTYPE IN COPY, RES_CAP, etc + +TODO: I don't know how to declare this subtype + +It's supposed to be + + subtype Capacity_Subtype is Count_Type range 0 .. <expression>; + +The intent was to prevent a vector object from having a capacity +greater than the number of values in the index subtype, e.g. + + type IT is range 0 .. 5; + type ET is ...; + package P is new Bounded_Vectors (IT, ET); + + V : P.Vector (10); -- only V[0] .. V[5] are accessible + +Would this work? -The bounded doubly-linked list differs from the unbounded list as follows. + subtype Capacity_Subtype is Count_Type + range 0 .. Count_Type'Max (0, + Index_Type'Pos (Index_Type'Last) - + Index_Type'Pos (Index_Type'First) + 1); -The package is named Ada.Containers.Bounded_Doubly_Linked_Lists. +The problem here is the instantiation: + package P is new Bounded_Vectors (Natural, ET); + +Subtype Natural has more values in the type than Count_Type'Last. + +Another option is to raise Constraint_Error (or whatever) at the point +of declaration of the object -- but that won't work either, since +the bounded forms aren't controlled. + +If there were a way to return the count of the number of values in the +type, then the user could pass that as the capacity, and we could +leave the declaration of the descriminant as-is: + + V : P.Vector (IT'Value_Count); -- IT'Value_Count = 6 + +[END ARG] + + +[ARG] + + procedure Move (Target : in out Vector; Source : in out Vector); + +My notes say: + +RE-WRITE UNBOUNDED FORM TO INCLUDE A CALL TO RES_CAP, which means we +could reuse the wording for unbounded form, therefore we don't need to +say anything special here. + +Here's what the RM says now: + + "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." + +We change add a call to Reserve_Capacity to that description, subject +to the following constraints: + +(1) In the bounded form, if the source length is greater than target +capacity, we could prefer to raise Capacity_Error immediately (instead +of clearning target as a side effect). + +(2) In the unbounded form, we prefer to clear first, and then reserve +capacity. If you do in the other way around then the existing items +are copied (in the reserve) and then immediately deleted (in the +clear). Perhaps we only have to require the final effect (no items, +and such-and-such capacity), but merely describe it in terms of a +reserve followed by a clear. + +With that in mind, here's the revised description: + + "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." + +If the original description of the Move operation is modified as above +for the unbounded form, then there's probably nothing else we need to +say for the bounded form (since Reserve_Capacity does what we want +here). + +[END ARG] + +[ARG] + +My notes from Portland say: + +NEED IMPL ADVICE TO SAY THAT MOVE MUST COPY. + +That's necessary because the description of the unbounded form (see +RM05 A.18.2 (261/2)) says: + + "Move should not copy elements, and should minimize copying of + internal data structures." + +This needs to be modified. Do we write distinct implementation advice +for both unbounded and bounded forms? Or can we leave it as is: +that's implementation advice for the unbounded form (only), and we +need not say anything for the bounded case. + +Alternatively, if this implementation advice is supposed to be general +enough to apply to both forms, then we could qualify the advice by +saying: + + "For the unbounded form, Move should not copy elements, and should + minimize copying of internal data structures." + +[END ARG] + + procedure Reserve_Capacity + (Container : in out Vector; + Capacity : Capacity_Subtype); + +If the specified Capacity is larger than the Container.Capacity, then +Reserve_Capacity raises Capacity_Error. Otherwise, the operation has +no effect. + +[ARG] + +Does the bounded form get a distinct description for Reserve_Capacity? +The Reserve_Capacity operation for the unbounded form does not raise +Capacity_Error. + +More generally, no operations for the unbounded forms raise +Capacity_Error. Do we need to specify this distinct behavior of the +bounded forms? + +[END ARG] + + +Bounded Doubly-Linked List + +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 internal storage is allocated statically. + +Static Semantics + +The declaration of the generic library package +Containers.Bounded_Doubly_Linked_Lists has the same contents as +Containers.Doubly_Linked_Lists except: + The package has Pure categorization. The list container type is declared with a discriminant that specifies the capacity, as follows: type List (Capacity : Count_Type) is tagged private; + +[ARG] -Immediately following the declaration of operation Clear, the following -pair of operations are declared: +Here's what I have for Assign: procedure Assign (Target : in out List; Source : List); + "If Target denotes the same object as Source, the operation has no + effect. If Source length is greater than Target capacity, then the + operation raises Capacity_Error, and Target is not modified. + Otherwise, it clears Target, and then each element of Source is + assigned to the matching element of Target." + +The issue is that there's no Reserve_Capacity operation for lists, so +we can't use the trick as we did for vectors to write a description +that works for both the unbounded and bounded forms. Do we write +distinct descriptions of Assign for the unbounded vs. bounded cases? + +[END ARG] + function Copy (Source : List; Capacity : Count_Type := 0) return List; -The semantics of Assign are as follows. If Target denotes the same -object as Source, the operation does nothing. If Source length is -greater than Target capacity, then the operation raises Storage_Error. -Otherwise, it clears Target and appends each element in Source to -Target. +Returns a list whose match the elements of Source. 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 is at least the +specified value. Otherwise, the operation raises Capacity_Error. + + procedure Move (Target : in out List; Source : in out List); -[ARG]: Perhaps we can consolidate the descriptions of Assign and Copy into a -single place, so we only have to describe these operations once. +Equivalent to Target.Assign (Source) followed by Source.Clear. -The semantics of Copy is as follows. The function declares a bounded list -object (call it the Target) whose capacity is the maximum of Source.Length and -the Capacity argument, then appends each element of Source to Target, and -finally returns the Target object. - -The semantics of Move are as follows. If Target denotes the same object -as Source, the operation does nothing. If Source is busy, then it raises -Program_Error. If Source.Length is greater than Target.Capacity, then -it raises Storage_Error. Otherwise, the operation clears Target, then -copies (not moves -- which is not possible for a bounded form) elements -from Source to Target, and finally clears Source. - -[ARG]: This isn't really how it's done. Really, it copies an element from -source to target, and then (assuming the assignment succeeds) unlinks it from -source. This process repeats until the source list is exhausted. I don't know -how much or how little needs to be specified. - - -[ARG]: -Do we need to state this explicitly: -(Swap_Links doesn't change) -(Splice with one container also doesn't change) -[END ARG]. +[ARG] + +Will this description suffice for both the unbounded and bounded +forms? + +[END ARG] + +[ARG] -The semantics of +RM05 A.18.3 (162/2) says: + + "Move should not copy elements, and should minimize copying of + internal data structures." + +As with the vector (and other containers), we need to decide what to +say here as implementation advice. + +[END ARG] + +[END ARG] procedure Splice (Target : in out List; Before : Cursor; Source : in out List); -differ from the unbounded form as follows. All elements of Source are copied -(preserving their order) to Target, at the position immediately preceeding -Before, and then deleted from Source. (Moving elements from Source is not -possible for a bounded from, since storage for nodes is associated with the -container object.) - -[ARG]: We probably don't want to overspecify here, since we want to allow one -element at a time to be copied to the target and then immediately deleted from -source. [END ARG] +If the sum of the Target length and Source length is greater than the +Target capacity, then Splice raises Capacity_Error. Otherwise the +elements from Source are moved to Target, immediately preceding +position Before. -The semantics of +[ARG] + +We say "... are moved to ..." implying a call to Move. Do we need to +say that explicitly? + +[END ARG] procedure Splice (Target : in out List; @@ -227,112 +355,131 @@ Source : in out List; Position : in out Cursor); -differ from the unbounded form as follows. The element of Source designated by -Position is copied to Target, at the position immediately preceeding Before, -and then deleted from Source. On return, cursor Position designates the -newly-inserted element of Target. - -[ARG]: We might not need to bring this up at all, for either version of splice. -We do say in the RM that the elements are "removed from Source and moved to -Target", but you could interpret that liberally for our purposes here, to mean -that the elements are "removed from Source and copied to Target". [END ARG] +If the Target length equals the Target capacity, then Splice raises +Capacity_Error. Otherwise the element of Source designated by +Position is moved to Target, immediately preceeding position Before. Bounded Hashed Map - -The bounded hashed map differs from the unbounded hashed map as follows. -The package is named Ada.Containers.Bounded_Hashed_Maps. +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 internal storage is allocated statically. + +Static Semantics + +The declaration of the generic library package +Containers.Bounded_Hashed_Maps has the same contents as +Containers.Hashed_Maps except: The package has Pure categorization. The container type is declared with a discriminant that specifies both -the capacity (number of elements) and modulus (length of buckets array), -as follows: +the capacity (number of elements) and modulous (number of distinct +hash values) of the hash table as follows: type Map (Capacity : Count_Type; Modulus : Hash_Type) is tagged private; -The semantics of Reserve_Capacity is as follows. If the specified -Capacity is larger than the Container.Capacity, then it raises -Storage_Error. Otherwise, the operation does nothing. - -[ARG] Actually, I think this has the same behavior as the unbounded form -(since in principle the unbounded form could also raise an exception "if -the specified capacity is larger than the container capacity". Since -this API is just supposed to specify how the bounded form differs from -the unbounded form, then do we need to mention Reserve_Capacity here? -[END ARG] + procedure Reserve_Capacity + (Container : in out Map; + Capacity : Count_Type); -Immediately following the declaration of operation Clear, the following -pair of operations are declared: +If the specified Capacity is larger than the Container.Capacity, then +it raises Capacity_Error. Otherwise, the operation has no effect. procedure Assign (Target : in out Map; Source : 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. +Otherwise, it clears Target and inserts each key/element pair of +Source into Target. + +[ARG] + +This is written very similar (i.e. in terms of Reserve_Capacity) to +the description of Assign for the vector (with the intent that it work +for both unbounded and bounded forms). Whatever we decide for vector +should probably apply here as well. + +Note also we say "If Source length is greater than Target capacity, +then Reserve_Capacity is called...". Do we need to bother with the +if-clause? Reserve_Capacity is allowed to return more than requested, +so the post-condition would be satified no matter what. + +[END ARG] + + function Copy (Source : Map; Capacity : Count_Type := 0; Modulus : Hash_Type := 0) return Map; -[ARG] Need ruling about whether the formal parameter should be "Source" -or "Container". +Returns a map with key/element pairs copied from Source, and having a +capacity and modulus determined as follows. 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 least the specified +value; 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 argument. -The semantics of Assign are as follows. If Target denotes the same -object as Source, the operation does nothing. If Source length is -greater than Target capacity, then the operation raises Storage_Error. -Otherwise, it clears Target and inserts each key/element pair of Source -into Target. +[ARG] -The semantics of Copy are as follows. The function declares a bounded -hashed map object (call it the Target) whose capacity is the maximum of -Source.Length and the Capacity argument, and a modulus determined as -follows. If the Modulus parameter is 0, then the Target's modulus is -the value returned by a call of function Default_Modulus with the -capacity specified as above; otherwise the Target's modulus is the value -of the actual parameter. The operation then inserts each key/element -pair of Source into Target, and finally returns the Target object. +We say "... pairs copied from Source ..." above: is this too +tautological? -[ARG] Another way to say that last sentence is: +[END ARG] -"The operation then calls Target.Assign (Source), and finally returns -the Target object." + procedure Move (Target : in out Map; Source : in out Map); -Any preference? [END ARG] +Equivalent to Target.Assign (Source) followed by Source.Clear. -The semantics of Move are as follows. If Target denotes the same object -as Source, the operation does nothing. If Source is busy, then it raises -Program_Error. If Source.Length is greater than Target.Capacity, then -it raises Storage_Error. Otherwise, the operation clears Target, then -copies (not moves -- which is not possible for a bounded form) the -key/element pairs from Source to Target, and finally clears Source. +[ARG] +Here we describe Move in terms of Assign (which is in turn described +in terms of Reserve_Capacity). Should we describe Move directly in +terms of Reserve_Capacity, instead of in terms of Assign? + +[END ARG] + + [ARG] -The implementation advice in RM05 A.18.4 says: + +Make this an implementation note? -83/2 Move should not copy elements, and should minimize copying of -internal data structures. +KNUTH SAYS YOU SHOULD GOLDEN RATIO FOR LOAD FACTOR +SEE JOHN'S BOOK FOR SPECIFIC REF -Do we need some new implementation advice somewhere? [END ARG] -Immediately following operation Iterate, the following operation is -declared: function Default_Modulus (Capacity : Count_Type) return Hash_Type; -Default_Modulus returns the length of a buckets array that would be -proper for hashing the given capacity (maximum number of elements). This -is useful for specifying descriminant values for the declaration of a -bounded hashed map object. +Default_Modulus returns an implementation-defined value for the length +of the buckets array (number of distinct hash values) for hashing the +given capacity (maximum number of elements). -[ARG]: Should be define "proper"? +[ARG] +Use of "implementation-defined" is OK here? -Bounded Ordered Map +[END ARG] -The bounded ordered map differs from the unbounded ordered map as -follows. -The package is named Ada.Containers.Bounded_Ordered_Maps. +Bounded Ordered Map + +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 internal storage is allocated statically. + +Static Semantics + +The declaration of the generic library package +Containers.Bounded_Ordered_Maps has the same contents as +Containers.Ordered_Maps except: The package has Pure categorization. @@ -341,101 +488,125 @@ type Map (Capacity : Count_Type) is tagged private; -Immediately following the declaration of operation Clear, the following -pair of operations are declared: - procedure Assign (Target : in out Map; Source : Map); +If Target denotes the same object as Source, the operation has no +effect. If Source length is greater than Target capacity, then the +operation raises Capacity_Error. Otherwise, it clears Target and +inserts each key/element pair of Source into Target. + +[ARG] + +This is similar to the case of lists (no Reserve_Capacity). + +[END ARG] + + function Copy (Source : Map; - Capacity : Count_Type := 0; - Modulus : Hash_Type := 0) return Map; + Capacity : Count_Type := 0) return Map; -The semantics of Assign are as follows. If Target denotes the same -object as Source, the operation does nothing. If Source length is -greater than Target capacity, then the operation raises Storage_Error. -Otherwise, it clears Target and inserts each key/element pair of Source -into Target. - -The semantics of Copy are as follows. The function declares a bounded -ordered map object (call it the Target) whose capacity is the maximum of -Source.Length and the Capacity parameter. The operation then inserts -each key/element pair of Source into Target, and finally returns the -Target object. - -The semantics of Move are as follows. If Target denotes the same object -as Source, the operation does nothing. If Source is busy, then it raises -Program_Error. If Source.Length is greater than Target.Capacity, then -it raises Storage_Error. Otherwise, the operation clears Target, then -copies (not moves -- which is not possible for a bounded form) the -key/element pairs from Source to Target, and finally clears Source. +Returns a map with key/element pairs copied from Source, and having a +capacity determined as follows. 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. +[ARG] -Bounded Hashed Set +My notes say: + +WE DON'T HAVE RES_CAP, SO WE NEED LIST OF OPS THAT MUST ADD CAP CHECK + +Does this still apply? + +[END ARG] + -The bounded hashed set differs from the unbounded hashed set as follows. + procedure Move (Target : in out Map; Source : in out Map); -The package is named Ada.Containers.Bounded_Hashed_Sets. +Equivalent to Target.Assign (Source) followed by Source.Clear. + +Bounded Hashed Set + +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 internal storage is allocated statically. + +Static Semantics + +The declaration of the generic library package +Containers.Bounded_Hashed_Sets has the same contents as +Containers.Hashed_Sets except: + The package has Pure categorization. The container type is declared with a discriminant that specifies both -the capacity (maximum number of elements) and modulus (length of buckets -array), as follows: +the capacity (number of elements) and modulous (number of distinct +hash values) of the hash table as follows: type Set (Capacity : Count_Type; Modulus : Hash_Type) is tagged private; + -The semantics of Reserve_Capacity is as follows. If the specified -Capacity is larger than the Container.Capacity, then it raises -Storage_Error. Otherwise, the operation does nothing. + procedure Reserve_Capacity + (Container : in out Map; + Capacity : Count_Type); -Immediately following the declaration of operation Clear, the following -pair of operations are declared: +If the specified Capacity is larger than the Container.Capacity, then +it raises Capacity_Error. Otherwise, the operation has no effect. procedure Assign (Target : in out Set; Source : 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. +Otherwise, it clears Target and inserts each element of Source into +Target. + + function Copy (Source : Set; Capacity : Count_Type := 0; Modulus : Hash_Type := 0) return Set; -The semantics of Assign are as follows. If Target denotes the same -object as Source, the operation does nothing. If Source length is -greater than Target capacity, then the operation raises Storage_Error. -Otherwise, it clears Target and inserts (a copy of) each element of -Source into Target. +Returns a set with elements copied from Source, and having a capacity +and modulus determined as follows. 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. 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 argument. -The semantics of Copy are as follows. The function declares a bounded -hashed set object (call it the Target) whose capacity is the maximum of -Source.Length and the Capacity argument, and a modulus determined as -follows. If the Modulus parameter is 0, then the Target's modulus is -the value returned by a call of function Default_Modulus with the -capacity specified as above; otherwise the Target's modulus is the value -of the actual parameter. The operation then inserts (a copy of) each -element of Source into Target, and finally returns the Target object. - -The semantics of Move are as follows. If Target denotes the same object -as Source, the operation does nothing. If Source is busy, then it raises -Program_Error. If Source.Length is greater than Target.Capacity, then -it raises Storage_Error. Otherwise, the operation clears Target, then -copies (not moves -- which is not possible for a bounded form) the -elements from Source to Target, and finally clears Source. + procedure Move (Target : in out Set; Source : in out Set); -Immediately following operation Iterate, the following operation is -declared: +Equivalent to Target.Assign (Source) followed by Source.Clear. function Default_Modulus (Capacity : Count_Type) return Hash_Type; -Default_Modulus returns the length of a buckets array that would be -proper for hashing the given capacity (maximum number of elements). This -is useful for specifying descriminant values for the declaration of a -bounded hashed set object. +Default_Modulus returns an implementation-defined value for the length +of the buckets array (number of distinct hash values) for hashing the +given capacity (maximum number of elements). +[ARG] -Bounded Ordered Set +Use of "implementation-defined" is OK here? -The bounded ordered set differs from the unbounded ordered set as -follows. +[END ARG] + + +Bounded Ordered Set -The package is named Ada.Containers.Bounded_Ordered_Sets. +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 internal storage is allocated statically. + +Static Semantics + +The declaration of the generic library package +Containers.Bounded_Ordered_Sets has the same contents as +Containers.Ordered_Sets except: The package has Pure categorization. @@ -444,42 +615,36 @@ type Set (Capacity : Count_Type) is tagged private; -Immediately following the declaration of operation Clear, the following -pair of operations are declared: - procedure Assign (Target : in out Set; Source : Set); - function Copy (Source : Set; - Capacity : Count_Type := 0; - Modulus : Hash_Type := 0) return Set; +If Target denotes the same object as Source, the operation has no +effect. If Source length is greater than Target capacity, then the +operation raises Capacity_Error. Otherwise, it clears Target and +inserts each element of Source into Target. -The semantics of Assign are as follows. If Target denotes the same -object as Source, the operation does nothing. If Source length is -greater than Target capacity, then the operation raises Storage_Error. -Otherwise, it clears Target and inserts (a copy of) each element of -Source into Target. + function Copy (Source : Set; + Capacity : Count_Type := 0) return Set; -The semantics of Copy are as follows. The function declares a bounded -ordered set object (call it the Target) whose capacity is the maximum of -Source.Length and the Capacity parameter. The operation then inserts (a -copy of) each element Source into Target, and finally returns the Target -object. - -The semantics of Move are as follows. If Target denotes the same object -as Source, the operation does nothing. If Source is busy, then it raises -Program_Error. If Source.Length is greater than Target.Capacity, then -it raises Storage_Error. Otherwise, the operation clears Target, then -copies (not moves -- which is not possible for a bounded form) the -elements from Source to Target, and finally clears Source. +Returns a set with elements copied from Source, and having a capacity +determined as follows. 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. + procedure Move (Target : in out Set; Source : in out Set); +Equivalent to Target.Assign (Source) followed by Source.Clear. Source +is cleared. Protected Queues -[ARG] Is parameter name "Q" OK? Should this be "Container"? +[ARG] +Should we have priority queues too? (Steve B. suggested something +like fibbonacci heaps as implementation data structure.) +[END ARG] -The generic library package Containers.Queues has the following -declaration: +The language-defined generic package Containers.Queues provides +interface type Queue, and a set of operations for that type. generic type Element_Type is private; @@ -489,85 +654,96 @@ type Queue is synchronized interface; - procedure Enqueue (Q : in out Queue; New_Item : Element_Type) - is abstract; + procedure Enqueue + (Container : in out Queue; + New_Item : Element_Type) is abstract; pragma Implemented (Enqueue, By_Entry); - procedure Dequeue (Q : in out Queue; Element : out Element_Type) - is abstract; + procedure Dequeue + (Container : in out Queue; + Element : out Element_Type) is abstract; pragma Implemented (Dequeue, By_Entry); - function Is_Full (Q : Queue) return Boolean is abstract; + function Is_Empty (Container : Queue) return Boolean is abstract; - -- [ARG] What about: - -- - -- procedure Enqueue - -- (Q : in out Queue; - -- New_Item : in Element_Type; - -- Existing : out Count_Type) is abstract; - -- - -- procedure Dequeue - -- (Q : in out Queue; - -- Element : out Element_Type; - -- Remaining : out Count_Type) is abstract; - -- - -- function Length (Q : Queue) return Count_Type is abstract; - -- - -- [END ARG] + function Is_Full (Container : Queue) return Boolean is abstract; end Ada.Containers.Queues; Interface Queue specifies a first-in, first-out queue. + + procedure Enqueue + (Container : in out Queue; + New_Item : Element_Type) is abstract; + +Copies New_Item onto the tail of the queue. If Is_Full is True, then +Enqueue waits on the entry for storage to become available. + + procedure Dequeue + (Container : in out Queue; + Element : out Element_Type) is abstract; + +Removes the element at the head of the queue, and returns a copy of +the element. Is Is_Empty is True, then Dequeue waits on the entry for +an item to become available. -Enqueue copies New_Item onto the back of the queue. If Is_Full is True, -then Enqueue waits on the entry for storage to become available. + function Is_Empty (Container : Queue) return Boolean is abstract; -Dequeue removes the element at the front of the queue, and returns a -copy of the element. Is Is_Empty is True, then Dequeue waits on the -entry for an item to become available. +Returns an indication of whether the queue contains items. -Is_Empty returns an indication of whether the queue contains items. + function Is_Full (Container : Queue) return Boolean is abstract; -Is_Full returns an indication of whether the queue is able to contain -more items. +Returns an indication of whether the queue is able to contain more +items. -The generic library package Containers.Queues.Bounded has the following -declaration: +Bounded Queues +The language-defined generic package Containers.Bounded_Queues +provides type Queue, which implements the interface type +Containers.Queues.Queue. + +with Ada.Containers.Queues; generic -package Queues.Bounded is -- [ARG]: Should this be Generic_Bounded? - pragma Pure; -- [ARG] OK? (Can PO be pure?) + with package Queues is new Ada.Containers.Queues (<>); + +package Ada.Containers.Bounded_Queues is + pragma Pure; type Queue (Capacity : Count_Type) is synchronized new Queues.Queue with private; private - -- not specified + -- not specified by the language -end Queues.Bounded; +end Ada.Containers.Bounded_Queues; The bounded queue specifies a queue with finite capacity. Is_Full returns True when the length (the current number of items) equals the capacity. +Unbounded Queues -The generic library package Containers.Queues.Unbounded has the following -declaration: +The language-defined generic package Containers.Unbounded_Queues +provides type Queue, which implements the interface type +Containers.Queues.Queue. +with Ada.Containers.Queues; generic -package Queues.Unbounded is -- [ARG]: Should this be Generic_Unbounded? - pragma Preelaborate; -- [ARG] OK? + with package Queues is new Ada.Containers.Queues (<>); +package Ada.Containers.Unbounded_Queues is + pragma Preelaborate; + type Queue is synchronized new Queues.Queue with private; private - -- not specified + -- not specified by the language -end Queues.Unbounded; +end Ada.Containers.Unbounded_Queues; The unbounded queue specifies a queue with no specified maximum capacity. Is_Full always returns False. Enqueue will never block @@ -576,7 +752,8 @@ Generic_Sort -The following generic sort procedure is defined: +The generic library procedure Containers.Generic_Sort has the +following declaration: generic type Index_Type is (<>); @@ -585,24 +762,22 @@ procedure Ada.Containers.Generic_Sort (First, Last : Index_Type'Base); pragma Pure (Ada.Containers.Generic_Sort); - -Reorders the elements of an anonmyous array-like container, over the -range First .. Last, such that the elements are sorted smallest first as -determined by the generic formal Less function provided. Generic formal -Less compares the container elements having the given indices, and -generic formal Swap exchanges the values of the indicated container -elements. Any exception raised during evaluation of Less or Swap is -propagated. - -The actual function for the generic formal function Less 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 ordering -relationship, that is, be irreflexive, asymmetric, and transitive; it -should not modify the container. If the actual for Less behaves in some -other manner, the behavior of the instance of Generic_Sort is -unspecified. How many times Generic_Sort calls Less or Swap is -unspecified. +Reorders the elements of an indexable container, over the range First +.. Last, such that the elements are sorted smallest first as +determined by the generic formal Less function provided. Generic +formal Less compares the container elements having the given indices, +and generic formal Swap exchanges the values of the indicated +container elements. Any exception raised during evaluation of Less or +Swap is propagated. + +The actual function for the generic formal function Less 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 +Container. If the actual for Less behaves in some other manner, the +behavior of Generic_Sort is unspecified. How many times the +Generic_Sorts calls Less or Swap is unspecified. Case-Insensitive Operations

Questions? Ask the ACAA Technical Agent