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