collections: Remove all collections traits

As part of the collections reform RFC, this commit removes all collections
traits in favor of inherent methods on collections themselves. All methods
should continue to be available on all collections.

This is a breaking change with all of the collections traits being removed and
no longer being in the prelude. In order to update old code you should move the
trait implementations to inherent implementations directly on the type itself.

Note that some traits had default methods which will also need to be implemented
to maintain backwards compatibility.

[breaking-change]
cc #18424

23 files changed, 383 insertions, 157 deletions

diff --git a/src/libstd/ascii.rs b/src/libstd/ascii.rs
index 31f37a8a1bb..6b64959a843 100644
--- a/src/libstd/ascii.rs
+++ b/src/libstd/ascii.rs
@@ -14,7 +14,6 @@
 
 #![experimental]
 
-use collections::Collection;
 use core::kinds::Sized;
 use fmt;
 use iter::Iterator;
diff --git a/src/libstd/c_vec.rs b/src/libstd/c_vec.rs
index bb7de168898..fd605bb2b5c 100644
--- a/src/libstd/c_vec.rs
+++ b/src/libstd/c_vec.rs
@@ -35,7 +35,6 @@
 
 #![experimental]
 
-use collections::Collection;
 use kinds::Send;
 use mem;
 use ops::Drop;
@@ -143,6 +142,12 @@ impl<T> CVec<T> {
         self.dtor = None;
         self.base
     }
+
+    /// Returns the number of items in this vector.
+    pub fn len(&self) -> uint { self.len }
+
+    /// Returns whether this vector is empty.
+    pub fn is_empty(&self) -> bool { self.len() == 0 }
 }
 
 impl<T> AsSlice<T> for CVec<T> {
@@ -154,10 +159,6 @@ impl<T> AsSlice<T> for CVec<T> {
     }
 }
 
-impl<T> Collection for CVec<T> {
-    fn len(&self) -> uint { self.len }
-}
-
 #[cfg(test)]
 mod tests {
     use prelude::*;
diff --git a/src/libstd/collections/hashmap/map.rs b/src/libstd/collections/hashmap/map.rs
index 881ffd21d71..596e483c2f6 100644
--- a/src/libstd/collections/hashmap/map.rs
+++ b/src/libstd/collections/hashmap/map.rs
@@ -12,7 +12,6 @@
 
 use clone::Clone;
 use cmp::{max, Eq, Equiv, PartialEq};
-use collections::{Collection, Mutable, MutableSet, Map, MutableMap};
 use default::Default;
 use fmt::{mod, Show};
 use hash::{Hash, Hasher, RandomSipHasher};
@@ -471,86 +470,6 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     }
 }
 
-impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Collection for HashMap<K, V, H> {
-    /// Return the number of elements in the map.
-    fn len(&self) -> uint { self.table.size() }
-}
-
-impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Mutable for HashMap<K, V, H> {
-    /// Clear the map, removing all key-value pairs. Keeps the allocated memory
-    /// for reuse.
-    fn clear(&mut self) {
-        // Prevent reallocations from happening from now on. Makes it possible
-        // for the map to be reused but has a downside: reserves permanently.
-        self.resize_policy.reserve(self.table.size());
-
-        let cap = self.table.capacity();
-        let mut buckets = Bucket::first(&mut self.table);
-
-        while buckets.index() != cap {
-            buckets = match buckets.peek() {
-                Empty(b)  => b.next(),
-                Full(full) => {
-                    let (b, _, _) = full.take();
-                    b.next()
-                }
-            };
-        }
-    }
-}
-
-impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Map<K, V> for HashMap<K, V, H> {
-    fn find<'a>(&'a self, k: &K) -> Option<&'a V> {
-        self.search(k).map(|bucket| {
-            let (_, v) = bucket.into_refs();
-            v
-        })
-    }
-
-    fn contains_key(&self, k: &K) -> bool {
-        self.search(k).is_some()
-    }
-}
-
-impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> MutableMap<K, V> for HashMap<K, V, H> {
-    fn find_mut<'a>(&'a mut self, k: &K) -> Option<&'a mut V> {
-        match self.search_mut(k) {
-            Some(bucket) => {
-                let (_, v) = bucket.into_mut_refs();
-                Some(v)
-            }
-            _ => None
-        }
-    }
-
-    fn swap(&mut self, k: K, v: V) -> Option<V> {
-        let hash = self.make_hash(&k);
-        let potential_new_size = self.table.size() + 1;
-        self.make_some_room(potential_new_size);
-
-        let mut retval = None;
-        self.insert_or_replace_with(hash, k, v, |_, val_ref, val| {
-            retval = Some(replace(val_ref, val));
-        });
-        retval
-    }
-
-
-    fn pop(&mut self, k: &K) -> Option<V> {
-        if self.table.size() == 0 {
-            return None
-        }
-
-        let potential_new_size = self.table.size() - 1;
-        self.make_some_room(potential_new_size);
-
-        self.search_mut(k).map(|bucket| {
-            let (_k, val) = pop_internal(bucket);
-            val
-        })
-    }
-}
-
 impl<K: Hash + Eq, V> HashMap<K, V, RandomSipHasher> {
     /// Create an empty HashMap.
     ///
@@ -1064,6 +983,219 @@ impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
         let hash = self.make_hash(&key);
         search_entry_hashed(&mut self.table, hash, key)
     }
