class DocDiff::Diff::ShortestPath
Public Class Methods
new(a, b)
click to toggle source
# File lib/docdiff/diff/shortestpath.rb, line 12 def initialize(a, b) if a.length > b.length @a = b @b = a @exchanged = true else @a = a @b = b @exchanged = false end @m = @a.length @n = @b.length end
Public Instance Methods
lcs(lcs=Subsequence.new)
click to toggle source
# File lib/docdiff/diff/shortestpath.rb, line 26 def lcs(lcs=Subsequence.new) d = @n - @m fp = Array.new(@n+1+@m+1+1, -1) fp_base = -(@m+1) path = Array.new(fp.length) p = -1 begin p += 1 (-p).upto(d-1) {|k| a = fp[fp_base+k-1]+1 b = fp[fp_base+k+1] if a < b y = fp[fp_base+k] = snake(k, b) path[fp_base+k] = path[fp_base+k+1] path[fp_base+k] = [y - k, y, y - b, path[fp_base+k]] if b < y else y = fp[fp_base+k] = snake(k, a) path[fp_base+k] = path[fp_base+k-1] path[fp_base+k] = [y - k, y, y - a, path[fp_base+k]] if a < y end } (d+p).downto(d+1) {|k| a = fp[fp_base+k-1]+1 b = fp[fp_base+k+1] if a < b y = fp[fp_base+k] = snake(k, b) path[fp_base+k] = path[fp_base+k+1] path[fp_base+k] = [y - k, y, y - b, path[fp_base+k]] if b < y else y = fp[fp_base+k] = snake(k, a) path[fp_base+k] = path[fp_base+k-1] path[fp_base+k] = [y - k, y, y - a, path[fp_base+k]] if a < y end } a = fp[fp_base+d-1]+1 b = fp[fp_base+d+1] if a < b y = fp[fp_base+d] = snake(d, b) path[fp_base+d] = path[fp_base+d+1] path[fp_base+d] = [y - d, y, y - b, path[fp_base+d]] if b < y else y = fp[fp_base+d] = snake(d, a) path[fp_base+d] = path[fp_base+d-1] path[fp_base+d] = [y - d, y, y - a, path[fp_base+d]] if a < y end end until fp[fp_base+d] == @n shortest_path = path[fp_base+d] list = [] while shortest_path x, y, l, shortest_path = shortest_path list << [x - l, y - l, l] end if @exchanged list.collect {|xyl| tmp = xyl[0]; xyl[0] = xyl[1]; xyl[1] = tmp} end list.reverse_each {|xyl| lcs.add(*xyl)} return lcs end
snake(k, y)
click to toggle source
# File lib/docdiff/diff/shortestpath.rb, line 85 def snake(k, y) x = y - k while x < @m && y < @n && @a[x] == @b[y] x += 1 y += 1 end return y end