#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>

using namespace std;

// Structura pentru nodul arborelui Huffman
struct Node {
    char data;
    int frequency;
    Node* left;
    Node* right;

    Node(char data, int frequency) {
        this->data = data;
        this->frequency = frequency;
        left = right = nullptr;
    }

    // Funcție de supraincarcare a operatorului "<" pentru a permite sortarea în funcție de frecvență
    bool operator<(const Node& other) const {
        return frequency > other.frequency;
    }
};

// Funcție pentru construirea arborelui Huffman
Node* buildHuffmanTree(const unordered_map<char, int>& frequencyMap) {
    // Folosim o coadă de prioritate pentru a obține mereu cele două noduri cu frecvențe minime
    priority_queue<Node*> pq;

    // Creăm un nod pentru fiecare caracter și îl adăugăm în coadă
    for (const auto& pair : frequencyMap) {
        pq.push(new Node(pair.first, pair.second));
    }

    // Construim arborele Huffman prin unirea repetată a celor două noduri cu frecvențe minime
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();

        Node* parent = new Node('$', left->frequency + right->frequency);
        parent->left = left;
        parent->right = right;

        pq.push(parent);
    }

    // Returnăm rădăcina arborelui Huffman
    return pq.top();
}

// Funcție pentru construirea codurilor Huffman pentru fiecare caracter
void buildHuffmanCodes(Node* root, const string& code, unordered_map<char, string>& huffmanCodes) {
    if (root == nullptr) {
        return;
    }

    // Dacă nodul este o frunză, adăugăm codul Huffman pentru caracterul corespunzător în map
    if (!root->left && !root->right) {
        huffmanCodes[root->data] = code;
    }

    // Recursiv construim codurile pentru subarborii stângi și drepti
    buildHuffmanCodes(root->left, code + "0", huffmanCodes);
    buildHuffmanCodes(root->right, code + "1", huffmanCodes);
}

// Funcție pentru codificarea textului folosind codurile Huffman
string encode(const string& text, const unordered_map<char, string>& huffmanCodes) {
    string encodedText = "";
    for (char c : text) {
        encodedText += huffmanCodes.at(c);
    }
    return encodedText;
}

// Funcție pentru decodificarea textului folosind arborele Huffman
string decode(const string& encodedText, Node* root) {
    string decodedText = "";
    Node* current = root;

    for (char bit : encodedText) {
        if (bit == '0') {
            current = current->left;
        } else {
            current = current->right;
        }

        if (current->left == nullptr && current->right == nullptr) {
            decodedText += current->data;
            current = root;
        }
    }

    return decodedText;
}

int main() {
    string text = "Hello, World!";
    
    // Calculăm frecvența aparițiilor fiecărui caracter în text
    unordered_map<char, int> frequencyMap;
    for (char c : text) {
        frequencyMap[c]++;
    }

    // Construim arborele Huffman
    Node* root = buildHuffmanTree(frequencyMap);

    // Construim codurile Huffman pentru fiecare caracter
    unordered_map<char, string> huffmanCodes;
    buildHuffmanCodes(root, "", huffmanCodes);

    // Codificăm textul
    string encodedText = encode(text, huffmanCodes);

    // Decodificăm textul
    string decodedText = decode(encodedText, root);

    // Afișăm rezultatele
    cout << "Textul original: " << text << endl;
    cout << "Textul codat: " << encodedText << endl;
    cout << "Textul decodat: " << decodedText << endl;

    return 0;
}