int-set.cpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
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 bool
00060 IntSet::IntSetObject::in(int n) const {
00061 int l = 0;
00062 int r = this->n - 1;
00063
00064 while (l <= r) {
00065 int m = l + (r - l) / 2;
00066 if ((this->r[m].min <= n) && (n <= this->r[m].max)) {
00067 return true;
00068 } else if (l == r) {
00069 return false;
00070 } else if (n < this->r[m].min) {
00071 r=m-1;
00072 } else {
00073 l=m+1;
00074 }
00075 }
00076 return false;
00077 }
00078
00079 IntSet::IntSetObject::~IntSetObject(void) {
00080 heap.free<Range>(r,n);
00081 }
00082
00084 class IntSet::MinInc {
00085 public:
00086 bool operator ()(const Range &x, const Range &y);
00087 };
00088
00089 forceinline bool
00090 IntSet::MinInc::operator ()(const Range &x, const Range &y) {
00091 return x.min < y.min;
00092 }
00093
00094 void
00095 IntSet::normalize(Range* r, int n) {
00096 if (n > 0) {
00097
00098 {
00099 MinInc lt_mi;
00100 Support::quicksort<Range>(r, n, lt_mi);
00101 }
00102
00103 {
00104 int min = r[0].min;
00105 int max = r[0].max;
00106 int i = 1;
00107 int j = 0;
00108 while (i < n) {
00109 if (max+1 < r[i].min) {
00110 r[j].min = min; r[j].max = max; j++;
00111 min = r[i].min; max = r[i].max; i++;
00112 } else {
00113 max = std::max(max,r[i].max); i++;
00114 }
00115 }
00116 r[j].min = min; r[j].max = max;
00117 n=j+1;
00118 }
00119 IntSetObject* o = IntSetObject::allocate(n);
00120 unsigned int s = 0;
00121 for (int i=n; i--; ) {
00122 s += static_cast<unsigned int>(r[i].max-r[i].min+1);
00123 o->r[i]=r[i];
00124 }
00125 o->size = s;
00126 object(o);
00127 }
00128 }
00129
00130 void
00131 IntSet::init(const int r[], int n) {
00132 Range* dr = heap.alloc<Range>(n);
00133 for (int i=n; i--; ) {
00134 dr[i].min=r[i]; dr[i].max=r[i];
00135 }
00136 normalize(&dr[0],n);
00137 heap.free(dr,n);
00138 }
00139
00140 void
00141 IntSet::init(const int r[][2], int n) {
00142 Range* dr = heap.alloc<Range>(n);
00143 int j = 0;
00144 for (int i=n; i--; )
00145 if (r[i][0] <= r[i][1]) {
00146 dr[j].min=r[i][0]; dr[j].max=r[i][1]; j++;
00147 }
00148 normalize(&dr[0],j);
00149 heap.free(dr,n);
00150 }
00151
00152 void
00153 IntSet::init(int n, int m) {
00154 if (n <= m) {
00155 IntSetObject* o = IntSetObject::allocate(1);
00156 o->r[0].min = n; o->r[0].max = m;
00157 o->size = static_cast<unsigned int>(m - n + 1);
00158 object(o);
00159 }
00160 }
00161
00162 const IntSet IntSet::empty;
00163
00164 }
00165
00166
00167