Trait Traverser

Source

pub trait Traverser<O = OverData>: TraverserCore<O>where
    O: Over,{
    type IntoOver<O2>: TraverserCore<O2> + Traverser<O2>
       where O2: Over;

    // Required methods
    fn new() -> Self;
    fn transform_into<O2: Over>(self) -> Self::IntoOver<O2>;

    // Provided methods
    fn over_data(self) -> Self::IntoOver<O::IntoOverData> { ... }
    fn over_nodes(self) -> Self::IntoOver<O::IntoOverNode> { ... }
    fn with_depth(self) -> Self::IntoOver<O::IntoWithDepth> { ... }
    fn with_sibling_idx(self) -> Self::IntoOver<O::IntoWithSiblingIdx> { ... }
}

Expand description

A tree traverser that creates iterators which walk over a given node and all of its descendants; i.e., over all nodes of the subtree rooted at the given node.

The order the nodes are traversed depend on the specific traverser implementation; some well known traversals are depth-first, breadth-first or post-order.

A traverser holds its temporary data, and therefore, it might be used to create as many iterators as needed without requiring additional allocation.

The following three kinds of node methods can be called with a traverser.

walk_with
- Creates an iterator over references.
- Iterator<Item = &V::Item>
- The tree remains unchanged.
walk_mut_with
- Creates an iterator over mutable references.
- Iterator<Item = &mut V::Item>
- The data of the subtree rooted at the given node might be mutated.
- However, the structure of the tree remains unchanged.
into_walk_with
- Creates an iterator over owned values taken out of the nodes.
- Iterator<Item = V::Item>
- All nodes belonging to the subtree rooted at the given node will be removed.
- Corresponding data of the removed nodes will be yield in the order of the traversal.

§Construction

A traverser can be created by its new or default method such as:

use orx_tree::{*, traversal::*};

let mut traverser = Dfs::default();
let mut traverser = Bfs::default();
let mut traverser = PostOrder::default();

// or traverser to iterate over different items
let mut traverser = Dfs::<OverNode>::new(); // yields Node rather than data
let mut traverser = Bfs::<OverDepthData>::new(); // yields (depth, data)
let mut traverser = PostOrder::<OverDepthSiblingIdxData>::new(); // yields (depth, sibling_idx, data)

However, it is often more convenient to use the Traversal type to create the traverser instances; and transform them to yield different items if needed.

use orx_tree::*;

let mut traverser = Traversal.dfs();
let mut traverser = Traversal.bfs();
let mut traverser = Traversal.post_order();

// or traverser to iterate over different items
let mut traverser = Traversal.dfs().over_nodes(); // yields Node rather than data
let mut traverser = Traversal.bfs().with_depth(); // yields (depth, data)
let mut traverser = Traversal.post_order().with_depth().with_sibling_idx(); // yields (depth, sibling_idx, data)

§Iterating Over Different Values

For immutable walks, it is possible to iterate over Nodes rather than node data.

Further, for all three iterator methods, it is possible to add either or both of:

depth of the traversed node,
sibling_idx of the traversed node among its siblings

to node value which is either node data or the node itself.

The return value of the iterations depend on the second generic parameter of the traverser which implements the Over trait. The following is the complete list of implementations and the corresponding item type of the created iterators. For any Over implementation, the corresponding traverser can be created by using the Default::default() function; however, it is often more convenient to use the Traversal type.

The last column of the table demonstrates how to create different traverser types; where the depth first or dfs is replaceable with any available traversal strategy such as bfs or post_order.

Further, D refers to node data, which is:

&V::Item with iter,
&mut V::Item with iter_mut, and
V::Item with into_iter.

Over	Yields	Depth First Example
`OverData`	D	`Traversal.dfs()`
`OverDepthData`	(depth, D)	`Traversal.dfs().with_depth()`
`OverSiblingIdxData`	(sibling_idx, D)	`Traversal.dfs().with_sibling_idx()`
`OverDepthSiblingIdxData`	(depth, sibling_idx, D)	`Traversal.with_depth().with_sibling_idx()`
`OverNode`	Node	`Traversal.dfs().over_nodes()`
`OverDepthNode`	(depth, Node)	`Traversal.dfs().over_nodes().with_depth()`
`OverSiblingIdxNode`	(sibling_idx, Node)	`Traversal.dfs().over_nodes().with_sibling_idx()`
`OverDepthSiblingIdxNode`	(depth, sibling_idx, Node)	`Traversal.dfs().over_nodes().with_depth().with_sibling_idx()`