src/math/Rational.h

   1 #ifndef MATH_RATIONAL_H_
   2 #define MATH_RATIONAL_H_
   3
   4 #include <ostream>
   5
   6
   7 namespace math {
   8
   9 /// Rational number type.
  10 /// Stores 2 Integers and has the value num / denom.
  11 template<class Integer>
  12 class Rational {
  13
  14 public:
  15         explicit Rational(Integer num = 0, Integer denom = 1)
  16         : num(num), denom(denom) { }
  17         template<class OtherInt>
  18         explicit Rational(const Rational<OtherInt> &other)
  19         : num(other.Numerator()), denom(other.Denominator()) { }
  20
  21 public:
  22         Integer &Numerator() { return num; }
  23         const Integer &Numerator() const { return num; }
  24         Integer &Denominator() { return denom; }
  25         const Integer &Denominator() const { return denom; }
  26
  27         Integer Int() const { return num / denom; }
  28         Integer Inv() const { return denom / num; }
  29         float Float() const { return float(num) / denom; }
  30         double Double() const { return double(num) / denom; }
  31
  32         bool IsWhole() const {
  33                 return num % denom == 0;
  34         }
  35         bool IsFrac() const {
  36                 return num % denom != 0;
  37         }
  38
  39         void QuickPack() {
  40                 if (num == 1 || denom == 1) return;
  41                 if (num % denom == 0) {
  42                         num /= denom;
  43                         denom = 1;
  44                 } else if (denom % num == 0) {
  45                         denom /= num;
  46                         num = 1;
  47                 }
  48         }
  49
  50         void Pack() {
  51                 if (num == 1 || denom == 1) return;
  52                 if (num % denom == 0) {
  53                         num /= denom;
  54                         denom = 1;
  55                         return;
  56                 }
  57                 if (denom % num == 0) {
  58                         denom /= num;
  59                         num = 1;
  60                         return;
  61                 }
  62                 while (num % 2 == 0 && denom % 2 == 0) {
  63                         num /= 2;
  64                         denom /= 2;
  65                 }
  66                 while (num % 3 == 0 && denom % 3 == 0) {
  67                         num /= 3;
  68                         denom /= 3;
  69                 }
  70                 while (num % 5 == 0 && denom % 5 == 0) {
  71                         num /= 5;
  72                         denom /= 5;
  73                 }
  74         }
  75
  76 public:
  77         template<class OtherInt>
  78         Rational &operator =(OtherInt i) {
  79                 num = i;
  80                 denom = 1;
  81                 return *this;
  82         }
  83         template<class OtherInt>
  84         Rational &operator =(Rational<OtherInt> r) {
  85                 num = r.Numerator();
  86                 denom = r.Denominator();
  87                 return *this;
  88         }
  89         template<class OtherInt>
  90         Rational &operator +=(OtherInt i) {
  91                 num += i * denom;
  92                 return *this;
  93         }
  94         template<class OtherInt>
  95         Rational &operator +=(Rational<OtherInt> r) {
  96                 num = num * r.Denominator() + r.Numerator() * denom;
  97                 denom *= r.Denominator();
  98                 return *this;
  99         }
 100         template<class OtherInt>
 101         Rational &operator -=(OtherInt i) {
 102                 num -= i * denom;
 103                 return *this;
 104         }
 105         template<class OtherInt>
 106         Rational &operator -=(Rational<OtherInt> r) {
 107                 num = num * r.Denominator() - r.Numerator() * denom;
 108                 denom *= r.Denominator();
 109                 return *this;
 110         }
 111         template<class OtherInt>
 112         Rational &operator *=(OtherInt i) {
 113                 if (denom % i == 0) {
 114                         denom /= i;
 115                 } else {
 116                         num *= i;
 117                 }
 118                 return *this;
 119         }
 120         template<class OtherInt>
 121         Rational &operator *=(const Rational<OtherInt> &r) {
 122                 num *= r.Numerator();
 123                 denom *= r.Denominator();
 124                 return *this;
 125         }
 126         Rational &operator *=(float f) {
 127                 num *= f;
 128                 return *this;
 129         }
 130         Rational &operator *=(double d) {
 131                 num *= d;
 132                 return *this;
 133         }
 134         template<class OtherInt>
 135         Rational &operator /=(OtherInt i) {
 136                 if (num % i == 0) {
 137                         num /= i;
 138                 } else {
 139                         denom *= i;
 140                 }
 141                 return *this;
 142         }
 143         template<class OtherInt>
 144         Rational &operator /=(const Rational<OtherInt> &r) {
 145                 num *= r.Denominator();
 146                 denom *= r.Numerator();
 147                 return *this;
 148         }
 149         Rational &operator /=(float f) {
 150                 if (f > 1 || f < -1) {
 151                         denom *= f;
 152                 } else {
 153                         num /= f;
 154                 }
 155                 return *this;
 156         }
 157         Rational &operator /=(double d) {
 158                 if (d > 1 || d < -1) {
 159                         denom *= d;
 160                 } else {
 161                         num /= d;
 162                 }
 163                 return *this;
 164         }
 165
 166 private:
 167         Integer num;
 168         Integer denom;
 169
 170 };
 171
 172 template<class Integer>
 173 Rational<Integer> operator -(const Rational<Integer> &r) {
 174         return Rational<Integer>(-r.Numerator(), r.Denominator());
 175 }
 176
 177 template<class LInt, class RInt>
 178 bool operator ==(
 179                 const Rational<LInt> &lhs,
 180                 const Rational<RInt> &rhs) {
 181         return lhs.Numerator() * rhs.Denominator() ==
 182                         rhs.Numerator() * lhs.Denominator();
 183 }
 184 template<class LInt, class RInt>
 185 bool operator !=(
 186                 const Rational<LInt> &lhs,
 187                 const Rational<RInt> &rhs) {
 188         return !(lhs == rhs);
 189 }
 190 template<class LInt, class RInt>
 191 bool operator ==(
 192                 const Rational<LInt> &lhs,
 193                 RInt rhs) {
 194         return lhs.IsWhole() && lhs.Int() == rhs;
 195 }
 196 template<class LInt, class RInt>
 197 bool operator !=(
 198                 const Rational<LInt> &lhs,
 199                 RInt rhs) {
 200         return !(lhs == rhs);
 201 }
 202 template<class LInt, class RInt>
 203 bool operator ==(
 204                 LInt lhs,
 205                 const Rational<RInt> &rhs) {
 206         return rhs == lhs;
 207 }
 208 template<class LInt, class RInt>
 209 bool operator !=(
 210                 LInt lhs,
 211                 const Rational<RInt> &rhs) {
 212         return rhs != lhs;
 213 }
 214
 215 template<class LInt, class RInt>
 216 bool operator <(
 217                 const Rational<LInt> &lhs,
 218                 const Rational<RInt> &rhs) {
 219         return lhs.Numerator() * rhs.Denominator() <
 220                         rhs.Numerator() * lhs.Denominator();
 221 }
 222 template<class LInt, class RInt>
 223 bool operator <(
 224                 const Rational<LInt> &lhs,
 225                 RInt rhs) {
 226         return lhs.Numerator() < rhs * lhs.Denominator();
 227 }
 228 template<class LInt, class RInt>
 229 bool operator <(
 230                 LInt lhs,
 231                 const Rational<RInt> &rhs) {
 232         return lhs * rhs.Denominator() < rhs.Numerator();
 233 }
 234
 235 template<class LInt, class RInt>
 236 bool operator <=(
 237                 const Rational<LInt> &lhs,
 238                 const Rational<RInt> &rhs) {
 239         return lhs.Numerator() * rhs.Denominator() <=
 240                         rhs.Numerator() * lhs.Denominator();
 241 }
 242 template<class LInt, class RInt>
 243 bool operator <=(
 244                 const Rational<LInt> &lhs,
 245                 RInt rhs) {
 246         return lhs.Numerator() <= rhs * lhs.Denominator();
 247 }
 248 template<class LInt, class RInt>
 249 bool operator <=(
 250                 LInt lhs,
 251                 const Rational<RInt> &rhs) {
 252         return lhs * rhs.Denominator() <= rhs.Numerator();
 253 }
 254
 255 template<class LInt, class RInt>
 256 bool operator >(
 257                 const Rational<LInt> &lhs,
 258                 const Rational<RInt> &rhs) {
 259         return lhs.Numerator() * rhs.Denominator() >
 260                         rhs.Numerator() * lhs.Denominator();
 261 }
 262 template<class LInt, class RInt>
 263 bool operator >(
 264                 const Rational<LInt> &lhs,
 265                 RInt rhs) {
 266         return lhs.Numerator() > rhs * lhs.Denominator();
 267 }
 268 template<class LInt, class RInt>
 269 bool operator >(
 270                 LInt lhs,
 271                 const Rational<RInt> &rhs) {
 272         return lhs * rhs.Denominator() > rhs.Numerator();
 273 }
 274
 275 template<class LInt, class RInt>
 276 bool operator >=(
 277                 const Rational<LInt> &lhs,
 278                 const Rational<RInt> &rhs) {
 279         return lhs.Numerator() * rhs.Denominator() >=
 280                         rhs.Numerator() * lhs.Denominator();
 281 }
 282 template<class LInt, class RInt>
 283 bool operator >=(
 284                 const Rational<LInt> &lhs,
 285                 RInt rhs) {
 286         return lhs.Numerator() >= rhs * lhs.Denominator();
 287 }
 288 template<class LInt, class RInt>
 289 bool operator >=(
 290                 LInt lhs,
 291                 const Rational<RInt> &rhs) {
 292         return lhs * rhs.Denominator() >= rhs.Numerator();
 293 }
 294
 295 template<class LInt, class RInt>
 296 Rational<LInt> operator +(
 297                 const Rational<LInt> &lhs,
 298                 const Rational<RInt> &rhs) {
 299         return Rational<LInt>(lhs) += rhs;
 300 }
 301 template<class LInt, class RInt>
 302 Rational<LInt> operator +(
 303                 const Rational<LInt> &lhs,
 304                 RInt rhs) {
 305         return Rational<LInt>(lhs) += rhs;
 306 }
 307 template<class LInt, class RInt>
 308 LInt operator +(
 309                 LInt lhs,
 310                 const Rational<RInt> &rhs) {
 311         return lhs + rhs.Int();
 312 }
 313
 314 template<class LInt, class RInt>
 315 Rational<LInt> operator -(
 316                 const Rational<LInt> &lhs,
 317                 const Rational<RInt> &rhs) {
 318         return Rational<LInt>(lhs) -= rhs;
 319 }
 320 template<class LInt, class RInt>
 321 Rational<LInt> operator -(
 322                 const Rational<LInt> &lhs,
 323                 RInt rhs) {
 324         return Rational<LInt>(lhs) -= rhs;
 325 }
 326 template<class LInt, class RInt>
 327 LInt operator -(
 328                 LInt lhs,
 329                 const Rational<RInt> &rhs) {
 330         return lhs - rhs.Int();
 331 }
 332
 333 template<class LInt, class RInt>
 334 Rational<LInt> operator *(
 335                 const Rational<LInt> &lhs,
 336                 const Rational<RInt> &rhs) {
 337         return Rational<LInt>(lhs) *= rhs;
 338 }
 339 template<class LInt, class RInt>
 340 Rational<LInt> operator *(
 341                 const Rational<LInt> &lhs,
 342                 RInt rhs) {
 343         return Rational<LInt>(lhs) *= rhs;
 344 }
 345 template<class LInt, class RInt>
 346 LInt operator *(
 347                 LInt lhs,
 348                 const Rational<RInt> &rhs) {
 349         return lhs * rhs.Numerator() / rhs.Denominator();
 350 }
 351
 352 template<class LInt, class RInt>
 353 Rational<LInt> operator /(
 354                 const Rational<LInt> &lhs,
 355                 const Rational<RInt> &rhs) {
 356         return Rational<LInt>(lhs) /= rhs;
 357 }
 358 template<class LInt, class RInt>
 359 Rational<LInt> operator /(
 360                 const Rational<LInt> &lhs,
 361                 RInt rhs) {
 362         return Rational<LInt>(lhs) /= rhs;
 363 }
 364 template<class LInt, class RInt>
 365 LInt operator /(
 366                 LInt lhs,
 367                 const Rational<RInt> &rhs) {
 368         return lhs * rhs.Denominator() / rhs.Numerator();
 369 }
 370
 371
 372 template<class Integer>
 373 inline std::ostream &operator <<(std::ostream &out, const Rational<Integer> &r) {
 374         return out << r.Double();
 375 }
 376
 377 }
 378
 379 #endif