内部イテレータを外部イテレータに手動で変換してみる実験

前回の続き。

内部イテレータを書くのは簡単で、外部イテレータを書くのは難しい。となれば内部イテレータの実装を元に外部イテレータ化できないかと考えた。

こういうのには継続渡し形式(Continuation Passing Style、CPS)というのを使うと良いらしい。

参考にしたサイト:

• http://practical-scheme.net/docs/cont-j.html
• http://www.h4.dion.ne.jp/~unkai/js/js12.html

継続渡し形式(CPS)とは

関数を呼び出してその戻り値を使ってなんらかの処理を行う代わりに、関数にそのなんらかの処理(継続処理)を渡して、値をreturnする代わりにその値で処理を呼び出してもらう方式のことらしい。

例えば足し算をするメソッドとその結果をプリントする処理があるとする。

import junit.framework.TestCase;
/* 挙動が確認し易いようにJUnitのTestCaseの中に書くよ */

public class CpsExamination extends TestCase {
    /** xとyを足し算して戻す */
    public int sum(int x, int y) {
        return x + y;
    }
    /** 10と20をsum()して結果をprintln()する */
    public void testSum() {
        int x = 10, y=20;
        System.out.println(sum(x, y));
    }
}

これを継続渡し形式に変換すると、

    public static class PrintResultHandler {
        public void printResult(int result) {
            System.out.println("result = " + result);
        }
    }
    /** sum()の継続渡し版。結果をreturnする代わりにresultHandlerのprintResult()を呼ぶ */
    public void sumCps(int x, int y, PrintResultHandler resultHandler) {
        int result = x + y;
        resultHandler.printResult(result);
    }
    public void testSumCps() {
        int x = 10, y=20;
        // return値を受け取って処理する代わりにPrintResultHandlerを渡す
        sumCps(x, y, new PrintResultHandler());
    }

となる。

GUIの入力待ちなどのように処理を中断したり非同期化する際に便利だったり、関数型言語だと末尾再帰の最適化が出来たりというメリットがあるらしい。

継続渡し形式の練習 1. 階乗の計算

再帰処理をおこなっている処理を継続渡し形式化してみる。

まず階乗の計算。

9! = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
10! = 10 * (9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1)

のように、nの階乗はn-1の階乗値にnを掛けたものになっている。
javaで書くと。

    /** @return nの階乗数を戻す。*/
    public  int fact(int n) {
        if (n == 0) {
            return 1;
        } else {
            return n * fact(n - 1);
        }
    }
    public void testFact() {
        int result = fact(10);
        assertEquals("10の階乗は3628800", 3628800, result);
    }

これを継続渡し形式で書き直す。
まず、int値の結果を受け取るResultHandlerインタフェースを定義

    public interface ResultHandler {
        void putResult(int result);
    }

ResultHandlerを使ってfact()を書き直す

    /** nの階乗数をresultHandlerにputResult()する*/
    public void factCps(final int n, final ResultHandler resultHandler) {
        if (n == 0) {
            resultHandler.putResult(1);
        } else {
            factCps(n -1, new ResultHandler() {
                /* n - 1の階乗の結果がresultとして渡ってくるはず */
                public void putResult(int result) {
                    resultHandler.putResult(n * result);
                }
            });
        }
    }
    public void testFactCps() {
        factCps(10, new ResultHandler() {
            public void putResult(int result) {
                assertEquals("10の階乗は3628800", 3628800, result);
            }
        });
    }

n-1の階乗を計算するfactCps()に渡すResultHandlerの実装が肝。n-1の階乗の実行結果をうけとってnを掛け、本来のresultHandlerにputResult()する処理を匿名内部クラスで実装した。これによって、1からnの全ての数を掛けたものが、最終的にトップレベルのResultHandlerに渡せる。

継続渡し形式の練習 2. フィボナッチ数の計算

フィボナッチ数列とは、

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...
1, 1, 2(=1+1), 3(=1+2), 5(=2+3), 8(=3+5),...

のように、1, 1から始まり*1、その前の2つの数の合計になっている数列で、フィボナッチ数列のn番目をnのフィボナッチ数という。
これをjavaで実装すると次のようになる。

    public static int fibo(int n) {
        if (n == 1 || n == 2) {
            return 1;
        } else {
            return fibo(n - 1) + fibo(n - 2);
        }
    }
    public void testFibo() {
        int result = fibo(10);
        assertEquals("10番目のフィボナッチ数は55", 55, result);
    }

内部で再帰的にfibo()を2回呼んでいる。

