読者です 読者をやめる 読者になる 読者になる

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

Ruby C++

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

状況、モチベーション

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

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

Rubyの場合について

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

プログラミング言語 Ruby

  • 作者: まつもとゆきひろ,David Flanagan,卜部昌平(監訳),長尾高弘
  • 出版社/メーカー: オライリージャパン
  • 発売日: 2009/01/26
  • メディア: 大型本
  • 購入: 21人 クリック: 356回
  • この商品を含むブログ (129件) を見る
初めての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

実行結果

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

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

C++の場合

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

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

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