ObjectiveLib  1.0.0
Public Member Functions | Static Public Member Functions | Protected Attributes
OLHashSet Class Reference

A hash table based set. More...

#import <ObjectiveLib/HashSet.h>

Inheritance diagram for OLHashSet:
Inheritance graph
[legend]

List of all members.

Public Member Functions

(OLHashIterator *) - begin
 Return an iterator pointing to the beginning of the sequence.
(void) - clear
 Remove all elements.
(int) - compare:
 Compare this hash set to another object.
(id) - copyWithZone:
 Make a copy of this hash set allocating memory from the given zone.
(unsigned) - count:
 Return the number of elements equal to value.
(BOOL) - empty
 Test whether the set is empty.
(void) - encodeWithCoder:
 Encode the map.
(OLHashIterator *) - end
 Return an iterator pointing to one position beyond the end of the sequence.
(OLPair *) - equalRange:
 Return a range whose elements are equal to value.
(void) - erase:
 Remove the element designated by where.
(void) - eraseFrom:to:
 Remove a range of elements.
(unsigned) - eraseValue:
 Erase all instances of value.
(OLHashIterator *) - find:
 Find an element.
(id) - insert:
 Insert an object into the set.
(void) - insertFrom:to:
 Insert a range of objects into the set.
(BOOL) - isEqual:
 Test whether another set is equal to this one.
(NSObject
< OLBoolBinaryFunction > *) 
- keyEqual
 Return the function used to compare keys in the set.
(unsigned) - maxSize
 Return the maxiumum number of objects that can be stored in a set.
(unsigned) - size
 Return the number of elements in the set.
(void) - swap:
 Swap this set with another one.
(void) - writeSelfToStream:
 Write the object to a stream.
Initializers and Deallocators
(id) - init
 Initialize the set.
(id) - initFrom:to:
 Initialize the set.
(id) - initFrom:to:tableSize:
 Initialize the set.
(id) - initFrom:to:tableSize:keyEqual:
 Initialize the set.
(id) - initWithCoder:
 Initialize the set.
(id) - initWithHashSet:
 Initialize the set.
(id) - initWithObjectInStream:
 Initialize the object.
(id) - initWithTableSize:
 Initialize the set.
(id) - initWithTableSize:keyEqual:
 Initialize the set.
(void) - dealloc
 Finalize the set and deallocate any allocated memory.

Static Public Member Functions

(id) + hashSet
 Create and return a new hash set.
(id) + hashSetFrom:to:
 Create and return a new hash set.
(id) + hashSetWithHashSet:
 Create and return a new hash set.

Protected Attributes

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

Detailed Description

A hash table based set.

The class provides very similar functionality to OLSet, but it uses a hash table as the underlying data structure. Like OLSet it is a container of unique objects, and attempting to insert an object that is already in the set will fail. However, there are important differences to OLSet due to the use of the hash table as the data structure. Searching for an object in a hash set is inherently very fast, which is the main reason to choose to use OLHashSet over OLSet. Another difference is that, unlike OLSet, items in a hash set do not appear in a predictable order. Of course, the items are not ordered randomly, but the order will depend on the result of the hash function used for elements in the hash set.

OLHashSet 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 place objects of the same type in a hash set. 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, OLSet

Member Function Documentation

Return an iterator pointing to the beginning of the sequence.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Returns:
an iterator pointing to the first element
- (void) clear

Remove all elements.

- (int) compare: (id)  other

Compare this hash set to another object.

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

Parameters:
otherthe 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) copyWithZone: (NSZone *)  zone

Make a copy of this hash set allocating memory from the given zone.

Parameters:
zonethe zone from which to allocate memory
Returns:
the copy
- (unsigned) count: (id)  value

Return the number of elements equal to value.

Precondition:
value must respond to the message hash.
Parameters:
valuethe value to search for in the set
Returns:
the number of instances of value
- (void) dealloc

Finalize the set and deallocate any allocated memory.

- (BOOL) empty

Test whether the set is empty.

Returns:
YES if the set is empty, NO otherwise
- (void) encodeWithCoder: (NSCoder *)  encoder

Encode the map.

The map is saved to an archive using encoder. The map will be retrieved from the archive using the initializer initWithCoder:.

Parameters:
encoderthe coder which will save the bit set to the archive

Return an iterator pointing to one position beyond the end of the sequence.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Returns:
an iterator pointing to one position beyond the last element
- (OLPair*) equalRange: (id)  value

Return a range whose elements are equal to value.

The returned pair contains two instances of OLHashIterator delimiting the range of elements.

Precondition:
value must respond to the message hash.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
valuethe value for which to search
Returns:
a pair of OLHashIterator instances that define the range of elements in the set equal to value
- (void) erase: (OLHashIterator *)  where

Remove the element designated by where.

Precondition:
where must point to an element in this set.
Parameters:
wherean 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 set.

