Trees 0.1.0 published


#1

https://crates.io/crates/trees

The “trees” crate 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.

Quick start

  1. 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) );
  1. 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 equal to the forest descripted above.
tr(0) /(
    -( tr(1) /( -tr(2)-tr(3) ) )
    -( tr(4) /( -tr(5)-tr(6) ) )
);
  1. Preorder traversal
use std::string::{String,ToString};
use trees::{tr,Node};

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) + &" " )
            + &")"
    }
}

let tree = tr(0) /( tr(1) /tr(2)/tr(3) ) /( tr(4) /tr(5)/tr(6) );
assert_eq!( tree_to_string( &tree ), "0( 1( 2 3 ) 4( 5 6 ) )" );

#2

Just publised trees-0.1.1 to correct some typo and formatting problems.

I noticed that the “documentation” item in the navigation menu is missing for the 0.1.1 version, and https://docs.rs/trees/ does not generate the docs for 0.1.1 either.

Is it expected behavior, or had I missed something?


#3

docs.rs’s updater was down for awhile, but it’s back now, and your crate is updated