[trees 0.2.0] Writing trees in tuples

announcements
1

The version of trees project has been bumped to 0.2.0 with significant changes:

  • Introducing a new tree implementation named potted tree.
  • Dividing linked tree implementation into linked::singly and linked::fully.

The potted tree, for top-down construction

The library users can write potted trees in Rust tuples:

let potted_tree = potted::Tree::from(( 0, (1,2,3), (4,5,6) ));

The potted_tree encodes a tree drawn as follows:

.............
.     0     .
.   /   \   .
.  1     4  .
. / \   / \ .
.2   3 5   6.
.............

Any type as the tree node’s data type must impl TreeData trait.

impl TreeData for CustomType {}

The TreeData trait has already been implemented for the primitive types and string types.

This implementation use a Vec as its underlying storage of nodes. During tree construction from tuple, there will be only 2 dynamic memory allocations, and one of them can be elided as soon as Rust supports variadic generics.

The nth_child() of any node can be accessed in constant time, as long as no insertions/deletions happened. Insertion and deletion are always in constant time, and the children list will look more like linked list than array with more and more insertions/deletions.

The potted tree can be constructed from linked trees also, with breadth-first-search iter as medium.

The linked tree, for bottom-up construction

The library users can write linked trees in expressions composed of tree nodes linked by operator - and /:

let linked_tree = tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) );
let linked_tree = tr(0) /( tr(1) / (tr(2)-tr(3)) ) -( tr(4) / (tr(5)-tr(6)) ));

The linked_tree encodes a tree drawn as follows:

.............
.     0     .
.   /   \   .
.  1     4  .
. / \   / \ .
.2   3 5   6.
.............

This implementation use Boxes as its underlying storage of nodes. During the tree construction from expressions, there will be dynamic memory allocations as many as the node count.

Breaking changes

  • The mod name of linked tree implementation has be renamed as linked::fully and linked::singly, and the default tree is fully-linked rather than singly-linked.
  • Names of Iterators have been renamed in compliance with Rust naming conventions. Two old names children()/children_mut are still available but marked deprecated.

The project source code is here. Advises and code reviews are welcomed.
API doc is here.