more tests

5 files changed, 89 insertions, 6 deletions

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
--- a/tcr.pdf
+++ b/tcr.pdf
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();
+}