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 "gecode/int/rel.hh"
00039
00040 namespace Gecode { namespace Int { namespace Arithmetic {
00041
00042
00043
00044
00045
00046
00047 template <class View>
00048 forceinline ExecStatus
00049 prop_max_bnd(Space* home, View x0, View x1, View x2) {
00050 bool mod = false;
00051 do {
00052 mod = false;
00053 {
00054 ModEvent me = x2.lq(home,std::max(x0.max(),x1.max()));
00055 if (me_failed(me)) return ES_FAILED;
00056 mod |= me_modified(me);
00057 }
00058 {
00059 ModEvent me = x2.gq(home,std::max(x0.min(),x1.min()));
00060 if (me_failed(me)) return ES_FAILED;
00061 mod |= me_modified(me);
00062 }
00063 {
00064 ModEvent me = x0.lq(home,x2.max());
00065 if (me_failed(me)) return ES_FAILED;
00066 mod |= me_modified(me);
00067 }
00068 {
00069 ModEvent me = x1.lq(home,x2.max());
00070 if (me_failed(me)) return ES_FAILED;
00071 mod |= me_modified(me);
00072 }
00073 } while (mod);
00074 return ES_OK;
00075 }
00076
00077 template <class View>
00078 forceinline
00079 MaxBnd<View>::MaxBnd(Space* home, View x0, View x1, View x2)
00080 : TernaryPropagator<View,PC_INT_BND>(home,x0,x1,x2) {}
00081
00082 template <class View>
00083 ExecStatus
00084 MaxBnd<View>::post(Space* home, View x0, View x1, View x2) {
00085 GECODE_ME_CHECK(x2.gq(home,std::max(x0.min(),x1.min())));
00086 GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
00087 if (same(x0,x1))
00088 return Rel::EqBnd<View,View>::post(home,x0,x2);
00089 if (same(x0,x2))
00090 return Rel::Lq<View>::post(home,x1,x2);
00091 if (same(x1,x2))
00092 return Rel::Lq<View>::post(home,x0,x2);
00093 (void) new (home) MaxBnd<View>(home,x0,x1,x2);
00094 return ES_OK;
00095 }
00096
00097 template <class View>
00098 forceinline void
00099 MaxBnd<View>::post(Space* home, Reflection::VarMap& vars,
00100 const Reflection::ActorSpec& spec) {
00101 spec.checkArity(3);
00102 View x0(home, vars, spec[0]);
00103 View x1(home, vars, spec[1]);
00104 View x2(home, vars, spec[2]);
00105 (void) new (home) MaxBnd<View>(home,x0,x1,x2);
00106 }
00107
00108 template <class View>
00109 forceinline
00110 MaxBnd<View>::MaxBnd(Space* home, bool share, MaxBnd<View>& p)
00111 : TernaryPropagator<View,PC_INT_BND>(home,share,p) {}
00112
00113 template <class View>
00114 forceinline
00115 MaxBnd<View>::MaxBnd(Space* home, bool share, Propagator& p,
00116 View x0, View x1, View x2)
00117 : TernaryPropagator<View,PC_INT_BND>(home,share,p,x0,x1,x2) {}
00118
00119 template <class View>
00120 Actor*
00121 MaxBnd<View>::copy(Space* home, bool share) {
00122 return new (home) MaxBnd<View>(home,share,*this);
00123 }
00124
00125 template <class View>
00126 ExecStatus
00127 MaxBnd<View>::propagate(Space* home, ModEventDelta) {
00128 GECODE_ME_CHECK(prop_max_bnd(home,x0,x1,x2));
00129 if (x0.max() <= x1.min())
00130 GECODE_REWRITE(this,(Rel::EqBnd<View,View>::post(home,x1,x2)));
00131 if (x1.max() <= x0.min())
00132 GECODE_REWRITE(this,(Rel::EqBnd<View,View>::post(home,x0,x2)));
00133 return x0.assigned() && x1.assigned() && x2.assigned() ?
00134 ES_SUBSUMED(this,sizeof(*this)) : ES_FIX;
00135 }
00136
00137 template <class View>
00138 Support::Symbol
00139 MaxBnd<View>::ati(void) {
00140 return Reflection::mangle<View>("Gecode::Int::Arithmetic::MaxBnd");
00141 }
00142
00143 template <class View>
00144 Reflection::ActorSpec
00145 MaxBnd<View>::spec(const Space* home, Reflection::VarMap& m) const {
00146 return TernaryPropagator<View,PC_INT_BND>::spec(home, m, ati());
00147 }
00148
00149
00150
00151
00152
00153
00154 template <class View>
00155 forceinline
00156 NaryMaxBnd<View>::NaryMaxBnd(Space* home, ViewArray<View>& x, View y)
00157 : NaryOnePropagator<View,PC_INT_BND>(home,x,y) {}
00158
00159 template <class View>
00160 ExecStatus
00161 NaryMaxBnd<View>::post(Space* home, ViewArray<View>& x, View y) {
00162 assert(x.size() > 0);
00163 x.unique();
00164 if (x.size() == 1)
00165 return Rel::EqBnd<View,View>::post(home,x[0],y);
00166 if (x.size() == 2)
00167 return MaxBnd<View>::post(home,x[0],x[1],y);
00168 int l = Int::Limits::min;
00169 int u = Int::Limits::min;
00170 for (int i=x.size(); i--; ) {
00171 l = std::max(l,x[i].min());
00172 u = std::max(u,x[i].max());
00173 }
00174 GECODE_ME_CHECK(y.gq(home,l));
00175 GECODE_ME_CHECK(y.lq(home,u));
00176 if (x.same(y)) {
00177
00178 for (int i=x.size(); i--; )
00179 GECODE_ES_CHECK(Rel::Lq<View>::post(home,x[i],y));
00180 } else {
00181 (void) new (home) NaryMaxBnd<View>(home,x,y);
00182 }
00183 return ES_OK;
00184 }
00185
00186 template <class View>
00187 forceinline void
00188 NaryMaxBnd<View>::post(Space* home, Reflection::VarMap& vars,
00189 const Reflection::ActorSpec& spec) {
00190 spec.checkArity(2);
00191 ViewArray<View> x(home, vars, spec[0]);
00192 View y(home, vars, spec[1]);
00193 (void) new (home) NaryMaxBnd<View>(home,x,y);
00194 }
00195
00196 template <class View>
00197 forceinline
00198 NaryMaxBnd<View>::NaryMaxBnd(Space* home, bool share, NaryMaxBnd<View>& p)
00199 : NaryOnePropagator<View,PC_INT_BND>(home,share,p) {}
00200
00201 template <class View>
00202 Actor*
00203 NaryMaxBnd<View>::copy(Space* home, bool share) {
00204 if (x.size() == 1)
00205 return new (home) Rel::EqBnd<View,View>(home,share,*this,x[0],y);
00206 if (x.size() == 2)
00207 return new (home) MaxBnd<View>(home,share,*this,x[0],x[1],y);
00208 return new (home) NaryMaxBnd<View>(home,share,*this);
00209 }
00210
00212 enum MaxPropStatus {
00213 MPS_ASSIGNED = 1<<0,
00214 MPS_REMOVED = 1<<1,
00215 MPS_NEW_BOUND = 1<<2
00216 };
00217
00218 template <class View>
00219 forceinline ExecStatus
00220 prop_nary_max_bnd(Space* home, Propagator* p,
00221 ViewArray<View>& x, View y, PropCond pc) {
00222 rerun:
00223 assert(x.size() > 0);
00224 int maxmax = x[x.size()-1].max();
00225 int maxmin = x[x.size()-1].min();
00226 for (int i = x.size()-1; i--; ) {
00227 maxmax = std::max(x[i].max(),maxmax);
00228 maxmin = std::max(x[i].min(),maxmin);
00229 }
00230 GECODE_ME_CHECK(y.lq(home,maxmax));
00231 GECODE_ME_CHECK(y.gq(home,maxmin));
00232 maxmin = y.min();
00233 maxmax = y.max();
00234 int status = MPS_ASSIGNED;
00235 for (int i = x.size(); i--; ) {
00236 ModEvent me = x[i].lq(home,maxmax);
00237 if (me == ME_INT_FAILED)
00238 return ES_FAILED;
00239 if (me_modified(me) && (x[i].max() != maxmax))
00240 status |= MPS_NEW_BOUND;
00241 if (x[i].max() < maxmin) {
00242 x.move_lst(i,home,p,pc);
00243 status |= MPS_REMOVED;
00244 } else if (!x[i].assigned())
00245 status &= ~MPS_ASSIGNED;
00246 }
00247 if (x.size() == 0)
00248 return ES_FAILED;
00249 if ((status & MPS_REMOVED) != 0)
00250 goto rerun;
00251 if (((status & MPS_ASSIGNED) != 0) && y.assigned())
00252 return ES_SUBSUMED(p,sizeof(*p));
00253 return ((status & MPS_NEW_BOUND) != 0) ? ES_NOFIX : ES_FIX;
00254 }
00255
00256 template <class View>
00257 ExecStatus
00258 NaryMaxBnd<View>::propagate(Space* home, ModEventDelta) {
00259 return prop_nary_max_bnd(home,this,x,y,PC_INT_BND);
00260 }
00261
00262 template <class View>
00263 Support::Symbol
00264 NaryMaxBnd<View>::ati(void) {
00265 return Reflection::mangle<View>("Gecode::Int::Arithmetic::NaryMaxBnd");
00266 }
00267
00268 template <class View>
00269 Reflection::ActorSpec
00270 NaryMaxBnd<View>::spec(const Space* home, Reflection::VarMap& m) const {
00271 return NaryOnePropagator<View,PC_INT_BND>::spec(home, m, ati());
00272 }
00273
00274
00275
00276
00277
00278
00279
00280 template <class View>
00281 forceinline
00282 MaxDom<View>::MaxDom(Space* home, View x0, View x1, View x2)
00283 : MixTernaryPropagator<View,PC_INT_DOM,View,PC_INT_DOM,View,PC_INT_BND>
00284 (home,x0,x1,x2) {}
00285
00286 template <class View>
00287 ExecStatus
00288 MaxDom<View>::post(Space* home, View x0, View x1, View x2) {
00289 GECODE_ME_CHECK(x2.gq(home,std::max(x0.min(),x1.min())));
00290 GECODE_ME_CHECK(x2.lq(home,std::max(x0.max(),x1.max())));
00291 if (same(x0,x1))
00292 return Rel::EqDom<View,View>::post(home,x0,x2);
00293 if (same(x0,x2))
00294 return Rel::Lq<View>::post(home,x1,x2);
00295 if (same(x1,x2))
00296 return Rel::Lq<View>::post(home,x0,x2);
00297 (void) new (home) MaxDom<View>(home,x0,x1,x2);
00298 return ES_OK;
00299 }
00300
00301 template <class View>
00302 forceinline void
00303 MaxDom<View>::post(Space* home, Reflection::VarMap& vars,
00304 const Reflection::ActorSpec& spec) {
00305 spec.checkArity(3);
00306 View x0(home, vars, spec[0]);
00307 View x1(home, vars, spec[1]);
00308 View x2(home, vars, spec[2]);
00309 (void) new (home) MaxDom<View>(home,x0,x1,x2);
00310 }
00311
00312 template <class View>
00313 forceinline
00314 MaxDom<View>::MaxDom(Space* home, bool share, MaxDom<View>& p)
00315 : MixTernaryPropagator<View,PC_INT_DOM,View,PC_INT_DOM,View,PC_INT_BND>
00316 (home,share,p) {}
00317
00318 template <class View>
00319 forceinline
00320 MaxDom<View>::MaxDom(Space* home, bool share, Propagator& p,
00321 View x0, View x1, View x2)
00322 : MixTernaryPropagator<View,PC_INT_DOM,View,PC_INT_DOM,View,PC_INT_BND>
00323 (home,share,p,x0,x1,x2) {}
00324
00325 template <class View>
00326 Actor*
00327 MaxDom<View>::copy(Space* home, bool share) {
00328 return new (home) MaxDom<View>(home,share,*this);
00329 }
00330
00331 template <class View>
00332 PropCost
00333 MaxDom<View>::cost(ModEventDelta med) const {
00334 return (View::me(med) == ME_INT_DOM) ? PC_TERNARY_HI : PC_TERNARY_LO;
00335 }
00336
00337 template <class View>
00338 ExecStatus
00339 MaxDom<View>::propagate(Space* home, ModEventDelta med) {
00340 if (View::me(med) != ME_INT_DOM) {
00341 GECODE_ME_CHECK(prop_max_bnd(home,x0,x1,x2));
00342 if (x0.max() <= x1.min())
00343 GECODE_REWRITE(this,(Rel::EqDom<View,View>::post(home,x1,x2)));
00344 if (x1.max() <= x0.min())
00345 GECODE_REWRITE(this,(Rel::EqDom<View,View>::post(home,x0,x2)));
00346 return x0.assigned() && x1.assigned() && x2.assigned() ?
00347 ES_SUBSUMED(this,sizeof(*this)) :
00348 ES_NOFIX_PARTIAL(this,View::med(ME_INT_DOM));
00349 }
00350 ViewRanges<View> r0(x0), r1(x1);
00351 Iter::Ranges::Union<ViewRanges<View>,ViewRanges<View> > u(r0,r1);
00352 GECODE_ME_CHECK(x2.inter_r(home,u,false));
00353 return ES_FIX;
00354 }
00355
00356 template <class View>
00357 Support::Symbol
00358 MaxDom<View>::ati(void) {
00359 return Reflection::mangle<View>("Gecode::Int::Arithmetic::MaxDom");
00360 }
00361
00362 template <class View>
00363 Reflection::ActorSpec
00364 MaxDom<View>::spec(const Space* home, Reflection::VarMap& m) const {
00365 return MixTernaryPropagator<View,PC_INT_DOM,View,PC_INT_DOM,
00366 View,PC_INT_BND>::spec(home, m, ati());
00367 }
00368
00369
00370
00371
00372
00373
00374 template <class View>
00375 forceinline
00376 NaryMaxDom<View>::NaryMaxDom(Space* home, ViewArray<View>& x, View y)
00377 : MixNaryOnePropagator<View,PC_INT_DOM,View,PC_INT_BND>(home,x,y) {}
00378
00379 template <class View>
00380 ExecStatus
00381 NaryMaxDom<View>::post(Space* home, ViewArray<View>& x, View y) {
00382 assert(x.size() > 0);
00383 x.unique();
00384 if (x.size() == 1)
00385 return Rel::EqDom<View,View>::post(home,x[0],y);
00386 if (x.size() == 2)
00387 return MaxDom<View>::post(home,x[0],x[1],y);
00388 int l = Int::Limits::min;
00389 int u = Int::Limits::min;
00390 for (int i=x.size(); i--; ) {
00391 l = std::max(l,x[i].min());
00392 u = std::max(u,x[i].max());
00393 }
00394 GECODE_ME_CHECK(y.gq(home,l));
00395 GECODE_ME_CHECK(y.lq(home,u));
00396 if (x.same(y)) {
00397
00398 for (int i=x.size(); i--; )
00399 GECODE_ES_CHECK(Rel::Lq<View>::post(home,x[i],y));
00400 } else {
00401 (void) new (home) NaryMaxDom<View>(home,x,y);
00402 }
00403 return ES_OK;
00404 }
00405
00406 template <class View>
00407 forceinline void
00408 NaryMaxDom<View>::post(Space* home, Reflection::VarMap& vars,
00409 const Reflection::ActorSpec& spec) {
00410 spec.checkArity(2);
00411 ViewArray<View> x(home, vars, spec[0]);
00412 View y(home, vars, spec[1]);
00413 (void) new (home) NaryMaxDom<View>(home,x,y);
00414 }
00415
00416 template <class View>
00417 forceinline
00418 NaryMaxDom<View>::NaryMaxDom(Space* home, bool share, NaryMaxDom<View>& p)
00419 : MixNaryOnePropagator<View,PC_INT_DOM,View,PC_INT_BND>(home,share,p) {}
00420
00421 template <class View>
00422 Actor*
00423 NaryMaxDom<View>::copy(Space* home, bool share) {
00424 if (x.size() == 1)
00425 return new (home) Rel::EqDom<View,View>(home,share,*this,x[0],y);
00426 if (x.size() == 2)
00427 return new (home) MaxDom<View>(home,share,*this,x[0],x[1],y);
00428 return new (home) NaryMaxDom<View>(home,share,*this);
00429 }
00430
00431 template <class View>
00432 PropCost
00433 NaryMaxDom<View>::cost(ModEventDelta med) const {
00434 return (View::me(med) == ME_INT_DOM)
00435 ? cost_lo(y.size(),PC_LINEAR_HI)
00436 : cost_hi(x.size(),PC_LINEAR_LO);
00437 }
00438
00439 template <class View>
00440 ExecStatus
00441 NaryMaxDom<View>::propagate(Space* home, ModEventDelta med) {
00442 if (View::me(med) != ME_INT_DOM) {
00443 ExecStatus es = prop_nary_max_bnd(home,this,x,y,PC_INT_DOM);
00444 GECODE_ES_CHECK(es);
00445 return (es == ES_FIX) ?
00446 ES_FIX_PARTIAL(this,View::med(ME_INT_DOM)) :
00447 ES_NOFIX_PARTIAL(this,View::med(ME_INT_DOM));
00448 }
00449 GECODE_AUTOARRAY(ViewRanges<View>, i_x, x.size());
00450 for (int i = x.size(); i--; ) {
00451 ViewRanges<View> i_xi(x[i]); i_x[i]=i_xi;
00452 }
00453 Iter::Ranges::NaryUnion<ViewRanges<View> > u(i_x,x.size());
00454 GECODE_ME_CHECK(y.inter_r(home,u,false));
00455 return ES_FIX;
00456 }
00457
00458 template <class View>
00459 Support::Symbol
00460 NaryMaxDom<View>::ati(void) {
00461 return Reflection::mangle<View>("Gecode::Int::Arithmetic::NaryMaxDom");
00462 }
00463
00464 template <class View>
00465 Reflection::ActorSpec
00466 NaryMaxDom<View>::spec(const Space* home, Reflection::VarMap& m) const {
00467 return MixNaryOnePropagator<View,PC_INT_DOM,View,PC_INT_BND>
00468 ::spec(home, m, ati());
00469 }
00470
00471 }}}
00472
00473
00474