#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>

//----------------------------------------------------------------
// 注意：為了讓同學方便測試，本專案將所有程式碼放在同一個原始檔中
//----------------------------------------------------------------

// Gate 或 Signal「名稱」的最大字串長度
#define NAME_MAX_SIZE 6

// 代表一個 Gate 資訊的 struct
typedef struct GateType
{
	char szTypeName[NAME_MAX_SIZE];			// Gate 種類名稱
	int iNumOfInput;						// Gate Input 個數
	int iGateDelay;							// Gate Delay
} GateType;

// 代表 linked list 中一個 element 的 struct
typedef struct ListElement
{
	void *pvElement;						// 指向 element 內容物的指標
	struct ListElement *pleNext;			// 指向下一個 element 的指標
} ListElement;

// 代表一個 Signal 的 struct
typedef struct Signal
{
	char szSignalName[NAME_MAX_SIZE];		// Signal 名稱
	int iNumOfFanins;						// Fanin 個數
	int iSelfDelay;							// 本身的 Gate Delay
	int iAccumulateDelay;					// 在這個 Signal 上所累積的 Gate Delay
	ListElement *pleCriticalFanins;			// 在 Critical Path 上的前一個 Signal (linked list)
	ListElement *pleUnProcessedFanouts;		// 還未計算 Gate Delay 的下一個 Signal (linked list)
} Signal;

// 全域變數
// 為了減少各個函式的參數個數，維持程式碼簡潔，因此這裡採用一些全域變數
int g_iNumOfGateTypes;						// Gate 種類數
GateType *g_pgtAllGateTypes = 0;			// 儲存所有 Gate 資訊的陣列
ListElement *g_pleAllSignals = 0;			// 儲存所有 Signal 的 linked list
ListElement *g_pleSignalsToProcess = 0;		// 儲存所有待計算的 Signal 的 linked list
ListElement *g_pleCircuitOutputSignals = 0;	// 儲存所有 Circuit Output Signal 的 linked list

// 從輸入檔 (Gates.txt) 讀取 Gate 資訊
// szGatesInputPath 參數指定輸入檔路徑
void ReadGatesInput(const char *szGatesInputPath)
{
	int iIter;
	FILE *fp;
	
	// 開啟輸入檔
	fp = fopen(szGatesInputPath, "r");

	// 取得 Gate 種類數
	fscanf(fp, "%d", &g_iNumOfGateTypes);

	// 配置陣列記憶體
	g_pgtAllGateTypes = (GateType*)malloc(sizeof(GateType) * g_iNumOfGateTypes);

	// 從輸入檔讀入所有的 Gate 資訊並存入陣列中
	for(iIter = 0; iIter < g_iNumOfGateTypes; ++iIter)
	{
		fscanf(fp, "%s", g_pgtAllGateTypes[iIter].szTypeName);
		fscanf(fp, "%d", &g_pgtAllGateTypes[iIter].iNumOfInput);
		fscanf(fp, "%d", &g_pgtAllGateTypes[iIter].iGateDelay);
	}

	// 關檔
	fclose(fp);
}

// 以 Gate 種類名稱尋找該 Gate 的資訊 (回傳其位址)
// szTypeName 參數指定 Gate 種類名稱
// 為維持程式碼簡潔與易讀，此處使用線性搜尋，如果 Gate 種類數目很大，
// 則為了加快搜尋速度，可以考慮建置雜湊表
GateType* FindGateType(const char *szTypeName)
{
	int iIter;

	// 在 Gate 陣列中尋找符合名稱的 Gate，並將其位址回傳
	for(iIter = 0; iIter < g_iNumOfGateTypes; ++iIter)
	{
		if(strcmp(g_pgtAllGateTypes[iIter].szTypeName, szTypeName) == 0)
			return g_pgtAllGateTypes + iIter;
	}

	// 如果找不到就回傳空指標
	return 0;
}

// 以 Signal 名稱尋找該 Signal 的資訊 (回傳位址)
// szSignalName 參數指定 Signal 名稱
// 為維持程式碼簡潔與易讀，此處使用線性搜尋，如果 Signal 個數很多，
// 則為了加快搜尋速度，可以考慮建置雜湊表
Signal* FindSignal(const char *szSignalName)
{
	ListElement *pleTraversal = g_pleAllSignals;
	Signal *psglTmp;

	// 走訪儲存所有 Signal 的 linked list，尋找符合名稱的 Signal，並將其位址回傳
	while(pleTraversal != 0)
	{
		psglTmp = (Signal*)pleTraversal->pvElement;
		pleTraversal = pleTraversal->pleNext;

		if(strcmp(psglTmp->szSignalName, szSignalName) == 0)
			return psglTmp;
	}

	// 如果找不到就回傳空指標
	return 0;
}

