rope.rs

pub struct RopeNode<T> {
    left: Option<~RopeNode<T>>,
    right: Option<~RopeNode<T>>,
    weight: uint,
    balance_factor: int,
    height: int,
    data: Option<~[T]>
}

pub struct Rope<T> {
    root: Option<~RopeNode<T>>,
    size: uint
}

impl<T> RopeNode<T> {
    fn new_branch(left: ~RopeNode<T>, right: ~RopeNode<T>, weight: uint) -> ~RopeNode<T> {
        ~RopeNode {
            left: Some(left),
            right: Some(right),
            weight: weight,
            balance_factor: 0,
            height: 0,
            data: None
        }
    }

    fn new_leaf(data: ~[T]) -> ~RopeNode<T> {
        ~RopeNode {
            left: None,
            right: None,
            weight: data.len(),
            balance_factor: 0,
            height: 0,
            data: Some(data)
        }
    }

    fn calculate_weight(&mut self) {
        self.weight = self.subtree_weight(&self.left);
    }

    fn subtree_weight(&self, cursor: &Option<~RopeNode<T>>) -> uint {
        match *cursor {
            Some(ref node) => self.subtree_weight(&node.left) + self.subtree_weight(&node.right) + self.data_weight(&node.data),
            None => 0
        }
    }

    fn data_weight(&self, data: &Option<~[T]>) -> uint {
        match *data {
            Some(ref stuff) => stuff.len(),
            None => 0
        }
    }
}

impl<T> Rope<T> {
    pub fn new_empty() -> Rope<T> {
        Rope {
            root: None,
            size: 0
        }
    }

    pub fn new(data: ~[T]) -> Rope<T> {
        Rope {
            root: Some(RopeNode::new_leaf(data)),
            size: 1
        }
    }

    fn index(&self, cursor: &Option<~RopeNode<T>>, index: uint) -> T {
        match *cursor {
            Some(ref node) => {
                if node.weight < index {
                    self.index(&node.right, index - node.weight)
                } else {
                    match node.left {
                        Some(_) => self.index(&node.left, index),
                        None => node.data.unwrap()[index],
                        //      ^-------- cannot move out of dereference of & pointer
                    }
                }
            },
            None => fail!("Index out of bounds"),
        }
    }

    fn data_index(&self, cursor: RopeNode<T>, index: uint) -> T {
        match cursor.data {
            Some(stuff) => stuff[index],
            None => fail!("index out of bounds")
        }
    }
}