//staticPlanner
import java.util.*;
import java.io.*;

public class Planner {
	ArrayList<Operator> operators;
	static ArrayList<Operator> preInstantiations;
	Random rand;
	int max;
	int count = 0;
	ArrayList<Operator> plan;

	public static void main(String argv[]) {
		// Guiを起動
		try {
			new Gui();
		} catch (IOException e) {}
		/*
		ArrayList<String> goalList = initGoalList();
		ArrayList<String> initialState = initInitialState();
		
		// ブロックの初期化
		ArrayList<Block> blockList = initBlock();
		
		(new Planner()).start(goalList, initialState);
		*/
	}

	Planner() {
		rand = new Random();
		preInstantiations = new ArrayList<Operator>();
	}

	public void start(ArrayList<String> goalList, ArrayList<String> initialState) {
		System.out.println(initOperators("operator.txt"));
		System.out.println(operators);

		HashMap<String, String> theBinding = new HashMap<String, String>();
		plan = new ArrayList<Operator>();

		max = 20;
		while (max < 100) {
			count = 0;
			if (planning((ArrayList<String>) goalList.clone(),
					(ArrayList<String>) initialState.clone(),
					(HashMap<String, String>) theBinding.clone())) {

				System.out.println("***** This is a plan! *****");
				Gui.TaRE.append("\n***** This is a plan! *****\n");
				for (int i = 0; i < plan.size(); i++) {
					Operator op = (Operator) plan.get(i);
					System.out.println((op.instantiate(theBinding)).name);
					Gui.TaRE.append(op.instantiate(theBinding).name + "\n");
				}
				break;
			} else {
				System.out.println(false);
				Gui.TaRE.append("false\n");
				max++;
				preInstantiations.clear();
				plan.clear();
				int randInt = Math.abs(rand.nextInt()) % goalList.size();
				String goal = goalList.get(randInt);
				goalList.remove(goal);
				goalList.add(goal);
			}
		}
	}

	/*
	 * 与えられたゴールリストに対してプランニングを行うメソッド
	 * 
	 * @param ゴールリストを表す theGoalList,ワーキングメモリを表す theCurrentState,　変数束縛情報を表す
	 * theBinding
	 * 
	 * @return プランニングが成功すれば true, 失敗すれば false
	 */
	private boolean planning(ArrayList<String> theGoalList,
			ArrayList<String> theCurrentState,
			HashMap<String, String> theBinding) {
		System.out.println("*** GOALS ***" + theGoalList);
		// ワーキングメモリがゴール状態を達成していれば成功
		if (theCurrentState.containsAll(theGoalList))
			return true;

		if (theGoalList.size() == 1) {
			String aGoal = (String) theGoalList.get(0);
			if (planningAGoal(aGoal, theCurrentState, theBinding) != -1) {
				return true;
			} else {
				return false;
			}

		} else {
			String aGoal = (String) theGoalList.get(0);
			theGoalList.remove(0);

			// Store original binding
			HashMap<String, String> orgBinding = new HashMap<String, String>();
			for (Iterator e = theBinding.keySet().iterator(); e.hasNext();) {
				String key = (String) e.next();
				String value = (String) theBinding.get(key);
				orgBinding.put(key, value);
			}
			ArrayList<String> orgState = new ArrayList<String>();
			for (int i = 0; i < theCurrentState.size(); i++) {
				orgState.add(theCurrentState.get(i));
			}

			// 副ゴールに対してプランニングを行う
			int tmpPoint = planningAGoal(aGoal, theCurrentState, theBinding);
			if (tmpPoint != -1) {
				// ワーキングメモリがゴール状態を達成していれば成功とする
				if (theCurrentState.containsAll(theGoalList)) {
					return true;
				}
				/*
				 * ここがデバックのポイント 調べた副ゴールを再びゴールリストの尾に追加する
				 * これは他の副ゴールのプランニングによってワーキングメモリが変化する可能性があるため
				 * さらにゴールリストに対して変数束縛を行う
				 */
				theGoalList.add(aGoal);
				int size = theGoalList.size();
				for (int i = 0; i < size; ++i) {
					String st = theGoalList.get(0);
					theGoalList.remove(0);
					st = instantiateString(st, theBinding);
					theGoalList.add(st);
				}

				System.out.println(theCurrentState);
				System.out.println(theBinding);
				// 再帰的にプランニングを行い、成功すれば true 、失敗すれば false　を返す
				if (planning(theGoalList, theCurrentState, theBinding)) {
					return true;
				} else {

					theBinding.clear();
					for (Iterator e = orgBinding.keySet().iterator(); e
							.hasNext();) {
						String key = (String) e.next();
						String value = (String) orgBinding.get(key);
						theBinding.put(key, value);
					}
					theCurrentState.clear();
					for (int i = 0; i < orgState.size(); i++) {
						theCurrentState.add(orgState.get(i));
					}
				}
			} else {
				theBinding.clear();
				for (Iterator e = orgBinding.keySet().iterator(); e.hasNext();) {
					String key = (String) e.next();
					String value = (String) orgBinding.get(key);
					theBinding.put(key, value);
				}
				theCurrentState.clear();
				for (int i = 0; i < orgState.size(); i++) {
					theCurrentState.add(orgState.get(i));
				}
				return false;
			}
			return false;
		}
	}