// 把一個新的 element 加入 linked list 的頭部
// ppleList 參數指定 linked list 的開頭位址之指標
// pvElement 參數指定 element 內容物的指標
void AddFirstElementToList(ListElement **ppleList, void *pvElement)
{
	// 記置新的記憶體以產生新的 element，並設定其內容物的指標
	ListElement *pleNew = (ListElement*)malloc(sizeof(ListElement));
	memset(pleNew, 0, sizeof(ListElement));
	pleNew->pvElement = pvElement;

	// 把新的 element 串接到 linked list 的頭部
	pleNew->pleNext = *ppleList;
	*ppleList = pleNew;
}

// 從 linked list 的頭部移除一個 element (回傳該 element 內容物的指標)
// ppleList 參數指定 linked list 的開頭位址之指標
void* RemoveFirstElementFromList(ListElement **ppleList)
{
	void *pvElement;
	ListElement *pleTmp;

	// 如果 linked list 是空的，就直接回傳空指標
	if(*ppleList == 0)
		return 0;

	// 修改 linked list 的開頭指標
	pleTmp = *ppleList;
	*ppleList = (*ppleList)->pleNext;

	// 取得被移除之 element 的內容物的指標
	pvElement = pleTmp->pvElement;

	// 釋放被移除之 element 的記憶體
	free(pleTmp);

	// 回傳被移除之 element 的內容物的指標
	return pvElement;
}

// 將 linked list 中的 element 全數移除
// ppleList 參數指定 linked list 的開頭位址之指標
void RemoveAllElementsFromList(ListElement **ppleList)
{
	while(*ppleList != 0)
		RemoveFirstElementFromList(ppleList);
}

// 將一個新的 Signal 加入所有 Signal 列表中，並設定其名稱 (回傳新的 Signal 之位址)
// 如果有相同名稱的 Signal 已經存在，就不會產生新的 Signal，只會回傳該 Signal 的位址
// szSignalName 參數指定 Signal 的名稱
Signal* AddNewSignal(const char *szSignalName)
{
	Signal *psglNew;

	// 判斷有相同名稱的 Signal 是否已經存在，存在的話就直接回傳其位址
	if((psglNew = FindSignal(szSignalName)) != 0)
		return psglNew;

	// 記置新的記憶體以產生新的 Signal，並設定其名稱，其他 member 則全部設為 0
	psglNew = (Signal*)malloc(sizeof(Signal));
	memset(psglNew, 0, sizeof(Signal));
	strcpy(psglNew->szSignalName, szSignalName);

	// 將新產生的 Signal 加到所有 Signal 列表中
	AddFirstElementToList(&g_pleAllSignals, psglNew);

	// 將新產生的 Signal 之位址回傳
	return psglNew;
}

// 從輸入檔 (Circuit.txt) 讀取 Signal 資訊
// szCircuitInputPath 參數指定輸入檔路徑
void ReadCircuitInput(const char *szCircuitInputPath)
{
	int iNumOfCircuitInput, iNumOfCircuitOutput, iNumOfGates, iIter, iIter1;
	Signal *psglNew, *psglOutput;
	char szNameBuf[NAME_MAX_SIZE];
	GateType *pgtTypeRead;
	FILE *fp;
	
	// 開啟輸入檔，讀取 Circuit 的 input、output 個數與 Gate 個數
	fp = fopen(szCircuitInputPath, "r");
	fscanf(fp, "%d%d%d", &iNumOfCircuitInput, &iNumOfCircuitOutput, &iNumOfGates);

	// 讀取 Circuit 的 input Signal 資訊
	for(iIter = 0; iIter < iNumOfCircuitInput; ++iIter)
	{
		fscanf(fp, "%s", szNameBuf);
		psglNew = AddNewSignal(szNameBuf);
		AddFirstElementToList(&g_pleSignalsToProcess, psglNew);
	}

	// 讀取 Circuit 的 output Signal 資訊
	for(iIter = 0; iIter < iNumOfCircuitOutput; ++iIter)
	{
		fscanf(fp, "%s", szNameBuf);
		psglNew = AddNewSignal(szNameBuf);
		AddFirstElementToList(&g_pleCircuitOutputSignals, psglNew);
	}

	// 讀取 Circuit 的內部 Gate 連接資訊
	for(iIter = 0; iIter < iNumOfGates; ++iIter)
	{
		// Gate 的 output Signal
		fscanf(fp, "%s", szNameBuf);
		psglOutput = AddNewSignal(szNameBuf);

		// 尋找該 Gate 的資訊
		fscanf(fp, "%s", szNameBuf);
		pgtTypeRead = FindGateType(szNameBuf);
		psglOutput->iNumOfFanins = pgtTypeRead->iNumOfInput;
		psglOutput->iSelfDelay = pgtTypeRead->iGateDelay;

		// Gate 的 input Signal
		for(iIter1 = 0; iIter1 < pgtTypeRead->iNumOfInput; ++iIter1)
		{
			fscanf(fp, "%s", szNameBuf);
			psglNew = AddNewSignal(szNameBuf);

			// 把 psglOutput 加入 psglNew 的待計算 Gate Delay 列表中
			AddFirstElementToList(&psglNew->pleUnProcessedFanouts, psglOutput);
		}
	}

	// 關檔
	fclose(fp);
}

