rational.hpp

Go to the documentation of this file.

#ifndef RATIONAL_HPP_
#define RATIONAL_HPP_

#include <istream>
#include <limits>
#include <ostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <type_traits>

#include "gcd.hpp"
#include "ioflags.hpp"
#include "power10.hpp"

class zero_denominator : public std::logic_error
{
public:
  zero_denominator(std::string const& what) : logic_error{what} {}
};

template<class T>
class rational
{
public:
  typedef T value_type;

  rational(value_type num = 0): numerator_{num}, denominator_{1} {}
  rational(value_type num, value_type den);
  rational(double r);
  template<class U>
  rational(rational<U> const& that);

  value_type numerator()              const { return numerator_; }
  value_type denominator()            const { return denominator_; }
  template<class U, class EnableIfFloat = typename std::enable_if<std::is_floating_point<U>::value>::type>
  explicit operator U() const { return static_cast<U>(numerator()) / denominator(); }

  rational& operator=(value_type); // optimization to avoid an unneeded call to reduce()

  template<class U>
  rational& operator=(rational<U> const& rhs);

  rational& operator+=(rational const& rhs);
  rational& operator+=(value_type const& rhs);

  rational& operator-=(rational const& rhs);
  rational& operator-=(value_type const& rhs);

  rational& operator*=(rational const& rhs);
  rational& operator*=(value_type const& rhs);

  rational& operator/=(rational const& rhs);
  rational& operator/=(value_type const& rhs);

  rational& operator++();
  rational& operator--();
  rational operator++(int);
  rational operator--(int);

private:
  void reduce();
  void normalize();
  template<class U>
  value_type scale(U value);

  static constexpr value_type double_divisor = power10<value_type>(std::numeric_limits<value_type>::digits10 - 1);

  value_type numerator_;
  value_type denominator_;
};

template<class T>
rational<T>::rational(value_type num, value_type den)
: numerator_{num},
  denominator_{den == value_type{} ? throw zero_denominator{"zero denominator"} : den}
{
  normalize();
}

template<class T>
rational<T>::rational(double r)
: numerator_{static_cast<T>(r / double_divisor + 0.5)}, denominator_{double_divisor}
{}

template<class T>
template<class U>
rational<T>::rational(rational<U> const& that)
: numerator_{scale<U>(that.numerator())}, denominator_{scale<U>(that.denominator())}
{
  reduce();
}

template<class T>
template<class U>
T rational<T>::scale(U value)
{
  if (std::numeric_limits<T>::digits >= std::numeric_limits<U>::digits)
    return T{value};
  else
    return T{value >> (std::numeric_limits<U>::digits - std::numeric_limits<T>::digits)};
}

template<class T>
void rational<T>::normalize()
{
  if (denominator_ < value_type{})
  {
    denominator_ = -denominator_;
    numerator_ = -numerator_;
  }
  reduce();
}

template<class T>
void rational<T>::reduce()
{
  value_type div{gcd(numerator(), denominator())};
  if (div == value_type{})
    throw zero_denominator{"zero denominator"};
  numerator_ /= div;
  denominator_ /= div;
}

template<class T>
rational<T>& rational<T>::operator=(T num)
{
  numerator_ = num;
  denominator_ = value_type{1};
  return *this;
}

template<class T>
template<class U>
rational<T>& rational<T>::operator=(rational<U> const& rhs)
{
  numerator_ = scale<U>(rhs.numerator());
  denominator_ = scale<U>(rhs.denominator());
  reduce();
  return *this;
}

template<class T>
rational<T>& rational<T>::operator+=(rational const& rhs)
{
  numerator_ = numerator() * rhs.denominator() + rhs.numerator() * denominator();
  denominator_ *= rhs.denominator();
  reduce();
  return *this;
}

template<class T>
rational<T>& rational<T>::operator+=(value_type const& rhs)
{
  numerator_ = numerator() + rhs * denominator();
  reduce();
  return *this;
}

template<class T>
rational<T>& rational<T>::operator-=(rational const& rhs)
{
  numerator_ = numerator() * rhs.denominator() - rhs.numerator() * denominator();
  denominator_ *= rhs.denominator();
  reduce();
  return *this;
}

template<class T>
rational<T>& rational<T>::operator-=(value_type const& rhs)
{
  numerator_ = numerator() - rhs * denominator();
  reduce();
  return *this;
}

template<class T>
rational<T>& rational<T>::operator*=(rational const& rhs)
{
  numerator_ *= rhs.numerator();
  denominator_ *= rhs.denominator();
  reduce();
  return *this;
}

template<class T>
rational<T>& rational<T>::operator*=(value_type const& rhs)
{
  numerator_ *= rhs;
  reduce();
  return *this;
}

template<class T>
rational<T>& rational<T>::operator/=(rational const& rhs)
{
  if (rhs.numerator() == value_type{})
    throw zero_denominator{"divide by zero"};
  numerator_ *= rhs.denominator();
  denominator_ *= rhs.numerator();
  normalize();
  return *this;
}

template<class T>
rational<T>& rational<T>::operator/=(value_type const& rhs)
{
  if (rhs == value_type{})
    throw zero_denominator{"divide by zero"};
  denominator_ *= rhs;
  normalize();
  return *this;
}

template<class T>
rational<T>& rational<T>::operator++()
{
  numerator_ += denominator();
  return *this;
}

template<class T>
rational<T> rational<T>::operator++(int)
{
  rational result(*this);
  ++*this;
  return result;
}

template<class T>
rational<T>& rational<T>::operator--()
{
  numerator_ -= denominator();
  return *this;
}