これを継続渡しに変換すると、次のようになる。

    public static void fiboCps(final int n, final ResultHandler resultHandler) {
        if (n == 1 || n == 2) {
            resultHandler.putResult(1);
        } else {
            fiboCps(n - 1, new ResultHandler() {
                /* n-1番目のフィボナッチ数を受け取る */
                public void putResult(final int result_min1) {
                    fiboCps(n - 2, new ResultHandler() {
                        /* n-2番目のフィボナッチ数を受け取る */
                        public void putResult(int result_min2) {
                            resultHandler.putResult(result_min1 + result_min2);
                        }
                    });
                }
            });
        }
    }
    public void testFiboCps() {
        fiboCps(10, new ResultHandler() {
            public void putResult(int result) {
                assertEquals("10番目のフィボナッチ数は55", 55, result);
            }
        });
    }

匿名内部クラスが入れ子になっていてややこしいですが、n-1の呼び出しに渡したResultHandlerでn-1の結果を受け取り、その中でn-2の呼び出しをおこない、その際渡すResultHandlerでn-2の呼び出し結果を受け取り、合算して元のresultHandlerにputResult()している。

継続渡し形式を中断可能にする

returnのくびきから解き放たれたため、継続渡し形式の処理は途中で実行をちょん切ってあとから続けたりできる。

その実現方法としては、再帰呼び出しを実行する代わりに、後で再帰呼び出しを実行する為のオブジェクトを作ってどこかに保存する。この部分、あちこちのCPSについてのページを見ても、グローバル変数に保存したり、元の継続に渡したり、受け取る用に引数を増やしたり、いろんな流派がある。*2今回はresultHandler経由で保存できるようにした。

まず呼び出しをくるんでやるためのインタフェース。

    public interface CpsWrapper {
        // 後で実行する
        void invoke();
    }

ResultHandlerに次に実行する「次の処理」を保存できるように拡張してやる

    public interface ResultHandlerIterable {
        void putResult(int result);
        void setNext(CpsWrapper next);
    }

トップレベルで渡すResultHandlerは、保存した「次の処理」を取得できるように拡張してやる

    public static interface ResultHandlerIterableTop extends ResultHandlerIterable {
        public CpsWrapper getNext();
    }

factCps()を中断可能に変更

    public void factCpsIterable(final int n, final ResultHandlerIterable resultHandler) {
        if (n == 0) {
            resultHandler.setNext(null);
            resultHandler.putResult(1);
        } else {
            // factCpsIterable()を直接呼ばず、CpsWrapper()にくるんでsetNext()で保存
            resultHandler.setNext(new CpsWrapper() {
                public void invoke() {
                    factCpsIterable(n -1, new ResultHandlerIterable() {
                        public void putResult(int result) {
                            resultHandler.putResult(n * result);
                        }
                        public void setNext(CpsWrapper next) {
                            resultHandler.setNext(next);
                        }
                    });
                }
            });
        }
    }
    public void testFactCpsIterable() {
        ResultHandlerIterableTop resultHandler = new ResultHandlerIterableTop() {
            private CpsWrapper next;
            public void putResult(int result) {
                assertEquals("10の階乗は3628800", 3628800, result);
            }
            public void setNext(CpsWrapper next) {
                this.next = next;
            }
            public CpsWrapper getNext() {
                return this.next;
            }
        };
        factCpsIterable(10, resultHandler); // この状態では、まだputResult()は実行されない
        // 中断された処理を順次実行
        while (resultHandler.getNext() != null) {
            resultHandler.getNext().invoke();
        }
        // 最後のinvoke()が実行された際にputResult()は実行されている。
    }

fiboCps()を中断可能に変更

    public static void fiboCpsIterable(final int n, final ResultHandlerIterable resultHandler) {
        if (n == 1 || n == 2) {
            resultHandler.setNext(null);
            resultHandler.putResult(1);
        } else {
            // fiboCpsIterable()を直接呼ばず、CpsWrapper()にくるんでsetNext()で保存
            resultHandler.setNext(new CpsWrapper() {
                public void invoke() {
                    fiboCpsIterable(n - 1, new ResultHandlerIterable() {
                        /* n-1番目のフィボナッチ数を受け取る */
                        public void putResult(final int result_min1) {
                            fiboCpsIterable(n - 2, new ResultHandlerIterable() {
                                /* n-2番目のフィボナッチ数を受け取る */
                                public void putResult(int result_min2) {
                                    resultHandler.putResult(result_min1 + result_min2);
                                }
                                public void setNext(CpsWrapper next) {
                                    resultHandler.setNext(next);
                                }
                            });
                        }
                        public void setNext(CpsWrapper next) {
                            resultHandler.setNext(next);
                        }
                    });
                }
            });
        }
    }
    public void testFiboCpsIterable() {
        ResultHandlerIterableTop resultHandler = new ResultHandlerIterableTop() {
            private CpsWrapper next;
            public void putResult(int result) {
                assertEquals("10番目のフィボナッチ数は55", 55, result);
            }
            public void setNext(CpsWrapper next) {
                this.next = next;
            }
            public CpsWrapper getNext() {
                return this.next;
            }
        };
        fiboCpsIterable(10, resultHandler);
        // 中断された処理を順次実行
        while (resultHandler.getNext() != null) {
            resultHandler.getNext().invoke();
        }
    }

