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 #include "gecode/int/linear.hh"
00039
00040 namespace Gecode { namespace Int { namespace Arithmetic {
00041
00042
00043
00044
00045
00046 template <class Val, class VA, class VB, class VC, bool towardsMinInf>
00047 forceinline ExecStatus
00048 prop_div_plus_bnd(Space* home, Propagator* p, VA x0, VB x1, VC x2) {
00049 assert(pos(x0) && pos(x1) && !neg(x2));
00050 bool mod;
00051 do {
00052 mod = false;
00053 {
00054 ModEvent me;
00055 if (towardsMinInf)
00056 me = x2.lq(home,f_d_p<Val>(x0.max(),x1.min()));
00057 else
00058 me = x2.lq(home,c_d_p<Val>(x0.max(),x1.min()));
00059 if (me_failed(me)) return ES_FAILED;
00060 mod |= me_modified(me);
00061 }
00062 {
00063 ModEvent me;
00064 if (towardsMinInf)
00065 me = x2.gq(home,f_d_p<Val>(x0.min(),x1.max()));
00066 else
00067 me = x2.gq(home,c_d_p<Val>(x0.min(),x1.max()));
00068 if (me_failed(me)) return ES_FAILED;
00069 mod |= me_modified(me);
00070 }
00071 {
00072 ModEvent me;
00073 if (towardsMinInf)
00074 me = x0.le(home,m<Val>(x1.max(),
00075 static_cast<Val>(x2.max())+
00076 static_cast<Val>(1)));
00077 else
00078 me = x0.lq(home,m<Val>(x1.max(),x2.max()));
00079 if (me_failed(me)) return ES_FAILED;
00080 mod |= me_modified(me);
00081 }
00082 {
00083 ModEvent me;
00084 if (towardsMinInf)
00085 me = x0.gq(home,m<Val>(x1.min(),x2.min()));
00086 else
00087 me = x0.gr(home,m<Val>(x1.min(),
00088 static_cast<Val>(x2.min())-
00089 static_cast<Val>(1)));
00090 if (me_failed(me)) return ES_FAILED;
00091 mod |= me_modified(me);
00092 }
00093 {
00094 if (x2.min() > 0) {
00095 ModEvent me;
00096 if (towardsMinInf)
00097 me = x1.lq(home,f_d_p<Val>(x0.max(),x2.min()));
00098 else if (x2.min() != 1) {
00099 me = x1.lq(home,c_d_p<Val>(x0.max(),
00100 static_cast<Val>(x2.min())-
00101 static_cast<Val>(1)));
00102 } else
00103 me = ME_INT_NONE;
00104 if (me_failed(me)) return ES_FAILED;
00105 mod |= me_modified(me);
00106 }
00107 }
00108 {
00109 ModEvent me;
00110 if (towardsMinInf)
00111 me = x1.gq(home,c_d_p<Val>(x0.min(),
00112 static_cast<Val>(x2.max())+static_cast<Val>(1)));
00113 else
00114 me = x1.gq(home,f_d_p<Val>(x0.min(),
00115 static_cast<Val>(x2.max())+static_cast<Val>(1)));
00116 if (me_failed(me)) return ES_FAILED;
00117 mod |= me_modified(me);
00118 }
00119 } while (mod);
00120 return x0.assigned() && x1.assigned() ?
00121 ES_SUBSUMED(p,sizeof(*p)) : ES_FIX;
00122 }
00123
00124 template <class Val, class VA, class VB, class VC, bool towardsMinInf>
00125 forceinline
00126 DivPlusBnd<Val,VA,VB,VC,towardsMinInf>
00127 ::DivPlusBnd(Space* home, VA x0, VB x1, VC x2)
00128 : MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>
00129 (home,x0,x1,x2) {}
00130
00131 template <class Val, class VA, class VB, class VC, bool towardsMinInf>
00132 forceinline
00133 DivPlusBnd<Val,VA,VB,VC,towardsMinInf>
00134 ::DivPlusBnd(Space* home, bool share,
00135 DivPlusBnd<Val,VA,VB,VC,towardsMinInf>& p)
00136 : MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>
00137 (home,share,p) {}
00138
00139 template <class Val, class VA, class VB, class VC, bool towardsMinInf>
00140 Actor*
00141 DivPlusBnd<Val,VA,VB,VC,towardsMinInf>::copy(Space* home, bool share) {
00142 return new (home) DivPlusBnd<Val,VA,VB,VC,towardsMinInf>(home,
00143 share,*this);
00144 }
00145
00146 template <class Val, class VA, class VB, class VC, bool towardsMinInf>
00147 ExecStatus
00148 DivPlusBnd<Val,VA,VB,VC,towardsMinInf>
00149 ::propagate(Space* home, ModEventDelta) {
00150 return prop_div_plus_bnd<Val,VA,VB,VC,towardsMinInf>(home,this,x0,x1,x2);
00151 }
00152
00153 template <class Val, class VA, class VB, class VC, bool towardsMinInf>
00154 forceinline ExecStatus
00155 DivPlusBnd<Val,VA,VB,VC,towardsMinInf>
00156 ::post(Space* home, VA x0, VB x1, VC x2) {
00157 GECODE_ME_CHECK(x0.gr(home,0));
00158 GECODE_ME_CHECK(x1.gr(home,0));
00159 if (towardsMinInf) {
00160 GECODE_ME_CHECK(x2.gq(home,floor(static_cast<double>(x0.min()) /
00161 static_cast<double>(x1.max()))));
00162 } else {
00163 GECODE_ME_CHECK(x2.gq(home,ceil(static_cast<double>(x0.min()) /
00164 static_cast<double>(x1.max()))));
00165 }
00166 (void)
00167 new (home) DivPlusBnd<double,VA,VB,VC,towardsMinInf>(home,x0,x1,x2);
00168 return ES_OK;
00169 }
00170
00171 template <class Val, class VA, class VB, class VC, bool towardsMinInf>
00172 forceinline void
00173 DivPlusBnd<Val,VA,VB,VC,towardsMinInf>
00174 ::post(Space* home, Reflection::VarMap& vars,
00175 const Reflection::ActorSpec& spec) {
00176 spec.checkArity(3);
00177 VA x0(home, vars, spec[0]);
00178 VB x1(home, vars, spec[1]);
00179 VC x2(home, vars, spec[2]);
00180 (void) new (home) DivPlusBnd<Val,VA,VB,VC,towardsMinInf>(home,x0,x1,x2);
00181 }
00182
00183 template <class Val, class VA, class VB, class VC, bool towardsMinInf>
00184 Support::Symbol
00185 DivPlusBnd<Val,VA,VB,VC,towardsMinInf>::ati(void) {
00186 return Reflection::mangle<VA,VB,VC,Val>
00187 ("Gecode::Int::Arithmetic::DivPlusBnd",towardsMinInf);
00188 }
00189
00190 template <class Val, class VA, class VB, class VC, bool towardsMinInf>
00191 Reflection::ActorSpec
00192 DivPlusBnd<Val,VA,VB,VC,towardsMinInf>
00193 ::spec(const Space* home, Reflection::VarMap& m) const {
00194 return MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>
00195 ::spec(home, m, ati());
00196 }
00197
00198
00199
00200
00201
00202
00203 template <class View>
00204 forceinline
00205 DivBnd<View>::DivBnd(Space* home, View x0, View x1, View x2)
00206 : TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {}
00207
00208 template <class View>
00209 forceinline
00210 DivBnd<View>::DivBnd(Space* home, bool share, DivBnd<View>& p)
00211 : TernaryPropagator<View,PC_INT_BND>(home,share,p) {}
00212
00213 template <class View>
00214 Actor*
00215 DivBnd<View>::copy(Space* home, bool share) {
00216 return new (home) DivBnd<View>(home,share,*this);
00217 }
00218
00219 template <class View>
00220 ExecStatus
00221 DivBnd<View>::propagate(Space* home, ModEventDelta) {
00222 if (pos(x1)) {
00223 if (pos(x2) || pos(x0)) goto rewrite_ppp;
00224 if (neg(x2) || neg(x0)) goto rewrite_npn;
00225 goto prop_xpx;
00226 }
00227 if (neg(x1)) {
00228 if (neg(x2) || pos(x0)) goto rewrite_pnn;
00229 if (pos(x2) || neg(x0)) goto rewrite_nnp;
00230 goto prop_xnx;
00231 }
00232 if (pos(x2)) {
00233 if (pos(x0)) goto rewrite_ppp;
00234 if (neg(x0)) goto rewrite_nnp;
00235 goto prop_xxp;
00236 }
00237 if (neg(x2)) {
00238 if (pos(x0)) goto rewrite_pnn;
00239 if (neg(x0)) goto rewrite_npn;
00240 goto prop_xxn;
00241 }
00242 assert(any(x1) && any(x2));
00243
00244 GECODE_ME_CHECK(x0.le(home,std::max(m<double>(x1.max(),x2.max()+1),
00245 m<double>(x1.min(),x2.min()-1))));
00246 GECODE_ME_CHECK(x0.gq(home,std::min(m<double>(x1.min(),x2.max()+1),
00247 m<double>(x1.max(),x2.min()-1))));
00248
00249 return ES_NOFIX;
00250
00251 prop_xxp:
00252 assert(any(x0) && any(x1) && pos(x2));
00253
00254 GECODE_ME_CHECK(x0.le(home, m<double>(x1.max(),x2.max()+1)));
00255 GECODE_ME_CHECK(x0.gq(home, m<double>(x1.min(),x2.max()+1)));
00256
00257 if (pos(x0)) goto rewrite_ppp;
00258 if (neg(x0)) goto rewrite_nnp;
00259
00260 GECODE_ME_CHECK(x1.lq(home,f_d_p<double>(x0.max(),x2.min())));
00261 GECODE_ME_CHECK(x1.gq(home,c_d(x0.min(),x2.min())));
00262
00263 if (x0.assigned() && x1.assigned()) {
00264 GECODE_ME_CHECK(x2.eq(home,f_d(x0.val(),x1.val())));
00265 return ES_SUBSUMED(this,sizeof(*this));
00266 }
00267
00268 return ES_NOFIX;
00269 prop_xpx:
00270 assert(any(x0) && pos(x1) && any(x2));
00271
00272 GECODE_ME_CHECK(x0.le(home, m<double>(x1.max(),x2.max()+1)));
00273 GECODE_ME_CHECK(x0.gq(home, m<double>(x1.max(),x2.min()-1)));
00274
00275 if (pos(x0)) goto rewrite_ppp;
00276 if (neg(x0)) goto rewrite_npn;
00277
00278 GECODE_ME_CHECK(x2.lq(home,f_d(x0.max(),x1.min())));
00279 GECODE_ME_CHECK(x2.gq(home,f_d(x0.min(),x1.min())));
00280
00281 if (x0.assigned() && x1.assigned()) {
00282 GECODE_ME_CHECK(x2.eq(home,f_d(x0.val(),x1.val())));
00283 return ES_SUBSUMED(this,sizeof(*this));
00284 }
00285
00286 return ES_NOFIX;
00287
00288 prop_xxn:
00289 assert(any(x0) && any(x1) && neg(x2));
00290
00291 GECODE_ME_CHECK(x0.le(home, m<double>(x1.min(),x2.min()-1)));
00292 GECODE_ME_CHECK(x0.gq(home, m<double>(x1.max(),x2.min()-1)));
00293
00294 if (pos(x0)) goto rewrite_pnn;
00295 if (neg(x0)) goto rewrite_npn;
00296
00297 if (x2.max() != -1)
00298 GECODE_ME_CHECK(x1.lq(home,c_d(x0.min(),x2.max()+1)));
00299 if (x2.max() != -1)
00300 GECODE_ME_CHECK(x1.gq(home,c_d(x0.max(),x2.max()+1)));
00301
00302 if (x0.assigned() && x1.assigned()) {
00303 GECODE_ME_CHECK(x2.eq(home,f_d(x0.val(),x1.val())));
00304 return ES_SUBSUMED(this,sizeof(*this));
00305 }
00306 return ES_NOFIX;
00307
00308 prop_xnx:
00309 assert(any(x0) && neg(x1) && any(x2));
00310
00311 GECODE_ME_CHECK(x0.le(home, m<double>(x1.min(),x2.min()-1)));
00312 GECODE_ME_CHECK(x0.gq(home, m<double>(x1.min(),x2.max()+1)));
00313
00314 if (pos(x0)) goto rewrite_pnn;
00315 if (neg(x0)) goto rewrite_nnp;
00316
00317 GECODE_ME_CHECK(x2.lq(home,f_d(x0.min(),x1.max())));
00318 GECODE_ME_CHECK(x2.gq(home,f_d(x0.max(),x1.max())));
00319
00320 if (x0.assigned() && x1.assigned()) {
00321 GECODE_ME_CHECK(x2.eq(home,f_d(x0.val(),x1.val())));
00322 return ES_SUBSUMED(this,sizeof(*this));
00323 }
00324 return ES_NOFIX;
00325
00326 rewrite_ppp:
00327 GECODE_REWRITE(this,(DivPlusBnd<double,IntView,IntView,IntView>
00328 ::post(home,x0,x1,x2)));
00329 rewrite_nnp:
00330 GECODE_REWRITE(this,(DivPlusBnd<double,MinusView,MinusView,IntView>
00331 ::post(home,x0,x1,x2)));
00332 rewrite_pnn:
00333 GECODE_REWRITE(this,(DivPlusBnd<double,IntView,MinusView,MinusView,false>
00334 ::post(home,x0,x1,x2)));
00335 rewrite_npn:
00336 GECODE_REWRITE(this,(DivPlusBnd<double,MinusView,IntView,MinusView,false>
00337 ::post(home,x0,x1,x2)));
00338 }
00339
00340 template <class View>
00341 ExecStatus
00342 DivBnd<View>::post(Space* home, View x0, View x1, View x2) {
00343 GECODE_ME_CHECK(x1.nq(home, 0));
00344 if (pos(x0)) {
00345 if (pos(x1) || pos(x2)) goto post_ppp;
00346 if (neg(x1) || neg(x2)) goto post_pnn;
00347 } else if (neg(x0)) {
00348 if (neg(x1) || pos(x2)) goto post_nnp;
00349 if (pos(x1) || neg(x2)) goto post_npn;
00350 } else if (pos(x1)) {
00351 if (pos(x2)) goto post_ppp;
00352 if (neg(x2)) goto post_npn;
00353 } else if (neg(x1)) {
00354 if (pos(x2)) goto post_nnp;
00355 if (neg(x2)) goto post_pnn;
00356 }
00357 (void) new (home) DivBnd<View>(home,x0,x1,x2);
00358 return ES_OK;
00359
00360 post_ppp:
00361 return DivPlusBnd<double,IntView,IntView,IntView>::post(home,x0,x1,x2);
00362 post_nnp:
00363 return DivPlusBnd<double,MinusView,MinusView,IntView>::post(home,x0,x1,x2);
00364 post_pnn:
00365 return DivPlusBnd<double,IntView,MinusView,MinusView,false>::post(home,x0,x1,x2);
00366 post_npn:
00367 return DivPlusBnd<double,MinusView,IntView,MinusView,false>::post(home,x0,x1,x2);
00368 }
00369
00370 template <class View>
00371 forceinline void
00372 DivBnd<View>::post(Space* home, Reflection::VarMap& vars,
00373 const Reflection::ActorSpec& spec) {
00374 spec.checkArity(3);
00375 View x0(home, vars, spec[0]);
00376 View x1(home, vars, spec[1]);
00377 View x2(home, vars, spec[2]);
00378 (void) new (home) DivBnd<View>(home,x0,x1,x2);
00379 }
00380
00381 template <class View>
00382 Support::Symbol
00383 DivBnd<View>::ati(void) {
00384 return Reflection::mangle<View>("Gecode::Int::Arithmetic::DivBnd");
00385 }
00386
00387 template <class View>
00388 Reflection::ActorSpec
00389 DivBnd<View>::spec(const Space* home, Reflection::VarMap& m) const {
00390 return TernaryPropagator<View,PC_INT_BND>::spec(home, m, ati());
00391 }
00392
00393
00394
00395
00396
00397
00398 template <class View>
00399 forceinline
00400 DivMod<View>::DivMod(Space* home, View x0, View x1)
00401 : BinaryPropagator<View,PC_INT_BND>(home,x0,x1) {}
00402
00403 template <class View>
00404 forceinline ExecStatus
00405 DivMod<View>::post(Space* home, View x0, View x1) {
00406 GECODE_ME_CHECK(x0.nq(home,0));
00407 (void) new (home) DivMod<View>(home,x0,x1);
00408 return ES_OK;
00409 }
00410
00411 template <class View>
00412 forceinline void
00413 DivMod<View>::post(Space* home, Reflection::VarMap& vars,
00414 const Reflection::ActorSpec& spec) {
00415 spec.checkArity(2);
00416 View x0(home, vars, spec[0]);
00417 View x1(home, vars, spec[1]);
00418 (void) new (home) DivMod<View>(home,x0,x1);
00419 }
00420
00421 template <class View>
00422 forceinline
00423 DivMod<View>::DivMod(Space* home, bool share,
00424 DivMod<View>& p)
00425 : BinaryPropagator<View,PC_INT_BND>(home,share,p) {}
00426
00427 template <class View>
00428 Actor*
00429 DivMod<View>::copy(Space* home, bool share) {
00430 return new (home) DivMod<View>(home,share,*this);
00431 }
00432
00433 template <class View>
00434 ExecStatus
00435 DivMod<View>::propagate(Space* home, ModEventDelta) {
00436 bool signIsSame;
00437 do {
00438 signIsSame = true;
00439
00440 if (x0.min() > 0) {
00441 GECODE_ME_CHECK(x1.gq(home, 0));
00442 } else if (x0.max() < 0) {
00443 GECODE_ME_CHECK(x1.lq(home, 0));
00444 } else if (x1.min() > 0) {
00445 GECODE_ME_CHECK(x0.gr(home, 0));
00446 } else if (x1.max() < 0) {
00447 GECODE_ME_CHECK(x0.le(home, 0));
00448 } else {
00449 signIsSame = false;
00450 }
00451
00452
00453 int x0max = std::max(x0.max(),std::max(-x0.max(),
00454 std::max(x0.min(),-x0.min())));
00455 GECODE_ME_CHECK(x1.le(home, x0max));
00456 GECODE_ME_CHECK(x1.gr(home, -x0max));
00457
00458 if (x0.min() > 0) {
00459 int min = std::min(x1.min() < 0 ? -x1.min():x1.min(),
00460 x1.max() < 0 ? -x1.max():x1.max());
00461 GECODE_ME_CHECK(x0.gr(home,min));
00462 } else if (x0.max() < 0) {
00463 int min = std::min(x1.min() < 0 ? -x1.min():x1.min(),
00464 x1.max() < 0 ? -x1.max():x1.max());
00465 GECODE_ME_CHECK(x0.le(home,-min));
00466 }
00467 } while (!signIsSame &&
00468 (x0.min() > 0 || x0.max() < 0 || x1.min() > 0 || x1.max() < 0));
00469
00470 if (signIsSame) {
00471 int maxx1 = std::max(x1.min() < 0 ? -x1.min():x1.min(),
00472 x1.max() < 0 ? -x1.max():x1.max());
00473 int minx0 = std::min(x0.min() < 0 ? -x0.min():x0.min(),
00474 x0.max() < 0 ? -x0.max():x0.max());
00475 if (maxx1 < minx0) {
00476 return ES_SUBSUMED(this,home);
00477 }
00478 }
00479 return ES_FIX;
00480 }
00481
00482 template <class View>
00483 Support::Symbol
00484 DivMod<View>::ati(void) {
00485 return Reflection::mangle<View>("Gecode::Int::Arithmetic::DivMod");
00486 }
00487
00488 template <class View>
00489 Reflection::ActorSpec
00490 DivMod<View>::spec(const Space* home, Reflection::VarMap& m) const {
00491 return BinaryPropagator<View,PC_INT_BND>::spec(home, m, ati());
00492 }
00493
00494 }}}
00495
00496