/*
 * R5.A.04 - Qualité Algorithmique
 * TD Complexité algorithmique : analyse des transactions d'une banque
 *
 * Le programme génère des transactions pseudo-aléatoires (toujours les
 * mêmes, grâce à une graine fixe), puis calcule plusieurs indicateurs
 * et produit un rapport dans rapport.txt.
 *
 * L'empreinte affichée à la fin doit rester IDENTIQUE après vos
 * optimisations : elle prouve que le résultat n'a pas changé.
 *
 * Interdit : modifier les constantes, la génération des données,
 * le format du rapport, ou écrire les résultats « en dur ».
 *
 * Compilation : gcc -O2 banque.c -o banque
 * Profiling   : gcc -O0 -g -pg banque.c -o banque && ./banque && gprof ./banque gmon.out
 */

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

#define NB_TRANSACTIONS 30000
#define NB_CLIENTS      2000
#define NB_JOURS        1000
#define NB_REQUETES     30000
#define MONTANT_MONNAIE 400
#define GRAINE          20261020UL

typedef struct {
    int id;
    int client;
    int jour;
    long montant;   /* en centimes, négatif pour un débit */
} Transaction;

/* ------------------------------------------------------------------ */
/* Données (ne pas modifier)                                          */
/* ------------------------------------------------------------------ */

static unsigned long etat_alea = GRAINE;

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

Transaction *generer_transactions(int n)
{
    Transaction *t = malloc(n * sizeof(Transaction));
    for (int i = 0; i < n; i++) {
        t[i].id = i;
        t[i].client = alea() % NB_CLIENTS;
        t[i].jour = alea() % NB_JOURS;
        if (i > 0 && alea() % 20 == 0)
            t[i].montant = -t[alea() % i].montant;   /* opération inverse */
        else
            t[i].montant = (long)(alea() % 100001) - 50000;
    }
    for (int i = n - 1; i > 0; i--) {                /* mélange des id */
        int j = alea() % (i + 1);
        int tmp = t[i].id;
        t[i].id = t[j].id;
        t[j].id = tmp;
    }
    return t;
}

/* ------------------------------------------------------------------ */
/* Fonctions à analyser et à optimiser                                */
/* ------------------------------------------------------------------ */

/* F1 : trie les transactions par montant croissant, puis par id */
int comparer_transactions(const void *a, const void *b)
{
    const Transaction *t1 = a;
    const Transaction *t2 = b;

    if (t1->montant < t2->montant)
        return -1;

    if (t1->montant > t2->montant)
        return 1;

    if (t1->id < t2->id)
        return -1;

    if (t1->id > t2->id)
        return 1;

    return 0;
}

void trier_par_montant(Transaction *t, int n)
{
    qsort(t, n, sizeof(Transaction), comparer_transactions);
}


/* F2 : nombre de clients ayant au moins une transaction */
int nb_clients_distincts(const Transaction *t, int n)
{
    int nb = 0;
    int vus[NB_CLIENTS] = {0};

    for (int i = 0; i < n; i++) {
        int client = t[i].client;

        if (!vus[client]) {
            vus[client] = 1;
            nb++;
        }
    }

    return nb;
}

/* F3 : solde total de chaque client */
void total_par_client(const Transaction *t, int n, long *totaux)
{
    for (int c = 0; c < NB_CLIENTS; c++)
        totaux[c] = 0;
    for (int i = 0; i < n; i++)
        totaux[t[i].client] += t[i].montant;
}

/* F4 : solde total de chaque jour */
void total_par_jour(const Transaction *t, int n, long *totaux)
{
    for (int j = 0; j < NB_JOURS; j++) {
        totaux[j] = 0;
        for (int i = 0; i < n; i++)
            if (t[i].jour == j)
                totaux[j] += t[i].montant;
    }
}

/* F5 : période de jours consécutifs dont la somme des soldes est maximale */
long meilleure_periode(const long *totaux, int nb_jours, int *debut, int *fin)
{
    long P[NB_JOURS + 1];
    long sufmax[NB_JOURS + 1];

    P[0] = 0;
    for (int k = 0; k < nb_jours; k++)
        P[k + 1] = P[k] + totaux[k];

    long min_prefixe = P[0];
    long meilleur = totaux[0];
    for (int j = 0; j < nb_jours; j++) {
        if (P[j] < min_prefixe) min_prefixe = P[j];
        if (P[j + 1] - min_prefixe > meilleur)
            meilleur = P[j + 1] - min_prefixe;
    }

    sufmax[nb_jours - 1] = P[nb_jours];
    for (int i = nb_jours - 2; i >= 0; i--)
        sufmax[i] = P[i + 1] > sufmax[i + 1] ? P[i + 1] : sufmax[i + 1];

    int i = 0;
    while (sufmax[i] - P[i] != meilleur) i++;
    int j = i;
    while (P[j + 1] - P[i] != meilleur) j++;

    *debut = i;
    *fin = j;
    return meilleur;
}

