デザインパターンを覚えたい (Visitor)

Visitorパターン

データ構造上を探索しながら処理をしていくパターン。データとなるElementクラスとそれに処理を行うVisitorクラスを用意し、相互にメソッドを呼び合うことでデータの網羅的な処理を行う。
ポイントは

• データ構造とそれに対する処理を分離することができる

ところ。後で処理を追加する場合が容易になる一方で、新しいデータを追加したり修正するのは苦手。相互に呼び合うといってるけど、実際の処理はVisitor側でまとめて行う (シーケンス図みるとわかる)。

実装。今日はJavaで。題材はVisitorということでダイクストラ法にする。
http://dl.dropbox.com/u/7810000/code/design_pattern/visitor.zip

実行結果は以下の通り。
なお、テストで用いた経路図は以下のサイトのものを利用してます。
http://www.deqnotes.net/acmicpc/dijkstra/

$ ant test
Buildfile: /Users/xxx/tmp/visitor/build.xml

build:

test:
[java] nodeId=0 : cost=0
[java] nodeId=1 : cost=5
[java] nodeId=2 : cost=4
[java] nodeId=3 : cost=2
[java] nodeId=4 : cost=6
[java] nodeId=5 : cost=10

BUILD SUCCESSFUL
Total time: 0 seconds

# 多分数値はあってるはず

実装のポイントはNodeクラスとDijkstraVisitorクラスの以下の部分で相互に呼び合ってるところ

public class Node implements Element {

    /* 中略 */

    // Visitorから呼ばれる部分
    public void accept(Visitor v) {
        v.visit(this);
    }
}

public class DijkstraVisitor extends Visitor {

    /* 中略 */

    protected void visit(Node node) {
        if (!costMap.containsKey(node.getNodeId())) {
            throw new NodeNotFoundException();
        }

        // 現在のノードのコストを取得
        int baseCost = costMap.get(node.getNodeId());

        // 隣接ノードについてコスト更新
        Iterator<Edge> edgeIter = node.getEdgeIterator();
        while (edgeIter.hasNext()) {
            Edge edge = edgeIter.next();
            Node distNode = edge.getDistNode();

            // コスト更新
            if (!costMap.containsKey(distNode.getNodeId())) {
                costMap.put(distNode.getNodeId(), baseCost + edge.getCost());
                nodeQueue.offer(distNode);
            } else {
                int curCost = costMap.get(distNode.getNodeId());
                if (curCost > baseCost + edge.getCost()) {
                    costMap.put(distNode.getNodeId(), baseCost + edge.getCost());
                    nodeQueue.offer(distNode);
                }
            }
        }

        Node nextNode;
        while ((nextNode = nodeQueue.pollFirst()) != null) {
            // かなり無理やりだけどデータの方のacceptを呼ぶ
            nextNode.accept(this);
        } 
    }
}

コメントにも書いてあるけどかなり無理やり。多分Visitorパターンって深さ優先探索に向いてる形な気がするけど、ダイクストラ法だとどちらかというと幅優先探索なのでコードがきれいにまとめられなかったのかな。
# Visitorパターンの使い方が間違ってたりして、うーむ