Struct outils::tree::bst::waatree::WeightedAaTree

pub struct WeightedAaTree<K, V, W = DefaultWeightType> where
    K: KeyType,
    V: ValueType,
    W: WeightType,  { /* fields omitted */ }

WeightedAaTree<K, V, W> is a weighted balanced binary search tree data structure. Its tree nodes are held in a memory arena and are addressed through their associated NodeIndex.

The balancing method for maintaining a tree height of log(n) where n is the number nodes in the tree is described here: AA tree.

WeightedAaTree is parameterized over:

• Search keys of type K, where K must implement the trait KeyType
• Associated values of type V, where V must implement the trait ValueType
• Associated node weights and subweights of type W, where W must implement the trait WeightType.

The usage of WeightedAaTree resembles that of BTreeMap from the standard library:

use std::collections::BTreeMap;
use outils::prelude::*;

let mut btreemap = BTreeMap::new();
let mut waatree = WeightedAaTree::new(10);

btreemap.insert("DE", "Germany");
btreemap.insert("FR", "France");
btreemap.insert("IT", "Italy");

waatree.insert_weighted("DE", "Germany", 1);
waatree.insert_weighted("FR", "France", 1);
waatree.insert_weighted("IT", "Italy", 1);

assert_eq!(btreemap.get(&"DE"), Some(&"Germany"));
assert_eq!(waatree.get(&"DE"), Some(&"Germany"));

assert_eq!(btreemap.remove(&"FR"), Some("France"));
assert_eq!(waatree.remove(&"FR"), Some("France"));

assert_eq!(btreemap.get(&"FR"), None);
assert_eq!(waatree.get(&"FR"), None);

For most use cases, it is recommended to simply use BTreeMap, as it is considerably faster (appr. 50%). However, if information on parent and child relations between tree nodes, or custom traversal of the tree as such, are needed, WeightedAaTree has an advantage over BTreeMap.

Also, the capability of managing node weights and subweights offers additional possibilities to reason about trees. For example, simply storing a node weight of 1 with each item in the tree will result in the size of the subtree of a node being stored in its subweight:

use outils::prelude::*;                     // The resulting tree is shown below:
let mut waatree = WeightedAaTree::new(10);  //       -- (3) --
                                            //      /         \
for i in 0..7 {                             //    (1)         (5)
    waatree.insert_weighted(i, i, 1);       //   /   \       /   \
}                                           // (0)   (2)    (4)   (6)

let n1 = waatree.index(1).expect("Key '1' should be present");
let n3 = waatree.index(3).expect("Key '3' should be present");
let n4 = waatree.index(4).expect("Key '4' should be present");

assert_eq!(waatree.subweight(n1), Some(&3)); // The subtree rooted in 1 consists of 3 nodes.
assert_eq!(waatree.subweight(n3), Some(&7)); // The subtree rooted in 3 consists of 7 nodes.
assert_eq!(waatree.subweight(n4), Some(&1)); // The subtree rooted in 4 consists of 1 node.

Implementations

impl<K, V, W> WeightedAaTree<K, V, W> where
    K: KeyType,
    V: ValueType,
    W: WeightType, 

pub fn new(size: usize) -> Self

Construct a new empty WeightedAaTree with an initial capacity of size.

pub fn insert_weighted(&mut self, key: K, value: V, weight: W) -> Option<V>

Inserts a key-value pair into the WeightedAaTree and assign the node the weight weight. If the tree did not have this key present, None is returned. If the tree did have this key present, the value and the weight are updated, and the old value is returned. Note that in this situation, the key is left unchanged.

use outils::prelude::*;

let mut waatree = WeightedAaTree::new(10);

assert_eq!(waatree.insert_weighted("KEY-1", "VALUE-1", 1), None);
assert_eq!(waatree.insert_weighted("KEY-2", "VALUE-2", 1), None);
assert_eq!(waatree.insert_weighted("KEY-1", "VALUE-3", 3), Some("VALUE-1"));
assert_eq!(waatree.get(&"KEY-1"), Some(&"VALUE-3"));
assert_eq!(waatree.get(&"KEY-2"), Some(&"VALUE-2"));

let n1 = waatree.index(&"KEY-1").expect("KEY-1 should be present!");
assert_eq!(waatree.weight(n1), Some(&3)); // Weight of KEY-1 changed from 1 to 3.

Trait Implementations

impl<K, V, W> BinarySearchTree<K, V, usize> for WeightedAaTree<K, V, W> where
    K: KeyType,
    V: ValueType,
    W: WeightType, 

