Library/Algebraic/Monoid.hpp

• View this file on GitHub
• Last update: 2024-12-27 16:29:20+09:00
• Include: #include "Library/Algebraic/Monoid.hpp"

Required by

• Library/DataStructure/DynamicSegmentTree.hpp
• Library/DataStructure/LazySegmentTree.hpp
• Library/DataStructure/SegmentTree.hpp
• Library/Graph/Tree/ReRootingDP.hpp

Verified with

• Test/Algorithms/CoordinateCompression_comp.test.cpp
• Test/Algorithms/CoordinateCompression_to.test.cpp
• Test/DataStructure/DynamicSegmentTree.test.cpp
• Test/DataStructure/DynamicSegmentTree_RMQ.test.cpp
• Test/DataStructure/DynamicSegmentTree_RSQ.test.cpp
• Test/DataStructure/LazySegmentTree_RAQRMQ.test.cpp
• Test/DataStructure/LazySegmentTree_RAQRSQ.test.cpp
• Test/DataStructure/LazySegmentTree_RUQRMQ.test.cpp
• Test/DataStructure/LazySegmentTree_RUQRSQ.test.cpp
• Test/DataStructure/LazySegmentTree_maxright.test.cpp
• Test/DataStructure/SegmentTree_RMQ.test.cpp
• Test/DataStructure/SegmentTree_RSQ.test.cpp
• Test/DataStructure/SegmentTree_maxright.test.cpp
• Test/DataStructure/SegmentTree_minleft.test.cpp
• Test/Graph/Tree/HeavyLightDecomposition_edge.test.cpp
• Test/Graph/Tree/ReRootingDP.test.cpp
• Test/Graph/Tree/ReRootingDP_cost.test.cpp
• Test/String/LCPArray.test.cpp

Code

#pragma once

#include <iostream>

namespace mtd {

  template <class S,    // set
            S element,  // identity element
            class op    // binary operation
            >
  requires std::is_invocable_r_v<S, op, S, S>
  struct Monoid {
    using value_type = S;
    constexpr static S _element = element;
    using op_type = op;

    S m_val;
    constexpr Monoid(S val) : m_val(val) {}
    constexpr Monoid() : Monoid(element) {}
    constexpr Monoid binaryOperation(const Monoid& m2) const {
      return op()(m_val, m2.m_val);
    }
    friend std::ostream& operator<<(std::ostream& os,
                                    const Monoid<S, element, op>& m) {
      return os << m.m_val;
    }
  };

  namespace __detail {
    template <typename T, template <typename, auto, typename> typename S>
    concept is_monoid_specialization_of = requires {
      typename std::enable_if_t<std::is_same_v<
          T, S<typename T::value_type, T::_element, typename T::op_type>>>;
    };
  }  // namespace __detail

  template <typename M>
  concept monoid = __detail::is_monoid_specialization_of<M, Monoid>;

}  // namespace mtd

#line 2 "Library/Algebraic/Monoid.hpp"

#include <iostream>

namespace mtd {

  template <class S,    // set
            S element,  // identity element
            class op    // binary operation
            >
  requires std::is_invocable_r_v<S, op, S, S>
  struct Monoid {
    using value_type = S;
    constexpr static S _element = element;
    using op_type = op;

    S m_val;
    constexpr Monoid(S val) : m_val(val) {}
    constexpr Monoid() : Monoid(element) {}
    constexpr Monoid binaryOperation(const Monoid& m2) const {
      return op()(m_val, m2.m_val);
    }
    friend std::ostream& operator<<(std::ostream& os,
                                    const Monoid<S, element, op>& m) {
      return os << m.m_val;
    }
  };

  namespace __detail {
    template <typename T, template <typename, auto, typename> typename S>
    concept is_monoid_specialization_of = requires {
      typename std::enable_if_t<std::is_same_v<
          T, S<typename T::value_type, T::_element, typename T::op_type>>>;
    };
  }  // namespace __detail

  template <typename M>
  concept monoid = __detail::is_monoid_specialization_of<M, Monoid>;

}  // namespace mtd

Back to top page