Generated on Thu Mar 22 10:39:33 2012 for Gecode by doxygen 1.6.3

mult.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, 2004
00008  *
00009  *  Last modified:
00010  *     $Date: 2010-06-03 13:46:55 +0200 (Thu, 03 Jun 2010) $ by $Author: schulte $
00011  *     $Revision: 11014 $
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 <cmath>
00039 #include <climits>
00040 
00041 #include <gecode/int/support-values.hh>
00042 
00043 namespace Gecode { namespace Int { namespace Arithmetic {
00044 
00045   /*
00046    * Arithmetic help functions
00047    *
00048    */
00049 
00051   template<class Val>
00052   Val m(int x, int y);
00053 
00055   template<class Val>
00056   Val m(int x, double y);
00057 
00058   template<>
00059   forceinline double
00060   m(int x, int y) {
00061     return static_cast<double>(x)*static_cast<double>(y);
00062   }
00063 
00064   template<>
00065   forceinline double
00066   m(int x, double y) {
00067     return static_cast<double>(x)*y;
00068   }
00069 
00070   template<>
00071   forceinline int
00072   m(int x, int y) {
00073     return x*y;
00074   }
00075 
00077   template<class Val>
00078   int c_d_p(int x, Val y);
00080   template<class Val>
00081   int f_d_p(int x, Val y);
00082 
00083   template<>
00084   forceinline int
00085   c_d_p<int>(int x, int y) {
00086     assert((x >= 0) && (y >= 0));
00087     return (x+y-1)/y;
00088   }
00089   template<>
00090   forceinline int
00091   c_d_p<double>(int x, double y) {
00092     assert((x >= 0) && (y >= 0));
00093     return static_cast<int>(ceil(static_cast<double>(x) / y));
00094   }
00095   template<>
00096   forceinline int
00097   f_d_p<int>(int x, int y) {
00098     assert((x >= 0) && (y >= 0));
00099     return x/y;
00100   }
00101   template<>
00102   forceinline int
00103   f_d_p<double>(int x, double y) {
00104     assert((x >= 0) && (y >= 0));
00105     return static_cast<int>(floor(static_cast<double>(x) / y));
00106   }
00107 
00108 
00110   forceinline int
00111   f_d(int x, int y) {
00112     return static_cast<int>(floor(static_cast<double>(x) /
00113                                   static_cast<double>(y)));
00114   }
00115 
00117   forceinline int
00118   c_d(int x, int y) {
00119     return static_cast<int>(ceil(static_cast<double>(x) /
00120                                  static_cast<double>(y)));
00121   }
00122 
00124   template<class View>
00125   forceinline bool
00126   pos(const View& x) {
00127     return x.min() > 0;
00128   }
00130   template<class View>
00131   forceinline bool
00132   neg(const View& x) {
00133     return x.max() < 0;
00134   }
00136   template<class View>
00137   forceinline bool
00138   any(const View& x) {
00139     return (x.min() <= 0) && (x.max() >= 0);
00140   }
00141 
00142 
00143   /*
00144    * Propagator for x * y = x
00145    *
00146    */
00147 
00148   template<class View, PropCond pc>
00149   forceinline
00150   MultZeroOne<View,pc>::MultZeroOne(Home home, View x0, View x1)
00151     : BinaryPropagator<View,pc>(home,x0,x1) {}
00152 
00153   template<class View, PropCond pc>
00154   forceinline RelTest
00155   MultZeroOne<View,pc>::equal(View x, int n) {
00156     if (pc == PC_INT_DOM) {
00157       return rtest_eq_dom(x,n);
00158     } else {
00159       return rtest_eq_bnd(x,n);
00160     }
00161   }
00162 
00163   template<class View, PropCond pc>
00164   forceinline ExecStatus
00165   MultZeroOne<View,pc>::post(Home home, View x0, View x1) {
00166     switch (equal(x0,0)) {
00167     case RT_FALSE:
00168       GECODE_ME_CHECK(x1.eq(home,1));
00169       break;
00170     case RT_TRUE:
00171       break;
00172     case RT_MAYBE:
00173       switch (equal(x1,1)) {
00174       case RT_FALSE:
00175         GECODE_ME_CHECK(x0.eq(home,0));
00176         break;
00177       case RT_TRUE:
00178         break;
00179       case RT_MAYBE:
00180         (void) new (home) MultZeroOne<View,pc>(home,x0,x1);
00181         break;
00182       default: GECODE_NEVER;
00183       }
00184       break;
00185     default: GECODE_NEVER;
00186     }
00187     return ES_OK;
00188   }
00189 
00190   template<class View, PropCond pc>
00191   forceinline
00192   MultZeroOne<View,pc>::MultZeroOne(Space& home, bool share,
00193                                     MultZeroOne<View,pc>& p)
00194     : BinaryPropagator<View,pc>(home,share,p) {}
00195 
00196   template<class View, PropCond pc>
00197   Actor*
00198   MultZeroOne<View,pc>::copy(Space& home, bool share) {
00199     return new (home) MultZeroOne<View,pc>(home,share,*this);
00200   }
00201 
00202   template<class View, PropCond pc>
00203   ExecStatus
00204   MultZeroOne<View,pc>::propagate(Space& home, const ModEventDelta&) {
00205     switch (equal(x0,0)) {
00206     case RT_FALSE:
00207       GECODE_ME_CHECK(x1.eq(home,1));
00208       break;
00209     case RT_TRUE:
00210       break;
00211     case RT_MAYBE:
00212       switch (equal(x1,1)) {
00213       case RT_FALSE:
00214         GECODE_ME_CHECK(x0.eq(home,0));
00215         break;
00216       case RT_TRUE:
00217         break;
00218       case RT_MAYBE:
00219         return ES_FIX;
00220       default: GECODE_NEVER;
00221       }
00222       break;
00223     default: GECODE_NEVER;
00224     }
00225     return home.ES_SUBSUMED(*this);
00226   }
00227 
00228 
00229   /*
00230    * Positive bounds consistent multiplication
00231    *
00232    */
00233   template<class Val, class VA, class VB, class VC>
00234   forceinline ExecStatus
00235   prop_mult_plus_bnd(Space& home, Propagator& p, VA x0, VB x1, VC x2) {
00236     assert(pos(x0) && pos(x1) && pos(x2));
00237     bool mod;
00238     do {
00239       mod = false;
00240       {
00241         ModEvent me = x2.lq(home,m<Val>(x0.max(),x1.max()));
00242         if (me_failed(me)) return ES_FAILED;
00243         mod |= me_modified(me);
00244       }
00245       {
00246         ModEvent me = x2.gq(home,m<Val>(x0.min(),x1.min()));
00247         if (me_failed(me)) return ES_FAILED;
00248         mod |= me_modified(me);
00249       }
00250       {
00251         ModEvent me = x0.lq(home,f_d_p<Val>(x2.max(),x1.min()));
00252         if (me_failed(me)) return ES_FAILED;
00253         mod |= me_modified(me);
00254       }
00255       {
00256         ModEvent me = x0.gq(home,c_d_p<Val>(x2.min(),x1.max()));
00257         if (me_failed(me)) return ES_FAILED;
00258         mod |= me_modified(me);
00259       }
00260       {
00261         ModEvent me = x1.lq(home,f_d_p<Val>(x2.max(),x0.min()));
00262         if (me_failed(me)) return ES_FAILED;
00263         mod |= me_modified(me);
00264       }
00265       {
00266         ModEvent me = x1.gq(home,c_d_p<Val>(x2.min(),x0.max()));
00267         if (me_failed(me)) return ES_FAILED;
00268         mod |= me_modified(me);
00269       }
00270     } while (mod);
00271     return x0.assigned() && x1.assigned() ?
00272       home.ES_SUBSUMED(p) : ES_FIX;
00273   }
00274 
00275   template<class Val, class VA, class VB, class VC>
00276   forceinline
00277   MultPlusBnd<Val,VA,VB,VC>::MultPlusBnd(Home home, VA x0, VB x1, VC x2)
00278     : MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>
00279   (home,x0,x1,x2) {}
00280 
00281   template<class Val, class VA, class VB, class VC>
00282   forceinline
00283   MultPlusBnd<Val,VA,VB,VC>::MultPlusBnd(Space& home, bool share,
00284                                    MultPlusBnd<Val,VA,VB,VC>& p)
00285     : MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>
00286   (home,share,p) {}
00287 
00288   template<class Val, class VA, class VB, class VC>
00289   Actor*
00290   MultPlusBnd<Val,VA,VB,VC>::copy(Space& home, bool share) {
00291     return new (home) MultPlusBnd<Val,VA,VB,VC>(home,share,*this);
00292   }
00293 
00294   template<class Val, class VA, class VB, class VC>
00295   ExecStatus
00296   MultPlusBnd<Val,VA,VB,VC>::propagate(Space& home, const ModEventDelta&) {
00297     return prop_mult_plus_bnd<Val,VA,VB,VC>(home,*this,x0,x1,x2);
00298   }
00299 
00300   template<class Val, class VA, class VB, class VC>
00301   forceinline ExecStatus
00302   MultPlusBnd<Val,VA,VB,VC>::post(Home home, VA x0, VB x1, VC x2) {
00303     GECODE_ME_CHECK(x0.gr(home,0));
00304     GECODE_ME_CHECK(x1.gr(home,0));
00305     GECODE_ME_CHECK(x2.gq(home,(static_cast<double>(x0.min()) *
00306                                 static_cast<double>(x1.min()))));
00307     double u = static_cast<double>(x0.max()) * static_cast<double>(x1.max());
00308     if (u > INT_MAX) {
00309       (void) new (home) MultPlusBnd<double,VA,VB,VC>(home,x0,x1,x2);
00310     } else {
00311       GECODE_ME_CHECK(x2.lq(home,u));
00312       (void) new (home) MultPlusBnd<int,VA,VB,VC>(home,x0,x1,x2);
00313     }
00314     return ES_OK;
00315   }
00316 
00317 
00318   /*
00319    * Bounds consistent multiplication
00320    *
00321    */
00322   template<class View>
00323   forceinline
00324   MultBnd<View>::MultBnd(Home home, View x0, View x1, View x2)
00325     : TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {}
00326 
00327   template<class View>
00328   forceinline
00329   MultBnd<View>::MultBnd(Space& home, bool share, MultBnd<View>& p)
00330     : TernaryPropagator<View,PC_INT_BND>(home,share,p) {}
00331 
00332   template<class View>
00333   Actor*
00334   MultBnd<View>::copy(Space& home, bool share) {
00335     return new (home) MultBnd<View>(home,share,*this);
00336   }
00337 
00338   template<class View>
00339   ExecStatus
00340   MultBnd<View>::propagate(Space& home, const ModEventDelta&) {
00341     if (pos(x0)) {
00342       if (pos(x1) || pos(x2)) goto rewrite_ppp;
00343       if (neg(x1) || neg(x2)) goto rewrite_pnn;
00344       goto prop_pxx;
00345     }
00346     if (neg(x0)) {
00347       if (neg(x1) || pos(x2)) goto rewrite_nnp;
00348       if (pos(x1) || neg(x2)) goto rewrite_npn;
00349       goto prop_nxx;
00350     }
00351     if (pos(x1)) {
00352       if (pos(x2)) goto rewrite_ppp;
00353       if (neg(x2)) goto rewrite_npn;
00354       goto prop_xpx;
00355     }
00356     if (neg(x1)) {
00357       if (pos(x2)) goto rewrite_nnp;
00358       if (neg(x2)) goto rewrite_pnn;
00359       goto prop_xnx;
00360     }
00361 
00362     assert(any(x0) && any(x1));
00363     GECODE_ME_CHECK(x2.lq(home,std::max(m<double>(x0.max(),x1.max()),
00364                                         m<double>(x0.min(),x1.min()))));
00365     GECODE_ME_CHECK(x2.gq(home,std::min(m<double>(x0.min(),x1.max()),
00366                                         m<double>(x0.max(),x1.min()))));
00367 
00368     if (x0.assigned()) {
00369       assert((x0.val() == 0) && (x2.val() == 0));
00370       return home.ES_SUBSUMED(*this);
00371     }
00372 
00373     if (x1.assigned()) {
00374       assert((x1.val() == 0) && (x2.val() == 0));
00375       return home.ES_SUBSUMED(*this);
00376     }
00377 
00378     return ES_NOFIX;
00379 
00380   prop_xpx:
00381     std::swap(x0,x1);
00382   prop_pxx:
00383     assert(pos(x0) && any(x1) && any(x2));
00384 
00385     GECODE_ME_CHECK(x2.lq(home,m<double>(x0.max(),x1.max())));
00386     GECODE_ME_CHECK(x2.gq(home,m<double>(x0.max(),x1.min())));
00387 
00388     if (pos(x2)) goto rewrite_ppp;
00389     if (neg(x2)) goto rewrite_pnn;
00390 
00391     GECODE_ME_CHECK(x1.lq(home,f_d(x2.max(),x0.min())));
00392     GECODE_ME_CHECK(x1.gq(home,c_d(x2.min(),x0.min())));
00393 
00394     if (x0.assigned() && x1.assigned()) {
00395       GECODE_ME_CHECK(x2.eq(home,m<double>(x0.val(),x1.val())));
00396       return home.ES_SUBSUMED(*this);
00397     }
00398 
00399     return ES_NOFIX;
00400 
00401   prop_xnx:
00402     std::swap(x0,x1);
00403   prop_nxx:
00404     assert(neg(x0) && any(x1) && any(x2));
00405 
00406     GECODE_ME_CHECK(x2.lq(home,m<double>(x0.min(),x1.min())));
00407     GECODE_ME_CHECK(x2.gq(home,m<double>(x0.min(),x1.max())));
00408 
00409     if (pos(x2)) goto rewrite_nnp;
00410     if (neg(x2)) goto rewrite_npn;
00411 
00412     GECODE_ME_CHECK(x1.lq(home,f_d(x2.min(),x0.max())));
00413     GECODE_ME_CHECK(x1.gq(home,c_d(x2.max(),x0.max())));
00414 
00415     if (x0.assigned() && x1.assigned()) {
00416       GECODE_ME_CHECK(x2.eq(home,m<double>(x0.val(),x1.val())));
00417       return home.ES_SUBSUMED(*this);
00418     }
00419 
00420     return ES_NOFIX;
00421 
00422   rewrite_ppp:
00423     GECODE_REWRITE(*this,(MultPlusBnd<double,IntView,IntView,IntView>
00424                          ::post(home(*this),x0,x1,x2)));
00425   rewrite_nnp:
00426     GECODE_REWRITE(*this,(MultPlusBnd<double,MinusView,MinusView,IntView>
00427                          ::post(home(*this),MinusView(x0),MinusView(x1),x2)));
00428   rewrite_pnn:
00429     std::swap(x0,x1);
00430   rewrite_npn:
00431     GECODE_REWRITE(*this,(MultPlusBnd<double,MinusView,IntView,MinusView>
00432                          ::post(home(*this),MinusView(x0),x1,MinusView(x2))));
00433   }
00434 
00435   template<class View>
00436   ExecStatus
00437   MultBnd<View>::post(Home home, View x0, View x1, View x2) {
00438     if (same(x0,x1))
00439       return SqrBnd<View>::post(home,x0,x2);
00440     if (same(x0,x2))
00441       return MultZeroOne<View,PC_INT_BND>::post(home,x0,x1);
00442     if (same(x1,x2))
00443       return MultZeroOne<View,PC_INT_BND>::post(home,x1,x0);
00444     if (pos(x0)) {
00445       if (pos(x1) || pos(x2)) goto post_ppp;
00446       if (neg(x1) || neg(x2)) goto post_pnn;
00447     } else if (neg(x0)) {
00448       if (neg(x1) || pos(x2)) goto post_nnp;
00449       if (pos(x1) || neg(x2)) goto post_npn;
00450     } else if (pos(x1)) {
00451       if (pos(x2)) goto post_ppp;
00452       if (neg(x2)) goto post_npn;
00453     } else if (neg(x1)) {
00454       if (pos(x2)) goto post_nnp;
00455       if (neg(x2)) goto post_pnn;
00456     }
00457     {
00458       double a =
00459         static_cast<double>(x0.min()) * static_cast<double>(x1.min());
00460       double b =
00461         static_cast<double>(x0.min()) * static_cast<double>(x1.max());
00462       double c =
00463         static_cast<double>(x0.max()) * static_cast<double>(x1.min());
00464       double d =
00465         static_cast<double>(x0.max()) * static_cast<double>(x1.max());
00466       GECODE_ME_CHECK(x2.gq(home,std::min(std::min(a,b),std::min(c,d))));
00467       GECODE_ME_CHECK(x2.lq(home,std::max(std::max(a,b),std::max(c,d))));
00468       (void) new (home) MultBnd<View>(home,x0,x1,x2);
00469     }
00470     return ES_OK;
00471 
00472   post_ppp:
00473     return MultPlusBnd<double,IntView,IntView,IntView>::post(home,x0,x1,x2);
00474   post_nnp:
00475     return MultPlusBnd<double,MinusView,MinusView,IntView>::post(home,
00476       MinusView(x0),MinusView(x1),x2);
00477   post_pnn:
00478     std::swap(x0,x1);
00479   post_npn:
00480     return MultPlusBnd<double,MinusView,IntView,MinusView>::post(home,
00481       MinusView(x0),x1,MinusView(x2));
00482   }
00483 
00484 
00485   /*
00486    * Positive domain consistent multiplication
00487    *
00488    */
00489   template<class Val, class View>
00490   forceinline ExecStatus
00491   prop_mult_dom(Space& home, Propagator& p, View x0, View x1, View x2) {
00492     Region r(home);
00493     SupportValues<View,Region> s0(r,x0), s1(r,x1), s2(r,x2);
00494     while (s0()) {
00495       while (s1()) {
00496         if (s2.support(m<Val>(s0.val(),s1.val()))) {
00497           s0.support(); s1.support();
00498         }
00499         ++s1;
00500       }
00501       s1.reset(); ++s0;
00502     }
00503     GECODE_ME_CHECK(s0.tell(home));
00504     GECODE_ME_CHECK(s1.tell(home));
00505     GECODE_ME_CHECK(s2.tell(home));
00506     return x0.assigned() && x1.assigned() ? home.ES_SUBSUMED(p) : ES_FIX;
00507   }
00508 
00509   template<class Val, class VA, class VB, class VC>
00510   forceinline
00511   MultPlusDom<Val,VA,VB,VC>::MultPlusDom(Home home, VA x0, VB x1, VC x2)
00512     : MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM>
00513   (home,x0,x1,x2) {}
00514 
00515   template<class Val, class VA, class VB, class VC>
00516   forceinline
00517   MultPlusDom<Val,VA,VB,VC>::MultPlusDom(Space& home, bool share,
00518                                          MultPlusDom<Val,VA,VB,VC>& p)
00519     : MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM>
00520       (home,share,p) {}
00521 
00522   template<class Val, class VA, class VB, class VC>
00523   Actor*
00524   MultPlusDom<Val,VA,VB,VC>::copy(Space& home, bool share) {
00525     return new (home) MultPlusDom<Val,VA,VB,VC>(home,share,*this);
00526   }
00527 
00528   template<class Val, class VA, class VB, class VC>
00529   PropCost
00530   MultPlusDom<Val,VA,VB,VC>::cost(const Space&,
00531                                   const ModEventDelta& med) const {
00532     if (VA::me(med) == ME_INT_DOM)
00533       return PropCost::ternary(PropCost::HI);
00534     else
00535       return PropCost::ternary(PropCost::LO);
00536   }
00537 
00538   template<class Val, class VA, class VB, class VC>
00539   ExecStatus
00540   MultPlusDom<Val,VA,VB,VC>::propagate(Space& home, const ModEventDelta& med) {
00541     if (VA::me(med) != ME_INT_DOM) {
00542       GECODE_ES_CHECK((prop_mult_plus_bnd<Val,VA,VB,VC>(home,*this,x0,x1,x2)));
00543       return home.ES_FIX_PARTIAL(*this,VA::med(ME_INT_DOM));
00544     }
00545     IntView y0(x0.varimp()), y1(x1.varimp()), y2(x2.varimp());
00546     return prop_mult_dom<Val,IntView>(home,*this,y0,y1,y2);
00547   }
00548 
00549   template<class Val, class VA, class VB, class VC>
00550   forceinline ExecStatus
00551   MultPlusDom<Val,VA,VB,VC>::post(Home home, VA x0, VB x1, VC x2) {
00552     GECODE_ME_CHECK(x0.gr(home,0));
00553     GECODE_ME_CHECK(x1.gr(home,0));
00554     GECODE_ME_CHECK(x2.gq(home,(static_cast<double>(x0.min()) *
00555                                 static_cast<double>(x1.min()))));
00556     double u = static_cast<double>(x0.max()) * static_cast<double>(x1.max());
00557     if (u > INT_MAX) {
00558       (void) new (home) MultPlusDom<double,VA,VB,VC>(home,x0,x1,x2);
00559     } else {
00560       GECODE_ME_CHECK(x2.lq(home,u));
00561       (void) new (home) MultPlusDom<int,VA,VB,VC>(home,x0,x1,x2);
00562     }
00563     return ES_OK;
00564   }
00565 
00566 
00567   /*
00568    * Bounds consistent multiplication
00569    *
00570    */
00571   template<class View>
00572   forceinline
00573   MultDom<View>::MultDom(Home home, View x0, View x1, View x2)
00574     : TernaryPropagator<View,PC_INT_DOM>(home,x0,x1,x2) {}
00575 
00576   template<class View>
00577   forceinline
00578   MultDom<View>::MultDom(Space& home, bool share, MultDom<View>& p)
00579     : TernaryPropagator<View,PC_INT_DOM>(home,share,p) {}
00580 
00581   template<class View>
00582   Actor*
00583   MultDom<View>::copy(Space& home, bool share) {
00584     return new (home) MultDom<View>(home,share,*this);
00585   }
00586 
00587   template<class View>
00588   PropCost
00589   MultDom<View>::cost(const Space&, const ModEventDelta& med) const {
00590     if (View::me(med) == ME_INT_DOM)
00591       return PropCost::ternary(PropCost::HI);
00592     else
00593       return PropCost::ternary(PropCost::LO);
00594   }
00595 
00596   template<class View>
00597   ExecStatus
00598   MultDom<View>::propagate(Space& home, const ModEventDelta& med) {
00599     if (View::me(med) != ME_INT_DOM) {
00600       if (pos(x0)) {
00601         if (pos(x1) || pos(x2)) goto rewrite_ppp;
00602         if (neg(x1) || neg(x2)) goto rewrite_pnn;
00603         goto prop_pxx;
00604       }
00605       if (neg(x0)) {
00606         if (neg(x1) || pos(x2)) goto rewrite_nnp;
00607         if (pos(x1) || neg(x2)) goto rewrite_npn;
00608         goto prop_nxx;
00609       }
00610       if (pos(x1)) {
00611         if (pos(x2)) goto rewrite_ppp;
00612         if (neg(x2)) goto rewrite_npn;
00613         goto prop_xpx;
00614       }
00615       if (neg(x1)) {
00616         if (pos(x2)) goto rewrite_nnp;
00617         if (neg(x2)) goto rewrite_pnn;
00618         goto prop_xnx;
00619       }
00620 
00621       assert(any(x0) && any(x1));
00622       GECODE_ME_CHECK(x2.lq(home,std::max(m<double>(x0.max(),x1.max()),
00623                                           m<double>(x0.min(),x1.min()))));
00624       GECODE_ME_CHECK(x2.gq(home,std::min(m<double>(x0.min(),x1.max()),
00625                                           m<double>(x0.max(),x1.min()))));
00626 
00627       if (x0.assigned()) {
00628         assert((x0.val() == 0) && (x2.val() == 0));
00629         return home.ES_SUBSUMED(*this);
00630       }
00631 
00632       if (x1.assigned()) {
00633         assert((x1.val() == 0) && (x2.val() == 0));
00634         return home.ES_SUBSUMED(*this);
00635       }
00636 
00637       return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
00638 
00639     prop_xpx:
00640       std::swap(x0,x1);
00641     prop_pxx:
00642       assert(pos(x0) && any(x1) && any(x2));
00643 
00644       GECODE_ME_CHECK(x2.lq(home,m<double>(x0.max(),x1.max())));
00645       GECODE_ME_CHECK(x2.gq(home,m<double>(x0.max(),x1.min())));
00646 
00647       if (pos(x2)) goto rewrite_ppp;
00648       if (neg(x2)) goto rewrite_pnn;
00649 
00650       GECODE_ME_CHECK(x1.lq(home,f_d(x2.max(),x0.min())));
00651       GECODE_ME_CHECK(x1.gq(home,c_d(x2.min(),x0.min())));
00652 
00653       if (x0.assigned() && x1.assigned()) {
00654         GECODE_ME_CHECK(x2.eq(home,m<double>(x0.val(),x1.val())));
00655         return home.ES_SUBSUMED(*this);
00656       }
00657 
00658       return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
00659 
00660     prop_xnx:
00661       std::swap(x0,x1);
00662     prop_nxx:
00663       assert(neg(x0) && any(x1) && any(x2));
00664 
00665       GECODE_ME_CHECK(x2.lq(home,m<double>(x0.min(),x1.min())));
00666       GECODE_ME_CHECK(x2.gq(home,m<double>(x0.min(),x1.max())));
00667 
00668       if (pos(x2)) goto rewrite_nnp;
00669       if (neg(x2)) goto rewrite_npn;
00670 
00671       GECODE_ME_CHECK(x1.lq(home,f_d(x2.min(),x0.max())));
00672       GECODE_ME_CHECK(x1.gq(home,c_d(x2.max(),x0.max())));
00673 
00674       if (x0.assigned() && x1.assigned()) {
00675         GECODE_ME_CHECK(x2.eq(home,m<double>(x0.val(),x1.val())));
00676         return home.ES_SUBSUMED(*this);
00677       }
00678 
00679       return home.ES_NOFIX_PARTIAL(*this,View::med(ME_INT_DOM));
00680 
00681     rewrite_ppp:
00682       GECODE_REWRITE(*this,(MultPlusDom<double,IntView,IntView,IntView>
00683                            ::post(home(*this),x0,x1,x2)));
00684     rewrite_nnp:
00685       GECODE_REWRITE(*this,(MultPlusDom<double,MinusView,MinusView,IntView>
00686                            ::post(home(*this),
00687                                   MinusView(x0),MinusView(x1),x2)));
00688     rewrite_pnn:
00689       std::swap(x0,x1);
00690     rewrite_npn:
00691       GECODE_REWRITE(*this,(MultPlusDom<double,MinusView,IntView,MinusView>
00692                            ::post(home(*this),
00693                                   MinusView(x0),x1,MinusView(x2))));
00694     }
00695     return prop_mult_dom<double,View>(home,*this,x0,x1,x2);
00696   }
00697 
00698   template<class View>
00699   ExecStatus
00700   MultDom<View>::post(Home home, View x0, View x1, View x2) {
00701     if (same(x0,x1))
00702       return SqrDom<View>::post(home,x0,x2);
00703     if (same(x0,x2))
00704       return MultZeroOne<View,PC_INT_DOM>::post(home,x0,x1);
00705     if (same(x1,x2))
00706       return MultZeroOne<View,PC_INT_DOM>::post(home,x1,x0);
00707     if (pos(x0)) {
00708       if (pos(x1) || pos(x2)) goto post_ppp;
00709       if (neg(x1) || neg(x2)) goto post_pnn;
00710     } else if (neg(x0)) {
00711       if (neg(x1) || pos(x2)) goto post_nnp;
00712       if (pos(x1) || neg(x2)) goto post_npn;
00713     } else if (pos(x1)) {
00714       if (pos(x2)) goto post_ppp;
00715       if (neg(x2)) goto post_npn;
00716     } else if (neg(x1)) {
00717       if (pos(x2)) goto post_nnp;
00718       if (neg(x2)) goto post_pnn;
00719     }
00720     {
00721       double a =
00722         static_cast<double>(x0.min()) * static_cast<double>(x1.min());
00723       double b =
00724         static_cast<double>(x0.min()) * static_cast<double>(x1.max());
00725       double c =
00726         static_cast<double>(x0.max()) * static_cast<double>(x1.min());
00727       double d =
00728         static_cast<double>(x0.max()) * static_cast<double>(x1.max());
00729       GECODE_ME_CHECK(x2.gq(home,std::min(std::min(a,b),std::min(c,d))));
00730       GECODE_ME_CHECK(x2.lq(home,std::max(std::max(a,b),std::max(c,d))));
00731       (void) new (home) MultDom<View>(home,x0,x1,x2);
00732     }
00733     return ES_OK;
00734 
00735   post_ppp:
00736     return MultPlusDom<double,IntView,IntView,IntView>::post(home,x0,x1,x2);
00737   post_nnp:
00738     return MultPlusDom<double,MinusView,MinusView,IntView>::post(home,
00739       MinusView(x0),MinusView(x1),x2);
00740   post_pnn:
00741     std::swap(x0,x1);
00742   post_npn:
00743     return MultPlusDom<double,MinusView,IntView,MinusView>::post(home,
00744       MinusView(x0),x1,MinusView(x2));
00745   }
00746 
00747 }}}
00748 
00749 // STATISTICS: int-prop
00750