Generated on Thu Apr 11 13:59:04 2019 for Gecode by doxygen 1.6.3

mult.cpp

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, 2004
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/arithmetic.hh>
00035 
00036 namespace Gecode { namespace Int { namespace Arithmetic {
00037 
00038   /*
00039    * Bounds consistent multiplication
00040    *
00041    */
00042   Actor*
00043   MultBnd::copy(Space& home) {
00044     return new (home) MultBnd(home,*this);
00045   }
00046 
00047   ExecStatus
00048   MultBnd::propagate(Space& home, const ModEventDelta&) {
00049     if (pos(x0)) {
00050       if (pos(x1) || pos(x2)) goto rewrite_ppp;
00051       if (neg(x1) || neg(x2)) goto rewrite_pnn;
00052       goto prop_pxx;
00053     }
00054     if (neg(x0)) {
00055       if (neg(x1) || pos(x2)) goto rewrite_nnp;
00056       if (pos(x1) || neg(x2)) goto rewrite_npn;
00057       goto prop_nxx;
00058     }
00059     if (pos(x1)) {
00060       if (pos(x2)) goto rewrite_ppp;
00061       if (neg(x2)) goto rewrite_npn;
00062       goto prop_xpx;
00063     }
00064     if (neg(x1)) {
00065       if (pos(x2)) goto rewrite_nnp;
00066       if (neg(x2)) goto rewrite_pnn;
00067       goto prop_xnx;
00068     }
00069 
00070     assert(any(x0) && any(x1));
00071     GECODE_ME_CHECK(x2.lq(home,std::max(mll(x0.max(),x1.max()),
00072                                         mll(x0.min(),x1.min()))));
00073     GECODE_ME_CHECK(x2.gq(home,std::min(mll(x0.min(),x1.max()),
00074                                         mll(x0.max(),x1.min()))));
00075 
00076     if (x0.assigned()) {
00077       assert((x0.val() == 0) && (x2.val() == 0));
00078       return home.ES_SUBSUMED(*this);
00079     }
00080 
00081     if (x1.assigned()) {
00082       assert((x1.val() == 0) && (x2.val() == 0));
00083       return home.ES_SUBSUMED(*this);
00084     }
00085 
00086     return ES_NOFIX;
00087 
00088   prop_xpx:
00089     std::swap(x0,x1);
00090   prop_pxx:
00091     assert(pos(x0) && any(x1) && any(x2));
00092 
00093     GECODE_ME_CHECK(x2.lq(home,mll(x0.max(),x1.max())));
00094     GECODE_ME_CHECK(x2.gq(home,mll(x0.max(),x1.min())));
00095 
00096     if (pos(x2)) goto rewrite_ppp;
00097     if (neg(x2)) goto rewrite_pnn;
00098 
00099     GECODE_ME_CHECK(x1.lq(home,floor_div_xp(x2.max(),x0.min())));
00100     GECODE_ME_CHECK(x1.gq(home,ceil_div_xp(x2.min(),x0.min())));
00101 
00102     if (x0.assigned() && x1.assigned()) {
00103       GECODE_ME_CHECK(x2.eq(home,mll(x0.val(),x1.val())));
00104       return home.ES_SUBSUMED(*this);
00105     }
00106 
00107     return ES_NOFIX;
00108 
00109   prop_xnx:
00110     std::swap(x0,x1);
00111   prop_nxx:
00112     assert(neg(x0) && any(x1) && any(x2));
00113 
00114     GECODE_ME_CHECK(x2.lq(home,mll(x0.min(),x1.min())));
00115     GECODE_ME_CHECK(x2.gq(home,mll(x0.min(),x1.max())));
00116 
00117     if (pos(x2)) goto rewrite_nnp;
00118     if (neg(x2)) goto rewrite_npn;
00119 
00120     GECODE_ME_CHECK(x1.lq(home,floor_div_xx(x2.min(),x0.max())));
00121     GECODE_ME_CHECK(x1.gq(home,ceil_div_xx(x2.max(),x0.max())));
00122 
00123     if (x0.assigned() && x1.assigned()) {
00124       GECODE_ME_CHECK(x2.eq(home,mll(x0.val(),x1.val())));
00125       return home.ES_SUBSUMED(*this);
00126     }
00127 
00128     return ES_NOFIX;
00129 
00130   rewrite_ppp:
00131     GECODE_REWRITE(*this,(MultPlusBnd<IntView,IntView,IntView>
00132                          ::post(home(*this),x0,x1,x2)));
00133   rewrite_nnp:
00134     GECODE_REWRITE(*this,(MultPlusBnd<MinusView,MinusView,IntView>
00135                          ::post(home(*this),MinusView(x0),MinusView(x1),x2)));
00136   rewrite_pnn:
00137     std::swap(x0,x1);
00138   rewrite_npn:
00139     GECODE_REWRITE(*this,(MultPlusBnd<MinusView,IntView,MinusView>
00140                          ::post(home(*this),MinusView(x0),x1,MinusView(x2))));
00141   }
00142 
00143   ExecStatus
00144   MultBnd::post(Home home, IntView x0, IntView x1, IntView x2) {
00145     if (x0 == x1) {
00146       SqrOps ops;
00147       return PowBnd<SqrOps>::post(home,x0,x2,ops);
00148     }
00149     if (x0 == x2)
00150       return MultZeroOne<IntView,PC_INT_BND>::post(home,x0,x1);
00151     if (x1 == x2)
00152       return MultZeroOne<IntView,PC_INT_BND>::post(home,x1,x0);
00153     if (pos(x0)) {
00154       if (pos(x1) || pos(x2)) goto post_ppp;
00155       if (neg(x1) || neg(x2)) goto post_pnn;
00156     } else if (neg(x0)) {
00157       if (neg(x1) || pos(x2)) goto post_nnp;
00158       if (pos(x1) || neg(x2)) goto post_npn;
00159     } else if (pos(x1)) {
00160       if (pos(x2)) goto post_ppp;
00161       if (neg(x2)) goto post_npn;
00162     } else if (neg(x1)) {
00163       if (pos(x2)) goto post_nnp;
00164       if (neg(x2)) goto post_pnn;
00165     }
00166     {
00167       long long int a = mll(x0.min(),x1.min());
00168       long long int b = mll(x0.min(),x1.max());
00169       long long int c = mll(x0.max(),x1.min());
00170       long long int d = mll(x0.max(),x1.max());
00171       GECODE_ME_CHECK(x2.gq(home,std::min(std::min(a,b),std::min(c,d))));
00172       GECODE_ME_CHECK(x2.lq(home,std::max(std::max(a,b),std::max(c,d))));
00173       (void) new (home) MultBnd(home,x0,x1,x2);
00174     }
00175     return ES_OK;
00176 
00177   post_ppp:
00178     return MultPlusBnd<IntView,IntView,IntView>
00179       ::post(home,x0,x1,x2);
00180   post_nnp:
00181     return MultPlusBnd<MinusView,MinusView,IntView>
00182       ::post(home,MinusView(x0),MinusView(x1),x2);
00183   post_pnn:
00184     std::swap(x0,x1);
00185   post_npn:
00186     return MultPlusBnd<MinusView,IntView,MinusView>
00187       ::post(home,MinusView(x0),x1,MinusView(x2));
00188   }
00189 
00190 
00191 
00192   /*
00193    * Domain consistent multiplication
00194    *
00195    */
00196   Actor*
00197   MultDom::copy(Space& home) {
00198     return new (home) MultDom(home,*this);
00199   }
00200 
00201   PropCost
00202   MultDom::cost(const Space&, const ModEventDelta& med) const {
00203     if (IntView::me(med) == ME_INT_DOM)
00204       return PropCost::ternary(PropCost::HI);
00205     else
00206       return PropCost::ternary(PropCost::LO);
00207   }
00208 
00209   ExecStatus
00210   MultDom::propagate(Space& home, const ModEventDelta& med) {
00211     if (IntView::me(med) != ME_INT_DOM) {
00212       if (pos(x0)) {
00213         if (pos(x1) || pos(x2)) goto rewrite_ppp;
00214         if (neg(x1) || neg(x2)) goto rewrite_pnn;
00215         goto prop_pxx;
00216       }
00217       if (neg(x0)) {
00218         if (neg(x1) || pos(x2)) goto rewrite_nnp;
00219         if (pos(x1) || neg(x2)) goto rewrite_npn;
00220         goto prop_nxx;
00221       }
00222       if (pos(x1)) {
00223         if (pos(x2)) goto rewrite_ppp;
00224         if (neg(x2)) goto rewrite_npn;
00225         goto prop_xpx;
00226       }
00227       if (neg(x1)) {
00228         if (pos(x2)) goto rewrite_nnp;
00229         if (neg(x2)) goto rewrite_pnn;
00230         goto prop_xnx;
00231       }
00232 
00233       assert(any(x0) && any(x1));
00234       GECODE_ME_CHECK(x2.lq(home,std::max(mll(x0.max(),x1.max()),
00235                                           mll(x0.min(),x1.min()))));
00236       GECODE_ME_CHECK(x2.gq(home,std::min(mll(x0.min(),x1.max()),
00237                                           mll(x0.max(),x1.min()))));
00238 
00239       if (x0.assigned()) {
00240         assert((x0.val() == 0) && (x2.val() == 0));
00241         return home.ES_SUBSUMED(*this);
00242       }
00243 
00244       if (x1.assigned()) {
00245         assert((x1.val() == 0) && (x2.val() == 0));
00246         return home.ES_SUBSUMED(*this);
00247       }
00248 
00249       return home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
00250 
00251     prop_xpx:
00252       std::swap(x0,x1);
00253     prop_pxx:
00254       assert(pos(x0) && any(x1) && any(x2));
00255 
00256       GECODE_ME_CHECK(x2.lq(home,mll(x0.max(),x1.max())));
00257       GECODE_ME_CHECK(x2.gq(home,mll(x0.max(),x1.min())));
00258 
00259       if (pos(x2)) goto rewrite_ppp;
00260       if (neg(x2)) goto rewrite_pnn;
00261 
00262       GECODE_ME_CHECK(x1.lq(home,floor_div_xp(x2.max(),x0.min())));
00263       GECODE_ME_CHECK(x1.gq(home,ceil_div_xp(x2.min(),x0.min())));
00264 
00265       if (x0.assigned() && x1.assigned()) {
00266         GECODE_ME_CHECK(x2.eq(home,mll(x0.val(),x1.val())));
00267         return home.ES_SUBSUMED(*this);
00268       }
00269 
00270       return home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
00271 
00272     prop_xnx:
00273       std::swap(x0,x1);
00274     prop_nxx:
00275       assert(neg(x0) && any(x1) && any(x2));
00276 
00277       GECODE_ME_CHECK(x2.lq(home,mll(x0.min(),x1.min())));
00278       GECODE_ME_CHECK(x2.gq(home,mll(x0.min(),x1.max())));
00279 
00280       if (pos(x2)) goto rewrite_nnp;
00281       if (neg(x2)) goto rewrite_npn;
00282 
00283       GECODE_ME_CHECK(x1.lq(home,floor_div_xx(x2.min(),x0.max())));
00284       GECODE_ME_CHECK(x1.gq(home,ceil_div_xx(x2.max(),x0.max())));
00285 
00286       if (x0.assigned() && x1.assigned()) {
00287         GECODE_ME_CHECK(x2.eq(home,mll(x0.val(),x1.val())));
00288         return home.ES_SUBSUMED(*this);
00289       }
00290 
00291       return home.ES_NOFIX_PARTIAL(*this,IntView::med(ME_INT_DOM));
00292 
00293     rewrite_ppp:
00294       GECODE_REWRITE(*this,(MultPlusDom<IntView,IntView,IntView>
00295                            ::post(home(*this),x0,x1,x2)));
00296     rewrite_nnp:
00297       GECODE_REWRITE(*this,(MultPlusDom<MinusView,MinusView,IntView>
00298                            ::post(home(*this),
00299                                   MinusView(x0),MinusView(x1),x2)));
00300     rewrite_pnn:
00301       std::swap(x0,x1);
00302     rewrite_npn:
00303       GECODE_REWRITE(*this,(MultPlusDom<MinusView,IntView,MinusView>
00304                            ::post(home(*this),
00305                                   MinusView(x0),x1,MinusView(x2))));
00306     }
00307     return prop_mult_dom<IntView>(home,*this,x0,x1,x2);
00308   }
00309 
00310   ExecStatus
00311   MultDom::post(Home home, IntView x0, IntView x1, IntView x2) {
00312     if (x0 == x1) {
00313       SqrOps ops;
00314       return PowDom<SqrOps>::post(home,x0,x2,ops);
00315     }
00316     if (x0 == x2)
00317       return MultZeroOne<IntView,PC_INT_DOM>::post(home,x0,x1);
00318     if (x1 == x2)
00319       return MultZeroOne<IntView,PC_INT_DOM>::post(home,x1,x0);
00320     if (pos(x0)) {
00321       if (pos(x1) || pos(x2)) goto post_ppp;
00322       if (neg(x1) || neg(x2)) goto post_pnn;
00323     } else if (neg(x0)) {
00324       if (neg(x1) || pos(x2)) goto post_nnp;
00325       if (pos(x1) || neg(x2)) goto post_npn;
00326     } else if (pos(x1)) {
00327       if (pos(x2)) goto post_ppp;
00328       if (neg(x2)) goto post_npn;
00329     } else if (neg(x1)) {
00330       if (pos(x2)) goto post_nnp;
00331       if (neg(x2)) goto post_pnn;
00332     }
00333     {
00334       long long int a = mll(x0.min(),x1.min());
00335       long long int b = mll(x0.min(),x1.max());
00336       long long int c = mll(x0.max(),x1.min());
00337       long long int d = mll(x0.max(),x1.max());
00338       GECODE_ME_CHECK(x2.gq(home,std::min(std::min(a,b),std::min(c,d))));
00339       GECODE_ME_CHECK(x2.lq(home,std::max(std::max(a,b),std::max(c,d))));
00340       (void) new (home) MultDom(home,x0,x1,x2);
00341     }
00342     return ES_OK;
00343 
00344   post_ppp:
00345     return MultPlusDom<IntView,IntView,IntView>
00346       ::post(home,x0,x1,x2);
00347   post_nnp:
00348     return MultPlusDom<MinusView,MinusView,IntView>
00349       ::post(home,MinusView(x0),MinusView(x1),x2);
00350   post_pnn:
00351     std::swap(x0,x1);
00352   post_npn:
00353     return MultPlusDom<MinusView,IntView,MinusView>
00354       ::post(home,MinusView(x0),x1,MinusView(x2));
00355   }
00356 
00357 }}}
00358 
00359 // STATISTICS: int-prop
00360