Skip to content

consecutive_segment.hpp

#include "noya/consecutive_segment.hpp"

View on GitHub

#ifndef NOYA_CONSECUTIVE_SEGMENT_HPP
#define NOYA_CONSECUTIVE_SEGMENT_HPP 1

#include <map>
#include <tuple>
#include <vector>

namespace noya {

/// @brief Interval assignment container maintaining consecutive segments of equal values.
template <class T> struct consecutive_segment {
  std::map<int, T> mp;
  consecutive_segment() {}
  consecutive_segment(int N, int v = 0) { mp[N] = v; }
  void split(int x) {
    auto it = mp.lower_bound(x);
    mp[x] = it->second;
  }

  /// @brief Get the value at position x.
  T get(int x) const {
    return mp.upper_bound(x)->second;
  }

  /// @brief Assign [l, r) = v.
  /// @return The original segments as vector of (left, right, value).
  std::vector<std::tuple<int, int, T>> assign(int l, int r, T v) {
    split(l);
    split(r);
    auto it = mp.find(l);
    T t = mp[l];
    std::vector<std::tuple<int, int, T>> segments;
    while (it->first != r) {
      auto nx = next(it);
      segments.push_back({it->first, nx->first, nx->second});
      it = mp.erase(it);
    }
    mp[l] = t;
    mp[r] = v;
    return segments;
  }
};

} // namespace noya

#endif // NOYA_CONSECUTIVE_SEGMENT_HPP

#include <map>
#include <tuple>
#include <vector>

namespace noya {

/// @brief Interval assignment container maintaining consecutive segments of equal values.
template <class T> struct consecutive_segment {
  std::map<int, T> mp;
  consecutive_segment() {}
  consecutive_segment(int N, int v = 0) { mp[N] = v; }
  void split(int x) {
    auto it = mp.lower_bound(x);
    mp[x] = it->second;
  }

  /// @brief Get the value at position x.
  T get(int x) const {
    return mp.upper_bound(x)->second;
  }

  /// @brief Assign [l, r) = v.
  /// @return The original segments as vector of (left, right, value).
  std::vector<std::tuple<int, int, T>> assign(int l, int r, T v) {
    split(l);
    split(r);
    auto it = mp.find(l);
    T t = mp[l];
    std::vector<std::tuple<int, int, T>> segments;
    while (it->first != r) {
      auto nx = next(it);
      segments.push_back({it->first, nx->first, nx->second});
      it = mp.erase(it);
    }
    mp[l] = t;
    mp[r] = v;
    return segments;
  }
};

} // namespace noya