Java 8 functional style to iterate with indexes

Question

I have been practicing java 8 streams and functional style for a while. Sometimes I try to solve some programming puzzles just using streams. And during this time I found a class of tasks which I don't know how to solve with streams, only with classical approach.

One example of this kind of tasks is: Given an array of numbers find index of the element which will make sum of the left part of array below zero. e.g. for array [1, 2, 3, -1, 3, -10, 9] answer will be 5

My first idea was to use IntStream.generate(0, arr.length)... but then I don't know how to accumulate values and being aware of index same time.

So questions are:

• Is it possible to somehow accumulate value over stream and then make conditional exit?
• What is then with parallel execution? it's not fitting to problem of finding indexes where we need to be aware of elements order.

Answer 1

I doubt your task is well suited for streams. What you are looking for is a typical scan left operation which is by nature a sequential operation.

For instance imagine the following elements in the pipeline: [1, 2, -4, 5]. A parallel execution may split it into two subparts namely [1, 2] and [-4, 5]. Then what would you do with them ? You cannot sum them independently because it will yields [3] and [1] and then you lost the fact that 1 + 2 - 4 < 0 was respected.

So even if you write a collector that keeps track of the index, and the sum, it won't be able to perform well in parallel (I doubt you can even benefit from it) but you can imagine such a collector for sequential use :

public static Collector<Integer, ?, Integer> indexSumLeft(int limit) {
        return Collector.of(
                () -> new int[]{-1, 0, 0},
                (arr, elem) -> {
                    if(arr[2] == 0) {
                        arr[1] += elem;
                        arr[0]++;
                    }
                    if(arr[1] < limit) {
                        arr[2] = 1;
                    }

                },
                (arr1, arr2) -> {throw new UnsupportedOperationException("Cannot run in parallel");},
                arr -> arr[0]

        );
    }

and a simple usage:

int index = IntStream.of(arr).boxed().collect(indexSumLeft(0));

This will still traverse all the elements of the pipeline, so not very efficient.

Also you might consider using Arrays.parallelPrefix if the data-source is an array. Just compute the partial sums over it and then use a stream to find the first index where the sum is below the limit.

Arrays.parallelPrefix(arr, Integer::sum);
int index = IntStream.range(0, arr.length)
                     .filter(i -> arr[i] < limit)
                     .findFirst()
                     .orElse(-1);

Here also all the partial sums are computed (but in parallel).

In short, I would use a simple for-loop.