rational.hpp

/*********************************************************************
 *
 * Linear Arrangement Library - A library that implements a collection
 * algorithms for linear arrangments of graphs.
 *
 * Copyright (C) 2019 - 2023
 *
 * This file is part of Linear Arrangement Library. The full code is available
 * at:
 *      https://github.com/LAL-project/linear-arrangement-library.git
 *
 * Linear Arrangement Library is free software: you can redistribute it
 * and/or modify it under the terms of the GNU Affero General Public License
 * as published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * Linear Arrangement Library is distributed in the hope that it will be
 * useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with Linear Arrangement Library.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Contact:
 *
 *     Lluís Alemany Puig (lalemany@cs.upc.edu)
 *         LARCA (Laboratory for Relational Algorithmics, Complexity and Learning)
 *         CQL (Complexity and Quantitative Linguistics Lab)
 *         Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona.   CATALONIA, SPAIN
 *         Webpage: https://cqllab.upc.edu/people/lalemany/
 *
 *     Ramon Ferrer i Cancho (rferrericancho@cs.upc.edu)
 *         LARCA (Laboratory for Relational Algorithmics, Complexity and Learning)
 *         CQL (Complexity and Quantitative Linguistics Lab)
 *         Office S124, Omega building
 *         Jordi Girona St 1-3, Campus Nord UPC, 08034 Barcelona.   CATALONIA, SPAIN
 *         Webpage: https://cqllab.upc.edu/people/rferrericancho/
 *
 ********************************************************************/
 
#pragma once
 
// C includes
#include <gmp.h>
 
// C++ includes
#include <cstdint>
#include <string>
 
// lal includes
#include <lal/numeric/integer.hpp>
 
namespace lal {
namespace numeric {
 
class rational {
public:
    /* CONSTRUCTORS */
 
    rational() noexcept { mpq_init(m_val); }
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    rational(T n, uint64_t d = 1) noexcept
    { mpq_init(m_val); set_number(n, d); }
    rational(const integer& n, const integer& d = 1) noexcept
    { mpq_init(m_val); set_integer(n, d); }
    rational(const std::string& s) noexcept
    { mpq_init(m_val); set_str(s); }
    rational(const rational& r) noexcept
    { mpq_init(m_val); mpq_set(m_val, r.m_val); }
#ifndef SWIG
    rational(integer&& i) noexcept {
        // move i's contents into numerator
        m_val[0]._mp_num = *i.m_val;
        // set the denominator to 1
        mpz_init_set_ui(&m_val[0]._mp_den, 1);
        // we must canonicalize
        mpq_canonicalize(m_val);
        
        // invalidate i's contents
        i.m_val->_mp_alloc = 0;
        i.m_val->_mp_size = 0;
        i.m_val->_mp_d = nullptr;
        i.m_initialized = false;
    }
    rational(integer&& n, integer&& d) noexcept {
        // move n's contents into numerator
        m_val[0]._mp_num = *n.m_val;
        // move d's contents into denominator
        m_val[0]._mp_den = *d.m_val;
        // we must canonicalize
        mpq_canonicalize(m_val);
 
        // invalidate n's contents
        n.m_val->_mp_alloc = 0;
        n.m_val->_mp_size = 0;
        n.m_val->_mp_d = nullptr;
        n.m_initialized = false;
 
        // invalidate d's contents
        d.m_val->_mp_alloc = 0;
        d.m_val->_mp_size = 0;
        d.m_val->_mp_d = nullptr;
        d.m_initialized = false;
    }
    rational(rational&& r) noexcept {
        *m_val = *r.m_val;
 
        // invalidate r's contents
        r.m_val->_mp_num._mp_alloc = 0;
        r.m_val->_mp_num._mp_size = 0;
        r.m_val->_mp_num._mp_d = nullptr;
        r.m_val->_mp_den._mp_alloc = 0;
        r.m_val->_mp_den._mp_size = 0;
        r.m_val->_mp_den._mp_d = nullptr;
        r.m_initialized = false;
    }
#endif
    ~rational() noexcept { mpq_clear(m_val); }
 
