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 template<class VA, class VB, class Ops>
00046 inline ExecStatus
00047 prop_pow_plus_bnd(Space& home, VA x0, VB x1, const Ops& ops) {
00048 bool mod;
00049 do {
00050 mod = false;
00051 {
00052 ModEvent me = x0.lq(home,ops.fnroot(x1.max()));
00053 if (me_failed(me)) return ES_FAILED;
00054 mod |= me_modified(me);
00055 }
00056 {
00057 ModEvent me = x0.gq(home,ops.cnroot(x1.min()));
00058 if (me_failed(me)) return ES_FAILED;
00059 mod |= me_modified(me);
00060 }
00061 {
00062 ModEvent me = x1.lq(home,ops.pow(x0.max()));
00063 if (me_failed(me)) return ES_FAILED;
00064 mod |= me_modified(me);
00065 }
00066 {
00067 ModEvent me = x1.gq(home,ops.pow(x0.min()));
00068 if (me_failed(me)) return ES_FAILED;
00069 mod |= me_modified(me);
00070 }
00071 } while (mod);
00072 return ES_OK;
00073 }
00074
00075 template<class VA, class VB, class Ops>
00076 forceinline
00077 PowPlusBnd<VA,VB,Ops>::PowPlusBnd(Home home, VA x0, VB x1, const Ops& o)
00078 : MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND>(home,x0,x1),
00079 ops(o) {}
00080
00081 template<class VA, class VB, class Ops>
00082 forceinline ExecStatus
00083 PowPlusBnd<VA,VB,Ops>::post(Home home, VA x0, VB x1, Ops ops) {
00084 GECODE_ME_CHECK(x0.gq(home,0));
00085 GECODE_ME_CHECK(x1.gq(home,0));
00086 GECODE_ES_CHECK(prop_pow_plus_bnd(home,x0,x1,ops));
00087 if (!x0.assigned()) {
00088 assert(!x1.assigned());
00089 (void) new (home) PowPlusBnd<VA,VB,Ops>(home,x0,x1,ops);
00090 }
00091 return ES_OK;
00092 }
00093
00094 template<class VA, class VB, class Ops>
00095 forceinline
00096 PowPlusBnd<VA,VB,Ops>::PowPlusBnd(Space& home, PowPlusBnd<VA,VB,Ops>& p)
00097 : MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND>(home,p),
00098 ops(p.ops) {}
00099
00100 template<class VA, class VB, class Ops>
00101 Actor*
00102 PowPlusBnd<VA,VB,Ops>::copy(Space& home) {
00103 return new (home) PowPlusBnd<VA,VB,Ops>(home,*this);
00104 }
00105
00106 template<class VA, class VB, class Ops>
00107 ExecStatus
00108 PowPlusBnd<VA,VB,Ops>::propagate(Space& home, const ModEventDelta&) {
00109 GECODE_ES_CHECK(prop_pow_plus_bnd(home,x0,x1,ops));
00110 return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00111 }
00112
00113
00114
00115
00116
00117
00118
00119
00120 template<class Ops>
00121 inline ExecStatus
00122 prop_pow_bnd(Space& home, IntView x0, IntView x1, const Ops& ops) {
00123 assert((x0.min() < 0) && (0 < x0.max()));
00124 if (ops.even()) {
00125 assert(x1.min() >= 0);
00126 int u = ops.fnroot(x1.max());
00127 GECODE_ME_CHECK(x0.lq(home,u));
00128 GECODE_ME_CHECK(x0.gq(home,-u));
00129 GECODE_ME_CHECK(x1.lq(home,std::max(ops.pow(x0.max()),
00130 ops.pow(-x0.min()))));
00131 } else {
00132 assert((x1.min() < 0) && (0 < x1.max()));
00133 GECODE_ME_CHECK(x0.lq(home,ops.fnroot(x1.max())));
00134 GECODE_ME_CHECK(x0.gq(home,-ops.fnroot(-x1.min())));
00135 GECODE_ME_CHECK(x1.lq(home,ops.pow(x0.max())));
00136 GECODE_ME_CHECK(x1.gq(home,ops.pow(x0.min())));
00137 }
00138 return ES_OK;
00139 }
00140
00141 template<class Ops>
00142 forceinline
00143 PowBnd<Ops>::PowBnd(Home home, IntView x0, IntView x1, const Ops& o)
00144 : BinaryPropagator<IntView,PC_INT_BND>(home,x0,x1),
00145 ops(o) {}
00146
00147 template<class Ops>
00148 inline ExecStatus
00149 PowBnd<Ops>::post(Home home, IntView x0, IntView x1, Ops ops) {
00150 if (static_cast<unsigned int>(ops.exp()) >= sizeof(int) * CHAR_BIT) {
00151
00152 GECODE_ME_CHECK(x0.lq(home,1));
00153 GECODE_ME_CHECK(x0.gq(home,-1));
00154
00155 ops.exp(ops.even() ? 2 : 1);
00156 }
00157
00158 if (ops.exp() == 0) {
00159 GECODE_ME_CHECK(x1.eq(home,1));
00160 return ES_OK;
00161 } else if (ops.exp() == 1) {
00162 return Rel::EqBnd<IntView,IntView>::post(home,x0,x1);
00163 }
00164
00165 if (same(x0,x1)) {
00166 assert(ops.exp() != 0);
00167 GECODE_ME_CHECK(x0.lq(home,1));
00168 GECODE_ME_CHECK(x0.gq(home,ops.even() ? 0 : -1));
00169 return ES_OK;
00170 }
00171
00172
00173 assert(Limits::max == -Limits::min);
00174 {
00175 int l = ops.fnroot(Limits::max);
00176 GECODE_ME_CHECK(x0.lq(home,l));
00177 GECODE_ME_CHECK(x0.gq(home,-l));
00178 }
00179
00180 if ((x0.min() >= 0) || ((x1.min() >= 0) && !ops.even()))
00181 return PowPlusBnd<IntView,IntView,Ops>::post(home,x0,x1,ops);
00182
00183 if (ops.even() && (x0.max() <= 0))
00184 return PowPlusBnd<MinusView,IntView,Ops>
00185 ::post(home,MinusView(x0),x1,ops);
00186
00187 if (!ops.even() && ((x0.max() <= 0) || (x1.max() <= 0)))
00188 return PowPlusBnd<MinusView,MinusView,Ops>
00189 ::post(home,MinusView(x0),MinusView(x1),ops);
00190
00191 if (ops.even())
00192 GECODE_ME_CHECK(x1.gq(home,0));
00193
00194 assert((x0.min() < 0) && (x0.max() > 0));
00195
00196 if (ops.even()) {
00197 GECODE_ME_CHECK(x1.lq(home,std::max(ops.pow(x0.min()),
00198 ops.pow(x0.max()))));
00199 } else {
00200 GECODE_ME_CHECK(x1.lq(home,ops.pow(x0.max())));
00201 GECODE_ME_CHECK(x1.gq(home,ops.pow(x0.min())));
00202 }
00203
00204 (void) new (home) PowBnd<Ops>(home,x0,x1,ops);
00205 return ES_OK;
00206 }
00207
00208 template<class Ops>
00209 forceinline
00210 PowBnd<Ops>::PowBnd(Space& home, PowBnd<Ops>& p)
00211 : BinaryPropagator<IntView,PC_INT_BND>(home,p),
00212 ops(p.ops) {}
00213
00214 template<class Ops>
00215 Actor*
00216 PowBnd<Ops>::copy(Space& home) {
00217 return new (home) PowBnd<Ops>(home,*this);
00218 }
00219
00220 template<class Ops>
00221 ExecStatus
00222 PowBnd<Ops>::propagate(Space& home, const ModEventDelta&) {
00223 if ((x0.min() >= 0) || ((x1.min() >= 0) && !ops.even()))
00224 GECODE_REWRITE(*this,(PowPlusBnd<IntView,IntView,Ops>
00225 ::post(home(*this),x0,x1,ops)));
00226
00227 if (ops.even() && (x0.max() <= 0))
00228 GECODE_REWRITE(*this,(PowPlusBnd<MinusView,IntView,Ops>
00229 ::post(home(*this),MinusView(x0),x1,ops)));
00230
00231 if (!ops.even() && ((x0.max() <= 0) || (x1.max() <= 0)))
00232 GECODE_REWRITE(*this,(PowPlusBnd<MinusView,MinusView,Ops>
00233 ::post(home(*this),MinusView(x0),
00234 MinusView(x1),ops)));
00235
00236 GECODE_ES_CHECK(prop_pow_bnd<Ops>(home,x0,x1,ops));
00237
00238 if (x0.assigned() && x1.assigned())
00239 return (ops.pow(x0.val()) == x1.val()) ?
00240 home.ES_SUBSUMED(*this) : ES_FAILED;
00241
00242 return ES_NOFIX;
00243 }
00244
00245
00246
00247
00248
00249
00250
00252 template<class Ops>
00253 class ValuesMapPow {
00254 protected:
00256 Ops ops;
00257 public:
00259 forceinline ValuesMapPow(const Ops& o) : ops(o) {}
00261 forceinline int val(int x) const {
00262 return ops.pow(x);
00263 }
00264 };
00265
00267 template<class Ops>
00268 class ValuesMapNroot {
00269 protected:
00271 Ops ops;
00272 public:
00274 forceinline ValuesMapNroot(const Ops& o) : ops(o) {}
00276 forceinline int val(int x) const {
00277 return ops.fnroot(x);
00278 }
00279 };
00280
00282 template<class Ops>
00283 class ValuesMapNrootSigned {
00284 protected:
00286 Ops ops;
00287 public:
00289 forceinline ValuesMapNrootSigned(const Ops& o) : ops(o) {}
00291 forceinline int val(int x) const {
00292 if (x < 0)
00293 return -ops.fnroot(-x);
00294 else
00295 return ops.fnroot(x);
00296 }
00297 };
00298
00299
00300
00301
00302
00303
00304 template<class VA, class VB, class Ops>
00305 forceinline
00306 PowPlusDom<VA,VB,Ops>::PowPlusDom(Home home, VA x0, VB x1, const Ops& o)
00307 : MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM>(home,x0,x1),
00308 ops(o) {}
00309
00310 template<class VA, class VB, class Ops>
00311 forceinline ExecStatus
00312 PowPlusDom<VA,VB,Ops>::post(Home home, VA x0, VB x1, Ops ops) {
00313 GECODE_ME_CHECK(x0.gq(home,0));
00314 GECODE_ME_CHECK(x1.gq(home,0));
00315 GECODE_ES_CHECK(prop_pow_plus_bnd(home,x0,x1,ops));
00316 if (!x0.assigned()) {
00317 assert(!x1.assigned());
00318 (void) new (home) PowPlusDom<VA,VB,Ops>(home,x0,x1,ops);
00319 }
00320 return ES_OK;
00321 }
00322
00323 template<class VA, class VB, class Ops>
00324 forceinline
00325 PowPlusDom<VA,VB,Ops>::PowPlusDom(Space& home, PowPlusDom<VA,VB,Ops>& p)
00326 : MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM>(home,p),
00327 ops(p.ops) {}
00328
00329 template<class VA, class VB, class Ops>
00330 Actor*
00331 PowPlusDom<VA,VB,Ops>::copy(Space& home) {
00332 return new (home) PowPlusDom<VA,VB,Ops>(home,*this);
00333 }
00334
00335 template<class VA, class VB, class Ops>
00336 PropCost
00337 PowPlusDom<VA,VB,Ops>::cost(const Space&, const ModEventDelta& med) const {
00338 if (VA::me(med) == ME_INT_VAL)
00339 return PropCost::unary(PropCost::LO);
00340 else if (VA::me(med) == ME_INT_DOM)
00341 return PropCost::binary(PropCost::HI);
00342 else
00343 return PropCost::binary(PropCost::LO);
00344 }
00345
00346 template<class VA, class VB, class Ops>
00347 ExecStatus
00348 PowPlusDom<VA,VB,Ops>::propagate(Space& home, const ModEventDelta& med) {
00349 if (VA::me(med) != ME_INT_DOM) {
00350 GECODE_ES_CHECK(prop_pow_plus_bnd(home,x0,x1,ops));
00351 return x0.assigned() ?
00352 home.ES_SUBSUMED(*this)
00353 : home.ES_NOFIX_PARTIAL(*this,VA::med(ME_INT_DOM));
00354 }
00355
00356 {
00357 ViewValues<VA> v0(x0);
00358 ValuesMapPow<Ops> vmp(ops);
00359 Iter::Values::Map<ViewValues<VA>,ValuesMapPow<Ops> > s0(v0,vmp);
00360 GECODE_ME_CHECK(x1.inter_v(home,s0,false));
00361 }
00362
00363 {
00364 ViewValues<VB> v1(x1);
00365 ValuesMapNroot<Ops> vmn(ops);
00366 Iter::Values::Map<ViewValues<VB>,ValuesMapNroot<Ops> > s1(v1,vmn);
00367 GECODE_ME_CHECK(x0.inter_v(home,s1,false));
00368 }
00369
00370 return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00371 }
00372
00373
00374
00375
00376
00377
00378
00379 template<class Ops>
00380 forceinline
00381 PowDom<Ops>::PowDom(Home home, IntView x0, IntView x1, const Ops& o)
00382 : BinaryPropagator<IntView,PC_INT_DOM>(home,x0,x1), ops(o) {}
00383
00384 template<class Ops>
00385 inline ExecStatus
00386 PowDom<Ops>::post(Home home, IntView x0, IntView x1, Ops ops) {
00387 if (static_cast<unsigned int>(ops.exp()) >= sizeof(int) * CHAR_BIT) {
00388
00389 GECODE_ME_CHECK(x0.lq(home,1));
00390 GECODE_ME_CHECK(x0.gq(home,-1));
00391
00392 ops.exp(ops.even() ? 2 : 1);
00393 }
00394
00395 if (ops.exp() == 0) {
00396 GECODE_ME_CHECK(x1.eq(home,1));
00397 return ES_OK;
00398 } else if (ops.exp() == 1) {
00399 return Rel::EqDom<IntView,IntView>::post(home,x0,x1);
00400 }
00401
00402 if (same(x0,x1)) {
00403 assert(ops.exp() != 0);
00404 GECODE_ME_CHECK(x0.lq(home,1));
00405 GECODE_ME_CHECK(x0.gq(home,ops.even() ? 0 : -1));
00406 return ES_OK;
00407 }
00408
00409
00410 assert(Limits::max == -Limits::min);
00411 {
00412 int l = ops.fnroot(Limits::max);
00413 GECODE_ME_CHECK(x0.lq(home,l));
00414 GECODE_ME_CHECK(x0.gq(home,-l));
00415 }
00416
00417 if ((x0.min() >= 0) || ((x1.min() >= 0) && !ops.even()))
00418 return PowPlusDom<IntView,IntView,Ops>::post(home,x0,x1,ops);
00419
00420 if (ops.even() && (x0.max() <= 0))
00421 return PowPlusDom<MinusView,IntView,Ops>
00422 ::post(home,MinusView(x0),x1,ops);
00423
00424 if (!ops.even() && ((x0.max() <= 0) || (x1.max() <= 0)))
00425 return PowPlusDom<MinusView,MinusView,Ops>
00426 ::post(home,MinusView(x0),MinusView(x1),ops);
00427
00428 if (ops.even())
00429 GECODE_ME_CHECK(x1.gq(home,0));
00430
00431 assert((x0.min() < 0) && (x0.max() > 0));
00432
00433 if (ops.even()) {
00434 GECODE_ME_CHECK(x1.lq(home,std::max(ops.pow(x0.min()),
00435 ops.pow(x0.max()))));
00436 } else {
00437 GECODE_ME_CHECK(x1.lq(home,ops.pow(x0.max())));
00438 GECODE_ME_CHECK(x1.gq(home,ops.pow(x0.min())));
00439 }
00440
00441 (void) new (home) PowDom<Ops>(home,x0,x1,ops);
00442 return ES_OK;
00443 }
00444
00445 template<class Ops>
00446 forceinline
00447 PowDom<Ops>::PowDom(Space& home, PowDom<Ops>& p)
00448 : BinaryPropagator<IntView,PC_INT_DOM>(home,p),
00449 ops(p.ops) {}
00450
00451 template<class Ops>
00452 Actor*
00453 PowDom<Ops>::copy(Space& home) {
00454 return new (home) PowDom<Ops>(home,*this);
00455 }
00456
00457 template<class Ops>
00458 PropCost
00459 PowDom<Ops>::cost(const Space&, const ModEventDelta& med) const {
00460 if (IntView::me(med) == ME_INT_VAL)
00461 return PropCost::unary(PropCost::LO);
00462 else if (IntView::me(med) == ME_INT_DOM)
00463 return PropCost::binary(PropCost::HI);
00464 else
00465 return PropCost::binary(PropCost::LO);
00466 }
00467
00468 template<class Ops>
00469 ExecStatus
00470 PowDom<Ops>::propagate(Space& home, const ModEventDelta& med) {
00471 if ((x0.min() >= 0) || ((x1.min() >= 0) && !ops.even()))
00472 GECODE_REWRITE(*this,(PowPlusDom<IntView,IntView,Ops>
00473 ::post(home(*this),x0,x1,ops)));
00474
00475 if (ops.even() && (x0.max() <= 0))
00476 GECODE_REWRITE(*this,(PowPlusDom<MinusView,IntView,Ops>
00477 ::post(home(*this),MinusView(x0),x1,ops)));
00478
00479 if (!ops.even() && ((x0.max() <= 0) || (x1.max() <= 0)))
00480 GECODE_REWRITE(*this,(PowPlusDom<MinusView,MinusView,Ops>
00481 ::post(home(*this),MinusView(x0),
00482 MinusView(x1),ops)));
00483
00484 if (IntView::me(med) != ME_INT_DOM) {
00485 GECODE_ES_CHECK(prop_pow_bnd<Ops>(home,x0,x1,ops));
00486 if (x0.assigned() && x1.assigned())
00487 return (ops.pow(x0.val()) == x1.val()) ?
00488 home.ES_SUBSUMED(*this) : ES_FAILED;
00489
00490 return home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
00491 }
00492
00493 Region r;
00494 if (ops.even()) {
00495 ViewValues<IntView> i(x0), j(x0);
00496 using namespace Iter::Values;
00497 Positive<ViewValues<IntView> > pos(i);
00498 Negative<ViewValues<IntView> > neg(j);
00499 Minus m(r,neg);
00500
00501 ValuesMapPow<Ops> vmp(ops);
00502 Map<Positive<ViewValues<IntView> >,ValuesMapPow<Ops>,true> sp(pos,vmp);
00503 Map<Minus,ValuesMapPow<Ops>,true> sm(m,vmp);
00504 Union<Map<Positive<ViewValues<IntView> >,ValuesMapPow<Ops>,true>,
00505 Map<Minus,ValuesMapPow<Ops>,true> > u(sp,sm);
00506 GECODE_ME_CHECK(x1.inter_v(home,u,false));
00507 } else {
00508 ViewValues<IntView> v0(x0);
00509 ValuesMapPow<Ops> vmp(ops);
00510 Iter::Values::Map<ViewValues<IntView>,ValuesMapPow<Ops> > s0(v0,vmp);
00511 GECODE_ME_CHECK(x1.inter_v(home,s0,false));
00512 }
00513
00514 if (ops.even()) {
00515 ViewValues<IntView> i(x1), j(x1);
00516 using namespace Iter::Values;
00517 ValuesMapNroot<Ops> vmn(ops);
00518 Map<ViewValues<IntView>,ValuesMapNroot<Ops>,true> si(i,vmn), sj(j,vmn);
00519 Minus mi(r,si);
00520 Union<Minus,
00521 Map<ViewValues<IntView>,ValuesMapNroot<Ops>,true> > u(mi,sj);
00522 GECODE_ME_CHECK(x0.inter_v(home,u,false));
00523 } else {
00524 ViewValues<IntView> v1(x1);
00525 ValuesMapNrootSigned<Ops> vmn(ops);
00526 Iter::Values::Map<ViewValues<IntView>,ValuesMapNrootSigned<Ops> >
00527 s1(v1,vmn);
00528 GECODE_ME_CHECK(x0.inter_v(home,s1,false));
00529 }
00530
00531 return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00532 }
00533
00534 }}}
00535
00536
00537