import java.lang.*;
import java.util.*;
import java.io.*;


class Rule {
    public String nodetype;
    public Vector<String> subs;

    Rule() {
	subs = new Vector<String>();
    }
}

public class TreeReorder {
    Vector<Rule> rules;
    boolean debug;

    TreeReorder() {
	rules = new Vector<Rule>();
	debug = false;
    }

    void readRules(String rulefile) {
	String line;
	Rule tmprule;
	int i;

	try {
	    InputStream ruledata = new FileInputStream(rulefile);
	    BufferedReader in = new BufferedReader(new InputStreamReader(ruledata, "GBK"));
	    
	    while ((line = in.readLine()) != null) {
		line.trim();
		if (line.length() == 0) { continue; }
		String[] fields = line.split("\\s+");
		if (fields.length < 3) { continue; }
		tmprule = new Rule();
		tmprule.nodetype = fields[0];
		for (i = 1; i < fields.length; i++) {
		    tmprule.subs.add(fields[i]);
		}
		rules.add(tmprule);
	    }
	}
	catch (Exception e) {
	    e.printStackTrace();
	}
	System.out.println("Rule count: " + rules.size());
    }


    pTreeNode buildTree(String tree) {
	StringReader sr = new StringReader(tree);
	ParseTreeLexer ptl = new ParseTreeLexer(sr);
	ParseTreeParser ptp = new ParseTreeParser(ptl);

	pTreeNode ptn = new pTreeNode();
	ptp.setTopNode(ptn);
	try {
	    ptp.tree();
	}
	catch (Exception e) {
	    e.printStackTrace();
	}
	return ptn;
    }


    void applyRules(pTreeNode topnode) {
	Stack<pTreeNode> nodestack = new Stack<pTreeNode>();
	int i, j, ruleindex, first, second;
	pTreeNode ptn;
	String nodetype;
	boolean submatch;

	nodestack.push(topnode);
	while (nodestack.size() > 0) {
	    //System.out.println("Node stack size: " + nodestack.size());
	    ptn = nodestack.pop();
	    nodetype = ptn.nodetype;
	    if (ptn.subs.size() > 0) {
		for (ruleindex = 0; ruleindex < rules.size(); ruleindex++) {
		    //System.out.println("Rule node type " + ruleindex + " " + rules.elementAt(ruleindex).nodetype);
		    if (nodetype.equals(rules.elementAt(ruleindex).nodetype) == true) {
			//System.out.println("Rule node type match " + rules.elementAt(ruleindex).nodetype);
			first = -1;
			if (rules.elementAt(ruleindex).subs.elementAt(0).indexOf("/") > 0) {
			    String[] levels = rules.elementAt(ruleindex).subs.elementAt(0).split("/");
			    for (i = 0; i < ptn.subs.size(); i++) {
				if (ptn.subs.elementAt(i).nodetype.equals(levels[0])) {
				    first = i;
				    // Check next level
				    submatch = false;
				    for (j = 0; j < ptn.subs.elementAt(i).subs.size(); j++) {
					if (ptn.subs.elementAt(i).subs.elementAt(j).nodetype.equals(levels[1])) {
					    submatch = true;
					    break;
					}
				    }
				    if (submatch == false) {
					first = -1;
				    } else {
					break;
				    }

				    //System.out.println("First: " + first);
				}
			    }
			    
			} else {
			    for (i = 0; i < ptn.subs.size(); i++) {
				if (ptn.subs.elementAt(i).nodetype.equals(rules.elementAt(ruleindex).subs.elementAt(0))) {
				    first = i;
				    break;
				    //System.out.println("First: " + first);
				}
			    }

			}

			if (first == -1) { continue; }
			second = -1;
			for (i = ptn.subs.size()-1; i >= 0; i--) {
			    if (ptn.subs.elementAt(i).nodetype.equals(rules.elementAt(ruleindex).subs.elementAt(1))) {
				second = i;
				//System.out.println("Second: " + second);

			    }
			}
			if (second == -1 || second <= first) {
			    continue;
			}
			if (debug) System.out.println("Rule applied " + ruleindex);

			ptn.subs.add(second+1, ptn.subs.elementAt(first));
			ptn.subs.remove(first);

		    }
		}

		for (i = ptn.subs.size()-1; i >= 0; i--) {
		    nodestack.push(ptn.subs.elementAt(i));
		}
	    } else {
		//sentence.append(ptn.word + " ");
	    }
	}	

    }


