swag.hpp

• View this file on GitHub
• Last update: 2025-01-19 15:28:01+08:00
• Include: #include "swag.hpp"
• Link: https://www.hirzels.com/martin/papers/debs17-tutorial.pdf

Required by

• Shift Sample Points (shift_sample_points.hpp)

Verified with

• test/data_structure/queue_operate_all_composite.0.test.cpp
• test/enumerative_combinatorics/factorial.0.test.cpp
• test/formal_power_series/shift_of_sampling_points_of_polynomial.1.test.cpp

Code

#pragma once

#include <cassert>
#include <cstddef>
#include <optional>
#include <stack>
#include <type_traits>
#include <vector>

// see: https://www.hirzels.com/martin/papers/debs17-tutorial.pdf
// requires: Op(Op(A,B),C) = Op(A,Op(B,C))
template<typename Tp, typename Op,
         std::enable_if_t<std::is_invocable_r_v<Tp, Op, const Tp &, const Tp &>, int> = 0>
class SWAG {
public:
    Op F;
    std::stack<Tp, std::vector<Tp>> Front, Back;
    std::optional<Tp> Agg;

    explicit SWAG(Op F) : F(F) {}
    bool empty() const { return Front.empty() && Back.empty(); }
    std::size_t size() const { return Front.size() + Back.size(); }
    void push_back(const Tp &v) {
        Back.push(v);
        Agg.emplace(Agg ? F(*Agg, v) : v);
    }
    void pop_front() {
        assert(!empty());
        if (Front.empty()) {
            Front.push(Back.top());
            Back.pop();
            while (!Back.empty()) {
                Front.push(F(Back.top(), Front.top()));
                Back.pop();
            }
            Agg.reset();
        }
        Front.pop();
    }

    // returns F(...F(F(Q[0],Q[1]),Q[2]),...,Q[N-1])
    std::optional<Tp> query() const {
        if (empty()) return {};
        if (Front.empty()) return Agg;
        if (!Agg) return Front.top();
        return F(Front.top(), *Agg);
    }
};

#line 2 "swag.hpp"

#include <cassert>
#include <cstddef>
#include <optional>
#include <stack>
#include <type_traits>
#include <vector>

// see: https://www.hirzels.com/martin/papers/debs17-tutorial.pdf
// requires: Op(Op(A,B),C) = Op(A,Op(B,C))
template<typename Tp, typename Op,
         std::enable_if_t<std::is_invocable_r_v<Tp, Op, const Tp &, const Tp &>, int> = 0>
class SWAG {
public:
    Op F;
    std::stack<Tp, std::vector<Tp>> Front, Back;
    std::optional<Tp> Agg;

    explicit SWAG(Op F) : F(F) {}
    bool empty() const { return Front.empty() && Back.empty(); }
    std::size_t size() const { return Front.size() + Back.size(); }
    void push_back(const Tp &v) {
        Back.push(v);
        Agg.emplace(Agg ? F(*Agg, v) : v);
    }
    void pop_front() {
        assert(!empty());
        if (Front.empty()) {
            Front.push(Back.top());
            Back.pop();
            while (!Back.empty()) {
                Front.push(F(Back.top(), Front.top()));
                Back.pop();
            }
            Agg.reset();
        }
        Front.pop();
    }

    // returns F(...F(F(Q[0],Q[1]),Q[2]),...,Q[N-1])
    std::optional<Tp> query() const {
        if (empty()) return {};
        if (Front.empty()) return Agg;
        if (!Agg) return Front.top();
        return F(Front.top(), *Agg);
    }
};

Back to top page