#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

struct _element {
	char icao_code[5];
	char station_name[100];
};

typedef struct _element element;

void insertion_sort(element* stations, int size) {
	// implement either insertion_sort or selection_sort
    if (size <= 1) {
        return;
    }
    insertion_sort(stations, size-1);
    printf("\n");
    char last[5];
    strcpy(last,stations[size-1].icao_code);
    char letzte[100];
    strcpy(letzte,stations[size-1].station_name);
    int j = size-2;
    while (j >= 0 && strcmp(stations[j].icao_code,last) > 0){
        stations[j+1] = stations[j];
        j--;
    }
    strcpy(stations[j+1].icao_code, last);
    strcpy(stations[j+1].station_name,letzte);
}
void swap(element* a, element* b){
    element t = *a;
    *a = *b;
    *b = t;
}

void swaper(void *a, void *b, size_t size){
    void *temp = malloc(size);
    memcpy(temp,a,size);
    memcpy(a,b,size);
    memcpy(b,temp,size);
    free(temp);
}

int comp (void *p, void *q){
    return strcmp(((struct _element *)p)->icao_code,((struct _element *)q)->icao_code);
}

void insertion_sort2(void* data, int nitems, int size, int (*comp) (void *, void*)){
    char *carray = (char *)data;
    int j;
    for(int i = 0; i < nitems; i++){
        j = i;
        while(j > 0 && comp(&carray[j * size], &carray[(j - 1) * size]) < 0){
            swaper(&carray[j * size], &carray[(j - 1) * size], size);
            j--;
        }
    }
};

void selection_sort(element* stations, int size) {}


int partition(element * stations, int left, int right){
    char pivot[5];
    strcpy(pivot,stations[right].icao_code);
    int i = left - 1;
    for(int j = left; j <= right-1; j++){
        if(strcmp(pivot,stations[j].icao_code) > 0){
            i++;
            swap(&stations[i],&stations[j]);
        }
    }
    swap(&stations[i+1],&stations[right]);

    return (i+1);
}

void quick_sort(element* stations, int left, int right) {
	// implement either quick_sort or merge_sort
	if(left < right){
	    int pi = partition(stations, left, right);
	    quick_sort(stations,left,pi-1);
	    quick_sort(stations,pi+1,right);
	}
}



void merge_sort(element* stations, element* tmpStations, int left, int right) {
	// implement either quick_sort or merge_sort
	// tmpStations corresponds to the array B in the lecture slides
}

void print_stations(element* stations, int size) {
	int i;
	for (i = 0; i < size; i++) {
		printf("%s : %s", stations[i].icao_code, stations[i].station_name);
	}
}

int readfile(element* stations, int* size) {
	FILE * fp;
	char line[100]; // keeps one line of the file

	// try to open the file; in case of an error exit the program
	*size = 0;
	fp = fopen("stations.csv", "r");
	if (!fp) {
		printf("Cannot open file stations.csv!\n");
		return 1;
	}

	// read all weather stations from file and add them to the
	// hash table
	while (!feof(fp)) {
		// read one line and skip empty and comment lines
		fgets(line, 100, fp);
		if (line[0] == '#') continue;
		if (isspace(line[0])) continue;

		// take the first 4 characters as key value
		strncpy(stations[*size].icao_code, line, 4);
		stations[*size].icao_code[4] = '\0';

		// take the rest as value
		strcpy(stations[*size].station_name, strchr(line, ';')+1);
		*size += 1;
	}

	// close the file
	fclose(fp);

	return 0;
}

int main(int argc, char** argv) {
	element* stations; // holds the station codes and names
	element* tmpStations; // holds temporary station codes and names for merge sort
	int size; // holds the number of valid entries in the array

	stations = (element*)malloc(sizeof(element)*6000);
	tmpStations = (element*)malloc(sizeof(element)*6000);

	// now lets try insertion sort
	//printf("Sorting with insertion sort:\n");
	// read the station data from file
	//readfile(stations, &size);
	// sort the station names
	//insertion_sort(stations, size);
	// print the result
	//print_stations(stations, size);

	// now lets try selection sort
	//printf("Sorting with selection sort:\n\n");
	// read the station data from file
	//readfile(stations, &size);
	// sort the station names
	//selection_sort(stations, size);
	// print the result
	//print_stations(stations, size);

	// now lets try merge sort
	//printf("Sorting with merge sort:\n\n");
	// read the station data from file
	//readfile(stations, &size);
	// sort the station names
	//merge_sort(stations, tmpStations, 0, size-1);
	// print the result
	//print_stations(stations, size);

	// now lets try quick sort
	//printf("Sorting with quick sort:\n\n");
	// read the station data from file
	//readfile(stations, &size);
	// sort the station names
	//quick_sort(stations, 0, size-1);
	// print the result
	//print_stations(stations, size);


	// now lets try insertion sort with Pointer
	printf("Sorting with Insertion Sort Pointer:\n\n");
	readfile(stations, &size);
	insertion_sort2(stations,size, sizeof(element),comp);
   print_stations(stations,size);

	free(stations);
	free(tmpStations);

	return 0;
}