matsutaku-library
This documentation is automatically generated by competitive-verifier/competitive-verifier
test/standalone/skewbinary_list_test.cpp
- View this file on GitHub
- Last update: 2024-07-11 22:21:57+09:00
Code
#define STANDALONE
#include "include/mtl/skewbinary_list.hpp"
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <random>
int main() {
const int Max = 1e5;
int n = Max;
std::vector<int> values(n);
for (int& v : values) v = rand();
// PersistentSkewbinaryList<int> S;
// for (int v : values) {
// S = S.pushed(v);
// }
// std::reverse(values.begin(), values.end());
PersistentSkewbinaryList<int> S(values.begin(), values.end());
// S.print_for_debug();
{ // Test random-access
// std::cout << "random-access" << std::endl;
for (int i = 0; i < S.size(); i++) {
int get = S.get_at(i);
if (get != values[i]) {
std::cout << "get " << i << " " << get << " != " << values[i] << std::endl;
assert(false);
return 1;
}
}
}
{ // Test pop
// std::cout << "pop" << std::endl;
auto P = S;
int popcount = 0;
while (!P.empty()) {
auto get = P.front();
if (get != values[popcount]) {
std::cout << "pop " << popcount << " " << get << " != " << values[popcount] << std::endl;
assert(false);
return 1;
}
P = P.popped();
popcount++;
}
}
{ // Test drop
// std::cout << "drop" << std::endl;
auto O = S;
int dropcount = 0;
std::uniform_real_distribution<double> dist(0,1);
std::default_random_engine eng;
while (!O.empty()) {
auto get = O.front();
if (get != values[dropcount]) {
std::cout << "drop " << dropcount << " " << get << " != " << values[dropcount] << std::endl;
assert(false);
return 1;
}
int off = std::round((std::exp(dist(eng))-1) * O.size());
off = std::min(std::max(off, 1), (int)O.size());
O = O.dropped(off);
dropcount += off;
}
}
{ // Test update
for (int t = 0; t < 100; t++) {
int idx = rand() % n;
values[idx] = rand();
S = S.updated_at(idx, values[idx]);
for (int i = 0; i < n; i++) {
auto get = S.get_at(i);
if (get != values[i]) {
std::cout << "update " << idx << " " << get << " != " << values[i] << std::endl;
assert(false);
return 1;
}
}
}
}
{ // Test iterator
// std::cout << "iter" << std::endl;
int i = 0;
for (auto v : S) {
if (v != values[i]) {
std::cout << "iter get " << i << " " << v << " != " << values[i] << std::endl;
assert(false);
return 1;
}
++i;
}
}
std::cout << "OK" << std::endl;
}
#line 1 "test/standalone/skewbinary_list_test.cpp"
#define STANDALONE
#line 2 "include/mtl/skewbinary_list.hpp"
#include <memory>
#include <vector>
#include <stack>
#include <cassert>
#include <cstddef>
#include <type_traits>
#include <iterator>
#include <iostream>
#line 2 "include/mtl/bit_manip.hpp"
#include <cstdint>
#line 4 "include/mtl/bit_manip.hpp"
#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 12 "include/mtl/skewbinary_list.hpp"
/*
* Persistent purely functional random-access list
*/
template<typename T>
class PersistentSkewbinaryList {
public:
using value_type = T;
class iterator;
private:
struct Digit;
struct Node;
using digit_pointer = std::shared_ptr<Digit>;
using node_pointer = std::shared_ptr<Node>;
struct Node {
T v;
uint8_t dig;
node_pointer left, right;
Node(const T& v, uint8_t dig = 1) : v(v), dig(dig), left(nullptr), right(nullptr) {}
size_t size() const {
return (1ull<<dig) - 1;
}
bool is_lump() const {
return dig > 1 and left == nullptr;
}
};
struct Digit {
node_pointer ch;
digit_pointer next;
Digit(node_pointer root, digit_pointer right) : ch(root), next(right) {}
};
digit_pointer root_;
size_t size_;
private:
explicit PersistentSkewbinaryList(digit_pointer root, size_t size=0) : root_(root), size_(size) {}
void _push_node(node_pointer u) {
root_ = std::make_shared<Digit>(u, root_);
size_ += u->size();
}
public:
PersistentSkewbinaryList() : root_(nullptr), size_(0) {}
template<class InputIt>
PersistentSkewbinaryList(InputIt begin, InputIt end) : PersistentSkewbinaryList() {
using traits = std::iterator_traits<InputIt>;
using value_type = typename traits::value_type;
static_assert(std::is_convertible<T, value_type>::value);
using category = typename traits::iterator_category;
if constexpr (std::is_base_of<std::bidirectional_iterator_tag, category>::value) {
for (auto it = std::prev(end); ; --it) {
*this = pushed(*it);
if (it == begin)
break;
}
} else if constexpr (std::is_base_of<std::forward_iterator_tag, category>::value) {
std::stack<T> s(begin, end);
while (!s.empty()) {
_push_node(std::make_shared<Node>(s.top()));
s.pop();
}
}
}
PersistentSkewbinaryList(std::initializer_list<T> list) : PersistentSkewbinaryList(list.begin(), list.end()) {}
size_t size() const { return size_; }
bool empty() const { return size() == 0; }
T front() const {
return root_->ch->v;
}
[[nodiscard]] PersistentSkewbinaryList pushed(const T& v) const {
if (root_ and root_->next and root_->ch->dig == root_->next->ch->dig) {
auto new_u = std::make_shared<Node>(v, root_->ch->dig+1);
new_u->left = root_->ch;
new_u->right = root_->next->ch;
auto new_root = std::make_shared<Digit>(new_u, root_->next->next);
return PersistentSkewbinaryList(new_root, size()+1);
} else {
auto new_root = std::make_shared<Digit>(std::make_shared<Node>(v), root_);
return PersistentSkewbinaryList(new_root, size()+1);
}
}
[[nodiscard]] PersistentSkewbinaryList popped() const {
if (root_->ch->size() > 1) {
if (!root_->ch->is_lump()) {
digit_pointer new_next = std::make_shared<Digit>(root_->ch->right, root_->next);
digit_pointer new_root = std::make_shared<Digit>(root_->ch->left, new_next);
return PersistentSkewbinaryList(new_root, size()-1);
} else {
node_pointer new_u = std::make_shared<Node>(root_->ch->v, root_->ch->dig-1);
digit_pointer new_next = std::make_shared<Digit>(new_u, root_->next);
digit_pointer new_root = std::make_shared<Digit>(new_u, new_next);
return PersistentSkewbinaryList(new_root, size()-1);
}
} else {
return PersistentSkewbinaryList(root_->next, size()-1);
}
}
T get_at(int i) const {
int j = i;
auto d = root_;
while (d->ch->size() <= j) {
j -= d->ch->size();
d = d->next;
}
auto u = d->ch;
while (j > 0) {
j--;
if (u->is_lump()) {
return u->v;
}
if (j < u->left->size()) {
u = u->left;
} else {
j -= u->left->size();
u = u->right;
}
}
return u->v;
}
[[nodiscard]] PersistentSkewbinaryList updated_at(int i, const T& v) const {
auto d = root_;
digit_pointer pd = std::make_shared<Digit>(nullptr, nullptr);
PersistentSkewbinaryList dst(pd, size());
int j = i;
while (j >= d->ch->size()) {
auto new_d = std::make_shared<Digit>(nullptr, nullptr);
pd->ch = d->ch;
pd->next = new_d;
pd = new_d;
j -= d->ch->size();
d = d->next;
}
auto u = d->ch;
node_pointer pu = std::make_shared<Node>(d->ch->v, d->ch->dig);
pd->ch = pu;
pd->next = d->next;
while (j > 0 and !u->is_lump()) {
j--;
if (j < u->left->size()) {
auto new_u = std::make_shared<Node>(u->left->v, u->left->dig);
pu->left = new_u;
pu->right = u->right;
pu = new_u;
u = u->left;
} else {
auto new_u = std::make_shared<Node>(u->right->v, u->right->dig);
pu->left = u->left;
pu->right = new_u;
pu = new_u;
j -= u->left->size();
u = u->right;
}
}
if (!u->is_lump()) {
pu->v = v;
pu->left = u->left;
pu->right = u->right;
} else {
int s = u->size() >> 1;
int dig = u->dig-1;
while (j > 0) {
j--;
pu->left = std::make_shared<Node>(u->v, dig);
pu->right = std::make_shared<Node>(u->v, dig);
if (j < s) {
pu = pu->left;
} else {
j -= s;
pu = pu->right;
}
s >>= 1;
dig--;
}
pu->v = v;
pu->left = pu->right = std::make_shared<Node>(u->v, dig);
}
return dst;
}
[[nodiscard]] PersistentSkewbinaryList dropped(const int i) const {
int j = i;
auto d = root_;
while (d and d->ch->size() <= j) {
j -= d->ch->size();
d = d->next;
}
if (!d) {
return PersistentSkewbinaryList();
}
PersistentSkewbinaryList dst(d->next); // dst.size_ is not correct value.
auto u = d->ch;
while (j > 0) {
j--;
if (j < u->left->size()) {
dst._push_node(u->right);
u = u->left;
} else {
j -= u->left->size();
u = u->right;
}
}
dst._push_node(u);
dst.size_ = size() - i;
return dst;
}
uint64_t sbdig_to_num(int dig) const {
return (1ull<<dig) - 1;
}
[[nodiscard]] PersistentSkewbinaryList extended(size_t n, const T& v) const {
PersistentSkewbinaryList dst(root_, size());
auto m = n;
while (m > 0) {
if (dst.root_ and dst.root_->next and dst.root_->ch->size() == dst.root_->next->ch->size()) {
auto new_u = std::make_shared<Node>(v, dst.root_->ch->dig+1);
new_u->left = dst.root_->ch;
new_u->right = dst.root_->next->ch;
dst.root_ = std::make_shared<Digit>(new_u, dst.root_->next->next);
dst.size_++;
m--;
} else if (m >= dst.root_->ch->size()) {
m -= dst.root_->ch->size();
dst._push_node(std::make_shared<Node>(v, dst.root_->ch->dig));
} else {
break;
}
}
while (m > 0) {
int dig = 63-bm::clz(m+1);
dst._push_node(std::make_shared<Node>(v, dig));
size_t s = (1ull<<dig) - 1;
assert(m >= s);
m -= s;
}
assert(dst.size_ == size() + n);
return dst;
}
public:
T operator[](size_t i) const {
return get_at(i);
}
class iterator {
public:
using value_type = T;
using iterator_category = std::forward_iterator_tag;
using difference_type = unsigned long long;
private:
digit_pointer root_;
public:
iterator(digit_pointer root) : root_(root) {}
value_type operator*() const { return root_->ch->v; }
bool operator==(iterator r) { return root_ == r.root_; }
bool operator!=(iterator r) { return root_ != r.root_; }
iterator& operator++() {
root_ = PersistentSkewbinaryList(root_).popped().root_;
return *this;
}
iterator operator++(int) {
auto dst = *this;
root_ = PersistentSkewbinaryList(root_).popped().root_;
return dst;
}
iterator operator+(difference_type x) const {
return iterator(PersistentSkewbinaryList(root_).dropped(x).root_);
}
iterator operator+=(difference_type x) {
root_ = PersistentSkewbinaryList(root_).dropped(x).root_;
return *this;
}
};
iterator begin() const {
return iterator(root_);
}
iterator end() const {
return iterator(nullptr);
}
};
#line 3 "test/standalone/skewbinary_list_test.cpp"
#line 7 "test/standalone/skewbinary_list_test.cpp"
#include <algorithm>
#include <cmath>
#include <random>
int main() {
const int Max = 1e5;
int n = Max;
std::vector<int> values(n);
for (int& v : values) v = rand();
// PersistentSkewbinaryList<int> S;
// for (int v : values) {
// S = S.pushed(v);
// }
// std::reverse(values.begin(), values.end());
PersistentSkewbinaryList<int> S(values.begin(), values.end());
// S.print_for_debug();
{ // Test random-access
// std::cout << "random-access" << std::endl;
for (int i = 0; i < S.size(); i++) {
int get = S.get_at(i);
if (get != values[i]) {
std::cout << "get " << i << " " << get << " != " << values[i] << std::endl;
assert(false);
return 1;
}
}
}
{ // Test pop
// std::cout << "pop" << std::endl;
auto P = S;
int popcount = 0;
while (!P.empty()) {
auto get = P.front();
if (get != values[popcount]) {
std::cout << "pop " << popcount << " " << get << " != " << values[popcount] << std::endl;
assert(false);
return 1;
}
P = P.popped();
popcount++;
}
}
{ // Test drop
// std::cout << "drop" << std::endl;
auto O = S;
int dropcount = 0;
std::uniform_real_distribution<double> dist(0,1);
std::default_random_engine eng;
while (!O.empty()) {
auto get = O.front();
if (get != values[dropcount]) {
std::cout << "drop " << dropcount << " " << get << " != " << values[dropcount] << std::endl;
assert(false);
return 1;
}
int off = std::round((std::exp(dist(eng))-1) * O.size());
off = std::min(std::max(off, 1), (int)O.size());
O = O.dropped(off);
dropcount += off;
}
}
{ // Test update
for (int t = 0; t < 100; t++) {
int idx = rand() % n;
values[idx] = rand();
S = S.updated_at(idx, values[idx]);
for (int i = 0; i < n; i++) {
auto get = S.get_at(i);
if (get != values[i]) {
std::cout << "update " << idx << " " << get << " != " << values[i] << std::endl;
assert(false);
return 1;
}
}
}
}
{ // Test iterator
// std::cout << "iter" << std::endl;
int i = 0;
for (auto v : S) {
if (v != values[i]) {
std::cout << "iter get " << i << " " << v << " != " << values[i] << std::endl;
assert(false);
return 1;
}
++i;
}
}
std::cout << "OK" << std::endl;
}