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