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