4
\$\begingroup\$

I have this Huffman compressor that can compress both text and binary files by treating each as binary files. (By the way, it is fully compatible with this Java implementation.) See what I have:

Code

main.cpp

#include "bit_string.hpp"
#include "byte_counts.hpp"
#include "huffman_decoder.hpp"
#include "huffman_deserializer.hpp"
#include "huffman_encoder.hpp"
#include "huffman_serializer.hpp"
#include "huffman_tree.hpp"

#include <algorithm>
#include <cstdint>
#include <fstream>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <random>
#include <set>
#include <stdexcept>
#include <string>

using std::cout;
using std::cerr;
using std::endl;

#define ASSERT(C) if (!(C)) report(#C, __FILE__, __LINE__)

void report(const char* condition, const char* file, size_t line)
{
    cerr << "The condition \""
         << condition
         << "\" failed in file \""
         << file
         << "\", line: "
         << line
         << "."
         << endl;
    exit(1);
}

static std::string ENCODE_FLAG_SHORT  = "-e";
static std::string ENCODE_FLAG_LONG   = "--encode";
static std::string DECODE_FLAG_SHORT  = "-d";
static std::string DECODE_FLAG_LONG   = "--decode";
static std::string HELP_FLAG_SHORT    = "-h";
static std::string HELP_FLAG_LONG     = "--help";
static std::string VERSION_FLAG_SHORT = "-v";
static std::string VERSION_FLAG_LONG  = "--version";
static std::string ENCODED_FILE_EXTENSION = "het";

static std::string BAD_CMD_FORMAT = "Bad command line format.";

void test_append_bit();
void test_bit_string();
void test_all();

void exec(int argc, const char *argv[]);
void print_help_message(std::string& image_name);
void print_version();
std::string get_base_name(const char *arg1);

void file_write(std::string& file_name, std::vector<int8_t>& data);
std::vector<int8_t> file_read(std::string& file_name);

int main(int argc, const char * argv[])
{
    try
    {
        exec(argc, argv);
    }
    catch (std::runtime_error& error)
    {
        cerr << "Error: " << error.what() << endl;
        return 1;
    }

    //test_all();
    return 0;
}

void file_write(std::string& file_name, std::vector<int8_t>& data)
{
    std::ofstream file(file_name, std::ios::out | std::ofstream::binary);
    std::size_t size = data.size();
    char* byte_data = new char[size];
    std::copy(data.begin(), data.end(), byte_data);
    file.write(byte_data, size);
    file.close();
}

std::vector<int8_t> file_read(std::string& file_name)
{
    std::ifstream file(file_name, std::ios::in | std::ifstream::binary);
    std::vector<int8_t> ret;
    std::filebuf* pbuf = file.rdbuf();
    std::size_t size = pbuf->pubseekoff(0, file.end, file.in);

    pbuf->pubseekpos(0, file.in);
    char* buffer = new char[size];
    pbuf->sgetn(buffer, size);

    for (std::size_t i = 0; i != size; ++i)
    {
        ret.push_back((int8_t) buffer[i]);
    }

    delete[] buffer;
    file.close();
    return std::move(ret);
}

void do_decode(int argc, const char * argv[])
{
    if (argc != 4)
    {
        throw std::runtime_error{BAD_CMD_FORMAT};
    }

    std::string flag = argv[1];

    if (flag != DECODE_FLAG_SHORT and flag != DECODE_FLAG_LONG)
    {
        throw std::runtime_error{BAD_CMD_FORMAT};
    }

    std::string source_file = argv[2];
    std::string target_file = argv[3];

    std::vector<int8_t> encoded_data = file_read(source_file);
    huffman_deserializer deserializer;
    huffman_deserializer::result decode_result =
        deserializer.deserialize(encoded_data);

    huffman_tree decoder_tree(decode_result.count_map);
    huffman_decoder decoder;
    std::vector<int8_t> text = decoder.decode(decoder_tree,
                                              decode_result.encoded_text);
    file_write(target_file, text);
}

void do_encode(int argc, const char * argv[])
{
    if (argc != 3)
    {
        throw std::runtime_error{BAD_CMD_FORMAT};
    }

    std::string flag = argv[1];

    if (flag != ENCODE_FLAG_SHORT and flag != ENCODE_FLAG_LONG)
    {
        throw std::runtime_error{BAD_CMD_FORMAT};
    }

    std::string source_file = argv[2];
    std::vector<int8_t> text = file_read(source_file);
    std::map<int8_t, uint32_t> count_map = compute_byte_counts(text);

    huffman_tree tree(count_map);
    std::map<int8_t, bit_string> encoder_map = tree.infer_encoder_map();

    huffman_encoder encoder;
    bit_string encoded_text = encoder.encode(encoder_map, text);

    huffman_serializer serializer;
    std::vector<int8_t> encoded_data = serializer.serialize(count_map,
                                                            encoded_text);
    std::string out_file_name = source_file;
    out_file_name += ".";
    out_file_name += ENCODED_FILE_EXTENSION;

    file_write(out_file_name, encoded_data);
}

void exec(int argc, const char *argv[])
{
    std::set<std::string> command_line_argument_set;
    std::for_each(argv + 1,
                  argv + argc,
                  [&command_line_argument_set](const char *s) {
                      command_line_argument_set.insert(std::string{s});});

    std::string image_name = get_base_name(argv[0]);
    auto args_end = command_line_argument_set.end();

    if (command_line_argument_set.find(HELP_FLAG_SHORT) != args_end ||
        command_line_argument_set.find(HELP_FLAG_LONG)  != args_end)
    {
        print_help_message(image_name);
        exit(0);
    }

    if (command_line_argument_set.find(VERSION_FLAG_SHORT) != args_end ||
        command_line_argument_set.find(VERSION_FLAG_LONG)  != args_end)
    {
        print_version();
        exit(0);
    }

    if (command_line_argument_set.find(DECODE_FLAG_SHORT) != args_end &&
        command_line_argument_set.find(DECODE_FLAG_LONG)  != args_end)
    {
        print_help_message(image_name);
        exit(1);
    }

    if (command_line_argument_set.find(ENCODE_FLAG_SHORT) != args_end &&
        command_line_argument_set.find(ENCODE_FLAG_LONG)  != args_end)
    {
        print_help_message(image_name);
        exit(0);
    }

    bool decode = false;
    bool encode = false;

    if (command_line_argument_set.find(DECODE_FLAG_SHORT) != args_end ||
        command_line_argument_set.find(DECODE_FLAG_LONG)  != args_end)
    {
        decode = true;
    }

    if (command_line_argument_set.find(ENCODE_FLAG_SHORT) != args_end ||
        command_line_argument_set.find(ENCODE_FLAG_LONG)  != args_end)
    {
        encode = true;
    }

    if ((!decode and !encode) or (decode and encode))
    {
        print_help_message(image_name);
        exit(0);
    }

    if (decode)
    {
        do_decode(argc, argv);
    }
    else
    {
        do_encode(argc, argv);
    }
}

