Generated on Tue Jul 27 2010 21:59:19 for Gecode by doxygen 1.7.1

const.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  *  Copyright:
00007  *     Guido Tack, 2004
00008  *
00009  *  Last modified:
00010  *     $Date: 2010-06-29 10:39:13 +0200 (Tue, 29 Jun 2010) $ by $Author: schulte $
00011  *     $Revision: 11118 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 namespace Gecode { namespace Set {
00039 
00044   class ArrayRanges {
00045   private:
00046     int *_ranges;
00047     int _size;
00048     int _pos;
00049   public:
00051 
00052 
00053     ArrayRanges(void) : _ranges(NULL), _size(0), _pos(0) {}
00055     ArrayRanges(int *ranges, int size)
00056       : _ranges(ranges), _size(size), _pos(0) {}
00058     void init(int* ranges, int size) {
00059       _ranges = ranges; _size = size; _pos = 0;
00060     }
00062 
00064 
00065 
00066     bool operator ()(void) const { return _pos<_size; }
00068     void operator ++(void) { _pos++; }
00070 
00072 
00073 
00074     int min(void) const { return _ranges[_pos*2]; }
00076     int max(void) const { return _ranges[_pos*2+1]; }
00078     unsigned int width(void) const {
00079       return static_cast<unsigned int>(_ranges[_pos*2+1]-_ranges[_pos*2]+1);
00080     }
00082   };
00083 
00084   forceinline
00085   ConstSetView::ConstSetView(void) : ranges(NULL), size(0), domSize(0) {}
00086 
00087   forceinline
00088   ConstSetView::ConstSetView(Space& home, const IntSet& dom) {
00089     size = dom.ranges();
00090     domSize = 0;
00091     if (size > 0) {
00092       ranges = home.alloc<int>(2*size);
00093       IntSetRanges dr(dom);
00094       for (int i=0; dr(); ++dr, i+=2) {
00095         int min = dr.min(); int max = dr.max();
00096         ranges[i] = min;
00097         ranges[i+1] = max;
00098         domSize += static_cast<unsigned int>(max-min+1);
00099       }
00100     } else {
00101       ranges = NULL;
00102     }
00103   }
00104 
00105   forceinline unsigned int
00106   ConstSetView::glbSize(void) const { return domSize; }
00107 
00108   forceinline unsigned int
00109   ConstSetView::lubSize(void) const { return domSize; }
00110 
00111   forceinline unsigned int
00112   ConstSetView::unknownSize(void) const { return 0; }
00113 
00114   forceinline bool
00115   ConstSetView::contains(int i) const {
00116     for (int j=size; j--; ) {
00117       if (ranges[2*j+1] < i)
00118         return false;
00119       if (ranges[2*j] >= i)
00120         return true;
00121     }
00122     return false;
00123   }
00124 
00125   forceinline bool
00126   ConstSetView::notContains(int i) const {
00127     return !contains(i);
00128   }
00129 
00130   forceinline unsigned int
00131   ConstSetView::cardMin(void) const { return domSize; }
00132 
00133   forceinline unsigned int
00134   ConstSetView::cardMax(void) const { return domSize; }
00135 
00136   forceinline int
00137   ConstSetView::lubMin(void) const {
00138     return size==0 ? BndSet::MIN_OF_EMPTY : ranges[0];
00139   }
00140 
00141   forceinline int
00142   ConstSetView::lubMax(void) const {
00143     return size==0 ? BndSet::MAX_OF_EMPTY : ranges[size*2-1];
00144   }
00145 
00146   forceinline int
00147   ConstSetView::glbMin(void) const { return lubMin(); }
00148 
00149   forceinline int
00150   ConstSetView::glbMax(void) const { return lubMax(); }
00151 
00152   forceinline ModEvent
00153   ConstSetView::cardMin(Space&,unsigned int c) {
00154     return c<=domSize ? ME_SET_NONE : ME_SET_FAILED;
00155   }
00156 
00157   forceinline ModEvent
00158   ConstSetView::cardMax(Space&,unsigned int c) {
00159     return c>=domSize ? ME_SET_NONE : ME_SET_FAILED;
00160   }
00161 
00162   forceinline ModEvent
00163   ConstSetView::include(Space&,int c) {
00164     return contains(c) ? ME_SET_NONE : ME_SET_FAILED;
00165   }
00166 
00167   forceinline ModEvent
00168   ConstSetView::exclude(Space&,int c) {
00169     return contains(c) ? ME_SET_FAILED : ME_SET_NONE;
00170   }
00171 
00172   forceinline ModEvent
00173   ConstSetView::intersect(Space&,int c) {
00174     return (size==0 ||
00175             (size==1 &&
00176              ranges[0]==ranges[1] && ranges[0]==c)) ?
00177       ME_SET_NONE : ME_SET_FAILED;
00178   }
00179 
00180   forceinline ModEvent
00181   ConstSetView::intersect(Space&,int i,int j) {
00182     return (glbMin()>=i && glbMax()<=j) ?
00183       ME_SET_NONE : ME_SET_FAILED;
00184   }
00185 
00186   forceinline ModEvent
00187   ConstSetView::include(Space&,int i,int j) {
00188     Iter::Ranges::Singleton single(i,j);
00189     ArrayRanges ar(ranges, size);
00190     return (single() && Iter::Ranges::subset(single, ar)) ?
00191       ME_SET_NONE : ME_SET_FAILED;
00192   }
00193 
00194   forceinline ModEvent
00195   ConstSetView::exclude(Space&,int i,int j) {
00196     Iter::Ranges::Singleton single(i,j);
00197     ArrayRanges ar(ranges, size);
00198     return (single() && Iter::Ranges::subset(single, ar)) ?
00199       ME_SET_FAILED : ME_SET_NONE;
00200   }
00201 
00202   template<class I> ModEvent
00203   ConstSetView::excludeI(Space&,I& i) {
00204     Iter::Ranges::IsRangeIter<I>();
00205     ArrayRanges ar(ranges, size);
00206     return (i() && Iter::Ranges::subset(i, ar)) ? ME_SET_FAILED : ME_SET_NONE;
00207   }
00208 
00209   template<class I> ModEvent
00210   ConstSetView::includeI(Space&,I& i) {
00211     Iter::Ranges::IsRangeIter<I>();
00212     ArrayRanges ar(ranges, size);
00213     return Iter::Ranges::subset(i, ar) ? ME_SET_NONE : ME_SET_FAILED;
00214   }
00215 
00216   template<class I> ModEvent
00217   ConstSetView::intersectI(Space&,I& i) {
00218     Iter::Ranges::IsRangeIter<I>();
00219     ArrayRanges ar(ranges, size);
00220     return Iter::Ranges::subset(ar, i) ? ME_SET_NONE : ME_SET_FAILED;
00221   }
00222 
00223   forceinline void
00224   ConstSetView::update(Space& home, bool share, ConstSetView& p) {
00225     ConstView<SetView>::update(home,share,p);
00226     // dispose old ranges
00227     if (size > 0)
00228       home.free<int>(ranges, 2);
00229 
00230     domSize = p.domSize;
00231     size = p.size;
00232     if (size == 0) {
00233       ranges = NULL;
00234     } else {
00235       // copy ranges from p
00236       ranges = home.alloc<int>(2*size);
00237       for (int i=size; i--; ) {
00238         ranges[2*i]   = p.ranges[2*i];
00239         ranges[2*i+1] = p.ranges[2*i+1];
00240       }
00241     }
00242   }
00243 
00244 
00245   /*
00246    * Delta information for advisors
00247    *
00248    */
00249   forceinline int
00250   ConstSetView::glbMin(const Delta&) const {
00251     GECODE_NEVER;
00252     return 0;
00253   }
00254   forceinline int
00255   ConstSetView::glbMax(const Delta&) const {
00256     GECODE_NEVER;
00257     return 0;
00258   }
00259   forceinline bool
00260   ConstSetView::glbAny(const Delta&) const {
00261     GECODE_NEVER;
00262     return false;
00263   }
00264   forceinline int
00265   ConstSetView::lubMin(const Delta&) const {
00266     GECODE_NEVER;
00267     return 0;
00268   }
00269   forceinline int
00270   ConstSetView::lubMax(const Delta&) const {
00271     GECODE_NEVER;
00272     return 0;
00273   }
00274   forceinline bool
00275   ConstSetView::lubAny(const Delta&) const {
00276     GECODE_NEVER;
00277     return false;
00278   }
00279 
00280   forceinline
00281   EmptyView::EmptyView(void) {}
00282 
00283 
00284 
00285   forceinline unsigned int
00286   EmptyView::glbSize(void) const { return 0; }
00287 
00288   forceinline unsigned int
00289   EmptyView::lubSize(void) const { return 0; }
00290 
00291   forceinline unsigned int
00292   EmptyView::unknownSize(void) const { return 0; }
00293 
00294   forceinline bool
00295   EmptyView::contains(int) const { return false; }
00296 
00297   forceinline bool
00298   EmptyView::notContains(int) const { return true; }
00299 
00300   forceinline unsigned int
00301   EmptyView::cardMin(void) const { return 0; }
00302 
00303   forceinline unsigned int
00304   EmptyView::cardMax(void) const { return 0; }
00305 
00306   forceinline int
00307   EmptyView::lubMin(void) const { return 0; }
00308 
00309   forceinline int
00310   EmptyView::lubMax(void) const { return 0; }
00311 
00312   forceinline int
00313   EmptyView::glbMin(void) const { return 0; }
00314 
00315   forceinline int
00316   EmptyView::glbMax(void) const { return 0; }
00317 
00318   forceinline ModEvent
00319   EmptyView::cardMin(Space&,unsigned int c) {
00320     return c==0 ? ME_SET_NONE : ME_SET_FAILED;
00321   }
00322 
00323   forceinline ModEvent
00324   EmptyView::cardMax(Space&,unsigned int) {
00325     return ME_SET_NONE;
00326   }
00327 
00328 
00329   forceinline ModEvent
00330   EmptyView::include(Space&,int) {
00331     return ME_SET_FAILED;
00332   }
00333 
00334   forceinline ModEvent
00335   EmptyView::exclude(Space&,int) { return ME_SET_NONE; }
00336 
00337   forceinline ModEvent
00338   EmptyView::intersect(Space&,int) { return ME_SET_NONE; }
00339 
00340   forceinline ModEvent
00341   EmptyView::intersect(Space&,int,int) { return ME_SET_NONE; }
00342 
00343   forceinline ModEvent
00344   EmptyView::include(Space&,int,int) {
00345     return ME_SET_FAILED; }
00346 
00347   forceinline ModEvent
00348   EmptyView::exclude(Space&,int,int) { return ME_SET_NONE; }
00349 
00350   template<class I> ModEvent
00351   EmptyView::excludeI(Space&,I&) {
00352     Iter::Ranges::IsRangeIter<I>();
00353     return ME_SET_NONE;
00354   }
00355 
00356   template<class I> ModEvent
00357   EmptyView::includeI(Space&,I& i) {
00358     Iter::Ranges::IsRangeIter<I>();
00359     return i() ? ME_SET_FAILED : ME_SET_NONE;
00360   }
00361 
00362   template<class I> ModEvent
00363   EmptyView::intersectI(Space&,I&) {
00364     Iter::Ranges::IsRangeIter<I>();
00365     return ME_SET_NONE;
00366   }
00367 
00368   /*
00369    * Delta information for advisors
00370    *
00371    */
00372   forceinline int
00373   EmptyView::glbMin(const Delta&) const {
00374     GECODE_NEVER;
00375     return 0;
00376   }
00377 
00378   forceinline int
00379   EmptyView::glbMax(const Delta&) const {
00380     GECODE_NEVER;
00381     return 0;
00382   }
00383 
00384   forceinline bool
00385   EmptyView::glbAny(const Delta&) const {
00386     GECODE_NEVER;
00387     return false;
00388   }
00389 
00390   forceinline int
00391   EmptyView::lubMin(const Delta&) const {
00392     GECODE_NEVER;
00393     return 0;
00394   }
00395 
00396   forceinline int
00397   EmptyView::lubMax(const Delta&) const {
00398     GECODE_NEVER;
00399     return 0;
00400   }
00401 
00402   forceinline bool
00403   EmptyView::lubAny(const Delta&) const {
00404     GECODE_NEVER;
00405     return false;
00406   }
00407 
00408   // Constant universe variable
00409 
00410   forceinline
00411   UniverseView::UniverseView(void) {}
00412 
00413   forceinline unsigned int
00414   UniverseView::glbSize(void) const { return Set::Limits::card; }
00415 
00416   forceinline unsigned int
00417   UniverseView::lubSize(void) const { return Set::Limits::card; }
00418 
00419   forceinline unsigned int
00420   UniverseView::unknownSize(void) const { return 0; }
00421 
00422   forceinline bool
00423   UniverseView::contains(int) const { return true; }
00424 
00425   forceinline bool
00426   UniverseView::notContains(int) const { return false; }
00427 
00428   forceinline unsigned int
00429   UniverseView::cardMin(void) const { return Set::Limits::card; }
00430 
00431   forceinline unsigned int
00432   UniverseView::cardMax(void) const { return Limits::card; }
00433 
00434   forceinline int
00435   UniverseView::lubMin(void) const { return Limits::card; }
00436 
00437   forceinline int
00438   UniverseView::lubMax(void) const { return Limits::card; }
00439 
00440   forceinline int
00441   UniverseView::glbMin(void) const { return Limits::card; }
00442 
00443   forceinline int
00444   UniverseView::glbMax(void) const { return Limits::card; }
00445 
00446   forceinline ModEvent
00447   UniverseView::cardMin(Space&,unsigned int c) {
00448     return c>Limits::card ? ME_SET_FAILED : ME_SET_NONE;
00449   }
00450 
00451   forceinline ModEvent
00452   UniverseView::cardMax(Space&,unsigned int c) {
00453     return c>=Limits::card ? ME_SET_NONE : ME_SET_FAILED;
00454   }
00455 
00456 
00457   forceinline ModEvent
00458   UniverseView::include(Space&,int) {
00459     return ME_SET_NONE;
00460   }
00461 
00462   forceinline ModEvent
00463   UniverseView::exclude(Space&,int) { return ME_SET_FAILED; }
00464 
00465   forceinline ModEvent
00466   UniverseView::intersect(Space&,int) { return ME_SET_FAILED; }
00467 
00468   forceinline ModEvent
00469   UniverseView::include(Space&,int,int) { return ME_SET_NONE; }
00470 
00471   forceinline ModEvent
00472   UniverseView::exclude(Space&,int,int) { return ME_SET_FAILED; }
00473 
00474   template<class I> ModEvent
00475   UniverseView::excludeI(Space&,I& i) {
00476     Iter::Ranges::IsRangeIter<I>();
00477     return i() ? ME_SET_FAILED : ME_SET_NONE;
00478   }
00479 
00480   template<class I> forceinline ModEvent
00481   UniverseView::includeI(Space&,I&) {
00482     Iter::Ranges::IsRangeIter<I>();
00483     return ME_SET_NONE;
00484   }
00485 
00486   forceinline ModEvent
00487   UniverseView::intersect(Space&,int i,int j) {
00488     return (i>Limits::min ||
00489             j<Limits::max) ? ME_SET_FAILED : ME_SET_NONE;
00490   }
00491 
00492   template<class I> forceinline ModEvent
00493   UniverseView::intersectI(Space&,I& i) {
00494     Iter::Ranges::IsRangeIter<I>();
00495     return (i() &&
00496             (i.min()>Limits::min ||
00497              i.max()<Limits::max) ) ?
00498       ME_SET_FAILED : ME_SET_NONE;
00499   }
00500 
00501 
00502   /*
00503    * Delta information for advisors
00504    *
00505    */
00506   forceinline int
00507   UniverseView::glbMin(const Delta&) const {
00508     GECODE_NEVER;
00509     return 0;
00510   }
00511 
00512   forceinline int
00513   UniverseView::glbMax(const Delta&) const {
00514     GECODE_NEVER;
00515     return 0;
00516   }
00517 
00518   forceinline bool
00519   UniverseView::glbAny(const Delta&) const {
00520     GECODE_NEVER;
00521     return false;
00522   }
00523 
00524   forceinline int
00525   UniverseView::lubMin(const Delta&) const {
00526     GECODE_NEVER;
00527     return 0;
00528   }
00529 
00530   forceinline int
00531   UniverseView::lubMax(const Delta&) const {
00532     GECODE_NEVER;
00533     return 0;
00534   }
00535 
00536   forceinline bool
00537   UniverseView::lubAny(const Delta&) const {
00538     GECODE_NEVER;
00539     return false;
00540   }
00541 
00542   /*
00543    * Iterators
00544    *
00545    */
00546 
00551   template<>
00552   class LubRanges<EmptyView> : public Iter::Ranges::Empty {
00553   public:
00555 
00556 
00557     LubRanges(void) {}
00559     LubRanges(const EmptyView& x) { (void)x; }
00561     void init(const EmptyView& x) { (void)x; }
00563   };
00564 
00569   template<>
00570   class GlbRanges<EmptyView> : public Iter::Ranges::Empty {
00571   public:
00573 
00574 
00575     GlbRanges(void) {}
00577     GlbRanges(const EmptyView& x) { (void)x; }
00579     void init(const EmptyView& x) { (void)x; }
00581   };
00582 
00587   template<>
00588   class LubRanges<UniverseView> : public Iter::Ranges::Singleton {
00589   public:
00591 
00592 
00593     LubRanges(void)
00594       : Iter::Ranges::Singleton(Limits::min,
00595                                 Limits::max) {}
00597     LubRanges(const UniverseView& x)
00598       : Iter::Ranges::Singleton(Limits::min,
00599                                 Limits::max) {
00600         (void)x;
00601       }
00603     void init(const UniverseView& x) { (void)x; }
00605   };
00606 
00611   template<>
00612   class GlbRanges<UniverseView> : public Iter::Ranges::Singleton {
00613   public:
00615 
00616 
00617     GlbRanges(void)
00618       : Iter::Ranges::Singleton(Limits::min,
00619                                 Limits::max) {}
00621     GlbRanges(const UniverseView& x)
00622       : Iter::Ranges::Singleton(Limits::min,
00623                                 Limits::max) {
00624       (void)x;
00625     }
00627     void init(const UniverseView& x) { (void)x; }
00629   };
00630 
00631 
00636   template<>
00637   class LubRanges<ConstSetView> {
00638   private:
00639     ArrayRanges ar;
00640   public:
00642 
00643 
00644     LubRanges(void) {}
00646     LubRanges(const ConstSetView& x) : ar(x.ranges,x.size) {}
00648     void init(const ConstSetView& x) {
00649       ar.init(x.ranges,x.size);
00650     }
00652 
00654 
00655 
00656     bool operator ()(void) const { return ar(); }
00658     void operator ++(void) { ++ar; }
00660 
00662 
00663 
00664     int min(void) const { return ar.min(); }
00666     int max(void) const { return ar.max(); }
00668     unsigned int width(void) const { return ar.width(); }
00670   };
00671 
00676   template<>
00677   class GlbRanges<ConstSetView> : public LubRanges<ConstSetView> {
00678   public:
00680 
00681 
00682     GlbRanges(void) {}
00684     GlbRanges(const ConstSetView& x) : LubRanges<ConstSetView>(x) {}
00686     void init(const ConstSetView& x) {
00687       LubRanges<ConstSetView>::init(x);
00688     }
00690   };
00691 
00692   /*
00693    * Testing
00694    *
00695    */
00696   forceinline bool
00697   same(const ConstSetView& x, const ConstSetView& y) {
00698     if ((x.size != y.size) || (x.domSize != y.domSize))
00699       return false;
00700     for (int i=x.size; i--; )
00701       if (x.ranges[2*i]   != y.ranges[2*i] ||
00702           x.ranges[2*i+1] != y.ranges[2*i+1])
00703         return false;
00704     return true;
00705   }
00706   forceinline bool
00707   before(const ConstSetView& x, const ConstSetView& y) {
00708     if (x.size < y.size)
00709       return true;
00710     if (x.domSize < y.domSize)
00711       return true;
00712     for (int i=x.size; i--; )
00713       if (x.ranges[2*i]   < y.ranges[2*i] ||
00714           x.ranges[2*i+1] < y.ranges[2*i+1])
00715         return true;
00716     return false;
00717   }
00718 
00719 
00720   forceinline bool
00721   same(const EmptyView&, const EmptyView&) {
00722     return true;
00723   }
00724   forceinline bool
00725   same(const UniverseView&, const UniverseView&) {
00726     return true;
00727   }
00728 
00729 }}
00730 
00731 // STATISTICS: set-var
00732