<filename>static_tree.cpp
/* Autor: <NAME> (xsuhaj02)
*  Datum vytvorenia: 05.04.2019
*  Subor: static_tree.cpp:
   Subor obsahuje implementaciu triedy static_tree, ktora obsahuje potrebne moteody
   pre vytvorenie stacikeho Huffmanovo stromu a pracu s nim.
*/

#include <string>
#include <queue>
#include <iostream>
#include "static_tree.hpp"


using namespace std;


/**
 * konstruktor - inicializacia potrebnych privatnych premennych
 */
static_tree::static_tree(){
	root = NULL;
    padding = -2;
    bit_shift = 7;
}

/**
 * destruktor - vymazanie stromu
 */
static_tree::~static_tree(){
	delete_tree(root);
}


/**
 * Metoda na kopirovanie uzlov stromu
 * @param from zdrojovy uzol
 * @param to cielovy uzol
 */
void static_tree::copy_nodes(node *from, node* to){
    node *tmp = new node;
    tmp->id = from->id;
    tmp->frequency = from->frequency;
    tmp->left_node = from->left_node;
    tmp->right_node = from->right_node;


    to->id = tmp->id;
    to->frequency = tmp->frequency;
    to->left_node = NULL;
    to->right_node = NULL;
    if(tmp->left_node != NULL){
        to->left_node = tmp->left_node;
    }
    if(tmp->right_node != NULL){
        to->right_node = tmp->right_node;
    }
    delete tmp;
}


/**
 * Metoda na zrusenie stromu.
 * @param to_delete uzol od ktoreho sa ma mazat
 */
void static_tree::delete_tree(node *to_delete){
	if(to_delete != NULL){
		delete_tree(to_delete->right_node);
		delete_tree(to_delete->left_node);
		delete to_delete;
	}
}


//vytvorenie stromu na zaklade frekvencii
/**
 * Metoda vytvori staticky huffmanov strom na zaklade frekvencii jednotlivych symbolov.
 * @param frequencies pole frekvencii symbolov
 */
void static_tree::create_tree(uint32_t* frequencies){
	//prioritna fronta - vzdy sa vyberu uzly s najmensou frekvenciou
	priority_queue<node*, vector<node*>, compare_nodes> min_heap;
	//naplnime frontu uzlami
	for(int i = 0; i< 256; i++){
		//inicializacia a pridanie uzlu do minheapu
		node *tmp_node = new node;
		tmp_node->id = i;
		tmp_node->frequency = frequencies[i];
		tmp_node->left_node = NULL;
		tmp_node->right_node = NULL;
		min_heap.push(tmp_node);
	}


	//vybrat 2, spojit ich a push do fronty
	while(min_heap.size()>1){
		node *first = min_heap.top();
		min_heap.pop();
		node *second = min_heap.top();
		min_heap.pop();

		//novy uzol pre spojenie tych dvoch
		node *new_node = new node;
		new_node->id = 0;//jeho id neni dvolezite pre vypocet
		new_node->frequency = first->frequency + second->frequency;
		new_node->left_node = first;
		new_node->right_node = second;

		min_heap.push(new_node);
	}

    root = min_heap.top();
    min_heap.pop();
}


/**
 * Metoda rekurzivne prechodom stromu vytvori kodovu knihu.
 * Pri prechode do laveho syna prida sa do kodu 0, pri praveho 1.
 * @param codebook pole pre ulozenie kodovej knihy
 * @param tmp aktualny uzol
 * @param code kod pre dany symbol, ku ktoremu sa postupne pridavaju 0 a 1
 */
void static_tree::create_codebook(string *codebook, node *tmp, string code){
	//ak sa uz doslo na koniec
	if(tmp->left_node == NULL && tmp->right_node == NULL){
		codebook[tmp->id] = code;
		return;
	}

	if(tmp->left_node != NULL){
		create_codebook(codebook, tmp->left_node, code+"0");
	}
	if(tmp->right_node != NULL){
		create_codebook(codebook, tmp->right_node, code+"1");
	}
}


/**
 * Public metoda pre vytvorenie kodovej knihy, vola privatnu metodu pre vytvorenie.
 * @param codebook pole pre ulozenie kodovej knihy
 */
void static_tree::create_codebook(string *codebook){
	create_codebook(codebook, root, "");
}



/**
 * Metoda sluzi na dekomprimovanie suboru, postupne nacitava bajty.
 * Prechadza strom od rootu, ak narazi na list tak vrati dekodovany symbol.
 * @param infile vstupny subor
 * @param pos pozicia v subore
 * @param end flag pre indikaciu konca
 * @param compressed_size velkost vstupneho suboru
 * @return dekodovany znak
 */
uint8_t static_tree::get_character(uint8_t *infile, int& pos, bool& end, int compressed_size){
    uint8_t to_write;
    node *tmp_node = new node;
    copy_nodes(root, tmp_node);//zaciname od roota

    //prechadzame stromom az kym sa nedojde k listu
    while(tmp_node->left_node != NULL && tmp_node->right_node != NULL){
        if(bit_shift == 7){//ak sa spracoval predosli bajt tak nacitame dalsi
            c = infile[pos++];
            //kontrola ci sme v poslednom bajte
            if(pos == compressed_size-1 && padding == -2){//ak sme v poslednom-v tom ktorom je ulozeny pocet paddingu v predposlednom bajte
                padding = infile[pos++];
                if(padding == 8){
                    bit_shift = 7;
                }
                else{
                    bit_shift = 7-padding;
                }
            }
        }


        if((c >> bit_shift) & 1){//ak to bolo 1
            copy_nodes(tmp_node->right_node ,tmp_node);
            bit_shift--;
        }
        else{//ak bit je 0
            copy_nodes(tmp_node->left_node ,tmp_node);
            bit_shift--;
        }

        //ak koniec
        if(pos == compressed_size && bit_shift == -1){
            end = true;
        }

        //posledny bajt
        if(bit_shift == -1){//kontrola ci sa uz spracoval bajt
            bit_shift = 7;
        }
    }

    //sme v koncovom uzli
    to_write = tmp_node->id;
    delete tmp_node;
    return to_write;
}
