Foldable Queue
(Src/DataStructure/SWAG/FoldableQueue.hpp)

View this file on GitHub
Last update: 2025-04-17 21:24:54+09:00
Include: #include "Src/DataStructure/SWAG/FoldableQueue.hpp"

概要

半群の積が取れるQueue

モノイドじゃなくて半群だから、単位元がいらない！すごい？

参考の名称に従い、SWAGでは無く「Foldable Queue」という呼び名を使用しているが、ライブラリの総積を取得するメンバの名前はproduct()

雛形

struct S {
    using Fold = struct {
        using Element = ;
        /*
        static Element identity() {
        }
        static Element operation(Element, Element) {
        }
        */
    };
    using Element = std::pair<int, int>;
    using F = typename Fold::Element;
    static F convert(Element v) {
    }
    static F pushBack(F dp, Element v) {
    }
    static F pushFront(F dp, Element v) {
    }
};

または、concepts::Semigroup, concepts::Monoidを満たすクラスをSWAGableに変換するラッパーSemigroupSWAGable<S>, MonoidSWAGable<S>が提供されている。

意味合いを説明する。SWAGは以下の条件を満たす集合の二つ組 $(S, F)$ を要求する。前者が実装におけるElement、後者がFoldである

$s\in S$ を $f\in F$ に変換する関数 $f: S\rightarrow F$ が定義されている (convert)
関数 $g: (F, S) \rightarrow F$ が定義されている (pushBack)
関数 $h: (S, F) \rightarrow F$ が定義されている (pushFront)

dequeに挿入する各要素は $S$ の元であり、積を取った値が $F$ の元になる。

一要素からなる $s\in S$ の総積を取るために $f$ が必要
SWAGに値を追加したときの総積の更新に $g, h$ が必要

ここで、 $F$ 上の二項演算演算(operation)が結合律を満たすとき盆栽から直接product()を取得できるようになる。

更に、 $F$ とその二項演算がモノイドを成すとき、空列からproduct()を取得できるようになる。

参考

Depends on

Required by

Src/Sequence/EnumerateStaticLengthProduct.hpp

Verified with

Code

#pragma once

#include "./SWAGable.hpp"
#include "../../Algebra/Monoid/MonoidConcept.hpp"
#include "../../Algebra/Semigroup/SemigroupConcept.hpp"
#include "../../Template/TypeAlias.hpp"

#include <cassert>
#include <optional>
#include <vector>

namespace zawa {

template <concepts::SWAGable S>
class FoldableQueue {
public:

    using V = typename S::Element;
    using Fold = typename S::Fold;
    using F = typename Fold::Element;

    FoldableQueue() = default;

    usize size() const noexcept {
        return m_front.size() + m_back.size();
    }

    bool empty() const noexcept {
        return size() == 0u;
    }

    void push(const V& v) {
        m_raw.push_back(v);
        m_back.push_back(m_back.size() ? S::pushBack(m_back.back(), v) : S::convert(v));
    }

    void pop() {
        assert(size());
        move();
        m_front.pop_back();
    }

    std::pair<F, F> get() const requires concepts::Identitiable<typename S::Fold> {
        return {
            m_front.empty() ? Fold::identity() : m_front.back(),
            m_back.empty() ? Fold::identity() : m_back.back()
        };
    }

    std::pair<std::optional<F>, std::optional<F>> get() const {
        return {
            m_front.empty() ? std::nullopt : std::optional<F>{m_front.back().first},
            m_back.empty() ? std::nullopt : std::optional<F>{m_back.back().first}
        };
    }

    F product() const requires concepts::Monoid<typename S::Fold> {
        auto [f, b] = get();
        return Fold::operation(f, b);
    }

    F product() const requires concepts::Semigroup<typename S::Fold> {
        assert(m_front.size() or m_back.size());
        if (m_front.empty()) return m_back.back().first;
        if (m_back.empty()) return m_front.back().first;
        return S::Fold::operation(m_front.back().first, m_back.back().first);
    }
    
private:
    std::vector<F> m_front{}, m_back{};
    std::vector<V> m_raw{};

    void move() {
        if (m_front.size()) return;
        while (m_back.size()) {
            m_back.pop_back();
            V v{m_raw.back()};
            m_raw.pop_back();
            m_front.push_back(m_front.size() ? S::pushFront(m_front.back(), v) : S::convert(v));
        }
    }
};

} // namespace zawa

#line 2 "Src/DataStructure/SWAG/FoldableQueue.hpp"

#line 2 "Src/DataStructure/SWAG/SWAGable.hpp"

#line 2 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 2 "Src/Algebra/Semigroup/SemigroupConcept.hpp"

