nested - 将具有父 ID 的结构列表转换为树列表

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关于将递归想法转化为迭代代码表明这样的实现是可能的，但我很难从那个问题中提取想法并将它们应用到这里。

有人可以描述一种转换此 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是问题的递归核心。我们构建另一个 Bar对于每个 child ，将它们全部塞进 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 .