// CS235102 Data structure 2007
// program 3
// programmed by Liang-yu Chen
// find the critical path of a circuit
// most of the error-checking steps for file reading are omitted

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

// nodes in the circuit (linked list implementation)
typedef struct Node *NodePtr;
typedef struct Node {
	char name[6];		// node name
	int finishTime;		// its finish time (time to get this output ready)
	NodePtr next;		// next node in the circuit
} Node;

// a list of nodes (linked list implementation)
typedef struct NodeList *NodeListPtr;
typedef struct NodeList {
	NodePtr theNode;	// a pointer that points to the node
	NodeListPtr next;	// next node in the list
} NodeList;

// gate type (linked list implementation)
typedef struct GateType *GateTypePtr;
typedef struct GateType {
	char name[6];		// gate name
	int inputNum;		// number of input nodes
	int delay;			// gate delay
	GateTypePtr next;	// next gate type
} GateType;

// gates in the circuit (linked list implementation)
typedef struct Gate *GatePtr;
typedef struct Gate {
	NodeListPtr inputList;	// list of input nodes
	NodePtr output;			// output node
	short done;				// a flag that tells if this gate has computed its output finish time
	GateTypePtr type;		// gate type pointer
	GatePtr next;			// next gate in the circuit
} Gate;

// path node in the circuit (linked list implementation)
typedef struct PathHeader *PathHeaderPtr;
typedef struct PathHeader {
	NodeListPtr path;	// a list of nodes in the path
	PathHeaderPtr next;	// next path
} PathHeader;

// global variables
GateTypePtr gateTypeList, thisGateType;			// (stack) stores the gate types used in this circuit
GatePtr gateList, thisGate;						// (stack) stores all the gates in the circuit
NodePtr nodeList, thisNode;						// (stack) stores all the nodes in the circuit
PathHeaderPtr pathHeaderHead, pathHeaderTail;	// stores the path nodes in this circuit
PathHeaderPtr thisPathHeader;					// same as above
NodeListPtr thisNodeList;						// a node for the gate input list
NodeListPtr outputNodeList;						// stores the output node list
int inputNum, outputNum, gateNum;				// number of input / output / gate in the circuit
int maxCircuitDelay = 0;						// total delay of the circuit

// function prototypes
void readGates();
void readCircuit();
NodePtr findThisNode(char* name);
GateTypePtr findThisGateType(char* name);
void freeEverything();
void outputResult();
void findMaxCircuitDelay();
void findCriticalPath();
void computeGateFinishTime();

int main()
{
	// read from gates file
	readGates();

	// read from circuit file
	readCircuit();

	// compute all gate finish time
	computeGateFinishTime();

	// find max circuit delay
	findMaxCircuitDelay();

	// find critical path
	findCriticalPath();

	// output the results
	outputResult();

	// free memory here
	freeEverything();

	return 0;
}

//-------------------------------------------------------------------------------------
// some functions...
//-------------------------------------------------------------------------------------

// read from Gates.txt
void readGates()
{
	FILE *fpGates;			// Gates file pointer
	int i;					// loop index
	int num1, num2, num3;	// temporary storage for numbers read from file
	char str1[6];			// temporary storage for strings read from file

	// open file to read
	if ((fpGates = fopen("Gates.txt", "rt")) == NULL){
		fprintf(stderr, "ERROR: fail to read from Gates.txt\n");
		freeEverything();
		exit(-1);
	}

	// number of gate types
	fscanf(fpGates, "%d", &num1);

	// read each gate type definition
	gateTypeList = NULL;
	for (i = 0; i < num1; i++) {
		// read gate type name, number of input, delay time
		fscanf(fpGates, "%s %d %d", str1, &num2, &num3);
		thisGateType = (GateTypePtr) malloc( sizeof(GateType) );
		strcpy(thisGateType->name, str1);
		thisGateType->inputNum = num2;
		thisGateType->delay = num3;
		thisGateType->next = gateTypeList;
		gateTypeList = thisGateType;
	}

	fclose(fpGates);
}