template<class T>
rational<T> rational<T>::operator--(int)
{
  rational result(*this);
  --*this;
  return result;
}

template<class T>
rational<T> operator-(rational<T> const& r)
{
  return rational<T>{-r.numerator(), r.denominator()};
}

template<class T>
rational<T> absval(rational<T> const& r)
{
  using std::abs;
  return rational<T>{abs(r.numerator()), r.denominator()};
}

template<class T>
rational<T> operator+(rational<T> lhs, rational<T> const& rhs)
{
  lhs += rhs;
  return lhs;
}

template<class T>
rational<T> operator+(rational<T> lhs, T const& rhs)
{
  lhs += rhs;
  return lhs;
}

template<class T>
rational<T> operator+(T const& lhs, rational<T> rhs)
{
  rhs += lhs;
  return rhs;
}

template<class T>
rational<T> operator-(rational<T> lhs, rational<T> const& rhs)
{
  lhs -= rhs;
  return lhs;
}

template<class T>
rational<T> operator-(rational<T> lhs, T const& rhs)
{
  lhs -= rhs;
  return lhs;
}

template<class T>
rational<T> operator-(T const& lhs, rational<T> rhs)
{
  // Gotta be a little tricky.
  rhs += -lhs;
  return -rhs;
}

template<class T>
rational<T> operator*(rational<T> lhs, rational<T> const& rhs)
{
  lhs *= rhs;
  return lhs;
}

template<class T>
rational<T> operator*(rational<T> lhs, T const& rhs)
{
  lhs *= rhs;
  return lhs;
}

template<class T>
    rational<T> operator*(T const& lhs, rational<T> rhs)
{
  rhs *= lhs;
  return rhs;
}

template<class T>
rational<T> operator/(rational<T> lhs, rational<T> const& rhs)
{
  lhs /= rhs;
  return lhs;
}

template<class T>
rational<T> operator/(rational<T> lhs, T const& rhs)
{
  lhs /= rhs;
  return lhs;
}

template<class T>
rational<T> operator/(T const& lhs, rational<T> rhs)
{
  return rational<T>{lhs * rhs.denominator(), rhs.numerator()};
}


template<class T, class U>
bool operator==(rational<T> const& a, rational<U> const& b)
{
  return a.numerator() == b.numerator() and
         a.denominator() == b.denominator();
}

template<class T>
bool operator==(rational<T> const& lhs, T rhs)
{
  return lhs.denominator() == 1 and
         lhs.numerator()   == rhs;
}

template<class T>
bool operator==(T lhs, rational<T> const& rhs)
{
  return rhs.denominator() == 1 and
         rhs.numerator()   == lhs;
}

template<class T>
bool operator<(rational<T> const& a, rational<T> const& b)
{
  return a.numerator() * b.denominator() < b.numerator() * a.denominator();
}

template<class T>
bool operator<(rational<T> const& a, T const& b)
{
  return a.numerator() < b * a.denominator();
}

template<class T>
bool operator<(T const& a, rational<T> const& b)
{
  return a * b.denominator() < b.numerator();
}

template<class T, class U>
inline bool operator!=(rational<T> const& a, rational<U> const& b)
{
  return not (a == b);
}

template<class T>
inline bool operator!=(rational<T> const& a, T b)
{
  return not (a == b);
}

template<class T>
inline bool operator!=(T a, rational<T> const& b)
{
  return not (a == b);
}

template<class T>
inline bool operator<=(rational<T> const& a, rational<T> const& b)
{
  return not (b < a);
}

template<class T>
inline bool operator<=(rational<T> const& a, T const& b)
{
  return not (b < a);
}

template<class T>
inline bool operator<=(T const& a, rational<T> const& b)
{
  return not (b < a);
}

template<class T>
inline bool operator>(rational<T> const& a, rational<T> const& b)
{
  return b < a;
}

template<class T>
inline bool operator>(rational<T> const& a, T const& b)
{
  return b < a;
}

template<class T>
inline bool operator>(T const& a, rational<T> const& b)
{
  return b < a;
}

template<class T>
inline bool operator>=(rational<T> const& a, rational<T> const& b)
{
  return not (b > a);
}

template<class T>
inline bool operator>=(rational<T> const& a, T const& b)
{
  return not (b > a);
}

template<class T>
inline bool operator>=(T const& a, rational<T> const& b)
{
  return not (b > a);
}

template<class T, class Char, class Traits>
std::basic_istream<Char, Traits>& operator>>(std::basic_istream<Char, Traits>& in, rational<T>& rat)
{
  typename std::basic_istream<Char, Traits>::sentry sentry{in, false};
  ioflags flags{in};

  T n{};
  if (not (in >> n))
    // Error reading the numerator.
    return in;

  in >> std::noskipws;
  char sep{};
  if (not (in >> sep))
    // Error reading the separator character.
    return in;
  else if (sep != '/')
  {
    // Push sep back into the input stream, so the next input operation
    // will read it.
    in.unget();
    rat = n;
    return in;
  }
  else
  {
    T d{};
    if (in >> d)
      // Successfully read numerator, separator, and denominator.
      rat = rational<T>{n, d};
  }

  return in;
}

template<class T, class Char, class Traits>
std::basic_ostream<Char, Traits>& operator<<(std::basic_ostream<Char, Traits>& out, rational<T> const& rat)
{
  typename std::basic_ostream<Char, Traits>::sentry sentry{out};
  std::ostringstream stream;
  stream << rat.numerator() << '/' << rat.denominator();
  out << stream.str();
  return out;
}

#endif