+#ifndef MATH_RATIONAL_H_
+#define MATH_RATIONAL_H_
+
+#include <ostream>
+
+
+namespace math {
+
+/// Rational number type.
+/// Stores 2 Integers and has the value num / denom.
+template<class Integer>
+class Rational {
+
+public:
+ explicit Rational(Integer num = 0, Integer denom = 1)
+ : num(num), denom(denom) { }
+ template<class OtherInt>
+ explicit Rational(const Rational<OtherInt> &other)
+ : num(other.Numerator()), denom(other.Denominator()) { }
+
+public:
+ Integer &Numerator() { return num; }
+ const Integer &Numerator() const { return num; }
+ Integer &Denominator() { return denom; }
+ const Integer &Denominator() const { return denom; }
+
+ Integer Int() const { return num / denom; }
+ Integer Inv() const { return denom / num; }
+ float Float() const { return float(num) / denom; }
+ double Double() const { return double(num) / denom; }
+
+ bool IsWhole() const {
+ return num % denom == 0;
+ }
+ bool IsFrac() const {
+ return num % denom != 0;
+ }
+
+ void QuickPack() {
+ if (num == 1 || denom == 1) return;
+ if (num % denom == 0) {
+ num /= denom;
+ denom = 1;
+ } else if (denom % num == 0) {
+ denom /= num;
+ num = 1;
+ }
+ }
+
+ void Pack() {
+ if (num == 1 || denom == 1) return;
+ if (num % denom == 0) {
+ num /= denom;
+ denom = 1;
+ return;
+ }
+ if (denom % num == 0) {
+ denom /= num;
+ num = 1;
+ return;
+ }
+ while (num % 2 == 0 && denom % 2 == 0) {
+ num /= 2;
+ denom /= 2;
+ }
+ while (num % 3 == 0 && denom % 3 == 0) {
+ num /= 3;
+ denom /= 3;
+ }
+ while (num % 5 == 0 && denom % 5 == 0) {
+ num /= 5;
+ denom /= 5;
+ }
+ }
+
+public:
+ template<class OtherInt>
+ Rational &operator =(OtherInt i) {
+ num = i;
+ denom = 1;
+ return *this;
+ }
+ template<class OtherInt>
+ Rational &operator =(Rational<OtherInt> r) {
+ num = r.Numerator();
+ denom = r.Denominator();
+ return *this;
+ }
+ template<class OtherInt>
+ Rational &operator +=(OtherInt i) {
+ num += i * denom;
+ return *this;
+ }
+ template<class OtherInt>
+ Rational &operator +=(Rational<OtherInt> r) {
+ num = num * r.Denominator() + r.Numerator() * denom;
+ denom *= r.Denominator();
+ return *this;
+ }
+ template<class OtherInt>
+ Rational &operator -=(OtherInt i) {
+ num -= i * denom;
+ return *this;
+ }
+ template<class OtherInt>
+ Rational &operator -=(Rational<OtherInt> r) {
+ num = num * r.Denominator() - r.Numerator() * denom;
+ denom *= r.Denominator();
+ return *this;
+ }
+ template<class OtherInt>
+ Rational &operator *=(OtherInt i) {
+ if (denom % i == 0) {
+ denom /= i;
+ } else {
+ num *= i;
+ }
+ return *this;
+ }
+ template<class OtherInt>
+ Rational &operator *=(const Rational<OtherInt> &r) {
+ num *= r.Numerator();
+ denom *= r.Denominator();
+ return *this;
+ }
+ Rational &operator *=(float f) {
+ num *= f;
+ return *this;
+ }
+ Rational &operator *=(double d) {
+ num *= d;
+ return *this;
+ }
+ template<class OtherInt>
+ Rational &operator /=(OtherInt i) {
+ if (num % i == 0) {
+ num /= i;
+ } else {
+ denom *= i;
+ }
+ return *this;
+ }
+ template<class OtherInt>
+ Rational &operator /=(const Rational<OtherInt> &r) {
+ num *= r.Denominator();
+ denom *= r.Numerator();
+ return *this;
+ }
+ Rational &operator /=(float f) {
+ if (f > 1 || f < -1) {
+ denom *= f;
+ } else {
+ num /= f;
+ }
+ return *this;
+ }
+ Rational &operator /=(double d) {
+ if (d > 1 || d < -1) {
+ denom *= d;
+ } else {
+ num /= d;
+ }
+ return *this;
+ }
+
+private:
+ Integer num;
+ Integer denom;
+
+};
+
+template<class Integer>
+Rational<Integer> operator -(const Rational<Integer> &r) {
+ return Rational<Integer>(-r.Numerator(), r.Denominator());
+}
+
+template<class LInt, class RInt>
+bool operator ==(
+ const Rational<LInt> &lhs,
+ const Rational<RInt> &rhs) {
+ return lhs.Numerator() * rhs.Denominator() ==
+ rhs.Numerator() * lhs.Denominator();
+}
+template<class LInt, class RInt>
+bool operator !=(
+ const Rational<LInt> &lhs,
+ const Rational<RInt> &rhs) {
+ return !(lhs == rhs);
+}
+template<class LInt, class RInt>
+bool operator ==(
+ const Rational<LInt> &lhs,
+ RInt rhs) {
+ return lhs.IsWhole() && lhs.Int() == rhs;
+}
+template<class LInt, class RInt>
+bool operator !=(
+ const Rational<LInt> &lhs,
+ RInt rhs) {
+ return !(lhs == rhs);
+}
+template<class LInt, class RInt>
+bool operator ==(
+ LInt lhs,
+ const Rational<RInt> &rhs) {
+ return rhs == lhs;
+}
+template<class LInt, class RInt>
+bool operator !=(
+ LInt lhs,
+ const Rational<RInt> &rhs) {
+ return rhs != lhs;
+}
+
+template<class LInt, class RInt>
+bool operator <(
+ const Rational<LInt> &lhs,
+ const Rational<RInt> &rhs) {
+ return lhs.Numerator() * rhs.Denominator() <
+ rhs.Numerator() * lhs.Denominator();
+}
+template<class LInt, class RInt>
+bool operator <(
+ const Rational<LInt> &lhs,
+ RInt rhs) {
+ return lhs.Numerator() < rhs * lhs.Denominator();
+}
+template<class LInt, class RInt>
+bool operator <(
+ LInt lhs,
+ const Rational<RInt> &rhs) {
+ return lhs * rhs.Denominator() < rhs.Numerator();
+}
+
+template<class LInt, class RInt>
+bool operator <=(
+ const Rational<LInt> &lhs,
+ const Rational<RInt> &rhs) {
+ return lhs.Numerator() * rhs.Denominator() <=
+ rhs.Numerator() * lhs.Denominator();
+}
+template<class LInt, class RInt>
+bool operator <=(
+ const Rational<LInt> &lhs,
+ RInt rhs) {
+ return lhs.Numerator() <= rhs * lhs.Denominator();
+}
+template<class LInt, class RInt>
+bool operator <=(
+ LInt lhs,
+ const Rational<RInt> &rhs) {
+ return lhs * rhs.Denominator() <= rhs.Numerator();
+}
+
+template<class LInt, class RInt>
+bool operator >(
+ const Rational<LInt> &lhs,
+ const Rational<RInt> &rhs) {
+ return lhs.Numerator() * rhs.Denominator() >
+ rhs.Numerator() * lhs.Denominator();
+}
+template<class LInt, class RInt>
+bool operator >(
+ const Rational<LInt> &lhs,
+ RInt rhs) {
+ return lhs.Numerator() > rhs * lhs.Denominator();
+}
+template<class LInt, class RInt>
+bool operator >(
+ LInt lhs,
+ const Rational<RInt> &rhs) {
+ return lhs * rhs.Denominator() > rhs.Numerator();
+}
+
+template<class LInt, class RInt>
+bool operator >=(
+ const Rational<LInt> &lhs,
+ const Rational<RInt> &rhs) {
+ return lhs.Numerator() * rhs.Denominator() >=
+ rhs.Numerator() * lhs.Denominator();
+}
+template<class LInt, class RInt>
+bool operator >=(
+ const Rational<LInt> &lhs,
+ RInt rhs) {
+ return lhs.Numerator() >= rhs * lhs.Denominator();
+}
+template<class LInt, class RInt>
+bool operator >=(
+ LInt lhs,
+ const Rational<RInt> &rhs) {
+ return lhs * rhs.Denominator() >= rhs.Numerator();
+}
+
+template<class LInt, class RInt>
+Rational<LInt> operator +(
+ const Rational<LInt> &lhs,
+ const Rational<RInt> &rhs) {
+ return Rational<LInt>(lhs) += rhs;
+}
+template<class LInt, class RInt>
+Rational<LInt> operator +(
+ const Rational<LInt> &lhs,
+ RInt rhs) {
+ return Rational<LInt>(lhs) += rhs;
+}
+template<class LInt, class RInt>
+LInt operator +(
+ LInt lhs,
+ const Rational<RInt> &rhs) {
+ return lhs + rhs.Int();
+}
+
+template<class LInt, class RInt>
+Rational<LInt> operator -(
+ const Rational<LInt> &lhs,
+ const Rational<RInt> &rhs) {
+ return Rational<LInt>(lhs) -= rhs;
+}
+template<class LInt, class RInt>
+Rational<LInt> operator -(
+ const Rational<LInt> &lhs,
+ RInt rhs) {
+ return Rational<LInt>(lhs) -= rhs;
+}
+template<class LInt, class RInt>
+LInt operator -(
+ LInt lhs,
+ const Rational<RInt> &rhs) {
+ return lhs - rhs.Int();
+}
+
+template<class LInt, class RInt>
+Rational<LInt> operator *(
+ const Rational<LInt> &lhs,
+ const Rational<RInt> &rhs) {
+ return Rational<LInt>(lhs) *= rhs;
+}
+template<class LInt, class RInt>
+Rational<LInt> operator *(
+ const Rational<LInt> &lhs,
+ RInt rhs) {
+ return Rational<LInt>(lhs) *= rhs;
+}
+template<class LInt, class RInt>
+LInt operator *(
+ LInt lhs,
+ const Rational<RInt> &rhs) {
+ return lhs * rhs.Numerator() / rhs.Denominator();
+}
+
+template<class LInt, class RInt>
+Rational<LInt> operator /(
+ const Rational<LInt> &lhs,
+ const Rational<RInt> &rhs) {
+ return Rational<LInt>(lhs) /= rhs;
+}
+template<class LInt, class RInt>
+Rational<LInt> operator /(
+ const Rational<LInt> &lhs,
+ RInt rhs) {
+ return Rational<LInt>(lhs) /= rhs;
+}
+template<class LInt, class RInt>
+LInt operator /(
+ LInt lhs,
+ const Rational<RInt> &rhs) {
+ return lhs * rhs.Denominator() / rhs.Numerator();
+}
+
+
+template<class Integer>
+inline std::ostream &operator <<(std::ostream &out, const Rational<Integer> &r) {
+ return out << r.Double();
+}
+
+}
+
+#endif