Open
Graph Drawing
Framework

  v.2010.10
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

Public Member Functions | Protected Member Functions | Protected Attributes | Private Member Functions

ogdf::HashingBase Class Reference

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

#include <ogdf/basic/Hashing.h>

Inheritance diagram for ogdf::HashingBase:
ogdf::Hashing< I, E, H > ogdf::Hashing< Tuple2< I1_, I2_ >, E_, HashFuncTuple< I1_, I2_, Hash1_, Hash2_ > > ogdf::Hashing< K, I, H > ogdf::HashArray< I, E, H > ogdf::HashArray2D< I1_, I2_, E_, Hash1_, Hash2_ >

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 (size_t 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 104 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::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, ClusterInfo >, ogdf::HashArray< int, cluster >, ogdf::HashArray2D< int, int, List< edge > >, ogdf::Hashing< int, String >, ogdf::Hashing< int, cluster, DefHashFunc< int > >, ogdf::Hashing< String, int >, ogdf::Hashing< I, E, H >, ogdf::Hashing< Tuple2< int, int >, List< edge >, HashFuncTuple< int, int, DefHashFunc< int >, DefHashFunc< int > > >, ogdf::Hashing< String, cluster >, ogdf::Hashing< Tuple2< I1_, I2_ >, E_, HashFuncTuple< I1_, I2_, Hash1_, Hash2_ > >, ogdf::Hashing< String, DPoint >, ogdf::Hashing< String, OgmlNodeTemplate * >, ogdf::Hashing< int, int, DefHashFunc< int > >, ogdf::Hashing< int, OgmlTag >, ogdf::Hashing< int, ClusterInfo, DefHashFunc< int > >, ogdf::Hashing< int, NodeElement * >, ogdf::Hashing< int, EdgeElement * >, ogdf::Hashing< String, node >, ogdf::Hashing< String, const XmlTagObject * >, ogdf::Hashing< String, edge >, ogdf::Hashing< String, OgmlEdgeTemplate * >, ogdf::Hashing< int, OgmlAttributeValue >, and ogdf::Hashing< int, OgmlAttribute >.

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< int, String >, ogdf::Hashing< int, cluster, DefHashFunc< int > >, ogdf::Hashing< String, int >, ogdf::Hashing< I, E, H >, ogdf::Hashing< Tuple2< int, int >, List< edge >, HashFuncTuple< int, int, DefHashFunc< int >, DefHashFunc< int > > >, ogdf::Hashing< String, cluster >, ogdf::Hashing< Tuple2< I1_, I2_ >, E_, HashFuncTuple< I1_, I2_, Hash1_, Hash2_ > >, ogdf::Hashing< String, DPoint >, ogdf::Hashing< String, OgmlNodeTemplate * >, ogdf::Hashing< int, int, DefHashFunc< int > >, ogdf::Hashing< int, OgmlTag >, ogdf::Hashing< int, ClusterInfo, DefHashFunc< int > >, ogdf::Hashing< int, NodeElement * >, ogdf::Hashing< int, EdgeElement * >, ogdf::Hashing< String, node >, ogdf::Hashing< String, const XmlTagObject * >, ogdf::Hashing< String, edge >, ogdf::Hashing< String, OgmlEdgeTemplate * >, ogdf::Hashing< int, OgmlAttributeValue >, and ogdf::Hashing< int, OgmlAttribute >.

void ogdf::HashingBase::copyAll ( const HashingBase &  H  )  [private]

Copies all elements from H to this hash table.

void ogdf::HashingBase::del ( HashElementBase *  pElement  ) 

Removes the element pElement from the hash 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< int, String >, ogdf::Hashing< int, cluster, DefHashFunc< int > >, ogdf::Hashing< String, int >, ogdf::Hashing< I, E, H >, ogdf::Hashing< Tuple2< int, int >, List< edge >, HashFuncTuple< int, int, DefHashFunc< int >, DefHashFunc< int > > >, ogdf::Hashing< String, cluster >, ogdf::Hashing< Tuple2< I1_, I2_ >, E_, HashFuncTuple< I1_, I2_, Hash1_, Hash2_ > >, ogdf::Hashing< String, DPoint >, ogdf::Hashing< String, OgmlNodeTemplate * >, ogdf::Hashing< int, int, DefHashFunc< int > >, ogdf::Hashing< int, OgmlTag >, ogdf::Hashing< int, ClusterInfo, DefHashFunc< int > >, ogdf::Hashing< int, NodeElement * >, ogdf::Hashing< int, EdgeElement * >, ogdf::Hashing< String, node >, ogdf::Hashing< String, const XmlTagObject * >, ogdf::Hashing< String, edge >, ogdf::Hashing< String, OgmlEdgeTemplate * >, ogdf::Hashing< int, OgmlAttributeValue >, and ogdf::Hashing< int, OgmlAttribute >.

void ogdf::HashingBase::destroyAll (  )  [protected]

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

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, ClusterInfo >, ogdf::HashArray< int, cluster >, ogdf::HashArray2D< int, int, List< edge > >, ogdf::Hashing< int, String >, ogdf::Hashing< int, cluster, DefHashFunc< int > >, ogdf::Hashing< String, int >, ogdf::Hashing< I, E, H >, ogdf::Hashing< Tuple2< int, int >, List< edge >, HashFuncTuple< int, int, DefHashFunc< int >, DefHashFunc< int > > >, ogdf::Hashing< String, cluster >, ogdf::Hashing< Tuple2< I1_, I2_ >, E_, HashFuncTuple< I1_, I2_, Hash1_, Hash2_ > >, ogdf::Hashing< String, DPoint >, ogdf::Hashing< String, OgmlNodeTemplate * >, ogdf::Hashing< int, int, DefHashFunc< int > >, ogdf::Hashing< int, OgmlTag >, ogdf::Hashing< int, ClusterInfo, DefHashFunc< int > >, ogdf::Hashing< int, NodeElement * >, ogdf::Hashing< int, EdgeElement * >, ogdf::Hashing< String, node >, ogdf::Hashing< String, const XmlTagObject * >, ogdf::Hashing< String, edge >, ogdf::Hashing< String, OgmlEdgeTemplate * >, ogdf::Hashing< int, OgmlAttributeValue >, and ogdf::Hashing< int, OgmlAttribute >.

Definition at line 143 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::firstListElement ( size_t  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 150 of file Hashing.h.

void ogdf::HashingBase::init ( int  tableSize  )  [private]

Initializes the table for given table size.

void ogdf::HashingBase::insert ( HashElementBase *  pElement  ) 

Inserts a new element pElement into the hash table.

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.
HashingBase& ogdf::HashingBase::operator= ( const HashingBase &  H  ) 

Assignment operator.

void ogdf::HashingBase::resize ( int  newTableSize  ) 

Resizes the hash table to newTableSize.

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, ClusterInfo >, ogdf::HashArray< int, cluster >, ogdf::HashArray2D< int, int, List< edge > >, ogdf::Hashing< int, String >, ogdf::Hashing< int, cluster, DefHashFunc< int > >, ogdf::Hashing< String, int >, ogdf::Hashing< I, E, H >, ogdf::Hashing< Tuple2< int, int >, List< edge >, HashFuncTuple< int, int, DefHashFunc< int >, DefHashFunc< int > > >, ogdf::Hashing< String, cluster >, ogdf::Hashing< Tuple2< I1_, I2_ >, E_, HashFuncTuple< I1_, I2_, Hash1_, Hash2_ > >, ogdf::Hashing< String, DPoint >, ogdf::Hashing< String, OgmlNodeTemplate * >, ogdf::Hashing< int, int, DefHashFunc< int > >, ogdf::Hashing< int, OgmlTag >, ogdf::Hashing< int, ClusterInfo, DefHashFunc< int > >, ogdf::Hashing< int, NodeElement * >, ogdf::Hashing< int, EdgeElement * >, ogdf::Hashing< String, node >, ogdf::Hashing< String, const XmlTagObject * >, ogdf::Hashing< String, edge >, ogdf::Hashing< String, OgmlEdgeTemplate * >, ogdf::Hashing< int, OgmlAttributeValue >, and ogdf::Hashing< int, OgmlAttribute >.

Definition at line 140 of file Hashing.h.

Member Data Documentation

int ogdf::HashingBase::m_count [protected]

The current number of elements.

Definition at line 111 of file Hashing.h.

int ogdf::HashingBase::m_hashMask [protected]

The current table size minus one.

Definition at line 107 of file Hashing.h.

int ogdf::HashingBase::m_minTableSize [protected]

The minimal table size.

Definition at line 108 of file Hashing.h.

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

The hash table (an array of lists).

Definition at line 112 of file Hashing.h.

int ogdf::HashingBase::m_tableSize [protected]

The current table size.

Definition at line 106 of file Hashing.h.

int ogdf::HashingBase::m_tableSizeHigh [protected]

The maximal number of elements at this table size.

Definition at line 110 of file Hashing.h.

int ogdf::HashingBase::m_tableSizeLow [protected]

The minimal number of elements at this table size.

Definition at line 109 of file Hashing.h.

The documentation for this class was generated from the following file:
© 1999-2010 by oreas GmbH, © 2005-2010 by Technische Universität Dortmund, University of Jena and University of Cologne.

Generated on Wed Oct 20 2010 11:14:13 by doxygen 1.7.1.