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 size_t
00135 SquarePlus<VA,VB>::dispose(Space* home) {
00136 assert(!home->failed());
00137 x0.cancel(home,this,PC_INT_BND);
00138 x1.cancel(home,this,PC_INT_BND);
00139 (void) Propagator::dispose(home);
00140 return sizeof(*this);
00141 }
00142
00143
00144
00145
00146
00147
00148
00149 template <class View>
00150 forceinline
00151 Square<View>::Square(Space* home, View x0, View x1)
00152 : BinaryPropagator<View,PC_INT_BND>(home,x0,x1) {}
00153
00154 template <class View>
00155 forceinline ExecStatus
00156 Square<View>::post(Space* home, View x0, View x1) {
00157 GECODE_ME_CHECK(x1.gq(home,0));
00158 GECODE_ME_CHECK(x0.lq(home,floor(sqrt(static_cast<double>
00159 (Limits::Int::int_max)))));
00160
00161
00162 if (x0.min() >= 0)
00163 return SquarePlus<IntView,IntView>::post(home,x0,x1);
00164 if (x0.max() <= 0)
00165 return SquarePlus<MinusView,IntView>::post(home,x0,x1);
00166 (void) new (home) Square<View>(home,x0,x1);
00167 return ES_OK;
00168 }
00169
00170 template <class View>
00171 forceinline
00172 Square<View>::Square(Space* home, bool share, Square<View>& p)
00173 : BinaryPropagator<View,PC_INT_BND>(home,share,p) {}
00174
00175 template <class View>
00176 Actor*
00177 Square<View>::copy(Space* home, bool share) {
00178 return new (home) Square<View>(home,share,*this);
00179 }
00180
00181 template <class View>
00182 PropCost
00183 Square<View>::cost(void) const {
00184 return PC_BINARY_HI;
00185 }
00186
00187 template <class View>
00188 ExecStatus
00189 Square<View>::propagate(Space* home) {
00190
00191 assert(x1.min() >= 0);
00192 if (x0.min() >= 0)
00193 return (SquarePlus<IntView,IntView>::post(home,x0,x1)
00194 == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00195 if (x0.max() <= 0)
00196 return (SquarePlus<MinusView,IntView>::post(home,x0,x1)
00197 == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00198
00199 GECODE_ME_CHECK(x1.lq(home,std::max(x0.min()*x0.min(),
00200 x0.max()*x0.max())));
00201
00202 int s = static_cast<int>(floor(sqrt(static_cast<double>(x1.max()))));
00203
00204 GECODE_ME_CHECK(x0.gq(home,-s));
00205 GECODE_ME_CHECK(x0.lq(home,s));
00206
00207 if (x0.assigned() && x1.assigned())
00208 return (x0.val()*x0.val() == x1.val()) ? ES_SUBSUMED : ES_FAILED;
00209
00210 return ES_NOFIX;
00211 }
00212
00213
00214
00215
00216
00217
00218 template <class VA, class VB, class VC>
00219 inline
00220 MultPlus<VA,VB,VC>::MultPlus(Space* home, VA y0, VB y1, VC y2)
00221 : Propagator(home), x0(y0), x1(y1), x2(y2) {
00222 x0.subscribe(home,this,PC_INT_BND);
00223 x1.subscribe(home,this,PC_INT_BND);
00224 x2.subscribe(home,this,PC_INT_BND);
00225 }
00226
00227 template <class VA, class VB, class VC>
00228 inline ExecStatus
00229 MultPlus<VA,VB,VC>::post(Space* home, VA x0, VB x1, VC x2) {
00230 GECODE_ME_CHECK(x0.gr(home,0));
00231 GECODE_ME_CHECK(x1.gr(home,0));
00232 GECODE_ME_CHECK(x2.gr(home,0));
00233 (void) new (home) MultPlus<VA,VB,VC>(home,x0,x1,x2);
00234 return ES_OK;
00235 }
00236
00237 template <class VA, class VB, class VC>
00238 forceinline
00239 MultPlus<VA,VB,VC>::MultPlus(Space* home, bool share, MultPlus<VA,VB,VC>& p)
00240 : Propagator(home,share,p) {
00241 x0.update(home,share,p.x0);
00242 x1.update(home,share,p.x1);
00243 x2.update(home,share,p.x2);
00244 }
00245
00246 template <class VA, class VB, class VC>
00247 Actor*
00248 MultPlus<VA,VB,VC>::copy(Space* home, bool share) {
00249 return new (home) MultPlus<VA,VB,VC>(home,share,*this);
00250 }
00251
00252 template <class VA, class VB, class VC>
00253 PropCost
00254 MultPlus<VA,VB,VC>::cost(void) const {
00255 return PC_TERNARY_HI;
00256 }
00257
00258 template <class VA, class VB, class VC>
00259 ExecStatus
00260 MultPlus<VA,VB,VC>::propagate(Space* home) {
00261 assert(p(x0) && p(x1) && p(x2));
00262 bool mod;
00263 do {
00264 mod = false;
00265 GECODE_CM(x2.lq(home,m(x0.max(),x1.max())));
00266 GECODE_CM(x2.gq(home,m(x0.min(),x1.min())));
00267 GECODE_CM(x0.lq(home,f_d(x2.max(),x1.min())));
00268 GECODE_CM(x0.gq(home,c_d(x2.min(),x1.max())));
00269 GECODE_CM(x1.lq(home,f_d(x2.max(),x0.min())));
00270 GECODE_CM(x1.gq(home,c_d(x2.min(),x0.max())));
00271 } while (mod);
00272 return x0.assigned() && x1.assigned() ? ES_SUBSUMED : ES_FIX;
00273 }
00274
00275 template <class VA, class VB, class VC>
00276 size_t
00277 MultPlus<VA,VB,VC>::dispose(Space* home) {
00278 assert(!home->failed());
00279 x0.cancel(home,this,PC_INT_BND);
00280 x1.cancel(home,this,PC_INT_BND);
00281 x2.cancel(home,this,PC_INT_BND);
00282 (void) Propagator::dispose(home);
00283 return sizeof(*this);
00284 }
00285
00286
00287
00288
00289
00290
00291
00292 template <class View>
00293 forceinline
00294 Mult<View>::Mult(Space* home, View x0, View x1, View x2)
00295 : TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {}
00296
00297 template <class View>
00298 forceinline
00299 Mult<View>::Mult(Space* home, bool share, Mult<View>& p)
00300 : TernaryPropagator<View,PC_INT_BND>(home,share,p) {}
00301
00302 template <class View>
00303 Actor*
00304 Mult<View>::copy(Space* home, bool share) {
00305 return new (home) Mult<View>(home,share,*this);
00306 }
00307
00308 template <class View>
00309 PropCost
00310 Mult<View>::cost(void) const {
00311 return PC_TERNARY_HI;
00312 }
00313
00314 template <class View>
00315 ExecStatus
00316 Mult<View>::propagate(Space* home) {
00317 if (p(x0)) {
00318 if (p(x1) || p(x2)) goto rewrite_ppp;
00319 if (n(x1) || n(x2)) goto rewrite_pnn;
00320 goto prop_pxx;
00321 }
00322 if (n(x0)) {
00323 if (n(x1) || p(x2)) goto rewrite_nnp;
00324 if (p(x1) || n(x2)) goto rewrite_npn;
00325 goto prop_nxx;
00326 }
00327 if (p(x1)) {
00328 if (p(x2)) goto rewrite_ppp;
00329 if (n(x2)) goto rewrite_npn;
00330 goto prop_xpx;
00331 }
00332 if (n(x1)) {
00333 if (p(x2)) goto rewrite_nnp;
00334 if (n(x2)) goto rewrite_pnn;
00335 goto prop_xnx;
00336 }
00337
00338 assert(x(x0) && x(x1));
00339 GECODE_ME_CHECK(x2.lq(home,std::max(m(x0.max(),x1.max()),
00340 m(x0.min(),x1.min()))));
00341 GECODE_ME_CHECK(x2.gq(home,std::min(m(x0.min(),x1.max()),
00342 m(x0.max(),x1.min()))));
00343
00344 if (x0.assigned()) {
00345 assert((x0.val() == 0) && (x2.val() == 0));
00346 return ES_SUBSUMED;
00347 }
00348
00349 if (x1.assigned()) {
00350 assert((x1.val() == 0) && (x2.val() == 0));
00351 return ES_SUBSUMED;
00352 }
00353
00354 return ES_NOFIX;
00355
00356 prop_xpx:
00357 std::swap(x0,x1);
00358 prop_pxx:
00359 assert(p(x0) && x(x1) && x(x2));
00360
00361 GECODE_ME_CHECK(x2.lq(home,m(x0.max(),x1.max())));
00362 GECODE_ME_CHECK(x2.gq(home,m(x0.max(),x1.min())));
00363
00364 if (p(x2)) goto rewrite_ppp;
00365 if (n(x2)) goto rewrite_pnn;
00366
00367 GECODE_ME_CHECK(x1.lq(home,f_d(x2.max(),x0.min())));
00368 GECODE_ME_CHECK(x1.gq(home,c_d(x2.min(),x0.min())));
00369
00370 if (x0.assigned() && x1.assigned()) {
00371 GECODE_ME_CHECK(x2.eq(home,m(x0.val(),x1.val())));
00372 return ES_SUBSUMED;
00373 }
00374
00375 return ES_NOFIX;
00376
00377 prop_xnx:
00378 std::swap(x0,x1);
00379 prop_nxx:
00380 assert(n(x0) && x(x1) && x(x2));
00381
00382 GECODE_ME_CHECK(x2.lq(home,m(x0.min(),x1.min())));
00383 GECODE_ME_CHECK(x2.gq(home,m(x0.min(),x1.max())));
00384
00385 if (p(x2)) goto rewrite_nnp;
00386 if (n(x2)) goto rewrite_npn;
00387
00388 GECODE_ME_CHECK(x1.lq(home,f_d(x2.min(),x0.max())));
00389 GECODE_ME_CHECK(x1.gq(home,c_d(x2.max(),x0.max())));
00390
00391 if (x0.assigned() && x1.assigned()) {
00392 GECODE_ME_CHECK(x2.eq(home,m(x0.val(),x1.val())));
00393 return ES_SUBSUMED;
00394 }
00395
00396 return ES_NOFIX;
00397
00398 rewrite_ppp:
00399 return (MultPlus<IntView,IntView,IntView>::post(home,x0,x1,x2)
00400 == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00401
00402 rewrite_nnp:
00403 return (MultPlus<MinusView,MinusView,IntView>::post(home,x0,x1,x2)
00404 == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00405
00406 rewrite_pnn:
00407 std::swap(x0,x1);
00408 rewrite_npn:
00409 return (MultPlus<MinusView,IntView,MinusView>::post(home,x0,x1,x2)
00410 == ES_FAILED) ? ES_FAILED : ES_SUBSUMED;
00411
00412 }
00413
00414 template <class View>
00415 ExecStatus
00416 Mult<View>::post(Space* home, View x0, View x1, View x2) {
00417 if (same(x0,x1))
00418 return Square<View>::post(home,x0,x2);
00419 if (p(x0)) {
00420 if (p(x1) || p(x2)) goto post_ppp;
00421 if (n(x1) || n(x2)) goto post_pnn;
00422 } else if (n(x0)) {
00423 if (n(x1) || p(x2)) goto post_nnp;
00424 if (p(x1) || n(x2)) goto post_npn;
00425 } else if (p(x1)) {
00426 if (p(x2)) goto post_ppp;
00427 if (n(x2)) goto post_npn;
00428 } else if (n(x1)) {
00429 if (p(x2)) goto post_nnp;
00430 if (n(x2)) goto post_pnn;
00431 }
00432 (void) new (home) Mult<View>(home,x0,x1,x2);
00433 return ES_OK;
00434
00435 post_ppp:
00436 return MultPlus<IntView,IntView,IntView>::post(home,x0,x1,x2);
00437 post_nnp:
00438 return MultPlus<MinusView,MinusView,IntView>::post(home,x0,x1,x2);
00439 post_pnn:
00440 std::swap(x0,x1);
00441 post_npn:
00442 return MultPlus<MinusView,IntView,MinusView>::post(home,x0,x1,x2);
00443 }
00444
00445
00446 #undef GECODE_CM
00447
00448 }}}
00449
00450
00451