[−][src]Trait outils::tree::traversal::Traversable

pub trait Traversable<V, Ix = DefaultIndexType> where
    V: ValueType,
    Ix: IndexType, {
    fn root(&self, node: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>;

    fn value(&self, node: NodeIndex<Ix>) -> Option<&V>;

    fn value_mut(&mut self, node: NodeIndex<Ix>) -> Option<&mut V>;

    fn parent(&self, node: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>;

    fn child(&self, node: NodeIndex<Ix>, pos: usize) -> Option<NodeIndex<Ix>>;

    fn child_count(&self, node: NodeIndex<Ix>) -> usize;

    fn node_count(&self) -> usize;
}

This trait defines the interface for using the traversal iterators provided by this module.

Required methods

fn root(&self, node: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>

Returns the index of the root node of the tree containing the tree node indexed by node.

fn value(&self, node: NodeIndex<Ix>) -> Option<&V>

Immutably access the value stored in the tree node indexed by node.

fn value_mut(&mut self, node: NodeIndex<Ix>) -> Option<&mut V>

Mutably access the value stored in the tree node indexed by node.

fn parent(&self, node: NodeIndex<Ix>) -> Option<NodeIndex<Ix>>

Returns the index of parent node tree node indexed by node.

fn child(&self, node: NodeIndex<Ix>, pos: usize) -> Option<NodeIndex<Ix>>

Returns the index of the child node at position pos of the tree node indexed by node.

fn child_count(&self, node: NodeIndex<Ix>) -> usize

Returns the number of child nodes of the tree node indexed by node.

fn node_count(&self) -> usize

Returns the total number of tree nodes of the tree self.

Loading content...

Implementors

impl<K, V> Traversable<V, usize> for AaTree<K, V> where
    K: KeyType,
    V: ValueType, [src]

fn root(&self, _node: NodeIndex) -> Option<NodeIndex>[src]

Returns the index of the root node of the AaTree. Since the tree can only have one root the parameter node is not used.

use outils::prelude::*;

let mut aatree = AaTree::new(10);
assert_eq!(aatree.root(NodeIndex(0)), None); // The parameter to root() doesn't matter!
aatree.insert("KEY-1", "VALUE-1");

// The solitary key in the tree must be the root
let index = aatree.index(&"KEY-1").expect("KEY-1 should be present");

assert_eq!(aatree.root(index), Some(index));
assert_eq!(aatree.root(NodeIndex(0)), Some(index)); // The parameter to root() doesn't matter!

fn value(&self, node: NodeIndex) -> Option<&V>[src]

Immutably access the value stored in the AaTree indexed by node.

fn value_mut(&mut self, node: NodeIndex) -> Option<&mut V>[src]

Mutably access the value stored in the AaTree indexed by node.

fn parent(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the index of parent node tree node indexed by node.

fn child(&self, node: NodeIndex, pos: usize) -> Option<NodeIndex>[src]

Returns the index of the child node at position pos of the tree node indexed by node.

Note that a binary search tree node will always have two children, i.e. that even if the left child (pos == 0) is empty, the right child (pos == 1) might contain a value. In case of a leaf node, both children will be empty:

use outils::prelude::*;

let mut aatree = AaTree::new(10);
aatree.insert(1, "1");
aatree.insert(2, "2");

// At this point, the AA algorithm has not had to rotate the tree, so that
// the key `2` will be the right child of the key `1`:

let parent = aatree.index(1).expect("Key '1' should be present");
assert_eq!(aatree.child(parent, 0), None);
assert_eq!(aatree.child(parent, 1), aatree.index(2));

fn child_count(&self, node: NodeIndex) -> usize[src]

Returns the number of child nodes of the tree node indexed by node.

Note that a binary search tree node will always have two children, i.e. that even if the left child is empty, the right child might contain a value. In case of a leaf node, both children will be empty, but the number of (empty) children will still be 2:

use outils::prelude::*;

let mut aatree = AaTree::new(10);
aatree.insert(1, "1");
aatree.insert(2, "2");

// At this point, the AA algorithm has not had to rotate the tree, so that
// the key `2` will be the right child of the key `1`:

let parent = aatree.index(1).expect("Key '1' should be present");
let child = aatree.index(2).expect("Key '2' should be present");

assert_eq!(aatree.child_count(parent), 2);
assert_eq!(aatree.child_count(child), 2);
assert_eq!(aatree.child_count(NodeIndex(999)), 0); // Invalid index => no children

fn node_count(&self) -> usize[src]

Returns the total number of tree nodes of the tree self.

impl<K, V, W> Traversable<V, usize> for WeightedAaTree<K, V, W> where
    K: KeyType,
    V: ValueType,
    W: WeightType, [src]

fn root(&self, _node: NodeIndex) -> Option<NodeIndex>[src]

Returns the index of the root node of the WeightedAaTree. Since the tree can only have one root the parameter node is not used.

use outils::prelude::*;

let mut waatree = WeightedAaTree::new(10);
assert_eq!(waatree.root(NodeIndex(0)), None); // The parameter to root() doesn't matter!
waatree.insert_weighted("KEY-1", "VALUE-1", 1);

// The solitary key in the tree must be the root
let index = waatree.index(&"KEY-1").expect("KEY-1 should be present");

assert_eq!(waatree.root(index), Some(index));
assert_eq!(waatree.root(NodeIndex(0)), Some(index)); // The parameter to root() doesn't matter!

fn value(&self, node: NodeIndex) -> Option<&V>[src]

Immutably access the value stored in the WeightedAaTree indexed by node.

fn value_mut(&mut self, node: NodeIndex) -> Option<&mut V>[src]

Mutably access the value stored in the WeightedAaTree indexed by node.

fn parent(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the index of parent node tree node indexed by node.

fn child(&self, node: NodeIndex, pos: usize) -> Option<NodeIndex>[src]

Returns the index of the child node at position pos of the tree node indexed by node.

Note that a binary search tree node will always have two children, i.e. that even if the left child (pos == 0) is empty, the right child (pos == 1) might contain a value. In case of a leaf node, both children will be empty:

use outils::prelude::*;

let mut waatree = WeightedAaTree::new(10);
waatree.insert_weighted(1, "1", 1);
waatree.insert_weighted(2, "2", 1);

// At this point, the AA algorithm has not had to rotate the tree, so that
// the key `2` will be the right child of the key `1`:

let parent = waatree.index(1).expect("Key '1' should be present");
assert_eq!(waatree.child(parent, 0), None);
assert_eq!(waatree.child(parent, 1), waatree.index(2));

fn child_count(&self, node: NodeIndex) -> usize[src]

Returns the number of child nodes of the tree node indexed by node.

Note that a binary search tree node will always have two children, i.e. that even if the left child is empty, the right child might contain a value. In case of a leaf node, both children will be empty, but the number of (empty) children will still be 2:

use outils::prelude::*;

let mut waatree = WeightedAaTree::new(10);
waatree.insert_weighted(1, "1" ,1);
waatree.insert_weighted(2, "2", 1);

// At this point, the AA algorithm has not had to rotate the tree, so that
// the key `2` will be the right child of the key `1`:

let parent = waatree.index(1).expect("Key '1' should be present");
let child = waatree.index(2).expect("Key '2' should be present");

assert_eq!(waatree.child_count(parent), 2);
assert_eq!(waatree.child_count(child), 2);
assert_eq!(waatree.child_count(NodeIndex(999)), 0); // Invalid index => no children

fn node_count(&self) -> usize[src]

Returns the total number of tree nodes of the tree self.

impl<V> Traversable<V, usize> for AaForest<V> where
    V: ValueType, [src]

fn root(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the index of the root node of the tree containing the tree node indexed by node. In case of an invalid index, None is returned.

fn value(&self, node: NodeIndex) -> Option<&V>[src]

Immutably access the value stored in the tree node indexed by node.

fn value_mut(&mut self, node: NodeIndex) -> Option<&mut V>[src]

Mutably access the value stored in the tree node indexed by node.

fn parent(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the index of parent node tree node indexed by node.

fn child(&self, node: NodeIndex, pos: usize) -> Option<NodeIndex>[src]

Returns the index of the child node at position pos of the tree node indexed by node.

Note that a binary tree node will always have two children, i.e. that even if the left child (pos == 0) is empty, the right child (pos == 1) might contain a value. In case of a leaf node, both children will be empty:

use outils::prelude::*;

let mut aaforest = AaForest::new(10);
let n1 = aaforest.insert(1);
let n2 = aaforest.insert(2);
aaforest.append(n1, n2);

// At this point, the AA algorithm has not had to rotate the tree, so that
// `n2` will be the right child of `n1`:

assert_eq!(aaforest.child(n1, 0), None);
assert_eq!(aaforest.child(n1, 1), Some(n2));

fn child_count(&self, node: NodeIndex) -> usize[src]

Returns the number of child nodes of the tree node indexed by node.

Note that a binary tree node will always have two children, i.e. that even if the left child is empty, the right child might contain a value. In case of a leaf node, both children will be empty, but the number of (empty) children will still be 2:

use outils::prelude::*;

let mut aaforest = AaForest::new(10);
let n1 = aaforest.insert(1);
let n2 = aaforest.insert(2);
aaforest.append(n1, n2);

// At this point, the AA algorithm has not had to rotate the tree, so that
// `n2` will be the right child of `n1`:

assert_eq!(aaforest.child_count(n1), 2);
assert_eq!(aaforest.child_count(n2), 2);
assert_eq!(aaforest.child_count(NodeIndex(999)), 0); // Invalid index => no children

fn node_count(&self) -> usize[src]

Returns the total number of tree nodes of the forest trees in self.

impl<V> Traversable<V, usize> for Forest<V> where
    V: ValueType, [src]

fn root(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the index of the root node of the tree containing the tree node indexed by node.

fn value(&self, node: NodeIndex) -> Option<&V>[src]

Immutably access the value stored in the tree node indexed by node.

fn value_mut(&mut self, node: NodeIndex) -> Option<&mut V>[src]

Mutably access the value stored in the tree node indexed by node.

fn parent(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the index of parent node tree node indexed by node.

fn child(&self, node: NodeIndex, pos: usize) -> Option<NodeIndex>[src]

Returns the index of the child node at position pos of the tree node indexed by node.

fn child_count(&self, node: NodeIndex) -> usize[src]

Returns the number of child nodes of the tree node indexed by node.

fn node_count(&self) -> usize[src]

Returns the total number of tree nodes of the tree self.

impl<V, W> Traversable<V, usize> for WeightedAaForest<V, W> where
    V: ValueType,
    W: WeightType, [src]

fn root(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the index of the root node of the tree containing the tree node indexed by node. In case of an invalid index, None is returned.

fn value(&self, node: NodeIndex) -> Option<&V>[src]

Immutably access the value stored in the tree node indexed by node.

fn value_mut(&mut self, node: NodeIndex) -> Option<&mut V>[src]

Mutably access the value stored in the tree node indexed by node.

fn parent(&self, node: NodeIndex) -> Option<NodeIndex>[src]

Returns the index of parent node tree node indexed by node.

fn child(&self, node: NodeIndex, pos: usize) -> Option<NodeIndex>[src]

Returns the index of the child node at position pos of the tree node indexed by node.

Note that a binary tree node will always have two children, i.e. that even if the left child (pos == 0) is empty, the right child (pos == 1) might contain a value. In case of a leaf node, both children will be empty:

use outils::prelude::*;

let mut waaforest = WeightedAaForest::new(10);
let n1 = waaforest.insert_weighted(1, 1);
let n2 = waaforest.insert_weighted(2, 1);
waaforest.append(n1, n2);

// At this point, the AA algorithm has not had to rotate the tree, so that
// n2 will be the right child of n1:

assert_eq!(waaforest.child(n1, 0), None);
assert_eq!(waaforest.child(n1, 1), Some(n2));

fn child_count(&self, node: NodeIndex) -> usize[src]

Returns the number of child nodes of the tree node indexed by node.

Note that a binary tree node will always have two children, i.e. that even if the left child is empty, the right child might contain a value. In case of a leaf node, both children will be empty, but the number of (empty) children will still be 2:

use outils::prelude::*;

let mut waaforest = WeightedAaForest::new(10);
let n1 = waaforest.insert_weighted(1, 1);
let n2 = waaforest.insert_weighted(2, 1);
waaforest.append(n1, n2);

// At this point, the AA algorithm has not had to rotate the tree, so that
// n2 will be the right child of n1:

assert_eq!(waaforest.child_count(n1), 2);
assert_eq!(waaforest.child_count(n2), 2);
assert_eq!(waaforest.child_count(NodeIndex(999)), 0); // Invalid index => no children

fn node_count(&self) -> usize[src]

Returns the total number of tree nodes of the forest trees in self.

Loading content...