proconlib

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: tests/persistent_array.test.cpp

Depends on

Code

// competitive-verifier: STANDALONE

#include <cmath>
#include <iostream>
#include <iterator>
#include <random>
#include <ranges>
#include <utility>
#include <vector>
#include "tools/assert_that.hpp"
#include "tools/persistent_array.hpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  {
    const tools::persistent_array<int> a;
    assert_that(a.empty());
    assert_that(a.size() == 0);
  }
  assert_that(tools::persistent_array<int>::fully_released());
  {
    const tools::persistent_array<int> a{0};
    assert_that(!a.empty());
    assert_that(a.size() == 1);
    assert_that(a[0] == 0);
  }
  assert_that(tools::persistent_array<int>::fully_released());
  {
    const tools::persistent_array<int> a{0, 1};
    assert_that(!a.empty());
    assert_that(a.size() == 2);
    assert_that(a[0] == 0);
    assert_that(a[1] == 1);
  }
  assert_that(tools::persistent_array<int>::fully_released());
  {
    const tools::persistent_array<int> a{0, 1, 2};
    assert_that(!a.empty());
    assert_that(a.size() == 3);
    assert_that(a[0] == 0);
    assert_that(a[1] == 1);
    assert_that(a[2] == 2);
  }
  assert_that(tools::persistent_array<int>::fully_released());

  for (int n = 0; n <= 40; ++n) {
    {
      const tools::persistent_array<int> a(n);
      for (int i = 0; i < n; ++i) {
        assert_that(a[i] == 0);
      }
      assert_that(static_cast<std::vector<int>>(a) == std::vector<int>(n, 0));
    }
    assert_that(tools::persistent_array<int>::fully_released());
    {
      const tools::persistent_array<int> a(n, -1234);
      for (int i = 0; i < n; ++i) {
        assert_that(a[i] == -1234);
      }
      assert_that(static_cast<std::vector<int>>(a) == std::vector<int>(n, -1234));
    }
    assert_that(tools::persistent_array<int>::fully_released());
    {
      const tools::persistent_array<int> a(std::views::iota(0, n));
      for (int i = 0; i < n; ++i) {
        assert_that(a[i] == i);
      }
      assert_that(static_cast<std::vector<int>>(a) == (std::views::iota(0, n) | std::ranges::to<std::vector>()));
    }
    assert_that(tools::persistent_array<int>::fully_released());

    {
      std::vector<tools::persistent_array<int>> arrays(n + 1);
      arrays[0] = tools::persistent_array<int>(n, -1234);
      for (int i = 1; i <= n; ++i) {
        arrays[i] = arrays[i - 1].set(i - 1, i - 1);
      }
      for (int i = 0; i <= n; ++i) {
        assert_that(static_cast<std::vector<int>>(arrays[i]) == (std::views::iota(0, n) | std::views::transform([&](const auto j) { return j < i ? j : -1234; }) | std::ranges::to<std::vector>()));
      }
    }
    assert_that(tools::persistent_array<int>::fully_released());
    {
      std::vector<tools::persistent_array<int>> arrays(n + 1);
      arrays[0] = tools::persistent_array<int>(std::views::repeat(-1234, n));
      for (int i = 1; i <= n; ++i) {
        arrays[i] = arrays[i - 1].set(i - 1, i - 1);
      }
      for (int i = 0; i <= n; ++i) {
        assert_that(static_cast<std::vector<int>>(arrays[i]) == (std::views::iota(0, n) | std::views::transform([&](const auto j) { return j < i ? j : -1234; }) | std::ranges::to<std::vector>()));
      }
    }
    assert_that(tools::persistent_array<int>::fully_released());

    {
      std::vector<tools::persistent_array<int>> arrays(2 * n + 1);
      for (int i = 1; i <= n; ++i) {
        arrays[i] = arrays[i - 1].push_back(i - 1);
      }
      for (int i = n + 1; i <= 2 * n; ++i) {
        arrays[i] = arrays[i - 1].pop_back();
      }
      for (int i = 0; i <= 2 * n; ++i) {
        assert_that(static_cast<std::vector<int>>(arrays[i]) == (std::views::iota(0, n - std::abs(n - i)) | std::ranges::to<std::vector>()));
      }
    }
    assert_that(tools::persistent_array<int>::fully_released());
  }

  {
    const tools::persistent_array<int> a{3, 1, 4, 1, 5};
    auto b = a;
    const auto c = b;
    b = b.set(2, -1);
    assert_that(static_cast<std::vector<int>>(a) == std::vector<int>{3, 1, 4, 1, 5});
    assert_that(static_cast<std::vector<int>>(b) == std::vector<int>{3, 1, -1, 1, 5});
    assert_that(static_cast<std::vector<int>>(c) == std::vector<int>{3, 1, 4, 1, 5});
  }
  assert_that(tools::persistent_array<int>::fully_released());
  {
    tools::persistent_array<int> a{3, 1, 4, 1, 5};
    tools::persistent_array<int> b(std::move(a));
    assert_that(a.empty());
    assert_that(static_cast<std::vector<int>>(b) == std::vector<int>{3, 1, 4, 1, 5});

    const auto c = std::move(b);
    assert_that(a.empty());
    assert_that(b.empty());
    assert_that(static_cast<std::vector<int>>(c) == std::vector<int>{3, 1, 4, 1, 5});
  }
  assert_that(tools::persistent_array<int>::fully_released());

  {
    std::random_device seed_gen;
    std::mt19937 engine(seed_gen());
    std::uniform_int_distribution<int> t_dist(0, 3);
    std::uniform_int_distribution<int> x_dist(-1000000000, 1000000000);

    tools::persistent_array<int> a;
    std::vector<tools::persistent_array<int>> a_history;
    std::vector<int> naive;
    std::vector<std::vector<int>> naive_history;
    for (int q = 1; q <= 1000000; ++q) {
      const int t = a.empty() ? 0 : t_dist(engine);
      if (t <= 1) {
        const auto x = x_dist(engine);
        a = a.push_back(x);
        naive.push_back(x);
      } else if (t == 2) {
        a = a.pop_back();
        naive.pop_back();
      } else {
        const auto i = std::uniform_int_distribution<int>(0, a.size() - 1)(engine);
        const auto x = x_dist(engine);
        a = a.set(i, x);
        naive[i] = x;
      }

      if (q % 100000 == 0) {
        a_history.push_back(a);
        naive_history.push_back(naive);
      }
    }

    for (int q = 0; q < std::ssize(a_history); ++q) {
      assert_that(static_cast<std::vector<int>>(a_history[q]) == naive_history[q]);
    }
  }
  assert_that(tools::persistent_array<int>::fully_released());

  return 0;
}

