Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
hash.h
Go to the documentation of this file.
1
30#pragma once
31
33
34namespace abacus {
35
36class AbacusGlobal;
37
38template<class KeyType,class ItemType> class AbaHash;
39
40template <class KeyType, class ItemType>
41class AbaHashItem;
42template <class KeyType, class ItemType>
43class AbaHash;
44
45template <class KeyType, class ItemType>
46std::ostream &operator<< (std::ostream &out, const AbaHashItem<KeyType, ItemType> &rhs);
47
48template <class KeyType, class ItemType>
49std::ostream &operator<< (std::ostream &out, const AbaHash<KeyType, ItemType> &hash);
50
51
53/*
54 * \sa AbaHash
55 */
56template <class KeyType, class ItemType>
57class AbaHashItem : public AbacusRoot {
58 friend class AbaHash<KeyType, ItemType>;
59
60public:
61
63
67 AbaHashItem(const KeyType &key, const ItemType &item);
68
69
71
74 friend std::ostream &operator<< <> (std::ostream &,
76
79
82
83private:
87
89};
90
91
93
123template <class KeyType, class ItemType>
124class AbaHash : public AbacusRoot {
125public:
126
128
131 explicit AbaHash(int size);
132
134
138
140
151 friend std::ostream &operator<< <> (std::ostream &out,
152 const AbaHash<KeyType, ItemType> &hash);
153
155
163 void insert(const KeyType &newKey, const ItemType &newItem);
164
166
174
176
184 const ItemType *find(const KeyType &key) const;
185
187
195 ItemType *find(const KeyType &key);
196
198
204 bool find(const KeyType &key, const ItemType &item) const;
205
211
213
220
222
228 const ItemType *initializeIteration(const KeyType &key) const;
229
231
243 ItemType *next(const KeyType &key);
244
246
258 const ItemType *next(const KeyType &key) const;
260
262
268 int remove(const KeyType &key);
269
271
278 int remove(const KeyType &key, const ItemType &item);
279
281 int size() const;
282
284 int nCollisions() const;
285
287
290 void resize(int newSize);
291
292 private:
293
295
301 int hf(int key) const;
302
304 int hf(unsigned key) const;
305
307
310 int hf(const string &str) const;
311
312
314
320
322 int size_;
323
326
328
333
334 AbaHash(const AbaHash &rhs);
336};
337
338}
339
Hash tables.
Definition hash.h:124
int nCollisions_
The number of collisions on calls of insert() and overWrite().
Definition hash.h:325
bool find(const KeyType &key, const ItemType &item) const
Checks if a prespecified item with a prespecified key is contained in the hash table.
int remove(const KeyType &key)
Removes the first item with a given key from the hash table.
int size_
The length of the hash table.
Definition hash.h:322
int hf(unsigned key) const
This version of hf() implements a Fibonacci hash function for keys of type unsigned.
AbaHashItem< KeyType, ItemType > ** table_
The hash table storing a linked list of hash items in each slot.
Definition hash.h:319
int nCollisions() const
Returns the number of collisions which occurred during all previous calls of the functions insert() a...
ItemType * find(const KeyType &key)
Looks for an item in the hash table with a given key.
const ItemType * find(const KeyType &key) const
Looks for an item in the hash table with a given key.
const ItemType * next(const KeyType &key) const
This function can be used to go to the next item in the hash table with key key.
const ItemType * initializeIteration(const KeyType &key) const
This function retrieves the first item.
void insert(const KeyType &newKey, const ItemType &newItem)
Adds an item to the hash table.
ItemType * initializeIteration(const KeyType &key)
This function retrieves the first item.
AbaHash(const AbaHash &rhs)
AbaHash(int size)
Initializes each slot with a 0-pointer to indicate that the linked list of hash items of this slot is...
int hf(const string &str) const
This is a hash function for character strings.
int remove(const KeyType &key, const ItemType &item)
Removes the first item with a given key and a prespecified element from the hash table.
AbaHash & operator=(const AbaHash &rhs)
int hf(int key) const
Computes the hash value of key.
ItemType * next(const KeyType &key)
This function can be used to go to the next item in the hash table with key key.
AbaHashItem< KeyType, ItemType > * iter_
An iterator for all items stored in a slot.
Definition hash.h:332
void overWrite(const KeyType &newKey, const ItemType &newItem)
Adds a item to the has table (with overwrite).
int size() const
Returns the length of the hash table.
void resize(int newSize)
Can be used to change the size of the hash table.
~AbaHash()
The destructor.
Items in hash tables.
Definition hash.h:57
ItemType item_
Definition hash.h:85
KeyType key_
Definition hash.h:84
AbaHashItem< KeyType, ItemType > * next_
Definition hash.h:86
AbaHashItem(const KeyType &key, const ItemType &item)
The constructor.
const AbaHashItem< KeyType, ItemType > * next() const
Returns a const pointer to the next hash-item stored in the linked list corresponding to the slot of ...
AbaHashItem< KeyType, ItemType > * next()
Returns a pointer to the next hash-item stored in the linked list corresponding to the slot of this i...
Base class of all other classes of ABACUS.
Definition abacusroot.h:68
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition memory.h:84
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
std::ostream & operator<<(std::ostream &out, const Active< BaseType, CoType > &rhs)