fn insert_pos(&self, key: K) -> Option<(NodeIndex, Ordering)>

Returns the insertion point for a given key. None is returned, if the tree is empty, otherwise an index to a node is returned together with the result of the comparison against its key.

fn insert(&mut self, key: K, value: V) -> Option<V>

Inserts a key-value pair into the WeightedAaTree and assign the node the weight W::default(). If the tree did not have this key present, None is returned. If the tree did have this key present, the value and the weight are updated, and the old value is returned. Note that in this situation, the key is left unchanged.

use outils::prelude::*;

let mut waatree = WeightedAaTree::new(10);

assert_eq!(waatree.insert_weighted("KEY-1", "VALUE-1", 1), None);
assert_eq!(waatree.insert_weighted("KEY-2", "VALUE-2", 1), None);
assert_eq!(waatree.insert_weighted("KEY-1", "VALUE-3", 1), Some("VALUE-1"));
assert_eq!(waatree.get(&"KEY-1"), Some(&"VALUE-3"));
assert_eq!(waatree.get(&"KEY-2"), Some(&"VALUE-2"));

fn remove(&mut self, key: K) -> Option<V>

Removes a key from the tree if present, in this case returning the associated value.

use outils::prelude::*;

let mut waatree = WeightedAaTree::new(10);
waatree.insert_weighted("KEY-1", "VALUE-1", 1);
assert_eq!(waatree.remove(&"KEY-1"), Some("VALUE-1"));
assert_eq!(waatree.remove(&"KEY-2"), None);

fn contains_key(&self, key: K) -> bool

Returns true if the map contains a value for the specified key.

fn get(&self, key: K) -> Option<&V>

Returns an immutable reference to the associated value of the specified key.

fn get_mut(&mut self, key: K) -> Option<&mut V>

Returns a mutable reference to the associated value of the specified key.

fn index(&self, key: K) -> Option<NodeIndex>

Returns the index of the tree node holding the specified key.

fn key(&self, node: NodeIndex) -> Option<&K>

Returns the key held by the tree node indexed by node.

use outils::prelude::*;

let mut waatree = WeightedAaTree::new(10);
waatree.insert_weighted("KEY-1", "VALUE-1", 1);
let index = waatree.index(&"KEY-1").expect("KEY-1 should be present");
assert_eq!(waatree.key(index), Some(&"KEY-1"));

impl<K: Clone, V: Clone, W: Clone> Clone for WeightedAaTree<K, V, W> where
    K: KeyType,
    V: ValueType,
    W: WeightType, 

fn clone(&self) -> WeightedAaTree<K, V, W>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug, V: Debug, W: Debug> Debug for WeightedAaTree<K, V, W> where
    K: KeyType,
    V: ValueType,
    W: WeightType, 

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

Formats the value using the given formatter.

impl<K, V, W> Index<NodeIndex<usize>> for WeightedAaTree<K, V, W> where
    K: KeyType,
    V: ValueType,
    W: WeightType, 

type Output = V

The returned type after indexing.

fn index(&self, index: NodeIndex) -> &V

Performs the indexing (container[index]) operation.

impl<K, V, W> IndexMut<NodeIndex<usize>> for WeightedAaTree<K, V, W> where
    K: KeyType,
    V: ValueType,
    W: WeightType, 

fn index_mut(&mut self, index: NodeIndex) -> &mut V

Performs the mutable indexing (container[index]) operation.

impl<'slf, K, V, W> Keys<'slf, K, usize> for WeightedAaTree<K, V, W> where
    K: 'slf + KeyType,
    V: ValueType,
    W: WeightType, 

fn keys(&'slf self) -> Box<dyn Iterator<Item = (NodeIndex, &'slf K)> + 'slf>

Returns a boxed iterator over the search keys and their corresponding tree node indices held by self. The keys are returned in the order of the search keys.

impl<K, V, W> OrderedTree<usize> for WeightedAaTree<K, V, W> where
    K: KeyType,
    V: ValueType,
    W: WeightType, 

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

Returns the biggest node of the left subtree of the tree node indexed by node.

use outils::prelude::*;                     // The resulting tree is shown below:
                                            //
let mut waatree = WeightedAaTree::new(10);  //       -- (3) --
                                            //      /         \
for i in 0..7 {                             //    (1)         (5)
    waatree.insert_weighted(i, i, 1);       //   /   \       /   \
}                                           // (0)   (2)    (4)   (6)

