mult.cpp

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