//KISS
#include <errno.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <stdint.h>
#include <limits.h>

#define NBCAR_ASCII_MAX 256
#define OPTIONS_ARG "hVsf:vqla"
#define NBOPTIONSARG 8 //Toujours +1 (pour l'erreur) et -1 (pour verbose)
#define DEV_NULL "/dev/null"
#define W_SPACE 1
#define W_NOEUD 2

//maximum entre deux nombre
inline unsigned int max (unsigned int a, unsigned int b) { return a>b?a:b; }

//Pour les connaitre les options actives passés en argument
enum FLAG
  {
    FLAG_ERR,
    FLAG_STRING,
    FLAG_HELP,
    FLAG_VERSION,
    FLAG_STDIN,
    FLAG_FILE,
    FLAG_VERBOSE,
    FLAG_LISTE,
    FLAG_ARBRE
  };

//Pour toutes les erreurs qu'il peut y avoir au cours de l'execution
enum ERROR
  {
    EXIT_NO     = 0,
    EXIT_MEM    = 1, //erreur de mémoire
    EXIT_HELP   = 2,
    EXIT_VERSION= 3,
    EXIT_OPT    = 4, //option incorrect ou incomplète
    EXIT_TYPE   = 5  //le type choisis n'est pas assez important
  };

//Pour le tableau des occurences
enum OCC
  {
    OCC_ID   = 0,
    OCC_VAL  = 1
  };

//Type de l'arbre utilisé
typedef struct TNoeud
{
  uint16_t           lettre;
  unsigned int       occ;
  struct TNoeud     *g; //g pour fils gauche
  struct TNoeud     *d; //d pour fils droit
} TNoeud;

typedef struct Liste_TNoeud
{
  struct TNoeud       *noeud;
  struct Liste_TNoeud *suivant;
} Liste_TNoeud;

//fonction qui fait l'addition entre noeud, pour retourner la somme des deux (le nouveau noeud, racine des noeuds passés en paramètre)
//normalement les deux espaces mémoires ne sont pas les mêmes et ne doivent en aucun cas se chevaucher (restrict)
TNoeud *somme_TNoeud (TNoeud *a, TNoeud *b)
{
  TNoeud *s = NULL;
  
  s = (TNoeud *)malloc(sizeof(TNoeud));
  if (s == NULL || a == NULL || b == NULL) return NULL;
  
  s->lettre = (uint16_t)0; //0 équivaut à une racine, sinon c'est une feuille (= une lettre)
  s->occ = a->occ + b->occ;
  s->g = a;
  s->d = b;

  return s;
}

//fonction qui réordonne le premier élément de la liste par rapport aux autres éléments. Retourne le premier élément de la liste.
Liste_TNoeud *ordre_LTNoeud (Liste_TNoeud *l)
{
  Liste_TNoeud *L_TNdep = l, *L_TNdep_suiv = NULL, //premier élément de la liste - à retourner (pour le momement = l)
    *L_TNmp = NULL, //pointeur temporaire
    *L_TNi = NULL; //pointeur temporaire

  int i=0;

  if (l == NULL) return NULL;
  L_TNdep_suiv = l->suivant;
  L_TNi = l->suivant;

  while (L_TNi != NULL && i > 0)
    {
      switch (i=(compare_TNoeud(l->noeud, L_TNi->noeud)))
	{
	case 1: //plus grand
	  L_TNmp = L_TNi;
	  L_TNi = L_TNi->suivant;
	  break;
	case -1: //plus petit

	  break;
	default: //pas normal
	  fprintf(stderr, "Attention, ça va péter!!!! ...\nBon finalement, revoir le code ça ira mieux.\n");
	  return NULL;
	}
    }
  if (L_TNmp == NULL) //l est bien le premier élément
    return L_TNdep;

  L_TNmp->suivant = l;
  l->suivant = L_TNi;

  return L_TNdep_suiv;
}

unsigned int hauteur_TNoeud (TNoeud *a)
{
  if (a == NULL) return 0;
  return (max(hauteur_TNoeud(a->g), hauteur_TNoeud(a->d)) + 1);
}

