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