#line 1 "tests/persistent_array.test.cpp"
// competitive-verifier: STANDALONE

#include <cmath>
#include <iostream>
#include <iterator>
#include <random>
#include <ranges>
#include <utility>
#include <vector>
#line 1 "tools/assert_that.hpp"



#line 5 "tools/assert_that.hpp"
#include <cstdlib>

#define assert_that_impl(cond, file, line, func) do {\
  if (!cond) {\
    std::cerr << file << ':' << line << ": " << func << ": Assertion `" << #cond << "' failed." << '\n';\
    std::exit(EXIT_FAILURE);\
  }\
} while (false)
#define assert_that(...) assert_that_impl((__VA_ARGS__), __FILE__, __LINE__, __func__)


#line 1 "tools/persistent_array.hpp"



#include <algorithm>
#include <array>
#include <cassert>
#include <concepts>
#include <functional>
#include <initializer_list>
#line 11 "tools/persistent_array.hpp"
#include <memory>
#line 13 "tools/persistent_array.hpp"
#include <stack>
#line 1 "tools/ceil_log2.hpp"



#line 1 "tools/bit_width.hpp"



#include <bit>
#line 6 "tools/bit_width.hpp"
#include <type_traits>
#line 1 "tools/is_signed.hpp"



#line 5 "tools/is_signed.hpp"

namespace tools {
  template <typename T>
  struct is_signed : std::is_signed<T> {};

  template <typename T>
  inline constexpr bool is_signed_v = tools::is_signed<T>::value;
}


#line 1 "tools/is_unsigned.hpp"



#line 5 "tools/is_unsigned.hpp"

namespace tools {
  template <typename T>
  struct is_unsigned : std::is_unsigned<T> {};