//fonction qui compare deux noeud et indique quel est le plus grand (1 a plus grand, -1 b plus grand)
//normalement les deux espaces mémoires ne sont pas les mêmes et ne doivent en aucun cas se chevaucher (restrict)
int compare_TNoeud (TNoeud *a, TNoeud *b)
{
  uint16_t diff;
  if (a == NULL || b == NULL) return 0; //ce n'est normalement pas possible que 2 noeuds soit équivalent (à moins que le même paramètre est transmis).

  diff = (a->occ > b->occ) - (a->occ < b->occ);
  if (!diff) //égaux
    diff = (a->lettre > b->lettre) - (a->lettre < b->lettre);

  return diff;
}
 
//fonction qui libère la mémoire d'un arbre binaire de type TNoeud
void free_TNoeud (TNoeud *speech)
{
  if (speech != NULL)
    {
      free_TNoeud(speech->g);
      free_TNoeud(speech->d);
      free(speech);
      speech = NULL;
    }
}

//fonction qui libère la mémoire de la liste, de type Liste_TNoeud
void free_ListeTNoeud (Liste_TNoeud *beer)
{
  if (beer != NULL)
    {
      if (beer->suivant != NULL) free_ListeTNoeud(beer->suivant);
      free(beer);
      beer = NULL;
    }
}

//fonction qui s'occupe de comparer deux valeurs pour connaitre la plus grande (utiliser pour mettre dans l'ordre le tableau d'occurences)
//il faut prendre en compte que les valeurs donnés représente à chaque fois une ligne de deux colonnes
int __compare_int2 (const void *a, const void *b)
{
  const int *da = (const int *)a;
  const int *db = (const int *)b;
  //on regarde d'abbord la deuxième valeur (= le nombre d'occurences)
  int diff1 = (*(da+1) > *(db+1)) - (*(da+1) < *(db+1));
  if (diff1) return diff1;
  return (*da > *db) - (*da < *db);
}

//afficher le texte d'aide quand on se trompe de paramètres
int help()
{
  fprintf(stderr, "Usage : huffman [OPTIONS...] [string]\n  -h : help.\n  -V : version.\n  -s : lire l'entrée sur 'stdin'.\n  -f : lire le fichier donné en paramètre.\n  -v : mode verbose.\n  -q : mode quiet (par défaut). \n  -l : dessiner la liste (si l'option verbose n'est pas active).\n  -a : dessiner l'arbre (si l'option verbose n'est pas active).\n");
  return EXIT_HELP;
}

//OBSELETE
/*
//compte le nombre d'occurence d'une chaine
size_t occ (const char *s, int c)
{
  //on aurait pu choisir la fonction memchr, mais on considère être avec toujours des chaines de caractères faisant 8bits (ASCII 7bits) - c'est plus simple
  char * res;
  return ((size_t)((res=strchr(s, c))? 1+occ((const char *)(res+1), c) : 0));
}
*/

int main (int argc, char *argv[])
{
  int ARGFLAG[NBOPTIONSARG], //0:par défaut chaine,1:h,2:v,3:s,4:f
    i, //compteur réutilisé régulièrement dans le programme. bien l'initialiser à chaque fois.
    nbc, //nb caractère concerné (utilisé pour le tableau de TNoeud).
    eksit = EXIT_SUCCESS; //variable contient la valeur de retour du programme

  //Pour le tableau d'occurence, il aurait été plus jolie de prendre un type de 16bits (char ou int16), mais étant donné que l'on compte le nombre d'occurence, le type aurait pu ne pas suffire.
  unsigned int OCCURENCE[NBCAR_ASCII_MAX][2];

  char *chaine = NULL; //la chaine de caractère concerné - si l'option choisis

  FILE *stream = NULL, //le flux de donné qui sera lu, qu'importe l'option choisis.
    *stdverb = NULL; //le flux de donné où on écrira le texte d'information selon le mode verbose

  TNoeud *root = NULL, //La racine de l'arbre
    *TNmp = NULL, //pointeur temporaire réutilisé pour garder en mémoire l'adresse à traiter
    *TNmp_next = NULL; //pointeur temporaire

  Liste_TNoeud *liste = NULL, //Le tableau des noeuds après récupérations de toutes les occurences de chaque bytes.
    *L_TNmp = NULL, *L_TNmp_prev = NULL; //pointeur temporaire

  /*
    //Initialisations des variables
  */
  ARGFLAG[FLAG_ERR]=0;
  ARGFLAG[FLAG_STRING]=1;
  ARGFLAG[FLAG_HELP]=0;
  ARGFLAG[FLAG_VERSION]=0;
  ARGFLAG[FLAG_STDIN]=0;
  ARGFLAG[FLAG_FILE]=0;
  ARGFLAG[FLAG_VERBOSE]=0; //quiet par défaut
  ARGFLAG[FLAG_LISTE]=0;
  ARGFLAG[FLAG_ARBRE]=0;

  for (i=0; i<NBCAR_ASCII_MAX; OCCURENCE[i][OCC_ID]=(unsigned int)i, OCCURENCE[i++][OCC_VAL]=0);

  errno=0;
  /*
    //FIN INITIALISATION
  */


  /*
    == DÉBUT PROGRAMME ==
  */

  //récupérer les arguments et les arguments passés à l'appel du programme
  i = 0;
  opterr = 0;
  while ((i = getopt (argc, argv, OPTIONS_ARG)) != -1)
  {
    switch (i)
      {  
      case 'V':
	ARGFLAG[FLAG_VERSION]=1;
       	fprintf(stdout, "Pourquoi tu veux connaitre la version du programme?\n");
	eksit = EXIT_VERSION;
	break;
      case 's':
	//stdin : ce qui est à convertir sera en entrée
	ARGFLAG[FLAG_STRING]=0;
	ARGFLAG[FLAG_STDIN]=1;
	break;
      case 'f':
	//file : on lit le fichier
	ARGFLAG[FLAG_STRING]=0;
	ARGFLAG[FLAG_FILE]=1;
	chaine=(char *)malloc(sizeof(char)*(1+strlen(optarg)));
	if (chaine == NULL)
	  {
	    perror("malloc");
	    eksit = EXIT_MEM;
	    goto clean;
	  }
	strcpy(chaine, optarg);
	break;
      case 'v':
	ARGFLAG[FLAG_VERBOSE]=1;
	break;
      case 'q':
	ARGFLAG[FLAG_VERBOSE]=0;
	break;
      case 'l':
	ARGFLAG[FLAG_LISTE]=1;
	break;
      case 'a':
	ARGFLAG[FLAG_ARBRE]=1;
	break;
      case '?':
	if (optopt == 'f')
	  fprintf (stderr, "L'option -%c a besoin d'un argument.\n", optopt);
	else if (isprint (optopt))
	  fprintf (stderr, "Option '-%c' inconnu.\n", optopt);
	else
	  fprintf (stderr, "Caractère '\\x%x' inconnu.\n", optopt);
	eksit = EXIT_OPT;
	ARGFLAG[FLAG_ERR]=1;
	break;
      default:
	eksit = help();
	ARGFLAG[FLAG_ERR]=1;
      }

    if (ARGFLAG[FLAG_VERSION] || ARGFLAG[FLAG_ERR]) goto clean;
  }



  //selon le mode verbose ou quiet, on choisit un fichier de sortie différent
  //verbose : stdout
  //quiet : /dev/null
  if (ARGFLAG[FLAG_VERBOSE]) stdverb = stdout;
  else
    {
      stdverb = fopen(DEV_NULL,"w");
      if (stdverb == NULL)
	{
	  perror("fopen");
	  eksit = EXIT_MEM;
	  goto clean;
	}
    }

  if (argc > optind)
    {
      //s'il y a un argument qui ne correspond pas aux options, c'est le texte pour le mode par défaut
      ARGFLAG[FLAG_STRING]=1;
      chaine=(char *)malloc(sizeof(char)*(1+strlen(argv[optind])));
      if (chaine == NULL)
	{
	  perror("malloc");
	  eksit = EXIT_MEM;
	  goto clean;
	}
      strcpy(chaine, argv[optind]);
      fprintf(stdverb,". Récupère la chaine à traiter donné en argument...\n");
    }

  //il ne peut y avoir que SOIT lecture de la chaine ou SOIT lecture fichier stdin ou SOIT lecture fichier %f
  if (!(ARGFLAG[FLAG_STRING] ^ ARGFLAG[FLAG_STDIN] ^ ARGFLAG[FLAG_FILE]))
    {
      eksit = help();
      goto clean;
    }

  if (ARGFLAG[FLAG_STRING] && chaine == NULL)
    {
      fprintf(stderr, "Il faut une chaine de caractère à traiter.\n");
      eksit = help();
      goto clean;
    }
  
  //printf ("%zu\n", occ((char *)chaine, (int)'a'));  
  //while ((i=fgetc(stdin))!=EOF) { fprintf(stdout, "%c\n", (char)i); }

  //Pour chaque option, on initialise 'stream', le flux de donnée qui sera lu
  //printf("%d\n",argflag[FLAG_STRING]+(argflag[FLAG_STDIN]<<1)+(argflag[FLAG_FILE]<<2));
  switch (ARGFLAG[FLAG_STRING] + (ARGFLAG[FLAG_STDIN]<<1) + (ARGFLAG[FLAG_FILE]<<2))
    {
    case 0x1 :
      fprintf(stdverb, ". Lecture chaine...\n");
      stream = fmemopen(chaine, strlen(chaine), "r");
      break;
    case 0x2 :
      fprintf(stdverb, ". Lecture entrée stdin...\n");
      stream = stdin;
      break;
    case 0x4 :
      fprintf(stdverb, ". Lecture fichier...\n");
      stream = fopen(chaine, "r");
      break;
    default :
      fprintf(stderr, "Panique à bord!\n");
    }

  if (stream == NULL)
    {
      perror("f*open");
      eksit = EXIT_MEM;
      goto clean;
    }

  //on commence à compter les occurences
  //on considère que ce qui est lu est toujours en ASCII -> plus facile : donc 1 octet = 1 caractère
  //et bien parce que je considère que chaque caractère vaut 1 octet, je peux utiliser un tableau fixe de 256 cases
  //ça sera plus simple, et évite les problèmes, et permet de récupérer plus rapidement la valeur de l'occurence d'un caractère
  fprintf(stdverb, ". Calcul du nombre d'occurences pour chaques caractères...\n");
  while ((i=fgetc(stream))!=EOF)
    {
      //s'il y a dépassement du type unsigned int, on arrête là - le résultat sera faux par la suite
      if (OCCURENCE[i][OCC_VAL] == UINT_MAX)
	{
	  fprintf(stderr, "Dépassement du type UINT %zu\n", UINT_MAX);
	  fprintf(stderr, "Le programme n'a pas été conçu pour gérer ce genre de cas. Passes sur du long int, s'il le faut, on le fera pas à ta place.\n");
	  eksit = EXIT_TYPE;
	  goto clean;
	}
      OCCURENCE[i][OCC_VAL]++;
    }

  //printf("%zu\n", OCCURENCE[(int)'a'][VAL]);

  /*
    =================
    à noté:
     - suivis la méthode sur htpp://tcharles.developpez.com/Huffman
    =================
  */

  //On ordonne le tableau d'occurence
  fprintf(stdverb, ". Trie du tableau contenant les occurences...\n");
  qsort(OCCURENCE, (size_t)NBCAR_ASCII_MAX, 2*(size_t)sizeof(int), __compare_int2);

  //for (i=0; i<NBCAR_ASCII_MAX; printf("%zu:%zu\n", OCCURENCE[i][OCC_ID], OCCURENCE[i][OCC_VAL]), i++);

  /*
    ICI LE TABLEAU EST TRIÉ PAR ORDRE __CROISSANT__.
    Donc il faut prendre le tableau par la dernière case pour avoir le plus grand.
   */

  //on remplit la liste de noeuds (déjà trié)
  fprintf(stdverb, ". Ajoute et crée chaque noeuds dans la liste...\n");
  for (nbc=0, liste=NULL, L_TNmp=NULL, L_TNmp_prev=NULL, TNmp=NULL, i=0; i<NBCAR_ASCII_MAX; i++)
    {
      //Toutes les occurences valant 0 ne nous intéresse pas
      if (OCCURENCE[i][OCC_VAL])
	{
	  ++nbc; //nb de caractère concerné

	  //on alloue une nouvelle case dans la liste tab 
	  L_TNmp = (Liste_TNoeud *)malloc(sizeof(Liste_TNoeud));
	  if (L_TNmp == NULL)
	    {
	      perror("malloc");
	      eksit = EXIT_MEM;
	      goto clean;
	    }
	  //si liste est NULL ça veut dire que la première case de la liste a été alloué (on aurait pu le vérifier à partir de la variable nbc)
	  if (liste == NULL) liste = L_TNmp;

	  //on alloue le noeud qui sera placé dans la nouvelle case
	  TNmp = (TNoeud *)malloc(sizeof(TNoeud));
	  if (TNmp == NULL)
	    {
	      perror("malloc");
	      eksit = EXIT_MEM;
	      goto clean;
	    }
	  TNmp->lettre = (uint16_t)OCCURENCE[i][OCC_ID];
	  TNmp->occ = (unsigned int)OCCURENCE[i][OCC_VAL];
	  TNmp->g = NULL;
	  TNmp->d = NULL;

	  //on ajoute le noeud dans la liste
	  L_TNmp->noeud = TNmp;
	  L_TNmp->suivant = NULL;

	  //on s'occupe du pointeur de la case de liste précédente
	  if (L_TNmp_prev != NULL) { L_TNmp_prev->suivant = L_TNmp; }

	  //le precedent devient l'actuel (pour seulement une instruction :( snif... )
	  L_TNmp_prev = L_TNmp;
	}
    }

  L_TNmp = NULL;
  L_TNmp_prev = NULL;
  TNmp = NULL;

  //ICI on a un tableau de noeud déjà trié.
  //on affiche la liste de noeud
  if (ARGFLAG[FLAG_VERBOSE] || ARGFLAG[FLAG_LISTE])
    {
      fprintf(stdverb,". Affiche la liste :\n");

      for (L_TNmp = liste; L_TNmp != NULL; TNmp = L_TNmp->noeud, fprintf(stdout, "   %c (0x%02X) : %d\n", TNmp->lettre, TNmp->lettre, TNmp->occ), L_TNmp = L_TNmp->suivant);
    }

  //La liste doit avoir comme 2 premiers éléments toujours ceux avec l'occurence la plus petite
  while (L_TNmp=NULL, TNmp=NULL, TNmp_next=NULL, liste->suivant != NULL)
    {
      TNmp = liste->noeud; //Le fils gauche,
      TNmp_next = (liste->suivant)->noeud; //la fille droite,
      TNmp = somme_TNoeud(TNmp, TNmp_next); //et le père courbe
      if (TNmp == NULL)
	{
	  perror("somme_TNoeud");
	  eksit = EXIT_MEM;
	  goto clean;
	}
      
      //on libère la mémoire du premier élément, et on réutilise le deuxième pour le père
      L_TNmp = liste;
      liste = liste->suivant;
      liste->noeud = TNmp; //dans la maison
      //on ne change pas le suivant,
      //on libère le premier.
      free(L_TNmp); //ouvrent la fenêtre

      //il faut placer le premier élément de la liste (liste) correctement dans l'ordre par rapport aux autres éléments
      liste = ordre_LTNoeud(liste); //sans oublier la porte.
      if (liste == NULL)
	{
	  perror("ordre_LTNoeud");
	  eksit = EXIT_MEM;
	  goto clean;
	}
    }

  //c'est bon, la liste n'a comme noeud enregistré un seul élément : la racine de tous les autres noeud = la racine de l'arbre.
  root = liste->noeud;

  if (ARGFLAG[FLAG_VERBOSE] || ARGFLAG[FLAG_ARBRE])
    {
      fprintf(stdverb, ". Dessin de l'arbre huffman:\n");
      
    }

  /*
    LIBERATION MÉMOIRE
    //on oublie pas de libérer la mémoire alloué.
    //ici pas de ramasses miettes, pas de prison.
   */

 clean:
  free_TNoeud(root); root = NULL;
  free_ListeTNoeud(liste); liste = NULL;
  TNmp = NULL; L_TNmp = NULL; L_TNmp_prev = NULL;

  if (stream) fclose(stream); stream = NULL;
  if (stdverb) fclose(stdverb); stdverb = NULL;

  free(chaine); chaine = NULL;

  /*
   TOUT le monde est libre !
   */

  /*
    ==== FIN DU PROGRAMME ====
    c'est gentil d'être passé
    à la prochaine :)
  */

  exit(eksit);
}

//KILL COPYRIGHT