Generated on Tue Apr 18 10:22:14 2017 for Gecode by doxygen 1.6.3

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-07-28 17:35:33 +0200 (Wed, 28 Jul 2010) $ by $Author: schulte $
00011  *     $Revision: 11294 $
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     ArrayRanges ar(ranges, size);
00205     return (i() && Iter::Ranges::subset(i, ar)) ? ME_SET_FAILED : ME_SET_NONE;
00206   }
00207 
00208   template<class I> ModEvent
00209   ConstSetView::includeI(Space&,I& i) {
00210     ArrayRanges ar(ranges, size);
00211     return Iter::Ranges::subset(i, ar) ? ME_SET_NONE : ME_SET_FAILED;
00212   }
00213 
00214   template<class I> ModEvent
00215   ConstSetView::intersectI(Space&,I& i) {
00216     ArrayRanges ar(ranges, size);
00217     return Iter::Ranges::subset(ar, i) ? ME_SET_NONE : ME_SET_FAILED;
00218   }
00219 
00220   forceinline void
00221   ConstSetView::update(Space& home, bool share, ConstSetView& p) {
00222     ConstView<SetView>::update(home,share,p);
00223     // dispose old ranges
00224     if (size > 0)
00225       home.free<int>(ranges, 2);
00226 
00227     domSize = p.domSize;
00228     size = p.size;
00229     if (size == 0) {
00230       ranges = NULL;
00231     } else {
00232       // copy ranges from p
00233       ranges = home.alloc<int>(2*size);
00234       for (int i=size; i--; ) {
00235         ranges[2*i]   = p.ranges[2*i];
00236         ranges[2*i+1] = p.ranges[2*i+1];
00237       }
00238     }
00239   }
00240 
00241 
00242   /*
00243    * Delta information for advisors
00244    *
00245    */
00246   forceinline int
00247   ConstSetView::glbMin(const Delta&) const {
00248     GECODE_NEVER;
00249     return 0;
00250   }
00251   forceinline int
00252   ConstSetView::glbMax(const Delta&) const {
00253     GECODE_NEVER;
00254     return 0;
00255   }
00256   forceinline bool
00257   ConstSetView::glbAny(const Delta&) const {
00258     GECODE_NEVER;
00259     return false;
00260   }
00261   forceinline int
00262   ConstSetView::lubMin(const Delta&) const {
00263     GECODE_NEVER;
00264     return 0;
00265   }
00266   forceinline int
00267   ConstSetView::lubMax(const Delta&) const {
00268     GECODE_NEVER;
00269     return 0;
00270   }
00271   forceinline bool
00272   ConstSetView::lubAny(const Delta&) const {
00273     GECODE_NEVER;
00274     return false;
00275   }
00276 
00277   forceinline
00278   EmptyView::EmptyView(void) {}
00279 
00280 
00281 
00282   forceinline unsigned int
00283   EmptyView::glbSize(void) const { return 0; }
00284 
00285   forceinline unsigned int
00286   EmptyView::lubSize(void) const { return 0; }
00287 
00288   forceinline unsigned int
00289   EmptyView::unknownSize(void) const { return 0; }
00290 
00291   forceinline bool
00292   EmptyView::contains(int) const { return false; }
00293 
00294   forceinline bool
00295   EmptyView::notContains(int) const { return true; }
00296 
00297   forceinline unsigned int
00298   EmptyView::cardMin(void) const { return 0; }
00299 
00300   forceinline unsigned int
00301   EmptyView::cardMax(void) const { return 0; }
00302 
00303   forceinline int
00304   EmptyView::lubMin(void) const { return 0; }
00305 
00306   forceinline int
00307   EmptyView::lubMax(void) const { return 0; }
00308 
00309   forceinline int
00310   EmptyView::glbMin(void) const { return 0; }
00311 
00312   forceinline int
00313   EmptyView::glbMax(void) const { return 0; }
00314 
00315   forceinline ModEvent
00316   EmptyView::cardMin(Space&,unsigned int c) {
00317     return c==0 ? ME_SET_NONE : ME_SET_FAILED;
00318   }
00319 
00320   forceinline ModEvent
00321   EmptyView::cardMax(Space&,unsigned int) {
00322     return ME_SET_NONE;
00323   }
00324 
00325 
00326   forceinline ModEvent
00327   EmptyView::include(Space&,int) {
00328     return ME_SET_FAILED;
00329   }
00330 
00331   forceinline ModEvent
00332   EmptyView::exclude(Space&,int) { return ME_SET_NONE; }
00333 
00334   forceinline ModEvent
00335   EmptyView::intersect(Space&,int) { return ME_SET_NONE; }
00336 
00337   forceinline ModEvent
00338   EmptyView::intersect(Space&,int,int) { return ME_SET_NONE; }
00339 
00340   forceinline ModEvent
00341   EmptyView::include(Space&,int,int) {
00342     return ME_SET_FAILED; }
00343 
00344   forceinline ModEvent
00345   EmptyView::exclude(Space&,int,int) { return ME_SET_NONE; }
00346 
00347   template<class I> ModEvent
00348   EmptyView::excludeI(Space&,I&) {
00349     return ME_SET_NONE;
00350   }
00351 
00352   template<class I> ModEvent
00353   EmptyView::includeI(Space&,I& i) {
00354     return i() ? ME_SET_FAILED : ME_SET_NONE;
00355   }
00356 
00357   template<class I> ModEvent
00358   EmptyView::intersectI(Space&,I&) {
00359     return ME_SET_NONE;
00360   }
00361 
00362   /*
00363    * Delta information for advisors
00364    *
00365    */
00366   forceinline int
00367   EmptyView::glbMin(const Delta&) const {
00368     GECODE_NEVER;
00369     return 0;
00370   }
00371 
00372   forceinline int
00373   EmptyView::glbMax(const Delta&) const {
00374     GECODE_NEVER;
00375     return 0;
00376   }
00377 
00378   forceinline bool
00379   EmptyView::glbAny(const Delta&) const {
00380     GECODE_NEVER;
00381     return false;
00382   }
00383 
00384   forceinline int
00385   EmptyView::lubMin(const Delta&) const {
00386     GECODE_NEVER;
00387     return 0;
00388   }
00389 
00390   forceinline int
00391   EmptyView::lubMax(const Delta&) const {
00392     GECODE_NEVER;
00393     return 0;
00394   }
00395 
00396   forceinline bool
00397   EmptyView::lubAny(const Delta&) const {
00398     GECODE_NEVER;
00399     return false;
00400   }
00401 
00402   // Constant universe variable
00403 
00404   forceinline
00405   UniverseView::UniverseView(void) {}
00406 
00407   forceinline unsigned int
00408   UniverseView::glbSize(void) const { return Set::Limits::card; }
00409 
00410   forceinline unsigned int
00411   UniverseView::lubSize(void) const { return Set::Limits::card; }
00412 
00413   forceinline unsigned int
00414   UniverseView::unknownSize(void) const { return 0; }
00415 
00416   forceinline bool
00417   UniverseView::contains(int) const { return true; }
00418 
00419   forceinline bool
00420   UniverseView::notContains(int) const { return false; }
00421 
00422   forceinline unsigned int
00423   UniverseView::cardMin(void) const { return Set::Limits::card; }
00424 
00425   forceinline unsigned int
00426   UniverseView::cardMax(void) const { return Limits::card; }
00427 
00428   forceinline int
00429   UniverseView::lubMin(void) const { return Limits::card; }
00430 
00431   forceinline int
00432   UniverseView::lubMax(void) const { return Limits::card; }
00433 
00434   forceinline int
00435   UniverseView::glbMin(void) const { return Limits::card; }
00436 
00437   forceinline int
00438   UniverseView::glbMax(void) const { return Limits::card; }
00439 
00440   forceinline ModEvent
00441   UniverseView::cardMin(Space&,unsigned int c) {
00442     return c>Limits::card ? ME_SET_FAILED : ME_SET_NONE;
00443   }
00444 
00445   forceinline ModEvent
00446   UniverseView::cardMax(Space&,unsigned int c) {
00447     return c>=Limits::card ? ME_SET_NONE : ME_SET_FAILED;
00448   }
00449 
00450 
00451   forceinline ModEvent
00452   UniverseView::include(Space&,int) {
00453     return ME_SET_NONE;
00454   }
00455 
00456   forceinline ModEvent
00457   UniverseView::exclude(Space&,int) { return ME_SET_FAILED; }
00458 
00459   forceinline ModEvent
00460   UniverseView::intersect(Space&,int) { return ME_SET_FAILED; }
00461 
00462   forceinline ModEvent
00463   UniverseView::include(Space&,int,int) { return ME_SET_NONE; }
00464 
00465   forceinline ModEvent
00466   UniverseView::exclude(Space&,int,int) { return ME_SET_FAILED; }
00467 
00468   template<class I> ModEvent
00469   UniverseView::excludeI(Space&,I& i) {
00470     return i() ? ME_SET_FAILED : ME_SET_NONE;
00471   }
00472 
00473   template<class I> forceinline ModEvent
00474   UniverseView::includeI(Space&,I&) {
00475     return ME_SET_NONE;
00476   }
00477 
00478   forceinline ModEvent
00479   UniverseView::intersect(Space&,int i,int j) {
00480     return (i>Limits::min ||
00481             j<Limits::max) ? ME_SET_FAILED : ME_SET_NONE;
00482   }
00483 
00484   template<class I> forceinline ModEvent
00485   UniverseView::intersectI(Space&,I& i) {
00486     return (i() &&
00487             (i.min()>Limits::min ||
00488              i.max()<Limits::max) ) ?
00489       ME_SET_FAILED : ME_SET_NONE;
00490   }
00491 
00492 
00493   /*
00494    * Delta information for advisors
00495    *
00496    */
00497   forceinline int
00498   UniverseView::glbMin(const Delta&) const {
00499     GECODE_NEVER;
00500     return 0;
00501   }
00502 
00503   forceinline int
00504   UniverseView::glbMax(const Delta&) const {
00505     GECODE_NEVER;
00506     return 0;
00507   }
00508 
00509   forceinline bool
00510   UniverseView::glbAny(const Delta&) const {
00511     GECODE_NEVER;
00512     return false;
00513   }
00514 
00515   forceinline int
00516   UniverseView::lubMin(const Delta&) const {
00517     GECODE_NEVER;
00518     return 0;
00519   }
00520 
00521   forceinline int
00522   UniverseView::lubMax(const Delta&) const {
00523     GECODE_NEVER;
00524     return 0;
00525   }
00526 
00527   forceinline bool
00528   UniverseView::lubAny(const Delta&) const {
00529     GECODE_NEVER;
00530     return false;
00531   }
00532 
00533   /*
00534    * Iterators
00535    *
00536    */
00537 
00542   template<>
00543   class LubRanges<EmptyView> : public Iter::Ranges::Empty {
00544   public:
00546 
00547 
00548     LubRanges(void) {}
00550     LubRanges(const EmptyView& x) { (void)x; }
00552     void init(const EmptyView& x) { (void)x; }
00554   };
00555 
00560   template<>
00561   class GlbRanges<EmptyView> : public Iter::Ranges::Empty {
00562   public:
00564 
00565 
00566     GlbRanges(void) {}
00568     GlbRanges(const EmptyView& x) { (void)x; }
00570     void init(const EmptyView& x) { (void)x; }
00572   };
00573 
00578   template<>
00579   class LubRanges<UniverseView> : public Iter::Ranges::Singleton {
00580   public:
00582 
00583 
00584     LubRanges(void)
00585       : Iter::Ranges::Singleton(Limits::min,
00586                                 Limits::max) {}
00588     LubRanges(const UniverseView& x)
00589       : Iter::Ranges::Singleton(Limits::min,
00590                                 Limits::max) {
00591         (void)x;
00592       }
00594     void init(const UniverseView& x) { (void)x; }
00596   };
00597 
00602   template<>
00603   class GlbRanges<UniverseView> : public Iter::Ranges::Singleton {
00604   public:
00606 
00607 
00608     GlbRanges(void)
00609       : Iter::Ranges::Singleton(Limits::min,
00610                                 Limits::max) {}
00612     GlbRanges(const UniverseView& x)
00613       : Iter::Ranges::Singleton(Limits::min,
00614                                 Limits::max) {
00615       (void)x;
00616     }
00618     void init(const UniverseView& x) { (void)x; }
00620   };
00621 
00622 
00627   template<>
00628   class LubRanges<ConstSetView> {
00629   private:
00630     ArrayRanges ar;
00631   public:
00633 
00634 
00635     LubRanges(void) {}
00637     LubRanges(const ConstSetView& x) : ar(x.ranges,x.size) {}
00639     void init(const ConstSetView& x) {
00640       ar.init(x.ranges,x.size);
00641     }
00643 
00645 
00646 
00647     bool operator ()(void) const { return ar(); }
00649     void operator ++(void) { ++ar; }
00651 
00653 
00654 
00655     int min(void) const { return ar.min(); }
00657     int max(void) const { return ar.max(); }
00659     unsigned int width(void) const { return ar.width(); }
00661   };
00662 
00667   template<>
00668   class GlbRanges<ConstSetView> : public LubRanges<ConstSetView> {
00669   public:
00671 
00672 
00673     GlbRanges(void) {}
00675     GlbRanges(const ConstSetView& x) : LubRanges<ConstSetView>(x) {}
00677     void init(const ConstSetView& x) {
00678       LubRanges<ConstSetView>::init(x);
00679     }
00681   };
00682 
00683   /*
00684    * Testing
00685    *
00686    */
00687   forceinline bool
00688   same(const ConstSetView& x, const ConstSetView& y) {
00689     if ((x.size != y.size) || (x.domSize != y.domSize))
00690       return false;
00691     for (int i=x.size; i--; )
00692       if (x.ranges[2*i]   != y.ranges[2*i] ||
00693           x.ranges[2*i+1] != y.ranges[2*i+1])
00694         return false;
00695     return true;
00696   }
00697   forceinline bool
00698   before(const ConstSetView& x, const ConstSetView& y) {
00699     if (x.size < y.size)
00700       return true;
00701     if (x.domSize < y.domSize)
00702       return true;
00703     for (int i=x.size; i--; )
00704       if (x.ranges[2*i]   < y.ranges[2*i] ||
00705           x.ranges[2*i+1] < y.ranges[2*i+1])
00706         return true;
00707     return false;
00708   }
00709 
00710 
00711   forceinline bool
00712   same(const EmptyView&, const EmptyView&) {
00713     return true;
00714   }
00715   forceinline bool
00716   same(const UniverseView&, const UniverseView&) {
00717     return true;
00718   }
00719 
00720 }}
00721 
00722 // STATISTICS: set-var
00723