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