/*
 * R5.A.04 - Qualité Algorithmique
 * TD Profiling : analyseur de fréquence de mots
 *
 * Le programme génère un texte pseudo-aléatoire (toujours le même, grâce
 * à une graine fixe), puis :
 *   1. découpe le texte en lignes et le normalise (minuscules, ponctuation)
 *   2. compte les occurrences de chaque mot (hors mots vides)
 *   3. trie les mots par fréquence
 *   4. calcule des statistiques sur la longueur des mots
 *   5. analyse les bigrammes de lettres
 *   6. génère un rapport complet dans rapport.txt
 *
 * L'empreinte affichée à la fin doit rester IDENTIQUE après optimisation :
 * elle prouve que le résultat du programme n'a pas changé.
 *
 * Compilation :  gcc -O0 -g -pg analyseur.c -o analyseur
 * Exécution :    ./analyseur
 * Profil :       gprof ./analyseur gmon.out > profil.txt
 */

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

#define NB_MOTS_TEXTE   250000
#define NB_MOTS_VOCAB   7000
#define TAILLE_MOT      32
#define MAX_MOTS_UNIQUES 20000
#define GRAINE          20261006UL

/* ------------------------------------------------------------------------ */
/* Générateur pseudo-aléatoire (identique sur toutes les machines)          */
/* ------------------------------------------------------------------------ */

static unsigned long etat_alea = GRAINE;

unsigned long alea(void)
{
    etat_alea = etat_alea * 6364136223846793005UL + 1442695040888963407UL;
    return etat_alea >> 33;
}

/* ------------------------------------------------------------------------ */
/* Fonctions utilitaires sur les chaînes                                    */
/* ------------------------------------------------------------------------ */

int longueur(const char *s)
{
    int n = 0;
    while (s[n] != '\0')
        n++;
    return n;
}

void copier(char *dest, const char *src)
{
    int i = 0;
    while (src[i] != '\0') {
        dest[i] = src[i];
        i++;
    }
    dest[i] = '\0';
}

int egales(const char *a, const char *b)
{
    int i = 0;
    while (a[i] != '\0' && b[i] != '\0') {
        if (a[i] != b[i])
            return 0;
        i++;
    }
    return a[i] == b[i];
}

int comparer(const char *a, const char *b)
{
    int i = 0;
    while (a[i] != '\0' && a[i] == b[i])
        i++;
    return (unsigned char)a[i] - (unsigned char)b[i];
}

void ajouter(char *dest, const char *src)
{
    copier(dest + longueur(dest), src);
}

char en_minuscule(char c)
{
    if (c >= 'A' && c <= 'Z')
        return c - 'A' + 'a';
    return c;
}

int est_lettre(char c)
{
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}

/* ------------------------------------------------------------------------ */
/* Génération du texte                                                      */
/* ------------------------------------------------------------------------ */

static const char *MOTS_VIDES[] = {
    "le", "la", "les", "un", "une", "des", "du", "de", "et", "ou",
    "mais", "donc", "or", "ni", "car", "que", "qui", "quoi", "dont", "ou",
    "a", "au", "aux", "en", "dans", "par", "pour", "sur", "sous", "avec",
    "sans", "chez", "vers", "entre", "il", "elle", "ils", "elles", "on", "nous",
    "vous", "je", "tu", "se", "ce", "cet", "cette", "ces", "son", "sa",
    "ses", "leur", "leurs", "mon", "ma", "mes", "ne", "pas", "plus", "est"
};
#define NB_MOTS_VIDES ((int)(sizeof(MOTS_VIDES) / sizeof(MOTS_VIDES[0])))

static const char *SYLLABES[] = {
    "ba", "be", "bi", "bo", "ca", "co", "da", "de", "di", "fa", "fi", "ga",
    "go", "la", "le", "li", "lo", "ma", "me", "mi", "mo", "na", "ne", "no",
    "pa", "pe", "pi", "po", "ra", "re", "ri", "ro", "sa", "se", "si", "so",
    "ta", "te", "ti", "to", "va", "ve", "vi", "vo", "tion", "ment", "eur", "ique"
};
#define NB_SYLLABES ((int)(sizeof(SYLLABES) / sizeof(SYLLABES[0])))

char **generer_vocabulaire(void)
{
    char **vocab = malloc(NB_MOTS_VOCAB * sizeof(char *));
    for (int i = 0; i < NB_MOTS_VOCAB; i++) {
        vocab[i] = malloc(TAILLE_MOT);
        vocab[i][0] = '\0';
        int nb_syllabes = 2 + alea() % 3;
        for (int j = 0; j < nb_syllabes; j++)
            ajouter(vocab[i], SYLLABES[alea() % NB_SYLLABES]);
    }
    return vocab;
}

