16#ifndef OR_TOOLS_UTIL_BITSET_H_
17#define OR_TOOLS_UTIL_BITSET_H_
29#include "absl/log/check.h"
36static const uint64_t
kAllBits64 = uint64_t{0xFFFFFFFFFFFFFFFF};
41inline uint64_t
OneBit64(
int pos) {
return uint64_t{1} << pos; }
42inline uint32_t
OneBit32(
int pos) {
return 1U << pos; }
46 const uint64_t m1 = uint64_t{0x5555555555555555};
47 const uint64_t m2 = uint64_t{0x3333333333333333};
48 const uint64_t m4 = uint64_t{0x0F0F0F0F0F0F0F0F};
49 const uint64_t h01 = uint64_t{0x0101010101010101};
51 n = (n & m2) + ((n >> 2) & m2);
52 n = (n + (n >> 4)) & m4;
57 n -= (n >> 1) & 0x55555555UL;
58 n = (n & 0x33333333) + ((n >> 2) & 0x33333333UL);
59 n = (n + (n >> 4)) & 0x0F0F0F0FUL;
62 return n & 0x0000003FUL;
73#define USE_DEBRUIJN true
74#if defined(__GNUC__) || defined(__llvm__)
75#define USE_FAST_LEAST_SIGNIFICANT_BIT true
78#if defined(USE_FAST_LEAST_SIGNIFICANT_BIT)
79inline int LeastSignificantBitPosition64Fast(uint64_t n) {
80 return __builtin_ctzll(n);
85 static const uint64_t kSeq = uint64_t{0x0218a392dd5fb34f};
86 static const int kTab[64] = {
88 0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 52, 20, 58,
89 5, 17, 26, 56, 15, 38, 29, 40, 10, 49, 53, 31, 21, 34, 59, 42,
90 63, 6, 12, 18, 24, 27, 51, 57, 16, 55, 37, 39, 48, 30, 33, 41,
91 62, 11, 23, 50, 54, 36, 47, 32, 61, 22, 35, 46, 60, 45, 44, 43,
93 return kTab[((n & (~n + 1)) * kSeq) >> 58];
99 if (n & 0x00000000FFFFFFFFLL) {
104 if (n & 0x000000000000FFFFLL) {
109 if (n & 0x00000000000000FFLL) {
114 if (n & 0x000000000000000FLL) {
119 if (n & 0x0000000000000003LL) {
124 if (n & 0x0000000000000001LL) {
132#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
133 return LeastSignificantBitPosition64Fast(n);
134#elif defined(USE_DEBRUIJN)
141#if defined(USE_FAST_LEAST_SIGNIFICANT_BIT)
142inline int LeastSignificantBitPosition32Fast(uint32_t n) {
143 return __builtin_ctzl(n);
148 static const uint32_t kSeq = 0x077CB531U;
149 static const int kTab[32] = {
150 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20,
151 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19,
152 16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
153 return kTab[((n & (~n + 1)) * kSeq) >> 27];
159 if (n & 0x0000FFFFL) {
164 if (n & 0x000000FFL) {
169 if (n & 0x0000000FL) {
174 if (n & 0x00000003L) {
179 if (n & 0x00000001L) {
187#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
188 return LeastSignificantBitPosition32Fast(n);
189#elif defined(USE_DEBRUIJN)
197#if USE_FAST_LEAST_SIGNIFICANT_BIT
198inline int MostSignificantBitPosition64Fast(uint64_t n) {
201 const int offset = __builtin_clzll(1);
202 return n == 0 ? 0 : (offset - __builtin_clzll(n));
235#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
236 return MostSignificantBitPosition64Fast(n);
242#if USE_FAST_LEAST_SIGNIFICANT_BIT
243inline int MostSignificantBitPosition32Fast(uint32_t n) {
247 const int offset = __builtin_clzl(1);
248 return n == 0 ? 0 : (offset - __builtin_clzl(n));
277#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
278 return MostSignificantBitPosition32Fast(n);
285#undef USE_FAST_LEAST_SIGNIFICANT_BIT
333inline uint32_t
BitPos64(uint64_t pos) {
return (pos & 63); }
334inline uint32_t
BitPos32(uint32_t pos) {
return (pos & 31); }
341inline uint64_t
BitLength64(uint64_t size) {
return ((size + 63) >> 6); }
342inline uint32_t
BitLength32(uint32_t size) {
return ((size + 31) >> 5); }
349inline bool IsBitSet64(
const uint64_t*
const bitset, uint64_t pos) {
352inline bool IsBitSet32(
const uint32_t*
const bitset, uint32_t pos) {
357inline void SetBit64(uint64_t*
const bitset, uint64_t pos) {
360inline void SetBit32(uint32_t*
const bitset, uint32_t pos) {
365inline void ClearBit64(uint64_t*
const bitset, uint64_t pos) {
368inline void ClearBit32(uint32_t*
const bitset, uint32_t pos) {
395 uint64_t start, uint64_t
end);
397 uint32_t start, uint32_t
end);
400 uint64_t start, uint64_t
end);
402 uint32_t start, uint32_t
end);
406 return uint64_t{3} << (pos & 62);
414template <
typename IndexType =
int64_t>
428 const uint64_t*
data()
const {
return data_; }
431 const uint64_t*
const data_;
451 uint64_t*
const data_;
456 : size_(Value(
size) > 0 ?
size : IndexType(0)),
460 View
view() {
return View(
this); }
463 IndexType
size()
const {
return size_; }
469 Set(size_ - 1, value);
475 DCHECK_GE(Value(
size), 0);
476 IndexType new_size = Value(
size) > 0 ?
size : IndexType(0);
477 if (new_size < size_ && Value(new_size) > 0) {
478 const int64_t new_data_size =
BitLength64(Value(new_size));
481 data_[new_data_size - 1] &= ~bitmask;
489 DCHECK_GE(Value(
size), 0);
490 size_ = Value(
size) > 0 ?
size : IndexType(0);
495 const size_t bit_length =
static_cast<size_t>(
BitLength64(Value(size_)));
496 const size_t to_clear = std::min(data_.size(), bit_length);
497 data_.resize(bit_length, 0);
498 memset(data_.data(), 0, to_clear *
sizeof(int64_t));
502 void ClearAll() { memset(data_.data(), 0, data_.size() *
sizeof(int64_t)); }
506 DCHECK_GE(Value(i), 0);
507 DCHECK_LT(Value(i), Value(size_));
513 DCHECK_GE(Value(i), 0);
514 DCHECK_LT(Value(i), Value(size_));
520 DCHECK_GE(Value(i), 0);
521 DCHECK_LT(Value(i), Value(size_));
527 DCHECK_GE(Value(i), 0);
528 DCHECK_LT(Value(i), Value(size_));
534 DCHECK_GE(Value(i), 0);
535 DCHECK_LT(Value(i), Value(size_));
544 DCHECK_GE(Value(i), 0);
545 DCHECK_LT(Value(i), size_);
551 void Set(IndexType i,
bool value) {
562 data_[offset] = other.data_[offset];
568 template <
typename OtherIndexType>
570 const int64_t min_size = std::min(data_.size(), other.data_.size());
571 if (min_size == 0)
return;
572 const uint64_t last_common_bucket = data_[min_size - 1];
573 memcpy(data_.data(), other.data_.data(), min_size *
sizeof(uint64_t));
574 if (data_.size() >= other.data_.size()) {
577 data_[min_size - 1] &= ~bitmask;
578 data_[min_size - 1] |= (bitmask & last_common_bucket);
583 template <
typename OtherIndexType>
585 DCHECK_EQ(Value(
size()), other.Value(other.
size()));
586 memcpy(data_.data(), other.data_.data(), data_.size() *
sizeof(uint64_t));
593 const int min_size = std::min(data_.size(), other.data_.size());
594 uint64_t*
const d = data_.data();
595 const uint64_t*
const o = other.data_.data();
596 for (
int i = 0; i < min_size; ++i) {
599 for (
int i = min_size; i < data_.size(); ++i) {
607 DCHECK_EQ(a.
size(), b.size());
611 const int num_buckets = a.data_.size();
612 for (
int i = 0; i < num_buckets; ++i) {
613 data_[i] = a.data_[i] & b.data_[i];
621 const int min_size = std::min(data_.size(), other.data_.size());
622 for (
int i = 0; i < min_size; ++i) {
623 data_[i] |= other.data_[i];
647 : data_(bitset.data_.data()), size_(bitset.data_.
size()) {
648 if (!bitset.data_.empty()) {
655 return Iterator(bitset.data_.data());
660 if (other.size_ == 0) {
663 return std::tie(index_, current_) !=
664 std::tie(other.index_, other.current_);
667 IndexType
operator*()
const {
return IndexType(index_); }
677 while (current_ == 0) {
679 if (bucket == size_) {
683 current_ = data_[bucket];
688 current_ &= current_ - 1;
693 explicit Iterator(
const uint64_t* data) : data_(data), size_(0) {}
695 const uint64_t* data_;
698 uint64_t current_ = 0;
703 Iterator
begin()
const {
return Iterator(*
this); }
712 DCHECK(use1 == 0 || use1 == 1);
713 DCHECK(use2 == 0 || use2 == 1);
716 return ((use1 << pos) & set1.
data()[bucket]) ^
717 ((use2 << pos) & set2.
data()[bucket]);
723 for (IndexType i(0); i <
size(); ++i) {
724 output +=
IsSet(i) ?
"1" :
"0";
730 return std::all_of(data_.begin(), data_.end(),
731 [](uint64_t v) { return v == 0; });
737 static int Value(IndexType
input);
740 std::vector<uint64_t> data_;
742 template <
class OtherIndexType>
752 : size_(size), top_(-1), data_(
BitLength64(size), 0) {}
759 CHECK_GE(size, size_);
773 top_ = std::max(top_, i);
781 top_ = std::max(top_, i - 1);
782 int bucket_index =
static_cast<int>(
BitOffset64(i));
784 for (--bucket_index; bucket_index >= 0; --bucket_index) {
790 int Top()
const {
return top_; }
795 int bucket_index =
static_cast<int>(
BitOffset64(top_));
798 if (bucket_index == 0) {
802 bucket = data_[--bucket_index];
808 top_ =
static_cast<int>(
BitShift64(bucket_index) +
815 std::vector<uint64_t> data_;
819template <
typename IntType>
820inline int Bitset64<IntType>::Value(IntType
input) {
821 DCHECK_GE(
input.value(), 0);
822 return input.value();
825inline int Bitset64<int>::Value(
int input) {
830inline int Bitset64<int64_t>::Value(int64_t
input) {
835inline int Bitset64<size_t>::Value(
size_t input) {
841template <
typename IntegerType =
int64_t>
850 IntegerType
size()
const {
return bitset_.size(); }
854 const int kSparseThreshold = 300;
855 if (to_clear_.size() * kSparseThreshold <
size) {
856 for (
const IntegerType i : to_clear_) bitset_.ClearBucket(i);
858 bitset_.Resize(
size);
860 bitset_.ClearAndResize(
size);
865 if (
size < bitset_.size()) {
867 for (IntegerType index : to_clear_) {
869 to_clear_[new_index] = index;
873 to_clear_.resize(new_index);
875 bitset_.Resize(
size);
877 bool operator[](IntegerType index)
const {
return bitset_[index]; }
878 void Set(IntegerType index) {
879 if (!bitset_[index]) {
881 to_clear_.push_back(index);
888 return bitset_.const_view();
892 to_clear_.push_back(index);
895 void Clear(IntegerType index) { bitset_.Clear(index); }
897 return to_clear_.size();
911 for (IntegerType index : to_clear_) CHECK(!bitset_[index]);
917 return bitset_.const_view();
922 std::vector<IntegerType> to_clear_;
int Top() const
Returns the position of the highest bit set in O(1) or -1 if no bit is set.
void ClearAndResize(int size)
void ClearTop()
Clears the Top() bit and recomputes the position of the next Top().
BitQueue64(const BitQueue64 &)=delete
This type is neither copyable nor movable.
void IncreaseSize(int size)
BitQueue64 & operator=(const BitQueue64 &)=delete
void SetAllBefore(int i)
Sets all the bits from 0 up to i-1 to 1.
When speed matter, caching the base pointer helps.
const uint64_t * data() const
bool operator[](IndexType i) const
ConstView(const Bitset64 *bitset)
Iterator(const Iterator &other)=default
bool operator==(const Iterator &other) const
bool operator!=(const Iterator &other) const
std::forward_iterator_tag iterator_category
Iterator(Iterator &&other)=default
Iterator & operator=(const Iterator &other)=default
std::ptrdiff_t difference_type
IndexType operator*() const
static Iterator EndIterator(const Bitset64 &bitset)
Iterator(const Bitset64 &bitset)
bool operator[](IndexType i) const
void CopyBucket(const Bitset64< IndexType > &other, IndexType i)
Copies bucket containing bit i from "other" to "this".
void ClearAll()
Sets all bits to 0.
void ClearBucket(IndexType i)
Sets bucket containing bit i to 0.
void SetContentFromBitset(const Bitset64< OtherIndexType > &other)
bool IsSet(IndexType i) const
Returns true if the bit at position i is set.
void Clear(IndexType i)
Sets the bit at position i to 0.
void Set(IndexType i, bool value)
If value is true, sets the bit at position i to 1, sets it to 0 otherwise.
void Union(const Bitset64< IndexType > &other)
void Intersection(const Bitset64< IndexType > &other)
void resize(int size)
Resizes the Bitset64 to the given number of bits. New bits are sets to 0.
std::string DebugString() const
Returns a 0/1 string representing the bitset.
static uint64_t ConditionalXorOfTwoBits(IndexType i, uint64_t use1, Bitset64< IndexType >::ConstView set1, uint64_t use2, Bitset64< IndexType >::ConstView set2)
void ClearTwoBits(IndexType i)
Clears the bits at position i and i ^ 1.
void Resize(IndexType size)
bool AreOneOfTwoBitsSet(IndexType i) const
Returns true if the bit at position i or the one at position i ^ 1 is set.
void SetToIntersectionOf(const Bitset64< IndexType > &a, const Bitset64< IndexType > &b)
This one assume both given bitset to be of the same size.
void ClearAndResize(IndexType size)
Changes the number of bits the Bitset64 can hold and set all of them to 0.
void PushBack(bool value)
Appends value at the end of the bitset.
bool operator[](IndexType i) const
Same as IsSet().
void SetContentFromBitsetOfSameSize(const Bitset64< OtherIndexType > &other)
Same as SetContentFromBitset where "this" and "other" have the same size.
ConstView const_view() const
void Set(IndexType i)
Sets the bit at position i to 1.
Bitset64< IntegerType >::ConstView BitsetConstView()
void ClearAndResize(IntegerType size)
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
void Clear(IntegerType index)
bool operator[](IntegerType index) const
SparseBitset & operator=(const SparseBitset &)=delete
Bitset64< IntegerType >::ConstView const_view() const
SparseBitset(IntegerType size)
void Set(IntegerType index)
Bitset64< IntegerType >::View BitsetView()
A bit hacky for really hot loop.
int NumberOfSetCallsWithDifferentArguments() const
SparseBitset(const SparseBitset &)=delete
This type is neither copyable nor movable.
void Resize(IntegerType size)
void SetUnsafe(typename Bitset64< IntegerType >::View view, IntegerType index)
In SWIG mode, we don't want anything besides these top-level includes.
uint32_t IntervalDown32(uint32_t s)
int64_t UnsafeMostSignificantBitPosition64(const uint64_t *bitset, uint64_t start, uint64_t end)
uint32_t BitCountRange32(const uint32_t *bitset, uint32_t start, uint32_t end)
int LeastSignificantBitPosition32Default(uint32_t n)
void SetBit32(uint32_t *const bitset, uint32_t pos)
int64_t UnsafeLeastSignificantBitPosition64(const uint64_t *bitset, uint64_t start, uint64_t end)
uint32_t BitLength32(uint32_t size)
static const uint32_t kAllBits32
bool IsEmptyRange32(const uint32_t *bitset, uint32_t start, uint32_t end)
uint32_t BitCount32(uint32_t n)
int32_t UnsafeLeastSignificantBitPosition32(const uint32_t *bitset, uint32_t start, uint32_t end)
int LeastSignificantBitPosition64DeBruijn(uint64_t n)
int MostSignificantBitPosition32Default(uint32_t n)
int LeastSignificantBitPosition64Default(uint64_t n)
bool IsBitSet32(const uint32_t *const bitset, uint32_t pos)
uint32_t BitPos32(uint32_t pos)
ClosedInterval::Iterator end(ClosedInterval interval)
uint64_t BitShift64(uint64_t v)
Returns the bit number in the bitset of the first bit of word number v.
uint32_t BitOffset32(uint32_t pos)
uint32_t LeastSignificantBitWord32(uint32_t n)
uint64_t IntervalDown64(uint64_t s)
Returns a word with the s most significant bits unset.
uint32_t IntervalUp32(uint32_t s)
void ClearBit32(uint32_t *const bitset, uint32_t pos)
static const uint64_t kAllBits64
Basic bit operations.
int LeastSignificantBitPosition32DeBruijn(uint32_t n)
void ClearBit64(uint64_t *const bitset, uint64_t pos)
Sets the bit pos to false in bitset.
uint32_t OneBit32(int pos)
uint64_t OneRange64(uint64_t s, uint64_t e)
Returns a word with bits from s to e set.
static const uint64_t kAllBitsButLsb64
uint32_t BitShift32(uint32_t v)
uint32_t BitPos64(uint64_t pos)
Bit operators used to manipulates bitsets.
uint64_t BitCountRange64(const uint64_t *bitset, uint64_t start, uint64_t end)
Returns the number of bits set in bitset between positions start and end.
uint64_t BitCount64(uint64_t n)
Returns the number of bits set in n.
int MostSignificantBitPosition32(uint32_t n)
bool IsBitSet64(const uint64_t *const bitset, uint64_t pos)
Returns true if the bit pos is set in bitset.
uint64_t OneBit64(int pos)
Returns a word with only bit pos set.
uint32_t OneRange32(uint32_t s, uint32_t e)
uint64_t BitOffset64(uint64_t pos)
Returns the word number corresponding to bit number pos.
bool IsEmptyRange64(const uint64_t *bitset, uint64_t start, uint64_t end)
Returns true if no bits are set in bitset between start and end.
uint64_t BitLength64(uint64_t size)
Returns the number of words needed to store size bits.
int LeastSignificantBitPosition64(uint64_t n)
int32_t UnsafeMostSignificantBitPosition32(const uint32_t *bitset, uint32_t start, uint32_t end)
int MostSignificantBitPosition64Default(uint64_t n)
Returns the most significant bit position in n.
int LeastSignificantBitPosition32(uint32_t n)
void SetBit64(uint64_t *const bitset, uint64_t pos)
Sets the bit pos to true in bitset.
uint64_t LeastSignificantBitWord64(uint64_t n)
Returns a word with only the least significant bit of n set.
uint64_t TwoBitsFromPos64(uint64_t pos)
Returns a mask with the bits pos % 64 and (pos ^ 1) % 64 sets.
int MostSignificantBitPosition64(uint64_t n)
uint64_t IntervalUp64(uint64_t s)
Returns a word with s least significant bits unset.
static int input(yyscan_t yyscanner)