Boost.Variant そのよん 二分木で計算

C++ boost

http://d.hatena.ne.jp/janus_wel/20101009/1286612190 の続き。 boost::recursive_wrapper<> を使うと何がうれしいのかというのを実際に確かめてみようという段。

とはいうもののいい例を思いつかなかったので tutorial の例がすばらしすぎたので http://www.boost.org/doc/libs/1_44_0/doc/html/variant/tutorial.html#variant.tutorial.recursive.recursive-wrapper を写経 & いじって遊んだだけというアレ具合。

ちょっと長い。

とりあえず一番のキモは以下の場所。

template <typename Op> struct binary_op;

typedef boost::variant<
    double,
    boost::recursive_wrapper<binary_op<add> >,
    boost::recursive_wrapper<binary_op<sub> >,
    boost::recursive_wrapper<binary_op<mul> >,
    boost::recursive_wrapper<binary_op<div> >
        > expr;

template <typename Op>
struct binary_op {
    expr left;
    expr right;

    binary_op(const expr& lhs, const expr& rhs)
        : left(lhs), right(rhs) {}
};

まずこれ別に binary_op<> を前方宣言しないでダラダラと書いてもいいんだけど boost::variant でまとめる型が 5 つあって長いので typedef したいので前方宣言、 typedef 、定義という流れになってる。

で、その typedef の行、 boost::variant でいくつかの型をまとめてるときに binary_op<> に boost::recursive_wrapper<> を適用してるのが point 。これないと http://d.hatena.ne.jp/janus_wel/20101009/1286612190 で説明した言語仕様にひっかかる。

ちなみにこの data structure が何を表すかというと http://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%9C%A8#.E7.AE.97.E8.A1.93.E5.BC.8F.E3.81.AE.E6.A7.8B.E6.96.87.E6.9C.A8 で説明されている四則演算を二分木に落としたもの。 natural に実装していて驚いたのでいじったわけなんだけど。

次に、というか同じくらい重要なんだけどこの data structure を走査するために left や right を辿っていく、ということはできない。なぜかというと boost::recursive_wrapper<> で wrap されているわけで透過的に binary_op<> 型として扱えないからだね。まぁ access する方法もあるんだけどそんなに便利じゃないのでそこは through する。

それじゃあ意味ないじゃんというのはその通りなんだけど Boost.Variant は visitor pattern が適用できるのでそれを使って access しなさいという方向なわけだ -> http://d.hatena.ne.jp/janus_wel/20101004/1286201416 。

というわけで以下のように visitor class とそれを適用するための helper function を定義している。

// evaluate data structure recursively
struct evaluator : public boost::static_visitor<double> {
    double operator()(const double& value) const {
        return value;
    }

    double operator()(const op_add& i) const {
        return
              boost::apply_visitor(evaluator(), i.left)
            + boost::apply_visitor(evaluator(), i.right);
    }

    /* snip */
};

// for convenience
inline double calc(const expr& e) {
    return boost::apply_visitor(evaluator(), e);
}

最初の operator() 関数と他 4 つで違いがあって最初だけ数を数として返せ、その他はそれぞれで left と right を引数にして四則演算した結果を返せ、ってそのままだな。まぁ最初がないと二分木をどんどんくだっていって葉、つまり数に辿りついたときに評価するための rule がないのでうまくいかないというだけなんだけど。

ちなみに evaluator というのは評価器というくらいの意味合いでつけた名前なんだけど、四則演算を評価していって結果を出せ、つまり計算しろということね。

とまぁこのふたつがわかっていればいい感じ。他の細かいところは好みというか Boost.Variant に限ったことではないので好きなように書けばいいかな。