This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A" #include <bitset> #include <iostream> #include "library/datastructure/util/dynamic_bitset.hpp" using suisen::DynamicBitSet; template <std::size_t n> bool operator==(const DynamicBitSet& dbs, const std::bitset<n>& bs) { if (dbs.size() != int(n)) return false; for (std::size_t i = 0; i < n; ++i) if (dbs[i] != bs[i]) return false; return true; } template <std::size_t n> bool operator==(const std::bitset<n>& bs, const DynamicBitSet& dbs) { return dbs == bs; } template <std::size_t n> bool operator!=(const DynamicBitSet& dbs, const std::bitset<n>& bs) { return not (dbs == bs); } template <std::size_t n> bool operator!=(const std::bitset<n>& bs, const DynamicBitSet& dbs) { return dbs != bs; } void test_empty() { assert(DynamicBitSet(0).empty()); assert(not DynamicBitSet(1).empty()); } void test_size() { assert(DynamicBitSet(0).size() == 0); assert(DynamicBitSet(1).size() == 1); assert(DynamicBitSet(64).size() == 64); } void test_resize() { DynamicBitSet bs; bs.resize(35, true); assert(bs.size() == 35); for (int i = 0; i < 35; ++i) assert(bs[i]); bs.resize(1026, false); assert(bs.size() == 1026); for (int i = 0; i < 35; ++i) assert(bs[i]); for (int i = 35; i < 1026; ++i) assert(not bs[i]); bs.resize(78); assert(bs.size() == 78); for (int i = 0; i < 35; ++i) assert(bs[i]); for (int i = 35; i < 78; ++i) assert(not bs[i]); bs.resize(512, true); assert(bs.size() == 512); for (int i = 0; i < 35; ++i) assert(bs[i]); for (int i = 35; i < 78; ++i) assert(not bs[i]); for (int i = 78; i < 512; ++i) assert(bs[i]); bs.resize(128, false); assert(bs.size() == 128); for (int i = 0; i < 35; ++i) assert(bs[i]); for (int i = 35; i < 78; ++i) assert(not bs[i]); for (int i = 78; i < 128; ++i) assert(bs[i]); } void test_push_back() { DynamicBitSet bs; for (int i = 0; i < 1000; ++i) { bs.push_back(i & 1); assert(bs.size() == i + 1); for (int j = 0; j <= i; ++j) assert(bs[j] == (j & 1)); } } void test_pop_back() { DynamicBitSet bs; for (int i = 0; i < 1000; ++i) { bs.push_back(i & 1); } for (int i = 0; i < 1000; ++i) { bs.pop_back(); assert(bs.size() == 999 - i); for (int j = 0; j < 999 - i; ++j) assert(bs[j] == (j & 1)); } } void test_eq() { DynamicBitSet x(10, true); DynamicBitSet y(10); for (int i = 0; i < 10; ++i) y[i] = true; assert(x == y); x.resize(516, false); y.resize(516, false); assert(x == y); x.resize(100); y.resize(200); x.resize(300, true); y.resize(300, true); for (int i = 100; i < 200; ++i) y[i] = true; assert(x == y); } void test_neq() { DynamicBitSet x(10); DynamicBitSet y; assert(x != y); y.resize(5); assert(x != y); y.resize(64, true); assert(x != y); y.resize(10); assert(x != y); x.resize(500); y.resize(500); for (int i = 5; i < 10; ++i) x[i] = true; assert(x == y); y[499] = true; assert(x != y); y[499] = false; assert(x == y); y[256] = true; assert(x != y); y[256] = false; assert(x == y); y[255] = true; assert(x != y); } void test_lt() { DynamicBitSet x(100), y(100); assert(not (x < y)); x[56] = true; assert(not (x < y)); y[56] = true; assert(not (x < y)); y[99] = true; assert(x < y); x.resize(200), y.resize(200); x[100] = true; assert(not (x < y)); y[100] = true; assert(x < y); x[99] = true; assert(not (x < y)); y[199] = true; assert(x < y); y[199] = false; y[128] = true; assert(x < y); y[128] = false; y[127] = true; assert(x < y); } void test_leq() { DynamicBitSet x(100), y(100); assert(x <= y); x[56] = true; assert(not (x <= y)); y[56] = true; assert(x <= y); y[99] = true; assert(x <= y); x.resize(200), y.resize(200); x[100] = true; assert(not (x <= y)); y[100] = true; assert(x <= y); x[99] = true; assert(x <= y); y[199] = true; assert(x <= y); y[199] = false; y[128] = true; assert(x <= y); y[128] = false; y[127] = true; assert(x <= y); } void test_gt() { DynamicBitSet x(100), y(100); assert(not (x > y)); x[56] = true; assert(x > y); y[56] = true; assert(not (x > y)); y[99] = true; assert(not (x > y)); x.resize(200), y.resize(200); x[100] = true; assert(x > y); y[100] = true; assert(not (x > y)); x[99] = true; assert(not (x > y)); y[199] = true; assert(not (x > y)); y[199] = false; y[128] = true; assert(not (x > y)); y[128] = false; y[127] = true; assert(not (x > y)); } void test_geq() { DynamicBitSet x(100), y(100); assert(x >= y); x[56] = true; assert(x >= y); y[56] = true; assert(x >= y); y[99] = true; assert(not (x >= y)); x.resize(200), y.resize(200); x[100] = true; assert(x >= y); y[100] = true; assert(not (x >= y)); x[99] = true; assert(x >= y); y[199] = true; assert(not (x >= y)); y[199] = false; y[128] = true; assert(not (x >= y)); y[128] = false; y[127] = true; assert(not (x >= y)); } void test_cast_bool() { DynamicBitSet x; assert(not x); x.resize(100); assert(not x); x[99] = true; assert(x); } void test_and() { constexpr int n = 353; std::bitset<n> bs1, bs2; DynamicBitSet dbs1(n), dbs2(n); for (int i = 0; i < n; ++i) { bs1[i] = i % 3 == 0; dbs1[i] = i % 3 == 0; } for (int i = 0; i < n; ++i) { bs2[i] = i % 5 == 0; dbs2[i] = i % 5 == 0; } auto bs = bs1 & bs2; auto dbs = dbs1 & dbs2; assert(bs == dbs); } void test_or() { constexpr int n = 353; std::bitset<n> bs1, bs2; DynamicBitSet dbs1(n), dbs2(n); for (int i = 0; i < n; ++i) { bs1[i] = i % 3 == 0; dbs1[i] = i % 3 == 0; } for (int i = 0; i < n; ++i) { bs2[i] = i % 5 == 0; dbs2[i] = i % 5 == 0; } auto bs = bs1 | bs2; auto dbs = dbs1 | dbs2; assert(bs == dbs); } void test_xor() { constexpr int n = 353; std::bitset<n> bs1, bs2; DynamicBitSet dbs1(n), dbs2(n); for (int i = 0; i < n; ++i) { bs1[i] = i % 3 == 0; dbs1[i] = i % 3 == 0; } for (int i = 0; i < n; ++i) { bs2[i] = i % 5 == 0; dbs2[i] = i % 5 == 0; } auto bs = bs1 ^ bs2; auto dbs = dbs1 ^ dbs2; assert(bs == dbs); } void test_shift_r() { constexpr int n = 353; std::bitset<n> bs; DynamicBitSet dbs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 == 0; dbs[i] = i % 3 == 0; } for (std::size_t i = 0; i < n; ++i) { assert((bs >> i) == (dbs >> i)); } } void test_shift_l() { constexpr int n = 353; std::bitset<n> bs; DynamicBitSet dbs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 == 0; dbs[i] = i % 3 == 0; } for (std::size_t i = 0; i < n; ++i) { assert((bs << i) == (dbs << i)); } } void test_neg() { constexpr int n = 353; std::bitset<n> bs; DynamicBitSet dbs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 == 0; dbs[i] = i % 3 == 0; } assert(~bs == ~dbs); } void test_get_set() { constexpr int n = 2349; DynamicBitSet bs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 != 0; } for (int i = 0; i < n; ++i) { assert(bs[i] == (i % 3 != 0)); } } void test_range_set() { constexpr int n = 513; std::bitset<n> bs; DynamicBitSet dbs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 == 0; dbs[i] = i % 3 == 0; } auto range_set_dbs = [&](int l, int r) { auto dbs2 = dbs; dbs2.range_set(l, r); return dbs2; }; auto range_set_bs = [&](int l, int r) { auto bs2 = bs; for (int i = l; i < r; ++i) bs2[i] = true; return bs2; }; for (int l = 0; l <= n; ++l) for (int r = l; r <= n; ++r) { assert(range_set_bs(l, r) == range_set_dbs(l, r)); } } void test_range_reset() { constexpr int n = 513; std::bitset<n> bs; DynamicBitSet dbs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 == 0; dbs[i] = i % 3 == 0; } auto range_reset_dbs = [&](int l, int r) { auto dbs2 = dbs; dbs2.range_reset(l, r); return dbs2; }; auto range_reset_bs = [&](int l, int r) { auto bs2 = bs; for (int i = l; i < r; ++i) bs2[i] = false; return bs2; }; for (int l = 0; l <= n; ++l) for (int r = l; r <= n; ++r) { assert(range_reset_bs(l, r) == range_reset_dbs(l, r)); } } void test_range_flip() { constexpr int n = 513; std::bitset<n> bs; DynamicBitSet dbs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 == 0; dbs[i] = i % 3 == 0; } auto range_flip_dbs = [&](int l, int r) { auto dbs2 = dbs; dbs2.range_flip(l, r); return dbs2; }; auto range_flip_bs = [&](int l, int r) { auto bs2 = bs; for (int i = l; i < r; ++i) bs2[i].flip(); return bs2; }; for (int l = 0; l <= n; ++l) for (int r = l; r <= n; ++r) { assert(range_flip_bs(l, r) == range_flip_dbs(l, r)); } } void test_range_update() { constexpr int n = 513; std::bitset<n> bs; DynamicBitSet dbs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 == 0; dbs[i] = i % 3 == 0; } auto range_update_dbs = [&](int l, int r, bool val) { auto dbs2 = dbs; dbs2.range_update(l, r, val); return dbs2; }; auto range_update_bs = [&](int l, int r, bool val) { auto bs2 = bs; for (int i = l; i < r; ++i) bs2[i] = val; return bs2; }; for (bool b : { false, true }) { for (int l = 0; l <= n; ++l) for (int r = l; r <= n; ++r) { assert(range_update_bs(l, r, b) == range_update_dbs(l, r, b)); } } } void test_range_count() { constexpr int n = 513; std::bitset<n> bs; DynamicBitSet dbs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 == 0; dbs[i] = i % 3 == 0; } auto range_count_dbs = [&](int l, int r) { return dbs.range_count(l, r); }; auto range_count_bs = [&](int l, int r) { int res = 0; for (int i = l; i < r; ++i) res += bs[i]; return res; }; for (int l = 0; l <= n; ++l) for (int r = l; r <= n; ++r) { assert(range_count_bs(l, r) == range_count_dbs(l, r)); } } void test_all() { DynamicBitSet x; assert(x.all()); x.push_back(true); assert(x.all()); x[0] = false; assert(not x.all()); x.resize(129, true); assert(not x.all()); x[0] = true; assert(x.all()); x[128] = false; assert(not x.all()); } void test_none() { DynamicBitSet x; assert(x.none()); x.push_back(true); assert(not x.none()); x[0] = false; assert(x.none()); x.resize(129, false); assert(x.none()); x[0] = true; assert(not x.none()); x[0] = false; assert(x.none()); x[128] = true; assert(not x.none()); } void test_any() { DynamicBitSet x; assert(not x.any()); x.push_back(true); assert(x.any()); x[0] = false; assert(not x.any()); x.resize(129, false); assert(not x.any()); x[0] = true; assert(x.any()); x[0] = false; assert(not x.any()); x[128] = true; assert(x.any()); } void test_count() { DynamicBitSet x; assert(x.count() == 0); x.resize(10); assert(x.count() == 0); x[3] = true; assert(x.count() == 1); x.resize(176, true); assert(x.count() == 167); } void test_set() { DynamicBitSet x; x.set(); assert(x.count() == 0); x.resize(20, false); x.set(); assert(x.count() == 20); x.resize(1238); x.set(); assert(x.count() == 1238); } void test_reset() { DynamicBitSet x; x.reset(); assert(x.count() == 0); x.resize(20, true); x.reset(); assert(x.count() == 0); x.resize(1238); x.reset(); assert(x.count() == 0); } void test_find() { constexpr int n = 513; std::bitset<n> bs; DynamicBitSet dbs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 == 0; dbs[i] = i % 3 == 0; } int i = bs._Find_first(), j = dbs.find_first(); for (; i < n and j < n; i = bs._Find_next(i), j = dbs.find_next(j)) { assert(i == j); } assert(i == n and j == n); } void test_has_intersectoin() { DynamicBitSet x(10, true), y; assert(not x.has_intersection(y)); y.resize(10); y[9] = true; assert(x.has_intersection(y)); y[9] = false; y.resize(123); y[122] = true; assert(not x.has_intersection(y)); x.resize(1230); x[122] = true; assert(x.has_intersection(y)); } void test_is_disjoint() { DynamicBitSet x(10, true), y; assert(x.is_disjoint(y)); y.resize(10); y[9] = true; assert(not x.is_disjoint(y)); y[9] = false; y.resize(123); y[122] = true; assert(x.is_disjoint(y)); x.resize(1230); x[122] = true; assert(not x.is_disjoint(y)); } void test() { test_empty(); test_size(); test_resize(); test_push_back(); test_pop_back(); test_eq(); test_neq(); test_lt(); test_leq(); test_gt(); test_geq(); test_cast_bool(); test_and(); test_or(); test_xor(); test_shift_r(); test_shift_l(); test_neg(); test_get_set(); test_range_set(); test_range_reset(); test_range_flip(); test_range_update(); test_range_count(); test_all(); test_none(); test_any(); test_count(); test_set(); test_reset(); test_find(); test_has_intersectoin(); test_is_disjoint(); } int main() { test(); std::cout << "Hello World" << std::endl; return 0; }
#line 1 "test/src/datastructure/util/dynamic_bitset/dummy.test.cpp" #define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A" #include <bitset> #include <iostream> #line 1 "library/datastructure/util/dynamic_bitset.hpp" #include <cassert> #include <limits> #include <utility> #include <vector> namespace suisen { struct DynamicBitSet { private: using block = unsigned long long; static constexpr std::size_t block_size = std::numeric_limits<block>::digits; static constexpr std::size_t log_block_size = __builtin_ctz(block_size); struct bitref { block& b; std::size_t i; operator bool() const { return (b >> i) & 1; } bool test() const { return (b >> i) & 1; } void set() { b |= block(1) << i; } void reset() { b &= ~(block(1) << i); } void flip() { b ^= block(1) << i; } bitref& operator&=(bool val) { b &= block(val) << i; return *this; } bitref& operator|=(bool val) { b |= block(val) << i; return *this; } bitref& operator^=(bool val) { b ^= block(val) << i; return *this; } bitref& operator =(bool val) { val ? set() : reset(); return *this; } bitref& operator =(const bitref& v) { return (*this) = bool(v); } }; std::size_t n; std::vector<block> blocks; public: DynamicBitSet(std::size_t n = 0, bool fill_value = false) : n(n), blocks((n + block_size - 1) >> log_block_size, fill_value ? ~block(0) : 0) {} bool empty() const { return n == 0; } int size() const { return n; } void resize(std::size_t new_size, bool fill_value = false) { std::size_t new_block_num = (new_size + block_size - 1) >> log_block_size; if (new_block_num < block_num()) { n = new_size; return blocks.resize(new_block_num); } blocks.resize(new_block_num); std::size_t old_size = std::exchange(n, new_size); if (old_size <= new_size) range_update(old_size, new_size, fill_value); } void push_back(bool val) { if (n & (block_size - 1)) { (*this)[n] = val; } else { blocks.push_back(val); } ++n; } void pop_back() { if ((n & (block_size - 1)) == 1) blocks.pop_back(); --n; } friend bool operator==(const DynamicBitSet& x, const DynamicBitSet& y) { if (x.n != y.n) return false; if (x.empty()) return true; for (std::size_t i = 0; i < x.block_num() - 1; ++i) { if (x.blocks[i] != y.blocks[i]) return false; } const std::size_t num = x.n - ((x.block_num() - 1) << log_block_size); return get_lower_bits(x.blocks.back(), num) == get_lower_bits(y.blocks.back(), num); } friend bool operator!=(const DynamicBitSet& x, const DynamicBitSet& y) { return not (x == y); } friend bool operator<(const DynamicBitSet& x, const DynamicBitSet& y) { assert(x.n == y.n); if (x.empty()) return false; std::size_t num = x.n - ((x.block_num() - 1) << log_block_size); block tx = get_lower_bits(x.blocks.back(), num); block ty = get_lower_bits(y.blocks.back(), num); if (tx != ty) return tx < ty; for (std::size_t i = x.block_num() - 1; i-- > 0;) { if (x.blocks[i] != y.blocks[i]) return x.blocks[i] < y.blocks[i]; } return false; } friend bool operator<=(const DynamicBitSet& x, const DynamicBitSet& y) { assert(x.n == y.n); if (x.empty()) return true; std::size_t num = x.n - ((x.block_num() - 1) << log_block_size); block tx = get_lower_bits(x.blocks.back(), num); block ty = get_lower_bits(y.blocks.back(), num); if (tx != ty) return tx < ty; for (std::size_t i = x.block_num() - 1; i-- > 0;) { if (x.blocks[i] != y.blocks[i]) return x.blocks[i] < y.blocks[i]; } return true; } friend bool operator>(const DynamicBitSet& x, const DynamicBitSet& y) { return not (x <= y); } friend bool operator>=(const DynamicBitSet& x, const DynamicBitSet& y) { return not (x < y); } operator bool() const { return any(); } friend DynamicBitSet& operator&=(DynamicBitSet& x, const DynamicBitSet& y) { assert(x.n == y.n); for (std::size_t i = 0; i < y.block_num(); ++i) x.blocks[i] &= y.blocks[i]; return x; } friend DynamicBitSet& operator|=(DynamicBitSet& x, const DynamicBitSet& y) { assert(x.n == y.n); for (std::size_t i = 0; i < y.block_num(); ++i) x.blocks[i] |= y.blocks[i]; return x; } friend DynamicBitSet& operator^=(DynamicBitSet& x, const DynamicBitSet& y) { assert(x.n == y.n); for (std::size_t i = 0; i < y.block_num(); ++i) x.blocks[i] ^= y.blocks[i]; return x; } friend DynamicBitSet operator&(DynamicBitSet x, const DynamicBitSet& y) { x &= y; return x; } friend DynamicBitSet operator|(DynamicBitSet x, const DynamicBitSet& y) { x |= y; return x; } friend DynamicBitSet operator^(DynamicBitSet x, const DynamicBitSet& y) { x ^= y; return x; } friend DynamicBitSet& operator<<=(DynamicBitSet &x, std::size_t shamt) { return x = x << shamt; } friend DynamicBitSet& operator>>=(DynamicBitSet &x, std::size_t shamt) { return x = x >> shamt; } friend DynamicBitSet operator<<(const DynamicBitSet &x, std::size_t shamt) { if (shamt >= x.n) return DynamicBitSet(x.size()); DynamicBitSet res(x.size()); std::size_t block_shamt = shamt >> log_block_size; std::size_t bit_shamt = shamt & (block_size - 1); for (std::size_t i = 0; i + block_shamt < res.block_num(); ++i) { if (bit_shamt == 0) { res.blocks[i + block_shamt] = x.blocks[i]; } else { res.blocks[i + block_shamt] |= x.blocks[i] << bit_shamt; if (i + block_shamt + 1 != res.block_num()) { res.blocks[i + block_shamt + 1] |= x.blocks[i] >> (block_size - bit_shamt); } } } return res; } friend DynamicBitSet operator>>(const DynamicBitSet& x, std::size_t shamt) { if (shamt >= x.n) return DynamicBitSet(x.size()); DynamicBitSet res(x.size()); std::size_t block_shamt = shamt >> log_block_size; std::size_t bit_shamt = shamt & (block_size - 1); for (std::size_t i = 0; i + block_shamt < x.block_num(); ++i) { if (bit_shamt == 0) { res.blocks[i] = x.blocks[i + block_shamt]; } else { res.blocks[i] |= x.blocks[i + block_shamt] >> bit_shamt; if (i + block_shamt + 1 != x.block_num()) { res.blocks[i] |= x.blocks[i + block_shamt + 1] << (block_size - bit_shamt); } } } res.range_reset(x.n - shamt, x.n); return res; } DynamicBitSet operator~() const { DynamicBitSet neg(n); for (std::size_t i = 0; i < block_num(); ++i) neg.blocks[i] = ~blocks[i]; return neg; } bool operator[](std::size_t i) const { return (blocks[block_index(i)] >> bit_index(i)) & 1; } bitref operator[](std::size_t i) { return { blocks[block_index(i)], bit_index(i) }; } void range_set(std::size_t l, std::size_t r) { assert(l <= r and r <= n); if (l == r) return; std::size_t lb = block_index(l), rb = block_index(r - 1); std::size_t li = bit_index(l), ri = bit_index(r); if (ri == 0) ri = block_size; if (lb == rb) { blocks[lb] |= mask_range_bits(~block(0), li, ri); return; } blocks[lb] |= mask_upper_bits(~block(0), block_size - li); blocks[rb] |= mask_lower_bits(~block(0), ri); for (std::size_t i = lb + 1; i < rb; ++i) blocks[i] = ~block(0); } void range_reset(std::size_t l, std::size_t r) { assert(l <= r and r <= n); if (l == r) return; std::size_t lb = block_index(l), rb = block_index(r - 1); std::size_t li = bit_index(l), ri = bit_index(r); if (ri == 0) ri = block_size; if (lb == rb) { blocks[lb] &= ~mask_range_bits(~block(0), li, ri); return; } blocks[lb] &= ~mask_upper_bits(~block(0), block_size - li); blocks[rb] &= ~mask_lower_bits(~block(0), ri); for (std::size_t i = lb + 1; i < rb; ++i) blocks[i] = block(0); } void range_flip(std::size_t l, std::size_t r) { assert(l <= r and r <= n); if (l == r) return; std::size_t lb = block_index(l), rb = block_index(r - 1); std::size_t li = bit_index(l), ri = bit_index(r); if (ri == 0) ri = block_size; if (lb == rb) { blocks[lb] ^= mask_range_bits(~block(0), li, ri); return; } blocks[lb] ^= mask_upper_bits(~block(0), block_size - li); blocks[rb] ^= mask_lower_bits(~block(0), ri); for (std::size_t i = lb + 1; i < rb; ++i) blocks[i] ^= ~block(0); } void range_update(std::size_t l, std::size_t r, bool val) { val ? range_set(l, r) : range_reset(l, r); } int range_count(std::size_t l, std::size_t r) const { assert(l <= r and r <= n); if (l == r) return 0; std::size_t lb = block_index(l), rb = block_index(r - 1); std::size_t li = bit_index(l), ri = bit_index(r); if (ri == 0) ri = block_size; if (lb == rb) { return __builtin_popcountll(blocks[lb] & mask_range_bits(~block(0), li, ri)); } int res = 0; res += __builtin_popcountll(blocks[lb] & mask_upper_bits(~block(0), block_size - li)); res += __builtin_popcountll(blocks[rb] & mask_lower_bits(~block(0), ri)); for (std::size_t i = lb + 1; i < rb; ++i) res += __builtin_popcountll(blocks[i]); return res; } void set() { for (block& b : blocks) b = ~block(0); } void reset() { for (block& b : blocks) b = 0; } bool all() const { if (empty()) return true; for (std::size_t i = 0; i < block_num() - 1; ++i) { if (blocks[i] != ~block(0)) return false; } const std::size_t num = n - ((block_num() - 1) << log_block_size); assert(num); const block upper = ((block(1) << (block_size - num)) - 1) << num; return (upper | blocks.back()) == ~block(0); } bool none() const { if (empty()) return true; for (std::size_t i = 0; i < block_num() - 1; ++i) { if (blocks[i] != 0) return false; } const std::size_t num = n - ((block_num() - 1) << log_block_size); return get_lower_bits(blocks.back(), num) == 0; } bool any() const { return not none(); } int count() const { if (empty()) return 0; int res = 0; for (std::size_t i = 0; i < block_num() - 1; ++i) { res += __builtin_popcountll(blocks[i]); } const std::size_t num = n - ((block_num() - 1) << log_block_size); return res + __builtin_popcountll(get_lower_bits(blocks.back(), num)); } // Returns the position of first set bit. If there is no such positions, then returns size(). int find_first() const { if (empty()) return size(); for (std::size_t i = 0; i < block_num(); ++i) { if (blocks[i] != 0) return std::min(n, __builtin_ctzll(blocks[i]) | (i << log_block_size)); } return n; } // Returns the position of first set bit after the given position (exclusive). If there is no such positions, then returns size(). int find_next(std::size_t pos) const { std::size_t i = block_index(++pos); if (i >= blocks.size()) return n; block upper = mask_upper_bits(blocks[i], block_size - bit_index(pos)); if (upper != 0) return std::min(n, __builtin_ctzll(upper) | (i << log_block_size)); while (++i < block_num()) { if (blocks[i] != 0) return std::min(n, __builtin_ctzll(blocks[i]) | (i << log_block_size)); } return n; } bool has_intersection(const DynamicBitSet& y) const { if (n > y.n) return y.has_intersection(*this); if (empty()) return false; for (std::size_t i = 0; i < block_num() - 1; ++i) { if (blocks[i] & y.blocks[i]) return true; } const std::size_t num = n - ((block_num() - 1) << log_block_size); return get_lower_bits(blocks.back(), num) & y.blocks[block_num() - 1]; } bool is_disjoint(const DynamicBitSet& y) const { return not has_intersection(y); } private: static constexpr std::size_t block_index(std::size_t i) { return i >> log_block_size; } static constexpr std::size_t bit_index(std::size_t i) { return i & (block_size - 1); } static constexpr block get_lower_bits(block b, std::size_t num) { return num ? (b << (block_size - num) >> (block_size - num)) : block(0); } static constexpr block get_upper_bits(block b, std::size_t num) { return num ? (b >> (block_size - num)) : block(0); } static constexpr block get_range_bits(block b, std::size_t l, std::size_t r) { return l < r ? b << (block_size - r) >> (block_size - r + l) : block(0); } static constexpr block mask_lower_bits(block b, std::size_t num) { return get_lower_bits(b, num); } static constexpr block mask_upper_bits(block b, std::size_t num) { return num ? (b >> (block_size - num) << (block_size - num)) : block(0); } static constexpr block mask_range_bits(block b, std::size_t l, std::size_t r) { return l < r ? b << (block_size - r) >> (block_size - r + l) << l : block(0); } std::size_t block_num() const { return blocks.size(); } }; } // namespace suisen #line 7 "test/src/datastructure/util/dynamic_bitset/dummy.test.cpp" using suisen::DynamicBitSet; template <std::size_t n> bool operator==(const DynamicBitSet& dbs, const std::bitset<n>& bs) { if (dbs.size() != int(n)) return false; for (std::size_t i = 0; i < n; ++i) if (dbs[i] != bs[i]) return false; return true; } template <std::size_t n> bool operator==(const std::bitset<n>& bs, const DynamicBitSet& dbs) { return dbs == bs; } template <std::size_t n> bool operator!=(const DynamicBitSet& dbs, const std::bitset<n>& bs) { return not (dbs == bs); } template <std::size_t n> bool operator!=(const std::bitset<n>& bs, const DynamicBitSet& dbs) { return dbs != bs; } void test_empty() { assert(DynamicBitSet(0).empty()); assert(not DynamicBitSet(1).empty()); } void test_size() { assert(DynamicBitSet(0).size() == 0); assert(DynamicBitSet(1).size() == 1); assert(DynamicBitSet(64).size() == 64); } void test_resize() { DynamicBitSet bs; bs.resize(35, true); assert(bs.size() == 35); for (int i = 0; i < 35; ++i) assert(bs[i]); bs.resize(1026, false); assert(bs.size() == 1026); for (int i = 0; i < 35; ++i) assert(bs[i]); for (int i = 35; i < 1026; ++i) assert(not bs[i]); bs.resize(78); assert(bs.size() == 78); for (int i = 0; i < 35; ++i) assert(bs[i]); for (int i = 35; i < 78; ++i) assert(not bs[i]); bs.resize(512, true); assert(bs.size() == 512); for (int i = 0; i < 35; ++i) assert(bs[i]); for (int i = 35; i < 78; ++i) assert(not bs[i]); for (int i = 78; i < 512; ++i) assert(bs[i]); bs.resize(128, false); assert(bs.size() == 128); for (int i = 0; i < 35; ++i) assert(bs[i]); for (int i = 35; i < 78; ++i) assert(not bs[i]); for (int i = 78; i < 128; ++i) assert(bs[i]); } void test_push_back() { DynamicBitSet bs; for (int i = 0; i < 1000; ++i) { bs.push_back(i & 1); assert(bs.size() == i + 1); for (int j = 0; j <= i; ++j) assert(bs[j] == (j & 1)); } } void test_pop_back() { DynamicBitSet bs; for (int i = 0; i < 1000; ++i) { bs.push_back(i & 1); } for (int i = 0; i < 1000; ++i) { bs.pop_back(); assert(bs.size() == 999 - i); for (int j = 0; j < 999 - i; ++j) assert(bs[j] == (j & 1)); } } void test_eq() { DynamicBitSet x(10, true); DynamicBitSet y(10); for (int i = 0; i < 10; ++i) y[i] = true; assert(x == y); x.resize(516, false); y.resize(516, false); assert(x == y); x.resize(100); y.resize(200); x.resize(300, true); y.resize(300, true); for (int i = 100; i < 200; ++i) y[i] = true; assert(x == y); } void test_neq() { DynamicBitSet x(10); DynamicBitSet y; assert(x != y); y.resize(5); assert(x != y); y.resize(64, true); assert(x != y); y.resize(10); assert(x != y); x.resize(500); y.resize(500); for (int i = 5; i < 10; ++i) x[i] = true; assert(x == y); y[499] = true; assert(x != y); y[499] = false; assert(x == y); y[256] = true; assert(x != y); y[256] = false; assert(x == y); y[255] = true; assert(x != y); } void test_lt() { DynamicBitSet x(100), y(100); assert(not (x < y)); x[56] = true; assert(not (x < y)); y[56] = true; assert(not (x < y)); y[99] = true; assert(x < y); x.resize(200), y.resize(200); x[100] = true; assert(not (x < y)); y[100] = true; assert(x < y); x[99] = true; assert(not (x < y)); y[199] = true; assert(x < y); y[199] = false; y[128] = true; assert(x < y); y[128] = false; y[127] = true; assert(x < y); } void test_leq() { DynamicBitSet x(100), y(100); assert(x <= y); x[56] = true; assert(not (x <= y)); y[56] = true; assert(x <= y); y[99] = true; assert(x <= y); x.resize(200), y.resize(200); x[100] = true; assert(not (x <= y)); y[100] = true; assert(x <= y); x[99] = true; assert(x <= y); y[199] = true; assert(x <= y); y[199] = false; y[128] = true; assert(x <= y); y[128] = false; y[127] = true; assert(x <= y); } void test_gt() { DynamicBitSet x(100), y(100); assert(not (x > y)); x[56] = true; assert(x > y); y[56] = true; assert(not (x > y)); y[99] = true; assert(not (x > y)); x.resize(200), y.resize(200); x[100] = true; assert(x > y); y[100] = true; assert(not (x > y)); x[99] = true; assert(not (x > y)); y[199] = true; assert(not (x > y)); y[199] = false; y[128] = true; assert(not (x > y)); y[128] = false; y[127] = true; assert(not (x > y)); } void test_geq() { DynamicBitSet x(100), y(100); assert(x >= y); x[56] = true; assert(x >= y); y[56] = true; assert(x >= y); y[99] = true; assert(not (x >= y)); x.resize(200), y.resize(200); x[100] = true; assert(x >= y); y[100] = true; assert(not (x >= y)); x[99] = true; assert(x >= y); y[199] = true; assert(not (x >= y)); y[199] = false; y[128] = true; assert(not (x >= y)); y[128] = false; y[127] = true; assert(not (x >= y)); } void test_cast_bool() { DynamicBitSet x; assert(not x); x.resize(100); assert(not x); x[99] = true; assert(x); } void test_and() { constexpr int n = 353; std::bitset<n> bs1, bs2; DynamicBitSet dbs1(n), dbs2(n); for (int i = 0; i < n; ++i) { bs1[i] = i % 3 == 0; dbs1[i] = i % 3 == 0; } for (int i = 0; i < n; ++i) { bs2[i] = i % 5 == 0; dbs2[i] = i % 5 == 0; } auto bs = bs1 & bs2; auto dbs = dbs1 & dbs2; assert(bs == dbs); } void test_or() { constexpr int n = 353; std::bitset<n> bs1, bs2; DynamicBitSet dbs1(n), dbs2(n); for (int i = 0; i < n; ++i) { bs1[i] = i % 3 == 0; dbs1[i] = i % 3 == 0; } for (int i = 0; i < n; ++i) { bs2[i] = i % 5 == 0; dbs2[i] = i % 5 == 0; } auto bs = bs1 | bs2; auto dbs = dbs1 | dbs2; assert(bs == dbs); } void test_xor() { constexpr int n = 353; std::bitset<n> bs1, bs2; DynamicBitSet dbs1(n), dbs2(n); for (int i = 0; i < n; ++i) { bs1[i] = i % 3 == 0; dbs1[i] = i % 3 == 0; } for (int i = 0; i < n; ++i) { bs2[i] = i % 5 == 0; dbs2[i] = i % 5 == 0; } auto bs = bs1 ^ bs2; auto dbs = dbs1 ^ dbs2; assert(bs == dbs); } void test_shift_r() { constexpr int n = 353; std::bitset<n> bs; DynamicBitSet dbs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 == 0; dbs[i] = i % 3 == 0; } for (std::size_t i = 0; i < n; ++i) { assert((bs >> i) == (dbs >> i)); } } void test_shift_l() { constexpr int n = 353; std::bitset<n> bs; DynamicBitSet dbs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 == 0; dbs[i] = i % 3 == 0; } for (std::size_t i = 0; i < n; ++i) { assert((bs << i) == (dbs << i)); } } void test_neg() { constexpr int n = 353; std::bitset<n> bs; DynamicBitSet dbs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 == 0; dbs[i] = i % 3 == 0; } assert(~bs == ~dbs); } void test_get_set() { constexpr int n = 2349; DynamicBitSet bs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 != 0; } for (int i = 0; i < n; ++i) { assert(bs[i] == (i % 3 != 0)); } } void test_range_set() { constexpr int n = 513; std::bitset<n> bs; DynamicBitSet dbs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 == 0; dbs[i] = i % 3 == 0; } auto range_set_dbs = [&](int l, int r) { auto dbs2 = dbs; dbs2.range_set(l, r); return dbs2; }; auto range_set_bs = [&](int l, int r) { auto bs2 = bs; for (int i = l; i < r; ++i) bs2[i] = true; return bs2; }; for (int l = 0; l <= n; ++l) for (int r = l; r <= n; ++r) { assert(range_set_bs(l, r) == range_set_dbs(l, r)); } } void test_range_reset() { constexpr int n = 513; std::bitset<n> bs; DynamicBitSet dbs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 == 0; dbs[i] = i % 3 == 0; } auto range_reset_dbs = [&](int l, int r) { auto dbs2 = dbs; dbs2.range_reset(l, r); return dbs2; }; auto range_reset_bs = [&](int l, int r) { auto bs2 = bs; for (int i = l; i < r; ++i) bs2[i] = false; return bs2; }; for (int l = 0; l <= n; ++l) for (int r = l; r <= n; ++r) { assert(range_reset_bs(l, r) == range_reset_dbs(l, r)); } } void test_range_flip() { constexpr int n = 513; std::bitset<n> bs; DynamicBitSet dbs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 == 0; dbs[i] = i % 3 == 0; } auto range_flip_dbs = [&](int l, int r) { auto dbs2 = dbs; dbs2.range_flip(l, r); return dbs2; }; auto range_flip_bs = [&](int l, int r) { auto bs2 = bs; for (int i = l; i < r; ++i) bs2[i].flip(); return bs2; }; for (int l = 0; l <= n; ++l) for (int r = l; r <= n; ++r) { assert(range_flip_bs(l, r) == range_flip_dbs(l, r)); } } void test_range_update() { constexpr int n = 513; std::bitset<n> bs; DynamicBitSet dbs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 == 0; dbs[i] = i % 3 == 0; } auto range_update_dbs = [&](int l, int r, bool val) { auto dbs2 = dbs; dbs2.range_update(l, r, val); return dbs2; }; auto range_update_bs = [&](int l, int r, bool val) { auto bs2 = bs; for (int i = l; i < r; ++i) bs2[i] = val; return bs2; }; for (bool b : { false, true }) { for (int l = 0; l <= n; ++l) for (int r = l; r <= n; ++r) { assert(range_update_bs(l, r, b) == range_update_dbs(l, r, b)); } } } void test_range_count() { constexpr int n = 513; std::bitset<n> bs; DynamicBitSet dbs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 == 0; dbs[i] = i % 3 == 0; } auto range_count_dbs = [&](int l, int r) { return dbs.range_count(l, r); }; auto range_count_bs = [&](int l, int r) { int res = 0; for (int i = l; i < r; ++i) res += bs[i]; return res; }; for (int l = 0; l <= n; ++l) for (int r = l; r <= n; ++r) { assert(range_count_bs(l, r) == range_count_dbs(l, r)); } } void test_all() { DynamicBitSet x; assert(x.all()); x.push_back(true); assert(x.all()); x[0] = false; assert(not x.all()); x.resize(129, true); assert(not x.all()); x[0] = true; assert(x.all()); x[128] = false; assert(not x.all()); } void test_none() { DynamicBitSet x; assert(x.none()); x.push_back(true); assert(not x.none()); x[0] = false; assert(x.none()); x.resize(129, false); assert(x.none()); x[0] = true; assert(not x.none()); x[0] = false; assert(x.none()); x[128] = true; assert(not x.none()); } void test_any() { DynamicBitSet x; assert(not x.any()); x.push_back(true); assert(x.any()); x[0] = false; assert(not x.any()); x.resize(129, false); assert(not x.any()); x[0] = true; assert(x.any()); x[0] = false; assert(not x.any()); x[128] = true; assert(x.any()); } void test_count() { DynamicBitSet x; assert(x.count() == 0); x.resize(10); assert(x.count() == 0); x[3] = true; assert(x.count() == 1); x.resize(176, true); assert(x.count() == 167); } void test_set() { DynamicBitSet x; x.set(); assert(x.count() == 0); x.resize(20, false); x.set(); assert(x.count() == 20); x.resize(1238); x.set(); assert(x.count() == 1238); } void test_reset() { DynamicBitSet x; x.reset(); assert(x.count() == 0); x.resize(20, true); x.reset(); assert(x.count() == 0); x.resize(1238); x.reset(); assert(x.count() == 0); } void test_find() { constexpr int n = 513; std::bitset<n> bs; DynamicBitSet dbs(n); for (int i = 0; i < n; ++i) { bs[i] = i % 3 == 0; dbs[i] = i % 3 == 0; } int i = bs._Find_first(), j = dbs.find_first(); for (; i < n and j < n; i = bs._Find_next(i), j = dbs.find_next(j)) { assert(i == j); } assert(i == n and j == n); } void test_has_intersectoin() { DynamicBitSet x(10, true), y; assert(not x.has_intersection(y)); y.resize(10); y[9] = true; assert(x.has_intersection(y)); y[9] = false; y.resize(123); y[122] = true; assert(not x.has_intersection(y)); x.resize(1230); x[122] = true; assert(x.has_intersection(y)); } void test_is_disjoint() { DynamicBitSet x(10, true), y; assert(x.is_disjoint(y)); y.resize(10); y[9] = true; assert(not x.is_disjoint(y)); y[9] = false; y.resize(123); y[122] = true; assert(x.is_disjoint(y)); x.resize(1230); x[122] = true; assert(not x.is_disjoint(y)); } void test() { test_empty(); test_size(); test_resize(); test_push_back(); test_pop_back(); test_eq(); test_neq(); test_lt(); test_leq(); test_gt(); test_geq(); test_cast_bool(); test_and(); test_or(); test_xor(); test_shift_r(); test_shift_l(); test_neg(); test_get_set(); test_range_set(); test_range_reset(); test_range_flip(); test_range_update(); test_range_count(); test_all(); test_none(); test_any(); test_count(); test_set(); test_reset(); test_find(); test_has_intersectoin(); test_is_disjoint(); } int main() { test(); std::cout << "Hello World" << std::endl; return 0; }