int-set-1.hpp
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 <sstream>
00035
00036 namespace Gecode {
00037
00038
00039
00040
00041
00042 forceinline
00043 IntSet::IntSet(void) {}
00044
00052 template<class I>
00053 class IntSetInit {
00054 public:
00056 static void init(IntSet& s, I& i) {
00057 Support::DynamicArray<IntSet::Range,Heap> d(heap);
00058 int n=0;
00059 unsigned int size = 0;
00060 while (i()) {
00061 d[n].min = i.min(); d[n].max = i.max(); size += i.width();
00062 ++n; ++i;
00063 }
00064 if (n > 0) {
00065 IntSet::IntSetObject* o = IntSet::IntSetObject::allocate(n);
00066 for (int j=n; j--; )
00067 o->r[j]=d[j];
00068 o->size = size;
00069 s.object(o);
00070 }
00071 }
00072 };
00073
00075 template<>
00076 class IntSetInit<IntSet> {
00077 public:
00078 static void init(IntSet& s, const IntSet& i) {
00079 s.object(i.object());
00080 }
00081 };
00082
00084 template<class I>
00085 IntSet::IntSet(I& i) {
00086 IntSetInit<I>::init(*this,i);
00087 }
00088
00090 template<class I>
00091 IntSet::IntSet(const I& i) {
00092 IntSetInit<I>::init(*this,i);
00093 }
00094
00095 forceinline
00096 IntSet::IntSet(const int r[][2], int n) {
00097 init(r,n);
00098 }
00099
00100 forceinline
00101 IntSet::IntSet(const int r[], int n) {
00102 init(r,n);
00103 }
00104
00105 forceinline
00106 IntSet::IntSet(int n, int m) {
00107 init(n,m);
00108 }
00109
00110 forceinline int
00111 IntSet::min(int i) const {
00112 assert(object() != NULL);
00113 return static_cast<IntSetObject*>(object())->r[i].min;
00114 }
00115
00116 forceinline int
00117 IntSet::max(int i) const {
00118 assert(object() != NULL);
00119 return static_cast<IntSetObject*>(object())->r[i].max;
00120 }
00121
00122 forceinline unsigned int
00123 IntSet::width(int i) const {
00124 assert(object() != NULL);
00125 IntSetObject* o = static_cast<IntSetObject*>(object());
00126 return static_cast<unsigned int>(o->r[i].max-o->r[i].min)+1;
00127 }
00128
00129 forceinline int
00130 IntSet::ranges(void) const {
00131 IntSetObject* o = static_cast<IntSetObject*>(object());
00132 return (o == NULL) ? 0 : o->n;
00133 }
00134
00135 forceinline bool
00136 IntSet::in(int n) const {
00137 IntSetObject* o = static_cast<IntSetObject*>(object());
00138 if ((o == NULL) || (n < o->r[0].min) || (n > o->r[o->n-1].max))
00139 return false;
00140 else
00141 return o->in(n);
00142 }
00143
00144 forceinline int
00145 IntSet::min(void) const {
00146 IntSetObject* o = static_cast<IntSetObject*>(object());
00147 return (o == NULL) ? Int::Limits::max : o->r[0].min;
00148 }
00149
00150 forceinline int
00151 IntSet::max(void) const {
00152 IntSetObject* o = static_cast<IntSetObject*>(object());
00153 return (o == NULL) ? Int::Limits::min : o->r[o->n-1].max;
00154 }
00155
00156 forceinline unsigned int
00157 IntSet::size(void) const {
00158 IntSetObject* o = static_cast<IntSetObject*>(object());
00159 return (o == NULL) ? 0 : o->size;
00160 }
00161
00162 forceinline unsigned int
00163 IntSet::width(void) const {
00164 return static_cast<unsigned int>(max()-min()+1);
00165 }
00166
00167
00168
00169
00170
00171
00172
00173 forceinline
00174 IntSetRanges::IntSetRanges(void) {}
00175 forceinline
00176 void
00177 IntSetRanges::init(const IntSet& s) {
00178 int n = s.ranges();
00179 if (n > 0) {
00180 i = &static_cast<IntSet::IntSetObject*>(s.object())->r[0]; e = i+n;
00181 } else {
00182 i = e = NULL;
00183 }
00184 }
00185 forceinline
00186 IntSetRanges::IntSetRanges(const IntSet& s) { init(s); }
00187
00188
00189 forceinline void
00190 IntSetRanges::operator ++(void) {
00191 i++;
00192 }
00193 forceinline bool
00194 IntSetRanges::operator ()(void) const {
00195 return i<e;
00196 }
00197
00198 forceinline int
00199 IntSetRanges::min(void) const {
00200 return i->min;
00201 }
00202 forceinline int
00203 IntSetRanges::max(void) const {
00204 return i->max;
00205 }
00206 forceinline unsigned int
00207 IntSetRanges::width(void) const {
00208 return static_cast<unsigned int>(i->max - i->min) + 1;
00209 }
00210
00211
00212
00213
00214
00215 forceinline
00216 IntSetValues::IntSetValues(void) {}
00217
00218 forceinline
00219 IntSetValues::IntSetValues(const IntSet& s) {
00220 IntSetRanges r(s);
00221 Iter::Ranges::ToValues<IntSetRanges>::init(r);
00222 }
00223
00224 forceinline void
00225 IntSetValues::init(const IntSet& s) {
00226 IntSetRanges r(s);
00227 Iter::Ranges::ToValues<IntSetRanges>::init(r);
00228 }
00229
00230 template<class Char, class Traits>
00231 std::basic_ostream<Char,Traits>&
00232 operator <<(std::basic_ostream<Char,Traits>& os, const IntSet& is) {
00233 std::basic_ostringstream<Char,Traits> s;
00234 s.copyfmt(os); s.width(0);
00235 s << '{';
00236 for (int i = 0; i < is.ranges(); ) {
00237 int min = is.min(i);
00238 int max = is.max(i);
00239 if (min == max)
00240 s << min;
00241 else
00242 s << min << ".." << max;
00243 i++;
00244 if (i < is.ranges())
00245 s << ',';
00246 }
00247 s << '}';
00248 return os << s.str();
00249 }
00250
00251 }
00252
00253
00254