+
+    /// Return the number of elements in the map.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashMap;
+    ///
+    /// let mut a = HashMap::new();
+    /// assert_eq!(a.len(), 0);
+    /// a.insert(1u, "a");
+    /// assert_eq!(a.len(), 1);
+    /// ```
+    pub fn len(&self) -> uint { self.table.size() }
+
+    /// Return true if the map contains no elements.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashMap;
+    ///
+    /// let mut a = HashMap::new();
+    /// assert!(a.is_empty());
+    /// a.insert(1u, "a");
+    /// assert!(!a.is_empty());
+    /// ```
+    #[inline]
+    pub fn is_empty(&self) -> bool { self.len() == 0 }
+
+    /// Clears the map, removing all key-value pairs. Keeps the allocated memory
+    /// for reuse.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashMap;
+    ///
+    /// let mut a = HashMap::new();
+    /// a.insert(1u, "a");
+    /// a.clear();
+    /// assert!(a.is_empty());
+    /// ```
+    pub fn clear(&mut self) {
+        // Prevent reallocations from happening from now on. Makes it possible
+        // for the map to be reused but has a downside: reserves permanently.
+        self.resize_policy.reserve(self.table.size());
+
+        let cap = self.table.capacity();
+        let mut buckets = Bucket::first(&mut self.table);
+
+        while buckets.index() != cap {
+            buckets = match buckets.peek() {
+                Empty(b)  => b.next(),
+                Full(full) => {
+                    let (b, _, _) = full.take();
+                    b.next()
+                }
+            };
+        }
+    }
+
+    /// Returns a reference to the value corresponding to the key.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashMap;
+    ///
+    /// let mut map = HashMap::new();
+    /// map.insert(1u, "a");
+    /// assert_eq!(map.find(&1), Some(&"a"));
+    /// assert_eq!(map.find(&2), None);
+    /// ```
+    pub fn find<'a>(&'a self, k: &K) -> Option<&'a V> {
+        self.search(k).map(|bucket| {
+            let (_, v) = bucket.into_refs();
+            v
+        })
+    }
+
+    /// Returns true if the map contains a value for the specified key.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashMap;
+    ///
+    /// let mut map = HashMap::new();
+    /// map.insert(1u, "a");
+    /// assert_eq!(map.contains_key(&1), true);
+    /// assert_eq!(map.contains_key(&2), false);
+    /// ```
+    pub fn contains_key(&self, k: &K) -> bool {
+        self.search(k).is_some()
+    }
+
+    /// Returns a mutable reference to the value corresponding to the key.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashMap;
+    ///
+    /// let mut map = HashMap::new();
+    /// map.insert(1u, "a");
+    /// match map.find_mut(&1) {
+    ///     Some(x) => *x = "b",
+    ///     None => (),
+    /// }
+    /// assert_eq!(map[1], "b");
+    /// ```
+    pub fn find_mut<'a>(&'a mut self, k: &K) -> Option<&'a mut V> {
+        match self.search_mut(k) {
+            Some(bucket) => {
+                let (_, v) = bucket.into_mut_refs();
+                Some(v)
+            }
+            _ => None
+        }
+    }
+
+    /// Inserts a key-value pair into the map. An existing value for a
+    /// key is replaced by the new value. Returns `true` if the key did
+    /// not already exist in the map.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashMap;
+    ///
+    /// let mut map = HashMap::new();
+    /// assert_eq!(map.insert(2u, "value"), true);
+    /// assert_eq!(map.insert(2, "value2"), false);
+    /// assert_eq!(map[2], "value2");
+    /// ```
+    #[inline]
+    pub fn insert(&mut self, key: K, value: V) -> bool {
+        self.swap(key, value).is_none()
+    }
+
+    /// Removes a key-value pair from the map. Returns `true` if the key
+    /// was present in the map.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashMap;
+    ///
+    /// let mut map = HashMap::new();
+    /// assert_eq!(map.remove(&1u), false);
+    /// map.insert(1, "a");
+    /// assert_eq!(map.remove(&1), true);
+    /// ```
+    #[inline]
+    pub fn remove(&mut self, key: &K) -> bool {
+        self.pop(key).is_some()
+    }
+
+    /// Inserts a key-value pair from the map. If the key already had a value
+    /// present in the map, that value is returned. Otherwise, `None` is returned.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashMap;
+    ///
+    /// let mut map = HashMap::new();
+    /// assert_eq!(map.swap(37u, "a"), None);
+    /// assert_eq!(map.is_empty(), false);
+    ///
+    /// map.insert(37, "b");
+    /// assert_eq!(map.swap(37, "c"), Some("b"));
+    /// assert_eq!(map[37], "c");
+    /// ```
+    pub fn swap(&mut self, k: K, v: V) -> Option<V> {
+        let hash = self.make_hash(&k);
+        let potential_new_size = self.table.size() + 1;
+        self.make_some_room(potential_new_size);
+
+        let mut retval = None;
+        self.insert_or_replace_with(hash, k, v, |_, val_ref, val| {
+            retval = Some(replace(val_ref, val));
+        });
+        retval
+    }
+
+    /// Removes a key from the map, returning the value at the key if the key
+    /// was previously in the map.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashMap;
+    ///
+    /// let mut map = HashMap::new();
+    /// map.insert(1u, "a");
+    /// assert_eq!(map.pop(&1), Some("a"));
+    /// assert_eq!(map.pop(&1), None);
+    /// ```
+    pub fn pop(&mut self, k: &K) -> Option<V> {
+        if self.table.size() == 0 {
+            return None
+        }
+
+        let potential_new_size = self.table.size() - 1;
+        self.make_some_room(potential_new_size);
+
+        self.search_mut(k).map(|bucket| {
+            let (_k, val) = pop_internal(bucket);
+            val
+        })
+    }
 }
 
 fn search_entry_hashed<'a, K: Eq, V>(table: &'a mut RawTable<K,V>, hash: SafeHash, k: K)
