将对象列表转换为树结构的通用代码

Question

我有一些树状结构的菜单，定义如下：

use rocket::serde::Deserialize;
use rocket::serde::Serialize;
use crate::model::diesel::dolphin::dolphin_models::MenuResource;

#[derive(Deserialize, Serialize)]
#[allow(non_snake_case)]
pub struct MenuResponse {
    pub id: i32,
    pub name: String,
    pub name_zh: String,
    pub parent_id: i32,
    pub disableCheckbox: bool,
    pub tree_id_path: String,
    pub children: Vec<MenuResponse>
}

在数据库中，我将菜单存储为包含 id 和 parent_id 的列表。我将列表转换为这样的树：

/**
** convert the list menu to tree recursive
**/
pub fn convert_menu_to_tree(root_menus: &Vec<MenuResource>, sub_menus: &Vec<MenuResource>) -> Vec<MenuResponse>{
    let mut menu_res_list = Vec::new();
    for root_menu in root_menus {
        let mut origin_menu_res_list = Vec::new();
        let mut menu_res = MenuResponse::from(root_menu);
        for sub_menu in sub_menus{
            if sub_menu.parent_id == root_menu.id {
                let menu_res_sub = MenuResponse::from(sub_menu);
                menu_res.children.push(menu_res_sub);
                origin_menu_res_list.push(sub_menu.clone());
            }
        }
        if !menu_res.children.is_empty() {
            menu_res.children = convert_menu_to_tree(&origin_menu_res_list, sub_menus);
        }
        menu_res_list.push(menu_res);
    }
    return menu_res_list;
}

这段代码工作正常。问题是我有另一种数据类型，我想像这样将其视为树结构。我必须为每个列表编写树转换函数。是否可以编写一个函数来处理这样的所有数据结构？一个将所有列表对象转换为树结构的函数。

在 Java 中，我可以使用泛型和反射来做到这一点。在 Rust 中怎么样？

我试过像这样以通用方式定义函数：

/**
** convert the list menu to tree recursive
**/
pub fn convert_menu_to_tree<T,E>(root_menus: &Vec<T>, sub_menus: &Vec<T>) -> Vec<E>{
    let mut menu_res_list = Vec::new();
    for root_menu in root_menus {
        let mut origin_menu_res_list = Vec::new();
        let mut menu_res = E::from(root_menu);
        for sub_menu in sub_menus{
            if sub_menu.parent_id == root_menu.id {
                let menu_res_sub = E::from(sub_menu);
                menu_res.children.push(menu_res_sub);
                origin_menu_res_list.push(sub_menu.clone());
            }
        }
        if !menu_res.children.is_empty() {
            menu_res.children = convert_menu_to_tree(&origin_menu_res_list, sub_menus);
        }
        menu_res_list.push(menu_res);
    }
    return menu_res_list;
}

但我不知道如何用T或E处理children属性。是否可以按名称设置值 children?

Answer 1

因为你的例子不完全是一个 minimal reproducible example，我 re-wrote 它（抱歉，稍微延伸了 'minimal' 的定义）来玩：

use serde::Serialize;

#[derive(Clone)]
pub struct MenuResource {
    parent_id: i32,
    id: i32,
    content: i32,
}

impl MenuResource {
    pub fn new(parent_id: i32, id: i32, content: i32) -> Self {
        Self {
            parent_id,
            id,
            content,
        }
    }
}

#[derive(Debug, Serialize)]
pub struct MenuResponse {
    pub id: i32,
    pub content: i32,
    pub children: Vec<MenuResponse>,
}

impl From<&MenuResource> for MenuResponse {
    fn from(src: &MenuResource) -> Self {
        Self {
            id: src.id,
            content: src.content,
            children: vec![],
        }
    }
}

/**
** convert the list menu to tree recursive
**/
pub fn convert_menu_to_tree(
    root_menus: &Vec<MenuResource>,
    sub_menus: &Vec<MenuResource>,
) -> Vec<MenuResponse> {
    let mut menu_res_list = Vec::new();
    for root_menu in root_menus {
        let mut origin_menu_res_list: Vec<MenuResource> = Vec::new();
        let mut menu_res = MenuResponse::from(root_menu);
        for sub_menu in sub_menus {
            if sub_menu.parent_id == root_menu.id {
                let menu_res_sub = MenuResponse::from(sub_menu);
                menu_res.children.push(menu_res_sub);
                origin_menu_res_list.push((*sub_menu).clone());
            }
        }
        if !menu_res.children.is_empty() {
            menu_res.children = convert_menu_to_tree(&origin_menu_res_list, sub_menus);
        }
        menu_res_list.push(menu_res);
    }
    return menu_res_list;
}

pub fn main() {
    let root_menus = vec![MenuResource::new(0, 1, 101), MenuResource::new(0, 2, 102)];
    let sub_menus = vec![
        MenuResource::new(1, 3, 201),
        MenuResource::new(1, 4, 202),
        MenuResource::new(2, 5, 203),
        MenuResource::new(3, 6, 204),
        MenuResource::new(6, 7, 205),
    ];

    let result = convert_menu_to_tree(&root_menus, &sub_menus);
    println!("{}", serde_json::to_string_pretty(&result).unwrap());
}

输出：

