Typical monoids (tools/monoid.hpp)

They are typical monoids.

License

Author

anqooqie

monoid::max

(1) template <typename M> struct monoid::max;
(2) template <typename M, M E> struct monoid::max;

It is a monoid $(M, \max, E)$.

(1)
- If <M> is a built-in integral type, let $E$ be std::numeric_limits<M>::min().
- If <M> is a built-in floating-point type, let $E$ be -std::numeric_limits<M>::infinity().

Constraints

(1)
- $M$ is a built-in arithmetic type.
(2)
- $M$ is a built-in integral type.

Time Complexity

Not applicable

monoid::max::T

using T = M;

It is an alias for <M>.

Constraints

None

Time Complexity

Not applicable

monoid::max::op

static M op(M x, M y);

It returns $\max(x, y)$.

Constraints

$E \leq x$
$E \leq y$

Time Complexity

$O(1)$

monoid::max::e

static M e();

It returns $E$.

Constraints

None

Time Complexity

$O(1)$

monoid::min

(1) template <typename M> struct monoid::min;
(2) template <typename M, M E> struct monoid::min;

It is a monoid $(M, \min, E)$.

(1)
- If <M> is a built-in integral type, let $E$ be std::numeric_limits<M>::max().
- If <M> is a built-in floating-point type, let $E$ be std::numeric_limits<M>::infinity().

Constraints

(1)
- $M$ is a built-in arithmetic type.
(2)
- $M$ is a built-in integral type.

Time Complexity

Not applicable

monoid::min::T

using T = M;

It is an alias for <M>.

Constraints

None

Time Complexity

Not applicable

monoid::min::op

static M op(M x, M y);

It returns $\min(x, y)$.

Constraints

$x \leq E$
$y \leq E$

Time Complexity

$O(1)$

monoid::min::e

static M e();

It returns $E$.

Constraints

None

Time Complexity

$O(1)$

monoid::multiplies

template <typename M> struct monoid::multiplies;

It is a monoid $(M, \times, 1)$.

Constraints

If x is <M> and y is <M>, then x * y is also <M>.
For all x in <M>, y in <M> and z in <M>, (x * y) * z $=$ x * (y * z).
For all x in <M>, M(1) * x $=$ x * M(1) $=$ x.

Time Complexity

Not applicable

monoid::multiplies::T

using T = M;

It is an alias for <M>.

Constraints

None

Time Complexity

Not applicable

monoid::multiplies::op

static M op(M x, M y);

It returns x * y.

Constraints

None

Time Complexity

Same as that of x * y

monoid::multiplies::e

static M e();

It returns M(1).

Constraints

None

Time Complexity

Same as that of M(1)

monoid::gcd

template <typename M> struct monoid::gcd;

It is a monoid $(M, \gcd, 0)$. Note that we define $\gcd(a, 0) = a$, $\gcd(0, b) = b$ and $\gcd(0, 0) = 0$ in this monoid.

Constraints

tools::gcd(x, y) is defined for x and y of type <M>. In particular, <M> is neither a built-in floating-point type nor bool.

Time Complexity

Not applicable

monoid::gcd::T

using T = M;

It is an alias for <M>.

Constraints

None

Time Complexity

Not applicable

monoid::gcd::op

static M op(M x, M y);

It returns tools::gcd(x, y). For a built-in integral type <M>, this is equivalent to returning std::gcd(x, y).

Constraints

None

Time Complexity

Same as that of tools::gcd(x, y)

monoid::gcd::e

static M e();

It returns M(0).

Constraints

None

Time Complexity

Same as that of M(0).

monoid::update

template <typename M, M E> struct monoid::update;

It is a monoid $(M, U, E)$ where

