|
|||
|
|
|
|||
|
|
Hashing with chaining and table doubling. More...
#include <ogdf/basic/Hashing.h>
Public Types | |
| typedef HashConstIterator< K, I, H > | const_iterator |
| 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 > |
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 290 of file Hashing.h.
| typedef HashConstIterator<K,I,H> ogdf::Hashing< K, I, H >::const_iterator |
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, ClusterInfo >, ogdf::HashArray< int, cluster >, and ogdf::HashArray2D< int, int, List< edge > >.
| ogdf::Hashing< K, I, H >::Hashing | ( | int | minTableSize = 256, |
|
| const H & | hashFunc = H() | |||
| ) | [inline, explicit] |
| ogdf::Hashing< K, I, H >::Hashing | ( | const Hashing< K, I > & | h | ) | [inline] |
| ogdf::Hashing< K, I, H >::~Hashing | ( | ) | [inline] |
| 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, ClusterInfo >, ogdf::HashArray< int, cluster >, and ogdf::HashArray2D< int, int, List< edge > >.
| 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, ClusterInfo >, ogdf::HashArray< int, cluster >, and ogdf::HashArray2D< int, int, List< edge > >.
| virtual HashElementBase* ogdf::Hashing< K, I, H >::copy | ( | HashElementBase * | pElement | ) | const [inline, private, virtual] |
Returns a copy of hash element pElement.
Implements ogdf::HashingBase.
| void ogdf::Hashing< K, I, H >::del | ( | const K & | key | ) | [inline] |
| virtual void ogdf::Hashing< K, I, H >::destroy | ( | HashElementBase * | pElement | ) | [inline, private, virtual] |
Deletes hash element pElement.
Implements ogdf::HashingBase.
| 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, ClusterInfo >, ogdf::HashArray< int, cluster >, and ogdf::HashArray2D< int, int, List< edge > >.
| HashElement<K,I>* ogdf::Hashing< K, I, H >::fastInsert | ( | const K & | key, | |
| const I & | info | |||
| ) | [inline] |
| 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.
| pList | is assigned the list containing the first element. |
| HashElement<K,I>* ogdf::Hashing< K, I, H >::insert | ( | const K & | key, | |
| const I & | info | |||
| ) | [inline] |
| HashElement<K,I>* ogdf::Hashing< K, I, H >::insertByNeed | ( | const K & | key, | |
| const I & | info | |||
| ) | [inline] |
| HashElement<K,I>* ogdf::Hashing< K, I, H >::lookup | ( | const K & | key | ) | const [inline] |
| bool ogdf::Hashing< K, I, H >::member | ( | const K & | key | ) | const [inline] |
| 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.
| pList | is assigned the list containing the first element. | |
| pElement | points to an element in the has table. |
| Hashing<K,I>& ogdf::Hashing< K, I, H >::operator= | ( | const Hashing< K, I > & | hashing | ) | [inline] |
| 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, ClusterInfo >, ogdf::HashArray< int, cluster >, and ogdf::HashArray2D< int, int, List< edge > >.
friend class HashConstIterator< K, I, H > [friend] |
H ogdf::Hashing< K, I, H >::m_hashFunc [private] |
