Update for modern RustHEADmaster

1 files changed, 139 insertions, 135 deletions

diff --git a/src/node.rs b/src/node.rs
index d1ba097..d2ba567 100644
--- a/src/node.rs
+++ b/src/node.rs
@@ -141,12 +141,6 @@ pub fn search_pair<'a, K:Ord,D>(key: &K, root: &'a Box<Node<K,D>>) -> Option<(&'
 }
 
 
-/// returns true iff key is stored in the tree given by root
-fn contains<K:Ord,D>(key: &K, root: &Box<Node<K,D>> ) -> bool  {
-    search(key,root).is_some()
-}
-
-
 ///returns the smallest key and value after the given key.
 pub fn min_after<'a, K:Ord,D>(key: &K, root: &'a Box<Node<K,D>>) -> Option<(&'a K,&'a D)> {
     match root.key.cmp(key){
@@ -170,17 +164,6 @@ pub fn min_pair<K:Ord,D>(root: &Box<Node<K,D>>) -> (&K,&D) {
 pub fn max_pair<K:Ord,D>(root: &Box<Node<K,D>>) -> (&K,&D) {
     root.right.as_ref().map_or((&root.key,&root.data), max_pair)
 }
-
-///returns the minimal value within this tree
-pub fn min<K:Ord,D>(root: &Box<Node<K,D>>) -> &D {
-    root.left.as_ref().map_or(&root.data, min)
-}
-
-///returns the minimal value within this tree
-pub fn max<K:Ord,D>(root: &Box<Node<K,D>>) -> &D {
-    root.right.as_ref().map_or(&root.data, max)
-}
-
 //will update_heights and rotate the node if necessary, returns the rotated node
 fn updated_node<K:Ord,D>(mut root: Box<Node<K,D>>) -> Box<Node<K,D>> {
     update_height(&mut root);
@@ -245,141 +228,162 @@ pub fn delete<K:Ord,D>(key: K, mut root: Box<Node<K,D>>) -> Option<Box<Node<K,D>
     }
     return Some(root);
 }
+#[cfg(test)]
+mod tests {
 
-fn simple_tree(size: i32) -> Box<Node<u64,i32>> {
-    let mut t = Box::new(Node::<u64,i32>{key: 1, data: 1337, height: 0, left:None, right: None});
-    for x in 2..size+1 {
-        t = insert((x as u64),1337+x-1,t)
+    ///returns the minimal value within this tree
+    pub fn min<K:Ord,D>(root: &Box<Node<K,D>>) -> &D {
+        root.left.as_ref().map_or(&root.data, min)
     }
-    t
-}
 
-fn is_sorted_left<K:Ord,D>(node: &Box<Node<K,D>>) -> bool {
-    node.left.as_ref().map_or(true, |succ| succ.key < node.key)
-}
+    ///returns the minimal value within this tree
+    pub fn max<K:Ord,D>(root: &Box<Node<K,D>>) -> &D {
+        root.right.as_ref().map_or(&root.data, max)
+    }
 
-fn is_sorted_right<K:Ord,D>(node: &Box<Node<K,D>>) -> bool {
-    node.right.as_ref().map_or(true, |succ| succ.key > node.key)
-}
+    /// returns true iff key is stored in the tree given by root
+    fn contains<K:Ord,D>(key: &K, root: &Box<Node<K,D>> ) -> bool  {
+        search(key,root).is_some()
+    }
 
-fn is_avl_node<K:Ord,D>(node: &Box<Node<K,D>>) -> bool {
-    let sorted = is_sorted_left(node) && is_sorted_right(node);
-    let balanced = node.height == cmp::max(height(&node.left),height(&node.right))+1;
-    return sorted && balanced;
-}
+    fn simple_tree(size: i32) -> Box<Node<u64,i32>> {
+        let mut t = Box::new(Node::<u64,i32>{key: 1, data: 1337, height: 0, left:None, right: None});
+        for x in 2..size+1 {
+            t = insert(x as u64,1337+x-1,t)
+        }
+        t
+    }
 
-pub fn is_avl_tree<K:Ord,D>(root: &Option<Box<Node<K,D>>>) -> bool {
-    (*root).as_ref().map_or(true, is_avl_node)
-}
+    fn is_sorted_left<K:Ord,D>(node: &Box<Node<K,D>>) -> bool {
+        node.left.as_ref().map_or(true, |succ| succ.key < node.key)
+    }
 
-#[test]
-fn simple_tree_operations() {
-    let mut t = Box::new(Node::<u64,i32>{key: 3, data: 4, height: 2,
-        left: Some(Box::new(Node::<u64,i32>{key: 2, data: 5, height:1, left: None, right: None})), 
-        right: None});
-    assert!(is_avl_node(&t));
-    assert!( contains::<u64,i32>(&3,&t) );
-    assert!( contains::<u64,i32>(&2,&t) );
-    assert!( !contains::<u64,i32>(&6,&t) );
-    assert!( !contains::<u64,i32>(&4,&t) );
-    t = insert::<u64,i32>(4,7, t);
-    t = insert::<u64,i32>(5,7, t);
-    t = insert::<u64,i32>(6,8, t);
-    assert!( contains::<u64,i32>(&4,&t) );
-    assert!( contains::<u64,i32>(&6,&t) );
-    assert!( !contains::<u64,i32>(&7,&t) );
-}
+    fn is_sorted_right<K:Ord,D>(node: &Box<Node<K,D>>) -> bool {
+        node.right.as_ref().map_or(true, |succ| succ.key > node.key)
+    }
+
+    fn is_avl_node<K:Ord,D>(node: &Box<Node<K,D>>) -> bool {
+        let sorted = is_sorted_left(node) && is_sorted_right(node);
+        let balanced = node.height == cmp::max(height(&node.left),height(&node.right))+1;
+        return sorted && balanced;
+    }
 
-#[test]
-fn rotations_on_tree(){ 
-    let mut t = Box::new(Node::<u64,i32>{key: 1, data: 1337, height: 1, left: None, right: None});
-    for i in 2..255 {
-        t = insert::<u64,i32>(i,1337, t);
+    pub fn _is_avl_tree<K:Ord,D>(root: &Option<Box<Node<K,D>>>) -> bool {
+        (*root).as_ref().map_or(true, is_avl_node)
+    }
+
+
+    use super::*;
+
+    #[test]
+    fn simple_tree_operations() {
+        let mut t = Box::new(Node::<u64,i32>{key: 3, data: 4, height: 2,
+            left: Some(Box::new(Node::<u64,i32>{key: 2, data: 5, height:1, left: None, right: None})), 
+            right: None});
         assert!(is_avl_node(&t));
+        assert!( contains::<u64,i32>(&3,&t) );
+        assert!( contains::<u64,i32>(&2,&t) );
+        assert!( !contains::<u64,i32>(&6,&t) );
+        assert!( !contains::<u64,i32>(&4,&t) );
+        t = insert::<u64,i32>(4,7, t);
+        t = insert::<u64,i32>(5,7, t);
+        t = insert::<u64,i32>(6,8, t);
+        assert!( contains::<u64,i32>(&4,&t) );
+        assert!( contains::<u64,i32>(&6,&t) );
+        assert!( !contains::<u64,i32>(&7,&t) );
     }
-    //check that the tree is indeed balanced
-    assert!(height(&Some(t)) <= 8);
-}
 
-#[test]
-fn test_drop_min(){
-    let mut t = simple_tree(3);
-    let (maybe_tree,min) = drop_min(t);
-    t = maybe_tree.expect("failure to get tree for first min delete");
-    assert!(is_avl_node(&t));
-    assert!( min.key == 1);
-    assert!(!contains::<u64,i32>(&1,&t));
-    assert!(contains::<u64,i32>(&2,&t));
-    assert!(contains::<u64,i32>(&3,&t));
-
-    let (maybe_tree,min) = drop_min(t);
-    t = maybe_tree.expect("failure to get tree for second min delete");
-    assert!(is_avl_node(&t));
-    assert!( min.key == 2);
-    assert!(!contains::<u64,i32>(&1,&t));
-    assert!(!contains::<u64,i32>(&2,&t));
-    assert!(contains::<u64,i32>(&3,&t));
-
-    let (maybe_tree,min) = drop_min(t);
-    assert!( maybe_tree.is_none() );
-    assert!( min.key == 3);
-}
+    #[test]
+    fn rotations_on_tree(){ 
+        let mut t = Box::new(Node::<u64,i32>{key: 1, data: 1337, height: 1, left: None, right: None});
+        for i in 2..255 {
+            t = insert::<u64,i32>(i,1337, t);
+            assert!(is_avl_node(&t));
+        }
+        //check that the tree is indeed balanced
+        assert!(height(&Some(t)) <= 8);
+    }
 
-#[test]
-fn test_drop_root(){
-    let mut t = simple_tree(3);
-    let maybe_tree = delete_root(t);
-    t = maybe_tree.expect("failure to get tree for first root drop");
-    assert!(is_avl_node(&t));
-    println!("{}",t.to_string());
-    assert!( t.height == 2);
-    assert!(contains::<u64,i32>(&1,&t));
-    assert!(!contains::<u64,i32>(&2,&t));
-    assert!(contains::<u64,i32>(&3,&t));
-
-    let maybe_tree = delete_root(t);
-    t = maybe_tree.expect("failure to get tree for second root drop");
-    assert!(is_avl_node(&t));
-    assert!(contains::<u64,i32>(&1,&t));
-    assert!(!contains::<u64,i32>(&2,&t));
-    assert!(!contains::<u64,i32>(&3,&t));
-
-    let maybe_tree = delete_root(t);
-    assert!( maybe_tree.is_none() );
-}
+    #[test]
+    fn test_drop_min(){
+        let mut t = simple_tree(3);
+        let (maybe_tree,min) = drop_min(t);
+        t = maybe_tree.expect("failure to get tree for first min delete");
+        assert!(is_avl_node(&t));
+        assert!( min.key == 1);
+        assert!(!contains::<u64,i32>(&1,&t));
+        assert!(contains::<u64,i32>(&2,&t));
+        assert!(contains::<u64,i32>(&3,&t));
 
-#[test]
-fn test_delete(){
-    let mut t = simple_tree(10);
-    for i in 1..10 {
-        assert!(contains::<u64,i32>(&i,&t));
-        let maybe_tree = delete(i,t);
-        t = maybe_tree.expect("failure to get tree for delete");
-        assert!(!contains::<u64,i32>(&i,&t));
+        let (maybe_tree,min) = drop_min(t);
+        t = maybe_tree.expect("failure to get tree for second min delete");
         assert!(is_avl_node(&t));
+        assert!( min.key == 2);
+        assert!(!contains::<u64,i32>(&1,&t));
+        assert!(!contains::<u64,i32>(&2,&t));
+        assert!(contains::<u64,i32>(&3,&t));
+
+        let (maybe_tree,min) = drop_min(t);
+        assert!( maybe_tree.is_none() );
+        assert!( min.key == 3);
     }
-    assert!(contains::<u64,i32>(&10,&t));
-    let maybe_tree = delete(10,t);
-    assert!(maybe_tree.is_none());
-}
 
-#[test] 
-fn test_min_max() {
-    let mut t = simple_tree(50);
-    assert_eq!(min(&t),&1337);
-    assert_eq!(max(&t),&(1337+50-1));
-    assert_eq!(max_pair(&t).0,&50);
-    assert_eq!(min_pair(&t).0,&1);
-}
+    #[test]
+    fn test_drop_root(){
+        let mut t = simple_tree(3);
+        let maybe_tree = delete_root(t);
+        t = maybe_tree.expect("failure to get tree for first root drop");
+        assert!(is_avl_node(&t));
+        println!("{}",t.to_string());
+        assert!( t.height == 2);
+        assert!(contains::<u64,i32>(&1,&t));
+        assert!(!contains::<u64,i32>(&2,&t));
+        assert!(contains::<u64,i32>(&3,&t));
+
+        let maybe_tree = delete_root(t);
+        t = maybe_tree.expect("failure to get tree for second root drop");
+        assert!(is_avl_node(&t));
+        assert!(contains::<u64,i32>(&1,&t));
+        assert!(!contains::<u64,i32>(&2,&t));
+        assert!(!contains::<u64,i32>(&3,&t));
 
-#[test]
-fn test_min_after(){
-    let t = simple_tree(50);
-    for old_key in 0..55 {
-        println!("trying value: {}", old_key);
-        match min_after(&old_key,&t) {
-            Some((k,_d)) => assert_eq!(k, &(old_key+1)),
-            None => assert!(old_key >= 50)
+        let maybe_tree = delete_root(t);
+        assert!( maybe_tree.is_none() );
+    }
+
+    #[test]
+    fn test_delete(){
+        let mut t = simple_tree(10);
+        for i in 1..10 {
+            assert!(contains::<u64,i32>(&i,&t));
+            let maybe_tree = delete(i,t);
+            t = maybe_tree.expect("failure to get tree for delete");
+            assert!(!contains::<u64,i32>(&i,&t));
+            assert!(is_avl_node(&t));
+        }
+        assert!(contains::<u64,i32>(&10,&t));
+        let maybe_tree = delete(10,t);
+        assert!(maybe_tree.is_none());
+    }
+
+    #[test] 
+    fn test_min_max() {
+        let t = simple_tree(50);
+        assert_eq!(min(&t),&1337);
+        assert_eq!(max(&t),&(1337+50-1));
+        assert_eq!(max_pair(&t).0,&50);
+        assert_eq!(min_pair(&t).0,&1);
+    }
+
+    #[test]
+    fn test_min_after(){
+        let t = simple_tree(50);
+        for old_key in 0..55 {
+            println!("trying value: {}", old_key);
+            match min_after(&old_key,&t) {
+                Some((k,_d)) => assert_eq!(k, &(old_key+1)),
+                None => assert!(old_key >= 50)
+            }
         }
     }
 }