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.
This is the trait that this crate revoles around:
pub trait Visitor:Sized{
type Item;
fn next(self)->(Self::Item,Option<[Self;2]>);
}If you have a visitor, you can call next() on it to consume it, and produce a reference to the node it is visiting, plus the children nodes.
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 a tree has properties 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.
A downside with dfs ordering is that if not all space is used by the leaf nodes, Then that wasted space is interspered throughout the entire data structure. In a bfs ordering, All the leaves are at the end of the data structure, so the memory locality penalty may not be as high When traversing tree.
For parallel divide and conquer, dfs ordering is likely better than bfs ordering. With dfs ordering, once you divide the problem, the memory sections that each task deals with do not intersect. With bfs ordering the tasks would still be operating on memory sections that interleave