class DocDiff::Diff
Public Class Methods
algorithm(algorithm)
click to toggle source
# File lib/docdiff/diff.rb, line 144 def Diff.algorithm(algorithm) case algorithm when :shortestpath return ShortestPath when :contours return Contours when :speculative return Speculative else raise ArgumentError.new("unknown diff algorithm: #{algorithm}") end end
new(a, b)
click to toggle source
# File lib/docdiff/diff.rb, line 55 def initialize(a, b) @original_a = a @original_b = b count_a = {} count_a.default = 0 a.each {|e| count_a[e] += 1} count_b = {} count_b.default = 0 b.each {|e| count_b[e] += 1} beg_a = 0 end_a = a.length beg_b = 0 end_b = b.length @prefix_lcs = [] @suffix_lcs = [] flag = true while flag flag = false while beg_a < end_a && beg_b < end_b && a[beg_a].eql?(b[beg_b]) @prefix_lcs << [beg_a, beg_b] count_a[a[beg_a]] -= 1 count_b[b[beg_b]] -= 1 beg_a += 1 beg_b += 1 flag = true end while beg_a < end_a && beg_b < end_b && a[end_a - 1].eql?(b[end_b - 1]) @suffix_lcs << [end_a - 1, end_b - 1] count_a[a[end_a - 1]] -= 1 count_b[b[end_b - 1]] -= 1 end_a -= 1 end_b -= 1 flag = true end while beg_a < end_a && count_b[a[beg_a]] == 0 count_a[a[beg_a]] -= 1 beg_a += 1 flag = true end while beg_b < end_b && count_a[b[beg_b]] == 0 count_b[b[beg_b]] -= 1 beg_b += 1 flag = true end while beg_a < end_a && count_b[a[end_a - 1]] == 0 count_a[a[end_a - 1]] -= 1 end_a -= 1 flag = true end while beg_b < end_b && count_a[b[end_b - 1]] == 0 count_b[b[end_b - 1]] -= 1 end_b -= 1 flag = true end end @alphabet = Alphabet.new @a = [] @revert_index_a = [] (beg_a...end_a).each {|i| if count_b[a[i]] != 0 @a << @alphabet.add(a[i]) @revert_index_a << i end } @b = [] @revert_index_b = [] (beg_b...end_b).each {|i| if count_a[b[i]] != 0 @b << @alphabet.add(b[i]) @revert_index_b << i end } end
rcsdiff(a, b)
click to toggle source
# File lib/docdiff/diff/rcsdiff.rb, line 3 def Diff.rcsdiff(a, b) al = [] a.each_line {|l| al << l} bl = [] b.each_line {|l| bl << l} return Diff.new(al, bl).ses.rcsdiff end
unidiff(a, b, algorithm=nil)
click to toggle source
# File lib/docdiff/diff/unidiff.rb, line 3 def Diff.unidiff(a, b, algorithm=nil) al = [] a.each_line {|l| al << l} bl = [] b.each_line {|l| bl << l} return Diff.new(al, bl).ses(algorithm).unidiff end
Public Instance Methods
lcs(algorithm=:speculative)
click to toggle source
# File lib/docdiff/diff.rb, line 157 def lcs(algorithm=:speculative) # longest common subsequence klass = Diff.algorithm(algorithm) reduced_lcs = klass.new(@a, @b).lcs lcs = Subsequence.new @prefix_lcs.each {|i, j| lcs.add i, j} reduced_lcs.each {|i, j, l| l.times {|k| lcs.add @revert_index_a[i+k], @revert_index_b[j+k] } } @suffix_lcs.reverse_each {|i, j| lcs.add i, j} return lcs end
ses(algorithm=nil)
click to toggle source
# File lib/docdiff/diff.rb, line 173 def ses(algorithm=nil) # shortest edit script algorithm ||= :speculative lcs = lcs(algorithm) ses = EditScript.new i0 = j0 = 0 lcs.each {|i, j, l| ses.del @original_a[i0, i - i0] if i0 < i ses.add @original_b[j0, j - j0] if j0 < j ses.common @original_a[i, l], @original_b[j, l] i0 = i + l j0 = j + l } i = @original_a.length j = @original_b.length ses.del @original_a[i0, i - i0] if i0 < i ses.add @original_b[j0, j - j0] if j0 < j return ses end