00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include <cmath>
00023
00024 namespace Gecode { namespace Int { namespace Arithmetic {
00025
00026
00027
00028
00029
00030
00032 forceinline double
00033 m(int a, int b) {
00034 return static_cast<double>(a)*static_cast<double>(b);
00035 }
00036
00038 forceinline int
00039 f_d(int x, int y) {
00040 return static_cast<int>(floor(static_cast<double>(x) /
00041 static_cast<double>(y)));
00042 }
00043
00045 forceinline int
00046 c_d(int x, int y) {
00047 return static_cast<int>(ceil(static_cast<double>(x) /
00048 static_cast<double>(y)));
00049 }
00050
00052 template <class View>
00053 forceinline bool
00054 p(const View& x) {
00055 return x.min() > 0;
00056 }
00058 template <class View>
00059 forceinline bool
00060 n(const View& x) {
00061 return x.max() < 0;
00062 }
00064 template <class View>
00065 forceinline bool
00066 x(const View& x) {
00067 return (x.min() <= 0) && (x.max() >= 0);
00068 }
00069
00070
00072 #define GECODE_CM(TELL) \
00073 { \
00074 ModEvent me = (TELL); \
00075 if (me_failed(me)) return ES_FAILED; \
00076 if (me_modified(me)) mod = true; \
00077 }
00078
00079
00080
00081
00082
00083
00084 template <class VA, class VB>
00085 forceinline
00086 SquarePlus<VA,VB>::SquarePlus(Space* home, VA y0, VB y1)
00087 : Propagator(home), x0(y0), x1(y1) {
00088 x0.subscribe(home,this,PC_INT_BND);
00089 x1.subscribe(home,this,PC_INT_BND);
00090 }
00091
00092 template <class VA, class VB>
00093 forceinline ExecStatus
00094 SquarePlus<VA,VB>::post(Space* home, VA x0, VB x1) {
00095 (void) new (home) SquarePlus<VA,VB>(home,x0,x1);
00096 return ES_OK;
00097 }
00098
00099 template <class VA, class VB>
00100 forceinline
00101 SquarePlus<VA,VB>::SquarePlus(Space* home, bool share, SquarePlus<VA,VB>& p)
00102 : Propagator(home,share,p) {
00103 x0.update(home,share,p.x0);
00104 x1.update(home,share,p.x1);
00105 }
00106
00107 template <class VA, class VB>
00108 Actor*
00109 SquarePlus<VA,VB>::copy(Space* home, bool share) {
00110 return new (home) SquarePlus<VA,VB>(home,share,*this);
00111 }
00112
00113 template <class VA, class VB>
00114 PropCost
00115 SquarePlus<VA,VB>::cost(void) const {
00116 return PC_TERNARY_HI;
00117 }
00118
00119 template <class VA, class VB>
00120 ExecStatus
00121 SquarePlus<VA,VB>::propagate(Space* home) {
00122 bool mod;
00123 do {
00124 mod = false;
00125 GECODE_CM(x0.lq(home,floor(sqrt(static_cast<double>(x1.max())))));
00126 GECODE_CM(x0.gq(home,ceil(sqrt(static_cast<double>(x1.min())))));
00127 GECODE_CM(x1.lq(home,x0.max()*x0.max()));
00128 GECODE_CM(x1.gq(home,x0.min()*x0.min()));
00129 } while (mod);
00130 return x0.assigned() ? ES_SUBSUMED : ES_FIX;
00131 }
00132
00133 template <class VA, class VB>
00134 SquarePlus<VA,VB>::~SquarePlus(void) {
00135 x0.cancel(this,PC_INT_BND);
00136 x1.cancel(this,PC_INT_BND);
00137 }
00138
00139
00140
00141
00142
00143
00144
00145 template <class View>
00146 forceinline
00147 Square<View>::Square(Space* home, View x0, View x1)
00148 : BinaryPropagator<View,PC_INT_BND>(home,x0,x1) {}
00149
00150 template <class View>
00151 forceinline ExecStatus
00152 Square<View>::post(Space* home, View x0, View x1) {
00153 GECODE_ME_CHECK(x1.gq(home,0));
00154 GECODE_ME_CHECK(x0.lq(home,floor(sqrt(static_cast<double>(Limits::Int::int_max)))));
00155 if (x0.min() >= 0)
00156 return SquarePlus<IntView,IntView>::post(home,x0,x1);
00157 if (x0.max() <= 0)
00158 return SquarePlus<MinusView,IntView>::post(home,x0,x1);
00159 (void) new (home) Square<View>(home,x0,x1);
00160 return ES_OK;
00161 }
00162
00163 template <class View>
00164 forceinline
00165 Square<View>::Square(Space* home, bool share, Square<View>& p)
00166 : BinaryPropagator<View,PC_INT_BND>(home,share,p) {}
00167
00168 template <class View>
00169 Actor*
00170 Square<View>::copy(Space* home, bool share) {
00171 return new (home) Square<View>(home,share,*this);
00172 }
00173
00174 template <class View>
00175 PropCost
00176 Square<View>::cost(void) const {
00177 return PC_BINARY_HI;
00178 }
00179
00180 template <class View>
00181 ExecStatus
00182 Square<View>::propagate(Space* home) {
00183
00184 assert(x1.min() >= 0);
00185 if (x0.min() >= 0)
00186 return (SquarePlus<IntView,IntView>::post(home,x0,x1)
00187 == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00188 if (x0.max() <= 0)
00189 return (SquarePlus<MinusView,IntView>::post(home,x0,x1)
00190 == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00191
00192 bool mod;
00193 do {
00194 mod = false;
00195 GECODE_CM(x1.lq(home,std::max(x0.min()*x0.min(),x0.max()*x0.max())));
00196 int s = static_cast<int>(floor(sqrt(static_cast<double>(x1.max()))));
00197 GECODE_CM(x0.gq(home,-s));
00198 GECODE_CM(x0.lq(home,s));
00199 } while (mod);
00200 return x0.assigned() && x1.assigned() ? ES_SUBSUMED : ES_FIX;
00201 }
00202
00203
00204
00205
00206
00207
00208 template <class VA, class VB, class VC>
00209 inline
00210 MultPlus<VA,VB,VC>::MultPlus(Space* home, VA y0, VB y1, VC y2)
00211 : Propagator(home), x0(y0), x1(y1), x2(y2) {
00212 x0.subscribe(home,this,PC_INT_BND);
00213 x1.subscribe(home,this,PC_INT_BND);
00214 x2.subscribe(home,this,PC_INT_BND);
00215 }
00216
00217 template <class VA, class VB, class VC>
00218 inline ExecStatus
00219 MultPlus<VA,VB,VC>::post(Space* home, VA x0, VB x1, VC x2) {
00220 GECODE_ME_CHECK(x0.gr(home,0));
00221 GECODE_ME_CHECK(x1.gr(home,0));
00222 GECODE_ME_CHECK(x2.gr(home,0));
00223 (void) new (home) MultPlus<VA,VB,VC>(home,x0,x1,x2);
00224 return ES_OK;
00225 }
00226
00227 template <class VA, class VB, class VC>
00228 forceinline
00229 MultPlus<VA,VB,VC>::MultPlus(Space* home, bool share, MultPlus<VA,VB,VC>& p)
00230 : Propagator(home,share,p) {
00231 x0.update(home,share,p.x0);
00232 x1.update(home,share,p.x1);
00233 x2.update(home,share,p.x2);
00234 }
00235
00236 template <class VA, class VB, class VC>
00237 Actor*
00238 MultPlus<VA,VB,VC>::copy(Space* home, bool share) {
00239 return new (home) MultPlus<VA,VB,VC>(home,share,*this);
00240 }
00241
00242 template <class VA, class VB, class VC>
00243 PropCost
00244 MultPlus<VA,VB,VC>::cost(void) const {
00245 return PC_TERNARY_HI;
00246 }
00247
00248 template <class VA, class VB, class VC>
00249 ExecStatus
00250 MultPlus<VA,VB,VC>::propagate(Space* home) {
00251 assert(p(x0) && p(x1) && p(x2));
00252 bool mod;
00253 do {
00254 mod = false;
00255 GECODE_CM(x2.lq(home,m(x0.max(),x1.max())));
00256 GECODE_CM(x2.gq(home,m(x0.min(),x1.min())));
00257 GECODE_CM(x0.lq(home,f_d(x2.max(),x1.min())));
00258 GECODE_CM(x0.gq(home,c_d(x2.min(),x1.max())));
00259 GECODE_CM(x1.lq(home,f_d(x2.max(),x0.min())));
00260 GECODE_CM(x1.gq(home,c_d(x2.min(),x0.max())));
00261 } while (mod);
00262 return x0.assigned() && x1.assigned() ? ES_SUBSUMED : ES_FIX;
00263 }
00264
00265 template <class VA, class VB, class VC>
00266 MultPlus<VA,VB,VC>::~MultPlus(void) {
00267 x0.cancel(this,PC_INT_BND);
00268 x1.cancel(this,PC_INT_BND);
00269 x2.cancel(this,PC_INT_BND);
00270 }
00271
00272
00273
00274
00275
00276
00277
00278 template <class View>
00279 forceinline
00280 Mult<View>::Mult(Space* home, View x0, View x1, View x2)
00281 : TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {}
00282
00283 template <class View>
00284 forceinline
00285 Mult<View>::Mult(Space* home, bool share, Mult<View>& p)
00286 : TernaryPropagator<View,PC_INT_BND>(home,share,p) {}
00287
00288 template <class View>
00289 Actor*
00290 Mult<View>::copy(Space* home, bool share) {
00291 return new (home) Mult<View>(home,share,*this);
00292 }
00293
00294 template <class View>
00295 PropCost
00296 Mult<View>::cost(void) const {
00297 return PC_TERNARY_HI;
00298 }
00299
00300 template <class View>
00301 ExecStatus
00302 Mult<View>::propagate(Space* home) {
00303 if (p(x0)) {
00304 if (p(x1) || p(x2)) goto rewrite_ppp;
00305 if (n(x1) || n(x2)) goto rewrite_pnn;
00306 goto prop_pxx;
00307 }
00308 if (n(x0)) {
00309 if (n(x1) || p(x2)) goto rewrite_nnp;
00310 if (p(x1) || n(x2)) goto rewrite_npn;
00311 goto prop_nxx;
00312 }
00313 if (p(x1)) {
00314 if (p(x2)) goto rewrite_ppp;
00315 if (n(x2)) goto rewrite_npn;
00316 goto prop_xpx;
00317 }
00318 if (n(x1)) {
00319 if (p(x2)) goto rewrite_nnp;
00320 if (n(x2)) goto rewrite_pnn;
00321 goto prop_xnx;
00322 }
00323
00324 assert(x(x0) && x(x1));
00325 GECODE_ME_CHECK(x2.lq(home,std::max(m(x0.max(),x1.max()),
00326 m(x0.min(),x1.min()))));
00327 GECODE_ME_CHECK(x2.gq(home,std::min(m(x0.min(),x1.max()),
00328 m(x0.max(),x1.min()))));
00329
00330 if (x0.assigned()) {
00331 assert((x0.val() == 0) && (x2.val() == 0));
00332 return ES_SUBSUMED;
00333 }
00334
00335 if (x1.assigned()) {
00336 assert((x1.val() == 0) && (x2.val() == 0));
00337 return ES_SUBSUMED;
00338 }
00339
00340 return ES_NOFIX;
00341
00342 prop_xpx:
00343 std::swap(x0,x1);
00344 prop_pxx:
00345 assert(p(x0) && x(x1) && x(x2));
00346
00347 GECODE_ME_CHECK(x2.lq(home,m(x0.max(),x1.max())));
00348 GECODE_ME_CHECK(x2.gq(home,m(x0.max(),x1.min())));
00349
00350 if (p(x2)) goto rewrite_ppp;
00351 if (n(x2)) goto rewrite_pnn;
00352
00353 GECODE_ME_CHECK(x1.lq(home,f_d(x2.max(),x0.min())));
00354 GECODE_ME_CHECK(x1.gq(home,c_d(x2.min(),x0.min())));
00355
00356 if (x0.assigned() && x1.assigned()) {
00357 GECODE_ME_CHECK(x2.eq(home,m(x0.val(),x1.val())));
00358 return ES_SUBSUMED;
00359 }
00360
00361 return ES_NOFIX;
00362
00363 prop_xnx:
00364 std::swap(x0,x1);
00365 prop_nxx:
00366 assert(n(x0) && x(x1) && x(x2));
00367
00368 GECODE_ME_CHECK(x2.lq(home,m(x0.min(),x1.min())));
00369 GECODE_ME_CHECK(x2.gq(home,m(x0.min(),x1.max())));
00370
00371 if (p(x2)) goto rewrite_nnp;
00372 if (n(x2)) goto rewrite_npn;
00373
00374 GECODE_ME_CHECK(x1.lq(home,f_d(x2.min(),x0.max())));
00375 GECODE_ME_CHECK(x1.gq(home,c_d(x2.max(),x0.max())));
00376
00377 if (x0.assigned() && x1.assigned()) {
00378 GECODE_ME_CHECK(x2.eq(home,m(x0.val(),x1.val())));
00379 return ES_SUBSUMED;
00380 }
00381
00382 return ES_NOFIX;
00383
00384 rewrite_ppp:
00385 return (MultPlus<IntView,IntView,IntView>::post(home,x0,x1,x2)
00386 == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00387
00388 rewrite_nnp:
00389 return (MultPlus<MinusView,MinusView,IntView>::post(home,x0,x1,x2)
00390 == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00391
00392 rewrite_pnn:
00393 std::swap(x0,x1);
00394 rewrite_npn:
00395 return (MultPlus<MinusView,IntView,MinusView>::post(home,x0,x1,x2)
00396 == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00397
00398 }
00399
00400 template <class View>
00401 ExecStatus
00402 Mult<View>::post(Space* home, View x0, View x1, View x2) {
00403 if (same(x0,x1))
00404 return Square<View>::post(home,x0,x2);
00405 if (p(x0)) {
00406 if (p(x1) || p(x2)) goto post_ppp;
00407 if (n(x1) || n(x2)) goto post_pnn;
00408 } else if (n(x0)) {
00409 if (n(x1) || p(x2)) goto post_nnp;
00410 if (p(x1) || n(x2)) goto post_npn;
00411 } else if (p(x1)) {
00412 if (p(x2)) goto post_ppp;
00413 if (n(x2)) goto post_npn;
00414 } else if (n(x1)) {
00415 if (p(x2)) goto post_nnp;
00416 if (n(x2)) goto post_pnn;
00417 }
00418 (void) new (home) Mult<View>(home,x0,x1,x2);
00419 return ES_OK;
00420
00421 post_ppp:
00422 return MultPlus<IntView,IntView,IntView>::post(home,x0,x1,x2);
00423 post_nnp:
00424 return MultPlus<MinusView,MinusView,IntView>::post(home,x0,x1,x2);
00425 post_pnn:
00426 std::swap(x0,x1);
00427 post_npn:
00428 return MultPlus<MinusView,IntView,MinusView>::post(home,x0,x1,x2);
00429 }
00430
00431
00432 #undef GECODE_CM
00433
00434 }}}
00435
00436
00437