Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/math/rational/rational.h
Go to the documentation of this file.
00001 #ifndef H_MATH_RATIONAL_RATIONAL
00002 #define H_MATH_RATIONAL_RATIONAL
00003 
00006 #include <ostream>
00007 #include <stdexcept>
00008 #include <stdint.h>
00009 #include "math/gcd/gcd.h"
00010 #include "utils/preconditions/preconditions.h"
00011 
00012 #define NEEDS_INT_DEFINED
00013 #include "third_party/safeint3.hpp"
00014 
00015 
00020 #pragma GCC diagnostic ignored "-Wtype-limits"
00021 namespace math {
00022 namespace rational {
00023 
00024 template <typename T>
00025 class Rational {
00026  public:
00027   // compile assert
00028   C_ASSERT(NumericType<T>::isInt);
00029 
00033   Rational():num(0),den(1) {
00034   }
00035 
00040   Rational(T value):num(value),den(1) {
00041     normalize();
00042   }
00043 
00050   Rational(T n, T d):num(n),den(d) {
00051     Preconditions::check(d != 0,
00052         "Rational number shoud have non-zero denominator");
00053 
00054     normalize();
00055   }
00056 
00060   Rational(const Rational<T>& value):num(value.num),den(value.den) {
00061     Preconditions::check(value.den != 0,
00062         "Rational numer shoud have non-zero denominator");
00063     normalize();
00064   }
00065 
00069   Rational<T> inverted() const {
00070     if (num == 0) {
00071       throw std::overflow_error("Division by zero!");
00072     }
00073     return Rational<T>(den, num);
00074   }
00075 
00079   T numerator() const {
00080     return num;
00081   }
00082 
00086   T denominator() const {
00087     return den;
00088   }
00089 
00095   void normalize() {
00096     T h = math::gcd::gcd(num, den);
00097     assert(h != 0); // gcd shouldn't return zero (den != 0)
00098     num /= h;
00099     den /= h;
00100 
00101     if (IntTraits<T>::isSigned && (den < 0)) {
00102       den = -den;
00103       num = -num;
00104     }
00105   }
00106 
00107 
00108   private:
00110     T num;
00112     T den;
00113 };
00114 
00115 
00128 template<typename T>
00129 Rational<T> operator*(const Rational<T> &a, const Rational<T> &b)
00130 {
00131   // here we use safe versions of computations
00132   // if you believe your code will won't need them, just make it as
00133   // normal multiplication (but it is not recommended)
00134   try {
00135     SafeInt<T> num(a.numerator()); num *= b.numerator();
00136     SafeInt<T> den(a.denominator()); den *= b.denominator();
00137     return Rational<T>((T)num, (T)den);
00138   } catch (SafeIntException err){
00139     throw std::overflow_error("Overflow while multiplying");
00140   }
00141 }
00142 
00150 template<typename T>
00151 Rational<T> operator/(const Rational<T> &a, const Rational<T> &b)
00152 {
00153   if (b.numerator() == 0) {
00154     throw std::overflow_error("Division by zero!");
00155   }
00156 
00157   return a * b.inverted();
00158 }
00159 
00165 template<typename T>
00166 Rational<T> operator-(const Rational<T> &a)
00167 {
00168   // can't do unary minus on unsigned types
00169   C_ASSERT(IntTraits<T>::isSigned);
00170   // we need SafeInt here because unary minus on
00171   // MIN_INT will overflow.
00172   try {
00173     return Rational<T>(-SafeInt<T>(a.numerator()), a.denominator());
00174   } catch (SafeIntException err){
00175     throw std::overflow_error("Overflow while add/subtract");
00176   }
00177 }
00178 
00186 template<typename T>
00187 Rational<T> operator+(const Rational<T> &a, const Rational<T> &b)
00188 {
00189   try {
00190     SafeInt<T> t1(a.numerator()); t1 *= b.denominator();
00191     SafeInt<T> t2(b.numerator()); t2 *= a.denominator();
00192     SafeInt<T> den(a.denominator()); den *= b.denominator();
00193     return Rational<T>( (T) (t1 + t2), den);
00194   } catch (SafeIntException err){
00195     throw std::overflow_error("Overflow while add/subtract");
00196   }
00197 }
00198 
00206 template<typename T>
00207 Rational<T> operator-(const Rational<T> &a, const Rational<T> &b)
00208 {
00209   try {
00210     SafeInt<T> t1(a.numerator()); t1 *= b.denominator();
00211     SafeInt<T> t2(b.numerator()); t2 *= a.denominator();
00212     SafeInt<T> den(a.denominator()); den *= b.denominator();
00213     return Rational<T>( (T) (t1 - t2), den);
00214   } catch (SafeIntException err){
00215     throw std::overflow_error("Overflow while add/subtract");
00216   }
00217 }
00218 
00227 template<typename T>
00228 bool operator==(const Rational<T> &a, const Rational<T> &b) {
00229   return (a.numerator() == b.numerator()) && (a.denominator() == b.denominator());
00230 }
00231 
00237 template<typename T>
00238 bool operator<(const Rational<T> &a, const Rational<T> &b) {
00239   try {
00240     SafeInt<T> t1(a.numerator()); t1 *= b.denominator();
00241     SafeInt<T> t2(b.numerator()); t2 *= a.denominator();
00242     return t1 < t2; 
00243   } catch (SafeIntException err){
00244     throw std::overflow_error("Overflow while comparison");
00245   }
00246 }
00247 
00253 template<typename T>
00254 bool operator>(const Rational<T> &a, const Rational<T> &b) {
00255   return b < a;
00256 }
00257 
00263 template<typename T>
00264 bool operator<=(const Rational<T> &a, const Rational<T> &b) {
00265   return !(b>a);
00266 }
00267 
00273 template<typename T>
00274 bool operator>=(const Rational<T> &a, const Rational<T> &b) {
00275   return !(a<b);
00276 }
00277 
00289 template<typename T>
00290 std::ostream& operator<<(std::ostream& out, const Rational<T> &a) {
00291   out << a.numerator() << "/" << a.denominator();
00292   return out;
00293 }
00294 
00295 } // rational
00296 } // math
00297 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines