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