Generated on Fri Oct 19 11:25:01 2018 for Gecode by doxygen 1.6.3

pow.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2012
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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    * Positive bounds consistent power
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    * Bounds consistent power
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       // The integer limits allow only -1, 0, 1 for x0
00152       GECODE_ME_CHECK(x0.lq(home,1));
00153       GECODE_ME_CHECK(x0.gq(home,-1));
00154       // Just rewrite to values that can be handeled without overflow
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 (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     // Limits values such that no overflow can occur
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    * Value mappings for power and nroot
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    * Positive domain consistent power
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    * Domain consistent power
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       // The integer limits allow only -1, 0, 1 for x0
00389       GECODE_ME_CHECK(x0.lq(home,1));
00390       GECODE_ME_CHECK(x0.gq(home,-1));
00391       // Just rewrite to values that can be handeled without overflow
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 (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     // Limits values such that no overflow can occur
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 // STATISTICS: int-prop
00537