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 #include <gecode/int/rel.hh>
00035
00036 #include <climits>
00037 #include <algorithm>
00038
00039 namespace Gecode { namespace Int { namespace Arithmetic {
00040
00041
00042
00043
00044
00045
00046 template<class Ops, bool minus>
00047 forceinline ExecStatus
00048 prop_nroot_plus_bnd(Space& home, IntView x0, IntView x1, const Ops& ops) {
00049 if (minus) {
00050 bool mod;
00051 do {
00052 mod = false;
00053 {
00054 ModEvent me = x1.gq(home,-ops.cnroot(-x0.min()));
00055 if (me_failed(me)) return ES_FAILED;
00056 mod |= me_modified(me);
00057 }
00058 {
00059 ModEvent me = x1.lq(home,-ops.cnroot(-x0.max()));
00060 if (me_failed(me)) return ES_FAILED;
00061 mod |= me_modified(me);
00062 }
00063 {
00064 ModEvent me = x0.gq(home,-ops.tpow(-x1.min()));
00065 if (me_failed(me)) return ES_FAILED;
00066 mod |= me_modified(me);
00067 }
00068 {
00069 ModEvent me = x0.lq(home,-(ops.tpow(-x1.max()-1)+1));
00070 if (me_failed(me)) return ES_FAILED;
00071 mod |= me_modified(me);
00072 }
00073 } while (mod);
00074 } else {
00075 bool mod;
00076 do {
00077 mod = false;
00078 {
00079 ModEvent me = x1.lq(home,ops.fnroot(x0.max()));
00080 if (me_failed(me)) return ES_FAILED;
00081 mod |= me_modified(me);
00082 }
00083 {
00084 ModEvent me = x1.gq(home,ops.fnroot(x0.min()));
00085 if (me_failed(me)) return ES_FAILED;
00086 mod |= me_modified(me);
00087 }
00088 {
00089 ModEvent me = x0.le(home,ops.tpow(x1.max()+1));
00090 if (me_failed(me)) return ES_FAILED;
00091 mod |= me_modified(me);
00092 }
00093 {
00094 ModEvent me = x0.gq(home,ops.tpow(x1.min()));
00095 if (me_failed(me)) return ES_FAILED;
00096 mod |= me_modified(me);
00097 }
00098 } while (mod);
00099 }
00100 return ES_OK;
00101 }
00102
00103 template<class Ops, bool minus>
00104 forceinline
00105 NrootPlusBnd<Ops,minus>::NrootPlusBnd(Home home, IntView x0, IntView x1,
00106 const Ops& o)
00107 : BinaryPropagator<IntView,PC_INT_BND>(home,x0,x1),
00108 ops(o) {}
00109
00110 template<class Ops, bool minus>
00111 forceinline ExecStatus
00112 NrootPlusBnd<Ops,minus>::post(Home home, IntView x0, IntView x1, Ops ops) {
00113 if (minus) {
00114 GECODE_ME_CHECK(x0.lq(home,0));
00115 GECODE_ME_CHECK(x1.lq(home,0));
00116 } else {
00117 GECODE_ME_CHECK(x0.gq(home,0));
00118 GECODE_ME_CHECK(x1.gq(home,0));
00119 }
00120 (void) new (home) NrootPlusBnd<Ops,minus>(home,x0,x1,ops);
00121 return ES_OK;
00122 }
00123
00124 template<class Ops, bool minus>
00125 forceinline
00126 NrootPlusBnd<Ops,minus>::NrootPlusBnd(Space& home,
00127 NrootPlusBnd<Ops,minus>& p)
00128 : BinaryPropagator<IntView,PC_INT_BND>(home,p),
00129 ops(p.ops) {}
00130
00131 template<class Ops, bool minus>
00132 Actor*
00133 NrootPlusBnd<Ops,minus>::copy(Space& home) {
00134 return new (home) NrootPlusBnd<Ops,minus>(home,*this);
00135 }
00136
00137 template<class Ops, bool minus>
00138 ExecStatus
00139 NrootPlusBnd<Ops,minus>::propagate(Space& home, const ModEventDelta&) {
00140 GECODE_ES_CHECK((prop_nroot_plus_bnd<Ops,minus>(home,x0,x1,ops)));
00141 return x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00142 }
00143
00144
00145
00146
00147
00148
00149
00150 template<class Ops>
00151 forceinline ExecStatus
00152 prop_nroot_bnd(Space& home, IntView x0, IntView x1, const Ops& ops) {
00153 assert((x0.min() < 0) && (x0.max() > 0));
00154 assert((x1.min() < 0) && (x1.max() > 0));
00155
00156 GECODE_ME_CHECK(x1.lq(home,ops.fnroot(x0.max())));
00157 GECODE_ME_CHECK(x1.gq(home,-ops.cnroot(-x0.min())));
00158 GECODE_ME_CHECK(x0.le(home,ops.tpow(x1.max()+1)));
00159 GECODE_ME_CHECK(x0.gq(home,ops.tpow(x1.min()-1)+1));
00160
00161 return ES_OK;
00162 }
00163
00164 template<class Ops>
00165 forceinline
00166 NrootBnd<Ops>::NrootBnd(Home home, IntView x0, IntView x1, const Ops& o)
00167 : BinaryPropagator<IntView,PC_INT_BND>(home,x0,x1),
00168 ops(o) {}
00169
00170 template<class Ops>
00171 forceinline ExecStatus
00172 NrootBnd<Ops>::post(Home home, IntView x0, IntView x1, Ops ops) {
00173 if (static_cast<unsigned int>(ops.exp()) >= sizeof(int) * CHAR_BIT) {
00174
00175 GECODE_ME_CHECK(x1.lq(home,1));
00176 GECODE_ME_CHECK(x1.gq(home,-2));
00177
00178 ops.exp(ops.even() ? 30 : 31);
00179 }
00180
00181 if (ops.exp() == 0) {
00182 GECODE_ME_CHECK(x1.eq(home,1));
00183 return ES_OK;
00184 } else if (ops.exp() == 1) {
00185 return Rel::EqBnd<IntView,IntView>::post(home,x0,x1);
00186 }
00187
00188 if (same(x0,x1)) {
00189 assert(ops.exp() > 1);
00190 GECODE_ME_CHECK(x0.lq(home,1));
00191 GECODE_ME_CHECK(x0.gq(home,ops.even() ? 0 : -2));
00192 return ES_OK;
00193 }
00194
00195
00196 GECODE_ME_CHECK(x1.lq(home,ops.fnroot(Limits::max)));
00197 GECODE_ME_CHECK(x1.gq(home,-ops.cnroot(-Limits::min)));
00198
00199 if (ops.even()) {
00200 GECODE_ME_CHECK(x0.gq(home,0));
00201 GECODE_ME_CHECK(x1.gq(home,0));
00202 }
00203
00204 if ((x0.min() >= 0) || (x1.min() >= 0))
00205 return NrootPlusBnd<Ops,false>::post(home,x0,x1,ops);
00206
00207 if ((x0.max() <= 0) || (x1.max() <= 0))
00208 return NrootPlusBnd<Ops,true>::post(home,x0,x1,ops);
00209
00210 assert((x0.min() < 0) && (x0.max() > 0));
00211 assert((x1.min() < 0) && (x1.max() > 0));
00212 GECODE_ES_CHECK(prop_nroot_bnd<Ops>(home,x0,x1,ops));
00213 (void) new (home) NrootBnd(home,x0,x1,ops);
00214 return ES_OK;
00215 }
00216
00217 template<class Ops>
00218 forceinline
00219 NrootBnd<Ops>::NrootBnd(Space& home, NrootBnd<Ops>& p)
00220 : BinaryPropagator<IntView,PC_INT_BND>(home,p),
00221 ops(p.ops) {}
00222
00223 template<class Ops>
00224 Actor*
00225 NrootBnd<Ops>::copy(Space& home) {
00226 return new (home) NrootBnd<Ops>(home,*this);
00227 }
00228
00229 template<class Ops>
00230 ExecStatus
00231 NrootBnd<Ops>::propagate(Space& home, const ModEventDelta&) {
00232 assert(!ops.even());
00233 if ((x0.min() >= 0) || (x1.min() >= 0))
00234 GECODE_REWRITE(*this,(NrootPlusBnd<Ops,false>::post(home(*this),x0,x1,ops)));
00235
00236 if ((x0.max() <= 0) || (x1.max() <= 0))
00237 GECODE_REWRITE(*this,(NrootPlusBnd<Ops,true>::post(home(*this),x0,x1,ops)));
00238
00239 GECODE_ES_CHECK(prop_nroot_bnd(home,x0,x1,ops));
00240
00241 return x0.assigned() && x1.assigned() ? home.ES_SUBSUMED(*this) : ES_NOFIX;
00242 }
00243
00244
00245
00246
00247
00248
00250 template<class Ops>
00251 class RangesMapPow {
00252 protected:
00254 Ops ops;
00255 public:
00257 forceinline RangesMapPow(const Ops& o) : ops(o) {}
00259 forceinline int min(int x) const {
00260 return ops.tpow(x);
00261 }
00263 forceinline int max(int x) const {
00264 return ops.tpow(x+1)-1;
00265 }
00266 };
00267
00269 template<class Ops>
00270 class RangesMapNroot {
00271 protected:
00273 Ops ops;
00274 public:
00276 forceinline RangesMapNroot(const Ops& o) : ops(o) {}
00278 forceinline int min(int x) const {
00279 return (x < 0) ? -ops.cnroot(-x) : ops.fnroot(x);
00280 }
00282 forceinline int max(int x) const {
00283 return (x < 0) ? -ops.cnroot(-x) : ops.fnroot(x);
00284 }
00285 };
00286
00287 template<class Ops, bool minus>
00288 forceinline
00289 NrootPlusDom<Ops,minus>::NrootPlusDom(Home home, IntView x0, IntView x1,
00290 const Ops& o)
00291 : BinaryPropagator<IntView,PC_INT_DOM>(home,x0,x1),
00292 ops(o) {}
00293
00294 template<class Ops, bool minus>
00295 forceinline ExecStatus
00296 NrootPlusDom<Ops,minus>::post(Home home, IntView x0, IntView x1, Ops ops) {
00297 if (minus) {
00298 GECODE_ME_CHECK(x0.lq(home,0));
00299 GECODE_ME_CHECK(x1.lq(home,0));
00300 } else {
00301 GECODE_ME_CHECK(x0.gq(home,0));
00302 GECODE_ME_CHECK(x1.gq(home,0));
00303 }
00304 GECODE_ES_CHECK((prop_nroot_plus_bnd<Ops,minus>(home,x0,x1,ops)));
00305 (void) new (home) NrootPlusDom<Ops,minus>(home,x0,x1,ops);
00306 return ES_OK;
00307 }
00308
00309 template<class Ops, bool minus>
00310 forceinline
00311 NrootPlusDom<Ops,minus>::NrootPlusDom(Space& home,
00312 NrootPlusDom<Ops,minus>& p)
00313 : BinaryPropagator<IntView,PC_INT_DOM>(home,p),
00314 ops(p.ops) {}
00315
00316 template<class Ops, bool minus>
00317 Actor*
00318 NrootPlusDom<Ops,minus>::copy(Space& home) {
00319 return new (home) NrootPlusDom<Ops,minus>(home,*this);
00320 }
00321
00322 template<class Ops, bool minus>
00323 PropCost
00324 NrootPlusDom<Ops,minus>::cost(const Space&, const ModEventDelta& med) const {
00325 if (IntView::me(med) == ME_INT_VAL)
00326 return PropCost::unary(PropCost::LO);
00327 else if (IntView::me(med) == ME_INT_DOM)
00328 return PropCost::binary(PropCost::HI);
00329 else
00330 return PropCost::binary(PropCost::LO);
00331 }
00332
00333 template<class Ops, bool minus>
00334 ExecStatus
00335 NrootPlusDom<Ops,minus>::propagate(Space& home, const ModEventDelta& med) {
00336 if (IntView::me(med) != ME_INT_DOM) {
00337 GECODE_ES_CHECK((prop_nroot_plus_bnd<Ops,minus>(home,x0,x1,ops)));
00338 return x1.assigned() ? home.ES_SUBSUMED(*this)
00339 : home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
00340 }
00341
00342 {
00343 ViewRanges<IntView> r(x0);
00344 RangesMapNroot<Ops> rmn(ops);
00345 Iter::Ranges::Map<ViewRanges<IntView>,RangesMapNroot<Ops>,false>
00346 m(r,rmn);
00347 GECODE_ME_CHECK(x1.inter_r(home,m,false));
00348 }
00349
00350 {
00351 ViewRanges<IntView> r(x1);
00352 RangesMapPow<Ops> rmp(ops);
00353 Iter::Ranges::Map<ViewRanges<IntView>,RangesMapPow<Ops>,true>
00354 m(r,rmp);
00355 GECODE_ME_CHECK(x0.inter_r(home,m,false));
00356 }
00357
00358 return x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00359 }
00360
00361
00362
00363 template<class Ops>
00364 forceinline
00365 NrootDom<Ops>::NrootDom(Home home, IntView x0, IntView x1, const Ops& o)
00366 : BinaryPropagator<IntView,PC_INT_DOM>(home,x0,x1),
00367 ops(o) {}
00368
00369 template<class Ops>
00370 forceinline ExecStatus
00371 NrootDom<Ops>::post(Home home, IntView x0, IntView x1, Ops ops) {
00372 if (static_cast<unsigned int>(ops.exp()) >= sizeof(int) * CHAR_BIT) {
00373
00374 GECODE_ME_CHECK(x1.lq(home,1));
00375 GECODE_ME_CHECK(x1.gq(home,-2));
00376
00377 ops.exp(ops.even() ? 30 : 31);
00378 }
00379
00380 if (ops.exp() == 0) {
00381 GECODE_ME_CHECK(x1.eq(home,1));
00382 return ES_OK;
00383 } else if (ops.exp() == 1) {
00384 return Rel::EqDom<IntView,IntView>::post(home,x0,x1);
00385 }
00386
00387 if (same(x0,x1)) {
00388 assert(ops.exp() > 1);
00389 GECODE_ME_CHECK(x0.lq(home,1));
00390 GECODE_ME_CHECK(x0.gq(home,ops.even() ? 0 : -2));
00391 return ES_OK;
00392 }
00393
00394
00395 GECODE_ME_CHECK(x1.lq(home,ops.fnroot(Limits::max)));
00396 GECODE_ME_CHECK(x1.gq(home,-ops.cnroot(-Limits::min)));
00397
00398 if (ops.even()) {
00399 GECODE_ME_CHECK(x0.gq(home,0));
00400 GECODE_ME_CHECK(x1.gq(home,0));
00401 }
00402
00403 if ((x0.min() >= 0) || (x1.min() >= 0))
00404 return NrootPlusDom<Ops,false>::post(home,x0,x1,ops);
00405
00406 if ((x0.max() <= 0) || (x1.max() <= 0))
00407 return NrootPlusDom<Ops,true>::post(home,x0,x1,ops);
00408
00409 assert((x0.min() < 0) && (x0.max() > 0));
00410 assert((x1.min() < 0) && (x1.max() > 0));
00411 GECODE_ES_CHECK(prop_nroot_bnd<Ops>(home,x0,x1,ops));
00412 (void) new (home) NrootDom(home,x0,x1,ops);
00413 return ES_OK;
00414 }
00415
00416 template<class Ops>
00417 forceinline
00418 NrootDom<Ops>::NrootDom(Space& home, NrootDom<Ops>& p)
00419 : BinaryPropagator<IntView,PC_INT_DOM>(home,p),
00420 ops(p.ops) {}
00421
00422 template<class Ops>
00423 Actor*
00424 NrootDom<Ops>::copy(Space& home) {
00425 return new (home) NrootDom<Ops>(home,*this);
00426 }
00427
00428 template<class Ops>
00429 PropCost
00430 NrootDom<Ops>::cost(const Space&, const ModEventDelta& med) const {
00431 if (IntView::me(med) == ME_INT_VAL)
00432 return PropCost::unary(PropCost::LO);
00433 else if (IntView::me(med) == ME_INT_DOM)
00434 return PropCost::binary(PropCost::HI);
00435 else
00436 return PropCost::binary(PropCost::LO);
00437 }
00438
00439 template<class Ops>
00440 ExecStatus
00441 NrootDom<Ops>::propagate(Space& home, const ModEventDelta& med) {
00442 assert(!ops.even());
00443 if ((x0.min() >= 0) || (x1.min() >= 0))
00444 GECODE_REWRITE(*this,(NrootPlusDom<Ops,false>::post(home(*this),x0,x1,ops)));
00445
00446 if ((x0.max() <= 0) || (x1.max() <= 0))
00447 GECODE_REWRITE(*this,(NrootPlusDom<Ops,true>::post(home(*this),x0,x1,ops)));
00448
00449 if (IntView::me(med) != ME_INT_DOM) {
00450 GECODE_ES_CHECK(prop_nroot_bnd<Ops>(home,x0,x1,ops));
00451 return x0.assigned() && x1.assigned() ? home.ES_SUBSUMED(*this)
00452 : home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
00453 }
00454
00455 {
00456 ViewRanges<IntView> r(x0);
00457 RangesMapNroot<Ops> rmn(ops);
00458 Iter::Ranges::Map<ViewRanges<IntView>,RangesMapNroot<Ops>,false>
00459 m(r,rmn);
00460 GECODE_ME_CHECK(x1.inter_r(home,m,false));
00461 }
00462
00463 {
00464 ViewRanges<IntView> r(x1);
00465 RangesMapPow<Ops> rmp(ops);
00466 Iter::Ranges::Map<ViewRanges<IntView>,RangesMapPow<Ops>,true>
00467 m(r,rmp);
00468 GECODE_ME_CHECK(x0.inter_r(home,m,false));
00469 }
00470
00471 return x0.assigned() && x1.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00472 }
00473
00474
00475 }}}
00476
00477
00478