aGrUM  0.16.0
set.h
Go to the documentation of this file.
1 
29 #ifndef GUM_SET_H
30 #define GUM_SET_H
31 
32 #include <initializer_list>
33 #include <iostream>
34 #include <sstream>
35 #include <string>
36 
37 #include <agrum/core/debug.h>
38 #include <agrum/core/hashTable.h>
39 #include <agrum/core/list.h>
40 
41 namespace gum {
42 
43 #ifndef DOXYGEN_SHOULD_SKIP_THIS
44 
45  template < typename Key >
46  class SetIteratorSafe;
47  template < typename Key >
48  class SetIterator;
49  template < typename Key, typename Alloc >
50  class Set;
51 
52  template < typename Key >
53  using SetConstIterator = SetIterator< Key >;
54  template < typename Key >
55  using SetConstIteratorSafe = SetIteratorSafe< Key >;
56 
57 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
58 
69  class SetIteratorStaticEnd {
70  private:
75  static const SetIteratorSafe< int >* __SetIterEndSafe;
76 
81  static const SetIterator< int >* __SetIterEnd;
82 
87  static const SetIteratorSafe< int >* endSafe4Statics();
88 
93  static const SetIteratorSafe< int >* constEndSafe4Statics();
94 
99  static const SetIterator< int >* end4Statics();
100 
105  static const SetIterator< int >* constEnd4Statics();
106 
108  template < typename Key, typename Alloc >
109  friend class Set;
110  };
111 
112 
113  // ===========================================================================
114  // === GUM_SET ===
115  // ===========================================================================
116 
164  template < typename Key, typename Alloc = std::allocator< Key > >
165  class Set {
166  public:
169  using value_type = Key;
170  using reference = Key&;
171  using const_reference = const Key&;
172  using pointer = Key*;
173  using const_pointer = const Key*;
174  using size_type = std::size_t;
175  using difference_type = std::ptrdiff_t;
176  using allocator_type = Alloc;
177  using iterator = SetIterator< Key >;
178  using const_iterator = SetIterator< Key >;
179  using iterator_safe = SetIteratorSafe< Key >;
180  using const_iterator_safe = SetIteratorSafe< Key >;
182 
183  // ============================================================================
185  // ============================================================================
187 
200  explicit Set(Size capacity = HashTableConst::default_size,
201  bool resize_policy = true);
202 
207  Set(std::initializer_list< Key > list);
208 
213  Set(const Set< Key, Alloc >& aHT);
214 
220  template < typename OtherAlloc >
221  Set(const Set< Key, OtherAlloc >& aHT);
222 
227  Set(Set< Key, Alloc >&& aHT);
228 
232  ~Set();
233 
235  // ============================================================================
237  // ============================================================================
239 
245  Set< Key, Alloc >& operator=(const Set< Key, Alloc >& from);
246 
253  template < typename OtherAlloc >
254  Set< Key, Alloc >& operator=(const Set< Key, OtherAlloc >& from);
255 
261  Set< Key, Alloc >& operator=(Set< Key, Alloc >&& from);
262 
269  template < typename OtherAlloc >
270  bool operator==(const Set< Key, OtherAlloc >& s2) const;
271 
278  template < typename OtherAlloc >
279  bool operator!=(const Set< Key, OtherAlloc >& s2) const;
280 
288  template < typename OtherAlloc >
289  const Set< Key, Alloc >& operator*=(const Set< Key, OtherAlloc >& s2);
290 
298  template < typename OtherAlloc >
299  Set< Key, Alloc > operator*(const Set< Key, OtherAlloc >& s2) const;
300 
308  template < typename OtherAlloc >
309  const Set< Key, Alloc >& operator+=(const Set< Key, OtherAlloc >& s2);
310 
318  template < typename OtherAlloc >
319  Set< Key, Alloc > operator+(const Set< Key, OtherAlloc >& s2) const;
320 
321 
329  template < typename OtherAlloc >
330  Set< Key, Alloc > operator-(const Set< Key, OtherAlloc >& s2) const;
331 
337  Set< Key, Alloc >& operator<<(const Key& k);
338 
344  Set< Key, Alloc >& operator<<(Key&& k);
345 
351  Set< Key, Alloc >& operator>>(const Key& k);
352 
354  // ============================================================================
356  // ============================================================================
358 
365  void insert(const Key& k);
366 
373  void insert(Key&& k);
374 
385  template < typename... Args >
386  void emplace(Args&&... args);
387 
395  void erase(const Key& k);
396 
403  void erase(const iterator_safe& k);
404 
408  void clear();
409 
414  Size size() const noexcept;
415 
420  bool contains(const Key& k) const;
421 
425  template < typename OtherAlloc >
426  bool isSubsetOf(const Set< Key, OtherAlloc >& s) const;
427 
431  template < typename OtherAlloc >
432  bool isSupersetOf(const Set< Key, OtherAlloc >& s) const;
433 
438  bool exists(const Key& k) const;
439 
444  bool empty() const noexcept;
445 
450  std::string toString() const;
451 
453  // ============================================================================
455  // ============================================================================
457 
462  iterator_safe beginSafe() const;
463 
468  const_iterator_safe cbeginSafe() const;
469 
474  const iterator_safe& endSafe() const noexcept;
475 
480  const const_iterator_safe& cendSafe() const noexcept;
481 
486  iterator begin() const;
487 
492  const_iterator cbegin() const;
493 
498  const iterator& end() const noexcept;
499 
504  const const_iterator& cend() const noexcept;
505 
541  static const iterator& end4Statics();
542 
578  static const const_iterator& constEnd4Statics();
579 
615  static const iterator_safe& endSafe4Statics();
616 
652  static const const_iterator_safe& constEndSafe4Statics();
653 
655  // ============================================================================
657  // ============================================================================
659 
669  Size capacity() const;
670 
678  void resize(Size new_capacity);
679 
690  void setResizePolicy(const bool new_policy);
691 
697  bool resizePolicy() const;
698 
700  // ============================================================================
702  // ============================================================================
704 
717  template <
718  typename NewKey,
719  typename NewAlloc = typename Alloc::template rebind< NewKey >::other >
720  HashTable< Key, NewKey, NewAlloc > hashMap(NewKey (*f)(const Key&),
721  Size capacity = 0) const;
722 
736  template <
737  typename NewKey,
738  typename NewAlloc = typename Alloc::template rebind< NewKey >::other >
739  HashTable< Key, NewKey, NewAlloc > hashMap(const NewKey& val,
740  Size size = 0) const;
741 
750  template <
751  typename NewKey,
752  typename NewAlloc = typename Alloc::template rebind< NewKey >::other >
753  List< NewKey, NewAlloc > listMap(NewKey (*f)(const Key&)) const;
754 
756 
757  private:
760  friend class SetIterator< Key >;
761  friend class SetIteratorSafe< Key >;
762  template < typename K, typename A >
763  friend class Set;
765 
767  HashTable< Key, bool, Alloc > __inside;
768 
770  Set(const HashTable< Key, bool, Alloc >& h);
771  };
772 
773 
774  // ===========================================================================
775  // === SAFE SET ITERATORS ===
776  // ===========================================================================
777 
810  template < typename Key >
811  class SetIteratorSafe {
812  public:
815  using iterator_category = std::forward_iterator_tag;
816  using value_type = Key;
817  using reference = value_type&;
818  using const_reference = const value_type&;
819  using pointer = value_type*;
820  using const_pointer = const value_type*;
821  using difference_type = std::ptrdiff_t;
823 
828  enum Position { BEGIN, END };
829 
830  // ============================================================================
832  // ============================================================================
834 
838  SetIteratorSafe();
839 
850  template < typename Alloc >
851  SetIteratorSafe(const Set< Key, Alloc >& from, Position pos = BEGIN);
852 
857  SetIteratorSafe(const SetIteratorSafe< Key >& from);
858 
863  explicit SetIteratorSafe(const SetIterator< Key >& from);
864 
869  SetIteratorSafe(SetIteratorSafe< Key >&& from);
870 
874  ~SetIteratorSafe() noexcept;
875 
877  // ============================================================================
879  // ============================================================================
881 
887  SetIteratorSafe< Key >& operator=(const SetIteratorSafe< Key >& from);
888 
894  SetIteratorSafe< Key >& operator=(const SetIterator< Key >& from);
895 
901  SetIteratorSafe< Key >& operator=(SetIteratorSafe< Key >&& from) noexcept;
902 
907  SetIteratorSafe< Key >& operator++() noexcept;
908 
914  SetIteratorSafe< Key >& operator+=(Size i) noexcept;
915 
921  SetIteratorSafe< Key > operator+(Size i) const;
922 
929  bool operator!=(const SetIteratorSafe< Key >& from) const noexcept;
930 
937  bool operator==(const SetIteratorSafe< Key >& from) const noexcept;
938 
948  const Key& operator*() const;
949 
959  const Key* operator->() const;
960 
962  // ============================================================================
964  // ============================================================================
966 
971  void clear() noexcept;
972 
974 
975  private:
977  template < typename K, typename A >
978  friend class Set;
979 
981  HashTableConstIteratorSafe< Key, bool > __ht_iter;
982  };
983 
984  // ===========================================================================
985  // === UNSAFE SET ITERATORS ===
986  // ===========================================================================
987 
1024  template < typename Key >
1025  class SetIterator {
1026  public:
1029  using iterator_category = std::forward_iterator_tag;
1030  using value_type = Key;
1031  using reference = value_type&;
1032  using const_reference = const value_type&;
1033  using pointer = value_type*;
1034  using const_pointer = const value_type*;
1035  using difference_type = std::ptrdiff_t;
1037 
1042  enum Position { BEGIN, END };
1043 
1044  // ============================================================================
1046  // ============================================================================
1048 
1052  SetIterator() noexcept;
1053 
1064  template < typename Alloc >
1065  SetIterator(const Set< Key, Alloc >& from, Position pos = BEGIN);
1066 
1071  SetIterator(const SetIterator< Key >& from) noexcept;
1072 
1077  SetIterator(SetIterator< Key >&& from) noexcept;
1078 
1082  ~SetIterator() noexcept;
1083 
1085  // ============================================================================
1087  // ============================================================================
1089 
1095  SetIterator< Key >& operator=(const SetIterator< Key >& from) noexcept;
1096 
1102  SetIterator< Key >& operator=(SetIterator< Key >&& from) noexcept;
1103 
1108  SetIterator< Key >& operator++() noexcept;
1109 
1115  SetIterator< Key >& operator+=(Size i) noexcept;
1116 
1122  SetIterator< Key > operator+(Size i) const noexcept;
1123 
1130  bool operator!=(const SetIterator< Key >& from) const noexcept;
1131 
1138  bool operator==(const SetIterator< Key >& from) const noexcept;
1139 
1149  const Key& operator*() const;
1150 
1160  const Key* operator->() const;
1161 
1163  // ============================================================================
1165  // ============================================================================
1167 
1172  void clear() noexcept;
1173 
1175 
1176  private:
1178  template < typename K, typename A >
1179  friend class Set;
1180  friend class SetIteratorSafe< Key >;
1181 
1183  HashTableConstIterator< Key, bool > __ht_iter;
1184  };
1185 
1186 
1188  template < typename Key, typename Alloc >
1189  std::ostream& operator<<(std::ostream&, const Set< Key, Alloc >&);
1190 
1191 
1193  template < typename T, typename Alloc >
1194  class HashFunc< Set< T, Alloc > > : public HashFuncBase< Set< T, Alloc > > {
1195  public:
1201  static Size castToSize(const Set< T, Alloc >& key);
1202 
1204  virtual Size operator()(const Set< T, Alloc >& key) const override final;
1205  };
1206 
1207 } /* namespace gum */
1208 
1209 
1210 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1211 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1212 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1213 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1214 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1215 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1216 extern template class gum::Set< int >;
1217 # endif
1218 # endif
1219 # endif
1220 # endif
1221 # endif
1222 #endif
1223 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1224 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1225 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1226 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1227 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1228 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1229 extern template class gum::Set< long >;
1230 # endif
1231 # endif
1232 # endif
1233 # endif
1234 # endif
1235 #endif
1236 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1237 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1238 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1239 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1240 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1241 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1242 extern template class gum::Set< unsigned int >;
1243 # endif
1244 # endif
1245 # endif
1246 # endif
1247 # endif
1248 #endif
1249 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1250 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1251 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1252 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1253 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1254 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1255 extern template class gum::Set< unsigned long >;
1256 # endif
1257 # endif
1258 # endif
1259 # endif
1260 # endif
1261 #endif
1262 
1263 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1264 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1265 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1266 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1267 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1268 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1269 extern template class gum::Set< double >;
1270 # endif
1271 # endif
1272 # endif
1273 # endif
1274 # endif
1275 #endif
1276 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1277 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1278 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1279 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1280 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1281 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1282 extern template class gum::Set< std::string >;
1283 # endif
1284 # endif
1285 # endif
1286 # endif
1287 # endif
1288 #endif
1289 
1290 
1291 // always include the implementation of the templates
1292 #include <agrum/core/set_tpl.h>
1293 
1294 #endif // GUM_SET_H
gum::Potential
aGrUM&#39;s Potential is a multi-dimensional array with tensor operators.
Definition: potential.h:60
gum::SetIterator::pointer
value_type * pointer
Types for STL compliance.
Definition: set.h:1033
set_tpl.h
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
gum::operator+
Formula operator+(const Formula &a, const Formula &b)
Definition: formula_inl.h:479
gum::SetIteratorSafe
Safe iterators for the Set classDevelopers may consider using Set<x>::iterator_safe instead of SetIte...
Definition: set.h:811
gum::SetIterator::value_type
Key value_type
Types for STL compliance.
Definition: set.h:1030
std
STL namespace.
gum::SetIterator::iterator_category
std::forward_iterator_tag iterator_category
Types for STL compliance.
Definition: set.h:1029
gum::HashTableConst::default_size
static constexpr Size default_size
The default number of slots in hashtables.
Definition: hashTable.h:80
gum::HashFunc
Class template representing hashing function of LpCol.
Definition: hashFunc.h:471
gum::DiscreteVariable
Base class for discrete random variable.
Definition: discreteVariable.h:60
gum::List
Generic doubly linked lists.
Definition: list.h:372
gum
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
Definition: agrum.h:25
gum::HashTable
The class for generic Hash Tables.
Definition: hashTable.h:679
gum::Set
Representation of a setA Set is a structure that contains arbitrary elements.
Definition: set.h:165
gum::SetIterator::reference
value_type & reference
Types for STL compliance.
Definition: set.h:1031
gum::SetIteratorSafe::__ht_iter
HashTableConstIteratorSafe< Key, bool > __ht_iter
The underlying iterator for the set&#39;s hash table containing the data.
Definition: set.h:981
gum::SetIterator::Position
Position
An enumeration to position the iterator at the beginning or the end of the set.
Definition: set.h:1042
gum::operator<<
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:605
list.h
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
gum::SetIterator::__ht_iter
HashTableConstIterator< Key, bool > __ht_iter
The underlying iterator for the set&#39;s hash table containing the data.
Definition: set.h:1183
gum::SetIteratorSafe< const gum::DiscreteVariable * >::Position
Position
An enumeration to position the iterator at the beginning or the end of the set.
Definition: set.h:828
gum::SetIterator::const_reference
const value_type & const_reference
Types for STL compliance.
Definition: set.h:1032
gum::operator*
Formula operator*(const Formula &a, const Formula &b)
Definition: formula_inl.h:489
gum::SetIteratorSafe< const gum::DiscreteVariable * >::iterator_category
std::forward_iterator_tag iterator_category
Types for STL compliance.
Definition: set.h:815
operator==
bool operator==(const TiXmlString &a, const TiXmlString &b)
Definition: tinystr.h:243
gum::operator-
ListConstIterator< Val >::difference_type operator-(const ListConstIterator< Val > &iter1, const ListConstIterator< Val > &iter2)
For STL compliance, a distance operator.
Definition: list_tpl.h:349
gum::SetIterator
Unsafe iterators for the Set class.
Definition: set.h:1025
gum::SetIterator::difference_type
std::ptrdiff_t difference_type
Types for STL compliance.
Definition: set.h:1035
gum::Set< gum::Potential< GUM_SCALAR > * >::allocator_type
std::allocator< gum::Potential< GUM_SCALAR > * > allocator_type
Definition: set.h:176
operator!=
bool operator!=(const TiXmlString &a, const TiXmlString &b)
Definition: tinystr.h:251
gum::HashFuncBase
All hash functions should inherit from this class.
Definition: hashFunc.h:149
gum::SetIterator::const_pointer
const value_type * const_pointer
Types for STL compliance.
Definition: set.h:1034
gum::Size
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:48
gum::operator>>
MultiDimInterface & operator>>(MultiDimInterface &c, const DiscreteVariable &v)
Removes a var from the variables of the MutliDimAdressing.
Definition: multiDimInterface.cpp:42
hashTable.h
Copyright 2005-2019 Pierre-Henri WUILLEMIN et Christophe GONZALES (LIP6) {prenom.nom}_at_lip6.fr.
aGrUM 0.16.0
Tue Aug 27 2019 12:07:01
© CG&PHW&others - LIP6 2005-2007-2012
DoXyGeN 1.8.13