树形结构上的引用路径

我正在尝试构建树形结构并在遍历树时维护路径。树形结构上的引用路径

下面是一些代码：

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被借用了两次。有没有办法在不编写“不安全”代码的情况下维护树节点的路径？

来源

2016-06-10 ynimous

为什么你需要可变的参考？ – Shepmaster

我想修改nodes.I只需要修改堆栈顶部的节点，但是我不知道如何表达这个。我可以有一个可变的引用到当前节点和一个具有不可变引用路径的堆栈，但是当我上传树时，我无法从不可变引用创建可变引用。 – ynimous

我结束了从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") 
       } 
      } 
     } 
    } 
}

来源

2016-06-10 17:38:10 ynimous

树形结构上的引用路径

回答

相关问题