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

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//  DEFINITIONS
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

// En cas d'erreur sur les arguments
#define ERREUR_NBARGS 1
#define ERREUR_ARGS 2
#define ERREUR_MOTS 3
#define ERREUR_TESTS 4

// Le plus grand entier positif sur nbbits
#define MAXINT(nb) ((1ULL) << (nb))

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//  TYPES
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

// Raccourcis pour les types entiers
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ullong;

// Structure de chaîne de caractères
typedef char *tmot;

// Structure de cellule pour liste chaînée.
// 2 champs: 1 chaîne et 1 pointeur > cellule suivante.
typedef struct tcell{
  tmot mot;
  struct tcell *suiv;
} tcell;

// Structure de liste chaînée
typedef tcell *tliste; 

// Structure d'alvéole
// 2 champs: liste des collisions + longueur de la liste
typedef struct talveole{
  tliste LC;
  uint longueur;
} talveole;

// Structure de table de hachage
typedef talveole *ttabhach;

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//  VARIABLES GLOBALES 
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

// Le nombre de bits pour les hachés
uchar nbbits = 0;

// La taille de la table de hachage
ullong lenTH = 0;

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//  FONCTIONS 
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

///////////////////////////////////////////////////////////////
// Empile le <mot> au sommet de la <liste> et renvoie s'il y a
// eu collision ou non. 
///////////////////////////////////////////////////////////////
int Empiler(tmot mot, tliste *liste){
  tliste tete = malloc(sizeof(tcell)); 
  tete->mot = mot;
  tete->suiv = *liste;
  *liste = tete;
  return ((*liste)->suiv) == NULL;
}

///////////////////////////////////////////////////////////////
// Renvoie la chaine de caractères au sommet de la <liste>
// en l'étêtant et en libérant la mémoire.
///////////////////////////////////////////////////////////////
tmot Depiler(tliste *liste){
  tliste alib = *liste;
  tmot mot = NULL;
  
  if ((*liste) != NULL){
    mot = (*liste)->mot;
    (*liste) = (*liste)->suiv;
    free(alib);
  }  
  return mot;  
}

///////////////////////////////////////////////////////////////
// Affiche les mots dans la <liste>.
///////////////////////////////////////////////////////////////
void AfficherListe(tliste liste){
  printf("[ ");
  while (liste != NULL){
    printf("%s ", liste->mot);
    liste = liste->suiv;
  }
  printf("]");
}

///////////////////////////////////////////////////////////////
// Affiche les collisions dans la table des hachés <TH>.
///////////////////////////////////////////////////////////////
void AfficherTable(ttabhach TH){
  for (uint i = 0; i < lenTH; i++){
      printf("\nH = %4u (%3u) > ", i, TH[i].longueur);
      AfficherListe((TH[i]).LC);
  }
}

///////////////////////////////////////////////////////////////
// Renvoie un entier choisi "aléatoirement" dans 
// l'intervalle [<start>, <stop>] (stop <= RAND_MAX).
// On élimine les tirages qui présentent un biais.
///////////////////////////////////////////////////////////////
uint randint(uint start, uint stop){
  uint nb = stop - start + 1;
  uint limit = RAND_MAX - (RAND_MAX % nb);
  uint alea = rand();
  while (alea  >= limit)
    alea = rand();
  return start + (alea % nb);
}

///////////////////////////////////////////////////////////////
// À COMPLÉTER - À COMPLÉTER - À COMPLÉTER - À COMPLÉTER 
// Renvoie la longueur du <mot> (chaine qui finit par '\0')
///////////////////////////////////////////////////////////////
uint len(tmot mot){



}

///////////////////////////////////////////////////////////////
// Libère la mémoire allouée pour <*liste>. 
///////////////////////////////////////////////////////////////
void LibererListe(tliste *liste){
  tliste tete = NULL;
  
  while (*liste != NULL){
    tete = *liste;
    free(tete->mot);
    *liste = (*liste)->suiv;
    free(tete);
  }
  *liste = NULL;
}

///////////////////////////////////////////////////////////////
// Renvoie le haché du <mot> (sur <nbbits>) par la fonction
// Fowler–Noll–Vo-1a, i.e un entier dans [0, 2^<nbbits> - 1]
///////////////////////////////////////////////////////////////
ullong Hacher(tmot mot){
  ullong aux = 14695981039346656037ULL;
  uint n = len(mot);
  ullong mask = lenTH - 1ULL;
  ullong hash = 0;
  
  for (uint i = 0; i < n; i++){
    aux ^= mot[i];
    aux *= 1099511628211ULL;      
  }
  while (aux) {
    hash ^= (aux & mask);
    aux >>= nbbits;
  }
  
  return hash;
}

///////////////////////////////////////////////////////////////
// À COMPLÉTER - À COMPLÉTER - À COMPLÉTER - À COMPLÉTER
// Renvoie un mot sur l'alphabet {A,B,...,Z} de longueur dans
// [<lmin>, <lmax>] construit aléatoirement. 
///////////////////////////////////////////////////////////////
tmot GenMot(uchar lmin, uchar lmax){


}

///////////////////////////////////////////////////////////////
// À COMPLÉTER - À COMPLÉTER - À COMPLÉTER - À COMPLÉTER
// Alloue et renvoie une table de <nbalv> alvéoles dont les
// listes sont initialisées à NULL et les longueurs à 0.
///////////////////////////////////////////////////////////////
ttabhach AllouerTable(ullong nbalv){


}

