Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Create a stream of custom alternating numbers

How can I make an IntStream that starts in the middle of a given sequential range, and then streams the next numbers starting in the middle and alternating to the left and right. For example, for a given sequential range of numbers 1 2 3 4 5, the custom sequence would be 3 2 4 1 5 or 3 4 2 5 1 depending whether you start with left or right first.

I basically am trying to iterate through an array starting from the middle and going outward evenly (not going to the left or right fully first).

I have tried this using just for loops but the code is messy and I think it would be much better to just line up a collection or stream of numbers instead of checking for it on the fly (because of all the index out of bounds exceptions that have to be checked for). Here is the original code that I think would be much better as a pre computed stream of ints:

        int middle = myArray.length / 2;
        Object value = myArray[middle]; //have to reference middle since the for loop won't
        //do operation on value
        for (int offset = 1; true; offset++) {
            int nextRight = middle + offset;
            int nextLeft = middle - offset;
            if (nextRight < myArray.length) { // Have to guard against exception, but can't catch exception ahead of time because left or null may not be empty.
                Object value = myArray[nextRight];
                //do operation on value
            }
            if (nextLeft >= 0) {
                Object value = myArray[nextRight];
                //do operation on value
            }
            if (nextRight >= myArray.length) {
                break; //exit logic
            }
            if (nextLeft < 0) {
                break; //exit logic
            }
        }
like image 851
Zombies Avatar asked Dec 30 '17 15:12

Zombies


2 Answers

Try this:

import static java.lang.Integer.signum;

static IntStream altSeq(int n) {
    return IntStream.iterate(2 * (n % 2) - 1, i -> -i - signum(i))
                    .map(i -> i / 2 + (n + 1) / 2)
                    .limit(n);
}

For example, altSeq(5) produces:

[3, 2, 4, 1, 5]

and running altSeq(6) produces:

[3, 4, 2, 5, 1, 6]

Briefly, we generate an ascending sequence that alternates sign:

1, -2, 3, -4, 5, ...

That's what the i -> -i - signum(i) expression does. Then, we divide by two in order to get the offsets from the midpoint:

0, -1, 1, -2, 2, ...

That's where the i / 2 in the first term of the map expression comes from. Then we add the midpoint of the range 1..n which is (n + 1) / 2, the second term of the map expression. For n = 5, this gives us

3, 2, 4, 1, 5, ...

Starting at 1 works for odd length sequences. For even lengths, we want to start with -1. The seed expression 2 * (n % 2) - 1 computes the right seed value for both even and odd length sequences.

Finally, we apply limit(n) to terminate the sequence.

like image 102
Stuart Marks Avatar answered Sep 23 '22 11:09

Stuart Marks


Since you said, you want to use the sequence to iterate over an array, I changed it to produce numbers including zero, but excluding n, so you can directly pass in an array length and get valid indices.

Then you can use

static IntStream altSeq(int n) {
    int mid = (n-1)/2;
    return IntStream.rangeClosed(1, n)
                    .map(i -> mid + (i>>>1)*signum(rotateRight(i,1)));
}

The approach is similar to Stuart Marks’ answer, but uses an IntStream.rangeClosed() as base, which creates a sized stream, which works much more efficient than creating an infinite stream (like iterate) and applying a limit, especially for operations like toArray, count, and for parallel streams. In other words, the performance is on par with iterating over the range/array in the usual order.

The natural number range is converted by using the lowest bit as sign, which is alternating for ascending numbers, and shifting the numbers one bit to the right, which is equivalent to dividing the magnitude of the numbers by two.

An alternative notation performing only one bitshift per element would be

static IntStream altSeq(int n) {
    int mid = (n-1)/2;
    return IntStream.rangeClosed(1, n)
                    .map(i -> Integer.rotateRight(i, 1))
                    .map(i -> mid + (i&Integer.MAX_VALUE)*signum(i));
}
like image 43
Holger Avatar answered Sep 21 '22 11:09

Holger