std: Drop Total from Total{Eq,Ord}

This completes the last stage of the renaming of the comparison hierarchy of
traits. This change renames TotalEq to Eq and TotalOrd to Ord.

In the future the new Eq/Ord will be filled out with their appropriate methods,
but for now this change is purely a renaming change.

[breaking-change]

7 files changed, 126 insertions, 126 deletions

diff --git a/src/libcollections/btree.rs b/src/libcollections/btree.rs
index e0bb8658c13..cebf21ee7e7 100644
--- a/src/libcollections/btree.rs
+++ b/src/libcollections/btree.rs
@@ -29,7 +29,7 @@ pub struct BTree<K, V> {
     upper_bound: uint
 }
 
-impl<K: TotalOrd, V> BTree<K, V> {
+impl<K: Ord, V> BTree<K, V> {
 
     ///Returns new BTree with root node (leaf) and user-supplied lower bound
     ///The lower bound applies to every node except the root node.
@@ -59,7 +59,7 @@ impl<K: TotalOrd, V> BTree<K, V> {
 //We would probably want to remove the dependence on the Clone trait in the future.
 //It is here as a crutch to ensure values can be passed around through the tree's nodes
 //especially during insertions and deletions.
-impl<K: Clone + TotalOrd, V: Clone> BTree<K, V> {
+impl<K: Clone + Ord, V: Clone> BTree<K, V> {
     ///Returns the value of a given key, which may not exist in the tree.
     ///Calls the root node's get method.
     pub fn get(self, k: K) -> Option<V> {
@@ -84,7 +84,7 @@ impl<K: Clone + TotalOrd, V: Clone> BTree<K, V> {
     }
 }
 
-impl<K: Clone + TotalOrd, V: Clone> Clone for BTree<K, V> {
+impl<K: Clone + Ord, V: Clone> Clone for BTree<K, V> {
     ///Implements the Clone trait for the BTree.
     ///Uses a helper function/constructor to produce a new BTree.
     fn clone(&self) -> BTree<K, V> {
@@ -92,28 +92,28 @@ impl<K: Clone + TotalOrd, V: Clone> Clone for BTree<K, V> {
     }
 }
 
-impl<K: TotalOrd, V: TotalEq> PartialEq for BTree<K, V> {
+impl<K: Ord, V: Eq> PartialEq for BTree<K, V> {
     fn eq(&self, other: &BTree<K, V>) -> bool {
         self.root.cmp(&other.root) == Equal
     }
 }
 
-impl<K: TotalOrd, V: TotalEq> TotalEq for BTree<K, V> {}
+impl<K: Ord, V: Eq> Eq for BTree<K, V> {}
 
-impl<K: TotalOrd, V: TotalEq> PartialOrd for BTree<K, V> {
+impl<K: Ord, V: Eq> PartialOrd for BTree<K, V> {
     fn lt(&self, other: &BTree<K, V>) -> bool {
         self.cmp(other) == Less
     }
 }
 
-impl<K: TotalOrd, V: TotalEq> TotalOrd for BTree<K, V> {
+impl<K: Ord, V: Eq> Ord for BTree<K, V> {
     ///Returns an ordering based on the root nodes of each BTree.
     fn cmp(&self, other: &BTree<K, V>) -> Ordering {
         self.root.cmp(&other.root)
     }
 }
 
-impl<K: fmt::Show + TotalOrd, V: fmt::Show> fmt::Show for BTree<K, V> {
+impl<K: fmt::Show + Ord, V: fmt::Show> fmt::Show for BTree<K, V> {
     ///Returns a string representation of the BTree
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         self.root.fmt(f)
@@ -133,7 +133,7 @@ enum Node<K, V> {
 
 
 //Node functions/methods
-impl<K: TotalOrd, V> Node<K, V> {
+impl<K: Ord, V> Node<K, V> {
     ///Creates a new leaf node given a vector of elements.
     fn new_leaf(vec: Vec<LeafElt<K, V>>) -> Node<K,V> {
         LeafNode(Leaf::new(vec))
@@ -164,7 +164,7 @@ impl<K: TotalOrd, V> Node<K, V> {
      }
 }
 
-impl<K: Clone + TotalOrd, V: Clone> Node<K, V> {
+impl<K: Clone + Ord, V: Clone> Node<K, V> {
     ///Returns the corresponding value to the provided key.
     ///get() is called in different ways on a branch or a leaf.
     fn get(&self, k: K) -> Option<V> {
@@ -183,7 +183,7 @@ impl<K: Clone + TotalOrd, V: Clone> Node<K, V> {
     }
 }
 
-impl<K: Clone + TotalOrd, V: Clone> Clone for Node<K, V> {
+impl<K: Clone + Ord, V: Clone> Clone for Node<K, V> {
     ///Returns a new node based on whether or not it is a branch or a leaf.
     fn clone(&self) -> Node<K, V> {
         match *self {
@@ -198,7 +198,7 @@ impl<K: Clone + TotalOrd, V: Clone> Clone for Node<K, V> {
     }
 }
 
-impl<K: TotalOrd, V: TotalEq> PartialEq for Node<K, V> {
+impl<K: Ord, V: Eq> PartialEq for Node<K, V> {
     fn eq(&self, other: &Node<K, V>) -> bool {
         match *self{
             BranchNode(ref branch) => {
@@ -220,16 +220,16 @@ impl<K: TotalOrd, V: TotalEq> PartialEq for Node<K, V> {
     }
 }
 
-impl<K: TotalOrd, V: TotalEq> TotalEq for Node<K, V> {}
+impl<K: Ord, V: Eq> Eq for Node<K, V> {}
 
-impl<K: TotalOrd, V: TotalEq> PartialOrd for Node<K, V> {
+impl<K: Ord, V: Eq> PartialOrd for Node<K, V> {
     fn lt(&self, other: &Node<K, V>) -> bool {
         self.cmp(other) == Less
     }
 }
 
-impl<K: TotalOrd, V: TotalEq> TotalOrd for Node<K, V> {
-    ///Implementation of TotalOrd for Nodes.
+impl<K: Ord, V: Eq> Ord for Node<K, V> {
+    ///Implementation of Ord for Nodes.
     fn cmp(&self, other: &Node<K, V>) -> Ordering {
         match *self {
             LeafNode(ref leaf) => {
@@ -248,7 +248,7 @@ impl<K: TotalOrd, V: TotalEq> TotalOrd for Node<K, V> {
     }
 }
 
-impl<K: fmt::Show + TotalOrd, V: fmt::Show> fmt::Show for Node<K, V> {
+impl<K: fmt::Show + Ord, V: fmt::Show> fmt::Show for Node<K, V> {
     ///Returns a string representation of a Node.
     ///Will iterate over the Node and show "Key: x, value: y, child: () // "
     ///for all elements in the Node. "Child" only exists if the Node contains
@@ -275,7 +275,7 @@ struct Branch<K, V> {
 }
 
 
-impl<K: TotalOrd, V> Leaf<K, V> {
+impl<K: Ord, V> Leaf<K, V> {
     ///Creates a new Leaf from a vector of LeafElts.
     fn new(vec: Vec<LeafElt<K, V>>) -> Leaf<K, V> {
         Leaf {
@@ -335,7 +335,7 @@ impl<K: TotalOrd, V> Leaf<K, V> {
 }
 
 
-impl<K: Clone + TotalOrd, V: Clone> Leaf<K, V> {
+impl<K: Clone + Ord, V: Clone> Leaf<K, V> {
     ///Returns the corresponding value to the supplied key.
     fn get(&self, k: K) -> Option<V> {
         for s in self.elts.iter() {
@@ -386,28 +386,28 @@ impl<K: Clone + TotalOrd, V: Clone> Leaf<K, V> {
     }
 }
 
-impl<K: Clone + TotalOrd, V: Clone> Clone for Leaf<K, V> {
+impl<K: Clone + Ord, V: Clone> Clone for Leaf<K, V> {
     ///Returns a new Leaf with the same elts.
     fn clone(&self) -> Leaf<K, V> {
         Leaf::new(self.elts.clone())
     }
 }
 
-impl<K: TotalOrd, V: TotalEq> PartialEq for Leaf<K, V> {
+impl<K: Ord, V: Eq> PartialEq for Leaf<K, V> {
     fn eq(&self, other: &Leaf<K, V>) -> bool {
         self.elts == other.elts
     }
 }
 
-impl<K: TotalOrd, V: TotalEq> TotalEq for Leaf<K, V> {}
+impl<K: Ord, V: Eq> Eq for Leaf<K, V> {}
 
-impl<K: TotalOrd, V: TotalEq> PartialOrd for Leaf<K, V> {
+impl<K: Ord, V: Eq> PartialOrd for Leaf<K, V> {
     fn lt(&self, other: &Leaf<K, V>) -> bool {
         self.cmp(other) == Less
     }
 }
 
-impl<K: TotalOrd, V: TotalEq> TotalOrd for Leaf<K, V> {
+impl<K: Ord, V: Eq> Ord for Leaf<K, V> {
     ///Returns an ordering based on the first element of each Leaf.
     fn cmp(&self, other: &Leaf<K, V>) -> Ordering {
         if self.elts.len() > other.elts.len() {
@@ -421,7 +421,7 @@ impl<K: TotalOrd, V: TotalEq> TotalOrd for Leaf<K, V> {
 }
 
 
-impl<K: fmt::Show + TotalOrd, V: fmt::Show> fmt::Show for Leaf<K, V> {
+impl<K: fmt::Show + Ord, V: fmt::Show> fmt::Show for Leaf<K, V> {
     ///Returns a string representation of a Leaf.
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         for (i, s) in self.elts.iter().enumerate() {
@@ -433,7 +433,7 @@ impl<K: fmt::Show + TotalOrd, V: fmt::Show> fmt::Show for Leaf<K, V> {
 }
 
 
-impl<K: TotalOrd, V> Branch<K, V> {
+impl<K: Ord, V> Branch<K, V> {
     ///Creates a new Branch from a vector of BranchElts and a rightmost child (a node).
     fn new(vec: Vec<BranchElt<K, V>>, right: Box<Node<K, V>>)
            -> Branch<K, V> {
@@ -492,7 +492,7 @@ impl<K: TotalOrd, V> Branch<K, V> {
     }
 }
 
-impl<K: Clone + TotalOrd, V: Clone> Branch<K, V> {
+impl<K: Clone + Ord, V: Clone> Branch<K, V> {
     ///Returns the corresponding value to the supplied key.
     ///If the key is not there, find the child that might hold it.
     fn get(&self, k: K) -> Option<V> {
@@ -616,28 +616,28 @@ impl<K: Clone + TotalOrd, V: Clone> Branch<K, V> {
     }
 }
 
-impl<K: Clone + TotalOrd, V: Clone> Clone for Branch<K, V> {
+impl<K: Clone + Ord, V: Clone> Clone for Branch<K, V> {
     ///Returns a new branch using the clone methods of the Branch's internal variables.
     fn clone(&self) -> Branch<K, V> {
         Branch::new(self.elts.clone(), self.rightmost_child.clone())
     }
 }
 
-impl<K: TotalOrd, V: TotalEq> PartialEq for Branch<K, V> {
+impl<K: Ord, V: Eq> PartialEq for Branch<K, V> {
     fn eq(&self, other: &Branch<K, V>) -> bool {
         self.elts == other.elts
     }
 }
 
-impl<K: TotalOrd, V: TotalEq> TotalEq for Branch<K, V> {}
+impl<K: Ord, V: Eq> Eq for Branch<K, V> {}
 
-impl<K: TotalOrd, V: TotalEq> PartialOrd for Branch<K, V> {
+impl<K: Ord, V: Eq> PartialOrd for Branch<K, V> {
     fn lt(&self, other: &Branch<K, V>) -> bool {
         self.cmp(other) == Less
     }
 }
 
-impl<K: TotalOrd, V: TotalEq> TotalOrd for Branch<K, V> {
+impl<K: Ord, V: Eq> Ord for Branch<K, V> {
     ///Compares the first elements of two branches to determine an ordering
     fn cmp(&self, other: &Branch<K, V>) -> Ordering {
         if self.elts.len() > other.elts.len() {
@@ -650,7 +650,7 @@ impl<K: TotalOrd, V: TotalEq> TotalOrd for Branch<K, V> {
     }
 }
 
-impl<K: fmt::Show + TotalOrd, V: fmt::Show> fmt::Show for Branch<K, V> {
+impl<K: fmt::Show + Ord, V: fmt::Show> fmt::Show for Branch<K, V> {
     ///Returns a string representation of a Branch.
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         for (i, s) in self.elts.iter().enumerate() {
@@ -674,7 +674,7 @@ struct BranchElt<K, V> {
     value: V
 }
 
-impl<K: TotalOrd, V> LeafElt<K, V> {
+impl<K: Ord, V> LeafElt<K, V> {
     ///Creates a new LeafElt from a supplied key-value pair.
     fn new(k: K, v: V) -> LeafElt<K, V> {
         LeafElt {
@@ -684,42 +684,42 @@ impl<K: TotalOrd, V> LeafElt<K, V> {
     }
 }
 
-impl<K: Clone + TotalOrd, V: Clone> Clone for LeafElt<K, V> {
+impl<K: Clone + Ord, V: Clone> Clone for LeafElt<K, V> {
     ///Returns a new LeafElt by cloning the key and value.
     fn clone(&self) -> LeafElt<K, V> {
         LeafElt::new(self.key.clone(), self.value.clone())
     }
 }
 
-impl<K: TotalOrd, V: TotalEq> PartialEq for LeafElt<K, V> {
+impl<K: Ord, V: Eq> PartialEq for LeafElt<K, V> {
     fn eq(&self, other: &LeafElt<K, V>) -> bool {
         self.key == other.key && self.value == other.value
     }
 }
 
-impl<K: TotalOrd, V: TotalEq> TotalEq for LeafElt<K, V> {}
+impl<K: Ord, V: Eq> Eq for LeafElt<K, V> {}
 
-impl<K: TotalOrd, V: TotalEq> PartialOrd for LeafElt<K, V> {
+impl<K: Ord, V: Eq> PartialOrd for LeafElt<K, V> {
     fn lt(&self, other: &LeafElt<K, V>) -> bool {
         self.cmp(other) == Less
     }
 }
 
-impl<K: TotalOrd, V: TotalEq> TotalOrd for LeafElt<K, V> {
+impl<K: Ord, V: Eq> Ord for LeafElt<K, V> {
     ///Returns an ordering based on the keys of the LeafElts.
     fn cmp(&self, other: &LeafElt<K, V>) -> Ordering {
         self.key.cmp(&other.key)
     }
 }
 
-impl<K: fmt::Show + TotalOrd, V: fmt::Show> fmt::Show for LeafElt<K, V> {
+impl<K: fmt::Show + Ord, V: fmt::Show> fmt::Show for LeafElt<K, V> {
     ///Returns a string representation of a LeafElt.
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         write!(f, "Key: {}, value: {};", self.key, self.value)
     }
 }
 
-impl<K: TotalOrd, V> BranchElt<K, V> {
+impl<K: Ord, V> BranchElt<K, V> {
     ///Creates a new BranchElt from a supplied key, value, and left child.
     fn new(k: K, v: V, n: Box<Node<K, V>>) -> BranchElt<K, V> {
         BranchElt {
@@ -731,7 +731,7 @@ impl<K: TotalOrd, V> BranchElt<K, V> {
 }
 
 
-impl<K: Clone + TotalOrd, V: Clone> Clone for BranchElt<K, V> {
+impl<K: Clone + Ord, V: Clone> Clone for BranchElt<K, V> {
     ///Returns a new BranchElt by cloning the key, value, and left child.
     fn clone(&self) -> BranchElt<K, V> {
         BranchElt::new(self.key.clone(),
@@ -740,28 +740,28 @@ impl<K: Clone + TotalOrd, V: Clone> Clone for BranchElt<K, V> {
     }
 }
 
-impl<K: TotalOrd, V: TotalEq> PartialEq for BranchElt<K, V>{
+impl<K: Ord, V: Eq> PartialEq for BranchElt<K, V>{
     fn eq(&self, other: &BranchElt<K, V>) -> bool {
         self.key == other.key && self.value == other.value
     }
 }
 
-impl<K: TotalOrd, V: TotalEq> TotalEq for BranchElt<K, V>{}
+impl<K: Ord, V: Eq> Eq for BranchElt<K, V>{}
 
-impl<K: TotalOrd, V: TotalEq> PartialOrd for BranchElt<K, V> {
+impl<K: Ord, V: Eq> PartialOrd for BranchElt<K, V> {
     fn lt(&self, other: &BranchElt<K, V>) -> bool {
         self.cmp(other) == Less
     }
 }
 
-impl<K: TotalOrd, V: TotalEq> TotalOrd for BranchElt<K, V> {
-    ///Fulfills TotalOrd for BranchElts
+impl<K: Ord, V: Eq> Ord for BranchElt<K, V> {
+    ///Fulfills Ord for BranchElts
     fn cmp(&self, other: &BranchElt<K, V>) -> Ordering {
         self.key.cmp(&other.key)
     }
 }
 
-impl<K: fmt::Show + TotalOrd, V: fmt::Show> fmt::Show for BranchElt<K, V> {
+impl<K: fmt::Show + Ord, V: fmt::Show> fmt::Show for BranchElt<K, V> {
     /// Returns string containing key, value, and child (which should recur to a
     /// leaf) Consider changing in future to be more readable.
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
diff --git a/src/libcollections/dlist.rs b/src/libcollections/dlist.rs
index d99474cf5f8..014d4e680ee 100644
--- a/src/libcollections/dlist.rs
+++ b/src/libcollections/dlist.rs
@@ -388,7 +388,7 @@ impl<T> DList<T> {
     }
 }
 
-impl<T: TotalOrd> DList<T> {
+impl<T: Ord> DList<T> {
     /// Insert `elt` sorted in ascending order
     ///
     /// O(N)
diff --git a/src/libcollections/enum_set.rs b/src/libcollections/enum_set.rs
index 797fbbcebf7..78485321aa5 100644
--- a/src/libcollections/enum_set.rs
+++ b/src/libcollections/enum_set.rs
@@ -15,7 +15,7 @@
 
 use std::num::Bitwise;
 
-#[deriving(Clone, PartialEq, TotalEq, Hash, Show)]
+#[deriving(Clone, PartialEq, Eq, Hash, Show)]
 /// A specialized Set implementation to use enum types.
 pub struct EnumSet<E> {
     // We must maintain the invariant that no bits are set
diff --git a/src/libcollections/hashmap.rs b/src/libcollections/hashmap.rs
index f535e87de5c..4eacc386306 100644
--- a/src/libcollections/hashmap.rs
+++ b/src/libcollections/hashmap.rs
@@ -12,7 +12,7 @@
 
 use std::container::{Container, Mutable, Map, MutableMap, Set, MutableSet};
 use std::clone::Clone;
-use std::cmp::{PartialEq, TotalEq, Equiv, max};
+use std::cmp::{PartialEq, Eq, Equiv, max};
 use std::default::Default;
 use std::fmt;
 use std::fmt::Show;
@@ -733,7 +733,7 @@ fn grow_at(capacity: uint, load_factor: Fraction) -> uint {
     fraction_mul(capacity, load_factor)
 }
 
-impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
+impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     /// Get the number of elements which will force the capacity to shrink.
     /// When size == self.shrink_at(), we halve the capacity.
     fn shrink_at(&self) -> uint {
@@ -925,12 +925,12 @@ impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     }
 }
 
-impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> Container for HashMap<K, V, H> {
+impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Container for HashMap<K, V, H> {
     /// Return the number of elements in the map
     fn len(&self) -> uint { self.table.size() }
 }
 
-impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> Mutable for HashMap<K, V, H> {
+impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> Mutable for HashMap<K, V, H> {
     /// Clear the map, removing all key-value pairs.
     fn clear(&mut self) {
         self.minimum_capacity = self.table.size();
@@ -945,7 +945,7 @@ impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> Mutable for HashMap<K, V, H> {
 }
 
 
-impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> Map<K, V> for HashMap<K, V, H> {
+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(|idx| {
             let (_, v) = self.table.read(&idx);
@@ -958,7 +958,7 @@ impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> Map<K, V> for HashMap<K, V, H> {
     }
 }
 
-impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> MutableMap<K, V> for HashMap<K, V, H> {
+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(k) {
             None => None,
@@ -1027,7 +1027,7 @@ impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> MutableMap<K, V> for HashMap<K, V
 
 }
 
-impl<K: Hash + TotalEq, V> HashMap<K, V, sip::SipHasher> {
+impl<K: Hash + Eq, V> HashMap<K, V, sip::SipHasher> {
     /// Create an empty HashMap.
     pub fn new() -> HashMap<K, V, sip::SipHasher> {
         HashMap::with_capacity(INITIAL_CAPACITY)
@@ -1042,7 +1042,7 @@ impl<K: Hash + TotalEq, V> HashMap<K, V, sip::SipHasher> {
     }
 }
 
-impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
+impl<K: Eq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     pub fn with_hasher(hasher: H) -> HashMap<K, V, H> {
         HashMap::with_capacity_and_hasher(INITIAL_CAPACITY, hasher)
     }
@@ -1390,7 +1390,7 @@ impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S>> HashMap<K, V, H> {
     }
 }
 
-impl<K: TotalEq + Hash<S>, V: Clone, S, H: Hasher<S>> HashMap<K, V, H> {
+impl<K: Eq + Hash<S>, V: Clone, S, H: Hasher<S>> HashMap<K, V, H> {
     /// Like `find`, but returns a copy of the value.
     pub fn find_copy(&self, k: &K) -> Option<V> {
         self.find(k).map(|v| (*v).clone())
@@ -1402,7 +1402,7 @@ impl<K: TotalEq + Hash<S>, V: Clone, S, H: Hasher<S>> HashMap<K, V, H> {
     }
 }
 
-impl<K: TotalEq + Hash<S>, V: PartialEq, S, H: Hasher<S>> PartialEq for HashMap<K, V, H> {
+impl<K: Eq + Hash<S>, V: PartialEq, S, H: Hasher<S>> PartialEq for HashMap<K, V, H> {
     fn eq(&self, other: &HashMap<K, V, H>) -> bool {
         if self.len() != other.len() { return false; }
 
@@ -1416,7 +1416,7 @@ impl<K: TotalEq + Hash<S>, V: PartialEq, S, H: Hasher<S>> PartialEq for HashMap<
     }
 }
 
-impl<K: TotalEq + Hash<S> + Show, V: Show, S, H: Hasher<S>> Show for HashMap<K, V, H> {
+impl<K: Eq + Hash<S> + Show, V: Show, S, H: Hasher<S>> Show for HashMap<K, V, H> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         try!(write!(f, r"\{"));
 
@@ -1429,7 +1429,7 @@ impl<K: TotalEq + Hash<S> + Show, V: Show, S, H: Hasher<S>> Show for HashMap<K,
     }
 }
 
-impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S> + Default> Default for HashMap<K, V, H> {
+impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Default for HashMap<K, V, H> {
     fn default() -> HashMap<K, V, H> {
         HashMap::with_hasher(Default::default())
     }
@@ -1453,7 +1453,7 @@ pub type Keys<'a, K, V> =
 pub type Values<'a, K, V> =
     iter::Map<'static, (&'a K, &'a V), &'a V, Entries<'a, K, V>>;
 
-impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S> + Default> FromIterator<(K, V)> for HashMap<K, V, H> {
+impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> FromIterator<(K, V)> for HashMap<K, V, H> {
     fn from_iter<T: Iterator<(K, V)>>(iter: T) -> HashMap<K, V, H> {
         let (lower, _) = iter.size_hint();
         let mut map = HashMap::with_capacity_and_hasher(lower, Default::default());
@@ -1462,7 +1462,7 @@ impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S> + Default> FromIterator<(K, V)> fo
     }
 }
 
-impl<K: TotalEq + Hash<S>, V, S, H: Hasher<S> + Default> Extendable<(K, V)> for HashMap<K, V, H> {
+impl<K: Eq + Hash<S>, V, S, H: Hasher<S> + Default> Extendable<(K, V)> for HashMap<K, V, H> {
     fn extend<T: Iterator<(K, V)>>(&mut self, mut iter: T) {
         for (k, v) in iter {
             self.insert(k, v);
@@ -1486,7 +1486,7 @@ pub struct HashSet<T, H = sip::SipHasher> {
     map: HashMap<T, (), H>
 }
 
-impl<T: TotalEq + Hash<S>, S, H: Hasher<S>> PartialEq for HashSet<T, H> {
+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; }
 
@@ -1494,15 +1494,15 @@ impl<T: TotalEq + Hash<S>, S, H: Hasher<S>> PartialEq for HashSet<T, H> {
     }
 }
 
-impl<T: TotalEq + Hash<S>, S, H: Hasher<S>> Container for HashSet<T, H> {
+impl<T: Eq + Hash<S>, S, H: Hasher<S>> Container for HashSet<T, H> {
     fn len(&self) -> uint { self.map.len() }
 }
 
-impl<T: TotalEq + Hash<S>, S, H: Hasher<S>> Mutable for HashSet<T, H> {
+impl<T: Eq + Hash<S>, S, H: Hasher<S>> Mutable for HashSet<T, H> {
     fn clear(&mut self) { self.map.clear() }
 }
 
-impl<T: TotalEq + Hash<S>, S, H: Hasher<S>> Set<T> for HashSet<T, H> {
+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) }
 
     fn is_disjoint(&self, other: &HashSet<T, H>) -> bool {
@@ -1514,13 +1514,13 @@ impl<T: TotalEq + Hash<S>, S, H: Hasher<S>> Set<T> for HashSet<T, H> {
     }
 }
 
-impl<T: TotalEq + Hash<S>, S, H: Hasher<S>> MutableSet<T> for HashSet<T, H> {
+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, ()) }
 
     fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
 }
 
-impl<T: Hash + TotalEq> HashSet<T, sip::SipHasher> {
+impl<T: Hash + Eq> HashSet<T, sip::SipHasher> {
     /// Create an empty HashSet
     pub fn new() -> HashSet<T, sip::SipHasher> {
         HashSet::with_capacity(INITIAL_CAPACITY)
@@ -1533,7 +1533,7 @@ impl<T: Hash + TotalEq> HashSet<T, sip::SipHasher> {
     }
 }
 
-impl<T: TotalEq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
+impl<T: Eq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     pub fn with_hasher(hasher: H) -> HashSet<T, H> {
         HashSet::with_capacity_and_hasher(INITIAL_CAPACITY, hasher)
     }
@@ -1603,7 +1603,7 @@ impl<T: TotalEq + Hash<S>, S, H: Hasher<S>> HashSet<T, H> {
     }
 }
 
-impl<T: TotalEq + Hash<S> + fmt::Show, S, H: Hasher<S>> fmt::Show 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, r"\{"));
 
@@ -1616,7 +1616,7 @@ impl<T: TotalEq + Hash<S> + fmt::Show, S, H: Hasher<S>> fmt::Show for HashSet<T,
     }
 }
 
-impl<T: TotalEq + Hash<S>, S, H: Hasher<S> + Default> FromIterator<T> for HashSet<T, H> {
+impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> FromIterator<T> for HashSet<T, H> {
     fn from_iter<I: Iterator<T>>(iter: I) -> HashSet<T, H> {
         let (lower, _) = iter.size_hint();
         let mut set = HashSet::with_capacity_and_hasher(lower, Default::default());
@@ -1625,7 +1625,7 @@ impl<T: TotalEq + Hash<S>, S, H: Hasher<S> + Default> FromIterator<T> for HashSe
     }
 }
 
-impl<T: TotalEq + Hash<S>, S, H: Hasher<S> + Default> Extendable<T> for HashSet<T, H> {
+impl<T: Eq + Hash<S>, S, H: Hasher<S> + Default> Extendable<T> for HashSet<T, H> {
     fn extend<I: Iterator<T>>(&mut self, mut iter: I) {
         for k in iter {
             self.insert(k);
@@ -1633,7 +1633,7 @@ impl<T: TotalEq + Hash<S>, S, H: Hasher<S> + Default> Extendable<T> for HashSet<
     }
 }
 
-impl<T: TotalEq + Hash> Default for HashSet<T, sip::SipHasher> {
+impl<T: Eq + Hash> Default for HashSet<T, sip::SipHasher> {
     fn default() -> HashSet<T> { HashSet::new() }
 }
 
@@ -1691,7 +1691,7 @@ mod test_map {
 
     local_data_key!(drop_vector: RefCell<Vec<int>>)
 
-    #[deriving(Hash, PartialEq, TotalEq)]
+    #[deriving(Hash, PartialEq, Eq)]
     struct Dropable {
         k: uint
     }
diff --git a/src/libcollections/lru_cache.rs b/src/libcollections/lru_cache.rs
index 7c8513bac32..ea25eee06d0 100644
--- a/src/libcollections/lru_cache.rs
+++ b/src/libcollections/lru_cache.rs
@@ -73,7 +73,7 @@ impl<K: PartialEq> PartialEq for KeyRef<K> {
     }
 }
 
-impl<K: TotalEq> TotalEq for KeyRef<K> {}
+impl<K: Eq> Eq for KeyRef<K> {}
 
 impl<K, V> LruEntry<K, V> {
     fn new(k: K, v: V) -> LruEntry<K, V> {
@@ -86,7 +86,7 @@ impl<K, V> LruEntry<K, V> {
     }
 }
 
-impl<K: Hash + TotalEq, V> LruCache<K, V> {
+impl<K: Hash + Eq, V> LruCache<K, V> {
     /// Create an LRU Cache that holds at most `capacity` items.
     pub fn new(capacity: uint) -> LruCache<K, V> {
         let cache = LruCache {
@@ -201,7 +201,7 @@ impl<K: Hash + TotalEq, V> LruCache<K, V> {
     }
 }
 
-impl<A: fmt::Show + Hash + TotalEq, B: fmt::Show> fmt::Show for LruCache<A, B> {
+impl<A: fmt::Show + Hash + Eq, B: fmt::Show> fmt::Show for LruCache<A, B> {
     /// Return a string that lists the key-value pairs from most-recently
     /// used to least-recently used.
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
@@ -222,14 +222,14 @@ impl<A: fmt::Show + Hash + TotalEq, B: fmt::Show> fmt::Show for LruCache<A, B> {
     }
 }
 
-impl<K: Hash + TotalEq, V> Container for LruCache<K, V> {
+impl<K: Hash + Eq, V> Container for LruCache<K, V> {
     /// Return the number of key-value pairs in the cache.
     fn len(&self) -> uint {
         self.map.len()
     }
 }
 
-impl<K: Hash + TotalEq, V> Mutable for LruCache<K, V> {
+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();
diff --git a/src/libcollections/priority_queue.rs b/src/libcollections/priority_queue.rs
index 4a0daf529de..3c1337a0382 100644
--- a/src/libcollections/priority_queue.rs
+++ b/src/libcollections/priority_queue.rs
@@ -22,17 +22,17 @@ pub struct PriorityQueue<T> {
     data: Vec<T>,
 }
 
-impl<T: TotalOrd> Container for PriorityQueue<T> {
+impl<T: Ord> Container for PriorityQueue<T> {
     /// Returns the length of the queue
     fn len(&self) -> uint { self.data.len() }
 }
 
-impl<T: TotalOrd> Mutable for PriorityQueue<T> {
+impl<T: Ord> Mutable for PriorityQueue<T> {
     /// Drop all items from the queue
     fn clear(&mut self) { self.data.truncate(0) }
 }
 
-impl<T: TotalOrd> PriorityQueue<T> {
+impl<T: Ord> PriorityQueue<T> {
     /// An iterator visiting all values in underlying vector, in
     /// arbitrary order.
     pub fn iter<'a>(&'a self) -> Items<'a, T> {
@@ -214,7 +214,7 @@ impl<'a, T> Iterator<&'a T> for Items<'a, T> {
     fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 }
 
-impl<T: TotalOrd> FromIterator<T> for PriorityQueue<T> {
+impl<T: Ord> FromIterator<T> for PriorityQueue<T> {
     fn from_iter<Iter: Iterator<T>>(iter: Iter) -> PriorityQueue<T> {
         let mut q = PriorityQueue::new();
         q.extend(iter);
@@ -222,7 +222,7 @@ impl<T: TotalOrd> FromIterator<T> for PriorityQueue<T> {
     }
 }
 
-impl<T: TotalOrd> Extendable<T> for PriorityQueue<T> {
+impl<T: Ord> Extendable<T> for PriorityQueue<T> {
     fn extend<Iter: Iterator<T>>(&mut self, mut iter: Iter) {
         let (lower, _) = iter.size_hint();
 
diff --git a/src/libcollections/treemap.rs b/src/libcollections/treemap.rs
index 98816003a37..1184c9b7b52 100644
--- a/src/libcollections/treemap.rs
+++ b/src/libcollections/treemap.rs
@@ -10,7 +10,7 @@
 
 //! An ordered map and set implemented as self-balancing binary search
 //! trees. The only requirement for the types is that the key implements
-//! `TotalOrd`.
+//! `Ord`.
 
 use std::cmp::Ordering;
 use std::fmt::Show;
@@ -43,7 +43,7 @@ pub struct TreeMap<K, V> {
     length: uint
 }
 
-impl<K: PartialEq + TotalOrd, V: PartialEq> PartialEq for TreeMap<K, V> {
+impl<K: PartialEq + Ord, V: PartialEq> PartialEq for TreeMap<K, V> {
     fn eq(&self, other: &TreeMap<K, V>) -> bool {
         self.len() == other.len() &&
             self.iter().zip(other.iter()).all(|(a, b)| a == b)
@@ -51,7 +51,7 @@ impl<K: PartialEq + TotalOrd, V: PartialEq> PartialEq for TreeMap<K, V> {
 }
 
 // Lexicographical comparison
-fn lt<K: PartialOrd + TotalOrd, V: PartialOrd>(a: &TreeMap<K, V>,
+fn lt<K: PartialOrd + Ord, V: PartialOrd>(a: &TreeMap<K, V>,
                                  b: &TreeMap<K, V>) -> bool {
     // the Zip iterator is as long as the shortest of a and b.
     for ((key_a, value_a), (key_b, value_b)) in a.iter().zip(b.iter()) {
@@ -64,12 +64,12 @@ fn lt<K: PartialOrd + TotalOrd, V: PartialOrd>(a: &TreeMap<K, V>,
     a.len() < b.len()
 }
 
-impl<K: PartialOrd + TotalOrd, V: PartialOrd> PartialOrd for TreeMap<K, V> {
+impl<K: PartialOrd + Ord, V: PartialOrd> PartialOrd for TreeMap<K, V> {
     #[inline]
     fn lt(&self, other: &TreeMap<K, V>) -> bool { lt(self, other) }
 }
 
-impl<K: TotalOrd + Show, V: Show> Show for TreeMap<K, V> {
+impl<K: Ord + Show, V: Show> Show for TreeMap<K, V> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         try!(write!(f, r"\{"));
 
@@ -82,18 +82,18 @@ impl<K: TotalOrd + Show, V: Show> Show for TreeMap<K, V> {
     }
 }
 
-impl<K: TotalOrd, V> Container for TreeMap<K, V> {
+impl<K: Ord, V> Container for TreeMap<K, V> {
     fn len(&self) -> uint { self.length }
 }
 
-impl<K: TotalOrd, V> Mutable for TreeMap<K, V> {
+impl<K: Ord, V> Mutable for TreeMap<K, V> {
     fn clear(&mut self) {
         self.root = None;
         self.length = 0
     }
 }
 
-impl<K: TotalOrd, V> Map<K, V> for TreeMap<K, V> {
+impl<K: Ord, V> Map<K, V> for TreeMap<K, V> {
     fn find<'a>(&'a self, key: &K) -> Option<&'a V> {
         let mut current: &'a Option<Box<TreeNode<K, V>>> = &self.root;
         loop {
@@ -111,7 +111,7 @@ impl<K: TotalOrd, V> Map<K, V> for TreeMap<K, V> {
     }
 }
 
-impl<K: TotalOrd, V> MutableMap<K, V> for TreeMap<K, V> {
+impl<K: Ord, V> MutableMap<K, V> for TreeMap<K, V> {
     #[inline]
     fn find_mut<'a>(&'a mut self, key: &K) -> Option<&'a mut V> {
         find_mut(&mut self.root, key)
@@ -130,7 +130,7 @@ impl<K: TotalOrd, V> MutableMap<K, V> for TreeMap<K, V> {
     }
 }
 
-impl<K: TotalOrd, V> TreeMap<K, V> {
+impl<K: Ord, V> TreeMap<K, V> {
     /// Create an empty TreeMap
     pub fn new() -> TreeMap<K, V> { TreeMap{root: None, length: 0} }
 
@@ -216,7 +216,7 @@ macro_rules! bound_setup {
 }
 
 
-impl<K: TotalOrd, V> TreeMap<K, V> {
+impl<K: Ord, V> TreeMap<K, V> {
     /// Get a lazy iterator that should be initialized using
     /// `traverse_left`/`traverse_right`/`traverse_complete`.
     fn iter_for_traversal<'a>(&'a self) -> Entries<'a, K, V> {
@@ -546,23 +546,23 @@ impl<'a, T> Iterator<&'a T> for RevSetItems<'a, T> {
 
 /// A implementation of the `Set` trait on top of the `TreeMap` container. The
 /// only requirement is that the type of the elements contained ascribes to the
-/// `TotalOrd` trait.
+/// `Ord` trait.
 #[deriving(Clone)]
 pub struct TreeSet<T> {
     map: TreeMap<T, ()>
 }
 
-impl<T: PartialEq + TotalOrd> PartialEq for TreeSet<T> {
+impl<T: PartialEq + Ord> PartialEq for TreeSet<T> {
     #[inline]
     fn eq(&self, other: &TreeSet<T>) -> bool { self.map == other.map }
 }
 
-impl<T: PartialOrd + TotalOrd> PartialOrd for TreeSet<T> {
+impl<T: PartialOrd + Ord> PartialOrd for TreeSet<T> {
     #[inline]
     fn lt(&self, other: &TreeSet<T>) -> bool { self.map < other.map }
 }
 
-impl<T: TotalOrd + Show> Show for TreeSet<T> {
+impl<T: Ord + Show> Show for TreeSet<T> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         try!(write!(f, r"\{"));
 
@@ -575,17 +575,17 @@ impl<T: TotalOrd + Show> Show for TreeSet<T> {
     }
 }
 
-impl<T: TotalOrd> Container for TreeSet<T> {
+impl<T: Ord> Container for TreeSet<T> {
     #[inline]
     fn len(&self) -> uint { self.map.len() }
 }
 
-impl<T: TotalOrd> Mutable for TreeSet<T> {
+impl<T: Ord> Mutable for TreeSet<T> {
     #[inline]
     fn clear(&mut self) { self.map.clear() }
 }
 
-impl<T: TotalOrd> Set<T> for TreeSet<T> {
+impl<T: Ord> Set<T> for TreeSet<T> {
     #[inline]
     fn contains(&self, value: &T) -> bool {
         self.map.contains_key(value)
@@ -620,7 +620,7 @@ impl<T: TotalOrd> Set<T> for TreeSet<T> {
     }
 }
 
-impl<T: TotalOrd> MutableSet<T> for TreeSet<T> {
+impl<T: Ord> MutableSet<T> for TreeSet<T> {
     #[inline]
     fn insert(&mut self, value: T) -> bool { self.map.insert(value, ()) }
 
@@ -628,7 +628,7 @@ impl<T: TotalOrd> MutableSet<T> for TreeSet<T> {
     fn remove(&mut self, value: &T) -> bool { self.map.remove(value) }
 }
 
-impl<T: TotalOrd> TreeSet<T> {
+impl<T: Ord> TreeSet<T> {
     /// Create an empty TreeSet
     #[inline]
     pub fn new() -> TreeSet<T> { TreeSet{map: TreeMap::new()} }
@@ -728,7 +728,7 @@ pub struct UnionItems<'a, T> {
 }
 
 /// Compare `x` and `y`, but return `short` if x is None and `long` if y is None
-fn cmp_opt<T: TotalOrd>(x: Option<&T>, y: Option<&T>,
+fn cmp_opt<T: Ord>(x: Option<&T>, y: Option<&T>,
                         short: Ordering, long: Ordering) -> Ordering {
     match (x, y) {
         (None    , _       ) => short,
@@ -737,7 +737,7 @@ fn cmp_opt<T: TotalOrd>(x: Option<&T>, y: Option<&T>,
     }
 }
 
-impl<'a, T: TotalOrd> Iterator<&'a T> for DifferenceItems<'a, T> {
+impl<'a, T: Ord> Iterator<&'a T> for DifferenceItems<'a, T> {
     fn next(&mut self) -> Option<&'a T> {
         loop {
             match cmp_opt(self.a.peek(), self.b.peek(), Less, Less) {
@@ -749,7 +749,7 @@ impl<'a, T: TotalOrd> Iterator<&'a T> for DifferenceItems<'a, T> {
     }
 }
 
-impl<'a, T: TotalOrd> Iterator<&'a T> for SymDifferenceItems<'a, T> {
+impl<'a, T: Ord> Iterator<&'a T> for SymDifferenceItems<'a, T> {
     fn next(&mut self) -> Option<&'a T> {
         loop {
             match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
@@ -761,7 +761,7 @@ impl<'a, T: TotalOrd> Iterator<&'a T> for SymDifferenceItems<'a, T> {
     }
 }
 
-impl<'a, T: TotalOrd> Iterator<&'a T> for IntersectionItems<'a, T> {
+impl<'a, T: Ord> Iterator<&'a T> for IntersectionItems<'a, T> {
     fn next(&mut self) -> Option<&'a T> {
         loop {
             let o_cmp = match (self.a.peek(), self.b.peek()) {
@@ -779,7 +779,7 @@ impl<'a, T: TotalOrd> Iterator<&'a T> for IntersectionItems<'a, T> {
     }
 }
 
-impl<'a, T: TotalOrd> Iterator<&'a T> for UnionItems<'a, T> {
+impl<'a, T: Ord> Iterator<&'a T> for UnionItems<'a, T> {
     fn next(&mut self) -> Option<&'a T> {
         loop {
             match cmp_opt(self.a.peek(), self.b.peek(), Greater, Less) {
@@ -803,7 +803,7 @@ struct TreeNode<K, V> {
     level: uint
 }
 
-impl<K: TotalOrd, V> TreeNode<K, V> {
+impl<K: Ord, V> TreeNode<K, V> {
     /// Creates a new tree node.
     #[inline]
     pub fn new(key: K, value: V) -> TreeNode<K, V> {
@@ -812,7 +812,7 @@ impl<K: TotalOrd, V> TreeNode<K, V> {
 }
 
 // Remove left horizontal link by rotating right
-fn skew<K: TotalOrd, V>(node: &mut Box<TreeNode<K, V>>) {
+fn skew<K: Ord, V>(node: &mut Box<TreeNode<K, V>>) {
     if node.left.as_ref().map_or(false, |x| x.level == node.level) {
         let mut save = node.left.take_unwrap();
         swap(&mut node.left, &mut save.right); // save.right now None
@@ -823,7 +823,7 @@ fn skew<K: TotalOrd, V>(node: &mut Box<TreeNode<K, V>>) {
 
 // Remove dual horizontal link by rotating left and increasing level of
 // the parent
-fn split<K: TotalOrd, V>(node: &mut Box<TreeNode<K, V>>) {
+fn split<K: Ord, V>(node: &mut Box<TreeNode<K, V>>) {
     if node.right.as_ref().map_or(false,
       |x| x.right.as_ref().map_or(false, |y| y.level == node.level)) {
         let mut save = node.right.take_unwrap();
@@ -834,7 +834,7 @@ fn split<K: TotalOrd, V>(node: &mut Box<TreeNode<K, V>>) {
     }
 }
 
-fn find_mut<'r, K: TotalOrd, V>(node: &'r mut Option<Box<TreeNode<K, V>>>,
+fn find_mut<'r, K: Ord, V>(node: &'r mut Option<Box<TreeNode<K, V>>>,
                                 key: &K)
                              -> Option<&'r mut V> {
     match *node {
@@ -849,7 +849,7 @@ fn find_mut<'r, K: TotalOrd, V>(node: &'r mut Option<Box<TreeNode<K, V>>>,
     }
 }
 
-fn insert<K: TotalOrd, V>(node: &mut Option<Box<TreeNode<K, V>>>,
+fn insert<K: Ord, V>(node: &mut Option<Box<TreeNode<K, V>>>,
                           key: K, value: V) -> Option<V> {
     match *node {
       Some(ref mut save) => {
@@ -879,9 +879,9 @@ fn insert<K: TotalOrd, V>(node: &mut Option<Box<TreeNode<K, V>>>,
     }
 }
 
-fn remove<K: TotalOrd, V>(node: &mut Option<Box<TreeNode<K, V>>>,
+fn remove<K: Ord, V>(node: &mut Option<Box<TreeNode<K, V>>>,
                           key: &K) -> Option<V> {
-    fn heir_swap<K: TotalOrd, V>(node: &mut Box<TreeNode<K, V>>,
+    fn heir_swap<K: Ord, V>(node: &mut Box<TreeNode<K, V>>,
                                  child: &mut Option<Box<TreeNode<K, V>>>) {
         // *could* be done without recursion, but it won't borrow check
         for x in child.mut_iter() {
@@ -962,7 +962,7 @@ fn remove<K: TotalOrd, V>(node: &mut Option<Box<TreeNode<K, V>>>,
     };
 }
 
-impl<K: TotalOrd, V> FromIterator<(K, V)> for TreeMap<K, V> {
+impl<K: Ord, V> FromIterator<(K, V)> for TreeMap<K, V> {
     fn from_iter<T: Iterator<(K, V)>>(iter: T) -> TreeMap<K, V> {
         let mut map = TreeMap::new();
         map.extend(iter);
@@ -970,7 +970,7 @@ impl<K: TotalOrd, V> FromIterator<(K, V)> for TreeMap<K, V> {
     }
 }
 
-impl<K: TotalOrd, V> Extendable<(K, V)> for TreeMap<K, V> {
+impl<K: Ord, V> Extendable<(K, V)> for TreeMap<K, V> {
     #[inline]
     fn extend<T: Iterator<(K, V)>>(&mut self, mut iter: T) {
         for (k, v) in iter {
@@ -979,7 +979,7 @@ impl<K: TotalOrd, V> Extendable<(K, V)> for TreeMap<K, V> {
     }
 }
 
-impl<T: TotalOrd> FromIterator<T> for TreeSet<T> {
+impl<T: Ord> FromIterator<T> for TreeSet<T> {
     fn from_iter<Iter: Iterator<T>>(iter: Iter) -> TreeSet<T> {
         let mut set = TreeSet::new();
         set.extend(iter);
@@ -987,7 +987,7 @@ impl<T: TotalOrd> FromIterator<T> for TreeSet<T> {
     }
 }
 
-impl<T: TotalOrd> Extendable<T> for TreeSet<T> {
+impl<T: Ord> Extendable<T> for TreeSet<T> {
     #[inline]
     fn extend<Iter: Iterator<T>>(&mut self, mut iter: Iter) {
         for elem in iter {
@@ -1070,7 +1070,7 @@ mod test_treemap {
         assert_eq!(m.find(&k1), Some(&v1));
     }
 
-    fn check_equal<K: PartialEq + TotalOrd, V: PartialEq>(ctrl: &[(K, V)],
+    fn check_equal<K: PartialEq + Ord, V: PartialEq>(ctrl: &[(K, V)],
                                             map: &TreeMap<K, V>) {
         assert_eq!(ctrl.is_empty(), map.is_empty());
         for x in ctrl.iter() {
@@ -1091,7 +1091,7 @@ mod test_treemap {
         }
     }
 
-    fn check_left<K: TotalOrd, V>(node: &Option<Box<TreeNode<K, V>>>,
+    fn check_left<K: Ord, V>(node: &Option<Box<TreeNode<K, V>>>,
                                   parent: &Box<TreeNode<K, V>>) {
         match *node {
           Some(ref r) => {
@@ -1104,7 +1104,7 @@ mod test_treemap {
         }
     }
 
-    fn check_right<K: TotalOrd, V>(node: &Option<Box<TreeNode<K, V>>>,
+    fn check_right<K: Ord, V>(node: &Option<Box<TreeNode<K, V>>>,
                                    parent: &Box<TreeNode<K, V>>,
                                    parent_red: bool) {
         match *node {
@@ -1121,7 +1121,7 @@ mod test_treemap {
         }
     }
 
-    fn check_structure<K: TotalOrd, V>(map: &TreeMap<K, V>) {
+    fn check_structure<K: Ord, V>(map: &TreeMap<K, V>) {
         match map.root {
           Some(ref r) => {
             check_left(&r.left, r);