Maintains a set, where an element is a 64 bit integer. More...

#include <HashSet.h>

Inheritance diagram for grafalgo::HashSet:

Collaboration diagram for grafalgo::HashSet:

Public Member Functions
	HashSet (int)
	Constructor for HashSet, allocates space and initializes set.
	~HashSet ()
	Destructor for HashSet.
void	clear ()
	Clear the set contents.
void	resize (int)
	Resize a HashSet object, discarding old contents.
void	expand (int)
	Expand the space available for this HashSet.
void	copyFrom (const HashSet &)
	Copy into this from source.
int	size () const
	Determine the number of elements in the set.
bool	member (int64_t) const
	Determine if an element is in the set.
index	first () const
	Get the index of the first element in the set.
index	next (index) const
	Determine the index of the next element in the set.
bool	isValid (index) const
	Determine if an index corresponds to a set element.
uint64_t	val (index) const
	Get the value of an element in the set.
index	getIndex (int64_t) const
	Perform a lookup in the set.
index	insert (int64_t)
	Insert a value into the set.
void	remove (int64_t)
	Remove a value from the set.
string &	toString (string &) const
	Create a string representation of the set.
Private Types
typedef uint32_t	bkt_t [BKT_SIZ]
	bucket type
Private Member Functions
uint32_t	hashit (int64_t, int) const
	Compute a bucket index for a given val.
void	makeSpace (int)
	Allocate and initialize space for list.
void	freeSpace ()
	Free dynamic storage used by list.
Private Attributes
int	nb
	# of buckets in each half
uint32_t	bktMsk
	mask used by hash function
bkt_t *	bkt
	buckets for hash table
SetPair *	ex
	indexes of in-set elements and out
Static Private Attributes
static const int	BKT_SIZ = 8
	# of elements per bucket

Detailed Description

Maintains a set, where an element is a 64 bit integer.

Main methods member - tests an element for membership in the set insert - adds an element to the set remove - removes an element from the set

Each element is assigned an index that can be used for iterating through the set.

The implementation uses a 2-left hash table with eight items in each bucket. The table is dimensioned for a load factor of no more than 50%.

Definition at line 32 of file HashSet.h.

Constructor & Destructor Documentation

grafalgo::HashSet::HashSet ( int n1 )

Constructor for HashSet, allocates space and initializes set.

N1 is the target number of elements in the table; the table is dimensioned for a load of no more than 0.5.

Definition at line 17 of file HashSet.cpp.

Here is the call graph for this function:

grafalgo::HashSet::~HashSet ( )

Destructor for HashSet.

Definition at line 20 of file HashSet.cpp.

Here is the call graph for this function:

Member Function Documentation

void grafalgo::HashSet::clear ( ) [virtual]

Clear the set contents.

Implements grafalgo::Adt.

Definition at line 69 of file HashSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::HashSet::copyFrom ( const HashSet & source )

Copy into this from source.

Definition at line 74 of file HashSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::HashSet::expand ( int size ) [virtual]

Expand the space available for this HashSet.

Rebuilds old value in new space. This operation changes the index values assigned to each element.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 62 of file HashSet.cpp.

Here is the call graph for this function:

index grafalgo::HashSet::first ( ) const [inline]

Get the index of the first element in the set.

Returns:: the index of the first element in the set; the order of the elements is arbitrary

Definition at line 85 of file HashSet.h.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::HashSet::freeSpace ( ) [private]

Free dynamic storage used by list.

Definition at line 44 of file HashSet.cpp.

Here is the caller graph for this function:

index grafalgo::HashSet::getIndex ( int64_t val ) const

Perform a lookup in the set.

Parameters:

val	is the value to be looked up in the table

Returns:: the index assigned to val or 0 if not in set

Definition at line 109 of file HashSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

uint32_t grafalgo::HashSet::hashit	(	int64_t	val,
		int	hf
	)		const `[private]`

Compute a bucket index for a given val.

Hashit uses multiplicative hashing with one of two different multipliers, after first converting the 64 bit integer into a 32 bit integer.

Parameters:

val	is the value to be hashed
hf	is either 0 or 1 and selects one of two hash functions

Returns:: b return the index of the bucket that val hashes to

Definition at line 92 of file HashSet.cpp.

Here is the caller graph for this function:

index grafalgo::HashSet::insert ( int64_t val )

Insert a value into the set.

If the value is already in the set, no change is made.

Parameters:

val	is the value to insert

Returns:: the index assigned to val on success, 0 on failure.

Definition at line 133 of file HashSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

bool grafalgo::HashSet::isValid ( index x ) const [inline]

Determine if an index corresponds to a set element.

Parameters:

x	is an index

Returns:: true if there is some element with x as its index, else false

Definition at line 97 of file HashSet.h.

Here is the call graph for this function:

void grafalgo::HashSet::makeSpace ( int size ) [private]

Allocate and initialize space for list.

Parameters:

size	is number of index values to provide space for

Definition at line 25 of file HashSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

bool grafalgo::HashSet::member ( int64_t e ) const [inline]

Determine if an element is in the set.

e is an element to be tested for set membership

Returns:: true if e is a member of the set, else false

Definition at line 79 of file HashSet.h.

Here is the call graph for this function:

Here is the caller graph for this function:

index grafalgo::HashSet::next ( index x ) const [inline]

Determine the index of the next element in the set.

Parameters:

x	is an index for a set element

Returns:: the index of the element that follows x in the set

Definition at line 91 of file HashSet.h.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::HashSet::remove ( int64_t val )

Remove a value from the set.

Parameters:

val	is the value of the pair to be removed

Definition at line 170 of file HashSet.cpp.

Here is the call graph for this function:

void grafalgo::HashSet::resize ( int size ) [virtual]

Resize a HashSet object, discarding old contents.

Parameters:

size	is the size of the resized object.

Implements grafalgo::Adt.

Definition at line 49 of file HashSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

int grafalgo::HashSet::size ( ) const [inline]

Determine the number of elements in the set.

Returns:: the number of elements in the set

Definition at line 73 of file HashSet.h.

Here is the call graph for this function:

Here is the caller graph for this function:

string & grafalgo::HashSet::toString ( string & s ) const [virtual]

Create a string representation of the set.

Parameters:

s	is a reference to a string in whcih result is returned

Returns:: a reference to s

Implements grafalgo::Adt.

Definition at line 193 of file HashSet.cpp.

Here is the call graph for this function:

uint64_t grafalgo::HashSet::val ( index x ) const [inline]

Get the value of an element in the set.

Parameters:

x	is an index of a set element

Returns:: the element value

Definition at line 103 of file HashSet.h.

Here is the caller graph for this function:

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

/Users/jst/src/grafalgo/cpp/include/HashSet.h
/Users/jst/src/grafalgo/cpp/dataStructures/hash/HashSet.cpp

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation