Каноническая реализация изменчивых деревьев

Question

Я недавно начал переносить небольшую графическую программу с C++ на Rust. В ней я использую квадрантное хранилище динамически созданной местности. Узлы добавляются и удаляются из дерева в зависимости от LOD и положения. Предполагая, что я использую Enum для представления дерева, что лучше всего подходит для добавления и удаления узлов?

Answer 1

Будет ли что-то в этом направлении работать для вас? Это общее дерево, которое я только что сделал в качестве примера, но вы можете заменить динамический вектор (Vec) на фиксированный размер, если это то, что проблема вашего домена (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); 
    } 
}