//#include "stdafx.h" /* make compatible with MS Visual Studio */

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

#define TIME 29
#define NOPT 3

typedef struct e {
    int to, from, cost;
} edge;

typedef struct c {
    int c1, c2, group;
} city;

int * table;

int n_cities;

void swap (edge ** e, edge ** f);

int part (edge ** edges, int low, int high);

void quicksort (edge ** edges, int low, int high);

int compare (edge * e, edge * f);

void city_init(city * c);

int city_open(city * c);

void city_connect(city * c, int i);

int cities_verify(city * cities);

void cities_output (city * cities, int size, int sum);

void shuffle_one (edge ** edges, int min, int max);

int * access_table (int i, int j);

int * cities_convert (city * input);

// command line arguments example
// tsp 1000 tsp_exp.txt
// 0   1    2

int main (int argc, const char * argv[]) {
    time_t start_time, stop_time;

    start_time = stop_time = clock();

    if (argc < 3) {
        printf("Usage: tsp [number of cities] [matrix file]\n");
        return 1;
    }

    FILE * file_in = 0;

    srand((unsigned int)time(0));

    n_cities = atoi(argv[1]);

    if (n_cities < 1) {
        printf("FILE READ ERROR!\n");
        return 2;
    }

    file_in = fopen(argv[2], "r");

    if (!file_in) {
        printf("FILE NOT FOUND!\n");
        return 3;
    }

    table = (int*)malloc(n_cities * n_cities * sizeof(int));

    edge ** edges = (edge**)malloc((n_cities * (n_cities - 1) >> 1) * sizeof(edge*));

    int r = 0;

    for (int i = 0; i < n_cities; i++) {
        for (int j = 0; j < n_cities; j++) {
            if(fscanf(file_in, "%u%*[,]", access_table(i, j))) {
                if (i < j) {
                    edges[r] = (edge*)malloc(sizeof(edge));
                    edges[r]->from = i;
                    edges[r]->to = j;
                    edges[r]->cost = *access_table(i, j);
                    r++;
                }
            } else {
                printf("READ ERROR!\n");
                return 4;
            }
        }
    }

    fclose(file_in);

    city * cities = (city*)malloc(n_cities * sizeof(city));

    printf("Sorting edges...");
    time_t qst = clock();
    quicksort(edges, 0, r-1);
    stop_time = clock() - qst;

    printf(" done! (%.3f s)\n", stop_time / (double)CLOCKS_PER_SEC);

    int sum = INT_MAX;

    do {
        int group_count, sum_tmp, lowest_cost, connection_count, index, first;

        for (int k = 0; k < n_cities; k++) {
            city_init(&cities[k]);
        }

        index = first = connection_count = sum_tmp = 0;

        lowest_cost = edges[0]->cost;

        group_count = 1;

        while(connection_count < n_cities - 1) {

            int i, j;

            i = edges[index]->from;
            j = edges[index]->to;

            if(*access_table(i, j) > lowest_cost) {
                shuffle_one(edges, first, index - 1);
                lowest_cost = *access_table(i, j);
                first = index;
            }

            if (++index > r) index = 0;

            // check if cities have free connections
            if (city_open(&cities[i]) && city_open(&cities[j])) {
                // check group status of cities
                // true if both cities belong to no group or one city belongs to a group
                // false if both cities belong to the same group
                if(cities[i].group == -1 || cities[j].group == -1 || cities[i].group != cities[j].group) {

                    city_connect(&cities[i], j);
                    city_connect(&cities[j], i);

                    sum_tmp += *access_table(i,j);
                    connection_count++;


                    if (cities[i].group != cities[j].group && cities[i].group != -1 && cities[j].group != -1) {
                        int i_prev, i_this, i_next;

                        i_this = i;
                        i_next = j;

                        do {
                            cities[i_next].group = cities[i].group;

                            i_prev = i_this;
                            i_this = i_next;
                            i_next = cities[i_this].c1 != i_prev ? cities[i_this].c1 : cities[i_this].c2;
                        } while ( i_next != -1);

                    } else if (cities[i].group != -1) {
                        cities[j].group = cities[i].group;
                    //check if city j belongs to a group, if so add city i to the same group
                    } else if (cities[j].group != -1) {
                        cities[i].group = cities[j].group;
                    //check if cities belongs to different groups, if so add all connected cities to group of city i
                    } else {
                        cities[i].group = cities[j].group = group_count;
                        group_count++;
                    }
                }
            }
        }

        int lastindex = -1;
        int i = 0;

        while (connection_count != n_cities) {

            if (city_open(&cities[i])) {
                if (lastindex == -1) {
                    lastindex = i;
                } else {
                    city_connect(&cities[i], lastindex);
                    city_connect(&cities[lastindex], i);
                    sum_tmp += *access_table(i, lastindex);
                    connection_count++;
                }
            }
            i++;
        }

//        int opt = 3;
//        for(int n = 2; n < opt; n++) {
//            int k = n;
//
//            int * p = malloc(n * sizeof(int));
//
//            for(int t = 0; t < n; t++) {
//                p[n] = 0;
//            }
//
//            while( k ) {
//                for (int j = 0; j < n; n++) {
//
//                    ;
//                }
//                k--;
//                ;
//            }
//
//        int * cities_ordered = cities_convert(cities);
//
//        int x, y, new_cost;
//        new_cost = sum_tmp;
//
//        for (int i = 0; i < n_cities; i++) {
//            for (int j = 0; j < n_cities; j++) {
//                if (i >= j) {
//                    x = y = n_cities; // NDBG
//            }
//        }
//
//
//
//             for every permutation of n elements from opt elements
//             in other words n kanter ska swappas
//             för det finns n! / (n! * opt!) möjligheter
//             där varje möjlighet innehåller n kanter
//
//             för varje möjlighet kan
//             finns det n^2 kombinationer
//             varav vissa återkommer
//
//            ;
//        }


        if (sum_tmp < sum && cities_verify(cities)) {
            sum = sum_tmp;

            printf("(new result: %d, %.3f s)\n", sum, stop_time / (double)CLOCKS_PER_SEC);

            cities_output(cities, n_cities, sum);
        }

        stop_time = clock() - start_time;
    } while(clock() - start_time < TIME * CLOCKS_PER_SEC);

    printf("Final result: %d (%.3f s)\n", sum, stop_time / (double)CLOCKS_PER_SEC);

    return 0;
}

