From fd79fe020011ed552d8763339434458e9f1f10b6 Mon Sep 17 00:00:00 2001
From: Gloria Mundi <gloria@gloria-mundi.eu>
Date: Fri, 7 Jun 2024 18:35:50 +0200
Subject: yeah maybe I should actually commit the test code

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

(limited to 'datastructures/test/treap2.cpp')

diff --git a/datastructures/test/treap2.cpp b/datastructures/test/treap2.cpp
new file mode 100644
index 0000000..1a435d3
--- /dev/null
+++ b/datastructures/test/treap2.cpp
@@ -0,0 +1,41 @@
+#include "../treap2.cpp"
+
+void test(int n) {
+	Treap treap;
+	vector<ll> dumb;
+	for (int i = 0; i < n; i++) {
+		assert(treap.getSize(treap.root) == ssize(dumb));
+		int j = util::randint(ssize(dumb) + 1);
+		ll x = util::randint();
+		treap.insert(j, x);
+		dumb.insert(begin(dumb) + j, x);
+	}
+	for (int i = 0; i < 5*n; i++) {
+		assert(treap.getSize(treap.root) == ssize(dumb));
+		{
+			int j = util::randint(ssize(dumb));
+			treap.remove(j);
+			dumb.erase(begin(dumb) + j);
+		}
+		{
+			int j = util::randint(ssize(dumb) + 1);
+			ll x = util::randint();
+			treap.insert(j, x);
+			dumb.insert(begin(dumb) + j, x);
+		}
+	}
+	for (int i = 0; i < n; i++) {
+		assert(treap.getSize(treap.root) == ssize(dumb));
+		int j = util::randint(ssize(dumb));
+		treap.remove(j);
+		dumb.erase(begin(dumb) + j);
+	}
+	assert(treap.root < 0);
+	assert(empty(dumb));
+}
+
+int main() {
+	test(1000);
+	test(1);
+	test(0);
+}
-- 
cgit v1.2.3