Persistent Rope Core

components/persistent_rope.hpp · GitHub で見る

共通ページ

重み付きの断片列を、節点を共有する永続 AVL 木で管理する内部部品です。永続 deque の更新や、動的パターン照合 の部分文字列の分割・連結・コピーに使います。

#include "lib/components/persistent_rope.hpp"
#include <string>

std::uint64_t length(const std::string &s) { return s.size(); }

int main() {
	PersistentRope<std::string, length> rope;
	int original = rope.build(std::vector<std::string>{"ab", "cde"});
	auto [left, right] = rope.split(original, 3, [](const std::string &s, std::uint64_t p) {
		return std::pair{s.substr(0, p), s.substr(p)};
	});
	int changed = rope.join(right, left);
	std::string text;
	rope.for_each(changed, [&](const std::string &s) { text += s; });
	assert(text == "deabc" && rope.size(original) == 5);
	auto [chunk, offset] = rope.at(original, 2);
	assert(chunk == "cde" && offset == 0);
	PersistentRope<std::string, length> compact;
	int copied = compact.copy_from(rope, changed);
	assert(compact.size(copied) == 5);
}

木の根は int の節点番号で持ちます。0 は空の列です。木自身は現在の根を保持しないため、利用側で根番号を保存します。make・build・join・split などは新しい根を返し、以前の根の内容を変更しません。根番号を再利用して同じ列を何度も連結できます。

T はデフォルト構築・コピー・代入できる型にし、weight(value) は断片の正の整数の重みを返す関数にします。重みと列全体の重みは uint64_t に収めてください。位置は断片の個数ではなく、先頭からの重みの合計で指定します。

split(root,p,splitter) は重みの合計が p となる位置で分割します。0 <= p <= size(root) が必要です。断片の途中で分割するときだけ splitter(value,offset) を呼びます。返す pair<T,T> の重みは、それぞれ offset と weight(value)-offset にしてください。断片の境界では呼びません。at(root,p) は、その位置を含む断片と、断片内の重みのオフセットを返します。

insert は 0 <= p <= size(root)、erase は 0 <= l <= r <= size(root) とします。どちらも断片の途中を操作するときだけ、split と同じ条件の splitter を呼びます。replace は p < size(root) が必要で、位置を含む断片全体を置き換えます。新しい値の重みは、その断片の重みと同じにしてください。

根番号は、その節点を保持する同じインスタンスで使います。別のインスタンスへ移す場合は copy_from を使います。不要になった節点は自動で回収せず、build でも既存の領域は残ります。新しいインスタンスへ copy_from すると、指定した根から到達する節点だけを、共有関係を保って移せます。保持する節点数は INT_MAX 未満にしてください。

\(L\) を根からたどった列の断片数、\(A\) を保持する節点数、\(C\) を分割コールバックの時間とします。表は T のコピー・構築、weight、訪問コールバックが定数時間の場合です。文字列などを T にする場合は、そのコピー時間も加わります。† は節点配列の伸長を含む償却計算量です。

操作	内容・返り値	計算量
PersistentRope<T,weight>()	空の節点領域を作る。空列の根は 0	\(O(1)\)
make(value)	断片 1 つから葉を作り、根番号を返す	† \(O(1)\)
build(values)	vector<T> の断片列から木を作り、根番号を返す	† \(O(L)\)
join(a,b)	2 つの根の列をこの順に連結した根番号	† \(O(\log L)\)
split(root,p,splitter)	分割後の左・右の根番号の組	† \(O(\log L+C)\)
replace(root,p,value)	位置 p を含む断片を、同じ重みの value に置き換えた根番号	† \(O(\log L)\)
insert(root,p,value,splitter)	位置 p に断片を挿入した根番号	† \(O(\log L+C)\)
erase(root,l,r,splitter)	重みの区間 [l,r) を削除した根番号	† \(O(\log L+C)\)
size(root)	列の重みの合計。根 0 なら 0	\(O(1)\)
storage_nodes()	このインスタンスが保持する節点数	\(O(1)\)
leaf(node)	葉か。leaf(0) は false	\(O(1)\)
value(node)	葉が持つ断片をコピーして返す	\(O(1)\)
front(root) / back(root)	先頭 / 末尾の断片をコピーして返す	\(O(\log L)\)
pop_front(root)	先頭の断片と、残りの列の根番号の組	† \(O(\log L)\)
pop_back(root)	残りの列の根番号と、末尾の断片の組	† \(O(\log L)\)
at(root,p)	位置を含む断片と、その断片内のオフセットの組	\(O(\log L)\)
for_each(root,visitor)	左から各断片に visitor(value) を呼ぶ	\(O(L)\)
copy_from(other,root)	別の領域から共有を保ってコピーし、コピー先の根を返す	† \(O(A)\) 時間・追加空間。ここではコピー元の保持数
コピー構築・コピー代入	節点領域全体をコピー。同じ根番号をコピー先でも使える	\(O(A)\)。代入は旧領域の解放も加わる
ムーブ構築・ムーブ代入	節点領域を移動	構築 \(O(1)\)。代入は旧領域の解放も加わる

