Typical monoids (tools/monoids.hpp)

They are typical monoids.

License

Author

anqooqie

monoids::bit_and

template <typename M> struct monoids::bit_and;

It is a commutative monoid $(M, \mathrm{AND}, $std::numeric_limits<M>::max()$)$.

Constraints

tools::commutative_monoid<tools::monoids::bit_and<M>> holds.

Time Complexity

Not applicable

monoids::bit_and::T

using T = M;

It is an alias for <M>.

Constraints

None

Time Complexity

Not applicable

monoids::bit_and::op

static M op(M x, M y);

It returns x & y.

Constraints

None

Time Complexity

Same as that of x & y

monoids::bit_and::e

static M e();

It returns std::numeric_limits<M>::max().

Constraints

None

Time Complexity

Same as that of std::numeric_limits<M>::max()

monoids::bit_or

template <typename M> struct monoids::bit_or;

It is a commutative monoid $(M, \mathrm{OR}, 0)$.

Constraints

tools::commutative_monoid<tools::monoids::bit_or<M>> holds.

Time Complexity

Not applicable

monoids::bit_or::T

using T = M;

It is an alias for <M>.

Constraints

None

Time Complexity

Not applicable

monoids::bit_or::op

static M op(M x, M y);

It returns x | y.

Constraints

None

Time Complexity

Same as that of x | y

monoids::bit_or::e

static M e();

It returns M(0).

Constraints

None

Time Complexity

Same as that of M(0)

monoids::gcd

template <typename M>
requires requires (M x, M y) {
  {tools::gcd(x, y)} -> std::convertible_to<M>;
}
struct monoids::gcd;

It is a commutative 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

None

Time Complexity

Not applicable

monoids::gcd::T

using T = M;

It is an alias for <M>.

Constraints

None

Time Complexity

Not applicable

monoids::gcd::op

static M op(M x, M y);

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

Constraints

None

Time Complexity

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

monoids::gcd::e

static M e();

It returns M(0).

Constraints

None

Time Complexity

Same as that of M(0).

monoids::max

(1) template <tools::arithmetic M> struct monoids::max;
(2) template <std::totally_ordered M, M E> struct monoids::max;

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

(1)
- If tools::integral<M>, let $E$ be std::numeric_limits<M>::min().
- If std::floating_point<M>, let $E$ be -std::numeric_limits<M>::infinity().

Constraints

None

Time Complexity

Not applicable

monoids::max::T

using T = M;

It is an alias for <M>.

Constraints

None

Time Complexity

Not applicable

monoids::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)$

monoids::max::e

static M e();

It returns $E$.

Constraints

None

Time Complexity

$O(1)$

monoids::min

(1) template <tools::arithmetic M> struct monoids::min;
(2) template <std::totally_ordered M, M E> struct monoids::min;

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

(1)
- If tools::integral<M>, let $E$ be std::numeric_limits<M>::max().
- If std::floating_point<M>, let $E$ be std::numeric_limits<M>::infinity().

Constraints

None

Time Complexity

Not applicable

monoids::min::T

using T = M;

It is an alias for <M>.

Constraints

None

Time Complexity

Not applicable

monoids::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)$

monoids::min::e

static M e();

It returns $E$.

Constraints

None

Time Complexity

$O(1)$

monoids::multiplies

template <typename M> struct monoids::multiplies;

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

Constraints

tools::monoid<tools::monoids::multiplies<M>> holds.

Time Complexity

Not applicable

monoids::multiplies::T

using T = M;

It is an alias for <M>.

Constraints

None

Time Complexity

Not applicable

monoids::multiplies::op

static M op(M x, M y);

It returns x * y.

Constraints

None

Time Complexity

Same as that of x * y

monoids::multiplies::e

static M e();

It returns M(1).

Constraints

None

Time Complexity

Same as that of M(1)

monoids::update

template <typename M, M E> struct monoids::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

None

Time Complexity

Not applicable

monoids::update::T

using T = M;

It is an alias for <M>.

Constraints

None

Time Complexity

Not applicable

monoids::update::op

static M op(M x, M y);

It returns $U(x, y)$.

Constraints

None

Time Complexity

$O(1)$

monoids::update::e

static M e();

It returns E.

Constraints

None

Time Complexity

$O(1)$

Depends on

Required by

Verified with

Code

#ifndef TOOLS_MONOIDS_HPP
#define TOOLS_MONOIDS_HPP

#include <algorithm>
#include <cassert>
#include <concepts>
#include <cstddef>
#include <limits>
#include <type_traits>
#include "tools/arithmetic.hpp"
#include "tools/gcd.hpp"
#include "tools/integral.hpp"
#include "tools/non_bool_integral.hpp"

namespace tools {
  namespace monoids {
    template <typename M>
    struct bit_and {
      using T = M;
      static T op(const T& x, const T& y) {
        return x & y;
      }
      static T e() {
        return std::numeric_limits<T>::max();
      }
    };

    template <typename M>
    struct bit_or {
      using T = M;
      static T op(const T& x, const T& y) {
        return x | y;
      }
      static T e() {
        return T(0);
      }
    };

    template <typename M>
    requires requires (M x, M y) {
      {tools::gcd(x, y)} -> std::convertible_to<M>;
    }
    struct gcd {
      using T = M;
      static T op(const T& x, const T& y) {
        return tools::gcd(x, y);
      }
      static T e() {
        return T(0);
      }
    };

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