  template <typename T>
  inline constexpr bool is_unsigned_v = tools::is_unsigned<T>::value;
}


#line 1 "tools/make_unsigned.hpp"



#line 5 "tools/make_unsigned.hpp"

namespace tools {
  template <typename T>
  struct make_unsigned : std::make_unsigned<T> {};

  template <typename T>
  using make_unsigned_t = typename tools::make_unsigned<T>::type;
}


#line 1 "tools/non_bool_integral.hpp"



#line 1 "tools/integral.hpp"



#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = tools::is_integral<T>::value;
}


#line 5 "tools/integral.hpp"

namespace tools {
  template <typename T>
  concept integral = tools::is_integral_v<T>;
}


#line 7 "tools/non_bool_integral.hpp"

namespace tools {
  template <typename T>
  concept non_bool_integral = tools::integral<T> && !std::same_as<std::remove_cv_t<T>, bool>;
}


#line 12 "tools/bit_width.hpp"

namespace tools {
  namespace detail::bit_width {
    template <tools::non_bool_integral T>
    struct impl {
      constexpr int operator()(const T x) const noexcept(noexcept(impl<tools::make_unsigned_t<T>>{}(x))) requires tools::is_signed_v<T> {
        assert(x >= 0);
        return impl<tools::make_unsigned_t<T>>{}(x);
      }
      constexpr int operator()(const T x) const noexcept(noexcept(std::bit_width(x))) requires tools::is_unsigned_v<T> {
        return std::bit_width(x);
      }
    };
  }

  template <typename T>
  constexpr decltype(auto) bit_width(T&& x) noexcept(noexcept(tools::detail::bit_width::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x)))) {
    return tools::detail::bit_width::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x));
  }
}


#line 6 "tools/ceil_log2.hpp"

namespace tools {
  template <typename T>
  constexpr T ceil_log2(T x) noexcept {
    assert(x > 0);
    return tools::bit_width(x - 1);
  }
}


#line 1 "tools/countr_zero.hpp"



#line 7 "tools/countr_zero.hpp"
#include <limits>
#line 14 "tools/countr_zero.hpp"

namespace tools {
  namespace detail::countr_zero {
    template <tools::non_bool_integral T>
    struct impl {
      constexpr int operator()(const T x) const noexcept(noexcept(impl<tools::make_unsigned_t<T>>{}(x))) requires tools::is_signed_v<T> {
        assert(x >= 0);
        return std::min(impl<tools::make_unsigned_t<T>>{}(x), std::numeric_limits<T>::digits);
      }
      constexpr int operator()(const T x) const noexcept(noexcept(std::countr_zero(x))) requires tools::is_unsigned_v<T> {
        return std::countr_zero(x);
      }
    };
  }

  template <typename T>
  constexpr decltype(auto) countr_zero(T&& x) noexcept(noexcept(tools::detail::countr_zero::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x)))) {
    return tools::detail::countr_zero::impl<std::remove_cvref_t<T>>{}(std::forward<T>(x));
  }
}


#line 1 "tools/fix.hpp"



#line 6 "tools/fix.hpp"

namespace tools {
  template <typename F>
  struct fix : F {
    template <typename G>
    fix(G&& g) : F({std::forward<G>(g)}) {
    }

    template <typename... Args>
    decltype(auto) operator()(Args&&... args) const {
      return F::operator()(*this, std::forward<Args>(args)...);
    }
  };

  template <typename F>
  fix(F&&) -> fix<std::decay_t<F>>;
}


#line 1 "tools/floor_log2.hpp"



#line 6 "tools/floor_log2.hpp"

namespace tools {
  template <typename T>
  constexpr T floor_log2(T x) noexcept {
    assert(x > 0);
    return tools::bit_width(x) - 1;
  }
}


#line 1 "tools/pow2.hpp"



#line 7 "tools/pow2.hpp"

namespace tools {
  template <tools::integral T>
  constexpr T pow2(const T x) noexcept {
    assert(0 <= x && x < std::numeric_limits<T>::digits);
    return T(1) << x;
  }
}


#line 21 "tools/persistent_array.hpp"

namespace tools {
  template <typename T>
  class persistent_array {
    struct inner_node {
      std::array<int, 2> children;
      int refcnt;
    };
    struct leaf_node {
      T data;
      int refcnt;
    };