char *generer_texte(char **vocab, int nb_mots)
{
    char *texte = malloc((size_t)nb_mots * (TAILLE_MOT + 2) + 1);
    long pos = 0;
    int debut_phrase = 1;
    int mots_restants_phrase = 8 + alea() % 8;

    for (int i = 0; i < nb_mots; i++) {
        const char *mot;
        if (alea() % 100 < 40) {
            mot = MOTS_VIDES[alea() % NB_MOTS_VIDES];
        } else {
            /* distribution biaisée : certains mots sont bien plus fréquents */
            unsigned long r1 = alea() % NB_MOTS_VOCAB;
            unsigned long r2 = alea() % NB_MOTS_VOCAB;
            mot = vocab[(r1 * r2) / NB_MOTS_VOCAB];
        }

        for (int j = 0; mot[j] != '\0'; j++) {
            char c = mot[j];
            if (debut_phrase && j == 0)
                c = c - 'a' + 'A';
            texte[pos++] = c;
        }
        debut_phrase = 0;

        mots_restants_phrase--;
        if (mots_restants_phrase == 0) {
            texte[pos++] = '.';
            texte[pos++] = '\n';
            debut_phrase = 1;
            mots_restants_phrase = 8 + alea() % 8;
        } else if (alea() % 10 == 0) {
            texte[pos++] = ',';
            texte[pos++] = ' ';
        } else {
            texte[pos++] = ' ';
        }
    }
    texte[pos++] = '\n';
    texte[pos] = '\0';
    return texte;
}

/* ------------------------------------------------------------------------ */
/* Découpage et normalisation                                               */
/* ------------------------------------------------------------------------ */

char **decouper_lignes(const char *texte, int *nb_lignes)
{
    int capacite = 1024;
    char **lignes = malloc(capacite * sizeof(char *));
    int n = 0;
    int debut = 0;

    for (int i = 0; texte[i] != '\0'; i++) {
        if (texte[i] == '\n') {
            int taille = i - debut;
            if (n == capacite) {
                capacite *= 2;
                lignes = realloc(lignes, capacite * sizeof(char *));
            }
            lignes[n] = malloc(taille + 1);
            for (int j = 0; j < taille; j++)
                lignes[n][j] = texte[debut + j];
            lignes[n][taille] = '\0';
            n++;
            debut = i + 1;
        }
    }
    *nb_lignes = n;
    return lignes;
}

void normaliser_ligne(char *ligne)
{
    for (int i = 0; i < longueur(ligne); i++) {
        if (est_lettre(ligne[i]))
            ligne[i] = en_minuscule(ligne[i]);
        else
            ligne[i] = ' ';
    }
}

/* ------------------------------------------------------------------------ */
/* Comptage des mots                                                        */
/* ------------------------------------------------------------------------ */

typedef struct {
    char mot[TAILLE_MOT];
    int occurrences;
} Entree;

int est_mot_vide(const char *mot)
{
    for (int i = 0; i < NB_MOTS_VIDES; i++) {
        if (egales(mot, MOTS_VIDES[i]))
            return 1;
    }
    return 0;
}

int chercher_mot(Entree *table, int nb_entrees, const char *mot)
{
    for (int i = 0; i < nb_entrees; i++) {
        if (egales(table[i].mot, mot))
            return i;
    }
    return -1;
}

void compter_mot(Entree *table, int *nb_entrees, const char *mot)
{
    int indice = chercher_mot(table, *nb_entrees, mot);
    if (indice >= 0) {
        table[indice].occurrences++;
    } else {
        copier(table[*nb_entrees].mot, mot);
        table[*nb_entrees].occurrences = 1;
        (*nb_entrees)++;
    }
}

void compter_mots_ligne(Entree *table, int *nb_entrees, const char *ligne,
                        long *nb_mots_total)
{
    char mot[TAILLE_MOT];
    int i = 0;

    while (ligne[i] != '\0') {
        while (ligne[i] == ' ')
            i++;
        int k = 0;
        while (ligne[i] != '\0' && ligne[i] != ' ') {
            if (k < TAILLE_MOT - 1)
                mot[k++] = ligne[i];
            i++;
        }
        mot[k] = '\0';
        if (k > 0) {
            (*nb_mots_total)++;
            if (!est_mot_vide(mot))
                compter_mot(table, nb_entrees, mot);
        }
    }
}

/* ------------------------------------------------------------------------ */
/* Tri : par nombre d'occurrences décroissant, puis ordre alphabétique      */
/* ------------------------------------------------------------------------ */

int doit_echanger(const Entree *a, const Entree *b)
{
    if (a->occurrences != b->occurrences)
        return a->occurrences < b->occurrences;
    return comparer(a->mot, b->mot) > 0;
}

void trier_entrees(Entree *table, int n)
{
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (doit_echanger(&table[j], &table[j + 1])) {
                Entree tmp = table[j];
                table[j] = table[j + 1];
                table[j + 1] = tmp;
            }
        }
    }
}

/* ------------------------------------------------------------------------ */
/* Statistiques                                                             */
/* ------------------------------------------------------------------------ */

double longueur_moyenne(const Entree *table, int n)
{
    long total = 0;
    for (int i = 0; i < n; i++)
        total += longueur(table[i].mot);
    return (double)total / n;
}