    /* SETTERS */
 
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    void set_number(T n, uint64_t d = 1) noexcept {
        if (not is_initialized()) { mpq_init(m_val); }
        if constexpr (std::is_signed_v<T>) { mpq_set_si(m_val, n, d); }
        else { mpq_set_ui(m_val, n, d); }
        mpq_canonicalize(m_val);
        m_initialized = true;
    }
    void set_str(const std::string& s) noexcept {
        if (not is_initialized()) { mpq_init(m_val); }
        mpq_set_str(m_val, s.c_str(), 10);
        mpq_canonicalize(m_val);
        m_initialized = true;
    }
    void set_integer(const integer& n, const integer& d) noexcept {
        if (not is_initialized()) { mpq_init(m_val); }
        mpq_set_num(m_val, n.get_raw_value());
        mpq_set_den(m_val, d.get_raw_value());
        mpq_canonicalize(m_val);
        m_initialized = true;
    }
    void set_rational(const rational& r) noexcept {
        if (not is_initialized()) { mpq_init(m_val); }
        mpq_set(m_val, r.m_val);
    }
 
    void invert() noexcept { mpq_inv(m_val, m_val); }
 
    /* OPERATORS */
 
    // -- ASSIGNMENT
 
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    rational& operator= (T i) noexcept
    { set_number(i); return *this; }
    rational& operator= (const std::string& s) noexcept
    { set_str(s); return *this; }
    rational& operator= (const integer& i) noexcept
    { set_integer(i, 1); return *this; }
    rational& operator= (const rational& r) noexcept
    { set_rational(r); return *this; }
#ifndef SWIG
    rational& operator= (integer&& i) noexcept {
        // clear this's contents
        mpq_clear(m_val);
        m_initialized = true;
 
        // move i's contents into numerator
        m_val[0]._mp_num = *i.m_val;
        // set the denominator to 1
        mpz_init_set_ui(&m_val[0]._mp_den, 1);
        // we must canonicalize
        mpq_canonicalize(m_val);
 
        // invalidate i's contents
        i.m_val->_mp_alloc = 0;
        i.m_val->_mp_size = 0;
        i.m_val->_mp_d = nullptr;
        i.m_initialized = false;
 
        return *this;
    }
    rational& operator= (rational&& r) noexcept {
        // clear this's contents
        mpq_clear(m_val);
        m_initialized = true;
 
        // move r's contents into this's
        *m_val = *r.m_val;
 
        // invalidate r's contents
        r.m_val->_mp_num._mp_alloc = 0;
        r.m_val->_mp_num._mp_size = 0;
        r.m_val->_mp_num._mp_d = nullptr;
        r.m_val->_mp_den._mp_alloc = 0;
        r.m_val->_mp_den._mp_size = 0;
        r.m_val->_mp_den._mp_d = nullptr;
        r.m_initialized = false;
 
        return *this;
    }
#endif
 
    // -- EQUALITY
 
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    bool operator== (T i) const noexcept {
        return
        (std::is_signed_v<T> ? mpq_cmp_si(m_val, i, 1) : mpq_cmp_ui(m_val, i, 1)) == 0;
    }
#ifndef SWIG
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    friend bool operator== (T i, const rational& r) noexcept
    { return r == i; }
#endif
    bool operator== (const integer& i) const noexcept
    { rational r(i); return mpq_equal(m_val, r.m_val); }
#ifndef SWIG
    friend bool operator== (const integer& i, const rational& r) noexcept
    { return r == i; }
#endif
    bool operator== (const rational& r) const noexcept {
        // this function returns non-zero if parameters are equal!
        return mpq_equal(m_val, r.m_val);
    }
 
    // -- NON-EQUALITY
 
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    bool operator!= (T i) const noexcept
    { return not (*this == i); }
#ifndef SWIG
    friend bool operator!= (int64_t i, const rational& r) noexcept
    { return r != i; }
#endif
    bool operator!= (const integer& i) const noexcept
    { return not (*this == i); }
#ifndef SWIG
    friend bool operator!= (const integer& i, const rational& r) noexcept
    { return r != i; }
#endif
    bool operator!= (const rational& r) const noexcept
    { return not (*this == r); }
 
