Huffman decoding

gistfile1.cpp

#include <memory>
#include <queue>
#include <string>
#include <utility>
#include <cassert>
#include <iostream>
#include <fstream>

class huffman {
    public:
        void add_letter(char c, int f) { queue.emplace(new node(c, f)); }
        void decompress(std::istream &input, std::ostream &output);
    private:
        struct node {
            std::unique_ptr<node> right, left;
            int frequency;
            char letter;
            node(char c = 0, int f = 0) : frequency(f), letter(c) {};
        };
        void build_tree();
        friend bool operator>(const std::unique_ptr<node> &lhs, const std::unique_ptr<node> &rhs) {
            return lhs->frequency > rhs->frequency;
        };
        std::priority_queue<std::unique_ptr<node>, std::vector<std::unique_ptr<node>>, std::greater<std::unique_ptr<node>>> queue;
};

void huffman::build_tree()
{
    while(queue.size() > 1) {
        std::unique_ptr<node> n(new node);
        n->left = std::move(const_cast<std::unique_ptr<node> &>(queue.top()));
        queue.pop();
        n->right = std::move(const_cast<std::unique_ptr<node> &>(queue.top()));
        queue.pop();
        n->frequency = n->left->frequency + n->right->frequency;
        queue.push(std::move(n));
    }
}

void huffman::decompress(std::istream &input, std::ostream &output)
{
    if(queue.size() > 1)
        build_tree();

    assert(!queue.empty());
    node const *cur = queue.top().get();    // non-owning pointer
    char c;
    while(input.get(c)) {
        if(c == '0')
            assert(cur = cur->left.get());
        else if(c == '1')
            assert(cur = cur->right.get());
        else
            continue;

        // is this a leaf node?
        if(cur->letter) {
            output << cur->letter;
            cur = queue.top().get();
        }
    }
}

int main()
{
    huffman huff;
    std::ifstream frequencytable("a3-1-check.txt");
    assert(frequencytable);

    int numletters;
    frequencytable >> numletters;
    for(int i = 0; i < numletters; i++) {
        std::string letter;
        int freq;
        frequencytable >> letter >> freq;
        huff.add_letter(letter[0], freq);
    }

    std::ifstream compressedfile("a3-2.txt");
    assert(compressedfile);
    
    huff.decompress(compressedfile, std::cout);
    std::cout << std::endl;
}