Generated on Mon Nov 30 23:53:30 2009 for Gecode by doxygen 1.6.1

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: 2009-09-08 21:10:29 +0200 (Tue, 08 Sep 2009) $ by $Author: schulte $
00015  *     $Revision: 9692 $
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 process=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 ModEvent modevent(const Delta& d);
00376     static int min(const Delta& d);
00378     static int max(const Delta& d);
00380     static bool any(const Delta& d);
00382   };
00383 
00384 
00389   class IntVarImpFwd {
00390   private:
00392     const IntVarImp::RangeList* p;
00394     const IntVarImp::RangeList* c;
00395   public:
00397 
00398 
00399     IntVarImpFwd(void);
00401     IntVarImpFwd(const IntVarImp* x);
00403     void init(const IntVarImp* x);
00405 
00407 
00408 
00409     bool operator ()(void) const;
00411     void operator ++(void);
00413 
00415 
00416 
00417     int min(void) const;
00419     int max(void) const;
00421     unsigned int width(void) const;
00423   };
00424 
00432   class IntVarImpBwd {
00433   private:
00435     const IntVarImp::RangeList* n;
00437     const IntVarImp::RangeList* c;
00438   public:
00440 
00441 
00442     IntVarImpBwd(void);
00444     IntVarImpBwd(const IntVarImp* x);
00446     void init(const IntVarImp* x);
00448 
00450 
00451 
00452     bool operator ()(void) const;
00454     void operator ++(void);
00456 
00458 
00459 
00460     int min(void) const;
00462     int max(void) const;
00464     unsigned int width(void) const;
00466   };
00467 
00468 }}
00469 
00470 #include <gecode/int/var-imp/int.hpp>
00471 
00472 namespace Gecode {
00473 
00474   class IntVar;
00475 
00477   template<>
00478   class VarImpVarTraits<Int::IntVarImp> {
00479   public:
00480     typedef IntVar Var;
00481   };
00482 
00483   class BoolVar;
00484 }
00485 
00486 namespace Gecode { namespace Int {
00487 
00489   typedef unsigned int BoolStatus;
00490 
00496   class BoolVarImp : public BoolVarImpBase {
00497     friend class ::Gecode::BoolVar;
00498   private:
00510     GECODE_INT_EXPORT static BoolVarImp s_one;
00511     GECODE_INT_EXPORT static BoolVarImp s_zero;
00512 
00514     BoolVarImp(Space& home, bool share, BoolVarImp& x);
00516     BoolVarImp(int n);
00517   public:
00519     BoolVarImp(Space& home, int min, int max);
00520 
00522 
00523 
00524     static const int BITS = 2;
00526     static const BoolStatus ZERO = 0;
00528     static const BoolStatus ONE  = 3;
00530     static const BoolStatus NONE = 2;
00532     BoolStatus status(void) const;
00534 
00536 
00537 
00538     int min(void) const;
00540     int max(void) const;
00542     int val(void) const;
00544     int med(void) const;
00545 
00547     unsigned int size(void) const;
00549     unsigned int width(void) const;
00551     unsigned int regret_min(void) const;
00553     unsigned int regret_max(void) const;
00555 
00557 
00558 
00559     bool zero(void) const;
00561     bool one(void) const;
00563     bool none(void) const;
00565 
00567 
00568 
00569     bool range(void) const;
00571     bool assigned(void) const;
00572 
00574     bool in(int n) const;
00576     bool in(double n) const;
00578 
00580 
00581 
00582     ModEvent lq(Space& home, int n);
00584     ModEvent lq(Space& home, double n);
00585 
00587     ModEvent gq(Space& home, int n);
00589     ModEvent gq(Space& home, double n);
00590 
00592     ModEvent nq(Space& home, int n);
00594     ModEvent nq(Space& home, double n);
00595 
00597     ModEvent eq(Space& home, int n);
00599     ModEvent eq(Space& home, double n);
00601 
00618 
00619     template<class I>
00620     ModEvent narrow_r(Space& home, I& i, bool depends=true);
00622     template<class I>
00623     ModEvent inter_r(Space& home, I& i, bool depends=true);
00625     template<class I>
00626     ModEvent minus_r(Space& home, I& i, bool depends=true);
00628     template<class I>
00629     ModEvent narrow_v(Space& home, I& i, bool depends=true);
00631     template<class I>
00632     ModEvent inter_v(Space& home, I& i, bool depends=true);
00634     template<class I>
00635     ModEvent minus_v(Space& home, I& i, bool depends=true);
00637 
00639 
00640 
00641     ModEvent zero(Space& home);
00643     ModEvent one(Space& home);
00645     GECODE_INT_EXPORT ModEvent zero_none(Space& home);
00647     GECODE_INT_EXPORT ModEvent one_none(Space& home);
00649 
00650   public:
00652 
00653 
00663     void subscribe(Space& home, Propagator& p, PropCond pc, bool process=true);
00670     void cancel(Space& home, Propagator& p, PropCond pc);
00672     void subscribe(Space& home, Advisor& a);
00674     void cancel(Space& home, Advisor& a);
00676 
00678 
00679 
00686     static void schedule(Space& home, Propagator& p, ModEvent me);
00688     static ModEventDelta med(ModEvent me);
00690 
00692 
00693 
00694     static ModEvent modevent(const Delta& d);
00696     static int min(const Delta& d);
00698     static int max(const Delta& d);
00700     static bool any(const Delta& d);
00702     static bool zero(const Delta& d);
00704     static bool one(const Delta& d);
00706 
00708 
00709 
00710     BoolVarImp* copy(Space& home, bool share);
00712 
00713   };
00714 
00715 }}
00716 
00717 #include <gecode/int/var-imp/bool.hpp>
00718 
00719 namespace Gecode {
00721   template<>
00722   class VarImpVarTraits<Int::BoolVarImp> {
00723   public:
00724     typedef BoolVar Var;
00725   };
00726 }
00727 
00728 // STATISTICS: int-var
00729