std::string get_base_name(const char *cmd_line)
{
    std::string tmp = cmd_line;

    if (tmp.empty())
    {
        throw std::runtime_error{"Empty base name string."};
    }

    char file_separator;

#ifdef _WIN32
    file_separator = '\\';
#else
    file_separator = '/';
#endif

    int index = (int) tmp.length() - 1;

    for (; index >= 0; --index)
    {
        if (tmp[index] == file_separator)
        {
            std::string ret;

            while (++index < tmp.length())
            {
                ret += tmp[index];
            }

            return ret;
        }
    }

    return tmp;
}

std::string get_indent(size_t len)
{
    std::string ret;

    for (size_t i = 0; i != len; ++i)
    {
        ret += ' ';
    }

    return ret;
}

void print_help_message(std::string& process_image_name)
{
    std::string preamble = "usage: " + process_image_name + " ";
    size_t preamble_length = preamble.length();
    std::string indent = get_indent(preamble_length);
    cout << preamble;

    cout << "[" << HELP_FLAG_SHORT << " | " << HELP_FLAG_LONG << "]\n";
    cout << indent
         << "[" << VERSION_FLAG_SHORT << " | " << VERSION_FLAG_LONG << "]\n";
    cout << indent
         << "[" << ENCODE_FLAG_SHORT << " | " << ENCODE_FLAG_LONG
         << "] FILE\n";
    cout << indent
         << "[" << DECODE_FLAG_SHORT << " | " << DECODE_FLAG_LONG
         << "] FILE_FROM FILE_TO\n";

    cout << "Where:" << endl;

    cout << HELP_FLAG_SHORT << ", " << HELP_FLAG_LONG
         << "    Print this message and exit.\n";
    cout << VERSION_FLAG_SHORT << ", " << VERSION_FLAG_LONG
         << " Print the version info and exit.\n";
    cout << ENCODE_FLAG_SHORT << ", " << ENCODE_FLAG_LONG
         << "  Encode the text from file.\n";
    cout << DECODE_FLAG_SHORT << ", " << DECODE_FLAG_LONG
         << "  Decode the text from file.\n";
}

void print_version()
{
    cout << "Huffman compressor C++ tool, version 1.6 (Nov 29, 2016)" << endl;
    cout << "By Rodion \"rodde\" Efremov" << endl;
}

void test_append_bit()
{
    bit_string b;

    ASSERT(b.length() == 0);

    for (int i = 0; i < 100; ++i)
    {
        ASSERT(b.length() == i);
        b.append_bit(false);
    }

    for (int i = 0; i < 30; ++i)
    {
        ASSERT(b.length() == 100 + i);
        b.append_bit(true);
    }

    ASSERT(b.length() == 130);

    for (int i = 0; i < 100; ++i)
    {
        ASSERT(b.read_bit(i) == false);
    }

    for (int i = 100; i < 130; ++i)
    {
        ASSERT(b.read_bit(i) == true);
    }
}

void test_append_bits_from()
{
    bit_string b;
    bit_string c;

    for (int i = 0; i < 200; ++i)
    {
        b.append_bit(false);
    }

    for (int i = 0; i < 100; ++i)
    {
        c.append_bit(true);
    }

    ASSERT(b.length() == 200);
    ASSERT(c.length() == 100);

    b.append_bits_from(c);

    ASSERT(b.length() == 300);
    ASSERT(c.length() == 100);

    for (int i = 0; i < 200; ++i)
    {
        ASSERT(b.read_bit(i) == false);
    }

    for (int i = 200; i < 300; ++i)
    {
        ASSERT(b.read_bit(i) == true);
    }
}

void test_read_bit()
{
    bit_string b;
    b.append_bit(true);
    b.append_bit(false);
    b.append_bit(false);
    b.append_bit(true);
    b.append_bit(false);

    ASSERT(b.length() == 5);

    ASSERT(b.read_bit(0) == true);
    ASSERT(b.read_bit(3) == true);

    ASSERT(b.read_bit(1) == false);
    ASSERT(b.read_bit(2) == false);
    ASSERT(b.read_bit(4) == false);
}

void test_read_bit_bad_index_throws()
{
    bit_string b;
    b.append_bit(true);

    try
    {
        b.read_bit(1); ASSERT(false);
    }
    catch (std::runtime_error& err)
    {

    }

    try
    {
        b.read_bit(-1); ASSERT(false);
    }
    catch (std::runtime_error& err)
    {

    }
}

void test_read_bit_throws_on_empty_string()
{
    bit_string b;

    try
    {
        b.read_bit(0); ASSERT(false);
    }
    catch (std::runtime_error& err)
    {

    }
}

void test_remove_last_bit()
{
    bit_string b;

    b.append_bit(true);
    b.append_bit(true);
    b.append_bit(false);
    b.append_bit(true);
    b.append_bit(false);

    ASSERT(b.read_bit(0) == true);
    ASSERT(b.read_bit(1) == true);
    ASSERT(b.read_bit(2) == false);
    ASSERT(b.read_bit(3) == true);
    ASSERT(b.read_bit(4) == false);

    for (int i = 5; i > 0; --i)
    {
        ASSERT(b.length() == i);
        b.remove_last_bit();
        ASSERT(b.length() == i - 1);
    }
}

void test_remove_last_bit_throws_on_empty_string()
{
    bit_string b;

    try
    {
        b.remove_last_bit(); ASSERT(false);
    }
    catch (std::runtime_error& err)
    {

    }
}

void test_bit_string_clear()
{
    bit_string b;

    for (int i = 0; i < 1000; ++i)
    {
        ASSERT(b.length() == i);
        b.append_bit(true);
        ASSERT(b.length() == i + 1);
    }

    b.clear();
    ASSERT(b.length() == 0);
}

