Partially Retroactive Priority Queue

data_structure/partially_retroactive_priority_queue.hpp · GitHub で見る

共通ページ

#include "lib/data_structure/partially_retroactive_priority_queue.hpp"

PartiallyRetroactivePriorityQueue<long long> queue;
queue.insert(10, 5);
queue.insert(20, 2);
queue.insert_pop(30);
auto now = queue.top();
queue.set(10, 1);
queue.erase(30);

現在の要素集合の総和などは、変更通知を使って外部で管理できます。

long long sum = 0;
auto changed = [&](std::int64_t, const long long &value, bool added) {
	sum += added ? value : -value;
};
PartiallyRetroactivePriorityQueue<long long> queue;
queue.insert(10, 5, changed);     // sum = 5
queue.insert(20, 2, changed);     // sum = 7
queue.insert_pop(30, changed);   // sum = 5
queue.set(10, 1, changed);       // sum = 2
queue.erase(30, changed);        // sum = 3

PartiallyRetroactivePriorityQueue<T, Compare = std::less<T>, Time = std::int64_t> は、過去の操作を変更し、現在の状態をクエリる優先度付きキューです。std::less<T> では最小値、std::greater<T> では最大値を先頭にします。同順位の要素は挿入時刻順です。時刻は64 bit以下の整数で、各時刻に置ける操作は1つです。

操作	内容・返り値	計算量
PartiallyRetroactivePriorityQueue(compare = {},seed = 0)	空の履歴を構築	\(O(1)\)
PartiallyRetroactivePriorityQueue(updates,compare = {},seed = 0)	有効な操作履歴から構築	\(O(m\log m)\)
insert(t,x)	時刻 t に push(x) を追加	償却期待 \(O(\log m)\)
insert_pop(t)	時刻 t に先頭要素の削除を追加	償却期待 \(O(\log m)\)
set(t,x)	既存の push の値を変更	償却期待 \(O(\log m)\)
erase(t)	時刻 t の操作を取り消す	償却期待 \(O(\log m)\)
insert(t,x,f) / insert_pop(t,f)	操作を追加し、現在の集合の変化を f に通知	償却期待 \(O(\log m)\)
set(t,x,f) / erase(t,f)	操作を変更・取消し、現在の集合の変化を f に通知	償却期待 \(O(\log m)\)
top()	現在の先頭を optional<T> で取得。空なら nullopt	\(O(1)\)
size() / empty()	現在の要素数／空判定	\(O(1)\)
contains_time(t) / operation_count()	時刻 t の操作の有無／操作数	contains_time: 期待 \(O(\log m)\)、operation_count: \(O(1)\)
assign(updates)	操作履歴をまとめて設定。無効なら false を返して元の履歴を保つ	\(O(M+m\log m)\)
assign(updates,f)	履歴を設定し、旧集合の削除・新集合の追加を通知。無効なら通知しない	\(O(M+m\log m)\)
reserve(m) / clear()	領域予約／容量を残して履歴を初期化	\(O(M)\)
clear(f)	現在の全要素の削除を通知して初期化	\(O(M)\)
for_each(f)	現在の全要素について f(挿入時刻,const T&) を挿入時刻順に呼ぶ	\(O(m)\)
memory_usage()	確保済み領域のバイト数	\(O(1)\)
swap(other)	内容・比較関数・乱数生成器の状態を交換	\(O(1)\)
top_ptr()	現在の先頭の const T*。空なら nullptr。次の変更操作まで有効	\(O(1)\)

履歴変更は成功時に true を返します。時刻の衝突、対象操作の不在、set の対象が pop の場合や、空キューへの削除が発生する変更は false を返し、履歴を保ちます。

変更通知は f(挿入時刻,const T&,bool added) です。added=true は現在の集合への追加、false は現在の集合からの削除です。指定した操作の値ではなく、過去の変更の結果として現在の集合で増減する要素を通知します。同じ値も挿入時刻で区別でき、総和・XOR・頻度・外部の集合などを管理できます。コールバックは呼び出しごとに渡し、キューには保存しません。コピーできないコールバックにも対応します。

insert・insert_pop・erase は成功時に 1 要素、set は削除・追加を各高々 1 要素通知します。set は削除を先に通知し、内部の一時的な追加と削除は通知しません。変更を拒否した場合は通知しません。assign は同じ要素でも旧集合から一度削除して新集合へ追加します。既存のキューから集計を始める場合は for_each で初期化できます。継続して集計する場合は、全ての変更に同じ通知処理を渡してください。swap・コピー・ムーブ・通知なしの変更は通知しません。

通知中の参照はその呼び出し中だけ有効です。コールバックから同じキューを参照・変更したり、例外を投げたりしないでください。

