9 releases
0.2.1  Nov 9, 2018 

0.2.0  Sep 26, 2018 
0.1.6  Jun 19, 2018 
0.1.4  May 26, 2018 
#73 in Data structures
179 downloads per month
Used in 2 crates
265KB
4K
SLoC
This project provides various implementations of trees serving for general purpose.
Features

Traversal
Each node in a tree provides standard forward iterators for visiting its children nodes. Tree traversal can be done using these iterators in recursive function calls.
Depthfirst search and breadthfirst iterators are also provided.

Operation
The methods for adding or removing child tree at the front/back of a node’s children list are guaranteed constant time. Accessing, inserting or removing nodes in any position are linear time.
The
potted
trees constructed in batch mode can randomly access the child nodes in constant time.The library users does not need any
unsafe
code to use this library. 
Notation
Tow compact notations of tree construction has been developed by overloading sub and div operators. They make complex tree composition look like literal expression, reducing a bit of syntax noise.
The first notation is using operator overloading. Using operator '' to express sibling relationship, and '/' to express parentchild relationship. Something like
root /( first_child  second_child )
.The second notation is using Rust tuple, something like
( root, first_child, second_child )
.See the example section for more.
Implementations
Currently this library provides three different trees, implemented in rawpointerlinked or vecbacked nodes.

linked::singly
Two pointers per node. Hold no size infomation. Note that constant timepop_back
is not supported. 
linked::singly
Four pointers plus twou32
s per node. Hold children count and node count. 
potted
Sevenu32
s per node. Hold children count, node count and adjoined children count.
Prominent types
Tree, Forest and Node are the big three types in this library.

Tree is a collection of owned nodes in hierarchical structure, with one toplevel node named root.

Forest is similar to Tree, except that it has no root node.

Node is the underlying storage type and opaque to the library users. Instead,
&Node
/&mut Node
orNodeRef
/NodeMut
are exposed.
Examples

notation of a literal tree
let linked_tree = tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) ); let potted_tree = potted::Tree::from(( 0, (1,2,3), (4,5,6) ));
They both encode a tree drawn as follows:
............. . 0 . . / \ . . 1 4 . . / \ / \ . .2 3 5 6. .............

use tree notation to reduce syntax noise, quoted from crate
reflection_derive
, version 0.1.1:quote! { #( ( ::reflection::variant( stringify!( #vnames )) /( #( ( ::reflection::field( #fnames, <#ftypes1 as ::reflection::Reflection>::ty(), <#ftypes2 as ::reflection::Reflection>::name(), Some( <#ftypes3 as ::reflection::Reflection>::members ))) )* ) ) )* }
The starting of tree operations are denoted by
(
and/(
which are humble enough to let the reader focusing on the data part. 
use iterators if the tree travesal is a "driving wheel"( you can iterate over the tree on your own ).
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 ) )" );

use
TreeWalk
when the tree travesal is a "driven wheel"( driven by other library ). Quoted from cratetsv
, version 0.1.0:fn next_value_seed<V:DeserializeSeed<'de>>( &mut self, seed: V ) > Result<V::Value> { let result = self.next_element_in_row( seed )?; self.de.next_column(); self.de.row += 1; self.de.pop_stack(); // finish keyvalue pair self.de.next_column(); self.de.columns.revisit(); Ok( result ) }
The
serde
library is driving on the schema tree when (de)serializing variables. UseTreeWalk
methods such asnext_column
andrevisit
to follow the step.
License
Under Apache License 2.0 or MIT License, at your will.
Quickstart
API document and quickstart here: docs.rs