///////////////////////////////////////////////////////////////
// Libère la mémoire allouée pour les listes de <TH> mais pas
// <TH> (évite une réallocation de <TH> à chaque expérience).
// Utile dans la fonction MesurerUniformite().
///////////////////////////////////////////////////////////////
void LibererHaches(ttabhach TH){  
  for (uint i = 0; i < lenTH; i++){
    (TH[i]).longueur = 0;
    LibererListe(&((TH[i]).LC));
  }
}

///////////////////////////////////////////////////////////////
// À COMPLÉTER - À COMPLÉTER - À COMPLÉTER - À COMPLÉTER
// Renvoie la liste des mots dans l'ordre croissant des valeurs
// des hachés. Le principe de construction de la liste est
// identique au tri par répartition quand on vide les casiers.
// Indication: utilisez les fonctions Depiler et Empiler.
// NB. Question indépendante du  sujet général.
///////////////////////////////////////////////////////////////
tliste Trier(ttabhach TH){


}

///////////////////////////////////////////////////////////////
// Renvoie le coefficient de variation du nombre de mots de
// même haché de la table <TH> où <mu> est la moyenne.
///////////////////////////////////////////////////////////////
float Variation(ttabhach TH, float mu, uint nbmots){
  float sum = 0.0;
  
  for (uint i = 0; i < lenTH; i++)
      sum += (float) ((TH[i]).longueur - mu) * ((TH[i]).longueur - mu);
  return sqrt((float) sum / (nbmots * mu));
}


///////////////////////////////////////////////////////////////
// À COMPLÉTER - À COMPLÉTER - À COMPLÉTER - À COMPLÉTER
// 1. Alloue une table de hachage TH, y range <nbmots> générés
// aléatoirement et l'affiche. Les longueurs des mots seront
// tirées au hasard entre 8 et 32.
// 2. Affiche le coefficient de variation
// 3. Libère toute la mémoire, i.e. les listes de TH puis TH.
///////////////////////////////////////////////////////////////
void MesurerUniformite(uint nbmots){







}

///////////////////////////////////////////////////////////////
// À COMPLÉTER - À COMPLÉTER - À COMPLÉTER - À COMPLÉTER
// Ajoute des mots générés aléatoirement dans la table <TH>
// des hachés (de 2^<nbbits>) jusqu'à ce qu'il y ait une
// collision. Renvoie le nombre de mots nécessaires.
// Les longueurs des mots sont tirées au hasard entre 8 et 32
///////////////////////////////////////////////////////////////
uint ChercherCollision(ttabhach TH){



}


///////////////////////////////////////////////////////////////
// À COMPLÉTER - À COMPLÉTER - À COMPLÉTER - À COMPLÉTER
// Repète <nbexp> fois la recherche d'une première collision
// en repartant d'une table vierge à chaque fois et renvoie la
// moyenne du nombre de tirages aléatoires qui ont été
// nécessaires pour obtenir une première collision.
///////////////////////////////////////////////////////////////
void EstimerNbTirages(uint nbexp){


}

///////////////////////////////////////////////////////////////
// FONCTION MAIN
// Traite trois arguments:
//    1. Le nombre de bits b pour un haché, qui fixe la taille
//       2^b de la table de hachage.
//    2. Le nombre de mots à hacher et à répartir dans la table
//       pour vérifier la distribution des hachés et répondre à
//       la question (1).
//    3. Le nombre de fois où il faudra répéter l'expérience
//       consistant à calculer le nombre de tirages de mots
//       aléatoires nécessaires pour obtenir une première collision
//       dans la table afin d'en calculer la moyenne et répondre
//       à la question (2). 
///////////////////////////////////////////////////////////////
int main(int argc, char* argv[]){
  uint nbmots = 0;
  uint nbexp = 0;

  // Création d'un germe pour le générateur aléatoire
  srand((uint) time(NULL));
  
  // VALIDATION DES PARAMÈTRES DE LA LIGNE DE COMMANDE
  // VERIFICATION NOMBRE DE PARAMÈTRES
  if (argc < 4){    
    printf("Syntaxe: %s nbbits nbmots nbexp\n",argv[0]);
    return ERREUR_NBARGS;
  }

  // TENTATIVE DE CONVERSION DU NOMBRE DE BITS DES HACHÉS  
  if ((sscanf(argv[1], "%hhu", &nbbits) == 0) ||
      (nbbits > 32)){
    printf("Pb sur #bits du haché\n");
    return ERREUR_ARGS;
  }

  // TENTATIVE DE CONVERSION DU NB DE MOTS A HACHER 
  if ((sscanf(argv[2], "%u", &nbmots) == 0) ||
      (nbmots > (1ULL << 24))){
    printf("Pb sur #mots\n");
    return ERREUR_MOTS;
  }

    // TENTATIVE DE CONVERSION DU NOMBRE DE TESTS
  if ((sscanf(argv[3], "%u", &nbexp) == 0) ||
      (nbexp > 65536)){
    printf("Pb sur #tests\n");
    return ERREUR_TESTS;
  }

  // INITIALISATION DE LA TAILLE DE LA TABLE DE HACHAGE
  lenTH = MAXINT(nbbits);

  // TEST D'UNIFORMITE DE LA DISTRIBUTION DES HACHES
  MesurerUniformite(nbmots);  
  
  // PARADOXE DES ANNIVERSAIRES
  EstimerNbTirages(nbexp);

  return 0;
}