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().

`` ub 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

o create a safe and compact complete binary tree data structure that provides an api hat parallel algorithms can exploit.

Unsafety

ith a regular slice, getting one mutable reference to an element will borrow the ntire slice. The slice that GenTree uses, however, internally has the invariant that it is laid out n BFS order. Therefore one can safely assume that if (starting at the root), ne had a mutable reference to a parent k, and one were to get the children using 2k+1 and 2k+2 o get two mutable references to the children, hey would be guarenteed to be distinct (from each other and also the parent) despite the fact that they belong to the same slice.

Example

`` xtern crate compt; n 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));
   }

``