Generated on Mon Nov 30 23:53:27 2009 for Gecode by doxygen 1.6.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-09-08 21:10:29 +0200 (Tue, 08 Sep 2009) $ by $Author: schulte $
00011  *     $Revision: 9692 $
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 int
00123   IntSet::min(void) const {
00124     IntSetObject* o = static_cast<IntSetObject*>(object());
00125     return (o == NULL) ? Int::Limits::max : o->r[0].min;
00126   }
00127 
00128   forceinline int
00129   IntSet::max(void) const {
00130     IntSetObject* o = static_cast<IntSetObject*>(object());
00131     return (o == NULL) ? Int::Limits::min : o->r[o->n-1].max;
00132   }
00133 
00134   forceinline unsigned int
00135   IntSet::size(void) const {
00136     IntSetObject* o = static_cast<IntSetObject*>(object());
00137     return (o == NULL) ? 0 : o->size;
00138   }
00139 
00140   forceinline unsigned int
00141   IntSet::width(void) const {
00142     return static_cast<unsigned int>(max()-min()+1);
00143   }
00144 
00145 
00146   /*
00147    * Range iterator for integer sets
00148    *
00149    */
00150 
00151   forceinline
00152   IntSetRanges::IntSetRanges(void) {}
00153   forceinline
00154   void
00155   IntSetRanges::init(const IntSet& s) {
00156     int n = s.ranges();
00157     if (n > 0) {
00158       i = &static_cast<IntSet::IntSetObject*>(s.object())->r[0]; e = i+n;
00159     } else {
00160       i = e = NULL;
00161     }
00162   }
00163   forceinline
00164   IntSetRanges::IntSetRanges(const IntSet& s) { init(s); }
00165 
00166 
00167   forceinline void
00168   IntSetRanges::operator ++(void) {
00169     i++;
00170   }
00171   forceinline bool
00172   IntSetRanges::operator ()(void) const {
00173     return i<e;
00174   }
00175 
00176   forceinline int
00177   IntSetRanges::min(void) const {
00178     return i->min;
00179   }
00180   forceinline int
00181   IntSetRanges::max(void) const {
00182     return i->max;
00183   }
00184   forceinline unsigned int
00185   IntSetRanges::width(void) const {
00186     return static_cast<unsigned int>(i->max - i->min) + 1;
00187   }
00188 
00189   /*
00190    * Value iterator for integer sets
00191    *
00192    */
00193   forceinline
00194   IntSetValues::IntSetValues(void) {}
00195 
00196   forceinline
00197   IntSetValues::IntSetValues(const IntSet& s) {
00198     IntSetRanges r(s);
00199     Iter::Ranges::ToValues<IntSetRanges>::init(r);
00200   }
00201 
00202   forceinline void
00203   IntSetValues::init(const IntSet& s) {
00204     IntSetRanges r(s);
00205     Iter::Ranges::ToValues<IntSetRanges>::init(r);
00206   }
00207 
00208   template<class Char, class Traits>
00209   std::basic_ostream<Char,Traits>&
00210   operator <<(std::basic_ostream<Char,Traits>& os, const IntSet& is) {
00211     std::basic_ostringstream<Char,Traits> s;
00212     s.copyfmt(os); s.width(0);
00213     s << '{';
00214     for (int i = 0; i < is.ranges(); ) {
00215       int min = is.min(i);
00216       int max = is.max(i);
00217       if (min == max)
00218         s << min;
00219       else
00220         s << min << ".." << max;
00221       i++;
00222       if (i < is.ranges())
00223         s << ',';
00224     }
00225     s << '}';
00226     return os << s.str();
00227   }
00228 
00229 }
00230 
00231 // STATISTICS: int-var
00232