pow.hpp

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  *  Last modified:
00010  *     $Date: 2016-04-19 17:19:45 +0200 (Tue, 19 Apr 2016) $ by $Author: schulte $
00011  *     $Revision: 14967 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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    * Positive bounds consistent power
00047    *
00048    */
00049   template<class VA, class VB, class Ops>
00050   inline ExecStatus
00051   prop_pow_plus_bnd(Space& home, VA x0, VB x1, const Ops& ops) {
00052     bool mod;
00053     do {
00054       mod = false;
00055       {
00056         ModEvent me = x0.lq(home,ops.fnroot(x1.max()));
00057         if (me_failed(me)) return ES_FAILED;
00058         mod |= me_modified(me);
00059       }
00060       {
00061         ModEvent me = x0.gq(home,ops.cnroot(x1.min()));
00062         if (me_failed(me)) return ES_FAILED;
00063         mod |= me_modified(me);
00064       }
00065       {
00066         ModEvent me = x1.lq(home,ops.pow(x0.max()));
00067         if (me_failed(me)) return ES_FAILED;
00068         mod |= me_modified(me);
00069       }
00070       {
00071         ModEvent me = x1.gq(home,ops.pow(x0.min()));
00072         if (me_failed(me)) return ES_FAILED;
00073         mod |= me_modified(me);
00074       }
00075     } while (mod);
00076     return ES_OK;
00077   }
00078 
00079   template<class VA, class VB, class Ops>
00080   forceinline
00081   PowPlusBnd<VA,VB,Ops>::PowPlusBnd(Home home, VA x0, VB x1, const Ops& o)
00082     : MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND>(home,x0,x1),
00083       ops(o) {}
00084 
00085   template<class VA, class VB, class Ops>
00086   forceinline ExecStatus
00087   PowPlusBnd<VA,VB,Ops>::post(Home home, VA x0, VB x1, Ops ops) {
00088     GECODE_ME_CHECK(x0.gq(home,0));
00089     GECODE_ME_CHECK(x1.gq(home,0));
00090     GECODE_ES_CHECK(prop_pow_plus_bnd(home,x0,x1,ops));
00091     if (!x0.assigned()) {
00092       assert(!x1.assigned());
00093       (void) new (home) PowPlusBnd<VA,VB,Ops>(home,x0,x1,ops);
00094     }
00095     return ES_OK;
00096   }
00097 
00098   template<class VA, class VB, class Ops>
00099   forceinline
00100   PowPlusBnd<VA,VB,Ops>::PowPlusBnd(Space& home, bool share,
00101                                     PowPlusBnd<VA,VB,Ops>& p)
00102     : MixBinaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND>(home,share,p),
00103       ops(p.ops) {}
00104 
00105   template<class VA, class VB, class Ops>
00106   Actor*
00107   PowPlusBnd<VA,VB,Ops>::copy(Space& home, bool share) {
00108     return new (home) PowPlusBnd<VA,VB,Ops>(home,share,*this);
00109   }
00110 
00111   template<class VA, class VB, class Ops>
00112   ExecStatus
00113   PowPlusBnd<VA,VB,Ops>::propagate(Space& home, const ModEventDelta&) {
00114     GECODE_ES_CHECK(prop_pow_plus_bnd(home,x0,x1,ops));
00115     return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00116   }
00117 
00118 
00119 
00120   /*
00121    * Bounds consistent power
00122    *
00123    */
00124 
00125   template<class Ops>
00126   inline ExecStatus
00127   prop_pow_bnd(Space& home, IntView x0, IntView x1, const Ops& ops) {
00128     assert((x0.min() < 0) && (0 < x0.max()));
00129     if (ops.even()) {
00130       assert(x1.min() >= 0);
00131       int u = ops.fnroot(x1.max());
00132       GECODE_ME_CHECK(x0.lq(home,u));
00133       GECODE_ME_CHECK(x0.gq(home,-u));
00134       GECODE_ME_CHECK(x1.lq(home,std::max(ops.pow(x0.max()),
00135                                           ops.pow(-x0.min()))));
00136     } else {
00137       assert((x1.min() < 0) && (0 < x1.max()));
00138       GECODE_ME_CHECK(x0.lq(home,ops.fnroot(x1.max())));
00139       GECODE_ME_CHECK(x0.gq(home,-ops.fnroot(-x1.min())));
00140       GECODE_ME_CHECK(x1.lq(home,ops.pow(x0.max())));
00141       GECODE_ME_CHECK(x1.gq(home,ops.pow(x0.min())));
00142     }
00143     return ES_OK;
00144   }
00145 
00146   template<class Ops>
00147   forceinline
00148   PowBnd<Ops>::PowBnd(Home home, IntView x0, IntView x1, const Ops& o)
00149     : BinaryPropagator<IntView,PC_INT_BND>(home,x0,x1),
00150       ops(o) {}
00151 
00152   template<class Ops>
00153   inline ExecStatus
00154   PowBnd<Ops>::post(Home home, IntView x0, IntView x1, Ops ops) {
00155     if (static_cast<unsigned int>(ops.exp()) >= sizeof(int) * CHAR_BIT) {
00156       // The integer limits allow only -1, 0, 1 for x0
00157       GECODE_ME_CHECK(x0.lq(home,1));
00158       GECODE_ME_CHECK(x0.gq(home,-1));
00159       // Just rewrite to values that can be handeled without overflow
00160       ops.exp(ops.even() ? 2 : 1);
00161     }
00162 
00163     if (ops.exp() == 0) {
00164       GECODE_ME_CHECK(x1.eq(home,1));
00165       return ES_OK;
00166     } else if (ops.exp() == 1) {
00167       return Rel::EqBnd<IntView,IntView>::post(home,x0,x1);
00168     }
00169 
00170     if (same(x0,x1)) {
00171       assert(ops.exp() != 0);
00172       GECODE_ME_CHECK(x0.lq(home,1));
00173       GECODE_ME_CHECK(x0.gq(home,ops.even() ? 0 : -1));
00174       return ES_OK;
00175     }
00176 
00177     // Limits values such that no overflow can occur
00178     assert(Limits::max == -Limits::min);
00179     {
00180       int l = ops.fnroot(Limits::max);
00181       GECODE_ME_CHECK(x0.lq(home,l));
00182       GECODE_ME_CHECK(x0.gq(home,-l));
00183     }
00184 
00185     if ((x0.min() >= 0) || ((x1.min() >= 0) && !ops.even()))
00186       return PowPlusBnd<IntView,IntView,Ops>::post(home,x0,x1,ops);
00187 
00188     if (ops.even() && (x0.max() <= 0))
00189       return PowPlusBnd<MinusView,IntView,Ops>
00190         ::post(home,MinusView(x0),x1,ops);
00191 
00192     if (!ops.even() && ((x0.max() <= 0) || (x1.max() <= 0)))
00193       return PowPlusBnd<MinusView,MinusView,Ops>
00194         ::post(home,MinusView(x0),MinusView(x1),ops);
00195 
00196     if (ops.even())
00197       GECODE_ME_CHECK(x1.gq(home,0));
00198 
00199     assert((x0.min() < 0) && (x0.max() > 0));
00200 
00201     if (ops.even()) {
00202       GECODE_ME_CHECK(x1.lq(home,std::max(ops.pow(x0.min()),
00203                                           ops.pow(x0.max()))));
00204     } else {
00205       GECODE_ME_CHECK(x1.lq(home,ops.pow(x0.max())));
00206       GECODE_ME_CHECK(x1.gq(home,ops.pow(x0.min())));
00207     }
00208 
00209     (void) new (home) PowBnd<Ops>(home,x0,x1,ops);
00210     return ES_OK;
00211   }
00212 
00213   template<class Ops>
00214   forceinline
00215   PowBnd<Ops>::PowBnd(Space& home, bool share, PowBnd<Ops>& p)
00216     : BinaryPropagator<IntView,PC_INT_BND>(home,share,p),
00217       ops(p.ops) {}
00218 
00219   template<class Ops>
00220   Actor*
00221   PowBnd<Ops>::copy(Space& home, bool share) {
00222     return new (home) PowBnd<Ops>(home,share,*this);
00223   }
00224 
00225   template<class Ops>
00226   ExecStatus
00227   PowBnd<Ops>::propagate(Space& home, const ModEventDelta&) {
00228     if ((x0.min() >= 0) || ((x1.min() >= 0) && !ops.even()))
00229       GECODE_REWRITE(*this,(PowPlusBnd<IntView,IntView,Ops>
00230                             ::post(home(*this),x0,x1,ops)));
00231 
00232     if (ops.even() && (x0.max() <= 0))
00233       GECODE_REWRITE(*this,(PowPlusBnd<MinusView,IntView,Ops>
00234                             ::post(home(*this),MinusView(x0),x1,ops)));
00235 
00236     if (!ops.even() && ((x0.max() <= 0) || (x1.max() <= 0)))
00237       GECODE_REWRITE(*this,(PowPlusBnd<MinusView,MinusView,Ops>
00238                             ::post(home(*this),MinusView(x0),
00239                                    MinusView(x1),ops)));
00240 
00241     GECODE_ES_CHECK(prop_pow_bnd<Ops>(home,x0,x1,ops));
00242 
00243     if (x0.assigned() && x1.assigned())
00244       return (ops.pow(x0.val()) == x1.val()) ?
00245         home.ES_SUBSUMED(*this) : ES_FAILED;
00246 
00247     return ES_NOFIX;
00248   }
00249 
00250 
00251   /*
00252    * Value mappings for power and nroot
00253    *
00254    */
00255 
00257   template<class Ops>
00258   class ValuesMapPow {
00259   protected:
00261     Ops ops;
00262   public:
00264     forceinline ValuesMapPow(const Ops& o) : ops(o) {}
00266     forceinline int val(int x) const {
00267       return ops.pow(x);
00268     }
00269   };
00270 
00272   template<class Ops>
00273   class ValuesMapNroot {
00274   protected:
00276     Ops ops;
00277   public:
00279     forceinline ValuesMapNroot(const Ops& o) : ops(o) {}
00281     forceinline int val(int x) const {
00282       return ops.fnroot(x);
00283     }
00284   };
00285 
00287   template<class Ops>
00288   class ValuesMapNrootSigned {
00289   protected:
00291     Ops ops;
00292   public:
00294     forceinline ValuesMapNrootSigned(const Ops& o) : ops(o) {}
00296     forceinline int val(int x) const {
00297       if (x < 0)
00298         return -ops.fnroot(-x);
00299       else
00300         return ops.fnroot(x);
00301     }
00302   };
00303 
00304 
00305   /*
00306    * Positive domain consistent power
00307    *
00308    */
00309   template<class VA, class VB, class Ops>
00310   forceinline
00311   PowPlusDom<VA,VB,Ops>::PowPlusDom(Home home, VA x0, VB x1, const Ops& o)
00312     : MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM>(home,x0,x1),
00313       ops(o) {}
00314 
00315   template<class VA, class VB, class Ops>
00316   forceinline ExecStatus
00317   PowPlusDom<VA,VB,Ops>::post(Home home, VA x0, VB x1, Ops ops) {
00318     GECODE_ME_CHECK(x0.gq(home,0));
00319     GECODE_ME_CHECK(x1.gq(home,0));
00320     GECODE_ES_CHECK(prop_pow_plus_bnd(home,x0,x1,ops));
00321     if (!x0.assigned()) {
00322       assert(!x1.assigned());
00323       (void) new (home) PowPlusDom<VA,VB,Ops>(home,x0,x1,ops);
00324     }
00325     return ES_OK;
00326   }
00327 
00328   template<class VA, class VB, class Ops>
00329   forceinline
00330   PowPlusDom<VA,VB,Ops>::PowPlusDom(Space& home, bool share,
00331                                     PowPlusDom<VA,VB,Ops>& p)
00332     : MixBinaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM>(home,share,p),
00333       ops(p.ops) {}
00334 
00335   template<class VA, class VB, class Ops>
00336   Actor*
00337   PowPlusDom<VA,VB,Ops>::copy(Space& home, bool share) {
00338     return new (home) PowPlusDom<VA,VB,Ops>(home,share,*this);
00339   }
00340 
00341   template<class VA, class VB, class Ops>
00342   PropCost
00343   PowPlusDom<VA,VB,Ops>::cost(const Space&, const ModEventDelta& med) const {
00344     if (VA::me(med) == ME_INT_VAL)
00345       return PropCost::unary(PropCost::LO);
00346     else if (VA::me(med) == ME_INT_DOM)
00347       return PropCost::binary(PropCost::HI);
00348     else
00349       return PropCost::binary(PropCost::LO);
00350   }
00351 
00352   template<class VA, class VB, class Ops>
00353   ExecStatus
00354   PowPlusDom<VA,VB,Ops>::propagate(Space& home, const ModEventDelta& med) {
00355     if (VA::me(med) != ME_INT_DOM) {
00356       GECODE_ES_CHECK(prop_pow_plus_bnd(home,x0,x1,ops));
00357       return x0.assigned() ?
00358         home.ES_SUBSUMED(*this)
00359         : home.ES_NOFIX_PARTIAL(*this,VA::med(ME_INT_DOM));
00360     }
00361 
00362     {
00363       ViewValues<VA> v0(x0);
00364       ValuesMapPow<Ops> vmp(ops);
00365       Iter::Values::Map<ViewValues<VA>,ValuesMapPow<Ops> > s0(v0,vmp);
00366       GECODE_ME_CHECK(x1.inter_v(home,s0,false));
00367     }
00368 
00369     {
00370       ViewValues<VB> v1(x1);
00371       ValuesMapNroot<Ops> vmn(ops);
00372       Iter::Values::Map<ViewValues<VB>,ValuesMapNroot<Ops> > s1(v1,vmn);
00373       GECODE_ME_CHECK(x0.inter_v(home,s1,false));
00374     }
00375 
00376     return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00377   }
00378 
00379 
00380   /*
00381    * Domain consistent power
00382    *
00383    */
00384 
00385   template<class Ops>
00386   forceinline
00387   PowDom<Ops>::PowDom(Home home, IntView x0, IntView x1, const Ops& o)
00388     : BinaryPropagator<IntView,PC_INT_DOM>(home,x0,x1), ops(o) {}
00389 
00390   template<class Ops>
00391   inline ExecStatus
00392   PowDom<Ops>::post(Home home, IntView x0, IntView x1, Ops ops) {
00393     if (static_cast<unsigned int>(ops.exp()) >= sizeof(int) * CHAR_BIT) {
00394       // The integer limits allow only -1, 0, 1 for x0
00395       GECODE_ME_CHECK(x0.lq(home,1));
00396       GECODE_ME_CHECK(x0.gq(home,-1));
00397       // Just rewrite to values that can be handeled without overflow
00398       ops.exp(ops.even() ? 2 : 1);
00399     }
00400 
00401     if (ops.exp() == 0) {
00402       GECODE_ME_CHECK(x1.eq(home,1));
00403       return ES_OK;
00404     } else if (ops.exp() == 1) {
00405       return Rel::EqDom<IntView,IntView>::post(home,x0,x1);
00406     }
00407 
00408     if (same(x0,x1)) {
00409       assert(ops.exp() != 0);
00410       GECODE_ME_CHECK(x0.lq(home,1));
00411       GECODE_ME_CHECK(x0.gq(home,ops.even() ? 0 : -1));
00412       return ES_OK;
00413     }
00414 
00415     // Limits values such that no overflow can occur
00416     assert(Limits::max == -Limits::min);
00417     {
00418       int l = ops.fnroot(Limits::max);
00419       GECODE_ME_CHECK(x0.lq(home,l));
00420       GECODE_ME_CHECK(x0.gq(home,-l));
00421     }
00422 
00423     if ((x0.min() >= 0) || ((x1.min() >= 0) && !ops.even()))
00424       return PowPlusDom<IntView,IntView,Ops>::post(home,x0,x1,ops);
00425 
00426     if (ops.even() && (x0.max() <= 0))
00427       return PowPlusDom<MinusView,IntView,Ops>
00428         ::post(home,MinusView(x0),x1,ops);
00429 
00430     if (!ops.even() && ((x0.max() <= 0) || (x1.max() <= 0)))
00431       return PowPlusDom<MinusView,MinusView,Ops>
00432         ::post(home,MinusView(x0),MinusView(x1),ops);
00433 
00434     if (ops.even())
00435       GECODE_ME_CHECK(x1.gq(home,0));
00436 
00437     assert((x0.min() < 0) && (x0.max() > 0));
00438 
00439     if (ops.even()) {
00440       GECODE_ME_CHECK(x1.lq(home,std::max(ops.pow(x0.min()),
00441                                           ops.pow(x0.max()))));
00442     } else {
00443       GECODE_ME_CHECK(x1.lq(home,ops.pow(x0.max())));
00444       GECODE_ME_CHECK(x1.gq(home,ops.pow(x0.min())));
00445     }
00446 
00447     (void) new (home) PowDom<Ops>(home,x0,x1,ops);
00448     return ES_OK;
00449   }
00450 
00451   template<class Ops>
00452   forceinline
00453   PowDom<Ops>::PowDom(Space& home, bool share, PowDom<Ops>& p)
00454     : BinaryPropagator<IntView,PC_INT_DOM>(home,share,p),
00455       ops(p.ops) {}
00456 
00457   template<class Ops>
00458   Actor*
00459   PowDom<Ops>::copy(Space& home, bool share) {
00460     return new (home) PowDom<Ops>(home,share,*this);
00461   }
00462 
00463   template<class Ops>
00464   PropCost
00465   PowDom<Ops>::cost(const Space&, const ModEventDelta& med) const {
00466     if (IntView::me(med) == ME_INT_VAL)
00467       return PropCost::unary(PropCost::LO);
00468     else if (IntView::me(med) == ME_INT_DOM)
00469       return PropCost::binary(PropCost::HI);
00470     else
00471       return PropCost::binary(PropCost::LO);
00472   }
00473 
00474   template<class Ops>
00475   ExecStatus
00476   PowDom<Ops>::propagate(Space& home, const ModEventDelta& med) {
00477     if ((x0.min() >= 0) || ((x1.min() >= 0) && !ops.even()))
00478       GECODE_REWRITE(*this,(PowPlusDom<IntView,IntView,Ops>
00479                             ::post(home(*this),x0,x1,ops)));
00480 
00481     if (ops.even() && (x0.max() <= 0))
00482       GECODE_REWRITE(*this,(PowPlusDom<MinusView,IntView,Ops>
00483                             ::post(home(*this),MinusView(x0),x1,ops)));
00484 
00485     if (!ops.even() && ((x0.max() <= 0) || (x1.max() <= 0)))
00486       GECODE_REWRITE(*this,(PowPlusDom<MinusView,MinusView,Ops>
00487                             ::post(home(*this),MinusView(x0),
00488                                    MinusView(x1),ops)));
00489 
00490     if (IntView::me(med) != ME_INT_DOM) {
00491       GECODE_ES_CHECK(prop_pow_bnd<Ops>(home,x0,x1,ops));
00492       if (x0.assigned() && x1.assigned())
00493         return (ops.pow(x0.val()) == x1.val()) ?
00494           home.ES_SUBSUMED(*this) : ES_FAILED;
00495 
00496       return home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
00497     }
00498 
00499     Region r(home);
00500     if (ops.even()) {
00501       ViewValues<IntView> i(x0), j(x0);
00502       using namespace Iter::Values;
00503       Positive<ViewValues<IntView> > pos(i);
00504       Negative<ViewValues<IntView> > neg(j);
00505       Minus m(r,neg);
00506 
00507       ValuesMapPow<Ops> vmp(ops);
00508       Map<Positive<ViewValues<IntView> >,ValuesMapPow<Ops>,true> sp(pos,vmp);
00509       Map<Minus,ValuesMapPow<Ops>,true> sm(m,vmp);
00510       Union<Map<Positive<ViewValues<IntView> >,ValuesMapPow<Ops>,true>,
00511         Map<Minus,ValuesMapPow<Ops>,true> > u(sp,sm);
00512       GECODE_ME_CHECK(x1.inter_v(home,u,false));
00513     } else {
00514       ViewValues<IntView> v0(x0);
00515       ValuesMapPow<Ops> vmp(ops);
00516       Iter::Values::Map<ViewValues<IntView>,ValuesMapPow<Ops> > s0(v0,vmp);
00517       GECODE_ME_CHECK(x1.inter_v(home,s0,false));
00518     }
00519 
00520     if (ops.even()) {
00521       ViewValues<IntView> i(x1), j(x1);
00522       using namespace Iter::Values;
00523       ValuesMapNroot<Ops> vmn(ops);
00524       Map<ViewValues<IntView>,ValuesMapNroot<Ops>,true> si(i,vmn), sj(j,vmn);
00525       Minus mi(r,si);
00526       Union<Minus,
00527         Map<ViewValues<IntView>,ValuesMapNroot<Ops>,true> > u(mi,sj);
00528       GECODE_ME_CHECK(x0.inter_v(home,u,false));
00529     } else {
00530       ViewValues<IntView> v1(x1);
00531       ValuesMapNrootSigned<Ops> vmn(ops);
00532       Iter::Values::Map<ViewValues<IntView>,ValuesMapNrootSigned<Ops> >
00533         s1(v1,vmn);
00534       GECODE_ME_CHECK(x0.inter_v(home,s1,false));
00535     }
00536 
00537     return x0.assigned() ? home.ES_SUBSUMED(*this) : ES_FIX;
00538   }
00539 
00540 }}}
00541 
00542 // STATISTICS: int-prop
00543