Open Graph Drawing Framework  v.2007.11

Overview Class Hierarchy Class Index Class List Members Namespaces Source Files Search for:

ogdf::HashingBase Class Reference

Base class for hashing with chaining and table doubling. More...

#include <Hashing.h>

Inheritance diagram for ogdf::HashingBase:

List of all members.

Public Member Functions
	HashingBase (int minTableSize)
	Creates a hash table with minimum table size minTableSize.
	HashingBase (const HashingBase &H)
	Copy constructor.
virtual	~HashingBase ()
void	resize (int newTableSize)
	Resizes the hash table to newTableSize.
void	insert (HashElementBase *pElement)
	Inserts a new element pElement into the hash table.
void	del (HashElementBase *pElement)
	Removes the element pElement from the hash table.
void	clear ()
	Removes all elements from the hash table.
HashingBase &	operator= (const HashingBase &H)
	Assignment operator.
int	size () const
	Returns the number of elements in the hash table.
int	empty () const
	Returns if the hash table is empty.
HashElementBase *	firstListElement (int hashValue) const
	Returns the first element in the list for elements with hash value hashValue.
HashElementBase *	firstElement (HashElementBase ***pList) const
	Returns the first element in the list of all elements in the hash table.
HashElementBase *	nextElement (HashElementBase ***pList, HashElementBase *pElement) const
	Returns the successor of pElement in the list of all elements in the hash table.
Protected Member Functions
void	destroyAll ()
	Deletes all elements in hash table (but does not free m_table!).
virtual void	destroy (HashElementBase *pElement)=0
	Called to delete hash element.
virtual HashElementBase *	copy (HashElementBase *pElement) const =0
	Called to create a copy of the element pElement.
Protected Attributes
int	m_tableSize
	The current table size.
int	m_hashMask
	The current table size minus one.
int	m_minTableSize
	The minimal table size.
int	m_tableSizeLow
	The minimal number of elements at this table size.
int	m_tableSizeHigh
	The maximal number of elements at this table size.
int	m_count
	The current number of elements.
HashElementBase **	m_table
	The hash table (an array of lists).
Private Member Functions
void	init (int tableSize)
	Initializes the table for given table size.
void	copyAll (const HashingBase &H)
	Copies all elements from H to this hash table.

---

Detailed Description

Base class for hashing with chaining and table doubling.

The actual hashing is provided by the parameterized class Hashing<K,I> which derives from HashingBase.

Definition at line 103 of file Hashing.h.

---

Constructor & Destructor Documentation

ogdf::HashingBase::HashingBase

(

int

minTableSize

)

Creates a hash table with minimum table size minTableSize.

ogdf::HashingBase::HashingBase

(

const HashingBase &

H

)

Copy constructor.

virtual ogdf::HashingBase::~HashingBase

(

)

[virtual]

---

Member Function Documentation

void ogdf::HashingBase::resize

(

int

newTableSize

)

Resizes the hash table to newTableSize.

void ogdf::HashingBase::insert

(

HashElementBase *

pElement

)

Inserts a new element pElement into the hash table.

void ogdf::HashingBase::del

(

HashElementBase *

pElement

)

Removes the element pElement from the hash table.

void ogdf::HashingBase::clear

(

)

Removes all elements from the hash table.

Reimplemented in ogdf::HashArray< I, E, H >, ogdf::HashArray2D< I1_, I2_, E_, Hash1_, Hash2_ >, ogdf::Hashing< K, I, H >, ogdf::HashArray< int, int >, ogdf::HashArray< int, ogdf::ClusterElement >, ogdf::HashArray< int, ogdf::ClusterInfo >, ogdf::HashArray2D< int, int, ogdf::List< ogdf::EdgeElement > >, ogdf::Hashing< ogdf::Tuple2< I1_, I2_ >, E_, ogdf::HashFuncTuple< I1_, I2_, Hash1_, Hash2_ > >, ogdf::Hashing< int, ogdf::ClusterInfo, ogdf::DefHashFunc< int > >, ogdf::Hashing< I, E, H >, ogdf::Hashing< int, ogdf::NodeElement * >, ogdf::Hashing< int, int, ogdf::DefHashFunc< int > >, ogdf::Hashing< ogdf::Tuple2< int, int >, ogdf::List< ogdf::EdgeElement >, ogdf::HashFuncTuple< int, int, ogdf::DefHashFunc< int >, ogdf::DefHashFunc< int > > >, ogdf::Hashing< ogdf::String, int >, ogdf::Hashing< int, ogdf::ClusterElement, ogdf::DefHashFunc< int > >, and ogdf::Hashing< int, ogdf::EdgeElement * >.

