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

#define TOTAL_NODES 30

struct stackNode {
	int Name;
	struct stackNode *nextPtr;
};
typedef struct stackNode StackNode;
typedef StackNode *StackNodePtr;

void printStack(StackNodePtr, int);
void push(StackNodePtr *, StackNodePtr *);
int pop(StackNodePtr *);
int isEmpty(StackNodePtr);
void initialStackPtr(StackNodePtr *, int);


struct checkList {
	int Location;
	struct checkList *nextPtr;
};
typedef struct checkList CheckList;
typedef CheckList *CheckListPtr;

void initializeCheckList(void);
void checkListMalloc(CheckListPtr *, CheckListPtr *, int);
void addCheck(CheckListPtr *, int); //add to check list
int popCheck(CheckListPtr *);  //Start to search paths from the check list
int checkisEmpty(CheckListPtr); //check list is empty


struct Map {
	int Name;
	int Dist1, Dist2, Dist3, Dist4, Dist5;
	int numberofPath;
	struct Map *Ptr1;
	struct Map *Ptr2;
	struct Map *Ptr3;
	struct Map *Ptr4;
	struct Map *Ptr5;
};
typedef struct Map map;
typedef map *mapPtr;

void initializeMap(mapPtr *, int);
void addMap(mapPtr *, const int [][2], int, int);


//There are possibilities that the shortest path stack, 'stackPtr[]' will loop back.
//Therefore in order to avoid the problem, if two connected Nodes share the same
//shortest routes, they must be exclude from the path search map.
struct specialcase {
	int case1, case2;
	struct specialcase *nextPtr;
};
typedef struct specialcase specialCase;
typedef specialCase *specialCasePtr;

void prestageCheck(mapPtr *);
void special_Cases(void);

void searchRoutes(const mapPtr [], int);

StackNodePtr stackPtr[TOTAL_NODES];
int shortest[TOTAL_NODES];
CheckListPtr listPtr = NULL;

int main()
{
	int i, j, numberofPaths;
	mapPtr currPtr = NULL;
	mapPtr myPath[TOTAL_NODES];

	for(i=0; i<TOTAL_NODES; i++) {
		stackPtr[i] = NULL;
		shortest[TOTAL_NODES];
		initialStackPtr(&stackPtr[i], i);
	}

	FILE *cfPtr;
	if( (cfPtr = fopen("1.txt", "r")) == NULL)
		printf("File couldn't be opened\n");
	else {
		int tmpt[5][2], step=0;
		int shortestRoutesofNode[TOTAL_NODES][2];

		printf("Add Path now!\n");
		initializeMap(myPath, TOTAL_NODES);

		currPtr = myPath[0];

		fscanf(cfPtr, "%d%d%d%d%d%d%d%d%d%d%d", &numberofPaths, &tmpt[0][0], &tmpt[0][1], &tmpt[1][0], &tmpt[1][1], &tmpt[2][0], &tmpt[2][1], &tmpt[3][0], &tmpt[3][1], &tmpt[4][0], &tmpt[4][1]);
		addMap(myPath, tmpt, numberofPaths, step++);
		shortestRoutesofNode[0][0] = tmpt[0][0];	//Record the shortest Routes of a Node in order to build special_Case data to avoid path loop back scenario
		shortestRoutesofNode[0][1] = tmpt[0][1];	//Record the distance
		for(i=1; i<5; i++) {
			if( (shortestRoutesofNode[0][1] > tmpt[i][1]) && (tmpt[i][1] != 0) ) {
				shortestRoutesofNode[0][0] = tmpt[i][0];
				shortestRoutesofNode[0][1] = tmpt[i][1];
			}	
		}

		while( !feof(cfPtr) ) {
			fscanf(cfPtr, "%d%d%d%d%d%d%d%d%d%d%d", &numberofPaths, &tmpt[0][0], &tmpt[0][1], &tmpt[1][0], &tmpt[1][1], &tmpt[2][0], &tmpt[2][1], &tmpt[3][0], &tmpt[3][1], &tmpt[4][0], &tmpt[4][1]);
			addMap(myPath, tmpt, numberofPaths, step);
			shortestRoutesofNode[step][0] = tmpt[0][0];
			shortestRoutesofNode[step][1] = tmpt[0][1];
			for(i=1; i<5; i++) {
				if( (shortestRoutesofNode[step][1] > tmpt[i][1]) && (tmpt[i][1] != 0) ) {
					shortestRoutesofNode[step][0] = tmpt[i][0];
					shortestRoutesofNode[step][1] = tmpt[i][1];
				}
			}
			step++;
		}

		fclose(cfPtr);

		for(i=0; i<TOTAL_NODES; i++)
			printf("#%d shortest routes is %d %d\n", i, shortestRoutesofNode[i][0], shortestRoutesofNode[i][1]);

		specialCasePtr SpecialCases = NULL;
		for(i=0; i<TOTAL_NODES; i++)
			if(shortestRoutesofNode[ shortestRoutesofNode[i][0] ][0] == i)
				special_Cases(&SpecialCases, i, shortestRoutesofNode[i][0]);

		printf("Path establish.\n");

		printf("\n\n");

		initializeCheckList();

		while( !checkisEmpty(listPtr) )
			searchRoutes(myPath, popCheck(&listPtr));

		for(i=0; i<TOTAL_NODES; i++) {
			printStack(stackPtr[i], i);
			printf("Shortest Distance for '%d' = %d\n\n", i, shortest[i]);
		}

		printf("\n");

	}

	return 0;
}