void test_bit_string_get_number_of_occupied_bytes()
{
    bit_string b;
    ASSERT(0 == b.get_number_of_occupied_bytes());

    for (int i = 0; i < 100; ++i)
    {
        ASSERT(b.get_number_of_occupied_bytes() == i);

        for (int j = 0; j < 8; ++j)
        {
            b.append_bit(true);
            ASSERT(i + 1 == b.get_number_of_occupied_bytes());
        }

        ASSERT(i + 1 == b.get_number_of_occupied_bytes());
    }
}

void test_bit_string_to_byte_array()
{
    bit_string b;

    for (int i = 0; i < 40; ++i)
    {
        b.append_bit(i % 2 == 1);
    }

    for (int i = 0; i < 80; ++i)
    {
        b.append_bit(i % 2 == 0);
    }

    std::vector<int8_t> bytes{b.to_byte_array()};

    for (int i = 0; i < 5; ++i)
    {
        ASSERT(0xaa == (uint8_t) bytes[i]);
    }

    for (int i = 5; i < 15; ++i)
    {
        ASSERT(0x55 == bytes[i]);
    }
}

void test_bit_string()
{
    test_append_bit();
    test_append_bits_from();
    test_read_bit();
    test_read_bit_bad_index_throws();
    test_read_bit_throws_on_empty_string();
    test_remove_last_bit();
    test_remove_last_bit_throws_on_empty_string();
    test_bit_string_clear();
    test_bit_string_get_number_of_occupied_bytes();
    test_bit_string_to_byte_array();
}

std::vector<int8_t> random_text()
{
    std::random_device rd;
    std::default_random_engine engine(rd());
    std::uniform_int_distribution<size_t> uniform_dist_length(0, 10 * 100);
    std::uniform_int_distribution<int8_t>
        uniform_dist(std::numeric_limits<int8_t>::min(),
                     std::numeric_limits<int8_t>::max());

    size_t len = uniform_dist_length(engine);
    std::vector<int8_t> ret;

    for (size_t i = 0; i != len; ++i)
    {
        ret.push_back(uniform_dist(engine));
    }

    return ret;
}

void test_brute_force()
{
    std::vector<int8_t> text = random_text();
    std::map<int8_t, uint32_t> count_map = compute_byte_counts(text);

    huffman_tree tree(count_map);

    std::map<int8_t, bit_string> encoder_map = tree.infer_encoder_map();

    huffman_encoder encoder;

    bit_string text_bit_string = encoder.encode(encoder_map, text);

    huffman_serializer serializer;

    std::vector<int8_t> encoded_data = serializer.serialize(count_map,
                                                            text_bit_string);
    huffman_deserializer deserializer;
    huffman_deserializer::result hdr = deserializer.deserialize(encoded_data);

    huffman_tree decoder_tree(hdr.count_map);
    huffman_decoder decoder;

    ASSERT(hdr.count_map.size() == count_map.size());

    for (auto& e : hdr.count_map)
    {
        auto iter = count_map.find(e.first);
        ASSERT(iter != count_map.end());
        ASSERT(e.second == iter->second);
    }

    ASSERT(text_bit_string.length() == hdr.encoded_text.length());

    std::vector<int8_t> recovered_text = decoder.decode(decoder_tree,
                                                        hdr.encoded_text);
    ASSERT(text.size() == recovered_text.size());
    ASSERT(std::equal(text.begin(), text.end(), recovered_text.begin()));
}

void test_simple_algorithm()
{
    std::string text = "hello world";
    std::vector<int8_t> text_vector;

    for (char c : text)
    {
        text_vector.push_back((int8_t) c);
    }

    std::map<int8_t, uint32_t> count_map = compute_byte_counts(text_vector);

    huffman_tree tree(count_map);

    std::map<int8_t, bit_string> encoder_map = tree.infer_encoder_map();

    huffman_encoder encoder;

    bit_string text_bit_string = encoder.encode(encoder_map, text_vector);

    huffman_serializer serializer;

    std::vector<int8_t> encoded_text = serializer.serialize(count_map,
                                                            text_bit_string);

    huffman_deserializer deserializer;

    huffman_deserializer::result hdr = deserializer.deserialize(encoded_text);

    huffman_tree decoder_tree(hdr.count_map);
    huffman_decoder decoder;

    std::vector<int8_t> recovered_text = decoder.decode(decoder_tree,
                                                        hdr.encoded_text);
    ASSERT(text.size() == recovered_text.size());
    ASSERT(std::equal(text.begin(), text.end(), recovered_text.begin()));
}

void test_one_byte_text()
{
    std::vector<int8_t> text = { 0x01, 0x01 };
    std::map<int8_t, uint32_t> count_map = compute_byte_counts(text);
    huffman_tree tree(count_map);
    std::map<int8_t, bit_string> encoder_map = tree.infer_encoder_map();
    huffman_encoder encoder;
    bit_string text_bit_string = encoder.encode(encoder_map, text);
    huffman_serializer serializer;
    std::vector<int8_t> serialized_text = serializer.serialize(count_map,
                                                               text_bit_string);
    huffman_deserializer deserializer;
    huffman_deserializer::result hdr =
        deserializer.deserialize(serialized_text);

    huffman_tree decoder_tree(hdr.count_map);

    huffman_decoder decoder;

    std::vector<int8_t> recovered_text = decoder.decode(decoder_tree,
                                                        hdr.encoded_text);
    ASSERT(recovered_text.size() == 2);
    ASSERT(recovered_text[0] = 0x1);
    ASSERT(recovered_text[1] = 0x1);
}

void test_algorithms()
{
    test_simple_algorithm();
    test_one_byte_text();

    for (int iter = 0; iter != 100; ++iter)
    {
        test_brute_force();
    }
}

void test_all()
{
    test_bit_string();
    test_algorithms();
    cout << "All tests passed." << endl;
}

bit_string.hpp

#pragma once

#ifndef CODERODDE_BIT_STRING
#define CODERODDE_BIT_STRING

#include <cstdint>
#include <iostream>
#include <vector>

class bit_string {
public:

    constexpr static size_t DEFAULT_NUMBER_OF_UINT64S = 2;
    constexpr static size_t MODULO_MASK = 0x3F;
    constexpr static size_t BITS_PER_UINT64 = 64;

    /**********************************
    * Constructs an empty bit string. *
    **********************************/
    explicit bit_string();

