[−][src]Trait outils::tree::WeightedTree
Trees implementing this trait are able to maintain node weights and subweights. The subweight of a tree node is recursively defined as the sum of its own weight plus the subweights of its children. The subweight of a leaf node is equal to its weight.
Required methods
fn set_weight(&mut self, node: NodeIndex<Ix>, weight: W) -> Option<W>
Set the weight of the tree node indexed by node
to weight
and update the subweight
of this node as well as the subweights of the nodes on the path from this node to the tree
root. If node
was a valid index, the old weight is returned.
fn weight(&self, node: NodeIndex<Ix>) -> Option<&W>
Immutably access the weight of the tree node indexed by node
.
fn subweight(&self, node: NodeIndex<Ix>) -> Option<&W>
Immutably access the subweight of the tree node indexed by node
.
fn adjust_weight(
&mut self,
node: NodeIndex<Ix>,
f: &dyn Fn(&mut W)
) -> Option<&W>
&mut self,
node: NodeIndex<Ix>,
f: &dyn Fn(&mut W)
) -> Option<&W>
Change the weight of the tree node indexed by node
by applying the closure f
. After
applying the closure, the subweight of this node as well as the subweights of the nodes on
the path from this node to the tree root will be updated accordingly. If node
was a valid
index a reference to the changed weight is returned.
Implementors
impl<K, V, W> WeightedTree<W, usize> for WeightedAaTree<K, V, W> where
K: KeyType,
V: ValueType,
W: WeightType,
[src]
K: KeyType,
V: ValueType,
W: WeightType,
fn set_weight(&mut self, node: NodeIndex, weight: W) -> Option<W>
[src]
Set the weight of the tree node indexed by node
to weight
and update the subweight
of this node as well as the subweights of the nodes on the path from this node to the tree
root. If node
was a valid index, the old weight is returned.
use outils::prelude::*; let mut waatree = WeightedAaTree::new(10); waatree.insert_weighted(1, 1, 1); let n1 = waatree.index(1).expect("Key 1 should be present"); let w = waatree.set_weight(n1, 2).expect("Previous weight should not be None"); assert_eq!(w, 1); assert_eq!(waatree.weight(n1), Some(&2));
fn weight(&self, node: NodeIndex) -> Option<&W>
[src]
Immutably access the weight of the tree node indexed by node
.
fn subweight(&self, node: NodeIndex) -> Option<&W>
[src]
Immutably access the subweight of the tree node indexed by node
.
use outils::prelude::*; let mut waatree = WeightedAaTree::new(10); waatree.insert_weighted(1, 1, 1); waatree.insert_weighted(2, 2, 1); let n1 = waatree.index(1).expect("Key 1 should be present"); let n2 = waatree.index(2).expect("Key 2 should be present"); // 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!(waatree.subweight(n1), Some(&2));
fn adjust_weight(&mut self, node: NodeIndex, f: &dyn Fn(&mut W)) -> Option<&W>
[src]
Change the weight of the tree node indexed by node
by applying the closure f
. After
applying the closure, the subweight of this node as well as the subweights of the nodes on
the path from this node to the tree root will be updated accordingly. If node
was a valid
index a reference to the changed weight is returned.
use outils::prelude::*; let mut waatree = WeightedAaTree::new(10); waatree.insert_weighted(1, 1, 1); waatree.insert_weighted(2, 2, 1); let n1 = waatree.index(1).expect("Key 1 should be present"); let n2 = waatree.index(2).expect("Key 2 should be present"); // At this point, the AA algorithm has not had to rotate the tree, so that // n2 will be the right child of n1. Now the weight if n2 will be increased by 1. waatree.adjust_weight(n2, &|w: &mut usize| *w += 1); assert_eq!(waatree.weight(n2), Some(&2)); assert_eq!(waatree.subweight(n1), Some(&3));
impl<V, W> WeightedTree<W, usize> for WeightedAaForest<V, W> where
V: ValueType,
W: WeightType,
[src]
V: ValueType,
W: WeightType,
fn set_weight(&mut self, node: NodeIndex, weight: W) -> Option<W>
[src]
Set the weight of the tree node indexed by node
to weight
and update the subweight
of this node as well as the subweights of the nodes on the path from this node to the tree
root. If node
was a valid index, the old weight is returned.
use outils::prelude::*; let mut waaforest = WeightedAaForest::new(10); let n1 = waaforest.insert_weighted(1, 1); let w = waaforest.set_weight(n1, 2).expect("Previous weight should not be None"); assert_eq!(w, 1); assert_eq!(waaforest.weight(n1), Some(&2));
fn weight(&self, node: NodeIndex) -> Option<&W>
[src]
Immutably access the weight of the tree node indexed by node
.
fn subweight(&self, node: NodeIndex) -> Option<&W>
[src]
Immutably access the subweight of the tree node indexed by node
.
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.subweight(n1), Some(&2));
fn adjust_weight(&mut self, node: NodeIndex, f: &dyn Fn(&mut W)) -> Option<&W>
[src]
Change the weight of the tree node indexed by node
by applying the closure f
. After
applying the closure, the subweight of this node as well as the subweights of the nodes on
the path from this node to the tree root will be updated accordingly. If node
was a valid
index a reference to the changed weight is returned.
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. Now the weight if n2 will be increased by 1. waaforest.adjust_weight(n2, &|w: &mut usize| *w += 1); assert_eq!(waaforest.weight(n2), Some(&2)); assert_eq!(waaforest.subweight(n1), Some(&3));