CODEWITHSUNDEEP
rust
Dolphin
Dolphin

Reputation: 38681

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

I have some menus with a tree structure, defined like this:

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

In the database I store the menus as a list with id and parent_id. I transform the list to a tree like this:

/**
** 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;
}

This code works fine. The problem is that I have another datatype I want to treat as tree structure like this. I have to write the list to tree conversion function for each one. Is it possible to write a function to handle all data structure like this? One function to convert all list objects to tree structure.

In Java, I could using generics and reflection to do it. How about in Rust?

I have tried to define the function the generic way like this:

/**
** 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;
}

But I don't know how to handle the children attribute with T or E. Is is possible to set the value by name children?

Upvotes: 0

Views: 265

Answers (1)

Finomnis
Finomnis

Reputation: 22476

As your example wasn't quite a minimal reproducible example, I re-wrote it (sorry, stretches the definition of 'minimal' a little) to play around with:

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

Output:

[
  {
    "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": []
      }
    ]
  }
]

The Serialize and json is of course not strictly necessary, but the output is very unreadable otherwise, and I was too lazy to write a proper Display impl.

Interface

Now, let's see what we need to make the convert_menu_to_tree function more generic (let's rename it convert_to_tree):

  • A type, T that we want to convert to a tree
  • An output type
  • A function that takes &T and a list of children and creates the output type
  • A function that reads the id and the parent_id from T.

Therefore, let's define a trait IntoTree for that type 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;
}

Solution

Now here is an algorithm that puts it all together:

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

With this, you can now convert every type that implements IntoTree to a tree.

The conversion should be very fast as it first builds a HashMap of ids and children. Then, it just takes the children for every node out of the HashMap.

Alternative Solution

Just for reference, another solution that is closer to your code:

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

What I don't like about this solution is the use of .clone and the Clone requirement for T.

Upvotes: 2

Related Questions