fractions.hpp

Go to the documentation of this file.

#pragma once
 
// #include <boost/operators.hpp>
// #include <cmath>
// #include <numeric>
#include <type_traits>
#include <utility>
 
// #include "common_concepts.h"
 
#if __cpp_constexpr >= 201304
#    define CONSTEXPR14 constexpr
#else
#    define CONSTEXPR14 inline
#endif
 
namespace fun {
 
    template <typename T> CONSTEXPR14 auto abs(const T& a) ->
        typename std::enable_if<std::is_unsigned<T>::value, T>::type {
        return a;
    }
 
    template <typename T> CONSTEXPR14 auto abs(const T& a) ->
        typename std::enable_if<!std::is_unsigned<T>::value, T>::type {
        return (a < T(0)) ? -a : a;
    }
 
    template <typename Mn> CONSTEXPR14 auto gcd_recur(const Mn& _m, const Mn& _n) -> Mn {
        if (_n == 0) {
            return abs(_m);
        }
        return gcd_recur(_n, _m % _n);
    }
 
    template <typename Mn> CONSTEXPR14 auto gcd(const Mn& _m, const Mn& _n) -> Mn {
        if (_m == 0) {
            return abs(_n);
        }
        return gcd_recur(_m, _n);
    }
 
    template <typename Mn> CONSTEXPR14 auto lcm(const Mn& _m, const Mn& _n) -> Mn {
        if (_m == 0 || _n == 0) {
            return 0;
        }
        return (abs(_m) / gcd(_m, _n)) * abs(_n);
    }
 
