new tests

2 files changed, 297 insertions, 0 deletions

diff --git a/test/graph/connect.cpp b/test/graph/connect.cpp
new file mode 100644
index 0000000..065e21f
--- /dev/null
+++ b/test/graph/connect.cpp
@@ -0,0 +1,124 @@
+#include "../util.h"
+#pragma GCC diagnostic ignored "-Wshadow"
+#include "connectMinLCT.h"
+constexpr ll INF = 0x3FFF'FFFF;
+#include <graph/connect.cpp>
+
+struct Naive {
+	vector<multiset<int>> adj;
+	vector<int> seen;
+	int counter;
+	Naive(int n) : adj(n), seen(n), counter(0) {}
+
+	template<typename F>
+	void dfs(int x, F&& f) {
+		counter++;
+		vector<int> todo = {x};
+		seen[x] = counter;
+		while (!todo.empty()) {
+			x = todo.back();
+			todo.pop_back();
+			f(x);
+			for (ll y : adj[x]) {
+				if (seen[y] != counter) {
+					seen[y] = counter;
+					todo.push_back(y);
+				}
+			}
+		}
+	}
+
+	bool connected(int a, int b) {
+		bool res = false;
+		dfs(a, [&](int x){res |= x == b;});
+		return res;
+	}
+
+	void addEdge(int a, int b) {
+		adj[a].insert(b);
+		adj[b].insert(a);
+	}
+
+	void eraseEdge(int a, int b) {
+		adj[a].erase(adj[a].find(b));
+		adj[b].erase(adj[b].find(a));
+	}
+};
+
+void stress_test() {
+	ll queries = 0;
+	for (int tries = 0; tries < 2'000; tries++) {
+		int n = Random::integer<int>(2, 30);
+		int m = Random::integer<int>(30, 300);
+
+		vector<int> insertOrder(m);
+		iota(all(insertOrder), 0);
+		shuffle(all(insertOrder), Random::rng);
+		vector<pair<int, int>> edges(m, {-1, -1});
+
+		connect con(n, m);
+		Naive naive(n);
+
+		int deleted = 0;
+		for (int i = 0; i < m; i++) {
+			{
+				int a = Random::integer<int>(0, n);
+				int b = a;
+				while (b == a) b = Random::integer<int>(0, n);
+				edges[insertOrder[i]] = {a, b};
+
+				con.addEdge(a, b, insertOrder[i]);
+				naive.addEdge(a, b);
+			}
+
+			while (deleted < m && edges[deleted] != pair<int, int>{-1, -1} && Random::integer<int>(2) == 0) {
+				auto [a, b] = edges[deleted];
+
+				con.eraseEdge(deleted);
+				naive.eraseEdge(a, b);
+				deleted++;
+			}
+
+			for (int j = 0; j < n; j++) {
+				int a = Random::integer<int>(0, n);
+				int b = Random::integer<int>(0, n);
+
+				auto got = con.connected(a, b);
+				auto expected = naive.connected(a, b);
+
+				if (got != expected) cerr << "error" << FAIL;
+			}
+
+			queries += n;
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 2'000'000;
+void performance_test() {
+	/*timer t;
+	t.start();
+	UF uf(N);
+	t.stop();
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		int i = Random::integer<int>(0, N);
+		int j = Random::integer<int>(0, N);
+		int k = Random::integer<int>(0, N);
+		int l = Random::integer<int>(0, N);
+		
+		t.start();
+		uf.unionSets(i, j);
+		hash += uf.size(k);
+		hash += uf.size(l);
+		t.stop();
+	}
+	if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;*/
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
diff --git a/test/graph/connectMinLCT.h b/test/graph/connectMinLCT.h
new file mode 100644
index 0000000..4d509f7
--- /dev/null
+++ b/test/graph/connectMinLCT.h
@@ -0,0 +1,173 @@
+constexpr ll queryDefault = 0x3FFF'FFFF;
+constexpr ll updateDefault = 0;
+//modifiable:
+ll _modify(ll x, ll y) {
+	return min(x, y);
+}
+ll _query(ll x, ll y) {
+	return min(x, y);
+}
+ll _update(ll delta, int /*length*/) {
+	return delta;
+}
+
+//generic:
+ll joinValueDelta(ll value, ll delta) {
+	if (delta == updateDefault) return value;
+	return _modify(value, delta);
+}
+
+ll joinDeltas(ll delta1, ll delta2) {
+	if (delta1 == updateDefault) return delta2;
+	if (delta2 == updateDefault) return delta1;
+	return _modify(delta1, delta2);
+}
+
+struct LCT {
+	struct Node {
+		ll nodeValue, subTreeValue, delta;
+		bool revert;
+		int id, size;
+		Node *left, *right, *parent;
+
+		Node(int id = 0, int val = queryDefault) :
+			nodeValue(val), subTreeValue(val), delta(updateDefault),
+			revert(false), id(id), size(1),
+			left(nullptr), right(nullptr), parent(nullptr) {}
+
+		bool isRoot() {
+			return !parent || (parent->left != this &&
+			                   parent->right != this);
+		}
+
+		void push() {
+			if (revert) {
+				revert = false;
+				swap(left, right);
+				if (left) left->revert ^= 1;
+				if (right) right->revert ^= 1;
+			}
+			nodeValue = joinValueDelta(nodeValue, delta);
+			subTreeValue = joinValueDelta(subTreeValue,
+			                              _update(delta, size));
+			if (left) left->delta = joinDeltas(left->delta, delta);
+			if (right) right->delta = joinDeltas(right->delta, delta);
+			delta = updateDefault;
+		}
+
+		ll getSubtreeValue() {
+			return joinValueDelta(subTreeValue, _update(delta, size));
+		}
+
+		void update() {
+			subTreeValue = joinValueDelta(nodeValue, delta);
+			size = 1;
+			if (left) {
+				subTreeValue = _query(subTreeValue,
+				                      left->getSubtreeValue());
+				size += left->size;
+			}
+			if (right) {
+				subTreeValue = _query(subTreeValue,
+				                      right->getSubtreeValue());
+				size += right->size;
+		}}
+	};
+
+	vector<Node> nodes;
+
+	LCT(int n) : nodes(n) {
+		for (int i = 0; i < n; i++) nodes[i].id = i;
+	}
+
+	void connect(Node* ch, Node* p, int isLeftChild) {
+		if (ch) ch->parent = p;
+		if (isLeftChild >= 0) {
+			if (isLeftChild) p->left = ch;
+			else p->right = ch;
+	}}
+
+	void rotate(Node* x) {
+		Node* p = x->parent;
+		Node* g = p->parent;
+		bool isRootP = p->isRoot();
+		bool leftChildX = (x == p->left);
+
+		connect(leftChildX ? x->right : x->left, p, leftChildX);
+		connect(p, x, !leftChildX);
+		connect(x, g, isRootP ? -1 : p == g->left);
+		p->update();
+	}
+
+	void splay(Node* x) {
+		while (!x->isRoot()) {
+			Node* p = x->parent;
+			Node* g = p->parent;
+			if (!p->isRoot()) g->push();
+			p->push();
+			x->push();
+			if (!p->isRoot()) rotate((x == p->left) ==
+			                         (p == g->left) ?  p : x);
+			rotate(x);
+		}
+		x->push();
+		x->update();
+	}
+
+	Node* expose(Node* x) {
+		Node* last = nullptr;
+		for (Node* y = x; y; y = y->parent) {
+			splay(y);
+			y->left = last;
+			last = y;
+		}
+		splay(x);
+		return last;
+	}
+
+	void makeRoot(Node* x) {
+		expose(x);
+		x->revert ^= 1;
+	}
+
+	bool connected(Node* x, Node* y) {
+		if (x == y) return true;
+		expose(x);
+		expose(y);
+		return x->parent;
+	}
+
+	void link(Node* x, Node* y) {
+		assert(!connected(x, y)); // not yet connected!
+		makeRoot(x);
+		x->parent = y;
+	}
+
+	void cut(Node* x, Node* y) {
+		makeRoot(x);
+		expose(y);
+		//must be a tree edge!
+		assert(!(y->right != x || x->left != nullptr));
+		y->right->parent = nullptr;
+		y->right = nullptr;
+	}
+
+	Node* lca(Node* x, Node* y) {
+		assert(connected(x, y));
+		expose(x);
+		return expose(y);
+	}
+
+	ll query(Node* from, Node* to) {
+		makeRoot(from);
+		expose(to);
+		if (to) return to->getSubtreeValue();
+		return queryDefault;
+	}
+
+	void modify(Node* from, Node* to, ll delta) {
+		makeRoot(from);
+		expose(to);
+		to->delta = joinDeltas(to->delta, delta);
+	}
+};