    // -- LESS THAN
 
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    bool operator< (T i) const noexcept {
        return
        (std::is_signed_v<T> ? mpq_cmp_si(m_val, i, 1) : mpq_cmp_ui(m_val, i, 1)) < 0;
    }
#ifndef SWIG
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    friend bool operator< (T i, const rational& r) noexcept
    { return r > i; }
#endif
    bool operator< (const integer& i) const noexcept
    { rational r(i); return mpq_cmp(m_val, r.m_val) < 0; }
#ifndef SWIG
    friend bool operator< (const integer& i, const rational& r) noexcept
    { return r > i; }
#endif
    bool operator< (const rational& r) const noexcept
    { return mpq_cmp(m_val, r.m_val) < 0; }
 
    // -- LESS THAN OR EQUAL TO
 
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    bool operator<= (T i) const noexcept {
        return
        (std::is_signed_v<T> ? mpq_cmp_si(m_val, i, 1) : mpq_cmp_ui(m_val, i, 1)) <= 0;
    }
#ifndef SWIG
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    friend bool operator<= (T i, const rational& r) noexcept
    { return r >= i; }
#endif
    bool operator<= (const integer& i) const noexcept
    { rational r(i); return mpq_cmp(m_val, r.m_val) <= 0; }
#ifndef SWIG
    friend bool operator<= (const integer& i, const rational& r) noexcept
    { return r >= i; }
#endif
    bool operator<= (const rational& r) const noexcept
    { return mpq_cmp(m_val, r.m_val) <= 0; }
 
    // -- GREATER THAN
 
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    bool operator> (T i) const noexcept {
        return
        (std::is_signed_v<T> ? mpq_cmp_si(m_val, i, 1) : mpq_cmp_ui(m_val, i, 1)) > 0;
    }
#ifndef SWIG
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    friend bool operator> (T i, const rational& r) noexcept
    { return r < i; }
#endif
    bool operator> (const integer& i) const noexcept
    { rational r(i); return mpq_cmp(m_val, r.m_val) > 0; }
#ifndef SWIG
    friend bool operator> (const integer& i, const rational& r) noexcept
    { return r < i; }
#endif
    bool operator> (const rational& r) const noexcept
    { return mpq_cmp(m_val, r.m_val) > 0; }
 
    // -- GREATER THAN OR EQUAL TO
 
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    bool operator>= (T i) const noexcept {
        return
        (std::is_signed_v<T> ? mpq_cmp_si(m_val, i, 1) : mpq_cmp_ui(m_val, i, 1)) >= 0;
    }
#ifndef SWIG
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    friend bool operator>= (T i, const rational& r) noexcept
    { return r <= i; }
#endif
    bool operator>= (const integer& i) const noexcept
    { rational r(i); return mpq_cmp(m_val, r.m_val) >= 0; }
#ifndef SWIG
    friend bool operator>= (const integer& i, const rational& r) noexcept
    { return r <= i; }
#endif
    bool operator>= (const rational& r) const noexcept
    { return mpq_cmp(m_val, r.m_val) >= 0; }
 
    // -- ADDITION
 
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    rational operator+ (T i) const noexcept
    { rational r(*this); r += i; return r; }
#ifndef SWIG
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    friend rational operator+ (T i, const rational& r) noexcept
    { return r + i; }
#endif
    rational operator+ (const integer& i) const noexcept
    { rational r(*this); r += i; return r; }
#ifndef SWIG
    friend rational operator+ (const integer& i, const rational& r) noexcept
    { return r + i; }
#endif
    rational operator+ (const rational& r) const noexcept
    { rational k(*this); k += r; return k; }
 
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    rational& operator+= (T i) noexcept
    { rational r(i); mpq_add(m_val, m_val, r.m_val); return *this; }
    rational& operator+= (const integer& i) noexcept
    { rational r(i); mpq_add(m_val, m_val, r.m_val); return *this; }
    rational& operator+= (const rational& r) noexcept
    { mpq_add(m_val, m_val, r.m_val); return *this; }
 
    // -- SUBSTRACTION
 
