aGrUM  0.14.2
idSet_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  ***************************************************************************/
26 #ifndef DOXYGEN_SHOULD_SKIP_THIS
27 
28 
29 namespace gum {
30 
31  namespace learning {
32 
33 
35  template < template < typename > class ALLOC >
36  INLINE IdSetIterator< ALLOC >::IdSetIterator() {
37  GUM_CONSTRUCTOR(IdSetIterator);
38  }
39 
40 
42  template < template < typename > class ALLOC >
43  INLINE IdSetIterator< ALLOC >::IdSetIterator(const IdSet< ALLOC >& idset) :
44  __seq(&(idset.ids())) {
45  GUM_CONSTRUCTOR(IdSetIterator);
46  }
47 
48 
50  template < template < typename > class ALLOC >
51  INLINE
52  IdSetIterator< ALLOC >::IdSetIterator(const IdSetIterator< ALLOC >& from) :
53  __seq(from.__seq),
54  __index(from.__index) {
55  GUM_CONS_CPY(IdSetIterator);
56  }
57 
58 
60  template < template < typename > class ALLOC >
61  INLINE IdSetIterator< ALLOC >::IdSetIterator(IdSetIterator< ALLOC >&& from) :
62  __seq(from.__seq), __index(from.__index) {
63  GUM_CONS_MOV(IdSetIterator);
64  }
65 
66 
68  template < template < typename > class ALLOC >
69  INLINE IdSetIterator< ALLOC >::~IdSetIterator() {
70  GUM_DESTRUCTOR(IdSetIterator);
71  }
72 
73 
75  template < template < typename > class ALLOC >
76  INLINE void IdSetIterator< ALLOC >::__gotoEnd() {
77  if (__seq != nullptr)
78  __index = __seq->size();
79  else
80  __index = std::size_t(0);
81  }
82 
83 
85  template < template < typename > class ALLOC >
86  INLINE IdSetIterator< ALLOC >& IdSetIterator< ALLOC >::
87  operator=(const IdSetIterator< ALLOC >& from) {
88  __seq = from.__seq;
89  __index = from.__index;
90  return *this;
91  }
92 
93 
95  template < template < typename > class ALLOC >
96  INLINE IdSetIterator< ALLOC >& IdSetIterator< ALLOC >::
97  operator=(IdSetIterator< ALLOC >&& from) {
98  __seq = from.__seq;
99  __index = from.__index;
100  return *this;
101  }
102 
103 
105  template < template < typename > class ALLOC >
106  INLINE NodeId IdSetIterator< ALLOC >::operator*() const {
107  return __seq->operator[](__index);
108  }
109 
110 
112  template < template < typename > class ALLOC >
113  INLINE bool IdSetIterator< ALLOC >::
114  operator!=(const IdSetIterator< ALLOC >& from) const {
115  return (__index != from.__index) || (__seq != from.__seq);
116  }
117 
118 
120  template < template < typename > class ALLOC >
121  INLINE bool IdSetIterator< ALLOC >::
122  operator==(const IdSetIterator< ALLOC >& from) const {
123  return !operator!=(from);
124  }
125 
126 
128  template < template < typename > class ALLOC >
129  INLINE IdSetIterator< ALLOC >& IdSetIterator< ALLOC >::operator++() {
130  ++__index;
131  return *this;
132  }
133 
134 
136  template < template < typename > class ALLOC >
137  INLINE IdSetIterator< ALLOC >& IdSetIterator< ALLOC >::
138  operator+=(const std::size_t i) {
139  __index += i;
140  return *this;
141  }
142 
143 
145  template < template < typename > class ALLOC >
146  IdSetIterator< ALLOC > IdSetIterator< ALLOC >::operator+(const std::size_t i) {
147  IdSetIterator< ALLOC > res(*this);
148  res += i;
149  return res;
150  }
151 
152 
154  template < template < typename > class ALLOC >
155  std::size_t IdSetIterator< ALLOC >::pos() const {
156  if (__seq == nullptr)
157  GUM_ERROR(UndefinedIteratorValue,
158  "The IdSet is empty, so its iterators have no position");
159  if (__index >= __seq->size())
160  GUM_ERROR(UndefinedIteratorValue,
161  "the IdSet iterator has no position because it reached "
162  "the set's end.");
163  return __index;
164  }
165 
166 
169 
170 
172  template < template < typename > class ALLOC >
173  INLINE typename IdSet< ALLOC >::allocator_type
174  IdSet< ALLOC >::getAllocator() const {
175  return *this;
176  }
177 
178 
180  template < template < typename > class ALLOC >
181  INLINE IdSet< ALLOC >::IdSet(
182  const typename IdSet< ALLOC >::allocator_type& alloc) :
183  ALLOC< NodeId >(alloc),
184  __end_safe(*this) {
185  GUM_CONSTRUCTOR(IdSet);
186  }
187 
188 
190  template < template < typename > class ALLOC >
191  INLINE IdSet< ALLOC >::IdSet(
192  const std::vector< NodeId, ALLOC< NodeId > >& ids,
193  const bool rhs_ids,
194  const bool ordered_ids,
195  const typename IdSet< ALLOC >::allocator_type& alloc) :
196  ALLOC< NodeId >(alloc),
197  __end_safe(*this) {
198  __ids.resize(ids.size());
199 
200  // if the rhs_ids should be considered as unordered, we sort them by
201  // increasing order so that we can compare easily two different rhs_ids
202  if (!ordered_ids) {
203  std::vector< NodeId, ALLOC< NodeId > > vect(ids);
204  std::sort(vect.begin(), vect.end());
205  for (const auto id : vect)
206  __ids << id;
207  } else {
208  for (const auto id : ids)
209  __ids << id;
210  }
211 
212  if (!rhs_ids) __nb_lhs_ids = __ids.size();
213 
214  // update the end iterator
215  __end_safe.__gotoEnd();
216 
217  GUM_CONSTRUCTOR(IdSet);
218  }
219 
220 
222  template < template < typename > class ALLOC >
223  INLINE IdSet< ALLOC >::IdSet(
224  NodeId var1,
225  const std::vector< NodeId, ALLOC< NodeId > >& rhs_ids,
226  const bool ordered_rhs_ids,
227  const typename IdSet< ALLOC >::allocator_type& alloc) :
228  ALLOC< NodeId >(alloc),
229  __nb_lhs_ids(std::size_t(1)), __end_safe(*this) {
230  __ids.resize(rhs_ids.size() + std::size_t(1));
231  __ids << var1;
232 
233  // if the rhs_ids should be considered as unordered, we sort them by
234  // increasing order so that we can compare easily two different rhs_ids
235  if (!ordered_rhs_ids) {
236  std::vector< NodeId, ALLOC< NodeId > > vect(rhs_ids);
237  std::sort(vect.begin(), vect.end());
238  for (const auto id : vect)
239  __ids << id;
240  } else {
241  for (const auto id : rhs_ids)
242  __ids << id;
243  }
244 
245  // update the end iterator
246  __end_safe.__gotoEnd();
247 
248  GUM_CONSTRUCTOR(IdSet);
249  }
250 
251 
253  template < template < typename > class ALLOC >
254  INLINE IdSet< ALLOC >::IdSet(
255  NodeId var1,
256  NodeId var2,
257  const std::vector< NodeId, ALLOC< NodeId > >& rhs_ids,
258  const bool ordered_lhs_vars,
259  const bool ordered_rhs_ids,
260  const typename IdSet< ALLOC >::allocator_type& alloc) :
261  ALLOC< NodeId >(alloc),
262  __nb_lhs_ids(std::size_t(2)), __end_safe(*this) {
263  __ids.resize(rhs_ids.size() + std::size_t(2));
264 
265  // if the variables on the left side are unordered, sort them by
266  // increasing order
267  if (!ordered_lhs_vars && (var1 > var2)) std::swap(var1, var2);
268  __ids << var1;
269  __ids << var2;
270 
271  // if the rhs_ids should be considered as unordered, we sort them by
272  // increasing order so that we can compare easily two different rhs_ids
273  if (!ordered_rhs_ids) {
274  std::vector< NodeId, ALLOC< NodeId > > vect(rhs_ids);
275  std::sort(vect.begin(), vect.end());
276  for (const auto id : vect)
277  __ids << id;
278  } else {
279  for (const auto id : rhs_ids)
280  __ids << id;
281  }
282 
283  // update the end iterator
284  __end_safe.__gotoEnd();
285 
286  GUM_CONSTRUCTOR(IdSet);
287  }
288 
289 
291  template < template < typename > class ALLOC >
292  INLINE IdSet< ALLOC >::IdSet(
293  NodeId var1,
294  NodeId var2,
295  NodeId var3,
296  const std::vector< NodeId, ALLOC< NodeId > >& rhs_ids,
297  const bool ordered_lhs_vars,
298  const bool ordered_rhs_ids,
299  const typename IdSet< ALLOC >::allocator_type& alloc) :
300  ALLOC< NodeId >(alloc),
301  __nb_lhs_ids(std::size_t(3)), __end_safe(*this) {
302  __ids.resize(rhs_ids.size() + std::size_t(3));
303 
304  // if the variables on the left side are unordered, sort them by
305  // increasing order
306  if (!ordered_lhs_vars) {
307  if (var1 > var2) std::swap(var1, var2);
308  if (var1 > var3) std::swap(var1, var3);
309  if (var2 > var3) std::swap(var2, var3);
310  }
311  __ids << var1;
312  __ids << var2;
313  __ids << var3;
314 
315  // if the rhs_ids should be considered as unordered, we sort them by
316  // increasing order so that we can compare easily two different rhs_ids
317  if (!ordered_rhs_ids) {
318  std::vector< NodeId, ALLOC< NodeId > > vect(rhs_ids);
319  std::sort(vect.begin(), vect.end());
320  for (const auto id : vect)
321  __ids << id;
322  } else {
323  for (const auto id : rhs_ids)
324  __ids << id;
325  }
326 
327  // update the end iterator
328  __end_safe.__gotoEnd();
329 
330  GUM_CONSTRUCTOR(IdSet);
331  }
332 
333 
335  template < template < typename > class ALLOC >
336  INLINE IdSet< ALLOC >::IdSet(
337  const IdSet< ALLOC >& from,
338  const typename IdSet< ALLOC >::allocator_type& alloc) :
339  ALLOC< NodeId >(alloc),
340  __ids(from.__ids), __nb_lhs_ids(from.__nb_lhs_ids), __end_safe(*this) {
341  __end_safe.__gotoEnd();
342  GUM_CONS_CPY(IdSet);
343  }
344 
345 
347  template < template < typename > class ALLOC >
348  INLINE IdSet< ALLOC >::IdSet(const IdSet< ALLOC >& from) :
349  IdSet< ALLOC >(from, from.getAllocator()) {}
350 
351 
353  template < template < typename > class ALLOC >
354  INLINE IdSet< ALLOC >::IdSet(
355  IdSet< ALLOC >&& from,
356  const typename IdSet< ALLOC >::allocator_type& alloc) :
357  ALLOC< NodeId >(alloc),
358  __ids(std::move(from.__ids)), __nb_lhs_ids(from.__nb_lhs_ids),
359  __end_safe(*this) {
360  __end_safe.__gotoEnd();
361  GUM_CONS_MOV(IdSet);
362  }
363 
364 
366  template < template < typename > class ALLOC >
367  INLINE IdSet< ALLOC >::IdSet(IdSet< ALLOC >&& from) :
368  IdSet< ALLOC >(std::move(from), from.getAllocator()) {}
369 
370 
372  template < template < typename > class ALLOC >
373  IdSet< ALLOC >* IdSet< ALLOC >::clone(
374  const typename IdSet< ALLOC >::allocator_type& alloc) const {
375  ALLOC< IdSet< ALLOC > > allocator(alloc);
376  IdSet< ALLOC >* new_set = allocator.allocate(1);
377  try {
378  allocator.construct(new_set, *this, alloc);
379  } catch (...) {
380  allocator.deallocate(new_set, 1);
381  throw;
382  }
383 
384  return new_set;
385  }
386 
387 
389  template < template < typename > class ALLOC >
390  IdSet< ALLOC >* IdSet< ALLOC >::clone() const {
391  return clone(this->getAllocator());
392  }
393 
394 
396  template < template < typename > class ALLOC >
397  INLINE IdSet< ALLOC >::~IdSet() {
398  GUM_DESTRUCTOR(IdSet);
399  }
400 
401 
403  template < template < typename > class ALLOC >
404  INLINE IdSet< ALLOC >& IdSet< ALLOC >::operator=(const IdSet< ALLOC >& from) {
405  if (this != &from) {
406  __ids = from.__ids;
407  __nb_lhs_ids = from.__nb_lhs_ids;
408  __end_safe.__gotoEnd();
409  }
410  return *this;
411  }
412 
413 
415  template < template < typename > class ALLOC >
416  INLINE IdSet< ALLOC >& IdSet< ALLOC >::operator=(IdSet< ALLOC >&& from) {
417  if (this != &from) {
418  __ids = std::move(from.__ids);
419  __nb_lhs_ids = from.__nb_lhs_ids;
420  __end_safe.__gotoEnd();
421  }
422  return *this;
423  }
424 
425 
427  template < template < typename > class ALLOC >
428  INLINE NodeId IdSet< ALLOC >::operator[](const std::size_t index) const {
429  return __ids.atPos(index);
430  }
431 
432 
434  template < template < typename > class ALLOC >
435  INLINE bool IdSet< ALLOC >::operator==(const IdSet< ALLOC >& from) const {
436  if (__nb_lhs_ids != from.__nb_lhs_ids) return false;
437 
438  const std::size_t size = __ids.size();
439 
440  if (size != from.__ids.size()) return false;
441 
442  for (std::size_t i = std::size_t(0); i < size; ++i) {
443  if (__ids[i] != from.__ids[i]) return false;
444  }
445 
446  return true;
447  }
448 
449 
451  template < template < typename > class ALLOC >
452  INLINE bool IdSet< ALLOC >::operator!=(const IdSet< ALLOC >& from) const {
453  return !operator==(from);
454  }
455 
456 
458  template < template < typename > class ALLOC >
459  INLINE typename IdSet< ALLOC >::iterator_safe
460  IdSet< ALLOC >::beginSafe() const {
461  return IdSetIterator< ALLOC >(*this);
462  }
463 
464 
466  template < template < typename > class ALLOC >
467  INLINE const typename IdSet< ALLOC >::iterator_safe&
468  IdSet< ALLOC >::endSafe() const {
469  return __end_safe;
470  }
471 
472 
474  template < template < typename > class ALLOC >
475  INLINE typename IdSet< ALLOC >::iterator IdSet< ALLOC >::begin() const {
476  return IdSetIterator< ALLOC >(*this);
477  }
478 
479 
481  template < template < typename > class ALLOC >
482  INLINE const typename IdSet< ALLOC >::iterator& IdSet< ALLOC >::end() const {
483  return __end_safe;
484  }
485 
486 
488  template < template < typename > class ALLOC >
489  INLINE const Sequence< NodeId, ALLOC< NodeId > >& IdSet< ALLOC >::ids() const {
490  return __ids;
491  }
492 
493 
495  template < template < typename > class ALLOC >
496  IdSet< ALLOC > IdSet< ALLOC >::conditionalIdSet() const {
497  IdSet< ALLOC > set(this->getAllocator());
498  const std::size_t size = __ids.size();
499  for (std::size_t i = __nb_lhs_ids; i < size; ++i)
500  set.__ids << __ids[i];
501  set.__end_safe.__gotoEnd();
502  return set;
503  }
504 
505 
507  template < template < typename > class ALLOC >
508  void IdSet< ALLOC >::erase(const NodeId id) {
509  // search for id in Sequence __ids
510  const std::size_t size = __ids.size();
511  std::size_t pos = std::size_t(0);
512  for (; pos < size; ++pos) {
513  if (__ids[pos] == id) break;
514  }
515 
516  // if we found the id, remove it
517  if (pos < size) {
518  __ids.erase(SequenceIteratorSafe< NodeId >(__ids, pos));
519  if (pos < __nb_lhs_ids) --__nb_lhs_ids;
520  __end_safe.__gotoEnd();
521  }
522  }
523 
524 
526  template < template < typename > class ALLOC >
527  std::string IdSet< ALLOC >::toString() const {
528  std::stringstream str;
529 
530  str << '{';
531  bool deja = false;
532 
533  for (std::size_t i = std::size_t(0); i < __nb_lhs_ids; ++i) {
534  if (deja)
535  str << " , ";
536  else
537  deja = true;
538  str << __ids[i];
539  }
540 
541  deja = false;
542  for (auto iter = __ids.begin() + __nb_lhs_ids; iter != __ids.end(); ++iter) {
543  if (deja)
544  str << " , ";
545  else {
546  deja = true;
547  str << " | ";
548  }
549  str << *iter;
550  }
551 
552  str << '}';
553 
554  return str.str();
555  }
556 
557 
559  template < template < typename > class ALLOC >
560  INLINE std::size_t IdSet< ALLOC >::nbLHSIds() const {
561  return __nb_lhs_ids;
562  }
563 
564 
566  template < template < typename > class ALLOC >
567  INLINE std::size_t IdSet< ALLOC >::nbRHSIds() const {
568  return __ids.size() - __nb_lhs_ids;
569  }
570 
571 
573  template < template < typename > class ALLOC >
574  bool IdSet< ALLOC >::contains(const IdSet< ALLOC >& set) const {
575  if (set.__ids.size() > __ids.size()) return false;
576  for (const auto node : set.__ids) {
577  if (!__ids.exists(node)) return false;
578  }
579  return true;
580  }
581 
582 
584  template < template < typename > class ALLOC >
585  INLINE void IdSet< ALLOC >::clear() {
586  __ids.clear();
587  __nb_lhs_ids = std::size_t(0);
588  __end_safe.__gotoEnd();
589  }
590 
591 
593  template < template < typename > class ALLOC >
594  INLINE std::size_t IdSet< ALLOC >::size() const {
595  return __ids.size();
596  }
597 
598 
600  template < template < typename > class ALLOC >
601  INLINE std::size_t IdSet< ALLOC >::pos(const NodeId id) const {
602  return __ids.pos(id);
603  }
604 
605 
607  template < template < typename > class ALLOC >
608  INLINE bool IdSet< ALLOC >::exists(const NodeId id) const {
609  return __ids.exists(id);
610  }
611 
612 
614  template < template < typename > class ALLOC >
615  INLINE bool IdSet< ALLOC >::hasConditioningSet() const {
616  return __nb_lhs_ids != __ids.size();
617  }
618 
619 
621  template < template < typename > class ALLOC >
622  INLINE bool IdSet< ALLOC >::empty() const {
623  return __ids.empty();
624  }
625 
626 
627  // the display operator
628  template < template < typename > class ALLOC >
629  std::ostream& operator<<(std::ostream& stream, const IdSet< ALLOC >& idset) {
630  return stream << idset.toString();
631  }
632 
633  } /* namespace learning */
634 
635 
636  // Returns the value of a key as a Size.
637  template < template < typename > class ALLOC >
638  Size HashFunc< learning::IdSet< ALLOC > >::castToSize(
639  const learning::IdSet< ALLOC >& key) {
640  Size h = Size(key.nbLHSIds());
641  const Sequence< NodeId, ALLOC< NodeId > >& vect = key.ids();
642  const std::size_t size = vect.size();
643 
644  std::size_t i = std::size_t(0);
645  while (i < size) {
646  const Size id = Size(vect[i]);
647  ++i;
648  h += Size(i) * id;
649  }
650 
651  return h;
652  }
653 
654 
655  // the hash function for idSets
656  template < template < typename > class ALLOC >
657  INLINE Size HashFunc< learning::IdSet< ALLOC > >::
658  operator()(const learning::IdSet< ALLOC >& key) const {
659  return (castToSize(key) * HashFuncConst::gold) & this->_hash_mask;
660  }
661 
662 } /* namespace gum */
663 
664 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
gum::HashFuncConst::gold
static constexpr Size gold
Definition: hashFunc.h:74
std
STL namespace.
gum::credal::lp::swap
void swap(HashTable< LpCol, double > *&a, HashTable< LpCol, double > *&b)
Swap the addresses of two pointers to hashTables.
Definition: LpInterface_tpl.h:1035
gum
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
gum::credal::lp::operator+
LpExpr operator+(LpExpr &&lhs, const T2 &rhs)
Overload of operator + between anything ( a scalar, a variable or an expression ) and anything except...
Definition: LpInterface_tpl.h:1043
operator==
bool operator==(const TiXmlString &a, const TiXmlString &b)
Definition: tinystr.h:243
gum::learning::IdSetIterator::IdSetIterator
IdSetIterator()
default constructor
gum::credal::lp::operator*
LpExpr operator*(const SCALAR &lhs, const LpCol &rhs)
Overload of operator * between a scalar and a variable.
Definition: LpInterface_tpl.h:1161
operator!=
bool operator!=(const TiXmlString &a, const TiXmlString &b)
Definition: tinystr.h:251
gum::Size
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:45
gum::NodeId
Size NodeId
Type for node ids.
Definition: graphElements.h:97
GUM_ERROR
#define GUM_ERROR(type, msg)
Definition: exceptions.h:52
aGrUM 0.14.2
Thu Feb 28 2019 14:11:14
© CG&PHW&others - LIP6 2005-2007-2012
DoXyGeN 1.8.13