From d7905f7dec9e306d7d6f907ce35abc40f24af1c5 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Tue, 30 Jul 2024 23:58:19 +0200
Subject: more tests

---
 test/datastructures/persistent.cpp      | 35 ++++++++++++++++++++++++
 test/datastructures/persistentArray.cpp | 48 +++++++++++++++++++++++++++++++++
 2 files changed, 83 insertions(+)
 create mode 100644 test/datastructures/persistent.cpp
 create mode 100644 test/datastructures/persistentArray.cpp

(limited to 'test/datastructures')

diff --git a/test/datastructures/persistent.cpp b/test/datastructures/persistent.cpp
new file mode 100644
index 0000000..4e304fa
--- /dev/null
+++ b/test/datastructures/persistent.cpp
@@ -0,0 +1,35 @@
+#include "../util.h"
+#pragma GCC diagnostic ignored "-Wshadow"
+#include <datastructures/persistent.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (int tries = 0; tries < 100'000; tries++) {
+		int n = Random::integer<int>(1, 30);
+
+		int timeRef = Random::integer<int>(1, 30);
+		persistent<double> got(timeRef);
+		map<int, double> expected;
+
+		for (int i = 0; i < n; i++) {
+			timeRef += Random::integer<int>(1, 30);
+			double x = Random::real<double>(-1'000, 1'000);
+			auto t = got.set(x);
+
+			if (!expected.empty() && t <= expected.rbegin()->first) cerr << "error: time travel" << FAIL;
+			expected[t] = x;
+		}
+
+		double tmp = 0;
+		for (int i = expected.begin()->first; i < expected.rbegin()->first + 10; i++) {
+			if (expected.find(i) != expected.end()) tmp = expected[i];
+			if (got.get(i) != tmp) cerr << "got: " << got.get(i) << ", " << "expected: " << tmp << FAIL;
+		}
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+int main() {
+	stress_test();
+}
diff --git a/test/datastructures/persistentArray.cpp b/test/datastructures/persistentArray.cpp
new file mode 100644
index 0000000..6712089
--- /dev/null
+++ b/test/datastructures/persistentArray.cpp
@@ -0,0 +1,48 @@
+#include "../util.h"
+#pragma GCC diagnostic ignored "-Wshadow"
+#include <datastructures/persistent.cpp>
+#include <datastructures/persistentArray.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (int tries = 0; tries < 2'000; tries++) {
+		int n = Random::integer<int>(1, 30)*1000;
+		int m = Random::integer<int>(1, 30);
+
+		persistentArray<double> got(m);
+		vector<double> cur(m);
+		vector<pair<int, vector<double>>> expected;
+		for (int i = 0; i < n; i++) {
+			int op = Random::integer<int>(0, 20);
+			if (op <= 10) {
+				int j = Random::integer<int>(0, m);
+				double x = Random::real<double>(-1'000, 1'000);
+
+				auto t = got.set(j, x);
+				if (!expected.empty() && t <= expected.rbegin()->first) cerr << "error: time travel" << FAIL;
+
+				cur[j] = x;
+				expected.emplace_back(t, cur);
+			} else if (op <= 16) {
+				if (sz(expected) < 1) continue;
+				int j = Random::integer<int>(0, sz(expected));
+				for (int k = 0; k < m; k++) {
+					if (got.get(k, expected[j].first) != expected[j].second[k]) cerr << "got: " << got.get(k, expected[j].first) << ", expected: " << expected[j].second[k] << FAIL;
+				}
+			} else {
+				if (sz(expected) < 1) continue;
+				int j = Random::integer<int>(0, sz(expected));
+				got.reset(expected[j].first);
+				expected.resize(j + 1);
+				cur = expected.back().second;
+			}
+			
+		}
+		queries += n;
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+int main() {
+	stress_test();
+}
-- 
cgit v1.2.3


From 2419f32f0d4b4884dc0fc7567efed7aa711036c3 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Fri, 2 Aug 2024 13:41:09 +0200
Subject: more tests

---
 test/datastructures/LCT.cpp | 198 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 198 insertions(+)
 create mode 100644 test/datastructures/LCT.cpp

(limited to 'test/datastructures')

