Persistent Stack
(data_structure/persistent_stack.cpp)

• View this file on GitHub
• Last update: 2020-03-16 22:45:32+09:00

Required by

• Physicist's Queue (data_structure/physicists_queue.cpp)
• Realtime Queue (data_structure/realtime_queue.cpp)

Verified with

• test/physicists_queue.test.cpp
• test/realtime_queue.test.cpp

Code

#include <cassert>
#include <memory>
#include <utility>

template <class T> class persistent_stack {
  using Self = persistent_stack<T>;
  class node_type;
  using node_ptr = std::shared_ptr<const node_type>;

  class node_type {
  public:
    T value;
    node_ptr next;

    node_type(T value, node_ptr next) : value(value), next(next) {}
  };

  node_ptr root;

  persistent_stack(node_ptr root) : root(root) {}

public:
  persistent_stack() = default;

  bool empty() const { return not root; }

  T top() const {
    assert(not empty());

    return root->value;
  }

  Self push(T x) const {
    return Self(std::make_shared<const node_type>(x, root));
  }

  Self pop() const {
    assert(not empty());

    return Self(root->next);
  }

  Self reverse() const {
    Self ret;
    Self x = *this;
    while (not x.empty()) {
      ret = ret.push(x.top());
      x = x.pop();
    }
    return ret;
  }
};

/**
 * @brief Persistent Stack
 */

#line 1 "data_structure/persistent_stack.cpp"
#include <cassert>
#include <memory>
#include <utility>

template <class T> class persistent_stack {
  using Self = persistent_stack<T>;
  class node_type;
  using node_ptr = std::shared_ptr<const node_type>;

  class node_type {
  public:
    T value;
    node_ptr next;

    node_type(T value, node_ptr next) : value(value), next(next) {}
  };

  node_ptr root;

  persistent_stack(node_ptr root) : root(root) {}

public:
  persistent_stack() = default;

  bool empty() const { return not root; }

  T top() const {
    assert(not empty());

    return root->value;
  }

  Self push(T x) const {
    return Self(std::make_shared<const node_type>(x, root));
  }

  Self pop() const {
    assert(not empty());

    return Self(root->next);
  }

  Self reverse() const {
    Self ret;
    Self x = *this;
    while (not x.empty()) {
      ret = ret.push(x.top());
      x = x.pop();
    }
    return ret;
  }
};

/**
 * @brief Persistent Stack
 */

Back to top page