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

public class Planner {
	ArrayList<Operator> operators;
	static ArrayList<Operator> preInstantiations;
	Random rand;
	ArrayList<Operator> plan;

	BlockOp bop = new BlockOp();
	
	public static void main(String argv[]) {
		(new Planner()).start();
	}

	/**
	 * コンストラクタ
	 */
	Planner() {
		rand = new Random();
		preInstantiations = new ArrayList<Operator>();
	}

	/**
	 * プログラムをスタートさせる
	 */
	public void start() {
		//オペレーターの読み込み
		System.out.println(initOperators("operator.txt"));
		System.out.println(operators);
		
		//ブロックの初期化
		ArrayList<Block> blockList = initBlock();
		// ゴールリストの初期化
		ArrayList<String> goalList = initGoalList();
		// 状態リストの初期化
		ArrayList<String> initialState = initInitialState();

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

		// プランニングの実行
		if (planning(goalList, initialState, theBinding)) {
			//プランニング成功
			System.out.println("***** This is a plan! *****");
			for (int i = 0; i < plan.size(); i++) {
				Operator op = (Operator) plan.get(i);
				System.out.println((op.instantiate(theBinding)).name);
			}
		} else {
			//プランニング失敗
			System.out.println(false);
		}
	}

	/**
	 * プランニングを実行する
	 * 
	 * @param theGoalList
	 * @param theCurrentState
	 * @param theBinding
	 * @return
	 */
	private boolean planning(ArrayList<String> theGoalList,
			ArrayList<String> theCurrentState,
			HashMap<String, String> theBinding) {
		System.out.println("*** GOALS ***" + theGoalList);
		
		//ゴールリストがカレントステイとに全て含まれていた時
		if (theCurrentState.containsAll(theGoalList))
			return true;

		//ゴールリストが1つの時
		if (theGoalList.size() == 1) {
			// ゴールリストの先頭を取り出す
			String aGoal = (String) theGoalList.get(0);
			//プランニング
			if (planningAGoal(aGoal, theCurrentState, theBinding, 0) != -1) {
				return true;
			} else {
				return false;
			}

		} else {//ゴールリストが複数の時
			// ゴールリストの先頭を取り出す
			String aGoal = (String) theGoalList.get(0);
			theGoalList.remove(0);

			int cPoint = 0;
			// Store original binding
			// theBindingをorgBindingにコピー
			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);
			}
			// theCurrentStateをorgStateにコピー
			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,
					cPoint);
			if (tmpPoint == 1) {
				if (theCurrentState.containsAll(theGoalList)) {
					return true;
				} else {
					theGoalList.add(aGoal);
					for (int i = 0; i < theGoalList.size(); ++i) {
						String st = theGoalList.get(0);
						theGoalList.remove(0);
						st = instantiateString(st, theBinding);
						theGoalList.add(st);
					}
					return planning(theGoalList, theCurrentState, theBinding);
				}
			} else if (tmpPoint == 0) {
				if (theCurrentState.containsAll(theGoalList)) {
					return true;
				}
				int size = theGoalList.size();
				/*
				 * ArrayList<String> orgGoals = new ArrayList<String>(); for(int
				 * i = 0; i < size; ++i){ orgGoals.add(theGoalList.get(i)); }
				 * System.out.println("bsefor :"+theGoalList);
				 */
				theGoalList.add(aGoal);
				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("after :"+theGoalList);
				 */
				System.out.println(theCurrentState);
				System.out.println(theBinding);
				if (planning(theGoalList, theCurrentState, theBinding)) {
					return true;
				} else {

					cPoint = tmpPoint;

					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;
		}
	}

	/**
	 * プランニング
	 * 
	 * @param theGoal
	 * @param theCurrentState
	 * @param theBinding
	 * @param cPoint
	 * @return 
	 */
	private int planningAGoal(String theGoal,
			ArrayList<String> theCurrentState,
			HashMap<String, String> theBinding, int cPoint) {
		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;
			}
		}
		/*
		 * int randInt = Math.abs(rand.nextInt()) % operators.size(); Operator
		 * op = (Operator)operators.get(randInt); operators.remove(randInt);
		 * operators.add(op);
		 */

		HashMap<Operator, HashMap<String, String>> conflictSet = new HashMap<Operator, HashMap<String, String>>();
		// 現在の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));
		}

		System.out.print("Conflict :");
		for (int i = 0; i < operators.size(); i++) {
			Operator anOperator = rename((Operator) operators.get(i));
			ArrayList<String> addList = anOperator.getAddList();

			for (int j = 0; j < addList.size(); j++) {
				HashMap<String, String> tmpBinding = (HashMap<String, String>) theBinding
						.clone();
				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);
				}
			}
		}
		//addListとゴールがマッチするオペレーターが無い時
		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());
					// preInstantiations.add(newOperator);
					plan.add(newOperator);
					theCurrentState = newOperator.applyState(theCurrentState);
					// theBinding.clear();
					// theBinding = newBinding;
					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);
	}

	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);
				// Operator instantiateKey = key.instantiate(value);

				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 if(key.getDeleteList().contains(theGoal)){
				} 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 HashMap<Operator, HashMap<String, String>> shuffle(
			HashMap<Operator, HashMap<String, String>> table) {
		if (table.size() == 0 || table.size() == 1)
			return table;
		HashMap<Operator, HashMap<String, String>> result = new HashMap<Operator, HashMap<String, String>>();
		Iterator e = table.keySet().iterator();
		ArrayList<Operator> list = new ArrayList<Operator>();
		while (e.hasNext()) {
			list.add((Operator) e.next());
		}
		int randInt = Math.abs(rand.nextInt()) % list.size();
		Operator op = (Operator) list.get(randInt);
		list.remove(randInt);
		list.add(op);
		for (int i = 0; i < list.size(); ++i) {
			result.put(list.get(i), table.get(list.get(i)));
		}
		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);
	}

	int uniqueNum = 0;

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

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

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

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

		initialState.add("ontable A");
		initialState.add("C on B");
		initialState.add("ontable D");
		*/
		initialState.add("clear C");
		initialState.add("ontable C");
		initialState.add("A on B");
		initialState.add("clear A");
		initialState.add("ontable B");
		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);
	}
}

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);

		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 (new 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);
	}
	
}