pub fn walk_tree_postfix<S, B, I>(
root: S,
children_of: B,
) -> WalkTreePostfix<S, B>
Expand description
Create a tree like postfix parallel iterator from an initial root node.
The children_of
function should take a node and iterate on all of its child nodes.
The best parallelization is obtained when the tree is balanced
but we should also be able to handle harder cases.
§Ordering
This function guarantees a postfix ordering. See also walk_tree_prefix
which guarantees a
prefix order. If you don’t care about ordering, you should use walk_tree
, which will use
whatever is believed to be fastest.
Between siblings, children are reduced in order – that is first children are reduced first.
For example a perfect binary tree of 7 nodes will reduced in the following order:
a
/ \
/ \
b c
/ \ / \
d e f g
reduced as d,e,b,f,g,c,a
§Example
4
/ \
/ \
2 3
/ \
1 2
use rayon::iter::walk_tree_postfix;
use rayon::prelude::*;
let par_iter = walk_tree_postfix(4, |&e| {
if e <= 2 {
Vec::new()
} else {
vec![e / 2, e / 2 + 1]
}
});
assert_eq!(par_iter.sum::<u32>(), 12);
§Example
use rayon::prelude::*;
use rayon::iter::walk_tree_postfix;
struct Node {
content: u32,
left: Option<Box<Node>>,
right: Option<Box<Node>>,
}
// Here we loop on the following tree:
//
// 10
// / \
// / \
// 3 14
// \
// \
// 18
let root = Node {
content: 10,
left: Some(Box::new(Node {
content: 3,
left: None,
right: None,
})),
right: Some(Box::new(Node {
content: 14,
left: None,
right: Some(Box::new(Node {
content: 18,
left: None,
right: None,
})),
})),
};
let mut v: Vec<u32> = walk_tree_postfix(&root, |r| {
r.left
.as_ref()
.into_iter()
.chain(r.right.as_ref())
.map(|n| &**n)
})
.map(|node| node.content)
.collect();
assert_eq!(v, vec![3, 18, 14, 10]);