Generated on Wed Jul 21 2021 00:00:00 for Gecode by doxygen 1.9.1
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
93  ComplementView<View>::contains(int n) const { return x.notContains(n); }
94 
95  template<class View>
96  forceinline bool
97  ComplementView<View>::notContains(int n) const { return x.contains(n); }
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
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Base-class for advisors.
Definition: core.hpp:1292
Generic domain change information to be supplied to advisors.
Definition: core.hpp:204
Base-class for derived views.
Definition: view.hpp:230
View base(void) const
Return view from which this view is derived.
Definition: view.hpp:605
int min(void) const
Return smallest value of range.
int max(void) const
Return largest value of range.
Range iterator for singleton range.
Base-class for propagators.
Definition: core.hpp:1064
static const int MAX_OF_EMPTY
Returned by empty sets when asked for their maximum element.
Definition: var-imp.hpp:110
static const int MIN_OF_EMPTY
Returned by empty sets when asked for their minimum element.
Definition: var-imp.hpp:112
Complement set view.
Definition: view.hpp:769
bool glbAny(const Delta &d) const
Test whether arbitrary values got pruned from glb.
Definition: complement.hpp:303
static ModEvent me_negateset(ModEvent me)
Negate the modification event me.
Definition: complement.hpp:53
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
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition: complement.hpp:268
bool contains(int i) const
Test whether i is in the greatest lower bound.
Definition: complement.hpp:93
unsigned int cardMax(void) const
Return maximum cardinality.
Definition: complement.hpp:107
unsigned int lubSize(void) const
Return the number of elements in the least upper bound.
Definition: complement.hpp:81
int glbMin(void) const
Return minimum of the greatest lower bound.
Definition: complement.hpp:138
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition: complement.hpp:150
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
Definition: complement.hpp:263
int lubMax(void) const
Return maximum of the least upper bound.
Definition: complement.hpp:125
bool notContains(int i) const
Test whether i is not in the least upper bound.
Definition: complement.hpp:97
int lubMin(void) const
Return minimum of the least upper bound.
Definition: complement.hpp:113
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
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition: complement.hpp:238
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
static PropCond pc_negateset(PropCond pc)
Negate the propagation condition pc.
Definition: complement.hpp:65
ModEvent intersectI(Space &home, I &iter)
Intersect least upper bound with range sequence described by i.
Definition: complement.hpp:231
ComplementView(void)
Default constructor.
Definition: complement.hpp:44
unsigned int glbSize(void) const
Return the number of elements in the greatest lower bound.
Definition: complement.hpp:75
bool lubAny(const Delta &d) const
Test whether arbitrary values got pruned from lub.
Definition: complement.hpp:321
unsigned int cardMin(void) const
Return minimum cardinality.
Definition: complement.hpp:101
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition: complement.hpp:245
ModEvent excludeI(Space &home, I &i)
Remove range sequence described by i from least upper bound.
Definition: complement.hpp:219
ModEvent includeI(Space &home, I &i)
Include range sequence described by i in greatest lower bound.
Definition: complement.hpp:225
static ModEventDelta med(ModEvent)
Translate modification event me to modification event delta for view.
Definition: complement.hpp:274
unsigned int unknownSize(void) const
Return the number of unknown elements.
Definition: complement.hpp:87
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: complement.hpp:285
bool operator()(void) const
Test whether iterator is still at a range or done.
void init(const T &x)
Initialize with greatest lower bound ranges for set variable x.
int min(void) const
Return smallest value of range.
int max(void) const
Return largest value of range.
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
void operator++(void)
Move iterator to next range (if possible)
GlbRanges(void)
Default constructor.
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
LubRanges(void)
Default constructor.
void init(const T &x)
Initialize with least upper bound ranges for set variable x.
int max(void) const
Return largest value of range.
bool operator()(void) const
Test whether iterator is still at a range or done.
void operator++(void)
Move iterator to next range (if possible)
int min(void) const
Return smallest value of range.
A complement iterator spezialized for the BndSet limits.
Definition: var-imp.hpp:293
Computation spaces.
Definition: core.hpp:1742
int PropCond
Type for propagation conditions.
Definition: core.hpp:72
int ModEvent
Type for modification events.
Definition: core.hpp:62
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:767
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
const double base
Base for geometric restart sequence.
Definition: search.hh:126
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:101
const Gecode::ModEvent ME_SET_CLUB
Domain operation has changed the least upper bound and the cardinality.
Definition: var-type.hpp:179
const Gecode::ModEvent ME_SET_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:140
const Gecode::ModEvent ME_SET_GLB
Domain operation has changed the greatest lower bound.
Definition: var-type.hpp:164
const Gecode::ModEvent ME_SET_CGLB
Domain operation has changed the greatest lower bound and the cardinality.
Definition: var-type.hpp:186
const Gecode::PropCond PC_SET_CLUB
Propagate when the cardinality or the least upper bound of a view changes.
Definition: var-type.hpp:227
bool operator==(const CachedView< View > &x, const CachedView< View > &y)
Definition: cached.hpp:381
const Gecode::ModEvent ME_SET_LUB
Domain operation has changed the least upper bound.
Definition: var-type.hpp:156
const Gecode::PropCond PC_SET_CGLB
Propagate when the cardinality or the greatest lower bound of a view changes.
Definition: var-type.hpp:238
bool operator!=(const CachedView< View > &x, const CachedView< View > &y)
Definition: cached.hpp:387
std::basic_ostream< Char, Traits > & operator<<(std::basic_ostream< Char, Traits > &os, const CachedView< View > &x)
Definition: cached.hpp:374
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)
const SetInstr * si[]
Definition: mm-set.cpp:4341
#define forceinline
Definition: config.hpp:192