Generated on Mon Nov 30 23:53:27 2009 for Gecode by doxygen 1.6.1

int-set.cpp

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