	/*
	 * 1つのゴール状態に対してプランニングを行うメソッド
	 * 
	 * @param ある1つのゴール状態を表す theGoal, ワーキングメモリを表す theCurrentState, 変数束縛情報を表す
	 * theBinding
	 * 
	 * @return　theGoal がワーキングメモリにおいて達成されていれば 1, 再帰的なプランニングにおいて達成されれば 0,　達成されなければ
	 * -1
	 */
	private int planningAGoal(String theGoal,
			ArrayList<String> theCurrentState,
			HashMap<String, String> theBinding) {
		// 無限ループと判定
		if (count++ > max)
			return -1;
		;

		System.out.println("**" + theGoal);
		// ワーキングメモリとマッチング
		int size = theCurrentState.size();
		
		for (int i = 0; i < size; i++) {
			String aState = (String) theCurrentState.get(i);

			if ((new Unifier()).unify(theGoal, aState, theBinding)) {
				System.out.println(theGoal + " <=> " + aState);
				System.out.println(theBinding);
				return 1;
			}
		}

		// 現在のCurrent state, Binding, planをbackup
		HashMap<String, String> orgBinding = new HashMap<String, String>();
		for (Iterator e = theBinding.keySet().iterator(); e.hasNext();) {
			String key = (String) e.next();
			String value = (String) theBinding.get(key);
			orgBinding.put(key, value);
		}
		ArrayList<String> orgState = new ArrayList<String>();
		for (int j = 0; j < theCurrentState.size(); j++) {
			orgState.add(theCurrentState.get(j));
		}
		ArrayList<Operator> orgPlan = new ArrayList<Operator>();
		for (int j = 0; j < plan.size(); j++) {
			orgPlan.add(plan.get(j));
		}

		// 競合集合を見つける
		HashMap<Operator, HashMap<String, String>> conflictSet = new HashMap<Operator, HashMap<String, String>>();
		System.out.print("Conflict :");
		for (int i = 0; i < operators.size(); i++) {
			Operator anOperator = rename((Operator) operators.get(i));
			ArrayList<String> addList = anOperator.getAddList();

			//テスト
			//System.out.println("テストtheGoal="+theGoal);
			for (int j = 0; j < addList.size(); j++) {
				HashMap<String, String> tmpBinding = (HashMap<String, String>) theBinding
						.clone();

				//テスト
				//System.out.println("テストaddList.get("+j+")="+addList.get(j));
				if ((new Unifier()).unify(theGoal, (String) addList.get(j),
						tmpBinding)) {
					anOperator = anOperator.instantiate(tmpBinding);
					conflictSet.put(anOperator, tmpBinding);
					System.out.println(anOperator.name + ",");
					System.out.println(tmpBinding);
				}
			}
		}
		// 適応可能なオペレータがなければ失敗
		if (conflictSet.size() == 0)
			return -1;

		System.out.println("");
		// 競合解消
		ArrayList<HashMap> newConflictSetList = resolveConflict(theGoal,
				conflictSet);

		// 優先度順にオペレータを適応
		for (int i = 0; i < newConflictSetList.size(); ++i) {
			HashMap<Operator, HashMap<String, String>> newConflictSet = newConflictSetList
					.get(i);
			for (Iterator e = newConflictSet.keySet().iterator(); e.hasNext();) {
				Operator newOperator = (Operator) e.next();
				HashMap<String, String> newBinding = newConflictSet
						.get(newOperator);

				newOperator = newOperator.instantiate(newBinding);
				ArrayList<String> newGoals = newOperator.getIfList();

				// 適応したインスタンシエーションは保存
				preInstantiations.add(newOperator);

				System.out.println("newOp:" + newOperator.name);
				System.out.println("newBind:" + newBinding);

				// 再帰的にプランニング
				if (planning(newGoals, theCurrentState, newBinding)) {
					newOperator = newOperator.instantiate(newBinding);
					System.out.println(newOperator.name);
					System.out.println(newBinding.toString()
							+ theBinding.toString());

					plan.add(newOperator);
					theCurrentState = newOperator.applyState(theCurrentState);

					// 呼び出し元にも束縛情報の更新を適応するためにコピーが必要
					copyMap(newBinding, theBinding);
					System.out.println(theBinding);
					return 0;
				} else {
					// 失敗したら元に戻す．
					preInstantiations.remove(newOperator);
					System.out.println("失敗 :" + newOperator.name + "\nGoal :"
							+ theGoal);
					theBinding.clear();
					for (Iterator e1 = orgBinding.keySet().iterator(); e1
							.hasNext();) {
						String key = (String) e1.next();
						String value = (String) orgBinding.get(key);
						theBinding.put(key, value);
					}
					theCurrentState.clear();
					for (int k = 0; k < orgState.size(); k++) {
						theCurrentState.add(orgState.get(k));
					}
					plan.clear();
					for (int k = 0; k < orgPlan.size(); k++) {
						plan.add(orgPlan.get(k));
					}
				}
			}
		}
		return -1;
	}