diff --git a/src/libstd/collections/hashmap/set.rs b/src/libstd/collections/hashmap/set.rs
index e4016c70320..69f3812425f 100644
--- a/src/libstd/collections/hashmap/set.rs
+++ b/src/libstd/collections/hashmap/set.rs
@@ -12,7 +12,6 @@
 
 use clone::Clone;
 use cmp::{Eq, Equiv, PartialEq};
-use collections::{Collection, Mutable, Set, MutableSet, Map, MutableMap};
 use core::kinds::Sized;
 use default::Default;
 use fmt::Show;
@@ -376,44 +375,170 @@ impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
         -> Chain<SetItems<'a, T>, SetAlgebraItems<'a, T, H>> {
         self.iter().chain(other.difference(self))
     }
-}
 
-impl<T: Eq + Hash<S>, S, H: Hasher<S>> PartialEq for HashSet<T, H> {
-    fn eq(&self, other: &HashSet<T, H>) -> bool {
-        if self.len() != other.len() { return false; }
-
-        self.iter().all(|key| other.contains(key))
-    }
-}
-
-impl<T: Eq + Hash<S>, S, H: Hasher<S>> Eq for HashSet<T, H> {}
+    /// Return the number of elements in the set
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashSet;
+    ///
+    /// let mut v = HashSet::new();
+    /// assert_eq!(v.len(), 0);
+    /// v.insert(1u);
+    /// assert_eq!(v.len(), 1);
+    /// ```
+    pub fn len(&self) -> uint { self.map.len() }
 
