/* dv_sim.c: vector de distancias, ronda por ronda.
 *
 * Simula routers que solo conocen sus enlaces y lo que les cuentan sus vecinos.
 * Cada router guarda, por destino, un costo y un next hop, y aplica dos reglas:
 *   1. Lo que diga su next hop actual se acepta siempre, aunque sea peor.
 *   2. Lo que diga otro vecino se acepta solo si mejora el costo.
 *
 *   ./dv_sim GRAFO [--mode plain|split|poison] [--dest NODO] [--inf N] [--max N]
 *            [--fail U V | --set U V COSTO | --lie NODO DESTINO COSTO]
 *            [--order U:V,U:V,...]
 *
 * Primero converge y después aplica el evento. Sin --order, en cada ronda todos
 * anuncian a la vez. Con --order, cada paso es un solo anuncio U -> V, en ese orden,
 * que se repite: sirve para fijar cuál mensaje llega antes.
 */
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES 16
#define NAME_SIZE 8
#define NO_HOP (-1)
#define MAX_ORDER 64
#define EXPIRY_ROUNDS 6 /* sin noticias del next hop por tantas rondas, la ruta vence */

enum mode { MODE_PLAIN, MODE_SPLIT, MODE_POISON };

struct message {
    int from;
    int to;
};

static char names[MAX_NODES][NAME_SIZE];
static int node_count;
static int link_cost[MAX_NODES][MAX_NODES]; /* 0 = sin enlace */
static int dist[MAX_NODES][MAX_NODES];
static int hop[MAX_NODES][MAX_NODES];
static int age[MAX_NODES][MAX_NODES];
static int infinity = 16;
static enum mode mode = MODE_PLAIN;
static long announcements;
static bool stopped_by_limit; /* run terminó por --max, no porque nada cambiara */
/* Un router que miente: anuncia este costo sin importar lo que sepa. */
static int liar = NO_HOP;
static int lie_dest = NO_HOP;
static int lie_cost;

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 require_node(const char *name) {
    for (int i = 0; i < node_count; i++) {
        if (strcmp(names[i], name) == 0) {
            return i;
        }
    }
    fprintf(stderr, "no existe el nodo %s\n", name);
    exit(EXIT_FAILURE);
}

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

static void load_graph(const char *path) {
    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) {
                link_cost[u][v] = value;
                link_cost[v][u] = value;
            }
        }
        if (fclose(file) != 0) {
            perror("fclose");
            exit(EXIT_FAILURE);
        }
        if (pass == 0) {
            qsort(names, (size_t)node_count, NAME_SIZE, compare_names);
        }
    }
}

/* Al inicio, cada router conoce solo sus enlaces directos. */
static void init_tables(void) {
    for (int u = 0; u < node_count; u++) {
        for (int d = 0; d < node_count; d++) {
            bool direct = link_cost[u][d] > 0 && link_cost[u][d] < infinity;
            dist[u][d] = u == d ? 0 : (direct ? link_cost[u][d] : infinity);
            hop[u][d] = u == d ? u : (direct ? d : NO_HOP);
        }
    }
}

/* Qué le anuncia from a to sobre un destino. Devuelve false si no anuncia nada. */
static bool advertised(int from, int to, int d, int *value) {
    if (from == liar && d == lie_dest) {
        *value = lie_cost;
        return true;
    }
    if (hop[from][d] == to && d != from) {
        if (mode == MODE_SPLIT) {
            return false; /* split horizon: no se lo cuento a quien me lo enseñó */
        }
        if (mode == MODE_POISON) {
            *value = infinity; /* poison reverse: se lo cuento como infinito */
            return true;
        }
    }
    *value = dist[from][d];
    return true;
}

/* Aplica el anuncio de un vecino sobre un destino. Devuelve si cambió la tabla. */
static bool apply(int router, int neighbor, int d, int value) {
    if (d == router || (router == liar && d == lie_dest)) {
        return false;
    }
    int through = value + link_cost[router][neighbor];
    if (through > infinity) {
        through = infinity;
    }
    if (hop[router][d] == neighbor) {
        age[router][d] = 0;
        if (through != dist[router][d]) {
            dist[router][d] = through;
            if (through == infinity) {
                hop[router][d] = NO_HOP;
            }
            return true;
        }
    } else if (through < dist[router][d]) {
        dist[router][d] = through;
        hop[router][d] = neighbor;
        age[router][d] = 0;
        return true;
    }
    return false;
}

