aGrUM  0.18.1
a C++ library for (probabilistic) graphical models
hashTable_tpl.h
Go to the documentation of this file.
1 
29 #include <iostream>
30 #include <sstream>
31 #include <string>
32 
33 // to help IDE parser
35 
36 namespace gum {
37 
38 
39  // ===========================================================================
40  // === IMPLEMENTATION OF THE CHAINED LISTS USED IN THE HASH TABLES ===
41  // ===========================================================================
42 
43  template < typename Key, typename Val, typename Alloc >
44  template < typename OtherAlloc >
47  Bucket *ptr, *old_ptr{nullptr}, *new_elt{nullptr};
48  // set the defaults
49  deb_list__ = nullptr;
50 
51  // copy from's list
52  try {
53  for (ptr = from.deb_list__; ptr != nullptr; ptr = ptr->next) {
54  // copy the current from's bucket (may throw an exception either because
55  // new cannot allocate the bucket or because the copy constructor of Val
56  // throws an exception)
57  new_elt = alloc_bucket__->allocate(1);
58 
59  try {
60  alloc_bucket__->construct(new_elt, *ptr);
61  } catch (...) {
62  alloc_bucket__->deallocate(new_elt, 1);
63  throw;
64  }
65 
66  // rechain properly the new list
67  new_elt->prev = old_ptr;
68 
69  if (old_ptr != nullptr)
70  old_ptr->next = new_elt;
71  else
72  deb_list__ = new_elt;
73 
74  old_ptr = new_elt;
75  }
76 
77  if (old_ptr != nullptr) old_ptr->next = nullptr;
78 
79  // update the number of elements stored into the list and the end of the
80  // list
81  nb_elements__ = from.nb_elements__;
82  end_list__ = new_elt;
83  } catch (...) {
84  // problem: we could not allocate an element in the list => we delete
85  // the elements created so far and we throw an exception
86  for (; deb_list__ != nullptr; deb_list__ = new_elt) {
87  new_elt = deb_list__->next;
88  alloc_bucket__->destroy(deb_list__);
89  alloc_bucket__->deallocate(deb_list__, 1);
90  }
91 
92  nb_elements__ = 0;
93  end_list__ = nullptr;
94 
95  throw;
96  }
97  }
98 
99  template < typename Key, typename Val, typename Alloc >
102  for (Bucket* ptr = deb_list__; ptr != nullptr; ptr = ptr->next)
103  if (ptr->key() == key) return ptr;
104 
105  return nullptr;
106  }
107 
108  template < typename Key, typename Val, typename Alloc >
109  INLINE void
111  // check that the pointer is not nullptr
112  if (ptr == nullptr) {
113  GUM_ERROR(NullElement, "trying to erase a nullptr bucket");
114  }
115 
116  // relink properly the doubly chained list
117  if (ptr->prev != nullptr)
118  ptr->prev->next = ptr->next;
119  else
120  deb_list__ = ptr->next;
121 
122  if (ptr->next != nullptr)
123  ptr->next->prev = ptr->prev;
124  else
125  end_list__ = ptr->prev;
126 
127  // remove the current element from the list
128  alloc_bucket__->destroy(ptr);
129  alloc_bucket__->deallocate(ptr, 1);
130 
131  --nb_elements__;
132  }
133 
134  template < typename Key, typename Val, typename Alloc >
137  allocator) noexcept :
138  alloc_bucket__{allocator} {}
139 
140  template < typename Key, typename Val, typename Alloc >
142  const HashTableList< Key, Val, Alloc >& from) :
143  alloc_bucket__{from.alloc_bucket__} {
144  copy__(from);
145  }
146 
147  template < typename Key, typename Val, typename Alloc >
149  HashTableList< Key, Val, Alloc >&& from) noexcept :
150  deb_list__{from.deb_list__},
151  end_list__{from.end_list__}, nb_elements__{from.nb_elements__},
152  alloc_bucket__{from.alloc_bucket__} {
153  from.deb_list__ = nullptr;
154  }
155 
156  template < typename Key, typename Val, typename Alloc >
158  for (Bucket *next_ptr, *ptr = deb_list__; ptr != nullptr; ptr = next_ptr) {
159  next_ptr = ptr->next;
160  alloc_bucket__->destroy(ptr);
161  alloc_bucket__->deallocate(ptr, 1);
162  }
163  }
164 
165  template < typename Key, typename Val, typename Alloc >
167  for (Bucket *next_ptr, *ptr = deb_list__; ptr != nullptr; ptr = next_ptr) {
168  next_ptr = ptr->next;
169  alloc_bucket__->destroy(ptr);
170  alloc_bucket__->deallocate(ptr, 1);
171  }
172 
173  nb_elements__ = Size(0);
174  deb_list__ = nullptr;
175  end_list__ = nullptr;
176  }
177 
178  template < typename Key, typename Val, typename Alloc >
181  const HashTableList< Key, Val, Alloc >& from) {
182  // avoid self assignment
183  if (this != &from) {
184  clear();
185  copy__(from);
186  }
187 
188  return *this;
189  }
190 
191  template < typename Key, typename Val, typename Alloc >
192  template < typename OtherAlloc >
196  // avoid self assignment
197  if (this
198  != reinterpret_cast< const HashTableList< Key, Val, Alloc >* >(&from)) {
199  clear();
200  copy__(from);
201  }
202 
203  return *this;
204  }
205 
206  template < typename Key, typename Val, typename Alloc >
209  HashTableList< Key, Val, Alloc >&& from) noexcept {
210  // avoid self assignment
211  if (this != &from) {
212  deb_list__ = from.deb_list__;
213  end_list__ = from.end_list__;
214  nb_elements__ = from.nb_elements__;
215  from.deb_list__ = nullptr;
216  }
217 
218  return *this;
219  }
220 
221  template < typename Key, typename Val, typename Alloc >
224  alloc_bucket__ = &alloc;
225  }
226 
227  template < typename Key, typename Val, typename Alloc >
230  if (i >= nb_elements__) {
231  GUM_ERROR(NotFound, "not enough elements in the chained list");
232  }
233 
234  Bucket* ptr;
235 
236  for (ptr = deb_list__; i; --i, ptr = ptr->next) {}
237 
238  return ptr->elt();
239  }
240 
241  template < typename Key, typename Val, typename Alloc >
242  INLINE const typename HashTableList< Key, Val, Alloc >::value_type&
244  if (i >= nb_elements__) {
245  GUM_ERROR(NotFound, "not enough elements in the chained list");
246  }
247 
248  Bucket* ptr;
249 
250  for (ptr = deb_list__; i; --i, ptr = ptr->next) {}
251 
252  return ptr->elt();
253  }
254 
255  template < typename Key, typename Val, typename Alloc >
256  INLINE const typename HashTableList< Key, Val, Alloc >::mapped_type&
258  for (Bucket* ptr = deb_list__; ptr != nullptr; ptr = ptr->next)
259  if (ptr->key() == key) return ptr->val();
260 
261  GUM_ERROR(NotFound, "No element with the key <" << key << ">");
262  }
263 
264  template < typename Key, typename Val, typename Alloc >
267  for (Bucket* ptr = deb_list__; ptr != nullptr; ptr = ptr->next)
268  if (ptr->key() == key) return ptr->val();
269 
270  GUM_ERROR(NotFound, "No element with the key <" << key << ">");
271  }
272 
273  template < typename Key, typename Val, typename Alloc >
274  INLINE bool HashTableList< Key, Val, Alloc >::exists(const Key& key) const {
275  for (Bucket* ptr = deb_list__; ptr != nullptr; ptr = ptr->next) {
276  if (ptr->key() == key) { return true; }
277  }
278 
279  return false;
280  }
281 
282  template < typename Key, typename Val, typename Alloc >
283  INLINE bool HashTableList< Key, Val, Alloc >::empty() const noexcept {
284  return (nb_elements__ == Size(0));
285  }
286 
287  template < typename Key, typename Val, typename Alloc >
289  HashTableBucket< Key, Val >* new_elt) noexcept {
290  // place the bucket at the beginning of the list
291  new_elt->prev = nullptr;
292  new_elt->next = deb_list__;
293 
294  if (deb_list__ != nullptr)
295  deb_list__->prev = new_elt;
296  else
297  end_list__ = new_elt;
298 
299  deb_list__ = new_elt;
300 
301  ++nb_elements__;
302  }
303 
304  // ===========================================================================
305  // === GENERIC HASH TABLE IMPLEMENTATION ===
306  // ===========================================================================
307 
308  template < typename Key, typename Val, typename Alloc >
309  template < typename OtherAlloc >
311  const HashTable< Key, Val, OtherAlloc >& table) {
312  // in debug mode, check that this and table have '__nodes' arrays of the
313  // same size
314  GUM_ASSERT(table.size__ == size__);
315 
316  // try to fill the array of chained lists
317  for (Size i = 0; i < table.size__; ++i) {
318  try {
319  nodes__[i] = table.nodes__[i];
320  } catch (...) {
321  // here we could allocate the nodes__[j], j=0..i-1, so we should
322  // deallocate them
323  for (Size j = 0; j < size__; ++j)
324  nodes__[j].clear();
325 
326  nb_elements__ = Size(0);
327 
328  // propagate the exception
329  throw;
330  }
331  }
332 
333  nb_elements__ = table.nb_elements__;
334  }
335 
336  template < typename Key, typename Val, typename Alloc >
337  INLINE const typename HashTable< Key, Val, Alloc >::iterator&
339  return *(reinterpret_cast< const iterator* >(
340  HashTableIteratorStaticEnd::end4Statics()));
341  }
342 
343  template < typename Key, typename Val, typename Alloc >
344  INLINE const typename HashTable< Key, Val, Alloc >::const_iterator&
346  return *(reinterpret_cast< const const_iterator* >(
347  HashTableIteratorStaticEnd::constEnd4Statics()));
348  }
349 
350  template < typename Key, typename Val, typename Alloc >
351  INLINE const typename HashTable< Key, Val, Alloc >::iterator_safe&
353  return *(reinterpret_cast< const iterator_safe* >(
354  HashTableIteratorStaticEnd::endSafe4Statics()));
355  }
356 
357  template < typename Key, typename Val, typename Alloc >
360  return *(reinterpret_cast< const const_iterator_safe* >(
361  HashTableIteratorStaticEnd::constEndSafe4Statics()));
362  }
363 
364  template < typename Key, typename Val, typename Alloc >
366  // setup the nodes__ vector (contains only empty lists)
367  nodes__.resize(size);
368 
369  for (auto& list: nodes__) {
370  list.setAllocator(alloc__);
371  }
372 
373  // set up properly the hash function
374  hash_func__.resize(size);
375 
376  // make sure the end() iterator is constructed properly
377  end4Statics();
378  endSafe4Statics();
379  }
380 
381  template < typename Key, typename Val, typename Alloc >
383  bool resize_pol,
384  bool key_uniqueness_pol) :
385  // size must be >= 2 else we lose all the bits of the hash function
386  size__{Size(1) << hashTableLog2__(std::max(Size(2), size_param))},
387  resize_policy__{resize_pol}, key_uniqueness_policy__{key_uniqueness_pol} {
388  // for debugging purposes
389  GUM_CONSTRUCTOR(HashTable);
390 
391  // finalize the creation
392  create__(size__);
393  }
394 
395  template < typename Key, typename Val, typename Alloc >
397  std::initializer_list< std::pair< Key, Val > > list) :
398  // size must be >= 2 else we lose all the bits of the hash function
399  size__{Size(1) << hashTableLog2__(
400  std::max< Size >(Size(2), Size(list.size()) / 2))} {
401  // for debugging purposes
402  GUM_CONSTRUCTOR(HashTable);
403 
404  // setup the nodes__ vector (contains only empty lists)
405  create__(size__);
406 
407  // insert all the elements
408  for (const auto& elt: list) {
409  insert(elt);
410  }
411  }
412 
413  template < typename Key, typename Val, typename Alloc >
415  const HashTable< Key, Val, Alloc >& table) :
416  size__{table.size__},
417  resize_policy__{table.resize_policy__},
418  key_uniqueness_policy__{table.key_uniqueness_policy__},
419  begin_index__{table.begin_index__} {
420  // for debugging purposes
421  GUM_CONS_CPY(HashTable);
422 
423  // setup the nodes__ vector (contains only empty lists)
424  create__(size__);
425 
426  // fill with the content of table
427  copy__(table);
428  }
429 
430  template < typename Key, typename Val, typename Alloc >
431  template < typename OtherAlloc >
433  const HashTable< Key, Val, OtherAlloc >& table) :
434  size__{table.size__},
435  resize_policy__{table.resize_policy__},
436  key_uniqueness_policy__{table.key_uniqueness_policy__},
437  begin_index__{table.begin_index__} {
438  // for debugging purposes
439  GUM_CONS_CPY(HashTable);
440 
441  // setup the nodes__ vector (contains only empty lists)
442  create__(size__);
443 
444  // fill with the content of table
445  copy__(table);
446  }
447 
448  template < typename Key, typename Val, typename Alloc >
450  nodes__(std::move(table.nodes__)), size__{table.size__},
451  nb_elements__{table.nb_elements__}, hash_func__{table.hash_func__},
452  resize_policy__{table.resize_policy__},
453  key_uniqueness_policy__{table.key_uniqueness_policy__},
454  begin_index__{table.begin_index__},
455  safe_iterators__(std::move(table.safe_iterators__)),
456  alloc__(std::move(table.alloc__)) {
457  // for debugging purposes
458  table.size__ = 0;
459  GUM_CONS_MOV(HashTable);
460  }
461 
462  template < typename Key, typename Val, typename Alloc >
464  const Size len = safe_iterators__.size();
465  for (Size i = Size(0); i < len; ++i)
466  safe_iterators__[i]->clear();
467  }
468 
469  template < typename Key, typename Val, typename Alloc >
471  // update all the registered iterators: they should now point to nullptr
472  // and they are positioned to the end of the hashtable.
473  clearIterators__();
474 
475  // remove the buckets
476  for (Size i = Size(0); i < size__; ++i)
477  nodes__[i].clear();
478 
479  nb_elements__ = Size(0);
480  begin_index__ = std::numeric_limits< Size >::max();
481  }
482 
483  template < typename Key, typename Val, typename Alloc >
485  // for debugging purposes
486  GUM_DESTRUCTOR(HashTable);
487 
488  // update all the registered iterators: they should now point to nullptr
489  // and their hashtable should be set to nullptr
490  clearIterators__();
491  }
492 
493  template < typename Key, typename Val, typename Alloc >
495  const HashTable< Key, Val, Alloc >& from) {
496  // avoid self assignment
497  if (this != &from) {
498  // for debugging purposes
499  GUM_OP_CPY(HashTable);
500 
501  // first remove the current content of the hashtable and make
502  // the iterators point to end
503  clear();
504 
505  // if sizes of from's and this' nodes__ vectors are not the same,
506  // we need to remove the current nodes__' array and to create a
507  // new array with the correct size
508  if (size__ != from.size__) {
509  nodes__.resize(from.size__);
510 
511  for (Size i = Size(0); i < from.size__; ++i) {
512  nodes__[i].setAllocator(alloc__);
513  }
514 
515  size__ = from.size__;
516 
517  // update the hash function : this is important as the computation of
518  // the hash values heavily depends on the size of the hash table
519  hash_func__.resize(size__);
520  }
521 
522  resize_policy__ = from.resize_policy__;
523  key_uniqueness_policy__ = from.key_uniqueness_policy__;
524  begin_index__ = from.begin_index__;
525 
526  // perform the copy
527  copy__(from);
528  }
529 
530  return *this;
531  }
532 
533  template < typename Key, typename Val, typename Alloc >
534  template < typename OtherAlloc >
536  const HashTable< Key, Val, OtherAlloc >& from) {
537  // avoid self assignment
538  if (this != reinterpret_cast< const HashTable< Key, Val, Alloc >* >(&from)) {
539  // for debugging purposes
540  GUM_OP_CPY(HashTable);
541 
542  // first remove the current content of the hashtable and make
543  // the iterators point to end
544  clear();
545 
546  // if sizes of from's and this' nodes__ vectors are not the same,
547  // we need to remove the current nodes__' array and to create a
548  // new array with the correct size
549  if (size__ != from.size__) {
550  nodes__.resize(from.size__);
551 
552  for (Size i = 0; i < from.size__; ++i) {
553  nodes__[i].setAllocator(alloc__);
554  }
555 
556  size__ = from.size__;
557 
558  // update the hash function : this is important as the computation of
559  // the hash values heavily depends on the size of the hash table
560  hash_func__.resize(size__);
561  }
562 
563  resize_policy__ = from.resize_policy__;
564  key_uniqueness_policy__ = from.key_uniqueness_policy__;
565  begin_index__ = from.begin_index__;
566 
567  // perform the copy
568  copy__(from);
569  }
570 
571  return *this;
572  }
573 
574  template < typename Key, typename Val, typename Alloc >
577  // avoid self assignment
578  if (this != &table) {
579  // for debugging purposes
580  GUM_OP_MOV(HashTable);
581 
582  // first remove the current content of the hashtable and make
583  // the iterators point to end
584  clear();
585 
586  nodes__ = std::move(table.nodes__);
587  safe_iterators__ = std::move(table.safe_iterators__);
588  alloc__ = std::move(table.alloc__);
589  size__ = table.size__;
590  nb_elements__ = table.nb_elements__;
591  hash_func__ = table.hash_func__;
592  resize_policy__ = table.resize_policy__;
593  key_uniqueness_policy__ = table.key_uniqueness_policy__;
594  begin_index__ = table.begin_index__;
595 
596  table.size__ = 0; // necessary if we wish to perform moves iteratively,
597  // i.e. x = std::move ( y ); y = std::move ( z ); ...
598  }
599 
600  return *this;
601  }
602 
603  template < typename Key, typename Val, typename Alloc >
604  INLINE const typename HashTable< Key, Val, Alloc >::iterator&
606  // note that, here, we know for sure that HashTableIterEnd has been properly
607  // initialized as it is initialized by end4Statics, which is called by
608  // all hashtables' constructors
609  return *(reinterpret_cast< const iterator* >(
610  HashTableIteratorStaticEnd::HashTableIterEnd__));
611  }
612 
613  template < typename Key, typename Val, typename Alloc >
614  INLINE const typename HashTable< Key, Val, Alloc >::const_iterator&
616  // note that, here, we know for sure that HashTableIterEnd has been properly
617  // initialized as it is initialized by end4Statics, which is called by
618  // all hashtables' constructors
619  return *(reinterpret_cast< const const_iterator* >(
620  HashTableIteratorStaticEnd::HashTableIterEnd__));
621  }
622 
623  template < typename Key, typename Val, typename Alloc >
624  INLINE const typename HashTable< Key, Val, Alloc >::const_iterator&
626  // note that, here, we know for sure that HashTableIterEnd has been properly
627  // initialized as it is initialized by end4Statics, which is called by
628  // all hashtables' constructors
629  return *(reinterpret_cast< const const_iterator* >(
630  HashTableIteratorStaticEnd::HashTableIterEnd__));
631  }
632 
633  template < typename Key, typename Val, typename Alloc >
636  // if the table is empty, make the begin and end point to the same element
637  if (nb_elements__ == Size(0))
638  return iterator{end()};
639  else
640  return iterator{*this};
641  }
642 
643  template < typename Key, typename Val, typename Alloc >
646  // if the table is empty, make the begin and end point to the same element
647  if (nb_elements__ == Size(0))
648  return const_iterator{end()};
649  else
650  return const_iterator{*this};
651  }
652 
653  template < typename Key, typename Val, typename Alloc >
656  // if the table is empty, make the begin and end point to the same element
657  if (nb_elements__ == Size(0))
658  return const_iterator{cend()};
659  else
660  return const_iterator{*this};
661  }
662 
663  template < typename Key, typename Val, typename Alloc >
664  INLINE const typename HashTable< Key, Val, Alloc >::iterator_safe&
666  // note that, here, we know for sure that HashTableIterEnd has been properly
667  // initialized as it is initialized by end4Statics, which is called by
668  // all hashtables' constructors
669  return *(reinterpret_cast< const iterator_safe* >(
670  HashTableIteratorStaticEnd::HashTableIterEndSafe__));
671  }
672 
673  template < typename Key, typename Val, typename Alloc >
676  // note that, here, we know for sure that HashTableIterEnd has been properly
677  // initialized as it is initialized by end4Statics, which is called by
678  // all hashtables' constructors
679  return *(reinterpret_cast< const const_iterator_safe* >(
680  HashTableIteratorStaticEnd::HashTableIterEndSafe__));
681  }
682 
683  template < typename Key, typename Val, typename Alloc >
686  // note that, here, we know for sure that HashTableIterEnd has been properly
687  // initialized as it is initialized by end4Statics, which is called by
688  // all hashtables' constructors
689  return *(reinterpret_cast< const const_iterator_safe* >(
690  HashTableIteratorStaticEnd::HashTableIterEndSafe__));
691  }
692 
693  template < typename Key, typename Val, typename Alloc >
696  // if the table is empty, make the begin and end point to the same element
697  if (nb_elements__ == Size(0))
698  return iterator_safe{endSafe()};
699  else
700  return iterator_safe{*this};
701  }
702 
703  template < typename Key, typename Val, typename Alloc >
706  // if the table is empty, make the begin and end point to the same element
707  if (nb_elements__ == Size(0))
708  return const_iterator_safe{endSafe()};
709  else
710  return const_iterator_safe{*this};
711  }
712 
713  template < typename Key, typename Val, typename Alloc >
716  // if the table is empty, make the begin and end point to the same element
717  if (nb_elements__ == Size(0))
718  return const_iterator_safe{cendSafe()};
719  else
720  return const_iterator_safe{*this};
721  }
722 
723  template < typename Key, typename Val, typename Alloc >
724  INLINE Val& HashTable< Key, Val, Alloc >::operator[](const Key& key) {
725  return nodes__[hash_func__(key)][key];
726  }
727 
728  template < typename Key, typename Val, typename Alloc >
729  INLINE const Val&
731  return nodes__[hash_func__(key)][key];
732  }
733 
734  template < typename Key, typename Val, typename Alloc >
735  INLINE Size HashTable< Key, Val, Alloc >::size() const noexcept {
736  return nb_elements__;
737  }
738 
739  template < typename Key, typename Val, typename Alloc >
741  return size__;
742  }
743 
744  template < typename Key, typename Val, typename Alloc >
745  INLINE bool HashTable< Key, Val, Alloc >::exists(const Key& key) const {
746  return nodes__[hash_func__(key)].exists(key);
747  }
748 
749  template < typename Key, typename Val, typename Alloc >
751  const bool new_policy) noexcept {
752  resize_policy__ = new_policy;
753  }
754 
755  template < typename Key, typename Val, typename Alloc >
756  INLINE bool HashTable< Key, Val, Alloc >::resizePolicy() const noexcept {
757  return resize_policy__;
758  }
759 
760  template < typename Key, typename Val, typename Alloc >
762  const bool new_policy) noexcept {
763  key_uniqueness_policy__ = new_policy;
764  }
765 
766  template < typename Key, typename Val, typename Alloc >
768  return key_uniqueness_policy__;
769  }
770 
771  template < typename Key, typename Val, typename Alloc >
773  // new_size must be >= 2 else all the bits of the hash function are lost
774  new_size = std::max(Size(2), new_size);
775 
776  // find the real size for allocation (the smallest power of 2 greater
777  // than or equal to new_size) and get its base-2 logarithm
778  int log_size = hashTableLog2__(new_size);
779  new_size = Size(1) << log_size;
780 
781  // check if the new size is different from the actual size
782  // if not, nothing else need be done
783 
784  if (new_size != size__) {
785  // under automatic resize policy, check if the new size leaves
786  // enough space for storing all the current elements
787  if (!resize_policy__
788  || (nb_elements__
789  <= new_size * HashTableConst::default_mean_val_by_slot)) {
790  // create a new array of nodes__ to store the elements
791  std::vector< HashTableList< Key, Val, Alloc > > new_nodes(new_size);
792 
793  for (auto& list: new_nodes) {
794  list.setAllocator(alloc__);
795  }
796 
797  // set the new hash function
798  hash_func__.resize(new_size);
799 
800  // put all the elements of the current nodes__ array into the new one
801  Bucket* bucket;
802  Size new_hashed_key;
803 
804  for (Size i = Size(0); i < size__; ++i) {
805  while ((bucket = nodes__[i].deb_list__) != nullptr) {
806  // compute the new hashed key
807  new_hashed_key = hash_func__(bucket->key());
808 
809  // remove the bucket from the list of buckets of the current
810  // node vector
811  nodes__[i].deb_list__ = bucket->next;
812 
813  // put the bucket into the new nodes__ vector
814  new_nodes[new_hashed_key].insert(bucket);
815  }
816  }
817 
818  // update the size of the hash table
819  size__ = new_size;
820  begin_index__ = std::numeric_limits< Size >::max();
821 
822  // substitute the current nodes__ array by the new one
823  std::swap(nodes__, new_nodes);
824 
825  // update the iterators
826  for (auto iter: safe_iterators__) {
827  if (iter->bucket__)
828  iter->index__ = hash_func__(iter->bucket__->key());
829  else {
830  iter->next_bucket__ = nullptr;
831  iter->index__ = 0;
832  }
833  }
834  }
835  }
836  }
837 
838  template < typename Key, typename Val, typename Alloc >
839  void
841  Size hash_key = hash_func__(bucket->key());
842 
843  // check that there does not already exist an element with the same key
844  if (key_uniqueness_policy__ && nodes__[hash_key].exists(bucket->key())) {
845  // remove the bucket from memory
846  Key k = bucket->key();
847  alloc__.destroy(bucket);
848  alloc__.deallocate(bucket, 1);
850  "the hashtable contains an element with the same key (" << k
851  << ")");
852  }
853 
854  // check whether there is sufficient space to insert the new pair
855  // if not, resize the current hashtable
856  if (resize_policy__
857  && (nb_elements__ >= size__ * HashTableConst::default_mean_val_by_slot)) {
858  resize(size__ << 1);
859  hash_key = hash_func__(bucket->key());
860  }
861 
862  // add the new pair
863  nodes__[hash_key].insert(bucket);
864  ++nb_elements__;
865 
866  // recompute the index of the beginning of the hashtable if possible
867  // WARNING: if begin_index__ = std::numeric_limits<Size>::max (), we CANNOT
868  // recompute the index because we cannot know whether the current index is
869  // equal to max because there was no element in the hashtable or whether a
870  // previous erase__() has set the index to max.
871  if (begin_index__ < hash_key) { begin_index__ = hash_key; }
872  }
873 
874  template < typename Key, typename Val, typename Alloc >
876  HashTable< Key, Val, Alloc >::insert(const Key& thekey, const Val& theval) {
877  Bucket* bucket = alloc__.allocate(1);
878 
879  try {
880  alloc__.construct(bucket, thekey, theval);
881  } catch (...) {
882  alloc__.deallocate(bucket, 1);
883  throw;
884  }
885 
886  insert__(bucket);
887  return bucket->elt();
888  }
889 
890  template < typename Key, typename Val, typename Alloc >
892  HashTable< Key, Val, Alloc >::insert(Key&& thekey, Val&& theval) {
893  Bucket* bucket = alloc__.allocate(1);
894 
895  try {
896  alloc__.construct(bucket, std::move(thekey), std::move(theval));
897  } catch (...) {
898  alloc__.deallocate(bucket, 1);
899  throw;
900  }
901 
902  insert__(bucket);
903  return bucket->elt();
904  }
905 
906  template < typename Key, typename Val, typename Alloc >
908  HashTable< Key, Val, Alloc >::insert(const std::pair< Key, Val >& elt) {
909  Bucket* bucket = alloc__.allocate(1);
910 
911  try {
912  alloc__.construct(bucket, reinterpret_cast< const value_type& >(elt));
913  } catch (...) {
914  alloc__.deallocate(bucket, 1);
915  throw;
916  }
917 
918  insert__(bucket);
919  return bucket->elt();
920  }
921 
922  template < typename Key, typename Val, typename Alloc >
924  HashTable< Key, Val, Alloc >::insert(std::pair< Key, Val >&& elt) {
925  Bucket* bucket = alloc__.allocate(1);
926 
927  try {
928  alloc__.construct(bucket, std::move(reinterpret_cast< value_type& >(elt)));
929  } catch (...) {
930  alloc__.deallocate(bucket, 1);
931  throw;
932  }
933 
934  insert__(bucket);
935  return bucket->elt();
936  }
937 
938  template < typename Key, typename Val, typename Alloc >
939  template < typename... Args >
942  Bucket* bucket = alloc__.allocate(1);
943 
944  try {
945  alloc__.construct(bucket,
947  std::forward< Args >(args)...);
948  } catch (...) {
949  alloc__.deallocate(bucket, 1);
950  throw;
951  }
952 
953  insert__(bucket);
954  return bucket->elt();
955  }
956 
957  template < typename Key, typename Val, typename Alloc >
960  const Val& default_value) {
961  Bucket* bucket = nodes__[hash_func__(key)].bucket(key);
962 
963  if (bucket == nullptr)
964  return insert(key, default_value).second;
965  else
966  return bucket->val();
967  }
968 
969  template < typename Key, typename Val, typename Alloc >
971  HashTable< Key, Val, Alloc >::getWithDefault(Key&& key, Val&& default_value) {
972  Bucket* bucket = nodes__[hash_func__(key)].bucket(key);
973 
974  if (bucket == nullptr)
975  return insert(std::move(key), std::move(default_value)).second;
976  else
977  return bucket->val();
978  }
979 
980  template < typename Key, typename Val, typename Alloc >
981  INLINE void HashTable< Key, Val, Alloc >::set(const Key& key, const Val& value) {
982  Bucket* bucket = nodes__[hash_func__(key)].bucket(key);
983 
984  if (bucket == nullptr)
985  insert(key, value);
986  else
987  bucket->val() = value;
988  }
989 
990  template < typename Key, typename Val, typename Alloc >
992  Size index) {
993  if (bucket == nullptr) return;
994 
995  // update the registered iterators pointing to this bucket
996  for (auto iter: safe_iterators__) {
997  if (iter->bucket__ == bucket) {
998  iter->operator++();
999  iter->next_bucket__ = iter->bucket__;
1000  iter->bucket__ = nullptr;
1001  } else if (iter->next_bucket__ == bucket) {
1002  iter->bucket__ = bucket;
1003  iter->operator++();
1004  iter->next_bucket__ = iter->bucket__;
1005  iter->bucket__ = nullptr;
1006  }
1007  }
1008 
1009  // remove the element from the nodes__ vector
1010  nodes__[index].erase(bucket);
1011 
1012  --nb_elements__;
1013 
1014  if ((index == begin_index__) && nodes__[index].empty()) {
1015  begin_index__ = std::numeric_limits< Size >::max();
1016  }
1017  }
1018 
1019  template < typename Key, typename Val, typename Alloc >
1020  INLINE void HashTable< Key, Val, Alloc >::erase(const Key& key) {
1021  // get the hashed key
1022  Size hash = hash_func__(key);
1023 
1024  // get the bucket containing the element to erase
1025  HashTableBucket< Key, Val >* bucket = nodes__[hash].bucket(key);
1026 
1027  erase__(bucket, hash);
1028  }
1029 
1030  template < typename Key, typename Val, typename Alloc >
1032  erase__(iter.getBucket__(), iter.getIndex__());
1033  }
1034 
1035  template < typename Key, typename Val, typename Alloc >
1036  INLINE void
1038  erase__(iter.getBucket__(), iter.getIndex__());
1039  }
1040 
1041  template < typename Key, typename Val, typename Alloc >
1042  INLINE void HashTable< Key, Val, Alloc >::eraseByVal(const Val& val) {
1043  for (auto iter = cbegin(); iter != cend(); ++iter)
1044  if (iter.bucket__->val() == val) {
1045  erase__(iter.getBucket__(), iter.getIndex__());
1046  return;
1047  }
1048  }
1049 
1050  template < typename Key, typename Val, typename Alloc >
1051  INLINE void HashTable< Key, Val, Alloc >::reset(const Key& key) {
1052  erase(key);
1053  }
1054 
1055  template < typename Key, typename Val, typename Alloc >
1056  INLINE const Key& HashTable< Key, Val, Alloc >::keyByVal(const Val& val) const {
1057  for (auto iter = begin(); iter != end(); ++iter)
1058  if (iter.bucket__->val() == val) return iter.key();
1059 
1060  GUM_ERROR(NotFound, "not enough elements in the chained list");
1061  }
1062 
1063  template < typename Key, typename Val, typename Alloc >
1064  INLINE const Key& HashTable< Key, Val, Alloc >::key(const Key& key) const {
1065  // get the bucket corresponding to the key
1066  Bucket* bucket = nodes__[hash_func__(key)].bucket(key);
1067 
1068  if (bucket == nullptr) {
1069  GUM_ERROR(NotFound, "key does not belong to the hashtable");
1070  }
1071 
1072  return bucket->key();
1073  }
1074 
1075  template < typename Key, typename Val, typename Alloc >
1077  for (auto iterAll = cbeginSafe(); iterAll != cendSafe(); ++iterAll) {
1078  if (iterAll.bucket__->val() == val) {
1079  erase__(iterAll.bucket__, iterAll.index__);
1080  }
1081  }
1082  }
1083 
1084  template < typename Key, typename Val, typename Alloc >
1085  INLINE bool HashTable< Key, Val, Alloc >::empty() const noexcept {
1086  return (nb_elements__ == Size(0));
1087  }
1088 
1089  template < typename Key, typename Val, typename Alloc >
1090  template < typename Mount, typename OtherAlloc >
1092  Mount (*f)(Val), Size size, bool resize_pol, bool key_uniqueness_pol) const {
1093  // determine the proper size of the hashtable
1094  // by default, the size of the table is set so that the table does not take
1095  // too much space while allowing to add a few elements without needing to
1096  // resize in autmatic resizing mode
1097  if (size == 0) size = std::max(Size(2), nb_elements__ / 2);
1098 
1099  // create a new table
1101  size, resize_pol, key_uniqueness_pol);
1102 
1103  // fill the new hash table
1104  for (auto iter = begin(); iter != end(); ++iter) {
1105  table.insert(iter.key(), f(iter.val()));
1106  }
1107 
1108  return table;
1109  }
1110 
1111  template < typename Key, typename Val, typename Alloc >
1112  template < typename Mount, typename OtherAlloc >
1114  Mount (*f)(Val&), Size size, bool resize_pol, bool key_uniqueness_pol) const {
1115  // determine the proper size of the hashtable
1116  // by default, the size of the table is set so that the table does not take
1117  // too much space while allowing to add a few elements without needing to
1118  // resize in autmatic resizing mode
1119  if (size == Size(0)) size = std::max(Size(2), nb_elements__ / 2);
1120 
1121  // create a new table
1123  size, resize_pol, key_uniqueness_pol);
1124 
1125  // fill the new hash table
1126  for (auto iter = begin(); iter != end(); ++iter) {
1127  table.insert(iter.key(), f(const_cast< Val& >(iter.val())));
1128  }
1129 
1130  return table;
1131  }
1132 
1133  template < typename Key, typename Val, typename Alloc >
1134  template < typename Mount, typename OtherAlloc >
1136  INLINE HashTable< Key, Val, Alloc >::map(Mount (*f)(const Val&),
1137  Size size,
1138  bool resize_pol,
1139  bool key_uniqueness_pol) const {
1140  // determine the proper size of the hashtable
1141  // by default, the size of the table is set so that the table does not take
1142  // too much space while allowing to add a few elements without needing to
1143  // resize in autmatic resizing mode
1144  if (size == Size(0)) size = std::max(Size(2), nb_elements__ / 2);
1145 
1146  // create a new table
1148  size, resize_pol, key_uniqueness_pol);
1149 
1150  // fill the new hash table
1151  for (auto iter = begin(); iter != end(); ++iter) {
1152  table.insert(iter.key(), f(iter.val()));
1153  }
1154 
1155  return table;
1156  }
1157 
1158  template < typename Key, typename Val, typename Alloc >
1159  template < typename Mount, typename OtherAlloc >
1161  const Mount& val, Size size, bool resize_pol, bool key_uniqueness_pol) const {
1162  // determine the proper size of the hashtable
1163  // by default, the size of the table is set so that the table does not take
1164  // too much space while allowing to add a few elements without needing to
1165  // resize in autmatic resizing mode
1166  if (size == Size(0)) size = std::max(Size(2), nb_elements__ / 2);
1167 
1168  // create a new table
1170  size, resize_pol, key_uniqueness_pol);
1171 
1172  // fill the new hash table
1173  for (auto iter = begin(); iter != end(); ++iter) {
1174  table.insert(iter.key(), val);
1175  }
1176 
1177  return table;
1178  }
1179 
1180  template < typename Key, typename Val, typename Alloc >
1181  template < typename OtherAlloc >
1183  const HashTable< Key, Val, OtherAlloc >& from) const {
1184  // checks whether the two hashtables contain the same number of elements
1185  if (from.nb_elements__ != nb_elements__) return false;
1186 
1187  // parse this and check that each element also belongs to from
1188  for (auto iter = begin(); iter != end(); ++iter) {
1189  try {
1190  if (iter.val() != from[iter.key()]) return false;
1191  } catch (NotFound&) { return false; }
1192  }
1193 
1194  return true;
1195  }
1196 
1197  template < typename Key, typename Val, typename Alloc >
1198  template < typename OtherAlloc >
1200  const HashTable< Key, Val, OtherAlloc >& from) const {
1201  return !operator==(from);
1202  }
1203 
1204  template < typename Key, typename Val, typename Alloc >
1205  std::ostream& operator<<(std::ostream& stream,
1206  const HashTableList< Key, Val, Alloc >& list) {
1207  bool deja = false;
1208  stream << "[";
1209 
1210  for (HashTableBucket< Key, Val >* ptr = list.deb_list__; ptr;
1211  ptr = ptr->list.next, deja = true) {
1212  if (deja) stream << " , ";
1213 
1214  stream << ptr->key() << "=>" << ptr->val();
1215  }
1216 
1217  stream << "]";
1218 
1219  return stream;
1220  }
1221 
1222  template < typename Key, typename Val, typename Alloc >
1223  std::ostream& operator<<(std::ostream& stream,
1224  const HashTableList< Key*, Val, Alloc >& list) {
1225  bool deja = false;
1226  stream << "[";
1227 
1228  for (HashTableBucket< Key, Val >* ptr = list.deb_list__; ptr;
1229  ptr = ptr->list.next, deja = true) {
1230  if (deja) stream << " , ";
1231 
1232  stream << ptr->key() << "=>" << ptr->val();
1233  }
1234 
1235  stream << "]";
1236 
1237  return stream;
1238  }
1239 
1240  template < typename Key, typename Val, typename Alloc >
1241  std::ostream& operator<<(std::ostream& stream,
1242  const HashTable< Key, Val, Alloc >& table) {
1243  bool deja = false;
1244  stream << "{";
1245 
1246  for (Size i = Size(0); i < table.size__; ++i)
1247  for (auto ptr = table.nodes__[i].deb_list__; ptr; ptr = ptr->next) {
1248  if (deja) stream << " , ";
1249 
1250  stream << ptr->key() << "=>" << ptr->val();
1251 
1252  deja = true;
1253  }
1254 
1255  stream << "}";
1256 
1257  return stream;
1258  }
1259 
1260  template < typename Key, typename Val, typename Alloc >
1261  std::ostream& operator<<(std::ostream& stream,
1262  const HashTable< Key*, Val, Alloc >& table) {
1263  bool deja = false;
1264  stream << "{";
1265 
1266  for (Size i = Size(0); i < table.size__; ++i)
1267  for (auto ptr = table.nodes__[i].deb_list__; ptr; ptr = ptr->next) {
1268  if (deja) stream << " , ";
1269 
1270  stream << ptr->key() << "=>" << ptr->val();
1271 
1272  deja = true;
1273  }
1274 
1275  stream << "}";
1276 
1277  return stream;
1278  }
1279 
1280  // ===========================================================================
1281  // === SAFE HASH TABLE ITERATORS IMPLEMENTATION ===
1282  // ===========================================================================
1283 
1284  template < typename Key, typename Val >
1285  INLINE void
1287  table__->safe_iterators__.push_back(
1288  const_cast< HashTableConstIteratorSafe< Key, Val >* >(this));
1289  }
1290 
1291  template < typename Key, typename Val >
1292  INLINE void
1294  if (table__ == nullptr) return;
1295 
1296  // find where the iterator is
1297  std::vector< HashTableConstIteratorSafe< Key, Val >* >& iter_vect =
1298  table__->safe_iterators__;
1299 
1300  auto len = iter_vect.size();
1301  for (Size i = Size(0); i < len; ++i) {
1302  if (iter_vect[i] == this) {
1303  iter_vect.erase(iter_vect.begin() + i);
1304  break;
1305  }
1306  }
1307  }
1308 
1309  template < typename Key, typename Val >
1311  // for debugging purposes
1312  GUM_CONSTRUCTOR(HashTableConstIteratorSafe);
1313  }
1314 
1315  template < typename Key, typename Val >
1316  template < typename Alloc >
1318  const HashTable< Key, Val, Alloc >& tab) :
1319  table__{reinterpret_cast< const HashTable< Key, Val >* >(&tab)} {
1320  // for debugging purposes
1321  GUM_CONSTRUCTOR(HashTableConstIteratorSafe);
1322 
1323  // make the hashtable keep track of this iterator
1324  insertIntoSafeList__();
1325 
1326  if (table__->nb_elements__) {
1327  if (table__->begin_index__ != std::numeric_limits< Size >::max()) {
1328  index__ = table__->begin_index__;
1329  bucket__ = table__->nodes__[index__].end_list__;
1330  } else {
1331  // find the element we shall point to from the start of the hashtable
1332  for (Size i = table__->size__ - Size(1);; --i) { // no test on i since
1333  // nb_elements__ != 0
1334  if (table__->nodes__[i].nb_elements__) {
1335  index__ = i;
1336  bucket__ = table__->nodes__[index__].end_list__;
1337  table__->begin_index__ = index__;
1338  break;
1339  }
1340  }
1341  }
1342  }
1343  }
1344 
1345  template < typename Key, typename Val >
1346  template < typename Alloc >
1348  const HashTable< Key, Val, Alloc >& tab, Size ind_elt) :
1349  table__{reinterpret_cast< const HashTable< Key, Val >* >(&tab)} {
1350  Size i;
1351 
1352  // check if we are looking for a begin() and we know for sure its index
1353  if ((ind_elt == Size(0))
1354  && (table__->begin_index__ != std::numeric_limits< Size >::max())) {
1355  index__ = table__->begin_index__;
1356  bucket__ = table__->nodes__[index__].end_list__;
1357  } else {
1358  // check if it is faster to find the ind_eltth element from the start or
1359  // from the end of the hashtable
1360  if (ind_elt < (table__->nb_elements__ >> 1)) {
1361  // find the element we shall point to from the start of the hashtable
1362  for (i = table__->size__ - 1;; --i) { // no test on i since
1363  // ind_elt < table_->nb_elements__
1364  if (table__->nodes__[i].nb_elements__) {
1365  if (ind_elt >= table__->nodes__[i].nb_elements__)
1366  ind_elt -= table__->nodes__[i].nb_elements__;
1367  else {
1368  for (bucket__ = table__->nodes__[i].end_list__; ind_elt;
1369  --ind_elt, bucket__ = bucket__->prev) {}
1370 
1371  index__ = i;
1372  break;
1373  }
1374  }
1375  }
1376  } else {
1377  // ind_elt = the index of the element we should point to
1378  // check if the index passed as parameter is valid
1379  if (ind_elt >= table__->nb_elements__) {
1381  "Not enough elements in the hashtable");
1382  }
1383 
1384  // find the element we shall point to from the end of the hashtable
1385  for (i = 0, ind_elt = table__->nb_elements__ - ind_elt - 1;; ++i) {
1386  if (table__->nodes__[i].nb_elements__) {
1387  if (ind_elt >= table__->nodes__[i].nb_elements__)
1388  ind_elt -= table__->nodes__[i].nb_elements__;
1389  else {
1390  for (bucket__ = table__->nodes__[i].deb_list__; ind_elt;
1391  --ind_elt, bucket__ = bucket__->next) {}
1392 
1393  index__ = i;
1394  break;
1395  }
1396  }
1397  }
1398  }
1399  }
1400 
1401  // for debugging purposes
1402  GUM_CONSTRUCTOR(HashTableConstIteratorSafe);
1403 
1404  // make the hashtable keep track of this iterator
1405  insertIntoSafeList__();
1406  }
1407 
1408  template < typename Key, typename Val >
1411  table__{from.table__},
1412  index__{from.index__}, bucket__{from.bucket__}, next_bucket__{
1413  from.next_bucket__} {
1414  // make the hashtable keep track of this iterator
1415  if (table__ != nullptr) { insertIntoSafeList__(); }
1416 
1417  // for debugging purposes
1418  GUM_CONS_CPY(HashTableConstIteratorSafe);
1419  }
1420 
1421  template < typename Key, typename Val >
1423  const HashTableConstIterator< Key, Val >& from) :
1424  table__{from.table__},
1425  index__{from.index__}, bucket__{from.bucket__} {
1426  // make the hashtable keep track of this iterator
1427  if (table__ != nullptr) { insertIntoSafeList__(); }
1428 
1429  // for debugging purposes
1430  GUM_CONS_CPY(HashTableConstIteratorSafe);
1431  }
1432 
1433  template < typename Key, typename Val >
1436  table__{from.table__},
1437  index__{from.index__}, bucket__{from.bucket__}, next_bucket__{
1438  from.next_bucket__} {
1439  GUM_CONS_MOV(HashTableConstIteratorSafe);
1440 
1441  // find "from" in the hashtable's list of safe iterators and substitute
1442  // it by this
1443  if (table__ != nullptr) {
1444  std::vector< HashTableConstIteratorSafe< Key, Val >* >& vect =
1445  table__->safe_iterators__;
1446 
1447  for (auto ptr = vect.rbegin(); ptr != vect.rend(); ++ptr) {
1448  if (*ptr == &from) {
1449  *ptr = this;
1450  from.table__ = nullptr;
1451  break;
1452  }
1453  }
1454  }
1455  }
1456 
1457  template < typename Key, typename Val >
1458  INLINE
1460  Val >::~HashTableConstIteratorSafe() noexcept {
1461  // for debugging purposes
1462  GUM_DESTRUCTOR(HashTableConstIteratorSafe);
1463 
1464  // remove the iterator from the table's iterator list
1465  removeFromSafeList__();
1466  }
1467 
1468  template < typename Key, typename Val >
1472  // here, no need to avoid self assignment: this would slow down normal
1473  // assignments and, in any case, this would not result in an iterator in
1474  // an incoherent state
1475  // check if the current hashtable is different from that of "from". In such
1476  // a case, we shall remove the iterator from its current hashtable
1477  // iterator's
1478  // list and add it to the new hashtable iterator's list
1479  if (table__ != from.table__) {
1480  // remove the iterator from its hashtable iterator's list'
1481  removeFromSafeList__();
1482 
1483  table__ = from.table__;
1484 
1485  // add to the new table
1486  if (table__) { insertIntoSafeList__(); }
1487  }
1488 
1489  index__ = from.index__;
1490  bucket__ = from.bucket__;
1491  next_bucket__ = from.next_bucket__;
1492 
1493  return *this;
1494  }
1495 
1496  template < typename Key, typename Val >
1499  const HashTableConstIterator< Key, Val >& from) {
1500  // here, no need to avoid self assignment: this would slow down normal
1501  // assignments and, in any case, this would not result in an iterator in
1502  // an incoherent state
1503  // check if the current hashtable is different from that of "from". In such
1504  // a case, we shall remove the iterator from its current hashtable
1505  // iterator's
1506  // list and add it to the new hashtable iterator's list
1507  if (table__ != from.table__) {
1508  // remove the iterator from its hashtable iterator's list'
1509  removeFromSafeList__();
1510 
1511  table__ = from.table__;
1512 
1513  // add to the new table
1514  if (table__) { insertIntoSafeList__(); }
1515  }
1516 
1517  index__ = from.index__;
1518  bucket__ = from.bucket__;
1519  next_bucket__ = nullptr;
1520 
1521  return *this;
1522  }
1523 
1524  template < typename Key, typename Val >
1527  HashTableConstIteratorSafe< Key, Val >&& from) noexcept {
1528  // here, no need to avoid self assignment: this would slow down normal
1529  // assignments and, in any case, this would not result in an iterator in
1530  // an incoherent state
1531  // check if the current hashtable is different from that of "from". In such
1532  // a case, we shall remove the iterator from its current hashtable
1533  // iterator's
1534  // list and add it to the new hashtable iterator's list
1535  if (table__ != from.table__) {
1536  // remove the iterator from its hashtable iterator's list'
1537  removeFromSafeList__();
1538 
1539  if (from.table__ != nullptr) {
1540  // substitute from by this in the list of safe iterators
1541  std::vector< HashTableConstIteratorSafe< Key, Val >* >& vect =
1542  from.table__->safe_iterators__;
1543 
1544  for (auto ptr = vect.rbegin(); ptr != vect.rend(); ++ptr) {
1545  if (*ptr == &from) {
1546  *ptr = this;
1547  break;
1548  }
1549  }
1550  }
1551 
1552  table__ = from.table__;
1553  from.table__ = nullptr;
1554  }
1555 
1556  index__ = from.index__;
1557  bucket__ = from.bucket__;
1558  next_bucket__ = from.next_bucket__;
1559 
1560  return *this;
1561  }
1562 
1563  template < typename Key, typename Val >
1566  if (bucket__ != nullptr)
1567  return bucket__->key();
1568  else {
1569  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object");
1570  }
1571  }
1572 
1573  template < typename Key, typename Val >
1576  if (bucket__ != nullptr)
1577  return bucket__->val();
1578  else {
1579  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object");
1580  }
1581  }
1582 
1583  template < typename Key, typename Val >
1585  // remove the iterator from the table's iterator list
1586  removeFromSafeList__();
1587 
1588  // set its table as well as the element it points to to 0
1589  table__ = nullptr;
1590  bucket__ = nullptr;
1591  next_bucket__ = nullptr;
1592  index__ = Size(0);
1593  }
1594 
1595  // WARNING: never inline this function: this result in g++4.3.3 producing a
1596  // code that segfaults.
1597  template < typename Key, typename Val >
1600  // if bucket__ != nullptr then use it, else use next_bucket
1601  if (bucket__ == nullptr) {
1602  // note that this case only happens when the iterator pointed to an
1603  // element
1604  // that has just been erased. Fortunately, in this case, the Hashtable's
1605  // erase functions update appropriately the next_bucket__ and index__
1606  // fields.
1607  bucket__ = next_bucket__;
1608  next_bucket__ = nullptr;
1609  } else {
1610  // ok, here we can use bucket__ as a starting point
1611 
1612  // if we are not pointing on the first element of the chained list, just
1613  // point to the preceding bucket in this list
1614  if (bucket__->prev) {
1615  bucket__ = bucket__->prev;
1616  // here, no need to update next_bucket__, which is compulsorily
1617  // equal to nullptr, nor index__ which has not changed.
1618  } else {
1619  // ok, here we are on the beginning of a chained list,
1620  // so 2 cases can obtain:
1621  // 1/ index = 0 : then we have reached the end of the hashtable
1622  // 2/ index != 0 => we must search for a new slot containing elements
1623 
1624  // case 1:
1625  if (index__ == Size(0)) {
1626  bucket__ = nullptr;
1627  // we are thus at the end() of the hashTable
1628  }
1629  // case 2:
1630  else {
1631  // arrived here, we need to parse the hash table until we find a new
1632  // bucket because we are pointing on a chained list with no more
1633  // element
1634  // to the left of the current element
1635  if (index__ > Size(0)) {
1636  for (Size i = index__ - Size(1); i > Size(0); --i) {
1637  if (table__->nodes__[i].nb_elements__) {
1638  index__ = i;
1639  bucket__ = table__->nodes__[i].end_list__;
1640  return *this;
1641  }
1642  }
1643  }
1644 
1645  if (table__->nodes__[0].nb_elements__)
1646  bucket__ = table__->nodes__[0].end_list__;
1647  else
1648  bucket__ = nullptr;
1649 
1650  index__ = 0;
1651  }
1652  }
1653  }
1654 
1655  return *this;
1656  }
1657 
1658  template < typename Key, typename Val >
1661  if ((nb == Size(0)) || (table__ == nullptr)) return *this;
1662 
1663  // if bucket__ != nullptr then use it, else use next_bucket
1664  if (bucket__ == nullptr) {
1665  // note that this case only happens when the iterator pointed to an
1666  // element
1667  // that has just been erased. Fortunately, in this case, the Hashtable's
1668  // erase functions update appropriately the next_bucket__ and index__
1669  // fields.
1670  bucket__ = next_bucket__;
1671  next_bucket__ = nullptr;
1672  --nb;
1673  }
1674 
1675  // ok, here we can use bucket__ as a starting point: parse all the elements
1676  // of the current chained list
1677  for (; nb && bucket__ != nullptr; --nb, bucket__ = bucket__->prev) {}
1678 
1679  if (bucket__ != nullptr) return *this;
1680 
1681  // here, we shall skip all the chained list that have not sufficiently
1682  // many elements
1683  --index__;
1684 
1685  for (; index__ < table__->size__
1686  && nb >= table__->nodes__[index__].nb_elements__;
1687  nb -= table__->nodes__[index__].nb_elements__, --index__) {}
1688 
1689  // here: either index__ >= table__->size__, which means that we did not find
1690  // the element we looked for, i.e., we are at the end of the hashtable, or
1691  // nb < table__->nodes__[index__].nb_elements__, and we should parse the
1692  // chained list to get the element (which, we know for sure, exists)
1693  if (index__ >= table__->size__) {
1694  index__ = Size(0);
1695  return *this;
1696  }
1697 
1698  for (bucket__ = table__->nodes__[index__].end_list__; nb;
1699  --nb, bucket__ = bucket__->prev) {}
1700 
1701  return *this;
1702  }
1703 
1704  template < typename Key, typename Val >
1707  return HashTableConstIteratorSafe< Key, Val >{*this} += nb;
1708  }
1709 
1710  template < typename Key, typename Val >
1712  const HashTableConstIteratorSafe< Key, Val >& from) const noexcept {
1713  return ((bucket__ != from.bucket__) || (index__ != from.index__));
1714  }
1715 
1716  template < typename Key, typename Val >
1718  const HashTableConstIteratorSafe< Key, Val >& from) const noexcept {
1719  return ((bucket__ == from.bucket__) && (index__ == from.index__));
1720  }
1721 
1722  template < typename Key, typename Val >
1725  if (bucket__)
1726  return bucket__->elt();
1727  else {
1728  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object");
1729  }
1730  }
1731 
1732  template < typename Key, typename Val >
1735  return bucket__;
1736  }
1737 
1738  template < typename Key, typename Val >
1740  return index__;
1741  }
1742 
1743  // ===========================================================================
1744  // === SAFE HASH TABLE ITERATORS IMPLEMENTATION ===
1745  // ===========================================================================
1746 
1747  template < typename Key, typename Val >
1749  HashTableConstIteratorSafe< Key, Val >() {
1750  GUM_CONSTRUCTOR(HashTableIteratorSafe);
1751  }
1752 
1753  template < typename Key, typename Val >
1754  template < typename Alloc >
1756  const HashTable< Key, Val, Alloc >& tab) :
1757  HashTableConstIteratorSafe< Key, Val >(tab) {
1758  GUM_CONSTRUCTOR(HashTableIteratorSafe);
1759  }
1760 
1761  template < typename Key, typename Val >
1762  template < typename Alloc >
1764  const HashTable< Key, Val, Alloc >& tab, Size ind_elt) :
1765  HashTableConstIteratorSafe< Key, Val >(tab, ind_elt) {
1766  GUM_CONSTRUCTOR(HashTableIteratorSafe);
1767  }
1768 
1769  template < typename Key, typename Val >
1771  const HashTableIteratorSafe< Key, Val >& from) :
1772  HashTableConstIteratorSafe< Key, Val >(from) {
1773  GUM_CONS_CPY(HashTableIteratorSafe);
1774  }
1775 
1776  template < typename Key, typename Val >
1778  const HashTableIterator< Key, Val >& from) :
1779  HashTableConstIteratorSafe< Key, Val >(from) {
1780  GUM_CONS_CPY(HashTableIteratorSafe);
1781  }
1782 
1783  template < typename Key, typename Val >
1785  HashTableIteratorSafe< Key, Val >&& from) noexcept :
1786  HashTableConstIteratorSafe< Key, Val >(std::move(from)) {
1787  GUM_CONS_MOV(HashTableIteratorSafe);
1788  }
1789 
1790  template < typename Key, typename Val >
1792  GUM_DESTRUCTOR(HashTableIteratorSafe);
1793  }
1794 
1795  template < typename Key, typename Val >
1798  return const_cast< Val& >(HashTableConstIteratorSafe< Key, Val >::val());
1799  }
1800 
1801  template < typename Key, typename Val >
1804  const HashTableIteratorSafe< Key, Val >& from) {
1805  GUM_OP_CPY(HashTableIteratorSafe);
1807  return *this;
1808  }
1809 
1810  template < typename Key, typename Val >
1813  const HashTableIterator< Key, Val >& from) {
1814  GUM_OP_CPY(HashTableIteratorSafe);
1816  return *this;
1817  }
1818 
1819  template < typename Key, typename Val >
1822  HashTableIteratorSafe< Key, Val >&& from) noexcept {
1824  return *this;
1825  }
1826 
1827  template < typename Key, typename Val >
1831  return *this;
1832  }
1833 
1834  template < typename Key, typename Val >
1838  return *this;
1839  }
1840 
1841  template < typename Key, typename Val >
1845  iter += nb;
1846  return iter;
1847  }
1848 
1849  template < typename Key, typename Val >
1851  const HashTableIteratorSafe< Key, Val >& from) const noexcept {
1853  }
1854 
1855  template < typename Key, typename Val >
1857  const HashTableIteratorSafe< Key, Val >& from) const noexcept {
1859  }
1860 
1861  template < typename Key, typename Val >
1864  return const_cast< Val& >(HashTableConstIteratorSafe< Key, Val >::operator*());
1865  }
1866 
1867  template < typename Key, typename Val >
1868  INLINE const typename HashTableIteratorSafe< Key, Val >::value_type&
1871  }
1872 
1873  // ===========================================================================
1874  // === UNSAFE HASH TABLE CONST ITERATORS IMPLEMENTATION ===
1875  // ===========================================================================
1876 
1877  template < typename Key, typename Val >
1879  GUM_CONSTRUCTOR(HashTableConstIterator);
1880  }
1881 
1882  template < typename Key, typename Val >
1883  template < typename Alloc >
1885  const HashTable< Key, Val, Alloc >& tab) noexcept :
1886  table__{reinterpret_cast< const HashTable< Key, Val >* >(&tab)} {
1887  // for debugging purposes
1888  GUM_CONSTRUCTOR(HashTableConstIterator);
1889 
1890  if (table__->nb_elements__) {
1891  if (table__->begin_index__ != std::numeric_limits< Size >::max()) {
1892  index__ = table__->begin_index__;
1893  bucket__ = table__->nodes__[index__].end_list__;
1894  } else {
1895  // find the element we shall point to from the start of the hashtable
1896  for (Size i = table__->size__ - Size(1);; --i) { // no test on i since
1897  // nb_elements__ != 0
1898  if (table__->nodes__[i].nb_elements__) {
1899  index__ = i;
1900  bucket__ = table__->nodes__[index__].end_list__;
1901  table__->begin_index__ = index__;
1902  break;
1903  }
1904  }
1905  }
1906  }
1907  }
1908 
1909  template < typename Key, typename Val >
1910  template < typename Alloc >
1912  const HashTable< Key, Val, Alloc >& tab, Size ind_elt) :
1913  table__{reinterpret_cast< const HashTable< Key, Val >* >(&tab)} {
1914  Size i;
1915 
1916  // check if we are looking for a begin() and we know for sure its index
1917  if ((ind_elt == Size(0))
1918  && (table__->begin_index__ != std::numeric_limits< Size >::max())) {
1919  index__ = table__->begin_index__;
1920  bucket__ = table__->nodes__[index__].end_list__;
1921  } else {
1922  // check if it is faster to find the ind_eltth element from the start or
1923  // from the end of the hashtable
1924  if (ind_elt < (table__->nb_elements__ >> 1)) {
1925  // find the element we shall point to from the start of the hashtable
1926  for (i = table__->size__ - 1;; --i) { // no test on i since
1927  // ind_elt < table_->nb_elements__
1928  if (table__->nodes__[i].nb_elements__) {
1929  if (ind_elt >= table__->nodes__[i].nb_elements__)
1930  ind_elt -= table__->nodes__[i].nb_elements__;
1931  else {
1932  for (bucket__ = table__->nodes__[i].end_list__; ind_elt;
1933  --ind_elt, bucket__ = bucket__->prev) {}
1934 
1935  index__ = i;
1936  break;
1937  }
1938  }
1939  }
1940  } else {
1941  // ind_elt = the index of the element we should point to
1942  // check if the index passed as parameter is valid
1943  if (ind_elt >= table__->nb_elements__) {
1945  "Not enough elements in the hashtable");
1946  }
1947 
1948  // find the element we shall point to from the end of the hashtable
1949  for (i = 0, ind_elt = table__->nb_elements__ - ind_elt - 1;; ++i) {
1950  if (table__->nodes__[i].nb_elements__) {
1951  if (ind_elt >= table__->nodes__[i].nb_elements__)
1952  ind_elt -= table__->nodes__[i].nb_elements__;
1953  else {
1954  for (bucket__ = table__->nodes__[i].deb_list__; ind_elt;
1955  --ind_elt, bucket__ = bucket__->next) {}
1956 
1957  index__ = i;
1958  break;
1959  }
1960  }
1961  }
1962  }
1963  }
1964 
1965  // for debugging purposes
1966  GUM_CONSTRUCTOR(HashTableConstIterator);
1967  }
1968 
1969  template < typename Key, typename Val >
1971  const HashTableConstIterator< Key, Val >& from) noexcept :
1972  table__{from.table__},
1973  index__{from.index__}, bucket__{from.bucket__} {
1974  GUM_CONS_CPY(HashTableConstIterator);
1975  }
1976 
1977  template < typename Key, typename Val >
1979  HashTableConstIterator< Key, Val >&& from) noexcept :
1980  table__{from.table__},
1981  index__{from.index__}, bucket__{from.bucket__} {
1982  GUM_CONS_MOV(HashTableConstIterator);
1983  }
1984 
1985  template < typename Key, typename Val >
1987  // for debugging purposes
1988  GUM_DESTRUCTOR(HashTableConstIterator);
1989  }
1990 
1991  template < typename Key, typename Val >
1994  const HashTableConstIterator< Key, Val >& from) noexcept {
1995  // here, no need to avoid self assignment: this would slow down normal
1996  // assignments and, in any case, this would not result in an iterator in
1997  // an incoherent state
1998  table__ = from.table__;
1999  index__ = from.index__;
2000  bucket__ = from.bucket__;
2001 
2002  return *this;
2003  }
2004 
2005  template < typename Key, typename Val >
2008  HashTableConstIterator< Key, Val >&& from) noexcept {
2009  // here, no need to avoid self assignment: this would slow down normal
2010  // assignments and, in any case, this would not result in an iterator in
2011  // an incoherent state
2012  table__ = from.table__;
2013  index__ = from.index__;
2014  bucket__ = from.bucket__;
2015 
2016  return *this;
2017  }
2018 
2019  template < typename Key, typename Val >
2020  INLINE const typename HashTableConstIterator< Key, Val >::key_type&
2022  if (bucket__)
2023  return bucket__->pair.first;
2024  else {
2025  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object");
2026  }
2027  }
2028 
2029  template < typename Key, typename Val >
2032  if (bucket__)
2033  return bucket__->val();
2034  else {
2035  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object");
2036  }
2037  }
2038 
2039  template < typename Key, typename Val >
2041  table__ = nullptr;
2042  bucket__ = nullptr;
2043  index__ = 0;
2044  }
2045 
2046  template < typename Key, typename Val >
2049  // if bucket__ == nullptr then we are at the end of the hashtable
2050  if (bucket__ == nullptr) return *this;
2051 
2052  // if we are not pointing on the first element of the chained list, just
2053  // point to the next bucket in this list
2054  if (bucket__->prev) {
2055  bucket__ = bucket__->prev;
2056  // here, no need to update index__ which has not changed.
2057  } else {
2058  // ok, here we are on the end of a chained list,
2059  // so 2 cases can obtain:
2060  // 1/ index = 0 : then we have reached the end of the hashtable
2061  // 2/ index != 0 => we must search for a new slot containing elements
2062 
2063  // case 1:
2064  if (index__ == Size(0)) {
2065  bucket__ = nullptr;
2066  // we are thus at the end() of the hashTable
2067  }
2068 
2069  // case 2:
2070  else {
2071  // arrived here, we need to parse the hash table until we find a new
2072  // bucket because we are pointing on a chained list with no more element
2073  // to the right of the current element
2074  for (Size i = index__ - Size(1); i; --i) {
2075  if (table__->nodes__[i].nb_elements__) {
2076  index__ = i;
2077  bucket__ = table__->nodes__[i].end_list__;
2078  return *this;
2079  }
2080  }
2081 
2082  if (table__->nodes__[0].nb_elements__)
2083  bucket__ = table__->nodes__[0].end_list__;
2084  else
2085  bucket__ = nullptr;
2086 
2087  index__ = Size(0);
2088  }
2089  }
2090 
2091  return *this;
2092  }
2093 
2094  template < typename Key, typename Val >
2097  if ((nb == 0) || (table__ == nullptr) || (bucket__ == nullptr)) return *this;
2098 
2099  // ok, here we can use bucket__ as a starting point: parse all the elements
2100  // of the current chained list
2101  for (; nb && bucket__ != nullptr; --nb, bucket__ = bucket__->prev) {}
2102 
2103  if (bucket__ != nullptr) return *this;
2104 
2105  // here, we shall skip all the chained list that have not sufficiently
2106  // many elements
2107  --index__;
2108 
2109  for (; index__ < table__->size__
2110  && nb >= table__->nodes__[index__].nb_elements__;
2111  nb -= table__->nodes__[index__].nb_elements__, --index__) {}
2112 
2113  // here: either index__ >= table__->size__, which means that we did not find
2114  // the element we looked for, i.e., we are at the end of the hashtable, or
2115  // nb < table__->nodes__[index__].nb_elements__, and we should parse the
2116  // chained list to get the element (which, we know for sure, exists)
2117  if (index__ >= table__->size__) {
2118  index__ = 0;
2119  return *this;
2120  }
2121 
2122  for (bucket__ = table__->nodes__[index__].end_list__; nb;
2123  --nb, bucket__ = bucket__->prev) {}
2124 
2125  return *this;
2126  }
2127 
2128  template < typename Key, typename Val >
2131  return HashTableConstIterator< Key, Val >{*this} += nb;
2132  }
2133 
2134  template < typename Key, typename Val >
2136  const HashTableConstIterator< Key, Val >& from) const noexcept {
2137  return (bucket__ != from.bucket__);
2138  }
2139 
2140  template < typename Key, typename Val >
2142  const HashTableConstIterator< Key, Val >& from) const noexcept {
2143  return (bucket__ == from.bucket__);
2144  }
2145 
2146  template < typename Key, typename Val >
2147  INLINE const typename HashTableConstIterator< Key, Val >::value_type&
2149  if (bucket__)
2150  return bucket__->elt();
2151  else {
2152  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object");
2153  }
2154  }
2155 
2156  template < typename Key, typename Val >
2157  INLINE typename HashTable< Key, Val >::Bucket*
2159  return bucket__;
2160  }
2161 
2162  template < typename Key, typename Val >
2164  return index__;
2165  }
2166 
2167  // ===========================================================================
2168  // === UNSAFE HASH TABLE ITERATORS IMPLEMENTATION ===
2169  // ===========================================================================
2170 
2171  template < typename Key, typename Val >
2173  HashTableConstIterator< Key, Val >() {
2174  GUM_CONSTRUCTOR(HashTableIterator);
2175  }
2176 
2177  template < typename Key, typename Val >
2178  template < typename Alloc >
2180  const HashTable< Key, Val, Alloc >& tab) noexcept :
2182  GUM_CONSTRUCTOR(HashTableIterator);
2183  }
2184 
2185  template < typename Key, typename Val >
2186  template < typename Alloc >
2188  const HashTable< Key, Val, Alloc >& tab, Size ind_elt) :
2189  HashTableConstIterator< Key, Val >(tab, ind_elt) {
2190  GUM_CONSTRUCTOR(HashTableIterator);
2191  }
2192 
2193  template < typename Key, typename Val >
2195  const HashTableIterator< Key, Val >& from) noexcept :
2197  GUM_CONS_CPY(HashTableIterator);
2198  }
2199 
2200  template < typename Key, typename Val >
2202  HashTableIterator< Key, Val >&& from) noexcept :
2203  HashTableConstIterator< Key, Val >(std::move(from)) {
2204  GUM_CONS_MOV(HashTableIterator);
2205  }
2206 
2207  template < typename Key, typename Val >
2209  GUM_DESTRUCTOR(HashTableIterator);
2210  }
2211 
2212  template < typename Key, typename Val >
2215  if (this->bucket__)
2216  return this->bucket__->val();
2217  else {
2218  GUM_ERROR(UndefinedIteratorValue, "Accessing a nullptr object");
2219  }
2220  }
2221 
2222  template < typename Key, typename Val >
2224  const HashTableIterator< Key, Val >& from) noexcept {
2226  return *this;
2227  }
2228 
2229  template < typename Key, typename Val >
2231  HashTableIterator< Key, Val >&& from) noexcept {
2233  return *this;
2234  }
2235 
2236  template < typename Key, typename Val >
2240  return *this;
2241  }
2242 
2243  template < typename Key, typename Val >
2247  return *this;
2248  }
2249 
2250  template < typename Key, typename Val >
2253  HashTableIterator< Key, Val > iter{*this};
2254  iter += nb;
2255  return iter;
2256  }
2257 
2258  template < typename Key, typename Val >
2260  const HashTableIterator< Key, Val >& from) const noexcept {
2262  }
2263 
2264  template < typename Key, typename Val >
2266  const HashTableIterator< Key, Val >& from) const noexcept {
2268  }
2269 
2270  template < typename Key, typename Val >
2273  return const_cast< value_type& >(
2275  }
2276 
2277  template < typename Key, typename Val >
2278  INLINE const typename HashTableIterator< Key, Val >::value_type&
2281  }
2282 
2283 } /* namespace gum */
void resize(Size new_size)
Changes the number of slots in the &#39;nodes&#39; vector of the hash table.
BucketAllocator * alloc_bucket__
The allocator of the containing hashTable.
Definition: hashTable.h:543
Key & key()
Returns the key part of the pair.
Definition: hashTable.h:281
Key key_type
Types for STL compliance.
Definition: hashTable.h:1923
const mapped_type & val() const
Returns the mapped value pointed to by the iterator.
Unsafe Const Iterators for hashtablesHashTableConstIterator provides a fast but unsafe way to parse H...
Definition: hashTable.h:2465
Size size() const noexcept
Returns the number of elements stored into the hashtable.
Val mapped_type
Types for STL compliance.
Definition: hashTable.h:1924
const key_type & key() const
Returns the key pointed to by the iterator.
bool resize_policy__
Is resizing performed automatically?
Definition: hashTable.h:1730
Unsafe Iterators for hashtablesHashTableIterator provides a fast but unsafe way to parse HashTables...
Definition: hashTable.h:2750
HashTableBucket< Key, Val > * bucket__
The bucket in the chained list pointed to by the iterator.
Definition: hashTable.h:2135
Safe Const Iterators for hashtables.
Definition: hashTable.h:1918
bool key_uniqueness_policy__
Shall we check for key uniqueness in the table?
Definition: hashTable.h:1733
void erase(Bucket *ptr)
Removes an element from this chained list.
STL namespace.
Size getIndex__() const noexcept
Returns the index in the hashtable&#39;s node vector pointed to by the iterator.
bool exists(const Key &key) const
Checks whether there exists an element with a given key in the hashtable.
void swap(HashTable< LpCol, double > *&a, HashTable< LpCol, double > *&b)
Swap the addresses of two pointers to hashTables.
const Key & key(const Key &key) const
Returns a reference on a given key.
HashTableBucket< Key, Val > * next_bucket__
the bucket we should start from when we decide to do a ++.
Definition: hashTable.h:2145
Safe Iterators for hashtables.
Definition: hashTable.h:2220
std::vector< HashTableList< Key, Val, Alloc > > nodes__
The hash table is represented as a vector of chained lists.
Definition: hashTable.h:1718
Copyright 2005-2020 Pierre-Henri WUILLEMIN() & Christophe GONZALES() info_at_agrum_dot_org.
Definition: agrum.h:25
Size index__
the index of the chained list pointed to by the iterator in the array nodes__ of the hash table...
Definition: hashTable.h:2132
HashTable< Key, Val >::Bucket * bucket__
The bucket in the chained list pointed to by the iterator.
Definition: hashTable.h:2681
const mapped_type & val() const
Returns the mapped value pointed to by the iterator.
The class for generic Hash Tables.
Definition: hashTable.h:679
std::pair< const Key, Val > value_type
types for STL compliance
Definition: hashTable.h:311
Key key_type
Types for STL compliance.
Definition: hashTable.h:2470
unsigned int hashTableLog2__(const Size nb)
Returns the size in bits - 1 necessary to store the smallest power of 2 greater than or equal to nb...
std::ostream & operator<<(std::ostream &output, const BayesNet< GUM_SCALAR > &bn)
Prints map&#39;s DAG in output using the Graphviz-dot format.
Definition: BayesNet_tpl.h:631
Val mapped_type
Types for STL compliance.
Definition: hashTable.h:2471
Val mapped_type
types for STL compliance
Definition: hashTable.h:2756
Size begin_index__
Returns where the begin index should be.
Definition: hashTable.h:1749
std::pair< const Key, Val > value_type
Types for STL compliance.
Definition: hashTable.h:2227
std::pair< const Key, Val > value_type
Types for STL compliance.
Definition: hashTable.h:1925
LpExpr operator+(LpExpr &&lhs, const T2 &rhs)
Overload of operator + between anything ( a scalar, a variable or an expression ) and anything except...
HashTableBucket< Key, Val > * getBucket__() const noexcept
Returns the current iterator&#39;s bucket.
Val mapped_type
Types for STL compliance.
Definition: hashTable.h:684
bool operator==(const TiXmlString &a, const TiXmlString &b)
Definition: tinystr.h:243
HashTableBucket< Key, Val > * deb_list__
A pointer on the first element of the chained list.
Definition: hashTable.h:534
Val mapped_type
Types for STL compliance.
Definition: hashTable.h:2226
Val mapped_type
types for STL compliance
Definition: hashTable.h:310
Val & val()
Returns the value part of the pair.
Definition: hashTable.h:287
std::pair< const Key, Val > value_type
Types for STL compliance.
Definition: hashTable.h:685
HashTableBucket< Key, Val > * next
A pointer toward the next bucket in the gum::HashTableList.
Definition: hashTable.h:210
LpExpr operator*(const SCALAR &lhs, const LpCol &rhs)
Overload of operator * between a scalar and a variable.
std::pair< const Key, Val > value_type
Types for STL compliance.
Definition: hashTable.h:2472
Size nb_elements__
Number of elements of type Val stored in the hash table.
Definition: hashTable.h:1724
bool operator!=(const TiXmlString &a, const TiXmlString &b)
Definition: tinystr.h:251
const HashTable< Key, Val > * table__
The hash table the iterator is pointing to.
Definition: hashTable.h:2672
A chained list used by gum::HashTable.
Definition: hashTable.h:305
void copy__(const HashTableList< Key, Val, OtherAlloc > &from)
A function used to perform copies of HashTableLists.
Definition: hashTable_tpl.h:45
friend class HashTableList
Friend for faster access.
Definition: hashTable.h:517
HashTableBucket< Key, Val > * prev
A pointer toward the previous bucket in the gum::HashTableList.
Definition: hashTable.h:207
Bucket * bucket(const Key &key) const
A method to get the bucket corresponding to a given key.
Size size__
The number of nodes in vector &#39;__nodes&#39;.
Definition: hashTable.h:1721
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
Size nb_elements__
The number of elements in the chained list.
Definition: hashTable.h:540
const HashTable< Key, Val > * table__
The hash table the iterator is pointing to.
Definition: hashTable.h:2126
Size index__
The index of the chained list pointed by the iterator in the array of nodes of the hash table...
Definition: hashTable.h:2678
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.
typename Alloc::template rebind< Bucket >::other BucketAllocator
The Bucket allocator.
Definition: hashTable.h:322
Copyright 2005-2020 Pierre-Henri WUILLEMIN() & Christophe GONZALES() info_at_agrum_dot_org.
mapped_type & val()
Returns the mapped value pointed to by the iterator.
std::pair< const Key, Val > & elt()
Returns the pair stored in this bucket.
Definition: hashTable.h:275
#define GUM_ERROR(type, msg)
Definition: exceptions.h:55
std::pair< const Key, Val > value_type
types for STL compliance
Definition: hashTable.h:2757