00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "int/linear/noview.icc"
00023
00024 namespace Gecode { namespace Int { namespace Linear {
00025
00026
00027
00028
00029
00030 template <class Val, class P, class N, PropCond pc>
00031 forceinline
00032 Lin<Val,P,N,pc>::Lin(Space* home, ViewArray<P>& x0, ViewArray<N>& y0, Val c0)
00033 : Propagator(home), x(x0), y(y0), c(c0) {
00034 x.subscribe(home,this,pc);
00035 y.subscribe(home,this,pc);
00036 }
00037
00038 template <class Val, class P, class N, PropCond pc>
00039 forceinline
00040 Lin<Val,P,N,pc>::Lin(Space* home, bool share, Lin<Val,P,N,pc>& p)
00041 : Propagator(home,share,p), c(p.c) {
00042 x.update(home,share,p.x);
00043 y.update(home,share,p.y);
00044 }
00045
00046 template <class Val, class P, class N, PropCond pc>
00047 PropCost
00048 Lin<Val,P,N,pc>::cost(void) const {
00049 return cost_lo(x.size() + y.size(), PC_LINEAR_LO);
00050 }
00051
00052 template <class Val, class P, class N, PropCond pc>
00053 inline
00054 Lin<Val,P,N,pc>::~Lin(void) {
00055 x.cancel(this,pc);
00056 y.cancel(this,pc);
00057 }
00058
00059
00060
00061
00062
00063
00064 template <class Val, class P, class N, PropCond pc, class Ctrl>
00065 forceinline
00066 ReLin<Val,P,N,pc,Ctrl>::ReLin
00067 (Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b0)
00068 : Lin<Val,P,N,pc>(home,x,y,c), b(b0) {
00069 b.subscribe(home,this,PC_INT_VAL);
00070 }
00071
00072 template <class Val, class P, class N, PropCond pc, class Ctrl>
00073 forceinline
00074 ReLin<Val,P,N,pc,Ctrl>::ReLin
00075 (Space* home, bool share, ReLin<Val,P,N,pc,Ctrl>& p)
00076 : Lin<Val,P,N,pc>(home,share,p) {
00077 b.update(home,share,p.b);
00078 }
00079
00080 template <class Val, class P, class N, PropCond pc, class Ctrl>
00081 inline
00082 ReLin<Val,P,N,pc,Ctrl>::~ReLin(void) {
00083 b.cancel(this,PC_INT_VAL);
00084 }
00085
00086
00087
00088
00089
00090
00091
00092 template <class Val, class View>
00093 void
00094 bounds_p(const Propagator* p, ViewArray<View>& x,
00095 Val& c, Val& sl, Val& su) {
00096 int n = x.size();
00097 if (IntView::pme(p) == ME_INT_VAL) {
00098 for (int i = n; i--; ) {
00099 Val m = x[i].min();
00100 if (x[i].assigned()) {
00101 c -= m; x[i] = x[--n];
00102 } else {
00103 sl -= m; su -= x[i].max();
00104 }
00105 }
00106 x.size(n);
00107 } else {
00108 for (int i = n; i--; ) {
00109 sl -= x[i].min(); su -= x[i].max();
00110 }
00111 }
00112 }
00113
00114 template <class Val, class View>
00115 void
00116 bounds_n(const Propagator* p, ViewArray<View>& y,
00117 Val& c, Val& sl, Val& su) {
00118 int n = y.size();
00119 if (IntView::pme(p) == ME_INT_VAL) {
00120 for (int i = n; i--; ) {
00121 Val m = y[i].max();
00122 if (y[i].assigned()) {
00123 c += m; y[i] = y[--n];
00124 } else {
00125 sl += m; su += y[i].min();
00126 }
00127 }
00128 y.size(n);
00129 } else {
00130 for (int i = n; i--; ) {
00131 sl += y[i].max(); su += y[i].min();
00132 }
00133 }
00134 }
00135
00136
00137
00138
00139
00140
00141
00142 template <class Val, class P, class N>
00143 forceinline
00144 Eq<Val,P,N>::Eq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c)
00145 : Lin<Val,P,N,PC_INT_BND>(home,x,y,c) {}
00146
00147 template <class Val, class P, class N>
00148 ExecStatus
00149 Eq<Val,P,N>::post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c) {
00150 ViewArray<NoView> nva;
00151 if (y.size() == 0) {
00152 (void) new (home) Eq<Val,P,NoView>(home,x,nva,c);
00153 } else if (x.size() == 0) {
00154 (void) new (home) Eq<Val,N,NoView>(home,y,nva,-c);
00155 } else {
00156 (void) new (home) Eq<Val,P,N>(home,x,y,c);
00157 }
00158 return ES_OK;
00159 }
00160
00161
00162 template <class Val, class P, class N>
00163 forceinline
00164 Eq<Val,P,N>::Eq(Space* home, bool share, Eq<Val,P,N>& p)
00165 : Lin<Val,P,N,PC_INT_BND>(home,share,p) {}
00166
00167 template <class Val, class P, class N>
00168 Actor*
00169 Eq<Val,P,N>::copy(Space* home, bool share) {
00170 return new (home) Eq<Val,P,N>(home,share,*this);
00171 }
00172
00173
00174 template <class Val, class P, class N>
00175 ExecStatus
00176 Eq<Val,P,N>::propagate(Space* home) {
00177
00178 Val sl = 0;
00179 Val su = 0;
00180
00181 bounds_p<Val,P>(this, x, c, sl, su);
00182 bounds_n<Val,N>(this, y, c, sl, su);
00183
00184 if ((IntView::pme(this) == ME_INT_VAL) && ((x.size() + y.size()) <= 1)) {
00185 if (x.size() == 1) {
00186 GECODE_ME_CHECK(x[0].eq(home,c)); return ES_SUBSUMED;
00187 }
00188 if (y.size() == 1) {
00189 GECODE_ME_CHECK(y[0].eq(home,-c)); return ES_SUBSUMED;
00190 }
00191 return (c == static_cast<Val>(0)) ? ES_SUBSUMED : 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
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
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
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
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) ? ES_SUBSUMED : ES_FIX;
00255 }
00256
00257
00258
00259
00260
00261
00262 template <class Val, class P, class N, class Ctrl>
00263 forceinline
00264 ReEq<Val,P,N,Ctrl>::ReEq(Space* home,
00265 ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b)
00266 : ReLin<Val,P,N,PC_INT_BND,Ctrl>(home,x,y,c,b) {}
00267
00268 template <class Val, class P, class N, class Ctrl>
00269 ExecStatus
00270 ReEq<Val,P,N,Ctrl>::post(Space* home,
00271 ViewArray<P>& x, ViewArray<N>& y, Val c, Ctrl b) {
00272 ViewArray<NoView> nva;
00273 if (y.size() == 0) {
00274 (void) new (home) ReEq<Val,P,NoView,Ctrl>(home,x,nva,c,b);
00275 } else if (x.size() == 0) {
00276 (void) new (home) ReEq<Val,N,NoView,Ctrl>(home,y,nva,-c,b);
00277 } else {
00278 (void) new (home) ReEq<Val,P,N,Ctrl>(home,x,y,c,b);
00279 }
00280 return ES_OK;
00281 }
00282
00283
00284 template <class Val, class P, class N, class Ctrl>
00285 forceinline
00286 ReEq<Val,P,N,Ctrl>::ReEq(Space* home, bool share, ReEq<Val,P,N,Ctrl>& p)
00287 : ReLin<Val,P,N,PC_INT_BND,Ctrl>(home,share,p) {}
00288
00289 template <class Val, class P, class N, class Ctrl>
00290 Actor*
00291 ReEq<Val,P,N,Ctrl>::copy(Space* home, bool share) {
00292 return new (home) ReEq<Val,P,N,Ctrl>(home,share,*this);
00293 }
00294
00295 template <class Val, class P, class N, class Ctrl>
00296 ExecStatus
00297 ReEq<Val,P,N,Ctrl>::propagate(Space* home) {
00298 if (b.zero())
00299 return (Nq<Val,P,N>::post(home,x,y,c) == ES_FAILED)
00300 ? ES_FAILED : ES_SUBSUMED;
00301 if (b.one())
00302 return (Eq<Val,P,N>::post(home,x,y,c) == ES_FAILED)
00303 ? ES_FAILED : ES_SUBSUMED;
00304
00305 Val sl = 0;
00306 Val su = 0;
00307
00308 bounds_p<Val,P>(this, x, c, sl, su);
00309 bounds_n<Val,N>(this, y, c, sl, su);
00310
00311 if ((-sl == c) && (-su == c)) {
00312 b.t_one_none(home); return ES_SUBSUMED;
00313 }
00314 if ((-sl > c) || (-su < c)) {
00315 b.t_zero_none(home); return ES_SUBSUMED;
00316 }
00317 return ES_FIX;
00318 }
00319
00320
00321
00322
00323
00324
00325
00326 template <class Val, class P, class N>
00327 forceinline
00328 Nq<Val,P,N>::Nq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c)
00329 : Lin<Val,P,N,PC_INT_VAL>(home,x,y,c) {}
00330
00331 template <class Val, class P, class N>
00332 ExecStatus
00333 Nq<Val,P,N>::post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c) {
00334 ViewArray<NoView> nva;
00335 if (y.size() == 0) {
00336 (void) new (home) Nq<Val,P,NoView>(home,x,nva,c);
00337 } else if (x.size() == 0) {
00338 (void) new (home) Nq<Val,N,NoView>(home,y,nva,-c);
00339 } else {
00340 (void) new (home) Nq<Val,P,N>(home,x,y,c);
00341 }
00342 return ES_OK;
00343 }
00344
00345
00346 template <class Val, class P, class N>
00347 forceinline
00348 Nq<Val,P,N>::Nq(Space* home, bool share, Nq<Val,P,N>& p)
00349 : Lin<Val,P,N,PC_INT_VAL>(home,share,p) {}
00350
00351 template <class Val, class P, class N>
00352 Actor*
00353 Nq<Val,P,N>::copy(Space* home, bool share) {
00354 return new (home) Nq<Val,P,N>(home,share,*this);
00355 }
00356
00357
00358 template <class Val, class P, class N>
00359 ExecStatus
00360 Nq<Val,P,N>::propagate(Space* home) {
00361 for (int i = x.size(); i--; )
00362 if (x[i].assigned()) {
00363 c -= x[i].val(); x.move_lst(i);
00364 }
00365 for (int i = y.size(); i--; )
00366 if (y[i].assigned()) {
00367 c += y[i].val(); y.move_lst(i);
00368 }
00369 if (x.size() + y.size() <= 1) {
00370 if (x.size() == 1) {
00371 GECODE_ME_CHECK(x[0].nq(home,c)); return ES_SUBSUMED;
00372 }
00373 if (y.size() == 1) {
00374 GECODE_ME_CHECK(y[0].nq(home,-c)); return ES_SUBSUMED;
00375 }
00376 return (c == static_cast<Val>(0)) ? ES_FAILED : ES_SUBSUMED;
00377 }
00378 return ES_FIX;
00379 }
00380
00381
00382
00383
00384
00385
00386
00387 template <class Val, class P, class N>
00388 forceinline
00389 Lq<Val,P,N>::Lq(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c)
00390 : Lin<Val,P,N,PC_INT_BND>(home,x,y,c) {}
00391
00392 template <class Val, class P, class N>
00393 ExecStatus
00394 Lq<Val,P,N>::post(Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c) {
00395 ViewArray<NoView> nva;
00396 if (y.size() == 0) {
00397 (void) new (home) Lq<Val,P,NoView>(home,x,nva,c);
00398 } else if (x.size() == 0) {
00399 (void) new (home) Lq<Val,NoView,N>(home,nva,y,c);
00400 } else {
00401 (void) new (home) Lq<Val,P,N>(home,x,y,c);
00402 }
00403 return ES_OK;
00404 }
00405
00406
00407 template <class Val, class P, class N>
00408 forceinline
00409 Lq<Val,P,N>::Lq(Space* home, bool share, Lq<Val,P,N>& p)
00410 : Lin<Val,P,N,PC_INT_BND>(home,share,p) {}
00411
00412 template <class Val, class P, class N>
00413 Actor*
00414 Lq<Val,P,N>::copy(Space* home, bool share) {
00415 return new (home) Lq<Val,P,N>(home,share,*this);
00416 }
00417
00418
00419 template <class Val, class P, class N>
00420 ExecStatus
00421 Lq<Val,P,N>::propagate(Space* home) {
00422
00423 Val sl = 0;
00424
00425 if (IntView::pme(this) == ME_INT_VAL) {
00426 for (int i = x.size(); i--; ) {
00427 Val m = x[i].min();
00428 if (x[i].assigned()) {
00429 c -= m; x.move_lst(i);
00430 } else {
00431 sl -= m;
00432 }
00433 }
00434 for (int i = y.size(); i--; ) {
00435 Val m = y[i].max();
00436 if (y[i].assigned()) {
00437 c += m; y.move_lst(i);
00438 } else {
00439 sl += m;
00440 }
00441 }
00442 if ((x.size() + y.size()) <= 1) {
00443 if (x.size() == 1) {
00444 GECODE_ME_CHECK(x[0].lq(home,c));
00445 return ES_SUBSUMED;
00446 }
00447 if (y.size() == 1) {
00448 GECODE_ME_CHECK(y[0].gq(home,-c));
00449 return ES_SUBSUMED;
00450 }
00451 return (c >= static_cast<Val>(0)) ? ES_SUBSUMED : ES_FAILED;
00452 }
00453 } else {
00454 for (int i = x.size(); i--; )
00455 sl -= x[i].min();
00456 for (int i = y.size(); i--; )
00457 sl += y[i].max();
00458 }
00459
00460 sl += c;
00461
00462 ExecStatus es = ES_FIX;
00463 bool assigned = true;
00464 for (int i = x.size(); i--; ) {
00465 assert(!x[i].assigned());
00466 Val slx = sl + x[i].min();
00467 ModEvent me = x[i].lq(home,slx);
00468 if (me == ME_INT_FAILED)
00469 return ES_FAILED;
00470 if (me != ME_INT_VAL)
00471 assigned = false;
00472 if (me_modified(me) && (slx != x[i].max()))
00473 es = ES_NOFIX;
00474 }
00475
00476 for (int i = y.size(); i--; ) {
00477 assert(!y[i].assigned());
00478 Val sly = y[i].max() - sl;
00479 ModEvent me = y[i].gq(home,sly);
00480 if (me == ME_INT_FAILED)
00481 return ES_FAILED;
00482 if (me != ME_INT_VAL)
00483 assigned = false;
00484 if (me_modified(me) && (sly != y[i].min()))
00485 es = ES_NOFIX;
00486 }
00487 return assigned ? ES_SUBSUMED : es;
00488 }
00489
00490
00491
00492
00493
00494
00495 template <class Val, class P, class N>
00496 forceinline
00497 ReLq<Val,P,N>::ReLq
00498 (Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b)
00499 : ReLin<Val,P,N,PC_INT_BND,BoolView>(home,x,y,c,b) {}
00500
00501 template <class Val, class P, class N>
00502 ExecStatus
00503 ReLq<Val,P,N>::post
00504 (Space* home, ViewArray<P>& x, ViewArray<N>& y, Val c, BoolView b) {
00505 ViewArray<NoView> nva;
00506 if (y.size() == 0) {
00507 (void) new (home) ReLq<Val,P,NoView>(home,x,nva,c,b);
00508 } else if (x.size() == 0) {
00509 (void) new (home) ReLq<Val,NoView,N>(home,nva,y,c,b);
00510 } else {
00511 (void) new (home) ReLq<Val,P,N>(home,x,y,c,b);
00512 }
00513 return ES_OK;
00514 }
00515
00516
00517 template <class Val, class P, class N>
00518 forceinline
00519 ReLq<Val,P,N>::ReLq(Space* home, bool share, ReLq<Val,P,N>& p)
00520 : ReLin<Val,P,N,PC_INT_BND,BoolView>(home,share,p) {}
00521
00522 template <class Val, class P, class N>
00523 Actor*
00524 ReLq<Val,P,N>::copy(Space* home, bool share) {
00525 return new (home) ReLq<Val,P,N>(home,share,*this);
00526 }
00527
00528
00529 template <class Val, class P, class N>
00530 ExecStatus
00531 ReLq<Val,P,N>::propagate(Space* home) {
00532 if (b.zero())
00533 return (Lq<Val,N,P>::post(home,y,x,-c+1) == ES_FAILED)
00534 ? ES_FAILED : ES_SUBSUMED;
00535 if (b.one())
00536 return (Lq<Val,P,N>::post(home,x,y,c) == ES_FAILED)
00537 ? ES_FAILED : ES_SUBSUMED;
00538
00539
00540 Val sl = 0;
00541 Val su = 0;
00542
00543 bounds_p<Val,P>(this,x,c,sl,su);
00544 bounds_n<Val,N>(this,y,c,sl,su);
00545
00546 if (-sl > c) {
00547 b.t_zero_none(home); return ES_SUBSUMED;
00548 }
00549 if (-su <= c) {
00550 b.t_one_none(home); return ES_SUBSUMED;
00551 }
00552
00553 return ES_FIX;
00554 }
00555
00556 }}}
00557
00558
00559