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