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