!standard A.17 04-02-02 AI95-00302-03/01 !class amendment 04-01-14 !status work item 04-01-14 !status received 04-01-14 !priority Medium !difficulty Hard !subject Container library !summary The following API describes a standard container library for Ada. The library comprises sequence containers (vectors), for inserting elements at specified positions, and associative containers (sets and maps), which position elements in order by key. The library is general, flexible, and efficient, and its design has been guided by the philosophy that a library should stay out of the programmer's way. !problem If is often the case that the solution to a programming problem requires a collection of elements. The Ada language of course provides a built-in array type, but typical problems often require a data structure with better time behavior or more sophisticated semantics. Even if you can get by with using an array, any non-trivial array manipulation quickly becomes unwieldy, and hence error-prone. An array is also not general enough in that it only provides a mapping from a discrete index to the element type. The developer typically needs a container that can map an element to any arbitrary type. The key type often needs to be a string, but of course this cannot be used as an array index subtype. With no general-purpose standard container library, a developer is left to craft his own container type. The data structure invariably chosen is some kind of linked-list, because it's relatively simple. However, manipulation of raw access types tends to be error-prone, and is a source of memory leaks. A linked-list also does not perform well as a general-purpose set or map when the number of elements is large. One argument for having a standard library is that it's nice to be able to use a language right out-of-the-box. If a developer has to leave the language to solve common problems then perhaps that is a sign the language doesn't provide enough support for the developer. Other languages with which Ada competes, such as C++ or Java, come with rich standard container libraries. Many existing container libraries are either badly designed or difficult to use. One issue is that it should be simple and easy to instantiate a component. If it requires more than a single instantiation to create a useable container, then it's too much pain and no developer will bother. Or if he does bother his experience will be unpleasant. Programming is work, but it should be fun work, not drudgery. Libraries often have the problem that they are not sufficiently general, or simply not intended as industrial-strength libraries. The library designer can't possibly predict all the myriad uses to which his library will be put, and so the library must be general and flexible enough to suit unimagined uses. Another problem is that these libraries often don't scale well to large numbers of elements. Their behavior is neither predictable nor is it even specified. They are often both time and space inefficient for various other reasons. In real-time programs especially, it's important to have predictable run-time behavior. An industrial-strength, general-purpose standard container library must provide containers that perform better than linear time complexity. Searches in particular need to be fast. !proposal This library API proposal is modeled on the Standard Template Library (STL), an algorithms and data structure library popularized by Alexander Stepanov, and included in the C++ standard library. We can broadly characterize containers as being either "sequence containers" or "associative containers." All sequence containers allow insertion and deletion at any position in the container, but each one optimizes differently for insertions at certain positions. Associative containers associate elements with a key, which defines how elements are ordered in the container. A vector is a sequence container optimized for insertion at the back end. It of course allows insertion at any position, but as you move 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.) 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 itself. The map associative containers scatter keys in the container according to a hash function. The hash table is automatically resized when the number of elements equals the number of buckets. Insertions and searches therefore have a time complexity of O(1) on average. 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. There is also a package of routines for managing case-insensitive strings, and library-level subprograms for returning the hash value of strings. This API is based on an existing container library called Charles. The source code itself and a couple of papers about the design of Charles can be found at: Following the API proper, this proposal concludes with an examples section that illustrates the kinds of problems the library solves, and the most effective way to use the library to solve them. !wording Add Ada.Strings.Hash, Ada.Strings.Unbounded.Hash, and Ada.Strings.Case_Insensitive to A.4.7(29). [This gives us Wide_ versions of these packages and functions.] A.4.8 Hashing and String Comparison Static Semantics The following library-level subprograms and packages are defined: [Question: 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); with Ada.Containers; function Ada.Strings.Unbounded.Hash (Key : Unbounded_String) return 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 "<=" (Left, Right : String) return Boolean; function Hash (Key : String) return Containers.Hash_Type; end Ada.Strings.Case_Insensitive; 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). 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). 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 a wide spread of values for different string values. [Query: Anybody got better wording? Matt was nice enough to ignore these definitions completely!] A.17 Containers This clause presents the specifications of the package Containers and several child packages, which provide facilities for storing collections of elements. AARM Text Language Design Principles This clause provides a number of useful containers for Ada. Only the most useful containers are provided. Ones that are relatively easy to code, redundant, or rarely used are omitted from this set, even if they are generally included in containers libraries. The containers packages are modeled on the Standard Template Library (STL), an algorithms and data structure library popularized by Alexander Stepanov, and included in the C++ standard library. The structure and terminology differ from the STL where that better maps to common Ada usage. For instance, what the STL 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. The containers packages are structured so that additional packages can be added in the future. Indeed, we hope that these packages provide the basis for a more extensive secondary standard for containers. If containers with similar functionality (but different performance characteristics) are provided, we suggest that a prefix be used to identify the class of the functionality: "Ada.Containers.Bounded_Sets" (for a set with a maximum number of elements); "Ada.Containers.Protected_Maps" (for a map which can be accessed by multiple tasks at one time); "Ada.Containers.Persistent_Vectors" (for a persistent vector which continues to exist between executions of a program) and so on. Note that the language already includes several requirements that are important to the use of containers. First, library packages must be reentrant - multiple tasks can use the packages as long as they operate on separate containers. Thus, it is only necessary for a user to protect a container if a single container needs to be used by multiple tasks. Second, the language requires that language-defined types stream "properly". That means that the stream attributes can be used to implement persistence of containers when necessary, and containers can be passed between partitions of a program. End AARM Text A.17.1 The Package Containers The package Containers is the root of the containers subsystem. Static Semantics The library package Containers has the following declaration: package Ada.Containers is pragma Pure; type Hash_Type is mod ; end Ada.Containers; Hash_Type represents the range of the result of a hash function. Implementation Requirements Hash_Type'Modulus shall be at least as large as the smaller of System.Max_Binary_Modulus and 2**32. [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.] 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. 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 array. Static Semantics The library package Containers.Vectors has the following declaration: generic type Index_Type is (<>); type Element_Type is private; with function "=" (Left, Right : Element_Type) return Boolean is <>; package Ada.Containers.Vectors is pragma Preelaborate; pragma Assert (Index_Type'Base'First < Index_Type'First); subtype Index_Subtype is Index_Type; type Vector_Type is private; function "=" (Left, Right : Vector_Type) return Boolean; function Length (Vector : Vector_Type) return Natural; function Is_Empty (Vector : Vector_Type) return Boolean; procedure Clear (Vector : in out Vector_Type); procedure Swap (Left, Right : in out Vector_Type); procedure Append (Vector : in out Vector_Type; New_Item : in Element_Type); procedure Insert (Vector : in out Vector_Type; Before : in Index_Type'Base; New_Item : in Element_Type); procedure Insert (Vector : in out Vector_Type; Before : in Index_Type'Base); procedure Insert_N (Vector : in out Vector_Type; Before : in Index_Type'Base; Count : in Natural; New_Item : in Element_Type); procedure Insert_N (Vector : in out Vector_Type; Before : in Index_Type'Base; Count : in Natural); procedure Delete (Vector : in out Vector_Type; Index : in Index_Type'Base); procedure Delete_Last (Vector : in out Vector_Type); procedure Delete_N (Vector : in out Vector_Type; First : in Index_Type'Base; Count : in Natural); function Size (Vector : Vector_Type) return Natural; procedure Resize (Vector : in out Vector_Type; Size : in Natural); function Front (Vector : Vector_Type) return Index_Type'Base; function First (Vector : Vector_Type) return Index_Type; function First_Element (Vector : Vector_Type) return Element_Type; function Last (Vector : Vector_Type) return Index_Type'Base; function Last_Element (Vector : Vector_Type) return Element_Type; function Back (Vector : Vector_Type) return Index_Type'Base; function Element (Vector : Vector_Type; Index : Index_Type'Base) 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); generic with function "<" (Left, Right : Element_Type) return Boolean is <>; procedure Generic_Sort (Vector : in Vector_Type); private ... -- not specified by the language end Ada.Containers.Vectors; [Open issue: Should Index_Type be "range <>" instead of "(<>)"? 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).] If an object of type Vector_Type is not otherwise initialized, it will initialized with a size (internal array length) of 0. function "=" (Left, Right : Vector_Type) 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. function Length (Vector : Vector_Type) return Natural; The Length function returns the number of active elements in Vector. function Is_Empty (Vector : Vector_Type) return Boolean; Equivalent to Length (Vector) = 0. procedure Clear (Vector : in out Vector_Type); Sets the length of Vector to 0. Its size does not change. procedure Swap (Left, Right : in out Vector_Type); Exchanges the internal array and element count of Left and Right. procedure Append (Vector : in out Vector_Type; New_Item : in Element_Type); Equivalent to Insert (Vector, Back (Vector), New_Item). procedure Insert (Vector : in out Vector_Type; Before : in Index_Type'Base; New_Item : in Element_Type); Equivalent to Insert_N (Vector, Before, 1, New_Item). procedure Insert (Vector : in out Vector_Type; Before : in Index_Type'Base); Equivalent to Insert_N (Vector, Before, 1). procedure Insert_N (Vector : in out Vector_Type; Before : in Index_Type'Base; Count : in Natural; New_Item : in Element_Type); If Count has the value 0, then Insert_N 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. If the current vector size is greater than or equal to the new length, then Insert_N 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. Otherwise if the current vector size is less than the new length, Insert_N 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_N 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_N (Vector : in out Vector_Type; Before : in Index_Type'Base; Count : in Natural); Equivalent to Insert_N (Vector, Before, Count, New_Item), with the difference that the elements in the Count positions starting at Before are not assigned. procedure Delete (Vector : in out Vector_Type; Index : in Index_Type'Base); 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. procedure Delete_Last (Vector : in out Vector_Type); Equivalent to Delete (Vector, Last (Vector)). procedure Delete_N (Vector : in out Vector_Type; First : in Index_Type'Base; Count : in Natural); If Count is 0, the operation has no effect. If First does not specify a value in the range First (Vector) .. Last (Vector), then Constraint_Error is propagated. Otherwise Delete_N slides the active elements (if any) starting First plus Count down to First. Any exceptions raised during element assignment are propagated. function Size (Vector : Vector_Type) return Natural; Returns the length of the internal array. procedure Resize (Vector : in out Vector_Type; Size : in Natural); 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.] function First (Vector : Vector_Type) return Index_Type; Returns the value Index_Type'First. function First_Element (Vector : Vector_Type) return Element_Type; Equivalent to Element (Vector, First (Vector)). function Last (Vector : Vector_Type) return Index_Type'Base; Returns the position of the last element in Vector. function Last_Element (Vector : Vector_Type) return Element_Type; Equivalent to Element (Vector, Last (Vector)). function Back (Vector : Vector_Type) return Index_Type'Base; Equivalent to Index_Type'Succ (Last (Vector)). function Element (Vector : Vector_Type; 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 element at position Index. 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. 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. generic with function "<" (Left, Right : Element_Type) return Boolean is <>; procedure Generic_Sort (Vector : in Vector_Type); Reorders the elements of Vector 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. 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 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. Implementation Requirements No storage associated with a vector Vector_Type 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 roughly proportional to the number of elements in the vector. [Open issue: We should say that Containers.Vectors.Generic_Sort is O(N log N) on average, 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. 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 itmes 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! Containers.Vectors.Generic_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. A.17.3 The Package Containers.Maps The language-defined package Containers.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. Static Semantics The library package Containers.Maps has the following declaration: generic type Key_Type is private; type Element_Type is private; with function Hash (Key : Key_Type) return Hash_Type is <>; with function Is_Equal_Key (Left, Right : Key_Type) return Boolean is "="; with function "=" (Left, Right : Element_Type) return Boolean is <>; package Ada.Containers.Maps is pragma Preelaborate; type Map_Type is private; type Cursor_Type is private; Null_Cursor : constant Cursor_Type; function "=" (Left, Right : Map_Type) return Boolean; function Length (Map : Map_Type) return Natural; function Is_Empty (Map : Map_Type) return Boolean; procedure Clear (Map : in out Map_Type); procedure Swap (Left, Right : in out Map_Type); procedure Insert (Map : in out Map_Type; Key : in Key_Type; New_Item : in Element_Type; Cursor : out Cursor_Type; Success : out Boolean); procedure Replace (Map : in out Map_Type; Key : in Key_Type; New_Item : in Element_Type); procedure Insert (Map : in out Map_Type; Key : in Key_Type; Cursor : out Cursor_Type; Success : out Boolean); procedure Delete (Map : in out Map_Type; Key : in Key_Type); procedure Delete (Map : in out Map_Type; Cursor : in out Cursor_Type); function Is_In (Key : Key_Type; Map : Map_Type) return Boolean; function Find (Map : Map_Type; Key : Key_Type) return Cursor_Type; function Element (Map : Map_Type; Key : Key_Type) return Element_Type; function Size (Map : Map_Type) return Hash_Type; procedure Resize (Map : in out Map_Type; Size : in Hash_Type); function First (Map : Map_Type) return Cursor_Type; function Back (Map : Map_Type) return Cursor_Type; function Succ (Cursor : Cursor_Type) return Cursor_Type; procedure Increment (Cursor : in out Cursor_Type); function Key (Cursor : Cursor_Type) return Key_Type; generic type Key_Access is access constant Key_Type; function Generic_Key (Cursor : Cursor_Type) return Key_Access; function Is_Equal_Key (Left, Right : Cursor_Type) return Boolean; function Is_Equal_Key (Left : Cursor_Type; Right : Key_Type) return Boolean; function Is_Equal_Key (Left : Key_Type; Right : Cursor_Type) return Boolean; function Element (Cursor : Cursor_Type) return Element_Type; generic type Element_Access is access all Element_Type; function Generic_Element (Cursor : Cursor_Type) return Element_Access; procedure Replace_Element (Cursor : in Cursor_Type; By : in Element_Type); generic with procedure Process (Cursor : in Cursor_Type) is <>; procedure Generic_Iteration (Map : in Map_Type); private ... -- not specified by the language end Ada.Containers.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. AARM Note The expected implementation for a Map uses a hash table which is grown when it is too small, with linked lists hanging off of each bucket. Note that in that implementation a cursor needs a back pointer to the Map object to implement iteration; that could either be in the nodes, or in the cursor object. Function Hash is expected to return the same result value each time it is called with a particular key value. For any two key values for which Is_Equal_Key returns True, Hash should return the same result value. If Hash behaves in some other manner, the behavior of this package is unspecified. AARM Note 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. The function Length returns the number of key/element pairs in Container. The function Is_Empty is equivalent to Length (Map) = 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. [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.] procedure Insert (Map : in out Map_Type; Key : in Key_Type; New_Item : in Element_Type; Cursor : out Cursor_Type; 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 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. AARM Note: Insert should only compare elements that hash to the same bucket in the hash table. procedure Replace (Map : in out Map_Type; 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. procedure Insert (Map : in out Map_Type; Key : in Key_Type; Cursor : out Cursor_Type; Success : out Boolean); 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. AARM Note: Find 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); 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. function Find (Map : Map_Type; Key : Key_Type) return Cursor_Type; If Length (Map) equals 0, then this function returns Null_Cursor. 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. AARM Note: Find should only compare elements that hash to the same bucket in the hash table. The function Is_In is equivalent to Find (Map, Key) /= Null_Cursor. The function Element is equivalent to Element (Find (Map, Key)). The function Size returns the size of Map. procedure Resize (Map : in out Map_Type; Size : in Hash_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. function First (Map : Map_Type) return Cursor_Type; If Length (Map) = 0, then it returns Null_Cursor. Otherwise, it returns a that designates the first hashed node in Map. 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 (I); end loop; end; [Open issue: This implies that Vectors ought to have Increment and Decrement procedures.] function Succ (Cursor : Cursor_Type) return Cursor_Type; 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 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 next non-empty bucket. The procedure Increment is equivalent to Cursor := Succ (Cursor). function Key (Cursor : Cursor_Type) return Key_Type; If Cursor equals Null_Cursor, then Constraint_Error is propagated. Otherwise, this operation returns the key component of node designated by Cursor. generic type Key_Access is access constant Key_Type; function Generic_Key (Cursor : Cursor_Type) return Key_Access; 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. The function Is_Equal_Key (Left, Right : Cursor_Type) is equivalent to Is_Equal_Key (Key (Left), Key (Right)). The function Is_Equal_Key (Left : Cursor_Type; Right : Key_Type) is equivalent to Is_Equal_Key (Key (Left), Right). The function Is_Equal_Key (Left : Key_Type; Right : Cursor_Type) is equivalent to Is_Equal_Key (Left, Key (Right)). function Element (Cursor : Cursor_Type) return Element_Type; 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. generic with procedure Process (Cursor : in Cursor_Type) is <>; procedure Generic_Iteration (Map : in Map_Type); Generic_Cursor calls Process with a cursor that designates each node in the Map. Any exceptions raised during Process are propagated. Legality Rules An instantiation of Containers.Maps 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 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. Implementation Requirements No storage associated with a map Map_Type 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. A.17.4 The Package Containers.Maps.Strings The package Containers.Maps.Strings 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.Maps does, with the difference that predefined type String is the key. Static Semantics The declaration of the library package Containers.Maps.Strings has the same contents as Containers.Maps except: * There is no generic formal Key_Type. Everywhere the formal type Key_Type is specified, it is systematically replaced by type String. * The Generic_Key function is omitted. A.17.5 The Package Containers.Maps.Wide_Strings Static Semantics The declaration of the library package Containers.Maps.Wide_Strings has the same contents as Containers.Maps.Strings except that everywhere the formal type String is specified, it is systematically replaced by type Wide_String. A.17.6 The Package Containers.Sorted_Sets 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. AARM Note: This is called "Sorted_Sets" so as to allow a possible future enhancement to include unsorted sets (which would be called "Sets"). Static Semantics The package Containers.Sorted_Sets has the following declaration: generic type Element_Type is private; with function "<" (Left, Right : Element_Type) return Boolean is <>; with function "=" (Left, Right : Element_Type) return Boolean is <>; package Ada.Containers.Sorted_Sets is pragma Preelaborate; type Set_Type is private; type Cursor_Type is private; Null_Cursor : constant Cursor_Type; function "=" (Left, Right : Set_Type) return Boolean; function "<" (Left, Right : Set_Type) return Boolean; function "<=" (Left, Right : Set_Type) return Boolean; function ">" (Left, Right : Set_Type) return Boolean; function ">=" (Left, Right : Set_Type) return Boolean; function Length (Set : Set_Type) return Natural; function Is_Empty (Set : Set_Type) return Boolean; procedure Clear (Set : in out Set_Type); procedure Swap (Left, Right : in out Set_Type); procedure Insert (Set : in out Set_Type; New_Item : in Element_Type; Cursor : out Cursor_Type; Success : out Boolean); 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 (Set : in out Set_Type; Item : in Element_Type); procedure Delete (Set : in out Set_Type; Cursor : in out Cursor_Type); procedure Delete_Sans_Increment (Set : in out Set_Type; Cursor : in out Cursor_Type); procedure Delete_First (Set : in out Set_Type); procedure Delete_Last (Set : in out Set_Type); function Is_In (Item : Element_Type; Set : Set_Type) return Boolean; function Find (Set : Set_Type; Item : Element_Type) return Cursor_Type; function Lower_Bound (Set : Set_Type; Item : Element_Type) return Cursor_Type; function Upper_Bound (Set : Set_Type; Item : Element_Type) return Cursor_Type; function First (Set : Set_Type) return Cursor_Type; function First_Element (Set : Set_Type) return Element_Type; function Last (Set : Set_Type) return Cursor_Type; function Last_Element (Set : Set_Type) return Element_Type; function Back (Set : Set_Type) return Cursor_Type; function Succ (Cursor : Cursor_Type) return Cursor_Type; function Pred (Cursor : Cursor_Type) return Cursor_Type; procedure Increment (Cursor : in out Cursor_Type); procedure Decrement (Cursor : in out Cursor_Type); function "<" (Left, Right : Cursor_Type) return Boolean; function "<" (Left : Cursor_Type; Right : Element_Type) return Boolean; function "<" (Left : Element_Type; Right : Cursor_Type) return Boolean; function Element (Cursor : Cursor_Type) return Element_Type; generic type Element_Access is access constant Element_Type; function Generic_Element (Cursor : Cursor_Type) return Element_Access; generic with procedure Process (Cursor : in Cursor_Type) is <>; procedure Generic_Iteration (Set : in Set_Type); generic with procedure Process (Cursor : in Cursor_Type) is <>; procedure Generic_Reverse_Iteration (Set : in Set_Type); generic type Key_Type (<>) is limited private; with function "<" (Left : Element_Type; Right : Key_Type) return Boolean is <>; with function "<" (Left : Key_Type; Right : Element_Type) return Boolean is <>; package Generic_Keys is pragma Preelaborate; function Is_In (Key : Key_Type; Container : Set_Type) return Boolean; function Find (Container : Set_Type; Key : Key_Type) return Cursor_Type; function Element (Container : Set_Type; 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; Key : in Key_Type); function "<" (Left : Cursor_Type; Right : Key_Type) return Boolean; function "<" (Left : Key_Type; Right : Cursor_Type) return Boolean; generic with procedure Set_Key (Element : in out Element_Type; Key : in Key_Type) is <>; package Generic_Insertion is 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; 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. function "=" (Left, Right : Set_Type) 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 using the generic formal equality operator for elements. Any exception raised during evaluation of element equality is propagated. If a corresponding pair of elements compare False, the function returns False. Otherwise if all corresponding elements compare True, the function returns True. function "<" (Left, Right : Set_Type) return Boolean; If Left denotes the same object as Right, then the function returns False. Otherwise, it compares elements in sequential order using the generic formal less-than operator for elements. Any exception raised during evaluation of less-than is propagated. If an element in Left compares less than a corresponding element in Right, the function returns True. If there are no more elements in Left, then if there are more elements in Right, then the function returns True; otherwise if there no more elements in Right, then it returns False. If there are more elements in Left but none remaining in Right, then the function returns False. The function "<=" is equivalent to not (Left > Right). The function ">" is equivalent to Right < Left. The function ">=" is equivalent to not (Left < Right). The function Length returns the number of elements in Set. The function Is_Empty is equivalent to Length (Set) = 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. Swap exchanges all the nodes (including the sentinel) of Left and Right. procedure Insert (Set : in out Set_Type; New_Item : in Element_Type; Cursor : out Cursor_Type; Success : out Boolean); Insert compares New_Item to the elements in Set 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 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. 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); 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. procedure Delete (Set : in out Set_Type; Cursor : in out Cursor_Type); 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. procedure Delete_Sans_Increment (Set : in out Set_Type; Cursor : in out Cursor_Type); Equivalent to Delete (Set, Cursor), with the difference that the cursor value returned equals Null_Cursor. procedure Delete_First (Set : in out Set_Type); 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. procedure Delete_Last (Set : in out Set_Type); 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. function Find (Set : Set_Type; Item : Element_Type) return Cursor_Type; 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 Null_Cursor. The function Is_In is equivalent to Find (Set, Item) /= Null_Cursor. function Lower_Bound (Set : Set_Type; Item : Element_Type) return Cursor_Type; 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). 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 First_Element (Set : Set_Type) return Element_Type; 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; Returns a cursor that designates the node containing the greatest element. If Set is empty, it returns Back (Set). function Last_Element (Set : Set_Type) return Element_Type; If Set is empty, then Constraint_Error is propagated. Otherwise, it returns the element on the node designated by Last (Set). function Back (Set : Set_Type) return Cursor_Type; Returns a cursor that designates the sentinel node. function Succ (Cursor : Cursor_Type) return Cursor_Type; If Cursor equals Null_Cursor, then Constraint_Error is propagated. Otherwise it returns the successor of the node designated by Cursor. 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 Pred (Cursor : Cursor_Type) return Cursor_Type; If Cursor equals Null_Cursor, then Constraint_Error is propagated. Otherwise it returns the predecessor of the node designated by Cursor. AARM NOTE The predecessor of First is Back, and the predecessor of Back is Last. The procedure Increment is equivalent to Cursor := Succ (Cursor). The procedure Decrement is equivalent to Cursor := Pred (Cursor). The function "<" (Left, Right : Cursor_Type) is equivalent to Element (Left) < Element (Right). The function "<" (Left : Cursor_Type; Right : Element_Type) is equivalent to Element (Left) < Right. The function "<" (Left : Element_Type; Right : Cursor_Type) is equivalent to Left < Element (Right). function Element (Cursor : Cursor_Type) return Element_Type; If Cursor equals Null_Cursor, then Constraint_Error is propagated. Otherwise, it returns the element on the node designated by Cursor. generic type Element_Access is access constant Element_Type; function Generic_Element (Cursor : Cursor_Type) return Element_Access; If Cursor equals Null_Cursor, 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. generic with procedure Process (Cursor : in Cursor_Type) is <>; procedure Generic_Iteration (Set : in Set_Type); Invokes Process with a cursor that designates each (non-sentinel) node in Set. generic with procedure Process (Cursor : in Cursor_Type) is <>; procedure Generic_Reverse_Iteration (Set : in Set_Type); Iterates over the nodes in Set 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. 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. Legality Rules An instantiation of Containers.Sorted_Sets 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 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. 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. AARM Note This can be accomplished with a balanced (red-black) tree for keys. !example A.17.2 The Package Containers.Vectors Append is the canonical method for inserting items into a vector container: procedure Copy (A : Array_Subtype) is V : Vector_Type; begin Resize (V, Size => A'Length); for I in A'Range loop Append (V, New_Item => A (I)); end loop; ... end Copy; The Resize operation tells the vector object to preallocate an internal array having at least the size specified. If you need to perform many repeated insertions, then if you know the ultimate length apriori you should always call Resize beforehand. This is more efficient because it allocates the internal array once, and therefore avoids the repeated reallocation, copying, and deallocation cycles that might be necessary otherwise as the array is expanded. You can use a vector to implement a stack in the traditional way: package Stacks is new Ada.Containers.Vectors (ET); use Stacks; Stack : Stacks.Vector_Type; procedure Push (E : in ET) is begin Append (Stack, New_Item => E); end; function Top return ET is begin return Last_Element (Stack); end; procedure Pop is begin 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_N 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; I : in Index_Type'Base) is J : Index_Type'Base := I; begin Insert_N (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 J := J + 1; end loop; ... 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: type Element_Access is access all Element_Subtype; for Element_Access'Storage_Size use 0; function To_Access is new Generic_Element (Element_Access); procedure Finalize (Element : in out Element_Subtype) is ...; procedure My_Clear (V : in out Vector_Type) is begin for I in First (V) .. Last (V) loop Finalize (To_Access (V, I).all); end loop; Clear (V); end My_Clear; Here we use the Generic_Element selector function to get a variable view of the vector elements. 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: procedure Clear_And_Deallocate (V : in out Vector_Type) is V2 : Vector_Type; -- internal array is null begin Swap (V, V2); 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 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: procedure Reclaim_Storage (V : in out Vector_Type) is Temp : Vector_Type := V; begin Swap (V, 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. 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, 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: procedure Pop (V : in out Vector_Type) is procedure Free is new Ada.Unchecked_Deallocation (T, T_Access); begin Free (To_Access (V, Last (V)).all); 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: procedure Op (V : in Vector_Type) is I : Index_Subtype := Last (V); J : constant Index_Subtype'Base := Front (V); begin while I /= J 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: procedure Op (V : in Vector_Type) is procedure Process (E : in Element_Subtype) is ...; begin for I in First (V) .. Last (V) loop Process (E => Element (V, I)); end loop; end Op; 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: type Inner_Vector_Access is access all Inner_Vector_Type; for Inner_Vector_Access'Storage_Size use 0; function To_Access is new Generic_Element (Inner_Vector_Access); procedure Append (V : Vector_of_Vectors.Vector_Type; I : Index_Type'Base; E : Element_Subtype) is Inner_Vector : Inner_Vector_Type renames To_Access (V, I).all; begin Append (Inner_Vector, New_Item => E); 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 (V, Before => Back (V)); -- no item declare E : Element_Subtype renames To_Access (V, Last (V)).all; begin -- now modify E 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 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; begin Swap (L, VE); end; 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: 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 (V, Before => Back (V)); -- create a new element in V Swap (V, Last (V), L); -- swap new element in V with L end; 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: procedure Swap (V : in out Vector_of_Vectors.Vector_Type; I, J : in Index_Type'Base) is 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; 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 I : Index_Subtype := ...; E : Element_Subtype := ...; begin Insert (V, Before => I, New_Item => E); ... -- modify E some more Replace_Element (V, Index => I, By => E); -- aka V(I) := E; end; 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); procedure Post_Process (Histogram : in String_Integer_Maps.Map_Type) is Vector : Vector_Types.Vector_Type; procedure Process (I : in String_Integer_Maps.Cursor_Type) is begin Vector_Types.Append (Vector, New_Item => I); end; procedure Populate_Vector is new String_Integer_Maps.Generic_Iteration; -- use default name begin -- Post_Process Resize (Vector, Length (Histogram)); Populate_Vector (Histogram); ... -- see below end Post_Process; 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: declare function "<" (L, R : String_Integer_Maps.Cursor_Type) return Boolean is begin return Element (L) > Element (R); -- yes end; procedure Sort is new Vector_Types.Generic_Sort; -- use "<" default begin Sort (Vector); 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: 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; procedure Sort is new Vector_Types.Generic_Sort; -- use "<" default begin Sort (Vector); end; To display the results, all we have to do is iterate through the sorted vector: 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; 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; 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. A.17.3 The Package Containers.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 perform the insertions. This preallocates a hash table that is properly sized, and thus avoids the automatic rehashing that occurs during normal insertion to preserve the load factor. For example: procedure Op (N : Natural) is Map : Map_Types.Map_Type; -- Size = 0 Cursor : Map_Types.Cursor_Type; Success : Boolean; begin Resize (Map, 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, Success => Success); end loop; ... end Op; 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.) The simplest and fastest way to iterate over all the elements in the map is to use one of the passive iterator: procedure Op (Map : in Map_Types.Map_Type) is procedure Process (I : in Map_Types.Cursor_Type) is K : Key_Subtype := Key (I); E : Element_Subtype := Element (I); begin ... -- do whatever end; procedure Iterate is new Generic_Iteration; -- accept default name begin Iterate (Map); end; You could implement this function yourself, by iterating over the items in the map: procedure Op (Map : in Map_Types.Map_Type) is procedure Process (I : in Map_Types.Cursor_Type) is ...; I : Map_Types.Cursor_Type; begin I := First (Map); while I /= Null_Cursor loop Process (I); Increment (I); end loop; end Op; 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); The implementation would look something like this: procedure Generic_Algorithm (First, Back : in IT) is I : IT := First; begin while I /= Back loop ... Process (I); ... I := Succ (I); 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 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 containers in the library -- it even works for built-in array types. 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 Process (Cursor : Cursor_Type) is ...; 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. 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 completes asynchronously, the OS delivers an RT signal that specifies the file descriptor of the socket whose I/O completed. The problem is that I typically declare the socket as part the representation of some abstraction that gets allocated dynamically, and therefore I have no idea which object the socket belonged to, so I have no idea how to act on the information the OS is providing me. The abstraction I have in mind looks like this: package Sessions is type Session_Type (<>) is limited private; function Session_Access is access all Session_Type; function Setup_Session return Session_Type; -- ctor procedure Play (Session : access Session_Type; Stream : in String); ... procedure IO_Completion (Session : access Session_Type); private type Session_Type is limited record Socket : Socket_Type; ...; end Session_Type; end Sessions; 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: function Hash_FD is new Ada.Containers.Generic_Hash_Discrete (C.int); -- or whatever package FD_Map_Types is new Ada.Containers.Maps (Key_Type => C.int, Element_Type => Session_Access, Hash => Hash_FD); Now I can declare a map object in the body: package Sessions is ... FD_Map : FD_Map_Types.Map_Type; 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 this as the key to insert the session object into the map: function Setup_Session return Session_Access is Session : constant Session_Access := new Session_Type; Cursor : FD_Map_Types.Cursor_Type; Success : Boolean; begin Open (Session.Socket, ...); Insert (Map => FD_Map, Key => FD (Session.Socket), New_Item => Session, Cursor => Cursor, Success => Success); ... return Session; end; Now that the session object has inserted itself into the map, I can use map lookup to find that session when I receive a signal. Something like: procedure Handle_Signal (Siginfo : in Siginfo_Type) FD : constant C.int := Siginfo.FD; Iter : constant Cursor_Type := Find (FD_Map, Key => FD); begin if Iter /= Null_Cursor then IO_Completion (Element (Iter)); end if; end Handle_Signal; and then the session object reacts to the I/O completion accordingly. A.17.4 The Package Containers.Maps.Strings 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: with Ada.Strings.Hash_String; package Wordcount_Maps is new Ada.Containers.Maps.Strings (Element_Type => Natural, Hash => Ada.Strings.Hash_String); -- case-sensitive Map : Wordcount_Maps.Map_Type; Here we've specified the hash function for strings provided by the library. The scanning phase looks like this: Open (File, In_File, Name); Scan_Lines: while not End_Of_File (File) loop Get_Line (File, Line, Line_Last); Line_First := Line'First; Scan_Line: loop Find_Token (Line (Line_First .. Line_Last), ...); exit when Word_Last = 0; -- the interesting part happens here: Insert (Word => Line (Word_First .. Word_Last)); Line_First := Word_Last + 1; end loop Scan_Line; end loop Scan_Lines; Now all we have to do is implement Insert. That function looks like this: procedure Insert (Word : String) is Cursor : Wordcount_Maps.Cursor_Type; Success : Boolean; type Count_Access is access all Natural; function To_Element_Access is new Wordcount_Maps.Generic_Element (Count_Access); begin -- Insert Insert (Map => Map, Key => To_Lower (Word), New_Item => 0, -- yes Cursor => Cursor, Success => Success); declare N : Natural renames To_Element_Access (Cursor).all; begin N := N + 1; end; end Insert; Map (and set) insertion works conditionally. It searches the container to determine whether there is an equal key already in the map. Note that in the example above, the New_Item parameter has the value 0. This is deliberate. What happens is that if the word is already in the map, then the insertion "fails" in the sense that no new node is allocated. Rather, Insert reports the fact that the key was already in the map (by returning the value False for Success), and a cursor that designates the node with the matching key. 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 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 designates the newly-inserted element (really, it designates the node containing that key/element pair). When we alias the element, the count has the value 0, and so by incrementing it the count gets set to the 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. To dump the contents of the map, you can use the passive iterator: declare procedure Process (I : in Wordcount_Maps.Cursor_Type) is begin Put (Key (I)); Put (':'); Put (Element (I)); New_Line; end; procedure Dump is new Wordcount_Maps.Generic_Iteration; -- "Process" begin Dump (Map); end; 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: declare Vector : Vector_Type; procedure Process (I : Wordcount_Maps.Cursor_Type) is begin Append (Vector, New_Item => I); end; procedure Populate_Vector is new Wordcount_Maps.Generic_Iteration; -- "Process" begin Populate_Vector (Map); ... -- see vector end; 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. 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 frames to the client. Ultra-efficient file I/O is usually done by memory-mapping the sections on disk. Typically, a server maintains its own file cache, so that many clients streaming the same file can share the memory-mapped sections. When the client request comes in, the server must look up the file by name in order to see if it's in cache. If it's already in cache, then we increment a reference count. If it's not, we create some context for the file and create a new entry for it in the cache. Suppose the context type looks like this: type Context_Type is limited record File : File_Type; Ref_Count : Natural; ...; end record; type Context_Access is access Context_Type; Our cache is just a map, indexed by file name: package File_Cache_Types is new Ada.Containers.Maps.Strings (Element_Type => Context_Access, Hash => Ada.Strings.Hash_String_Case_Insensitive, Is_Equal_Key => Ada.Containers.Equal_String_Case_Insensitive); File_Cache : File_Cache_Types.Map_Type; The naive way to implement the lookup is: procedure Setup (Name : in String) is Cursor : File_Cache_Types.Cursor_Type := Find (File_Cache, Key => Name); Success : Boolean; Context : Context_Access; begin -- Setup if Cursor = Null_Cursor then Context := new Context_Type; Context.Ref_Count := 0; ... -- init Context Insert (Map => File_Cache, Key => Name, New_Item => Context, Cursor => Cursor, Success => Success); else Context := Element (Iter); end if; Context.Ref_Count := Context.Ref_Count + 1; ... -- use Context end Setup; The problem is that we're duplicating work: we first searched for the file context in the cache, and if it wasn't found we insert a new entry, which just searches again. The correct way to do this is as follows: procedure Setup (Name : in String) is Iter : File_Cache_Types.Cursor_Type; Not_In_Cache : Boolean; Context : Context_Access; begin Insert (Map => File_Cache, Key => Name, New_Item => null, -- yes Cursor => Cursor, Success => Not_In_Cache); if Not_In_Cache then pragma Assert (Element (Iter) = null); Context := new Context_Type; Context.Ref_Count := 0; ... -- init context Replace_Element (Iter, By => Context); else Context := Element (Iter); end if; Context.Ref_Count := Context.Ref_Count + 1; ... -- use context end Setup; Here we make an insertion attempt, by trying to insert a null context into the map. If it's already in the map, then the insertion fails, but that's just what we want to happen, because we wish to share the file already in cache. If it's not in the map, the insertion succeeds, by creating a slot for this file (the context is null), which we just fill in with a newly-allocated context object. In the RTSP protocol, requests are sent to a server in (clear) text. To create a session, a client connects to the server and sends it a SETUP request, e.g. SETUP rtsp://mheaney/thematrix.avi RTSP/1.0 Transport: ... Each RTSP session has a "session id," which is a random string of characters at least 8 characters long. When a SETUP request doesn't specify a session id, this is interpreted to mean that the client wishes to create a new session. On the server side, it allocates a session object (described above), and generates a session id for it. The representation of the session object looks like this: type Session_Type is limited record Id : String (1 .. 8); ...; end record; And the session constructor looks like: function Setup_Session return Session_Access is Session : constant Session_Access := new Session_Type; begin Generate_Id (Session.Id); ... -- see below end; The server responds by including the session id in the response: RTSP/1.0 200 OK Session: HAiye8-r And thereafter, a client sends requests to a session by specifying a session id header: PLAY rtsp://mheaney/thematrix.avi RTSP/1.0 Range: npt=101.42- Session: HAiye8-r The server-side problem is this. When the server receives the request from the client, it parses the request and looks for a session id. The problem then becomes finding the session object that is associated with that unique id. There might very well be hundreds of session objects, so whatever method we use has to run fast. (The is a real-time streaming server, and RTSP request/response overhead must be kept to a minimum.) What we do is declare a string-key map object that uses the session id as the key, and a Session_Access as the element, like this: package Id_Maps is new Ada.Containers.Maps.Strings (Element_Type => Session_Access, Hash => Ada.Strings.Hash_String); -- case-sensitive Id_Map : Id_Maps.Map_Type; use Id_Maps; When the session is allocated, we insert the id/session pair into the map like this: function Setup_Session return Session_Access is Session : constant Session_Access := new Session_Type; Cursor : Id_Map_Types.Cursor_Type; Success : Boolean; begin Generate_Id (Session.Id); Insert (Map => Id_Map, Key => Session.Id, New_Item => Session, Cursor => Cursor, Success => Success); ... return Session; end; When a client issues a request, we parse out the session id, and then forward the command to the session object associated with that session id key: procedure Play (Session_Id : in String; NPT_Range : in NPT_Range_Type; RTSP_Status : out RTSP_Status_Type) is Iter : constant Cursor_Type := Find (Id_Map, Key => Session_Id); Session : Session_Access; begin if Iter = Null_Cursor then RTSP_Status := RTSP.Session_Not_Found; return; end if; Session := Element (Iter); 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: procedure Free (X : in out Session_Access); What's the best way to remove the object from the map? Since the session knows its own Id, it can use the key-form of Delete: procedure Free (X : in out Session_Access) is begin if X /= null then Delete (Id_Map, Key => X.Id); Deallocate (X); end if; end; Another option is to use the cursor-form of Delete. What we can do is cache the cursor returned by Insert as part of the state of the session object: function Setup_Session return Session_Access is Session : constant Session_Access := new Session_Type; Success : Boolean; begin Generate_Id (Session.Id); Insert (Map => Id_Map, Key => Session.Id, New_Item => Session, Cursor => Session.Id_Map_Iter, Success => Success); pragma Assert (Success); pragma Assert (Key (Session.Id_Map_Iter) = Session.Id); pragma Assert (Element (Session.Id_Map_Iter) = Session); ... return Session; end Setup_Session; Now we can implement Free this way: procedure Free (X : in out Session_Access) is begin if X /= null then Delete (Id_Map, Cursor => X.Id_Map_Iter); Deallocate (X); end if; end; 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. 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. 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; ... 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 (I : Id_Map_Types.Cursor_Type) is Session : Session_Access renames To_Access (I).all; begin Free (Session); -- free map element directly 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; A.17.6 The Package Containers.Sorted_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 A : Integer_Array (1 .. Length (S)); I : Integer_Sets.Cursor_Type := First (S); J : Positive := A'First; begin while I /= Back (S) loop A (J) := Element (I); Increment (I); J := J + 1; end loop; ... end Op; Here we're incrementing both the array index and the set cursor manually. However, when you're iterating over two containers simultaneously, you can often let one or the other drive the iteration, so that only one position needs to be incremented manually. We can change the example use a built-in for loop: procedure Op (S : in Integer_Sets.Set_Type) is A : Integer_Array (1 .. Length (S)); I : Integer_Sets.Cursor_Type := First (S); begin for J in A'Range loop A (J) := Element (I); Increment (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: procedure Op (S : in Integer_Sets.Set_Type) is A : Integer_Array (1 .. Length (S)); J : Positive := A'First; procedure Process (I : Integer_Sets.Cursor_Type) is begin A (J) := Element (I); J := J + 1; end; procedure Fill_Array_A is new Integer_Sets.Generic_Iteration; -- accept default begin Fill_Array_A (S); ... end Op; This lets the set drive the iteration. Let's continue the streaming server examples from earlier. In TCP, a client "connects" to a server, who is "listening" on a port known to the client. When the server "accepts" the connection, this establishes a dedicated connection with that client. We can reify this in code as follows: package Connections is type Connection_Type (<>) is limited private; type Connection_Access is access Connection_Type; function Accept_Connection (Socket : Socket_Type) return Connection_Access; -- the ctor for connection objects ... end Connections; We have a need to keep track of all of our current connections. So when we create a new connection object, what we do is insert it in a set: package body Connections is function "<" (L, R : Connection_Access) return Boolean is begin return L.all'Address < R.all'Address; end; package Connection_Sets is new Ada.Containers.Sorted_Sets (Connection_Access); Connection_Set : Connection_Sets.Set_Type; function Accept_Connection (Socket : Socket_Type) return Connection_Access is Connection : constant Connection_Access := new Connect_Type; Cursor : Connection_Sets.Cursor_Type; Success : Boolean; begin Insert (Set => Connection_Set, New_Item => Connection, Cursor => Cursor, Success => Success); ... return Connection; end; ... end Connections; When a new connection object is allocated, it is inserted into the Connection_Set. Here insertions will always succeed because each allocated object has a unique access value. Now let's suppose we want to shutdown a specific connection. We can do it like this: procedure Shutdown (X : in out Connection_Access) is begin if X /= null then Delete (Connection_Set, Item => X); Free (X); end if; end Shutdown; Here we use the item-form of Delete to simply remove the item from the set, and then deallocate it. Now let's suppose we want to shutdown the entire system, and so we need to clear out all of the connection objects. We could do it like this: procedure Shutdown_Connections is X : Connection_Access; begin while not Is_Empty (Connection_Set) loop X := First_Element (Connection_Set); Shutdown (X); 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); X : Connection_Access; begin while I /= Stop loop X := Element (I); Delete (Connection_Set, Cursor => 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. 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 random characters. One of our requirements for a session id is that it must be unique among all the sessions currently being streamed by this server. Even if we use a random number generator to synthesize characters, we still must check to ensure that this session id is unique. The obvious 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; begin loop Synthesize_Random_String (Id); Cursor := Find (Id_Map, Key => Id); exit when Cursor = Null_Cursor; -- good: not found end loop; end Generate_Id; The constructor for session objects generates a unique session id, and then uses the id as the key when inserting the new session object: function Setup_Session return Session_Access is I : Id_Maps.Cursor_Type; 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); Insert (Map => Id_Map, Position => Hint, Key => Id, Cursor => I, Success => B; pragma Assert (B); pragma Assert (Succ (I) = Hint); ... 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: 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; Success : Boolean; Id : Id_Subtype; begin -- Setup_Session loop Generate_Id (Id); Insert (Map => Id_Map, Key => Id, Cursor => Cursor, Success => Success; exit when Success; end loop; ... end Setup_Session; Here we don't need a separate call to Find, because the regular Insert operation does a search anyway. One of the canonical container examples is the set-of-employees. Suppose we have an employee type defined this way: type Employee_Type is record SSN : SSN_Type; -- social security no. Name : Name_Type; Home_Address : Home_Address_Type; ...; end record; To make a set, we need to establish an order relationship for its elements. Since each social security number is presumably unique (unless your identity has been stolen), we can use that to define an order for Employee_Type: function "<" (L, R : Employee_Type) return Boolean is begin return L.SSN < R.SSN; end; This allows us to instantiate the set in the normal way: package Employee_Sets is new Ada.Containers.Sets.Sorted.Unbounded (Employee_Type); Employees : Employee_Sets.Set_Type; When someone gets a job at our firm, we add them to our little database as follows: procedure Hire (Name : Name_Type; SSN : SSN_Type; ...) is Employee : Employee_Type; begin Employee.SSN := SSN; Employee.Name := Name; ... Insert (Employees, New_Item => Employee); end; Now let's suppose that we need to modify some information for an employee. Like a map, a set orders its elements in key order, except that for a set the element is its own key. In the example here, the key is really the SSN part of the employee object. Suppose we only know the employee's social security number. How do we find that employee? Remember that the "key" of a set is just the element itself. One way is to synthesize a dummy employee object, and then look it up by element type: procedure Change_Address (SSN : SSN_Type; New_Home : Home_Address_Type) is Iter : Cursor_Type; begin declare Dummy : Employee_Type; begin Dummy.SSN := SSN; Iter := Find (Employees, Item => Dummy); end; if Iter /= Null_Iter then ...; end; But this is kind of a hack. I don't really want to make a dummy element just to look up the real element. For many types synthesizing a dummy object this way might not even be possible. A much more elegant technique is to use the nested generic package Generic_Keys, which allows you to explicitly name the key-part of the element. We can instantiate that package like this: function "<" (Employee : Employee_Type; SSN : SSN_Type) return Boolean is begin return Employee.SSN < SSN; end; function "<" (SSN : SSN_Type; Employee : Employee_Type) return Boolean is begin return SSN < Employee.SSN; end; package SSN_Keys is new Employee_Sets.Generic_Keys (SSN_Type); With this new package we can now look up the employee by his SSN directly: procedure Change_Address (SSN : SSN_Type; New_Home : Home_Address_Type) is Iter : Cursor_Type := Find (Employees, Key => SSN); begin if Iter /= Null_Iter then ...; end; Now let's say that the employee's wallet was stolen, which contained his social security card. In order to prevent identity theft, he needs to 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: procedure Change_SSN (Old_SSN : SSN_Type; New_SSN : SSN_Type) is Cursor : Cursor_Type := Find (Employees, Key => Old_SSN); Success : Boolean; begin if Cursor /= Null_Cursor then declare Employee : Employee_Type := Element (Cursor); begin Employee.SSN := New_SSN; Insert (Employees, Employee, Cursor, Success); end; end if; end Change_SSN; Suppose now we want a list all the employees in the firm. One way to do it is like this: procedure Display is procedure Process (I : in Employee_Sets.Cursor_Type) is E : Employee_Type renames To_Constant_Access (I).all; begin Put ("Name: "); Put (E.Name); Put ("SSN: "); Put (E.SSN); ...; end; procedure Print is new Employee_Sets.Generic_Iteration; -- "Process" begin Print (Employees); end; However, this will list employees in order of their social security number. This is probably not what we want, which is to print employees in order of name. One way would be to copy the elements into some other container, which is sorted according to the criterion we desire. However, if elements are large or otherwise not easily copied, then this is not not really an 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: package Vector_Types is new Ada.Containers.Vectors (Index_Type => Positive, Element_Type => Employee_Sets.Cursor_Type); procedure Display is Vector : Vector_Types.Vector_Type; begin -- Display declare procedure Process (I : Employee_Sets.Cursor_Type) is begin Vector_Types.Append (Vector, New_Item => I); end; procedure Populate_Vector is new Employee_Sets.Generic_Iteration; -- "Process" begin Vector_Types.Resize (Vector, Size => Employee_Sets.Length (Employees)); Populate_Vector (Employees); end; declare function "<" (L, R : Employee_Sets.Cursor_Type) return Boolean is 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 Vector_Types.Generic_Sort; -- "<" begin Sort (Vector); 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. 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 the Id object, since it's also stored as the key-part of the map entry. In turns out we didn't really need to use a map. We could have used a set, and instantiated the generic package Generic_Keys using type String as the formal Key_Type. function "<" (L, R : Session_Access) return Boolean is begin return L.Id < R.Id; end; package Session_Set_Types is new Ada.Containers.Sets.Sorted.Unbounded (Session_Access); -- instead of Id_Map, use a set to store sessions: Session_Set : Session_Set_Types.Set_Type; function "<" (Session : Session_Access; Id : String) return Boolean is begin return Session.Id < Id; end; function "<" (Id : String; Session : Session_Access) return Boolean is begin return Id < Session.Id; end; package Id_Keys is new Session_Set_Types.Generic_Keys (String); This lets us perform session lookups based on the session identifier: procedure Play (Session_Id : in String; NPT_Range : in NPT_Range_Type; RTSP_Status : out RTSP_Status_Type) is Cursor : constant Session_Set_Types.Cursor_Type := Find (Session_Set, Key => Session_Id); Session : Session_Access; begin if Cursor = Null_Cursor then RTSP_Status := RTSP.Session_Not_Found; return; end if; Session := Element (Cursor); Play (Session, NPT_Range, RTSP_Status); end; We can insert a session object into the set in the normal way, using the item-form of insertion: function Setup_Session return Session_Access is Session : constant Session_Access := new Session_Type; -- allocate Cursor : Session_Set_Types.Cursor_Type; Success : Boolean; begin Generate_Id (Session.Id); Insert (Container => Sessions_Set, New_Item => Session, -- element, has its own key Cursor => Cursor, Success => Success); ... return Session; end; An alternate way to do this is to use the key-form of insertion: procedure Set_Key (Session : in out Session_Access; Id : in String) is begin Session := new Session_Type; Session.Id = Id; end; procedure Insertion 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; Success : Boolean; Id : Id_Subtype; begin Generate_Id (Id); Insert (Container => Sessions_Set, Key => Id, -- key, not element Cursor => Cursor, Success => Success); Session := Element (Cursor); -- element was allocated in Set_Key ... return Session; end; This example also illustrates that sets and maps are essentially the same. The only real difference is where the key lives. --!corrigendum A.17 !ACATS Test ACATS tests will be needed for this library. !appendix Report of the ARG Select Committee on Containers February 3, 2004 Executive Summary The committee selected the second proposal as a starting point for a standard containers library, with a number of simple changes. The changes were simple enough that we produced a version of the library with the changes made (AI-00302-3/01). The resulting proposal is not much larger than the Vector and Matrix libraries already adopted for the standard. It also should be a good seed for a more encompassing secondary standard. Therefore, we recommend that the ARG adopt this alternative for the standard. By the ARG Select Committee on Containers: Randy Brukardt Bob Duff Tucker Taft Full Report Goals A core library of containers is an important addition to Ada. Other competitive programming languages include standard sets of containers, and these are widely used. Users often note that a standard set of containers is a missing piece of Ada. In addition, adding such containers to the standard is not a large burden on implementers. However, the resources available for work on the standard preclude adding a large container library to the standard. If the library is too large, it will be insuffiently reviewed, and that has the danger of providing something useless. Therefore, the committee settled on a limited set of goals: (1) To provide a number of the most useful containers to Ada users in a standard fashion; (2) To provide a framework for future work in this area (hopefully leading to a secondary or de-facto standard). We considered other goals as well. Performance issues were deemed of secondary importance. Most uses of containers (indeed, most software) do not have critical performance requirements. To provide a library with the variety of components needed to meet critical requirements (bounded and unbounded forms, array and list implementations, etc.) would be beyond the resources available to work on the standard. Moreover, the existence of many components actually makes construction of simple applications harder: the programmer has to choose a component based on performance considerations that are simply irrelevant for the application. Evaluation of existing proposals We determined that the most important containers are the following: * extensible "vectors" (like an array, indexed by any discrete type); * (hashed) "maps" (or "hash table", with arbitrary keys); * (sorted) "sets" (set of arbitrary items). The names "map", "set", and "vector" are those used in the Java containers. We evaluated the two proposals for their support of these components. Alternative 1 (AI-302-1/07) contains a number of low level data structure components such as Lists, Bags, Queues, etc. These can be used to create "vector", "map", and "set" containers, but the containers themselves are absent. Moreover, most of these components are relatively easy to create when needed. Alternative 2 (AI-302-2/02) contains mainly five containers: vector, list, map, set, and multiset. These include the abstractions mentioned above. We also determined that the basic design was consistent and sound. Therefore, we discarded alternative 1, and concentrated on improving and simplifying alternative 2. We decided the sorts of changes that we would consider. The great value to having containers in the standard is that they are standard: everybody has them and can use them. Perfection is not required of the standard components. Moreover, what is one person's "improvement" is another's "mistake". In addition, we run the risk of introducing real errors by further fiddling. Therefore, we decided to simplify the interfaces by deleting unnecessary capabilities, by systematic substitutions, and by introducing missing capabilities (along with general wordsmithing). In particular, we avoided changing existing interfaces unless there was a clear error. The specific improvements and simplifications are detailed in the Appendix. Performance issues For the purposes of components in the standard, the precise performance of them is not important. Whatever the performance is will be good enough for the vast majority of uses - in prototyping, quick and dirty programs, and the majority of programs that aren't performance critical. Therefore, we provide only a single version of each component. We don't, for instance, provide both Vectors and Lists, which are really the same abstraction with the different performance characteristics. However, it is important that the performance characteristics of the components be specified. That is, if searches are expected to be no worse than O(N), we need to say that. That's because we want programs using the components to be portable. That wouldn't be true for programs using components with large numbers of items if the performance characteristics vary widely between implementations. Consider a Vector component. It could in theory be implemented with an array or with a linked list. The cost of an arbitrary insertion is O(N) for the array implementation and O(1) for the list implementation. If a program using a large vector is moved from a list implementation to an array implementation, the performance change could be so large as to make the program non-functional. That is unacceptable, so we specify minimum performance characteristics. But those characteristics are not intended to specify a particular implementation, only to insure that some characteristics can be relied upon. Therefore, the containers library needs to suggest some performance characteristics. We believe Implementation Advice is best for this purpose, as we don't have to be as precise in the language defining the characteristics, and implementations are required to document deviations from the given advice. Appendix Detailed changes made to the Alternative 2 proposal The Unchecked_Modification packages were dropped. These are just a hack to avoid copying keys - a solely performance-based concern. Other stuff does not logically belong in keys, and modifying the key value itself it a disaster waiting to happen. The Vector, List, and Multiset abstractions are essentially the same abstraction with differences in performance and details. When performance is not critical, only one is needed. The package structure has many levels of empty packages for organization. These are unnecessary when there are only a few packages. Moreover, related packages can be given similar names (i.e. "Bounded_Set", "Protected_Vector"), which provides all of the organization needed. The extra empty packages were eliminated. Similarly, "Unbounded" was dropped; these are the most general forms, and should be the ones used for general-purpose programming. Other forms (in a secondary standard) would be more specialized. We discussed dropping the special string maps. We eventually decided to keep them, because string maps are common, and a Map cannot be instantiated with "String" (the key type must be definite). We also discussed whether Sets should be sorted. We concluded that the extra cost of sorted insertions is fairly small, and thus there is little advantage to using unsorted sets other than when performance is critical (which again is not the purpose of the standard). We did, however, name the package "Sorted_Sets" so that a basic unsorted set could be provided in a secondary standard without contorted naming. We added a modular Hash_Type to Ada.Containers. The choice of Integer'Base is a horrible one on compilers that use 16-bit Integer (as allowed by the standard), and in any case, the hashing type should be modular. The string hash and comparison functions were moved to be part of the Ada.Strings heirarchy. It would be a bad idea to have the hash functions of all types gathered in one place (in the containers library). Unbounded string hash and comparison functions were added. We changed the type names to the more descriptive "Vector_Type", "Map_Type", and "Set_Type". These are much better for users who use Use clauses. The argument that having a common name makes it easier to change between containers is mostly irrelevant: changing between the provided containers is going to be rare. Moreover, qualifying "Container_Type" (that is, "Vector.Container_Type") would be necessary in any unit with more than one container -- eliminating any advantage for using the same name. The proposal confused the meaning of "iterator", using it both for the code that visits each element of a container (the conventional meaning) and the "handle" or "cursor" used to access an element of a container. We decided to use "cursor" for the second meaning to make the interfaces clearer. We added a sort routine to Vector. For some reason, this was only present in the (removed) List abstraction. Having a simple sort available can simplify many programming problems. We added legality rules that these packages must be instantiated at the library level. The requirement that these packages do not leak memory (like Ada.Strings.Unbounded) imply that they are implemented with controlled types (or something like controlled types). We do not want to implicitly require implementers to support nested controlled types without making that support available to users. (If AI-344 or AC-50 were adopted, we could drop these rules.) The proposal was completely missing definitions for the string hash and compare functions. Performance requirements were moved from the !proposal into Implementation Advice. As much as possible, mention of specific implementation strategies was moved into AARM notes following that Advice. (We're not going to specify red-black trees!). An Assert pragma was added to the Vector package to prevent instantiation with a type for which Index_Type'Base'First = Index_Type'First. For such a type, the initial value of Last and the value of Front must necessarily raise Constraint_Error. It's better to fail an assertion immediately, rather than during some later operation. The Map container in the proposal is far too specific to a particular implementation. It exposes that implementation in the interface, and as a result makes iteration operations harder. That seems like a bad choice for a simple abstraction; it's fine to suggest an implementation, but bad to make it part of the interface. We therefore simplied the interface and the description. (We consulted with the author of the proposal on this and other changes.) ****************************************************************