ツリー構造用の外部/内部イテレータの実装

Java

お題:

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

外部イテレータと内部イテレータ - kaisehのブログ


ツリー構造(複雑というほどではないけど、)の場合に、どれぐらい骨が折れるが実際にやってみた。


結論としては、やっぱり内部イテレータの方が楽そうだ。でも外部イテレータを作るのも面白いかも。


追記(2011/11/18) :
外部イテレータの実装は、Tree Iteratorを使う方が圧倒的にシンプルなのでそっちのが参考になるかも。

データ構造

図のような数値付のツリー構造を考える。

クラスで書くと次のような感じ。

public class IntNode {
    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)
           )))
       );
}

このツリーの全valueを処理するように外部イテレータ/内部イテレータ化してみる。

内部イテレータを実装

IntIterator/IntProcedure/IntIterableは参照先のエントリのものをそのまま使います。

public class IntNode implements IntIterable {
...(前出の部分は省略)...

    /** 内部イテレータ版のIntIterableを実装 */
    public boolean forEach(IntProcedure proc) {
        if (!proc.process(value)) {
            return false;
        }
        if (children != null) {
            /** 子要素を順に処理。 */
            for (IntNode child: children) {
                if (!child.forEach(proc)) {
                    return false;
                }
            }
        }
        return true;
    }
}

IntProcedureを引き回して再帰的に処理するだけなのでとても簡単。

外部イテレータを実装 その1. 最初に全要素をスキャンして配列を作成

IntIterableは参照先のエントリの外部イテレータ用のものをそのまま使います。

public class IntNode implements IntIterable {
...(前出の部分は省略)...