    static inline std::vector<inner_node> s_inner_nodes;
    static inline std::vector<int> s_free_inner_ids;
    static inline std::vector<leaf_node> s_leaf_nodes;
    static inline std::vector<int> s_free_leaf_ids;

    static int malloc_inner() {
      if (s_free_inner_ids.empty()) {
        s_inner_nodes.emplace_back();
        return s_inner_nodes.size() - 1;
      } else {
        const auto id = s_free_inner_ids.back();
        s_free_inner_ids.pop_back();
        return id;
      }
    }
    static void free_inner(const int id) {
      assert(0 <= id && id < std::ssize(s_inner_nodes));
      assert(s_inner_nodes[id].refcnt == 0);
      s_free_inner_ids.push_back(id);
    }
    static int malloc_leaf() {
      if (s_free_leaf_ids.empty()) {
        s_leaf_nodes.emplace_back();
        return s_leaf_nodes.size() - 1;
      } else {
        const auto id = s_free_leaf_ids.back();
        s_free_leaf_ids.pop_back();
        return id;
      }
    }
    static void free_leaf(const int id) {
      assert(0 <= id && id < std::ssize(s_leaf_nodes));
      assert(s_leaf_nodes[id].refcnt == 0);
      s_free_leaf_ids.push_back(id);
    }
    static void increment_refcnt(int id) {
      if (id >= 0) {
        assert(0 <= id && id < std::ssize(s_inner_nodes));
        ++s_inner_nodes[id].refcnt;
      } else {
        id = ~id;
        assert(0 <= id && id < std::ssize(s_leaf_nodes));
        ++s_leaf_nodes[id].refcnt;
      }
    }
    static void increment_refcnt(const std::array<int, 2>& children) {
      increment_refcnt(children[0]);
      increment_refcnt(children[1]);
    }

    int m_size;
    int m_root;

    void wipe() const {
      if (!this->empty()) {
        tools::fix([&](auto&& dfs, int id) -> void {
          if (id >= 0) {
            assert(0 <= id && id < std::ssize(s_inner_nodes));
            assert(s_inner_nodes[id].refcnt > 0);
            --s_inner_nodes[id].refcnt;
            if (s_inner_nodes[id].refcnt == 0) {
              dfs(s_inner_nodes[id].children[0]);
              dfs(s_inner_nodes[id].children[1]);
              free_inner(id);
            }
          } else {
            id = ~id;
            assert(0 <= id && id < std::ssize(s_leaf_nodes));
            assert(s_leaf_nodes[id].refcnt > 0);
            --s_leaf_nodes[id].refcnt;
            if (s_leaf_nodes[id].refcnt == 0) {
              free_leaf(id);
            }
          }
        })(this->m_root);
      }
    }

  public:
    // For testing purposes.
    static bool fully_released() {
      std::vector<bool> released_inner(s_inner_nodes.size(), false);
      for (const auto id : s_free_inner_ids) {
        assert(!released_inner[id]);
        released_inner[id] = true;
      }
      std::vector<bool> released_leaf(s_leaf_nodes.size(), false);
      for (const auto id : s_free_leaf_ids) {
        assert(!released_leaf[id]);
        released_leaf[id] = true;
      }
      return std::ranges::all_of(released_inner, std::identity{}) && std::ranges::all_of(released_leaf, std::identity{});
    }