/* Las rutas de quien calla envejecen. Solo pasa con split horizon. */
static bool expire_routes(void) {
    bool changed = false;
    for (int u = 0; u < node_count; u++) {
        for (int d = 0; d < node_count; d++) {
            if (u == d || hop[u][d] == NO_HOP || (u == liar && d == lie_dest)) {
                continue;
            }
            if (++age[u][d] > EXPIRY_ROUNDS) {
                dist[u][d] = infinity;
                hop[u][d] = NO_HOP;
                age[u][d] = 0;
                changed = true;
            }
        }
    }
    return changed;
}

static bool any_aging(void) {
    for (int u = 0; u < node_count; u++) {
        for (int d = 0; d < node_count; d++) {
            if (age[u][d] > 0) {
                return true;
            }
        }
    }
    return false;
}

/* Una ronda: todos arman sus anuncios con la tabla de antes y luego todos los
 * aplican. El next hop actual se atiende primero, para que el resultado no dependa
 * del orden de los vecinos. */
static bool round_all_at_once(void) {
    static int inbox[MAX_NODES][MAX_NODES][MAX_NODES];
    static bool present[MAX_NODES][MAX_NODES][MAX_NODES];
    for (int from = 0; from < node_count; from++) {
        for (int to = 0; to < node_count; to++) {
            if (link_cost[from][to] == 0) {
                continue;
            }
            announcements++;
            for (int d = 0; d < node_count; d++) {
                present[from][to][d] = advertised(from, to, d, &inbox[from][to][d]);
            }
        }
    }
    bool changed = expire_routes();
    for (int to = 0; to < node_count; to++) {
        for (int d = 0; d < node_count; d++) {
            int current = hop[to][d];
            if (current != NO_HOP && current != to && link_cost[current][to] > 0
                && present[current][to][d]) {
                changed |= apply(to, current, d, inbox[current][to][d]);
            }
        }
        for (int from = 0; from < node_count; from++) {
            if (link_cost[from][to] == 0) {
                continue;
            }
            for (int d = 0; d < node_count; d++) {
                if (present[from][to][d] && hop[to][d] != from) {
                    changed |= apply(to, from, d, inbox[from][to][d]);
                }
            }
        }
    }
    return changed;
}

/* Un solo anuncio, que el receptor aplica de inmediato. */
static bool single_message(struct message message) {
    announcements++;
    bool changed = false;
    for (int d = 0; d < node_count; d++) {
        int value;
        if (advertised(message.from, message.to, d, &value)) {
            changed |= apply(message.to, message.from, d, value);
        }
    }
    return changed;
}

static void format_entry(char *cell, size_t size, int router, int d) {
    if (dist[router][d] >= infinity) {
        snprintf(cell, size, "inf");
    } else if (router == d) {
        snprintf(cell, size, "0");
    } else if (hop[router][d] == NO_HOP) {
        snprintf(cell, size, "%d", dist[router][d]);
    } else {
        snprintf(cell, size, "%d/%s", dist[router][d], names[hop[router][d]]);
    }
}

static void print_matrix(void) {
    printf("    ");
    for (int d = 0; d < node_count; d++) {
        printf(" %-6s", names[d]);
    }
    printf("\n");
    for (int u = 0; u < node_count; u++) {
        printf("%-4s", names[u]);
        for (int d = 0; d < node_count; d++) {
            char cell[32];
            format_entry(cell, sizeof cell, u, d);
            printf(" %-6s", cell);
        }
        printf("\n");
    }
}

