Rope もどきの落ち穂拾い

昨日の 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