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