auto merge of #7768 : sfackler/rust/containers, r=huonw

See #4989. I didn't add Persistent{Set,Map} since the only
persistent data structure is fun_treemap and its functionality is
currently too limited to build a trait out of.

13 files changed, 114 insertions, 91 deletions

diff --git a/src/libextra/bitv.rs b/src/libextra/bitv.rs
index 7a0db7a1de7..49cedac399e 100644
--- a/src/libextra/bitv.rs
+++ b/src/libextra/bitv.rs
@@ -718,38 +718,6 @@ impl Set<uint> for BitvSet {
         *value < self.bitv.storage.len() * uint::bits && self.bitv.get(*value)
     }
 
-    fn insert(&mut self, value: uint) -> bool {
-        if self.contains(&value) {
-            return false;
-        }
-        let nbits = self.capacity();
-        if value >= nbits {
-            let newsize = num::max(value, nbits * 2) / uint::bits + 1;
-            assert!(newsize > self.bitv.storage.len());
-            self.bitv.storage.grow(newsize, &0);
-        }
-        self.size += 1;
-        self.bitv.set(value, true);
-        return true;
-    }
-
-    fn remove(&mut self, value: &uint) -> bool {
-        if !self.contains(value) {
-            return false;
-        }
-        self.size -= 1;
-        self.bitv.set(*value, false);
-
-        // Attempt to truncate our storage
-        let mut i = self.bitv.storage.len();
-        while i > 1 && self.bitv.storage[i - 1] == 0 {
-            i -= 1;
-        }
-        self.bitv.storage.truncate(i);
-
-        return true;
-    }
-
     fn is_disjoint(&self, other: &BitvSet) -> bool {
         for self.intersection(other) |_| {
             return false;
@@ -816,6 +784,40 @@ impl Set<uint> for BitvSet {
     }
 }
 
+impl MutableSet<uint> for BitvSet {
+    fn insert(&mut self, value: uint) -> bool {
+        if self.contains(&value) {
+            return false;
+        }
+        let nbits = self.capacity();
+        if value >= nbits {
+            let newsize = num::max(value, nbits * 2) / uint::bits + 1;
+            assert!(newsize > self.bitv.storage.len());
+            self.bitv.storage.grow(newsize, &0);
+        }
+        self.size += 1;
+        self.bitv.set(value, true);
+        return true;
+    }
+
+    fn remove(&mut self, value: &uint) -> bool {
+        if !self.contains(value) {
+            return false;
+        }
+        self.size -= 1;
+        self.bitv.set(*value, false);
+
+        // Attempt to truncate our storage
+        let mut i = self.bitv.storage.len();
+        while i > 1 && self.bitv.storage[i - 1] == 0 {
+            i -= 1;
+        }
+        self.bitv.storage.truncate(i);
+
+        return true;
+    }
+}
+
 impl BitvSet {
     /// Visits each of the words that the two bit vectors (self and other)
     /// both have in common. The three yielded arguments are (bit location,
diff --git a/src/libextra/smallintmap.rs b/src/libextra/smallintmap.rs
index d79a8cc426a..27e9f8cd60f 100644
--- a/src/libextra/smallintmap.rs
+++ b/src/libextra/smallintmap.rs
@@ -17,8 +17,7 @@
 
 
 use std::cmp;
-use std::container::{Container, Mutable, Map, Set};
-use std::iterator::*;
+use std::iterator::{Iterator,IteratorUtil,ZipIterator,Counter,EnumerateIterator,FilterMapIterator};
 use std::uint;
 use std::util::replace;
 use std::vec::{VecIterator,VecMutIterator,VecRevIterator,VecMutRevIterator};
@@ -68,7 +67,9 @@ impl<V> Map<uint, V> for SmallIntMap<V> {
             None
         }
     }
+}
 
