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