1#ifndef ITERABLEBITSET_HH
2#define ITERABLEBITSET_HH
32 using WordType = std::conditional_t<(N > 32), uint64_t,
33 std::conditional_t<(N > 16), uint32_t,
34 std::conditional_t<(N > 8), uint16_t,
36 static constexpr size_t BITS_PER_WORD = 8 *
sizeof(WordType);
37 static constexpr size_t NUM_WORDS = (N + BITS_PER_WORD - 1) / BITS_PER_WORD;
45 [[nodiscard]]
bool empty()
const
55 if constexpr (NUM_WORDS > 1) {
56 auto w = pos / BITS_PER_WORD;
57 auto m = WordType(1) << (pos % BITS_PER_WORD);
60 words[0] |= WordType(1) << pos;
80 if constexpr (NUM_WORDS > 1) {
81 auto firstWord =
begin / BITS_PER_WORD;
82 auto lastWord = (
end - 1) / BITS_PER_WORD;
83 if (firstWord != lastWord) {
84 auto firstPos =
begin % BITS_PER_WORD;
85 auto firstMask = WordType(-1) << firstPos;
86 words[firstWord++] |= firstMask;
88 while (firstWord != lastWord) {
89 words[firstWord++] = WordType(-1);
92 auto lastPos =
end % BITS_PER_WORD;
93 auto lastMask = WordType(-1) >> (lastPos ? (BITS_PER_WORD - lastPos) : 0);
94 words[firstWord] |= lastMask;
96 auto firstPos =
begin % BITS_PER_WORD;
97 auto mask = WordType(-1) << firstPos;
98 auto lastPos =
end % BITS_PER_WORD;
100 auto lastMask = WordType(-1) >> (BITS_PER_WORD - lastPos);
103 words[firstWord] |= mask;
107 auto mask1 = WordType(-1) <<
begin;
108 auto mask2 = WordType(-1) >> (BITS_PER_WORD -
end);
109 words[0] |= mask1 & mask2;
119 for (
auto i :
xrange(NUM_WORDS)) {
122 op(i * BITS_PER_WORD + std::countr_zero(w));
129 std::array<WordType, NUM_WORDS> words = {};
bool empty() const
(Implicit) default constructor.
void setPosN(size_t pos, size_t n)
Starting from position 'pos', set the 'n' following bits to '1'.
void setRange(size_t begin, size_t end)
Set all bits in the half-open range [begin, end) to '1'.
void foreachSetBit(std::invocable< size_t > auto op) const
Execute the given operation 'op' for all '1' bits.
void set(size_t pos)
Set the (single) bit at position 'pos' to '1'.
constexpr bool all_of(InputRange &&range, UnaryPredicate pred)
constexpr auto xrange(T e)
constexpr auto begin(const zstring_view &x)
constexpr auto end(const zstring_view &x)