1 /** 2 * 3 * Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU) 4 * info_at_agrum_dot_org 5 * 6 * This library is free software: you can redistribute it and/or modify 7 * it under the terms of the GNU Lesser General Public License as published by 8 * the Free Software Foundation, either version 3 of the License, or 9 * (at your option) any later version. 10 * 11 * This library is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU Lesser General Public License for more details. 15 * 16 * You should have received a copy of the GNU Lesser General Public License 17 * along with this library. If not, see <http://www.gnu.org/licenses/>. 18 * 19 */ 20 21 22 /** @file 23 * @brief A class used by learning caches to represent uniquely sets of variables 24 * 25 * @author Christophe GONZALES(_at_AMU) and Pierre-Henri WUILLEMIN(_at_LIP6) 26 */ 27 #ifndef GUM_LEARNING_ID_SET_H 28 #define GUM_LEARNING_ID_SET_H 29 30 #include <iostream> 31 #include <sstream> 32 #include <string> 33 #include <type_traits> 34 #include <utility> 35 #include <vector> 36 37 #include <agrum/agrum.h> 38 #include <agrum/tools/core/sequence.h> 39 #include <agrum/tools/graphs/graphElements.h> 40 41 namespace gum { 42 43 namespace learning { 44 45 46 template < template < typename > class ALLOC > 47 class IdCondSet; 48 49 50 /** @class IdCondSetIterator 51 * @brief The iterators for IdSets 52 * @headerfile idCondSet.h <agrum/BN/learning/scores_and_tests/idSet.h> 53 * @ingroup learning_scores 54 */ 55 template < template < typename > class ALLOC = std::allocator > 56 class IdCondSetIterator { 57 public: 58 /// types for STL compliance 59 /// @{ 60 using iterator_category = std::forward_iterator_tag; 61 using value_type = NodeId; 62 using reference = NodeId&; 63 using const_reference = const NodeId&; 64 using pointer = NodeId*; 65 using const_pointer = const NodeId*; 66 using difference_type = std::ptrdiff_t; 67 /// @} 68 69 70 // ########################################################################## 71 /// @name Constructors / Destructors 72 // ########################################################################## 73 /// @{ 74 75 /// default constructor 76 /** @return an iterator pointing toward nothing. */ 77 IdCondSetIterator(); 78 79 /// Constructor for a begin 80 /** @param idset The IdCondSet to iterate over. */ 81 IdCondSetIterator(const IdCondSet< ALLOC >& idset); 82 83 /// Copy constructor. 84 IdCondSetIterator(const IdCondSetIterator< ALLOC >& from); 85 86 /// move constructor 87 IdCondSetIterator(IdCondSetIterator< ALLOC >&& from); 88 89 /// destructor 90 virtual ~IdCondSetIterator(); 91 92 /// @} 93 94 95 // ########################################################################## 96 /// @name Operators 97 // ########################################################################## 98 /// @{ 99 100 /// copy operator 101 IdCondSetIterator< ALLOC >& operator=(const IdCondSetIterator< ALLOC >& from); 102 103 /// move operator 104 IdCondSetIterator< ALLOC >& operator=(IdCondSetIterator< ALLOC >&& from); 105 106 /** @brief Gives access to the content of the iterator. 107 * @throw UndefinedIteratorValue Raised if the iterator points to nothing. 108 * @return Returns the content of the iterator. 109 */ 110 NodeId operator*() const; 111 112 /// Checks whether two iterators point toward different elements. 113 bool operator!=(const IdCondSetIterator< ALLOC >& from) const; 114 115 /// Checks whether two iterators point toward the same elements. 116 bool operator==(const IdCondSetIterator< ALLOC >& from) const; 117 118 /** @brief Makes the iterator point to the next element in the IdCondSet 119 * 120 * @code 121 * for (iter = idset.begin(); iter != idset.end(); ++iter) {} 122 * @endcode 123 * 124 * The above loop is guaranteed to parse the whole IdCondSet as long as no 125 * element is added to or deleted from the IdCondSet while being in the loop. 126 * 127 * @return Returns this gum::IdCondSetIterator. 128 */ 129 IdCondSetIterator< ALLOC >& operator++(); 130 131 /** 132 * @brief Makes the iterator point to i elements further in the IdCondSet 133 * @param i The number of steps to move the iterator. 134 * @return Returns this gum::IdCondSetIterator. 135 */ 136 IdCondSetIterator< ALLOC >& operator+=(const std::size_t i); 137 138 /** 139 * @brief Returns a new iterator pointing to i further elements in the 140 * IdCondSet 141 * @param i The number of steps to move the iterator. 142 * @return Returns a new gum::IdCondSetIterator. 143 */ 144 IdCondSetIterator< ALLOC > operator+(const std::size_t i); 145 146 /// @} 147 148 149 // ########################################################################## 150 /// @name Accessors / Modifiers 151 // ########################################################################## 152 /// @{ 153 154 /** 155 * @brief Returns the position of the iterator in the IdCondSet. 156 * @return Returns the position of the iterator in the IdCondSet. 157 * @throw UndefinedIteratorValue Raised on end() 158 */ 159 std::size_t pos() const; 160 161 /// @} 162 163 164 #ifndef DOXYGEN_SHOULD_SKIP_THIS 165 166 private: 167 /// a pointer on the sequence stored in the IdCondSet 168 const Sequence< NodeId, ALLOC< NodeId > >* _seq_{nullptr}; 169 170 /// The index in the IdCondSet's sequence where the iterator is pointing. 171 std::size_t _index_{std::size_t(0)}; 172 173 174 /// places the index to the end of the sequence 175 void _gotoEnd_(); 176 177 friend class IdCondSet< ALLOC >; 178 179 #endif /* DOXYGEN_SHOULD_SKIP_THIS */ 180 }; 181 182 183 /** @class IdCondSet 184 * @brief A class for storing a pair of sets of NodeIds, the second one 185 * corresponding to a conditional set. 186 * @headerfile idSet.h <agrum/BN/learning/scores_and_tests/idSet.h> 187 * @ingroup learning_scores 188 * 189 * IdCondSets are used by learning caches to store pairs of sets of nodes, 190 * the second ones represent typically conditional sets. 191 * This is useful for storing in hashtables the scores assigned to sets 192 * of nodes given other nodes. NodeSets are actually not well suited for 193 * this purpose because their implementations makes the computation of their 194 * hash values quite difficult. IdCondSets fix this issue. 195 */ 196 template < template < typename > class ALLOC = std::allocator > 197 class IdCondSet: private ALLOC< NodeId > { 198 public: 199 /// type for the allocators passed in arguments of methods 200 using allocator_type = ALLOC< NodeId >; 201 202 using iterator = IdCondSetIterator< ALLOC >; 203 using const_iterator = IdCondSetIterator< ALLOC >; 204 using iterator_safe = IdCondSetIterator< ALLOC >; 205 using const_iterator_safe = IdCondSetIterator< ALLOC >; 206 207 // ########################################################################## 208 /// @name Constructors / Destructors 209 // ########################################################################## 210 /// @{ 211 212 /// default constructor 213 IdCondSet(const allocator_type& alloc = allocator_type()); 214 215 /// default constructor with no variable on the left side 216 /** @param ids the set of variables 217 * @param rhs_ids indicate whether the ids are on the right side of the 218 * conditioning bar or not 219 * @param ordered_ids indicates whether the ids in rhs_ids should be 220 * considered as an ordered set or an unordered set 221 * @param alloc the allocator used to store the data in the IdCondSet */ 222 IdCondSet(const std::vector< NodeId, ALLOC< NodeId > >& ids, 223 const bool rhs_ids, 224 const bool ordered_ids, 225 const allocator_type& alloc = allocator_type()); 226 227 /// default constructor with one variable on the left side 228 /** @param var1 the variable on the left side of the conditioning bar 229 * @param rhs_ids the set of variables on the right side of the 230 * conditioning bar 231 * @param ordered_rhs_ids indicates whether the ids in rhs_ids should be 232 * considered as an ordered set or an unordered set 233 * @param alloc the allocator used to store the data in the IdCondSet */ 234 IdCondSet(NodeId var1, 235 const std::vector< NodeId, ALLOC< NodeId > >& rhs_ids, 236 const bool ordered_rhs_ids = false, 237 const allocator_type& alloc = allocator_type()); 238 239 /// default constructor with two variables on the left side 240 /** @param var1 the 1st variable on the left side of the conditioning bar 241 * @param var2 the 2nd variable on the left side of the conditioning bar 242 * @param rhs_ids the set of variables on the right side of the 243 * conditioning bar 244 * @param ordered_lhs_vars a Boolean indicating whether {var1,var2} should 245 * be considered as an ordered set or not. Typically, in an independence 246 * test, this set is unordered. When set to false, 247 * @param ordered_rhs_ids indicates whether the ids in rhs_ids should be 248 * considered as an ordered set or an unordered set 249 * @param ordered_rhs_ids 250 * @param alloc the allocator used to store the data in the IdCondSet */ 251 IdCondSet(NodeId var1, 252 NodeId var2, 253 const std::vector< NodeId, ALLOC< NodeId > >& rhs_ids, 254 const bool ordered_lhs_vars, 255 const bool ordered_rhs_ids = false, 256 const allocator_type& alloc = allocator_type()); 257 258 /// default constructor with three variables on the left side 259 /** @param var1 the 1st variable on the left side of the conditioning bar 260 * @param var2 the 2nd variable on the left side of the conditioning bar 261 * @param var3 the 3rd variable on the left side of the conditioning bar 262 * @param rhs_ids the set of variables on the right side of the 263 * conditioning bar 264 * @param ordered_vars a Boolean indicating whether {var1,var2,var3} 265 * should be considered as an ordered set or not. 266 * @param ordered_rhs_ids indicates whether the ids in rhs_ids should be 267 * considered as an ordered set or an unordered set 268 * @param alloc the allocator used to store the data in the IdCondSet */ 269 IdCondSet(NodeId var1, 270 NodeId var2, 271 NodeId var3, 272 const std::vector< NodeId, ALLOC< NodeId > >& rhs_ids, 273 const bool ordered_lhs_vars, 274 const bool ordered_rhs_ids = false, 275 const allocator_type& alloc = allocator_type()); 276 277 /// copy constructor 278 IdCondSet(const IdCondSet< ALLOC >& from); 279 280 /// copy constructor with a given allocator 281 IdCondSet(const IdCondSet< ALLOC >& from, const allocator_type& alloc); 282 283 /// move constructor 284 IdCondSet(IdCondSet< ALLOC >&& from); 285 286 /// move constructor with a given allocator 287 IdCondSet(IdCondSet< ALLOC >&& from, const allocator_type& alloc); 288 289 /// virtual copy constructor 290 virtual IdCondSet< ALLOC >* clone() const; 291 292 /// virtual copy constructor with a given allocator 293 virtual IdCondSet< ALLOC >* clone(const allocator_type& alloc) const; 294 295 /// destructor 296 virtual ~IdCondSet(); 297 298 /// @} 299 300 301 // ########################################################################## 302 /// @name Operators 303 // ########################################################################## 304 /// @{ 305 306 /// copy operator 307 IdCondSet< ALLOC >& operator=(const IdCondSet< ALLOC >& from); 308 309 /// move operator 310 IdCondSet< ALLOC >& operator=(IdCondSet< ALLOC >&& from); 311 312 /// returns the node id stored at a given index 313 NodeId operator[](const std::size_t index) const; 314 315 /// returns true if both sets are equal 316 bool operator==(const IdCondSet< ALLOC >& from) const; 317 318 /// returns true if the sets differ 319 bool operator!=(const IdCondSet< ALLOC >& from) const; 320 321 /// @} 322 323 324 // ########################################################################## 325 /// @name Iterators 326 // ########################################################################## 327 /// @{ 328 329 /** 330 * @brief Returns a safe begin iterator. 331 * @return Returns a safe begin iterator. 332 */ 333 iterator_safe beginSafe() const; 334 335 /** 336 * @brief Returns the safe end iterator. 337 * @return Returns the safe end iterator. 338 */ 339 const iterator_safe& endSafe() const; 340 341 /** 342 * @brief Returns an unsafe begin iterator. 343 * @return Returns an unsafe begin iterator. 344 */ 345 iterator begin() const; 346 347 /** 348 * @brief Returns the unsafe end iterator. 349 * @return Returns the unsafe end iterator. 350 */ 351 const iterator& end() const; 352 353 /// @} 354 355 356 // ########################################################################## 357 /// @name Accessors / Modifiers 358 // ########################################################################## 359 /// @{ 360 361 /// returns the set of ids 362 const Sequence< NodeId, ALLOC< NodeId > >& ids() const; 363 364 /// returns the idSet at the right hand side of the conditioning bar 365 IdCondSet< ALLOC > conditionalIdCondSet() const; 366 367 /// returns the number of left hand side ids 368 std::size_t nbLHSIds() const; 369 370 /// returns the number of right hand side ids 371 std::size_t nbRHSIds() const; 372 373 /// indicates whether the IdCondSet contains the IdCondSet passed in argument 374 bool contains(const IdCondSet< ALLOC >& set) const; 375 376 /// removes all the nodes from the IdCondSet 377 void clear(); 378 379 /// returns the number of variables (both left and right hand side) 380 std::size_t size() const; 381 382 /// returns the position of a given node in the IdCondSet 383 /** @throw NotFound Raised if the element does not exist. */ 384 std::size_t pos(const NodeId id) const; 385 386 /// indicates whether a given id is contained in the IdCondSet 387 bool exists(const NodeId id) const; 388 389 /// erase a node in the idset 390 /** If the element cannot be found, the function does nothing. In 391 * particular, it throws no exception. */ 392 void erase(const NodeId id); 393 394 /// indicates whether the idset contains a non-empty conditioning set 395 bool hasConditioningSet() const; 396 397 /// indicates whether the IdCondSet contains some nodes or not 398 bool empty() const; 399 400 /// returns the content of the set as a string 401 std::string toString() const; 402 403 /// returns the allocator used 404 allocator_type getAllocator() const; 405 406 /// @} 407 408 409 #ifndef DOXYGEN_SHOULD_SKIP_THIS 410 411 private: 412 /// the ordered set of ids on the right side of the conditioning bar 413 Sequence< NodeId, ALLOC< NodeId > > _ids_; 414 415 /// the number of left ids 416 std::size_t _nb_lhs_ids_{std::size_t(0)}; 417 418 /// Stores the end iterator for fast access. 419 IdCondSetIterator< ALLOC > _end_safe_; 420 421 #endif /* DOXYGEN_SHOULD_SKIP_THIS */ 422 }; 423 424 425 /// the display operator 426 template < template < typename > class ALLOC > 427 std::ostream& operator<<(std::ostream& stream, const IdCondSet< ALLOC >& idset); 428 429 } /* namespace learning */ 430 431 432 /// the hash function for idSets 433 template < template < typename > class ALLOC > 434 class HashFunc< learning::IdCondSet< ALLOC > >: 435 public HashFuncBase< learning::IdCondSet< ALLOC > > { 436 public: 437 /** 438 * @brief Returns the value of a key as a Size. 439 * @param key The value to return as a Size. 440 * @return Returns the value of a key as a Size. 441 */ 442 static Size castToSize(const learning::IdCondSet< ALLOC >& key); 443 444 /// computes the hashed value of a key 445 virtual Size operator()(const learning::IdCondSet< ALLOC >& key) const override final; 446 }; 447 448 449 } /* namespace gum */ 450 451 452 // always include the template implementation 453 #include <agrum/tools/stattests/idCondSet_tpl.h> 454 455 #endif /* GUM_LEARNING_ID_SET_H */ 456