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

#define ZEILENLAENGE 100
#define TRUE 1
#define FALSE 0
#define MAX 100

//Globale Variablen
float strecke = 0;

//Funktionen
void zeige_hilfe();
void datei_hilfe();
float kleinste_strecke(float array[MAX], int anzahl);
int naechster_nachbar(float matrix[MAX][MAX], int n, int punkt);
/**********************************************************************************************************/
int main(int argc, char *argv[])
{
	FILE *fp;				//Variablen	
	clock_t start, ende;
	char puffer[ZEILENLAENGE];
	int zeilen = 0;
	int n,i,j;
	int letzter_punkt;
	float x[MAX];
	float y[MAX];
	float matrix[MAX][MAX];
	float matrix_tmp[MAX][MAX];

	if(argv[1] == NULL)			/*Wurde ein Kommandozeilenparameter angegeben*/
	{
		printf("Es wurde keine Datei angegeben!\n");
		exit(1);
	}
	if(argc != 2)
	{
		zeige_hilfe();
	}

	if((fp = fopen(argv[1], "r")) == NULL)		/*Kann die Datei zum Lesen geöffnet werden*/		
		perror("Fehler beim Oeffnen der Datei");	
	else	
	{	
		while(fgets(puffer,ZEILENLAENGE,fp))	/*Die Anzahl der Zeilen wird ermittelt*/
			zeilen++;

		fseek(fp, 0L, SEEK_SET);		/*Der Zeiger fp wird an den Anfang der Datei gesetzt*/
		fscanf(fp,"%d",&n);
		if(n <= 0 || n != zeilen - 1)//stimmt n nicht mit den zeilen-1 ueberein, zeige datei_hilfe()
			datei_hilfe();
		else
		{
			i = 0;
			while(fgets(puffer,ZEILENLAENGE,fp) && i < n)//die datei wird zeilenweise ausgelesen
			{

				fscanf(fp,"%f %f",&x[i],&y[i]);//Die Koordinaten x und y werden befuellt
				i++;
			}
			fclose(fp);//die datei wird geschlossen
			for(i = 0; i < n; i++)
			{
				for(j = 0; j < n; j++)
				{
					if(i == j) //der weg zu sich selbst ist null
						matrix[i][j] = 0.0;
					else//die entfernung der knoten wird berechnet und in der matrix abgespeichert
						matrix[i][j] = (float)sqrt(pow((x[i] - x[j]),2) + pow((y[i] - y[j]),2));
				}
			}
			
			for(i = 0; i < n; i++)//Befuellen der matrix_tmp
			{
				for(j = 0; j < n; j++)
				{
					matrix_tmp[i][j] = matrix[i][j];
				}
			}
			/*for(i = 0; i < n; i++)//testausgabe der matrix
			{
				for(j = 0; j < n; j++)
				{
					printf("\t%g",matrix[i][j]);
				}
				printf("\n");
			}*/
			printf("-----------------------------------------------------------------------------\n");
			printf("---------------------NEAREST NEIGHBOUR ALGORITHMUS---------------------------\n");
			printf("-----------------------------------------------------------------------------\n\n");
			start = clock();			//Die Zeit beginnt zu laufen
			printf("Startpunkt 1\n"); //Es wird immer vom Punkt 1 ausgegangen
			letzter_punkt = naechster_nachbar(matrix_tmp,n,0);	
			strecke = strecke + matrix[0][letzter_punkt]; //die strecke vom letzten zum ersten Punkt wird noch addiert	
			printf("Strecke: %g\n",matrix[0][letzter_punkt]);
			printf("Endpunkt 1\n");
			printf("Gesamtstrecke: %g\n",strecke);
			ende = clock();			//Die Zeit stoppt
			printf("-----------------------------------------------------------------------------\n");
			printf("CPU-Zeit fuer den Nearest Neighbour Algorithmus: %.2f Sekunden\n",	/*Ausgabe der benötigten Zeit in Sekunden*/
            (float)(ende-start)/CLOCKS_PER_SEC);
			printf("-----------------------------------------------------------------------------\n");
		}
	}
	return EXIT_SUCCESS;
}
/**********************************************************************************************************/
void zeige_hilfe()
{
	printf("usage: tsp <filename>\n");
    exit(1);
}
/**********************************************************************************************************/
void datei_hilfe()
{
	printf("Der Wert n muss mit der Anzahl der Koordinaten uebereinstimmen!\n");
    exit(1);
}
/**********************************************************************************************************/
int naechster_nachbar(float matrix[MAX][MAX], int n, int punkt)
{
	int i, j;
	int next;
	int ende = TRUE;
	float kleinste = 0;
	float matrix_tmp[MAX];

	for(i = 0; i < n; i++)//Befuellen des Arrays matrix_tmp[], wird dann an die 
	{					  //Fkt. kleinste_strecke uebergeben
		matrix_tmp[i] = matrix[punkt][i]; 
	}

	kleinste = kleinste_strecke(matrix_tmp,n);//Aufruf der Fkt. kleinste_strecke

	for(i = 0; i < n; i++)
	{
		if(kleinste == matrix[punkt][i])//der naechste Punkt wird ermittelt
			next = i;
	}

	printf("Strecke: %f\n",kleinste);
	printf("Naechster Punkt: %d\n",next+1);

	for(i = 0; i < n; i++)//Punkte die nicht mehr besucht werden koennen, werden mit False befuellt
	{
		matrix[punkt][i] = FALSE;
		matrix[i][punkt] = FALSE;
	}

	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			if(matrix[i][j] > 0) //ist noch ein Punkt vorhanden
				ende = FALSE;
		}
	}
	if(ende == FALSE) // es ist noch ein Punkt vorhanden, also rekursiver Aufruf der Funktion
		naechster_nachbar(matrix,n,next);
	
	strecke = strecke + kleinste;
	return next;
}
/**********************************************************************************************************/
float kleinste_strecke(float array[MAX], int anzahl)
{		
	int i, j;
	float kleinste;

	for (i = 0; i < anzahl; i++)
    {
		for (j = anzahl - 1; j >= i; j--)
		{
			if (array[j] < array[j - 1])
			{
					kleinste = array[j];
					array[j] = array[j - 1];
					array[j - 1] = kleinste;
			}
		}
	}
	i = 0;
	while(array[i] == 0)
		i++;

	return array[i]; //die kleinste strecke != 0 wird zurueckgegeben!
}