Generated on Thu Apr 11 13:59:01 2019 for Gecode by doxygen 1.6.3

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  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 #include <iostream>
00041 
00042 namespace Gecode { namespace Set {
00043 
00044   class SetVarImp;
00045   class LUBndSet;
00046   class GLBndSet;
00047 
00052   class SetDelta : public Delta {
00053     friend class SetVarImp;
00054     friend class LUBndSet;
00055     friend class GLBndSet;
00056   private:
00057     int _glbMin; 
00058     int _glbMax; 
00059     int _lubMin; 
00060     int _lubMax; 
00061   public:
00063     SetDelta(void);
00065     SetDelta(int glbMin, int glbMax, int lubMin, int lubMax);
00067     int glbMin(void) const;
00069     int glbMax(void) const;
00071     int lubMin(void) const;
00073     int lubMax(void) const;
00075     bool glbAny(void) const;
00077     bool lubAny(void) const;
00078   };
00079 
00080 }}
00081 
00082 #include <gecode/set/var-imp/delta.hpp>
00083 
00084 namespace Gecode { namespace Set {
00085 
00089   class BndSet  {
00090   private:
00091     RangeList* first;
00092     RangeList* last;
00093   protected:
00095     unsigned int _size;
00097     unsigned int _card;
00099     void fst(RangeList* r);
00101     void lst(RangeList* r);
00102 
00104     RangeList* fst(void) const;
00106     RangeList* lst(void) const;
00107 
00108   public:
00110     static const int MAX_OF_EMPTY = Limits::min-1;
00112     static const int MIN_OF_EMPTY = Limits::max+1;
00113 
00115 
00116 
00117     BndSet(void);
00119     BndSet(Space& home, int i, int j);
00121     GECODE_SET_EXPORT BndSet(Space& home, const IntSet& s);
00123 
00125 
00126 
00127     void dispose(Space& home);
00129 
00131 
00132 
00133     int min(void) const;
00135     int max(void) const;
00137     int minN(unsigned int n) const;
00139     unsigned int size(void) const;
00141     unsigned int card(void) const;
00143     void card(unsigned int c);
00145 
00147 
00148 
00149     bool empty(void) const;
00151     bool in(int i) const;
00153 
00155 
00156 
00157     void become(Space& home, const BndSet& s);
00159 
00161 
00162 
00163     RangeList* ranges(void) const;
00165 
00166   protected:
00168     template<class I> bool overwrite(Space& home,I& i);
00169 
00170   public:
00172 
00173 
00174     void update(Space& home, BndSet& x);
00176 
00178     GECODE_SET_EXPORT bool isConsistent(void) const;
00179   };
00180 
00185   class BndSetRanges : public Iter::Ranges::RangeList {
00186   public:
00188 
00189 
00190     BndSetRanges(void);
00192     BndSetRanges(const BndSet& s);
00194     void init(const BndSet& s);
00196   };
00197 
00205   class GLBndSet : public BndSet {
00206   private:
00208     GECODE_SET_EXPORT bool include_full(Space& home,int,int,SetDelta&);
00209   public:
00211 
00212 
00213     GLBndSet(void);
00215     GLBndSet(Space&);
00217     GLBndSet(Space& home, int i, int j);
00219     GLBndSet(Space& home, const IntSet& s);
00221     void init(Space& home);
00223 
00225 
00226 
00227     bool include(Space& home,int i,int j,SetDelta& d);
00229     template<class I> bool includeI(Space& home,I& i);
00231   private:
00232     GLBndSet(const GLBndSet&);
00233     const GLBndSet& operator =(const GLBndSet&);
00234   };
00235 
00243   class LUBndSet: public BndSet{
00244   private:
00245     GECODE_SET_EXPORT bool exclude_full(Space& home, int, int, SetDelta&);
00246     GECODE_SET_EXPORT bool intersect_full(Space& home, int i, int j);
00247   public:
00249 
00250 
00251     LUBndSet(void);
00253     LUBndSet(Space& home);
00255     LUBndSet(Space& home, int i, int j);
00257     LUBndSet(Space& home, const IntSet& s);
00259     void init(Space& home);
00261 
00263 
00264 
00265     bool exclude(Space& home, int i, int j, SetDelta& d);
00267     bool intersect(Space& home, int i, int j);
00269     template<class I> bool intersectI(Space& home, I& i);
00271     template<class I> bool excludeI(Space& home, I& i);
00273     void excludeAll(Space& home);
00275   private:
00276     LUBndSet(const LUBndSet&);
00277     const LUBndSet& operator =(const LUBndSet&);
00278   };
00279 
00280   /*
00281    * Iterators
00282    *
00283    */
00284 
00285 
00291   template<class I>
00292   class RangesCompl :
00293     public Iter::Ranges::Compl<Limits::min, Limits::max, I> {
00294   public:
00296 
00297 
00298     RangesCompl(void);
00300     RangesCompl(I& i);
00302     void init(I& i);
00304   };
00305 
00317   template<class T> class LubRanges {
00318   public:
00320 
00321 
00322     LubRanges(void);
00324     LubRanges(const T& x);
00326     void init(const T& x);
00328 
00330 
00331 
00332     bool operator ()(void) const;
00334     void operator ++(void);
00336 
00338 
00339 
00340     int min(void) const;
00342     int max(void) const;
00344     unsigned int width(void) const;
00346   };
00347 
00359   template<class T> class GlbRanges {
00360   public:
00362 
00363 
00364     GlbRanges(void);
00366     GlbRanges(const T& x);
00368     void init(const T& x);
00370 
00372 
00373 
00374     bool operator ()(void) const;
00376     void operator ++(void);
00378 
00380 
00381 
00382     int min(void) const;
00384     int max(void) const;
00386     unsigned int width(void) const;
00388   };
00389 
00401   template<class T>
00402   class UnknownRanges : public Iter::Ranges::Diff<LubRanges<T>, GlbRanges<T> >{
00403   private:
00404     LubRanges<T> i1;
00405     GlbRanges<T> i2;
00406   public:
00408 
00409 
00410     UnknownRanges(void);
00412     UnknownRanges(const T& x);
00414     void init(const T& x);
00416   };
00417 
00418 }}
00419 
00420 #include <gecode/set/var-imp/integerset.hpp>
00421 #include <gecode/set/var-imp/iter.hpp>
00422 
00423 namespace Gecode { namespace Set {
00424 
00430   class SetVarImp : public SetVarImpBase {
00431     friend class LubRanges<SetVarImp*>;
00432     friend class GlbRanges<SetVarImp*>;
00433   private:
00435     LUBndSet lub;
00437     GLBndSet glb;
00438 
00439   protected:
00441     SetVarImp(Space& home, SetVarImp& x);
00442   public:
00444 
00445 
00446     SetVarImp(Space& home);
00455     SetVarImp(Space& home,int glbMin,int glbMax,int lubMin,int lubMax,
00456                unsigned int cardMin = 0,
00457                unsigned int cardMax = Limits::card);
00466     SetVarImp(Space& home,const IntSet& glbD,int lubMin,int lubMax,
00467               unsigned int cardMin,unsigned int cardMax);
00476     SetVarImp(Space& home,int glbMin,int glbMax,const IntSet& lubD,
00477               unsigned int cardMin,unsigned int cardMax);
00486     SetVarImp(Space& home,const IntSet& glbD,const IntSet& lubD,
00487               unsigned int cardMin,unsigned int cardMax);
00489 
00491 
00492 
00493     unsigned int cardMin(void) const;
00495     unsigned int cardMax(void) const;
00497     int lubMin(void) const;
00499     int lubMax(void) const;
00501     int lubMinN(unsigned int n) const;
00503     int glbMin(void) const;
00505     int glbMax(void) const;
00507     unsigned int glbSize(void) const;
00509     unsigned int lubSize(void) const;
00511 
00513 
00514 
00515     bool assigned(void) const;
00517     bool knownIn(int n) const;
00519     bool knownOut(int) const;
00521 
00522   private:
00524 
00525 
00526     template<class I> ModEvent includeI_full(Space& home,int mi, int ma, I& i);
00528     template<class I> ModEvent excludeI_full(Space& home,int mi, int ma, I& i);
00530     template<class I> ModEvent intersectI_full(Space& home,int mi, int ma, I& i);
00532 
00533     GECODE_SET_EXPORT ModEvent processLubChange(Space& home, SetDelta& d);
00534     GECODE_SET_EXPORT ModEvent processGlbChange(Space& home, SetDelta& d);
00535 
00537 
00538 
00539     GECODE_SET_EXPORT ModEvent cardMin_full(Space& home);
00541     GECODE_SET_EXPORT ModEvent cardMax_full(Space& home);
00543 
00544   public:
00545 
00547 
00548 
00549     ModEvent include(Space& home,int n);
00551     ModEvent include(Space& home,int i,int j);
00553     ModEvent exclude(Space& home,int n);
00555     ModEvent exclude(Space& home,int i,int j);
00557     ModEvent intersect(Space& home,int n);
00559     ModEvent intersect(Space& home,int i,int j);
00561     ModEvent cardMin(Space& home,unsigned int n);
00563     ModEvent cardMax(Space& home,unsigned int n);
00565 
00567 
00568 
00569     template<class I> ModEvent includeI(Space& home,I& i);
00571     template<class I> ModEvent excludeI(Space& home,I& i);
00573     template<class I> ModEvent intersectI(Space& home,I& i);
00575 
00576   public:
00578 
00579 
00586     GECODE_SET_EXPORT void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
00588     GECODE_SET_EXPORT void reschedule(Space& home, Propagator& p, PropCond pc);
00597     GECODE_SET_EXPORT void subscribe(Space& home, Advisor& a, bool fail);
00599 
00600   private:
00602     GECODE_SET_EXPORT SetVarImp* perform_copy(Space& home);
00603 
00604   public:
00606 
00607 
00608     SetVarImp* copy(Space& home);
00610 
00612 
00613 
00614     static int glbMin(const Delta& d);
00616     static int glbMax(const Delta& d);
00618     static bool glbAny(const Delta& d);
00620     static int lubMin(const Delta& d);
00622     static int lubMax(const Delta& d);
00624     static bool lubAny(const Delta& d);
00626 
00627   };
00628 
00629   class SetView;
00630 
00631 }}
00632 
00633 #include <gecode/set/var-imp/set.hpp>
00634 
00635 // STATISTICS: set-var