-
Notifications
You must be signed in to change notification settings - Fork 1
/
Huffman.cpp
102 lines (79 loc) · 2.41 KB
/
Huffman.cpp
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include "Huffman.h"
Huffman::Huffman(){
}
INode* Huffman::BuildTree(const int (&frequencies)[constants::HUFFMAN_RANGE])
{
std::priority_queue<INode*, std::vector<INode*>, NodeCmp> trees;
for (int i = 0; i < constants::HUFFMAN_RANGE; ++i)
{
if(frequencies[i] != 0)
trees.push(new LeafNode(frequencies[i], (uint16_t)i));
}
while (trees.size() > 1)
{
INode* childR = trees.top();
trees.pop();
INode* childL = trees.top();
trees.pop();
INode* parent = new InternalNode(childR, childL);
trees.push(parent);
}
return trees.top();
}
void Huffman::GenerateCodes(const INode* node, const HuffCode& prefix, HuffCodeMap& outCodes)
{
if (const LeafNode* lf = dynamic_cast<const LeafNode*>(node))
{
outCodes[lf->c] = prefix;
}
else if (const InternalNode* in = dynamic_cast<const InternalNode*>(node))
{
HuffCode leftPrefix = prefix;
leftPrefix.push_back(false);
GenerateCodes(in->left, leftPrefix, outCodes);
HuffCode rightPrefix = prefix;
rightPrefix.push_back(true);
GenerateCodes(in->right, rightPrefix, outCodes);
}
}
void Huffman::WriteCodesToFile(const char *filename, const HuffCodeMap& codes){
std::ofstream os(filename);
for(HuffCodeMap::const_iterator it = codes.begin(); it != codes.end(); it++){
os << it->first << " ";
std::copy(it->second.begin(), it->second.end(),
std::ostream_iterator<bool>(os));
os << std::endl;
}
}
void Huffman::CodesFromFile(const char *filename, HuffCodeMap& outCodes){
std::ifstream is(filename);
std::string line;
if (!is.good()) {
std::cerr << "can not open file " << filename << " for reading of Huffman code table" << std::endl;
return;
}
while(!is.eof()){
std::vector<bool> codes;
std::getline(is, line);
try{
uint16_t val = std::stoi(line.substr(0, line.find(" ")));
std::string code = line.substr(line.find(" ")+1);
for(char& c : code){
codes.push_back(c == '1');
outCodes[val] = codes;
}
} catch(const std::invalid_argument& ia){
}
}
}
void Huffman::CreateTree(const std::vector<uint16_t>& words, HuffCodeMap& outCodes){
int frequencies[constants::HUFFMAN_RANGE] = {0};
for(int i = 0; i < words.size(); i++){
uint16_t ptr = words.at(i);
if(ptr < constants::HUFFMAN_RANGE)
++frequencies[ptr];
}
INode* root = BuildTree(frequencies);
GenerateCodes(root, HuffCode(), outCodes);
delete root;
}