auto merge of #6471 : gifnksm/rust/reform-rational, r=brson

`std::ratio` module contains `BigRational` type, but the type is not usable by following reasons.
* `Ratio::new` requires `T: Copy + Num + Ord`, but `BigInt` is not implicitly copyable, because it contains unique vector.
* `BigInt` is not implements `Num`

So, I rewrite `Ratio` as follows.
* `Ratio` requires `T: Clone + Integer + Ord`.
  * `Copy` -> `Clone`: to be able to use `BigRational`
  * `Num` -> `Integer`: It is incorrect that a rational number constructed by two non-integer numbers.
* `BigInt` implements `Num` and `Orderable` which are required by `Integer` bound

2 files changed, 126 insertions, 84 deletions

diff --git a/src/libstd/num/bigint.rs b/src/libstd/num/bigint.rs
index 498c86dd8e1..c35415c5331 100644
--- a/src/libstd/num/bigint.rs
+++ b/src/libstd/num/bigint.rs
@@ -17,7 +17,7 @@ A BigInt is a combination of BigUint and Sign.
 */
 
 use core::cmp::{Eq, Ord, TotalEq, TotalOrd, Ordering, Less, Equal, Greater};
-use core::num::{IntConvertible, Zero, One, ToStrRadix, FromStrRadix};
+use core::num::{IntConvertible, Zero, One, ToStrRadix, FromStrRadix, Orderable};
 
 /**
 A BigDigit is a BigUint's composing element.
@@ -144,6 +144,26 @@ impl FromStr for BigUint {
     }
 }
 
+impl Num for BigUint {}
+
+impl Orderable for BigUint {
+    #[inline(always)]
+    fn min(&self, other: &BigUint) -> BigUint {
+        if self < other { self.clone() } else { other.clone() }
+    }
+
+    #[inline(always)]
+    fn max(&self, other: &BigUint) -> BigUint {
+        if self > other { self.clone() } else { other.clone() }
+    }
+
+    #[inline(always)]
+    fn clamp(&self, mn: &BigUint, mx: &BigUint) -> BigUint {
+        if self > mx { mx.clone() } else
+        if self < mn { mn.clone() } else { self.clone() }
+    }
+}
+
 impl Shl<uint, BigUint> for BigUint {
     #[inline(always)]
     fn shl(&self, rhs: &uint) -> BigUint {
@@ -788,6 +808,26 @@ impl FromStr for BigInt {
     }
 }
 
+impl Num for BigInt {}
+
+impl Orderable for BigInt {
+    #[inline(always)]
+    fn min(&self, other: &BigInt) -> BigInt {
+        if self < other { self.clone() } else { other.clone() }
+    }
+
+    #[inline(always)]
+    fn max(&self, other: &BigInt) -> BigInt {
+        if self > other { self.clone() } else { other.clone() }
+    }
+
+    #[inline(always)]
+    fn clamp(&self, mn: &BigInt, mx: &BigInt) -> BigInt {
+        if self > mx { mx.clone() } else
+        if self < mn { mn.clone() } else { self.clone() }
+    }
+}
+
 impl Shl<uint, BigInt> for BigInt {
     #[inline(always)]
     fn shl(&self, rhs: &uint) -> BigInt {
diff --git a/src/libstd/num/rational.rs b/src/libstd/num/rational.rs
index a47f68091a7..d57c642c5a2 100644
--- a/src/libstd/num/rational.rs
+++ b/src/libstd/num/rational.rs
@@ -30,7 +30,7 @@ pub type Rational64 = Ratio<i64>;
 /// Alias for arbitrary precision rationals.
 pub type BigRational = Ratio<BigInt>;
 
-impl<T: Copy + Num + Ord>
+impl<T: Clone + Integer + Ord>
     Ratio<T> {
     /// Create a ratio representing the integer `t`.
     #[inline(always)]
@@ -57,10 +57,14 @@ impl<T: Copy + Num + Ord>
 
     /// Put self into lowest terms, with denom > 0.
     fn reduce(&mut self) {
-        let g : T = gcd(self.numer, self.denom);
+        let g : T = self.numer.gcd(&self.denom);
 
-        self.numer /= g;
-        self.denom /= g;
+        // 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() {
@@ -68,42 +72,15 @@ impl<T: Copy + Num + Ord>
             self.denom = -self.denom;
         }
     }
+
     /// Return a `reduce`d copy of self.
     fn reduced(&self) -> Ratio<T> {
-        let mut ret = copy *self;
+        let mut ret = self.clone();
         ret.reduce();
         ret
     }
 }
 
-/**
-Compute the greatest common divisor of two numbers, via Euclid's algorithm.
-
-The result can be negative.
-*/
-#[inline]
-pub fn gcd_raw<T: Num>(n: T, m: T) -> T {
-    let mut m = m, n = n;
-    while m != Zero::zero() {
-        let temp = m;
-        m = n % temp;
-        n = temp;
-    }
-    n
-}
-
-/**
-Compute the greatest common divisor of two numbers, via Euclid's algorithm.
-
-The result is always positive.
-*/
-#[inline]
-pub fn gcd<T: Num + Ord>(n: T, m: T) -> T {
-    let g = gcd_raw(n, m);
-    if g < Zero::zero() { -g }
-    else { g }
-}
-
 /* Comparisons */
 
 // comparing a/b and c/d is the same as comparing a*d and b*c, so we
