Class: Test::Diff::SequenceMatcher

Inherits:
Object
  • Object
show all
Defined in:
lib/test-unit-ext/diff.rb

Instance Method Summary collapse

Constructor Details

#initialize(from, to) ⇒ SequenceMatcher

Returns a new instance of SequenceMatcher.



6
7
8
9
10
 
# File 'lib/test-unit-ext/diff.rb', line 6

def initialize(from, to)
  @from = from
  @to = to
  update_to_indexes
end

Instance Method Details

#longest_match(from_start, from_end, to_start, to_end) ⇒ Object 



12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
# File 'lib/test-unit-ext/diff.rb', line 12

def longest_match(from_start, from_end, to_start, to_end)
  best_from, best_to, best_size = from_start, to_start, 0
  lengths = {}
  from_start.upto(from_end) do |i|
    new_lengths = {}
    (@to_indexes[@from[i]] || []).each do |j|
      next if j < to_start
      break if j >= to_end
      k = new_lengths[j] = (lengths[j - 1] || 0) + 1
      if k > best_size
        best_from, best_to, best_size = i - k + 1, j - k + 1, k
      end
    end
    lengths = new_lengths
  end

  while best_from > from_start and best_to > to_start and
      @from[best_from - 1] == @to[best_to - 1]
    best_from -= 1
    best_to -= 1
    best_size += 1
  end

  while best_from + best_size <= from_end and
      best_to + best_size <= to_end and
      @from[best_from + best_size] == @to[best_to + best_size]
    best_size += 1
  end

  [best_from, best_to, best_size]
end

#matching_blocks ⇒ Object 



44
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
77
78
79
80
81
82
83
84
85
 
# File 'lib/test-unit-ext/diff.rb', line 44

def matching_blocks
  queue = [[0, @from.size - 1, 0, @to.size - 1]]
  blocks = []
  until queue.empty?
    from_start, from_end, to_start, to_end = queue.pop
    match_info = longest_match(from_start, from_end, to_start, to_end)
    match_from_index, match_to_index, size = match_info
    unless size.zero?
      blocks << match_info
      if from_start < match_from_index and to_start < match_to_index
        queue.push([from_start, match_from_index,
                    to_start, match_to_index])
      end
      if match_from_index + size < from_end and
          match_to_index + size < to_end
        queue.push([match_from_index + size, from_end,
                    match_to_index + size, to_end])
      end
    end
  end

  non_adjacent = []
  prev_from_index = prev_to_index = prev_size = 0
  blocks.sort.each do |from_index, to_index, size|
    if prev_from_index + prev_size == from_index and
        prev_to_index + prev_size == to_index
      prev_size += size
    else
      unless prev_size.zero?
        non_adjacent << [prev_from_index, prev_to_index, prev_size]
      end
      prev_from_index, prev_to_index, prev_size =
        from_index, to_index, size
    end
  end
  unless prev_size.zero?
    non_adjacent << [prev_from_index, prev_to_index, prev_size]
  end

  non_adjacent << [@from.size, @to.size, 0]
  non_adjacent
end

#operations ⇒ Object 



87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
# File 'lib/test-unit-ext/diff.rb', line 87

def operations
  from_index = to_index = 0
  operations = []
  matching_blocks.each do |match_from_index, match_to_index, size|
    tag = nil
    if from_index < match_from_index and to_index < match_to_index
      tag = :replace
    elsif from_index < match_from_index
      tag = :delete
    elsif to_index < match_to_index
      tag = :insert
    end

    if tag
      operations << [tag,
                     from_index, match_from_index,
                     to_index, match_to_index]
    end

    from_index, to_index = match_from_index + size, match_to_index + size
    if size > 0
      operations << [:equal,
                     match_from_index, from_index,
                     match_to_index, to_index]
    end
  end

  operations
end