	/*
	 * map1 copy to map2
	 */
	private void copyMap(HashMap map1, HashMap map2) {
		map2.clear();
		map2.putAll(map1);
	}

	/*
	 * 競合解消を行うメソッド
	 * 
	 * @param 現在与えられているゴールを表す theGoal, 競合集合を表す conflictSet
	 * 
	 * @return 優先度順にソートされたインスタンシエーションと変数束縛情報のペアのリスト
	 */
	private ArrayList<HashMap> resolveConflict(String theGoal,
			HashMap<Operator, HashMap<String, String>> conflictSet) {
		ArrayList<HashMap> result = new ArrayList<HashMap>();
		if (conflictSet.size() == 1) {
			Iterator e = conflictSet.keySet().iterator();
			Operator newOperator = (Operator) e.next();
			HashMap<String, String> newBinding = conflictSet.get(newOperator);
			HashMap tmp = new HashMap();
			tmp.put(newOperator, newBinding);
			result.add(tmp);
		} else {

			ArrayList<Operator> delete = new ArrayList<Operator>();
			// 過去に使用したインスタンシエーションは削除
			for (Iterator ite = conflictSet.keySet().iterator(); ite.hasNext();) {
				Operator op = (Operator) ite.next();
				for (int i = 0; i < preInstantiations.size(); ++i) {
					// if((new
					// Unifier()).unify(preInstantiations.get(i).name,op.name
					// )){
					if (preInstantiations.get(i).name.equals(op.name)) {
						System.out.println("DELETE :"
								+ preInstantiations.get(i).name + "<=>"
								+ op.name);
						delete.add(op);
					}
				}
			}
			for (int i = 0; i < delete.size(); ++i) {
				conflictSet.remove(delete.get(i));
			}

			HashMap<Operator, HashMap<String, String>> conflictSet1 = new HashMap<Operator, HashMap<String, String>>();
			HashMap<Operator, HashMap<String, String>> conflictSet2 = new HashMap<Operator, HashMap<String, String>>();
			HashMap<Operator, HashMap<String, String>> conflictSet3 = new HashMap<Operator, HashMap<String, String>>();
			int minSize = -1;
			for (Iterator e = conflictSet.keySet().iterator(); e.hasNext();) {
				Operator key = (Operator) e.next();
				HashMap<String, String> value = conflictSet.get(key);

				if (minSize == -1 || minSize > key.getAddList().size()) {
					minSize = key.getAddList().size();
					conflictSet3.putAll(conflictSet2);
					conflictSet2.clear();
					conflictSet2.put(key, value);
				} else if (minSize == key.getAddList().size()) {
					conflictSet2.put(key, value);
				} else {
					conflictSet3.put(key, value);
				}
			}
			minSize = -1;
			ArrayList<Operator> delete2 = new ArrayList<Operator>();
			for (Iterator ite = conflictSet2.keySet().iterator(); ite.hasNext();) {
				Operator key = (Operator) ite.next();
				HashMap<String, String> value = conflictSet2.get(key);
				if (minSize == -1 || minSize > key.getDeleteList().size()) {
					minSize = key.getDeleteList().size();
					delete2.clear();
					conflictSet1.clear();
					delete2.add(key);
					conflictSet1.put(key, value);
				} else if (minSize == key.getDeleteList().size()) {
					delete2.add(key);
					conflictSet1.put(key, value);
				}
			}
			for (int i = 0; i < delete2.size(); ++i) {
				conflictSet2.remove(delete2.get(i));
			}
			System.out.println("con1");
			for (Iterator i = conflictSet1.keySet().iterator(); i.hasNext();) {
				System.out.println("-" + ((Operator) i.next()).name);
			}
			System.out.println("con2");
			for (Iterator i = conflictSet2.keySet().iterator(); i.hasNext();) {
				System.out.println("-" + ((Operator) i.next()).name);
			}
			System.out.println("con3");
			for (Iterator i = conflictSet3.keySet().iterator(); i.hasNext();) {
				System.out.println("-" + ((Operator) i.next()).name);
			}
			result.add(conflictSet1);
			result.add(conflictSet2);
			result.add(conflictSet3);
		}
		return result;
	}

