import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class huffman
{
    private static final int NBCAR_ASCII_MAX = 256;
    //private static final string OPTIONS_ARG = "hVsf:vqla";
    //private static final int NBOPTIONSARG = 8;
    //private static final string DEV_NULL = "/dev/null";
    //private static final int W_SPACE = 1;
    //private static final int W_NOEUD = 2;
    private static final int OCC_ID = 0;
    private static final int OCC_VAL = 1;
    
    public static void main(String[] args) throws IOException
    {
	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 = ERROR.FLAG.EXIT_SUCCESS //variable contient la valeur de retour du programme
	    ; 
 
	Liste_TNoeud liste = new Liste_TNoeud(); //Le tableau des noeuds après récupérations de toutes les occurences de chaque bytes.
	Liste_TNoeud L_TNmp = new Liste_TNoeud(), L_TNmp_prev = new Liste_TNoeud(); //pointeur temporaire

	//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.
	int[][] OCCURENCE = new int[NBCAR_ASCII_MAX][2]; //ça aurait été mieux en unsigned ... mais en java? http://stackoverflow.com/questions/430346/why-doesnt-java-support-unsigned-ints

	//string chaine; //la chaine de caractère concerné - si l'option choisis

	BufferedReader stream = new BufferedReader(new InputStreamReader (System.in));
	//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 = new TNoeud(), //La racine de l'arbre
	    TNmp = new TNoeud(), //pointeur temporaire réutilisé pour garder en mémoire l'adresse à traiter
	    TNmp_next = new TNoeud(); //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]=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=stream.read())!=-1)
	    {
		/*
		//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;
	          }
		*/
		//		System.out.printf("%d\n",i);
		OCCURENCE[i][OCC_VAL]++;
	    }

	
	/*
	  =================
	  à noté:
	  - suivis la méthode sur htpp://tcharles.developpez.com/Huffman
	  =================
	*/
	
	//On ordonne le tableau d'occurence
	//qsort(OCCURENCE, (size_t)NBCAR_ASCII_MAX, 2*(size_t)sizeof(int), __compare_int2);
	Arrays.sort(OCCURENCE, new Comparator<int[]>()
		    {
			@Override
			    public int compare(final int[] da, final int[] db)
			    {
				int diff1 = ((da[1] > db[1])?1:0) - ((da[1] < db[1])?1:0);
				if (diff1!=0) return diff1;
				return (((da[0] > db[0])?1:0) - ((da[0] < db[0])?1:0));
			    }
		    });

	//for (i=0; i<NBCAR_ASCII_MAX; System.out.printf("%d:%d\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, i=0; i<NBCAR_ASCII_MAX; i++)
	    {
		//Toutes les occurences valant 0 ne nous intéresse pas
		if (OCCURENCE[i][OCC_VAL]!=0)
		    {
			++nbc; //nb de caractère concerné

			//on alloue une nouvelle case dans la liste tab 
			L_TNmp = new Liste_TNoeud();
		     
			//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 (nbc == 1) liste = L_TNmp;

			//on alloue le noeud qui sera placé dans la nouvelle case
			TNmp = new TNoeud();
			TNmp.lettre = OCCURENCE[i][OCC_ID];
			TNmp.occ = OCCURENCE[i][OCC_VAL];
			TNmp.g = new TNoeud();
			TNmp.d = new TNoeud();
			
			//on ajoute le noeud dans la liste
			L_TNmp.noeud = TNmp;
			L_TNmp.suivant = new Liste_TNoeud();

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

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

	 //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.isEmpty(); TNmp = L_TNmp.noeud, System.out.printf("   %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
	TNmp = new TNoeud();
	while (!(liste.suivant).isEmpty())
	    {
		TNmp = liste.noeud; //Le fils gauche,
		TNmp_next = (liste.suivant).noeud; //la fille droite,
		TNmp = TNmp.somme(TNmp_next); //et le père courbe
      
		//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 = liste.ordre(); //sans oublier la porte.
	    }

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

	//fprintf(stdverb, ". Dessin de l'arbre huffman:\n");
      
    }

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


}


//Type de l'arbre utilisé
class TNoeud
{
  public int  lettre;
  public int  occ;
  public TNoeud  g; //g pour fils gauche
  public TNoeud  d; //d pour fils droit

    public TNoeud()
    {
	this.lettre = 0;
	this.occ = 0;
	this.g = null;
	this.d = null;
    }

//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)
    public TNoeud somme(TNoeud b)
    {
	TNoeud s = new TNoeud();

	if (this.isEmpty() || b.isEmpty()) return s;

	s.lettre = 0;
	s.occ = this.occ + b.occ;
	s.g = this;
	s.d = b;

	return s;
    }

    public int hauteur()
    {
	if (this.isEmpty()) return 0;

	TNoeud gauche = this.g;
	TNoeud droite = this.d;
	
	int maximum = max(gauche.hauteur(), droite.hauteur());
	return (maximum + 1);
    }

    public int max (int a, int b)
    {
	return (a>b?a:b);
    }

    //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)
    public int compare(TNoeud b)
    {
	int diff;
	if (this.isEmpty() || b.isEmpty()) return 0; //ce n'est normalement pas possible que 2 noeuds soit équivalent (à moins que le même paramètre est transmis).
	
	diff = ((this.occ > b.occ)?1:0) - ((this.occ < b.occ)?1:0);
	if (diff==0) //égaux
	    diff = ((this.lettre > b.lettre)?1:0) - ((this.lettre < b.lettre)?1:0);

	return diff;
    }

    public boolean isEmpty()
    {
	return (this.occ < 1);
    }
}

class Liste_TNoeud
{
  public TNoeud noeud;
  public Liste_TNoeud suivant;

    public Liste_TNoeud()
    {
        this.noeud = new TNoeud();
	this.suivant = null;
    }

    //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.
    public Liste_TNoeud ordre()
    {
	Liste_TNoeud L_TNdep = new Liste_TNoeud();
	L_TNdep = this;
	Liste_TNoeud L_TNdep_suiv = new Liste_TNoeud();
	Liste_TNoeud L_TNmp = new Liste_TNoeud();
	Liste_TNoeud L_TNi = new Liste_TNoeud();

	int i=0;

	L_TNdep_suiv = this.suivant;
	L_TNi = this.suivant;

	while (!L_TNi.isEmpty() && i > 0)
	    {
		switch (i=((this.noeud).compare(L_TNi.noeud)))
		    {
		    case 1: //plus grand
			L_TNmp = L_TNi;
			L_TNi = L_TNi.suivant;
			break;
		    case -1: //plus petit
			break;
		    }
	    }
	if (L_TNmp.isEmpty()) //this est bien le premier élément
	    return L_TNdep;

	L_TNmp.suivant = this;
	this.suivant = L_TNi;
	return L_TNdep_suiv;
    }
    
    public boolean isEmpty()
    {
	return (noeud.isEmpty());
    }
}

//KILL COPYRIGHT