00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 namespace Gecode { namespace Int { namespace Rel {
00023
00024
00025
00026
00027
00028
00029 template <class View0, class View1>
00030 forceinline
00031 EqBnd<View0,View1>::EqBnd(Space* home, View0 x0, View1 x1)
00032 : InhomBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND>(home,x0,x1) {}
00033
00034 template <class View0, class View1>
00035 ExecStatus
00036 EqBnd<View0,View1>::post(Space* home, View0 x0, View1 x1){
00037 if (x0.assigned()) {
00038 GECODE_ME_CHECK(x1.eq(home,x0.val()));
00039 } else if (x1.assigned()) {
00040 GECODE_ME_CHECK(x0.eq(home,x1.val()));
00041 } else if (!same(x0,x1)) {
00042 (void) new (home) EqBnd<View0,View1>(home,x0,x1);
00043 }
00044 return ES_OK;
00045 }
00046
00047 template <class View0, class View1>
00048 forceinline
00049 EqBnd<View0,View1>::EqBnd(Space* home, bool share, EqBnd<View0,View1>& p)
00050 : InhomBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND>(home,share,p) {}
00051
00052 template <class View0, class View1>
00053 forceinline
00054 EqBnd<View0,View1>::EqBnd(Space* home, bool share, Propagator& p,
00055 View0 x0, View1 x1)
00056 : InhomBinaryPropagator<View0,PC_INT_BND,View1,PC_INT_BND>(home,share,p,
00057 x0,x1) {}
00058
00059 template <class View0, class View1>
00060 Actor*
00061 EqBnd<View0,View1>::copy(Space* home, bool share) {
00062 return new (home) EqBnd<View0,View1>(home,share,*this);
00063 }
00064
00065 template <class View0, class View1>
00066 ExecStatus
00067 EqBnd<View0,View1>::propagate(Space* home) {
00068 if (x0.assigned()) {
00069 GECODE_ME_CHECK(x1.eq(home,x0.val()));
00070 return ES_SUBSUMED;
00071 }
00072 if (x1.assigned()) {
00073 GECODE_ME_CHECK(x0.eq(home,x1.val()));
00074 return ES_SUBSUMED;
00075 }
00076 do {
00077 GECODE_ME_CHECK(x0.gq(home,x1.min()));
00078 GECODE_ME_CHECK(x1.gq(home,x0.min()));
00079 } while (x0.min() != x1.min());
00080 do {
00081 GECODE_ME_CHECK(x0.lq(home,x1.max()));
00082 GECODE_ME_CHECK(x1.lq(home,x0.max()));
00083 } while (x0.max() != x1.max());
00084 return x0.assigned() ? ES_SUBSUMED : ES_FIX;
00085 }
00086
00087
00088
00089
00090
00091
00092
00093
00094
00095
00096 template <class View0, class View1>
00097 forceinline
00098 EqDom<View0,View1>::EqDom(Space* home, View0 x0, View1 x1)
00099 : InhomBinaryPropagator<View0,PC_INT_DOM,View1,PC_INT_DOM>(home,x0,x1) {}
00100
00101 template <class View0, class View1>
00102 ExecStatus
00103 EqDom<View0,View1>::post(Space* home, View0 x0, View1 x1){
00104 if (x0.assigned()) {
00105 GECODE_ME_CHECK(x1.eq(home,x0.val()));
00106 } else if (x1.assigned()) {
00107 GECODE_ME_CHECK(x0.eq(home,x1.val()));
00108 } else if (!same(x0,x1)) {
00109 (void) new (home) EqDom<View0,View1>(home,x0,x1);
00110 }
00111 return ES_OK;
00112 }
00113
00114
00115 template <class View0, class View1>
00116 forceinline
00117 EqDom<View0,View1>::EqDom(Space* home, bool share, EqDom<View0,View1>& p)
00118 : InhomBinaryPropagator<View0,PC_INT_DOM,View1,PC_INT_DOM>(home,share,p) {}
00119
00120 template <class View0, class View1>
00121 Actor*
00122 EqDom<View0,View1>::copy(Space* home, bool share) {
00123 return new (home) EqDom<View0,View1>(home,share,*this);
00124 }
00125
00126
00127 template <class View0, class View1>
00128 PropCost
00129 EqDom<View0,View1>::cost(void) const {
00130 if (View0::pme(this) == ME_INT_VAL || View1::pme(this) == ME_INT_VAL)
00131 return PC_UNARY_LO;
00132 if (View0::pme(this) == ME_INT_DOM || View1::pme(this) == ME_INT_DOM)
00133 return PC_BINARY_HI;
00134 return PC_BINARY_LO;
00135 }
00136
00137 template <class View0, class View1>
00138 ExecStatus
00139 EqDom<View0,View1>::propagate(Space* home) {
00140 if (x0.assigned()) {
00141 GECODE_ME_CHECK(x1.eq(home,x0.val()));
00142 return ES_SUBSUMED;
00143 }
00144 if (x1.assigned()) {
00145 GECODE_ME_CHECK(x0.eq(home,x1.val()));
00146 return ES_SUBSUMED;
00147 }
00148 if (View0::pme(this) != ME_INT_DOM && View1::pme(this) != ME_INT_DOM) {
00149 do {
00150 GECODE_ME_CHECK(x0.gq(home,x1.min()));
00151 GECODE_ME_CHECK(x1.gq(home,x0.min()));
00152 } while (x0.min() != x1.min());
00153 do {
00154 GECODE_ME_CHECK(x0.lq(home,x1.max()));
00155 GECODE_ME_CHECK(x1.lq(home,x0.max()));
00156 } while (x0.max() != x1.max());
00157 if (x0.assigned())
00158 return ES_SUBSUMED;
00159 if (x0.range() && x1.range())
00160 return ES_FIX;
00161 return this->ES_FIX_PARTIAL(View0::pme(ME_INT_DOM));
00162 }
00163 ViewRanges<View0> r0(x0);
00164 GECODE_ME_CHECK(x1.inter(home,r0));
00165 ViewRanges<View1> r1(x1);
00166 GECODE_ME_CHECK(x0.narrow(home,r1));
00167 return x0.assigned() ? ES_SUBSUMED : ES_FIX;
00168 }
00169
00170
00171
00172
00173
00174
00175
00176
00177 template <class View>
00178 forceinline
00179 NaryEqDom<View>::NaryEqDom(Space* home, ViewArray<View>& x)
00180 : NaryPropagator<View,PC_INT_DOM>(home,x) {}
00181
00182 template <class View>
00183 ExecStatus
00184 NaryEqDom<View>::post(Space* home, ViewArray<View>& x) {
00185 x.unique();
00186 if (x.size() == 2)
00187 return EqDom<View,View>::post(home,x[0],x[1]);
00188 else if (x.size() > 2)
00189 (void) new (home) NaryEqDom<View>(home,x);
00190 return ES_OK;
00191 }
00192
00193 template <class View>
00194 forceinline
00195 NaryEqDom<View>::NaryEqDom(Space* home, bool share, NaryEqDom<View>& p)
00196 : NaryPropagator<View,PC_INT_DOM>(home,share,p) {}
00197
00198 template <class View>
00199 Actor*
00200 NaryEqDom<View>::copy(Space* home, bool share) {
00201 return new (home) NaryEqDom<View>(home,share,*this);
00202 }
00203
00204 template <class View>
00205 PropCost
00206 NaryEqDom<View>::cost(void) const {
00207 if (View::pme(this) == ME_INT_VAL)
00208 return PC_UNARY_LO;
00209 if (View::pme(this) == ME_INT_DOM)
00210 return cost_hi(x.size(),PC_LINEAR_HI);
00211 return cost_lo(x.size(),PC_LINEAR_LO);
00212 }
00213
00214 template <class View>
00215 ExecStatus
00216 NaryEqDom<View>::propagate(Space* home) {
00217 assert(x.size() > 2);
00218
00219 ModEvent me = View::pme(this);
00220 if (me == ME_INT_VAL) {
00221
00222 for (int i = 0; ; i++)
00223 if (x[i].assigned()) {
00224 int n = x[i].val();
00225 x.move_lst(i);
00226 for (int i = x.size(); i--; )
00227 GECODE_ME_CHECK(x[i].eq(home,n));
00228 return ES_SUBSUMED;
00229 }
00230 assert(0);
00231 return ES_SUBSUMED;
00232 }
00233
00234 if (me == ME_INT_BND) {
00235 {
00236
00237 int mn = x[0].min();
00238 restart_min:
00239 for (int i = x.size(); i--; ) {
00240 GECODE_ME_CHECK(x[i].gq(home,mn));
00241 if (mn < x[i].min()) {
00242 mn = x[i].min();
00243 goto restart_min;
00244 }
00245 }
00246 }
00247 {
00248
00249 int mx = x[0].max();
00250 restart_max:
00251 for (int i = x.size(); i--; ) {
00252 GECODE_ME_CHECK(x[i].lq(home,mx));
00253 if (mx > x[i].max()) {
00254 mx = x[i].max();
00255 goto restart_max;
00256 }
00257 }
00258 }
00259 if (x[0].assigned())
00260 return ES_SUBSUMED;
00261 return this->ES_FIX_PARTIAL(View::pme(ME_INT_DOM));
00262 }
00263
00264 int n = x.size();
00265
00266 GECODE_AUTOARRAY(ViewRanges<View>, i_x, n);
00267 for (int i = n; i--; ) {
00268 ViewRanges<View> i_xi(x[i]);
00269 i_x[i] = i_xi;
00270 }
00271 Iter::Ranges::NaryInter<ViewRanges<View> > r(i_x,n);
00272 Iter::Ranges::Cache<Iter::Ranges::NaryInter<ViewRanges<View> > > rc(r);
00273
00274 if (!rc())
00275 return ES_FAILED;
00276 ++rc;
00277 if (!rc()) {
00278 rc.reset();
00279 for (int i = n; i--; ) {
00280 GECODE_ME_CHECK(x[i].gq(home,rc.min()));
00281 GECODE_ME_CHECK(x[i].lq(home,rc.max()));
00282 }
00283 } else {
00284 for (int i = n; i--; ) {
00285 rc.reset();
00286 GECODE_ME_CHECK(x[i].narrow(home,rc));
00287 }
00288 }
00289 return ES_FIX;
00290 }
00291
00292
00293
00294
00295
00296
00297
00298
00299 template <class View>
00300 forceinline
00301 NaryEqBnd<View>::NaryEqBnd(Space* home, ViewArray<View>& x)
00302 : NaryPropagator<View,PC_INT_BND>(home,x) {}
00303
00304 template <class View>
00305 ExecStatus
00306 NaryEqBnd<View>::post(Space* home, ViewArray<View>& x) {
00307 if (x.size() == 2)
00308 return EqBnd<View,View>::post(home,x[0],x[1]);
00309 else if (x.size() > 2)
00310 (void) new (home) NaryEqBnd<View>(home,x);
00311 return ES_OK;
00312 }
00313
00314 template <class View>
00315 forceinline
00316 NaryEqBnd<View>::NaryEqBnd(Space* home, bool share, NaryEqBnd<View>& p)
00317 : NaryPropagator<View,PC_INT_BND>(home,share,p) {}
00318
00319 template <class View>
00320 Actor*
00321 NaryEqBnd<View>::copy(Space* home, bool share) {
00322 return new (home) NaryEqBnd<View>(home,share,*this);
00323 }
00324
00325 template <class View>
00326 PropCost
00327 NaryEqBnd<View>::cost(void) const {
00328 if (View::pme(this) == ME_INT_VAL)
00329 return PC_UNARY_LO;
00330 return cost_lo(x.size(),PC_LINEAR_LO);
00331 }
00332
00333 template <class View>
00334 ExecStatus
00335 NaryEqBnd<View>::propagate(Space* home) {
00336 assert(x.size() > 2);
00337
00338 if (View::pme(this) == ME_INT_VAL) {
00339
00340 for (int i = 0; ; i++)
00341 if (x[i].assigned()) {
00342 int n = x[i].val();
00343 x.move_lst(i);
00344 for (int i = x.size(); i--; )
00345 GECODE_ME_CHECK(x[i].eq(home,n));
00346 return ES_SUBSUMED;
00347 }
00348 assert(0);
00349 return ES_SUBSUMED;
00350 }
00351
00352 int mn = x[0].min();
00353 restart_min:
00354 for (int i = x.size(); i--; ) {
00355 GECODE_ME_CHECK(x[i].gq(home,mn));
00356 if (mn < x[i].min()) {
00357 mn = x[i].min();
00358 goto restart_min;
00359 }
00360 }
00361 int mx = x[0].max();
00362 restart_max:
00363 for (int i = x.size(); i--; ) {
00364 GECODE_ME_CHECK(x[i].lq(home,mx));
00365 if (mx > x[i].max()) {
00366 mx = x[i].max();
00367 goto restart_max;
00368 }
00369 }
00370 return x[0].assigned() ? ES_SUBSUMED : ES_FIX;
00371 }
00372
00373
00374
00375
00376
00377
00378
00379
00380 template <class View, class CtrlView>
00381 forceinline
00382 ReEqDom<View,CtrlView>::ReEqDom(Space* home, View x0, View x1, CtrlView b)
00383 : ReBinaryPropagator<View,PC_INT_DOM,CtrlView>(home,x0,x1,b) {}
00384
00385 template <class View, class CtrlView>
00386 ExecStatus
00387 ReEqDom<View,CtrlView>::post(Space* home, View x0, View x1, CtrlView b) {
00388 if (b.one())
00389 return EqDom<View,View>::post(home,x0,x1);
00390 if (b.zero())
00391 return Nq<View>::post(home,x0,x1);
00392 if (!same(x0,x1)) {
00393 (void) new (home) ReEqDom(home,x0,x1,b);
00394 } else {
00395 GECODE_ME_CHECK(b.t_one(home));
00396 }
00397 return ES_OK;
00398 }
00399
00400
00401 template <class View, class CtrlView>
00402 forceinline
00403 ReEqDom<View,CtrlView>::ReEqDom(Space* home, bool share, ReEqDom& p)
00404 : ReBinaryPropagator<View,PC_INT_DOM,CtrlView>(home,share,p) {}
00405
00406 template <class View, class CtrlView>
00407 Actor*
00408 ReEqDom<View,CtrlView>::copy(Space* home, bool share) {
00409 return new (home) ReEqDom<View,CtrlView>(home,share,*this);
00410 }
00411
00412
00413 template <class View, class CtrlView>
00414 ExecStatus
00415 ReEqDom<View,CtrlView>::propagate(Space* home) {
00416 if (b.one()) {
00417 if (EqDom<View,View>::post(home,x0,x1) == ES_FAILED)
00418 return ES_FAILED;
00419 return ES_SUBSUMED;
00420 }
00421 if (b.zero()) {
00422 if (Nq<View>::post(home,x0,x1) == ES_FAILED)
00423 return ES_FAILED;
00424 return ES_SUBSUMED;
00425 }
00426 switch (rtest_eq_dom(x0,x1)) {
00427 case RT_TRUE:
00428 b.t_one_none(home); return ES_SUBSUMED;
00429 case RT_FALSE:
00430 b.t_zero_none(home); return ES_SUBSUMED;
00431 default: ;
00432 }
00433 return ES_FIX;
00434 }
00435
00436
00437
00438
00439
00440
00441
00442
00443 template <class View, class CtrlView>
00444 forceinline
00445 ReEqBnd<View,CtrlView>::ReEqBnd(Space* home, View x0, View x1, CtrlView b)
00446 : ReBinaryPropagator<View,PC_INT_BND,CtrlView>(home,x0,x1,b) {}
00447
00448 template <class View, class CtrlView>
00449 ExecStatus
00450 ReEqBnd<View,CtrlView>::post(Space* home, View x0, View x1, CtrlView b){
00451 if (b.one())
00452 return EqBnd<View,View>::post(home,x0,x1);
00453 if (b.zero())
00454 return Nq<View>::post(home,x0,x1);
00455 if (!same(x0,x1)) {
00456 (void) new (home) ReEqBnd(home,x0,x1,b);
00457 } else {
00458 GECODE_ME_CHECK(b.t_one(home));
00459 }
00460 return ES_OK;
00461 }
00462
00463
00464 template <class View, class CtrlView>
00465 forceinline
00466 ReEqBnd<View,CtrlView>::ReEqBnd(Space* home, bool share, ReEqBnd& p)
00467 : ReBinaryPropagator<View,PC_INT_BND,CtrlView>(home,share,p) {}
00468
00469 template <class View, class CtrlView>
00470 Actor*
00471 ReEqBnd<View,CtrlView>::copy(Space* home, bool share) {
00472 return new (home) ReEqBnd<View,CtrlView>(home,share,*this);
00473 }
00474
00475
00476 template <class View, class CtrlView>
00477 ExecStatus
00478 ReEqBnd<View,CtrlView>::propagate(Space* home) {
00479 if (b.one()) {
00480 if (EqBnd<View,View>::post(home,x0,x1) == ES_FAILED)
00481 return ES_FAILED;
00482 return ES_SUBSUMED;
00483 }
00484 if (b.zero()) {
00485 if (Nq<View>::post(home,x0,x1) == ES_FAILED)
00486 return ES_FAILED;
00487 return ES_SUBSUMED;
00488 }
00489 switch (rtest_eq_bnd(x0,x1)) {
00490 case RT_TRUE:
00491 b.t_one_none(home); return ES_SUBSUMED;
00492 case RT_FALSE:
00493 b.t_zero_none(home); return ES_SUBSUMED;
00494 default: ;
00495 }
00496 return ES_FIX;
00497 }
00498
00499
00500
00501
00502
00503
00504
00505
00506
00507 template <class View, class CtrlView>
00508 forceinline
00509 ReEqDomInt<View,CtrlView>::ReEqDomInt
00510 (Space* home, View x, int c0, CtrlView b)
00511 : ReUnaryPropagator<View,PC_INT_DOM,CtrlView>(home,x,b), c(c0) {}
00512
00513 template <class View, class CtrlView>
00514 ExecStatus
00515 ReEqDomInt<View,CtrlView>::post(Space* home, View x, int c, CtrlView b) {
00516 if (b.one()) {
00517 GECODE_ME_CHECK(x.eq(home,c));
00518 } else if (b.zero()) {
00519 GECODE_ME_CHECK(x.nq(home,c));
00520 } else if (x.assigned()) {
00521 assert(b.none());
00522 if (x.val() == c) {
00523 b.t_one_none(home);
00524 } else {
00525 b.t_zero_none(home);
00526 }
00527 } else {
00528 (void) new (home) ReEqDomInt(home,x,c,b);
00529 }
00530 return ES_OK;
00531 }
00532
00533
00534 template <class View, class CtrlView>
00535 forceinline
00536 ReEqDomInt<View,CtrlView>::ReEqDomInt(Space* home, bool share, ReEqDomInt& p)
00537 : ReUnaryPropagator<View,PC_INT_DOM,CtrlView>(home,share,p), c(p.c) {}
00538
00539 template <class View, class CtrlView>
00540 Actor*
00541 ReEqDomInt<View,CtrlView>::copy(Space* home, bool share) {
00542 return new (home) ReEqDomInt<View,CtrlView>(home,share,*this);
00543 }
00544
00545 template <class View, class CtrlView>
00546 ExecStatus
00547 ReEqDomInt<View,CtrlView>::propagate(Space* home) {
00548 if (b.one()) {
00549 GECODE_ME_CHECK(x0.eq(home,c)); return ES_SUBSUMED;
00550 }
00551 if (b.zero()) {
00552 GECODE_ME_CHECK(x0.nq(home,c)); return ES_SUBSUMED;
00553 }
00554 switch (rtest_eq_dom(x0,c)) {
00555 case RT_TRUE:
00556 b.t_one_none(home); return ES_SUBSUMED;
00557 case RT_FALSE:
00558 b.t_zero_none(home); return ES_SUBSUMED;
00559 default: ;
00560 }
00561 return ES_FIX;
00562 }
00563
00564
00565
00566
00567
00568
00569
00570
00571
00572 template <class View, class CtrlView>
00573 forceinline
00574 ReEqBndInt<View,CtrlView>::ReEqBndInt
00575 (Space* home, View x, int c0, CtrlView b)
00576 : ReUnaryPropagator<View,PC_INT_BND,CtrlView>(home,x,b), c(c0) {}
00577
00578 template <class View, class CtrlView>
00579 ExecStatus
00580 ReEqBndInt<View,CtrlView>::post(Space* home, View x, int c, CtrlView b) {
00581 if (b.one()) {
00582 GECODE_ME_CHECK(x.eq(home,c));
00583 } else if (b.zero()) {
00584 GECODE_ME_CHECK(x.nq(home,c));
00585 } else if (x.assigned()) {
00586 assert(b.none());
00587 if (x.val() == c) {
00588 b.t_one_none(home);
00589 } else {
00590 b.t_zero_none(home);
00591 }
00592 } else {
00593 (void) new (home) ReEqBndInt(home,x,c,b);
00594 }
00595 return ES_OK;
00596 }
00597
00598
00599 template <class View, class CtrlView>
00600 forceinline
00601 ReEqBndInt<View,CtrlView>::ReEqBndInt(Space* home, bool share, ReEqBndInt& p)
00602 : ReUnaryPropagator<View,PC_INT_BND,CtrlView>(home,share,p), c(p.c) {}
00603
00604 template <class View, class CtrlView>
00605 Actor*
00606 ReEqBndInt<View,CtrlView>::copy(Space* home, bool share) {
00607 return new (home) ReEqBndInt<View,CtrlView>(home,share,*this);
00608 }
00609
00610 template <class View, class CtrlView>
00611 ExecStatus
00612 ReEqBndInt<View,CtrlView>::propagate(Space* home) {
00613 if (b.one()) {
00614 GECODE_ME_CHECK(x0.eq(home,c)); return ES_SUBSUMED;
00615 }
00616 if (b.zero()) {
00617 GECODE_ME_CHECK(x0.nq(home,c)); return ES_SUBSUMED;
00618 }
00619 switch (rtest_eq_bnd(x0,c)) {
00620 case RT_TRUE:
00621 b.t_one_none(home); return ES_SUBSUMED;
00622 case RT_FALSE:
00623 b.t_zero_none(home); return ES_SUBSUMED;
00624 default: ;
00625 }
00626 return ES_FIX;
00627 }
00628
00629 }}}
00630
00631
00632