[−][src]Struct outils::tree::bst::waaforest::WeightedAaForest
WeightedAaForest<V, W>
is a data structure for holding balanced binary trees. Its tree nodes
are held in a memory arena and are addressed through their associated NodeIndex
.
AaForest
is parameterized over:
- Associated values of type
V
, whereV
must implement the traitValueType
- Associated node weights and subweights of type
W
, whereW
must implement the traitWeightType
.
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.
Forest trees can be joined and split as required by the provided operations, which will
also take care of the re-balancing of the trees. The in-order of the forest trees implies an
ordered sequence of values - this order does not depend on the order traits of the type V
(i.e. std::cmp::Ord
) but solely on the in-order of the nodes which is under the control
of the user (see the documentation of split
and append
).
use outils::prelude::*; use outils::tree::traversal::BinaryInOrderValues; let mut waaforest = WeightedAaForest::new(10); // Insert values into the forest - each value will be a single-node tree in the forest. let n1 = waaforest.insert_weighted(1, 1); let n2 = waaforest.insert_weighted(2, 1); let n3 = waaforest.insert_weighted(3, 1); // Link the single-node trees, constructing the in-order sequence 1,2,3. waaforest.append(n1, n2); waaforest.append(n2, n3); let seq: Vec<&usize> = BinaryInOrderValues::new(&waaforest, n1).collect(); assert_eq!(seq, vec![&1, &2, &3]); // Because the tree constructed above contains three nodes with weight 1, the root of the // tree is expected to have a subweight of 3: let root = waaforest.root(n1).expect("The root of the tree should exist!"); assert_eq!(waaforest.subweight(root), Some(&3));
Implementations
impl<V, W> WeightedAaForest<V, W> where
V: ValueType,
W: WeightType,
[src]
V: ValueType,
W: WeightType,
pub fn new(size: usize) -> Self
[src]
Construct a new empty WeigthedAaForest
with an initial capacity of size
.
pub fn insert_weighted(&mut self, value: V, weight: W) -> NodeIndex
[src]
Insert a new singleton node containing value
into the forest and set its weight to weight
.
Trait Implementations
impl<V, W> BalancedBinaryForest<V, usize> for WeightedAaForest<V, W> where
V: ValueType,
W: WeightType,
[src]
V: ValueType,
W: WeightType,
fn insert(&mut self, value: V) -> NodeIndex
[src]
fn remove(&mut self, node: NodeIndex) -> Option<V>
[src]
Removes the tree node indexed by node
from the tree if present, in this case returning
the associated value.
use outils::prelude::*; // The resulting tree is shown below: use outils::tree::traversal::BinaryInOrderValues; // // -- (3) -- let mut waaforest = WeightedAaForest::new(10); // / \ // (1) (5) let mut indices = Vec::new(); // / \ / \ indices.push(waaforest.insert_weighted(0, 1)); // (0) (2) (4) (6) for i in 1..7 { indices.push(waaforest.insert_weighted(i, 1)); waaforest.append(indices[i-1], indices[i]); } assert_eq!(waaforest.remove(indices[5]), Some(5)); let seq: Vec<&usize> = BinaryInOrderValues::new(&waaforest, indices[0]).collect(); assert_eq!(seq, vec![&0, &1, &2, &3, &4, &6]);
fn split(
&mut self,
node: NodeIndex,
dir: BstDirection
) -> (Option<NodeIndex>, Option<NodeIndex>)
[src]
&mut self,
node: NodeIndex,
dir: BstDirection
) -> (Option<NodeIndex>, Option<NodeIndex>)
Splits the sequence of tree nodes represented by the forest tree containing the tree node
indexed by node
.
If dir == BstDirection::Left
, node
will index the last tree node of the left sequence,
while if dir == BstDirection::Right
, node
will index the first tree node of the right
sequence (both with respect to in-order). The roots of the resulting sequences will be
returned as a tuple.
use outils::prelude::*; // The resulting trees are shown below: use outils::tree::traversal::BinaryInOrderValues; // // -- (3) -- let mut waaforest1 = WeightedAaForest::new(10); // / \ let mut waaforest2 = WeightedAaForest::new(10); // (1) (5) // / \ / \ let mut indices1 = Vec::new(); // (0) (2) (4) (6) indices1.push(waaforest1.insert_weighted(0, 1)); let mut indices2 = Vec::new(); indices2.push(waaforest2.insert_weighted(0, 1)); for i in 1..7 { indices1.push(waaforest1.insert_weighted(i, 1)); waaforest1.append(indices1[i-1], indices1[i]); indices2.push(waaforest2.insert_weighted(i, 1)); waaforest2.append(indices2[i-1], indices2[i]); } // Split the tree at 3 and keep 3 as part of the left (i.e. _smaller_) tree. // Because every node of the tree constructed above has a weight of 1, the root of the // left tree is expected to have a subweight of 4, the root of the right a subweight of 3: let result1 = waaforest1.split(indices1[3], BstDirection::Left); match(result1) { (Some(left), Some(right)) => { assert_eq!(waaforest1.subweight(left), Some(&4)); let seq_left: Vec<&usize> = BinaryInOrderValues::new(&waaforest1, left).collect(); assert_eq!(seq_left, vec![&0, &1, &2, &3]); assert_eq!(waaforest1.subweight(right), Some(&3)); let seq_right: Vec<&usize> = BinaryInOrderValues::new(&waaforest1, right).collect(); assert_eq!(seq_right, vec![&4, &5, &6]); } _ => { panic!("3 was neither first nor last, so the returned tuple should be (Some, Some)") } } // Split the tree at 3 and keep 3 as part of the right (i.e. _bigger_) tree. // Because every node of the tree constructed above has a weight of 1, the root of the // left tree is expected to have a subweight of 3, the root of the right a subweight of 4: let result2 = waaforest2.split(indices2[3], BstDirection::Right); match(result2) { (Some(left), Some(right)) => { assert_eq!(waaforest2.subweight(left), Some(&3)); let seq_left: Vec<&usize> = BinaryInOrderValues::new(&waaforest2, left).collect(); assert_eq!(seq_left, vec![&0, &1, &2]); assert_eq!(waaforest2.subweight(right), Some(&4)); let seq_right: Vec<&usize> = BinaryInOrderValues::new(&waaforest2, right).collect(); assert_eq!(seq_right, vec![&3, &4, &5, &6]); } _ => { panic!("3 was neither first nor last, so the returned tuple should be (Some, Some)"); } }
fn split_all(
&mut self,
node: NodeIndex,
size_hint: Option<usize>
) -> Vec<NodeIndex>
[src]
&mut self,
node: NodeIndex,
size_hint: Option<usize>
) -> Vec<NodeIndex>
Splits the whole sequence of tree nodes represented by the forest tree containing the tree
node indexed by node
into singleton (i.e. sole leaf) nodes. The subweights of the split nodes
will be adjusted accordingly.
If the tree nodes to be split is known beforehand, it can be specified optionally as
the size_hint
of the returned Vec
containing the split tree nodes.
Generally, this operation will be much faster than calling split
on each node of the
sequence separately, the reason being that no re-balancing is necessary when it is known
beforehand that every tree node will be split.
use outils::prelude::*; // The resulting tree is shown below: // let mut waaforest = WeightedAaForest::new(10); // -- (3) -- // / \ let mut indices = Vec::new(); // (1) (5) indices.push(waaforest.insert_weighted(0, 1)); // / \ / \ // (0) (2) (4) (6) for i in 1..7 { indices.push(waaforest.insert_weighted(i, 1)); waaforest.append(indices[i-1], indices[i]); } let split_nodes = waaforest.split_all(indices[0], Some(7)); assert_eq!(split_nodes.len(), indices.len()); // After splitting the forest tree, every one of its former nodes should be a singleton. // In particular, we expect the subweight of every node to equals its weight. for i in 0..7 { assert!(split_nodes.contains(&indices[i])); assert_eq!(waaforest.weight(indices[i]), waaforest.subweight(indices[i])); assert_eq!(waaforest.parent(indices[i]), None); assert_eq!(waaforest.child(indices[i], 0), None); assert_eq!(waaforest.child(indices[i], 1), None); }
fn append(&mut self, node_u: NodeIndex, node_v: NodeIndex) -> Option<NodeIndex>
[src]
Concatenate the sequences of tree nodes represented by the forest trees containing the
tree nodes indexed by node_u
and node_v
, respectively.
With respect to in-order, the former sequence will represent the smaller part of the new sequence, the latter sequence the bigger part. The root of the resulting sequence will be returned.
use outils::prelude::*; use outils::tree::traversal::BinaryInOrderValues; let mut waaforest = WeightedAaForest::new(10); // Insert values into the forest - each value will be a single-node tree in the forest. let mut indices = Vec::new(); for i in 0..7 { indices.push(waaforest.insert_weighted(i, 1)); } // Construct the _smaller_ tree, containing the in-order sequence 0,1,2,3 let mut left = indices[0]; left = waaforest.append(left, indices[1]).expect("Result should not be None"); left = waaforest.append(left, indices[2]).expect("Result should not be None"); left = waaforest.append(left, indices[3]).expect("Result should not be None"); { // Restrict scope of the borrow of `waaforest`. let seq: Vec<&usize> = BinaryInOrderValues::new(&waaforest, left).collect(); assert_eq!(seq, vec![&0, &1, &2, &3]); } // Construct the _bigger_ tree, containing the in-order sequence 4,5,6 let mut right = indices[4]; right = waaforest.append(right, indices[5]).expect("Result should not be None"); right = waaforest.append(right, indices[6]).expect("Result should not be None"); { // Restrict scope of the borrow of `waaforest`. let seq: Vec<&usize> = BinaryInOrderValues::new(&waaforest, right).collect(); assert_eq!(seq, vec![&4, &5, &6]); } // Because every node of the trees constructed above has a weight of 1, the root of the // left tree is expected to have a subweight of 4, the root of the right a subweight of 3: assert_eq!(waaforest.subweight(left), Some(&4)); assert_eq!(waaforest.subweight(right), Some(&3)); // Link left and right, constructing the in-order sequence 0,1,2,3,4,5,6. Afterwards, we // expect the subweight of the new root to equal 7. let root = waaforest.append(left, right).expect("Result should not be None"); assert_eq!(waaforest.subweight(root), Some(&7)); let seq: Vec<&usize> = BinaryInOrderValues::new(&waaforest, root).collect(); assert_eq!(seq, vec![&0, &1, &2, &3, &4, &5, &6]);
impl<V: Clone, W: Clone> Clone for WeightedAaForest<V, W> where
V: ValueType,
W: WeightType,
[src]
V: ValueType,
W: WeightType,
fn clone(&self) -> WeightedAaForest<V, W>
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
impl<V: Debug, W: Debug> Debug for WeightedAaForest<V, W> where
V: ValueType,
W: WeightType,
[src]
V: ValueType,
W: WeightType,
impl<V, W> Index<NodeIndex<usize>> for WeightedAaForest<V, W> where
V: ValueType,
W: WeightType,
[src]
V: ValueType,
W: WeightType,
impl<V, W> IndexMut<NodeIndex<usize>> for WeightedAaForest<V, W> where
V: ValueType,
W: WeightType,
[src]
V: ValueType,
W: WeightType,
impl<V, W> OrderedTree<usize> for WeightedAaForest<V, W> where
V: ValueType,
W: WeightType,
[src]
V: ValueType,
W: WeightType,
fn sub_predecessor(&self, node: NodeIndex) -> Option<NodeIndex>
[src]
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 waaforest = WeightedAaForest::new(10); // -- (3) -- // / \ let mut indices = Vec::new(); // (1) (5) indices.push(waaforest.insert_weighted(0, 1)); // / \ / \ // (0) (2) (4) (6) for i in 1..7 { indices.push(waaforest.insert_weighted(i, 1)); waaforest.append(indices[i-1], indices[i]); } // 2 is biggest key in left subtree of 3. assert_eq!(waaforest.sub_predecessor(indices[3]), Some(indices[2])); // 4 is a leaf and thus has no subtrees. assert_eq!(waaforest.sub_predecessor(indices[4]), None);
fn sub_successor(&self, node: NodeIndex) -> Option<NodeIndex>
[src]
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>
[src]
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 waaforest = WeightedAaForest::new(10); // -- (3) -- // / \ let mut indices = Vec::new(); // (1) (5) indices.push(waaforest.insert_weighted(0, 1)); // / \ / \ // (0) (2) (4) (6) for i in 1..7 { indices.push(waaforest.insert_weighted(i, 1)); waaforest.append(indices[i-1], indices[i]); } // 3 is the biggest key of the whole tree smaller than 4. assert_eq!(waaforest.predecessor(indices[4]), Some(indices[3])); // 0 is globally the smallest key of the whole tree and thus has no predecessor. assert_eq!(waaforest.predecessor(indices[0]), None);
fn successor(&self, node: NodeIndex) -> Option<NodeIndex>
[src]
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>
[src]
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 waaforest = WeightedAaForest::new(10); // -- (3) -- // / \ let mut indices = Vec::new(); // (1) (5) indices.push(waaforest.insert_weighted(0, 1)); // / \ / \ // (0) (2) (4) (6) for i in 1..7 { indices.push(waaforest.insert_weighted(i, 1)); waaforest.append(indices[i-1], indices[i]); } // 0 is the smallest key of the left subtree of 3 assert_eq!(waaforest.first(indices[3]), Some(indices[0])); // 0 is the smallest key of the left subtree of 1 assert_eq!(waaforest.first(indices[1]), Some(indices[0]));
fn last(&self, node: NodeIndex) -> Option<NodeIndex>
[src]
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
[src]
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, or if the nodes do not belong to the same forest tree, 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 waaforest = WeightedAaForest::new(10); // -- (3) -- // / \ let mut indices = Vec::new(); // (1) (5) indices.push(waaforest.insert_weighted(0, 1)); // / \ / \ // (0) (2) (4) (6) for i in 1..7 { indices.push(waaforest.insert(i)); waaforest.append(indices[i-1], indices[i]); } assert!(waaforest.is_smaller(indices[0], indices[3])); assert!(!waaforest.is_smaller(indices[3], indices[1]));
impl<V, W> Tgf for WeightedAaForest<V, W> where
V: ValueType,
W: WeightType,
[src]
V: ValueType,
W: WeightType,
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
.
impl<'slf, V, W> Values<'slf, V, usize> for WeightedAaForest<V, W> where
V: 'slf + ValueType,
W: WeightType,
[src]
V: 'slf + ValueType,
W: WeightType,
fn values(&'slf self) -> Box<dyn Iterator<Item = (NodeIndex, &'slf V)> + 'slf>
[src]
Returns a boxed iterator over the stored values and their corresponding
tree node indices held by self
. The values are not returned in any
particular order.
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));
Auto Trait Implementations
impl<V, W> RefUnwindSafe for WeightedAaForest<V, W> where
V: RefUnwindSafe,
W: RefUnwindSafe,
V: RefUnwindSafe,
W: RefUnwindSafe,
impl<V, W> Send for WeightedAaForest<V, W> where
V: Send,
W: Send,
V: Send,
W: Send,
impl<V, W> Sync for WeightedAaForest<V, W> where
V: Sync,
W: Sync,
V: Sync,
W: Sync,
impl<V, W> Unpin for WeightedAaForest<V, W> where
V: Unpin,
W: Unpin,
V: Unpin,
W: Unpin,
impl<V, W> UnwindSafe for WeightedAaForest<V, W> where
V: UnwindSafe,
W: UnwindSafe,
V: UnwindSafe,
W: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<V, T> VZip<V> for T where
V: MultiLane<T>,
V: MultiLane<T>,