#!/usr/bin/env ruby

require_relative './util.rb'

# ISSUES
# new rule already in global g?
#  => uniq!
# singletons? => uniq -D
# R+S = R => X
# variants?
#


def is_sub(first, second, dir='left')
  if dir=='right'
    first = first.reverse; second = second.reverse
  end

  second_index = 0
  match = false
  first_range = Range.new; second_range = Range.new
  first.each_with_index { |i,first_index|
    break if i.match('\[X,\d\]') #(/\[X,\d\]/)
    break if second_index > second.size-1
    if i == second[second_index]
      if !match
        first_range.from = first_index
        first_range.to   = first_index
        second_range.from = second_index
        second_range.to   = second_index
        match = true
      else
        first_range.to = first_index
        second_range.to = second_index
      end
      second_index += 1
    else
      first_range.from = first_range.to = second_range.from = second_range.to = nil
    end
  }
  if dir=='right' && first_range.from&&first_range.to&&second_range.from&&second_range.to
    first_range.correct(first.size-1)
    second_range.correct(second.size-1)
  end
  return first_range, second_range if (first_range.from&&first_range.to&&second_range.from&&second_range.to)&&
                                      (first_range.from>0||first_range.to>0||second_range.from>0||second_range.to>0)
  return false
end

def merge(r, s, r_f_range, s_f_range, r_e_range, s_e_range, dir)
  #ret = []  ?
  new_rule = Rule.new
  new_rule.f = Array.new(s.f)
  new_rule.e = Array.new(s.e)
  new_rule.nt = r.nt
  if dir == 'left'
    return nil if r_f_range.from==0&&r_e_range.from==0
    (r_f_range.from-1).downto(0) { |i| new_rule.f.unshift r.f[i] }
    (r_e_range.from-1).downto(0) { |i| new_rule.e.unshift r.e[i] }
  elsif dir == 'right'
    return nil if r_f_range.from==r.f.size-1&&r_e_range.from==r.e.size-1
    (r_f_range.to+1).upto(r.f.size-1) { |i| new_rule.f <<  r.f[i] }
    (r_e_range.to+1).upto(r.e.size-1) { |i| new_rule.e <<  r.e[i] }
  end
  return new_rule
end

def test
  a = ["der", "eurozone", "[X,1]", "die", "[X,2]"]
  b = ["eurozone"]
  x = ["the", "eurozone", "[X,1]", "[X,2]"]
  y = ["eurozone", "members"]

  r,s = is_sub(a,b)
  puts "#{r} #{s}"

  r,s = is_sub(b,a)
  puts "#{r} #{s}"

  r,s = is_sub(x,y)
  puts "#{r} #{s}"

  r,s = is_sub(y,x)
  puts "#{r} #{s}"

  puts
  puts

  a = ["schuld", "an", "[X,1]", "inflation"]
  b = ["schuld"]
  x = ["blamed", "for", "[X,1]", "inflation"]
  y = ["for", "responsible"]

  r,s = is_sub(a,b)
  puts "#{r} #{s}"

  r,s = is_sub(b,a)
  puts "#{r} #{s}"

  r,s = is_sub(x,y)
  puts "#{r} #{s}"

  r,s = is_sub(y,x)
  puts "#{r} #{s}"
  exit
end
test if ARGV[0] == 'test'

# main
def main
  strings = {}
  while line = STDIN.gets
    ids, data = line.split "\t", 2
    r_id, s_id = ids.split '+', 2
    r_id = r_id.to_s
    s_id = s_id.to_s
    r_raw, s_raw = data.split ' <<<>>> ', 2
    r = Rule.new r_raw, r_id
    s = Rule.new s_raw, s_id
    #STDERR.puts "reporter:status:processing rules #{r_id} and #{s_id}"

    # left, R->S
    range_f_first, range_f_second = is_sub(r.f, s.f)
    range_e_first, range_e_second = is_sub(r.e, s.e)
    if range_f_first&&range_f_second&&range_e_first&&range_e_second
      new_rule = merge(r, s, range_f_first, range_f_first, range_e_first, range_e_second, 'left')
      if new_rule && !strings.has_key?(new_rule.rule_id_string)
        #puts "R: #{r.f} ||| #{r.e}\nS: #{s.f} ||| #{s.e}"
        #puts "f:(#{range_f_first} #{range_f_second}) e:(#{range_e_first} #{range_e_second})\n"
        puts new_rule.to_s
        strings[new_rule.rule_id_string] = true
        #puts "\n"
      end
    end

    # left, S->R
    range_f_first, range_f_second = is_sub(s.f, r.f)
    range_e_first, range_e_second = is_sub(s.e, r.e)
    if range_f_first&&range_f_second&&range_e_first&&range_e_second
      new_rule = merge(s, r, range_f_first, range_f_first, range_e_first, range_e_second, 'left')
      if new_rule && !strings.has_key?(new_rule.rule_id_string)
        #puts "S: #{s.f} ||| #{s.e}\nR: #{r.f} ||| #{r.e}"
        #puts "f:(#{range_f_first} #{range_f_second}) e:(#{range_e_first} #{range_e_second})\n"
        puts new_rule.to_s
        strings[new_rule.rule_id_string] = true
        #puts "\n"
      end
    end

    # right, R->S
    range_f_first, range_f_second = is_sub(r.f, s.f, 'right')
    range_e_first, range_e_second = is_sub(r.e, s.e, 'right')
    if range_f_first&&range_f_second&&range_e_first&&range_e_second
      new_rule = merge(r, s, range_f_first, range_f_first, range_e_first, range_e_second, 'right')
      if new_rule && !strings.has_key?(new_rule.rule_id_string)
        #puts "Rr: #{r.f} ||| #{r.e}\nSr: #{s.f} ||| #{s.e}"
        #puts "f:(#{range_f_first} #{range_f_second}) e:(#{range_e_first} #{range_e_second})\n"
        puts new_rule.to_s
        strings[new_rule.rule_id_string] = true
        #puts "\n"
      end
    end

    # right, S->R
    range_f_first, range_f_second = is_sub(s.f, r.f, 'right')
    range_e_first, range_e_second = is_sub(s.e, r.e, 'right')
    if range_f_first&&range_f_second&&range_e_first&&range_e_second
      new_rule = merge(s, r, range_f_first, range_f_first, range_e_first, range_e_second, 'right')
      if new_rule && !strings.has_key?(new_rule.rule_id_string)
        #puts "Sr: #{s.f} ||| #{s.e}\nRr: #{r.f} ||| #{r.e}"
        #puts "f:(#{range_f_first} #{range_f_second}) e:(#{range_e_first} #{range_e_second})\n"
        puts new_rule.to_s
        strings[new_rule.rule_id_string] = true if new_rule
        #puts "\n"
      end
    end
  end
end