void initializeMap(mapPtr *wmyPath, int size) {
	int i;

	for(i=0; i<=size-1; i++) {
		wmyPath[i] = (mapPtr) malloc(sizeof(map));
		if(wmyPath[i] != NULL) {
			wmyPath[i]->Name = i;
			wmyPath[i]->numberofPath = 0;
			wmyPath[i]->Dist1 = 0;
			wmyPath[i]->Dist2 = 0;
			wmyPath[i]->Dist3 = 0;
			wmyPath[i]->Dist4 = 0;
			wmyPath[i]->Dist5 = 0;
			wmyPath[i]->Ptr1 = NULL;
			wmyPath[i]->Ptr2 = NULL;
			wmyPath[i]->Ptr3 = NULL;
			wmyPath[i]->Ptr4 = NULL;
			wmyPath[i]->Ptr5 = NULL;
		}
		else
			printf("Path not established. No memory available.\n\n");
	}
}

void addMap(mapPtr *myPath, const int tempt[][2], int numberofPaths, int wStep)
{
	if(tempt[0][0] != 0) {
		myPath[wStep]->numberofPath = numberofPaths;
		myPath[wStep]->Ptr1 = myPath[tempt[0][0]];
		myPath[wStep]->Dist1 = tempt[0][1];
		printf("%d %d %d ", myPath[wStep]->numberofPath, myPath[wStep]->Ptr1->Name, myPath[wStep]->Dist1);
	}

	if(myPath[wStep]->numberofPath >= 2) {
		if(tempt[1][0] != 0) {
			myPath[wStep]->Ptr2 = myPath[tempt[1][0]];
			myPath[wStep]->Dist2 = tempt[1][1];
			printf("%d %d ", myPath[wStep]->Ptr2->Name, myPath[wStep]->Dist2);
		}

		if(myPath[wStep]->numberofPath >= 3) {
			if(tempt[2][0] != 0){
				myPath[wStep]->Ptr3 = myPath[tempt[2][0]];
				myPath[wStep]->Dist3 = tempt[2][1];
				printf("%d %d ", myPath[wStep]->Ptr3->Name, myPath[wStep]->Dist3);
			}

			if(myPath[wStep]->numberofPath >= 4) {
				if(tempt[3][0] != 0){
					myPath[wStep]->Ptr4 = myPath[tempt[3][0]];
					myPath[wStep]->Dist4 = tempt[3][1];
					printf("%d %d ", myPath[wStep]->Ptr4->Name, myPath[wStep]->Dist4);
				}

				if(tempt[4][0] != 0){
					myPath[wStep]->Ptr5 = myPath[tempt[4][0]];
					myPath[wStep]->Dist5 = tempt[4][1];
					printf("%d %d ", myPath[wStep]->Ptr5->Name, myPath[wStep]->Dist5);
				}
			}
		}
	}
	printf("\n");
}

