Struct trees::Forest

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

Collection of circularly-linked Trees

Methods

impl<T> Forest<T>

pub fn new() -> Forest<T>

Makes an empty Forest

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

add the child as the first child

Examples

use trees::tr;

let mut forest = tr(1)-tr(2);
forest.push_front( tr(3) );
let mut iter = forest.children();
assert_eq!( iter.next().unwrap().to_owned(), tr(3) );
assert_eq!( iter.next().unwrap().to_owned(), tr(1) );
assert_eq!( iter.next().unwrap().to_owned(), tr(2) );
assert_eq!( iter.next(), None );

pub fn prepend(self, node: Tree<T>) -> Self

Add the child as the first child and return the Forest itself.

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

Removes and returns the tree at the front of the forest.

Examples

use trees::{tr,fr};

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

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

Appends the given tree at the end of this forest

Examples

use trees::tr;

let mut forest = tr(1)-tr(2);
forest.push_back( tr(3) );
let mut iter = forest.children();
assert_eq!( iter.next().unwrap().to_owned(), tr(1) );
assert_eq!( iter.next().unwrap().to_owned(), tr(2) );
assert_eq!( iter.next().unwrap().to_owned(), tr(3) );
assert_eq!( iter.next(), None );

pub fn append(self, child: Tree<T>) -> Self

Appends the given tree at the end of this forest and return the forest.

pub fn merge(self, other: Self) -> Self

Merges two forests into one, and return it

Examples

use trees::{tr,fr};

let mut forest = fr().append( tr(1) ).append( tr(2) );
let f2 = fr().append( tr(3) ).append( tr(4) );
forest = forest.merge( f2 );
assert_eq!( forest, tr(1)-tr(2)-tr(3)-tr(4) );

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 the Forest's direct decendants

Examples

use trees::tr;

let forest = tr(1)/tr(2)/tr(3) - tr(4)/tr(5)/tr(6);
let mut iter = forest.children();
//assert_eq!( iter.next().unwrap().clone(), tr(1) /tr(2)/tr(3) );
//assert_eq!( iter.next().unwrap().clone(), 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 the Forest's direct decendants with mutable references.

Examples

use trees::tr;

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

Important traits for SubtreeIter<T>

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

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

Provides an iterator over the Forest's subtrees for insert/remove at any position.

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) );

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_empty(&self) -> bool

Returns true if the Forest is empty.

This operation should compute in O(1) time.

Examples

use trees::{tr,fr};

let mut forest = fr();
assert!( forest.is_empty() );
forest.push_back( tr(1) ); 
assert!( !forest.is_empty() );

Trait Implementations

impl<T> IntoIterator for Forest<T>

type Item = Tree<T>

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

Important traits for IntoIter<T>

impl<T> Iterator for IntoIter<T> type Item = Tree<T>;

fn into_iter(self) -> IntoIter<T>

Consumes the Forest into an iterator yielding Trees.

impl<T> FromIterator<Tree<T>> for Forest<T>

fn from_iter<I: IntoIterator<Item = Tree<T>>>(iter: I) -> Self

Creates a value from an iterator.

impl<T> Extend<Tree<T>> for Forest<T>

fn extend<I: IntoIterator<Item = Tree<T>>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

impl<T: Clone> Clone for Forest<T>

fn clone(&self) -> Self

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: PartialEq> PartialEq for Forest<T>

fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Self) -> bool

This method tests for !=.

impl<T: Eq> Eq for Forest<T>

impl<T: PartialOrd> PartialOrd for Forest<T>

fn partial_cmp(&self, other: &Self) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T: Ord> Ord for Forest<T>

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

impl<T> Default for Forest<T>

fn default() -> Self

Returns the "default value" for a type.

impl<T> Drop for Forest<T>

fn drop(&mut self)

Executes the destructor for this type.

impl<T: Hash> Hash for Forest<T>

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given [Hasher].

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given [Hasher].

impl<T: Debug> Debug for Forest<T>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<T: Display> Display for Forest<T>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<T: Send> Send for Forest<T>

impl<T: Sync> Sync for Forest<T>

impl<T> Div<Forest<T>> for Tree<T>

type Output = Tree<T>

The resulting type after applying the / operator.

fn div(self, rhs: Forest<T>) -> Tree<T>

Performs the / operation.

impl<'a, T: Clone> Div<&'a Forest<T>> for Tree<T>

type Output = Tree<T>

The resulting type after applying the / operator.

fn div(self, rhs: &'a Forest<T>) -> Tree<T>

Performs the / operation.

impl<'a, T: Clone> Div<Forest<T>> for &'a Tree<T>

type Output = Tree<T>

The resulting type after applying the / operator.

fn div(self, rhs: Forest<T>) -> Tree<T>

Performs the / operation.

impl<'a, T: Clone> Div<&'a Forest<T>> for &'a Tree<T>

type Output = Tree<T>

The resulting type after applying the / operator.

fn div(self, rhs: &'a Forest<T>) -> Tree<T>

Performs the / operation.

impl<T> Sub<Tree<T>> for Forest<T>

type Output = Forest<T>

The resulting type after applying the - operator.

fn sub(self, rhs: Tree<T>) -> Self

Performs the - operation.

impl<'a, T: Clone> Sub<&'a Tree<T>> for Forest<T>

type Output = Forest<T>

The resulting type after applying the - operator.

fn sub(self, rhs: &'a Tree<T>) -> Self

Performs the - operation.

impl<'a, T: Clone> Sub<Tree<T>> for &'a Forest<T>

type Output = Forest<T>

The resulting type after applying the - operator.

fn sub(self, rhs: Tree<T>) -> Forest<T>

Performs the - operation.

impl<'a, 'b, T: Clone> Sub<&'b Tree<T>> for &'a Forest<T>

type Output = Forest<T>

The resulting type after applying the - operator.

fn sub(self, rhs: &'b Tree<T>) -> Forest<T>

Performs the - operation.

impl<T> Sub<Forest<T>> for Forest<T>

type Output = Forest<T>

The resulting type after applying the - operator.

fn sub(self, rhs: Self) -> Self

Performs the - operation.

impl<'a, T: Clone> Sub<&'a Forest<T>> for Forest<T>

type Output = Forest<T>

The resulting type after applying the - operator.

fn sub(self, rhs: &'a Forest<T>) -> Self

Performs the - operation.

impl<'a, T: Clone> Sub<Forest<T>> for &'a Forest<T>

type Output = Forest<T>

The resulting type after applying the - operator.

fn sub(self, rhs: Forest<T>) -> Forest<T>

Performs the - operation.

impl<'a, 'b, T: Clone> Sub<&'b Forest<T>> for &'a Forest<T>

type Output = Forest<T>

The resulting type after applying the - operator.

fn sub(self, rhs: &'b Forest<T>) -> Forest<T>

Performs the - operation.