Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_data/src/tree.rs

19.1 KiB, 6 runs

created by r1870400018:279, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1use oxedyne_fe2o3_core::{
2 prelude::*,
3 count::ErrorWhen,
4};
5
6use std::{
7 cmp::Ordering,
8 fmt,
9};
10
11
12#[derive(Clone, Copy, Debug, Default)]
13pub enum SortBy {
14 #[default]
15 Name,
16 Path,
17 ModifiedTime,
18 Size,
19}
20
21pub trait NodeData: Clone + fmt::Debug + Eq + PartialEq + Ord + PartialOrd {}
22
23#[derive(Clone, Debug)]
24pub struct Leaf<D: NodeData> {
25 pub name: String,
26 pub data: D,
27 pub focus: bool,
28 pub selected: bool,
29}
30
31impl<D: NodeData> Leaf<D> {
32 pub fn name(&self) -> &String {
33 &self.name
34 }
35 pub fn data(&self) -> &D {
36 &self.data
37 }
38}
39
40#[derive(Clone, Debug)]
41pub struct Branch<D: NodeData> {
42 pub name: String,
43 pub data: D,
44 pub nodes: Vec<Node<D>>,
45 pub expanded: bool,
46 pub focus: bool,
47 pub selected: bool,
48}
49
50impl<D: NodeData> Branch<D> {
51 pub fn name(&self) -> &String {
52 &self.name
53 }
54 pub fn data(&self) -> &D {
55 &self.data
56 }
57}
58
59#[derive(Clone, Debug, Default)]
60pub struct NodeProperties {
61 is_branch: bool,
62 has_parent: bool,
63 has_children: bool,
64 num_children: usize,
65 num_siblings: usize,
66}
67
68#[derive(Clone, Debug)]
69pub enum Node<D: NodeData> {
70 Leaf(Leaf<D>),
71 Branch(Branch<D>),
72}
73
74impl<D: NodeData> Node<D> {
75
76 pub fn name(&self) -> &String {
77 match self {
78 Node::Leaf(Leaf { name, .. }) => &name,
79 Node::Branch(Branch { name, .. }) => &name,
80 }
81 }
82
83 pub fn data(&self) -> &D {
84 match self {
85 Node::Leaf(Leaf { data, .. }) => &data,
86 Node::Branch(Branch { data, .. }) => &data,
87 }
88 }
89
90 pub fn is_expanded(&self) -> bool {
91 match self {
92 Node::Leaf(_) => false,
93 Node::Branch(branch) => branch.expanded,
94 }
95 }
96
97 pub fn set_expanded(&mut self, expanded: bool) {
98 if let Node::Branch(branch) = self {
99 branch.expanded = expanded;
100 }
101 }
102
103 pub fn set_node_focus(&mut self, focus: bool) {
104 match self {
105 Node::Leaf(leaf) => leaf.focus = focus,
106 Node::Branch(branch) => branch.focus = focus,
107 }
108 }
109
110 pub fn set_selected(&mut self, selected: bool) {
111 match self {
112 Node::Leaf(leaf) => leaf.selected = selected,
113 Node::Branch(branch) => branch.selected = selected,
114 }
115 }
116
117 pub fn is_selected(&self) -> bool {
118 match self {
119 Node::Leaf(leaf) => leaf.selected,
120 Node::Branch(branch) => branch.selected,
121 }
122 }
123
124 pub fn is_focused(&self) -> bool {
125 match self {
126 Node::Leaf(leaf) => leaf.focus,
127 Node::Branch(branch) => branch.focus,
128 }
129 }
130}
131
132pub fn sort_nodes<
133 D: NodeData,
134 F: Fn(&D, &D) -> Ordering,
135>(
136 nodes: &mut Vec<Node<D>>,
137 compare: &F,
138) {
139 nodes.sort_by(|a, b| compare(a.data(), b.data()))
140}
141
142pub fn sort_nodes_by_name<D: NodeData>(nodes: &mut Vec<Node<D>>) {
143 nodes.sort_by(|a, b| a.name().cmp(b.name()))
144}
145
146#[derive(Clone, Debug, Default)]
147pub struct Tree<R, D: NodeData> {
148 pub root: R,
149 pub focus_path: Vec<usize>,
150 pub nodes: Vec<Node<D>>,
151 pub max_depth: usize,
152}
153
154impl<R, D: NodeData> Tree<R, D> {
155
156 pub fn new(
157 root: R,
158 nodes: Vec<Node<D>>,
159 max_depth: usize,
160 )
161 -> Self
162 {
163 Self {
164 root,
165 focus_path: if !nodes.is_empty() {
166 vec![0]
167 } else {
168 Vec::new()
169 },
170 nodes,
171 max_depth,
172 }
173 }
174
175 pub fn for_all<F>(&mut self, mut callback: F)
176 where
177 F: FnMut(&mut Node<D>),
178 {
179 Self::for_all_recursive(&mut self.nodes, &mut callback);
180 }
181
182 fn for_all_recursive<F>(nodes: &mut [Node<D>], callback: &mut F)
183 where
184 F: FnMut(&mut Node<D>),
185 {
186 for node in nodes.iter_mut() {
187 callback(node);
188 if let Node::Branch(branch) = node {
189 Self::for_all_recursive(&mut branch.nodes, callback);
190 }
191 }
192 }
193
194 pub fn get_node<'a>(
195 &'a self,
196 path: &'a [usize],
197 )
198 -> Option<&'a Node<D>>
199 {
200 let mut nodes = &self.nodes;
201 let imax = path.len().saturating_sub(1);
202 for (i, &index) in path.iter().enumerate() {
203 if i >= imax {
204 return nodes.get(index);
205 } else {
206 nodes = match nodes.get(index) {
207 Some(Node::Branch(branch)) => &branch.nodes,
208 Some(node) => return Some(node),
209 None => return None,
210 };
211 }
212 }
213 nodes.get(path.last().cloned().unwrap_or(0))
214 }
215
216 pub fn get_focal_node<'a>(&'a self) -> Option<&'a Node<D>> {
217 let mut nodes = &self.nodes;
218 let imax = self.focus_path.len().saturating_sub(1);
219 for (i, &index) in self.focus_path.iter().enumerate() {
220 if i >= imax {
221 return nodes.get(index);
222 } else {
223 nodes = match nodes.get(index) {
224 Some(Node::Branch(branch)) => &branch.nodes,
225 Some(node) => return Some(node),
226 None => return None,
227 };
228 }
229 }
230 nodes.get(self.focus_path.last().cloned().unwrap_or(0))
231 }
232
233 pub fn get_node_mut<'a>(
234 &'a mut self,
235 path: &'a [usize],
236 )
237 -> Option<&'a mut Node<D>>
238 {
239 let mut nodes = &mut self.nodes;
240 let imax = path.len().saturating_sub(1);
241 for (i, &index) in path.iter().enumerate() {
242 if i >= imax {
243 return nodes.get_mut(index);
244 } else {
245 nodes = match nodes.get_mut(index) {
246 Some(Node::Branch(branch)) => &mut branch.nodes,
247 Some(node) => return Some(node),
248 None => return None,
249 };
250 }
251 }
252 nodes.get_mut(path.last().cloned().unwrap_or(0))
253 }
254
255 fn get_focal_node_mut(&mut self) -> Option<&mut Node<D>> {
256 let mut nodes = &mut self.nodes;
257 let imax = self.focus_path.len().saturating_sub(1);
258 for (i, &index) in self.focus_path.iter().enumerate() {
259 if i >= imax {
260 return nodes.get_mut(index);
261 } else {
262 nodes = match nodes.get_mut(index) {
263 Some(Node::Branch(branch)) => &mut branch.nodes,
264 Some(node) => return Some(node),
265 None => return None,
266 };
267 }
268 }
269 nodes.get_mut(self.focus_path.last().cloned().unwrap_or(0))
270 }
271
272 pub fn get_sibling_count(&self, path: &[usize]) -> Option<usize> {
273 if path.is_empty() {
274 Some(self.nodes.len())
275 } else {
276 let parent_path = &path[..path.len() - 1];
277 if let Some(parent_node) = self.get_node(parent_path) {
278 match parent_node {
279 Node::Branch(branch) => Some(branch.nodes.len() - 1),
280 Node::Leaf(_) => None,
281 }
282 } else {
283 None
284 }
285 }
286 }
287
288 pub fn has_next_sibling(&self, path: &[usize], index: usize) -> bool {
289 if let Some(Node::Branch(branch)) = self.get_node(&path) {
290 if index >= branch.nodes.len() {
291 false
292 } else {
293 true
294 }
295 } else {
296 false
297 }
298 }
299
300 pub fn has_children(&self, path: &[usize]) -> bool {
301 if let Some(Node::Branch(branch)) = self.get_node(&path) {
302 if branch.nodes.is_empty() {
303 false
304 } else {
305 true
306 }
307 } else {
308 false
309 }
310 }
311
312 pub fn is_branch(&self, path: &[usize]) -> bool {
313 if let Some(Node::Branch(_branch)) = self.get_node(&path) {
314 true
315 } else {
316 false
317 }
318 }
319
320 pub fn get_properties(&self, path: &[usize]) -> NodeProperties {
321
322 let mut is_branch = false;
323 let mut has_parent = false;
324 let mut has_children = false;
325 let mut num_children = 0;
326 let mut num_siblings = 0;
327
328 if let Some(Node::Branch(branch)) = self.get_node(&path) {
329 is_branch = true;
330 if branch.nodes.len() > 0 {
331 has_children = true;
332 }
333 num_children = branch.nodes.len();
334 }
335
336 if path.len() == 1 {
337 num_siblings = self.nodes.len().saturating_sub(1); // Don't count the focus node.
338 } else if path.len() > 1 {
339 if let Some(node) = self.get_node(&path[..(path.len() - 1)]) {
340 has_parent = true;
341 if let Node::Branch(branch) = node {
342 num_siblings = branch.nodes.len().saturating_sub(1); // Don't count the focus node.
343 }
344 }
345 }
346
347 NodeProperties {
348 is_branch,
349 has_parent,
350 has_children,
351 num_children,
352 num_siblings,
353 }
354 }
355
356 // Sort by provided closure.
357
358 pub fn sort<F: Fn(&D, &D) -> Ordering>(&mut self, compare: F) {
359 self.sort_nodes(&compare);
360 self.sort_child_nodes(compare);
361 }
362
363 fn sort_nodes<F: Fn(&D, &D) -> Ordering>(&mut self, compare: F) {
364 sort_nodes(&mut self.nodes, &compare);
365 }
366
367 fn sort_child_nodes<F: Fn(&D, &D) -> Ordering>(&mut self, compare: F) {
368 for node in &mut self.nodes {
369 if let Node::Branch(branch) = node {
370 sort_nodes(&mut branch.nodes, &compare);
371 Self::sort_child_nodes_recursive(&mut branch.nodes, &compare);
372 }
373 }
374 }
375
376 fn sort_child_nodes_recursive<
377 F: Fn(&D, &D) -> Ordering
378 >(
379 nodes: &mut Vec<Node<D>>,
380 compare: &F,
381 ) {
382 for node in nodes {
383 if let Node::Branch(branch) = node {
384 sort_nodes(&mut branch.nodes, compare);
385 Self::sort_child_nodes_recursive(&mut branch.nodes, compare);
386 }
387 }
388 }
389
390 // Sort by name.
391
392 pub fn sort_by_name(&mut self) {
393 self.sort_nodes_by_name();
394 self.sort_child_nodes_by_name();
395 }
396
397 fn sort_nodes_by_name(&mut self) {
398 sort_nodes_by_name(&mut self.nodes);
399 }
400
401 fn sort_child_nodes_by_name(&mut self) {
402 for node in &mut self.nodes {
403 if let Node::Branch(branch) = node {
404 sort_nodes_by_name(&mut branch.nodes);
405 Self::sort_child_nodes_by_name_recursive(&mut branch.nodes);
406 }
407 }
408 }
409
410 fn sort_child_nodes_by_name_recursive(nodes: &mut Vec<Node<D>>) {
411 for node in nodes {
412 if let Node::Branch(branch) = node {
413 sort_nodes_by_name(&mut branch.nodes);
414 Self::sort_child_nodes_by_name_recursive(&mut branch.nodes);
415 }
416 }
417 }
418
419 pub fn display(&self, lines: bool) -> Outcome<Vec<String>> {
420 let mut output = Vec::new();
421 res!(Self::display_nodes(
422 &self.nodes,
423 0,
424 lines,
425 &mut output,
426 &mut Vec::new(),
427 ));
428 Ok(output)
429 }
430
431 pub fn display_nodes(
432 nodes: &[Node<D>],
433 depth: usize,
434 lines: bool,
435 output: &mut Vec<String>,
436 is_last_at_level: &mut Vec<bool>,
437 )
438 -> Outcome<()>
439 {
440 for (index, node) in nodes.iter().enumerate() {
441 let is_last = index == nodes.len() - 1;
442 let prefix = if lines {
443 if is_last {
444 "└── "
445 } else {
446 "├── "
447 }
448 } else {
449 " "
450 };
451
452 let mut line_prefix = String::new();
453 for i in 0..depth {
454 if is_last_at_level[i] {
455 line_prefix.push_str(" ");
456 } else {
457 line_prefix.push_str("│ ");
458 }
459 }
460
461 match node {
462 Node::Leaf(leaf) => {
463 let focus_prefix = if leaf.focus { ">>> " } else { "" };
464 let selected_prefix = if leaf.selected { "[*] " } else { "" };
465 output.push(format!(
466 "{}{}{}{}{}",
467 line_prefix,
468 prefix,
469 focus_prefix,
470 selected_prefix,
471 leaf.name(),
472 ));
473 }
474 Node::Branch(branch) => {
475 let focus_prefix = if branch.focus { ">>> " } else { "" };
476 let selected_prefix = if branch.selected { "[*] " } else { "" };
477 output.push(format!(
478 "{}{}{}{}{}",
479 line_prefix,
480 prefix,
481 focus_prefix,
482 selected_prefix,
483 branch.name(),
484 ));
485 if branch.expanded {
486 if is_last_at_level.len() <= depth {
487 is_last_at_level.push(is_last);
488 } else {
489 is_last_at_level[depth] = is_last;
490 }
491 res!(Self::display_nodes(
492 &branch.nodes,
493 depth + 1,
494 lines,
495 output,
496 is_last_at_level,
497 ));
498 }
499 }
500 }
501 }
502 Ok(())
503 }
504
505 pub fn inc_focus(&mut self) -> Outcome<()> {
506
507 let mut path = self.focus_path.clone();
508 if self.get_node(&path).is_none() {
509 return Ok(());
510 }
511
512 let mut ascending = false;
513 let mut safety = ErrorWhen::new(self.max_depth);
514 loop {
515 res!(safety.inc());
516 let len = path.len();
517 if len > 0 {
518 let last = len - 1;
519 let props = self.get_properties(&path);
520 let index = path[last];
521 if props.is_branch {
522 if props.has_children && !ascending {
523 // Focus goes to first child.
524 path.push(0);
525 break;
526 } else {
527 if index < props.num_siblings {
528 // Focus goes to next sibling.
529 path[last] += 1;
530 break;
531 } else {
532 // There is no next sibiling.
533 if props.has_parent {
534 path = path[..last].to_vec();
535 ascending = true;
536 continue;
537 } else {
538 return Ok(());
539 }
540 }
541 }
542 } else {
543 // Node is a leaf.
544 if index < props.num_siblings {
545 // Focus goes to next sibling.
546 path[last] += 1;
547 break;
548 } else {
549 // There is no next sibling. Begin ascent back up branch.
550 if props.has_parent {
551 path = path[..last].to_vec();
552 ascending = true;
553 continue;
554 } else {
555 return Ok(());
556 }
557 }
558 }
559 } else {
560 break;
561 }
562 }
563
564 res!(self.set_node_focus(false));
565 self.focus_path = path;
566 res!(self.set_node_focus(true));
567
568 Ok(())
569 }
570
571 pub fn dec_focus(&mut self) -> Outcome<()> {
572
573 let mut path = self.focus_path.clone();
574 if self.get_node(&path).is_none() {
575 return Ok(());
576 }
577
578 let mut descending = false;
579 let mut safety = ErrorWhen::new(self.max_depth);
580 loop {
581 res!(safety.inc());
582 let len = path.len();
583 if len > 0 {
584 let last = len - 1;
585 let props = self.get_properties(&path);
586 let index = path[last];
587 if descending {
588 // Slippery slide to the bottom.
589 if props.has_children {
590 // Descend to bottom of the level and try to keep going.
591 path.push(props.num_children - 1);
592 continue;
593 } else {
594 // We've reached the bottom, a branch with no children. Make this the
595 // focus.
596 break;
597 }
598 } else {
599 if props.is_branch {
600 if index > 0 {
601 // Focus goes to previous sibling.
602 path[last] -= 1;
603 descending = true;
604 continue;
605 } else {
606 // There is no previous sibiling.
607 if props.has_parent {
608 path = path[..last].to_vec();
609 break;
610 } else {
611 return Ok(());
612 }
613 }
614 } else {
615 // Node is a leaf.
616 if index > 0 {
617 // Focus on previous sibling.
618 path[last] -= 1;
619 descending = true;
620 continue;
621 } else {
622 // There is no previous sibling.
623 if props.has_parent {
624 path = path[..last].to_vec();
625 break;
626 } else {
627 return Ok(());
628 }
629 }
630 }
631 }
632 } else {
633 break;
634 }
635 }
636
637 res!(self.set_node_focus(false));
638 self.focus_path = path;
639 res!(self.set_node_focus(true));
640
641 Ok(())
642 }
643
644 pub fn set_node_focus(&mut self, focus: bool) -> Outcome<()> {
645
646 if let Some(current) = self.get_focal_node_mut() {
647 current.set_node_focus(focus);
648 } else {
649 return Err(err!(
650 "Could not find a tree node matching the current focus \
651 with path {:?}.", self.focus_path;
652 Data, Missing));
653 }
654
655 Ok(())
656 }
657
658 pub fn toggle_selection(&mut self) -> Outcome<()> {
659 if let Some(node) = self.nodes.iter_mut().find(|node| node.is_focused()) {
660 node.set_selected(!node.is_selected());
661 }
662 Ok(())
663 }
664}