    template <typename Z> struct Fraction {
        Z _num;
        Z _den;
 
        CONSTEXPR14 Fraction(Z num, Z den) : _num{std::move(num)}, _den{std::move(den)} {
            this->normalize();
        }
 
        CONSTEXPR14 auto normalize() -> Z {
            this->normalize1();
            return this->normalize2();
        }
 
        CONSTEXPR14 void normalize1() {
            if (this->_den < Z(0)) {
                this->_num = -this->_num;
                this->_den = -this->_den;
            }
        }
 
        CONSTEXPR14 auto normalize2() -> Z {
            Z common = gcd(this->_num, this->_den);
            if (common == Z(1) || common == Z(0)) {
                return common;
            }
            this->_num /= common;
            this->_den /= common;
            return common;
        }
 
        CONSTEXPR14 explicit Fraction(Z&& num) : _num{std::move(num)}, _den(Z(1)) {}
 
        CONSTEXPR14 explicit Fraction(const Z& num) : _num{num}, _den(1) {}
 
        CONSTEXPR14 Fraction() : _num(0), _den(1) {}
 
        CONSTEXPR14 auto num() const noexcept -> const Z& { return _num; }
 
        CONSTEXPR14 auto den() const noexcept -> const Z& { return _den; }
 
        CONSTEXPR14 auto cross(const Fraction& rhs) const -> Z {
            return this->_num * rhs._den - this->_den * rhs._num;
        }
 
 
        friend CONSTEXPR14 auto operator==(const Fraction& lhs, const Z& rhs) -> bool {
            if (lhs._den == Z(1) || rhs == Z(0)) {
                return lhs._num == rhs;
            }
            auto lhs2{lhs};
            auto rhs2{rhs};
            std::swap(lhs2._den, rhs2);
            lhs2.normalize2();
            return lhs2._num < lhs2._den * rhs2;
        }
 
        friend CONSTEXPR14 auto operator<(const Fraction& lhs, const Z& rhs) -> bool {
            if (lhs._den == Z(1) || rhs == Z(0)) {
                return lhs._num < rhs;
            }
            auto lhs2{lhs};
            auto rhs2{rhs};
            std::swap(lhs2._den, rhs2);
            lhs2.normalize2();
            return lhs2._num < lhs2._den * rhs2;
        }
 
        friend CONSTEXPR14 auto operator<(const Z& lhs, const Fraction& rhs) -> bool {
            if (rhs._den == Z(1) || lhs == Z(0)) {
                return lhs < rhs._num;
            }
            auto lhs2{lhs};
            auto rhs2{rhs};
            std::swap(rhs2._den, lhs2);
            rhs2.normalize2();
            return rhs2._den * lhs2 < rhs2._num;
        }
 
        friend CONSTEXPR14 auto operator==(const Z& lhs, const Fraction& rhs) -> bool {
            return rhs == lhs;
        }
 
        friend CONSTEXPR14 auto operator==(const Fraction& lhs, const Fraction& rhs) -> bool {
            if (lhs._den == rhs._den) {
                return lhs._num == rhs._num;
            }
            auto lhs2{lhs};
            auto rhs2{rhs};
            std::swap(lhs2._den, rhs2._num);
            lhs2.normalize2();
            rhs2.normalize2();
            return lhs2._num * rhs2._den == lhs2._den * rhs2._num;
        }
 
        friend CONSTEXPR14 auto operator<(const Fraction& lhs, const Fraction& rhs) -> bool {
            if (lhs._den == rhs._den) {
                return lhs._num < rhs._num;
            }
            auto lhs2{lhs};
            auto rhs2{rhs};
            std::swap(lhs2._den, rhs2._num);
            lhs2.normalize2();
            rhs2.normalize2();
            return lhs2._num * rhs2._den < lhs2._den * rhs2._num;
        }
 
        CONSTEXPR14 auto operator!=(const Fraction& rhs) const -> bool { return !(*this == rhs); }
 
        CONSTEXPR14 auto operator>(const Fraction& rhs) const -> bool { return rhs < *this; }
 
        CONSTEXPR14 auto operator>=(const Fraction& rhs) const -> bool { return !(*this < rhs); }
 
        CONSTEXPR14 auto operator<=(const Fraction& rhs) const -> bool { return !(rhs < *this); }
 
        CONSTEXPR14 auto operator>(const Z& rhs) const -> bool { return rhs < *this; }
 
        CONSTEXPR14 auto operator<=(const Z& rhs) const -> bool { return !(rhs < *this); }
 
        CONSTEXPR14 auto operator>=(const Z& rhs) const -> bool { return !(*this < rhs); }
 
        friend CONSTEXPR14 auto operator>(const Z& lhs, const Fraction& rhs) -> bool {
            return rhs < lhs;
        }
 
        friend CONSTEXPR14 auto operator<=(const Z& lhs, const Fraction& rhs) -> bool {
            return !(rhs < lhs);
        }
 
        friend CONSTEXPR14 auto operator>=(const Z& lhs, const Fraction& rhs) -> bool {
            return !(lhs < rhs);
        }
 
 
        CONSTEXPR14 void reciprocal() {
            std::swap(this->_num, this->_den);
            this->normalize1();
        }
 
        CONSTEXPR14 auto operator*=(Fraction rhs) -> Fraction& {
            std::swap(this->_num, rhs._num);
            this->normalize2();
            rhs.normalize2();
            this->_num *= rhs._num;
            this->_den *= rhs._den;
            return *this;
        }
 
        friend CONSTEXPR14 auto operator*(Fraction lhs, const Fraction& rhs) -> Fraction {
            return lhs *= rhs;
        }
 
        CONSTEXPR14 auto operator*=(Z rhs) -> Fraction& {
            std::swap(this->_num, rhs);
            this->normalize2();
            this->_num *= rhs;
            return *this;
        }
 
        friend CONSTEXPR14 auto operator*(Fraction lhs, const Z& rhs) -> Fraction {
            return lhs *= rhs;
        }
 
        friend CONSTEXPR14 auto operator*(const Z& lhs, Fraction rhs) -> Fraction {
            return rhs *= lhs;
        }
 
        CONSTEXPR14 auto operator/=(Fraction rhs) -> Fraction& {
            std::swap(this->_den, rhs._num);
            this->normalize();
            rhs.normalize2();
            this->_num *= rhs._den;
            this->_den *= rhs._num;
            return *this;
        }
 
        friend CONSTEXPR14 auto operator/(Fraction lhs, const Fraction& rhs) -> Fraction {
            return lhs /= rhs;
        }
 
        CONSTEXPR14 auto operator/=(Z rhs) -> Fraction& {
            std::swap(this->_den, rhs);
            this->normalize();
            this->_den *= rhs;
            return *this;
        }
 
        friend CONSTEXPR14 auto operator/(Fraction lhs, const Z& rhs) -> Fraction {
            return lhs /= rhs;
        }
 
        friend CONSTEXPR14 auto operator/(const Z& lhs, Fraction rhs) -> Fraction {
            rhs.reciprocal();
            return rhs *= lhs;
        }
 
        CONSTEXPR14 auto operator-() const -> Fraction {
            auto res = Fraction(*this);
            res._num = -res._num;
            return res;
        }
 
        CONSTEXPR14 auto operator+(const Fraction& rhs) const -> Fraction {
            if (this->_den == rhs._den) {
                return Fraction(this->_num + rhs._num, this->_den);
            }
            const auto common = gcd(this->_den, rhs._den);
            if (common == Z(0)) {
                return Fraction(rhs._den * this->_num + this->_den * rhs._num, Z(0));
            }
            const auto l = this->_den / common;
            const auto r = rhs._den / common;
            auto d = this->_den * r;
            auto n = r * this->_num + l * rhs._num;
            return Fraction(std::move(n), std::move(d));
        }
 
        CONSTEXPR14 auto operator-(const Fraction& frac) const -> Fraction {
            return *this + (-frac);
        }
 
        friend CONSTEXPR14 auto operator+(Fraction frac, const Z& i) -> Fraction {
            return frac += i;
        }
 
        friend CONSTEXPR14 auto operator+(const Z& i, Fraction frac) -> Fraction {
            return frac += i;
        }
 
        CONSTEXPR14 auto operator-(const Z& i) const -> Fraction { return *this + (-i); }
 
        CONSTEXPR14 auto operator+=(const Fraction& rhs) -> Fraction& { return *this -= (-rhs); }
 
        CONSTEXPR14 auto operator-=(const Fraction& rhs) -> Fraction& {
            if (this->_den == rhs._den) {
                this->_num -= rhs._num;
                this->normalize2();
                return *this;
            }
 
            auto other{rhs};
            std::swap(this->_den, other._num);
            auto common_n = this->normalize2();
            auto common_d = other.normalize2();
            std::swap(this->_den, other._num);
            this->_num = this->cross(other);
            this->_den *= other._den;
            std::swap(this->_den, common_d);
            this->normalize2();
            this->_num *= common_n;
            this->_den *= common_d;
            this->normalize2();
            return *this;
        }
 
        CONSTEXPR14 auto operator+=(const Z& i) -> Fraction& { return *this -= (-i); }
 
        CONSTEXPR14 auto operator-=(const Z& rhs) -> Fraction& {
            if (this->_den == Z(1)) {
                this->_num -= rhs;
                return *this;
            }
 
            auto other{rhs};
            std::swap(this->_den, other);
            auto common_n = this->normalize2();
            std::swap(this->_den, other);
            this->_num -= other * this->_den;
            this->_num *= common_n;
            this->normalize2();
            return *this;
        }
 
        friend CONSTEXPR14 auto operator-(const Z& c, const Fraction& frac) -> Fraction {
            return c + (-frac);
        }
 
        friend CONSTEXPR14 auto operator+(int&& c, const Fraction& frac) -> Fraction {
            return frac + Z(c);
        }
 
        friend CONSTEXPR14 auto operator-(int&& c, const Fraction& frac) -> Fraction {
            return (-frac) + Z(c);
        }
 
        friend CONSTEXPR14 auto operator*(int&& c, const Fraction& frac) -> Fraction {
            return frac * Z(c);
        }
 
        template <typename Stream> friend auto operator<<(Stream& os, const Fraction& frac)
            -> Stream& {
            os << "(" << frac.num() << "/" << frac.den() << ")";
            return os;
        }
    };
 
    // For template deduction
    // typename{Z} Fraction(const Z &, const Z &) noexcept -> Fraction<Z>;
 
}  // namespace fun