// read from Circuit.txt
void readCircuit()
{
	FILE *fpCircuit;	// Circuit.txt file pointer
	int i, j;				// loop indices
	char str1[6];		// temporary storage for strings read from file

	// open file to read
	if ((fpCircuit = fopen("Circuit.txt", "rt")) == NULL){
		fprintf(stderr, "ERROR: fail to read from Circuit.txt\n");
		freeEverything();
		exit(-1);
	}

	// read number of input, number of output, number of gates
	fscanf(fpCircuit,"%d %d %d", &inputNum, &outputNum, &gateNum);

	// read input nodes
	nodeList = NULL;
	for (i = 0; i < inputNum; i++){
		fscanf(fpCircuit, "%s", str1);
		thisNode = (NodePtr) malloc(sizeof(Node));
		strcpy(thisNode->name, str1);
		thisNode->finishTime = 0;
		thisNode->next = nodeList;
		nodeList = thisNode;
	}

	// read output nodes (check if the output node is also an input node)
	outputNodeList = NULL;
	for (i = 0; i < outputNum; i++){
		fscanf(fpCircuit, "%s", str1);
		if ((thisNode = findThisNode(str1)) == NULL){
			// this node is not found in the input node list, put it into the node list
			thisNode = (NodePtr) malloc(sizeof(Node));
			strcpy(thisNode->name, str1);
			thisNode->finishTime = -1; // not determined yet
			thisNode->next = nodeList;
			nodeList = thisNode;
		}

		// store this node into the output node list
		thisNodeList = (NodeListPtr) malloc( sizeof(NodeList) );
		thisNodeList->theNode = thisNode;
		thisNodeList->next = outputNodeList;
		outputNodeList = thisNodeList;
	}

	// read gates info
	for (i = 0; i < gateNum; i++){
		// read gate output
		fscanf(fpCircuit, "%s", str1);
		if ((thisNode = findThisNode(str1)) == NULL){
			// node not found, create a new one
			thisNode = (NodePtr) malloc(sizeof(Node));
			strcpy(thisNode->name, str1);
			thisNode->finishTime = -1; // not determined yet
			thisNode->next = nodeList;
			nodeList = thisNode;
		}

		// read gate type
		fscanf(fpCircuit, "%s", str1);
		if (gateList) { // previous gate exists
			thisGate = (GatePtr) malloc( sizeof(Gate) );
			thisGate->done = 0; // not producing any output yet
			thisGate->output = thisNode;
			thisGate->type = findThisGateType(str1);
			if (thisGate->type == NULL){ // gate type not found
				freeEverything();
				fprintf(stderr, "ERROR: gate type \"%s\" is not found!!!\n", str1);
				fclose(fpCircuit);
				exit(-1);
			}
			thisGate->next = gateList;
			gateList = thisGate;
		} else { // this is the first gate in the list
			gateList = (GatePtr) malloc( sizeof(Gate) );
			gateList->done = 0; // not producing any output yet
			gateList->output = thisNode;
			gateList->type = findThisGateType(str1);
			if (gateList->type == NULL){ // gate type not found
				freeEverything();
				fprintf(stderr, "ERROR: gate type \"%s\" is not found!!!\n", str1);
				fclose(fpCircuit);
				exit(-1);
			}
			gateList->next = NULL;
		}

		// read gate input list
		gateList->inputList = NULL;
		for (j = 0; j < gateList->type->inputNum; j++){
			fscanf(fpCircuit, "%s", str1);
			if ((thisNode = findThisNode(str1)) == NULL){
				// node not found, create a new node
				thisNode = (NodePtr) malloc( sizeof(Node) );
				strcpy(thisNode->name, str1);
				thisNode->finishTime = -1; // not determined yet
				thisNode->next = nodeList;
				nodeList = thisNode;
			}

			// create node for gate input list
			thisNodeList = (NodeListPtr) malloc( sizeof(NodeList) );
			thisNodeList->theNode = thisNode;
			thisNodeList->next = gateList->inputList;
			gateList->inputList = thisNodeList;
		}
	}

	fclose(fpCircuit);
}

// find the node by its name, and return its pointer or NULL if not found
NodePtr findThisNode(char* name)
{
	NodePtr thisNode = nodeList;

	while (thisNode != NULL){
		if (strcmp(thisNode->name, name)==0) // found it!!!
			return thisNode;
		else
			thisNode = thisNode->next;
	}

	return NULL; // not found
}

