Trait TreeIterator

pub trait TreeIterator<Value, Children>: TreeIteratorBase<Value, Children>
where
    Self: Sized,
{
    // Provided methods
    fn prune<F>(self, f: F) -> Prune<Value, Children, Self, F> 
       where F: FnMut(&Value) -> bool { ... }
    fn prune_path<F>(self, f: F) -> PrunePath<Value, Children, Self, F> 
       where F: FnMut(&[usize], &Value) -> bool { ... }
    fn collect_tree(self) -> Option<Tree<Value>> { ... }
    fn fold_tree<F, Output>(self, f: F) -> Option<Output>
       where F: FnMut(Vec<Output>, Value) -> Output { ... }
}

Provided Methods

fn prune<F>(self, f: F) -> Prune<Value, Children, Self, F>

where F: FnMut(&Value) -> bool,

Prune is a tree-based analog to filter. Uses the given closure to determine if each subtree in this tree should be pruned.

Given an element the closure must return true or false. Any nodes in the tree for which this evaluates to true will be pruned out of the resulting tree. If the root node is pruned, any subsequent calls to collect_tree will yield None.

The closure is called on the nodes in a depth first preorder traversal order (see dfs_preorder for more details). If a node is determined to be pruned, its entire subtree will be pruned without calling the closure on its descendent nodes.

Basic usage:

use tree_iterators_rs::prelude::{Tree, TreeIterator, OwnedTreeNode, TreeIteratorBase};

let tree = Tree {
    value: 0,
    children: vec![
        Tree {
            value: 1,
            children: vec![Tree {
                value: 3,
                children: vec![],
            }],
        },
        Tree {
            value: 2,
            children: vec![],
        },
    ],
};

let result = tree.into_pipeline()
    .prune(|value| {
        println!("{value:?}");
        *value == 1
    })
    .collect_tree();

assert_eq!(
    Some(Tree {
        value: 0,
        children: vec![Tree {
            value: 2,
            children: vec![],
        }],
    }),
    result);

The output for this code would be the following. A couple notes about this output:

1. the node with a value of ‘1’ has been removed
2. the closure is never called on the node with a value of ‘3’ since it is already determined to be pruned once ‘1’ has been evaluated.

0
1
2

fn prune_path<F>(self, f: F) -> PrunePath<Value, Children, Self, F>

where F: FnMut(&[usize], &Value) -> bool,

Identical to prune except that the closure is passed an additional parameter: the path of the current node in the tree (see current_path for more details).

fn collect_tree(self) -> Option<Tree<Value>>

Collects the current TreeIterator back into a Tree.

If the TreeIterator is empty (usually due to pruning the root node), yields None.

Example Usage

use tree_iterators_rs::prelude::{Tree, OwnedTreeNode, TreeIterator};

let tree = Tree {
    value: 0,
    children: vec![],
};

let result =
    tree.into_pipeline()
        .collect_tree()
        .expect("the root of the tree to remain un-pruned");

assert_eq!(
    Tree {
        value: 0,
        children: vec![],
    },
    result);

fn fold_tree<F, Output>(self, f: F) -> Option<Output>

where F: FnMut(Vec<Output>, Value) -> Output,

A tree-based analog to fold.

Folds every node in the tree into an accumulated value by applying an operation, returning the final result.

fold_tree() takes one arguments: a closure with two arguments: an ‘accumulator’ (the result of accumulating all children of the current node), and the current node’s value. The closure returns the value that the accumulator should have for the subtree’s parent’s iteration.

After applying this closure to every element of the tree, fold_tree() returns the accumulator.

Folding is useful whenever you have a tree of something, and want to produce a single value from it.

Basic Usage

use tree_iterators_rs::prelude::{Tree, OwnedTreeNode, TreeIterator};

let tree = Tree {
    value: 0,
    children: vec![
        Tree {
            value: 1,
            children: vec![],
        },
        Tree {
            value: 2,
            children: vec![Tree {
                value: 3,
                children: vec![],
            }],
        },
    ],
};

let num_nodes_in_tree =
    tree.into_pipeline()
        .fold_tree(|children, value| {
            let num_nodes_in_subtrees = children
                .into_iter()
                .sum::<usize>();

            num_nodes_in_subtrees + 1
        })
        .expect("the root of the tree to remain un-pruned");

assert_eq!(num_nodes_in_tree, 4);

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<Value, Children, Inner> TreeIterator<Value, Children> for PruneDepth<Value, Children, Inner>

where Inner: TreeIterator<Value, Children>,

impl<Value, Children, InnerIter, F> TreeIterator<Value, Children> for Prune<Value, Children, InnerIter, F>

where InnerIter: TreeIterator<Value, Children>, F: FnMut(&Value) -> bool,

impl<Value, Children, InnerIter, F> TreeIterator<Value, Children> for PrunePath<Value, Children, InnerIter, F>

where InnerIter: TreeIterator<Value, Children>, F: FnMut(&[usize], &Value) -> bool,

impl<Value, Children, InnerIter, F, Output> TreeIterator<Output, ()> for Map<Value, Children, InnerIter, F, Output>

where InnerIter: TreeIterator<Value, Children>, F: FnMut(Value) -> Output,