/* Busca un ciclo de forwarding hacia d. Lo imprime si lo hay. */
static void print_loop(int d) {
    for (int start = 0; start < node_count; start++) {
        if (start == d) {
            continue;
        }
        int visits[MAX_NODES] = {0};
        int current = start;
        while (current != d && current != NO_HOP && visits[current] == 0) {
            visits[current] = 1;
            current = hop[current][d];
        }
        if (current == d || current == NO_HOP) {
            continue;
        }
        /* current está en el ciclo; se imprime una vez, desde su nodo menor */
        int lowest = current;
        for (int walk = hop[current][d]; walk != current; walk = hop[walk][d]) {
            if (walk < lowest) {
                lowest = walk;
            }
        }
        printf("  ciclo: %s", names[lowest]);
        for (int walk = hop[lowest][d]; walk != lowest; walk = hop[walk][d]) {
            printf(" > %s", names[walk]);
        }
        printf(" > %s", names[lowest]);
        return;
    }
}

static void print_line(const char *label, int d) {
    printf("%-14s", label);
    for (int u = 0; u < node_count; u++) {
        if (u == d) {
            continue;
        }
        char cell[32];
        format_entry(cell, sizeof cell, u, d);
        printf(" %s=%-6s", names[u], cell);
    }
    print_loop(d);
    printf("\n");
}

/* Corre hasta que nada cambie. Devuelve cuántas rondas o pasos hicieron cambios. */
static int run(int dest, bool show, const struct message *order, int order_size, int max_rounds) {
    int last_change = 0;
    char label[64];
    if (order_size > 0) {
        int unchanged_steps = 0;
        for (int step = 1; step <= max_rounds; step++) {
            struct message message = order[(step - 1) % order_size];
            bool changed = single_message(message);
            if (changed) {
                last_change = step;
                unchanged_steps = 0;
            } else {
                unchanged_steps++;
            }
            if (show && dest != NO_HOP) {
                snprintf(label, sizeof label, "paso %d %s>%s", step, names[message.from],
                         names[message.to]);
                print_line(label, dest);
            }
            if (unchanged_steps >= order_size) {
                return last_change;
            }
        }
        stopped_by_limit = true;
        return last_change;
    }
    for (int round = 1; round <= max_rounds; round++) {
        bool changed = round_all_at_once();
        if (changed) {
            last_change = round;
        }
        if (show && changed) {
            if (dest != NO_HOP) {
                snprintf(label, sizeof label, "ronda %d", round);
                print_line(label, dest);
            } else {
                printf("ronda %d\n", round);
                print_matrix();
                printf("\n");
            }
        }
        if (!changed && !any_aging()) {
            return last_change;
        }
    }
    stopped_by_limit = true;
    return last_change;
}

static void fail_link(int u, int v) {
    link_cost[u][v] = 0;
    link_cost[v][u] = 0;
    for (int d = 0; d < node_count; d++) {
        if (hop[u][d] == v) {
            dist[u][d] = infinity;
            hop[u][d] = NO_HOP;
        }
        if (hop[v][d] == u) {
            dist[v][d] = infinity;
            hop[v][d] = NO_HOP;
        }
    }
}

/* El costo cambia en los dos extremos. Las rutas por ese enlace suben o bajan igual. */
static void set_link(int u, int v, int value) {
    int delta = value - link_cost[u][v];
    link_cost[u][v] = value;
    link_cost[v][u] = value;
    for (int d = 0; d < node_count; d++) {
        if (hop[u][d] == v) {
            dist[u][d] += delta;
        }
        if (hop[v][d] == u) {
            dist[v][d] += delta;
        }
    }
}

static int parse_order(char *text, struct message *order) {
    int size = 0;
    for (char *pair = strtok(text, ","); pair != NULL; pair = strtok(NULL, ",")) {
        char *colon = strchr(pair, ':');
        if (colon == NULL || size == MAX_ORDER) {
            fprintf(stderr, "--order mal formado: %s\n", pair);
            exit(EXIT_FAILURE);
        }
        *colon = '\0';
        order[size].from = require_node(pair);
        order[size].to = require_node(colon + 1);
        size++;
    }
    return size;
}

static void usage(const char *program) {
    fprintf(stderr,
            "uso: %s GRAFO [--mode plain|split|poison] [--dest NODO] [--inf N] [--max N]\n"
            "       [--fail U V | --set U V COSTO | --lie NODO DESTINO COSTO]\n"
            "       [--order U:V,U:V,...]\n",
            program);
    exit(EXIT_FAILURE);
}