// find the gate type by its name and return its pointer or NULL if not found
GateTypePtr findThisGateType(char* name)
{
	GateTypePtr thisGateType = gateTypeList;

	while (thisGateType != NULL){
		if (strcmp(thisGateType->name, name)==0) // found it!!!
			return thisGateType;
		else
			thisGateType = thisGateType->next;
	}

	return NULL;
}

// free four lists used in the program
// and free the input list used in the gate list!!!
void freeEverything()
{
	for ( ; gateTypeList != NULL; gateTypeList = thisGateType){
		thisGateType = gateTypeList->next;
		free(gateTypeList);
	}

	for ( ; gateList != NULL; gateList = thisGate){
		thisGate = gateList->next;
		// free input list first!!!
		for ( ; gateList->inputList != NULL; gateList->inputList = thisNodeList){
			thisNodeList = gateList->inputList->next;
			free(gateList->inputList);
		}
		free(gateList);
	}

	for ( ; nodeList != NULL; nodeList = thisNode){
		thisNode = nodeList->next;
		free(nodeList);
	}

	for ( ; pathHeaderHead != NULL; pathHeaderHead = thisPathHeader){
		thisPathHeader = pathHeaderHead->next;
		// free path node first!!!
		for ( ; pathHeaderHead->path != NULL; pathHeaderHead->path = thisNodeList){
			thisNodeList = pathHeaderHead->path->next;
			free(pathHeaderHead->path);
		}
		free(pathHeaderHead);
	}

	for ( ; outputNodeList != NULL; outputNodeList = thisNodeList){
		thisNodeList = outputNodeList->next;
		free(outputNodeList);
	}
}

// compute all gate finish time
void computeGateFinishTime()
{
	int numGateDone = 0;	// number of gates that are done with computing its finish time
	short gotAll;			// a flag that tells if a gate has all of its input finish time
	int fTime;				// finish time of a gate

	while (numGateDone != gateNum){
		thisGate = gateList;
		for ( ; thisGate != NULL; thisGate = thisGate->next){
			if (thisGate->done == 1) // this gate has been processed before
				continue;

			// check if this gate has all of its input finish time
			thisNodeList = thisGate->inputList;
			gotAll = 1; // true
			fTime = 0;
			for ( ; thisNodeList != NULL; thisNodeList = thisNodeList->next){
				if (thisNodeList->theNode->finishTime == -1){ // not done yet
					gotAll = 0; // false
					break;
				}
				if (thisNodeList->theNode->finishTime > fTime)
					fTime = thisNodeList->theNode->finishTime;
			}
			if (gotAll){ // all input signals are ready!!!
				thisGate->output->finishTime = fTime + thisGate->type->delay;
				thisGate->done = 1;
				numGateDone++;
				if (numGateDone == gateNum)
					break; // every gate has been processed, quit immediately
			}
		}
	}
}

// fidn max circuit delay
void findMaxCircuitDelay()
{
	maxCircuitDelay = 0;
	for (thisNodeList = outputNodeList; thisNodeList != NULL; thisNodeList = thisNodeList->next)
		if (thisNodeList->theNode->finishTime > maxCircuitDelay)
			maxCircuitDelay = thisNodeList->theNode->finishTime;
}

