Desktop/Daniele/Program Editing/Progetto di informatica 2/componenti/compressore.cpp

#include "compressore.h"
#include "listadoppia.h"

//#define DEBUG true
/*
togliere il commento se si vuole provare il programma in funzione debug
ho utilizzato le direttive di compilazione condizionale per includere parti
di codice che mi sono servite per il debug, a tal proposito ho introdotto la
macro sopra riportata*/
/* funzione che eleva a potenza b un intero a */
int compressore::elevato (int a, int b)
{
if (a == 0) return 0;
int app = 1;
for (int i = 0; i < b; i++)
    app *= a;
return app;
}

/*questa funzione è necessaria per come è implementata la traduzione da
carattere a intero, infatti in certi casi i valori sono completamente
errati, definisco questa funzione per operare direttamente sui bit*/
int compressore::traduci (char c)
{
int a = 0;
for (int i = 0; i < 8; i++)
    a = a + ((c >> (i)) & 1) * elevato(2,i);
return a;
}
    #if DEBUG
    #include <iostream> 
    #endif
    #if DEBUG
    namespace com
    {
    void preorder (node* tree)
    {
    if (tree == 0) return;
    cout << tree -> c << ' ' << tree -> freq << endl;
    preorder (tree -> left);
    preorder (tree -> right);
    }
    void postorder (node* tree)
    {
    if (tree == 0) return;
    postorder (tree -> left);
    postorder (tree -> right);
    cout << tree -> c << ' ' << tree -> freq << endl;
    }
    void inorder (node* tree)
    {
    if (tree == 0) return;
    inorder (tree -> left);
    cout << tree -> c << ' ' << tree -> freq << endl;
    inorder (tree -> right);
    }
    }
    #endif
    
//costruttore: compie tutte le operazioni necessarie
compressore::compressore(const char file[], const char fileo[])
{
    #if DEBUG
    cout << "DEBUG" << endl;
    #endif
stream.open (file, ios::in | ios::binary);
if (!stream) throw "apertura";
    #if DEBUG
    cout << "apertura ultimata" << endl;
    system ("PAUSE");
    #endif
    
contaoccorrenze();
    #if DEBUG
    cout << "conteggio occorrenze terminato" << endl;
    for (int i = 0; i < 256; i++)
        cout << char(i) << ' ' << v[i] << endl;
    system ("PAUSE");
    #endif

int a = arrayfreq();
num = a;
delete[] v; //cancella v, infatti adesso il vettore è inutile e occupa solo spazio
v = 0;
    #if DEBUG
    cout << "vettorizzazione, stampo risultati" << endl;
    cout << "vettore pf:" << endl;
    for (int i = 0; i < a; i++)
        cout << pf[i]->c << ' ' << pf[i]->freq << endl;
    system ("PAUSE");
    #endif


IOs out (fileo, pf, a);
heap hp(pf, a); //in questo punto viene generato lo heap
    #if DEBUG
    cout << "generazione heap completata" << endl;
    for (int i = 0; i < a; i++)
        cout << hp.v[i] -> c << ' ' << hp.v[i]->freq << endl;
    system ("PAUSE");
    #endif


int last = hp.lastn(); 
root = huffman (hp, last); //costruisce l'albero di huffman
delete[] pf; //una volta che ho distrutto il contenuto di questo array
             //anche l'heap corrispondente è vuoto
pf = 0; //dopo il passo sopra questo puntatore è inutile
    #if DEBUG
    cout << "costruzione albero ultimata" << endl;
    com::preorder (root);
    cout << "--------" << endl;
    com::postorder (root);
    cout << "--------" << endl;
    com::inorder (root);
    system ("PAUSE");
    #endif

c = new char*[256]; //array che conterrà le codifiche per velocizzare
if (c == 0) throw "memoria";
for (int i = 0; i < 256; i++)
    c[i] = 0;
char* app = new char[last+1];  //la traduzione
if (app == 0) throw "memoria";
app[0] = '\0';
if (root -> left == 0 && root -> right == 0)
   {
   int i = traduci(root -> c);
   c[i] = new char[2];
   if (c[i] == 0) throw "memoria";
   c[i][0] = '1';
   c[i][1] = '\0';
   }
else
    linearizza(root, app); //l'albero viene linearizzato nel vettore c
                          //che oltre al carattere contiene direttamente la
                          //frequenza
delete[] app;
app = 0;
cancella(root);
    #if DEBUG
    cout << "array di codifica ultimato" << endl;
    for (int i = 0; i < a; i++)
        cout << c[i].c << ' ' << c[i].codice << endl;
    system ("PAUSE");
    #endif

comprimi(file ,out);
for (int i = 0; i < last + 1; i++)
    delete[] c[i];
delete[] c; //cancello anche il vettore di codifiche
            //ora che la compressione è terminata

c = 0;
stream.close();
}

