Crate trees

Expand description

trees

General purpose tree library.

The current version provides two implementions of heap-allocated, child-sibling linked trees and one implementation of vec-backed tree.

The default implementation is linked::fully, which stores previous/next sibling and parent/child pointers in one node, with size information tracked.
The alternative linked tree is linked::singly, which stores only next sibling and last child pointers in one node, without size information tracked. The space cost is minimal, but with a few penalties on time cost or lack of function, e.g. linear time size_hint of iterators, and missing pop_back().
The other alternative using vec as its underlying storage is potted. The memory allocations are minimal, and trees can be written in Rust tuples. Random access over child nodes is supported for tree/forest constructed in batch mode.

More kinds of trees will be added in the future.

This crate can be used with or without libstd.

Quick start

Tree notation

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) has one child tr(1)
tr(0) /tr(1)/tr(2); // tr(0) has children tr(1) and tr(2)
 
// tr(0) has children tr(1) and tr(4), while tr(1) has children tr(2) and tr(3), and tr(4) has children tr(5) and tr(6).
// The spaces and carriage returns are for pretty format and do not make sense.
tr(0)
    /( tr(1) /tr(2)/tr(3) )
    /( tr(4) /tr(5)/tr(6) );

The potted version:

// the trees written in potted tree, same as described above
use trees::potted::{Tree,TreeData,TupleTree};
Tree::from(( 0, ));
Tree::from(( 0, 1 ));
Tree::from(( 0, 1, 2 ));

Forest notation

use trees::{tr,fr}; // fr stands for forest

fr::<i32>();        // An empty forest
fr() - tr(1);       // forest has one child tr(1)
- tr(1);            // forest has one child tr(1). The fr() can be omitted. The Neg operator for Tree converts the tree to a forest.
- tr(1) - tr(2);    // forest has child tr(1) and tr(2)
tr(1) - tr(2);      // forest has child tr(1) and tr(2). The leading neg can be omitted.
 
// forest has children tr(1) and tr(4), while tr(1) has children tr(2) and tr(3), and tr(4) has children tr(5) and tr(6).
-( tr(1) /tr(2)/tr(3) )
-( tr(4) /tr(5)/tr(6) );

// A tree tr(0) whose children equal to the forest descripted above.
tr(0) /(
    -( tr(1) /( -tr(2)-tr(3) ) )
    -( tr(4) /( -tr(5)-tr(6) ) )
);

The potted version:

// the forests written in potted tree, same as described above
use trees::potted::{Forest,TreeData,TupleForest,fr};

Forest::<i32>::new(); Forest::<i32>::from(( fr(), ));
Forest::from(( fr(), 1 ));
Forest::from(( fr(), 1, 2 ));
Forest::from(( fr(), (1,2,3), (4,5,6) ));

Tree traversal, using Node::iter() recursively

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.is_leaf() {
        node.data.to_string()
    } else {
        format!( "{}( {})", node.data, 
            node.iter().fold( String::new(),
                |s,c| s + &tree_to_string(c) + &" " ))
    }
}

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

String representation

The Debug and Display trait has been implemented that is essentially the same as tree_to_tring() mentioned above.

Children are seperated by spaces and grouped in the parentheses that follow their parent closely.

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!( format!( "{:?}", tree ), 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 );
assert_eq!( format!( "{:?}", fr::<i32>() ), "()" );

Slow start

Concepts

Tree is composed of a root Node and an optional Forest as its children. A tree can NOT be empty.

use trees::{tr,Tree,Forest};

let mut tree: Tree<i32> = tr(0);

let forest: Forest<i32> = -tr(1)-tr(2)-tr(3);
tree.append( forest );
assert_eq!( tree, tr(0) /tr(1) /tr(2) /tr(3) );

{ let _forest: &Forest<i32>     = tree.forest();     }
{ let _forest: &mut Forest<i32> = tree.forest_mut(); }
{ let _forest: Forest<i32>      = tree.abandon();    }

assert_eq!( tree, tr(0) );

The potted version:

// `potted::Forest` cannot be borrowed from `potted::Tree`, and `abandon` is different.
use trees::potted::{Tree,Forest,TreeData,TupleTree,TupleForest,fr};

let mut forest = Forest::from(( fr(), 1, 2, 3 ));
let mut tree = forest.adopt( 0 );
assert_eq!( tree.to_string(), "0( 1 2 3 )" );
let ( root_data, forest ) = tree.abandon();
assert_eq!( root_data, 0 );
assert_eq!( forest.to_string(), "( 1 2 3 )" );

Forest is composed of Nodes as its children. A forest can be empty.

use trees::{tr,fr,Forest};

