樹形結構上的引用路徑

我正在嘗試構建樹形結構並在遍歷樹時維護路徑。樹形結構上的引用路徑

下面是一些代碼：

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

樹形結構上的引用路徑

回答

相關問題