@@ -133,7 +110,7 @@ cmp_impl!(impl TotalOrd, cmp -> cmp::Ordering)
 
 /* Arithmetic */
 // a/b * c/d = (a*c)/(b*d)
-impl<T: Copy + Num + Ord>
+impl<T: Clone + Integer + Ord>
     Mul<Ratio<T>,Ratio<T>> for Ratio<T> {
     #[inline]
     fn mul(&self, rhs: &Ratio<T>) -> Ratio<T> {
@@ -142,7 +119,7 @@ impl<T: Copy + Num + Ord>
 }
 
 // (a/b) / (c/d) = (a*d)/(b*c)
-impl<T: Copy + Num + Ord>
+impl<T: Clone + Integer + Ord>
     Div<Ratio<T>,Ratio<T>> for Ratio<T> {
     #[inline]
     fn div(&self, rhs: &Ratio<T>) -> Ratio<T> {
@@ -153,7 +130,7 @@ impl<T: Copy + Num + Ord>
 // 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: Copy + Num + Ord>
+        impl<T: Clone + Integer + Ord>
             $imp<Ratio<T>,Ratio<T>> for Ratio<T> {
             #[inline]
             fn $method(&self, rhs: &Ratio<T>) -> Ratio<T> {
@@ -173,16 +150,16 @@ arith_impl!(impl Sub, sub)
 // a/b % c/d = (a*d % b*c)/(b*d)
 arith_impl!(impl Rem, rem)
 
-impl<T: Copy + Num + Ord>
+impl<T: Clone + Integer + Ord>
     Neg<Ratio<T>> for Ratio<T> {
     #[inline]
     fn neg(&self) -> Ratio<T> {
-        Ratio::new_raw(-self.numer, self.denom)
+        Ratio::new_raw(-self.numer, self.denom.clone())
     }
 }
 
 /* Constants */
-impl<T: Copy + Num + Ord>
+impl<T: Clone + Integer + Ord>
     Zero for Ratio<T> {
     #[inline]
     fn zero() -> Ratio<T> {
@@ -195,7 +172,7 @@ impl<T: Copy + Num + Ord>
     }
 }
 
-impl<T: Copy + Num + Ord>
+impl<T: Clone + Integer + Ord>
     One for Ratio<T> {
     #[inline]
     fn one() -> Ratio<T> {
@@ -203,11 +180,11 @@ impl<T: Copy + Num + Ord>
     }
 }
 
-impl<T: Copy + Num + Ord>
+impl<T: Clone + Integer + Ord>
     Num for Ratio<T> {}
 
 /* Utils */
-impl<T: Copy + Num + Ord>
+impl<T: Clone + Integer + Ord>
     Round for Ratio<T> {
 
     fn floor(&self) -> Ratio<T> {
@@ -241,14 +218,14 @@ impl<T: Copy + Num + Ord>
     }
 
     fn fract(&self) -> Ratio<T> {
-        Ratio::new_raw(self.numer % self.denom, self.denom)
+        Ratio::new_raw(self.numer % self.denom, self.denom.clone())
     }
 }
 
-impl<T: Copy + Num + Ord> Fractional for Ratio<T> {
+impl<T: Clone + Integer + Ord> Fractional for Ratio<T> {
     #[inline]
     fn recip(&self) -> Ratio<T> {
-        Ratio::new_raw(self.denom, self.numer)
+        Ratio::new_raw(self.denom.clone(), self.numer.clone())
     }
 }
 
@@ -266,7 +243,7 @@ impl<T: ToStrRadix> ToStrRadix for Ratio<T> {
     }
 }
 
-impl<T: FromStr + Copy + Num + Ord>
+impl<T: FromStr + Clone + Integer + Ord>
     FromStr for Ratio<T> {
     /// Parses `numer/denom`.
     fn from_str(s: &str) -> Option<Ratio<T>> {
@@ -276,14 +253,14 @@ impl<T: FromStr + Copy + Num + Ord>
             }
         });
         if split.len() < 2 { return None; }
-        do FromStr::from_str(split[0]).chain |a| {
-            do FromStr::from_str(split[1]).chain |b| {
-                Some(Ratio::new(a,b))
+        do FromStr::from_str::<T>(split[0]).chain |a| {
+            do FromStr::from_str::<T>(split[1]).chain |b| {
+                Some(Ratio::new(a.clone(), b.clone()))
             }
         }
     }
 }
-impl<T: FromStrRadix + Copy + Num + Ord>
+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>> {
@@ -294,9 +271,9 @@ impl<T: FromStrRadix + Copy + Num + Ord>
         });
         if split.len() < 2 { None }
         else {
-            do FromStrRadix::from_str_radix(split[0], radix).chain |a| {
-                do FromStrRadix::from_str_radix(split[1], radix).chain |b| {
-                    Some(Ratio::new(a,b))
+            do FromStrRadix::from_str_radix::<T>(split[0], radix).chain |a| {
+                do FromStrRadix::from_str_radix::<T>(split[1], radix).chain |b| {
+                    Some(Ratio::new(a.clone(), b.clone()))
                 }
             }
         }
@@ -306,7 +283,7 @@ impl<T: FromStrRadix + Copy + Num + Ord>
 #[cfg(test)]
 mod test {
     use super::*;
-    use core::num::{Zero,One,FromStrRadix};
+    use core::num::{Zero,One,FromStrRadix,IntConvertible};
     use core::from_str::FromStr;
 
     pub static _0 : Rational = Ratio { numer: 0, denom: 1};
@@ -316,16 +293,11 @@ mod test {
     pub static _3_2: Rational = Ratio { numer: 3, denom: 2};
     pub static _neg1_2: Rational =  Ratio { numer: -1, denom: 2};
 
-    #[test]
-    fn test_gcd() {
-        assert_eq!(gcd(10,2),2);
-        assert_eq!(gcd(10,3),1);
-        assert_eq!(gcd(0,3),3);
-        assert_eq!(gcd(3,3),3);
-
-        assert_eq!(gcd(3,-3), 3);
-        assert_eq!(gcd(-6,3), 3);
-        assert_eq!(gcd(-4,-2), 2);
+    pub fn to_big(n: Rational) -> BigRational {
+        Ratio::new(
+            IntConvertible::from_int(n.numer),
+            IntConvertible::from_int(n.denom)
+        )
     }
 
     #[test]
@@ -374,45 +346,75 @@ mod test {
 
         #[test]
         fn test_add() {
-            assert_eq!(_1 + _1_2, _3_2);
-            assert_eq!(_1 + _1, _2);
-            assert_eq!(_1_2 + _3_2, _2);
-            assert_eq!(_1_2 + _neg1_2, _0);
+            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() {
-            assert_eq!(_1 - _1_2, _1_2);
-            assert_eq!(_3_2 - _1_2, _1);
-            assert_eq!(_1 - _neg1_2, _3_2);
+            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() {
-            assert_eq!(_1 * _1_2, _1_2);
-            assert_eq!(_1_2 * _3_2, Ratio::new(3,4));
-            assert_eq!(_1_2 * _neg1_2, Ratio::new(-1, 4));
+            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() {
-            assert_eq!(_1 / _1_2, _2);
-            assert_eq!(_3_2 / _1_2, _1 + _2);
-            assert_eq!(_1 / _neg1_2, _neg1_2 + _neg1_2 + _neg1_2 + _neg1_2);
+            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() {
-            assert_eq!(_3_2 % _1, _1_2);
-            assert_eq!(_2 % _neg1_2, _0);
-            assert_eq!(_1_2 % _2,  _1_2);
+            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() {
-            assert_eq!(-_0, _0);
-            assert_eq!(-_1_2, _neg1_2);
-            assert_eq!(-(-_1), _1);
+            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() {