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 = 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
00077 MinInc lt_mi;
00078 Support::quicksort<Range>(r, n, lt_mi);
00079
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
00153