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