gistfile1.rs

use std::fmt;
use std::boxed::Box;
use std::cmp::Ordering;

struct Tree<T> {
    root: Option<Box<Node<T>>>
}

pub struct Node<T> {
    left: Option<Box<Node<T>>>,
    right: Option<Box<Node<T>>>,
    key: T
}

impl<T: Ord + Eq + fmt::Display> Node<T> {
    fn new(key: T) -> Node<T> {
        Node{left: None, right: None, key: key}
    }

    fn insert(option: &mut Option<Box<Node<T>>>, key: T) -> bool {
        match *option {
            None => {
                *option = Some(Box::new(Node::new(key)));
                true
            }
            Some(ref mut node) => {
                match key.cmp(&node.key) {
                    Ordering::Less => Node::insert(&mut node.left, key),
                    Ordering::Greater => Node::insert(&mut node.right, key),
                    Ordering::Equal => false
                }
            }
        }
    }

    fn find_first<'a>(option: &'a mut Option<Box<Node<T>>>) -> &'a mut Option<Box<Node<T>>> {
        match *option {
            None => option,
            Some(ref mut node) => Node::find_first(&mut node.left)
        }
    }

//    fn remove_left(option: &mut Option<Box<Node<T>>>, key: &T) -> bool {
//        match *option {
//            None => return false,
//            Some(ref mut node) => {
//                match key.cmp(&node.key) {
//                    Ordering::Less => return Node::remove_left(&mut node.left, key),
//                    Ordering::Greater => return Node::remove_left(&mut node.right, key),
//                    Ordering::Equal => {
//                        let mut temp = std::mem::replace(&mut node.right, None);
//                        let first = Node::find_first(&mut temp);
//                        std::mem::swap(first, &mut node.left);
//                        std::mem::swap(&mut temp, option);
//                        true
//                    }
//                }
//            }
//        }
//    }


    fn remove_left(option: &mut Option<Box<Node<T>>>, key: &T) -> bool {
        let mut temp;

        match *option {
            None => return false,
            Some(ref mut node) => {
                match key.cmp(&node.key) {
                    Ordering::Less => return Node::remove_left(&mut node.left, key),
                    Ordering::Greater => return Node::remove_left(&mut node.right, key),
                    Ordering::Equal => {
                        temp = std::mem::replace(&mut node.right, None);
                        let first = Node::find_first(&mut temp);
                        std::mem::swap(first, &mut node.left)
                    }
                }
            }
        }

        std::mem::swap(&mut temp, option);
        true
    }

    fn print_all(option: &Option<Box<Node<T>>>) {
        option.as_ref().map(|node| {
            Node::print_all(&node.left);
            println!("{}", node.key);
            Node::print_all(&node.right)                    
        });
    }
}

impl<T: Ord + Eq + fmt::Display> Tree<T> {
    fn new() -> Tree<T> {
        Tree{root: None}
    }

    fn insert(&mut self, key: T) -> bool {
        Node::insert(&mut self.root, key)
    }

    fn remove_left(&mut self, key: &T) -> bool {
        Node::remove_left(&mut self.root, key)
    }

    fn print_all(&self) {
        Node::print_all(&self.root)
    }
}

fn main() {
    let mut tree = Tree::new();
    tree.insert(3);
    tree.insert(4);
    tree.insert(5);
    tree.insert(2);
    tree.insert(1);
    tree.insert(6);
    tree.remove_left(&6);
    tree.remove_left(&4);
    tree.print_all();
}