disjoint.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 ElementDisjoint<SView,RView>::ElementDisjoint(Home home, 00045 IdxViewArray& iv0, 00046 RView y1) 00047 : Propagator(home), iv(iv0), x1(y1) { 00048 00049 x1.subscribe(home,*this, PC_SET_ANY); 00050 iv.subscribe(home,*this, PC_SET_ANY); 00051 } 00052 00053 template<class SView, class RView> 00054 forceinline 00055 ElementDisjoint<SView,RView>::ElementDisjoint(Space& home, bool share, 00056 ElementDisjoint& p) 00057 : Propagator(home,share,p) { 00058 x1.update(home,share,p.x1); 00059 iv.update(home,share,p.iv); 00060 } 00061 00062 template<class SView, class RView> 00063 forceinline ExecStatus 00064 ElementDisjoint<SView,RView>::post(Home home, IdxViewArray& xs, 00065 RView x1) { 00066 int n = xs.size(); 00067 00068 // s2 \subseteq {0,...,n-1} 00069 Iter::Ranges::Singleton s(0, n-1); 00070 GECODE_ME_CHECK(x1.intersectI(home,s)); 00071 (void) new (home) 00072 ElementDisjoint(home,xs,x1); 00073 return ES_OK; 00074 } 00075 00076 template<class SView, class RView> 00077 PropCost 00078 ElementDisjoint<SView,RView>::cost(const Space&, const ModEventDelta&) const { 00079 return PropCost::quadratic(PropCost::LO, iv.size()+2); 00080 } 00081 00082 template<class SView, class RView> 00083 forceinline size_t 00084 ElementDisjoint<SView,RView>::dispose(Space& home) { 00085 x1.cancel(home,*this, PC_SET_ANY); 00086 iv.cancel(home,*this,PC_SET_ANY); 00087 (void) Propagator::dispose(home); 00088 return sizeof(*this); 00089 } 00090 00091 template<class SView, class RView> 00092 Actor* 00093 ElementDisjoint<SView,RView>::copy(Space& home, bool share) { 00094 return new (home) ElementDisjoint(home,share,*this); 00095 } 00096 00097 template<class SView, class RView> 00098 ExecStatus 00099 ElementDisjoint<SView,RView>::propagate(Space& home, const ModEventDelta&) { 00100 int n = iv.size(); 00101 00102 Region r(home); 00103 00104 bool fix_flag = false; 00105 do { 00106 fix_flag = false; 00107 // Compute union of all selected elements' lower bounds 00108 GlbRanges<RView> x1lb(x1); 00109 Iter::Ranges::ToValues<GlbRanges<RView> > vx1lb(x1lb); 00110 GLBndSet unionOfSelected(home); 00111 for(int i=0; vx1lb(); ++vx1lb) { 00112 while (iv[i].idx < vx1lb.val()) i++; 00113 GlbRanges<SView> clb(iv[i].view); 00114 unionOfSelected.includeI(home,clb); 00115 } 00116 00117 { 00118 LubRanges<RView> x1ub(x1); 00119 Iter::Ranges::ToValues<LubRanges<RView> > vx1ub(x1ub); 00120 int i=0; 00121 int j=0; 00122 // Cancel all elements that are no longer in the upper bound 00123 while (vx1ub()) { 00124 if (iv[i].idx < vx1ub.val()) { 00125 iv[i].view.cancel(home,*this, PC_SET_ANY); 00126 i++; 00127 continue; 00128 } 00129 iv[j] = iv[i]; 00130 ++vx1ub; 00131 ++i; ++j; 00132 } 00133 00134 // cancel the variables with index greater than 00135 // max of lub(x1) 00136 for (int k=i; k<n; k++) { 00137 iv[k].view.cancel(home,*this, PC_SET_ANY); 00138 } 00139 n = j; 00140 iv.size(n); 00141 } 00142 00143 { 00144 UnknownRanges<RView> x1u(x1); 00145 Iter::Ranges::Cache<UnknownRanges<RView> > x1uc(r,x1u); 00146 Iter::Ranges::ToValues<Iter::Ranges::Cache<UnknownRanges<RView> > > 00147 vx1u(x1uc); 00148 int i=0; 00149 int j=0; 00150 while (vx1u()) { 00151 while (iv[i].idx < vx1u.val()) { 00152 iv[j] = iv[i]; 00153 i++; j++; 00154 } 00155 assert(iv[i].idx == vx1u.val()); 00156 00157 SView candidate = iv[i].view; 00158 int candidateInd = iv[i].idx; 00159 00160 GlbRanges<SView> clb(candidate); 00161 BndSetRanges uos(unionOfSelected); 00162 Iter::Ranges::Inter<GlbRanges<SView>, BndSetRanges> 00163 inter(clb, uos); 00164 if (inter()) { 00165 ModEvent me = x1.exclude(home,candidateInd); 00166 fix_flag |= me_modified(me); 00167 GECODE_ME_CHECK(me); 00168 00169 candidate.cancel(home,*this, PC_SET_ANY); 00170 ++i; 00171 ++vx1u; 00172 continue; 00173 } 00174 iv[j] = iv[i]; 00175 ++vx1u; 00176 ++i; ++j; 00177 } 00178 00179 unionOfSelected.dispose(home); 00180 00181 // copy remaining variables 00182 for (int k=i; k<n; k++) { 00183 iv[j] = iv[k]; 00184 j++; 00185 } 00186 n = j; 00187 iv.size(n); 00188 } 00189 00190 if (x1.cardMax()==0) { 00191 // Selector is empty, we're done 00192 return home.ES_SUBSUMED(*this); 00193 } 00194 00195 { 00196 // remove all elements in a selected variable from 00197 // all other selected variables 00198 GlbRanges<RView> x1lb(x1); 00199 Iter::Ranges::ToValues<GlbRanges<RView> > vx1lb(x1lb); 00200 int i=0; 00201 for (; vx1lb(); ++vx1lb) { 00202 while (iv[i].idx < vx1lb.val()) i++; 00203 assert(iv[i].idx==vx1lb.val()); 00204 GlbRanges<RView> x1lb2(x1); 00205 Iter::Ranges::ToValues<GlbRanges<RView> > vx1lb2(x1lb2); 00206 for (int j=0; vx1lb2(); ++vx1lb2) { 00207 while (iv[j].idx < vx1lb2.val()) j++; 00208 assert(iv[j].idx==vx1lb2.val()); 00209 if (iv[i].idx!=iv[j].idx) { 00210 GlbRanges<SView> xilb(iv[i].view); 00211 ModEvent me = iv[j].view.excludeI(home,xilb); 00212 fix_flag |= me_modified(me); 00213 GECODE_ME_CHECK(me); 00214 } 00215 } 00216 } 00217 } 00218 00219 // remove all elements from the selector that overlap 00220 // with all other possibly selected elements, if 00221 // at least two more elements need to be selected 00222 if (x1.cardMin()-x1.glbSize() > 1) { 00223 UnknownRanges<RView> x1u(x1); 00224 Iter::Ranges::Cache<UnknownRanges<RView> > x1uc(r,x1u); 00225 Iter::Ranges::ToValues<Iter::Ranges::Cache<UnknownRanges<RView> > > 00226 vx1u(x1uc); 00227 00228 for (; vx1u() && x1.cardMin()-x1.glbSize() > 1; ++vx1u) { 00229 int i = 0; 00230 while (iv[i].idx < vx1u.val()) i++; 00231 assert(iv[i].idx == vx1u.val()); 00232 bool flag=true; 00233 00234 UnknownRanges<RView> x1u2(x1); 00235 Iter::Ranges::ToValues<UnknownRanges<RView> > vx1u2(x1u2); 00236 for (; vx1u2(); ++vx1u2) { 00237 int j = 0; 00238 while (iv[j].idx < vx1u2.val()) j++; 00239 assert(iv[j].idx == vx1u2.val()); 00240 if (iv[i].idx!=iv[j].idx) { 00241 GlbRanges<SView> xjlb(iv[j].view); 00242 GlbRanges<SView> xilb(iv[i].view); 00243 Iter::Ranges::Inter<GlbRanges<SView>, GlbRanges<SView> > 00244 inter(xjlb, xilb); 00245 if (!inter()) { 00246 flag = false; 00247 goto here; 00248 } 00249 } 00250 } 00251 here: 00252 if (flag) { 00253 ModEvent me = x1.exclude(home,iv[i].idx); 00254 fix_flag |= me_modified(me); 00255 GECODE_ME_CHECK(me); 00256 } 00257 } 00258 } 00259 00260 // if exactly two more elements need to be selected 00261 // and there is a possible element i such that all other pairs of 00262 // elements overlap, select i 00263 UnknownRanges<RView> x1u(x1); 00264 Iter::Ranges::Cache<UnknownRanges<RView> > x1uc(r,x1u); 00265 Iter::Ranges::ToValues<Iter::Ranges::Cache<UnknownRanges<RView> > > 00266 vx1u(x1uc); 00267 00268 for (; x1.cardMin()-x1.glbSize() == 2 && vx1u(); ++vx1u) { 00269 int i = 0; 00270 while (iv[i].idx < vx1u.val()) i++; 00271 assert (iv[i].idx == vx1u.val()); 00272 bool flag=true; 00273 00274 UnknownRanges<RView> x1u2(x1); 00275 Iter::Ranges::ToValues<UnknownRanges<RView> > vx1u2(x1u2); 00276 for (; vx1u2(); ++vx1u2) { 00277 int j = 0; 00278 while (iv[j].idx < vx1u2.val()) j++; 00279 assert (iv[j].idx == vx1u2.val()); 00280 if (iv[i].idx!=iv[j].idx) { 00281 UnknownRanges<RView> x1u3(x1); 00282 Iter::Ranges::ToValues<UnknownRanges<RView> > vx1u3(x1u3); 00283 for (; vx1u3(); ++vx1u3) { 00284 int k = 0; 00285 while (iv[k].idx < vx1u3.val()) k++; 00286 assert (iv[k].idx == vx1u3.val()); 00287 if (iv[j].idx!=iv[k].idx && iv[i].idx!=iv[k].idx) { 00288 GlbRanges<SView> xjlb(iv[j].view); 00289 GlbRanges<SView> xilb(iv[k].view); 00290 Iter::Ranges::Inter<GlbRanges<SView>, GlbRanges<SView> > 00291 inter(xjlb, xilb); 00292 if (!inter()) { 00293 flag = false; 00294 goto here2; 00295 } 00296 } 00297 } 00298 } 00299 } 00300 here2: 00301 if (flag) { 00302 ModEvent me = x1.include(home,iv[i].idx); 00303 fix_flag |= me_modified(me); 00304 GECODE_ME_CHECK(me); 00305 } 00306 } 00307 } while (fix_flag); 00308 00309 bool allAssigned = true; 00310 for (int i=iv.size(); i--;) 00311 if (!iv[i].view.assigned()) { 00312 allAssigned = false; 00313 break; 00314 } 00315 if (!x1.assigned()) 00316 allAssigned = false; 00317 00318 return allAssigned ? home.ES_SUBSUMED(*this) : ES_FIX; 00319 } 00320 00321 00322 }}} 00323 00324 // STATISTICS: set-prop