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