class Aio::Base::Toolkit::Myers
Public Class Methods
diff(a, b)
click to toggle source
# File lib/aio/base/toolkit/myers.rb, line 37 def self.diff(a, b) new(a, b).diff end
new(a, b)
click to toggle source
# File lib/aio/base/toolkit/myers.rb, line 41 def initialize(a, b) @a, @b = a, b end
Public Instance Methods
backtrack() { |x| ... }
click to toggle source
# File lib/aio/base/toolkit/myers.rb, line 78 def backtrack x, y = @a.size, @b.size shortest_edit.each_with_index.reverse_each do |v, d| k = x - y if k == -d or (k != d and v[k-1] < v[k+1]) prev_k = k + 1 else prev_k = k - 1 end prev_x = v[prev_k] prev_y = prev_x - prev_k while x > prev_x and y > prev_y yield x - 1, y - 1, x, y x, y = x - 1, y - 1 end yield prev_x, prev_y, x, y if d > 0 x, y = prev_x, prev_y end end
diff()
click to toggle source
# File lib/aio/base/toolkit/myers.rb, line 104 def diff diff = [] backtrack do |prev_x, prev_y, x, y| a_line, b_line = @a[prev_x], @b[prev_y] if x == prev_x diff.unshift(Diff::Edit.new(:ins, nil, b_line)) elsif y == prev_y diff.unshift(Diff::Edit.new(:del, a_line, nil)) else diff.unshift(Diff::Edit.new(:eql, a_line, b_line)) end end # 此时得到的是按顺序排列的数组 diff end
shortest_edit()
click to toggle source
# File lib/aio/base/toolkit/myers.rb, line 45 def shortest_edit n, m = @a.size, @b.size max = n + m v = ::Array.new(2 * max + 1) v[1] = 0 trace = [] (0..max).step do |d| trace << v.clone (-d..d).step(2) do |k| if k == -d or (k != d and v[k-1] < v[k+1]) x = v[k+1] else x = v[k-1] + 1 end y = x - k # while x < n and y < m and @a[x].text == @b[y].text while x < n and y < m and !@a[x].diff? and !@b[y].diff? x, y = x + 1, y + 1 end v[k] = x return trace if x >= n and y >= m end end end