Update for modern RustHEADmaster

7 files changed, 204 insertions, 221 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..ea8c4bf
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1 @@
+/target
diff --git a/Cargo.lock b/Cargo.lock
new file mode 100644
index 0000000..f4d489c
--- /dev/null
+++ b/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 4
+
+[[package]]
+name = "avl_tree"
+version = "0.2.0"
diff --git a/Cargo.toml b/Cargo.toml
index e871ae0..ebfdb3f 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -1,8 +1,9 @@
 [package]
 name = "avl_tree"
 version = "0.2.0"
-authors = ["Cornelius Aschermann <coco@hexgolems.com>"]
+authors = ["Cornelius Aschermann <coco@hexgolems.com>", "cc <cc@localhost>"]
 description = "A simple AVL Tree implementation"
+edition = "2024"
 
 # This is a string description of the license for this package. Currently
 # crates.io will validate the license provided against a whitelist of known
@@ -11,4 +12,3 @@ description = "A simple AVL Tree implementation"
 license = "GPL-2.0"
 
 [dependencies]
-rand = "*" # Or a specific version
diff --git a/src/iterators.rs b/src/iterators.rs
index 2d7a673..23ecf03 100644
--- a/src/iterators.rs
+++ b/src/iterators.rs
@@ -1,5 +1,5 @@
-use ::tree;
-use ::node;
+use crate::tree;
+use crate::node;
 use std::collections::Bound;
 
 pub struct RangePairIter<'a, K:'a+Ord+Copy,D:'a> {
@@ -57,45 +57,50 @@ impl<'a, K:'a+Ord+Copy,D:'a> Iterator for RangePairIter<'a, K, D> {
 
 }
 
-#[test]
-fn test_iterators(){
-    let mut tree = tree::AVLTree::<u64,i32>::new();
-    tree.insert(18, 1337);
-    tree.insert(13, 1338);
-    tree.insert(17, 1339);
-    tree.insert(10, 1321);
-    tree.insert(1, 1321);
-    tree.insert(3, 1322);
-    let init_key = 0;
-    let mut iter = RangePairIter::<u64,i32>{tree: &tree, prev: Some(&init_key), from: Bound::Unbounded, to: Bound::Unbounded};
-    assert_eq!(iter.next().expect("should have a few values").0, &1);
-    assert_eq!(iter.next().expect("should have a few values").0, &3);
-    assert_eq!(iter.next().expect("should have a few values").0, &10);
-    assert_eq!(iter.next().expect("should have a few values").0, &13);
-    assert_eq!(iter.next().expect("should have a few values").0, &17);
-    assert_eq!(iter.next().expect("should have a few values").0, &18);
-    assert!(iter.next().is_none());
-
-    let mut iter = RangePairIter::new(&tree, Bound::Unbounded, Bound::Unbounded);
-    assert_eq!(iter.next().expect("should have a few values").0, &1);
-    assert_eq!(iter.next().expect("should have a few values").0, &3);
-    assert_eq!(iter.next().expect("should have a few values").0, &10);
-    assert_eq!(iter.next().expect("should have a few values").0, &13);
-    assert_eq!(iter.next().expect("should have a few values").0, &17);
-    assert_eq!(iter.next().expect("should have a few values").0, &18);
-    assert!(iter.next().is_none());
-
-    let mut iter = RangePairIter::new(&tree, Bound::Included(3), Bound::Included(17));
-    assert_eq!(iter.next().expect("should have a few values").0, &3);
-    assert_eq!(iter.next().expect("should have a few values").0, &10);
-    assert_eq!(iter.next().expect("should have a few values").0, &13);
-    assert_eq!(iter.next().expect("should have a few values").0, &17);
-    assert!(iter.next().is_none());
-
-    let mut iter = RangePairIter::new(&tree, Bound::Excluded(1), Bound::Excluded(18));
-    assert_eq!(iter.next().expect("should have a few values").0, &3);
-    assert_eq!(iter.next().expect("should have a few values").0, &10);
-    assert_eq!(iter.next().expect("should have a few values").0, &13);
-    assert_eq!(iter.next().expect("should have a few values").0, &17);
-    assert!(iter.next().is_none());
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_iterators(){
+        let mut tree = tree::AVLTree::<u64,i32>::new();
+        tree.insert(18, 1337);
+        tree.insert(13, 1338);
+        tree.insert(17, 1339);
+        tree.insert(10, 1321);
+        tree.insert(1, 1321);
+        tree.insert(3, 1322);
+        let init_key = 0;
+        let mut iter = RangePairIter::<u64,i32>{tree: &tree, prev: Some(&init_key), from: Bound::Unbounded, to: Bound::Unbounded};
+        assert_eq!(iter.next().expect("should have a few values").0, &1);
+        assert_eq!(iter.next().expect("should have a few values").0, &3);
+        assert_eq!(iter.next().expect("should have a few values").0, &10);
+        assert_eq!(iter.next().expect("should have a few values").0, &13);
+        assert_eq!(iter.next().expect("should have a few values").0, &17);
+        assert_eq!(iter.next().expect("should have a few values").0, &18);
+        assert!(iter.next().is_none());
+
+        let mut iter = RangePairIter::new(&tree, Bound::Unbounded, Bound::Unbounded);
+        assert_eq!(iter.next().expect("should have a few values").0, &1);
+        assert_eq!(iter.next().expect("should have a few values").0, &3);
+        assert_eq!(iter.next().expect("should have a few values").0, &10);
+        assert_eq!(iter.next().expect("should have a few values").0, &13);
+        assert_eq!(iter.next().expect("should have a few values").0, &17);
+        assert_eq!(iter.next().expect("should have a few values").0, &18);
+        assert!(iter.next().is_none());
+
+        let mut iter = RangePairIter::new(&tree, Bound::Included(3), Bound::Included(17));
+        assert_eq!(iter.next().expect("should have a few values").0, &3);
+        assert_eq!(iter.next().expect("should have a few values").0, &10);
+        assert_eq!(iter.next().expect("should have a few values").0, &13);
+        assert_eq!(iter.next().expect("should have a few values").0, &17);
+        assert!(iter.next().is_none());
+
+        let mut iter = RangePairIter::new(&tree, Bound::Excluded(1), Bound::Excluded(18));
+        assert_eq!(iter.next().expect("should have a few values").0, &3);
+        assert_eq!(iter.next().expect("should have a few values").0, &10);
+        assert_eq!(iter.next().expect("should have a few values").0, &13);
+        assert_eq!(iter.next().expect("should have a few values").0, &17);
+        assert!(iter.next().is_none());
+    }
 }
