Huffman algorithm implementation in C++

Question

Lately, I have been working on this Huffman algorithm and it is finally done, though I think it is improvable due to the fact that people say you have got to use two priority queues but I ended up just using one, so maybe it is even not correctly implemented.

Code:

#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <fstream>
#include <functional>

class HuffmanCoder{
    struct TreeNode {
        char character;
        unsigned frequency, code;

        TreeNode* left, *right;

        friend bool operator>(const TreeNode& a, const TreeNode& b) {
            return a.frequency > b.frequency;
        }

        TreeNode() = default;
        TreeNode(char chara, int freq)
            : character(chara), frequency(freq), code(0u), left(nullptr), right(nullptr) {}
    } m_root;

    //recursive function that assigns codes for every char in the map passed as a reference in the parameters
    void assignCodes(std::map<char, std::string>& map, const TreeNode& rootNode, unsigned currWord, unsigned depth) {
        if (!rootNode.left && !rootNode.right) {
            std::string s;
            for (auto d = 0u; d < depth; ++d) {
                s.push_back('0' + (currWord & 1));
                currWord >>= 1;
            }
            std::reverse(s.begin(), s.end());
            map[rootNode.character] = std::move(s);
        }
        else {
            assignCodes(map, *rootNode.left, currWord << 1, depth + 1);
            assignCodes(map, *rootNode.right, (currWord << 1) | 1, depth + 1);
        }
    }

public:
    HuffmanCoder() = default;

    std::string encodeMessage(const std::string& message) {
        std::map<char, int> frequencies;
        for (const auto& character : message)
            frequencies[character]++;

        std::priority_queue<TreeNode,std::vector<TreeNode>, std::greater<>> pairs;
        for (auto&& value : frequencies)
            pairs.push({ value.first, value.second });

        //huffman algorithm
        while (pairs.size() > 1) {
            const auto pair1 = pairs.top();
            pairs.pop();
            const auto pair2 = pairs.top();
            pairs.pop();

            TreeNode temp('*', pair1.frequency + pair2.frequency);
            temp.left = new TreeNode(pair1);
            temp.right = new TreeNode(pair2);
            pairs.push(temp);
        }

        m_root = pairs.top();

        std::map<char, std::string> map;
        assignCodes(map, m_root, 0u, 0u);

        std::string ret;
        for (auto&& character : message)
            ret += map[character];      
        return std::move(ret);
    }

    std::string decodeMessage(const std::string& binaryMessage) {
        std::string decodedStr;
        auto temp = m_root;
        for (auto&& character : binaryMessage) {
            if (character == '1')
                temp = *temp.right;
            else 
                temp = *temp.left;

            if (!temp.left && !temp.right) {
                decodedStr += temp.character;
                temp = m_root;
            }
        }
        return std::move(decodedStr);
    }
};

int main() {
    std::ifstream file("text.txt");
    std::string message, line;
    while (std::getline(file, line)) 
        message += line;

    HuffmanCoder hf;
    const auto& a = hf.encodeMessage(message);
    const auto& b = hf.decodeMessage(a);

    std::cout << a << "\n\n" << b;
}

Input for the encoder:

Here's the thing. You said a "jackdaw is a crow."
Is it in the same family ? Yes.No one's arguing that.
As someone who is a scientist who studies crows, I am telling you, specifically, in science, no one calls jackdaws crows.If you want to be "specific" like you said, then you shouldn't either. They're not the same thing.
If you're saying "crow family" you're referring to the taxonomic grouping of Corvidae, which includes things from nutcrackers to blue jays to ravens.
So your reasoning for calling a jackdaw a crow is because random people "call the black ones crows?" Let's get grackles and blackbirds in there, then, too.
Also, calling someone a human or an ape ? It's not one or the other, that's not how taxonomy works.They're both. A jackdaw is a jackdaw and a member of the crow family. But that's not what you said.You said a jackdaw is a crow, which is not true unless you're okay with calling all members of the crow family crows, which means you'd call blue jays, ravens, and other birds crows, too.Which you said you don't.
It's okay to just admit you're wrong, you know ?

