class Test::Unit::Diff::SequenceMatcher

# File test-unit-3.3.4/lib/test/unit/diff.rb, line 14
def initialize(from, to, &junk_predicate)
  @from = from
  @to = to
  @junk_predicate = junk_predicate
  update_to_indexes
end

# File test-unit-3.3.4/lib/test/unit/diff.rb, line 35
def blocks
  @blocks ||= compute_blocks
end

# File test-unit-3.3.4/lib/test/unit/diff.rb, line 43
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

# File test-unit-3.3.4/lib/test/unit/diff.rb, line 21
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

# File test-unit-3.3.4/lib/test/unit/diff.rb, line 39
def operations
  @operations ||= compute_operations
end

# File test-unit-3.3.4/lib/test/unit/diff.rb, line 70
def ratio
  @ratio ||= compute_ratio
end

# File test-unit-3.3.4/lib/test/unit/diff.rb, line 118
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

# File test-unit-3.3.4/lib/test/unit/diff.rb, line 174
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

# File test-unit-3.3.4/lib/test/unit/diff.rb, line 148
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

# File test-unit-3.3.4/lib/test/unit/diff.rb, line 198
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

# File test-unit-3.3.4/lib/test/unit/diff.rb, line 220
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

# File test-unit-3.3.4/lib/test/unit/diff.rb, line 230
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

# File test-unit-3.3.4/lib/test/unit/diff.rb, line 243
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

# File test-unit-3.3.4/lib/test/unit/diff.rb, line 98
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

# File test-unit-3.3.4/lib/test/unit/diff.rb, line 144
def matches
  @matches ||= compute_matches
end

# File test-unit-3.3.4/lib/test/unit/diff.rb, line 75
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