aGrUM  0.15.1
set_tpl.h
Go to the documentation of this file.
1 
30 #include <agrum/core/set.h>
31 
32 namespace gum {
33 
34  // ===========================================================================
35  // === SAFE SET ITERATORS ===
36  // ===========================================================================
37 
38  // default constructor: the iterator points toward nothing
39  template < typename Key >
41  GUM_CONSTRUCTOR(SetIteratorSafe);
42  }
43 
44  // creates an iterator for a given set
45  template < typename Key >
46  template < typename Alloc >
48  Position pos) :
49  __ht_iter{pos == SetIteratorSafe< Key >::END ? set.__inside.cendSafe()
50  : set.__inside.cbeginSafe()} {
51  GUM_CONSTRUCTOR(SetIteratorSafe);
52  }
53 
54  // copy constructor
55  template < typename Key >
56  INLINE
58  __ht_iter{iter.__ht_iter} {
59  GUM_CONS_CPY(SetIteratorSafe);
60  }
61 
62  // copy constructor
63  template < typename Key >
65  __ht_iter{iter.__ht_iter} {
66  GUM_CONS_CPY(SetIteratorSafe);
67  }
68 
69  // move constructor
70  template < typename Key >
72  __ht_iter{std::move(from.__ht_iter)} {
73  GUM_CONS_MOV(SetIteratorSafe);
74  }
75 
76  // destructor
77  template < typename Key >
79  GUM_DESTRUCTOR(SetIteratorSafe);
80  }
81 
82  // assignment operator
83  template < typename Key >
86  __ht_iter = from.__ht_iter;
87  return *this;
88  }
89 
90  // assignment operator
91  template < typename Key >
94  __ht_iter = from.__ht_iter;
95  return *this;
96  }
97 
98  // move operator
99  template < typename Key >
102  __ht_iter = std::move(from.__ht_iter);
103  return *this;
104  }
105 
106  // increments the iterator
107  template < typename Key >
109  // note that, if the hashtable's iterator points toward nothing, the
110  // hashtable's iterator incrementation will do nothing. In particular, it
111  // will not segfault.
112  ++__ht_iter;
113  return *this;
114  }
115 
116  // makes the iterator point to i elements further in the set
117  template < typename Key >
119  operator+=(Size nb) noexcept {
120  __ht_iter += nb;
121  return *this;
122  }
123 
124  // returns a new iterator
125  template < typename Key >
127  return SetIteratorSafe< Key >{*this} += nb;
128  }
129 
130  // indicates whether two iterators point to different elements or sets
131  template < typename Key >
132  INLINE bool SetIteratorSafe< Key >::
133  operator!=(const SetIteratorSafe< Key >& from) const noexcept {
134  return __ht_iter != from.__ht_iter;
135  }
136 
137  // indicates whether two iterators point toward the same element of a same
138  // set
139  template < typename Key >
140  INLINE bool SetIteratorSafe< Key >::
141  operator==(const SetIteratorSafe< Key >& from) const noexcept {
142  return __ht_iter == from.__ht_iter;
143  }
144 
145  // returns the element pointed to by the iterator
146  template < typename Key >
147  INLINE const Key& SetIteratorSafe< Key >::operator*() const {
148  // note that, if the hashtable's iterator points toward nothing, it will
149  // raise an UndefinedIteratorValue exception
150  return __ht_iter.key();
151  }
152 
153  // returns aointer to the element pointed to by the iterator
154  template < typename Key >
155  INLINE const Key* SetIteratorSafe< Key >::operator->() const {
156  // note that, if the hashtable's iterator points toward nothing, it will
157  // raise an UndefinedIteratorValue exception
158  return &(__ht_iter.key());
159  }
160 
161  // @brief makes the iterator point toward nothing (in particular, it is not
162  // related anymore to its current set) */
163  template < typename Key >
164  INLINE void SetIteratorSafe< Key >::clear() noexcept {
165  __ht_iter.clear();
166  }
167 
168  // ===========================================================================
169  // === UNSAFE SET ITERATORS ===
170  // ===========================================================================
171 
172  // default constructor: the iterator points toward nothing
173  template < typename Key >
175  GUM_CONSTRUCTOR(SetIterator);
176  }
177 
178  // creates an iterator for a given set
179  template < typename Key >
180  template < typename Alloc >
182  Position pos) :
183  __ht_iter{pos == SetIterator< Key >::END ? set.__inside.cend()
184  : set.__inside.cbegin()} {
185  GUM_CONSTRUCTOR(SetIterator);
186  }
187 
188  // copy constructor
189  template < typename Key >
191  __ht_iter{iter.__ht_iter} {
192  GUM_CONS_CPY(SetIterator);
193  }
194 
195  // move constructor
196  template < typename Key >
198  __ht_iter{std::move(from.__ht_iter)} {
199  GUM_CONS_MOV(SetIterator);
200  }
201 
202  // destructor
203  template < typename Key >
205  GUM_DESTRUCTOR(SetIterator);
206  }
207 
208  // assignment operator
209  template < typename Key >
211  operator=(const SetIterator< Key >& from) noexcept {
212  __ht_iter = from.__ht_iter;
213  return *this;
214  }
215 
216  // move operator
217  template < typename Key >
219  operator=(SetIterator< Key >&& from) noexcept {
220  __ht_iter = std::move(from.__ht_iter);
221  return *this;
222  }
223 
224  // increments the iterator
225  template < typename Key >
227  // note that, if the hashtable's iterator points toward nothing, the
228  // hashtable's iterator incrementation will do nothing. In particular, it
229  // will not segfault.
230  ++__ht_iter;
231  return *this;
232  }
233 
234  // makes the iterator point to i elements further in the set
235  template < typename Key >
237  __ht_iter += nb;
238  return *this;
239  }
240 
241  // returns a new iterator
242  template < typename Key >
244  return SetIterator< Key >{*this} += nb;
245  }
246 
247  // indicates whether two iterators point to different elements or sets
248  template < typename Key >
249  INLINE bool SetIterator< Key >::operator!=(const SetIterator< Key >& from) const
250  noexcept {
251  return __ht_iter != from.__ht_iter;
252  }
253 
254  // indicates whether two iterators point toward the same element of a same
255  // set
256  template < typename Key >
257  INLINE bool SetIterator< Key >::operator==(const SetIterator< Key >& from) const
258  noexcept {
259  return __ht_iter == from.__ht_iter;
260  }
261 
262  // returns the element pointed to by the iterator
263  template < typename Key >
264  INLINE const Key& SetIterator< Key >::operator*() const {
265  // note that, if the hashtable's iterator points toward nothing, it will
266  // raise an UndefinedIteratorValue exception
267  return __ht_iter.key();
268  }
269 
270  // returns aointer to the element pointed to by the iterator
271  template < typename Key >
272  INLINE const Key* SetIterator< Key >::operator->() const {
273  // note that, if the hashtable's iterator points toward nothing, it will
274  // raise an UndefinedIteratorValue exception
275  return &(__ht_iter.key());
276  }
277 
278  // @brief makes the iterator point toward nothing (in particular, it is not
279  // related anymore to its current set) */
280  template < typename Key >
281  INLINE void SetIterator< Key >::clear() noexcept {
282  __ht_iter.clear();
283  }
284 
285  // ===========================================================================
286  // === SETS ===
287  // ===========================================================================
288 
289  // returns the end iterator for other classes' statics
290  template < typename Key, typename Alloc >
292  return *(reinterpret_cast< const SetIteratorSafe< Key >* >(
293  SetIteratorStaticEnd::endSafe4Statics()));
294  }
295 
296  // returns the end iterator for other classes' statics
297  template < typename Key, typename Alloc >
299  return *(reinterpret_cast< const SetIteratorSafe< Key >* >(
300  SetIteratorStaticEnd::constEndSafe4Statics()));
301  }
302 
303  // returns the end iterator for other classes' statics
304  template < typename Key, typename Alloc >
306  return *(reinterpret_cast< const SetIterator< Key >* >(
307  SetIteratorStaticEnd::end4Statics()));
308  }
309 
310  // returns the end iterator for other classes' statics
311  template < typename Key, typename Alloc >
313  return *(reinterpret_cast< const SetIterator< Key >* >(
314  SetIteratorStaticEnd::constEnd4Statics()));
315  }
316 
317  // default constructor
318  template < typename Key, typename Alloc >
319  INLINE Set< Key, Alloc >::Set(Size capacity, bool resize_policy) :
320  // create the hash table without key uniqueness policy (as we will
321  // check
322  // ourselves the uniqueness of Keys before inserting new elements)
323  __inside(capacity, resize_policy, false) {
324  GUM_CONSTRUCTOR(Set);
325 
326  // make sure the end() iterator is constructed properly
327  endSafe4Statics();
328  end4Statics();
329  }
330 
331  // initializer list constructor
332  template < typename Key, typename Alloc >
333  INLINE Set< Key, Alloc >::Set(std::initializer_list< Key > list) :
334  __inside(Size(list.size()) / 2, true, false) {
335  GUM_CONSTRUCTOR(Set);
336  for (const auto& elt : list) {
337  insert(elt);
338  }
339 
340  // make sure the end() iterator is constructed properly
341  endSafe4Statics();
342  end4Statics();
343  }
344 
345  // copy constructor
346  template < typename Key, typename Alloc >
348  __inside(s.__inside) {
349  GUM_CONS_CPY(Set);
350  }
351 
352  // generalized copy constructor
353  template < typename Key, typename Alloc >
354  template < typename OtherAlloc >
356  __inside(s.__inside) {
357  GUM_CONS_CPY(Set);
358  }
359 
360  // move constructor
361  template < typename Key, typename Alloc >
363  __inside(std::move(s.__inside)) {
364  GUM_CONS_MOV(Set);
365  }
366 
367  // destructor
368  template < typename Key, typename Alloc >
370  GUM_DESTRUCTOR(Set);
371  }
372 
373  // removes all the elements, if any, from the set
374  template < typename Key, typename Alloc >
375  INLINE void Set< Key, Alloc >::clear() {
376  // first we remove all the elements from the hashtable actually containing
377  // the elements of the set. Note that, doing so, all the hashtable iterators
378  // will be updated as well. In turn, this will imply that, whenever an
379  // operation will be performed on a SetIteratorSafe, this will raise an
380  // exception.
381  __inside.clear();
382 
383  // Note that actually there is no need to update the end iterator as this
384  // one
385  // is not affected by changes within hashtables (adding/deleting elements).
386  // Hence, for speedup, we do not update the end iterator
387  }
388 
389  // copy operator
390  template < typename Key, typename Alloc >
392  // avoid self assignment
393  if (&s != this) {
394  // remove the old content of the set. Actually, we remove all the elements
395  // from the underlying hashtable. Note that, doing so, all the hashtable
396  // iterators will be updated as well. In turn, this will imply that,
397  // whenever
398  // an operation will be performed on a SetIteratorSafe, this will raise an
399  // exception.
400  clear();
401 
402  // prepare the set for its new data
403  resize(s.capacity());
404  setResizePolicy(s.resizePolicy());
405 
406  // copy the set
407  __inside = s.__inside;
408 
409  // Note that actually there is no need to update the end iterator as this
410  // one
411  // is not affected by changes within hashtables (adding/deleting
412  // elements).
413  // Hence, for speedup, we do not update the end iterator
414  }
415 
416  return *this;
417  }
418 
419  // generalized copy operator
420  template < typename Key, typename Alloc >
421  template < typename OtherAlloc >
424  // avoid self assignment
425  if (this != reinterpret_cast< const Set< Key, Alloc >* >(&s)) {
426  // remove the old content of the set. Actually, we remove all the elements
427  // from the underlying hashtable. Note that, doing so, all the hashtable
428  // iterators will be updated as well. In turn, this will imply that,
429  // whenever
430  // an operation will be performed on a SetIteratorSafe, this will raise an
431  // exception.
432  clear();
433 
434  // prepare the set for its new data
435  resize(s.capacity());
436  setResizePolicy(s.resizePolicy());
437 
438  // copy the set
439  __inside = s.__inside;
440 
441  // Note that actually there is no need to update the end iterator as this
442  // one
443  // is not affected by changes within hashtables (adding/deleting
444  // elements).
445  // Hence, for speedup, we do not update the end iterator
446  }
447 
448  return *this;
449  }
450 
451  // move operator
452  template < typename Key, typename Alloc >
454  __inside = std::move(from.__inside);
455  return *this;
456  }
457 
458  // mathematical equality between two sets
459  template < typename Key, typename Alloc >
460  template < typename OtherAlloc >
463 
464  // check whether both sets have the same number of elements
465  if (size() != h2.size()) return false;
466 
467  // check the content of the sets
468  for (HashTableConstIterator< Key, bool > iter = __inside.cbegin();
469  iter != __inside.cend();
470  ++iter) {
471  if (!h2.exists(iter.key())) return false;
472  }
473 
474  return true;
475  }
476 
477  // mathematical inequality between two sets
478  template < typename Key, typename Alloc >
479  template < typename OtherAlloc >
480  INLINE bool Set< Key, Alloc >::
482  return !(operator==(s2));
483  }
484 
485  // the usual begin iterator to parse the set
486  template < typename Key, typename Alloc >
487  INLINE typename Set< Key, Alloc >::iterator_safe
489  return SetIteratorSafe< Key >{*this};
490  }
491 
492  // the usual begin iterator to parse the set
493  template < typename Key, typename Alloc >
496  return SetIteratorSafe< Key >{*this};
497  }
498 
499  // the usual end iterator to parse the set
500  template < typename Key, typename Alloc >
501  INLINE const typename Set< Key, Alloc >::iterator_safe&
502  Set< Key, Alloc >::endSafe() const noexcept {
503  return *(reinterpret_cast< const SetIteratorSafe< Key >* >(
504  SetIteratorStaticEnd::__SetIterEndSafe));
505  }
506 
507  // the usual end iterator to parse the set
508  template < typename Key, typename Alloc >
509  INLINE const typename Set< Key, Alloc >::const_iterator_safe&
510  Set< Key, Alloc >::cendSafe() const noexcept {
511  return *(reinterpret_cast< const SetIteratorSafe< Key >* >(
512  SetIteratorStaticEnd::__SetIterEndSafe));
513  }
514 
515  // the usual begin iterator to parse the set
516  template < typename Key, typename Alloc >
518  return SetIterator< Key >{*this};
519  }
520 
521  // the usual begin iterator to parse the set
522  template < typename Key, typename Alloc >
523  INLINE typename Set< Key, Alloc >::const_iterator
525  return SetIterator< Key >{*this};
526  }
527 
528  // the usual end iterator to parse the set
529  template < typename Key, typename Alloc >
531  noexcept {
532  return *(reinterpret_cast< const SetIterator< Key >* >(
533  SetIteratorStaticEnd::__SetIterEnd));
534  }
535 
536  // the usual end iterator to parse the set
537  template < typename Key, typename Alloc >
538  INLINE const typename Set< Key, Alloc >::const_iterator&
539  Set< Key, Alloc >::cend() const noexcept {
540  return *(reinterpret_cast< const SetIterator< Key >* >(
541  SetIteratorStaticEnd::__SetIterEnd));
542  }
543 
544  // returns the size of the underlying hashtable containing the set
545  template < typename Key, typename Alloc >
547  return __inside.capacity();
548  }
549 
550  // changes the size of the underlying hashtable
551  template < typename Key, typename Alloc >
552  INLINE void Set< Key, Alloc >::resize(Size new_size) {
553  __inside.resize(new_size);
554 
555  // Note that actually there is no need to update the end iterator as this
556  // one
557  // is not affected by changes within hashtables (adding/deleting elements).
558  // Hence, for speedup, we do not update the end iterator
559  }
560 
561  // enables the user to change dynamically the resizing policy of the
562  // underlying hashtable
563  template < typename Key, typename Alloc >
564  INLINE void Set< Key, Alloc >::setResizePolicy(const bool new_policy) {
565  __inside.setResizePolicy(new_policy);
566 
567  // Note that actually there is no need to update the end iterator as this
568  // one
569  // is not affected by changes within hashtables (adding/deleting elements).
570  // Hence, for speedup, we do not update the end iterator
571  }
572 
573  // returns the current resizing policy of the underlying hashtable
574  template < typename Key, typename Alloc >
575  INLINE bool Set< Key, Alloc >::resizePolicy() const {
576  return __inside.resizePolicy();
577  }
578 
579  // indicates whether a given elements belong to the set
580  template < typename Key, typename Alloc >
581  INLINE bool Set< Key, Alloc >::contains(const Key& k) const {
582  return __inside.exists(k);
583  }
584 
585 
586  template < typename Key, typename Alloc >
587  template < typename OtherAlloc >
588  INLINE bool
590  if (this->size() >= s.size()) { return false; }
591 
592  for (const auto& elt : *this) {
593  if (!s.contains(elt)) { return false; }
594  }
595  return true;
596  }
597 
598  template < typename Key, typename Alloc >
599  template < typename OtherAlloc >
600  INLINE bool
602  return s.isSubsetOf(*this);
603  }
604 
605  // indicates whether a given elements belong to the set
606  template < typename Key, typename Alloc >
607  INLINE bool Set< Key, Alloc >::exists(const Key& k) const {
608  return __inside.exists(k);
609  }
610 
611  // inserts a new element in the set
612  template < typename Key, typename Alloc >
613  INLINE void Set< Key, Alloc >::insert(const Key& k) {
614  // WARNING: we shall always test whether k already belongs to the set before
615  // trying to insert it because we set __inside's key uniqueness policy to
616  // false
617  if (!contains(k)) {
618  // insert the element
619  __inside.insert(k, true);
620 
621  // Note that actually there is no need to update the end iterator as this
622  // one
623  // is not affected by changes within hashtables (adding/deleting
624  // elements).
625  // Hence, for speedup, we do not update the end iterator
626  }
627  }
628 
629  // inserts a new element in the set
630  template < typename Key, typename Alloc >
631  INLINE void Set< Key, Alloc >::insert(Key&& k) {
632  // WARNING: we shall always test whether k already belongs to the set before
633  // trying to insert it because we set __inside's key uniqueness policy to
634  // false
635  if (!contains(k)) {
636  // insert the element
637  __inside.insert(std::move(k), true);
638 
639  // Note that actually there is no need to update the end iterator as this
640  // one
641  // is not affected by changes within hashtables (adding/deleting
642  // elements).
643  // Hence, for speedup, we do not update the end iterator
644  }
645  }
646 
647  // emplace a new element in the set
648  template < typename Key, typename Alloc >
649  template < typename... Args >
650  INLINE void Set< Key, Alloc >::emplace(Args&&... args) {
651  insert(std::move(Key(std::forward< Args >(args)...)));
652  }
653 
654  // erases an element from the set
655  template < typename Key, typename Alloc >
656  INLINE void Set< Key, Alloc >::erase(const Key& k) {
657  // erase the element (if it exists)
658  __inside.erase(k);
659 
660  // Note that actually there is no need to update the end iterator as this
661  // one
662  // is not affected by changes within hashtables (adding/deleting elements).
663  // Hence, for speedup, we do not update the end iterator
664  }
665 
666  // erases an element from the set
667  template < typename Key, typename Alloc >
669  // erase the element
670  __inside.erase(iter.__ht_iter);
671 
672  // Note that actually there is no need to update the end iterator as this
673  // one
674  // is not affected by changes within hashtables (adding/deleting elements).
675  // Hence, for speedup, we do not update the end iterator
676  }
677 
678  // adds a new element to the set
679  template < typename Key, typename Alloc >
681  insert(k);
682  return *this;
683  }
684 
685  // adds a new element to the set
686  template < typename Key, typename Alloc >
688  insert(std::move(k));
689  return *this;
690  }
691 
692  // removes an element from the set
693  template < typename Key, typename Alloc >
695  erase(k);
696  return *this;
697  }
698 
699  // returns the number of elements in the set
700  template < typename Key, typename Alloc >
701  INLINE Size Set< Key, Alloc >::size() const noexcept {
702  return __inside.size();
703  }
704 
705  // indicates whether the set is the empty set
706  template < typename Key, typename Alloc >
707  INLINE bool Set< Key, Alloc >::empty() const noexcept {
708  return __inside.empty();
709  }
710 
711  // Intersection operator
712  template < typename Key, typename Alloc >
713  template < typename OtherAlloc >
716  Set< Key, Alloc > res;
719 
720  if (size() < h2.size()) {
721  for (HashTableConstIterator< Key, bool > iter = __inside.cbegin();
722  iter != __inside.cend();
723  ++iter) {
724  if (h2.exists(iter.key())) h_r.insert(iter.key(), true);
725  }
726  } else {
728  iter != h2.cend();
729  ++iter) {
730  if (__inside.exists(iter.key())) h_r.insert(iter.key(), true);
731  }
732  }
733 
734  return res;
735  }
736 
737 
738  // Intersection update operator
739  template < typename Key, typename Alloc >
740  template < typename OtherAlloc >
743  if (&s2 != this) {
745  for (auto iter = __inside.beginSafe(); iter != __inside.endSafe(); ++iter) {
746  if (!h2.exists(iter.key())) __inside.erase(iter);
747  }
748  }
749 
750  return *this;
751  }
752 
753 
754  // Union update operator
755  template < typename Key, typename Alloc >
756  template < typename OtherAlloc >
759  if (&s2 != this) {
760  for (auto pair : s2.__inside) {
761  if (!__inside.exists(pair.first)) __inside.insert(pair.first, true);
762  }
763  }
764 
765  return *this;
766  }
767 
768 
769  // Union operator
770  template < typename Key, typename Alloc >
771  template < typename OtherAlloc >
774  Set< Key, Alloc > res = *this;
777 
778  for (HashTableConstIterator< Key, bool > iter = h2.cbegin(); iter != h2.cend();
779  ++iter) {
780  if (!h_r.exists(iter.key())) h_r.insert(iter.key(), true);
781  }
782 
783  return res;
784  }
785 
786 
787  // Disjunction operator
788  template < typename Key, typename Alloc >
789  template < typename OtherAlloc >
792  Set< Key, Alloc > res;
795 
796  for (HashTableConstIterator< Key, bool > iter = __inside.cbegin();
797  iter != __inside.cend();
798  ++iter)
799  if (!h2.exists(iter.key())) h_r.insert(iter.key(), true);
800 
801  return res;
802  }
803 
804  // to display the content of the set
805  template < typename Key, typename Alloc >
806  INLINE std::string Set< Key, Alloc >::toString() const {
807  std::stringstream out;
808  bool first = true;
809  out << "{";
810 
811  for (iterator iter = begin(); iter != end(); ++iter) {
812  if (first) {
813  out << *iter;
814  first = false;
815  } else {
816  out << "," << *iter;
817  }
818  }
819 
820  out << "}";
821 
822  std::string res;
823  out >> res;
824  return res;
825  }
826 
827  // to friendly display the content of the set
828  template < typename Key, typename Alloc >
829  std::ostream& operator<<(std::ostream& stream, const Set< Key, Alloc >& set) {
830  stream << set.toString();
831  return stream;
832  }
833 
834  // creates a hashtable of NewKey from the set
835  template < typename Key, typename Alloc >
836  template < typename NewKey, typename NewAlloc >
838  Set< Key, Alloc >::hashMap(NewKey (*f)(const Key&), Size size) const {
839  // determine the proper size of the hashtable
840  // by default, the size of the table is set so that the table does not take
841  // too much space while allowing to add a few elements without resizing
842  if (size == 0) size = std::max(Size(2), __inside.size() / 2);
843 
844  // create a new table
846 
847  // fill the new hash table
848  for (HashTableConstIterator< Key, bool > iter = __inside.cbegin();
849  iter != __inside.cend();
850  ++iter) {
851  table.insert(iter.key(), f(iter.key()));
852  }
853 
854  return table;
855  }
856 
857  // creates a hashtable of NewKey from the set
858  template < typename Key, typename Alloc >
859  template < typename NewKey, typename NewAlloc >
861  Size size) const {
862  // determine the proper size of the hashtable
863  // by default, the size of the table is set so that the table does not take
864  // too much space while allowing to add a few elements without resizing
865  if (size == 0) size = std::max(Size(2), __inside.size() / 2);
866 
867  // create a new table
869 
870  // fill the new hash table
871  for (HashTableConstIterator< Key, bool > iter = __inside.cbegin();
872  iter != __inside.cend();
873  ++iter) {
874  table.insert(iter.key(), val);
875  }
876 
877  return table;
878  }
879 
880  // a method to create a list of NewKey from the set
881  template < typename Key, typename Alloc >
882  template < typename NewKey, typename NewAlloc >
884  Set< Key, Alloc >::listMap(NewKey (*f)(const Key&)) const {
885  // create a new list
887 
888  // fill the new list
889  for (HashTableConstIterator< Key, bool > iter = __inside.cbegin();
890  iter != __inside.cend();
891  ++iter) {
892  list.pushBack(f(iter.key()));
893  }
894 
895  return list;
896  }
897 
898 
899  // Returns the value of a key as a Size
900  template < typename T, typename Alloc >
901  INLINE Size HashFunc< Set< T, Alloc > >::castToSize(const Set< T, Alloc >& key) {
902  Size h = Size(0);
903  Size i = Size(0);
904  for (const auto& k : key) {
905  h += ++i * HashFunc< T >::castToSize(k);
906  }
907 
908  return h;
909  }
910 
911 
912  // Returns the hashed value of a key.
913  template < typename T, typename Alloc >
915  operator()(const Set< T, Alloc >& key) const {
916  return (castToSize(key) * HashFuncConst::gold) & this->_hash_mask;
917  }
918 
919 } /* namespace gum */
bool contains(const Key &k) const
Indicates whether a given elements belong to the set.
Definition: set_tpl.h:581
const key_type & key() const
Returns the key corresponding to the element pointed to by the iterator.
bool empty() const noexcept
Indicates whether the set is the empty set.
Definition: set_tpl.h:707
SetIterator< Key > operator+(Size i) const noexcept
Returns a new iterator.
Definition: set_tpl.h:243
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
static const const_iterator_safe & constEndSafe4Statics()
Returns the end iterator for other classes&#39; statics (read the detailed description of this method)...
Definition: set_tpl.h:298
bool operator!=(const SetIterator< Key > &from) const noexcept
Indicates whether two iterators point to different elements or sets.
Definition: set_tpl.h:249
Safe iterators for the Set classDevelopers may consider using Set<x>::iterator_safe instead of SetIte...
Definition: set.h:811
Size capacity() const
Returns the capacity of the underlying hash table containing the set.
Definition: set_tpl.h:546
Size size() const noexcept
Returns the number of elements stored into the hashtable.
bool isSubsetOf(const Set< Key, OtherAlloc > &s) const
STL namespace.
bool exists(const Key &key) const
Checks whether there exists an element with a given key in the hashtable.
Class template representing hashing function of LpCol.
Definition: hashFunc.h:471
void erase(const Key &k)
Erases an element from the set.
Definition: set_tpl.h:656
void clear() noexcept
Makes the iterator point toward nothing (in particular, it is not related anymore to its current hash...
Generic doubly linked lists.
Definition: list.h:372
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
Definition: agrum.h:25
bool operator==(const SetIterator< Key > &from) const noexcept
Indicates whether two iterators point toward the same element of a same set.
Definition: set_tpl.h:257
The class for generic Hash Tables.
Definition: hashTable.h:679
SetIterator() noexcept
Default constructor: the iterator points toward nothing.
Definition: set_tpl.h:174
std::istream & operator>>(std::istream &in, TiXmlNode &base)
Definition: tinyxml.cpp:1505
Representation of a setA Set is a structure that contains arbitrary elements.
Definition: set.h:165
static const iterator & end4Statics()
Returns the end iterator for other classes&#39; statics (read the detailed description of this method)...
Definition: set_tpl.h:305
HashTableConstIteratorSafe< Key, bool > __ht_iter
The underlying iterator for the set&#39;s hash table containing the data.
Definition: set.h:981
bool exists(const Key &k) const
Indicates whether a given elements belong to the set.
Definition: set_tpl.h:607
Position
An enumeration to position the iterator at the beginning or the end of the set.
Definition: set.h:1042
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:586
void resize(Size new_capacity)
Changes the size of the underlying hash table containing the set.
Definition: set_tpl.h:552
HashTableConstIterator< Key, bool > __ht_iter
The underlying iterator for the set&#39;s hash table containing the data.
Definition: set.h:1183
bool resizePolicy() const
Returns the current resizing policy of the underlying hash table.
Definition: set_tpl.h:575
Position
An enumeration to position the iterator at the beginning or the end of the set.
Definition: set.h:828
const const_iterator & cend() const noexcept
Returns the unsafe const_iterator pointing to the end of the hashtable.
LpExpr operator+(LpExpr &&lhs, const T2 &rhs)
Overload of operator + between anything ( a scalar, a variable or an expression ) and anything except...
Val & pushBack(const Val &val)
Inserts a new element (a copy) at the end of the chained list.
Definition: list_tpl.h:1592
bool operator==(const TiXmlString &a, const TiXmlString &b)
Definition: tinystr.h:243
void setResizePolicy(const bool new_policy)
Enables the user to change dynamically the resizing policy of the underlying hash table...
Definition: set_tpl.h:564
static const iterator_safe & endSafe4Statics()
Returns the end iterator for other classes&#39; statics (read the detailed description of this method)...
Definition: set_tpl.h:291
SetIterator< Key > & operator+=(Size i) noexcept
Makes the iterator point to i elements further in the set.
Definition: set_tpl.h:236
void clear() noexcept
makes the iterator point toward nothing (in particular, it is not related anymore to its current set)...
Definition: set_tpl.h:164
friend class Set
Friends to speed up access.
Definition: set.h:763
const_iterator cbegin() const
Returns an unsafe const_iterator pointing to the beginning of the hashtable.
const Key * operator->() const
Returns a pointer to the element pointed to by the iterator.
Definition: set_tpl.h:272
Unsafe iterators for the Set class.
Definition: set.h:1025
LpExpr operator*(const SCALAR &lhs, const LpCol &rhs)
Overload of operator * between a scalar and a variable.
SetIterator< Key > & operator++() noexcept
Increments the iterator.
Definition: set_tpl.h:226
bool operator!=(const TiXmlString &a, const TiXmlString &b)
Definition: tinystr.h:251
void clear() noexcept
makes the iterator point toward nothing (in particular, it is not related anymore to its current set)...
Definition: set_tpl.h:281
HashTable< Key, bool, Alloc > __inside
A set of X&#39;s is actually a hash table whose keys are the X&#39;s.
Definition: set.h:767
~SetIterator() noexcept
Class destructor.
Definition: set_tpl.h:204
void clear()
Removes all the elements, if any, from the set.
Definition: set_tpl.h:375
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
LpExpr operator-(LpExpr &&lhs, const T2 &rhs)
Overload of operator - between anything ( a scalar, a variable or an expression ) and anything except...
Size size() const noexcept
Returns the number of elements in the set.
Definition: set_tpl.h:701
value_type & insert(const Key &key, const Val &val)
Adds a new element (actually a copy of this element) into the hash table.
SetIteratorSafe()
Default constructor: the iterator points toward nothing.
Definition: set_tpl.h:40
static const const_iterator & constEnd4Statics()
Returns the end iterator for other classes&#39; statics (read the detailed description of this method)...
Definition: set_tpl.h:312
void insert(const Key &k)
Inserts a new element into the set.
Definition: set_tpl.h:613
const Key & operator*() const
Returns the element pointed to by the iterator.
Definition: set_tpl.h:264
SetIterator< Key > & operator=(const SetIterator< Key > &from) noexcept
Assignment operator.
Definition: set_tpl.h:211