	private String instantiateString(String thePattern,
			HashMap<String, String> theBinding) {
		String result = new String();
		StringTokenizer st = new StringTokenizer(thePattern);
		for (int i = 0; i < st.countTokens();) {
			String tmp = st.nextToken();
			if (var(tmp) || var2(tmp)) {
				String newString = (String) theBinding.get(tmp);
				if (newString == null) {
					result = result + " " + tmp;
				} else {
					result = result + " " + newString;
				}
			} else {
				result = result + " " + tmp;
			}
		}
		return result.trim();
	}

	private boolean var(String str1) {
		// 先頭が ? なら変数
		return str1.startsWith("?");
	}

	private boolean var2(String str1) {
		// ブロックの要素（色、形）なら変数
		//return BlockOp.elements.contains(str1);
		Iterator ite = BlockOp.elements.iterator();
		while(ite.hasNext()) {
			if(str1.startsWith((String) ite.next())) {
				return true;
			}
		}
		return false;
	}
	
	int uniqueNum = 0;

	private Operator rename(Operator theOperator) {
		Operator newOperator = theOperator.getRenamedOperator(uniqueNum);
		uniqueNum = uniqueNum + 1;
		return newOperator;
	}

	/**
	 * ブロックの設定
	 * 
	 * @return
	 */
	public ArrayList<Block> initBlock() {
		BlockOp.addBlock("A", "red", "triangle");
		BlockOp.addBlock("B", "blue", "square");
		BlockOp.addBlock("C", "yellow", "square");
		BlockOp.addBlock("D", "green", "triangle");

		return BlockOp.list;
	}
	
	private static ArrayList<String> initGoalList() {
		ArrayList<String> goalList = new ArrayList<String>();
		/*
		goalList.add("A on B");
		goalList.add("B on C");
*/
		goalList.add("square on blue");
		return goalList;
	}

	private static ArrayList<String> initInitialState() {
		ArrayList<String> initialState = new ArrayList<String>();
		/*
		initialState.add("clear B");
		initialState.add("ontable A");
		initialState.add("clear A");
		initialState.add("ontable B");
		initialState.add("clear C");
		initialState.add("ontable C");
		*/
		initialState.add("ontable C");
		initialState.add("clear C");
		initialState.add("A on B");
		initialState.add("ontable B");
		initialState.add("clear A");
		initialState.add("handEmpty");

		return initialState;
	}

	/*
	 * ファイルからオペレータを読み込むメソッド ファイルの書き方の例は
	 * 
	 * NAME RULE IF pattern1 patten2 ADD addition DELETE remove
	 * 
	 * @param ファイル名
	 * 
	 * @ret 読み込み成功時は0,Exception時は-1,読み込み途中で失敗した場合は途中までの行数
	 */
	private int initOperators(String filename) {
		operators = new ArrayList<Operator>();
		// operators = new LinkedList<Operator>();
		try {
			BufferedReader bf = new BufferedReader(new FileReader(filename));

			String line = bf.readLine();
			int errorLine = 1;
			// System.out.println(errorLine +":"+line);
			while (true) {
				if (line == null) {
					return errorLine;
				}
				String name = null;
				ArrayList<String> theIfList = new ArrayList<String>();
				ArrayList<String> theAddList = new ArrayList<String>();
				ArrayList<String> theDeleteList = new ArrayList<String>();

				while (!line.startsWith("NAME")) {
					line = bf.readLine();
					errorLine++;
					System.out.println(errorLine + ":" + line);
					if (line == null) {
						return errorLine;
					}
				}
				name = (line.replace("NAME", "").trim());
				line = bf.readLine();
				errorLine++;
				// System.out.println(errorLine +":1"+line);
				if (line == null) {
					return errorLine;
				}
				line = line.trim();

				while (!line.startsWith("IF")) {
					line = bf.readLine();
					errorLine++;
					// System.out.println(errorLine +":"+line);
					if (line == null) {
						return errorLine;
					}
				}
				line = (line.replace("IF", "")).trim();
				while (line != null && !line.startsWith("ADD")
						&& !line.startsWith("DELETE")) {
					if (line.length() != 0) {
						theIfList.add(line);
					}
					line = bf.readLine();
					errorLine++;
					// System.out.println(errorLine +":"+line);
					if (line != null) {
						line = line.trim();
					}
				}

				if (line != null && line.startsWith("ADD")) {
					line = (line.replace("ADD", "")).trim();
					while (line != null && !line.startsWith("DELETE")
							&& !line.startsWith("NAME")) {
						if (line.length() != 0) {
							theAddList.add(line);
						}
						line = bf.readLine();
						errorLine++;
						// System.out.println(errorLine +":"+line);
						if (line != null) {
							line = line.trim();
						}
					}
				}

				if (line != null && line.startsWith("DELETE")) {
					line = (line.replace("DELETE", "")).trim();
					while (line != null && !line.startsWith("NAME")) {
						if (line.length() != 0) {
							theDeleteList.add(line);
						}
						line = bf.readLine();
						errorLine++;
						// System.out.println(errorLine +":"+line);
						if (line != null) {
							line = line.trim();
						}
					}
				}

				if (name != null
						&& theIfList != null
						&& (theAddList.size() != 0 || theDeleteList.size() != 0)) {
					operators.add(new Operator(name, theIfList, theAddList,
							theDeleteList));
					// operators.offer(new
					// Operator(name,theIfList,theAddList,theDeleteList));
					if (line == null) {
						break;
					}
				} else {
					bf.close();
					// ERROR
					return errorLine;
				}
			}
			bf.close(); // Reader を閉じる
			return 0;

		} catch (FileNotFoundException e) {
			e.printStackTrace();
			return -1;
		} catch (IOException e) {
			e.printStackTrace();
			return -1;
		}
	}

}