void compressore::cancella(node*& tree) //funzione di appoggio per la
                                        //distruzione dell'albero
{
if (tree==0) return;
cancella (tree ->left);
cancella (tree -> right);
delete tree;
tree = 0;
}

void compressore::contaoccorrenze() //funzione conta le occorrenze di ogni
{                                   //carattere calcolandone la frequenza
v = new int[256];
if (!v) throw "memoria";
for (int i = 0; i < 256; i++)
    v[i] = 0;
int a;
a = stream.get();
while (stream)
    {
    v[a]++;
    a = stream.get();
    }
}

/*per la prossima funzione ho pensato di usare la classe listadoppia per evitare
di scorrere più volte l'array e, dato che essa è munita di distruttore
la memoria al termine verrà liberata*/

int compressore::arrayfreq()
{
listadoppia l;
for (int j = 0; j < 256; j++)
    if (v[j] > 0) l.inserisci(j);
int n = l.numero();
if (n == 0) throw "vuoto";
pf = new frequenza* [n];
if (!pf) throw "memoria";
for (int i = 0; i < n; i++)
    {
    int e = l.estrai();
    pf[i] = new frequenza;
    if (!pf[i]) throw "memoria";
    pf[i] -> c = char(e);
    pf[i] -> freq = v[e];
    pf[i] -> left = pf[i] -> right = 0; 
    }
if (n == 0) throw "vuoto";
return n; //ritorna il numero di caratteri-frequenze trovate nel testo
}

/*huffman costruisce l'albero di huffman con il suo stesso algoritmo, a partire
da un heap ordinato in modo che la radice abbia frequenza minore, comincia a
estrarre dalla radice due nodi alla volta creando un sottoalbero che viene
reinserito nell'heap, e continua fino a che non ci rimane un solo puntatore
nell'heap, che viene restituito e assegnato alla variabile root della classe
compressore, ora ho la mia codifica*/

node* compressore::huffman (heap H, int last) //il mio heap va a costruire
{                                             //l'albero di huffman
for(int i = 0; i < last; i++) 
    {
    node* t = new node;
    if (t == 0) throw "memoria";
    t->left = H.estrai();
    t->right = H.estrai();
    t->freq= t->left->freq + t->right->freq; 
    H.inserisci(t);     
    }
return H.estrai();
}

void compressore::linearizza (node* tree, char* codice, int j)
{
if (tree == 0) return;                          //funzione che raccoglie le
if (tree -> left == 0 && tree -> right == 0)    //codifiche dall'albero
   {
   int i = traduci (tree -> c); //memorizzo la codifica direttamente nella
                                //cella corrispondente al carattere (accesso
                                //diretto hash)
   c[i] = new char[j+1];
   for (int a = 0; a < j+1; a++)
       c[i][a] = codice[a];
   return;
   }
char* codices = new char[j+2];
char* codiced = new char[j+2];
strcpy (codices,codice);
strcpy (codiced,codice);
codices[j] = '0';
codices[j+1] = '\0';
codiced[j] = '1';
codiced[j+1] = '\0';
linearizza(tree->left,codices, j+1);
linearizza(tree->right,codiced, j+1);
delete[] codices;
delete[] codiced;
}

void compressore::comprimi(const char file[], IOs& out)
{  //la comprimi mentre legge il file scrive nel file specificato alla
   //costruzione di compressore la codifica tramite la classe IO
char a;
stream.clear();
stream.close();
stream.open(file, ios::in | ios::binary);
a = char(stream.get());
while (stream)
    {
    int i = traduci(a);
    if (c[i] == 0) throw "lettura";
    for (int j = 0; j < strlen(c[i]); j++)
        out.inserisci(int(c[i][j]) - int('0'));
    a = char(stream.get());
    }
if (!stream.eof()) throw "compressione";
out.svuota();
}

---