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