The "trees" project written in rust aims at:
-
expressing hierarchical data conveniently and compactly.
-
storing and manipulating tree-like data structure the simple way.
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
notation
use 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
notation
use ; // 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
and Display
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.