Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

hash.h
Go to the documentation of this file.
1 
30 #pragma once
31 
33 
34 #pragma GCC visibility push(default)
35 namespace abacus {
36 
37 class AbacusGlobal;
38 
39 template<class KeyType,class ItemType> class AbaHash;
40 
41 template <class KeyType, class ItemType>
43 template <class KeyType, class ItemType>
44 class AbaHash;
45 
46 template <class KeyType, class ItemType>
47 std::ostream &operator<< (std::ostream &out, const AbaHashItem<KeyType, ItemType> &rhs);
48 
49 template <class KeyType, class ItemType>
50 std::ostream &operator<< (std::ostream &out, const AbaHash<KeyType, ItemType> &hash);
51 
52 
54 /*
55  * \sa AbaHash
56  */
57 template <class KeyType, class ItemType>
58 class AbaHashItem : public AbacusRoot {
59  friend class AbaHash<KeyType, ItemType>;
60 
61 public:
62 
64 
68  AbaHashItem(const KeyType &key, const ItemType &item);
69 
70 
72 
75  friend std::ostream &operator<< <> (std::ostream &,
77 
80 
82  const AbaHashItem<KeyType, ItemType> *next() const;
83 
84 private:
85  KeyType key_;
86  ItemType item_;
88 
90 };
91 
92 
94 
124 template <class KeyType, class ItemType>
125 class AbaHash : public AbacusRoot {
126 public:
127 
129 
132  explicit AbaHash(int size);
133 
135 
138  ~AbaHash();
139 
141 
152  friend std::ostream &operator<< <> (std::ostream &out,
154 
156 
164  void insert(const KeyType &newKey, const ItemType &newItem);
165 
167 
174  void overWrite(const KeyType &newKey, const ItemType &newItem);
175 
177 
185  const ItemType *find(const KeyType &key) const;
186 
188 
196  ItemType *find(const KeyType &key);
197 
199 
205  bool find(const KeyType &key, const ItemType &item) const;
206 
211 
214 
220  ItemType *initializeIteration(const KeyType &key);
221 
223 
229  const ItemType *initializeIteration(const KeyType &key) const;
230 
232 
244  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>
342 #pragma GCC visibility pop
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:42
abacus
Definition: ILPClusterPlanarity.h:50
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:85
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:86
abacus::AbaHash::operator=
AbaHash & operator=(const AbaHash &rhs)
abacus::AbacusRoot
Base class of all other classes of ABACUS.
Definition: abacusroot.h:69
abacus::AbaHash
Hash tables.
Definition: hash.h:39
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:39
abacus::AbaHash::hf
int hf(int key) const
Computes the hash value of key.
abacus::AbaHashItem::key_
KeyType key_
Definition: hash.h:85
abacus::AbaHashItem::next_
AbaHashItem< KeyType, ItemType > * next_
Definition: hash.h:87