Open Graph Drawing Framework  v.2007.11

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

ogdf::Hashing< K, I, H > Class Template Reference

Hashing with chaining and table doubling. More...

#include <Hashing.h>

Inheritance diagram for ogdf::Hashing< K, I, H >:

List of all members.

Public Types
typedef HashConstIterator< K, I, H >	const_terator
	The type of const-iterators for hash tables.
Public Member Functions
	Hashing (int minTableSize=256, const H &hashFunc=H())
	Creates a hash table for given initial table size minTableSize.
	Hashing (const Hashing< K, I > &h)
	Copy constructor.
	~Hashing ()
int	size () const
	Returns the number of elements in the hash table.
bool	empty () const
	Returns true iff the table is empty, i.e., contains no elements.
bool	member (const K &key) const
	Returns true iff the hash table contains an element with key key.
HashConstIterator< K, I, H >	begin () const
	Returns an hash iterator to the first element in the list of all elements.
HashElement< K, I > *	lookup (const K &key) const
	Returns the hash element with key key in the hash table; returns 0 if no such element.
Hashing< K, I > &	operator= (const Hashing< K, I > &hashing)
	Assignment operator.
HashElement< K, I > *	insert (const K &key, const I &info)
	Inserts a new element with key key and information info into the hash table.
HashElement< K, I > *	insertByNeed (const K &key, const I &info)
	Inserts a new element with key key and information info into the hash table.
HashElement< K, I > *	fastInsert (const K &key, const I &info)
	Inserts a new element with key key and information info into the hash table.
void	del (const K &key)
	Removes the element with key key from the hash table (does nothing if no such element).
void	clear ()
	Removes all elements from the hash table.
Protected Member Functions
HashElement< K, I > *	firstElement (HashElement< K, I > ***pList) const
	Returns the first element in the list of all elements in the hash table.
HashElement< K, I > *	nextElement (HashElement< K, I > ***pList, HashElement< K, I > *pElement) const
	Returns the successor of pElement in the list of all elements in the hash table.
Private Member Functions
virtual void	destroy (HashElementBase *pElement)
	Deletes hash element pElement.
virtual HashElementBase *	copy (HashElementBase *pElement) const
	Returns a copy of hash element pElement.
Private Attributes
H	m_hashFunc
	The hash function.
Friends
class	HashConstIterator< K, I, H >

---

Detailed Description

template<class K, class I, class H = DefHashFunc<K>>
class ogdf::Hashing< K, I, H >

Hashing with chaining and table doubling.

The class Hashing<K,I> implements a hashing table which realizes a mapping from a key type K to an information type I.

The class requires three template parameters:

• K is the type of keys.
• I is the type of information.
• H is the hash function type. The hash function type argument is optional; its default uses the class DefHashFunc.

Definition at line 289 of file Hashing.h.

---

Member Typedef Documentation

template<class K, class I, class H = DefHashFunc<K>>

typedef HashConstIterator<K,I,H> ogdf::Hashing< K, I, H >::const_terator

The type of const-iterators for hash tables.

Reimplemented in ogdf::HashArray< I, E, H >, ogdf::HashArray2D< I1_, I2_, E_, Hash1_, Hash2_ >, ogdf::HashArray< int, int >, ogdf::HashArray< int, ogdf::ClusterElement >, ogdf::HashArray< int, ogdf::ClusterInfo >, and ogdf::HashArray2D< int, int, ogdf::List< ogdf::EdgeElement > >.

Definition at line 296 of file Hashing.h.

---

Constructor & Destructor Documentation

template<class K, class I, class H = DefHashFunc<K>>

ogdf::Hashing< K, I, H >::Hashing	(	int	minTableSize = 256,
		const H &	hashFunc = H()
	)			[inline, explicit]

Creates a hash table for given initial table size minTableSize.

Definition at line 299 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>

ogdf::Hashing< K, I, H >::Hashing

(

const Hashing< K, I > &

h

)

[inline]

Copy constructor.

Definition at line 303 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>

ogdf::Hashing< K, I, H >::~Hashing

(

)

[inline]

Definition at line 306 of file Hashing.h.

---

Member Function Documentation

template<class K, class I, class H = DefHashFunc<K>>

int ogdf::Hashing< K, I, H >::size

(

)

const [inline]

Returns the number of elements in the hash table.

Reimplemented from ogdf::HashingBase.

Reimplemented in ogdf::HashArray< I, E, H >, ogdf::HashArray2D< I1_, I2_, E_, Hash1_, Hash2_ >, ogdf::HashArray< int, int >, ogdf::HashArray< int, ogdf::ClusterElement >, ogdf::HashArray< int, ogdf::ClusterInfo >, and ogdf::HashArray2D< int, int, ogdf::List< ogdf::EdgeElement > >.

Definition at line 309 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>

bool ogdf::Hashing< K, I, H >::empty

(

)

const [inline]

Returns true iff the table is empty, i.e., contains no elements.

