00001
00002
00003
00004
00005
00006
00007
00008
00009 #ifndef RATIONAL_H_
00010 #define RATIONAL_H_
00011
00012 #include<iostream.h>
00013 #include<stdlib.h>
00014 #include<strstrea.h>
00015 #include<string.h>
00016 #include<ctype.h>
00017 #include"gcd.h"
00018
00019
00025
00026 #if defined(__BORLANDC__) && defined(__WIN32__) //bc 5.5/
00027 template <class T> class rational;
00028 template <class T> istream & operator >> (istream & s, rational<T> & x);
00029 template <class T> ostream & operator << (ostream & s, const rational<T> & x);
00030 template <class T> int cmp(const rational<T> & a, const rational<T> & b);
00031 template <class T> int operator == (const rational<T> & a, const rational<T> & b);
00032 template <class T> int operator != (const rational<T> & a, const rational<T> & b);
00033 template <class T> int operator > (const rational<T> & a, const rational<T> & b);
00034 template <class T> int operator >= (const rational<T> & a, const rational<T> & b);
00035 template <class T> int operator < (const rational<T> & a, const rational<T> & b);
00036 template <class T> int operator <= (const rational<T> & a, const rational<T> & b);
00037 template <class T> int is_integer(const rational<T> & a);
00038 template <class T> rational<T> ceil(const rational<T> & a);
00039 template <class T> rational<T> floor(const rational<T> & a);
00040 template <class T> rational<T> frac(const rational<T> & a);
00041 template <class T> T iceil(const rational<T> & a);
00042 template <class T> T ifloor(const rational<T> & a);
00043 template <class T> rational<T> operator + (const rational<T> & a);
00044 template <class T> rational<T> operator - (const rational<T> & a);
00045 template <class T> rational<T> operator + (const rational<T> & b, const rational<T> & c);
00046 template <class T> rational<T> operator - (const rational<T> & b, const rational<T> & c);
00047 template <class T> rational<T> operator * (const rational<T> & b, const rational<T> & c);
00048 template <class T> rational<T> operator / (const rational<T> & b, const rational<T> & c);
00049 template <class T> rational<T> operator += (rational<T> & b, const rational<T> & c);
00050 template <class T> rational<T> operator -= (rational<T> & b, const rational<T> & c);
00051 template <class T> rational<T> operator *= (rational<T> & b, const rational<T> & c);
00052 template <class T> rational<T> operator /= (rational<T> & b, const rational<T> & c);
00053 #endif
00054
00058
00059 template <class T>
00060 class rational
00061 {
00062 public:
00063
00078
00079 rational();
00080 rational(char* str);
00081 rational(const rational<T>& b);
00082 rational(int w);
00083 rational(T w);
00084 rational(T u, T v);
00085
00086 rational<T> & operator = (const rational<T>& b);
00087
00094 int sign() const;
00095
00096
00097
00098 #if !defined(__BORLANDC__) || !defined(__WIN32__)
00099
00100 friend ostream & operator << (ostream & s, const rational<T> & x);
00101
00102 friend istream & operator >> (istream & s, rational<T> & x);
00103
00110 friend int cmp (const rational<T> & a, const rational<T> & b);
00112 friend int operator == (const rational<T> & a, const rational<T> & b);
00114 friend int operator != (const rational<T> & a, const rational<T> & b);
00116 friend int operator > (const rational<T> & a, const rational<T> & b);
00118 friend int operator >= (const rational<T> & a, const rational<T> & b);
00120 friend int operator < (const rational<T> & a, const rational<T> & b);
00122 friend int operator <= (const rational<T> & a, const rational<T> & b);
00124 friend int is_integer (const rational<T> & a);
00126 friend rational<T> ceil (const rational<T> & a);
00128 friend rational<T> floor (const rational<T> & a);
00130 friend rational<T> frac(const rational<T> & a);
00132 friend T iceil (const rational<T> & a);
00134 friend T ifloor (const rational<T> & a);
00135 friend rational<T> operator + (const rational<T> & a);
00136 friend rational<T> operator - (const rational<T> & a);
00137
00138 friend rational<T> operator + (const rational<T> & b, const rational<T> & c);
00140 friend rational<T> operator - (const rational<T> & b, const rational<T> & c);
00142 friend rational<T> operator * (const rational<T> & b, const rational<T> & c);
00144 friend rational<T> operator / (const rational<T> & b, const rational<T> & c);
00146 friend rational<T> operator += (rational<T> & b, const rational<T> & c);
00148 friend rational<T> operator -= (rational<T> & b, const rational<T> & c);
00150 friend rational<T> operator *= (rational<T> & b, const rational<T> & c);
00152 friend rational<T> operator /= (rational<T> & b, const rational<T> & c);
00153 #else // bc 5.5
00154 friend ostream & operator <<<T> (ostream & s, const rational<T> & x);
00155 friend istream & operator >><T> (istream & s, rational<T> & x);
00156 friend int cmp<T> (const rational<T> & a, const rational<T> & b);
00157 friend int operator ==<T> (const rational<T> & a, const rational<T> & b);
00158 friend int operator !=<T> (const rational<T> & a, const rational<T> & b);
00159 friend int operator > <T>(const rational<T> & a, const rational<T> & b);
00160 friend int operator >=<T> (const rational<T> & a, const rational<T> & b);
00161 friend int operator < <T> (const rational<T> & a, const rational<T> & b);
00162 friend int operator <=<T> (const rational<T> & a, const rational<T> & b);
00163 friend int is_integer<T> (const rational<T> & a);
00164 friend rational<T> ceil<T> (const rational<T> & a);
00165 friend rational<T> floor<T> (const rational<T> & a);
00166 friend rational<T> frac<T> (const rational<T> & a);
00167 friend T iceil<T> (const rational<T> & a);
00168 friend T ifloor<T> (const rational<T> & a);
00169 friend rational<T> operator +<T> (const rational<T> & a);
00170 friend rational<T> operator -<T> (const rational<T> & a);
00171 friend rational<T> operator +<T> (const rational<T> & b, const rational<T> & c);
00172 friend rational<T> operator -<T> (const rational<T> & b, const rational<T> & c);
00173 friend rational<T> operator *<T> (const rational<T> & b, const rational<T> & c);
00174 friend rational<T> operator /<T> (const rational<T> & b, const rational<T> & c);
00175 friend rational<T> operator +=<T> (rational<T> & b, const rational<T> & c);
00176 friend rational<T> operator -=<T> (rational<T> & b, const rational<T> & c);
00177 friend rational<T> operator *=<T> (rational<T> & b, const rational<T> & c);
00178 friend rational<T> operator /=<T> (rational<T> & b, const rational<T> & c);
00179 #endif
00180
00181 #if !defined(__BORLANDC__) || !defined(__WIN32__)
00182 private:
00183 #endif
00184
00185
00186
00187
00188 T p;
00189 T q;
00190
00191 void optimize();
00192
00193 };
00194
00195 void rational_warning(const char* s)
00196 {
00197 cerr << "Rationals Warning: " << s << "\n";
00198 }
00199
00200 void rational_error(const char* s)
00201 {
00202 cerr << "Rationals Error: " << s << "\n";
00203 }
00204
00205 void rational_fatal_error(const char* s)
00206 {
00207 cerr << "Rationals Fatal Error: \n " << s << "\n";
00208 exit(1);
00209 }
00210
00211 template <class T>
00212 rational<T>::
rational()
00213 {
00214 p = 0;
00215 q = 1;
00216 }
00217
00218 template <class T>
00219 rational<T>::
rational(char* str)
00220 {
00221 rational<T> a;
00222 #ifdef __WATCOMC__
00223 # pragma warn -665
00224 (istream)(istrstream) str >> a;
00225 # pragma warn +665
00226 #else
00227 (istrstream) str >> a;
00228 #endif
00229 *this = a;
00230 }
00231
00232 template <class T>
00233 rational<T>::
rational(const rational<T> & b)
00234 {
00235 p = b.p;
00236 q = b.q;
00237 }
00238
00239 template <class T>
00240 rational<T>::
rational(int w)
00241 {
00242 p = w;
00243 q = 1;
00244 }
00245
00246 template <class T>
00247 rational<T>::
rational(T w)
00248 {
00249 p = w;
00250 q = 1;
00251 }
00252
00253
00254 template <class T>
00255 rational<T>::
rational(T u, T v)
00256 {
00257 p = u;
00258 q = v;
00259 optimize();
00260 }
00261
00262 template <class T> rational<T> &
00263 rational<T>::
operator = (const rational<T> & b)
00264 {
00265 p = b.p;
00266 q = b.q;
00267 return *this;
00268 }
00269
00270
00271 template <class T>
00272 ostream & operator << (ostream & s, const rational<T> & x)
00273 {
00274 if (x.q == 1)
00275 return s << x.p;
00276
00277 ostrstream tmp_stream;
00278 #ifdef __WATCOMC__
00279 # pragma warn -665
00280 (ostream)tmp_stream << x.p << "/" << x.q << ends;
00281 # pragma warn +665
00282 #else
00283 tmp_stream << x.p << "/" << x.q << ends;
00284 #endif
00285 char *str = tmp_stream.str();
00286 s << str;
00287 delete [] str;
00288 return s;
00289 }
00290
00291 template <class T>
00292 istream & operator >> (istream & s, rational<T>& x)
00293 {
00294 T p, q;
00295 s >> p;
00296 char ch;
00297 s.get(ch);
00298 if (ch != '/')
00299 {
00300 s.putback(ch);
00301 x = p;
00302 }
00303 else
00304 {
00305 s >> q;
00306 x = (rational<T>) p / (rational<T>) q;
00307 }
00308 return s;
00309 }
00310
00311 template <class T> int
00312 is_integer(const rational<T> & a)
00313 {
00314 if (a.q == 1)
00315 return 1;
00316 return 0;
00317 }
00318
00319 template <class T> rational<T>
00320 operator + (const rational<T> & b, const rational<T> & c)
00321 {
00322 rational<T> a;
00323 a.p = b.p * c.q + c.p * b.q;
00324 a.q = b.q * c.q;
00325 a.optimize();
00326 return a;
00327 }
00328
00329 template <class T> rational<T>
00330 operator - (const rational<T> & b, const rational<T> & c)
00331 {
00332 rational<T> a;
00333 a.p = b.p * c.q - c.p * b.q;
00334 a.q = b.q * c.q;
00335 a.optimize();
00336 return a;
00337 }
00338
00339 template <class T> rational<T>
00340 operator * (const rational<T> & b, const rational<T> & c)
00341 {
00342 rational<T> a;
00343 T first_gcd = gcd(b.p, c.q);
00344 T second_gcd = gcd(c.p, b.q);
00345 a.p = (b.p/first_gcd) * (c.p/second_gcd);
00346 a.q = (b.q/second_gcd) * (c.q/first_gcd);
00347 a.optimize();
00348 return a;
00349 }
00350
00351 template <class T> rational<T>
00352 operator / (const rational<T> & b, const rational<T> & c)
00353 {
00354 rational<T> a;
00355 T first_gcd = gcd(b.p, c.p);
00356 T second_gcd = gcd(c.q, b.q);
00357 a.p = (b.p/first_gcd) * (c.q/second_gcd);
00358 a.q = (b.q/second_gcd) * (c.p/first_gcd);
00359 a.optimize();
00360 return a;
00361 }
00362
00363 template <class T> rational<T>
00364 operator += (rational<T> & b, const rational<T> & c)
00365 {
00366 return b = b + c;
00367 }
00368
00369 template <class T> rational<T>
00370 operator -= (rational<T> & b, const rational<T> & c)
00371 {
00372 return b = b - c;
00373 }
00374
00375 template <class T> rational<T>
00376 operator *= (rational<T> & b, const rational<T> & c)
00377 {
00378 return b = b * c;
00379 }
00380
00381 template <class T> rational<T>
00382 operator /= (rational<T> & b, const rational<T> & c)
00383 {
00384 return b = b / c;
00385 }
00386
00387 template <class T> int rational<T>::sign() const
00388 {
00389 if (p ==T(0)) return 0;
00390 if (((p > T(0)) && (q > T(0))) || ((p < T(0)) && (q < T(0)))) return 1;
00391 return -1;
00392 }
00393
00394 template <class T>
00395 int cmp(const rational<T> & a, const rational<T> & b)
00396 {
00397 return (a - b).sign();
00398 }
00399
00400 template <class T> int
00401 operator < (const rational<T> & a, const rational<T> & b)
00402 {
00403 return cmp(a, b) == -1;
00404 }
00405
00406 template <class T>
00407 int operator == (const rational<T> & a, const rational<T> & b)
00408 {
00409 return cmp(a, b) == 0;
00410 }
00411
00412 template <class T>
00413 int operator != (const rational<T> & a, const rational<T> & b)
00414 {
00415 return cmp(a, b) != 0;
00416 }
00417
00418 template <class T>
00419 int operator > (const rational<T> & a, const rational<T> & b)
00420 {
00421 return cmp(a, b) == 1;
00422 }
00423
00424 template <class T>
00425 int operator >= (const rational<T> & a, const rational<T> & b)
00426 {
00427 return cmp(a, b) != -1;
00428 }
00429
00430 template <class T>
00431 int operator <= (const rational<T> & a, const rational<T> & b)
00432 {
00433 return cmp(a, b) != 1;
00434 }
00435
00436 template <class T>
00437 rational<T> operator + (const rational<T> & a)
00438 {
00439 return a;
00440 }
00441
00442 template <class T>
00443 rational<T> operator - (const rational<T> & b)
00444 {
00445 rational<T> a = b;
00446 a.p = -a.p;
00447 return a;
00448 }
00449
00450 template <class T> void rational<T>::
00451 optimize()
00452 {
00453 if (q < 0)
00454 {
00455 p = -p;
00456 q = -q;
00457 }
00458 T d = gcd(p, q);
00459 p = p / d;
00460 q = q / d;
00461 }
00462
00463 template <class T>
00464 rational<T> floor(const rational<T> & a)
00465 {
00466 return ifloor(a);
00467 }
00468
00469 template <class T>
00470 T ifloor(const rational<T> & a)
00471 {
00472 T result = a.p / a.q;
00473 if (a.p % a.q == 0)
00474 return result;
00475 if (a.p >= 0)
00476 return result;
00477 return result - 1;
00478 }
00479
00480 template <class T>
00481 rational<T> ceil(const rational<T> & a)
00482 {
00483 return iceil(a);
00484 }
00485
00486 template <class T>
00487 T iceil(const rational<T> & a)
00488 {
00489 T result = a.p / a.q;
00490 if (a.p % a.q == 0)
00491 return result;
00492 if (a.p < 0)
00493 return result;
00494 return result + 1;
00495 }
00496
00497 template <class T>
00498 rational<T> frac(const rational<T> & a)
00499 {
00500 return a - floor(a);
00501 }
00502
00503
00504
00505 #endif // RATIONAL_H_