let mut forest: Forest<i32> = fr(); // an empty forest
forest.push_back( tr(1) );          // forest has one tree
forest.push_back( tr(2) );          // forest has two trees

The potted version:

use trees::potted::{Tree,Forest,TreeData,TupleForest};
let mut forest = Forest::<i32>::new(); // an empty forest
forest.append_tr(( 1, 2, 3 ));         // forest has three nodes

Node is a borrowed tree, and Tree is an owned Node. All nodes in a tree can be referenced as &Node, but only the root node can be observed as Tree by the user.

use trees::{tr,Tree,Node};
use std::borrow::Borrow;

let mut tree: Tree<i32> = tr(0) /tr(1)/tr(2)/tr(3);
{
    let root: &Node<i32> = tree.borrow(); // you can also use tree.root()
    let first_child : &Node<i32> = tree.iter().next().unwrap();
    let second_child: &Node<i32> = tree.iter().nth(1).unwrap();
    let third_child : &Node<i32> = tree.iter().last().unwrap();
}
let first_child: Tree<i32> = tree.pop_front().unwrap();

The potted version:

use trees::potted::{Tree,Node,TreeData,TupleTree};
let mut tree = Tree::from(( 0, 1, 2, 3 ));
{
    let root: &Node<i32> = tree.root();
    let first_child : &Node<i32> = tree.root().iter().next().unwrap();
    let second_child: &Node<i32> = tree.root().nth_child(1).unwrap(); // `nth_child()` is in constant time.
    let third_child : &Node<i32> = tree.root().iter().last().unwrap();
}

Iterators

The children nodes of a node, or a forest, is conceptually a forward list.

Using iter() to iterate over referenced child Nodes, you can:

1.1 read the data associated with each node.

1.2 use iter() to iterate over children’s children, etc.
Using iter_mut() to iterate over referenced child Nodes, you can:

2.1 read/write the data associated with each node, or prepend(), append, abandon(), push_front(), pop_front(), push_back(), pop_back() child node(s) in constant time.

Note that linked::singly does not have pop_back(), and potted tree/forest’s methods are different in names and/or functionalities.

2.2 use iter_mut() to iterate over children’s children, etc.
Using onto_iter() to iterate over Subnodes, you can:

3.1 insert_before, insert_after(), depart() node(s) at any position.

3.2 do whatever iter() or iter_mut() can do.

Note that it is not implemented for potted version.
Using Forest::<T>::into_iter() to iterate over Trees, you can:

Do whatever you want to.

Note that it is not implemented for potted version.

Traversal in depth-first manner

Using TreeWalk/ForestWalk to traverse on Tree/Forest, you can:

read the data associated with each descendant node in depth first manner, preorder or postorder at will.
visit Nodes irregularly, unlike the iterators mentioned above that are usually called intensively.

Note that it is not implemented yet for potted version.

Resource management

Tree/Forest will recursively destruct all the nodes owned by them when reaching the end of their lifetimes.
Clone for Tree and Forest makes deep copy which clones all its decendant nodes. To do copy for just one node, simplely let cloned = trees::tr( node.data.clone() );.
linked::fully::Node will track count of children nodes, and count of all descendant nodes and itself, while linked::singly::node does not track any size information.

Traversal in breadth-first manner

Node provides (mutably) borrowed iterator fn bfs_iter( &self )/fn bfs_iter_mut( &mut self ).
Tree/Forest provides owned iterator fn bfs_into_iter( self ).
All version of Tree/Forest/Node support Into BFS streams, while potted version supports From BFS streams also.

Panics

One cause of panics is tree data’s Clone:

Node::<T>::to_owned()
Tree::<T>::clone()
Forest::<T>::clone()
all of the operator overloading functions the operands of which contain at least one referenced type.

A few assertions in potted version can also cause panics.

Collections of pointer-based tree implementation require many unsafes to do raw pointer dereferences. Currently this crate contains nearly 200 unsafe blocks in its source code. This crate relies on lifetime bounds and borrow check to keep memory-safety, in compile time. The following are some simple demonstrations.

use trees::tr;

let root; // node reference can not live longer than tree
{
    let tree = tr(0);
    root = tree.root();
}

use trees::tr;

let root; // mutable node reference can not longer than tree
{
    let mut tree = tr(0);
    root = tree.root_mut();
}

use trees::tr;

let mut tree = tr(0) /tr(1);
let child = tree.iter().next();
tree.abandon(); // can not drop sub trees being borrowed

use trees::{Node,tr};

let mut tree = tr(0) /tr(1);
let child1 = tree.iter_mut().next();
let child2 = tree.iter_mut().next(); // can not have two mutable references on the same node