ds/slidingWindowAggregation.cpp

View this file on GitHub
Last update: 2024-04-05 18:02:52+08:00

Verified with

test/queue_operate_all_composite.test.cpp

Code

template<class M, M(*id)(), M(*op)(const M&, const M&)>
struct SWAG {
  vector<M> left, right;
  M rightComp;

  SWAG() : left(1, id()), rightComp(id()) {}
  void push(M x) {
    right.emplace_back(x);
    rightComp = op(rightComp, x);
  }
  void pop() {
    if (ssize(left) == 1) {
      for(auto &x : right | views::reverse)
        left.emplace_back(op(x, left.back()));
      vector<M> tmp;
      right.swap(tmp);
      rightComp = id();
    }
    left.pop_back();
  }
  M query() { return op(left.back(), rightComp); }
};

#line 1 "ds/slidingWindowAggregation.cpp"
template<class M, M(*id)(), M(*op)(const M&, const M&)>
struct SWAG {
  vector<M> left, right;
  M rightComp;

  SWAG() : left(1, id()), rightComp(id()) {}
  void push(M x) {
    right.emplace_back(x);
    rightComp = op(rightComp, x);
  }
  void pop() {
    if (ssize(left) == 1) {
      for(auto &x : right | views::reverse)
        left.emplace_back(op(x, left.back()));
      vector<M> tmp;
      right.swap(tmp);
      rightComp = id();
    }
    left.pop_back();
  }
  M query() { return op(left.back(), rightComp); }
};