Generated on Mon Nov 30 23:53:24 2009 for Gecode by doxygen 1.6.1

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: 2009-10-05 15:07:24 +0200 (Mon, 05 Oct 2009) $ by $Author: zayenz $
00016  *  $Revision: 9821 $
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 DerivedViewBase<IntView> {
00142   protected:
00143     using DerivedViewBase<IntView>::view;
00145     int _card;
00147     int _counter;
00148   public:
00150     static const bool propagate = true;
00152 
00153 
00154     CardView(void);
00156     void init(const IntView& x, 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     bool assigned(void) const;
00180 
00184     void counter(int n);
00186     ModEvent inc(void);
00188     ModEvent lq(Space& home, int n);
00190     ModEvent gq(Space& home, int n);
00192     ModEvent eq(Space& home, int n);
00194 
00196 
00197 
00198     template<class I>
00199     ModEvent narrow_v(Space& home, I& i, bool depends=true);
00201     template<class I>
00202     ModEvent inter_v(Space& home, I& i, bool depends=true);
00204     template<class I>
00205     ModEvent minus_v(Space& home, I& i, bool depends=true);
00207 
00211     void subscribe(Space& home, Propagator& p, PropCond pc, bool process=true);
00213     void cancel(Space& home, Propagator& p, PropCond pc);
00215 
00219     void update(Space& home, bool share, CardView& x);
00221   };
00222 
00223 
00224 
00225   /*
00226    * Constant cardinality view
00227    *
00228    */
00229   forceinline
00230   CardConst::CardConst(void) {}
00231   forceinline void
00232   CardConst::init(Space&, int min, int max, int c) {
00233     _min = min; _max=max; _card = c; _counter = 0;
00234   }
00235 
00236   forceinline int
00237   CardConst::min(void) const {
00238     return _min;
00239   }
00240   forceinline int
00241   CardConst::max(void) const {
00242     return _max;
00243   }
00244   forceinline int
00245   CardConst::card(void) const {
00246     return _card;
00247   }
00248   forceinline int
00249   CardConst::counter(void) const {
00250     return _counter;
00251   }
00252   forceinline bool
00253   CardConst::assigned(void) const {
00254     return _min==_max;
00255   }
00256 
00257 
00258   forceinline void
00259   CardConst::counter(int n) {
00260     _counter = n;
00261   }
00262   forceinline ModEvent
00263   CardConst::inc(void) {
00264     if (++_counter > _max)
00265       return ME_INT_FAILED;
00266     return ME_INT_NONE;
00267   }
00268   forceinline ModEvent
00269   CardConst::lq(Space&, int n) {
00270     if (_min > n)
00271       return ME_INT_FAILED;
00272     return ME_INT_NONE;
00273   }
00274   forceinline ModEvent
00275   CardConst::gq(Space&, int n) {
00276     if (_max < n)
00277       return ME_INT_FAILED;
00278     return ME_INT_NONE;
00279   }
00280   forceinline ModEvent
00281   CardConst::eq(Space&, int n) {
00282     if ((_min > n) || (_max < n))
00283       return ME_INT_FAILED;
00284     return ME_INT_NONE;
00285   }
00286 
00287   forceinline void
00288   CardConst::subscribe(Space&, Propagator&, PropCond, bool) {}
00289   forceinline void
00290   CardConst::cancel(Space&, Propagator&, PropCond) {}
00291 
00292   forceinline void
00293   CardConst::update(Space&, bool, CardConst& x) {
00294     _min=x._min; _max=x._max; _card=x._card; _counter=x._counter;
00295   }
00296 
00297   forceinline IntView
00298   CardConst::base(void) const {
00299     GECODE_NEVER;
00300     return IntView();
00301   }
00302 
00303 
00304 
00305   /*
00306    * Cardinality integer view
00307    *
00308    */
00309   forceinline
00310   CardView::CardView(void) {}
00311   forceinline void
00312   CardView::init(const IntView& x, int c) {
00313     view = x; _card = c; _counter = 0;
00314   }
00315   forceinline void
00316   CardView::init(Space& home, const IntSet& s, int c) {
00317     IntVar x(home,s);
00318     view = x; _card = c;  _counter = 0;
00319   }
00320 
00321   forceinline int
00322   CardView::counter(void) const {
00323     return _counter;
00324   }
00325   forceinline int
00326   CardView::card(void) const {
00327     return _card;
00328   }
00329   forceinline int
00330   CardView::min(void) const {
00331     return view.min();
00332   }
00333   forceinline int
00334   CardView::max(void) const {
00335     return view.max();
00336   }
00337   forceinline unsigned int
00338   CardView::size(void) const {
00339     return view.size();
00340   }
00341 
00342   forceinline bool
00343   CardView::assigned(void) const {
00344     return view.assigned();
00345   }
00346 
00347   forceinline void
00348   CardView::counter(int n) {
00349     _counter = n;
00350   }
00351   forceinline ModEvent
00352   CardView::inc(void) {
00353     if (++_counter > this->max())
00354       return ME_INT_FAILED;
00355     return ME_GEN_NONE;
00356   }
00357   forceinline ModEvent
00358   CardView::lq(Space& home, int n) {
00359     return view.lq(home,n);
00360   }
00361   forceinline ModEvent
00362   CardView::gq(Space& home, int n) {
00363     return view.gq(home,n);
00364   }
00365   forceinline ModEvent
00366   CardView::eq(Space& home, int n) {
00367     return view.eq(home,n);
00368   }
00369 
00370   template<class I>
00371   forceinline ModEvent
00372   CardView::narrow_v(Space& home, I& i, bool depends) {
00373     return view.narrow_v(home,i,depends);
00374   }
00375   template<class I>
00376   forceinline ModEvent
00377   CardView::inter_v(Space& home, I& i, bool depends) {
00378     return view.inter_v(home,i,depends);
00379   }
00380   template<class I>
00381   forceinline ModEvent
00382   CardView::minus_v(Space& home, I& i, bool depends) {
00383     return view.minus_v(home,i,depends);
00384   }
00385 
00386   forceinline void
00387   CardView::subscribe(Space& home, Propagator& p, PropCond pc, bool process) {
00388     view.subscribe(home, p, pc, process);
00389   }
00390   forceinline void
00391   CardView::cancel(Space& home, Propagator& p, PropCond pc) {
00392     view.cancel(home,p, pc);
00393   }
00394 
00395   forceinline void
00396   CardView::update(Space& home, bool share, CardView& x) {
00397     view.update(home,share,x.view);
00398     _card = x._card; _counter = x._counter;
00399   }
00400 
00401 }
00402 
00403 
00407   template<>
00408   class ViewRanges<GCC::CardView>
00409     : public Gecode::Int::ViewRanges<IntView> {
00410   public:
00414     ViewRanges(void);
00416     ViewRanges(const GCC::CardView& x);
00418     void init(const GCC::CardView& x);
00420   };
00421 
00422   forceinline
00423   ViewRanges<GCC::CardView>::ViewRanges(void) :
00424     Gecode::Int::ViewRanges<IntView>()  {}
00425 
00426   forceinline
00427   ViewRanges<GCC::CardView>::ViewRanges (const GCC::CardView& x)
00428     : Gecode::Int::ViewRanges<IntView>(x.base())  {}
00429 
00430   forceinline void
00431   ViewRanges<GCC::CardView>::init(const GCC::CardView& x) {
00432     Gecode::Int::ViewRanges<IntView> xi(x.base());
00433   }
00434 
00435 }}
00436 
00437 
00438 
00439 // STATISTICS: int-prop