fractions.hpp

Go to the documentation of this file.

// -*- coding: utf-16 -*-
#pragma once
 
// #include <boost/operators.hpp>
// #include <cmath>
#include <numeric>
#include <type_traits>
#include <utility>
 
#include "common_concepts.h"
 
namespace fun {
 
    template <typename T> constexpr auto abs(const T& a) -> T {
        if constexpr (std::is_unsigned_v<T>) {
            return a;
        } else {
            return (a < T(0)) ? -a : a;
        }
    }
 
    template <Integral Mn> constexpr auto gcd_recur(const Mn& _m, const Mn& _n) -> Mn {
        if (_n == 0) {
            return abs(_m);
        }
        return gcd_recur(_n, _m % _n);
    }
 
    template <Integral Mn> constexpr auto gcd(const Mn& _m, const Mn& _n) -> Mn {
        if (_m == 0) {
            return abs(_n);
        }
        return gcd_recur(_m, _n);
    }
 
    template <Integral Mn> constexpr 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 <Integral Z> struct Fraction {
        Z _num;
        Z _den;
 
        constexpr Fraction(Z num, Z den) : _num{std::move(num)}, _den{std::move(den)} {
            this->normalize();
        }
 
        constexpr auto normalize() -> Z {
            this->normalize1();
            return this->normalize2();
        }
 
        constexpr void normalize1() {
            if (this->_den < Z(0)) {
                this->_num = -this->_num;
                this->_den = -this->_den;
            }
        }
 
        constexpr 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;
        }
 
        constexpr explicit Fraction(Z&& num) : _num{std::move(num)}, _den(Z(1)) {}
 
        constexpr explicit Fraction(const Z& num) : _num{num}, _den(1) {}
 
        constexpr Fraction() : _num(0), _den(1) {}
 
        [[nodiscard]] constexpr auto num() const noexcept -> const Z& { return _num; }
 
        [[nodiscard]] constexpr auto den() const noexcept -> const Z& { return _den; }
 
        constexpr auto cross(const Fraction& rhs) const -> Z {
            return this->_num * rhs._den - this->_den * rhs._num;
        }
 
 
        friend constexpr auto operator==(Fraction lhs, Z rhs) -> bool {
            if (lhs._den == Z(1) || rhs == Z(0)) {
                return lhs._num == rhs;
            }
            std::swap(lhs._den, rhs);
            lhs.normalize2();
            return lhs._num == lhs._den * rhs;
        }
 
        friend constexpr auto operator<(Fraction lhs, Z rhs) -> bool {
            if (lhs._den == Z(1) || rhs == Z(0)) {
                return lhs._num < rhs;
            }
            std::swap(lhs._den, rhs._num);
            lhs.normalize2();
            return lhs._num < lhs._den * rhs;
        }
 
        friend constexpr auto operator<(Z lhs, Fraction rhs) -> bool {
            if (rhs._den == Z(1) || lhs == Z(0)) {
                return lhs < rhs._num;
            }
            std::swap(rhs._den, lhs);
            rhs.normalize2();
            return rhs._den * lhs < rhs._num;
        }
 
        friend constexpr auto operator==(const Z& lhs, const Fraction& rhs) -> bool {
            return rhs == lhs;
        }
 
        constexpr friend auto operator==(Fraction lhs, Fraction rhs) -> bool {
            if (lhs._den == rhs._den) {
                return lhs._num == rhs._num;
            }
            std::swap(lhs._den, rhs._num);
            lhs.normalize2();
            rhs.normalize2();
            return lhs._num * rhs._den == lhs._den * rhs._num;
        }
 
        constexpr friend auto operator<(Fraction lhs, Fraction rhs) -> bool {
            if (lhs._den == rhs._den) {
                return lhs._num < rhs._num;
            }
            std::swap(lhs._den, rhs._num);
            lhs.normalize2();
            rhs.normalize2();
            return lhs._num * rhs._den < lhs._den * rhs._num;
        }
 
