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 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Contributing authors: 00007 * Guido Tack <tack@gecode.org> 00008 * 00009 * Copyright: 00010 * Christian Schulte, 2002 00011 * Guido Tack, 2004 00012 * 00013 * Last modified: 00014 * $Date: 2010-06-02 21:01:00 +0200 (Wed, 02 Jun 2010) $ by $Author: schulte $ 00015 * $Revision: 11008 $ 00016 * 00017 * This file is part of Gecode, the generic constraint 00018 * development environment: 00019 * http://www.gecode.org 00020 * 00021 * Permission is hereby granted, free of charge, to any person obtaining 00022 * a copy of this software and associated documentation files (the 00023 * "Software"), to deal in the Software without restriction, including 00024 * without limitation the rights to use, copy, modify, merge, publish, 00025 * distribute, sublicense, and/or sell copies of the Software, and to 00026 * permit persons to whom the Software is furnished to do so, subject to 00027 * the following conditions: 00028 * 00029 * The above copyright notice and this permission notice shall be 00030 * included in all copies or substantial portions of the Software. 00031 * 00032 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00033 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00034 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00035 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00036 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00037 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00038 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00039 * 00040 */ 00041 00042 #include <cmath> 00043 00044 namespace Gecode { namespace Int { 00045 00046 class IntVarImp; 00047 class BoolVarImp; 00048 00055 class IntDelta : public Delta { 00056 friend class IntVarImp; 00057 friend class BoolVarImp; 00058 private: 00059 int _min; 00060 int _max; 00061 public: 00063 IntDelta(void); 00065 IntDelta(int min, int max); 00067 IntDelta(int min); 00068 private: 00070 int min(void) const; 00072 int max(void) const; 00074 bool any(void) const; 00075 }; 00076 00077 }} 00078 00079 #include <gecode/int/var-imp/delta.hpp> 00080 00081 namespace Gecode { namespace Int { 00082 00083 class IntVarImpFwd; 00084 class IntVarImpBwd; 00085 00091 class IntVarImp : public IntVarImpBase { 00092 friend class IntVarImpFwd; 00093 friend class IntVarImpBwd; 00094 protected: 00104 class RangeList : public FreeList { 00105 protected: 00107 int _min; 00109 int _max; 00110 public: 00112 00113 00114 RangeList(void); 00116 RangeList(int min, int max); 00118 RangeList(int min, int max, RangeList* p, RangeList* n); 00120 00122 00123 00124 int min(void) const; 00126 int max(void) const; 00128 unsigned int width(void) const; 00129 00131 RangeList* next(const RangeList* p) const; 00133 RangeList* prev(const RangeList* n) const; 00135 00137 00138 00139 void min(int n); 00141 void max(int n); 00142 00144 void prevnext(RangeList* p, RangeList* n); 00146 void next(RangeList* o, RangeList* n); 00148 void prev(RangeList* o, RangeList* n); 00150 void fix(RangeList* n); 00152 00154 00155 00160 void dispose(Space& home, RangeList* p, RangeList* l); 00166 void dispose(Space& home, RangeList* l); 00168 void dispose(Space& home); 00169 00171 static void* operator new(size_t s, Space& home); 00173 static void* operator new(size_t s, void* p); 00175 static void operator delete(void*); 00177 static void operator delete(void*, Space&); 00179 static void operator delete(void*, void*); 00181 }; 00182 00190 RangeList dom; 00192 RangeList* _lst; 00194 RangeList* fst(void) const; 00196 void fst(RangeList* f); 00198 RangeList* lst(void) const; 00200 void lst(RangeList* l); 00202 unsigned int holes; 00203 00204 protected: 00206 IntVarImp(Space& home, bool share, IntVarImp& x); 00207 public: 00209 IntVarImp(Space& home, int min, int max); 00211 IntVarImp(Space& home, const IntSet& d); 00212 00214 00215 00216 int min(void) const; 00218 int max(void) const; 00220 int val(void) const; 00222 GECODE_INT_EXPORT int med(void) const; 00223 00225 unsigned int size(void) const; 00227 unsigned int width(void) const; 00229 unsigned int regret_min(void) const; 00231 unsigned int regret_max(void) const; 00233 00234 private: 00236 GECODE_INT_EXPORT bool in_full(int n) const; 00237 00238 public: 00240 00241 00242 bool range(void) const; 00244 bool assigned(void) const; 00245 00247 bool in(int n) const; 00249 bool in(double n) const; 00251 00252 protected: 00254 00255 00256 const RangeList* ranges_fwd(void) const; 00258 const RangeList* ranges_bwd(void) const; 00260 00261 private: 00263 bool closer_min(int b) const; 00265 00266 00267 GECODE_INT_EXPORT ModEvent lq_full(Space& home, int n); 00269 GECODE_INT_EXPORT ModEvent gq_full(Space& home, int n); 00271 GECODE_INT_EXPORT ModEvent eq_full(Space& home, int n); 00273 GECODE_INT_EXPORT ModEvent nq_full(Space& home, int n); 00275 public: 00277 00278 00279 ModEvent lq(Space& home, int n); 00281 ModEvent lq(Space& home, double n); 00282 00284 ModEvent gq(Space& home, int n); 00286 ModEvent gq(Space& home, double n); 00287 00289 ModEvent nq(Space& home, int n); 00291 ModEvent nq(Space& home, double n); 00292 00294 ModEvent eq(Space& home, int n); 00296 ModEvent eq(Space& home, double n); 00298 00315 00316 template<class I> 00317 ModEvent narrow_r(Space& home, I& i, bool depends=true); 00319 template<class I> 00320 ModEvent inter_r(Space& home, I& i, bool depends=true); 00322 template<class I> 00323 ModEvent minus_r(Space& home, I& i, bool depends=true); 00325 template<class I> 00326 ModEvent narrow_v(Space& home, I& i, bool depends=true); 00328 template<class I> 00329 ModEvent inter_v(Space& home, I& i, bool depends=true); 00331 template<class I> 00332 ModEvent minus_v(Space& home, I& i, bool depends=true); 00334 00336 00337 00345 void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true); 00347 void cancel(Space& home, Propagator& p, PropCond pc); 00349 void subscribe(Space& home, Advisor& a); 00351 void cancel(Space& home, Advisor& a); 00353 00355 00356 00357 static ModEventDelta med(ModEvent me); 00359 00360 00361 private: 00363 GECODE_INT_EXPORT IntVarImp* perform_copy(Space& home, bool share); 00364 public: 00366 00367 00368 IntVarImp* copy(Space& home, bool share); 00370 00372 00373 00374 static int min(const Delta& d); 00376 static int max(const Delta& d); 00378 static bool any(const Delta& d); 00380 }; 00381 00382 00387 class IntVarImpFwd { 00388 private: 00390 const IntVarImp::RangeList* p; 00392 const IntVarImp::RangeList* c; 00393 public: 00395 00396 00397 IntVarImpFwd(void); 00399 IntVarImpFwd(const IntVarImp* x); 00401 void init(const IntVarImp* x); 00403 00405 00406 00407 bool operator ()(void) const; 00409 void operator ++(void); 00411 00413 00414 00415 int min(void) const; 00417 int max(void) const; 00419 unsigned int width(void) const; 00421 }; 00422 00430 class IntVarImpBwd { 00431 private: 00433 const IntVarImp::RangeList* n; 00435 const IntVarImp::RangeList* c; 00436 public: 00438 00439 00440 IntVarImpBwd(void); 00442 IntVarImpBwd(const IntVarImp* x); 00444 void init(const IntVarImp* x); 00446 00448 00449 00450 bool operator ()(void) const; 00452 void operator ++(void); 00454 00456 00457 00458 int min(void) const; 00460 int max(void) const; 00462 unsigned int width(void) const; 00464 }; 00465 00466 }} 00467 00468 #include <gecode/int/var-imp/int.hpp> 00469 00470 namespace Gecode { 00471 00472 class IntVar; 00473 class BoolVar; 00474 } 00475 00476 namespace Gecode { namespace Int { 00477 00479 typedef unsigned int BoolStatus; 00480 00486 class BoolVarImp : public BoolVarImpBase { 00487 friend class ::Gecode::BoolVar; 00488 private: 00500 GECODE_INT_EXPORT static BoolVarImp s_one; 00501 GECODE_INT_EXPORT static BoolVarImp s_zero; 00502 00504 BoolVarImp(Space& home, bool share, BoolVarImp& x); 00506 BoolVarImp(int n); 00507 public: 00509 BoolVarImp(Space& home, int min, int max); 00510 00512 00513 00514 static const int BITS = 2; 00516 static const BoolStatus ZERO = 0; 00518 static const BoolStatus ONE = 3; 00520 static const BoolStatus NONE = 2; 00522 BoolStatus status(void) const; 00524 00526 00527 00528 int min(void) const; 00530 int max(void) const; 00532 int val(void) const; 00534 int med(void) const; 00535 00537 unsigned int size(void) const; 00539 unsigned int width(void) const; 00541 unsigned int regret_min(void) const; 00543 unsigned int regret_max(void) const; 00545 00547 00548 00549 bool zero(void) const; 00551 bool one(void) const; 00553 bool none(void) const; 00555 00557 00558 00559 bool range(void) const; 00561 bool assigned(void) const; 00562 00564 bool in(int n) const; 00566 bool in(double n) const; 00568 00570 00571 00572 ModEvent lq(Space& home, int n); 00574 ModEvent lq(Space& home, double n); 00575 00577 ModEvent gq(Space& home, int n); 00579 ModEvent gq(Space& home, double n); 00580 00582 ModEvent nq(Space& home, int n); 00584 ModEvent nq(Space& home, double n); 00585 00587 ModEvent eq(Space& home, int n); 00589 ModEvent eq(Space& home, double n); 00591 00608 00609 template<class I> 00610 ModEvent narrow_r(Space& home, I& i, bool depends=true); 00612 template<class I> 00613 ModEvent inter_r(Space& home, I& i, bool depends=true); 00615 template<class I> 00616 ModEvent minus_r(Space& home, I& i, bool depends=true); 00618 template<class I> 00619 ModEvent narrow_v(Space& home, I& i, bool depends=true); 00621 template<class I> 00622 ModEvent inter_v(Space& home, I& i, bool depends=true); 00624 template<class I> 00625 ModEvent minus_v(Space& home, I& i, bool depends=true); 00627 00629 00630 00631 ModEvent zero(Space& home); 00633 ModEvent one(Space& home); 00635 GECODE_INT_EXPORT ModEvent zero_none(Space& home); 00637 GECODE_INT_EXPORT ModEvent one_none(Space& home); 00639 00640 public: 00642 00643 00653 void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true); 00660 void cancel(Space& home, Propagator& p, PropCond pc); 00662 void subscribe(Space& home, Advisor& a); 00664 void cancel(Space& home, Advisor& a); 00666 00668 00669 00676 static void schedule(Space& home, Propagator& p, ModEvent me); 00678 static ModEventDelta med(ModEvent me); 00680 00682 00683 00684 static ModEvent modevent(const Delta& d); 00686 static int min(const Delta& d); 00688 static int max(const Delta& d); 00690 static bool any(const Delta& d); 00692 static bool zero(const Delta& d); 00694 static bool one(const Delta& d); 00696 00698 00699 00700 BoolVarImp* copy(Space& home, bool share); 00702 00703 }; 00704 00705 }} 00706 00707 #include <gecode/int/var-imp/bool.hpp> 00708 00709 // STATISTICS: int-var 00710