AVL-Tree implementation in Rust

avl.rs

#[derive(Clone)]
enum AvlTree<T> {
    Leaf,
    Node {
        left: Box<AvlTree<T>>,
        right: Box<AvlTree<T>>,
        value: T
    }
}



impl<T: Clone> AvlTree<T> {
    fn new() -> AvlTree<T> { AvlTree::Leaf }

    fn print(tree: &AvlTree<T>) where T: std::string::ToString {
        let printer = |val: &T| (*val).to_string();
        AvlTree::print_printer(tree, &printer);
    }
    fn print_printer<P: Fn(&T) -> String>(tree: &AvlTree<T>, printer: &P) {
        AvlTree::print_indent(tree, printer, 0);
    }
    fn print_indent<P: Fn(&T) -> String>(tree: &AvlTree<T>, printer: &P, ind: i32) {
		fn indent(indentation: i32) {
            for _ in 0..indentation { print!("      "); }
        }

        match tree {
            &AvlTree::Leaf => {
                indent(ind);
                println!("|-> Leaf (no value / subtrees)");
            },
            &AvlTree::Node { ref left, ref right, ref value } => {
                indent(ind);
                println!("/-> Left subtree:");
                AvlTree::print_indent(&*left, printer, ind + 1);

                indent(ind);
                println!("|-> Value: {}", printer(value));

                indent(ind);
                println!("\\-> Right subtree:");
                AvlTree::print_indent(&*right, printer, ind + 1);
            }
        }
    }

    fn depth(tree: &AvlTree<T>) -> i64 {
        match tree {
            &AvlTree::Leaf => 0,
            &AvlTree::Node {ref left, ref right, ..} => {
                std::cmp::max(
                    AvlTree::depth(&*left),
                    AvlTree::depth(&*right)
                             ) + 1
            }
        }
    }

    fn balance_factor(left: &AvlTree<T>, right: &AvlTree<T>) -> i64 {
        AvlTree::depth(left) - AvlTree::depth(right)
    }

    fn balance_ll(tree: AvlTree<T>) -> AvlTree<T> {
        let original_tree = tree.clone();

        if let AvlTree::Node {left: t, right: u, value: v} = tree {
            let original_left = *t;

            if let AvlTree::Node {left: tl, right: ul, value: vl} = original_left {
                AvlTree::Node {
                    value: vl,
                    left: tl,
                    right: Box::new(
                        AvlTree::Node {
                            value: v,
                            left: ul,
                            right: u
                        }
                    )
                }
            } else {
                original_tree
            }
        } else {
            original_tree
        }
    }

    fn balance_rr(tree: AvlTree<T>) -> AvlTree<T> {
        let original_tree = tree.clone();

        if let AvlTree::Node {left: t, right: u, value: v} = tree {
            let original_right = *u;

            if let AvlTree::Node {left: tr, right: ur, value: vr} = original_right {
                AvlTree::Node {
                    value: vr,
                    left: Box::new(
                        AvlTree::Node {
                            value: v,
                            left: t,
                            right: tr
                        }
                    ),
                    right: ur
                }
            } else {
                original_tree
            }
        } else {
            original_tree
        }
    }

    fn balance_lr(tree: AvlTree<T>) -> AvlTree<T> {
        let original_tree = tree.clone();

        if let AvlTree::Node {left: t, right: u, value: v} = tree {
            let original_left = *t;

            if let AvlTree::Node {left: tl, right: ul, value: vl} = original_left {
                let original_left_right = *ul;

                if let AvlTree::Node {left: tlr, right: ulr, value: vlr} = original_left_right {
                    AvlTree::Node {
                        value: vlr,
                        left: Box::new(
                            AvlTree::Node {
                                value: vl,
                                left: tl,
                                right: tlr
                            }
                        ),
                        right: Box::new(
                            AvlTree::Node {
                                value: v,
                                left: ulr,
                                right: u
                            }
                        )
                    }
                } else {
                    original_tree
                }
            } else {
                original_tree
            }
        } else {
            original_tree
        }
    }

    fn balance_rl(tree: AvlTree<T>) -> AvlTree<T> {
        let original_tree = tree.clone();

        if let AvlTree::Node {left: t, right: u, value: v} = tree {
            let original_right = *u;

            if let AvlTree::Node {left: tr, right: ur, value: vr} = original_right {
                let original_right_left = *tr;

                if let AvlTree::Node {left: trl, right: url, value: vrl} = original_right_left {
                    AvlTree::Node {
                        value: vrl,
                        left: Box::new(
                            AvlTree::Node {
                                value: v,
                                left: t,
                                right: trl
                            }
                        ),
                        right: Box::new(
                            AvlTree::Node {
                                value: vr,
                                left: url,
                                right: ur
                            }
                        )
                    }
                } else {
                    original_tree
                }
            } else {
                original_tree
            }
        } else {
            original_tree
        }
    }

    fn get_value(tree: &AvlTree<T>) -> &T {
        if let &AvlTree::Node {ref value, ..} = tree {
            value
        } else {
            panic!("AvlTree::get_value called with a leaf as tree");
        }
    }

    fn insert<Comp: Fn(&T, &T) -> i32>(tree: AvlTree<T>, element: T, comp: &Comp) -> AvlTree<T> {
        let tree_clone = tree.clone();
        println!("Insert!");

        match tree {
            AvlTree::Leaf => AvlTree::Node {
                value: element.clone(),
                left: Box::new(AvlTree::Leaf),
                right: Box::new(AvlTree::Leaf)
            },
            AvlTree::Node {left, right, value} =>
                AvlTree::insert_node(tree_clone, *left, *right, value, element, comp)
        }
    }

    fn insert_node<Comp: Fn(&T, &T) -> i32>(
        original_tree: AvlTree<T>,
        left: AvlTree<T>,
        right: AvlTree<T>,
        value: T,
        element: T,
        comp: &Comp) -> AvlTree<T> {
        println!("Insert node!");

        let left_i = AvlTree::insert(left.clone(), element.clone(), comp);
        let right_i = AvlTree::insert(right.clone(), element.clone(), comp);

        if (*comp)(&element, &value) == 0 {
            original_tree
        } else if
            (*comp)(&element, &value) < 0 &&
            AvlTree::balance_factor(&left_i, &right) == 2 &&
            (*comp)(&element, AvlTree::get_value(&left)) < 0 {
                println!("1. Clause");
                AvlTree::balance_ll(AvlTree::Node {
                    left: Box::new(left_i),
                    right: Box::new(right),
                    value: value
                })
        } else if
            (*comp)(&element, &value) < 0 &&
            AvlTree::balance_factor(&left_i, &right) == 2 &&
            (*comp)(&element, AvlTree::get_value(&left)) > 0 {
                println!("2. Clause");
                AvlTree::balance_lr(AvlTree::Node {
                    left: Box::new(left_i),
                    right: Box::new(right),
                    value: value
                })
        } else if
            (*comp)(&element, &value) > 0 &&
            AvlTree::balance_factor(&left, &right_i) == -2 &&
            (*comp)(&element, AvlTree::get_value(&right)) < 0 {
                println!("3. Clause");
                AvlTree::balance_rl(AvlTree::Node {
                    left: Box::new(left),
                    right: Box::new(right_i),
                    value: value
                })
        } else if
            (*comp)(&element, &value) > 0 &&
            AvlTree::balance_factor(&left, &right_i) == -2 &&
            (*comp)(&element, AvlTree::get_value(&right)) > 0 {
                println!("4. Clause");
                AvlTree::balance_rr(AvlTree::Node {
                    left: Box::new(left),
                    right: Box::new(right_i),
                    value: value
                })
        } else if (*comp)(&element, &value) < 0 {
            println!("5. Clause");
            AvlTree::Node {
                left: Box::new(left_i),
                right: Box::new(right),
                value: value
            }
        } else if (*comp)(&element, &value) > 0 {
            println!("6. Clause");
            AvlTree::Node {
                left: Box::new(left),
                right: Box::new(right_i),
                value: value
            }
        } else {
            panic!("Error while inserting, no valid clause matched.");
        }
    }
}


fn main() {
    let mytree = AvlTree::<i32>::new();
    AvlTree::print(&mytree);
    print!("\n\n");

    let mytree = AvlTree::insert(mytree, 200, &(|a: &i32, b: &i32| -> i32 { *a - *b }));
    AvlTree::print(&mytree);
    print!("\n\n");

    let mytree = AvlTree::insert(mytree, 300, &(|a: &i32, b: &i32| -> i32 { *a - *b }));
    AvlTree::print(&mytree);
    print!("\n\n");

    let mytree = AvlTree::insert(mytree, 400, &(|a: &i32, b: &i32| -> i32 { *a - *b }));
    AvlTree::print(&mytree);
    print!("\n\n");

    let mytree = AvlTree::insert(mytree, 500, &(|a: &i32, b: &i32| -> i32 { *a - *b }));
    AvlTree::print(&mytree);
    print!("\n\n");

    let mytree = AvlTree::insert(mytree, 350, &(|a: &i32, b: &i32| -> i32 { *a - *b }));
    AvlTree::print(&mytree);
    print!("\n\n");

    let mytree = AvlTree::insert(mytree, 100, &(|a: &i32, b: &i32| -> i32 { *a - *b }));
    AvlTree::print(&mytree);
    print!("\n\n");

    let mytree = AvlTree::insert(mytree, 125, &(|a: &i32, b: &i32| -> i32 { *a - *b }));
    AvlTree::print(&mytree);
    print!("\n\n");

    let mytree = AvlTree::insert(mytree, 50, &(|a: &i32, b: &i32| -> i32 { *a - *b }));
    AvlTree::print(&mytree);
    print!("\n\n");

    let mytree = AvlTree::insert(mytree, 60, &(|a: &i32, b: &i32| -> i32 { *a - *b }));
    AvlTree::print(&mytree);
    print!("\n\n");

    let mytree = AvlTree::insert(mytree, 70, &(|a: &i32, b: &i32| -> i32 { *a - *b }));
    AvlTree::print(&mytree);
    print!("\n\n");

    let mytree = AvlTree::insert(mytree, 80, &(|a: &i32, b: &i32| -> i32 { *a - *b }));
    AvlTree::print(&mytree);
    print!("\n\n");

    let mytree = AvlTree::insert(mytree, 150, &(|a: &i32, b: &i32| -> i32 { *a - *b }));
    AvlTree::print(&mytree);
    print!("\n\n");

    let mytree = AvlTree::insert(mytree, 180, &(|a: &i32, b: &i32| -> i32 { *a - *b }));
    AvlTree::print(&mytree);
    print!("\n\n");

    let mytree = AvlTree::insert(mytree, 170, &(|a: &i32, b: &i32| -> i32 { *a - *b }));
    AvlTree::print(&mytree);
    print!("\n\n");

    let mytree = AvlTree::insert(mytree, 140, &(|a: &i32, b: &i32| -> i32 { *a - *b }));
    AvlTree::print(&mytree);
    print!("\n\n");
}