updates は std::vector<Queue::update_type> で、要素は {時刻, std::optional<T>}、nullopt は削除操作です。順不同で渡せます。Queue(updates, compare = Compare{}, seed = 0) による構築には有効な履歴を渡します。空列の構築は Queue(compare = Compare{}, seed = 0) です。top_ptr() の戻り値は次の変更操作まで使用できます。削除ノードは再利用し、clear() は確保容量を残します。

操作数を \(m\)、過去の最大操作数を \(M\) とします。履歴変更は償却期待 \(O(\log m)\)、contains_time は期待 \(O(\log m)\)、現在のクエリ・operation_count・memory_usage は \(O(1)\)、構築は \(O(m\log m)\)、assign は \(O(M+m\log m)\)、reserve・clear は \(O(M)\)、for_each は \(O(m)\) です。変更通知付きも通知処理が \(O(1)\) なら同じ計算量です。空間は \(O(M)\)（予約容量が大きい場合はその容量分）です。比較・値のコピーを \(O(1)\) とします。

依存ライブラリ

• SplitMix64

検証コード

• test/partially_retroactive_priority_queue.test.cpp

コード

#ifndef PARTIALLY_RETROACTIVE_PRIORITY_QUEUE_HPP
#define PARTIALLY_RETROACTIVE_PRIORITY_QUEUE_HPP

#include "../components/splitmix64.hpp"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <optional>
#include <type_traits>
#include <utility>
#include <vector>

