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