// 從 Circuit 的 input Signal 開始，逐一推算從 Circuit input 開始，到每個 Signal 
// 間的最大累積 Gate Delay 總和，並記錄發生最大值時的 Critical Path
void FindCriticalPath()
{
	Signal *psglToProcess, *psglFanout;
	int iDelay;

	// 只要整個電路中還有 Signal 未確定其最大累積 Gate Delay 值，就要繼續計算
	while(g_pleSignalsToProcess != 0)
	{
		// 從待計算的 Signal 之 linked list 中取出一個 Signal 來計算
		// 一開始這個 linked list 中存的全都是 Circuit 的 input Signal
		psglToProcess = (Signal*)RemoveFirstElementFromList(&g_pleSignalsToProcess);

		// 逐一取出這個 Signal 所連接的 output Signal
		while(psglToProcess->pleUnProcessedFanouts != 0)
		{
			// 把這個 Signal 上所累積的 Gate Delay，加上這個 Signal 所連接的 Gate 之 Delay
			psglFanout = (Signal*)RemoveFirstElementFromList(&psglToProcess->pleUnProcessedFanouts);
			iDelay = psglToProcess->iAccumulateDelay + psglFanout->iSelfDelay;

			// 如果加總出來的值大於這個 Signal 所連接的 output Signal 原先的累積 Gate Delay
			// 表示這是一條新找到的 Critical Path
			if(iDelay > psglFanout->iAccumulateDelay)
			{
				// 更新 output Signal 上所記錄的最大累積 Gate Delay 值
				psglFanout->iAccumulateDelay = iDelay;

				// 清除 output Signal 上所記錄的 Critical Path 資訊
				// 並將此設為新的 Critical Path
				RemoveAllElementsFromList(&psglFanout->pleCriticalFanins);
				AddFirstElementToList(&psglFanout->pleCriticalFanins, psglToProcess);
			}
			// 如果加總出來的值等於這個 Signal 所連接的 output Signal 原先的累積 Gate Delay
			// 表示 output Signal 有多條 Critical Path，將此加入 Critical Path 列表中
			else if(iDelay == psglFanout->iAccumulateDelay)
			{
				AddFirstElementToList(&psglFanout->pleCriticalFanins, psglToProcess);
			}

			// 如果 output Signal 上的所有可能 input 都計算過了
			// 表示這個 output Signal 的最大累積 Gate Delay 已經確定不會再更動
			// 將此 output Signal 加入待計算的 Signal 之 linked list 中，以便讓計算工作向前推進
			if(--psglFanout->iNumOfFanins <= 0)
				AddFirstElementToList(&g_pleSignalsToProcess, psglFanout);
		}
	}
}

// 找出整個 Circuit 的 Critical Path 之累積 Gate Delay
int FindCriticalPathDelay()
{
	int iMaxDelay = -1;
	Signal *psglTmp;
	ListElement *pleTraversal = g_pleCircuitOutputSignals;

	// 走訪 Circuit 的所有 output Signal，找出裡面記錄的最大累積 Gate Delay 值
	while(pleTraversal != 0)
	{
		psglTmp = (Signal*)pleTraversal->pvElement;
		pleTraversal = pleTraversal->pleNext;

		if(psglTmp->iAccumulateDelay > iMaxDelay)
			iMaxDelay = psglTmp->iAccumulateDelay;
	}

	return iMaxDelay;
}

