tree.rs

use std::mem;

type TreeRef<K, V> = Option<Box<Tree<K, V>>>;

struct Tree<K: PartialOrd, V> {
    key: K,
    val: V,
    left: TreeRef<K, V>,
    right: TreeRef<K, V>
}

macro_rules! swap {
    ( $x:ident : $t:ty = $d:expr; $v:expr => $o:expr ) => {
        {
            let mut $x: $t = $d;
            mem::swap(&mut $x, &mut $o);
            $o = $v;
        }
    };
}

fn tree_insert<K: PartialOrd, V>(t: TreeRef<K, V>, k: K, v: V) -> TreeRef<K, V> {
    return match t {
        None => Some(Box::new(Tree{key: k, val: v, left: None, right: None})),
        Some(mut node) => {
            if k == node.key {
                node.val = v;
            } else if k < node.key {
                swap!(tmp: TreeRef<K, V> = None; tree_insert(tmp, k, v) => node.left)
            } else {
                swap!(tmp: TreeRef<K, V> = None; tree_insert(tmp, k, v) => node.right)
            }
            Some(node)
        }
    }
}

fn tree_get<K: PartialOrd, V>(t: &TreeRef<K, V>, k: K) -> Option<&V> {
    return match t {
        &None => None,
        &Some(ref node) if k == node.key => Some(&node.val),
        &Some(ref node) if k < node.key => tree_get(&node.left, k),
        &Some(ref node) /*if k > node.key*/ => tree_get(&node.right, k),
    }
}

struct TreeMap<K: PartialOrd, V> {
    tree: TreeRef<K, V>
}

impl<K: PartialOrd, V> TreeMap<K, V> {
    fn new() -> Self {
        return Self{tree: None};
    }
    fn insert(self: &mut Self, key: K, val: V) {
        let mut tmp: TreeRef<K, V> = None;
        mem::swap(&mut tmp, &mut self.tree);
        self.tree = tree_insert(tmp, key, val);
    }
    fn get(self: &Self, key: K) -> Option<&V> {
        return tree_get(&self.tree, key);
    }
}

macro_rules! treemap {
    ( $( $k:expr => $v:expr ),* ) => {
        {
            let mut temp_tree = TreeMap::new();
            $(
                temp_tree.insert($k, $v);
            )*
            temp_tree
        }
    };
}

fn main() {
    let mut x = treemap!{1 => "One",
                         2 => "Two",
                         3 => "Three",
                         4 => "Four",
                         5 => "Five"};
    x.insert(3, "Tree");
    assert_eq!(x.get(1), Some(&"One"));
    assert_eq!(x.get(2), Some(&"Two"));
    assert_eq!(x.get(3), Some(&"Tree"));
    assert_eq!(x.get(4), Some(&"Four"));
    assert_eq!(x.get(5), Some(&"Five"));
    assert_eq!(x.get(6), None);
}

Updated to use generics.

Added a macro

Added a swap! macro to ease the inconvenience of having to use a temporary variable to mutate a field.