Precondition:
first and last must refer to elements in this set.
Parameters:
firstthe first in the range of elements to remove
lastone position beyond the last in the range of elements to remove
- (unsigned) eraseValue: (id)  value

Erase all instances of value.

The set is searched for value, all instances are removed from the set and the number removed is returned.

Precondition:
value must respond to the message hash.
Parameters:
valuethe value to remove from the set
Returns:
the number of elements removed
- (OLHashIterator*) find: (id)  object

Find an element.

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

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

Create and return a new hash set.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Returns:
a new hash set
+ (id) hashSetFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last 

Create and return a new hash set.

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

Precondition:
All objects in the range [first, last) must respond to the message hash.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
firstthe first in the range of elements to insert
lastone beyond the last in the range of elements to insert
Returns:
a new hash set
+ (id) hashSetWithHashSet: (OLHashSet *)  right

Create and return a new hash set.

The hash set is initialized with the contents of right.

Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
rightthe hash set to copy
Returns:
a new hash set
- (id) init

Initialize the set.

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

Returns:
a reference to this set
- (id) initFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last 

Initialize the set.

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

Precondition:
All objects in the range [first, last) must respond to the message hash.
Parameters:
firstthe first in the range of elements to insert
lastone beyond the last in the range of elements to insert
Returns:
a reference to this set
- (id) initFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
tableSize: (unsigned)  size 

Initialize the set.

The set uses the comparison function OLEqualTo 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:
All objects in the range [first, last) must respond to the message hash.
Parameters:
firstthe first in the range of elements to insert
lastone beyond the last in the range of elements to insert
sizea hint as to the desired hash table size
Returns:
a reference to this set
- (id) initFrom: (OLForwardIterator *)  first
to: (OLForwardIterator *)  last
tableSize: (unsigned)  size
keyEqual: (NSObject< OLBoolBinaryFunction > *)  eq 

Initialize the set.

The set 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:
All objects in the range [first, last) must respond to the message hash.
Parameters:
firstthe first in the range of elements to insert
lastone beyond the last in the range of elements to insert
sizea hint as to the desired hash table size
eqthe function object used to test elements for equality
Returns:
a reference to this set
- (id) initWithCoder: (NSCoder *)  decoder

Initialize the set.

This initializer creates a new set from an archive and returns it.

Postcondition:
The set returned will be identical to the set saved to the archive using the encodeWithCoder: message.
Parameters:
decoderthe coder which will decode the archived set
Returns:
a reference to this set
- (id) initWithHashSet: (OLHashSet *)  right

Initialize the set.

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

Parameters:
rightthe hash set to copy
Returns:
a reference to this set

Initialize the object.

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

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

Reimplemented from <OLStreamable>.

- (id) initWithTableSize: (unsigned)  size

Initialize the set.

The set is initially empty and uses 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:
sizea hint as to the desired hash table size
Returns:
a reference to this set
- (id) initWithTableSize: (unsigned)  size
keyEqual: (NSObject< OLBoolBinaryFunction > *)  eq 

Initialize the set.

The set 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:
sizea hint as to the desired hash table size
eqthe function object used to test elements for equality
Returns:
a reference to this set
- (id) insert: (id)  object

Insert an object into the set.

An attempt is made to insert object into the set, 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 object in the set, 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 object to insert must respond to the message hash.
Note:
If OpenStep is present the returned object will be autoreleased before being returned.
Parameters:
objectthe element to insert
Returns:
an instance of OLPair indicating the position of object in the set and whether the insertion succeeded or failed

Reimplemented in OLHashMultiSet.

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

Insert a range of objects into the set.

An attempt is made to insert all objects 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 set.

Precondition:
All objects in the range [first, last) must respond to the message hash.
Parameters:
firstthe first in the range of objects to insert
lastone position beyond the last in the range of objects to insert

Reimplemented in OLHashMultiSet.

- (BOOL) isEqual: (id)  object

Test whether another set is equal to this one.

Two sets are considered equal if they contain the same number of objects and the objects are in the same order and each object is equal to the corresponding object in the other set.

Parameters:
objectthe object to test
Returns:
YES if object is equal to this set

Reimplemented in OLHashMultiSet.

Return the function used to compare keys in the set.

Returns:
the function object that is used to compare keys
- (unsigned) maxSize

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

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

Returns:
the maximum number of objects for a set
- (unsigned) size

Return the number of elements in the set.

Returns:
the number of elements
- (void) swap: (OLHashSet *)  right

Swap this set with another one.

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

Parameters:
rightthe set with which to swap this one
- (void) writeSelfToStream: (OLObjectOutStream *)  stream

Write the object to a stream.

All instance variables are written to stream.

Parameters:
streamthe stream to which to write.

Reimplemented from <OLStreamable>.


Member Data Documentation

- (OLHashTable*) table [protected]

The hash table that provides the underlying data structure.


The documentation for this class was generated from the following file:

ObjectiveLibGenerated Sat Feb 15 2014 07:45:34, © 2004-2007 Will Mason