Interval Map

data_structure/interval_map.hpp · GitHub で見る

共通ページ

整数の半開区間 \([l,r)\) に値を代入するデータ構造です。重なった部分は上書きし、隣接する同じ値の区間は自動で結合します。値が設定されていない場所も扱えます。

#include "lib/data_structure/interval_map.hpp"
#include <string>

IntervalMap<int, std::string> colors(0, 10, "red");
colors.assign(3, 7, "blue");
auto value = colors.get(4); // optional("blue")
auto missing = colors.get(10); // nullopt

colors.erase(4, 6);
auto size = colors.size(); // 8: 値が設定されている整数の個数
for (const auto &[left, segment] : colors) {
    // [left, segment.right) の値が segment.value
}

colors.assign(3, 7, "red");
auto count = colors.interval_count(); // 1: [0,10) がすべて red
colors.set(2, "green"); // [2,3) に代入

IntervalMap<T,V,Size,Equal> の T は座標型、V は値の型です。どちらも既定は std::int64_t です。T は bool を除く整数型を使います。負の座標、__int128_t・__uint128_t、Boost.Multiprecision の整数型にも対応し、ヘッダー自体は Boost に依存しません。

API

操作	内容・返り値
IntervalMap()	空のマップを作成
IntervalMap(l,r,value)	初めに [l,r) へ value を代入
IntervalMap(intervals)	vector<interval_type> または初期化子リストの区間を順番に代入
assign(l,r,value)	[l,r) を value で上書き
set(x,value)	整数 x の値を設定
assign(intervals)	全内容を、区間列を順番に代入した結果で置き換える
erase(l,r) / erase(x)	区間／整数 x の値を削除。値がなくなった整数の個数を返す
get(x)	x の値を std::optional<V> で返す。未設定なら nullopt
at(x)	x の値の const V& を返す。値が設定されていることが必要
find(x)	x を含む区間のイテレータ。未設定なら end()
lower_bound(x)	x を含む区間、なければ右側の最初の区間のイテレータ。なければ end()
contains(x)	x に値が設定されているか
contains(l,r)	値を問わず [l,r) 全体に値が設定されているか
contains(l,r,value)	[l,r) 全体が value か
intersects(l,r)	[l,r) 内に値が設定された整数があるか
count(l,r)	[l,r) 内で値が設定された整数の個数
for_each(l,r,visit)	重なる区間を [l,r) で切り詰め、visit(left,right,const V&) を左から呼ぶ。未設定部分は省く
size() / interval_count()	値が設定された整数の個数／区間数
empty()	区間がないか
begin() / end()	左端の昇順に区間を読み取り専用で走査
rbegin() / rend()	左端の降順に区間を読み取り専用で走査
clear()	全内容を削除
コピー／代入	独立したマップとして複製
移動／移動代入	内容を移動。移動元は空になり、再利用可能
swap(t) / swap(s,t)	内容と値の比較関数を交換

interval_type は {left,right,value} の 3 メンバーを持つ構造体です。区間列に重なりがあれば、後の要素の値を優先します。イテレータは左端をキーとし、second.right が右端、second.value が値です。更新で分割・結合・削除された区間のイテレータや参照は取得し直してください。for_each のコールバック内で同じマップを更新しないでください。

V はコピー・移動・代入ができる型です。等値比較には Equal（既定は std::equal_to<V>）を使い、同値な値は同じ値として扱います。独自の同値関係を使う場合は、同値性を判定する関数を Equal に指定し、コンストラクタの最後の引数で渡します。assign(intervals)・clear は比較関数を維持します。

範囲と計算量

区間は \(l\le r\) とし、両端とも T で表します。空区間の更新・列挙は何もせず、contains(l,r)・contains(l,r,value) は true、intersects(l,r) は false、count(l,r) は 0 です。

上限のある座標型では、設定できる整数は T の最小値以上、最大値未満です。最大値を区間の右端や検索座標には使えます。set(x,value) は最大値未満の x に対して使い、erase(x) は最大値なら 0 を返します。

