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

Question

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;
}

Answer 1

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.

Answer 2

You can't get at the indexes of the elements in one single stream unless you feed indices from the beginning, like the IntStream trick does. If you feed it Strings only, you're lost.

Zipping the streamed characters with another stream of Integers to operate eventually on a Pair<String, Integer> would be another way to introduce indexes, but there's no built in zip method in the streaming framework (yet). There are libraries and workarounds (see link).

Also you can't operate on consecutive elements, all you ever see (outside the collect stage or the reduce method, which is of no help for the purpose) is the element at hand (except you come up with dirty tricks as shown below and).

Btw. here's a potential one-liner that popped up in the process, perhaps with some edge-case flaws regarding binary gap (ask @Holger (or Eugene), I think, they're still discussing...). I'm not familiar with its fine print actually, and it is not relevant for the OP (IMO).

Arrays.stream(Integer.toBinaryString(n).replaceAll("0*$|^0*", "").split("1"))
      .map(String::length)
      .reduce(0, Math::max)

This one I think is as close as you can get (without zipping) to your initial idea, with elements scavenged from @Kaya3 and this interesting hack to get pairs from consecutive elements ({1,2,3,4} -> {{1,2},{2,3},{3,4}}). You could do the diff in the map-to-pair step too, spares another line maybe, but its weird enough like this:

        String st = Integer.toBinaryString(N);
        Integer max = IntStream.range(0, st.length() - 1)
                .filter(i -> st.charAt(i) == '1')
                .boxed()
                .map(new Function<Integer, Pair>() {
                    Integer previous;

                    @Override
                    public Pair apply(Integer i) {
                        Pair p = new Pair(previous, i);
                        previous = i;
                        return p;
                    }
                }).skip(1) //first element is {null, smthg}
                .map(i -> (i.right - i.left) - 1)
                .max(Integer::compareTo)
                .orElse(0);

But mind you: "This [map hack] is completely contrary to the design of the streams framework and directly violates the contract of the map API, as the anonymous function is not stateless. Try running this with a parallel stream and ... you will see ... infrequent random "errors" almost impossible to reproduce ... This can be disastrous."

I think, used with parallelStream() it would give you results that are even guaranteed to be wrong, because then as many pairs are missing as there are partitions of the stream.

Answer 3

Note that a computer does already compute in the binary system whereas both, converting a value to a String and processing a String, are expensive operations, compared to processing an int value.

To stream over the bits of an int, you can use the following solutions:

Given

int value = 1001;

IntStream.range(0, 32)
    .filter(i -> (value & (1 << i)) != 0)
    .forEach(System.out::println);

This utilizes the fact that we know that there can be at most 32 bits and it just checks for each whether it is set in the int value. The printing action is just for demonstration.

Alternatively, we can use a builtin tool for bit manipulations:

BitSet.valueOf(new long[] { Integer.toUnsignedLong(value) }).stream()
    .forEach(System.out::println);

For completeness, an iteration logic like with a loop

IntStream.iterate(value, i -> i != 0, i -> i - Integer.highestOneBit(i))
    .map(i -> Integer.numberOfTrailingZeros(Integer.highestOneBit(i)))
    .forEach(System.out::println);

But this iterate method with an end condition requires Java 9. For Java 8, we would need a work-around:

IntStream.iterate(value, i -> i - Integer.highestOneBit(i))
    .limit(32).filter(i -> i != 0)
    .map(i -> Integer.numberOfTrailingZeros(Integer.highestOneBit(i)))
    .forEach(System.out::println);

This again uses the fact that we know the maximum number of bits, further that we know that after encountering a zero, no non-zero value will appear, so filter is semantically equivalent to a stop condition here.

Still, a Stream is not a good tool for the tasks of processing two adjacent elements. As the other answers show, a Stream solution is complicated and still, these solutions are not fully adhering to the contract of the Stream API, bearing certain limitations, you have to keep in mind.

In contrast, a BitSet based loop solution looks like:

BitSet bs = BitSet.valueOf(new long[] { Integer.toUnsignedLong(value) });
int maxDiff = 0;
for(int s = bs.nextSetBit(0), e; (e = bs.nextSetBit(s + 1)) >= 0; s = e) {
    maxDiff = Math.max(maxDiff, e - s);
}
System.out.println(maxDiff == 0? "No range at all":
    "max diff: "+maxDiff+", resp, max gap "+(maxDiff-1));

Note that the gap, i.e the number of zeros between two one bits, is one smaller than the difference between the bit numbers.

We can perform the operation entirely with intrinsic int operations, which will be the most efficient:

int maxDiff = 0;
for(int i = value, bit1 = Integer.lowestOneBit(i), bit2,
        s = Integer.numberOfTrailingZeros(bit1), e;
        (bit2 = Integer.lowestOneBit(i -= bit1)) != 0; bit1 = bit2, s = e) {
    e = Integer.numberOfTrailingZeros(bit2);
    maxDiff = Math.max(maxDiff, e - s);
}
System.out.println(maxDiff == 0? "No range at all":
    "max diff: "+maxDiff+", resp, max gap "+(maxDiff-1));

This is a bit hard to read, but still way simpler than the Stream solution…

Answer 4

My first intuition would be to go for a regex, something like this:

static int regex(int n) {
    String s = Integer.toBinaryString(n);
    Pattern p = Pattern.compile("1(0+)(?=1)");
    Matcher m = p.matcher(s);
    int max = 0;
    while (m.find()) {
        max = Math.max(max, m.end(1) - m.start(1));
    }
    return max;
}

If you have java-9, this could be written in "one-liner" too:

static int regexMineJava9(int n) {
    return Pattern.compile("1(0+)(?=1)")
                  .matcher(Integer.toBinaryString(n))
                  .results()
                  .mapToInt(mr -> mr.end(1) - mr.start(1))
                  .max()
                  .orElse(0);
}

To me this is a bit more readable than this for example:

static int loop(int n) {
    int max = 0;

    while (n != 0) {
        int left = Integer.numberOfTrailingZeros(Integer.highestOneBit(n));
        n = n & ~(1 << left);
        int right = Integer.numberOfTrailingZeros(Integer.highestOneBit(n));

        if (right != 32) {
            max = left - right - 1;
        }
    }

    return max;
}

Though the last loop should be the most performant one.

For the fun of it here is a BitSet also, pretty much what Holger did, but a bit un-winded:

static int bitSet(int n) {
    BitSet bitSet = BitSet.valueOf(new long[]{Integer.toUnsignedLong(n)});
    int left = bitSet.nextSetBit(0);
    int max = 0;
    while (left != -1) {
        int right = bitSet.nextSetBit(left + 1);
        if (right == -1) {
            break;
        }
        max = Math.max(right - left - 1, max);
        left = right;
    }

    return max;
}