rustango_cms/
tree_build.rs1use std::collections::HashMap;
17
18pub fn index_by_parent<T, F>(rows: &[T], parent_of: F) -> HashMap<Option<i64>, Vec<&T>>
25where
26 F: Fn(&T) -> Option<i64>,
27{
28 let mut by_parent: HashMap<Option<i64>, Vec<&T>> = HashMap::new();
29 for r in rows {
30 by_parent.entry(parent_of(r)).or_default().push(r);
31 }
32 by_parent
33}
34
35pub fn build<'a, T, N, I, M>(
42 by_parent: &HashMap<Option<i64>, Vec<&'a T>>,
43 parent: Option<i64>,
44 depth: i64,
45 id_of: &I,
46 make: &M,
47) -> Vec<N>
48where
49 I: Fn(&T) -> i64,
50 M: Fn(&'a T, Vec<N>) -> N,
51{
52 if depth <= 0 {
53 return Vec::new();
54 }
55 let Some(rows) = by_parent.get(&parent) else {
56 return Vec::new();
57 };
58 rows.iter()
59 .map(|r| {
60 let children = if depth > 1 {
61 build(by_parent, Some(id_of(r)), depth - 1, id_of, make)
62 } else {
63 Vec::new()
64 };
65 make(r, children)
66 })
67 .collect()
68}
69
70#[cfg(test)]
71mod tests {
72 use super::*;
73
74 #[derive(Debug)]
75 struct Row {
76 id: i64,
77 parent: Option<i64>,
78 label: &'static str,
79 }
80
81 #[derive(Debug, PartialEq)]
82 struct Node {
83 label: &'static str,
84 children: Vec<Node>,
85 }
86
87 fn rows() -> Vec<Row> {
88 vec![
92 Row { id: 1, parent: None, label: "root-a" },
93 Row { id: 2, parent: Some(1), label: "child-a1" },
94 Row { id: 3, parent: Some(1), label: "child-a2" },
95 Row { id: 4, parent: Some(2), label: "grandchild" },
96 Row { id: 5, parent: None, label: "root-b" },
97 ]
98 }
99
100 fn tree(depth: i64) -> Vec<Node> {
101 let rows = rows();
102 let idx = index_by_parent(&rows, |r| r.parent);
103 build(
104 &idx,
105 None,
106 depth,
107 &|r: &Row| r.id,
108 &|r: &Row, children| Node { label: r.label, children },
109 )
110 }
111
112 #[test]
113 fn nests_children_under_their_parent() {
114 let t = tree(10);
115 assert_eq!(t.len(), 2, "two roots");
116 assert_eq!(t[0].label, "root-a");
117 assert_eq!(t[0].children.len(), 2);
118 assert_eq!(t[0].children[0].children[0].label, "grandchild");
119 assert!(t[1].children.is_empty(), "root-b is childless");
120 }
121
122 #[test]
123 fn depth_bounds_the_walk() {
124 let t = tree(1);
127 assert_eq!(t.len(), 2);
128 assert!(t[0].children.is_empty(), "depth 1 = roots only");
129
130 let t = tree(2);
131 assert_eq!(t[0].children.len(), 2);
132 assert!(
133 t[0].children[0].children.is_empty(),
134 "depth 2 stops before grandchildren"
135 );
136 }
137
138 #[test]
139 fn a_zero_or_negative_depth_yields_nothing() {
140 assert!(tree(0).is_empty());
141 assert!(tree(-1).is_empty());
142 }
143
144 #[test]
145 fn bucket_order_follows_input_order() {
146 let rows = rows();
149 let idx = index_by_parent(&rows, |r| r.parent);
150 let kids: Vec<&str> = idx[&Some(1)].iter().map(|r| r.label).collect();
151 assert_eq!(kids, vec!["child-a1", "child-a2"]);
152 }
153
154 #[test]
155 fn an_orphan_row_is_simply_absent() {
156 let rows = vec![
160 Row { id: 1, parent: None, label: "root" },
161 Row { id: 9, parent: Some(404), label: "orphan" },
162 ];
163 let idx = index_by_parent(&rows, |r| r.parent);
164 let t: Vec<Node> = build(
165 &idx,
166 None,
167 10,
168 &|r: &Row| r.id,
169 &|r: &Row, children| Node { label: r.label, children },
170 );
171 assert_eq!(t.len(), 1);
172 assert_eq!(t[0].label, "root");
173 }
174}