/**
 * 基于狀態轉換矩陣表示的FA確定化、最小化并給出有限自動機的通用實現
 * @author Skypia0000
 *
 */

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

@SuppressWarnings(value = {"unchecked"})
public class ConfirmNFA {
	private String matrix_NFA[][];					/* 存放待確定化的非確定有限自動機的狀態轉換矩陣 */
	private String matrix_DFA[][];					/* 存放確定化后的狀態轉換矩陣 */
	private char input_SYM[];						/* 存放輸入符號，初始符號集包含e(在數組尾端)，確定化之后去掉e，長度減1 */
	private char endStatus_NFA[];				/* 存放NFA的終態集 */
	private String end_Status;

	private ArrayList c_Group;						/* 存放根據NFA構造出來的C子集 */

	private int len_SYMS;							/* 存放輸入符號長度，input_SYM數組的長度 */
	private int len_ENDSTNFA;					/* 存放NFA終態集的長度，endStatus_NFA數組的長度 */
	private int row_NFA, col_NFA;				/* 存放最初NFA狀態轉換矩陣(matrix_NFA)的行數及列數，其中col_NFA比實際矩陣列數小1  */
	private int index_CGroup;						/* 存放在c_Group中游走的下標 */
	private int counter;								/* 子集中的狀態計數器 */
	private int row_DFA, col_DFA;				/* 存放確定化之后的狀態轉換矩陣(matrix_DFA)行數及列數，其中col_DFA比實際矩陣列數小1*/

	/**
	 * DFA的最小化
	 * 思想：
	 * 1.首先去掉無用狀態: a.任何狀態都不能到達的狀態 b.從這個狀態沒有通路到達終態
	 * 2.合并等價狀態：
	 * 		a.一致性條件：狀態s和狀態t必須同時為可接受狀態(初態)或不可接受狀態(終態)
	 * 		b.蔓延性條件：對以所有輸入符號，狀態s和狀態t必須轉換到等價的狀態里
	 */
	public void miniDFA() {
		String start = "", end = "";					/* start為初態集，end為終態集 */
		boolean isUniform = true;
		ArrayList strOnly;								/* 存放P集合，與p_Group不同之處是只存放字符串，兒p_Group存放PStatus對象 */

		removeExcrescent();							/* 刪除無用狀態，未完全實現 */
		strOnly = divide();								/* 分割成初態集和終態集的列表 */
		start = strOnly.get(0).toString();			/* 初態集賦值 */
		end = strOnly.get(1).toString();			/* 終態集賦值 */

		/*
		 * 從狀態0開始與之后的每一個狀態進行匹配，如果有等價狀態則合并狀態
		 * 將與當前狀態等價的狀態
		 */
		while(isUniform) {
			for(int i = 0; i < row_DFA; i++) {						/* 當前狀態循環 */
				if(!matrix_DFA[i][0].equals("@")) {					/* 如果該狀態被合并，則跳過此狀態，繼續下一個狀態 */
					for(int j = i + 1; j < row_DFA; j++) {			/* 尋找與當前狀態等價的狀態的循環 */
						if(!matrix_DFA[j][0].equals("@")) {			/* 如果該狀態已被合并，則跳過此狀態，繼續下一個狀態 */
							String first = matrix_DFA[i][1];			/* 獲取當前狀態在第一個輸入符號下的跳轉狀態 */
							String next = matrix_DFA[j][1];			/* 獲取待匹配狀態在第一個輸入符號下的跳轉狀態 */
							/* 當前狀態和待匹配狀態的首個輸入符號下的跳轉狀態相同，當前狀態和待匹配狀態在同一個集合中(可接受或不可接受)*/
							if(first.equals(next) && ((start.contains(first) && start.contains(next)) || (end.contains(next) && end.contains(next)))) {//bug
								isUniform = true;
								for(int k = 2; k <= col_DFA; k++) {	/* 接續判斷之后所有輸入符號下跳轉狀態是否相同*/
									String first2 = matrix_DFA[i][k];		
									String next2 = matrix_DFA[j][k];
									if(!first2.equals(next2)) {					/* 如果在同一個輸入符號下，跳轉狀態不相同，則放棄繼續到下一個狀態 */
										isUniform = false;
										break;
									}
								}
								if(isUniform) {									/* 如果所有輸入下跳轉狀態都相同，則合并，即對待匹配狀態進行標記 */
									for(int m = 0; m < row_DFA; m++) {
										for(int n = 1; n <= col_DFA; n++) {
											if(matrix_DFA[m][n].equals(matrix_DFA[j][0])) {
												matrix_DFA[m][n] = matrix_DFA[i][0];
											}
										}
									}
									matrix_DFA[j][0] = "@";					/* 對待匹配狀態進行標記 */
									continue;
								}
							}
						}
					}
				}
			}	
		}

		/* 確定最小化DFA終態 */
		for(int i = 0; i < row_DFA; i++) {
			if(matrix_DFA[i][0].equals("@")) {continue;}
			if(end.contains(matrix_DFA[i][0])) {
				end_Status = matrix_DFA[i][0];
				break;
			}
		}
	}
	/**
	 * 將狀態子集分割成初態集和終態集
	 */
	public ArrayList divide() {
		String sStatus = "";								/* 初態集 */
		String eStatus = "";								/* 終態集 */
		ArrayList arrayList = new ArrayList();

		for(int i = 0; i < c_Group.size(); i++) {		/* 對C子集的每個元素(確定化之后的狀態集)進行檢測 */
			if(!((ClosureStatus)c_Group.get(i)).getST().equals("@")) {		/* 如果該狀態不是無用狀態，繼續執行 */
				int j;
				for(j = 0; j < len_ENDSTNFA; j++) {
					if(((ClosureStatus)c_Group.get(i)).getSTATUS().contains("" + endStatus_NFA[j])) {	/* 如果狀態集包含最初NFA的終態，則被加入到終態集 */
						eStatus += ((ClosureStatus)c_Group.get(i)).getST();			/* 將字符標記添加到終態集中 */
						break;
					}
				}
				if(j >= len_ENDSTNFA) {						/* 其余添加到初態集中 */
					sStatus += ((ClosureStatus)c_Group.get(i)).getST();
				}
			}
		}
		arrayList.add(sStatus);
		arrayList.add(eStatus);
		return arrayList;
	}
	/**
	 * 刪除無用狀態
	 * 用@做標記
	 */
	public void removeExcrescent() {
		for(int i = 1; i < row_DFA; i++) {
			if(!exit(matrix_DFA[i][0])) {
				matrix_DFA[i][0] = "@";
				((ClosureStatus)c_Group.get(i)).setST("@");
			}
		}
	}
	/**
	 * 判斷是否為無用狀態
	 * @param status
	 * @return
	 */
	public boolean exit(String status) {
		boolean exit = false;

		for(int i = 0; i < row_DFA; i++) {
			/* 檢查除自身以外的狀態  */
			if(!status.equals(matrix_DFA[i][0])) {
				for(int j = 1; j < col_DFA + 1; j++) {
					if(status.equals(matrix_DFA[i][j])) {
						exit = true;
						i = row_DFA;
						break;
					}
				}
			}
		}
		//haven't been completed..........
		if(exit) {

		}

		return exit;
	}

