unionConst.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,2007 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 ElementUnionConst<SView,RView>:: 00045 ElementUnionConst(Home home, SView y0, 00046 SharedArray<IntSet>& 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 } 00053 00054 template<class SView, class RView> 00055 forceinline 00056 ElementUnionConst<SView,RView>:: 00057 ElementUnionConst(Space& home, bool share, 00058 ElementUnionConst<SView,RView>& p) 00059 : Propagator(home,share,p) { 00060 x0.update(home,share,p.x0); 00061 x1.update(home,share,p.x1); 00062 iv.update(home,share,p.iv); 00063 } 00064 00065 template<class SView, class RView> 00066 PropCost 00067 ElementUnionConst<SView,RView>::cost(const Space&, const ModEventDelta&) const { 00068 return PropCost::linear(PropCost::HI, iv.size()+2); 00069 } 00070 00071 template<class SView, class RView> 00072 forceinline size_t 00073 ElementUnionConst<SView,RView>::dispose(Space& home) { 00074 home.ignore(*this,AP_DISPOSE); 00075 if (!home.failed()) { 00076 x0.cancel(home,*this, PC_SET_ANY); 00077 x1.cancel(home,*this, PC_SET_ANY); 00078 } 00079 iv.~SharedArray(); 00080 (void) Propagator::dispose(home); 00081 return sizeof(*this); 00082 } 00083 00084 template<class SView, class RView> 00085 ExecStatus 00086 ElementUnionConst<SView,RView>:: 00087 post(Home home, SView x0, SharedArray<IntSet>& xs, 00088 RView x1) { 00089 int n = xs.size(); 00090 00091 // s2 \subseteq {1,...,n} 00092 Iter::Ranges::Singleton s(0, n-1); 00093 GECODE_ME_CHECK(x1.intersectI(home,s)); 00094 (void) new (home) 00095 ElementUnionConst<SView,RView>(home,x0,xs,x1); 00096 return ES_OK; 00097 } 00098 00099 template<class SView, class RView> 00100 Actor* 00101 ElementUnionConst<SView,RView>::copy(Space& home, bool share) { 00102 return new (home) ElementUnionConst<SView,RView>(home,share,*this); 00103 } 00104 00105 template<class SView, class RView> 00106 ExecStatus 00107 ElementUnionConst<SView,RView>::propagate(Space& home, const ModEventDelta&) { 00108 Region r(home); 00109 int n = iv.size(); 00110 00111 bool* stillSelected = r.alloc<bool>(n); 00112 00113 bool loopVar; 00114 do { 00115 loopVar = false; 00116 for (int i=n; i--;) 00117 stillSelected[i] = false; 00118 00119 // Cache the upper bound iterator, as we have to 00120 // modify the upper bound while iterating 00121 LubRanges<RView> x1ub(x1); 00122 Iter::Ranges::Cache<LubRanges<RView> > x1ubc(r,x1ub); 00123 Iter::Ranges::ToValues<Iter::Ranges::Cache<LubRanges<RView> > > 00124 vx1ub(x1ubc); 00125 00126 GlbRanges<RView> x1lb(x1); 00127 Iter::Ranges::Cache<GlbRanges<RView> > x1lbc(r,x1lb); 00128 Iter::Ranges::ToValues<Iter::Ranges::Cache<GlbRanges<RView> > > 00129 vx1(x1lbc); 00130 00131 // In the first iteration, compute in before[i] the union 00132 // of all the upper bounds of the x_i. At the same time, 00133 // exclude inconsistent x_i from x1. 00134 00135 GLBndSet sofarBefore(home); 00136 LUBndSet selectedInter(home, IntSet (Limits::min, 00137 Limits::max)); 00138 GLBndSet* before = 00139 static_cast<GLBndSet*>(r.ralloc(sizeof(GLBndSet)*n)); 00140 00141 int i = 0; 00142 00143 unsigned int maxCard = 0; 00144 unsigned int minCard = Limits::card; 00145 00146 while ( vx1ub() ) { 00147 00148 i = vx1ub.val(); 00149 IntSetRanges candCardR(iv[i]); 00150 unsigned int candidateCard = Iter::Ranges::size(candCardR); 00151 00152 IntSetRanges candlb(iv[i]); 00153 LubRanges<SView> x0ub(x0); 00154 Iter::Ranges::Diff<IntSetRanges, 00155 LubRanges<SView> > diff(candlb, x0ub); 00156 00157 bool selectSingleInconsistent = false; 00158 if (x1.cardMax() <= 1) { 00159 GlbRanges<SView> x0lb(x0); 00160 IntSetRanges candub(iv[i]); 00161 Iter::Ranges::Diff<GlbRanges<SView>, 00162 IntSetRanges > diff2(x0lb, candub); 00163 selectSingleInconsistent = diff2() || candidateCard < x0.cardMin(); 00164 } 00165 00166 // exclude inconsistent x_i 00167 // an x_i is inconsistent if 00168 // * at most one x_i can be selected and there are 00169 // elements in x_0 that can't be in x_i 00170 // (selectSingleInconsistent) 00171 // * its min cardinality is greater than maxCard of x0 00172 // * inter is not empty (there are elements in x_i 00173 // that can't be in x_0) 00174 if (selectSingleInconsistent || 00175 candidateCard > x0.cardMax() || 00176 diff()) { 00177 ModEvent me = (x1.exclude(home,i)); 00178 loopVar |= me_modified(me); 00179 GECODE_ME_CHECK(me); 00180 } else { 00181 stillSelected[i] = true; 00182 // if x_i is consistent, check whether we know 00183 // that its index is in x1 00184 if (vx1() && vx1.val()==i) { 00185 // x0 >= candidate, candidate <= x0 00186 // GlbRanges<SView> candlb(candidate); 00187 IntSetRanges candlb(iv[i]); 00188 ModEvent me = x0.includeI(home,candlb); 00189 loopVar |= me_modified(me); 00190 GECODE_ME_CHECK(me); 00191 ++vx1; 00192 } 00193 new (&before[i]) GLBndSet(home); 00194 before[i].update(home,sofarBefore); 00195 IntSetRanges cub(iv[i]); 00196 sofarBefore.includeI(home,cub); 00197 IntSetRanges clb(iv[i]); 00198 selectedInter.intersectI(home,clb); 00199 maxCard = std::max(maxCard, candidateCard); 00200 minCard = std::min(minCard, candidateCard); 00201 } 00202 00203 ++vx1ub; 00204 } 00205 00206 if (x1.cardMax()==0) { 00207 // Selector is empty, hence the result must be empty 00208 { 00209 GECODE_ME_CHECK(x0.cardMax(home,0)); 00210 } 00211 for (int i=n; i--;) 00212 if (stillSelected[i]) 00213 before[i].dispose(home); 00214 selectedInter.dispose(home); 00215 sofarBefore.dispose(home); 00216 return home.ES_SUBSUMED(*this); 00217 } 00218 00219 if (x1.cardMin() > 0) { 00220 // Selector is not empty, hence the intersection of the 00221 // possibly selected lower bounds is contained in x0 00222 BndSetRanges si(selectedInter); 00223 ModEvent me = x0.includeI(home, si); 00224 loopVar |= me_modified(me); 00225 GECODE_ME_CHECK(me); 00226 me = x0.cardMin(home, minCard); 00227 loopVar |= me_modified(me); 00228 GECODE_ME_CHECK(me); 00229 } 00230 selectedInter.dispose(home); 00231 00232 if (x1.cardMax() <= 1) { 00233 ModEvent me = x0.cardMax(home, maxCard); 00234 loopVar |= me_modified(me); 00235 GECODE_ME_CHECK(me); 00236 } 00237 00238 { 00239 // x0 <= sofarBefore 00240 BndSetRanges sfB(sofarBefore); 00241 ModEvent me = x0.intersectI(home,sfB); 00242 loopVar |= me_modified(me); 00243 GECODE_ME_CHECK(me); 00244 } 00245 00246 sofarBefore.dispose(home); 00247 00248 GLBndSet sofarAfter(home); 00249 00250 // In the second iteration, this time backwards, compute 00251 // sofarAfter as the union of all lub(x_j) with j>i 00252 for (int i=n; i--;) { 00253 if (!stillSelected[i]) 00254 continue; 00255 BndSetRanges b(before[i]); 00256 BndSetRanges s(sofarAfter); 00257 GlbRanges<SView> x0lb(x0); 00258 Iter::Ranges::Union<BndSetRanges, BndSetRanges> inter(b,s); 00259 Iter::Ranges::Diff<GlbRanges<SView>, 00260 Iter::Ranges::Union<BndSetRanges,BndSetRanges> > diff(x0lb, inter); 00261 if (diff()) { 00262 ModEvent me = (x1.include(home,i)); 00263 loopVar |= me_modified(me); 00264 GECODE_ME_CHECK(me); 00265 00266 // candidate != extra 00267 IntSetRanges ivi(iv[i]); 00268 if (!Iter::Ranges::subset(diff, ivi)) 00269 GECODE_ME_CHECK(ME_SET_FAILED); 00270 } 00271 00272 IntSetRanges iviub(iv[i]); 00273 sofarAfter.includeI(home,iviub); 00274 before[i].dispose(home); 00275 } 00276 sofarAfter.dispose(home); 00277 00278 } while (loopVar); 00279 00280 if (x0.assigned() || x1.assigned()) { 00281 return home.ES_SUBSUMED(*this); 00282 } 00283 00284 return ES_FIX; 00285 } 00286 00287 }}} 00288 00289 // STATISTICS: set-prop