    /***********************************
    * Copy constructs this bit string. *
    ***********************************/
    explicit bit_string(const bit_string& to_copy);

    /********************************
    * The move assignment operator. *
    ********************************/
    bit_string& operator=(bit_string&& other);

    /************************
    * The move constructor. *
    ************************/
    bit_string(bit_string&& other);

    /************************************
    * Appends 'bit' to this bit string. *
    ************************************/
    void append_bit(bool bit);

    /*************************************************
    * Returns the number of bits in this bit string. *
    *************************************************/
    size_t length() const;

    /***********************************************
    * Appends 'bs' to the tail of this bit string. *
    ***********************************************/
    void append_bits_from(const bit_string& bs);

    /********************************
    * Reads a bit at index 'index'. *
    ********************************/
    bool read_bit(size_t index) const;

    /*********************************************
    * Removes the last bit from this bit string. *
    *********************************************/
    void remove_last_bit();

    /*******************************************
    * Removes all the bits in this bit string. *
    *******************************************/
    void clear();

    /***************************************************************************
    * Returns the number of bytes it takes to accommodate all the bits in this *
    * bit string.                                                              *
    ***************************************************************************/
    size_t get_number_of_occupied_bytes() const;

    /***********************************************************************
    * Returns an array of bytes holding all the bits from this bit string. *
    ***********************************************************************/
    std::vector<int8_t> to_byte_array() const;

    /***************************************************************************
    * Used for printing the bits in the output stream. Note that for each long *
    * its bits are printed starting from the lowest bit, which implies that    *
    * the actual longs are printed correctly, yet the bits within each long    *
    * are printed "backwards."                                                 *
    ***************************************************************************/
    friend std::ostream& operator<<(std::ostream& out, bit_string& b)
    {
        for (size_t i = 0; i != b.length(); ++i)
        {
            out << (b.read_bit(i) ? '1' : '0');
        }

        return out;
    }

private:
    // The actual vector of longs storing the bits.
    std::vector<uint64_t> storage_longs;

    // The maximum number of bits this bit string can hold without enlarging the
    // 'storage_longs'.
    size_t storage_capacity;

    // The actual number of bits this string is composed of.
    size_t size;

    // Makes sure that the index is within the range.
    void check_access_index(size_t index) const;

    // An implementation of the reading operation. Does not check the index.
    bool read_bit_impl(size_t index) const;

    // An implementation of the writing operation. Does not check the index.
    void write_bit_impl(size_t index, bool bit);

    // Makes sure that this bit string can fit 'requested_capacity' bits.
    void check_bit_array_capacity(size_t requested_capacity);
};

#endif // CODERODDE_BIT_STRING

bit_string.cpp

#include "bit_string.hpp"
#include <climits>
#include <stdexcept>
#include <sstream>
#include <iostream>

bit_string::bit_string()
:
    storage_longs{DEFAULT_NUMBER_OF_UINT64S, 0},
    storage_capacity{BITS_PER_UINT64 * DEFAULT_NUMBER_OF_UINT64S},
    size{0}
{}

bit_string::bit_string(const bit_string& to_copy)
:
    size{to_copy.size},
    storage_longs{to_copy.storage_longs},
    storage_capacity{to_copy.storage_capacity}
{}

bit_string& bit_string::operator=(bit_string &&other)
{
    storage_longs = std::move(other.storage_longs);
    storage_capacity = other.storage_capacity;
    size = other.size;
    return *this;
}

void bit_string::append_bit(bool bit)
{
    check_bit_array_capacity(size + 1);
    write_bit_impl(size, bit);
    ++size;
}

size_t bit_string::length() const {
    return size;
}

void bit_string::append_bits_from(const bit_string& bs)
{
    check_bit_array_capacity(size + bs.size);
    size_t other_size = bs.size;

    for (size_t i = 0; i != other_size; ++i)
    {
        append_bit(bs.read_bit_impl(i));
    }
}

bool bit_string::read_bit(size_t index) const
{
    check_access_index(index);
    return read_bit_impl(index);
}

void bit_string::remove_last_bit()
{
    if (size == 0)
    {
        throw std::runtime_error{"Removing a bit from empty bit string."};
    }

    --size;
}

void bit_string::clear()
{
    size = 0;
}

size_t bit_string::get_number_of_occupied_bytes() const
{
    return size / CHAR_BIT + ((size % CHAR_BIT == 0) ? 0 : 1);
}

std::vector<int8_t> bit_string::to_byte_array() const
{
    size_t number_of_bytes = get_number_of_occupied_bytes();
    std::vector<int8_t> ret(number_of_bytes);

    for (size_t i = 0; i != number_of_bytes; ++i)
    {
        ret[i] = (int8_t)((storage_longs[i / sizeof(uint64_t)]
                           >> CHAR_BIT * (i % sizeof(uint64_t))));
    }

    return std::move(ret);
}

void bit_string::check_access_index(size_t index) const
{
    if (size == 0)
    {
        throw std::runtime_error{"Accesing an empty bit string."};
    }

    if (index >= size)
    {
        std::stringstream ss;
        ss << "The access index is out of range. Index = "
           << index
           << ", length: "
           << size
           << ".";

        throw std::runtime_error{ss.str()};
    }
}

bool bit_string::read_bit_impl(size_t index) const
{
    size_t word_index = index / BITS_PER_UINT64;
    size_t bit_index  = index & MODULO_MASK;
    uint64_t mask = 1ULL << bit_index;
    return (storage_longs[word_index] & mask) != 0;
}

void bit_string::write_bit_impl(size_t index, bool bit)
{
    size_t word_index = index / BITS_PER_UINT64;
    size_t bit_index  = index & MODULO_MASK;

    if (bit)
    {
        uint64_t mask = (1ULL << bit_index);
        storage_longs[word_index] |= mask;
    }
    else
    {
        uint64_t mask = ~(1ULL << bit_index);
        storage_longs[word_index] &= mask;
    }
}

void bit_string::check_bit_array_capacity(size_t requested_capacity)
{
    if (requested_capacity > storage_capacity)
    {
        size_t requested_words_1 =
            requested_capacity / BITS_PER_UINT64 +
         (((requested_capacity & MODULO_MASK) == 0) ? 0 : 1);

        size_t requested_words_2 =
            (3 * storage_capacity / 2) / BITS_PER_UINT64;

        size_t selected_requested_words = std::max(requested_words_1,
                                                   requested_words_2);

        storage_longs.resize(selected_requested_words);
        storage_capacity = storage_longs.size() * BITS_PER_UINT64;
    }
}

