borrow problems

rbtreestuff.rs

#[deriving(TotalEq, ToStr, Clone)]
enum Color {
    Red,
    Black
}

impl Not<Color> for Color {
    #[inline]
    fn not(&self) -> Color {
        match *self {
            Red => Black,
            Black => Red,
        }
    }
}

struct Node<K,V> {
    key: K,
    val: V,
    left: Option<~Node<K,V>>,
    right: Option<~Node<K,V>>,
    color: Color,
}

impl<K: TotalOrd, V> Node<K,V> {
    fn new(key: K, val: V) -> Node<K,V> {
        Node {
            key: key,
            val: val,
            left: None,
            right: None,
            color: Red
        }
    }


    #[inline]
    fn is_red(&self) -> bool {
        match self.color {
            Red => true,
            Black => false,
        }
    }
}

#[inline]
fn is_red<K: TotalOrd, V>(node: &Option<~Node<K, V>>) -> bool {
    match *node {
        None => false,
        Some(ref n) => n.is_red(),
    }
}

fn rot_left<K: TotalOrd, V>(node: &mut ~Node<K, V>) {
    match node.right {
        None => {}
        Some(_) => {
            let mut save = node.right.take_unwrap();
            swap(&mut node.right, &mut save.left);
            save.color = node.color;
            node.color = Red;
            swap(node, &mut save);
            node.left = Some(save);
        }
    }
}

fn rot_right<K: TotalOrd, V>(node: &mut ~Node<K, V>) {
    match node.left {
        None => {}
        Some(_) => {
            let mut save = node.left.take_unwrap();
            swap(&mut node.left, &mut save.right);
            save.color = node.color;
            node.color = Red;
            swap(node, &mut save);
            node.right = Some(save);
        }
    }
}

fn double_left<K: TotalOrd, V>(root: &mut ~Node<K,V>) {
    do root.right.map_mut |right| {
        rot_right(right);
    };

    rot_left(root);
}

fn double_right<K: TotalOrd, V>(root: &mut ~Node<K,V>) {
    do root.left.map_mut |left| {
        rot_left(left);
    };

    rot_right(root);
}

fn remove_rebalance_left<K: TotalOrd, V>(root: &mut ~Node<K, V>, done: &mut bool) {
    match root.right {
        Some(ref mut s) => {
            if !s.is_red() {
                if !is_red(&s.left) && !is_red(&s.right) {
                    if root.is_red() {
                        *done = true;
                    }
                    root.color = Black;
                    s.color = Red;
                } else {
                    let save = root.color.clone();

                    if root.right.map_default(false, |right| is_red(&right.right)) {
                        rot_left(root);
                    } else {
                        double_left(root);
                    }

                    root.color = save;
                    root.left.map_mut(|left| left.color = Black);
                    root.right.map_mut(|right| right.color = Black );

                    *done = true;
                }
            }
        }
        None => {}
    }
}