Generated on Mon May 5 05:53:56 2008 for Gecode by doxygen 1.5.5

int-set.cc

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: 2008-02-12 08:13:01 +0100 (Tue, 12 Feb 2008) $ by $Author: schulte $
00011  *     $Revision: 6130 $
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 "gecode/int.hh"
00039 
00040 namespace Gecode {
00041 
00042   IntSet::IntSetObject*
00043   IntSet::IntSetObject::allocate(int n) {
00044     IntSetObject* o = new IntSetObject;
00045     o->n = n;
00046     o->r = static_cast<Range*>(Memory::malloc(n*sizeof(Range)));
00047     return o;
00048   }
00049 
00050   SharedHandle::Object*
00051   IntSet::IntSetObject::copy(void) const {
00052     IntSetObject* o = allocate(n);
00053     for (int i=n; i--; )
00054       o->r[i]=r[i];
00055     return o;
00056   }
00057 
00058   IntSet::IntSetObject::~IntSetObject(void) {
00059     Memory::free(r);
00060   }
00061 
00063   class IntSet::MinInc {
00064   public:
00065     bool operator()(const Range &x, const Range &y);
00066   };
00067 
00068   forceinline bool
00069   IntSet::MinInc::operator()(const Range &x, const Range &y) {
00070     return x.min < y.min;
00071   }
00072 
00073   void
00074   IntSet::normalize(Range* r, int n) {
00075     if (n > 0) {
00076       // Sort ranges
00077       MinInc lt_mi;
00078       Support::quicksort<Range>(r, n, lt_mi);
00079       // Conjoin continuous ranges
00080       int min = r[0].min;
00081       int max = r[0].max;
00082       int i = 1;
00083       int j = 0;
00084       while (i < n) {
00085         if (max+1 < r[i].min) {
00086           r[j].min = min; r[j].max = max; j++;
00087           min = r[i].min; max = r[i].max; i++;
00088         } else {
00089           max = std::max(max,r[i].max); i++;
00090         }
00091       }
00092       r[j].min = min; r[j].max = max;
00093       n=j+1;
00094       IntSetObject* o = IntSetObject::allocate(n);
00095       for (int i=n; i--; )
00096         o->r[i]=r[i];
00097       object(o);
00098     }
00099   }
00100 
00101   void
00102   IntSet::init(const int r[], int n) {
00103     GECODE_AUTOARRAY(Range,dr,n);
00104     for (int i=n; i--; ) {
00105       dr[i].min=r[i]; dr[i].max=r[i];
00106     }
00107     normalize(&dr[0],n);
00108   }
00109 
00110   void
00111   IntSet::init(const int r[][2], int n) {
00112     GECODE_AUTOARRAY(Range,dr,n);
00113     int j = 0;
00114     for (int i=n; i--; )
00115       if (r[i][0] <= r[i][1]) {
00116         dr[j].min=r[i][0]; dr[j].max=r[i][1]; j++;
00117       }
00118     normalize(&dr[0],j);
00119   }
00120 
00121   void
00122   IntSet::init(int n, int m) {
00123     if (n <= m) {
00124       IntSetObject* o = IntSetObject::allocate(1);
00125       o->r[0].min = n; o->r[0].max = m;
00126       object(o);
00127     }
00128   }
00129 
00130   const IntSet IntSet::empty;
00131 
00132 }
00133 
00134 std::ostream&
00135 operator<<(std::ostream& os, const Gecode::IntSet& is) {
00136   os << '{';
00137   for (int i = 0; i < is.size(); ) {
00138     int min = is.min(i);
00139     int max = is.max(i);
00140     if (min == max)
00141       os << min;
00142     else
00143       os << min << ".." << max;
00144     i++;
00145     if (i < is.size())
00146       os << ',';
00147   }
00148   return os << '}';
00149 }
00150 
00151 
00152 // STATISTICS: int-var
00153