Generated on Thu Mar 22 10:39:37 2012 for Gecode by doxygen 1.6.3

view.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
00005  *
00006  *  Contributing authors:
00007  *     Christian Schulte <schulte@gecode.org>
00008  *     Guido Tack <tack@gecode.org>
00009  *
00010  *  Copyright:
00011  *     Patrick Pekczynski, 2004
00012  *     Christian Schulte, 2009
00013  *     Guido Tack, 2009
00014  *
00015  *  Last modified: $Date: 2010-06-29 10:39:13 +0200 (Tue, 29 Jun 2010) $ by $Author: schulte $
00016  *  $Revision: 11118 $
00017  *
00018  *  This file is part of Gecode, the generic constrain
00019  *  development environment:
00020  *     http://www.gecode.org
00021  *
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 namespace Gecode { namespace Int { namespace GCC {
00044 
00046   template<class T>
00047   forceinline bool
00048   lookupValue(T& a, int v, int& i) {
00049     int l = 0;
00050     int r = a.size() - 1;
00051 
00052     while (l <= r) {
00053       int m = l + (r - l) / 2;
00054       if (v == a[m].card()) {
00055         i=m; return true;
00056       } else if (l == r) {
00057         return false;
00058       } else if (v < a[m].card()) {
00059         r=m-1;
00060       } else {
00061         l=m+1;
00062       }
00063     }
00064     return false;
00065   }
00066 
00068   class CardConst {
00069   private:
00071     int _min;
00073     int _max;
00075     int _card;
00077     int _counter;
00078   public:
00080     static const bool propagate = false;
00081 
00083 
00084 
00085     CardConst(void);
00087     void init(Space& home, int min, int max, int c);
00089 
00091 
00092 
00093     int min(void) const;
00095     int max(void) const;
00097     int card(void) const;
00099     int counter(void) const;
00101 
00105     bool assigned(void) const;
00107 
00111     void counter(int n);
00113     ModEvent inc(void);
00115     ModEvent lq(Space& home, int n);
00117     ModEvent gq(Space& home, int n);
00119     ModEvent eq(Space& home, int n);
00121 
00125     void subscribe(Space& home, Propagator& p, PropCond pc, bool process=true);
00127     void cancel(Space& home, Propagator& p, PropCond pc);
00129 
00133     void update(Space& home, bool share, CardConst& x);
00135 
00137     IntView base(void) const;
00138   };
00139 
00141   class CardView : public DerivedView<IntView> {
00142   protected:
00143     using DerivedView<IntView>::x;
00145     int _card;
00147     int _counter;
00148   public:
00150     static const bool propagate = true;
00152 
00153 
00154     CardView(void);
00156     void init(const IntView& y, int c);
00158     void init(Space& home, const IntSet& s, int c);
00160 
00162 
00163 
00164     int min(void) const;
00166     int max(void) const;
00168     unsigned int size(void) const;
00170     int counter(void) const;
00172     int card(void) const;
00174 
00178     void counter(int n);
00180     ModEvent inc(void);
00182     ModEvent lq(Space& home, int n);
00184     ModEvent gq(Space& home, int n);
00186     ModEvent eq(Space& home, int n);
00188 
00190 
00191 
00192     template<class I>
00193     ModEvent narrow_v(Space& home, I& i, bool depends=true);
00195     template<class I>
00196     ModEvent inter_v(Space& home, I& i, bool depends=true);
00198     template<class I>
00199     ModEvent minus_v(Space& home, I& i, bool depends=true);
00201 
00205     void update(Space& home, bool share, CardView& x);
00207   };
00208 
00209 
00210 
00211   /*
00212    * Constant cardinality view
00213    *
00214    */
00215   forceinline
00216   CardConst::CardConst(void) {}
00217   forceinline void
00218   CardConst::init(Space&, int min, int max, int c) {
00219     _min = min; _max=max; _card = c; _counter = 0;
00220   }
00221 
00222   forceinline int
00223   CardConst::min(void) const {
00224     return _min;
00225   }
00226   forceinline int
00227   CardConst::max(void) const {
00228     return _max;
00229   }
00230   forceinline int
00231   CardConst::card(void) const {
00232     return _card;
00233   }
00234   forceinline int
00235   CardConst::counter(void) const {
00236     return _counter;
00237   }
00238   forceinline bool
00239   CardConst::assigned(void) const {
00240     return _min==_max;
00241   }
00242 
00243 
00244   forceinline void
00245   CardConst::counter(int n) {
00246     _counter = n;
00247   }
00248   forceinline ModEvent
00249   CardConst::inc(void) {
00250     if (++_counter > _max)
00251       return ME_INT_FAILED;
00252     return ME_INT_NONE;
00253   }
00254   forceinline ModEvent
00255   CardConst::lq(Space&, int n) {
00256     if (_min > n)
00257       return ME_INT_FAILED;
00258     return ME_INT_NONE;
00259   }
00260   forceinline ModEvent
00261   CardConst::gq(Space&, int n) {
00262     if (_max < n)
00263       return ME_INT_FAILED;
00264     return ME_INT_NONE;
00265   }
00266   forceinline ModEvent
00267   CardConst::eq(Space&, int n) {
00268     if ((_min > n) || (_max < n))
00269       return ME_INT_FAILED;
00270     return ME_INT_NONE;
00271   }
00272 
00273   forceinline void
00274   CardConst::subscribe(Space&, Propagator&, PropCond, bool) {}
00275   forceinline void
00276   CardConst::cancel(Space&, Propagator&, PropCond) {}
00277 
00278   forceinline void
00279   CardConst::update(Space&, bool, CardConst& x) {
00280     _min=x._min; _max=x._max; _card=x._card; _counter=x._counter;
00281   }
00282 
00283   forceinline IntView
00284   CardConst::base(void) const {
00285     GECODE_NEVER;
00286     return IntView();
00287   }
00288 
00289 
00290 
00291   /*
00292    * Cardinality integer view
00293    *
00294    */
00295   forceinline
00296   CardView::CardView(void) {}
00297   forceinline void
00298   CardView::init(const IntView& y, int c) {
00299     x = y; _card = c; _counter = 0;
00300   }
00301   forceinline void
00302   CardView::init(Space& home, const IntSet& s, int c) {
00303     x = IntVar(home,s); _card = c; _counter = 0;
00304   }
00305 
00306   forceinline int
00307   CardView::counter(void) const {
00308     return _counter;
00309   }
00310   forceinline int
00311   CardView::card(void) const {
00312     return _card;
00313   }
00314   forceinline int
00315   CardView::min(void) const {
00316     return x.min();
00317   }
00318   forceinline int
00319   CardView::max(void) const {
00320     return x.max();
00321   }
00322   forceinline unsigned int
00323   CardView::size(void) const {
00324     return x.size();
00325   }
00326 
00327   forceinline void
00328   CardView::counter(int n) {
00329     _counter = n;
00330   }
00331   forceinline ModEvent
00332   CardView::inc(void) {
00333     if (++_counter > this->max())
00334       return ME_INT_FAILED;
00335     return ME_GEN_NONE;
00336   }
00337   forceinline ModEvent
00338   CardView::lq(Space& home, int n) {
00339     return x.lq(home,n);
00340   }
00341   forceinline ModEvent
00342   CardView::gq(Space& home, int n) {
00343     return x.gq(home,n);
00344   }
00345   forceinline ModEvent
00346   CardView::eq(Space& home, int n) {
00347     return x.eq(home,n);
00348   }
00349 
00350   template<class I>
00351   forceinline ModEvent
00352   CardView::narrow_v(Space& home, I& i, bool depends) {
00353     return x.narrow_v(home,i,depends);
00354   }
00355   template<class I>
00356   forceinline ModEvent
00357   CardView::inter_v(Space& home, I& i, bool depends) {
00358     return x.inter_v(home,i,depends);
00359   }
00360   template<class I>
00361   forceinline ModEvent
00362   CardView::minus_v(Space& home, I& i, bool depends) {
00363     return x.minus_v(home,i,depends);
00364   }
00365 
00366   forceinline void
00367   CardView::update(Space& home, bool share, CardView& y) {
00368     x.update(home,share,y.x);
00369     _card = y._card; _counter = y._counter;
00370   }
00371 
00372 }
00373 
00374 
00378   template<>
00379   class ViewRanges<GCC::CardView>
00380     : public Gecode::Int::ViewRanges<IntView> {
00381   public:
00385     ViewRanges(void);
00387     ViewRanges(const GCC::CardView& x);
00389     void init(const GCC::CardView& x);
00391   };
00392 
00393   forceinline
00394   ViewRanges<GCC::CardView>::ViewRanges(void) :
00395     Gecode::Int::ViewRanges<IntView>()  {}
00396 
00397   forceinline
00398   ViewRanges<GCC::CardView>::ViewRanges (const GCC::CardView& x)
00399     : Gecode::Int::ViewRanges<IntView>(x.base())  {}
00400 
00401   forceinline void
00402   ViewRanges<GCC::CardView>::init(const GCC::CardView& x) {
00403     Gecode::Int::ViewRanges<IntView> xi(x.base());
00404   }
00405 
00406 }}
00407 
00408 
00409 
00410 // STATISTICS: int-prop