OLHashMap Class Reference
[Containers]

A map based on a hash table. More...

#import <ObjectiveLib/HashMap.h>

Inheritance diagram for OLHashMap:

Inheritance graph
[legend]
List of all members.

Public Member Functions

(void) - assignKey:value:
 Assign a value to a key.
(OLHashIterator *) - begin
 Return an iterator that points to the first element in the map.
(void) - clear
 Remove all elements.
(int) - compare:
 Compare this hash map to another object.
(id) - copy
 Make a copy of this hash map.
(unsigned) - count:
 Return the number of instances of key in the map.
(BOOL) - empty
 Return whether the map is empty.
(OLHashIterator *) - end
 Return an iterator that points to one position beyond the last element.
(OLPair *) - equalRange:
 Return a range whose elements are equal to key.
(void) - erase:
 Remove the element designated by where.
(void) - eraseFrom:to:
 Remove a range of elements.
(unsigned) - eraseKey:
 Erase all instances of key.
(OLHashIterator *) - find:
 Find an element.
(id) - insert:
 Insert a key-value pair into the map.
(void) - insertFrom:to:
 Insert a range of key-value pairs into the map.
(id) - insertKey:value:
 Insert a key-value pair.
(BOOL) - isEqual:
 Test whether another map is equal to this one.
(Object< OLBoolBinaryFunction > *) - keyEqual
 Return the comparison function for keys.
(unsigned) - maxSize
 Return the maxiumum number of objects that can be stored in a map.
(unsigned) - size
 Return the number of elements in the map.
(void) - swap:
 Swap this map with another one.
(id) - valueForKey:
 Find the value of a given key.
(void) - writeSelfToStream:
 Write the object to a stream.
Initializers and Deallocators
(id) - free
 Finalize the map and deallocate any allocated memory.
(id) - init
 Initialize the map.
(id) - initFrom:to:
 Initialize the map.
(id) - initFrom:to:tableSize:
 Initialize the map.
(id) - initFrom:to:tableSize:keyEqual:
 Initialize the map.
(id) - initWithHashMap:
 Initialize the map.
(id) - initWithObjectInStream:
 Initialize the object.
(id) - initWithTableSize:
 Initialize the map.
(id) - initWithTableSize:keyEqual:
 Initialize the map.

Static Public Member Functions

(id) + hashMap
 Create and return a new hash map.
(id) + hashMapFrom:to:
 Create and return a new hash map.
(id) + hashMapWithHashMap:
 Create and return a new hash map.

Protected Attributes

OLHashTableMap * table
 The hash table that provides the underlying data structure.

Detailed Description

A map based on a hash table.

This class provides very similar functionality to OLMap, but it uses a hash table as the underyling data structure. Like OLMap it is a container for associative values with unique keys, meaning that attempting to insert a key that already exists in the container will fail. However, there are important differences to OLMap due to the use of the hash table as the data structure. Searching for a key in a hash map is inherently very fast, which is the primary reason to choose OLHashMap over OLMap. Another difference is that, unlike OLMap, items in a hash map do not appear in a predictable order. Of course, the order is not random, but it does depend on the results of the hash function used.

OLHashMap requires a function object to test elements for equality, as equal elements are grouped together. If no function is explicitly given, then OLEqualTo is used.

Note:
It is important only to use objects of the same type for the keys in a hash map. If a mixture of types is used, then different hash functions will also be used, resulting in corruption of the distribution of elements in the hash table.
See also:
OLHashIterator, OLMap


Member Function Documentation

- (void) assignKey: (id)  key
value: (id)  value 

Assign a value to a key.

If the key exists in the map, then value is assigned to the key and the old value is dropped. If the key does not exist in the map, then the key-value pair is inserted.

Precondition:
key must respond to the message hash.
Parameters:
key the key to which to assign
value the value to assign

Reimplemented in OLHashMultiMap.

- (OLHashIterator*) begin  

Return an iterator that points to the first element in the map.

The object to which the iterator points is an instance of OLPair. The first element of the pair is the key and the second element of the pair is the key's value.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Returns:
the first iterator for the map

- (void) clear  

Remove all elements.

- (int) compare: (id)  other  

Compare this hash map to another object.

If the other object is of type OLHashMap, each of the contained objects is compared to the corresponding object in other by calling the compare: method.

Parameters:
other the object with which to compare this one
Returns:
a value greater than, equal to, or less than zero accoringly as this object is greater than, equal to, or less than other

- (id) copy  

Make a copy of this hash map.

Returns:
the copy

- (unsigned) count: (id)  key  

Return the number of instances of key in the map.

Precondition:
key must respond to the message hash.
Parameters:
key the key for which to search
Returns:
the number of values that exist for key

- (BOOL) empty  

Return whether the map is empty.

Returns:
YES if the map is empty, NO otherwise

- (OLHashIterator*) end  

Return an iterator that points to one position beyond the last element.

