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 #include <climits>
00041
00042 #ifdef _MSC_VER
00043
00044 #include <intrin.h>
00045
00046 #if defined(_M_IX86)
00047 #pragma intrinsic(_BitScanForward)
00048 #pragma intrinsic(__popcnt)
00049 #define GECODE_SUPPORT_MSVC_32
00050 #endif
00051
00052 #if defined(_M_X64) || defined(_M_IA64)
00053 #pragma intrinsic(_BitScanForward64)
00054 #pragma intrinsic(__popcnt64)
00055 #define GECODE_SUPPORT_MSVC_64
00056 #endif
00057
00058 #endif
00059
00060 namespace Gecode { namespace Support {
00061
00062 class RawBitSetBase;
00063
00065 class BitSetData {
00066 friend class RawBitSetBase;
00067 protected:
00068 #if defined(GECODE_SUPPORT_MSVC_32)
00069
00070 typedef unsigned long int Base;
00071 #else
00072
00073 typedef unsigned long long int Base;
00074 #endif
00075
00076 Base bits;
00077 public:
00079 static const unsigned int bpb =
00080 static_cast<unsigned int>(CHAR_BIT * sizeof(Base));
00082 void init(bool setbits=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;
00104 unsigned int ones(void) const;
00106 unsigned int zeroes(void) const;
00108 bool one(void) const;
00110 void a(BitSetData a);
00112 void a(BitSetData a, unsigned int i);
00114 static BitSetData a(BitSetData a, BitSetData b);
00116 void o(BitSetData a);
00118 void o(BitSetData a, unsigned int i);
00120 static BitSetData o(BitSetData a, BitSetData b);
00122 bool operator ==(BitSetData a) const;
00124 bool operator !=(BitSetData a) const;
00126 BitSetData operator ~(void) const;
00127 };
00128
00130 enum BitSetStatus {
00131 BSS_NONE,
00132 BSS_ALL,
00133 BSS_SOME
00134 };
00135
00137 class RawBitSetBase {
00138 protected:
00140 static const unsigned int bpb = BitSetData::bpb;
00142 BitSetData* data;
00143 private:
00145 RawBitSetBase(const RawBitSetBase&);
00147 RawBitSetBase& operator =(const RawBitSetBase&);
00148 public:
00150 RawBitSetBase(void);
00152 template<class A>
00153 RawBitSetBase(A& a, unsigned int sz, bool setbits=false);
00155 template<class A>
00156 RawBitSetBase(A& a, unsigned int sz, const RawBitSetBase& bs);
00158 template<class A>
00159 void allocate(A& a, unsigned int sz);
00161 template<class A>
00162 void init(A& a, unsigned int sz, bool setbits=false);
00164 void clearall(unsigned int sz, bool setbits=false);
00166 void copy(unsigned int sz, const RawBitSetBase& bs);
00168 bool get(unsigned int i) const;
00170 void set(unsigned int i);
00172 void clear(unsigned int i);
00174 unsigned int next(unsigned int i) const;
00176 BitSetStatus status(unsigned int sz) const;
00178 bool all(unsigned int sz) const;
00180 bool none(unsigned int sz) const;
00182 template<class A>
00183 void resize(A& a, unsigned int sz, unsigned int n, bool setbits=false);
00185 template<class A>
00186 void dispose(A& a, unsigned int sz);
00187 };
00188
00190 class BitSetBase : public RawBitSetBase {
00191 protected:
00193 unsigned int sz;
00194 private:
00196 BitSetBase(const BitSetBase&);
00198 BitSetBase& operator =(const BitSetBase&);
00199 public:
00201 BitSetBase(void);
00203 template<class A>
00204 BitSetBase(A& a, unsigned int s, bool setbits=false);
00206 template<class A>
00207 BitSetBase(A& a, const BitSetBase& bs);
00209 template<class A>
00210 void init(A& a, unsigned int s, bool setbits=false);
00212 void clearall(bool setbits=false);
00214 void copy(const BitSetBase& bs);
00216 unsigned int size(void) const;
00218 bool get(unsigned int i) const;
00220 void set(unsigned int i);
00222 void clear(unsigned int i);
00224 unsigned int next(unsigned int i) const;
00226 BitSetStatus status(void) const;
00228 bool all(void) const;
00230 bool none(void) const;
00232 template<class A>
00233 void resize(A& a, unsigned int n, bool setbits=false);
00235 template<class A>
00236 void dispose(A& a);
00237 };
00238
00239
00240
00241
00242
00243
00244
00245 forceinline void
00246 BitSetData::init(bool setbits) {
00247 bits = setbits ? ~static_cast<Base>(0) : static_cast<Base>(0);
00248 }
00249 forceinline unsigned int
00250 BitSetData::data(unsigned int s) {
00251 return s == 0 ? 0 : ((s-1) / bpb + 1);
00252 }
00253 forceinline bool
00254 BitSetData::operator ()(unsigned int i) const {
00255 return (bits >> i) != static_cast<Base>(0U);
00256 }
00257 forceinline bool
00258 BitSetData::get(unsigned int i) const {
00259 return (bits & (static_cast<Base>(1U) << i)) != static_cast<Base>(0U);
00260 }
00261 forceinline void
00262 BitSetData::set(unsigned int i) {
00263 bits |= (static_cast<Base>(1U) << i);
00264 }
00265 forceinline void
00266 BitSetData::clear(unsigned int i) {
00267 bits &= ~(static_cast<Base>(1U) << i);
00268 }
00269 forceinline unsigned int
00270 BitSetData::next(unsigned int i) const {
00271 assert(bits != static_cast<Base>(0));
00272 #if defined(GECODE_SUPPORT_MSVC_32)
00273 assert(bpb == 32);
00274 unsigned long int p;
00275 _BitScanForward(&p,bits >> i);
00276 return static_cast<unsigned int>(p)+i;
00277 #elif defined(GECODE_SUPPORT_MSVC_64)
00278 assert(bpb == 64);
00279 unsigned long int p;
00280 _BitScanForward64(&p,bits >> i);
00281 return static_cast<unsigned int>(p)+i;
00282 #elif defined(GECODE_HAS_BUILTIN_FFSLL)
00283 if (bpb == 64) {
00284 int p = __builtin_ffsll(bits >> i);
00285 assert(p > 0);
00286 return static_cast<unsigned int>(p-1)+i;
00287 }
00288 #else
00289 while (!get(i)) i++;
00290 return i;
00291 #endif
00292 }
00293 forceinline bool
00294 BitSetData::all(void) const {
00295 return bits == ~static_cast<Base>(0U);
00296 }
00297 forceinline bool
00298 BitSetData::all(unsigned int i) const {
00299 const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
00300 return (bits & mask) == mask;
00301 }
00302 forceinline bool
00303 BitSetData::none(void) const {
00304 return bits == static_cast<Base>(0U);
00305 }
00306 forceinline bool
00307 BitSetData::none(unsigned int i) const {
00308 const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
00309 return (bits & mask) == static_cast<Base>(0U);
00310 }
00311
00312 forceinline unsigned int
00313 BitSetData::ones(void) const {
00314 #if defined(GECODE_SUPPORT_MSVC_32)
00315 assert(bpb == 32);
00316 return static_cast<unsigned int>(__popcnt(bits));
00317 #elif defined(GECODE_SUPPORT_MSVC_64)
00318 assert(bpb == 64);
00319 return static_cast<unsigned int>(__popcnt64(bits));
00320 #elif defined(GECODE_HAS_BUILTIN_POPCOUNTLL)
00321 if (bpb == 64)
00322 return static_cast<unsigned int>(__builtin_popcountll(bits));
00323 #else
00324 const unsigned long long int m1 = 0x5555555555555555;
00325 const unsigned long long int m2 = 0x3333333333333333;
00326 const unsigned long long int m4 = 0x0f0f0f0f0f0f0f0f;
00327 unsigned long long int b = bits;
00328 b -= (b >> 1) & m1;
00329 b = (b & m2) + ((b >> 2) & m2);
00330 b = (b + (b >> 4)) & m4;
00331 b += b >> 8; b += b >> 16; b += b >> 32;
00332 return static_cast<unsigned int>(b & 0x7f);
00333 #endif
00334 }
00335 forceinline unsigned int
00336 BitSetData::zeroes(void) const {
00337 return bpb - ones();
00338 }
00339 forceinline bool
00340 BitSetData::one(void) const {
00341 return (bits & (bits - static_cast<Base>(1U))) ==
00342 static_cast<Base>(0U);
00343 }
00344
00345 forceinline void
00346 BitSetData::a(BitSetData a) {
00347 bits &= a.bits;
00348 }
00349 forceinline void
00350 BitSetData::a(BitSetData a, unsigned int i) {
00351 const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
00352 bits &= (a.bits & mask);
00353 }
00354 forceinline BitSetData
00355 BitSetData::a(BitSetData a, BitSetData b) {
00356 BitSetData ab;
00357 ab.bits = a.bits & b.bits;
00358 return ab;
00359 }
00360
00361 forceinline void
00362 BitSetData::o(BitSetData a) {
00363 bits |= a.bits;
00364 }
00365 forceinline void
00366 BitSetData::o(BitSetData a, unsigned int i) {
00367 const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
00368 bits |= (a.bits & mask);
00369 }
00370 forceinline BitSetData
00371 BitSetData::o(BitSetData a, BitSetData b) {
00372 BitSetData ab;
00373 ab.bits = a.bits | b.bits;
00374 return ab;
00375 }
00376
00377 forceinline BitSetData
00378 BitSetData::operator ~(void) const {
00379 BitSetData iv;
00380 iv.bits = ~bits;
00381 return iv;
00382 }
00383 forceinline bool
00384 BitSetData::operator ==(BitSetData a) const {
00385 return bits == a.bits;
00386 }
00387 forceinline bool
00388 BitSetData::operator !=(BitSetData a) const {
00389 return bits != a.bits;
00390 }
00391
00392
00393
00394
00395
00396
00397
00398 forceinline bool
00399 RawBitSetBase::get(unsigned int i) const {
00400 return data[i / bpb].get(i % bpb);
00401 }
00402 forceinline void
00403 RawBitSetBase::set(unsigned int i) {
00404 data[i / bpb].set(i % bpb);
00405 }
00406 forceinline void
00407 RawBitSetBase::clear(unsigned int i) {
00408 data[i / bpb].clear(i % bpb);
00409 }
00410
00411 template<class A>
00412 void
00413 RawBitSetBase::resize(A& a, unsigned int sz, unsigned int n, bool setbits) {
00414 if (n>sz) {
00415 data = a.template realloc<BitSetData>(data,BitSetData::data(sz+1),
00416 BitSetData::data(n+1));
00417 for (unsigned int i=BitSetData::data(sz)+1;
00418 i<BitSetData::data(n+1); i++) {
00419 data[i].init(setbits);
00420 }
00421 for (unsigned int i=(sz%bpb); i<bpb; i++)
00422 if (setbits)
00423 data[sz / bpb].set(i);
00424 else
00425 data[sz / bpb].clear(i);
00426 }
00427 set(n);
00428 }
00429
00430 template<class A>
00431 forceinline void
00432 RawBitSetBase::dispose(A& a, unsigned int sz) {
00433 a.template free<BitSetData>(data,BitSetData::data(sz+1));
00434 }
00435
00436 forceinline
00437 RawBitSetBase::RawBitSetBase(void)
00438 : data(NULL) {}
00439
00440 template<class A>
00441 forceinline
00442 RawBitSetBase::RawBitSetBase(A& a, unsigned int sz, bool setbits)
00443 : data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
00444 for (unsigned int i=0U; i<BitSetData::data(sz+1); i++)
00445 data[i].init(setbits);
00446
00447 set(sz);
00448 }
00449
00450 template<class A>
00451 forceinline
00452 RawBitSetBase::RawBitSetBase(A& a, unsigned int sz, const RawBitSetBase& bs)
00453 : data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
00454 for (unsigned int i=0U; i<BitSetData::data(sz+1); i++)
00455 data[i] = bs.data[i];
00456
00457 set(sz);
00458 }
00459
00460 template<class A>
00461 forceinline void
00462 RawBitSetBase::allocate(A& a, unsigned int sz) {
00463 assert(data == NULL);
00464 data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
00465 }
00466
00467 template<class A>
00468 forceinline void
00469 RawBitSetBase::init(A& a, unsigned int sz, bool setbits) {
00470 assert(data == NULL);
00471 data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
00472 for (unsigned int i=0U; i<BitSetData::data(sz+1); i++)
00473 data[i].init(setbits);
00474
00475 set(sz);
00476 }
00477
00478 forceinline void
00479 RawBitSetBase::copy(unsigned int sz, const RawBitSetBase& bs) {
00480 for (unsigned int i=0U; i<BitSetData::data(sz+1); i++)
00481 data[i] = bs.data[i];
00482 }
00483
00484 forceinline void
00485 RawBitSetBase::clearall(unsigned int sz, bool setbits) {
00486 for (unsigned int i=0U; i<BitSetData::data(sz+1); i++)
00487 data[i].init(setbits);
00488 }
00489
00490 forceinline unsigned int
00491 RawBitSetBase::next(unsigned int i) const {
00492 unsigned int pos = i / bpb;
00493 unsigned int bit = i % bpb;
00494 if (data[pos](bit))
00495 return pos * bpb + data[pos].next(bit);
00496
00497 do {
00498 pos++;
00499 } while (!data[pos]());
00500 return pos * bpb + data[pos].next();
00501 }
00502
00503 forceinline BitSetStatus
00504 RawBitSetBase::status(unsigned int sz) const {
00505 unsigned int pos = sz / bpb;
00506 unsigned int bits = sz % bpb;
00507 if (pos > 0) {
00508 if (data[0].all()) {
00509 for (unsigned int i=1; i<pos; i++)
00510 if (!data[i].all())
00511 return BSS_SOME;
00512 return data[pos].all(bits) ? BSS_ALL : BSS_SOME;
00513 } else if (data[0].none()) {
00514 for (unsigned int i=1; i<pos; i++)
00515 if (!data[i].none())
00516 return BSS_SOME;
00517 return data[pos].none(bits) ? BSS_NONE : BSS_SOME;
00518 } else {
00519 return BSS_SOME;
00520 }
00521 }
00522 if (data[0].all(bits))
00523 return BSS_ALL;
00524 if (data[0].none(bits))
00525 return BSS_NONE;
00526 return BSS_SOME;
00527 }
00528
00529 forceinline bool
00530 RawBitSetBase::all(unsigned int sz) const {
00531 return status(sz) == BSS_ALL;
00532 }
00533
00534 forceinline bool
00535 RawBitSetBase::none(unsigned int sz) const {
00536 return status(sz) == BSS_NONE;
00537 }
00538
00539
00540 template<class A>
00541 void
00542 BitSetBase::resize(A& a, unsigned int n, bool setbits) {
00543 RawBitSetBase::resize(a,sz,n,setbits); sz=n;
00544 }
00545
00546 template<class A>
00547 forceinline void
00548 BitSetBase::dispose(A& a) {
00549 RawBitSetBase::dispose(a,sz);
00550 }
00551
00552 forceinline
00553 BitSetBase::BitSetBase(void)
00554 : sz(0U) {}
00555
00556 template<class A>
00557 forceinline
00558 BitSetBase::BitSetBase(A& a, unsigned int s, bool setbits)
00559 : RawBitSetBase(a,s,setbits), sz(s) {}
00560
00561 template<class A>
00562 forceinline
00563 BitSetBase::BitSetBase(A& a, const BitSetBase& bs)
00564 : RawBitSetBase(a,bs.sz,bs), sz(bs.sz) {}
00565
00566 template<class A>
00567 forceinline void
00568 BitSetBase::init(A& a, unsigned int s, bool setbits) {
00569 assert(sz == 0);
00570 RawBitSetBase::init(a,s,setbits); sz=s;
00571 }
00572
00573 forceinline void
00574 BitSetBase::copy(const BitSetBase& bs) {
00575 assert(sz == bs.sz);
00576 RawBitSetBase::copy(sz,bs);
00577 }
00578
00579 forceinline void
00580 BitSetBase::clearall(bool setbits) {
00581 RawBitSetBase::clearall(sz,setbits);
00582 }
00583
00584 forceinline unsigned int
00585 BitSetBase::size(void) const {
00586 return sz;
00587 }
00588
00589 forceinline bool
00590 BitSetBase::get(unsigned int i) const {
00591 assert(i < sz);
00592 return RawBitSetBase::get(i);
00593 }
00594 forceinline void
00595 BitSetBase::set(unsigned int i) {
00596 assert(i < sz);
00597 RawBitSetBase::set(i);
00598 }
00599 forceinline void
00600 BitSetBase::clear(unsigned int i) {
00601 assert(i < sz);
00602 RawBitSetBase::clear(i);
00603 }
00604
00605 forceinline unsigned int
00606 BitSetBase::next(unsigned int i) const {
00607 assert(i <= sz);
00608 return RawBitSetBase::next(i);
00609 }
00610
00611 forceinline BitSetStatus
00612 BitSetBase::status(void) const {
00613 return RawBitSetBase::status(sz);
00614 }
00615
00616 forceinline bool
00617 BitSetBase::all(void) const {
00618 return RawBitSetBase::all(sz);
00619 }
00620
00621 forceinline bool
00622 BitSetBase::none(void) const {
00623 return RawBitSetBase::none(sz);
00624 }
00625
00626 }}
00627
00628 #ifdef GECODE_SUPPORT_MSVC_32
00629 #undef GECODE_SUPPORT_MSVC_32
00630 #endif
00631 #ifdef GECODE_SUPPORT_MSVC_64
00632 #undef GECODE_SUPPORT_MSVC_64
00633 #endif
00634
00635