Canonical implementation of mutable trees

Question

I have recently started porting a small graphics program from c++ to Rust. In it I make use of a quad tree store dynamically created terrain. Nodes are added and removed from the tree depending on LOD and position. Assuming I am using a Enum to represent the tree what is the best approach for adding and removing nodes?

Answer 1

Would something along these lines work for you? This is a generic tree I just made as an example, but you can replace dynamic vector (Vec) with a fixed-size one, if that's what your domain problem has (quad-tree).

use std::slice::Items;

enum Node<V> {
    Parent(Vec<Node<V>>),
    Leaf(V),
}

struct NodeIter<'a, V> {
    stack: Vec<Items<'a,Node<V>>>,
}

impl<'a, V> NodeIter<'a, V> {
    fn from(node: &'a Node<V>) -> NodeIter<'a, V> {
        let mut stack = Vec::new();
        match node {
            &Parent(ref children) => stack.push(children.iter()),
            &Leaf(_) => ()
        }
        NodeIter {
            stack: stack
        }
    }
}

impl<'a, V> Iterator<&'a V> for NodeIter<'a, V> {
    fn next(&mut self) -> Option<&'a V> {
        while !self.stack.is_empty() {
            match self.stack.mut_last().unwrap().next() {
                Some(&Parent(ref vec)) => {
                    self.stack.push(vec.iter());
                },
                Some(&Leaf(ref v)) => {
                    return Some(v)
                },
                None => {
                    self.stack.pop();
                }
            }
        }
        None
    }
}

impl<V> Node<V> {
    fn append<'a>(&'a mut self, n: Node<V>) -> Option<&'a mut Node<V>> {
        match self {
            &Parent(ref mut children) => {
                let len = children.len();
                children.push(n);
                Some(children.get_mut(len))
            },
            &Leaf(_) => None,
        }
    }

    fn retain_leafs(&mut self, f: |&V|->bool) {
        match self {
            &Parent(ref mut children) => {
                children.retain(|node| match node {
                    &Parent(_) => true,
                    &Leaf(ref v) => f(v),
                })
            },
            &Leaf(_) => (),
        }
    }

    fn iter<'a>(&'a self) -> NodeIter<'a, V> {
        NodeIter::from(self)
    }
}


fn main() {
    let mut tree: Node<int> = Parent(Vec::new());
    {
        let b1 = tree.append(Parent(Vec::new())).unwrap();
        b1.append(Leaf(1));
        b1.append(Leaf(2));
        b1.retain_leafs(|v| *v>1);
    }
    {
        let b2 = tree.append(Parent(Vec::new())).unwrap();
        b2.append(Leaf(5));
        b2.append(Leaf(6));
    }

    for val in tree.iter() {
        println!("Leaf {}", *val);
    }
}