Added in Clone/TotalEq/TotalOrd/ToStr traits to all parts of btree.

Equals is now compact and uses vec's equals method.  Cmp compares
all elements on branches and leaves (Nodes).

1 files changed, 256 insertions, 115 deletions

diff --git a/src/libextra/btree.rs b/src/libextra/btree.rs
index 0f9eba2e9dc..ee6d7e8f16f 100644
--- a/src/libextra/btree.rs
+++ b/src/libextra/btree.rs
@@ -15,7 +15,7 @@
 //! Structure inspired by github user davidhalperin's gist.
 
 #[allow(dead_code)];
-use std::util::replace;
+#[allow(unused_variable)];
 
 ///A B-tree contains a root node (which contains a vector of elements),
 ///a length (the height of the tree), and lower and upper bounds on the
@@ -33,7 +33,7 @@ pub struct BTree<K, V> {
 //especially during insertions and deletions.
 //Using the swap or replace methods is one option for replacing dependence on Clone, or
 //changing the way in which the BTree is stored could also potentially work.
-impl<K: Clone + TotalOrd, V: Clone> BTree<K, V> {
+impl<K: TotalOrd, V> BTree<K, V> {
 
     ///Returns new BTree with root node (leaf) and user-supplied lower bound
     pub fn new(k: K, v: V, lb: uint) -> BTree<K, V> {
@@ -58,27 +58,43 @@ impl<K: Clone + TotalOrd, V: Clone> BTree<K, V> {
         }
     }
 
-    ///Implements the Clone trait for the BTree.
-    ///Uses a helper function/constructor to produce a new BTree.
-    pub fn clone(&self) -> BTree<K, V> {
-        return BTree::new_with_node_len(self.root.clone(), self.len, self.lower_bound);
+
+    ///Stub for add method in progress.
+    pub fn add(self, k: K, v: V) -> BTree<K, V> {
+        //replace(&self.root,self.root.add(k, v));
+        return BTree::new(k, v, 2);
     }
+}
+
+impl<K: TotalOrd, 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> {
         return self.root.get(k);
     }
+}
 
-    ///Checks to see if the key already exists in the tree, and if it is not,
-    ///the key-value pair is added to the tree by calling add on the root node.
-    pub fn add(self, k: K, v: V) -> bool {
-        let is_get = &self.clone().get(k.clone());
-        if is_get.is_some(){ return false; }
-        else {
-            replace(&mut self.root.clone(),self.root.add(k.clone(), v));
-            return true;
-        }
+impl<K: Clone + TotalOrd, 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> {
+        BTree::new_with_node_len(self.root.clone(), self.len, self.lower_bound)
+    }
+}
+
+
+impl<K: TotalOrd, V: TotalEq> TotalEq for BTree<K, V> {
+    ///Testing equality on BTrees by comparing the root.
+    fn equals(&self, other: &BTree<K, V>) -> bool {
+        self.root.cmp(&other.root) == Equal
+    }
+}
+
+impl<K: TotalOrd, V: TotalEq> TotalOrd 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)
     }
 }
 