byte_counts.hpp

#pragma once

#ifndef BYTE_COUNTS_HPP
#define BYTE_COUNTS_HPP

#include "huffman_tree.hpp"
#include <cstdint>
#include <map>

/***********************************************************************
* Counts relative frequencies of each character represented by a byte. *
***********************************************************************/
std::map<int8_t, uint32_t>
compute_byte_counts(std::vector<int8_t>& text);

#endif // BYTE_WEIGHTS_HPP

byte_counts.cpp

#include "huffman_tree.hpp"
#include <cstdint>
#include <map>
#include <vector>

using std::map;
using std::vector;

std::map<int8_t, uint32_t> compute_byte_counts(std::vector<int8_t>& text)
{
    std::map<int8_t, uint32_t> map;

    for (auto byte : text)
    {
        map[byte] += 1;
    }

    return map;
}

huffman_encoder.hpp

#ifndef HUFFMAN_ENCODER_HPP
#define HUFFMAN_ENCODER_HPP

#include "bit_string.hpp"
#include <map>
#include <vector>

class huffman_encoder {
public:

    /***************************************************************************
    * Encodes the input "text" using the encoder map 'encoder_map' and returns *
    * the result bit string.                                                   *
    ***************************************************************************/
    bit_string encode(std::map<int8_t, bit_string>& encoder_map,
                      std::vector<int8_t>& text);
};

#endif // HUFFMAN_ENCODER_HPP

huffman_encoder.cpp

#include "bit_string.hpp"
#include "huffman_encoder.hpp"

#include <map>

bit_string huffman_encoder::encode(std::map<int8_t, bit_string>& encoder_map,
                                   std::vector<int8_t>& text)
{
    bit_string output_bit_string;
    size_t text_length = text.size();

    for (size_t index = 0; index != text_length; ++index)
    {
        int8_t current_byte = text[index];
        output_bit_string.append_bits_from(encoder_map[current_byte]);
    }

    return output_bit_string;
}

huffman_tree.hpp

#ifndef HUFFMAN_TREE_HPP
#define HUFFMAN_TREE_HPP

#include "bit_string.hpp"
#include <cstdint>
#include <map>

class huffman_tree
{
public:
    /******************************************************
    * Build this Huffman tree using the character counts. *
    ******************************************************/
    explicit huffman_tree(std::map<int8_t, uint32_t>& count_map);

    ~huffman_tree();

    /*****************************************
    * Infers the encoder map from this tree. *
    *****************************************/ 
    std::map<int8_t, bit_string> infer_encoder_map();

    /***************************************************************************
    * Decodes the next character from the bit string starting at bit with      *
    * index 'start_index'. This method will advance the value of 'start_index' *
    * by the code word length read from the tree.                              *
    ***************************************************************************/
    int8_t decode_bit_string(size_t& start_index, bit_string& bits);

private:

    // The actual Huffman tree node type:
    struct huffman_tree_node
    {
        int8_t             character; // The character of this node. Ignore if
                                      // not a leaf node.
        uint32_t           count;     // If a leaf, the count of the character.
                                      // Otherwise, the sum of counts of its
                                      // left and right child nodes.
        bool               is_leaf;   // This node is leaf?
        huffman_tree_node* left;      // The left child node.
        huffman_tree_node* right;     // The right child node.

        // Construct a new Huffman tree node.
        huffman_tree_node(int8_t character,
                          uint32_t count,
                          bool is_leaf)
        :
        character   {character},
        count       {count},
        is_leaf     {is_leaf},
        left        {nullptr},
        right       {nullptr}
        {}
    };

    // The root node of this Huffman tree:
    huffman_tree_node* root;

    // Merges the two input into a new node that has 'node1' and 'node2' as its
    // children. The node with lower ...
    huffman_tree_node* merge(huffman_tree_node* node1,
                             huffman_tree_node* node2);

    // The recursive implementation of the routine that builds the encoder map:
    void infer_encoder_map_impl(bit_string& bit_string_builder,
                                huffman_tree_node* current_node,
                                std::map<int8_t, bit_string>& map);

    // Checks that the input count is positive:
    uint32_t check_count(uint32_t count);

    // Used for deallocating the memory occupied by the tree nodes:
    void recursive_node_delete(huffman_tree_node* node);

public:

    // Used for the priority queue:
    class huffman_tree_node_comparator {
    public:
        bool operator()(const huffman_tree_node *const lhs,
                        const huffman_tree_node *const rhs)
        {
            if (lhs->count == rhs->count)
            {
                // If same weights, order by char value:
                return lhs->character > rhs->character;
            }

            // Otherwise, compare by weights:
            return lhs->count > rhs->count;
        }
    };
};


#endif // HUFFMAN_TREE_HPP

huffman_tree.cpp

#include "bit_string.hpp"
#include "huffman_tree.hpp"
#include <sstream>
#include <stdexcept>
#include <cstdint>
#include <queue>
#include <unordered_map>
#include <utility>
#include <vector>

huffman_tree::huffman_tree(std::map<int8_t, uint32_t>& count_map)
{
    if (count_map.empty())
    {
        std::stringstream ss;
        ss << "Compressor requires a non-empty text.";
        throw std::runtime_error{ss.str()};
    }

    std::priority_queue<huffman_tree_node*,
                        std::vector<huffman_tree_node*>,
                        huffman_tree::huffman_tree_node_comparator> queue;

    std::for_each(count_map.cbegin(),
                  count_map.cend(),
                  [&queue](std::pair<int8_t, uint32_t> p) {
                      queue.push(new huffman_tree_node(p.first,
                                                       p.second,
                                                       true));
                  });

    while (queue.size() > 1)
    {
        huffman_tree_node* node1 = queue.top(); queue.pop();
        huffman_tree_node* node2 = queue.top(); queue.pop();
        queue.push(merge(node1, node2));
    }

    root = queue.top(); queue.pop();
}

void huffman_tree::recursive_node_delete(huffman_tree::huffman_tree_node* node)
{
    if (node == nullptr)
    {
        return;
    }

    recursive_node_delete(node->left);
    recursive_node_delete(node->right);

    delete node;
}

huffman_tree::~huffman_tree()
{
    recursive_node_delete(root);
}