The object to which the iterator points is an instance of OLPair. The first element of the pair is the key and the second element of the pair is the key's value.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Returns:
an iterator one position beyond the last element in the map

- (OLPair*) equalRange: (id)  key  

Return a range whose elements are equal to key.

The returned pair contains two instances of OLHashIterator delimiting the range of elements. The objects to which the iterators point are instances of OLPair. The first element of the pair is the key and the second element of the pair is the key's value.

Precondition:
key must respond to the message hash.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
key the value for which to search
Returns:
a pair of OLHashIterator instances that define the range of elements in the map equal to key

- (void) erase: (OLHashIterator *)  where  

Remove the element designated by where.

Precondition:
where must point to an element in this map.
Parameters:
where an iterator designating the element to remove

- (void) eraseFrom: (OLHashIterator *)  first
to: (OLHashIterator *)  last 

Remove a range of elements.

All elements in the range [first, last) will be removed from the map.

Precondition:
first and last must refer to elements in this map.
Parameters:
first the first in the range of elements to remove
last one position beyond the last in the range of elements to remove

- (unsigned) eraseKey: (id)  key  

Erase all instances of key.

The map is searched for key, all instances are removed from the map and the number removed is returned.

Precondition:
key must respond to the message hash.
Parameters:
key the key to remove from the map
Returns:
the number of elements removed

- (OLHashIterator*) find: (id)  key  

Find an element.

The element key is searched for in the map and an iterator to its location is returned. If the element does not exist in the map, then the returned iterator will be equal to the iterator returned by end.

The object to which the iterator points is an instance of OLPair. The first element of the pair is the key and the second element of the pair is the key's value.

Precondition:
key must respond to the mssage hash.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
key the key for which to search
Returns:
an iterator pointing to the location of key, or an iterator equal to that returned by end if key does not exist

- (id) free  

Finalize the map and deallocate any allocated memory.

+ (id) hashMap  

Create and return a new hash map.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Returns:
a new hash map

+ (id) hashMapFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last 

Create and return a new hash map.

The hash map is initialized with the contents of the range [first, last).

Precondition:
Each element in the range [first, last) must be an instance of OLPair. The first element of the pair is the key and the second element is the key's value. Additionally, each key object must respond to the message hash.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
first the first in the range of elements to insert
last one beyond the last in the range of elements to insert
Returns:
a new hash map

+ (id) hashMapWithHashMap: (OLHashMap *)  right  

Create and return a new hash map.

The hash map is initialized with the contents of right.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
right the hash map to copy
Returns:
a new hash map

- (id) init  

Initialize the map.

The map is empty and uses OLEqualTo to test for equality.

Returns:
a reference to this map

- (id) initFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last 

Initialize the map.

The map uses the comparison function OLEqualTo to test for equality, and inserts all elements in the range [first, last).

Precondition:
Each element in the range [first, last) must be an instance of OLPair. The first element of the pair is the key and the second element is the key's value. Additionally, each key object must respond to the message hash.
Parameters:
first the first in the range of elements to insert
last one beyond the last in the range of elements to insert
Returns:
a reference to this map

- (id) initFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
tableSize: (unsigned)  size 

Initialize the map.

The map uses the comparison function OLEqualTo to test for equality, and inserts all elements in the range [first, last). The parameter size is uses as a hint for the desired hash table size. The table size will grow as needed, so it is not crucial that this parameter carry any particular meaning. However, providing a size can reduce the number of memory allocations required to build the table.

Precondition:
Each element in the range [first, last) must be an instance of OLPair. The first element of the pair is the key and the second element is the key's value. Additionally, each key object must respond to the message hash.
Parameters:
first the first in the range of elements to insert
last one beyond the last in the range of elements to insert
size a hint as to the desired hash table size
Returns:
a reference to this map

- (id) initFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
tableSize: (unsigned)  size
keyEqual: (Object< OLBoolBinaryFunction > *)  eq 

Initialize the map.

The map uses the comparison function eq to test for equality, and inserts all elements in the range [first, last). The parameter size is used as a hint for the desired hash table size. The table size will grow as needed, so it is not crucial that this parameter carry any particular meaning. However, providing a size can reduce the number of memory allocations required to build the table.

Precondition:
Each element in the range [first, last) must be an instance of OLPair. The first element of the pair is the key and the second element is the key's value. Additionally, each key object must respond to the message hash.
Parameters:
first the first in the range of elements to insert
last one beyond the last in the range of elements to insert
size a hint as to the desired hash table size
eq the function object used to test elements for equality
Returns:
a reference to this map

- (id) initWithHashMap: (OLHashMap *)  right  

Initialize the map.

The map copies the comparison function and all elements from right.

Parameters:
right the hash map to copy
Returns:
a reference to this map

- (id) initWithObjectInStream: (OLObjectInStream *)  stream  

Initialize the object.

Each instance variable is read from stream and all other initialization is performed.

