private static <T, R> ComposableFuture<Void> processTree(final List<T> elements,
                                                           final int rootNode,
                                                           final AtomicIntegerArray nodesState,
                                                           final R[] results,
                                                           final AtomicInteger pendingNodeLowerBound,
                                                           final FutureSuccessHandler<T, R> producer,
                                                           final boolean jumpWhenDone) {
    if (rootNode > elements.size()) {
      return ComposableFutures.fromNull();
    }

    if (!nodesState.compareAndSet(rootNode - 1, 0, 1)) {
      // A parallel flow is working on our subtree, let's look for another subtree.
      return jump(elements, nodesState, results, pendingNodeLowerBound, producer);
    }

    final ComposableFuture<R> root = producer.handle(elements.get(rootNode - 1));

    return root.flatMap(rootResult -> {
      results[rootNode - 1] = rootResult;
      final int leftNode = rootNode << 1;
      final ComposableFuture<Void> left = processTree(elements, leftNode, nodesState, results, pendingNodeLowerBound, producer, false);
      return left.flatMap(leftResults -> {
        final int rightNode = leftNode + 1;
        final ComposableFuture<Void> right = processTree(elements, rightNode, nodesState, results, pendingNodeLowerBound, producer, false);
        return jumpWhenDone ? right.flatMap(rightResults -> jump(elements, nodesState, results, pendingNodeLowerBound, producer)) : right;
      });
    });
  }
private static < T , R > ComposableFuture < Void > processTree ( final List < T > elements , final int rootNode , final AtomicIntegerArray nodesState , final R [ ] results , final AtomicInteger pendingNodeLowerBound , final FutureSuccessHandler < T , R > producer , final boolean jumpWhenDone ) { if ( rootNode > elements . size ( ) ) { return ComposableFutures . fromNull ( ) ; } if ( ! nodesState . compareAndSet ( rootNode - 1 , 0 , 1 ) ) { return jump ( elements , nodesState , results , pendingNodeLowerBound , producer ) ; } final ComposableFuture < R > root = producer . handle ( elements . get ( rootNode - 1 ) ) ; return root . flatMap ( rootResult -> { results [ rootNode - 1 ] = rootResult ; final int leftNode = rootNode << 1 ; final ComposableFuture < Void > left = processTree ( elements , leftNode , nodesState , results , pendingNodeLowerBound , producer , false ) ; return left . flatMap ( leftResults -> { final int rightNode = leftNode + 1 ; final ComposableFuture < Void > right = processTree ( elements , rightNode , nodesState , results , pendingNodeLowerBound , producer , false ) ; return jumpWhenDone ? right . flatMap ( rightResults -> jump ( elements , nodesState , results , pendingNodeLowerBound , producer ) ) : right ; } ) ; } ) ; }
@param elements
@param rootNode:              The root of the tree currently being processed.
@param nodesState:            Pending node is marked with 0, processed node with 1.
@param results:               An array containing the results of the computation.
@param pendingNodeLowerBound: All elements with index < pendingNodeLowerBound are
either processed, or going to be processed by the thread modifying pendingNodeLowerBound.
@param producer
@param jumpWhenDone:          Indicates whether to continue processing from the pending node
with smallest index or return the processed results.
@param <T>
@param <R>
@return A ComposableFuture that will eventually apply producer to a subset of elements.
The computation progresses serially through a subset of elements in no particular order.
Since the algorithm is recursive, effort is made to limit the recursion depth.
The list of elements is treated as a binary tree rooted at index 1 (which maps to elements index 0),
where each tree rooted at index i has left subtree rooted at 2 * i and right subtree rooted
at 2 * i + 1.
Given an input rootNode, the subtree rooted at rootNode is traversed Pre-order serially.
When the traversal of a complete subtree ends,
or a processed element is encountered, the traversal proceeds
from the top leftmost pending node (smallest index).
This traversal strategy minimizes contention on the same part of the tree
by separate flows, and decreases the recursion depth.