divmod.icc

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Guido Tack, 2008
00008  *
00009  *  Last modified:
00010  *     $Date: 2008-07-11 16:57:02 +0200 (Fri, 11 Jul 2008) $ by $Author: tack $
00011  *     $Revision: 7368 $
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/linear.hh"
00039 
00040 namespace Gecode { namespace Int { namespace Arithmetic {
00041 
00042   /*
00043    * Positive bounds consistent division
00044    *
00045    */
00046   template <class Val, class VA, class VB, class VC, bool towardsMinInf>
00047   forceinline ExecStatus
00048   prop_div_plus_bnd(Space* home, Propagator* p, VA x0, VB x1, VC x2) {
00049     assert(pos(x0) && pos(x1) && !neg(x2));
00050     bool mod;
00051     do {
00052       mod = false;
00053       {
00054         ModEvent me;
00055         if (towardsMinInf)
00056           me = x2.lq(home,f_d_p<Val>(x0.max(),x1.min()));
00057         else
00058           me = x2.lq(home,c_d_p<Val>(x0.max(),x1.min()));
00059         if (me_failed(me)) return ES_FAILED;
00060         mod |= me_modified(me);
00061       }
00062       {
00063         ModEvent me;
00064         if (towardsMinInf)
00065           me = x2.gq(home,f_d_p<Val>(x0.min(),x1.max()));
00066         else
00067           me = x2.gq(home,c_d_p<Val>(x0.min(),x1.max()));
00068         if (me_failed(me)) return ES_FAILED;
00069         mod |= me_modified(me);
00070       }
00071       {
00072         ModEvent me;
00073         if (towardsMinInf)
00074           me = x0.le(home,m<Val>(x1.max(),
00075                                  static_cast<Val>(x2.max())+
00076                                  static_cast<Val>(1)));
00077         else
00078           me = x0.lq(home,m<Val>(x1.max(),x2.max()));
00079         if (me_failed(me)) return ES_FAILED;
00080         mod |= me_modified(me);
00081       }
00082       {
00083         ModEvent me;
00084         if (towardsMinInf)
00085           me = x0.gq(home,m<Val>(x1.min(),x2.min()));
00086         else
00087           me = x0.gr(home,m<Val>(x1.min(),
00088                                  static_cast<Val>(x2.min())-
00089                                  static_cast<Val>(1)));
00090         if (me_failed(me)) return ES_FAILED;
00091         mod |= me_modified(me);
00092       }
00093       {
00094         if (x2.min() > 0) {
00095           ModEvent me;
00096           if (towardsMinInf)
00097             me = x1.lq(home,f_d_p<Val>(x0.max(),x2.min()));
00098           else if (x2.min() != 1) {
00099             me = x1.lq(home,c_d_p<Val>(x0.max(),
00100                                        static_cast<Val>(x2.min())-
00101                                        static_cast<Val>(1)));
00102           } else
00103             me = ME_INT_NONE;
00104           if (me_failed(me)) return ES_FAILED;
00105           mod |= me_modified(me);
00106         }
00107       }
00108       {
00109         ModEvent me;
00110         if (towardsMinInf)
00111           me = x1.gq(home,c_d_p<Val>(x0.min(),
00112             static_cast<Val>(x2.max())+static_cast<Val>(1)));
00113         else
00114           me = x1.gq(home,f_d_p<Val>(x0.min(),
00115             static_cast<Val>(x2.max())+static_cast<Val>(1)));
00116         if (me_failed(me)) return ES_FAILED;
00117         mod |= me_modified(me);
00118       }
00119     } while (mod);
00120     return x0.assigned() && x1.assigned() ?
00121       ES_SUBSUMED(p,sizeof(*p)) : ES_FIX;
00122   }
00123 
00124   template <class Val, class VA, class VB, class VC, bool towardsMinInf>
00125   forceinline
00126   DivPlusBnd<Val,VA,VB,VC,towardsMinInf>
00127   ::DivPlusBnd(Space* home, VA x0, VB x1, VC x2)
00128     : MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>
00129   (home,x0,x1,x2) {}
00130 
00131   template <class Val, class VA, class VB, class VC, bool towardsMinInf>
00132   forceinline
00133   DivPlusBnd<Val,VA,VB,VC,towardsMinInf>
00134   ::DivPlusBnd(Space* home, bool share, 
00135                DivPlusBnd<Val,VA,VB,VC,towardsMinInf>& p)
00136     : MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>
00137   (home,share,p) {}
00138 
00139   template <class Val, class VA, class VB, class VC, bool towardsMinInf>
00140   Actor*
00141   DivPlusBnd<Val,VA,VB,VC,towardsMinInf>::copy(Space* home, bool share) {
00142     return new (home) DivPlusBnd<Val,VA,VB,VC,towardsMinInf>(home,
00143                                                              share,*this);
00144   }
00145 
00146   template <class Val, class VA, class VB, class VC, bool towardsMinInf>
00147   ExecStatus
00148   DivPlusBnd<Val,VA,VB,VC,towardsMinInf>
00149   ::propagate(Space* home, ModEventDelta) {
00150     return prop_div_plus_bnd<Val,VA,VB,VC,towardsMinInf>(home,this,x0,x1,x2);
00151   }
00152 
00153   template <class Val, class VA, class VB, class VC, bool towardsMinInf>
00154   forceinline ExecStatus
00155   DivPlusBnd<Val,VA,VB,VC,towardsMinInf>
00156   ::post(Space* home, VA x0, VB x1, VC x2) {
00157     GECODE_ME_CHECK(x0.gr(home,0));
00158     GECODE_ME_CHECK(x1.gr(home,0));
00159     if (towardsMinInf) {
00160       GECODE_ME_CHECK(x2.gq(home,floor(static_cast<double>(x0.min()) / 
00161                                        static_cast<double>(x1.max()))));
00162     } else {
00163       GECODE_ME_CHECK(x2.gq(home,ceil(static_cast<double>(x0.min()) / 
00164                                       static_cast<double>(x1.max()))));      
00165     }
00166     (void)
00167       new (home) DivPlusBnd<double,VA,VB,VC,towardsMinInf>(home,x0,x1,x2);
00168     return ES_OK;
00169   }
00170 
00171   template <class Val, class VA, class VB, class VC, bool towardsMinInf>
00172   forceinline void
00173   DivPlusBnd<Val,VA,VB,VC,towardsMinInf>
00174   ::post(Space* home, Reflection::VarMap& vars,
00175          const Reflection::ActorSpec& spec) {
00176      spec.checkArity(3);
00177      VA x0(home, vars, spec[0]);
00178      VB x1(home, vars, spec[1]);
00179      VC x2(home, vars, spec[2]);
00180      (void) new (home) DivPlusBnd<Val,VA,VB,VC,towardsMinInf>(home,x0,x1,x2);
00181   }
00182 
00183   template <class Val, class VA, class VB, class VC, bool towardsMinInf>
00184   Support::Symbol
00185   DivPlusBnd<Val,VA,VB,VC,towardsMinInf>::ati(void) {
00186     return Reflection::mangle<VA,VB,VC,Val>
00187       ("Gecode::Int::Arithmetic::DivPlusBnd",towardsMinInf);
00188   }
00189 
00190   template <class Val, class VA, class VB, class VC, bool towardsMinInf>
00191   Reflection::ActorSpec
00192   DivPlusBnd<Val,VA,VB,VC,towardsMinInf>
00193   ::spec(const Space* home, Reflection::VarMap& m) const {
00194     return MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>
00195       ::spec(home, m, ati());
00196   }
00197 
00198 
00199   /*
00200    * Bounds consistent multiplication
00201    *
00202    */
00203   template <class View>
00204   forceinline
00205   DivBnd<View>::DivBnd(Space* home, View x0, View x1, View x2)
00206     : TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {}
00207 
00208   template <class View>
00209   forceinline
00210   DivBnd<View>::DivBnd(Space* home, bool share, DivBnd<View>& p)
00211     : TernaryPropagator<View,PC_INT_BND>(home,share,p) {}
00212 
00213   template <class View>
00214   Actor*
00215   DivBnd<View>::copy(Space* home, bool share) {
00216     return new (home) DivBnd<View>(home,share,*this);
00217   }
00218 
00219   template <class View>
00220   ExecStatus
00221   DivBnd<View>::propagate(Space* home, ModEventDelta) {
00222     if (pos(x1)) {
00223       if (pos(x2) || pos(x0)) goto rewrite_ppp;
00224       if (neg(x2) || neg(x0)) goto rewrite_npn;
00225       goto prop_xpx;
00226     }
00227     if (neg(x1)) {
00228       if (neg(x2) || pos(x0)) goto rewrite_pnn;
00229       if (pos(x2) || neg(x0)) goto rewrite_nnp;
00230       goto prop_xnx;
00231     }
00232     if (pos(x2)) {
00233       if (pos(x0)) goto rewrite_ppp;
00234       if (neg(x0)) goto rewrite_nnp;
00235       goto prop_xxp;
00236     }
00237     if (neg(x2)) {
00238       if (pos(x0)) goto rewrite_pnn;
00239       if (neg(x0)) goto rewrite_npn;
00240       goto prop_xxn;
00241     }
00242     assert(any(x1) && any(x2));
00243 
00244     GECODE_ME_CHECK(x0.le(home,std::max(m<double>(x1.max(),x2.max()+1),
00245                                         m<double>(x1.min(),x2.min()-1))));
00246     GECODE_ME_CHECK(x0.gq(home,std::min(m<double>(x1.min(),x2.max()+1),
00247                                         m<double>(x1.max(),x2.min()-1))));
00248 
00249     return ES_NOFIX;
00250 
00251   prop_xxp:
00252     assert(any(x0) && any(x1) && pos(x2));
00253 
00254     GECODE_ME_CHECK(x0.le(home, m<double>(x1.max(),x2.max()+1)));
00255     GECODE_ME_CHECK(x0.gq(home, m<double>(x1.min(),x2.max()+1)));
00256 
00257     if (pos(x0)) goto rewrite_ppp;
00258     if (neg(x0)) goto rewrite_nnp;
00259 
00260     GECODE_ME_CHECK(x1.lq(home,f_d_p<double>(x0.max(),x2.min())));
00261     GECODE_ME_CHECK(x1.gq(home,c_d(x0.min(),x2.min())));
00262 
00263     if (x0.assigned() && x1.assigned()) {
00264       GECODE_ME_CHECK(x2.eq(home,f_d(x0.val(),x1.val())));
00265       return ES_SUBSUMED(this,sizeof(*this));
00266     }
00267 
00268     return ES_NOFIX;
00269   prop_xpx:
00270     assert(any(x0) && pos(x1) && any(x2));
00271 
00272     GECODE_ME_CHECK(x0.le(home, m<double>(x1.max(),x2.max()+1)));
00273     GECODE_ME_CHECK(x0.gq(home, m<double>(x1.max(),x2.min()-1)));
00274 
00275     if (pos(x0)) goto rewrite_ppp;
00276     if (neg(x0)) goto rewrite_npn;
00277 
00278     GECODE_ME_CHECK(x2.lq(home,f_d(x0.max(),x1.min())));
00279     GECODE_ME_CHECK(x2.gq(home,f_d(x0.min(),x1.min())));
00280 
00281     if (x0.assigned() && x1.assigned()) {
00282       GECODE_ME_CHECK(x2.eq(home,f_d(x0.val(),x1.val())));
00283       return ES_SUBSUMED(this,sizeof(*this));
00284     }
00285 
00286     return ES_NOFIX;
00287 
00288   prop_xxn:
00289     assert(any(x0) && any(x1) && neg(x2));
00290 
00291     GECODE_ME_CHECK(x0.le(home, m<double>(x1.min(),x2.min()-1)));
00292     GECODE_ME_CHECK(x0.gq(home, m<double>(x1.max(),x2.min()-1)));
00293 
00294     if (pos(x0)) goto rewrite_pnn;
00295     if (neg(x0)) goto rewrite_npn;
00296 
00297     if (x2.max() != -1)
00298       GECODE_ME_CHECK(x1.lq(home,c_d(x0.min(),x2.max()+1)));
00299     if (x2.max() != -1)
00300       GECODE_ME_CHECK(x1.gq(home,c_d(x0.max(),x2.max()+1)));
00301 
00302     if (x0.assigned() && x1.assigned()) {
00303       GECODE_ME_CHECK(x2.eq(home,f_d(x0.val(),x1.val())));
00304       return ES_SUBSUMED(this,sizeof(*this));
00305     }
00306     return ES_NOFIX;
00307 
00308   prop_xnx:
00309     assert(any(x0) && neg(x1) && any(x2));
00310 
00311     GECODE_ME_CHECK(x0.le(home, m<double>(x1.min(),x2.min()-1)));
00312     GECODE_ME_CHECK(x0.gq(home, m<double>(x1.min(),x2.max()+1)));
00313 
00314     if (pos(x0)) goto rewrite_pnn;
00315     if (neg(x0)) goto rewrite_nnp;
00316 
00317     GECODE_ME_CHECK(x2.lq(home,f_d(x0.min(),x1.max())));
00318     GECODE_ME_CHECK(x2.gq(home,f_d(x0.max(),x1.max())));
00319 
00320     if (x0.assigned() && x1.assigned()) {
00321       GECODE_ME_CHECK(x2.eq(home,f_d(x0.val(),x1.val())));
00322       return ES_SUBSUMED(this,sizeof(*this));
00323     }
00324     return ES_NOFIX;
00325 
00326   rewrite_ppp:
00327     GECODE_REWRITE(this,(DivPlusBnd<double,IntView,IntView,IntView>
00328                          ::post(home,x0,x1,x2)));
00329   rewrite_nnp:
00330     GECODE_REWRITE(this,(DivPlusBnd<double,MinusView,MinusView,IntView>
00331                          ::post(home,x0,x1,x2)));
00332   rewrite_pnn:
00333     GECODE_REWRITE(this,(DivPlusBnd<double,IntView,MinusView,MinusView,false>
00334                          ::post(home,x0,x1,x2)));
00335   rewrite_npn:
00336     GECODE_REWRITE(this,(DivPlusBnd<double,MinusView,IntView,MinusView,false>
00337                          ::post(home,x0,x1,x2)));
00338   }
00339 
00340   template <class View>
00341   ExecStatus
00342   DivBnd<View>::post(Space* home, View x0, View x1, View x2) {
00343     GECODE_ME_CHECK(x1.nq(home, 0));
00344     if (pos(x0)) {
00345       if (pos(x1) || pos(x2)) goto post_ppp;
00346       if (neg(x1) || neg(x2)) goto post_pnn;
00347     } else if (neg(x0)) {
00348       if (neg(x1) || pos(x2)) goto post_nnp;
00349       if (pos(x1) || neg(x2)) goto post_npn;
00350     } else if (pos(x1)) {
00351       if (pos(x2)) goto post_ppp;
00352       if (neg(x2)) goto post_npn;
00353     } else if (neg(x1)) {
00354       if (pos(x2)) goto post_nnp;
00355       if (neg(x2)) goto post_pnn;
00356     }
00357     (void) new (home) DivBnd<View>(home,x0,x1,x2);
00358     return ES_OK;
00359 
00360   post_ppp:
00361     return DivPlusBnd<double,IntView,IntView,IntView>::post(home,x0,x1,x2);
00362   post_nnp:
00363     return DivPlusBnd<double,MinusView,MinusView,IntView>::post(home,x0,x1,x2);
00364   post_pnn:
00365     return DivPlusBnd<double,IntView,MinusView,MinusView,false>::post(home,x0,x1,x2);
00366   post_npn:
00367     return DivPlusBnd<double,MinusView,IntView,MinusView,false>::post(home,x0,x1,x2);
00368   }
00369 
00370   template <class View>
00371   forceinline void
00372   DivBnd<View>::post(Space* home, Reflection::VarMap& vars,
00373                    const Reflection::ActorSpec& spec) {
00374      spec.checkArity(3);
00375      View x0(home, vars, spec[0]);
00376      View x1(home, vars, spec[1]);
00377      View x2(home, vars, spec[2]);
00378      (void) new (home) DivBnd<View>(home,x0,x1,x2);
00379   }
00380 
00381   template <class View>
00382   Support::Symbol
00383   DivBnd<View>::ati(void) {
00384     return Reflection::mangle<View>("Gecode::Int::Arithmetic::DivBnd");
00385   }
00386 
00387   template <class View>
00388   Reflection::ActorSpec
00389   DivBnd<View>::spec(const Space* home, Reflection::VarMap& m) const {
00390     return TernaryPropagator<View,PC_INT_BND>::spec(home, m, ati());
00391   }
00392 
00393   /*
00394    * Propagator for x0 != 0 /\ (x1 != 0 => x0*x1>0) /\ abs(x1)<abs(x0)
00395    *
00396    */
00397 
00398   template <class View>
00399   forceinline
00400   DivMod<View>::DivMod(Space* home, View x0, View x1)
00401     : BinaryPropagator<View,PC_INT_BND>(home,x0,x1) {}
00402 
00403   template <class View>
00404   forceinline ExecStatus
00405   DivMod<View>::post(Space* home, View x0, View x1) {
00406     GECODE_ME_CHECK(x0.nq(home,0));
00407     (void) new (home) DivMod<View>(home,x0,x1);
00408     return ES_OK;
00409   }
00410 
00411   template <class View>
00412   forceinline void
00413   DivMod<View>::post(Space* home, Reflection::VarMap& vars,
00414                         const Reflection::ActorSpec& spec) {
00415      spec.checkArity(2);
00416      View x0(home, vars, spec[0]);
00417      View x1(home, vars, spec[1]);
00418      (void) new (home) DivMod<View>(home,x0,x1);
00419   }
00420 
00421   template <class View>
00422   forceinline
00423   DivMod<View>::DivMod(Space* home, bool share, 
00424                              DivMod<View>& p)
00425   : BinaryPropagator<View,PC_INT_BND>(home,share,p) {}
00426 
00427   template <class View>
00428   Actor*
00429   DivMod<View>::copy(Space* home, bool share) {
00430     return new (home) DivMod<View>(home,share,*this);
00431   }
00432 
00433   template <class View>
00434   ExecStatus
00435   DivMod<View>::propagate(Space* home, ModEventDelta) {
00436     bool signIsSame;
00437     do {
00438       signIsSame = true;
00439       // The sign of x1 and x3 is the same
00440       if (x0.min() > 0) {
00441         GECODE_ME_CHECK(x1.gq(home, 0));
00442       } else if (x0.max() < 0) {
00443         GECODE_ME_CHECK(x1.lq(home, 0));
00444       } else if (x1.min() > 0) {
00445         GECODE_ME_CHECK(x0.gr(home, 0));
00446       } else if (x1.max() < 0) {
00447         GECODE_ME_CHECK(x0.le(home, 0));
00448       } else {
00449         signIsSame = false;
00450       }
00451       
00452       // abs(x1) is less than abs(x0)
00453       int x0max = std::max(x0.max(),std::max(-x0.max(),
00454                            std::max(x0.min(),-x0.min())));
00455       GECODE_ME_CHECK(x1.le(home, x0max));
00456       GECODE_ME_CHECK(x1.gr(home, -x0max));
00457 
00458       if (x0.min() > 0) {
00459         int min = std::min(x1.min() < 0 ? -x1.min():x1.min(),
00460                            x1.max() < 0 ? -x1.max():x1.max());
00461         GECODE_ME_CHECK(x0.gr(home,min));  
00462       } else if (x0.max() < 0) {
00463         int min = std::min(x1.min() < 0 ? -x1.min():x1.min(),
00464                            x1.max() < 0 ? -x1.max():x1.max());
00465         GECODE_ME_CHECK(x0.le(home,-min));
00466       }
00467     } while (!signIsSame &&
00468              (x0.min() > 0 || x0.max() < 0 || x1.min() > 0 || x1.max() < 0));
00469 
00470     if (signIsSame) {
00471       int maxx1 = std::max(x1.min() < 0 ? -x1.min():x1.min(),
00472                            x1.max() < 0 ? -x1.max():x1.max());
00473       int minx0 = std::min(x0.min() < 0 ? -x0.min():x0.min(),
00474                            x0.max() < 0 ? -x0.max():x0.max());
00475       if (maxx1 < minx0) {
00476         return ES_SUBSUMED(this,home);
00477       }
00478     }
00479     return ES_FIX;
00480   }
00481 
00482   template <class View>
00483   Support::Symbol
00484   DivMod<View>::ati(void) {
00485     return Reflection::mangle<View>("Gecode::Int::Arithmetic::DivMod");
00486   }
00487 
00488   template <class View>
00489   Reflection::ActorSpec
00490   DivMod<View>::spec(const Space* home, Reflection::VarMap& m) const {
00491     return BinaryPropagator<View,PC_INT_BND>::spec(home, m, ati());
00492   }
00493 
00494 }}}
00495 
00496 // STATISTICS: int-prop