Expand description
Summary
A library that provides a complete binary tree visitor trait with default implemenations for visiting strategies such as dfs_inorder or bfs, etc. Some adaptors are also provided that let you map, zip, or optionally also produce the depth on every call to next(). It also provides two flavors of a complete binary tree data structure with mutable and immutable visitors that implement the visitor trait. One laid out in bfs, and one laid out in dfs in order in memory. Both of these flavors assume that every node in the tree is the same type. The visitor trait is more flexible than this, however. With the NonLeafItem associated type, users can implement a visitor for tree data structures that have different types for the nonleafs and leafs.
This is the trait that this crate revoles around:
pub trait Visitor:Sized{
type Item;
type NonLeafItem;
fn next(self)->(Self::Item,Option<(Self::NonLeafItem,Self,Self)>);
}If you have a visitor, you can call next() on it to consume it, and produce the node it is visiting, plus the children nodes. Sometimes, non leaf nodes contain additional data that does not apply to leaf nodes. This is the purpose of the NonLeafItem associated type. Users can choose to define it to be some data that only non leaf nodes provide. For the two provided implementations, both leafs and nonleafs have the same time, so in those cases we just use the empty type.
The fact that the iterator is consumed when calling next(), allows us to return mutable references without fear of the users being able to create the same mutable reference some other way. So this property provides a way to get mutable references to children nodes simultaneously safely. Useful for parallelizing divide and conquer style problems.
Goals
To provide a useful complete binary tree visitor trait that has some similar features to the Iterator trait, such as zip(), and map(), and that can be used in parallel divide and conquer style problems.
Unsafety in the provided two tree implementations
With a regular Vec, getting one mutable reference to an element will borrow the entire Vec. However the two provided trees have invariants that let us make guarentees about which elements can be mutably borrowed at the same time. With the bfs tree, the children for an element at index k can be found at 2k+1 and 2k+2. This means that we are guarenteed that the parent, and the two children are all distinct elements and so mutable references two all of them can exist at the same time. With the dfs implementation, on every call to next() we use split_at_mut() to split the current slice we have into three parts: the current node, the elements ot the left, and the elements to the right.
Memory Locality
Ordering the elements in dfs in order is likely better for divide and conquer style problems. The main memory access pattern that we want to be fast is the following: If I have a parent, I hope to be able to access the children fast. So we want the children to be close to the parent. While in bfs order, the root’s children are literally right next to it, the children of nodes in the the second to last level of the tree could be extremly far apart (possibly n/2 elements away!). With dfs order, as you go down the tree, you gain better and better locality.