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-07-28 17:35:33 +0200 (Wed, 28 Jul 2010) $ by $Author: schulte $ 00017 * $Revision: 11294 $ 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 if (assigned()) { 00218 BndSetRanges lbi(glb); 00219 Iter::Ranges::Diff<BndSetRanges,I> probe(lbi,iterator); 00220 if (probe()) 00221 return ME_SET_FAILED; 00222 return ME_SET_NONE; 00223 } 00224 if (!iterator()) { 00225 if (cardMin() > 0) 00226 return ME_SET_FAILED; 00227 lub.card(0); 00228 SetDelta d(1, 0, lub.min(), lub.max()); 00229 lub.excludeAll(home); 00230 return notify(home, ME_SET_VAL, d); 00231 } 00232 int mi=iterator.min(); 00233 int ma=iterator.max(); 00234 ++iterator; 00235 if (iterator()) 00236 return intersectI_full(home, mi, ma, iterator); 00237 else 00238 return intersect(home, mi, ma); 00239 } 00240 00241 template<class I> 00242 ModEvent 00243 SetVarImp::intersectI_full(Space& home, int mi, int ma, I& iterator) { 00244 Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator); 00245 if (lub.intersectI(home, si)) { 00246 BndSetRanges ub(lub); 00247 BndSetRanges lb(glb); 00248 if (!Iter::Ranges::subset(lb,ub)) { 00249 glb.become(home, lub); 00250 glb.card(glb.size()); 00251 lub.card(glb.size()); 00252 return ME_SET_FAILED; 00253 } 00254 ModEvent me = ME_SET_LUB; 00255 if (cardMax() > lub.size()) { 00256 lub.card(lub.size()); 00257 if (cardMin() > cardMax()) { 00258 glb.become(home, lub); 00259 glb.card(glb.size()); 00260 lub.card(glb.size()); 00261 return ME_SET_FAILED; 00262 } 00263 me = ME_SET_CLUB; 00264 } 00265 if (cardMax() == lub.size() && cardMin() == cardMax()) { 00266 glb.become(home, lub); 00267 me = ME_SET_VAL; 00268 } 00269 SetDelta d; 00270 return notify(home, me, d); 00271 } 00272 return ME_SET_NONE; 00273 } 00274 00275 forceinline ModEvent 00276 SetVarImp::include(Space& home, int i, int j) { 00277 if (j<i) 00278 return ME_SET_NONE; 00279 BndSetRanges ub(lub); 00280 Iter::Ranges::Singleton sij(i,j); 00281 if (!Iter::Ranges::subset(sij,ub)) { 00282 return ME_SET_FAILED; 00283 } 00284 SetDelta d; 00285 if (glb.include(home, i, j, d)) 00286 return processGlbChange(home, d); 00287 return ME_SET_NONE; 00288 } 00289 00290 forceinline ModEvent 00291 SetVarImp::include(Space& home, int i) { 00292 return include(home, i, i); 00293 } 00294 00295 template<class I> forceinline ModEvent 00296 SetVarImp::includeI(Space& home, I& iterator) { 00297 if (!iterator()) { 00298 return ME_SET_NONE; 00299 } 00300 if (assigned()) { 00301 BndSetRanges lbi(glb); 00302 Iter::Ranges::Diff<I,BndSetRanges> 00303 probe(iterator,lbi); 00304 return probe() ? ME_SET_FAILED : ME_SET_NONE; 00305 } 00306 int mi=iterator.min(); 00307 int ma=iterator.max(); 00308 ++iterator; 00309 if (iterator()) 00310 return includeI_full(home, mi, ma, iterator); 00311 else 00312 return include(home, mi, ma); 00313 } 00314 00315 template<class I> 00316 ModEvent 00317 SetVarImp::includeI_full(Space& home, int mi, int ma, I& iterator) { 00318 Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator); 00319 if (glb.includeI(home, si)) { 00320 BndSetRanges ub(lub); 00321 BndSetRanges lb(glb); 00322 if (!Iter::Ranges::subset(lb,ub)) { 00323 glb.become(home, lub); 00324 glb.card(glb.size()); 00325 lub.card(glb.size()); 00326 return ME_SET_FAILED; 00327 } 00328 ModEvent me = ME_SET_GLB; 00329 if (cardMin() < glb.size()) { 00330 glb.card(glb.size()); 00331 if (cardMin() > cardMax()) { 00332 glb.become(home, lub); 00333 glb.card(glb.size()); 00334 lub.card(glb.size()); 00335 return ME_SET_FAILED; 00336 } 00337 me = ME_SET_CGLB; 00338 } 00339 if (cardMin() == glb.size() && cardMin() == cardMax()) { 00340 lub.become(home, glb); 00341 me = ME_SET_VAL; 00342 } 00343 SetDelta d; 00344 return notify(home, me, d); 00345 } 00346 return ME_SET_NONE; 00347 } 00348 00349 forceinline ModEvent 00350 SetVarImp::exclude(Space& home, int i, int j) { 00351 if (j<i) 00352 return ME_SET_NONE; 00353 Iter::Ranges::Singleton sij(i,j); 00354 BndSetRanges lb(glb); 00355 Iter::Ranges::Inter<Iter::Ranges::Singleton,BndSetRanges> probe(sij,lb); 00356 if (probe()) 00357 return ME_SET_FAILED; 00358 SetDelta d; 00359 if (lub.exclude(home, i, j, d)) 00360 return processLubChange(home, d); 00361 return ME_SET_NONE; 00362 } 00363 00364 forceinline ModEvent 00365 SetVarImp::exclude(Space& home, int i) { 00366 return exclude(home, i, i); 00367 } 00368 00369 template<class I> 00370 inline ModEvent 00371 SetVarImp::excludeI(Space& home, I& iterator) { 00372 if (!iterator()) 00373 return ME_SET_NONE; 00374 if (assigned()) { 00375 BndSetRanges ubi(lub); 00376 Iter::Ranges::Inter<BndSetRanges,I> probe(ubi,iterator); 00377 return probe() ? ME_SET_FAILED : ME_SET_NONE; 00378 } 00379 int mi=iterator.min(); 00380 int ma=iterator.max(); 00381 ++iterator; 00382 if (iterator()) 00383 return excludeI_full(home, mi, ma, iterator); 00384 else 00385 return exclude(home, mi, ma); 00386 } 00387 00388 template<class I> 00389 ModEvent 00390 SetVarImp::excludeI_full(Space& home, int mi, int ma, I& iterator) { 00391 Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator); 00392 if (lub.excludeI(home, si)) { 00393 BndSetRanges ub(lub); 00394 BndSetRanges lb(glb); 00395 if (!Iter::Ranges::subset(lb,ub)) { 00396 glb.become(home, lub); 00397 glb.card(glb.size()); 00398 lub.card(glb.size()); 00399 return ME_SET_FAILED; 00400 } 00401 ModEvent me = ME_SET_LUB; 00402 if (cardMax() > lub.size()) { 00403 lub.card(lub.size()); 00404 if (cardMin() > cardMax()) { 00405 glb.become(home, lub); 00406 glb.card(glb.size()); 00407 lub.card(glb.size()); 00408 return ME_SET_FAILED; 00409 } 00410 me = ME_SET_CLUB; 00411 } 00412 if (cardMax() == lub.size() && cardMin() == cardMax()) { 00413 glb.become(home, lub); 00414 me = ME_SET_VAL; 00415 } 00416 SetDelta d; 00417 return notify(home, me, d); 00418 } 00419 return ME_SET_NONE; 00420 } 00421 00422 /* 00423 * Copying a variable 00424 * 00425 */ 00426 00427 forceinline SetVarImp* 00428 SetVarImp::copy(Space& home, bool share) { 00429 return copied() ? 00430 static_cast<SetVarImp*>(forward()) : 00431 perform_copy(home,share); 00432 } 00433 00434 /* 00435 * Iterator specializations 00436 * 00437 */ 00438 00447 template<> 00448 class LubRanges<SetVarImp*> : public BndSetRanges { 00449 public: 00451 00452 00453 LubRanges(void); 00455 LubRanges(const SetVarImp*); 00457 void init(const SetVarImp*); 00459 }; 00460 00461 forceinline 00462 LubRanges<SetVarImp*>::LubRanges(void) {} 00463 00464 forceinline 00465 LubRanges<SetVarImp*>::LubRanges(const SetVarImp* x) 00466 : BndSetRanges(x->lub) {} 00467 00468 forceinline void 00469 LubRanges<SetVarImp*>::init(const SetVarImp* x) { 00470 BndSetRanges::init(x->lub); 00471 } 00472 00481 template<> 00482 class GlbRanges<SetVarImp*> : public BndSetRanges { 00483 public: 00485 00486 00487 GlbRanges(void); 00489 GlbRanges(const SetVarImp* x); 00491 void init(const SetVarImp*); 00493 }; 00494 00495 forceinline 00496 GlbRanges<SetVarImp*>::GlbRanges(void) {} 00497 00498 forceinline 00499 GlbRanges<SetVarImp*>::GlbRanges(const SetVarImp* x) 00500 : BndSetRanges(x->glb) {} 00501 00502 forceinline void 00503 GlbRanges<SetVarImp*>::init(const SetVarImp* x) { 00504 BndSetRanges::init(x->glb); 00505 } 00506 00507 00508 /* 00509 * Dependencies 00510 * 00511 */ 00512 forceinline void 00513 SetVarImp::subscribe(Space& home, Propagator& p, PropCond pc, bool schedule) { 00514 SetVarImpBase::subscribe(home,p,pc,assigned(),schedule); 00515 } 00516 forceinline void 00517 SetVarImp::cancel(Space& home, Propagator& p, PropCond pc) { 00518 SetVarImpBase::cancel(home,p,pc,assigned()); 00519 } 00520 forceinline void 00521 SetVarImp::subscribe(Space& home, Advisor& a) { 00522 SetVarImpBase::subscribe(home,a,assigned()); 00523 } 00524 forceinline void 00525 SetVarImp::cancel(Space& home, Advisor& a) { 00526 SetVarImpBase::cancel(home,a,assigned()); 00527 } 00528 00529 }} 00530 00531 // STATISTICS: set-var