Crate vectree 

A simple vector-based tree collection that provides flexible immutable and mutable iterators. See the VecTree type for a list of methods.

Building the tree

The nodes are manipulated by their indices, which are returned by the methods adding a node to the tree.

Example:

use vectree::VecTree;

fn build_tree() -> VecTree<String> {
    // use `with_capacity` if you know the number of nodes:
    let mut tree = VecTree::new();

    // adds the tree root:
    let root: usize = tree.add_root("root".to_string());

    // adds three children to the root:
    let a = tree.add(Some(root), "a".to_string());
    let _ = tree.add(Some(root), "b".to_string());
    let c = tree.add(Some(root), "c".to_string());

    // adds children to existing nodes, "_iter" = from anything iterable
    tree.add_iter(Some(a), ["a1".to_string(), "a2".to_string()]);
    tree.add_iter(Some(c), ["c1", "c2"].map(|s| s.to_string()));

    tree
}

The following methods are used to add nodes:

• VecTree::add(&mut self, parent_index: Option<usize>, item: T)
• VecTree::addc(&mut self, parent_index: Option<usize>, item: T, child: T)
• VecTree::addci(&mut self, parent_index: Option<usize>, item: T, child_id: usize)
• VecTree::addci_iter(&mut self, parent_index: Option<usize>, item: T, children_id: IntoIterator<Item = usize>)
• VecTree::add_iter(&mut self, parent_index: Option<usize>, items: IntoIterator<Item = T>)
• VecTree::addc_iter(&mut self, parent_index: Option<usize>, item: T, children: IntoIterator<Item = T>)

The key to the names is

• “c” when a child or children can be specified
• “i” when indices are used instead of data, if those nodes were previously added to the tree
• “iter” when items are provided by anything iterable, like an array or an iterator

Iterators

The iterators are visiting the nodes in a pre- or post-order, depth-first search. There are simple and full-fledged iterators

• the “simple” iterators give a mutable / immutable reference to each node but not to its children
• the “full-fledged” iterators give a mutable / immutable reference to each node and immutable access to its children, with a variety of iterators.

List of simple post-order iterators:

• VecTree::iter_post_depth_simple (from the top)
• VecTree::iter_post_depth_simple_mut (from the top, mutable reference to node)
• VecTree::iter_post_depth_simple_at (from a specific node)
• VecTree::iter_post_depth_simple_at_mut (from a specific node, mutable reference to node)

List of full-fledged iterators:

• VecTree::iter_post_depth (from the top)
• VecTree::iter_post_depth_mut (from the top, mutable reference to node)
• VecTree::iter_post_depth_at (from a specific node)
• VecTree::iter_post_depth_at_mut (from a specific node, mutable reference to node)

List of pre-order iterators:

• VecTree::iter_pre_depth_simple (simple, from the top)
• VecTree::iter_pre_depth_simple_mut (simple, from the top, mutable reference to node)
• VecTree::iter_pre_depth_simple_at (simple, from a specific node)
• VecTree::iter_pre_depth_simple_at_mut (simple, from a specific node, mutable reference to node)
• VecTree::iter_pre_depth (full-fledged, from the top)
• VecTree::iter_pre_depth_mut (full-fledged, from the top, mutable reference to node)
• VecTree::iter_pre_depth_at (full-fledged, from a specific node)
• VecTree::iter_pre_depth_at_mut (full-fledged, from a specific node, mutable reference to node)

The full-fledged iterators add the following methods to the “proxy” (smart pointer) returned by the iterator:

• NodeProxy::num_children(), to get the number of children
• NodeProxy::iter_children(), to iterate over the children with a proxy to access their children
• NodeProxy::iter_children_simple(), to iterate over the children
• NodeProxy::iter_post_depth_simple(), to iterate the subtree under the node in post-order, depth-first search
• NodeProxy::iter_pre_depth_simple(), to iterate the subtree under the node in pre-order, depth-first search

Examples

Simple iterator:

let mut tree = build_tree();
let mut result = String::new();
let mut result_index = vec![];
let mut result_depth = vec![];
for inode in tree.iter_post_depth_simple() {
    result.push_str(&inode.to_uppercase());
    result.push(',');
    result_index.push(inode.index);
    result_depth.push(inode.depth);
}
assert_eq!(result, "A1,A2,A,B,C1,C2,C,ROOT,");
assert_eq!(result_index, [4, 5, 1, 2, 6, 7, 3, 0]);
assert_eq!(result_depth, [2, 2, 1, 1, 2, 2, 1, 0]);

More complex iterator that gives access to the node’s children:

let mut tree = build_tree();
for mut inode in tree.iter_post_depth_mut() {
    // condition: any child j begins with 'c' and
    //                        all j's children k (if any) begin with 'c'
    let sub_is_c = inode.iter_children()
        .any(|j| {
            j.to_lowercase().starts_with('c') &&
                j.iter_children().all(|k| k.to_lowercase().starts_with('c'))
        });
    if sub_is_c {
        *inode = inode.to_uppercase();
    }
}
let result = tree_to_string(&tree);
assert_eq!(result, "ROOT(a(a1,a2),b,C(c1,c2))");

Important limitation

The VecTree object doesn’t provide methods to delete nodes.

Modules

skip_last

This crate offers a skip_last iterator adapter for convenience when a post-order iterator such as iter_post_depth_simple is used on a depth-first iterator node. Since the post-order search ends with the top item itself, which is the root of the children subtree, it may be desirable to skip it if it’s not required at all.

Structs

IterData

A structure used by full-fledged VecTree iterators that give immutable access to each node, its children, and the whole subtree under that node.

IterDataMut

A structure used by full-fledged VecTree iterators that give mutable access to each node, and also immutable access to its children and the whole subtree under that node.

IterDataSimple

A structure used by simple VecTree iterators that give immutable access to each node but not to its children.

IterDataSimpleMut

A structure used by simple VecTree iterators that give mutable access to each node but no access to its children.

Node

A node of a VecTree<T> collection. It holds a data of type <T> and a list of indices to its children in the tree collection.

NodeProxy

A proxy returned by full-fledged VecTree iterators that give immutable access to each node, its children, and the whole subtree under that node.

NodeProxyMut

A proxy returned by full-fledged VecTree iterators that give mutable access to each node, and also immutable access to its children and the whole subtree under that node.

NodeProxySimple

A proxy returned by simple VecTree iterators that give immutable access to each node but not to its children.

NodeProxySimpleMut

A proxy returned by simple VecTree iterators that give mutable access to each node but no access to its children.

PostOrder

PreOrder

VecTree

A vector-based tree collection type. Each node is of type Node<T>.

VecTreePoDfsIter

A VecTree post-order, depth-first search iterator.

Traits

TreeDataIter

Implements methods used by the depth-first search algorithm and which depends on the type of iterator: simple or full-fledged (allowing to search each node’s children), immutable or mutable.