#include <stdio.h>
#include <stdlib.h>
#include <math.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);
float naechster_nachbar(float matrix[MAX][MAX], int n, int punkt);
/**********************************************************************************************************/
int main(int argc, char *argv[])
{
	FILE *fp;										
	char puffer[ZEILENLAENGE];
	int zeilen = 0;
	int n,i,j;
	float x[MAX];
	float y[MAX];
	float matrix[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++)//testausgabe der matrix
			{
				for(j = 0; j < n; j++)
				{
					printf("\t%g",matrix[i][j]);
				}
				printf("\n");
			}
			naechster_nachbar(matrix,n,0);
			printf("Strecke: %f\n",strecke);
		}
	}

	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);
}
/**********************************************************************************************************/
float 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++)
	{
		matrix_tmp[i] = matrix[punkt][i]; 
	}
	
	kleinste = kleinste_strecke(matrix_tmp,n);

	for(i = 0; i < n; i++)
	{
		if(kleinste == matrix[punkt][i])
			next = i;
	}

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

	for(i = 0; i < n; i++)
	{
		matrix[punkt][i] = FALSE;
		matrix[i][punkt] = FALSE;
	}

	for(i = 0; i < n; i++)//testausgabe der matrix
	{
		for(j = 0; j < n; j++)
		{
			printf("\t%g",matrix[i][j]);
		}
		printf("\n");
	}

	strecke = strecke + kleinste;
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			if(matrix[i][j] > 0)
				ende = FALSE;
		}
	}
	if(ende == FALSE)
		naechster_nachbar(matrix,n,next);
	else
		return strecke;
}
/**********************************************************************************************************/
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!
}