Lib.rs

Summary

A library that provides a complete binary tree visitor trait with common default implementations for visiting strategies such as dfs_inorder or dfs preorder, etc. It also provides two flavors of a complete binary tree data structure with mutable and immutable visitors that implement the visitor trait.

lib.rs:

Summary

A library that provides a complete binary tree visitor trait with default implementations for visiting strategies such as dfs_inorder or dfs_preorder, 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.

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 extremely 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