Output.

Characters and their binds.

Answer 1

There's really no need to do all that bit manipulation when you can simply do:

assignCodes(map, *(rootNode.left), currWord * 2, depth + 1);
assignCodes(map, *(rootNode.right), currWord * 2 + 1, depth + 1);

and let the compiler worry about those kinds of "instead of multiplying by 2, shift by 1" optimizations and have it handle it for us. That version (to me at least) is much clearer than the one you previously had.

EDIT: I would also put parenthesis around the expression that the * operator is supposed to dereference to make it clearer as I've done above. A similar syntactical fix needs to be done in decodeMessage() too.

I think you're trying to force move semantics in areas where they aren't necessary. An example is the code snippet below:

std::string ret;
for (auto&& character : message)
    ret += map[character];
return std::move(ret);

There is no reason to have an r-value reference (and consequently moving characters out of the message string) when you're updating the ret string. You're passing in message by const reference so you should not be modifying the message in the function. This loop really should be:

std::string ret;
ret.reserve(message.size()); // reserve memory up front to avoid  repeated allocations
for (const auto& c : message) {
    ret += map[c];
}

This also applies for the similar loop in decodeMessage().

Having std::move to move the return value out of the function may inhibit the compiler from performing RVO (which is even faster than move assignment). Just return the value normally and only add the std::move when you have evidence that the return value is returned by a copy.

There is no need to have this line in the code:

 HuffmanCoder() = default;

The compiler generates the default constructor for you so there's no reason to declare it here.

In your assignCodes function, you're creating a binary representation of the currWord number here:

std::string s;
for (auto d = 0u; d < depth; ++d) {
     s.push_back('0' + (currWord & 1));
     currWord >>= 1;
}
std::reverse(s.begin(), s.end());

I would be inclined to have this as a private member method to do this for me:

std::string numToBin(unsigned num, unsigned depth)
{
    std::string s;
    s.reserve(depth);
    for (unsigned i = 0; i < depth; ++i, num >>= 1){
        s.push_back('0' + (num & 1));
    }
    std::reverse(s.begin(), s.end());
    return s;
}

Now I can just simply call the function inside of assignCodes():

map[rootNode.character] = numToBin(currWord, depth);

You can avoid having to do a string reverse by doing this:

std::string numToBin(unsigned num, unsigned depth)
{
    std::string s;
    s.reserve(depth);
    unsigned bits = sizeof(unsigned) * 8 - 1;
    for (unsigned i = 0, shift = bits; i < depth && shift <= bits; 
                  ++i, --shift){
        s.push_back('0' + ((num & (1 << shift)) >> shift));
    }
    return s;
}

A similar transformation can be done for this code inside of encodeMessage():

std::map<char, int> frequencies;
for (const auto& character : message)
    frequencies[character]++;

std::priority_queue<TreeNode,std::vector<TreeNode>, std::greater<>> pairs;
for (auto&& value : frequencies)
    pairs.push({ value.first, value.second });

Turn that into a function that returns the priority_queue:

std::priority_queue<TreeNode,std::vector<TreeNode>, std::greater<>>
getPairs(const std::string& message)
{
    std::map<char, int> frequencies;
    for (const auto& c : message)
        ++frequencies[c];

    std::priority_queue<TreeNode,std::vector<TreeNode>, std::greater<>> pairs;
    for (const auto& value : frequencies)
        pairs.push(value.first, value.second);

    return pairs;
}

Finally, in your TreeNode() initializer list, you're initializing frequency (which is an unsigned type) using a signed value. If you don't need negative numbers (and you don't), then use only unsigned numbers:

TreeNode(char chara, unsigned freq)
            : character(chara), frequency(freq), code(0), left(nullptr), right(nullptr)

EDIT:

I can't believe I failed to mention this:

Your class dynamically creates Nodes using new but I don't see delete anywhere; as a result, your class will leak all that memory. Use std::unique_ptr to avoid having to deal with memory management issues.