class Operator {
	String name;
	ArrayList<String> ifList;
	ArrayList<String> addList;
	ArrayList<String> deleteList;

	Operator(String theName, ArrayList<String> theIfList,
			ArrayList<String> theAddList, ArrayList<String> theDeleteList) {
		name = theName;
		ifList = theIfList;
		addList = theAddList;
		deleteList = theDeleteList;
	}

	public ArrayList<String> getAddList() {
		return addList;
	}

	public ArrayList<String> getDeleteList() {
		return deleteList;
	}

	public ArrayList<String> getIfList() {
		return ifList;
	}

	public String toString() {
		String result = "NAME: " + name + "\n" + "IF :" + ifList + "\n"
				+ "ADD:" + addList + "\n" + "DELETE:" + deleteList;
		return result;
	}

	public ArrayList<String> applyState(ArrayList<String> theState) {
		for (int i = 0; i < addList.size(); i++) {
			theState.add(addList.get(i));
		}
		for (int i = 0; i < deleteList.size(); i++) {
			theState.remove(deleteList.get(i));
		}
		return theState;
	}

	public Operator getRenamedOperator(int uniqueNum) {
		ArrayList<String> vars = new ArrayList<String>();
		// IfListの変数を集める
		for (int i = 0; i < ifList.size(); i++) {
			String anIf = (String) ifList.get(i);
			vars = getVars(anIf, vars);
		}
		// addListの変数を集める
		for (int i = 0; i < addList.size(); i++) {
			String anAdd = (String) addList.get(i);
			vars = getVars(anAdd, vars);
		}
		// deleteListの変数を集める
		for (int i = 0; i < deleteList.size(); i++) {
			String aDelete = (String) deleteList.get(i);
			vars = getVars(aDelete, vars);
		}
		Hashtable renamedVarsTable = makeRenamedVarsTable(vars, uniqueNum);

		// 新しいIfListを作る
		ArrayList<String> newIfList = new ArrayList<String>();
		for (int i = 0; i < ifList.size(); i++) {
			String newAnIf = renameVars((String) ifList.get(i),
					renamedVarsTable);
			newIfList.add(newAnIf);
		}
		// 新しいaddListを作る
		ArrayList<String> newAddList = new ArrayList<String>();
		for (int i = 0; i < addList.size(); i++) {
			String newAnAdd = renameVars((String) addList.get(i),
					renamedVarsTable);
			newAddList.add(newAnAdd);
		}
		// 新しいdeleteListを作る
		ArrayList<String> newDeleteList = new ArrayList<String>();
		for (int i = 0; i < deleteList.size(); i++) {
			String newADelete = renameVars((String) deleteList.get(i),
					renamedVarsTable);
			newDeleteList.add(newADelete);
		}
		// 新しいnameを作る
		String newName = renameVars(name, renamedVarsTable);

		return new Operator(newName, newIfList, newAddList, newDeleteList);
	}

	private ArrayList<String> getVars(String thePattern, ArrayList<String> vars) {
		StringTokenizer st = new StringTokenizer(thePattern);
		for (int i = 0; i < st.countTokens();) {
			String tmp = st.nextToken();
			if (var(tmp) || var2(tmp)) {
				vars.add(tmp);
			}
		}
		return vars;
	}

