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 void set(int i, bool j) {
00061 if (j)
00062 b.set(i);
00063 else
00064 b.clear(i);
00065 }
00066
00068 class CSIter {
00069 public:
00071 CharacteristicSets* cs;
00073 unsigned int i;
00075 int xoff;
00077 int yoff;
00079 void operator++ (void) {
00080 i++;
00081 while (i<cs->xsize && !cs->b.get(xoff+2*i+yoff))
00082 i++;
00083 }
00085 CSIter(void) {}
00087 CSIter(CharacteristicSets& cs0, int xoff0, int yoff0)
00088 : cs(&cs0), i(static_cast<unsigned int>(-1)),
00089 xoff(xoff0), yoff(yoff0) {
00090 ++(*this);
00091 }
00093 bool operator() (void) const { return i<cs->xsize; }
00095 int val(void) const { return cs->ub[i]; }
00096 };
00097
00098 public:
00100 template<class View0, class View1>
00101 CharacteristicSets(Region& re, View0 x, View1 y);
00102
00104 bool xmin(int i) const { return b.get(2*i); }
00106 bool xmax(int i) const { return b.get(2*i+1); }
00108 bool ymin(int i) const { return b.get(2*xsize+2*i); }
00110 bool ymax(int i) const { return b.get(2*xsize+2*i+1); }
00111
00113 void xmin(int i, bool j) { set(2*i,j); }
00115 void xmax(int i, bool j) { set(2*i+1,j); }
00117 void ymin(int i, bool j) { set(2*xsize+2*i,j); }
00119 void ymax(int i, bool j) { set(2*xsize+2*i+1,j); }
00120
00122 ModEvent xlq(int i, bool j) {
00123 if (!j) {
00124 if (xmin(i)) return ME_SET_FAILED;
00125 if (xmax(i)) {
00126 xmax(i,false);
00127 xum=true;
00128 }
00129 }
00130 return ME_SET_NONE;
00131 }
00133 ModEvent xgq(int i, bool j) {
00134 if (j) {
00135 if (!xmax(i)) return ME_SET_FAILED;
00136 if (!xmin(i)) {
00137 xmin(i,true);
00138 xlm=true;
00139 }
00140 }
00141 return ME_SET_NONE;
00142 }
00144 ModEvent ylq(int i, bool j) {
00145 if (!j) {
00146 if (ymin(i)) return ME_SET_FAILED;
00147 if (ymax(i)) {
00148 ymax(i,false);
00149 yum=true;
00150 }
00151 }
00152 return ME_SET_NONE;
00153 }
00155 ModEvent ygq(int i, bool j) {
00156 if (j) {
00157 if (!ymax(i)) return ME_SET_FAILED;
00158 if (!ymin(i)) {
00159 ymin(i,true);
00160 ylm=true;
00161 }
00162 }
00163 return ME_SET_NONE;
00164 }
00165
00167 int size(void) const { return xsize; }
00168
00170 template<class View0, class View1>
00171 ExecStatus prune(Space& home, View0 x, View1 y) {
00172 if (xlm) {
00173 CSIter i(*this,0,0);
00174 Iter::Values::ToRanges<CSIter> ir(i);
00175 GECODE_ME_CHECK(x.includeI(home,ir));
00176 }
00177 if (xum) {
00178 CSIter i(*this,0,1);
00179 Iter::Values::ToRanges<CSIter> ir(i);
00180 GECODE_ME_CHECK(x.intersectI(home,ir));
00181 }
00182 if (ylm) {
00183 CSIter i(*this,2*xsize,0);
00184 Iter::Values::ToRanges<CSIter> ir(i);
00185 GECODE_ME_CHECK(y.includeI(home,ir));
00186 }
00187 if (yum) {
00188 CSIter i(*this,2*xsize,1);
00189 Iter::Values::ToRanges<CSIter> ir(i);
00190 GECODE_ME_CHECK(y.intersectI(home,ir));
00191 }
00192 return ES_OK;
00193 }
00194
00195 };
00196
00197 template<class View0, class View1>
00198 CharacteristicSets::CharacteristicSets(Region& re,View0 x, View1 y)
00199 : xlm(false), xum(false), ylm(false), yum(false) {
00200 LubRanges<View0> xlub(x);
00201 LubRanges<View1> ylub(y);
00202 Iter::Ranges::Union<LubRanges<View0>,LubRanges<View1> > xylub(xlub,ylub);
00203 Iter::Ranges::Cache xylubc(re,xylub);
00204 xsize = Iter::Ranges::size(xylubc);
00205 b.init(re,4*xsize);
00206 ub = re.alloc<int>(xsize);
00207 xylubc.reset();
00208 Iter::Ranges::ToValues<Iter::Ranges::Cache> xylubv(xylubc);
00209 LubRanges<View0> xur(x);
00210 GlbRanges<View0> xlr(x);
00211 LubRanges<View1> yur(y);
00212 GlbRanges<View1> ylr(y);
00213 Iter::Ranges::ToValues<LubRanges<View0> > xuv(xur);
00214 Iter::Ranges::ToValues<GlbRanges<View0> > xlv(xlr);
00215 Iter::Ranges::ToValues<LubRanges<View1> > yuv(yur);
00216 Iter::Ranges::ToValues<GlbRanges<View1> > ylv(ylr);
00217 for (int i=0; xylubv(); ++xylubv, ++i) {
00218 ub[i] = xylubv.val();
00219 if (xlv() && xylubv.val()==xlv.val()) {
00220 b.set(2*i);
00221 ++xlv;
00222 }
00223 if (xuv() && xylubv.val()==xuv.val()) {
00224 b.set(2*i+1);
00225 ++xuv;
00226 }
00227 if (ylv() && xylubv.val()==ylv.val()) {
00228 b.set(2*xsize+2*i);
00229 ++ylv;
00230 }
00231 if (yuv() && xylubv.val()==yuv.val()) {
00232 b.set(2*xsize+2*i+1);
00233 ++yuv;
00234 }
00235 }
00236 }
00237
00238 template<class View0, class View1, bool strict>
00239 forceinline
00240 Lq<View0,View1,strict>::Lq(Home home, View0 x, View1 y)
00241 : MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y) {}
00242
00243 template<class View0, class View1, bool strict>
00244 forceinline
00245 Lq<View0,View1,strict>::Lq(Space& home, bool share, Lq& p)
00246 : MixBinaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,share,p) {}
00247
00248 template<class View0, class View1, bool strict>
00249 ExecStatus
00250 Lq<View0,View1,strict>::post(Home home, View0 x, View1 y) {
00251 if (strict)
00252 GECODE_ME_CHECK(y.cardMin(home,1));
00253 (void) new (home) Lq(home,x,y);
00254 return ES_OK;
00255 }
00256
00257 template<class View0, class View1, bool strict>
00258 Actor*
00259 Lq<View0,View1,strict>::copy(Space& home, bool share) {
00260 return new (home) Lq(home,share,*this);
00261 }
00262
00263 template<class View0, class View1, bool strict>
00264 ExecStatus
00265 Lq<View0,View1,strict>::propagate(Space& home, const ModEventDelta&) {
00266 if ( (!strict) && x1.cardMax()==0) {
00267 GECODE_ME_CHECK(x0.cardMax(home,0));
00268 }
00269
00270 if (x0.cardMax()==0) {
00271 return home.ES_SUBSUMED(*this);
00272 }
00273
00274 if (x0.glbMin() < x1.lubMin())
00275 return ES_FAILED;
00276 if (x1.glbMin() < x0.lubMin())
00277 return home.ES_SUBSUMED(*this);
00278
00279 bool assigned = x0.assigned() && x1.assigned();
00280
00281 Region re(home);
00282 CharacteristicSets cs(re,x0,x1);
00283
00284
00285
00286
00287
00288 int i=0;
00289 int firsti=0;
00290 int n=cs.size();
00291 while ((i<n) && cs.xmin(i) == cs.ymax(i)) {
00292
00293 GECODE_ME_CHECK(cs.xlq(i,cs.ymax(i)));
00294 GECODE_ME_CHECK(cs.ygq(i,cs.xmin(i)));
00295 i++;
00296 }
00297
00298 if (i == n) {
00299 if (strict) {
00300 return ES_FAILED;
00301 } else {
00302 GECODE_ES_CHECK(cs.prune(home,x0,x1));
00303 return home.ES_SUBSUMED(*this);
00304 }
00305 }
00306
00307
00308 GECODE_ME_CHECK(cs.xlq(i,cs.ymax(i)));
00309 GECODE_ME_CHECK(cs.ygq(i,cs.xmin(i)));
00310
00311 if (cs.xmax(i) < cs.ymin(i)) {
00312 GECODE_ES_CHECK(cs.prune(home,x0,x1));
00313 return home.ES_SUBSUMED(*this);
00314 }
00315
00316 firsti=i;
00317
00318
00319
00320
00321
00322
00323 i++;
00324
00325 while ((i < n) &&
00326 (cs.xmin(i) == cs.ymax(i)) &&
00327 (cs.xmax(i) == cs.ymin(i))) {
00328 i++;
00329 }
00330
00331 if (i == n) {
00332 if (strict)
00333 goto rewrite_le;
00334 else
00335 goto rewrite_lq;
00336 }
00337
00338 if (cs.xmax(i) < cs.ymin(i))
00339 goto rewrite_lq;
00340
00341 if (cs.xmin(i) > cs.ymax(i))
00342 goto rewrite_le;
00343
00344 if (cs.xmax(i) <= cs.ymin(i)) {
00345
00346
00347
00348
00349
00350
00351 i++;
00352
00353 while ((i < n) && (cs.xmax(i) == cs.ymin(i))) {
00354 i++;
00355 }
00356
00357 if (i == n) {
00358 if (strict) {
00359 GECODE_ES_CHECK(cs.prune(home,x0,x1));
00360 return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00361 } else {
00362 goto rewrite_lq;
00363 }
00364 }
00365
00366 if (cs.xmax(i) < cs.ymin(i))
00367 goto rewrite_lq;
00368
00369 GECODE_ES_CHECK(cs.prune(home,x0,x1));
00370 return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00371 }
00372
00373 if (cs.xmin(i) >= cs.ymax(i)) {
00374
00375
00376
00377
00378
00379
00380 i++;
00381
00382 while ((i < n) && (cs.xmin(i) == cs.ymax(i))) {
00383
00384 i++;
00385 }
00386
00387 if (i == n) {
00388 if (strict) {
00389 goto rewrite_le;
00390 } else {
00391 GECODE_ES_CHECK(cs.prune(home,x0,x1));
00392 return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00393 }
00394 }
00395
00396 if (cs.xmin(i) > cs.ymax(i))
00397 goto rewrite_le;
00398
00399 GECODE_ES_CHECK(cs.prune(home,x0,x1));
00400 return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00401 }
00402
00403 GECODE_ES_CHECK(cs.prune(home,x0,x1));
00404 return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00405
00406 rewrite_le:
00407 GECODE_ME_CHECK(cs.xlq(firsti,false));
00408 GECODE_ME_CHECK(cs.ygq(firsti,true));
00409 GECODE_ES_CHECK(cs.prune(home,x0,x1));
00410 return home.ES_SUBSUMED(*this);
00411 rewrite_lq:
00412 GECODE_ES_CHECK(cs.prune(home,x0,x1));
00413 return assigned ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00414 }
00415
00416 }}}
00417
00418