Generated on Mon Feb 8 2021 00:00:00 for Gecode by doxygen 1.8.20
complement.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Guido Tack <tack@gecode.org>
5  *
6  * Contributing authors:
7  * Christian Schulte <schulte@gecode.org>
8  *
9  * Copyright:
10  * Guido Tack, 2004
11  * Christian Schulte, 2004
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include <sstream>
39 
40 namespace Gecode { namespace Set {
41 
42  template<class View>
45 
46  template<class View>
49  : DerivedView<View>(y) {}
50 
51  template<class View>
54  switch(me) {
55  case ME_SET_LUB : return ME_SET_GLB;
56  case ME_SET_GLB : return ME_SET_LUB;
57  case ME_SET_CLUB : return ME_SET_CGLB;
58  case ME_SET_CGLB : return ME_SET_CLUB;
59  default: return me;
60  }
61  }
62 
63  template<class View>
66  switch(pc) {
67  case PC_SET_CLUB : return PC_SET_CGLB;
68  case PC_SET_CGLB : return PC_SET_CLUB;
69  default: return pc;
70  }
71  }
72 
73  template<class View>
74  forceinline unsigned int
76  return Limits::card - x.lubSize();
77  }
78 
79  template<class View>
80  forceinline unsigned int
82  return Limits::card - x.glbSize();
83  }
84 
85  template<class View>
86  forceinline unsigned int
88  return lubSize() - glbSize();
89  }
90 
91  template<class View>
92  forceinline bool
94 
95  template<class View>
96  forceinline bool
98 
99  template<class View>
100  forceinline unsigned int
102  return Limits::card - x.cardMax();
103  }
104 
105  template<class View>
106  forceinline unsigned int
108  return Limits::card - x.cardMin();
109  }
110 
111  template<class View>
112  forceinline int
114  GlbRanges<View> lb(x);
115  RangesCompl<GlbRanges<View> > lbc(lb);
116  if (lbc()) {
117  return lbc.min();
118  } else {
119  return BndSet::MIN_OF_EMPTY;
120  }
121  }
122 
123  template<class View>
124  forceinline int
126  GlbRanges<View> lb(x);
127  RangesCompl<GlbRanges<View> > lbc(lb);
128  if (lbc()) {
129  while(lbc()) ++lbc;
130  return lbc.max();
131  } else {
132  return BndSet::MAX_OF_EMPTY;
133  }
134  }
135 
136  template<class View>
137  forceinline int
139  LubRanges<View> ub(x);
140  RangesCompl<LubRanges<View> > ubc(ub);
141  if (ubc()) {
142  return ubc.min();
143  } else {
144  return BndSet::MIN_OF_EMPTY;
145  }
146  }
147 
148  template<class View>
149  forceinline int
151  LubRanges<View> ub(x);
152  RangesCompl<LubRanges<View> > ubc(ub);
153  if (ubc()) {
154  while (ubc()) ++ubc;
155  return ubc.max();
156  } else {
157  return BndSet::MAX_OF_EMPTY;
158  }
159  }
160 
161  template<class View>
163  ComplementView<View>::cardMin(Space& home, unsigned int c) {
164  if (c < Limits::card)
165  return me_negateset(x.cardMax(home, Limits::card - c));
166  return ME_SET_NONE;
167  }
168 
169  template<class View>
171  ComplementView<View>::cardMax(Space& home, unsigned int c) {
172  if (c < Limits::card)
173  return me_negateset(x.cardMin(home, Limits::card - c));
174  return ME_SET_NONE;
175  }
176 
177  template<class View>
180  return me_negateset((x.exclude(home, c)));
181  }
182 
183  template<class View>
186  return me_negateset((x.include(home, c)));
187  }
188 
189  template<class View>
194  return me_negateset((x.includeI(home, csi)));
195  }
196 
197  template<class View>
202  return me_negateset((x.includeI(home, csi)));
203  }
204 
205  template<class View>
207  ComplementView<View>::include(Space& home, int j, int k) {
208  return me_negateset(x.exclude(home,j,k));
209  }
210 
211  template<class View>
213  ComplementView<View>::exclude(Space& home, int j, int k) {
214  return me_negateset(x.include(home,j,k));
215  }
216 
217  template<class View>
218  template<class I> ModEvent
220  return me_negateset(x.includeI(home,iter));
221  }
222 
223  template<class View>
224  template<class I> ModEvent
226  return me_negateset(x.excludeI(home,iter));
227  }
228 
229  template<class View>
230  template<class I> ModEvent
232  RangesCompl<I> c(iter);
233  return me_negateset(x.includeI(home,c));
234  }
235 
236  template<class View>
237  forceinline void
239  bool schedule) {
240  x.subscribe(home,p, pc_negateset(pc),schedule);
241  }
242 
243  template<class View>
244  forceinline void
246  x.cancel(home,p, pc_negateset(pc));
247  }
248 
249  template<class View>
250  forceinline void
252  x.subscribe(home,a);
253  }
254 
255  template<class View>
256  forceinline void
258  x.cancel(home,a);
259  }
260 
261  template<class View>
262  forceinline void
264  return View::schedule(home,p,me_negateset(me));
265  }
266  template<class View>
269  return me_negateset(View::me(med));
270  }
271 
272  template<class View>
275  return me_negateset(View::med(me));
276  }
277 
278  /*
279  * Delta information for advisors
280  *
281  */
282 
283  template<class View>
286  return me_negateset(View::modevent(d));
287  }
288 
289  template<class View>
290  forceinline int
292  return x.lubMin(d);
293  }
294 
295  template<class View>
296  forceinline int
298  return x.lubMax(d);
299  }
300 
301  template<class View>
302  forceinline bool
304  return x.lubAny(d);
305  }
306 
307  template<class View>
308  forceinline int
310  return x.glbMin(d);
311  }
312 
313  template<class View>
314  forceinline int
316  return x.glbMax(d);
317  }
318 
319  template<class View>
320  forceinline bool
322  return x.glbAny(d);
323  }
324 
325 
330  template<class View>
331  class LubRanges<ComplementView<View> > {
332  private:
333  GlbRanges<View> lb;
335  public:
337 
338  LubRanges(void) {}
343  void init(const ComplementView<View>& x);
345 
347 
348  bool operator ()(void) const;
351  void operator ++(void);
353 
355 
356  int min(void) const;
359  int max(void) const;
361  unsigned int width(void) const;
363  };
364 
365  template<class View>
368  : lb(s.base()), lbc(lb) {}
369 
370  template<class View>
371  forceinline void
373  lb.init(s.base());
374  lbc.init(lb);
375  }
376 
377  template<class View>
378  forceinline bool
379  LubRanges<ComplementView<View> >::operator ()(void) const { return lbc(); }
380 
381  template<class View>
382  forceinline void
383  LubRanges<ComplementView<View> >::operator ++(void) { return ++lbc; }
384 
385  template<class View>
386  forceinline int
387  LubRanges<ComplementView<View> >::min(void) const { return lbc.min(); }
388 
389  template<class View>
390  forceinline int
391  LubRanges<ComplementView<View> >::max(void) const { return lbc.max(); }
392 
393  template<class View>
394  forceinline unsigned int
395  LubRanges<ComplementView<View> >::width(void) const { return lbc.width(); }
396 
405  template<class View>
407  public LubRanges<View> {
408  public:
410 
411  LubRanges(void) {}
416  void init(const ComplementView<ComplementView<View> >& x);
418  };
419 
420  template<class View>
423  LubRanges(const ComplementView<ComplementView<View> >& x) :
424  LubRanges<View>(x) {}
425 
426  template<class View>
427  forceinline void
429  init(const ComplementView<ComplementView<View> >& x) {
431  }
432 
437  template<class View>
438  class GlbRanges<ComplementView<View> > {
439  private:
440  LubRanges<View> ub;
442  public:
444 
445  GlbRanges(void) {}
450  void init(const ComplementView<View> & x);
452 
454 
455  bool operator ()(void) const;
458  void operator ++(void);
460 
462 
463  int min(void) const;
466  int max(void) const;
468  unsigned int width(void) const;
470  };
471 
472  template<class View>
475  : ub(s.base()), ubc(ub) {}
476 
477  template<class View>
478  forceinline void
480  ub.init(s.base());
481  ubc.init(ub);
482  }
483 
484  template<class View>
485  forceinline bool
486  GlbRanges<ComplementView<View> >::operator ()(void) const { return ubc(); }
487 
488  template<class View>
489  forceinline void
490  GlbRanges<ComplementView<View> >::operator ++(void) { return ++ubc; }
491 
492  template<class View>
493  forceinline int
494  GlbRanges<ComplementView<View> >::min(void) const { return ubc.min(); }
495 
496  template<class View>
497  forceinline int
498  GlbRanges<ComplementView<View> >::max(void) const { return ubc.max(); }
499 
500  template<class View>
501  forceinline unsigned int
502  GlbRanges<ComplementView<View> >::width(void) const { return ubc.width(); }
503 
512  template<class View>
514  public GlbRanges<View> {
515  public:
517 
518  GlbRanges(void) {}
523  void init(const ComplementView<ComplementView<View> >& x);
525  };
526 
527  template<class View>
530  GlbRanges(const ComplementView<ComplementView<View> >& x) :
531  GlbRanges<View>(x) {}
532 
533  template<class View>
534  forceinline void
536  init(const ComplementView<ComplementView<View> >& x) {
538  }
539 
540  template<class Char, class Traits, class View>
541  std::basic_ostream<Char,Traits>&
542  operator <<(std::basic_ostream<Char,Traits>& os,
543  const ComplementView<View>& x) {
544  std::basic_ostringstream<Char,Traits> s;
545  s.copyfmt(os); s.width(0);
546  s << "(" << x.base() << ")^C";
547  return os << s.str();
548  }
549 
550 
551  template<class View>
552  forceinline bool
554  return x.base() == y.base();
555  }
556 
557  template<class View>
558  forceinline bool
560  return x.base() != y.base();
561  }
562 
563 }}
564 
565 // STATISTICS: set-var
ModEvent intersect(Space &home, int i, int j)
Update least upper bound to contain at most all elements between and including i and j.
Definition: complement.hpp:199
ModEvent intersectI(Space &home, I &iter)
Intersect least upper bound with range sequence described by i.
Definition: complement.hpp:231
Post propagator for SetVar x
Definition: set.hh:767
const Gecode::PropCond PC_SET_CGLB
Propagate when the cardinality or the greatest lower bound of a view changes.
Definition: var-type.hpp:238
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
bool operator()(void) const
Test whether iterator is still at a range or done.
bool notContains(int i) const
Test whether i is not in the least upper bound.
Definition: complement.hpp:97
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
int lubMax(void) const
Return maximum element of least upper bound.
Definition: set.hpp:87
ModEvent includeI(Space &home, I &i)
Include range sequence described by i in greatest lower bound.
Definition: complement.hpp:225
unsigned int cardMax(void) const
Return maximum cardinality.
Definition: complement.hpp:107
const Gecode::ModEvent ME_SET_CLUB
Domain operation has changed the least upper bound and the cardinality.
Definition: var-type.hpp:179
LubRanges(void)
Default constructor.
int lubMin(void) const
Return minimum of the least upper bound.
Definition: complement.hpp:113
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition: complement.hpp:268
unsigned int cardMin(void) const
Return cardinality minimum.
Definition: set.hpp:78
int lubMin(void) const
Return minimum element of least upper bound.
Definition: set.hpp:84
static ModEventDelta med(ModEvent)
Translate modification event me to modification event delta for view.
Definition: complement.hpp:274
Computation spaces.
Definition: core.hpp:1742
void init(const T &x)
Initialize with least upper bound ranges for set variable x.
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition: complement.hpp:238
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition: complement.hpp:150
bool lubAny(const Delta &d) const
Test whether arbitrary values got pruned from lub.
Definition: complement.hpp:321
static const int MIN_OF_EMPTY
Returned by empty sets when asked for their minimum element.
Definition: var-imp.hpp:112
bool operator!=(const CachedView< View > &x, const CachedView< View > &y)
Definition: cached.hpp:387
unsigned int glbSize(void) const
Return the number of elements in the greatest lower bound.
Definition: complement.hpp:75
Base-class for derived views.
Definition: view.hpp:230
Gecode toplevel namespace
Base-class for propagators.
Definition: core.hpp:1064
int glbMin(void) const
Return minimum of the greatest lower bound.
Definition: complement.hpp:138
const Gecode::ModEvent ME_SET_GLB
Domain operation has changed the greatest lower bound.
Definition: var-type.hpp:164
const Gecode::ModEvent ME_SET_LUB
Domain operation has changed the least upper bound.
Definition: var-type.hpp:156
ModEvent include(Space &home, int i, int j)
Update greatest lower bound to include all elements between and including i and j.
Definition: complement.hpp:207
int max(void) const
Return largest value of range.
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:101
unsigned int lubSize(void) const
Return number of elements in the least upper bound.
Definition: set.hpp:66
static const int MAX_OF_EMPTY
Returned by empty sets when asked for their maximum element.
Definition: var-imp.hpp:110
A complement iterator spezialized for the BndSet limits.
Definition: var-imp.hpp:293
GlbRanges(void)
Default constructor.
int min(void) const
Return smallest value of range.
Generic domain change information to be supplied to advisors.
Definition: core.hpp:204
unsigned int unknownSize(void) const
Return the number of unknown elements.
Definition: complement.hpp:87
const Gecode::PropCond PC_SET_CLUB
Propagate when the cardinality or the least upper bound of a view changes.
Definition: var-type.hpp:227
int lubMax(void) const
Return maximum of the least upper bound.
Definition: complement.hpp:125
unsigned int lubSize(void) const
Return the number of elements in the least upper bound.
Definition: complement.hpp:81
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const CachedView< View > &x)
Definition: cached.hpp:374
const Gecode::ModEvent ME_SET_CGLB
Domain operation has changed the greatest lower bound and the cardinality.
Definition: var-type.hpp:186
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition: complement.hpp:245
unsigned int cardMax(void) const
Return cardinality maximum.
Definition: set.hpp:81
const double base
Base for geometric restart sequence.
Definition: search.hh:126
int max(void) const
Return largest value of range.
const Gecode::ModEvent ME_SET_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:140
ModEvent excludeI(Space &home, I &i)
Remove range sequence described by i from least upper bound.
Definition: complement.hpp:219
ModEvent exclude(Space &home, int i, int j)
Restrict least upper bound to not contain all elements between and including i and j.
Definition: complement.hpp:213
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
Definition: complement.hpp:263
int min(void) const
Return smallest value of range.
int ModEvent
Type for modification events.
Definition: core.hpp:62
bool contains(int i) const
Test whether i is in greatest lower bound.
Definition: set.hpp:72
ComplementView(void)
Default constructor.
Definition: complement.hpp:44
int PropCond
Type for propagation conditions.
Definition: core.hpp:72
bool operator==(const CachedView< View > &x, const CachedView< View > &y)
Definition: cached.hpp:381
const SetInstr * si[]
Definition: mm-set.cpp:4341
bool contains(int i) const
Test whether i is in the greatest lower bound.
Definition: complement.hpp:93
View base(void) const
Return view from which this view is derived.
Definition: view.hpp:605
void operator++(void)
Move iterator to next range (if possible)
Gecode::IntSet d(v, 7)
Base-class for advisors.
Definition: core.hpp:1292
static PropCond pc_negateset(PropCond pc)
Negate the propagation condition pc.
Definition: complement.hpp:65
unsigned int glbSize(void) const
Return number of elements in the greatest lower bound.
Definition: set.hpp:63
int max(void) const
Return largest value of range.
int glbMin(void) const
Return minimum element of greatest lower bound.
Definition: set.hpp:90
#define forceinline
Definition: config.hpp:192
Range iterator for singleton range.
int glbMax(void) const
Return maximum of greatest lower bound.
Definition: set.hpp:93
bool operator()(void) const
Test whether iterator is still at a range or done.
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
static ModEvent me_negateset(ModEvent me)
Negate the modification event me.
Definition: complement.hpp:53
Complement set view.
Definition: view.hpp:769
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
Gecode::FloatVal c(-8, 8)
void operator++(void)
Move iterator to next range (if possible)
void init(const T &x)
Initialize with greatest lower bound ranges for set variable x.
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
int min(void) const
Return smallest value of range.
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Gecode::IntArgs i({1, 2, 3, 4})
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
unsigned int cardMin(void) const
Return minimum cardinality.
Definition: complement.hpp:101
bool notContains(int i) const
Test whether i is not in the least upper bound.
Definition: set.hpp:75
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: complement.hpp:285
bool glbAny(const Delta &d) const
Test whether arbitrary values got pruned from glb.
Definition: complement.hpp:303