    persistent_array() : m_size(0) {
    }
    persistent_array(const int n) : persistent_array(n, T{}) {
    }
    template <typename U>
    requires std::assignable_from<T&, U>
    persistent_array(const int n, U&& x) {
      assert(n >= 0);
      if (n == 0) {
        this->m_size = 0;
        return;
      }

      const auto floor_log2_n = tools::floor_log2(n);
      const auto ceil_log2_n = tools::ceil_log2(n);
      const auto v2_n = tools::countr_zero(n);

      std::vector<int> perfect_binary_trees(floor_log2_n + 1);
      perfect_binary_trees[0] = ~malloc_leaf();
      s_leaf_nodes[~perfect_binary_trees[0]].data = std::forward<U>(x);
      s_leaf_nodes[~perfect_binary_trees[0]].refcnt = 0;
      for (int h = 1; h < std::ssize(perfect_binary_trees); ++h) {
        perfect_binary_trees[h] = malloc_inner();
        s_inner_nodes[perfect_binary_trees[h]].children = {perfect_binary_trees[h - 1], perfect_binary_trees[h - 1]};
        increment_refcnt(s_inner_nodes[perfect_binary_trees[h]].children);
        s_inner_nodes[perfect_binary_trees[h]].refcnt = 0;
      }

      auto right_id = perfect_binary_trees[v2_n];
      for (auto h = v2_n + 2; h <= ceil_log2_n; ++h) {
        if ((n >> (h - 1)) & 1) {
          const auto id = malloc_inner();
          s_inner_nodes[id].children = {perfect_binary_trees[h - 1], right_id};
          increment_refcnt(s_inner_nodes[id].children);
          s_inner_nodes[id].refcnt = 0;
          right_id = id;
        }
      }

      this->m_size = n;
      this->m_root = right_id;
      increment_refcnt(this->m_root);
    }
    template <std::ranges::input_range R>
    requires (!std::ranges::random_access_range<R> && std::assignable_from<T&, std::ranges::range_reference_t<R>>)
    persistent_array(R&& v) : persistent_array(std::forward<R>(v) | std::ranges::to<std::vector>()) {
    }
    template <std::ranges::random_access_range R>
    requires std::assignable_from<T&, std::ranges::range_reference_t<R>>
    persistent_array(R&& v) {
      this->m_size = std::ranges::distance(v);
      if (!this->empty()) {
        this->m_root = tools::fix([&](auto&& dfs, const int l, const int r, const int h) -> int {
          assert(0 <= l && l < r && r <= this->m_size);
          assert(h >= 0);
          assert(r - l <= tools::pow2(h));

          if (r - l == 1) {
            const auto id = malloc_leaf();
            s_leaf_nodes[id].data = std::ranges::begin(v)[l];
            s_leaf_nodes[id].refcnt = 0;
            return ~id;
          }

          const auto m = l + tools::pow2(h - 1);
          if (this->m_size <= m) {
            return dfs(l, r, h - 1);
          }

          const auto id = malloc_inner();
          const auto left_id = dfs(l, m, h - 1);
          const auto right_id = dfs(m, r, h - 1);
          s_inner_nodes[id].children = {left_id, right_id};
          increment_refcnt(s_inner_nodes[id].children);
          s_inner_nodes[id].refcnt = 0;
          return id;
        })(0, this->m_size, tools::ceil_log2(this->m_size));
        increment_refcnt(this->m_root);
      }
    }
    persistent_array(std::initializer_list<T> il) : persistent_array(std::views::all(il)) {
    }
    persistent_array(const tools::persistent_array<T>& other) : m_size(other.m_size) {
      if (!this->empty()) {
        this->m_root = other.m_root;
        increment_refcnt(this->m_root);
      }
    }
    persistent_array(tools::persistent_array<T>&& other) noexcept : m_size(other.m_size), m_root(other.m_root) {
      other.m_size = 0;
    }
    ~persistent_array() {
      this->wipe();
    }
    tools::persistent_array<T>& operator=(const tools::persistent_array<T>& other) {
      if (this != std::addressof(other)) {
        this->wipe();
        this->m_size = other.m_size;
        if (!this->empty()) {
          this->m_root = other.m_root;
          increment_refcnt(this->m_root);
        }
      }
      return *this;
    }
    tools::persistent_array<T>& operator=(tools::persistent_array<T>&& other) noexcept {
      if (this != std::addressof(other)) {
        this->wipe();
        this->m_size = other.m_size;
        this->m_root = other.m_root;
        other.m_size = 0;
      }
      return *this;
    }

    bool empty() const {
      return this->m_size == 0;
    }
    int size() const {
      return this->m_size;
    }

    const T& operator[](const int i) const {
      assert(0 <= i && i < this->m_size);
      auto id = this->m_root;
      int l = 0;
      int r = this->m_size;
      int h = tools::ceil_log2(this->m_size);
      while (id >= 0) {
        assert(0 <= l && l + 2 <= r && r <= this->m_size);
        assert(h >= 1);
        assert(r - l <= tools::pow2(h));

        const auto m = l + tools::pow2(h - 1);
        if (m < this->m_size) {
          if (i < m) {
            r = m;
            id = s_inner_nodes[id].children[0];
          } else {
            l = m;
            id = s_inner_nodes[id].children[1];
          }
        }
        --h;
      }

      id = ~id;
      return s_leaf_nodes[id].data;
    }

