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 #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 IntSet::IntSetObject::~IntSetObject(void) {
00067 heap.free<Range>(r,n);
00068 }
00069
00071 class IntSet::MinInc {
00072 public:
00073 bool operator ()(const Range &x, const Range &y);
00074 };
00075
00076 forceinline bool
00077 IntSet::MinInc::operator ()(const Range &x, const Range &y) {
00078 return x.min < y.min;
00079 }
00080
00081 void
00082 IntSet::normalize(Range* r, int n) {
00083 if (n > 0) {
00084
00085 {
00086 MinInc lt_mi;
00087 Support::quicksort<Range>(r, n, lt_mi);
00088 }
00089
00090 {
00091 int min = r[0].min;
00092 int max = r[0].max;
00093 int i = 1;
00094 int j = 0;
00095 while (i < n) {
00096 if (max+1 < r[i].min) {
00097 r[j].min = min; r[j].max = max; j++;
00098 min = r[i].min; max = r[i].max; i++;
00099 } else {
00100 max = std::max(max,r[i].max); i++;
00101 }
00102 }
00103 r[j].min = min; r[j].max = max;
00104 n=j+1;
00105 }
00106 IntSetObject* o = IntSetObject::allocate(n);
00107 unsigned int s = 0;
00108 for (int i=n; i--; ) {
00109 s += static_cast<unsigned int>(r[i].max-r[i].min+1);
00110 o->r[i]=r[i];
00111 }
00112 o->size = s;
00113 object(o);
00114 }
00115 }
00116
00117 void
00118 IntSet::init(const int r[], int n) {
00119 Range* dr = heap.alloc<Range>(n);
00120 for (int i=n; i--; ) {
00121 dr[i].min=r[i]; dr[i].max=r[i];
00122 }
00123 normalize(&dr[0],n);
00124 heap.free(dr,n);
00125 }
00126
00127 void
00128 IntSet::init(const int r[][2], int n) {
00129 Range* dr = heap.alloc<Range>(n);
00130 int j = 0;
00131 for (int i=n; i--; )
00132 if (r[i][0] <= r[i][1]) {
00133 dr[j].min=r[i][0]; dr[j].max=r[i][1]; j++;
00134 }
00135 normalize(&dr[0],j);
00136 heap.free(dr,n);
00137 }
00138
00139 void
00140 IntSet::init(int n, int m) {
00141 if (n <= m) {
00142 IntSetObject* o = IntSetObject::allocate(1);
00143 o->r[0].min = n; o->r[0].max = m;
00144 o->size = static_cast<unsigned int>(m - n + 1);
00145 object(o);
00146 }
00147 }
00148
00149 const IntSet IntSet::empty;
00150
00151 }
00152
00153
00154