matsutaku-library
This documentation is automatically generated by competitive-verifier/competitive-verifier
test/standalone/bitmap_test.cpp
- View this file on GitHub
- Last update: 2024-07-11 22:21:57+09:00
Code
#define STANDALONE
#include "include/mtl/bitmap.hpp"
#include <iostream>
int main() {
const int n = 1e6;
std::vector<bool> B(n);
int c = 0;
int k = 0;
std::vector<int> rank(n), select(n);
for (int i = 0; i < n; i++) {
rank[i] = c;
B[i] = rand()%2;
c += B[i];
if (B[i]) select[k++] = i;
}
Bitmap bm(B.begin(), B.end());
// get
for (int i = 0; i < n; i++) {
auto v = bm.get(i);
if (v != B[i]) {
std::cout << "Failed get: " << i << " bm.get " << v << " != B " << B[i] << std::endl;
return 1;
}
}
// rank
for (int i = 0; i < n; i++) {
auto v = bm.rank(i);
if (v != rank[i]) {
std::cout << "Failed rank: " << i << " bm.rank " << v << " != rank " << rank[i] << std::endl;
return 1;
}
}
// select
for (int i = 1; i < k; i++) {
auto v = bm.select(i);
if (v != select[i]) {
std::cout << "Failed select: " << i << " bm.select " << v << " != select " << select[i] << std::endl;
return 1;
}
}
std::cout << "OK" << std::endl;
}
#line 1 "test/standalone/bitmap_test.cpp"
#define STANDALONE
#line 2 "include/mtl/bit_manip.hpp"
#include <cstdint>
#include <cassert>
#if __cplusplus >= 202002L
#ifndef MTL_CPP20
#define MTL_CPP20
#endif
#include <bit>
#endif
namespace bm {
/// Count 1s for each 8 bits
inline constexpr uint64_t popcnt_e8(uint64_t x) {
x = (x & 0x5555555555555555) + ((x>>1) & 0x5555555555555555);
x = (x & 0x3333333333333333) + ((x>>2) & 0x3333333333333333);
x = (x & 0x0F0F0F0F0F0F0F0F) + ((x>>4) & 0x0F0F0F0F0F0F0F0F);
return x;
}
/// Count 1s
inline constexpr unsigned popcnt(uint64_t x) {
#ifdef MTL_CPP20
return std::popcount(x);
#else
return (popcnt_e8(x) * 0x0101010101010101) >> 56;
#endif
}
/// Alias to mtl::popcnt(x)
constexpr unsigned popcount(uint64_t x) {
return popcnt(x);
}
/// Count trailing 0s. s.t. *11011000 -> 3
inline constexpr unsigned ctz(uint64_t x) {
#ifdef MTL_CPP20
return std::countr_zero(x);
#else
return popcnt((x & (-x)) - 1);
#endif
}
/// Alias to mtl::ctz(x)
constexpr unsigned countr_zero(uint64_t x) {
return ctz(x);
}
/// Count trailing 1s. s.t. *11011011 -> 2
inline constexpr unsigned cto(uint64_t x) {
#ifdef MTL_CPP20
return std::countr_one(x);
#else
return ctz(~x);
#endif
}
/// Alias to mtl::cto(x)
constexpr unsigned countr_one(uint64_t x) {
return cto(x);
}
inline constexpr unsigned ctz8(uint8_t x) {
return x == 0 ? 8 : popcnt_e8((x & (-x)) - 1);
}
/// [00..0](8bit) -> 0, [**..*](not only 0) -> 1
inline constexpr uint8_t summary(uint64_t x) {
constexpr uint64_t hmask = 0x8080808080808080ull;
constexpr uint64_t lmask = 0x7F7F7F7F7F7F7F7Full;
auto a = x & hmask;
auto b = x & lmask;
b = hmask - b;
b = ~b;
auto c = (a | b) & hmask;
c *= 0x0002040810204081ull;
return uint8_t(c >> 56);
}
/// Extract target area of bits
inline constexpr uint64_t bextr(uint64_t x, unsigned start, unsigned len) {
uint64_t mask = len < 64 ? (1ull<<len)-1 : 0xFFFFFFFFFFFFFFFFull;
return (x >> start) & mask;
}
/// 00101101 -> 00111111 -count_1s-> 6
inline constexpr unsigned log2p1(uint8_t x) {
if (x & 0x80)
return 8;
uint64_t p = uint64_t(x) * 0x0101010101010101ull;
p -= 0x8040201008040201ull;
p = ~p & 0x8080808080808080ull;
p = (p >> 7) * 0x0101010101010101ull;
p >>= 56;
return p;
}
/// 00101100 -mask_mssb-> 00100000 -to_index-> 5
inline constexpr unsigned mssb8(uint8_t x) {
assert(x != 0);
return log2p1(x) - 1;
}
/// 00101100 -mask_lssb-> 00000100 -to_index-> 2
inline constexpr unsigned lssb8(uint8_t x) {
assert(x != 0);
return popcnt_e8((x & -x) - 1);
}
/// Count leading 0s. 00001011... -> 4
inline constexpr unsigned clz(uint64_t x) {
#ifdef MTL_CPP20
return std::countl_zero(x);
#else
if (x == 0)
return 64;
auto i = mssb8(summary(x));
auto j = mssb8(bextr(x, 8 * i, 8));
return 63 - (8 * i + j);
#endif
}
/// Alias to mtl::clz(x)
constexpr unsigned countl_zero(uint64_t x) {
return clz(x);
}
/// Count leading 1s. 11110100... -> 4
inline constexpr unsigned clo(uint64_t x) {
#ifdef MTL_CPP20
return std::countl_one(x);
#else
return clz(~x);
#endif
}
/// Alias to mtl::clo(x)
constexpr unsigned countl_one(uint64_t x) {
return clo(x);
}
inline constexpr unsigned clz8(uint8_t x) {
return x == 0 ? 8 : 7 - mssb8(x);
}
inline constexpr uint64_t bit_reverse(uint64_t x) {
x = ((x & 0x00000000FFFFFFFF) << 32) | ((x & 0xFFFFFFFF00000000) >> 32);
x = ((x & 0x0000FFFF0000FFFF) << 16) | ((x & 0xFFFF0000FFFF0000) >> 16);
x = ((x & 0x00FF00FF00FF00FF) << 8) | ((x & 0xFF00FF00FF00FF00) >> 8);
x = ((x & 0x0F0F0F0F0F0F0F0F) << 4) | ((x & 0xF0F0F0F0F0F0F0F0) >> 4);
x = ((x & 0x3333333333333333) << 2) | ((x & 0xCCCCCCCCCCCCCCCC) >> 2);
x = ((x & 0x5555555555555555) << 1) | ((x & 0xAAAAAAAAAAAAAAAA) >> 1);
return x;
}
/// Check if x is power of 2. 00100000 -> true, 00100001 -> false
constexpr bool has_single_bit(uint64_t x) noexcept {
#ifdef MTL_CPP20
return std::has_single_bit(x);
#else
return x != 0 && (x & (x - 1)) == 0;
#endif
}
/// Bit width needs to represent x. 00110110 -> 6
constexpr int bit_width(uint64_t x) noexcept {
#ifdef MTL_CPP20
return std::bit_width(x);
#else
return 64 - clz(x);
#endif
}
/// Ceil power of 2. 00110110 -> 01000000
constexpr uint64_t bit_ceil(uint64_t x) {
#ifdef MTL_CPP20
return std::bit_ceil(x);
#else
if (x == 0) return 1;
return 1ull << bit_width(x - 1);
#endif
}
/// Floor power of 2. 00110110 -> 00100000
constexpr uint64_t bit_floor(uint64_t x) {
#ifdef MTL_CPP20
return std::bit_floor(x);
#else
if (x == 0) return 0;
return 1ull << (bit_width(x) - 1);
#endif
}
} // namespace bm
#line 3 "include/mtl/fenwick_tree.hpp"
#include <cstddef>
#include <vector>
template <class T>
class FenwickTree {
private:
std::vector<T> tree_;
public:
FenwickTree() = default;
explicit FenwickTree(size_t size) : tree_(size+1) {}
size_t size() const { return tree_.size()-1; }
template <class Iter>
explicit FenwickTree(Iter begin, Iter end) : FenwickTree(std::distance(begin, end)) {
size_t i = 1;
for (auto it = begin; it != end; ++it) {
tree_[i] = tree_[i] + *it;
auto j = i + (i&(-i));
if (j < tree_.size())
tree_[j] = tree_[j] + tree_[i];
++i;
}
}
template<class V>
void add(size_t index, const V& x) {
for (size_t i = index+1; i < tree_.size(); i += i&(-i))
tree_[i] = tree_[i] + x;
}
T sum(size_t index) const {
T sum = 0;
for (size_t i = index+1; i > 0; i -= i&(-i))
sum = sum + tree_[i];
return sum;
}
T range_sum(size_t l, size_t r) const {
auto sl = l > 0 ? sum(l-1) : 0;
auto sr = r > 0 ? sum(r-1) : 0;
return sr - sl;
}
/// @brief Alias of range_sum(l, r)
T sum(size_t l, size_t r) const {
return range_sum(l, r);
}
template<class V>
size_t lower_bound(const V& _sum) const {
size_t ret = 0;
T s = 0;
for (int k = 63-bm::clz(size()); k >= 0; k--) {
size_t j = ret | (1ull<<k);
if (j < tree_.size() and s + tree_[j] < _sum) {
s = s + tree_[j];
ret = j;
}
}
return ret;
}
};
#line 6 "include/mtl/bitmap.hpp"
#include <array>
#line 8 "include/mtl/bitmap.hpp"
#include <iostream>
class Bitmap {
public:
using size_type = int;
using RSQ = FenwickTree<size_type>;
private:
RSQ rsq;
std::vector<uint64_t> bv;
size_t word_size(size_t sz) const {
return (sz + 64-1) / 64;
}
std::array<std::array<uint8_t, 9>, 1<<8> sel_tb;
constexpr void init_sel_tb() {
for (int i = 0; i < 1<<8; i++) {
int c = 0;
int x = i;
for (int j = 0; j < 8; j++) {
if (x & 1)
sel_tb[i][++c] = j;
x >>= 1;
}
}
}
public:
explicit Bitmap(size_t size = 0, bool init_b = false)
: rsq(word_size(size)),
bv(word_size(size), init_b ? 0xFFFFFFFFFFFFFFFF : 0) {
init_sel_tb();
}
template<typename It>
explicit Bitmap(It begin, It end) : Bitmap(end-begin) {
using traits = std::iterator_traits<It>;
static_assert(std::is_convertible<typename traits::value_type,
bool>::value, "");
static_assert(std::is_base_of<std::random_access_iterator_tag,
typename traits::iterator_category>::value, "");
size_type i = 0;
for (auto it = begin; it != end; ++it)
set(i++, *it);
}
bool get(size_t i) const {
return (bv[i/64] >> (i%64)) & 1ull;
}
void set(size_t i, bool b) {
int q = i/64, r = i%64;
rsq.add(q, (int) b - get(i));
if (b) bv[q] |= 1ull<<r;
else bv[q] &= ~(1ull<<r);
}
/* Count 1s in [0, i) */
size_type rank(size_t i) const {
if (i == 0) return 0;
int b = i/64;
return (size_type) (b > 0 ? rsq.sum(b-1) : 0)
+ bm::popcnt(bv[i/64] & ((1ull<<(i%64))-1));
}
/* Position (0-indexed) of the (n+1) th 1 */
size_type select(size_t n) const { // 0-index
n += 1; // to 1-index
int s = rsq.lower_bound(n);
int m = n - (s > 0 ? rsq.sum(s-1) : 0);
uint64_t w = bv[s];
auto x = bm::popcnt_e8(w) * 0x0101010101010100ull; // Cumulative sum for 8bit blocks.
auto b_rank = (const uint8_t*) &x;
int b = 0;
{
int d = 8;
while (d > 1) {
int c = b + d/2;
if (b_rank[c] < m)
b = c;
d /= 2;
}
}
int k = m - b_rank[b];
int B = ((const uint8_t*) &w)[b];
return 64 * s + 8 * b + sel_tb[B][k];
}
};
#line 4 "test/standalone/bitmap_test.cpp"
int main() {
const int n = 1e6;
std::vector<bool> B(n);
int c = 0;
int k = 0;
std::vector<int> rank(n), select(n);
for (int i = 0; i < n; i++) {
rank[i] = c;
B[i] = rand()%2;
c += B[i];
if (B[i]) select[k++] = i;
}
Bitmap bm(B.begin(), B.end());
// get
for (int i = 0; i < n; i++) {
auto v = bm.get(i);
if (v != B[i]) {
std::cout << "Failed get: " << i << " bm.get " << v << " != B " << B[i] << std::endl;
return 1;
}
}
// rank
for (int i = 0; i < n; i++) {
auto v = bm.rank(i);
if (v != rank[i]) {
std::cout << "Failed rank: " << i << " bm.rank " << v << " != rank " << rank[i] << std::endl;
return 1;
}
}
// select
for (int i = 1; i < k; i++) {
auto v = bm.select(i);
if (v != select[i]) {
std::cout << "Failed select: " << i << " bm.select " << v << " != select " << select[i] << std::endl;
return 1;
}
}
std::cout << "OK" << std::endl;
}