- Main Page
- Namespaces
- Classes
- Files

# rational.hpp

    00001 #ifndef RATIONAL_HPP_
    00002 #define RATIONAL_HPP_
    00003
    00004 #include <istream>
    00005 #include <limits>
    00006 #include <ostream>
    00007 #include <sstream>
    00008 #include <stdexcept>
    00009 #include <string>
    00010
    00011 #include "gcd.hpp"
    00012 #include "ioflags.hpp"
    00013
    00015 template<class T>
    00016 class rational
    00017 {
    00018 public:
    00020   typedef T value_type;
    00022   class zero_denominator : public std::logic_error
    00023   {
    00024   public:
    00026     zero_denominator(std::string const& what) : logic_error(what) {}
    00027   };
    00028
    00033   rational(value_type num = 0): numerator_(num), denominator_(1) {}
    00038   rational(value_type num, value_type den);
    00041   rational(double r);
    00043   template<class U>
    00044   rational(rational<U> const& that);
    00045
    00047   value_type numerator()              const { return numerator_; }
    00049   value_type denominator()            const { return denominator_; }
    00051   template<class U>
    00052   U as() const { return static_cast<U>(numerator()) / denominator(); }
    00053
    00055   rational& operator=(value_type); // optimization to avoid an unneeded call to reduce()
    00056
    00058   template<class U>
    00059   rational& operator=(rational<U> const& rhs);
    00060
    00062   rational& operator+=(rational const& rhs);
    00064   rational& operator+=(value_type const& rhs);
    00065
    00067   rational& operator-=(rational const& rhs);
    00069   rational& operator-=(value_type const& rhs);
    00070
    00072   rational& operator*=(rational const& rhs);
    00074   rational& operator*=(value_type const& rhs);
    00075
    00077   rational& operator/=(rational const& rhs);
    00079   rational& operator/=(value_type const& rhs);
    00080
    00082   rational& operator++();
    00084   rational& operator--();
    00086   rational operator++(int);
    00088   rational operator--(int);
    00089
    00090 private:
    00092   void reduce();
    00095   void normalize();
    00098   template<class U>
    00099   value_type scale(U value);
    00100
    00101   value_type numerator_;
    00102   value_type denominator_;
    00103 };
    00104
    00105 template<class T>
    00106 rational<T>::rational(value_type num, value_type den)
    00107 : numerator_(num),
    00108   denominator_(den == value_type() ? throw zero_denominator("zero denominator") : den)
    00109 {
    00110   normalize();
    00111 }
    00112
    00113 template<class T>
    00114 rational<T>::rational(double r)
    00115 : numerator_(static_cast<T>(r / 100000)), denominator_(static_cast<T>(100000))
    00116 {}
    00117
    00118 template<class T>
    00119 template<class U>
    00120 rational<T>::rational(rational<U> const& that)
    00121 : numerator_(scale<U>(that.numerator())), denominator_(scale<U>(that.denominator()))
    00122 {
    00123   reduce();
    00124 }
    00125
    00126 template<class T>
    00127 template<class U>
    00128 T rational<T>::scale(U value)
    00129 {
    00130   if (std::numeric_limits<T>::digits >= std::numeric_limits<U>::digits)
    00131     return T(value);
    00132   else
    00133     return T(value >> (std::numeric_limits<U>::digits - std::numeric_limits<T>::digits));
    00134 }
    00135
    00136 template<class T>
    00137 void rational<T>::normalize()
    00138 {
    00139   if (denominator_ < value_type())
    00140   {
    00141     denominator_ = -denominator_;
    00142     numerator_ = -numerator_;
    00143   }
    00144   reduce();
    00145 }
    00146
    00147 template<class T>
    00148 void rational<T>::reduce()
    00149 {
    00150   value_type div(gcd(numerator(), denominator()));
    00151   if (div == value_type())
    00152     throw zero_denominator("zero denominator");
    00153   numerator_ /= div;
    00154   denominator_ /= div;
    00155 }
    00156
    00157 template<class T>
    00158 rational<T>& rational<T>::operator=(T num)
    00159 {
    00160   numerator_ = num;
    00161   denominator_ = value_type(1);
    00162   return *this;
    00163 }
    00164
    00165 template<class T>
    00166 template<class U>
    00167 rational<T>& rational<T>::operator=(rational<U> const& rhs)
    00168 {
    00169   numerator_ = scale<U>(rhs.numerator());
    00170   denominator_ = scale<U>(rhs.denominator());
    00171   reduce();
    00172   return *this;
    00173 }
    00174
    00175 template<class T>
    00176 rational<T>& rational<T>::operator+=(rational const& rhs)
    00177 {
    00178   numerator_ = numerator() * rhs.denominator() + rhs.numerator() * denominator();
    00179   denominator_ *= rhs.denominator();
    00180   reduce();
    00181   return *this;
    00182 }
    00183
    00184 template<class T>
    00185 rational<T>& rational<T>::operator+=(value_type const& rhs)
    00186 {
    00187   numerator_ = numerator() + rhs * denominator();
    00188   reduce();
    00189   return *this;
    00190 }
    00191
    00192 template<class T>
    00193 rational<T>& rational<T>::operator-=(rational const& rhs)
    00194 {
    00195   numerator_ = numerator() * rhs.denominator() - rhs.numerator() * denominator();
    00196   denominator_ *= rhs.denominator();
    00197   reduce();
    00198   return *this;
    00199 }
    00200
    00201 template<class T>
    00202 rational<T>& rational<T>::operator-=(value_type const& rhs)
    00203 {
    00204   numerator_ = numerator() - rhs * denominator();
    00205   reduce();
    00206   return *this;
    00207 }
    00208
    00209 template<class T>
    00210 rational<T>& rational<T>::operator*=(rational const& rhs)
    00211 {
    00212   numerator_ *= rhs.numerator();
    00213   denominator_ *= rhs.denominator();
    00214   reduce();
    00215   return *this;
    00216 }
    00217
    00218 template<class T>
    00219 rational<T>& rational<T>::operator*=(value_type const& rhs)
    00220 {
    00221   numerator_ *= rhs;
    00222   reduce();
    00223   return *this;
    00224 }
    00225
    00226 template<class T>
    00227 rational<T>& rational<T>::operator/=(rational const& rhs)
    00228 {
    00229   if (rhs.numerator() == value_type())
    00230     throw zero_denominator("divide by zero");
    00231   numerator_ *= rhs.denominator();
    00232   denominator_ *= rhs.numerator();
    00233   normalize();
    00234   return *this;
    00235 }
    00236
    00237 template<class T>
    00238 rational<T>& rational<T>::operator/=(value_type const& rhs)
    00239 {
    00240   if (rhs == value_type())
    00241     throw zero_denominator("divide by zero");
    00242   denominator_ *= rhs;
    00243   normalize();
    00244   return *this;
    00245 }
    00246
    00247 template<class T>
    00248 rational<T>& rational<T>::operator++()
    00249 {
    00250   numerator_ += denominator();
    00251   return *this;
    00252 }
    00253
    00254 template<class T>
    00255 rational<T> rational<T>::operator++(int)
    00256 {
    00257   rational result(*this);
    00258   ++*this;
    00259   return result;
    00260 }
    00261
    00262 template<class T>
    00263 rational<T>& rational<T>::operator--()
    00264 {
    00265   numerator_ -= denominator();
    00266   return *this;
    00267 }
    00268
    00269 template<class T>
    00270 rational<T> rational<T>::operator--(int)
    00271 {
    00272   rational result(*this);
    00273   --*this;
    00274   return result;
    00275 }
    00276
    00278 template<class T>
    00279 rational<T> operator-(rational<T> const& r)
    00280 {
    00281   return rational<T>(-r.numerator(), r.denominator());
    00282 }
    00283
    00284 template<class T>
    00285 rational<T> absval(rational<T> const& r)
    00286 {
    00287   using namespace std;
    00288   return rational<T>(abs(r.numerator()), r.denominator());
    00289 }
    00290
    00292 template<class T>
    00293 rational<T> operator+(rational<T> lhs, rational<T> const& rhs)
    00294 {
    00295   lhs += rhs;
    00296   return lhs;
    00297 }
    00298
    00300 template<class T>
    00301 rational<T> operator+(rational<T> lhs, T const& rhs)
    00302 {
    00303   lhs += rhs;
    00304   return lhs;
    00305 }
    00306
    00308 template<class T>
    00309 rational<T> operator+(T const& lhs, rational<T> rhs)
    00310 {
    00311   rhs += lhs;
    00312   return rhs;
    00313 }
    00314
    00316 template<class T>
    00317 rational<T> operator-(rational<T> lhs, rational<T> const& rhs)
    00318 {
    00319   lhs -= rhs;
    00320   return lhs;
    00321 }
    00322
    00324 template<class T>
    00325 rational<T> operator-(rational<T> lhs, T const& rhs)
    00326 {
    00327   lhs -= rhs;
    00328   return lhs;
    00329 }
    00330
    00332 template<class T>
    00333 rational<T> operator-(T const& lhs, rational<T> rhs)
    00334 {
    00335   // Gotta be a little tricky.
    00336   rhs += -lhs;
    00337   return -rhs;
    00338 }
    00339
    00341 template<class T>
    00342 rational<T> operator*(rational<T> lhs, rational<T> const& rhs)
    00343 {
    00344   lhs *= rhs;
    00345   return lhs;
    00346 }
    00347
    00349 template<class T>
    00350 rational<T> operator*(rational<T> lhs, T const& rhs)
    00351 {
    00352   lhs *= rhs;
    00353   return lhs;
    00354 }
    00355
    00357 template<class T>
    00358     rational<T> operator*(T const& lhs, rational<T> rhs)
    00359 {
    00360   rhs *= lhs;
    00361   return rhs;
    00362 }
    00363
    00365 template<class T>
    00366 rational<T> operator/(rational<T> lhs, rational<T> const& rhs)
    00367 {
    00368   lhs /= rhs;
    00369   return lhs;
    00370 }
    00371
    00373 template<class T>
    00374 rational<T> operator/(rational<T> lhs, T const& rhs)
    00375 {
    00376   lhs /= rhs;
    00377   return lhs;
    00378 }
    00379
    00381 template<class T>
    00382 rational<T> operator/(T const& lhs, rational<T> rhs)
    00383 {
    00384   return rational<T>(lhs * rhs.denominator(), rhs.numerator());
    00385 }
    00386
    00387
    00389 template<class T, class U>
    00390 bool operator==(rational<T> const& a, rational<U> const& b)
    00391 {
    00392   return a.numerator() == b.numerator() and
    00393          a.denominator() == b.denominator();
    00394 }
    00395
    00397 template<class T>
    00398 bool operator==(rational<T> const& lhs, T rhs)
    00399 {
    00400   return lhs.denominator() == 1 and
    00401          lhs.numerator()   == rhs;
    00402 }
    00403
    00405 template<class T>
    00406 bool operator==(T lhs, rational<T> const& rhs)
    00407 {
    00408   return rhs.denominator() == 1 and
    00409          rhs.numerator()   == lhs;
    00410 }
    00411
    00413 template<class T>
    00414 bool operator<(rational<T> const& a, rational<T> const& b)
    00415 {
    00416   return a.numerator() * b.denominator() < b.numerator() * a.denominator();
    00417 }
    00418
    00420 template<class T>
    00421 bool operator<(rational<T> const& a, T const& b)
    00422 {
    00423   return a.numerator() < b * a.denominator();
    00424 }
    00425
    00427 template<class T>
    00428 bool operator<(T const& a, rational<T> const& b)
    00429 {
    00430   return a * b.denominator() < b.numerator();
    00431 }
    00432
    00434 template<class T, class U>
    00435 inline bool operator!=(rational<T> const& a, rational<U> const& b)
    00436 {
    00437   return not (a == b);
    00438 }
    00439
    00441 template<class T>
    00442 inline bool operator!=(rational<T> const& a, T b)
    00443 {
    00444   return not (a == b);
    00445 }
    00446
    00448 template<class T>
    00449 inline bool operator!=(T a, rational<T> const& b)
    00450 {
    00451   return not (a == b);
    00452 }
    00453
    00455 template<class T>
    00456 inline bool operator<=(rational<T> const& a, rational<T> const& b)
    00457 {
    00458   return not (b < a);
    00459 }
    00460
    00462 template<class T>
    00463 inline bool operator<=(rational<T> const& a, T const& b)
    00464 {
    00465   return not (b < a);
    00466 }
    00467
    00469 template<class T>
    00470 inline bool operator<=(T const& a, rational<T> const& b)
    00471 {
    00472   return not (b < a);
    00473 }
    00474
    00476 template<class T>
    00477 inline bool operator>(rational<T> const& a, rational<T> const& b)
    00478 {
    00479   return b < a;
    00480 }
    00481
    00483 template<class T>
    00484 inline bool operator>(rational<T> const& a, T const& b)
    00485 {
    00486   return b < a;
    00487 }
    00488
    00490 template<class T>
    00491 inline bool operator>(T const& a, rational<T> const& b)
    00492 {
    00493   return b < a;
    00494 }
    00495
    00497 template<class T>
    00498 inline bool operator>=(rational<T> const& a, rational<T> const& b)
    00499 {
    00500   return not (b > a);
    00501 }
    00502
    00504 template<class T>
    00505 inline bool operator>=(rational<T> const& a, T const& b)
    00506 {
    00507   return not (b > a);
    00508 }
    00509
    00511 template<class T>
    00512 inline bool operator>=(T const& a, rational<T> const& b)
    00513 {
    00514   return not (b > a);
    00515 }
    00516
    00518 template<class T, class Char, class Traits>
    00519 std::basic_istream<Char, Traits>& operator>>(std::basic_istream<Char, Traits>& in, rational<T>& rat)
    00520 {
    00521   typename std::basic_istream<Char, Traits>::sentry sentry(in, false);
    00522   ioflags flags(in);
    00523
    00524   T n = T();
    00525   if (not (in >> n))
    00526     // Error reading the numerator.
    00527     return in;
    00528
    00529   in >> std::noskipws;
    00530   char sep('\0');
    00531   if (not (in >> sep))
    00532     // Error reading the separator character.
    00533     return in;
    00534   else if (sep != '/')
    00535   {
    00536     // Push sep back into the input stream, so the next input operation
    00537     // will read it.
    00538     in.unget();
    00539     rat = n;
    00540     return in;
    00541   }
    00542   else
    00543   {
    00544     T d = T();
    00545     if (in >> d)
    00546       // Successfully read numerator, separator, and denominator.
    00547       rat = rational<T>(n, d);
    00548   }
    00549
    00550   return in;
    00551 }
    00552
    00554 template<class T, class Char, class Traits>
    00555 std::basic_ostream<Char, Traits>& operator<<(std::basic_ostream<Char, Traits>& out, rational<T> const& rat)
    00556 {
    00557   typename std::basic_ostream<Char, Traits>::sentry sentry(out);
    00558   std::ostringstream stream;
    00559   stream << rat.numerator() << '/' << rat.denominator();
    00560   out << stream.str();
    00561   return out;
    00562 }
    00563
    00564 #endif