+impl<V> MutableMap<uint, V> for SmallIntMap<V> {
     /// Return a mutable reference to the value corresponding to the key
     fn find_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut V> {
         if *key < self.v.len() {
@@ -349,14 +350,6 @@ impl Set<uint> for SmallIntSet {
     /// Return true if the set contains a value
     fn contains(&self, value: &uint) -> bool { self.map.contains_key(value) }
 
-    /// Add a value to the set. Return true if the value was not already
-    /// present in the set.
-    fn insert(&mut self, value: uint) -> bool { self.map.insert(value, ()) }
-
-    /// Remove a value from the set. Return true if the value was
-    /// present in the set.
-    fn remove(&mut self, value: &uint) -> bool { self.map.remove(value) }
-
     /// Return true if the set has no elements in common with `other`.
     /// This is equivalent to checking for an empty uintersection.
     fn is_disjoint(&self, other: &SmallIntSet) -> bool {
@@ -412,6 +405,16 @@ impl Set<uint> for SmallIntSet {
     }
 }
 
+impl MutableSet<uint> for SmallIntSet {
+    /// Add a value to the set. Return true if the value was not already
+    /// present in the set.
+    fn insert(&mut self, value: uint) -> bool { self.map.insert(value, ()) }
+
+    /// Remove a value from the set. Return true if the value was
+    /// present in the set.
+    fn remove(&mut self, value: &uint) -> bool { self.map.remove(value) }
+}
+
 impl SmallIntSet {
     /// Create an empty SmallIntSet
     pub fn new() -> SmallIntSet { SmallIntSet{map: SmallIntMap::new()} }
diff --git a/src/libextra/treemap.rs b/src/libextra/treemap.rs
index 8fac055d26f..05a941b4925 100644
--- a/src/libextra/treemap.rs
+++ b/src/libextra/treemap.rs
@@ -124,7 +124,9 @@ impl<K: TotalOrd, V> Map<K, V> for TreeMap<K, V> {
             }
         }
     }
+}
 
+impl<K: TotalOrd, V> MutableMap<K, V> for TreeMap<K, V> {
     /// Return a mutable reference to the value corresponding to the key
     #[inline]
     fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V> {
@@ -293,16 +295,6 @@ impl<T: TotalOrd> Set<T> for TreeSet<T> {
         self.map.contains_key(value)
     }
 
-    /// Add a value to the set. Return true if the value was not already
-    /// present in the set.
-    #[inline]
-    fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
-
-    /// Remove a value from the set. Return true if the value was
-    /// present in the set.
-    #[inline]
-    fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
-
     /// Return true if the set has no elements in common with `other`.
     /// This is equivalent to checking for an empty intersection.
     fn is_disjoint(&self, other: &TreeSet<T>) -> bool {
@@ -475,6 +467,18 @@ impl<T: TotalOrd> Set<T> for TreeSet<T> {
     }
 }
 
+impl<T: TotalOrd> MutableSet<T> for TreeSet<T> {
+    /// Add a value to the set. Return true if the value was not already
+    /// present in the set.
+    #[inline]
+    fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
+
+    /// Remove a value from the set. Return true if the value was
+    /// present in the set.
+    #[inline]
+    fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
+}
+
 impl<T: TotalOrd> TreeSet<T> {
     /// Create an empty TreeSet
     #[inline]
diff --git a/src/libstd/container.rs b/src/libstd/container.rs
index d6f4c26715a..4bad28ca338 100644
--- a/src/libstd/container.rs
+++ b/src/libstd/container.rs
@@ -30,16 +30,16 @@ pub trait Mutable: Container {
 
 /// A map is a key-value store where values may be looked up by their keys. This
 /// trait provides basic operations to operate on these stores.
-pub trait Map<K, V>: Mutable {
+pub trait Map<K, V>: Container {
     /// Return true if the map contains a value for the specified key
     fn contains_key(&self, key: &K) -> bool;
 
     /// Return a reference to the value corresponding to the key
     fn find<'a>(&'a self, key: &K) -> Option<&'a V>;
+}
 
-    /// Return a mutable reference to the value corresponding to the key
-    fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V>;
-
+/// This trait provides basic operations to modify the contents of a map.
+pub trait MutableMap<K, V>: Map<K, V> + Mutable {
     /// Insert a key-value pair into the map. An existing value for a
     /// key is replaced by the new value. Return true if the key did
     /// not already exist in the map.
@@ -56,23 +56,18 @@ pub trait Map<K, V>: Mutable {
     /// Removes a key from the map, returning the value at the key if the key
     /// was previously in the map.
     fn pop(&mut self, k: &K) -> Option<V>;
+
+    /// Return a mutable reference to the value corresponding to the key
+    fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V>;
 }
 
 /// A set is a group of objects which are each distinct from one another. This
-/// trait represents actions which can be performed on sets to manipulate and
-/// iterate over them.
-pub trait Set<T>: Mutable {
+/// trait represents actions which can be performed on sets to iterate over
+/// them.
+pub trait Set<T>: Container {
     /// Return true if the set contains a value
     fn contains(&self, value: &T) -> bool;
 
-    /// Add a value to the set. Return true if the value was not already
-    /// present in the set.
-    fn insert(&mut self, value: T) -> bool;
-
-    /// Remove a value from the set. Return true if the value was
-    /// present in the set.
-    fn remove(&mut self, value: &T) -> bool;
-
     /// Return true if the set has no elements in common with `other`.
     /// This is equivalent to checking for an empty intersection.
     fn is_disjoint(&self, other: &Self) -> bool;
@@ -95,3 +90,15 @@ pub trait Set<T>: Mutable {
     /// Visit the values representing the union
     fn union(&self, other: &Self, f: &fn(&T) -> bool) -> bool;
 }
+
+/// This trait represents actions which can be performed on sets to mutate
+/// them.
+pub trait MutableSet<T>: Set<T> + Mutable {
+    /// Add a value to the set. Return true if the value was not already
+    /// present in the set.
+    fn insert(&mut self, value: T) -> bool;
+
+    /// Remove a value from the set. Return true if the value was
+    /// present in the set.
+    fn remove(&mut self, value: &T) -> bool;
+}
diff --git a/src/libstd/gc.rs b/src/libstd/gc.rs
index f92561edcb0..9d0588fdcc1 100644
--- a/src/libstd/gc.rs
+++ b/src/libstd/gc.rs
@@ -39,7 +39,7 @@ with destructors.
 */
 
 use cast;
-use container::{Map, Set};
+use container::{Set, MutableSet};
 use io;
 use libc::{uintptr_t};
 use option::{None, Option, Some};
diff --git a/src/libstd/hashmap.rs b/src/libstd/hashmap.rs
index 6c93cd0dc86..e95c63e8912 100644
--- a/src/libstd/hashmap.rs
+++ b/src/libstd/hashmap.rs
@@ -15,7 +15,7 @@
 
 #[mutable_doc];
 
-use container::{Container, Mutable, Map, Set};
+use container::{Container, Mutable, Map, MutableMap, Set, MutableSet};
 use cmp::{Eq, Equiv};
 use hash::Hash;
 use iterator::{Iterator, IteratorUtil};
@@ -316,7 +316,9 @@ impl<K:Hash + Eq,V> Map<K, V> for HashMap<K, V> {
             TableFull | FoundHole(_) => None,
         }
     }
+}
 
+impl<K:Hash + Eq,V> MutableMap<K, V> for HashMap<K, V> {
     /// Return a mutable reference to the value corresponding to the key
     fn find_mut<'a>(&'a mut self, k: &K) -> Option<&'a mut V> {
         let idx = match self.bucket_for_key(k) {
@@ -640,14 +642,6 @@ impl<T:Hash + Eq> Set<T> for HashSet<T> {
     /// Return true if the set contains a value
     fn contains(&self, value: &T) -> bool { self.map.contains_key(value) }
 
-    /// Add a value to the set. Return true if the value was not already
-    /// present in the set.
-    fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
-
-    /// Remove a value from the set. Return true if the value was
-    /// present in the set.
-    fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
-
     /// Return true if the set has no elements in common with `other`.
     /// This is equivalent to checking for an empty intersection.
     fn is_disjoint(&self, other: &HashSet<T>) -> bool {
@@ -688,6 +682,16 @@ impl<T:Hash + Eq> Set<T> for HashSet<T> {
     }
 }
 
+impl<T:Hash + Eq> MutableSet<T> for HashSet<T> {
+    /// Add a value to the set. Return true if the value was not already
+    /// present in the set.
+    fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
+
+    /// Remove a value from the set. Return true if the value was
+    /// present in the set.
+    fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
+}
+
 impl<T:Hash + Eq> HashSet<T> {
     /// Create an empty HashSet
     pub fn new() -> HashSet<T> {
diff --git a/src/libstd/prelude.rs b/src/libstd/prelude.rs
index ea49144b771..8be34896bef 100644
--- a/src/libstd/prelude.rs
+++ b/src/libstd/prelude.rs
@@ -45,7 +45,7 @@ pub use io::{print, println};
 pub use clone::{Clone, DeepClone};
 pub use cmp::{Eq, ApproxEq, Ord, TotalEq, TotalOrd, Ordering, Less, Equal, Greater, Equiv};
 pub use char::Char;
-pub use container::{Container, Mutable, Map, Set};
+pub use container::{Container, Mutable, Map, MutableMap, Set, MutableSet};
 pub use hash::Hash;
 pub use iter::Times;
 pub use iterator::{Iterator, IteratorUtil, DoubleEndedIterator, DoubleEndedIteratorUtil};
diff --git a/src/libstd/task/spawn.rs b/src/libstd/task/spawn.rs
index f45d470a9f6..27cb1c2c100 100644
--- a/src/libstd/task/spawn.rs
+++ b/src/libstd/task/spawn.rs
@@ -77,7 +77,7 @@ use prelude::*;
 use cast::transmute;
 use cast;
 use cell::Cell;
-use container::Map;
+use container::MutableMap;
 use comm::{Chan, GenericChan};
 use hashmap::HashSet;
 use task::local_data_priv::{local_get, local_set, OldHandle};
diff --git a/src/libstd/to_str.rs b/src/libstd/to_str.rs
index 77701acd33e..0c82df7e43a 100644
--- a/src/libstd/to_str.rs
+++ b/src/libstd/to_str.rs
@@ -182,7 +182,7 @@ impl<A:ToStr> ToStr for @[A] {
 mod tests {
     use hashmap::HashMap;
     use hashmap::HashSet;
-    use container::{Set, Map};
+    use container::{Set, Map, MutableSet, MutableMap};
     #[test]
     fn test_simple_types() {
         assert_eq!(1i.to_str(), ~"1");
diff --git a/src/libstd/trie.rs b/src/libstd/trie.rs
index 8ce02d59ab1..c4bfda7e2be 100644
--- a/src/libstd/trie.rs
+++ b/src/libstd/trie.rs
@@ -78,7 +78,9 @@ impl<T> Map<uint, T> for TrieMap<T> {
             idx += 1;
         }
     }
+}
 
+impl<T> MutableMap<uint, T> for TrieMap<T> {
     /// Return a mutable reference to the value corresponding to the key
     #[inline]
     fn find_mut<'a>(&'a mut self, key: &uint) -> Option<&'a mut T> {
diff --git a/src/test/bench/core-map.rs b/src/test/bench/core-map.rs
index fd1110abb22..730b175a499 100644
--- a/src/test/bench/core-map.rs
+++ b/src/test/bench/core-map.rs
@@ -27,7 +27,7 @@ fn timed(label: &str, f: &fn()) {
     io::println(fmt!("  %s: %f", label, end - start));
 }
 
-fn ascending<M: Map<uint, uint>>(map: &mut M, n_keys: uint) {
+fn ascending<M: MutableMap<uint, uint>>(map: &mut M, n_keys: uint) {
     io::println(" Ascending integers:");
 
     do timed("insert") {
@@ -49,7 +49,7 @@ fn ascending<M: Map<uint, uint>>(map: &mut M, n_keys: uint) {
     }
 }
 
-fn descending<M: Map<uint, uint>>(map: &mut M, n_keys: uint) {
+fn descending<M: MutableMap<uint, uint>>(map: &mut M, n_keys: uint) {
     io::println(" Descending integers:");
 
     do timed("insert") {
@@ -71,7 +71,7 @@ fn descending<M: Map<uint, uint>>(map: &mut M, n_keys: uint) {
     }
 }
 
-fn vector<M: Map<uint, uint>>(map: &mut M, n_keys: uint, dist: &[uint]) {
+fn vector<M: MutableMap<uint, uint>>(map: &mut M, n_keys: uint, dist: &[uint]) {
 
     do timed("insert") {
         for uint::range(0, n_keys) |i| {
diff --git a/src/test/bench/core-set.rs b/src/test/bench/core-set.rs
index a0b74251549..461f4caa30b 100644
--- a/src/test/bench/core-set.rs
+++ b/src/test/bench/core-set.rs
@@ -36,7 +36,7 @@ fn timed(result: &mut float, op: &fn()) {
 }
 
 impl Results {
-    pub fn bench_int<T:Set<uint>,
+    pub fn bench_int<T:MutableSet<uint>,
                  R: rand::Rng>(
                  &mut self,
                  rng: &mut R,
@@ -79,7 +79,7 @@ impl Results {
         }
     }
 
-    pub fn bench_str<T:Set<~str>,
+    pub fn bench_str<T:MutableSet<~str>,
                  R:rand::Rng>(
                  &mut self,
                  rng: &mut R,
diff --git a/src/test/run-pass/class-impl-very-parameterized-trait.rs b/src/test/run-pass/class-impl-very-parameterized-trait.rs
index 2805fec6fce..a1ea1d6e3e2 100644
--- a/src/test/run-pass/class-impl-very-parameterized-trait.rs
+++ b/src/test/run-pass/class-impl-very-parameterized-trait.rs
@@ -11,7 +11,6 @@
 // xfail-fast
 
 use std::cmp;
-use std::container::{Container, Mutable, Map};
 use std::int;
 use std::uint;
 
@@ -63,11 +62,6 @@ impl<T> Mutable for cat<T> {
 impl<T> Map<int, T> for cat<T> {
     fn contains_key(&self, k: &int) -> bool { *k <= self.meows }
 
-    fn insert(&mut self, k: int, _: T) -> bool {
-        self.meows += k;
-        true
-    }
-
     fn find<'a>(&'a self, k: &int) -> Option<&'a T> {
         if *k <= self.meows {
             Some(&self.name)
@@ -75,6 +69,13 @@ impl<T> Map<int, T> for cat<T> {
             None
         }
     }
+}
+
+impl<T> MutableMap<int, T> for cat<T> {
+    fn insert(&mut self, k: int, _: T) -> bool {
+        self.meows += k;
+        true
+    }
 
     fn find_mut<'a>(&'a mut self, _k: &int) -> Option<&'a mut T> { fail!() }