昨日の Rope もどきのコードに AVL 木のバランス崩れの条件判定に誤りがあったので、修正しておきました。それ以外に、2つの懸案事項が気になっていたので、今回、修正をおこないます。さらに、文字列比較をおこなえるように機能を追加します。
⇒ https://gist.github.com/tociyuki/10372481 avlrope.rb
懸案事項その1は、部分文字列を表す葉が、葉を作るごとに文字列オブジェクトから部分文字列をコピーしており、本来の Rope とは異なっている点です。本来の Rope なら文字列そのもののコピーをおこないません。近いやりかたとして、文字列オブジェクトを葉で共用し、葉ごとに文字列の中の部分文字列のとりだし位置を覚えておくことにします。
#@<ロープの葉クラス@>= class Leaf attr_reader :string, :offset, :length # 修正 def initialize(string, offset = 0, length = nil) # 修正 @string = string @offset = offset # 追加 @length = length || string.size - offset # 修正 end # 途中略 end
Leaf オブジェクトを生成している箇所を修正します。
class Rope EMPTY_LEAF = Leaf.new('', 0, 0) # 追加 def initialize(*a) case a.size when 0 @root = EMPTY_LEAF # 修正 when 1 # 途中略 else @root = Rope.new.concat(*a).root end end #@<ロープから部分ロープを切り出す@>= def slice(x, len = nil) #@< 切り出し文字位置を String クラス方式にする@> # ふるまいは string[i ... j] と同じ。ここで i と j は両方ともゼロ以上 return nil if i > j || i > @root.length return Rope.new(EMPTY_LEAF) if i == j # 修正 # 途中略 end #@<ロープの二分木から部分ロープを切り出す@>= def subrope(r, s, e) while r.node? return EMPTY_LEAF if s >= e # 修正 # 途中略 if s == 0 && e == r.length r else Leaf.new(r.string, s, e - s) # 修正 end end end
懸案事項その 2 は subrope を再帰呼び出しで記述していたことでした。ループ版へ書き直します。Ruby の break に式を与えると while の値にするというおもしろ機能を使うと、再帰呼び出し版の return を break へ置換できるので書き換えが楽です。
#@<ロープの二分木から部分ロープを切り出す@>= def subrope(r, s, e) k = [:node, r, s, e] while not k.empty? case k.first when :node _, r, s, e = k.shift(4) r = while true break EMPTY_LEAF if s >= e if r.leaf? break r if s == 0 && e == r.length break Leaf.new(r.string, s, e - s) end if e <= r.left.length r = r.left elsif s >= r.left.length s = s - r.left.length e = e - r.left.length r = r.right elsif s == 0 && e == r.length break r else k.unshift :right, r, e e = r.left.length r = r.left end end when :right _, r0, e = k.shift(3) k.unshift :node, r0.right, 0, e - r0.left.length, :graft, r when :graft _, x = k.shift(2) r = if r.length == 0 then x elsif x.length == 0 then r elsif x.depth == r.depth then Node.new(x, r) elsif x.depth > r.depth then append_right(x, r) else append_left(x, r) end end end r end
少しは文字列らしさをということで、each_char、大小比較、to_s を追加します。これらは、葉を順番にとりだす each_leaf を使います。深さ優先で、葉を yield させます。
2014年4月30日: ループを素直に利用して書き改めました。
#@<葉を順番にとりだす@>= def each_leaf path = [] r = @root while true while not r.leaf? path.push r r = r.left end yield r break if path.empty? r = path.pop.right end # k = [@root] # while not k.empty? # r = k.shift # if r.leaf? # yield r # else # k.unshift r.left, r.right # end # end self end
to_s は、葉から部分文字列をとりだして、すべて文字列オブジェクトへ連結します。
#@<文字列オブジェクトへ変換する@>= def to_s s = '' each_leaf {|r| s << r.string[r.offset, r.length] } s end
each_char は、葉の部分文字列中の文字を、順番に yield します。
#@<文字単位イテレータ@>= def each_char return to_enum(:each_char) if not block_given? each_leaf do |r| r.offset.upto(r.offset + r.length - 1){|i| yield r.string[i] } end self end
大小比較は、each_char を外部イテレータとして使って、文字単位の比較をおこないます。
include Comparable #@<大小比較をおこなう@>= def <=>(other) return 0 if equal?(other) x = self.each_char y = other.each_char c = 0 while c == 0 a = (begin x.next; rescue StopIteration; '' end) b = (begin y.next; rescue StopIteration; '' end) break if a.empty? and b.empty? c = a <=> b end c end
これ以外に、エイリアスを作っておいて、Ruby の文字列オブジェクトらしくふるまわせるようにします。
alias :+ append alias :[] slice