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

4 files changed, 372 insertions, 123 deletions

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};