00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034 #include <gecode/int/arithmetic.hh>
00035
00036 namespace Gecode { namespace Int { namespace Arithmetic {
00037
00038
00039
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 (same(x0,x1)) {
00146 SqrOps ops;
00147 return PowBnd<SqrOps>::post(home,x0,x2,ops);
00148 }
00149 if (same(x0,x2))
00150 return MultZeroOne<IntView,PC_INT_BND>::post(home,x0,x1);
00151 if (same(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
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 (same(x0,x1)) {
00313 SqrOps ops;
00314 return PowDom<SqrOps>::post(home,x0,x2,ops);
00315 }
00316 if (same(x0,x2))
00317 return MultZeroOne<IntView,PC_INT_DOM>::post(home,x0,x1);
00318 if (same(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
00360