I have this beautiful code, from the internet. It takes random text and outputs Huffman code for each symbol, based on its frequency in text.
I am trying to access the final output and save it to file and do other stuff with it.
The output is in the map<char>
(for the ASCII characters) and vector<bool>
is for the codes.
Unfortunately, I think that they get destroyed after the loop is done with them.
#include <iostream>
#include <queue>
#include <map>
#include <climits> // for CHAR_BIT
#include <iterator>
#include <algorithm>
#include <fstream>
#include <stdio.h>
const int UniqueSymbols = 1 << CHAR_BIT;
const char* SampleString = "Hello StackOverflow community !";
typedef std::vector<bool> HuffCode;
typedef std::map<char, HuffCode> HuffCodeMap;
class INode
{
public:
const int f;
virtual ~INode() {}
protected:
INode(int f) : f(f) {}
};
class InternalNode : public INode
{
public:
INode *const left;
INode *const right;
InternalNode(INode* c0, INode* c1) : INode(c0->f + c1->f), left(c0),
right(c1) {}
~InternalNode()
{
delete left;
delete right;
}
};
class LeafNode : public INode
{
public:
const char c;
LeafNode(int f, char c) : INode(f), c(c) {}
};
struct NodeCmp
{
bool operator()(const INode* lhs, const INode* rhs) const { return lhs- >f > rhs->f; }
};
INode* BuildTree(const int(&frequencies)[UniqueSymbols])
{
std::priority_queue<INode*, std::vector<INode*>, NodeCmp> trees;
for (int i = 0; i < UniqueSymbols; ++i)
{
if (frequencies[i] != 0)
trees.push(new LeafNode(frequencies[i], (char)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 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);
}
}
int main()
{
// Build frequency table
int frequencies[UniqueSymbols] = { 0 };
const char* ptr = SampleString;
while (*ptr != '\0')
++frequencies[*ptr++];
INode* root = BuildTree(frequencies);
HuffCodeMap codes;
GenerateCodes(root, HuffCode(), codes);
//for (int i = 0; i < HuffCode.size(); i++) {
// HuffCode[i] = i;
// std::cout << HuffCode[i];
//}
delete root;
for (HuffCodeMap::const_iterator it = codes.begin(); it != codes.end(); ++it)
{
std::cout << it->first << " == ";
std::copy(it->second.begin(), it->second.end(),
std::ostream_iterator<bool>(std::cout));
std::cout << std::endl;
}
}
My goal is to put the map<char>
and vector<bool>
on heap and access it later in the program in full extent (meaning all the chars and all the codes).
Comments
Post a Comment