可變樹的規範實現

Question

我最近開始將一個小型圖形程序從C++移植到Rust。在這裏我使用了一個四叉樹商店動態創建的地形。取決於LOD和位置，添加節點並從樹中移除節點。假設我使用Enum來表示樹，添加和刪除節點的最佳方法是什麼？

Answer 1

這方面的工作會對你有用嗎？這是我剛剛作爲示例創建的通用樹，但如果這是您的域問題（四叉樹），則可以用固定大小的替換動態矢量（Vec）。

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); 
    } 
}