var-imp.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 * 00006 * Contributing authors: 00007 * Christian Schulte <schulte@gecode.org> 00008 * Gabor Szokoli <szokoli@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 21:01:00 +0200 (Wed, 02 Jun 2010) $ by $Author: schulte $ 00017 * $Revision: 11008 $ 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 #include <iostream> 00045 00046 namespace Gecode { namespace Set { 00047 00048 class SetVarImp; 00049 class LUBndSet; 00050 class GLBndSet; 00051 00056 class SetDelta : public Delta { 00057 friend class SetVarImp; 00058 friend class LUBndSet; 00059 friend class GLBndSet; 00060 private: 00061 int _glbMin; 00062 int _glbMax; 00063 int _lubMin; 00064 int _lubMax; 00065 public: 00067 SetDelta(void); 00069 SetDelta(int glbMin, int glbMax, int lubMin, int lubMax); 00071 int glbMin(void) const; 00073 int glbMax(void) const; 00075 int lubMin(void) const; 00077 int lubMax(void) const; 00079 bool glbAny(void) const; 00081 bool lubAny(void) const; 00082 }; 00083 00084 }} 00085 00086 #include <gecode/set/var-imp/delta.hpp> 00087 00088 namespace Gecode { namespace Set { 00089 00094 class RangeList : public FreeList { 00095 protected: 00097 int _min; 00099 int _max; 00100 public: 00102 00103 00104 RangeList(void); 00106 RangeList(int min, int max, RangeList* n); 00108 00110 00111 00112 int min(void) const; 00114 int max(void) const; 00116 unsigned int width(void) const; 00117 00119 RangeList* next(void) const; 00121 00123 00124 00125 void min(int n); 00127 void max(int n); 00129 void next(RangeList* n); 00131 00133 00134 00137 void dispose(Space& home, RangeList* l); 00138 00140 static void* operator new(size_t s, Space& home); 00142 static void* operator new(size_t s, void* p); 00144 static void operator delete(void*); 00146 static void operator delete(void*, Space& home); 00148 static void operator delete(void*, void*); 00150 }; 00151 00152 00156 class BndSet { 00157 private: 00158 RangeList* first; 00159 RangeList* last; 00160 protected: 00162 unsigned int _size; 00164 unsigned int _card; 00166 void fst(RangeList* r); 00168 void lst(RangeList* r); 00169 00171 RangeList* fst(void) const; 00173 RangeList* lst(void) const; 00174 00175 public: 00177 static const int MAX_OF_EMPTY = Limits::min-1; 00179 static const int MIN_OF_EMPTY = Limits::max+1; 00180 00182 00183 00184 BndSet(void); 00186 BndSet(Space& home, int i, int j); 00188 BndSet(Space& home, const IntSet& s); 00190 00192 00193 00194 void dispose(Space& home); 00196 00198 00199 00200 int min(void) const; 00202 int max(void) const; 00204 int minN(unsigned int n) const; 00206 unsigned int size(void) const; 00208 unsigned int card(void) const; 00210 void card(unsigned int c); 00212 00214 00215 00216 bool empty(void) const; 00218 bool in(int i) const; 00220 00222 00223 00224 void become(Space& home, const BndSet& s); 00226 00228 00229 00230 RangeList* ranges(void) const; 00232 00233 protected: 00235 template<class I> bool overwrite(Space& home,I& i); 00236 00237 public: 00239 00240 00241 void update(Space& home, BndSet& x); 00243 00245 GECODE_SET_EXPORT bool isConsistent(void) const; 00246 }; 00247 00252 class BndSetRanges { 00253 private: 00255 const RangeList* c; 00256 public: 00258 00259 00260 BndSetRanges(void); 00262 BndSetRanges(const BndSet& s); 00264 void init(const BndSet& s); 00266 00268 00269 00270 bool operator ()(void) const; 00272 void operator ++(void); 00274 00276 00277 00278 int min(void) const; 00280 int max(void) const; 00282 unsigned int width(void) const; 00284 }; 00285 00293 class GLBndSet : public BndSet { 00294 private: 00296 GECODE_SET_EXPORT bool include_full(Space& home,int,int,SetDelta&); 00297 public: 00299 00300 00301 GLBndSet(void); 00303 GLBndSet(Space&); 00305 GLBndSet(Space& home, int i, int j); 00307 GLBndSet(Space& home, const IntSet& s); 00309 void init(Space& home); 00311 00313 00314 00315 bool include(Space& home,int i,int j,SetDelta& d); 00317 template<class I> bool includeI(Space& home,I& i); 00319 private: 00320 GLBndSet(const GLBndSet&); 00321 const GLBndSet& operator =(const GLBndSet&); 00322 }; 00323 00331 class LUBndSet: public BndSet{ 00332 private: 00333 GECODE_SET_EXPORT bool exclude_full(Space& home, int, int, SetDelta&); 00334 GECODE_SET_EXPORT bool intersect_full(Space& home, int i, int j); 00335 public: 00337 00338 00339 LUBndSet(void); 00341 LUBndSet(Space& home); 00343 LUBndSet(Space& home, int i, int j); 00345 LUBndSet(Space& home, const IntSet& s); 00347 void init(Space& home); 00349 00351 00352 00353 bool exclude(Space& home, int i, int j, SetDelta& d); 00355 bool intersect(Space& home, int i, int j); 00357 template<class I> bool intersectI(Space& home, I& i); 00359 template<class I> bool excludeI(Space& home, I& i); 00361 void excludeAll(Space& home); 00363 private: 00364 LUBndSet(const LUBndSet&); 00365 const LUBndSet& operator =(const LUBndSet&); 00366 }; 00367 00368 /* 00369 * Iterators 00370 * 00371 */ 00372 00373 00379 template<class I> 00380 class RangesCompl : 00381 public Iter::Ranges::Compl<Limits::min, Limits::max, I> { 00382 public: 00384 00385 00386 RangesCompl(void); 00388 RangesCompl(I& i); 00390 void init(I& i); 00392 }; 00393 00405 template<class T> class LubRanges { 00406 public: 00408 00409 00410 LubRanges(void); 00412 LubRanges(const T& x); 00414 void init(const T& x); 00416 00418 00419 00420 bool operator ()(void) const; 00422 void operator ++(void); 00424 00426 00427 00428 int min(void) const; 00430 int max(void) const; 00432 unsigned int width(void) const; 00434 }; 00435 00447 template<class T> class GlbRanges { 00448 public: 00450 00451 00452 GlbRanges(void); 00454 GlbRanges(const T& x); 00456 void init(const T& x); 00458 00460 00461 00462 bool operator ()(void) const; 00464 void operator ++(void); 00466 00468 00469 00470 int min(void) const; 00472 int max(void) const; 00474 unsigned int width(void) const; 00476 }; 00477 00489 template<class T> 00490 class UnknownRanges : public Iter::Ranges::Diff<LubRanges<T>, GlbRanges<T> >{ 00491 private: 00492 LubRanges<T> i1; 00493 GlbRanges<T> i2; 00494 public: 00496 00497 00498 UnknownRanges(void); 00500 UnknownRanges(const T& x); 00502 void init(const T& x); 00504 }; 00505 00506 }} 00507 00508 #include <gecode/set/var-imp/integerset.hpp> 00509 #include <gecode/set/var-imp/iter.hpp> 00510 00511 namespace Gecode { namespace Set { 00512 00518 class SetVarImp : public SetVarImpBase { 00519 friend class LubRanges<SetVarImp*>; 00520 friend class GlbRanges<SetVarImp*>; 00521 private: 00523 LUBndSet lub; 00525 GLBndSet glb; 00526 00527 protected: 00529 SetVarImp(Space& home, bool share, SetVarImp& x); 00530 public: 00532 00533 00534 SetVarImp(Space& home); 00543 SetVarImp(Space& home,int glbMin,int glbMax,int lubMin,int lubMax, 00544 unsigned int cardMin = 0, 00545 unsigned int cardMax = Limits::card); 00554 SetVarImp(Space& home,const IntSet& glbD,int lubMin,int lubMax, 00555 unsigned int cardMin,unsigned int cardMax); 00564 SetVarImp(Space& home,int glbMin,int glbMax,const IntSet& lubD, 00565 unsigned int cardMin,unsigned int cardMax); 00574 SetVarImp(Space& home,const IntSet& glbD,const IntSet& lubD, 00575 unsigned int cardMin,unsigned int cardMax); 00577 00579 00580 00581 unsigned int cardMin(void) const; 00583 unsigned int cardMax(void) const; 00585 int lubMin(void) const; 00587 int lubMax(void) const; 00589 int lubMinN(unsigned int n) const; 00591 int glbMin(void) const; 00593 int glbMax(void) const; 00595 unsigned int glbSize(void) const; 00597 unsigned int lubSize(void) const; 00599 00601 00602 00603 bool assigned(void) const; 00605 bool knownIn(int n) const; 00607 bool knownOut(int) const; 00609 00610 private: 00612 00613 00614 template<class I> ModEvent includeI_full(Space& home,int mi, int ma, I& i); 00616 template<class I> ModEvent excludeI_full(Space& home,int mi, int ma, I& i); 00618 template<class I> ModEvent intersectI_full(Space& home,int mi, int ma, I& i); 00620 00621 GECODE_SET_EXPORT ModEvent processLubChange(Space& home, SetDelta& d); 00622 GECODE_SET_EXPORT ModEvent processGlbChange(Space& home, SetDelta& d); 00623 00625 00626 00627 GECODE_SET_EXPORT ModEvent cardMin_full(Space& home); 00629 GECODE_SET_EXPORT ModEvent cardMax_full(Space& home); 00631 00632 public: 00633 00635 00636 00637 ModEvent include(Space& home,int n); 00639 ModEvent include(Space& home,int i,int j); 00641 ModEvent exclude(Space& home,int n); 00643 ModEvent exclude(Space& home,int i,int j); 00645 ModEvent intersect(Space& home,int n); 00647 ModEvent intersect(Space& home,int i,int j); 00649 ModEvent cardMin(Space& home,unsigned int n); 00651 ModEvent cardMax(Space& home,unsigned int n); 00653 00655 00656 00657 template<class I> ModEvent includeI(Space& home,I& i); 00659 template<class I> ModEvent excludeI(Space& home,I& i); 00661 template<class I> ModEvent intersectI(Space& home,I& i); 00663 00664 public: 00666 00667 00674 void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true); 00676 void cancel(Space& home, Propagator& p, PropCond pc); 00678 void subscribe(Space& home, Advisor& a); 00680 void cancel(Space& home, Advisor& a); 00682 00683 private: 00685 GECODE_SET_EXPORT SetVarImp* perform_copy(Space& home, bool share); 00686 00687 public: 00689 00690 00691 SetVarImp* copy(Space& home, bool share); 00693 00695 00696 00697 static int glbMin(const Delta& d); 00699 static int glbMax(const Delta& d); 00701 static bool glbAny(const Delta& d); 00703 static int lubMin(const Delta& d); 00705 static int lubMax(const Delta& d); 00707 static bool lubAny(const Delta& d); 00709 00710 }; 00711 00712 class SetView; 00713 00714 }} 00715 00716 #include <gecode/set/var-imp/set.hpp> 00717 00718 // STATISTICS: set-var