/*
 * diferencas - Compara dois arquivos linha a linha (análogo ao diff)
 * Uso: diferencas <arquivo1> <arquivo2>
 * Mostra as linhas que diferem entre os dois arquivos.
 */

#define _DEFAULT_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

#define MAX_LINHA 8192

/*
 * Algoritmo LCS (Longest Common Subsequence) simples para comparar
 * dois arquivos e mostrar as diferenças.
 */

typedef struct {
    char **linhas;
    int    count;
    int    cap;
} Arquivo;

static int carregar_arquivo(const char *nome, Arquivo *arq) {
    FILE *fp = fopen(nome, "r");
    if (!fp) {
        fprintf(stderr, "diferencas: erro ao abrir '%s': %s\n", nome, strerror(errno));
        return -1;
    }

    arq->count = 0;
    arq->cap   = 256;
    arq->linhas = malloc(arq->cap * sizeof(char *));
    if (!arq->linhas) {
        fprintf(stderr, "diferencas: erro de memória\n");
        fclose(fp);
        return -1;
    }

    char buf[MAX_LINHA];
    while (fgets(buf, sizeof(buf), fp)) {
        /* Remove trailing newline para comparação, mas guarda original */
        size_t len = strlen(buf);
        if (len > 0 && buf[len - 1] == '\n') buf[len - 1] = '\0';

        if (arq->count >= arq->cap) {
            arq->cap *= 2;
            arq->linhas = realloc(arq->linhas, arq->cap * sizeof(char *));
            if (!arq->linhas) {
                fprintf(stderr, "diferencas: erro de memória\n");
                fclose(fp);
                return -1;
            }
        }
        arq->linhas[arq->count] = strdup(buf);
        arq->count++;
    }

    fclose(fp);
    return 0;
}

static void liberar_arquivo(Arquivo *arq) {
    for (int i = 0; i < arq->count; i++)
        free(arq->linhas[i]);
    free(arq->linhas);
}

/* Algoritmo simples de diff baseado em LCS com backtracking */
static void exibir_diferencas(Arquivo *a, Arquivo *b,
                               const char *nome_a, const char *nome_b) {
    int m = a->count;
    int n = b->count;

    /* Tabela LCS */
    int **dp = malloc((m + 1) * sizeof(int *));
    for (int i = 0; i <= m; i++) {
        dp[i] = calloc(n + 1, sizeof(int));
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (strcmp(a->linhas[i - 1], b->linhas[j - 1]) == 0) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }

    /* Backtrack para gerar diff */
    int i = m, j = n;
    int tem_diffs = 0;

    /* Arrays temporários para armazenar diff chunks */
    typedef struct { int linha; char *texto; int tipo; } DiffLinha;
    /* tipo: 0 = igual, -1 = removido (só em A), +1 = adicionado (só em B) */
    DiffLinha *diff = malloc((m + n) * sizeof(DiffLinha));
    int diff_count = 0;

    while (i > 0 || j > 0) {
        if (i > 0 && j > 0 && strcmp(a->linhas[i - 1], b->linhas[j - 1]) == 0) {
            diff[diff_count].linha = i;
            diff[diff_count].texto = a->linhas[i - 1];
            diff[diff_count].tipo  = 0;
            diff_count++;
            i--; j--;
        } else if (j > 0 && (i == 0 || dp[i][j - 1] >= dp[i - 1][j])) {
            diff[diff_count].linha = j;
            diff[diff_count].texto = b->linhas[j - 1];
            diff[diff_count].tipo  = 1; /* adicionado em B */
            diff_count++;
            tem_diffs = 1;
            j--;
        } else if (i > 0 && (j == 0 || dp[i][j - 1] < dp[i - 1][j])) {
            diff[diff_count].linha = i;
            diff[diff_count].texto = a->linhas[i - 1];
            diff[diff_count].tipo  = -1; /* removido de A */
            diff_count++;
            tem_diffs = 1;
            i--;
        }
    }

    /* Inverte para exibir em ordem crescente */
    if (!tem_diffs) {
        printf("Os arquivos '%s' e '%s' são idênticos.\n", nome_a, nome_b);
    } else {
        for (int k = diff_count - 1; k >= 0; k--) {
            DiffLinha *dl = &diff[k];
            switch (dl->tipo) {
                case -1: printf("< %4d | %s\n", dl->linha, dl->texto); break;
                case  1: printf("> %4d | %s\n", dl->linha, dl->texto); break;
                default: break; /* não mostra linhas iguais */
            }
        }
    }

    free(diff);
    for (int i = 0; i <= m; i++) free(dp[i]);
    free(dp);
}

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(stderr, "Uso: diferencas <arquivo1> <arquivo2>\n");
        return EXIT_FAILURE;
    }

    Arquivo a, b;
    if (carregar_arquivo(argv[1], &a) != 0)
        return EXIT_FAILURE;
    if (carregar_arquivo(argv[2], &b) != 0) {
        liberar_arquivo(&a);
        return EXIT_FAILURE;
    }

    exibir_diferencas(&a, &b, argv[1], argv[2]);

    liberar_arquivo(&a);
    liberar_arquivo(&b);
    return EXIT_SUCCESS;
}