void push(StackNodePtr * nextPath, StackNodePtr * previousPaths)
{
	(*nextPath)->nextPtr = *previousPaths;
}

int pop(StackNodePtr *topPtr) {
	StackNodePtr tempPtr;
	int popValue;

	tempPtr = *topPtr;
	popValue = (*topPtr)->Name;
	*topPtr = (*topPtr)->nextPtr;
	free(tempPtr);
	return popValue;
}

void printStack(StackNodePtr currentPtr, int location) {
	if(currentPtr == NULL)
		printf("The stack is empty.\n\n");
	else {
		printf("The shortest paths from 0 to \"%d\" is:\n", location);

		while(currentPtr != NULL) {
			printf("%d --> ", currentPtr->Name);
			currentPtr = currentPtr->nextPtr;
		}

		printf("NULL\n\n");
	}
}

int isEmpty(StackNodePtr topPtr)
{
	return topPtr == NULL;
}

void initialStackPtr(StackNodePtr * newStackPtr, int i) {
	StackNodePtr newPtr;
	
	newPtr = (StackNodePtr) malloc(sizeof(StackNode));
	if(newPtr != NULL) {
			newPtr->Name = i;
			newPtr->nextPtr = NULL;
			*newStackPtr = newPtr;
	}
	else
		printf("New Path Solution Stack \"%d\" not inserted. No memory available.\n", i);
}

void initializeCheckList(void)
{
	CheckListPtr currPtr = NULL, prevPtr = NULL;
	int i;

	checkListMalloc(&currPtr, &prevPtr, TOTAL_NODES-2);

	printf("Node %d created\n", currPtr->Location);

	for(i=TOTAL_NODES-3; i>=0; i--) {
		checkListMalloc(&currPtr, &prevPtr, i);
		currPtr->nextPtr = prevPtr;
		prevPtr = currPtr;
	}

	listPtr = currPtr;

	printf("Initialize Check-list successfully. listPtr is %d\n\n", listPtr->Location);
}

void checkListMalloc(CheckListPtr *currPtr, CheckListPtr *prevPtr, int theLocation)
{
	CheckListPtr newPtr;

	newPtr = (CheckListPtr)malloc( sizeof(CheckList) );
	if(newPtr != NULL) {
		newPtr->Location = theLocation;
		newPtr->nextPtr = NULL;

		if(checkisEmpty(*prevPtr))
			*prevPtr = newPtr;
		else
			newPtr->nextPtr = *prevPtr;

		*currPtr = newPtr;
	}
	else
		printf("%d is not created\n", theLocation);
}

void addCheck(CheckListPtr *sPtr, int pointLocation)
{
	if( (*sPtr)->Location != pointLocation) {
		CheckListPtr newPtr, currPtr, previousPtr;

		newPtr = (CheckListPtr) malloc(sizeof(CheckList));
		if(newPtr != NULL) {
			newPtr->Location = pointLocation;
			newPtr->nextPtr = NULL;
		}
		else
			printf("%d not inserted to check-list. No memory available\n", pointLocation);

		previousPtr = NULL;
		currPtr = *sPtr;

		while(currPtr != NULL && pointLocation > currPtr->Location) {
			previousPtr = currPtr;
			currPtr = currPtr->nextPtr;
		}

		if(previousPtr == NULL) { 	//either the list is empty or new location is smaller than the head of list
			newPtr->nextPtr = *sPtr;
			*sPtr = newPtr;
		}
		else if(currPtr == NULL)		//That's mean end of the queue
			previousPtr->nextPtr = newPtr;
		else if(currPtr->Location != pointLocation) {
			previousPtr->nextPtr = newPtr;
			newPtr->nextPtr = currPtr;
		}
		else {}
	}
}

