単一要素からなる多重集合か判定するモノイド
(Src/Algebra/Monoid/SameMonoid.hpp)

View this file on GitHub
Last update: 2024-02-25 01:37:51+09:00
Include: #include "Src/Algebra/Monoid/SameMonoid.hpp"

概要

しばしば「指定された集合 $S$ に属する要素が全て同じ値か $o(|S|)$ で判定せよ」といった問題が要求されることがある。

数列 $A$ の区間 $[l, r)$ に属する要素が… 等

こういったクエリをデータ構造に載せたい時用。

std::optional<T>の運用については std::optional cpprefjp 等も参考にすること。

使い方

コンストラクタ

(1) SameMonoidData<T>() = default;
(2) SameMonoidData<T>(const T& element)
(3) SameMonoidData<T>(const std::optional<T>& element, bool same)

(1) 空集合の時 (2) 単一要素elementからなる集合の時 (3) ユーザー側からの使用は特に想定していない。protectedとかにすればよかったかも。

empty

bool SameMonoidData<T>::empty() const noexcept

持っている集合が空集合の時true

same

bool SameMonoidData<T>::same() const noexcept

持っている集合が空または単一要素からなる多重集合の時true

element

std::optional<T> SameMonoidData<T>::element() const noexcept

集合の代表元を返す。集合が空だったり単一要素から構成されていない場合はstd::nulloptが返る。

value

T SameMonoidData<T>::value() const noexcept

集合の代表元を返す。集合が空だったり単一要素から構成されていない場合は実行時エラーになる。

Verified with

Code

#pragma once

#include <optional>

namespace zawa {

template <class T>
class SameMonoidData {
private:
    std::optional<T> element_{};
    bool same_{true};
public:

    static std::optional<T> merge(const std::optional<T>& l, const std::optional<T>& r) noexcept {
        if (l and r) return (l.value() == r.value() ? l : std::nullopt);
        if (l) return l;
        if (r) return r;
        return std::nullopt;
    }

    SameMonoidData() = default;
    SameMonoidData(const T& element) 
        : element_{element}, same_{true} {}
    SameMonoidData(const std::optional<T>& element, bool same)
        : element_{element}, same_{same} {}

    bool empty() const noexcept {
        return same_ and !element_.has_value();
    }
    bool same() const noexcept {
        return same_;
    }
    std::optional<T> element() const noexcept {
        return element_;
    }
    T value() const noexcept {
        return element_.value();
    }
};

template <class T>
struct SameMonoid {
public:
    using Element = SameMonoidData<T>;
    static Element identity() noexcept {
        return Element{}; 
    }
    static Element operation(const Element& l, const Element& r) {
        if (l.empty() and r.empty()) return identity();
        if (l.empty()) return r;
        if (r.empty()) return l;
        std::optional<T> element{Element::merge(l.element(), r.element())};
        return Element{element, l.same() and r.same() and element.has_value()};
    }
};

} // namespace zawa

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

#include <optional>

namespace zawa {

template <class T>
class SameMonoidData {
private:
    std::optional<T> element_{};
    bool same_{true};
public:

    static std::optional<T> merge(const std::optional<T>& l, const std::optional<T>& r) noexcept {
        if (l and r) return (l.value() == r.value() ? l : std::nullopt);
        if (l) return l;
        if (r) return r;
        return std::nullopt;
    }

    SameMonoidData() = default;
    SameMonoidData(const T& element) 
        : element_{element}, same_{true} {}
    SameMonoidData(const std::optional<T>& element, bool same)
        : element_{element}, same_{same} {}

    bool empty() const noexcept {
        return same_ and !element_.has_value();
    }
    bool same() const noexcept {
        return same_;
    }
    std::optional<T> element() const noexcept {
        return element_;
    }
    T value() const noexcept {
        return element_.value();
    }
};

template <class T>
struct SameMonoid {
public:
    using Element = SameMonoidData<T>;
    static Element identity() noexcept {
        return Element{}; 
    }
    static Element operation(const Element& l, const Element& r) {
        if (l.empty() and r.empty()) return identity();
        if (l.empty()) return r;
        if (r.empty()) return l;
        std::optional<T> element{Element::merge(l.element(), r.element())};
        return Element{element, l.same() and r.same() and element.has_value()};
    }
};

} // namespace zawa

単一要素からなる多重集合か判定するモノイド (Src/Algebra/Monoid/SameMonoid.hpp)

概要

使い方