Generated on Tue Dec 13 2011 10:02:15 for Gecode by doxygen 1.7.4
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  *  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 #include <sstream>
00039 
00040 namespace Gecode {
00041 
00042   /*
00043    * Integer sets
00044    *
00045    */
00046   forceinline
00047   IntSet::IntSet(void) {}
00048 
00049   template<class I>
00050   IntSet::IntSet(I& i) {
00051     Support::DynamicArray<Range,Heap> d(heap);
00052     int n=0;
00053     unsigned int s = 0;
00054     while (i()) {
00055       d[n].min = i.min(); d[n].max = i.max(); s += i.width();
00056       ++n; ++i;
00057     }
00058     if (n > 0) {
00059       IntSetObject* o = IntSetObject::allocate(n);
00060       for (int j=n; j--; )
00061         o->r[j]=d[j];
00062       o->size = s;
00063       object(o);
00064     }
00065   }
00066 
00067 #ifndef __INTEL_COMPILER
00068   template<>
00069 #endif
00070   forceinline
00071   IntSet::IntSet(const IntSet& s)
00072     : SharedHandle(s) {}
00073 
00074 #ifndef __INTEL_COMPILER
00075   template<>
00076 #endif
00077   forceinline
00078   IntSet::IntSet(IntSet& s)
00079     : SharedHandle(s) {}
00080 
00081   forceinline
00082   IntSet::IntSet(const int r[][2], int n) {
00083     init(r,n);
00084   }
00085 
00086   forceinline
00087   IntSet::IntSet(const int r[], int n) {
00088     init(r,n);
00089   }
00090 
00091   forceinline
00092   IntSet::IntSet(int n, int m) {
00093     init(n,m);
00094   }
00095 
00096   forceinline int
00097   IntSet::min(int i) const {
00098     assert(object() != NULL);
00099     return static_cast<IntSetObject*>(object())->r[i].min;
00100   }
00101 
00102   forceinline int
00103   IntSet::max(int i) const {
00104     assert(object() != NULL);
00105     return static_cast<IntSetObject*>(object())->r[i].max;
00106   }
00107 
00108   forceinline unsigned int
00109   IntSet::width(int i) const {
00110     assert(object() != NULL);
00111     IntSetObject* o = static_cast<IntSetObject*>(object());
00112     return static_cast<unsigned int>(o->r[i].max-o->r[i].min)+1;
00113   }
00114 
00115   forceinline int
00116   IntSet::ranges(void) const {
00117     IntSetObject* o = static_cast<IntSetObject*>(object());
00118     return (o == NULL) ? 0 : o->n;
00119   }
00120 
00121   forceinline bool
00122   IntSet::in(int n) const {
00123     IntSetObject* o = static_cast<IntSetObject*>(object());
00124     if ((o == NULL) || (n < o->r[0].min) || (n > o->r[o->n-1].max))
00125       return false;
00126     else
00127       return o->in(n);
00128   }
00129 
00130   forceinline int
00131   IntSet::min(void) const {
00132     IntSetObject* o = static_cast<IntSetObject*>(object());
00133     return (o == NULL) ? Int::Limits::max : o->r[0].min;
00134   }
00135 
00136   forceinline int
00137   IntSet::max(void) const {
00138     IntSetObject* o = static_cast<IntSetObject*>(object());
00139     return (o == NULL) ? Int::Limits::min : o->r[o->n-1].max;
00140   }
00141 
00142   forceinline unsigned int
00143   IntSet::size(void) const {
00144     IntSetObject* o = static_cast<IntSetObject*>(object());
00145     return (o == NULL) ? 0 : o->size;
00146   }
00147 
00148   forceinline unsigned int
00149   IntSet::width(void) const {
00150     return static_cast<unsigned int>(max()-min()+1);
00151   }
00152 
00153 
00154   /*
00155    * Range iterator for integer sets
00156    *
00157    */
00158 
00159   forceinline
00160   IntSetRanges::IntSetRanges(void) {}
00161   forceinline
00162   void
00163   IntSetRanges::init(const IntSet& s) {
00164     int n = s.ranges();
00165     if (n > 0) {
00166       i = &static_cast<IntSet::IntSetObject*>(s.object())->r[0]; e = i+n;
00167     } else {
00168       i = e = NULL;
00169     }
00170   }
00171   forceinline
00172   IntSetRanges::IntSetRanges(const IntSet& s) { init(s); }
00173 
00174 
00175   forceinline void
00176   IntSetRanges::operator ++(void) {
00177     i++;
00178   }
00179   forceinline bool
00180   IntSetRanges::operator ()(void) const {
00181     return i<e;
00182   }
00183 
00184   forceinline int
00185   IntSetRanges::min(void) const {
00186     return i->min;
00187   }
00188   forceinline int
00189   IntSetRanges::max(void) const {
00190     return i->max;
00191   }
00192   forceinline unsigned int
00193   IntSetRanges::width(void) const {
00194     return static_cast<unsigned int>(i->max - i->min) + 1;
00195   }
00196 
00197   /*
00198    * Value iterator for integer sets
00199    *
00200    */
00201   forceinline
00202   IntSetValues::IntSetValues(void) {}
00203 
00204   forceinline
00205   IntSetValues::IntSetValues(const IntSet& s) {
00206     IntSetRanges r(s);
00207     Iter::Ranges::ToValues<IntSetRanges>::init(r);
00208   }
00209 
00210   forceinline void
00211   IntSetValues::init(const IntSet& s) {
00212     IntSetRanges r(s);
00213     Iter::Ranges::ToValues<IntSetRanges>::init(r);
00214   }
00215 
00216   template<class Char, class Traits>
00217   std::basic_ostream<Char,Traits>&
00218   operator <<(std::basic_ostream<Char,Traits>& os, const IntSet& is) {
00219     std::basic_ostringstream<Char,Traits> s;
00220     s.copyfmt(os); s.width(0);
00221     s << '{';
00222     for (int i = 0; i < is.ranges(); ) {
00223       int min = is.min(i);
00224       int max = is.max(i);
00225       if (min == max)
00226         s << min;
00227       else
00228         s << min << ".." << max;
00229       i++;
00230       if (i < is.ranges())
00231         s << ',';
00232     }
00233     s << '}';
00234     return os << s.str();
00235   }
00236 
00237 }
00238 
00239 // STATISTICS: int-var
00240