/* this code is written as an assignement for Algorithms and Data Structures course */
/* implemented are following algorithms :                                           */
/* * greedy:  dijkstra +  dijkstra with n starting points, where N is number of     */
/*   cities                                                                         */
/* * Branch And Bound :  priority queue based and depth first algorithms            */
/* * complete algorithm ( brute force )                                             */
/* * dynamic : recursive dynamic + recursive dynamic with branch and bound          */
/*   hybrid with BnB doesn't work correctly yet                                     */
/* Sven Petai hadara@bsd.ee                                                         */

#include "tsp.h"

/* global variables */
unsigned long int best_length,cur_length=0;
unsigned char *cur_path,*full_best_path,*used;
unsigned int **calculated;
unsigned int cities;
unsigned int edges;
unsigned int best_possible=0;
unsigned int *best_path=NULL;
/* all algorithms store their answer in this array */
/* to make possible usage of several algorithms at once */
/* (BnB) uses it */
unsigned int *best_array=NULL;
/* used by BnB algorithms */
unsigned int **main_edge_array;
/* lengths are stored in this array */
long int best_pathlength = 0;
/* best pathlength found so far */
/* global variables end */

FILE *stream;

void print_help(void) {
	printf("\n syntax is:\n");
	printf("./tspsolver data.file\n");
	printf("\t this uses Dikstras algorithm with starting point 0\n");
	printf("./tspsolver -c data.file\n");
	printf("\t uses complete algorithm\n");
	printf("./tspsolver -m data.file\n");
	printf("\t try Dijkstras algorithm with N starting points\n");
	printf("./tspsolver -p data.file\n");
	printf("\t use priority queue based BnB algorithm\n");
	printf("./tspsolver -b data.file\n");
	printf("\t use depth first based BnB\n");
	printf("./tspsolver -d data.file\n");
	printf("\t use dynamic algorihtm");
	printf("\t you can interrupt searching with CTRL+C, then you\n");
	printf("\t will be given best path found up to this moment\n");
	exit(0);
}

void handle_error(char *reason) {
	perror(reason);
	exit(-1);
}

int interrupted(void) {
	register int i;

	if( best_path != NULL ) 
		for(i=0; i<=cities; i++)
			printf(" %u->",best_path[i]);
	printf("\n Best path so far is %ld\n",best_pathlength);
			
	exit(-1);
return(0);
}

int interrupted2(void) {
	register int i;

	printf("\n");
	if( full_best_path != NULL )
		for(i=0; i<cities; i++) 
			printf("%u->",full_best_path[i]);
	printf("\n Best pathlength found so far is %ld\n",best_pathlength);

	exit(-1);
	return(0);
}

void read_fast(unsigned int *where) {
	/* substitution for fscanf(), this dedicated function is  */
	/* about 25% faster                                       */
        char c;
        register int i;
        char buf[6];
        buf[5] = buf[4] = buf[3] = buf[2] = buf[1] = buf[0] = 0;
 
        while(isspace((c=fgetc(stream))));
        buf[0] = c;
        for(i=1; (c = fgetc(stream)); i++) {
                if(isspace(c))
                        break;
                else if(c != EOF)
                        buf[i] = c;
                else
                        handle_error("something is wrong with the array");
        }
        *where = (unsigned int)atoi(buf);
}

