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