外部イテレータと内部イテレータ

Javaでコレクションクラスを作ってそのイテレータを実装する場合、Javaにはクロージャが無いので、外部イテレータを使うことがほとんどだと思います。

例えばint値のコレクションとイテレータを自作するときは、まず以下のようにIntIteratorとIntIterableを用意して

public interface IntIterator {
    boolean hasNext();
    int next();
}

public interface IntIterable {
    IntIterator iterator();
}

以下のように実装します。

public class IntArray implements IntIterable {
    private int[] array;
    private int length;

    public IntArray(int[] array) {
        this.array = array;
        this.length = array.length;
    }

    public IntIterator iterator() {
        return new IntIterator() {
            int index;

            public boolean hasNext() {
                return index < length;
            }

            public int next() {
                return array[index++];
            }
        };
    }
}

ただ、Javaでも状況によっては内部イテレータを使うのもありだと思います。その場合は、例えばIntProcedureとIntIterableを次のように用意して

public interface IntProcedure {
    boolean process(int n); // 処理を打ち切るとき false を返す
}

public interface IntIterable {
    boolean forEach(IntProcedure proc);
}

以下のように実装します。

public class IntArray implements IntIterable {
    private int[] array;
    private int length;

    public IntArray(int[] array) {
        this.array = array;
        this.length = array.length;
    }

    public boolean forEach(IntProcedure proc) {
        for (int i = 0; i < length; i++) {
            if (!proc.process(array[i])) {
                return false;
            }
        }
        return true;
    }
}

使用例としては、コレクションに特定の要素が含まれているかどうか調べる場合、外部イテレータだとこうなりますが

public boolean contains(IntIterable c, int value) {
    IntIterator it = c.iterator();
    while (it.hasNext()) {
        if (it.next() == value) {
            return true;
        }
    }
    return false;
}

内部イテレータだとこうなります。

public boolean contains(IntIterable c, final int value) {
    return !c.forEach(new IntProcedure() {
        public boolean process(int n) {
            return n != value;
        }
    });
}

内部イテレータを使うメリットは、

イテレータ自体を簡単に実装できる
パフォーマンスが良い

の2点があると思います。

1については、コレクションのデータ構造が複雑化したときに、yield文の無いJavaで外部イテレータを作るのは結構骨が折れますが、内部イテレータなら要素を順に辿ってコールバックするだけなので簡単です。

2については、ループの内側の処理が軽くて、制御文自身のパフォーマンスが相対的に無視できない場合、結構大きな差が出ます。実際GNU Troveでは、パフォーマンスを稼ぐ目的で内部イテレータが用意されています。

自分の場合、Javaでイテレータといえば無条件に外部イテレータを想像しがちなので、内部イテレータのことも忘れないようにしようと思いました。