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

#define TOTAL_NODES 30

struct stackNode {
	int Name;
	struct stackNode *nextPtr;
};

struct checkList {
	int Location;
	struct checkList *nextPtr;
};

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 stackNode StackNode;
typedef StackNode *StackNodePtr;

typedef struct checkList CheckList;
typedef CheckList *CheckListPtr;

typedef struct Map map;
typedef map *mapPtr;

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

void initializePath(mapPtr *, int);
void addPath(mapPtr *, const int [][2], int, int);
void printPath(StackNodePtr, 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

void initialStackPtr(StackNodePtr *, int);
void stackUp(const mapPtr [], int);

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

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

	for(i=0; i<TOTAL_NODES; i++) {
		shortest[i] = 0;
		stackPtr[i] = NULL;
		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;

		for(i=0; i<5; i++)
			for(j=0; j<2; j++)
				tmpt[i][j] = 0;

		printf("Add Path now!\n");
		initializePath(myPath, TOTAL_NODES);
		for(i=0; i<TOTAL_NODES; i++)
			printf("%d\n", myPath[i]->Name);

		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], &tmpt[5][0], &tmpt[5][1]);
		addPath(myPath, tmpt, numberofPaths, step++);

		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], &tmpt[5][0], &tmpt[5][1]);
			printf("%d ", step);
			for(i=0; i<5; i++)
				for(j=0; j<2; j++)
					printf("%d ", tmpt[i][j]);
			printf("\n");
			addPath(myPath, tmpt, numberofPaths, step++);
		}

		fclose(cfPtr);
	}

	printf("Path establish.\n");

	listPtr = NULL;
	addCheck(&listPtr, 0);
	while(listPtr != NULL) {
		if( !checkisEmpty(listPtr) )
			stackUp(myPath, popCheck(&listPtr));
		else
			printf("End of execution of search shortest path\n");
	}

	for(i=0; i<TOTAL_NODES; i++)
		printPath(stackPtr[i], i);
	
	for(i=0; i<TOTAL_NODES; i++)
		printf("%d ", shortest[i]);
	printf("\n");

	return 0;
}

void initializePath(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 addPath(mapPtr *myPath, const int tempt[][2], int numberofPaths, int wStep)
{
	myPath[wStep]->numberofPath = numberofPaths;
	myPath[wStep]->Ptr1 = myPath[tempt[0][0]];
	myPath[wStep]->Dist1 = tempt[0][1];

	if(myPath[wStep]->numberofPath >= 2) {
		myPath[wStep]->Ptr2 = myPath[tempt[1][0]];
		myPath[wStep]->Dist2 = tempt[1][1];

		if(myPath[wStep]->numberofPath >= 3) {
			myPath[wStep]->Ptr3 = myPath[tempt[2][0]];
			myPath[wStep]->Dist3 = tempt[2][1];
	
			if(myPath[wStep]->numberofPath >= 4) {
				myPath[wStep]->Ptr4 = myPath[tempt[3][0]];
				myPath[wStep]->Dist4 = tempt[3][1];

				if(myPath[wStep]->numberofPath == 5) {
					myPath[wStep]->Ptr5 = myPath[tempt[4][0]];
					myPath[wStep]->Dist5 = tempt[4][1];
				}
			}
		}
	}
}

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 printPath(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 addCheck(CheckListPtr *sPtr, int pointLocation)
{
	CheckListPtr newPtr, currPtr, previousPtr;

	newPtr = (CheckListPtr) malloc(sizeof(CheckList));

	if(newPtr != NULL) {
		newPtr->Location = pointLocation;
		newPtr->nextPtr = NULL;

		previousPtr = NULL;
		currPtr = *sPtr;

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

		if(previousPtr == NULL) {
			newPtr->nextPtr = *sPtr;
			*sPtr = newPtr;
		}
		else {
			previousPtr->nextPtr = newPtr;
			newPtr->nextPtr = currPtr;
		}
	}
	else
		printf("%d not inserted to check-list. No memory available\n", pointLocation);
}

//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 stackUp(const mapPtr myPath[], int curr) {
	int tempSum;

	tempSum = myPath[curr]->Dist1 + shortest[myPath[curr]->Name];
	if( (shortest[myPath[curr]->Ptr1->Name] == 0) || (shortest[myPath[curr]->Ptr1->Name] > tempSum) ) {
		push(&stackPtr[myPath[curr]->Ptr1->Name], &stackPtr[myPath[curr]->Name]);
		shortest[myPath[curr]->Ptr1->Name] = tempSum;
		if(myPath[curr]->Ptr1->Name != TOTAL_NODES-1)
			addCheck(&listPtr, myPath[curr]->Ptr1->Name);
		printf("%d is added to check-list\n", myPath[curr]->Ptr1->Name);
	}

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

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

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

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