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