/*
  mede frequencia de chars num arquivo
  desenha codigo de Huffman baseado em frequencias
  salva arquivo-codigo
  le arquivo-codigo
  compacta arquivo baseado em arquivo-codigo
  descompacta arquivo baseado em arquivo-codigo
 
  Arquivo-codigo e' um arquivo num formato especial, onde
  cada linha contem um byte em hexadecimal e seu codigo em bits. 
   (porem e' um arquivo texto).  Exemplo:
 
  23 101
  A4 01
  5B 11
 
  Serve para guardar codigos de Huffman em arquivos.
 
*/    

#include "heap.h"
#include "malloc.h"
#include "huffman.h"
#include <string.h>

typedef struct boku{
  int index;
  int letra;
  struct boku *dir;
  struct boku *esq;
} arvore;


/*-----------------------------------
  todas as rotinas abaixo retornam
  1 para sucesso
  0 para fracasso
 
  alem disso, input e output sempre
  se referem aos filenames, que devem
  ser abertos e fechados pela rotina
-----------------------------------*/     

/*
   freq e' um vetor indexado por CHARS
   os chars que nao aparecem no arquivo input terao
   frequencia zero
*/
 
int MedeFreq (filename input, int *freq)
{
  FILE *x;
  char y;
  x = fopen(input, "r");
  if (x!=NULL)
    {
      while(fscanf(x,"%c", &y)==1)
	freq[(int)y]++;
      fclose(x);
      return 1;
    }
  else return 0;
}
 
/*
  recebe frequencias e monta o codigo de Huffman 
  (string eh um vetor de 256 strings de zeros e uns).
*/

arvore *juntaarvore(arvore *pinheiro, arvore *carvalho)
{
  arvore *macieira;
  macieira = calloc(1,sizeof(arvore));
  macieira->index = pinheiro->index + carvalho->index;
  if (pinheiro->index < carvalho->index)
    /*nao serve pra nada a comparacao, so pra deixar bonitinha a arvore*/
    {
      macieira->esq = carvalho;
      macieira->dir = pinheiro;
    }
  else 
    {
      macieira->dir = carvalho;
      macieira->esq = pinheiro;
    }
  return macieira;
}

void destroiarvore(arvore **gorifico){
  if (*gorifico == NULL) return;
  destroiarvore(&((*gorifico)->dir));
  destroiarvore(&((*gorifico)->esq));
  free(*gorifico);
}

void codigovetor(arvore *teste, string *destino, string solucao, int pos)
{
  if (teste == NULL)
    return;
  if ((teste->esq == NULL)&&(teste->dir == NULL))
    {
      strcpy(destino[teste->letra],solucao);
      return;
    }
  solucao[pos] = '0';
  codigovetor(teste->esq, destino, solucao, pos+1);
  solucao[pos] = '1';
  codigovetor(teste->dir, destino, solucao, pos+1);
  return;
}

int Huffman (int *freq, string *codigo) {
  arvore *arbusto;
  arvore *tempa, *tempb;
  string solucao;
  Heap h;
  int i;
  
  CriaHeap(&h);
  for(i=0; i < CHARS ; i++) {
    if(freq[i]>0) {
      arbusto = calloc(1, sizeof(arvore));
      arbusto->esq = NULL;
      arbusto->dir = NULL;
      arbusto->index = freq[i];
      arbusto->letra = i;
      InsereOk(&h, arbusto->index, arbusto);
    }
  }

  while(!VazioHeap(&h)) {
    ExtraiMinOk(&h, &i, (void *)&tempa);
      if (ExtraiMinOk(&h, &i, (void *)&tempb)) {
	  arbusto = juntaarvore(tempa, tempb);
	  InsereOk(&h, arbusto->index, arbusto);
      } else
	arbusto = tempa;
  }
  solucao = calloc(CHARS, sizeof(char));
  codigovetor(arbusto, codigo, solucao, 0);
  free(solucao);
  destroiarvore(&arbusto);
  return 1;      
}
 
/* salva codigo em arquivo-codigo */  

