JavaでTree Iteratorいろいろ

前回ラーニングしたTree Iteratorで、過去に書いたツリー構造を外部イテレータにするコードを書き直した。
こりゃシンプル。

黒歴史:

• ツリー構造用の外部/内部イテレータの実装 - terazzoの日記
• http://d.hatena.ne.jp/terazzo/20090308/1236526403

ノードに数値付のツリー構造

package sample.tree;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

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;
    }
    /** 外部イテレータを戻す(Tree Iterator版) */
    public Iterator<Integer> iterator() {
        final LinkedList<IntNode> stack = new LinkedList<IntNode>();
        stack.push(this);
        return new Iterator<Integer>() {
            @Override
            public boolean hasNext() {
                return !stack.isEmpty();
            }

            @Override
            public Integer next() {
                IntNode node = stack.pop();
                if (node.children != null) {
                    // 子ノードを追加(深さ優先)
                    int count = node.children.size();
                    while (count-- > 0) {
                        stack.push(node.children.get(count));
                    }
               }
                return node.value;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
}

テスツ:

package sample.tree;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;

import java.util.Arrays;
import java.util.Iterator;

import org.junit.Test;

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

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

ファイル階層をIterator化する

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

package sample.tree;

import java.io.File;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class FileNode {
    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;
    }
    /** 外部イテレータを戻す(Tree Iterator版) */
    public Iterator<File> iterator() {
        final LinkedList<FileNode> stack = new LinkedList<FileNode>();
        stack.addLast(this);
        return new Iterator<File>() {
            @Override
            public boolean hasNext() {
                return !stack.isEmpty();
            }

            @Override
            public File next() {
                FileNode node = stack.pop();
                List<FileNode> children = node.getChildren();
                if (children != null) {
                    // 子ノードを追加(幅優先)
                    for (FileNode child : children) {
                        stack.addLast(child);
                    }
               }
                return node.file;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
}

テスツ。
ファイル名に合致するものが存在すれば戻すコード。
プロジェクトディレクトリ下のソースコード自体を見つけてみる。

package sample.tree;

import static org.junit.Assert.assertNotNull;

import java.io.File;
import java.util.Iterator;

import org.junit.Test;

public class FileNodeTest {
    // ファイル名に一致すればそのFileを戻す。
    public File find(FileNode c, String filename) {
        Iterator<File> it = c.iterator();
        while (it.hasNext()) {
            File file = it.next();
            if (file.getName().equals(filename)) {
                return file;
            }
        }
        return null;
    }
    @Test
    public void testIterator() {
        FileNode sampleNode = new FileNode(new File(".")); // プロジェクトディレクトリ下
        File file = find(sampleNode, "FileNodeTest.java");
        assertNotNull(file);
    }
}

しりとりになっている単語リストを探す

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

package sample.tree;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class 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;
    }
    /** 外部イテレータを戻す(Tree Iterator版) */
    public Iterator<List<String>> iterator() {
        final LinkedList<WordListNode> stack = new LinkedList<WordListNode>();
        stack.addLast(this);
        return new Iterator<List<String>>() {
            @Override
            public boolean hasNext() {
                return !stack.isEmpty();
            }

            @Override
            public List<String> next() {
                WordListNode node = stack.removeFirst();
                List<WordListNode> children = node.getChildren();
                if (children != null) {
                    // 子ノードを追加(幅優先にしないと大変な目に。)
                    for (WordListNode child : children) {
                        stack.addLast(child);
                    }
               }
               return node.wordList;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
}

テスツ:

package sample.tree;

import java.util.Collections;
import java.util.Iterator;
import java.util.List;

import org.junit.Test;

public class WordListNodeTest {

    /** しりとりになっているかを判定。空のリストおよび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;
    }

    @Test
    public void testShiritori() {
        int wordSize = 5;
        String[] dict = new String[] {"こぶた", "たぬき", "きつね", "ねこ", "きつつき", "たこ"};
        WordListNode sampleNode = new WordListNode(dict, Collections.<String>emptyList());
        Iterator<List<String>> it = sampleNode.iterator();
        while (it.hasNext()) {
            List<String>wordList = it.next();
            // 単語数が5を越えていれば終了
            if (wordList.size() > wordSize) break;
            if (wordList.size() == wordSize && isValidAsShiritori(wordList)) {
                System.out.println(wordList);
            }
        }
    }
}

出力:

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