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 #include <gecode/int/linear/int-noview.hpp>
00039
00040 namespace Gecode { namespace Int { namespace Linear {
00041
00046 template<class P, class N>
00047 forceinline bool
00048 isunit(ViewArray<P>&, ViewArray<N>&) { return false; }
00049 template<>
00050 forceinline bool
00051 isunit(ViewArray<IntView>&, ViewArray<IntView>&) { return true; }
00052 template<>
00053 forceinline bool
00054 isunit(ViewArray<IntView>&, ViewArray<NoView>&) { return true; }
00055 template<>
00056 forceinline bool
00057 isunit(ViewArray<NoView>&, ViewArray<IntView>&) { return true; }
00058
00059
00060
00061
00062
00063 template<class Val, class P, class N, PropCond pc>
00064 forceinline
00065 Lin<Val,P,N,pc>::Lin(Home home, ViewArray<P>& x0, ViewArray<N>& y0, Val c0)
00066 : Propagator(home), x(x0), y(y0), c(c0) {
00067 x.subscribe(home,*this,pc);
00068 y.subscribe(home,*this,pc);
00069 }
00070
00071 template<class Val, class P, class N, PropCond pc>
00072 forceinline
00073 Lin<Val,P,N,pc>::Lin(Space& home, bool share, Lin<Val,P,N,pc>& p)
00074 : Propagator(home,share,p), c(p.c) {
00075 x.update(home,share,p.x);
00076 y.update(home,share,p.y);
00077 }
00078
00079 template<class Val, class P, class N, PropCond pc>
00080 PropCost
00081 Lin<Val,P,N,pc>::cost(const Space&, const ModEventDelta&) const {
00082 return PropCost::linear(PropCost::LO, x.size()+y.size());
00083 }
00084
00085 template<class Val, class P, class N, PropCond pc>
00086 void
00087 Lin<Val,P,N,pc>::reschedule(Space& home) {
00088 x.reschedule(home,*this,pc);
00089 y.reschedule(home,*this,pc);
00090 }
00091
00092 template<class Val, class P, class N, PropCond pc>
00093 forceinline size_t
00094 Lin<Val,P,N,pc>::dispose(Space& home) {
00095 x.cancel(home,*this,pc);
00096 y.cancel(home,*this,pc);
00097 (void) Propagator::dispose(home);
00098 return sizeof(*this);
00099 }
00100
00101
00102
00103
00104
00105 template<class Val, class P, class N, PropCond pc, class Ctrl>
00106 forceinline
00107 ReLin<Val,P,N,pc,Ctrl>::ReLin
00108 (Home home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b0)
00109 : Lin<Val,P,N,pc>(home,x,y,c), b(b0) {
00110 b.subscribe(home,*this,PC_INT_VAL);
00111 }
00112
00113 template<class Val, class P, class N, PropCond pc, class Ctrl>
00114 forceinline
00115 ReLin<Val,P,N,pc,Ctrl>::ReLin
00116 (Space& home, bool share, ReLin<Val,P,N,pc,Ctrl>& p)
00117 : Lin<Val,P,N,pc>(home,share,p) {
00118 b.update(home,share,p.b);
00119 }
00120
00121 template<class Val, class P, class N, PropCond pc, class Ctrl>
00122 void
00123 ReLin<Val,P,N,pc,Ctrl>::reschedule(Space& home) {
00124 x.reschedule(home,*this,pc);
00125 y.reschedule(home,*this,pc);
00126 b.reschedule(home,*this,PC_INT_VAL);
00127 }
00128
00129 template<class Val, class P, class N, PropCond pc, class Ctrl>
00130 forceinline size_t
00131 ReLin<Val,P,N,pc,Ctrl>::dispose(Space& home) {
00132 b.cancel(home,*this,PC_BOOL_VAL);
00133 (void) Lin<Val,P,N,pc>::dispose(home);
00134 return sizeof(*this);
00135 }
00136
00137
00138
00139
00140
00141
00142 template<class Val, class View>
00143 void
00144 bounds_p(ModEventDelta med, ViewArray<View>& x, Val& c, Val& sl, Val& su) {
00145 int n = x.size();
00146 if (IntView::me(med) == ME_INT_VAL) {
00147 for (int i = n; i--; ) {
00148 Val m = x[i].min();
00149 if (x[i].assigned()) {
00150 c -= m; x[i] = x[--n];
00151 } else {
00152 sl -= m; su -= x[i].max();
00153 }
00154 }
00155 x.size(n);
00156 } else {
00157 for (int i = n; i--; ) {
00158 sl -= x[i].min(); su -= x[i].max();
00159 }
00160 }
00161 }
00162
00163 template<class Val, class View>
00164 void
00165 bounds_n(ModEventDelta med, ViewArray<View>& y, Val& c, Val& sl, Val& su) {
00166 int n = y.size();
00167 if (IntView::me(med) == ME_INT_VAL) {
00168 for (int i = n; i--; ) {
00169 Val m = y[i].max();
00170 if (y[i].assigned()) {
00171 c += m; y[i] = y[--n];
00172 } else {
00173 sl += m; su += y[i].min();
00174 }
00175 }
00176 y.size(n);
00177 } else {
00178 for (int i = n; i--; ) {
00179 sl += y[i].max(); su += y[i].min();
00180 }
00181 }
00182 }
00183
00184
00185 template<class Val, class P, class N>
00186 ExecStatus
00187 prop_bnd(Space& home, ModEventDelta med, Propagator& p,
00188 ViewArray<P>& x, ViewArray<N>& y, Val& c) {
00189
00190 Val sl = 0;
00191 Val su = 0;
00192
00193 bounds_p<Val,P>(med, x, c, sl, su);
00194 bounds_n<Val,N>(med, y, c, sl, su);
00195
00196 if ((IntView::me(med) == ME_INT_VAL) && ((x.size() + y.size()) <= 1)) {
00197 if (x.size() == 1) {
00198 GECODE_ME_CHECK(x[0].eq(home,c));
00199 return home.ES_SUBSUMED(p);
00200 }
00201 if (y.size() == 1) {
00202 GECODE_ME_CHECK(y[0].eq(home,-c));
00203 return home.ES_SUBSUMED(p);
00204 }
00205 return (c == static_cast<Val>(0)) ?
00206 home.ES_SUBSUMED(p) : ES_FAILED;
00207 }
00208
00209 sl += c; su += c;
00210
00211 const int mod_sl = 1;
00212 const int mod_su = 2;
00213
00214 int mod = mod_sl | mod_su;
00215
00216 do {
00217 if (mod & mod_sl) {
00218 mod -= mod_sl;
00219
00220 for (int i = x.size(); i--; ) {
00221 const Val xi_max = x[i].max();
00222 ModEvent me = x[i].lq(home,sl + x[i].min());
00223 if (me_failed(me))
00224 return ES_FAILED;
00225 if (me_modified(me)) {
00226 su += xi_max - x[i].max();
00227 mod |= mod_su;
00228 }
00229 }
00230
00231 for (int i = y.size(); i--; ) {
00232 const Val yi_min = y[i].min();
00233 ModEvent me = y[i].gq(home,y[i].max() - sl);
00234 if (me_failed(me))
00235 return ES_FAILED;
00236 if (me_modified(me)) {
00237 su += y[i].min() - yi_min;
00238 mod |= mod_su;
00239 }
00240 }
00241 }
00242 if (mod & mod_su) {
00243 mod -= mod_su;
00244
00245 for (int i = x.size(); i--; ) {
00246 const Val xi_min = x[i].min();
00247 ModEvent me = x[i].gq(home,su + x[i].max());
00248 if (me_failed(me))
00249 return ES_FAILED;
00250 if (me_modified(me)) {
00251 sl += xi_min - x[i].min();
00252 mod |= mod_sl;
00253 }
00254 }
00255
00256 for (int i = y.size(); i--; ) {
00257 const Val yi_max = y[i].max();
00258 ModEvent me = y[i].lq(home,y[i].min() - su);
00259 if (me_failed(me))
00260 return ES_FAILED;
00261 if (me_modified(me)) {
00262 sl += y[i].max() - yi_max;
00263 mod |= mod_sl;
00264 }
00265 }
00266 }
00267 } while (mod);
00268
00269 return (sl == su) ? home.ES_SUBSUMED(p) : ES_FIX;
00270 }
00271
00272
00273
00274
00275
00276
00277 template<class Val, class P, class N>
00278 forceinline
00279 Eq<Val,P,N>::Eq(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c)
00280 : Lin<Val,P,N,PC_INT_BND>(home,x,y,c) {}
00281
00282 template<class Val, class P, class N>
00283 ExecStatus
00284 Eq<Val,P,N>::post(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c) {
00285 ViewArray<NoView> nva;
00286 if (y.size() == 0) {
00287 (void) new (home) Eq<Val,P,NoView>(home,x,nva,c);
00288 } else if (x.size() == 0) {
00289 (void) new (home) Eq<Val,N,NoView>(home,y,nva,-c);
00290 } else {
00291 (void) new (home) Eq<Val,P,N>(home,x,y,c);
00292 }
00293 return ES_OK;
00294 }
00295
00296
00297 template<class Val, class P, class N>
00298 forceinline
00299 Eq<Val,P,N>::Eq(Space& home, bool share, Eq<Val,P,N>& p)
00300 : Lin<Val,P,N,PC_INT_BND>(home,share,p) {}
00301
00306 template<class Val, class P, class N>
00307 forceinline Actor*
00308 eqtobin(Space&, bool, Propagator&, ViewArray<P>&, ViewArray<N>&, Val) {
00309 return NULL;
00310 }
00311 template<class Val>
00312 forceinline Actor*
00313 eqtobin(Space& home, bool share, Propagator& p,
00314 ViewArray<IntView>& x, ViewArray<NoView>&, Val c) {
00315 assert(x.size() == 2);
00316 return new (home) EqBin<Val,IntView,IntView>
00317 (home,share,p,x[0],x[1],c);
00318 }
00319 template<class Val>
00320 forceinline Actor*
00321 eqtobin(Space& home, bool share, Propagator& p,
00322 ViewArray<NoView>&, ViewArray<IntView>& y, Val c) {
00323 assert(y.size() == 2);
00324 return new (home) EqBin<Val,IntView,IntView>
00325 (home,share,p,y[0],y[1],-c);
00326 }
00327 template<class Val>
00328 forceinline Actor*
00329 eqtobin(Space& home, bool share, Propagator& p,
00330 ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
00331 if (x.size() == 2)
00332 return new (home) EqBin<Val,IntView,IntView>
00333 (home,share,p,x[0],x[1],c);
00334 if (x.size() == 1)
00335 return new (home) EqBin<Val,IntView,MinusView>
00336 (home,share,p,x[0],MinusView(y[0]),c);
00337 return new (home) EqBin<Val,IntView,IntView>
00338 (home,share,p,y[0],y[1],-c);
00339 }
00340
00345 template<class Val, class P, class N>
00346 forceinline Actor*
00347 eqtoter(Space&, bool, Propagator&, ViewArray<P>&, ViewArray<N>&, Val) {
00348 return NULL;
00349 }
00350 template<class Val>
00351 forceinline Actor*
00352 eqtoter(Space& home, bool share, Propagator& p,
00353 ViewArray<IntView>& x, ViewArray<NoView>&, Val c) {
00354 assert(x.size() == 3);
00355 return new (home) EqTer<Val,IntView,IntView,IntView>
00356 (home,share,p,x[0],x[1],x[2],c);
00357 }
00358 template<class Val>
00359 forceinline Actor*
00360 eqtoter(Space& home, bool share, Propagator& p,
00361 ViewArray<NoView>&, ViewArray<IntView>& y, Val c) {
00362 assert(y.size() == 3);
00363 return new (home) EqTer<Val,IntView,IntView,IntView>
00364 (home,share,p,y[0],y[1],y[2],-c);
00365 }
00366 template<class Val>
00367 forceinline Actor*
00368 eqtoter(Space& home, bool share, Propagator& p,
00369 ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
00370 if (x.size() == 3)
00371 return new (home) EqTer<Val,IntView,IntView,IntView>
00372 (home,share,p,x[0],x[1],x[2],c);
00373 if (x.size() == 2)
00374 return new (home) EqTer<Val,IntView,IntView,MinusView>
00375 (home,share,p,x[0],x[1],MinusView(y[0]),c);
00376 if (x.size() == 1)
00377 return new (home) EqTer<Val,IntView,IntView,MinusView>
00378 (home,share,p,y[0],y[1],MinusView(x[0]),-c);
00379 return new (home) EqTer<Val,IntView,IntView,IntView>
00380 (home,share,p,y[0],y[1],y[2],-c);
00381 }
00382
00383 template<class Val, class P, class N>
00384 Actor*
00385 Eq<Val,P,N>::copy(Space& home, bool share) {
00386 if (isunit(x,y)) {
00387
00388 if (x.size() + y.size() == 2)
00389 return eqtobin(home,share,*this,x,y,c);
00390 if (x.size() + y.size() == 3)
00391 return eqtoter(home,share,*this,x,y,c);
00392 }
00393 return new (home) Eq<Val,P,N>(home,share,*this);
00394 }
00395
00396 template<class Val, class P, class N>
00397 ExecStatus
00398 Eq<Val,P,N>::propagate(Space& home, const ModEventDelta& med) {
00399 return prop_bnd<Val,P,N>(home,med,*this,x,y,c);
00400 }
00401
00402
00403
00404
00405
00406
00407 template<class Val, class P, class N, class Ctrl, ReifyMode rm>
00408 forceinline
00409 ReEq<Val,P,N,Ctrl,rm>::ReEq(Home home,
00410 ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b)
00411 : ReLin<Val,P,N,PC_INT_BND,Ctrl>(home,x,y,c,b) {}
00412
00413 template<class Val, class P, class N, class Ctrl, ReifyMode rm>
00414 ExecStatus
00415 ReEq<Val,P,N,Ctrl,rm>::post(Home home,
00416 ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b) {
00417 ViewArray<NoView> nva;
00418 if (y.size() == 0) {
00419 (void) new (home) ReEq<Val,P,NoView,Ctrl,rm>(home,x,nva,c,b);
00420 } else if (x.size() == 0) {
00421 (void) new (home) ReEq<Val,N,NoView,Ctrl,rm>(home,y,nva,-c,b);
00422 } else {
00423 (void) new (home) ReEq<Val,P,N,Ctrl,rm>(home,x,y,c,b);
00424 }
00425 return ES_OK;
00426 }
00427
00428
00429 template<class Val, class P, class N, class Ctrl, ReifyMode rm>
00430 forceinline
00431 ReEq<Val,P,N,Ctrl,rm>::ReEq(Space& home, bool share,
00432 ReEq<Val,P,N,Ctrl,rm>& p)
00433 : ReLin<Val,P,N,PC_INT_BND,Ctrl>(home,share,p) {}
00434
00435 template<class Val, class P, class N, class Ctrl, ReifyMode rm>
00436 Actor*
00437 ReEq<Val,P,N,Ctrl,rm>::copy(Space& home, bool share) {
00438 return new (home) ReEq<Val,P,N,Ctrl,rm>(home,share,*this);
00439 }
00440
00441 template<class Val, class P, class N, class Ctrl, ReifyMode rm>
00442 ExecStatus
00443 ReEq<Val,P,N,Ctrl,rm>::propagate(Space& home, const ModEventDelta& med) {
00444 if (b.zero()) {
00445 if (rm == RM_IMP)
00446 return home.ES_SUBSUMED(*this);
00447 GECODE_REWRITE(*this,(Nq<Val,P,N>::post(home(*this),x,y,c)));
00448 }
00449 if (b.one()) {
00450 if (rm == RM_PMI)
00451 return home.ES_SUBSUMED(*this);
00452 GECODE_REWRITE(*this,(Eq<Val,P,N>::post(home(*this),x,y,c)));
00453 }
00454
00455 Val sl = 0;
00456 Val su = 0;
00457
00458 bounds_p<Val,P>(med, x, c, sl, su);
00459 bounds_n<Val,N>(med, y, c, sl, su);
00460
00461 if ((-sl == c) && (-su == c)) {
00462 if (rm != RM_IMP)
00463 GECODE_ME_CHECK(b.one_none(home));
00464 return home.ES_SUBSUMED(*this);
00465 }
00466 if ((-sl > c) || (-su < c)) {
00467 if (rm != RM_PMI)
00468 GECODE_ME_CHECK(b.zero_none(home));
00469 return home.ES_SUBSUMED(*this);
00470 }
00471 return ES_FIX;
00472 }
00473
00474
00475
00476
00477
00478
00479
00480 template<class Val, class P, class N>
00481 forceinline
00482 Nq<Val,P,N>::Nq(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c)
00483 : Lin<Val,P,N,PC_INT_VAL>(home,x,y,c) {}
00484
00485 template<class Val, class P, class N>
00486 ExecStatus
00487 Nq<Val,P,N>::post(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c) {
00488 ViewArray<NoView> nva;
00489 if (y.size() == 0) {
00490 (void) new (home) Nq<Val,P,NoView>(home,x,nva,c);
00491 } else if (x.size() == 0) {
00492 (void) new (home) Nq<Val,N,NoView>(home,y,nva,-c);
00493 } else {
00494 (void) new (home) Nq<Val,P,N>(home,x,y,c);
00495 }
00496 return ES_OK;
00497 }
00498
00499
00500 template<class Val, class P, class N>
00501 forceinline
00502 Nq<Val,P,N>::Nq(Space& home, bool share, Nq<Val,P,N>& p)
00503 : Lin<Val,P,N,PC_INT_VAL>(home,share,p) {}
00504
00509 template<class Val, class P, class N>
00510 forceinline Actor*
00511 nqtobin(Space&, bool, Propagator&, ViewArray<P>&, ViewArray<N>&, Val) {
00512 return NULL;
00513 }
00514 template<class Val>
00515 forceinline Actor*
00516 nqtobin(Space& home, bool share, Propagator& p,
00517 ViewArray<IntView>& x, ViewArray<NoView>&, Val c) {
00518 assert(x.size() == 2);
00519 return new (home) NqBin<Val,IntView,IntView>
00520 (home,share,p,x[0],x[1],c);
00521 }
00522 template<class Val>
00523 forceinline Actor*
00524 nqtobin(Space& home, bool share, Propagator& p,
00525 ViewArray<NoView>&, ViewArray<IntView>& y, Val c) {
00526 assert(y.size() == 2);
00527 return new (home) NqBin<Val,IntView,IntView>
00528 (home,share,p,y[0],y[1],-c);
00529 }
00530 template<class Val>
00531 forceinline Actor*
00532 nqtobin(Space& home, bool share, Propagator& p,
00533 ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
00534 if (x.size() == 2)
00535 return new (home) NqBin<Val,IntView,IntView>
00536 (home,share,p,x[0],x[1],c);
00537 if (x.size() == 1)
00538 return new (home) NqBin<Val,IntView,MinusView>
00539 (home,share,p,x[0],MinusView(y[0]),c);
00540 return new (home) NqBin<Val,IntView,IntView>
00541 (home,share,p,y[0],y[1],-c);
00542 }
00543
00548 template<class Val, class P, class N>
00549 forceinline Actor*
00550 nqtoter(Space&, bool, Propagator&,ViewArray<P>&, ViewArray<N>&, Val) {
00551 return NULL;
00552 }
00553 template<class Val>
00554 forceinline Actor*
00555 nqtoter(Space& home, bool share, Propagator& p,
00556 ViewArray<IntView>& x, ViewArray<NoView>&, Val c) {
00557 assert(x.size() == 3);
00558 return new (home) NqTer<Val,IntView,IntView,IntView>
00559 (home,share,p,x[0],x[1],x[2],c);
00560 }
00561 template<class Val>
00562 forceinline Actor*
00563 nqtoter(Space& home, bool share, Propagator& p,
00564 ViewArray<NoView>&, ViewArray<IntView>& y, Val c) {
00565 assert(y.size() == 3);
00566 return new (home) NqTer<Val,IntView,IntView,IntView>
00567 (home,share,p,y[0],y[1],y[2],-c);
00568 }
00569 template<class Val>
00570 forceinline Actor*
00571 nqtoter(Space& home, bool share, Propagator& p,
00572 ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
00573 if (x.size() == 3)
00574 return new (home) NqTer<Val,IntView,IntView,IntView>
00575 (home,share,p,x[0],x[1],x[2],c);
00576 if (x.size() == 2)
00577 return new (home) NqTer<Val,IntView,IntView,MinusView>
00578 (home,share,p,x[0],x[1],MinusView(y[0]),c);
00579 if (x.size() == 1)
00580 return new (home) NqTer<Val,IntView,IntView,MinusView>
00581 (home,share,p,y[0],y[1],MinusView(x[0]),-c);
00582 return new (home) NqTer<Val,IntView,IntView,IntView>
00583 (home,share,p,y[0],y[1],y[2],-c);
00584 }
00585
00586 template<class Val, class P, class N>
00587 Actor*
00588 Nq<Val,P,N>::copy(Space& home, bool share) {
00589 if (isunit(x,y)) {
00590
00591 if (x.size() + y.size() == 2)
00592 return nqtobin(home,share,*this,x,y,c);
00593 if (x.size() + y.size() == 3)
00594 return nqtoter(home,share,*this,x,y,c);
00595 }
00596 return new (home) Nq<Val,P,N>(home,share,*this);
00597 }
00598
00599 template<class Val, class P, class N>
00600 ExecStatus
00601 Nq<Val,P,N>::propagate(Space& home, const ModEventDelta&) {
00602 for (int i = x.size(); i--; )
00603 if (x[i].assigned()) {
00604 c -= x[i].val(); x.move_lst(i);
00605 }
00606 for (int i = y.size(); i--; )
00607 if (y[i].assigned()) {
00608 c += y[i].val(); y.move_lst(i);
00609 }
00610 if (x.size() + y.size() <= 1) {
00611 if (x.size() == 1) {
00612 GECODE_ME_CHECK(x[0].nq(home,c)); return home.ES_SUBSUMED(*this);
00613 }
00614 if (y.size() == 1) {
00615 GECODE_ME_CHECK(y[0].nq(home,-c)); return home.ES_SUBSUMED(*this);
00616 }
00617 return (c == static_cast<Val>(0)) ?
00618 ES_FAILED : home.ES_SUBSUMED(*this);
00619 }
00620 return ES_FIX;
00621 }
00622
00623
00624
00625
00626
00627
00628
00629 template<class Val, class P, class N>
00630 forceinline
00631 Lq<Val,P,N>::Lq(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c)
00632 : Lin<Val,P,N,PC_INT_BND>(home,x,y,c) {}
00633
00634 template<class Val, class P, class N>
00635 ExecStatus
00636 Lq<Val,P,N>::post(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c) {
00637 ViewArray<NoView> nva;
00638 if (y.size() == 0) {
00639 (void) new (home) Lq<Val,P,NoView>(home,x,nva,c);
00640 } else if (x.size() == 0) {
00641 (void) new (home) Lq<Val,NoView,N>(home,nva,y,c);
00642 } else {
00643 (void) new (home) Lq<Val,P,N>(home,x,y,c);
00644 }
00645 return ES_OK;
00646 }
00647
00648
00649 template<class Val, class P, class N>
00650 forceinline
00651 Lq<Val,P,N>::Lq(Space& home, bool share, Lq<Val,P,N>& p)
00652 : Lin<Val,P,N,PC_INT_BND>(home,share,p) {}
00653
00658 template<class Val, class P, class N>
00659 forceinline Actor*
00660 lqtobin(Space&, bool, Propagator&,ViewArray<P>&, ViewArray<N>&, Val) {
00661 return NULL;
00662 }
00663 template<class Val>
00664 forceinline Actor*
00665 lqtobin(Space& home, bool share, Propagator& p,
00666 ViewArray<IntView>& x, ViewArray<NoView>&, Val c) {
00667 assert(x.size() == 2);
00668 return new (home) LqBin<Val,IntView,IntView>
00669 (home,share,p,x[0],x[1],c);
00670 }
00671 template<class Val>
00672 forceinline Actor*
00673 lqtobin(Space& home, bool share, Propagator& p,
00674 ViewArray<NoView>&, ViewArray<IntView>& y, Val c) {
00675 assert(y.size() == 2);
00676 return new (home) LqBin<Val,MinusView,MinusView>
00677 (home,share,p,MinusView(y[0]),MinusView(y[1]),c);
00678 }
00679 template<class Val>
00680 forceinline Actor*
00681 lqtobin(Space& home, bool share, Propagator& p,
00682 ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
00683 if (x.size() == 2)
00684 return new (home) LqBin<Val,IntView,IntView>
00685 (home,share,p,x[0],x[1],c);
00686 if (x.size() == 1)
00687 return new (home) LqBin<Val,IntView,MinusView>
00688 (home,share,p,x[0],MinusView(y[0]),c);
00689 return new (home) LqBin<Val,MinusView,MinusView>
00690 (home,share,p,MinusView(y[0]),MinusView(y[1]),c);
00691 }
00692
00697 template<class Val, class P, class N>
00698 forceinline Actor*
00699 lqtoter(Space&, bool, Propagator&, ViewArray<P>&, ViewArray<N>&, Val) {
00700 return NULL;
00701 }
00702 template<class Val>
00703 forceinline Actor*
00704 lqtoter(Space& home, bool share, Propagator& p,
00705 ViewArray<IntView>& x, ViewArray<NoView>&, Val c) {
00706 assert(x.size() == 3);
00707 return new (home) LqTer<Val,IntView,IntView,IntView>
00708 (home,share,p,x[0],x[1],x[2],c);
00709 }
00710 template<class Val>
00711 forceinline Actor*
00712 lqtoter(Space& home, bool share, Propagator& p,
00713 ViewArray<NoView>&, ViewArray<IntView>& y, Val c) {
00714 assert(y.size() == 3);
00715 return new (home) LqTer<Val,MinusView,MinusView,MinusView>
00716 (home,share,p,MinusView(y[0]),MinusView(y[1]),MinusView(y[2]),c);
00717 }
00718 template<class Val>
00719 forceinline Actor*
00720 lqtoter(Space& home, bool share, Propagator& p,
00721 ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) {
00722 if (x.size() == 3)
00723 return new (home) LqTer<Val,IntView,IntView,IntView>
00724 (home,share,p,x[0],x[1],x[2],c);
00725 if (x.size() == 2)
00726 return new (home) LqTer<Val,IntView,IntView,MinusView>
00727 (home,share,p,x[0],x[1],MinusView(y[0]),c);
00728 if (x.size() == 1)
00729 return new (home) LqTer<Val,IntView,MinusView,MinusView>
00730 (home,share,p,x[0],MinusView(y[0]),MinusView(y[1]),c);
00731 return new (home) LqTer<Val,MinusView,MinusView,MinusView>
00732 (home,share,p,MinusView(y[0]),MinusView(y[1]),MinusView(y[2]),c);
00733 }
00734
00735 template<class Val, class P, class N>
00736 Actor*
00737 Lq<Val,P,N>::copy(Space& home, bool share) {
00738 if (isunit(x,y)) {
00739
00740 if (x.size() + y.size() == 2)
00741 return lqtobin(home,share,*this,x,y,c);
00742 if (x.size() + y.size() == 3)
00743 return lqtoter(home,share,*this,x,y,c);
00744 }
00745 return new (home) Lq<Val,P,N>(home,share,*this);
00746 }
00747
00748 template<class Val, class P, class N>
00749 ExecStatus
00750 Lq<Val,P,N>::propagate(Space& home, const ModEventDelta& med) {
00751
00752 Val sl = 0;
00753
00754 if (IntView::me(med) == ME_INT_VAL) {
00755 for (int i = x.size(); i--; ) {
00756 Val m = x[i].min();
00757 if (x[i].assigned()) {
00758 c -= m; x.move_lst(i);
00759 } else {
00760 sl -= m;
00761 }
00762 }
00763 for (int i = y.size(); i--; ) {
00764 Val m = y[i].max();
00765 if (y[i].assigned()) {
00766 c += m; y.move_lst(i);
00767 } else {
00768 sl += m;
00769 }
00770 }
00771 if ((x.size() + y.size()) <= 1) {
00772 if (x.size() == 1) {
00773 GECODE_ME_CHECK(x[0].lq(home,c));
00774 return home.ES_SUBSUMED(*this);
00775 }
00776 if (y.size() == 1) {
00777 GECODE_ME_CHECK(y[0].gq(home,-c));
00778 return home.ES_SUBSUMED(*this);
00779 }
00780 return (c >= static_cast<Val>(0)) ?
00781 home.ES_SUBSUMED(*this) : ES_FAILED;
00782 }
00783 } else {
00784 for (int i = x.size(); i--; )
00785 sl -= x[i].min();
00786 for (int i = y.size(); i--; )
00787 sl += y[i].max();
00788 }
00789
00790 sl += c;
00791
00792 ExecStatus es = ES_FIX;
00793 bool assigned = true;
00794 for (int i = x.size(); i--; ) {
00795 assert(!x[i].assigned());
00796 Val slx = sl + x[i].min();
00797 ModEvent me = x[i].lq(home,slx);
00798 if (me == ME_INT_FAILED)
00799 return ES_FAILED;
00800 if (me != ME_INT_VAL)
00801 assigned = false;
00802 if (me_modified(me) && (slx != x[i].max()))
00803 es = ES_NOFIX;
00804 }
00805
00806 for (int i = y.size(); i--; ) {
00807 assert(!y[i].assigned());
00808 Val sly = y[i].max() - sl;
00809 ModEvent me = y[i].gq(home,sly);
00810 if (me == ME_INT_FAILED)
00811 return ES_FAILED;
00812 if (me != ME_INT_VAL)
00813 assigned = false;
00814 if (me_modified(me) && (sly != y[i].min()))
00815 es = ES_NOFIX;
00816 }
00817 return assigned ? home.ES_SUBSUMED(*this) : es;
00818 }
00819
00820
00821
00822
00823
00824
00825 template<class Val, class P, class N, ReifyMode rm>
00826 forceinline
00827 ReLq<Val,P,N,rm>::ReLq(Home home,
00828 ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b)
00829 : ReLin<Val,P,N,PC_INT_BND,BoolView>(home,x,y,c,b) {}
00830
00831 template<class Val, class P, class N, ReifyMode rm>
00832 ExecStatus
00833 ReLq<Val,P,N,rm>::post(Home home,
00834 ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b) {
00835 ViewArray<NoView> nva;
00836 if (y.size() == 0) {
00837 (void) new (home) ReLq<Val,P,NoView,rm>(home,x,nva,c,b);
00838 } else if (x.size() == 0) {
00839 (void) new (home) ReLq<Val,NoView,N,rm>(home,nva,y,c,b);
00840 } else {
00841 (void) new (home) ReLq<Val,P,N,rm>(home,x,y,c,b);
00842 }
00843 return ES_OK;
00844 }
00845
00846
00847 template<class Val, class P, class N, ReifyMode rm>
00848 forceinline
00849 ReLq<Val,P,N,rm>::ReLq(Space& home, bool share, ReLq<Val,P,N,rm>& p)
00850 : ReLin<Val,P,N,PC_INT_BND,BoolView>(home,share,p) {}
00851
00852 template<class Val, class P, class N, ReifyMode rm>
00853 Actor*
00854 ReLq<Val,P,N,rm>::copy(Space& home, bool share) {
00855 return new (home) ReLq<Val,P,N,rm>(home,share,*this);
00856 }
00857
00858 template<class Val, class P, class N, ReifyMode rm>
00859 ExecStatus
00860 ReLq<Val,P,N,rm>::propagate(Space& home, const ModEventDelta& med) {
00861 if (b.zero()) {
00862 if (rm == RM_IMP)
00863 return home.ES_SUBSUMED(*this);
00864 GECODE_REWRITE(*this,(Lq<Val,N,P>::post(home(*this),y,x,-c-1)));
00865 }
00866 if (b.one()) {
00867 if (rm == RM_PMI)
00868 return home.ES_SUBSUMED(*this);
00869 GECODE_REWRITE(*this,(Lq<Val,P,N>::post(home(*this),x,y,c)));
00870 }
00871
00872
00873 Val sl = 0;
00874 Val su = 0;
00875
00876 bounds_p<Val,P>(med,x,c,sl,su);
00877 bounds_n<Val,N>(med,y,c,sl,su);
00878
00879 if (-sl > c) {
00880 if (rm != RM_PMI)
00881 GECODE_ME_CHECK(b.zero_none(home));
00882 return home.ES_SUBSUMED(*this);
00883 }
00884 if (-su <= c) {
00885 if (rm != RM_IMP)
00886 GECODE_ME_CHECK(b.one_none(home));
00887 return home.ES_SUBSUMED(*this);
00888 }
00889
00890 return ES_FIX;
00891 }
00892
00893 }}}
00894
00895
00896