/* dijkstra.c: el algoritmo de estado de enlace, paso a paso.
 *
 * Lee un grafo (líneas "nodo nodo costo") y corre Dijkstra desde un nodo. Imprime
 * la tabla de cada iteración y la forwarding table que resulta. Cuando dos caminos
 * empatan guarda los dos: un destino puede tener varios next hop (ECMP).
 *
 *   ./dijkstra graphs/six.txt a
 */
#include <inttypes.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES 32
#define NAME_SIZE 8
#define INFINITE_COST INT32_MAX

static char names[MAX_NODES][NAME_SIZE];
static int node_count;
static int32_t cost[MAX_NODES][MAX_NODES]; /* 0 = sin enlace */

static int find_or_add(const char *name) {
    for (int i = 0; i < node_count; i++) {
        if (strcmp(names[i], name) == 0) {
            return i;
        }
    }
    if (node_count == MAX_NODES) {
        fprintf(stderr, "demasiados nodos (máximo %d)\n", MAX_NODES);
        exit(EXIT_FAILURE);
    }
    snprintf(names[node_count], NAME_SIZE, "%s", name);
    return node_count++;
}

static int compare_names(const void *left, const void *right) {
    return strcmp(left, right);
}

/* Primera pasada: nombres, en orden alfabético. Segunda pasada: costos. */
static int load_graph(const char *path) {
    int links = 0;
    for (int pass = 0; pass < 2; pass++) {
        FILE *file = fopen(path, "r");
        if (file == NULL) {
            perror(path);
            exit(EXIT_FAILURE);
        }
        char line[128];
        while (fgets(line, sizeof line, file) != NULL) {
            char left[NAME_SIZE];
            char right[NAME_SIZE];
            int value;
            if (line[0] == '#' || sscanf(line, "%7s %7s %d", left, right, &value) != 3) {
                continue;
            }
            if (value <= 0) {
                fprintf(stderr, "costo inválido: %s", line);
                exit(EXIT_FAILURE);
            }
            int u = find_or_add(left);
            int v = find_or_add(right);
            if (pass == 1) {
                cost[u][v] = value;
                cost[v][u] = value;
                links++;
            }
        }
        if (fclose(file) != 0) {
            perror("fclose");
            exit(EXIT_FAILURE);
        }
        if (pass == 0) {
            qsort(names, (size_t)node_count, NAME_SIZE, compare_names);
        }
    }
    return links;
}

static void print_header(int source) {
    printf("%-4s %-*s", "paso", node_count + 1, "N'");
    for (int v = 0; v < node_count; v++) {
        if (v != source) {
            printf(" %-8s", names[v]);
        }
    }
    printf("\n");
}

/* Una celda como "6,cd": costo y predecesores en el camino más corto. */
static void print_row(int step, int source, const int *order, int done_count,
                      const int32_t *dist, const uint32_t *previous, const bool *done) {
    printf("%-4d ", step);
    int written = 0;
    for (int i = 0; i < done_count; i++) {
        written += printf("%s", names[order[i]]);
    }
    printf("%*s", node_count + 1 > written ? node_count + 1 - written : 0, "");
    for (int v = 0; v < node_count; v++) {
        if (v == source) {
            continue;
        }
        char cell[64] = "-";
        if (done[v]) {
            snprintf(cell, sizeof cell, "*");
        } else if (dist[v] != INFINITE_COST) {
            size_t used = (size_t)snprintf(cell, sizeof cell, "%" PRId32 ",", dist[v]);
            for (int u = 0; u < node_count; u++) {
                if (previous[v] & (UINT32_C(1) << u)) {
                    used += (size_t)snprintf(cell + used, sizeof cell - used, "%s", names[u]);
                }
            }
        }
        printf(" %-8s", cell);
    }
    printf("\n");
}

static void dijkstra(int source) {
    int32_t dist[MAX_NODES];
    uint32_t previous[MAX_NODES] = {0}; /* predecesores, como conjunto de bits */
    uint32_t first_hops[MAX_NODES] = {0}; /* next hop desde el origen, también */
    bool done[MAX_NODES] = {false};
    int order[MAX_NODES];
    int done_count = 0;

    for (int v = 0; v < node_count; v++) {
        dist[v] = INFINITE_COST;
    }
    dist[source] = 0;
    done[source] = true;
    order[done_count++] = source;
    for (int v = 0; v < node_count; v++) {
        if (cost[source][v] > 0) {
            dist[v] = cost[source][v];
            previous[v] = UINT32_C(1) << source;
            first_hops[v] = UINT32_C(1) << v;
        }
    }

    print_header(source);
    print_row(0, source, order, done_count, dist, previous, done);
    for (int step = 1; step < node_count; step++) {
        /* El más cercano que falta. Con empate, el primero en orden alfabético. */
        int nearest = -1;
        for (int v = 0; v < node_count; v++) {
            if (!done[v] && dist[v] != INFINITE_COST && (nearest < 0 || dist[v] < dist[nearest])) {
                nearest = v;
            }
        }
        if (nearest < 0) {
            break; /* lo que queda no se alcanza */
        }
        done[nearest] = true;
        order[done_count++] = nearest;
        for (int v = 0; v < node_count; v++) {
            if (done[v] || cost[nearest][v] == 0) {
                continue;
            }
            int32_t through = dist[nearest] + cost[nearest][v];
            if (through < dist[v]) {
                dist[v] = through;
                previous[v] = UINT32_C(1) << nearest;
                first_hops[v] = first_hops[nearest];
            } else if (through == dist[v]) {
                /* Empate: este camino se suma a los que ya había. */
                previous[v] |= UINT32_C(1) << nearest;
                first_hops[v] |= first_hops[nearest];
            }
        }
        print_row(step, source, order, done_count, dist, previous, done);
    }

    printf("\nforwarding table de %s\n", names[source]);
    printf("%-8s %-6s %s\n", "destino", "costo", "next hop");
    for (int v = 0; v < node_count; v++) {
        if (v == source) {
            continue;
        }
        if (dist[v] == INFINITE_COST) {
            printf("%-8s %-6s -\n", names[v], "inf");
            continue;
        }
        printf("%-8s %-6" PRId32, names[v], dist[v]);
        for (int u = 0; u < node_count; u++) {
            if (first_hops[v] & (UINT32_C(1) << u)) {
                printf(" %s", names[u]);
            }
        }
        printf("\n");
    }
}

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(stderr, "uso: %s GRAFO ORIGEN\n", argv[0]);
        return EXIT_FAILURE;
    }
    int links = load_graph(argv[1]);
    int source = -1;
    for (int v = 0; v < node_count; v++) {
        if (strcmp(names[v], argv[2]) == 0) {
            source = v;
        }
    }
    if (source < 0) {
        fprintf(stderr, "no existe el nodo %s\n", argv[2]);
        return EXIT_FAILURE;
    }
    printf("%d nodos, %d enlaces, origen %s\n\n", node_count, links, argv[2]);
    dijkstra(source);
    return EXIT_SUCCESS;
}