Class: Aio::Base::Toolkit::Myers

Inherits:
Object
  • Object
show all
Defined in:
lib/aio/base/toolkit/myers.rb

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(a, b) ⇒ Myers

Returns a new instance of Myers.



41
42
43
 
# File 'lib/aio/base/toolkit/myers.rb', line 41

def initialize(a, b)
  @a, @b = a, b
end

Class Method Details

.diff(a, b) ⇒ Object 



37
38
39
 
# File 'lib/aio/base/toolkit/myers.rb', line 37

def self.diff(a, b)
  new(a, b).diff
end

Instance Method Details

#backtrack ⇒ Object 



78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
 
# 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 ⇒ Object 



104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
# 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 ⇒ Object 



45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
# 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