110 int size()
const {
return m_count; }
113 int empty()
const {
return m_count == 0; }
121 return *(m_table + (hashValue & m_hashMask));
175template<
class K,
class I>
201template<
class K,
class I,
class H>
202class HashConstIterator;
223 size_t hash(
const void*& key)
const {
return size_t(key && 0xffffffff); }
230 size_t hash(
const double& key)
const {
232 return (
size_t)((
double)std::numeric_limits<size_t>::max() *
frexp(key, &dummy));
240 size_t hash(
const string& key)
const;
260template<
class K,
class I,
class H = DefHashFunc<K>>
428template<
class K,
class I,
class H = DefHashFunc<K>>
467 return it1.m_pElement ==
it2.m_pElement;
473 return it1.m_pElement !=
it2.m_pElement;
483template<
class K,
class I,
class H>
Basic declarations, included by all source files.
size_t hash(const double &key) const
size_t hash(const string &key) const
size_t hash(const void *&key) const
size_t hash(const K &key) const
Returns the hash value of key.
Iterators for hash tables.
HashConstIterator(const HashConstIterator< K, I, H > &it)
Copy constructor.
HashConstIterator< K, I, H > & operator++()
Moves this hash iterator to the next element (iterator gets invalid if no more elements).
HashConstIterator & operator=(const HashConstIterator< K, I, H > &it)
Assignment operator.
bool valid() const
Returns true if the hash iterator points to an element.
HashConstIterator()
Creates a hash iterator pointing to no element.
const K & key() const
Returns the key of the hash element pointed to.
HashElement< K, I > * m_pElement
The hash element to which the iterator points.
friend bool operator==(const HashConstIterator< K, I, H > &it1, const HashConstIterator< K, I, H > &it2)
Equality operator.
HashElement< K, I > ** m_pList
The list containg the hash element.
const I & info() const
Returns the information of the hash element pointed to.
friend bool operator!=(const HashConstIterator< K, I, H > &it1, const HashConstIterator< K, I, H > &it2)
Inequality operator.
const Hashing< K, I, H > * m_pHashing
The associated hash table.
HashConstIterator(HashElement< K, I > *pElement, HashElement< K, I > **pList, const Hashing< K, I, H > *pHashing)
Creates a hash iterator pointing to element pElement in list pList of hash table pHashing.
Base class for elements within a hash table.
size_t m_hashValue
The hash value.
size_t hashValue() const
Returns the hash value of this element.
HashElementBase(size_t hashValue)
Creates a hash element with hash value hashValue.
HashElementBase * next() const
Returns the successor to this element in the list.
HashElementBase * m_next
The successor in the list.
Representation of elements in a hash table.
HashElement< K, I > * next() const
Returns the successor element in the list.
const K & key() const
Returns the key value.
HashElement(size_t hashValue, const K &key, const I &info)
Creates a hash element with given hash value, key, and information.
const I & info() const
Returns the information value.
I & info()
Returns a refeence to the information value.
I m_info
The information value.
Base class for hashing with chaining and table doubling.
void init(int tableSize)
Initializes the table for given table size.
HashElementBase ** m_table
The hash table (an array of lists).
void del(HashElementBase *pElement)
Removes the element pElement from the hash table.
virtual ~HashingBase()
Destruction.
HashElementBase * nextElement(HashElementBase ***pList, HashElementBase *pElement) const
Returns the successor of pElement in the list of all elements in the hash table.
HashingBase & operator=(const HashingBase &H)
Assignment operator.
HashElementBase * firstElement(HashElementBase ***pList) const
Returns the first element in the list of all elements in the hash table.
int m_tableSizeHigh
The maximal number of elements at this table size.
HashingBase(int minTableSize)
Creates a hash table with minimum table size minTableSize.
int m_count
The current number of elements.
void clear()
Removes all elements from the hash table.
void resize(int newTableSize)
Resizes the hash table to newTableSize.
int m_minTableSize
The minimal table size.
virtual void destroy(HashElementBase *pElement)=0
Called to delete hash element.
int size() const
Returns the number of elements in the hash table.
virtual HashElementBase * copy(HashElementBase *pElement) const =0
Called to create a copy of the element pElement.
int m_tableSize
The current table size.
int m_tableSizeLow
The minimal number of elements at this table size.
HashingBase(const HashingBase &H)
Copy constructor.
void insert(HashElementBase *pElement)
Inserts a new element pElement into the hash table.
int m_hashMask
The current table size minus one.
void copyAll(const HashingBase &H)
Copies all elements from H to this hash table.
void destroyAll()
Deletes all elements in hash table (but does not free m_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.
Hashing with chaining and table doubling.
HashElement< K, I > * insert(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).
Hashing(int minTableSize=256, const H &hashFunc=H())
Creates a hash table for given initial table size minTableSize.
Hashing(const Hashing< K, I, H > &h)=default
Copy constructor.
virtual void destroy(HashElementBase *pElement) override
Deletes hash element pElement.
virtual HashElementBase * copy(HashElementBase *pElement) const override
Returns a copy of hash element pElement.
HashConstIterator< K, I, H > begin() const
Returns an hash iterator to the first element in the list of all elements.
void clear()
Removes all elements from 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.
bool empty() const
Returns true iff the table is empty, i.e., contains no elements.
H m_hashFunc
The hash function.
Hashing< K, I, H > & operator=(const Hashing< K, I, H > &hashing)=default
Assignment operator.
HashElement< K, I > * insertByNeed(const K &key, const I &info)
Inserts a new element with key key and information info into the hash table.
int size() const
Returns the number of elements in the hash table.
bool member(const K &key) const
Returns true iff the hash table contains an element with key key.
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 > * lookup(const K &key) const
Returns the hash element with key key in the hash table; returns nullptr if no such element exists.
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.
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Declaration of memory manager for allocating small pieces of memory.
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.