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 timesize_hint
of iterators, and missingpop_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
notationuse 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
notationuse 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, usingNode::iter()
recursivelyuse 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
andDisplay
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 rootNode
and an optionalForest
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 ofNode
s 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, andTree
is an ownedNode
. All nodes in a tree can be referenced as&Node
, but only the root node can be observed asTree
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 childNode
s, 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 childNode
s, 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 havepop_back()
, andpotted
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 overSubnode
s, you can:3.1
insert_before
,insert_after()
,depart()
node(s) at any position.3.2 do whatever
iter()
oriter_mut()
can do.Note that it is not implemented for potted version.
-
Using
Forest::<T>::into_iter()
to iterate overTree
s, 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
Node
s 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
forTree
andForest
makes deep copy which clones all its decendant nodes. To do copy for just one node, simplelylet cloned = trees::tr( node.data.clone() );
. -
linked::fully::Node
will track count of children nodes, and count of all descendant nodes and itself, whilelinked::singly::node
does not track any size information.
Traversal in breadth-first manner
-
Node
provides (mutably) borrowed iteratorfn bfs_iter( &self )
/fn bfs_iter_mut( &mut self )
. -
Tree
/Forest
provides owned iteratorfn bfs_into_iter( self )
. -
All version of
Tree
/Forest
/Node
supportInto
BFS streams, while potted version supportsFrom
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.
Safety
Collections of pointer-based tree implementation require many unsafe
s 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
Re-exports
pub use linked::tr;
pub use linked::fr;
pub use linked::Tree;
pub use linked::Forest;
pub use linked::Node;
pub use linked::Iter;
pub use linked::IterMut;
pub use linked::Subnode;
pub use linked::OntoIter;
pub use linked::Visit;
pub use linked::TreeWalk;
pub use linked::ForestWalk;
pub use size::Size;