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 = if initial_row.remaining_depth == 0 {
69                Parenthood::Childless
70            } else {
71                Parenthood::from_children_count(initial_row.children_count)
72            };
73            let skeletal_component = TreeSkeletalComponent {
74                child_position,
75                parenthood,
76                direction: visualizer.direction,
77            };
78            let ancestor_relative_positions = initial_row
79                .ancestors
80                .iter()
81                .map(|node_info| {
82                    ChildPosition::from_index(node_info.index_as_child, node_info.sibling_count)
83                })
84                .collect();
85            let mut tree_horizontal_slice = TreeHorizontalSlice {
86                ancestor_relative_positions,
87                skeletal_component,
88                name: initial_row.name.to_string(),
89            };
90            if let Ok(()) = tree_horizontal_slice.truncate(max_width) {
91                tree_column_width.tree_column_width = max(
92                    tree_column_width.tree_column_width,
93                    tree_horizontal_slice.width(),
94                );
95            } else {
96                excluded_row_indices.insert(initial_row.row_index);
97            }
98            TreeRow {
99                initial_row,
100                tree_horizontal_slice,
101            }
102        })
103        .collect();
104
105    debug_assert_op_expr!(intermediate_table.len(), ==, initial_data_len);
106    if cfg!(debug_assertions) {
107        intermediate_table
108            .iter()
109            .map(|row| row.row_index)
110            .enumerate()
111            .for_each(|(expected_row_index, actual_row_index)| {
112                debug_assert_op!(actual_row_index == expected_row_index)
113            });
114    }
115
116    // mark children of excluded nodes as excluded
117    loop {
118        let excluded_count = excluded_row_indices.len();
119        let mut children_of_excluded = LinkedList::<usize>::new();
120
121        for excluded_row_index in excluded_row_indices.iter().copied() {
122            let is_child = |row: &&TreeRow<&Name, Size>| {
123                row.parent()
124                    .map_or(false, |node_info| node_info.row_index == excluded_row_index)
125            };
126            intermediate_table
127                .index(excluded_row_index..)
128                .iter()
129                .filter(is_child)
130                .map(|row| row.row_index)
131                .pipe(|iter| children_of_excluded.extend(iter));
132        }
133
134        excluded_row_indices.extend(children_of_excluded);
135        if excluded_row_indices.len() == excluded_count {
136            break;
137        }
138    }
139
140    for excluded_row_index in excluded_row_indices.iter().copied() {
141        // mark more nodes as childless
142        let parent_row_index = intermediate_table
143            .index(excluded_row_index)
144            .parent()
145            .map(|parent_info| parent_info.row_index);
146        if let Some(parent_row_index) = parent_row_index {
147            let parent_row = &mut intermediate_table[parent_row_index];
148            debug_assert_op_expr!(parent_row.children_count, >, 0);
149            if parent_row.children_count == 1 {
150                parent_row.children_count = 0;
151                parent_row
152                    .tree_horizontal_slice
153                    .skeletal_component
154                    .parenthood = Parenthood::Childless;
155            } else {
156                parent_row.children_count -= 1;
157            }
158        }
159
160        // mark more nodes as last amongst siblings
161        let preceding_sibling_row_index = intermediate_table
162            .index(excluded_row_index)
163            .preceding_sibling
164            .map(|node_info| node_info.row_index);
165        if let (Some(preceding_sibling_row_index), Some(parent_row_index)) =
166            (preceding_sibling_row_index, parent_row_index)
167        {
168            let is_sibling = |row: &&TreeRow<&Name, Size>| {
169                row.parent()
170                    .map_or(false, |parent| parent.row_index == parent_row_index)
171            };
172            let is_excluded =
173                |row: &TreeRow<&Name, Size>| excluded_row_indices.contains(&row.row_index);
174            let following_siblings_are_all_excluded = intermediate_table
175                .index(excluded_row_index..)
176                .iter()
177                .filter(is_sibling)
178                .all(is_excluded);
179            if following_siblings_are_all_excluded {
180                let target = &mut intermediate_table
181                    .index_mut(preceding_sibling_row_index)
182                    .tree_horizontal_slice
183                    .skeletal_component
184                    .child_position;
185                *target = ChildPosition::Last;
186            }
187        }
188    }
189
190    let is_included = |row: &TreeRow<&Name, Size>| !excluded_row_indices.contains(&row.row_index);
191    let tree_data: LinkedList<_> = intermediate_table.into_iter().filter(is_included).collect();
192
193    TreeTable {
194        data: tree_data,
195        column_width: tree_column_width,
196    }
197}
parallel_disk_usage/visualizer/methods/tree_table.rs

parallel_disk_usage/visualizer/methods/
tree_table.rs
