Function walk_tree_prefix

pub fn walk_tree_prefix<S, B, I>(
    root: S,
    children_of: B,
) -> WalkTreePrefix<S, B>
where
    S: Send,
    B: Fn(&S) -> I + Send + Sync,
    I: IntoIterator<Item = S>,
    I::IntoIter: DoubleEndedIterator,

Create a tree-like prefix parallel iterator from an initial root node. The children_of function should take a node and return an iterator over 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 prefix ordering. See also walk_tree_postfix, which guarantees a postfix order. If you don’t care about ordering, you should use walk_tree, which will use whatever is believed to be fastest. For example a perfect binary tree of 7 nodes will reduced in the following order:

     a
    / \
   /   \
  b     c
 / \   / \
d   e f   g

reduced as a,b,d,e,c,f,g

Example

     4
    / \
   /   \
  2     3
       / \
      1   2

use rayon::iter::walk_tree_prefix;
use rayon::prelude::*;

let par_iter = walk_tree_prefix(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_prefix;

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_prefix(&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![10, 3, 14, 18]);