int-nary.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2003 00008 * 00009 * Last modified: 00010 * $Date: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $ 00011 * $Revision: 10364 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 * Linear propagators 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 forceinline size_t 00087 Lin<Val,P,N,pc>::dispose(Space& home) { 00088 x.cancel(home,*this,pc); 00089 y.cancel(home,*this,pc); 00090 (void) Propagator::dispose(home); 00091 return sizeof(*this); 00092 } 00093 00094 /* 00095 * Reified linear propagators 00096 * 00097 */ 00098 template<class Val, class P, class N, PropCond pc, class Ctrl> 00099 forceinline 00100 ReLin<Val,P,N,pc,Ctrl>::ReLin 00101 (Home home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b0) 00102 : Lin<Val,P,N,pc>(home,x,y,c), b(b0) { 00103 b.subscribe(home,*this,PC_INT_VAL); 00104 } 00105 00106 template<class Val, class P, class N, PropCond pc, class Ctrl> 00107 forceinline 00108 ReLin<Val,P,N,pc,Ctrl>::ReLin 00109 (Space& home, bool share, ReLin<Val,P,N,pc,Ctrl>& p) 00110 : Lin<Val,P,N,pc>(home,share,p) { 00111 b.update(home,share,p.b); 00112 } 00113 00114 template<class Val, class P, class N, PropCond pc, class Ctrl> 00115 forceinline size_t 00116 ReLin<Val,P,N,pc,Ctrl>::dispose(Space& home) { 00117 b.cancel(home,*this,PC_BOOL_VAL); 00118 (void) Lin<Val,P,N,pc>::dispose(home); 00119 return sizeof(*this); 00120 } 00121 00122 /* 00123 * Computing bounds 00124 * 00125 */ 00126 00127 template<class Val, class View> 00128 void 00129 bounds_p(ModEventDelta med, ViewArray<View>& x, Val& c, Val& sl, Val& su) { 00130 int n = x.size(); 00131 if (IntView::me(med) == ME_INT_VAL) { 00132 for (int i = n; i--; ) { 00133 Val m = x[i].min(); 00134 if (x[i].assigned()) { 00135 c -= m; x[i] = x[--n]; 00136 } else { 00137 sl -= m; su -= x[i].max(); 00138 } 00139 } 00140 x.size(n); 00141 } else { 00142 for (int i = n; i--; ) { 00143 sl -= x[i].min(); su -= x[i].max(); 00144 } 00145 } 00146 } 00147 00148 template<class Val, class View> 00149 void 00150 bounds_n(ModEventDelta med, ViewArray<View>& y, Val& c, Val& sl, Val& su) { 00151 int n = y.size(); 00152 if (IntView::me(med) == ME_INT_VAL) { 00153 for (int i = n; i--; ) { 00154 Val m = y[i].max(); 00155 if (y[i].assigned()) { 00156 c += m; y[i] = y[--n]; 00157 } else { 00158 sl += m; su += y[i].min(); 00159 } 00160 } 00161 y.size(n); 00162 } else { 00163 for (int i = n; i--; ) { 00164 sl += y[i].max(); su += y[i].min(); 00165 } 00166 } 00167 } 00168 00169 00170 template<class Val, class P, class N> 00171 ExecStatus 00172 prop_bnd(Space& home, ModEventDelta med, Propagator& p, 00173 ViewArray<P>& x, ViewArray<N>& y, Val& c) { 00174 // Eliminate singletons 00175 Val sl = 0; 00176 Val su = 0; 00177 00178 bounds_p<Val,P>(med, x, c, sl, su); 00179 bounds_n<Val,N>(med, y, c, sl, su); 00180 00181 if ((IntView::me(med) == ME_INT_VAL) && ((x.size() + y.size()) <= 1)) { 00182 if (x.size() == 1) { 00183 GECODE_ME_CHECK(x[0].eq(home,c)); 00184 return home.ES_SUBSUMED(p); 00185 } 00186 if (y.size() == 1) { 00187 GECODE_ME_CHECK(y[0].eq(home,-c)); 00188 return home.ES_SUBSUMED(p); 00189 } 00190 return (c == static_cast<Val>(0)) ? 00191 home.ES_SUBSUMED(p) : ES_FAILED; 00192 } 00193 00194 sl += c; su += c; 00195 00196 const int mod_sl = 1; 00197 const int mod_su = 2; 00198 00199 int mod = mod_sl | mod_su; 00200 00201 do { 00202 if (mod & mod_sl) { 00203 mod -= mod_sl; 00204 // Propagate upper bound for positive variables 00205 for (int i = x.size(); i--; ) { 00206 const Val xi_max = x[i].max(); 00207 ModEvent me = x[i].lq(home,sl + x[i].min()); 00208 if (me_failed(me)) 00209 return ES_FAILED; 00210 if (me_modified(me)) { 00211 su += xi_max - x[i].max(); 00212 mod |= mod_su; 00213 } 00214 } 00215 // Propagate lower bound for negative variables 00216 for (int i = y.size(); i--; ) { 00217 const Val yi_min = y[i].min(); 00218 ModEvent me = y[i].gq(home,y[i].max() - sl); 00219 if (me_failed(me)) 00220 return ES_FAILED; 00221 if (me_modified(me)) { 00222 su += y[i].min() - yi_min; 00223 mod |= mod_su; 00224 } 00225 } 00226 } 00227 if (mod & mod_su) { 00228 mod -= mod_su; 00229 // Propagate lower bound for positive variables 00230 for (int i = x.size(); i--; ) { 00231 const Val xi_min = x[i].min(); 00232 ModEvent me = x[i].gq(home,su + x[i].max()); 00233 if (me_failed(me)) 00234 return ES_FAILED; 00235 if (me_modified(me)) { 00236 sl += xi_min - x[i].min(); 00237 mod |= mod_sl; 00238 } 00239 } 00240 // Propagate upper bound for negative variables 00241 for (int i = y.size(); i--; ) { 00242 const Val yi_max = y[i].max(); 00243 ModEvent me = y[i].lq(home,y[i].min() - su); 00244 if (me_failed(me)) 00245 return ES_FAILED; 00246 if (me_modified(me)) { 00247 sl += y[i].max() - yi_max; 00248 mod |= mod_sl; 00249 } 00250 } 00251 } 00252 } while (mod); 00253 00254 return (sl == su) ? home.ES_SUBSUMED(p) : ES_FIX; 00255 } 00256 00257 /* 00258 * Bound consistent linear equation 00259 * 00260 */ 00261 00262 template<class Val, class P, class N> 00263 forceinline 00264 Eq<Val,P,N>::Eq(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c) 00265 : Lin<Val,P,N,PC_INT_BND>(home,x,y,c) {} 00266 00267 template<class Val, class P, class N> 00268 ExecStatus 00269 Eq<Val,P,N>::post(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c) { 00270 ViewArray<NoView> nva; 00271 if (y.size() == 0) { 00272 (void) new (home) Eq<Val,P,NoView>(home,x,nva,c); 00273 } else if (x.size() == 0) { 00274 (void) new (home) Eq<Val,N,NoView>(home,y,nva,-c); 00275 } else { 00276 (void) new (home) Eq<Val,P,N>(home,x,y,c); 00277 } 00278 return ES_OK; 00279 } 00280 00281 00282 template<class Val, class P, class N> 00283 forceinline 00284 Eq<Val,P,N>::Eq(Space& home, bool share, Eq<Val,P,N>& p) 00285 : Lin<Val,P,N,PC_INT_BND>(home,share,p) {} 00286 00291 template<class Val, class P, class N> 00292 forceinline Actor* 00293 eqtobin(Space&, bool, Propagator&, ViewArray<P>&, ViewArray<N>&, Val) { 00294 return NULL; 00295 } 00296 template<class Val> 00297 forceinline Actor* 00298 eqtobin(Space& home, bool share, Propagator& p, 00299 ViewArray<IntView>& x, ViewArray<NoView>&, Val c) { 00300 assert(x.size() == 2); 00301 return new (home) EqBin<Val,IntView,IntView> 00302 (home,share,p,x[0],x[1],c); 00303 } 00304 template<class Val> 00305 forceinline Actor* 00306 eqtobin(Space& home, bool share, Propagator& p, 00307 ViewArray<NoView>&, ViewArray<IntView>& y, Val c) { 00308 assert(y.size() == 2); 00309 return new (home) EqBin<Val,IntView,IntView> 00310 (home,share,p,y[0],y[1],-c); 00311 } 00312 template<class Val> 00313 forceinline Actor* 00314 eqtobin(Space& home, bool share, Propagator& p, 00315 ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) { 00316 if (x.size() == 2) 00317 return new (home) EqBin<Val,IntView,IntView> 00318 (home,share,p,x[0],x[1],c); 00319 if (x.size() == 1) 00320 return new (home) EqBin<Val,IntView,MinusView> 00321 (home,share,p,x[0],MinusView(y[0]),c); 00322 return new (home) EqBin<Val,IntView,IntView> 00323 (home,share,p,y[0],y[1],-c); 00324 } 00325 00330 template<class Val, class P, class N> 00331 forceinline Actor* 00332 eqtoter(Space&, bool, Propagator&, ViewArray<P>&, ViewArray<N>&, Val) { 00333 return NULL; 00334 } 00335 template<class Val> 00336 forceinline Actor* 00337 eqtoter(Space& home, bool share, Propagator& p, 00338 ViewArray<IntView>& x, ViewArray<NoView>&, Val c) { 00339 assert(x.size() == 3); 00340 return new (home) EqTer<Val,IntView,IntView,IntView> 00341 (home,share,p,x[0],x[1],x[2],c); 00342 } 00343 template<class Val> 00344 forceinline Actor* 00345 eqtoter(Space& home, bool share, Propagator& p, 00346 ViewArray<NoView>&, ViewArray<IntView>& y, Val c) { 00347 assert(y.size() == 3); 00348 return new (home) EqTer<Val,IntView,IntView,IntView> 00349 (home,share,p,y[0],y[1],y[2],-c); 00350 } 00351 template<class Val> 00352 forceinline Actor* 00353 eqtoter(Space& home, bool share, Propagator& p, 00354 ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) { 00355 if (x.size() == 3) 00356 return new (home) EqTer<Val,IntView,IntView,IntView> 00357 (home,share,p,x[0],x[1],x[2],c); 00358 if (x.size() == 2) 00359 return new (home) EqTer<Val,IntView,IntView,MinusView> 00360 (home,share,p,x[0],x[1],MinusView(y[0]),c); 00361 if (x.size() == 1) 00362 return new (home) EqTer<Val,IntView,IntView,MinusView> 00363 (home,share,p,y[0],y[1],MinusView(x[0]),-c); 00364 return new (home) EqTer<Val,IntView,IntView,IntView> 00365 (home,share,p,y[0],y[1],y[2],-c); 00366 } 00367 00368 template<class Val, class P, class N> 00369 Actor* 00370 Eq<Val,P,N>::copy(Space& home, bool share) { 00371 if (isunit(x,y)) { 00372 // Check whether rewriting is possible 00373 if (x.size() + y.size() == 2) 00374 return eqtobin(home,share,*this,x,y,c); 00375 if (x.size() + y.size() == 3) 00376 return eqtoter(home,share,*this,x,y,c); 00377 } 00378 return new (home) Eq<Val,P,N>(home,share,*this); 00379 } 00380 00381 template<class Val, class P, class N> 00382 ExecStatus 00383 Eq<Val,P,N>::propagate(Space& home, const ModEventDelta& med) { 00384 return prop_bnd<Val,P,N>(home,med,*this,x,y,c); 00385 } 00386 00387 /* 00388 * Reified bound consistent linear equation 00389 * 00390 */ 00391 00392 template<class Val, class P, class N, class Ctrl> 00393 forceinline 00394 ReEq<Val,P,N,Ctrl>::ReEq(Home home, 00395 ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b) 00396 : ReLin<Val,P,N,PC_INT_BND,Ctrl>(home,x,y,c,b) {} 00397 00398 template<class Val, class P, class N, class Ctrl> 00399 ExecStatus 00400 ReEq<Val,P,N,Ctrl>::post(Home home, 00401 ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b) { 00402 ViewArray<NoView> nva; 00403 if (y.size() == 0) { 00404 (void) new (home) ReEq<Val,P,NoView,Ctrl>(home,x,nva,c,b); 00405 } else if (x.size() == 0) { 00406 (void) new (home) ReEq<Val,N,NoView,Ctrl>(home,y,nva,-c,b); 00407 } else { 00408 (void) new (home) ReEq<Val,P,N,Ctrl>(home,x,y,c,b); 00409 } 00410 return ES_OK; 00411 } 00412 00413 00414 template<class Val, class P, class N, class Ctrl> 00415 forceinline 00416 ReEq<Val,P,N,Ctrl>::ReEq(Space& home, bool share, ReEq<Val,P,N,Ctrl>& p) 00417 : ReLin<Val,P,N,PC_INT_BND,Ctrl>(home,share,p) {} 00418 00419 template<class Val, class P, class N, class Ctrl> 00420 Actor* 00421 ReEq<Val,P,N,Ctrl>::copy(Space& home, bool share) { 00422 return new (home) ReEq<Val,P,N,Ctrl>(home,share,*this); 00423 } 00424 00425 template<class Val, class P, class N, class Ctrl> 00426 ExecStatus 00427 ReEq<Val,P,N,Ctrl>::propagate(Space& home, const ModEventDelta& med) { 00428 if (b.zero()) 00429 GECODE_REWRITE(*this,(Nq<Val,P,N>::post(home(*this),x,y,c))); 00430 if (b.one()) 00431 GECODE_REWRITE(*this,(Eq<Val,P,N>::post(home(*this),x,y,c))); 00432 00433 Val sl = 0; 00434 Val su = 0; 00435 00436 bounds_p<Val,P>(med, x, c, sl, su); 00437 bounds_n<Val,N>(med, y, c, sl, su); 00438 00439 if ((-sl == c) && (-su == c)) { 00440 GECODE_ME_CHECK(b.one_none(home)); 00441 return home.ES_SUBSUMED(*this); 00442 } 00443 if ((-sl > c) || (-su < c)) { 00444 GECODE_ME_CHECK(b.zero_none(home)); 00445 return home.ES_SUBSUMED(*this); 00446 } 00447 return ES_FIX; 00448 } 00449 00450 00451 /* 00452 * Domain consistent linear disequation 00453 * 00454 */ 00455 00456 template<class Val, class P, class N> 00457 forceinline 00458 Nq<Val,P,N>::Nq(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c) 00459 : Lin<Val,P,N,PC_INT_VAL>(home,x,y,c) {} 00460 00461 template<class Val, class P, class N> 00462 ExecStatus 00463 Nq<Val,P,N>::post(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c) { 00464 ViewArray<NoView> nva; 00465 if (y.size() == 0) { 00466 (void) new (home) Nq<Val,P,NoView>(home,x,nva,c); 00467 } else if (x.size() == 0) { 00468 (void) new (home) Nq<Val,N,NoView>(home,y,nva,-c); 00469 } else { 00470 (void) new (home) Nq<Val,P,N>(home,x,y,c); 00471 } 00472 return ES_OK; 00473 } 00474 00475 00476 template<class Val, class P, class N> 00477 forceinline 00478 Nq<Val,P,N>::Nq(Space& home, bool share, Nq<Val,P,N>& p) 00479 : Lin<Val,P,N,PC_INT_VAL>(home,share,p) {} 00480 00485 template<class Val, class P, class N> 00486 forceinline Actor* 00487 nqtobin(Space&, bool, Propagator&, ViewArray<P>&, ViewArray<N>&, Val) { 00488 return NULL; 00489 } 00490 template<class Val> 00491 forceinline Actor* 00492 nqtobin(Space& home, bool share, Propagator& p, 00493 ViewArray<IntView>& x, ViewArray<NoView>&, Val c) { 00494 assert(x.size() == 2); 00495 return new (home) NqBin<Val,IntView,IntView> 00496 (home,share,p,x[0],x[1],c); 00497 } 00498 template<class Val> 00499 forceinline Actor* 00500 nqtobin(Space& home, bool share, Propagator& p, 00501 ViewArray<NoView>&, ViewArray<IntView>& y, Val c) { 00502 assert(y.size() == 2); 00503 return new (home) NqBin<Val,IntView,IntView> 00504 (home,share,p,y[0],y[1],-c); 00505 } 00506 template<class Val> 00507 forceinline Actor* 00508 nqtobin(Space& home, bool share, Propagator& p, 00509 ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) { 00510 if (x.size() == 2) 00511 return new (home) NqBin<Val,IntView,IntView> 00512 (home,share,p,x[0],x[1],c); 00513 if (x.size() == 1) 00514 return new (home) NqBin<Val,IntView,MinusView> 00515 (home,share,p,x[0],MinusView(y[0]),c); 00516 return new (home) NqBin<Val,IntView,IntView> 00517 (home,share,p,y[0],y[1],-c); 00518 } 00519 00524 template<class Val, class P, class N> 00525 forceinline Actor* 00526 nqtoter(Space&, bool, Propagator&,ViewArray<P>&, ViewArray<N>&, Val) { 00527 return NULL; 00528 } 00529 template<class Val> 00530 forceinline Actor* 00531 nqtoter(Space& home, bool share, Propagator& p, 00532 ViewArray<IntView>& x, ViewArray<NoView>&, Val c) { 00533 assert(x.size() == 3); 00534 return new (home) NqTer<Val,IntView,IntView,IntView> 00535 (home,share,p,x[0],x[1],x[2],c); 00536 } 00537 template<class Val> 00538 forceinline Actor* 00539 nqtoter(Space& home, bool share, Propagator& p, 00540 ViewArray<NoView>&, ViewArray<IntView>& y, Val c) { 00541 assert(y.size() == 3); 00542 return new (home) NqTer<Val,IntView,IntView,IntView> 00543 (home,share,p,y[0],y[1],y[2],-c); 00544 } 00545 template<class Val> 00546 forceinline Actor* 00547 nqtoter(Space& home, bool share, Propagator& p, 00548 ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) { 00549 if (x.size() == 3) 00550 return new (home) NqTer<Val,IntView,IntView,IntView> 00551 (home,share,p,x[0],x[1],x[2],c); 00552 if (x.size() == 2) 00553 return new (home) NqTer<Val,IntView,IntView,MinusView> 00554 (home,share,p,x[0],x[1],MinusView(y[0]),c); 00555 if (x.size() == 1) 00556 return new (home) NqTer<Val,IntView,IntView,MinusView> 00557 (home,share,p,y[0],y[1],MinusView(x[0]),-c); 00558 return new (home) NqTer<Val,IntView,IntView,IntView> 00559 (home,share,p,y[0],y[1],y[2],-c); 00560 } 00561 00562 template<class Val, class P, class N> 00563 Actor* 00564 Nq<Val,P,N>::copy(Space& home, bool share) { 00565 if (isunit(x,y)) { 00566 // Check whether rewriting is possible 00567 if (x.size() + y.size() == 2) 00568 return nqtobin(home,share,*this,x,y,c); 00569 if (x.size() + y.size() == 3) 00570 return nqtoter(home,share,*this,x,y,c); 00571 } 00572 return new (home) Nq<Val,P,N>(home,share,*this); 00573 } 00574 00575 template<class Val, class P, class N> 00576 ExecStatus 00577 Nq<Val,P,N>::propagate(Space& home, const ModEventDelta&) { 00578 for (int i = x.size(); i--; ) 00579 if (x[i].assigned()) { 00580 c -= x[i].val(); x.move_lst(i); 00581 } 00582 for (int i = y.size(); i--; ) 00583 if (y[i].assigned()) { 00584 c += y[i].val(); y.move_lst(i); 00585 } 00586 if (x.size() + y.size() <= 1) { 00587 if (x.size() == 1) { 00588 GECODE_ME_CHECK(x[0].nq(home,c)); return home.ES_SUBSUMED(*this); 00589 } 00590 if (y.size() == 1) { 00591 GECODE_ME_CHECK(y[0].nq(home,-c)); return home.ES_SUBSUMED(*this); 00592 } 00593 return (c == static_cast<Val>(0)) ? 00594 ES_FAILED : home.ES_SUBSUMED(*this); 00595 } 00596 return ES_FIX; 00597 } 00598 00599 00600 /* 00601 * Bound consistent linear inequation 00602 * 00603 */ 00604 00605 template<class Val, class P, class N> 00606 forceinline 00607 Lq<Val,P,N>::Lq(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c) 00608 : Lin<Val,P,N,PC_INT_BND>(home,x,y,c) {} 00609 00610 template<class Val, class P, class N> 00611 ExecStatus 00612 Lq<Val,P,N>::post(Home home, ViewArray<P>& x, ViewArray<N>& y, Val c) { 00613 ViewArray<NoView> nva; 00614 if (y.size() == 0) { 00615 (void) new (home) Lq<Val,P,NoView>(home,x,nva,c); 00616 } else if (x.size() == 0) { 00617 (void) new (home) Lq<Val,NoView,N>(home,nva,y,c); 00618 } else { 00619 (void) new (home) Lq<Val,P,N>(home,x,y,c); 00620 } 00621 return ES_OK; 00622 } 00623 00624 00625 template<class Val, class P, class N> 00626 forceinline 00627 Lq<Val,P,N>::Lq(Space& home, bool share, Lq<Val,P,N>& p) 00628 : Lin<Val,P,N,PC_INT_BND>(home,share,p) {} 00629 00634 template<class Val, class P, class N> 00635 forceinline Actor* 00636 lqtobin(Space&, bool, Propagator&,ViewArray<P>&, ViewArray<N>&, Val) { 00637 return NULL; 00638 } 00639 template<class Val> 00640 forceinline Actor* 00641 lqtobin(Space& home, bool share, Propagator& p, 00642 ViewArray<IntView>& x, ViewArray<NoView>&, Val c) { 00643 assert(x.size() == 2); 00644 return new (home) LqBin<Val,IntView,IntView> 00645 (home,share,p,x[0],x[1],c); 00646 } 00647 template<class Val> 00648 forceinline Actor* 00649 lqtobin(Space& home, bool share, Propagator& p, 00650 ViewArray<NoView>&, ViewArray<IntView>& y, Val c) { 00651 assert(y.size() == 2); 00652 return new (home) LqBin<Val,MinusView,MinusView> 00653 (home,share,p,MinusView(y[0]),MinusView(y[1]),c); 00654 } 00655 template<class Val> 00656 forceinline Actor* 00657 lqtobin(Space& home, bool share, Propagator& p, 00658 ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) { 00659 if (x.size() == 2) 00660 return new (home) LqBin<Val,IntView,IntView> 00661 (home,share,p,x[0],x[1],c); 00662 if (x.size() == 1) 00663 return new (home) LqBin<Val,IntView,MinusView> 00664 (home,share,p,x[0],MinusView(y[0]),c); 00665 return new (home) LqBin<Val,MinusView,MinusView> 00666 (home,share,p,MinusView(y[0]),MinusView(y[1]),c); 00667 } 00668 00673 template<class Val, class P, class N> 00674 forceinline Actor* 00675 lqtoter(Space&, bool, Propagator&, ViewArray<P>&, ViewArray<N>&, Val) { 00676 return NULL; 00677 } 00678 template<class Val> 00679 forceinline Actor* 00680 lqtoter(Space& home, bool share, Propagator& p, 00681 ViewArray<IntView>& x, ViewArray<NoView>&, Val c) { 00682 assert(x.size() == 3); 00683 return new (home) LqTer<Val,IntView,IntView,IntView> 00684 (home,share,p,x[0],x[1],x[2],c); 00685 } 00686 template<class Val> 00687 forceinline Actor* 00688 lqtoter(Space& home, bool share, Propagator& p, 00689 ViewArray<NoView>&, ViewArray<IntView>& y, Val c) { 00690 assert(y.size() == 3); 00691 return new (home) LqTer<Val,MinusView,MinusView,MinusView> 00692 (home,share,p,MinusView(y[0]),MinusView(y[1]),MinusView(y[2]),c); 00693 } 00694 template<class Val> 00695 forceinline Actor* 00696 lqtoter(Space& home, bool share, Propagator& p, 00697 ViewArray<IntView>& x, ViewArray<IntView>& y, Val c) { 00698 if (x.size() == 3) 00699 return new (home) LqTer<Val,IntView,IntView,IntView> 00700 (home,share,p,x[0],x[1],x[2],c); 00701 if (x.size() == 2) 00702 return new (home) LqTer<Val,IntView,IntView,MinusView> 00703 (home,share,p,x[0],x[1],MinusView(y[0]),c); 00704 if (x.size() == 1) 00705 return new (home) LqTer<Val,IntView,MinusView,MinusView> 00706 (home,share,p,x[0],MinusView(y[0]),MinusView(y[1]),c); 00707 return new (home) LqTer<Val,MinusView,MinusView,MinusView> 00708 (home,share,p,MinusView(y[0]),MinusView(y[1]),MinusView(y[2]),c); 00709 } 00710 00711 template<class Val, class P, class N> 00712 Actor* 00713 Lq<Val,P,N>::copy(Space& home, bool share) { 00714 if (isunit(x,y)) { 00715 // Check whether rewriting is possible 00716 if (x.size() + y.size() == 2) 00717 return lqtobin(home,share,*this,x,y,c); 00718 if (x.size() + y.size() == 3) 00719 return lqtoter(home,share,*this,x,y,c); 00720 } 00721 return new (home) Lq<Val,P,N>(home,share,*this); 00722 } 00723 00724 template<class Val, class P, class N> 00725 ExecStatus 00726 Lq<Val,P,N>::propagate(Space& home, const ModEventDelta& med) { 00727 // Eliminate singletons 00728 Val sl = 0; 00729 00730 if (IntView::me(med) == ME_INT_VAL) { 00731 for (int i = x.size(); i--; ) { 00732 Val m = x[i].min(); 00733 if (x[i].assigned()) { 00734 c -= m; x.move_lst(i); 00735 } else { 00736 sl -= m; 00737 } 00738 } 00739 for (int i = y.size(); i--; ) { 00740 Val m = y[i].max(); 00741 if (y[i].assigned()) { 00742 c += m; y.move_lst(i); 00743 } else { 00744 sl += m; 00745 } 00746 } 00747 if ((x.size() + y.size()) <= 1) { 00748 if (x.size() == 1) { 00749 GECODE_ME_CHECK(x[0].lq(home,c)); 00750 return home.ES_SUBSUMED(*this); 00751 } 00752 if (y.size() == 1) { 00753 GECODE_ME_CHECK(y[0].gq(home,-c)); 00754 return home.ES_SUBSUMED(*this); 00755 } 00756 return (c >= static_cast<Val>(0)) ? 00757 home.ES_SUBSUMED(*this) : ES_FAILED; 00758 } 00759 } else { 00760 for (int i = x.size(); i--; ) 00761 sl -= x[i].min(); 00762 for (int i = y.size(); i--; ) 00763 sl += y[i].max(); 00764 } 00765 00766 sl += c; 00767 00768 ExecStatus es = ES_FIX; 00769 bool assigned = true; 00770 for (int i = x.size(); i--; ) { 00771 assert(!x[i].assigned()); 00772 Val slx = sl + x[i].min(); 00773 ModEvent me = x[i].lq(home,slx); 00774 if (me == ME_INT_FAILED) 00775 return ES_FAILED; 00776 if (me != ME_INT_VAL) 00777 assigned = false; 00778 if (me_modified(me) && (slx != x[i].max())) 00779 es = ES_NOFIX; 00780 } 00781 00782 for (int i = y.size(); i--; ) { 00783 assert(!y[i].assigned()); 00784 Val sly = y[i].max() - sl; 00785 ModEvent me = y[i].gq(home,sly); 00786 if (me == ME_INT_FAILED) 00787 return ES_FAILED; 00788 if (me != ME_INT_VAL) 00789 assigned = false; 00790 if (me_modified(me) && (sly != y[i].min())) 00791 es = ES_NOFIX; 00792 } 00793 return assigned ? home.ES_SUBSUMED(*this) : es; 00794 } 00795 00796 /* 00797 * Reified bound consistent linear inequation 00798 * 00799 */ 00800 00801 template<class Val, class P, class N> 00802 forceinline 00803 ReLq<Val,P,N>::ReLq 00804 (Home home, ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b) 00805 : ReLin<Val,P,N,PC_INT_BND,BoolView>(home,x,y,c,b) {} 00806 00807 template<class Val, class P, class N> 00808 ExecStatus 00809 ReLq<Val,P,N>::post 00810 (Home home, ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b) { 00811 ViewArray<NoView> nva; 00812 if (y.size() == 0) { 00813 (void) new (home) ReLq<Val,P,NoView>(home,x,nva,c,b); 00814 } else if (x.size() == 0) { 00815 (void) new (home) ReLq<Val,NoView,N>(home,nva,y,c,b); 00816 } else { 00817 (void) new (home) ReLq<Val,P,N>(home,x,y,c,b); 00818 } 00819 return ES_OK; 00820 } 00821 00822 00823 template<class Val, class P, class N> 00824 forceinline 00825 ReLq<Val,P,N>::ReLq(Space& home, bool share, ReLq<Val,P,N>& p) 00826 : ReLin<Val,P,N,PC_INT_BND,BoolView>(home,share,p) {} 00827 00828 template<class Val, class P, class N> 00829 Actor* 00830 ReLq<Val,P,N>::copy(Space& home, bool share) { 00831 return new (home) ReLq<Val,P,N>(home,share,*this); 00832 } 00833 00834 template<class Val, class P, class N> 00835 ExecStatus 00836 ReLq<Val,P,N>::propagate(Space& home, const ModEventDelta& med) { 00837 if (b.zero()) 00838 GECODE_REWRITE(*this,(Lq<Val,N,P>::post(home(*this),y,x,-c-1))); 00839 if (b.one()) 00840 GECODE_REWRITE(*this,(Lq<Val,P,N>::post(home(*this),x,y,c))); 00841 00842 // Eliminate singletons 00843 Val sl = 0; 00844 Val su = 0; 00845 00846 bounds_p<Val,P>(med,x,c,sl,su); 00847 bounds_n<Val,N>(med,y,c,sl,su); 00848 00849 if (-sl > c) { 00850 GECODE_ME_CHECK(b.zero_none(home)); 00851 return home.ES_SUBSUMED(*this); 00852 } 00853 if (-su <= c) { 00854 GECODE_ME_CHECK(b.one_none(home)); 00855 return home.ES_SUBSUMED(*this); 00856 } 00857 00858 return ES_FIX; 00859 } 00860 00861 }}} 00862 00863 // STATISTICS: int-prop 00864