HashingBase& ogdf::HashingBase::operator=

(

const HashingBase &

H

)

Assignment operator.

int ogdf::HashingBase::size

(

)

const [inline]

Returns the number of elements in the hash table.

Reimplemented in ogdf::HashArray< I, E, H >, ogdf::HashArray2D< I1_, I2_, E_, Hash1_, Hash2_ >, ogdf::Hashing< K, I, H >, ogdf::HashArray< int, int >, ogdf::HashArray< int, ogdf::ClusterElement >, ogdf::HashArray< int, ogdf::ClusterInfo >, ogdf::HashArray2D< int, int, ogdf::List< ogdf::EdgeElement > >, ogdf::Hashing< ogdf::Tuple2< I1_, I2_ >, E_, ogdf::HashFuncTuple< I1_, I2_, Hash1_, Hash2_ > >, ogdf::Hashing< int, ogdf::ClusterInfo, ogdf::DefHashFunc< int > >, ogdf::Hashing< I, E, H >, ogdf::Hashing< int, ogdf::NodeElement * >, ogdf::Hashing< int, int, ogdf::DefHashFunc< int > >, ogdf::Hashing< ogdf::Tuple2< int, int >, ogdf::List< ogdf::EdgeElement >, ogdf::HashFuncTuple< int, int, ogdf::DefHashFunc< int >, ogdf::DefHashFunc< int > > >, ogdf::Hashing< ogdf::String, int >, ogdf::Hashing< int, ogdf::ClusterElement, ogdf::DefHashFunc< int > >, and ogdf::Hashing< int, ogdf::EdgeElement * >.

Definition at line 139 of file Hashing.h.

int ogdf::HashingBase::empty

(

)

const [inline]

Returns if the hash table is empty.

Reimplemented in ogdf::HashArray< I, E, H >, ogdf::HashArray2D< I1_, I2_, E_, Hash1_, Hash2_ >, ogdf::Hashing< K, I, H >, ogdf::HashArray< int, int >, ogdf::HashArray< int, ogdf::ClusterElement >, ogdf::HashArray< int, ogdf::ClusterInfo >, ogdf::HashArray2D< int, int, ogdf::List< ogdf::EdgeElement > >, ogdf::Hashing< ogdf::Tuple2< I1_, I2_ >, E_, ogdf::HashFuncTuple< I1_, I2_, Hash1_, Hash2_ > >, ogdf::Hashing< int, ogdf::ClusterInfo, ogdf::DefHashFunc< int > >, ogdf::Hashing< I, E, H >, ogdf::Hashing< int, ogdf::NodeElement * >, ogdf::Hashing< int, int, ogdf::DefHashFunc< int > >, ogdf::Hashing< ogdf::Tuple2< int, int >, ogdf::List< ogdf::EdgeElement >, ogdf::HashFuncTuple< int, int, ogdf::DefHashFunc< int >, ogdf::DefHashFunc< int > > >, ogdf::Hashing< ogdf::String, int >, ogdf::Hashing< int, ogdf::ClusterElement, ogdf::DefHashFunc< int > >, and ogdf::Hashing< int, ogdf::EdgeElement * >.

Definition at line 142 of file Hashing.h.

HashElementBase* ogdf::HashingBase::firstListElement

(

int

hashValue

)

const [inline]

Returns the first element in the list for elements with hash value hashValue.

This is the list m_table[hashValue & m_hashMask].

Definition at line 149 of file Hashing.h.

HashElementBase* ogdf::HashingBase::firstElement

(

HashElementBase ***

pList

)

const

Returns the first element in the list of all elements in the hash table.

This function is used by hash iterators for iterating over all elements in the hash table.

Parameters:

pList

is assigned the list containing the first element.

Returns:

a pointer to the first element or 0 if hash table is empty.

