tree_flat/
lib.rs

1//! # TreeFlat is the simplest way to build & traverse a pre-order Tree for Rust.
2//!
3//! If you build a [tree::Tree] *in pre-order*, and display *in pre-order*,
4//! this is the tree for you.
5//!
6//! **No extra fluff**, just a simple & performant one-trick pony.
7//!
8//! Note: The tree depends on the build order, so is not possible to re-order the tree
9//! (changing parents or levels) in different order. So, for example, you can't add
10//! a branch later to one in the *middle* (only can add *after* the end...).
11//!
12//! ## How it works
13//!
14//! Instead of creating an [tree::Tree] of [node::Node] pointers, nested enums, or nested `Arena`-based `ids`,
15//! it just stores the representation of a [tree::Tree] like:
16//!
17//! ```bash
18//! . Users
19//! ├── jhon_doe
20//! ├   ├── file1.rs
21//! ├   ├── file2.rs
22//! ├── jane_doe
23//! └────── cat.jpg
24//! ```
25//!
26//! ... flattened in pre-order on 3 [Vec], that store the data, the level/deep and the parent:
27//!
28//! | DATA:  | Users | jhon_doe | file1.rs | file2.rs | jane_doe | cat.jpg |
29//! |--------|-------|----------|----------|----------|----------|---------|
30//! | LEVEL:  | 0     | 1        | 2        | 2        | 1        | 2       |
31//! | PARENT:| 0     | 0        | 1        | 1        | 0        | 4       |
32//!
33//! This allows for the performance of [Vec], on the most common operations
34//! (critically: Push items + Iterate), and very efficient iterations of
35//! [node::Node::parents]/[node::Node::children]/[node::Node::siblings], because
36//! it just traverses the flat vectors.
37//!
38//! The iterators exploit these observations:
39//!
40//! * The children are at the right/up of the parent
41//! * The parents are at the left/down of the children
42//! * The siblings are all that share the same level
43//!
44//! # Examples
45//! ```
46//! use tree_flat::prelude::*;
47//!
48//! let mut tree = Tree::with_capacity("Users", 6);
49//!
50//! let mut root = tree.tree_root_mut();
51//!
52//! let mut child = root.push("jhon_doe");
53//! child.push("file1.rs");
54//! child.push("file2.rs");
55//!
56//! let mut child = root.push("jane_doe");
57//! child.push("cat.jpg");
58//!
59//! //The data is backed by vectors and arena-like ids on them:
60//! assert_eq!(
61//!    tree.as_data(),
62//!    ["Users", "jhon_doe", "file1.rs", "file2.rs", "jane_doe", "cat.jpg",]
63//! );
64//! assert_eq!(tree.as_level(), [0, 1, 2, 2, 1, 2,]);
65//! assert_eq!(tree.as_parents(), [0, 0, 1, 1, 0, 4,]);
66//! //Pretty print the tree
67//! println!("{}", tree);
68//!
69//! //Iterations are as inserted:
70//! for f in &tree {
71//!   dbg!(f);
72//! }
73//!
74//! ```
75//! - - - - - -
76//!
77//! Inspired by the talk:
78//!
79//! > “High-performance Tree Wrangling, the APL Way”
80//! > -- <cite> [Aaron Hsu - APL Wiki](https://aplwiki.com/wiki/Aaron_Hsu)  
81
82/// Flat-tree iterators
83pub mod iter;
84/// Flat-tree nodes
85pub mod node;
86#[cfg(test)]
87mod tests;
88/// Flat-tree implementation
89pub mod tree;
90/// Import this module for easy access to the Flat-tree
91pub mod prelude {
92    pub use crate::iter;
93    pub use crate::node::{Node, NodeId, NodeMut, TreeMut};
94    pub use crate::tree;
95    pub use crate::tree::Tree;
96}
tree_flat/lib.rs

tree_flat/
lib.rs
