core: Factor out uint/u8/16/32/64 mods into uint-template

11 files changed, 351 insertions, 442 deletions

diff --git a/src/libcore/core.rc b/src/libcore/core.rc
index 9d07d42f2c3..3659e53e993 100644
--- a/src/libcore/core.rc
+++ b/src/libcore/core.rc
@@ -81,6 +81,54 @@ mod i64 {
     mod inst;
 }
 
+#[doc = "Operations and constants for `uint`"]
+#[path = "uint-template"]
+mod uint {
+    import inst::{
+        div_ceil, div_round, div_floor, hash, iterate,
+        next_power_of_two, parse_buf, from_str, to_str, str
+    };
+    export div_ceil, div_round, div_floor, hash, iterate,
+    next_power_of_two, parse_buf, from_str, to_str, str;
+
+    #[path = "uint.rs"]
+    mod inst;
+}
+
+#[doc = "Operations and constants for `u8`"]
+#[path = "uint-template"]
+mod u8 {
+    import inst::is_ascii;
+    export is_ascii;
+
+    #[path = "u8.rs"]
+    mod inst;
+}
+
+#[doc = "Operations and constants for `u16`"]
+#[path = "uint-template"]
+mod u16 {
+    #[path = "u16.rs"]
+    mod inst;
+}
+
+#[doc = "Operations and constants for `u32`"]
+#[path = "uint-template"]
+mod u32 {
+    #[path = "u32.rs"]
+    mod inst;
+}
+
+#[doc = "Operations and constants for `u64`"]
+#[path = "uint-template"]
+mod u64 {
+    import inst::{ to_str, str, from_str };
+    export to_str, str, from_str;
+
+    #[path = "u64.rs"]
+    mod inst;
+}
+
 mod box;
 mod char;
 mod float;
@@ -88,11 +136,6 @@ mod f32;
 mod f64;
 mod str;
 mod ptr;
-mod uint;
-mod u8;
-mod u16;
-mod u32;
-mod u64;
 mod vec;
 mod bool;
 