	/**
	 * 將確定化之后的狀態集用一個字符表示：0~9序列
	 */
	private void strToChar() {
		String moveStatus;							/* 存放子集成員在a輸入下的狀態轉換集 */
		String closureStatus;							/* 存放在moveStatus的閉包集 */
		row_DFA = c_Group.size();					/* 利用C子集族中的元素個數定義 */
		col_DFA = len_SYMS - 1;					/* 確定化之后去掉了輸入符號e，所以減1 */
		matrix_DFA = new String[row_DFA][col_DFA + 1];								/* + 1 是為了在每一行開頭存放狀態位 */

		for(int i = 0; i < c_Group.size(); i++) {/* 檢測所有狀態在所有輸入符號下的跳轉狀態，并重新構造狀態轉換矩陣 */
			ClosureStatus newCS = (ClosureStatus)c_Group.get(i);
			matrix_DFA[i][0] = newCS.getST();				/* 每一行開頭添加狀態標記 */
			String tempStr = newCS.getSTATUS();
			for(int j = 1; j <= col_DFA; j++) {
				moveStatus = move(tempStr, j, matrix_NFA);			/* 求狀態在J輸入下的跳轉狀態 */
				closureStatus = moveStatus;
				closureStatus = sort(removeEcho(closure(moveStatus, closureStatus, len_SYMS)));
				for(int k = 0; k < c_Group.size(); k++) {
					if(closureStatus.equals(((ClosureStatus)c_Group.get(k)).getSTATUS())) {
						matrix_DFA[i][j] = ((ClosureStatus)c_Group.get(k)).getST();
						break;
					}
				}
			}
		}
	}
	/**
	 * 將狀態集中的狀態從小到大排序
	 * @param str
	 * @return
	 */
	public String sort(String str){
		char[] s=str.toCharArray();
		String strs="";
		for(int i=0;i<str.length();i++) {
			char temp=s[str.length()-(1+i)];
			for(int j=str.length()-1;j>=1;j--){
				if(s[j]<s[j-1]){
					temp=s[j];
					s[j]=s[j-1];
					s[j-1]=temp;
				}
			}
		}
		for(int m=0;m<s.length;m++)
			strs+=s[m];
		return strs;
	}
	/**
	 * 刪除狀態集中重復的狀態
	 * @param str
	 * @return
	 */
	public String removeEcho(String str) {
		String tempStr = "";
		for(int i=0;i<str.length();i++){
			if(!tempStr.contains(String.valueOf(str.charAt(i)))) {
				tempStr+=String.valueOf(str.charAt(i));
			}
		}
		return tempStr;
	}
	/**
	 * 求一個狀態集在input輸入下的跳轉狀態