    void readParses(String parsefile, String transformfile) {
	String line, sentence;
	pTreeNode topnode;
	int linecount = 0;
	String encoding = "GBK";
	try {
	    InputStream ruledata = new FileInputStream(parsefile);
	    BufferedReader in = new BufferedReader(new InputStreamReader(ruledata, encoding));

	    FileOutputStream out = new FileOutputStream(transformfile);
	    BufferedWriter w = new BufferedWriter(new OutputStreamWriter(out, encoding));
	    
	    while ((line = in.readLine()) != null) {
		line.trim();
		//System.out.println("Line: " + line);
		if (line.length() == 0) { continue; }
		if (line.charAt(0) != '(') { 
		    w.write(line + "\n");
		    linecount++; continue;
		}
		topnode = buildTree(line);
		applyRules(topnode);
		sentence = getSentence(topnode);
		//w.write("Sentence " + linecount + ": " + sentence + "\n");
		w.write(sentence + "\n");
		if (debug) System.out.println("topnode type: " + topnode.nodetype);
		//System.out.println("Sentence " + linecount + ": " + sentence);
		linecount++;
	    }
	    w.close();
	}
	catch (Exception e) {
	    e.printStackTrace();
	}
	System.out.println("Parse count: " + linecount);

    }


    String getSentence(pTreeNode topnode) {
	StringBuffer sentence = new StringBuffer();
	Stack<pTreeNode> nodestack = new Stack<pTreeNode>();
	int i;
	pTreeNode ptn;

	nodestack.push(topnode);
	while (nodestack.size() > 0) {
	    if (debug) System.out.println("Node stack size: " + nodestack.size());
	    ptn = nodestack.pop();
	    if (ptn.subs.size() > 0) {
		for (i = ptn.subs.size()-1; i >= 0; i--) {
		    nodestack.push(ptn.subs.elementAt(i));
		}
	    } else {
		sentence.append(ptn.word + " ");
	    }
	}

	return sentence.toString().trim();
    }


    public static void main(String[] argv) {
	String rulefile, parsefile, transformfile;

	rulefile = null; //"/afs/cs/user/eepeter/avenue/Transfer/Chinese/collins.txt";
	parsefile = null; //"/afs/cs/user/eepeter/cebmt/alignment/cn_corpus_parsed.txt";
	transformfile = null; //"cn_parse_leaves.txt";
	//System.out.println("Argv " + argv.length);
	if (argv.length < 2) {
	    System.out.println("Need at least rule file name and parse tree file");
	    System.exit(1);
	} else if (argv.length == 2) {
	    rulefile = argv[0];
	    parsefile = argv[1];
	    transformfile = argv[1] + ".map";
	} else if (argv.length == 3) {
	    rulefile = argv[0];
	    parsefile = argv[1];
	    transformfile = argv[2];
	} else {
	    System.out.println("Too many arguments");
	    System.exit(1);
	}
	
	if (rulefile == null) {
	    System.out.println("Need to specify rule file name");
	    System.exit(1);
	}
	if (parsefile == null) {
	    System.out.println("Need to specify file with parses");
	    System.exit(1);
	}
	if (transformfile == null) {
	    System.out.println("Need to specify file to write reordered sentences.");
	    System.exit(1);
	}

	TreeReorder tr = new TreeReorder();

	tr.readRules(rulefile);
	tr.readParses(parsefile, transformfile);

    }

}