binarytree.rs

// Simple Binary Tree implementation in Rust.
// This snippet fails to compile with the given message:
//

// Compilation started at Sat Jan 11 22:31:53

// rustc --test binarytree.rs 
// binarytree.rs:61:26: 61:32 error: mismatched types: expected `K` but found `K` (expected type parameter but found type parameter)
// binarytree.rs:61                 if key < node_k {
//                                           ^~~~~~
// binarytree.rs:62:42: 62:64 error: mismatched types: expected `~BinaryTree<K,V>` but found `~BinaryTree<K,V>` (expected type parameter but found type parameter)
// binarytree.rs:62                     Node(node_k, node_v, ~left.put(key, value), *right)
//                                                           ^~~~~~~~~~~~~~~~~~~~~~
// binarytree.rs:63:33: 63:39 error: mismatched types: expected `K` but found `K` (expected type parameter but found type parameter)
// binarytree.rs:63                 } else if key > node_k {
//                                                  ^~~~~~
// binarytree.rs:64:49: 64:72 error: mismatched types: expected `~BinaryTree<K,V>` but found `~BinaryTree<K,V>` (expected type parameter but found type parameter)
// binarytree.rs:64                     Node(node_k, node_v, *left, ~right.put(key, value))
//                                                                  ^~~~~~~~~~~~~~~~~~~~~~~
// binarytree.rs:56:9: 69:10 error: match arms have incompatible types: expected `BinaryTree<K,V>` but found `BinaryTree<K,V>` (expected type parameter but found type parameter)
// binarytree.rs:56         match *self {
// binarytree.rs:57             Nil => {
// binarytree.rs:58                 Node(key, value, ~Nil, ~Nil)
// binarytree.rs:59             }
// binarytree.rs:60             Node(node_k, node_v, ref left, ref right) => {
// binarytree.rs:61                 if key < node_k {
//                  ...
// binarytree.rs:76:27: 76:33 error: mismatched types: expected `K` but found `K` (expected type parameter but found type parameter)
// binarytree.rs:76                 if key == node_k {
//                                            ^~~~~~
// binarytree.rs:73:9: 82:10 error: mismatched types: expected `std::option::Option<V>` but found `std::option::Option<V>` (expected type parameter but found type parameter)
// binarytree.rs:73         match *self {
// binarytree.rs:74             Nil => None,
// binarytree.rs:75             Node(node_k, node_v, ref left, ref right) => {
// binarytree.rs:76                 if key == node_k {
// binarytree.rs:77                     Some(node_v)
// binarytree.rs:78                 } else {

pub enum BinaryTree<K, V> {
    Nil,
    Node(K, V, ~BinaryTree<K, V>, ~BinaryTree<K, V>)
}

pub fn new<K, V>() -> BinaryTree<K, V> {
    Nil
}

impl<K, V> Container for BinaryTree<K, V> {
    pub fn len(&self) -> uint {
        match *self {
            Nil => 0,
            Node(_, _, ref left, ref right) => left.len() + right.len() + 1
        }
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
}

impl<K, V> BinaryTree<K, V> {
    pub fn put<K:Ord, V>(&self, key: K, value: V) -> BinaryTree<K, V> {
        match *self {
            Nil => {
                Node(key, value, ~Nil, ~Nil)
            }
            Node(node_k, node_v, ref left, ref right) => {
                if key < node_k {
                    Node(node_k, node_v, ~left.put(key, value), *right)
                } else if key > node_k {
                    Node(node_k, node_v, *left, ~right.put(key, value))
                } else {
                    *self
                }
            }
        }
    }

    pub fn get<K:Ord + Eq, V>(&self, key: K) -> Option<V> {
        match *self {
            Nil => None,
            Node(node_k, node_v, ref left, ref right) => {
                if key == node_k {
                    Some(node_v)
                } else {
                    right.get(key).or(left.get(key))
                }
            }
        }
    }
}

#[cfg(test)]
mod tests {

    #[test]
    fn test_is_empty() {
        let tree: super::BinaryTree<int, int> = super::new();
        assert!(tree.len() == 0);
        assert!(tree.is_empty());
    }

    #[test]
    fn test_put() {
        let tree: super::BinaryTree<int, int> = super::new();
        tree = tree.put(5, 10);
        assert!(tree.len() == 1);
        assert!(!tree.is_empty());
        let output = tree.get(5);
        assert!(output == Some(10));
    }
}