int main(int argc, char **argv) {
	register char c;
	char flag = 0;
	/* flag = 0 -> usual greedy                  
	 *      = 1 -> complete algorithm            
	 *      = 2 -> greedy with N starting points 
	 *      = 3 -> priority based BnB            
	 *      = 4 -> depth first BnB               
	 *	= 5 -> dynamic                       
	 *      = 6 -> dynamic + BnB                 
	 * TODO:				
	 *	Genetic
	 * 	SAT
	 *	Prim
	 *	Bellman-Ford
	 *	Kruskal
	 */
	char *filename = NULL;
	int interrupted();
	int interrupted2();
	unsigned register int i,j;

	if( argc <= 1  ) 
		print_help();	

	if( argv[1][0] == '-' ) {
		switch(argv[1][1]) {
			case 'h': print_help();
				   break;
			case 'c': flag = 1 , filename = argv[2];
				   break;
			case 'm': flag = 2 , filename = argv[2];
				   break;
			case 'p': flag = 3 , filename = argv[2];
				   break;
			case 'b': flag = 4 , filename = argv[2];
				   break;
			case 'd': flag = 5 , filename = argv[2];
				   break;
			case 'e': flag = 6 , filename = argv[2];
				   break;
			default  : print_help();
		}
	}
	else
		filename = argv[1];

	if(!(stream = fopen(filename,"rb"))) 
		handle_error("failed to open data file ");

	while( (c = getc(stream)) != '\n')  /* find out how many cities we have */
		if( !isspace(c) ) {
			while(isdigit( (c=getc(stream)) ));	
			cities++;
			if(c == '\n')
				break;
			}

	/* allocate memory for 2 dimensional matrix */
	if(!( main_edge_array = (unsigned int**)calloc(cities, sizeof(unsigned int*)) ))
		handle_error("memory allocation failed");
	*(main_edge_array) = (unsigned int*)calloc(1, sizeof(unsigned int));
	for(i=1; i<cities; i++) 
		if(!( *(main_edge_array+i) = (unsigned int*)calloc(i, sizeof(unsigned int))))
			handle_error("memory allocation failed");
		
	main_edge_array[0][0] = 0;

	for(i=1; i<cities; i++) { /* fill in the array */
		for(j=0;j<i;j++) {
			read_fast(&main_edge_array[i][j]);
		}	
		while(getc(stream) != '\n'); /* we dont need any more data from this line */
	}

	fclose(stream);
	
	if( flag == 2 ) {
		printf("Algorithm used: Greedy (Dijkstra) with multiple starting points\n");
		signal(SIGINT,(void*)interrupted);
		best_path = (unsigned int*)malloc((cities+2) * sizeof(int));
		/* code crashes on solaris if I would try last vertix     */
		/* I have no time or solaris machine with normal debugger */
		/* (adb certainly isn't :-)) so I just don't use last one */
		for(i=0; i<(cities-1); i++)
			greedy(i);
		for(i=0; i<=cities; i++)
			printf(" %u ->",best_path[i]);
		printf("\n best path : %ld\n",best_pathlength);
	}
	else if( flag == 1 ) {
		printf("Algorithm used: complete\n");
		signal(SIGINT,(void*)interrupted);
		full_master();
	}
	else if( flag == 3 ) {
		printf("Algorithm used: Branch & Bound (priority queue)\n");
		signal(SIGINT,(void*)interrupted2);
		best_path = (unsigned int*)malloc((cities+2) * sizeof(int));
		for(i=0; i<(cities-1); i++)
			greedy(i);
		for(i=0; i<=cities; i++)
			printf("%u->",best_path[i]);
		bb();
		printf("Best pathlength was %ld\n",best_pathlength);
	}
	else if( flag == 4 ) {
		printf("Algorithm used: Branch & Bound (depth first)\n");
		signal(SIGINT,(void*)interrupted2);
		best_path = (unsigned int*)malloc((cities+2) * sizeof(int));
		for(i=0; i<(cities-1); i++)
			greedy(i);
		for(i=0; i<(cities-1); i++)
			printf("%u->",best_path[i]);
		bb2_master();
	}
	else if( flag == 5 ) {
		printf("Algorithm used: Dynamic\n");
		dynamic_master(DYNAMIC);
	}
	else if( flag == 6 ) {
		printf("Algorithm used: Dynamic + BnB\n");
		best_path = (unsigned int*)malloc((cities+2) * sizeof(int));
		for(i=0; i<(cities-1); i++)
			greedy(i);
		for(i=0; i<=cities; i++)
			printf("%u->",best_path[i]);
		estimate_best();
		dynamic_master(DYNAMIC_WITH_BNB);
	}
	else {
		printf("Algorithm used: Greedy (Dijkstra)");
		greedy(0);
	}
		

return(0);
}