std::map<int8_t, bit_string> huffman_tree::infer_encoder_map()
{
    std::map<int8_t, bit_string> map;

    if (root->is_leaf)
    {
        root->is_leaf = false;
        root->left = new huffman_tree_node(root->character,
                                           1,
                                           true);
        bit_string b;
        b.append_bit(false);
        map[root->character] = std::move(b);
        return map;
    }

    bit_string code_word;
    infer_encoder_map_impl(code_word, root, map);
    return map;
}

int8_t huffman_tree::decode_bit_string(size_t& index, bit_string& bits)
{
    if (root->is_leaf)
    {
        index++;
        return root->character;
    }

    huffman_tree_node* current_node = root;

    while (!current_node->is_leaf)
    {
        bool bit = bits.read_bit(index++);
        current_node = (bit ? current_node->right : current_node->left);
    }

    return current_node->character;
}

void huffman_tree::infer_encoder_map_impl(
                            bit_string& current_code_word,
                            huffman_tree::huffman_tree_node* node,
                            std::map<int8_t, bit_string>& map)
{
    if (node->is_leaf)
    {
        map[node->character] = bit_string(current_code_word);
        return;
    }

    current_code_word.append_bit(false);
    infer_encoder_map_impl(current_code_word,
                           node->left,
                           map);
    current_code_word.remove_last_bit();

    current_code_word.append_bit(true);
    infer_encoder_map_impl(current_code_word,
                           node->right,
                           map);
    current_code_word.remove_last_bit();
}

huffman_tree::huffman_tree_node* huffman_tree::merge(huffman_tree_node* node1,
                                                     huffman_tree_node* node2)
{
    huffman_tree_node* new_node = new huffman_tree_node(0,
                                                        node1->count +
                                                        node2->count,
                                                        false);
    if (node1->count < node2->count)
    {
        new_node->left  = node1;
        new_node->right = node2;
    }
    else
    {
        new_node->left  = node2;
        new_node->right = node1;
    }

    new_node->character = std::max(node1->character, node2->character);
    return new_node;
}

uint32_t huffman_tree::check_count(uint32_t count)
{
    if (count == 0)
    {
        throw std::runtime_error{"The input count is zero."};
    }

    return count;
}

huffman_decoder.hpp

#ifndef HUFFMAN_DECODER_HPP
#define HUFFMAN_DECODER_HPP

#include "bit_string.hpp"
#include "huffman_tree.hpp"
#include <vector>

class huffman_decoder {
public:
    std::vector<int8_t> decode(huffman_tree& tree, bit_string& encoded_text);
};

#endif // HUFFMAN_DECODER_HPP

huffman_decoder.cpp

#include "huffman_decoder.hpp"

std::vector<int8_t>
huffman_decoder::decode(huffman_tree& tree,
                        bit_string& encoded_text)
{
    size_t index = 0;
    size_t bit_string_length = encoded_text.length();
    std::vector<int8_t> decoded_text;

    while (index < bit_string_length)
    {
        int8_t character = tree.decode_bit_string(index, encoded_text);
        decoded_text.push_back(character);
    }

    return decoded_text;
}

huffman_serializer.hpp

#ifndef HUFFMAN_SERIALIZER_HPP
#define HUFFMAN_SERIALIZER_HPP

#include "bit_string.hpp"
#include <cstdint>
#include <cstdlib>
#include <map>
#include <vector>

class huffman_serializer {
public:

    static const int8_t MAGIC[4];
    static const size_t BYTES_PER_WEIGHT_MAP_ENTRY;
    static const size_t BYTES_PER_CODE_WORD_COUNT_ENTRY;
    static const size_t BYTES_PER_BIT_COUNT_ENTRY;

    std::vector<int8_t> serialize(std::map<int8_t, uint32_t>& count_map,
                                  bit_string& encoded_text);
};

#endif // HUFFMAN_SERIALIZER_HPP

huffman_serializer.cpp

#include "huffman_serializer.hpp"
#include <algorithm>

const int8_t huffman_serializer::MAGIC[4] = { (int8_t) 0xC0,
                                              (int8_t) 0xDE,
                                              (int8_t) 0x0D,
                                              (int8_t) 0xDE };

const size_t huffman_serializer::BYTES_PER_WEIGHT_MAP_ENTRY      = 5;
const size_t huffman_serializer::BYTES_PER_CODE_WORD_COUNT_ENTRY = 4;
const size_t huffman_serializer::BYTES_PER_BIT_COUNT_ENTRY       = 4;

static size_t compute_byte_list_size(std::map<int8_t, uint32_t>& count_map,
                                     bit_string& encoded_text)
{
    return sizeof(huffman_serializer::MAGIC)
                  + huffman_serializer::BYTES_PER_CODE_WORD_COUNT_ENTRY
                  + huffman_serializer::BYTES_PER_BIT_COUNT_ENTRY
                  + count_map.size()
                    * huffman_serializer::BYTES_PER_WEIGHT_MAP_ENTRY
                  + encoded_text.get_number_of_occupied_bytes();
}

std::vector<int8_t>
huffman_serializer::serialize(std::map<int8_t, uint32_t>& count_map,
                              bit_string& encoded_text)
{
    std::vector<int8_t> byte_list;
    byte_list.reserve(compute_byte_list_size(count_map, encoded_text));

    // Emit the file type signature magic:
    for (int8_t magic_byte : huffman_serializer::MAGIC)
    {
        byte_list.push_back(magic_byte);
    }

    union
    {
        uint32_t num;
        int8_t bytes[4];
    } t;

    t.num = (uint32_t) count_map.size();

    byte_list.push_back(t.bytes[0]);
    byte_list.push_back(t.bytes[1]);
    byte_list.push_back(t.bytes[2]);
    byte_list.push_back(t.bytes[3]);

    t.num = (uint32_t) encoded_text.length();

    byte_list.push_back(t.bytes[0]);
    byte_list.push_back(t.bytes[1]);
    byte_list.push_back(t.bytes[2]);
    byte_list.push_back(t.bytes[3]);

    union
    {
        uint32_t count;
        int8_t bytes[4];
    }
    count_bytes;

    // Emit the code words:
    for (const auto& entry : count_map)
    {
        int8_t byte = entry.first;
        byte_list.push_back(byte);

        uint32_t count = entry.second;
        count_bytes.count = count;

        byte_list.push_back(count_bytes.bytes[0]);
        byte_list.push_back(count_bytes.bytes[1]);
        byte_list.push_back(count_bytes.bytes[2]);
        byte_list.push_back(count_bytes.bytes[3]);
    }

    std::vector<int8_t> encoded_text_byte_vector = encoded_text.to_byte_array();

    std::copy(encoded_text_byte_vector.begin(),
              encoded_text_byte_vector.end(),
              std::back_inserter(byte_list));

    return byte_list;
}

