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 Int { namespace Rel {
00039
00040
00041
00042
00043 template<class View>
00044 inline
00045 LexLqLe<View>::LexLqLe(Home home,
00046 ViewArray<View>& x0, ViewArray<View>& y0, bool s)
00047 : Propagator(home), x(x0), y(y0), strict(s) {
00048 x.subscribe(home, *this, PC_INT_BND);
00049 y.subscribe(home, *this, PC_INT_BND);
00050 }
00051
00052 template<class View>
00053 forceinline
00054 LexLqLe<View>::LexLqLe(Space& home, bool share, LexLqLe<View>& p)
00055 : Propagator(home,share,p), strict(p.strict) {
00056 x.update(home,share,p.x);
00057 y.update(home,share,p.y);
00058 }
00059
00060 template<class View>
00061 Actor*
00062 LexLqLe<View>::copy(Space& home, bool share) {
00063 return new (home) LexLqLe<View>(home,share,*this);
00064 }
00065
00066 template<class View>
00067 PropCost
00068 LexLqLe<View>::cost(const Space&, const ModEventDelta&) const {
00069 return PropCost::linear(PropCost::LO, x.size());
00070 }
00071
00072 template<class View>
00073 forceinline size_t
00074 LexLqLe<View>::dispose(Space& home) {
00075 assert(!home.failed());
00076 x.cancel(home,*this,PC_INT_BND);
00077 y.cancel(home,*this,PC_INT_BND);
00078 (void) Propagator::dispose(home);
00079 return sizeof(*this);
00080 }
00081
00082 template<class View>
00083 ExecStatus
00084 LexLqLe<View>::propagate(Space& home, const ModEventDelta&) {
00085
00086
00087
00088
00089 {
00090 int i = 0;
00091 int n = x.size();
00092
00093 while ((i < n) && (x[i].min() == y[i].max())) {
00094
00095 GECODE_ME_CHECK(x[i].lq(home,y[i].max()));
00096 GECODE_ME_CHECK(y[i].gq(home,x[i].min()));
00097 i++;
00098 }
00099
00100 if (i == n)
00101 return strict ? ES_FAILED : home.ES_SUBSUMED(*this);
00102
00103
00104 GECODE_ME_CHECK(x[i].lq(home,y[i].max()));
00105 GECODE_ME_CHECK(y[i].gq(home,x[i].min()));
00106
00107 if (x[i].max() < y[i].min())
00108 return home.ES_SUBSUMED(*this);
00109
00110
00111 assert(!(x[i].assigned() && y[i].assigned() &&
00112 x[i].val() == y[i].val()));
00113
00114 x.drop_fst(i); y.drop_fst(i);
00115
00116 }
00117
00118
00119
00120
00121
00122
00123 {
00124 int i = 1;
00125 int n = x.size();
00126
00127 while ((i < n) &&
00128 (x[i].min() == y[i].max()) &&
00129 (x[i].max() == y[i].min())) {
00130 assert(x[i].assigned() && y[i].assigned() &&
00131 (x[i].val() == y[i].val()));
00132 i++;
00133 }
00134
00135 if (i == n) {
00136 if (strict)
00137 goto rewrite_le;
00138 else
00139 goto rewrite_lq;
00140 }
00141
00142 if (x[i].max() < y[i].min())
00143 goto rewrite_lq;
00144
00145 if (x[i].min() > y[i].max())
00146 goto rewrite_le;
00147
00148 if (i > 1) {
00149
00150 x[i-1]=x[0]; x.drop_fst(i-1);
00151 y[i-1]=y[0]; y.drop_fst(i-1);
00152 }
00153 }
00154
00155 if (x[1].max() <= y[1].min()) {
00156
00157
00158
00159
00160
00161
00162 int i = 2;
00163 int n = x.size();
00164
00165 while ((i < n) && (x[i].max() == y[i].min()))
00166 i++;
00167
00168 if (i == n) {
00169 if (strict)
00170 return ES_FIX;
00171 else
00172 goto rewrite_lq;
00173 }
00174
00175 if (x[i].max() < y[i].min())
00176 goto rewrite_lq;
00177
00178 if (x[i].min() > y[i].max()) {
00179
00180 for (int j=i; j<n; j++) {
00181 x[j].cancel(home,*this,PC_INT_BND);
00182 y[j].cancel(home,*this,PC_INT_BND);
00183 }
00184 x.size(i); y.size(i);
00185 strict = true;
00186 }
00187
00188 return ES_FIX;
00189 }
00190
00191 if (x[1].min() >= y[1].max()) {
00192
00193
00194
00195
00196
00197
00198 int i = 2;
00199 int n = x.size();
00200
00201 while ((i < n) && (x[i].min() == y[i].max()))
00202
00203 i++;
00204
00205 if (i == n) {
00206 if (strict)
00207 goto rewrite_le;
00208 else
00209 return ES_FIX;
00210 }
00211
00212 if (x[i].min() > y[i].max())
00213 goto rewrite_le;
00214
00215 if (x[i].max() < y[i].min()) {
00216
00217 for (int j=i; j<n; j++) {
00218 x[j].cancel(home,*this,PC_INT_BND);
00219 y[j].cancel(home,*this,PC_INT_BND);
00220 }
00221 x.size(i); y.size(i);
00222 strict = false;
00223 }
00224
00225 return ES_FIX;
00226 }
00227
00228 return ES_FIX;
00229
00230 rewrite_le:
00231 GECODE_REWRITE(*this,Le<View>::post(home(*this),x[0],y[0]));
00232 rewrite_lq:
00233 GECODE_REWRITE(*this,Lq<View>::post(home(*this),x[0],y[0]));
00234 }
00235
00236 template<class View>
00237 ExecStatus
00238 LexLqLe<View>::post(Home home,
00239 ViewArray<View>& x, ViewArray<View>& y, bool strict) {
00240 if (x.size() < y.size()) {
00241 y.size(x.size()); strict=false;
00242 } else if (x.size() > y.size()) {
00243 x.size(y.size()); strict=true;
00244 }
00245 if (x.size() == 0)
00246 return strict ? ES_FAILED : ES_OK;
00247 if (x.size() == 1) {
00248 if (strict)
00249 return Le<View>::post(home,x[0],y[0]);
00250 else
00251 return Lq<View>::post(home,x[0],y[0]);
00252 }
00253 (void) new (home) LexLqLe<View>(home,x,y,strict);
00254 return ES_OK;
00255 }
00256
00257
00258
00259
00260
00261 template<class View>
00262 forceinline
00263 LexNq<View>::LexNq(Home home, ViewArray<View>& xv, ViewArray<View>& yv)
00264 : Propagator(home),
00265 x0(xv[xv.size()-2]), y0(yv[xv.size()-2]),
00266 x1(xv[xv.size()-1]), y1(yv[xv.size()-1]),
00267 x(xv), y(yv) {
00268 int n = x.size();
00269 assert(n > 1);
00270 assert(n == y.size());
00271 x.size(n-2); y.size(n-2);
00272 x0.subscribe(home,*this,PC_INT_VAL); y0.subscribe(home,*this,PC_INT_VAL);
00273 x1.subscribe(home,*this,PC_INT_VAL); y1.subscribe(home,*this,PC_INT_VAL);
00274 }
00275
00276 template<class View>
00277 PropCost
00278 LexNq<View>::cost(const Space&, const ModEventDelta&) const {
00279 return PropCost::binary(PropCost::HI);
00280 }
00281
00282 template<class View>
00283 forceinline
00284 LexNq<View>::LexNq(Space& home, bool share, LexNq<View>& p)
00285 : Propagator(home,share,p) {
00286 x0.update(home,share,p.x0); y0.update(home,share,p.y0);
00287 x1.update(home,share,p.x1); y1.update(home,share,p.y1);
00288 x.update(home,share,p.x); y.update(home,share,p.y);
00289 }
00290
00291 template<class View>
00292 Actor*
00293 LexNq<View>::copy(Space& home, bool share) {
00294
00295
00296
00297
00298
00299
00300
00301
00302
00303
00304
00305
00306
00307
00308
00309
00310
00311
00312
00313
00314
00315
00316
00317 return new (home) LexNq<View>(home,share,*this);
00318 }
00319
00320 template<class View>
00321 inline ExecStatus
00322 LexNq<View>::post(Home home, ViewArray<View>& x, ViewArray<View>& y) {
00323 if (x.size() != y.size())
00324 return ES_OK;
00325 int n = x.size();
00326 if (n > 0) {
00327
00328 for (int i=n; i--; )
00329 switch (rtest_eq_bnd(x[i],y[i])) {
00330 case RT_TRUE:
00331
00332 n--; x[i]=x[n]; y[i]=y[n];
00333 break;
00334 case RT_FALSE:
00335 return ES_OK;
00336 case RT_MAYBE:
00337 if (same(x[i],y[i])) {
00338
00339 n--; x[i]=x[n]; y[i]=y[n];
00340 }
00341 break;
00342 default:
00343 GECODE_NEVER;
00344 }
00345 x.size(n); y.size(n);
00346 }
00347 if (n == 0)
00348 return ES_FAILED;
00349 if (n == 1)
00350 return Nq<View>::post(home,x[0],y[0]);
00351 (void) new (home) LexNq(home,x,y);
00352 return ES_OK;
00353 }
00354
00355 template<class View>
00356 forceinline size_t
00357 LexNq<View>::dispose(Space& home) {
00358 x0.cancel(home,*this,PC_INT_VAL); y0.cancel(home,*this,PC_INT_VAL);
00359 x1.cancel(home,*this,PC_INT_VAL); y1.cancel(home,*this,PC_INT_VAL);
00360 (void) Propagator::dispose(home);
00361 return sizeof(*this);
00362 }
00363
00364 template<class View>
00365 forceinline ExecStatus
00366 LexNq<View>::resubscribe(Space& home,
00367 RelTest rt, View& x0, View& y0, View x1, View y1) {
00368 if (rt == RT_TRUE) {
00369 assert(x0.assigned() && y0.assigned());
00370 assert(x0.val() == y0.val());
00371 int n = x.size();
00372 for (int i=n; i--; )
00373 switch (rtest_eq_bnd(x[i],y[i])) {
00374 case RT_TRUE:
00375
00376 n--; x[i]=x[n]; y[i]=y[n];
00377 break;
00378 case RT_FALSE:
00379 return home.ES_SUBSUMED(*this);
00380 case RT_MAYBE:
00381
00382 x0=x[i]; y0=y[i];
00383 n--; x[i]=x[n]; y[i]=y[n];
00384 x.size(n); y.size(n);
00385 x0.subscribe(home,*this,PC_INT_VAL,false);
00386 y0.subscribe(home,*this,PC_INT_VAL,false);
00387 return ES_FIX;
00388 default:
00389 GECODE_NEVER;
00390 }
00391
00392 GECODE_REWRITE(*this,Nq<View>::post(home,x1,y1));
00393 }
00394 return ES_FIX;
00395 }
00396
00397 template<class View>
00398 ExecStatus
00399 LexNq<View>::propagate(Space& home, const ModEventDelta&) {
00400 RelTest rt0 = rtest_eq_bnd(x0,y0);
00401 if (rt0 == RT_FALSE)
00402 return home.ES_SUBSUMED(*this);
00403 RelTest rt1 = rtest_eq_bnd(x1,y1);
00404 if (rt1 == RT_FALSE)
00405 return home.ES_SUBSUMED(*this);
00406 GECODE_ES_CHECK(resubscribe(home,rt0,x0,y0,x1,y1));
00407 GECODE_ES_CHECK(resubscribe(home,rt1,x1,y1,x0,y0));
00408 return ES_FIX;
00409 }
00410
00411
00412 }}}
00413
00414