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
00035
00036
00037
00038 #include <cmath>
00039 #include <climits>
00040
00041 #include <gecode/int/div.hh>
00042 #include <gecode/int/support-values.hh>
00043
00044 namespace Gecode { namespace Int { namespace Arithmetic {
00045
00046
00047
00048
00049
00051 forceinline long long int
00052 mll(long long int x, long long int y) {
00053 return x*y;
00054 }
00056 forceinline long long int
00057 ll(int x) {
00058 return static_cast<long long int>(x);
00059 }
00061 forceinline long long int
00062 ill(int x) {
00063 return static_cast<long long int>(x) + 1;
00064 }
00066 forceinline long long int
00067 dll(int x) {
00068 return static_cast<long long int>(x) - 1;
00069 }
00070
00072 template<class View>
00073 forceinline bool
00074 pos(const View& x) {
00075 return x.min() > 0;
00076 }
00078 template<class View>
00079 forceinline bool
00080 neg(const View& x) {
00081 return x.max() < 0;
00082 }
00084 template<class View>
00085 forceinline bool
00086 any(const View& x) {
00087 return (x.min() <= 0) && (x.max() >= 0);
00088 }
00089
00090
00091
00092
00093
00094
00095
00096 template<class View, PropCond pc>
00097 forceinline
00098 MultZeroOne<View,pc>::MultZeroOne(Home home, View x0, View x1)
00099 : BinaryPropagator<View,pc>(home,x0,x1) {}
00100
00101 template<class View, PropCond pc>
00102 forceinline RelTest
00103 MultZeroOne<View,pc>::equal(View x, int n) {
00104 if (pc == PC_INT_DOM) {
00105 return rtest_eq_dom(x,n);
00106 } else {
00107 return rtest_eq_bnd(x,n);
00108 }
00109 }
00110
00111 template<class View, PropCond pc>
00112 forceinline ExecStatus
00113 MultZeroOne<View,pc>::post(Home home, View x0, View x1) {
00114 switch (equal(x0,0)) {
00115 case RT_FALSE:
00116 GECODE_ME_CHECK(x1.eq(home,1));
00117 break;
00118 case RT_TRUE:
00119 break;
00120 case RT_MAYBE:
00121 switch (equal(x1,1)) {
00122 case RT_FALSE:
00123 GECODE_ME_CHECK(x0.eq(home,0));
00124 break;
00125 case RT_TRUE:
00126 break;
00127 case RT_MAYBE:
00128 (void) new (home) MultZeroOne<View,pc>(home,x0,x1);
00129 break;
00130 default: GECODE_NEVER;
00131 }
00132 break;
00133 default: GECODE_NEVER;
00134 }
00135 return ES_OK;
00136 }
00137
00138 template<class View, PropCond pc>
00139 forceinline
00140 MultZeroOne<View,pc>::MultZeroOne(Space& home, bool share,
00141 MultZeroOne<View,pc>& p)
00142 : BinaryPropagator<View,pc>(home,share,p) {}
00143
00144 template<class View, PropCond pc>
00145 Actor*
00146 MultZeroOne<View,pc>::copy(Space& home, bool share) {
00147 return new (home) MultZeroOne<View,pc>(home,share,*this);
00148 }
00149
00150 template<class View, PropCond pc>
00151 ExecStatus
00152 MultZeroOne<View,pc>::propagate(Space& home, const ModEventDelta&) {
00153 switch (equal(x0,0)) {
00154 case RT_FALSE:
00155 GECODE_ME_CHECK(x1.eq(home,1));
00156 break;
00157 case RT_TRUE:
00158 break;
00159 case RT_MAYBE:
00160 switch (equal(x1,1)) {
00161 case RT_FALSE:
00162 GECODE_ME_CHECK(x0.eq(home,0));
00163 break;
00164 case RT_TRUE:
00165 break;
00166 case RT_MAYBE:
00167 return ES_FIX;
00168 default: GECODE_NEVER;
00169 }
00170 break;
00171 default: GECODE_NEVER;
00172 }
00173 return home.ES_SUBSUMED(*this);
00174 }
00175
00176
00177
00178
00179
00180
00181 template<class VA, class VB, class VC>
00182 forceinline ExecStatus
00183 prop_mult_plus_bnd(Space& home, Propagator& p, VA x0, VB x1, VC x2) {
00184 assert(pos(x0) && pos(x1) && pos(x2));
00185 bool mod;
00186 do {
00187 mod = false;
00188 {
00189 ModEvent me = x2.lq(home,mll(x0.max(),x1.max()));
00190 if (me_failed(me)) return ES_FAILED;
00191 mod |= me_modified(me);
00192 }
00193 {
00194 ModEvent me = x2.gq(home,mll(x0.min(),x1.min()));
00195 if (me_failed(me)) return ES_FAILED;
00196 mod |= me_modified(me);
00197 }
00198 {
00199 ModEvent me = x0.lq(home,floor_div_pp(x2.max(),x1.min()));
00200 if (me_failed(me)) return ES_FAILED;
00201 mod |= me_modified(me);
00202 }
00203 {
00204 ModEvent me = x0.gq(home,ceil_div_pp(x2.min(),x1.max()));
00205 if (me_failed(me)) return ES_FAILED;
00206 mod |= me_modified(me);
00207 }
00208 {
00209 ModEvent me = x1.lq(home,floor_div_pp(x2.max(),x0.min()));
00210 if (me_failed(me)) return ES_FAILED;
00211 mod |= me_modified(me);
00212 }
00213 {
00214 ModEvent me = x1.gq(home,ceil_div_pp(x2.min(),x0.max()));
00215 if (me_failed(me)) return ES_FAILED;
00216 mod |= me_modified(me);
00217 }
00218 } while (mod);
00219 return x0.assigned() && x1.assigned() ?
00220 home.ES_SUBSUMED(p) : ES_FIX;
00221 }
00222
00223 template<class VA, class VB, class VC>
00224 forceinline
00225 MultPlusBnd<VA,VB,VC>::MultPlusBnd(Home home, VA x0, VB x1, VC x2)
00226 : MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>
00227 (home,x0,x1,x2) {}
00228
00229 template<class VA, class VB, class VC>
00230 forceinline
00231 MultPlusBnd<VA,VB,VC>::MultPlusBnd(Space& home, bool share,
00232 MultPlusBnd<VA,VB,VC>& p)
00233 : MixTernaryPropagator<VA,PC_INT_BND,VB,PC_INT_BND,VC,PC_INT_BND>
00234 (home,share,p) {}
00235
00236 template<class VA, class VB, class VC>
00237 Actor*
00238 MultPlusBnd<VA,VB,VC>::copy(Space& home, bool share) {
00239 return new (home) MultPlusBnd<VA,VB,VC>(home,share,*this);
00240 }
00241
00242 template<class VA, class VB, class VC>
00243 ExecStatus
00244 MultPlusBnd<VA,VB,VC>::propagate(Space& home, const ModEventDelta&) {
00245 return prop_mult_plus_bnd<VA,VB,VC>(home,*this,x0,x1,x2);
00246 }
00247
00248 template<class VA, class VB, class VC>
00249 forceinline ExecStatus
00250 MultPlusBnd<VA,VB,VC>::post(Home home, VA x0, VB x1, VC x2) {
00251 GECODE_ME_CHECK(x0.gr(home,0));
00252 GECODE_ME_CHECK(x1.gr(home,0));
00253 GECODE_ME_CHECK(x2.gq(home,mll(x0.min(),x1.min())));
00254 GECODE_ME_CHECK(x2.lq(home,mll(x0.max(),x1.max())));
00255 (void) new (home) MultPlusBnd<VA,VB,VC>(home,x0,x1,x2);
00256 return ES_OK;
00257 }
00258
00259
00260
00261
00262
00263
00264 forceinline
00265 MultBnd::MultBnd(Home home, IntView x0, IntView x1, IntView x2)
00266 : TernaryPropagator<IntView,PC_INT_BND>(home,x0,x1,x2) {}
00267
00268 forceinline
00269 MultBnd::MultBnd(Space& home, bool share, MultBnd& p)
00270 : TernaryPropagator<IntView,PC_INT_BND>(home,share,p) {}
00271
00272
00273
00274
00275
00276 template<class View>
00277 forceinline ExecStatus
00278 prop_mult_dom(Space& home, Propagator& p, View x0, View x1, View x2) {
00279 Region r(home);
00280 SupportValues<View,Region> s0(r,x0), s1(r,x1), s2(r,x2);
00281 while (s0()) {
00282 while (s1()) {
00283 if (s2.support(mll(s0.val(),s1.val()))) {
00284 s0.support(); s1.support();
00285 }
00286 ++s1;
00287 }
00288 s1.reset(); ++s0;
00289 }
00290 GECODE_ME_CHECK(s0.tell(home));
00291 GECODE_ME_CHECK(s1.tell(home));
00292 GECODE_ME_CHECK(s2.tell(home));
00293 return x0.assigned() && x1.assigned() ? home.ES_SUBSUMED(p) : ES_FIX;
00294 }
00295
00296 template<class VA, class VB, class VC>
00297 forceinline
00298 MultPlusDom<VA,VB,VC>::MultPlusDom(Home home, VA x0, VB x1, VC x2)
00299 : MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM>
00300 (home,x0,x1,x2) {}
00301
00302 template<class VA, class VB, class VC>
00303 forceinline
00304 MultPlusDom<VA,VB,VC>::MultPlusDom(Space& home, bool share,
00305 MultPlusDom<VA,VB,VC>& p)
00306 : MixTernaryPropagator<VA,PC_INT_DOM,VB,PC_INT_DOM,VC,PC_INT_DOM>
00307 (home,share,p) {}
00308
00309 template<class VA, class VB, class VC>
00310 Actor*
00311 MultPlusDom<VA,VB,VC>::copy(Space& home, bool share) {
00312 return new (home) MultPlusDom<VA,VB,VC>(home,share,*this);
00313 }
00314
00315 template<class VA, class VB, class VC>
00316 PropCost
00317 MultPlusDom<VA,VB,VC>::cost(const Space&,
00318 const ModEventDelta& med) const {
00319 if (VA::me(med) == ME_INT_DOM)
00320 return PropCost::ternary(PropCost::HI);
00321 else
00322 return PropCost::ternary(PropCost::LO);
00323 }
00324
00325 template<class VA, class VB, class VC>
00326 ExecStatus
00327 MultPlusDom<VA,VB,VC>::propagate(Space& home, const ModEventDelta& med) {
00328 if (VA::me(med) != ME_INT_DOM) {
00329 GECODE_ES_CHECK((prop_mult_plus_bnd<VA,VB,VC>(home,*this,x0,x1,x2)));
00330 return home.ES_FIX_PARTIAL(*this,VA::med(ME_INT_DOM));
00331 }
00332 IntView y0(x0.varimp()), y1(x1.varimp()), y2(x2.varimp());
00333 return prop_mult_dom<IntView>(home,*this,y0,y1,y2);
00334 }
00335
00336 template<class VA, class VB, class VC>
00337 forceinline ExecStatus
00338 MultPlusDom<VA,VB,VC>::post(Home home, VA x0, VB x1, VC x2) {
00339 GECODE_ME_CHECK(x0.gr(home,0));
00340 GECODE_ME_CHECK(x1.gr(home,0));
00341 GECODE_ME_CHECK(x2.gq(home,mll(x0.min(),x1.min())));
00342 GECODE_ME_CHECK(x2.lq(home,mll(x0.max(),x1.max())));
00343 (void) new (home) MultPlusDom<VA,VB,VC>(home,x0,x1,x2);
00344 return ES_OK;
00345 }
00346
00347
00348
00349
00350
00351
00352 forceinline
00353 MultDom::MultDom(Home home, IntView x0, IntView x1, IntView x2)
00354 : TernaryPropagator<IntView,PC_INT_DOM>(home,x0,x1,x2) {}
00355
00356 forceinline
00357 MultDom::MultDom(Space& home, bool share, MultDom& p)
00358 : TernaryPropagator<IntView,PC_INT_DOM>(home,share,p) {}
00359
00360 }}}
00361
00362
00363