Путь ссылок на древовидную структуру

Question

Я пытаюсь построить древовидную структуру и поддерживать путь при обходе дерева.

Вот код:

use std::collections::VecDeque; 

struct Node { 
    children: VecDeque<Node>, 
} 

struct Cursor<'a> { 
    path: VecDeque<&'a mut Node>, 
} 

impl<'a> Cursor<'a> { 
    fn new(n: &mut Node) -> Cursor { 
     let mut v = VecDeque::new(); 
     v.push_front(n); 
     Cursor { path: v } 
    } 

    fn go_down(&'a mut self, idx: usize) -> bool { 
     let n = match self.path[0].children.get_mut(idx) { 
      None => return false, 
      Some(x) => x 
     }; 
     self.path.push_front(n); 
     true 
    } 
} 

У меня есть два вопроса. Во-первых, компилятор предложил спецификатор времени жизни в аргументе go_down()self, но я не уверен, почему он исправляет сообщаемую проблему.

Даже при этом изменении, однако, приведенный выше код не будет скомпилирован, потому что self.path заимствован два раза. Есть ли способ поддерживать путь к узлам дерева без написания «небезопасного» кода?

Answer 1

Я закончил с подхода this answer до Recursive Data Structures in Rust. Идея заключается в том, что вы работаете с собственными объектами вместо ссылок, и вы деконструируете и восстанавливаете дерево по мере его перемещения.

Вот код, который я закончил с:

use std::collections::VecDeque; 

enum Child { Placeholder, Node(Node) } 

struct Node { 
    children: Vec<Child>, 
} 

impl Node { 
    fn swap_child(&mut self, idx: usize, c: Child) -> Option<Child> { 
     match self.children.get(idx) { 
      None => None, 
      Some(_) => { 
       self.children.push(c); 
       Some(self.children.swap_remove(idx)) 
      } 
     } 
    } 
} 

struct Cursor { 
    node: Node, 
    parents: VecDeque<(Node, usize /* index in parent */)>, 
} 

enum DescendRes { OK(Cursor), Fail(Cursor) } 
enum AscendRes { Done(Node), Cursor(Cursor) } 

impl Cursor { 
    fn new(n: Node) -> Cursor { 
     Cursor { node: n, parents: VecDeque::new() } 
    } 

    fn descent(mut self, idx: usize) -> DescendRes { 
     match self.node.swap_child(idx, Child::Placeholder) { 
      None => DescendRes::Fail(self), 
      Some(Child::Placeholder) => panic!("This should not happen"), 
      Some(Child::Node(child)) => { 
       let mut v = self.parents; 
       v.push_front((self.node, idx)); 
       DescendRes::OK(
        Cursor { node: child, parents: v } 
       ) 
      } 
     } 
    } 

    fn ascend(mut self) -> AscendRes { 
     match self.parents.pop_front() { 
      None => AscendRes::Done(self.node), 
      Some((mut parent, parent_idx)) => { 
       match parent.swap_child(parent_idx, Child::Node(self.node)) { 
        Some(Child::Placeholder) => { 
         AscendRes::Cursor(
          Cursor { node: parent, parents: self.parents } 
         ) 
        }, 
        _ => panic!("This should not happen") 
       } 
      } 
     } 
    } 
}