char *int2hexa(int i) /* transforma int ate 256 em hexa */
{
  char *hexa;
  hexa = calloc(2, sizeof(char));
  if ((i/16)<10)
    hexa[0] = '0'+(i/16);
  else
    hexa[0] = ('A'-10)+(i/16);
  if ((i%16)<10)
    hexa[1] = '0'+(i%16);
  else
    hexa[1] = ('A'-10)+(i%16);
  return(hexa);
}


int SalvaCodigo (string *codigo, filename arqcod)
{
  int i;
  char *hexa;
  FILE *x;
  x = fopen(arqcod,"w");
  if (x==NULL) return 0;
  for(i=0; i<CHARS; i++)
    {
      hexa = int2hexa(i);
      if (strcmp(codigo[i],"")!=0)
	fprintf(x,"%c%c %s\n", hexa[0], hexa[1], codigo[i]);
      free(hexa);
    }
  fclose(x);
  return 1;
}

/* compacta arquivo baseado em arquivo-codigo */

int Compacta (filename arqcod, filename input, filename output) {
  FILE *IN,*OUT;
  int freq[CHARS];
  int i,res=1;
  char c;
  string *codigo;	

  codigo = calloc(CHARS,sizeof(string));  /* tamanho maximo de codigo p/ n simbolos eŽ n */
  for (i=0;i<CHARS;i++)                   /* colocamos n+1 soŽ pra dar uma folga */
    codigo[i]= calloc(CHARS+1,sizeof(char));

  memset(freq, 0, sizeof(freq));
  if (MedeFreq(input,freq)){ 
    Huffman(freq,codigo);
    if(SalvaCodigo(codigo,arqcod)){
      
      IN = fopen(input, "r");
      OUT = fopen(output, "w");
      if ((IN!=NULL) && (OUT!=NULL)){
	

	while(fscanf(IN,"%c", &c)==1){
	  i=0;
	  while(codigo[(int)c][i]!= '\0'){
	    fprintf(OUT,"%c",codigo[(int)c][i]);
	    i++;
	  }
	}

	fclose(IN);
	fclose(OUT);
      }
    }
    else res=0;
  }
  else res=0;

  for (i=0;i<CHARS;i++)
    free(codigo[i]);
  free(codigo);
  return res;
}

/* descompacta arquivo baseado em arquivo-codigo */

/* 
   O descompactaro recebe um arquivo de entrada (input) e um arquivo codigo (arqcod), e deve, a partir desses, gerar um arquivo de saida (output) que contenha a operacao inversa da compactacao utilizando codigo de huffman.

   O formato de "arqcod" eh:
HH BBBBBBBBB\n
HH BBBBBBB...BBBBB\n
HH BBB\n
...
HH BBBBB..BBBBB\n

   Ou seja, existe um numero arbitrario de linhas, cada uma iniciada por dois caracteres representando um numero hexadecimal de 2 digitos (as letras sendo maiusculas). Depois vem 1 espaco, e depois vem um numero variavel de caracteres 0 e 1, que representam o codigo do caractere indicado pelo valor de HH.

   Por exemplo, a linha:
0A 0010011\n

   Significa que o caractere 0A (10, '\n') esta representado no arquivo compactado por "0010011". Depois da ultima linha existe o fim-de-arquivo.
   
   Para voce descompactar, voce tera que ler esses codigos do arquivo de codigo e armazena-los em alguma estrutura de dados (dica: arvore binaria). Depois voces devem ler o arquivo de entrada e substituir cada sequencia pertecente ao codigo que encontrarem la pelo caractere correspondente na saida.

   Para ficar mais simples, ao inves de salvar bits, o compactador escreve o codigo como uma sequencia de caracteres 0s e 1s (isto eh, voce nao precisa procurar pela sequencia de bits 0010011, mas sim pela sequencia de caracteres "0010011". Isso significa que nos nao vamos realmente compactar nada (na verdade, vamos "aumentar"), mas basta trocar este fato para termos um compactador funcional. Os mais empolgados deveriam tentar esse exercicio.
*/


