트리 구조의 참조 경로

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