    rational operator- () const noexcept
    { rational r(*this); mpq_neg(r.m_val, r.m_val); return r; }
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    rational operator- (T i) const noexcept
    { rational r(*this); r -= i; return r; }
#ifndef SWIG
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    friend rational operator- (T i, const rational& r) noexcept
    { return -r + i; }
#endif
    rational operator- (const integer& i) const noexcept
    { rational r(*this); r -= i; return r; }
#ifndef SWIG
    friend rational operator- (const integer& i, const rational& r) noexcept
    { return -r + i; }
#endif
    rational operator- (const rational& r) const noexcept
    { rational k(*this); k -= r; return k; }
 
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    rational& operator-= (T i) noexcept
    { rational r(i); mpq_sub(m_val, m_val, r.m_val); return *this; }
    rational& operator-= (const integer& i) noexcept
    { rational r(i); mpq_sub(m_val, m_val, r.m_val); return *this; }
    rational& operator-= (const rational& r) noexcept
    { mpq_sub(m_val, m_val, r.m_val); return *this; }
 
    // -- MULTIPLICATION
 
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    rational operator* (T i) const noexcept
    { rational r(*this); r *= i; return r; }
#ifndef SWIG
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    friend rational operator* (T i, const rational& r) noexcept
    { return r*i; }
#endif
    rational operator* (const integer& i) const noexcept
    { rational r(*this); r *= i; return r; }
#ifndef SWIG
    friend rational operator* (const integer& i, const rational& r) noexcept
    { return r*i; }
#endif
    rational operator* (const rational& r) const noexcept
    { rational k(*this); k *= r; return k; }
 
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    rational& operator*= (T i) noexcept
    { rational r(i); mpq_mul(m_val, m_val, r.m_val); return *this; }
    rational& operator*= (const integer& i) noexcept
    { rational r(i); mpq_mul(m_val, m_val, r.m_val); return *this; }
    rational& operator*= (const rational& r) noexcept
    { mpq_mul(m_val, m_val, r.m_val); return *this; }
 
    // -- DIVISION
 
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    rational operator/ (T i) const noexcept
    { rational r(*this); r /= i; return r; }
#ifndef SWIG
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    friend rational operator/ (T i, const rational& r) noexcept
    { rational inv(r); inv.invert(); return inv*i; }
#endif
 
    rational operator/ (const integer& i) const noexcept
    { rational r(*this); r /= i; return r; }
    rational operator/ (const rational& r) const noexcept
    { rational k(*this); k /= r; return k; }
 
    template <typename T,std::enable_if_t<std::is_integral_v<T>, bool> = true>
    rational& operator/= (T i) noexcept {
        integer I(i); *this /= I; return *this;
    }
    rational& operator/= (const integer& i) noexcept;
    rational& operator/= (const rational& r) noexcept;
 
    // -- EXPONENTIATION
 
    rational power(uint64_t i) const noexcept;
    rational power(const integer& i) const noexcept;
 
    rational& powt(uint64_t i) noexcept;
    rational& powt(const integer& i) noexcept;
 
    /* GETTERS */
 
    bool is_initialized() const noexcept { return m_initialized; }
    int64_t get_sign() const noexcept { return mpq_sgn(m_val); }
 
    std::size_t bytes() const noexcept;
 
    /* CONVERTERS */
 
    integer to_integer() const noexcept {
        integer i;
        as_integer(i);
        return i;
    }
    void as_integer(integer& i) const noexcept;
 
    double to_double() const noexcept { return mpq_get_d(m_val); }
    void as_double(double& d) const noexcept { d = mpq_get_d(m_val); }
 
    std::string to_string() const noexcept {
        std::string k;
        as_string(k);
        return k;
    }
    void as_string(std::string& s) const noexcept {
        char *buf = nullptr;
        buf = mpq_get_str(buf, 10, m_val);
        s = std::string(buf);
        free(buf);
    }
 
    integer get_numerator() const noexcept {
        mpz_t numerator;
        mpz_init(numerator);
        mpq_get_num(numerator, m_val);
        return integer(std::move(numerator));
    }
 
    integer get_denominator() const noexcept {
        mpz_t denominator;
        mpz_init(denominator);
        mpq_get_den(denominator, m_val);
        return integer(std::move(denominator));
    }
 
    /* OTHERS */
 
    void swap(rational& r) noexcept { mpq_swap(m_val, r.m_val); }
 
#ifndef SWIG
    friend void swap(rational& r1, rational& r2) noexcept { r1.swap(r2); }
#endif
 
private:
    mpq_t m_val;
    bool m_initialized = true;
};
 
} // -- namespace numeric
} // -- namespace lal