[ruby-list:39693] Re: [ANN] Algorithm-Diff 0.1 released

はじめまして。野分と申します。

RAAにあるMoonWolfさんのalgorithm-diffをちょっとだけ使いやすくするラッパー
クラスを作成しました。
また、独自の機能としてオリジナルのデータの位置を基準とした差分を吐き出す
機能、およびdiffの結合と一部diffの無効化機能を追加しています。

Lars Christensenさんのdiffの改造に行き詰まり、自分でdiffのの実装しなくちゃ
いけないかな……と肚をくくっていたところなので、大変助かりました。

diff同士の結合と一部diffの無効化は、実際に差分を復元してdiffしなおすイカ
サマ実装です。色々と微妙な条件判定が必要で、実装しきれませんでした。
何とかならないかな……

_______________________________________________________________________
# 使い方

require 'simple_diff'

original = '0123456789'.split(//)
result = '0c123d456789'.split(//)

# diffオブジェクトの作成
diff = Algorithm::SimpleDiff.new( original, result )

# まずはdiffモジュールの機能を使う場合
p 'sdiff', diff.sdiff, 'sdiff'
p 'diff', diff.diff, 'diff'
diff.sdiff.each {|x, a, b|
  puts "#{a}\t#{x}\t#{b}"
}

# イベントベースでの使用
def diff.discard_a(i, j, v)
  print "#{i} #{j} > ", v, "\n"
end
def diff.discard_b(i, j, v)
  print "#{i} #{j} < ", v, "\n"
end
def diff.match(i, j, v)
  print "#{i} #{j} = ", v, "\n"
end
diff.traverse

#イベント用のオブジェクトを作ってもＯＫ
o = Object.new
def o.discard_a(i, j, v)
  print "#{i} #{j} > ", v, "\n"
end
def o.discard_b(i, j, v)
  print "#{i} #{j} < ", v, "\n"
end
def o.match(i, j, v)
  print "#{i} #{j} = ", v, "\n"
end
diff.traverse_processor = o
diff.traverse
# ここまでがdiffモジュールの機能を使用した場合

# ここからは独自の機能
# オリジナルデータを基準とした差分を出力する
diff_result = diff.original_base_diff
p diff_result

# 結果を反転する
reverse_diff = diff_result.reverse
p reverse_diff

# 2つの結果を結合する
reverse_diff << diff_result
p reverse_diff

# diffの結果を一部無効にする
original = '0123456789'.split(//)
result   = '0abc123def456789'.split(//)
ignore   = '0ab123ef456789'.split(//)
d1 = Algorithm::SimpleDiff.new( original, result ).original_base_diff
d2 = Algorithm::SimpleDiff.new( original, ignore ).original_base_diff
p d1, d2, d1.ignore( d2 )

_______________________________________________________________________
# (c)野分<[e-mail]>
# License Ruby's

require 'algorithm/diff'
require 'diff'
require 'singleton'

module Algorithm
  class SimpleDiff
    attr_reader( :original, :modification )
    attr_accessor( :traverse_processor )
    def initialize( original, modification )
      @traverse_processor = self
      @ori = original
      @mod = modification
      @diff_count, @snake, @detail = Diff.ond( @ori, @mod )
      @match_path = Diff.solve( @ori, @mod, @diff_count, @snake, @detail )
    end
    ############################################
    # トラバース処理（イベント駆動のdiff処理）
    def traverse
      Algorithm::Diff.traverse( @ori, @mod, @match_path, @traverse_processor)
    end
    # 以下はオーバーライドして定義のこと
    def discard_a( original_pos, modification_pos, token )
      # originalにのみ現れるtokenの処理
    end
    def discard_b( original_pos, modification_pos, token )
      # modificationにのみ現れるtokenの処理
    end
    def match( original_pos, modification_pos, token )
      # 両方に現れるtokenの処理
    end
    ############################################
    # 結果
    def sdiff; Diff.sdiff( @ori, @mod, @match_path ) end
    def diff; Diff.diff( @ori, @mod, @match_path ) end
    def original_base_diff
      obj = TraverseProcessorForOriginalBaseDiff.new
      Algorithm::Diff.traverse( @ori, @mod, @match_path, obj )
      OriginalBaseResult.new( obj.result )
    end
  private
    class TraverseProcessorForOriginalBaseDiff
      def initialize; @result = []; @index = 0 end
      def result; @result end
      def discard_a(i, j, v)
        if @joint
          @result[-1][1] << v
        else
          @result << [@index, [v], []]
          @joint = true
        end
        @index += 1
      end
      def discard_b(i, j, v)
        if @joint
          @result[-1][2] << v
        else
          @result << [@index, [], [v]]
          @joint = true
        end
      end
      def match(i, j, v)
        @index += 1
        @joint = false
      end
    end
    #########################################################################
    # Diffの結果を保持するオブジェクト
    #   各要素の内容は次の通り
    #   基準は全てoriginal
    #   [操作する部分のoriginalに対する位置の先頭, 前の内容, 後の内容]
    class OriginalBaseResult
      class NoChange
        include Singleton
        def inspect; '*' end
      end
      def initialize( result_array=[] )
        @data = result_array
        unique!
      end
      def inspect; @data.inspect end
      def size; @data.size end
      def empty?; @data.empty? end
      def []( var ); @data[var] end
      def patch( original )
        result = []
        index = 0
        @data.each do | i |
          result.concat( original[index...i[0]] )
          result.concat( i[2] )
          index = i[0] + i[1].size
        end
        result.concat(original[index...original.size]) if index<original.size
        result
      end
      def reverse
        result = []
        gap = 0
        @data.each do | i |
          result << [i[0] + gap, [], []]
          i[1].each do | j | result[-1][2] << j end
          i[2].each do | j | result[-1][1] << j end
          gap += i[2].size - i[1].size
        end
        unique!
        OriginalBaseResult.new( result )
      end
      def <<( addition ) #手抜き実装
        if @data.empty?
          @data = addition.data
        else
          o = Array.new( @data[-1][0]+@data[-1][1].size, NoChange.instance )
          @data.each do | i | o[i[0], i[1].size] = i[1] end
          t = self.patch( o )
          addition.data.each do | i | t[i[0], i[1].size] = i[1] end
          o = self.reverse.patch( t )
          t = addition.patch( t )
          @data = SimpleDiff.new( o, t ).original_base_diff.data
        end
        unique!
        return self
      end
      def ignore( del ) #手抜き実装
        return self if @data.empty?
        o = Array.new( @data[-1][0]+@data[-1][1].size, NoChange.instance )
        @data.each do | i | o[i[0], i[1].size] = i[1] end
        t = self.patch( o )
        gap = 0
        del.data.each do | i |
          o[i[0], i[1].size] = Array.new( i[1].size, NoChange.instance )
          t[i[0]+gap, i[2].size] = Array.new( i[1].size, NoChange.instance )
          gap += i[2].size - i[1].size
        end
        if o.size < t.size
          o.concat( Array.new( t.size-o.size, NoChange.instance ) )
        elsif t.size < o.size
          t.concat( Array.new( o.size-t.size, NoChange.instance ) )
        end
        @data = SimpleDiff.new( o, t ).original_base_diff.data
        unique!
        return self
      end
    protected
      def data; @data end
    private
      def unique!
        result = []
        index = 0
        @data.each do | i |
          index = i[0]
          t1 = []; t2 = [];
          i[1].each do | j |
            t1 << (j ? j.clone : j) if j.class != NoChange
          end
          i[2].each do | j |
            t2 << (j ? j.clone : j) if j.class != NoChange
          end
          t1.delete_if do | x | (x.class == NoChange) or (not x) end
          t2.delete_if do | x | (x.class == NoChange) or (not x) end
          result << [index, t1, t2] unless t1.empty? and t2.empty?
        end
        @data = result
      end
    end
  end
end