modify_list.rs

use std::io;

struct Tree<K, V> {
    used: uint,
    nodes: [Option<TreeItem<K, V>>, ..3],
}

enum TreeItem<K, V> {
    TreeNode { key: K, value: ~Tree<K, V> },
    TreeLeaf { key: K, value: V },
}

impl<K: TotalOrd, V> Tree<K, V> {
    pub fn insert(&mut self, key: K, value: V) {
        self.used += 1;
        let (node, pos) = get_insert_node(self, key);
        io::println(fmt!("node: %?; pos: %?", node, pos));
    }
}

fn get_insert_node<K: TotalOrd, V>(tree: &mut Tree<K, V>, key: K)
        -> (&mut Tree<K, V>, uint) {
    let capacity = tree.nodes.len();

    if tree.used < capacity {
        let mut pos = 0;

        while pos < capacity {
            match tree.nodes[pos] {
                Some(TreeNode { key: ref k, value: ref mut tree }) => {
                    match key.cmp(copy k) {
                        Less => {
                            return get_insert_node(&mut **tree, key);
                        }
                        Equal => fail!("key found in node instead of leaf"),
                        Greater => { }
                    }
                }
                Some(TreeLeaf { key: ref k, value: _ }) => {
                    match key.cmp(copy k) {
                        Less => {
                            let mut i = capacity - 1;

                            while i >= pos {
                                tree.nodes.swap(i + 1, i);
                                i -= 1;
                            }

                            return (tree, pos);
                        }
                        Equal => return (tree, pos),
                        Greater => { }
                    }
                }
                None => return (tree, pos)
            }

            pos += 1;
        }

    }

    fail!("not implemented...");
}

fn main() {
    let mut tree = Tree { used: 0, nodes : [None, None, None] };

    tree.insert(1, 1);
    tree.insert(2, 2);
    tree.insert(3, 3);
}

/*
rustc -O -L. -o modify_list modify_list.rs
modify_list.rs:55:31: 55:42 error: mismatched types: expected `(&mut Tree<T,U>,uint)` but found `(&mut Tree<T,U>,uint)` (lifetime mismatch)
modify_list.rs:55                 None => return (tree, pos)
                                                 ^~~~~~~~~~~
modify_list.rs:22:35: 64:1 note: the anonymous lifetime #1 defined on the block at 22:35...
modify_list.rs:22         -> (&mut Tree<K, V>, uint) {
modify_list.rs:23     let capacity = tree.nodes.len();
modify_list.rs:24 
modify_list.rs:25     if tree.used < capacity {
modify_list.rs:26         let mut pos = 0;
modify_list.rs:27 
                  ...
modify_list.rs:22:35: 64:1 note: ...does not necessarily outlive the anonymous lifetime #2 defined on the block at 22:35
modify_list.rs:22         -> (&mut Tree<K, V>, uint) {
modify_list.rs:23     let capacity = tree.nodes.len();
modify_list.rs:24 
modify_list.rs:25     if tree.used < capacity {
modify_list.rs:26         let mut pos = 0;
modify_list.rs:27 
                  ...
modify_list.rs:49:35: 49:46 error: cannot infer an appropriate lifetime due to conflicting requirements
modify_list.rs:49                             return (tree, pos);
                                                     ^~~~~~~~~~~
modify_list.rs:22:35: 64:1 note: first, the lifetime cannot outlive the anonymous lifetime #2 defined on the block at 22:35...
modify_list.rs:22         -> (&mut Tree<K, V>, uint) {
modify_list.rs:23     let capacity = tree.nodes.len();
modify_list.rs:24 
modify_list.rs:25     if tree.used < capacity {
modify_list.rs:26         let mut pos = 0;
modify_list.rs:27 
                  ...
modify_list.rs:51:40: 51:51 note: ...due to the following expression
modify_list.rs:51                         Equal => return (tree, pos),
                                                          ^~~~~~~~~~~
modify_list.rs:22:35: 64:1 note: but, the lifetime must be valid for the anonymous lifetime #1 defined on the block at 22:35...
modify_list.rs:22         -> (&mut Tree<K, V>, uint) {
modify_list.rs:23     let capacity = tree.nodes.len();
modify_list.rs:24 
modify_list.rs:25     if tree.used < capacity {
modify_list.rs:26         let mut pos = 0;
modify_list.rs:27 
                  ...
modify_list.rs:49:35: 49:46 note: ...due to the following expression
modify_list.rs:49                             return (tree, pos);
                                                     ^~~~~~~~~~~
error: aborting due to 2 previous errors
*/