Typical rings (tools/rings.hpp)

They are typical rings.

License

Author

anqooqie

rings::of

template <tools::commutative_group A, tools::monoid M>
struct rings::of {
  using add = A;
  using mul = M;
};

It is a template to create a ring.

Constraints

tools::ring<tools::rings::of<A, M>> holds.

Time Complexity

Not applicable

rings::plus_multiplies

template <typename R>
struct rings::plus_multiplies {
  using add = tools::groups::plus<R>;
  using mul = tools::monoids::multiplies<R>;
};

It is a ring $(R, +, \times)$.

Constraints

tools::ring<tools::rings::plus_multiplies<R>> holds.

Time Complexity

Not applicable

rings::xor_and

template <typename R>
struct rings::xor_and {
  using add = tools::groups::bit_xor<R>;
  using mul = tools::monoids::bit_and<R>;
};

It is a commutative ring $(R, \oplus, \land)$.

Constraints

tools::ring<tools::rings::xor_and<R>> holds.

Time Complexity

Not applicable

Depends on

Required by

Verified with

Code

#ifndef TOOLS_RINGS_HPP
#define TOOLS_RINGS_HPP

#include "tools/commutative_group.hpp"
#include "tools/groups.hpp"
#include "tools/monoid.hpp"
#include "tools/monoids.hpp"
#include "tools/semirings.hpp"

namespace tools {
  namespace rings {
    template <tools::commutative_group A, tools::monoid M>
    using of = tools::semirings::of<A, M>;

    template <typename R>
    using plus_multiplies = tools::rings::of<tools::groups::plus<R>, tools::monoids::multiplies<R>>;

    template <typename R>
    using xor_and = tools::rings::of<tools::groups::bit_xor<R>, tools::monoids::bit_and<R>>;
  }
}

#endif

#line 1 "tools/rings.hpp"



#line 1 "tools/commutative_group.hpp"



#line 1 "tools/commutative_monoid.hpp"



#line 1 "tools/monoid.hpp"



#include <concepts>

namespace tools {
  template <typename M>
  concept monoid = requires(typename M::T x, typename M::T y) {
    { M::op(x, y) } -> std::same_as<typename M::T>;
    { M::e() } -> std::same_as<typename M::T>;
  };
}


#line 5 "tools/commutative_monoid.hpp"

namespace tools {
  template <typename M>
  concept commutative_monoid = tools::monoid<M>;
}


#line 1 "tools/group.hpp"



#line 6 "tools/group.hpp"

namespace tools {
  template <typename G>
  concept group = tools::monoid<G> && requires(typename G::T x) {
    { G::inv(x) } -> std::same_as<typename G::T>;
  };
}


#line 6 "tools/commutative_group.hpp"

namespace tools {
  template <typename G>
  concept commutative_group = tools::group<G> && tools::commutative_monoid<G>;
}


#line 1 "tools/groups.hpp"



#include <cstddef>
#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 7 "tools/groups.hpp"

namespace tools {
  namespace groups {
    template <typename G>
    struct bit_xor {
      using T = G;
      static T op(const T& x, const T& y) {
        return x ^ y;
      }
      static T e() {
        return T(0);
      }
      static T inv(const T& x) {
        return x;
      }
    };

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

    template <typename G>
    struct plus {
      using T = G;
      static T op(const T& x, const T& y) {
        return x + y;
      }
      static T e() {
        return T(0);
      }
      static T inv(const T& x) {
        return -x;
      }
    };
  }
}


#line 1 "tools/monoids.hpp"



#include <algorithm>
#include <cassert>
#line 8 "tools/monoids.hpp"
#include <limits>
#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;
      }
    };
  }
}


#line 1 "tools/semirings.hpp"



#line 8 "tools/semirings.hpp"

namespace tools {
  namespace semirings {
    template <tools::commutative_monoid A, tools::monoid M>
    struct of {
      using add = A;
      using mul = M;
    };

    template <typename R>
    using min_plus = tools::semirings::of<tools::monoids::min<R>, tools::groups::plus<R>>;

    template <typename R>
    using max_plus = tools::semirings::of<tools::monoids::max<R>, tools::groups::plus<R>>;

    template <typename R>
    using min_max = tools::semirings::of<tools::monoids::min<R>, tools::monoids::max<R>>;

    template <typename R>
    using max_min = tools::semirings::of<tools::monoids::max<R>, tools::monoids::min<R>>;
  }
}


#line 9 "tools/rings.hpp"

namespace tools {
  namespace rings {
    template <tools::commutative_group A, tools::monoid M>
    using of = tools::semirings::of<A, M>;

    template <typename R>
    using plus_multiplies = tools::rings::of<tools::groups::plus<R>, tools::monoids::multiplies<R>>;

    template <typename R>
    using xor_and = tools::rings::of<tools::groups::bit_xor<R>, tools::monoids::bit_and<R>>;
  }
}