aGrUM  0.14.2
set.h
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005 by Pierre-Henri WUILLEMIN et Christophe GONZALES *
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  ***************************************************************************/
26 #ifndef GUM_SET_H
27 #define GUM_SET_H
28 
29 #include <initializer_list>
30 #include <iostream>
31 #include <sstream>
32 #include <string>
33 
34 #include <agrum/core/debug.h>
35 #include <agrum/core/hashTable.h>
36 #include <agrum/core/list.h>
37 
38 namespace gum {
39 
40 #ifndef DOXYGEN_SHOULD_SKIP_THIS
41 
42  template < typename Key >
43  class SetIteratorSafe;
44  template < typename Key >
45  class SetIterator;
46  template < typename Key, typename Alloc >
47  class Set;
48 
49  template < typename Key >
50  using SetConstIterator = SetIterator< Key >;
51  template < typename Key >
52  using SetConstIteratorSafe = SetIteratorSafe< Key >;
53 
54 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
55 
66  class SetIteratorStaticEnd {
67  private:
72  static const SetIteratorSafe< int >* __SetIterEndSafe;
73 
78  static const SetIterator< int >* __SetIterEnd;
79 
84  static const SetIteratorSafe< int >* endSafe4Statics();
85 
90  static const SetIteratorSafe< int >* constEndSafe4Statics();
91 
96  static const SetIterator< int >* end4Statics();
97 
102  static const SetIterator< int >* constEnd4Statics();
103 
105  template < typename Key, typename Alloc >
106  friend class Set;
107  };
108 
109 
110  // ===========================================================================
111  // === GUM_SET ===
112  // ===========================================================================
113 
161  template < typename Key, typename Alloc = std::allocator< Key > >
162  class Set {
163  public:
166  using value_type = Key;
167  using reference = Key&;
168  using const_reference = const Key&;
169  using pointer = Key*;
170  using const_pointer = const Key*;
171  using size_type = std::size_t;
172  using difference_type = std::ptrdiff_t;
173  using allocator_type = Alloc;
174  using iterator = SetIterator< Key >;
175  using const_iterator = SetIterator< Key >;
176  using iterator_safe = SetIteratorSafe< Key >;
177  using const_iterator_safe = SetIteratorSafe< Key >;
179 
180  // ============================================================================
182  // ============================================================================
184 
197  explicit Set(Size capacity = HashTableConst::default_size,
198  bool resize_policy = true);
199 
204  Set(std::initializer_list< Key > list);
205 
210  Set(const Set< Key, Alloc >& aHT);
211 
217  template < typename OtherAlloc >
218  Set(const Set< Key, OtherAlloc >& aHT);
219 
224  Set(Set< Key, Alloc >&& aHT);
225 
229  ~Set();
230 
232  // ============================================================================
234  // ============================================================================
236 
242  Set< Key, Alloc >& operator=(const Set< Key, Alloc >& from);
243 
250  template < typename OtherAlloc >
251  Set< Key, Alloc >& operator=(const Set< Key, OtherAlloc >& from);
252 
258  Set< Key, Alloc >& operator=(Set< Key, Alloc >&& from);
259 
266  template < typename OtherAlloc >
267  bool operator==(const Set< Key, OtherAlloc >& s2) const;
268 
275  template < typename OtherAlloc >
276  bool operator!=(const Set< Key, OtherAlloc >& s2) const;
277 
285  template < typename OtherAlloc >
286  const Set< Key, Alloc >& operator*=(const Set< Key, OtherAlloc >& s2);
287 
295  template < typename OtherAlloc >
296  Set< Key, Alloc > operator*(const Set< Key, OtherAlloc >& s2) const;
297 
305  template < typename OtherAlloc >
306  const Set< Key, Alloc >& operator+=(const Set< Key, OtherAlloc >& s2);
307 
315  template < typename OtherAlloc >
316  Set< Key, Alloc > operator+(const Set< Key, OtherAlloc >& s2) const;
317 
318 
326  template < typename OtherAlloc >
327  Set< Key, Alloc > operator-(const Set< Key, OtherAlloc >& s2) const;
328 
334  Set< Key, Alloc >& operator<<(const Key& k);
335 
341  Set< Key, Alloc >& operator<<(Key&& k);
342 
348  Set< Key, Alloc >& operator>>(const Key& k);
349 
351  // ============================================================================
353  // ============================================================================
355 
362  void insert(const Key& k);
363 
370  void insert(Key&& k);
371 
382  template < typename... Args >
383  void emplace(Args&&... args);
384 
392  void erase(const Key& k);
393 
400  void erase(const iterator_safe& k);
401 
405  void clear();
406 
411  Size size() const noexcept;
412 
417  bool contains(const Key& k) const;
418 
422  template < typename OtherAlloc >
423  bool isSubsetOf(const Set< Key, OtherAlloc >& s) const;
424 
428  template < typename OtherAlloc >
429  bool isSupersetOf(const Set< Key, OtherAlloc >& s) const;
430 
435  bool exists(const Key& k) const;
436 
441  bool empty() const noexcept;
442 
447  std::string toString() const;
448 
450  // ============================================================================
452  // ============================================================================
454 
459  iterator_safe beginSafe() const;
460 
465  const_iterator_safe cbeginSafe() const;
466 
471  const iterator_safe& endSafe() const noexcept;
472 
477  const const_iterator_safe& cendSafe() const noexcept;
478 
483  iterator begin() const;
484 
489  const_iterator cbegin() const;
490 
495  const iterator& end() const noexcept;
496 
501  const const_iterator& cend() const noexcept;
502 
538  static const iterator& end4Statics();
539 
575  static const const_iterator& constEnd4Statics();
576 
612  static const iterator_safe& endSafe4Statics();
613 
649  static const const_iterator_safe& constEndSafe4Statics();
650 
652  // ============================================================================
654  // ============================================================================
656 
666  Size capacity() const;
667 
675  void resize(Size new_capacity);
676 
687  void setResizePolicy(const bool new_policy);
688 
694  bool resizePolicy() const;
695 
697  // ============================================================================
699  // ============================================================================
701 
714  template <
715  typename NewKey,
716  typename NewAlloc = typename Alloc::template rebind< NewKey >::other >
717  HashTable< Key, NewKey, NewAlloc > hashMap(NewKey (*f)(const Key&),
718  Size capacity = 0) const;
719 
733  template <
734  typename NewKey,
735  typename NewAlloc = typename Alloc::template rebind< NewKey >::other >
736  HashTable< Key, NewKey, NewAlloc > hashMap(const NewKey& val,
737  Size size = 0) const;
738 
747  template <
748  typename NewKey,
749  typename NewAlloc = typename Alloc::template rebind< NewKey >::other >
750  List< NewKey, NewAlloc > listMap(NewKey (*f)(const Key&)) const;
751 
753 
754  private:
757  friend class SetIterator< Key >;
758  friend class SetIteratorSafe< Key >;
759  template < typename K, typename A >
760  friend class Set;
762 
764  HashTable< Key, bool, Alloc > __inside;
765 
767  Set(const HashTable< Key, bool, Alloc >& h);
768  };
769 
770 
771  // ===========================================================================
772  // === SAFE SET ITERATORS ===
773  // ===========================================================================
774 
807  template < typename Key >
808  class SetIteratorSafe {
809  public:
812  using iterator_category = std::forward_iterator_tag;
813  using value_type = Key;
814  using reference = value_type&;
815  using const_reference = const value_type&;
816  using pointer = value_type*;
817  using const_pointer = const value_type*;
818  using difference_type = std::ptrdiff_t;
820 
825  enum Position { BEGIN, END };
826 
827  // ============================================================================
829  // ============================================================================
831 
835  SetIteratorSafe();
836 
847  template < typename Alloc >
848  SetIteratorSafe(const Set< Key, Alloc >& from, Position pos = BEGIN);
849 
854  SetIteratorSafe(const SetIteratorSafe< Key >& from);
855 
860  explicit SetIteratorSafe(const SetIterator< Key >& from);
861 
866  SetIteratorSafe(SetIteratorSafe< Key >&& from);
867 
871  ~SetIteratorSafe() noexcept;
872 
874  // ============================================================================
876  // ============================================================================
878 
884  SetIteratorSafe< Key >& operator=(const SetIteratorSafe< Key >& from);
885 
891  SetIteratorSafe< Key >& operator=(const SetIterator< Key >& from);
892 
898  SetIteratorSafe< Key >& operator=(SetIteratorSafe< Key >&& from) noexcept;
899 
904  SetIteratorSafe< Key >& operator++() noexcept;
905 
911  SetIteratorSafe< Key >& operator+=(Size i) noexcept;
912 
918  SetIteratorSafe< Key > operator+(Size i) const;
919 
926  bool operator!=(const SetIteratorSafe< Key >& from) const noexcept;
927 
934  bool operator==(const SetIteratorSafe< Key >& from) const noexcept;
935 
945  const Key& operator*() const;
946 
956  const Key* operator->() const;
957 
959  // ============================================================================
961  // ============================================================================
963 
968  void clear() noexcept;
969 
971 
972  private:
974  template < typename K, typename A >
975  friend class Set;
976 
978  HashTableConstIteratorSafe< Key, bool > __ht_iter;
979  };
980 
981  // ===========================================================================
982  // === UNSAFE SET ITERATORS ===
983  // ===========================================================================
984 
1021  template < typename Key >
1022  class SetIterator {
1023  public:
1026  using iterator_category = std::forward_iterator_tag;
1027  using value_type = Key;
1028  using reference = value_type&;
1029  using const_reference = const value_type&;
1030  using pointer = value_type*;
1031  using const_pointer = const value_type*;
1032  using difference_type = std::ptrdiff_t;
1034 
1039  enum Position { BEGIN, END };
1040 
1041  // ============================================================================
1043  // ============================================================================
1045 
1049  SetIterator() noexcept;
1050 
1061  template < typename Alloc >
1062  SetIterator(const Set< Key, Alloc >& from, Position pos = BEGIN);
1063 
1068  SetIterator(const SetIterator< Key >& from) noexcept;
1069 
1074  SetIterator(SetIterator< Key >&& from) noexcept;
1075 
1079  ~SetIterator() noexcept;
1080 
1082  // ============================================================================
1084  // ============================================================================
1086 
1092  SetIterator< Key >& operator=(const SetIterator< Key >& from) noexcept;
1093 
1099  SetIterator< Key >& operator=(SetIterator< Key >&& from) noexcept;
1100 
1105  SetIterator< Key >& operator++() noexcept;
1106 
1112  SetIterator< Key >& operator+=(Size i) noexcept;
1113 
1119  SetIterator< Key > operator+(Size i) const noexcept;
1120 
1127  bool operator!=(const SetIterator< Key >& from) const noexcept;
1128 
1135  bool operator==(const SetIterator< Key >& from) const noexcept;
1136 
1146  const Key& operator*() const;
1147 
1157  const Key* operator->() const;
1158 
1160  // ============================================================================
1162  // ============================================================================
1164 
1169  void clear() noexcept;
1170 
1172 
1173  private:
1175  template < typename K, typename A >
1176  friend class Set;
1177  friend class SetIteratorSafe< Key >;
1178 
1180  HashTableConstIterator< Key, bool > __ht_iter;
1181  };
1182 
1183 
1185  template < typename Key, typename Alloc >
1186  std::ostream& operator<<(std::ostream&, const Set< Key, Alloc >&);
1187 
1188 
1190  template < typename T, typename Alloc >
1191  class HashFunc< Set< T, Alloc > > : public HashFuncBase< Set< T, Alloc > > {
1192  public:
1198  static Size castToSize(const Set< T, Alloc >& key);
1199 
1201  virtual Size operator()(const Set< T, Alloc >& key) const override final;
1202  };
1203 
1204 } /* namespace gum */
1205 
1206 
1207 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1208 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1209 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1210 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1211 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1212 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1213 extern template class gum::Set< int >;
1214 # endif
1215 # endif
1216 # endif
1217 # endif
1218 # endif
1219 #endif
1220 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1221 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1222 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1223 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1224 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1225 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1226 extern template class gum::Set< long >;
1227 # endif
1228 # endif
1229 # endif
1230 # endif
1231 # endif
1232 #endif
1233 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1234 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1235 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1236 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1237 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1238 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1239 extern template class gum::Set< unsigned int >;
1240 # endif
1241 # endif
1242 # endif
1243 # endif
1244 # endif
1245 #endif
1246 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1247 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1248 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1249 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1250 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1251 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1252 extern template class gum::Set< unsigned long >;
1253 # endif
1254 # endif
1255 # endif
1256 # endif
1257 # endif
1258 #endif
1259 
1260 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1261 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1262 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1263 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1264 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1265 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1266 extern template class gum::Set< double >;
1267 # endif
1268 # endif
1269 # endif
1270 # endif
1271 # endif
1272 #endif
1273 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1274 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1275 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1276 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1277 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1278 # ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
1279 extern template class gum::Set< std::string >;
1280 # endif
1281 # endif
1282 # endif
1283 # endif
1284 # endif
1285 #endif
1286 
1287 
1288 // always include the implementation of the templates
1289 #include <agrum/core/set_tpl.h>
1290 
1291 #endif // GUM_SET_H
gum::Potential
aGrUM&#39;s Potential is a multi-dimensional array with tensor operators.
Definition: potential.h:57
gum::SetIterator::pointer
value_type * pointer
Types for STL compliance.
Definition: set.h:1030
set_tpl.h
Implementation of the Set.
gum::operator+
Formula operator+(const Formula &a, const Formula &b)
Definition: formula_inl.h:459
gum::SetIteratorSafe
Safe iterators for the Set classDevelopers may consider using Set<x>::iterator_safe instead of SetIte...
Definition: set.h:808
gum::SetIterator::value_type
Key value_type
Types for STL compliance.
Definition: set.h:1027
std
STL namespace.
gum::SetIterator::iterator_category
std::forward_iterator_tag iterator_category
Types for STL compliance.
Definition: set.h:1026
gum::HashTableConst::default_size
static constexpr Size default_size
The default number of slots in hashtables.
Definition: hashTable.h:77
gum::HashFunc
Class template representing hashing function of LpCol.
Definition: hashFunc.h:469
gum::DiscreteVariable
Base class for discrete random variable.
Definition: discreteVariable.h:57
gum::List
Generic doubly linked lists.
Definition: list.h:369
gum
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
gum::HashTable
The class for generic Hash Tables.
Definition: hashTable.h:676
gum::Set
Representation of a setA Set is a structure that contains arbitrary elements.
Definition: set.h:162
gum::SetIterator::reference
value_type & reference
Types for STL compliance.
Definition: set.h:1028
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:978
gum::SetIterator::Position
Position
An enumeration to position the iterator at the beginning or the end of the set.
Definition: set.h:1039
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:583
list.h
Generic class for manipulating lists.
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:1180
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:825
gum::SetIterator::const_reference
const value_type & const_reference
Types for STL compliance.
Definition: set.h:1029
gum::operator*
Formula operator*(const Formula &a, const Formula &b)
Definition: formula_inl.h:469
gum::SetIteratorSafe< const gum::DiscreteVariable * >::iterator_category
std::forward_iterator_tag iterator_category
Types for STL compliance.
Definition: set.h:812
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:346
gum::SetIterator
Unsafe iterators for the Set class.
Definition: set.h:1022
gum::SetIterator::difference_type
std::ptrdiff_t difference_type
Types for STL compliance.
Definition: set.h:1032
gum::Set< gum::Potential< GUM_SCALAR > * >::allocator_type
std::allocator< gum::Potential< GUM_SCALAR > * > allocator_type
Definition: set.h:173
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:147
gum::SetIterator::const_pointer
const value_type * const_pointer
Types for STL compliance.
Definition: set.h:1031
gum::Size
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:45
gum::operator>>
MultiDimInterface & operator>>(MultiDimInterface &c, const DiscreteVariable &v)
Removes a var from the variables of the MutliDimAdressing.
Definition: multiDimInterface.cpp:39
hashTable.h
Class hash tables iterators.
aGrUM 0.14.2
Thu Feb 28 2019 14:11:11
© CG&PHW&others - LIP6 2005-2007-2012
DoXyGeN 1.8.13