How to get the indexes of the elements in a Stream?

As an exercise to learn Java 8+ Streams I wanted to cast some of my simple Codility implementations as a Stream solution.

For example, the BinaryGap problem .. a simple one liner solution using Streams could be something like:

public static int solution(int N) {
    return Integer.toBinaryString(N).chars().
                     filter(x -> x == '1').whichIndexes().diff().max();
}

Only problem though, whichIndexes and diff don't exist. I need a way to get hold of the index of the filtered elements and then compute their pair-wise differences and that'd be a good starting point for a Streams' based one-liner solution.

UPDATE: here is my BinaryGap solution in C++, the Java non-Stream-ed version would be very similar though:

#include <bitset>
#include <iostream>
#include <math.h>

using namespace std;

int solution(int N) {
    bitset<32> bs(N);
    int maxGap = 0;
    std::size_t i = 0;
    while (bs[i] == 0) {
        i++;
    }
    int startPos = i;
    for (; i < bs.size(); ++i) {
        if (bs[i] == 1) {
            int gap = i - startPos - 1;
            if (gap > maxGap) {
                maxGap = gap;
            }
            startPos = i;
        }
    }
    return maxGap;
}

int main() {
    cout << solution(9) << " must be 2" << endl;
    cout << solution(529) << " must be 4" << endl;
    cout << solution(20) << " must be 1" << endl;
    cout << solution(32) << " must be 0" << endl;
    cout << solution(1041) << " must be 5" << endl;
    return 0;
}

Solution

Getting the indices is straightforward; stream a range of integers instead of the characters from the string.

String s = Integer.toBinaryString(N);
IntStream.range(0, s.length())
    .filter(i -> s.charAt(i) == '1')
    . // more stream operations

Computing the maximum difference is harder, since this depends on consecutive pairs from the stream, not individual elements. Anything which depends on multiple elements from the stream (rather than one at a time) has to be done in the collect stage. This is a bit tricky to get right: the IntStream.collect method takes three arguments:

A Supplier<R> which supplies a new object of type R to collect results in,
An ObjIntConsumer<R> which accumulates an object of type R with one more int,
A BiConsumer<R, R> which doesn't do anything in a non-parallel stream.

The type R will need to keep track of the the current maximum difference, and the last number seen so that the difference with the next number can be computed. One way to do this is to have a List of two numbers, where index 0 holds the max difference so far, and index 1 holds the previous number seen (if any).

String s = Integer.toBinaryString(N);
int maxDiff = IntStream.range(0, s.length())
    .filter(i -> s.charAt(i) == '1')
    .collect(
        // supply a new list to hold intermediate results
        () -> {
            List<Integer> acc = new ArrayList<Integer>();
            acc.add(0); // initial max diff; and result if no "gap" exists
            return acc;
        },
        // accumulate one more number into the result
        (List<Integer> list, int num) -> {
            if(list.size() == 1) {
                // this is the first number, no diffs yet
                list.add(num);
            } else {
                int max = list.get(0);
                int lastNum = list.get(1);
                int diff = num - lastNum;
                list.set(0, diff > max ? diff : max);
                list.set(1, num);
            }
        },
        // combine two accummulators; shouldn't be called
        (List<Integer> list1, List<Integer> list2) -> {
            throw new RuntimeException("combiner shouldn't be called");
        }
    )
    .get(0); // max diff is at index 0 in the list

This is almost certainly a worse solution than what you had before trying to use streams, but... well, you wanted a stream solution, so here it is.