16 #ifndef OR_TOOLS_UTIL_BITSET_H_
17 #define OR_TOOLS_UTIL_BITSET_H_
43 const uint64 m1 = uint64_t{0x5555555555555555};
44 const uint64 m2 = uint64_t{0x3333333333333333};
45 const uint64 m4 = uint64_t{0x0F0F0F0F0F0F0F0F};
46 const uint64 h01 = uint64_t{0x0101010101010101};
48 n = (n & m2) + ((n >> 2) & m2);
49 n = (n + (n >> 4)) & m4;
54 n -= (n >> 1) & 0x55555555UL;
55 n = (n & 0x33333333) + ((n >> 2) & 0x33333333UL);
56 n = (n + (n >> 4)) & 0x0F0F0F0FUL;
59 return n & 0x0000003FUL;
70 #define USE_DEBRUIJN true
71 #if defined(__GNUC__) || defined(__llvm__)
72 #define USE_FAST_LEAST_SIGNIFICANT_BIT true
75 #if defined(USE_FAST_LEAST_SIGNIFICANT_BIT)
76 inline int LeastSignificantBitPosition64Fast(
uint64 n) {
77 return n == 0 ? 0 : __builtin_ctzll(n);
82 static const uint64 kSeq = uint64_t{0x0218a392dd5fb34f};
83 static const int kTab[64] = {
85 0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 52, 20, 58,
86 5, 17, 26, 56, 15, 38, 29, 40, 10, 49, 53, 31, 21, 34, 59, 42,
87 63, 6, 12, 18, 24, 27, 51, 57, 16, 55, 37, 39, 48, 30, 33, 41,
88 62, 11, 23, 50, 54, 36, 47, 32, 61, 22, 35, 46, 60, 45, 44, 43,
90 return kTab[((n & (~n + 1)) * kSeq) >> 58];
96 if (n & 0x00000000FFFFFFFFLL) {
101 if (n & 0x000000000000FFFFLL) {
106 if (n & 0x00000000000000FFLL) {
111 if (n & 0x000000000000000FLL) {
116 if (n & 0x0000000000000003LL) {
121 if (n & 0x0000000000000001LL) {
129 #ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
130 return LeastSignificantBitPosition64Fast(n);
131 #elif defined(USE_DEBRUIJN)
138 #if defined(USE_FAST_LEAST_SIGNIFICANT_BIT)
139 inline int LeastSignificantBitPosition32Fast(
uint32 n) {
140 return n == 0 ? 0 : __builtin_ctzl(n);
145 static const uint32 kSeq = 0x077CB531U;
146 static const int kTab[32] = {
147 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20,
148 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19,
149 16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
150 return kTab[((n & (~n + 1)) * kSeq) >> 27];
154 if (n == 0)
return 0;
156 if (n & 0x0000FFFFL) {
161 if (n & 0x000000FFL) {
166 if (n & 0x0000000FL) {
171 if (n & 0x00000003L) {
176 if (n & 0x00000001L) {
184 #ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
185 return LeastSignificantBitPosition32Fast(n);
186 #elif defined(USE_DEBRUIJN)
194 #if USE_FAST_LEAST_SIGNIFICANT_BIT
195 inline int MostSignificantBitPosition64Fast(
uint64 n) {
198 const int offset = __builtin_clzll(1);
199 return n == 0 ? 0 : (offset - __builtin_clzll(n));
232 #ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
233 return MostSignificantBitPosition64Fast(n);
239 #if USE_FAST_LEAST_SIGNIFICANT_BIT
240 inline int MostSignificantBitPosition32Fast(
uint32 n) {
244 const int offset = __builtin_clzl(1);
245 return n == 0 ? 0 : (offset - __builtin_clzl(n));
274 #ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
275 return MostSignificantBitPosition32Fast(n);
282 #undef USE_FAST_LEAST_SIGNIFICANT_BIT
409 template <
typename IndexType =
int64>
412 Bitset64() : size_(), data_(), end_(*this, true) {}
414 : size_(Value(
size) > 0 ?
size : IndexType(0)),
419 IndexType
size()
const {
return size_; }
431 size_ = Value(
size) > 0 ?
size : IndexType(0);
438 size_ = Value(
size) > 0 ?
size : IndexType(0);
443 const size_t bit_length =
static_cast<size_t>(
BitLength64(Value(size_)));
444 const size_t to_clear =
std::min(data_.size(), bit_length);
445 data_.resize(bit_length, 0);
446 memset(data_.data(), 0, to_clear *
sizeof(
int64));
509 data_[offset] = other.data_[offset];
515 template <
typename OtherIndexType>
517 const int64 min_size =
std::min(data_.size(), other.data_.size());
518 if (min_size == 0)
return;
519 const uint64 last_common_bucket = data_[min_size - 1];
520 memcpy(data_.data(), other.data_.data(), min_size *
sizeof(
uint64));
521 if (data_.size() >= other.data_.size()) {
524 data_[min_size - 1] &= ~bitmask;
525 data_[min_size - 1] |= (bitmask & last_common_bucket);
530 template <
typename OtherIndexType>
533 memcpy(data_.data(), other.data_.data(), data_.size() *
sizeof(
uint64));
540 const int min_size =
std::min(data_.size(), other.data_.size());
541 for (
int i = 0; i < min_size; ++i) {
542 data_[i] &= other.data_[i];
544 for (
int i = min_size; i < data_.size(); ++i) {
553 const int min_size =
std::min(data_.size(), other.data_.size());
554 for (
int i = 0; i < min_size; ++i) {
555 data_[i] |= other.data_[i];
566 : bitset_(data_), index_(0), base_index_(0), current_(0) {
567 if (bitset_.data_.empty()) {
570 current_ = bitset_.data_[0];
576 bool Ok()
const {
return index_ != -1; }
581 return IndexType(index_);
589 const int size = bitset_.data_.size();
592 }
while (bucket <
size && bitset_.data_[bucket] == 0);
593 if (bucket ==
size) {
597 current_ = bitset_.data_[bucket];
603 current_ &= current_ - 1;
608 : bitset_(data_), index_(0), base_index_(0), current_(0) {
609 if (at_end || bitset_.data_.empty()) {
612 current_ = bitset_.data_[0];
617 return index_ != other.index_;
619 IndexType
operator*()
const {
return IndexType(index_); }
644 DCHECK_EQ(data_.size(), other1.data_.size());
645 DCHECK_EQ(data_.size(), other2.data_.size());
646 DCHECK(use1 == 0 || use1 == 1);
647 DCHECK(use2 == 0 || use2 == 1);
650 data_[bucket] ^= ((1ull << pos) & data_[bucket]) ^
651 ((use1 << pos) & other1.data_[bucket]) ^
652 ((use2 << pos) & other2.data_[bucket]);
658 for (IndexType i(0); i <
size(); ++i) {
659 output +=
IsSet(i) ?
"1" :
"0";
670 std::vector<uint64> data_;
676 template <
class OtherIndexType>
687 : size_(size), top_(-1), data_(
BitLength64(size), 0) {}
713 int bucket_index =
static_cast<int>(
BitOffset64(i));
715 for (--bucket_index; bucket_index >= 0; --bucket_index) {
721 int Top()
const {
return top_; }
726 int bucket_index =
static_cast<int>(
BitOffset64(top_));
729 if (bucket_index == 0) {
733 bucket = data_[--bucket_index];
739 top_ =
static_cast<int>(
BitShift64(bucket_index) +
746 std::vector<uint64> data_;
751 template <
typename IntType>
752 inline int64 Bitset64<IntType>::Value(IntType
input)
const {
754 return input.value();
764 template <
typename IntegerType =
int64>
769 IntegerType
size()
const {
return bitset_.size(); }
771 for (
const IntegerType i : to_clear_) bitset_.ClearBucket(i);
780 const int kSparseThreshold = 300;
781 if (to_clear_.size() * kSparseThreshold < size) {
783 bitset_.Resize(size);
785 bitset_.ClearAndResize(size);
790 if (size < bitset_.size()) {
792 for (IntegerType
index : to_clear_) {
794 to_clear_[new_index] =
index;
798 to_clear_.resize(new_index);
800 bitset_.Resize(size);
804 if (!bitset_[
index]) {
806 to_clear_.push_back(
index);
811 return to_clear_.size();
832 std::vector<IntegerType> to_clear_;
#define DCHECK_LE(val1, val2)
#define DCHECK_NE(val1, val2)
#define CHECK_GE(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
void IncreaseSize(int size)
void ClearAndResize(int size)
Iterator(const Bitset64 &data_)
Iterator(const Bitset64 &data_, bool at_end)
bool operator!=(const Iterator &other) const
IndexType operator*() const
void ClearAndResize(IndexType size)
void ClearBucket(IndexType i)
void Set(IndexType i, bool value)
void SetContentFromBitsetOfSameSize(const Bitset64< OtherIndexType > &other)
void SetBitFromOtherBitSets(IndexType i, const Bitset64< IndexType > &other1, uint64 use1, const Bitset64< IndexType > &other2, uint64 use2)
void Union(const Bitset64< IndexType > &other)
std::string DebugString() const
void SetContentFromBitset(const Bitset64< OtherIndexType > &other)
void Intersection(const Bitset64< IndexType > &other)
void Resize(IndexType size)
bool IsSet(IndexType i) const
void ClearTwoBits(IndexType i)
void CopyBucket(const Bitset64< IndexType > &other, IndexType i)
bool operator[](IndexType i) const
bool AreOneOfTwoBitsSet(IndexType i) const
void PushBack(bool value)
SparseBitset(IntegerType size)
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
void Set(IntegerType index)
int NumberOfSetCallsWithDifferentArguments() const
void Clear(IntegerType index)
void Resize(IntegerType size)
bool operator[](IntegerType index) const
void ClearAndResize(IntegerType size)
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
uint64 BitShift64(uint64 v)
int LeastSignificantBitPosition64(uint64 n)
uint32 BitCount32(uint32 n)
uint32 BitPos64(uint64 pos)
void SetBit32(uint32 *const bitset, uint32 pos)
int LeastSignificantBitPosition64Default(uint64 n)
uint32 LeastSignificantBitWord32(uint32 n)
uint64 IntervalUp64(uint64 s)
int MostSignificantBitPosition64(uint64 n)
uint32 BitShift32(uint32 v)
uint64 BitCount64(uint64 n)
uint32 BitPos32(uint32 pos)
uint32 IntervalDown32(uint32 s)
int64 UnsafeLeastSignificantBitPosition64(const uint64 *const bitset, uint64 start, uint64 end)
uint64 TwoBitsFromPos64(uint64 pos)
uint64 BitOffset64(uint64 pos)
static const uint64 kAllBitsButLsb64
void SetBit64(uint64 *const bitset, uint64 pos)
uint32 BitLength32(uint32 size)
bool IsBitSet32(const uint32 *const bitset, uint32 pos)
int32 UnsafeMostSignificantBitPosition32(const uint32 *const bitset, uint32 start, uint32 end)
bool IsBitSet64(const uint64 *const bitset, uint64 pos)
int LeastSignificantBitPosition32Default(uint32 n)
int32 UnsafeLeastSignificantBitPosition32(const uint32 *const bitset, uint32 start, uint32 end)
static const uint32 kAllBits32
bool IsEmptyRange64(const uint64 *const bitset, uint64 start, uint64 end)
int LeastSignificantBitPosition32(uint32 n)
int LeastSignificantBitPosition64DeBruijn(uint64 n)
static const uint64 kAllBits64
uint32 BitCountRange32(const uint32 *const bitset, uint32 start, uint32 end)
uint32 IntervalUp32(uint32 s)
void ClearBit64(uint64 *const bitset, uint64 pos)
uint64 LeastSignificantBitWord64(uint64 n)
void ClearBit32(uint32 *const bitset, uint32 pos)
uint64 OneRange64(uint64 s, uint64 e)
uint32 BitOffset32(uint32 pos)
int LeastSignificantBitPosition32DeBruijn(uint32 n)
uint64 BitCountRange64(const uint64 *const bitset, uint64 start, uint64 end)
int MostSignificantBitPosition64Default(uint64 n)
int64 UnsafeMostSignificantBitPosition64(const uint64 *const bitset, uint64 start, uint64 end)
uint64 IntervalDown64(uint64 s)
uint32 OneRange32(uint32 s, uint32 e)
int MostSignificantBitPosition32Default(uint32 n)
bool IsEmptyRange32(const uint32 *const bitset, uint32 start, uint32 end)
uint64 BitLength64(uint64 size)
int MostSignificantBitPosition32(uint32 n)
static int input(yyscan_t yyscanner)