auto merge of #11930 : bjz/rust/next_power_of_two, r=huonw

5 files changed, 89 insertions, 141 deletions

diff --git a/src/libstd/num/int.rs b/src/libstd/num/int.rs
index 96e182adb82..f336afe12f4 100644
--- a/src/libstd/num/int.rs
+++ b/src/libstd/num/int.rs
@@ -120,10 +120,3 @@ impl CheckedMul for int {
         }
     }
 }
-
-#[test]
-fn test_overflows() {
-    assert!((::int::MAX > 0));
-    assert!((::int::MIN <= 0));
-    assert!((::int::MIN + ::int::MAX + 1 == 0));
-}
diff --git a/src/libstd/num/int_macros.rs b/src/libstd/num/int_macros.rs
index c0f67912cde..c8d5dc12499 100644
--- a/src/libstd/num/int_macros.rs
+++ b/src/libstd/num/int_macros.rs
@@ -446,6 +446,13 @@ mod tests {
     use num::Bitwise;
 
     #[test]
+    fn test_overflows() {
+        assert!(MAX > 0);
+        assert!(MIN <= 0);
+        assert_eq!(MIN + MAX + 1, 0);
+    }
+
+    #[test]
     fn test_num() {
         num::test_num(10 as $T, 2 as $T);
     }
diff --git a/src/libstd/num/mod.rs b/src/libstd/num/mod.rs
index 956c04db09c..976761b5120 100644
--- a/src/libstd/num/mod.rs
+++ b/src/libstd/num/mod.rs
@@ -440,7 +440,39 @@ pub trait Primitive: Clone
 /// A collection of traits relevant to primitive signed and unsigned integers
 pub trait Int: Integer
              + Primitive
-             + Bitwise {}
+             + Bitwise
+             + CheckedAdd
+             + CheckedSub
+             // + CheckedMul // FIXME #8849: currently not impled on 32-bit
+             + CheckedDiv {}
+
+/// Returns the smallest power of 2 greater than or equal to `n`.
+#[inline]
+pub fn next_power_of_two<T: Unsigned + Int>(n: T) -> T {
+    let halfbits: T = cast(size_of::<T>() * 4).unwrap();
+    let mut tmp: T = n - one();
+    let mut shift: T = one();
+    while shift <= halfbits {
+        tmp = tmp | (tmp >> shift);
+        shift = shift << one();
+    }
+    tmp + one()
+}
+
+/// Returns the smallest power of 2 greater than or equal to `n`. If the next
+/// power of two is greater than the type's maximum value, `None` is returned,
+/// otherwise the power of 2 is wrapped in `Some`.
+#[inline]
+pub fn checked_next_power_of_two<T: Unsigned + Int>(n: T) -> Option<T> {
+    let halfbits: T = cast(size_of::<T>() * 4).unwrap();
+    let mut tmp: T = n - one();
+    let mut shift: T = one();
+    while shift <= halfbits {
+        tmp = tmp | (tmp >> shift);
+        shift = shift << one();
+    }
+    tmp.checked_add(&one())
+}
 
 /// Used for representing the classification of floating point numbers
 #[deriving(Eq)]
@@ -1589,6 +1621,48 @@ mod tests {
         assert_eq!(third.checked_mul(&4), None);
     }
 
+    macro_rules! test_next_power_of_two(
+        ($test_name:ident, $T:ident) => (
+            fn $test_name() {
+                #[test];
+                assert_eq!(next_power_of_two::<$T>(0), 0);
+                let mut next_power = 1;
+                for i in range::<$T>(1, 40) {
+                     assert_eq!(next_power_of_two(i), next_power);
+                     if i == next_power { next_power *= 2 }
+                }
+            }
+        )
+    )
+
+    test_next_power_of_two!(test_next_power_of_two_u8, u8)
+    test_next_power_of_two!(test_next_power_of_two_u16, u16)
+    test_next_power_of_two!(test_next_power_of_two_u32, u32)
+    test_next_power_of_two!(test_next_power_of_two_u64, u64)
+    test_next_power_of_two!(test_next_power_of_two_uint, uint)
+
+    macro_rules! test_checked_next_power_of_two(
+        ($test_name:ident, $T:ident) => (
+            fn $test_name() {
+                #[test];
+                assert_eq!(checked_next_power_of_two::<$T>(0), None);
+                let mut next_power = 1;
+                for i in range::<$T>(1, 40) {
+                     assert_eq!(checked_next_power_of_two(i), Some(next_power));
+                     if i == next_power { next_power *= 2 }
+                }
+                assert!(checked_next_power_of_two::<$T>($T::MAX / 2).is_some());
+                assert_eq!(checked_next_power_of_two::<$T>($T::MAX - 1), None);
+                assert_eq!(checked_next_power_of_two::<$T>($T::MAX), None);
+            }
+        )
+    )
+
+    test_checked_next_power_of_two!(test_checked_next_power_of_two_u8, u8)
+    test_checked_next_power_of_two!(test_checked_next_power_of_two_u16, u16)
+    test_checked_next_power_of_two!(test_checked_next_power_of_two_u32, u32)
+    test_checked_next_power_of_two!(test_checked_next_power_of_two_u64, u64)
+    test_checked_next_power_of_two!(test_checked_next_power_of_two_uint, uint)
 
     #[deriving(Eq)]
     struct Value { x: int }
diff --git a/src/libstd/num/uint.rs b/src/libstd/num/uint.rs
index 89914571ada..1811ebc7acc 100644
--- a/src/libstd/num/uint.rs
+++ b/src/libstd/num/uint.rs
@@ -15,7 +15,6 @@
 use prelude::*;
 
 use default::Default;
-use mem;
 use num::{Bitwise, Bounded};
 use num::{CheckedAdd, CheckedSub, CheckedMul};
 use num::{CheckedDiv, Zero, One, strconv};
@@ -26,79 +25,6 @@ use unstable::intrinsics;
 
 uint_module!(uint, int, ::int::BITS)
 
-///
-/// Divide two numbers, return the result, rounded up.
-///
-/// # Arguments
-///
-/// * x - an integer
-/// * y - an integer distinct from 0u
-///
-/// # Return value
-///
-/// The smallest integer `q` such that `x/y <= q`.
-///
-pub fn div_ceil(x: uint, y: uint) -> uint {
-    let div = x / y;
-    if x % y == 0u { div }
-    else { div + 1u }
-}
-
-///
-/// Divide two numbers, return the result, rounded to the closest integer.
-///
-/// # Arguments
-///
-/// * x - an integer
-/// * y - an integer distinct from 0u
-///
-/// # Return value
-///
-/// The integer `q` closest to `x/y`.
-///
-pub fn div_round(x: uint, y: uint) -> uint {
-    let div = x / y;
-    if x % y * 2u  < y { div }
-    else { div + 1u }
-}
-
-///
-/// Divide two numbers, return the result, rounded down.
-///
-/// Note: This is the same function as `div`.
-///
-/// # Arguments
-///
-/// * x - an integer
-/// * y - an integer distinct from 0u
-///
-/// # Return value
-///
-/// The smallest integer `q` such that `x/y <= q`. This
-/// is either `x/y` or `x/y + 1`.
-///
-pub fn div_floor(x: uint, y: uint) -> uint { return x / y; }
-
-/// Returns the smallest power of 2 greater than or equal to `n`
-#[inline]
-pub fn next_power_of_two(n: uint) -> uint {
-    let halfbits: uint = mem::size_of::<uint>() * 4u;
-    let mut tmp: uint = n - 1u;
-    let mut shift: uint = 1u;
-    while shift <= halfbits { tmp |= tmp >> shift; shift <<= 1u; }
-    tmp + 1u
-}
-
-/// Returns the smallest power of 2 greater than or equal to `n`
-#[inline]
-pub fn next_power_of_two_opt(n: uint) -> Option<uint> {
-    let halfbits: uint = mem::size_of::<uint>() * 4u;
-    let mut tmp: uint = n - 1u;
-    let mut shift: uint = 1u;
-    while shift <= halfbits { tmp |= tmp >> shift; shift <<= 1u; }
-    tmp.checked_add(&1)
-}
-
 #[cfg(target_word_size = "32")]
 impl CheckedAdd for uint {
     #[inline]
@@ -164,62 +90,3 @@ impl CheckedMul for uint {
         }
     }
 }
