Transformer une liste de struct avec ID parent dans une liste des arbres

Question

Je tire un ensemble de données à partir d'une base de données qui me donne un vecteur de struct de la forme:

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

Je voudrais sérialisation et la sortie JSON la version imbriquée de ces données comme vecteur de:

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

Je vais avoir des problèmes d'emballage ma tête autour de la mise en œuvre de ce en raison de la nature récurrente. Je peux résoudre le problème d'un niveau à l'aide d'itérateurs, mais ensuite frapper un mur quand je veux recommencer à itérer sur le même vecteur.

Par exemple, une méthode sur Vec<Foo> qui tente de ids seulement les enfants de nid dans un 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 
} 

cède

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

Mais ce que je demande serait quelque chose de plus profond:

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

Lecture à travers this post sur la transformation d'un récursif L'idée en code itératif suggère qu'une telle implémentation est possible, mais j'ai eu du mal à prendre les idées de ce problème et à les appliquer ici. Est-ce que quelqu'un peut décrire une méthode pour transformer ce Vec<Foo> en Vec<Bar>? Je serais heureux avec une suggestion itérative ou récursive; J'ai juste eu beaucoup de problèmes avec les emprunts et le référencement quand j'ai essayé la récursivité moi-même.

Answer 1

La solution linéaire consiste à créer un graphique de toutes vos données et à le parcourir récursivement, en retournant le Bar de chaque niveau et en les collectant.

Nous commençons par créer un petgraph::DiGraphMap - un graphe orienté qui nous permet de contrôler les identifiants de noeud (puisque nous avons juste des identifiants numériques). Si un nœud a un parent, nous nous assurons qu'il existe dans le graphique et ajoutez un bord du parent à l'enfant. Si elle ne dispose pas d'un parent, nous savons que ce sera l'un de nos ids de haut niveau, donc nous planquer de côté pour plus tard:

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

Ensuite, nous parcourons tous les ID de haut niveau et les convertir en un Bar:

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

Construire une Bar est le cœur du problème récurrent. Nous construisons une autre Bar pour chaque enfant, les farcir tout en Vec, puis retourner la Bar actuelle:

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

À ce stade, vous avez un Vec<Bar>. C'est un exercice pour le lecteur comment encoder correctement ceci pour le format JSON désiré :-).

The complete example.