    template <typename U>
    requires std::assignable_from<T&, U>
    tools::persistent_array<T> set(const int i, U&& x) const {
      assert(0 <= i && i < this->m_size);

      tools::persistent_array<T> res;
      res.m_size = this->m_size;
      res.m_root = tools::fix([&](auto&& dfs, const int id, const int l, const int r, const int h) -> int {
        assert(0 <= l && l < r && r <= this->m_size);
        assert(h >= 0);
        assert(r - l <= tools::pow2(h));

        if (id < 0) {
          assert(r - l == 1);
          const auto new_id = malloc_leaf();
          s_leaf_nodes[new_id].data = std::forward<U>(x);
          s_leaf_nodes[new_id].refcnt = 0;
          return ~new_id;
        }

        assert(r - l >= 2);
        assert(h >= 1);
        const auto m = l + tools::pow2(h - 1);
        if (this->m_size <= m) {
          return dfs(id, l, r, h - 1);
        }

        const auto new_id = malloc_inner();
        int left_id, right_id;
        if (i < m) {
          left_id = dfs(s_inner_nodes[id].children[0], l, m, h - 1);
          right_id = s_inner_nodes[id].children[1];
        } else {
          left_id = s_inner_nodes[id].children[0];
          right_id = dfs(s_inner_nodes[id].children[1], m, r, h - 1);
        }
        s_inner_nodes[new_id].children = {left_id, right_id};
        increment_refcnt(s_inner_nodes[new_id].children);
        s_inner_nodes[new_id].refcnt = 0;
        return new_id;
      })(this->m_root, 0, this->m_size, tools::ceil_log2(this->m_size));
      increment_refcnt(res.m_root);
      return res;
    }

    template <typename U>
    requires std::assignable_from<T&, U>
    tools::persistent_array<T> push_back(U&& x) const {
      tools::persistent_array<T> res;
      res.m_size = this->m_size + 1;
      if (this->empty()) {
        const auto new_id = malloc_leaf();
        s_leaf_nodes[new_id].data = std::forward<U>(x);
        s_leaf_nodes[new_id].refcnt = 0;
        res.m_root = ~new_id;
        increment_refcnt(res.m_root);
      } else {
        res.m_root = tools::fix([&](auto&& dfs, const int id, const int l, const int h) -> int {
          assert(0 <= l && l < this->m_size);
          assert(h >= 0);
          assert(this->m_size - l <= tools::pow2(h));

          if (this->m_size - l == tools::pow2(h)) {
            const auto new_leaf_id = malloc_leaf();
            s_leaf_nodes[new_leaf_id].data = std::forward<U>(x);
            s_leaf_nodes[new_leaf_id].refcnt = 0;
            const auto new_inner_id = malloc_inner();
            s_inner_nodes[new_inner_id].children = {id, ~new_leaf_id};
            increment_refcnt(s_inner_nodes[new_inner_id].children);
            s_inner_nodes[new_inner_id].refcnt = 0;
            return new_inner_id;
          }

          assert(h >= 1);
          const auto m = l + tools::pow2(h - 1);
          if (this->m_size <= m) {
            return dfs(id, l, h - 1);
          }

          assert(this->m_size - l >= 2);
          const auto new_id = malloc_inner();
          const auto right_id = dfs(s_inner_nodes[id].children[1], m, h - 1);
          s_inner_nodes[new_id].children = {s_inner_nodes[id].children[0], right_id};
          increment_refcnt(s_inner_nodes[new_id].children);
          s_inner_nodes[new_id].refcnt = 0;
          return new_id;
        })(this->m_root, 0, tools::ceil_log2(this->m_size));
        increment_refcnt(res.m_root);
      }
      return res;
    }

