IntervalCalculator

IntervalCounter.java

import static java.lang.Integer.bitCount;

final class IntervalCalculator
{
    private final int lengthAsPowerOfTwo;
    private final int mask;
    private int lastIntervalSize;
    private int currentIntervalSize;
    private int pointer;

    IntervalCalculator(final int lengthAsPowerOfTwo)
    {
        if(bitCount(lengthAsPowerOfTwo) != 1)
        {
            throw new IllegalArgumentException();
        }
        this.lengthAsPowerOfTwo = lengthAsPowerOfTwo;
        this.mask = lengthAsPowerOfTwo - 1;
        lastIntervalSize = lengthAsPowerOfTwo;
        currentIntervalSize = lengthAsPowerOfTwo / 2;
    }

    int nextInterval()
    {
        if(pointer == lengthAsPowerOfTwo)
        {
            currentIntervalSize /= 2;
            lastIntervalSize /= 2;

            if(currentIntervalSize == 0)
            {
                reset();
                return 0;
            }
        }

        if((pointer != 0 && (pointer & (lastIntervalSize - 1)) == 0) || pointer == lengthAsPowerOfTwo)
        {
            pointer += currentIntervalSize;
            int interval = pointer & mask;
            pointer += currentIntervalSize;
            if(pointer > lengthAsPowerOfTwo)
            {
                pointer = interval + currentIntervalSize;
            }
            return interval;
        }

        int interval = pointer;
        pointer += currentIntervalSize;
        return interval & mask;
    }

    private void reset()
    {
        lastIntervalSize = lengthAsPowerOfTwo;
        currentIntervalSize = lengthAsPowerOfTwo / 2;
        pointer = currentIntervalSize;
    }

    public static void main(String[] args)
    {
        final IntervalCalculator calculator = new IntervalCalculator(16);

        assertThat(calculator.nextInterval(), 0);
        assertThat(calculator.nextInterval(), 8);
        assertThat(calculator.nextInterval(), 4);
        assertThat(calculator.nextInterval(), 12);
        assertThat(calculator.nextInterval(), 2);
        assertThat(calculator.nextInterval(), 6);
        assertThat(calculator.nextInterval(), 10);
        assertThat(calculator.nextInterval(), 14);
        assertThat(calculator.nextInterval(), 1);
        assertThat(calculator.nextInterval(), 3);
        assertThat(calculator.nextInterval(), 5);
        assertThat(calculator.nextInterval(), 7);
        assertThat(calculator.nextInterval(), 9);
        assertThat(calculator.nextInterval(), 11);
        assertThat(calculator.nextInterval(), 13);
        assertThat(calculator.nextInterval(), 15);

        assertThat(calculator.nextInterval(), 0);
        assertThat(calculator.nextInterval(), 8);
        assertThat(calculator.nextInterval(), 4);
        assertThat(calculator.nextInterval(), 12);
        assertThat(calculator.nextInterval(), 2);
        assertThat(calculator.nextInterval(), 6);
        assertThat(calculator.nextInterval(), 10);
        assertThat(calculator.nextInterval(), 14);
        assertThat(calculator.nextInterval(), 1);
        assertThat(calculator.nextInterval(), 3);
        assertThat(calculator.nextInterval(), 5);
        assertThat(calculator.nextInterval(), 7);
        assertThat(calculator.nextInterval(), 9);
        assertThat(calculator.nextInterval(), 11);
        assertThat(calculator.nextInterval(), 13);
        assertThat(calculator.nextInterval(), 15);
    }

    private static void assertThat(final int actual, final int expected)
    {
        if(expected != actual)
        {
            throw new AssertionError();
        }
    }
}