Struct trees::Subtree

pub struct Subtree<T> { /* fields omitted */ }

Wrapper of tree Node with the additional function of inserting/removing node at given position in the subtrees in O(n) time.

Methods

impl<T> Subtree<T>

pub fn insert_sib(&mut self, sib: Tree<T>)

Insert the sib node after self node. The newly inserted node will not be iterated over by the currently running iterator.

Examples

insert after

use trees::tr;

let mut forest = tr(1)-tr(2)-tr(3);
for mut sub in forest.subtrees() {
        sub.insert_sib( tr(3) );
}
assert_eq!( forest, tr(1)-tr(3)-tr(2)-tr(3)-tr(3)-tr(3) );

insert before

use trees::tr;

let mut forest = tr(1)-tr(3)-tr(4);
let mut iter = forest.subtrees().peekable();
while let Some(mut sub) = iter.next() { 
    if let Some(next_sub) = iter.peek() {
        if next_sub.data == 3 {
            sub.insert_sib( tr(2) );
        }
    }
}
assert_eq!( forest, tr(1)-tr(2)-tr(3)-tr(4) );

pub fn remove(self) -> Tree<T>

This subtree removes itself from its parent tree

Examples

use trees::{tr,fr};

let mut forest = tr(1)-tr(2)-tr(3)-tr(4)-tr(5)-tr(6);
for sub in forest.subtrees() { sub.remove(); }
assert_eq!( forest, fr() );

Methods from Deref<Target = Node<T>>

pub fn adopt(&mut self, children: Forest<T>)

Append the given trees at the end of the Node's children list.

pub fn abandon(&mut self) -> Forest<T>

Removes and returns the given tree Node's children.

Examples

use trees::tr;

let mut tree = tr(0) /tr(1)/tr(2);
let children = tree.abandon();
assert_eq!( tree, tr(0) );
assert_eq!( children, -tr(1)-tr(2) );

pub fn push_front(&mut self, child: Tree<T>)

Adds the child as the first child.

Examples

use trees::tr;

let mut tree = tr(0) /tr(1);
tree.push_front( tr(2) );
let mut iter = tree.children();
assert_eq!( iter.next().unwrap().to_owned(), tr(2) );
assert_eq!( iter.next().unwrap().to_owned(), tr(1) );
assert_eq!( iter.next(), None );

pub fn pop_front(&mut self) -> Option<Tree<T>>

remove and return the first child

Examples

use trees::tr;

let mut tree = tr(0) /tr(1)/tr(2);
let child = tree.pop_front();
assert_eq!( tree, tr(0) /tr(2) );
assert_eq!( child.unwrap(), tr(1) );

pub fn push_back(&mut self, child: Tree<T>)

add the child as the last child

Examples

use trees::tr;

let mut tree = tr(0) /tr(1);
tree.push_back( tr(2) );
let mut iter = tree.children();
assert_eq!( iter.next().unwrap().to_owned(), tr(1) );
assert_eq!( iter.next().unwrap().to_owned(), tr(2) );
assert_eq!( iter.next(), None );

Important traits for Iter<'a, T>

impl<'a, T: 'a> Iterator for Iter<'a, T> type Item = &'a Node<T>;

pub fn children(&self) -> Iter<T>

Provides a forward iterator over tree Node's direct decendants

Examples

use trees::tr;

let tree = tr(0)
    /( tr(1) /tr(2)/tr(3) )
    /( tr(4) /tr(5)/tr(6) )
;
let mut iter = tree.children();
assert_eq!( iter.next().unwrap().to_owned(), tr(1) /tr(2)/tr(3) );
assert_eq!( iter.next().unwrap().to_owned(), tr(4) /tr(5)/tr(6) );
assert_eq!( iter.next(), None );

Important traits for IterMut<'a, T>

impl<'a, T: 'a> Iterator for IterMut<'a, T> type Item = &'a mut Node<T>;

pub fn children_mut(&mut self) -> IterMut<T>

Provides a forward iterator over tree Node's direct decendants with mutable references.

Examples

use trees::tr;

let mut tree = tr(0)
    /( tr(1) /tr(2)/tr(3) )
    /( tr(4) /tr(5)/tr(6) )
;
for mut child in tree.children_mut() {
    child.data *= 10;
}
let expedted = tr(0)
    /( tr(10) /tr(2)/tr(3) )
    /( tr(40) /tr(5)/tr(6) )
;
assert_eq!( tree, expedted );

Important traits for SubtreeIter<T>

impl<T> Iterator for SubtreeIter<T> type Item = Subtree<T>;

pub fn subtrees(&mut self) -> SubtreeIter<T>

Provide an iterator over the tree Node's subtrees for insert/remove at any position

Examples

insert after

use trees::tr;

let mut tree = tr(0) /tr(1)/tr(2)/tr(3);
for mut sub in tree.subtrees() {
    sub.insert_sib( tr(3) );
}
assert_eq!( tree, tr(0) /tr(1)/tr(3)/tr(2)/tr(3)/tr(3)/tr(3) );

insert before

use trees::tr;

let mut tree = tr(0) /tr(1)/tr(3)/tr(4);
let mut iter = tree.subtrees().peekable();
while let Some(mut sub) = iter.next() { 
    if let Some(next_sub) = iter.peek() {
        if next_sub.data == 3 {
            sub.insert_sib( tr(2) );
        }
    }
}
assert_eq!( tree, tr(0) /tr(1)/tr(2)/tr(3)/tr(4) );

remove

use trees::tr;
let mut tree = tr(0) /tr(1)/tr(2)/tr(3)/tr(4)/tr(5)/tr(6);
for mut sub in tree.subtrees() {
    let d = sub.data;
    if d%2 == 0 || d%3 == 0 {
        sub.remove();
    }
}
assert_eq!( tree, tr(0) /tr(1)/tr(5) );

pub fn is_leaf(&self) -> bool

Returns true if the Node has no children.

This operation should compute in O(1) time.

Examples

use trees::{tr};

let mut tree = tr(0);
assert!( tree.is_leaf() );
tree.push_back( tr(1) ); 
assert!( !tree.is_leaf() );

Trait Implementations

impl<T> Deref for Subtree<T>

type Target = Node<T>

The resulting type after dereferencing.

fn deref(&self) -> &Node<T>

Dereferences the value.

impl<T> DerefMut for Subtree<T>

fn deref_mut(&mut self) -> &mut Node<T>

Mutably dereferences the value.