Generated on Thu Jul 6 07:06:47 2006 for Gecode by doxygen 1.4.7

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: 2006-04-11 15:58:37 +0200 (Tue, 11 Apr 2006) $ by $Author: tack $
00016  *     $Revision: 3188 $
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 "gecode/support/shared-array.hh"
00029 
00030 #include <iostream>
00031 #include "gecode/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 
00313     GECODE_SET_EXPORT bool isConsistent(void) const;
00314   };
00315 
00320   class BndSetRanges {
00321   private:
00323     const RangeList* p;
00325     const RangeList* c;
00326   public:
00328 
00329 
00330     BndSetRanges(void);
00332     BndSetRanges(const BndSet& s);
00334     void init(const BndSet& s);
00336 
00338 
00339 
00340     bool operator()(void) const;
00342     void operator++(void);
00344 
00346 
00347 
00348     int min(void) const;
00350     int max(void) const;
00352     unsigned int width(void) const;
00354   };
00355 
00363   class GLBndSet : public BndSet {
00364   private:
00366     GECODE_SET_EXPORT bool include_full(Space* home,int,int);
00367   public:
00369 
00370 
00371     GLBndSet(Space* =NULL);
00373     GLBndSet(Space* home, int i, int j);
00375     GLBndSet(Space* home, const IntSet& s);
00377     void init(Space* home);
00379 
00381 
00382 
00383     bool include(Space* home,int i,int j);
00385     template <class I> bool includeI(Space* home,I& i);
00387   private:
00388     GLBndSet(const GLBndSet&);
00389     const GLBndSet& operator=(const GLBndSet&);
00390   };
00391 
00399   class LUBndSet: public BndSet{
00400   private:
00401     GECODE_SET_EXPORT bool exclude_full(Space* home, int, int);
00402   public:
00404 
00405 
00406     LUBndSet(void);
00408     LUBndSet(Space* home);
00410     LUBndSet(Space* home, int i, int j);
00412     LUBndSet(Space* home, const IntSet& s);
00414     void init(Space* home);
00416 
00418 
00419 
00420     bool exclude(Space* home, int i, int j);
00422     template <class I> bool intersectI(Space* home, I& i);
00424     template <class I> bool excludeI(Space* home, I& i);
00426   private:
00427     LUBndSet(const LUBndSet&);
00428     const LUBndSet& operator=(const LUBndSet&);
00429   };
00430 
00431   /*
00432    * Iterators
00433    *
00434    */
00435 
00436 
00442   template <class I>
00443   class RangesCompl :
00444     public Iter::Ranges::Compl<Limits::Set::int_min, Limits::Set::int_max, I> {
00445   public:
00447 
00448 
00449     RangesCompl(void);
00451     RangesCompl(I& i);
00453     void init(I& i);
00455   };
00456 
00468   template <class T> class LubRanges {
00469   public:
00471 
00472 
00473     LubRanges(void);
00475     LubRanges(const T& x);
00477     void init(const T& x);
00479 
00481 
00482 
00483     bool operator()(void) const;
00485     void operator++(void);
00487 
00489 
00490 
00491     int min(void) const;
00493     int max(void) const;
00495     unsigned int width(void) const;
00497   };
00498   
00510   template <class T> class GlbRanges {
00511   public:
00513 
00514 
00515     GlbRanges(void);
00517     GlbRanges(const T& x);
00519     void init(const T& x);
00521 
00523 
00524 
00525     bool operator()(void) const;
00527     void operator++(void);
00529 
00531 
00532 
00533     int min(void) const;
00535     int max(void) const;
00537     unsigned int width(void) const;
00539   };
00540 
00552   template <class T>
00553   class UnknownRanges : public Iter::Ranges::Diff<LubRanges<T>, GlbRanges<T> >{
00554   private:
00555     LubRanges<T> i1;
00556     GlbRanges<T> i2;
00557   public:
00559 
00560 
00561     UnknownRanges(void);
00563     UnknownRanges(const T& x);
00565     void init(const T& x);
00567   };
00568   
00569 }}
00570 
00571 #include "gecode/set/var/integerset.icc"
00572 #include "gecode/set/var/iter.icc"
00573 
00574 namespace Gecode { namespace Set {
00575 
00581   class SetVarImp : public Variable<VTI_SET,PC_SET_ANY> {
00582     friend class LubRanges<SetVarImp*>;
00583     friend class GlbRanges<SetVarImp*>;
00584   private:
00586     LUBndSet lub;
00588     GLBndSet glb;
00590     unsigned int _cardMin;
00592     unsigned int _cardMax;
00593 
00595     class Processor : public VarTypeProcessor<VTI_SET,PC_SET_ANY> {
00596     public:
00598       Processor(void);
00599     };
00601     GECODE_SET_EXPORT static Processor svp;
00602 
00603   protected:
00605     SetVarImp(Space* home, bool share, SetVarImp& x);
00606   public:
00608 
00609 
00610     SetVarImp(Space* home);
00619     SetVarImp(Space* home,int glbMin,int glbMax,int lubMin,int lubMax,
00620                unsigned int cardMin = 0,
00621                unsigned int cardMax = Limits::Set::card_max);
00630     SetVarImp(Space* home,const IntSet& glbD,int lubMin,int lubMax,
00631               unsigned int cardMin,unsigned int cardMax);
00640     SetVarImp(Space* home,int glbMin,int glbMax,const IntSet& lubD,
00641               unsigned int cardMin,unsigned int cardMax);
00650     SetVarImp(Space* home,const IntSet& glbD,const IntSet& lubD,
00651               unsigned int cardMin,unsigned int cardMax);
00653 
00655 
00656 
00657     unsigned int cardMin(void) const;
00659     unsigned int cardMax(void) const;
00661     int lubMin(void) const;
00663     int lubMax(void) const;
00665     int lubMinN(int n) const;
00667     int lubMaxN(int n) const;
00669     int glbMin(void) const;
00671     int glbMax(void) const;
00673     unsigned int glbSize(void) const;
00675     unsigned int lubSize(void) const;
00677 
00679 
00680 
00681     bool assigned(void) const;
00683     bool knownIn(int n) const;
00685     bool knownOut(int) const;
00687 
00688   private:
00690 
00691 
00692     GECODE_SET_EXPORT ModEvent processLubChange(Space* home);
00694     GECODE_SET_EXPORT ModEvent processGlbChange(Space* home);
00701     ModEvent checkLubCardAssigned(Space* home,ModEvent me);
00708     ModEvent checkGlbCardAssigned(Space* home,ModEvent me);
00710 
00712 
00713 
00714     GECODE_SET_EXPORT ModEvent cardMin_full(Space* home,unsigned int n);
00716     GECODE_SET_EXPORT ModEvent cardMax_full(Space* home,unsigned int n);
00718 
00720     bool boundsConsistent(void) const;
00721   public:
00722 
00724 
00725 
00726     ModEvent include(Space* home,int n);
00728     ModEvent include(Space* home,int i,int j);
00730     ModEvent exclude(Space* home,int n);
00732     ModEvent exclude(Space* home,int i,int j);
00734     ModEvent intersect(Space* home,int n);
00736     ModEvent intersect(Space* home,int i,int j);
00738     ModEvent cardMin(Space* home,unsigned int n);
00740     ModEvent cardMax(Space* home,unsigned int n);
00742 
00744 
00745 
00746     template <class I> ModEvent includeI(Space* home,I& i);
00748     template <class I> ModEvent excludeI(Space* home,I& i);
00750     template <class I> ModEvent intersectI(Space* home,I& i);
00752 
00753   public:
00755 
00756 
00757     GECODE_SET_EXPORT void subscribe(Space* home,Propagator* p,PropCond pc);
00759 
00760   private:
00762     GECODE_SET_EXPORT SetVarImp* perform_copy(Space* home, bool share);
00763 
00764   public:
00766 
00767 
00768     SetVarImp* copy(Space* home, bool share);
00770 
00771   };
00772 
00773 }}
00774 
00775 #include "gecode/set/var/imp.icc"
00776 
00777 namespace Gecode {
00778 
00784   class SetVar {
00785   private:
00787     Set::SetVarImp* x;
00788   public:
00790 
00791 
00792     GECODE_SET_EXPORT SetVar(void);
00793 
00795     GECODE_SET_EXPORT SetVar(Space* home);
00797     void init(Space* home);
00798 
00816     GECODE_SET_EXPORT 
00817     SetVar(Space* home,int glbMin,int glbMax,int lubMin,int lubMax,
00818            unsigned int cardMin = 0,
00819            unsigned int cardMax = Limits::Set::card_max);
00837     void init(Space* home,int glbMin,int glbMax,int lubMin,int lubMax,
00838               unsigned int cardMin = 0,
00839               unsigned int cardMax = Limits::Set::card_max);
00840 
00858     GECODE_SET_EXPORT 
00859     SetVar(Space* home,const IntSet& glbD,int lubMin,int lubMax,
00860            unsigned int cardMin = 0,
00861            unsigned int cardMax = Limits::Set::card_max);
00879     void init(Space* home,const IntSet& glbD,int lubMin,int lubMax,
00880               unsigned int cardMin = 0,
00881               unsigned int cardMax = Limits::Set::card_max);
00882 
00900     GECODE_SET_EXPORT 
00901     SetVar(Space* home,int glbMin,int glbMax,const IntSet& lubD,
00902            unsigned int cardMin = 0,
00903            unsigned int cardMax = Limits::Set::card_max);
00921     void init(Space* home,int glbMin,int glbMax,const IntSet& lubD,
00922               unsigned int cardMin = 0,
00923               unsigned int cardMax = Limits::Set::card_max);
00924 
00942     GECODE_SET_EXPORT 
00943     SetVar(Space* home,const IntSet& glbD,const IntSet& lubD,
00944            unsigned int cardMin = 0,
00945            unsigned int cardMax = Limits::Set::card_max);
00963     void init(Space* home,const IntSet& glbD,const IntSet& lubD,
00964               unsigned int cardMin = 0,
00965               unsigned int cardMax = Limits::Set::card_max);
00967 
00969 
00970 
00971     Set::SetVarImp* variable(void) const;
00973     
00975 
00976 
00977     unsigned int glbSize(void) const;
00979     unsigned int lubSize(void) const;
00981     unsigned int unknownSize(void) const;
00983     unsigned int cardMin(void) const;
00985     unsigned int cardMax(void) const;
00987     int lubMin(void) const;
00989     int lubMax(void) const;
00991     int glbMin(void) const;
00993     int glbMax(void) const;
00995 
00997 
00998 
00999     bool contains(int i) const;
01001     bool notContains(int i) const;
01003     bool assigned(void) const;
01004 
01006 
01007 
01008     void update(Space* home, bool, SetVar& x);
01010   };
01011 
01017 
01019   class SetVarGlbRanges {
01020   private:
01021     Set::GlbRanges<Set::SetVarImp*> iter;
01022   public:
01024 
01025 
01026     SetVarGlbRanges(void);
01028     SetVarGlbRanges(const SetVar& x);
01030 
01032 
01033 
01034     bool operator()(void) const;
01036     void operator++(void);
01038 
01040 
01041 
01042     int min(void) const;
01044     int max(void) const;
01046     unsigned int width(void) const;
01048   };
01049 
01051   class SetVarLubRanges {
01052   private:
01053     Set::LubRanges<Set::SetVarImp*> iter;
01054   public:
01056 
01057 
01058     SetVarLubRanges(void);
01060     SetVarLubRanges(const SetVar& x);
01062 
01064 
01065 
01066     bool operator()(void) const;
01068     void operator++(void);
01070 
01072 
01073 
01074     int min(void) const;
01076     int max(void) const;
01078     unsigned int width(void) const;
01080   };
01081 
01083   class SetVarUnknownRanges {
01084   private:
01085     Set::UnknownRanges<Set::SetVarImp*> iter;
01086   public:
01088 
01089 
01090     SetVarUnknownRanges(void);
01092     SetVarUnknownRanges(const SetVar& x);
01094 
01096 
01097 
01098     bool operator()(void) const;
01100     void operator++(void);
01102 
01104 
01105 
01106     int min(void) const;
01108     int max(void) const;
01110     unsigned int width(void) const;
01112   };
01113   
01115   class SetVarGlbValues {
01116   private:
01117     Iter::Ranges::ToValues<SetVarGlbRanges> iter;
01118   public:
01120 
01121 
01122     SetVarGlbValues(void);
01124     SetVarGlbValues(const SetVar& x);
01126 
01128 
01129 
01130     bool operator()(void) const;
01132     void operator++(void);
01134 
01136 
01137 
01138     int  val(void) const;
01140   };
01141 
01143   class SetVarLubValues {
01144   private:
01145     Iter::Ranges::ToValues<SetVarLubRanges> iter;
01146   public:
01148 
01149 
01150     SetVarLubValues(void);
01152     SetVarLubValues(const SetVar& x);
01154 
01156 
01157 
01158     bool operator()(void) const;
01160     void operator++(void);
01162 
01164 
01165 
01166     int  val(void) const;
01168   };
01169 
01171   class SetVarUnknownValues {
01172   private:
01173     Iter::Ranges::ToValues<SetVarUnknownRanges> iter;
01174   public:
01176 
01177 
01178     SetVarUnknownValues(void);
01180     SetVarUnknownValues(const SetVar& x);
01182 
01184 
01185 
01186     bool operator()(void) const;
01188     void operator++(void);
01190 
01192 
01193 
01194     int  val(void) const;
01196   };
01197 
01199 }
01200 
01201 #include "gecode/set/var/set.icc"
01202 
01207 GECODE_SET_EXPORT std::ostream&
01208 operator<<(std::ostream&, const Gecode::SetVar& x);
01209 
01210 // STATISTICS: set-var
01211