#include "Data-Structure/Range-Accumulate/foldLR.hpp"
#pragma once #include <vector> /** * @brief FoldLR */ template <class T> class FoldLR { std::vector<T> m_foldL, m_foldR; T m_e; public: FoldLR() = default; template <class BidirectionalItr, class Op> FoldLR(BidirectionalItr begin, BidirectionalItr end, const T& e, Op op) : FoldLR(begin, end, e, op, op) {} /** * foldLeftOp: (T, Elem) -> T * foldRightOp: (Elem, T) -> T */ template <class BidirectionalItr, class FoldLeftOp, class FoldRightOp> FoldLR(BidirectionalItr begin, BidirectionalItr end, const T& e, FoldLeftOp foldLeftOp, FoldRightOp foldRightOp) : m_foldL(std::distance(begin, end) + 1, e) , m_foldR(std::distance(begin, end) + 1, e) , m_e(e) { size_t i; BidirectionalItr itr; for (i = 0, itr = begin; itr != end; ++i, ++itr) { m_foldL[i + 1] = foldLeftOp(m_foldL[i], *itr); } for (i = m_foldR.size() - 1, itr = std::prev(end); i > 0; --i, --itr) { m_foldR[i - 1] = foldRightOp(*itr, m_foldR[i]); } } /** * [0, r) * ((((e op a[0]) op a[1]) op a[2]) ... op a[r - 1]) * foldL(0) returns e(); */ const T foldL(size_t r) const { return m_foldL[r]; } /** * [l, N) * (a[l] op ... (a[N - 3] op (a[N - 2] op (a[N - 1] op e)))) * foldR(N) returns e(); */ const T foldR(size_t l) const { return m_foldR[l]; } const T e() const { return m_e; } };
#line 2 "Data-Structure/Range-Accumulate/foldLR.hpp" #include <vector> /** * @brief FoldLR */ template <class T> class FoldLR { std::vector<T> m_foldL, m_foldR; T m_e; public: FoldLR() = default; template <class BidirectionalItr, class Op> FoldLR(BidirectionalItr begin, BidirectionalItr end, const T& e, Op op) : FoldLR(begin, end, e, op, op) {} /** * foldLeftOp: (T, Elem) -> T * foldRightOp: (Elem, T) -> T */ template <class BidirectionalItr, class FoldLeftOp, class FoldRightOp> FoldLR(BidirectionalItr begin, BidirectionalItr end, const T& e, FoldLeftOp foldLeftOp, FoldRightOp foldRightOp) : m_foldL(std::distance(begin, end) + 1, e) , m_foldR(std::distance(begin, end) + 1, e) , m_e(e) { size_t i; BidirectionalItr itr; for (i = 0, itr = begin; itr != end; ++i, ++itr) { m_foldL[i + 1] = foldLeftOp(m_foldL[i], *itr); } for (i = m_foldR.size() - 1, itr = std::prev(end); i > 0; --i, --itr) { m_foldR[i - 1] = foldRightOp(*itr, m_foldR[i]); } } /** * [0, r) * ((((e op a[0]) op a[1]) op a[2]) ... op a[r - 1]) * foldL(0) returns e(); */ const T foldL(size_t r) const { return m_foldL[r]; } /** * [l, N) * (a[l] op ... (a[N - 3] op (a[N - 2] op (a[N - 1] op e)))) * foldR(N) returns e(); */ const T foldR(size_t l) const { return m_foldR[l]; } const T e() const { return m_e; } };