如何用rust写一个把对象数组转成树结构的通用方法
最近用rust写web框架,无论菜单还是组织架构都需要把对象数组转成树结构,希望抽取出一个通用方法,以下代码可以跑起来,但效率极低,因为无脑clone,也尝试用智能指针去优化本段代码,但鉴于所有权和生命周期的报错,未能编译通过。希望群友可以给出一个思路去优化本段代码或者提供一个执行效率比较高的通用方法。
serde = { version = "1.0", features = ["derive"] }
use std::collections::HashMap;
use std::fmt::Debug;
use std::hash::Hash;
#[derive(Debug, Clone, Default)]
struct TreeNode<T>
where T: Clone + Default + Debug
{
item: T,
children: Option<Vec<TreeNode<T>>>,
}
impl<T> TreeNode<T>
where T: Clone + Default + Debug
{
fn init_tree(items: Vec<T>) -> Vec<TreeNode<T>> {
let mut tree_items: Vec<TreeNode<T>> = Vec::new();
for mut item in items {
let tree = TreeNode { item, ..Default::default() };
tree_items.push(tree);
}
tree_items
}
fn set_tree<F1, F2>(tree_items: Vec<TreeNode<T>>, parent_key: String, get_key: F1, get_parent_key: F2) -> Vec<TreeNode<T>>
where F1: Fn(&T) -> String + Clone,
F2: Fn(&T) -> String + Clone
{
let mut trees: Vec<TreeNode<T>> = Vec::new();
for mut tree in tree_items.clone() {
if get_parent_key(&tree.item) == parent_key {
tree.children = Some(Self::set_tree(tree_items.clone(), get_key(&tree.item), get_key.clone(), get_parent_key.clone()));
trees.push(tree.clone())
}
}
trees
}
fn build_tree<F1,F2>(items: Vec<T>, parent_key: String, get_key: F1, get_parent_key: F2) -> Vec<TreeNode<T>>
where F1: Fn(&T) -> String + Clone,
F2: Fn(&T) -> String + Clone
{
let items = Self::init_tree(items);
Self::set_tree(items,parent_key,get_key,get_parent_key)
}
}
fn main() {
#[derive(Debug, Clone, Default)]
struct Item {
id: String,
parent_id: Option<String>,
name: String,
}
let items = vec![
Item {
id: String::from("1"),
parent_id: Some(String::from("0")),
name: String::from("Root"),
},
Item {
id: String::from("2"),
parent_id: Some(String::from("1")),
name: String::from("Child 1"),
},
Item {
id: String::from("3"),
parent_id: Some(String::from("1")),
name: String::from("Child 2"),
},
Item {
id: String::from("4"),
parent_id: Some(String::from("2")),
name: String::from("Grandchild 1.1"),
},
Item {
id: String::from("5"),
parent_id: Some(String::from("2")),
name: String::from("Grandchild 1.2"),
},
];
let tree = TreeNode::build_tree(items,String::from("0"),|i|i.id.clone(),|i|i.parent_id.clone().unwrap().clone());
println!("tree is {:?}",tree);
}
推荐文章: