CVS difference for ai05s/ai05-0001-1.txt
--- 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