#include <iostream>
#include <queue>
#include <vector>
#include <string>

using namespace std;

struct Node {
    char ch;
    int freq;
    Node *left, *right;

    Node(char c, int f, Node* l = nullptr, Node* r = nullptr)
        : ch(c), freq(f), left(l), right(r) {}
};

struct Compare {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

void buildCodes(Node* root, string code, vector<pair<char,string>>& codes) {
    if (!root) return;

    if (!root->left && !root->right)
        codes.push_back({root->ch, code});

    buildCodes(root->left, code + "0", codes);
    buildCodes(root->right, code + "1", codes);
}

string encode(string text, vector<pair<char,string>>& codes) {
    string res;

    for (char c : text)
        for (auto &p : codes)
            if (p.first == c)
                res += p.second;

    return res;
}

string decode(string s, Node* root) {
    string res;
    Node* cur = root;

    for (char b : s) {
        cur = (b == '0') ? cur->left : cur->right;

        if (!cur->left && !cur->right) {
            res += cur->ch;
            cur = root;
        }
    }
    return res;
}

void printDOT(Node* root) {
    if (!root) return;

    if (root->left) {
        cout << "\"" << root->ch << root->freq << "\" -- \""
             << root->left->ch << root->left->freq << "\"\n";
        printDOT(root->left);
    }

    if (root->right) {
        cout << "\"" << root->ch << root->freq << "\" -- \""
             << root->right->ch << root->right->freq << "\"\n";
        printDOT(root->right);
    }
}

int main() {

    string text = "cheprazovivan";

    vector<Node*> nodes;

    for (char c : text) {
        bool found = false;

        for (auto &n : nodes) {
            if (n->ch == c) {
                n->freq++;
                found = true;
                break;
            }
        }

        if (!found)
            nodes.push_back(new Node(c, 1));
    }

    priority_queue<Node*, vector<Node*>, Compare> pq;

    for (auto n : nodes)
        pq.push(n);

    while (pq.size() > 1) {
        Node* a = pq.top(); pq.pop();
        Node* b = pq.top(); pq.pop();

        pq.push(new Node('\0', a->freq + b->freq, a, b));
    }

    Node* root = pq.top();

    vector<pair<char,string>> codes;
    buildCodes(root, "", codes);

    cout << "Коди Хаффмана:\n";
    for (auto &p : codes)
        cout << p.first << " : " << p.second << endl;

    string enc = encode(text, codes);
    cout << "\nENCODED:\n" << enc << endl;

    cout << "\nDECODED:\n" << decode(enc, root) << endl;

    cout << "\nDOT:\ngraph G {\n";
    printDOT(root);
    cout << "}\n";

    return 0;
}