Library/DataStructure/RunLengthEncoding.hpp

• View this file on GitHub
• Last update: 2024-12-27 17:07:26+09:00
• Include: #include "Library/DataStructure/RunLengthEncoding.hpp"

Verified with

• Test/DataStructure/RunLengthEncoding.test.cpp

Code

#pragma once

#include <ranges>
#include <vector>

namespace mtd {
  template <std::ranges::range _R>
  class RunLengthEncoding {
    using T = std::iter_value_t<std::ranges::iterator_t<_R>>;

    const std::vector<std::tuple<T, int>> r;

    static constexpr auto construct_rle(const _R& r) {
      std::vector<std::tuple<T, int>> rle;
      if (r.empty()) { return rle; }
      T now = *r.begin();
      int cnt = 1;
      for (const auto& x : r | std::views::drop(1)) {
        if (x == now) {
          ++cnt;
        } else {
          rle.emplace_back(now, cnt);
          cnt = 1;
          now = x;
        }
      }
      rle.emplace_back(now, cnt);
      return rle;
    }

  public:
    constexpr RunLengthEncoding(const _R& _r) : r(construct_rle(_r)) {}

    constexpr auto begin() const { return r.begin(); }
    constexpr auto end() const { return r.end(); }
  };
}  // namespace mtd

#line 2 "Library/DataStructure/RunLengthEncoding.hpp"

#include <ranges>
#include <vector>

namespace mtd {
  template <std::ranges::range _R>
  class RunLengthEncoding {
    using T = std::iter_value_t<std::ranges::iterator_t<_R>>;

    const std::vector<std::tuple<T, int>> r;

    static constexpr auto construct_rle(const _R& r) {
      std::vector<std::tuple<T, int>> rle;
      if (r.empty()) { return rle; }
      T now = *r.begin();
      int cnt = 1;
      for (const auto& x : r | std::views::drop(1)) {
        if (x == now) {
          ++cnt;
        } else {
          rle.emplace_back(now, cnt);
          cnt = 1;
          now = x;
        }
      }
      rle.emplace_back(now, cnt);
      return rle;
    }

  public:
    constexpr RunLengthEncoding(const _R& _r) : r(construct_rle(_r)) {}

    constexpr auto begin() const { return r.begin(); }
    constexpr auto end() const { return r.end(); }
  };
}  // namespace mtd

Back to top page