src/libextra/num/rational.rs - third_party/rust - Git at Google

 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
 // file at the top-level directory of this distribution and at
 // http://rust-lang.org/COPYRIGHT.
 //
 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.

 //! Rational numbers


 use std::cmp;
 use std::from_str::FromStr;
 use std::num::{Zero,One,ToStrRadix,FromStrRadix,Round};
 use super::bigint::BigInt;

 /// Represents the ratio between 2 numbers.
 #[deriving(Clone)]
 #[allow(missing_doc)]
 pub struct Ratio<T> {
     numer: T,
     denom: T
 }

 /// Alias for a `Ratio` of machine-sized integers.
 pub type Rational = Ratio<int>;
 pub type Rational32 = Ratio<i32>;
 pub type Rational64 = Ratio<i64>;

 /// Alias for arbitrary precision rationals.
 pub type BigRational = Ratio<BigInt>;

 impl<T: Clone + Integer + Ord>
     Ratio<T> {
     /// Create a ratio representing the integer `t`.
     #[inline]
     pub fn from_integer(t: T) -> Ratio<T> {
         Ratio::new_raw(t, One::one())
     }

     /// Create a ratio without checking for `denom == 0` or reducing.
     #[inline]
     pub fn new_raw(numer: T, denom: T) -> Ratio<T> {
         Ratio { numer: numer, denom: denom }
     }

     /// Create a new Ratio. Fails if `denom == 0`.
     #[inline]
     pub fn new(numer: T, denom: T) -> Ratio<T> {
         if denom == Zero::zero() {
             fail!("denominator == 0");
         }
         let mut ret = Ratio::new_raw(numer, denom);
         ret.reduce();
         ret
     }

     /// Put self into lowest terms, with denom > 0.
     fn reduce(&mut self) {
         let g : T = self.numer.gcd(&self.denom);

         // FIXME(#6050): overloaded operators force moves with generic types
         // self.numer /= g;
         self.numer = self.numer / g;
         // FIXME(#6050): overloaded operators force moves with generic types
         // self.denom /= g;
         self.denom = self.denom / g;

         // keep denom positive!
         if self.denom < Zero::zero() {
             self.numer = -self.numer;
             self.denom = -self.denom;
         }
     }

     /// Return a `reduce`d copy of self.
     fn reduced(&self) -> Ratio<T> {
         let mut ret = self.clone();
         ret.reduce();
         ret
     }
 }

 /* Comparisons */

 // comparing a/b and c/d is the same as comparing a*d and b*c, so we
 // abstract that pattern. The following macro takes a trait and either
 // a comma-separated list of "method name -> return value" or just
 // "method name" (return value is bool in that case)
 macro_rules! cmp_impl {
     (impl $imp:ident, $($method:ident),+) => {
         cmp_impl!(impl $imp, $($method -> bool),+)
     };
     // return something other than a Ratio<T>
     (impl $imp:ident, $($method:ident -> $res:ty),+) => {
         impl<T: Mul<T,T> + $imp> $imp for Ratio<T> {
             $(
                 #[inline]
                 fn $method(&self, other: &Ratio<T>) -> $res {
                     (self.numer * other.denom). $method (&(self.denom*other.numer))
                 }
             )+
         }
     };
 }
 cmp_impl!(impl Eq, eq, ne)
 cmp_impl!(impl TotalEq, equals)
 cmp_impl!(impl Ord, lt, gt, le, ge)
 cmp_impl!(impl TotalOrd, cmp -> cmp::Ordering)

 impl<T: Clone + Integer + Ord> Orderable for Ratio<T> {
     #[inline]
     fn min(&self, other: &Ratio<T>) -> Ratio<T> {
         if *self < *other { self.clone() } else { other.clone() }
     }

     #[inline]
     fn max(&self, other: &Ratio<T>) -> Ratio<T> {
         if *self > *other { self.clone() } else { other.clone() }
     }

     #[inline]
     fn clamp(&self, mn: &Ratio<T>, mx: &Ratio<T>) -> Ratio<T> {
         if *self > *mx { mx.clone()} else
         if *self < *mn { mn.clone() } else { self.clone() }
     }
 }


 /* Arithmetic */
 // a/b * c/d = (a*c)/(b*d)
 impl<T: Clone + Integer + Ord>
     Mul<Ratio<T>,Ratio<T>> for Ratio<T> {
     #[inline]
     fn mul(&self, rhs: &Ratio<T>) -> Ratio<T> {
         Ratio::new(self.numer * rhs.numer, self.denom * rhs.denom)
     }
 }

 // (a/b) / (c/d) = (a*d)/(b*c)
 impl<T: Clone + Integer + Ord>
     Div<Ratio<T>,Ratio<T>> for Ratio<T> {
     #[inline]
     fn div(&self, rhs: &Ratio<T>) -> Ratio<T> {
         Ratio::new(self.numer * rhs.denom, self.denom * rhs.numer)
     }
 }

 // Abstracts the a/b `op` c/d = (a*d `op` b*d) / (b*d) pattern
 macro_rules! arith_impl {
     (impl $imp:ident, $method:ident) => {
         impl<T: Clone + Integer + Ord>
             $imp<Ratio<T>,Ratio<T>> for Ratio<T> {
             #[inline]
             fn $method(&self, rhs: &Ratio<T>) -> Ratio<T> {
                 Ratio::new((self.numer * rhs.denom).$method(&(self.denom * rhs.numer)),
                            self.denom * rhs.denom)
             }
         }
     }
 }

 // a/b + c/d = (a*d + b*c)/(b*d
 arith_impl!(impl Add, add)

 // a/b - c/d = (a*d - b*c)/(b*d)
 arith_impl!(impl Sub, sub)

 // a/b % c/d = (a*d % b*c)/(b*d)
 arith_impl!(impl Rem, rem)

 impl<T: Clone + Integer + Ord>
     Neg<Ratio<T>> for Ratio<T> {
     #[inline]
     fn neg(&self) -> Ratio<T> {
         Ratio::new_raw(-self.numer, self.denom.clone())
     }
 }

 /* Constants */
 impl<T: Clone + Integer + Ord>
     Zero for Ratio<T> {
     #[inline]
     fn zero() -> Ratio<T> {
         Ratio::new_raw(Zero::zero(), One::one())
     }

     #[inline]
     fn is_zero(&self) -> bool {
         *self == Zero::zero()
     }
 }

 impl<T: Clone + Integer + Ord>
     One for Ratio<T> {
     #[inline]
     fn one() -> Ratio<T> {
         Ratio::new_raw(One::one(), One::one())
     }
 }

 impl<T: Clone + Integer + Ord>
     Num for Ratio<T> {}

 /* Utils */
 impl<T: Clone + Integer + Ord>
     Round for Ratio<T> {

     fn floor(&self) -> Ratio<T> {
         if *self < Zero::zero() {
             Ratio::from_integer((self.numer - self.denom + One::one()) / self.denom)
         } else {
             Ratio::from_integer(self.numer / self.denom)
         }
     }

     fn ceil(&self) -> Ratio<T> {
         if *self < Zero::zero() {
             Ratio::from_integer(self.numer / self.denom)
         } else {
             Ratio::from_integer((self.numer + self.denom - One::one()) / self.denom)
         }
     }

     #[inline]
     fn round(&self) -> Ratio<T> {
         if *self < Zero::zero() {
             Ratio::from_integer((self.numer - self.denom + One::one()) / self.denom)
         } else {
             Ratio::from_integer((self.numer + self.denom - One::one()) / self.denom)
         }
     }

     #[inline]
     fn trunc(&self) -> Ratio<T> {
         Ratio::from_integer(self.numer / self.denom)
     }

     fn fract(&self) -> Ratio<T> {
         Ratio::new_raw(self.numer % self.denom, self.denom.clone())
     }
 }

 impl<T: Clone + Integer + Ord> Fractional for Ratio<T> {
     #[inline]
     fn recip(&self) -> Ratio<T> {
         Ratio::new_raw(self.denom.clone(), self.numer.clone())
     }
 }

 /* String conversions */
 impl<T: ToStr> ToStr for Ratio<T> {
     /// Renders as `numer/denom`.
     fn to_str(&self) -> ~str {
         fmt!("%s/%s", self.numer.to_str(), self.denom.to_str())
     }
 }
 impl<T: ToStrRadix> ToStrRadix for Ratio<T> {
     /// Renders as `numer/denom` where the numbers are in base `radix`.
     fn to_str_radix(&self, radix: uint) -> ~str {
         fmt!("%s/%s", self.numer.to_str_radix(radix), self.denom.to_str_radix(radix))
     }
 }

 impl<T: FromStr + Clone + Integer + Ord>
     FromStr for Ratio<T> {
     /// Parses `numer/denom`.
     fn from_str(s: &str) -> Option<Ratio<T>> {
         let split: ~[&str] = s.splitn_iter('/', 1).collect();
         if split.len() < 2 {
             return None
         }
         let a_option: Option<T> = FromStr::from_str(split[0]);
         do a_option.and_then |a| {
             let b_option: Option<T> = FromStr::from_str(split[1]);
             do b_option.and_then |b| {
                 Some(Ratio::new(a.clone(), b.clone()))
             }
         }
     }
 }
 impl<T: FromStrRadix + Clone + Integer + Ord>
     FromStrRadix for Ratio<T> {
     /// Parses `numer/denom` where the numbers are in base `radix`.
     fn from_str_radix(s: &str, radix: uint) -> Option<Ratio<T>> {
         let split: ~[&str] = s.splitn_iter('/', 1).collect();
         if split.len() < 2 {
             None
         } else {
             let a_option: Option<T> = FromStrRadix::from_str_radix(split[0],
                                                                    radix);
             do a_option.and_then |a| {
                 let b_option: Option<T> =
                     FromStrRadix::from_str_radix(split[1], radix);
                 do b_option.and_then |b| {
                     Some(Ratio::new(a.clone(), b.clone()))
                 }
             }
         }
     }
 }

 #[cfg(test)]
 mod test {

     use super::*;
     use std::num::{Zero,One,FromStrRadix,IntConvertible};
     use std::from_str::FromStr;

     pub static _0 : Rational = Ratio { numer: 0, denom: 1};
     pub static _1 : Rational = Ratio { numer: 1, denom: 1};
     pub static _2: Rational = Ratio { numer: 2, denom: 1};
     pub static _1_2: Rational = Ratio { numer: 1, denom: 2};
     pub static _3_2: Rational = Ratio { numer: 3, denom: 2};
     pub static _neg1_2: Rational =  Ratio { numer: -1, denom: 2};

     pub fn to_big(n: Rational) -> BigRational {
         Ratio::new(
             IntConvertible::from_int(n.numer),
             IntConvertible::from_int(n.denom)
         )
     }

     #[test]
     fn test_test_constants() {
         // check our constants are what Ratio::new etc. would make.
         assert_eq!(_0, Zero::zero());
         assert_eq!(_1, One::one());
         assert_eq!(_2, Ratio::from_integer(2));
         assert_eq!(_1_2, Ratio::new(1,2));
         assert_eq!(_3_2, Ratio::new(3,2));
         assert_eq!(_neg1_2, Ratio::new(-1,2));
     }

     #[test]
     fn test_new_reduce() {
         let one22 = Ratio::new(2i,2);

         assert_eq!(one22, One::one());
     }
     #[test]
     #[should_fail]
     fn test_new_zero() {
         let _a = Ratio::new(1,0);
     }


     #[test]
     fn test_cmp() {
         assert!(_0 == _0 && _1 == _1);
         assert!(_0 != _1 && _1 != _0);
         assert!(_0 < _1 && !(_1 < _0));
         assert!(_1 > _0 && !(_0 > _1));

         assert!(_0 <= _0 && _1 <= _1);
         assert!(_0 <= _1 && !(_1 <= _0));

         assert!(_0 >= _0 && _1 >= _1);
         assert!(_1 >= _0 && !(_0 >= _1));
     }


     mod arith {
         use super::*;
         use super::super::*;


         #[test]
         fn test_add() {
             fn test(a: Rational, b: Rational, c: Rational) {
                 assert_eq!(a + b, c);
                 assert_eq!(to_big(a) + to_big(b), to_big(c));
             }

             test(_1, _1_2, _3_2);
             test(_1, _1, _2);
             test(_1_2, _3_2, _2);
             test(_1_2, _neg1_2, _0);
         }

         #[test]
         fn test_sub() {
             fn test(a: Rational, b: Rational, c: Rational) {
                 assert_eq!(a - b, c);
                 assert_eq!(to_big(a) - to_big(b), to_big(c))
             }

             test(_1, _1_2, _1_2);
             test(_3_2, _1_2, _1);
             test(_1, _neg1_2, _3_2);
         }

         #[test]
         fn test_mul() {
             fn test(a: Rational, b: Rational, c: Rational) {
                 assert_eq!(a * b, c);
                 assert_eq!(to_big(a) * to_big(b), to_big(c))
             }

             test(_1, _1_2, _1_2);
             test(_1_2, _3_2, Ratio::new(3,4));
             test(_1_2, _neg1_2, Ratio::new(-1, 4));
         }

         #[test]
         fn test_div() {
             fn test(a: Rational, b: Rational, c: Rational) {
                 assert_eq!(a / b, c);
                 assert_eq!(to_big(a) / to_big(b), to_big(c))
             }

             test(_1, _1_2, _2);
             test(_3_2, _1_2, _1 + _2);
             test(_1, _neg1_2, _neg1_2 + _neg1_2 + _neg1_2 + _neg1_2);
         }

         #[test]
         fn test_rem() {
             fn test(a: Rational, b: Rational, c: Rational) {
                 assert_eq!(a % b, c);
                 assert_eq!(to_big(a) % to_big(b), to_big(c))
             }

             test(_3_2, _1, _1_2);
             test(_2, _neg1_2, _0);
             test(_1_2, _2,  _1_2);
         }

         #[test]
         fn test_neg() {
             fn test(a: Rational, b: Rational) {
                 assert_eq!(-a, b);
                 assert_eq!(-to_big(a), to_big(b))
             }

             test(_0, _0);
             test(_1_2, _neg1_2);
             test(-_1, _1);
         }
         #[test]
         fn test_zero() {
             assert_eq!(_0 + _0, _0);
             assert_eq!(_0 * _0, _0);
             assert_eq!(_0 * _1, _0);
             assert_eq!(_0 / _neg1_2, _0);
             assert_eq!(_0 - _0, _0);
         }
         #[test]
         #[should_fail]
         fn test_div_0() {
             let _a =  _1 / _0;
         }
     }

     #[test]
     fn test_round() {
         assert_eq!(_1_2.ceil(), _1);
         assert_eq!(_1_2.floor(), _0);
         assert_eq!(_1_2.round(), _1);
         assert_eq!(_1_2.trunc(), _0);

         assert_eq!(_neg1_2.ceil(), _0);
         assert_eq!(_neg1_2.floor(), -_1);
         assert_eq!(_neg1_2.round(), -_1);
         assert_eq!(_neg1_2.trunc(), _0);

         assert_eq!(_1.ceil(), _1);
         assert_eq!(_1.floor(), _1);
         assert_eq!(_1.round(), _1);
         assert_eq!(_1.trunc(), _1);
     }

     #[test]
     fn test_fract() {
         assert_eq!(_1.fract(), _0);
         assert_eq!(_neg1_2.fract(), _neg1_2);
         assert_eq!(_1_2.fract(), _1_2);
         assert_eq!(_3_2.fract(), _1_2);
     }

     #[test]
     fn test_recip() {
         assert_eq!(_1 * _1.recip(), _1);
         assert_eq!(_2 * _2.recip(), _1);
         assert_eq!(_1_2 * _1_2.recip(), _1);
         assert_eq!(_3_2 * _3_2.recip(), _1);
         assert_eq!(_neg1_2 * _neg1_2.recip(), _1);
     }

     #[test]
     fn test_to_from_str() {
         fn test(r: Rational, s: ~str) {
             assert_eq!(FromStr::from_str(s), Some(r));
             assert_eq!(r.to_str(), s);
         }
         test(_1, ~"1/1");
         test(_0, ~"0/1");
         test(_1_2, ~"1/2");
         test(_3_2, ~"3/2");
         test(_2, ~"2/1");
         test(_neg1_2, ~"-1/2");
     }
     #[test]
     fn test_from_str_fail() {
         fn test(s: &str) {
             let rational: Option<Rational> = FromStr::from_str(s);
             assert_eq!(rational, None);
         }

         let xs = ["0 /1", "abc", "", "1/", "--1/2","3/2/1"];
         for &s in xs.iter() {
             test(s);
         }
     }

     #[test]
     fn test_to_from_str_radix() {
         fn test(r: Rational, s: ~str, n: uint) {
             assert_eq!(FromStrRadix::from_str_radix(s, n), Some(r));
             assert_eq!(r.to_str_radix(n), s);
         }
         fn test3(r: Rational, s: ~str) { test(r, s, 3) }
         fn test16(r: Rational, s: ~str) { test(r, s, 16) }

         test3(_1, ~"1/1");
         test3(_0, ~"0/1");
         test3(_1_2, ~"1/2");
         test3(_3_2, ~"10/2");
         test3(_2, ~"2/1");
         test3(_neg1_2, ~"-1/2");
         test3(_neg1_2 / _2, ~"-1/11");

         test16(_1, ~"1/1");
         test16(_0, ~"0/1");
         test16(_1_2, ~"1/2");
         test16(_3_2, ~"3/2");
         test16(_2, ~"2/1");
         test16(_neg1_2, ~"-1/2");
         test16(_neg1_2 / _2, ~"-1/4");
         test16(Ratio::new(13,15), ~"d/f");
         test16(_1_2*_1_2*_1_2*_1_2, ~"1/10");
     }

     #[test]
     fn test_from_str_radix_fail() {
         fn test(s: &str) {
             let radix: Option<Rational> = FromStrRadix::from_str_radix(s, 3);
             assert_eq!(radix, None);
         }

         let xs = ["0 /1", "abc", "", "1/", "--1/2","3/2/1", "3/2"];
         for &s in xs.iter() {
             test(s);
         }
     }
 }
	// Copyright 2013 The Rust Project Developers. See the COPYRIGHT
	// file at the top-level directory of this distribution and at
	// http://rust-lang.org/COPYRIGHT.
	//
	// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
	// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
	// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
	// option. This file may not be copied, modified, or distributed
	// except according to those terms.

	//! Rational numbers


	use std::cmp;
	use std::from_str::FromStr;
	use std::num::{Zero,One,ToStrRadix,FromStrRadix,Round};
	use super::bigint::BigInt;

	/// Represents the ratio between 2 numbers.
	#[deriving(Clone)]
	#[allow(missing_doc)]
	pub struct Ratio<T> {
	numer: T,
	denom: T
	}

	/// Alias for a `Ratio` of machine-sized integers.
	pub type Rational = Ratio<int>;
	pub type Rational32 = Ratio<i32>;
	pub type Rational64 = Ratio<i64>;

	/// Alias for arbitrary precision rationals.
	pub type BigRational = Ratio<BigInt>;

	impl<T: Clone + Integer + Ord>
	Ratio<T> {
	/// Create a ratio representing the integer `t`.
	#[inline]
	pub fn from_integer(t: T) -> Ratio<T> {
	Ratio::new_raw(t, One::one())
	}

	/// Create a ratio without checking for `denom == 0` or reducing.
	#[inline]
	pub fn new_raw(numer: T, denom: T) -> Ratio<T> {
	Ratio { numer: numer, denom: denom }
	}

	/// Create a new Ratio. Fails if `denom == 0`.
	#[inline]
	pub fn new(numer: T, denom: T) -> Ratio<T> {
	if denom == Zero::zero() {
	fail!("denominator == 0");
	}
	let mut ret = Ratio::new_raw(numer, denom);
	ret.reduce();
	ret
	}

	/// Put self into lowest terms, with denom > 0.
	fn reduce(&mut self) {
	let g : T = self.numer.gcd(&self.denom);

	// FIXME(#6050): overloaded operators force moves with generic types
	// self.numer /= g;
	self.numer = self.numer / g;
	// FIXME(#6050): overloaded operators force moves with generic types
	// self.denom /= g;
	self.denom = self.denom / g;

	// keep denom positive!
	if self.denom < Zero::zero() {
	self.numer = -self.numer;
	self.denom = -self.denom;
	}
	}

	/// Return a `reduce`d copy of self.
	fn reduced(&self) -> Ratio<T> {
	let mut ret = self.clone();
	ret.reduce();
	ret
	}
	}

	/* Comparisons */

	// comparing a/b and c/d is the same as comparing ad and bc, so we
	// abstract that pattern. The following macro takes a trait and either
	// a comma-separated list of "method name -> return value" or just
	// "method name" (return value is bool in that case)
	macro_rules! cmp_impl {
	(impl $imp:ident, $($method:ident),+) => {
	cmp_impl!(impl $imp, $($method -> bool),+)
	};
	// return something other than a Ratio<T>
	(impl $imp:ident, $($method:ident -> $res:ty),+) => {
	impl<T: Mul<T,T> + $imp> $imp for Ratio<T> {
	$(
	#[inline]
	fn $method(&self, other: &Ratio<T>) -> $res {
	(self.numer * other.denom). $method (&(self.denom*other.numer))
	}
	)+
	}
	};
	}
	cmp_impl!(impl Eq, eq, ne)
	cmp_impl!(impl TotalEq, equals)
	cmp_impl!(impl Ord, lt, gt, le, ge)
	cmp_impl!(impl TotalOrd, cmp -> cmp::Ordering)

	impl<T: Clone + Integer + Ord> Orderable for Ratio<T> {
	#[inline]
	fn min(&self, other: &Ratio<T>) -> Ratio<T> {
	if self < other { self.clone() } else { other.clone() }
	}

	#[inline]
	fn max(&self, other: &Ratio<T>) -> Ratio<T> {
	if self > other { self.clone() } else { other.clone() }
	}

	#[inline]
	fn clamp(&self, mn: &Ratio<T>, mx: &Ratio<T>) -> Ratio<T> {
	if self > mx { mx.clone()} else
	if self < mn { mn.clone() } else { self.clone() }
	}
	}


	/* Arithmetic */
	// a/b * c/d = (ac)/(bd)
	impl<T: Clone + Integer + Ord>
	Mul<Ratio<T>,Ratio<T>> for Ratio<T> {
	#[inline]
	fn mul(&self, rhs: &Ratio<T>) -> Ratio<T> {
	Ratio::new(self.numer * rhs.numer, self.denom * rhs.denom)
	}
	}

	// (a/b) / (c/d) = (ad)/(bc)
	impl<T: Clone + Integer + Ord>
	Div<Ratio<T>,Ratio<T>> for Ratio<T> {
	#[inline]
	fn div(&self, rhs: &Ratio<T>) -> Ratio<T> {
	Ratio::new(self.numer * rhs.denom, self.denom * rhs.numer)
	}
	}

	// Abstracts the a/b `op` c/d = (ad `op` bd) / (b*d) pattern
	macro_rules! arith_impl {
	(impl $imp:ident, $method:ident) => {
	impl<T: Clone + Integer + Ord>
	$imp<Ratio<T>,Ratio<T>> for Ratio<T> {
	#[inline]
	fn $method(&self, rhs: &Ratio<T>) -> Ratio<T> {
	Ratio::new((self.numer * rhs.denom).$method(&(self.denom * rhs.numer)),
	self.denom * rhs.denom)
	}
	}
	}
	}

	// a/b + c/d = (ad + bc)/(b*d
	arith_impl!(impl Add, add)

	// a/b - c/d = (ad - bc)/(b*d)
	arith_impl!(impl Sub, sub)

	// a/b % c/d = (ad % bc)/(b*d)
	arith_impl!(impl Rem, rem)

	impl<T: Clone + Integer + Ord>
	Neg<Ratio<T>> for Ratio<T> {
	#[inline]
	fn neg(&self) -> Ratio<T> {
	Ratio::new_raw(-self.numer, self.denom.clone())
	}
	}

	/* Constants */
	impl<T: Clone + Integer + Ord>
	Zero for Ratio<T> {
	#[inline]
	fn zero() -> Ratio<T> {
	Ratio::new_raw(Zero::zero(), One::one())
	}

	#[inline]
	fn is_zero(&self) -> bool {
	*self == Zero::zero()
	}
	}

	impl<T: Clone + Integer + Ord>
	One for Ratio<T> {
	#[inline]
	fn one() -> Ratio<T> {
	Ratio::new_raw(One::one(), One::one())
	}
	}

	impl<T: Clone + Integer + Ord>
	Num for Ratio<T> {}

	/* Utils */
	impl<T: Clone + Integer + Ord>
	Round for Ratio<T> {

	fn floor(&self) -> Ratio<T> {
	if *self < Zero::zero() {
	Ratio::from_integer((self.numer - self.denom + One::one()) / self.denom)
	} else {
	Ratio::from_integer(self.numer / self.denom)
	}
	}

	fn ceil(&self) -> Ratio<T> {
	if *self < Zero::zero() {
	Ratio::from_integer(self.numer / self.denom)
	} else {
	Ratio::from_integer((self.numer + self.denom - One::one()) / self.denom)
	}
	}

	#[inline]
	fn round(&self) -> Ratio<T> {
	if *self < Zero::zero() {
	Ratio::from_integer((self.numer - self.denom + One::one()) / self.denom)
	} else {
	Ratio::from_integer((self.numer + self.denom - One::one()) / self.denom)
	}
	}

	#[inline]
	fn trunc(&self) -> Ratio<T> {
	Ratio::from_integer(self.numer / self.denom)
	}

	fn fract(&self) -> Ratio<T> {
	Ratio::new_raw(self.numer % self.denom, self.denom.clone())
	}
	}

	impl<T: Clone + Integer + Ord> Fractional for Ratio<T> {
	#[inline]
	fn recip(&self) -> Ratio<T> {
	Ratio::new_raw(self.denom.clone(), self.numer.clone())
	}
	}

	/* String conversions */
	impl<T: ToStr> ToStr for Ratio<T> {
	/// Renders as `numer/denom`.
	fn to_str(&self) -> ~str {
	fmt!("%s/%s", self.numer.to_str(), self.denom.to_str())
	}
	}
	impl<T: ToStrRadix> ToStrRadix for Ratio<T> {
	/// Renders as `numer/denom` where the numbers are in base `radix`.
	fn to_str_radix(&self, radix: uint) -> ~str {
	fmt!("%s/%s", self.numer.to_str_radix(radix), self.denom.to_str_radix(radix))
	}
	}

	impl<T: FromStr + Clone + Integer + Ord>
	FromStr for Ratio<T> {
	/// Parses `numer/denom`.
	fn from_str(s: &str) -> Option<Ratio<T>> {
	let split: ~[&str] = s.splitn_iter('/', 1).collect();
	if split.len() < 2 {
	return None
	}
	let a_option: Option<T> = FromStr::from_str(split[0]);
	do a_option.and_then \|a\| {
	let b_option: Option<T> = FromStr::from_str(split[1]);
	do b_option.and_then \|b\| {
	Some(Ratio::new(a.clone(), b.clone()))
	}
	}
	}
	}
	impl<T: FromStrRadix + Clone + Integer + Ord>
	FromStrRadix for Ratio<T> {
	/// Parses `numer/denom` where the numbers are in base `radix`.
	fn from_str_radix(s: &str, radix: uint) -> Option<Ratio<T>> {
	let split: ~[&str] = s.splitn_iter('/', 1).collect();
	if split.len() < 2 {
	None
	} else {
	let a_option: Option<T> = FromStrRadix::from_str_radix(split[0],
	radix);
	do a_option.and_then \|a\| {
	let b_option: Option<T> =
	FromStrRadix::from_str_radix(split[1], radix);
	do b_option.and_then \|b\| {
	Some(Ratio::new(a.clone(), b.clone()))
	}
	}
	}
	}
	}

	#[cfg(test)]
	mod test {

	use super::*;
	use std::num::{Zero,One,FromStrRadix,IntConvertible};
	use std::from_str::FromStr;

	pub static _0 : Rational = Ratio { numer: 0, denom: 1};
	pub static _1 : Rational = Ratio { numer: 1, denom: 1};
	pub static _2: Rational = Ratio { numer: 2, denom: 1};
	pub static _1_2: Rational = Ratio { numer: 1, denom: 2};
	pub static _3_2: Rational = Ratio { numer: 3, denom: 2};
	pub static _neg1_2: Rational = Ratio { numer: -1, denom: 2};

	pub fn to_big(n: Rational) -> BigRational {
	Ratio::new(
	IntConvertible::from_int(n.numer),
	IntConvertible::from_int(n.denom)
	)
	}

	#[test]
	fn test_test_constants() {
	// check our constants are what Ratio::new etc. would make.
	assert_eq!(_0, Zero::zero());
	assert_eq!(_1, One::one());
	assert_eq!(_2, Ratio::from_integer(2));
	assert_eq!(_1_2, Ratio::new(1,2));
	assert_eq!(_3_2, Ratio::new(3,2));
	assert_eq!(_neg1_2, Ratio::new(-1,2));
	}

	#[test]
	fn test_new_reduce() {
	let one22 = Ratio::new(2i,2);

	assert_eq!(one22, One::one());
	}
	#[test]
	#[should_fail]
	fn test_new_zero() {
	let _a = Ratio::new(1,0);
	}


	#[test]
	fn test_cmp() {
	assert!(_0 == _0 && _1 == _1);
	assert!(_0 != _1 && _1 != _0);
	assert!(_0 < _1 && !(_1 < _0));
	assert!(_1 > _0 && !(_0 > _1));

	assert!(_0 <= _0 && _1 <= _1);
	assert!(_0 <= _1 && !(_1 <= _0));

	assert!(_0 >= _0 && _1 >= _1);
	assert!(_1 >= _0 && !(_0 >= _1));
	}


	mod arith {
	use super::*;
	use super::super::*;


	#[test]
	fn test_add() {
	fn test(a: Rational, b: Rational, c: Rational) {
	assert_eq!(a + b, c);
	assert_eq!(to_big(a) + to_big(b), to_big(c));
	}

	test(_1, _1_2, _3_2);
	test(_1, _1, _2);
	test(_1_2, _3_2, _2);
	test(_1_2, _neg1_2, _0);
	}

	#[test]
	fn test_sub() {
	fn test(a: Rational, b: Rational, c: Rational) {
	assert_eq!(a - b, c);
	assert_eq!(to_big(a) - to_big(b), to_big(c))
	}

	test(_1, _1_2, _1_2);
	test(_3_2, _1_2, _1);
	test(_1, _neg1_2, _3_2);
	}

	#[test]
	fn test_mul() {
	fn test(a: Rational, b: Rational, c: Rational) {
	assert_eq!(a * b, c);
	assert_eq!(to_big(a) * to_big(b), to_big(c))
	}

	test(_1, _1_2, _1_2);
	test(_1_2, _3_2, Ratio::new(3,4));
	test(_1_2, _neg1_2, Ratio::new(-1, 4));
	}

	#[test]
	fn test_div() {
	fn test(a: Rational, b: Rational, c: Rational) {
	assert_eq!(a / b, c);
	assert_eq!(to_big(a) / to_big(b), to_big(c))
	}

	test(_1, _1_2, _2);
	test(_3_2, _1_2, _1 + _2);
	test(_1, _neg1_2, _neg1_2 + _neg1_2 + _neg1_2 + _neg1_2);
	}

	#[test]
	fn test_rem() {
	fn test(a: Rational, b: Rational, c: Rational) {
	assert_eq!(a % b, c);
	assert_eq!(to_big(a) % to_big(b), to_big(c))
	}

	test(_3_2, _1, _1_2);
	test(_2, _neg1_2, _0);
	test(_1_2, _2, _1_2);
	}

	#[test]
	fn test_neg() {
	fn test(a: Rational, b: Rational) {
	assert_eq!(-a, b);
	assert_eq!(-to_big(a), to_big(b))
	}

	test(_0, _0);
	test(_1_2, _neg1_2);
	test(-_1, _1);
	}
	#[test]
	fn test_zero() {
	assert_eq!(_0 + _0, _0);
	assert_eq!(_0 * _0, _0);
	assert_eq!(_0 * _1, _0);
	assert_eq!(_0 / _neg1_2, _0);
	assert_eq!(_0 - _0, _0);
	}
	#[test]
	#[should_fail]
	fn test_div_0() {
	let _a = _1 / _0;
	}
	}

	#[test]
	fn test_round() {
	assert_eq!(_1_2.ceil(), _1);
	assert_eq!(_1_2.floor(), _0);
	assert_eq!(_1_2.round(), _1);
	assert_eq!(_1_2.trunc(), _0);

	assert_eq!(_neg1_2.ceil(), _0);
	assert_eq!(_neg1_2.floor(), -_1);
	assert_eq!(_neg1_2.round(), -_1);
	assert_eq!(_neg1_2.trunc(), _0);

	assert_eq!(_1.ceil(), _1);
	assert_eq!(_1.floor(), _1);
	assert_eq!(_1.round(), _1);
	assert_eq!(_1.trunc(), _1);
	}

	#[test]
	fn test_fract() {
	assert_eq!(_1.fract(), _0);
	assert_eq!(_neg1_2.fract(), _neg1_2);
	assert_eq!(_1_2.fract(), _1_2);
	assert_eq!(_3_2.fract(), _1_2);
	}

	#[test]
	fn test_recip() {
	assert_eq!(_1 * _1.recip(), _1);
	assert_eq!(_2 * _2.recip(), _1);
	assert_eq!(_1_2 * _1_2.recip(), _1);
	assert_eq!(_3_2 * _3_2.recip(), _1);
	assert_eq!(_neg1_2 * _neg1_2.recip(), _1);
	}

	#[test]
	fn test_to_from_str() {
	fn test(r: Rational, s: ~str) {
	assert_eq!(FromStr::from_str(s), Some(r));
	assert_eq!(r.to_str(), s);
	}
	test(_1, ~"1/1");
	test(_0, ~"0/1");
	test(_1_2, ~"1/2");
	test(_3_2, ~"3/2");
	test(_2, ~"2/1");
	test(_neg1_2, ~"-1/2");
	}
	#[test]
	fn test_from_str_fail() {
	fn test(s: &str) {
	let rational: Option<Rational> = FromStr::from_str(s);
	assert_eq!(rational, None);
	}

	let xs = ["0 /1", "abc", "", "1/", "--1/2","3/2/1"];
	for &s in xs.iter() {
	test(s);
	}
	}

	#[test]
	fn test_to_from_str_radix() {
	fn test(r: Rational, s: ~str, n: uint) {
	assert_eq!(FromStrRadix::from_str_radix(s, n), Some(r));
	assert_eq!(r.to_str_radix(n), s);
	}
	fn test3(r: Rational, s: ~str) { test(r, s, 3) }
	fn test16(r: Rational, s: ~str) { test(r, s, 16) }

	test3(_1, ~"1/1");
	test3(_0, ~"0/1");
	test3(_1_2, ~"1/2");
	test3(_3_2, ~"10/2");
	test3(_2, ~"2/1");
	test3(_neg1_2, ~"-1/2");
	test3(_neg1_2 / _2, ~"-1/11");

	test16(_1, ~"1/1");
	test16(_0, ~"0/1");
	test16(_1_2, ~"1/2");
	test16(_3_2, ~"3/2");
	test16(_2, ~"2/1");
	test16(_neg1_2, ~"-1/2");
	test16(_neg1_2 / _2, ~"-1/4");
	test16(Ratio::new(13,15), ~"d/f");
	test16(_1_2_1_2_1_2*_1_2, ~"1/10");
	}

	#[test]
	fn test_from_str_radix_fail() {
	fn test(s: &str) {
	let radix: Option<Rational> = FromStrRadix::from_str_radix(s, 3);
	assert_eq!(radix, None);
	}

	let xs = ["0 /1", "abc", "", "1/", "--1/2","3/2/1", "3/2"];
	for &s in xs.iter() {
	test(s);
	}
	}
	}