Struct trees::linked::fully::walk::TreeWalk

pub struct TreeWalk<T> { /* private fields */ }

Tree traversal

Implementations

impl<T> TreeWalk<T>

pub fn get(&self) -> Option<Visit<'_, T>>

Returns the current node in the tree traversal, or None if the traversal is completed.

Examples

use trees::{tr,Visit,TreeWalk};
let tree = tr(0) / tr(1)/tr(2)/tr(3);
let walk = TreeWalk::from( tree );
assert_eq!( walk.get(), Some( Visit::Begin( ( tr(0)/tr(1)/tr(2)/tr(3) ).root() )));

pub fn forward(&mut self)

Depth first search on TreeWalk. Preorder or postorder at will.

Examples

use trees::{tr,Visit,TreeWalk};
let tree = tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) );
let mut walk = TreeWalk::from( tree );
assert_eq!( walk.get(), Some( Visit::Begin( ( tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) ) ).root() )));
walk.forward();
assert_eq!( walk.get(), Some( Visit::Begin( (tr(1)/tr(2)/tr(3)).root() )));
walk.forward();
assert_eq!( walk.get(), Some( Visit::Leaf ( tr(2).root() )));
walk.forward();
assert_eq!( walk.get(), Some( Visit::Leaf ( tr(3).root() )));
walk.forward();
assert_eq!( walk.get(), Some( Visit::End  ( (tr(1)/tr(2)/tr(3)).root() )));
walk.forward();
assert_eq!( walk.get(), Some( Visit::Begin( (tr(4)/tr(5)/tr(6)).root() )));
walk.forward();
assert_eq!( walk.get(), Some( Visit::Leaf ( tr(5).root() )));
walk.forward();
assert_eq!( walk.get(), Some( Visit::Leaf ( tr(6).root() )));
walk.forward();
assert_eq!( walk.get(), Some( Visit::End  ( (tr(4)/tr(5)/tr(6)).root() )));
walk.forward();
assert_eq!( walk.get(), Some( Visit::End  ( ( tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) ) ).root() )));
walk.forward();
assert_eq!( walk.get(), None );
walk.forward();
assert_eq!( walk.get(), None );

pub fn next(&mut self) -> Option<Visit<'_, T>>

Advance the cursor and return the newly visited node.

NOTICE: the FIRST node in the traversal can NOT be accessed via next() call.

Examples

use trees::{tr,Visit,TreeWalk};
let tree = tr(0) / tr(1)/tr(2)/tr(3);
let mut walk = TreeWalk::from( tree );
assert_eq!( walk.next(), Some( Visit::Leaf( tr(1).root() )));
assert_eq!( walk.next(), Some( Visit::Leaf( tr(2).root() )));
assert_eq!( walk.next(), Some( Visit::Leaf( tr(3).root() )));
assert_eq!( walk.next(), Some( Visit::End( ( tr(0)/tr(1)/tr(2)/tr(3) ).root() )));
assert_eq!( walk.next(), None );
assert_eq!( walk.next(), None );

pub fn to_parent(&mut self) -> Option<Visit<'_, T>>

Set the cursor to the current node’s parent and returns it, or None if it has no parent.

Examples

use trees::{tr,Visit,TreeWalk};
let tree = tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) );
let mut walk = TreeWalk::from( tree );
assert_eq!( walk.get(), Some( Visit::Begin( ( tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) ) ).root() )));
walk.forward();
assert_eq!( walk.get(), Some( Visit::Begin( (tr(1)/tr(2)/tr(3)).root() )));
assert_eq!( walk.to_parent(), Some( Visit::End( ( tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) ) ).root() )));

pub fn get_parent(&self) -> Option<&Node<T>>

Returns the parent of current node, or None if it has no parent.

Examples

