轉化與父母標識結構的列表爲樹木

Question

我從給我的形式結構的載體的數據庫中提取數據集的列表：

struct Foo { 
    id: i32, 
    parent: Option<i32>, 
    data: String, 
} 

我想序列化和輸出到JSON這個數據的嵌套版本的向量：我有一些問題，我的包裹解決這個因執行頭部遞歸性

struct Bar { 
    id: i32, 
    data: String, 
    children: Option<Vec<Bar>>, 
} 

。我可以使用迭代器來解決這個問題，但是當我想通過同一個向量重新迭代時，會碰壁。

例如，在Vec<Foo>的方法，它試圖將只窩兒ID添加到一個HashMap：

fn build_tree(&self) -> HashMap<i32, Vec<i32>> { 
    let mut tree = HashMap::new(); 
    for node in self.iter() { 
     if let Some(parent) = node.parent { 
      let leaf = tree.entry(parent).or_insert(Vec::new()); 
      leaf.push(node.id); 
     } 
    } 
    tree 
} 

產生

{14: [15], 3: [14], 1: [2, 17], 2: [16, 18], 18: [19], 19: [20]} 

但我需要這將是更深層次的東西：

{3: [14: [15]], 1: [2: [16, 18: [19: [20]]], 17]} 

通過this post閱讀有關車削recursiv Ë想法付諸迭代的代碼表明，這樣的實現是可能的，但我已經從困難這一問題採取的思路和這裏應用它們。

有人能描述這種轉變對Vec<Foo>一個Vec<Bar>的方法？我會對迭代或遞歸建議感到滿意;當我自己嘗試遞歸時，我在借用和引用時遇到了很多問題。

Answer 1

直線解決方案包括建立所有數據的圖表和遞歸遍歷它，從每個級別返回Bar並加以收集。有向圖，使我們能夠控制的節點ID（因爲我們只是數字標識符） -

我們通過創建一個petgraph::DiGraphMap開始。如果一個節點有一個父節點，我們確保該節點存在於該圖中，並從父節點向該子節點添加一條邊。如果沒有父母，我們知道這將是我們的頂級ID之一，所以我們藏匿靜置後：

let mut graph = DiGraphMap::new(); 
let mut top_level_ids = vec![]; 

for i in &input { 
    graph.add_node(i.id); 

    match i.parent { 
     Some(parent_id) => { 
      graph.add_node(parent_id); 
      graph.add_edge(parent_id, i.id,()); 
     } 
     None => { 
      top_level_ids.push(i.id); 
     } 
    } 
} 

接下來，我們遍歷所有頂級的ID並將它們轉換成Bar：

let result: Vec<_> = top_level_ids 
    .into_iter() 
    .map(|id| build_tree(&graph, id)) 
    .collect(); 

建設Bar是問題的核心遞歸。我們構建另一個Bar每個孩子，他們的東西全部變成Vec，然後返回當前Bar：

fn build_tree(graph: &DiGraphMap<i32,()>, id: i32) -> Bar { 
    let children = graph 
     .neighbors(id) 
     .map(|child_id| build_tree(graph, child_id)) 
     .collect(); 

    Bar { id, children } 
} 

在這一點上，你有一個Vec<Bar>。這對讀者來說是一個練習，如何對所需的JSON格式進行正確編碼:-)。

The complete example。