(index<- ) ./libextra/num/rational.rs
1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 //! Rational numbers
12
13
14 use std::cmp;
15 use std::from_str::FromStr;
16 use std::num::{Zero,One,ToStrRadix,FromStrRadix,Round};
17 use super::bigint::BigInt;
18
19 /// Represents the ratio between 2 numbers.
20 #[deriving(Clone)]
21 #[allow(missing_doc)]
22 pub struct Ratio<T> {
23 numer: T,
24 denom: T
25 }
26
27 /// Alias for a `Ratio` of machine-sized integers.
28 pub type Rational = Ratio<int>;
29 pub type Rational32 = Ratio<i32>;
30 pub type Rational64 = Ratio<i64>;
31
32 /// Alias for arbitrary precision rationals.
33 pub type BigRational = Ratio<BigInt>;
34
35 impl<T: Clone + Integer + Ord>
36 Ratio<T> {
37 /// Create a ratio representing the integer `t`.
38 #[inline]
39 pub fn from_integer(t: T) -> Ratio<T> {
40 Ratio::new_raw(t, One::one())
41 }
42
43 /// Create a ratio without checking for `denom == 0` or reducing.
44 #[inline]
45 pub fn new_raw(numer: T, denom: T) -> Ratio<T> {
46 Ratio { numer: numer, denom: denom }
47 }
48
49 /// Create a new Ratio. Fails if `denom == 0`.
50 #[inline]
51 pub fn new(numer: T, denom: T) -> Ratio<T> {
52 if denom == Zero::zero() {
53 fail!("denominator == 0");
54 }
55 let mut ret = Ratio::new_raw(numer, denom);
56 ret.reduce();
57 ret
58 }
59
60 /// Put self into lowest terms, with denom > 0.
61 fn reduce(&mut self) {
62 let g : T = self.numer.gcd(&self.denom);
63
64 // FIXME(#6050): overloaded operators force moves with generic types
65 // self.numer /= g;
66 self.numer = self.numer / g;
67 // FIXME(#6050): overloaded operators force moves with generic types
68 // self.denom /= g;
69 self.denom = self.denom / g;
70
71 // keep denom positive!
72 if self.denom < Zero::zero() {
73 self.numer = -self.numer;
74 self.denom = -self.denom;
75 }
76 }
77
78 /// Return a `reduce`d copy of self.
79 fn reduced(&self) -> Ratio<T> {
80 let mut ret = self.clone();
81 ret.reduce();
82 ret
83 }
84 }
85
86 /* Comparisons */
87
88 // comparing a/b and c/d is the same as comparing a*d and b*c, so we
89 // abstract that pattern. The following macro takes a trait and either
90 // a comma-separated list of "method name -> return value" or just
91 // "method name" (return value is bool in that case)
92 macro_rules! cmp_impl {
93 (impl $imp:ident, $($method:ident),+) => {
94 cmp_impl!(impl $imp, $($method -> bool),+)
95 };
96 // return something other than a Ratio<T>
97 (impl $imp:ident, $($method:ident -> $res:ty),+) => {
98 impl<T: Mul<T,T> + $imp> $imp for Ratio<T> {
99 $(
100 #[inline]
101 fn $method(&self, other: &Ratio<T>) -> $res {
102 (self.numer * other.denom). $method (&(self.denom*other.numer))
103 }
104 )+
105 }
106 };
107 }
108 cmp_impl!(impl Eq, eq, ne)
109 cmp_impl!(impl TotalEq, equals)
110 cmp_impl!(impl Ord, lt, gt, le, ge)
111 cmp_impl!(impl TotalOrd, cmp -> cmp::Ordering)
112
113 impl<T: Clone + Integer + Ord> Orderable for Ratio<T> {
114 #[inline]
115 fn min(&self, other: &Ratio<T>) -> Ratio<T> {
116 if *self < *other { self.clone() } else { other.clone() }
117 }
118
119 #[inline]
120 fn max(&self, other: &Ratio<T>) -> Ratio<T> {
121 if *self > *other { self.clone() } else { other.clone() }
122 }
123
124 #[inline]
125 fn clamp(&self, mn: &Ratio<T>, mx: &Ratio<T>) -> Ratio<T> {
126 if *self > *mx { mx.clone()} else
127 if *self < *mn { mn.clone() } else { self.clone() }
128 }
129 }
130
131
132 /* Arithmetic */
133 // a/b * c/d = (a*c)/(b*d)
134 impl<T: Clone + Integer + Ord>
135 Mul<Ratio<T>,Ratio<T>> for Ratio<T> {
136 #[inline]
137 fn mul(&self, rhs: &Ratio<T>) -> Ratio<T> {
138 Ratio::new(self.numer * rhs.numer, self.denom * rhs.denom)
139 }
140 }
141
142 // (a/b) / (c/d) = (a*d)/(b*c)
143 impl<T: Clone + Integer + Ord>
144 Div<Ratio<T>,Ratio<T>> for Ratio<T> {
145 #[inline]
146 fn div(&self, rhs: &Ratio<T>) -> Ratio<T> {
147 Ratio::new(self.numer * rhs.denom, self.denom * rhs.numer)
148 }
149 }
150
151 // Abstracts the a/b `op` c/d = (a*d `op` b*d) / (b*d) pattern
152 macro_rules! arith_impl {
153 (impl $imp:ident, $method:ident) => {
154 impl<T: Clone + Integer + Ord>
155 $imp<Ratio<T>,Ratio<T>> for Ratio<T> {
156 #[inline]
157 fn $method(&self, rhs: &Ratio<T>) -> Ratio<T> {
158 Ratio::new((self.numer * rhs.denom).$method(&(self.denom * rhs.numer)),
159 self.denom * rhs.denom)
160 }
161 }
162 }
163 }
164
165 // a/b + c/d = (a*d + b*c)/(b*d
166 arith_impl!(impl Add, add)
167
168 // a/b - c/d = (a*d - b*c)/(b*d)
169 arith_impl!(impl Sub, sub)
170
171 // a/b % c/d = (a*d % b*c)/(b*d)
172 arith_impl!(impl Rem, rem)
173
174 impl<T: Clone + Integer + Ord>
175 Neg<Ratio<T>> for Ratio<T> {
176 #[inline]
177 fn neg(&self) -> Ratio<T> {
178 Ratio::new_raw(-self.numer, self.denom.clone())
179 }
180 }
181
182 /* Constants */
183 impl<T: Clone + Integer + Ord>
184 Zero for Ratio<T> {
185 #[inline]
186 fn zero() -> Ratio<T> {
187 Ratio::new_raw(Zero::zero(), One::one())
188 }
189
190 #[inline]
191 fn is_zero(&self) -> bool {
192 *self == Zero::zero()
193 }
194 }
195
196 impl<T: Clone + Integer + Ord>
197 One for Ratio<T> {
198 #[inline]
199 fn one() -> Ratio<T> {
200 Ratio::new_raw(One::one(), One::one())
201 }
202 }
203
204 impl<T: Clone + Integer + Ord>
205 Num for Ratio<T> {}
206
207 /* Utils */
208 impl<T: Clone + Integer + Ord>
209 Round for Ratio<T> {
210
211 fn floor(&self) -> Ratio<T> {
212 if *self < Zero::zero() {
213 Ratio::from_integer((self.numer - self.denom + One::one()) / self.denom)
214 } else {
215 Ratio::from_integer(self.numer / self.denom)
216 }
217 }
218
219 fn ceil(&self) -> Ratio<T> {
220 if *self < Zero::zero() {
221 Ratio::from_integer(self.numer / self.denom)
222 } else {
223 Ratio::from_integer((self.numer + self.denom - One::one()) / self.denom)
224 }
225 }
226
227 #[inline]
228 fn round(&self) -> Ratio<T> {
229 if *self < Zero::zero() {
230 Ratio::from_integer((self.numer - self.denom + One::one()) / self.denom)
231 } else {
232 Ratio::from_integer((self.numer + self.denom - One::one()) / self.denom)
233 }
234 }
235
236 #[inline]
237 fn trunc(&self) -> Ratio<T> {
238 Ratio::from_integer(self.numer / self.denom)
239 }
240
241 fn fract(&self) -> Ratio<T> {
242 Ratio::new_raw(self.numer % self.denom, self.denom.clone())
243 }
244 }
245
246 impl<T: Clone + Integer + Ord> Fractional for Ratio<T> {
247 #[inline]
248 fn recip(&self) -> Ratio<T> {
249 Ratio::new_raw(self.denom.clone(), self.numer.clone())
250 }
251 }
252
253 /* String conversions */
254 impl<T: ToStr> ToStr for Ratio<T> {
255 /// Renders as `numer/denom`.
256 fn to_str(&self) -> ~str {
257 fmt!("%s/%s", self.numer.to_str(), self.denom.to_str())
258 }
259 }
260 impl<T: ToStrRadix> ToStrRadix for Ratio<T> {
261 /// Renders as `numer/denom` where the numbers are in base `radix`.
262 fn to_str_radix(&self, radix: uint) -> ~str {
263 fmt!("%s/%s", self.numer.to_str_radix(radix), self.denom.to_str_radix(radix))
264 }
265 }
266
267 impl<T: FromStr + Clone + Integer + Ord>
268 FromStr for Ratio<T> {
269 /// Parses `numer/denom`.
270 fn from_str(s: &str) -> Option<Ratio<T>> {
271 let split: ~[&str] = s.splitn_iter('/', 1).collect();
272 if split.len() < 2 {
273 return None
274 }
275 let a_option: Option<T> = FromStr::from_str(split[0]);
276 do a_option.and_then |a| {
277 let b_option: Option<T> = FromStr::from_str(split[1]);
278 do b_option.and_then |b| {
279 Some(Ratio::new(a.clone(), b.clone()))
280 }
281 }
282 }
283 }
284 impl<T: FromStrRadix + Clone + Integer + Ord>
285 FromStrRadix for Ratio<T> {
286 /// Parses `numer/denom` where the numbers are in base `radix`.
287 fn from_str_radix(s: &str, radix: uint) -> Option<Ratio<T>> {
288 let split: ~[&str] = s.splitn_iter('/', 1).collect();
289 if split.len() < 2 {
290 None
291 } else {
292 let a_option: Option<T> = FromStrRadix::from_str_radix(split[0],
293 radix);
294 do a_option.and_then |a| {
295 let b_option: Option<T> =
296 FromStrRadix::from_str_radix(split[1], radix);
297 do b_option.and_then |b| {
298 Some(Ratio::new(a.clone(), b.clone()))
299 }
300 }
301 }
302 }
303 }
304
305 #[cfg(test)]
306 mod test {
307
308 use super::*;
309 use std::num::{Zero,One,FromStrRadix,IntConvertible};
310 use std::from_str::FromStr;
311
312 pub static _0 : Rational = Ratio { numer: 0, denom: 1};
313 pub static _1 : Rational = Ratio { numer: 1, denom: 1};
314 pub static _2: Rational = Ratio { numer: 2, denom: 1};
315 pub static _1_2: Rational = Ratio { numer: 1, denom: 2};
316 pub static _3_2: Rational = Ratio { numer: 3, denom: 2};
317 pub static _neg1_2: Rational = Ratio { numer: -1, denom: 2};
318
319 pub fn to_big(n: Rational) -> BigRational {
320 Ratio::new(
321 IntConvertible::from_int(n.numer),
322 IntConvertible::from_int(n.denom)
323 )
324 }
325
326 #[test]
327 fn test_test_constants() {
328 // check our constants are what Ratio::new etc. would make.
329 assert_eq!(_0, Zero::zero());
330 assert_eq!(_1, One::one());
331 assert_eq!(_2, Ratio::from_integer(2));
332 assert_eq!(_1_2, Ratio::new(1,2));
333 assert_eq!(_3_2, Ratio::new(3,2));
334 assert_eq!(_neg1_2, Ratio::new(-1,2));
335 }
336
337 #[test]
338 fn test_new_reduce() {
339 let one22 = Ratio::new(2i,2);
340
341 assert_eq!(one22, One::one());
342 }
343 #[test]
344 #[should_fail]
345 fn test_new_zero() {
346 let _a = Ratio::new(1,0);
347 }
348
349
350 #[test]
351 fn test_cmp() {
352 assert!(_0 == _0 && _1 == _1);
353 assert!(_0 != _1 && _1 != _0);
354 assert!(_0 < _1 && !(_1 < _0));
355 assert!(_1 > _0 && !(_0 > _1));
356
357 assert!(_0 <= _0 && _1 <= _1);
358 assert!(_0 <= _1 && !(_1 <= _0));
359
360 assert!(_0 >= _0 && _1 >= _1);
361 assert!(_1 >= _0 && !(_0 >= _1));
362 }
363
364
365 mod arith {
366 use super::*;
367 use super::super::*;
368
369
370 #[test]
371 fn test_add() {
372 fn test(a: Rational, b: Rational, c: Rational) {
373 assert_eq!(a + b, c);
374 assert_eq!(to_big(a) + to_big(b), to_big(c));
375 }
376
377 test(_1, _1_2, _3_2);
378 test(_1, _1, _2);
379 test(_1_2, _3_2, _2);
380 test(_1_2, _neg1_2, _0);
381 }
382
383 #[test]
384 fn test_sub() {
385 fn test(a: Rational, b: Rational, c: Rational) {
386 assert_eq!(a - b, c);
387 assert_eq!(to_big(a) - to_big(b), to_big(c))
388 }
389
390 test(_1, _1_2, _1_2);
391 test(_3_2, _1_2, _1);
392 test(_1, _neg1_2, _3_2);
393 }
394
395 #[test]
396 fn test_mul() {
397 fn test(a: Rational, b: Rational, c: Rational) {
398 assert_eq!(a * b, c);
399 assert_eq!(to_big(a) * to_big(b), to_big(c))
400 }
401
402 test(_1, _1_2, _1_2);
403 test(_1_2, _3_2, Ratio::new(3,4));
404 test(_1_2, _neg1_2, Ratio::new(-1, 4));
405 }
406
407 #[test]
408 fn test_div() {
409 fn test(a: Rational, b: Rational, c: Rational) {
410 assert_eq!(a / b, c);
411 assert_eq!(to_big(a) / to_big(b), to_big(c))
412 }
413
414 test(_1, _1_2, _2);
415 test(_3_2, _1_2, _1 + _2);
416 test(_1, _neg1_2, _neg1_2 + _neg1_2 + _neg1_2 + _neg1_2);
417 }
418
419 #[test]
420 fn test_rem() {
421 fn test(a: Rational, b: Rational, c: Rational) {
422 assert_eq!(a % b, c);
423 assert_eq!(to_big(a) % to_big(b), to_big(c))
424 }
425
426 test(_3_2, _1, _1_2);
427 test(_2, _neg1_2, _0);
428 test(_1_2, _2, _1_2);
429 }
430
431 #[test]
432 fn test_neg() {
433 fn test(a: Rational, b: Rational) {
434 assert_eq!(-a, b);
435 assert_eq!(-to_big(a), to_big(b))
436 }
437
438 test(_0, _0);
439 test(_1_2, _neg1_2);
440 test(-_1, _1);
441 }
442 #[test]
443 fn test_zero() {
444 assert_eq!(_0 + _0, _0);
445 assert_eq!(_0 * _0, _0);
446 assert_eq!(_0 * _1, _0);
447 assert_eq!(_0 / _neg1_2, _0);
448 assert_eq!(_0 - _0, _0);
449 }
450 #[test]
451 #[should_fail]
452 fn test_div_0() {
453 let _a = _1 / _0;
454 }
455 }
456
457 #[test]
458 fn test_round() {
459 assert_eq!(_1_2.ceil(), _1);
460 assert_eq!(_1_2.floor(), _0);
461 assert_eq!(_1_2.round(), _1);
462 assert_eq!(_1_2.trunc(), _0);
463
464 assert_eq!(_neg1_2.ceil(), _0);
465 assert_eq!(_neg1_2.floor(), -_1);
466 assert_eq!(_neg1_2.round(), -_1);
467 assert_eq!(_neg1_2.trunc(), _0);
468
469 assert_eq!(_1.ceil(), _1);
470 assert_eq!(_1.floor(), _1);
471 assert_eq!(_1.round(), _1);
472 assert_eq!(_1.trunc(), _1);
473 }
474
475 #[test]
476 fn test_fract() {
477 assert_eq!(_1.fract(), _0);
478 assert_eq!(_neg1_2.fract(), _neg1_2);
479 assert_eq!(_1_2.fract(), _1_2);
480 assert_eq!(_3_2.fract(), _1_2);
481 }
482
483 #[test]
484 fn test_recip() {
485 assert_eq!(_1 * _1.recip(), _1);
486 assert_eq!(_2 * _2.recip(), _1);
487 assert_eq!(_1_2 * _1_2.recip(), _1);
488 assert_eq!(_3_2 * _3_2.recip(), _1);
489 assert_eq!(_neg1_2 * _neg1_2.recip(), _1);
490 }
491
492 #[test]
493 fn test_to_from_str() {
494 fn test(r: Rational, s: ~str) {
495 assert_eq!(FromStr::from_str(s), Some(r));
496 assert_eq!(r.to_str(), s);
497 }
498 test(_1, ~"1/1");
499 test(_0, ~"0/1");
500 test(_1_2, ~"1/2");
501 test(_3_2, ~"3/2");
502 test(_2, ~"2/1");
503 test(_neg1_2, ~"-1/2");
504 }
505 #[test]
506 fn test_from_str_fail() {
507 fn test(s: &str) {
508 let rational: Option<Rational> = FromStr::from_str(s);
509 assert_eq!(rational, None);
510 }
511
512 let xs = ["0 /1", "abc", "", "1/", "--1/2","3/2/1"];
513 for &s in xs.iter() {
514 test(s);
515 }
516 }
517
518 #[test]
519 fn test_to_from_str_radix() {
520 fn test(r: Rational, s: ~str, n: uint) {
521 assert_eq!(FromStrRadix::from_str_radix(s, n), Some(r));
522 assert_eq!(r.to_str_radix(n), s);
523 }
524 fn test3(r: Rational, s: ~str) { test(r, s, 3) }
525 fn test16(r: Rational, s: ~str) { test(r, s, 16) }
526
527 test3(_1, ~"1/1");
528 test3(_0, ~"0/1");
529 test3(_1_2, ~"1/2");
530 test3(_3_2, ~"10/2");
531 test3(_2, ~"2/1");
532 test3(_neg1_2, ~"-1/2");
533 test3(_neg1_2 / _2, ~"-1/11");
534
535 test16(_1, ~"1/1");
536 test16(_0, ~"0/1");
537 test16(_1_2, ~"1/2");
538 test16(_3_2, ~"3/2");
539 test16(_2, ~"2/1");
540 test16(_neg1_2, ~"-1/2");
541 test16(_neg1_2 / _2, ~"-1/4");
542 test16(Ratio::new(13,15), ~"d/f");
543 test16(_1_2*_1_2*_1_2*_1_2, ~"1/10");
544 }
545
546 #[test]
547 fn test_from_str_radix_fail() {
548 fn test(s: &str) {
549 let radix: Option<Rational> = FromStrRadix::from_str_radix(s, 3);
550 assert_eq!(radix, None);
551 }
552
553 let xs = ["0 /1", "abc", "", "1/", "--1/2","3/2/1", "3/2"];
554 for &s in xs.iter() {
555 test(s);
556 }
557 }
558 }
libextra/num/rational.rs:21:22-21:22 -struct- definition:
#[allow(missing_doc)]
pub struct Ratio<T> {
references:-285: FromStrRadix for Ratio<T> {
20: #[deriving(Clone)]
20: #[deriving(Clone)]
219: fn ceil(&self) -> Ratio<T> {
287: fn from_str_radix(s: &str, radix: uint) -> Option<Ratio<T>> {
20: #[deriving(Clone)]
20: #[deriving(Clone)]
45: pub fn new_raw(numer: T, denom: T) -> Ratio<T> {
205: Num for Ratio<T> {}
39: pub fn from_integer(t: T) -> Ratio<T> {
155: $imp<Ratio<T>,Ratio<T>> for Ratio<T> {
155: $imp<Ratio<T>,Ratio<T>> for Ratio<T> {
98: impl<T: Mul<T,T> + $imp> $imp for Ratio<T> {
209: Round for Ratio<T> {
115: fn min(&self, other: &Ratio<T>) -> Ratio<T> {
197: One for Ratio<T> {
125: fn clamp(&self, mn: &Ratio<T>, mx: &Ratio<T>) -> Ratio<T> {
155: $imp<Ratio<T>,Ratio<T>> for Ratio<T> {
98: impl<T: Mul<T,T> + $imp> $imp for Ratio<T> {
186: fn zero() -> Ratio<T> {
101: fn $method(&self, other: &Ratio<T>) -> $res {
51: pub fn new(numer: T, denom: T) -> Ratio<T> {
101: fn $method(&self, other: &Ratio<T>) -> $res {
146: fn div(&self, rhs: &Ratio<T>) -> Ratio<T> {
33: pub type BigRational = Ratio<BigInt>;
125: fn clamp(&self, mn: &Ratio<T>, mx: &Ratio<T>) -> Ratio<T> {
120: fn max(&self, other: &Ratio<T>) -> Ratio<T> {
184: Zero for Ratio<T> {
135: Mul<Ratio<T>,Ratio<T>> for Ratio<T> {
30: pub type Rational64 = Ratio<i64>;
(120)(101)(155)(157)(248)(228)(98)(157)(29)(254)(101)(115)(155)(146)(101)(155)(155)(137)(79)(137)(125)(155)(260)(270)(175)(135)(144)(199)(155)(101)(157)(175)(144)(246)(241)(144)(98)(101)(157)(157)(268)(237)(157)(36)(211)(28)(113)(177)(135)(101)(46)