diff --git a/src/libcore/u16.rs b/src/libcore/u16.rs
deleted file mode 100644
index 16ca4800f81..00000000000
--- a/src/libcore/u16.rs
+++ /dev/null
@@ -1,36 +0,0 @@
-#[doc = "Operations and constants for `u16`"];
-
-const min_value: u16 = 0u16;
-const max_value: u16 = 0u16 - 1u16;
-
-pure fn min(x: u16, y: u16) -> u16 { if x < y { x } else { y } }
-pure fn max(x: u16, y: u16) -> u16 { if x > y { x } else { y } }
-
-pure fn add(x: u16, y: u16) -> u16 { x + y }
-pure fn sub(x: u16, y: u16) -> u16 { x - y }
-pure fn mul(x: u16, y: u16) -> u16 { x * y }
-pure fn div(x: u16, y: u16) -> u16 { x / y }
-pure fn rem(x: u16, y: u16) -> u16 { x % y }
-
-pure fn lt(x: u16, y: u16) -> bool { x < y }
-pure fn le(x: u16, y: u16) -> bool { x <= y }
-pure fn eq(x: u16, y: u16) -> bool { x == y }
-pure fn ne(x: u16, y: u16) -> bool { x != y }
-pure fn ge(x: u16, y: u16) -> bool { x >= y }
-pure fn gt(x: u16, y: u16) -> bool { x > y }
-
-pure fn is_positive(x: u16) -> bool { x > 0u16 }
-pure fn is_negative(x: u16) -> bool { x < 0u16 }
-pure fn is_nonpositive(x: u16) -> bool { x <= 0u16 }
-pure fn is_nonnegative(x: u16) -> bool { x >= 0u16 }
-
-#[doc = "Iterate over the range [`lo`..`hi`)"]
-fn range(lo: u16, hi: u16, it: fn(u16)) {
-    let mut i = lo;
-    while i < hi { it(i); i += 1u16; }
-}
-
-#[doc = "Computes the bitwise complement"]
-pure fn compl(i: u16) -> u16 {
-    max_value ^ i
-}
diff --git a/src/libcore/u32.rs b/src/libcore/u32.rs
deleted file mode 100644
index dfe88b19e6a..00000000000
--- a/src/libcore/u32.rs
+++ /dev/null
@@ -1,41 +0,0 @@
-#[doc = "Operations and constants for `u32`"];
-
-const min_value: u32 = 0u32;
-const max_value: u32 = 0u32 - 1u32;
-
-pure fn min(x: u32, y: u32) -> u32 { if x < y { x } else { y } }
-pure fn max(x: u32, y: u32) -> u32 { if x > y { x } else { y } }
-
-pure fn add(x: u32, y: u32) -> u32 { ret x + y; }
-pure fn sub(x: u32, y: u32) -> u32 { ret x - y; }
-pure fn mul(x: u32, y: u32) -> u32 { ret x * y; }
-pure fn div(x: u32, y: u32) -> u32 { ret x / y; }
-pure fn rem(x: u32, y: u32) -> u32 { ret x % y; }
-
-pure fn lt(x: u32, y: u32) -> bool { ret x < y; }
-pure fn le(x: u32, y: u32) -> bool { ret x <= y; }
-pure fn eq(x: u32, y: u32) -> bool { ret x == y; }
-pure fn ne(x: u32, y: u32) -> bool { ret x != y; }
-pure fn ge(x: u32, y: u32) -> bool { ret x >= y; }
-pure fn gt(x: u32, y: u32) -> bool { ret x > y; }
-
-#[doc = "Iterate over the range [`lo`..`hi`)"]
-fn range(lo: u32, hi: u32, it: fn(u32)) {
-    let mut i = lo;
-    while i < hi { it(i); i += 1u32; }
-}
-
-#[doc = "Computes the bitwise complement"]
-pure fn compl(i: u32) -> u32 {
-    max_value ^ i
-}
-
-//
-// Local Variables:
-// mode: rust
-// fill-column: 78;
-// indent-tabs-mode: nil
-// c-basic-offset: 4
-// buffer-file-coding-system: utf-8-unix
-// End:
-//
diff --git a/src/libcore/u8.rs b/src/libcore/u8.rs
deleted file mode 100644
index 613b1d6b15b..00000000000
--- a/src/libcore/u8.rs
+++ /dev/null
@@ -1,41 +0,0 @@
-#[doc = "Operations and constants for `u8`"];
-
-const min_value: u8 = 0u8;
-const max_value: u8 = 0u8 - 1u8;
-
-pure fn min(x: u8, y: u8) -> u8 { if x < y { x } else { y } }
-pure fn max(x: u8, y: u8) -> u8 { if x > y { x } else { y } }
-
-pure fn add(x: u8, y: u8) -> u8 { ret x + y; }
-pure fn sub(x: u8, y: u8) -> u8 { ret x - y; }
-pure fn mul(x: u8, y: u8) -> u8 { ret x * y; }
-pure fn div(x: u8, y: u8) -> u8 { ret x / y; }
-pure fn rem(x: u8, y: u8) -> u8 { ret x % y; }
-
-pure fn lt(x: u8, y: u8) -> bool { ret x < y; }
-pure fn le(x: u8, y: u8) -> bool { ret x <= y; }
-pure fn eq(x: u8, y: u8) -> bool { ret x == y; }
-pure fn ne(x: u8, y: u8) -> bool { ret x != y; }
-pure fn ge(x: u8, y: u8) -> bool { ret x >= y; }
-pure fn gt(x: u8, y: u8) -> bool { ret x > y; }
-
-pure fn is_ascii(x: u8) -> bool { ret 0u8 == x & 128u8; }
-
-#[doc = "Iterate over the range [`lo`..`hi`)"]
-fn range(lo: u8, hi: u8, it: fn(u8)) {
-    let mut i = lo;
-    while i < hi { it(i); i += 1u8; }
-}
-
-#[doc = "Computes the bitwise complement"]
-pure fn compl(i: u8) -> u8 {
-    max_value ^ i
-}
-
-// Local Variables:
-// mode: rust;
-// fill-column: 78;
-// indent-tabs-mode: nil
-// c-basic-offset: 4
-// buffer-file-coding-system: utf-8-unix
-// End:
diff --git a/src/libcore/uint-template.rs b/src/libcore/uint-template.rs
new file mode 100644
index 00000000000..0b95aadcb6a
--- /dev/null
+++ b/src/libcore/uint-template.rs
@@ -0,0 +1,45 @@
+import T = inst::T;
+
+export min_value, max_value;
+export min, max;
+export add, sub, mul, div, rem;
+export lt, le, eq, ne, ge, gt;
+export is_positive, is_negative;
+export is_nonpositive, is_nonnegative;
+export range;
+export compl;
+
+const min_value: T = 0 as T;
+const max_value: T = 0 as T - 1 as T;
+
+pure fn min(x: T, y: T) -> T { if x < y { x } else { y } }
+pure fn max(x: T, y: T) -> T { if x > y { x } else { y } }
+
+pure fn add(x: T, y: T) -> T { x + y }
+pure fn sub(x: T, y: T) -> T { x - y }
+pure fn mul(x: T, y: T) -> T { x * y }
+pure fn div(x: T, y: T) -> T { x / y }
+pure fn rem(x: T, y: T) -> T { x % y }
+
+pure fn lt(x: T, y: T) -> bool { x < y }
+pure fn le(x: T, y: T) -> bool { x <= y }
+pure fn eq(x: T, y: T) -> bool { x == y }
+pure fn ne(x: T, y: T) -> bool { x != y }
+pure fn ge(x: T, y: T) -> bool { x >= y }
+pure fn gt(x: T, y: T) -> bool { x > y }
+
+pure fn is_positive(x: T) -> bool { x > 0 as T }
+pure fn is_negative(x: T) -> bool { x < 0 as T }
+pure fn is_nonpositive(x: T) -> bool { x <= 0 as T }
+pure fn is_nonnegative(x: T) -> bool { x >= 0 as T }
+
+#[doc = "Iterate over the range [`lo`..`hi`)"]
+fn range(lo: T, hi: T, it: fn(T)) {
+    let mut i = lo;
+    while i < hi { it(i); i += 1 as T; }
+}
+
+#[doc = "Computes the bitwise complement"]
+pure fn compl(i: T) -> T {
+    max_value ^ i
+}
diff --git a/src/libcore/uint-template/u16.rs b/src/libcore/uint-template/u16.rs
new file mode 100644
index 00000000000..8d03656d6fe
--- /dev/null
+++ b/src/libcore/uint-template/u16.rs
@@ -0,0 +1 @@
+type T = u16;
diff --git a/src/libcore/uint-template/u32.rs b/src/libcore/uint-template/u32.rs
new file mode 100644
index 00000000000..df9cf28a16c
--- /dev/null
+++ b/src/libcore/uint-template/u32.rs
@@ -0,0 +1 @@
+type T = u32;
diff --git a/src/libcore/u64.rs b/src/libcore/uint-template/u64.rs
index a7542894452..5de83d41da3 100644
--- a/src/libcore/u64.rs
+++ b/src/libcore/uint-template/u64.rs
@@ -1,30 +1,10 @@
-#[doc = "Operations and constants for `u64`"];
+type T = u64;
 
