Sliding Window Aggregation
(data-structure/swag.hpp)

• View this file on GitHub
• Last update: 2023-07-25 00:50:50+07:00
• Include: #include "data-structure/swag.hpp"

Code

template <class T, class Op>
struct SWAG {
  T e;
  Op op;
  deque<T> dq;
  int front;
  T back;

  SWAG(T e_, Op op_) : e(e_), op(op_) {
    front = 0;
    back = e;
  }

  void push(T x) {
    dq.push_back(x);
    back = op(back, x);
  }

  void pop() {
    assert(not dq.empty());
    dq.pop_front();
    if (front) {
      --front;
    } else {
      int len = dq.size();
      for (int i = len - 2; i >= 0; i--) dq[i] = op(dq[i], dq[i + 1]);
      front = len;
      back = e;
    }
  }

  T sum() const { return front ? op(dq.front(), back) : back; }
};

#line 1 "data-structure/swag.hpp"
template <class T, class Op>
struct SWAG {
  T e;
  Op op;
  deque<T> dq;
  int front;
  T back;

  SWAG(T e_, Op op_) : e(e_), op(op_) {
    front = 0;
    back = e;
  }

  void push(T x) {
    dq.push_back(x);
    back = op(back, x);
  }

  void pop() {
    assert(not dq.empty());
    dq.pop_front();
    if (front) {
      --front;
    } else {
      int len = dq.size();
      for (int i = len - 2; i >= 0; i--) dq[i] = op(dq[i], dq[i + 1]);
      front = len;
      back = e;
    }
  }

  T sum() const { return front ? op(dq.front(), back) : back; }
};

Back to top page