Implement Natural trait

This adds the following methods to ints and uints:

- div
- modulo
- div_mod
- quot_rem
- gcd
- lcm
- divisible_by
- is_even
- is_odd

I have not implemented Natural for BigInt and BigUInt because they're a little over my head.

5 files changed, 335 insertions, 2 deletions

diff --git a/src/libcore/core.rc b/src/libcore/core.rc
index 123fbcca9d5..61fbf98a7c6 100644
--- a/src/libcore/core.rc
+++ b/src/libcore/core.rc
@@ -105,7 +105,7 @@ pub use iter::{BaseIter, ExtendedIter, EqIter, CopyableIter};
 pub use iter::{CopyableOrderedIter, CopyableNonstrictIter, Times};
 pub use iter::{ExtendedMutableIter};
 
-pub use num::{Num, Signed, Unsigned, NumCast};
+pub use num::{Num, Signed, Unsigned, Natural, NumCast};
 pub use ptr::Ptr;
 pub use to_str::ToStr;
 pub use clone::Clone;
diff --git a/src/libcore/num/int-template.rs b/src/libcore/num/int-template.rs
index d65cbb4cf92..426ed8a8b0f 100644
--- a/src/libcore/num/int-template.rs
+++ b/src/libcore/num/int-template.rs
@@ -191,6 +191,24 @@ impl Div<T,T> for T {
 #[cfg(stage2,notest)]
 #[cfg(stage3,notest)]
 impl Quot<T,T> for T {
+    /**
+     * Returns the integer quotient, truncated towards 0. As this behaviour reflects
+     * the underlying machine implementation it is more efficient than `Natural::div`.
+     *
+     * # Examples
+     *
+     * ~~~
+     * assert!( 8 /  3 ==  2);
+     * assert!( 8 / -3 == -2);
+     * assert!(-8 /  3 == -2);
+     * assert!(-8 / -3 ==  2);
+
+     * assert!( 1 /  2 ==  0);
+     * assert!( 1 / -2 ==  0);
+     * assert!(-1 /  2 ==  0);
+     * assert!(-1 / -2 ==  0);
+     * ~~~
+     */
     #[inline(always)]
     fn quot(&self, other: &T) -> T { *self / *other }
 }
@@ -205,6 +223,27 @@ impl Modulo<T,T> for T {
 #[cfg(stage2,notest)]
 #[cfg(stage3,notest)]
 impl Rem<T,T> for T {
+    /**
+     * Returns the integer remainder after division, satisfying:
+     *
+     * ~~~
+     * assert!((n / d) * d + (n % d) == n)
+     * ~~~
+     *
+     * # Examples
+     *
+     * ~~~
+     * assert!( 8 %  3 ==  2);
+     * assert!( 8 % -3 ==  2);
+     * assert!(-8 %  3 == -2);
+     * assert!(-8 % -3 == -2);
+
+     * assert!( 1 %  2 ==  1);
+     * assert!( 1 % -2 ==  1);
+     * assert!(-1 %  2 == -1);
+     * assert!(-1 % -2 == -1);
+     * ~~~
+     */
     #[inline(always)]
     fn rem(&self, other: &T) -> T { *self % *other }
 }
@@ -247,6 +286,123 @@ impl Signed for T {
     fn is_negative(&self) -> bool { *self < 0 }
 }
 
+impl Natural for T {
+    /**
+     * Floored integer division
+     *
+     * # Examples
+     *
+     * ~~~
+     * assert!(( 8).div( 3) ==  2);
+     * assert!(( 8).div(-3) == -3);
+     * assert!((-8).div( 3) == -3);
+     * assert!((-8).div(-3) ==  2);
+     *
+     * assert!(( 1).div( 2) ==  0);
+     * assert!(( 1).div(-2) == -1);
+     * assert!((-1).div( 2) == -1);
+     * assert!((-1).div(-2) ==  0);
+     * ~~~
+     */
+    #[inline(always)]
+    fn div(&self, other: T) -> T {
+        // Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_,
+        // December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf)
+        match self.quot_rem(other) {
+            (q, r) if (r > 0 && other < 0)
+                   || (r < 0 && other > 0) => q - 1,
+            (q, _)                         => q,
+        }
+    }
+
+    /**
+     * Integer modulo, satisfying:
+     *
+     * ~~~
+     * assert!(n.div(d) * d + n.modulo(d) == n)
+     * ~~~
+     *
+     * # Examples
+     *
+     * ~~~
+     * assert!(( 8).modulo( 3) ==  2);
+     * assert!(( 8).modulo(-3) == -1);
+     * assert!((-8).modulo( 3) ==  1);
+     * assert!((-8).modulo(-3) == -2);
+     *
+     * assert!(( 1).modulo( 2) ==  1);
+     * assert!(( 1).modulo(-2) == -1);
+     * assert!((-1).modulo( 2) ==  1);
+     * assert!((-1).modulo(-2) == -1);
+     * ~~~
+     */
+    #[inline(always)]
+    fn modulo(&self, other: T) -> T {
+        // Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_,
+        // December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf)
+        match *self % other {
+            r if (r > 0 && other < 0)
+              || (r < 0 && other > 0) => r + other,
+            r                         => r,
+        }
+    }
+
+    /// Calculates `div` and `modulo` simultaneously
+    #[inline(always)]
+    fn div_mod(&self, other: T) -> (T,T) {
+        // Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_,
+        // December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf)
+        match self.quot_rem(other) {
+            (q, r) if (r > 0 && other < 0)
+                   || (r < 0 && other > 0) => (q - 1, r + other),
+            (q, r)                         => (q, r),
+        }
+    }
+
+    /// Calculates `quot` (`\`) and `rem` (`%`) simultaneously
+    #[inline(always)]
+    fn quot_rem(&self, other: T) -> (T,T) {
+        (*self / other, *self % other)
+    }
+
+    /**
+     * Calculates the Greatest Common Divisor (GCD) of the number and `other`
+     *
+     * The result is always positive
+     */
+    #[inline(always)]
+    fn gcd(&self, other: T) -> T {
+        // Use Euclid's algorithm
+        let mut m = *self, n = other;
+        while m != 0 {
+            let temp = m;
+            m = n % temp;
+            n = temp;
+        }
+        n.abs()
+    }
+
+    /**
+     * Calculates the Lowest Common Multiple (LCM) of the number and `other`
+     */
+    #[inline(always)]
+    fn lcm(&self, other: T) -> T {
+        ((*self * other) / self.gcd(other)).abs() // should not have to recaluculate abs
+    }
+
+    /// Returns `true` if the number can be divided by `other` without leaving a remainder
+    #[inline(always)]
+    fn divisible_by(&self, other: T) -> bool { *self % other == 0 }
+
+    /// Returns `true` if the number is divisible by `2`
+    #[inline(always)]
+    fn is_even(&self) -> bool { self.divisible_by(2) }
+
+    /// Returns `true` if the number is not divisible by `2`
+    #[inline(always)]
+    fn is_odd(&self) -> bool { !self.is_even() }
+}
+
 #[cfg(notest)]
 impl BitOr<T,T> for T {
     #[inline(always)]
@@ -388,6 +544,95 @@ mod tests {
         assert!((-1 as T).is_negative());
     }
 
+    /**
+     * Checks that the division rule holds for:
+     *
+     * - `n`: numerator (dividend)
+     * - `d`: denominator (divisor)
+     * - `qr`: quotient and remainder
+     */
+    #[cfg(test)]
+    fn test_division_rule(nd: (T,T), qr: (T,T)) {
+        let (n,d) = nd,
+            (q,r) = qr;
+
+        assert_eq!(d * q + r, n);
+    }
+
+    #[test]
+    fn test_quot_rem() {
+        fn test_nd_qr(nd: (T,T), qr: (T,T)) {
+            let (n,d) = nd;
+            let separate_quot_rem = (n / d, n % d);
+            let combined_quot_rem = n.quot_rem(d);
+
+            assert_eq!(separate_quot_rem, qr);
+            assert_eq!(combined_quot_rem, qr);
+
+            test_division_rule(nd, separate_quot_rem);
+            test_division_rule(nd, combined_quot_rem);
+        }
+
+        test_nd_qr(( 8,  3), ( 2,  2));
+        test_nd_qr(( 8, -3), (-2,  2));
+        test_nd_qr((-8,  3), (-2, -2));
+        test_nd_qr((-8, -3), ( 2, -2));
+
+        test_nd_qr(( 1,  2), ( 0,  1));
+        test_nd_qr(( 1, -2), ( 0,  1));
+        test_nd_qr((-1,  2), ( 0, -1));
+        test_nd_qr((-1, -2), ( 0, -1));
+    }
+
+    #[test]
+    fn test_div_mod() {
+        fn test_nd_dm(nd: (T,T), dm: (T,T)) {
+            let (n,d) = nd;
+            let separate_div_mod = (n.div(d), n.modulo(d));
+            let combined_div_mod = n.div_mod(d);
+
+            assert_eq!(separate_div_mod, dm);
+            assert_eq!(combined_div_mod, dm);
+
+            test_division_rule(nd, separate_div_mod);
+            test_division_rule(nd, combined_div_mod);
+        }
+
+        test_nd_dm(( 8,  3), ( 2,  2));
+        test_nd_dm(( 8, -3), (-3, -1));
+        test_nd_dm((-8,  3), (-3,  1));
+        test_nd_dm((-8, -3), ( 2, -2));
+
+        test_nd_dm(( 1,  2), ( 0,  1));
+        test_nd_dm(( 1, -2), (-1, -1));
+        test_nd_dm((-1,  2), (-1,  1));
+        test_nd_dm((-1, -2), ( 0, -1));
+    }
+
+    #[test]
+    fn test_gcd() {
+        assert_eq!((10 as T).gcd(2), 2 as T);
+        assert_eq!((10 as T).gcd(3), 1 as T);
+        assert_eq!((0 as T).gcd(3), 3 as T);
+        assert_eq!((3 as T).gcd(3), 3 as T);
+        assert_eq!((56 as T).gcd(42), 14 as T);
+        assert_eq!((3 as T).gcd(-3), 3 as T);
+        assert_eq!((-6 as T).gcd(3), 3 as T);
+        assert_eq!((-4 as T).gcd(-2), 2 as T);
+    }
+
+    #[test]
+    fn test_lcm() {
+        assert_eq!((1 as T).lcm(0), 0 as T);
+        assert_eq!((0 as T).lcm(1), 0 as T);
+        assert_eq!((1 as T).lcm(1), 1 as T);
+        assert_eq!((-1 as T).lcm(1), 1 as T);
+        assert_eq!((1 as T).lcm(-1), 1 as T);
+        assert_eq!((-1 as T).lcm(-1), 1 as T);
+        assert_eq!((8 as T).lcm(9), 72 as T);
+        assert_eq!((11 as T).lcm(5), 55 as T);
+    }
+
     #[test]
     fn test_bitwise_ops() {
         assert_eq!(0b1110 as T, (0b1100 as T).bitor(&(0b1010 as T)));
diff --git a/src/libcore/num/num.rs b/src/libcore/num/num.rs
index ea0b290aac2..577bb3f0f15 100644
--- a/src/libcore/num/num.rs
+++ b/src/libcore/num/num.rs
@@ -75,6 +75,22 @@ pub fn abs<T:Ord + Zero + Neg<T>>(v: T) -> T {
     if v < Zero::zero() { v.neg() } else { v }
 }
 
+pub trait Natural: Num
+                 + Ord
+                 + Quot<Self,Self>
+                 + Rem<Self,Self> {
+    fn div(&self, other: Self) -> Self;
+    fn modulo(&self, other: Self) -> Self;
+    fn div_mod(&self, other: Self) -> (Self,Self);
+    fn quot_rem(&self, other: Self) -> (Self,Self);
+
+    fn gcd(&self, other: Self) -> Self;
+    fn lcm(&self, other: Self) -> Self;
+    fn divisible_by(&self, other: Self) -> bool;
+    fn is_even(&self) -> bool;
+    fn is_odd(&self) -> bool;
+}
+
 pub trait Round {
     fn round(&self, mode: RoundMode) -> Self;
 
diff --git a/src/libcore/num/uint-template.rs b/src/libcore/num/uint-template.rs
index 41205145f17..a0da84a8c53 100644
--- a/src/libcore/num/uint-template.rs
+++ b/src/libcore/num/uint-template.rs
@@ -184,6 +184,59 @@ impl Neg<T> for T {
 
 impl Unsigned for T {}
 
+impl Natural for T {
+    /// Unsigned integer division. Returns the same result as `quot` (`/`).
+    #[inline(always)]
+    fn div(&self, other: T) -> T { *self / other }
+
+    /// Unsigned integer modulo operation. Returns the same result as `rem` (`%`).
+    #[inline(always)]
+    fn modulo(&self, other: T) -> T { *self / other }
+
+    /// Calculates `div` and `modulo` simultaneously
+    #[inline(always)]
+    fn div_mod(&self, other: T) -> (T,T) {
+        (*self / other, *self % other)
+    }
+
+    /// Calculates `quot` (`\`) and `rem` (`%`) simultaneously
+    #[inline(always)]
+    fn quot_rem(&self, other: T) -> (T,T) {
+        (*self / other, *self % other)
+    }
+
+    /// Calculates the Greatest Common Divisor (GCD) of the number and `other`
+    #[inline(always)]
+    fn gcd(&self, other: T) -> T {
+        // Use Euclid's algorithm
+        let mut m = *self, n = other;
+        while m != 0 {
+            let temp = m;
+            m = n % temp;
+            n = temp;
+        }
+        n
+    }
+
+    /// Calculates the Lowest Common Multiple (LCM) of the number and `other`
+    #[inline(always)]
+    fn lcm(&self, other: T) -> T {
+        (*self * other) / self.gcd(other)
+    }
+
+    /// Returns `true` if the number can be divided by `other` without leaving a remainder
+    #[inline(always)]
+    fn divisible_by(&self, other: T) -> bool { *self % other == 0 }
+
+    /// Returns `true` if the number is divisible by `2`
+    #[inline(always)]
+    fn is_even(&self) -> bool { self.divisible_by(2) }
+
+    /// Returns `true` if the number is not divisible by `2`
+    #[inline(always)]
+    fn is_odd(&self) -> bool { !self.is_even() }
+}
+
 #[cfg(notest)]
 impl BitOr<T,T> for T {
     #[inline(always)]
@@ -304,6 +357,25 @@ mod tests {
     use prelude::*;
 
     #[test]
+    fn test_gcd() {
+        assert_eq!((10 as T).gcd(2), 2 as T);
+        assert_eq!((10 as T).gcd(3), 1 as T);
+        assert_eq!((0 as T).gcd(3), 3 as T);
+        assert_eq!((3 as T).gcd(3), 3 as T);
+        assert_eq!((56 as T).gcd(42), 14 as T);
+    }
+
+    #[test]
+    fn test_lcm() {
+        assert_eq!((1 as T).lcm(0), 0 as T);
+        assert_eq!((0 as T).lcm(1), 0 as T);
+        assert_eq!((1 as T).lcm(1), 1 as T);
+        assert_eq!((8 as T).lcm(9), 72 as T);
+        assert_eq!((11 as T).lcm(5), 55 as T);
+        assert_eq!((99 as T).lcm(17), 1683 as T);
+    }
+
+    #[test]
     fn test_bitwise_ops() {
         assert_eq!(0b1110 as T, (0b1100 as T).bitor(&(0b1010 as T)));
         assert_eq!(0b1000 as T, (0b1100 as T).bitand(&(0b1010 as T)));
diff --git a/src/libcore/prelude.rs b/src/libcore/prelude.rs
index 157a0e3752d..03e6065a85c 100644
--- a/src/libcore/prelude.rs
+++ b/src/libcore/prelude.rs
@@ -39,7 +39,7 @@ pub use hash::Hash;
 pub use iter::{BaseIter, ReverseIter, MutableIter, ExtendedIter, EqIter};
 pub use iter::{CopyableIter, CopyableOrderedIter, CopyableNonstrictIter};
 pub use iter::{Times, ExtendedMutableIter};
-pub use num::{Num, Signed, Unsigned, NumCast};
+pub use num::{Num, Signed, Unsigned, Natural, NumCast};
 pub use path::GenericPath;
 pub use path::Path;
 pub use path::PosixPath;