#include <iostream>
#include <cstdio>
using namespace std;
typedef struct _nodo{
char letra;
int frecuencia;
_nodo *sig;
_nodo *cero;
_nodo *uno;
} tipoNodo;
typedef struct _tabla{
char letra;
unsigned long int bits;
char nbits;
_tabla *sig;
} tipoTabla;
tipoTabla *Tabla;
void Cuenta(tipoNodo* &Lista, char c);
void Ordenar(tipoNodo* &Lista);
void InsertarOrden(tipoNodo* &Cabeza, tipoNodo *e);
void BorrarArbol(tipoNodo *n);
void CrearTabla(tipoNodo *n, int l, int v);
void InsertarTabla(char c, int l, int v);
tipoTabla *BuscaCaracter(tipoTabla *Tabla, char c);
int main(int argc, char *argv[]){
tipoNodo *Lista;
tipoNodo *Arbol;
FILE *fe, *fs;
char c;
tipoNodo *p;
tipoTabla *t;
int nElementos;
long int Longitud = 0;
unsigned long int dWORD;
int nBits;
if(argc < 3)
{
cout<<"\n\tUsar:\n\t"<<argv[0]<<" <fichero_entrada> <fichero_salida>\n";
return 1;
}
Lista = NULL;
fe = fopen(argv[1], "r");
while((c = fgetc(fe)) != EOF){
Longitud++;
Cuenta(Lista, c);
}
fclose(fe);
Ordenar(Lista);
Arbol = Lista;
while(Arbol && Arbol->sig){
p = new(tipoNodo);
p->letra = 0;
p->uno = Arbol;
Arbol = Arbol->sig;
p->cero = Arbol;
Arbol = Arbol->sig;
p->frecuencia = p->uno->frecuencia + p->cero->frecuencia;
InsertarOrden(Arbol, p);
}
Tabla = NULL;
CrearTabla(Arbol, 0, 0);
fs = fopen(argv[2], "wb");
fwrite(&Longitud, sizeof(long int), 1, fs);
nElementos = 0;
t = Tabla;
while(t){
nElementos++;
t = t->sig;
}
fwrite(&nElementos, sizeof(int), 1, fs);
t = Tabla;
while(t)
{
fwrite(&t->letra, sizeof(char), 1, fs);
fwrite(&t->bits, sizeof(unsigned long int), 1, fs);
fwrite(&t->nbits, sizeof(char), 1, fs);
t = t->sig;
}
fe = fopen(argv[1], "r");
dWORD = 0;
nBits = 0;
while((c = fgetc(fe)) != EOF)
{
t = BuscaCaracter(Tabla, c);
while(nBits + t->nbits > 32){
c = dWORD >> (nBits-8);
fwrite(&c, sizeof(char), 1, fs);
nBits -= 8;
}
dWORD <<= t->nbits;
dWORD |= t->bits;
nBits += t->nbits;
}
while(nBits>0){
if(nBits>=8) c = dWORD >> (nBits-8);
else c = dWORD << (8-nBits);
fwrite(&c, sizeof(char), 1, fs);
nBits -= 8;
}
fclose(fe);
fclose(fs);
BorrarArbol(Arbol);
while(Tabla){
t = Tabla;
Tabla = t->sig;
delete(t);
}
return 0;
}
void Cuenta(tipoNodo* &Lista, char c){
tipoNodo *p, *a, *q;
if(!Lista){
Lista = new(tipoNodo);
Lista->letra = c;
Lista->frecuencia = 1;
Lista->sig = Lista->cero = Lista->uno = NULL;
}
else{
p = Lista;
a = NULL;
while(p && p->letra < c){
a = p;
p = p->sig;
}
if(p && p->letra == c) p->frecuencia++;
else{
q = new(tipoNodo);
q->letra = c;
q->frecuencia = 1;
q->cero = q->uno = NULL;
q->sig = p;
if(a) a->sig = q;
else Lista = q;
}
}
}
void Ordenar(tipoNodo* &Lista){
tipoNodo *Lista2, *a;
if(!Lista) return;
Lista2 = Lista;
Lista = NULL;
while(Lista2){
a = Lista2;
Lista2 = a->sig;
InsertarOrden(Lista, a);
}
}
void InsertarOrden(tipoNodo* &Cabeza, tipoNodo *e)
{
tipoNodo *p, *a;
if(!Cabeza){
Cabeza = e;
Cabeza->sig = NULL;
}
else{
p = Cabeza;
a = NULL;
while(p && p->frecuencia < e->frecuencia){
a = p;
p = p->sig;
}
e->sig = p;
if(a) a->sig = e;
else Cabeza = e;
}
}
void CrearTabla(tipoNodo *n, int l, int v){
if(n->uno) CrearTabla(n->uno, l+1, (v<<1)|1);
if(n->cero) CrearTabla(n->cero, l+1, v<<1);
if(!n->uno && !n->cero) InsertarTabla(n->letra, l, v);
}
void InsertarTabla(char c, int l, int v){
tipoTabla *t, *p, *a;
t = new(tipoTabla);
t->letra = c;
t->bits = v;
t->nbits = l;
if(!Tabla){
Tabla = t;
Tabla->sig = NULL;
}
else{
p = Tabla;
a = NULL;
while(p && p->letra < t->letra){
a = p;
p = p->sig;
}
t->sig = p;
if(a) a->sig = t;
else Tabla = t;
}
}
tipoTabla *BuscaCaracter(tipoTabla *Tabla, char c){
tipoTabla *t;
t = Tabla;
while(t && t->letra != c) t = t->sig;
return t;
}
void BorrarArbol(tipoNodo *n){
if(n->cero) BorrarArbol(n->cero);
if(n->uno) BorrarArbol(n->uno);
delete(n);
}