/* F6 : retrouve une transaction à partir de son id en O(1) */
const Transaction *rechercher_par_id(const Transaction *t, const int *index, int n, int id)
{
    if (id < 0 || id >= n)
        return NULL;
    return &t[index[id]];
}

/* Comparaison de montants pour qsort */
static int comparer_montants(const void *a, const void *b)
{
    long x = *(const long *)a;
    long y = *(const long *)b;
    if (x < y) return -1;
    if (x > y) return 1;
    return 0;
}

/* F7 optimisée : compte les paires de montants opposés (a + b = 0) */
long nb_paires_opposees(const Transaction *t, int n)
{
    if (n < 2)
        return 0;

    long *montants = malloc(n * sizeof(long));
    if (montants == NULL) {
        /* En cas d'échec d'allocation, conserve un résultat correct. */
        long nb = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (t[i].montant + t[j].montant == 0)
                    nb++;
        return nb;
    }

    for (int i = 0; i < n; i++)
        montants[i] = t[i].montant;

    qsort(montants, n, sizeof(long), comparer_montants);

    long nb = 0;
    int gauche = 0;
    int droite = n - 1;

    while (gauche < droite) {
        long somme = montants[gauche] + montants[droite];

        if (somme < 0) {
            gauche++;
        } else if (somme > 0) {
            droite--;
        } else if (montants[gauche] == montants[droite]) {
            long nombre = droite - gauche + 1;
            nb += nombre * (nombre - 1) / 2;
            break;
        } else {
            long valeur_gauche = montants[gauche];
            long valeur_droite = montants[droite];
            long compte_gauche = 0;
            long compte_droite = 0;

            while (gauche <= droite && montants[gauche] == valeur_gauche) {
                compte_gauche++;
                gauche++;
            }
            while (droite >= gauche && montants[droite] == valeur_droite) {
                compte_droite++;
                droite--;
            }
            nb += compte_gauche * compte_droite;
        }
    }

    free(montants);
    return nb;
}

/* F8 : nombre de façons de rendre une somme avec les pièces disponibles */
/* F8 : nombre de façons de rendre une somme avec les pièces disponibles */
static const int PIECES[] = {1, 2, 5, 10, 20, 50, 100, 200};
#define NB_PIECES 8

long nb_facons_rendre(int somme, int nb_pieces)
{
    long dp[MONTANT_MONNAIE + 1] = {0};
    dp[0] = 1;

    for (int i = 0; i < nb_pieces; i++) {
        for (int s = PIECES[i]; s <= somme; s++) {
            dp[s] += dp[s - PIECES[i]];
        }
    }

    return dp[somme];
}

/* F9 : catégorie des transactions négatives */
static int categorie_negative(const Transaction *t)
{
    if (t->montant < -20000) {
        if (t->jour % 7 >= 5)
            return 1;
        return 2;
    }

    if (t->montant < -5000)
        return 3;

    if (t->client % 10 == 0)
        return 4;

    return 5;
}

/* F9 : catégorie des transactions positives */
static int categorie_positive(const Transaction *t)
{
    if (t->montant > 30000) {
        if (t->client % 10 == 0 && t->jour % 7 < 5)
            return 6;
        return 7;
    }

    if (t->montant > 10000)
        return 8;

    if (t->montant > 1000) {
        if (t->jour % 30 == 0)
            return 9;
        return 10;
    }

    return 11;
}

/* F9 : catégorie d'une transaction */
int categorie(const Transaction *t)
{
    if (t->montant < 0)
        return categorie_negative(t);

    if (t->montant == 0)
        return 0;

    return categorie_positive(t);
}

/* F10 : ajoute une ligne à la fin du rapport en conservant sa position */
void ajouter_ligne(char *rapport, int *fin, const char *ligne)
{
    int i = 0;

    while (ligne[i] != '\0') {
        rapport[*fin + i] = ligne[i];
        i++;
    }

    *fin += i;
    rapport[*fin] = '\0';
}

