Generated on Fri May 13 2011 22:41:19 for Gecode by doxygen 1.7.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  *     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