Parameters:
stream the stream from which to read
Returns:
a reference to this object

Reimplemented from < OLStreamable >.

- (id) initWithTableSize: (unsigned)  size  

Initialize the map.

The map is initially empty and OLEqualTo to test elements for equality. The parameter size is a hint as to the desired capacity for the hash table. The table will grow as needed, so it isn't strictly necessary to specify a table size, but providing a valid hint can reduce the number of memory allocations performed.

Parameters:
size a hint as to the desired hash table size
Returns:
a reference to this map

- (id) initWithTableSize: (unsigned)  size
keyEqual: (Object< OLBoolBinaryFunction > *)  eq 

Initialize the map.

The map is initially empty and uses eq to test elements for equality. The parameter size is a hint as to the desired capacity for the hash table. The table will grow as needed, so it isn't strictly necessary to specify a table size, but providing a valid hint can reduce the number of memory allocations performed.

Parameters:
size a hint as to the desired hash table size
eq the function object used to test elements for equality
Returns:
a reference to this map

- (id) insert: (OLPair *)  keyValue  

Insert a key-value pair into the map.

An attempt is made to insert keyValue into the map, and an instance of OLPair is returned indicating the state of the insertion. The first element in the returned pair is an instance of OLHashIterator indicating the position of keyValue in the map, and the second element of the returned pair is an object that responds to the message boolValue. The message boolValue will return YES if the insertion was successful, or NO if not.

Precondition:
The first element of keyValue must be the key and the second element must be the key's value. Additionally, the key object must resopnd to the message hash.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
keyValue the key-value pair to insert
Returns:
an instance of OLPair indicating the position of keyVal in the map and whether the insertion succeeded or failed

Reimplemented in OLHashMultiMap.

- (void) insertFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last 

Insert a range of key-value pairs into the map.

An attempt is made to insert all pairs in the range [first, last), however there is no guarantee that any of the elements in the range will actually be inserted if they already exist in the map.

Precondition:
All elements in the range [first, last) must be instances of OLPair where the first element of the pair is the key and the second element is the key's value. Additionally, each key object must respond to the message hash.
Parameters:
first the first in the range of pairs to insert
last one position beyond the last in the range of pairs to insert

Reimplemented in OLHashMultiMap.

- (id) insertKey: (id)  key
value: (id)  val 

Insert a key-value pair.

This message is simply a wrapper for insert:, provided as a convenience. It elminiates the need to create an instance of OLPair before performing insertion. As with insert: the message returns an instance of OLPair indicating the state of the insertion. The first element of the pair returned is an instance of OLHashIterator indicating the position of key in the map, and the second element of the pair is an object that responds to the message boolValue. The message boolValue will return YES if the insertion succeeded, or NO if it did not.

Precondition:
key must respond to the message hash.
Parameters:
key the key to insert
val the value of the key
Returns:
an instance of OLPair indicating the position of key in the map and whether the insertion succeeded or failed

- (BOOL) isEqual: (id)  object  

Test whether another map is equal to this one.

Two maps are considered equal if they contain the same number of objects and the and the value of each key is equal to the value of the corresponding key in the other map. Values are always compared using the message isEqual:, while keys are compared using the functor returned by the message keyEqual.

Parameters:
object the object to test
Returns:
YES if object is equal to this map, NO otherwise

Reimplemented in OLHashMultiMap.

- (Object<OLBoolBinaryFunction>*) keyEqual  

Return the comparison function for keys.

The function is used to group equal elements together.

Returns:
the function object used to compare keys for equality

- (unsigned) maxSize  

Return the maxiumum number of objects that can be stored in a map.

This limit is theoretical, meaning that there is no guarantee that you can insert this many objects into any given map. The memory conditions of the run-time system play an important role.

Returns:
the maximum number of objects for a map

- (unsigned) size  

Return the number of elements in the map.

Returns:
the number of elements

- (void) swap: (OLHashMap *)  right  

Swap this map with another one.

All elements in right will be placed into this map, and all elements in this map will be placed in right.

Parameters:
right the map with which to swap this one

- (id) valueForKey: (id)  key  

Find the value of a given key.

The map is searched for key, and if it is found its value is returned. Otherwise, the message returns nil.

Precondition:
key must respond to the message hash.
Parameters:
key the key for which to search
Returns:
the key's value or nil if the key does not exist in the map

Reimplemented in OLHashMultiMap.

- (void) writeSelfToStream: (OLObjectOutStream *)  stream  

Write the object to a stream.

All instance variables are written to stream.

Parameters:
stream the stream to which to write.

Reimplemented from < OLStreamable >.


Member Data Documentation

- (OLHashTableMap*) table [protected]

The hash table that provides the underlying data structure.


The documentation for this class was generated from the following file:
ObjectiveLibGenerated Sun Apr 22 15:18:35 2007, © 2004-2007 Will Mason
SourceForge.net Logo