// find and construct all critical paths of a circuit
void findCriticalPath()
{
	int i;					// loop index
	int maxTime;			// the max finish time of a particular level
	short foundFirstInput;	// a flag that tells if the first input node has been found
	NodeListPtr newNodeList;	// newly created node list
	NodeListPtr thisNodeList2, thisNodeList3;	// used as loop indices

	// find all output nodes that have this max circuit delay
	for (thisNodeList = outputNodeList; thisNodeList != NULL; thisNodeList = thisNodeList->next){
		if (thisNodeList->theNode->finishTime != maxCircuitDelay)
			continue;

		// create new node list for the path
		newNodeList = (NodeListPtr) malloc( sizeof(NodeList) );
		newNodeList->theNode = thisNodeList->theNode;
		newNodeList->next = NULL;
		// create a new path header
		if (pathHeaderHead){ // previous path header exists
			thisPathHeader = (PathHeaderPtr) malloc( sizeof(PathHeader) );
			thisPathHeader->path = newNodeList;
			thisPathHeader->next = NULL;
			pathHeaderTail->next = thisPathHeader;
			pathHeaderTail = thisPathHeader;
		} else { // this is the first path header
			pathHeaderHead = (PathHeaderPtr) malloc( sizeof(PathHeader) );
			pathHeaderHead->path = newNodeList;
			pathHeaderHead->next = NULL;
			pathHeaderTail = pathHeaderHead;
		}
	}

	// process the rest of the node of a path (or many paths)
	// if a branch is found, the new branched path is appended at its end
	pathHeaderTail = pathHeaderHead; // this denotes of currently processed path, all previous paths have been processed
	while (pathHeaderTail != NULL){
		maxTime = pathHeaderTail->path->theNode->finishTime; // current finish time, = 0 if completed
		while (maxTime != 0){
			// find the gate that owns this output node (assume that only one gate has this as its output)
			for (thisGate = gateList; thisGate != NULL; thisGate = thisGate->next)
				if (thisGate->output == pathHeaderTail->path->theNode)
					break;
			if (thisGate == NULL){ // can't find this output node, what the hell....
				fprintf(stderr, "ERROR: can't find this output node \"%s\" from any gates!\n", pathHeaderTail->path->theNode->name);
				freeEverything();
				exit(-1);
			}
			// find max finish time of a level
			maxTime = 0;
			for (thisNodeList = thisGate->inputList; thisNodeList != NULL; thisNodeList = thisNodeList->next)
				if (thisNodeList->theNode->finishTime > maxTime)
					maxTime = thisNodeList->theNode->finishTime;
			// find all input nodes with this max finish time
			foundFirstInput = 0; // false, not found anything yet
			for (thisNodeList = thisGate->inputList; thisNodeList != NULL; thisNodeList = thisNodeList->next)
				if (thisNodeList->theNode->finishTime == maxTime) // found it
					if (foundFirstInput){ // found a branch, create a new path header!!!!!
						// create a new node list
						newNodeList = (NodeListPtr) malloc( sizeof(NodeList) );
						newNodeList->theNode = thisNodeList->theNode;
						newNodeList->next = NULL;
						// create a new path header
						thisPathHeader = (PathHeaderPtr) malloc( sizeof(PathHeader) );
						thisPathHeader->path = newNodeList;
						thisPathHeader->next = pathHeaderTail->next; // appending ...
						pathHeaderTail->next = thisPathHeader;		 // appending ...
						// put the rest of the path into this new path header
						thisNodeList2 = pathHeaderTail->path->next; // skip the first node
						thisNodeList3 = thisPathHeader->path;
						for ( ; thisNodeList2 != NULL; thisNodeList2 = thisNodeList2->next){
							newNodeList = (NodeListPtr) malloc( sizeof(NodeList) );
							newNodeList->theNode = thisNodeList2->theNode;
							newNodeList->next = NULL;
							thisNodeList3->next = newNodeList;
							thisNodeList3 = newNodeList;
						}
					} else { // this is the first input node
						foundFirstInput = 1; // toggle flag to 1 for finding the first input node
						// create a new node list
						newNodeList = (NodeListPtr) malloc( sizeof(NodeList) );
						newNodeList->theNode = thisNodeList->theNode;
						newNodeList->next = pathHeaderTail->path;
						pathHeaderTail->path = newNodeList;
					}
		}

		// proceed to the next path header in the list
		pathHeaderTail = pathHeaderTail->next;
	}
}

// output the results (longest delay and all critical paths)
void outputResult()
{
	FILE *fpOutput;		// output file pointer

	// open file to write
	if ((fpOutput = fopen("Output.txt", "wt")) == NULL){
		fprintf(stderr, "ERROR: fail to write to Output.txt\n");
		freeEverything();
		exit(-1);
	}

	// output max circuit delay time
	fprintf(fpOutput, "%d\n", maxCircuitDelay);

	// output all critical paths
	for (thisPathHeader = pathHeaderHead; thisPathHeader != NULL; thisPathHeader = thisPathHeader->next){
		thisNodeList = thisPathHeader->path;
		fprintf(fpOutput, "%s", thisNodeList->theNode->name);
		for (thisNodeList = thisPathHeader->path->next ; thisNodeList != NULL; thisNodeList = thisNodeList->next){
			fprintf(fpOutput, " %s", thisNodeList->theNode->name);
		}
		fprintf(fpOutput, "\n");
	}

	fclose(fpOutput);
}