huffman_deserializer.hpp

#ifndef HUFFMAN_DESERIALIZER_HPP
#define HUFFMAN_DESERIALIZER_HPP

#include "bit_string.hpp"
#include <map>
#include <cstdint>
#include <vector>

class huffman_deserializer {
public:

    struct result {
        bit_string encoded_text;
        std::map<int8_t, uint32_t> count_map;
    };

    /********************************************************************
    * Returns a struct holding the encoded text and the weight map that *
    * produced it.                                                      *
    ********************************************************************/
    result deserialize(std::vector<int8_t>& data);

private:

    // Make sure that the data contains the magic signature:
    void check_signature(std::vector<int8_t>& data);

    // Make sure that the data describes the number of code words in the stream
    // and returns that number:
    size_t extract_number_of_code_words(std::vector<int8_t>& data);

    // Make sure that the data describes the number of encoded text bits in the
    // stream and returns that number:
    size_t extract_number_of_encoded_text_bits(std::vector<int8_t>& data);

    // Extracts the actual encoder map from the stream:
    std::map<int8_t, uint32_t>
    extract_count_map(std::vector<int8_t>& data, size_t number_of_code_words);

    // Extracts the actual encoded text from the stream:
    bit_string extract_encoded_text(
                                const std::vector<int8_t>& data,
                                const std::map<int8_t, uint32_t>& weight_map,
                                const size_t number_of_encoded_text_bits);
};

#endif // HUFFMAN_DESERIALIZER_HPP

huffman_deserializer.cpp

#include "huffman_deserializer.hpp"
#include "huffman_serializer.hpp"
#include "file_format_error.h"

#include <sstream>
#include <string>

huffman_deserializer::result
huffman_deserializer::deserialize(std::vector<int8_t> &data)
{
    check_signature(data);
    // The number of code words is the same as the number of mappings in the
    // deserialized weight map.
    size_t number_of_code_words = extract_number_of_code_words(data);
    size_t number_of_text_bits  = extract_number_of_encoded_text_bits(data);
    std::map<int8_t, uint32_t> count_map =
                extract_count_map(data, number_of_code_words);

    bit_string encoded_text = extract_encoded_text(data,
                                                   count_map,
                                                   number_of_text_bits);
    result ret;
    ret.count_map    = std::move(count_map);
    ret.encoded_text = std::move(encoded_text);
    return ret;
}

void huffman_deserializer::check_signature(std::vector<int8_t>& data)
{
    if (data.size() < sizeof(huffman_serializer::MAGIC))
    {
        std::stringstream ss;

        ss << "The data is too short to contain "
              "the mandatory signature. Data length: "
           << data.size()
           << ".";

        std::string err_msg = ss.str();
        throw file_format_error(err_msg.c_str());
    }

    for (size_t i = 0; i != sizeof(huffman_serializer::MAGIC); ++i)
    {
        if (data[i] != huffman_serializer::MAGIC[i])
        {
            throw file_format_error("Bad file type signature.");
        }
    }
}

size_t huffman_deserializer
::extract_number_of_code_words(std::vector<int8_t>& data)
{
    if (data.size() < 8)
    {
        std::stringstream ss;
        ss << "No number of code words in the data. The file is too short: ";
        ss << data.size() << " bytes.";
        std::string err_msg = ss.str();
        throw file_format_error{err_msg.c_str()};
    }

    union
    {
        size_t num;
        int8_t bytes[sizeof(size_t)];
    } t;

    t.num = 0;
    t.bytes[0] = data[4];
    t.bytes[1] = data[5];
    t.bytes[2] = data[6];
    t.bytes[3] = data[7];

    return t.num;
}

size_t huffman_deserializer
::extract_number_of_encoded_text_bits(std::vector<int8_t>& data)
{
    if (data.size() < 12)
    {
        std::stringstream ss;
        ss << "No number of encoded text bits. The file is too short: ";
        ss << data.size() << " bytes.";
        std::string err_msg = ss.str();
        throw file_format_error{err_msg.c_str()};
    }

    union
    {
        size_t num;
        int8_t bytes[8];
    } t;

    t.num = 0;
    t.bytes[0] = data[8];
    t.bytes[1] = data[9];
    t.bytes[2] = data[10];
    t.bytes[3] = data[11];

    return t.num;
}

std::map<int8_t, uint32_t> huffman_deserializer::
extract_count_map(std::vector<int8_t>& data, size_t number_of_code_words)
{
    std::map<int8_t, uint32_t> count_map;

    try
    {
        size_t data_byte_index =
            sizeof(huffman_serializer::MAGIC) +
            huffman_serializer::BYTES_PER_BIT_COUNT_ENTRY +
            huffman_serializer::BYTES_PER_CODE_WORD_COUNT_ENTRY;

        union
        {
            uint32_t count;
            int8_t bytes[4];
        }
        count_bytes;

        for (size_t i = 0; i != number_of_code_words; ++i)
        {
            int8_t byte = data.at(data_byte_index++);
            count_bytes.count = 0;
            count_bytes.bytes[0] = data.at(data_byte_index++);
            count_bytes.bytes[1] = data.at(data_byte_index++);
            count_bytes.bytes[2] = data.at(data_byte_index++);
            count_bytes.bytes[3] = data.at(data_byte_index++);

            count_map[byte] = count_bytes.count;
        }
    }
    catch (std::out_of_range& error)
    {
        std::stringstream ss;
        ss << "The input data is too short in order to recover the encoding "
              "map. "
        << error.what();
        std::string err_msg = ss.str();
        throw file_format_error{err_msg.c_str()};
    }

    return count_map;
}

bit_string huffman_deserializer
::extract_encoded_text(const std::vector<int8_t>& data,
                       const std::map<int8_t, uint32_t>& count_map,
                       const size_t number_of_encoded_text_bits)
{
    size_t omitted_bytes =
        sizeof(huffman_serializer::MAGIC) +
        huffman_serializer::BYTES_PER_BIT_COUNT_ENTRY +
        huffman_serializer::BYTES_PER_CODE_WORD_COUNT_ENTRY;

    omitted_bytes +=
        count_map.size() * huffman_serializer::BYTES_PER_WEIGHT_MAP_ENTRY;

    bit_string encoded_text;
    size_t current_byte_index = omitted_bytes;
    size_t current_bit_index = 0;

    try
    {
        for (size_t bit_index = 0;
             bit_index != number_of_encoded_text_bits;
             bit_index++)
        {
            bool bit =
                (data.at(current_byte_index) & (1 << current_bit_index)) != 0;

            encoded_text.append_bit(bit);

            if (++current_bit_index == CHAR_BIT)
            {
                current_bit_index = 0;
                current_byte_index++;
            }
        }
    }
    catch (std::out_of_range& error)
    {
        std::stringstream ss;
        ss << "The input data is too short in order to recover encoded text. "
           << error.what();
        std::string err_msg = ss.str();
        throw file_format_error{err_msg.c_str()};
    }

    return encoded_text;
}

file_format_error.h

#ifndef FILE_FORMAT_ERROR_H
#define FILE_FORMAT_ERROR_H

#include <stdexcept>

class file_format_error : public std::runtime_error {
public:

    explicit file_format_error(const char* err_msg)
    :
    std::runtime_error{err_msg}
    {}
};

#endif // FILE_FORMAT_ERROR_H

Critique request

Please tell me anything you have in mind. In particular:

  • Efficiency (correct use of move semantics),
  • Coding and naming conventions,
  • Modularity,
  • API design.
\$\endgroup\$
  • \$\begingroup\$ I completed my answer. \$\endgroup\$ – Stud Dec 3 '16 at 21:04
3
\$\begingroup\$

Minor stuffs

1) std::string get_indent(size_t len) could use a constructor for basic_string. Like this: std::string s(len, ' ');

2) byte_counts.hpp and bit_string.hpp use #pragma once before the include guards.

3) Instead of:

bool decode = false;
if (command_line_argument_set.find(DECODE_FLAG_SHORT) != args_end ||
    command_line_argument_set.find(DECODE_FLAG_LONG) != args_end)
{
    decode = true;
}

You can directly write:

bool decode = command_line_argument_set.find(DECODE_FLAG_SHORT) != args_end || 
              command_line_argument_set.find(DECODE_FLAG_LONG) != args_end

4) if ((!decode and !encode) or (decode and encode)) could be if (decode == encode)

OOP

Your main.cpp is a bit messy. A 700 lines long file with C functions only should not appear in C++ project, even for testing purposes.

Move

In std::vector<int8_t> file_read(std::string& file_name) you use return std::move(ret);

return ret; is a case of NRVO, so copy elision is permitted. As ret is an lvalue, the move constructor of std::vector<int8_t> will be used to obtain the return value of file_read. A simple rule for this: if you return a local variable by value, the compiler knows that this variable won't be use later so it'll use the move constructor.

If you want to return an lvalue expression or a non local variable, using std::move allows you to tell the constructor to move instead of copy.

So why not use std::move all the time (even when the compiler does the optimization)? Using std::move on a return value is considered harmful as it can prevent elision.

Containers

You used a lot of c++11 and c++14 features and it's really nice, I love it. You could have use an std::array instead of static const int8_t MAGIC[4]; to be even better at this.

In huffman_serializer::serialize(std::map<int8_t, uint32_t>& count_map, bit_string& encoded_text) you can replace this

// Emit the file type signature magic:
for (int8_t magic_byte : huffman_serializer::MAGIC)
{
    byte_list.push_back(magic_byte);
}

by this:

 byte_list.insert(byte_list.end(),  &huffman_serializer::MAGIC[0], &huffman_serializer::MAGIC[4]);

Using std::vector::insert is clearer and it generaly is the best solution to add an array in an std::vector.

You wrote this:

union
{
    uint32_t num;
    int8_t bytes[4];
} t;

t.num = (uint32_t) count_map.size();

byte_list.push_back(t.bytes[0]);
byte_list.push_back(t.bytes[1]);
byte_list.push_back(t.bytes[2]);
byte_list.push_back(t.bytes[3]);

I never encountered this use of a Union and I find it interesting. Thanks to you I learned that this is a perfectly correct way to use Unions at least since C++11.

Modularity You copy pasted your code chunk with std::stringstream here and there, It looks like you could do something to encapsulate your error messages.

\$\endgroup\$
  • \$\begingroup\$ Awesome review! Just what I needed. :^) \$\endgroup\$ – coderodde Dec 3 '16 at 22:34
  • \$\begingroup\$ I'm glad I helped! \$\endgroup\$ – Stud Dec 3 '16 at 22:41
3
\$\begingroup\$

For efficiency you mention "correct use of move semantics", but there is a more fundamental problem with this setup: it uses tree walking decoding. That algorithm really only exists to show that Huffman codes are decodable, not to actually decode them.

Unlike most other Huffman decoding algorithms, it will scale to very unbalanced trees. However, very unbalanced trees are not necessary for good compression, only for theoretical optimality. Every real life use of Huffman codes (that I know of) sacrifices theoretical optimality to enable fast decoding.

If the code length is limited* to some reasonable size (say 15, like Deflate, but you can go a bit higher, 20 is doable even with the simplest table-based decoding algorithm), you can decode a symbol using a single table lookup. The table would be indexed by a bitbuffer holding sufficient bits to decode any symbol, and give you a pair (symbol, length) decoding the first symbol in the buffer. The table is easy to generate from the list of code words. There are some more complex schemes that reduce the table size, and multi-level tables would enable accelerated decoding even without limited code word length but it obviously comes at an efficiency price - it becomes tree-decoding again, but with a high branching factor so multiple bits are decoded per level.

*: Code lengths can be limited by dividing the symbol counts by 2 (rounding up), and then re-creating a Huffman tree. Repeat until the length is not exceeded. This is a bit of a dumb way to do it (but simple to implement and it does work), you can also solve it in one go with the package-merge algorithm.

Secondly, it does not use canonical Huffman codes. This means it has to store the full code words in the header, making the compressed file bigger. When using canonical Huffman codes, the code word lengths are sufficient to recreate the code words themselves. You can apply run-length encoding to the table of lengths to (typically) make it even smaller.

Of course both of these suggestions would cause you to lose compatibility with the linked Java code, so perhaps you cannot use them.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.