##
# Myers 比较排序算法
##

module Aio::Base::Toolkit

  module Diff
    Line = Struct.new(:number, :text, :diff?) do
      def inspect
        text.to_s
      end
    end

    def self.lines(document, lines)
      # document = document.lines if document.is_a?(String)
      document.map.with_index do |text, i| 
        bool = lines.include?(i)
        Line.new(i + 1, text, bool)
      end
    end

    def self.empty_line
      Line.new(0, '', false)
    end

    # CompareDiff
    def self.diff(cd, differ: Myers)
      differ.diff(
        lines(cd.content, cd.lines), 
        lines(cd.content_compare, cd.lines_compare)
      )
    end
  end

  class Myers

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

    def initialize(a, b)
      @a, @b = a, b
    end

    def shortest_edit
      n, m = @a.size, @b.size
      max = n + m

      v = ::Array.new(2 * max + 1)
      v[1] = 0
      trace = []

      (0..max).step do |d|
        trace << v.clone

        (-d..d).step(2) do |k|

          if k == -d or (k != d and v[k-1] < v[k+1])
            x = v[k+1]
          else
            x = v[k-1] + 1
          end

          y = x - k

          # while x < n and y < m and @a[x].text == @b[y].text
          while x < n and y < m and !@a[x].diff? and !@b[y].diff?
            x, y = x + 1, y + 1
          end

          v[k] = x

          return trace if x >= n and y >= m
        end
      end
    end

    def backtrack
      x, y = @a.size, @b.size

      shortest_edit.each_with_index.reverse_each do |v, d|
        k = x - y

        if k == -d or (k != d and v[k-1] < v[k+1])
          prev_k = k + 1
        else
          prev_k = k - 1
        end

        prev_x = v[prev_k]
        prev_y = prev_x - prev_k

        while x > prev_x and y > prev_y
          yield x - 1, y - 1, x, y
          x, y = x - 1, y - 1
        end

        yield prev_x, prev_y, x, y if d > 0

        x, y = prev_x, prev_y
      end
    end

    def diff
      diff = []

      backtrack do |prev_x, prev_y, x, y|
        a_line, b_line = @a[prev_x], @b[prev_y]

        if x == prev_x
          diff.unshift(Diff::Edit.new(:ins, nil, b_line))
        elsif y == prev_y
          diff.unshift(Diff::Edit.new(:del, a_line, nil))
        else
          diff.unshift(Diff::Edit.new(:eql, a_line, b_line))
        end
      end

      # 此时得到的是按顺序排列的数组
      diff
    end

  end

  module Diff
    Edit = Struct.new(:type, :old_line, :new_line) do
      def old_number
        return '' if old_line.number.to_s == '0'
        old_line ? old_line.number.to_s : ''
      end

      def new_number
        return '' if new_line.number.to_s == '0'
        new_line ? new_line.number.to_s : ''
      end

      def text
        (old_line || new_line).text
      end

      def old_text
        old_line.text
      end

      def new_text
        new_line.text
      end

      def empty?
        (old_line.empty? and new_line.empty?)
      end

      def type_class
        type.to_s + '_style'
      end

      def type_class_con
        type.to_s + '_style_con'
      end

      def self.empty_line
        Edit.new(:eql, Diff.empty_line, Diff.empty_line)
      end
    end
  end
end