pragma Preelaborate (Hashed_Maps);
|
Type Summary
Cursor |
| Primitive Operations: |
Delete,
Element,
Find,
First,
Has_Element,
Insert,
Insert,
Is_Equal_Key,
Is_Equal_Key,
Is_Equal_Key,
Key,
Next,
Next,
Replace_Element,
Update_Element
|
Iterate_Process |
Map |
| Primitive Operations: |
"=",
Capacity,
Clear,
Delete,
Delete,
Element,
Find,
First,
Insert,
Insert,
Is_Empty,
Is_In,
Iterate,
Length,
Move,
Replace,
Set_Capacity
|
Update_Element_Process |
|
Constants and Named Numbers
Empty_Map : constant Map;
|
|
Represents the empty Map object. It has a length of 0. If an object of
type Map is not otherwise initialized, it will be
initialized to the same value as Empty_Map.
|
No_Element : constant Cursor;
|
|
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.
|
|
Other Items:
|
type Map is tagged private;
|
An object of type Map contains an expandable hash table,
-- which is used to provide direct access to elements. The *size* 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 ("resized"). 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).
|
|
|
function "=" (Left, Right : Map) return Boolean;
|
If Left and Right denote the same map
Map object, then the function returns immediately the value
True. If Left and Right have
different lengths, then the function returns the value False
. Otherwise, for each key K> in Left, the function
returns False if:
* K is not present in Right (using the generic formal
equality operator for keys); 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 or element equality is propagated.
|
|
function Length (Container : Map) return Count_Type;
|
|
Returns the number of key/element pairs in Container.
|
|
function Is_Empty (Container : Map) return Boolean;
|
|
Equivalent to Length (Container) = 0.
|
|
procedure Clear (Container : in out Map);
|
|
Removes all the elements from Container. The size of
Container is not affected. Any exceptions raised during
deallocation of storage propagated.
|
|
function Element (Position : Cursor)
return Element_Type;
|
|
If Position equals No_Element, then
Constraint_Error is propagated. Otherwise,
this operation returns the element designated by Position.
|
|
|
procedure Update_Element
(Position : in Cursor;
Process : Update_Element_Process);
|
Ada0Y
not null access procedure (Element : in out Element_Type));
The best we can do in Ada95 is to generate a run-time error, so if
Process is null a
Program_Error is raised.
If Position equals No_Element, then
Constraint_Error is propagated. Otherwise,
Update_Element invokes the generic actual procedure bound
to Process with the element designated by
Position as the argument.
|
|
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);
|
|
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 size 0 after successful
call to Move.
|
|
procedure Insert (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type;
Position : out Cursor;
Success : out Boolean);
|
|
If Length (Container) equals Size (Container),
then Insert calls Resize to resize
Container to some larger value. Insert then
uses Hash and Is_Equal_Key to check if
Key is already present in Container. If a key
matches, Success 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. Success returns True
and Position designates the newly-inserted node. Any
exceptions raised during allocation are propagated and
Container is not modified.
|
|
procedure Replace (Container : in out Map;
Key : in Key_Type;
New_Item : in Element_Type);
|
MJH:
This should probably be named "Insert", since
it can actuall insert a new key.
ENDMJH.
Replace inserts Key and New_Item
as per Insert, with the difference that if Key is already
in the map, then this operation assigns New_Item to the
element associated with Key. Any exceptions raised during
as signmentare propagated.
|
|
procedure Insert (Container : in out Map;
Key : in Key_Type;
Position : out Cursor;
Success : out Boolean);
|
|
Inserts Key into Container as per Insert
(Container, Key, New_Item, Position, Success), with the
difference that an 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.
|
|
procedure Delete (Container : in out Map;
Key : in Key_Type);
|
|
It uses Hash and Is_Equal_Key to check if
Key is present in Container. If
Key matches the key of a node, Delete removes
the node from the map and then deallocates the node.
|
|
procedure Delete (Container : in out Map;
Position : in out Cursor);
|
|
If Position equals No_Element, this operation
has no effect. Otherwise, Delete removes the node from the
map and deallocates the node. Position is set to
No_Element on return.
|
|
function Is_In (Key : Key_Type;
Container : Map)
return Boolean;
|
|
Equivalent to Find (Container, Key) /= No_Element.
|
|
function Find (Container : Map;
Key : Key_Type)
return Cursor;
|
|
If Length (Container) equals 0, then this function returns
No_Element. Otherwise, it uses Hash and
Is_Equal_Key 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.
|
|
|
|
procedure Set_Capacity (Container : in out Map;
Capacity : in Count_Type);
|
|
If Capacity (Container) is equal to or greater than
Capacity, this operation has no effect. Otherwise, it
allocates a new hash table such that the length of the resulting map can
become at least the value Capacity without requiring an
additional Resize operation. 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 First (Container : Map) return Cursor;
|
|
If Length (Container) = 0, then First returns
No_Element. Otherwise, it returns a cursor that designates
the first hashed node in Container.
|
|
function Next (Position : Cursor) return Cursor;
|
Returns a cursor that designates the node that immediately follows
Position. If there are no more nodes in the map identified
by Position, it returns No_Element. If
Position equals No_Element, then
No_Element is returned.
If there are no other intervening operations, calling Next
in a loop starting with First (Container) shall return a
cursor designating each node in the Container (other than
First) exactly once, then return No_Element.
|
|
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.
|
|
function Key (Position : Cursor) return Key_Type;
|
|
If Position equals No_Element, then
Constraint_Error is propagated. Otherwise,
this operation returns the key component of the node designated by
Position.
|
|
function Is_Equal_Key (Left, Right : Cursor)
return Boolean;
|
|
Equivalent to Is_Equal_Key (Key (Left), Key (Right)).
|
|
|
|
|
procedure Iterate
(Container : in Map;
Process : Iterate_Process);
|
Ada0Y
not null access procedure (Position : in Cursor));
The best we can do in Ada95 is to generate a run-time error, so if
Process is null a
Program_Error is raised.
Iterate calls Process with a cursor that
designates each node in the Container. Any exceptions
raised during Process are propagated.
|
|
|
private
|