-const min_value: u64 = 0u64;
-const max_value: u64 = 0u64 - 1u64;
+// Type-specific functions here. These must be reexported by the
+// parent module so that they appear in core::u8 and not core::u8::u8;
 
-pure fn min(x: u64, y: u64) -> u64 { if x < y { x } else { y } }
-pure fn max(x: u64, y: u64) -> u64 { if x > y { x } else { y } }
-
-pure fn add(x: u64, y: u64) -> u64 { ret x + y; }
-pure fn sub(x: u64, y: u64) -> u64 { ret x - y; }
-pure fn mul(x: u64, y: u64) -> u64 { ret x * y; }
-pure fn div(x: u64, y: u64) -> u64 { ret x / y; }
-pure fn rem(x: u64, y: u64) -> u64 { ret x % y; }
-
-pure fn lt(x: u64, y: u64) -> bool { ret x < y; }
-pure fn le(x: u64, y: u64) -> bool { ret x <= y; }
-pure fn eq(x: u64, y: u64) -> bool { ret x == y; }
-pure fn ne(x: u64, y: u64) -> bool { ret x != y; }
-pure fn ge(x: u64, y: u64) -> bool { ret x >= y; }
-pure fn gt(x: u64, y: u64) -> bool { ret x > y; }
-
-#[doc = "Iterate over the range [`lo`..`hi`)"]
-fn range(lo: u64, hi: u64, it: fn(u64)) {
-    let mut i = lo;
-    while i < hi { it(i); i += 1u64; }
-}
 
