#include <stdio.h>

struct char_struct {
  unsigned char c;
  struct char_struct *prox;
};

unsigned char *leia_texto(long *n)
{
  struct char_struct *p, *t;
  int ch;
  long n_chars=0;
  long k;

  unsigned char *ptr;

  t=NULL;
  while ((ch=getchar())>-1) { /* getchar() devolve -1 no fim do arquivo */
    p=(struct char_struct *)malloc(sizeof(struct char_struct));
    if (!p) {
      fprintf(stderr, "Oops, estou sem memoria para os caracteres!\n");
      exit(-1);
    }
    p->c=(unsigned char)ch;
    p->prox=t;
    t=p;
    n_chars++;
  }

  *n=n_chars;  
  ptr=(unsigned char *)malloc(n_chars);
  if (!ptr) {
    fprintf(stderr, "Oops, estou sem memoria para o vetor!\n");
    exit(-2);
  }

  k=n_chars;
  while (t) {
    p=t;
    t=t->prox;
    k--;
    *(ptr+k)=p->c;
    free(p);
  }

  return ptr;
}

void pqdownheap(int *heap, long h_size, long *count, long k)
{
  int j;
  int v=heap[k];
  while (k<=h_size/2) {
    j=k+k;
    if ((j<h_size)&&(count[heap[j]]>count[heap[j+1]])) j++;
    if (count[v]<=count[heap[j]]) break;
    heap[k]=heap[j];
    k=j;
  }
  heap[k]=v;
}

main(argc, argv)
   int argc; 
   char **argv;
{
  long n_chars;
  long n_bits=0;
  unsigned char *texto;
  long i, j, k, x;
  long h_size;
  int t;

  long count[520];
  long dad[520];
  int heap[520];

  long code[256];
  long len[256];

  long quer_texto_compactado=1;

  if (argc>1) /* assumimos que queremos texto compactado impresso */
    quer_texto_compactado=0;
  
  texto=leia_texto(&n_chars);

  for (i=0; i<520; i++)
    count[i]=0;

  for (k=0; k<520; k++)
    dad[k]=heap[k]=0;

  for (j=0; j<n_chars; j++)
    count[*(texto+j)]++;

  for (i=h_size=0; i<=256; i++)
    if (count[i]) heap[++h_size]=i;

  for (k=h_size/2; k>0; k--)
    pqdownheap(heap, h_size, count, k);

  while (h_size>1) {
    t=heap[1]; heap[1]=heap[h_size--];
    pqdownheap(heap, h_size, count, 1);

    count[256+h_size]=count[heap[1]]+count[t];
    dad[t]=256+h_size;
    dad[heap[1]]=-256-h_size;

    heap[1]=256+h_size; pqdownheap(heap, h_size, count, 1);
  }
  dad[256+h_size]=0;

  for (k=0; k<256; k++)
    if (!count[k]) 
      code[k]=len[k]=0;
    else {
      i=0; j=1; t=dad[k]; x=0;
      while (t) {
        if (t<0) {
          x+=j; t=-t;
        }
        t=dad[t]; j+=j; i++;
      }
      code[k]=x;
      len[k]=i;
    }

  for (j=0; j<n_chars; j++)
    for (i=len[texto[j]]; i>0; i--) {
      if (quer_texto_compactado)
        printf("%1d", (code[texto[j]]>>(i-1))&01); 
      n_bits++;
    }
  if (quer_texto_compactado)
    printf("\n\n");

  printf("Numero de caracteres lidos: %ld\n", n_chars);
  printf("Numero de bits necessarios para representar %ld caracteres: %ld\n", 
          n_chars, n_chars*8);  
  printf("Numero de bits usados: %ld\nEconomia de %.1f%% do original.\n",
         n_bits, 100*(1-(double)n_bits/(8*n_chars)));
  printf("O codigo gerado e usado foi o seguinte:\n");
  for (k=0; k<256; k++)
    if (count[k]) {
      printf("%c: ", k);
      for (i=len[k]; i>0; i--)
        printf("%1d", (code[k]>>(i-1))&01);
      printf("\n");
    }

  return 0;
}