    template <tools::arithmetic M>
    struct max<M> {
      using T = M;
      static T op(const T& x, const T& y) {
        return std::max(x, y);
      }
      static T e() {
        if constexpr (tools::integral<M>) {
          return std::numeric_limits<M>::min();
        } else {
          return -std::numeric_limits<M>::infinity();
        }
      }
    };

    template <std::totally_ordered M, M E>
    struct max<M, E> {
      using T = M;
      static T op(const T& x, const T& y) {
        assert(E <= x);
        assert(E <= y);
        return std::max(x, y);
      }
      static T e() {
        return E;
      }
    };

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

    template <tools::arithmetic M>
    struct min<M> {
      using T = M;
      static T op(const T& x, const T& y) {
        return std::min(x, y);
      }
      static T e() {
        if constexpr (tools::integral<M>) {
          return std::numeric_limits<M>::max();
        } else {
          return std::numeric_limits<M>::infinity();
        }
      }
    };

    template <std::totally_ordered M, M E>
    struct min<M, E> {
      using T = M;
      static T op(const T& x, const T& y) {
        assert(x <= E);
        assert(y <= E);
        return std::min(x, y);
      }
      static T e() {
        return E;
      }
    };

    template <typename M>
    struct multiplies {
      using T = M;
      static T op(const T& x, const T& y) {
        return x * y;
      }
      static T e() {
        return T(1);
      }
    };

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

    template <typename M, M E>
    struct update {
      using T = M;
      static T op(const T& x, const T& y) {
        return x == E ? y : x;
      }
      static T e() {
        return E;
      }
    };
  }
}

#endif

#line 1 "tools/monoids.hpp"



#include <algorithm>
#include <cassert>
#include <concepts>
#include <cstddef>
#include <limits>
#include <type_traits>
#line 1 "tools/arithmetic.hpp"



#line 1 "tools/integral.hpp"



#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = tools::is_integral<T>::value;
}


#line 5 "tools/integral.hpp"

namespace tools {
  template <typename T>
  concept integral = tools::is_integral_v<T>;
}


#line 6 "tools/arithmetic.hpp"

namespace tools {
  template <typename T>
  concept arithmetic = tools::integral<T> || std::floating_point<T>;
}


#line 1 "tools/gcd.hpp"



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

namespace tools {
  namespace detail::gcd {
    template <typename M, typename N>
    struct impl {
      constexpr decltype(auto) operator()(const M m, const N n) const noexcept(noexcept(std::gcd(m, n))) {
        return std::gcd(m, n);
      }
    };
  }

  template <typename M, typename N>
  constexpr decltype(auto) gcd(M&& m, N&& n) noexcept(noexcept(tools::detail::gcd::impl<std::remove_cvref_t<M>, std::remove_cvref_t<N>>{}(std::forward<M>(m), std::forward<N>(n)))) {
    return tools::detail::gcd::impl<std::remove_cvref_t<M>, std::remove_cvref_t<N>>{}(std::forward<M>(m), std::forward<N>(n));
  }
}


#line 1 "tools/non_bool_integral.hpp"



#line 7 "tools/non_bool_integral.hpp"

namespace tools {
  template <typename T>
  concept non_bool_integral = tools::integral<T> && !std::same_as<std::remove_cv_t<T>, bool>;
}


#line 14 "tools/monoids.hpp"

namespace tools {
  namespace monoids {
    template <typename M>
    struct bit_and {
      using T = M;
      static T op(const T& x, const T& y) {
        return x & y;
      }
      static T e() {
        return std::numeric_limits<T>::max();
      }
    };

    template <typename M>
    struct bit_or {
      using T = M;
      static T op(const T& x, const T& y) {
        return x | y;
      }
      static T e() {
        return T(0);
      }
    };

    template <typename M>
    requires requires (M x, M y) {
      {tools::gcd(x, y)} -> std::convertible_to<M>;
    }
    struct gcd {
      using T = M;
      static T op(const T& x, const T& y) {
        return tools::gcd(x, y);
      }
      static T e() {
        return T(0);
      }
    };

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

    template <tools::arithmetic M>
    struct max<M> {
      using T = M;
      static T op(const T& x, const T& y) {
        return std::max(x, y);
      }
      static T e() {
        if constexpr (tools::integral<M>) {
          return std::numeric_limits<M>::min();
        } else {
          return -std::numeric_limits<M>::infinity();
        }
      }
    };

    template <std::totally_ordered M, M E>
    struct max<M, E> {
      using T = M;
      static T op(const T& x, const T& y) {
        assert(E <= x);
        assert(E <= y);
        return std::max(x, y);
      }
      static T e() {
        return E;
      }
    };

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

    template <tools::arithmetic M>
    struct min<M> {
      using T = M;
      static T op(const T& x, const T& y) {
        return std::min(x, y);
      }
      static T e() {
        if constexpr (tools::integral<M>) {
          return std::numeric_limits<M>::max();
        } else {
          return std::numeric_limits<M>::infinity();
        }
      }
    };

    template <std::totally_ordered M, M E>
    struct min<M, E> {
      using T = M;
      static T op(const T& x, const T& y) {
        assert(x <= E);
        assert(y <= E);
        return std::min(x, y);
      }
      static T e() {
        return E;
      }
    };

    template <typename M>
    struct multiplies {
      using T = M;
      static T op(const T& x, const T& y) {
        return x * y;
      }
      static T e() {
        return T(1);
      }
    };

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

    template <typename M, M E>
    struct update {
      using T = M;
      static T op(const T& x, const T& y) {
        return x == E ? y : x;
      }
      static T e() {
        return E;
      }
    };
  }
}