Size は区間の長さと個数の型です。既定は、64 bit 以下の組み込み整数座標では std::uint64_t、128 bit 座標では __uint128_t、その他では T です。T・Size は std::numeric_limits の is_integer が true になる型を使います。独自の Size を指定する場合は、端点からの変換・長さの差・個数の加減算を正確に計算できる型を選んでください。固定幅の多倍長整数で広い区間を扱う場合は、Size に cpp_int などを指定できます。

保持する区間数を \(n\)、対象範囲に重なる区間数を \(k\) とします。区間の代入・削除、contains(l,r)・count・for_each は \(O(\log n+k)\) 時間、単点更新・検索・contains(l,r,value)・intersects は \(O(\log n)\) 時間です。size・interval_count・empty とイテレータの取得は \(O(1)\)、コピー・clear は \(O(n)\)、移動構築・交換は \(O(1)\) 時間です。移動代入は移動先の区間数に比例します。空のマップに対する操作は定数時間です。

長さ \(m\) の区間列からの構築は \(O(m\log m)\)、assign(intervals) は \(O(n+m\log m)\) 時間です。使用空間は \(O(n)\) で、区間列からの構築・置換中は \(O(n+m)\) です。以上は座標・値の比較、コピー、演算を定数時間とした計算量です。

検証コード

• test/interval_map.test.cpp

コード

#ifndef INTERVAL_MAP_HPP
#define INTERVAL_MAP_HPP

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <map>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>

template<class T = std::int64_t, class V = std::int64_t, class Size = std::conditional_t<
	std::is_integral_v<T> && sizeof(T) <= 8, std::uint64_t,
	std::conditional_t<std::is_same_v<T, __int128_t>, __uint128_t, T>>, class Equal = std::equal_to<V>>
class IntervalMap {
	static_assert(std::numeric_limits<T>::is_integer && !std::is_same_v<T, bool>);
	static_assert(std::numeric_limits<Size>::is_integer && !std::is_same_v<Size, bool>);

public:
	using coordinate_type = T;
	using mapped_type = V;
	using size_type = Size;
	using value_equal = Equal;
	struct interval_type { T left, right; V value; };
	struct segment_type { T right; V value; };
	using const_iterator = typename std::map<T, segment_type>::const_iterator;
	using const_reverse_iterator = typename std::map<T, segment_type>::const_reverse_iterator;

private:
	std::map<T, segment_type> ranges;
	Size total = 0;
	[[no_unique_address]] Equal equal;
	static Size length(const T &l, const T &r) { return static_cast<Size>(r) - static_cast<Size>(l); }
	auto split(const T &x) {
		auto it = ranges.lower_bound(x);
		if (it != ranges.end() && it->first == x) return it;
		if (it == ranges.begin()) return it;
		auto previous = std::prev(it);
		if (previous->second.right <= x) return it;
		auto next = ranges.emplace_hint(it, x, segment_type{previous->second.right, previous->second.value});
		previous->second.right = x;
		return next;
	}

public:
	explicit IntervalMap(Equal compare = Equal{}) : equal(std::move(compare)) {}
	IntervalMap(T l, T r, const V &value, Equal compare = Equal{}) : IntervalMap(std::move(compare)) { assign(l, r, value); }
	explicit IntervalMap(std::vector<interval_type> intervals, Equal compare = Equal{}) : IntervalMap(std::move(compare)) { assign(std::move(intervals)); }
	IntervalMap(std::initializer_list<interval_type> intervals, Equal compare = Equal{}) : IntervalMap(std::vector<interval_type>(intervals), std::move(compare)) {}
	IntervalMap(const IntervalMap &) = default;
	IntervalMap(IntervalMap &&other) noexcept(std::is_nothrow_copy_constructible_v<Equal> && std::is_nothrow_constructible_v<Size, int> && std::is_nothrow_swappable_v<Size> && std::is_nothrow_swappable_v<Equal>)
		: equal(other.equal) { swap(other); }
	IntervalMap &operator=(IntervalMap other) noexcept(std::is_nothrow_swappable_v<Size> && std::is_nothrow_swappable_v<Equal>) { swap(other); return *this; }