/* ------------------------------------------------------------------ */
/* Programme principal (à adapter si vous changez les signatures)     */
/* ------------------------------------------------------------------ */

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

int main(void)
{
    Transaction *t = generer_transactions(NB_TRANSACTIONS);
    int *index = malloc(NB_TRANSACTIONS * sizeof(int));
    char *rapport = malloc(1 << 20);
    char ligne[128];
    int fin_rapport = 0;

    if (t == NULL || index == NULL || rapport == NULL) {
        fprintf(stderr, "Erreur d'allocation mémoire.\n");
        free(t);
        free(index);
        free(rapport);
        return 1;
    }

    for (int i = 0; i < NB_TRANSACTIONS; i++)
        index[t[i].id] = i;

    rapport[0] = '\0';

    /* recherches par id, dans l'ordre d'origine */
    long somme_requetes = 0;
    unsigned long etat = 12345;
    for (int q = 0; q < NB_REQUETES; q++) {
        etat = etat * 1103515245UL + 12345UL;
        const Transaction *r = rechercher_par_id(t, index, NB_TRANSACTIONS,
                                                   (int)((etat >> 8) % NB_TRANSACTIONS));
        if (r != NULL)
            somme_requetes += r->montant;
    }

    int nb_clients = nb_clients_distincts(t, NB_TRANSACTIONS);

    static long totaux_clients[NB_CLIENTS];
    total_par_client(t, NB_TRANSACTIONS, totaux_clients);

    static long totaux_jours[NB_JOURS];
    total_par_jour(t, NB_TRANSACTIONS, totaux_jours);
    int debut, fin;
    long meilleure = meilleure_periode(totaux_jours, NB_JOURS, &debut, &fin);

    long nb_paires = nb_paires_opposees(t, NB_TRANSACTIONS);

    int categories[12] = {0};
    for (int i = 0; i < NB_TRANSACTIONS; i++)
        categories[categorie(&t[i])]++;

    trier_par_montant(t, NB_TRANSACTIONS);

    long nb_facons = nb_facons_rendre(MONTANT_MONNAIE, NB_PIECES);

    /* rapport */
    snprintf(ligne, sizeof(ligne), "clients distincts;%d\n", nb_clients);
    ajouter_ligne(rapport, &fin_rapport, ligne);
    snprintf(ligne, sizeof(ligne), "somme des requetes;%ld\n", somme_requetes);
    ajouter_ligne(rapport, &fin_rapport, ligne);
    snprintf(ligne, sizeof(ligne), "meilleure periode;%d;%d;%ld\n", debut, fin, meilleure);
    ajouter_ligne(rapport, &fin_rapport, ligne);
    snprintf(ligne, sizeof(ligne), "paires opposees;%ld\n", nb_paires);
    ajouter_ligne(rapport, &fin_rapport, ligne);
    snprintf(ligne, sizeof(ligne), "facons de rendre %d;%ld\n", MONTANT_MONNAIE, nb_facons);
    ajouter_ligne(rapport, &fin_rapport, ligne);
    for (int c = 0; c < 12; c++) {
        snprintf(ligne, sizeof(ligne), "categorie;%d;%d\n", c, categories[c]);
        ajouter_ligne(rapport, &fin_rapport, ligne);
    }
    for (int c = 0; c < NB_CLIENTS; c++) {
        snprintf(ligne, sizeof(ligne), "client;%d;%ld\n", c, totaux_clients[c]);
        ajouter_ligne(rapport, &fin_rapport, ligne);
    }
    for (int j = 0; j < NB_JOURS; j++) {
        snprintf(ligne, sizeof(ligne), "jour;%d;%ld\n", j, totaux_jours[j]);
        ajouter_ligne(rapport, &fin_rapport, ligne);
    }
    for (int i = 0; i < NB_TRANSACTIONS; i += 10) {
        snprintf(ligne, sizeof(ligne), "rang;%d;%d;%ld\n", i, t[i].id, t[i].montant);
        ajouter_ligne(rapport, &fin_rapport, ligne);
    }

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

    printf("Clients distincts   : %d\n", nb_clients);
    printf("Somme des requêtes  : %ld\n", somme_requetes);
    printf("Meilleure période   : jours %d à %d (%ld)\n", debut, fin, meilleure);
    printf("Paires opposées     : %ld\n", nb_paires);
    printf("Façons de rendre %d : %ld\n", MONTANT_MONNAIE, nb_facons);
    printf("Empreinte           : %016lx\n", empreinte(rapport));

    free(rapport);
    free(index);
    free(t);
    return 0;
}