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 namespace Gecode { namespace Int { namespace Linear {
00039
00040
00041
00042
00043
00044 template<class Val, class A, class B, PropCond pc>
00045 forceinline
00046 LinBin<Val,A,B,pc>::LinBin(Home home, A y0, B y1, Val c0)
00047 : Propagator(home), x0(y0), x1(y1), c(c0) {
00048 x0.subscribe(home,*this,pc);
00049 x1.subscribe(home,*this,pc);
00050 }
00051
00052 template<class Val, class A, class B, PropCond pc>
00053 forceinline
00054 LinBin<Val,A,B,pc>::LinBin(Space& home, bool share, LinBin<Val,A,B,pc>& p)
00055 : Propagator(home,share,p), c(p.c) {
00056 x0.update(home,share,p.x0);
00057 x1.update(home,share,p.x1);
00058 }
00059
00060 template<class Val, class A, class B, PropCond pc>
00061 forceinline
00062 LinBin<Val,A,B,pc>::LinBin(Space& home, bool share, Propagator& p,
00063 A y0, B y1, Val c0)
00064 : Propagator(home,share,p), c(c0) {
00065 x0.update(home,share,y0);
00066 x1.update(home,share,y1);
00067 }
00068
00069 template<class Val, class A, class B, PropCond pc>
00070 PropCost
00071 LinBin<Val,A,B,pc>::cost(const Space&, const ModEventDelta&) const {
00072 return PropCost::binary(PropCost::LO);
00073 }
00074
00075 template<class Val, class A, class B, PropCond pc>
00076 forceinline size_t
00077 LinBin<Val,A,B,pc>::dispose(Space& home) {
00078 assert(!home.failed());
00079 x0.cancel(home,*this,pc);
00080 x1.cancel(home,*this,pc);
00081 (void) Propagator::dispose(home);
00082 return sizeof(*this);
00083 }
00084
00085
00086
00087
00088
00089
00090 template<class Val, class A, class B, PropCond pc, class Ctrl>
00091 forceinline
00092 ReLinBin<Val,A,B,pc,Ctrl>::ReLinBin(Home home, A y0, B y1, Val c0, Ctrl b0)
00093 : Propagator(home), x0(y0), x1(y1), c(c0), b(b0) {
00094 x0.subscribe(home,*this,pc);
00095 x1.subscribe(home,*this,pc);
00096 b.subscribe(home,*this,PC_INT_VAL);
00097 }
00098
00099 template<class Val, class A, class B, PropCond pc, class Ctrl>
00100 forceinline
00101 ReLinBin<Val,A,B,pc,Ctrl>::ReLinBin(Space& home, bool share,
00102 ReLinBin<Val,A,B,pc,Ctrl>& p)
00103 : Propagator(home,share,p), c(p.c) {
00104 x0.update(home,share,p.x0);
00105 x1.update(home,share,p.x1);
00106 b.update(home,share,p.b);
00107 }
00108
00109 template<class Val, class A, class B, PropCond pc, class Ctrl>
00110 PropCost
00111 ReLinBin<Val,A,B,pc,Ctrl>::cost(const Space&, const ModEventDelta&) const {
00112 return PropCost::binary(PropCost::LO);
00113 }
00114
00115 template<class Val, class A, class B, PropCond pc, class Ctrl>
00116 forceinline size_t
00117 ReLinBin<Val,A,B,pc,Ctrl>::dispose(Space& home) {
00118 assert(!home.failed());
00119 x0.cancel(home,*this,pc);
00120 x1.cancel(home,*this,pc);
00121 b.cancel(home,*this,PC_BOOL_VAL);
00122 (void) Propagator::dispose(home);
00123 return sizeof(*this);
00124 }
00125
00126
00127
00128
00129
00130
00131 template<class Val, class A, class B>
00132 forceinline
00133 EqBin<Val,A,B>::EqBin(Home home, A x0, B x1, Val c)
00134 : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
00135
00136 template<class Val, class A, class B>
00137 ExecStatus
00138 EqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) {
00139 (void) new (home) EqBin<Val,A,B>(home,x0,x1,c);
00140 return ES_OK;
00141 }
00142
00143
00144 template<class Val, class A, class B>
00145 forceinline
00146 EqBin<Val,A,B>::EqBin(Space& home, bool share, EqBin<Val,A,B>& p)
00147 : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
00148
00149 template<class Val, class A, class B>
00150 forceinline
00151 EqBin<Val,A,B>::EqBin(Space& home, bool share, Propagator& p,
00152 A x0, B x1, Val c)
00153 : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {}
00154
00155 template<class Val, class A, class B>
00156 Actor*
00157 EqBin<Val,A,B>::copy(Space& home, bool share) {
00158 return new (home) EqBin<Val,A,B>(home,share,*this);
00159 }
00160
00162 enum BinMod {
00163 BM_X0_MIN = 1<<0,
00164 BM_X0_MAX = 1<<1,
00165 BM_X1_MIN = 1<<2,
00166 BM_X1_MAX = 1<<3,
00167 BM_ALL = BM_X0_MIN|BM_X0_MAX|BM_X1_MIN|BM_X1_MAX
00168 };
00169
00170 #define GECODE_INT_PV(CASE,TELL,UPDATE) \
00171 if (bm & (CASE)) { \
00172 bm -= (CASE); ModEvent me = (TELL); \
00173 if (me_failed(me)) return ES_FAILED; \
00174 if (me_modified(me)) bm |= (UPDATE); \
00175 }
00176
00177 template<class Val, class A, class B>
00178 ExecStatus
00179 EqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) {
00180 int bm = BM_ALL;
00181 do {
00182 GECODE_INT_PV(BM_X0_MIN, x0.gq(home,c-x1.max()), BM_X1_MAX);
00183 GECODE_INT_PV(BM_X1_MIN, x1.gq(home,c-x0.max()), BM_X0_MAX);
00184 GECODE_INT_PV(BM_X0_MAX, x0.lq(home,c-x1.min()), BM_X1_MIN);
00185 GECODE_INT_PV(BM_X1_MAX, x1.lq(home,c-x0.min()), BM_X0_MIN);
00186 } while (bm);
00187 return x0.assigned() ? ES_SUBSUMED(*this,sizeof(*this)) : ES_FIX;
00188 }
00189
00190 #undef GECODE_INT_PV
00191
00192
00193
00194
00195
00196
00197
00198
00199
00200
00201 template<class Val, class A, class B, class Ctrl>
00202 forceinline
00203 ReEqBin<Val,A,B,Ctrl>::ReEqBin(Home home, A x0, B x1, Val c, Ctrl b)
00204 : ReLinBin<Val,A,B,PC_INT_BND,Ctrl>(home,x0,x1,c,b) {}
00205
00206 template<class Val, class A, class B, class Ctrl>
00207 ExecStatus
00208 ReEqBin<Val,A,B,Ctrl>::post(Home home, A x0, B x1, Val c, Ctrl b) {
00209 (void) new (home) ReEqBin<Val,A,B,Ctrl>(home,x0,x1,c,b);
00210 return ES_OK;
00211 }
00212
00213
00214 template<class Val, class A, class B, class Ctrl>
00215 forceinline
00216 ReEqBin<Val,A,B,Ctrl>::ReEqBin(Space& home, bool share,
00217 ReEqBin<Val,A,B,Ctrl>& p)
00218 : ReLinBin<Val,A,B,PC_INT_BND,Ctrl>(home,share,p) {}
00219
00220 template<class Val, class A, class B, class Ctrl>
00221 Actor*
00222 ReEqBin<Val,A,B,Ctrl>::copy(Space& home, bool share) {
00223 return new (home) ReEqBin<Val,A,B,Ctrl>(home,share,*this);
00224 }
00225
00226 template<class Val, class A, class B, class Ctrl>
00227 ExecStatus
00228 ReEqBin<Val,A,B,Ctrl>::propagate(Space& home, const ModEventDelta&) {
00229 if (b.zero())
00230 GECODE_REWRITE(*this,(NqBin<Val,A,B>::post(home(*this),x0,x1,c)));
00231 if (b.one())
00232 GECODE_REWRITE(*this,(EqBin<Val,A,B>::post(home(*this),x0,x1,c)));
00233 if ((x0.min() + x1.min() > c) || (x0.max() + x1.max() < c)) {
00234 GECODE_ME_CHECK(b.zero_none(home)); return ES_SUBSUMED(*this,home);
00235 }
00236 if (x0.assigned() && x1.assigned()) {
00237 assert(x0.val() + x1.val() == c);
00238 GECODE_ME_CHECK(b.one_none(home)); return ES_SUBSUMED(*this,home);
00239 }
00240 return ES_FIX;
00241 }
00242
00243
00244
00245
00246
00247
00248
00249
00250 template<class Val, class A, class B>
00251 forceinline
00252 NqBin<Val,A,B>::NqBin(Home home, A x0, B x1, Val c)
00253 : LinBin<Val,A,B,PC_INT_VAL>(home,x0,x1,c) {}
00254
00255 template<class Val, class A, class B>
00256 ExecStatus
00257 NqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) {
00258 (void) new (home) NqBin<Val,A,B>(home,x0,x1,c);
00259 return ES_OK;
00260 }
00261
00262
00263 template<class Val, class A, class B>
00264 forceinline
00265 NqBin<Val,A,B>::NqBin(Space& home, bool share, NqBin<Val,A,B>& p)
00266 : LinBin<Val,A,B,PC_INT_VAL>(home,share,p) {}
00267
00268 template<class Val, class A, class B>
00269 Actor*
00270 NqBin<Val,A,B>::copy(Space& home, bool share) {
00271 return new (home) NqBin<Val,A,B>(home,share,*this);
00272 }
00273
00274 template<class Val, class A, class B>
00275 forceinline
00276 NqBin<Val,A,B>::NqBin(Space& home, bool share, Propagator& p,
00277 A x0, B x1, Val c)
00278 : LinBin<Val,A,B,PC_INT_VAL>(home,share,p,x0,x1,c) {}
00279
00280
00281
00282 template<class Val, class A, class B>
00283 PropCost
00284 NqBin<Val,A,B>::cost(const Space&, const ModEventDelta&) const {
00285 return PropCost::unary(PropCost::LO);
00286 }
00287
00288 template<class Val, class A, class B>
00289 ExecStatus
00290 NqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) {
00291 if (x0.assigned()) {
00292 GECODE_ME_CHECK(x1.nq(home,c-x0.val()));
00293 } else {
00294 assert(x1.assigned());
00295 GECODE_ME_CHECK(x0.nq(home,c-x1.val()));
00296 }
00297 return ES_SUBSUMED(*this,home);
00298 }
00299
00300
00301
00302
00303
00304
00305
00306 template<class Val, class A, class B>
00307 forceinline
00308 LqBin<Val,A,B>::LqBin(Home home, A x0, B x1, Val c)
00309 : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
00310
00311 template<class Val, class A, class B>
00312 ExecStatus
00313 LqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) {
00314 (void) new (home) LqBin<Val,A,B>(home,x0,x1,c);
00315 return ES_OK;
00316 }
00317
00318
00319 template<class Val, class A, class B>
00320 forceinline
00321 LqBin<Val,A,B>::LqBin(Space& home, bool share, LqBin<Val,A,B>& p)
00322 : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
00323
00324 template<class Val, class A, class B>
00325 Actor*
00326 LqBin<Val,A,B>::copy(Space& home, bool share) {
00327 return new (home) LqBin<Val,A,B>(home,share,*this);
00328 }
00329
00330 template<class Val, class A, class B>
00331 forceinline
00332 LqBin<Val,A,B>::LqBin(Space& home, bool share, Propagator& p,
00333 A x0, B x1, Val c)
00334 : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {}
00335
00336 template<class Val, class A, class B>
00337 ExecStatus
00338 LqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) {
00339 GECODE_ME_CHECK(x0.lq(home,c-x1.min()));
00340 GECODE_ME_CHECK(x1.lq(home,c-x0.min()));
00341 return (x0.max()+x1.max() <= c) ? ES_SUBSUMED(*this,home) : ES_FIX;
00342 }
00343
00344
00345
00346
00347
00348
00349
00350
00351
00352 template<class Val, class A, class B>
00353 forceinline
00354 GqBin<Val,A,B>::GqBin(Home home, A x0, B x1, Val c)
00355 : LinBin<Val,A,B,PC_INT_BND>(home,x0,x1,c) {}
00356
00357 template<class Val, class A, class B>
00358 ExecStatus
00359 GqBin<Val,A,B>::post(Home home, A x0, B x1, Val c) {
00360 (void) new (home) GqBin<Val,A,B>(home,x0,x1,c);
00361 return ES_OK;
00362 }
00363
00364
00365 template<class Val, class A, class B>
00366 forceinline
00367 GqBin<Val,A,B>::GqBin(Space& home, bool share, GqBin<Val,A,B>& p)
00368 : LinBin<Val,A,B,PC_INT_BND>(home,share,p) {}
00369
00370 template<class Val, class A, class B>
00371 Actor*
00372 GqBin<Val,A,B>::copy(Space& home, bool share) {
00373 return new (home) GqBin<Val,A,B>(home,share,*this);
00374 }
00375
00376 template<class Val, class A, class B>
00377 forceinline
00378 GqBin<Val,A,B>::GqBin(Space& home, bool share, Propagator& p,
00379 A x0, B x1, Val c)
00380 : LinBin<Val,A,B,PC_INT_BND>(home,share,p,x0,x1,c) {}
00381
00382 template<class Val, class A, class B>
00383 ExecStatus
00384 GqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) {
00385 GECODE_ME_CHECK(x0.gq(home,c-x1.max()));
00386 GECODE_ME_CHECK(x1.gq(home,c-x0.max()));
00387 return (x0.min()+x1.min() >= c) ? ES_SUBSUMED(*this,home) : ES_FIX;
00388 }
00389
00390
00391
00392
00393
00394
00395
00396
00397
00398 template<class Val, class A, class B>
00399 forceinline
00400 ReLqBin<Val,A,B>::ReLqBin(Home home, A x0, B x1, Val c, BoolView b)
00401 : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,x0,x1,c,b) {}
00402
00403 template<class Val, class A, class B>
00404 ExecStatus
00405 ReLqBin<Val,A,B>::post(Home home, A x0, B x1, Val c, BoolView b) {
00406 (void) new (home) ReLqBin<Val,A,B>(home,x0,x1,c,b);
00407 return ES_OK;
00408 }
00409
00410
00411 template<class Val, class A, class B>
00412 forceinline
00413 ReLqBin<Val,A,B>::ReLqBin(Space& home, bool share, ReLqBin<Val,A,B>& p)
00414 : ReLinBin<Val,A,B,PC_INT_BND,BoolView>(home,share,p) {}
00415
00416 template<class Val, class A, class B>
00417 Actor*
00418 ReLqBin<Val,A,B>::copy(Space& home, bool share) {
00419 return new (home) ReLqBin<Val,A,B>(home,share,*this);
00420 }
00421
00422 template<class Val, class A, class B>
00423 ExecStatus
00424 ReLqBin<Val,A,B>::propagate(Space& home, const ModEventDelta&) {
00425 if (b.one())
00426 GECODE_REWRITE(*this,(LqBin<Val,A,B>::post(home(*this),x0,x1,c)));
00427 if (b.zero())
00428 GECODE_REWRITE(*this,(GqBin<Val,A,B>::post(home(*this),x0,x1,c+1)));
00429 if (x0.max() + x1.max() <= c) {
00430 GECODE_ME_CHECK(b.one_none(home)); return ES_SUBSUMED(*this,home);
00431 }
00432 if (x0.min() + x1.min() > c) {
00433 GECODE_ME_CHECK(b.zero_none(home)); return ES_SUBSUMED(*this,home);
00434 }
00435 return ES_FIX;
00436 }
00437
00438 }}}
00439
00440
00441