test/standalone/persistent_array_test.cpp

• View this file on GitHub
• Last update: 2024-07-11 22:21:57+09:00

Code

#define STANDALONE
#include "include/mtl/persistent_array.hpp"

#include <vector>
#include <stack>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <cassert>

constexpr int N = 1e5;
int main() {
  std::vector<std::pair<int,int>> U(N);
  for (int i = 0; i < N; i++) {
    U[i] = {rand()%N, rand()%N};
  }
  std::vector<std::pair<int,int>> Q(N);
  for (int i = 0; i < N; i++) {
    Q[i] = {rand()%N+1, rand()%N};
  }
  std::vector<int> expected(N+1, -1);
  std::vector<int> st(N);
  int k = 0;
  std::vector<int> qi(N);
  std::iota(qi.begin(), qi.end(), 0);
  std::sort(qi.begin(), qi.end(),
            [&](int l, int r) { return Q[l].first < Q[r].first; });
  for (int i = 0; i < (int)U.size(); i++) {
    st[U[i].first] = U[i].second;
    while (k < N and Q[qi[k]].first == i+1) {
      expected[qi[k]] = st[Q[qi[k]].second];
      k++;
    }
  }

  std::vector<PersistentArray<int>> ps(N+1);
  for (int i = 0; i < N; i++)
    ps[0] = ps[0].set(i, 0);
  for (int i = 0; i < N; i++) {
    ps[i+1] = ps[i].set(U[i].first, U[i].second);
  }

  for (int i = 0; i < (int)Q.size(); i++) {
    int v = ps[Q[i].first].get(Q[i].second);
    if (expected[i] != v) {
      std::cout << i<<", "<<Q[i].first<<", "<<Q[i].second<<" expected[i] != ps[Q[i].first].get(Q[i].second): " << expected[i] << ' ' << v << std::endl;
      exit(EXIT_FAILURE);
    }
  }
  std::cout << "OK" << std::endl;
}

#line 1 "test/standalone/persistent_array_test.cpp"
#define STANDALONE
#line 2 "include/mtl/persistent_array.hpp"
#include <memory>
#include <utility>
#include <array>

template<typename T, unsigned Degree=4>
class PersistentArray {
  static constexpr unsigned M = Degree;
 private:
  struct Node;
  using node_ptr = std::shared_ptr<Node>;
  struct Node {
    T v;
    std::array<node_ptr, M> ch;
    Node() = default;
    explicit Node(const T& v) : v(v), ch({}) {}
    explicit Node(T&& v) : v(std::move(v)), ch({}) {}
  };
  node_ptr root_;
  T init_v_;
  explicit PersistentArray(node_ptr ptr, T init_v)
    : root_(ptr), init_v_(init_v) {}

 public:
  explicit PersistentArray(T init_v = T())
    : root_(nullptr), init_v_(init_v) {}

  bool empty() const { return root_ == nullptr; }
  T get(size_t i) const {
    auto u = root_;
    while (u and i > 0) {
      i--;
      u = u->ch[i % M];
      i /= M;
    }
    return u ? u->v : init_v_;
  }

 private:
  template<typename V>
  node_ptr set_rec(node_ptr u, size_t id, V&& v) const {
    if (id == 0) {
      if (u) {
        auto new_node = std::make_shared<Node>(*u);
        new_node->v = std::forward<V>(v);
        return new_node;
      } else {
        return std::make_shared<Node>(std::forward<V>(v));
      }
    } else {
      auto new_node = u ? std::make_shared<Node>(*u) : std::make_shared<Node>(init_v_);
      --id;
      new_node->ch[id % M] = set_rec(new_node->ch[id % M], id / M, std::forward<V>(v));
      return new_node;
    }
  }
 public:
  template<typename V>
  [[nodiscard]] PersistentArray set(size_t i, V&& v) const {
    static_assert(std::is_convertible<V, T>::value, "");
    return PersistentArray(set_rec(root_, i, std::forward<V>(v)), init_v_);
  }
  [[nodiscard]] PersistentArray set(size_t i, const T& v) const {
    return PersistentArray(set_rec(root_, i, v), init_v_);
  }
  [[nodiscard]] PersistentArray set(size_t i, T&& v) const {
    return PersistentArray(set_rec(root_, i, std::move(v)), init_v_);
  }
};
#line 3 "test/standalone/persistent_array_test.cpp"

#include <vector>
#include <stack>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <cassert>

constexpr int N = 1e5;
int main() {
  std::vector<std::pair<int,int>> U(N);
  for (int i = 0; i < N; i++) {
    U[i] = {rand()%N, rand()%N};
  }
  std::vector<std::pair<int,int>> Q(N);
  for (int i = 0; i < N; i++) {
    Q[i] = {rand()%N+1, rand()%N};
  }
  std::vector<int> expected(N+1, -1);
  std::vector<int> st(N);
  int k = 0;
  std::vector<int> qi(N);
  std::iota(qi.begin(), qi.end(), 0);
  std::sort(qi.begin(), qi.end(),
            [&](int l, int r) { return Q[l].first < Q[r].first; });
  for (int i = 0; i < (int)U.size(); i++) {
    st[U[i].first] = U[i].second;
    while (k < N and Q[qi[k]].first == i+1) {
      expected[qi[k]] = st[Q[qi[k]].second];
      k++;
    }
  }

  std::vector<PersistentArray<int>> ps(N+1);
  for (int i = 0; i < N; i++)
    ps[0] = ps[0].set(i, 0);
  for (int i = 0; i < N; i++) {
    ps[i+1] = ps[i].set(U[i].first, U[i].second);
  }

  for (int i = 0; i < (int)Q.size(); i++) {
    int v = ps[Q[i].first].get(Q[i].second);
    if (expected[i] != v) {
      std::cout << i<<", "<<Q[i].first<<", "<<Q[i].second<<" expected[i] != ps[Q[i].first].get(Q[i].second): " << expected[i] << ' ' << v << std::endl;
      exit(EXIT_FAILURE);
    }
  }
  std::cout << "OK" << std::endl;
}

Back to top page