sliding_window_aggregation.hpp¶

#include "noya/sliding_window_aggregation.hpp"

SourceExpanded

#ifndef NOYA_SLIDING_WINDOW_AGGREGATION_HPP
#define NOYA_SLIDING_WINDOW_AGGREGATION_HPP 1

#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>

namespace noya {
#if __cplusplus >= 201703L

/// @brief Sliding window aggregation (SWAG) supporting push_back, pop_front, and monoid product queries.
template <class S, auto op, auto e> struct swag {
  static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                "op must work as S(S, S)");
  static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                "e must work as S()");

#else

/// @brief Sliding window aggregation (SWAG) supporting push_back, pop_front, and monoid product queries.
template <class S, S (*op)(S, S), S (*e)()> struct swag {

#endif
  int sz = 0;
  std::vector<S> dat;
  std::vector<S> sum_l;
  S sum_r;

  swag() {
    sum_l = {e()};
    sum_r = e();
  }

  int size() { return sz; }
  /// @brief Push element x to the back of the window.
  void push(S x) {
    ++sz;
    sum_r = op(sum_r, x);
    dat.push_back(x);
  }

  /// @brief Pop the front element from the window.
  void pop() {
    assert(0 < sz);
    --sz;
    sum_l.pop_back();
    if ((int)sum_l.size() == 0) {
      sum_l = {e()};
      sum_r = e();
      while ((int)dat.size() > 1) {
        sum_l.push_back(op(dat.back(), sum_l.back()));
        dat.pop_back();
      }
      dat.pop_back();
    }
  }

  S lprod() { return sum_l.back(); }
  S rprod() { return sum_r; }

  /// @brief Return the aggregate product of all elements in the window.
  S prod() { return op(sum_l.back(), sum_r); }
};
} // namespace noya

#endif // NOYA_SLIDING_WINDOW_AGGREGATION_HPP

#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>

namespace noya {
#if __cplusplus >= 201703L

/// @brief Sliding window aggregation (SWAG) supporting push_back, pop_front, and monoid product queries.
template <class S, auto op, auto e> struct swag {
  static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                "op must work as S(S, S)");
  static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                "e must work as S()");

#else

/// @brief Sliding window aggregation (SWAG) supporting push_back, pop_front, and monoid product queries.
template <class S, S (*op)(S, S), S (*e)()> struct swag {

#endif
  int sz = 0;
  std::vector<S> dat;
  std::vector<S> sum_l;
  S sum_r;

  swag() {
    sum_l = {e()};
    sum_r = e();
  }

  int size() { return sz; }
  /// @brief Push element x to the back of the window.
  void push(S x) {
    ++sz;
    sum_r = op(sum_r, x);
    dat.push_back(x);
  }

  /// @brief Pop the front element from the window.
  void pop() {
    assert(0 < sz);
    --sz;
    sum_l.pop_back();
    if ((int)sum_l.size() == 0) {
      sum_l = {e()};
      sum_r = e();
      while ((int)dat.size() > 1) {
        sum_l.push_back(op(dat.back(), sum_l.back()));
        dat.pop_back();
      }
      dat.pop_back();
    }
  }

  S lprod() { return sum_l.back(); }
  S rprod() { return sum_r; }

  /// @brief Return the aggregate product of all elements in the window.
  S prod() { return op(sum_l.back(), sum_r); }
};
} // namespace noya