Persistent stack (tools/persistent_stack.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2022-04-16 10:31:14+09:00
• Include: #include "tools/persistent_stack.hpp"

It is a persistent stack.

License

• CC0

Author

• anqooqie

Constructor of buffer

persistent_stack<T>::buffer buffer();

It creates an empty buffer for tools::persistent_stack<T>.

Constraints

• None

Time Complexity

• $O(1)$

Constructor

persistent_stack<T> stack(persistent_stack<T>::buffer& buffer);

It creates an empty stack whose data stores on buffer.

Constraints

• None

Time Complexity

• $O(1)$

empty

bool stack.empty();

It returns whether the stack is empty or not.

Constraints

• buffer is in its lifetime.

Time Complexity

• $O(1)$

size

std::size_t stack.size();

It returns the current number of elements of the stack.

Constraints

• buffer is in its lifetime.

Time Complexity

• $O(1)$

top

T stack.top();

It returns the newest element in the stack.

Constraints

• buffer is in its lifetime.
• stack is not empty.

Time Complexity

• $O(1)$

push

persistent_stack<T> stack.push(T x);

It clones stack, adds x to the new stack and returns the new stack.

Constraints

• buffer is in its lifetime.

Time Complexity

• $O(1)$ amortized

pop

persistent_stack<T> stack.pop();

It clones stack, removes the newest element from the new stack and returns the new stack.

Constraints

• buffer is in its lifetime.
• stack is not empty.

Time Complexity

• $O(1)$

emplace

template <typename... Args>
persistent_stack<T> emplace(Args&&... args);

It clones stack, adds T(args...) to the new stack and returns the new stack.

Constraints

• buffer is in its lifetime.

Time Complexity

• $O(1)$ amortized

Verified with

• tests/persistent_stack.test.cpp

Code

#ifndef TOOLS_PERSISTENT_STACK_HPP
#define TOOLS_PERSISTENT_STACK_HPP

#include <cstddef>
#include <vector>
#include <limits>
#include <cassert>
#include <type_traits>

namespace tools {
  template <typename T>
  class persistent_stack {
  private:
    struct node {
      ::std::size_t parent;
      ::std::size_t depth;
      T value;
    };

  public:
    class buffer {
    private:
      ::std::vector<::tools::persistent_stack<T>::node> m_nodes;

    public:
      buffer() = default;
      buffer(const ::tools::persistent_stack<T>::buffer&) = default;
      buffer(::tools::persistent_stack<T>::buffer&&) = default;
      ~buffer() = default;
      ::tools::persistent_stack<T>::buffer& operator=(const ::tools::persistent_stack<T>::buffer&) = default;
      ::tools::persistent_stack<T>::buffer& operator=(::tools::persistent_stack<T>::buffer&&) = default;

      friend ::tools::persistent_stack<T>;
    };

  private:
    static const ::std::size_t EMPTY = ::std::numeric_limits<::std::size_t>::max();
    ::tools::persistent_stack<T>::buffer *m_buffer;
    ::std::size_t m_top;

    persistent_stack(::tools::persistent_stack<T>::buffer& buffer, const ::std::size_t top) : m_buffer(&buffer), m_top(top) {
    }

  public:
    persistent_stack() = default;
    persistent_stack(const ::tools::persistent_stack<T>&) = default;
    persistent_stack(::tools::persistent_stack<T>&&) = default;
    ~persistent_stack() = default;
    ::tools::persistent_stack<T>& operator=(const ::tools::persistent_stack<T>&) = default;
    ::tools::persistent_stack<T>& operator=(::tools::persistent_stack<T>&&) = default;

    explicit persistent_stack(::tools::persistent_stack<T>::buffer& buffer) : m_buffer(&buffer), m_top(EMPTY) {
    }

    bool empty() const {
      return this->m_top == EMPTY;
    }

    ::std::size_t size() const {
      return this->empty() ? 0 : this->m_buffer->m_nodes[this->m_top].depth + 1;
    }

    T top() const {
      assert(!this->empty());
      return this->m_buffer->m_nodes[this->m_top].value;
    }

    ::tools::persistent_stack<T> push(const T& x) const {
      this->m_buffer->m_nodes.emplace_back();
      this->m_buffer->m_nodes.back().parent = this->m_top;
      this->m_buffer->m_nodes.back().depth = this->empty() ? 0 : this->m_buffer->m_nodes[this->m_top].depth + 1;
      this->m_buffer->m_nodes.back().value = x;
      return ::tools::persistent_stack<T>(*this->m_buffer, this->m_buffer->m_nodes.size() - 1);
    }

    ::tools::persistent_stack<T> pop() const {
      assert(!this->empty());
      return ::tools::persistent_stack<T>(*this->m_buffer, this->m_buffer->m_nodes[this->m_top].parent);
    }

    template <typename... Args>
    ::tools::persistent_stack<T> emplace(Args&&... args) const {
      return this->push(T(::std::forward<Args>(args)...));
    }
  };
}

#endif

#line 1 "tools/persistent_stack.hpp"



#include <cstddef>
#include <vector>
#include <limits>
#include <cassert>
#include <type_traits>

namespace tools {
  template <typename T>
  class persistent_stack {
  private:
    struct node {
      ::std::size_t parent;
      ::std::size_t depth;
      T value;
    };

  public:
    class buffer {
    private:
      ::std::vector<::tools::persistent_stack<T>::node> m_nodes;

    public:
      buffer() = default;
      buffer(const ::tools::persistent_stack<T>::buffer&) = default;
      buffer(::tools::persistent_stack<T>::buffer&&) = default;
      ~buffer() = default;
      ::tools::persistent_stack<T>::buffer& operator=(const ::tools::persistent_stack<T>::buffer&) = default;
      ::tools::persistent_stack<T>::buffer& operator=(::tools::persistent_stack<T>::buffer&&) = default;

      friend ::tools::persistent_stack<T>;
    };

  private:
    static const ::std::size_t EMPTY = ::std::numeric_limits<::std::size_t>::max();
    ::tools::persistent_stack<T>::buffer *m_buffer;
    ::std::size_t m_top;

    persistent_stack(::tools::persistent_stack<T>::buffer& buffer, const ::std::size_t top) : m_buffer(&buffer), m_top(top) {
    }

  public:
    persistent_stack() = default;
    persistent_stack(const ::tools::persistent_stack<T>&) = default;
    persistent_stack(::tools::persistent_stack<T>&&) = default;
    ~persistent_stack() = default;
    ::tools::persistent_stack<T>& operator=(const ::tools::persistent_stack<T>&) = default;
    ::tools::persistent_stack<T>& operator=(::tools::persistent_stack<T>&&) = default;

    explicit persistent_stack(::tools::persistent_stack<T>::buffer& buffer) : m_buffer(&buffer), m_top(EMPTY) {
    }

    bool empty() const {
      return this->m_top == EMPTY;
    }

    ::std::size_t size() const {
      return this->empty() ? 0 : this->m_buffer->m_nodes[this->m_top].depth + 1;
    }

    T top() const {
      assert(!this->empty());
      return this->m_buffer->m_nodes[this->m_top].value;
    }

    ::tools::persistent_stack<T> push(const T& x) const {
      this->m_buffer->m_nodes.emplace_back();
      this->m_buffer->m_nodes.back().parent = this->m_top;
      this->m_buffer->m_nodes.back().depth = this->empty() ? 0 : this->m_buffer->m_nodes[this->m_top].depth + 1;
      this->m_buffer->m_nodes.back().value = x;
      return ::tools::persistent_stack<T>(*this->m_buffer, this->m_buffer->m_nodes.size() - 1);
    }

    ::tools::persistent_stack<T> pop() const {
      assert(!this->empty());
      return ::tools::persistent_stack<T>(*this->m_buffer, this->m_buffer->m_nodes[this->m_top].parent);
    }

    template <typename... Args>
    ::tools::persistent_stack<T> emplace(Args&&... args) const {
      return this->push(T(::std::forward<Args>(args)...));
    }
  };
}

Back to top page