	void assign(T l, T r, const V &value) {
		assert(l <= r);
		if (l == r || contains(l, r, value)) return;
		V stored(value);
		auto last = split(r), first = split(l);
		for (auto it = first; it != last; ++it) total -= length(it->first, it->second.right);
		ranges.erase(first, last);
		auto it = ranges.emplace_hint(last, l, segment_type{r, std::move(stored)});
		total += length(l, r);
		if (it != ranges.begin()) {
			auto previous = std::prev(it);
			if (previous->second.right == l && equal(previous->second.value, it->second.value)) {
				previous->second.right = r;
				ranges.erase(it);
				it = previous;
			}
		}
		auto next = std::next(it);
		if (next != ranges.end() && it->second.right == next->first && equal(it->second.value, next->second.value)) {
			it->second.right = next->second.right;
			ranges.erase(next);
		}
	}
	void assign(std::vector<interval_type> intervals) {
		IntervalMap next(equal);
		for (const auto &[l, r, value] : intervals) next.assign(l, r, value);
		swap(next);
	}
	void set(T x, const V &value) {
		if constexpr (std::numeric_limits<T>::is_bounded) assert(x < (std::numeric_limits<T>::max)());
		assign(x, static_cast<T>(x + 1), value);
	}
	size_type erase(T l, T r) {
		assert(l <= r);
		if (l == r) return 0;
		auto last = split(r), first = split(l);
		size_type removed = 0;
		for (auto it = first; it != last; ++it) removed += length(it->first, it->second.right);
		ranges.erase(first, last);
		total -= removed;
		return removed;
	}
	size_type erase(T x) {
		if constexpr (std::numeric_limits<T>::is_bounded) if (x == (std::numeric_limits<T>::max)()) return 0;
		return erase(x, static_cast<T>(x + 1));
	}
	const_iterator find(T x) const {
		auto it = ranges.upper_bound(x);
		if (it == ranges.begin()) return ranges.end();
		--it;
		return x < it->second.right ? it : ranges.end();
	}
	const_iterator lower_bound(T x) const {
		auto it = ranges.upper_bound(x);
		if (it != ranges.begin() && x < std::prev(it)->second.right) --it;
		return it;
	}
	std::optional<V> get(T x) const {
		auto it = find(x);
		return it == end() ? std::nullopt : std::optional<V>(it->second.value);
	}
	const V &at(T x) const { auto it = find(x); assert(it != end()); return it->second.value; }
	bool contains(T x) const { return find(x) != end(); }
	bool contains(T l, T r) const {
		assert(l <= r);
		if (l == r) return true;
		auto it = find(l);
		if (it == end()) return false;
		T right = it->second.right;
		while (right < r) {
			++it;
			if (it == end() || right != it->first) return false;
			right = it->second.right;
		}
		return true;
	}
	bool contains(T l, T r, const V &value) const {
		assert(l <= r);
		if (l == r) return true;
		auto it = find(l);
		return it != end() && r <= it->second.right && equal(it->second.value, value);
	}
	bool intersects(T l, T r) const {
		assert(l <= r);
		if (l == r) return false;
		auto it = lower_bound(l);
		return it != end() && it->first < r;
	}
	template<class F> void for_each(T l, T r, F &&visit) const {
		assert(l <= r);
		if (l == r) return;
		for (auto it = lower_bound(l); it != end() && it->first < r; ++it)
			std::invoke(visit, (std::max)(l, it->first), (std::min)(r, it->second.right), it->second.value);
	}
	size_type count(T l, T r) const {
		size_type result = 0;
		for_each(l, r, [&](const T &a, const T &b, const V &) { result += length(a, b); });
		return result;
	}
	size_type size() const { return total; }
	std::size_t interval_count() const { return ranges.size(); }
	bool empty() const { return ranges.empty(); }
	const_iterator begin() const { return ranges.begin(); }
	const_iterator end() const { return ranges.end(); }
	const_reverse_iterator rbegin() const { return ranges.rbegin(); }
	const_reverse_iterator rend() const { return ranges.rend(); }
	void clear() { ranges.clear(); total = 0; }
	void swap(IntervalMap &other) noexcept(std::is_nothrow_swappable_v<Size> && std::is_nothrow_swappable_v<Equal>) {
		ranges.swap(other.ranges);
		using std::swap;
		swap(total, other.total); swap(equal, other.equal);
	}
	friend void swap(IntervalMap &a, IntervalMap &b) noexcept(noexcept(a.swap(b))) { a.swap(b); }
};

#endif

Back to top page