13 releases
0.4.2 | Feb 20, 2021 |
---|---|
0.4.1 | Jan 25, 2021 |
0.3.0 | Feb 21, 2020 |
0.2.1 | Nov 9, 2018 |
0.1.4 | May 26, 2018 |
#139 in Data structures
53,933 downloads per month
Used in 101 crates
(18 directly)
195KB
3.5K
SLoC
This project provides trees data structure serving for general purpose.
Quickstart
Impatient readers can start with the notations.
Features
-
Step-by-step creating, reading, updating, deleting and iterating nodes with assocated data items.
-
Compact notations to express trees:
-
,/
encoded or tuple encoded trees. -
Depth first search cursor.
-
Breadth first search iterators.
-
Trees can be built by stages, with nodes stored scatteredly among memory.
-
Trees can be built once through, with nodes stored contiguously.
-
Support exclusive ownership with static borrow check.
-
Support shared ownership with dynamic borrow check.
Examples
-
notation of a literal tree
use trees::tr; let scattered_tree = tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) ); let piled_tree = trees::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::{Node, tr}; 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.has_no_child() { 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 key-value 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.