Crate trees [−] [src]
trees
Provides the Tree
/Forest
data structures which are suitable for storing hierarchical data built from the bottom up.
This crate does not depend on 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) );
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 are the forest descripted above. tr(0) /( -( tr(1) /( -tr(2)-tr(3) ) ) -( tr(4) /( -tr(5)-tr(6) ) ) );
- Preorder traversal
use std::string::{String,ToString}; use trees::{tr,Node}; let tree = tr(0) /( tr(1) /tr(2)/tr(3) ) /( tr(4) /tr(5)/tr(6) ); fn tree_to_string<T:ToString>( node: &Node<T> ) -> String { if node.is_leaf() { node.data.to_string() } else { node.data.to_string() + &"( " + &node.children().fold( String::new(), |s,c| s + &tree_to_string(c) + &" " ) + &")" } } assert_eq!( tree_to_string( &tree ), "0( 1( 2 3 ) 4( 5 6 ) )" );
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 tree: Tree<i32> = tr(0); let forest: Forest<i32> = -tr(1)-tr(2)-tr(3); let mut tree = tree.adopt( forest ); let forest = tree.abandon();
Forest
is composed ofNode
s as its children. A forest can be empty.
use trees::{tr,fr,Tree,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
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(); let first_child : &Node<i32> = tree.children().next().unwrap(); let second_child: &Node<i32> = tree.children().nth(2).unwrap(); let third_child : &Node<i32> = tree.children().last().unwrap(); } let first_child: Tree<i32> = 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.
Structs
Forest |
Collection of circularly-linked |
IntoIter |
An owning iterator over the children of a |
Iter |
An iterator over the direct decendants of a tree |
IterMut |
A mutable iterator over the direct decendants of a tree |
Node |
Tree node implemented in singly-linked-children / circularly-linked-siblings. |
Subtree |
Wrapper of tree |
SubtreeIter |
A mutable iterator over the direct decendants of a |
Tree |
Tree with owned |
Functions
fr |
Makes an empty |
tr |
Creates a |
Type Definitions
StrForest | |
StrNode | |
StrTree |