union.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 union" propagator 00048 * 00049 */ 00050 00051 template<class View0, class View1, class View2> 00052 forceinline 00053 Union<View0,View1,View2>::Union(Home home, View0 y0,View1 y1,View2 y2) 00054 : MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY, 00055 View2,PC_SET_ANY>(home,y0,y1,y2) {} 00056 00057 template<class View0, class View1, class View2> 00058 forceinline 00059 Union<View0,View1,View2>::Union(Space& home, bool share, 00060 Union<View0,View1,View2>& p) 00061 : MixTernaryPropagator<View0,PC_SET_ANY,View1,PC_SET_ANY, 00062 View2,PC_SET_ANY>(home,share,p) {} 00063 00064 template<class View0, class View1, class View2> 00065 ExecStatus Union<View0,View1,View2>::post(Home home, View0 x0, 00066 View1 x1, View2 x2) { 00067 (void) new (home) Union<View0,View1,View2>(home,x0,x1,x2); 00068 return ES_OK; 00069 } 00070 00071 template<class View0, class View1, class View2> 00072 Actor* 00073 Union<View0,View1,View2>::copy(Space& home, bool share) { 00074 return new (home) Union(home,share,*this); 00075 } 00076 00077 template<class View0, class View1, class View2> 00078 ExecStatus 00079 Union<View0,View1,View2>::propagate(Space& home, const ModEventDelta& med) { 00080 // This propagator implements the constraint 00081 // x2 = x0 u x1 00082 00083 bool x0ass = x0.assigned(); 00084 bool x1ass = x1.assigned(); 00085 bool x2ass = x2.assigned(); 00086 00087 ModEvent me0 = View0::me(med); 00088 ModEvent me1 = View1::me(med); 00089 ModEvent me2 = View2::me(med); 00090 00091 bool x0ubmod = false; 00092 bool x1ubmod = false; 00093 bool modified = false; 00094 00095 do { 00096 00097 modified = false; 00098 do { 00099 // 4) lub(x2) <= lub(x0) u lub(x1) 00100 { 00101 LubRanges<View0> x0ub(x0); 00102 LubRanges<View1> x1ub(x1); 00103 Iter::Ranges::Union<LubRanges<View0>, LubRanges<View1> > u2(x0ub,x1ub); 00104 GECODE_ME_CHECK_MODIFIED(modified, x2.intersectI(home,u2) ); 00105 } 00106 00107 if (modified || Rel::testSetEventUB(me2) ) 00108 { 00109 modified = false; 00110 // 5) x0 <= x2 00111 LubRanges<View2> x2ub1(x2); 00112 GECODE_ME_CHECK_MODIFIED(modified, x0.intersectI(home,x2ub1) ); 00113 x0ubmod |= modified; 00114 00115 // 6) x1 <= x2 00116 bool modified2=false; 00117 LubRanges<View2> x2ub2(x2); 00118 GECODE_ME_CHECK_MODIFIED(modified2, x1.intersectI(home,x2ub2) ); 00119 x1ubmod |= modified2; 00120 modified |= modified2; 00121 } 00122 00123 } while (modified); 00124 00125 modified = false; 00126 do { 00127 bool modifiedOld = modified; 00128 modified = false; 00129 00130 if (Rel::testSetEventLB(me2) || Rel::testSetEventUB(me0) 00131 || x0ubmod || modifiedOld) 00132 { 00133 // 1) glb(x0) \ lub(x1) <= glb(x2) 00134 GlbRanges<View2> x2lb(x2); 00135 LubRanges<View0> x0ub(x0); 00136 Iter::Ranges::Diff<GlbRanges<View2>, LubRanges<View0> > 00137 diff(x2lb, x0ub); 00138 GECODE_ME_CHECK_MODIFIED(modified, x1.includeI(home,diff) ); 00139 } 00140 00141 if (Rel::testSetEventLB(me2) || Rel::testSetEventUB(me1) 00142 || x1ubmod || modifiedOld) 00143 { 00144 // 2) glb(x0) \ lub(x2) <= glb(x1) 00145 GlbRanges<View2> x2lb(x2); 00146 LubRanges<View1> x1ub(x1); 00147 Iter::Ranges::Diff<GlbRanges<View2>, LubRanges<View1> > 00148 diff(x2lb, x1ub); 00149 GECODE_ME_CHECK_MODIFIED(modified, x0.includeI(home,diff) ); 00150 } 00151 00152 if (Rel::testSetEventLB(me0,me1) || modified) 00153 { 00154 // modified = false; 00155 // 3) glb(x1) u glb(x2) <= glb(x0) 00156 GlbRanges<View0> x0lb(x0); 00157 GlbRanges<View1> x1lb(x1); 00158 Iter::Ranges::Union<GlbRanges<View0>, GlbRanges<View1> > 00159 u1(x0lb,x1lb); 00160 GECODE_ME_CHECK_MODIFIED(modified, x2.includeI(home,u1) ); 00161 } 00162 00163 } while(modified); 00164 00165 modified = false; 00166 { 00167 // cardinality 00168 ExecStatus ret = unionCard(home,modified, x0, x1, x2); 00169 GECODE_ES_CHECK(ret); 00170 } 00171 00172 if (x2.cardMax() == 0) { 00173 GECODE_ME_CHECK( x0.cardMax(home, 0) ); 00174 GECODE_ME_CHECK( x1.cardMax(home, 0) ); 00175 return home.ES_SUBSUMED(*this); 00176 } 00177 00178 if (x0.cardMax() == 0) 00179 GECODE_REWRITE(*this,(Rel::Eq<View1,View2>::post(home(*this),x1,x2))); 00180 if (x1.cardMax() == 0) 00181 GECODE_REWRITE(*this,(Rel::Eq<View0,View2>::post(home(*this),x0,x2))); 00182 00183 } while(modified); 00184 00185 if (shared(x0,x1,x2)) { 00186 return (x0ass && x1ass && x2ass) ? home.ES_SUBSUMED(*this) : ES_NOFIX; 00187 } else { 00188 if (x0ass && x1ass && x2ass) 00189 return home.ES_SUBSUMED(*this); 00190 if (x0ass != x0.assigned() || 00191 x1ass != x1.assigned() || 00192 x2ass != x2.assigned()) { 00193 return ES_NOFIX; 00194 } else { 00195 return ES_FIX; 00196 } 00197 } 00198 } 00199 00200 00201 /* 00202 * "Nary union" propagator 00203 * 00204 */ 00205 00206 template<class View0, class View1> 00207 forceinline 00208 UnionN<View0,View1>::UnionN(Home home, ViewArray<View0>& x, View1 y) 00209 : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y) { 00210 shared = x.shared(home) || viewarrayshared(home,x,y); 00211 } 00212 00213 template<class View0, class View1> 00214 forceinline 00215 UnionN<View0,View1>::UnionN(Home home, ViewArray<View0>& x, 00216 const IntSet& z, View1 y) 00217 : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,x,y) { 00218 shared = x.shared(home) || viewarrayshared(home,x,y); 00219 IntSetRanges rz(z); 00220 unionOfDets.includeI(home, rz); 00221 } 00222 00223 template<class View0, class View1> 00224 forceinline 00225 UnionN<View0,View1>::UnionN(Space& home, bool share, UnionN& p) 00226 : MixNaryOnePropagator<View0,PC_SET_ANY,View1,PC_SET_ANY>(home,share,p), 00227 shared(p.shared) { 00228 unionOfDets.update(home,p.unionOfDets); 00229 } 00230 00231 template<class View0, class View1> 00232 Actor* 00233 UnionN<View0,View1>::copy(Space& home, bool share) { 00234 return new (home) UnionN<View0,View1>(home,share,*this); 00235 } 00236 00237 template<class View0, class View1> 00238 ExecStatus 00239 UnionN<View0,View1>::post(Home home, ViewArray<View0>& x, View1 y) { 00240 switch (x.size()) { 00241 case 0: 00242 GECODE_ME_CHECK(y.cardMax(home, 0)); 00243 return ES_OK; 00244 case 1: 00245 return Rel::Eq<View0,View1>::post(home, x[0], y); 00246 case 2: 00247 return Union<View0,View0,View1>::post(home, x[0], x[1], y); 00248 default: 00249 (void) new (home) UnionN<View0,View1>(home,x,y); 00250 return ES_OK; 00251 } 00252 } 00253 00254 template<class View0, class View1> 00255 ExecStatus 00256 UnionN<View0,View1>::post(Home home, ViewArray<View0>& x, 00257 const IntSet& z, View1 y) { 00258 (void) new (home) UnionN<View0,View1>(home,x,z,y); 00259 return ES_OK; 00260 } 00261 00262 template<class View0, class View1> 00263 PropCost 00264 UnionN<View0,View1>::cost(const Space&, const ModEventDelta&) const { 00265 return PropCost::quadratic(PropCost::LO, x.size()+1); 00266 } 00267 00268 template<class View0, class View1> 00269 ExecStatus 00270 UnionN<View0,View1>::propagate(Space& home, const ModEventDelta& med) { 00271 ModEvent me0 = View0::me(med); 00272 ModEvent me1 = View1::me(med); 00273 bool ubevent = Rel::testSetEventUB(me0, me1); 00274 bool lbevent = Rel::testSetEventLB(me0, me1); 00275 bool anybevent = Rel::testSetEventAnyB(me0, me1); 00276 bool cardevent = Rel::testSetEventCard(me0, me1); 00277 00278 bool modified = false; 00279 bool oldModified = false; 00280 00281 do { 00282 oldModified = modified; 00283 modified = false; 00284 if (modified || oldModified || ubevent) 00285 GECODE_ME_CHECK(unionNXiUB(home, modified, x, y,unionOfDets)); 00286 if (modified || oldModified || ubevent) 00287 GECODE_ME_CHECK(partitionNYUB(home, modified, x, y,unionOfDets)); 00288 if (modified || oldModified || anybevent) 00289 GECODE_ME_CHECK(partitionNXiLB(home, modified, x, y,unionOfDets)); 00290 if (modified || oldModified || lbevent) 00291 GECODE_ME_CHECK(partitionNYLB(home, modified, x, y,unionOfDets)); 00292 if (modified || oldModified || cardevent || ubevent) 00293 GECODE_ME_CHECK(unionNCard(home, modified, x, y, unionOfDets)); 00294 } while (modified); 00295 00296 for(int i=0;i<x.size();i++){ 00297 //Do not reverse! Eats away the end of the array! 00298 while (i<x.size() && x[i].assigned()) { 00299 GlbRanges<View0> det(x[i]); 00300 unionOfDets.includeI(home,det); 00301 x.move_lst(i); 00302 } 00303 } 00304 // When we run out of variables, make a final check and disolve: 00305 if (x.size()==0) { 00306 BndSetRanges all1(unionOfDets); 00307 GECODE_ME_CHECK( y.intersectI(home,all1) ); 00308 BndSetRanges all2(unionOfDets); 00309 GECODE_ME_CHECK( y.includeI(home,all2) ); 00310 unionOfDets.dispose(home); 00311 return home.ES_SUBSUMED(*this); 00312 } 00313 00314 return shared ? ES_NOFIX : ES_FIX; 00315 } 00316 00317 }}} 00318 00319 // STATISTICS: set-prop