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 namespace Gecode { namespace Set { namespace Rel {
00035
00039 class CharacteristicSets {
00040 protected:
00042 unsigned int xsize;
00044 Support::BitSetBase b;
00046 int* ub;
00048 bool xlm;
00050 bool xum;
00052 bool ylm;
00054 bool yum;
00056 bool get(unsigned int i) const;
00058 void set(unsigned int i, bool j);
00059
00061 class CSIter {
00062 public:
00064 CharacteristicSets* cs;
00066 unsigned int i;
00068 unsigned int xoff;
00070 unsigned int yoff;
00072 void operator++ (void);
00074 CSIter(void);
00076 CSIter(CharacteristicSets& cs0, unsigned int xoff0, unsigned int yoff0);
00078 bool operator() (void) const;
00080 int val(void) const;
00081 };
00082
00083 public:
00085 template<class View0, class View1>
00086 CharacteristicSets(Region& re, View0 x, View1 y);
00087
00089 bool xmin(unsigned int i) const;
00091 bool xmax(unsigned int i) const;
00093 bool ymin(unsigned int i) const;
00095 bool ymax(unsigned int i) const;
00096
00098 void xmin(unsigned int i, bool j);
00100 void xmax(unsigned int i, bool j);
00102 void ymin(unsigned int i, bool j);
00104 void ymax(unsigned int i, bool j);
00105
00107 ModEvent xlq(unsigned int i, bool j);
00109 ModEvent xgq(unsigned int i, bool j);
00111 ModEvent ylq(unsigned int i, bool j);
00113 ModEvent ygq(unsigned int i, bool j);
00114
00116 unsigned int size(void) const;
00117
00119 template<class View0, class View1>
00120 ExecStatus prune(Space& home, View0 x, View1 y);
00121
00122 };
00123
00124
00125 forceinline bool
00126 CharacteristicSets::get(unsigned int i) const {
00127 return b.get(i);
00128 }
00129 forceinline void
00130 CharacteristicSets::set(unsigned int i, bool j) {
00131 if (j)
00132 b.set(i);
00133 else
00134 b.clear(i);
00135 }
00136 forceinline unsigned int
00137 CharacteristicSets::size(void) const {
00138 return xsize;
00139 }
00140
00141 forceinline
00142 CharacteristicSets::CSIter::CSIter(void) {}
00143 forceinline
00144 CharacteristicSets::CSIter::CSIter(CharacteristicSets& cs0,
00145 unsigned int xoff0, unsigned int yoff0)
00146 : cs(&cs0), i(0), xoff(xoff0), yoff(yoff0) {
00147 while ((i < cs->xsize) && !cs->get(xoff+2*i+yoff))
00148 i++;
00149 }
00150 forceinline void
00151 CharacteristicSets::CSIter::operator++ (void) {
00152 i++;
00153 while ((i < cs->xsize) && !cs->get(xoff+2*i+yoff))
00154 i++;
00155 }
00156 forceinline bool
00157 CharacteristicSets::CSIter::operator() (void) const {
00158 return i<cs->xsize;
00159 }
00160 forceinline int
00161 CharacteristicSets::CSIter::val(void) const {
00162 return cs->ub[i];
00163 }
00164
00165
00166 forceinline bool
00167 CharacteristicSets::xmin(unsigned int i) const {
00168 return get(2*i);
00169 }
00170 forceinline bool
00171 CharacteristicSets::xmax(unsigned int i) const {
00172 return get(2*i+1);
00173 }
00174 forceinline bool
00175 CharacteristicSets::ymin(unsigned int i) const {
00176 return get(2*xsize+2*i);
00177 }
00178 forceinline bool
00179 CharacteristicSets::ymax(unsigned int i) const {
00180 return get(2*xsize+2*i+1);
00181 }
00182
00183 forceinline void
00184 CharacteristicSets::xmin(unsigned int i, bool j) {
00185 set(2*i,j);
00186 }
00187 forceinline void
00188 CharacteristicSets::xmax(unsigned int i, bool j) {
00189 set(2*i+1,j);
00190 }
00191 forceinline void
00192 CharacteristicSets::ymin(unsigned int i, bool j) {
00193 set(2*xsize+2*i,j);
00194 }
00195 forceinline void
00196 CharacteristicSets::ymax(unsigned int i, bool j) {
00197 set(2*xsize+2*i+1,j);
00198 }
00199
00200 forceinline ModEvent
00201 CharacteristicSets::xlq(unsigned int i, bool j) {
00202 if (!j) {
00203 if (xmin(i)) return ME_SET_FAILED;
00204 if (xmax(i)) {
00205 xmax(i,false);
00206 xum=true;
00207 }
00208 }
00209 return ME_SET_NONE;
00210 }
00211 forceinline ModEvent
00212 CharacteristicSets::xgq(unsigned int i, bool j) {
00213 if (j) {
00214 if (!xmax(i)) return ME_SET_FAILED;
00215 if (!xmin(i)) {
00216 xmin(i,true);
00217 xlm=true;
00218 }
00219 }
00220 return ME_SET_NONE;
00221 }
00222 forceinline ModEvent
00223 CharacteristicSets::ylq(unsigned int i, bool j) {
00224 if (!j) {
00225 if (ymin(i)) return ME_SET_FAILED;
00226 if (ymax(i)) {
00227 ymax(i,false);
00228 yum=true;
00229 }
00230 }
00231 return ME_SET_NONE;
00232 }
00233 forceinline ModEvent
00234 CharacteristicSets::ygq(unsigned int i, bool j) {
00235 if (j) {
00236 if (!ymax(i)) return ME_SET_FAILED;
00237 if (!ymin(i)) {
00238 ymin(i,true);
00239 ylm=true;
00240 }
00241 }
00242 return ME_SET_NONE;
00243 }
00244
00245 template<class View0, class View1>
00246 forceinline ExecStatus
00247 CharacteristicSets::prune(Space& home, View0 x, View1 y) {
00248 if (xlm) {
00249 CSIter i(*this,0,0);
00250 Iter::Values::ToRanges<CSIter> ir(i);
00251 GECODE_ME_CHECK(x.includeI(home,ir));
00252 }
00253 if (xum) {
00254 CSIter i(*this,0,1);
00255 Iter::Values::ToRanges<CSIter> ir(i);
00256 GECODE_ME_CHECK(x.intersectI(home,ir));
00257 }
00258 if (ylm) {
00259 CSIter i(*this,2*xsize,0);
00260 Iter::Values::ToRanges<CSIter> ir(i);
00261 GECODE_ME_CHECK(y.includeI(home,ir));
00262 }
00263 if (yum) {
00264 CSIter i(*this,2*xsize,1);
00265 Iter::Values::ToRanges<CSIter> ir(i);
00266 GECODE_ME_CHECK(y.intersectI(home,ir));
00267 }
00268 return ES_OK;
00269 }
00270
00271 template<class View0, class View1>
00272 forceinline
00273 CharacteristicSets::CharacteristicSets(Region& re,View0 x, View1 y)
00274 : xlm(false), xum(false), ylm(false), yum(false) {
00275 LubRanges<View0> xlub(x);
00276 LubRanges<View1> ylub(y);
00277 Iter::Ranges::Union<LubRanges<View0>,LubRanges<View1> > xylub(xlub,ylub);
00278 Iter::Ranges::Cache xylubc(re,xylub);
00279 xsize = Iter::Ranges::size(xylubc);
00280 b.init(re,4*xsize);
00281 ub = re.alloc<int>(xsize);
00282 xylubc.reset();
00283 Iter::Ranges::ToValues<Iter::Ranges::Cache> xylubv(xylubc);
00284 LubRanges<View0> xur(x);
00285 GlbRanges<View0> xlr(x);
00286 LubRanges<View1> yur(y);
00287 GlbRanges<View1> ylr(y);
00288 Iter::Ranges::ToValues<LubRanges<View0> > xuv(xur);
00289 Iter::Ranges::ToValues<GlbRanges<View0> > xlv(xlr);
00290 Iter::Ranges::ToValues<LubRanges<View1> > yuv(yur);
00291 Iter::Ranges::ToValues<GlbRanges<View1> > ylv(ylr);
00292 for (unsigned int i=0; xylubv(); ++xylubv, ++i) {
00293 ub[i] = xylubv.val();
00294 if (xlv() && xylubv.val()==xlv.val()) {
00295 b.set(2*i);
00296 ++xlv;
00297 }
00298 if (xuv() && xylubv.val()==xuv.val()) {
00299 b.set(2*i+1);
00300 ++xuv;
00301 }
00302 if (ylv() && xylubv.val()==ylv.val()) {
00303 b.set(2*xsize+2*i);
00304 ++ylv;
00305 }
00306 if (yuv() && xylubv.val()==yuv.val()) {
00307 b.set(2*xsize+2*i+1);
00308 ++yuv;
00309 }
00310 }
00311 }
00312
00313 template<class View0, class View1, bool strict>
00314 forceinline
00315 Lq<View0,View1,strict>::Lq(Home home, View0 x, View1 y)
00316 : MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y) {}
00317
00318 template<class View0, class View1, bool strict>
00319 forceinline
00320 Lq<View0,View1,strict>::Lq(Space& home, Lq& p)
00321 : MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,p) {}
00322
00323 template<class View0, class View1, bool strict>
00324 ExecStatus
00325 Lq<View0,View1,strict>::post(Home home, View0 x, View1 y) {
00326 if (strict)
00327 GECODE_ME_CHECK(y.cardMin(home,1));
00328 if (same(x,y))
00329 return strict ? ES_FAILED : ES_OK;
00330 (void) new (home) Lq(home,x,y);
00331 return ES_OK;
00332 }
00333
00334 template<class View0, class View1, bool strict>
00335 Actor*
00336 Lq<View0,View1,strict>::copy(Space& home) {
00337 return new (home) Lq(home,*this);
00338 }
00339
00340 template<class View0, class View1, bool strict>
00341 ExecStatus
00342 Lq<View0,View1,strict>::propagate(Space& home, const ModEventDelta&) {
00343 if ( (!strict) && x1.cardMax()==0) {
00344 GECODE_ME_CHECK(x0.cardMax(home,0));
00345 }
00346
00347 if (x0.cardMax()==0) {
00348 return home.ES_SUBSUMED(*this);
00349 }
00350
00351 if (x0.glbMin() < x1.lubMin())
00352 return ES_FAILED;
00353 if (x1.glbMin() < x0.lubMin())
00354 return home.ES_SUBSUMED(*this);
00355
00356 bool assigned = x0.assigned() && x1.assigned();
00357
00358 Region re;
00359 CharacteristicSets cs(re,x0,x1);
00360
00361
00362
00363
00364
00365 unsigned int i=0;
00366 unsigned int firsti=0;
00367 unsigned int n=cs.size();
00368 while ((i<n) && (cs.xmin(i) == cs.ymax(i))) {
00369
00370 GECODE_ME_CHECK(cs.xlq(i,cs.ymax(i)));
00371 GECODE_ME_CHECK(cs.ygq(i,cs.xmin(i)));
00372 i++;
00373 }
00374
00375 if (i == n) {
00376 if (strict) {
00377 return ES_FAILED;
00378 } else {
00379 GECODE_ES_CHECK(cs.prune(home,x0,x1));
00380 return home.ES_SUBSUMED(*this);
00381 }
00382 }
00383
00384
00385 GECODE_ME_CHECK(cs.xlq(i,cs.ymax(i)));
00386 GECODE_ME_CHECK(cs.ygq(i,cs.xmin(i)));
00387
00388 if (cs.xmax(i) < cs.ymin(i)) {
00389 GECODE_ES_CHECK(cs.prune(home,x0,x1));
00390 return home.ES_SUBSUMED(*this);
00391 }
00392
00393 firsti=i;
00394
00395
00396
00397
00398
00399
00400 i++;
00401
00402 while ((i < n) &&
00403 (cs.xmin(i) == cs.ymax(i)) &&
00404 (cs.xmax(i) == cs.ymin(i))) {
00405 i++;
00406 }
00407
00408 if (i == n) {
00409 if (strict)
00410 goto rewrite_le;
00411 else
00412 goto rewrite_lq;
00413 }
00414
00415 if (cs.xmax(i) < cs.ymin(i))
00416 goto rewrite_lq;
00417
00418 if (cs.xmin(i) > cs.ymax(i))
00419 goto rewrite_le;
00420
00421 if (cs.xmax(i) <= cs.ymin(i)) {
00422
00423
00424
00425
00426
00427
00428 i++;
00429
00430 while ((i < n) && (cs.xmax(i) == cs.ymin(i))) {
00431 i++;
00432 }
00433
00434 if (i == n) {
00435 if (strict) {
00436 GECODE_ES_CHECK(cs.prune(home,x0,x1));
00437 return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00438 } else {
00439 goto rewrite_lq;
00440 }
00441 }
00442
00443 if (cs.xmax(i) < cs.ymin(i))
00444 goto rewrite_lq;
00445
00446 GECODE_ES_CHECK(cs.prune(home,x0,x1));
00447 return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00448 }
00449
00450 if (cs.xmin(i) >= cs.ymax(i)) {
00451
00452
00453
00454
00455
00456
00457 i++;
00458
00459 while ((i < n) && (cs.xmin(i) == cs.ymax(i))) {
00460
00461 i++;
00462 }
00463
00464 if (i == n) {
00465 if (strict) {
00466 goto rewrite_le;
00467 } else {
00468 GECODE_ES_CHECK(cs.prune(home,x0,x1));
00469 return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00470 }
00471 }
00472
00473 if (cs.xmin(i) > cs.ymax(i))
00474 goto rewrite_le;
00475
00476 GECODE_ES_CHECK(cs.prune(home,x0,x1));
00477 return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00478 }
00479
00480 GECODE_ES_CHECK(cs.prune(home,x0,x1));
00481 return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00482
00483 rewrite_le:
00484 GECODE_ME_CHECK(cs.xlq(firsti,false));
00485 GECODE_ME_CHECK(cs.ygq(firsti,true));
00486 GECODE_ES_CHECK(cs.prune(home,x0,x1));
00487 return home.ES_SUBSUMED(*this);
00488 rewrite_lq:
00489 GECODE_ES_CHECK(cs.prune(home,x0,x1));
00490 return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00491 }
00492
00493 }}}
00494
00495