半開区間の探索

連続した半開区間があるとき、与えられた整数がどの半開区間に属するかを知りたい、なんて応用があって。

たとえば [0,30), [30, 50), [50, 80), [80, 100) とのような半開区間列があったとき 13 は [0, 30) に入るし、 50 は [50, 80) に入る。
この探索を Java コードでどう表現するか。

というので書いてみたのがこちら。：

class RangeFinder {
    public RangeFinder(long[] range) {
        assert range != null && range.length > 1 : "range は非 null で、要素を少なくともふたつ含む。";
        final int length = range.length - 1;
        index = new Range[length];
        for (int i = 0; i < length; ++i) {
            index[i] = new Range(range[i], range[i + 1]);
        }
    }

    public int find(final long value) {
        return Arrays.binarySearch(index, value);
    }

    private final Range[] index;

    private static final class Range implements Comparable<Long> {
        private final long beg;
        private final long end;

        public Range(long begin, long end) {
            this.beg = begin;
            this.end = end;
        }

        @Override
        public int compareTo(Long other) {
            final long value = other;
            if (value < beg) {
                return 1;
            }
            if (value < end) {
                return 0;
            }
            /* else */{
                return -1;
            }
        }
    }
}

こんなテストコードが動く。：

@Test
public void 所属する半開区間の探索() {
    // [0,10),[10,20),[20,30),[30,40),[40,50),[50,60),[60,70),[70,80),[80,90),[90,100)
    final long[] range = { 0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };

    final RangeFinder finder = new RangeFinder(range);
    assertEquals(-1, finder.find(-1));
    for (int i = 0; i < 100; ++i) {
        assertEquals(i / 10, finder.find(i));
    }
    assertEquals(-11, finder.find(100));
}

binarySearch を使っているので、与える範囲の数列は昇順で並んでいることが前提。

もともとは…

もともとは binarySearch は値の探索には使えるけれど、連続した区間の探索に使うにはどうすればいいかな？　というのがはじまりで。
long 配列があるんだったら、それを参照する形で流用できないものかと考えたのが次のコード。：

class OriginalRangeFinder {
    public OriginalRangeFinder(long[] range) {
        final int length = range.length - 1;
        this.range = range;
        index = new Index[length];
        for (int i = 0; i < length; ++i) {
            index[i] = new Index(i);
        }
    }

    public int find(final long value) {
        return Arrays.binarySearch(index, value);
    }

    private final long[] range;
    private final Index[] index;

    private final class Index implements Comparable<Long> {
        final int offset;

        public Index(int offset) {
            this.offset = offset;
        }

        @Override
        public int compareTo(Long other) {
            final long value = other;
            if (value < range[offset]) {
                return 1;
            }
            if (value < range[offset + 1]) {
                return 0;
            }
            /* else */{
                return -1;
            }
        }
    }
}

でも long と Index の配列を二本もたないほうが、そして Index クラスで親の range フィールドを共有しないほうが、わかりやすいだろうなというので冒頭に掲げたコードになりました。