rle.hpp

#pragma once

namespace cipher
{
    namespace rle
    {
        namespace details
        {
            template <typename T>
            struct RLEPair { std::size_t count; T t; };

            template<typename T>
            bool operator==(const RLEPair<T>& lhs, const RLEPair<T>& rhs)
            {
                return lhs.count == rhs.count && lhs.t == rhs.t;
            }
        }

        template <typename InputIter, typename OutputIter>
        OutputIter encode(InputIter begin, InputIter end, OutputIter out)
        {
            InputIter it = begin;
            if (it == end) return out;

            details::RLEPair<typename InputIter::value_type> pair = { 1, *(it++) };
            for (; it != end; ++it)
            {
                if (*it == pair.t)
                {
                    ++pair.count;
                }
                else
                {
                    *(out++) = pair;
                    pair = { 1, *it };
                }
            }

            *(out++) = pair;

            return out;
        }
    }
}

rletests.cpp

#include <algorithm>
#include <iterator>
#include <string>
#include <vector>

#include "catch.hpp"
#include "../cipher/rle.hpp"

TEST_CASE("RLE Encoding a string", "[string]") {

    std::string input = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW";
    std::vector<cipher::rle::details::RLEPair<char>> encodedInput = { { 12, 'W' }, { 1, 'B' }, { 12, 'W' }, { 3, 'B' }, { 24, 'W' }, { 1, 'B' }, { 14, 'W' } };

    std::vector<cipher::rle::details::RLEPair<char>> output;
    cipher::rle::encode(input.begin(), input.end(), std::back_inserter(output));

    REQUIRE(output.size() == encodedInput.size());

    auto pair = std::mismatch(encodedInput.begin(), encodedInput.end(), output.begin());
    REQUIRE(pair.first == encodedInput.end());
    REQUIRE(pair.second == output.end());
}