#include <concepts>

namespace zawa {

namespace concepts {

template <class T>
concept Semigroup = requires {
    typename T::Element;
    { T::operation(std::declval<typename T::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Element>;
};

} // namespace concepts

} // namespace zawa
#line 4 "Src/Algebra/Monoid/MonoidConcept.hpp"

#line 6 "Src/Algebra/Monoid/MonoidConcept.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept Identitiable = requires {
    typename T::Element;
    { T::identity() } -> std::same_as<typename T::Element>;
};

template <class T>
concept Monoid = Semigroup<T> and Identitiable<T>;

} // namespace

} // namespace zawa
#line 5 "Src/DataStructure/SWAG/SWAGable.hpp"

#line 7 "Src/DataStructure/SWAG/SWAGable.hpp"

namespace zawa {

namespace concepts {

template <class T>
concept SWAGable = requires {
    typename T::Element;
    typename T::Fold;
    typename T::Fold::Element;
    { T::convert(std::declval<typename T::Element>()) } -> std::same_as<typename T::Fold::Element>;
    { T::pushBack(std::declval<typename T::Fold::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Fold::Element>;
    { T::pushFront(std::declval<typename T::Fold::Element>(), std::declval<typename T::Element>()) } -> std::same_as<typename T::Fold::Element>;
};

} // namespace concepts

template <concepts::Semigroup S>
class SemigroupSWAGable {
public:
    using Element = typename S::Element;
    using Fold = S;
    using F = Fold::Element;
    static F convert(Element v) {
        return v;
    }
    static F pushBack(F f, Element v) {
        return S::operation(f, v);
    }
    static F pushFront(F f, Element v) {
        return S::operation(v, f);
    }
    static F operation(F l, F r) {
        return S::operation(l, r);
    }
};

template <concepts::Monoid S>
class MonoidSWAGable {
public:
    using Element = typename S::Element;
    using Fold = S;
    using F = Fold::Element;
    static F convert(Element v) {
        return v;
    }
    static F pushBack(F f, Element v) {
        return S::operation(f, v);
    }
    static F pushFront(F f, Element v) {
        return S::operation(v, f);
    }
    static F identity() {
        return S::identity();
    }
    static F operation(F l, F r) {
        return S::operation(l, r);
    }
};

} // namespace zawa
#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 7 "Src/DataStructure/SWAG/FoldableQueue.hpp"

#include <cassert>
#include <optional>
#include <vector>

namespace zawa {

template <concepts::SWAGable S>
class FoldableQueue {
public:

    using V = typename S::Element;
    using Fold = typename S::Fold;
    using F = typename Fold::Element;

    FoldableQueue() = default;

    usize size() const noexcept {
        return m_front.size() + m_back.size();
    }

    bool empty() const noexcept {
        return size() == 0u;
    }

    void push(const V& v) {
        m_raw.push_back(v);
        m_back.push_back(m_back.size() ? S::pushBack(m_back.back(), v) : S::convert(v));
    }

    void pop() {
        assert(size());
        move();
        m_front.pop_back();
    }

    std::pair<F, F> get() const requires concepts::Identitiable<typename S::Fold> {
        return {
            m_front.empty() ? Fold::identity() : m_front.back(),
            m_back.empty() ? Fold::identity() : m_back.back()
        };
    }

    std::pair<std::optional<F>, std::optional<F>> get() const {
        return {
            m_front.empty() ? std::nullopt : std::optional<F>{m_front.back().first},
            m_back.empty() ? std::nullopt : std::optional<F>{m_back.back().first}
        };
    }

    F product() const requires concepts::Monoid<typename S::Fold> {
        auto [f, b] = get();
        return Fold::operation(f, b);
    }

    F product() const requires concepts::Semigroup<typename S::Fold> {
        assert(m_front.size() or m_back.size());
        if (m_front.empty()) return m_back.back().first;
        if (m_back.empty()) return m_front.back().first;
        return S::Fold::operation(m_front.back().first, m_back.back().first);
    }
    
private:
    std::vector<F> m_front{}, m_back{};
    std::vector<V> m_raw{};

    void move() {
        if (m_front.size()) return;
        while (m_back.size()) {
            m_back.pop_back();
            V v{m_raw.back()};
            m_raw.pop_back();
            m_front.push_back(m_front.size() ? S::pushFront(m_front.back(), v) : S::convert(v));
        }
    }
};

} // namespace zawa

Foldable Queue (Src/DataStructure/SWAG/FoldableQueue.hpp)

概要

参考

Depends on

Required by

Verified with

Code

Foldable Queue
(Src/DataStructure/SWAG/FoldableQueue.hpp)