#!/usr/bin/env ruby

require 'zipf'

class RuleAndSpan
  attr_accessor :span, :symbol, :source, :target, :subspans, :done, :id

  def initialize s, id
    spans, srcs, tgts = splitpipe s.strip
    _,@symbol = spans.split
    @span = _.split(",", 2).map { |i| i.gsub(/[<>]/, "").to_i}
    @source = srcs.strip.split
    j = 0
    @source.map! { |i| if i.match(/\[X\]/) then "[#{j+=1}]"  else i end }
    @target = tgts.strip.split
    @subspans = []
    @done = false
    @id = id
  end

  def to_s
    return "#{@id}\t<#{@span.first},#{@span[1]}> [X] ||| #{@source.join " "} ||| #{@target.join " "}"
  end

  def is_terminal_rule?
    @source.each { |w|
      return true if !w.match(/\[S|(\d+)\]/)
    }

    return false
  end
end

def conv_cdec_show_deriv s
  a = s.split("}").map { |i|
    i.gsub /^[()\s]*/, ""
  }.reject { |i|
    i.size==0 }.map { |i|
      i.gsub /^\{/, ""
  }

  return a
end

def derive span, spans, by_span, o, groups, source
  if groups.size==0 || groups.last.size>0
    groups << []
  end
  a = nil
  if source
    a = span.source
  else
    a = span.target
  end
  a.each_with_index { |w,k|
    nt = w.match /\[(\d+)\]/
    if nt
      idx = nt.captures.first.to_i-1
      _ = derive by_span[span.subspans[idx]], spans, by_span, o, groups, source
      (k+1).upto(a.size-1) { |i|
        if !a[i].match(/\[(\d+)\]/) && groups.last.size>0
          groups << []
        end
      }
    else
      groups.last << ["#{w}", span.id]
      o << w
    end
  }
  span.done = true
end

def proc_deriv s
  a = conv_cdec_show_deriv s

  by_span = {}
  spans = []
  id = 0
  a.each { |line|
    rs = RuleAndSpan.new line, id
    id += 1
    by_span[rs.span] = rs
    if rs.is_terminal_rule?
      spans << rs.span
    end
  }

  spans.reverse.each_with_index { |s,k|
    (spans.size-(k+2)).downto(0) { |l|
      t = spans[l]
      if s[0] >= t[0] and s[1] <= t[1]
        by_span[t].subspans << s
        break
      end
    }
  }

  # fix order
  spans.each { |s|
    by_span[s].subspans.reverse!
  }

  so = []
  source_groups = []
  spans.each { |span|
    next if by_span[span].done
    derive by_span[span], spans, by_span, so, source_groups, true
  }

  spans.each { |s| by_span[s].done = false }

  o = []
  groups = []
  spans.each { |span|
    next if by_span[span].done
    derive by_span[span], spans, by_span, o, groups, false
  }

  source_rgroups = []
  rgroups = []
  source_groups.each { |i| source_rgroups << i.first[1] }
  groups.each { |i| rgroups << i.first[1] }

  phrase_align = []
  source_rgroups.each { |i|
    phrase_align << []
    rgroups.each_with_index { |j,k|
      if i==j
        phrase_align.last << k
      end
    }
  }

  h = {}
  h[:phrase_alignment] =  phrase_align
  h[:source_groups] = source_groups.map { |a| a.map { |i| i.first }.join " " }
  h[:target_groups] = groups.map { |a| a.map { |i| i.first }.join " " }

  return h.to_json
end

if __FILE__ == $0
  json = proc_deriv(STDIN.gets.strip)
  obj = JSON.parse(json)
  STDERR.write "#{json}\n"
  puts obj["target_groups"].join " "
end