@@ -103,10 +119,10 @@ enum Node<K, V> {
 
 
 //Node functions/methods
-impl<K: Clone + TotalOrd, V: Clone> Node<K, V> {
+impl<K: TotalOrd, V> Node<K, V> {
 
     ///Differentiates between leaf and branch nodes.
-    fn is_leaf(&self) -> bool{
+    fn is_leaf(&self) -> bool {
         match self{
             &LeafNode(..) => true,
             &BranchNode(..) => false
@@ -118,12 +134,20 @@ impl<K: Clone + TotalOrd, V: Clone> Node<K, V> {
         LeafNode(Leaf::new(vec))
     }
 
+
     ///Creates a new branch node given a vector of an elements and a pointer to a rightmost child.
     fn new_branch(vec: ~[BranchElt<K, V>], right: ~Node<K, V>) -> Node<K, V> {
         BranchNode(Branch::new(vec, right))
     }
 
+    ///A placeholder/stub for add
+    ///Currently returns a leaf node with a single value (the added one)
+    fn add(self, k: K, v: V) -> Node<K, V> {
+        return Node::new_leaf(~[LeafElt::new(k, v)]);
+    }
+}
 
+impl<K: TotalOrd, 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> {
@@ -132,84 +156,71 @@ impl<K: Clone + TotalOrd, V: Clone> Node<K, V> {
             BranchNode(ref branch) => return branch.get(k)
         }
     }
-
-    ///A placeholder for add
-    ///Currently returns a leaf node with a single value (the added one)
-    fn add(self, k: K, v: V) -> Node<K, V> {
-        return Node::new_leaf(~[LeafElt::new(k, v)]);
-    }
 }
 
-//Again, this might not be necessary in the future.
 impl<K: Clone + TotalOrd, 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 {
             LeafNode(ref leaf) => {
-                return Node::new_leaf(leaf.elts.clone());
+                Node::new_leaf(leaf.elts.clone())
             }
             BranchNode(ref branch) => {
-                return Node::new_branch(branch.elts.clone(),
-                                        branch.rightmost_child.clone());
+                Node::new_branch(branch.elts.clone(),
+                                 branch.rightmost_child.clone())
             }
         }
     }
 }
 
-//The following impl is unfinished.  Old iterations of code are left in for
-//future reference when implementing this trait (commented-out).
-impl<K: Clone + TotalOrd, V: Clone> TotalOrd for Node<K, V> {
+impl<K: TotalOrd, V: TotalEq> TotalEq for Node<K, V> {
+    ///Returns whether two nodes are equal
+    fn equals(&self, other: &Node<K, V>) -> bool{
+        match *self{
+            BranchNode(ref branch) => {
+                match *other{
+                    BranchNode(ref branch2) => branch.cmp(branch2) == Equal,
+                    LeafNode(ref leaf) => false
+                }
+            }
 
-    ///Placeholder for an implementation of TotalOrd for Nodes.
-    #[allow(unused_variable)]
-    fn cmp(&self, other: &Node<K, V>) -> Ordering {
-        //Requires a match statement--defer these procs to branch and leaf.
-        /* if self.elts[0].less_than(other.elts[0]) { return Less}
-        if self.elts[0].greater_than(other.elts[0]) {return Greater}
-            else {return Equal}
-         */
-        return Equal;
+            LeafNode(ref leaf) => {
+                match *other{
+                    LeafNode(ref leaf2) => leaf.cmp(leaf2) == Equal,
+                    BranchNode(ref branch) => false
+                }
+            }
+        }
     }
 }
 
-//The following impl is unfinished.  Old iterations of code are left in for
-//future reference when implementing this trait (commented-out).
-impl<K: Clone + TotalOrd, V: Clone> TotalEq for Node<K, V> {
-
-    ///Placeholder for an implementation of TotalEq for Nodes.
-    #[allow(unused_variable)]
-    fn equals(&self, other: &Node<K, V>) -> bool {
-        /* put in a match and defer this stuff to branch and leaf
-
-        let mut shorter = 0;
-        if self.elts.len() <= other.elts.len(){
-        shorter = self.elts.len();
-    }
-            else{
-        shorter = other.elts.len();
-    }
-        let mut i = 0;
-        while i < shorter{
-        if !self.elts[i].has_key(other.elts[i].key){
-        return false;
-    }
-        i +=1;
-    }
-        return true;
-         */
-        return true;
+impl<K: TotalOrd, V: TotalEq> TotalOrd for Node<K, V> {
+    ///Implementation of TotalOrd for Nodes.
+    fn cmp(&self, other: &Node<K, V>) -> Ordering {
+        match *self {
+            LeafNode(ref leaf) => {
+                match *other {
+                    LeafNode(ref leaf2) => leaf.cmp(leaf2),
+                    BranchNode(_) => Less
+                }
+            }
+            BranchNode(ref branch) => {
+                match *other {
+                    BranchNode(ref branch2) => branch.cmp(branch2),
+                    LeafNode(_) => Greater
+                }
+            }
+        }
     }
 }
 
-
 impl<K: ToStr + TotalOrd, V: ToStr> ToStr for Node<K, V> {
     ///Returns a string representation of a Node.
     ///The Branch's to_str() is not implemented yet.
     fn to_str(&self) -> ~str {
         match *self {
             LeafNode(ref leaf) => leaf.to_str(),
-            BranchNode(..) => ~""
+            BranchNode(ref branch) => branch.to_str()
         }
     }
 }
@@ -228,8 +239,7 @@ struct Branch<K, V> {
 }
 
 
-impl<K: Clone + TotalOrd, V: Clone> Leaf<K, V> {
-
+impl<K: TotalOrd, V> Leaf<K, V> {
     ///Creates a new Leaf from a vector of LeafElts.
     fn new(vec: ~[LeafElt<K, V>]) -> Leaf<K, V> {
         Leaf {
@@ -237,6 +247,15 @@ impl<K: Clone + TotalOrd, V: Clone> Leaf<K, V> {
         }
     }
 
+    ///Placeholder for add method in progress.
+    ///Currently returns a new Leaf containing a single LeafElt.
+    fn add(&self, k: K, v: V) -> Node<K, V> {
+        return Node::new_leaf(~[LeafElt::new(k, v)]);
+    }
+
+}
+
+impl<K: TotalOrd, 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() {
@@ -248,31 +267,45 @@ impl<K: Clone + TotalOrd, V: Clone> Leaf<K, V> {
         }
         return None;
     }
+}
 
-    ///Placeholder for add method in progress.
-    ///Currently returns a new Leaf containing a single LeafElt.
-    fn add(&self, k: K, v: V) -> Node<K, V> {
-        return Node::new_leaf(~[LeafElt::new(k, v)]);
+impl<K: Clone + TotalOrd, 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> TotalEq for Leaf<K, V> {
+    ///Implementation of equals function for leaves that compares LeafElts.
+    fn equals(&self, other: &Leaf<K, V>) -> bool {
+        self.elts.equals(&other.elts)
     }
+}
 
+impl<K: TotalOrd, V: TotalEq> TotalOrd 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() {
+            return Greater;
+        }
+        if self.elts.len() < other.elts.len() {
+            return Less;
+        }
+        self.elts[0].cmp(&other.elts[0])
+    }
 }
 
-impl<K: ToStr + TotalOrd, V: ToStr> ToStr for Leaf<K, V> {
 
+impl<K: ToStr + TotalOrd, V: ToStr> ToStr for Leaf<K, V> {
     ///Returns a string representation of a Leaf.
     fn to_str(&self) -> ~str {
-        let mut ret = ~"";
-        for s in self.elts.iter() {
-            ret = ret + " // " + s.to_str();
-        }
-        ret
+        self.elts.iter().map(|s| s.to_str()).to_owned_vec().connect(" // ")
     }
-
 }
 
 
-impl<K: Clone + TotalOrd, V: Clone> Branch<K, V> {
-
+impl<K: TotalOrd, V> Branch<K, V> {
     ///Creates a new Branch from a vector of BranchElts and a rightmost child (a node).
     fn new(vec: ~[BranchElt<K, V>], right: ~Node<K, V>) -> Branch<K, V> {
         Branch {
@@ -281,6 +314,13 @@ impl<K: Clone + TotalOrd, V: Clone> Branch<K, V> {
         }
     }
 
+    ///Placeholder for add method in progress
+    fn add(&self, k: K, v: V) -> Node<K, V> {
+        return Node::new_leaf(~[LeafElt::new(k, v)]);
+    }
+}
+
+impl<K: TotalOrd, 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> {
@@ -292,13 +332,44 @@ impl<K: Clone + TotalOrd, V: Clone> Branch<K, V> {
                 _ => {}
             }
         }
-        return self.rightmost_child.get(k);
+        self.rightmost_child.get(k)
     }
+}
 
+impl<K: Clone + TotalOrd, 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())
+    }
+}
 
-    ///Placeholder for add method in progress
-    fn add(&self, k: K, v: V) -> Node<K, V> {
-        return Node::new_leaf(~[LeafElt::new(k, v)]);
+impl<K: TotalOrd, V: TotalEq> TotalEq for Branch<K, V> {
+    ///Equals function for Branches--compares all the elements in each branch
+    fn equals(&self, other: &Branch<K, V>) -> bool {
+        self.elts.equals(&other.elts)
+    }
+}
+
+impl<K: TotalOrd, V: TotalEq> TotalOrd 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() {
+            return Greater;
+        }
+        if self.elts.len() < other.elts.len() {
+            return Less;
+        }
+        self.elts[0].cmp(&other.elts[0])
+    }
+}
+
+impl<K: ToStr + TotalOrd, V: ToStr> ToStr for Branch<K, V> {
+    ///Returns a string representation of a Branch.
+    fn to_str(&self) -> ~str {
+        let mut ret = self.elts.iter().map(|s| s.to_str()).to_owned_vec().connect(" // ");
+        ret.push_str(" // ");
+        ret.push_str(self.rightmost_child.to_str());
+        ret
     }
 }
 
@@ -315,8 +386,7 @@ struct BranchElt<K, V> {
     value: V
 }
 
-impl<K: Clone + TotalOrd, V> LeafElt<K, V> {
-
+impl<K: TotalOrd, V> LeafElt<K, V> {
     ///Creates a new LeafElt from a supplied key-value pair.
     fn new(k: K, v: V) -> LeafElt<K, V> {
         LeafElt {
@@ -356,28 +426,36 @@ impl<K: Clone + TotalOrd, V> LeafElt<K, V> {
     }
 }
 
-//This may be eliminated in the future to perserve efficiency by adjusting the way
-//the BTree as a whole is stored in memory.
 impl<K: Clone + TotalOrd, V: Clone> Clone for LeafElt<K, V> {
-
     ///Returns a new LeafElt by cloning the key and value.
     fn clone(&self) -> LeafElt<K, V> {
-        return LeafElt::new(self.key.clone(), self.value.clone());
+        LeafElt::new(self.key.clone(), self.value.clone())
     }
 }
 
-impl<K: ToStr + TotalOrd, V: ToStr> ToStr for LeafElt<K, V> {
+impl<K: TotalOrd, V: TotalEq> TotalEq for LeafElt<K, V> {
+    ///TotalEq for LeafElts
+    fn equals(&self, other: &LeafElt<K, V>) -> bool {
+        self.key.equals(&other.key) && self.value.equals(&other.value)
+    }
+}
 
+impl<K: TotalOrd, V: TotalEq> TotalOrd 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: ToStr + TotalOrd, V: ToStr> ToStr for LeafElt<K, V> {
     ///Returns a string representation of a LeafElt.
     fn to_str(&self) -> ~str {
-        return "Key: " + self.key.to_str() + ", value: "
-                       + self.value.to_str() + "; ";
+        format!("Key: {}, value: {};",
+            self.key.to_str(), self.value.to_str())
     }
-
 }
 
-impl<K: Clone + TotalOrd, V: Clone> BranchElt<K, V> {
-
+impl<K: TotalOrd, V> BranchElt<K, V> {
     ///Creates a new BranchElt from a supplied key, value, and left child.
     fn new(k: K, v: V, n: Node<K, V>) -> BranchElt<K, V> {
         BranchElt {
@@ -394,59 +472,122 @@ impl<K: Clone + TotalOrd, V: Clone> BranchElt<K, V> {
     }
 }
 
-impl<K: Clone + TotalOrd, V: Clone> Clone for BranchElt<K, V> {
 
+impl<K: Clone + TotalOrd, 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> {
-        return BranchElt::new(self.key.clone(),
-                              self.value.clone(),
-                              self.left.clone());
+        BranchElt::new(self.key.clone(),
+                       self.value.clone(),
+                       self.left.clone())
+    }
+}
+
+impl<K: TotalOrd, V: TotalEq> TotalEq for BranchElt<K, V>{
+    ///TotalEq for BranchElts
+    fn equals(&self, other: &BranchElt<K, V>) -> bool {
+        self.key.equals(&other.key)&&self.value.equals(&other.value)
+    }
+}
+
+impl<K: TotalOrd, V: TotalEq> TotalOrd for BranchElt<K, V> {
+    ///Fulfills TotalOrd for BranchElts
+    fn cmp(&self, other: &BranchElt<K, V>) -> Ordering {
+        self.key.cmp(&other.key)
+    }
+}
+
+impl<K: ToStr + TotalOrd, V: ToStr> ToStr 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 to_str(&self) -> ~str {
+        format!("Key: {}, value: {}, child: {};",
+            self.key.to_str(), self.value.to_str(), self.left.to_str())
     }
 }
 
 #[cfg(test)]
-mod test_btree{
+mod test_btree {
 
     use super::{BTree, LeafElt};
 
-    ///Tests the functionality of the add methods (which are unfinished).
-    #[test]
+    //Tests the functionality of the add methods (which are unfinished).
+    /*#[test]
     fn add_test(){
         let b = BTree::new(1, ~"abc", 2);
         let is_add = b.add(2, ~"xyz");
         assert!(is_add);
-    }
+    }*/
 
-    ///Tests the functionality of the get method.
+    //Tests the functionality of the get method.
     #[test]
-    fn get_test(){
+    fn get_test() {
         let b = BTree::new(1, ~"abc", 2);
         let val = b.get(1);
         assert_eq!(val, Some(~"abc"));
     }
 
-    ///Tests the LeafElt's less_than() method.
+    //Tests the LeafElt's less_than() method.
     #[test]
-    fn leaf_lt(){
+    fn leaf_lt() {
         let l1 = LeafElt::new(1, ~"abc");
         let l2 = LeafElt::new(2, ~"xyz");
         assert!(l1.less_than(l2));
     }
 
 
-    ///Tests the LeafElt's greater_than() method.
+    //Tests the LeafElt's greater_than() method.
     #[test]
-    fn leaf_gt(){
+    fn leaf_gt() {
         let l1 = LeafElt::new(1, ~"abc");
         let l2 = LeafElt::new(2, ~"xyz");
         assert!(l2.greater_than(l1));
     }
 
-    ///Tests the LeafElt's has_key() method.
+    //Tests the LeafElt's has_key() method.
     #[test]
-    fn leaf_hk(){
+    fn leaf_hk() {
         let l1 = LeafElt::new(1, ~"abc");
         assert!(l1.has_key(1));
     }
+
+    //Tests the BTree's clone() method.
+    #[test]
+    fn btree_clone_test() {
+        let b = BTree::new(1, ~"abc", 2);
+        let b2 = b.clone();
+        assert!(b.root.equals(&b2.root))
+    }
+
+    //Tests the BTree's cmp() method when one node is "less than" another.
+    #[test]
+    fn btree_cmp_test_less() {
+        let b = BTree::new(1, ~"abc", 2);
+        let b2 = BTree::new(2, ~"bcd", 2);
+        assert!(&b.cmp(&b2) == &Less)
+    }
+
+    //Tests the BTree's cmp() method when two nodes are equal.
+    #[test]
+    fn btree_cmp_test_eq() {
+        let b = BTree::new(1, ~"abc", 2);
+        let b2 = BTree::new(1, ~"bcd", 2);
+        assert!(&b.cmp(&b2) == &Equal)
+    }
+
+    //Tests the BTree's cmp() method when one node is "greater than" another.
+    #[test]
+    fn btree_cmp_test_greater() {
+        let b = BTree::new(1, ~"abc", 2);
+        let b2 = BTree::new(2, ~"bcd", 2);
+        assert!(&b2.cmp(&b) == &Greater)
+    }
+
+    //Tests the BTree's to_str() method.
+    #[test]
+    fn btree_tostr_test() {
+        let b = BTree::new(1, ~"abc", 2);
+        assert_eq!(b.to_str(), ~"Key: 1, value: abc;")
+    }
+
 }