Crate compt [−] [src]
Summary
A Complete Binary Tree library. It is internally represented as a 1D vec. Provides a way to get mutable references to children nodes simultaneously. Useful for parallelizing divide and conquer style problems. There is no api to add and remove nodes. The existence of the tree implies that 2k-1 elements already exist. It is a full tree. Provides tree visitors that implement the below trait. They can be combined together using zip().
pub trait CTreeIterator:Sized{ type Item; ///Consume this visitor, and produce the element it was pointing to ///along with it's children visitors. fn next(self)->(Self::Item,Option<(Self,Self)>); }
Goals
To create a safe and compact complete binary tree data structure that provides an api that parallel algorithms can exploit.
Unsafety
With a regular slice, getting one mutable reference to an element will borrow the entire slice. The slice that GenTree uses, however, internally has the invariant that it is laid out in BFS order. Therefore one can safely assume that if (starting at the root), one had a mutable reference to a parent k, and one were to get the children using 2k+1 and 2k+2 to get two mutable references to the children, they would be guarenteed to be distinct (from each other and also the parent) despite the fact that they belong to the same slice.
Example
extern crate compt; fn main() { use compt::CTreeIterator; //Create a tree of height 2 with elemenets set to zero. let mut tree=compt::GenTree::from_bfs(||0,2); { //Create a mutable tree visitor. let mut down=tree.create_down_mut(); //Call the iterator's next() function. let (e,maybe_children)=down.next(); //Set the root to 1. *e=1; //Set the children to 2 and 3. let (mut left,mut right)=maybe_children.unwrap(); *left.next().0=2; *right.next().0=3; } { //Create a immutable tree visitor. let down=tree.create_down(); //Iterate dfs over our constructed tree. let mut v=Vec::new(); down.dfs_postorder(|a|{ v.push(*a); }); assert_eq!(v,vec!(3,2,1)); } }
Structs
DownT |
Tree visitor that returns a reference to each element in the tree. |
DownTMut |
Tree visitor that returns a mutable reference to each element in the tree. |
GenTree |
The complete binary tree. Internally stores the elements in a Vec |
LevelDesc |
A level descriptor. This is passed to LevelIter. |
LevelIter |
A wrapper iterator that will additionally return the depth of each element. |
Wrap |
Allows to traverse down from a visitor twice by creating a new visitor that borrows the other. |
ZippedDownTMut |
Tree visitor that zips up two seperate visitors. If one of the iterators returns None for its children, this iterator will return None. |
Traits
CTreeIterator |
All binary tree visitors implement this. |
Functions
compute_num_nodes |
Compute the number of nodes in a complete binary tree based on a height. |