set.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 * Gabor Szokoli <szokoli@gecode.org> 00006 * 00007 * Contributing authors: 00008 * Christian Schulte <schulte@gecode.org> 00009 * 00010 * Copyright: 00011 * Guido Tack, 2004 00012 * Christian Schulte, 2004 00013 * Gabor Szokoli, 2004 00014 * 00015 * Last modified: 00016 * $Date: 2010-06-02 14:54:28 +0200 (Wed, 02 Jun 2010) $ by $Author: schulte $ 00017 * $Revision: 11005 $ 00018 * 00019 * This file is part of Gecode, the generic constraint 00020 * development environment: 00021 * http://www.gecode.org 00022 * 00023 * Permission is hereby granted, free of charge, to any person obtaining 00024 * a copy of this software and associated documentation files (the 00025 * "Software"), to deal in the Software without restriction, including 00026 * without limitation the rights to use, copy, modify, merge, publish, 00027 * distribute, sublicense, and/or sell copies of the Software, and to 00028 * permit persons to whom the Software is furnished to do so, subject to 00029 * the following conditions: 00030 * 00031 * The above copyright notice and this permission notice shall be 00032 * included in all copies or substantial portions of the Software. 00033 * 00034 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00035 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00036 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00037 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00038 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00039 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00040 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00041 * 00042 */ 00043 00044 namespace Gecode { namespace Set { 00045 00046 /* 00047 * Creation of new variable implementations 00048 * 00049 */ 00050 00051 forceinline 00052 SetVarImp::SetVarImp(Space& home) 00053 : SetVarImpBase(home), lub(home), glb(home) { 00054 lub.card(Limits::card); 00055 assert(lub.card()==lub.size()); 00056 } 00057 00058 forceinline 00059 SetVarImp::SetVarImp(Space& home,int lbMin,int lbMax,int ubMin,int ubMax, 00060 unsigned int cardMin, unsigned int cardMax) 00061 : SetVarImpBase(home), 00062 lub(home,ubMin,ubMax), glb(home,lbMin,lbMax) { 00063 glb.card(std::max(cardMin, glb.size() )); 00064 lub.card(std::min(cardMax, lub.size() )); 00065 } 00066 00067 forceinline 00068 SetVarImp::SetVarImp(Space& home, 00069 const IntSet& theGlb,int ubMin,int ubMax, 00070 unsigned int cardMin, unsigned int cardMax) 00071 : SetVarImpBase(home), 00072 lub(home,ubMin,ubMax), glb(home,theGlb) { 00073 glb.card(std::max(cardMin, glb.size() )); 00074 lub.card(std::min(cardMax, lub.size() )); 00075 } 00076 00077 forceinline 00078 SetVarImp::SetVarImp(Space& home, 00079 int lbMin,int lbMax,const IntSet& theLub, 00080 unsigned int cardMin, unsigned int cardMax) 00081 : SetVarImpBase(home), 00082 lub(home,theLub), glb(home,lbMin,lbMax) { 00083 glb.card(std::max(cardMin, glb.size() )); 00084 lub.card(std::min(cardMax, lub.size() )); 00085 } 00086 00087 forceinline 00088 SetVarImp::SetVarImp(Space& home, 00089 const IntSet& theGlb,const IntSet& theLub, 00090 unsigned int cardMin, unsigned int cardMax) 00091 : SetVarImpBase(home), lub(home,theLub), glb(home,theGlb) { 00092 glb.card(std::max(cardMin, glb.size() )); 00093 lub.card(std::min(cardMax, lub.size() )); 00094 } 00095 00096 00097 forceinline bool 00098 SetVarImp::assigned(void) const { 00099 return glb.size() == lub.size(); 00100 } 00101 00102 forceinline unsigned int 00103 SetVarImp::cardMin(void) const { return glb.card(); } 00104 00105 forceinline unsigned int 00106 SetVarImp::cardMax(void) const { return lub.card(); } 00107 00108 forceinline bool 00109 SetVarImp::knownIn(int i) const { return (glb.in(i)); } 00110 00111 forceinline bool 00112 SetVarImp::knownOut(int i) const { return !(lub.in(i)); } 00113 00114 forceinline int 00115 SetVarImp::lubMin(void) const { return lub.min(); } 00116 00117 forceinline int 00118 SetVarImp::lubMax(void) const { return lub.max(); } 00119 00120 forceinline int 00121 SetVarImp::lubMinN(unsigned int n) const { return lub.minN(n); } 00122 00123 forceinline int 00124 SetVarImp::glbMin(void) const { return glb.min(); } 00125 00126 forceinline int 00127 SetVarImp::glbMax(void) const { return glb.max(); } 00128 00129 forceinline unsigned int 00130 SetVarImp::glbSize() const { return glb.size(); } 00131 00132 forceinline unsigned int 00133 SetVarImp::lubSize() const { return lub.size(); } 00134 00135 /* 00136 * Support for delta information 00137 * 00138 */ 00139 forceinline int 00140 SetVarImp::glbMin(const Delta& d) { 00141 return static_cast<const SetDelta&>(d).glbMin(); 00142 } 00143 forceinline int 00144 SetVarImp::glbMax(const Delta& d) { 00145 return static_cast<const SetDelta&>(d).glbMax(); 00146 } 00147 forceinline bool 00148 SetVarImp::glbAny(const Delta& d) { 00149 return static_cast<const SetDelta&>(d).glbAny(); 00150 } 00151 forceinline int 00152 SetVarImp::lubMin(const Delta& d) { 00153 return static_cast<const SetDelta&>(d).lubMin(); 00154 } 00155 forceinline int 00156 SetVarImp::lubMax(const Delta& d) { 00157 return static_cast<const SetDelta&>(d).lubMax(); 00158 } 00159 forceinline bool 00160 SetVarImp::lubAny(const Delta& d) { 00161 return static_cast<const SetDelta&>(d).lubAny(); 00162 } 00163 00164 forceinline ModEvent 00165 SetVarImp::cardMin(Space& home,unsigned int newMin) { 00166 if (cardMin() >= newMin) 00167 return ME_SET_NONE; 00168 if (newMin > cardMax()) 00169 return ME_SET_FAILED; 00170 glb.card(newMin); 00171 return cardMin_full(home); 00172 } 00173 00174 forceinline ModEvent 00175 SetVarImp::cardMax(Space& home,unsigned int newMax) { 00176 if (cardMax() <= newMax) 00177 return ME_SET_NONE; 00178 if (cardMin() > newMax) 00179 return ME_SET_FAILED; 00180 lub.card(newMax); 00181 return cardMax_full(home); 00182 } 00183 00184 forceinline ModEvent 00185 SetVarImp::intersect(Space& home,int i, int j) { 00186 BndSetRanges lb(glb); 00187 Iter::Ranges::Singleton s(i,j); 00188 Iter::Ranges::Diff<BndSetRanges, Iter::Ranges::Singleton> probe(lb, s); 00189 if (probe()) 00190 return ME_SET_FAILED; 00191 if (assigned()) 00192 return ME_SET_NONE; 00193 int oldMin = lub.min(); 00194 int oldMax = lub.max(); 00195 if (lub.intersect(home, i, j)) { 00196 SetDelta d; 00197 if (i == oldMin) { 00198 d._lubMin = lub.max()+1; 00199 d._lubMax = oldMax; 00200 } else if (j == oldMax) { 00201 d._lubMin = oldMin; 00202 d._lubMax = lub.min()-1; 00203 } 00204 return processLubChange(home, d); 00205 } 00206 return ME_SET_NONE; 00207 } 00208 00209 forceinline ModEvent 00210 SetVarImp::intersect(Space& home,int i) { 00211 return intersect(home, i, i); 00212 } 00213 00214 template<class I> 00215 inline ModEvent 00216 SetVarImp::intersectI(Space& home, I& iterator) { 00217 Iter::Ranges::IsRangeIter<I>(); 00218 if (assigned()) { 00219 BndSetRanges lbi(glb); 00220 Iter::Ranges::Diff<BndSetRanges,I> probe(lbi,iterator); 00221 if (probe()) 00222 return ME_SET_FAILED; 00223 return ME_SET_NONE; 00224 } 00225 if (!iterator()) { 00226 if (cardMin() > 0) 00227 return ME_SET_FAILED; 00228 lub.card(0); 00229 SetDelta d(1, 0, lub.min(), lub.max()); 00230 lub.excludeAll(home); 00231 return notify(home, ME_SET_VAL, d); 00232 } 00233 int mi=iterator.min(); 00234 int ma=iterator.max(); 00235 ++iterator; 00236 if (iterator()) 00237 return intersectI_full(home, mi, ma, iterator); 00238 else 00239 return intersect(home, mi, ma); 00240 } 00241 00242 template<class I> 00243 ModEvent 00244 SetVarImp::intersectI_full(Space& home, int mi, int ma, I& iterator) { 00245 Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator); 00246 if (lub.intersectI(home, si)) { 00247 BndSetRanges ub(lub); 00248 BndSetRanges lb(glb); 00249 if (!Iter::Ranges::subset(lb,ub)) { 00250 glb.become(home, lub); 00251 glb.card(glb.size()); 00252 lub.card(glb.size()); 00253 return ME_SET_FAILED; 00254 } 00255 ModEvent me = ME_SET_LUB; 00256 if (cardMax() > lub.size()) { 00257 lub.card(lub.size()); 00258 if (cardMin() > cardMax()) { 00259 glb.become(home, lub); 00260 glb.card(glb.size()); 00261 lub.card(glb.size()); 00262 return ME_SET_FAILED; 00263 } 00264 me = ME_SET_CLUB; 00265 } 00266 if (cardMax() == lub.size() && cardMin() == cardMax()) { 00267 glb.become(home, lub); 00268 me = ME_SET_VAL; 00269 } 00270 SetDelta d; 00271 return notify(home, me, d); 00272 } 00273 return ME_SET_NONE; 00274 } 00275 00276 forceinline ModEvent 00277 SetVarImp::include(Space& home, int i, int j) { 00278 if (j<i) 00279 return ME_SET_NONE; 00280 BndSetRanges ub(lub); 00281 Iter::Ranges::Singleton sij(i,j); 00282 if (!Iter::Ranges::subset(sij,ub)) { 00283 return ME_SET_FAILED; 00284 } 00285 SetDelta d; 00286 if (glb.include(home, i, j, d)) 00287 return processGlbChange(home, d); 00288 return ME_SET_NONE; 00289 } 00290 00291 forceinline ModEvent 00292 SetVarImp::include(Space& home, int i) { 00293 return include(home, i, i); 00294 } 00295 00296 template<class I> forceinline ModEvent 00297 SetVarImp::includeI(Space& home, I& iterator) { 00298 Iter::Ranges::IsRangeIter<I>(); 00299 if (!iterator()) { 00300 return ME_SET_NONE; 00301 } 00302 if (assigned()) { 00303 BndSetRanges lbi(glb); 00304 Iter::Ranges::Diff<I,BndSetRanges> 00305 probe(iterator,lbi); 00306 return probe() ? ME_SET_FAILED : ME_SET_NONE; 00307 } 00308 int mi=iterator.min(); 00309 int ma=iterator.max(); 00310 ++iterator; 00311 if (iterator()) 00312 return includeI_full(home, mi, ma, iterator); 00313 else 00314 return include(home, mi, ma); 00315 } 00316 00317 template<class I> 00318 ModEvent 00319 SetVarImp::includeI_full(Space& home, int mi, int ma, I& iterator) { 00320 Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator); 00321 if (glb.includeI(home, si)) { 00322 BndSetRanges ub(lub); 00323 BndSetRanges lb(glb); 00324 if (!Iter::Ranges::subset(lb,ub)) { 00325 glb.become(home, lub); 00326 glb.card(glb.size()); 00327 lub.card(glb.size()); 00328 return ME_SET_FAILED; 00329 } 00330 ModEvent me = ME_SET_GLB; 00331 if (cardMin() < glb.size()) { 00332 glb.card(glb.size()); 00333 if (cardMin() > cardMax()) { 00334 glb.become(home, lub); 00335 glb.card(glb.size()); 00336 lub.card(glb.size()); 00337 return ME_SET_FAILED; 00338 } 00339 me = ME_SET_CGLB; 00340 } 00341 if (cardMin() == glb.size() && cardMin() == cardMax()) { 00342 lub.become(home, glb); 00343 me = ME_SET_VAL; 00344 } 00345 SetDelta d; 00346 return notify(home, me, d); 00347 } 00348 return ME_SET_NONE; 00349 } 00350 00351 forceinline ModEvent 00352 SetVarImp::exclude(Space& home, int i, int j) { 00353 if (j<i) 00354 return ME_SET_NONE; 00355 Iter::Ranges::Singleton sij(i,j); 00356 BndSetRanges lb(glb); 00357 Iter::Ranges::Inter<Iter::Ranges::Singleton,BndSetRanges> probe(sij,lb); 00358 if (probe()) 00359 return ME_SET_FAILED; 00360 SetDelta d; 00361 if (lub.exclude(home, i, j, d)) 00362 return processLubChange(home, d); 00363 return ME_SET_NONE; 00364 } 00365 00366 forceinline ModEvent 00367 SetVarImp::exclude(Space& home, int i) { 00368 return exclude(home, i, i); 00369 } 00370 00371 template<class I> 00372 inline ModEvent 00373 SetVarImp::excludeI(Space& home, I& iterator) { 00374 Iter::Ranges::IsRangeIter<I>(); 00375 if (!iterator()) 00376 return ME_SET_NONE; 00377 if (assigned()) { 00378 BndSetRanges ubi(lub); 00379 Iter::Ranges::Inter<BndSetRanges,I> probe(ubi,iterator); 00380 return probe() ? ME_SET_FAILED : ME_SET_NONE; 00381 } 00382 int mi=iterator.min(); 00383 int ma=iterator.max(); 00384 ++iterator; 00385 if (iterator()) 00386 return excludeI_full(home, mi, ma, iterator); 00387 else 00388 return exclude(home, mi, ma); 00389 } 00390 00391 template<class I> 00392 ModEvent 00393 SetVarImp::excludeI_full(Space& home, int mi, int ma, I& iterator) { 00394 Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator); 00395 if (lub.excludeI(home, si)) { 00396 BndSetRanges ub(lub); 00397 BndSetRanges lb(glb); 00398 if (!Iter::Ranges::subset(lb,ub)) { 00399 glb.become(home, lub); 00400 glb.card(glb.size()); 00401 lub.card(glb.size()); 00402 return ME_SET_FAILED; 00403 } 00404 ModEvent me = ME_SET_LUB; 00405 if (cardMax() > lub.size()) { 00406 lub.card(lub.size()); 00407 if (cardMin() > cardMax()) { 00408 glb.become(home, lub); 00409 glb.card(glb.size()); 00410 lub.card(glb.size()); 00411 return ME_SET_FAILED; 00412 } 00413 me = ME_SET_CLUB; 00414 } 00415 if (cardMax() == lub.size() && cardMin() == cardMax()) { 00416 glb.become(home, lub); 00417 me = ME_SET_VAL; 00418 } 00419 SetDelta d; 00420 return notify(home, me, d); 00421 } 00422 return ME_SET_NONE; 00423 } 00424 00425 /* 00426 * Copying a variable 00427 * 00428 */ 00429 00430 forceinline SetVarImp* 00431 SetVarImp::copy(Space& home, bool share) { 00432 return copied() ? 00433 static_cast<SetVarImp*>(forward()) : 00434 perform_copy(home,share); 00435 } 00436 00437 /* 00438 * Iterator specializations 00439 * 00440 */ 00441 00450 template<> 00451 class LubRanges<SetVarImp*> : public BndSetRanges { 00452 public: 00454 00455 00456 LubRanges(void); 00458 LubRanges(const SetVarImp*); 00460 void init(const SetVarImp*); 00462 }; 00463 00464 forceinline 00465 LubRanges<SetVarImp*>::LubRanges(void) {} 00466 00467 forceinline 00468 LubRanges<SetVarImp*>::LubRanges(const SetVarImp* x) 00469 : BndSetRanges(x->lub) {} 00470 00471 forceinline void 00472 LubRanges<SetVarImp*>::init(const SetVarImp* x) { 00473 BndSetRanges::init(x->lub); 00474 } 00475 00484 template<> 00485 class GlbRanges<SetVarImp*> : public BndSetRanges { 00486 public: 00488 00489 00490 GlbRanges(void); 00492 GlbRanges(const SetVarImp* x); 00494 void init(const SetVarImp*); 00496 }; 00497 00498 forceinline 00499 GlbRanges<SetVarImp*>::GlbRanges(void) {} 00500 00501 forceinline 00502 GlbRanges<SetVarImp*>::GlbRanges(const SetVarImp* x) 00503 : BndSetRanges(x->glb) {} 00504 00505 forceinline void 00506 GlbRanges<SetVarImp*>::init(const SetVarImp* x) { 00507 BndSetRanges::init(x->glb); 00508 } 00509 00510 00511 /* 00512 * Dependencies 00513 * 00514 */ 00515 forceinline void 00516 SetVarImp::subscribe(Space& home, Propagator& p, PropCond pc, bool schedule) { 00517 SetVarImpBase::subscribe(home,p,pc,assigned(),schedule); 00518 } 00519 forceinline void 00520 SetVarImp::cancel(Space& home, Propagator& p, PropCond pc) { 00521 SetVarImpBase::cancel(home,p,pc,assigned()); 00522 } 00523 forceinline void 00524 SetVarImp::subscribe(Space& home, Advisor& a) { 00525 SetVarImpBase::subscribe(home,a,assigned()); 00526 } 00527 forceinline void 00528 SetVarImp::cancel(Space& home, Advisor& a) { 00529 SetVarImpBase::cancel(home,a,assigned()); 00530 } 00531 00532 }} 00533 00534 // STATISTICS: set-var