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 { namespace Set {
00045
00046 template<class View>
00047 forceinline
00048 ComplementView<View>::ComplementView(void) {}
00049
00050 template<class View>
00051 forceinline
00052 ComplementView<View>::ComplementView(View& y)
00053 : DerivedView<View>(y) {}
00054
00055 template<class View>
00056 forceinline ModEvent
00057 ComplementView<View>::me_negateset(ModEvent me) {
00058 switch(me) {
00059 case ME_SET_LUB : return ME_SET_GLB;
00060 case ME_SET_GLB : return ME_SET_LUB;
00061 case ME_SET_CLUB : return ME_SET_CGLB;
00062 case ME_SET_CGLB : return ME_SET_CLUB;
00063 default: return me;
00064 }
00065 }
00066
00067 template<class View>
00068 forceinline PropCond
00069 ComplementView<View>::pc_negateset(PropCond pc) {
00070 switch(pc) {
00071 case PC_SET_CLUB : return PC_SET_CGLB;
00072 case PC_SET_CGLB : return PC_SET_CLUB;
00073 default: return pc;
00074 }
00075 }
00076
00077 template<class View>
00078 forceinline unsigned int
00079 ComplementView<View>::glbSize(void) const {
00080 return Limits::card - x.lubSize();
00081 }
00082
00083 template<class View>
00084 forceinline unsigned int
00085 ComplementView<View>::lubSize(void) const {
00086 return Limits::card - x.glbSize();
00087 }
00088
00089 template<class View>
00090 forceinline unsigned int
00091 ComplementView<View>::unknownSize(void) const {
00092 return lubSize() - glbSize();
00093 }
00094
00095 template<class View>
00096 forceinline bool
00097 ComplementView<View>::contains(int n) const { return x.notContains(n); }
00098
00099 template<class View>
00100 forceinline bool
00101 ComplementView<View>::notContains(int n) const { return x.contains(n); }
00102
00103 template<class View>
00104 forceinline unsigned int
00105 ComplementView<View>::cardMin(void) const {
00106 return Limits::card - x.cardMax();
00107 }
00108
00109 template<class View>
00110 forceinline unsigned int
00111 ComplementView<View>::cardMax(void) const {
00112 return Limits::card - x.cardMin();
00113 }
00114
00115 template<class View>
00116 forceinline int
00117 ComplementView<View>::lubMin(void) const {
00118 GlbRanges<View> lb(x);
00119 RangesCompl<GlbRanges<View> > lbc(lb);
00120 if (lbc()) {
00121 return lbc.min();
00122 } else {
00123 return BndSet::MIN_OF_EMPTY;
00124 }
00125 }
00126
00127 template<class View>
00128 forceinline int
00129 ComplementView<View>::lubMax(void) const {
00130 GlbRanges<View> lb(x);
00131 RangesCompl<GlbRanges<View> > lbc(lb);
00132 if (lbc()) {
00133 while(lbc()) ++lbc;
00134 return lbc.max();
00135 } else {
00136 return BndSet::MAX_OF_EMPTY;
00137 }
00138 }
00139
00140 template<class View>
00141 forceinline int
00142 ComplementView<View>::glbMin(void) const {
00143 LubRanges<View> ub(x);
00144 RangesCompl<LubRanges<View> > ubc(ub);
00145 if (ubc()) {
00146 return ubc.min();
00147 } else {
00148 return BndSet::MIN_OF_EMPTY;
00149 }
00150 }
00151
00152 template<class View>
00153 forceinline int
00154 ComplementView<View>::glbMax(void) const {
00155 LubRanges<View> ub(x);
00156 RangesCompl<LubRanges<View> > ubc(ub);
00157 if (ubc()) {
00158 while (ubc()) ++ubc;
00159 return ubc.max();
00160 } else {
00161 return BndSet::MAX_OF_EMPTY;
00162 }
00163 }
00164
00165 template<class View>
00166 forceinline ModEvent
00167 ComplementView<View>::cardMin(Space& home, unsigned int c) {
00168 if (c < Limits::card)
00169 return me_negateset(x.cardMax(home, Limits::card - c));
00170 return ME_SET_NONE;
00171 }
00172
00173 template<class View>
00174 forceinline ModEvent
00175 ComplementView<View>::cardMax(Space& home, unsigned int c) {
00176 if (c < Limits::card)
00177 return me_negateset(x.cardMin(home, Limits::card - c));
00178 return ME_SET_NONE;
00179 }
00180
00181 template<class View>
00182 forceinline ModEvent
00183 ComplementView<View>::include(Space& home, int c) {
00184 return me_negateset((x.exclude(home, c)));
00185 }
00186
00187 template<class View>
00188 forceinline ModEvent
00189 ComplementView<View>::exclude(Space& home, int c) {
00190 return me_negateset((x.include(home, c)));
00191 }
00192
00193 template<class View>
00194 forceinline ModEvent
00195 ComplementView<View>::intersect(Space& home, int c) {
00196 Iter::Ranges::Singleton si(c,c);
00197 RangesCompl<Iter::Ranges::Singleton> csi(si);
00198 return me_negateset((x.includeI(home, csi)));
00199 }
00200
00201 template<class View>
00202 forceinline ModEvent
00203 ComplementView<View>::intersect(Space& home, int i, int j) {
00204 Iter::Ranges::Singleton si(i,j);
00205 RangesCompl<Iter::Ranges::Singleton> csi(si);
00206 return me_negateset((x.includeI(home, csi)));
00207 }
00208
00209 template<class View>
00210 forceinline ModEvent
00211 ComplementView<View>::include(Space& home, int j, int k) {
00212 return me_negateset(x.exclude(home,j,k));
00213 }
00214
00215 template<class View>
00216 forceinline ModEvent
00217 ComplementView<View>::exclude(Space& home, int j, int k) {
00218 return me_negateset(x.include(home,j,k));
00219 }
00220
00221 template<class View>
00222 template<class I> ModEvent
00223 ComplementView<View>::excludeI(Space& home,I& iter) {
00224 return me_negateset(x.includeI(home,iter));
00225 }
00226
00227 template<class View>
00228 template<class I> ModEvent
00229 ComplementView<View>::includeI(Space& home,I& iter) {
00230 return me_negateset(x.excludeI(home,iter));
00231 }
00232
00233 template<class View>
00234 template<class I> ModEvent
00235 ComplementView<View>::intersectI(Space& home,I& iter) {
00236 RangesCompl<I> c(iter);
00237 return me_negateset(x.includeI(home,c));
00238 }
00239
00240 template<class View>
00241 forceinline void
00242 ComplementView<View>::subscribe(Space& home, Propagator& p, PropCond pc,
00243 bool schedule) {
00244 x.subscribe(home,p, pc_negateset(pc),schedule);
00245 }
00246
00247 template<class View>
00248 forceinline void
00249 ComplementView<View>::cancel(Space& home, Propagator& p, PropCond pc) {
00250 x.cancel(home,p, pc_negateset(pc));
00251 }
00252
00253 template<class View>
00254 forceinline void
00255 ComplementView<View>::subscribe(Space& home, Advisor& a) {
00256 x.subscribe(home,a);
00257 }
00258
00259 template<class View>
00260 forceinline void
00261 ComplementView<View>::cancel(Space& home, Advisor& a) {
00262 x.cancel(home,a);
00263 }
00264
00265 template<class View>
00266 forceinline void
00267 ComplementView<View>::schedule(Space& home, Propagator& p, ModEvent me) {
00268 return View::schedule(home,p,me_negateset(me));
00269 }
00270 template<class View>
00271 forceinline ModEvent
00272 ComplementView<View>::me(const ModEventDelta& med) {
00273 return me_negateset(View::me(med));
00274 }
00275
00276 template<class View>
00277 forceinline ModEventDelta
00278 ComplementView<View>::med(ModEvent me) {
00279 return me_negateset(View::med(me));
00280 }
00281
00282
00283
00284
00285
00286
00287 template<class View>
00288 forceinline ModEvent
00289 ComplementView<View>::modevent(const Delta& d) {
00290 return me_negateset(View::modevent(d));
00291 }
00292
00293 template<class View>
00294 forceinline int
00295 ComplementView<View>::glbMin(const Delta& d) const {
00296 return x.lubMin(d);
00297 }
00298
00299 template<class View>
00300 forceinline int
00301 ComplementView<View>::glbMax(const Delta& d) const {
00302 return x.lubMax(d);
00303 }
00304
00305 template<class View>
00306 forceinline bool
00307 ComplementView<View>::glbAny(const Delta& d) const {
00308 return x.lubAny(d);
00309 }
00310
00311 template<class View>
00312 forceinline int
00313 ComplementView<View>::lubMin(const Delta& d) const {
00314 return x.glbMin(d);
00315 }
00316
00317 template<class View>
00318 forceinline int
00319 ComplementView<View>::lubMax(const Delta& d) const {
00320 return x.glbMax(d);
00321 }
00322
00323 template<class View>
00324 forceinline bool
00325 ComplementView<View>::lubAny(const Delta& d) const {
00326 return x.glbAny(d);
00327 }
00328
00329
00334 template<class View>
00335 class LubRanges<ComplementView<View> > {
00336 private:
00337 GlbRanges<View> lb;
00338 RangesCompl<GlbRanges<View> > lbc;
00339 public:
00341
00342
00343 LubRanges(void) {}
00345 LubRanges(const ComplementView<View>& x);
00347 void init(const ComplementView<View>& x);
00348
00350
00351
00352 bool operator ()(void) const;
00354 void operator ++(void);
00356
00358
00359
00360 int min(void) const;
00362 int max(void) const;
00364 unsigned int width(void) const;
00366 };
00367
00368 template<class View>
00369 forceinline
00370 LubRanges<ComplementView<View> >::LubRanges(const ComplementView<View>& s)
00371 : lb(s.base()), lbc(lb) {}
00372
00373 template<class View>
00374 forceinline void
00375 LubRanges<ComplementView<View> >::init(const ComplementView<View>& s) {
00376 lb.init(s.base());
00377 lbc.init(lb);
00378 }
00379
00380 template<class View>
00381 forceinline bool
00382 LubRanges<ComplementView<View> >::operator ()(void) const { return lbc(); }
00383
00384 template<class View>
00385 forceinline void
00386 LubRanges<ComplementView<View> >::operator ++(void) { return ++lbc; }
00387
00388 template<class View>
00389 forceinline int
00390 LubRanges<ComplementView<View> >::min(void) const { return lbc.min(); }
00391
00392 template<class View>
00393 forceinline int
00394 LubRanges<ComplementView<View> >::max(void) const { return lbc.max(); }
00395
00396 template<class View>
00397 forceinline unsigned int
00398 LubRanges<ComplementView<View> >::width(void) const { return lbc.width(); }
00399
00408 template<class View>
00409 class LubRanges<ComplementView<ComplementView<View> > > :
00410 public LubRanges<View> {
00411 public:
00413
00414
00415 LubRanges(void) {}
00417 LubRanges(const ComplementView<ComplementView<View> >& x);
00419 void init(const ComplementView<ComplementView<View> >& x);
00421 };
00422
00423 template<class View>
00424 forceinline
00425 LubRanges<ComplementView<ComplementView<View> > >::
00426 LubRanges(const ComplementView<ComplementView<View> >& x) :
00427 LubRanges<View>(x) {}
00428
00429 template<class View>
00430 forceinline void
00431 LubRanges<ComplementView<ComplementView<View> > >::
00432 init(const ComplementView<ComplementView<View> >& x) {
00433 LubRanges<View>::init(x);
00434 }
00435
00440 template<class View>
00441 class GlbRanges<ComplementView<View> > {
00442 private:
00443 LubRanges<View> ub;
00444 RangesCompl<LubRanges<View> > ubc;
00445 public:
00447
00448
00449 GlbRanges(void) {}
00451 GlbRanges(const ComplementView<View> & x);
00453 void init(const ComplementView<View> & x);
00454
00456
00457
00458 bool operator ()(void) const;
00460 void operator ++(void);
00462
00464
00465
00466 int min(void) const;
00468 int max(void) const;
00470 unsigned int width(void) const;
00472 };
00473
00474 template<class View>
00475 forceinline
00476 GlbRanges<ComplementView<View> >::GlbRanges(const ComplementView<View> & s)
00477 : ub(s.base()), ubc(ub) {}
00478
00479 template<class View>
00480 forceinline void
00481 GlbRanges<ComplementView<View> >::init(const ComplementView<View> & s) {
00482 ub.init(s.base());
00483 ubc.init(ub);
00484 }
00485
00486 template<class View>
00487 forceinline bool
00488 GlbRanges<ComplementView<View> >::operator ()(void) const { return ubc(); }
00489
00490 template<class View>
00491 forceinline void
00492 GlbRanges<ComplementView<View> >::operator ++(void) { return ++ubc; }
00493
00494 template<class View>
00495 forceinline int
00496 GlbRanges<ComplementView<View> >::min(void) const { return ubc.min(); }
00497
00498 template<class View>
00499 forceinline int
00500 GlbRanges<ComplementView<View> >::max(void) const { return ubc.max(); }
00501
00502 template<class View>
00503 forceinline unsigned int
00504 GlbRanges<ComplementView<View> >::width(void) const { return ubc.width(); }
00505
00514 template<class View>
00515 class GlbRanges<ComplementView<ComplementView<View> > > :
00516 public GlbRanges<View> {
00517 public:
00519
00520
00521 GlbRanges(void) {}
00523 GlbRanges(const ComplementView<ComplementView<View> >& x);
00525 void init(const ComplementView<ComplementView<View> >& x);
00527 };
00528
00529 template<class View>
00530 forceinline
00531 GlbRanges<ComplementView<ComplementView<View> > >::
00532 GlbRanges(const ComplementView<ComplementView<View> >& x) :
00533 GlbRanges<View>(x) {}
00534
00535 template<class View>
00536 forceinline void
00537 GlbRanges<ComplementView<ComplementView<View> > >::
00538 init(const ComplementView<ComplementView<View> >& x) {
00539 GlbRanges<View>::init(x);
00540 }
00541
00542 template<class Char, class Traits, class View>
00543 std::basic_ostream<Char,Traits>&
00544 operator <<(std::basic_ostream<Char,Traits>& os,
00545 const ComplementView<View>& x) {
00546 std::basic_ostringstream<Char,Traits> s;
00547 s.copyfmt(os); s.width(0);
00548 s << "(" << x.base() << ")^C";
00549 return os << s.str();
00550 }
00551
00552 }}
00553
00554