cdiff

#!/usr/bin/env ruby
# -*- encoding: utf-8 -*-
require 'optparse'

#
# common diff viewer
#
#
# $ find . -type f | cdiff
#
# $ find . -type f | cdiff mv {c1}{d1}{c2}{d2}{c3} {c1}{d1}/res/ic_link_arrow.png
#

def extractCommonDigitList (str1, str2, min_common_width=3)
  map = []
  height = str1.size
  width  = str2.size

  height.times do |y|
    map.push( Array.new(width){ |i| 0 } )
  end

  # create match map
  height.times do |y|
    s1 = str1.slice(y, 1)

    width.times do |x|
      s2 = str2.slice(x, 1)
      v = (s1 == s2) ? 1 : 0
      map[y][x] = v
    end
  end

  pipes = []

  height.times do |y|
    width.times do |x|
      score = 0
      py = y
      px = x

      next if y > 1 && x > 1 && map[y-1][x-1] == 1

      while py < height && px < width && map[py][px] == 1
        score += 1
        py+=1
        px+=1
      end

      if score >= min_common_width
        arr = []
        arr += Array.new(y) { |i| 0 }
        arr += Array.new(score) { |i| 1 }
        arr += Array.new(height - y - score) { |i| 0 }
        raise "error" if arr.size != height
        pipes.push(arr)
      end
    end
  end

  pipes
end

def getCommonDigits(digits1, digits2)
  digits1.zip(digits2).collect do |d1, d2|
    d1 & d2
  end
end

def summerize(arr)
  arr.inject(0){ |sum, x| sum + x }
end

## 
# compare digits and get common
# @param 
#   [0,1,1], [[0,0,1], [1,1,1]]
# @return
#   [0,1,1]
#
def getDigitListCommon(digits, list)
  max_sum = -1
  max_digits = nil

  list.each do |dst_digits|
    common_digits = getCommonDigits(digits,dst_digits)
    sum = summerize(common_digits)

    if sum > max_sum
      max_digits = common_digits
      max_sum = sum
    end
  end

  max_digits
end

def digits2str(str, digits)
  result = []
  past_digit = -1

  str.split("").zip(digits).collect do |s, d|
    if past_digit != d
      past_digit = d
      result.push(s)
    else
      result[-1] += s
    end
  end

  result
end

def digits2divided_str(str, digits)
  p_start = digits.index(1)
  p_end   = digits.size - digits.reverse.index(1)

  [
    str.slice(0, p_start),
    str.slice(p_start, p_end - p_start),
    str.slice(p_end, digits.size - p_end),
  ]
end

def str2divided_str(str, common_str)
  p_start = str.index(common_str)
  p_end   = p_start + common_str.size
  
  [
    str.slice(0, p_start),
    str.slice(p_start, p_end - p_start),
    str.slice(p_end, str.size - p_end),
  ]
end

def longestDivide(list, min_common_width)
  return "" if list.include?("") || list.include?(nil)

  target_message = list[0]

  # グループごとに共通部分を抽出
  group_digits = []
  list.drop(1).each do |message|
    group = extractCommonDigitList(target_message, message, min_common_width)
    group_digits.push(group)
  end

  # グループ内に共通部分が存在するかどうか調べる
  global_min_digits = nil
  global_min_digits_size = target_message.size

  # Aグループの共通部分に対してみていく
  target_group = group_digits[0]
  target_group.each do |digits|
    found = true
    found_min_digits = digits

    # グループ内に共通する部分があるかどうか？
    group_digits.each do |group|
      common_digits = getDigitListCommon(digits, group)

      if common_digits == nil
        found = false
        break
      end

      found_min_digits = getCommonDigits(found_min_digits, common_digits)
    end

    # found!
    if found
      if global_min_digits == nil
        global_min_digits = found_min_digits
        global_min_digits_size = summerize(found_min_digits)
      else 
        min_size = summerize(found_min_digits)
        if min_size > global_min_digits_size
          global_min_digits_size = min_size
          global_min_digits = found_min_digits
        end
      end
    end
  end

  if global_min_digits == nil
    return "{#{ list.sort.uniq.join(',') }}"
  end

  first, common, last = digits2divided_str(target_message, global_min_digits)
  if common == nil || common ==""
    "{#{ list.join(',') }}"
  else
    firsts = []
    lasts  = []

    list.collect do |line|
      afirst, acommon, alast = str2divided_str(line, common)
      firsts.push(afirst)
      lasts.push(alast)
    end

    before = longestDivide(firsts, min_common_width)
    after  = longestDivide(lasts, min_common_width)

    before + common + after
  end
end

# 引数を置換する
def replace_arg(common_vars, diff_vars, arg)
  statement = arg

  if statement =~ /\{\}/
    commons = common_vars.size.times.collect do |i|
      "{c#{i}}"
    end

    diffs = diff_vars.size.times.collect do |i|
      "{d#{i}}"
    end

    statement = statement.gsub(/{}/, commons.zip(diffs).flatten.join(""))
  end

  common_vars.size.times do |i|
    var = common_vars[i]
    reg = Regexp.new("{c#{i}}")
    statement = statement.gsub(reg, var)
  end

  statements = [statement]

  diff_vars.size.times do |i|
    vars = diff_vars[i]
    reg = Regexp.new("{d#{i}}")

    new_statements = []
    statements.each do |st|
      vars.each do |var|
        statement = st.gsub(reg, var)
        new_statements.push(statement)
      end
    end

    statements = new_statements.sort.uniq
  end

  if statements.size == 1
    diff_vars_size = diff_vars.inject(1) do |sum, x|
      sum *= x.size
    end

    return statements * diff_vars_size
  end

  statements
end

def getCommonVars(statement)
  commons = statement.split(/{[^}]+}/)
end

def getDiffVars(statement)
  diffs = statement.scan(/{([^}]+)}/).collect do |var|
    var[0].split(",")
  end
end

def onlyExistFile(pathes)
  result = []

  pathes.each do |path|
    result << path if File.exist?(path)
  end

  result
end

#
# main
#

option = { checkfile: nil, min_common_width: 3 }

opt = OptionParser.new
opt.on('-e COLUMN_NUMS') { |v| option[:checkfile] = v.split(",").collect{|a| a.to_i } }
opt.on('-w MIN_COMMON_WIDTH') { |v| option[:min_common_width] = v.to_i }
opt.parse!(ARGV)

lines = STDIN.read.split("\n")
minify = longestDivide(lines, option[:min_common_width])

if ARGV.size > 0
  common_vars = getCommonVars(minify)
  diff_vars   = getDiffVars(minify)

  states = []
  ARGV.each_with_index do |arg, i|
    replaced_array = replace_arg(common_vars, diff_vars, arg)

    if option[:checkfile] != nil && option[:checkfile].include?(i)
      replaced_array = onlyExistFile(replaced_array)
    end

    states << replaced_array
  end

  if states.size > 0
    width = states[0].size

    width.times do |i|
      result = states.collect do |line|
        line[i]
      end

      puts result.join(" ")
    end
  end
else
  puts minify
end