[][src]Crate compt

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

Modules

bfs_order

A complete binary tree stored in a Vec laid out in bfs order.

dfs_order

A complete binary tree stored in a Vec laid out in dfs in order. One advantage of using the dfs order over the bfs order, is that at any point during traversal of the tree, you can turn the visitor into a slice representing the rest of the nodes underneath that visitor.

Structs

BfsIter

Bfs Iterator. Each call to next() returns the next element in bfs order. Internally uses a VecDeque for the queue.

Depth

A level descriptor.

DfsInOrderIter

Dfs in order iterator. Each call to next() will return the next element in dfs in order. Internally uses a Vec for the stack.

DfsPreOrderIter

Dfs preorder iterator. Each call to next() will return the next element in dfs order. Internally uses a Vec for the stack.

Flip

Flips left and right children.

LevelIter

A wrapper iterator that will additionally return the depth of each element.

Map

Map iterator adapter

Take

Only returns children up untill level num.

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

FixedDepthVisitor

If implemented, then the level_remaining_hint must return the exact height of the tree. If this is implemented, then the exact number of nodes that will be returned by a dfs or bfs traversal is known so those iterators can implement TrustedLen in this case.

Visitor

The trait this crate revoles around. A complete binary tree visitor.

Functions

compute_height

Computes the height for the number of nodes given. Returns the number of trailing zeroes after the last bit in the binary representation. For complete binary trees this would be the height.

compute_num_nodes

Compute the number of nodes in a complete binary tree based on a height.