parallel_disk_usage/visualizer/methods/
tree_table.rs

1use super::{InitialColumnWidth, InitialRow, InitialTable, Table};
2use crate::{
3    size,
4    visualizer::{
5        ChildPosition, Parenthood, TreeHorizontalSlice, TreeSkeletalComponent, Visualizer,
6    },
7};
8use assert_cmp::{debug_assert_op, debug_assert_op_expr};
9use derive_more::{Deref, DerefMut};
10use pipe_trait::Pipe;
11use std::{
12    cmp::max,
13    collections::{HashSet, LinkedList},
14    fmt::Display,
15    ops::{Index, IndexMut},
16};
17use zero_copy_pads::Width;
18
19#[derive(Deref, DerefMut)]
20pub(super) struct TreeRow<Name, NodeData> {
21    #[deref]
22    #[deref_mut]
23    pub(super) initial_row: InitialRow<Name, NodeData>,
24    pub(super) tree_horizontal_slice: TreeHorizontalSlice<String>,
25}
26
27#[derive(Default, Clone, Copy, Deref, DerefMut)]
28pub(super) struct TreeColumnWidth {
29    #[deref]
30    #[deref_mut]
31    pub(super) initial_column_width: InitialColumnWidth,
32    pub(super) tree_column_width: usize,
33}
34
35impl TreeColumnWidth {
36    #[inline]
37    pub(super) const fn total_max_width(self) -> usize {
38        self.initial_column_width.total_max_width() + self.tree_column_width
39    }
40}
41
42pub(super) type TreeTable<Name, NodeData> = Table<TreeRow<Name, NodeData>, TreeColumnWidth>;
43
44pub(super) fn render_tree<'a, Name, Size>(
45    visualizer: Visualizer<'a, Name, Size>,
46    initial_table: InitialTable<&'a Name, Size>,
47    max_width: usize,
48) -> TreeTable<&'a Name, Size>
49where
50    Name: Display,
51    Size: size::Size + Into<u64>,
52{
53    let InitialTable {
54        data: initial_data,
55        column_width: initial_column_width,
56    } = initial_table;
57    let initial_data_len = initial_data.len();
58    let mut tree_column_width = TreeColumnWidth {
59        initial_column_width,
60        tree_column_width: 0,
61    };
62    let mut excluded_row_indices = HashSet::with_capacity(initial_data_len);
63    let mut intermediate_table: Vec<_> = initial_data
64        .into_iter()
65        .map(|initial_row| {
66            let child_position =
67                ChildPosition::from_index(initial_row.index_as_child, initial_row.sibling_count);
68            let parenthood = Parenthood::from_children_count(initial_row.children_count);
69            let skeletal_component = TreeSkeletalComponent {
70                child_position,
71                parenthood,
72                direction: visualizer.direction,
73            };
74            let ancestor_relative_positions = initial_row
75                .ancestors
76                .iter()
77                .map(|node_info| {
78                    ChildPosition::from_index(node_info.index_as_child, node_info.sibling_count)
79                })
80                .collect();
81            let mut tree_horizontal_slice = TreeHorizontalSlice {
82                ancestor_relative_positions,
83                skeletal_component,
84                name: initial_row.name.to_string(),
85            };
86            if let Ok(()) = tree_horizontal_slice.truncate(max_width) {
87                tree_column_width.tree_column_width = max(
88                    tree_column_width.tree_column_width,
89                    tree_horizontal_slice.width(),
90                );
91            } else {
92                excluded_row_indices.insert(initial_row.row_index);
93            }
94            TreeRow {
95                initial_row,
96                tree_horizontal_slice,
97            }
98        })
99        .collect();
100
101    debug_assert_op_expr!(intermediate_table.len(), ==, initial_data_len);
102    if cfg!(debug_assertions) {
103        intermediate_table
104            .iter()
105            .map(|row| row.row_index)
106            .enumerate()
107            .for_each(|(expected_row_index, actual_row_index)| {
108                debug_assert_op!(actual_row_index == expected_row_index)
109            });
110    }
111
112    // mark children of excluded nodes as excluded
113    loop {
114        let excluded_count = excluded_row_indices.len();
115        let mut children_of_excluded = LinkedList::<usize>::new();
116
117        for excluded_row_index in excluded_row_indices.iter().copied() {
118            let is_child = |row: &&TreeRow<&Name, Size>| {
119                row.parent()
120                    .is_some_and(|node_info| node_info.row_index == excluded_row_index)
121            };
122            intermediate_table
123                .index(excluded_row_index..)
124                .iter()
125                .filter(is_child)
126                .map(|row| row.row_index)
127                .pipe(|iter| children_of_excluded.extend(iter));
128        }
129
130        excluded_row_indices.extend(children_of_excluded);
131        if excluded_row_indices.len() == excluded_count {
132            break;
133        }
134    }
135
136    for excluded_row_index in excluded_row_indices.iter().copied() {
137        // mark more nodes as childless
138        let parent_row_index = intermediate_table
139            .index(excluded_row_index)
140            .parent()
141            .map(|parent_info| parent_info.row_index);
142        if let Some(parent_row_index) = parent_row_index {
143            let parent_row = &mut intermediate_table[parent_row_index];
144            debug_assert_op_expr!(parent_row.children_count, >, 0);
145            if parent_row.children_count == 1 {
146                parent_row.children_count = 0;
147                parent_row
148                    .tree_horizontal_slice
149                    .skeletal_component
150                    .parenthood = Parenthood::Childless;
151            } else {
152                parent_row.children_count -= 1;
153            }
154        }
155
156        // mark more nodes as last amongst siblings
157        let preceding_sibling_row_index = intermediate_table
158            .index(excluded_row_index)
159            .preceding_sibling
160            .map(|node_info| node_info.row_index);
161        if let (Some(preceding_sibling_row_index), Some(parent_row_index)) =
162            (preceding_sibling_row_index, parent_row_index)
163        {
164            let is_sibling = |row: &&TreeRow<&Name, Size>| {
165                row.parent()
166                    .is_some_and(|parent| parent.row_index == parent_row_index)
167            };
168            let is_excluded =
169                |row: &TreeRow<&Name, Size>| excluded_row_indices.contains(&row.row_index);
170            let following_siblings_are_all_excluded = intermediate_table
171                .index(excluded_row_index..)
172                .iter()
173                .filter(is_sibling)
174                .all(is_excluded);
175            if following_siblings_are_all_excluded {
176                let target = &mut intermediate_table
177                    .index_mut(preceding_sibling_row_index)
178                    .tree_horizontal_slice
179                    .skeletal_component
180                    .child_position;
181                *target = ChildPosition::Last;
182            }
183        }
184    }
185
186    let is_included = |row: &TreeRow<&Name, Size>| !excluded_row_indices.contains(&row.row_index);
187    let tree_data: LinkedList<_> = intermediate_table.into_iter().filter(is_included).collect();
188
189    TreeTable {
190        data: tree_data,
191        column_width: tree_column_width,
192    }
193}
parallel_disk_usage/visualizer/methods/tree_table.rs

parallel_disk_usage/visualizer/methods/
tree_table.rs