-impl<T: Eq + Hash<S>, S, H: Hasher<S>> Collection for HashSet<T, H> {
-    fn len(&self) -> uint { self.map.len() }
-}
+    /// Returns true if the set contains no elements
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashSet;
+    ///
+    /// let mut v = HashSet::new();
+    /// assert!(v.is_empty());
+    /// v.insert(1u);
+    /// assert!(!v.is_empty());
+    /// ```
+    pub fn is_empty(&self) -> bool { self.map.len() == 0 }
 
-impl<T: Eq + Hash<S>, S, H: Hasher<S>> Mutable for HashSet<T, H> {
-    fn clear(&mut self) { self.map.clear() }
-}
+    /// Clears the set, removing all values.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashSet;
+    ///
+    /// let mut v = HashSet::new();
+    /// v.insert(1u);
+    /// v.clear();
+    /// assert!(v.is_empty());
+    /// ```
+    pub fn clear(&mut self) { self.map.clear() }
 
-impl<T: Eq + Hash<S>, S, H: Hasher<S>> Set<T> for HashSet<T, H> {
-    fn contains(&self, value: &T) -> bool { self.map.contains_key(value) }
+    /// Returns `true` if the set contains a value.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashSet;
+    ///
+    /// let set: HashSet<uint> = [1, 2, 3].iter().map(|&x| x).collect();
+    /// assert_eq!(set.contains(&1), true);
+    /// assert_eq!(set.contains(&4), false);
+    /// ```
+    pub fn contains(&self, value: &T) -> bool { self.map.contains_key(value) }
 
-    fn is_disjoint(&self, other: &HashSet<T, H>) -> bool {
+    /// Returns `true` if the set has no elements in common with `other`.
+    /// This is equivalent to checking for an empty intersection.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashSet;
+    ///
+    /// let a: HashSet<uint> = [1, 2, 3].iter().map(|&x| x).collect();
+    /// let mut b: HashSet<uint> = HashSet::new();
+    ///
+    /// assert_eq!(a.is_disjoint(&b), true);
+    /// b.insert(4);
+    /// assert_eq!(a.is_disjoint(&b), true);
+    /// b.insert(1);
+    /// assert_eq!(a.is_disjoint(&b), false);
+    /// ```
+    pub fn is_disjoint(&self, other: &HashSet<T, H>) -> bool {
         self.iter().all(|v| !other.contains(v))
     }
 
-    fn is_subset(&self, other: &HashSet<T, H>) -> bool {
+    /// Returns `true` if the set is a subset of another.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashSet;
+    ///
+    /// let sup: HashSet<uint> = [1, 2, 3].iter().map(|&x| x).collect();
+    /// let mut set: HashSet<uint> = HashSet::new();
+    ///
+    /// assert_eq!(set.is_subset(&sup), true);
+    /// set.insert(2);
+    /// assert_eq!(set.is_subset(&sup), true);
+    /// set.insert(4);
+    /// assert_eq!(set.is_subset(&sup), false);
+    /// ```
+    pub fn is_subset(&self, other: &HashSet<T, H>) -> bool {
         self.iter().all(|v| other.contains(v))
     }
+
+    /// Returns `true` if the set is a superset of another.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashSet;
+    ///
+    /// let sub: HashSet<uint> = [1, 2].iter().map(|&x| x).collect();
+    /// let mut set: HashSet<uint> = HashSet::new();
+    ///
+    /// assert_eq!(set.is_superset(&sub), false);
+    ///
+    /// set.insert(0);
+    /// set.insert(1);
+    /// assert_eq!(set.is_superset(&sub), false);
+    ///
+    /// set.insert(2);
+    /// assert_eq!(set.is_superset(&sub), true);
+    /// ```
+    #[inline]
+    pub fn is_superset(&self, other: &HashSet<T, H>) -> bool {
+        other.is_subset(self)
+    }
+
+    /// Adds a value to the set. Returns `true` if the value was not already
+    /// present in the set.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashSet;
+    ///
+    /// let mut set = HashSet::new();
+    ///
+    /// assert_eq!(set.insert(2u), true);
+    /// assert_eq!(set.insert(2), false);
+    /// assert_eq!(set.len(), 1);
+    /// ```
+    pub fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
+
+    /// Removes a value from the set. Returns `true` if the value was
+    /// present in the set.
+    ///
+    /// # Example
+    ///
+    /// ```
+    /// use std::collections::HashSet;
+    ///
+    /// let mut set = HashSet::new();
+    ///
+    /// set.insert(2u);
+    /// assert_eq!(set.remove(&2), true);
+    /// assert_eq!(set.remove(&2), false);
+    /// ```
+    pub fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
 }
 
-impl<T: Eq + Hash<S>, S, H: Hasher<S>> MutableSet<T> for HashSet<T, H> {
-    fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
+impl<T: Eq + Hash<S>, S, H: Hasher<S>> PartialEq for HashSet<T, H> {
+    fn eq(&self, other: &HashSet<T, H>) -> bool {
+        if self.len() != other.len() { return false; }
 
-    fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
+        self.iter().all(|key| other.contains(key))
+    }
 }
 
+impl<T: Eq + Hash<S>, S, H: Hasher<S>> Eq for HashSet<T, H> {}
+
 impl<T: Eq + Hash<S> + fmt::Show, S, H: Hasher<S>> fmt::Show for HashSet<T, H> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         try!(write!(f, "{{"));
@@ -471,7 +596,6 @@ mod test_set {
 
     use super::HashSet;
     use slice::ImmutablePartialEqSlice;
-    use collections::Collection;
 
     #[test]
     fn test_disjoint() {
diff --git a/src/libstd/collections/lru_cache.rs b/src/libstd/collections/lru_cache.rs
index 5408e50f2bd..93e649f9355 100644
--- a/src/libstd/collections/lru_cache.rs
+++ b/src/libstd/collections/lru_cache.rs
@@ -38,7 +38,7 @@
 //! ```
 
 use cmp::{PartialEq, Eq};
-use collections::{HashMap, Collection, Mutable, MutableMap};
+use collections::HashMap;
 use fmt;
 use hash::Hash;
 use iter::{range, Iterator};
@@ -288,6 +288,15 @@ impl<K: Hash + Eq, V> LruCache<K, V> {
             (*(*node).next).prev = node;
         }
     }
+
+    /// Return the number of key-value pairs in the cache.
+    pub fn len(&self) -> uint { self.map.len() }
+
+    /// Returns whether the cache is currently empty.
+    pub fn is_empty(&self) -> bool { self.len() == 0 }
+
+    /// Clear the cache of all key-value pairs.
+    pub fn clear(&mut self) { self.map.clear(); }
 }
 
 impl<A: fmt::Show + Hash + Eq, B: fmt::Show> fmt::Show for LruCache<A, B> {
@@ -311,20 +320,6 @@ impl<A: fmt::Show + Hash + Eq, B: fmt::Show> fmt::Show for LruCache<A, B> {
     }
 }
 
-impl<K: Hash + Eq, V> Collection for LruCache<K, V> {
-    /// Return the number of key-value pairs in the cache.
-    fn len(&self) -> uint {
-        self.map.len()
-    }
-}
-
-impl<K: Hash + Eq, V> Mutable for LruCache<K, V> {
-    /// Clear the cache of all key-value pairs.
-    fn clear(&mut self) {
-        self.map.clear();
-    }
-}
-
 #[unsafe_destructor]
 impl<K, V> Drop for LruCache<K, V> {
     fn drop(&mut self) {
diff --git a/src/libstd/collections/mod.rs b/src/libstd/collections/mod.rs
index c227aa65b48..be9e22ee9d1 100644
--- a/src/libstd/collections/mod.rs
+++ b/src/libstd/collections/mod.rs
@@ -328,8 +328,6 @@
 
 #![experimental]
 
-pub use core_collections::{Collection, Mutable, Map, MutableMap};
-pub use core_collections::{Set, MutableSet, Deque, MutableSeq};
 pub use core_collections::{Bitv, BitvSet, BTreeMap, BTreeSet, DList, EnumSet};
 pub use core_collections::{PriorityQueue, RingBuf, SmallIntMap};
 pub use core_collections::{TreeMap, TreeSet, TrieMap, TrieSet};
diff --git a/src/libstd/dynamic_lib.rs b/src/libstd/dynamic_lib.rs
index ec6eef07c95..4c133fc7397 100644
--- a/src/libstd/dynamic_lib.rs
+++ b/src/libstd/dynamic_lib.rs
@@ -20,7 +20,6 @@ A simple wrapper over the platform's dynamic library facilities
 #![allow(missing_docs)]
 
 use clone::Clone;
-use collections::MutableSeq;
 use c_str::ToCStr;
 use iter::Iterator;
 use mem;
@@ -280,7 +279,6 @@ pub mod dl {
 #[cfg(target_os = "windows")]
 pub mod dl {
     use c_str::ToCStr;
-    use collections::MutableSeq;
     use iter::Iterator;
     use libc;
     use os;
diff --git a/src/libstd/io/buffered.rs b/src/libstd/io/buffered.rs
index a01787c286b..49c688da31c 100644
--- a/src/libstd/io/buffered.rs
+++ b/src/libstd/io/buffered.rs
@@ -13,7 +13,6 @@
 //! Buffering wrappers for I/O traits
 
 use cmp;
-use collections::Collection;
 use io::{Reader, Writer, Stream, Buffer, DEFAULT_BUF_SIZE, IoResult};
 use iter::ExactSize;
 use ops::Drop;
diff --git a/src/libstd/io/comm_adapters.rs b/src/libstd/io/comm_adapters.rs
index 91f3f38f89d..c925208c3ee 100644
--- a/src/libstd/io/comm_adapters.rs
+++ b/src/libstd/io/comm_adapters.rs
@@ -10,7 +10,6 @@
 
 use clone::Clone;
 use cmp;
-use collections::Collection;
 use comm::{Sender, Receiver};
 use io;
 use option::{None, Some};
diff --git a/src/libstd/io/extensions.rs b/src/libstd/io/extensions.rs
index 06ed183e936..6d0b8ebc3d9 100644
--- a/src/libstd/io/extensions.rs
+++ b/src/libstd/io/extensions.rs
@@ -15,7 +15,6 @@
 // FIXME: Not sure how this should be structured
 // FIXME: Iteration should probably be considered separately
 
-use collections::{Collection, MutableSeq};
 use io::{IoError, IoResult, Reader};
 use io;
 use iter::Iterator;
@@ -502,7 +501,6 @@ mod test {
 mod bench {
     extern crate test;
 
-    use collections::Collection;
     use prelude::*;
     use self::test::Bencher;
 
diff --git a/src/libstd/io/fs.rs b/src/libstd/io/fs.rs
index f193ce8cffa..c8524676a6d 100644
--- a/src/libstd/io/fs.rs
+++ b/src/libstd/io/fs.rs
@@ -54,7 +54,6 @@ fs::unlink(&path);
 
 use c_str::ToCStr;
 use clone::Clone;
-use collections::{Collection, MutableSeq};
 use io::standard_error;
 use io::{FilePermission, Write, UnstableFileStat, Open, FileAccess, FileMode};
 use io::{IoResult, IoError, FileStat, SeekStyle, Seek, Writer, Reader};
diff --git a/src/libstd/io/mem.rs b/src/libstd/io/mem.rs
index 2f6dd7e4795..60104365817 100644
--- a/src/libstd/io/mem.rs
+++ b/src/libstd/io/mem.rs
@@ -13,13 +13,11 @@
 //! Readers and Writers for in-memory buffers
 
 use cmp::min;
-use collections::Collection;
 use option::None;
 use result::{Err, Ok};
 use io;
 use io::{Reader, Writer, Seek, Buffer, IoError, SeekStyle, IoResult};
-use slice;
-use slice::AsSlice;
+use slice::{mod, AsSlice, ImmutableSlice};
 use vec::Vec;
 
 const BUF_CAPACITY: uint = 128;
diff --git a/src/libstd/io/mod.rs b/src/libstd/io/mod.rs
index 6d6c0c0dd75..c6f237ff1da 100644
--- a/src/libstd/io/mod.rs
+++ b/src/libstd/io/mod.rs
@@ -222,7 +222,6 @@ responding to errors that may occur while attempting to read the numbers.
 #![deny(unused_must_use)]
 
 use char::Char;
-use collections::Collection;
 use default::Default;
 use fmt;
 use int;
diff --git a/src/libstd/io/net/ip.rs b/src/libstd/io/net/ip.rs
index e93af744699..f4f3be13f66 100644
--- a/src/libstd/io/net/ip.rs
+++ b/src/libstd/io/net/ip.rs
@@ -15,13 +15,12 @@
 
 #![allow(missing_docs)]
 
-use collections::Collection;
 use fmt;
 use from_str::FromStr;
 use iter::Iterator;
 use option::{Option, None, Some};
 use str::StrSlice;
-use slice::{MutableCloneableSlice, MutableSlice};
+use slice::{MutableCloneableSlice, MutableSlice, ImmutableSlice};
 
 pub type Port = u16;
 
diff --git a/src/libstd/num/strconv.rs b/src/libstd/num/strconv.rs
index 3b17f0bc79f..30ecf2284df 100644
--- a/src/libstd/num/strconv.rs
+++ b/src/libstd/num/strconv.rs
@@ -14,7 +14,6 @@
 
 use char;
 use clone::Clone;
-use collections::{Collection, MutableSeq};
 use num::{NumCast, Zero, One, cast, Int};
 use num::{Float, FPNaN, FPInfinite, ToPrimitive};
 use num;
diff --git a/src/libstd/os.rs b/src/libstd/os.rs
index d4e6251cebe..5b3c872d2b7 100644
--- a/src/libstd/os.rs
+++ b/src/libstd/os.rs
@@ -32,7 +32,6 @@
 #![allow(non_snake_case)]
 
 use clone::Clone;
-use collections::{Collection, MutableSeq};
 use fmt;
 use io::{IoResult, IoError};
 use iter::Iterator;
diff --git a/src/libstd/path/mod.rs b/src/libstd/path/mod.rs
index 6a122990246..62105c0d90e 100644
--- a/src/libstd/path/mod.rs
+++ b/src/libstd/path/mod.rs
@@ -67,7 +67,6 @@ println!("path exists: {}", path.exists());
 
 #![experimental]
 
-use collections::{Collection, MutableSeq};
 use c_str::CString;
 use clone::Clone;
 use fmt;
diff --git a/src/libstd/path/posix.rs b/src/libstd/path/posix.rs
index 0d7a467b313..596dbfc7e63 100644
--- a/src/libstd/path/posix.rs
+++ b/src/libstd/path/posix.rs
@@ -13,7 +13,6 @@
 use c_str::{CString, ToCStr};
 use clone::Clone;
 use cmp::{PartialEq, Eq, PartialOrd, Ord, Ordering};
-use collections::{Collection, MutableSeq};
 use from_str::FromStr;
 use hash;
 use io::Writer;
diff --git a/src/libstd/path/windows.rs b/src/libstd/path/windows.rs
index 1ddc027a07e..de85748da5e 100644
--- a/src/libstd/path/windows.rs
+++ b/src/libstd/path/windows.rs
@@ -16,7 +16,6 @@ use ascii::AsciiCast;
 use c_str::{CString, ToCStr};
 use clone::Clone;
 use cmp::{PartialEq, Eq, PartialOrd, Ord, Ordering};
-use collections::{Collection, MutableSeq};
 use from_str::FromStr;
 use hash;
 use io::Writer;
diff --git a/src/libstd/prelude.rs b/src/libstd/prelude.rs
index 48be404b0d0..b2ff29c0f7e 100644
--- a/src/libstd/prelude.rs
+++ b/src/libstd/prelude.rs
@@ -65,8 +65,6 @@
 #[doc(no_inline)] pub use clone::Clone;
 #[doc(no_inline)] pub use cmp::{PartialEq, PartialOrd, Eq, Ord};
 #[doc(no_inline)] pub use cmp::{Ordering, Less, Equal, Greater, Equiv};
-#[doc(no_inline)] pub use collections::{Collection, Mutable, Map, MutableMap, MutableSeq};
-#[doc(no_inline)] pub use collections::{Set, MutableSet};
 #[doc(no_inline)] pub use iter::{FromIterator, Extendable, ExactSize};
 #[doc(no_inline)] pub use iter::{Iterator, DoubleEndedIterator};
 #[doc(no_inline)] pub use iter::{RandomAccessIterator, CloneableIterator};
diff --git a/src/libstd/rand/os.rs b/src/libstd/rand/os.rs
index bf5bdc8a308..b7b08581230 100644
--- a/src/libstd/rand/os.rs
+++ b/src/libstd/rand/os.rs
@@ -62,7 +62,6 @@ mod imp {
 mod imp {
     extern crate libc;
 
-    use collections::Collection;
     use io::{IoResult};
     use kinds::marker;
     use mem;
@@ -70,7 +69,7 @@ mod imp {
     use rand::Rng;
     use result::{Ok};
     use self::libc::{c_int, size_t};
-    use slice::MutableSlice;
+    use slice::{ImmutableSlice, MutableSlice};
 
     /// A random number generator that retrieves randomness straight from
     /// the operating system. Platform sources:
@@ -130,7 +129,6 @@ mod imp {
 mod imp {
     extern crate libc;
 
-    use core_collections::Collection;
     use io::{IoResult, IoError};
     use mem;
     use ops::Drop;
@@ -139,7 +137,7 @@ mod imp {
     use result::{Ok, Err};
     use self::libc::{DWORD, BYTE, LPCSTR, BOOL};
     use self::libc::types::os::arch::extra::{LONG_PTR};
-    use slice::MutableSlice;
+    use slice::{ImmutableSlice, MutableSlice};
 
     type HCRYPTPROV = LONG_PTR;
 
diff --git a/src/libstd/rand/reader.rs b/src/libstd/rand/reader.rs
index 4f220531237..c1bb6970f71 100644
--- a/src/libstd/rand/reader.rs
+++ b/src/libstd/rand/reader.rs
@@ -10,10 +10,10 @@
 
 //! A wrapper around any Reader to treat it as an RNG.
 
-use collections::Collection;
 use io::Reader;
 use rand::Rng;
 use result::{Ok, Err};
+use slice::ImmutableSlice;
 
 /// An RNG that reads random bytes straight from a `Reader`. This will
 /// work best with an infinite reader, but this is not required.
diff --git a/src/libstd/rt/backtrace.rs b/src/libstd/rt/backtrace.rs
index 5bd39277275..5d7aa0509c5 100644
--- a/src/libstd/rt/backtrace.rs
+++ b/src/libstd/rt/backtrace.rs
@@ -12,7 +12,6 @@
 
 #![allow(non_camel_case_types)]
 
-use collections::Collection;
 use from_str::from_str;
 use io::{IoResult, Writer};
 use iter::Iterator;
@@ -390,7 +389,6 @@ mod imp {
 
     #[cfg(not(any(target_os = "macos", target_os = "ios")))]
     fn print(w: &mut Writer, idx: int, addr: *mut libc::c_void) -> IoResult<()> {
-        use collections::Collection;
         use iter::Iterator;
         use os;
         use path::GenericPath;
@@ -659,7 +657,6 @@ mod imp {
 #[allow(dead_code, non_snake_case)]
 mod imp {
     use c_str::CString;
-    use core_collections::Collection;
     use intrinsics;
     use io::{IoResult, Writer};
     use libc;