23template <fl::u32 N>
class bitset_inlined;
25template <fl::u32 N>
class bitset_fixed;
28template <fl::u32 N = 16>
29using bitset = bitset_inlined<N>;
37template<
typename IntType>
40 const U u =
static_cast<U
>(
value);
41 return static_cast<fl::u8>(
42 sizeof(U) <=
sizeof(unsigned) ? __builtin_popcount(
static_cast<unsigned>(u))
43 :
sizeof(U) <=
sizeof(
unsigned long) ? __builtin_popcountl(
static_cast<unsigned long>(u))
44 : __builtin_popcountll(
static_cast<unsigned long long>(u)));
49template<
typename IntType>
52 const U u =
static_cast<U
>(
value);
53 return static_cast<fl::u8>(
54 sizeof(U) <=
sizeof(unsigned) ? __builtin_ctz(
static_cast<unsigned>(u))
55 :
sizeof(U) <=
sizeof(
unsigned long) ? __builtin_ctzl(
static_cast<unsigned long>(u))
56 : __builtin_ctzll(
static_cast<unsigned long long>(u)));
60template <fl::u32 N>
class bitset_fixed {
63 static constexpr fl::u32 bits_per_block = 8 *
sizeof(fl::u16);
64 static constexpr fl::u32 block_count =
65 (N + bits_per_block - 1) / bits_per_block;
66 using block_type = fl::u16;
69 block_type _blocks[block_count];
73 bitset_fixed &_bitset;
79 _bitset.set(_pos, value);
83 operator bool()
const FL_NO_EXCEPT {
return _bitset.test(_pos); }
97 for (fl::u32 i = 0; i < block_count; ++i) {
105 const fl::u32 idx =
pos / bits_per_block;
106 const fl::u32 off =
pos % bits_per_block;
108 _blocks[idx] |= (block_type(1) << off);
110 _blocks[idx] &= ~(block_type(1) << off);
120 for (fl::size i = 0; i < n; ++i) {
131 const fl::u32 idx =
pos / bits_per_block;
132 const fl::u32 off =
pos % bits_per_block;
133 _blocks[idx] ^= (block_type(1) << off);
140 for (fl::u32 i = 0; i < block_count; ++i) {
141 _blocks[i] = ~_blocks[i];
144 if (N % bits_per_block != 0) {
145 const fl::u32 extra = bits_per_block - (N % bits_per_block);
146 _blocks[block_count - 1] &= (~block_type(0) >> extra);
154 const fl::u32 idx =
pos / bits_per_block;
155 const fl::u32 off =
pos % bits_per_block;
156 return (_blocks[idx] >> off) & 1;
168 for (fl::u32 i = 0; i + 1 < block_count; ++i) {
169 cnt += fl::popcount(_blocks[i]);
174 if (block_count > 0) {
175 block_type last_block = _blocks[block_count - 1];
178 if (N % bits_per_block != 0) {
179 const fl::u32 valid_bits = N % bits_per_block;
181 block_type mask = (valid_bits == bits_per_block)
182 ?
static_cast<block_type
>(~block_type(0))
183 : ((block_type(1) << valid_bits) - 1);
186 cnt += fl::popcount(last_block);
200 for (fl::u32 i = 0; i < block_count - 1; ++i) {
201 if (_blocks[i] != ~block_type(0)) {
207 if (block_count > 0) {
209 if (N % bits_per_block != 0) {
211 mask = (block_type(1) << (N % bits_per_block)) - 1;
213 mask =
static_cast<block_type
>(~block_type(0));
216 if ((_blocks[block_count - 1] & mask) != mask) {
225 bitset_fixed &operator&=(
const bitset_fixed &other)
FL_NO_EXCEPT {
226 for (fl::u32 i = 0; i < block_count; ++i) {
227 _blocks[i] &= other._blocks[i];
233 for (fl::u32 i = 0; i < block_count; ++i) {
234 _blocks[i] |= other._blocks[i];
239 bitset_fixed &operator^=(
const bitset_fixed &other)
FL_NO_EXCEPT {
240 for (fl::u32 i = 0; i < block_count; ++i) {
241 _blocks[i] ^= other._blocks[i];
247 constexpr fl::u32 size()
const FL_NO_EXCEPT {
return N; }
260 fl::u32 start_block =
offset / bits_per_block;
261 fl::u32 start_bit =
offset % bits_per_block;
263 for (fl::u32 block_idx = start_block; block_idx < block_count; ++block_idx) {
264 block_type current_block = _blocks[block_idx];
267 if (block_idx == block_count - 1 && N % bits_per_block != 0) {
268 const fl::u32 valid_bits = N % bits_per_block;
269 block_type mask = (valid_bits == bits_per_block)
270 ?
static_cast<block_type
>(~block_type(0))
271 : ((block_type(1) << valid_bits) - 1);
272 current_block &= mask;
277 current_block = ~current_block;
281 if (block_idx == start_block && start_bit > 0) {
282 current_block &= ~((block_type(1) << start_bit) - 1);
286 if (current_block != 0) {
288 fl::u32 bit_pos = fl::countr_zero(current_block);
289 fl::u32 absolute_pos = block_idx * bits_per_block + bit_pos;
292 if (absolute_pos < N) {
293 return static_cast<fl::i32
>(absolute_pos);
306 fl::i32 find_run(
bool test_value, fl::u32 min_length, fl::u32
offset = 0)
const FL_NO_EXCEPT {
307 fl::u32 run_start =
offset;
308 fl::u32 run_length = 0;
310 for (fl::u32 i =
offset; i < N && run_length < min_length; ++i) {
311 bool current_bit = test(i);
312 if (current_bit != test_value) {
322 if (run_length >= min_length) {
323 return static_cast<fl::i32
>(run_start);
331 for (fl::u32 i = 0; i < block_count; ++i) {
332 if (_blocks[i] != other._blocks[i]) {
340 return !(*
this == other);
345 for (fl::i32 i =
static_cast<fl::i32
>(block_count) - 1; i >= 0; --i) {
346 if (_blocks[i] < other._blocks[i]) {
349 if (_blocks[i] > other._blocks[i]) {
357 return *
this < other || *
this == other;
361 return other < *
this;
365 return other <= *
this;
369 friend bitset_fixed
operator&(bitset_fixed lhs,
373 friend bitset_fixed
operator|(bitset_fixed lhs,
377 friend bitset_fixed operator^(bitset_fixed lhs,
381 friend bitset_fixed operator~(bitset_fixed bs)
FL_NO_EXCEPT {
return bs.flip(); }
387template <fl::u32 N = 16>
388class bitset_inlined {
391 using fixed_bitset = bitset_fixed<N>;
392 variant<fixed_bitset, bitset_dynamic> _storage;
396 bitset_inlined &_bitset;
400 : _bitset(bitset), _pos(
pos) {}
403 _bitset.set(_pos, value);
407 operator bool()
const FL_NO_EXCEPT {
return _bitset.test(_pos); }
413 bitset_inlined()
FL_NO_EXCEPT : _storage(fixed_bitset()) {}
414 bitset_inlined(fl::size size)
FL_NO_EXCEPT : _storage(fixed_bitset()) {
416 _storage = bitset_dynamic(size);
419 bitset_inlined(
const bitset_inlined &other)
FL_NO_EXCEPT : _storage(other._storage) {}
421 : _storage(
fl::move(other._storage)) {}
422 bitset_inlined &operator=(
const bitset_inlined &other)
FL_NO_EXCEPT {
423 if (
this != &other) {
424 _storage = other._storage;
428 bitset_inlined &operator=(bitset_inlined &&other)
FL_NO_EXCEPT {
429 if (
this != &other) {
430 _storage =
fl::move(other._storage);
437 if (_storage.template is<fixed_bitset>()) {
438 _storage.template ptr<fixed_bitset>()->reset();
440 _storage.template ptr<bitset_dynamic>()->reset();
446 if (_storage.template is<fixed_bitset>()) {
447 _storage.template ptr<fixed_bitset>()->assign(n,
value);
449 _storage.template ptr<bitset_dynamic>()->assign(n,
value);
459 if (_storage.template is<bitset_dynamic>()) {
462 bitset_dynamic *dynamic =
463 _storage.template ptr<bitset_dynamic>();
466 for (fl::u32 i = 0; i < N && i < dynamic->size(); ++i) {
467 if (dynamic->test(i)) {
476 if (_storage.template is<fixed_bitset>()) {
478 bitset_dynamic dynamic(new_size);
479 fixed_bitset *fixed = _storage.template ptr<fixed_bitset>();
482 for (fl::u32 i = 0; i < N; ++i) {
483 if (fixed->test(i)) {
491 _storage.template ptr<bitset_dynamic>()->resize(new_size);
498 if (
pos >= N && _storage.template is<fixed_bitset>()) {
502 if (_storage.template is<fixed_bitset>()) {
504 _storage.template ptr<fixed_bitset>()->set(
pos,
value);
507 if (
pos >= _storage.template ptr<bitset_dynamic>()->size()) {
508 _storage.template ptr<bitset_dynamic>()->resize(
pos + 1);
510 _storage.template ptr<bitset_dynamic>()->set(
pos,
value);
520 if (
pos >= N && _storage.template is<fixed_bitset>()) {
524 if (_storage.template is<fixed_bitset>()) {
526 _storage.template ptr<fixed_bitset>()->flip(
pos);
529 if (
pos >= _storage.template ptr<bitset_dynamic>()->size()) {
530 _storage.template ptr<bitset_dynamic>()->resize(
pos + 1);
532 _storage.template ptr<bitset_dynamic>()->flip(
pos);
539 if (_storage.template is<fixed_bitset>()) {
540 _storage.template ptr<fixed_bitset>()->flip();
542 _storage.template ptr<bitset_dynamic>()->flip();
549 fl::u32 new_size = size() + 1;
554 template<
typename... Args>
568 if (_storage.template is<fixed_bitset>()) {
569 return pos < N ? _storage.template ptr<fixed_bitset>()->test(
pos)
572 return _storage.template ptr<bitset_dynamic>()->test(
pos);
581 if (_storage.template is<fixed_bitset>()) {
582 return _storage.template ptr<fixed_bitset>()->count();
584 return _storage.template ptr<bitset_dynamic>()->count();
590 if (_storage.template is<fixed_bitset>()) {
591 return _storage.template ptr<fixed_bitset>()->any();
593 return _storage.template ptr<bitset_dynamic>()->any();
598 if (_storage.template is<fixed_bitset>()) {
599 return _storage.template ptr<fixed_bitset>()->none();
601 return _storage.template ptr<bitset_dynamic>()->none();
606 if (_storage.template is<fixed_bitset>()) {
607 return _storage.template ptr<fixed_bitset>()->all();
609 return _storage.template ptr<bitset_dynamic>()->all();
615 if (_storage.template is<fixed_bitset>()) {
618 return _storage.template ptr<bitset_dynamic>()->size();
624 if (_storage.template is<fixed_bitset>()) {
625 _storage.template ptr<fixed_bitset>()->to_string(dst);
627 _storage.template ptr<bitset_dynamic>()->to_string(dst);
636 if (_storage.template is<fixed_bitset>()) {
637 return _storage.template ptr<fixed_bitset>()->find_first(test_value,
offset);
639 return _storage.template ptr<bitset_dynamic>()->find_first(test_value,
offset);
644 friend bitset_inlined operator~(
const bitset_inlined &bs)
FL_NO_EXCEPT {
645 bitset_inlined
result = bs;
650 friend bitset_inlined
operator&(
const bitset_inlined &lhs,
652 bitset_inlined
result = lhs;
654 if (
result._storage.template is<fixed_bitset>() &&
655 rhs._storage.template is<fixed_bitset>()) {
657 *
result._storage.template ptr<fixed_bitset>() &=
658 *rhs._storage.template ptr<fixed_bitset>();
662 result.size() < rhs.size() ?
result.size() : rhs.size();
663 for (fl::u32 i = 0; i < min_size; ++i) {
667 for (fl::u32 i = min_size; i <
result.size(); ++i) {
675 friend bitset_inlined
operator|(
const bitset_inlined &lhs,
677 bitset_inlined
result = lhs;
679 if (
result._storage.template is<fixed_bitset>() &&
680 rhs._storage.template is<fixed_bitset>()) {
682 *
result._storage.template ptr<fixed_bitset>() |=
683 *rhs._storage.template ptr<fixed_bitset>();
687 result.size() > rhs.size() ?
result.size() : rhs.size();
690 if (
result.size() < max_size) {
695 for (fl::u32 i = 0; i < rhs.size(); ++i) {
705 friend bitset_inlined operator^(
const bitset_inlined &lhs,
707 bitset_inlined
result = lhs;
709 if (
result._storage.template is<fixed_bitset>() &&
710 rhs._storage.template is<fixed_bitset>()) {
712 *
result._storage.template ptr<fixed_bitset>() ^=
713 *rhs._storage.template ptr<fixed_bitset>();
717 result.size() > rhs.size() ?
result.size() : rhs.size();
720 if (
result.size() < max_size) {
725 for (fl::u32 i = 0; i < rhs.size(); ++i) {
735 if (size() != other.size()) {
738 for (fl::u32 i = 0; i < size(); ++i) {
739 if (test(i) != other.test(i)) {
747 return !(*
this == other);
752 fl::u32 min_size = size() < other.size() ? size() : other.size();
753 for (fl::u32 i = min_size; i > 0; --i) {
754 bool this_bit = test(i - 1);
755 bool other_bit = other.test(i - 1);
756 if (this_bit != other_bit) {
761 return size() < other.size();
765 return *
this < other || *
this == other;
769 return other < *
this;
773 return other <= *
this;