CVS difference for ais/ai-20302.txt
--- ais/ai-20302.txt 2004/11/02 01:50:33 1.11
+++ ais/ai-20302.txt 2004/11/03 00:47:46 1.12
@@ -1,4 +1,4 @@
-!standard A.17 04-10-04 AI95-00302-03/07
+!standard A.17 04-11-01 AI95-00302-03/08
!class amendment 04-01-14
!status work item 04-01-14
!status received 04-01-14
@@ -813,14 +813,14 @@
If Index does not specify a value in the range First_Index (Container) ..
Last_Index (Container), then Constraint_Error is propagated. Otherwise this
-function assigns the value By to the element at position Index. Any exceptions
+procedure assigns the value By to the element at position Index. Any exceptions
raised during the assignment are propagated. The element at position Index is
not an empty element after successful completion of this operation.
procedure Replace_Element (Position : in Cursor;
By : in Element_Type);
-This function assigns the value By to the element designated by Position.
+This procedure assigns the value By to the element designated by Position.
If Position equals No_Element, then Constraint_Error is propagated.
Any exception raised during the assignment is propagated. The element
designated by Position is not an empty element after successful completion of
@@ -1980,16 +1980,320 @@
remain in the original order). This is different than sorting an array or
vector, which may need to copy elements, and is probably not a stable sort.
-A.17.4 The Package Containers.Hashed_Maps
-The language-defined package Containers.Hashed_Maps provides private
-types Map and Cursor, and a set of operations for each type. A hashed
-map container allows an arbitrary type to be used as a key to find the
-element associated with that key.
+A.17.4 Maps
-AARM Note: The name is "Hashed_Maps" to allow for a secondary standard
-to include "Ordered_Maps".
+The language-defined packages Containers.Hashed_Maps and Containers.Ordered_Maps
+provide private types Map and Cursor, and a set of operations for each type.
+A map container allows an arbitrary type to be used as a key to find the
+element associated with that key. A hashed map uses a hash function to organize
+the keys, while an ordered map orders the keys per a specified relation.
+
+This section describes the declarations that are common to both kinds of maps.
+See A.17.5 for a description of the semantics specific to Containers.Hashed_Maps
+and A.17.6 for a description of the semantics specific to
+Containers.Ordered_Maps.
+The type Map is used to represent maps. The type Map needs finalization (see
+7.6).
+
+A map contains pairs of keys and elements, called *nodes*. Map cursors
+designate nodes, but also can be thought of as designating an element (the
+element contained in the node) for consistency with the other containers. There
+exists an equivalence relation on keys, whose definition is different for hashed
+maps and ordered maps. A map never contains two or more nodes with equivalent
+keys. The *length* of a map is the number of nodes it contains.
+
+Each nonempty map has two particular nodes called the *first node* and the *last
+node* (which may be the same). Each node except for the last node has a
+*successor node*. If there are no other intervening operations, starting with
+the first node and repeatedly going to the successor node will visit each node
+in the map exactly once until the last node is reached. The exact definition of
+these terms is different for hashed maps and ordered maps.
+
+Empty_Map represents the empty Map object. It has a length of 0. If an object
+of type Map is not otherwise initialized, it is initialized to the same
+value as Empty_Map.
+
+No_Element represents a cursor that designates no node. If an object of type
+Cursor is not otherwise initialized, it is initialized to the same
+value as No_Element.
+
+function "=" (Left, Right : Map) return Boolean;
+
+If Left and Right denote the same map object, then the function returns True. If
+Left and Right have different lengths, then the function returns False.
+Otherwise, for each key K in Left, the function returns False if:
+
+ * a key equivalent to K is not present in Right; or
+ * the element associated with K in Left is not equal to the element associated
+ with K in Right (using the generic formal equality operator for elements).
+
+If the function has not returned a result after checking all of the keys, it
+returns True. Any exception raised during evaluation of key equivalence or
+element equality is propagated.
+
+function Length (Container : Map) return Count_Type;
+
+Returns the number of nodes in Container.
+
+function Is_Empty (Container : Map) return Boolean;
+
+Equivalent to Length (Container) = 0.
+
+procedure Clear (Container : in out Map);
+
+Removes all the nodes from Container. Any exception raised during deallocation
+of
+storage is propagated.
+
+function Key (Position : Cursor) return Key_Type;
+
+If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
+Key returns the key component of the node designated by Position.
+
+function Element (Position : Cursor) return Element_Type;
+
+If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
+Element returns the element component of the node designated by Position.
+
+procedure Query_Element
+ (Position : in Cursor;
+ Process : not null access procedure (Key : in Key_Type;
+ Element : in Element_Type));
+
+If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
+Query_Element calls Process.all with the key and element from the node
+designated by Position as the arguments.
+
+procedure Update_Element
+ (Position : in Cursor;
+ Process : not null access procedure (Key : in Key_Type;
+ Element : in out Element_Type));
+
+If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
+Update_Element calls Process.all with the key and element from the node
+designated by Position as the arguments.
+
+If Element_Type is unconstrained and definite, then the Element parameter
+of Process.all shall be unconstrained.
+
+AARM Note: This means that the elements cannot be directly allocated from the
+heap (nor aliased unless AI-363 is included in the Amendment); it must be
+possible to change the discriminants of the element in place.
+
+procedure Replace_Element (Position : in Cursor;
+ By : in Element_Type);
+
+If Position equals No_Element, then Constraint_Error is propagated.
+Otherwise this operation assigns By to the element of the node designated by
+Position.
+
+procedure Move (Target : in out Map;
+ Source : in out Map);
+
+Move first clears Target. Then each node from Source is removed from Source and
+inserted into Target. The length of Source is 0 after a successful call to
+Move.
+
+procedure Insert (Container : in out Map;
+ Key : in Key_Type;
+ New_Item : in Element_Type;
+ Position : out Cursor;
+ Inserted : out Boolean);
+
+Insert checks if a node with a key equivalent to Key is already present in
+Container. If a match is found, Inserted is set to False and Position
+designates the element with the matching key. Otherwise, Insert allocates a new
+node, initializes it to Key and New_Item, and adds it to Container; Inserted is
+set to True and Position designates the newly-inserted node. Any exception
+raised during allocation is propagated and Container is not modified.
+
+procedure Insert (Container : in out Map;
+ Key : in Key_Type;
+ Position : out Cursor;
+ Inserted : out Boolean);
+
+Insert inserts Key into Container as per the five-parameter Insert, with the
+difference that an element initialized with any implicit initial values for any
+part (as for an object_declaration with no initialization expression - see
+3.3.1) is inserted.
+
+procedure Insert (Container : in out Map;
+ Key : in Key_Type;
+ New_Item : in Element_Type);
+
+Insert inserts Key and New_Item into Container as per the five-parameter
+Insert, with the difference that if a node with a key equivalent to Key is
+already in the map, then Constraint_Error is propagated.
+
+AARM Note: This is equivalent to:
+ declare
+ Inserted : Boolean; C : Cursor;
+ begin
+ Insert (Container, Key, New_Item, C, Inserted);
+ if not Inserted then
+ raise Constraint_Error;
+ end if;
+ end;
+but doesn't require the hassle of out parameters.
+
+procedure Include (Container : in out Map;
+ Key : in Key_Type;
+ New_Item : in Element_Type);
+
+Include inserts Key and New_Item into Container as per the five-parameter
+Insert, with the difference that if a node with a key equivalent to Key is
+already in the map, then this operation assigns Key and New_Item to the
+matching node. Any exception raised during assignment is propagated.
+
+AARM Note: This is equivalent to:
+ declare
+ C : Cursor := Find (Container, Key);
+ begin
+ if C = No_Element then
+ Insert (Container, Key, New_Item);
+ else
+ Replace (Container, Key, New_Item);
+ end if;
+ end;
+but this avoids doing the search twice.
+
+procedure Replace (Container : in out Map;
+ Key : in Key_Type;
+ New_Item : in Element_Type);
+
+Replace checks if a node with a key equivalent to Key is present in Container.
+If a match is found, Replace assigns Key and New_Item to the matching node;
+otherwise, Constraint_Error is propagated.
+
+AARM Note: We update the key as well as the element, as the key might include
+additional information that does not participate in equivalence. If only the
+element needs to be updated, use
+Replace_Element (Find (Container, Key), New_Element).
+
+procedure Delete (Container : in out Map;
+ Key : in Key_Type);
+
+Delete checks if a node with a key equivalent to Key is present in Container.
+If a match is found, Delete removes the node from the map; otherwise,
+Constraint_Error is propagated.
+
+procedure Delete (Container : in out Map;
+ Position : in out Cursor);
+
+If Position equals No_Element, Delete has no effect. If Position does not
+designate an element in Container, then Program_Error is propagated. Otherwise,
+Delete removes the node designated by Position from the map. Position is set to
+No_Element on return.
+
+AARM Note: The check on Position checks that the cursor does not belong to some
+other map. This check implies that a reference to the map is included in the
+cursor value. This wording is not meant to require detection of dangling
+cursors; such cursors are defined to be invalid, which means that execution is
+erroneous, and any result is allowed (including not raising an exception).
+
+procedure Exclude (Container : in out Map;
+ Key : in Key_Type);
+
+Exclude checks if a node with a key equivalent to Key is present in Container.
+If a match is found, Exclude removes the node from the map and then
+deallocates the node.
+
+function Contains (Container : Map;
+ Key : Key_Type) return Boolean;
+
+Equivalent to Find (Container, Key) /= No_Element.
+
+function Find (Container : Map;
+ Key : Key_Type) return Cursor;
+
+If Length (Container) equals 0, then Find returns No_Element. Otherwise, Find
+checks if a node with a key equivalent to Key is present in Container. If a
+match is found, a cursor designating the matching node is returned; otherwise,
+No_Element is returned.
+
+function Element (Container : Map;
+ Key : Key_Type) return Element_Type;
+
+Equivalent to Element (Find (Container, Key)).
+
+function First (Container : Map) return Cursor;
+
+If Length (Container) = 0, then First returns No_Element. Otherwise,
+First returns a cursor that designates the first node in Container.
+
+function Next (Position : Cursor) return Cursor;
+
+Returns a cursor that designates the successor of the node designated by
+Position. If Position designates the last node, then No_Element is returned. If
+Position equals No_Element, then No_Element is returned.
+
+procedure Next (Position : in out Cursor);
+
+Equivalent to Position := Next (Position).
+
+function Has_Element (Position : Cursor) return Boolean;
+
+Returns True if Position designates a node, and returns False otherwise.
+
+AARM Note: To Be Honest: This function may not detect cursors that designate
+deleted elements; such cursors are invalid (see below).
+
+procedure Iterate
+ (Container : in Map;
+ Process : not null access procedure (Position : in Cursor));
+
+Iterate calls Process.all with a cursor that designates each node in Container,
+starting with the first node and moving the cursor according to the successor
+relation. Any exception raised by Process.all is propagated. Program_Error is
+propagated if:
+ * Process.all attempts to insert or delete nodes from Container; or
+ * Process.all finalizes Container; or
+ * Process.all calls Move with Container as a parameter.
+
+AARM Note:
+This check takes place when the operations that insert or delete elements, etc.
+are called.
+
+See Iterate for vectors for a suggested implementation of the check.
+End AARM Notes.
+
+Erroneous Execution
+
+A Cursor value is *invalid* if any of the following have occurred since it was
+created:
+ * The map that contains the node it designates has been finalized;
+ * The map that contains the node it designates has been used as the
+ Source or Target of a call to Move;
+ * The node it designates has been deleted from the map.
+
+The result of "=" or Has_Element is unspecified if these function are called
+with an invalid cursor parameter. Execution is erroneous if any other subprogram
+declared in Containers.Hashed_Maps or Containers.Ordered_Maps is called with an
+invalid cursor parameter.
+
+Execution also is erroneous if the called Process.all procedure of a call to
+Query_Element or Update_Element executes an operation that causes the Position
+cursor of Query_Element or Update_Element to become invalid.
+
+AARM Notes: The list above is intended to be exhaustive. In other cases, a
+cursor value continues to designate its original element. For instance, cursor
+values survive the insertion and deletion of other nodes.
+
+While it is possible to check for these cases, in many cases the overhead
+necessary to make the check is substantial in time or space. Implementations
+are encouraged to check for as many of these cases as possible and raise
+Program_Error if detected.
+End AARM Notes.
+
+Implementation Requirements
+
+No storage associated with a Map object shall be lost upon assignment or
+scope exit.
+
+A.17.5 The Package Containers.Hashed_Maps
+
Static Semantics
The library package Containers.Hashed_Maps has the following
@@ -2028,8 +2332,9 @@
procedure Clear (Container : in out Map);
- function Element (Position : Cursor)
- return Element_Type;
+ function Key (Position : Cursor) return Key_Type;
+
+ function Element (Position : Cursor) return Element_Type;
procedure Query_Element
(Position : in Cursor;
@@ -2055,6 +2360,11 @@
procedure Insert (Container : in out Map;
Key : in Key_Type;
+ Position : out Cursor;
+ Inserted : out Boolean);
+
+ procedure Insert (Container : in out Map;
+ Key : in Key_Type;
New_Item : in Element_Type);
procedure Include (Container : in out Map;
@@ -2065,20 +2375,15 @@
Key : in Key_Type;
New_Item : in Element_Type);
- procedure Insert (Container : in out Map;
- Key : in Key_Type;
- Position : out Cursor;
- Inserted : out Boolean);
-
procedure Delete (Container : in out Map;
Key : in Key_Type);
- procedure Exclude (Container : in out Map;
- Key : in Key_Type);
-
procedure Delete (Container : in out Map;
Position : in out Cursor);
+ procedure Exclude (Container : in out Map;
+ Key : in Key_Type);
+
function Contains (Container : Map;
Key : Key_Type) return Boolean;
@@ -2090,11 +2395,6 @@
Key : Key_Type)
return Element_Type;
- function Capacity (Container : Map) return Count_Type;
-
- procedure Reserve_Capacity (Container : in out Map;
- Capacity : in Count_Type);
-
function First (Container : Map)
return Cursor;
@@ -2104,8 +2404,6 @@
function Has_Element (Position : Cursor) return Boolean;
- function Key (Position : Cursor) return Key_Type;
-
function Equivalent_Keys (Left, Right : Cursor)
return Boolean;
@@ -2121,6 +2419,11 @@
(Container : in Map;
Process : not null access procedure (Position : in Cursor));
+ function Capacity (Container : Map) return Count_Type;
+
+ procedure Reserve_Capacity (Container : in out Map;
+ Capacity : in Count_Type);
+
private
... -- not specified by the language
@@ -2128,38 +2431,32 @@
end Ada.Containers.Hashed_Maps;
An object of type Map contains an expandable hash table, which is used to
-provide direct access to elements. The *capacity* of an object of type Map is
-the maximum number of elements that can be inserted into the hash table prior
-to it being automatically expanded. The *length* of an object of type Map
-object is the number of elements it contains. If an object of type Map is not
-otherwise initialized, it will be initialized with a length of 0.
-
-A map contains pairs of keys and elements, called a *node*. Map cursors
-designate nodes, but also can be thought of as designating an element (the
-element contained in the node) for consistency with the other containers.
-
-The type Map needs finalization (see 7.6).
+provide direct access to nodes. The *capacity* of an object of type Map is the
+maximum number of nodes that can be inserted into the hash table prior to it
+being automatically expanded.
AARM Notes
-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. To provide an average O(1) access time, capacity would
-typically equal the number of buckets in such an implementation, so
-that the average bucket linked list length would be no more than 1.0.
+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. To
+provide an average O(1) access time, capacity would typically equal the number
+of buckets in such an implementation, so that the average bucket linked list
+length would be no more than 1.0.
-There is no defined relationship between elements in a map. Typically,
+There is no defined relationship between elements in a hashed map. Typically,
iteration will return elements in the order that they are hashed in.
End AARM Notes
-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
-Equivalent_Keys returns True, Hash should return the same result value. If Hash
-behaves in some other manner, the behavior of this package is unspecified.
-Which subprograms of this package call Hash, and how many times they call Hash,
-is unspecified.
+Two keys K1 and K2 are defined to be *equivalent* if Equivalent_Keys (K1, K2)
+returns True.
+Function Hash is expected to return the same value each time it is called with a
+particular key value. For any two equivalent key values, Hash is expected to
+return the same value. If Hash behaves in some other manner, the behavior of
+this package is unspecified. Which subprograms of this package call Hash, and
+how many times they call it, is unspecified.
+
AARM Notes
The implementation is not required to protect against Hash raising an exception,
or returning random numbers, or any other "bad" behavior. It's not practical to
@@ -2170,31 +2467,23 @@
logically a pure function), or the behavior is unspecified.
End AARM Notes
-Function Equivalent_Keys is expected to return the same result value each time
-it is called with a particular pair of key values. If Equivalent_Keys behaves
-in some other manner, the behavior of this package is unspecified. Which
-subprograms of this package call Equivalent_Keys, and how many times they call
-Equivalent_Keys, is unspecified.
+Function Equivalent_Keys is expected to return the same value each time it is
+called with a particular pair of key values. For any two keys K1 and K2, the
+boolean values Equivalent_Keys (K1, K2) and Equivalent_Key (K2, K1) are expected
+to be equal. If Equivalent_Keys behaves in some other manner, the behavior of
+this package is unspecified. Which subprograms of this package call
+Equivalent_Keys, and how many times they call it, is unspecified.
-AARM Notes
+AARM Note
As with Hash, the implementation is not required to protect against
-Equivalent_Keysraising an exception or returning random results. Similarly, the
+Equivalent_Keys raising an exception or returning random results. Similarly, the
implementation can call this operation whenever it is needed. The result must
remain the same (this is a logically pure function), or the behavior is
unspecified.
-Key equality for a map is named Equivalent_Keys in order that named notation
-can be used in an instantiation. Otherwise, there would be two parameters named
-"=", and named notation could not be used. This generic has too many formal
-parameters to allow confortable use of positional notation; named notation is
-required. Since key equality is likely to be overridden and needs to be
-frequently referenced in the wording, it is given the explicit name.
-End AARM Notes
-
If the value of a key stored in a node of a map is changed other than by an
-operation in this package such that at least one of Hash, Equivalent_Keys, or the
-generic formal equality operator give different results, the behavior of this
-package is unspecified.
+operation in this package such that at least one of Hash or Equivalent_Keys give
+different results, the behavior of this package is unspecified.
AARM Notes
The implementation is not required to protect against changes to key values
@@ -2210,417 +2499,872 @@
be possible to modify keys stored in a map. But we can't prevent this error
anymore than we can prevent someone passing as Hash a random number generator.
End AARM Notes
-
-Empty_Map represents the empty Map object. It has a length of 0. If an object
-of type Map is not otherwise initialized, it will be initialized to the same
-value as Empty_Map.
+Which nodes are the first node and the last node of a map, and which node is the
+successor of a given node, are unspecified, other than the general semantics
+described in A.17.4.
-No_Element represents a cursor that designates no element. If an object of type
-Cursor is not otherwise initialized, it will be initialized to the same
-value as No_Element.
+AARM Note
+Typically the first node will be the first node in the first bucket, the last
+node will be the last node in the last bucket, and the successor will be
+obtained by following the collision list, and going to the next bucket at the
+end of each bucket.
-function "=" (Left, Right : Map) return Boolean;
+procedure Clear (Container : in out Map);
-If Left and Right denote the same 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, for each key K in Left, the
-function returns False if:
- * a key equivalent to K is not present in Right (using the generic formal
- Equivalent_Keys function); or
- * the element associated with K in Left is not equivalent to the element
- associated with K in Right (using the generic formal equality operator for
- elements).
-If the function has not returned a result after checking all of the keys, the
-function returns True. Any exception raised during evaluation of key
-equivalence or element equality is propagated.
+In addition to the semantics described in A.17.4, Clear does not affect the
+capacity of Container.
-The function Length returns the number of key/element pairs in Map.
+AARM Note:
+procedure Move (Target : in out Map;
+ Source : in out Map);
-The function Is_Empty is equivalent to Length (Container) = 0.
+The intended implementation is that the internal hash table of Target is first
+deallocated; then the internal hash table is removed from Source and moved to
+Target.
+End AARM Note.
-Clear removes all the elements from Map. The capacity of Map is not affected.
-Any exception raised during deallocation of storage is propagated.
+procedure Insert (Container : in out Map;
+ Key : in Key_Type;
+ New_Item : in Element_Type;
+ Position : out Cursor;
+ Inserted : out Boolean);
+In addition to the semantics described in A.17.4, if Length (Container) equals
+Capacity (Container), then Insert first calls Reserve_Capacity to increase the
+capacity of Container to some larger value.
-function Element (Position : Cursor) return Element_Type;
+AARM Notes:
+Insert should only compare keys that hash to the same bucket in the hash table.
-If Position equals No_Element, then Constraint_Error is propagated.
-Otherwise, this operation returns the element designated by Position.
+We specify when Reserve_Capacity is called to bound the overhead of capacity
+expansion operations (which are potentially expensive). Moreover, expansion can
+be predicted by comparing Capacity(Map) to Length(Map). Since we don't specify
+by how much the hash table is expanded, this only can be used to predict the
+next expansion, not later ones.
+End AARM Notes.
-procedure Query_Element
- (Position : in Cursor;
- Process : not null access procedure (Key : in Key_Type;
- Element : in Element_Type));
+AARM Notes:
+procedure Delete (Container : in out Map;
+ Key : in Key_Type);
-If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
-Query_Element invokes Process.all with the key and element from the node
-designated by Position as the arguments.
+Delete should only compare keys that hash to the same bucket in the hash
+table. The node containing the element may be deallocated now,
+or it may be saved and reused later.
+End AARM Notes.
-procedure Update_Element
- (Position : in Cursor;
- Process : not null access procedure (Key : in Key_Type;
- Element : in out Element_Type));
+AARM Notes:
+procedure Exclude (Container : in out Map;
+ Key : in Key_Type);
+
+Exclude should only compare keys that hash to the same bucket in the hash
+table. Exclude should work on an empty map; nothing happens in that case.
+End AARM Notes.
+
+AARM Note:
+function Find (Container : Map;
+ Key : Key_Type) return Cursor;
+
+Find should only compare keys that hash to the same bucket in the hash table.
+End AARM Notes.
+
+AARM Note:
+function First (Container : Map) return Cursor;
+
+In a typical implementation, this will be the first node in the lowest numbered
+hash bucket that contains a node.
+End AARM Notes.
+
+AARM Note:
+function Next (Position : Cursor) return Cursor;
+
+In a typical implementation, this will return the next node in a bucket; if
+Position is the last node in a bucket, this will return the first node in the
+next non-empty bucket.
+
+A typical implementation will need to a keep a pointer at the map container
+in the cursor in order to implement this function.
+End AARM Note.
+
+function Equivalent_Keys (Left, Right : Cursor)
+ return Boolean;
+
+Equivalent to Equivalent_Keys (Key (Left), Key (Right)).
+
+function Equivalent_Keys (Left : Cursor;
+ Right : Key_Type) return Boolean;
+
+Equivalent to Equivalent_Keys (Key (Left), Right).
+
+function Equivalent_Keys (Left : Key_Type;
+ Right : Cursor) return Boolean;
+
+Equivalent to Equivalent_Keys (Left, Key (Right)).
+
+procedure Iterate
+ (Container : in Map;
+ Process : not null access procedure (Position : in Cursor));
+
+In addition to the semantics described in A.17.4, Program_Error is propagated
+if Process.all calls Reserve_Capacity.
+
+AARM Note:
+See Iterate for vectors for a suggested implementation of the check.
+
+We have to include Reserve_Capacity here, as rehashing probably will change
+the order that elements are stored in the map.
+End AARM Notes.
+
+function Capacity (Container : Map) return Count_Type;
+
+Returns the capacity of Container.
+
+procedure Reserve_Capacity (Container : in out Map;
+ Capacity : in Count_Type);
+
+Reserve_Capacity allocates a new hash table such that the length of the
+resulting map can become at least the value Capacity without requiring an
+additional call to Reserve_Capacity, and is large enough to hold the current
+length of Map. Reserve_Capacity then rehashes the nodes in Container onto the
+new hash table. It replaces the old hash table with the new hash table, and
+then deallocates the old hash table. Any exception raised during allocation is
+propagated and Container is not modified.
+
+AARM Notes: This routine is used to preallocate the internal hash table to the
+specified capacity such that future Inserts do not require expansion of the
+hash table. Therefore, the implementation should allocate the needed memory to
+make that true at this point, even though the visible semantics could be
+preserved by waiting until enough elements are inserted.
+
+While Reserve_Capacity can be used to reduce the capacity of a map, we do not
+specify whether an implementation actually supports reduction of the capacity.
+Since the actual capacity can be anything greater than or equal to Count, an
+implementation never has to reduce the capacity.
+End AARM Notes
+
+Implementation Advice
+
+If *N* is the length of a map, the average time complexity of the subprograms
+Element, Insert, Include, Replace, Delete, Exclude and Find that take a key
+parameter should be O(log N). The average time complexity of the subprograms
+that take a cursor parameter should be O(1). The average time complexity of
+Reserve_Capacity should be O(N).
+
+AARM Note
+We do not mean to overly constrain implementation strategies 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 for which Find is O(N), that program could be unusable when
+the maps are large. We allow O(log N) access because the proportionality
+constant and caching effects are likely to be larger than the log factor, and
+we don't want to discourage innovative implementations.
+
+
+A.17.6 The Package Containers.Ordered_Maps
+
+Static Semantics
+
+The package Containers.Ordered_Maps has the following declaration:
+
+generic
+
+ type Key_Type is private;
+
+ type Element_Type is private;
+
+ with function "<" (Left, Right : Key_Type) return Boolean is <>;
+
+ with function "=" (Left, Right : Element_Type) return Boolean is <>;
+
+package Ada.Containers.Ordered_Maps is
+ pragma Preelaborate (Ordered_Maps);
+
+ type Map is tagged private;
+
+ type Cursor is private;
+
+ Empty_Map : constant Map;
+
+ No_Element : constant Cursor;
+
+ function "=" (Left, Right : Map) return Boolean;
+
+ function Length (Container : Map) return Count_Type;
+
+ function Is_Empty (Container : Map) return Boolean;
+
+ procedure Clear (Container : in out Map);
+
+ function Key (Position : Cursor) return Key_Type;
+
+ function Element (Position : Cursor) return Element_Type;
+
+ procedure Query_Element
+ (Position : in Cursor;
+ Process : not null access procedure (Key : in Key_Type;
+ Element : in Element_Type));
+
+ procedure Update_Element
+ (Position : in Cursor;
+ Process : not null access procedure (Key : in Key_Type;
+ Element : in out Element_Type));
+
+ procedure Replace_Element (Position : in Cursor;
+ By : in Element_Type);
+
+ procedure Move (Target : in out Map;
+ Source : in out Map);
+
+ procedure Insert (Container : in out Map;
+ Key : in Key_Type;
+ New_Item : in Element_Type;
+ Position : out Cursor;
+ Inserted : out Boolean);
+
+ procedure Insert (Container : in out Map;
+ Key : in Key_Type;
+ Position : out Cursor;
+ Inserted : out Boolean);
+
+ procedure Insert (Container : in out Map;
+ Key : in Key_Type;
+ New_Item : in Element_Type);
+
+ procedure Include (Container : in out Map;
+ Key : in Key_Type;
+ New_Item : in Element_Type);
+
+ procedure Replace (Container : in out Map;
+ Key : in Key_Type;
+ New_Item : in Element_Type);
+
+ procedure Delete (Container : in out Map;
+ Key : in Key_Type);
+
+ procedure Delete (Container : in out Map;
+ Position : in out Cursor);
+
+ procedure Delete_First (Container : in out Map);
+
+ procedure Delete_Last (Container : in out Map);
+
+ procedure Exclude (Container : in out Map;
+ Key : in Key_Type);
+
+ function Contains (Container : Map;
+ Key : Key_Type) return Boolean;
+
+ function Find (Container : Map;
+ Key : Key_Type) return Cursor;
+
+ function Element (Container : Map;
+ Key : Key_Type) return Element_Type;
+
+ function Floor (Container : Map;
+ Key : Key_Type) return Cursor;
+
+ function Ceiling (Container : Map;
+ Key : Key_Type) return Cursor;
+
+ function First (Container : Map) return Cursor;
+
+ function First_Key (Container : Map) return Key_Type;
+
+ function First_Element (Container : Map) return Element_Type;
+
+ function Last (Container : Map) return Cursor;
+
+ function Last_Key (Container : Map) return Key_Type;
+
+ function Last_Element (Container : Map) return Element_Type;
+
+ function Next (Position : Cursor) return Cursor;
+
+ procedure Next (Position : in out Cursor);
+
+ function Previous (Position : Cursor) return Cursor;
+
+ procedure Previous (Position : in out Cursor);
+
+ function Has_Element (Position : Cursor) return Boolean;
+
+ function "<" (Left, Right : Cursor) return Boolean;
+
+ function ">" (Left, Right : Cursor) return Boolean;
+
+ function "<" (Left : Cursor; Right : Key_Type) return Boolean;
+
+ function ">" (Left : Cursor; Right : Key_Type) return Boolean;
+
+ function "<" (Left : Key_Type; Right : Cursor) return Boolean;
+
+ function ">" (Left : Key_Type; Right : Cursor) return Boolean;
+
+ procedure Iterate
+ (Container : in Map;
+ Process : not null access procedure (Position : in Cursor));
+
+ procedure Reverse_Iterate
+ (Container : in Map;
+ Process : not null access procedure (Position : in Cursor));
+
+private
+
+ ... -- not specified by the language
+
+end Ada.Containers.Ordered_Maps;
+
+Two keys K1 and K2 are *equivalent* if both K1 < K2 and K2 < K1 return False,
+using the generic formal less-than operator for keys.
+
+Functions "<" and "=" on Key_Type values are expected to return the same result
+value each time they are called with a particular pair of key values. If A = B
+returns True, then B = A is expected to also return True. If A < B returns
+True, then B < A is expected to return False. For any two equivalent elements,
+"=" is expected to return True. If "<" or "=" behaves in some other manner, the
+behavior of this package is unspecified. Which subprograms of this package call
+"<" and "=", and how many times these functions are called, is unspecified.
+
+AARM Notes
+The implementation is not required to protect against "<" or "=" raising an
+exception, or returning random results, or any other "bad" behavior. It's not
+practical to do so, and a broken "<" or "=" function makes the container
+unusable.
+
+The implementation can call "<" and "=" whenever it is needed; we don't want to
+specify how often that happens. The result must remain the same (these are
+logically pure functions), or the behavior is unspecified.
+End AARM Notes
+
+If the value of a key stored in a map is changed other than by an operation in
+this package such that at least one of "<" or "=" give different results, the
+behavior of this package is unspecified.
+
+AARM Notes
+The implementation is not required to protect against changes to key values
+other than via the operations declared in the Ordered_Maps package.
+
+To see how this could happen, imagine an instantiation of Ordered_Maps package
+where the key type is an access-to-variable type and "<" returns a value
+derived from comparing the components of the designated objects. Then, any
+operation that has a key value (even if the key value is constant) could modify
+those components and change the result of "<":
+ Key (Map).Some_Component := New_Value;
+
+This is really a design error on the part of the user of the map; it shouldn't
+be possible to modify keys stored in a map such that "<" changes. But we
+can't prevent this error anymore than we can prevent someone passing as "<"
+a routine that produces random answers.
+End AARM Notes
+
+The first node of a nonempty map is the one whose key is less than the key of
+all the other nodes in the map. The last node of a nonempty map is the one
+whose key is greater than the key of all the other elements in the map. The
+successor of a node is the node with the smallest key that is larger than the
+key of the given node. The predecessor of a node is the node with the largest
+key that is smaller than the key of the given node. All comparisons are done
+using the generic formal less-than operator for keys.
+
+procedure Delete_First (Container : in out Map);
+
+If Container is empty, Delete_First has no effect. Otherwise the node
+designated by First (Container) is removed from Container.
+
+procedure Delete_Last (Container : in out Map);
+
+If Container is empty, Delete_Last has no effect. Otherwise the node designated
+by Last (Container) is removed from Container.
+function Floor (Container : Map;
+ Key : Key_Type) return Cursor;
+
+Floor searches for the last node whose key is not greater than Key. If such a
+node is found, a cursor that designates it is returned. Otherwise No_Element is
+returned.
+
+function Ceiling (Container : Map;
+ Key : Key_Type) return Cursor;
+
+Ceiling searches for the first node whose key is not less than Key, using the
+generic formal less-than operator for keys. If such a node is found, a cursor
+that designates it is returned. Otherwise No_Element is returned.
+
+function First_Key (Container : Map) return Key_Type;
+
+Equivalent to Key (First (Container)).
+
+function First_Element (Container : Map) return Element_Type;
+
+Equivalent to Element (First (Container)).
+
+function Last (Container : Map) return Cursor;
+
+Returns a cursor that designates the last node in Container. If Container is
+empty, returns No_Element.
+
+function Last_Key (Container : Map) return Key_Type;
+
+Equivalent to Key (Last (Container)).
+
+function Last_Element (Container : Map) return Element_Type;
+
+Equivalent to Element (Last (Container)).
+
+function Previous (Position : Cursor) return Cursor;
+
+If Position equals No_Element, then Previous returns No_Element. Otherwise
+Previous returns the a cursor designating the node that precedes the one
+designated by Position. If Position designates the first element, then Previous
+returns No_Element.
+
+procedure Previous (Position : in out Cursor);
+
+Equivalent to Position := Previous (Position).
+
+function "<" (Left, Right : Cursor) return Boolean;
+
+Equivalent to Key (Left) < Key (Right).
+
+function ">" (Left, Right : Cursor) return Boolean;
+
+Equivalent to Key (Right) < Key (Left).
+
+function "<" (Left : Cursor; Right : Key_Type) return Boolean;
+
+Equivalent to Key (Left) < Right.
+
+function ">" (Left : Cursor; Right : Key_Type) return Boolean;
+
+Equivalent to Right < Key (Left).
+
+function "<" (Left : Key_Type; Right : Cursor) return Boolean;
+
+Equivalent to Left < Key (Right).
+
+function ">" (Left : Key_Type; Right : Cursor) return Boolean;
+
+Equivalent to Key (Right) < Left.
+
+procedure Reverse_Iterate
+ (Container : in Map;
+ Process : not null access procedure (Position : in Cursor));
+
+Iterates over the nodes in Container as per Iterate, with the difference that
+the nodes are traversed in predecessor order, starting with the last node.
+
+Implementation Advice
+
+If *N* is the length of a map, then the worst-case time complexity of the
+Element, Insert, Include, Replace, Delete, Exclude and Find operations that take
+a key parameter should be O((log N)**2) or better. The worst-case time
+complexity of the subprograms that take a cursor parameter should be O(1).
+
+AARM Note
+A balanced (red-black) tree for keys has O(log N) worst-case performance. Note
+that a O(N) worst-case implementation (like a list) would be wrong. We do not
+mean to overly constrain implementation strategies here. However, it is
+important for portability that the performance of large containers has roughly
+the same factors on different implementations. If a program is moved to an
+implementation that takes O(N) to find elements, that program could be unusable
+when the maps are large. We allow the extra log N factors because the
+proportionality constant and caching effects are likely to be larger than the
+log factor, and we don't want to discourage innovative implementations.
+
+
+A.17.7 Sets
+
+The language-defined packages Containers.Hashed_Sets and
+Containers.Ordered_Sets provide private types Set and Cursor, and a set of
+operations for each type. A set container allows elements of an arbitrary type
+to be stored without duplication. A hashed set uses a hash function to organize
+elements, while an ordered set orders its element per a specified relation.
+
+This section describes the declarations that are common to both kinds of sets.
+See A.17.8 for a description of the semantics specific to
+Containers.Hashed_Sets and A.17.9 for a description of the semantics specific
+to Containers.Ordered_Sets.
+
+The type Set is used to represent sets. The type Set needs finalization (see
+7.6).
+
+A set contains elements. Set cursors designate elements. There exists an
+equivalence relation on elements, whose definition is different for hashed sets
+and ordered sets. A set never contains two or more equivalent elements. The
+*length* of a set is the number of elements it contains.
+
+Each nonempty set has two particular elements called the *first element* and
+the *last element* (which may be the same). Each element except for the last
+element has a *successor element*. If there are no other intervening
+operations, starting with the first element and repeatedly going to the
+successor element will visit each element in the map exactly once until the
+last element is reached. The exact definition of these terms is different for
+hashed sets and ordered sets.
+
+Empty_Set represents the empty Set object. It has a length of 0. If an object
+of type Set is not otherwise initialized, it is initialized to the same
+value as Empty_Set.
+
+No_Element represents a cursor that designates no element. If an object of type
+Cursor is not otherwise initialized, it is initialized to the same
+value as No_Element.
+
+function "=" (Left, Right : Set) return Boolean;
+
+If Left and Right denote the same set object, then the function returns True.
+If Left and Right have different lengths, then the function returns False.
+Otherwise, for each element E in Left, the function returns False if an element
+equivalent to E is not present in Right. If the function has not returned a
+result after checking all of the elements, it return True. Any exception raised
+during evaluation of element equivalence is propagated.
+
+function Length (Container : Set) return Count_Type;
+
+Returns the number of elements in Container.
+
+function Is_Empty (Container : Set) return Boolean;
+
+Equivalent to Length (Container) = 0.
+
+procedure Clear (Container : in out Set);
+
+Removes all the elements from Container. Any exception raised during
+deallocation of storage is propagated.
+
+function Element (Position : Cursor) return Element_Type;
+
If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
-Update_Element invokes Process.all with the key and element from the node
-designated by Position as the arguments.
+Element returns the element designated by Position.
-If Element_Type is unconstrained and definite, then the Element parameter
-of Process.all shall be unconstrained.
+procedure Query_Element
+ (Position : in Cursor;
+ Process : not null access procedure (Element : in Element_Type));
-AARM Note: This means that the elements cannot be directly allocated from the
-heap (nor aliased unless AI-363 is included in the Amendment); it must be
-possible to change the discriminants of the element in place.
+If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
+Query_Element calls Process.all with the element designated by Position as the
+argument.
-procedure Replace_Element (Position : in Cursor;
- By : in Element_Type);
+procedure Replace_Element (Container : in Set;
+ Position : in Cursor;
+ By : in Element_Type);
If Position equals No_Element, then Constraint_Error is propagated.
-Otherwise this operation assigns By to the element of the node designated by
-Position.
-
+If Position does not designate an element in Container, then Program_Error
+is propagated. Otherwise, the element designated by Position is tested for
+equivalence to By; if equivalent Replace assigns By to the element designated
+by Position. Otherwise, the element designated by Position is removed from the
+container, then By is inserted into the container. If the insertion fails,
+Program_Error is propagated.
-procedure Move (Target : in out Map;
- Source : in out Map);
+procedure Move (Target : in out Set;
+ Source : in out Set);
-If Target denotes the same object as Source, then this operation has no effect.
-If the length of Target is greater than 0, then Move raises Constraint_Error.
-Otherwise, the internal hash table of Target is deallocated; then the internal
-hash table is removed from Source and moved to Target. Source has capacity 0
-after a successful call to Move.
+Move first clears Target. Then each element from Source is removed from Source
+and inserted into Target. The length of Source is 0 after a successful call to
+Move.
-procedure Insert (Container : in out Map;
- Key : in Key_Type;
+procedure Insert (Container : in out Set;
New_Item : in Element_Type;
Position : out Cursor;
Inserted : out Boolean);
-
-If Length (Container) equals Capacity (Container), then Insert calls
-Reserve_Capacity to increase the capacity of Container to some larger value.
-Insert then uses Hash and Equivalent_Keys to check if Key is already present in
-Container. If a key matches, Inserted returns False and Position designates the
-element with the matching key. Otherwise, Insert allocates a new node,
-initializes it to Key and New_Item, and adds it to Container. Inserted returns
-True and Position designates the newly-inserted node. Any exception raised
-during allocation is propagated and Container is not modified.
-
-AARM Notes:
-Insert should only compare keys that hash to the same bucket in the hash table.
-We specify when Reserve_Capacity is called to bound the overhead of capacity
-expansion operations (which are potentially expensive). Moreover, expansion can
-be predicted by comparing Capacity(Map) to Length(Map). Since we don't specify
-by how much the hash table is expanded, this only can be used to predict the
-next expansion, not later ones.
-End AARM Notes.
+Insert checks if an element equivalent to New_Item is already present in
+Container. If a match is found, Inserted is set to False and Position
+designates the matching element. Otherwise, Insert adds New_Item to Container;
+Inserted is set to True and Position designates the newly-inserted element. Any
+exception raised during allocation is propagated and Container is not modified.
-procedure Insert (Container : in out Map;
- Key : in Key_Type;
+procedure Insert (Container : in out Set;
New_Item : in Element_Type);
-Insert inserts Key and New_Item as per the five parameter Insert, with the
-difference that if Key is already in the map, then Constraint_Error is
-propagated.
+Insert inserts New_Item into Container as per the four-parameter Insert, with
+the difference that if an element equivalent to New_Item is already in the set,
+then Constraint_Error is propagated.
AARM Note: This is equivalent to:
declare
Inserted : Boolean; C : Cursor;
begin
- Insert (Container, Key, New_Item, C, Inserted);
+ Insert (Container, New_Item, C, Inserted);
if not Inserted then
raise Constraint_Error;
end if;
end;
-but doesn't require the hastle of out parameters.
+but doesn't require the hassle of out parameters.
-procedure Replace (Container : in out Map;
- Key : in Key_Type;
+procedure Include (Container : in out Set;
New_Item : in Element_Type);
-If Length (Container) equals 0, then Contraint_Error is propagated. Otherwise, it
-uses Hash and Equivalent_Keys to check if Key is present in Container. If Key
-is present in Container, assigns Key and New_Item to the
-node associated with Key; otherwise, it raises Constraint_Error.
-
-AARM Note: We update the key as well as the element, as the key might include
-additional information that does not participate in equivalence. If only the
-element needs to be updated, use
-Replace_Element (Find (Container, Key), New_Element).
+Include inserts New_Item into Container as per the four-parameter Insert, with
+the difference that if an element equivalent to New_Item is already in the set,
+then it is replaced. Any exception raised during assignment is propagated.
-procedure Include (Container : in out Map;
- Key : in Key_Type;
+procedure Replace (Container : in out Set;
New_Item : in Element_Type);
-Insert inserts Key and New_Item as per Insert, with the difference
-that if Key is already in the map, then this operation assigns Key and New_Item
-to the node associated with Key. Any exception raised during assignment is
-propagated.
+Replace checks if an element equivalent to New_Item is already in the set. If a
+match is found, that element is replaced with New_Item; otherwise,
+Constraint_Error is propagated.
-AARM Note: This is equivalent to:
- declare
- C : Cursor := Find (Container, Key);
- begin
- if C = No_Element then
- Insert (Container, Key, New_Item);
- else
- Replace (Container, Key, New_Item);
- end if;
- end;
-but this avoids doing the search twice.
+procedure Delete (Container : in out Set;
+ Item : in Element_Type);
+Delete checks if an element equivalent to Item is present in Container. If a
+match is found, Delete removes the element from the set; otherwise,
+Constraint_Error is propagated.
-procedure Insert (Container : in out Map;
- Key : in Key_Type;
- Position : out Cursor;
- Inserted : out Boolean);
+procedure Delete (Container : in out Set;
+ Position : in out Cursor);
-Inserts Key into Container as per Insert (Container, Key, New_Item,
-Position, Inserted), with the difference that an object initialized with any
-implicit initial values for any part (as for an object_declaration with no
-initialization expression - see 3.3.1) is inserted.
+If Position equals No_Element, Delete has no effect. If Position does not
+designate an element in Container, then Program_Error is propagated. Otherwise,
+Delete removes the node designated by Position from the set. Position is set to
+No_Element on return.
-procedure Delete (Container : in out Map;
- Key : in Key_Type);
+AARM Note: The check on Position checks that the cursor does not belong to some
+other set. This check implies that a reference to the set is included in the
+cursor value. This wording is not meant to require detection of dangling
+cursors; such cursors are defined to be invalid, which means that execution is
+erroneous, and any result is allowed (including not raising an exception).
-It uses Hash and Equivalent_Keys to check if Key is present in Container.
-If Key matches the key of a node, Delete removes the node from the map;
-otherwise, Delete raises Constraint_Error.
+procedure Exclude (Container : in out Set;
+ Item : in Element_Type);
-AARM Notes:
-Delete should only compare keys that hash to the same bucket in the hash
-table. The node containing the element may be deallocated now,
-or it may be saved and reused later.
+Exclude checks if an element equivalent to Item is present in Container. If a
+match is found, Exclude removes the element from the set.
-procedure Exclude (Container : in out Map;
- Key : in Key_Type);
+function Contains (Container : Set;
+ Item : Element_Type) return Boolean;
-It uses Hash and Equivalent_Keys to check if Key is present in Container. If Key
-matches the key of a node, Exclude removes the node from the map and then
-deallocates the node.
+Equivalent to Find (Container, Item) /= No_Element.
-AARM Notes:
-Exclude should only compare keys that hash to the same bucket in the hash
-table. Exclude should work on an empty map; nothing happens in that case.
+function Find (Container : Set;
+ Item : Element_Type) return Cursor;
-procedure Delete (Container : in out Map;
- Position : in out Cursor);
+If Length (Container) equals 0, then Find returns No_Element. Otherwise, Find
+checks if an element equivalent to Item is present in Container. If a match is
+found, a cursor designating the matching element is returned; otherwise,
+No_Element is returned.
-If Position equals No_Element, this operation has no effect. If Position does
-not designate an element in Container, then Program_Error is propagated. Otherwise,
-Delete removes the node designated by Position from the map. Position is set
-to No_Element on return.
+function First (Container : Set) return Cursor;
-AARM Note: The check on Position checks that the cursor does not belong to some
-other Container. This check implies that a reference to the container is
-included in the cursor value. This wording is not meant to require detection of
-dangling cursors; such cursors are defined to be invalid, which means that
-execution is erroneous, and any result is allowed (including not raising an
-exception).
+If Length (Container) = 0, then First returns No_Element. Otherwise, First
+returns a cursor that designates the first node in Container.
-function Find (Container : Map;
- Key : Key_Type) return Cursor;
+function Next (Position : Cursor) return Cursor;
-If Length (Container) equals 0, then this function returns
-No_Element. Otherwise, it uses Hash and Equivalent_Keys to check if Key is
-present in Container. If Key is present in Container, it
-returns a cursor designating the node with the matching key; otherwise, it
-returns No_Element.
+Returns a cursor that designates the successor of the element designated by
+Position. If Position designates the last element, then No_Element is returned.
+If Position equals No_Element, then No_Element is returned.
+
+procedure Next (Position : in out Cursor);
+
+Equivalent to Position := Next (Position).
+
+function Has_Element (Position : Cursor) return Boolean;
+
+Returns True if Position designates an element, and returns False otherwise.
+
+AARM Note: To Be Honest: This function may not detect cursors that designate
+deleted elements; such cursors are invalid (see below).
+
+procedure Iterate
+ (Container : in Set;
+ Process : not null access procedure (Position : in Cursor));
+
+Iterate calls Process.all with a cursor that designates each element in
+Container, starting with the first node and moving the cursor according to the
+successor relation. Any exception raised by Process.all is propagated.
+Program_Error is propagated if:
+ * Process.all attempts to insert or delete elements from Container; or
+ * Process.all finalizes Container; or
+ * Process.all calls Move with Container as a parameter.
AARM Note:
-Find should only compare keys that hash to the same bucket in the hash table.
+This check takes place when the operations that insert or delete elements, etc.
+are called.
-The function Contains is equivalent to Find (Container, Key) /= No_Element.
+See Iterate for vectors for a suggested implementation of the check.
+End AARM Notes.
-The function Element is equivalent to Element (Find (Container, Key)).
+procedure Union (Target : in out Set;
+ Source : in Set);
-The function Capacity returns the capacity of Container.
+Union inserts into Target the elements of Source that are not equivalent to
+some element already in Target.
-procedure Reserve_Capacity (Container : in out Map;
- Capacity : in Count_Type);
+AARM Note: If the objects are the same, the result is the same as the
+original object. The implementation needs to take care so that aliasing effects
+do not make the result trash; Union (S, S); must work.
-Reserve_Capacity allocates a new hash table such that the length of the
-resulting map can become at least the value Capacity without requiring an
-additional Reserve_Capacity operation and is large enough to hold the current
-length of Map. If the allocation fails, the exception is
-propagated and Container is not modified. It then rehashes the nodes in
-Container onto the new hash table. It replaces the old hash table with the new
-hash table, and then deallocates the old hash table.
+function Union (Left, Right : Set) return Set;
-AARM Notes: This routine is used to preallocate the internal hash table to the
-specified capacity such that future Inserts do not require expansion of the
-hash table. Therefore, the implementation should allocate the needed memory to
-make that true at this point, even though the visible semantics could be
-preserved by waiting until enough elements are inserted.
+Returns a set comprising all of the elements of Left, and the elements of Right
+that are not equivalent to some element of Left.
-While Reserve_Capacity can be used to reduce the capacity of a map, we do not
-specify whether an implementation actually supports reduction of the capacity.
-Since the actual capacity can be anything greater than or equal to Count, an
-implementation never has to reduce the capacity.
-End AARM Notes
+procedure Intersection (Target : in out Set;
+ Source : in Set);
-function First (Container : Map) return Cursor;
+Union deletes from Target the elements of Target that are not equivalent to
+some element of Source.
-If Length (Container) = 0, then First returns No_Element. Otherwise,
-First returns a cursor that designates the first hashed node in Container.
+AARM Note: If the objects are the same, the result is the same as the
+original object. The implementation needs to take care so that aliasing effects
+do not make the result trash; Intersection (S, S); must work.
-AARM Note:
-In a typical implementation, this will be the first node in the lowest numbered
-hash bucket that contains a node.
+function Intersection (Left, Right : Set) return Set;
-function Next (Position : Cursor) return Cursor;
+Returns a set comprising all the elements of Left that are equivalent to
+the some element of Right.
-Returns a cursor that designates the node that immediately follows
-Position. If there are no more nodes in the map identified by Position, then
-No_Element is returned. If Position equals No_Element, then No_Element
-is returned.
+procedure Difference (Target : in out Set;
+ Source : in Set);
-If there are no other intervening operations, calling Next in a loop
-starting with First (Container) shall return a cursor designating each
-node in the Container (other than First) exactly once, then return
-No_Element.
+If Target denotes the same object as Source, then Difference clears Target.
+Otherwise, it deletes from Target the elements that are equivalent to some
+element of Source.
-AARM Notes
-In a typical implementation, this will return the next node in a bucket; if
-Position is the last node in a bucket, this will return the first node in the
-next non-empty bucket.
+function Difference (Left, Right : Set) return Set;
-A typical implementation will need to a keep a pointer at the map container
-in the cursor in order to implement this function.
+Returns a set comprising the elements of Left that are not equivalent to some
+element of Right.
-The procedure Next is equivalent to Position := Next (Position).
+procedure Symmetric_Difference (Target : in out Set;
+ Source : in Set);
-function Has_Element (Position : Cursor) return Boolean;
+If Target denotes the same object as Source, then Symmetric_Difference clears
+Target. Otherwise, it deletes from Target the elements that are equivalent to
+some element of Source, and inserts into Target the elements of Source that are
+not equivalent to some element of Target.
-Returns True if Position designates an element, and returns False otherwise.
+function Symmetric_Difference (Left, Right : Set) return Set;
-AARM Note: To Be Honest: This function may not detect cursors that
-designate deleted elements; such cursors are invalid (see below) and any
-use of them (including in this routine) is erroneous.
+Returns a set comprising the elements of Left that are not equivalent to some
+element of Right, and the elements of Right that are not equivalent to some
+element of Left.
-function Key (Position : Cursor) return Key_Type;
+function Overlap (Left, Right : Set) return Boolean;
-If Position equals No_Element, then Constraint_Error is propagated.
-Otherwise, this operation returns the key component of the node designated
-by Position.
+If an element of Left is equivalent to some element of Right, then Overlap
+returns True. Otherwise it returns False.
+AARM Notes: This operation is commutative. If Overlap returns False, the two
+sets are disjoint.
-The function Equivalent_Keys (Left, Right : Cursor) is equivalent to
-Equivalent_Keys (Key (Left), Key (Right)).
+function Is_Subset (Subset : Set;
+ Of_Set : Set) return Boolean;
-The function Equivalent_Keys (Left : Cursor; Right : Key_Type) is
-equivalent to Equivalent_Keys (Key (Left), Right).
+If an element of Subset is not equivalent to some element of Of_Set, then
+Is_Subset returns False. Otherwise it returns True.
-The function Equivalent_Keys (Left : Key_Type; Right : Cursor) is
-equivalent to Equivalent_Keys (Left, Key (Right)).
+AARM Note: This operation is not commutative, so we use parameter names that
+make it clear in named notation which set is which.
-procedure Iterate
- (Container : in Map;
- Process : not null access procedure (Position : in Cursor));
+Both Containers.Hashed_Set and Containers.Ordered_Set declare a nested generic
+package Generic_Keys, which provides operations that allow set manipulation in
+terms of a key (typically, a portion of an element) instead of a complete
+element. The formal function Key of Generic_Keys extracts a key value from an
+element. It is expected to return the same value each time it is called with a
+particular element. The behavior of Generic_Keys is unspecified if Key behaves
+in some other manner.
+
+A key is expected to unambiguously determine one equivalence class for elements.
+The behavior of Generic_Keys is unspecified if the formal parameters of this
+package behave in some other manner.
+
+The subprograms in package Generic_Keys named Contains, Find, Element, Delete,
+and Exclude, are equivalent to the corresponding subprograms in the parent
+package, with the difference that the Key parameter is used locate an element in
+the set.
-Iterate calls Process.all with a cursor that designates each node
-in the Container. Any exception raised by Process is propagated.
-Program_Error is propagated if:
- * Process.all attempts to insert or delete elements from Container; or
- * Process.all calls Reserve_Capacity; or
- * Process.all finalizes Container; or
- * Process.all calls Move with Container as a parameter.
+procedure Replace (Container : in out Set;
+ Key : in Key_Type;
+ New_Item : in Element_Type);
-AARM Note:
-This check takes place when the operations that insert or delete elements, etc.
-are called.
+Equivalent to Replace (Container, Find (Container, Key), New_Item).
-See Iterate for vectors for a suggested implementation of the check.
+function Key (Position : Cursor) return Key_Type;
-We have to include Reserve_Capacity here, as rehashing probably will change
-the order that elements are stored in the map.
-End AARM Notes.
+Equivalent to Key (Element (Position)).
-Legality Rules
+procedure Checked_Update_Element
+ (Container : in out Set;
+ Position : in Cursor;
+ Process : not null access procedure (Element : in out Element_Type));
-An instantiation of Containers.Hashed_Maps shall be at the library level.
+If Position equals No_Element, then Constraint_Error is propagated. If Position
+does not designate an element in Container, then Program_Error is propagated.
+Otherwise, Checked_Update_Element uses Key to save the key value K of the
+element designated by Position. Checked_Update_Element then calls Process.all
+with that element as the argument. After Process.all returns,
+Checked_Update_Element checks if K determines the same equivalence class as
+that for the new element; if not, the element is removed from the set, then
+inserted back into the set. If the insertion fails, Program_Error is
+propagated.
-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 will
-be dropped if AI-344 or some other solution to nested controlled types is
-adopted.
+AARM Note: The key check insures that the invariants of the set are preserved
+by the modification. If not, we try to re-insert the element at the correct
+place. If that fails, we have no choice other than to drop the element
+completely, because saving a value to roll back to would be expensive and
+defeat the purpose of this routine (which is cheap, in-place modifications).
+
+If Element_Type is unconstrained and definite, then the Element parameter
+of Process.all shall be unconstrained.
+
+AARM Note: This means that the elements cannot be directly allocated from the
+heap (nor aliased unless AI-363 is included in the Amendment); it must be
+possible to change the discriminants of the element in place.
Erroneous Execution
A Cursor value is *invalid* if any of the following have occurred since it was
created:
- * The map that contains the element it designates has been finalized;
- * The map that contains the element it designates has been used as the
+ * The set that contains the element it designates has been finalized;
+ * The set that contains the element it designates has been used as the
Source or Target of a call to Move;
- * The element it designates has been deleted from the map.
+ * The element it designates has been deleted from the set.
-The result of "=" or Has_Element is unspecified if it is called with an invalid
-cursor parameter. Execution is erroneous if any other subprogram declared in
-Containers.Hashed_Maps is called with an invalid cursor parameter.
+The result of "=" or Has_Element is unspecified if these functions are called
+with an invalid cursor parameter. Execution is erroneous if any other
+subprogram declared in Containers.Hashed_Sets or Containers.Ordered_Sets is
+called with an invalid cursor parameter.
-Execution also is erroneous if the called Process procedure of a call to
-Query_Element or Update_Element executes an operation that causes the Position
-cursor of Query_Element or Update_Element to become invalid.
+Execution also is erroneous if the called Process.all procedure of a call to
+Query_Element or Checked_Update_Element executes an operation that causes the
+Position cursor of Query_Element or Checked_Update_Element to become invalid.
AARM Notes: The list above is intended to be exhaustive. In other cases, a
-cursor value continues to designate its original element. For instance,
-cursor values survive the insertion and deletion of other nodes.
+cursor value continues to designate its original element. For instance, cursor
+values survive the insertion and deletion of other elements.
While it is possible to check for these cases, in many cases the overhead
necessary to make the check is substantial in time or space. Implementations
are encouraged to check for as many of these cases as possible and raise
-Constraint_Error if detected.
+Program_Error if detected.
End AARM Notes.
Implementation Requirements
-
-No storage associated with a Map object shall be lost upon assignment or
-scope exit.
-
-Implementation Advice
-
-If *N* is the length of a map, the average time complexity of Element,
-Insert, and Find should be O(log N).
-
-AARM Note
-We do not mean to overly constrain implementation strategies 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 for which Find is O(N), that program could be unusable when
-the maps are large. We allow O(log N) access because the proportionality
-constant and caching effects are likely to be larger than the log factor, and
-we don't want to discourage innovative implementations.
+No storage associated with a Set object shall be lost upon assignment or scope
+exit.
-A.17.5 The Package Containers.Ordered_Sets
+A.17.8 The Package Containers.Hashed_Sets
-The language-defined package Containers.Ordered_Sets provides
-private types Set and Cursor, and a set of operations for each type. An
-ordered set container orders its elements per a specified relation.
-
-AARM Note: This is called "Ordered_Sets" so as to allow a possible
-future enhancement to include unsorted sets (which would be called
-"Sets") or hashed sets (which would be called "Hashed_Sets").
-
Static Semantics
-The package Containers.Ordered_Sets has the following declaration:
+The package Containers.Hashed_Sets has the following declaration:
generic
type Element_Type is private;
- with function "<" (Left, Right : Element_Type) return Boolean is <>;
+ with function Hash (Element : Element_Type) return Hash_Type;
- with function "=" (Left, Right : Element_Type) return Boolean is <>;
+ with function Equivalent_Elements (Left, Right : Element_Type)
+ return Boolean;
-package Ada.Containers.Ordered_Sets is
- pragma Preelaborate (Ordered_Sets);
+package Ada.Containers.Hashed_Sets is
+ pragma Preelaborate (Hashed_Sets);
type Set is tagged private;
@@ -2641,9 +3385,13 @@
function Element (Position : Cursor) return Element_Type;
procedure Query_Element
- (Position : in Cursor;
- Process : not null access procedure (Element : in Element_Type));
+ (Position : in Cursor;
+ Process : not null access procedure (Element : in Element_Type));
+ procedure Replace_Element (Container : in Set;
+ Position : in Cursor;
+ By : in Element_Type);
+
procedure Move (Target : in out Set;
Source : in out Set);
@@ -2660,24 +3408,45 @@
procedure Replace (Container : in out Set;
New_Item : in Element_Type);
+
+ procedure Delete (Container : in out Set;
+ Item : in Element_Type);
+
+ procedure Delete (Container : in out Set;
+ Position : in out Cursor);
+
+ procedure Exclude (Container : in out Set;
+ Item : in Element_Type);
+
+ function Contains (Container : Set;
+ Item : Element_Type) return Boolean;
+
+ function Find (Container : Set;
+ Item : Element_Type) return Cursor;
- procedure Delete (Container : in out Set;
- Item : in Element_Type);
+ function First (Container : Set) return Cursor;
- procedure Exclude (Container : in out Set;
- Item : in Element_Type);
+ function Next (Position : Cursor) return Cursor;
- procedure Delete (Container : in out Set;
- Position : in out Cursor);
+ procedure Next (Position : in out Cursor);
- procedure Delete_First (Container : in out Set);
+ function Has_Element (Position : Cursor) return Boolean;
- procedure Delete_Last (Container : in out Set);
+ function Equivalent_Elements (Left, Right : Cursor)
+ return Boolean;
- procedure Replace (Container : in Set;
- Position : in Cursor;
- By : in Element_Type);
+ function Equivalent_Elements (Left : Cursor;
+ Right : Element_Type)
+ return Boolean;
+
+ function Equivalent_Elements (Left : Element_Type;
+ Right : Cursor)
+ return Boolean;
+ procedure Iterate
+ (Container : in Set;
+ Process : not null access procedure (Position : in Cursor));
+
procedure Union (Target : in out Set;
Source : in Set);
@@ -2704,648 +3473,574 @@
function Symmetric_Difference (Left, Right : Set) return Set;
- function "xor" (Left, Right : Set) return Set renames
- Symmetric_Difference;
+ function "xor" (Left, Right : Set) return Set
+ renames Symmetric_Difference;
function Overlap (Left, Right : Set) return Boolean;
function Is_Subset (Subset : Set;
Of_Set : Set) return Boolean;
- function Contains (Container : Set;
- Item : Element_Type) return Boolean;
+ function Capacity (Container : Set) return Count_Type;
- function Find (Container : Set;
- Item : Element_Type)
- return Cursor;
+ procedure Reserve_Capacity (Container : in out Set;
+ Capacity : in Count_Type);
- function Floor (Container : Set;
- Item : Element_Type)
- return Cursor;
+ generic
- function Ceiling (Container : Set;
- Item : Element_Type)
- return Cursor;
+ type Key_Type (<>) is limited private;
- function First (Container : Set) return Cursor;
+ with function Key (Element : in Element_Type) return Key_Type;
- function First_Element (Container : Set) return Element_Type;
+ with function Hash (Key : Key_Type) return Hash_Type;
- function Last (Container : Set) return Cursor;
+ with function Equivalent_Keys (Left : Key_Type; Right : Element_Type)
+ return Boolean;
- function Last_Element (Container : Set) return Element_Type;
+ package Generic_Keys is
- function Next (Position : Cursor) return Cursor;
+ function Contains (Container : Set;
+ Key : Key_Type)
+ return Boolean;
- function Previous (Position : Cursor) return Cursor;
+ function Find (Container : Set;
+ Key : Key_Type)
+ return Cursor;
- procedure Next (Position : in out Cursor);
+ function Key (Position : Cursor) return Key_Type;
- procedure Previous (Position : in out Cursor);
+ function Element (Container : Set;
+ Key : Key_Type)
+ return Element_Type;
- function Has_Element (Position : Cursor) return Boolean;
+ procedure Replace (Container : in out Set;
+ Key : in Key_Type;
+ New_Item : in Element_Type);
- function "<" (Left, Right : Cursor) return Boolean;
+ procedure Delete (Container : in out Set;
+ Key : in Key_Type);
- function ">" (Left, Right : Cursor) return Boolean;
+ procedure Exclude (Container : in out Set;
+ Key : in Key_Type);
- function "<" (Left : Cursor; Right : Element_Type)
- return Boolean;
+ procedure Checked_Update_Element
+ (Container : in out Set;
+ Position : in Cursor;
+ Process : not null access procedure (Element : in out Element_Type));
+
+ function Equivalent_Keys (Left : Cursor;
+ Right : Key_Type)
+ return Boolean;
+
+ function Equivalent_Keys (Left : Key_Type;
+ Right : Cursor)
+ return Boolean;
- function ">" (Left : Cursor; Right : Element_Type)
- return Boolean;
+ end Generic_Keys;
- function "<" (Left : Element_Type; Right : Cursor)
- return Boolean;
+private
- function ">" (Left : Element_Type; Right : Cursor)
- return Boolean;
+ ... -- not specified by the language
- procedure Iterate
- (Container : in Set;
- Process : not null access procedure (Position : in Cursor));
+end Ada.Containers.Hashed_Sets;
- procedure Reverse_Iterate
- (Container : in Set;
- Process : not null access procedure (Position : in Cursor));
+An object of type Set contains an expandable hash table, which is used to
+provide direct access to elements. The *capacity* of an object of type Set is
+the maximum number of elements that can be inserted into the hash table prior
+to it being automatically expanded.
- generic
+Two elements E1 and E2 are defined to be *equivalent* if Equivalent_Elements
+(E1, E2) returns True.
- type Key_Type (<>) is limited private;
+Function Hash is expected to return the same value each time it is called with
+a particular element value. For any two equivalent elements, Hash is expected
+to return the same value. If Hash behaves in some other manner, the behavior of
+this package is unspecified. Which subprograms of this package call Hash, and
+how many times they call it, is unspecified.
+
+Function Equivalent_Elements is expected to return the same value each time
+it is called with a particular pair of element values. For any two elements E1
+and E2, the boolean values Equivalent_Keys (E1, E2) and Equivalent_Key (E2, E1)
+are expected to be equal. If Equivalent_Elements behaves in some other manner,
+the behavior of this package is unspecified. Which subprograms of this package
+call Equivalent_Elements, and how many times they call it, is unspecified.
- with function Key (Element : Element_Type) return Key_Type;
+If the value of an element stored in a set is changed other than by an
+operation in this package such that at least one of Hash or Equivalent_Elements
+give different results, the behavior of this package is unspecified.
- with function "<" (Left : Key_Type; Right : Element_Type)
- return Boolean is <>;
+AARM Note
+See Hashed_Maps for a suggested implementation, and for justification of the
+restrictions regarding Hash and Equivalent_Elements. Note that sets only need
+to store elements, not key/element pairs.
+
+Which elements are the first element and the last element of a set, and which
+element is the successor of a given element, are unspecified, other than the
+general semantics described in A.17.7.
- with function ">" (Left : Key_Type; Right : Element_Type)
- return Boolean is <>;
+procedure Clear (Container : in out Set);
- package Generic_Keys is
+In addition to the semantics described in A.17.7, Clear does not affect the
+capacity of Container.
- function Contains (Container : Set;
- Key : Key_Type) return Boolean;
+procedure Insert (Container : in out Set;
+ New_Item : in Element_Type;
+ Position : out Cursor;
+ Inserted : out Boolean);
- function Find (Container : Set;
- Key : Key_Type)
- return Cursor;
+In addition to the semantics described in A.17.7, if Length (Container) equals
+Capacity (Container), then Insert first calls Reserve_Capacity to increase the
+capacity of Container to some larger value.
- function Floor (Container : Set;
- Item : Key_Type)
- return Cursor;
+function First (Container : Set) return Cursor;
- function Ceiling (Container : Set;
- Item : Key_Type)
- return Cursor;
+If Length (Container) = 0, then First returns No_Element. Otherwise, First
+returns a cursor that designates the first hashed element in Container.
- function Key (Position : Cursor) return Key_Type;
+function Equivalent_Elements (Left, Right : Cursor)
+ return Boolean;
- function Element (Container : Set;
- Key : Key_Type)
- return Element_Type;
+Equivalent to Equivalent_Elements (Element (Left), Element (Right)).
- procedure Replace (Container : in out Set;
- Key : in Key_Type;
- New_Item : in Element_Type);
+function Equivalent_Elements (Left : Cursor;
+ Right : Element_Type) return Boolean;
- procedure Delete (Container : in out Set;
- Key : in Key_Type);
+Equivalent to Equivalent_Elements (Element (Left), Right).
- procedure Exclude (Container : in out Set;
- Key : in Key_Type);
+function Equivalent_Elements (Left : Element_Type;
+ Right : Cursor) return Boolean;
- function "<" (Left : Cursor; Right : Key_Type)
- return Boolean;
+Equivalent to Equivalent_Elements (Left, Element (Right)).
- function ">" (Left : Cursor; Right : Key_Type)
- return Boolean;
+procedure Iterate
+ (Container : in Set;
+ Process : not null access procedure (Position : in Cursor));
- function "<" (Left : Key_Type; Right : Cursor)
- return Boolean;
+In addition to the semantics described in A.17.7, Program_Error is propagated
+if Process.all calls Reserve_Capacity.
- function ">" (Left : Key_Type; Right : Cursor)
- return Boolean;
+function Capacity (Container : Set) return Count_Type;
- procedure Checked_Update_Element
- (Container : in out Set;
- Position : in Cursor;
- Process : not null access procedure (Element : in out Element_Type));
+Returns the capacity of Container.
- end Generic_Keys;
+procedure Reserve_Capacity (Container : in out Set;
+ Capacity : in Count_Type);
-private
+Reserve_Capacity allocates a new hash table such that the length of the
+resulting set can become at least the value Capacity without requiring an
+additional call to Reserve_Capacity, and is large enough to hold the current
+length of Set. Reserve_Capacity then rehashes the nodes in Container onto the
+new hash table. It replaces the old hash table with the new hash table, and
+then deallocates the old hash table. Any exception raised during allocation is
+propagated and Container is not modified.
- ... -- not specified by the language
-end Ada.Containers.Ordered_Sets;
+For any element E, the function Generic_Keys.Hash must be such that Hash (E) =
+Generic_Keys.Hash (Key (E)). If Key or Generic_Keys.Hash behave in some other
+manner, the behavior of Generic_Keys is unspecified. Which subprograms of
+Generic_Keys call Generic_Keys.Hash, and how many times they call it, is
+unspecified.
-The type Set needs finalization (see 7.6).
+For any two elements E1 and E2, the boolean values Equivalent_Element (E1, E2),
+Equivalent_Keys (Key (E1), E2) and Equivalent_Keys (Key (E2), E1) are all
+expected to be equal. If Key or Equivalent behave in some other manner, the
+behavior of Generic_Keys is unspecified. Which subprograms of Generic_Keys call
+Equivalent, and how many times they call it, is unspecified.
-Functions "<" and "=" on Element_Type values are expected to return the same
-result value each time they are called with a particular pair of element
-values. If A = B returns True, then B = A should also return True. If A < B
-returns True, then B < A should return False. If "<" or "=" behaves in some
-other manner, the behavior of this package is unspecified. Which subprograms of
-this package call "<" and "=", and how many times the functions are called, is
-unspecified.
+function Equivalent_Keys (Left : Cursor;
+ Right : Key_Type) return Boolean;
-Two elements E1 and E2 are *equivalent* if not (E1 < E2) and not (E2 < E1) is
-true for the elements, using the generic formal less-than operator for elements.
+Equivalent to Equivalent_Keys (Key (Left), Right).
-AARM Notes
-The implementation is not required to protect against "<" or "=" raising an
-exception, or returning random results, or any other "bad" behavior. It's not
-practical to do so, and a broken "<" or "=" function makes the container
-unusable.
+function Equivalent_Keys (Left : Key_Type;
+ Right : Cursor) return Boolean;
-The implementation can call "<" and "=" whenever it is needed; we don't want to
-specify how often that happens. The result must remain the same (these are
-logically pure functions), or the behavior is unspecified.
-End AARM Notes
+Equivalent to Equivalent_Keys (Left, Key (Right)).
-If the value of an element stored in a set is changed other than by an
-operation in this package such that at least one of "<" or "=" give different
-results, the behavior of this package is unspecified.
-AARM Notes
-The implementation is not required to protect against changes to element values
-other than via the operations declared in the Ordered_Sets package.
+Implementation Advice
-To see how this could happen, imagine an instantiation of Ordered_Sets package
-where the element type is an access-to-variable type and "<" returns a value
-derived from comparing the components of the designated objects. Then, any
-operation that has a element value (even if the element value is constant)
-could modify those components and change the result of "<":
- Element (Set).Some_Component := New_Value;
+If *N* is the length of a set, the average time complexity of the subprograms
+Insert, Include, Replace, Delete, Exclude and Find that take an element
+parameter should be O(log N). The average time complexity of the subprograms
+that take a cursor parameter should be O(1). The average time complexity of
+Reserve_Capacity should be O(N).
-This is really a design error on the part of the user of the set; it shouldn't
-be possible to modify elements stored in a set such that "<" changes. But we
-can't prevent this error anymore than we can prevent someone passing as "<"
-a routine that produces random answers.
-End AARM Notes
+AARM Note:
+See Hashed_Maps for implementation notes regarding some of the operations of
+this package.
-Empty_Set represents the empty ordered set. If an object of type Set is
-not otherwise initialized, it will be initialized to the same value as
-Empty_Set.
+A.17.9 The Package Containers.Ordered_Sets
-No_Element represents a cursor that designates no element. If an object of type
-Cursor is not otherwise initialized, it will be initialized to the same
-value as No_Element.
+Static Semantics
-function "=" (Left, Right : Set) return Boolean;
+The package Containers.Ordered_Sets has the following declaration:
-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.
+generic
-The function Length returns the number of elements in Container.
+ type Element_Type is private;
-The function Is_Empty is equivalent to Length (Container) = 0.
+ with function "<" (Left, Right : Element_Type) return Boolean is <>;
-Clear removes all the elements in Set, and sets the length to 0.
+ with function "=" (Left, Right : Element_Type) return Boolean is <>;
-function Element (Position : Cursor) return Element_Type;
+package Ada.Containers.Ordered_Sets is
+ pragma Preelaborate (Ordered_Sets);
-If Position equals No_Element, then Constraint_Error is propagated.
-Otherwise, it returns the element designated by Position.
+ type Set is tagged private;
-procedure Query_Element
- (Position : in Cursor;
- Process : not null access procedure (Element : in Element_Type));
+ type Cursor is private;
-If Position equals No_Element, then Constraint_Error is propagated. Otherwise,
-Query_Element invokes Process.all with the element on node designated by
-Position as the argument.
+ Empty_Set : constant Set;
-procedure Move (Target : in out Set;
- Source : in out Set);
+ No_Element : constant Cursor;
-If the length of Target is greater than 0, then Move raises
-Constraint_Error. Otherwise, the elements are removed from Source and
-moved to Target. The length of Source is 0 after a successful call to Move.
+ function "=" (Left, Right : Set) return Boolean;
+ function Length (Container : Set) return Count_Type;
-procedure Insert (Container : in out Set;
- New_Item : in Element_Type;
- Position : out Cursor;
- Inserted : out Boolean);
+ function Is_Empty (Container : Set) return Boolean;
-Insert compares New_Item to the elements in Container using the generic formal
-less-than operator for elements. If an element equivalent to New_Item is
-already in Container, Inserted is False and Position designates the element.
-Otherwise, it allocates a new element which is initialized to New_Item.
-Inserted returns True and Position designates the newly-inserted element. Any
-exception raised during allocation and initialization is propagated and
-Container is not modified.
+ procedure Clear (Container : in out Set);
-procedure Insert (Container : in out Set;
- New_Item : in Element_Type);
+ function Element (Position : Cursor) return Element_Type;
-Insert compares New_Item to the elements in Container using the generic formal
-less-than operator for elements. If an element equivalent to New_Item is
-already in Container, Insert raises Constraint_Error. Otherwise, it allocates a
-new element which is initialized to New_Item. Any exception raised during
-allocation and initialization is propagated and Container is not modified.
+ procedure Query_Element
+ (Position : in Cursor;
+ Process : not null access procedure (Element : in Element_Type));
-procedure Include (Container : in out Set;
- New_Item : in Element_Type);
+ procedure Replace_Element (Container : in Set;
+ Position : in Cursor;
+ By : in Element_Type);
-Include compares New_Item to the elements in Container using the generic formal
-less-than operator for elements. If an element equivalent to New_Item is
-already in Container, Include assigns New_Item to the equivalent element.
-Otherwise, it allocates a new element which is initialized to New_Item. Any
-exception raised during allocation and initialization is propagated and
-Container is not modified.
+ procedure Move (Target : in out Set;
+ Source : in out Set);
-procedure Replace (Container : in out Set;
- New_Item : in Element_Type);
+ procedure Insert (Container : in out Set;
+ New_Item : in Element_Type;
+ Position : out Cursor;
+ Inserted : out Boolean);
-Replace compares New_Item to the elements in Container using the generic formal
-less-than operator for elements. If an element equivalent to New_Item is
-already in Container, Replace assigns New_Item to the equivalent element.
-Otherwise, Constraint_Error is propagated.
+ procedure Insert (Container : in out Set;
+ New_Item : in Element_Type);
+ procedure Include (Container : in out Set;
+ New_Item : in Element_Type);
-procedure Delete (Container : in out Set;
- Item : in Element_Type);
+ procedure Replace (Container : in out Set;
+ New_Item : in Element_Type);
-Delete searches Container for an element equivalent to Item. If there is an
-element in Container equivalent to Item, the element is removed from Container.
-Otherwise, Constraint_Error is propagated.
+ procedure Delete (Container : in out Set;
+ Item : in Element_Type);
-AARM Note: The internal node containing the element may be deallocated now,
-or it may be saved and reused later.
+ procedure Exclude (Container : in out Set;
+ Item : in Element_Type);
-procedure Exclude (Container : in out Set;
- Item : in Element_Type);
+ procedure Delete (Container : in out Set;
+ Position : in out Cursor);
-Exclude searches Container for an element equivalent to Item. If there is an
-element in Container equivalent to Item, the element is removed from Container.
+ procedure Delete_First (Container : in out Set);
-procedure Delete (Container : in out Set;
- Position : in out Cursor);
+ procedure Delete_Last (Container : in out Set);
-If Position equals No_Element, this operation has no effect. If Position does
-not designate an element in Container, then Program_Error is propagated. Otherwise,
-Delete removes the element designated by Position from Container.
-Position is set to No_Element on return.
+ procedure Union (Target : in out Set;
+ Source : in Set);
-AARM Note: The check on Position checks that the cursor does not belong to some
-other Container. This check implies that a reference to the container is
-included in the cursor value. This wording is not meant to require detection of
-dangling cursors; such cursors are defined to be invalid, which means that
-execution is erroneous, and any result is allowed (including not raising an
-exception).
+ function Union (Left, Right : Set) return Set;
-procedure Delete_First (Container : in out Set);
+ function "or" (Left, Right : Set) return Set renames Union;
-If Container is empty, the operation has no effect. Otherwise the element
-designated by First (Container) is removed from Container.
+ procedure Intersection (Target : in out Set;
+ Source : in Set);
-procedure Delete_Last (Container : in out Set);
+ function Intersection (Left, Right : Set) return Set;
-If Container is empty, the operation has no effect. Otherwise the element
-designated by Last (Container) is removed from Container.
+ function "and" (Left, Right : Set) return Set renames Intersection;
-procedure Replace (Container : in Set;
- Position : in Cursor;
- By : in Element_Type);
+ procedure Difference (Target : in out Set;
+ Source : in Set);
-If Position equals No_Element, then Constraint_Error is propagated.
-If Positiond oes not designate an element in Container, then Program_Error
-is propagated. Otherwise, Replace compares By to the element
-designated by Position using the generic formal less-than operator for
-elements. If the element designated by Position is equivalent to By, Replace
-assigns By to the element designated by Position. Otherwise, the element
-designated by Position is removed from the container, then By is inserted
-into the container. If the insertion fails, Program_Error is propagated.
+ function Difference (Left, Right : Set) return Set;
-procedure Union (Target : in out Set;
- Source : in Set);
+ function "-" (Left, Right : Set) return Set renames Difference;
-The elements of Source that are not equivalent to items already in Target are
-inserted into Target.
+ procedure Symmetric_Difference (Target : in out Set;
+ Source : in Set);
-AARM Note: If the objects are the same, the result is the same as the
-original object. The implementation needs to take care so that aliasing effects
-do not make the result trash; Union (S, S); must work.
+ function Symmetric_Difference (Left, Right : Set) return Set;
-function Union (Left, Right : Set) return Set;
+ function "xor" (Left, Right : Set) return Set renames
+ Symmetric_Difference;
+
+ function Overlap (Left, Right : Set) return Boolean;
-Returns a set comprising all of the elements of Left, and the elements
-of Right that are not equivalent to elements of Left.
+ function Is_Subset (Subset : Set;
+ Of_Set : Set) return Boolean;
+ function Contains (Container : Set;
+ Item : Element_Type) return Boolean;
-procedure Intersection (Target : in out Set;
- Source : in Set);
+ function Find (Container : Set;
+ Item : Element_Type)
+ return Cursor;
-All the elements of Target that are not equivalent to the corresponding
-elements of Source are deleted from Target.
+ function Floor (Container : Set;
+ Item : Element_Type)
+ return Cursor;
-AARM Note: If the objects are the same, the result is the same as the
-original object. The implementation needs to take care so that aliasing effects
-do not make the result trash; Intersection (S, S); must work.
+ function Ceiling (Container : Set;
+ Item : Element_Type)
+ return Cursor;
+ function First (Container : Set) return Cursor;
-function Intersection (Left, Right : Set) return Set;
+ function First_Element (Container : Set) return Element_Type;
-Returns a set comprising all the elements of Left that are equivalent to
-the corresponding elements of Right.
+ function Last (Container : Set) return Cursor;
+ function Last_Element (Container : Set) return Element_Type;
-procedure Difference (Target : in out Set;
- Source : in Set);
+ function Next (Position : Cursor) return Cursor;
-If Target denotes the same object as Source, then the operation
-clears Target. Otherwise, it deletes the elements of Target that
-are equivalent to elements of Source.
+ procedure Next (Position : in out Cursor);
+ function Previous (Position : Cursor) return Cursor;
-function Difference (Left, Right : Set) return Set;
+ procedure Previous (Position : in out Cursor);
-Returns a set comprising the elements of Left that are not equivalent to
-the corresponding elements of Right.
+ function Has_Element (Position : Cursor) return Boolean;
+ function "<" (Left, Right : Cursor) return Boolean;
-procedure Symmetric_Difference (Target : in out Set;
- Source : in Set);
+ function ">" (Left, Right : Cursor) return Boolean;
-If Target denotes the same object as Source, then the operation
-clears Target. Otherwise, it deletes the elements of Target that
-are equivalent to elements of Source, and inserts the elements are
-Source that are not equivalent to the corresponding elements of
-Target.
+ function "<" (Left : Cursor; Right : Element_Type)
+ return Boolean;
+ function ">" (Left : Cursor; Right : Element_Type)
+ return Boolean;
-function Symmetric_Difference (Left, Right : Set) return Set;
+ function "<" (Left : Element_Type; Right : Cursor)
+ return Boolean;
-Returns a set comprising the elements of Left that are not equivalent to
-the corresponding elements of Right, and the elements of Right that are
-not equivalent to the corresponding elements of Left.
+ function ">" (Left : Element_Type; Right : Cursor)
+ return Boolean;
+ procedure Iterate
+ (Container : in Set;
+ Process : not null access procedure (Position : in Cursor));
-function Overlap (Left, Right : Set) return Boolean;
+ procedure Reverse_Iterate
+ (Container : in Set;
+ Process : not null access procedure (Position : in Cursor));
-If an element of Left is equivalent to some element of Right, then
-Overlap returns True. Otherwise it returns False.
+ generic
-AARM Notes: This operation is communative. If Overlap returns False, the
-two sets are disjoint.
+ type Key_Type (<>) is limited private;
-function Is_Subset (Subset : Set;
- Of_Set : Set) return Boolean;
+ with function Key (Element : Element_Type) return Key_Type;
-If an element of Subset is not equivalent to some element of
-Of_Set, the function returns False. Otherwise it returns True.
+ with function "<" (Left : Key_Type; Right : Element_Type)
+ return Boolean is <>;
-AARM Note: This operation is not communative, so we use parameter names that
-make it clear in named notation which set is which.
+ with function ">" (Left : Key_Type; Right : Element_Type)
+ return Boolean is <>;
+ package Generic_Keys is
-function Find (Container : Set;
- Item : Element_Type) return Cursor;
+ function Contains (Container : Set;
+ Key : Key_Type) return Boolean;
-The Find operation searches for the element equivalent to Item. If it finds
-an equivalent element, it returns a cursor designating the element. Otherwise
-it returns No_Element.
+ function Find (Container : Set;
+ Key : Key_Type)
+ return Cursor;
-The function Contains is equivalent to Find (Set, Item) /= No_Element.
+ function Floor (Container : Set;
+ Item : Key_Type)
+ return Cursor;
-function Floor (Container : Set;
- Item : Element_Type)
- return Cursor;
+ function Ceiling (Container : Set;
+ Item : Key_Type)
+ return Cursor;
-The Floor operation searches for the largest element not greater than Item,
-using the generic formal less-than operator for elements. If there is an
-element in Set that is not greater than Item, it returns a cursor designating
-the node containing the element. Otherwise it returns No_Element.
+ function Key (Position : Cursor) return Key_Type;
-function Ceiling (Container : Set;
- Item : Element_Type)
- return Cursor;
+ function Element (Container : Set;
+ Key : Key_Type)
+ return Element_Type;
-The Ceiling operation searches for the smallest element not less
-than Item, using the generic formal less-than operator for elements. 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 No_Element.
+ procedure Replace (Container : in out Set;
+ Key : in Key_Type;
+ New_Item : in Element_Type);
-function First (Container : Set) return Cursor;
+ procedure Delete (Container : in out Set;
+ Key : in Key_Type);
-Returns a cursor that designates the smallest element. If Container is empty,
-it returns No_Element.
+ procedure Exclude (Container : in out Set;
+ Key : in Key_Type);
-function First_Element (Container : Set) return Element_Type;
+ function "<" (Left : Cursor; Right : Key_Type)
+ return Boolean;
-If Container is empty, then Constraint_Error is propagated. Otherwise,
-it returns the element designated by First (Container).
+ function ">" (Left : Cursor; Right : Key_Type)
+ return Boolean;
-function Last (Container : Set) return Cursor;
+ function "<" (Left : Key_Type; Right : Cursor)
+ return Boolean;
-Returns a cursor that designates the greatest element. If Container is empty,
-it returns No_Element.
+ function ">" (Left : Key_Type; Right : Cursor)
+ return Boolean;
-function Last_Element (Container : Set) return Element_Type;
+ procedure Checked_Update_Element
+ (Container : in out Set;
+ Position : in Cursor;
+ Process : not null access procedure
+ (Element : in out Element_Type));
-If Container is empty, then Constraint_Error is propagated. Otherwise, it
-returns the element designated by Last (Container).
+ end Generic_Keys;
-function Next (Position : Cursor) return Cursor;
+private
-If Position equals No_Element, then No_Element is returned. Otherwise
-it returns the successor of the element designated by Position.
+ ... -- not specified by the language
-function Previous (Position : Cursor) return Cursor;
+end Ada.Containers.Ordered_Sets;
-If Position equals No_Element, then No_Element is returned. Otherwise
-it returns the predecessor of the element designated by Position.
+Two elements E1 and E2 are *equivalent* if both E1 < E2 and E2 < E1 return
+False, using the generic formal less-than operator for elements.
-The procedure Next is equivalent to Position := Next (Position).
+Functions "<" and "=" on Element_Type values are expected to return the same
+result value each time they are called with a particular pair of element values.
+If A = B returns True, then B = A is expected to also return True. If A < B
+returns True, then B < A is expected to return False. For any two equivalent
+elements, "=" is expected to return True. If "<" or "=" behaves in some other
+manner, the behavior of this package is unspecified. Which subprograms of this
+package call "<" and "=", and how many times these functions are called, is
+unspecified.
-The procedure Previous is equivalent to Position := Previous (Position).
+If the value of an element stored in a set is changed other than by an
+operation in this package such that at least one of "<" or "=" give different
+results, the behavior of this package is unspecified.
-function Has_Element (Position : Cursor) return Boolean;
+AARM Note
+See Ordered_Maps for a suggested implementation, and for justification of the
+restrictions regarding "<" and "=". Note that sets only need to store elements,
+not key/element pairs.
+
+The first element of a nonempty set is the one which is less than all the other
+elements in the set. The last element of a nonempty set is the one which is
+greater than all the other elements in the set. The successor of an element is
+the smallest element that is larger than the given element. The predecessor of
+an element is the largest element that is smaller than the given element. All
+comparisons are done using the generic formal less-than operator for elements.
-Returns True if Position designates an element, and returns False otherwise.
+procedure Delete_First (Container : in out Set);
-AARM Note: To Be Honest: This function might not detect cursors that
-designate deleted elements; such cursors are invalid (see below) and any
-use of them (including in this routine) is erroneous.
+If Container is empty, Delete_First has no effect. Otherwise the element
+designated by First (Container) is removed from Container.
-The function "<" (Left, Right : Cursor) is equivalent to Element
-(Left) < Element (Right).
+procedure Delete_Last (Container : in out Set);
-The function ">" (Left, Right : Cursor) is equivalent to Element
-(Right) < Element (Left).
+If Container is empty, Delete_Last has no effect. Otherwise the element
+designated by Last (Container) is removed from Container.
-The function "<" (Left : Cursor; Right : Element_Type) is
-equivalent to Element (Left) < Right.
+function Floor (Container : Set;
+ Item : Element_Type) return Cursor;
-The function ">" (Left : Cursor; Right : Element_Type) is
-equivalent to Right < Element (Left).
+Floor searches for the last element which is not greater than Item. If such an
+element is found, a cursor that designates it is returned. Otherwise No_Element
+is returned.
-The function "<" (Left : Element_Type; Right : Cursor) is
-equivalent to Left < Element (Right).
+function Ceiling (Container : Set;
+ Item : Element_Type) return Cursor;
-The function ">" (Left : Element_Type; Right : Cursor) is
-equivalent to Element (Right) < Left.
+Ceiling searches for the first element which is not less than Item. If such an
+element is found, a cursor that designates it is returned. Otherwise No_Element
+is returned.
-procedure Iterate
- (Container : in Set;
- Process : not null access procedure (Position : in Cursor));
+function First_Element (Container : Set) return Element_Type;
-Invokes Process.all with a cursor that designates each element in Container.
-Program_Error is propagated if:
- * Process.all attempts to insert or delete elements from Container; or
- * Process.all finalizes Container; or
- * Process.all calls Move with Container as a parameter.
+Equivalent to Element (First (Container)).
-AARM Note:
-This check takes place when the operations that insert or delete elements, etc.
-are called.
+function Last (Container : Set) return Cursor;
-See Iterate for vectors for a suggested implementation of the check.
-End AARM Notes.
+Returns a cursor that designates the last node in Container. If Container is
+empty, returns No_Element.
+function Last_Element (Container : Set) return Element_Type;
-procedure Reverse_Iterate
- (Container : in Set;
- Process : not null access procedure (Position : in Cursor));
+Equivalent to Element (Last (Container)).
-Iterates over the elements in Container as per Iterate, with the
-difference that the nodes are traversed in reverse order.
+function Previous (Position : Cursor) return Cursor;
-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 formal function Key is intended to extract a key value from an element. For
-any two elements E1 and E2, it is expected that (E1 < E2) = (Key(E1) < E2) =
-(Key(E2) > E1). If Key, "<", or ">" behaves in some other manner, the behavior
-of this package is unspecified. Which subprograms of this package call Key, "<"
-and ">", and how many times the functions are called, is unspecified.
-
-AARM Note: As for the main package, if the formal subprograms don't make sense,
-the package is not required to do anything that makes sense.
-
-
-The operations in package Generic_Keys named Contains, Find, Floor, Ceiling,
-Element, Delete, Exclude, and operators designated "<" and ">", are equivalent
-to the corresponding operations in the parent package, with the difference that
-the Key subprogram parameter is compared to elements in the container using the
-Generic_Keys generic formal relational operators.
+If Position equals No_Element, then Previous returns No_Element. Otherwise
+Previous returns a cursor designating the element that precedes the one
+designated by Position. If Position designates the first element, then Previous
+returns No_Element.
-procedure Replace (Container : in out Set;
- Key : in Key_Type;
- New_Item : in Element_Type);
+procedure Previous (Position : in out Cursor);
-Equivalent to Replace (Container, Find (Container, Key), New_Item).
+Equivalent to Position := Previous (Position).
-function Key (Position : Cursor) return Key_Type;
+function "<" (Left, Right : Cursor) return Boolean;
-If Position equals No_Element, then Constraint_Error is propagated.
-Otherwise, this operation returns the key obtained by calling the generic
-formal Key operation on the element designated by Position.
+Equivalent to Element (Left) < Element (Right).
-procedure Checked_Update_Element
- (Container : in out Set;
- Position : in Cursor;
- Process : not null access procedure (Element : in out Element_Type));
+function ">" (Left, Right : Cursor) return Boolean;
-If Position equals No_Element, then Constraint_Error is propagated.
-If Position does not designate an element in Container, then Program_Error
-is propagated. Otherwise,
-Checked_Update_Element uses Key to save the key value (KB) of the element.
-Checked_Update_Element then invokes Process.all with the element designated
-by Position as the argument. The key KB is compared to the new element value
-using the generic formal less-than and greater-than operators; if either
-returns True, the element is removed from the set, then is inserted back into
-the set. If the insertion fails, Program_Error is propagated.
-
-AARM Note: The key check insures that the invariants of the set are
-preserved by the modification. If not, we try to re-insert the element at
-the correct place. If that fails, we have no choice other than to drop
-the element completely, because saving a value to roll back to would be
-expensive and defeat the purpose of this routine (which is cheap, in-place
-modifications).
+Equivalent to Element (Right) < Element (Left).
-If Element_Type is unconstrained and definite, then the Element parameter
-of Process.all shall be unconstrained.
+function "<" (Left : Cursor; Right : Element_Type) return Boolean;
-AARM Note: This means that the elements cannot be directly allocated from the
-heap (nor aliased unless AI-363 is included in the Amendment); it must be
-possible to change the discriminants of the element in place.
+Equivalent to Element (Left) < Right.
-Legality Rules
+function ">" (Left : Cursor; Right : Element_Type) return Boolean;
-An instantiation of Containers.Ordered_Sets shall be at the library level.
+Equivalent to Right < Element (Left).
-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 will
-be dropped if AI-344 or some other solution to nested controlled types is
-adopted.
+function "<" (Left : Element_Type; Right : Cursor) return Boolean;
-Erroneous Execution
+Equivalent to Left < Element (Right).
-A Cursor value is *invalid* if any of the following have occurred since it was
-created:
- * The set that contains the element it designates has been finalized;
- * The set that contains the element it designates has been used as the
- Source or Target of a call to Move;
- * The element it designates has been deleted from the set.
+function ">" (Left : Element_Type; Right : Cursor) return Boolean;
-The result of "=" or Has_Element is unspecified if it is called with an invalid
-cursor parameter. Execution is erroneous if any other subprogram declared in
-Containers.Ordered_Sets is called with an invalid cursor parameter.
+Equivalent to Element (Right) < Left.
-Execution also is erroneous if the called Process procedure of a call to
-Query_Element or Checked_Update_Element executes an operation that causes the
-Position cursor of Query_Element or Checked_Update_Element to become invalid.
+procedure Reverse_Iterate
+ (Container : in Set;
+ Process : not null access procedure (Position : in Cursor));
-AARM Notes: The list above is intended to be exhaustive. In other cases, a
-cursor value continues to designate its original element. For instance,
-cursor values survive the insertion and deletion of other elements.
+Iterates over the elements in Container as per Iterate, with the difference
+that the elements are traversed in predecessor order, starting with the last
+node.
-While it is possible to check for these cases, in many cases the overhead
-necessary to make the check is substantial in time or space. Implementations
-are encouraged to check for as many of these cases as possible and raise
-Constraint_Error if detected.
-End AARM Notes.
-Implementation Requirements
+For any two elements E1 and E2, the boolean values (E1 < E2), (Key(E1) < E2),
+and (Key(E2) > E1) are all expected to be equal. If Key, Generic_Keys."<", or
+Generic_Keys.">" behave in some other manner, the behavior of this package is
+unspecified. Which subprograms of this package call Key, Generic_Keys."<" and
+Generic_Keys.">", and how many times the functions are called, is unspecified.
+
+In addition to the semantics described in A.17.7, the subprograms in package
+Generic_Keys named Floor, Ceiling, "<", and ">", are equivalent to the
+corresponding subprograms in the parent package, with the difference that the
+Key subprogram parameter is compared to elements in the container using the
+Generic_Keys generic formal relational operators.
-No storage associated with an ordered set object shall be lost upon assignment
-or scope exit.
Implementation Advice
-If *N* is the length of a set, then:
- * The worst-case time complexity of Insert and Find should be O((log N)**2)
- or better;
- * the worst-case time complexity of Element should be O(log N) or better.
+If *N* is the length of a set, then the worst-case time complexity of the
+Insert, Include, Replace, Delete, Exclude and Find operations that take an
+element parameter should be O((log N)**2) or better. The worst-case time
+complexity of the subprograms that take a cursor parameter should be O(1).
-AARM Note
-A balanced (red-black) tree for keys has O(log N) worst-case performance. Note
-that a O(N) worst-case implementation (like a list) would be wrong.
-We do not mean to overly constrain implementation strategies here. However, it
-is important for portability that the performance of large containers has
-roughly the same factors on different implementations. If a program is moved
-to an implementation that takes O(N) to find elements, that program could
-be unusable when the sets are large. We allow the extra log N factors because
-the proportionality constant and caching effects are likely to be larger than
-the log factor, and we don't want to discourage innovative implementations.
+AARM Note:
+See Ordered_Maps for implementation notes regarding some of the operations of
+this package.
-A.17.6 The Package Containers.Indefinite_Vectors
+A.17.10 The Package Containers.Indefinite_Vectors
The language-defined package Containers.Indefinite_Vectors provides a
private type Vector and a set of operations. It provides the same
@@ -3363,7 +4058,7 @@
may be constrained even if Element_Type is unconstrained.
-A.17.7 The Package Containers.Indefinite_Doubly_Linked_Lists
+A.17.11 The Package Containers.Indefinite_Doubly_Linked_Lists
The language-defined package Containers.Indefinite_Doubly_Linked_Lists
provides private types List and Cursor, and a set of operations for each
@@ -3399,11 +4094,10 @@
may be constrained even if Element_Type is unconstrained.
-A.17.8 The Package Containers.Indefinite_Hashed_Maps
+A.17.12 The Package Containers.Indefinite_Hashed_Maps
The language-defined package Containers.Indefinite_Hashed_Maps provides
-private types Map and Cursor, and a set of operations for each type. It
-provides the same operations as the package Hashed_Maps does, with the
+a map with the same operations as the package Hashed_Maps, with the
difference that the generic formal types Key_Type and Element_Type are
indefinite.
@@ -3435,12 +4129,65 @@
* The Element parameter of access subprogram Process of Update_Element
may be constrained even if Element_Type is unconstrained.
+
+A.17.13 The Package Containers.Indefinite_Ordered_Maps
+
+The language-defined package Containers.Indefinite_Ordered_Maps provides
+a map with the same operations as the package Ordered, with the
+difference that the generic formal types Key_Type and Element_Type are
+indefinite.
+
+Static Semantics
+
+The declaration of the library package Containers.Indefinite_Ordered_Maps
+has the same contents as Containers.Ordered_Maps except:
+
+ * The generic formal Key_Type is indefinite.
+
+ * The generic formal Element_Type is indefinite.
+
+ * The procedure with the profile:
+ procedure Insert (Container : in out Map;
+ Key : in Key_Type;
+ Position : out Cursor;
+ Inserted : out Boolean);
+ is omitted.
+
+AARM Note: This procedure is omitted because there is no way to create a
+default-initialized object of an indefinite type. We considered having this
+routine insert an empty element similar to the empty elements of a vector,
+but rejected this possibility because the semantics are fairly complex and
+very different from the existing case. That would make it more error-prone
+to convert a container from a definite type to an indefinite type; by
+omitting the routine completely, any problems will be diagnosed by the
+compiler.
+
+ * The Element parameter of access subprogram Process of Update_Element
+ may be constrained even if Element_Type is unconstrained.
+
+
+A.17.14 The Package Containers.Indefinite_Hashed_Sets
+
+The language-defined package Containers.Indefinite_Hashed_Sets provides
+a set with the same operations as the package Hashed_Sets, with the
+difference that the generic formal type Element_Type is indefinite.
+
+Static Semantics
+
+The declaration of the library package Containers.Indefinite_Hashed_Sets
+has the same contents as Containers.Hashed_Sets except:
+
+ * The generic formal Element_Type is indefinite.
+
+ * The Element parameter of access subprogram Process of
+ Checked_Update_Element may be constrained even if Element_Type is
+ unconstrained.
+
-A.17.9 The Package Containers.Indefinite_Ordered_Sets
+A.17.15 The Package Containers.Indefinite_Ordered_Sets
The language-defined package Containers.Indefinite_Ordered_Sets provides
-private types Set and Cursor, and a set of operations for each type. It
-provides the same operations as the package Ordered_Sets does, with the
+a set with the same operations as the package Ordered_Sets, with the
difference that the generic formal type Element_Type is indefinite.
Static Semantics
@@ -3455,7 +4202,7 @@
unconstrained.
-A.17.10 Array Sorting
+A.17.16 Array Sorting
The language-defined procedures Containers.Generic_Array_Sort and
Containers.Generic_Constrained_Array_Sort provide sorting on
@@ -3931,7 +4678,7 @@
end Op;
-A.17.4 The Package Containers.Hashed_Maps
+A.17.5 The Package Containers.Hashed_Maps
It's often the case that you know apriori the total number of elements
you intend to insert into the map. Under these circumstances you should
@@ -4741,7 +5488,7 @@
operation does a search anyway.
-A.17.5 The Package Containers.Ordered_Sets
+A.17.9 The Package Containers.Ordered_Sets
Suppose we have a set and want to copy the elements from the set into an
array. Here's one way to do it:
@@ -8711,7 +9458,8 @@
From: Randy Brukardt
Sent: Monday, October 3, 2004 xx:xx PM
-Here is a listing of the AI-302 updates that I made beyond those discussed at the meeting. These mostly have come up in more recent e-mail discussions.
+Here is a listing of the AI-302 updates that I made beyond those discussed at
+the meeting. These mostly have come up in more recent e-mail discussions.
1) Moved the AARM noted describing the now removed Assert to a (user) "Note".
The fact that instantiating Ada.Containers.Vectors with a type for which
@@ -8752,9 +9500,11 @@
(see below), replacing the element referred to by the Key. Thus it works
similarly to Checked_Update_Element.
- Replace (Container, Cursor, New_Item) also has been added to the Set itself,
- as there is not a Replace_Element for a set. This tries to replace in place,
- but will do an insert/delete if necessary.
+ Replace_Element (Container, Cursor, New_Item) also has been added to the
+ Set itself, as there is not a Replace_Element for a set. This tries to
+ replace in place, but will do an insert/delete if necessary. [Should this
+ have a different name? The profile and semantics are a bit different than
+ the normal Replace_Element?]
4) The definition of *cursor* was buried in the introductory AARM text. I moved
@@ -8811,7 +9561,7 @@
operations that would make the cursor ambigious. (That's a bounded error in
other cases.)
-7) Matt had previous made a number of suggestions about improving/correcting
+7) Matt had previously made a number of suggestions about improving/correcting
the examples. These have been integrated.
8) Delete for cursors does nothing if the cursor is No_Element for Lists, Maps,
Questions? Ask the ACAA Technical Agent