trees

Quickstart

Impatient readers can start with the notation chapter.

Overview

1. Step-by-step creating, reading, updating, deleting and iterating nodes with assocated data items.

2. Compact notations to express trees: -,/ encoded or tuple encoded trees.

3. Depth first search cursor.

4. Breadth first search iterators.

5. Trees can be built by stages, with nodes stored scatteredly among memory.

6. Trees can be built once through, with nodes stored contiguously.

7. Support exclusive ownership with static borrow check.

8. Support shared ownership with dynamic borrow check.

Concepts

The definitions of trees are as follows:

• A tree is composed of one or more nodes.

• A node has zero or more nodes as its children.

• A node has zero or one node as its parent.

• The node without parent is called the tree's root.

• A node associates data of generic type, and data of all nodes in the same tree must be of the same type.

• Children nodes preserve insertion order.

• A forest is composed of zero or more nodes.

• A node's children is a non-owning forest.

• Two node's are siblings if their parents are the same node.

Tree

Tree is composed of one or more Nodes. A tree is always non-empty.

Tree root

Tree can be constructed from a root value of type T, which can be accessed later via root() and root_mut().

Children

Tree can insert/delete child Nodes at front/back of its children list, which is a conceptual Forest and can be removed once the abandon() is called.

Degree

The amount of child nodes of a tree is called tree's degree().

The amount of all nodes of a tree is returned by node_count().

Breadth first search

A Tree may be converted to an owning iterator via into_bfs(), which iterates all its nodes in the manner of breadth first search.

Forest

A Forest is composed of zero or more Nodes. An empty forest is constructed via Forest::new().

Children

A Forest can be considered as a list of Nodes, with the ability of inserting/deleting child nodes at its front/back: push_front(), push_back(), pop_front() and pop_back(). The first and last child can be accessed via front()/front_mut() and back()/back_mut().

A forest can merge another one via prepend() or append().

Forest's children can be iterated via iter()/iter_mut()/into_iter().

Degree

The amount of child nodes of a forest is called forest's degree(). A forest has_no_child() if its degree is 0.

The amount of desendant nodes of a forest is returned by node_count().

Breadth first search

A Forest may provide bfs()/bfs_mut()/into_bfs(), which iterate all its child nodes in the manner of breadth first search.

Node

A Node is associated with data of type T, which is accessible via data()/data_mut() or even pub data field.

Node may have zero or more Nodes as its children; zero or one node as its parent().

Node can be cloned to an owning Tree via to_tree(), with all its descendant nodes cloned.

Node can be detach()-ed from its parent, making a standalone Tree.

Children

The children of a Node can be considered as a list of Nodes, with the ability of inserting/deleting child nodes at its front/back: push_front(), push_back(), pop_front() and pop_back(). The first and last child can be accessed via front()/front_mut() and back()/back_mut().

A forest can be merged via prepend() or append().

Node's children can be iterated via iter()/iter_mut()/into_iter().

Siblings

Two node's are siblings if their parents are the same node.

Node can add an sibling node before/after itself via insert_prev_sib()/ insert_next_sib().

Degree

The amount of child nodes of a node is called node's degree(). A node has_no_child() if its degree is 0.

The amount of all nodes( including itself and its descendants ) of a node is returned by node_count().

Breadth first search

A Node may provide bfs()/bfs_mut(), which iterate all its child nodes in the manner of breadth first search.

Create, read, update, delete

Tree CRUD APIs

A tree can be created via Tree::new() which constructs the root node only with associated data.

#![allow(unused)]
fn main() {
use trees::Tree;
let mut tree = Tree::new(9);
}

This will construct a tree composed of only one root node with data 9.

.............
.     9     .
.............

The root node can be accessed via Tree::root()/Tree::root_mut().

#![allow(unused)]
fn main() {
let root = tree.root();
assert!( root.has_no_child() );
}

The associated data can be read/updated via Tree::data()/Tree::data_mut().

#![allow(unused)]
fn main() {
assert_eq!( root.data(), &9 );

let root = tree.root_mut();
*root.data_mut() = 0;
}

The root data has been modified:

.............
.     0     .
.............

A tree can adopt other trees as children via Tree::push_back().

#![allow(unused)]
fn main() {
tree.push_back( Tree::new(1) );
tree.push_back( Tree::new(2) );
}

This will add two child nodes.

.............
.     0     .
.   /   \   .
.  1     2  .
.............

The child nodes can be accessed via iter().

#![allow(unused)]
fn main() {
let iter = tree.iter();
assert_eq!( iter.next().unwrap().data(), &1 );
assert_eq!( iter.next().unwrap().data(), &2 );
}

Specially, the first/last child can be accessed via front()/back().

#![allow(unused)]
fn main() {
assert_eq!( tree.front().unwrap().data(), &1 );
assert_eq!( tree.back() .unwrap().data(), &2 );
}

