Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

hash.h
Go to the documentation of this file.
1 
30 #pragma once
31 
33 
34 namespace abacus {
35 
36 class AbacusGlobal;
37 
38 template<class KeyType,class ItemType> class AbaHash;
39 
40 template <class KeyType, class ItemType>
42 template <class KeyType, class ItemType>
43 class AbaHash;
44 
45 template <class KeyType, class ItemType>
46 std::ostream &operator<< (std::ostream &out, const AbaHashItem<KeyType, ItemType> &rhs);
47 
48 template <class KeyType, class ItemType>
49 std::ostream &operator<< (std::ostream &out, const AbaHash<KeyType, ItemType> &hash);
50 
51 
53 /*
54  * \sa AbaHash
55  */
56 template <class KeyType, class ItemType>
57 class AbaHashItem : public AbacusRoot {
58  friend class AbaHash<KeyType, ItemType>;
59 
60 public:
61 
63 
67  AbaHashItem(const KeyType &key, const ItemType &item);
68 
69 
71 
74  friend std::ostream &operator<< <> (std::ostream &,
76 
79 
81  const AbaHashItem<KeyType, ItemType> *next() const;
82 
83 private:
84  KeyType key_;
85  ItemType item_;
87 
89 };
90 
91 
93 
123 template <class KeyType, class ItemType>
124 class AbaHash : public AbacusRoot {
125 public:
126 
128 
131  explicit AbaHash(int size);
132 
134 
137  ~AbaHash();
138 
140 
151  friend std::ostream &operator<< <> (std::ostream &out,
153 
155 
163  void insert(const KeyType &newKey, const ItemType &newItem);
164 
166 
173  void overWrite(const KeyType &newKey, const ItemType &newItem);
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 
219  ItemType *initializeIteration(const KeyType &key);
220 
222 
228  const ItemType *initializeIteration(const KeyType &key) const;
229 
231 
243  ItemType *next(const KeyType &key);
245 
247 
259  const ItemType *next(const KeyType &key) const;
261 
263 
269  int remove(const KeyType &key);
270 
272 
279  int remove(const KeyType &key, const ItemType &item);
280 
282  int size() const;
283 
285  int nCollisions() const;
286 
288 
291  void resize(int newSize);
292 
293  private:
294 
296 
302  int hf(int key) const;
303 
305  int hf(unsigned key) const;
306 
308 
311  int hf(const string &str) const;
312 
313 
315 
321 
323  int size_;
324 
327 
329 
334 
335  AbaHash(const AbaHash &rhs);
336  AbaHash &operator=(const AbaHash &rhs);
337 };
338 
339 }
340 
341 #include <ogdf/lib/abacus/hash.inc>
abacus::AbaHash::initializeIteration
ItemType * initializeIteration(const KeyType &key)
This function retrieves the first item.
abacus::AbaHash::AbaHash
AbaHash(int size)
Initializes each slot with a 0-pointer to indicate that the linked list of hash items of this slot is...
abacus::AbaHash::resize
void resize(int newSize)
Can be used to change the size of the hash table.
abacus::AbaHash::next
ItemType * next(const KeyType &key)
This function can be used to go to the next item in the hash table with key key.
abacus::operator<<
std::ostream & operator<<(std::ostream &out, const Active< BaseType, CoType > &rhs)
abacusroot.h
abacus::AbaHashItem
Items in hash tables.
Definition: hash.h:41
abacus
Definition: abacusroot.h:48
abacus::AbaHash::find
const ItemType * find(const KeyType &key) const
Looks for an item in the hash table with a given key.
abacus::AbaHash::size_
int size_
The length of the hash table.
Definition: hash.h:323
OGDF_NEW_DELETE
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition: memory.h:84
abacus::AbaHash::nCollisions_
int nCollisions_
The number of collisions on calls of insert() and overWrite().
Definition: hash.h:326
abacus::AbaHash::remove
int remove(const KeyType &key)
Removes the first item with a given key from the hash table.
abacus::AbaHashItem::item_
ItemType item_
Definition: hash.h:85
abacus::AbaHash::operator=
AbaHash & operator=(const AbaHash &rhs)
abacus::AbacusRoot
Base class of all other classes of ABACUS.
Definition: abacusroot.h:68
abacus::AbaHash
Hash tables.
Definition: hash.h:38
abacus::AbaHashItem::AbaHashItem
AbaHashItem(const KeyType &key, const ItemType &item)
The constructor.
abacus::AbaHash::iter_
AbaHashItem< KeyType, ItemType > * iter_
An iterator for all items stored in a slot.
Definition: hash.h:333
abacus::AbaHash::size
int size() const
Returns the length of the hash table.
abacus::AbaHashItem::next
AbaHashItem< KeyType, ItemType > * next()
Returns a pointer to the next hash-item stored in the linked list corresponding to the slot of this i...
abacus::AbaHash::nCollisions
int nCollisions() const
Returns the number of collisions which occurred during all previous calls of the functions insert() a...
abacus::AbaHash::~AbaHash
~AbaHash()
The destructor.
abacus::AbaHash::insert
void insert(const KeyType &newKey, const ItemType &newItem)
Adds an item to the hash table.
abacus::AbaHash::overWrite
void overWrite(const KeyType &newKey, const ItemType &newItem)
Adds a item to the has table (with overwrite).
abacus::AbaHash::table_
AbaHashItem< KeyType, ItemType > ** table_
The hash table storing a linked list of hash items in each slot.
Definition: hash.h:320
hash.inc
Minisat::Internal::hash
static uint32_t hash(uint32_t x)
Definition: Map.h:38
abacus::AbaHash::hf
int hf(int key) const
Computes the hash value of key.
abacus::AbaHashItem::key_
KeyType key_
Definition: hash.h:84
abacus::AbaHashItem::next_
AbaHashItem< KeyType, ItemType > * next_
Definition: hash.h:86