Generated on Fri Oct 19 11:25:06 2018 for Gecode by doxygen 1.6.3

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  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <gecode/int.hh>
00035 
00036 namespace Gecode {
00037 
00038   IntSet::IntSetObject*
00039   IntSet::IntSetObject::allocate(int n) {
00040     IntSetObject* o = new IntSetObject;
00041     o->n = n;
00042     o->r = heap.alloc<Range>(n);
00043     return o;
00044   }
00045 
00046   bool
00047   IntSet::IntSetObject::in(int n) const {
00048     int l = 0;
00049     int r = this->n - 1;
00050 
00051     while (l <= r) {
00052       int m = l + (r - l) / 2;
00053       if ((this->r[m].min <= n) && (n <= this->r[m].max)) {
00054         return true;
00055       } else if (l == r) {
00056         return false;
00057       } else if (n < this->r[m].min) {
00058         r=m-1;
00059       } else {
00060         l=m+1;
00061       }
00062     }
00063     return false;
00064   }
00065 
00066   bool
00067   IntSet::IntSetObject::equal(const IntSetObject& iso) const {
00068     assert((size == iso.size) || (n == iso.n));
00069     for (int i=0; i<n; i++)
00070       if ((r[i].min != iso.r[i].min) || (r[i].max != iso.r[i].max))
00071         return false;
00072     return true;
00073   }
00074 
00075   IntSet::IntSetObject::~IntSetObject(void) {
00076     heap.free<Range>(r,n);
00077   }
00078 
00080   class IntSet::MinInc {
00081   public:
00082     bool operator ()(const Range &x, const Range &y);
00083   };
00084 
00085   forceinline bool
00086   IntSet::MinInc::operator ()(const Range &x, const Range &y) {
00087     return x.min < y.min;
00088   }
00089 
00090   void
00091   IntSet::normalize(Range* r, int n) {
00092     if (n > 0) {
00093       // Sort ranges
00094       {
00095         MinInc lt_mi;
00096         Support::quicksort<Range>(r, n, lt_mi);
00097       }
00098       // Conjoin continuous ranges
00099       {
00100         int min = r[0].min;
00101         int max = r[0].max;
00102         int i = 1;
00103         int j = 0;
00104         while (i < n) {
00105           if (max+1 < r[i].min) {
00106             r[j].min = min; r[j].max = max; j++;
00107             min = r[i].min; max = r[i].max; i++;
00108           } else {
00109             max = std::max(max,r[i].max); i++;
00110           }
00111         }
00112         r[j].min = min; r[j].max = max;
00113         n=j+1;
00114       }
00115       IntSetObject* o = IntSetObject::allocate(n);
00116       unsigned int s = 0;
00117       for (int i=0; i<n; i++) {
00118         s += static_cast<unsigned int>(r[i].max-r[i].min+1);
00119         o->r[i]=r[i];
00120       }
00121       o->size = s;
00122       object(o);
00123     }
00124   }
00125 
00126   void
00127   IntSet::init(const int r[], int n) {
00128     assert(n > 0);
00129     Region reg;
00130     Range* dr = reg.alloc<Range>(n);
00131     for (int i=0; i<n; i++) {
00132       dr[i].min=r[i]; dr[i].max=r[i];
00133     }
00134     normalize(&dr[0],n);
00135   }
00136 
00137   void
00138   IntSet::init(const int r[][2], int n) {
00139     assert(n > 0);
00140     Region reg;
00141     Range* dr = reg.alloc<Range>(n);
00142     int j = 0;
00143     for (int i=0; i<n; i++)
00144       if (r[i][0] <= r[i][1]) {
00145         dr[j].min=r[i][0]; dr[j].max=r[i][1]; j++;
00146       }
00147     normalize(&dr[0],j);
00148   }
00149 
00150   IntSet::IntSet(std::initializer_list<int> r) {
00151     int n = static_cast<int>(r.size());
00152     assert(n > 0);
00153     Region reg;
00154     Range* dr = reg.alloc<Range>(n);
00155     int j=0;
00156     for (int k : r) {
00157       dr[j].min=dr[j].max=k; j++;
00158     }
00159     normalize(&dr[0],j);
00160   }
00161 
00162   IntSet::IntSet(std::initializer_list<std::pair<int,int>> r) {
00163     int n = static_cast<int>(r.size());
00164     assert(n > 0);
00165     Region reg;
00166     Range* dr = reg.alloc<Range>(n);
00167     int j=0;
00168     for (const std::pair<int,int>& k : r) 
00169       if (k.first <= k.second) {
00170         dr[j].min=k.first; dr[j].max=k.second; j++;
00171       }
00172     normalize(&dr[0],j);
00173   }
00174 
00175 
00176   void
00177   IntSet::init(int n, int m) {
00178     if (n <= m) {
00179       IntSetObject* o = IntSetObject::allocate(1);
00180       o->r[0].min = n; o->r[0].max = m;
00181       o->size = static_cast<unsigned int>(m - n + 1);
00182       object(o);
00183     }
00184   }
00185 
00186   const IntSet IntSet::empty;
00187 
00188 }
00189 
00190 // STATISTICS: int-var
00191