diff --git a/test/datastructures/LCT.cpp b/test/datastructures/LCT.cpp
new file mode 100644
index 0000000..58d76d7
--- /dev/null
+++ b/test/datastructures/LCT.cpp
@@ -0,0 +1,198 @@
+#include "../util.h"
+#pragma GCC diagnostic ignored "-Wshadow"
+#include <datastructures/LCT.cpp>
+
+struct Naive {
+	vector<set<int>> adj;
+	vector<ll> weight;
+	Naive(int n) : adj(n), weight(n, queryDefault) {}
+
+	pair<ll, bool> dfs_path(int from, int to, ll delta = queryDefault, int prev = -1) {
+		if (from == to) {
+			weight[from] += delta;
+			return {weight[from], true};
+		}
+		for (int x : adj[from]) {
+			if (x == prev) continue;
+			auto [res, seen] = dfs_path(x, to, delta, from);
+			if (seen) {
+				weight[from] += delta;
+				return {res + weight[from], true};
+			}
+		}
+		return {queryDefault, false};
+	}
+
+	bool connected(int x, int y) {
+		return dfs_path(x, y).second;
+	}
+
+	void link(int x, int y) {
+		adj[x].insert(y);
+		adj[y].insert(x);
+	}
+
+	void cut(int x, int y) {
+		adj[x].erase(y);
+		adj[y].erase(x);
+	}
+
+	int lca(int root, int a, int b) {
+		int res = -1;
+		auto dfs_lca = [&](auto&& self, int c, int prev = -1) -> pair<bool, bool>{
+			bool seenA = c == a;
+			bool seenB = c == b;
+			for (int x : adj[c]) {
+				if (x == prev) continue;
+				auto [tmpA, tmpB] = self(self, x, c);
+				seenA |= tmpA;
+				seenB |= tmpB;
+			}
+			if (seenA && seenB && res < 0) res = c;
+			return {seenA, seenB};
+		};
+		dfs_lca(dfs_lca, root);
+		return res;
+	}
+
+	ll query(int from, int to) {
+		return dfs_path(from, to).first;
+	}
+
+	void modify(int from, int to, ll delta) {
+		dfs_path(from, to, delta);
+	}
+
+	int random(int x) {
+		vector<int> seen;
+		auto dfs_comp = [&](auto&& self, int c, int prev = -1) -> void {
+			seen.push_back(c);
+			for (int x : adj[c]) {
+				if (x == prev) continue;
+				self(self, x, c);
+			}
+		};
+		dfs_comp(dfs_comp, x);
+		return seen[Random::integer<int>(sz(seen))];
+	}
+
+	int randomAdj(int x) {
+		if (adj[x].empty()) return -1;
+		vector<int> seen(all(adj[x]));
+		return seen[Random::integer<int>(sz(seen))];
+	}
+};
+
+void stress_test() {
+	ll queries = 0;
+	ll connected = 0;
+	ll link = 0;
+	ll lca = 0;
+	ll sum = 0;
+	ll modify = 0;
+	ll cut = 0;
+	for (int tries = 0; tries < 500; tries++) {
+		int n = Random::integer<int>(1, 100);
+		int m = Random::integer<int>(100, 10'000);
+
+		LCT lct(n);
+		Naive naive(n);
+		for (int i = 0; i < m; i++) {
+			bool testConnected = Random::integer<int>(2) == 0;
+			bool testLink = Random::integer<int>(2) == 0;
+			bool testLCA = Random::integer<int>(2) == 0;
+			bool testSum = Random::integer<int>(2) == 0;
+			bool testModify = Random::integer<int>(2) == 0;
+			bool testCut = Random::integer<int>(2) == 0;
+
+			{
+				int a = Random::integer<int>(0, n);
+				int b = Random::integer<int>(0, n);
+
+				auto expected = naive.connected(a, b);
+				if (testConnected) {
+					connected++;
+					auto got = lct.connected(&lct.nodes[a], &lct.nodes[b]);
+					if (got != expected) cerr << "error: 1" << FAIL;
+				}
+
+				if (!expected && testLink) {
+					lct.link(&lct.nodes[a], &lct.nodes[b]);
+					naive.link(a, b);
+					link++;
+					expected = true;
+				}
+
+				if (testLCA && expected) {
+					int c = naive.random(a);
+					lct.makeRoot(&lct.nodes[c]);
+					auto gotLCA = lct.lca(&lct.nodes[a], &lct.nodes[b])->id;
+					auto expectedLCA = naive.lca(c, a, b);
+					if (gotLCA != expectedLCA) cerr << "error: 2" << FAIL;
+					lca++;
+				}
+
+				if (testSum && expected) {
+					auto gotSum = lct.query(&lct.nodes[a], &lct.nodes[b]);
+					auto expectedSum = naive.query(a, b);
+					if (gotSum != expectedSum) cerr << "error: 3" << FAIL;
+					sum++;
+				}
+
+				if (testModify && expected) {
+					ll w = Random::integer<ll>(-1000, 1000);
+					lct.modify(&lct.nodes[a], &lct.nodes[b], w);//must a and b directly connected??
+					naive.modify(a, b, w);
+					modify++;
+				}
+			}
+			{
+				int a = Random::integer<int>(0, n);
+				int b = naive.randomAdj(a);
+				if (b >= 0 && testCut) {
+					lct.cut(&lct.nodes[a], &lct.nodes[b]);
+					naive.cut(a, b);
+					cut++;
+				}
+			}
+			queries++;
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+	cerr << "  connected: " << connected << endl;
+	cerr << "  link: " << link << endl;
+	cerr << "  lca: " << lca << endl;
+	cerr << "  sum: " << sum << endl;
+	cerr << "  modify: " << modify << endl;
+	cerr << "  cut: " << cut << endl;
+}
+
+constexpr int N = 200'000;
+constexpr int M = 500'000;
+void performance_test() {
+	timer t;
+	t.start();
+	LCT lct(N);
+	t.stop();
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		int a = Random::integer<int>(0, N);
+		int b = Random::integer<int>(0, N);
+		ll w = Random::integer<ll>(-1000, 1000);
+		
+		t.start();
+		if (!lct.connected(&lct.nodes[a], &lct.nodes[b])) {
+			lct.link(&lct.nodes[a], &lct.nodes[b]);
+		}
+		lct.modify(&lct.nodes[a], &lct.nodes[b], w);
+		hash += lct.query(&lct.nodes[a], &lct.nodes[b]);
+		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();
+}
-- 
cgit v1.2.3


From 1ad495344f764e979e93f394f76716cf527c2940 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Sun, 4 Aug 2024 15:58:47 +0200
Subject: more tests

---
 content/datastructures/lichao.cpp |   6 ++--
 tcr.pdf                           | Bin 691201 -> 691040 bytes
 test/datastructures/lichao.cpp    |  73 ++++++++++++++++++++++++++++++++++++++
 3 files changed, 76 insertions(+), 3 deletions(-)
 create mode 100644 test/datastructures/lichao.cpp

(limited to 'test/datastructures')

diff --git a/content/datastructures/lichao.cpp b/content/datastructures/lichao.cpp
index f66778e..646ad68 100644
--- a/content/datastructures/lichao.cpp
+++ b/content/datastructures/lichao.cpp
@@ -11,10 +11,10 @@ struct Lichao {
 	static constexpr Fun id = {0, inf}; // {0, -inf}
 	int n, cap;
 	vector<Fun> seg;
-	Lichao() : n(sz(xs)), cap(2<<__lg(n)), seg(2*cap, id) {}
+	Lichao() : n(sz(xs)), cap(2 << __lg(n)), seg(2 * cap, id) {}
 	
 	void _insert(Fun f, int l, int r, int i) {
-		while (i < 2*cap){
+		while (i < 2 * cap) {
 			int m = (l+r)/2;
 			if (m >= n) {r = m; i = 2*i; continue;}
 			Fun &g = seg[i];
@@ -26,7 +26,7 @@ struct Lichao {
 
 	void _segmentInsert(Fun f, int l, int r, int a, int b, int i) {
 		if (l <= a && b <= r) _insert(f, a, b, i);
-		else if (a < r && l < b){
+		else if (a < r && l < b) {
 			int m = (a+b)/2;
 			_segmentInsert(f, l, r, a, m, 2*i);
 			_segmentInsert(f, l, r, m, b, 2*i+1);
diff --git a/tcr.pdf b/tcr.pdf
index 8440c54..1cb888a 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/datastructures/lichao.cpp b/test/datastructures/lichao.cpp
new file mode 100644
index 0000000..acd048f
--- /dev/null
+++ b/test/datastructures/lichao.cpp
@@ -0,0 +1,73 @@
+#include "../util.h"
+constexpr ll inf = LL::INF;
+#include <datastructures/lichao.cpp>
+
+void stress_test() {
+	ll queries = 0;
+	for (int tries = 0; tries < 1000; tries++) {
+		int n = Random::integer<int>(1, 100);
+		xs = Random::distinct<ll>(n, -1000, 1000);
+		sort(all(xs));
+
+		vector<ll> naive(n, inf);
+		Lichao tree;
+
+		for (int operations = 0; operations < 1000; operations++) {
+			{
+				ll m = Random::integer<ll>(-100, 100);
+				ll c = Random::integer<ll>(-1000, 1000);
+				ll l = Random::integer<ll>(-1000, 1000);
+				ll r = Random::integer<ll>(-1000, 1000);
+				Fun f{m, c};
+
+				tree.segmentInsert(f, l, r);
+				for (int i = 0; i < n; i++) {
+					if (l <= xs[i] && xs[i] < r) naive[i] = min(naive[i], f(i));
+				}
+			}
+			{
+				queries++;
+				int i = Random::integer<int>(0, n);
+				ll got = tree.query(xs[i]);
+				ll expected = naive[i];
+				if (got != expected) cerr << xs[i] << endl;
+				if (got != expected) cerr << "  got: " << got << ", expected: " << expected << FAIL;
+			}
+		}
+	}
+	cerr << "  tested random queries: " << queries << endl;
+}
+
+constexpr int N = 200'000;
+void performance_test() {
+	timer t;
+	xs = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000);
+	sort(all(xs));
+
+	t.start();
+	Lichao tree;
+	t.stop();
+
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+
+		ll m = Random::integer<ll>(-1'000'000, 1'000'000);
+		ll c = Random::integer<ll>(-1'000'000, 1'000'000);
+		ll l = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
+		ll r = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
+		ll x = xs[Random::integer<int>(N)];
+		Fun f{m, c};
+
+		t.start();
+		tree.segmentInsert(f, l, r);
+		hash ^= tree.query(x);
+		t.stop();
+	}
+	if (t.time > 1000) cerr << "  too slow: " << t.time << FAIL;
+	cerr << "  tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test();
+	performance_test();
+}
-- 
cgit v1.2.3


From ff3b67478b1f08b0a2b83565de8a454e23441f3a Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 5 Aug 2024 15:41:25 +0200
Subject: more testcases

---
 content/datastructures/monotonicConvexHull.cpp |  18 +++---
 tcr.pdf                                        | Bin 691040 -> 691039 bytes
 test/datastructures/lichao.cpp                 |  22 +++----
 test/datastructures/monotonicConvexHull.cpp    |  79 +++++++++++++++++++++++++
 4 files changed, 100 insertions(+), 19 deletions(-)
 create mode 100644 test/datastructures/monotonicConvexHull.cpp

(limited to 'test/datastructures')

diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp
index 44bff83..119015e 100644
--- a/content/datastructures/monotonicConvexHull.cpp
+++ b/content/datastructures/monotonicConvexHull.cpp
@@ -1,27 +1,27 @@
-// Lower Envelope mit MONOTONEN Inserts und Queries. Jede neue
+// Lower Envelope mit MONOTONEN Inserts UND Queries. Jede neue
 // Gerade hat kleinere Steigung als alle vorherigen.
 struct Line {
-	ll m, b;
-	ll operator()(ll x) {return m*x+b;}
+	ll m, c;
+	ll operator()(ll x) {return m*x+c;}
 };
 
 vector<Line> ls;
-int ptr = 0;
+ll ptr = 0;
 
 bool bad(Line l1, Line l2, Line l3) {
-	return (l3.b-l1.b)*(l1.m-l2.m) < (l2.b-l1.b)*(l1.m-l3.m);
+	return (l3.c-l1.c)*(l1.m-l2.m) < (l2.c-l1.c)*(l1.m-l3.m);
 }
 
-void add(ll m, ll b) { // Laufzeit O(1) amortisiert
-	while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, b})) {
+void add(ll m, ll c) { // Laufzeit O(1) amortisiert
+	while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, c})) {
 		ls.pop_back();
 	}
-	ls.push_back({m, b});
+	ls.push_back({m, c});
 	ptr = min(ptr, sz(ls) - 1);
 }
 
 ll query(ll x) { // Laufzeit: O(1) amortisiert
 	ptr = min(ptr, sz(ls) - 1);
-	while (ptr < sz(ls)-1 && ls[ptr + 1](x) < ls[ptr](x)) ptr++;
+	while (ptr + 1 < sz(ls) && ls[ptr + 1](x) < ls[ptr](x)) ptr++;
 	return ls[ptr](x);
 }
\ No newline at end of file
diff --git a/tcr.pdf b/tcr.pdf
index 1cb888a..48a07d7 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/datastructures/lichao.cpp b/test/datastructures/lichao.cpp
index acd048f..c8a56a3 100644
--- a/test/datastructures/lichao.cpp
+++ b/test/datastructures/lichao.cpp
@@ -2,11 +2,11 @@
 constexpr ll inf = LL::INF;
 #include <datastructures/lichao.cpp>
 
-void stress_test() {
+void stress_test(ll range) {
 	ll queries = 0;
 	for (int tries = 0; tries < 1000; tries++) {
 		int n = Random::integer<int>(1, 100);
-		xs = Random::distinct<ll>(n, -1000, 1000);
+		xs = Random::distinct<ll>(n, -range, range);
 		sort(all(xs));
 
 		vector<ll> naive(n, inf);
@@ -15,9 +15,9 @@ void stress_test() {
 		for (int operations = 0; operations < 1000; operations++) {
 			{
 				ll m = Random::integer<ll>(-100, 100);
-				ll c = Random::integer<ll>(-1000, 1000);
-				ll l = Random::integer<ll>(-1000, 1000);
-				ll r = Random::integer<ll>(-1000, 1000);
+				ll c = Random::integer<ll>(-range, range);
+				ll l = Random::integer<ll>(-range, range);
+				ll r = Random::integer<ll>(-range, range);
 				Fun f{m, c};
 
 				tree.segmentInsert(f, l, r);
@@ -31,11 +31,11 @@ void stress_test() {
 				ll got = tree.query(xs[i]);
 				ll expected = naive[i];
 				if (got != expected) cerr << xs[i] << endl;
-				if (got != expected) cerr << "  got: " << got << ", expected: " << expected << FAIL;
+				if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
 			}
 		}
 	}
-	cerr << "  tested random queries: " << queries << endl;
+	cerr << "tested random queries: " << queries << endl;
 }
 
 constexpr int N = 200'000;
@@ -63,11 +63,13 @@ void performance_test() {
 		hash ^= tree.query(x);
 		t.stop();
 	}
-	if (t.time > 1000) cerr << "  too slow: " << t.time << FAIL;
-	cerr << "  tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+	if (t.time > 1000) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
 }
 
 int main() {
-	stress_test();
+	stress_test(100);
+	stress_test(1'000);
+	stress_test(1'000'000);
 	performance_test();
 }
diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp
new file mode 100644
index 0000000..0d4e10d
--- /dev/null
+++ b/test/datastructures/monotonicConvexHull.cpp
@@ -0,0 +1,79 @@
+#include "../util.h"
+struct MCH {
+	#include <datastructures/monotonicConvexHull.cpp>
+};
+
+struct Line {
+	ll m, c;
+	Line(ll m_, ll c_) : m(m_), c(c_) {}
+	ll operator()(ll x) {return m*x+c;}
+};
+
+void stress_test(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 1000; tries++) {
+		int n = Random::integer<int>(1, 100);
+		auto ms = Random::distinct<ll>(n, -range, range);
+		sort(all(ms), greater<>{});
+		auto xs = Random::distinct<ll>(n*100, -range*n, range*n);
+		sort(all(xs));
+		int i = 0;
+
+		vector<Line> naive;
+
+		MCH mch;
+		for (ll m : ms) {
+			ll c = Random::integer<ll>(-1000, 1000);
+			mch.add(m, c);
+			naive.emplace_back(m, c);
+
+			for (int j = i + 100; i < j; i++) {
+				ll x = xs[i];
+
+				ll got = mch.query(x);
+				ll expected = naive[0](x);
+				for (auto l : naive) expected = min(expected, l(x));
+
+				if (got != expected) {
+					for (auto l : naive) cerr << l.m << "*x+" << l.c << endl;
+					cerr << x << ": " << got << " " << expected << endl;
+				}
+
+				if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+				queries++;
+			}
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+	timer t;
+	auto ms = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000);
+	sort(all(ms), greater<>{});
+	auto xs = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000);
+	sort(all(xs));
+	MCH mch;
+
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll c = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
+		ll m = ms[operations];
+		ll x = xs[operations];
+		
+		t.start();
+		mch.add(m, c);
+		hash += mch.query(x);
+		t.stop();
+	}
+	if (t.time > 100) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test(100);
+	stress_test(1'000);
+	stress_test(1'000'000);
+	performance_test();
+}
-- 
cgit v1.2.3


From bbec09408867e82fb9dd9b242e6d99014f9534b6 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 5 Aug 2024 20:10:57 +0200
Subject: more tests

---
 content/datastructures/dynamicConvexHull.cpp   |   2 +-
 content/datastructures/monotonicConvexHull.cpp |   6 +--
 tcr.pdf                                        | Bin 691039 -> 691129 bytes
 test/datastructures/dynamicConvexHull.cpp      |  72 +++++++++++++++++++++++++
 test/datastructures/monotonicConvexHull.cpp    |   7 +--
 5 files changed, 77 insertions(+), 10 deletions(-)
 create mode 100644 test/datastructures/dynamicConvexHull.cpp

(limited to 'test/datastructures')

diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp
index d669847..dfcfe0b 100644
--- a/content/datastructures/dynamicConvexHull.cpp
+++ b/content/datastructures/dynamicConvexHull.cpp
@@ -4,7 +4,7 @@ struct Line {
 	bool operator<(ll x) const {return p < x;}
 };
 
-struct HullDynamic : multiset<Line, less<>> {
+struct HullDynamic : multiset<Line, less<>> { // max über Geraden
 	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
 	ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);}
 
diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp
index 119015e..e84ad86 100644
--- a/content/datastructures/monotonicConvexHull.cpp
+++ b/content/datastructures/monotonicConvexHull.cpp
@@ -1,4 +1,4 @@
-// Lower Envelope mit MONOTONEN Inserts UND Queries. Jede neue
+// Min über Geraden mit MONOTONEN Inserts UND Queries. Jede neue
 // Gerade hat kleinere Steigung als alle vorherigen.
 struct Line {
 	ll m, c;
@@ -12,7 +12,7 @@ bool bad(Line l1, Line l2, Line l3) {
 	return (l3.c-l1.c)*(l1.m-l2.m) < (l2.c-l1.c)*(l1.m-l3.m);
 }
 
-void add(ll m, ll c) { // Laufzeit O(1) amortisiert
+void add(ll m, ll c) { // m fallend, Laufzeit O(1) amortisiert
 	while (sz(ls) > 1 && bad(ls.end()[-2], ls.end()[-1], {m, c})) {
 		ls.pop_back();
 	}
@@ -20,7 +20,7 @@ void add(ll m, ll c) { // Laufzeit O(1) amortisiert
 	ptr = min(ptr, sz(ls) - 1);
 }
 
-ll query(ll x) { // Laufzeit: O(1) amortisiert
+ll query(ll x) { // x steigend, Laufzeit: O(1) amortisiert
 	ptr = min(ptr, sz(ls) - 1);
 	while (ptr + 1 < sz(ls) && ls[ptr + 1](x) < ls[ptr](x)) ptr++;
 	return ls[ptr](x);
diff --git a/tcr.pdf b/tcr.pdf
index 48a07d7..1b58dc4 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/datastructures/dynamicConvexHull.cpp b/test/datastructures/dynamicConvexHull.cpp
new file mode 100644
index 0000000..e0e56ef
--- /dev/null
+++ b/test/datastructures/dynamicConvexHull.cpp
@@ -0,0 +1,72 @@
+#include "../util.h"
+namespace dch {
+	constexpr ll INF = LL::INF;
+	#include <datastructures/dynamicConvexHull.cpp>
+}
+
+struct Line {
+	ll m, c;
+	Line(ll m_, ll c_) : m(m_), c(c_) {}
+	ll operator()(ll x) {return m*x+c;}
+};
+
+void stress_test(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 1000; tries++) {
+		int n = Random::integer<int>(1, 100);
+
+		vector<Line> naive;
+
+		dch::HullDynamic hd;
+		for (int i = 0; i < n; i++) {
+			ll m = Random::integer<ll>(-range, range);
+			ll c = Random::integer<ll>(-range, range);
+			hd.add(m, c);
+			naive.emplace_back(m, c);
+
+			for (int j = 0; j < 100; j++) {
+				ll x = Random::integer<ll>(-range, range);
+
+				ll got = hd.query(x);
+				ll expected = naive[0](x);
+				for (auto l : naive) expected = max(expected, l(x));
+
+				if (got != expected) {
+					for (auto l : naive) cerr << l.m << "*x+" << l.c << endl;
+					cerr << x << ": " << got << " " << expected << endl;
+				}
+
+				if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+				queries++;
+			}
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+	timer t;
+	dch::HullDynamic hd;
+
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+		ll m = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
+		ll c = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
+		ll x = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
+		
+		t.start();
+		hd.add(m, c);
+		hash += hd.query(x);
+		t.stop();
+	}
+	if (t.time > 100) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test(100);
+	stress_test(1'000);
+	stress_test(1'000'000);
+	performance_test();
+}
diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp
index 0d4e10d..4dafbd4 100644
--- a/test/datastructures/monotonicConvexHull.cpp
+++ b/test/datastructures/monotonicConvexHull.cpp
@@ -23,7 +23,7 @@ void stress_test(ll range) {
 
 		MCH mch;
 		for (ll m : ms) {
-			ll c = Random::integer<ll>(-1000, 1000);
+			ll c = Random::integer<ll>(-range, range);
 			mch.add(m, c);
 			naive.emplace_back(m, c);
 
@@ -34,11 +34,6 @@ void stress_test(ll range) {
 				ll expected = naive[0](x);
 				for (auto l : naive) expected = min(expected, l(x));
 
-				if (got != expected) {
-					for (auto l : naive) cerr << l.m << "*x+" << l.c << endl;
-					cerr << x << ": " << got << " " << expected << endl;
-				}
-
 				if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
 				queries++;
 			}
-- 
cgit v1.2.3


From d88debc398f18d4e3d1c53d221dffe3981f35e41 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Tue, 6 Aug 2024 16:14:04 +0200
Subject: add another test

---
 test/datastructures/dynamicConvexHull.cpp        |  5 ----
 test/datastructures/dynamicConvexHull.lichao.cpp | 38 ++++++++++++++++++++++++
 2 files changed, 38 insertions(+), 5 deletions(-)
 create mode 100644 test/datastructures/dynamicConvexHull.lichao.cpp

(limited to 'test/datastructures')

diff --git a/test/datastructures/dynamicConvexHull.cpp b/test/datastructures/dynamicConvexHull.cpp
index e0e56ef..f163397 100644
--- a/test/datastructures/dynamicConvexHull.cpp
+++ b/test/datastructures/dynamicConvexHull.cpp
@@ -31,11 +31,6 @@ void stress_test(ll range) {
 				ll expected = naive[0](x);
 				for (auto l : naive) expected = max(expected, l(x));
 
-				if (got != expected) {
-					for (auto l : naive) cerr << l.m << "*x+" << l.c << endl;
-					cerr << x << ": " << got << " " << expected << endl;
-				}
-
 				if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
 				queries++;
 			}
diff --git a/test/datastructures/dynamicConvexHull.lichao.cpp b/test/datastructures/dynamicConvexHull.lichao.cpp
new file mode 100644
index 0000000..6ab55f0
--- /dev/null
+++ b/test/datastructures/dynamicConvexHull.lichao.cpp
@@ -0,0 +1,38 @@
+#include "../util.h"
+constexpr ll INF = LL::INF;
+constexpr ll inf = LL::INF;
+#include <datastructures/dynamicConvexHull.cpp>
+#include <datastructures/lichao.cpp>
+
+void stress_test(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 1000; tries++) {
+		int n = Random::integer<int>(1, 100);
+		xs = Random::distinct(n, -range, range);
+		sort(all(xs));
+
+		HullDynamic hd;
+		Lichao lichao;
+		for (int i = 0; i < 1000; i++) {
+			ll m = Random::integer<ll>(-range, range);
+			ll c = Random::integer<ll>(-range, range);
+			hd.add(m, c);
+			lichao.insert({-m, -c});
+
+			for (ll x : xs) {
+				ll gotA = hd.query(x);
+				ll gotB = -lichao.query(x);
+
+				if (gotA != gotB) cerr << "gotA: " << gotA << ", gotB: " << gotB << FAIL;
+				queries++;
+			}
+		}
+	}
+	cerr << "tested random queries: " << queries << endl;
+}
+
+int main() {
+	stress_test(100);
+	stress_test(1'000);
+	stress_test(1'000'000);
+}
-- 
cgit v1.2.3


From 19436370fb48bc0a5e356d1ba713dc39b1a35d3a Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Tue, 6 Aug 2024 16:54:13 +0200
Subject: upper case INF

---
 content/datastructures/dynamicConvexHull.cpp     |   2 +-
 content/datastructures/lazyPropagation.cpp       |   2 +-
 content/datastructures/lichao.cpp                |   4 ++--
 content/geometry/hpi.cpp                         |   2 +-
 content/other/divideAndConquer.cpp               |   4 ++--
 content/other/knuth.cpp                          |   2 +-
 tcr.pdf                                          | Bin 691129 -> 691160 bytes
 test/datastructures/dynamicConvexHull.lichao.cpp |   1 -
 test/datastructures/lazyPropagation.cpp          |   2 +-
 test/datastructures/lichao.cpp                   |   4 ++--
 test/other/divideAndConquer.cpp                  |   8 ++++----
 test/other/knuth.cpp                             |   8 ++++----
 12 files changed, 19 insertions(+), 20 deletions(-)

(limited to 'test/datastructures')

diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp
index dfcfe0b..27ec898 100644
--- a/content/datastructures/dynamicConvexHull.cpp
+++ b/content/datastructures/dynamicConvexHull.cpp
@@ -5,7 +5,7 @@ struct Line {
 };
 
 struct HullDynamic : multiset<Line, less<>> { // max über Geraden
-	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
+	// (for doubles, use INF = 1/.0, div(a,b) = a/b)
 	ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);}
 
 	bool isect(iterator x, iterator y) {
diff --git a/content/datastructures/lazyPropagation.cpp b/content/datastructures/lazyPropagation.cpp
index 441590e..ab91364 100644
--- a/content/datastructures/lazyPropagation.cpp
+++ b/content/datastructures/lazyPropagation.cpp
@@ -2,7 +2,7 @@ struct SegTree {
 	using T = ll; using U = ll;
 	int n;
 	static constexpr T E = 0; // Neutral element for combine
-	static constexpr U UF = inf; // Unused value by updates
+	static constexpr U UF = INF; // Unused value by updates
 	vector<T> tree;
 	int h;
 	vector<U> lazy;
diff --git a/content/datastructures/lichao.cpp b/content/datastructures/lichao.cpp
index 646ad68..1318ca7 100644
--- a/content/datastructures/lichao.cpp
+++ b/content/datastructures/lichao.cpp
@@ -8,7 +8,7 @@ struct Fun { // Default: Linear function. Change as needed.
 
 // Default: Computes min. Change lines with comment for max.
 struct Lichao {
-	static constexpr Fun id = {0, inf}; // {0, -inf}
+	static constexpr Fun id = {0, INF}; // {0, -INF}
 	int n, cap;
 	vector<Fun> seg;
 	Lichao() : n(sz(xs)), cap(2 << __lg(n)), seg(2 * cap, id) {}
@@ -36,7 +36,7 @@ struct Lichao {
 	}
 
 	ll _query(int x) {
-		ll ans = inf; // -inf
+		ll ans = INF; // -INF
 		for (int i = x + cap; i > 0; i /= 2) {
 			ans = min(ans, seg[i](x)); // max
 		}
diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp
index 3509e0e..bd3ab1e 100644
--- a/content/geometry/hpi.cpp
+++ b/content/geometry/hpi.cpp
@@ -1,4 +1,4 @@
-constexpr ll inf = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP
+constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP
 
 bool left(pt p) {return real(p) < 0 || 
 					   (real(p) == 0 && imag(p) < 0);}
diff --git a/content/other/divideAndConquer.cpp b/content/other/divideAndConquer.cpp
index 830dc7f..9bd5f0c 100644
--- a/content/other/divideAndConquer.cpp
+++ b/content/other/divideAndConquer.cpp
@@ -5,7 +5,7 @@ void rec(int i, int j0, int j1, int m0, int m1) {
 	if (j1 < j0) return;
 	int jmid = (j0 + j1) / 2;
 
-	dp[i][jmid] = inf;
+	dp[i][jmid] = INF;
 	int bestk = m0;
 	for (int k = m0; k < min(jmid, m1 + 1); ++k) {
 		if (dp[i - 1][k] + C[k + 1][jmid] < dp[i][jmid]) {
@@ -18,7 +18,7 @@ void rec(int i, int j0, int j1, int m0, int m1) {
 }
 
 ll calc(int n, int m) {
-	dp = vector<vector<ll>>(m, vector<ll>(n, inf));
+	dp = vector<vector<ll>>(m, vector<ll>(n, INF));
 	for (int i = 0; i < n; i++) dp[0][i] = C[0][i];
 	for (int i = 1; i < m; i++) {
 		rec(i, 0, n - 1, 0, n - 1);
diff --git a/content/other/knuth.cpp b/content/other/knuth.cpp
index 1d513c8..aa54924 100644
--- a/content/other/knuth.cpp
+++ b/content/other/knuth.cpp
@@ -1,5 +1,5 @@
 ll calc(int n, int m, const vector<vector<ll>>& C) {
-	vector<vector<ll>> dp(m, vector<ll>(n, inf));
+	vector<vector<ll>> dp(m, vector<ll>(n, INF));
 	vector<vector<int>> opt(m, vector<int>(n + 1, n - 1));
 
 	for (int i = 0; i < n; i++) dp[0][i] = C[0][i];
diff --git a/tcr.pdf b/tcr.pdf
index 1b58dc4..649aa24 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/datastructures/dynamicConvexHull.lichao.cpp b/test/datastructures/dynamicConvexHull.lichao.cpp
index 6ab55f0..d50ca60 100644
--- a/test/datastructures/dynamicConvexHull.lichao.cpp
+++ b/test/datastructures/dynamicConvexHull.lichao.cpp
@@ -1,6 +1,5 @@
 #include "../util.h"
 constexpr ll INF = LL::INF;
-constexpr ll inf = LL::INF;
 #include <datastructures/dynamicConvexHull.cpp>
 #include <datastructures/lichao.cpp>
 
diff --git a/test/datastructures/lazyPropagation.cpp b/test/datastructures/lazyPropagation.cpp
index 7002061..feb07f0 100644
--- a/test/datastructures/lazyPropagation.cpp
+++ b/test/datastructures/lazyPropagation.cpp
@@ -1,5 +1,5 @@
 #include "../util.h"
-constexpr ll inf = LL::INF;
+constexpr ll INF = LL::INF;
 #include <datastructures/lazyPropagation.cpp>
 
 constexpr int N = 1000'000;
diff --git a/test/datastructures/lichao.cpp b/test/datastructures/lichao.cpp
index c8a56a3..f4b797b 100644
--- a/test/datastructures/lichao.cpp
+++ b/test/datastructures/lichao.cpp
@@ -1,5 +1,5 @@
 #include "../util.h"
-constexpr ll inf = LL::INF;
+constexpr ll INF = LL::INF;
 #include <datastructures/lichao.cpp>
 
 void stress_test(ll range) {
@@ -9,7 +9,7 @@ void stress_test(ll range) {
 		xs = Random::distinct<ll>(n, -range, range);
 		sort(all(xs));
 
-		vector<ll> naive(n, inf);
+		vector<ll> naive(n, INF);
 		Lichao tree;
 
 		for (int operations = 0; operations < 1000; operations++) {
diff --git a/test/other/divideAndConquer.cpp b/test/other/divideAndConquer.cpp
index a6fda9d..6d1b444 100644
--- a/test/other/divideAndConquer.cpp
+++ b/test/other/divideAndConquer.cpp
@@ -1,5 +1,5 @@
 #include "../util.h"
-constexpr ll inf = LL::INF;
+constexpr ll INF = LL::INF;
 #include <other/divideAndConquer.cpp>
 
 vector<vector<ll>> gen(int n) {
@@ -43,7 +43,7 @@ vector<vector<ll>> genQuick(int n) {
 }
 
 /*ll naive(int n, int m) {
-	vector<vector<ll>> state(m+1, vector<ll>(n+1, inf));
+	vector<vector<ll>> state(m+1, vector<ll>(n+1, INF));
 	state[0][0] = 0;
 	for (int i = 1; i <= m; i++) {
 		for (int j = 1; j <= n; j++) {
@@ -56,9 +56,9 @@ vector<vector<ll>> genQuick(int n) {
 }*/
 
 vector<ll> naive(int n) {
-	vector<vector<ll>> state(n+1, vector<ll>(n+1, inf));
+	vector<vector<ll>> state(n+1, vector<ll>(n+1, INF));
 	state[0][0] = 0;
-	vector<ll> res(n+1, inf);
+	vector<ll> res(n+1, INF);
 	for (int i = 1; i <= n; i++) {
 		for (int j = 1; j <= n; j++) {
 			for (int k = 1; k <= j; k++) {
diff --git a/test/other/knuth.cpp b/test/other/knuth.cpp
index d469ceb..3462c0a 100644
--- a/test/other/knuth.cpp
+++ b/test/other/knuth.cpp
@@ -1,5 +1,5 @@
 #include "../util.h"
-constexpr ll inf = LL::INF;
+constexpr ll iINFnf = LL::INF;
 #include <other/knuth.cpp>
 
 vector<vector<ll>> gen(int n) {
@@ -43,7 +43,7 @@ vector<vector<ll>> genQuick(int n) {
 }
 
 /*ll naive(int n, int m, const vector<vector<ll>>& C) {
-	vector<vector<ll>> state(m+1, vector<ll>(n+1, inf));
+	vector<vector<ll>> state(m+1, vector<ll>(n+1, INF));
 	state[0][0] = 0;
 	for (int i = 1; i <= m; i++) {
 		for (int j = 1; j <= n; j++) {
@@ -56,9 +56,9 @@ vector<vector<ll>> genQuick(int n) {
 }*/
 
 vector<ll> naive(int n, const vector<vector<ll>>& C) {
-	vector<vector<ll>> state(n+1, vector<ll>(n+1, inf));
+	vector<vector<ll>> state(n+1, vector<ll>(n+1, INF));
 	state[0][0] = 0;
-	vector<ll> res(n+1, inf);
+	vector<ll> res(n+1, INF);
 	for (int i = 1; i <= n; i++) {
 		for (int j = 1; j <= n; j++) {
 			for (int k = 1; k <= j; k++) {
-- 
cgit v1.2.3


From 22536b7fbc050075a1420c0f1a7125b9185c9519 Mon Sep 17 00:00:00 2001
From: Yidi <noob999noob999@gmail.com>
Date: Mon, 12 Aug 2024 13:22:34 +0200
Subject: add treap test

---
 content/datastructures/datastructures.tex |   2 +-
 content/datastructures/treap.cpp          | 140 +++++++++++++++---------------
 content/datastructures/treap2.cpp         |  79 -----------------
 test/datastructures/treap.cpp             |  85 ++++++++++++++++++
 4 files changed, 156 insertions(+), 150 deletions(-)
 delete mode 100644 content/datastructures/treap2.cpp
 create mode 100644 test/datastructures/treap.cpp

(limited to 'test/datastructures')

diff --git a/content/datastructures/datastructures.tex b/content/datastructures/datastructures.tex
index 40132a9..c9f3d2a 100644
--- a/content/datastructures/datastructures.tex
+++ b/content/datastructures/datastructures.tex
@@ -50,7 +50,7 @@
 		\method{insert}{fügt wert $\mathit{val}$ an stelle $i$ ein (verschiebt alle Positionen $\geq i$)}{\log(n)}
 		\method{remove}{löscht werte $[i,i+\mathit{count})$}{\log(n)}
 	\end{methods}
-	\sourcecode{datastructures/treap2.cpp}
+	\sourcecode{datastructures/treap.cpp}
 \end{algorithm}
 
 \begin{algorithm}{Range Minimum Query}
diff --git a/content/datastructures/treap.cpp b/content/datastructures/treap.cpp
index c96e36a..c5a60e9 100644
--- a/content/datastructures/treap.cpp
+++ b/content/datastructures/treap.cpp
@@ -1,79 +1,79 @@
-struct node {
-	int key, prio, left, right, size;
-	node(int key, int prio) : key(key), prio(prio), left(-1),
-	                          right(-1), size(1) {};
-};
+mt19937 rng(0xc4bd5dad);
+struct Treap {
+	struct Node {
+		ll val;
+		int prio, size = 1, l = -1, r = -1;
+		Node(ll x) : val(x), prio(rng()) {}
+	};
 
-vector<node> treap;
+	vector<Node> treap;
+	int root = -1;
 
-int getSize(int root) {
-	return root < 0 ? 0 : treap[root].size;
-}
+	int getSize(int v) {
+		return v < 0 ? 0 : treap[v].size;
+	}
 
-void update(int root) {
-	if (root < 0) return;
-	treap[root].size = 1 + getSize(treap[root].left)
-	                     + getSize(treap[root].right);
-}
+	void upd(int v) {
+		if (v < 0) return;
+		auto& V = treap[v];
+		V.size = 1 + getSize(V.l) + getSize(V.r);
+		// Update Node Code
+	}
 
-pair<int, int> split(int root, int minKeyRight) {
-	if (root < 0) return {-1, -1};
-	if (treap[root].key >= minKeyRight) {
-		auto leftSplit = split(treap[root].left, minKeyRight);
-		treap[root].left = leftSplit.second;
-		update(root);
-		leftSplit.second = root;
-		return leftSplit;
-	} else {
-		auto rightSplit = split(treap[root].right, minKeyRight);
-		treap[root].right = rightSplit.first;
-		update(root);
-		rightSplit.first = root;
-		return rightSplit;
-}}
+	void push(int v) {
+		if (v < 0) return;
+		//auto& V = treap[v];
+		//if (V.lazy) {
+		//	Lazy Propagation Code
+		//	if (V.l >= 0) treap[V.l].lazy = true;
+		//	if (V.r >= 0) treap[V.r].lazy = true;
+		//	V.lazy = false;
+		//}
+	}
 
-int merge (int left, int right) {
-	if (left < 0) return right;
-	if (right < 0) return left;
-	if (treap[left].prio < treap[right].prio) { //min priority heap
-		treap[left].right = merge(treap[left].right, right);
-		update(left);
-		return left;
-	} else {
-		treap[right].left = merge(left, treap[right].left);
-		update(right);
-		return right;
-}}
+	pair<int, int> split(int v, int k) {
+		if (v < 0) return {-1, -1};
+		auto& V = treap[v];
+		push(v);
+		if (getSize(V.l) >= k) { // "V.val >= k" for lower_bound(k)
+			auto [left, right] = split(V.l, k);
+			V.l = right;
+			upd(v);
+			return {left, v};
+		} else {
+			// and only "k"
+			auto [left, right] = split(V.r, k - getSize(V.l) - 1);
+			V.r = left;
+			upd(v);
+			return {v, right};
+	}}
 
-//insert values with high priority first
-int insert(int root, int key, int prio) {
-	int next = sz(treap);
-	treap.emplace_back(key, prio);
-	auto t = split(root, key);
-	//returns new root
-	return merge(merge(t.first, next), t.second);
-}
+	int merge(int left, int right) {
+		if (left < 0) return right;
+		if (right < 0) return left;
+		if (treap[left].prio < treap[right].prio) {
+			push(left);
+			treap[left].r = merge(treap[left].r, right);
+			upd(left);
+			return left;
+		} else {
+			push(right);
+			treap[right].l = merge(left, treap[right].l);
+			upd(right);
+			return right;
+	}}
 
-int remove(int root, int key) {
-	if (root < 0) return -1;
-	if (key < treap[root].key) {
-		treap[root].left = remove(treap[root].left, key);
-		update(root);
-		return root;
-	} else if (key > treap[root].key) {
-		treap[root].right = remove(treap[root].right, key);
-		update(root);
-		return root;
-	} else { //check prio?
-		return merge(treap[root].left, treap[root].right);
-}}
+	void insert(int i, ll val) { // and i = val
+		auto [left, right] = split(root, i);
+		treap.emplace_back(val);
+		left = merge(left, sz(treap) - 1);
+		root = merge(left, right);
+	}
 
-int kth(int root, int k) {
-	if (root < 0) return -1;
-	int leftSize = getSize(treap[root].left);
-	if (k < leftSize) return kth(treap[root].left, k);
-	else if (k > leftSize) {
-		return kth(treap[root].right, k - 1 - leftSize);
+	void remove(int i, int count = 1) {
+		auto [left, t_right] = split(root, i);
+		auto [middle, right] = split(t_right, count);
+		root = merge(left, right);
 	}
-	return root;
-}
+	// for query use remove and read middle BEFORE remerging
+};
diff --git a/content/datastructures/treap2.cpp b/content/datastructures/treap2.cpp
deleted file mode 100644
index c5a60e9..0000000
--- a/content/datastructures/treap2.cpp
+++ /dev/null
@@ -1,79 +0,0 @@
-mt19937 rng(0xc4bd5dad);
-struct Treap {
-	struct Node {
-		ll val;
-		int prio, size = 1, l = -1, r = -1;
-		Node(ll x) : val(x), prio(rng()) {}
-	};
-
-	vector<Node> treap;
-	int root = -1;
-
-	int getSize(int v) {
-		return v < 0 ? 0 : treap[v].size;
-	}
-
-	void upd(int v) {
-		if (v < 0) return;
-		auto& V = treap[v];
-		V.size = 1 + getSize(V.l) + getSize(V.r);
-		// Update Node Code
-	}
-
-	void push(int v) {
-		if (v < 0) return;
-		//auto& V = treap[v];
-		//if (V.lazy) {
-		//	Lazy Propagation Code
-		//	if (V.l >= 0) treap[V.l].lazy = true;
-		//	if (V.r >= 0) treap[V.r].lazy = true;
-		//	V.lazy = false;
-		//}
-	}
-
-	pair<int, int> split(int v, int k) {
-		if (v < 0) return {-1, -1};
-		auto& V = treap[v];
-		push(v);
-		if (getSize(V.l) >= k) { // "V.val >= k" for lower_bound(k)
-			auto [left, right] = split(V.l, k);
-			V.l = right;
-			upd(v);
-			return {left, v};
-		} else {
-			// and only "k"
-			auto [left, right] = split(V.r, k - getSize(V.l) - 1);
-			V.r = left;
-			upd(v);
-			return {v, right};
-	}}
-
-	int merge(int left, int right) {
-		if (left < 0) return right;
-		if (right < 0) return left;
-		if (treap[left].prio < treap[right].prio) {
-			push(left);
-			treap[left].r = merge(treap[left].r, right);
-			upd(left);
-			return left;
-		} else {
-			push(right);
-			treap[right].l = merge(left, treap[right].l);
-			upd(right);
-			return right;
-	}}
-
-	void insert(int i, ll val) { // and i = val
-		auto [left, right] = split(root, i);
-		treap.emplace_back(val);
-		left = merge(left, sz(treap) - 1);
-		root = merge(left, right);
-	}
-
-	void remove(int i, int count = 1) {
-		auto [left, t_right] = split(root, i);
-		auto [middle, right] = split(t_right, count);
-		root = merge(left, right);
-	}
-	// for query use remove and read middle BEFORE remerging
-};
diff --git a/test/datastructures/treap.cpp b/test/datastructures/treap.cpp
new file mode 100644
index 0000000..ebab34d
--- /dev/null
+++ b/test/datastructures/treap.cpp
@@ -0,0 +1,85 @@
+#include "../util.h"
+#include <datastructures/treap.cpp>
+
+void add(Treap& t, vector<ll>& ans, int v) {
+    if (v < 0) return;
+    add(t, ans, t.treap[v].l);
+    ans.push_back(t.treap[v].val);
+    add(t, ans, t.treap[v].r);
+}
+
+vector<ll> to_vec(Treap& t) {
+    vector<ll> ans;
+    add(t, ans, t.root);
+    return ans;
+}
+
+void stress_test(int T, int n) {
+	for (int tries = 0; tries < T; tries++) {
+		int ins = Random::integer<int>(1, n);
+        int rem = Random::integer<int>(0, ins+1);
+
+        vector<ll> a;
+        Treap t;
+        while (ins + rem > 0) {
+            bool is_ins = Random::integer(0, ins+rem) < ins;
+            if (a.empty()) is_ins = true;
+
+            if (is_ins) {
+                int ind = Random::integer<int>(0, (int)sz(a)+1);
+                ll val = Random::integer((ll)-1e18, (ll)1e18+1);
+                t.insert(ind, val);
+                a.insert(a.begin() + ind, val);
+                ins--;
+            } else {
+                int ind = Random::integer<int>(0, (int)sz(a));
+                int cnt = Random::integer<int>(1, 1 + min<int>({(int)sz(a)-ind, rem, (int)sqrt(n)}));
+                t.remove(ind, cnt);
+                a.erase(a.begin() + ind, a.begin() + ind + cnt);
+                rem -= cnt;
+            }
+        }
+        if (to_vec(t) != a) cerr << "Failed stress test" << endl;
+	}
+	cerr << "Tested " << T << " random tests with n<=" << n << endl;
+}
+
+constexpr int N = 200'000;
+void performance_test() {
+	timer t;
+
+	t.start();
+	Treap tr;
+	t.stop();
+
+	hash_t hash = 0;
+	for (int operations = 0; operations < N; operations++) {
+        int ind = Random::integer<int>(0, operations+1);
+        ll val = Random::integer((ll)-1e18, (ll)1e18+1);
+
+		t.start();
+        tr.insert(ind, val);
+		hash ^= tr.root;
+		t.stop();
+	}
+    while (tr.root != -1) {
+        t.start();
+        int sz = tr.getSize(tr.root);
+        t.stop();
+
+        int ind = Random::integer<int>(0, sz);
+        int cnt = Random::integer<int>(1, 1 + min<int>(sz-ind, 10));
+        t.start();
+        tr.remove(ind, cnt);
+        t.stop();
+    }
+	if (t.time > 1000) cerr << "too slow: " << t.time << FAIL;
+	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+	stress_test(10000, 10);
+	stress_test(1000, 100);
+	stress_test(100, 10000);
+	performance_test();
+}
-- 
cgit v1.2.3


From af07c941cb58bb73cffc12161e9f263819575e82 Mon Sep 17 00:00:00 2001
From: mzuenni <mzuenni@users.noreply.github.com>
Date: Mon, 12 Aug 2024 14:44:54 +0200
Subject: Update treap.cpp

use FAIL
---
 test/datastructures/treap.cpp | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'test/datastructures')

diff --git a/test/datastructures/treap.cpp b/test/datastructures/treap.cpp
index ebab34d..2fc9d63 100644
--- a/test/datastructures/treap.cpp
+++ b/test/datastructures/treap.cpp
@@ -39,7 +39,7 @@ void stress_test(int T, int n) {
                 rem -= cnt;
             }
         }
-        if (to_vec(t) != a) cerr << "Failed stress test" << endl;
+        if (to_vec(t) != a) cerr << "Failed stress test" << FAIL;
 	}
 	cerr << "Tested " << T << " random tests with n<=" << n << endl;
 }
-- 
cgit v1.2.3


From f32a00178f0d3b2152a6fc1dc492c987aaede85f Mon Sep 17 00:00:00 2001
From: MZuenni <michi.zuendorf@gmail.com>
Date: Tue, 13 Aug 2024 17:14:17 +0200
Subject: small improvements

---
 content/datastructures/dynamicConvexHull.cpp |  16 ++++++++--------
 content/datastructures/pbds.cpp              |   4 ++--
 content/geometry/convexHull.cpp              |   4 ++--
 content/geometry/hpi.cpp                     |   2 +-
 content/graph/bitonicTSP.cpp                 |   2 +-
 content/graph/bitonicTSPsimple.cpp           |   2 +-
 content/graph/pushRelabel.cpp                |   2 +-
 tcr.pdf                                      | Bin 691284 -> 691101 bytes
 test/datastructures/fenwickTree2.cpp         |   2 +-
 test/geometry/delaunay.cpp                   |   6 +++---
 test/math/gauss.cpp                          |   2 +-
 test/math/inversionsMerge.cpp                |   2 +-
 12 files changed, 22 insertions(+), 22 deletions(-)

(limited to 'test/datastructures')

diff --git a/content/datastructures/dynamicConvexHull.cpp b/content/datastructures/dynamicConvexHull.cpp
index 27ec898..abae1d7 100644
--- a/content/datastructures/dynamicConvexHull.cpp
+++ b/content/datastructures/dynamicConvexHull.cpp
@@ -1,22 +1,22 @@
 struct Line {
-	mutable ll m, b, p;
+	mutable ll m, c, p;
 	bool operator<(const Line& o) const {return m < o.m;}
 	bool operator<(ll x) const {return p < x;}
 };
 
 struct HullDynamic : multiset<Line, less<>> { // max über Geraden
-	// (for doubles, use INF = 1/.0, div(a,b) = a/b)
-	ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);}
+	// (for doubles, use INF = 1/.0, div(a,c) = a/c)
+	ll div(ll a, ll c) {return a / b - ((a ^ c) < 0 && a % c);}
 
 	bool isect(iterator x, iterator y) {
 		if (y == end()) {x->p = INF; return false;}
-		if (x->m == y->m) x->p = x->b > y->b ? INF : -INF;
-		else x->p = div(y->b - x->b, x->m - y->m);
+		if (x->m == y->m) x->p = x->c > y->c ? INF : -INF;
+		else x->p = div(y->c - x->c, x->m - y->m);
 		return x->p >= y->p;
 	}
 
-	void add(ll m, ll b) {
-		auto x = insert({m, b, 0});
+	void add(ll m, ll c) {
+		auto x = insert({m, c, 0});
 		while (isect(x, next(x))) erase(next(x));
 		if (x != begin()) {
 			x--;
@@ -31,6 +31,6 @@ struct HullDynamic : multiset<Line, less<>> { // max über Geraden
 
 	ll query(ll x) {
 		auto l = *lower_bound(x);
-		return l.m * x + l.b;
+		return l.m * x + l.c;
 	}
 };
diff --git a/content/datastructures/pbds.cpp b/content/datastructures/pbds.cpp
index f0889a2..de0ace6 100644
--- a/content/datastructures/pbds.cpp
+++ b/content/datastructures/pbds.cpp
@@ -6,11 +6,11 @@ using Tree = tree<T, null_type, less<T>, rb_tree_tag,
 // T.order_of_key(x): number of elements strictly less than x
 // *T.find_by_order(k): k-th element
 
+constexpr uint64_t RNG = ll(2e18 * acos(-1)) | 199; // random odd
 template<typename T>
 struct chash {
-	static const uint64_t C = ll(2e18 * acos(-1)) | 199; // random odd
 	size_t operator()(T o) const {
-		return __builtin_bswap64(hash<T>()(o) * C);
+		return __builtin_bswap64(hash<T>()(o) * RNG);
 }};
 template<typename K, typename V>
 using hashMap = gp_hash_table<K, V, chash<K>>;
diff --git a/content/geometry/convexHull.cpp b/content/geometry/convexHull.cpp
index 6d89e05..1173924 100644
--- a/content/geometry/convexHull.cpp
+++ b/content/geometry/convexHull.cpp
@@ -11,8 +11,8 @@ vector<pt> convexHull(vector<pt> pts){
 			while (k > t && cross(h[k-2], h[k-1], *it) <= 0) k--;
 			h[k++] = *it;
 	}};
-	half(all(pts), 1);// Untere Hülle.
-	half(next(pts.rbegin()), pts.rend(), k);// Obere Hülle.
+	half(all(pts), 1); // Untere Hülle.
+	half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle.
 	h.resize(k);
 	return h;
 }
diff --git a/content/geometry/hpi.cpp b/content/geometry/hpi.cpp
index bd3ab1e..c58a6e7 100644
--- a/content/geometry/hpi.cpp
+++ b/content/geometry/hpi.cpp
@@ -1,4 +1,4 @@
-constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP
+constexpr ll INF = 0x1FFF'FFFF'FFFF'FFFF; //THIS CODE IS WIP
 
 bool left(pt p) {return real(p) < 0 || 
 					   (real(p) == 0 && imag(p) < 0);}
diff --git a/content/graph/bitonicTSP.cpp b/content/graph/bitonicTSP.cpp
index 6470232..eee5082 100644
--- a/content/graph/bitonicTSP.cpp
+++ b/content/graph/bitonicTSP.cpp
@@ -27,5 +27,5 @@ auto bitonicTSP() {
 	(lt.back() == 1 ? lt : ut).push_back(0);
 	reverse(all(lt));
 	lt.insert(lt.end(), all(ut));
-	return lt;// Enthält Knoten 0 zweimal. An erster und letzter Position.
+	return lt; // Enthält Knoten 0 zweimal. An erster und letzter Position.
 }
diff --git a/content/graph/bitonicTSPsimple.cpp b/content/graph/bitonicTSPsimple.cpp
index 8b6e6c5..cacfb9c 100644
--- a/content/graph/bitonicTSPsimple.cpp
+++ b/content/graph/bitonicTSPsimple.cpp
@@ -23,5 +23,5 @@ auto bitonicTSP() {
 			rl.push_back(v); p2 = v;
 	}}
 	lr.insert(lr.end(), rl.rbegin(), rl.rend());
-	return lr;// Enthält Knoten 0 zweimal. An erster und letzter Position.
+	return lr; // Enthält Knoten 0 zweimal. An erster und letzter Position.
 }
diff --git a/content/graph/pushRelabel.cpp b/content/graph/pushRelabel.cpp
index 73a9eae..ec36026 100644
--- a/content/graph/pushRelabel.cpp
+++ b/content/graph/pushRelabel.cpp
@@ -29,7 +29,7 @@ ll maxFlow(int s, int t) {
 	cur.assign(n, 0);
 	H.assign(n, 0);
 	H[s] = n;
-	ec[t] = 1;//never set t to active...
+	ec[t] = 1; //never set t to active...
 	vector<int> co(2*n);
 	co[0] = n - 1;
 	for (Edge& e : adj[s]) addFlow(e, e.c);
diff --git a/tcr.pdf b/tcr.pdf
index b096438..57691c5 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/datastructures/fenwickTree2.cpp b/test/datastructures/fenwickTree2.cpp
index aa99576..89d5b0f 100644
--- a/test/datastructures/fenwickTree2.cpp
+++ b/test/datastructures/fenwickTree2.cpp
@@ -9,7 +9,7 @@ void stress_test() {
 	ll queries = 0;
 	for (int tries = 0; tries < 100; tries++) {
 		int n = Random::integer<int>(10, 100);
-		vector<ll> naive(n);// = Random::integers<ll>(n, -1000, 1000);
+		vector<ll> naive = Random::integers<ll>(n, -1000, 1000);
 		init(naive);
 		for (int operations = 0; operations < 1000; operations++) {
 			{
diff --git a/test/geometry/delaunay.cpp b/test/geometry/delaunay.cpp
index 7f8ec30..5740b95 100644
--- a/test/geometry/delaunay.cpp
+++ b/test/geometry/delaunay.cpp
@@ -16,11 +16,11 @@ vector<pt> convexHull(vector<pt> pts){
 	vector<pt> h(2 * sz(pts));
 	auto half = [&](auto begin, auto end, int t) {
 		for (auto it = begin; it != end; it++) {
-			while (k > t && cross(h[k-2], h[k-1], *it) < 0) k--;//allow collinear points!
+			while (k > t && cross(h[k-2], h[k-1], *it) < 0) k--; //allow collinear points!
 			h[k++] = *it;
 	}};
-	half(all(pts), 1);// Untere Hülle.
-	half(next(pts.rbegin()), pts.rend(), k);// Obere Hülle.
+	half(all(pts), 1); // Untere Hülle.
+	half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle.
 	h.resize(k);
 	return h;
 }
diff --git a/test/math/gauss.cpp b/test/math/gauss.cpp
index 37bacce..6e4759d 100644
--- a/test/math/gauss.cpp
+++ b/test/math/gauss.cpp
@@ -14,7 +14,7 @@ vector<vector<double>> inverseMat(const vector<vector<double>>& m) {
 		mat[i].resize(2*n);
 		mat[i][n+i] = 1;
 	}
-	gauss(n);//the unique cetc. checks are not usefull since we dont solve an lgs...
+	gauss(n); //the unique cetc. checks are not usefull since we dont solve an lgs...
 	vector<vector<double>> res(m);
 	for (int i = 0; i < n; i++) {
 		res[i] = vector<double>(mat[i].begin() + n, mat[i].end());
diff --git a/test/math/inversionsMerge.cpp b/test/math/inversionsMerge.cpp
index 85ab0d2..acdc555 100644
--- a/test/math/inversionsMerge.cpp
+++ b/test/math/inversionsMerge.cpp
@@ -16,7 +16,7 @@ void stress_test() {
 	for (ll i = 0; i < 100'000; i++) {
 		int n = Random::integer<int>(1, 100);
 		vector<ll> v(n);
-		for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer<ll>(0, 10000);//values must be unique ):
+		for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer<ll>(0, 10000); //values must be unique ):
 		shuffle(all(v), Random::rng);
 		ll expected = naive(v);
 		ll got = mergeSort(v);
-- 
cgit v1.2.3


From 55b0c65814beaac0e68b9c2b99bf42f9327ec61a Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Sat, 17 Aug 2024 16:05:00 +0200
Subject: further tests

---
 test/datastructures/monotonicConvexHull.cpp | 35 +++++++++++++++++++++++++++++
 1 file changed, 35 insertions(+)

(limited to 'test/datastructures')

diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp
index 4dafbd4..9edfb4b 100644
--- a/test/datastructures/monotonicConvexHull.cpp
+++ b/test/datastructures/monotonicConvexHull.cpp
@@ -42,6 +42,38 @@ void stress_test(ll range) {
 	cerr << "tested random queries: " << queries << endl;
 }
 
+void stress_test_independent(ll range) {
+	ll queries = 0;
+	for (int tries = 0; tries < 1000; tries++) {
+		int n = Random::integer<int>(1, 100);
+		auto ms = Random::distinct<ll>(n, -range, range);
+		sort(all(ms), greater<>{});
+
+		vector<Line> naive;
+
+		MCH mch;
+		for (ll m : ms) {
+			ll c = Random::integer<ll>(-range, range);
+			mch.add(m, c);
+			naive.emplace_back(m, c);
+
+			auto xs = Random::distinct<ll>(100, -range, range);
+			sort(all(xs));
+			auto tmp = mch;
+
+			for (auto x : xs) {
+				ll got = tmp.query(x);
+				ll expected = naive[0](x);
+				for (auto l : naive) expected = min(expected, l(x));
+
+				if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+				queries++;
+			}
+		}
+	}
+	cerr << "tested random independent queries: " << queries << endl;
+}
+
 constexpr int N = 1'000'000;
 void performance_test() {
 	timer t;
@@ -70,5 +102,8 @@ int main() {
 	stress_test(100);
 	stress_test(1'000);
 	stress_test(1'000'000);
+	stress_test_independent(100);
+	stress_test_independent(1'000);
+	stress_test_independent(1'000'000);
 	performance_test();
 }
-- 
cgit v1.2.3


From c31dcca8b822a38298c3dd624c3c1c0c23caa57d Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Sat, 17 Aug 2024 20:30:08 +0200
Subject: improved monotonic onvex hull

---
 content/datastructures/monotonicConvexHull.cpp |   4 +--
 tcr.pdf                                        | Bin 691092 -> 691111 bytes
 test/datastructures/monotonicConvexHull.cpp    |  41 ++++++++++++++++++++-----
 3 files changed, 35 insertions(+), 10 deletions(-)

(limited to 'test/datastructures')

diff --git a/content/datastructures/monotonicConvexHull.cpp b/content/datastructures/monotonicConvexHull.cpp
index e84ad86..f1721ae 100644
--- a/content/datastructures/monotonicConvexHull.cpp
+++ b/content/datastructures/monotonicConvexHull.cpp
@@ -1,5 +1,5 @@
 // Min über Geraden mit MONOTONEN Inserts UND Queries. Jede neue
-// Gerade hat kleinere Steigung als alle vorherigen.
+// Gerade hat kleineres pair(m, c) als alle vorherigen.
 struct Line {
 	ll m, c;
 	ll operator()(ll x) {return m*x+c;}
@@ -20,7 +20,7 @@ void add(ll m, ll c) { // m fallend, Laufzeit O(1) amortisiert
 	ptr = min(ptr, sz(ls) - 1);
 }
 
-ll query(ll x) { // x steigend, Laufzeit: O(1) amortisiert
+ll query(ll x) { // x >= letztes x, Laufzeit: O(1) amortisiert
 	ptr = min(ptr, sz(ls) - 1);
 	while (ptr + 1 < sz(ls) && ls[ptr + 1](x) < ls[ptr](x)) ptr++;
 	return ls[ptr](x);
diff --git a/tcr.pdf b/tcr.pdf
index d107dab..199c3de 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp
index 9edfb4b..0415068 100644
--- a/test/datastructures/monotonicConvexHull.cpp
+++ b/test/datastructures/monotonicConvexHull.cpp
@@ -13,17 +13,30 @@ void stress_test(ll range) {
 	ll queries = 0;
 	for (int tries = 0; tries < 1000; tries++) {
 		int n = Random::integer<int>(1, 100);
-		auto ms = Random::distinct<ll>(n, -range, range);
+		auto ms = Random::integers<ll>(n, -range, range);
 		sort(all(ms), greater<>{});
-		auto xs = Random::distinct<ll>(n*100, -range*n, range*n);
+		auto cs = ms;
+		for (int l = 0, r = 0; l < n;) {
+			while (r < n && ms[l] == ms[r]) r++;
+			auto tmp = Random::distinct<ll>(r - l, -range, range);
+			sort(all(tmp), greater<>{});
+			for (int c : tmp) {
+				cs[l] = c;
+				l++;
+			}
+		}
+
+		auto xs = Random::integers<ll>(n*100, -range*n, range*n);
 		sort(all(xs));
 		int i = 0;
 
 		vector<Line> naive;
 
 		MCH mch;
-		for (ll m : ms) {
-			ll c = Random::integer<ll>(-range, range);
+		for (int k = 0; k < n; k++) {
+			ll m = ms[k];
+			ll c = cs[k];
+
 			mch.add(m, c);
 			naive.emplace_back(m, c);
 
@@ -46,18 +59,30 @@ void stress_test_independent(ll range) {
 	ll queries = 0;
 	for (int tries = 0; tries < 1000; tries++) {
 		int n = Random::integer<int>(1, 100);
-		auto ms = Random::distinct<ll>(n, -range, range);
+		auto ms = Random::integers<ll>(n, -range, range);
 		sort(all(ms), greater<>{});
+		auto cs = ms;
+		for (int l = 0, r = 0; l < n;) {
+			while (r < n && ms[l] == ms[r]) r++;
+			auto tmp = Random::distinct<ll>(r - l, -range, range);
+			sort(all(tmp), greater<>{});
+			for (int c : tmp) {
+				cs[l] = c;
+				l++;
+			}
+		}
 
 		vector<Line> naive;
 
 		MCH mch;
-		for (ll m : ms) {
-			ll c = Random::integer<ll>(-range, range);
+		for (int i = 0; i < n; i++) {
+			ll m = ms[i];
+			ll c = cs[i];
+
 			mch.add(m, c);
 			naive.emplace_back(m, c);
 
-			auto xs = Random::distinct<ll>(100, -range, range);
+			auto xs = Random::integers<ll>(100, -range, range);
 			sort(all(xs));
 			auto tmp = mch;
 
-- 
cgit v1.2.3


From 65e5812f5b88989ea3ce4ac232f882004c60cc73 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Thu, 5 Sep 2024 14:20:50 +0200
Subject: more tests

---
 .gitignore                                   |  2 ++
 test/datastructures/dynamicConvexHull.cpp    |  2 +-
 test/datastructures/stlPriorityQueue.cpp     |  6 +++++
 test/datastructures/stlPriorityQueue.cpp.awk | 37 ++++++++++++++++++++++++++++
 test/datastructures/stlRope.cpp              |  6 +++++
 test/datastructures/stlRope.cpp.awk          | 27 ++++++++++++++++++++
 test/test.sh                                 | 23 ++++++++++++++---
 7 files changed, 98 insertions(+), 5 deletions(-)
 create mode 100644 test/datastructures/stlPriorityQueue.cpp
 create mode 100644 test/datastructures/stlPriorityQueue.cpp.awk
 create mode 100644 test/datastructures/stlRope.cpp
 create mode 100644 test/datastructures/stlRope.cpp.awk

(limited to 'test/datastructures')

diff --git a/.gitignore b/.gitignore
index 632f1b8..4c03241 100644
--- a/.gitignore
+++ b/.gitignore
@@ -225,3 +225,5 @@ TSWLatexianTemp*
 build/*
 # dont ignore build tcr
 !tcr.pdf
+# ignore build test awk files
+test/awk/*
diff --git a/test/datastructures/dynamicConvexHull.cpp b/test/datastructures/dynamicConvexHull.cpp
index f163397..e0345af 100644
--- a/test/datastructures/dynamicConvexHull.cpp
+++ b/test/datastructures/dynamicConvexHull.cpp
@@ -55,7 +55,7 @@ void performance_test() {
 		hash += hd.query(x);
 		t.stop();
 	}
-	if (t.time > 100) cerr << "too slow: " << t.time << FAIL;
+	if (t.time > 200) cerr << "too slow: " << t.time << FAIL;
 	cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
 }
 
diff --git a/test/datastructures/stlPriorityQueue.cpp b/test/datastructures/stlPriorityQueue.cpp
new file mode 100644
index 0000000..669f4d4
--- /dev/null
+++ b/test/datastructures/stlPriorityQueue.cpp
@@ -0,0 +1,6 @@
+#include "../util.h"
+#include <datastructures/stlPriorityQueue.cpp>
+
+int main() {
+	test();
+}
\ No newline at end of file
diff --git a/test/datastructures/stlPriorityQueue.cpp.awk b/test/datastructures/stlPriorityQueue.cpp.awk
new file mode 100644
index 0000000..99d0fb9
--- /dev/null
+++ b/test/datastructures/stlPriorityQueue.cpp.awk
@@ -0,0 +1,37 @@
+/auto/ {
+	print "void test() {"
+	print "pQueue<ll> pq, pq2;"
+	print "pq.push(1);"
+	print "pq.push(5);"
+	print "pq.push(7);"
+	print "pq2.push(2);"
+	print "pq2.push(4);"
+	print "pq2.push(8);"
+}
+END {
+	print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
+	print "if (pq.top() != 8) cerr << \"error, got: \" << pq.top() << \", expected: 8\" << FAIL;"
+	print "pq.pop();"
+	print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
+	print "if (pq.top() != 7) cerr << \"error, got: \" << pq.top() << \", expected: 7\" << FAIL;"
+	print "pq.pop();"
+	print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
+	print "if (pq.top() != 6) cerr << \"error, got: \" << pq.top() << \", expected: 6\" << FAIL;"
+	print "pq.pop();"
+	print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
+	print "if (pq.top() != 5) cerr << \"error, got: \" << pq.top() << \", expected: 5\" << FAIL;"
+	print "pq.pop();"
+	print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
+	print "if (pq.top() != 4) cerr << \"error, got: \" << pq.top() << \", expected: 4\" << FAIL;"
+	print "pq.pop();"
+	print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
+	print "if (pq.top() != 2) cerr << \"error, got: \" << pq.top() << \", expected: 2\" << FAIL;"
+	print "pq.pop();"
+	print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
+	print "if (pq.top() != 1) cerr << \"error, got: \" << pq.top() << \", expected: 1\" << FAIL;"
+	print "pq.pop();"
+	print "if (!pq.empty()) cerr << \"error, got: \" << pq.top() << \", expected: empty\" << FAIL;"
+	print "cerr << \"testes example\" << endl;"
+	print "}"
+}
+{ print }
diff --git a/test/datastructures/stlRope.cpp b/test/datastructures/stlRope.cpp
new file mode 100644
index 0000000..669f4d4
--- /dev/null
+++ b/test/datastructures/stlRope.cpp
@@ -0,0 +1,6 @@
+#include "../util.h"
+#include <datastructures/stlPriorityQueue.cpp>
+
+int main() {
+	test();
+}
\ No newline at end of file
diff --git a/test/datastructures/stlRope.cpp.awk b/test/datastructures/stlRope.cpp.awk
new file mode 100644
index 0000000..e19b8fd
--- /dev/null
+++ b/test/datastructures/stlRope.cpp.awk
@@ -0,0 +1,27 @@
+/rope<int> v;/ {
+	print "void test() {"
+	print "ll num = 5;"
+	print "ll start = 2;"
+	print "ll length = 4;"
+	print "ll offset = 3;"
+}
+/v.push_back(num);/ {
+	print "v.push_back(0);"
+	print "v.push_back(1);"
+	print "v.push_back(2);"
+	print "v.push_back(3);"
+	print "v.push_back(4);"
+}
+/rope<int> sub/ {
+	print "v.push_back(6);"
+	print "v.push_back(7);"	
+}
+/for\(auto it/ {
+	print "vector<int> got, expected = {0,1,6,2,3,4,5,7};"
+}
+END {
+	print "	got.push_back(*it)"
+	print "if (got != expected) cerr << \"error\" << endl;"
+	print "}"
+}
+{ print }
diff --git a/test/test.sh b/test/test.sh
index d34c446..d0ff995 100755
--- a/test/test.sh
+++ b/test/test.sh
@@ -8,6 +8,15 @@ declare -A cppstandard
 cppstandard["string/suffixArray.cpp"]="gnu++20"
 seedmacro=""
 
+process_awk() {
+    awk_file=$(realpath --relative-to="${PWD}" "${1}")
+    cpp_file=${awk_file%.awk}
+    folder=$(dirname $awk_file)
+    #echo "$awk_file"
+    mkdir -p "./awk/$folder"
+    awk -f "$awk_file" < "../content/$cpp_file" > "./awk/$cpp_file"
+}
+
 test_file() {
     file=$(realpath --relative-to="${PWD}" "${1}")
     echo "$file:"
@@ -16,7 +25,7 @@ test_file() {
     if [[ -v cppstandard[$file] ]]; then
         std=${cppstandard[$file]}
     fi
-    g++ -std=$std "$file" -I ../content/ -O2 -Wall -Wextra -Wshadow -Werror $seedmacro
+    g++ -std=$std "$file" -I ./awk/ -I ../content/ -O2 -Wall -Wextra -Wshadow -Werror $seedmacro
     echo "running..."
     timeout --foreground 60s ./a.out
     echo ""
@@ -25,10 +34,8 @@ test_file() {
 
 list_missing() {
     declare -A ignore
-    ignore["datastructures/stlPriorityQueue.cpp"]=1
     ignore["datastructures/stlRope.cpp"]=1
     ignore["other/bitOps.cpp"]=1
-    ignore["other/pbs.cpp"]=1
     ignore["other/pragmas.cpp"]=1
     ignore["other/stuff.cpp"]=1
     ignore["other/timed.cpp"]=1
@@ -46,10 +53,18 @@ list_missing() {
     done
 }
 
+rm -rf ./awk/
+find . -type f -path '*.awk' -print0 | sort -z | while read -d $'\0' file
+do
+    process_awk "$file"
+done
+
 if [ "$#" -ne 0 ]; then
     for arg in "$@"
     do
-        if [[ $arg == "--missing" ]]; then
+        if [[ $arg == "--awk" ]]; then
+            echo "processed all awk files"
+        elif [[ $arg == "--missing" ]]; then
             list_missing
         elif [[ $arg == --seed=* ]]; then
             seedmacro="-DSEED=${arg:7}ll"
-- 
cgit v1.2.3