Sliding Queue

template <typename T, typename F>
struct SlidingQueue {
  F func;
  std::vector<T> tail;
  std::vector<T> fhead;
  std::vector<T> ftail;

  SlidingQueue(const F& _func = F {}) : func(_func) {
    void(0);
  }

  [[nodiscard]] int size() const {
    return int(fhead.size() + ftail.size());
  }

  [[nodiscard]] bool empty() const {
    return size() == 0;
  }

  [[nodiscard]] T get() const {
    if (!fhead.empty() && !ftail.empty()) {
      return func(fhead.back(), ftail.back());
    } else if (!fhead.empty()) {
      return fhead.back();
    } else if (!ftail.empty()) {
      return ftail.back();
    } else {
      assert(false);
    }
  }

  void transport() {
    std::reverse(tail.begin(), tail.end());
    std::partial_sum(tail.begin(), tail.end(), std::back_inserter(fhead), [&](const T& a, const T& b) {
      return func(b, a);
    });
    tail = {};
    ftail = {};
  }

  void push(const T& x) {
    T nw = (ftail.empty() ? x : func(ftail.back(), x));
    tail.push_back(x);
    ftail.push_back(std::move(nw));
  }

  void pop() {
    assert(!empty());
    if (fhead.empty()) {
      transport();
    }
    fhead.pop_back();
  }

  void clear() {
    tail = {};
    fhead = {};
    ftail = {};
  }
};