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