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-03-03 17:32:21 +0100 (Wed, 03 Mar 2010) $ by $Author: schulte $ 00013 * $Revision: 10364 $ 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 bool fix_flag = false; 00103 do { 00104 fix_flag = false; 00105 // Compute union of all selected elements' lower bounds 00106 GlbRanges<RView> x1lb(x1); 00107 Iter::Ranges::ToValues<GlbRanges<RView> > vx1lb(x1lb); 00108 GLBndSet unionOfSelected(home); 00109 for(int i=0; vx1lb(); ++vx1lb) { 00110 while (iv[i].idx < vx1lb.val()) i++; 00111 GlbRanges<SView> clb(iv[i].view); 00112 unionOfSelected.includeI(home,clb); 00113 } 00114 00115 { 00116 LubRanges<RView> x1ub(x1); 00117 Iter::Ranges::ToValues<LubRanges<RView> > vx1ub(x1ub); 00118 int i=0; 00119 int j=0; 00120 // Cancel all elements that are no longer in the upper bound 00121 while (vx1ub()) { 00122 if (iv[i].idx < vx1ub.val()) { 00123 iv[i].view.cancel(home,*this, PC_SET_ANY); 00124 i++; 00125 continue; 00126 } 00127 iv[j] = iv[i]; 00128 ++vx1ub; 00129 ++i; ++j; 00130 } 00131 00132 // cancel the variables with index greater than 00133 // max of lub(x1) 00134 for (int k=i; k<n; k++) { 00135 iv[k].view.cancel(home,*this, PC_SET_ANY); 00136 } 00137 n = j; 00138 iv.size(n); 00139 } 00140 00141 { 00142 UnknownRanges<RView> x1u(x1); 00143 Iter::Ranges::Cache<UnknownRanges<RView> > x1uc(x1u); 00144 Iter::Ranges::ToValues<Iter::Ranges::Cache<UnknownRanges<RView> > > 00145 vx1u(x1uc); 00146 int i=0; 00147 int j=0; 00148 while (vx1u()) { 00149 while (iv[i].idx < vx1u.val()) { 00150 iv[j] = iv[i]; 00151 i++; j++; 00152 } 00153 assert(iv[i].idx == vx1u.val()); 00154 00155 SView candidate = iv[i].view; 00156 int candidateInd = iv[i].idx; 00157 00158 GlbRanges<SView> clb(candidate); 00159 BndSetRanges uos(unionOfSelected); 00160 Iter::Ranges::Inter<GlbRanges<SView>, BndSetRanges> 00161 inter(clb, uos); 00162 if (inter()) { 00163 ModEvent me = x1.exclude(home,candidateInd); 00164 fix_flag |= me_modified(me); 00165 GECODE_ME_CHECK(me); 00166 00167 candidate.cancel(home,*this, PC_SET_ANY); 00168 ++i; 00169 ++vx1u; 00170 continue; 00171 } 00172 iv[j] = iv[i]; 00173 ++vx1u; 00174 ++i; ++j; 00175 } 00176 00177 unionOfSelected.dispose(home); 00178 00179 // copy remaining variables 00180 for (int k=i; k<n; k++) { 00181 iv[j] = iv[k]; 00182 j++; 00183 } 00184 n = j; 00185 iv.size(n); 00186 } 00187 00188 if (x1.cardMax()==0) { 00189 // Selector is empty, we're done 00190 return home.ES_SUBSUMED(*this); 00191 } 00192 00193 { 00194 // remove all elements in a selected variable from 00195 // all other selected variables 00196 GlbRanges<RView> x1lb(x1); 00197 Iter::Ranges::ToValues<GlbRanges<RView> > vx1lb(x1lb); 00198 int i=0; 00199 for (; vx1lb(); ++vx1lb) { 00200 while (iv[i].idx < vx1lb.val()) i++; 00201 assert(iv[i].idx==vx1lb.val()); 00202 GlbRanges<RView> x1lb2(x1); 00203 Iter::Ranges::ToValues<GlbRanges<RView> > vx1lb2(x1lb2); 00204 for (int j=0; vx1lb2(); ++vx1lb2) { 00205 while (iv[j].idx < vx1lb2.val()) j++; 00206 assert(iv[j].idx==vx1lb2.val()); 00207 if (iv[i].idx!=iv[j].idx) { 00208 GlbRanges<SView> xilb(iv[i].view); 00209 ModEvent me = iv[j].view.excludeI(home,xilb); 00210 fix_flag |= me_modified(me); 00211 GECODE_ME_CHECK(me); 00212 } 00213 } 00214 } 00215 } 00216 00217 // remove all elements from the selector that overlap 00218 // with all other possibly selected elements, if 00219 // at least two more elements need to be selected 00220 if (x1.cardMin()-x1.glbSize() > 1) { 00221 UnknownRanges<RView> x1u(x1); 00222 Iter::Ranges::Cache<UnknownRanges<RView> > x1uc(x1u); 00223 Iter::Ranges::ToValues<Iter::Ranges::Cache<UnknownRanges<RView> > > 00224 vx1u(x1uc); 00225 00226 for (; vx1u() && x1.cardMin()-x1.glbSize() > 1; ++vx1u) { 00227 int i = 0; 00228 while (iv[i].idx < vx1u.val()) i++; 00229 assert(iv[i].idx == vx1u.val()); 00230 bool flag=true; 00231 00232 UnknownRanges<RView> x1u2(x1); 00233 Iter::Ranges::ToValues<UnknownRanges<RView> > vx1u2(x1u2); 00234 for (; vx1u2(); ++vx1u2) { 00235 int j = 0; 00236 while (iv[j].idx < vx1u2.val()) j++; 00237 assert(iv[j].idx == vx1u2.val()); 00238 if (iv[i].idx!=iv[j].idx) { 00239 GlbRanges<SView> xjlb(iv[j].view); 00240 GlbRanges<SView> xilb(iv[i].view); 00241 Iter::Ranges::Inter<GlbRanges<SView>, GlbRanges<SView> > 00242 inter(xjlb, xilb); 00243 if (!inter()) { 00244 flag = false; 00245 goto here; 00246 } 00247 } 00248 } 00249 here: 00250 if (flag) { 00251 ModEvent me = x1.exclude(home,iv[i].idx); 00252 fix_flag |= me_modified(me); 00253 GECODE_ME_CHECK(me); 00254 } 00255 } 00256 } 00257 00258 // if exactly two more elements need to be selected 00259 // and there is a possible element i such that all other pairs of 00260 // elements overlap, select i 00261 UnknownRanges<RView> x1u(x1); 00262 Iter::Ranges::Cache<UnknownRanges<RView> > x1uc(x1u); 00263 Iter::Ranges::ToValues<Iter::Ranges::Cache<UnknownRanges<RView> > > 00264 vx1u(x1uc); 00265 00266 for (; x1.cardMin()-x1.glbSize() == 2 && vx1u(); ++vx1u) { 00267 int i = 0; 00268 while (iv[i].idx < vx1u.val()) i++; 00269 assert (iv[i].idx == vx1u.val()); 00270 bool flag=true; 00271 00272 UnknownRanges<RView> x1u2(x1); 00273 Iter::Ranges::ToValues<UnknownRanges<RView> > vx1u2(x1u2); 00274 for (; vx1u2(); ++vx1u2) { 00275 int j = 0; 00276 while (iv[j].idx < vx1u2.val()) j++; 00277 assert (iv[j].idx == vx1u2.val()); 00278 if (iv[i].idx!=iv[j].idx) { 00279 UnknownRanges<RView> x1u3(x1); 00280 Iter::Ranges::ToValues<UnknownRanges<RView> > vx1u3(x1u3); 00281 for (; vx1u3(); ++vx1u3) { 00282 int k = 0; 00283 while (iv[k].idx < vx1u3.val()) k++; 00284 assert (iv[k].idx == vx1u3.val()); 00285 if (iv[j].idx!=iv[k].idx && iv[i].idx!=iv[k].idx) { 00286 GlbRanges<SView> xjlb(iv[j].view); 00287 GlbRanges<SView> xilb(iv[k].view); 00288 Iter::Ranges::Inter<GlbRanges<SView>, GlbRanges<SView> > 00289 inter(xjlb, xilb); 00290 if (!inter()) { 00291 flag = false; 00292 goto here2; 00293 } 00294 } 00295 } 00296 } 00297 } 00298 here2: 00299 if (flag) { 00300 ModEvent me = x1.include(home,iv[i].idx); 00301 fix_flag |= me_modified(me); 00302 GECODE_ME_CHECK(me); 00303 } 00304 } 00305 } while (fix_flag); 00306 00307 bool allAssigned = true; 00308 for (int i=iv.size(); i--;) 00309 if (!iv[i].view.assigned()) { 00310 allAssigned = false; 00311 break; 00312 } 00313 if (!x1.assigned()) 00314 allAssigned = false; 00315 00316 return allAssigned ? home.ES_SUBSUMED(*this) : ES_FIX; 00317 } 00318 00319 00320 }}} 00321 00322 // STATISTICS: set-prop