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

#include "graph.h"

// we keep track of the best path so far globally
pthread_mutex_t best_lock;
unsigned int best_cost = INT_MAX;
int* best_path = NULL;

// the parameters to our thread function are put into this struct
// pthreads only allows one pointer passed in, so we make it a pointer
// to all the things we need
struct permute_params {
    struct graph* graph;
    int* array;
    int start;
    int end;
};

// run through all permutations
void* permute(void* vparams) {
    // pull the values we need out of the struct
    struct permute_params* params = (struct permute_params*) vparams;
    struct graph* graph = params->graph;
    int* array = params->array;
    int start = params->start;
    int end = params->end;

    // if this is the end of the permutation, consider this path
    if (start == end) {
        unsigned int total_cost = 0;
        
        // add up this route
        for (int i = 0; i < (graph->size - 1); i++) {
            // get the cost of this leg
            int leg = get_cost(graph, array[i], array[i + 1]);
            total_cost = total_cost + leg;
        }
        
        // add end city back to start
        total_cost = total_cost + get_cost(graph, array[graph->size - 1], array[0]);

        // check if this is the best so far
        if (total_cost < best_cost) {
            // if it is, lock the mutex which protects the best path
            pthread_mutex_lock(&best_lock);

            // now we must check if this is STILL the best path
            // it's just possible that another thread updated it while we were
            // waiting on the mutex to be released
            if (total_cost < best_cost) {
                best_cost = total_cost;
                for (int i = 0; i < graph->size; i++) {
                    best_path[i] = array[i];
                }
            }
            pthread_mutex_unlock(&best_lock);
        }
    }

    // otherwise we are not at the end of this permutation yet
    else {
        // for each node in the list
        for (int i = start; i <= end; i++) {
            // swap this with the start
            int temp = array[start];
            array[start] = array[i];
            array[i] = temp;

            // permute all after the start
            params->start++;
            permute(params);
            params->start--;

            // swap it back
            temp = array[start];
            array[start] = array[i];
            array[i] = temp;
        }
    }
}

void shortestTour(struct graph* graph) {
    // use N-1 threads
    pthread_t threads[graph->size - 1];
    
    // setup our mutex for protecting the best path
    pthread_mutex_init(&best_lock, NULL);
    
    // launch N-1 threads
    for (int i = 0; i < graph->size - 1; i++) {
        // make an array of the nodes
        int* nodes = malloc(sizeof(int) * graph->size);
        
        // fix the start city, then fill in the rest with 1 through N-1
        nodes[0] = 0;
        for (int j = 1; j < graph->size; j++) {
            nodes[j] = j;
        }

        // swap i+1 into 1st slot to fix starting point for this thread
        int temp = nodes[i + 1];
        nodes[i + 1] = nodes[1];
        nodes[1] = temp;
        printf("Thread %d will start with array: ", i);
        for (int j = 0; j < graph->size; j++) {
            printf("%d, ", nodes[j]);
        }
        printf("\n");
       
        // launch the threads
        struct permute_params* params = malloc(sizeof(struct permute_params));
        params->graph = graph;
        params->array = nodes;
        params->start = 2;
        params->end = graph->size - 1;
        pthread_create(&threads[i], NULL, &permute, params);
    }

    // join all the threads
    for (int i = 0; i < graph->size - 1; i++) {
        pthread_join(threads[i], NULL);
    }

    // print the results
    printf("The tour should go through:\n");
    for (int i = 0; i < graph->size; i++) {
        printf("%s, ", get_label(graph, best_path[i]));
    }
    
    printf("and back to %s.\n", get_label(graph, best_path[0]));
    printf("For a total cost of %d.\n", best_cost);
}

int main(int argc, char** argv) {
    if (argc < 2) {
        printf("Please pass an input file!\n");
        return 0;
    }

    // open the file and read the input size
    FILE* file = fopen(argv[1], "r");
    int size;
    fscanf(file, "%d", &size);

    // create a graph with the given size
    struct graph graph;
    init_graph(&graph, size);

    // read the node labels
    for (int i = 0; i < size; i++) {
        char label[64];
        fscanf(file, "%s", label);
        set_label(&graph, i, label);

    }

    // read the edge information
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            int cost;
            fscanf(file, "%d", &cost);
            insert_edge(&graph, i, j, cost);
        }
    }

    // make space for the best path
    best_path = malloc(sizeof(int) * size);

    // compute the shortest tour
    shortestTour(&graph);
}