class Test::Unit::Diff::SequenceMatcher
Public Class Methods
new(from, to, &junk_predicate)
click to toggle source
# File test-unit-3.6.1/lib/test/unit/diff.rb, line 13 def initialize(from, to, &junk_predicate) @from = from @to = to @junk_predicate = junk_predicate update_to_indexes end
Public Instance Methods
blocks()
click to toggle source
# File test-unit-3.6.1/lib/test/unit/diff.rb, line 34 def blocks @blocks ||= compute_blocks end
grouped_operations(context_size=nil)
click to toggle source
# File test-unit-3.6.1/lib/test/unit/diff.rb, line 42 def grouped_operations(context_size=nil) context_size ||= 3 _operations = operations.dup _operations = [[:equal, 0, 0, 0, 0]] if _operations.empty? expand_edge_equal_operations!(_operations, context_size) group_window = context_size * 2 groups = [] group = [] _operations.each do |tag, from_start, from_end, to_start, to_end| if tag == :equal and from_end - from_start > group_window group << [tag, from_start, [from_end, from_start + context_size].min, to_start, [to_end, to_start + context_size].min] groups << group group = [] from_start = [from_start, from_end - context_size].max to_start = [to_start, to_end - context_size].max end group << [tag, from_start, from_end, to_start, to_end] end groups << group unless group.empty? groups end
longest_match(from_start, from_end, to_start, to_end)
click to toggle source
# File test-unit-3.6.1/lib/test/unit/diff.rb, line 20 def longest_match(from_start, from_end, to_start, to_end) best_info = find_best_match_position(from_start, from_end, to_start, to_end) unless @junks.empty? args = [from_start, from_end, to_start, to_end] best_info = adjust_best_info_with_junk_predicate(false, best_info, *args) best_info = adjust_best_info_with_junk_predicate(true, best_info, *args) end best_info end
operations()
click to toggle source
# File test-unit-3.6.1/lib/test/unit/diff.rb, line 38 def operations @operations ||= compute_operations end
ratio()
click to toggle source
# File test-unit-3.6.1/lib/test/unit/diff.rb, line 69 def ratio @ratio ||= compute_ratio end
Private Instance Methods
adjust_best_info_with_junk_predicate(should_junk, best_info, from_start, from_end, to_start, to_end)
click to toggle source
# File test-unit-3.6.1/lib/test/unit/diff.rb, line 117 def adjust_best_info_with_junk_predicate(should_junk, best_info, from_start, from_end, to_start, to_end) best_from, best_to, best_size = best_info while best_from > from_start and best_to > to_start and (should_junk ? @junks.has_key?(@to[best_to - 1]) : !@junks.has_key?(@to[best_to - 1])) 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 (should_junk ? @junks.has_key?(@to[best_to + best_size]) : !@junks.has_key?(@to[best_to + best_size])) and @from[best_from + best_size] == @to[best_to + best_size] best_size += 1 end [best_from, best_to, best_size] end
compute_blocks()
click to toggle source
# File test-unit-3.6.1/lib/test/unit/diff.rb, line 173 def compute_blocks blocks = [] current_from_index = current_to_index = current_size = 0 matches.each do |from_index, to_index, size| if current_from_index + current_size == from_index and current_to_index + current_size == to_index current_size += size else unless current_size.zero? blocks << [current_from_index, current_to_index, current_size] end current_from_index = from_index current_to_index = to_index current_size = size end end unless current_size.zero? blocks << [current_from_index, current_to_index, current_size] end blocks << [@from.size, @to.size, 0] blocks end
compute_matches()
click to toggle source
# File test-unit-3.6.1/lib/test/unit/diff.rb, line 147 def compute_matches matches = [] queue = [[0, @from.size, 0, @to.size]] until queue.empty? from_start, from_end, to_start, to_end = queue.pop match = longest_match(from_start, from_end - 1, to_start, to_end - 1) match_from_index, match_to_index, size = match unless size.zero? 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 matches << match 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 matches.sort_by do |(from_index, _, _)| from_index end end
compute_operations()
click to toggle source
# File test-unit-3.6.1/lib/test/unit/diff.rb, line 197 def compute_operations from_index = to_index = 0 operations = [] blocks.each do |match_from_index, match_to_index, size| tag = determine_tag(from_index, to_index, match_from_index, match_to_index) if tag != :equal 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
compute_ratio()
click to toggle source
# File test-unit-3.6.1/lib/test/unit/diff.rb, line 219 def compute_ratio matches = blocks.inject(0) {|result, block| result + block[-1]} length = @from.length + @to.length if length.zero? 1.0 else 2.0 * matches / length end end
determine_tag(from_index, to_index, match_from_index, match_to_index)
click to toggle source
# File test-unit-3.6.1/lib/test/unit/diff.rb, line 229 def determine_tag(from_index, to_index, match_from_index, match_to_index) if from_index < match_from_index and to_index < match_to_index :replace elsif from_index < match_from_index :delete elsif to_index < match_to_index :insert else :equal end end
expand_edge_equal_operations!(_operations, context_size)
click to toggle source
# File test-unit-3.6.1/lib/test/unit/diff.rb, line 242 def expand_edge_equal_operations!(_operations, context_size) tag, from_start, from_end, to_start, to_end = _operations[0] if tag == :equal _operations[0] = [tag, [from_start, from_end - context_size].max, from_end, [to_start, to_end - context_size].max, to_end] end tag, from_start, from_end, to_start, to_end = _operations[-1] if tag == :equal _operations[-1] = [tag, from_start, [from_end, from_start + context_size].min, to_start, [to_end, to_start + context_size].min] end end
find_best_match_position(from_start, from_end, to_start, to_end)
click to toggle source
# File test-unit-3.6.1/lib/test/unit/diff.rb, line 97 def find_best_match_position(from_start, from_end, to_start, to_end) best_from, best_to, best_size = from_start, to_start, 0 sizes = {} from_start.upto(from_end) do |from_index| _sizes = {} (@to_indexes[@from[from_index]] || []).each do |to_index| next if to_index < to_start break if to_index > to_end size = _sizes[to_index] = (sizes[to_index - 1] || 0) + 1 if size > best_size best_from = from_index - size + 1 best_to = to_index - size + 1 best_size = size end end sizes = _sizes end [best_from, best_to, best_size] end
matches()
click to toggle source
# File test-unit-3.6.1/lib/test/unit/diff.rb, line 143 def matches @matches ||= compute_matches end
update_to_indexes()
click to toggle source
# File test-unit-3.6.1/lib/test/unit/diff.rb, line 74 def update_to_indexes @to_indexes = {} @junks = {} if @to.is_a?(String) each = " "[0].is_a?(Integer) ? :each_byte : :each_char else each = :each end i = 0 @to.__send__(each) do |item| @to_indexes[item] ||= [] @to_indexes[item] << i i += 1 end return if @junk_predicate.nil? @to_indexes = @to_indexes.reject do |key, value| junk = @junk_predicate.call(key) @junks[key] = true if junk junk end end