summaryrefslogtreecommitdiff
path: root/src/node.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/node.rs')
-rw-r--r--src/node.rs274
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)
+ }
}
}
}
generated by cgit v1.2.1 (git 2.18.0) at 2025-08-22 18:10:47 +0000