木

Question

私は私のフォームの構造体のベクトルを与え、データベースからデータセットを引っ張ってるのリストに親IDを持つ構造体のリストを変換：

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

私はシリアル化して出力したいですベクトルとして、このデータのネストされたバージョンをJSONに：

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

私が原因再帰的な性質のために、この実施のまわりで私の頭をラップするいくつかの問題を抱えています。イテレータを使用して問題を1つ下に解決できますが、同じベクトル上で再び繰り返したいときに壁に当たっています。例えば

、ハッシュマップにIDSにちょうど巣の子供たちを試みるVec<Foo>の方法：

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再帰を回すことについてeアイデアを反復コードに組み込むことは、そのような実装が可能であることを示唆していますが、私はその問題からアイデアを取り出してここに適用することが困難でした。

Vec<Foo>をVec<Bar>に変換する方法を説明できる人はいますか？私は反復的または再帰的な提案に満足しています。私は自分で再帰を試みたときに、借用と参照に関して多くの問題を抱えていました。

Answer 1

直線的な解決策は、すべてのデータのグラフを構築し、それを再帰的にトラバースし、各レベルからBarを返して収集することです。

petgraph::DiGraphMap - ノードIDを制御できる有向グラフ（数字の識別子しかないため）を作成します。ノードに親がある場合は、それがグラフに存在することを確認し、親から子にエッジを追加します。それは親がない場合は、我々はそれが私たちの最上位レベルの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を構築することは、問題の再帰的なコアです。

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>を持っている：私たちは、現在のBarを返し、その後、Vecにそれらすべてを詰め込む、それぞれの子のために別のBarを構築します。読者にとっては、これを目的のJSON形式に適切にエンコードする方法を練習しています:-)。

The complete example。