// 要列印 Critical Path 時，從 Circuit 的 output Signal 開始，往回找出 Critical Path 路徑
// ppleTraceBackList 參數指定一個 linked list 的開頭位址之指標，此 list 用來存放 back trace 時每個經過的 Signal
// psglDest 參數指定 back trace 時的出發點
// fp 參數指定將整條路徑列印出的檔案指標
void CriticalPathTraceBack(ListElement **ppleTraceBackList, Signal *psglDest, FILE *fp)
{
	Signal *psglTmp;
	ListElement *pleTraversal;

	// 如果在 back trace 的過程中，遇到一個 Signal 沒有記錄 CriticalFanins
	// 表示這個 Signal 是整個 Circuit 的 input Signal，代表已經 back trace 完一條 Critical Path
	// 這時候就要把整條 Critical Path 列印到檔案中
	if(psglDest->pleCriticalFanins == 0)
	{
		fprintf(fp, "\n");
		pleTraversal = *ppleTraceBackList;

		// 將 ppleTraceBackList 中的每一個 Signal 逐一印出
		while(pleTraversal != 0)
		{
			psglTmp = (Signal*)pleTraversal->pvElement;
			pleTraversal = pleTraversal->pleNext;
			fprintf(fp, "%s", psglTmp->szSignalName);

			// 如果不是路徑上的最後一個 Signal，就要在後面加一個空白字元作為欄位分隔
			if(pleTraversal != 0)
				fprintf(fp, " ");
		}

		return;
	}

	// 從 back trace 的出發點開始
	pleTraversal = psglDest->pleCriticalFanins;
	
	// 逐一取出該 Signal 中記錄的 Critical Path 中的前一個 Signal，存入 ppleTraceBackList 中
	// 以 recursive 方式 back trace
	while(pleTraversal != 0)
	{
		psglTmp = (Signal*)pleTraversal->pvElement;
		pleTraversal = pleTraversal->pleNext;

		AddFirstElementToList(ppleTraceBackList, psglTmp);
		CriticalPathTraceBack(ppleTraceBackList, psglTmp, fp);
		RemoveFirstElementFromList(ppleTraceBackList);
	}
}

// 將整個 Circuit 的 Critical Path 列印到輸出檔
// szOutputPath 參數指定輸出檔路徑
// iMaxDelay 參數指定 Critical Path 上的 Gate Delay 總和
void WriteCriticalPaths(const char *szOutputPath, int iMaxDelay)
{
	ListElement *pleTraceBackList = 0;
	ListElement *pleOutputTraversal = g_pleCircuitOutputSignals;
	Signal *psglOutput;
	FILE *fp;

	// 開啟輸出檔，並列印 Critical Path 上的 Gate Delay 總和
	fp = fopen(szOutputPath, "w");
	fprintf(fp, "%d", iMaxDelay);

	// 將每條 Critical Path 印出
	while(pleOutputTraversal != 0)
	{
		psglOutput = (Signal*)pleOutputTraversal->pvElement;
		pleOutputTraversal = pleOutputTraversal->pleNext;
		
		// 如果 Circuit 的某個 output Signal 記錄之 Gate Delay 總和與 iMaxDelay 相同
		// 表示它是一條 Critical Path 的 output Signal
		// 由此 Signal 開始 back trace 出整條 Critical Path
		if(psglOutput->iAccumulateDelay == iMaxDelay)
		{
			AddFirstElementToList(&pleTraceBackList, psglOutput);
			CriticalPathTraceBack(&pleTraceBackList, psglOutput, fp);
			RemoveFirstElementFromList(&pleTraceBackList);
		}
	}

	// 關檔
	fclose(fp);
}

// 將動態配置的記憶體釋放
void MemoryCleanup()
{
	Signal *psglTmp;

	// 釋放儲存所有 Gate 資訊的陣列
	free(g_pgtAllGateTypes);

	// 釋放每個 Signal 使用的記憶體，並釋放儲存所有 Signal 的 linked list
	while(g_pleAllSignals != 0)
	{
		psglTmp = (Signal*)RemoveFirstElementFromList(&g_pleAllSignals);
		RemoveAllElementsFromList(&psglTmp->pleCriticalFanins);
		RemoveAllElementsFromList(&psglTmp->pleUnProcessedFanouts);
		free(psglTmp);
	}

	// 釋放儲存所有待計算的 Signal 的 linked list (事實上此 list 應該已經是空的)
	RemoveAllElementsFromList(&g_pleSignalsToProcess);

	// 釋放儲存所有 Circuit Output Signal 的 linked list
	RemoveAllElementsFromList(&g_pleCircuitOutputSignals);
}

// 主程式
int main()
{
	// 讀取輸入檔
	ReadGatesInput("Gates.txt");
	ReadCircuitInput("Circuit.txt");

	// 計算 Critical Path
	FindCriticalPath();

	// 產生輸出檔
	WriteCriticalPaths("Output.txt", FindCriticalPathDelay());

	// 釋放記憶體
	MemoryCleanup();
	return 0;
}