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