[−][src]Trait outils::tree::traversal::Traversable
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
.
Implementors
impl<K, V> Traversable<V, usize> for AaTree<K, V> where
K: KeyType,
V: ValueType,
[src]
K: KeyType,
V: ValueType,
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]
K: KeyType,
V: ValueType,
W: WeightType,
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]
V: ValueType,
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]
V: ValueType,
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]
V: ValueType,
W: WeightType,
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
.