テキスト差分プログラムRuby版

昨日書いたテキスト差分プログラムRuby版がとりあえず動きました。

ソースは以下のような感じです。

class Diff
  def initialize(a, b)
    @path = Hash.new
    if a.length < b.length then
      @a = a
      @b = b
    else
      @a = b
      @b = a
    end
    
    # push dummy.
    @a.unshift(nil)
    @b.unshift(nil)
    @fp = Hash.new(-1)
    @lcs = onp()
  end

  def max(*arguments)
    max = nil
    arguments.each{ |arg|
      max = arg if max.nil? || max < arg
    }

    return max
  end

  def getm
    return @a.length - 1
  end

  def getn
    return @b.length - 1
  end
    
  def onp
    m = getm()
    n = getn()
    delta = n - m
    p = 0
    loop do
      (-p).upto(delta - 1){ |k|
        @fp[k] = snake(k)
      }

      (delta + p).downto(delta + 1){ |k|
        @fp[k] = snake(k)
      }

      k = delta
      y = snake(k)
      @fp[k] = y

      p+=1
      break if @fp[delta] == n
    end
    
    return @path[delta]
  end

  def snake(k)
    i = @fp[k - 1]  + 1
    j = @fp[k + 1]

    v = 0
    if i > j then
      @path[k] = @path[k - 1].dup if @path[k - 1]
      v = 1
    else
      @path[k] = @path[k + 1].dup if @path[k + 1]
      v = -1
    end
    @path[k] = [] if @path[k].nil?
    @path[k].push(v)
    
    y = max(i, j)
    x = y - k
    while (x < getm()  &&  y < getn()) && compare(@a[x+1], @b[y+1])
      x+=1
      y+=1
      @path[k].push(0)
    end
    
    return y
  end

  def compare(a, b)
    return a == b
  end

  def asText
    a = @a.dup
    a.shift
    b = @b.dup
    b.shift

    l = @lcs.dup
    l.shift
    diff = l.map{ |n|
      if n > 0 then
        "+\t" + " \t" + b.shift().to_s
      elsif n < 0 then
        "-\t" + a.shift().to_s
      else
        "=\t" + a.shift().to_s + "\t" + b.shift().to_s
      end
    }
    content = diff.join("\n")
    return content
  end
end

a = [1, 2, 4, 8, 16]
b = [1, 2, 3, 4, 5, 6, 7, 8]
onp = Diff.new(a, b)
puts onp.asText

昨日も書きましたが、動くまでにかなり苦労しました。

もとの理論をよく理解していないので、ひたすらJavaScriptのロジックを追うしかありません。最後はFireBugでJavaScriptを、NetBeansでRubyをステップ実行しながら、各所で変数の内容を比べるという荒業でなんとか動かしました。

また、配列で負のインデックスが発生する部分は、オフセットを付けたり専用の配列クラスを作成したりすればいいですが、面倒なのでハッシュで代用してしまいました。