diff --git a/src/lib.rs b/src/lib.rs
index 7d6f732..d5da742 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,10 +1,3 @@
-//#![crate_id = "avl_tree"]
-#![crate_type = "lib"]
-#![feature(test)]
-#![feature(collections_bound)]
-#![feature(rand)]
-
-
 mod node;
 pub mod tree;
 mod iterators;
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)
+            }
         }
     }
 }
diff --git a/src/tree.rs b/src/tree.rs
index 1b7ed39..977cb78 100644
--- a/src/tree.rs
+++ b/src/tree.rs
@@ -1,9 +1,6 @@
-extern crate rand;
-extern crate test;
-
-use node::Node;
-use node::{insert,delete,search,min,max,is_avl_tree, to_string, min_pair, max_pair};
-use iterators::RangePairIter;
+use crate::node::Node;
+use crate::node::{insert,delete,search, min_pair, max_pair};
+use crate::iterators::RangePairIter;
 use std::collections::Bound;
 
 
@@ -85,7 +82,7 @@ impl <K:Ord+Copy,D> AVLTree<K,D>{
 /// assert_eq!(t.get_or(3,&2000), &2000);
 ///
 /// ```
-    pub fn get_or<'a>(&'a self, key: K, default: &'a D) -> &D{
+    pub fn get_or<'a>(&'a self, key: K, default: &'a D) -> &'a D{
         self.get(key).map_or(default, |data| data)
     }
 
@@ -166,11 +163,11 @@ impl <K:Ord+Copy,D> AVLTree<K,D>{
 /// be inclusive, exclusive or unbounded).
 /// # Examples
 /// ```
-/// #![feature(collections_bound)]
-/// # extern crate avl_tree;
+/// 
+/// 
 /// use std::collections::Bound;
 /// //[...]
-/// # let mut t=avl_tree::AVLTree::<u64,i32>::new();
+///  let mut t=avl_tree::AVLTree::<u64,i32>::new();
 /// for (key,val) in t.range(Bound::Excluded(32), Bound::Excluded(38)) {
 ///     println!("{} -> {}",key,val)
 /// }
@@ -179,28 +176,4 @@ impl <K:Ord+Copy,D> AVLTree<K,D>{
     pub fn range(&self, min: Bound<K>, max: Bound<K>) -> RangePairIter<K,D>{
         RangePairIter::new(self, min, max)
     }
-
-    fn test_avl_tree(&self) -> bool {
-        is_avl_tree(&self.root)
-    }
-}
-
-#[test]
-fn test_fuzz(){
-    let mut t = AVLTree::<u64,i32>::new();
-    for _ in 1..5000 {
-        let decision = rand::random::<bool>();
-        if  decision {
-            let to_insert = rand::random::<u64>()%500;
-            t.insert(to_insert, 1337);
-            assert!(t.contains(to_insert));
-            assert!(t.test_avl_tree());
-        } else {
-            let to_delete = rand::random::<u64>()%500;
-            t.delete(to_delete);
-            assert!(!t.contains(to_delete));
-            assert!(t.test_avl_tree());
-        };
-    };
-    return;
 }