myers_linear.rb

require "./diff"

class MyersLinear
  Window = Struct.new(:left, :top, :right, :bottom) do
    def width
      right - left
    end

    def height
      bottom - top
    end

    def size
      width + height
    end

    def dif
      width - height
    end

    def inspect
      "<Window (#{left}, #{top}), (#{right}, #{bottom})>"
    end
  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
    path = find_path(0, 0, @a.size, @b.size)
    diff = []

    path.each_cons(2) do |(prev_x, prev_y), (x, y)|
      if x == prev_x
        diff.push(Diff::Line.new(:ins, nil, y, @b[prev_y]))
      elsif y == prev_y
        diff.push(Diff::Line.new(:del, x, nil, @a[prev_x]))
      else
        diff.push(Diff::Line.new(:eql, x, y, @a[prev_x]))
      end
    end

    diff
  end

  def find_path(left, top, right, bottom)
    window = Window.new(left, top, right, bottom)
    snake  = midpoint(window)

    return nil unless snake

    start  = snake.shift
    finish = snake.pop
    prefix = find_path(window.left, window.top, start[0], start[1])
    suffix = find_path(finish[0], finish[1], window.right, window.bottom)

    (prefix || [start]) + snake + (suffix || [finish])
  end

  def midpoint(window)
    return nil if window.width == 0 and window.height == 0

    max = (window.size / 2.0).ceil
    cap = 2 * window.size + 1

    vf = Array.new(cap)
    vf[1] = 0

    vb = Array.new(cap)
    vb[window.dif + 1] = window.height

    (0 .. max).step do |d|
      snakes = []

      forwards(window, vf, vb, d) { |s| snakes << s }
      backward(window, vf, vb, d) { |s| snakes << s }

      next if snakes.empty?

      snake = snakes.max_by { |s| s.first[0] - s.first[1] }
      return snake.map { |x, y| [window.left + x, window.top + y] }
    end
  end

  def forwards(window, vf, vb, d)
    (-d .. d).step(2) do |k|
      if k == -d or (k != d and vf[k - 1] < vf[k + 1])
        px = x = vf[k + 1]
      else
        px = vf[k - 1]
        x  = px + 1
      end

      y = x - k
      snake = [[x, y]]
      snake.unshift(x == px ? [x, y - 1] : [x - 1, y]) if d > 0

      while x < window.width and y < window.height and @a[window.left + x] == @b[window.top + y]
        x, y = x + 1, y + 1
        snake.push([x, y])
      end

      vf[k] = x

      if window.dif.odd? and k.between?(window.dif - (d - 1), window.dif + (d - 1))
        yield snake if vf[k] >= vb[k] + k
      end
    end
  end

  def backward(window, vf, vb, d)
    (-d .. d).step(2) do |c|
      k = c + window.dif

      if c == -d or (c != d and vb[k - 1] > vb[k + 1])
        py = y = vb[k + 1]
      else
        py = vb[k - 1]
        y  = py - 1
      end

      x = y + k
      snake = [[x, y]]
      snake.push(y == py ? [x + 1, y] : [x, y + 1]) if d > 0

      while x > 0 and y > 0 and @a[window.left + x - 1] == @b[window.top + y - 1]
        x, y = x - 1, y - 1
        snake.unshift([x, y])
      end

      vb[k] = y

      if window.dif.even? and k.between?(-d, d)
        yield snake if vf[k] >= vb[k] + k
      end
    end
  end
end