途中で中断しても、中間結果を取り出せる訳じゃないのであまりうれしくないですが。特に階乗の方は、計算自体は最後の呼び出しで一気に実行されるので何もうれしくない。

内部イテレータを外部イテレータに変形する 1. 配列の場合

さて本題。

継続渡し形式に変換すると、途中で処理を中断して逐次実行できることが分かった。それを利用して、内部イテレータの実装を外部イテレータの実装に手動で変換してみる。

まずint配列の中身を順に返すイテレータの例(kaisehさんのところのものをそのまま拝借。ただしIntIterableは内部イテレータ用のものをIntIterableIn、外部イテレータ用のをIntIterableOutと名前を変更)

import junit.framework.TestCase;

public class IteratorTest extends TestCase {
    public interface IntIterator {
        boolean hasNext();
        int next();
    }
    public interface IntProcedure {
        boolean process(int n); // 処理を打ち切るとき false を返す
    }
    public interface IntIterableIn {
        boolean forEach(IntProcedure proc);
    }
    public interface IntIterableOut {
        IntIterator iterator();
    }
    public static class IntArray implements IntIterableIn {
        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 void testIteratorIn() {
        final int[] sample = new int[] {1,3,4,7,8};
        final IntArray intArray = new IntArray(sample);
        boolean result = intArray.forEach(new IntProcedure(){
            int counter = 0;
            public boolean process(int n) {
                assertEquals("" + counter + "番目の数が配列の" + counter + "番目の数と一致", sample[counter++], n);
                return true;
            }
        });
        assertTrue(result);
    }
}

これを継続渡しに変換していく。まず、enclosureの明確化の為にforEachをstatic化

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

次に、ループ処理を再帰に変更

        public boolean forEach(IntProcedure proc) {
            //return forEach(this, proc);
            return forEachRec(0, this, proc);
        }
        public static boolean forEachRec(int i, IntArray intArray, IntProcedure proc) {
            if (i >= intArray.length) {
                return true;
            } else {
                if (!proc.process(intArray.array[i])) {
                    return false;
                } else {
                    return forEachRec(i + 1, intArray, proc);
                }
            }
        }

継続渡しに変更

        public interface BooleanResultHandler {
            void putResult(boolean result);
        }
        /** トップレベルでresultを取り出す為のBooleanResultHandler拡張 */
        public interface BooleanResultHandlerTop extends BooleanResultHandler {
            boolean getResult();
        }
        public boolean forEach(IntProcedure proc) {
            BooleanResultHandlerTop resultHandler = new BooleanResultHandlerTop() {
                private boolean result;
                public void putResult(boolean result) {
                    this.result = result;
                }
                public boolean getResult() {
                    return this.result;
                }
            };
            forEachRecCps(0, this, proc, resultHandler);
            return resultHandler.getResult();
        }
        
        public static void forEachRecCps(int i, IntArray intArray, IntProcedure proc,
                final BooleanResultHandler resultHandler) {
            if (i >= intArray.length) {
                resultHandler.putResult(true);
            } else {
                if (!proc.process(intArray.array[i])) {
                    resultHandler.putResult(false);
                } else {
                    forEachRecCps(i + 1, intArray, proc, new BooleanResultHandler() {
                        public void putResult(boolean result) {
                            resultHandler.putResult(result);
                        }
                    });
                }
            }
        }
    }

forEachRecCps内の匿名内部クラスはなにもせずresultHandlerに委譲してるだけなので、単純に引数のresultHandlerをそのまま渡しても良いかも。

