test/standalone/persistent_stack_test.cpp

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

Code

#define STANDALONE
#include "include/mtl/persistent_stack.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);
  int sz = 0;
  for (int i = 0; i < N; i++) {
    int t = sz > 0 ? (rand()%3 != 0) : 1;
    if (t == 0) {
      U[i] = {t, 0};
      sz--;
    } else {
      U[i] = {t, rand()};
      sz++;
    }
  }
  std::vector<int> Q(N);
  for (int i = 0; i < N; i++) {
    Q[i] = rand() % N + 1;
  }
  std::vector<int> expected(N+1, -1);
  std::stack<int> st;
  for (int i = 0; i < (int)U.size(); i++) {
    if (U[i].first == 0) {
      st.pop();
    } else {
      st.push(U[i].second);
    }
    expected[i+1] = st.empty() ? -1 : st.top();
  }

  std::vector<PersistentStack<int>> ps(N+1);
  for (int i = 0; i < N; i++) {
    if (U[i].first == 0) {
      ps[i+1] = ps[i].pop();
    } else {
      ps[i+1] = ps[i].push(U[i].second);
    }
  }

  for (auto q : Q) {
    int v = ps[q].empty() ? -1 : ps[q].top();
    if (expected[q] != v) {
      std::cout << "expected[q] != ps[q].top(): " << expected[q] << ' ' << v << std::endl;
      exit(EXIT_FAILURE);
    }
  }
  std::cout << "OK" << std::endl;
}

#line 1 "test/standalone/persistent_stack_test.cpp"
#define STANDALONE
#line 2 "include/mtl/persistent_stack.hpp"
#include <algorithm>
#include <cstddef>
#include <memory>

template<typename T>
class PersistentStack {
 public:
  using value_type = T;
  using const_reference = const value_type&;
  using reference = const_reference;
  struct Node;
  using node_ptr = std::shared_ptr<Node>;
  struct Node {
    value_type v;
    node_ptr next;
    Node() = default;
    Node(const value_type& v, node_ptr next) : v(v), next(next) {}
    Node(value_type&& v, node_ptr next) : v(std::move(v)), next(next) {}
  };
 private:
  node_ptr top_;
  size_t size_;
  PersistentStack(node_ptr ptr, size_t sz) : top_(ptr), size_(sz) {}
 public:
  PersistentStack() : top_(nullptr), size_(0) {}
  size_t size() const { return size_; }
  bool empty() const { return size() == 0; }
  const_reference top() const { return top_->v; }
 private:
  template<typename V>
  PersistentStack _push(V&& v) const {
    auto new_node = std::make_shared<Node>(std::forward<V>(v), top_);
    return PersistentStack(new_node, size()+1);
  }
 public:
  template<class... Args>
  [[nodiscard]] PersistentStack emplace(Args&&... args) const {
    return _push(value_type(std::forward<Args>(args)...));
  }
  template<typename V>
  [[nodiscard]] PersistentStack push(V&& v) const {
    static_assert(std::is_convertible<V,value_type>::value, "");
    return _push(std::forward<V>(v));
  }
  [[nodiscard]] PersistentStack push(const value_type& v) const {
    return _push(v);
  }
  [[nodiscard]] PersistentStack push(value_type&& v) const {
    return _push(std::move(v));
  }
  [[nodiscard]] PersistentStack pop() const {
    return PersistentStack(top_->next, size()-1);
  }
  [[nodiscard]] PersistentStack concat(const PersistentStack& other) const {
    if (empty()) 
      return other;
    else 
      return pop().concat(other).push(top());
  }
  [[nodiscard]] PersistentStack reverse() const {
    PersistentStack ret;
    for (auto t = *this; !t.empty(); t = t.pop())
      ret = ret.push(t.top());
    return ret;
  }
};
#line 3 "test/standalone/persistent_stack_test.cpp"

#include <vector>
#include <stack>
#line 7 "test/standalone/persistent_stack_test.cpp"
#include <numeric>
#include <iostream>
#include <cassert>

constexpr int N = 1e5;
int main() {
  std::vector<std::pair<int,int>> U(N);
  int sz = 0;
  for (int i = 0; i < N; i++) {
    int t = sz > 0 ? (rand()%3 != 0) : 1;
    if (t == 0) {
      U[i] = {t, 0};
      sz--;
    } else {
      U[i] = {t, rand()};
      sz++;
    }
  }
  std::vector<int> Q(N);
  for (int i = 0; i < N; i++) {
    Q[i] = rand() % N + 1;
  }
  std::vector<int> expected(N+1, -1);
  std::stack<int> st;
  for (int i = 0; i < (int)U.size(); i++) {
    if (U[i].first == 0) {
      st.pop();
    } else {
      st.push(U[i].second);
    }
    expected[i+1] = st.empty() ? -1 : st.top();
  }

  std::vector<PersistentStack<int>> ps(N+1);
  for (int i = 0; i < N; i++) {
    if (U[i].first == 0) {
      ps[i+1] = ps[i].pop();
    } else {
      ps[i+1] = ps[i].push(U[i].second);
    }
  }

  for (auto q : Q) {
    int v = ps[q].empty() ? -1 : ps[q].top();
    if (expected[q] != v) {
      std::cout << "expected[q] != ps[q].top(): " << expected[q] << ' ' << v << std::endl;
      exit(EXIT_FAILURE);
    }
  }
  std::cout << "OK" << std::endl;
}

Back to top page