派閥ジェネレータで木を作る場合でのコードをRubyで書いてみる。

JS版は後ろからループでたどるやり方で、処理的にはそれで十分なのだが、こんどは頭からたどるやり方を示す。こんどはオリジナルのmzp氏の版のように木構造を一旦作ってしまう方式でやってみる。webric部分はなし。

ただし、このプログラムでとるべき構造は二分木。また、再帰構造を使うので再帰処理で処理する。

二分木では、ノードはコンテンツ、長子、すぐ下の弟の3つ組で構成される。
インデントを作るときは、直系の祖先にそれぞれ弟がいるかどうかだけわかれば線をどう引くかがきまる。こういう場合は二分木だと処理がシンプルになると思う。

二分木のノード、eldestが長子、youngerがすぐ下の弟。それぞれいない場合はnilがはいる

class Node
  def initialize(content, eldest, younger)
    @content = content
    @eldest = eldest
    @younger = younger
  end
  attr :content
  attr :eldest
  attr :younger
end

stringのリストからツリーを作るmake_subtree

def make_subtree(level, lines, index)
  return nil, index if lines.size <= index
  line = lines[index]
  return make_subtree(level, lines, index + 1) if line.strip == ""
  line_level = get_level(line)
  return nil, index if line_level != level

  content = line[level, line.size]
  eldest, index = make_subtree(level + 1, lines, index + 1)
  younger, index = make_subtree(level, lines, index)
  node = Node.new(content, eldest, younger)
  return node, index
end

def get_level(line)
  level = 0
  line.each_byte do |ch|
    if ch == ?-
      level += 1
    else
      break
    end
  end
  level
end

引数のlevelやindexの初期値は0。ネストレベルの判定はJS版と同じになるようにした。

自分のコンテンツ、子、弟たちで再帰的にツリーを作るだけ。とりあえず空行はスキップしてる。
再帰処理は帰納法と同じように、入れ子の再帰呼び出しがすべて正しいとしてみなすように作るのは基本。nilが帰ればとまるのでレベル判定すれば子部分か弟部分かの境界の判別すら親はしなくてよくなる。つまり、子供ちょうだい→そのレベルにはいないよ→いないって入れとく、ってこと。

ツリーからテキスト生成。頭からたどるやりかた。

def habatsu(node, level, ancestors_has_younger)
  return "" if node == nil
  has_younger = (node.younger != nil)
  indent = make_indent(level, ancestors_has_younger, has_younger)
  result = indent + node.content + "\r\n"
  ancestors_has_younger_for_children = ancestors_has_younger.dup
  ancestors_has_younger_for_children << has_younger
  result += habatsu(node.eldest, level + 1, ancestors_has_younger_for_children)
  result += habatsu(node.younger, level, ancestors_has_younger)
  result
end

def make_indent(level, ancestors_has_younger, node_has_younger)
  indent = ""
  (1...level).each do |i|
    indent += if ancestors_has_younger[i] then "│　" else "　　" end
  end
  if level > 0
    indent += if node_has_younger then "├─" else "└─" end
  end
  indent
end

引数のancestors_has_youngerは祖先に弟がいるかどうか。levelはインデントレベル。ancestors_hass_younger.size == levelではあるけれど。

これも自分を書いて、子を書いて、弟を書くだけ。頭のインデント生成は、JS版と同じく、自分や祖先に弟がいるかどうかで切り替えるだけ。

mzp版は、子を含んでインデント化した配列を返し、それぞれに親側で毎回インデントをくわえていくようになってる。子の配列をイテレートしてインデントを加える作業を、入れ子ごと毎回やっている。あと、大きな欠点としては、ルートノードがなく木の配列になっている。このため、mapを二箇所で呼ぶことになっている（再帰関数に配列を渡すという手もあるけど、そうするとノードそのものの処理は配列ループ内でやることになってより変なコードになる）。

上のコードでは、入れ子のたびにインデント生成用の情報を集めて子に渡してやる、そうすることでノードごとにその処理時点でインデントが決まるため、親が子の装飾をする必要がなくなる。

lines = %{
aaa
-bbb
--ccc
---ddd
---eee
-fff
--ggg
hhh
-iii
--jjj
--kkk
}.split("\n")

puts lines.join("\r\n")
tree, index = make_subtree(0, lines, 0)
puts habatsu(tree, 0, [])

aaa
-bbb
--ccc
---ddd
---eee
-fff
--ggg
hhh
-iii
--jjj
--kkk
aaa
├─bbb
│　└─ccc
│　　　├─ddd
│　　　└─eee
└─fff
　　└─ggg
hhh
└─iii
　　├─jjj
　　└─kkk

JS版はなぜ後ろからまわしたか。

  • 実際のところ各行にインデントを入れかえているだけ
  • インデントを作る情報として、祖先に弟がいるかどうか、(だけ)が必要
    • つまり弟にあたるか、いないことがわかるか、までたどる必要がある
    • 構文上、最初の行→弟がいない場合最後までたどることになる。その情報を得るだけのために。
  • 逆に兄がいるかどうか、子がいるかどうかの情報は不要
    • いてもいなくてもインデントの形は一緒
  • →デフォルト弟がいないとして、逆からたどって弟がいる情報をためていけばいい