	private Hashtable makeRenamedVarsTable(ArrayList<String> vars, int uniqueNum) {
		Hashtable result = new Hashtable();
		for (int i = 0; i < vars.size(); i++) {
			String newVar = (String) vars.get(i) + uniqueNum;
			result.put((String) vars.get(i), newVar);
		}
		return result;
	}

	private String renameVars(String thePattern, Hashtable renamedVarsTable) {
		String result = new String();
		StringTokenizer st = new StringTokenizer(thePattern);
		for (int i = 0; i < st.countTokens();) {
			String tmp = st.nextToken();
			if (var(tmp) || var2(tmp)) {
				result = result + " " + (String) renamedVarsTable.get(tmp);
			} else {
				result = result + " " + tmp;
			}
		}
		return result.trim();
	}

	public Operator instantiate(HashMap<String, String> theBinding) {
		// name を具体化
		String newName = instantiateString(name, theBinding);
		// ifList を具体化
		ArrayList<String> newIfList = new ArrayList<String>();
		for (int i = 0; i < ifList.size(); i++) {
			String newIf = instantiateString((String) ifList.get(i), theBinding);
			newIfList.add(newIf);
		}
		// addList を具体化
		ArrayList<String> newAddList = new ArrayList<String>();
		for (int i = 0; i < addList.size(); i++) {
			String newAdd = instantiateString((String) addList.get(i),
					theBinding);
			newAddList.add(newAdd);
		}
		// deleteListを具体化
		ArrayList<String> newDeleteList = new ArrayList<String>();
		for (int i = 0; i < deleteList.size(); i++) {
			String newDelete = instantiateString((String) deleteList.get(i),
					theBinding);
			newDeleteList.add(newDelete);
		}
		return new Operator(newName, newIfList, newAddList, newDeleteList);
	}

	private String instantiateString(String thePattern,
			HashMap<String, String> theBinding) {
		String result = new String();
		StringTokenizer st = new StringTokenizer(thePattern);
		for (int i = 0; i < st.countTokens();) {
			String tmp = st.nextToken();
			if (var(tmp) || var2(tmp)) {
				String newString = (String) theBinding.get(tmp);
				if (newString == null) {
					result = result + " " + tmp;
				} else {
					result = result + " " + newString;
				}
			} else {
				result = result + " " + tmp;
			}
		}
		return result.trim();
	}

	private boolean var(String str1) {
		// 先頭が ? なら変数
		return str1.startsWith("?");
	}

	private boolean var2(String str1) {
		// ブロックの要素（色、形）なら変数
		//return BlockOp.elements.contains(str1);
		Iterator ite = BlockOp.elements.iterator();
		while(ite.hasNext()) {
			if(str1.startsWith((String) ite.next())) {
				return true;
			}
		}
		return false;
	}
}

class Unifier {
	StringTokenizer st1;
	String buffer1[];
	StringTokenizer st2;
	String buffer2[];
	HashMap<String, String> vars;

	Unifier() {
		vars = new HashMap<String, String>();
	}

	public boolean unify(String string1, String string2,
			HashMap<String, String> theBindings) {
		HashMap<String, String> orgBindings = new HashMap<String, String>();
		for (Iterator<String> i = theBindings.keySet().iterator(); i.hasNext();) {
			String key = i.next();
			String value = theBindings.get(key);
			orgBindings.put(key, value);
		}
		this.vars = theBindings; // //これがポインタ代入なら理解できる
		if (unify(string1, string2)) {
			// //更新しなくていいのか？
			return true;
		} else {
			// 失敗したら元に戻す．
			theBindings.clear();
			for (Iterator<String> i = orgBindings.keySet().iterator(); i
					.hasNext();) {
				String key = i.next();
				String value = orgBindings.get(key);
				theBindings.put(key, value);
			}
			return false;
		}
	}

