huffmanEncoding/huffmanTree.cpp at main · 00ryanwelzel/huffmanEncoding · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include "huffmanTree.h"
#include "huffmanNode.h"

using namespace std;


huffmanTree::huffmanTree(unordered_map<char, int>& f, unordered_map<char, string>& c) : frequencies(f), codes(c) {}

struct lesserCompare{
    bool operator()(huffmanNode* a, huffmanNode* b) const {
        return a->frequency > b->frequency;
    }
};

void huffmanTree::buildTree(const string& text){
    priority_queue<huffmanNode*, vector<huffmanNode*>, lesserCompare> queue;

    for(char c : text) frequencies[c]++;
    for(auto pair : frequencies) queue.push(new huffmanNode(pair.first, pair.second));

    while(queue.size() > 1){
        huffmanNode* left = queue.top(); queue.pop();
        huffmanNode* right = queue.top(); queue.pop();

        int freqTotal = left->frequency + right->frequency;

        huffmanNode* comboNode = new huffmanNode('\0', freqTotal);
        comboNode->left = left;
        comboNode->right = right;

        queue.push(comboNode);
    }

    huffmanNode* root = queue.top();

    generateCodes(root, "");

    return;
}

void huffmanTree::generateCodes(huffmanNode* root, const string& code){
    if(!root) return;

    if(!root->left && !root->right){
        codes[root->c] = code;
    }

    generateCodes(root->left, code + "0");
    generateCodes(root->right, code + "1");

}

void huffmanTree::printCodes(){
    cout << "All Huffman codes:\n";

    for(auto pair : codes) cout << pair.first << ": " << pair.second << endl;
    return;
}

void huffmanTree::printEncoded(const string& text){
    string encoded = "";

    for(char c : text){
        encoded += codes[c];
    }

    cout << "Encoded string:\n" << encoded << endl;
}