void swap (edge ** e, edge ** f) {
    edge * t;

    t = *e;

    *e = *f;

    *f = t;
}

int part (edge ** edges, int low, int high) {
    int i = low - 1;

    for (int j = low; j <= high - 1; j++) {
        if(compare(edges[j], edges[high])) {
            swap(&edges[++i], &edges[j]);
        }
    }
    swap(&edges[i + 1], &edges[high]);
    return (i + 1);
}

void quicksort (edge ** edges, int low, int high) {
    if (low < high) {
        int p = part(edges, low, high);

        quicksort(edges, low, p - 1);
        quicksort(edges, p + 1, high);
    }
}

int compare (edge * e, edge * f) {
    return e->cost <= f->cost;
}

void city_init(city * c) {
    c->c1 = c->c2 = c->group = -1;
}

int city_open(city * c) {
    int count = 2;
    if (c->c1 != -1)
        count--;
    if (c->c2 != -1)
        count--;

    return count;
}

void city_connect(city * c, int i) {
    if (c->c1 == -1) c->c1 = i;
    else if (c->c2 == -1) c->c2 = i;
}

int cities_verify(city * cities) {

    int * city_visited = (int*)malloc(n_cities * sizeof(int));

    for (int i = 0; i < n_cities; i++) city_visited[i] = 0;

    int count, i_prev, i_this, i_next;

    i_this = count = 0;
    i_next = cities[i_this].c1;

    while (i_next != -1 && count < n_cities) {
        if (!city_visited[i_this]) {
            city_visited[i_this]++;
            count++;
        } else break;

        i_prev = i_this;
        i_this = i_next;
        i_next = cities[i_this].c1 != i_prev ? cities[i_this].c1 : cities[i_this].c2;
    }

    free(city_visited);

    return !i_this && count == n_cities ;
}

void cities_output (city * cities, int size, int sum) {
    char filename[0xC0];
//    sprintf(filename,"o_%d.txt",sum);
    sprintf(filename,"output.txt");
    FILE * file_out = fopen(filename, "w");

    int count, i_prev, i_this, i_next;

    i_this = count = 0;
    i_next = cities[i_this].c1;

    while (i_next != -1 && count++ <= size) {

        fprintf(file_out,"%d\n",i_this+1);

        i_prev = i_this;
        i_this = i_next;
        i_next = cities[i_this].c1 != i_prev ? cities[i_this].c1 : cities[i_this].c2;
    }

    fclose(file_out);
}

void shuffle_one (edge ** edges, int min, int max) {
    int r, size;

    size = max - min;

    if (size) {
        r = size > 1 ? min + (rand() % size) + 1 : max;
        swap(&edges[min], &edges[r]);
    }
}

int * access_table (int i, int j) {
    int offset = i * n_cities + j;

    return &table[offset];
}

// void cities_convert(city * input, int * output) {write to output}
// void cities_convert(city * input, int * output) {malloc, modify pointer}
// int * cities_convert(city * input) { malloc ... }

int * cities_convert (city * input) {
    int * output = (int*)malloc(n_cities*sizeof(int));

    for (int i = 0; i < n_cities ; i++)
        output[i] = 0;

    return output;
}