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 * Copyright: 00008 * Guido Tack, 2004 00009 * Christian Schulte, 2004 00010 * 00011 * Last modified: 00012 * $Date: 2010-07-28 16:13:53 +0200 (Wed, 28 Jul 2010) $ by $Author: schulte $ 00013 * $Revision: 11292 $ 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 ElementIntersection<SView,RView>:: 00045 ElementIntersection(Home home, RView y0, 00046 IdxViewArray& iv0, 00047 RView y1, 00048 const IntSet& theUniverse) 00049 : Propagator(home), universe(theUniverse), x0(y0), iv(iv0), x1(y1) { 00050 home.notice(*this,AP_DISPOSE); 00051 x0.subscribe(home,*this, PC_SET_ANY); 00052 x1.subscribe(home,*this, PC_SET_ANY); 00053 iv.subscribe(home,*this, PC_SET_ANY); 00054 } 00055 00056 template<class SView, class RView> 00057 forceinline 00058 ElementIntersection<SView,RView>:: 00059 ElementIntersection(Space& home, bool share, 00060 ElementIntersection<SView,RView>& p) 00061 : Propagator(home,share,p) { 00062 x0.update(home,share,p.x0); 00063 x1.update(home,share,p.x1); 00064 iv.update(home,share,p.iv); 00065 universe.update(home,share,p.universe); 00066 } 00067 00068 template<class SView, class RView> 00069 PropCost 00070 ElementIntersection<SView,RView>::cost(const Space&, 00071 const ModEventDelta&) const { 00072 return PropCost::linear(PropCost::HI, iv.size()+2); 00073 } 00074 00075 template<class SView, class RView> 00076 forceinline size_t 00077 ElementIntersection<SView,RView>::dispose(Space& home) { 00078 home.ignore(*this,AP_DISPOSE); 00079 if (!home.failed()) { 00080 x0.cancel(home,*this, PC_SET_ANY); 00081 x1.cancel(home,*this, PC_SET_ANY); 00082 iv.cancel(home,*this,PC_SET_ANY); 00083 } 00084 universe.~IntSet(); 00085 (void) Propagator::dispose(home); 00086 return sizeof(*this); 00087 } 00088 00089 template<class SView, class RView> 00090 ExecStatus 00091 ElementIntersection<SView,RView>:: 00092 post(Home home, RView x0, IdxViewArray& xs, 00093 RView x1, const IntSet& universe) { 00094 int n = xs.size(); 00095 00096 // s2 \subseteq {1,...,n} 00097 Iter::Ranges::Singleton s(0, n-1); 00098 GECODE_ME_CHECK(x1.intersectI(home,s)); 00099 (void) new (home) 00100 ElementIntersection<SView,RView>(home,x0,xs,x1,universe); 00101 return ES_OK; 00102 } 00103 00104 template<class SView, class RView> 00105 Actor* 00106 ElementIntersection<SView,RView>::copy(Space& home, bool share) { 00107 return new (home) ElementIntersection<SView,RView>(home,share,*this); 00108 } 00109 00110 template<class SView, class RView> 00111 ExecStatus 00112 ElementIntersection<SView,RView>::propagate(Space& home, const ModEventDelta&) { 00113 Region r(home); 00114 int n = iv.size(); 00115 00116 bool loopVar; 00117 do { 00118 loopVar = false; 00119 00120 // Cache the upper bound iterator, as we have to 00121 // modify the upper bound while iterating 00122 LubRanges<RView> x1ub(x1); 00123 Iter::Ranges::Cache<LubRanges<RView> > x1ubc(r,x1ub); 00124 Iter::Ranges::ToValues<Iter::Ranges::Cache<LubRanges<RView> > > 00125 vx1ub(x1ubc); 00126 00127 GlbRanges<RView> x1lb(x1); 00128 Iter::Ranges::Cache<GlbRanges<RView> > x1lbc(r,x1lb); 00129 Iter::Ranges::ToValues<Iter::Ranges::Cache<GlbRanges<RView> > > 00130 vx1(x1lbc); 00131 00132 // In the first iteration, compute in before[i] the intersection 00133 // of all the lower bounds of the x_i. At the same time, 00134 // exclude inconsistent x_i from x1 and remove them from 00135 // the list, cancel their dependencies. 00136 00137 LUBndSet sofarBefore(home,universe); 00138 LUBndSet* before = r.alloc<LUBndSet>(n); 00139 00140 int j = 0; 00141 int i = 0; 00142 while ( vx1ub() ) { 00143 00144 // Remove vars at indices not in the upper bound 00145 if (iv[i].idx < vx1ub.val()) { 00146 iv[i].view.cancel(home,*this, PC_SET_ANY); 00147 ++i; 00148 continue; 00149 } 00150 assert(iv[i].idx == vx1ub.val()); 00151 iv[j] = iv[i]; 00152 00153 SView candidate = iv[j].view; 00154 int candidateInd = iv[j].idx; 00155 00156 // inter = glb(x0) & complement(lub(candidate)) 00157 GlbRanges<RView> x0lb(x0); 00158 LubRanges<SView> candub(candidate); 00159 Iter::Ranges::Diff<GlbRanges<RView>,LubRanges<SView> > 00160 inter(x0lb, candub); 00161 00162 // exclude inconsistent x_i 00163 // an x_i is inconsistent if 00164 // * its max cardinality is less than minCard of x0 00165 // * inter is not empty (there are elements in x_0 00166 // that can't be in x_i) 00167 if (candidate.cardMax() < x0.cardMin() || 00168 inter()) { 00169 ModEvent me = (x1.exclude(home,candidateInd)); 00170 loopVar |= me_modified(me); 00171 GECODE_ME_CHECK(me); 00172 00173 iv[j].view.cancel(home,*this, PC_SET_ANY); 00174 ++i; 00175 ++vx1ub; 00176 continue; 00177 } else { 00178 // if x_i is consistent, check whether we know 00179 // that its index is in x1 00180 if (vx1() && vx1.val()==candidateInd) { 00181 // x0 <= candidate, candidate >= x0 00182 GlbRanges<RView> x0lb(x0); 00183 ModEvent me = candidate.includeI(home,x0lb); 00184 loopVar |= me_modified(me); 00185 GECODE_ME_CHECK(me); 00186 00187 LubRanges<SView> candub(candidate); 00188 me = x0.intersectI(home,candub); 00189 loopVar |= me_modified(me); 00190 GECODE_ME_CHECK(me); 00191 ++vx1; 00192 } 00193 new (&before[j]) LUBndSet(home); 00194 before[j].update(home,sofarBefore); 00195 GlbRanges<SView> clb(candidate); 00196 sofarBefore.intersectI(home,clb); 00197 } 00198 00199 ++vx1ub; 00200 ++i; ++j; 00201 } 00202 00203 // cancel the variables with index greater than 00204 // max of lub(x1) 00205 for (int k=i; k<n; k++) { 00206 iv[k].view.cancel(home,*this, PC_SET_ANY); 00207 } 00208 n = j; 00209 iv.size(n); 00210 00211 if (x1.cardMax()==0) { 00212 // Elementor is empty, hence the result must be universe 00213 { 00214 IntSetRanges uniI(universe); 00215 GECODE_ME_CHECK(x0.includeI(home,uniI)); 00216 } 00217 { 00218 IntSetRanges uniI(universe); 00219 GECODE_ME_CHECK(x0.intersectI(home,uniI)); 00220 } 00221 for (int i=n; i--;) 00222 before[i].dispose(home); 00223 return home.ES_SUBSUMED(*this); 00224 } 00225 00226 { 00227 // x0 >= sofarBefore 00228 BndSetRanges sfB(sofarBefore); 00229 ModEvent me = x0.includeI(home,sfB); 00230 loopVar |= me_modified(me); 00231 GECODE_ME_CHECK(me); 00232 } 00233 00234 sofarBefore.dispose(home); 00235 00236 LUBndSet sofarAfter(home, universe); 00237 00238 // In the second iteration, this time backwards, compute 00239 // sofarAfter as the intersection of all glb(x_j) with j>i 00240 for (int i=n; i--;) { 00241 if (sofarAfter.size() == 0) break; 00242 00243 // extra = inter(before[i], sofarAfter) - lub(x0) 00244 BndSetRanges b(before[i]); 00245 BndSetRanges s(sofarAfter); 00246 LubRanges<RView> x0ub(x0); 00247 Iter::Ranges::Inter<BndSetRanges, BndSetRanges> inter(b,s); 00248 Iter::Ranges::Diff<Iter::Ranges::Inter<BndSetRanges, 00249 BndSetRanges>, LubRanges<RView> > diff(inter, x0ub); 00250 if (diff()) { 00251 ModEvent me = (x1.include(home,iv[i].idx)); 00252 loopVar |= me_modified(me); 00253 GECODE_ME_CHECK(me); 00254 00255 // candidate != extra 00256 me = iv[i].view.excludeI(home,diff); 00257 loopVar |= me_modified(me); 00258 GECODE_ME_CHECK(me); 00259 } 00260 00261 GlbRanges<SView> ivilb(iv[i].view); 00262 sofarAfter.intersectI(home,ivilb); 00263 before[i].dispose(home); 00264 } 00265 sofarAfter.dispose(home); 00266 00267 } while (loopVar); 00268 00269 // Test whether we determined x1 without determining x0 00270 if (x1.assigned() && !x0.assigned()) { 00271 int ubsize = static_cast<int>(x1.lubSize()); 00272 if (ubsize > 2) { 00273 assert(ubsize==n); 00274 ViewArray<SView> is(home,ubsize); 00275 for (int i=n; i--;) 00276 is[i]=iv[i].view; 00277 GECODE_REWRITE(*this,(RelOp::IntersectionN<SView, RView> 00278 ::post(home(*this),is,x0))); 00279 } else if (ubsize == 2) { 00280 assert(n==2); 00281 SView a = iv[0].view; 00282 SView b = iv[1].view; 00283 GECODE_REWRITE(*this,(RelOp::Intersection<SView, SView, RView> 00284 ::post(home(*this),a,b,x0))); 00285 } else if (ubsize == 1) { 00286 assert(n==1); 00287 GECODE_REWRITE(*this,(Rel::Eq<RView,SView>::post(home(*this),x0,iv[0].view))); 00288 } else { 00289 GECODE_ME_CHECK(x0.cardMax(home, 0)); 00290 return home.ES_SUBSUMED(*this); 00291 } 00292 } 00293 00294 bool allAssigned = true; 00295 for (int i=iv.size(); i--;) { 00296 if (!iv[i].view.assigned()) { 00297 allAssigned = false; 00298 break; 00299 } 00300 } 00301 if (x0.assigned() && x1.assigned() && allAssigned) { 00302 return home.ES_SUBSUMED(*this); 00303 } 00304 00305 return ES_FIX; 00306 } 00307 00308 }}} 00309 00310 // STATISTICS: set-prop