A node can adopt other trees as children via Node::push_back().

#![allow(unused)]
fn main() {
let node_1 = tree.front_mut().unwrap();
node_1.push_back( Tree::new(3) );
node_1.push_back( Tree::new(4) );
node_1.push_back( Tree::new(5) );
}

The tree will be:

.............
.     0     .
.   /   \   .
.  1     2  .
. /|\       .
.3 4 5      .
.............

Nodes can be removed via Node::detach().

#![allow(unused)]
fn main() {
let tree_4 = node_1.iter_mut().nth(1).unwrap().detach();
}

The tree will be:

.............
.     0     .
.   /   \   .
.  1     2  .
. / \       .
.3   5      .
.............

Specially, the first/last child can be removed via pop_front()/pop_back().

#![allow(unused)]
fn main() {
node_1.pop_front();
}

The tree will be:

.............
.     0     .
.   /   \   .
.  1     2  .
.  |        .
.  5        .
.............

Forest CRUD APIs

The Forest's APIs are similar with Tree's. The main difference is that a Forest does not have root data, and may be empty.

Node CRUD APIs

The Node's APIs are similar with Tree's. The main difference is that Nodes provided to library users are always in the form of &Node<_> or Pin<&mut Node<_>>, which do not have ownership.

Notations

Using push_back() to construct a big tree can be verbose. This library provides some convenient notations to express trees compactly.

Operator overloading of -, / for scatteredly stored trees

Tree notations

#![allow(unused)]
fn main() {
use trees::tr;      // tr stands for tree

tr(0);              // a single tree node with data 0. tr(0) has no children
tr(0) /tr(1);       // tr(0) with one child tr(1)
tr(0) /tr(1)/tr(2); // tr(0) with children tr(1) and tr(2)

// tr(0) with children tr(1) and tr(4),
// tr(1) with children tr(2) and tr(3),
// tr(4) with children tr(5) and tr(6).
// Spaces and line breaks are for pretty format only.
tr(0)
    /( tr(1) /tr(2)/tr(3) )
    /( tr(4) /tr(5)/tr(6) );
}

Forest notations

#![allow(unused)]
fn main() {
use trees::{fr, tr}; // fr stands for forest

fr::<i32>();        // an empty forest
fr() - tr(1);       // forest with one child tr(1)
- tr(1);            // same forest as above, the leading `fr()` can be omitted.
- tr(1) - tr(2);    // forest with child tr(1) and tr(2).
tr(1) - tr(2);      // same forest as above, the leading `-` can be omitted.

// forest with children tr(1) and tr(4),
// tr(1) with children tr(2) and tr(3),
// tr(4) with children tr(5) and tr(6).
-( tr(1) /tr(2)/tr(3) )
-( tr(4) /tr(5)/tr(6) );

// A tree tr(0) whose children are the forest described above.
tr(0) /(
    -( tr(1) /( -tr(2)-tr(3) ) )
    -( tr(4) /( -tr(5)-tr(6) ) )
);
}

Tuples for contiguously stored trees

Tree notations

#![allow(unused)]
fn main() {
let tree = trees::Tree::<i32>::from_tuple(( 0, (1,2,3), (4,5,6) ));
}

The constructed tree is equvalent to:

#![allow(unused)]
fn main() {
tr(0) /(
    -( tr(1) /( -tr(2)-tr(3) ) )
    -( tr(4) /( -tr(5)-tr(6) ) )
);
}

Forest notations

#![allow(unused)]
fn main() {
let forest = trees::Forest::<i32>::from_tuple(( (1,2,3), (4,5,6) ));
}

The constructed forest is equivalent to:

#![allow(unused)]
fn main() {
-( tr(1) /( -tr(2)-tr(3) ) )
-( tr(4) /( -tr(5)-tr(6) ) );
}

String representation

In current implementation of Display, children are separated by spaces and grouped in the parentheses that follow their parent closely.

Example

.............
.     0     .
.   /   \   .
.  1     4  .
. / \   / \ .
.2   3 5   6.
.............

String representation of the tree drawn above is:

0( 1( 2 3 ) 4( 5 6 ) )

#![allow(unused)]
fn main() {
use trees::{tr, fr};

let tree = tr(0) /( tr(1) /tr(2)/tr(3) ) /( tr(4) /tr(5)/tr(6) );
let str_repr = "0( 1( 2 3 ) 4( 5 6 ) )";
assert_eq!( tree.to_string(), str_repr );

assert_eq!( fr::<i32>().to_string(), "()" );

let forest = -( tr(1) /tr(2)/tr(3) ) -( tr(4) /tr(5)/tr(6) );
let str_repr = "( 1( 2 3 ) 4( 5 6 ) )";
assert_eq!( forest.to_string(), str_repr );
}

Traversal via iterators

Node provides iterators iter()/iter_mut() to iterate over its child nodes, each of which provides iterators to iterate over their child nodes, and so on.

