#include <stdlib.h>
#include <sstream>
using namespace std;
#include <math.h>
#include "my_limits.h"
#include "Rational.h"
template<class T>
Rational<T>::Rational(T n, T d) {
if (d == 0) {
cerr << "Division by Zero" << endl;
exit(1);
}
if (d < 0) { n = -n; d = -d; }
if (n == 0) {
num = 0; den = 1;
} else {
T g = gcd(n, d);
num = n/g; den = d/g;
}
}
template<class T>
const Rational<T>& Rational<T>::operator+=(const Rational<T>& rhs) {
T g1 = gcd(den, rhs.den);
if (g1 == 1) {
num = num*rhs.den + den*rhs.num;
den = den*rhs.den;
} else {
T t = num * (rhs.den/g1) + (den/g1)*rhs.num;
T g2 = gcd(t, g1);
num = t/g2;
den = (den/g1) * (rhs.den/g2);
}
return *this;
}
template<class T>
const Rational<T>& Rational<T>::operator+=(T rhs) {
num = num + den*rhs;
return *this;
}
template<class T>
const Rational<T>& Rational<T>::operator-=(const Rational<T>& rhs) {
T g1 = gcd(den, rhs.den);
if (g1 == 1) {
num = num*rhs.den - den*rhs.num;
den = den*rhs.den;
} else {
T t = num * (rhs.den/g1) - (den/g1)*rhs.num;
T g2 = gcd(t, g1);
num = t/g2;
den = (den/g1) * (rhs.den/g2);
}
return *this;
}
template<class T>
const Rational<T>& Rational<T>::operator-=(T rhs) {
num = num - den*rhs;
return *this;
}
template<class T>
const Rational<T>& Rational<T>::operator*=(const Rational<T>& rhs) {
T g1 = gcd(num, rhs.den);
T g2 = gcd(den, rhs.num);
num = (num/g1) * (rhs.num/g2);
den = (den/g2) * (rhs.den/g1);
return *this;
}
template<class T>
const Rational<T>& Rational<T>::operator*=(T rhs) {
T g = gcd(den, rhs);
num *= rhs/g;
den /= g;
return *this;
}
template<class T>
const Rational<T>& Rational<T>::operator/=(const Rational<T>& rhs) {
if (rhs == Rational<T>(0)) {
cerr << "Division by Zero" << endl;
exit(1);
}
T g1 = gcd(num, rhs.num);
T g2 = gcd(den, rhs.den);
num = (num/g1) * (rhs.den/g2);
den = (den/g2) * (rhs.num/g1);
if (den < 0) { num = -num; den = -den; }
return *this;
}
template<class T>
const Rational<T>& Rational<T>::operator/=(T rhs) {
if (rhs == 0) {
cerr << "Division by Zero" << endl;
exit(1);
}
T g = gcd(num, rhs);
num /= g;
den *= rhs/g;
if (den < 0) { num = -num; den = -den; }
return *this;
}
template<class T>
const Rational<T>& Rational<T>::operator++() {
return (*this += 1);
}
template<class T>
const Rational<T> Rational<T>::operator++(int) {
Rational<T> oldVal = *this;
++(*this);
return oldVal;
}
template<class T>
const Rational<T>& Rational<T>::operator--() {
return (*this -= 1);
}
template<class T>
const Rational<T> Rational<T>::operator--(int) {
Rational<T> oldVal = *this;
--(*this);
return oldVal;
}
template<class T>
T Rational<T>::gcd(T u, T v) {
T a = u < 0 ? -u : u;
T b = v < 0 ? -v : v;
T tmp;
if (b > a) {
tmp = a; a = b; b = tmp;
}
for(;;) {
if (b == 0)
return a;
else if (b == 1)
return b;
else {
tmp = b; b = a % b; a = tmp;
}
}
}
template<class T>
const Rational<T> operator+(const Rational<T>& lhs, const Rational<T>& rhs) {
return Rational<T>(lhs) += rhs;
}
template<class T>
const Rational<T> operator-(const Rational<T>& lhs, const Rational<T>& rhs) {
return Rational<T>(lhs) -= rhs;
}
template<class T>
const Rational<T> operator*(const Rational<T>& lhs, const Rational<T>& rhs) {
return Rational<T>(lhs) *= rhs;
}
template<class T>
const Rational<T> operator/(const Rational<T>& lhs, const Rational<T>& rhs) {
return Rational<T>(lhs) /= rhs;
}
template<class T>
Rational<T> rabs(const Rational<T>& r) {
if (r.numerator() < 0) return -r; else return r;
}
template<class T>
bool operator==(const Rational<T>& lhs, const Rational<T>& rhs) {
return (lhs.numerator() == rhs.numerator() &&
lhs.denominator() == rhs.denominator());
}
template<class T>
bool operator!=(const Rational<T>& lhs, const Rational<T>& rhs) {
return (lhs.numerator() != rhs.numerator() ||
lhs.denominator() != rhs.denominator());
}
template<class T>
bool operator<(const Rational<T>& lhs, const Rational<T>& rhs) {
return (toDouble(lhs) < toDouble(rhs));
}
template<class T>
bool operator>(const Rational<T>& lhs, const Rational<T>& rhs) {
return (toDouble(lhs) > toDouble(rhs));
}
template<class T>
bool operator<=(const Rational<T>& lhs, const Rational<T>& rhs) {
return ((lhs < rhs) || (lhs == rhs));
}
template<class T>
bool operator>=(const Rational<T>& lhs, const Rational<T>& rhs) {
return ((lhs > rhs) || (lhs == rhs));
}
template<class T>
ostream& operator<< (ostream& ostr, const Rational<T>& r) {
if (r.denominator() == 1)
ostr << r.numerator();
else {
ostringstream buf;
buf.flags(ostr.flags());
buf.fill(ostr.fill());
buf << r.numerator() << "/" << r.denominator();
ostr << buf.str();
}
return ostr;
}
template<class T>
istream& operator>> (istream& istr, Rational<T>& r) {
T n = 0, d = 1;
istr >> n;
if ( istr.peek() == '/' ) {
istr.ignore(1);
istr >> d;
}
if ( istr ) r = Rational<T>(n,d);
return istr;
}
template<class T>
Rational<T> toRational(double x, double limit, int iterations) {
double intpart;
double fractpart = modf(x, &intpart);
double d = 1.0 / fractpart;
T left = T(intpart);
if ( d > limit || iterations == 0 ) {
return Rational<T>(left);
} else {
return Rational<T>(left) +
toRational<T>(d, limit * 0.1, --iterations).invert();
}
}
template<class T>
Rational<T> toRational(double x, int iterations) {
if ( x == 0.0 ||
x < numeric_limits<T>::min() ||
x > numeric_limits<T>::max() ) {
return Rational<T>(0,1);
} else {
int sign = x < 0.0 ? -1 : 1;
return Rational<T>(sign) * toRational<T>(sign * x, 1.0e12, iterations);
}
}