    /** 再帰的にすべての値をlistにaddする */
    private void addValuesToList(List<Integer> list) {
        list.add(Integer.valueOf(value));
        if (children != null) {
            for (IntNode child: children) {
                child.addValuesToList(list);
            }
        }
    }
    /** 外部イテレータ版のIntIterableを実装 */
    public IntIterator iterator() {
        List<Integer> allValues = new ArrayList<Integer>();
        IntNode.this.addValuesToList(allValues);

        final Integer array[] = allValues.toArray(new Integer[]{});
        final int length = array.length;
        return new IntIterator() {
            int index;

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

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


再帰的に値を全部集めれば、あとの実装は配列バージョンと同じなのでそこそこ楽。


全ての要素をスキャンするため処理としては重い。また、無限リストには対応できない。

外部イテレータを実装 その2. 最終処理位置を覚えておいて続きを処理

栞的なものを用意し、最終処理位置を覚えておく。
配列なら今何番目かを覚えておくだけで良かったが、ツリーの場合現在地を表すならパス的なものを用意すれば良い。

public class IntNode implements IntIterable {
...(前出の部分は省略)...

    /** 外部イテレータ版のIntIterableを実装 */
    public IntIterator iterator() {
        return new IntIterator() {
            /** ツリーの位置を子要素の順番で保持。'1'->'5'->'6'->'7'ならば[2,0,0] */
            Stack<Integer> path = new Stack<Integer>();
            /** 最後までスキャン済み */
            boolean atEnd = false;

            /** thisのpathで指定される現在のノードを戻す */
            private IntNode getLastNode() {
                int depth = path.size();
                IntNode lastNode = IntNode.this;
                for (int index = 0; index < depth; index++) {
                    List<IntNode> children = lastNode.children;
                    int pos = path.get(index);
                    lastNode = children.get(pos);
                }
                return lastNode;
            }

            public boolean hasNext() {
                return !atEnd;
            }

            public int next() {
                IntNode lastNode = getLastNode();
                int value = lastNode.value;

                if (lastNode.children != null && !lastNode.children.isEmpty()) {
                    // 子要素がある場合、パスの末尾に0(子要素の0番目を指示)を追加したものが次要素
                    path.push(0);
                } else {
                    while (!path.empty() || !(atEnd = true)) {
                        int pos = path.pop();
                        IntNode parent = getLastNode();

                        // 次の兄弟要素があれば、それを次要素として指定
                        if (pos + 1 < parent.children.size()) {
                            path.push(pos + 1);
                            break;
                        }
                        // 次の兄弟要素が無ければ一つ上の階層に移動
                    }
                }
                return value;
            }
        };
    }
}

面倒くさいです。これも再帰を使えばもう少し単純化できそうだけど、あえて再帰無しで実装してみた。


Stack型のpathに階層ごとに子要素の何番目を処理中かを覚えておき、次の処理のときにそこから再開する。次の要素を探すのに、繰り上がり処理があってやや複雑。

外部イテレータを実装 その3. 残りの要素を処理するオブジェクトを作る

残りの処理を覚えておくのに、逐次的にインスタンスを生成する。
nextの値を返すときに、値と一緒に残りの要素を処理するオブジェクトを生成して一緒に返すようにする。

public interface IntNodeGenerator {
    /** 現在の値を戻す */
    int getItem();
    /** 残りの要素を処理するIntNodeGeneratorを戻す */
    IntNodeGenerator nextNodeGenerator();
}

public class IntNode implements IntIterable {
...(前出の部分は省略)...

    public IntIterator iterator() {
        return new IntIterator() {
            private IntNodeGenerator nodeGenerator = ...; // 現在の値を生成するインスタンス
            public boolean hasNext() {
                return nodeGenerator != null;
            }
            public int next() { // 値を取得し、ついでに残りの値を処理するインスタンスも受け取る
                int value = nodeGenerator.getItem();
                nodeGenerator = nodeGenerator.nextNodeGenerator();
                return value;
            }
        };
    }
....

Generatorという名称はあまり適切でないかもしれない。ここでは端的に「値を生成する奴」という意味で。


で、その実装。まず、ツリー構造が処理できるように数珠つなぎに出来るようにする。

    public static class IntNodeGeneratorImpl implements IntNodeGenerator {
        private List<IntNode> nodes;
        private IntNodeGeneratorImpl next;
        IntNodeGeneratorImpl(List<IntNode> nodes, final IntNodeGeneratorImpl next) {
            if (nodes == null || nodes.isEmpty()) {
                throw new IllegalArgumentException("'nodes' is null or empty: " + nodes);
            }
            this.nodes = nodes;
            this.next = next;
        }
        ....
    }

現在の値としてリストの先頭の要素を戻す

        public int getItem() {
            return nodes.get(0).value;
        }

残りの要素を処理するIntNodeGeneratorImplを生成して戻す。先頭要素に子要素がある場合、先に子要素リストを処理し、その後残った兄弟要素を処理できるように、IntNodeGeneratorImplを二個生成して数珠つなぎにする。

        public IntNodeGenerator nextNodeGenerator() {
            List<IntNode> rest = nodes.subList(1, nodes.size());
            List<IntNode> children = nodes.get(0).children;

            IntNodeGeneratorImpl nextGenerator = this.next;
            // 同階層の残りを処理するIntNodeGeneratorを生成
            if (rest != null && !rest.isEmpty()) {
                nextGenerator = new IntNodeGeneratorImpl(rest, nextGenerator);
            }
            // 子供を処理するIntNodeGeneratorを生成
            if (children != null && !children.isEmpty()) {
                nextGenerator = new IntNodeGeneratorImpl(children, nextGenerator);
            }
            return nextGenerator;
        }


図で書くと次のような感じ。まず一つ目のIntNodeGeneratorから次のIntNodeGeneratorを生成するところ。

1つ目のNodeには兄弟は無いので、nextGenerator()は子供達を処理する奴を返す。


2番目のNodeには兄弟と子供があるので、二つのIntNodeGeneratorを作って子→兄弟の順に処理できるように繋ぐ。

これで階層が深くても、順に上の階層に戻って処理できる。


ソースコードをまとめると。

public class IntNode implements IntIterable {
...(前出の部分は省略)...

    public interface IntNodeGenerator {
        int getItem();
        IntNodeGenerator nextNodeGenerator();
    }
    public IntIterator iterator() {
        return new IntIterator() {
            private IntNodeGenerator nodeGenerator =
            　　　　new IntNodeGeneratorImpl(Arrays.asList(IntNode.this), null);
            public boolean hasNext() {
                return nodeGenerator != null;
            }
            public int next() {
                int value = nodeGenerator.getItem();
                nodeGenerator = nodeGenerator.nextNodeGenerator();
                return value;
            }
        };
    }
    public static class IntNodeGeneratorImpl implements IntNodeGenerator {
        private List<IntNode> nodes;
        private IntNodeGeneratorImpl next;

        IntNodeGeneratorImpl(List<IntNode> nodes, final IntNodeGeneratorImpl next) {
            if (nodes == null || nodes.isEmpty()) {
                throw new IllegalArgumentException("'nodes' is null or empty: " + nodes);
            }
            this.nodes = nodes;
            this.next = next;
        }
        public int getItem() {
            return nodes.get(0).value;
        }
        public IntNodeGenerator nextNodeGenerator() {
            List<IntNode> rest = nodes.subList(1, nodes.size());
            List<IntNode> children = nodes.get(0).children;

            IntNodeGeneratorImpl nextGenerator = this.next;
            // 同階層の残りを処理するIntNodeGeneratorを生成
            if (rest != null && !rest.isEmpty()) {
                nextGenerator = new IntNodeGeneratorImpl(rest, nextGenerator);
            }
            // 子供を処理するIntNodeGeneratorを生成
            if (children != null && !children.isEmpty()) {
                nextGenerator = new IntNodeGeneratorImpl(children, nextGenerator);
            }
            return nextGenerator;
        }
    }
}

うーん、なんだろうこれ。ちょっと面白いかも。

おまけ。その3の奴をGeneric化してみた。

Genericsの練習で。


IntNodeGeneratorをGeneratorに変更

public interface Generator<T> {
    T getItem();
    Generator<T> nextGenerator();
}


IntIteratorとIntIterableをGenericに変更。javaの標準クラスと同じ名前なので混乱しないように。

public interface Iterable<V> {
    Iterator<V> iterator();
}
public interface Iterator<V> {
    boolean hasNext();
    V next();
}


GeneratorをIteratorに変換する部分をクラス化。毎回実装しなくてよいように。

public class GeneratorIterator<V> implements Iterator<V> {
    private Generator<V> generator;
    public GeneratorIterator(Generator<V> rootGenerator) {
        this.generator = rootGenerator;
    }
    public boolean hasNext() {
        return generator != null;
    }
    public V next() {
        V item = generator.getItem();
        generator = generator.nextGenerator();
        return item;
    }
}


IntNodeをGeneric化。コード書く時にgetChildren()の要素を実クラスとして扱えるようにパラメータ増やしておく。
Genericの宣言って自己参照できるんだね。

import java.util.List;

public interface Node<V, N extends Node<V, N>> {
    V getValue();
    List<N> getChildren();
}


Nodeを扱う用のNodeGeneratorを実装。横型探索も出来るようにnextGenerator()を切り替えられるように修正。

import java.util.ArrayList;
import java.util.List;

public abstract class NodeGenerator<V, N extends Node<V, N>> implements Generator<V> {
    private final List<N> nodes;
    private final NodeGenerator<V, N> next;
    protected NodeGenerator(List<N> nodes, NodeGenerator<V, N> next) {
        if (nodes == null || nodes.isEmpty()) {
            throw new IllegalArgumentException("'nodes' is null or empty: " + nodes);
        }
        this.nodes = nodes;
        this.next = next;
    }
    public final V getItem() {
        return nodes.get(0).getValue();
    }
    public final Generator<V> nextGenerator() {
        List<N> children = nodes.get(0).getChildren();
        List<N> rest = nodes.subList(1, nodes.size());
        return doNextGenerator(rest, children, next);
        
    }
    /** それぞれ固有の処理順序になるようにGeneratorを生成して戻すべし */
    protected abstract Generator<V> doNextGenerator(List<N> rest, List<N> children, NodeGenerator<V, N> next);



    /** NodeGeneratorのチェーンを操作するためのクラス */
    private static abstract class NodeGeneratorBuilder<V, N extends Node<V, N>> {
        /**　nodes用のGeneratorを生成してgeneratorの前につける。nodesが空の場合generatorを戻す。 */
        NodeGenerator<V, N> getAddedToHead(List<N> nodes, NodeGenerator<V, N> generator) {
            if (nodes == null || nodes.isEmpty()) {
                return generator;
            }
            return newNodeGenerator(nodes, generator);
        }
        /**　nodes用のGeneratorを生成してgeneratorのチェーンの後ろにつける。
            nodesが空の場合generatorを戻す。generatorが空の場合nodesからNodeGeneratorを生成して戻す。 */
        NodeGenerator<V, N> getAddedToTail(List<N> nodes, NodeGenerator<V, N> generator) {
            if (nodes == null || nodes.isEmpty()) {
                return generator;
            }
            if (generator == null) {
                return newNodeGenerator(nodes, null);
            }
           return newNodeGenerator(generator.nodes,  getAddedToTail(nodes, generator.next));
        }
        /**　NodeGeneratorの実クラスを生成するべし。 */
        protected abstract NodeGenerator<V, N> newNodeGenerator(List<N> nodes, NodeGenerator<V, N> generator);
    }



   　/**　横型探索するNodeGenerator */
    private static class HorizontalNodeGenerator<V, N extends Node<V, N>> extends NodeGenerator<V, N> {
        NodeGeneratorBuilder<V, N> builder = new NodeGeneratorBuilder<V, N>() {
                protected NodeGenerator<V, N> newNodeGenerator(List<N> nodes, NodeGenerator<V, N> generator) {
                    return new HorizontalNodeGenerator<V, N>(nodes, generator);
                }};
        public HorizontalNodeGenerator(List<N> nodes, NodeGenerator<V, N> next) {
            super(nodes, next);
        }
        /** 同階層を先に処理。子要素は後回しにする */
        protected Generator<V> doNextGenerator(List<N> rest, List<N> children, NodeGenerator<V, N> next) {
            return builder.getAddedToHead(
                    rest,  
                    builder.getAddedToTail(children, next));
        }
    }
   　/**　縦型探索するNodeGenerator */
    private static class VerticalNodeGenerator<V, N extends Node<V, N>> extends NodeGenerator<V, N> {
        NodeGeneratorBuilder<V, N> builder = new NodeGeneratorBuilder<V, N>() {
                protected NodeGenerator<V, N> newNodeGenerator(List<N> nodes, NodeGenerator<V, N> generator) {
                    return new VerticalNodeGenerator<V, N>(nodes, generator);
                }};
        public VerticalNodeGenerator(List<N> nodes, NodeGenerator<V, N> next) {
            super(nodes, next);
        }
        /** 子要素→同階層(→上の階層)の順に処理 */
        protected Generator<V> doNextGenerator(List<N> rest, List<N> children, NodeGenerator<V, N> next) {
            return builder.getAddedToHead(
                    children, 
                    builder.getAddedToHead(rest, next));
        }
    }
   　/** トップnodeから横型探索NodeGeneratorを生成する */
    public static <V, N extends Node<V, N>> NodeGenerator<V, N> createHorizontalNodeGenerator(N node) {
        ArrayList<N> nodeAsList = new ArrayList<N>();
        nodeAsList.add(node);
        return new HorizontalNodeGenerator<V, N>(nodeAsList, null);
    }
   　/**　トップnodeから縦型探索NodeGeneratorを生成する */
    public static <V, N extends Node<V, N>> NodeGenerator<V, N> createVerticalNodeGenerator(N node) {
        ArrayList<N> nodeAsList = new ArrayList<N>();
        nodeAsList.add(node);
        return new VerticalNodeGenerator<V, N>(nodeAsList, null);
    }
}

使用例1。IntNodeを実装し直し

public class IntNode implements Node<Integer, IntNode>, Iterable<Integer> {
    private final int value;
    private final List<IntNode> children;

    public IntNode(int value, List<IntNode> children) {
        this.value = value;
        this.children = children;
    }
    public Integer getValue() {
        return value;
    }
    public List<IntNode> getChildren() {
        return children;
    }
    public Iterator<Integer> iterator() {
        return new GeneratorIterator<Integer>(NodeGenerator.createVerticalNodeGenerator(this));
    }
}

contains()も修正

    public boolean contains(Iterable<Integer> c, int value) {
        Iterator<Integer> it = c.iterator();
        while (it.hasNext()) {
            if (it.next().intValue() == value) {
                return true;
            }
        }
        return false;
    }

使用例2。ファイル階層をIterator化する

ディレクトリの中身をgetChildren()で戻すことでファイル階層をIteratorとして扱う。

public class FileNode implements Node<File, FileNode>, Iterable<File> {
    private final File file;

    public FileNode(File file) {
        if (file == null) {
            throw new IllegalArgumentException("file is null.");
        }
        this.file = file;
    }
    public File getValue() {
        return file;
    }
    public List<FileNode> getChildren() {
        if (!file.isDirectory()) {
            return null;
        }
        File[] files = file.listFiles();
        if (files == null) {
            return null;
        }
        List<FileNode> fileNodes = new ArrayList<FileNode>(files.length);
        for (File file: files) {
            fileNodes.add(new FileNode(file));
        }
        return fileNodes;
    }
    public Iterator<File> iterator() {
        return new GeneratorIterator<File>(NodeGenerator.createVerticalNodeGenerator(this));
    }
}


ファイル名で検索するメソッド

    public File find(Iterable<File> c, String filename) {
        Iterator<File> it = c.iterator();
        while (it.hasNext()) {
            File file = it.next();
            if (file.getName().equals(filename)) {
                return file;
            }
        }
        return null;
    }


使ってみる。「/Users/terazzo/Labs/workspace」以下の「FileNodeTest.java」というファイルを検索。

        FileNode sampleNode = new FileNode(new File("/Users/terazzo/Labs/workspace"));
        File file = find(sampleNode, "FileNodeTest.java");

使用例3。しりとりになっている単語リストを探す

単語リストの後ろに辞書から総当たり式で単語を付け加えたものをgetChildren()で返すことで単語の組み合わせをIteratorとして扱う。

public class WordListNode implements Node<List<String>, WordListNode> {
    /** 単語辞書は子供等に引き回しする */
    private String[] dict;
    /** 単語を並べたリスト */
    private final List<String> wordList;

    public WordListNode(String[] dict, List<String> wordList) {
        if (dict == null) {
            throw new IllegalArgumentException("dict is null.");
        }
        if (wordList == null) {
            throw new IllegalArgumentException("wordList is null.");
        }
        this.dict = dict;
        this.wordList = wordList;
    }
    public List<String> getValue() {
        return wordList;
    }
    /** 現在の単語リストの後ろに辞書内の各単語をくっ付けたもののリストを戻す */
    public List<WordListNode> getChildren() {
        List<WordListNode> children = new ArrayList<WordListNode>();
        for (String word : dict) {
            List<String> wordList = new ArrayList<String>(this.wordList);
            wordList.add(word);
            children.add(new WordListNode(dict, wordList));
        }
        return children;
    }
}


しりとり状態になってるかを判定するメソッド

    /** しりとりになっているかを判定。空のリストおよび1単語の場合もtrueを戻す。 */
    private boolean isValidAsShiritori(List<String> wordList) {
        if (wordList.isEmpty()) {
            return true;
        }
        String lastWord =  wordList.get(0);
        for (int index = 1, count = wordList.size(); index < count; index++) {
            String word = wordList.get(index);
            // 重複チェック
            if (wordList.indexOf(word) != index) {
                return false;
            }
            char lastLastChar = lastWord.charAt(lastWord.length() - 1);
            // 前の単語の最後の文字と次の単語の最初の文字の一致を調べる
            if (lastLastChar != word.charAt(0)) {
                return false;
            }
            lastWord = word;
        }
        return true;
    }


「こぶた」「たぬき」「きつね」「ねこ」「きつつき」「たこ」を使ってできる5単語のしりとりリストを出力

    public void testShiritori() {
        int wordSize = 5;
        String[] dict = new String[] {"こぶた", "たぬき", "きつね", "ねこ", "きつつき", "たこ"};
        WordListNode sampleNode = new WordListNode(dict, Collections.<String>emptyList());
        // 横型探索にしないと大変な目に。
        Iterator<List<String>> it =
            new GeneratorIterator<List<String>>(
                    NodeGenerator.createHorizontalNodeGenerator(sampleNode));
        while (it.hasNext()) {
            List<String>wordList = it.next();
            // 単語数が5を越えていれば終了
            if (wordList.size() > wordSize) break;
            if (wordList.size() == wordSize && isValidAsShiritori(wordList)) {
                System.out.println(wordList);
            }
        }
    }


出力結果

[こぶた, たぬき, きつつき, きつね, ねこ]
[たぬき, きつね, ねこ, こぶた, たこ]
[たぬき, きつつき, きつね, ねこ, こぶた]
[きつね, ねこ, こぶた, たぬき, きつつき]
[ねこ, こぶた, たぬき, きつつき, きつね]
[きつつき, きつね, ねこ, こぶた, たぬき]
[きつつき, きつね, ねこ, こぶた, たこ]
[たこ, こぶた, たぬき, きつね, ねこ]
[たこ, こぶた, たぬき, きつつき, きつね]

見ての通り何の工夫もしてないのでとても重いです。