Run-length encoding (tools/run_length.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2022-10-08 19:22:04+09:00
• Include: #include "tools/run_length.hpp"

template <typename InputIterator, typename OutputIterator>
void run_length(InputIterator begin, InputIterator end, OutputIterator result);

It replaces consecutive elements to a pair of the element and the number of occurrences, and stores the pairs with such a format to result.

Constraints

• None

Time Complexity

• $O(N)$ where $N$ is end - begin.

License

• CC0

Author

• anqooqie

Required by

• List all divisors (tools/divisors.hpp)
• Extended Lucas' theorem (tools/extended_lucas.hpp)
• $x \uparrow\uparrow y \pmod{M}$ (tools/tetration_mod.hpp)
• Euler's totient function (tools/totient.hpp)
• Twelvefold way (tools/twelvefold_way.hpp)

Verified with

• tests/divisors.test.cpp
• tests/divisors_of_divisor.test.cpp
• tests/extended_lucas.test.cpp
• tests/run_length.test.cpp
• tests/tetration_mod.test.cpp
• tests/totient.test.cpp
• tests/twelvefold_way/labeled_ball_labeled_box_at_least_1.test.cpp
• tests/twelvefold_way/labeled_ball_labeled_box_at_most_1.test.cpp
• tests/twelvefold_way/labeled_ball_labeled_box_unrestricted.test.cpp
• tests/twelvefold_way/labeled_ball_unlabeled_box_at_least_1.test.cpp
• tests/twelvefold_way/labeled_ball_unlabeled_box_at_most_1.test.cpp
• tests/twelvefold_way/labeled_ball_unlabeled_box_unrestricted.test.cpp
• tests/twelvefold_way/unlabeled_ball_labeled_box_at_least_1.test.cpp
• tests/twelvefold_way/unlabeled_ball_labeled_box_at_most_1.test.cpp
• tests/twelvefold_way/unlabeled_ball_labeled_box_unrestricted.test.cpp
• tests/twelvefold_way/unlabeled_ball_unlabeled_box_at_least_1.test.cpp
• tests/twelvefold_way/unlabeled_ball_unlabeled_box_at_most_1.test.cpp
• tests/twelvefold_way/unlabeled_ball_unlabeled_box_unrestricted.test.cpp

Code

#ifndef TOOLS_RUN_LENGTH_HPP
#define TOOLS_RUN_LENGTH_HPP

#include <iterator>
#include <cstddef>
#include <utility>
#include <cstdint>

namespace tools {
  template <typename InputIterator, typename OutputIterator>
  void run_length(const InputIterator& begin, const InputIterator& end, OutputIterator result) {
    using T = typename ::std::iterator_traits<InputIterator>::value_type;
    if (begin == end) return;

    ::std::pair<T, ::std::size_t> prev;
    for (auto [it, breaks] = ::std::make_pair(begin, false); !breaks; breaks = it == end, it = ::std::next(it, breaks ? 0 : 1)) {
      bool flg1, flg2;
      if (it == begin) {
        flg1 = false;
        flg2 = true;
      } else if (it == end) {
        flg1 = true;
        flg2 = false;
      } else if (*it != prev.first) {
        flg1 = true;
        flg2 = true;
      } else {
        flg1 = false;
        flg2 = false;
      }
      if (flg1 || flg2) {
        if (flg1) {
          *result = prev;
          ++result;
        }
        if (flg2) {
          prev.first = *it;
          prev.second = 1;
        }
      } else {
        ++prev.second;
      }
    }
  }
}

#endif

#line 1 "tools/run_length.hpp"



#include <iterator>
#include <cstddef>
#include <utility>
#include <cstdint>

namespace tools {
  template <typename InputIterator, typename OutputIterator>
  void run_length(const InputIterator& begin, const InputIterator& end, OutputIterator result) {
    using T = typename ::std::iterator_traits<InputIterator>::value_type;
    if (begin == end) return;

    ::std::pair<T, ::std::size_t> prev;
    for (auto [it, breaks] = ::std::make_pair(begin, false); !breaks; breaks = it == end, it = ::std::next(it, breaks ? 0 : 1)) {
      bool flg1, flg2;
      if (it == begin) {
        flg1 = false;
        flg2 = true;
      } else if (it == end) {
        flg1 = true;
        flg2 = false;
      } else if (*it != prev.first) {
        flg1 = true;
        flg2 = true;
      } else {
        flg1 = false;
        flg2 = false;
      }
      if (flg1 || flg2) {
        if (flg1) {
          *result = prev;
          ++result;
        }
        if (flg2) {
          prev.first = *it;
          prev.second = 1;
        }
      } else {
        ++prev.second;
      }
    }
  }
}

Back to top page