木構造に対してイテレータを作る

Rubyistなら知ってて当然みたいな内容かもしれませんが、自分で作るのはたぶん初めてのように思うのでメモ。本当はC++で同様のことがやりたいのだが、Rubyのほうがぱっとやるには早いのでとりあえずRubyにて。

状況、モチベーション

Rubyにしろ、C++にしろコンテナ(ArrayだったりMapだったりSetだったり)にはイテレータが付いている。これがあるおかげで僕らはその内部構造を特に意識せずにeachだったりBOOST_FOREACHみたいなことができる恩恵を受けている。が、自作したクラスや構造体に対してはそのような便利なイテレータは用意されていないので、自分で用意する必要がある。

今回は木構造に対してそれが必要になった。木を走査するには例えば幅優先探索や深さ優先探索のような基本的なアルゴリズムがあるので、それを使えばいいのだが、「ちょっとだけ」違う操作を木のそれぞれのノードに対してやりたい(例えばprintしたいとかノードの値をaccumulateしたいなどの要求が複数ある)場合、ほとんど同様のことを何回も書くはめになるので、バグが出てくるかもしれないしとりあえずかっこ悪い。そういう状況で木構造に対するイテレータが必要となった。

Rubyの場合について

Treeクラスにeachメソッドを生やしてやればよい。eachで必要になるそれぞれの変数はyieldで返してやればよい。yieldは慣れないとなかなか分かりにくいが、何か操作をやっていて、一回止めて途中から戻ってくる、みたいなイメージである。下の2冊の(どっちか|両方)を読んだりすれば分かってくるようになるんじゃないんでしょうか。

プログラミング言語 Ruby

初めてのRuby

class Tree
  attr_accessor :val, :level, :l, :r
  def initialize(val, level, l, r)
    @val = val; @level = level; @l = l; @r = r
  end
  def each
    stack = []
    stack.push self
    explored = []
    while !stack.empty?
      u = stack.shift
      if !explored.include?(u)
        explored.push u
        yield u
        stack.unshift u.l unless u.l.nil?
        stack.unshift u.r unless u.r.nil?
      end
    end
  end
end

tree = Tree.new("World", 0,
                Tree.new("Asia", 1,
                         Tree.new("Japan", 2, nil, nil),
                         Tree.new("China", 2, nil, nil)),
                Tree.new("Europe", 1, 
                         Tree.new("Dutch", 2, nil, nil),
                         Tree.new("Portugal", 2, nil, nil)))

tree.each {|node|
  puts "\s" * node.level + node.val
}

今回はスタックに積んでいくという形を取っているので深さ優先探索になりますが、キューに置いていくようにすれば(たぶん)幅優先探索での実行が簡単にできるようになると思います*1。

• 幅優先探索→深さ優先探索でした＞＜ - yasuhisa's blog

実行結果

ちゃんと深さ優先で木を走査できていることが確認できる。

/Users/yasuhisa/ruby% ruby traverse_tree.rb
World
 Europe
  Portugal
  Dutch
 Asia
  China
  Japan

C++の場合

Rubyの場合は簡単にイテレータを作ることができたのだが、C++で自分でイテレータをどうやって作ればいいのかよく分からない。調べてみるとBoostにそれっぽいのがあるらしい。

• letsboost::iterators

begin()はrootノードを返すようにするとして、end()の実装はどうすればいいかなぁ(適当にNULLでいいの?)。incrementするときにスタックから取り出してexpandする、というようなイメージ。

*1:最初「ん、再帰じゃないと深さ優先書けなくね?」と思ったのは内緒w