double ecart_type_longueur(const Entree *table, int n, double moyenne)
{
    double somme = 0.0;
    for (int i = 0; i < n; i++) {
        double ecart = longueur(table[i].mot) - moyenne;
        somme += ecart * ecart;
    }
    return somme / n;   /* variance ; la racine est prise dans main */
}

/* Recherche du bigramme de lettres le plus fréquent, avec en bonus la
 * troisième lettre qui le suit le plus souvent. */
void analyser_bigrammes(char **lignes, int nb_lignes,
                        char *meilleur, int *occ_meilleur)
{
    static int trigrammes[26][26][26];

    for (int l = 0; l < nb_lignes; l++) {
        const char *s = lignes[l];
        for (int i = 0; s[i] != '\0' && s[i + 1] != '\0' && s[i + 2] != '\0'; i++) {
            if (est_lettre(s[i]) && est_lettre(s[i + 1]) && est_lettre(s[i + 2]))
                trigrammes[s[i] - 'a'][s[i + 1] - 'a'][s[i + 2] - 'a']++;
        }
    }

    *occ_meilleur = -1;
    for (int a = 0; a < 26; a++) {
        for (int b = 0; b < 26; b++) {
            int total = 0;
            for (int c = 0; c < 26; c++)
                total += trigrammes[a][b][c];
            if (total > *occ_meilleur) {
                *occ_meilleur = total;
                int meilleur_c = 0;
                for (int c = 1; c < 26; c++)
                    if (trigrammes[a][b][c] > trigrammes[a][b][meilleur_c])
                        meilleur_c = c;
                meilleur[0] = 'a' + a;
                meilleur[1] = 'a' + b;
                meilleur[2] = 'a' + meilleur_c;
                meilleur[3] = '\0';
            }
        }
    }
}

/* ------------------------------------------------------------------------ */
/* Rapport                                                                  */
/* ------------------------------------------------------------------------ */

char *construire_rapport(const Entree *table, int n)
{
    char *rapport = malloc((size_t)n * 64 + 256);
    char ligne[128];
    rapport[0] = '\0';

    ajouter(rapport, "rang;mot;occurrences\n");
    for (int i = 0; i < n; i++) {
        snprintf(ligne, sizeof(ligne), "%d;%s;%d\n",
                 i + 1, table[i].mot, table[i].occurrences);
        ajouter(rapport, ligne);
    }
    return rapport;
}

unsigned long empreinte(const char *s)
{
    unsigned long h = 1469598103934665603UL;
    for (int i = 0; s[i] != '\0'; i++) {
        h ^= (unsigned char)s[i];
        h *= 1099511628211UL;
    }
    return h;
}

/* ------------------------------------------------------------------------ */

double racine(double x)
{
    double r = x > 1.0 ? x : 1.0;
    for (int i = 0; i < 50; i++)
        r = 0.5 * (r + x / r);
    return r;
}

int main(void)
{
    char **vocab = generer_vocabulaire();
    char *texte = generer_texte(vocab, NB_MOTS_TEXTE);

    int nb_lignes;
    char **lignes = decouper_lignes(texte, &nb_lignes);
    for (int i = 0; i < nb_lignes; i++)
        normaliser_ligne(lignes[i]);

    Entree *table = malloc(MAX_MOTS_UNIQUES * sizeof(Entree));
    int nb_entrees = 0;
    long nb_mots_total = 0;
    for (int i = 0; i < nb_lignes; i++)
        compter_mots_ligne(table, &nb_entrees, lignes[i], &nb_mots_total);

    trier_entrees(table, nb_entrees);

    double moyenne = longueur_moyenne(table, nb_entrees);
    double ecart_type = racine(ecart_type_longueur(table, nb_entrees, moyenne));

    char trigramme[4];
    int occ_trigramme;
    analyser_bigrammes(lignes, nb_lignes, trigramme, &occ_trigramme);

    char *rapport = construire_rapport(table, nb_entrees);
    FILE *f = fopen("rapport.txt", "w");
    if (f != NULL) {
        fputs(rapport, f);
        fclose(f);
    }

    printf("Lignes analysées      : %d\n", nb_lignes);
    printf("Mots au total         : %ld\n", nb_mots_total);
    printf("Mots distincts        : %d\n", nb_entrees);
    printf("Longueur moyenne      : %.3f (écart-type %.3f)\n", moyenne, ecart_type);
    printf("Bigramme le + courant : \"%c%c\" (%d fois, souvent suivi de '%c')\n",
           trigramme[0], trigramme[1], occ_trigramme, trigramme[2]);
    printf("\nTop 10 :\n");
    for (int i = 0; i < 10 && i < nb_entrees; i++)
        printf("  %2d. %-16s %d\n", i + 1, table[i].mot, table[i].occurrences);
    printf("\nEmpreinte du rapport  : %016lx\n", empreinte(rapport));

    free(rapport);
    free(table);
    for (int i = 0; i < nb_lignes; i++)
        free(lignes[i]);
    free(lignes);
    free(texte);
    for (int i = 0; i < NB_MOTS_VOCAB; i++)
        free(vocab[i]);
    free(vocab);
    return 0;
}