int LeCodigo (filename arqcod, string *codigo) {
  FILE *x;
  unsigned int i;

  x = fopen(arqcod,"r");
  if (x==NULL) return 0;

  while ( fscanf(x,"%X",&i) != EOF ) {
    if ( i < 256 ) 
      fscanf(x," %s\n", codigo[i]);
  }

  fclose(x);
  return 1;
}


void Codigo2Arvore(arvore *arv,string codigo, int *pos, char letra) {

  if (arv == NULL) return;

  switch ( codigo[*pos] ) {
  case '\0': 
    arv->letra=(char) letra;
    arv->index=0;
    arv->dir= arv->esq = NULL;
    break;
  case '0':
    if (arv->esq == NULL) {
      arv->esq = (arvore *) calloc(1,sizeof(arvore));
      arv->esq->dir=NULL;
      arv->esq->esq=NULL;
    }
    ++(*pos);
    
    Codigo2Arvore(arv->esq, codigo, pos, letra);
    break;
  case '1':
    if (arv->dir == NULL) {
      arv->dir = (arvore *) calloc(1,sizeof(arvore));
      arv->dir->dir=NULL;
      arv->dir->esq=NULL;
    }
    ++(*pos);
    Codigo2Arvore(arv->dir, codigo, pos, letra);
    break;
  }
}

void ImprimeArvore(arvore *arv) {
  if ( arv != NULL) {
    if ( (arv->esq==NULL) && (arv->dir==NULL) )
      printf("\n\tLetra da Folha: %c (ascii: %i)\n",arv->letra,arv->letra);
    if ( arv->esq!=NULL ) {
      printf("0 ");
      ImprimeArvore(arv->esq);
    } 
    if  ( arv->dir!=NULL ) {
      printf("1 ");
      ImprimeArvore(arv->dir);
    } 
  }     
} 

int Decodifica(arvore **arv,char c) {
  if ( *arv == NULL ) { fprintf(stderr,"Decodifica(): Arvore inexistente, retornando 0\n"); return 0; }
  switch (c) {
  case '0':
    *arv = (*arv)->esq;
    break;
  case '1':
    *arv = (*arv)->dir;
    break;
  }
  if ( ((*arv)->dir == NULL) && ((*arv)->esq == NULL) ) /* e folha, retorne o caracter */
    return (*arv)->letra;

  return -1; /* numero negativo= nao chegou aa folha */

}

int Descompacta (filename arqcod, filename input, filename output) {
  FILE *IN,*OUT;
  int i,res=1;
  int pos, r;
  char c;
  arvore *arv, *arv2;
  
  string *codigo;
  
  codigo = (string *) calloc(CHARS,sizeof(string));  /* tamanho maximo de codigo p/ n simbolos eŽ n */
  for (i=0;i<CHARS;i++)                 /* colocamos n+1 soŽ pra dar uma folga */
    codigo[i]= calloc(CHARS+1,sizeof(char));
  
  LeCodigo(arqcod,codigo);
  
  arv = (arvore *) calloc(1,sizeof(arvore));
  arv->dir=NULL;
  arv->esq=NULL;
  for (i=0,pos=0; i<CHARS; i++,pos=0)
    if (codigo[i][0]!='\0')
      Codigo2Arvore(arv,codigo[i],&pos,(char)i);
  
  arv2 = arv;


  IN = fopen(input,"r");
  OUT = fopen(output,"w");
  if ((IN!=NULL) && (OUT!=NULL)){
    while ( fscanf(IN,"%c",&c) != EOF ) {
      r=Decodifica(&arv2,c);
      if (r > -1){
	fprintf(OUT,"%c",r);
	arv2 = arv;
      }
    }
    fclose(IN);
    fclose(OUT);
  }
  
  for (i=0;i<CHARS;i++)
    free(codigo[i]);
  free(codigo);
  destroiarvore(&arv);
  return res;
}









/* author: Gustavo Sverzut Barbieri (http://www.gustavobarbieri.com.br) */