kubectl_view_allocations/
tree.rs

1//! module to make tree-table or tree from a list,
2//! by computing the string prefix that contains line of to link item of the list
3//! like a tree (multi-root)
4//!
5//! ```rust
6//! use kubectl_view_allocations::tree::provide_prefix;
7//!
8//! let items = vec![
9//!     "1/2",
10//!     "1/2/3",
11//!     "1/2/3/4",
12//!     "1/2/5",
13//!     "6",
14//!     "7",
15//!     "7/8",
16//!     "7/9",
17//! ];
18//!
19//! let prefixes = provide_prefix(&items, |parent, item| {
20//!     let pi = item.split("/");
21//!     let pp = parent.split("/");
22//!     (pi.count() == pp.count() + 1) && item.starts_with(parent)
23//! });
24//!
25//! let mut actual = String::new();
26//! prefixes.iter().zip(items).for_each(|(p, i)|
27//!     actual.push_str(&format!("{} {}\n", p, i))
28//! );
29//!
30//! let expected = r#" 1/2
31//!  ├─ 1/2/3
32//!  │  └─ 1/2/3/4
33//!  └─ 1/2/5
34//!  6
35//!  7
36//!  ├─ 7/8
37//!  └─ 7/9
38//! "#;
39//! //dbg!(&actual);
40//! assert_eq!(actual, expected);
41//! ```
42//!
43
44#[derive(Debug, Clone)]
45struct TreeNode {
46    parent: Option<usize>,
47    level: Vec<bool>,
48    children: Vec<usize>,
49}
50
51fn level_to_string(level: &[bool]) -> String {
52    const EMPTY: &str = "   ";
53    const EDGE: &str = " └─";
54    const PIPE: &str = " │ ";
55    const BRANCH: &str = " ├─";
56
57    let mut prefix = String::new();
58    if !level.is_empty() {
59        let last_col = level.len() - 1;
60        for (col, is_last_child) in level.iter().enumerate() {
61            let is_last_col = col == last_col;
62            let s = match (*is_last_child, is_last_col) {
63                (true, false) => EMPTY,
64                (true, true) => EDGE,
65                (false, false) => PIPE,
66                (false, true) => BRANCH,
67            };
68            prefix.push_str(s);
69        }
70    }
71    prefix
72}
73
74fn write_tree_level_of_children(nodes: &mut [TreeNode], idx: usize) {
75    if let Some(node) = nodes.get(idx) {
76        let treenode = node.clone();
77        let mut d = treenode.children.len();
78        for s in treenode.children.iter() {
79            if let Some(child) = nodes.get_mut(*s) {
80                let mut lnext = treenode.level.clone();
81                lnext.push(d == 1);
82                d -= 1;
83                child.level = lnext;
84            }
85        }
86    }
87}
88
89fn make_tree_by_reverse_depth_first<I, F>(items: &[I], is_parent_of: F) -> Vec<TreeNode>
90where
91    F: Fn(&I, &I) -> bool,
92{
93    let mut current: Option<usize> = None;
94    let mut nodes: Vec<TreeNode> = vec![];
95    for (i, item) in items.iter().enumerate() {
96        while current.is_some() && !is_parent_of(&items[current.unwrap()], item) {
97            current = nodes.get_mut(current.unwrap()).and_then(|n| n.parent);
98        }
99        let treenode = TreeNode {
100            parent: current,
101            level: vec![],
102            children: vec![],
103        };
104        if let Some(parent) = current
105            && let Some(node) = nodes.get_mut(parent)
106        {
107            node.children.push(i);
108        }
109        nodes.push(treenode);
110        current = Some(i);
111    }
112    nodes
113}
114
115/// Generate a list of prefix to display items as a tree (multi-root)
116/// - the input should be sorted in the target display order
117/// - the input order of ìtems is preserved into output
118/// - the input order is used to ask for parent of item (parent should be before child)
119/// - output as the same number of element than input `items`
120/// - output can be zipped with input ìtems
121/// - is_parent_of(maybe_parent, item)
122pub fn provide_prefix<I, F>(items: &[I], is_parent_of: F) -> Vec<String>
123where
124    F: Fn(&I, &I) -> bool,
125{
126    let mut nodes: Vec<TreeNode> = make_tree_by_reverse_depth_first(items, is_parent_of);
127    //dbg!(&nodes);
128    for i in 0..nodes.len() {
129        write_tree_level_of_children(&mut nodes, i);
130    }
131    //dbg!(&nodes);
132    nodes.iter().map(|n| level_to_string(&n.level)).collect()
133}
134
135#[cfg(test)]
136mod tests {
137    use super::*;
138
139    #[test]
140    fn test_() {
141        let items = vec!["1/2", "1/2/3", "1/2/3/4", "1/2/5", "6", "7", "7/8", "7/9"];
142
143        let prefixes = provide_prefix(&items, |parent, item| {
144            let pi = item.split('/');
145            let pp = parent.split('/');
146            (pi.count() == pp.count() + 1) && item.starts_with(parent)
147        });
148
149        let mut actual = String::new();
150        prefixes
151            .iter()
152            .zip(items)
153            .for_each(|(p, i)| actual.push_str(&format!("{} {}\n", p, i)));
154
155        let expected = r#" 1/2
156 ├─ 1/2/3
157 │  └─ 1/2/3/4
158 └─ 1/2/5
159 6
160 7
161 ├─ 7/8
162 └─ 7/9
163"#;
164        //dbg!(&actual);
165        assert_eq!(actual, expected);
166    }
167}
kubectl_view_allocations/tree.rs

kubectl_view_allocations/
tree.rs
