main.rs

#![feature(if_let)]

extern crate arena;

use arena::TypedArena;
use std::cell::Cell;
use std::fmt;

type NodeRef<'a, T> = Cell<Option<&'a Node<'a, T>>>;

struct Node<'a, T: 'a> {
    pub data: T,
    pub left: NodeRef<'a, T>,
    pub right: NodeRef<'a, T>,
    pub parent: NodeRef<'a, T>,
}


impl<'a, T: Ord + fmt::Show> Node<'a, T> {
    fn new(d: T, parent: Option<&'a Node<'a, T>>) -> Node<'a, T> {
        Node { data: d, left: Cell::new(None), right: Cell::new(None), parent: Cell::new(parent) }
    }

    fn insert(&'a self, tree: &'a Tree<'a, T>, d: T) {
        match d > self.data {
            true => self.insert_right(tree, d),
            false => self.insert_left(tree, d),
        }
    }

    fn insert_right(&'a self, tree: &'a Tree<'a, T>, d: T) {
        match self.right.get() {
            None => self.right.set(Some(&*tree.nodes.alloc(Node::new(d, Some(self))))),
            Some(ref x) => x.insert(tree, d)
        }
    }

    fn insert_left(&'a self, tree: &'a Tree<'a, T>, d: T) {
        match self.left.get() {
            None => self.left.set(Some(&*tree.nodes.alloc(Node::new(d, Some(self))))),
            Some(ref x) => x.insert(tree, d)
        }
    }

    fn print_node(&self, depth: int) {
        let left = self.left.get();
        let right = self.right.get();
        let connector = match (right.is_some(), left.is_some()) {
            (true, true)   => "├",
            (true, false)  => "┘",
            (false, false) => "",
            (false, true)  => "┐"
        };

        if let Some(ref right) = right {
            right.print_node(depth + 1)
        };

        for _ in range(0, depth) { print!(" ") }
        println!{"{}{}", self.data, connector};

        if let Some(ref left) = left {
            left.print_node(depth + 1)
        };
    }

    fn depth(&self) -> u64 {
        return 1 + match (self.right.get(), self.left.get()) {
            (Some(x),Some(y)) => x.depth() + y.depth(),
            (_,Some(y)) => y.depth(),
            (Some(x),_) => x.depth(),
            (_,_) => 0,
        };
    }

}

impl<'a, T: Ord + fmt::Show> PartialEq for Node<'a, T> {
    fn eq(&self, other: &Node<'a, T>) -> bool {
        self.data.eq(&other.data)
    }
}

impl<'a, T: Ord + fmt::Show> Eq for Node<'a, T> { }

impl<'a, T: Ord + fmt::Show> PartialOrd for Node<'a, T> {
    fn partial_cmp(&self, other: &Node<'a, T>) -> Option<Ordering> {
        self.data.partial_cmp(&other.data)
    }
}

impl<'a, T: Ord + fmt::Show> Ord for Node<'a, T> {
    fn cmp(&self, other: &Node<T>) -> Ordering {
        self.data.cmp(&other.data)
    }
}

struct Tree<'a, T: Ord + fmt::Show + 'a> {
    nodes: TypedArena<Node<'a, T>>,
    pub root: Cell<Option<&'a Node<'a, T>>>,
}

impl<'a, T: Ord + fmt::Show> Tree<'a, T> {
    fn new() -> Tree<'a, T> {
        Tree { nodes: TypedArena::new(), root: Cell::new(None) }
    }

    fn insert(&'a self, d: T) {
        match self.root.get() {
            None => {
                self.root.set(Some(&*self.nodes.alloc(Node::new(d, None))));
            },
            Some(ref x) => {
                x.insert(self, d);
            }
        }
    }

    fn print_tree(&self) {
        if let Some(ref root) = self.root.get() {
            root.print_node(0);
        }
    }

    fn rebalance() {

    }
}

fn main() {
    let t = Tree::<i32>::new();

    for i in range(0i32, 25) {
        t.insert(i);
    }

    t.print_tree();
}