    tools::persistent_array<T> pop_back() const {
      assert(!this->empty());
      tools::persistent_array<T> res;
      res.m_size = this->m_size - 1;
      if (!res.empty()) {
        res.m_root = tools::fix([&](auto&& dfs, const int id, const int l, const int h) -> int {
          assert(0 <= l && l + 2 <= this->m_size);
          assert(h >= 1);
          assert(this->m_size - l <= tools::pow2(h));

          if (this->m_size - l == tools::pow2(h - 1) + 1) {
            return s_inner_nodes[id].children[0];
          }

          assert(h >= 2);
          const auto m = l + tools::pow2(h - 1);
          if (this->m_size <= m) {
            return dfs(id, l, h - 1);
          }

          assert(this->m_size - l >= 3);
          const auto new_id = malloc_inner();
          const auto right_id = dfs(s_inner_nodes[id].children[1], m, h - 1);
          s_inner_nodes[new_id].children = {s_inner_nodes[id].children[0], right_id};
          increment_refcnt(s_inner_nodes[new_id].children);
          s_inner_nodes[new_id].refcnt = 0;
          return new_id;
        })(this->m_root, 0, tools::ceil_log2(this->m_size));
        increment_refcnt(res.m_root);
      }
      return res;
    }

    explicit operator std::vector<T>() const {
      std::vector<T> res(this->m_size);
      if (!this->empty()) {
        tools::fix([&](auto&& dfs, const int id, const int l, const int r, const int h) -> void {
          assert(0 <= l && l < r && r <= this->m_size);
          assert(h >= 0);
          assert(r - l <= tools::pow2(h));

          if (id < 0) {
            assert(r - l == 1);
            res[l] = s_leaf_nodes[~id].data;
            return;
          }

          assert(r - l >= 2);
          assert(h >= 1);
          const auto m = l + tools::pow2(h - 1);
          if (this->m_size <= m) {
            dfs(id, l, r, h - 1);
            return;
          }

          dfs(s_inner_nodes[id].children[0], l, m, h - 1);
          dfs(s_inner_nodes[id].children[1], m, r, h - 1);
        })(this->m_root, 0, this->m_size, tools::ceil_log2(this->m_size));
      }
      return res;
    }
  };
}


