Generated on Wed Jan 4 17:49:12 2006 for Gecode by doxygen 1.4.6

var.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Guido Tack <tack@gecode.org>
00004  *
00005  *  Contributing authors:
00006  *     Christian Schulte <schulte@gecode.org>
00007  *     Gabor Szokoli <szokoli@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Guido Tack, 2004
00011  *     Christian Schulte, 2004
00012  *     Gabor Szokoli, 2004
00013  *
00014  *  Last modified:
00015  *     $Date: 2005-11-29 18:02:48 +0100 (Tue, 29 Nov 2005) $ by $Author: tack $
00016  *     $Revision: 2665 $
00017  *
00018  *  This file is part of Gecode, the generic constraint
00019  *  development environment:
00020  *     http://www.gecode.org
00021  *
00022  *  See the file "LICENSE" for information on usage and
00023  *  redistribution of this file, and for a
00024  *     DISCLAIMER OF ALL WARRANTIES.
00025  *
00026  */
00027 
00028 #include "support/shared-array.hh"
00029 
00030 #include <iostream>
00031 #include "iter.hh"
00032 
00033 namespace Gecode { namespace Set {
00034 
00041 
00043   const ModEvent ME_SET_FAILED = ME_GEN_FAILED;
00045   const ModEvent ME_SET_NONE  = ME_GEN_NONE;
00047   const ModEvent ME_SET_VAL   = ME_GEN_ASSIGNED;
00048 
00054   const ModEvent ME_SET_CARD  = ME_SET_VAL + 1;
00062   const ModEvent ME_SET_LUB   = ME_SET_CARD + 1;
00070   const ModEvent ME_SET_GLB   = ME_SET_LUB + 1;
00078   const ModEvent ME_SET_BB    = ME_SET_GLB + 1;
00085   const ModEvent ME_SET_CLUB  = ME_SET_BB + 1;
00092   const ModEvent ME_SET_CGLB  = ME_SET_CLUB + 1;
00099   const ModEvent ME_SET_CBB   = ME_SET_CGLB + 1;
00100 
00101 
00102 
00110   const PropCond PC_SET_VAL  = PC_GEN_ASSIGNED;
00119   const PropCond PC_SET_CARD = PC_SET_VAL + 1;
00130   const PropCond PC_SET_CGLB = PC_SET_CARD + 1;
00141   const PropCond PC_SET_CLUB = PC_SET_CGLB + 1;
00151   const PropCond PC_SET_ANY  = PC_SET_CLUB + 1;
00153 
00154 
00159   class RangeList : public FreeList {
00160   protected:
00162     int        _min;
00164     int        _max;
00165   public:
00167 
00168 
00169     RangeList(void);
00171     RangeList(int min, int max, RangeList* p, RangeList* n);
00173 
00175 
00176 
00177     int min(void) const;
00179     int max(void) const;
00181     unsigned int width(void) const;
00182 
00184     RangeList* next(const RangeList* p) const;
00186     RangeList* prev(const RangeList* n) const;
00188 
00190 
00191 
00192     void min(int n);
00194     void max(int n);
00195 
00197     void prevnext(RangeList* p, RangeList* n);
00199     void next(RangeList* o, RangeList* n);
00201     void prev(RangeList* o, RangeList* n);
00203     void fix(RangeList* n);
00205 
00207 
00208 
00213     void dispose(Space* home, RangeList* p, RangeList* l);
00214     
00216     static void* operator new(size_t s, Space* home);
00218     static void  operator delete(void*);
00220     static void  operator delete(void*, Space* home);
00222   };
00223 
00224 
00228   class BndSet  {
00229   private:
00230     RangeList* first;
00231     RangeList* last;
00232   protected:
00234     unsigned int _size;
00236     void fst(RangeList* r);
00238     void lst(RangeList* r);
00239 
00241     RangeList* fst(void) const;
00243     RangeList* lst(void) const;
00244 
00245   public:
00247     static const int MAX_OF_EMPTY = Limits::Set::int_min-1;
00249     static const int MIN_OF_EMPTY = Limits::Set::int_max+1;
00250 
00252 
00253 
00254     BndSet(void);
00256     BndSet(Space* home, int i, int j);
00258     BndSet(Space* home, const IntSet& s);
00260 
00262 
00263 
00264     void dispose(Space* home);
00266 
00268 
00269 
00270     int min(void) const;
00272     int max(void) const;
00274     int minN(unsigned int n) const;
00276     int maxN(unsigned int n) const;
00278     unsigned int size(void) const;
00280 
00282 
00283 
00284     bool empty(void) const;
00286     bool in(int i) const;
00288 
00290 
00291 
00292     void linkTo(Space* home, const BndSet& s);
00294     
00296 
00297 
00298     RangeList* ranges(void) const;
00300 
00301   protected:
00303     template <class I> bool overwrite(Space* home,I& i);
00304 
00305   public:
00307 
00308 
00309     void update(Space* home, BndSet& x);
00311 
00312 #ifndef NDEBUG
00313 
00314     GECODE_SET_EXPORT bool isConsistent(void) const;
00315 #endif
00316   };
00317 
00322   class BndSetRanges {
00323   private:
00325     const RangeList* p;
00327     const RangeList* c;
00328   public:
00330 
00331 
00332     BndSetRanges(void);
00334     BndSetRanges(const BndSet& s);
00336     void init(const BndSet& s);
00338 
00340 
00341 
00342     bool operator()(void) const;
00344     void operator++(void);
00346 
00348 
00349 
00350     int min(void) const;
00352     int max(void) const;
00354     unsigned int width(void) const;
00356   };
00357 
00365   class GLBndSet : public BndSet {
00366   private:
00368     GECODE_SET_EXPORT bool include_full(Space* home,int,int);
00369   public:
00371 
00372 
00373     GLBndSet(Space* =NULL);
00375     GLBndSet(Space* home, int i, int j);
00377     GLBndSet(Space* home, const IntSet& s);
00379     void init(Space* home);
00381 
00383 
00384 
00385     bool include(Space* home,int i,int j);
00387     template <class I> bool includeI(Space* home,I& i);
00389   private:
00390     GLBndSet(const GLBndSet&);
00391     const GLBndSet& operator=(const GLBndSet&);
00392   };
00393 
00401   class LUBndSet: public BndSet{
00402   private:
00403     GECODE_SET_EXPORT bool exclude_full(Space* home, int, int);
00404   public:
00406 
00407 
00408     LUBndSet(void);
00410     LUBndSet(Space* home);
00412     LUBndSet(Space* home, int i, int j);
00414     LUBndSet(Space* home, const IntSet& s);
00416     void init(Space* home);
00418 
00420 
00421 
00422     bool exclude(Space* home, int i, int j);
00424     template <class I> bool intersectI(Space* home, I& i);
00426     template <class I> bool excludeI(Space* home, I& i);
00428   private:
00429     LUBndSet(const LUBndSet&);
00430     const LUBndSet& operator=(const LUBndSet&);
00431   };
00432 
00433   /*
00434    * Iterators
00435    *
00436    */
00437 
00438 
00444   template <class I>
00445   class RangesCompl :
00446     public Iter::Ranges::Compl<Limits::Set::int_min, Limits::Set::int_max, I> {
00447   public:
00449 
00450 
00451     RangesCompl(void);
00453     RangesCompl(I& i);
00455     void init(I& i);
00457   };
00458 
00470   template <class T> class LubRanges {
00471   public:
00473 
00474 
00475     LubRanges(void);
00477     LubRanges(const T& x);
00479     void init(const T& x);
00481 
00483 
00484 
00485     bool operator()(void) const;
00487     void operator++(void);
00489 
00491 
00492 
00493     int min(void) const;
00495     int max(void) const;
00497     unsigned int width(void) const;
00499   };
00500   
00512   template <class T> class GlbRanges {
00513   public:
00515 
00516 
00517     GlbRanges(void);
00519     GlbRanges(const T& x);
00521     void init(const T& x);
00523 
00525 
00526 
00527     bool operator()(void) const;
00529     void operator++(void);
00531 
00533 
00534 
00535     int min(void) const;
00537     int max(void) const;
00539     unsigned int width(void) const;
00541   };
00542 
00554   template <class T>
00555   class UnknownRanges : public Iter::Ranges::Diff<LubRanges<T>, GlbRanges<T> >{
00556   private:
00557     LubRanges<T> i1;
00558     GlbRanges<T> i2;
00559   public:
00561 
00562 
00563     UnknownRanges(void);
00565     UnknownRanges(const T& x);
00567     void init(const T& x);
00569   };
00570   
00571 }}
00572 
00573 #include "set/var/integerset.icc"
00574 #include "set/var/iter.icc"
00575 
00576 namespace Gecode { namespace Set {
00577 
00583   class SetVarImp : public Variable<VTI_SET,PC_SET_ANY> {
00584     friend class LubRanges<SetVarImp*>;
00585     friend class GlbRanges<SetVarImp*>;
00586   private:
00588     LUBndSet lub;
00590     GLBndSet glb;
00592     unsigned int _cardMin;
00594     unsigned int _cardMax;
00595 
00597     class Processor : public VarTypeProcessor<VTI_SET,PC_SET_ANY> {
00598     public:
00600       Processor(void);
00601     };
00603     GECODE_SET_EXPORT static Processor svp;
00604 
00605   protected:
00607     SetVarImp(Space* home, bool share, SetVarImp& x);
00608   public:
00610 
00611 
00612     SetVarImp(Space* home);
00621     SetVarImp(Space* home,int glbMin,int glbMax,int lubMin,int lubMax,
00622                unsigned int cardMin = 0,
00623                unsigned int cardMax = Limits::Set::card_max);
00632     SetVarImp(Space* home,const IntSet& glbD,int lubMin,int lubMax,
00633               unsigned int cardMin,unsigned int cardMax);
00642     SetVarImp(Space* home,int glbMin,int glbMax,const IntSet& lubD,
00643               unsigned int cardMin,unsigned int cardMax);
00652     SetVarImp(Space* home,const IntSet& glbD,const IntSet& lubD,
00653               unsigned int cardMin,unsigned int cardMax);
00655 
00657 
00658 
00659     unsigned int cardMin(void) const;
00661     unsigned int cardMax(void) const;
00663     int lubMin(void) const;
00665     int lubMax(void) const;
00667     int lubMinN(int n) const;
00669     int lubMaxN(int n) const;
00671     int glbMin(void) const;
00673     int glbMax(void) const;
00675     unsigned int glbSize(void) const;
00677     unsigned int lubSize(void) const;
00679 
00681 
00682 
00683     bool assigned(void) const;
00685     bool knownIn(int n) const;
00687     bool knownOut(int) const;
00689 
00690   private:
00692 
00693 
00694     GECODE_SET_EXPORT ModEvent processLubChange(Space* home);
00696     GECODE_SET_EXPORT ModEvent processGlbChange(Space* home);
00703     ModEvent checkLubCardAssigned(Space* home,ModEvent me);
00710     ModEvent checkGlbCardAssigned(Space* home,ModEvent me);
00712 
00714 
00715 
00716     GECODE_SET_EXPORT ModEvent cardMin_full(Space* home,unsigned int n);
00718     GECODE_SET_EXPORT ModEvent cardMax_full(Space* home,unsigned int n);
00720 
00722     bool boundsConsistent(void) const;
00723   public:
00724 
00726 
00727 
00728     ModEvent include(Space* home,int n);
00730     ModEvent include(Space* home,int i,int j);
00732     ModEvent exclude(Space* home,int n);
00734     ModEvent exclude(Space* home,int i,int j);
00736     ModEvent intersect(Space* home,int n);
00738     ModEvent intersect(Space* home,int i,int j);
00740     ModEvent cardMin(Space* home,unsigned int n);
00742     ModEvent cardMax(Space* home,unsigned int n);
00744 
00746 
00747 
00748     template <class I> ModEvent includeI(Space* home,I& i);
00750     template <class I> ModEvent excludeI(Space* home,I& i);
00752     template <class I> ModEvent intersectI(Space* home,I& i);
00754 
00755   public:
00757 
00758 
00759     GECODE_SET_EXPORT void subscribe(Space* home,Propagator* p,PropCond pc);
00761 
00762   private:
00764     GECODE_SET_EXPORT SetVarImp* perform_copy(Space* home, bool share);
00765 
00766   public:
00768 
00769 
00770     SetVarImp* copy(Space* home, bool share);
00772 
00773   };
00774 
00775 }}
00776 
00777 #include "set/var/imp.icc"
00778 
00779 namespace Gecode {
00780 
00786   class SetVar {
00787   private:
00789     Set::SetVarImp* x;
00790   public:
00792 
00793 
00794     GECODE_SET_EXPORT SetVar(void);
00795 
00797     GECODE_SET_EXPORT SetVar(Space* home);
00799     void init(Space* home);
00800 
00818     GECODE_SET_EXPORT 
00819     SetVar(Space* home,int glbMin,int glbMax,int lubMin,int lubMax,
00820            unsigned int cardMin = 0,
00821            unsigned int cardMax = Limits::Set::card_max);
00839     void init(Space* home,int glbMin,int glbMax,int lubMin,int lubMax,
00840               unsigned int cardMin = 0,
00841               unsigned int cardMax = Limits::Set::card_max);
00842 
00860     GECODE_SET_EXPORT 
00861     SetVar(Space* home,const IntSet& glbD,int lubMin,int lubMax,
00862            unsigned int cardMin = 0,
00863            unsigned int cardMax = Limits::Set::card_max);
00881     void init(Space* home,const IntSet& glbD,int lubMin,int lubMax,
00882               unsigned int cardMin = 0,
00883               unsigned int cardMax = Limits::Set::card_max);
00884 
00902     GECODE_SET_EXPORT 
00903     SetVar(Space* home,int glbMin,int glbMax,const IntSet& lubD,
00904            unsigned int cardMin = 0,
00905            unsigned int cardMax = Limits::Set::card_max);
00923     void init(Space* home,int glbMin,int glbMax,const IntSet& lubD,
00924               unsigned int cardMin = 0,
00925               unsigned int cardMax = Limits::Set::card_max);
00926 
00944     GECODE_SET_EXPORT 
00945     SetVar(Space* home,const IntSet& glbD,const IntSet& lubD,
00946            unsigned int cardMin = 0,
00947            unsigned int cardMax = Limits::Set::card_max);
00965     void init(Space* home,const IntSet& glbD,const IntSet& lubD,
00966               unsigned int cardMin = 0,
00967               unsigned int cardMax = Limits::Set::card_max);
00969 
00971 
00972 
00973     Set::SetVarImp* variable(void) const;
00975     
00977 
00978 
00979     unsigned int glbSize(void) const;
00981     unsigned int lubSize(void) const;
00983     unsigned int unknownSize(void) const;
00985     unsigned int cardMin(void) const;
00987     unsigned int cardMax(void) const;
00989     int lubMin(void) const;
00991     int lubMax(void) const;
00993     int glbMin(void) const;
00995     int glbMax(void) const;
00997 
00999 
01000 
01001     bool contains(int i) const;
01003     bool notContains(int i) const;
01005     bool assigned(void) const;
01006 
01008 
01009 
01010     void update(Space* home, bool, SetVar& x);
01012   };
01013 
01019 
01021   class SetVarGlbRanges {
01022   private:
01023     Set::GlbRanges<Set::SetVarImp*> iter;
01024   public:
01026 
01027 
01028     SetVarGlbRanges(void);
01030     SetVarGlbRanges(const SetVar& x);
01032 
01034 
01035 
01036     bool operator()(void) const;
01038     void operator++(void);
01040 
01042 
01043 
01044     int min(void) const;
01046     int max(void) const;
01048     unsigned int width(void) const;
01050   };
01051 
01053   class SetVarLubRanges {
01054   private:
01055     Set::LubRanges<Set::SetVarImp*> iter;
01056   public:
01058 
01059 
01060     SetVarLubRanges(void);
01062     SetVarLubRanges(const SetVar& x);
01064 
01066 
01067 
01068     bool operator()(void) const;
01070     void operator++(void);
01072 
01074 
01075 
01076     int min(void) const;
01078     int max(void) const;
01080     unsigned int width(void) const;
01082   };
01083 
01085   class SetVarUnknownRanges {
01086   private:
01087     Set::UnknownRanges<Set::SetVarImp*> iter;
01088   public:
01090 
01091 
01092     SetVarUnknownRanges(void);
01094     SetVarUnknownRanges(const SetVar& x);
01096 
01098 
01099 
01100     bool operator()(void) const;
01102     void operator++(void);
01104 
01106 
01107 
01108     int min(void) const;
01110     int max(void) const;
01112     unsigned int width(void) const;
01114   };
01115   
01117   class SetVarGlbValues {
01118   private:
01119     Iter::Ranges::ToValues<SetVarGlbRanges> iter;
01120   public:
01122 
01123 
01124     SetVarGlbValues(void);
01126     SetVarGlbValues(const SetVar& x);
01128 
01130 
01131 
01132     bool operator()(void) const;
01134     void operator++(void);
01136 
01138 
01139 
01140     int  val(void) const;
01142   };
01143 
01145   class SetVarLubValues {
01146   private:
01147     Iter::Ranges::ToValues<SetVarLubRanges> iter;
01148   public:
01150 
01151 
01152     SetVarLubValues(void);
01154     SetVarLubValues(const SetVar& x);
01156 
01158 
01159 
01160     bool operator()(void) const;
01162     void operator++(void);
01164 
01166 
01167 
01168     int  val(void) const;
01170   };
01171 
01173   class SetVarUnknownValues {
01174   private:
01175     Iter::Ranges::ToValues<SetVarUnknownRanges> iter;
01176   public:
01178 
01179 
01180     SetVarUnknownValues(void);
01182     SetVarUnknownValues(const SetVar& x);
01184 
01186 
01187 
01188     bool operator()(void) const;
01190     void operator++(void);
01192 
01194 
01195 
01196     int  val(void) const;
01198   };
01199 
01201 }
01202 
01203 #include "set/var/set.icc"
01204 
01209 GECODE_SET_EXPORT std::ostream&
01210 operator<<(std::ostream&, const Gecode::SetVar& x);
01211 
01212 // STATISTICS: set-var
01213