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

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