patience_diff.rb

class Patience
  Match = Struct.new(:a_line, :b_line, :text) do
    attr_accessor :prev
  end

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

  def initialize(a, b)
    a = a.lines if a.is_a?(String)
    b = b.lines if b.is_a?(String)

    @a, @b = a, b
  end

  def diff
    diff_range(0, @a.size, 0, @b.size)
  end

  def diff_range(a_low, a_high, b_low, b_high)
    head, tail = [], []

    while a_low < a_high and b_low < b_high and @a[a_low] == @b[b_low]
      head.push(Diff::Line.new(:eql, a_low + 1, b_low + 1, @a[a_low]))
      a_low = a_low + 1
      b_low = b_low + 1
    end

    while a_high > a_low and b_high > b_low and @a[a_high - 1] == @b[b_high - 1]
      tail.unshift(Diff::Line.new(:eql, a_high, b_high, @a[a_high - 1]))
      a_high = a_high - 1
      b_high = b_high - 1
    end

    matches = unique_lines((a_low ... a_high), (b_low ... b_high))
    matches = patience_lcs(matches)
      
    middle = []

    matches.each do |match|
      middle += diff_range(a_low, match.a_line + 1, b_low, match.b_line + 1)
      a_low = match.a_line + 1
      b_low = match.b_line + 1
    end

    (a_low ... a_high).each do |n|
      middle << Diff::Line.new(:del, n + 1, nil, @a[n])
    end

    (b_low ... b_high).each do |n|
      middle << Diff::Line.new(:ins, nil, n + 1, @b[n])
    end

    head + middle + tail
  end

  def unique_lines(a_range, b_range)
    counts = Hash.new { |h, k| h[k] = [0, 0, nil, nil] }

    a_range.each do |n|
      text = @a[n]
      counts[text][0]  += 1
      counts[text][2] ||= n
    end

    b_range.each do |n|
      text = @b[n]
      counts[text][1]  += 1
      counts[text][3] ||= n
    end

    counts = counts.select { |text, count| count.take(2) == [1, 1] }

    counts.map do |text, (n, m, a_line, b_line)|
      Match.new(a_line, b_line, text)
    end
  end

  def patience_lcs(matches)
    return [] if matches.empty?

    stacks = patience_sort(matches)
    match  = stacks.last.last
    lcs    = []

    while match
      lcs.unshift(match)
      match = match.prev
    end

    lcs
  end

  def patience_sort(matches)
    stacks = []

    matches.sort_by(&:b_line).each do |match|
      index = (0 ... stacks.size).find { |i| stacks[i].last.a_line > match.a_line }

      unless index
        index = stacks.size
        stacks << []
      end
      if index > 0
        match.prev = stacks[index - 1].last
      end
      stacks[index] << match
    end

    stacks
  end
end