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 * Copyright: 00008 * Guido Tack, 2004,2006 00009 * Christian Schulte, 2004 00010 * 00011 * Last modified: 00012 * $Date: 2010-07-14 17:46:18 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $ 00013 * $Revision: 11192 $ 00014 * 00015 * This file is part of Gecode, the generic constraint 00016 * development environment: 00017 * http://www.gecode.org 00018 * 00019 * Permission is hereby granted, free of charge, to any person obtaining 00020 * a copy of this software and associated documentation files (the 00021 * "Software"), to deal in the Software without restriction, including 00022 * without limitation the rights to use, copy, modify, merge, publish, 00023 * distribute, sublicense, and/or sell copies of the Software, and to 00024 * permit persons to whom the Software is furnished to do so, subject to 00025 * the following conditions: 00026 * 00027 * The above copyright notice and this permission notice shall be 00028 * included in all copies or substantial portions of the Software. 00029 * 00030 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00031 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00032 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00033 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00034 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00035 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00036 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00037 * 00038 */ 00039 00040 namespace Gecode { namespace Set { namespace Element { 00041 00042 template<class SView, class RView> 00043 forceinline 00044 ElementUnion<SView,RView>:: 00045 ElementUnion(Home home, SView y0, 00046 IdxViewArray& iv0, 00047 RView y1) 00048 : Propagator(home), x0(y0), iv(iv0), x1(y1) { 00049 home.notice(*this,AP_DISPOSE); 00050 x0.subscribe(home,*this, PC_SET_ANY); 00051 x1.subscribe(home,*this, PC_SET_ANY); 00052 iv.subscribe(home,*this, PC_SET_ANY); 00053 } 00054 00055 template<class SView, class RView> 00056 forceinline 00057 ElementUnion<SView,RView>:: 00058 ElementUnion(Space& home, bool share, 00059 ElementUnion<SView,RView>& p) 00060 : Propagator(home,share,p) { 00061 x0.update(home,share,p.x0); 00062 x1.update(home,share,p.x1); 00063 iv.update(home,share,p.iv); 00064 } 00065 00066 template<class SView, class RView> 00067 PropCost 00068 ElementUnion<SView,RView>::cost(const Space&, const ModEventDelta&) const { 00069 return PropCost::linear(PropCost::HI, iv.size()+2); 00070 } 00071 00072 template<class SView, class RView> 00073 forceinline size_t 00074 ElementUnion<SView,RView>::dispose(Space& home) { 00075 home.ignore(*this,AP_DISPOSE); 00076 if (!home.failed()) { 00077 x0.cancel(home,*this,PC_SET_ANY); 00078 x1.cancel(home,*this,PC_SET_ANY); 00079 iv.cancel(home,*this,PC_SET_ANY); 00080 } 00081 (void) Propagator::dispose(home); 00082 return sizeof(*this); 00083 } 00084 00085 template<class SView, class RView> 00086 ExecStatus 00087 ElementUnion<SView,RView>:: 00088 post(Home home, SView x0, IdxViewArray& xs, 00089 RView x1) { 00090 int n = xs.size(); 00091 00092 // s2 \subseteq {1,...,n} 00093 Iter::Ranges::Singleton s(0, n-1); 00094 GECODE_ME_CHECK(x1.intersectI(home,s)); 00095 (void) new (home) 00096 ElementUnion<SView,RView>(home,x0,xs,x1); 00097 return ES_OK; 00098 } 00099 00100 template<class SView, class RView> 00101 Actor* 00102 ElementUnion<SView,RView>::copy(Space& home, bool share) { 00103 return new (home) ElementUnion<SView,RView>(home,share,*this); 00104 } 00105 00106 template<class SView, class RView> 00107 ExecStatus 00108 ElementUnion<SView,RView>::propagate(Space& home, const ModEventDelta&) { 00109 Region r(home); 00110 int n = iv.size(); 00111 00112 bool loopVar; 00113 do { 00114 loopVar = false; 00115 00116 // Cache the upper bound iterator, as we have to 00117 // modify the upper bound while iterating 00118 LubRanges<RView> x1ub(x1); 00119 Iter::Ranges::Cache<LubRanges<RView> > x1ubc(x1ub); 00120 Iter::Ranges::ToValues<Iter::Ranges::Cache<LubRanges<RView> > > 00121 vx1ub(x1ubc); 00122 00123 GlbRanges<RView> x1lb(x1); 00124 Iter::Ranges::Cache<GlbRanges<RView> > x1lbc(x1lb); 00125 Iter::Ranges::ToValues<Iter::Ranges::Cache<GlbRanges<RView> > > 00126 vx1(x1lbc); 00127 00128 // In the first iteration, compute in before[i] the union 00129 // of all the upper bounds of the x_i. At the same time, 00130 // exclude inconsistent x_i from x1 and remove them from 00131 // the list, cancel their dependencies. 00132 00133 GLBndSet sofarBefore(home); 00134 LUBndSet selectedInter(home, IntSet (Limits::min, 00135 Limits::max)); 00136 GLBndSet* before = 00137 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*n)); 00138 00139 int j = 0; 00140 int i = 0; 00141 00142 unsigned int maxCard = 0; 00143 unsigned int minCard = Limits::card; 00144 00145 while ( vx1ub() ) { 00146 00147 // Remove vars at indices not in the upper bound 00148 if (iv[i].idx < vx1ub.val()) { 00149 iv[i].view.cancel(home,*this, PC_SET_ANY); 00150 ++i; 00151 continue; 00152 } 00153 assert(iv[i].idx == vx1ub.val()); 00154 iv[j] = iv[i]; 00155 00156 SView candidate = iv[j].view; 00157 int candidateInd = iv[j].idx; 00158 00159 // inter = glb(candidate) & complement(lub(x0)) 00160 GlbRanges<SView> candlb(candidate); 00161 LubRanges<SView> x0ub(x0); 00162 Iter::Ranges::Diff<GlbRanges<SView>, 00163 LubRanges<SView> > diff(candlb, x0ub); 00164 00165 bool selectSingleInconsistent = false; 00166 if (x1.cardMax() <= 1) { 00167 GlbRanges<SView> x0lb(x0); 00168 LubRanges<SView> candub(candidate); 00169 Iter::Ranges::Diff<GlbRanges<SView>, 00170 LubRanges<SView> > diff2(x0lb, candub); 00171 selectSingleInconsistent = diff2() || candidate.cardMax() < x0.cardMin(); 00172 } 00173 00174 // exclude inconsistent x_i 00175 // an x_i is inconsistent if 00176 // * at most one x_i can be selected and there are 00177 // elements in x_0 that can't be in x_i 00178 // (selectSingleInconsistent) 00179 // * its min cardinality is greater than maxCard of x0 00180 // * inter is not empty (there are elements in x_i 00181 // that can't be in x_0) 00182 if (selectSingleInconsistent || 00183 candidate.cardMin() > x0.cardMax() || 00184 diff()) { 00185 ModEvent me = (x1.exclude(home,candidateInd)); 00186 loopVar |= me_modified(me); 00187 GECODE_ME_CHECK(me); 00188 00189 iv[j].view.cancel(home,*this, PC_SET_ANY); 00190 ++i; 00191 ++vx1ub; 00192 continue; 00193 } else { 00194 // if x_i is consistent, check whether we know 00195 // that its index is in x1 00196 if (vx1() && vx1.val()==candidateInd) { 00197 // x0 >= candidate, candidate <= x0 00198 GlbRanges<SView> candlb(candidate); 00199 ModEvent me = x0.includeI(home,candlb); 00200 loopVar |= me_modified(me); 00201 GECODE_ME_CHECK(me); 00202 00203 LubRanges<SView> x0ub(x0); 00204 me = candidate.intersectI(home,x0ub); 00205 loopVar |= me_modified(me); 00206 GECODE_ME_CHECK(me); 00207 ++vx1; 00208 } 00209 new (&before[j]) GLBndSet(home); 00210 before[j].update(home,sofarBefore); 00211 LubRanges<SView> cub(candidate); 00212 sofarBefore.includeI(home,cub); 00213 GlbRanges<SView> clb(candidate); 00214 selectedInter.intersectI(home,clb); 00215 maxCard = std::max(maxCard, candidate.cardMax()); 00216 minCard = std::min(minCard, candidate.cardMin()); 00217 } 00218 00219 ++vx1ub; 00220 ++i; ++j; 00221 } 00222 00223 // cancel the variables with index greater than 00224 // max of lub(x1) 00225 for (int k=i; k<n; k++) { 00226 iv[k].view.cancel(home,*this, PC_SET_ANY); 00227 } 00228 n = j; 00229 iv.size(n); 00230 00231 if (x1.cardMax()==0) { 00232 // Selector is empty, hence the result must be empty 00233 { 00234 GECODE_ME_CHECK(x0.cardMax(home,0)); 00235 } 00236 for (int i=n; i--;) 00237 before[i].dispose(home); 00238 return home.ES_SUBSUMED(*this); 00239 } 00240 00241 if (x1.cardMin() > 0) { 00242 // Selector is not empty, hence the intersection of the 00243 // possibly selected lower bounds is contained in x0 00244 BndSetRanges si(selectedInter); 00245 ModEvent me = x0.includeI(home, si); 00246 loopVar |= me_modified(me); 00247 GECODE_ME_CHECK(me); 00248 me = x0.cardMin(home, minCard); 00249 loopVar |= me_modified(me); 00250 GECODE_ME_CHECK(me); 00251 } 00252 selectedInter.dispose(home); 00253 00254 if (x1.cardMax() <= 1) { 00255 ModEvent me = x0.cardMax(home, maxCard); 00256 loopVar |= me_modified(me); 00257 GECODE_ME_CHECK(me); 00258 } 00259 00260 { 00261 // x0 <= sofarBefore 00262 BndSetRanges sfB(sofarBefore); 00263 ModEvent me = x0.intersectI(home,sfB); 00264 loopVar |= me_modified(me); 00265 GECODE_ME_CHECK(me); 00266 } 00267 00268 sofarBefore.dispose(home); 00269 00270 GLBndSet sofarAfter(home); 00271 00272 // In the second iteration, this time backwards, compute 00273 // sofarAfter as the union of all lub(x_j) with j>i 00274 for (int i=n; i--;) { 00275 // TODO: check for size of universe here? 00276 // if (sofarAfter.size() == 0) break; 00277 00278 // extra = inter(before[i], sofarAfter) - lub(x0) 00279 BndSetRanges b(before[i]); 00280 BndSetRanges s(sofarAfter); 00281 GlbRanges<SView> x0lb(x0); 00282 Iter::Ranges::Union<BndSetRanges, BndSetRanges> inter(b,s); 00283 Iter::Ranges::Diff<GlbRanges<SView>, 00284 Iter::Ranges::Union<BndSetRanges,BndSetRanges> > diff(x0lb, inter); 00285 if (diff()) { 00286 ModEvent me = (x1.include(home,iv[i].idx)); 00287 loopVar |= me_modified(me); 00288 GECODE_ME_CHECK(me); 00289 00290 // candidate != extra 00291 me = iv[i].view.includeI(home,diff); 00292 loopVar |= me_modified(me); 00293 GECODE_ME_CHECK(me); 00294 } 00295 00296 LubRanges<SView> iviub(iv[i].view); 00297 sofarAfter.includeI(home,iviub); 00298 before[i].dispose(home); 00299 } 00300 sofarAfter.dispose(home); 00301 00302 } while (loopVar); 00303 00304 // Test whether we determined x1 without determining x0 00305 if (x1.assigned() && !x0.assigned()) { 00306 int ubsize = static_cast<int>(x1.lubSize()); 00307 if (ubsize > 2) { 00308 assert(ubsize==n); 00309 ViewArray<SView> is(home,ubsize); 00310 for (int i=n; i--;) 00311 is[i]=iv[i].view; 00312 GECODE_REWRITE(*this,(RelOp::UnionN<SView, SView> 00313 ::post(home(*this),is,x0))); 00314 } else if (ubsize == 2) { 00315 assert(n==2); 00316 SView a = iv[0].view; 00317 SView b = iv[1].view; 00318 GECODE_REWRITE(*this,(RelOp::Union<SView, SView, SView> 00319 ::post(home(*this),a,b,x0))); 00320 } else if (ubsize == 1) { 00321 assert(n==1); 00322 GECODE_REWRITE(*this,(Rel::Eq<SView,SView>::post(home(*this),x0,iv[0].view))); 00323 } else { 00324 GECODE_ME_CHECK(x0.cardMax(home, 0)); 00325 return home.ES_SUBSUMED(*this); 00326 } 00327 } 00328 00329 bool allAssigned = true; 00330 for (int i=iv.size(); i--;) { 00331 if (!iv[i].view.assigned()) { 00332 allAssigned = false; 00333 break; 00334 } 00335 } 00336 if (x0.assigned() && x1.assigned() && allAssigned) { 00337 return home.ES_SUBSUMED(*this); 00338 } 00339 00340 return ES_FIX; 00341 } 00342 00343 }}} 00344 00345 // STATISTICS: set-prop