cp-library-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub NotLeonian/cp-library-cpp

:heavy_check_mark: test/src/datastructure/util/dynamic_bitset/dummy.test.cpp

Depends on

Code

#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_intersection() {
    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_intersection();
    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_intersection() {
    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_intersection();
    test_is_disjoint();
}

int main() {
    test();
    std::cout << "Hello World" << std::endl;
    return 0;
}
Back to top page