\[\begin{align*} U(x, y) &= \left\{\begin{array}{ll} y & \text{(if $x = E$)}\\ x & \text{(if $x \neq E$)} \end{array}\right. \end{align*}\]

Constraints

<M> is a built-in integral type.

Time Complexity

Not applicable

monoid::update::T

using T = M;

It is an alias for <M>.

Constraints

None

Time Complexity

Not applicable

monoid::update::op

static M op(M x, M y);

It returns $U(x, y)$.

Constraints

None

Time Complexity

$O(1)$

monoid::update::e

static M e();

It returns E.

Constraints

None

Time Complexity

$O(1)$

Depends on

std::gcd(m, n) extended for my library (tools/gcd.hpp)

Required by

Verified with

Code

#ifndef TOOLS_MONOID_HPP
#define TOOLS_MONOID_HPP

#include <type_traits>
#include <algorithm>
#include <limits>
#include <cassert>
#include "tools/gcd.hpp"

namespace tools {
  namespace monoid {
    template <typename M, M ...dummy>
    struct max;

    template <typename M>
    struct max<M> {
      static_assert(::std::is_arithmetic_v<M>, "M must be a built-in arithmetic type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return ::std::max(lhs, rhs);
      }
      static T e() {
        if constexpr (::std::is_integral_v<M>) {
          return ::std::numeric_limits<M>::min();
        } else {
          return -::std::numeric_limits<M>::infinity();
        }
      }
    };

    template <typename M, M E>
    struct max<M, E> {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        assert(E <= lhs);
        assert(E <= rhs);
        return ::std::max(lhs, rhs);
      }
      static T e() {
        return E;
      }
    };

    template <typename M, M ...dummy>
    struct min;

    template <typename M>
    struct min<M> {
      static_assert(::std::is_arithmetic_v<M>, "M must be a built-in arithmetic type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return ::std::min(lhs, rhs);
      }
      static T e() {
        if constexpr (::std::is_integral_v<M>) {
          return ::std::numeric_limits<M>::max();
        } else {
          return ::std::numeric_limits<M>::infinity();
        }
      }
    };

    template <typename M, M E>
    struct min<M, E> {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        assert(lhs <= E);
        assert(rhs <= E);
        return ::std::min(lhs, rhs);
      }
      static T e() {
        return E;
      }
    };

    template <typename M>
    struct multiplies {
    private:
      using VR = ::std::conditional_t<::std::is_arithmetic_v<M>, const M, const M&>;

    public:
      using T = M;
      static T op(VR lhs, VR rhs) {
        return lhs * rhs;
      }
      static T e() {
        return T(1);
      }
    };

    template <>
    struct multiplies<bool> {
      using T = bool;
      static T op(const bool lhs, const bool rhs) {
        return lhs && rhs;
      }
      static T e() {
        return true;
      }
    };

    template <typename M>
    struct gcd {
    private:
      static_assert(!::std::is_arithmetic_v<M> || (::std::is_integral_v<M> && !::std::is_same_v<M, bool>), "If M is a built-in arithmetic type, it must be integral except for bool.");
      using VR = ::std::conditional_t<::std::is_arithmetic_v<M>, const M, const M&>;

    public:
      using T = M;
      static T op(VR lhs, VR rhs) {
        return ::tools::gcd(lhs, rhs);
      }
      static T e() {
        return T(0);
      }
    };

    template <typename M, M E>
    struct update {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return lhs == E ? rhs : lhs;
      }
      static T e() {
        return E;
      }
    };
  }
}

#endif

#line 1 "tools/monoid.hpp"



#include <type_traits>
#include <algorithm>
#include <limits>
#include <cassert>
#line 1 "tools/gcd.hpp"



#line 5 "tools/gcd.hpp"
#include <numeric>

namespace tools {
  template <typename M, typename N>
  constexpr ::std::common_type_t<M, N> gcd(const M m, const N n) {
    return ::std::gcd(m, n);
  }
}


#line 9 "tools/monoid.hpp"

namespace tools {
  namespace monoid {
    template <typename M, M ...dummy>
    struct max;

    template <typename M>
    struct max<M> {
      static_assert(::std::is_arithmetic_v<M>, "M must be a built-in arithmetic type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return ::std::max(lhs, rhs);
      }
      static T e() {
        if constexpr (::std::is_integral_v<M>) {
          return ::std::numeric_limits<M>::min();
        } else {
          return -::std::numeric_limits<M>::infinity();
        }
      }
    };

    template <typename M, M E>
    struct max<M, E> {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        assert(E <= lhs);
        assert(E <= rhs);
        return ::std::max(lhs, rhs);
      }
      static T e() {
        return E;
      }
    };

    template <typename M, M ...dummy>
    struct min;

    template <typename M>
    struct min<M> {
      static_assert(::std::is_arithmetic_v<M>, "M must be a built-in arithmetic type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return ::std::min(lhs, rhs);
      }
      static T e() {
        if constexpr (::std::is_integral_v<M>) {
          return ::std::numeric_limits<M>::max();
        } else {
          return ::std::numeric_limits<M>::infinity();
        }
      }
    };

    template <typename M, M E>
    struct min<M, E> {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        assert(lhs <= E);
        assert(rhs <= E);
        return ::std::min(lhs, rhs);
      }
      static T e() {
        return E;
      }
    };

    template <typename M>
    struct multiplies {
    private:
      using VR = ::std::conditional_t<::std::is_arithmetic_v<M>, const M, const M&>;

    public:
      using T = M;
      static T op(VR lhs, VR rhs) {
        return lhs * rhs;
      }
      static T e() {
        return T(1);
      }
    };

    template <>
    struct multiplies<bool> {
      using T = bool;
      static T op(const bool lhs, const bool rhs) {
        return lhs && rhs;
      }
      static T e() {
        return true;
      }
    };

    template <typename M>
    struct gcd {
    private:
      static_assert(!::std::is_arithmetic_v<M> || (::std::is_integral_v<M> && !::std::is_same_v<M, bool>), "If M is a built-in arithmetic type, it must be integral except for bool.");
      using VR = ::std::conditional_t<::std::is_arithmetic_v<M>, const M, const M&>;

    public:
      using T = M;
      static T op(VR lhs, VR rhs) {
        return ::tools::gcd(lhs, rhs);
      }
      static T e() {
        return T(0);
      }
    };

    template <typename M, M E>
    struct update {
      static_assert(::std::is_integral_v<M>, "M must be a built-in integral type.");

      using T = M;
      static T op(const T lhs, const T rhs) {
        return lhs == E ? rhs : lhs;
      }
      static T e() {
        return E;
      }
    };
  }
}