Zero  0.1.0
hashtable_deque.hpp
Go to the documentation of this file.
1 #ifndef __HASHTABLE_DEQUE_HPP
2 #define __HASHTABLE_DEQUE_HPP
3 
4 #include <cstdint>
5 #include <unordered_map>
6 #include <memory>
7 
8 #include "hashtable_deque_exceptions.hpp"
9 
10 namespace zero::hashtable_deque {
11 
35  template<class key_type, key_type invalid_key>
36  class HashtableDeque {
37  public:
48  HashtableDeque(key_type initialSize = 0) :
49  _directAccessDeque(initialSize ? std::make_unique<std::unordered_map<key_type, KeyPair>>(initialSize)
50  : std::make_unique<std::unordered_map<key_type, KeyPair>>()),
51  _back(invalid_key),
52  _front(invalid_key) {};
53 
59  ~HashtableDeque() {};
60 
69  bool contains(const key_type& k) const noexcept {
70  return static_cast<bool>(_directAccessDeque->count(k));
71  }
72 
80  void pushToBack(const key_type& k) {
81  if (!_directAccessDeque->empty()) {
82  auto oldSize = _directAccessDeque->size();
83  w_assert1(_back != invalid_key);
84  w_assert1((*_directAccessDeque)[_back]._next == invalid_key);
85 
86  if (_directAccessDeque->count(k)) {
87  throw HashtableDequeAlreadyContainsException<key_type, invalid_key>(_directAccessDeque->size(),
88  _back, _front, k);
89  }
90  (*_directAccessDeque)[k] = KeyPair(_back, invalid_key);
91  (*_directAccessDeque)[_back]._next = k;
92  _back = k;
93  w_assert1(_directAccessDeque->size() == oldSize + 1);
94  } else {
95  w_assert1(_back == invalid_key);
96  w_assert1(_front == invalid_key);
97 
98  (*_directAccessDeque)[k] = KeyPair(invalid_key, invalid_key);
99  _back = k;
100  _front = k;
101  w_assert1(_directAccessDeque->size() == 1);
102  }
103  }
104 
112  void pushToBack(key_type&& k) {
113  if (!_directAccessDeque->empty()) {
114  auto oldSize = _directAccessDeque->size();
115  w_assert1(_back != invalid_key);
116  w_assert1((*_directAccessDeque)[_back]._next == invalid_key);
117 
118  if (_directAccessDeque->count(k)) {
119  throw HashtableDequeAlreadyContainsException<key_type, invalid_key>(_directAccessDeque->size(),
120  _back, _front, k);
121  }
122  (*_directAccessDeque)[k] = KeyPair(_back, invalid_key);
123  (*_directAccessDeque)[_back]._next = k;
124  _back = k;
125  w_assert1(_directAccessDeque->size() == oldSize + 1);
126  } else {
127  w_assert1(_back == invalid_key);
128  w_assert1(_front == invalid_key);
129 
130  (*_directAccessDeque)[k] = KeyPair(invalid_key, invalid_key);
131  _back = k;
132  _front = k;
133  w_assert1(_directAccessDeque->size() == 1);
134  }
135  }
136 
143  void popFromFront() {
144  if (_directAccessDeque->empty()) {
145  throw HashtableDequeEmptyException<key_type, invalid_key>(_directAccessDeque->size(), _back, _front);
146  } else if (_directAccessDeque->size() == 1) {
147  w_assert1(_back == _front);
148  w_assert1((*_directAccessDeque)[_front]._next == invalid_key);
149  w_assert1((*_directAccessDeque)[_front]._previous == invalid_key);
150 
151  _directAccessDeque->erase(_front);
152  _front = invalid_key;
153  _back = invalid_key;
154  w_assert1(_directAccessDeque->size() == 0);
155  } else {
156  auto oldSize = _directAccessDeque->size();
157  key_type oldFront = _front;
158  KeyPair oldFrontEntry = (*_directAccessDeque)[_front];
159  w_assert1(_back != _front);
160  w_assert1(_back != invalid_key);
161 
162  _front = oldFrontEntry._next;
163  (*_directAccessDeque)[oldFrontEntry._next]._previous = invalid_key;
164  _directAccessDeque->erase(oldFront);
165  w_assert1(_directAccessDeque->size() == oldSize - 1);
166  }
167  }
168 
176  void popFromFront(key_type& k) {
177  if (_directAccessDeque->empty()) {
178  throw HashtableDequeEmptyException<key_type, invalid_key>(_directAccessDeque->size(), _back, _front);
179  } else if (_directAccessDeque->size() == 1) {
180  w_assert1(_back == _front);
181  w_assert1((*_directAccessDeque)[_front]._next == invalid_key);
182  w_assert1((*_directAccessDeque)[_front]._previous == invalid_key);
183 
184  _directAccessDeque->erase(_front);
185  k = _front;
186  _front = invalid_key;
187  _back = invalid_key;
188  w_assert1(_directAccessDeque->size() == 0);
189  } else {
190  auto oldSize = _directAccessDeque->size();
191  key_type oldFront = _front;
192  KeyPair oldFrontEntry = (*_directAccessDeque)[_front];
193  w_assert1(_back != _front);
194  w_assert1(_back != invalid_key);
195 
196  _front = oldFrontEntry._next;
197  (*_directAccessDeque)[oldFrontEntry._next]._previous = invalid_key;
198  _directAccessDeque->erase(oldFront);
199  w_assert1(_directAccessDeque->size() == oldSize - 1);
200  k = oldFront;
201  }
202  }
203 
211  void pushToFront(const key_type& k) {
212  if (!_directAccessDeque->empty()) {
213  auto oldSize = _directAccessDeque->size();
214  w_assert1(_back != invalid_key);
215  w_assert1((*_directAccessDeque)[_front]._previous == invalid_key);
216 
217  if (_directAccessDeque->count(k)) {
218  throw HashtableDequeAlreadyContainsException<key_type, invalid_key>(_directAccessDeque->size(),
219  _back, _front, k);
220  }
221  (*_directAccessDeque)[k] = KeyPair(invalid_key, _front);
222  (*_directAccessDeque)[_front]._previous = k;
223  _front = k;
224  w_assert1(_directAccessDeque->size() == oldSize + 1);
225  } else {
226  w_assert1(_back == invalid_key);
227  w_assert1(_front == invalid_key);
228 
229  (*_directAccessDeque)[k] = KeyPair(invalid_key, invalid_key);
230  _back = k;
231  _front = k;
232  w_assert1(_directAccessDeque->size() == 1);
233  }
234  }
235 
243  void pushToFront(key_type&& k) {
244  if (!_directAccessDeque->empty()) {
245  auto oldSize = _directAccessDeque->size();
246  w_assert1(_back != invalid_key);
247  w_assert1((*_directAccessDeque)[_front]._previous == invalid_key);
248 
249  if (_directAccessDeque->count(k)) {
250  throw HashtableDequeAlreadyContainsException<key_type, invalid_key>(_directAccessDeque->size(),
251  _back, _front, k);
252  }
253  (*_directAccessDeque)[k] = KeyPair(invalid_key, _front);
254  (*_directAccessDeque)[_front]._previous = k;
255  _front = k;
256  w_assert1(_directAccessDeque->size() == oldSize + 1);
257  } else {
258  w_assert1(_back == invalid_key);
259  w_assert1(_front == invalid_key);
260 
261  (*_directAccessDeque)[k] = KeyPair(invalid_key, invalid_key);
262  _back = k;
263  _front = k;
264  w_assert1(_directAccessDeque->size() == 1);
265  }
266  }
267 
274  void popFromBack() {
275  if (_directAccessDeque->empty()) {
276  throw HashtableDequeEmptyException<key_type, invalid_key>(_directAccessDeque->size(), _back, _front);
277  } else if (_directAccessDeque->size() == 1) {
278  w_assert1(_back == _front);
279  w_assert1((*_directAccessDeque)[_front]._next == invalid_key);
280  w_assert1((*_directAccessDeque)[_front]._previous == invalid_key);
281 
282  _directAccessDeque->erase(_front);
283  _front = invalid_key;
284  _back = invalid_key;
285  w_assert1(_directAccessDeque->size() == 0);
286  } else {
287  auto oldSize = _directAccessDeque->size();
288  key_type oldBack = _back;
289  KeyPair oldBackEntry = (*_directAccessDeque)[_back];
290  w_assert1(_back != _front);
291  w_assert1(_back != invalid_key);
292 
293  _back = oldBackEntry._previous;
294  (*_directAccessDeque)[oldBackEntry._previous]._next = invalid_key;
295  _directAccessDeque->erase(oldBack);
296  w_assert1(_directAccessDeque->size() == oldSize - 1);
297  }
298  }
299 
307  void popFromBack(key_type& k) {
308  if (_directAccessDeque->empty()) {
309  throw HashtableDequeEmptyException<key_type, invalid_key>(_directAccessDeque->size(), _back, _front);
310  } else if (_directAccessDeque->size() == 1) {
311  w_assert1(_back == _front);
312  w_assert1((*_directAccessDeque)[_front]._next == invalid_key);
313  w_assert1((*_directAccessDeque)[_front]._previous == invalid_key);
314 
315  _directAccessDeque->erase(_front);
316  k = _front;
317  _front = invalid_key;
318  _back = invalid_key;
319  w_assert1(_directAccessDeque->size() == 0);
320  } else {
321  auto oldSize = _directAccessDeque->size();
322  key_type oldBack = _back;
323  KeyPair oldBackEntry = (*_directAccessDeque)[_back];
324  w_assert1(_back != _front);
325  w_assert1(_back != invalid_key);
326 
327  _back = oldBackEntry._previous;
328  (*_directAccessDeque)[oldBackEntry._previous]._next = invalid_key;
329  _directAccessDeque->erase(oldBack);
330  w_assert1(_directAccessDeque->size() == oldSize - 1);
331  k = oldBack;
332  }
333  }
334 
343  void remove(const key_type& k) {
344  if (!_directAccessDeque->count(k)) {
345  throw HashtableDequeNotContainedException<key_type, invalid_key>(_directAccessDeque->size(), _back,
346  _front, k);
347  } else {
348  auto old_size = _directAccessDeque->size();
349  KeyPair old_key = (*_directAccessDeque)[k];
350  if (old_key._next != invalid_key) {
351  (*_directAccessDeque)[old_key._next]._previous = old_key._previous;
352  } else {
353  _back = old_key._previous;
354  }
355  if (old_key._previous != invalid_key) {
356  (*_directAccessDeque)[old_key._previous]._next = old_key._next;
357  } else {
358  _front = old_key._next;
359  }
360  _directAccessDeque->erase(k);
361  w_assert1(_directAccessDeque->size() == old_size - 1);
362  }
363  }
364 
373  void remove(key_type&& k) {
374  if (!_directAccessDeque->count(k)) {
375  throw HashtableDequeNotContainedException<key_type, invalid_key>(_directAccessDeque->size(), _back,
376  _front, k);
377  } else {
378  auto old_size = _directAccessDeque->size();
379  KeyPair old_key = (*_directAccessDeque)[k];
380  if (old_key._next != invalid_key) {
381  (*_directAccessDeque)[old_key._next]._previous = old_key._previous;
382  } else {
383  _back = old_key._previous;
384  }
385  if (old_key._previous != invalid_key) {
386  (*_directAccessDeque)[old_key._previous]._next = old_key._next;
387  } else {
388  _front = old_key._next;
389  }
390  _directAccessDeque->erase(k);
391  w_assert1(_directAccessDeque->size() == old_size - 1);
392  }
393  }
394 
406  void insertBefore(const key_type& k, const key_type& ref) {
407  if (_directAccessDeque->count(ref) == 0) {
408  throw HashtableDequeNotContainedException<key_type, invalid_key>(_directAccessDeque->size(),
409  _back, _front, ref);
410  } else if (_directAccessDeque->count(k)) {
411  throw HashtableDequeAlreadyContainsException<key_type, invalid_key>(_directAccessDeque->size(),
412  _back, _front, k);
413  } else if (_front == ref) {
414  auto oldSize = _directAccessDeque->size();
415  w_assert1((*_directAccessDeque)[ref]._previous == invalid_key);
416  w_assert1(_back != invalid_key);
417  (*_directAccessDeque)[k] = KeyPair(invalid_key, ref);
418  _front = k;
419  (*_directAccessDeque)[ref]._previous = k;
420  w_assert1(_directAccessDeque->size() == oldSize + 1);
421  } else {
422  auto oldSize = _directAccessDeque->size();
423  w_assert1((*_directAccessDeque)[ref]._previous != invalid_key);
424  (*_directAccessDeque)[k] = KeyPair((*_directAccessDeque)[ref]._previous, ref);
425  (*_directAccessDeque)[(*_directAccessDeque)[ref]._previous]._next = k;
426  (*_directAccessDeque)[ref]._previous = k;
427  w_assert1(_directAccessDeque->size() == oldSize + 1);
428  }
429  }
430 
442  void insertBefore(key_type&& k, key_type&& ref) {
443  if (_directAccessDeque->count(ref) == 0) {
444  throw HashtableDequeNotContainedException<key_type, invalid_key>(_directAccessDeque->size(),
445  _back, _front, ref);
446  } else if (_directAccessDeque->count(k)) {
447  throw HashtableDequeAlreadyContainsException<key_type, invalid_key>(_directAccessDeque->size(),
448  _back, _front, k);
449  } else if (_front == ref) {
450  auto oldSize = _directAccessDeque->size();
451  w_assert1((*_directAccessDeque)[ref]._previous == invalid_key);
452  w_assert1(_back != invalid_key);
453  (*_directAccessDeque)[k] = KeyPair(invalid_key, ref);
454  _front = k;
455  (*_directAccessDeque)[ref]._previous = k;
456  w_assert1(_directAccessDeque->size() == oldSize + 1);
457  } else {
458  auto oldSize = _directAccessDeque->size();
459  w_assert1((*_directAccessDeque)[ref]._previous != invalid_key);
460  (*_directAccessDeque)[k] = KeyPair((*_directAccessDeque)[ref]._previous, ref);
461  (*_directAccessDeque)[(*_directAccessDeque)[ref]._previous]._next = k;
462  (*_directAccessDeque)[ref]._previous = k;
463  w_assert1(_directAccessDeque->size() == oldSize + 1);
464  }
465  }
466 
478  void insertAfter(const key_type& k, const key_type& ref) {
479  if (_directAccessDeque->count(ref) == 0) {
480  throw HashtableDequeNotContainedException<key_type, invalid_key>(_directAccessDeque->size(),
481  _back, _front, ref);
482  } else if (_directAccessDeque->count(k)) {
483  throw HashtableDequeAlreadyContainsException<key_type, invalid_key>(_directAccessDeque->size(),
484  _back, _front, k);
485  } else if (_back == ref) {
486  auto oldSize = _directAccessDeque->size();
487  w_assert1((*_directAccessDeque)[ref]._next == invalid_key);
488  w_assert1(_front != invalid_key);
489  (*_directAccessDeque)[k] = KeyPair(ref, invalid_key);
490  _back = k;
491  (*_directAccessDeque)[ref]._next = k;
492  w_assert1(_directAccessDeque->size() == oldSize + 1);
493  } else {
494  auto oldSize = _directAccessDeque->size();
495  w_assert1((*_directAccessDeque)[ref]._next != invalid_key);
496  (*_directAccessDeque)[k] = KeyPair(ref, (*_directAccessDeque)[ref]._next);
497  (*_directAccessDeque)[(*_directAccessDeque)[ref]._next]._previous = k;
498  (*_directAccessDeque)[ref]._next = k;
499  w_assert1(_directAccessDeque->size() == oldSize + 1);
500  }
501  }
502 
514  void insertAfter(key_type&& k, key_type&& ref) {
515  if (_directAccessDeque->count(ref) == 0) {
516  throw HashtableDequeNotContainedException<key_type, invalid_key>(_directAccessDeque->size(),
517  _back, _front, ref);
518  } else if (_directAccessDeque->count(k)) {
519  throw HashtableDequeAlreadyContainsException<key_type, invalid_key>(_directAccessDeque->size(),
520  _back, _front, k);
521  } else if (_back == ref) {
522  auto oldSize = _directAccessDeque->size();
523  w_assert1((*_directAccessDeque)[ref]._next == invalid_key);
524  w_assert1(_front != invalid_key);
525  (*_directAccessDeque)[k] = KeyPair(ref, invalid_key);
526  _back = k;
527  (*_directAccessDeque)[ref]._next = k;
528  w_assert1(_directAccessDeque->size() == oldSize + 1);
529  } else {
530  auto oldSize = _directAccessDeque->size();
531  w_assert1((*_directAccessDeque)[ref]._next != invalid_key);
532  (*_directAccessDeque)[k] = KeyPair(ref, (*_directAccessDeque)[ref]._next);
533  (*_directAccessDeque)[(*_directAccessDeque)[ref]._next]._previous = k;
534  (*_directAccessDeque)[ref]._next = k;
535  w_assert1(_directAccessDeque->size() == oldSize + 1);
536  }
537  }
538 
546  void getFront(key_type& k) {
547  if (_directAccessDeque->empty()) {
548  throw HashtableDequeEmptyException<key_type, invalid_key>(_directAccessDeque->size(), _back, _front);
549  } else {
550  k = _front;
551  }
552  }
553 
561  key_type getFront() {
562  if (_directAccessDeque->empty()) {
563  throw HashtableDequeEmptyException<key_type, invalid_key>(_directAccessDeque->size(), _back, _front);
564  } else {
565  return _front;
566  }
567  }
568 
576  void getBack(key_type& k) {
577  if (_directAccessDeque->empty()) {
578  throw HashtableDequeEmptyException<key_type, invalid_key>(_directAccessDeque->size(), _back, _front);
579  } else {
580  k = _back;
581  }
582  }
583 
591  key_type getBack() {
592  if (_directAccessDeque->empty()) {
593  throw HashtableDequeEmptyException<key_type, invalid_key>(_directAccessDeque->size(), _back, _front);
594  } else {
595  return _back;
596  }
597  }
598 
611  void getBefore(key_type& k, const key_type& ref) {
612  if (_directAccessDeque->count(ref) == 0) {
613  throw HashtableDequeNotContainedException<key_type, invalid_key>(_directAccessDeque->size(),
614  _back, _front, ref);
615  } else if (_front == ref) {
616  w_assert1((*_directAccessDeque)[ref]._previous == invalid_key);
617  throw HashtableDequeAlreadyAtTheFrontException<key_type, invalid_key>(_directAccessDeque->size(),
618  _back, _front, invalid_key);
619  } else {
620  k = (*_directAccessDeque)[ref]._previous;
621  }
622  }
623 
636  void getBefore(key_type& k, key_type&& ref) {
637  if (_directAccessDeque->count(ref) == 0) {
638  throw HashtableDequeNotContainedException<key_type, invalid_key>(_directAccessDeque->size(),
639  _back, _front, ref);
640  } else if (_front == ref) {
641  w_assert1((*_directAccessDeque)[ref]._previous == invalid_key);
642  throw HashtableDequeAlreadyAtTheFrontException<key_type, invalid_key>(_directAccessDeque->size(),
643  _back, _front, invalid_key);
644  } else {
645  k = (*_directAccessDeque)[ref]._previous;
646  }
647  }
648 
661  key_type getBefore(const key_type& ref) {
662  if (_directAccessDeque->count(ref) == 0) {
663  throw HashtableDequeNotContainedException<key_type, invalid_key>(_directAccessDeque->size(),
664  _back, _front, ref);
665  } else if (_front == ref) {
666  w_assert1((*_directAccessDeque)[ref]._previous == invalid_key);
667  throw HashtableDequeAlreadyAtTheFrontException<key_type, invalid_key>(_directAccessDeque->size(),
668  _back, _front, invalid_key);
669  } else {
670  return (*_directAccessDeque)[ref]._previous;
671  }
672  }
673 
686  key_type getBefore(key_type&& ref) {
687  if (_directAccessDeque->count(ref) == 0) {
688  throw HashtableDequeNotContainedException<key_type, invalid_key>(_directAccessDeque->size(),
689  _back, _front, ref);
690  } else if (_front == ref) {
691  w_assert1((*_directAccessDeque)[ref]._previous == invalid_key);
692  throw HashtableDequeAlreadyAtTheFrontException<key_type, invalid_key>(_directAccessDeque->size(),
693  _back, _front, invalid_key);
694  } else {
695  return (*_directAccessDeque)[ref]._previous;
696  }
697  }
698 
711  void getAfter(key_type& k, const key_type& ref) {
712  if (_directAccessDeque->count(ref) == 0) {
713  throw HashtableDequeNotContainedException<key_type, invalid_key>(_directAccessDeque->size(),
714  _back, _front, ref);
715  } else if (_back == ref) {
716  w_assert1((*_directAccessDeque)[ref].next == invalid_key);
717  throw HashtableDequeAlreadyAtTheBackException<key_type, invalid_key>(_directAccessDeque->size(),
718  _back, _front, invalid_key);
719  } else {
720  k = (*_directAccessDeque)[ref]._next;
721  }
722  }
723 
736  void getAfter(key_type& k, key_type&& ref) {
737  if (_directAccessDeque->count(ref) == 0) {
738  throw HashtableDequeNotContainedException<key_type, invalid_key>(_directAccessDeque->size(),
739  _back, _front, ref);
740  } else if (_back == ref) {
741  w_assert1((*_directAccessDeque)[ref].next == invalid_key);
742  throw HashtableDequeAlreadyAtTheBackException<key_type, invalid_key>(_directAccessDeque->size(),
743  _back, _front, invalid_key);
744  } else {
745  k = (*_directAccessDeque)[ref]._next;
746  }
747  }
748 
761  key_type getAfter(const key_type& ref) {
762  if (_directAccessDeque->count(ref) == 0) {
763  throw HashtableDequeNotContainedException<key_type, invalid_key>(_directAccessDeque->size(),
764  _back, _front, ref);
765  } else if (_back == ref) {
766  w_assert1((*_directAccessDeque)[ref]._next == invalid_key);
767  throw HashtableDequeAlreadyAtTheBackException<key_type, invalid_key>(_directAccessDeque->size(),
768  _back, _front, invalid_key);
769  } else {
770  return (*_directAccessDeque)[ref]._next;
771  }
772  }
773 
786  key_type getAfter(key_type&& ref) {
787  if (_directAccessDeque->count(ref) == 0) {
788  throw HashtableDequeNotContainedException<key_type, invalid_key>(_directAccessDeque->size(),
789  _back, _front, ref);
790  } else if (_back == ref) {
791  w_assert1((*_directAccessDeque)[ref].next == invalid_key);
792  throw HashtableDequeAlreadyAtTheBackException<key_type, invalid_key>(_directAccessDeque->size(),
793  _back, _front, invalid_key);
794  } else {
795  return (*_directAccessDeque)[ref]._next;
796  }
797  }
798 
805  inline uint64_t length() const noexcept {
806  return _directAccessDeque->size();
807  }
808 
809  private:
817  class KeyPair {
818  public:
824  KeyPair() {}
825 
834  KeyPair(const key_type& previous, const key_type& next) {
835  this->_previous = previous;
836  this->_next = next;
837  }
838 
843  virtual ~KeyPair() {}
844 
851  key_type _previous;
852 
859  key_type _next;
860  };
861 
872  std::unique_ptr<std::unordered_map<key_type, KeyPair>> _directAccessDeque;
873 
879  key_type _back;
880 
886  key_type _front;
887  };
888 } // zero::hashtable_deque
889 
890 #endif // __HASHTABLE_DEQUE_HPP
zero::hashtable_deque::HashtableDeque::getBack
key_type getBack()
Get the key at the back.
Definition: hashtable_deque.hpp:591
zero::hashtable_deque::HashtableDeque::getBack
void getBack(key_type &k)
Get the key at the back.
Definition: hashtable_deque.hpp:576
zero::hashtable_deque::HashtableDeque::insertAfter
void insertAfter(const key_type &k, const key_type &ref)
Add the key to after a reference key.
Definition: hashtable_deque.hpp:478
w_assert1
#define w_assert1(x)
Level 1 should not add significant extra time.
Definition: w_base.h:198
zero::hashtable_deque::HashtableDeque::_directAccessDeque
std::unique_ptr< std::unordered_map< key_type, KeyPair > > _directAccessDeque
Maps from keys to their deque entry.
Definition: hashtable_deque.hpp:872
zero::hashtable_deque::HashtableDeque::KeyPair::_previous
key_type _previous
The previous element of this element.
Definition: hashtable_deque.hpp:851
zero::hashtable_deque::HashtableDeque::getAfter
key_type getAfter(const key_type &ref)
Definition: hashtable_deque.hpp:761
zero::hashtable_deque::HashtableDeque::KeyPair::KeyPair
KeyPair(const key_type &previous, const key_type &next)
Constructor for a pair of keys with initial values.
Definition: hashtable_deque.hpp:834
zero::hashtable_deque::HashtableDequeNotContainedException
Exception thrown when an entry was not already contained in an HashtableDeque.
Definition: hashtable_deque_exceptions.hpp:161
zero::hashtable_deque
Definition: hashtable_deque.hpp:10
std
STL namespace.
zero::hashtable_deque::HashtableDequeAlreadyAtTheFrontException
Exception thrown when an entry was already at the front of an HashtableDeque.
Definition: hashtable_deque_exceptions.hpp:204
zero::hashtable_deque::HashtableDeque::getFront
key_type getFront()
Get the key at the front.
Definition: hashtable_deque.hpp:561
zero::hashtable_deque::HashtableDequeAlreadyAtTheBackException
Exception thrown when an entry was already at the back of an HashtableDeque.
Definition: hashtable_deque_exceptions.hpp:247
zero::hashtable_deque::HashtableDeque::popFromBack
void popFromBack(key_type &k)
Removes the next key from this deque.
Definition: hashtable_deque.hpp:307
zero::hashtable_deque::HashtableDeque::contains
bool contains(const key_type &k) const noexcept
Entry with given key contained.
Definition: hashtable_deque.hpp:69
zero::hashtable_deque::HashtableDeque::getBefore
void getBefore(key_type &k, const key_type &ref)
Get the key to before a reference key.
Definition: hashtable_deque.hpp:611
zero::hashtable_deque::HashtableDeque::_front
key_type _front
Element at the front.
Definition: hashtable_deque.hpp:886
zero::hashtable_deque::HashtableDeque::popFromBack
void popFromBack()
Removes the next key from this deque.
Definition: hashtable_deque.hpp:274
zero::hashtable_deque::HashtableDeque::getAfter
key_type getAfter(key_type &&ref)
Definition: hashtable_deque.hpp:786
zero::hashtable_deque::HashtableDeque::insertBefore
void insertBefore(key_type &&k, key_type &&ref)
Add the key to before a reference key.
Definition: hashtable_deque.hpp:442
zero::hashtable_deque::HashtableDeque::popFromFront
void popFromFront()
Removes the next key from this deque.
Definition: hashtable_deque.hpp:143
zero::hashtable_deque::HashtableDeque::length
uint64_t length() const noexcept
Number of entries in this deque.
Definition: hashtable_deque.hpp:805
zero::hashtable_deque::HashtableDeque::~HashtableDeque
~HashtableDeque()
Destructor of a Deque with Direct Access.
Definition: hashtable_deque.hpp:59
zero::hashtable_deque::HashtableDeque::pushToFront
void pushToFront(const key_type &k)
Add the key to the front of this deque.
Definition: hashtable_deque.hpp:211
zero::hashtable_deque::HashtableDeque::_back
key_type _back
Element at the back.
Definition: hashtable_deque.hpp:879
zero::hashtable_deque::HashtableDeque::popFromFront
void popFromFront(key_type &k)
Removes the next key from this deque.
Definition: hashtable_deque.hpp:176
zero::hashtable_deque::HashtableDeque::KeyPair::KeyPair
KeyPair()
Constructor for an empty pair of keys.
Definition: hashtable_deque.hpp:824
zero::hashtable_deque::HashtableDeque::insertAfter
void insertAfter(key_type &&k, key_type &&ref)
Add the key to after a reference key.
Definition: hashtable_deque.hpp:514
zero::hashtable_deque::HashtableDequeAlreadyContainsException
Exception thrown when an entry was already contained in an HashtableDeque.
Definition: hashtable_deque_exceptions.hpp:93
zero::hashtable_deque::HashtableDeque::getBefore
key_type getBefore(key_type &&ref)
Get the key to before a reference key.
Definition: hashtable_deque.hpp:686
hashtable_deque_exceptions.hpp
zero::hashtable_deque::HashtableDeque::KeyPair
A pair of keys for the implementation of a deque as a doubly-linked list.
Definition: hashtable_deque.hpp:817
zero::hashtable_deque::HashtableDequeEmptyException
Exception thrown when an HashtableDeque is empty.
Definition: hashtable_deque_exceptions.hpp:141
zero::hashtable_deque::HashtableDeque::getAfter
void getAfter(key_type &k, key_type &&ref)
Get the key to after a reference key.
Definition: hashtable_deque.hpp:736
zero::hashtable_deque::HashtableDeque::HashtableDeque
HashtableDeque(key_type initialSize=0)
Constructor of a Deque with Direct Access.
Definition: hashtable_deque.hpp:48
zero::hashtable_deque::HashtableDeque::pushToFront
void pushToFront(key_type &&k)
Add the key to the front of this deque (with move semantics)
Definition: hashtable_deque.hpp:243
zero::hashtable_deque::HashtableDeque::pushToBack
void pushToBack(const key_type &k)
Add the key to the back of this deque.
Definition: hashtable_deque.hpp:80
zero::hashtable_deque::HashtableDeque::getAfter
void getAfter(key_type &k, const key_type &ref)
Get the key to after a reference key.
Definition: hashtable_deque.hpp:711
zero::hashtable_deque::HashtableDeque::pushToBack
void pushToBack(key_type &&k)
Add the key to the back of this deque (with move semantics)
Definition: hashtable_deque.hpp:112
zero::hashtable_deque::HashtableDeque::insertBefore
void insertBefore(const key_type &k, const key_type &ref)
Add the key to before a reference key.
Definition: hashtable_deque.hpp:406
zero::hashtable_deque::HashtableDeque::KeyPair::_next
key_type _next
The next element of this element.
Definition: hashtable_deque.hpp:859
zero::hashtable_deque::HashtableDeque::KeyPair::~KeyPair
virtual ~KeyPair()
Destructor for a pair of keys.
Definition: hashtable_deque.hpp:843
zero::hashtable_deque::HashtableDeque
Deque with Direct Access.
Definition: hashtable_deque.hpp:36
zero::hashtable_deque::HashtableDeque::getBefore
void getBefore(key_type &k, key_type &&ref)
Get the key to before a reference key.
Definition: hashtable_deque.hpp:636
zero::hashtable_deque::HashtableDeque::getBefore
key_type getBefore(const key_type &ref)
Get the key to before a reference key.
Definition: hashtable_deque.hpp:661
zero::hashtable_deque::HashtableDeque::getFront
void getFront(key_type &k)
Get the key at the front.
Definition: hashtable_deque.hpp:546
Generated by   doxygen 1.8.12