Queue Aggregation
(data_structure/queue_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

Depends on

• Stack Aggregation (data_structure/stack_aggregation.cpp)
• other/opposite_monoid.cpp

Verified with

• test/queue_aggregation.test.cpp

Code

#include "data_structure/stack_aggregation.cpp"
#include "other/opposite_monoid.cpp"

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

  stack_aggregation<opposite_monoid<M>> front_st;
  stack_aggregation<M> back_st;

public:
  queue_aggregation() = default;

  bool empty() const { return front_st.empty(); }
  T fold() const { return M::operation(front_st.fold(), back_st.fold()); }

  void push(const T x) {
    if (empty())
      front_st.push(x);
    else
      back_st.push(x);
  }
  void pop() {
    assert(!empty());
    front_st.pop();
    if (front_st.empty()) {
      while (!back_st.empty()) {
        front_st.push(back_st.top());
        back_st.pop();
      }
    }
  }
};

/**
 * @brief Queue 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
 */
#line 1 "other/opposite_monoid.cpp"
template <class M> class opposite_monoid {
  using T = typename M::value_type;

public:
  using value_type = T;
  static constexpr T operation(const T &l, const T &r) noexcept {
    return M::operation(r, l);
  }
  static constexpr T identity = M::identity;
};
#line 3 "data_structure/queue_aggregation.cpp"

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

  stack_aggregation<opposite_monoid<M>> front_st;
  stack_aggregation<M> back_st;

public:
  queue_aggregation() = default;

  bool empty() const { return front_st.empty(); }
  T fold() const { return M::operation(front_st.fold(), back_st.fold()); }

  void push(const T x) {
    if (empty())
      front_st.push(x);
    else
      back_st.push(x);
  }
  void pop() {
    assert(!empty());
    front_st.pop();
    if (front_st.empty()) {
      while (!back_st.empty()) {
        front_st.push(back_st.top());
        back_st.pop();
      }
    }
  }
};

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

Back to top page