Function rayon::iter::walk_tree_postfix

pub fn walk_tree_postfix<S, B, I>(
    root: S,
    children_of: B,
) -> WalkTreePostfix<S, B>
where
    S: Send,
    B: Fn(&S) -> I + Send + Sync,
    I: IntoIterator<Item = S>,

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