[−][src]Trait outils::tree::WeightedTree

pub trait WeightedTree<W, Ix = DefaultIndexType> where
    W: WeightType,
    Ix: IndexType, {
    fn set_weight(&mut self, node: NodeIndex<Ix>, weight: W) -> Option<W>;

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

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

    fn adjust_weight(
        &mut self, 
        node: NodeIndex<Ix>, 
        f: &dyn Fn(&mut W)
    ) -> Option<&W>;
}

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>

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.

Loading content...

Implementors

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

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]

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));
Loading content...