Generated on Sat Feb 7 2015 02:01:30 for Gecode by doxygen 1.8.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  * Last modified:
14  * $Date: 2011-05-02 00:24:42 +0200 (Mon, 02 May 2011) $ by $Author: tack $
15  * $Revision: 11973 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #include <sstream>
43 
44 namespace Gecode { namespace Set {
45 
46  template<class View>
49 
50  template<class View>
53  : DerivedView<View>(y) {}
54 
55  template<class View>
58  switch(me) {
59  case ME_SET_LUB : return ME_SET_GLB;
60  case ME_SET_GLB : return ME_SET_LUB;
61  case ME_SET_CLUB : return ME_SET_CGLB;
62  case ME_SET_CGLB : return ME_SET_CLUB;
63  default: return me;
64  }
65  }
66 
67  template<class View>
70  switch(pc) {
71  case PC_SET_CLUB : return PC_SET_CGLB;
72  case PC_SET_CGLB : return PC_SET_CLUB;
73  default: return pc;
74  }
75  }
76 
77  template<class View>
78  forceinline unsigned int
80  return Limits::card - x.lubSize();
81  }
82 
83  template<class View>
84  forceinline unsigned int
86  return Limits::card - x.glbSize();
87  }
88 
89  template<class View>
90  forceinline unsigned int
92  return lubSize() - glbSize();
93  }
94 
95  template<class View>
96  forceinline bool
97  ComplementView<View>::contains(int n) const { return x.notContains(n); }
98 
99  template<class View>
100  forceinline bool
101  ComplementView<View>::notContains(int n) const { return x.contains(n); }
102 
103  template<class View>
104  forceinline unsigned int
106  return Limits::card - x.cardMax();
107  }
108 
109  template<class View>
110  forceinline unsigned int
112  return Limits::card - x.cardMin();
113  }
114 
115  template<class View>
116  forceinline int
118  GlbRanges<View> lb(x);
119  RangesCompl<GlbRanges<View> > lbc(lb);
120  if (lbc()) {
121  return lbc.min();
122  } else {
123  return BndSet::MIN_OF_EMPTY;
124  }
125  }
126 
127  template<class View>
128  forceinline int
130  GlbRanges<View> lb(x);
131  RangesCompl<GlbRanges<View> > lbc(lb);
132  if (lbc()) {
133  while(lbc()) ++lbc;
134  return lbc.max();
135  } else {
136  return BndSet::MAX_OF_EMPTY;
137  }
138  }
139 
140  template<class View>
141  forceinline int
143  LubRanges<View> ub(x);
144  RangesCompl<LubRanges<View> > ubc(ub);
145  if (ubc()) {
146  return ubc.min();
147  } else {
148  return BndSet::MIN_OF_EMPTY;
149  }
150  }
151 
152  template<class View>
153  forceinline int
155  LubRanges<View> ub(x);
156  RangesCompl<LubRanges<View> > ubc(ub);
157  if (ubc()) {
158  while (ubc()) ++ubc;
159  return ubc.max();
160  } else {
161  return BndSet::MAX_OF_EMPTY;
162  }
163  }
164 
165  template<class View>
167  ComplementView<View>::cardMin(Space& home, unsigned int c) {
168  if (c < Limits::card)
169  return me_negateset(x.cardMax(home, Limits::card - c));
170  return ME_SET_NONE;
171  }
172 
173  template<class View>
175  ComplementView<View>::cardMax(Space& home, unsigned int c) {
176  if (c < Limits::card)
177  return me_negateset(x.cardMin(home, Limits::card - c));
178  return ME_SET_NONE;
179  }
180 
181  template<class View>
184  return me_negateset((x.exclude(home, c)));
185  }
186 
187  template<class View>
190  return me_negateset((x.include(home, c)));
191  }
192 
193  template<class View>
198  return me_negateset((x.includeI(home, csi)));
199  }
200 
201  template<class View>
206  return me_negateset((x.includeI(home, csi)));
207  }
208 
209  template<class View>
211  ComplementView<View>::include(Space& home, int j, int k) {
212  return me_negateset(x.exclude(home,j,k));
213  }
214 
215  template<class View>
217  ComplementView<View>::exclude(Space& home, int j, int k) {
218  return me_negateset(x.include(home,j,k));
219  }
220 
221  template<class View>
222  template<class I> ModEvent
224  return me_negateset(x.includeI(home,iter));
225  }
226 
227  template<class View>
228  template<class I> ModEvent
230  return me_negateset(x.excludeI(home,iter));
231  }
232 
233  template<class View>
234  template<class I> ModEvent
236  RangesCompl<I> c(iter);
237  return me_negateset(x.includeI(home,c));
238  }
239 
240  template<class View>
241  forceinline void
243  bool schedule) {
244  x.subscribe(home,p, pc_negateset(pc),schedule);
245  }
246 
247  template<class View>
248  forceinline void
250  x.cancel(home,p, pc_negateset(pc));
251  }
252 
253  template<class View>
254  forceinline void
256  x.subscribe(home,a);
257  }
258 
259  template<class View>
260  forceinline void
262  x.cancel(home,a);
263  }
264 
265  template<class View>
266  forceinline void
268  return View::schedule(home,p,me_negateset(me));
269  }
270  template<class View>
273  return me_negateset(View::me(med));
274  }
275 
276  template<class View>
279  return me_negateset(View::med(me));
280  }
281 
282  /*
283  * Delta information for advisors
284  *
285  */
286 
287  template<class View>
290  return me_negateset(View::modevent(d));
291  }
292 
293  template<class View>
294  forceinline int
296  return x.lubMin(d);
297  }
298 
299  template<class View>
300  forceinline int
302  return x.lubMax(d);
303  }
304 
305  template<class View>
306  forceinline bool
308  return x.lubAny(d);
309  }
310 
311  template<class View>
312  forceinline int
314  return x.glbMin(d);
315  }
316 
317  template<class View>
318  forceinline int
320  return x.glbMax(d);
321  }
322 
323  template<class View>
324  forceinline bool
326  return x.glbAny(d);
327  }
328 
329 
334  template<class View>
335  class LubRanges<ComplementView<View> > {
336  private:
337  GlbRanges<View> lb;
339  public:
341 
342  LubRanges(void) {}
347  void init(const ComplementView<View>& x);
349 
351 
352  bool operator ()(void) const;
355  void operator ++(void);
357 
359 
360  int min(void) const;
363  int max(void) const;
365  unsigned int width(void) const;
367  };
368 
369  template<class View>
372  : lb(s.base()), lbc(lb) {}
373 
374  template<class View>
375  forceinline void
377  lb.init(s.base());
378  lbc.init(lb);
379  }
380 
381  template<class View>
382  forceinline bool
383  LubRanges<ComplementView<View> >::operator ()(void) const { return lbc(); }
384 
385  template<class View>
386  forceinline void
387  LubRanges<ComplementView<View> >::operator ++(void) { return ++lbc; }
388 
389  template<class View>
390  forceinline int
391  LubRanges<ComplementView<View> >::min(void) const { return lbc.min(); }
392 
393  template<class View>
394  forceinline int
395  LubRanges<ComplementView<View> >::max(void) const { return lbc.max(); }
396 
397  template<class View>
398  forceinline unsigned int
399  LubRanges<ComplementView<View> >::width(void) const { return lbc.width(); }
400 
409  template<class View>
411  public LubRanges<View> {
412  public:
414 
415  LubRanges(void) {}
420  void init(const ComplementView<ComplementView<View> >& x);
422  };
423 
424  template<class View>
428  LubRanges<View>(x) {}
429 
430  template<class View>
431  forceinline void
435  }
436 
441  template<class View>
442  class GlbRanges<ComplementView<View> > {
443  private:
444  LubRanges<View> ub;
446  public:
448 
449  GlbRanges(void) {}
454  void init(const ComplementView<View> & x);
456 
458 
459  bool operator ()(void) const;
462  void operator ++(void);
464 
466 
467  int min(void) const;
470  int max(void) const;
472  unsigned int width(void) const;
474  };
475 
476  template<class View>
479  : ub(s.base()), ubc(ub) {}
480 
481  template<class View>
482  forceinline void
484  ub.init(s.base());
485  ubc.init(ub);
486  }
487 
488  template<class View>
489  forceinline bool
490  GlbRanges<ComplementView<View> >::operator ()(void) const { return ubc(); }
491 
492  template<class View>
493  forceinline void
494  GlbRanges<ComplementView<View> >::operator ++(void) { return ++ubc; }
495 
496  template<class View>
497  forceinline int
498  GlbRanges<ComplementView<View> >::min(void) const { return ubc.min(); }
499 
500  template<class View>
501  forceinline int
502  GlbRanges<ComplementView<View> >::max(void) const { return ubc.max(); }
503 
504  template<class View>
505  forceinline unsigned int
506  GlbRanges<ComplementView<View> >::width(void) const { return ubc.width(); }
507 
516  template<class View>
518  public GlbRanges<View> {
519  public:
521 
522  GlbRanges(void) {}
527  void init(const ComplementView<ComplementView<View> >& x);
529  };
530 
531  template<class View>
535  GlbRanges<View>(x) {}
536 
537  template<class View>
538  forceinline void
542  }
543 
544  template<class Char, class Traits, class View>
545  std::basic_ostream<Char,Traits>&
546  operator <<(std::basic_ostream<Char,Traits>& os,
547  const ComplementView<View>& x) {
548  std::basic_ostringstream<Char,Traits> s;
549  s.copyfmt(os); s.width(0);
550  s << "(" << x.base() << ")^C";
551  return os << s.str();
552  }
553 
554 }}
555 
556 // STATISTICS: set-var
const Gecode::PropCond PC_SET_CLUB
Propagate when the cardinality or the least upper bound of a view changes.
Definition: var-type.hpp:227
static ModEvent modevent(const Delta &d)
Return modification event.
Definition: complement.hpp:289
const SetInstr * si[]
Definition: mm-set.cpp:4340
ComplementView(void)
Default constructor.
Definition: complement.hpp:48
const Gecode::ModEvent ME_SET_LUB
Domain operation has changed the least upper bound.
Definition: var-type.hpp:156
Range iterator for singleton range.
bool operator()(void) const
Test whether iterator is still at a range or done.
int max(void) const
Return largest value of range.
int max(void) const
Return largest value of range.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
int ModEvent
Type for modification events.
Definition: core.hpp:146
Base-class for propagators.
Definition: core.hpp:755
Base-class for advisors.
Definition: core.hpp:926
ModEvent intersectI(Space &home, I &iter)
Intersect least upper bound with range sequence described by i.
Definition: complement.hpp:235
int min(void) const
Return smallest value of range.
static const int MIN_OF_EMPTY
Returned by empty sets when asked for their minimum element.
Definition: var-imp.hpp:116
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:103
Computation spaces.
Definition: core.hpp:1362
Base-class for derived views.
Definition: view.hpp:208
int min(void) const
Return smallest value of range.
Gecode::IntSet d(v, 7)
int min(void) const
Return smallest value of range.
static const int MAX_OF_EMPTY
Returned by empty sets when asked for their maximum element.
Definition: var-imp.hpp:114
Gecode::FloatVal c(-8, 8)
int max(void) const
Return largest value of range.
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
unsigned int unknownSize(void) const
Return the number of unknown elements.
Definition: complement.hpp:91
unsigned int cardMax(void) const
Return maximum cardinality.
Definition: complement.hpp:111
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition: complement.hpp:249
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:203
static ModEventDelta med(ModEvent)
Translate modification event me to modification event delta for view.
Definition: complement.hpp:278
static ModEvent me_negateset(ModEvent me)
Negate the modification event me.
Definition: complement.hpp:57
View base(void) const
Return view from which this view is derived.
Definition: view.hpp:526
bool operator()(void) const
Test whether iterator is still at a range or done.
const Gecode::ModEvent ME_SET_CGLB
Domain operation has changed the greatest lower bound and the cardinality.
Definition: var-type.hpp:186
int PropCond
Type for propagation conditions.
Definition: core.hpp:156
A complement iterator spezialized for the BndSet limits.
Definition: var-imp.hpp:296
void operator++(void)
Move iterator to next range (if possible)
int glbMin(void) const
Return minimum of the greatest lower bound.
Definition: complement.hpp:142
void operator++(void)
Move iterator to next range (if possible)
unsigned int glbSize(void) const
Return the number of elements in the greatest lower bound.
Definition: complement.hpp:79
bool contains(int i) const
Test whether i is in the greatest lower bound.
Definition: complement.hpp:97
const Gecode::ModEvent ME_SET_GLB
Domain operation has changed the greatest lower bound.
Definition: var-type.hpp:164
ModEvent includeI(Space &home, I &i)
Include range sequence described by i in greatest lower bound.
Definition: complement.hpp:229
const Gecode::ModEvent ME_SET_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:140
unsigned int lubSize(void) const
Return the number of elements in the least upper bound.
Definition: complement.hpp:85
unsigned int cardMin(void) const
Return minimum cardinality.
Definition: complement.hpp:105
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
int lubMax(void) const
Return maximum of the least upper bound.
Definition: complement.hpp:129
ModEvent excludeI(Space &home, I &i)
Remove range sequence described by i from least upper bound.
Definition: complement.hpp:223
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition: complement.hpp:242
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Generic domain change information to be supplied to advisors.
Definition: core.hpp:275
bool glbAny(const Delta &d) const
Test whether arbitrary values got pruned from glb.
Definition: complement.hpp:307
const Gecode::PropCond PC_SET_CGLB
Propagate when the cardinality or the greatest lower bound of a view changes.
Definition: var-type.hpp:238
const Gecode::ModEvent ME_SET_CLUB
Domain operation has changed the least upper bound and the cardinality.
Definition: var-type.hpp:179
GlbRanges(void)
Default constructor.
#define forceinline
Definition: config.hpp:132
void init(const T &x)
Initialize with least upper bound ranges for set variable x.
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition: complement.hpp:154
Complement set view.
Definition: view.hpp:754
Gecode toplevel namespace
bool lubAny(const Delta &d) const
Test whether arbitrary values got pruned from lub.
Definition: complement.hpp:325
LubRanges(void)
Default constructor.
static void schedule(Space &home, Propagator &p, ModEvent me)
Schedule propagator p with modification event me.
Definition: complement.hpp:267
static PropCond pc_negateset(PropCond pc)
Negate the propagation condition pc.
Definition: complement.hpp:69
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
int lubMin(void) const
Return minimum of the least upper bound.
Definition: complement.hpp:117
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:217
void init(const T &x)
Initialize with greatest lower bound ranges for set variable x.
static ModEvent me(const ModEventDelta &med)
Return modification event for view type in med.
Definition: complement.hpp:272
bool notContains(int i) const
Test whether i is not in the least upper bound.
Definition: complement.hpp:101
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:211