value は葉にだけ、front・back・pop_front・pop_back は空でない根にだけ使います。at は p < size(root) が必要です。copy_from のコピー元は別のインスタンスにしてください。ムーブ後の根は移動先で使います。

共有している断片も for_each では列中に現れる回数だけ訪問します。断片の共有を繰り返すと、列の断片数は保持節点数よりはるかに大きくなり得ます。保持空間は \(O(A)\)、連結・分割などで追加する節点数は \(O(\log L)\) です。対数の項は断片数が 0・1 の場合に定数として扱います。

検証コード

• test/dynamic_pattern_matching_array.test.cpp
• test/persistent_deque.test.cpp

コード

#ifndef PERSISTENT_ROPE_HPP
#define PERSISTENT_ROPE_HPP

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>

template<class T, auto weight> class PersistentRope {
	struct Node {
		std::uint64_t size;
		int left, right, height;
		T value;
	};
	std::vector<Node> nodes_{{0, 0, 0, 0, T{}}};
	int height(int v) const { return nodes_[v].height; }
	int append(Node node) {
		assert(nodes_.size() < std::size_t(std::numeric_limits<int>::max()));
		nodes_.push_back(std::move(node));
		return static_cast<int>(nodes_.size()) - 1;
	}
	int branch(int a, int b) {
		if (!a) return b;
		if (!b) return a;
		assert(size(a) <= std::numeric_limits<std::uint64_t>::max() - size(b));
		return append({size(a) + size(b), a, b, std::max(height(a), height(b)) + 1, T{}});
	}
	int balance(int a, int b) {
		if (height(a) > height(b) + 1) {
			int left = nodes_[a].left, right = nodes_[a].right;
			if (height(left) >= height(right)) return branch(left, branch(right, b));
			int middle_left = nodes_[right].left, middle_right = nodes_[right].right;
			return branch(branch(left, middle_left), branch(middle_right, b));
		}
		if (height(b) > height(a) + 1) {
			int left = nodes_[b].left, right = nodes_[b].right;
			if (height(right) >= height(left)) return branch(branch(a, left), right);
			int middle_left = nodes_[left].left, middle_right = nodes_[left].right;
			return branch(branch(a, middle_left), branch(middle_right, right));
		}
		return branch(a, b);
	}

  public:
	std::uint64_t size(int v) const { return nodes_[v].size; }
	std::size_t storage_nodes() const { return nodes_.size() - 1; }
	bool leaf(int v) const { return v && !nodes_[v].left; }
	T value(int v) const { assert(leaf(v)); return nodes_[v].value; }
	int make(T value) {
		auto length = std::uint64_t(weight(value));
		assert(length);
		return append({length, 0, 0, 1, std::move(value)});
	}
	int join(int a, int b) {
		if (!a || !b) return a ? a : b;
		if (height(a) > height(b) + 1) {
			int left = nodes_[a].left, right = nodes_[a].right;
			return balance(left, join(right, b));
		}
		if (height(b) > height(a) + 1) {
			int left = nodes_[b].left, right = nodes_[b].right;
			return balance(join(a, left), right);
		}
		return branch(a, b);
	}
	int build(const std::vector<T> &values) {
		auto visit = [&](auto &&self, std::size_t l, std::size_t r) -> int {
			if (l == r) return 0;
			if (r - l == 1) return make(values[l]);
			auto m = l + (r - l) / 2;
			int a = self(self, l, m), b = self(self, m, r);
			return branch(a, b);
		};
		return visit(visit, 0, values.size());
	}
	template<class Splitter> std::pair<int, int> split(int v, std::uint64_t p, const Splitter &splitter) {
		assert(p <= size(v));
		if (!p) return {0, v};
		if (p == size(v)) return {v, 0};
		int left = nodes_[v].left, right = nodes_[v].right;
		if (!left) {
			T value = nodes_[v].value;
			auto [a, b] = splitter(value, p);
			int l = make(std::move(a)), r = make(std::move(b));
			return {l, r};
		}
		auto k = size(left);
		if (p == k) return {left, right};
		if (p < k) {
			auto [a, b] = split(left, p, splitter);
			return {a, join(b, right)};
		}
		auto [a, b] = split(right, p - k, splitter);
		return {join(left, a), b};
	}
	int replace(int v, std::uint64_t p, T value) {
		assert(p < size(v));
		int a = nodes_[v].left, b = nodes_[v].right;
		if (!a) { assert(std::uint64_t(weight(value)) == size(v)); return make(std::move(value)); }
		if (p < size(a)) a = replace(a, p, std::move(value));
		else b = replace(b, p - size(a), std::move(value));
		return branch(a, b);
	}
	template<class Splitter> int insert(int v, std::uint64_t p, T value, const Splitter &splitter) {
		assert(p <= size(v));
		if (!v) return make(std::move(value));
		int a = nodes_[v].left, b = nodes_[v].right;
		if (!a) {
			if (!p) return branch(make(std::move(value)), v);
			if (p == size(v)) return branch(v, make(std::move(value)));
			auto [left, right] = split(v, p, splitter);
			int middle = make(std::move(value));
			return join(join(left, middle), right);
		}
		if (p <= size(a)) a = insert(a, p, std::move(value), splitter);
		else b = insert(b, p - size(a), std::move(value), splitter);
		return balance(a, b);
	}
	template<class Splitter> int erase(int v, std::uint64_t l, std::uint64_t r, const Splitter &splitter) {
		assert(l <= r && r <= size(v));
		if (l == r) return v;
		if (!l && r == size(v)) return 0;
		int a = nodes_[v].left, b = nodes_[v].right;
		if (!a) {
			if (!l) return split(v, r, splitter).second;
			if (r == size(v)) return split(v, l, splitter).first;
			auto [left, rest] = split(v, l, splitter);
			int right = split(rest, r - l, splitter).second;
			return join(left, right);
		}
		auto k = size(a);
		if (r <= k) a = erase(a, l, r, splitter);
		else if (l >= k) b = erase(b, l - k, r - k, splitter);
		else {
			a = erase(a, l, k, splitter);
			b = erase(b, 0, r - k, splitter);
		}
		return join(a, b);
	}

	T front(int v) const { assert(v); while (nodes_[v].left) v = nodes_[v].left; return value(v); }
	T back(int v) const { assert(v); while (nodes_[v].right) v = nodes_[v].right; return value(v); }
	std::pair<T, int> pop_front(int v) {
		assert(v);
		int left = nodes_[v].left, right = nodes_[v].right;
		if (!left) return {value(v), 0};
		auto [value, rest] = pop_front(left);
		return {std::move(value), join(rest, right)};
	}
	std::pair<int, T> pop_back(int v) {
		assert(v);
		int left = nodes_[v].left, right = nodes_[v].right;
		if (!right) return {0, value(v)};
		auto [rest, value] = pop_back(right);
		return {join(left, rest), std::move(value)};
	}
	std::pair<T, std::uint64_t> at(int v, std::uint64_t p) const {
		assert(p < size(v));
		while (int left = nodes_[v].left) {
			int right = nodes_[v].right;
			auto length = size(left);
			if (p < length) v = left;
			else p -= length, v = right;
		}
		return {value(v), p};
	}
	template<class Visitor> void for_each(int v, const Visitor &visitor) const {
		if (!v) return;
		if (leaf(v)) { visitor(value(v)); return; }
		for_each(nodes_[v].left, visitor);
		for_each(nodes_[v].right, visitor);
	}
	int copy_from(const PersistentRope &other, int root) {
		assert(this != &other);
		std::vector<int> mapped(other.nodes_.size(), 0);
		auto visit = [&](auto &&self, int v) -> int {
			if (!v || mapped[v]) return mapped[v];
			auto x = other.nodes_[v];
			if (x.left) {
				x.left = self(self, x.left);
				x.right = self(self, x.right);
			}
			return mapped[v] = append(std::move(x));
		};
		return visit(visit, root);
	}
};

#endif

Back to top page