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