	public boolean unify(String string1, String string2) {
		
		// 同じなら成功
		if (string1.equals(string2))
			return true;

		// 各々トークンに分ける
		st1 = new StringTokenizer(string1);
		st2 = new StringTokenizer(string2);

		// 数が異なったら失敗
		if (st1.countTokens() != st2.countTokens())
			return false;

		// 定数同士
		int length = st1.countTokens();
		buffer1 = new String[length];
		buffer2 = new String[length];
		for (int i = 0; i < length; i++) {
			buffer1[i] = st1.nextToken();
			buffer2[i] = st2.nextToken();
		}

		// 初期値としてバインディングが与えられていたら
		if (this.vars.size() != 0) {
			for (Iterator<String> i = vars.keySet().iterator(); i.hasNext();) {
				String key = i.next();
				String value = vars.get(key);
				replaceBuffer(key, value);
			}
		}

		for (int i = 0; i < length; i++) {
			if (!tokenMatching(buffer1[i], buffer2[i])) {
				return false;
			}
		}

		return true;
	}

	boolean tokenMatching(String token1, String token2) {
		if (token1.equals(token2))
			return true;
		if (var(token1) && !var(token2))
			return varMatching(token1, token2);
		if (!var(token1) && var(token2))
			return varMatching(token2, token1);
		if (var(token1) && var(token2))
			return varMatching(token1, token2);
		if (var2(token1) && !var2(token2))
			return blockMatching(token1, token2);
		if (!var2(token1) && var2(token2))
			return blockMatching(token2, token1);
		if (var2(token1) && var2(token2))
			return varMatching(token1, token2);
		if (var(token1) && var2(token2))
			return varMatching(token1, token2);
		if (var2(token1) && var(token2))
			return varMatching(token1, token2);
		return false;
	}

	
	/*
	 	boolean tokenMatching(String token1, String token2) {
		if (token1.equals(token2))
			return true;
		if (var(token1) && !var(token2))
			return varMatching(token1, token2);
		if (!var(token1) && var(token2))
			return varMatching(token2, token1);
		if (var(token1) && var(token2))
			return varMatching(token1, token2);
		if (var2(token1) && !var2(token2))
			return blockMatching(token1, token2);
		if (!var2(token1) && var2(token2))
			return blockMatching(token2, token1);

		return false;
	}
	 */
	boolean varMatching(String vartoken, String token) {
		if (vars.containsKey(vartoken)) {
			if (token.equals(vars.get(vartoken))) {
				return true;
			} else {
				return false;
			}
		} else {
			replaceBuffer(vartoken, token);
			if (vars.containsValue(vartoken)) {
				replaceBindings(vartoken, token);
			}
			vars.put(vartoken, token);
		}
		return true;
	}

	boolean blockMatching(String vartoken, String token) {
		if (vars.containsKey(vartoken)) {
			if (token.equals(vars.get(vartoken))) {
				return true;
			} else {
				return false;
			}
		} else {
			if (BlockOp.isHave(token, vartoken)) {
				replaceBuffer(vartoken, token);
				if (vars.containsValue(vartoken)) {
					replaceBindings(vartoken, token);
				}
				vars.put(vartoken, token);
				//System.out.println(vars);
			} else {
				return false;
			}
		}
		return true;
	}

	void replaceBuffer(String preString, String postString) {
		for (int i = 0; i < buffer1.length; i++) {
			if (preString.equals(buffer1[i])) {
				buffer1[i] = postString;
			}
			if (preString.equals(buffer2[i])) {
				buffer2[i] = postString;
			}
		}
	}

	void replaceBindings(String preString, String postString) {
		for (Iterator<String> i = vars.keySet().iterator(); i.hasNext();) {
			String key = i.next();
			if (preString.equals(vars.get(key))) {
				vars.put(key, postString);
			}
		}
	}

	boolean var(String str1) {
		// 先頭が ? なら変数
		return str1.startsWith("?");
	}

	boolean var2(String str1) {
		// ブロックの要素（色、形）なら変数
		//return BlockOp.elements.contains(str1);
		Iterator ite = BlockOp.elements.iterator();
		while(ite.hasNext()) {
			if(str1.startsWith((String) ite.next())) {
				return true;
			}
		}
		return false;
	}
}