+// FIXME: Surely we can generalize this to apply to all uint types
 #[doc = "Convert to a string in a given base"]
 fn to_str(n: u64, radix: uint) -> str {
     assert (0u < radix && radix <= 16u);
@@ -80,8 +60,3 @@ fn from_str(buf: str, radix: u64) -> option<u64> {
         i -= 1u;
     };
 }
-
-#[doc = "Computes the bitwise complement"]
-pure fn compl(i: u64) -> u64 {
-    max_value ^ i
-}
diff --git a/src/libcore/uint-template/u8.rs b/src/libcore/uint-template/u8.rs
new file mode 100644
index 00000000000..bc73536c4a4
--- /dev/null
+++ b/src/libcore/uint-template/u8.rs
@@ -0,0 +1,6 @@
+type T = u8;
+
+// Type-specific functions here. These must be reexported by the
+// parent module so that they appear in core::u8 and not core::u8::u8;
+
+pure fn is_ascii(x: T) -> bool { ret 0 as T == x & 128 as T; }
diff --git a/src/libcore/uint-template/uint.rs b/src/libcore/uint-template/uint.rs
new file mode 100644
index 00000000000..27a8c26a248
--- /dev/null
+++ b/src/libcore/uint-template/uint.rs
@@ -0,0 +1,246 @@
+type T = uint;
+
+#[doc = "
+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`.
+"]
+pure fn div_ceil(x: uint, y: uint) -> uint {
+    let div = div(x, y);
+    if x % y == 0u { ret div;}
+    else { ret div + 1u; }
+}
+
+#[doc = "
+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`.
+"]
+pure fn div_round(x: uint, y: uint) -> uint {
+    let div = div(x, y);
+    if x % y * 2u  < y { ret div;}
+    else { ret div + 1u; }
+}
+
+#[doc = "
+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`.
+"]
+pure fn div_floor(x: uint, y: uint) -> uint { ret x / y; }
+
+#[doc = "Produce a uint suitable for use in a hash table"]
+pure fn hash(x: uint) -> uint { ret x; }
+
+#[doc = "
+Iterate over the range [`lo`..`hi`), or stop when requested
+
+# Arguments
+
+* lo - The integer at which to start the loop (included)
+* hi - The integer at which to stop the loop (excluded)
+* it - A block to execute with each consecutive integer of the range.
+       Return `true` to continue, `false` to stop.
+
+# Return value
+
+`true` If execution proceeded correctly, `false` if it was interrupted,
+that is if `it` returned `false` at any point.
+"]
+fn iterate(lo: uint, hi: uint, it: fn(uint) -> bool) -> bool {
+    let mut i = lo;
+    while i < hi {
+        if (!it(i)) { ret false; }
+        i += 1u;
+    }
+    ret true;
+}
+
+#[doc = "Returns the smallest power of 2 greater than or equal to `n`"]
+fn next_power_of_two(n: uint) -> uint {
+    let halfbits: uint = sys::size_of::<uint>() * 4u;
+    let mut tmp: uint = n - 1u;
+    let mut shift: uint = 1u;
+    while shift <= halfbits { tmp |= tmp >> shift; shift <<= 1u; }
+    ret tmp + 1u;
+}
+
+#[doc = "
+Parse a buffer of bytes
+
+# Arguments
+
+* buf - A byte buffer
+* radix - The base of the number
+
+# Failure
+
+`buf` must not be empty
+"]
+fn parse_buf(buf: [u8], radix: uint) -> option<uint> {
+    if vec::len(buf) == 0u { ret none; }
+    let mut i = vec::len(buf) - 1u;
+    let mut power = 1u;
+    let mut n = 0u;
+    loop {
+        alt char::to_digit(buf[i] as char, radix) {
+          some(d) { n += d * power; }
+          none { ret none; }
+        }
+        power *= radix;
+        if i == 0u { ret some(n); }
+        i -= 1u;
+    };
+}
+
+#[doc = "Parse a string to an int"]
+fn from_str(s: str) -> option<uint> { parse_buf(str::bytes(s), 10u) }
+
+#[doc = "Convert to a string in a given base"]
+fn to_str(num: uint, radix: uint) -> str {
+    let mut n = num;
+    assert (0u < radix && radix <= 16u);
+    fn digit(n: uint) -> char {
+        ret alt n {
+              0u { '0' }
+              1u { '1' }
+              2u { '2' }
+              3u { '3' }
+              4u { '4' }
+              5u { '5' }
+              6u { '6' }
+              7u { '7' }
+              8u { '8' }
+              9u { '9' }
+              10u { 'a' }
+              11u { 'b' }
+              12u { 'c' }
+              13u { 'd' }
+              14u { 'e' }
+              15u { 'f' }
+              _ { fail }
+            };
+    }
+    if n == 0u { ret "0"; }
+    let mut s: str = "";
+    while n != 0u {
+        s += str::from_byte(digit(n % radix) as u8);
+        n /= radix;
+    }
+    let mut s1: str = "";
+    let mut len: uint = str::len(s);
+    while len != 0u { len -= 1u; s1 += str::from_byte(s[len]); }
+    ret s1;
+}
+
+#[doc = "Convert to a string"]
+fn str(i: uint) -> str { ret to_str(i, 10u); }
+
+#[test]
+fn test_from_str() {
+    assert uint::from_str("0") == some(0u);
+    assert uint::from_str("3") == some(3u);
+    assert uint::from_str("10") == some(10u);
+    assert uint::from_str("123456789") == some(123456789u);
+    assert uint::from_str("00100") == some(100u);
+
+    assert uint::from_str("") == none;
+    assert uint::from_str(" ") == none;
+    assert uint::from_str("x") == none;
+}
+
+#[Test]
+fn test_parse_buf() {
+    import str::bytes;
+    assert uint::parse_buf(bytes("123"), 10u) == some(123u);
+    assert uint::parse_buf(bytes("1001"), 2u) == some(9u);
+    assert uint::parse_buf(bytes("123"), 8u) == some(83u);
+    assert uint::parse_buf(bytes("123"), 16u) == some(291u);
+    assert uint::parse_buf(bytes("ffff"), 16u) == some(65535u);
+    assert uint::parse_buf(bytes("z"), 36u) == some(35u);
+
+    assert uint::parse_buf(str::bytes("Z"), 10u) == none;
+    assert uint::parse_buf(str::bytes("_"), 2u) == none;
+}
+
+#[test]
+fn test_next_power_of_two() {
+    assert (uint::next_power_of_two(0u) == 0u);
+    assert (uint::next_power_of_two(1u) == 1u);
+    assert (uint::next_power_of_two(2u) == 2u);
+    assert (uint::next_power_of_two(3u) == 4u);
+    assert (uint::next_power_of_two(4u) == 4u);
+    assert (uint::next_power_of_two(5u) == 8u);
+    assert (uint::next_power_of_two(6u) == 8u);
+    assert (uint::next_power_of_two(7u) == 8u);
+    assert (uint::next_power_of_two(8u) == 8u);
+    assert (uint::next_power_of_two(9u) == 16u);
+    assert (uint::next_power_of_two(10u) == 16u);
+    assert (uint::next_power_of_two(11u) == 16u);
+    assert (uint::next_power_of_two(12u) == 16u);
+    assert (uint::next_power_of_two(13u) == 16u);
+    assert (uint::next_power_of_two(14u) == 16u);
+    assert (uint::next_power_of_two(15u) == 16u);
+    assert (uint::next_power_of_two(16u) == 16u);
+    assert (uint::next_power_of_two(17u) == 32u);
+    assert (uint::next_power_of_two(18u) == 32u);
+    assert (uint::next_power_of_two(19u) == 32u);
+    assert (uint::next_power_of_two(20u) == 32u);
+    assert (uint::next_power_of_two(21u) == 32u);
+    assert (uint::next_power_of_two(22u) == 32u);
+    assert (uint::next_power_of_two(23u) == 32u);
+    assert (uint::next_power_of_two(24u) == 32u);
+    assert (uint::next_power_of_two(25u) == 32u);
+    assert (uint::next_power_of_two(26u) == 32u);
+    assert (uint::next_power_of_two(27u) == 32u);
+    assert (uint::next_power_of_two(28u) == 32u);
+    assert (uint::next_power_of_two(29u) == 32u);
+    assert (uint::next_power_of_two(30u) == 32u);
+    assert (uint::next_power_of_two(31u) == 32u);
+    assert (uint::next_power_of_two(32u) == 32u);
+    assert (uint::next_power_of_two(33u) == 64u);
+    assert (uint::next_power_of_two(34u) == 64u);
+    assert (uint::next_power_of_two(35u) == 64u);
+    assert (uint::next_power_of_two(36u) == 64u);
+    assert (uint::next_power_of_two(37u) == 64u);
+    assert (uint::next_power_of_two(38u) == 64u);
+    assert (uint::next_power_of_two(39u) == 64u);
+}
+
+#[test]
+fn test_overflows() {
+    assert (uint::max_value > 0u);
+    assert (uint::min_value <= 0u);
+    assert (uint::min_value + uint::max_value + 1u == 0u);
+}
+
+#[test]
+fn test_div() {
+    assert(uint::div_floor(3u, 4u) == 0u);
+    assert(uint::div_ceil(3u, 4u)  == 1u);
+    assert(uint::div_round(3u, 4u) == 1u);
+}
diff --git a/src/libcore/uint.rs b/src/libcore/uint.rs
deleted file mode 100644
index d2b04d78dca..00000000000
--- a/src/libcore/uint.rs
+++ /dev/null
@@ -1,290 +0,0 @@
-#[doc = "Operations and constants for `uint`"];
-
-const min_value: uint = 0u;
-const max_value: uint = 0u - 1u;
-
-pure fn min(x: uint, y: uint) -> uint { if x < y { x } else { y } }
-pure fn max(x: uint, y: uint) -> uint { if x > y { x } else { y } }
-
-pure fn add(x: uint, y: uint) -> uint { ret x + y; }
-pure fn sub(x: uint, y: uint) -> uint { ret x - y; }
-pure fn mul(x: uint, y: uint) -> uint { ret x * y; }
-pure fn div(x: uint, y: uint) -> uint { ret x / y; }
-pure fn rem(x: uint, y: uint) -> uint { ret x % y; }
-
-pure fn lt(x: uint, y: uint) -> bool { ret x < y; }
-pure fn le(x: uint, y: uint) -> bool { ret x <= y; }
-pure fn eq(x: uint, y: uint) -> bool { ret x == y; }
-pure fn ne(x: uint, y: uint) -> bool { ret x != y; }
-pure fn ge(x: uint, y: uint) -> bool { ret x >= y; }
-pure fn gt(x: uint, y: uint) -> bool { ret x > y; }
-
-
-#[doc = "
-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`.
-"]
-pure fn div_ceil(x: uint, y: uint) -> uint {
-    let div = div(x, y);
-    if x % y == 0u { ret div;}
-    else { ret div + 1u; }
-}
-
-#[doc = "
-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`.
-"]
-pure fn div_round(x: uint, y: uint) -> uint {
-    let div = div(x, y);
-    if x % y * 2u  < y { ret div;}
-    else { ret div + 1u; }
-}
-
-#[doc = "
-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`.
-"]
-pure fn div_floor(x: uint, y: uint) -> uint { ret x / y; }
-
-#[doc = "Produce a uint suitable for use in a hash table"]
-pure fn hash(x: uint) -> uint { ret x; }
-
-#[doc = "Iterate over the range [`lo`..`hi`)"]
-#[inline(always)]
-fn range(lo: uint, hi: uint, it: fn(uint)) {
-    let mut i = lo;
-    while i < hi { it(i); i += 1u; }
-}
-
-#[doc = "
-Iterate over the range [`lo`..`hi`), or stop when requested
-
-# Arguments
-
-* lo - The integer at which to start the loop (included)
-* hi - The integer at which to stop the loop (excluded)
-* it - A block to execute with each consecutive integer of the range.
-       Return `true` to continue, `false` to stop.
-
-# Return value
-
-`true` If execution proceeded correctly, `false` if it was interrupted,
-that is if `it` returned `false` at any point.
-"]
-fn iterate(lo: uint, hi: uint, it: fn(uint) -> bool) -> bool {
-    let mut i = lo;
-    while i < hi {
-        if (!it(i)) { ret false; }
-        i += 1u;
-    }
-    ret true;
-}
-
-#[doc = "Returns the smallest power of 2 greater than or equal to `n`"]
-fn next_power_of_two(n: uint) -> uint {
-    let halfbits: uint = sys::size_of::<uint>() * 4u;
-    let mut tmp: uint = n - 1u;
-    let mut shift: uint = 1u;
-    while shift <= halfbits { tmp |= tmp >> shift; shift <<= 1u; }
-    ret tmp + 1u;
-}
-
-#[doc = "
-Parse a buffer of bytes
-
-# Arguments
-
-* buf - A byte buffer
-* radix - The base of the number
-
-# Failure
-
-`buf` must not be empty
-"]
-fn parse_buf(buf: [u8], radix: uint) -> option<uint> {
-    if vec::len(buf) == 0u { ret none; }
-    let mut i = vec::len(buf) - 1u;
-    let mut power = 1u;
-    let mut n = 0u;
-    loop {
-        alt char::to_digit(buf[i] as char, radix) {
-          some(d) { n += d * power; }
-          none { ret none; }
-        }
-        power *= radix;
-        if i == 0u { ret some(n); }
-        i -= 1u;
-    };
-}
-
-#[doc = "Parse a string to an int"]
-fn from_str(s: str) -> option<uint> { parse_buf(str::bytes(s), 10u) }
-
-#[doc = "Convert to a string in a given base"]
-fn to_str(num: uint, radix: uint) -> str {
-    let mut n = num;
-    assert (0u < radix && radix <= 16u);
-    fn digit(n: uint) -> char {
-        ret alt n {
-              0u { '0' }
-              1u { '1' }
-              2u { '2' }
-              3u { '3' }
-              4u { '4' }
-              5u { '5' }
-              6u { '6' }
-              7u { '7' }
-              8u { '8' }
-              9u { '9' }
-              10u { 'a' }
-              11u { 'b' }
-              12u { 'c' }
-              13u { 'd' }
-              14u { 'e' }
-              15u { 'f' }
-              _ { fail }
-            };
-    }
-    if n == 0u { ret "0"; }
-    let mut s: str = "";
-    while n != 0u {
-        s += str::from_byte(digit(n % radix) as u8);
-        n /= radix;
-    }
-    let mut s1: str = "";
-    let mut len: uint = str::len(s);
-    while len != 0u { len -= 1u; s1 += str::from_byte(s[len]); }
-    ret s1;
-}
-
-#[doc = "Convert to a string"]
-fn str(i: uint) -> str { ret to_str(i, 10u); }
-
-#[doc = "Computes the bitwise complement"]
-pure fn compl(i: uint) -> uint {
-    max_value ^ i
-}
-
-#[cfg(test)]
-mod tests {
-
-    #[test]
-    fn test_from_str() {
-        assert uint::from_str("0") == some(0u);
-        assert uint::from_str("3") == some(3u);
-        assert uint::from_str("10") == some(10u);
-        assert uint::from_str("123456789") == some(123456789u);
-        assert uint::from_str("00100") == some(100u);
-
-        assert uint::from_str("") == none;
-        assert uint::from_str(" ") == none;
-        assert uint::from_str("x") == none;
-    }
-
-    #[Test]
-    fn test_parse_buf() {
-        import str::bytes;
-        assert uint::parse_buf(bytes("123"), 10u) == some(123u);
-        assert uint::parse_buf(bytes("1001"), 2u) == some(9u);
-        assert uint::parse_buf(bytes("123"), 8u) == some(83u);
-        assert uint::parse_buf(bytes("123"), 16u) == some(291u);
-        assert uint::parse_buf(bytes("ffff"), 16u) == some(65535u);
-        assert uint::parse_buf(bytes("z"), 36u) == some(35u);
-
-        assert uint::parse_buf(str::bytes("Z"), 10u) == none;
-        assert uint::parse_buf(str::bytes("_"), 2u) == none;
-    }
-
-    #[test]
-    fn test_next_power_of_two() {
-        assert (uint::next_power_of_two(0u) == 0u);
-        assert (uint::next_power_of_two(1u) == 1u);
-        assert (uint::next_power_of_two(2u) == 2u);
-        assert (uint::next_power_of_two(3u) == 4u);
-        assert (uint::next_power_of_two(4u) == 4u);
-        assert (uint::next_power_of_two(5u) == 8u);
-        assert (uint::next_power_of_two(6u) == 8u);
-        assert (uint::next_power_of_two(7u) == 8u);
-        assert (uint::next_power_of_two(8u) == 8u);
-        assert (uint::next_power_of_two(9u) == 16u);
-        assert (uint::next_power_of_two(10u) == 16u);
-        assert (uint::next_power_of_two(11u) == 16u);
-        assert (uint::next_power_of_two(12u) == 16u);
-        assert (uint::next_power_of_two(13u) == 16u);
-        assert (uint::next_power_of_two(14u) == 16u);
-        assert (uint::next_power_of_two(15u) == 16u);
-        assert (uint::next_power_of_two(16u) == 16u);
-        assert (uint::next_power_of_two(17u) == 32u);
-        assert (uint::next_power_of_two(18u) == 32u);
-        assert (uint::next_power_of_two(19u) == 32u);
-        assert (uint::next_power_of_two(20u) == 32u);
-        assert (uint::next_power_of_two(21u) == 32u);
-        assert (uint::next_power_of_two(22u) == 32u);
-        assert (uint::next_power_of_two(23u) == 32u);
-        assert (uint::next_power_of_two(24u) == 32u);
-        assert (uint::next_power_of_two(25u) == 32u);
-        assert (uint::next_power_of_two(26u) == 32u);
-        assert (uint::next_power_of_two(27u) == 32u);
-        assert (uint::next_power_of_two(28u) == 32u);
-        assert (uint::next_power_of_two(29u) == 32u);
-        assert (uint::next_power_of_two(30u) == 32u);
-        assert (uint::next_power_of_two(31u) == 32u);
-        assert (uint::next_power_of_two(32u) == 32u);
-        assert (uint::next_power_of_two(33u) == 64u);
-        assert (uint::next_power_of_two(34u) == 64u);
-        assert (uint::next_power_of_two(35u) == 64u);
-        assert (uint::next_power_of_two(36u) == 64u);
-        assert (uint::next_power_of_two(37u) == 64u);
-        assert (uint::next_power_of_two(38u) == 64u);
-        assert (uint::next_power_of_two(39u) == 64u);
-    }
-
-    #[test]
-    fn test_overflows() {
-        assert (uint::max_value > 0u);
-        assert (uint::min_value <= 0u);
-        assert (uint::min_value + uint::max_value + 1u == 0u);
-    }
-
-    #[test]
-    fn test_div() {
-        assert(uint::div_floor(3u, 4u) == 0u);
-        assert(uint::div_ceil(3u, 4u)  == 1u);
-        assert(uint::div_round(3u, 4u) == 1u);
-    }
-}
-
-// Local Variables:
-// mode: rust;
-// fill-column: 78;
-// indent-tabs-mode: nil
-// c-basic-offset: 4
-// buffer-file-coding-system: utf-8-unix
-// End: