Skel for Huffman coding

huffman.cpp

#include <iostream>
#include <fstream>
#include <map>

//#define FLAG_USE_STRUCT

namespace algorithm
{

class Huffman
{
public:
    typedef char            SymbolType;
    typedef size_t          SizeType;

    struct Run
    {
        /** Meta-symbol */
        const   SymbolType  symbol;
        const   SizeType    run_len;

        /** Freq */
                SizeType    freq;

        Run(const SymbolType & symbol, const SizeType & run_len, const SizeType & freq = 0)
        : symbol(symbol)
        , run_len(run_len)
        , freq(freq)
        { }
    };

    typedef
#ifdef FLAG_USE_STRUCT
        Run
#else
        std::pair<const SymbolType, const SizeType>
#endif
        MetaSymbolType;

private:
    std::map<MetaSymbolType, SizeType> runs_;

public:
    SizeType
    CollectRuns(std::ifstream & f)
    {
        const SizeType symbol_size = sizeof(SymbolType);

        SymbolType  symbol;
        SymbolType  next_symbol;
        SizeType    symbol_count = 1;

        if(! f.eof())
        {
            f.read(&symbol, symbol_size);

            while(! f.eof())
            {
                f.read(&next_symbol, symbol_size);

                if(symbol == next_symbol)
                    ++symbol_count;
                else
                {
#ifdef FLAG_USE_STRUCT
                    Run meta_symbol = Run(symbol, symbol_count);
#else
                    MetaSymbolType meta_symbol = std::make_pair(symbol, symbol_count);
#endif

                    if(runs_.find(meta_symbol) == runs_.end())
                        runs_.insert(std::make_pair(meta_symbol, 1));
                    else
                        ++runs_.at(meta_symbol);

                    symbol_count = 1;
                }

                symbol = next_symbol;
            }

#ifdef FLAG_USE_STRUCT
            Run meta_symbol = Run(symbol, symbol_count);
#else
            MetaSymbolType meta_symbol = std::make_pair(symbol, symbol_count);
#endif

            if(runs_.find(meta_symbol) == runs_.end())
                runs_.insert(std::make_pair(meta_symbol, 1));
            else
                ++runs_.at(meta_symbol);
        }
    }

    void
    PrintAllRuns(FILE * f = stdout)
    {
        fprintf(f, "SYM_HEX  LEN FREQ\n");

        for(auto run : runs_)
#ifdef FLAG_USE_STRUCT
            fprintf(f, "%2x  %2d  %3d\n", (unsigned char)run.first.symbol, run.first.run_len, run.second);
#else
            fprintf(f, "%2x  %2d  %3d\n", (unsigned char)run.first.first, run.first.second, run.second);
#endif
    }
};

} /** ns: algorithm */

using namespace algorithm;

bool
operator==
(const Huffman::Run & lhs, const Huffman::Run & rhs)
{ return (lhs.symbol == rhs.symbol && lhs.run_len == rhs.run_len); }

bool
operator<
(const Huffman::Run & lhs, const Huffman::Run & rhs)
{
    return true;
}

int
main(const int argc, const char * argv[])
{
    std::string file_name = argv[1];

    std::ifstream file(file_name, std::ios::binary);
    if(! file.is_open())
    {
        fprintf(stderr, "Error: File '%s' not found.\n", file_name.c_str());
        return -1;
    }

    Huffman huffman;
    huffman.CollectRuns(file);
    huffman.PrintAllRuns();

    return 0;
}