Crate compt

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

BfsIter	Bfs Iterator. Each call to next() returns the next element in bfs order. Internally uses a VecDeque for the queue.
DfsPreorderIter	Dfs iterator. Each call to next() will return the next element in dfs order. Internally uses a Vec for the stack.
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 so it is very compact. Height is atleast 1. Elements stored in BFS order. Has 2k-1 elements where k is the height.
LevelDesc	A level descriptor. This is passed to LevelIter.
LevelIter	A wrapper iterator that will additionally return the depth of each element.
WrapGen	Allows to traverse down from a visitor twice by creating a new visitor that borrows the other.
Zip	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.