use trees::{tr,Visit,TreeWalk};
let tree = tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) );
let mut walk = TreeWalk::from( tree );
assert_eq!( walk.get(), Some( Visit::Begin( ( tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) ) ).root() )));
assert_eq!( walk.get_parent(), None );
walk.forward();
assert_eq!( walk.get(), Some( Visit::Begin( (tr(1)/tr(2)/tr(3)).root() )));
assert_eq!( walk.get_parent(), Some( ( tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) ) ).root() ));

pub fn to_child(&mut self, n: usize) -> Option<Visit<'_, T>>

Set the cursor to the current node’s n-th child and returns it, or None if it has no child. Notice that n == 0 indicating the first child.

Examples

use trees::{tr,Visit,TreeWalk};
let tree = tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) );
let mut walk = TreeWalk::from( tree );
assert_eq!( walk.get(), Some( Visit::Begin( ( tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) ) ).root() )));
walk.to_child( 1 );
assert_eq!( walk.get(), Some( Visit::Begin( (tr(4)/tr(5)/tr(6)).root() )));

pub fn to_sib(&mut self, n: usize) -> Option<Visit<'_, T>>

Set the cursor to the current node’s next n-th sibling and returns it, or None if such sibling does not exist. Returns the current node if n == 0.

Examples

use trees::{tr,Visit,TreeWalk};
let tree = tr(0) / tr(1)/tr(2)/tr(3);
let mut walk = TreeWalk::from( tree );
assert_eq!( walk.next(), Some( Visit::Leaf( tr(1).root() )));
assert_eq!( walk.to_sib( 0 ), Some( Visit::Leaf( tr(1).root() )));
assert_eq!( walk.to_sib( 2 ), Some( Visit::Leaf( tr(3).root() )));

pub fn revisit(&mut self)

Revisit a Node that reached Visit::End. No effect on Visit::Begin or Visit::Leaf.

Examples

use trees::{tr,Visit,TreeWalk};
let tree = tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) );
let mut walk = TreeWalk::from( tree );
for _ in 0..3 {
    for _ in 0..3 {
        walk.revisit();
        assert_eq!( walk.get(), Some( Visit::Begin( ( tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) ) ).root() )));
        walk.forward();
        for _ in 0..3 {
            walk.revisit();
            assert_eq!( walk.get(), Some( Visit::Begin( (tr(1)/tr(2)/tr(3)).root() )));
            walk.forward();
            assert_eq!( walk.get(), Some( Visit::Leaf ( tr(2).root() )));
            walk.forward();
            assert_eq!( walk.get(), Some( Visit::Leaf ( tr(3).root() )));
            walk.forward();
            assert_eq!( walk.get(), Some( Visit::End  ( (tr(1)/tr(2)/tr(3)).root() )));
        }
        walk.forward();
        for _ in 0..3 {
            walk.revisit();
            assert_eq!( walk.get(), Some( Visit::Begin( (tr(4)/tr(5)/tr(6)).root() )));
            walk.forward();
            assert_eq!( walk.get(), Some( Visit::Leaf ( tr(5).root() )));
            walk.forward();
            assert_eq!( walk.get(), Some( Visit::Leaf ( tr(6).root() )));
            walk.forward();
            assert_eq!( walk.get(), Some( Visit::End  ( (tr(4)/tr(5)/tr(6)).root() )));
        }
        walk.forward();
        assert_eq!( walk.get(), Some( Visit::End  ( ( tr(0) /( tr(1)/tr(2)/tr(3) ) /( tr(4)/tr(5)/tr(6) ) ).root() )));
    }
    walk.forward();
    assert_eq!( walk.get(), None );
    walk.forward();
    assert_eq!( walk.get(), None );
}

Trait Implementations

impl<T> From<Tree<T>> for TreeWalk<T>

fn from(tree: Tree<T>) -> Self

Converts to this type from the input type.

impl<T> Into<Tree<T>> for TreeWalk<T>

fn into(self) -> Tree<T>

Converts this type into the (usually inferred) input type.

impl<T: Send> Send for TreeWalk<T>

impl<T: Sync> Sync for TreeWalk<T>