Generated on Fri Oct 19 11:25:06 2018 for Gecode by doxygen 1.6.3

int-set-1.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2003
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 #include <sstream>
00035 
00036 namespace Gecode {
00037 
00038   /*
00039    * Integer sets
00040    *
00041    */
00042   forceinline
00043   IntSet::IntSet(void) {}
00044 
00052   template<class I>
00053   class IntSetInit {
00054   public:
00056     static void init(IntSet& s, I& i) {
00057       Region reg;
00058       Support::DynamicArray<IntSet::Range,Region> d(reg);
00059       int n=0;
00060       unsigned int size = 0;
00061       while (i()) {
00062         d[n].min = i.min(); d[n].max = i.max(); size += i.width();
00063         ++n; ++i;
00064       }
00065       if (n > 0) {
00066         IntSet::IntSetObject* o = IntSet::IntSetObject::allocate(n);
00067         for (int j=0; j<n; j++)
00068           o->r[j]=d[j];
00069         o->size = size;
00070         s.object(o);
00071       }
00072     }
00073   };
00074 
00076   template<>
00077   class IntSetInit<IntSet> {
00078   public:
00079     static void init(IntSet& s, const IntSet& i) {
00080       s.object(i.object());
00081     }
00082   };
00083 
00085   template<class I>
00086   IntSet::IntSet(I& i) {
00087     IntSetInit<I>::init(*this,i);
00088   }
00089 
00091   template<class I>
00092   IntSet::IntSet(const I& i) {
00093     IntSetInit<I>::init(*this,i);
00094   }
00095 
00096   forceinline
00097   IntSet::IntSet(const int r[][2], int n) {
00098     if (n > 0)
00099       init(r,n);
00100   }
00101 
00102   forceinline
00103   IntSet::IntSet(const int r[], int n) {
00104     if (n > 0)
00105       init(r,n);
00106   }
00107 
00109   template<>
00110   inline
00111   IntSet::IntSet(const std::vector<int>& r) {
00112     int n = static_cast<int>(r.size());
00113     if (n > 0) {
00114       Region reg;
00115       Range* dr = reg.alloc<Range>(n);
00116       for (int i=0; i<n; i++)
00117         dr[i].min=dr[i].max=r[i];
00118       normalize(&dr[0],n);
00119     }
00120   }
00121 
00127   template<>
00128   inline
00129   IntSet::IntSet(const std::vector<std::pair<int,int>>& r) {
00130     int n = static_cast<int>(r.size());
00131     if (n > 0) {
00132       Region reg;
00133       Range* dr = reg.alloc<Range>(n);
00134       int j=0;
00135       for (int i=0; i<n; i++) 
00136         if (r[i].first <= r[i].second) {
00137           dr[j].min=r[i].first; dr[j].max=r[i].second; j++;
00138         }
00139       normalize(&dr[0],j);
00140     }
00141   }
00142 
00143   forceinline
00144   IntSet::IntSet(int n, int m) {
00145     init(n,m);
00146   }
00147 
00148   forceinline int
00149   IntSet::min(int i) const {
00150     assert(object() != NULL);
00151     return static_cast<IntSetObject*>(object())->r[i].min;
00152   }
00153 
00154   forceinline int
00155   IntSet::max(int i) const {
00156     assert(object() != NULL);
00157     return static_cast<IntSetObject*>(object())->r[i].max;
00158   }
00159 
00160   forceinline unsigned int
00161   IntSet::width(int i) const {
00162     assert(object() != NULL);
00163     IntSetObject* o = static_cast<IntSetObject*>(object());
00164     return static_cast<unsigned int>(o->r[i].max-o->r[i].min)+1;
00165   }
00166 
00167   forceinline int
00168   IntSet::ranges(void) const {
00169     IntSetObject* o = static_cast<IntSetObject*>(object());
00170     return (o == NULL) ? 0 : o->n;
00171   }
00172 
00173   forceinline bool
00174   IntSet::in(int n) const {
00175     IntSetObject* o = static_cast<IntSetObject*>(object());
00176     if ((o == NULL) || (n < o->r[0].min) || (n > o->r[o->n-1].max))
00177       return false;
00178     else
00179       return o->in(n);
00180   }
00181 
00182   forceinline int
00183   IntSet::min(void) const {
00184     IntSetObject* o = static_cast<IntSetObject*>(object());
00185     return (o == NULL) ? Int::Limits::max : o->r[0].min;
00186   }
00187 
00188   forceinline int
00189   IntSet::max(void) const {
00190     IntSetObject* o = static_cast<IntSetObject*>(object());
00191     return (o == NULL) ? Int::Limits::min : o->r[o->n-1].max;
00192   }
00193 
00194   forceinline unsigned int
00195   IntSet::size(void) const {
00196     IntSetObject* o = static_cast<IntSetObject*>(object());
00197     return (o == NULL) ? 0U : o->size;
00198   }
00199 
00200   forceinline unsigned int
00201   IntSet::width(void) const {
00202     IntSetObject* o = static_cast<IntSetObject*>(object());
00203     return (o == NULL) ? 0U : static_cast<unsigned int>(max()-min()+1);
00204   }
00205 
00206   forceinline bool
00207   IntSet::operator ==(const IntSet& s) const {
00208     IntSetObject* o1 = static_cast<IntSetObject*>(object());
00209     IntSetObject* o2 = static_cast<IntSetObject*>(s.object());
00210     if (o1 == o2)
00211       return true;
00212     if ((o1 == nullptr) || (o2 == nullptr))
00213       return false;
00214     if ((o1->size != o2->size) || (o1->n != o2->n))
00215       return false;
00216     return o1->equal(*o2);
00217   }
00218 
00219   forceinline bool
00220   IntSet::operator !=(const IntSet& s) const {
00221     return !(*this == s);
00222   }
00223 
00224 
00225   /*
00226    * Range iterator for integer sets
00227    *
00228    */
00229 
00230   forceinline
00231   IntSetRanges::IntSetRanges(void) {}
00232   forceinline
00233   void
00234   IntSetRanges::init(const IntSet& s) {
00235     int n = s.ranges();
00236     if (n > 0) {
00237       i = &static_cast<IntSet::IntSetObject*>(s.object())->r[0]; e = i+n;
00238     } else {
00239       i = e = NULL;
00240     }
00241   }
00242   forceinline
00243   IntSetRanges::IntSetRanges(const IntSet& s) { init(s); }
00244 
00245 
00246   forceinline void
00247   IntSetRanges::operator ++(void) {
00248     i++;
00249   }
00250   forceinline bool
00251   IntSetRanges::operator ()(void) const {
00252     return i<e;
00253   }
00254 
00255   forceinline int
00256   IntSetRanges::min(void) const {
00257     return i->min;
00258   }
00259   forceinline int
00260   IntSetRanges::max(void) const {
00261     return i->max;
00262   }
00263   forceinline unsigned int
00264   IntSetRanges::width(void) const {
00265     return static_cast<unsigned int>(i->max - i->min) + 1;
00266   }
00267 
00268   /*
00269    * Value iterator for integer sets
00270    *
00271    */
00272   forceinline
00273   IntSetValues::IntSetValues(void) {}
00274 
00275   forceinline
00276   IntSetValues::IntSetValues(const IntSet& s) {
00277     IntSetRanges r(s);
00278     Iter::Ranges::ToValues<IntSetRanges>::init(r);
00279   }
00280 
00281   forceinline void
00282   IntSetValues::init(const IntSet& s) {
00283     IntSetRanges r(s);
00284     Iter::Ranges::ToValues<IntSetRanges>::init(r);
00285   }
00286 
00287   template<class Char, class Traits>
00288   std::basic_ostream<Char,Traits>&
00289   operator <<(std::basic_ostream<Char,Traits>& os, const IntSet& is) {
00290     std::basic_ostringstream<Char,Traits> s;
00291     s.copyfmt(os); s.width(0);
00292     s << '{';
00293     for (int i = 0; i < is.ranges(); ) {
00294       int min = is.min(i);
00295       int max = is.max(i);
00296       if (min == max)
00297         s << min;
00298       else
00299         s << min << ".." << max;
00300       i++;
00301       if (i < is.ranges())
00302         s << ',';
00303     }
00304     s << '}';
00305     return os << s.str();
00306   }
00307 
00308 }
00309 
00310 // STATISTICS: int-var
00311