#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
unsigned int best_cost = INT_MAX;
int* best_path = NULL;

// run through all permutations
void permute(struct graph* graph, int* array, int start, int 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]);
        //printf("Found a path with cost %d.\n", total_cost);

        // check if this is the best so far
        if (total_cost < best_cost) {
            best_cost = total_cost;
            for (int i = 0; i < graph->size; i++) {
                best_path[i] = array[i];
            }
        }
    }

    // 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
            permute(graph, array, start + 1, end);

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

void shortestTour(struct graph* graph) {
    // make an array of the nodes
    int* nodes = malloc(sizeof(int) * graph->size);
    for (int i = 0; i < graph->size; i++) {
        nodes[i] = i;
    }

    // run through all permutations
    permute(graph, nodes, 1, graph->size - 1);

    // 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
    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);
}