[
  {
    "id": 1,
    "content": 101,
    "children": [
      {
        "id": 3,
        "content": 201,
        "children": [
          {
            "id": 6,
            "content": 204,
            "children": [
              {
                "id": 7,
                "content": 205,
                "children": []
              }
            ]
          }
        ]
      },
      {
        "id": 4,
        "content": 202,
        "children": []
      }
    ]
  },
  {
    "id": 2,
    "content": 102,
    "children": [
      {
        "id": 5,
        "content": 203,
        "children": []
      }
    ]
  }
]

Serialize 和 json 当然不是绝对必要的，但输出的结果非常不可读，我懒得写一个合适的 Display impl.

界面

现在，让我们看看我们需要什么来使 convert_menu_to_tree 函数更通用（让我们重命名它 convert_to_tree）：

我们要转换为树的类型，T
一个输出类型
一个接受 &T 和子列表并创建输出类型的函数
从 T 读取 id 和 parent_id 的函数。

因此，让我们为该类型定义一个特征 IntoTree T:

pub trait IntoTree: Sized {
    type Output;

    fn get_id(&self) -> i32;
    fn get_parent_id(&self) -> i32;
    fn convert(&self, children: Vec<Self::Output>) -> Self::Output;
}

解决方案

现在这是一个将所有这些放在一起的算法：

convert_to_tree.rs

use std::collections::HashMap;

pub trait IntoTree: Sized {
    type Output;

    fn get_id(&self) -> i32;
    fn get_parent_id(&self) -> i32;
    fn convert(&self, children: Vec<Self::Output>) -> Self::Output;
}

fn take_all_children<T>(parent_id: i32, sub_menus: &mut HashMap<i32, Vec<&T>>) -> Vec<T::Output>
where
    T: IntoTree,
{
    sub_menus
        .remove(&parent_id)
        .unwrap_or_default()
        .iter()
        .map(|child| {
            let grandchildren = take_all_children(child.get_id(), sub_menus);
            child.convert(grandchildren)
        })
        .collect()
}

pub fn convert_to_tree<T>(root_menus: &[T], sub_menus: &[T]) -> Vec<T::Output>
where
    T: IntoTree,
{
    let mut sub_menus_by_parent = HashMap::new();
    for sub in sub_menus {
        sub_menus_by_parent
            .entry(sub.get_parent_id())
            .or_insert_with(Vec::new)
            .push(sub);
    }

    root_menus
        .iter()
        .map(|root_menu| {
            let children = take_all_children(root_menu.get_id(), &mut sub_menus_by_parent);
            root_menu.convert(children)
        })
        .collect()
}

main.rs

mod convert_to_tree;
use convert_to_tree::{convert_to_tree, IntoTree};

use serde::Serialize;

#[derive(Clone)]
pub struct MenuResource {
    parent_id: i32,
    id: i32,
    content: i32,
}

impl MenuResource {
    pub fn new(parent_id: i32, id: i32, content: i32) -> Self {
        Self {
            parent_id,
            id,
            content,
        }
    }
}

#[derive(Debug, Serialize)]
pub struct MenuResponse {
    pub id: i32,
    pub content: i32,
    pub children: Vec<MenuResponse>,
}

impl IntoTree for MenuResource {
    type Output = MenuResponse;

    fn get_id(&self) -> i32 {
        self.id
    }

    fn get_parent_id(&self) -> i32 {
        self.parent_id
    }

    fn convert(&self, children: Vec<Self::Output>) -> Self::Output {
        MenuResponse {
            id: self.id,
            content: self.content,
            children,
        }
    }
}

pub fn main() {
    let root_menus = vec![MenuResource::new(0, 1, 101), MenuResource::new(0, 2, 102)];
    let sub_menus = vec![
        MenuResource::new(1, 3, 201),
        MenuResource::new(1, 4, 202),
        MenuResource::new(2, 5, 203),
        MenuResource::new(3, 6, 204),
        MenuResource::new(6, 7, 205),
    ];

    let result = convert_to_tree(&root_menus, &sub_menus);
    println!("{}", serde_json::to_string_pretty(&result).unwrap());
}

现在，您可以将实现 IntoTree 的每个类型转换为树。

转换应该非常快，因为它首先构建一个 HashMap ID 和子项。然后，它只是从 HashMap.

中取出每个节点的子节点

备选方案

仅供参考，另一种更接近你代码的方案：

convert_to_tree.rs

pub trait IntoTree: Sized + Clone {
    type Output;

    fn get_id(&self) -> i32;
    fn get_parent_id(&self) -> i32;
    fn convert(&self, children: Vec<Self::Output>) -> Self::Output;
}

pub fn convert_to_tree<T>(root_menus: &[T], sub_menus: &[T]) -> Vec<T::Output>
where
    T: IntoTree,
{
    let mut menu_res_list = Vec::new();
    for root_menu in root_menus {
        let mut origin_menu_res_list: Vec<T> = Vec::new();

        for sub_menu in sub_menus {
            if sub_menu.get_parent_id() == root_menu.get_id() {
                origin_menu_res_list.push(sub_menu.clone());
            }
        }

        let children = convert_to_tree(&origin_menu_res_list, sub_menus);

        let menu_res = root_menu.convert(children);
        menu_res_list.push(menu_res);
    }
    return menu_res_list;
}

我不喜欢这个解决方案的地方是 .clone 的使用和 T 的 Clone 要求。

将对象列表转换为树结构的通用代码

Generic code to convert a list of objects into a tree structure

rust

界面

解决方案

备选方案