        constexpr auto operator!=(const Fraction& rhs) const -> bool { return !(*this == rhs); }
 
        constexpr auto operator>(const Fraction& rhs) const -> bool { return rhs < *this; }
 
        constexpr auto operator>=(const Fraction& rhs) const -> bool { return !(*this < rhs); }
 
        constexpr auto operator<=(const Fraction& rhs) const -> bool { return !(rhs < *this); }
 
        constexpr auto operator>(const Z& rhs) const -> bool { return rhs < *this; }
 
        constexpr auto operator<=(const Z& rhs) const -> bool { return !(rhs < *this); }
 
        constexpr auto operator>=(const Z& rhs) const -> bool { return !(*this < rhs); }
 
        friend constexpr auto operator>(const Z& lhs, const Fraction& rhs) -> bool {
            return rhs < lhs;
        }
 
        friend constexpr auto operator<=(const Z& lhs, const Fraction& rhs) -> bool {
            return !(rhs < lhs);
        }
 
        friend constexpr auto operator>=(const Z& lhs, const Fraction& rhs) -> bool {
            return !(lhs < rhs);
        }
 
 
        constexpr void reciprocal() noexcept(std::is_nothrow_swappable_v<Z>) {
            std::swap(this->_num, this->_den);
            this->normalize1();
        }
 
        constexpr 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 constexpr auto operator*(Fraction lhs, const Fraction& rhs) -> Fraction {
            return lhs *= rhs;
        }
 
        constexpr auto operator*=(Z rhs) -> Fraction& {
            std::swap(this->_num, rhs);
            this->normalize2();
            this->_num *= rhs;
            return *this;
        }
 
        friend constexpr auto operator*(Fraction lhs, const Z& rhs) -> Fraction {
            return lhs *= rhs;
        }
 
        friend constexpr auto operator*(const Z& lhs, Fraction rhs) -> Fraction {
            return rhs *= lhs;
        }
 
        constexpr 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 constexpr auto operator/(Fraction lhs, const Fraction& rhs) -> Fraction {
            return lhs /= rhs;
        }
 
        constexpr auto operator/=(const Z& rhs) -> Fraction& {
            std::swap(this->_den, rhs);
            this->normalize();
            this->_den *= rhs;
            return *this;
        }
 
        friend constexpr auto operator/(Fraction lhs, const Z& rhs) -> Fraction {
            return lhs /= rhs;
        }
 
        friend constexpr auto operator/(const Z& lhs, Fraction rhs) -> Fraction {
            rhs.reciprocal();
            return rhs *= lhs;
        }
 
        constexpr auto operator-() const -> Fraction {
            auto res = Fraction(*this);
            res._num = -res._num;
            return res;
        }
 
        constexpr 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));
        }
 
        constexpr auto operator-(const Fraction& frac) const -> Fraction { return *this + (-frac); }
 
        friend constexpr auto operator+(Fraction frac, const Z& i) -> Fraction { return frac += i; }
 
        friend constexpr auto operator+(const Z& i, Fraction frac) -> Fraction { return frac += i; }
 
        constexpr auto operator-(const Z& i) const -> Fraction { return *this + (-i); }
 
        constexpr auto operator+=(const Fraction& rhs) -> Fraction& { return *this -= (-rhs); }
 
        constexpr 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;
        }
 
        constexpr auto operator+=(const Z& i) -> Fraction& { return *this -= (-i); }
 
        constexpr 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 constexpr auto operator-(const Z& c, const Fraction& frac) -> Fraction {
            return c + (-frac);
        }
 
        friend constexpr auto operator+(int&& c, const Fraction& frac) -> Fraction {
            return frac + Z(c);
        }
 
        friend constexpr auto operator-(int&& c, const Fraction& frac) -> Fraction {
            return (-frac) + Z(c);
        }
 
        friend constexpr 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;
        }
    };
}  // namespace fun