Stack Aggregation
(data_structure/stack_aggregation.cpp)

• View this file on GitHub
• Last update: 2020-02-28 14:18:18+09:00
• Link: https://scrapbox.io/data-structures/Sliding_Window_Aggregation

Required by

• Queue Aggregation (data_structure/queue_aggregation.cpp)

Verified with

• test/queue_aggregation.test.cpp

Code

#include <cassert>
#include <stack>

template <class M> class stack_aggregation {
  using T = typename M::value_type;

  class node_type {
  public:
    T value;
    T fold;

    node_type(const T value, const T fold) : value(value), fold(fold) {}
  };

  std::stack<node_type> st;

public:
  stack_aggregation() = default;

  bool empty() const { return st.empty(); }
  T top() const {
    assert(!empty());
    return st.top().value;
  }
  T fold() const { return st.empty() ? M::identity : st.top().fold; }

  void push(const T x) { st.push(node_type(x, M::operation(fold(), x))); }
  void pop() {
    assert(!empty());
    st.pop();
  }
};

/**
 * @brief Stack Aggregation
 * @see https://scrapbox.io/data-structures/Sliding_Window_Aggregation
 */

#line 1 "data_structure/stack_aggregation.cpp"
#include <cassert>
#include <stack>

template <class M> class stack_aggregation {
  using T = typename M::value_type;

  class node_type {
  public:
    T value;
    T fold;

    node_type(const T value, const T fold) : value(value), fold(fold) {}
  };

  std::stack<node_type> st;

public:
  stack_aggregation() = default;

  bool empty() const { return st.empty(); }
  T top() const {
    assert(!empty());
    return st.top().value;
  }
  T fold() const { return st.empty() ? M::identity : st.top().fold; }

  void push(const T x) { st.push(node_type(x, M::operation(fold(), x))); }
  void pop() {
    assert(!empty());
    st.pop();
  }
};

/**
 * @brief Stack Aggregation
 * @see https://scrapbox.io/data-structures/Sliding_Window_Aggregation
 */

Back to top page