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

---
 content/datastructures/persistent.cpp      |   8 ++---
 content/datastructures/persistentArray.cpp |   4 +--
 tcr.pdf                                    | Bin 691138 -> 691035 bytes
 test/datastructures/persistent.cpp         |  35 +++++++++++++++++++++
 test/datastructures/persistentArray.cpp    |  48 +++++++++++++++++++++++++++++
 5 files changed, 89 insertions(+), 6 deletions(-)
 create mode 100644 test/datastructures/persistent.cpp
 create mode 100644 test/datastructures/persistentArray.cpp

diff --git a/content/datastructures/persistent.cpp b/content/datastructures/persistent.cpp
index 4093cdc..7d15342 100644
--- a/content/datastructures/persistent.cpp
+++ b/content/datastructures/persistent.cpp
@@ -4,15 +4,15 @@ struct persistent {
 	vector<pair<int, T>> data;
 
 	persistent(int& time, T value = {}) 
-		: time(time), data(1, {time, value}) {}
+		: time(time), data(1, {2*time, value}) {}
 	
 	T get(int t) {
-		return prev(upper_bound(all(data), pair{t+1, T{}}))->second;
+		return prev(upper_bound(all(data), pair{2*t+1, T{}}))->second;
 	}
 	
 	int set(T value) {
-		time += 2;
-		data.push_back({time, value});
+		time++;
+		data.push_back({2*time, value});
 		return time;
 	}
 };
diff --git a/content/datastructures/persistentArray.cpp b/content/datastructures/persistentArray.cpp
index 60d8b17..8326700 100644
--- a/content/datastructures/persistentArray.cpp
+++ b/content/datastructures/persistentArray.cpp
@@ -10,8 +10,8 @@ struct persistentArray {
 	T get(int p, int t) {return data[p].get(t);}
 
 	int set(int p, T value) {
-		mods.push_back({p, time});
-		return data[p].set(value);
+		mods.push_back({p, data[p].set(value)});
+		return mods.back().second;
 	}
 
 	void reset(int t) {
diff --git a/tcr.pdf b/tcr.pdf
index 608476d..f4b94cd 100644
Binary files a/tcr.pdf and b/tcr.pdf differ
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