Combine values with Java8 stream

Question

If I have a list with integers, is there a way to construct another list, where integers are summed if the difference to the head of the new list is below a threashold? I would like to solve this using Java 8 streams. It should work similar to the Scan operator of RxJava.

Example: 5, 2, 2, 5, 13    
Threashold: 2    
Result: 5, 9, 13

Intermediate results:    
5
5, 2
5, 4 (2 and 2 summed)
5, 9 (4 and 5 summed)
5, 9, 13

Answer 1

Sequential Stream solution may look like this:

List<Integer> result = Stream.of(5, 2, 2, 5, 13).collect(ArrayList::new, (list, n) -> {
    if(!list.isEmpty() && Math.abs(list.get(list.size()-1)-n) < 2)
        list.set(list.size()-1, list.get(list.size()-1)+n);
    else
        list.add(n);
}, (l1, l2) -> {throw new UnsupportedOperationException();});
System.out.println(result);

Though it looks not much better as good old solution:

List<Integer> input = Arrays.asList(5, 2, 2, 5, 13);
List<Integer> list = new ArrayList<>();
for(Integer n : input) {
    if(!list.isEmpty() && Math.abs(list.get(list.size()-1)-n) < 2)
        list.set(list.size()-1, list.get(list.size()-1)+n);
    else
        list.add(n);
}
System.out.println(list);

Seems that your problem is not associative, so it cannot be easily parallelized. For example, if you split the input into two groups like this (5, 2), (2, 5, 13), you cannot say whether the first two items of the second group should be merged until the first group is processed. Thus I cannot specify the proper combiner function.

Answer 2

As Tagir Valeev observed, (+1) the combining function is not associative, so reduce() won't work, and it's not possible to write a combiner function for a Collector. Instead, this combining function needs to be applied left-to-right, with the previous partial result being fed into the next operation. This is called a fold-left operation, and unfortunately Java streams don't have such an operation.

(Should they? Let me know.)

It's possible to sort-of write your own fold-left operation using forEachOrdered while capturing and mutating an object to hold partial state. First, let's extract the combining function into its own method:

// extracted from Tagir Valeev's answer
void combine(List<Integer> list, int n) {
    if (!list.isEmpty() && Math.abs(list.get(list.size()-1)-n) < 2)
        list.set(list.size()-1, list.get(list.size()-1)+n);
    else
        list.add(n);
}

Then, create the initial result list and call the combining function from within forEachOrdered:

List<Integer> result = new ArrayList<>();
IntStream.of(5, 2, 2, 5, 13)
         .forEachOrdered(n -> combine(result, n));

This gives the desired result of

[5, 9, 13]

In principle this can be done on a parallel stream, but performance will probably degrade to sequential given the semantics of forEachOrdered. Also note that the forEachOrdered operations are performed one at a time, so we needn't worry about thread safety of the data we're mutating.