Example

#![allow(unused)]
fn main() {
use trees::{tr, Node};
use std::fmt::Display;

let tree = tr(0)
    /( tr(1) /tr(2)/tr(3) )
    /( tr(4) /tr(5)/tr(6) );

fn tree_to_string<T:Display>( node: &Node<T> ) -> String {
    if node.has_no_child() {
        node.data.to_string()
    } else {
        format!( "{}( {})", node.data, 
        node.iter().fold( String::new(),
            |s,c| format!( "{}{} ", s, tree_to_string(c) ))
    }
}

assert_eq!( tree_to_string( &tree ), "0( 1( 2 3 ) 4( 5 6 ) )" );
}

Depth first traversal

Tree<T>/Forest<T> can be converted to TreeWalk<T>/ForestWalk<T> which act like cursors for depth first traversal.

Keeping on get()-ing current node then forward()ing the cursor results in a depth first search sequence. The two operations are combined as next().

During traversal, the cursor can jump to_parent()/to_child()/to_sib() at any time. To restart DFS search of a node, use revisit().

Example

#![allow(unused)]
fn main() {
use trees::{tr, Visit, TreeWalk};

let tree = tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) );
let mut walk = TreeWalk::from( tree );
assert_eq!( walk.get(), Some( Visit::Begin(
    ( tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) ) )
    .root() )));

walk.forward();
assert_eq!( walk.get(), Some( Visit::Begin(
    ( tr(1) /tr(2)/tr(3) )
    .root() )));

walk.forward();
assert_eq!( walk.get(), Some( Visit::Leaf(
    tr(2)
    .root() )));

walk.forward();
assert_eq!( walk.get(), Some( Visit::Leaf(
    tr(3)
    .root() )));

walk.forward();
assert_eq!( walk.get(), Some( Visit::End(
    ( tr(1) /tr(2)/tr(3) )
    .root() )));

walk.forward();
assert_eq!( walk.get(), Some( Visit::Begin(
    ( tr(4) /tr(5)/tr(6) )
    .root() )));

walk.forward();
assert_eq!( walk.get(), Some( Visit::Leaf(
    tr(5)
    .root() )));

walk.forward();
assert_eq!( walk.get(), Some( Visit::Leaf(
    tr(6)
    .root() )));

walk.forward();
assert_eq!( walk.get(), Some( Visit::End(
    ( tr(4) /tr(5)/tr(6) )
    .root() )));

walk.forward();
assert_eq!( walk.get(), Some( Visit::End(
    ( tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) ) )
    .root() )));

walk.forward();
assert_eq!( walk.get(), None );

walk.forward();
assert_eq!( walk.get(), None );
}

Breath first traversal

Tree/Forest/Node may provide bfs()/bfs_mut()/into_bfs(), which iterate all its child nodes in the manner of breadth first search. Note that not all data structures provide all three kinds of iterators.

During breadth first search, you can get:

1. data associated with Node.

2. size info -- degree and node count.

Example of BFS iteration

#![allow(unused)]
fn main() {
use trees::{Size, bfs, tr};

let tree = tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) );
let visits = tree.into_bfs().iter.collect::<Vec<_>>();
assert_eq!( visits, vec![
    bfs::Visit{ data: 0, size: Size{ degree: 2, descendants: 6 }},
    bfs::Visit{ data: 1, size: Size{ degree: 2, descendants: 2 }},
    bfs::Visit{ data: 4, size: Size{ degree: 2, descendants: 2 }},
    bfs::Visit{ data: 2, size: Size{ degree: 0, descendants: 0 }},
    bfs::Visit{ data: 3, size: Size{ degree: 0, descendants: 0 }},
    bfs::Visit{ data: 5, size: Size{ degree: 0, descendants: 0 }},
    bfs::Visit{ data: 6, size: Size{ degree: 0, descendants: 0 }},
]);
}

Trees can be constructed from and converted into an owning BFS iterator, making it a bridge for conversions between trees.

Example of collecting scattered nodes to piled ones

#![allow(unused)]
fn main() {
use trees::{Tree, tr};

let scattered_tree = tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) );
let piled_tree = Tree::<i32>::from( scattered_tree.into_bfs() );
}

Shared ownership

Trees, Forests have exclusive ownership and borrowing of their Nodes are statically checked.

A Tree could be safely converted to RcNode to support shared ownership and dynamic borrow check.

#![allow(unused)]
fn main() {
use trees::{RcNode, Tree};
let tree = Tree::<i32>::from(( 0, (1,2,3), (4,5,6), ));
let root = RcNode::from( tree );
}

An RcNode could be unsafely converted to Tree to get exclusive ownership and static borrow check.

#![allow(unused)]
fn main() {
let tree = unsafe{ root.into_tree() };
}

WeakNode is the non-owning version of RcNode.