int main(int argc, char *argv[]) {
    if (argc < 2) {
        usage(argv[0]);
    }
    load_graph(argv[1]);

    int dest = NO_HOP;
    int max_rounds = 200;
    const char *fail_args[2] = {NULL, NULL};
    const char *set_args[3] = {NULL, NULL, NULL};
    const char *lie_args[3] = {NULL, NULL, NULL};
    char *order_text = NULL;
    for (int i = 2; i < argc; i++) {
        const char *flag = argv[i];
        int remaining = argc - i - 1;
        if (strcmp(flag, "--mode") == 0 && remaining >= 1) {
            const char *value = argv[++i];
            if (strcmp(value, "plain") == 0) {
                mode = MODE_PLAIN;
            } else if (strcmp(value, "split") == 0) {
                mode = MODE_SPLIT;
            } else if (strcmp(value, "poison") == 0) {
                mode = MODE_POISON;
            } else {
                usage(argv[0]);
            }
        } else if (strcmp(flag, "--dest") == 0 && remaining >= 1) {
            dest = require_node(argv[++i]);
        } else if (strcmp(flag, "--inf") == 0 && remaining >= 1) {
            infinity = atoi(argv[++i]);
        } else if (strcmp(flag, "--max") == 0 && remaining >= 1) {
            max_rounds = atoi(argv[++i]);
        } else if (strcmp(flag, "--fail") == 0 && remaining >= 2) {
            fail_args[0] = argv[++i];
            fail_args[1] = argv[++i];
        } else if (strcmp(flag, "--set") == 0 && remaining >= 3) {
            set_args[0] = argv[++i];
            set_args[1] = argv[++i];
            set_args[2] = argv[++i];
        } else if (strcmp(flag, "--lie") == 0 && remaining >= 3) {
            lie_args[0] = argv[++i];
            lie_args[1] = argv[++i];
            lie_args[2] = argv[++i];
        } else if (strcmp(flag, "--order") == 0 && remaining >= 1) {
            order_text = argv[++i];
        } else {
            usage(argv[0]);
        }
    }
    if (infinity <= 0 || max_rounds <= 0) {
        usage(argv[0]);
    }

    struct message order[MAX_ORDER];
    int order_size = order_text != NULL ? parse_order(order_text, order) : 0;
    bool has_event = fail_args[0] != NULL || set_args[0] != NULL || lie_args[0] != NULL;

    init_tables();
    if (!has_event) {
        if (dest != NO_HOP) {
            print_line("ronda 0", dest);
        } else {
            printf("ronda 0\n");
            print_matrix();
            printf("\n");
        }
    }
    int rounds = run(dest, !has_event, NULL, 0, max_rounds);
    printf("convergió: %d %s, %ld anuncios\n", rounds, rounds == 1 ? "ronda" : "rondas",
           announcements);
    if (!has_event) {
        return EXIT_SUCCESS;
    }

    if (dest != NO_HOP) {
        print_line("antes", dest);
    } else {
        print_matrix();
    }
    announcements = 0;
    if (fail_args[0] != NULL) {
        fail_link(require_node(fail_args[0]), require_node(fail_args[1]));
        printf("--- cae el enlace %s-%s\n", fail_args[0], fail_args[1]);
    } else if (set_args[0] != NULL) {
        set_link(require_node(set_args[0]), require_node(set_args[1]), atoi(set_args[2]));
        printf("--- el enlace %s-%s pasa a costar %s\n", set_args[0], set_args[1], set_args[2]);
    } else {
        liar = require_node(lie_args[0]);
        lie_dest = require_node(lie_args[1]);
        lie_cost = atoi(lie_args[2]);
        dist[liar][lie_dest] = lie_cost;
        hop[liar][lie_dest] = NO_HOP;
        printf("--- %s anuncia %s con costo %s\n", lie_args[0], lie_args[1], lie_args[2]);
    }
    if (dest != NO_HOP) {
        print_line("evento", dest);
    }
    rounds = run(dest, true, order, order_size, max_rounds);
    const char *unit = order_size > 0 ? (rounds == 1 ? "paso" : "pasos")
                                      : (rounds == 1 ? "ronda" : "rondas");
    printf("%s: %d %s, %ld anuncios\n", stopped_by_limit ? "detenido por --max" : "volvió a converger",
           rounds, unit, announcements);
    return EXIT_SUCCESS;
}