Open
Graph Drawing
Framework

 v.2007.11
 

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 >:

ogdf::HashingBase ogdf::HashArray2D< I1_, I2_, E_, Hash1_, Hash2_ >

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 HashElementBasecopy (HashElementBase *pElement) const
 Returns a copy of hash element pElement.

Private Attributes

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:

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:

© 1999-2007 by oreas GmbH, © 2005-2007 by University Dortmund and University Cologne.

Generated on Thu Nov 22 19:40:08 2007 by doxygen 1.5.4.