00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042 #include <sstream>
00043
00044 namespace Gecode {
00045
00046 namespace Set {
00047
00048 template<class View>
00049 forceinline
00050 ComplementView<View>::ComplementView(void) {}
00051
00052 template<class View>
00053 forceinline
00054 ComplementView<View>::ComplementView(View& s0)
00055 : DerivedViewBase<View>(s0) {}
00056
00057 template<class View>
00058 forceinline ModEvent
00059 ComplementView<View>::me_negateset(ModEvent me) {
00060 switch(me) {
00061 case ME_SET_LUB : return ME_SET_GLB;
00062 case ME_SET_GLB : return ME_SET_LUB;
00063 case ME_SET_CLUB : return ME_SET_CGLB;
00064 case ME_SET_CGLB : return ME_SET_CLUB;
00065 default: return me;
00066 }
00067 }
00068
00069 template<class View>
00070 forceinline PropCond
00071 ComplementView<View>::pc_negateset(PropCond pc) {
00072 switch(pc) {
00073 case PC_SET_CLUB : return PC_SET_CGLB;
00074 case PC_SET_CGLB : return PC_SET_CLUB;
00075 default: return pc;
00076 }
00077 }
00078
00079 template<class View>
00080 forceinline bool
00081 ComplementView<View>::assigned(void) const { return view.assigned(); }
00082
00083 template<class View>
00084 forceinline unsigned int
00085 ComplementView<View>::glbSize(void) const {
00086 return Limits::card - view.lubSize();
00087 }
00088
00089 template<class View>
00090 forceinline unsigned int
00091 ComplementView<View>::lubSize(void) const {
00092 return Limits::card - view.glbSize();
00093 }
00094
00095 template<class View>
00096 forceinline unsigned int
00097 ComplementView<View>::unknownSize(void) const {
00098 return lubSize() - glbSize();
00099 }
00100
00101 template<class View>
00102 forceinline bool
00103 ComplementView<View>::contains(int n) const { return view.notContains(n); }
00104
00105 template<class View>
00106 forceinline bool
00107 ComplementView<View>::notContains(int n) const { return view.contains(n); }
00108
00109 template<class View>
00110 forceinline unsigned int
00111 ComplementView<View>::cardMin() const {
00112 return Limits::card - view.cardMax();
00113 }
00114
00115 template<class View>
00116 forceinline unsigned int
00117 ComplementView<View>::cardMax() const {
00118 return Limits::card - view.cardMin();
00119 }
00120
00121 template<class View>
00122 forceinline int
00123 ComplementView<View>::lubMin() const {
00124 GlbRanges<View> lb(view);
00125 RangesCompl<GlbRanges<View> > lbc(lb);
00126 if (lbc()) {
00127 return lbc.min();
00128 } else {
00129 return BndSet::MIN_OF_EMPTY;
00130 }
00131 }
00132
00133 template<class View>
00134 forceinline int
00135 ComplementView<View>::lubMax() const {
00136 GlbRanges<View> lb(view);
00137 RangesCompl<GlbRanges<View> > lbc(lb);
00138 if (lbc()) {
00139 while(lbc()) ++lbc;
00140 return lbc.max();
00141 } else {
00142 return BndSet::MAX_OF_EMPTY;
00143 }
00144 }
00145
00146 template<class View>
00147 forceinline int
00148 ComplementView<View>::glbMin() const {
00149 LubRanges<View> ub(view);
00150 RangesCompl<LubRanges<View> > ubc(ub);
00151 if (ubc()) {
00152 return ubc.min();
00153 } else {
00154 return BndSet::MIN_OF_EMPTY;
00155 }
00156 }
00157
00158 template<class View>
00159 forceinline int
00160 ComplementView<View>::glbMax() const {
00161 LubRanges<View> ub(view);
00162 RangesCompl<LubRanges<View> > ubc(ub);
00163 if (ubc()) {
00164 while(ubc()) ++ubc;
00165 return ubc.max();
00166 } else {
00167 return BndSet::MAX_OF_EMPTY;
00168 }
00169 }
00170
00171 template<class View>
00172 forceinline ModEvent
00173 ComplementView<View>::cardMin(Space& home, unsigned int c) {
00174 if (c < Limits::card)
00175 return me_negateset(view.cardMax(home, Limits::card - c));
00176 return ME_SET_NONE;
00177 }
00178
00179 template<class View>
00180 forceinline ModEvent
00181 ComplementView<View>::cardMax(Space& home, unsigned int c) {
00182 if (c < Limits::card)
00183 return me_negateset(view.cardMin(home, Limits::card - c));
00184 return ME_SET_NONE;
00185 }
00186
00187 template<class View>
00188 forceinline ModEvent
00189 ComplementView<View>::include(Space& home, int c) {
00190 return me_negateset((view.exclude(home, c)));
00191 }
00192
00193 template<class View>
00194 forceinline ModEvent
00195 ComplementView<View>::exclude(Space& home, int c) {
00196 return me_negateset((view.include(home, c)));
00197 }
00198
00199 template<class View>
00200 forceinline ModEvent
00201 ComplementView<View>::intersect(Space& home, int c) {
00202 Iter::Ranges::Singleton si(c,c);
00203 RangesCompl<Iter::Ranges::Singleton> csi(si);
00204 return me_negateset((view.includeI(home, csi)));
00205 }
00206
00207 template<class View>
00208 forceinline ModEvent
00209 ComplementView<View>::intersect(Space& home, int i, int j) {
00210 Iter::Ranges::Singleton si(i,j);
00211 RangesCompl<Iter::Ranges::Singleton> csi(si);
00212 return me_negateset((view.includeI(home, csi)));
00213 }
00214
00215 template<class View>
00216 forceinline ModEvent
00217 ComplementView<View>::include(Space& home, int j, int k) {
00218 return me_negateset(view.exclude(home,j,k));
00219 }
00220
00221 template<class View>
00222 forceinline ModEvent
00223 ComplementView<View>::exclude(Space& home, int j, int k) {
00224 return me_negateset(view.include(home,j,k));
00225 }
00226
00227 template<class View>
00228 template<class I> ModEvent
00229 ComplementView<View>::excludeI(Space& home,I& iter) {
00230 return me_negateset(view.includeI(home,iter));
00231 }
00232
00233 template<class View>
00234 template<class I> ModEvent
00235 ComplementView<View>::includeI(Space& home,I& iter) {
00236 return me_negateset(view.excludeI(home,iter));
00237 }
00238
00239 template<class View>
00240 template<class I> ModEvent
00241 ComplementView<View>::intersectI(Space& home,I& iter) {
00242 RangesCompl<I> c(iter);
00243 return me_negateset(view.includeI(home,c));
00244 }
00245
00246 template<class View>
00247 forceinline void
00248 ComplementView<View>::subscribe(Space& home, Propagator& p, PropCond pc,
00249 bool process) {
00250 view.subscribe(home,p, pc_negateset(pc),process);
00251 }
00252
00253 template<class View>
00254 forceinline void
00255 ComplementView<View>::cancel(Space& home, Propagator& p, PropCond pc) {
00256 view.cancel(home,p, pc_negateset(pc));
00257 }
00258
00259 template<class View>
00260 forceinline void
00261 ComplementView<View>::subscribe(Space& home, Advisor& a) {
00262 view.subscribe(home,a);
00263 }
00264
00265 template<class View>
00266 forceinline void
00267 ComplementView<View>::cancel(Space& home, Advisor& a) {
00268 view.cancel(home,a);
00269 }
00270
00271 template<class View>
00272 forceinline void
00273 ComplementView<View>::schedule(Space& home, Propagator& p, ModEvent me) {
00274 return View::schedule(home,p,me_negateset(me));
00275 }
00276 template<class View>
00277 forceinline ModEvent
00278 ComplementView<View>::me(const ModEventDelta& med) {
00279 return me_negateset(View::me(med));
00280 }
00281
00282 template<class View>
00283 forceinline ModEventDelta
00284 ComplementView<View>::med(ModEvent me) {
00285 return me_negateset(View::med(me));
00286 }
00287
00288 template<class View>
00289 forceinline void
00290 ComplementView<View>::update(Space& home, bool share,
00291 ComplementView& y) {
00292 view.update(home,share,y.view);
00293 }
00294
00295
00296
00297
00298
00299
00300
00301 template<class View>
00302 forceinline ModEvent
00303 ComplementView<View>::modevent(const Delta& d) {
00304 return me_negateset(View::modevent(d));
00305 }
00306
00307 template<class View>
00308 forceinline int
00309 ComplementView<View>::glbMin(const Delta& d) const {
00310 return view.lubMin(d);
00311 }
00312
00313 template<class View>
00314 forceinline int
00315 ComplementView<View>::glbMax(const Delta& d) const {
00316 return view.lubMax(d);
00317 }
00318
00319 template<class View>
00320 forceinline bool
00321 ComplementView<View>::glbAny(const Delta& d) const {
00322 return view.lubAny(d);
00323 }
00324
00325 template<class View>
00326 forceinline int
00327 ComplementView<View>::lubMin(const Delta& d) const {
00328 return view.glbMin(d);
00329 }
00330
00331 template<class View>
00332 forceinline int
00333 ComplementView<View>::lubMax(const Delta& d) const {
00334 return view.glbMax(d);
00335 }
00336
00337 template<class View>
00338 forceinline bool
00339 ComplementView<View>::lubAny(const Delta& d) const {
00340 return view.glbAny(d);
00341 }
00342
00343
00348 template<class View>
00349 class LubRanges<ComplementView<View> > {
00350 private:
00351 GlbRanges<View> lb;
00352 RangesCompl<GlbRanges<View> > lbc;
00353 public:
00355
00356
00357 LubRanges(void) {}
00359 LubRanges(const ComplementView<View>& x);
00361 void init(const ComplementView<View>& x);
00362
00364
00365
00366 bool operator ()(void) const;
00368 void operator ++(void);
00370
00372
00373
00374 int min(void) const;
00376 int max(void) const;
00378 unsigned int width(void) const;
00380 };
00381
00382 template<class View>
00383 forceinline
00384 LubRanges<ComplementView<View> >::LubRanges(const ComplementView<View>& s)
00385 : lb(s.base()), lbc(lb) {}
00386
00387 template<class View>
00388 forceinline void
00389 LubRanges<ComplementView<View> >::init(const ComplementView<View>& s) {
00390 lb.init(s.base());
00391 lbc.init(lb);
00392 }
00393
00394 template<class View>
00395 forceinline bool
00396 LubRanges<ComplementView<View> >::operator ()(void) const { return lbc(); }
00397
00398 template<class View>
00399 forceinline void
00400 LubRanges<ComplementView<View> >::operator ++(void) { return ++lbc; }
00401
00402 template<class View>
00403 forceinline int
00404 LubRanges<ComplementView<View> >::min(void) const { return lbc.min(); }
00405
00406 template<class View>
00407 forceinline int
00408 LubRanges<ComplementView<View> >::max(void) const { return lbc.max(); }
00409
00410 template<class View>
00411 forceinline unsigned int
00412 LubRanges<ComplementView<View> >::width(void) const { return lbc.width(); }
00413
00422 template<class View>
00423 class LubRanges<ComplementView<ComplementView<View> > > :
00424 public LubRanges<View> {
00425 public:
00427
00428
00429 LubRanges(void) {}
00431 LubRanges(const ComplementView<ComplementView<View> >& x);
00433 void init(const ComplementView<ComplementView<View> >& x);
00435 };
00436
00437 template<class View>
00438 forceinline
00439 LubRanges<ComplementView<ComplementView<View> > >::
00440 LubRanges(const ComplementView<ComplementView<View> >& x) :
00441 LubRanges<View>(x) {}
00442
00443 template<class View>
00444 forceinline void
00445 LubRanges<ComplementView<ComplementView<View> > >::
00446 init(const ComplementView<ComplementView<View> >& x) {
00447 LubRanges<View>::init(x);
00448 }
00449
00454 template<class View>
00455 class GlbRanges<ComplementView<View> > {
00456 private:
00457 LubRanges<View> ub;
00458 RangesCompl<LubRanges<View> > ubc;
00459 public:
00461
00462
00463 GlbRanges(void) {}
00465 GlbRanges(const ComplementView<View> & x);
00467 void init(const ComplementView<View> & x);
00468
00470
00471
00472 bool operator ()(void) const;
00474 void operator ++(void);
00476
00478
00479
00480 int min(void) const;
00482 int max(void) const;
00484 unsigned int width(void) const;
00486 };
00487
00488 template<class View>
00489 forceinline
00490 GlbRanges<ComplementView<View> >::GlbRanges(const ComplementView<View> & s)
00491 : ub(s.base()), ubc(ub) {}
00492
00493 template<class View>
00494 forceinline void
00495 GlbRanges<ComplementView<View> >::init(const ComplementView<View> & s) {
00496 ub.init(s.base());
00497 ubc.init(ub);
00498 }
00499
00500 template<class View>
00501 forceinline bool
00502 GlbRanges<ComplementView<View> >::operator ()(void) const { return ubc(); }
00503
00504 template<class View>
00505 forceinline void
00506 GlbRanges<ComplementView<View> >::operator ++(void) { return ++ubc; }
00507
00508 template<class View>
00509 forceinline int
00510 GlbRanges<ComplementView<View> >::min(void) const { return ubc.min(); }
00511
00512 template<class View>
00513 forceinline int
00514 GlbRanges<ComplementView<View> >::max(void) const { return ubc.max(); }
00515
00516 template<class View>
00517 forceinline unsigned int
00518 GlbRanges<ComplementView<View> >::width(void) const { return ubc.width(); }
00519
00528 template<class View>
00529 class GlbRanges<ComplementView<ComplementView<View> > > :
00530 public GlbRanges<View> {
00531 public:
00533
00534
00535 GlbRanges(void) {}
00537 GlbRanges(const ComplementView<ComplementView<View> >& x);
00539 void init(const ComplementView<ComplementView<View> >& x);
00541 };
00542
00543 template<class View>
00544 forceinline
00545 GlbRanges<ComplementView<ComplementView<View> > >::
00546 GlbRanges(const ComplementView<ComplementView<View> >& x) :
00547 GlbRanges<View>(x) {}
00548
00549 template<class View>
00550 forceinline void
00551 GlbRanges<ComplementView<ComplementView<View> > >::
00552 init(const ComplementView<ComplementView<View> >& x) {
00553 GlbRanges<View>::init(x);
00554 }
00555
00556 template<class Char, class Traits, class View>
00557 std::basic_ostream<Char,Traits>&
00558 operator <<(std::basic_ostream<Char,Traits>& os,
00559 const ComplementView<View>& x) {
00560 std::basic_ostringstream<Char,Traits> s;
00561 s.copyfmt(os); s.width(0);
00562 s << "(" << x.base() << ")^C";
00563 return os << s.str();
00564 }
00565
00566 }
00567
00568
00569
00570
00571
00572
00573 template<class View>
00574 forceinline bool
00575 same(const Set::ComplementView<View>& x,
00576 const Set::ComplementView<View>& y) {
00577 return same(x.base(),y.base());
00578 }
00579 template<class View>
00580 forceinline bool
00581 before(const Set::ComplementView<View>& x,
00582 const Set::ComplementView<View>& y) {
00583 return before(x.base(),y.base());
00584 }
00585 template<class View>
00586 forceinline bool
00587 same(const Set::ComplementView<Set::ComplementView<View> >& x,
00588 const Set::ComplementView<Set::ComplementView<View> >& y) {
00589 return same(x,y);
00590 }
00591 template<class View>
00592 forceinline bool
00593 before(const Set::ComplementView<Set::ComplementView<View> >& x,
00594 const Set::ComplementView<Set::ComplementView<View> >& y) {
00595 return before(x,y);
00596 }
00597
00598 }
00599
00600