//Start to search paths from the check list
int popCheck(CheckListPtr *topPtr)
{
	CheckListPtr tempPtr;
	int popValue;

	tempPtr = *topPtr;
	popValue = (*topPtr)->Location;
	*topPtr = (*topPtr)->nextPtr;
	free(tempPtr);
	return popValue;
}

//check list is empty
int checkisEmpty(CheckListPtr sPtr)
{
	return sPtr == NULL;
}

void searchRoutes(const mapPtr myPath[], int curr) {
	int tempSum;

	printf("Location #%d currently probed\n", curr);

	tempSum = myPath[curr]->Dist1 + shortest[curr];
	if( (shortest[myPath[curr]->Ptr1->Name] == 0) || (shortest[myPath[curr]->Ptr1->Name] > tempSum) ) {
		if(shortest[myPath[curr]->Ptr1->Name] > tempSum)
			addCheck(&listPtr, myPath[curr]->Ptr1->Name);
		push(&stackPtr[myPath[curr]->Ptr1->Name], &stackPtr[myPath[curr]->Name]);
		shortest[myPath[curr]->Ptr1->Name] = tempSum;
		printf("Shortest path %d is changed\n", myPath[curr]->Ptr1->Name);
	}

	if(myPath[curr]->numberofPath >= 2) {
		
		tempSum = myPath[curr]->Dist2 + shortest[curr];
		if( (shortest[myPath[curr]->Ptr2->Name] == 0) || (shortest[myPath[curr]->Ptr2->Name] > tempSum) ) {
			if(shortest[myPath[curr]->Ptr2->Name] > tempSum)
				addCheck(&listPtr, myPath[curr]->Ptr2->Name);
			push(&stackPtr[myPath[curr]->Ptr2->Name], &stackPtr[myPath[curr]->Name]);
			shortest[myPath[curr]->Ptr2->Name] = tempSum;
		}

		if(myPath[curr]->numberofPath >= 3) {
			tempSum = myPath[curr]->Dist3 + shortest[curr];
			if( (shortest[myPath[curr]->Ptr3->Name] == 0) || (shortest[myPath[curr]->Ptr3->Name] > tempSum) ) {
				if(shortest[myPath[curr]->Ptr2->Name] > tempSum)
					addCheck(&listPtr, myPath[curr]->Ptr2->Name);
				push(&stackPtr[myPath[curr]->Ptr3->Name], &stackPtr[myPath[curr]->Name]);
				shortest[myPath[curr]->Ptr3->Name] = tempSum;
			}

			if(myPath[curr]->numberofPath >= 4) {
				tempSum = myPath[curr]->Dist4 + shortest[curr];
				if( (shortest[myPath[curr]->Ptr4->Name] == 0) || (shortest[myPath[curr]->Ptr4->Name] > tempSum) ) {
					if(shortest[myPath[curr]->Ptr3->Name] > tempSum)
						addCheck(&listPtr, myPath[curr]->Ptr3->Name);
					push(&stackPtr[myPath[curr]->Ptr4->Name], &stackPtr[myPath[curr]->Name]);
					shortest[myPath[curr]->Ptr4->Name] = tempSum;
				}

				if(myPath[curr]->numberofPath == 5) {
					tempSum = myPath[curr]->Dist5 + shortest[curr];
					if( (shortest[myPath[curr]->Ptr5->Name] == 0) || (shortest[myPath[curr]->Ptr5->Name] > tempSum) ) {
						if(shortest[myPath[curr]->Ptr4->Name] > tempSum)
							addCheck(&listPtr, myPath[curr]->Ptr4->Name);
						push(&stackPtr[myPath[curr]->Ptr5->Name], &stackPtr[myPath[curr]->Name]);
						shortest[myPath[curr]->Ptr5->Name] = tempSum;
					}
				}
			}
		}
	}
}