HashElementBase* ogdf::HashingBase::nextElement	(	HashElementBase ***	pList,
		HashElementBase *	pElement
	)			const

Returns the successor of pElement in the list of all elements in the hash table.

This function is used by hash iterators for iterating over all elements in the hash table.

Parameters:

	pList	is assigned the list containing the first element.
	pElement	points to an element in the has table.

Returns:

a pointer to the first element or 0 if hash table is empty.

void ogdf::HashingBase::destroyAll

(

)

[protected]

Deletes all elements in hash table (but does not free m_table!).

virtual void ogdf::HashingBase::destroy

(

HashElementBase *

pElement

)

[protected, pure virtual]

Called to delete hash element.

This must be done in Hashing<K,I> since only this class knows the actual element type; alternatively, HashElementBase could have a virtual destructor.

Implemented in ogdf::Hashing< K, I, H >, ogdf::Hashing< ogdf::Tuple2< I1_, I2_ >, E_, ogdf::HashFuncTuple< I1_, I2_, Hash1_, Hash2_ > >, ogdf::Hashing< int, ogdf::ClusterInfo, ogdf::DefHashFunc< int > >, ogdf::Hashing< I, E, H >, ogdf::Hashing< int, ogdf::NodeElement * >, ogdf::Hashing< int, int, ogdf::DefHashFunc< int > >, ogdf::Hashing< ogdf::Tuple2< int, int >, ogdf::List< ogdf::EdgeElement >, ogdf::HashFuncTuple< int, int, ogdf::DefHashFunc< int >, ogdf::DefHashFunc< int > > >, ogdf::Hashing< ogdf::String, int >, ogdf::Hashing< int, ogdf::ClusterElement, ogdf::DefHashFunc< int > >, and ogdf::Hashing< int, ogdf::EdgeElement * >.

virtual HashElementBase* ogdf::HashingBase::copy

(

HashElementBase *

pElement

)

const [protected, pure virtual]

Called to create a copy of the element pElement.

Implemented in ogdf::Hashing< K, I, H >, ogdf::Hashing< ogdf::Tuple2< I1_, I2_ >, E_, ogdf::HashFuncTuple< I1_, I2_, Hash1_, Hash2_ > >, ogdf::Hashing< int, ogdf::ClusterInfo, ogdf::DefHashFunc< int > >, ogdf::Hashing< I, E, H >, ogdf::Hashing< int, ogdf::NodeElement * >, ogdf::Hashing< int, int, ogdf::DefHashFunc< int > >, ogdf::Hashing< ogdf::Tuple2< int, int >, ogdf::List< ogdf::EdgeElement >, ogdf::HashFuncTuple< int, int, ogdf::DefHashFunc< int >, ogdf::DefHashFunc< int > > >, ogdf::Hashing< ogdf::String, int >, ogdf::Hashing< int, ogdf::ClusterElement, ogdf::DefHashFunc< int > >, and ogdf::Hashing< int, ogdf::EdgeElement * >.

void ogdf::HashingBase::init

(

int

tableSize

)

[private]

Initializes the table for given table size.

void ogdf::HashingBase::copyAll

(

const HashingBase &

H

)

[private]

Copies all elements from H to this hash table.

---

Member Data Documentation

int ogdf::HashingBase::m_tableSize [protected]

The current table size.

Definition at line 105 of file Hashing.h.

int ogdf::HashingBase::m_hashMask [protected]

The current table size minus one.

Definition at line 106 of file Hashing.h.

int ogdf::HashingBase::m_minTableSize [protected]

The minimal table size.

Definition at line 107 of file Hashing.h.

int ogdf::HashingBase::m_tableSizeLow [protected]

The minimal number of elements at this table size.

Definition at line 108 of file Hashing.h.

int ogdf::HashingBase::m_tableSizeHigh [protected]

The maximal number of elements at this table size.

Definition at line 109 of file Hashing.h.

int ogdf::HashingBase::m_count [protected]

The current number of elements.

Definition at line 110 of file Hashing.h.

HashElementBase** ogdf::HashingBase::m_table [protected]

The hash table (an array of lists).

Definition at line 111 of file Hashing.h.

---

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

• ogdf/basic/Hashing.h

---