inter.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Guido Tack <tack@gecode.org> 00005 * Christian Schulte <schulte@gecode.org> 00006 * 00007 * Contributing authors: 00008 * Gabor Szokoli <szokoli@gecode.org> 00009 * 00010 * Copyright: 00011 * Guido Tack, 2004 00012 * Christian Schulte, 2004 00013 * Gabor Szokoli, 2004 00014 * 00015 * Last modified: 00016 * $Date: 2010-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $ 00017 * $Revision: 10364 $ 00018 * 00019 * This file is part of Gecode, the generic constraint 00020 * development environment: 00021 * http://www.gecode.org 00022 * 00023 * Permission is hereby granted, free of charge, to any person obtaining 00024 * a copy of this software and associated documentation files (the 00025 * "Software"), to deal in the Software without restriction, including 00026 * without limitation the rights to use, copy, modify, merge, publish, 00027 * distribute, sublicense, and/or sell copies of the Software, and to 00028 * permit persons to whom the Software is furnished to do so, subject to 00029 * the following conditions: 00030 * 00031 * The above copyright notice and this permission notice shall be 00032 * included in all copies or substantial portions of the Software. 00033 * 00034 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00035 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00036 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00037 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00038 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00039 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00040 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00041 * 00042 */ 00043 00044 namespace Gecode { namespace Set { namespace RelOp { 00045 00046 /* 00047 * "Ternary intersection" propagator 00048 * 00049 */ 00050 00051 template<class View0, class View1, class View2> ExecStatus 00052 Intersection<View0,View1,View2>::post(Home home, 00053 View0 x0,View1 x1,View2 x2) { 00054 (void) new (home) Intersection<View0,View1,View2>(home,x0,x1,x2); 00055 return ES_OK; 00056 } 00057 00058 template<class View0, class View1, class View2> 00059 Actor* 00060 Intersection<View0,View1,View2>::copy(Space& home, bool share) { 00061 return new (home) Intersection(home,share,*this); 00062 } 00063 00064 template<class View0, class View1, class View2> 00065 ExecStatus 00066 Intersection<View0,View1,View2>::propagate(Space& home, const ModEventDelta& med) { 00067 // This propagator implements the constraint 00068 // x2 = x0 \cap x1 00069 00070 bool x0ass = x0.assigned(); 00071 bool x1ass = x1.assigned(); 00072 bool x2ass = x2.assigned(); 00073 00074 ModEvent me0 = View0::me(med); 00075 ModEvent me1 = View1::me(med); 00076 ModEvent me2 = View2::me(med); 00077 00078 bool x0lbmod = false; 00079 bool x1lbmod = false; 00080 bool modified = false; 00081 00082 do { 00083 00084 modified = false; 00085 do { 00086 // 4) glb(x2) <= glb(x0) \cap glb(x1) 00087 { 00088 GlbRanges<View0> x0lb(x0); 00089 GlbRanges<View1> x1lb(x1); 00090 Iter::Ranges::Inter<GlbRanges<View0>, GlbRanges<View1> > 00091 i2(x0lb,x1lb); 00092 GECODE_ME_CHECK_MODIFIED(modified, x2.includeI(home,i2) ); 00093 } 00094 00095 if (modified || Rel::testSetEventLB(me2) ) 00096 { 00097 modified = false; 00098 // 5) x2 <= x0 00099 GlbRanges<View2> x2lb1(x2); 00100 GECODE_ME_CHECK_MODIFIED(modified, x0.includeI(home,x2lb1) ); 00101 x0lbmod |= modified; 00102 00103 // 6) x2 <= x1 00104 bool modified2=false; 00105 GlbRanges<View2> x2lb2(x2); 00106 GECODE_ME_CHECK_MODIFIED(modified2, x1.includeI(home,x2lb2) ); 00107 x1lbmod |= modified2; 00108 modified |= modified2; 00109 } 00110 00111 } while (modified); 00112 00113 modified = false; 00114 do { 00115 bool modifiedOld = modified; 00116 modified = false; 00117 00118 if (Rel::testSetEventUB(me2) || Rel::testSetEventLB(me0) 00119 || x0lbmod || modifiedOld) 00120 { 00121 // 1) lub(x2) \ glb(x0) => lub(x1) 00122 GlbRanges<View0> x0lb(x0); 00123 LubRanges<View2> x2ub(x2); 00124 Iter::Ranges::Diff<GlbRanges<View0>,LubRanges<View2> > 00125 diff(x0lb, x2ub); 00126 GECODE_ME_CHECK_MODIFIED(modified, x1.excludeI(home,diff) ); 00127 } 00128 00129 if (Rel::testSetEventUB(me2) || Rel::testSetEventLB(me1) 00130 || x1lbmod || modifiedOld) 00131 { 00132 // 2) lub(x2) \ glb(x1) => lub(x0) 00133 GlbRanges<View1> x1lb(x1); 00134 LubRanges<View2> x2ub(x2); 00135 Iter::Ranges::Diff<GlbRanges<View1>, LubRanges<View2> > 00136 diff(x1lb, x2ub); 00137 GECODE_ME_CHECK_MODIFIED(modified, x0.excludeI(home,diff) ); 00138 } 00139 00140 if (Rel::testSetEventUB(me0,me1) || modified) 00141 { 00142 // modified = false; 00143 // 3) lub(x0) \cap lub(x1) <= lub(x2) 00144 LubRanges<View0> x0ub(x0); 00145 LubRanges<View1> x1ub(x1); 00146 Iter::Ranges::Inter<LubRanges<View0>, LubRanges<View1> > 00147 i1(x0ub,x1ub); 00148 GECODE_ME_CHECK_MODIFIED(modified, x2.intersectI(home,i1) ); 00149 } 00150 00151 } while(modified); 00152 00153 modified = false; 00154 { 00155 // cardinality 00156 ExecStatus ret = interCard(home,modified, x0, x1, x2); 00157 GECODE_ES_CHECK(ret); 00158 } 00159 00160 if (x2.cardMin() == Set::Limits::card) { 00161 GECODE_ME_CHECK( x0.cardMin(home, Set::Limits::card) ); 00162 GECODE_ME_CHECK( x1.cardMin(home, Set::Limits::card) ); 00163 return home.ES_SUBSUMED(*this); 00164 } 00165 00166 if (x0.cardMin() == Set::Limits::card) 00167 GECODE_REWRITE(*this,(Rel::Eq<View1,View2>::post(home(*this),x1,x2))); 00168 if (x1.cardMin() == Set::Limits::card) 00169 GECODE_REWRITE(*this,(Rel::Eq<View0,View2>::post(home(*this),x0,x2))); 00170 00171 } while(modified); 00172 00173 if (shared(x0,x1,x2)) { 00174 return (x0ass && x1ass && x2ass) ? home.ES_SUBSUMED(*this) : ES_NOFIX; 00175 } else { 00176 if (x0ass && x1ass && x2ass) 00177 return home.ES_SUBSUMED(*this); 00178 if (x0ass != x0.assigned() || 00179 x1ass != x1.assigned() || 00180 x2ass != x2.assigned()) { 00181 return ES_NOFIX; 00182 } else { 00183 return ES_FIX; 00184 } 00185 } 00186 } 00187 00188 template<class View0, class View1, class View2> 00189 forceinline 00190 Intersection<View0,View1,View2>::Intersection(Home home, 00191 View0 y0,View1 y1,View2 y2) 00192 : MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY, 00193 View2,PC_SET_ANY>(home,y0,y1,y2) {} 00194 00195 template<class View0, class View1, class View2> 00196 forceinline 00197 Intersection<View0,View1,View2>::Intersection(Space& home, bool share, 00198 Intersection<View0,View1,View2>& p) 00199 : MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY, 00200 View2,PC_SET_ANY>(home,share,p) {} 00201 00202 /* 00203 * "Nary intersection" propagator 00204 * 00205 */ 00206 00207 template<class View0, class View1> 00208 forceinline 00209 IntersectionN<View0,View1>::IntersectionN(Home home, ViewArray<View0>& x, 00210 View1 y) 00211 : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y), 00212 intOfDets(home) { 00213 shared = x.shared(home) || viewarrayshared(home,x,y); 00214 } 00215 00216 template<class View0, class View1> 00217 forceinline 00218 IntersectionN<View0,View1>::IntersectionN(Home home, ViewArray<View0>& x, 00219 const IntSet& z, View1 y) 00220 : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y), 00221 intOfDets(home) { 00222 shared = x.shared(home) || viewarrayshared(home,x,y); 00223 IntSetRanges rz(z); 00224 intOfDets.intersectI(home, rz); 00225 } 00226 00227 template<class View0, class View1> 00228 forceinline 00229 IntersectionN<View0,View1>::IntersectionN(Space& home, bool share, 00230 IntersectionN& p) 00231 : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,share,p), 00232 shared(p.shared), 00233 intOfDets() { 00234 intOfDets.update(home, p.intOfDets); 00235 } 00236 00237 template<class View0, class View1> 00238 ExecStatus 00239 IntersectionN<View0,View1>::post(Home home, 00240 ViewArray<View0>& x, View1 y) { 00241 switch (x.size()) { 00242 case 0: 00243 GECODE_ME_CHECK(y.cardMin(home, Limits::card)); 00244 return ES_OK; 00245 case 1: 00246 return Rel::Eq<View0,View1>::post(home, x[0], y); 00247 case 2: 00248 return Intersection<View0,View0,View1>::post(home, x[0], x[1], y); 00249 default: 00250 (void) new (home) IntersectionN<View0,View1>(home,x,y); 00251 return ES_OK; 00252 } 00253 } 00254 00255 template<class View0, class View1> 00256 ExecStatus 00257 IntersectionN<View0,View1>::post(Home home, ViewArray<View0>& x, 00258 const IntSet& z, View1 y) { 00259 (void) new (home) IntersectionN<View0,View1>(home,x,z,y); 00260 return ES_OK; 00261 } 00262 00263 template<class View0, class View1> 00264 Actor* 00265 IntersectionN<View0,View1>::copy(Space& home, bool share) { 00266 return new (home) IntersectionN<View0,View1>(home,share,*this); 00267 } 00268 00269 template<class View0, class View1> 00270 PropCost 00271 IntersectionN<View0,View1>::cost(const Space&, const ModEventDelta&) const { 00272 return PropCost::quadratic(PropCost::HI, x.size()+1); 00273 } 00274 00275 template<class View0, class View1> 00276 ExecStatus 00277 IntersectionN<View0,View1>::propagate(Space& home, const ModEventDelta&) { 00278 Region r(home); 00279 bool repeat = false; 00280 do { 00281 repeat = false; 00282 int xsize = x.size(); 00283 if (xsize == 0) 00284 goto size0; 00285 for (int i = xsize; i--; ) { 00286 GECODE_ME_CHECK( y.cardMax(home,x[i].cardMax()) ); 00287 GECODE_ME_CHECK( x[i].cardMin(home,y.cardMin()) ); 00288 if (x[i].cardMax()==0) { 00289 GECODE_ME_CHECK( y.cardMax(home, 0)); 00290 intOfDets.dispose(home); 00291 return home.ES_SUBSUMED(*this); 00292 } 00293 } 00294 { 00295 GlbRanges<View0>* xLBs = r.alloc<GlbRanges<View0> >(xsize); 00296 LubRanges<View0>* xUBs = r.alloc<LubRanges<View0> >(xsize); 00297 for (int i = xsize; i--; ) { 00298 GlbRanges<View0> lb(x[i]); 00299 LubRanges<View0> ub(x[i]); 00300 xLBs[i]=lb; 00301 xUBs[i]=ub; 00302 } 00303 Iter::Ranges::NaryInter<GlbRanges<View0> > lbi(xLBs,xsize); 00304 BndSetRanges dets1(intOfDets); 00305 Iter::Ranges::Inter< Iter::Ranges::NaryInter<GlbRanges<View0> >, 00306 BndSetRanges > 00307 lbiAll(lbi,dets1); 00308 GECODE_ME_CHECK( y.includeI(home,lbiAll) ); 00309 00310 Iter::Ranges::NaryInter<LubRanges<View0> > ubi(xUBs,xsize); 00311 BndSetRanges dets2(intOfDets); 00312 Iter::Ranges::Inter< Iter::Ranges::NaryInter<LubRanges<View0> >, 00313 BndSetRanges > 00314 ubiAll(ubi,dets2); 00315 GECODE_ME_CHECK( y.intersectI(home,ubiAll) ); 00316 } 00317 00318 for (int i = xsize; i--; ) { 00319 GlbRanges<View1> ylb(y); 00320 GECODE_ME_CHECK( x[i].includeI(home,ylb) ); 00321 } 00322 00323 // xi.exclude (Intersection(xj.lb) - y.ub) 00324 { 00325 GLBndSet* rightSet = 00326 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*xsize)); 00327 new (&rightSet[xsize-1]) GLBndSet(home); 00328 rightSet[xsize-1].update(home,intOfDets); 00329 for (int i=xsize-1;i--;) { 00330 GlbRanges<View0> xilb(x[i+1]); 00331 BndSetRanges prev(rightSet[i+1]); 00332 Iter::Ranges::Inter<GlbRanges<View0>, 00333 BndSetRanges> inter(xilb,prev); 00334 new (&rightSet[i]) GLBndSet(home); 00335 rightSet[i].includeI(home,inter); 00336 } 00337 00338 LUBndSet leftAcc(home); 00339 00340 for (int i=0;i<xsize;i++) { 00341 BndSetRanges left(leftAcc); 00342 BndSetRanges right(rightSet[i]); 00343 Iter::Ranges::Inter<BndSetRanges, 00344 BndSetRanges> inter(left, right); 00345 LubRanges<View1> yub(y); 00346 Iter::Ranges::Diff<Iter::Ranges::Inter<BndSetRanges, 00347 BndSetRanges>, LubRanges<View1> > 00348 forbidden(inter, yub); 00349 GECODE_ME_CHECK( x[i].excludeI(home,forbidden) ); 00350 GlbRanges<View0> xlb(x[i]); 00351 leftAcc.intersectI(home,xlb); 00352 } 00353 for (int i=xsize; i--;) 00354 rightSet[i].dispose(home); 00355 leftAcc.dispose(home); 00356 } 00357 00358 00359 for(int i=0;i<x.size();i++){ 00360 //Do not reverse! Eats away the end of the array! 00361 while (i<x.size() && x[i].assigned()) { 00362 GlbRanges<View0> det(x[i]); 00363 if (intOfDets.intersectI(home,det)) {repeat = true;} 00364 x.move_lst(i); 00365 if (intOfDets.size()==0) { 00366 GECODE_ME_CHECK( y.cardMax(home,0) ); 00367 intOfDets.dispose(home); 00368 return home.ES_SUBSUMED(*this); 00369 } 00370 } 00371 } 00372 size0: 00373 if (x.size()==0) { 00374 BndSetRanges all1(intOfDets); 00375 GECODE_ME_CHECK( y.intersectI(home,all1) ); 00376 BndSetRanges all2(intOfDets); 00377 GECODE_ME_CHECK( y.includeI(home,all2) ); 00378 intOfDets.dispose(home); 00379 return home.ES_SUBSUMED(*this); 00380 } 00381 00382 } while (repeat); 00383 00384 return shared ? ES_NOFIX : ES_FIX; 00385 } 00386 00387 }}} 00388 00389 // STATISTICS: set-prop