1 files changed, 52 insertions, 23 deletions

diff --git a/src/libcore/trie.rs b/src/libcore/trie.rs
index 7dc85cba297..6b2f2bb6a7d 100644
--- a/src/libcore/trie.rs
+++ b/src/libcore/trie.rs
@@ -32,7 +32,7 @@ pub struct TrieMap<T> {
 impl<T> BaseIter<(uint, &'self T)> for TrieMap<T> {
     /// Visit all key-value pairs in order
     #[inline(always)]
-    pure fn each(&self, f: &fn(&(uint, &self/T)) -> bool) {
+    pure fn each(&self, f: &fn(&(uint, &'self T)) -> bool) {
         self.root.each(f);
     }
     #[inline(always)]
@@ -42,7 +42,7 @@ impl<T> BaseIter<(uint, &'self T)> for TrieMap<T> {
 impl<T> ReverseIter<(uint, &'self T)> for TrieMap<T> {
     /// Visit all key-value pairs in reverse order
     #[inline(always)]
-    pure fn each_reverse(&self, f: &fn(&(uint, &self/T)) -> bool) {
+    pure fn each_reverse(&self, f: &fn(&(uint, &'self T)) -> bool) {
         self.root.each_reverse(f);
     }
 }
@@ -50,11 +50,11 @@ impl<T> ReverseIter<(uint, &'self T)> for TrieMap<T> {
 impl<T> Container for TrieMap<T> {
     /// Return the number of elements in the map
     #[inline(always)]
-    pure fn len(&self) -> uint { self.length }
+    pure fn len(&const self) -> uint { self.length }
 
     /// Return true if the map contains no elements
     #[inline(always)]
-    pure fn is_empty(&self) -> bool { self.len() == 0 }
+    pure fn is_empty(&const self) -> bool { self.len() == 0 }
 }
 
 impl<T> Mutable for TrieMap<T> {
@@ -81,15 +81,20 @@ impl<T> Map<uint, T> for TrieMap<T> {
 
     /// Visit all values in order
     #[inline(always)]
-    pure fn each_value(&self,
-                       f: &fn(&T) -> bool) {
+    pure fn each_value(&self, f: &fn(&T) -> bool) {
         self.each(|&(_, v)| f(v))
     }
 
+    /// Iterate over the map and mutate the contained values
+    #[inline(always)]
+    fn mutate_values(&mut self, f: &fn(&uint, &mut T) -> bool) {
+        self.root.mutate_values(f);
+    }
+
     /// Return the value corresponding to the key in the map
     #[inline(hint)]
-    pure fn find(&self, key: &uint) -> Option<&self/T> {
-        let mut node: &self/TrieNode<T> = &self.root;
+    pure fn find(&self, key: &uint) -> Option<&'self T> {
+        let mut node: &'self TrieNode<T> = &self.root;
         let mut idx = 0;
         loop {
             match node.children[chunk(*key, idx)] {
@@ -132,6 +137,7 @@ impl<T> Map<uint, T> for TrieMap<T> {
 }
 
 impl<T> TrieMap<T> {
+    /// Create an empty TrieMap
     #[inline(always)]
     static pure fn new() -> TrieMap<T> {
         TrieMap{root: TrieNode::new(), length: 0}
@@ -150,11 +156,6 @@ impl<T> TrieMap<T> {
     pure fn each_value_reverse(&self, f: &fn(&T) -> bool) {
         self.each_reverse(|&(_, v)| f(v))
     }
-
-    /// Iterate over the map and mutate the contained values
-    fn mutate_values(&mut self, f: &fn(uint, &mut T) -> bool) {
-        self.root.mutate_values(f);
-    }
 }
 
 pub struct TrieSet {
@@ -177,11 +178,11 @@ impl ReverseIter<uint> for TrieSet {
 impl Container for TrieSet {
     /// Return the number of elements in the set
     #[inline(always)]
-    pure fn len(&self) -> uint { self.map.len() }
+    pure fn len(&const self) -> uint { self.map.len() }
 
     /// Return true if the set contains no elements
     #[inline(always)]
-    pure fn is_empty(&self) -> bool { self.map.is_empty() }
+    pure fn is_empty(&const self) -> bool { self.map.is_empty() }
 }
 
 impl Mutable for TrieSet {
@@ -191,6 +192,12 @@ impl Mutable for TrieSet {
 }
 
 impl TrieSet {
+    /// Create an empty TrieSet
+    #[inline(always)]
+    static pure fn new() -> TrieSet {
+        TrieSet{map: TrieMap::new()}
+    }
+
     /// Return true if the set contains a value
     #[inline(always)]
     pure fn contains(&self, value: &uint) -> bool {
@@ -226,7 +233,7 @@ impl<T> TrieNode<T> {
 }
 
 impl<T> TrieNode<T> {
-    pure fn each(&self, f: &fn(&(uint, &self/T)) -> bool) -> bool {
+    pure fn each(&self, f: &fn(&(uint, &'self T)) -> bool) -> bool {
         for uint::range(0, self.children.len()) |idx| {
             match self.children[idx] {
                 Internal(ref x) => if !x.each(f) { return false },
@@ -237,7 +244,7 @@ impl<T> TrieNode<T> {
         true
     }
 
-    pure fn each_reverse(&self, f: &fn(&(uint, &self/T)) -> bool) -> bool {
+    pure fn each_reverse(&self, f: &fn(&(uint, &'self T)) -> bool) -> bool {
         for uint::range_rev(self.children.len(), 0) |idx| {
             match self.children[idx - 1] {
                 Internal(ref x) => if !x.each_reverse(f) { return false },
@@ -248,13 +255,13 @@ impl<T> TrieNode<T> {
         true
     }
 
-    fn mutate_values(&mut self, f: &fn(uint, &mut T) -> bool) -> bool {
+    fn mutate_values(&mut self, f: &fn(&uint, &mut T) -> bool) -> bool {
         for vec::each_mut(self.children) |child| {
             match *child {
                 Internal(ref mut x) => if !x.mutate_values(f) {
                     return false
                 },
-                External(k, ref mut v) => if !f(k, v) { return false },
+                External(k, ref mut v) => if !f(&k, v) { return false },
                 Nothing => ()
             }
         }
@@ -265,12 +272,12 @@ impl<T> TrieNode<T> {
 // if this was done via a trait, the key could be generic
 #[inline(always)]
 pure fn chunk(n: uint, idx: uint) -> uint {
-    let real_idx = uint::bytes - 1 - idx;
-    (n >> (SHIFT * real_idx)) & MASK
+    let sh = uint::bits - (SHIFT * (idx + 1));
+    (n >> sh) & MASK
 }
 
-fn insert<T>(count: &mut uint, child: &mut Child<T>, key: uint,
-                   value: T, idx: uint) -> bool {
+fn insert<T>(count: &mut uint, child: &mut Child<T>, key: uint, value: T,
+             idx: uint) -> bool {
     let mut tmp = Nothing;
     tmp <-> *child;
     let mut added = false;
@@ -462,4 +469,26 @@ mod tests {
             n -= 1;
         }
     }
+
+    #[test]
+    fn test_sane_chunk() {
+        let x = 1;
+        let y = 1 << (uint::bits - 1);
+
+        let mut trie = TrieSet::new();
+
+        fail_unless!(trie.insert(x));
+        fail_unless!(trie.insert(y));
+
+        fail_unless!(trie.len() == 2);
+
+        let expected = [x, y];
+
+        let mut i = 0;
+
+        for trie.each |x| {
+            fail_unless!(expected[i] == *x);
+            i += 1;
+        }
+    }
 }