module GreenWater

# File lib/green_water.rb, line 5
def diff!(argv)
  validate!(argv)
  a_file1, a_file2 = argv.collect{|f| read_array(f)}
  lcs_diff_data = raw_diff(lcs(a_file1, a_file2), a_file1, a_file2, a_file1.length, a_file2.length)
  print_formatter(lcs_diff_data).each{|f| puts f.join(' ')}
end

# File lib/green_water.rb, line 98
def lcs(x, y)
  x_len = x.size
  y_len = y.size
  c = Array.new(x_len){Array.new(y_len){0}}

  x_len.times do |i|
    y_len.times do |j|
      if x[i] == y[j]
        c[i][j] = (i==0 || j==0) ? 1: (1 + c[i-1][j-1])
      else
        if i==0 && j==0
          c[i][j] = 0
        elsif i==0 && j!=0
          c[i][j] = [0,  c[i][j-1]].max
        elsif j==0 && i!=0
          c[i][j] = [0, c[i-1][j]].max
        elsif i != 0 && j != 0
          c[i][j] = [c[i-1][j], c[i][j-1]].max
        end
      end
    end
  end

  return c
end

# File lib/green_water.rb, line 29
def print_formatter(r)
  rr = []
  add_array = []
  rem_array = []

  r.reverse.each_with_index do |line, index|
    add_array << line.last if line.first
    rem_array << line.last if !line.first && !line.first.nil?

    if r.reverse[index+1].nil? || r.reverse[index+1].first.nil?
      if(add_array.any? && rem_array.any?)
        if add_array.size > rem_array.size
          add_array.reverse[rem_array.size..-1].reverse.each do |line|
            rr << ["+", line]
          end
          (rem_array.size-1).step(0, -1) do |i|
            rr << ["*", "#{rem_array.reverse[i].strip} | #{add_array.reverse[i]}"]
          end
        elsif add_array.size < rem_array.size
          rem_array.reverse[add_array.size..-1].reverse.each do |line|
            rr << ["-", line]
          end
          (add_array.size-1).step(0, -1) do |i|
            rr << ["*", "#{rem_array.reverse[i].strip} | #{add_array.reverse[i]}"]
          end
        else
          add_array.size.step(0, -1) do |i|
            rr << ["*", "#{rem_array.reverse[i].strip} | #{add_array.reverse[i]}"]
          end
        end
        add_array = []
        rem_array = []
      elsif(add_array.any? && rem_array.none?)
        add_array.each do |line|
          rr << ["+", line]
        end
        add_array = []
      elsif(rem_array.any? && add_array.none?)
        rem_array.each do |line|
          rr << ["-", line]
        end
        rem_array = []
      end
    end

    if line.first.nil?
      rr << [" ", line.last]
    end                  
  end

  return rr.reverse
end

# File lib/green_water.rb, line 82
def raw_diff(c, x, y, i, j, r=[])
  if i > 0 && j > 0 && x[i-1] == y[j-1]
    raw_diff(c, x, y, i-1, j-1, r)
    r << [nil, x[i-1]]
  else
    if j > 0 && (i == 0 or c[i-1][j-2] >= c[i-2][j-1])
      raw_diff(c, x, y, i, j-1, r)
      r << [true, y[j-1]]
    elsif i > 0 && (j == 0 or c[i-1][j-2] < c[i-2][j-1])
      raw_diff(c, x, y, i-1, j, r)
      r << [false, x[i-1]]
    end
  end
  return r
end

# File lib/green_water.rb, line 21
def read_array(file)
  array_line = []  
  File.foreach( file ) do |line|
    array_line.push line
  end
  return array_line
end

# File lib/green_water.rb, line 12
def validate!(argv)
  abort("Wrong number of arguments: expected - 2, got - #{argv.size}") unless argv.size == 2
  argv.each do |file|
    puts file.inspect
    abort("File #{file} doesnt exists!") unless File.exist?(file)
  end
  return true
end