Foldable Deque
(Src/DataStructure/SWAG/FoldableDeque.hpp)

View this file on GitHub
Last update: 2025-04-17 19:44:48+09:00
Include: #include "Src/DataStructure/SWAG/FoldableDeque.hpp"

概要

半群の積が取れるDeque

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

雛形

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()を取得できるようになる。

参考

https://qiita.com/Shirotsume/items/4a2837b5895ef9a7aeb1

Depends on

Verified with

Code

#pragma once

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

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

namespace zawa {

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

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

    FoldableDeque() = default;

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

    inline bool empty() const {
        return m_front.empty() and m_back.empty();
    }

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

    void pushFront(const V& v) {
        m_front.push_back({
                m_front.empty() ? S::convert(v) : S::pushFront(m_front.back().first, v),
                v
                });
    }

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

    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);
    }

    V popFront() {
        assert(size());
        if (m_front.empty()) moveBtoF();
        V res = std::move(m_front.back().second);
        m_front.pop_back();
        return res;
    }

    V popBack() {
        assert(size());
        if (m_back.empty()) moveFtoB();
        V res = std::move(m_back.back().second);
        m_back.pop_back();
        return res;
    }

private:

    std::vector<std::pair<F, V>> m_front, m_back;

    void moveFtoB() {
        const usize sz = m_front.size() >> 1;
        std::vector<V> tmp(sz); 
        for (usize i = 0 ; i < sz ; i++) {
            tmp[i] = m_front.back().second;
            m_front.pop_back();
        }
        while (m_front.size()) {
            pushBack(m_front.back().second);
            m_front.pop_back();
        }
        for (usize i = sz ; i-- ; ) {
            pushFront(tmp[i]);
        }
    }

    void moveBtoF() {
        const usize sz = m_back.size() >> 1;
        std::vector<V> tmp(sz); 
        for (usize i = 0 ; i < sz ; i++) {
            tmp[i] = m_back.back().second;
            m_back.pop_back();
        }
        while (m_back.size()) {
            pushFront(m_back.back().second);
            m_back.pop_back();
        }
        for (usize i = sz ; i-- ; ) {
            pushBack(tmp[i]);
        }
    }
};

} // namespace zawa

#line 2 "Src/DataStructure/SWAG/FoldableDeque.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/FoldableDeque.hpp"

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

namespace zawa {

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

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

    FoldableDeque() = default;

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

    inline bool empty() const {
        return m_front.empty() and m_back.empty();
    }

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

    void pushFront(const V& v) {
        m_front.push_back({
                m_front.empty() ? S::convert(v) : S::pushFront(m_front.back().first, v),
                v
                });
    }

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

    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);
    }

    V popFront() {
        assert(size());
        if (m_front.empty()) moveBtoF();
        V res = std::move(m_front.back().second);
        m_front.pop_back();
        return res;
    }

    V popBack() {
        assert(size());
        if (m_back.empty()) moveFtoB();
        V res = std::move(m_back.back().second);
        m_back.pop_back();
        return res;
    }

private:

    std::vector<std::pair<F, V>> m_front, m_back;

    void moveFtoB() {
        const usize sz = m_front.size() >> 1;
        std::vector<V> tmp(sz); 
        for (usize i = 0 ; i < sz ; i++) {
            tmp[i] = m_front.back().second;
            m_front.pop_back();
        }
        while (m_front.size()) {
            pushBack(m_front.back().second);
            m_front.pop_back();
        }
        for (usize i = sz ; i-- ; ) {
            pushFront(tmp[i]);
        }
    }

    void moveBtoF() {
        const usize sz = m_back.size() >> 1;
        std::vector<V> tmp(sz); 
        for (usize i = 0 ; i < sz ; i++) {
            tmp[i] = m_back.back().second;
            m_back.pop_back();
        }
        while (m_back.size()) {
            pushFront(m_back.back().second);
            m_back.pop_back();
        }
        for (usize i = sz ; i-- ; ) {
            pushBack(tmp[i]);
        }
    }
};

} // namespace zawa

Foldable Deque (Src/DataStructure/SWAG/FoldableDeque.hpp)

概要

参考

Depends on

Verified with

Code

Foldable Deque
(Src/DataStructure/SWAG/FoldableDeque.hpp)