max.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Copyright: 00007 * Christian Schulte, 2004 00008 * 00009 * Last modified: 00010 * $Date: 2010-09-03 16:36:31 +0200 (Fri, 03 Sep 2010) $ by $Author: schulte $ 00011 * $Revision: 11390 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 #include <gecode/int/rel.hh> 00039 00040 namespace Gecode { namespace Int { namespace Arithmetic { 00041 00042 /* 00043 * Ternary bounds consistent maximum 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 * Nary bounds consistent maximum 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 // Check whether y occurs in x 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 return prop_nary_max_bnd(home,*this,x,y,PC_INT_BND); 00227 } 00228 00229 00230 /* 00231 * Ternary domain consistent maximum 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>::post(home,x1,x2); 00249 if (same(x1,x2)) 00250 return Rel::Lq<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, bool share, MaxDom<View>& p) 00258 : TernaryPropagator<View,PC_INT_DOM>(home,share,p) {} 00259 00260 template<class View> 00261 forceinline 00262 MaxDom<View>::MaxDom(Space& home, bool share, Propagator& p, 00263 View x0, View x1, View x2) 00264 : TernaryPropagator<View,PC_INT_DOM>(home,share,p,x0,x1,x2) {} 00265 00266 template<class View> 00267 Actor* 00268 MaxDom<View>::copy(Space& home, bool share) { 00269 return new (home) MaxDom<View>(home,share,*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>::post(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>::post(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 * Nary domain consistent maximum 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(home); 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(home,y)) { 00334 // Check whether y occurs in x 00335 for (int i=x.size(); i--; ) 00336 GECODE_ES_CHECK(Rel::Lq<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, bool share, NaryMaxDom<View>& p) 00346 : NaryOnePropagator<View,PC_INT_DOM>(home,share,p) {} 00347 00348 template<class View> 00349 Actor* 00350 NaryMaxDom<View>::copy(Space& home, bool share) { 00351 if (x.size() == 1) 00352 return new (home) Rel::EqDom<View,View>(home,share,*this,x[0],y); 00353 if (x.size() == 2) 00354 return new (home) MaxDom<View>(home,share,*this,x[0],x[1],y); 00355 return new (home) NaryMaxDom<View>(home,share,*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(home); 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<ViewRanges<View> > 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>::post(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 // STATISTICS: int-prop 00398