CVS difference for ais/ai-20302.txt
--- ais/ai-20302.txt 2004/02/21 03:07:27 1.3
+++ ais/ai-20302.txt 2004/04/23 03:50:22 1.4
@@ -1,4 +1,4 @@
-!standard A.17 04-02-18 AI95-00302-03/02
+!standard A.17 04-04-12 AI95-00302-03/03E
!class amendment 04-01-14
!status work item 04-01-14
!status received 04-01-14
@@ -84,12 +84,17 @@
toward the front the cost of vector insertion approaches linear time
complexity. A vector supports constant-time random access of elements.
-Vectors specify positions via a discrete index subtype. All of the associative
-containers specify positions using a cursor,
-which is similar to an access type in that designates a node of internal
-storage. Note that unlike a discrete index, a cursor always
-designates the node that contains an element; it never designates an
-element directly. (There's a special selector operation for that.)
+A linked-list is a sequence container that provides constant-time
+insertion and deletion at any position, but does not provide random
+access. The list container is doubly-linked, having nodes with next and
+previous pointers, and thus supports both forward and reverse iteration.
+
+All of the containers specify positions using a cursor,
+which is similar to an access type in that it designates an element. It
+is not (necessarily) implemented as an access type, so access to the element
+is through a selector function. Many cursor operations are common to all
+containers. Containers also support operations specific to that container;
+for instance, vectors also specify positions via an integer index subtype.
The associative containers order their elements by key. A map has an
explicit key type, but with a set the key is implicit in the element
@@ -103,13 +108,12 @@
The set associative container maintains elements in sort order. Insertions
and searches have O(log N) time complexity even in the worst case.
-For the map containers, there are forms that use types String and
-Wide_String specifically as the key. Using a string as the key of a map
-container is so common in nearly every application that the library
-provides this directly.
+All of the containers have alternate forms that accept an element type that is
+indefinite. The indefinite hashed maps also accept an indefinite key type,
+allowing (for example) type String to be used as the generic actual key type.
-There is also a package of routines for managing case-insensitive strings,
-and library-level subprograms for returning the hash value of strings.
+There are also library-level subprograms for returning the hash value of
+strings, and generic procedures for sorting an array.
The design of these packages follow the principle that they can be implemented
in Ada without any special implementation-specific magic. This is important,
@@ -129,25 +133,17 @@
!wording
-Add Ada.Strings.Hash, Ada.Strings.Unbounded.Hash, and
- Ada.Strings.Case_Insensitive to A.4.7(29).
+Add Ada.Strings.Hash and Ada.Strings.Unbounded.Hash to A.4.7(29).
-[This gives us Wide_ versions of these packages and functions.]
+[This gives us Wide_ versions of these functions.]
-A.4.8 Hashing and String Comparison
+A.4.8 String Hashing
Static Semantics
-The following library-level subprograms and packages are defined:
+The following library-level subprograms are defined:
-[Open Issues: Should Ada.Strings.Hash and Ada.Strings.Case_Insensitive be
-Ada.Strings.Fixed.Hash and Ada.Strings.Fixed.Case_Insensitive instead?
-Should there be a Ada.Strings.Unbounded.Case_Insensitive?
-Should there be Ada.Strings.Bounded.Hash and Ada.Strings.Bounded.Case_Insensitive?
-Note that the last two are generic with a formal package parameter, which is
-ugly.]
-
with Ada.Containers;
function Ada.Strings.Hash (Key : String) return Containers.Hash_Type;
pragma Pure (Ada.Strings.Hash);
@@ -157,44 +153,17 @@
Containers.Hash_Type;
pragma Pure (Ada.Strings.Unbounded.Hash);
-with Ada.Containers;
-package Ada.Strings.Case_Insensitive is
- pragma Pure (Case_Insensitive);
-
- function "=" (Left, Right : String) return Boolean;
- function ">" (Left, Right : String) return Boolean;
- function ">=" (Left, Right : String) return Boolean;
- function "<" (Left, Right : String) return Boolean;
- function "<=" (Left, Right : String) return Boolean;
-
- function Hash (Key : String) return Containers.Hash_Type;
-end Ada.Strings.Case_Insensitive;
-
-[Open Issue: Matt points out that a naive user might with and use this package
-expecting to get these operations. But of course, the ones in Standard will
-still be used. (Of course, dot notation will work, but no one *wants* to do
-that for operator calls). Do we have to give these names rather than operator
-symbols as they're not primitive for the type?]
-
function Ada.Strings.Hash (Key : String) return Containers.Hash_Type;
Return an implementation-defined value which is a function of the value of Key.
-If A and B are strings, then if A = B, Hash(A) shall equal Hash(B).
+If A and B are strings such that A equals B, Hash(A) equals Hash(B).
function Ada.Strings.Unbounded.Hash (Key : Unbounded_String) return
Containers.Hash_Type;
Return an implementation-defined value which is a function of the value of Key.
-If A and B are unbounded strings, then if A = B, Hash(A) shall equal Hash(B).
+If A and B are unbounded strings such that A equals B, Hash(A) equals Hash(B).
-The operations in Ada.Strings.Case_Insensitive return the value of a call on
-the corresponding function of type String, with all operands the result of
-calling Characters.Handling.To_Upper on the operands. For instance,
-Strings.Case_Insensitive."<" is equivalent to
-"<"(Characters.Handling.To_Upper(Left), Characters.Handling.To_Upper(Right)).
-
-AARM Note: Please don't implement it this way!
-
Implementation Advice
The various Hash functions should be good hash functions, returning
@@ -222,10 +191,20 @@
calls "iterators" are called "cursors" here.
The following major non-limited containers are provided:
- * (Expandable) Vectors of any non-limited definite type;
- * Sorted Sets of any non-limited definite type;
- * Hashed Maps keyed by any non-limited definite type containing any
-non-limited definite type.
+ * (Expandable) Vectors of any non-limited type;
+ * Doubly-linked Lists of any non-limited type;
+ * Ordered Sets of any non-limited type;
+ * Hashed Maps keyed by any non-limited type containing any
+non-limited type.
+
+Separate versions for definite element types are provided, as those can be
+implemented more efficiently.
+
+Each container includes a *cursor*, which is a reference to an element within
+a container. Cursors generally remain valid as long as the container exists and
+the element referenced is not deleted. Many operations on cursors are common to
+all of the containers. This makes it possible to write generic algorithms that
+work on any kind of container.
The containers packages are structured so that additional packages can be
added in the future. Indeed, we hope that these packages provide the basis
@@ -250,6 +229,36 @@
of containers when necessary, and containers can be passed between
partitions of a program.
+Finally, the language requires that equality of language-defined types
+compose "properly". This means that the version of "=" directly used by
+users is the same one that will be used in generics and in predefined equality
+operators of types with components of the containers and/or cursors. This
+prevents the abstraction from breaking unexpectedly.
+
+
+If a container's element type is controlled, the point at which the element
+is finalized will depend on the implementation of the container. We do not
+specify precisely where this will happen (it will happen no latter than the
+finalization of the container, of course) in order to give implementation's
+flexibility to cache, block, or split the nodes of the container. In particular,
+Delete does not necessarily finalize the element; the implementation may (or
+may not) hold the space for reuse. (The reference implementations show this
+well, as Delete for a Vector does not finalize the element, while Delete for
+an Ordered_Set does.)
+
+This is not likely to be a hardship, as the element type has to be non-limited.
+Types used to manage scarce resources generally need to be limited. Otherwise,
+the amount of resources needed is hard to control, as the language allows
+a lot of variation in the number or order of adjusts/finalizations. For
+common uses of non-limited controlled types such as managing storage, the
+types already have to manage arbitrary copies.
+
+The use of controlled type also brings up the possibility of failure of
+finalization (and thus deallocation) of an element. This is a "serious bug",
+as AI-179 puts it, so we don't try to specify what happens in that case.
+The implementation should propagate the exception, and should not damage
+the container (so that it can continue to be used without further error).
+
End AARM Text
A.17.1 The Package Containers
@@ -272,48 +281,46 @@
Hash_Type represents the range of the result of a hash function. Size_Type
represents the (potential or actual) size (number of elements) of a container.
-Implementation Requirements
+Implementation Advice
-Hash_Type'Modulus shall be at least as large as the smaller of
-System.Max_Binary_Modulus and 2**32.
+Hash_Type'Modulus should be at least 2**32. Size_Type'Last should be at least
+2**31-1.
-[Open Issue: Is this OK? We can't just say 2**32, as that might be a bad
-choice for the target (esp. a 24 bit machine!). And we don't want to insist
-on System.Max_Binary_Modulus on 64-bit machines -- that seems to be overkill.
-But we do want to give the user some guidance as to the range of this type.]
-
-Size_Type'Last shall be at least as large as the smaller of
-System.Max_Int and (2**31)-1.
-
-[Open Issue: Or we could just say
-Size_Type'Last shall be at least as large as Integer'Last.
-But that isn't quite as strong as the above.]
+AARM Note: This is not a requirement so that these types can be declared
+properly on machines with native sizes that are not 32 bits. For instance, a
+24-bit target could use 2**24 for Hash_Type'Modulus.
A.17.2 The Package Containers.Vectors
-The language-defined package Containers.Vectors provides a
-private type Vector_Type and a set of operations. A vector container
-allows insertion and deletion at any position, but it is specifically
-optimized for insertion and deletion at the back end of the container.
-A vector container also provides random access to its elements.
+The language-defined package Containers.Vectors provides a private type Vector
+and a set of operations. A vector container allows insertion and deletion at
+any position, but it is specifically optimized for insertion and deletion at
+the back end of the container. A vector container also provides random access
+to its elements.
A vector container object manages an unconstrained internal array, which
-expands as necessary as items are inserted. The "size" of a vector
-corresponds to the total length of the internal array, and the "length"
-of a vector corresponds to the number "active" elements in the internal
+expands as necessary as items are inserted. The *size* of a vector
+corresponds to the total length of the internal array, and the *length*
+of a vector corresponds to the number active elements in the internal
array.
-AARM Note:
+A vector container may contain *empty elements*. Empty elements do not have a
+defined value.
-Vectors are not intended to be sparse (that is, there are elements at all
-defined positions). If a sparse data structure is needed, use a Map.
+AARM Notes:
-[Open Issue: Should the above be a Note in the Standard?]
+Vectors are not intended to be sparse (that is, there are elements at all
+defined positions). Users are expected to use other containers (like a Map)
+when they need sparse structures (there is a Note to this effect at the
+end of this subclause).
+
+The internal array is a virtual structure. There is no requirement for the
+implementation to be a single contiguous array.
+End AARM Notes.
Static Semantics
-The library package Containers.Vectors has the following
-declaration:
+The library package Containers.Vectors has the following declaration:
generic
@@ -325,146 +332,267 @@
return Boolean is <>;
package Ada.Containers.Vectors is
+ pragma Preelaborate (Vectors);
- pragma Preelaborate;
-
pragma Assert (Index_Type'Base'First < Index_Type'First);
subtype Index_Subtype is Index_Type;
- type Vector_Type is private;
+ type Vector is private;
- function "=" (Left, Right : Vector_Type) return Boolean;
+ type Cursor is private;
- function Length (Vector : Vector_Type) return Size_Type;
+ Empty_Vector : constant Vector;
- function Is_Empty (Vector : Vector_Type) return Boolean;
+ No_Element : constant Cursor;
- procedure Clear (Vector : in out Vector_Type);
+ function To_Vector (Count : Size_Type) return Vector;
- procedure Swap (Left, Right : in out Vector_Type);
+ function To_Vector
+ (New_Item : Element_Type;
+ Count : Size_Type) return Vector;
- procedure Append (Vector : in out Vector_Type;
- New_Item : in Element_Type);
+ function "&" (Left, Right : Vector) return Vector;
- procedure Insert (Vector : in out Vector_Type;
- Before : in Index_Type'Base;
- New_Item : in Element_Type);
+ function "&" (Left : Vector;
+ Right : Element_Type) return Vector;
- procedure Insert (Vector : in out Vector_Type;
- Before : in Index_Type'Base;
- New_Item : in Element_Type;
- Count : in Size_Type);
+ function "&" (Left : Element_Type;
+ Right : Vector) return Vector;
- procedure Insert_Empty_Space
- (Vector : in out Vector_Type;
- Before : in Index_Type'Base;
- Count : in Size_Type);
+ function "=" (Left, Right : Vector) return Boolean;
- procedure Delete (Vector : in out Vector_Type;
- Index : in Index_Type'Base);
+ function Size (Container : Vector) return Size_Type;
- procedure Delete_Last (Vector : in out Vector_Type);
+ procedure Resize (Container : in out Vector;
+ Size : in Size_Type);
- procedure Delete (Vector : in out Vector_Type;
- First : in Index_Type'Base;
- Count : in Size_Type);
+ function Length (Container : Vector) return Size_Type;
- function Size (Vector : Vector_Type) return Size_Type;
+ function Is_Empty (Container : Vector) return Boolean;
- procedure Resize (Vector : in out Vector_Type;
- Size : in Size_Type);
+ procedure Clear (Container : in out Vector);
- function Front (Vector : Vector_Type) return Index_Type'Base;
+ function To_Cursor (Container : Vector;
+ Index : Index_Type'Base) return Cursor;
- function First (Vector : Vector_Type) return Index_Type;
+ function To_Index (Position : Cursor) return Index_Type'Base;
- function First_Element (Vector : Vector_Type)
- return Element_Type;
+ procedure Assign (Target : in out Vector;
+ Source : in Vector);
+
+ procedure Move (Target : in out Vector;
+ Source : in out Vector);
- function Last (Vector : Vector_Type) return Index_Type'Base;
+ procedure Insert (Container : in out Vector;
+ Before : in Index_Type'Base;
+ New_Item : in Vector);
- function Last_Element (Vector : Vector_Type)
+ procedure Insert (Container : in out Vector;
+ Before : in Cursor;
+ New_Item : in Vector);
+
+ procedure Insert (Container : in out Vector;
+ Before : in Cursor;
+ New_Item : in Vector;
+ Position : out Cursor);
+
+ procedure Insert (Container : in out Vector;
+ Before : in Index_Type'Base;
+ New_Item : in Element_Type;
+ Count : in Size_Type := 1);
+
+ procedure Insert (Container : in out Vector;
+ Before : in Cursor;
+ New_Item : in Element_Type;
+ Count : in Size_Type := 1);
+
+ procedure Insert (Container : in out Vector;
+ Before : in Cursor;
+ New_Item : in Element_Type;
+ Position : out Cursor;
+ Count : in Size_Type := 1);
+
+ procedure Prepend (Container : in out Vector;
+ New_Item : in Vector);
+
+ procedure Prepend (Container : in out Vector;
+ New_Item : in Element_Type;
+ Count : in Size_Type := 1);
+
+ procedure Append (Container : in out Vector;
+ New_Item : in Vector);
+
+ procedure Append (Container : in out Vector;
+ New_Item : in Element_Type;
+ Count : in Size_Type := 1);
+
+ procedure Insert_Space (Container : in out Vector;
+ Before : in Index_Type'Base;
+ Count : in Size_Type := 1);
+
+ procedure Insert_Space (Container : in out Vector;
+ Before : in Cursor;
+ Position : out Cursor;
+ Count : in Size_Type := 1);
+
+ procedure Set_Length (Container : in out Vector;
+ Length : in Size_Type);
+
+ procedure Delete (Container : in out Vector;
+ Index : in Index_Type'Base;
+ Count : in Size_Type := 1);
+
+ procedure Delete (Container : in out Vector;
+ Position : in out Cursor;
+ Count : in Size_Type := 1);
+
+ procedure Delete_First (Container : in out Vector;
+ Count : in Size_Type := 1);
+
+ procedure Delete_Last (Container : in out Vector;
+ Count : in Size_Type := 1);
+
+ function First_Index (Container : Vector) return Index_Type;
+
+ function First (Container : Vector) return Cursor;
+
+ function First_Element (Container : Vector)
return Element_Type;
- function Back (Vector : Vector_Type) return Index_Type'Base;
+ function Last_Index (Container : Vector) return Index_Type'Base;
+
+ function Last (Container : Vector) return Cursor;
+
+ function Last_Element (Container : Vector)
+ return Element_Type;
- function Element (Vector : Vector_Type;
- Index : Index_Type'Base)
+ function Element (Container : Vector;
+ Index : Index_Type'Base)
return Element_Type;
+ function Element (Position : Cursor) return Element_Type;
+
generic
- type Element_Access is access all Element_Type;
- function Generic_Element (Vector : Vector_Type;
- Index : Index_Type'Base)
- return Element_Access;
-
- procedure Replace_Element (Vector : in Vector_Type;
- Index : in Index_Type'Base;
- By : in Element_Type);
+ with procedure Process (Element : in out Element_Type) is <>;
+ procedure Generic_Update_by_Index (Container : in Vector;
+ Index : in Index_Type'Base);
generic
+ with procedure Process (Element : in out Element_Type) is <>;
+ procedure Generic_Update (Position : in Cursor);
+
+ procedure Replace_Element (Container : in Vector;
+ Index : in Index_Type'Base;
+ By : in Element_Type);
+
+ procedure Replace_Element (Position : in Cursor;
+ By : in Element_Type);
+
+ procedure Swap (Container : in Vector;
+ I, J : in Index_Type'Base);
+
+ procedure Swap (Container : in out Vector;
+ I, J : in Cursor);
+
+ generic
with function "<" (Left, Right : Element_Type)
return Boolean is <>;
- procedure Generic_Sort (Vector : in Vector_Type);
+ procedure Generic_Sort (Container : in Vector);
+
+ function Find (Container : Vector;
+ Item : Element_Type;
+ Index : Index_Type'Base := Index_Type'First)
+ return Index_Type'Base;
+
+ function Find (Container : Vector;
+ Item : Element_Type;
+ Position : Cursor := No_Element)
+ return Cursor;
+
+ function Reverse_Find (Container : Vector;
+ Item : Element_Type;
+ Index : Index_Type'Base :=
+ Index_Type'Pred (Index_Type'First))
+ return Index_Type'Base;
+
+ function Reverse_Find (Container : Vector;
+ Item : Element_Type;
+ Position : Cursor := No_Element)
+ return Cursor;
+
+ function Is_In (Item : Element_Type;
+ Container : Vector)
+ return Boolean;
+
+
+ function Next (Position : Cursor) return Cursor;
+
+ function Previous (Position : Cursor) return Cursor;
+
+ procedure Next (Position : in out Cursor);
+
+ procedure Previous (Position : in out Cursor);
+
+ function Has_Element (Position : Cursor) return Boolean;
+ generic
+ with procedure Process (Position : in Cursor) is <>;
+ procedure Generic_Iteration (Container : in Vector);
+
+ generic
+ with procedure Process (Position : in Cursor) is <>;
+ procedure Generic_Reverse_Iteration (Container : in Vector);
+
private
... -- not specified by the language
end Ada.Containers.Vectors;
-[Open issue: Should Index_Type be "(<>)" instead of "range <>"? The
-current version will not allow enumeration and modular index subtypes.
-Note that the assert will fail for enumeration and modular types (subtypes
-may work), so they're annoying at best. The Assert is needed as operations like
-Front and the value of Last for an empty Vector return
-Index_Type'Pred(Index_Type'First). Also note that this is not intended to be
-a sparse vector, so such types are less useful; if a sparse data structure is
-needed, use a map.]
-
-[Slightly Open issue: Several reviewers have complained about the use of
-the "_Type" suffix on the type names. That was originally retained when the
-names were changed because of all of the conflicts with parameter names.
-Of course, that can be easily worked around. However, there would also
-be a conflict with the functions Element and Key. Since these are going to
-be very common, we want a short, descriptive name for them, not something
-long-winded. OTOH, the formal parameter names will be used rarely, if at all.
-And we definitely can't use the same name for both (it's illegal). Thus, it is
-better to use the short names on the functions, and thus the "_Type" suffix
-is needed on at least the generic formal types.]
-
-[Open Issue: Should a vector have passive iterator(s), and if so, what should
-they look like? Note that for a vector, it is easier to write a for loop than
-a passive iterator instantiation, so these would mainly be for consistency.
-Matt suggested 4 (!) iterators of the form:
- generic
- with procedure Process (Element : in out Element_Type) is <>;
- procedure Generic_Iteration (Vector : in Vector_Type);
+Empty_Vector represents the empty vector container. It has a length of 0. If an
+object of type Vector is not otherwise initialized, it will be initialized to
+the same value as Empty_Vector.
-with constant (Process has an 'in' parameter), variable (like this), and
-reverse forms.
+No_Element represents a cursor that designates no element. If an object of type
+Cursor is not otherwise initialized, it will be initialized to the same
+value as No_Element.
-But these are not consistent with the other containers, which use Cursor_Type
-as the parameter to Process. To be consistent, we'd have to use:
+function To_Vector (Count : Size_Type) return Vector;
- generic
- with procedure Process (Index : in Index_Type) is <>;
- procedure Generic_Iteration (Vector : in Vector_Type);
+Returns a vector with a length of Count. The vector is filled with empty
+elements.
+
+
+function To_Vector
+ (New_Item : Element_Type;
+ Count : Size_Type) return Vector;
+
+Returns a vector with a length of Count, and elements initialized to the
+value New_Item.
+
+
+function "&" (Left, Right : Vector) return Vector;
+
+Returns a vector comprising the elements of Right appended to the
+elements of Left.
-which seems pretty silly. Or we could change all of the iterators to a form
-more like the one proposed above.
+function "&" (Left : Vector;
+ Right : Element_Type) return Vector;
-While a number of people are in favor of passive iterators, it's not clear
-that anyone had thought of the exact forms.]
+Returns a vector comprising the element Right appended to the elements
+of Left.
-If an object of type Vector_Type is not otherwise initialized, it
-will initialized with a size (internal array length) of 0.
+function "&" (Left : Element_Type;
+ Right : Vector) return Vector;
+Returns a vector comprising the element Right prepended to the elements
+of Left.
-function "=" (Left, Right : Vector_Type) return Boolean;
+function "=" (Left, Right : Vector) return Boolean;
+
If Left denotes the same object as Right, then this function returns
True. Otherwise if Left and Right have different lengths, then this
function returns False. Otherwise, it compares each element in Left to
@@ -472,216 +600,393 @@
operator. If element equality returns False, then this function returns
False; otherwise, this function returns True. Any exceptions raised
during evaluation of element equality are propagated.
+
+
+function Size (Container : Vector) return Size_Type;
-function Length (Vector : Vector_Type) return Size_Type;
+Returns the length of the internal array.
+
-The Length function returns the number of active elements in Vector.
+procedure Resize (Container : in out Vector;
+ Size : in Size_Type);
+If Size (Container) is equal to or greater than Size, the operation does
+nothing. Otherwise Resize sets the size of Container to a value which is
+at least the value Size, expanding the internal array to hold Size elements.
+Expansion will require allocation, and possibly copying and deallocation of
+elements. Any exceptions raised by these operations are propagated, leaving
+the container with at least the original Size, Length, and elements.
-function Is_Empty (Vector : Vector_Type) return Boolean;
+AARM Notes
-Equivalent to Length (Vector) = 0.
+Expanding the internal array can be done by allocating a new, longer array,
+copying the elements, and deallocating the original array. This may raise
+Storage_Error, or cause an exception from a controlled subprogram. We require
+that a failed Resize does not lose any elements if an exception occurs, but
+we do not require a specific order of evaluations or copying.
+This routine is used to preallocate the internal array to the specified
+size such that future Inserts do not require memory allocation overhead.
+Therefore, the implementation should allocate the needed memory to make that
+true at this point, even though the visible semantics could be preserved by
+waiting until the memory is needed.
-procedure Clear (Vector : in out Vector_Type);
+End AARM Notes
+function Length (Container : Vector) return Size_Type;
+
+The Length function returns the number of active elements in Container.
+
+
+function Is_Empty (Container : Vector) return Boolean;
+
+Equivalent to Length (Container) = 0.
+
+
+procedure Clear (Container : in out Vector);
+
Sets the length of Vector to 0. Its size does not change.
-procedure Swap (Left, Right : in out Vector_Type);
+function To_Cursor (Container : Vector;
+ Index : Index_Type'Base) return Cursor;
-Exchanges the internal array and element count of Left and Right.
+If the value of Index is not in the range First_Index (Container) .. Last_Index
+(Container), then Constraint_Error is propagated. Otherwise, a cursor
+designating the element currently at Index in Container is returned.
+
+
+function To_Index (Position : Cursor) return Index_Type'Base;
+
+If Position is No_Element, Constraint_Error is propagated. Otherwise, the
+index (within its containing vector) of the element designated by Cursor is
+returned.
+
+AARM Note: This implies that the index is determinable from a bare cursor
+alone. The basic model is that a vector cursor is implemented as a record
+containing an access to the vector container and a index value. This does
+constrain implementations, but it also allows all of the cursor operations
+to be defined in terms of the corresponding index operation (which should be
+primary for a vector). [Anyone that wants to change this is invited to rewrite
+this section first - ED]
+
+procedure Assign (Target : in out Vector;
+ Source : in Vector);
+
+If Target denotes the same object as Source, then the operation has no
+effect. Otherwise, Assign first calls Clear (Target), then Resize (Target,
+Length (Source)). It then assigns the active elements of Source to the
+corresponding positions in Target, and then sets the length of Target to
+the length of Source. Any exceptions raising during element assignment
+are propagated.
-procedure Append
- (Vector : in out Vector_Type;
- New_Item : in Element_Type);
+procedure Move (Target : in out Vector;
+ Source : in out Vector);
-Equivalent to Insert (Vector, Back (Vector), New_Item).
+If Target denotes the same object as Source, then the operation has no
+effect. If Length (Target) is greater than 0, then it raises Constraint_Error.
+Otherwise, the internal array is removed from Source (making its size 0) and
+moved to Target (making its size the original size of Source). The length of
+Target is set to the length of Source, and the length of Source is set to 0.
+AARM Note:
-procedure Insert
- (Vector : in out Vector_Type;
- Before : in Index_Type'Base;
- New_Item : in Element_Type);
+If Size (Target) /= 0, the previous internal array may need to be deallocated.
+We don't mention this explicitly, because it is covered by the "no memory
+loss" Implementation Requirement. If the deallocation raises an exception,
+the implementation should leave both Vectors in a consistent state (usually
+empty for Target and the original state for Source).
+
+
+procedure Insert (Container : in out Vector;
+ Before : in Index_Type'Base;
+ New_Item : in Vector);
+
+If Length(New_Item) is 0, then Insert does nothing. Otherwise, it calculates
+the new length *NL* as the sum of the current length and Length (New_Item); if
+the value of Last appropriate for length NL would be greater than
+Index_Type'Last then Constraint_Error is propagated. If the value of Before is
+not in the range First_Index (Container) .. Index_Type'Succ (Last_Index
+(Container)), then Constraint_Error is propagated.
+
+If the current vector size is less than or equal to the new length, Resize
+(Container, NL) is called to increase the vector size. Then Insert slides the
+elements in the range Before .. Last_Index (Container) up by Length(New_Item)
+positions, and then copies the elements of New_Item to the positions starting
+at Before. Any exceptions raised during the copying are propagated.
-Equivalent to Insert (Vector, Before, New_Item, 1).
+AARM Note
+Moving the elements does not necessarily involve copying. Similarly, since
+Resize does not require the copying of elements, it does not need to be
+explicitly called (the implementation can combine the operations if it wishes
+to). [Note to reviewers: I didn't want to duplicate the messy wording and notes
+about exceptions not losing anything.]
-procedure Insert
- (Vector : in out Vector_Type;
- Before : in Index_Type'Base;
- New_Item : in Element_Type;
- Count : in Size_Type);
-If Count has the value 0, then Insert does nothing. Otherwise, it
-calculates the new length as the sum of the current length and the value
-of Count; if the new value of Last would be greater than Index_Type'Last
-then Constraint_Error is propagated. If the value of Before is not in
-the range First (Vector) .. Back (Vector), then Constraint_Error
-is propagated.
+procedure Insert (Container : in out Vector;
+ Before : in Cursor;
+ New_Item : in Vector);
-If the current vector size is greater than or equal to the new length,
-then Insert slides the elements in the range Before .. Last
-(Vector) up by Count positions, and it assigns the value New_Item to
-the elements in the Count positions starting at Before. Any exceptions
-raised during the assignment are propagated.
+If Before is No_Element, then is equivalent to Insert (Container,
+Index_Type'Succ (Last_Index (Container)), New_Item); otherwise is
+equivalent to Insert (Container, To_Index (Before), New_Item);
-Otherwise if the current vector size is less than the new length,
-Insert allocates a new internal array, whose elements are initialized
-from New_Item and the active elements in Vector. Any exceptions are
-propagated and Vector is not modified. Insert then replaces the
-old internal array by the new array, and then deallocates the old array.
-Any exceptions raised during deallocation are propagated.
+procedure Insert (Container : in out Vector;
+ Before : in Cursor;
+ New_Item : in Vector;
+ Position : out Cursor);
-procedure Insert_Empty_Space
- (Vector : in out Vector_Type;
- Before : in Index_Type'Base;
- Count : in Size_Type);
+Create a temporary (call it Temp_Index) and set it to Index_Type'Succ
+(Last_Index (Container)) if Before equals No_Element, and To_Index (Before)
+otherwise. Then Insert (Container, Before, New_Item) is called, and finally
+Position is set to To_Cursor (Container, Temp_Index).
-Equivalent to Insert (Vector, Before, New_Item, Count), with the
-difference that the elements in the Count positions starting at Before
-are not assigned.
+AARM Note: The messy wording because Before is invalidated by Insert, and we
+don't want Position to be invalid after this call. An implementation probably
+only needs to copy Before to Position.
-[Open Issue: Is this a good idea? For a container with indefinite components,
-this would leave holes in the structure (since we wouldn't have any default
-value to fill in). Then we have to define what hitting a hole means. In
-general, Vectors are not intended to be sparse (use a Map if you want sparse),
-so that's just extra complication. A better way (but more expensive) to do this
-is to use the Insert with a Count to insert an appropriate "empty" value enough
-times. If we add array operations, we also would have them to fill this need.]
-procedure Delete
- (Vector : in out Vector_Type;
- Index : in Index_Type'Base);
+procedure Insert (Container : in out Vector;
+ Before : in Index_Type'Base;
+ New_Item : in Element_Type;
+ Count : in Size_Type := 1);
-If Index is outside the range First (Vector) .. Last (Vector), the
-operation has no effect. Otherwise, Delete slides down by one position
-the elements in the range Index_Type'Succ (Index) .. Last (Vector).
-Any exceptions raised during element assignment are propagated.
+Equivalent to Insert (Container, Before, To_Vector (New_Item, Count));
-procedure Delete_Last (Vector : in out Vector_Type);
+procedure Insert (Container : in out Vector;
+ Before : in Cursor;
+ New_Item : in Element_Type;
+ Count : in Size_Type := 1);
-Equivalent to Delete (Vector, Last (Vector)).
+Equivalent to Insert (Container, Before, To_Vector (New_Item, Count));
-procedure Delete
- (Vector : in out Vector_Type;
- First : in Index_Type'Base;
- Count : in Size_Type);
+procedure Insert (Container : in out Vector;
+ Before : in Cursor;
+ New_Item : in Element_Type;
+ Position : out Cursor;
+ Count : in Size_Type := 1);
+
+Equivalent to Insert (Container, Before, To_Vector (New_Item, Count), Position);
+
+
+procedure Prepend (Container : in out Vector;
+ New_Item : in Vector;
+ Count : in Size_Type := 1);
+
+Equivalent to Insert (Container, Index_Type'First, New_Item).
+
+
+procedure Prepend (Container : in out Vector;
+ New_Item : in Element_Type;
+ Count : in Size_Type := 1);
+
+Equivalent to Insert (Container, Index_Type'First, New_Item, Count).
+
+
+procedure Append (Container : in out Vector;
+ New_Item : in Vector);
+
+Equivalent to Insert (Container, Index_Type'Succ (Last_Index (Container)),
+New_Item).
+
+
+procedure Append (Container : in out Vector;
+ New_Item : in Element_Type;
+ Count : in Size_Type := 1);
+
+Equivalent to Insert (Container, Index_Type'Succ (Last_Index (Container)),
+New_Item, Count).
+
+
+procedure Insert_Space (Container : in out Vector;
+ Before : in Index_Type'Base;
+ Count : in Size_Type := 1);
+
+Equivalent to Insert (Container, Before, New_Item, Count), with the
+difference that the inserted elements are empty elements.
+
+
+procedure Insert_Space (Container : in out Vector;
+ Before : in Cursor;
+ Position : out Cursor;
+ Count : in Size_Type := 1);
+
+Create a temporary (call it Temp_Index) and set it to
+Index_Type'Succ (Last_Index (Container)) if Before equals No_Element, and
+To_Index (Before) otherwise. Then Insert_Space (Container, Temp_Index,
+Count) is called, and finally Position is set to To_Cursor (Container,
+Temp_Index).
+
+
+procedure Set_Length (Container : in out Vector;
+ Length : in Size_Type);
+
+Calls Resize (Length), then sets the length of the Container to Length.
+If Length is greater than the original length of Container, the added
+elements are empty elements.
+
+
+procedure Delete (Container : in out Vector;
+ Index : in Index_Type'Base;
+ Count : in Size_Type := 1);
-If Count is 0, the operation has no effect. If First does not specify a
-value in the range First (Vector) .. Last (Vector), then
+If Count is 0, the operation has no effect. If Index does not specify a
+value in the range First_Index (Container) .. Last_Index (Container), then
Constraint_Error is propagated. Otherwise Delete slides the active
-elements (if any) starting First plus Count down to First. Any
+elements (if any) starting Index plus Count down to Index. Any
exceptions raised during element assignment are propagated.
-[Open Issue: Matt now thinks that this should be
-procedure Delete
- (Vector : in out Vector_Type;
- First : in Index_Type'Base;
- Through: in Index_Type'Base);
-in order to more closely match Ada.Strings.Unbounded. But the definition of
-Delete in Ada.Strings.Unbounded has proven to be messy to use in practice
-(it is common to have a start and a length, calculating an end and verifying
-that it isn't past the end is messy and requires a if). Which should it be?]
+procedure Delete (Container : in out Vector;
+ Position : in out Cursor;
+ Count : in Size_Type := 1);
-function Size (Vector : Vector_Type) return Size_Type;
+If Count is 0, the operation has no effect. Otherwise is equivalent to
+Delete (Container, To_Index (Position), Count).
-Returns the length of the internal array.
+procedure Delete_First (Container : in out Vector;
+ Count : in Size_Type := 1);
+
+Equivalent to Delete (Container, Index_Type'First, Count).
+procedure Delete_Last (Container : in out Vector;
+ Count : in Size_Type := 1);
-procedure Resize
- (Vector : in out Vector_Type;
- Size : in Size_Type);
-
-If Size (Vector) is equal to or greater than Size, the operation does
-nothing. Otherwise Resize allocates a new internal array whose length
-is at least the value Size, and initializes it from the active elements
-in Vector. Any exceptions raised during the allocation are
-propagated, and Vector is not modified. Resize then replaces the old
-array by the new array, and then deallocates the old array. Any
-exceptions raised during deallocation are propagated.
-
-
-function Front (Vector : Vector_Type) return Index_Type'Base;
-
-Returns the value Index_Type'Pred (Index_Type'First).
-
-[Open issue: This function returns a value that doesn't depend on it's
-parameter. It possibility could be removed in favor of just saying
-Index_Type'Pred(Index_Type'First) appropriately. Committee discussion with the
-original proposal's author was inconclusive. Note that this function is mainly
-useful by analogy with other container packages; a For loop makes a better
-iterator for the Vector container. We could completely do without Front and
-Back for Vectors.]
+Equivalent to Delete (Container, Last_Index (Container), Count).
-function First (Vector : Vector_Type) return Index_Type;
+function First_Index (Container : Vector) return Index_Type;
+
Returns the value Index_Type'First.
+AARM Note: We'd rather call this "First", but then calling most routines in
+here with First (Some_Vect) would be ambiguous.
+
+function First (Container : Vector) return Cursor;
-function First_Element (Vector : Vector_Type) return Element_Type;
+If Container is empty, First returns the value No_Element. Otherwise,
+returns a cursor that designates the first element in Container.
-Equivalent to Element (Vector, First (Vector)).
+function First_Element (Container : Vector) return Element_Type;
+Equivalent to Element (Container, First_Index (Container)).
-function Last (Vector : Vector_Type) return Index_Type'Base;
+function Last_Index (Container : Vector) return Index_Type'Base;
+
Returns the position of the last element in Vector.
-function Last_Element (Vector : Vector_Type) return Element_Type;
+function Last (Container : Vector) return Cursor;
-Equivalent to Element (Vector, Last (Vector)).
+If Container is empty, Last returns the value No_Element. Otherwise,
+returns a cursor that designates the last element in Container.
-function Back (Vector : Vector_Type) return Index_Type'Base;
+function Last_Element (Container : Vector) return Element_Type;
-Equivalent to Index_Type'Succ (Last (Vector)).
+Equivalent to Element (Container, Last_Index (Container)).
-function Element (Vector : Vector_Type;
- Index : Index_Type'Base)
+function Element (Container : Vector;
+ Index : Index_Type'Base)
return Element_Type;
-If Index is not in the range First (Vector) .. Last (Vector), then
-Constraint_Error is propagated. Otherwise this function returns the
+If Index is not in the range First_Index (Container) .. Last_Index (Container),
+then Constraint_Error is propagated. Otherwise this function returns the
element at position Index.
+function Element (Position : Cursor) return Element_Type;
+
+Returns the element designated by Position. If Position equals No_Element,
+then Constraint_Error is propagated.
+
generic
- type Element_Access is access all Element_Type;
-function Generic_Element (Vector : Vector_Type;
- Index : Index_Type'Base)
- return Element_Access;
-
-If Index is not in the range First (Vector) .. Last (Vector), then
-Constraint_Error is propagated. Otherwise this function returns an
-access value that designates a variable view of the element at Index.
-
-[Open Issue: This function requires that the internal elements of Element_Type
-are aliased. However, Ada 95 makes such items constrained, which is a problem
-if Element_Type is mutable (has defaulted discriminants). We either would have
-to declare such elements as not supported (which is really ugly) or remove
-this function (meaning that no update-in-place is possible for elements - a
-real issue for large/expensive-to-copy element types). Luckily, AI-363
-provides a solution - but if that is not adopted, we'll need to revisit this.]
-
-procedure Replace_Element (Vector : in Vector_Type;
- Index : in Index_Type'Base;
- By : in Element_Type);
-
-If Index does not specify a value in the range First (Vector) .. Last
-(Vector), then Constraint_Error is propagated. Otherwise this
-function assigns to the element at position Index the value By. Any
-exceptions raised during the assignment are propagated.
+ with procedure Process (Element : in out Element_Type) is <>;
+procedure Generic_Update_by_Index (Container : in Vector;
+ Index : in Index_Type'Base);
+
+If Index is not in the range First_Index (Container) .. Last_Index (Container),
+then Constraint_Error is propagated. Otherwise, it calls the generic actual
+bound to Process with the element at position Index as the parameter. Any
+exceptions raised by Process are propagated.
+
+If Element_Type is unconstrained and definite, then the Element parameter
+shall be unconstrained.
+
+AARM Note: This means that the elements cannot be aliased nor directly
+allocated from the heap; it must be possible to change the discriminants
+of the element in place.
+
+The element at position Index is not an empty element after successful
+completion of this operation.
+
+AARM Note: Since reading an empty element is a bounded error, attempting to
+use this procedure to replace empty elements may fail. Use Replace_Element
+to do that reliably.
generic
+ with procedure Process (Element : in out Element_Type) is <>;
+procedure Generic_Update (Position : in Cursor);
+
+Calls the generic actual bound to Process with the element designated by
+Position as the parameter. If Position equals No_Element, then
+Constraint_Error is propagated. Any exceptions raised by Process are
+propagated.
+
+If Element_Type is unconstrained and definite, then the Element parameter
+shall be unconstrained.
+
+The element at position Index is not an empty element after successful
+completion of this operation.
+
+procedure Replace_Element (Container : in Vector;
+ Index : in Index_Type'Base;
+ By : in Element_Type);
+
+If Index does not specify a value in the range First_Index (Container) ..
+Last_Index (Container), then Constraint_Error is propagated. Otherwise this
+function assigns the value By to the element at position Index. Any exceptions
+raised during the assignment are propagated. The element at position Index is
+not an empty element after successful completion of this operation.
+
+procedure Replace_Element (Position : in Cursor;
+ By : in Element_Type);
+
+This function assigns the value By to the element designated by Position.
+If Position equals No_Element, then Constraint_Error is propagated.
+Any exceptions raised during the assignment are propagated. The element
+designated by Position is not an empty element after successful completion of
+this operation.
+
+AARM Note: Replace_Element, Generic_Update, and Generic_Update_by_Index are
+only ways that an element can change from empty to non-empty.
+
+procedure Swap (Container : in Vector;
+ I, J : in Index_Type'Base);
+
+If I or J does not specify a value in the range First_Index (Container) ..
+Last_Index (Container), then Constraint_Error is propagated. Otherwise Swap
+exchanges the values of the elements at positions I and J.
+
+AARM Note: To Be Honest: The implementation is not required to actually
+copy the elements if it can do the swap some other way. But it is allowed
+to copy the elements if needed.
+
+procedure Swap (Container : in Vector;
+ I, J : in Cursor);
+
+Equivalent to Swap (Container, To_Index (I), To_Index (J)).
+
+
+generic
with function "<" (Left, Right : Element_Type) return Boolean is <>;
-procedure Generic_Sort (Vector : in Vector_Type);
+procedure Generic_Sort (Container : in Vector);
Reorders the elements of Vector such that the elements are
sorted per the order specified as the generic formal less-than operator.
@@ -700,46 +1005,228 @@
implementation to do that, but it is mostly extra overhead -- usually there
is something already in the element that provides the needed stability.
+function Find (Container : Vector;
+ Item : Element_Type;
+ Index : Index_Type'Base := Index_Type'First)
+ return Index_Type'Base;
+
+Searches the elements of Container for an element equal to Item,
+starting at position Index. If Index is less than Index_Type'First,
+then Constraint_Error is propagated. If there are no elements in the
+range Index .. Last_Index (Container) equal to Item, then Find returns
+Index_Type'Succ (Last_Index (Container)). Otherwise, it returns the index of
+the matching element.
+
+function Find (Container : Vector;
+ Item : Element_Type;
+ Position : Cursor := No_Element)
+ return Cursor;
+
+Searches the elements of Container for an element equal to Item,
+starting at the first element if Cursor equals No_Element, and at
+the element designated by Cursor otherwise, and searching to the last
+element in Container. If an item equal to Item is found, Find returns a
+cursor designating the first element found equal to Item. If no such item is
+found, it returns No_Element.
+
+function Reverse_Find (Container : Vector;
+ Item : Element_Type;
+ Index : Index_Type'Base :=
+ Index_Type'Pred (Index_Type'First))
+ return Index_Type'Base;
+
+Searches the elements of Container in reverse for an element equal to
+Item, starting at position Index. If Index is greater than Last_Index
+(Container), then Constraint_Error is propagated. If Index is less than
+Index_Type'First, then the search begins at position Last_Index (Container).
+If there are no elements in the range Index_Type'First .. Index equal
+to Item, then Reverse_Find returns Index_Type'Succ (Last_Index (Container)).
+Otherwise, it returns the index of the matching element.
+
+function Reverse_Find (Container : Vector;
+ Item : Element_Type;
+ Position : Cursor := No_Element)
+ return Cursor;
+
+Searches the elements of Container for an element equal to Item,
+starting at the last element if Cursor equals No_Element, and at
+the element designated by Cursor otherwise, and searching backwards to the
+first element in Container. If an item equal to Item is found, Find returns a
+cursor designating the first element found equal to Item. If no such item is
+found, it returns No_Element.
+
+
+function Is_In (Item : Element_Type;
+ Container : Vector)
+ return Boolean;
+
+Equivalent to Find (Container, Item).
+
+
+function Next (Position : Cursor) return Cursor;
+
+If Position equals No_Element, then Next returns the value
+No_Element. If Position designates the last element of the container,
+then Next returns No_Element. Otherwise, returns a cursor that designates
+the element with index Index_Type'Succ (To_Index (Position)) in the
+same vector as Position.
+
+function Previous (Position : Cursor) return Cursor;
+
+If Position equals No_Element, then Previous returns the value No_Element. If
+ Position designates the first element of the container, then Previous returns
+No_Element. Otherwise, returns a cursor that designates
+the element with index Index_Type'Pred (To_Index (Position)) in the
+same vector as Position.
+
+The procedure Next is equivalent to Position := Next (Position).
+
+The procedure Previous is equivalent to Position := Previous (Position).
+
+function Has_Element (Position : Cursor) return Boolean;
+
+Returns True if Position designates an element, and returns False otherwise.
+
+AARM Note: To Be Honset: This function is may not detect cursors that
+designate deleted elements; such cursors are invalid (see below) and any
+use of them (including in this routine) is erroneous.
+
+generic
+ with procedure Process (Position : in Cursor) is <>;
+procedure Generic_Iteration (Container : in Vector);
+
+Invokes the actual subprogram bound to Process with a cursor that
+designates each node element Container. Any exceptions raised during Process
+are propagated.
+
+generic
+ with procedure Process (Position : in Cursor) is <>;
+procedure Generic_Reverse_Iteration (Container : in Vector);
+
+Iterates over the nodes in Container as per Generic_Iteration, except
+that elements are traversed in reverse order.
+
+
Legality Rules
An instantiation of Containers.Vectors shall be at the library level.
AARM Note
A implementation will typically need to use controlled types to insure that
-the Implementation Requirement is met. These would require all instantiations
+the Implementation Requirements are met. These would require all instantiations
to occur at the library level. We certainly do not want to require magic
for nested container instantiations, while not giving similar capabilities to
users. We've made this a legality rule to enhance portability. This rule can
be dropped if AI-344 or some other solution to nested controlled types is
adopted.
+Bounded (Run-Time) Errors
+
+Reading the value of an empty element by calling Element, Generic_Update,
+Generic_Update_By_Index, Generic_Sort, "=", Find, or Reverse_Find is a bounded
+error. The implementation may treat the element as having any valid value of
+the element type, or raise Constraint_Error or Program_Error before modifying
+the vector.
+
+AARM Notes: For instance, a default initialized element could be returned. Or
+some previous value of an element. But returning random junk is not allowed
+if the type has if the type has default initial value(s).
+
+Assignment and streaming of empty elements are NOT bounded errors.
+This is consistent with regular composite types, for which assignment and
+streaming of uninitialized components do not cause a bounded error, but reading
+the uninitialized component does cause a bounded error.
+
+There are other operations which are defined in terms of the operations listed
+above.
+End AARM Notes.
+
+A Cursor value is *dubious* if any of the following have occurred since it was
+created:
+ * Insert or Delete has been called on the vector that contains the element the
+ cursor designates with a index value (or a cursor designating an element at
+ such an index value) less than or equal to the index value of the element
+ designated by the cursor;
+ * The vector that contains the element it designates has been passed to an
+ instance of Generic_Sort.
+
+It is a bounded error to call any subprogram other than "=" or Has_Element
+declared in Containers.Vectors with a dubious (but not invalid, see below)
+cursor parameter. Possible results are:
+ * The cursor may be treated as if it was No_Element;
+ * The cursor may designate some element in the vector (but not necessarily
+ the element that it designates);
+ * Constraint_Error may be raised; or
+ * Program_Error may be raised.
+
+AARM Note: Cursors are invalidated if an Insert or Delete occurs that moves
+the elements in the internal array including the designated ones. After such
+an operation, the cursor probably still designates an element (although it
+might not after a deletion), but it is is a *different* element.
+That violates the definition of cursor -- it designates a particular element.
+
+For "=" or Has_Element, the cursor works normally (it would not be No_Element).
+We don't want to trigger an exception simply for comparing a bad cursor.
+
+While it is possible to check for or prevent these cases, in many cases the
+overhead necessary to make the check (or prevent the problems) is substantial
+in time or space.
+End AARM Notes.
+
+
+Erroneous Execution
+
+A Cursor value is *invalid* if any of the following have occurred since it was
+created:
+ * The vector that contains the element it designates has been finalized;
+ * The vector that contains the element it designates has been used as the
+ Source or Target of a call to Move;
+ * The element it designates has been deleted.
+
+The result of "=" or Has_Element is unspecified if it is called with an
+invalid cursor parameter. Execution is erroneous if any other subprogram
+declared in Containers.Vectors is called with an invalid cursor parameter, or
+if the cursor designates an element in a different vector object than the
+appropriate one specified in the call.
+
+AARM Notes: The list above (conbined with the bounded error cases) is intended
+to be exhaustive. In other cases, a cursor value continues to designate its
+original element. For instance, cursor values survive the appending of new
+elements.
+End AARM Notes.
+
Implementation Requirements
-No storage associated with a vector Vector_Type object shall be lost
-upon assignment or scope exit.
+No storage associated with a vector object shall be lost upon assignment or
+scope exit.
Implementation Advice
Containers.Vectors should be implemented similarly to an array. In particular,
-the time taken by Append and Element should not depend on the number of
-items in the Vector, and the time taken by Insert or Delete at First of the
-vector should take time no worse than roughly proportional to the number of
-elements in the vector.
+if the length of a vector is *N*, then
+ * the time taken by Append with Count=1 and Element should take time no
+ worse than roughly proportional to the log (base 2) of N;
+ * the time taken by Prepend with Count=1 or Delete_First with Count=1 of
+ the vector should take time no worse than roughly proportional to
+ N * log (base 2) of N.
AARM Note
We do not mean to overly constrain implementation stratgies here. However, it
is important for portability that the performance of large containers has
roughly the same factors on different implementations. If a program is moved
-to an implementation that take time proportional to the length of the vector
-to access elements, that program could be unusable when the vectors are large.
+to an implementation that takes O(N) time to access elements, that program
+could be unusable when the vectors are large. We allow O(log N) access because
+the proportionality constant and caching effects are likely to be larger than
+the log factor, and we don't want to discourage innovative implementations.
+
+A call on an instantiation of Containers.Vectors.Generic_Sort should take no
+worse than a time proportional to the square of the number of items in the
+vector, and on average a time better than proportional to the square of the
+number of items in the vector.
-A call on an instantiation of Containers.Vectors.Generic_Sort should take on
-average a time proportional to the log (base 2) of the number of items times
-the number of items in the vector.
-
AARM Note
-In other words, we're requiring the use of an O(N log N) sorting algorithm,
-such as Quicksort. No Bubble sorts allowed!
+In other words, we're requiring the use of a better than O(N**2) sorting
+algorithm, such as Quicksort. No Bubble sorts allowed!
Containers.Vectors.Generic_Sort should minimize copying of elements.
@@ -748,45 +1235,632 @@
single copy for each element. Rather, we want to suggest that the sorting
algorithm chosen is one that does not copy items unnecessarily. Bubble sort
would not meet this advice, for instance.
+
+NOTE:
+All elements of a vector occupy locations in the internal array.
+If a sparse container is required, a Hashed_Map should be used rather than a
+vector.
+
+A.17.3 The Package Containers.Doubly_Linked_Lists
+
+The language-defined package Containers.Doubly_Linked_Lists provides
+private types List and Cursor, and a set of operations for each type. A
+list container is optimized for insertion and deletion at any position.
+
+A doubly-linked list container object manages a linked list of internal
+storage nodes, each of which contains an element and pointers to the
+next (successor) and previous (predecessor) internal nodes. A cursor
+is used to specify positions of particular storage nodes within a list.
+
+A list container may contain *empty elements*. Empty elements do not have a
+defined value.
+
+Static Semantics
+
+The library package Containers.Doubly_Linked_Lists has the following
+declaration:
+
+generic
-[Open Issue: Should we also define "indefinite Element_Type" versions of these
-packages? They would allow String and T'Class containers to be used, at the
-cost of more memory allocation overhead. The wording cost is about one
-paragraph per package, with wording similar to that used for Wide_String
-versions of packages.
-
-There also is some sentiment for an indefinite Key_Type form of the Hashed_Map
-container. If we added that, we could eliminate the specific String version
-(or replace it by a language-defined instantiation).]
-
-[Open issue: Several reviewers complained about the lack of support for
-aggregate operations. Should there be operations to operate on slices of
-Vectors? These would take ranges similarly to Unbounded_Strings. Similarly,
-should there be operations to combine Vectors (such as an Insert of another
-Vector)?
-
-Another option to supporting more aggregate operations would be to define
-an array type for the package:
- type Vector_Elements is array (Index_Type range <>) of Element_Type;
-and then provide operations going to and from this type. But note that this
-doesn't work for indefinite elements.
-
-See Matt's design note in the !appendix for more ideas in both of these veins.]
-
-[Open Issue: After indefinite elements, the number one complaint of reviewers
-was the removal of the List sequence container. While it doesn't have any
-additional operations over a Vector, it does have different performance
-characteristics (particularly for insertion at the front {O(1) instead of O(N)}
-and for arbitrary element access {O(N) instead of O(1), because a search is
-needed to find the element). Should this container be reintroduced?]
-
-A.17.3 The Package Containers.Hashed_Maps
-
-The language-defined package Containers.Hashed_Maps provides
-private types Map_Type and Cursor_Type, and a set of operations
-for each type. A hashed map container allows an arbitrary type to be
-used as a key to find the element associated with that key.
+ type Element_Type is private;
+
+ with function "=" (Left, Right : Element_Type) return Boolean is <>;
+
+package Ada.Containers.Doubly_Linked_Lists is
+ pragma Preelaborate (Doubly_Linked_Lists);
+
+ type List is private;
+
+ type Cursor is private;
+
+ Empty_List : constant List;
+ --NOTE: function or deferred constant?
+
+ No_Element : constant Cursor;
+
+ function "=" (Left, Right : List) return Boolean;
+
+ function Length (Container : List) return Natural;
+
+ function Is_Empty (Container : List) return Boolean;
+
+ procedure Clear (Container : in out List);
+
+ procedure Move (Target : in out List;
+ Source : in out List);
+ procedure Prepend (Container : in out List;
+ New_Item : in Element_Type;
+ Count : in Size_Type := 1);
+
+ procedure Append (Container : in out List;
+ New_Item : in Element_Type;
+ Count : in Size_Type := 1);
+
+ procedure Insert (Container : in out List;
+ Before : in Cursor;
+ New_Item : in Element_Type;
+ Count : in Size_Type := 1);
+
+ procedure Insert (Container : in out List;
+ Before : in Cursor;
+ New_Item : in Element_Type;
+ Position : out Cursor;
+ Count : in Size_Type := 1);
+
+ procedure Insert_Space (Container : in out List;
+ Before : in Cursor;
+ Position : out Cursor;
+ Count : in Size_Type := 1);
+
+ procedure Delete (Container : in out List;
+ Position : in out Cursor;
+ Count : in Size_Type := 1);
+
+ procedure Delete_First (Container : in out List;
+ Count : in Size_Type := 1);
+
+ procedure Delete_Last (Container : in out List;
+ Count : in Size_Type := 1);
+
+ procedure Delete (Container : in out List;
+ Item : in Element_Type);
+
+ generic
+ with function Predicate (Element : Element_Type)
+ return Boolean is <>;
+ procedure Generic_Delete (Container : in out List);
+
+ generic
+ with function "<" (Left, Right : Element_Type)
+ return Boolean is <>;
+ procedure Generic_Sort (Container : in out List);
+
+ generic
+ with function "<" (Left, Right : Element_Type)
+ return Boolean is <>;
+ procedure Generic_Merge (Target : in out List;
+ Source : in out List);
+
+ procedure Reverse_List (Container : in out List);
+
+ procedure Swap (Container : in out List;
+ I, J : in Cursor);
+
+ procedure Splice (Target : in out List;
+ Before : in Cursor;
+ Source : in out List);
+
+ procedure Splice (Target : in out List;
+ Before : in Cursor;
+ Position : in Cursor);
+
+ procedure Splice (Target : in out List;
+ Before : in Cursor;
+ Source : in out List;
+ Position : in Cursor);
+
+ function First (Container : List) return Cursor;
+
+ function First_Element (Container : List)
+ return Element_Type;
+
+ function Last (Container : List) return Cursor;
+
+ function Last_Element (Container : List)
+ return Element_Type;
+
+ function Element (Position : Cursor)
+ return Element_Type;
+
+ generic
+ with procedure Process (Element : in out Element_Type) is <>;
+ procedure Generic_Update (Position : in Cursor);
+
+ procedure Replace_Element (Position : in Cursor;
+ By : in Element_Type);
+
+ function Is_In (Item : Element_Type;
+ Container : List) return Boolean;
+
+ function Find (Container : List;
+ Item : Element_Type;
+ Position : Cursor := No_Element)
+ return Cursor;
+
+ generic
+ with function Predicate (Element : Element_Type)
+ return Boolean is <>;
+ function Generic_Find (Container : List;
+ Position : Cursor := No_Element)
+ return Cursor;
+
+ function Reverse_Find (Container : List;
+ Item : Element_Type;
+ Position : Cursor := No_Element)
+ return Cursor;
+
+ generic
+ with function Predicate (Element : Element_Type)
+ return Boolean is <>;
+ function Generic_Reverse_Find (Container : List;
+ Position : Cursor := No_Element)
+ return Cursor;
+
+ function Next (Position : Cursor) return Cursor;
+
+ function Previous (Position : Cursor) return Cursor;
+
+ procedure Next (Position : in out Cursor);
+
+ procedure Previous (Position : in out Cursor);
+
+ function Has_Element (Position : Cursor) return Boolean;
+
+ generic
+ with procedure Process (Position : in Cursor) is <>;
+ procedure Generic_Iteration (Container : in List);
+
+ generic
+ with procedure Process (Position : in Cursor) is <>;
+ procedure Generic_Reverse_Iteration (Container : in List);
+
+private
+
+ ... -- not specified by the language
+
+end Ada.Containers.Doubly_Linked_Lists;
+
+
+Empty_List represents the empty list. If an object of type List is not
+otherwise initialized, it will be initialized to the same value as
+Empty_List.
+
+No_Element represents a cursor that designates no element. If an object of type
+Cursor is not otherwise initialized, it will be initialized to the same
+value as No_Element.
+
+function "=" (Left, Right : List) return Boolean;
+
+If Left denotes the same object as Right, then this function returns
+True. Otherwise if Left and Right have different lengths, then this
+function returns False. Otherwise, it compares each element in Left to
+the corresponding element in Right using the generic formal equality
+operator. If element equality returns False, then this function returns
+False; otherwise, this function returns True. Any exceptions raised
+during evaluation of element equality are propagated.
+
+The function Length returns the number of elements in Container.
+
+The function Is_Empty is equivalent to Length (Container) = 0.
+
+Clear removes all the nodes in Container, and sets the length to 0. Any
+exceptions raised during deallocation of storage are propagated.
+
+procedure Move (Target : in out List;
+ Source : in out List);
+
+If Target denotes the same object as Source, then the operation has no
+effect. If Length (Target) is greater than 0, then it raises
+Constraint_Error. Otherwise, the nodes in Source are moved to Target. The
+length of Target is set to the length of Source, and the length of Source is
+set to 0.
+
+Prepend is equivalent to Insert (Container, First (Container), New_Item, Count).
+
+Append is equivalent to Insert (Container, No_Element, New_Item, Count).
+
+procedure Insert (Container : in out List;
+ Before : in Cursor;
+ New_Item : in Element_Type;
+ Count : in Size_Type := 1);
+
+Insert allocates Count new nodes whose element is initialized to the value
+New_Item, and inserts them prior to the node designated by Before. If
+Before equals No_Element, the new node is inserted immediately
+following the last node (if any). Any exceptions raised during allocation of
+internal storage are propagated, and Container is not modified.
+
+procedure Insert (Container : in out List;
+ Before : in Cursor;
+ New_Item : in Element_Type;
+ Position : out Cursor;
+ Count : in Size_Type := 1);
+
+Insert allocates Count new nodes whose element is initialized to the value
+New_Item, and inserts them prior to the node designated by Before. If
+Before equals No_Element, the new node is inserted immediately
+following the last node (if any). Position designates the first
+newly-inserted node. Any exceptions raised during allocation of
+internal storage are propagated, and Container is not modified.
+
+procedure Insert_Space (Container : in out List;
+ Before : in Cursor;
+ Position : out Cursor;
+ Count : in Size_Type := 1);
+
+Insert_Space allocates Count new nodes whose elements are empty, and
+inserts them prior to the node designated by Before. If
+Before equals No_Element, the new node is inserted immediately
+following the last node (if any). Position designates the
+first newly-inserted node. Any exceptions raised during allocation of
+internal storage are propagated, and Container is not modified.
+
+procedure Delete (Container : in out List;
+ Position : in out Cursor;
+ Count : in Size_Type := 1);
+
+If Position equals No_Element, the operation has no effect. Otherwise
+Delete removes Count nodes starting at the node designated by Position
+from Container (or all of the nodes if there are less than Count nodes
+starting at Position). Any exceptions raised during deallocation of internal
+storage are propagated.
+
+procedure Delete_First (Container : in out List;
+ Count : in Size_Type := 1);
+
+If Length(Container) >= Count, Delete_First removes the first Count nodes from
+Container; otherwise, all of the nodes in Container are removed. Any exceptions
+raised during deallocation of storage are propagated.
+
+procedure Delete_Last (Container : in out List;
+ Count : in Size_Type := 1);
+
+If Length(Container) >= Count, Delete_Last removes the last Count nodes from
+Container; otherwise, all of the nodes in Container are removed. Any exceptions
+raised during deallocation of storage are propagated.
+
+procedure Delete (Container : in out List;
+ Item : in Element_Type);
+
+Equivalent to Generic_Delete instantiated with a predicate function
+implemented in terms of the equality operator for Element_Type.
+
+generic
+ with function Predicate (Element : Element_Type)
+ return Boolean is <>;
+procedure Generic_Delete (Container : in out List);
+
+Deletes each element in Container for which the generic formal function
+Predicate returns True.
+
+generic
+ with function "<" (Left, Right : Element_Type) return Boolean is <>;
+procedure Generic_Sort (Container : in out List);
+
+Reorders the nodes of Container such that the elements are sorted per the
+order specified as the generic formal less-than operator. The sort must be
+stable. Any exceptions raised during evalution of less-than are propagated,
+immediately terminating the sort operation.
+
+AARM Notes
+Unlike array sorts, we do require stable sorts here. That's because
+algorithms in the merge sort family (as described byt Knuth) can be both
+fast and stable. That's because we can use the extra memory as offered by
+the links to provide better performance.
+
+Note that list sorts never copy elements; it is the nodes, not the elements,
+that are reordered.
+End AARM Notes
+
+generic
+ with function "<" (Left, Right : Element_Type) return Boolean is <>;
+procedure Generic_Merge (Target : in out List;
+ Source : in out List);
+
+If Source denotes the same object as Target, the operation has no
+effect. Otherwise this operation reorders nodes such that they are
+removed from Source and moved to Target. Target and Source are
+assumed to be sorted in the order specified as the generic formal. The
+nodes in Source containing elements that are less than elements in
+Target are spliced in before the elements already in Target. The
+nodes in Source container elements that are equal to or greater than
+elements in Target are spliced in after the elements already in
+Target. Any exceptions raised during evaluation of less-than are
+propagated, immediately terminating the merge operation.
+
+procedure Reverse_List (Container : in out List);
+
+Reorders the nodes of Container in reverse order.
+
+procedure Swap (Container : in out List;
+ I, J : in Cursor);
+
+Swap exchanges the nodes designated by I and J.
+
+procedure Splice (Target : in out List;
+ Before : in Cursor;
+ Source : in out List);
+
+If Source denotes the same object as Target, the operation has no
+effect. Otherwise, Splice reorders nodes such that they are removed from
+Source and moved to Target, just prior to Before. If Before equals
+No_Element, the nodes of Source are spliced after the last node of
+Target. The length of Target is incremented by the number of
+nodes in Source, and the length of Source is set to 0.
+
+procedure Splice (Target : in out List;
+ Before : in Cursor;
+ Position : in Cursor);
+
+If Position equals No_Element, or if Position equals Before, or if the
+successor of Position equals Before, the operation has no effect.
+Otherwise the node designated by Position is becomes the predecessor of Before.
+If Before equals No_Element, then Position is moved after the last node.
+
+procedure Splice (Target : in out List;
+ Before : in Cursor;
+ Source : in out List;
+ Position : in Cursor);
+
+If Source denotes the same object as Target, then Splice is
+equivalent to the Splice operation sans Source parameter. If Position
+equals No_Element, the operation has no effect. Otherwise the node
+designated by Position is removed from Source and moved to Target, immediately
+prior to Before. If Before equals No_Element, then Position is moved after the
+last node of Container. The length of Target is incremented, and the length of
+Source is decremented.
+
+function First (Container : List) return Cursor;
+
+Returns a cursor that designates the first node. If Container is empty,
+First returns the value No_Element.
+
+function First_Element (Container : List) return Element_Type;
+
+If Container is empty, then Constraint_Error is propagated. Otherwise,
+it returns Element (First (Container)).
+
+function Last (Container : List) return Cursor;
+
+Returns a cursor that designates the last node. If Container is empty,
+Last returns the value No_Element.
+
+function Last_Element (Container : List) return Element_Type;
+
+If Container is empty, then Constraint_Error is propagated. Otherwise,
+it returns Element (Last (Container)).
+
+function Element (Position : Cursor) return Element_Type;
+
+Returns the element stored on the node designated by Cursor. If
+Position equals No_Element, then Constraint_Error is propagated.
+
+generic
+ with procedure Process (Element : in out Element_Type) is <>;
+procedure Generic_Update (Position : in Cursor);
+
+If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
+Generic_Update invokes the generic actual procedure bound to Process
+with the element on node designated by Position as the argument.
+
+If Element_Type is unconstrained and definite, then the Element parameter
+shall be unconstrained.
+
+AARM Note: This means that the elements cannot be aliased nor directly
+allocated from the heap; it must be possible to change the discriminants
+of the element in place.
+
+The element designated by Position is not an empty element after successful
+completion of this operation.
+
+AARM Note: Since reading an empty element is a bounded error, attempting to
+use this procedure to replace empty elements may fail. Use Replace_Element
+to do that reliably.
+
+procedure Replace_Element (Position : Cursor;
+ By : Element_Type);
+
+Assigns the value By to the element stored on the node designated by
+Position. If Position equals No_Element, then Constraint_Error is
+propagated. The element designated by Position is not an empty element after
+successful completion of this operation.
+
+AARM Note: Replace_Element and Generic_Update are only ways that an element
+can change from empty to non-empty.
+
+function Is_In (Item : Element_Type;
+ Container : List) return Boolean;
+
+Equivalent to Find (Container, Item) /= No_Element.
+
+function Find (Container : List;
+ Item : Element_Type;
+ Position : Cursor := No_Element)
+ return Cursor;
+
+Searches the nodes of Container for an element equal to Item. The
+search starts at the node designated by Position. If Position equals
+No_Element, then the search begins at the first node. If no element is
+found that matches Item, then Find returns the value No_Element.
+
+generic
+ with function Predicate (Element : Element_Type)
+ return Boolean is <>;
+function Generic_Find (Container : List;
+ Position : Cursor := No_Element)
+ return Cursor;
+
+Searches the nodes of Container for an element for which the generic
+formal Predicate function returns True. The search starts at the node
+designated by Position. If Position equals No_Element, then the search
+begins at the first node. If no element is found for which Predicate
+returns True, then Generic_Find returns the value No_Element.
+
+function Reverse_Find (Container : List;
+ Item : Element_Type;
+ Position : Cursor := No_Element)
+ return Cursor;
+
+Searches the nodes of Container in reverse for an element equal to Item.
+The search starts at the node designated by Position. If Position
+equals No_Element, then the search begins at the last node. If no
+element is found that matches Item, then Find returns the value
+No_Element.
+
+generic
+ with function Predicate (Element : Element_Type)
+ return Boolean is <>;
+function Generic_Reverse_Find (Container : List;
+ Position : Cursor := No_Element)
+ return Cursor;
+
+Searches the nodes of Container in reverse for an element for which the
+generic formal Predicate function returns True. The search starts at
+the node designated by Position. If Position equals No_Element, then
+the search begins at the last node. If no element is found for which
+Predicate returns True, then Generic_Revserse_Find returns the value
+No_Element.
+
+function Next (Position : Cursor) return Cursor;
+
+Returns a cursor that designates the successor of the node designated by
+Position. If Position equals No_Element, then Next returns the value
+No_Element. If Position designates the last node of the container,
+then Next returns No_Element.
+
+function Previous (Position : Cursor) return Cursor;
+
+Returns a cursor that designates the predecessor of the node designated
+by Position. If Position equals No_Element, then Previous returns the
+value No_Element. If Position designates the first node of the
+container, then Previous returns No_Element.
+
+The procedure Next is equivalent to Position := Next (Position).
+
+The procedure Previous is equivalent to Position := Previous (Position).
+
+function Has_Element (Position : Cursor) return Boolean;
+
+Returns True if Position designates an element, and returns False otherwise.
+
+AARM Note: To Be Honset: This function is may not detect cursors that
+designate deleted elements; such cursors are invalid (see below) and any
+use of them (including in this routine) is erroneous.
+
+generic
+ with procedure Process (Position : in Cursor) is <>;
+procedure Generic_Iteration (Container : in List);
+
+Invokes the actual subprogram bound to Process with a cursor that
+designates each node in Container. Any exceptions raised during Process
+are propagated.
+
+generic
+ with procedure Process (Position : in Cursor) is <>;
+procedure Generic_Reverse_Iteration (Container : in List);
+
+Iterates over the nodes in Container as per Generic_Iteration, except
+that elements are traversed in reverse order.
+
+Bounded (Run-Time) Errors
+
+Reading the value of an empty element by calling Element, Generic_Update,
+Generic_Sort, Generic_Merge, "=", Find, Reverse_Find, Generic_Find,
+Generic_Reverse_Find, Generic_Iteration, or Generic_Reverse_Iteration
+is a bounded error. The implementation may treat the element as having any
+valid value of the element type, or raise Constraint_Error or Program_Error.
+
+AARM Notes: For instance, a default initialized element could be returned. Or
+some previous value of an element. But returning random junk is not allowed
+if the type has if the type has default initial value(s).
+
+Assignment and streaming of empty elements are NOT bounded errors.
+This is consistent with regular composite types, for which assignment and
+streaming of uninitialized components do not cause a bounded error, but reading
+the uninitialized component does cause a bounded error.
+
+There are other operations which are defined in terms of the operations listed
+above.
+End AARM Notes.
+
+Erroneous Execution
+
+A Cursor value is *invalid* if any of the following have occurred since it was
+created:
+ * The list that contains the element it designates has been finalized;
+ * The list that contains the element it designates has been used as the
+ Source or Target of a call to Move;
+ * The element it designates has been deleted.
+
+The result of "=" or Has_Element is unspecified if it is called with an invalid
+cursor parameter. Execution is erroneous if any other subprogram declared in
+Containers.Doubly_Linked_Lists is called with an invalid cursor parameter, or
+if the cursor designates an element in a different list object than the
+appropriate one specified in the call.
+
+AARM Notes: The list above is intended to be exhaustive. In other cases, a
+cursor value continues to designate its original element. For instance,
+cursor values survive the insertion and deletion of other nodes.
+
+While it is possible to check for these cases, in many cases the overhead
+necessary to make the check is substantial in time or space. Implementations
+are encouraged to check for as many of these cases as possible and raise
+Constraint_Error if detected.
+End AARM Notes.
+
+Implementation Requirements
+
+No storage associated with a doubly-linked List object shall be lost
+upon assignment or scope exit.
+
+Implementation Advice
+
+Containers.Doubly_Linked_Lists should be implemented similarly to a linked list.
+In particular, the time taken by Element, Insert with Count=1, and Delete with
+Count=1 should take time no worse than roughly proportional to the log (base 2)
+of the length of the list.
+
+AARM Note
+We do not mean to overly constrain implementation stratgies here. However, it
+is important for portability that the performance of large containers has
+roughly the same factors on different implementations. If a program is moved to
+an implementation that takes O(N) time to access elements, that program could
+be unusable when the lists are large. We allow O(log N) access because the
+proportionality constant and caching effects are likely to be larger than the
+log factor, and we don't want to discourage innovative implementations.
+
+A call on an instantiation of Containers.Doubly_Linked_Lists.Generic_Sort
+should take no worse than a time proportional to the square of the number of
+items in the list, and on average a time better than proportional to the
+square of the number of items in the list.
+
+AARM Note
+In other words, we're requiring the use of a better than O(N**2) sorting
+algorithm, such as Quicksort. No Bubble sorts allowed!
+
+NOTE
+Sorting a list never copies elements, and is a stable sort (equal elements
+remain in the original order). This is different than sorting an array or
+vector, which may need to copy elements, and is probably not a stable sort.
+
+A.17.4 The Package Containers.Hashed_Maps
+
+The language-defined package Containers.Hashed_Maps provides private
+types Map and Cursor, and a set of operations for each type. A hashed
+map container allows an arbitrary type to be used as a key to find the
+element associated with that key.
+
AARM Note: The name is "Hashed_Maps" to allow for a secondary standard
to include "Sorted_Maps".
@@ -811,106 +1885,100 @@
return Boolean is <>;
package Ada.Containers.Hashed_Maps is
+ pragma Preelaborate (Hashed_Maps);
- pragma Preelaborate;
+ type Map is private;
- type Map_Type is private;
+ type Cursor is private;
- type Cursor_Type is private;
+ Empty_Map : constant Map;
- Null_Cursor : constant Cursor_Type;
+ No_Element : constant Cursor;
- function "=" (Left, Right : Map_Type) return Boolean;
+ function "=" (Left, Right : Map) return Boolean;
- function Length (Map : Map_Type) return Size_Type;
+ function Length (Container : Map) return Size_Type;
- function Is_Empty (Map : Map_Type) return Boolean;
+ function Is_Empty (Container : Map) return Boolean;
- procedure Clear (Map : in out Map_Type);
+ procedure Clear (Container : in out Map);
- procedure Swap (Left, Right : in out Map_Type);
+ procedure Move (Target : in out Map;
+ Source : in out Map);
- procedure Insert (Map : in out Map_Type;
+ procedure Insert (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type;
- Cursor : out Cursor_Type;
+ Position : out Cursor;
Success : out Boolean);
- procedure Replace (Map : in out Map_Type;
+ procedure Replace (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);
- procedure Insert (Map : in out Map_Type;
+ procedure Insert (Container : in out Map;
Key : in Key_Type;
- Cursor : out Cursor_Type;
+ Position : out Cursor;
Success : out Boolean);
- procedure Delete (Map : in out Map_Type;
+ procedure Delete (Container : in out Map;
Key : in Key_Type);
- procedure Delete (Map : in out Map_Type;
- Cursor : in out Cursor_Type);
+ procedure Delete (Container : in out Map;
+ Position : in out Cursor);
- function Is_In (Key : Key_Type;
- Map : Map_Type)
+ function Is_In (Key : Key_Type;
+ Container : Map)
return Boolean;
- function Find (Map : Map_Type;
- Key : Key_Type)
- return Cursor_Type;
+ function Find (Container : Map;
+ Key : Key_Type)
+ return Cursor;
- function Element (Map : Map_Type;
- Key : Key_Type)
+ function Element (Container : Map;
+ Key : Key_Type)
return Element_Type;
-
- function Size (Map : Map_Type) return Size_Type;
- procedure Resize (Map : in out Map_Type;
- Size : in Size_Type);
+ function Size (Container : Map) return Size_Type;
- function First (Map : Map_Type)
- return Cursor_Type;
+ procedure Resize (Container : in out Map;
+ Size : in Size_Type);
- function Back (Map : Map_Type)
- return Cursor_Type;
+ function First (Container : Map)
+ return Cursor;
- function Succ (Map : Map_Type;
- Cursor : Cursor_Type) return Cursor_Type;
+ function Next (Position : Cursor) return Cursor;
- procedure Increment (Map : in Map_Type;
- Cursor : in out Cursor_Type);
+ procedure Next (Position : in out Cursor);
- function Key (Cursor : Cursor_Type) return Key_Type;
+ function Has_Element (Position : Cursor) return Boolean;
- generic
- type Key_Access is access constant Key_Type;
- function Generic_Key (Cursor : Cursor_Type) return Key_Access;
+ function Key (Position : Cursor) return Key_Type;
- function Is_Equal_Key (Left, Right : Cursor_Type)
+ function Is_Equal_Key (Left, Right : Cursor)
return Boolean;
- function Is_Equal_Key (Left : Cursor_Type;
+ function Is_Equal_Key (Left : Cursor;
Right : Key_Type)
return Boolean;
function Is_Equal_Key (Left : Key_Type;
- Right : Cursor_Type)
+ Right : Cursor)
return Boolean;
- function Element (Cursor : Cursor_Type)
+ function Element (Position : Cursor)
return Element_Type;
generic
- type Element_Access is access all Element_Type;
- function Generic_Element (Cursor : Cursor_Type)
- return Element_Access;
+ with procedure Process (Element : in out Element_Type) is <>;
+ procedure Generic_Update (Position : in Cursor);
- procedure Replace_Element (Cursor : in Cursor_Type;
+ procedure Replace_Element (Position : in Cursor;
By : in Element_Type);
generic
- with procedure Process (Cursor : in Cursor_Type) is <>;
- procedure Generic_Iteration (Map : in Map_Type);
+ with procedure Process (Position : in Cursor) is <>;
+ procedure Generic_Iteration (Container : in Map);
private
@@ -918,12 +1986,11 @@
end Ada.Containers.Hashed_Maps;
-A object of type Map_Type contains a hash table, which is used
-to provide direct access to elements. The *size* of an object of type Map_Type
-object is the number of hash table entries it contains. If an object of type
-Map_Type is not otherwise initialized, it will be initialized with a size of 0.
-The *length* of an object of type Map_Type object is the number of elements
-it contains.
+A object of type Map contains a hash table, which is used to provide
+direct access to elements. The *size* of an object of type Map is the
+number of hash table entries it contains. The *length* of an object of type Map
+object is the number of elements it contains. If an object of type Map is not
+otherwise initialized, it will be initialized with a length of 0.
AARM Note
The expected implementation for a Map uses a hash table which is grown when
@@ -941,244 +2008,238 @@
There is no defined relationship between nodes in a map. Typically, iteration
will return nodes in the order that they are hashed in.
-Null_Cursor represents the null map cursor. If an object of type
-Cursor_Type is not otherwise initialized, it will be initialized to
-the same value as Null_Cursor.
-
-function "=" (Left, Right : Map_Type) return Boolean;
-
-If Left and Right denote the same map Map object, then the
-function returns immediately the value True. If Left and Right have
-different lengths, then the function returns the value False.
-Otherwise, it compares elements (and *only* elements -- keys do not
-participate in the computation of Map equality) in canonical order
-using the generic formal equality operator for elements. Any exception
-raised during evaluation of element equality is propagated.
+A map container may contain *empty elements*. Empty elements do not have a
+defined value.
+
+Empty_Map represents the empty Map object. It has a length of 0. If an object
+of type Map is not otherwise initialized, it will be initialized to the same
+value as Empty_Map.
+
+No_Element represents a cursor that designates no element. If an object of type
+Cursor is not otherwise initialized, it will be initialized to the same
+value as No_Element.
+
+function "=" (Left, Right : Map) return Boolean;
+
+If Left and Right denote the same map Map object, then the function returns
+immediately the value True. If Left and Right have different lengths, then the
+function returns the value False. Otherwise, it compares elements (and *only*
+elements -- keys do not participate in the computation of Map equality) in
+canonical order using the generic formal equality operator for elements. Any
+exception raised during evaluation of element equality is propagated.
The function Length returns the number of key/element pairs in Map.
-The function Is_Empty is equivalent to Length (Map) = 0.
+The function Is_Empty is equivalent to Length (Container) = 0.
Clear removes all the elements from Map. The size of Map is not affected. Any
exceptions raised during deallocation of storage propagated.
-Swap exchanges the internal nodes and hash table of Left and Right.
+procedure Move (Target : in out Map;
+ Source : in out Map);
-[Open issue: Do we really need this? It prevents an implementation that
-puts 'extra' information beyond the node pointer into the Cursor_Type. That
-means that the 'extra' information needed for iteration has to be in the nodes.
-
-Note that all of these objects are non-limited, so Swap is not strictly
-necessary. The one place that it would clearly help (sorting a vector of other
-containers) is also one place where it can't be used (Swap is not a parameter
-to Generic_Sort). All of the containers have Swap; they all could be dropped.]
+If the length of Target is greater than 0, then Move raises Constraint_Error.
+Otherwise, the internal hash table of Target is deallocated; then the internal
+hash table is removed from Source and moved to Target. Source has size 0 after
+a successful call to Move.
-procedure Insert (Map : in out Map_Type;
+procedure Insert (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type;
- Cursor : out Cursor_Type;
+ Position : out Cursor;
Success : out Boolean);
-If Length (Map) equals Size (Map), then Insert calls Resize to resize
-Map to some larger value. Insert then calls Hash to compute the hash value of
-Key; any exceptions raised by Hash are propagated. It then uses Is_Equal_Key
-to check if Key is already present in Map; any exceptions raised by
-Is_Equal_Key are propagated. If a key matches, Success returns
-False and Cursor designates the node with the matching key. Otherwise, Insert
+If Length (Container) equals Size (Container), then Insert calls Resize to
+resize Container to some larger value. Insert then calls Hash to compute the
+hash value of Key; any exceptions raised by Hash are propagated. It then uses
+Is_Equal_Key to check if Key is already present in Container; any exceptions
+raised by Is_Equal_Key are propagated. If a key matches, Success returns False
+and Position designates the node with the matching key. Otherwise, Insert
allocates a new node initialized to Key and New_Item and adds the node to
-Map. Success returns True and Cursor designates the
-newly-inserted node. Any exceptions raised during allocation are
-propagated and Map is not modified.
+Container. Success returns True and Position designates the newly-inserted
+node. Any exceptions raised during allocation are propagated and Container is
+not modified.
AARM Note:
Insert should only compare elements that hash to the same bucket in the hash
table.
-procedure Replace (Map : in out Map_Type;
+procedure Replace (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);
Replace inserts Key and New_Item as per Insert, with the difference that
-if Key is already in the map, then this operation assigns New_Item to the
-element associated with Key. Any exceptions raised during assignment
-are propagated.
+if Key is already in the map, then this operation assigns New_Item to
+the element associated with Key. Any exceptions raised during assignment
+are propagated. The element associated with Key is not an empty element after
+successful completion of this operation.
-procedure Insert (Map : in out Map_Type;
+procedure Insert (Container : in out Map;
Key : in Key_Type;
- Cursor : out Cursor_Type;
+ Position : out Cursor;
Success : out Boolean);
+
+Inserts Key into Container as per Insert (Container, Key, New_Item,
+Position, Success), with the difference that an empty element is inserted.
-Inserts Key into Map as per Insert (Map, Key, New_Item,
-Cursor, Success), with the difference that the element of a
-newly-inserted node is uninitialized, except for any controlled
-initialization or default-initialized components.
-
-procedure Delete (Map : in out Map_Type;
- Key : in Key_Type);
-
-If Length (Map) equals 0, then this operation has no effect.
-Otherwise, it calls Hash to compute the hash value of
-Key; any exceptions raised by Hash are propagated. It then uses Is_Equal_Key
-to check if Key is present in Map; any exceptions raised by Is_Equal_Key are
-propagated. If Key matches the key of a node, Delete removes the node from the
-map and then deallocates the node. Any exceptions raised during deallocation
-of storage are propagated.
+procedure Delete (Container : in out Map;
+ Key : in Key_Type);
+If Length (Container) equals 0, then this operation has no effect. Otherwise,
+it calls Hash to compute the hash value of Key; any exceptions raised by Hash
+are propagated. It then uses Is_Equal_Key to check if Key is present in
+Container; any exceptions raised by Is_Equal_Key are propagated. If Key matches
+the key of a node, Delete removes the node from the map and then deallocates
+the node. Any exceptions raised during deallocation of storage are propagated.
+
AARM Note:
-Find should only compare elements that hash to the same bucket in the hash
+Delete should only compare elements that hash to the same bucket in the hash
table.
-procedure Delete (Map : in out Map_Type;
- Cursor : in out Cursor_Type);
+procedure Delete (Container : in out Map;
+ Position : in out Cursor);
-If Cursor equals Null_Cursor, this operation has no effect. If
-Cursor does not designate a node that belongs to Map, program
-execution is erroneous. Otherwise, it calls Hash to computesthe hash value of
-the key of the node designated by Cursor; any exceptions raised by Hash are
-propagated. Delete then removes the node from the map and deallocates the node.
-Any exceptions raised during deallocation of storage are propagated.
-Cursor is set to Null_Cursor on return.
+If Position equals No_Element, this operation has no effect.
+Otherwise, it calls Hash to compute the hash value of the key of the node
+designated by Position; any exceptions raised by Hash are propagated. Delete
+then removes the node from the map and deallocates the node. Any exceptions
+raised during deallocation of storage are propagated. Position is set to
+No_Element on return.
-function Find (Map : Map_Type;
- Key : Key_Type) return Cursor_Type;
+function Find (Container : Map;
+ Key : Key_Type) return Cursor;
-If Length (Map) equals 0, then this function returns
-Null_Cursor. Otherwise, it calls Hash to compute the hash value of Key;
+If Length (Container) equals 0, then this function returns
+No_Element. Otherwise, it calls Hash to compute the hash value of Key;
any exceptions raised by Hash are propagated. It then uses Is_Equal_Key
-to check if Key is present in Map; any exceptions raised by Is_Equal_Key
-are propagated. If Key is present in Map, it returns an cursor
-designating the node with the matching key; otherwise, it returns
-Null_Cursor.
+to check if Key is present in Container; any exceptions raised by Is_Equal_Key
+are propagated. If Key is present in Container, it returns a cursor designating
+the node with the matching key; otherwise, it returns No_Element.
-AARM Notes:
+AARM Note:
Find should only compare elements that hash to the same bucket in the hash
table.
-
-Null_Cursor is the same as Back (Map); it's possible to compare against Back
-for consistency with other containers.
-The function Is_In is equivalent to Find (Map, Key) /= Null_Cursor.
+The function Is_In is equivalent to Find (Container, Key) /= No_Element.
-The function Element is equivalent to Element (Find (Map, Key)).
+The function Element is equivalent to Element (Find (Container, Key)).
-The function Size returns the size of Map.
+The function Size returns the size of Container.
-procedure Resize (Map : in out Map_Type;
- Size : in Size_Type);
+procedure Resize (Container : in out Map;
+ Size : in Size_Type);
-If Size (Map) is equal to or greater than Size, this operation has
-no effect. Otherwise, it allocates a new hash table whose length is
-a least the value Size. If the allocation fails, the exception is
-propagated and Map is not modified. It then rehashes the nodes in
-Map onto the new hash table. Any exception raised by Hash is
-propagated and the nodes that were moved onto the new hash table are
-lost. It replaces the old hash table with the new hash table, and
-then deallocates the old hash table. Any exceptions raised during
-deallocation are propagated.
+If Size (Container) is equal to or greater than Size, this operation has no
+effect. Otherwise, it allocates a new hash table whose length is at least the
+value Size. If the allocation fails, the exception is propagated and Container
+is not modified. It then rehashes the nodes in Container onto the new hash
+table. Any exception raised by Hash is propagated and the nodes that were moved
+onto the new hash table are lost. It replaces the old hash table with the new
+hash table, and then deallocates the old hash table. Any exceptions raised
+during deallocation are propagated.
-function First (Map : Map_Type) return Cursor_Type;
+function First (Container : Map) return Cursor;
-If Length (Map) = 0, then it returns Null_Cursor.
-Otherwise, it returns a that designates the first hashed node in Map.
+If Length (Container) = 0, then First returns No_Element. Otherwise,
+it returns a cursor that designates the first hashed node in Container.
AARM Note:
In a typical implementation, this will be the first node in the lowest numbered
hash bucket that contains a node.
-function Back (Map : Map_Type) return Cursor_Type;
-
-Returns Null_Cursor.
-
-AARM Note:
-This function is provided for compatibility with other containers.
-(Forward) active iteration for all containers can be written:
- declare
- I : Cursor_Type := First (M);
- The_End : Cursor_Type := Back (M); --here it is
- begin
- while I /= The_End loop
- E := Element (I);
- -- do something with E
- Increment (M, I);
- end loop;
- end;
-[Open issue: This implies that Vectors ought to have an Increment procedure.]
+function Next (Position : Cursor) return Cursor;
-function Succ (Map : Map_Type;
- Cursor : Cursor_Type) return Cursor_Type;
+Returns a cursor that designates the node that immediately follows
+Position. If there are no more nodes in the map identified by Position, it
+returns No_Element. If Position equals No_Element, then No_Element
+is returned.
+
+If there are no other intervening operations, calling Next in a loop
+starting with First (Container) shall return a cursor designating each
+node in the Container (other than First) exactly once, then return
+No_Element.
-If Cursor equals Null_Cursor, then Constraint_Error is propagated.
-Otherwise, Succ returns a cursor that designates the next node in Map.
-If there are no more nodes in Map, it returns Null_Cursor.
-
-If there are no other intervening operations, calling Succ in a loop starting
-with First (Map) shall return a cursor designating each node in the Map (other
-than First) exactly once, then return Null_Cursor.
-
-AARM Note
+AARM Notes
In a typical implementation, this will return the next node in a bucket; if
-Cursor is the last node in a bucket, this will return the first node in the
+Position is the last node in a bucket, this will return the first node in the
next non-empty bucket.
-The procedure Increment is equivalent to Cursor := Succ (Map, Cursor).
+A typical implementation will need to a keep a pointer at the map container
+in the cursor in order to implement this function.
-function Key (Cursor : Cursor_Type) return Key_Type;
+The procedure Next is equivalent to Position := Next (Position).
-If Cursor equals Null_Cursor, then Constraint_Error is propagated.
-Otherwise, this operation returns the key component of node designated
-by Cursor.
+function Has_Element (Position : Cursor) return Boolean;
+Returns True if Position designates an element, and returns False otherwise.
-generic
- type Key_Access is access constant Key_Type;
-function Generic_Key (Cursor : Cursor_Type) return Key_Access;
+AARM Note: To Be Honset: This function is may not detect cursors that
+designate deleted elements; such cursors are invalid (see below) and any
+use of them (including in this routine) is erroneous.
+
+function Key (Position : Cursor) return Key_Type;
-If Cursor equals Null_Cursor, then Constraint_Error is propagated.
-Otherwise, this operation returns an access value that designates a
-constant view of the key component of the node designated by Cursor.
+If Position equals No_Element, then Constraint_Error is propagated.
+Otherwise, this operation returns the key component of node designated
+by Position.
-The function Is_Equal_Key (Left, Right : Cursor_Type) is equivalent to
+The function Is_Equal_Key (Left, Right : Cursor) is equivalent to
Is_Equal_Key (Key (Left), Key (Right)).
-The function Is_Equal_Key (Left : Cursor_Type; Right : Key_Type) is
+The function Is_Equal_Key (Left : Cursor; Right : Key_Type) is
equivalent to Is_Equal_Key (Key (Left), Right).
-The function Is_Equal_Key (Left : Key_Type; Right : Cursor_Type) is
+The function Is_Equal_Key (Left : Key_Type; Right : Cursor) is
equivalent to Is_Equal_Key (Left, Key (Right)).
+
+function Element (Position : Cursor) return Element_Type;
+
+If Position equals No_Element, then Constraint_Error is propagated.
+Otherwise, this operation returns the element component of the node
+designated by Position.
+
+generic
+ with procedure Process (Element : in out Element_Type) is <>;
+procedure Generic_Update (Position : in Cursor);
+
+If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
+Generic_Update invokes the generic actual procedure bound to Process
+with the element on node designated by Position as the argument.
+
+The element designated by Position is not an empty element after successful
+completion of this operation.
+
+AARM Note: Since reading an empty element is a bounded error, attempting to
+use this procedure to replace empty elements may fail. Use Replace_Element
+to do that reliably.
+
+procedure Replace_Element (Position : in Cursor;
+ By : in Element_Type);
+
+If Position equals No_Element, then Constraint_Error is propagated.
+Otherwise this operation assigns By to the element on the node designed by
+Position. The element designated by Position is not an empty element after
+successful completion of this operation.
-function Element (Cursor : Cursor_Type) return Element_Type;
+AARM Note: Replace, Replace_Element, and Generic_Update are only ways that an
+element can change from empty to non-empty.
-If Cursor equals Null_Cursor, then Constraint_Error is propagated.
-Otherwise, this operation returns the element component of the node
-designated by Cursor.
generic
- type Element_Access is access all Element_Type;
-function Generic_Element (Cursor : Cursor_Type)
- return Element_Access;
-
-If Cursor equals Null_Cursor, then Constraint_Error is propagated.
-Otherwise, this operation returns an access value that designates a
-variable view of the element component of the node designated by
-Cursor.
-
-
-procedure Replace_Element
- (Cursor : in Cursor_Type;
- By : in Element_Type);
-
-If Cursor equals Null_Cursor, then Constraint_Error is propagated.
-Otherwise this operation assigns By to the element on the node designed
-by Cursor.
+ with procedure Process (Position : in Cursor) is <>;
+procedure Generic_Iteration (Container : in Map);
-generic
- with procedure Process (Cursor : in Cursor_Type) is <>;
-procedure Generic_Iteration (Map : in Map_Type);
+Generic_Iteration calls Process with a cursor that designates each node
+in the Container. Any exceptions raised during Process are propagated.
-Generic_Iteration calls Process with a cursor that designates each
-node in the Map. Any exceptions raised during Process are propagated.
+If Element_Type is unconstrained and definite, then the Element parameter
+shall be unconstrained.
+
+AARM Note: This means that the elements cannot be aliased nor directly
+allocated from the heap; it must be possible to change the discriminants
+of the element in place.
Legality Rules
@@ -1194,186 +2255,246 @@
be dropped if AI-344 or some other solution to nested controlled types is
adopted.
+Bounded (Run-Time) Errors
+
+Reading the value of an empty element by calling Element, Generic_Update,
+"=", or Generic_Iteration is a bounded error. The implementation may treat the
+element as having any valid value of the element type, or raise
+Constraint_Error or Program_Error.
+
+AARM Notes: For instance, a default initialized element could be returned. Or
+some previous value of an element. But returning random junk is not allowed
+if the type has if the type has default initial value(s).
+
+Assignment and streaming of empty elements are NOT bounded errors.
+This is consistent with regular composite types, for which assignment and
+streaming of uninitialized components do not cause a bounded error, but reading
+the uninitialized component does cause a bounded error.
+
+There are other operations which are defined in terms of the operations listed
+above.
+End AARM Notes.
+
+Erroneous Execution
+
+A Cursor value is *invalid* if any of the following have occurred since it was
+created:
+ * The map that contains the element it designates has been finalized;
+ * The map that contains the element it designates has been used as the
+ Source or Target of a call to Move;
+ * The element it designates has been deleted from the map.
+
+The result of "=" or Has_Element is unspecified if it is called with an invalid
+cursor parameter. Execution is erroneous if any other subprogram declared in
+Containers.Hashed_Maps is called with an invalid cursor parameter, or if the
+cursor designates an element in a different map object than the appropriate one
+specified in the call.
+
+AARM Notes: The list above is intended to be exhaustive. In other cases, a
+cursor value continues to designate its original element. For instance,
+cursor values survive the insertion and deletion of other nodes.
+
+While it is possible to check for these cases, in many cases the overhead
+necessary to make the check is substantial in time or space. Implementations
+are encouraged to check for as many of these cases as possible and raise
+Constraint_Error if detected.
+End AARM Notes.
+
Implementation Requirements
-No storage associated with a map Map_Type object shall be lost
-upon assignment or scope exit.
+No storage associated with a Map object shall be lost upon assignment or
+scope exit.
Implementation Advice
-Calls on Insert and Find should take constant time; that is, the time taken
-by a call on these routines should not increase significantly as the length of
-the map increases.
-
-[Open Issue: A sorted version of the container also is typical (with parameters
-similar to the ones of the Sorted_Set). This was left out to keep the size
-of the containers library manageable. Should it be reintroduced?
-One presumes it would be included in the secondary standard if it is not
-included here.]
-
-A.17.4 The Package Containers.String_Hashed_Maps
-
-The package Containers.String_Hashed_Maps provides private
-types Map_Type and Cursor_Type, and a set of operations for each
-type. It provides the same hashed map operations as the package
-Containers.Hashed_Maps does, with the difference that
-predefined type String is the key.
+The time taken by Insert and Find should take time on average
+roughly proportional to the log (base 2) of the length of the map.
+
+AARM Note
+We do not mean to overly constrain implementation stratgies here. However, it
+is important for portability that the performance of large containers has
+roughly the same factors on different implementations. If a program is moved
+to an implementation that take time proportional to the length of the map
+to find elements, that program could be unusable when the maps are large.
+We allow O(log N) access because the proportionality constant and caching
+*effects are likely to be larger than the log factor, and we don't want to
+discourage innovative implementations.
+
+
+A.17.5 The Package Containers.Ordered_Sets
+
+The language-defined package Containers.Ordered_Sets provides
+private types Set and Cursor, and a set of operations for each type. An
+ordered set container orders its elements per a specified relation.
+
+AARM Note: This is called "Ordered_Sets" so as to allow a possible
+future enhancement to include unsorted sets (which would be called
+"Sets") or hashed sets (which would be called "Hashed_Sets").
Static Semantics
-The declaration of the library package
-Containers.String_Hashed_Maps has the same contents as
-Containers.Hashed_Maps except:
+The package Containers.Ordered_Sets has the following declaration:
- * There is no generic formal Key_Type. Everywhere the formal type Key_Type
- is specified, it is systematically replaced by type String.
- * The generic formal function Hash has a named default, the function
- Ada.Strings.Hash.
- * The Generic_Key function is omitted.
+generic
+ type Element_Type is private;
-A.17.5 The Package Containers.Wide_String_Hashed_Maps
+ with function "<" (Left, Right : Element_Type) return Boolean is <>;
-Static Semantics
+ with function "=" (Left, Right : Element_Type) return Boolean is <>;
-The declaration of the library package Containers.Wide_String_Hashed_Maps has
-the same contents as Containers.String_Hashed_Maps except that everywhere the
-formal type String is specified, it is systematically replaced by type
-Wide_String. The named default for generic formal function Hash is replaced
-by Ada.Strings.Wide_Hash.
+package Ada.Containers.Ordered_Sets is
+ pragma Preelaborate (Ordered_Sets);
+ type Set is private;
+ type Cursor is private;
-A.17.6 The Package Containers.Sorted_Sets
+ Empty_Set : constant Set;
-The language-defined package Containers.Sorted_Sets provides
-private types Set_Type and Cursor_Type, and a set of operations
-for each type. A sorted set container orders its elements per a
-specified relation.
+ No_Element : constant Cursor;
-AARM Note: This is called "Sorted_Sets" so as to allow a possible future
-enhancement to include unsorted sets (which would be called "Sets").
+ function "=" (Left, Right : Set) return Boolean;
-Static Semantics
+ function "<" (Left, Right : Set) return Boolean;
-The package Containers.Sorted_Sets has the following declaration:
+ function "<=" (Left, Right : Set) return Boolean;
-generic
+ function ">" (Left, Right : Set) return Boolean;
- type Element_Type is private;
+ function ">=" (Left, Right : Set) return Boolean;
- with function "<" (Left, Right : Element_Type) return Boolean is <>;
+ function Length (Container : Set) return Size_Type;
- with function "=" (Left, Right : Element_Type) return Boolean is <>;
+ function Is_Empty (Container : Set) return Boolean;
-package Ada.Containers.Sorted_Sets is
+ procedure Clear (Container : in out Set);
- pragma Preelaborate;
+ procedure Move (Target : in out Set;
+ Source : in out Set);
- type Set_Type is private;
+ procedure Insert (Container : in out Set;
+ New_Item : in Element_Type;
+ Position : out Cursor;
+ Success : out Boolean);
- type Cursor_Type is private;
+ procedure Delete (Container : in out Set;
+ Item : in Element_Type);
- Null_Cursor : constant Cursor_Type;
+ procedure Delete (Container : in out Set;
+ Position : in out Cursor);
- function "=" (Left, Right : Set_Type) return Boolean;
+ procedure Delete_Sans_Increment (Container : in out Set;
+ Position : in out Cursor);
- function "<" (Left, Right : Set_Type) return Boolean;
+ procedure Delete_First (Container : in out Set);
- function "<=" (Left, Right : Set_Type) return Boolean;
+ procedure Delete_Last (Container : in out Set);
- function ">" (Left, Right : Set_Type) return Boolean;
+ procedure Union (Target : in out Set;
+ Source : in Set);
- function ">=" (Left, Right : Set_Type) return Boolean;
+ procedure Union (Target : in out Set;
+ Left, Right : in Set);
- function Length (Set : Set_Type) return Size_Type;
+ function Union (Left, Right : Set) return Set;
- function Is_Empty (Set : Set_Type) return Boolean;
+ function "or" (Left, Right : Set) return Set renames Union;
- procedure Clear (Set : in out Set_Type);
+ procedure Intersection (Target : in out Set;
+ Source : in Set);
- procedure Swap (Left, Right : in out Set_Type);
+ procedure Intersection (Target : in out Set;
+ Left, Right : in Set);
- procedure Insert (Set : in out Set_Type;
- New_Item : in Element_Type;
- Cursor : out Cursor_Type;
- Success : out Boolean);
+ function Intersection (Left, Right : Set) return Set;
- procedure Insert (Set : in out Set_Type;
- Position : in Cursor_Type;
- New_Item : in Element_Type;
- Cursor : out Cursor_Type;
- Success : out Boolean);
+ function "and" (Left, Right : Set) return Set renames Intersection;
- procedure Delete (Set : in out Set_Type;
- Item : in Element_Type);
+ procedure Difference (Target : in out Set;
+ Source : in Set);
- procedure Delete (Set : in out Set_Type;
- Cursor : in out Cursor_Type);
+ procedure Difference (Target : in out Set;
+ Left, Right : in Set);
- procedure Delete_Sans_Increment (Set : in out Set_Type;
- Cursor : in out Cursor_Type);
+ function Difference (Left, Right : Set) return Set;
- procedure Delete_First (Set : in out Set_Type);
+ function "-" (Left, Right : Set) return Set renames Difference;
- procedure Delete_Last (Set : in out Set_Type);
+ procedure Symmetric_Difference (Target : in out Set;
+ Source : in Set);
- function Is_In (Item : Element_Type;
- Set : Set_Type)
+ procedure Symmetric_Difference (Target : in out Set;
+ Left, Right : in Set);
+
+ function Symmetric_Difference (Left, Right : Set) return Set;
+
+ function "xor" (Left, Right : Set) return Set renames
+ Symmetric_Difference;
+
+ function Is_Subset (Item : Set;
+ Container : Set)
+ return Boolean;
+
+ function Is_Disjoint (Item : Set;
+ Container : Set)
+ return Boolean;
+
+ function Is_In (Item : Element_Type;
+ Container : Set)
return Boolean;
+
+ function Find (Container : Set;
+ Item : Element_Type)
+ return Cursor;
- function Find (Set : Set_Type;
- Item : Element_Type)
- return Cursor_Type;
+ function First (Container : Set) return Cursor;
- function Lower_Bound (Set : Set_Type;
- Item : Element_Type)
- return Cursor_Type;
+ function First_Element (Container : Set) return Element_Type;
- function Upper_Bound (Set : Set_Type;
- Item : Element_Type)
- return Cursor_Type;
+ function Last (Container : Set) return Cursor;
- function First (Set : Set_Type) return Cursor_Type;
+ function Last_Element (Container : Set) return Element_Type;
- function First_Element (Set : Set_Type) return Element_Type;
+ function Next (Position : Cursor) return Cursor;
- function Last (Set : Set_Type) return Cursor_Type;
+ function Previous (Position : Cursor) return Cursor;
- function Last_Element (Set : Set_Type) return Element_Type;
+ procedure Next (Position : in out Cursor);
- function Back (Set : Set_Type) return Cursor_Type;
+ procedure Previous (Position : in out Cursor);
- function Succ (Cursor : Cursor_Type) return Cursor_Type;
+ function Has_Element (Position : Cursor) return Boolean;
- function Pred (Cursor : Cursor_Type) return Cursor_Type;
+ function "<" (Left, Right : Cursor) return Boolean;
- procedure Increment (Cursor : in out Cursor_Type);
+ function ">" (Left, Right : Cursor) return Boolean;
- procedure Decrement (Cursor : in out Cursor_Type);
+ function "<" (Left : Cursor; Right : Element_Type)
+ return Boolean;
- function "<" (Left, Right : Cursor_Type) return Boolean;
+ function ">" (Left : Cursor; Right : Element_Type)
+ return Boolean;
- function "<" (Left : Cursor_Type; Right : Element_Type)
+ function "<" (Left : Element_Type; Right : Cursor)
return Boolean;
- function "<" (Left : Element_Type; Right : Cursor_Type)
+ function ">" (Left : Element_Type; Right : Cursor)
return Boolean;
- function Element (Cursor : Cursor_Type) return Element_Type;
+ function Element (Position : Cursor) return Element_Type;
generic
- type Element_Access is access constant Element_Type;
- function Generic_Element
- (Cursor : Cursor_Type) return Element_Access;
+ with procedure Process (Element : in out Element_Type) is <>;
+ procedure Generic_Update (Position : in Cursor);
generic
- with procedure Process (Cursor : in Cursor_Type) is <>;
- procedure Generic_Iteration (Set : in Set_Type);
+ with procedure Process (Position : in Cursor) is <>;
+ procedure Generic_Iteration (Container : in Set);
generic
- with procedure Process (Cursor : in Cursor_Type) is <>;
- procedure Generic_Reverse_Iteration (Set : in Set_Type);
+ with procedure Process (Position : in Cursor) is <>;
+ procedure Generic_Reverse_Iteration (Container : in Set);
generic
@@ -1388,32 +2509,30 @@
package Generic_Keys is
function Is_In (Key : Key_Type;
- Container : Set_Type)
+ Container : Set)
return Boolean;
- function Find (Container : Set_Type;
+ function Find (Container : Set;
Key : Key_Type)
- return Cursor_Type;
+ return Cursor;
- function Element (Container : Set_Type;
+ function Element (Container : Set;
Key : Key_Type)
return Element_Type;
-
- function Lower_Bound (Container : Set_Type;
- Key : Key_Type)
- return Cursor_Type;
-
- function Upper_Bound (Container : Set_Type;
- Key : Key_Type)
- return Cursor_Type;
- procedure Delete (Container : in out Set_Type;
+ procedure Delete (Container : in out Set;
Key : in Key_Type);
+
+ function "<" (Left : Cursor; Right : Key_Type)
+ return Boolean;
+
+ function ">" (Left : Cursor; Right : Key_Type)
+ return Boolean;
- function "<" (Left : Cursor_Type; Right : Key_Type)
+ function "<" (Left : Key_Type; Right : Cursor)
return Boolean;
- function "<" (Left : Key_Type; Right : Cursor_Type)
+ function ">" (Left : Key_Type; Right : Cursor)
return Boolean;
generic
@@ -1422,41 +2541,29 @@
(Element : in out Element_Type;
Key : in Key_Type) is <>;
- package Generic_Insertion is
+ procedure Generic_Insertion (Container : in out Set;
+ Key : in Key_Type;
+ Position : out Cursor;
+ Success : out Boolean);
- procedure Insert (Container : in out Set_Type;
- Key : in Key_Type;
- Cursor : out Cursor_Type;
- Success : out Boolean);
-
- procedure Insert (Container : in out Set_Type;
- Position : in Cursor_Type;
- Key : in Key_Type;
- Cursor : out Cursor_Type;
- Success : out Boolean);
-
- end Generic_Insertion;
-
end Generic_Keys;
private
... -- not specified by the language
-end Ada.Containers.Sorted_Sets;
+end Ada.Containers.Ordered_Sets;
-When a sorted set container elaborates, it automtically allocates a
-sentinel node. The element of the sentinel node is uninitialized,
-except for any controlled initialization or default-initialized
-components. The sentinel is not included in the count of elements in
-the container, and it cannot be deleted.
-
-Null_Cursor represents the null sorted set cursor. If an object of
-type Cursor_Type is not otherwise initialized, it will be initialized
-to the same value as Null_Cursor.
+Empty_Set represents the empty ordered set. If an object of type Set is
+not otherwise initialized, it will be initialized to the same value as
+Empty_Set.
-function "=" (Left, Right : Set_Type) return Boolean;
+No_Element represents a cursor that designates no element. If an object of type
+Cursor is not otherwise initialized, it will be initialized to the same
+value as No_Element.
+function "=" (Left, Right : Set) return Boolean;
+
If Left and Right denote the same object, then the function returns
True. If Left and Right have different lengths, then the function
returns False. Otherwise, it compares elements in sequential order
@@ -1466,7 +2573,7 @@
False. Otherwise if all corresponding elements compare True, the
function returns True.
-function "<" (Left, Right : Set_Type) return Boolean;
+function "<" (Left, Right : Set) return Boolean;
If Left denotes the same object as Right, then the function returns
False. Otherwise, it compares elements in sequential order using the
@@ -1485,255 +2592,307 @@
The function ">=" is equivalent to not (Left < Right).
-The function Length returns the number of elements in Set.
+The function Length returns the number of elements in Container.
-The function Is_Empty is equivalent to Length (Set) = 0.
+The function Is_Empty is equivalent to Length (Container) = 0.
-Clear removes all the nodes in Set (except for its sentinel), and
-sets the length to 0. Any exceptions raised during deallocation of
-storage are propagated.
+Clear removes all the nodes in Set, and sets the length to 0. Any
+exceptions raised during deallocation of storage are propagated.
-Swap exchanges all the nodes (including the sentinel) of Left and Right.
+procedure Move (Target : in out Set;
+ Source : in out Set);
-procedure Insert (Set : in out Set_Type;
+If the length of Target is greater than 0, then Move raises
+Constraint_Error. Otherwise, the internal nodes of Source are removed and
+moved to Target. The length of Source is 0 after a sucessful call to Move.
+
+
+procedure Insert (Container : in out Set;
New_Item : in Element_Type;
- Cursor : out Cursor_Type;
+ Position : out Cursor;
Success : out Boolean);
-Insert compares New_Item to the elements in Set using the generic
+Insert compares New_Item to the elements in Container using the generic
formal less-than operator for elements. Any exceptions raised by the
less-than operator are propagated. If an element equivalent (see below)
-to New_Item is already in Set, Success is False and Cursor
+to New_Item is already in Container, Success is False and Position
designates the node containing the element. Otherwise, it allocates a
new node whose element is initialized to New_Item. Success returns True
-and Cursor designates the newly-inserted node. Any exceptions raised
-during allocation are propagated and Set is not modified.
+and Position designates the newly-inserted node. Any exceptions raised
+during allocation are propagated and Container is not modified.
The equality operator for elements is not used by this operation.
Insert compares elements for "equivalence," which for elements E1 and E2
is defined as "not (E1 < E2) and not (E2 < E1)".
-procedure Insert (Set : in out Set_Type;
- Position : in Cursor_Type;
- New_Item : in Element_Type;
- Cursor : out Cursor_Type;
- Success : out Boolean);
+procedure Delete (Container : in out Set;
+ Item : in Element_Type);
-Equivalent to Insert (Set, New_Item, Cursor, Success), with the
-addition of a Position parameter, which specifies a hint about where to
-beging searching for an element equivalent to New_Item. If Position
-equals Null_Cursor, the operation is equivalent to the Position-less
-Insert. If Position does not designate a node that belongs to
-Set, program execution is erroneous. For a hint to be useful, it
-should designate a node containing an element that would be adjacent to
-New_Item, were it in the Set.
-
-
-procedure Delete (Set : in out Set_Type;
- Item : in Element_Type);
-
-Delete searches Set for an element equivalent to Item, using the
-generic formal less-than operator for elements. Any exceptions raised
-by less-than are propagated. If there is an element in Set
-equivalent to Item, the node containing the element is removed from
-Set and deallocated. Any exceptions raised during deallocation of
-storage are propagated.
+Delete searches Container for an element equivalent to Item, using the
+generic formal less-than operator for elements. Any exceptions raised by
+less-than are propagated. If there is an element in Container equivalent
+to Item, the node containing the element is removed from Container. Any
+exceptions raised during deallocation of storage (if any) are propagated.
+AARM Note: The node may be deallocated now, or it may be saved and reused
+later.
-procedure Delete (Set : in out Set_Type;
- Cursor : in out Cursor_Type);
+procedure Delete (Container : in out Set;
+ Position : in out Cursor);
-If Cursor equals Null_Cursor or Back (Set), the operation has
-no effect. If Cursor does not designate a node that belongs to
-Set, program execution is erroneous. Otherwise, Delete removes
-the node designated by Cursor from Set, and then deallocates the
-node. Any exception raised during deallocation of storage is
-propagated. The cursor value returned designates the successor of the
-node deleted.
+If Position equals No_Element, the operation has no effect. Otherwise, Delete
+removes the node designated by Position from Container. Any exception raised
+during deallocation of storage (if any) is propagated.
+The cursor value returned designates the successor of the node deleted.
-procedure Delete_Sans_Increment (Set : in out Set_Type;
- Cursor : in out Cursor_Type);
+procedure Delete_Sans_Increment (Container : in out Set;
+ Position : in out Cursor);
-Equivalent to Delete (Set, Cursor), with the difference that the
-cursor value returned equals Null_Cursor.
+Equivalent to Delete (Container, Position), with the difference that the
+cursor value returned equals No_Element.
-procedure Delete_First (Set : in out Set_Type);
+procedure Delete_First (Container : in out Set);
-If Set is empty, the operation has no effect. Otherwise the node
-designated by First (Set) is removed from Set and then
-deallocated. Any exception raised during deallocation of storage is
-propagated.
+If Container is empty, the operation has no effect. Otherwise the node
+designated by First (Container) is removed from Container. Any exception
+raised during deallocation of storage (if any) is propagated.
-procedure Delete_Last (Set : in out Set_Type);
+procedure Delete_Last (Container : in out Set);
-If Set is empty, the operation has no effect. Otherwise the node
-designated by Last (Set) is removed from Set and then
-deallocated. Any exception raised during deallocation of storage is
-propagated.
+If Container is empty, the operation has no effect. Otherwise the node
+designated by Last (Container) is removed from Container. Any exception
+raised during deallocation of storage (if any) is propagated.
-function Find (Set : Set_Type;
- Item : Element_Type) return Cursor_Type;
+procedure Union (Target : in out Set;
+ Source : in Set);
-The Find operation searches for the element equivalent to Item, using
-the generic formal less-than operator for elements. Any exception
-raised by less-than is propagated. If it finds an equivalent element,
-it returns a cursor designating the node that contains the element.
-Otherwise it returns Back (Set).
+If Target denotes the same object as Source, the operation has no
+effect. Otherwise, the elements of Source that are not equivalent to
+items already in Target are inserted into Target.
-The function Is_In is equivalent to Find (Set, Item) /= Back (Set).
-function Lower_Bound (Set : Set_Type;
- Item : Element_Type) return Cursor_Type;
+procedure Union (Target : in out Set;
+ Left, Right : in Set);
-The Lower_Bound operation searches for the smallest element not less
-than Item, using the generic formal less-than operator for elements.
-Any exception raised by less-than is propagated. If there is an element
-in Set that is not less than Item, it returns a cursor
-designating the node containing the element. Otherwise it returns Back
-(Set).
-
-function Upper_Bound
- (Set : Set_Type;
- Item : Element_Type) return Cursor_Type;
-
-The Upper_Bound operation searches for the smallest element greater than
-Item, using the generic formal less-than operator for elements. Any
-exception raised by less-than is propagated. If there is an element in
-Set that is greater than Item, it returns a cursor designating
-the node containing the element. Otherwise it returns Back (Set).
+Equivalent to Target := Union (Left, Right).
-function First (Set : Set_Type) return Cursor_Type;
-Returns a cursor that designates the node containing the smallest
-element. If Set is empty, it returns Back (Set).
+function Union (Left, Right : Set) return Set;
-function First_Element (Set : Set_Type) return Element_Type;
+Returns a set comprising all of the elements of Left, and the elements
+of Right that are not equivalent to elements of Left.
-If Set is empty, then Constraint_Error is propagated. Otherwise,
-it returns the element on the node designated by First (Set).
-function Last (Set : Set_Type) return Cursor_Type;
+procedure Intersection (Target : in out Set;
+ Source : in Set);
-Returns a cursor that designates the node containing the greatest
-element. If Set is empty, it returns Back (Set).
+If Target denotes the same object as Source, the operation has no
+effect. Otherwise, it deletes all the elements of Target that are
+not equivalent to the corresponding elements of Source.
+
+
+procedure Intersection (Target : in out Set;
+ Left, Right : in Set);
+
+Equivalent to Target := Intersection (Left, Right).
+
+
+function Intersection (Left, Right : Set) return Set;
+
+Returns a set comprising all the elements of Left that are equivalent to
+the corresponding elements of Right.
+
+
+procedure Difference (Target : in out Set;
+ Source : in Set);
+
+If Target denotes the same object as Source, then the operation
+clears Target. Otherwise, it deletes the elements of Target that
+are equivalent to elements of Source.
+
+
+procedure Difference (Target : in out Set;
+ Left, Right : in Set);
+
+Equivalent to Target := Difference (Left, Right).
+
+
+function Difference (Left, Right : Set) return Set;
+
+Returns a set comprising the elements of Left that are not equivalent to
+the corresponding elements of Right.
+
+
+procedure Symmetric_Difference (Target : in out Set;
+ Source : in Set);
+
+If Target denotes the same object as Source, then the operation
+clears Target. Otherwise, it deletes the elements of Target that
+are equivalent to elements of Source, and inserts the elements are
+Source that are not equivalent to the corresponding elements of
+Target.
+
+
+procedure Symmetric_Difference (Target : in out Set;
+ Left, Right : in Set);
+
+Equivalent to Target := Symmetric_Difference (Left, Right).
+
+
+function Symmetric_Difference (Left, Right : Set) return Set;
+
+Returns a set comprising the elements of Left that are not equivalent to
+the corresponding elements of Right, and the elements of Right that are
+not equivalent to the corresponding elements of Left.
+
+
+function Is_Subset (Item : Set;
+ Container : Set)
+ return Boolean;
+
+If Item denotes the same object as Container, then Is_Subset returns
+True. If Length (Item) is greater than Length (Container), then it
+returns False. If an element of Item is not equivalent to an element of
+Container, the function returns False. Otherwise it returns True.
+
+
+function Is_Disjoint (Item : Set;
+ Container : Set)
+ return Boolean;
+
+If an element of Item is equivalent to an element of Container, then
+Is_Disjoint returns False. Otherwise it returns True.
+
-function Last_Element (Set : Set_Type) return Element_Type;
+function Find (Container : Set;
+ Item : Element_Type) return Cursor;
-If Set is empty, then Constraint_Error is propagated. Otherwise,
-it returns the element on the node designated by Last (Set).
+The Find operation searches for the element equivalent to Item, using
+the generic formal less-than operator for elements. Any exception
+raised by less-than is propagated. If it finds an equivalent element,
+it returns a cursor designating the node that contains the element.
+Otherwise it returns No_Element.
+
+The function Is_In is equivalent to Find (Set, Item) /= No_Element.
+
+function First (Container : Set) return Cursor;
+
+Returns a cursor that designates the node containing the smallest
+element. If Container is empty, it returns No_Element.
-function Back (Set : Set_Type) return Cursor_Type;
+function First_Element (Container : Set) return Element_Type;
-Returns a cursor that designates the sentinel node.
+If Container is empty, then Constraint_Error is propagated. Otherwise,
+it returns the element on the node designated by First (Container).
+function Last (Container : Set) return Cursor;
-function Succ (Cursor : Cursor_Type) return Cursor_Type;
+Returns a cursor that designates the node containing the greatest
+element. If Container is empty, it returns No_Element.
+
+function Last_Element (Container : Set) return Element_Type;
-If Cursor equals Null_Cursor, then Constraint_Error is propagated.
-Otherwise it returns the successor of the node designated by Cursor.
+If Container is empty, then Constraint_Error is propagated. Otherwise,
+it returns the element on the node designated by Last (Container).
-AARM NOTE
-The successor of Last is Back, and the successor of Back is First. If
-the Set is empty, then First, Last, and Back all designate the
-sentinel node.
+function Next (Position : Cursor) return Cursor;
+If Position equals No_Element, then No_Element is returned. Otherwise
+it returns the successor of the node designated by Position.
-function Pred (Cursor : Cursor_Type) return Cursor_Type;
+function Previous (Position : Cursor) return Cursor;
-If Cursor equals Null_Cursor, then Constraint_Error is propagated.
-Otherwise it returns the predecessor of the node designated by Cursor.
+If Position equals No_Element, then No_Element is returned. Otherwise
+it returns the predecessor of the node designated by Position.
-AARM NOTE
-The predecessor of First is Back, and the predecessor of Back is Last.
+The procedure Next is equivalent to Position := Next (Position).
+The procedure Previous is equivalent to Position := Previous (Position).
-The procedure Increment is equivalent to Cursor := Succ (Cursor).
+function Has_Element (Position : Cursor) return Boolean;
-The procedure Decrement is equivalent to Cursor := Pred (Cursor).
+Returns True if Position designates an element, and returns False otherwise.
-The function "<" (Left, Right : Cursor_Type) is equivalent to Element
+AARM Note: To Be Honset: This function is may not detect cursors that
+designate deleted elements; such cursors are invalid (see below) and any
+use of them (including in this routine) is erroneous.
+
+The function "<" (Left, Right : Cursor) is equivalent to Element
(Left) < Element (Right).
+
+The function ">" (Left, Right : Cursor) is equivalent to Element
+(Right) < Element (Left).
-The function "<" (Left : Cursor_Type; Right : Element_Type) is
+The function "<" (Left : Cursor; Right : Element_Type) is
equivalent to Element (Left) < Right.
-The function "<" (Left : Element_Type; Right : Cursor_Type) is
+The function ">" (Left : Cursor; Right : Element_Type) is
+equivalent to Right < Element (Left).
+
+The function "<" (Left : Element_Type; Right : Cursor) is
equivalent to Left < Element (Right).
+The function ">" (Left : Element_Type; Right : Cursor) is
+equivalent to Element (Right) < Left.
-function Element (Cursor : Cursor_Type) return Element_Type;
+function Element (Position : Cursor) return Element_Type;
-If Cursor equals Null_Cursor or Back (Set), then Constraint_Error is propagated.
-Otherwise, it returns the element on the node designated by Cursor.
+If Position equals No_Element, then Constraint_Error is propagated.
+Otherwise, it returns the element on the node designated by Position.
generic
- type Element_Access is access Element_Type;
-function Generic_Element (Cursor : Cursor_Type)
- return Element_Access;
-
-If Cursor equals Null_Cursor or Back (Set), then Constraint_Error is
-propagated. Otherwise, it returns an access value that designates a constant
-view of the the element on the node designated by Cursor.
+ with procedure Process (Element : in out Element_Type) is <>;
+procedure Generic_Update (Position : in Cursor);
+
+If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
+Generic_Update invokes the generic actual procedure bound to Process
+with the element on node designated by Position as the argument.
generic
- with procedure Process (Cursor : in Cursor_Type) is <>;
-procedure Generic_Iteration (Set : in Set_Type);
+ with procedure Process (Position : in Cursor) is <>;
+procedure Generic_Iteration (Container : in Set);
-Invokes Process with a cursor that designates each (non-sentinel)
-node in Set.
+Invokes Process with a cursor that designates each node in Container.
generic
- with procedure Process (Cursor : in Cursor_Type) is <>;
-procedure Generic_Reverse_Iteration (Set : in Set_Type);
+ with procedure Process (Position : in Cursor) is <>;
+procedure Generic_Reverse_Iteration (Container : in Set);
-Iterates over the nodes in Set as per Generic_Iteration, with the
+Iterates over the nodes in Container as per Generic_Iteration, with the
difference that the nodes are traversed in reverse order.
The package Generic_Keys provides operations that allow set manipulation
in terms of a key (typically, a portion of an element) instead of a
complete element.
-
-The operations in package Generic_Keys named Is_In, Find, Element, Lower_Bound,
-Upper_Bound, Delete, and operators designated "<", are equivalent to the
-corresponding operations in the parent package, with the difference that the
-Key subprogram parameter is compared to elements in the container using the
-Generic_Keys generic formal less-than operators.
-
-procedure Insert (Container : in out Set_Type;
- Key : in Key_Type;
- Cursor : out Cursor_Type;
- Success : out Boolean);
-Insert compares Key to elements already in Container using the
-Generic_Keys generic formal less-than operators for keys and elements.
-Any exceptions raised by less-than are propagated. If an element
-equivalent to Key is already in Container, Success is False and Cursor
-designates the node containing the element equivalent to Key.
+The operations in package Generic_Keys named Is_In, Find, Element,
+Delete, and operators designated "<" and ">", are equivalent to the
+corresponding operations in the parent package, with the difference that
+the Key subprogram parameter is compared to elements in the container
+using the Generic_Keys generic formal relational operators.
+
+procedure Generic_Insertion (Container : in out Set;
+ Key : in Key_Type;
+ Position : out Cursor;
+ Success : out Boolean);
+
+Generic_Insertion compares Key to elements already in Container using
+the Generic_Keys generic formal relational operators for keys and
+elements. Any exceptions raised by less-than are propagated. If an
+element equivalent to Key is already in Container, Success is False and
+Position designates the node containing the element equivalent to Key.
Otherwise, it allocates a new node and then calls Set_Key with the
element of the node and Key as the parameters. Any exceptions raised
-during allocation are propagated. If Set_Key raises an exception,
-Insert deallocates the node and then propagates the exception.
-Otherwise, it inserts the node into the Container. Success returns True
-and Cursor designates the newly-inserted node.
-
-procedure Insert (Container : in out Set_Type;
- Position : in Cursor_Type;
- Key : in Key_Type;
- Cursor : out Cursor_Type;
- Success : out Boolean);
-
-Equivalent to Insert (Container, Key, Cursor, Success), with the
-addition of a Position parameter, which specifies a hint about where to
-begin searching for an element equivalent to Key. If Position equals
-Null_Cursor then this operation is equivalent to the Position-less
-Insert. If Position does not designate a node that belongs to Container
-then program execution is erroneous.
+during allocation are propagated. If Set_Key raises an exception, Insert
+deallocates the node and then propagates the exception. Otherwise, it
+inserts the node into the Container. Success returns True and Position
+designates the newly-inserted node.
Legality Rules
-An instantiation of Containers.Sorted_Sets shall be at the library level.
+An instantiation of Containers.Ordered_Sets shall be at the library level.
AARM Note
A implementation will typically need to use controlled types to insure that
@@ -1745,25 +2904,216 @@
adopted.
Erroneous Execution
+
+A Cursor value is *invalid* if any of the following have occurred since it was
+created:
+ * The set that contains the element it designates has been finalized;
+ * The set that contains the element it designates has been used as the
+ Source or Target of a call to Move;
+ * The element it designates has been deleted from the set
+
+The result of "=" or Has_Element is unspecified if it is called with an invalid
+cursor parameter. Execution is erroneous if any other subprogram declared in
+Containers.Ordered_Sets is called with an invalid cursor parameter, or
+if the cursor designates an element in a different set object than the
+appropriate one specified in the call.
+
+AARM Notes: The list above is intended to be exhaustive. In other cases, a
+cursor value continues to designate its original element. For instance,
+cursor values survive the insertion and deletion of other nodes.
+
+While it is possible to check for these cases, in many cases the overhead
+necessary to make the check is substantial in time or space. Implementations
+are encouraged to check for as many of these cases as possible and raise
+Constraint_Error if detected.
+End AARM Notes.
+
+Execution is erroneous if the actual subprogram of an instantiation of
+Generic_Update changes the element so that the formal subprogram "<" could give
+different results than before the modification.
+
+AARM Note: This means that the implementation is not required to check and
+fix the ordering if Generic_Update changes its position within the set. It
+would be possible to check for this, but it would be as expensive as a new
+insertion to do for the reference red-black tree. That would defeat the
+purpose of the Generic_Update routine (a cheap in-place update), so we didn't
+require it.
+
+Implementation Requirements
+
+No storage associated with an ordered set object shall be lost upon assignment
+or scope exit.
+
+Implementation Advice
+
+The time taken by Insert and Find should take time better than
+roughly proportional to the length of the set.
+
+AARM Note
+A balanced (red-black) tree for keys has O(log N) worst-case performance. Note
+that a O(N) worst-case implementation (like a list) would be wrong.
+We do not mean to overly constrain implementation stratgies here. However, it
+is important for portability that the performance of large containers has
+roughly the same factors on different implementations. If a program is moved
+to an implementation that takes O(N log N) to find elements, that program could
+be unusable when the sets are large. We allow <O(N) access because the
+proportionality constant and caching effects are likely to be larger than the
+log factor, and we don't want to discourage innovative implementations.
+
+
+A.17.6 The Package Containers.Indefinite_Vectors
+
+The language-defined package Containers.Indefinite_Vectors provides a
+private type Vector and a set of operations. It provides the same
+operations as the package Vectors does, with the difference that the
+generic formal Element_Type is indefinite.
+
+Static Semantics
+
+The declaration of the library package Containers.Indefinite_Vectors has
+the same contents as Containers.Vectors except:
+
+ * The generic formal Element_Type is indefinite.
+
+ * The Element parameter of formal subprogram Process of Generic_Update
+ and Generic_Update_by_Index may be constrained even if Element_Type is
+ unconstrained.
+
+
+A.17.7 The Package Containers.Indefinite_Doubly_Linked_Lists
+
+The language-defined package Containers.Indefinite_Doubly_Linked_Lists
+provides private types List and Cursor, and a set of operations for each
+type. It provides the same operations as the package Doubly_Linked_Lists
+does, with the difference that the generic formal Element_Type is
+indefinite.
+
+Static Semantics
+
+The declaration of the library package
+Containers.Indefinite_Doubly_Linked_Lists has the same contents as
+Containers.Doubly_Linked_Lists except:
+
+ * The generic formal Element_Type is indefinite.
+
+ * The Element parameter of formal subprogram Process of Generic_Update
+ may be constrained even if Element_Type is unconstrained.
+
+
+A.17.8 The Package Containers.Indefinite_Hashed_Maps
+
+The language-defined package Containers.Indefinite_Hashed_Maps provides
+private types Map and Cursor, and a set of operations for each type. It
+provides the same operations as the package Hashed_Maps does, with the
+difference that the generic formal types Key_Type and Element_Type are
+indefinite.
+
+Static Semantics
+
+The declaration of the library package Containers.Indefinite_Hashed_Maps
+has the same contents as Containers.Hashed_Maps except:
+
+ * The generic formal Key_Type is indefinite.
+
+ * The generic formal Element_Type is indefinite.
+
+ * The Element parameter of formal subprogram Process of Generic_Update
+ may be constrained even if Element_Type is unconstrained.
+
+
+A.17.9 The Package Containers.Indefinite_Ordered_Sets
+
+The language-defined package Containers.Indefinite_Ordered_Sets provides
+private types Set and Cursor, and a set of operations for each type. It
+provides the same operations as the package Ordered_Sets does, with the
+difference that the generic formal type Element_Type is indefinite.
+
+Static Semantics
+
+The declaration of the library package Containers.Indefinite_Ordered_Sets
+has the same contents as Containers.Ordered_Sets except:
+
+ * The generic formal Element_Type is indefinite.
+
+ * Instead of Set_Key, the generic formal operation of generic
+ operation Generic_Insertion is:
+
+ with function New_Element (Key : Key_Type) return Element_Type is <>;
+
+ * The Element parameter of formal subprogram Process of Generic_Update
+ may be constrained even if Element_Type is unconstrained.
+
+
+A.17.10 Array Sorting
+
+The language-defined procedures Containers.Generic_Array_Sort and
+Containers.Generic_Constrained_Array_Sort provide sorting on
+arbitrary array types.
+Static Semantics
+
+The procedure Containers.Generic_Array_Sort has the following declaration:
+
+ generic
+ type Index_Type is (<>);
+ type Element_Type is private;
+ type Array_Type is array (Index_Type range <>) of Element_Type;
+ with function "<" (Left, Right : Element_Type)
+ return Boolean is <>;
+ procedure Ada.Containers.Generic_Array_Sort (Container : in out Array_Type);
+
+Reorders the elements of Container such that the elements are
+sorted per the order specified as the generic formal less-than operator.
+Any exceptions raised during evalution of less-than are propagated.
+
+AARM Notes
+This implies swapping the elements, usually including an intermediate copy.
+This of course means that the elements will be copied. Since the elements are
+non-limited, this usually will not be a problem. Note that there is
+Implementation Advice below that the implementation should use
+a sort that minimizes copying of elements.
+
+The sort is not required to be stable (and the fast algorithm required will
+not be stable). If a stable sort is needed, the user can include the original
+location of the element as an extra "sort key". We considered requiring the
+implementation to do that, but it is mostly extra overhead -- usually there
+is something already in the element that provides the needed stability.
+
+The procedure Containers.Generic_Constrained_Array_Sort has the following
+declaration:
-Execution is erroneous if the access returned by an instantiation of
-Generic_Element changes the element so that the either of the formal
-subprograms "<" and "=" could give different results than before the
-modification.
+ generic
+ type Index_Type is (<>);
+ type Element_Type is private;
+ type Array_Type is array (Index_Type) of Element_Type;
+ with function "<" (Left, Right : Element_Type)
+ return Boolean is <>;
+ procedure Ada.Containers.Generic_Constrained_Array_Sort
+ (Container : in out Array_Type);
+
+Reorders the elements of Container such that the elements are
+sorted per the order specified as the generic formal less-than operator.
+Any exceptions raised during evalution of less-than are propagated.
Implementation Advice
-Insertions and searches in a Sorted_Set should take no longer than a time
-proportional to the log (base 2) of the number of items in the set.
+A call on an instantiation of Containers.Generic_Array_Sort or
+Containers.Generic_Constrained_Array_Sort should take no worse than a time
+proportional to the square of the number of items in the array, and
+on average a time better than proportional to the square of the number of
+items in the array.
AARM Note
-This can be accomplished with a balanced (red-black) tree for keys.
+In other words, we're requiring the use of a sorting algorithm better than
+O(N**2), such as Quicksort. No Bubble sorts allowed!
-[Open Issue: A hashed version of this container also is typical (with
-parameters similar to the ones of the Hashed_Map). This was left out to keep
-the size of the containers library manageable. Should it be reintroduced?
-One presumes it would be included in the secondary standard if it is not
-included here.]
+Containers.Generic_Array_Sort and Containers.Generic_Constrained_Array_Sort
+should minimize copying of elements.
+
+AARM Note - To Be Honest
+We do not mean "absolutely minimize" here; we're not intending to require a
+single copy for each element. Rather, we want to suggest that the sorting
+algorithm chosen is one that does not copy items unnecessarily. Bubble sort
+would not meet this advice, for instance.
!example
@@ -1773,7 +3123,7 @@
container:
procedure Copy (A : Array_Subtype) is
- V : Vector_Type;
+ V : Vector;
begin
Resize (V, Size => A'Length);
@@ -1796,7 +3146,7 @@
package Stacks is new Ada.Containers.Vectors (ET);
use Stacks;
- Stack : Stacks.Vector_Type;
+ Stack : Stacks.Vector;
procedure Push (E : in ET) is
begin
@@ -1813,23 +3163,20 @@
Delete_Last (Stack);
end;
-Note that we can't use the front end as the top of the stack, because
-there's no Delete_First.
-
-The Insert_Empty_Space operation essentially opens up a "hole" in the
-middle of the internal array. It's more efficient to do it this way than
+The Insert_Space operation essentially opens up a "hole" in the middle
+of the internal array. It's more efficient to do it this way than
inserting items one-at-a-time, because the sliding is done only once.
For example, we can copy an array (or any other container) into a vector
at some arbitary position like this:
procedure Copy
(A : in Array_Subtype;
- V : in out Vector_Type;
+ V : in out Vector;
I : in Index_Type'Base) is
J : Index_Type'Base := I;
begin
- Insert_Empty_Space (V, Before => I, Count => A'Length); -- dig the hole
+ Insert_Space (V, Before => I, Count => A'Length); -- dig the hole
for Index in A'Range loop
Replace_Element (V, J, By => A (Index)); -- fill the hole
@@ -1838,208 +3185,212 @@
...
end Copy;
-
-There's no Delete_First operation, as a not-so-subtle reminder to
-developers that that's a potentially expensive operation. However, you
-can achieve the same effect by simply specifying the first index:
-
- procedure Op (V : in out Vector_Type) is
- begin
- Delete (V, Index => First (V)); -- pop front element
- ...
- end;
-
You can think of Clear as "removing" the elements in the container, but
of course it does not really remove them. The elements that were
-formerly active simply now become inactive.
-
-In particular, the internal array is not altered, and no "finalization"
-of the active elements occurs. (Of course, the elements are finalized when
-the master of the vector object is left.) If this is required, then then user
-must effect this himself prior to clearing the vector. Here is one way to do
-that:
+formerly active simply now become inactive. In particular, the internal
+array is not altered, and no "finalization" of the active elements
+occurs. (Of course, the elements are finalized when the master of the
+vector object is left.) If this is required, then then user must effect
+this himself prior to clearing the vector. Here is one way to do that:
- type Element_Access is access all Element_Subtype;
- for Element_Access'Storage_Size use 0;
+ procedure Finalize (Element : in out My_Element_Type) is ...;
- function To_Access is new Generic_Element (Element_Access);
+ procedure My_Clear (V : in out Vector) is
- procedure Finalize (Element : in out Element_Subtype) is ...;
-
- procedure My_Clear (V : in out Vector_Type) is
+ procedure Finalize_Element is
+ new Generic_Update_By_Index (Finalize);
begin
- for I in First (V) .. Last (V) loop
- Finalize (To_Access (V, I).all);
+ for I in First_Index (V) .. Last_Index (V) loop
+ Finalize_Element (V, I);
end loop;
Clear (V);
end My_Clear;
-Here we use the Generic_Element selector function to get a variable view
-of the vector elements.
+Here we use the Generic_Update_By_Index modifier, and pass Finalize as
+the generic actual.
The internal array never shrinks, and it only expands under specific
conditions. If you want to clear the vector and also deallocate the
-internal array, you can use the swap trick:
+internal array, you can use Move:
- procedure Clear_And_Deallocate (V : in out Vector_Type) is
+ procedure Clear_And_Deallocate (V : in out Vector) is
- V2 : Vector_Type; -- internal array is null
+ V2 : Vector; -- length is 0; assume size is 0
begin
- Swap (V, V2);
+ Clear (V); -- sets length to 0, but size > 0
+ Move (Target => V, Source => V2); -- deallocate V's array
end;
-The internal array that belonged to V is swapped into V2, and the null
-array of V2 is swapped into V. When V2 is finalized, its internal array
-is deallocated. This also invokes Finalize for controlled elements.
+The internal array that belonged to V is deallocated, and the null (or
+otherwise small) array of V2 is moved into V.
The Resize operation can only be used to grow the internal array, not to
shrink it. If for whatever reason you want more efficient use of
-storage, you can use the swap trick to allocate an array having the
-minimum size necessary to store the active elements:
+storage, you can use Move to allocate an array having the minimum size
+necessary to store the active elements:
- procedure Reclaim_Storage (V : in out Vector_Type) is
- Temp : Vector_Type := V;
+ procedure Reclaim_Storage (V : in out Vector) is
+ Temp : Vector := V;
begin
- Swap (V, Temp);
+ Clear (V);
+ Move (Target => V, Source => Temp);
end;
-This copies all active elements in V to the temporary vector object
-Temp, which is allocated using a smaller internal array (presumably the
-smallest size necessary to store the elements, according to whatever
-algorithm the implementor has chosen). The new array is swapped with
-the original array, which is then deallocated when Temp is finalized.
+This operation first copies all active elements in V to the temporary
+vector object Temp, which is allocated using a smaller internal array
+(presumably the smallest size necessary to store the elements, according
+to whatever algorithm the implementor has chosen). The new, smaller
+array from Temp is then moved into V.
If some sort of finalization of the last element is necessary prior to
-its "removal" by Delete_Last, the programmer is responsible for
-effecting this action prior to calling Delete_Last. As an example,
+its "removal" by a deletion operation, the programmer is responsible for
+effecting this action prior to calling the operation. As an example,
suppose we have a vector whose elements are access objects, and we need
-to deallocate the element when it is "popped" from the vector. If we
-reuse our instantiation of Generic_Element from the example above, then
-we can do this:
+to deallocate the element when it is "popped" from the vector using
+Delete_Last. We can do that like this:
- procedure Pop (V : in out Vector_Type) is
+ procedure Pop (V : in out Vector) is
procedure Free is
new Ada.Unchecked_Deallocation (T, T_Access);
+
+ procedure Free_Element is
+ new Generic_Update_By_Index (Process => Free);
begin
- Free (To_Access (V, Last (V)).all);
+ Free_Element (V, Index => Last_Index (V));
Delete_Last (V);
end Pop;
-The Front selector exists so that during reverse iteration over a
-vector, the index can "fall off the end" of the range onto the sentinel:
+The First_Index and Last_Index selectors allow iteration over a vector
+analogous to iteration over an array, using the loop machinary provided
+by the language:
- procedure Op (V : in Vector_Type) is
- I : Index_Subtype := Last (V);
- J : constant Index_Subtype'Base := Front (V);
+ procedure Op (V : in Vector) is
+ procedure Process (E : in Element_Subtype) is ...;
begin
- while I /= J loop
+ for I in First_Index (V) .. Last_Index (V) loop
Process (E => Element (V, I));
- I := Index_Type'Pred (I);
end loop;
end Op;
-The First and Last selectors allow iteration over a vector analogous to
-iteration over an array, using the loop machinary provided by the
-language:
+We could also use the cursor-based operations to do the same thing.
- procedure Op (V : in Vector_Type) is
+ procedure Op (V : in Vector) is
procedure Process (E : in Element_Subtype) is ...;
+
+ I : Cursor := First (V);
begin
- for I in First (V) .. Last (V) loop
- Process (E => Element (V, I));
+ while Has_Element (I) loop
+ Process (E => Element (I));
end loop;
end Op;
+Here we iterate over all of the vector elements. Alternatively we could
+use a passive iterator:
+
+ procedure Op (V : in Vector) is
+ procedure Process (E : in Element_Subtype) is ...;
-The Generic_Element function is very important, as it allows in-place
-modification of elements. For example, suppose we have a vector whose
-elements are vectors, and we want to append an item to the inner vector at a
-specified outer vector position. We can do that as follows:
+ procedure Process (I : in Cursor) is
+ begin
+ Process (E => Element (I));
+ end;
- type Inner_Vector_Access is access all Inner_Vector_Type;
- for Inner_Vector_Access'Storage_Size use 0;
+ procedure Iterate is
+ new Generic_Iteration (Process);
+ begin
+ Iterate (V);
+ end Op;
- function To_Access is new Generic_Element (Inner_Vector_Access);
+The Generic_Update generic operation is very important, as it allows
+in-place modification of elements. For example, suppose we have a vector
+whose elements are lists, and we want to append an item to the list
+element at a specified vector position. We can do that as follows:
procedure Append
- (V : Vector_of_Vectors.Vector_Type;
+ (V : Vector_of_Lists.Vector;
I : Index_Type'Base;
E : Element_Subtype) is
+
+ procedure Process (L : in out List) is
+ begin
+ Append (L, New_Item => E);
+ end;
- Inner_Vector : Inner_Vector_Type renames To_Access (V, I).all;
+ procedure Update is
+ new Generic_Update_By_Index (Process);
begin
- Append (Inner_Vector, New_Item => E);
+ Update (V, Index => I);
end;
It's often the case that during an insertion you don't have an item
value to assign to the new element, and instead you want simply to
reserve space for an element and then modify it directly. For example:
- procedure Op (V : in out Vector_Type) is
- begin
- Insert_Empty_Space (V, Before => Back (V), Count => 1); -- no item
+ procedure Op (V : in out Vector) is
- declare
- E : Element_Subtype renames To_Access (V, Last (V)).all;
+ procedure Process (E : in out ET) is
begin
- -- now modify E
+ ... -- manipulate E as appropriate
end;
- end Op;
-Given our vector-of-vectors from the earlier example, we could swap an inner
-vector object with one of the inner vector elements already in vector, like
-this:
+ procedure Update is
+ new Generic_Update (Process);
- procedure Swap
- (V : in Vector_of_Vectors.Vector_Type;
- I : in Index_Type'Base;
- L : in out Inner_Vector_Type) is
-
- VE : Inner_Vector_Type renames To_Access (V, I).all;
+ C : Cursor;
+ Empty : ET; -- A default-initialized object of ET.
begin
- Swap (L, VE);
- end;
+ Insert --allocate the element
+ (Container => V,
+ Before => No_Element, --insert at back end
+ New_Item => Empty,
+ Position => C); --return value
-This would allow us to populate an inner vector object, separate from the
-vector-of-vectors, and then add it to the vector-of-vectors without having to
-actually copy it:
+ Update (Position => C); --give element a value
+ end Op;
- procedure Op (V : in Vector_of_Vectors.Vector_Type) is
- L : Inner_Vector_Type;
- begin
- Append (L, New_Item => E);
- ... -- populate vector some more
- Insert_Empty_Space (V, Before => Back (V), Count => 1); -- create a new element in V
- Swap (V, Last (V), L); -- swap new element in V with L
- end;
+We insert a default-initialized object so that the initial state of the
+item is known. If we didn't need that, we could have used Insert_Space and
+Replace_Element instead.
-The new vector element that is appended to V during Insert is immediately
-swapped with the vector object L. This effectively "moves" L onto V,
-without any copying. The element that was in V is moved into L, which
-is then finalized.
-To swap two inner vector elements in the same vector-of-vectors, we could
-implement it this way:
+If we have a container whose elements are vectors, we can use
+Generic_Update in combination with Move to insert a vector onto the
+container without actually copying the vector. (Actually, this is true
+for all containers -- not just vectors.) Suppose that we have a list of
+vectors:
- procedure Swap
- (V : in out Vector_of_Vectors.Vector_Type;
- I, J : in Index_Type'Base) is
+ procedure Op (L : in List_of_Vectors.List) is
+ V : Vector;
- IE : Inner_Vector_Type renames To_Access (V, I).all;
- JE : Inner_Vector_Type renames To_Access (V, J).all;
- begin
- Swap (IE, JE);
- end;
+ procedure Move_V (E : in out Vector) is
+ begin
+ Clear (E); -- technically E should already be empty
+ Move (Target => E, Source => V);
+ end;
+
+ procedure Update is
+ new Generic_Update (Move_V);
+
+ C : Cursor;
+ begin
+ Append (V, New_Item => E);
+ ... -- populate vector some more
+ Insert (L, Before => No_Element, New_Item => Empty_Vector, Position => C);
+ Update (C); --move V to position C of list L
+ end;
+A new, default-initialized vector element is appended to L by
+Insert, and then immediately replaced by moving the internal array
+of vector V into that new, empty element, without any copying.
If ordinary assignment of elements is acceptable, then Replace_Element
allows array-like modification of vector elements:
- procedure Op (V : in out Vector_Type) is
+ procedure Op (V : in out Vector) is
I : Index_Subtype := ...;
E : Element_Subtype := ...;
begin
@@ -2048,128 +3399,126 @@
Replace_Element (V, Index => I, By => E); -- aka V(I) := E;
end;
+All containers are non-limited, and hence allow ordinary assignment. In
+the unique case of a vector, there is a separate assignment procedure:
-Vector containers turn out to be extremely useful especially when
-used with other containers, especially associative containers that
-preserve an order-relationship among elements. For example, suppose we
-have a histogram that counts the frequency of each word in a text file.
-We would use the string-key map, that has type String as the key and
-Natural as its Element_Type.
-
-After we've exhausted the input, we want to display the words in
-frequency order. However, we can't iterate over the map directly, since
-it is ordered by key -- we need to order by element (here, a count).
-
-We can do that very easily by creating a vector of map cursors,
-and then sorting the vector according to the element count. For
-example:
-
- package Vector_Types is
- new Ada.Containers.Vectors
- (Index_Type => Positive,
- Element_Type => String_Integer_Maps.Cursor_Type);
+ Assert (Target => V1, Source => V2);
- procedure Post_Process
- (Histogram : in String_Integer_Maps.Map_Type) is
+The reason is that the model for a vector is that it's implemented using
+an unconstrained array. During ordinary assignment, the internal array
+is deallocated (during controlled finalization), and then a new internal
+is allocated (during controlled adjustment) to store a copy of the
+elements from the source vector. However, assignment would probably be
+more efficient if it were able to hold on to the existing array, and
+simply copy the elements of the source onto that array, instead of
+having to allocate a new one. This is exactly how Assign works.
- Vector : Vector_Types.Vector_Type;
- procedure Process (I : in String_Integer_Maps.Cursor_Type) is
- begin
- Vector_Types.Append (Vector, New_Item => I);
- end;
+A.17.3 The Package Containers.Doubly_Linked_List
- procedure Populate_Vector is
- new String_Integer_Maps.Generic_Iteration; -- use default name
+You can use a doubly-linked list to implement a queue in the traditional
+way:
- begin -- Post_Process
+ package Queues is new Ada.Containers.Doubly_Linked_Lists (ET);
+ use Queues;
+
+ Queue : Queues.List;
+
+ procedure Push (E : in ET) is
+ begin
+ Append (Queue, New_Item => E);
+ end;
- Resize (Vector, Length (Histogram));
- Populate_Vector (Histogram);
+ function Top return ET is
+ begin
+ return First_Element (Queue);
+ end;
- ... -- see below
+ procedure Pop is
+ begin
+ Delete_First (Queue);
+ end;
- end Post_Process;
+The doubly-linked list container allows iteration in both directions.
+To iterate forward you start at first and increment the cursor:
-Here we use the passive iterator for maps to populate the vector
-container object. We use resize to preallocate the internal array to the
-correct size, since we know the total number of vector elements.
-
-Now that we have the vector, we need to sort it, so we need an
-order relation. We want to sort the elements in reverse order, so that
-largest count is listed first in the output. We can define the order
-relation like this:
+ procedure Op (L : in List) is
+ C : Cursor := First (L);
+ begin
+ while Has_Element (C) loop
+ Process (C);
+ Next (C);
+ end loop;
+ end;
- declare
- function "<" (L, R : String_Integer_Maps.Cursor_Type)
- return Boolean is
- begin
- return Element (L) > Element (R); -- yes
- end;
+To iterate in reverse you start at last and decrement the cursor:
- procedure Sort is
- new Vector_Types.Generic_Sort; -- use "<" default
+ procedure Op (L : in List) is
+ C : Cursor := Last (C);
begin
- Sort (Vector);
+ while Has_Element (C) loop
+ Process (C);
+ Previous (C);
+ end loop;
end;
-We can do better though: suppose that for counts that are equal, we want
-to list the items in alphabetic order of the words. We only have fix
-our order relation to compare keys, too:
+Note that in both cases the iteration terminates by falling off the end
+of the list, at which point the cursor assumes the distinguished value
+No_Element, and Has_Element returns False.
- declare
- function "<" (L, R : String_Integer_Maps.Cursor_Type)
- return Boolean is
- begin
- if Element (L) = Element (R) then
- return Key (L) < Key (R); -- compare String
- else
- return Element (L) > Element (R); -- compare Integer
- end if;
- end;
+All of the containers have an operation to swap a pair of elements in
+the container:
- procedure Sort is
- new Vector_Types.Generic_Sort; -- use "<" default
- begin
- Sort (Vector);
- end;
+ procedure Swap
+ (V : in out Vector_Of_Lists.Vector;
+ I, J : in Index_Type'Base) is
+ begin
+ Swap (V, I, J); -- vector operation
+ end;
-To display the results, all we have to do is iterate through the sorted
-vector:
+For the definite form (the case here), this will make a copy of the
+element in order to perform the swap. However, we would prefer not to
+make a copy of this element, which is a list and hence potentially large
+(or otherwise expensive to copy). To avoid making a copy, we can use
+Move and nested instantiations of Generic_Update:
-Print_Results:
- for Index in First (Vector) .. Last (Vector) loop
- declare
- MI : String_Integer_Maps.Cursor_Type := Element (Vector, Index);
- begin
- Put (Element (MI), Width => 0); -- the count
- Put (':');
- Put (Key (MI)); --the word
- New_Line;
- end;
- end loop Print_Results;
+ procedure Swap
+ (V : in out Vector_Of_Lists.Vector;
+ I, J : in Index_Type'Base) is
-Et voila! As with all iterators, there's no need to pass an extra parameter
-to indicate that iteration should stop, since that functionality can be
-built using active iterators:
-
- procedure Op (C : in Vector_Type) is
- I : Index_Subtype := First (C);
- Stop : constant Index_Subtype := Back (C);
- begin
- while I /= Stop loop
- exit when Predicate (Element (I));
- Process (Element (I));
- Increment (I);
- end loop;
- end Op;
+ procedure Process_I (IE : in out List) is
-We didn't use a for loop to iterate here, in order to show how the form of an
-active iterator can be the same for all of the containers.
+ procedure Process_J (JE : in out List) is
+ IE_Temp : List;
+ begin
+ Move (Target => IE_Temp, Source => IE);
+ Move (Target => IE, Source => JE);
+ Move (Target => JE, Source => IE_Temp);
+ end;
+
+ procedure Update_J is
+ new Generic_Update_By_Index (Process_J);
+ begin
+ Update_J (V, Index => J);
+ end;
+ procedure Update_I is
+ new Generic_Update_By_Index (Process_I);
+ begin
+ Update_I (V, Index => I);
+ end Swap;
+
+To do the swap, we need direct visibility to both objects, so nested
+instantiations are required. We first move the list element at index I
+of the vector into a temporary. This allows another vector to by copied
+into that index position. We do that, moving the list element at index
+J into (empty) list element at index I. We then move the temporary
+(holding the list that was originally at index I) into the vector at
+index position J.
-A.17.3 The Package Containers.Hashed_Maps
+A.17.4 The Package Containers.Hashed_Maps
+
It's often the case that you know apriori the total number of elements
you intend to insert into the map. Under these circumstances you should
always Resize the map first (similar to a vector container), and then
@@ -2178,37 +3527,44 @@
during normal insertion to preserve the load factor. For example:
procedure Op (N : Size_Type) is
- Map : Map_Types.Map_Type; -- Size = 0
+ M : Map_Types.Map; -- Size = 0 (or small)
- Cursor : Map_Types.Cursor_Type;
+ Position : Map_Types.Cursor;
Success : Boolean;
begin
- Resize (Map, Size => N); -- Size >= N
+ Resize (M, Size => N); -- Size >= N
for I in 1 .. N loop
Insert -- no resizing will occur
- (Map => Map,
- Key => Get_Key (I),
- New_Item => Get_Element (I),
- Cursor => Cursor,
+ (Container => Map,
+ Key => New_Key (I),
+ New_Item => New_Element (I),
+ Position => Position,
Success => Success);
end loop;
...
end Op;
+
+Note that Clear doesn't delete the internal hash table -- it just
+deletes the nodes hanging off the hash table. If you want to delete the
+internal hash table too (thus setting the map's size to 0), then you can
+use Move with a temporary map object:
-Note that Clear doesn't delete the hash table -- it just deletes the
-nodes hanging off the hash table. If you want to delete the hash table
-too (thus setting the map's size to 0), then you can Swap with a temporary map
-object. (Map objects are default-initialized with a zero-length hash table.)
+ procedure Clear_And_Deallocate (M : in out Map) is
+ Temp : Map;
+ begin
+ Clear (M);
+ Move (Target => M, Source => Temp);
+ end;
The simplest and fastest way to iterate over all the elements in the map
-is to use one of the passive iterator:
+is to use a passive iterator:
- procedure Op (Map : in Map_Types.Map_Type) is
+ procedure Op (M : in Map_Types.Map) is
- procedure Process (I : in Map_Types.Cursor_Type) is
- K : Key_Subtype := Key (I);
- E : Element_Subtype := Element (I);
+ procedure Process (C : in Map_Types.Cursor) is
+ K : Key_Subtype := Key (C);
+ E : Element_Subtype := Element (C);
begin
... -- do whatever
end;
@@ -2216,53 +3572,56 @@
procedure Iterate is
new Generic_Iteration; -- accept default name
begin
- Iterate (Map);
+ Iterate (M);
end;
-You could implement this function yourself, by iterating over the items in
-the map:
+You could of course implement this function yourself, by iterating over
+the items in the map:
- procedure Op (Map : in Map_Types.Map_Type) is
+ procedure Op (M : in Map_Types.Map) is
- procedure Process (I : in Map_Types.Cursor_Type) is ...;
+ procedure Process (C : in Map_Types.Cursor) is ...;
- I : Map_Types.Cursor_Type;
+ C : Map_Types.Cursor := First (M);
begin
- I := First (Map);
-
- while I /= Null_Cursor loop
- Process (I);
- Increment (Map, I);
+ while Has_Element (C) loop
+ Process (C);
+ Next (C);
end loop;
end Op;
+However, a manual loop probably isn't as efficient as a passive iterator
+(especially for a hashed map), because the passive iterator can store
+implementation-specific context in order to find elements in sequence
+more quickly.
+
Generic algorithms are typically written to work with iterators this way:
generic
- type IT is private;
- with function Succ (I : IT) return IT is <>;
- with procedure Process (I : IT) is <>;
- with function "=" (L, R : IT) return Boolean is <>;
- procedure Generic_Algorithm (First, Back : in IT);
+ type Cursor is private;
+ with function Next (C : Cursor) return Cursor is <>;
+ with procedure Process (C : Cursor) is <>;
+ with function Has_Element (C : Cursor) return Boolean is <>;
+ procedure Generic_Algorithm (First : in Cursor);
The implementation would look something like this:
- procedure Generic_Algorithm (First, Back : in IT) is
- I : IT := First;
+ procedure Generic_Algorithm (First : in Cursor) is
+ C : Cursor := First;
begin
- while I /= Back loop
+ while Has_Element (C) loop
...
- Process (I);
+ Process (C);
...
- I := Succ (I);
+ C := Next (C);
end loop;
end Generic_Algorithm;
The benefit is that this algorithm will work with any "sequence of
-items," which just means any container with an iterator having the
+items," which just means any container with a cursor having the
requisite properties, as specified in the generic formal region. The
virtue of this approach is that it abstracts-away the container. The
generic algorithm above (and others like it) works with all the
@@ -2271,26 +3630,15 @@
To make this work with a map, we can just instantiate with an appropriate
Process operation:
- procedure Op (Map : in Map_Types.Map_Type) is
+ procedure Op (M : in Map_Types.Map) is
- procedure Process (Cursor : Cursor_Type) is ...;
+ procedure Process (C : Cursor) is ...;
- function Succ (C : Cursor_Type) return Cursor_Type is
- begin
- return Succ (Map, C);
- end;
-
procedure Algorithm is
- new Generic_Algorithm (Cursor_Type); -- accept defaults
-
- begin -- Op
-
- Algorithm (First => First (Map), Back => Back (Map));
-
- end Op;
-
-Back (Map) is really just Null_Cursor, but we use it to be consistent
-with other containers.
+ new Generic_Algorithm (Map_Types.Cursor); -- accept defaults
+ begin
+ Algorithm (First (Map));
+ end;
In a POSIX OS that supports real-time signals, the OS will deliver a
payload-carrying signal to the app. In the case of a socket, when I/O
@@ -2329,11 +3677,16 @@
What I need to do is correlate the file descriptor reported in the RT
-signal to a session object. With a map it's almost trivial. In the
-body I can instantiate the map like this:
+signal to a session object. With a map it's almost trivial. In the body
+I can instantiate the map as follows. First we make a hash function for
+socket descriptors:
+
+ function Hash_FD (fd : in C.int) return Ada.Containers.Hash_Type is
+ begin
+ return Ada.Containers.Hash_Type (fd); -- fd > 0
+ end;
- function Hash_FD is
- new Ada.Containers.Generic_Hash_Discrete (C.int); -- or whatever
+Next we instantiate the hashed map package using our hash function:
package FD_Map_Types is
new Ada.Containers.Hashed_Maps
@@ -2345,7 +3698,7 @@
package Sessions is
...
- FD_Map : FD_Map_Types.Map_Type;
+ FD_Map : FD_Map_Types.Map;
When I allocate a new session object, this opens the socket. A socket
object has a selector function to return its file descriptor. I use
@@ -2354,17 +3707,17 @@
function Setup_Session return Session_Access is
Session : constant Session_Access := new Session_Type;
- Cursor : FD_Map_Types.Cursor_Type;
+ Position : FD_Map_Types.Cursor;
Success : Boolean;
begin
Open (Session.Socket, ...);
Insert
- (Map => FD_Map,
- Key => FD (Session.Socket),
- New_Item => Session,
- Cursor => Cursor,
- Success => Success);
+ (Container => FD_Map,
+ Key => FD (Session.Socket),
+ New_Item => Session,
+ Position => Position,
+ Success => Success);
...
return Session;
end;
@@ -2374,35 +3727,33 @@
like:
procedure Handle_Signal (Siginfo : in Siginfo_Type)
- FD : constant C.int := Siginfo.FD;
- Iter : constant Cursor_Type := Find (FD_Map, Key => FD);
+ FD : constant C.int := Siginfo.FD;
+ C : constant Cursor := Find (FD_Map, Key => FD);
begin
- if Iter /= Null_Cursor then
- IO_Completion (Element (Iter));
+ if C /= No_Element then -- if search was successful
+ IO_Completion (Element (C));
end if;
end Handle_Signal;
and then the session object reacts to the I/O completion accordingly.
-
-A.17.4 The Package Containers.String_Hashed_Maps
-
Hashed maps with type String as the key are nearly ubiquitous. The
canonical example is of course the word-frequency problem, in which
"words" (using some suitable definition of delimiter) are counted as
they are scanned in the input stream.
-We can solve this problem easily using a map with string as the key and
-subtype Natural as the element:
+We can solve this problem easily using the indefinite form of the hashed
+map, with string as the key and subtype Natural as the element:
with Ada.Strings.Hash_String;
package Wordcount_Maps is
- new Ada.Containers.String_Hashed_Maps
- (Element_Type => Natural,
+ new Ada.Containers.Indefinited_Hashed_Maps
+ (Key_Type => String,
+ Element_Type => Natural,
Hash => Ada.Strings.Hash_String); -- case-sensitive
- Map : Wordcount_Maps.Map_Type;
+ Wordcount_Map : Wordcount_Maps.Map;
Here we've specified the hash function for strings provided by the
library. The scanning phase looks like this:
@@ -2436,28 +3787,27 @@
procedure Insert (Word : String) is
- Cursor : Wordcount_Maps.Cursor_Type;
- Success : Boolean;
+ procedure Increment (Count : in out Natural) is
+ begin
+ Count := Count + 1;
+ end;
- type Count_Access is access all Natural;
+ procedure Increment_Count is
+ new Generic_Update (Increment);
- function To_Element_Access is
- new Wordcount_Maps.Generic_Element (Count_Access);
+ Position : Wordcount_Maps.Cursor;
+ Success : Boolean;
begin -- Insert
Insert
- (Map => Map,
- Key => To_Lower (Word),
- New_Item => 0, -- yes
- Cursor => Cursor,
- Success => Success);
+ (Container => Wordcount_Map,
+ Key => To_Lower (Word),
+ New_Item => 0, -- yes
+ Position => Position,
+ Success => Success);
- declare
- N : Natural renames To_Element_Access (Cursor).all;
- begin
- N := N + 1;
- end;
+ Increment_Count (Position);
end Insert;
@@ -2473,30 +3823,30 @@
But not inserting a new node is exactly the behavior we want. In the
case of a word already in the map, the cursor returned designates an
-existing word/count pair, whose count is non-zero. When we alias the
+existing word/count pair, whose count is non-zero. When we update the
count object, we simply increment its value.
However, the word might not be in the map, in which case the insertion
"succeeds," which means a new node is inserted whose element is
-initialized to the value of New_Item, which here is 0. Cursor
+initialized to the value of New_Item, which here is 0. Position
designates the newly-inserted element (really, it designates the node
-containing that key/element pair). When we alias the element, the count
+containing that key/element pair). When we update the element, the count
has the value 0, and so by incrementing it the count gets set to the
-value 1.
+correct value 1.
Conditional insertion is a necessary feature of any efficient map
-abstraction. It makes no sense to search for the element (via Find,
-say) to determine whether it's in the map, and if it's not in the map
-call a separate operation to insert it. This would be horribly
-inefficient because the lookup done by insert would only duplicate the
-lookup just done by the search.
+abstraction. It makes no sense to search for the element (via Find, say)
+to determine whether it's in the map, and if it's not in the map call a
+separate operation to insert it. This would be horribly inefficient
+because the lookup done by insert would only duplicate the lookup just
+done by the search.
To dump the contents of the map, you can use the passive iterator:
declare
- procedure Process (I : in Wordcount_Maps.Cursor_Type) is
+ procedure Process (C : in Wordcount_Maps.Cursor) is
begin
- Put (Key (I)); Put (':'); Put (Element (I)); New_Line;
+ Put (Key (C)); Put (':'); Put (Element (C)); New_Line;
end;
procedure Dump is
@@ -2508,29 +3858,101 @@
This would display the words in their order in the hashed map. That's
probably not what you want (especially for a well-performing hash table,
which would scatter keys everywhere), which is to display them in order
-by frequency. I showed how to do that in the vector
-example. What we did was to populate the vector with cursors that
-designate the map entries, and then sort the vector:
+by frequency. We can do that easily enough by populating an array with
+map cursors, and then sorting the array according to element value:
+
+ procedure Print_Results (Histogram : in Wordcount_Map) is
+
+ type Cursor_Array is
+ array (Size_Type range <>) of Wordcount_Maps.Cursor;
+
+ Cursors : Cursor_Array (1 .. Length (Histogram));
+
+ I : Size_Type := Cursors'First;
+ procedure Process (C : in Wordcount_Maps.Cursor) is
+ begin
+ Cursors (I) := C;
+ I := Size_Type'Succ (I);
+ end;
+
+ procedure Populate_Array is
+ new Wordcount_Maps.Generic_Iteration; -- use default name
+
+ begin -- Print_Results
+
+ Populate_Array (Histogram);
+
+ ... -- see below
+
+ end Print_Results;
+
+Here we use the passive iterator for maps to populate the array. As
+with all containers, it's usually simpler and more efficient to use a
+passive iterator if you're going to traverse all the elements in the
+container. The library is often used by making a lot of little
+on-the-fly passive-iterator instantiations, as above.
+
+We now need to sort the array of cursors, and to do that we need an
+order relation for cursors. We want to sort the elements in reverse
+order, so that largest histogram count is listed first in the output. We
+can define the order relation like this:
+
+ Sort_Array:
declare
- Vector : Vector_Type;
+ function "<" (L, R : Wordcount_Maps.Cursor)
+ return Boolean is
+ begin
+ return Element (L) > Element (R); -- yes
+ end;
+
+ procedure Sort is
+ new Generic_Array_Sort
+ (Index_Type => Size_Type,
+ Element_Type => Word_Count_Maps.Cursor,
+ Array_Type => Cursor_Array); -- accept "<" default
+ begin
+ Sort (Cursors);
+ end Sort_Array;
+
+We can do better though: suppose that for counts that are equal, we want
+break the tie by listing the items in alphabetic order of the words. We
+only have fix our order relation to compare keys, too:
- procedure Process (I : Wordcount_Maps.Cursor_Type) is
+ Sort_Array:
+ declare
+ function "<" (L, R : Wordcount_Maps.Cursor)
+ return Boolean is
begin
- Append (Vector, New_Item => I);
+ if Element (L) = Element (R) then
+ return Key (L) < Key (R); -- compare String
+ else
+ return Element (L) > Element (R); -- compare Integer
+ end if;
end;
- procedure Populate_Vector is
- new Wordcount_Maps.Generic_Iteration; -- "Process"
+ procedure Sort is
+ new Generic_Array_Sort
+ (Index_Type => Size_Type,
+ Element_Type => Word_Count_Maps.Cursor,
+ Array_Type => Cursor_Array); -- accept "<" default
begin
- Populate_Vector (Map);
- ... -- see vector
- end;
+ Sort (Cursors);
+ end Sort_Array;
-As with all containers, it's usually simpler and more efficient to use
-the passive iterators if you're going to traverse all the elements in
-the container. The library is often used by making a lot of little
-on-the-fly passive-iterator instantiations, as in the examples above.
+To display the results, we iterate through the sorted cursor array:
+
+ Print_Array:
+ for Index in Cursors'Range loop
+ declare
+ C : constant Wordcount_Maps.Cursor := Cursors (Index);
+ begin
+ Put (Element (C), Width => 0); -- the count
+ Put (':');
+ Put (Key (C)); --the word
+ New_Line;
+ end;
+ end loop Print_Array;
As another example, consider a client that connects to a streaming media
server to play a video. The server opens the file and then transmits
@@ -2557,42 +3979,42 @@
Our cache is just a map, indexed by file name:
package File_Cache_Types is
- new Ada.Containers.String_Hashed_Maps
- (Element_Type => Context_Access,
- Hash => Ada.Strings.Hash_String_Case_Insensitive,
- Is_Equal_Key => Ada.Containers.Equal_String_Case_Insensitive);
+ new Ada.Containers.Indefinite_Hashed_Maps
+ (Key_Type => String,
+ Element_Type => Context_Access,
+ Hash => Hash_String_Case_Insensitive,
+ Is_Equal_Key => Equal_String_Case_Insensitive);
- File_Cache : File_Cache_Types.Map_Type;
+ File_Cache : File_Cache_Types.Map;
The naive way to implement the lookup is:
procedure Setup (Name : in String) is
- Cursor : File_Cache_Types.Cursor_Type :=
+ Position : File_Cache_Types.Cursor :=
Find (File_Cache, Key => Name);
Success : Boolean;
-
Context : Context_Access;
begin -- Setup
- if Cursor = Null_Cursor then
+ if Position = No_Element then
Context := new Context_Type;
Context.Ref_Count := 0;
... -- init Context
Insert
- (Map => File_Cache,
- Key => Name,
- New_Item => Context,
- Cursor => Cursor,
- Success => Success);
+ (Container => File_Cache,
+ Key => Name,
+ New_Item => Context,
+ Position => Cursor,
+ Success => Success);
else
- Context := Element (Iter);
+ Context := Element (Position);
end if;
@@ -2607,32 +4029,32 @@
procedure Setup (Name : in String) is
- Iter : File_Cache_Types.Cursor_Type;
+ Position : File_Cache_Types.Cursor;
Not_In_Cache : Boolean;
Context : Context_Access;
begin
Insert
- (Map => File_Cache,
- Key => Name,
- New_Item => null, -- yes
- Cursor => Cursor,
- Success => Not_In_Cache);
+ (Container => File_Cache,
+ Key => Name,
+ New_Item => null, -- yes
+ Position => Position,
+ Success => Not_In_Cache);
if Not_In_Cache then
- pragma Assert (Element (Iter) = null);
+ pragma Assert (Element (Position) = null);
Context := new Context_Type;
Context.Ref_Count := 0;
... -- init context
- Replace_Element (Iter, By => Context);
+ Replace_Element (Position, By => Context);
else
- Context := Element (Iter);
+ Context := Element (Position);
end if;
@@ -2702,11 +4124,12 @@
as the key, and a Session_Access as the element, like this:
package Id_Maps is
- new Ada.Containers.String_Hashed_Maps
- (Element_Type => Session_Access,
+ new Ada.Containers.Indefinite_Hashed_Maps
+ (Key_Type => String,
+ Element_Type => Session_Access,
Hash => Ada.Strings.Hash_String); -- case-sensitive
- Id_Map : Id_Maps.Map_Type;
+ Id_Map : Id_Maps.Map;
use Id_Maps;
When the session is allocated, we insert the id/session pair into the
@@ -2715,17 +4138,17 @@
function Setup_Session return Session_Access is
Session : constant Session_Access := new Session_Type;
- Cursor : Id_Map_Types.Cursor_Type;
+ Position : Id_Map_Types.Cursor;
Success : Boolean;
begin
Generate_Id (Session.Id);
Insert
- (Map => Id_Map,
- Key => Session.Id,
- New_Item => Session,
- Cursor => Cursor,
- Success => Success);
+ (Container => Id_Map,
+ Key => Session.Id,
+ New_Item => Session,
+ Position => Position,
+ Success => Success);
...
return Session;
end;
@@ -2739,49 +4162,21 @@
NPT_Range : in NPT_Range_Type;
RTSP_Status : out RTSP_Status_Type) is
- Iter : constant Cursor_Type :=
+ Position : constant Cursor :=
Find (Id_Map, Key => Session_Id);
Session : Session_Access;
begin
- if Iter = Null_Cursor then
+ if Position = No_Element then
RTSP_Status := RTSP.Session_Not_Found;
return;
end if;
- Session := Element (Iter);
+ Session := Element (Position);
Play (Session, NPT_Range, RTSP_Status);
end;
-The Id map we instantiated in the previous example takes type
-Session_Access as the element type. The constructor (repeated here)
-looks like this:
-
- function Setup_Session return Session_Access is
- Session : constant Session_Access := new Session_Type;
-
- Cursor : Id_Maps.Cursor_Type;
- Successs : Boolean;
- begin
- Generate_Id (Session.Id);
-
- Insert
- (Map => Id_Map,
- Key => Session.Id,
- New_Item => Session,
- Cursor => Cursor,
- Success => Success);
- ...
- return Session;
- end;
-
-Here we first allocate a session object, and then separately (during
-Insert) allocate a node (in the Id_Map container) whose element is the
-pointer to the session object. If you think about it, this means there
-are actually two separate allocations: one for the element (here, a
-session object), and another for the node.
-
When we create a session object, we insert a pointer to the session
object in the Id_Map. The complementary problem is how to handle
deletion of the session object. Suppose we have a function like this:
@@ -2810,15 +4205,15 @@
Generate_Id (Session.Id);
Insert
- (Map => Id_Map,
- Key => Session.Id,
- New_Item => Session,
- Cursor => Session.Id_Map_Iter,
- Success => Success);
+ (Container => Id_Map,
+ Key => Session.Id,
+ New_Item => Session,
+ Position => Session.Id_Map_Position,
+ Success => Success);
pragma Assert (Success);
- pragma Assert (Key (Session.Id_Map_Iter) = Session.Id);
- pragma Assert (Element (Session.Id_Map_Iter) = Session);
+ pragma Assert (Key (Session.Id_Map_Position) = Session.Id);
+ pragma Assert (Element (Session.Id_Map_Position) = Session);
...
return Session;
@@ -2829,7 +4224,7 @@
procedure Free (X : in out Session_Access) is
begin
if X /= null then
- Delete (Id_Map, Cursor => X.Id_Map_Iter);
+ Delete (Id_Map, Position => X.Id_Map_Position);
Deallocate (X);
end if;
end;
@@ -2837,60 +4232,31 @@
This turns out to be a very common idiom. In the body of a package that
declares a type, you declare a set or map container to keep track of
instances of the type. As part of its representation, the type includes
-a cursor that designates the node that contains this instance. When
-the object is finalized, it deletes itself from the container.
+a cursor that designates the node that contains this instance. When the
+object is finalized, it deletes itself from the container.
In the examples we've seen, the session object inserts itself into the
map during the constructor function Setup_Session, and deletes itself
-during the destructor operation Free. If the type is controlled,
-another possibility is to do the insertion during Initialize, and the
-deletion during Finalize. This technique would work even for
-stack-allocated (controlled) objects.
+during the destructor operation Free. If the type is controlled, another
+possibility is to do the insertion during Initialize, and the deletion during
+Finalize. This technique would work even for stack-allocated (controlled)
+objects.
Let's pretend Free doesn't remove the designated session object from the
map, but rather has its traditional semantics of merely deallocating the
object. To shutdown all the sessions, we could do this:
- Id_Map : Id_Map_Types.Map_Type;
+ Id_Map : Id_Map_Types.Map;
...
procedure Shutdown_Sessions is
-
- procedure Process (I : Id_Map_Types.Cursor_Type) is
- Session : Session_Access := Element (I);
- begin
- Free (Session); -- free a copy of the map element
- end;
-
- procedure Free_Sessions is
- new Id_Map_Types.Generic_Iteration; -- accept default
-
- begin -- Shutdown_Sessions
-
- Free_Sessions (Id_Map);
-
- Clear (Id_Map);
-
- end Shutdown_Sessions;
-
-The passive iterator visits all the sessions in the map and Free's them.
-We then Clear the map, which sets its length to 0.
-
-Note that in the example above all the session objects are deallocated,
-but all the map elements remain non-null. Here it doesn't really make
-any difference because we immediately clear the map. Another slightly
-more safe techique would be to use Generic_Element to get a variable
-view of the element, and call Free on the map element directly:
-
- procedure Shutdown_Sessions is
- function To_Access is
- new Id_Map_Types.Generic_Elemenets (Session_Access);
+ procedure Process (C : in Id_Map_Types.Cursor) is
- procedure Process (I : Id_Map_Types.Cursor_Type) is
- Session : Session_Access renames To_Access (I).all;
+ procedure Free_Session is
+ new Is_Map_Types.Generic_Update (Process => Free);
begin
- Free (Session); -- free map element directly
+ Free_Session (C);
end;
procedure Free_Sessions is
@@ -2904,21 +4270,25 @@
end Shutdown_Sessions;
+The passive iterator visits all the sessions in the map and Free's them;
+this also sets all of the map elements to null. We then Clear the map,
+which sets its length to 0.
+
-A.17.6 The Package Containers.Sorted_Sets
+A.17.5 The Package Containers.Ordered_Sets
Suppose we have a set and want to copy the elements from the set into an
array. Here's one way to do it:
- procedure Op (S : in Integer_Sets.Set_Type) is
+ procedure Op (S : in Integer_Sets.Set) is
A : Integer_Array (1 .. Length (S));
- I : Integer_Sets.Cursor_Type := First (S);
+ I : Integer_Sets.Cursor := First (S);
J : Positive := A'First;
begin
- while I /= Back (S) loop
+ while Has_Element (I) loop
A (J) := Element (I);
- Increment (I);
+ Next (I);
J := J + 1;
end loop;
...
@@ -2931,31 +4301,31 @@
We can change the example use a built-in for loop:
- procedure Op (S : in Integer_Sets.Set_Type) is
+ procedure Op (S : in Integer_Sets.Set) is
A : Integer_Array (1 .. Length (S));
- I : Integer_Sets.Cursor_Type := First (S);
+ I : Integer_Sets.Cursor := First (S);
begin
for J in A'Range loop
A (J) := Element (I);
- Increment (I);
+ Next (I);
end loop;
...
end Op;
-This lets the array drive the iteration. In general, however, you
-should use a passive iterator in preference to an explicit loop. The
-reason is that if a container knows that its elements are being
-traversed sequentially, then it can use a traversal algorithm that takes
-advantage of that container's unique representation. The algorithm
-above might run faster if we do this:
+This lets the array drive the iteration. In general, however, you should
+use a passive iterator in preference to an explicit loop. The reason is
+that if a container knows that its elements are being traversed
+sequentially, then it can use a traversal algorithm that takes advantage
+of that container's unique representation. The algorithm above might run
+faster if we do this:
- procedure Op (S : in Integer_Sets.Set_Type) is
+ procedure Op (S : in Integer_Sets.Set) is
A : Integer_Array (1 .. Length (S));
J : Positive := A'First;
- procedure Process (I : Integer_Sets.Cursor_Type) is
+ procedure Process (I : Integer_Sets.Cursor) is
begin
A (J) := Element (I);
J := J + 1;
@@ -2998,9 +4368,9 @@
end;
package Connection_Sets is
- new Ada.Containers.Sorted_Sets (Connection_Access);
+ new Ada.Containers.Ordered_Sets (Connection_Access);
- Connection_Set : Connection_Sets.Set_Type;
+ Connection_Set : Connection_Sets.Set;
function Accept_Connection (Socket : Socket_Type)
return Connection_Access is
@@ -3008,14 +4378,14 @@
Connection : constant Connection_Access :=
new Connect_Type;
- Cursor : Connection_Sets.Cursor_Type;
+ Position : Connection_Sets.Cursor;
Success : Boolean;
begin
Insert
- (Set => Connection_Set,
- New_Item => Connection,
- Cursor => Cursor,
- Success => Success);
+ (Container => Connection_Set,
+ New_Item => Connection,
+ Position => Position,
+ Success => Success);
...
return Connection;
end;
@@ -3048,27 +4418,30 @@
begin
while not Is_Empty (Connection_Set) loop
X := First_Element (Connection_Set);
- Shutdown (X);
+ Shutdown (X); --removes X from Connection_Set (see above)
end loop;
end Shutdown_Connections;
Another technique would be to use an active iterator, like this:
procedure Shutdown_Connections is
- I : Cursor_Type := First (Connection_Set);
- Stop : constant Cursor_Type := Back (Connection_Set);
-
+ I : Cursor := First (Connection_Set);
X : Connection_Access;
begin
- while I /= Stop loop
+ while Has_Element (I) loop
X := Element (I);
- Delete (Connection_Set, Cursor => I);
+ Delete (Connection_Set, Position => I); --increments I
Free (X);
end loop;
end Shutdown_Connections;
-Here we use the cursor-form of Delete. Delete returns the successor
-of the cursor deleted, so eventually the loop terminates.
+Here we use the cursor-form of Delete. Delete returns the successor of
+the cursor deleted, so eventually the loop terminates. (There is also a
+Delete_Sans_Increment operation, that does not increment the cursor.
+This is more efficient since it doesn't perform the tree traversal that
+would be necessary to find the successor. In this example, however, the
+loop depends on the cursor being incremented, so we use the canonical
+form of Delete.)
In other exmples, we have been silent about the operation of
Generate_Id, which makes a session id for us comprising a sequence of 8
@@ -3081,12 +4454,12 @@
way is to use Find to see if it's in the already:
procedure Generate_Id (Id : out Id_Subtype) is
- Cursor : Id_Maps.Cursor_Type;
+ Position : Id_Maps.Cursor;
begin
loop
Synthesize_Random_String (Id);
- Cursor := Find (Id_Map, Key => Id);
- exit when Cursor = Null_Cursor; -- good: not found
+ Position := Find (Id_Map, Key => Id);
+ exit when Position = No_Element; -- good: not found
end loop;
end Generate_Id;
@@ -3095,160 +4468,30 @@
function Setup_Session return Session_Access is
- I : Id_Maps.Cursor_Type;
+ I : Id_Maps.Cursor;
B : Boolean;
Id : Id_Subtype;
- begin
- Generate_Id (Id);
-
- Insert
- (Map => Id_Map,
- Key => Id,
- Cursor => I,
- Success => B;
- ...
- end Setup_Session;
-
-This works, but we can do better. The problem is that Insert duplicates
-the work done just earlier by Find, when checking the newly-synthesized
-id for uniqueness.
-
-Find is a bit of a sledgehammer: it tells us that the key isn't already
-in the map, but it doesn't tell us anything else. What would like to
-ask the container is, if the key isn't in the map, can you tell me who
-its neighbor would be?
-
-The function we're interested in is called Lower_Bound, which searches
-the container for the smallest key in the map not less than some key.
-It satisfies the invariant that
-
- Key <= Lower_Bound (Set, Key)
-
-The result of Lower_Bound is a cursor that designates the node that
-matches Key, if indeed Key is already in the map, or a cursor that
-designates its successor, if Key is not in the map. To disambiguate
-which case we have we only need to make a simple test:
-
- Cursor := Lower_Bound (Set, Key);
-
- if Key < Cursor then
- ... -- no match: Key is not in the map
- else
- ... -- match: Key is equivalent to Key (Cursor)
- end if;
-
-Let's rewrite our Generate_Id procedure so that it returns this extra
-information:
-
- procedure Generate_Id
- (Id : out Id_Subtype;
- Hint : out Id_Maps.Cursor_Type) is
- begin
- loop
- Synthesize_Random_String (Id);
- Hint := Lower_Bound (Id_Map, Key => Id);
- exit when Hint = Back (Id_Map); -- no match
- exit when Id < Hint; -- no match
- end loop;
- end Generate_Id;
-
-Now we can rewrite our constructor to use this new information during
-insertion:
-
- function Setup_Session return Session_Access is
-
- I : Id_Maps.Cursor_Type;
- B : Boolean;
-
- Id : Id_Subtype;
- Hint : Id_Maps.Cursor_Type;
begin
- Generate_Id (Id, Hint);
+ Generate_Id (Id); -- Id is guaranteed to be unique
Insert
- (Map => Id_Map,
- Position => Hint,
+ (Container => Id_Map,
Key => Id,
- Cursor => I,
- Success => B;
-
- pragma Assert (B);
- pragma Assert (Succ (I) = Hint);
+ Position => I,
+ Success => B);
...
end Setup_Session;
-
-Here we use the insert-with-hint procedure, which specifies where to
-begin searching for a matching Id. Since Hint is the result of
-Lower_Bound, we know the hint is useful and therefore the insertion has
-amortized constant time. It's hard to beat that!
-
-This is a great because we can test whether insert will succeed, and
-then reuse the results our test so that the insertion itself has
-essentially no cost. Thus we have a way to first search for a key and
-then insert it later, without incuring any penalty.
-
-When a client issues a play request, he can specify the time from which
-play begins. This lets him jump to any position in the file and play
-from that point. Let's assume a video frame index is implemented as a
-sorted set, with elements that look like this:
-
- 0 9 34 42 50 78 85 ...
-
-where the numbers above represent the time of the leading edge of each
-video frame in the file.
-
-If the play request specifies a time, we have to find the frame that
-"goes with" that time, which means the frame whose leading edge comes at
-or before the time specified.
-
-This is kind of like a floor function. You might think you could use
-Lower_Bound to do it, like this:
-
- function Floor (Time : Time_Type) return Cursor_Type is
- begin
- return Lower_Bound (Video_Index, Key => Time);
- end;
-
-This would work if the key matched a value already in the index, for
-example:
-
- Floor (42) = Lower_Bound (VI, 42) = 42
-
-The problem is if the key isn't in the index. Lower_Bound returns the
-smallest key in the container equal to or greater than a key, e.g.
-
- Floor (45) = Lower_Bound (VI, 45) = 50
-
-But this isn't what we want. The "floor" of 45 is 42, not 50.
-
-The solution is to use Upper_Bound, which returns the smallest key in the
-container greater than a key, and then back up one position:
-
- function Floor (Time : Time_Type) return Cursor_Type is
- begin
- return Pred (Upper_Bound (VI, Key => Time));
- end;
-This works for all key values:
+One issue with this algorithm is that Insert duplicates the work done
+just earlier by Find, when checking the newly-synthesized id for
+uniqueness. A simple way to efficiently generate a unique session id
+and insert it into the map is to just check whether the insertion
+succeeded:
- Floor (42) = Pred (UB (VI, 42)) = Pred (50) = 42
- Floor (45) = Pred (UB (VI, 45)) = Pred (50) = 42
-
-And now all is well. Note that it doesn't matter if you specify some
-large key value that is greater than every key in the set. In that case
-Upper_Bound returns Back, and the Pred of Back is Last, which is just
-what we want.
-
-The previous two examples were intended to demonstrate the utility of
-the Lower_Bound and Upper_Bound functions, and to show how
-insert-with-hint can be used to improve performance. Another way to
-efficiently generate a unique session id and insert it into the map is
-to simply check whether the insertion succeeded:
-
function Setup_Session return Session_Access is
- Cursor : Id_Maps.Cursor_Type;
+ Position : Id_Maps.Cursor;
Success : Boolean;
Id : Id_Subtype;
@@ -3260,10 +4503,10 @@
Generate_Id (Id);
Insert
- (Map => Id_Map,
- Key => Id,
- Cursor => Cursor,
- Success => Success;
+ (Container => Id_Map,
+ Key => Id,
+ Position => Position,
+ Success => Success);
exit when Success;
@@ -3298,9 +4541,9 @@
This allows us to instantiate the set in the normal way:
package Employee_Sets is
- new Ada.Containers.Sets.Sorted.Unbounded (Employee_Type);
+ new Ada.Containers.Ordered_Sets (Employee_Type);
- Employees : Employee_Sets.Set_Type;
+ Employees : Employee_Sets.Set;
When someone gets a job at our firm, we add them to our little database
as follows:
@@ -3308,11 +4551,14 @@
procedure Hire (Name : Name_Type; SSN : SSN_Type; ...) is
Employee : Employee_Type;
+
+ Position : Employee_Sets.Cursor;
+ Success : Boolean;
begin
Employee.SSN := SSN;
Employee.Name := Name;
...
- Insert (Employees, New_Item => Employee);
+ Insert (Employees, Employee, Position, Success);
end;
Now let's suppose that we need to modify some information for an
@@ -3329,16 +4575,16 @@
(SSN : SSN_Type;
New_Home : Home_Address_Type) is
- Iter : Cursor_Type;
+ Position : Cursor;
begin
declare
Dummy : Employee_Type;
begin
Dummy.SSN := SSN;
- Iter := Find (Employees, Item => Dummy);
+ Position := Find (Employees, Item => Dummy);
end;
- if Iter /= Null_Iter then ...;
+ if Has_Element (Position) then ...;
end;
But this is kind of a hack. I don't really want to make a dummy element
@@ -3356,15 +4602,15 @@
return Employee.SSN < SSN;
end;
- function "<"
- (SSN : SSN_Type;
- Employee : Employee_Type) return Boolean is
+ function ">"
+ (Employee : Employee_Type;
+ SSN : SSN_Type) return Boolean is
begin
- return SSN < Employee.SSN;
+ return Employee.SSN > SSN;
end;
package SSN_Keys is
- new Employee_Sets.Generic_Keys (SSN_Type);
+ new Employee_Sets.Generic_Keys (SSN_Type); --accept defaults
With this new package we can now look up the employee by his SSN
directly:
@@ -3373,9 +4619,9 @@
(SSN : SSN_Type;
New_Home : Home_Address_Type) is
- Iter : Cursor_Type := Find (Employees, Key => SSN);
+ Position : Cursor := Find (Employees, Key => SSN);
begin
- if Iter /= Null_Iter then ...;
+ if Has_Element (Position) then ...;
end;
Now let's say that the employee's wallet was stolen, which contained his
@@ -3383,22 +4629,22 @@
apply for a new social security number, and then change his entry in the
database.
-We need to copy him out of
-the set, change the value of the SSN field, and then (re)insert him:
+We need to copy him out of the set, change the value of the SSN field,
+and then (re)insert him:
procedure Change_SSN
(Old_SSN : SSN_Type;
New_SSN : SSN_Type) is
- Cursor : Cursor_Type := Find (Employees, Key => Old_SSN);
+ Position : Cursor := Find (Employees, Key => Old_SSN);
Success : Boolean;
begin
- if Cursor /= Null_Cursor then
+ if Has_Element (Position) then
declare
- Employee : Employee_Type := Element (Cursor);
+ Employee : Employee_Type := Element (Position);
begin
Employee.SSN := New_SSN;
- Insert (Employees, Employee, Cursor, Success);
+ Insert (Employees, Employee, Position, Success);
end;
end if;
end Change_SSN;
@@ -3407,13 +4653,20 @@
it is like this:
procedure Display is
+
+ procedure Process (I : in Employee_Sets.Cursor) is
+
+ procedure Do_Print (E : in out Employee_Type) is
+ begin
+ Put ("Name: "); Put (E.Name);
+ Put ("SSN: "); Put (E.SSN);
+ ...;
+ end;
- procedure Process (I : in Employee_Sets.Cursor_Type) is
- E : Employee_Type renames To_Constant_Access (I).all;
+ procedure Print is
+ new Generic_Update (Do_Print);
begin
- Put ("Name: "); Put (E.Name);
- Put ("SSN: "); Put (E.SSN);
- ...;
+ Print (Position => I);
end;
procedure Print is
@@ -3432,83 +4685,90 @@
option.
A much better way is not to copy elements directly but rather to copy
-cursors that designate those elements. Here we use a vector, which
-comes with its own sort operation:
+cursors that designate those elements:
- package Vector_Types is
- new Ada.Containers.Vectors
- (Index_Type => Positive,
- Element_Type => Employee_Sets.Cursor_Type);
+ procedure Display_Employees_In_Name_Order is
- procedure Display is
+ function "<" (L, R : Employee_Sets.Cursor)
+ return Boolean is
- Vector : Vector_Types.Vector_Type;
+ Result : Boolean;
- begin -- Display
+ procedure Process_LE (LE : in out Employee_Type) is
- declare
- procedure Process (I : Employee_Sets.Cursor_Type) is
- begin
- Vector_Types.Append (Vector, New_Item => I);
- end;
+ procedure Process_RE (RE : in out Employee_Type) is
+ begin
+ Result := LE.Name < RE.Name;
+ end;
+
+ procedure Update_R is
+ new Generic_Update (Process_RE);
+ begin
+ Update_R (R);
+ end Process_LE;
- procedure Populate_Vector is
- new Employee_Sets.Generic_Iteration; -- "Process"
+ procedure Update_L is
+ new Generic_Update (Process_LE);
begin
- Vector_Types.Resize (Vector, Size => Employee_Sets.Length (Employees));
- Populate_Vector (Employees);
+ Update_L (L);
+ return Result;
end;
- declare
- function "<" (L, R : Employee_Sets.Cursor_Type)
- return Boolean is
+ type Cursor_Array is
+ array (Size_Type range <>) of Employee_Sets.Cursor;
- EL : Employee_Type renames To_Constant_Access (L).all;
- ER : Employee_Type renames To_Constant_Access (R).all;
- begin
- return EL.Name < ER.Name;
- end;
+ procedure Sort is
+ new Generic_Array_Sort (Size_Type, Cursor, Cursor_Array);
+
+ procedure Do_Print (E : in out Employee_Type) is
+ begin
+ Put ("Name: "); Put (E.Name);
+ Put ("SSN: "); Put (E.SSN);
+ ...;
+ end;
+
+ procedure Print is
+ new Generic_Update (Do_Print);
+
+ C : Employee_Sets.Cursor := First (Employee_Sets);
- procedure Sort is
- new Vector_Types.Generic_Sort; -- "<"
+ function Get_Cursor return Employee_Sets.Cursor is
+ Result : Cursor := C;
begin
- Sort (Vector);
+ Next (C);
+ return Result;
end;
- Print_Employees:
- for Index in First (Vector) .. Last (Vector) loop
- declare
- C : Employee_Sets.Cursor_Type := Element (Vector, Index);
- E : Employee_Type renames To_Constant_Access (C).all;
- begin
- Put ("Name: "); Put (E.Name);
- Put ("SSN: "); Put (E.SSN);
- ...;
- end;
- end loop Print_Employees;
-
- end Display;
-
-First we use the passive iterator for sets to insert a cursor
-designating every employee into the vector container. Next we
-define an order for relation for vector elements, which here are just set
-cursors. We wish to print employees in order of name, so the order
-relation for cursors is defined in terms of the names of the employees
-designated by the cursors.
-
-Note carefully that we didn't use the element selector for cursors:
-
- EL : Employee_Type := Element (C); -- wrong!
-
-This would make a copy of the employee designated by the cursor, which
-is not what we want at all. That would undermine our reason for sorting
-set cursors instead of set elements. So we used our element access
-selector, which returns an access object.
-
-Now that the employees (really, cursors that designate the employees) have
-been sorted, we a loop to traverse all the set cursors, and print each
-employee (in name order) in turn.
+ Cursors : Cursor_Array (1 .. Length (Employee_Set)) :=
+ (others => Get_Cursor);
+ begin
+
+ Sort (Cursors);
+
+ for Index in Cursors'Range loop
+ C := Cursors (Index);
+ Print (Position => C);
+ end loop;
+
+ end Display_Employees_In_Name_Order;
+
+First we use an active iterator for sets to insert a cursor designating
+every employee into the array. Next we define an order for relation for
+the array elements, which here are just set cursors. We wish to print
+employees in order of name, so the order relation for cursors is defined
+in terms of the names of the employees designated by the cursors.
+
+Implementing the sort order relation turns out to slightly tricky,
+because we don't want to make a copy of the employee just do get its
+name. We use nested instantiations of Generic_Update to create a
+context in which both employee objects are directly visible, and then
+compare employee names by querying the employee elements directly.
+
+Now that the employees (really, cursors that designate the employees)
+have been sorted, we loop to traverse all the set cursors, and print
+each employee (in name order) in turn.
+
In you were paying very careful attention to the Id_Map hashed-map
example, you might have realized that since the session object (which
was the element of the map) had an Id field, we were in fact duplicating
@@ -3524,10 +4784,10 @@
end;
package Session_Set_Types is
- new Ada.Containers.Sets.Sorted.Unbounded (Session_Access);
+ new Ada.Containers.Ordered_Sets (Session_Access);
-- instead of Id_Map, use a set to store sessions:
- Session_Set : Session_Set_Types.Set_Type;
+ Session_Set : Session_Set_Types.Set;
function "<"
(Session : Session_Access;
@@ -3536,11 +4796,11 @@
return Session.Id < Id;
end;
- function "<"
- (Id : String;
- Session : Session_Access) return Boolean is
+ function ">"
+ (Session : Session_Access;
+ Id : String) return Boolean is
begin
- return Id < Session.Id;
+ return Session.Id > Id;
end;
package Id_Keys is
@@ -3553,17 +4813,17 @@
NPT_Range : in NPT_Range_Type;
RTSP_Status : out RTSP_Status_Type) is
- Cursor : constant Session_Set_Types.Cursor_Type :=
+ Position : constant Session_Set_Types.Cursor :=
Find (Session_Set, Key => Session_Id);
Session : Session_Access;
begin
- if Cursor = Null_Cursor then
+ if Position = No_Element then
RTSP_Status := RTSP.Session_Not_Found;
return;
end if;
- Session := Element (Cursor);
+ Session := Element (Position);
Play (Session, NPT_Range, RTSP_Status);
end;
@@ -3574,7 +4834,7 @@
function Setup_Session return Session_Access is
Session : constant Session_Access := new Session_Type; -- allocate
- Cursor : Session_Set_Types.Cursor_Type;
+ Position : Session_Set_Types.Cursor;
Success : Boolean;
begin
Generate_Id (Session.Id);
@@ -3582,7 +4842,7 @@
Insert
(Container => Sessions_Set,
New_Item => Session, -- element, has its own key
- Cursor => Cursor,
+ Position => Position,
Success => Success);
...
return Session;
@@ -3598,13 +4858,13 @@
Session.Id = Id;
end;
- procedure Insertion is
+ procedure Insert is
new Id_Types.Generic_Insertion; -- accept default
function Setup_Session return Session_Access is
Session : Session_Access; -- no allocation here
- Cursor : Session_Set_Types.Cursor_Type;
+ Position : Session_Set_Types.Cursor;
Success : Boolean;
Id : Id_Subtype;
@@ -3614,10 +4874,10 @@
Insert
(Container => Sessions_Set,
Key => Id, -- key, not element
- Cursor => Cursor,
+ Position => Position,
Success => Success);
- Session := Element (Cursor); -- element was allocated in Set_Key
+ Session := Element (Position); -- element was allocated in Set_Key
...
return Session;
end;
@@ -6513,6 +7773,61 @@
are implemented as a controlled type that contains a value by
reference. The swap for that element could then just swap the pointers,
instead of finalizing and then adjusting controlled objects.
+
+****************************************************************
+
+Comments on parameter names, Randy Brukardt, April 16, 2004.
+
+Most of the parameter names in the containers libraries are "Container".
+
+We considered using more functional names. We started with Insert:
+
+ procedure Insert (Container : in out Vector;
+ Before : in Cursor;
+ New_Item : in Element_Type;
+ Count : in Size_Type := 1);
+
+One possibility would be to use what Ada.Strings.Unbounded uses. The parameter
+there is named "Source". That appears to be for compatibility with the
+function version of the routine, but it is clearly inappropriate for a
+procedure. So no help there.
+
+Another possibility would be to use "Into":
+
+ procedure Insert (Into : in out Vector;
+ Before : in Cursor;
+ New_Item : in Element_Type;
+ Count : in Size_Type := 1);
+
+which makes nice named calls:
+
+ Insert (Into => My_Vector, Before => Blob, New_Item => An_Item);
+
+Similarly, Append and Prepend could use "To":
+
+ procedure Append (To : in out Vector;
+ Before : in Cursor;
+ New_Item : in Element_Type;
+ Count : in Size_Type := 1);
+
+And Delete could use "From":
+
+ procedure Delete (From : in out Vector;
+ Position : in Cursor;
+ Count : in Size_Type := 1);
+
+but then "Position" should really be "At" -- except that it's reserved in Ada.
+
+And Replace_Element and Find should use "In", but that is clearly not going
+to work. We could use "Inside", but that's a stretch.
+
+Then, we'd have to find something to use for the various functions. The
+existing:
+ function Last (Container : Vector) return Cursor;
+makes as much sense as anything I can come up with.
+
+I don't think that the above buy enough to change Matt's choices (except for
+a couple obvious mistakes, already fixed).
****************************************************************
Questions? Ask the ACAA Technical Agent