template <class T, class Compare = std::less<T>, class Time = std::int64_t>
class PartiallyRetroactivePriorityQueue {
	static_assert(std::is_integral_v<Time> && !std::is_same_v<Time, bool> && sizeof(Time) <= 8);
	struct Ignore { void operator()(Time, const T &, bool) const {} };
	struct Node {
		Time time{};
		std::optional<T> value;
		int left = 0, right = 0, size = 0, sum = 0, low = 0, count = 0, minimum_count = 0, alive = 0, dead = 0;
		std::uint32_t priority = 0;
		int state = 0;
	};
	std::vector<Node> nodes{1};
	[[no_unique_address]] Compare compare;
	SplitMix64 rng;
	int root = 0, free = 0;
	bool less(int a, int b) const {
		if (compare(*nodes[a].value, *nodes[b].value)) return true;
		if (compare(*nodes[b].value, *nodes[a].value)) return false;
		return nodes[a].time < nodes[b].time;
	}
	int smaller(int a, int b) const { return !a ? b : !b || less(a, b) ? a : b; }
	int larger(int a, int b) const { return !a ? b : !b || less(b, a) ? a : b; }
	void pull(int x) {
		auto &n = nodes[x];
		const auto &a = nodes[n.left], &b = nodes[n.right];
		int c = n.value ? 1 : -1;
		n.size = a.size + 1 + b.size;
		n.sum = a.sum + n.state + b.sum;
		n.low = std::min(a.low, a.sum + n.state + b.low);
		n.count = a.count + c + b.count;
		n.minimum_count = std::min(a.minimum_count, a.count + c + b.minimum_count);
		n.alive = smaller(smaller(a.alive, n.value && n.state == 0 ? x : 0), b.alive);
		n.dead = larger(larger(a.dead, n.state == 1 ? x : 0), b.dead);
	}
	int make(Time time, std::optional<T> value) {
		int x;
		if (free) { x = free; free = nodes[x].left; nodes[x] = Node{}; }
		else {
			assert(nodes.size() < std::size_t(std::numeric_limits<int>::max()));
			x = nodes.size(); nodes.emplace_back();
		}
		nodes[x].time = time;
		nodes[x].value = std::move(value);
		nodes[x].priority = std::uint32_t(rng());
		nodes[x].state = nodes[x].value ? 0 : -1;
		pull(x);
		return x;
	}
	int merge(int a, int b) {
		if (!a || !b) return a | b;
		if (nodes[a].priority > nodes[b].priority) {
			nodes[a].right = merge(nodes[a].right, b); pull(a); return a;
		}
		nodes[b].left = merge(a, nodes[b].left); pull(b); return b;
	}
	std::pair<int, int> split(int x, int k) {
		if (!x) return {0, 0};
		int n = nodes[nodes[x].left].size;
		if (k <= n) {
			auto [a, b] = split(nodes[x].left, k);
			nodes[x].left = b; pull(x); return {a, x};
		}
		auto [a, b] = split(nodes[x].right, k - n - 1);
		nodes[x].right = a; pull(x); return {x, b};
	}
	std::pair<int, int> locate(Time time) const {
		int x = root, rank = 0;
		while (x) {
			if (time < nodes[x].time) x = nodes[x].left;
			else {
				int n = nodes[nodes[x].left].size;
				if (time == nodes[x].time) return {rank + n, x};
				rank += n + 1; x = nodes[x].right;
			}
		}
		return {rank, 0};
	}
	int bridge_dead(int x, int offset) const {
		if (!x) return 0;
		int a = nodes[x].left, b = nodes[x].right;
		int after = offset + nodes[a].sum + nodes[x].state;
		if (after + nodes[b].low == 0) return bridge_dead(b, after);
		return larger(larger(bridge_dead(a, offset), nodes[x].state == 1 ? x : 0), nodes[b].dead);
	}
	int bridge_alive(int x, int offset) const {
		if (offset == 0) return 0;
		assert(x);
		int a = nodes[x].left;
		if (offset + nodes[a].low == 0) return bridge_alive(a, offset);
		int after = offset + nodes[a].sum + nodes[x].state;
		return smaller(smaller(nodes[a].alive, nodes[x].value && nodes[x].state == 0 ? x : 0), bridge_alive(nodes[x].right, after));
	}
	void change(int x, int key, int state) {
		assert(x);
		if (x == key) nodes[x].state = state;
		else change(nodes[key].time < nodes[x].time ? nodes[x].left : nodes[x].right, key, state);
		pull(x);
	}
	struct Selection { int tree, key; };
	Selection promote(int a, int b) const {
		int key = bridge_dead(a, 0);
		return larger(key, nodes[b].dead) == key ? Selection{a, key} : Selection{b, nodes[b].dead};
	}
	Selection demote(int a, int b, int offset) const {
		int key = bridge_alive(b, offset);
		return smaller(nodes[a].alive, key) == key ? Selection{b, key} : Selection{a, nodes[a].alive};
	}
	void change(Selection selected, int state) { change(selected.tree, selected.key, state); }
	int insert_push(int a, int b, int x) {
		auto selected = promote(a, b);
		int added = x;
		if (selected.key && less(x, selected.key)) {
			change(selected, 0); nodes[x].state = 1; pull(x);
			added = selected.key;
		}
		root = merge(merge(a, x), b);
		return added;
	}
	template <class F> bool erase_at(int rank, F &&on_change) {
		auto [a, tail] = split(root, rank);
		auto [x, b] = split(tail, 1);
		if (nodes[x].value && nodes[a].count + nodes[b].minimum_count < 0) {
			root = merge(merge(a, x), b); return false;
		}
		int changed = x;
		bool added = nodes[x].state == -1;
		if (added) {
			auto selected = promote(a, b);
			changed = selected.key; change(selected, 0);
		} else if (nodes[x].state == 1) {
			auto selected = demote(a, b, nodes[a].sum + 1);
			changed = selected.key; change(selected, 1);
		}
		root = merge(a, b);
		on_change(changed, added);
		nodes[x].value.reset(); nodes[x].left = free; free = x;
		return true;
	}
	template <class F> void visit(int x, F &f) const {
		if (!nodes[x].alive) return;
		visit(nodes[x].left, f);
		if (nodes[x].value && nodes[x].state == 0) f(nodes[x].time, *nodes[x].value);
		visit(nodes[x].right, f);
	}
	template <class F> void notify(int x, bool added, F &f) const { f(nodes[x].time, *nodes[x].value, added); }
public:
	using update_type = std::pair<Time, std::optional<T>>;
	explicit PartiallyRetroactivePriorityQueue(Compare compare = Compare{}, std::uint64_t seed = 0) : compare(std::move(compare)), rng(seed) {}
	PartiallyRetroactivePriorityQueue(const std::vector<update_type> &updates, Compare compare = Compare{}, std::uint64_t seed = 0)
		: PartiallyRetroactivePriorityQueue(std::move(compare), seed) {
		[[maybe_unused]] bool ok = assign(updates);
		assert(ok);
	}
	PartiallyRetroactivePriorityQueue(const PartiallyRetroactivePriorityQueue &) = default;
	PartiallyRetroactivePriorityQueue &operator=(const PartiallyRetroactivePriorityQueue &) = default;
	PartiallyRetroactivePriorityQueue(PartiallyRetroactivePriorityQueue &&other) : PartiallyRetroactivePriorityQueue(other.compare) { swap(other); }
	PartiallyRetroactivePriorityQueue &operator=(PartiallyRetroactivePriorityQueue &&other) {
		if (this != &other) { PartiallyRetroactivePriorityQueue next(std::move(other)); swap(next); }
		return *this;
	}
	void swap(PartiallyRetroactivePriorityQueue &other) {
		using std::swap;
		nodes.swap(other.nodes); swap(compare, other.compare); swap(rng, other.rng); swap(root, other.root); swap(free, other.free);
	}
	bool insert(Time time, T value) { return insert(time, std::move(value), Ignore{}); }
	template <class F> bool insert(Time time, T value, F &&on_change) {
		auto [rank, found] = locate(time);
		if (found) return false;
		int x = make(time, std::move(value));
		auto [a, b] = split(root, rank);
		int added = insert_push(a, b, x);
		notify(added, true, on_change); return true;
	}
	bool insert_pop(Time time) { return insert_pop(time, Ignore{}); }
	template <class F> bool insert_pop(Time time, F &&on_change) {
		auto [rank, found] = locate(time);
		if (found) return false;
		auto [a, b] = split(root, rank);
		if (nodes[a].count + nodes[b].minimum_count < 1) { root = merge(a, b); return false; }
		auto selected = demote(a, b, nodes[a].sum);
		change(selected, 1);
		int x = make(time, std::nullopt);
		root = merge(merge(a, x), b);
		notify(selected.key, false, on_change); return true;
	}
	bool set(Time time, T value) { return set(time, std::move(value), Ignore{}); }
	template <class F> bool set(Time time, T value, F &&on_change) {
		auto [rank, found] = locate(time);
		if (!found || !nodes[found].value) return false;
		int x = make(time, std::move(value));
		auto [a, b] = split(root, rank);
		int added = insert_push(a, b, x);
		bool canceled = false;
		[[maybe_unused]] bool ok = erase_at(rank + 1, [&](int key, bool inserted) {
			assert(!inserted); (void)inserted;
			if (key == added) canceled = true;
			else notify(key, false, on_change);
		});
		assert(ok);
		if (!canceled) notify(added, true, on_change);
		return true;
	}
	bool erase(Time time) { return erase(time, Ignore{}); }
	template <class F> bool erase(Time time, F &&on_change) {
		auto [rank, found] = locate(time);
		return found && erase_at(rank, [&](int key, bool added) { notify(key, added, on_change); });
	}
	bool contains_time(Time time) const { return locate(time).second != 0; }
	const T *top_ptr() const { int x = nodes[root].alive; return x ? &*nodes[x].value : nullptr; }
	std::optional<T> top() const { auto p = top_ptr(); return p ? std::optional<T>(*p) : std::nullopt; }
	int size() const { return nodes[root].count; }
	bool empty() const { return size() == 0; }
	int operation_count() const { return nodes[root].size; }
	void reserve(std::size_t capacity) { nodes.reserve(capacity + 1); }
	void clear() { nodes.resize(1); root = free = 0; }
	template <class F> void clear(F &&on_change) {
		for_each([&](Time time, const T &value) { on_change(time, value, false); });
		clear();
	}
	template <class F> void for_each(F &&f) const { visit(root, f); }
	std::size_t memory_usage() const { return nodes.capacity() * sizeof(Node); }
	bool assign(const std::vector<update_type> &updates) { return assign(updates, Ignore{}); }
	template <class F> bool assign(const std::vector<update_type> &updates, F &&on_change) {
		auto sorted = updates;
		std::sort(sorted.begin(), sorted.end(), [](const auto &a, const auto &b) { return a.first < b.first; });
		int count = 0;
		for (std::size_t i = 0; i < sorted.size(); ++i) {
			if (i && sorted[i - 1].first == sorted[i].first) return false;
			count += sorted[i].second ? 1 : -1;
			if (count < 0) return false;
		}
		PartiallyRetroactivePriorityQueue next(compare, rng());
		next.reserve(sorted.size());
		std::vector<int> heap, stack;
		heap.reserve(count); stack.reserve(sorted.size());
		auto order = [&](int a, int b) { return next.less(b, a); };
		for (auto &[time, value] : sorted) {
			int x = next.make(time, std::move(value));
			if (next.nodes[x].value) {
				heap.push_back(x); std::push_heap(heap.begin(), heap.end(), order);
			} else {
				std::pop_heap(heap.begin(), heap.end(), order);
				next.nodes[heap.back()].state = 1; heap.pop_back();
			}
		}
		for (int x = 1; x < int(next.nodes.size()); ++x) {
			int left = 0;
			while (!stack.empty() && next.nodes[stack.back()].priority < next.nodes[x].priority) {
				left = stack.back(); stack.pop_back(); next.pull(left);
			}
			next.nodes[x].left = left;
			if (!stack.empty()) next.nodes[stack.back()].right = x;
			stack.push_back(x);
		}
		while (!stack.empty()) { next.root = stack.back(); next.pull(next.root); stack.pop_back(); }
		if constexpr (!std::is_same_v<std::remove_cvref_t<F>, Ignore>) {
			for_each([&](Time time, const T &value) { on_change(time, value, false); });
			next.for_each([&](Time time, const T &value) { on_change(time, value, true); });
		}
		swap(next); return true;
	}
};

#endif

Back to top page