Reimplemented from ogdf::HashingBase.

Reimplemented in ogdf::HashArray< I, E, H >, ogdf::HashArray2D< I1_, I2_, E_, Hash1_, Hash2_ >, ogdf::HashArray< int, int >, ogdf::HashArray< int, ogdf::ClusterElement >, ogdf::HashArray< int, ogdf::ClusterInfo >, and ogdf::HashArray2D< int, int, ogdf::List< ogdf::EdgeElement > >.

Definition at line 312 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>

bool ogdf::Hashing< K, I, H >::member

(

const K &

key

)

const [inline]

Returns true iff the hash table contains an element with key key.

Definition at line 315 of file Hashing.h.

template<class K, class I, class H>

HashConstIterator< K, I, H > ogdf::Hashing< K, I, H >::begin

(

)

const [inline]

Returns an hash iterator to the first element in the list of all elements.

Reimplemented in ogdf::HashArray< I, E, H >, ogdf::HashArray2D< I1_, I2_, E_, Hash1_, Hash2_ >, ogdf::HashArray< int, int >, ogdf::HashArray< int, ogdf::ClusterElement >, ogdf::HashArray< int, ogdf::ClusterInfo >, and ogdf::HashArray2D< int, int, ogdf::List< ogdf::EdgeElement > >.

Definition at line 515 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>

HashElement<K,I>* ogdf::Hashing< K, I, H >::lookup

(

const K &

key

)

const [inline]

Returns the hash element with key key in the hash table; returns 0 if no such element.

Definition at line 321 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>

Hashing<K,I>& ogdf::Hashing< K, I, H >::operator=

(

const Hashing< K, I > &

hashing

)

[inline]

Assignment operator.

Definition at line 331 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>

HashElement<K,I>* ogdf::Hashing< K, I, H >::insert	(	const K &	key,
		const I &	info
	)			[inline]

Inserts a new element with key key and information info into the hash table.

The new element will only be inserted if no element with key key is already contained; if such an element already exists the information of this element will be changed to info.

Definition at line 344 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>

HashElement<K,I>* ogdf::Hashing< K, I, H >::insertByNeed	(	const K &	key,
		const I &	info
	)			[inline]

Inserts a new element with key key and information info into the hash table.

The new element will only be inserted if no element with key key is already contained; if such an element already exists the information of this element remains unchanged.

Definition at line 363 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>

HashElement<K,I>* ogdf::Hashing< K, I, H >::fastInsert	(	const K &	key,
		const I &	info
	)			[inline]

Inserts a new element with key key and information info into the hash table.

This is a faster version of insert() that assumes that no element with key key is already contained in the hash table.

Definition at line 378 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>

void ogdf::Hashing< K, I, H >::del

(

const K &

key

)

[inline]

Removes the element with key key from the hash table (does nothing if no such element).

Definition at line 385 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>

void ogdf::Hashing< K, I, H >::clear

(

)

[inline]

Removes all elements from the hash table.

Reimplemented from ogdf::HashingBase.

Reimplemented in ogdf::HashArray< I, E, H >, ogdf::HashArray2D< I1_, I2_, E_, Hash1_, Hash2_ >, ogdf::HashArray< int, int >, ogdf::HashArray< int, ogdf::ClusterElement >, ogdf::HashArray< int, ogdf::ClusterInfo >, and ogdf::HashArray2D< int, int, ogdf::List< ogdf::EdgeElement > >.

Definition at line 394 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>

HashElement<K,I>* ogdf::Hashing< K, I, H >::firstElement

(

HashElement< K, I > ***

pList

)

const [inline, protected]

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.

Definition at line 405 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>

HashElement<K,I>* ogdf::Hashing< K, I, H >::nextElement	(	HashElement< K, I > ***	pList,
		HashElement< K, I > *	pElement
	)			const [inline, protected]

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.

Definition at line 418 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>

virtual void ogdf::Hashing< K, I, H >::destroy

(

HashElementBase *

pElement

)

[inline, private, virtual]

Deletes hash element pElement.

Implements ogdf::HashingBase.

Definition at line 427 of file Hashing.h.

template<class K, class I, class H = DefHashFunc<K>>

virtual HashElementBase* ogdf::Hashing< K, I, H >::copy

(

HashElementBase *

pElement

)

const [inline, private, virtual]

Returns a copy of hash element pElement.

Implements ogdf::HashingBase.

Definition at line 432 of file Hashing.h.

---

Friends And Related Function Documentation

template<class K, class I, class H = DefHashFunc<K>>

friend class HashConstIterator< K, I, H > [friend]

Definition at line 291 of file Hashing.h.

---

Member Data Documentation

template<class K, class I, class H = DefHashFunc<K>>

H ogdf::Hashing< K, I, H >::m_hashFunc [private]

The hash function.

Definition at line 292 of file Hashing.h.

---

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

• ogdf/basic/Hashing.h

---