Line data Source code
1 : /**
2 : * @file rational.h
3 : * @author Essam A. El-Sherif
4 : * @version v1.0.0
5 : *
6 : * A C++ header that defines a template based class 'rational' for representing and manipulating rational numbers.
7 : */
8 :
9 : #ifndef __RATIONAL_H__
10 : #define __RATIONAL_H__
11 :
12 : #include <iomanip>
13 : #include <iostream>
14 : #include <sstream>
15 : #include <stdexcept>
16 : #include <cassert>
17 : #include <limits>
18 :
19 : /**
20 : * A namespace to enclose the C++ rational class and global helper classes and functions.
21 : */
22 : namespace src{
23 : /**
24 : * An exception class for bad rationals.
25 : */
26 : class bad_rational : public std::domain_error{
27 : public:
28 : /** Default constructor. */
29 6 : explicit bad_rational() : std::domain_error("bad rational: zero denominator"){}
30 :
31 : /** One argument constructor. */
32 0 : explicit bad_rational(const char *what) : std::domain_error(what){}
33 : };
34 :
35 : /**
36 : * A template based class for representing and manipulating rational numbers.
37 : */
38 : template<typename I>
39 : class rational{
40 : private: /* Helper static functions [3] */
41 :
42 : /** Greatest common divisor. */
43 0 : static I inner_gcd(I, I, const I& = I(0));
44 :
45 : /** Absolute value. */
46 0 : static I inner_abs(I, const I& = I(0));
47 :
48 : /** Inspect the two given parameters are in normalized form. */
49 0 : static bool is_normalized(I, I, const I& = I(0), const I& = I(1));
50 :
51 : private: /* Helper member functions [2] */
52 :
53 : /** Normalize the rational number i.e. no common factors and denominator is positive. */
54 : void normalize();
55 :
56 : /** Light test of normalized rational number. */
57 : bool test_invariant()const;
58 :
59 : private:
60 : I num; /**< Numerator (normalized).*/
61 : I den; /**< Denominator (normalized).*/
62 :
63 : public:
64 : /* Constructors [4] */
65 : rational(); /**< Default constructor. */
66 : rational(I); /**< One argument constructor. */
67 : rational(I, I); /**< Two arguments constructor. */
68 :
69 : template<typename J>
70 : explicit rational(const rational<J>&); /**< Copy constructor. */
71 :
72 : /* Access to representation [2] */
73 180 : const I& numerator() const { return num; } /**< Get numerator. */
74 172 : const I& denominator() const { return den; } /**< Get denominator. */
75 :
76 : /* Assignment [2] */
77 : rational& operator =(const I&); /**< Assignment from Int type. */
78 : rational& assign(const I&, const I&); /**< Assignment in place. */
79 :
80 : /* Arithmetic assignment operators [8] */
81 : rational& operator +=(const rational<I>&); /**< Arithmetic assignment operator += */
82 : rational& operator -=(const rational<I>&); /**< Arithmetic assignment operator -= */
83 : rational& operator *=(const rational<I>&); /**< Arithmetic assignment operator *= */
84 : rational& operator /=(const rational<I>&); /**< Arithmetic assignment operator /= */
85 :
86 : rational& operator +=(const I&); /**< Arithmetic assignment operator += from int type. */
87 : rational& operator -=(const I&); /**< Arithmetic assignment operator -= from int type. */
88 : rational& operator *=(const I&); /**< Arithmetic assignment operator *= from int type. */
89 : rational& operator /=(const I&); /**< Arithmetic assignment operator /= from int type. */
90 :
91 : /* Increment and decrement operators [4] */
92 : rational& operator ++(); /**< Pre-increment operator. */
93 : rational& operator --(); /**< Pre-decrement operator. */
94 :
95 : rational operator ++(int); /**< Post-increment operator. */
96 : rational operator --(int); /**< Post-decrement operator. */
97 :
98 : /* Operator not [1] */
99 : bool operator !() const; /**< Not operator. */
100 :
101 : /* Boolean conversion [1] */
102 : operator bool () const; /**< Boolean conversion. */
103 :
104 : /* Comparison operators [4] */
105 : bool operator <(const rational&) const; /**< Comparison operator < */
106 : bool operator >(const rational&) const; /**< Comparison operator < */
107 : bool operator ==(const rational&) const; /**< Comparison operator == */
108 : bool operator !=(const rational&) const; /**< Comparison operator != */
109 :
110 : /* Comparison with integers [4] */
111 : bool operator <(const I&) const; /**< Comparison operator < int type. */
112 : bool operator >(const I&) const; /**< Comparison operator > int type. */
113 : bool operator ==(const I&) const; /**< Comparison operator == int type. */
114 : bool operator !=(const I&) const; /**< Comparison operator != int type. */
115 : };
116 :
117 : /* Global unary operators [2] */
118 : template<typename I>
119 : rational<I> operator +(const rational<I>&); /**< Unary operator + */
120 :
121 : template<typename I>
122 : rational<I> operator -(const rational<I>&); /**< Unary operator - */
123 :
124 : /* Global binary operators [12] */
125 : template<typename I>
126 : rational<I> operator +(const rational<I>&, const rational<I>&);
127 :
128 : template<typename I>
129 : rational<I> operator +(const rational<I>&, const I&);
130 :
131 : template<typename I>
132 : rational<I> operator +(const I&, const rational<I>&);
133 :
134 : template<typename I>
135 : rational<I> operator -(const rational<I>&, const rational<I>&);
136 :
137 : template<typename I>
138 : rational<I> operator -(const rational<I>&, const I&);
139 :
140 : template<typename I>
141 : rational<I> operator -(const I&, const rational<I>&);
142 :
143 : template<typename I>
144 : rational<I> operator *(const rational<I>&, const rational<I>&);
145 :
146 : template<typename I>
147 : rational<I> operator *(const rational<I>&, const I&);
148 :
149 : template<typename I>
150 : rational<I> operator *(const I&, const rational<I>&);
151 :
152 : template<typename I>
153 : rational<I> operator /(const rational<I>&, const rational<I>&);
154 :
155 : template<typename I>
156 : rational<I> operator /(const rational<I>&, const I&);
157 :
158 : template<typename I>
159 : rational<I> operator /(const I&, const rational<I>&);
160 :
161 : /* Global absolute value function [1] */
162 : template<typename I>
163 : rational<I> abs(const rational<I>&);
164 :
165 : /* Global input and output operators [2] */
166 : template<typename I>
167 : std::istream& operator >>(std::istream&, rational<I>&);
168 :
169 : template<typename I>
170 : std::ostream& operator <<(std::ostream&, const rational<I>&);
171 :
172 : /* Global type conversion function [1] */
173 : template<typename T, typename I>
174 : T rational_cast(const rational<I>& r);
175 : }
176 :
177 : /* Constructors [4] */
178 : template<typename I>
179 34 : src::rational<I>::rational() : num(0), den(1){}
180 :
181 : template<typename I>
182 44 : src::rational<I>::rational(I n) : num(n), den(1){}
183 :
184 : template<typename I>
185 124 : src::rational<I>::rational(I n, I d) : num(n), den(d){
186 124 : normalize();
187 122 : }
188 :
189 : template<typename I>
190 : template<typename J>
191 2 : src::rational<I>::rational(const src::rational<J>& r){
192 2 : if(is_normalized(
193 2 : I(r.numerator()),
194 2 : I(r.denominator())
195 : )
196 : ){
197 2 : num = r.numerator();
198 2 : den = r.denominator();
199 : }
200 : else{
201 0 : throw bad_rational("bad rational: denormalized conversion");
202 : }
203 2 : }
204 :
205 : /* Helper static functions [3] */
206 : template<typename I>
207 770 : I src::rational<I>::inner_gcd(I a, I b, const I& zero){
208 770 : return b == zero ? a : inner_gcd(b, a % b, zero);
209 : }
210 :
211 : template<typename I>
212 300 : I src::rational<I>::inner_abs(I x, const I& zero){
213 300 : return x < zero ? -x : +x;
214 : }
215 :
216 : template<typename I>
217 2 : bool src::rational<I>::is_normalized(I n, I d, const I& zero, const I& one){
218 : return
219 4 : d > zero &&
220 4 : (n != zero || d == one) &&
221 4 : inner_abs( inner_gcd(n, d, zero), zero ) == one;
222 : }
223 :
224 : /* Helper member functions [2] */
225 : template<typename I>
226 124 : void src::rational<I>::normalize(){
227 124 : I zero(0);
228 :
229 124 : if(den == zero) throw bad_rational();
230 :
231 122 : if(num == zero){
232 10 : den = I(1);
233 10 : return;
234 : }
235 :
236 112 : I g = inner_abs( inner_gcd(num, den) );
237 :
238 112 : num /= g;
239 112 : den /= g;
240 :
241 112 : if(den < -(std::numeric_limits<I>::max)()){
242 0 : throw bad_rational("bad rational: non-zero singular denominator");
243 : }
244 :
245 112 : if(den < zero){
246 14 : num = -num;
247 14 : den = -den;
248 : }
249 :
250 112 : assert(test_invariant());
251 : }
252 :
253 : template<typename I>
254 112 : bool src::rational<I>::test_invariant()const{
255 : return
256 224 : this->den > I(0) &&
257 224 : inner_abs( inner_gcd(this->num, this->den) ) == I(1);
258 : }
259 :
260 : /* Assignment [2] */
261 : template<typename I>
262 40 : src::rational<I>& src::rational<I>::operator =(const I& n){
263 40 : return assign( static_cast<I>(n), static_cast<I>(1) );
264 : }
265 :
266 : template<typename I>
267 42 : src::rational<I>& src::rational<I>::assign(const I& n, const I& d){
268 42 : return *this = rational<I>( static_cast<I>(n), static_cast<I>(d) );
269 : }
270 :
271 : /* Arithmetic assignment operators [8] */
272 : template<typename I>
273 8 : src::rational<I>& src::rational<I>::operator +=(const rational& r){
274 8 : I r_num = r.numerator();
275 8 : I r_den = r.denominator();
276 :
277 8 : I g = inner_gcd(den, r_den);
278 :
279 8 : den /= g;
280 8 : num = num * (r_den / g) + r_num * den;
281 :
282 8 : g = inner_abs( inner_gcd(num, g) );
283 8 : num /= g;
284 8 : den *= r_den/g;
285 :
286 8 : return *this;
287 : }
288 :
289 : template<typename I>
290 6 : src::rational<I>& src::rational<I>::operator -=(const rational& r){
291 6 : I r_num = r.numerator();
292 6 : I r_den = r.denominator();
293 :
294 6 : I g = inner_gcd(den, r_den);
295 :
296 6 : den /= g;
297 6 : num = num * (r_den / g) - r_num * den;
298 :
299 6 : g = inner_abs( inner_gcd(num, g) );
300 6 : num /= g;
301 6 : den *= r_den/g;
302 :
303 6 : return *this;
304 : }
305 :
306 : template<typename I>
307 6 : src::rational<I>& src::rational<I>::operator *=(const rational& r){
308 6 : I r_num = r.num;
309 6 : I r_den = r.den;
310 :
311 6 : I gcd1 = inner_abs( inner_gcd(num, r_den) );
312 6 : I gcd2 = inner_abs( inner_gcd(r_num, den) );
313 :
314 6 : num = (num/gcd1) * (r_num/gcd2);
315 6 : den = (den/gcd2) * (r_den/gcd1);
316 :
317 6 : return *this;
318 : }
319 :
320 : template<typename I>
321 24 : src::rational<I>& src::rational<I>::operator /=(const rational& r){
322 24 : I r_num = r.num;
323 24 : I r_den = r.den;
324 :
325 24 : I zero(0);
326 :
327 24 : if(r_num == zero){
328 2 : throw bad_rational();
329 : }
330 :
331 22 : if(num == zero){
332 8 : return *this;
333 : }
334 :
335 14 : I gcd1 = inner_abs( inner_gcd(num, r_num) );
336 14 : I gcd2 = inner_abs( inner_gcd(r_den, den) );
337 :
338 14 : num = (num/gcd1) * (r_den/gcd2);
339 14 : den = (den/gcd2) * (r_num/gcd1);
340 :
341 14 : if(den < zero){
342 2 : num = -num;
343 2 : den = -den;
344 : }
345 :
346 14 : return *this;
347 : }
348 :
349 : template<typename I>
350 8 : src::rational<I>& src::rational<I>::operator +=(const I& i){
351 8 : num += i * den;
352 8 : return *this;
353 : }
354 :
355 : template<typename I>
356 8 : src::rational<I>& src::rational<I>::operator -=(const I& i){
357 8 : num -= i * den;
358 8 : return *this;
359 : }
360 :
361 : template<typename I>
362 14 : src::rational<I>& src::rational<I>::operator *=(const I& i){
363 14 : I gcd = inner_abs( inner_gcd( static_cast<I>(i), den ) );
364 14 : num *= i / gcd;
365 14 : den /= gcd;
366 14 : return *this;
367 : }
368 :
369 : template<typename I>
370 14 : src::rational<I>& src::rational<I>::operator /=(const I& i){
371 14 : const I zero(0);
372 :
373 14 : if(i == zero) throw bad_rational();
374 12 : if(num == zero) return *this;
375 :
376 6 : const I gcd = inner_abs( inner_gcd(num, static_cast<I>(i)) );
377 6 : num /= gcd;
378 6 : den *= i / gcd;
379 :
380 6 : if(den < zero){
381 2 : num = -num;
382 2 : den = -den;
383 : }
384 :
385 6 : return *this;
386 : }
387 :
388 : /* Increment and decrement operators [4] */
389 : template<typename I>
390 4 : src::rational<I>& src::rational<I>::operator ++(){
391 4 : num += den;
392 4 : return *this;
393 : }
394 :
395 : template<typename I>
396 4 : src::rational<I>& src::rational<I>::operator --(){
397 4 : num -= den;
398 4 : return *this;
399 : }
400 :
401 : template<typename I>
402 2 : src::rational<I> src::rational<I>::operator ++(int){
403 2 : rational t(*this);
404 2 : ++(*this);
405 2 : return t;
406 : }
407 :
408 : template<typename I>
409 2 : src::rational<I> src::rational<I>::operator --(int){
410 2 : rational t(*this);
411 2 : --(*this);
412 2 : return t;
413 : }
414 :
415 : /* Operator not [1] */
416 : template<typename I>
417 4 : bool src::rational<I>::operator !() const{
418 4 : return !num;
419 : }
420 :
421 : /* Boolean conversion [1] */
422 : template<typename I>
423 2 : src::rational<I>::operator bool() const{
424 2 : return static_cast<bool>(num);
425 : }
426 :
427 : /* Comparison operators [4] */
428 : template<typename I>
429 4 : bool src::rational<I>::operator <(const rational& r) const{
430 4 : const I zero(0);
431 :
432 4 : assert( this->den > zero );
433 4 : assert( r.den > zero );
434 :
435 : struct{
436 : I n, d, q, r;
437 : }
438 4 : ts = {
439 4 : this->num,
440 4 : this->den,
441 4 : static_cast<I>( this->num / this->den ),
442 4 : static_cast<I>( this->num % this->den )
443 : },
444 4 : rs = {
445 4 : r.num,
446 4 : r.den,
447 4 : static_cast<I>(r.num / r.den),
448 4 : static_cast<I>(r.num % r.den)
449 : };
450 :
451 4 : unsigned int reverse = 0u;
452 :
453 4 : while (ts.r < zero){ ts.r += ts.d; --ts.q; }
454 4 : while (rs.r < zero){ rs.r += rs.d; --rs.q; }
455 :
456 : for( ;; ){
457 4 : if(ts.q != rs.q){
458 4 : return reverse ? ts.q > rs.q : ts.q < rs.q;
459 : }
460 :
461 0 : reverse ^= 1u;
462 :
463 0 : if(ts.r == zero || rs.r == zero){
464 : break;
465 : }
466 :
467 0 : ts.n = ts.d; ts.d = ts.r;
468 0 : ts.q = ts.n / ts.d; ts.r = ts.n % ts.d;
469 0 : rs.n = rs.d; rs.d = rs.r;
470 0 : rs.q = rs.n / rs.d; rs.r = rs.n % rs.d;
471 : }
472 :
473 0 : if(ts.r == rs.r){
474 0 : return false;
475 : }
476 : else{
477 0 : return ( ts.r != zero ) != static_cast<bool>( reverse );
478 : }
479 : }
480 :
481 : template<typename I>
482 : bool src::rational<I>::operator >(const rational& r) const{
483 : return !(*this < r || *this == r);
484 : }
485 :
486 : template<typename I>
487 66 : bool src::rational<I>::operator ==(const rational& r) const{
488 66 : return (num == r.numerator() && den == r.denominator());
489 : }
490 :
491 : template<typename I>
492 4 : bool src::rational<I>::operator !=(const rational& r) const{
493 4 : return (num != r.numerator() || den != r.denominator());
494 : }
495 :
496 : /* Comparison with integers [4] */
497 : template<typename I>
498 8 : bool src::rational<I>::operator <(const I& i) const{
499 8 : const I zero(0);
500 :
501 8 : assert(this->den > zero);
502 8 : I q = this->num / this->den;
503 8 : I r = this->num % this->den;
504 8 : while(r < zero){ r += this->den; --q; }
505 :
506 8 : return q < i;
507 : }
508 :
509 : template<typename I>
510 4 : bool src::rational<I>::operator >(const I& i) const{
511 4 : return operator ==(i) ? false : !(operator <(i));
512 : }
513 :
514 : template<typename I>
515 18 : bool src::rational<I>::operator ==(const I& i) const{
516 18 : return ((den == I(1)) && (num == i));
517 : }
518 :
519 : template<typename I>
520 : bool src::rational<I>::operator !=(const I& i) const{
521 : return ((den != I(1)) || (num != i));
522 : }
523 :
524 : /* Global unary operators [2] */
525 : template<typename I>
526 8 : inline src::rational<I> src::operator +(const rational<I>& r){
527 8 : return r;
528 : }
529 :
530 : template<typename I>
531 24 : inline src::rational<I> src::operator -(const rational<I>& r){
532 24 : return rational<I>( static_cast<I>(-r.numerator()), r.denominator() );
533 : }
534 :
535 : /* Global binary operators [12] */
536 : template<typename I>
537 6 : inline src::rational<I> src::operator+ (const rational<I>& a, const rational<I>& b){
538 6 : rational<I> t(a);
539 6 : t += b;
540 6 : return t;
541 : }
542 :
543 : template<typename I>
544 4 : inline src::rational<I> src::operator+ (const rational<I>& r, const I& i){
545 4 : rational<I> t(r);
546 4 : t += i;
547 4 : return t;
548 : }
549 :
550 : template<typename I>
551 2 : inline src::rational<I> src::operator+ (const I& i, const rational<I>& r){
552 2 : rational<I> t(r);
553 2 : t += i;
554 2 : return t;
555 : }
556 :
557 : template<typename I>
558 4 : inline src::rational<I> src::operator- (const rational<I>& a, const rational<I>& b){
559 4 : rational<I> t(a);
560 4 : t -= b;
561 4 : return t;
562 : }
563 :
564 : template<typename I>
565 4 : inline src::rational<I> src::operator- (const rational<I>& r, const I& i){
566 4 : rational<I> t(r);
567 4 : t -= i;
568 4 : return t;
569 : }
570 :
571 : template<typename I>
572 2 : inline src::rational<I> src::operator- (const I& i, const rational<I>& r){
573 2 : rational<I> t(r);
574 2 : t -= i;
575 4 : return -t;
576 : }
577 :
578 : template<typename I>
579 4 : inline src::rational<I> src::operator* (const rational<I>& a, const rational<I>& b){
580 4 : rational<I> t(a);
581 4 : t *= b;
582 4 : return t;
583 : }
584 :
585 : template<typename I>
586 4 : inline src::rational<I> src::operator* (const rational<I>& r, const I& i){
587 4 : rational<I> t(r);
588 4 : t *= i;
589 4 : return t;
590 : }
591 :
592 : template<typename I>
593 8 : inline src::rational<I> src::operator* (const I& i, const rational<I>& r){
594 8 : rational<I> t(r);
595 8 : t *= i;
596 8 : return t;
597 : }
598 :
599 : template<typename I>
600 10 : inline src::rational<I> src::operator/ (const rational<I>& a, const rational<I>& b){
601 10 : rational<I> t(a);
602 10 : t /= b;
603 10 : return t;
604 : }
605 :
606 : template<typename I>
607 8 : inline src::rational<I> src::operator/ (const rational<I>& r, const I& i){
608 8 : rational<I> t(r);
609 8 : t /= i;
610 8 : return t;
611 : }
612 :
613 : template<typename I>
614 6 : inline src::rational<I> src::operator/ (const I& i, const rational<I>& r){
615 6 : rational<I> t(i);
616 6 : t /= r;
617 6 : return t;
618 : }
619 :
620 : /* Global absolute value function [1] */
621 : template<typename I>
622 4 : inline src::rational<I> src::abs(const rational<I>& r){
623 4 : return r.numerator() >= I(0) ? r : -r;
624 : }
625 :
626 : /* Global input and output operators [2] */
627 : template<typename I>
628 : std::istream& src::operator >>(std::istream& is, rational<I>& r){
629 : using std::ios;
630 :
631 : I n = I(0), d = I(1);
632 : char c = 0;
633 :
634 : if( is >> n ){
635 : if( is.get(c) ){
636 : if( c == '/' ){
637 : if( is >> std::noskipws >> d )
638 : try{
639 : r.assign( n, d );
640 : }
641 : catch( bad_rational & ){
642 : try{
643 : is.setstate(ios::failbit);
644 : }
645 : catch( ... ) {}
646 :
647 : if( is.exceptions() & ios::failbit )
648 : throw;
649 : }
650 : }
651 : else{
652 : is.setstate( ios::failbit );
653 : }
654 : }
655 : }
656 :
657 : return is;
658 : }
659 :
660 : template<typename I>
661 : std::ostream& src::operator <<(std::ostream& os, const rational<I>& r){
662 : std::ostringstream ss;
663 :
664 : ss.copyfmt( os );
665 : ss.tie( NULL );
666 : ss.exceptions( std::ios::goodbit );
667 : ss.width( 0 );
668 : ss << std::noshowpos << std::noshowbase << '/' << r.denominator();
669 :
670 : const std::string tail = ss.str();
671 : std::streamsize const w =
672 : os.width() - static_cast<std::streamsize>( tail.size() );
673 :
674 : ss.clear();
675 : ss.str( "" );
676 : ss.flags( os.flags() );
677 : ss << std::setw( w < 0 || (os.flags() & std::ios::adjustfield) !=
678 : std::ios::internal ? 0 : w ) << r.numerator();
679 : return os << ss.str() + tail;
680 : }
681 :
682 : /* Global type conversion function [1] */
683 : template<typename T, typename I>
684 2 : inline T src::rational_cast(const rational<I>& r){
685 :
686 2 : return static_cast<T>(r.numerator()) / static_cast<T>(r.denominator());
687 : }
688 :
689 : #endif
|