中断可能に変更

        // 次に実行する処理を保存できるように拡張
        public interface BooleanResultHandlerIterable {
            boolean getResult();
            void setNext(CpsWrapper cpsWrapper);
        }
        /**
         * トップレベルでnextを取得する為のBooleanResultHandlerIterable拡張。
         * 後で使うのでクラス化
         */
        public static class BooleanResultHandlerIterableTop implements BooleanResultHandlerIterable {
            private boolean result;
            private CpsWrapper cpsWrapper;
            public void putResult(boolean result) {
                this.result = result;
            }
            public void setNext(CpsWrapper cpsWrapper) {
                this.cpsWrapper = cpsWrapper;
            }
            public boolean getResult() {
                return this.result;
            }
            public CpsWrapper getNext() {
                return this.cpsWrapper;
            }
        };
        public boolean forEach(IntProcedure proc) {
            BooleanResultHandlerIterableTop resultHandler = new BooleanResultHandlerIterableTop();
            forEachRecCpsIterable(0, this, proc, resultHandler);
            // resultHandler.getNext()がなくなるまで回した後、getResult()で結果を取得
            while (resultHandler.getNext() != null) {
                resultHandler.getNext().invoke();
            }
            return resultHandler.getResult();
        }
        public static void forEachRecCpsIterable(final int i, final IntArray intArray, final IntProcedure proc,
                final BooleanResultHandlerIterable resultHandler) {
            if (i >= intArray.length) {
                resultHandler.setNext(null);
                resultHandler.putResult(true);
            } else {
                if (!proc.process(intArray.array[i])) {
                    resultHandler.setNext(null);
                    resultHandler.putResult(false);
                } else {
                    resultHandler.setNext(new CpsWrapper() {
                        public void invoke() {
                            forEachRecCpsIterable(i + 1, intArray, proc, new BooleanResultHandlerIterable() {
                                public void putResult(boolean result) {
                                    resultHandler.putResult(result);
                                }
                                public void setNext(CpsWrapper cpsWrapper) {
                                    resultHandler.setNext(cpsWrapper);
                                }
                            });
                        }
                    });
                }
            }
        }