#line 12 "tests/persistent_array.test.cpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  {
    const tools::persistent_array<int> a;
    assert_that(a.empty());
    assert_that(a.size() == 0);
  }
  assert_that(tools::persistent_array<int>::fully_released());
  {
    const tools::persistent_array<int> a{0};
    assert_that(!a.empty());
    assert_that(a.size() == 1);
    assert_that(a[0] == 0);
  }
  assert_that(tools::persistent_array<int>::fully_released());
  {
    const tools::persistent_array<int> a{0, 1};
    assert_that(!a.empty());
    assert_that(a.size() == 2);
    assert_that(a[0] == 0);
    assert_that(a[1] == 1);
  }
  assert_that(tools::persistent_array<int>::fully_released());
  {
    const tools::persistent_array<int> a{0, 1, 2};
    assert_that(!a.empty());
    assert_that(a.size() == 3);
    assert_that(a[0] == 0);
    assert_that(a[1] == 1);
    assert_that(a[2] == 2);
  }
  assert_that(tools::persistent_array<int>::fully_released());

  for (int n = 0; n <= 40; ++n) {
    {
      const tools::persistent_array<int> a(n);
      for (int i = 0; i < n; ++i) {
        assert_that(a[i] == 0);
      }
      assert_that(static_cast<std::vector<int>>(a) == std::vector<int>(n, 0));
    }
    assert_that(tools::persistent_array<int>::fully_released());
    {
      const tools::persistent_array<int> a(n, -1234);
      for (int i = 0; i < n; ++i) {
        assert_that(a[i] == -1234);
      }
      assert_that(static_cast<std::vector<int>>(a) == std::vector<int>(n, -1234));
    }
    assert_that(tools::persistent_array<int>::fully_released());
    {
      const tools::persistent_array<int> a(std::views::iota(0, n));
      for (int i = 0; i < n; ++i) {
        assert_that(a[i] == i);
      }
      assert_that(static_cast<std::vector<int>>(a) == (std::views::iota(0, n) | std::ranges::to<std::vector>()));
    }
    assert_that(tools::persistent_array<int>::fully_released());

    {
      std::vector<tools::persistent_array<int>> arrays(n + 1);
      arrays[0] = tools::persistent_array<int>(n, -1234);
      for (int i = 1; i <= n; ++i) {
        arrays[i] = arrays[i - 1].set(i - 1, i - 1);
      }
      for (int i = 0; i <= n; ++i) {
        assert_that(static_cast<std::vector<int>>(arrays[i]) == (std::views::iota(0, n) | std::views::transform([&](const auto j) { return j < i ? j : -1234; }) | std::ranges::to<std::vector>()));
      }
    }
    assert_that(tools::persistent_array<int>::fully_released());
    {
      std::vector<tools::persistent_array<int>> arrays(n + 1);
      arrays[0] = tools::persistent_array<int>(std::views::repeat(-1234, n));
      for (int i = 1; i <= n; ++i) {
        arrays[i] = arrays[i - 1].set(i - 1, i - 1);
      }
      for (int i = 0; i <= n; ++i) {
        assert_that(static_cast<std::vector<int>>(arrays[i]) == (std::views::iota(0, n) | std::views::transform([&](const auto j) { return j < i ? j : -1234; }) | std::ranges::to<std::vector>()));
      }
    }
    assert_that(tools::persistent_array<int>::fully_released());

    {
      std::vector<tools::persistent_array<int>> arrays(2 * n + 1);
      for (int i = 1; i <= n; ++i) {
        arrays[i] = arrays[i - 1].push_back(i - 1);
      }
      for (int i = n + 1; i <= 2 * n; ++i) {
        arrays[i] = arrays[i - 1].pop_back();
      }
      for (int i = 0; i <= 2 * n; ++i) {
        assert_that(static_cast<std::vector<int>>(arrays[i]) == (std::views::iota(0, n - std::abs(n - i)) | std::ranges::to<std::vector>()));
      }
    }
    assert_that(tools::persistent_array<int>::fully_released());
  }

  {
    const tools::persistent_array<int> a{3, 1, 4, 1, 5};
    auto b = a;
    const auto c = b;
    b = b.set(2, -1);
    assert_that(static_cast<std::vector<int>>(a) == std::vector<int>{3, 1, 4, 1, 5});
    assert_that(static_cast<std::vector<int>>(b) == std::vector<int>{3, 1, -1, 1, 5});
    assert_that(static_cast<std::vector<int>>(c) == std::vector<int>{3, 1, 4, 1, 5});
  }
  assert_that(tools::persistent_array<int>::fully_released());
  {
    tools::persistent_array<int> a{3, 1, 4, 1, 5};
    tools::persistent_array<int> b(std::move(a));
    assert_that(a.empty());
    assert_that(static_cast<std::vector<int>>(b) == std::vector<int>{3, 1, 4, 1, 5});

    const auto c = std::move(b);
    assert_that(a.empty());
    assert_that(b.empty());
    assert_that(static_cast<std::vector<int>>(c) == std::vector<int>{3, 1, 4, 1, 5});
  }
  assert_that(tools::persistent_array<int>::fully_released());

  {
    std::random_device seed_gen;
    std::mt19937 engine(seed_gen());
    std::uniform_int_distribution<int> t_dist(0, 3);
    std::uniform_int_distribution<int> x_dist(-1000000000, 1000000000);

    tools::persistent_array<int> a;
    std::vector<tools::persistent_array<int>> a_history;
    std::vector<int> naive;
    std::vector<std::vector<int>> naive_history;
    for (int q = 1; q <= 1000000; ++q) {
      const int t = a.empty() ? 0 : t_dist(engine);
      if (t <= 1) {
        const auto x = x_dist(engine);
        a = a.push_back(x);
        naive.push_back(x);
      } else if (t == 2) {
        a = a.pop_back();
        naive.pop_back();
      } else {
        const auto i = std::uniform_int_distribution<int>(0, a.size() - 1)(engine);
        const auto x = x_dist(engine);
        a = a.set(i, x);
        naive[i] = x;
      }

      if (q % 100000 == 0) {
        a_history.push_back(a);
        naive_history.push_back(naive);
      }
    }

    for (int q = 0; q < std::ssize(a_history); ++q) {
      assert_that(static_cast<std::vector<int>>(a_history[q]) == naive_history[q]);
    }
  }
  assert_that(tools::persistent_array<int>::fully_released());

  return 0;
}
Back to top page