structure/others/sliding-window-aggregation.hpp

• View this file on GitHub
• Last update: 2024-04-24 02:34:04+09:00
• Include: #include "structure/others/sliding-window-aggregation.hpp"

Verified with

• test/verify/yosupo-queue-operate-all-composite.test.cpp

Code

template< typename SemiGroup >
struct SlidingWindowAggregation {
  using F = function< SemiGroup(SemiGroup, SemiGroup) >;
 
  struct Node {
    SemiGroup val, sum;
 
    Node(const SemiGroup &val, const SemiGroup &sum) : val(val), sum(sum) {}
  };
 
  SlidingWindowAggregation(F f) : f(f) {}
 
 
  const F f;
  stack< Node > front, back;
 
  bool empty() const {
    return front.empty() && back.empty();
  }
 
  size_t size() const {
    return front.size() + back.size();
  }
 
  SemiGroup fold_all() const {
    if(front.empty()) {
      return back.top().sum;
    } else if(back.empty()) {
      return front.top().sum;
    } else {
      return f(front.top().sum, back.top().sum);
    }
  }
 
  void push(const SemiGroup &x) {
    if(back.empty()) {
      back.emplace(x, x);
    } else {
      back.emplace(x, f(back.top().sum, x));
    }
  }
 
  void pop() {
    if(front.empty()) {
      front.emplace(back.top().val, back.top().val);
      back.pop();
      while(!back.empty()) {
        front.emplace(back.top().val, f(back.top().val, front.top().sum));
        back.pop();
      }
    }
    front.pop();
  }
};

#line 1 "structure/others/sliding-window-aggregation.hpp"
template< typename SemiGroup >
struct SlidingWindowAggregation {
  using F = function< SemiGroup(SemiGroup, SemiGroup) >;
 
  struct Node {
    SemiGroup val, sum;
 
    Node(const SemiGroup &val, const SemiGroup &sum) : val(val), sum(sum) {}
  };
 
  SlidingWindowAggregation(F f) : f(f) {}
 
 
  const F f;
  stack< Node > front, back;
 
  bool empty() const {
    return front.empty() && back.empty();
  }
 
  size_t size() const {
    return front.size() + back.size();
  }
 
  SemiGroup fold_all() const {
    if(front.empty()) {
      return back.top().sum;
    } else if(back.empty()) {
      return front.top().sum;
    } else {
      return f(front.top().sum, back.top().sum);
    }
  }
 
  void push(const SemiGroup &x) {
    if(back.empty()) {
      back.emplace(x, x);
    } else {
      back.emplace(x, f(back.top().sum, x));
    }
  }
 
  void pop() {
    if(front.empty()) {
      front.emplace(back.top().val, back.top().val);
      back.pop();
      while(!back.empty()) {
        front.emplace(back.top().val, f(back.top().val, front.top().sum));
        back.pop();
      }
    }
    front.pop();
  }
};

Back to top page