最後に、このforEachRecCpsIterableを使ってIntArrayを外部イテレータ化する。

    public static class IntArray implements IntIterableIn, IntIterableOut {
        ... 
        // 最後に処理した値を取得できるようにIntProcedureを拡張
        public interface IntProcedureTop extends IntProcedure {
            int lastProcessedValue();
        }
        public IntIterator iterator() {
            // process()した値を横取りできるように、IntProcedureを作成する
            final IntProcedureTop intProcedure = new IntProcedureTop() {
                private int lastProcessedValue;
                public boolean process(int n) {
                    this.lastProcessedValue = n;
                    return true; // 自分からは中断しない
                }
                public int lastProcessedValue() {
                    return lastProcessedValue;
                }
            };
            // いきなりforEachRecCpsIterable()を呼ばない(next()時に実行)
            final BooleanResultHandlerIterableTop resultHandler = new BooleanResultHandlerIterableTop();
            if (length > 0) {
                resultHandler.setNext(new CpsWrapper() {
                    public void invoke() {
                        forEachRecCpsIterable(0, IntArray.this, intProcedure, resultHandler);
                    }
                });
            }
            return new IntIterator() {
                public boolean hasNext() {
                    return resultHandler.getNext() != null;
                }
                public int next() {
                    resultHandler.getNext().invoke();
                    return intProcedure.lastProcessedValue();
                }
            };
        }
    ...
    public void testIteratorOut() {
        final int[] sample = new int[] {1,3,4,7,8};
        IntArray intArray = new IntArray(sample);
        IntIterator it = intArray.iterator();
        int counter = 0;
        while(it.hasNext()) {
            assertEquals("" + counter + "番目の数が配列の" + counter + "番目の数と一致",
                    sample[counter++], it.next());
        };
    }

これで完成！と思いきや、実は5回呼んでもhasNext()がtrueを戻すため、ループが一回増えてしまう。これはforEachRecCpsIterable()で無条件で匿名内部クラスをnewしてsetNext()しているため。

外部イテレータを実装する場合、実際に処理を行う前にhasNext()で次の処理が可能かを返してやらないと行けない。事前に処理可能かどうかを判定できるかは処理によって違う。この部分は処理の内容を見て手を入れてやらないと行けないかも。

        public static void forEachRecCpsIterable(final int i, final IntArray intArray, final IntProcedure proc,
                final BooleanResultHandlerIterable resultHandler) {
            if (i >= intArray.length) {
                resultHandler.setNext(null);
                resultHandler.putResult(true);
            } else {
                if (!proc.process(intArray.array[i])) {
                    resultHandler.setNext(null);
                    resultHandler.putResult(false);
                } else {
                    // 次の処理が可能な場合だけ次の処理を作成
                    if (i + 1 >= intArray.length) {
                        resultHandler.setNext(null);
                        resultHandler.putResult(true);
                    } else {
                        resultHandler.setNext(new CpsWrapper() {
                            public void invoke() {
                                forEachRecCpsIterable(i + 1, intArray, proc, new BooleanResultHandlerIterable() {
                                    public void putResult(boolean result) {
                                        resultHandler.putResult(result);
                                    }
                                    public void setNext(CpsWrapper cpsWrapper) {
                                        resultHandler.setNext(cpsWrapper);
                                    }
                                });
                            }
                        });
                    }
                }
            }
        }

内部イテレータを外部イテレータに変形する 2. Tree構造の場合

前回作ったIntNodeの内部イテレータ実装を外部イテレータ化した。(途中経過は省略)

public class IntNode implements IntIterableIn, IntIterableOut {
    private final int value;
    private final List<IntNode> children;
    public IntNode(int value, List<IntNode> children) {
        this.value = value;
        this.children = children;
    }
    public final static IntNode sampleNode =
        new IntNode(1, Arrays.<IntNode>asList(
           new IntNode(2, Arrays.<IntNode>asList(
               new IntNode(3, null)
           )),
           new IntNode(4, null),
           new IntNode(5, Arrays.<IntNode>asList(
                   new IntNode(6,Arrays.<IntNode>asList(
                           new IntNode(7, null)
                   )),
                   new IntNode(8, null)
           )))
       );
    /** 外部イテレータを戻す */
    public IntIterator iterator() {
        final IntProcedureTop intProcedure = new IntProcedureTop() {
            private int lastProcessedValue;
            public boolean process(int n) {
                this.lastProcessedValue = n;
                return true; // 自分からは中断しない
            }
            public int lastProcessedValue() {
                return lastProcessedValue;
            }
        };
        final BooleanResultHandlerIterableTop resultHandler =  new BooleanResultHandlerIterableTop();
        resultHandler.setNext(new CpsWrapper() {
            public void invoke() {
                forEachRecCpsIterable(IntNode.this, intProcedure, resultHandler);                
            }
        });

        return new IntIterator() {
            public boolean hasNext() {
                return resultHandler.getNext() != null;
            }

            public int next() {
                resultHandler.getNext().invoke();
                return intProcedure.lastProcessedValue();
            }
        };
    }

    /** 内部イテレータ処理を実行 */
    public boolean forEach(final IntProcedure proc) {
        final BooleanResultHandlerIterableTop resultHandler =  new BooleanResultHandlerIterableTop();
        resultHandler.setNext(new CpsWrapper() {
            public void invoke() {
                forEachRecCpsIterable(IntNode.this, proc, resultHandler);                
            }
        });
        
        while (resultHandler.getNext() != null) {
            resultHandler.getNext().invoke();
        }
        return resultHandler.getResult();
    }
    /** IntNodeを引数に取るパターン */
    public static void forEachRecCpsIterable(IntNode node, final IntProcedure proc,
            final BooleanResultHandlerIterable resultHandler) {
        if (!proc.process(node.value)) {
            resultHandler.setNext(null);
            resultHandler.putResult(false);
        } else {
            forEachRecCpsIterable(node.children, proc, resultHandler);
        }
    }
    /** IntNodeのListを引数に取るパターン */
    public static void forEachRecCpsIterable(final List<IntNode> nodes,
            final IntProcedure proc,final BooleanResultHandlerIterable resultHandler) {
        if (nodes == null || nodes.isEmpty()) {
            resultHandler.setNext(null);
            resultHandler.putResult(true);
        } else {
            resultHandler.setNext(new CpsWrapper() {
                public void invoke() {
                    forEachRecCpsIterable(nodes.get(0), proc, new BooleanResultHandlerIterable() {
                        public void putResult(final boolean resultHead) {
                            forEachRecCpsIterable(nodes.subList(1, nodes.size()), proc,
                                    new BooleanResultHandlerIterable() {
                                public void putResult(boolean resultRest) {
                                    resultHandler.putResult(resultHead && resultRest);
                                }
                                public void setNext(CpsWrapper next) {
                                    resultHandler.setNext(next);
                                }
                            });
                        }
                        public void setNext(CpsWrapper next) {
                            resultHandler.setNext(next);
                        }
                    });
                }
            });
        }
    }
}

単体のIntNodeとIntNodeのListを引数にとるものの2メソッドを使って交互に呼んでいる。List版の方にだけ中断処理を入れている。

そのテスツ。

import junit.framework.TestCase;

public class InnerIteratorTest extends TestCase {

    /** 内部イテレータ用のcontains */
    public boolean containsIn(IntIterableIn c, final int value) {
        return !c.forEach(new IntProcedure() {
            public boolean process(int n) {
                return n != value;
            }
        });
    }
    public void testIteratorIn() {
        assertTrue("1は含まれる", containsIn(IntNode.sampleNode, 1));
        assertTrue("2は含まれる", containsIn(IntNode.sampleNode, 2));
        assertTrue("3は含まれる", containsIn(IntNode.sampleNode, 3));
        assertTrue("4は含まれる", containsIn(IntNode.sampleNode, 4));
        assertTrue("5は含まれる", containsIn(IntNode.sampleNode, 5));
        assertTrue("6は含まれる", containsIn(IntNode.sampleNode, 6));
        assertTrue("7は含まれる", containsIn(IntNode.sampleNode, 7));
        assertTrue("8は含まれる", containsIn(IntNode.sampleNode, 8));
        assertFalse("9は含まれない", containsIn(IntNode.sampleNode, 9));
    }

    /** 外部イテレータ用のcontains */
    public boolean containsOut(IntIterableOut c, int value) {
        IntIterator it = c.iterator();
        while (it.hasNext()) {
            if (it.next() == value) {
                return true;
            }
        }
        return false;
    }
    public void testIteratorOut() {
        assertTrue("1は含まれる", containsOut(IntNode.sampleNode, 1));
        assertTrue("2は含まれる", containsOut(IntNode.sampleNode, 2));
        assertTrue("3は含まれる", containsOut(IntNode.sampleNode, 3));
        assertTrue("4は含まれる", containsOut(IntNode.sampleNode, 4));
        assertTrue("5は含まれる", containsOut(IntNode.sampleNode, 5));
        assertTrue("6は含まれる", containsOut(IntNode.sampleNode, 6));
        assertTrue("7は含まれる", containsOut(IntNode.sampleNode, 7));
        assertTrue("8は含まれる", containsOut(IntNode.sampleNode, 8));
        assertFalse("9は含まれない", containsOut(IntNode.sampleNode, 9));
    }

    /** 取り出し順序と終端テスト */
    public void testIteratorOutIteration() {
        IntIterator it = IntNode.sampleNode.iterator();
        assertEquals(1, it.next());
        assertEquals(2, it.next());
        assertEquals(3, it.next());
        assertEquals(4, it.next());
        assertEquals(5, it.next());
        assertEquals(6, it.next());
        assertEquals(7, it.next());
        assertEquals(8, it.next());
        assertFalse(it.hasNext());
    }
}

感想

前回中途半端に手動で実装していたものは、継続渡し形式の出来損ないみたいな感じのものだった。

内部イテレータ処理の継続渡し変換は割と機械的に出来る。その上で外部イテレータ化変換する場合、hasNext()の為に事前に次回処理が可能かどうかの判定を実装しなければならず、敷居はやはり内部イテレータの実装より少し高い。

匿名内部クラスを使いまくりでネストが深くて読みにくいかもしれない。今回は関数型言語での実装例と見比べ易いようにあえて同じように実装した。もし実クラスが好きなら、以下のように変換できる。

interface Hoge {
    void doHoge();
}
public void testHoge() {
    final int intValue = 0;
    Hoge hoge = new Hoge() {
        public void doHoge() {
            System.out.println("value = " + intValue);
        }
    };
    hoge.doHoge();
}

/* は、下のように書けるよ */

interface Hoge {
    void doHoge();
}
public static class HogeImpl implements Hoge {
    private final int intValue;
    public HogeImpl(int intValue) {
        this.intValue = intValue;
    }
    public void doHoge() {
        System.out.println("value = " + this.intValue);
    }
}
public void testHoge2() {
    final int intValue = 0;
    Hoge hoge = new HogeImpl(intValue);
    hoge.doHoge();
}

クロージャと違ってfinalの変数の参照しか出来ないので、内部で参照する全変数をコンストラクタで渡してやればいい。

*1:Wikipediaなどでは0, 1から開始してるけど。1, 1の方が自然かも。兎的に考えて

*2:無くしたreturnの代わりにreturnすればシンプルそうだけど、そういう例は見かけなかった。