Struct trees::Tree

pub struct Tree<T>(_);

Tree with owned Nodes.

Methods

impl<T> Tree<T>

pub fn new(data: T) -> Tree<T>

Creates a Tree with given data on heap. Tree is NOT nullable. Consider using an empty Forest instead if needed.

Examples

use trees::Tree;

let tree = Tree::new( 1 );
assert_eq!( tree.data, 1 );

pub fn adopt(self, children: Forest<T>) -> Self

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

Examples

use trees::tr;

let mut tree = tr(0);
tree = tree.adopt( -tr(1)-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 );

pub fn prepend(self, child: Self) -> Self

Prepend the given tree at the begin of the Tree's children list.

Examples

use trees::{tr,fr};

let mut tree = tr(0);
tree = tree.prepend( tr(1) );
tree = tree.prepend( 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 append(self, child: Self) -> Self

Prepend the given tree at the begin of the Tree's children list.

Examples

use trees::{tr,fr};

let mut tree = tr(0);
tree = tree.append( tr(1) );
tree = tree.append( 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 );

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: PartialEq> PartialEq for Tree<T>

fn eq(&self, __arg_0: &Tree<T>) -> bool

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

fn ne(&self, __arg_0: &Tree<T>) -> bool

This method tests for !=.

impl<T: Eq> Eq for Tree<T>

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 Node<T>

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

Extends a collection with the contents of 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> Borrow<Node<T>> for Tree<T>

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

Immutably borrows from an owned value.

impl<T> BorrowMut<Node<T>> for Tree<T>

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

Mutably borrows from an owned value.

impl<T: Clone> Clone for Tree<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> Deref for Tree<T>

type Target = Node<T>

The resulting type after dereferencing.

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

Dereferences the value.

impl<T> DerefMut for Tree<T>

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

Mutably dereferences the value.

impl<T: Debug> Debug for Tree<T>

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

Formats the value using the given formatter.

impl<T> Neg for Tree<T>

type Output = Forest<T>

The resulting type after applying the - operator.

fn neg(self) -> Forest<T>

Performs the unary - operation.

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

type Output = Forest<T>

The resulting type after applying the - operator.

fn neg(self) -> Forest<T>

Performs the unary - operation.

impl<T> Sub<Self> for Tree<T>

type Output = Forest<T>

The resulting type after applying the - operator.

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

Performs the - operation.

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

type Output = Forest<T>

The resulting type after applying the - operator.

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

Performs the - operation.

impl<'a, T: Clone> Sub<Tree<T>> for &'a Tree<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, T: Clone> Sub<Self> for &'a Tree<T>

type Output = Forest<T>

The resulting type after applying the - operator.

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

Performs the - operation.

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> Div<Tree<T>> for Tree<T>

type Output = Tree<T>

The resulting type after applying the / operator.

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

Performs the / operation.

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

type Output = Tree<T>

The resulting type after applying the / operator.

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

Performs the / operation.

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

type Output = Tree<T>

The resulting type after applying the / operator.

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

Performs the / operation.

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

type Output = Tree<T>

The resulting type after applying the / operator.

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

Performs the / operation.

impl<T> Div<()> for Tree<T>

type Output = Tree<T>

The resulting type after applying the / operator.

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

Performs the / operation.

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

type Output = Tree<T>

The resulting type after applying the / operator.

fn div(self, _rhs: ()) -> 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.