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
00039
00040
00041
00042 #include <climits>
00043
00044 #ifdef _MSC_VER
00045
00046 #include <intrin.h>
00047
00048 #if defined(_M_IX86)
00049 #pragma intrinsic(_BitScanForward)
00050 #define GECODE_SUPPORT_MSVC_32
00051 #endif
00052
00053 #if defined(_M_X64) || defined(_M_IA64)
00054 #pragma intrinsic(_BitScanForward64)
00055 #define GECODE_SUPPORT_MSVC_64
00056 #endif
00057
00058 #endif
00059
00060 namespace Gecode { namespace Support {
00061
00062 class BitSetBase;
00063
00065 class BitSetData {
00066 friend class BitSetBase;
00067 protected:
00068 #ifdef GECODE_SUPPORT_MSVC_64
00069
00070 typedef unsigned __int64 Base;
00071 #else
00072
00073 typedef unsigned long int Base;
00074 #endif
00075
00076 Base bits;
00078 static const unsigned int bpb =
00079 static_cast<unsigned int>(CHAR_BIT * sizeof(Base));
00080 public:
00082 void init(bool set=false);
00084 static unsigned int data(unsigned int s);
00086 bool operator ()(unsigned int i=0U) const;
00088 bool get(unsigned int i) const;
00090 void set(unsigned int i);
00092 void clear(unsigned int i);
00094 unsigned int next(unsigned int i=0U) const;
00096 bool all(void) const;
00098 bool all(unsigned int i) const;
00100 bool none(void) const;
00102 bool none(unsigned int i) const;
00103 };
00104
00106 enum BitSetStatus {
00107 BSS_NONE,
00108 BSS_ALL,
00109 BSS_SOME
00110 };
00111
00113 class BitSetBase {
00114 protected:
00116 static const unsigned int bpb = BitSetData::bpb;
00118 unsigned int sz;
00120 BitSetData* data;
00122 bool _get(unsigned int i) const;
00124 void _set(unsigned int i);
00125 private:
00127 BitSetBase(const BitSetBase&);
00129 BitSetBase& operator =(const BitSetBase&);
00130 public:
00132 BitSetBase(void);
00134 template<class A>
00135 BitSetBase(A& a, unsigned int s, bool set=false);
00137 template<class A>
00138 BitSetBase(A& a, const BitSetBase& bs);
00140 template<class A>
00141 void init(A& a, unsigned int s, bool set=false);
00143 unsigned int size(void) const;
00145 bool get(unsigned int i) const;
00147 void set(unsigned int i);
00149 void clear(unsigned int i);
00151 unsigned int next(unsigned int i) const;
00153 BitSetStatus status(void) const;
00155 template<class A>
00156 void resize(A& a, unsigned int n, bool set=false);
00158 template<class A>
00159 void dispose(A& a);
00160 };
00161
00162
00163
00164
00165
00166
00167
00168 forceinline void
00169 BitSetData::init(bool set) {
00170 bits = set ? ~static_cast<Base>(0) : static_cast<Base>(0);
00171 }
00172 forceinline unsigned int
00173 BitSetData::data(unsigned int s) {
00174 return s == 0 ? 0 : ((s-1) / bpb + 1);
00175 }
00176 forceinline bool
00177 BitSetData::operator ()(unsigned int i) const {
00178 return (bits >> i) != static_cast<Base>(0U);
00179 }
00180 forceinline bool
00181 BitSetData::get(unsigned int i) const {
00182 return (bits & (static_cast<Base>(1U) << i)) != static_cast<Base>(0U);
00183 }
00184 forceinline void
00185 BitSetData::set(unsigned int i) {
00186 bits |= (static_cast<Base>(1U) << i);
00187 }
00188 forceinline void
00189 BitSetData::clear(unsigned int i) {
00190 bits &= ~(static_cast<Base>(1U) << i);
00191 }
00192 forceinline unsigned int
00193 BitSetData::next(unsigned int i) const {
00194 assert(bits != static_cast<Base>(0));
00195 #if defined(GECODE_SUPPORT_MSVC_32)
00196 assert(bpb == 32);
00197 unsigned long int p;
00198 _BitScanForward(&p,bits >> i);
00199 return static_cast<unsigned int>(p)+i;
00200 #elif defined(GECODE_SUPPORT_MSVC_64)
00201 assert(bpb == 64);
00202 unsigned long int p;
00203 _BitScanForward64(&p,bits >> i);
00204 return static_cast<unsigned int>(p)+i;
00205 #elif defined(GECODE_HAS_BUILTIN_FFSL)
00206 if ((bpb == 32) || (bpb == 64)) {
00207 int p = __builtin_ffsl(bits >> i);
00208 assert(p > 0);
00209 return static_cast<unsigned int>(p-1)+i;
00210 }
00211 #else
00212 while (!get(i)) i++;
00213 return i;
00214 #endif
00215 }
00216 forceinline bool
00217 BitSetData::all(void) const {
00218 return bits == ~static_cast<Base>(0U);
00219 }
00220 forceinline bool
00221 BitSetData::all(unsigned int i) const {
00222 const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
00223 return (bits & mask) == mask;
00224 }
00225 forceinline bool
00226 BitSetData::none(void) const {
00227 return bits == static_cast<Base>(0U);
00228 }
00229 forceinline bool
00230 BitSetData::none(unsigned int i) const {
00231 const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
00232 return (bits & mask) == static_cast<Base>(0U);
00233 }
00234
00235
00236
00237
00238
00239
00240
00241
00242 forceinline bool
00243 BitSetBase::_get(unsigned int i) const {
00244 return data[i / bpb].get(i % bpb);
00245 }
00246 forceinline void
00247 BitSetBase::_set(unsigned int i) {
00248 data[i / bpb].set(i % bpb);
00249 }
00250
00251 template<class A>
00252 void
00253 BitSetBase::resize(A& a, unsigned int n, bool set) {
00254 if (n>sz) {
00255 data = a.template realloc<BitSetData>(data,BitSetData::data(sz+1),
00256 BitSetData::data(n+1));
00257 for (unsigned int i=BitSetData::data(sz)+1;
00258 i<BitSetData::data(n+1); i++) {
00259 data[i].init(set);
00260 }
00261 for (unsigned int i=(sz%bpb); i<bpb; i++)
00262 if (set)
00263 data[sz / bpb].set(i);
00264 else
00265 data[sz / bpb].clear(i);
00266 }
00267 sz = n; _set(sz);
00268 }
00269
00270 template<class A>
00271 forceinline void
00272 BitSetBase::dispose(A& a) {
00273 a.template free<BitSetData>(data,BitSetData::data(sz+1));
00274 }
00275
00276 forceinline
00277 BitSetBase::BitSetBase(void)
00278 : sz(0), data(NULL) {}
00279
00280 template<class A>
00281 forceinline
00282 BitSetBase::BitSetBase(A& a, unsigned int s, bool set)
00283 : sz(s),
00284 data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
00285 for (unsigned int i = BitSetData::data(sz+1); i--; )
00286 data[i].init(set);
00287
00288 _set(sz);
00289 }
00290
00291 template<class A>
00292 forceinline
00293 BitSetBase::BitSetBase(A& a, const BitSetBase& bs)
00294 : sz(bs.sz),
00295 data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
00296 for (unsigned int i = BitSetData::data(sz+1); i--; )
00297 data[i] = bs.data[i];
00298
00299 _set(sz);
00300 }
00301
00302 template<class A>
00303 forceinline void
00304 BitSetBase::init(A& a, unsigned int s, bool set) {
00305 assert((sz == 0) && (data == NULL));
00306 sz=s; data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
00307 for (unsigned int i=BitSetData::data(sz+1); i--; )
00308 data[i].init(set);
00309
00310 _set(sz);
00311 }
00312
00313 forceinline unsigned int
00314 BitSetBase::size(void) const {
00315 return sz;
00316 }
00317
00318 forceinline bool
00319 BitSetBase::get(unsigned int i) const {
00320 assert(i < sz);
00321 return _get(i);
00322 }
00323 forceinline void
00324 BitSetBase::set(unsigned int i) {
00325 assert(i < sz);
00326 _set(i);
00327 }
00328 forceinline void
00329 BitSetBase::clear(unsigned int i) {
00330 assert(i < sz);
00331 data[i / bpb].clear(i % bpb);
00332 }
00333
00334 forceinline unsigned int
00335 BitSetBase::next(unsigned int i) const {
00336 assert(i <= sz);
00337 unsigned int pos = i / bpb;
00338 unsigned int bit = i % bpb;
00339 if (data[pos](bit))
00340 return pos * bpb + data[pos].next(bit);
00341
00342 do {
00343 pos++;
00344 } while (!data[pos]());
00345 return pos * bpb + data[pos].next();
00346 }
00347
00348 forceinline BitSetStatus
00349 BitSetBase::status(void) const {
00350 unsigned int pos = sz / bpb;
00351 unsigned int bits = sz % bpb;
00352 if (pos > 0) {
00353 if (data[0].all()) {
00354 for (unsigned int i=1; i<pos; i++)
00355 if (!data[i].all())
00356 return BSS_SOME;
00357 return data[pos].all(bits) ? BSS_ALL : BSS_SOME;
00358 } else if (data[0].none()) {
00359 for (unsigned int i=1; i<pos; i++)
00360 if (!data[i].none())
00361 return BSS_SOME;
00362 return data[pos].none(bits) ? BSS_NONE : BSS_SOME;
00363 } else {
00364 return BSS_SOME;
00365 }
00366 }
00367 if (data[0].all(bits))
00368 return BSS_ALL;
00369 if (data[0].none(bits))
00370 return BSS_NONE;
00371 return BSS_SOME;
00372 }
00373
00374 }}
00375
00376 #ifdef GECODE_SUPPORT_MSVC_32
00377 #undef GECODE_SUPPORT_MSVC_32
00378 #endif
00379 #ifdef GECODE_SUPPORT_MSVC_64
00380 #undef GECODE_SUPPORT_MSVC_64
00381 #endif
00382
00383
00384