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 namespace Gecode { namespace Int { namespace Rel {
00041
00042
00043
00044
00045
00046
00047 template<class View>
00048 forceinline
00049 Lq<View>::Lq(Home home, View x0, View x1)
00050 : BinaryPropagator<View,PC_INT_BND>(home,x0,x1) {}
00051
00052 template<class View>
00053 ExecStatus
00054 Lq<View>::post(Home home, View x0, View x1) {
00055 GECODE_ME_CHECK(x0.lq(home,x1.max()));
00056 GECODE_ME_CHECK(x1.gq(home,x0.min()));
00057 if (!same(x0,x1) && (x0.max() > x1.min()))
00058 (void) new (home) Lq<View>(home,x0,x1);
00059 return ES_OK;
00060 }
00061
00062 template<class View>
00063 forceinline
00064 Lq<View>::Lq(Space& home, bool share, Lq<View>& p)
00065 : BinaryPropagator<View,PC_INT_BND>(home,share,p) {}
00066
00067 template<class View>
00068 Actor*
00069 Lq<View>::copy(Space& home, bool share) {
00070 return new (home) Lq<View>(home,share,*this);
00071 }
00072
00073 template<class View>
00074 ExecStatus
00075 Lq<View>::propagate(Space& home, const ModEventDelta&) {
00076 GECODE_ME_CHECK(x0.lq(home,x1.max()));
00077 GECODE_ME_CHECK(x1.gq(home,x0.min()));
00078 return (x0.max() <= x1.min()) ? home.ES_SUBSUMED(*this) : ES_FIX;
00079 }
00080
00081
00082
00083
00084
00085
00086
00087
00088 template<class View>
00089 forceinline
00090 Le<View>::Le(Home home, View x0, View x1)
00091 : BinaryPropagator<View,PC_INT_BND>(home,x0,x1) {}
00092
00093 template<class View>
00094 ExecStatus
00095 Le<View>::post(Home home, View x0, View x1) {
00096 if (same(x0,x1))
00097 return ES_FAILED;
00098 GECODE_ME_CHECK(x0.le(home,x1.max()));
00099 GECODE_ME_CHECK(x1.gr(home,x0.min()));
00100 if (x0.max() >= x1.min())
00101 (void) new (home) Le<View>(home,x0,x1);
00102 return ES_OK;
00103 }
00104
00105 template<class View>
00106 forceinline
00107 Le<View>::Le(Space& home, bool share, Le<View>& p)
00108 : BinaryPropagator<View,PC_INT_BND>(home,share,p) {}
00109
00110 template<class View>
00111 Actor*
00112 Le<View>::copy(Space& home, bool share) {
00113 return new (home) Le<View>(home,share,*this);
00114 }
00115
00116 template<class View>
00117 ExecStatus
00118 Le<View>::propagate(Space& home, const ModEventDelta&) {
00119 GECODE_ME_CHECK(x0.le(home,x1.max()));
00120 GECODE_ME_CHECK(x1.gr(home,x0.min()));
00121 return (x0.max() < x1.min()) ? home.ES_SUBSUMED(*this) : ES_FIX;
00122 }
00123
00124
00125
00126
00127
00128
00129
00130
00131 template<class View, int o>
00132 forceinline
00133 NaryLqLe<View,o>::Index::Index(Space& home, Propagator& p,
00134 Council<Index>& c, int i0)
00135 : Advisor(home,p,c), i(i0) {}
00136
00137 template<class View, int o>
00138 forceinline
00139 NaryLqLe<View,o>::Index::Index(Space& home, bool share, Index& a)
00140 : Advisor(home,share,a), i(a.i) {}
00141
00142
00143
00144 template<class View, int o>
00145 forceinline
00146 NaryLqLe<View,o>::Pos::Pos(int p0, Pos* n)
00147 : FreeList(n), p(p0) {}
00148
00149 template<class View, int o>
00150 forceinline typename NaryLqLe<View,o>::Pos*
00151 NaryLqLe<View,o>::Pos::next(void) const {
00152 return static_cast<Pos*>(FreeList::next());
00153 }
00154
00155 template<class View, int o>
00156 forceinline void
00157 NaryLqLe<View,o>::Pos::operator delete(void*) {}
00158
00159 template<class View, int o>
00160 forceinline void
00161 NaryLqLe<View,o>::Pos::operator delete(void*, Space&) {
00162 GECODE_NEVER;
00163 }
00164
00165 template<class View, int o>
00166 forceinline void*
00167 NaryLqLe<View,o>::Pos::operator new(size_t, Space& home) {
00168 return home.fl_alloc<sizeof(Pos)>();
00169 }
00170
00171 template<class View, int o>
00172 forceinline void
00173 NaryLqLe<View,o>::Pos::dispose(Space& home) {
00174 home.fl_dispose<sizeof(Pos)>(this,this);
00175 }
00176
00177
00178 template<class View, int o>
00179 forceinline bool
00180 NaryLqLe<View,o>::empty(void) const {
00181 return pos == NULL;
00182 }
00183 template<class View, int o>
00184 forceinline void
00185 NaryLqLe<View,o>::push(Space& home, int p) {
00186
00187 if ((pos != NULL) && (pos->p == p))
00188 return;
00189 pos = new (home) Pos(p,pos);
00190 }
00191 template<class View, int o>
00192 forceinline int
00193 NaryLqLe<View,o>::pop(Space& home) {
00194 Pos* t = pos;
00195 int p = t->p;
00196 pos = pos->next();
00197 t->dispose(home);
00198 return p;
00199 }
00200
00201 template<class View, int o>
00202 forceinline
00203 NaryLqLe<View,o>::NaryLqLe(Home home, ViewArray<View>& x)
00204 : NaryPropagator<View,PC_INT_NONE>(home,x),
00205 c(home), pos(NULL), run(false), n_subsumed(0) {
00206 for (int i=x.size(); i--; )
00207 x[i].subscribe(home, *new (home) Index(home,*this,c,i));
00208 }
00209
00210 template<class View, int o>
00211 ExecStatus
00212 NaryLqLe<View,o>::post(Home home, ViewArray<View>& x) {
00213 assert((o == 0) || (o == 1));
00214
00215 if (x.same(home)) {
00216 if (o == 1)
00217 return ES_FAILED;
00218
00219
00220
00221
00222 int n = x.size();
00223 for (int i=0; i<n; i++)
00224 for (int j=n-1; j>i; j--)
00225 if (same(x[i],x[j])) {
00226 if (i+1 != j) {
00227
00228 ViewArray<View> y(home,j-i);
00229 for (int k=j-i; k--; )
00230 y[k] = x[i+1+k];
00231 GECODE_ES_CHECK(NaryEqBnd<View>::post(home,y));
00232 }
00233 for (int k=0; k<n-1-j-1+1; k++)
00234 x[i+1+k]=x[j+1+k];
00235 n -= j-i;
00236 }
00237 x.size(n);
00238 }
00239
00240
00241 for (int i=1; i<x.size(); i++)
00242 GECODE_ME_CHECK(x[i].gq(home,x[i-1].min()+o));
00243 for (int i=x.size()-1; i--;)
00244 GECODE_ME_CHECK(x[i].lq(home,x[i+1].max()-o));
00245
00246 {
00247
00248 {
00249 int i=0;
00250 while ((i+1 < x.size()) && (x[i].max()+o <= x[i+1].min()))
00251 i++;
00252 x.drop_fst(i);
00253 }
00254
00255 {
00256 int i=x.size()-1;
00257 while ((i > 0) && (x[i-1].max()+o <= x[i].min()))
00258 i--;
00259 x.drop_lst(i);
00260 }
00261
00262 if (x.size() > 1) {
00263 int j=1;
00264 for (int i=1; i+1<x.size(); i++)
00265 if ((x[j-1].max()+o > x[i].min()) ||
00266 (x[i].max()+o > x[i+1].min()))
00267 x[j++]=x[i];
00268 x[j++]=x[x.size()-1];
00269 x.size(j);
00270 }
00271 }
00272 if (x.size() == 2) {
00273 if (o == 0)
00274 return Lq<View>::post(home,x[0],x[1]);
00275 else
00276 return Le<View>::post(home,x[0],x[1]);
00277 } else if (x.size() >= 2) {
00278 (void) new (home) NaryLqLe<View,o>(home,x);
00279 }
00280 return ES_OK;
00281 }
00282
00283 template<class View, int o>
00284 forceinline
00285 NaryLqLe<View,o>::NaryLqLe(Space& home, bool share, NaryLqLe<View,o>& p)
00286 : NaryPropagator<View,PC_INT_NONE>(home,share,p),
00287 pos(NULL), run(false), n_subsumed(p.n_subsumed) {
00288 assert(p.pos == NULL);
00289 c.update(home, share, p.c);
00290 }
00291
00292 template<class View, int o>
00293 Actor*
00294 NaryLqLe<View,o>::copy(Space& home, bool share) {
00295 if (n_subsumed > n_threshold) {
00296 Region r(home);
00297
00298 Support::BitSet<Region> a(r,static_cast<unsigned int>(x.size()));
00299 for (Advisors<Index> as(c); as(); ++as)
00300 a.set(static_cast<unsigned int>(as.advisor().i));
00301
00302 int* m = r.alloc<int>(x.size());
00303 int j=0;
00304 for (int i=0; i<x.size(); i++)
00305 if (a.get(static_cast<unsigned int>(i))) {
00306 m[i] = j; x[j++] = x[i];
00307 }
00308 x.size(j);
00309
00310 for (Advisors<Index> as(c); as(); ++as)
00311 as.advisor().i = m[as.advisor().i];
00312
00313 n_subsumed = 0;
00314 }
00315 return new (home) NaryLqLe<View,o>(home,share,*this);
00316 }
00317
00318 template<class View, int o>
00319 PropCost
00320 NaryLqLe<View,o>::cost(const Space&, const ModEventDelta&) const {
00321 return PropCost::binary(PropCost::HI);
00322 }
00323
00324 template<class View, int o>
00325 forceinline size_t
00326 NaryLqLe<View,o>::dispose(Space& home) {
00327 for (Advisors<Index> as(c); as(); ++as)
00328 x[as.advisor().i].cancel(home,as.advisor());
00329 c.dispose(home);
00330 while (!empty())
00331 (void) pop(home);
00332 (void) NaryPropagator<View,PC_INT_NONE>::dispose(home);
00333 return sizeof(*this);
00334 }
00335
00336
00337 template<class View, int o>
00338 ExecStatus
00339 NaryLqLe<View,o>::advise(Space& home, Advisor& _a, const Delta& d) {
00340 Index& a = static_cast<Index&>(_a);
00341 const int i = a.i;
00342 switch (View::modevent(d)) {
00343 case ME_INT_VAL:
00344 a.dispose(home,c);
00345 n_subsumed++;
00346 break;
00347 case ME_INT_BND:
00348 if (((i == 0) || (x[i-1].max()+o <= x[i].min())) &&
00349 ((i == x.size()-1) || (x[i].max()+o <= x[i+1].min()))) {
00350 x[i].cancel(home,a);
00351 a.dispose(home,c);
00352 n_subsumed++;
00353 return (run || (n_subsumed + 1 < x.size())) ? ES_FIX : ES_NOFIX;
00354 }
00355 break;
00356 default:
00357 return ES_FIX;
00358 }
00359 if (run)
00360 return ES_FIX;
00361 if (((i < x.size()-1) && (x[i+1].min() < x[i].min()+o)) ||
00362 ((i > 0) && (x[i-1].max() > x[i].max()-o))) {
00363 push(home,i);
00364 return ES_NOFIX;
00365 }
00366 return (n_subsumed+1 >= x.size()) ? ES_NOFIX : ES_FIX;
00367 }
00368
00369 template<class View, int o>
00370 ExecStatus
00371 NaryLqLe<View,o>::propagate(Space& home, const ModEventDelta&) {
00372 run = true;
00373 int n = x.size();
00374 while (!empty()) {
00375 int p = pop(home);
00376 for (int i=p; i<n-1; i++) {
00377 ModEvent me = x[i+1].gq(home,x[i].min()+o);
00378 if (me_failed(me))
00379 return ES_FAILED;
00380 if (!me_modified(me))
00381 break;
00382 }
00383 for (int i=p; i>0; i--) {
00384 ModEvent me = x[i-1].lq(home,x[i].max()-o);
00385 if (me_failed(me))
00386 return ES_FAILED;
00387 if (!me_modified(me))
00388 break;
00389 }
00390 }
00391 #ifdef GECODE_AUDIT
00392 for (int i=0; i<n-1; i++)
00393 assert(!me_modified(x[i+1].gq(home,x[i].min()+o)));
00394 for (int i=n-1; i>0; i--)
00395 assert(!me_modified(x[i-1].lq(home,x[i].max()-o)));
00396 #endif
00397 if (n_subsumed+1 >= n)
00398 return home.ES_SUBSUMED(*this);
00399 run = false;
00400 return ES_FIX;
00401 }
00402
00403
00404
00405
00406
00407
00408
00409
00410 template<class View, class CtrlView, ReifyMode rm>
00411 forceinline
00412 ReLq<View,CtrlView,rm>::ReLq(Home home, View x0, View x1, CtrlView b)
00413 : ReBinaryPropagator<View,PC_INT_BND,CtrlView>(home,x0,x1,b) {}
00414
00415 template<class View, class CtrlView, ReifyMode rm>
00416 ExecStatus
00417 ReLq<View,CtrlView,rm>::post(Home home, View x0, View x1, CtrlView b) {
00418 if (b.one()) {
00419 if (rm == RM_PMI)
00420 return ES_OK;
00421 return Lq<View>::post(home,x0,x1);
00422 }
00423 if (b.zero()) {
00424 if (rm == RM_IMP)
00425 return ES_OK;
00426 return Le<View>::post(home,x1,x0);
00427 }
00428 if (!same(x0,x1)) {
00429 switch (rtest_lq(x0,x1)) {
00430 case RT_TRUE:
00431 if (rm != RM_IMP)
00432 GECODE_ME_CHECK(b.one_none(home));
00433 break;
00434 case RT_FALSE:
00435 if (rm != RM_PMI)
00436 GECODE_ME_CHECK(b.zero_none(home));
00437 break;
00438 case RT_MAYBE:
00439 (void) new (home) ReLq<View,CtrlView,rm>(home,x0,x1,b);
00440 break;
00441 default: GECODE_NEVER;
00442 }
00443 } else if (rm != RM_IMP) {
00444 GECODE_ME_CHECK(b.one_none(home));
00445 }
00446 return ES_OK;
00447 }
00448
00449 template<class View, class CtrlView, ReifyMode rm>
00450 forceinline
00451 ReLq<View,CtrlView,rm>::ReLq(Space& home, bool share, ReLq& p)
00452 : ReBinaryPropagator<View,PC_INT_BND,CtrlView>(home,share,p) {}
00453
00454 template<class View, class CtrlView, ReifyMode rm>
00455 Actor*
00456 ReLq<View,CtrlView,rm>::copy(Space& home, bool share) {
00457 return new (home) ReLq<View,CtrlView,rm>(home,share,*this);
00458 }
00459
00460 template<class View, class CtrlView, ReifyMode rm>
00461 ExecStatus
00462 ReLq<View,CtrlView,rm>::propagate(Space& home, const ModEventDelta&) {
00463 if (b.one()) {
00464 if (rm != RM_PMI)
00465 GECODE_REWRITE(*this,Lq<View>::post(home(*this),x0,x1));
00466 } else if (b.zero()) {
00467 if (rm != RM_IMP)
00468 GECODE_REWRITE(*this,Le<View>::post(home(*this),x1,x0));
00469 } else {
00470 switch (rtest_lq(x0,x1)) {
00471 case RT_TRUE:
00472 if (rm != RM_IMP)
00473 GECODE_ME_CHECK(b.one_none(home));
00474 break;
00475 case RT_FALSE:
00476 if (rm != RM_PMI)
00477 GECODE_ME_CHECK(b.zero_none(home));
00478 break;
00479 case RT_MAYBE:
00480 return ES_FIX;
00481 default: GECODE_NEVER;
00482 }
00483 }
00484 return home.ES_SUBSUMED(*this);
00485 }
00486
00487
00488
00489
00490
00491
00492 template<class View, class CtrlView, ReifyMode rm>
00493 forceinline
00494 ReLqInt<View,CtrlView,rm>::ReLqInt(Home home, View x, int c0, CtrlView b)
00495 : ReUnaryPropagator<View,PC_INT_BND,CtrlView>(home,x,b), c(c0) {}
00496
00497 template<class View, class CtrlView, ReifyMode rm>
00498 ExecStatus
00499 ReLqInt<View,CtrlView,rm>::post(Home home, View x, int c, CtrlView b) {
00500 if (b.one()) {
00501 if (rm != RM_PMI)
00502 GECODE_ME_CHECK(x.lq(home,c));
00503 } else if (b.zero()) {
00504 if (rm != RM_IMP)
00505 GECODE_ME_CHECK(x.gr(home,c));
00506 } else {
00507 switch (rtest_lq(x,c)) {
00508 case RT_TRUE:
00509 if (rm != RM_IMP)
00510 GECODE_ME_CHECK(b.one_none(home));
00511 break;
00512 case RT_FALSE:
00513 if (rm != RM_PMI)
00514 GECODE_ME_CHECK(b.zero_none(home));
00515 break;
00516 case RT_MAYBE:
00517 (void) new (home) ReLqInt<View,CtrlView,rm>(home,x,c,b);
00518 break;
00519 default: GECODE_NEVER;
00520 }
00521 }
00522 return ES_OK;
00523 }
00524
00525
00526 template<class View, class CtrlView, ReifyMode rm>
00527 forceinline
00528 ReLqInt<View,CtrlView,rm>::ReLqInt(Space& home, bool share, ReLqInt& p)
00529 : ReUnaryPropagator<View,PC_INT_BND,CtrlView>(home,share,p), c(p.c) {}
00530
00531 template<class View, class CtrlView, ReifyMode rm>
00532 Actor*
00533 ReLqInt<View,CtrlView,rm>::copy(Space& home, bool share) {
00534 return new (home) ReLqInt<View,CtrlView,rm>(home,share,*this);
00535 }
00536
00537 template<class View, class CtrlView, ReifyMode rm>
00538 ExecStatus
00539 ReLqInt<View,CtrlView,rm>::propagate(Space& home, const ModEventDelta&) {
00540 if (b.one()) {
00541 if (rm != RM_PMI)
00542 GECODE_ME_CHECK(x0.lq(home,c));
00543 } else if (b.zero()) {
00544 if (rm != RM_IMP)
00545 GECODE_ME_CHECK(x0.gr(home,c));
00546 } else {
00547 switch (rtest_lq(x0,c)) {
00548 case RT_TRUE:
00549 if (rm != RM_IMP)
00550 GECODE_ME_CHECK(b.one_none(home));
00551 break;
00552 case RT_FALSE:
00553 if (rm != RM_PMI)
00554 GECODE_ME_CHECK(b.zero_none(home));
00555 break;
00556 case RT_MAYBE:
00557 return ES_FIX;
00558 default: GECODE_NEVER;
00559 }
00560 }
00561 return home.ES_SUBSUMED(*this);
00562 }
00563
00564 }}}
00565
00566
00567