-
-#[test]
-fn test_next_power_of_two() {
-    assert!((next_power_of_two(0u) == 0u));
-    assert!((next_power_of_two(1u) == 1u));
-    assert!((next_power_of_two(2u) == 2u));
-    assert!((next_power_of_two(3u) == 4u));
-    assert!((next_power_of_two(4u) == 4u));
-    assert!((next_power_of_two(5u) == 8u));
-    assert!((next_power_of_two(6u) == 8u));
-    assert!((next_power_of_two(7u) == 8u));
-    assert!((next_power_of_two(8u) == 8u));
-    assert!((next_power_of_two(9u) == 16u));
-    assert!((next_power_of_two(10u) == 16u));
-    assert!((next_power_of_two(11u) == 16u));
-    assert!((next_power_of_two(12u) == 16u));
-    assert!((next_power_of_two(13u) == 16u));
-    assert!((next_power_of_two(14u) == 16u));
-    assert!((next_power_of_two(15u) == 16u));
-    assert!((next_power_of_two(16u) == 16u));
-    assert!((next_power_of_two(17u) == 32u));
-    assert!((next_power_of_two(18u) == 32u));
-    assert!((next_power_of_two(19u) == 32u));
-    assert!((next_power_of_two(20u) == 32u));
-    assert!((next_power_of_two(21u) == 32u));
-    assert!((next_power_of_two(22u) == 32u));
-    assert!((next_power_of_two(23u) == 32u));
-    assert!((next_power_of_two(24u) == 32u));
-    assert!((next_power_of_two(25u) == 32u));
-    assert!((next_power_of_two(26u) == 32u));
-    assert!((next_power_of_two(27u) == 32u));
-    assert!((next_power_of_two(28u) == 32u));
-    assert!((next_power_of_two(29u) == 32u));
-    assert!((next_power_of_two(30u) == 32u));
-    assert!((next_power_of_two(31u) == 32u));
-    assert!((next_power_of_two(32u) == 32u));
-    assert!((next_power_of_two(33u) == 64u));
-    assert!((next_power_of_two(34u) == 64u));
-    assert!((next_power_of_two(35u) == 64u));
-    assert!((next_power_of_two(36u) == 64u));
-    assert!((next_power_of_two(37u) == 64u));
-    assert!((next_power_of_two(38u) == 64u));
-    assert!((next_power_of_two(39u) == 64u));
-}
-
-#[test]
-fn test_overflows() {
-    use uint;
-    assert!((uint::MAX > 0u));
-    assert!((uint::MIN <= 0u));
-    assert!((uint::MIN + uint::MAX + 1u == 0u));
-}
-
-#[test]
-fn test_div() {
-    assert!((div_floor(3u, 4u) == 0u));
-    assert!((div_ceil(3u, 4u)  == 1u));
-    assert!((div_round(3u, 4u) == 1u));
-}
diff --git a/src/libstd/num/uint_macros.rs b/src/libstd/num/uint_macros.rs
index 224f16cc663..eb483843b5d 100644
--- a/src/libstd/num/uint_macros.rs
+++ b/src/libstd/num/uint_macros.rs
@@ -318,6 +318,13 @@ mod tests {
     use u16;
 
     #[test]
+    fn test_overflows() {
+        assert!(MAX > 0);
+        assert!(MIN <= 0);
+        assert_eq!(MIN + MAX + 1, 0);
+    }
+
+    #[test]
     fn test_num() {
         num::test_num(10 as $T, 2 as $T);
     }