mamcx / tree-flat Goto Github PK

View Code? Open in Web Editor NEW

25.0 2.0 2.0 53 KB

TreeFlat is the simplest way to build & traverse a pre-order Tree in Rust

License: Apache License 2.0

Rust 99.66% Shell 0.34%

tree-flat's Introduction

TreeFlat is the simplest way to build & traverse a pre-order Tree for Rust.

Alpha-relase!

If you build a Tree in pre-order, and display in pre-order, this is the tree for you.

No extra fluff, just a simple & performant one-trick pony.

Note: The tree depends on the build order, so is not possible to re-order the tree (changing parents or levels) in a different order. So, for example, you can't add a branch later to one in the middle (only can add after the end...).

How it works

Instead of creating a Tree of Node pointers, nested enums, or nested Arena-based ids, it just stores the representation of a Tree:

. Users
├── jhon_doe
├   ├── file1.rs
├   ├── file2.rs
├── jane_doe
└────── cat.jpg

... flattened in pre-order on 3 vectors, that store the data, the level & the parent:

DATA:	Users	jhon_doe	file1.rs	file2.rs	jane_doe	cat.jpg
LEVEl:	0	1	2	2	1	2
PARENT:	0	0	1	1	0	4

This allows for the performance of Rust Vec, on the most common operations (critically: Push items + Iterate), and very efficient iterations of node::Node::parents/node::Node::children/node::Node::siblings, because it just traverses the flat vectors.

The iterators exploit these observations:

The children are at the right/up of the parent
The parents are at the left/down of the children
The siblings are all that share the same level

So this means that in the case of navigating the children of jhon_doe:

. Users			  ⇡ parents
├── jhon_doe		Index: 1, Level: 1
			  ⇩ children start at 
				jhon_doe + 1,
				level 	 > jhon_doe
├   ├── file1.rs	: Level 2 is child!
├   ├── file2.rs	: Level 2 is child!
├── jane_doe		: Level 1 is below, stop!
└────── cat.jpg

With this, instead of searching a potentially large array, it jumps directly after the node and iterates as long the nodes are above it!.

Examples

use tree_flat::prelude::*;

let mut tree = Tree::with_capacity("Users", 6);

let mut root = tree.tree_root_mut();

let mut child = root.push("jhon_doe");
child.push("file1.rs");
child.push("file2.rs");

let mut child = root.push("jane_doe");
child.push("cat.jpg");

//The data is backed by vectors and arena-like ids on them:
assert_eq!(
   tree.as_data(),
   ["Users", "jhon_doe", "file1.rs", "file2.rs", "jane_doe", "cat.jpg",]
);
assert_eq!(tree.as_level(), [0, 1, 2, 2, 1, 2,]);
assert_eq!(tree.as_parents(), [0, 0, 1, 1, 0, 4,]);
//Pretty print the tree
println!("{}", tree);

// Iterations is as inserted:
for f in &tree {
  dbg!(f);
}

More info at my blog .

Inspired by the talk:

“High-performance Tree Wrangling, the APL Way” -- Aaron Hsu - APL Wiki

🤝 Contributing

Contributions, issues, and feature requests are welcome!

Show your support

Give a ⭐️ if you like this project! or wanna help make my projects a reality consider donating or sponsoring my work with a subscription in https://www.buymeacoffee.com/mamcx.

📝 License

This project is dual licenced as MIT & APACHE.

tree-flat's People

Contributors

Stargazers

Watchers

Forkers

cyriacbr timmmm

tree-flat's Issues

Benchmark against a standard approach

I'm exploring options around custom types for collections - so arenas are out of my wheelhouse.

I find it difficult to get a sense of the performance of this vs what you might do using Rust std collections.

Without that information it is tough to justify investing time into implementing something that may yield insufficient benefit?

Generalize to accept given collection types?

Thanks you for making this available.
Would it make sense be possible to generalize this to allow some other collection? Say some newtype specialization of Vec or Hash*

Don't require a root node up-front

First I want to say this is a great library! However I ran into a little snag which is that you require creating a root node up front. That feels a little inelegant (you don't need to insert the first element into a Vec when you create it) and I imagine it won't match how most people use it.

For example I'm parsing a format which gives you a series of tags like OPEN_NODE, SET_VALUE, OPEN_NODE, SET_VALUE, SET_VALUE, CLOSE_NODE, CLOSE_NODE.

The root node is just the first OPEN_NODE. If I weren't required to set one up front then the code would be much simpler; as it is I have a load of if is_first_node {} checks.

Does it support remove or detach node?

Thanks for the crate!

Is removing a node a planned feature?

I saw the discussion in ego-tree.
They decided to detach but not remove the node to not change the underlying structure.

Children and Siblings are wrong

This may be a language issue, but the children and siblings iterators do not do what they say. In the example from the tests:

// . 0
// ├── 1
// ├   ├── 2
// ├── 3
// ├   ├── 4
// ├   ├   ├── 5
// ├   ├── 6
// ├── 7
// ├   ├── 8
// ├   ├   ├── 9
// ├   ├   ├── 10
// ├   ├── 11
// ├   ├   ├── 12
// ├   ├   ├── 13
// └────── 14

The children of 0 are 1, 3 and 7. The other nodes are descendants. I would rename children to descendants.

Similarly, the siblings of 12 are 13 and 14. 9 and 10 are not siblings of 12. I'm not sure why you would ever want the get_all_nodes_at_same_level operation really but I would rename it to something other than siblings (or maybe just remove it).

Don't worry too much about fixing these. I decided to write my own version of this library. Yours was a great inspiration though, thanks!

low benchmark scores

from looking at your benchmark scores, they seem really low (by a factor of 10-100x) for reading/writing contiguous memory, even if your doing some other stuff too...did you remember to benchmark with optimizations enabled? you never mentioned the commands you used in the blog entry so I couldn't tell.