let n2 = waatree.index(2).expect("Key '2' should be present");
let n3 = waatree.index(3).expect("Key '3' should be present");
let n4 = waatree.index(4).expect("Key '4' should be present");

assert_eq!(waatree.sub_predecessor(n3), Some(n2)); // 2 is biggest key in left subtree of 3.
assert_eq!(waatree.sub_predecessor(n4), None);     // 4 is a leaf and thus has no subtrees.'

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

Returns the smallest node of the right subtree of the tree node indexed by node.

Usage is analogous to sub_predecessor

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

Returns the biggest node of the whole tree which is smaller than the tree node indexed by node.

use outils::prelude::*;                     // The resulting tree is shown below:
                                            //
let mut waatree = WeightedAaTree::new(10);  //       -- (3) --
                                            //      /         \
for i in 0..7 {                             //    (1)         (5)
    waatree.insert_weighted(i, i, 1);       //   /   \       /   \
}                                           // (0)   (2)    (4)   (6)

let n0 = waatree.index(0).expect("Key '0' should be present");
let n3 = waatree.index(3).expect("Key '3' should be present");
let n4 = waatree.index(4).expect("Key '4' should be present");

assert_eq!(waatree.predecessor(n4), Some(n3)); // 3 is the biggest key of the whole tree
                                              // smaller than 4.
assert_eq!(waatree.predecessor(n0), None);     // 0 is globally the smallest key of the
                                              // whole tree and thus has no predecessor.

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

Returns the smallest node of the whole tree which is bigger than the tree node indexed by node.

Usage is analogous to predecessor

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

Returns the smallest node of the left subtree of the tree node indexed by node.

use outils::prelude::*;                     // The resulting tree is shown below:
                                            //
let mut waatree = WeightedAaTree::new(10);  //       -- (3) --
                                            //      /         \
for i in 0..7 {                             //    (1)         (5)
    waatree.insert_weighted(i, i, 1);       //   /   \       /   \
}                                           // (0)   (2)    (4)   (6)

let n0 = waatree.index(0).expect("Key '0' should be present");
let n1 = waatree.index(1).expect("Key '1' should be present");
let n3 = waatree.index(3).expect("Key '3' should be present");

assert_eq!(waatree.first(n3), Some(n0));  // 0 is the smallest key of the left subtree of 3
assert_eq!(waatree.first(n1), Some(n0));  // 0 is the smallest key of the left subtree of 1

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

Returns the biggest node of the right subtree of the tree node indexed by node.

Usage is analogous to first

fn is_smaller(&self, node_u: NodeIndex, node_v: NodeIndex) -> bool

Returns true if the tree node indexed by node_u is smaller than the tree node indexed by node_v. Otherwise, and in particular if one of the specified indices is invalid, false is returned.

Panics if the path to the root from either of the tree nodes to be compared contains more than 64 nodes. This is because the directions (i.e. left or right) on the path are encoded in a bitmap of type u64. In practice it is next to impossible for this method to panic because the number of tree nodes needs to be close to 2^64 for the above condition to occur.

use outils::prelude::*;                     // The resulting tree is shown below:
                                            //
let mut waatree = WeightedAaTree::new(10);  //       -- (3) --
                                            //      /         \
for i in 0..7 {                             //    (1)         (5)
    waatree.insert_weighted(i, i, 1);       //   /   \       /   \
}                                           // (0)   (2)    (4)   (6)

let n0 = waatree.index(0).expect("Key '0' should be present");
let n1 = waatree.index(1).expect("Key '1' should be present");
let n3 = waatree.index(3).expect("Key '3' should be present");

assert!(waatree.is_smaller(n0, n3));
assert!(!waatree.is_smaller(n3, n1));

impl<K, V, W> Tgf for WeightedAaTree<K, V, W> where
    K: KeyType,
    V: ValueType,
    W: WeightType, 

fn to_tgf(&self) -> String

Returns a TGF representation of Self.

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

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

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>

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

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

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

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

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

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

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

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

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

impl<'slf, K, V, W> Values<'slf, V, usize> for WeightedAaTree<K, V, W> where
    K: KeyType,
    V: 'slf + ValueType,
    W: WeightType, 

fn values(&'slf self) -> Box<dyn Iterator<Item = (NodeIndex, &'slf V)> + 'slf>

Returns a boxed iterator over the stored values and their corresponding tree node indices held by self. The values are returned in the order of the corresponding search keys.

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

fn set_weight(&mut self, node: NodeIndex, 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.

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>

Immutably access the weight of the tree node indexed by node.

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

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>

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));