#include "nodo_albero.h"
#include "info.h"
#define MAX 256 //nome della macro(identificatore)
using namespace std;
typedef unsigned long long int uint64;
void menu(int &);
void assegna_nome_file(int opzione,ifstream &, ofstream &,char [],char []);
void conta_occorrenze(int[],ifstream &);
void riempi_coda(priority_queue<NODO,vector<NODO>,greater<NODO> > &, int[], int &);
void costruisci_albero(priority_queue<NODO,vector<NODO>,greater<NODO> > , NODO **);
void tabella_codici(NODO *, INFO [],unsigned,unsigned);
void scrivi_output(INFO [], int, int[], ofstream &);
void genera_codifica(INFO [], ifstream &, ofstream &,char [],char []);
void leggi_output(int &, int[], ifstream &);
void genera_decodifica(int , NODO *, ifstream &, ofstream &,char [],char []);
void visita_albero(unsigned, NODO **);
void stampa(int,char [],char []);
const uint64 getsize(const char *filename)
{
uint64 size = 0;
ifstream fp(filename, ios::in | ios::binary);
if(!fp.is_open())
return 0x00;
fp.seekg(0, ios::end);
size = fp.tellg();
fp.close();
return size;
}
int main()
{
priority_queue<NODO,vector<NODO>,greater<NODO> > PQ; //coda di priorità
int freq[MAX]={0},size_PQ=0,n_bit=0,opzione;
/*In c++ si apre un file collegandolo a uno stream.Prima di poter aprire un file
si dovrà pertanto aprire uno stream(ci sono 3 tipi di stream: di input,di output,
di input/output)*/
ifstream input; /*la classe ifstream crea uno stream di input(cioè uno
stream che dovrà eseguire operazioni di lettura)*/
ofstream output; /*la classe ofstream crea uno stream di output(cioè uno
stream che dovrà eseguire operazioni di scrittura)*/
//array che conterranno i nomi dei file
char nomefile_in[50],nomefile_out[50];
INFO w[MAX]; //dichiarazione tabella dei codici
NODO *radice=NULL; //radice dell'albero/sottoalbero
menu(opzione);
assegna_nome_file(opzione,input,output,nomefile_in,nomefile_out);
//uint64 size_f=getsize(nomefile_in);
//cout<<"%llu"<<size_f;
switch(opzione)
{
case 1:
{
conta_occorrenze(freq,input);
riempi_coda(PQ,freq,size_PQ);
costruisci_albero(PQ,&radice);
tabella_codici(radice,w,0,0);
scrivi_output(w,size_PQ,freq,output);
genera_codifica(w,input,output,nomefile_in,nomefile_out);
break;
}
case 2:
{
leggi_output(n_bit,freq,input);
riempi_coda(PQ,freq,size_PQ);
costruisci_albero(PQ,&radice);
genera_decodifica(n_bit,radice,input,output,nomefile_in,nomefile_out);
}
}
input.close(); //chiudo il file collegato allo stream input
output.close(); //chiudo il file collegato allo stream output
delete radice;
system("pause");
return 0;
}
//funzione che stampa il menu e restituisce la scelta effettuata dall'utente
void menu(int &scelta)
{
system("color B");
do
{
cout<<"-------------------------------------MENU--------------------------------------"<<endl;
cout<<" 1)Codifica di Huffman "<<endl;
cout<<" 2)Decodifica di Huffman "<<endl;
cout<<" 0)Uscita "<<endl;
cout<<"-------------------------------------------------------------------------------"<<endl;
cout<<endl<<endl;
cout<<"\n\t\t\t Scelta : ";
cin>>scelta;
//svuota il buffer di input fino al carattere di fine riga '\n'
cin.ignore(numeric_limits<streamsize>::max(),'\n');
if (scelta==0)
{
system("cls");
cout<<"Arrivederci!"<<endl;
exit(1);
}
if(scelta<0 | scelta>2)
{
cout<<"\n\nLa scelta "<<scelta<<" e' errata."<<endl<<"Prego, ripetere l'inserimento!!!!"<<endl;
Sleep(3000);
system("cls");
}
} while (scelta<0 | scelta>2);
}
//funzione che apre i flussi di I/O e che restituisce i nomi dei file di input/output
void assegna_nome_file(int opzione,ifstream & input, ofstream & output,char nomefile_in[],char nomefile_out[])
{
cout<<endl;
if(opzione==1)
{
cout << "Inserisci il nome del file di input (con estensione): ";
cin.getline(nomefile_in,50);
}
else
{
cout << "Inserisci il nome del file di input (senza estensione): ";
cin.getline(nomefile_in,50);
strcat(nomefile_in,".huf"); //Nella decodifica aggiungere l'estensione .huf in automatico al file di input
}
//Dopo aver creato uno stream,un modo per associarlo ad un file consiste nell' uso della funzione open(),che è un membro di ognuna delle 3 classi di stream.Qui nomefile_in è il nome del file(si puo anche includere uno specificatore di percorso), il valore ios::binary provoca l' apertura di un file in modalità binaria.Per ifstream i valore standard di modalità è ios::in il quale specifica che il file è in grado di fornire dati per operazioni di input.
input.open(nomefile_in,ios::binary);
if (!input.is_open()) //Verifico se c'è un errore nell' apertura del file
{
cout<<"Impossibile aprire il file"<<endl;
system("pause");
exit(1);
}
if(opzione==1)
{
cout << "Inserisci il nome del file di output (senza estensione): ";
cin.getline(nomefile_out,50);
strcat(nomefile_out,".huf"); //Nella codifica aggiungere l'estensione .gm in automatico al file di output
}
else
{
cout << "Inserisci il nome del file di output (con estensione): ";
cin.getline(nomefile_out,50);
}
//Qui nomefile_out è il nome del file, il valore ios::binary provoca l' apertura di un file in modalità binaria.Per ofstream i valori standard di modalità sono ios::out il quale specifica che il file è in grado di accettare dati in output, e ios::trunc che provoca la distruzione del contenuto di un file precedente avente lo stesso nome e tronca la lunghezza del file a zero(quando si crea uno stream di output con ofstream,un eventuale file preesistente verrà troncato a zero).
output.open(nomefile_out,ios::binary);
//Prima di utilizzare un file si deve controllare che l'operazione di apertura abbia avuto successo.Per controllare se il file è stato aperto con successo si usa la funzione is_open()(che è un membro di ifstream,ofstream,fstream),la quale restituisce true se lo stream è connesso a un file aperto e false in tutti gli altri casi.
if (!output.is_open())
{
cout<<"Impossibile aprire il file"<<endl;
system("pause");
exit(1);
}
}
/*funzione in cui si determinano le frequenze con le quali ciascun carattere
ricorre nel file di input*/
void conta_occorrenze(int v[],ifstream &input)
{
unsigned char c;
while(input)
{
/*La funzione get() legge un carattere per volta da uno stream e ,in tal caso,
ne restituisce il valore*/
c=input.get();
v[c]++;
}
}
/*funzione che riempie la coda di priorità Q.Per ciascun carattere viene allocato
un nodo che lo rappresenti.In virtù delle proprietà di questa struttura dati, i
nodi verranno ordinati in maniera tale che il primo elemento ad essere estratto
sarà quello con il minimo valore della frequenza. Attenzione:ciò non significa
che gli elementi siano in ordine crescente di frequenza ma solo che il primo ha
il minimo valore di essa.*/
void riempi_coda(priority_queue<NODO,vector<NODO>,greater<NODO> > &PQ, int freq[], int & size_PQ)
{
NODO *rif;
/*Gestione delle eccezioni (gestione degli errori che si verificano al momento
dell' esecuzione,per evitare che provochino il blocco del programma): Allocazione
dinamica della memoria*/
try
{
rif=new NODO(0,0); //istruzione del programma che si desidera controllare
}
//se all' interno del blocco try si verifica l' errore(eccezione),esso viene raccolto tramite catch che lo gestisce.
catch (bad_alloc xa)
{
cout<<"\aErrore allocazione memoria"<<endl;
exit(1);
}
for (int c=0;c<MAX;c++)
if (freq[c]!=0)
{
rif->setCarattere(c); //inizializza tramite il metodo setCarattere il campo carattere del nodo rif
rif->setFreq(freq[c]); //inizializza tramite il metodo setFreq il campo Freq del nodo rif
PQ.push(NODO(rif)); //inserisce in coda il nodo rif
}
size_PQ=PQ.size(); //contiene il numero di elementi presenti nella coda
}
//funzione che costruisce l'albero dei codici di huffman associato alle frequenze precedentemente calcolate.Viene allocato un nuovo nodo z che avrà come figli i due nodi minimi estratti dalla coda e come frequenza la somma delle loro frequenze. Tale nodo sarà poi inserito nella coda e occuperà un certo posto in essa, a seconda del valore della sua frequenza.
void costruisci_albero(priority_queue<NODO,vector<NODO>,greater<NODO> > PQ,NODO **radice)
{
//Ciclo che continua fin quando la coda contiene almeno due elementi
while (PQ.size()>1)
{
NODO *figlio_0;
try//Gestione delle eccezioni : Allocazione dinamica della memoria
{
figlio_0 = new NODO(PQ.top()); /*Estrazione di un elemento dalla coda.
top() restituisce l'elemento superiore
nel priority_queue.*/
}
catch (bad_alloc xa)
{
cout<<"\aError : Allocazione memoria"<<endl;
exit(1);
}
PQ.pop();
NODO *figlio_1;
try//Gestione delle eccezioni : Allocazione dinamica della memoria
{
figlio_1 = new NODO(PQ.top()); //Estrazione di un elemento dalla coda
}
catch (bad_alloc xa)
{
cout<<"\aErrore allocazione memoria"<<endl;
exit(1);
}
PQ.pop();
PQ.push(NODO(figlio_0,figlio_1));
}
NODO *z;
//Gestione delle eccezioni : Allocazione dinamica della memoria
try
{
z=new NODO(PQ.top()); //Estrazione dell'ultimo elemento dalla coda ovvero la radice
}
catch (bad_alloc xa)
{
cout<<"\aErrore allocazione memoria"<<endl;
exit(1);
}
*radice=z;
PQ.pop();
}
//funzione che attraversa l'albero di Huffman e che restituisce la tabella dei codici
void tabella_codici(NODO *radice,INFO w[],unsigned code,unsigned len)
{
//Dato che l'albero di huffman è un albero completo, basta controllare se il nodo esaminato ha il figlio sinistro
if (radice->getsx())
{
code<<=1; //shift del codice per aggiungere successivamente un bit
len++; //incremento della lunghezza del codice
//chiamata ricorsiva : attraversa l'albero a sinistra con l'aggiunta del bit 0
tabella_codici(radice->getsx(),w,code,len);
//chiamata ricorsiva : attraversa l'albero a destra con l'aggiunta del bit 1
tabella_codici(radice->getdx(),w,code|1,len);
}
else
{
unsigned char ch=radice->getCarattere(); //lettura del carattere
w[ch].setCod(code); //inizializzazione del codice nella tabella dei codici
w[ch].setLen(len); //inizializzazione della lunghezza del codice nella tabella dei codici
}
}
//funzione che scrive i caratteri con le rispettive frequenze sul file di output
void scrivi_output(INFO w[],int size_PQ, int f[],ofstream & output)
{
//output del size su file, il size indica il numero di caratteri codificati
output.put((char)(size_PQ>>8)&255);
output.put((char)size_PQ&255);
int n_bit=0;
for (int i=0;i<MAX;i++)
if (f[i]!=0)
{
output.put(i);
output.put((char)(f[i]>>24)&255); //output frequenze su file a blocchi di 8 bit
output.put((char)(f[i]>>16)&255);
output.put((char)(f[i]>>8)&255);
output.put((char)f[i]&255);
//Calcolo dei bit significativi per la decodifica, per evitare il problema dell'ultimo byte letto
n_bit+=w[i].getLen()*f[i];
}
output.put((char)(n_bit>>24)&255); //output del numero di bit significativi per la decodifica
output.put((char)(n_bit>>16)&255);
output.put((char)(n_bit>>8)&255);
output.put((char)n_bit&255);
}
//funzione che genera la codifica associata all'albero di Huffman precedentemente calcolato
void genera_codifica(INFO w[],ifstream & input,ofstream & output,char nomefile_in[],char nomefile_out[])
{
unsigned char c,buffer=0,b;
unsigned codice,k=0;
input.clear();
//La funzione seekg() è un membro di istream,quindi può essere usata solo se lo stream è aperto in lettura.Essa gestisce un puntatore che specifica la posizione in cui avverrà la prossima operazione di input. 0 indica l' offset di cui spostare il puntatore in modo relativo a quanto specificato dall'argomento beg(che indica la direzione dello spostamento).In tal caso seekg() sposta il puntatore di input a 0 byte dalla posizione specificata da ios::beg(posizionamento dall' inizio).
input.seekg(0,ios::beg);
while (input.good())
{
c=input.get(); //input di un singolo carattere
codice=w[c].getCod(); //input del codice del carattere letto dalla tabella dei codici
for (int i=w[c].getLen()-1;i>=0;i--) //ciclo in base alla lunghezza del codice di ogni carattere
{
b=codice&1;
b=(codice>>i)&1; //estrazione del bit, man mano, più significativo
if (k<8)
{
buffer=(buffer<<1)|b; //aggiunta del bit estratto alla variabile buffer
k++;
}
else
{
output.put(buffer);
buffer=b;
k=1;
}
}
}
buffer=buffer<<(8-k); //controllo sull'ultimo byte
output.put(buffer);
stampa(0,nomefile_in,nomefile_out);
}
//funzione che legge il contenuto del file compresso
void leggi_output(int & n_bit,int freq[],ifstream &input)
{
int size,f=0;
unsigned char char_ind,ch;
ch=input.get(); //input primo carattere ovvero il size
size=ch;
ch=input.get();
size=(size<<8)|ch; //operazione di shift e or per leggere il size composto da 2 byte
for (int i=0;i<size;i++)
{
char_ind=input.get(); //input carattere che verrà usato come indice del carattere in formato ascii
//input di 4 byte che rappresentano la frequenza del carattere; frequenza espressa rifunto da 4 byte in intero
for (int j=0;j<4;j++)
{
ch=input.get();
f=(f<<8)|ch;
}
freq[char_ind]=f; //salvataggio frequenza
f=0;
}
for (int j=0;j<4;j++) //input ultimi 2 byte di size che rappresentano il numero di bits significativi per la decodifica
{
ch=input.get();
n_bit=(n_bit<<8)|ch;
}
}
//funzione che decodifica il file di output creato della funzione codifica
void genera_decodifica(int n_bit,NODO *radice,ifstream &input,ofstream & output,char nomefile_in[],char nomefile_out[])
{
unsigned char ch,c_dec=0;
unsigned b=0;
int j=0;
NODO *punt=NULL;
punt=radice;
while (input.good())
{
ch=input.get();
if(ch=='255')
exit(1);
else//input di un singolo carattere
for (int i=7;i>=0 && j<n_bit;i--,j++) //ciclo che attraversa man mano l'albero di huffman in base ai bit estratti
{
b=ch;
b=(b>>i)&1; //estrazione di un singolo bit
visita_albero(b,&punt); //attraversamento dell'albero di huffman in base al bit estratto
//Controllo sul nodo: se è una foglia
if (punt->getsx()==NULL && punt->getdx()==NULL)
{
c_dec=punt->getCarattere(); //input del carattere dall'albero di huffman
output.put(c_dec); //output del carattere decodificato sul file di output
punt=radice; //puntatore che ritorna alla radice dell'albero
b=0;
}
}
}
//La funzione seekp() è un membro di ostream,quindi può essere usata solo se lo stream è aperto in scrittura. In tal caso il valore negativo dell' offset(-1) permette di spostarsi all' indietro rispetto alla fine del file(ios::end).
output.seekp(-1,ios::end);
c_dec=c_dec&0;
output.put(c_dec);
stampa(1,nomefile_in,nomefile_out);
}
//funzione che attraversa l'albero di Huffman in base ai bit estratti dal file codificato.Ogni qual volta si raggiunge una foglia dell'albero, la visita si arresta, il rispettivo carattere viene scritto nel file di output e si riposiziona il puntatore della visita alla radice dell'albero stesso.
void visita_albero(unsigned ramo,NODO **punt)
{
if (ramo==0)
*punt=(*punt)->getsx();
else
*punt=(*punt)->getdx();
}
//funzione che stampa i due disegni che rrifresentano codifica e decodifica in base ad un flag dato in input
void stampa(int flag,char in[],char out[])
{
//system("cls");
string intestazione="<ALGORITMO HUFFMAN>";
cout<<"\t\t\t\t"<<intestazione<<endl;
cout<<endl<<endl;
if(flag==0)
cout<<"File "<<"<"<<in<<">"<<" codificato in ---> "<<out<<endl;
else
cout<<"File "<<" <"<<in<<"> "<<" decodificato in ---> "<<out<<endl;
}