The "trees" project written in rust aims at:
-
a fundamental library for storing and manipulating tree-like data structures.
-
expressing hierarchical data conveniently and compactly.
The implementation is straightforward:
-
none-intrusive nodes with child-sibling pointers.
-
children nodes, or forest, are singly-linked circular list.
This crate does not depend on libstd, and can be regarded as the nonlinear version of std::collections::LinkedList.
API document: docs.rs
Quick start
-
Tree
notationuse tr; // tr stands for tree tr; // A single tree node with data 0. tr(0) has no children tr /tr; // tr(0) has one child tr(1) tr /tr/tr; // 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 / /;
-
Forest
notationuse ; // fr stands for forest ; // An empty forest fr - tr; // forest has one child tr(1) - tr; // forest has one child tr(1). The fr() can be omitted. The Neg operator for Tree converts the tree to a forest. - tr - tr; // forest has child tr(1) and tr(2) tr - tr; // 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). - -; // A tree tr(0) whose children equal to the forest descripted above. tr /;
-
Preorder traversal
use ; use ; let tree = tr / /; assert_eq!;
-
String representation
The
Debug
andDisplay
trait has been implemented and are 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 ; let tree = tr / /; let str_repr = "0( 1( 2 3 ) 4( 5 6 ) )"; assert_eq!; assert_eq!; assert_eq!; assert_eq!; let forest = - -; let str_repr = "( 1( 2 3 ) 4( 5 6 ) )"; assert_eq!; assert_eq!;
Slow start
Concepts
-
Tree
is composed of a rootNode
and an optionalForest
as its children. A tree can NOT be empty.use ; let tree: = tr; let forest: = -tr-tr-tr; let mut tree = tree.adopt; let forest = tree.abandon;
-
Forest
is composed ofNode
s as its children. A forest can be empty.use ; let mut forest: = fr; // an empty forest forest.push_back; // forest has one tree forest.push_back; // forest has two trees
-
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 ; use Borrow; let mut tree: = tr /tr/tr/tr; let first_child: = tree.pop_front.unwrap;
Iterators
The children nodes of a node, or a forest, is conceptually a forward list.
-
Using
children()
to iterate over referenced childNode
s, you can:-
read the data associated with each node.
-
using
children()
to iterate over children's children, perhaps read the data associated with children's children, etc.
-
-
Using
children_mut()
to iterate over referenced childNode
s, you can:-
read/write the data associated with each node, or
adopt()
,abandon()
,push_front()
,pop_front()
,push_back()
child node(s) in constant time. -
using
children_mut()
to iterate over children's children, perhaps read/write the data associated with children's children, oradopt()
,abandon()
,push_front()
,pop_front()
,push_back()
child node(s) in constant time, etc.
-
-
Using
subtrees()
to iterate overSubtree
s, you can:-
insert_sib()
,remove()
node(s) at given position in the children forward list in O(n) time. -
do whatever
children()
orchildren_mut()
allows to do.
-
-
Using
Forest::<T>::into_iter()
to iterate overTree
s, you can:- do whatever you want to.
Resource management
-
Tree
/Forest
are implemented in extrusive manner with two extra pointers per node, and will recursively destruct all the nodes owned by the tree/forest 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() );
. -
No bookkeeping of size information.
Panics
No panics unless Clone
is involved:
-
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.
Panics if and only if T::clone()
panics.