summaryrefslogtreecommitdiff
path: root/test/datastructures
diff options
context:
space:
mode:
Diffstat (limited to 'test/datastructures')
-rw-r--r--test/datastructures/LCT.cpp198
-rw-r--r--test/datastructures/dynamicConvexHull.cpp67
-rw-r--r--test/datastructures/dynamicConvexHull.lichao.cpp37
-rw-r--r--test/datastructures/fenwickTree2.cpp2
-rw-r--r--test/datastructures/lazyPropagation.cpp2
-rw-r--r--test/datastructures/lichao.cpp75
-rw-r--r--test/datastructures/monotonicConvexHull.cpp132
-rw-r--r--test/datastructures/persistent.cpp35
-rw-r--r--test/datastructures/persistentArray.cpp48
-rw-r--r--test/datastructures/stlRope.cpp6
-rw-r--r--test/datastructures/stlRope.cpp.awk27
-rw-r--r--test/datastructures/treap.cpp85
12 files changed, 712 insertions, 2 deletions
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();
+}
diff --git a/test/datastructures/dynamicConvexHull.cpp b/test/datastructures/dynamicConvexHull.cpp
new file mode 100644
index 0000000..e0345af
--- /dev/null
+++ b/test/datastructures/dynamicConvexHull.cpp
@@ -0,0 +1,67 @@
+#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) 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 > 200) 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/dynamicConvexHull.lichao.cpp b/test/datastructures/dynamicConvexHull.lichao.cpp
new file mode 100644
index 0000000..d50ca60
--- /dev/null
+++ b/test/datastructures/dynamicConvexHull.lichao.cpp
@@ -0,0 +1,37 @@
+#include "../util.h"
+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);
+}
diff --git a/test/datastructures/fenwickTree2.cpp b/test/datastructures/fenwickTree2.cpp
index d332dc8..bc0753f 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/datastructures/lazyPropagation.cpp b/test/datastructures/lazyPropagation.cpp
index 7b0e448..3030e1c 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
new file mode 100644
index 0000000..f4b797b
--- /dev/null
+++ b/test/datastructures/lichao.cpp
@@ -0,0 +1,75 @@
+#include "../util.h"
+constexpr ll INF = LL::INF;
+#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<ll>(n, -range, range);
+ 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>(-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);
+ 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(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..3ae7c4d
--- /dev/null
+++ b/test/datastructures/monotonicConvexHull.cpp
@@ -0,0 +1,132 @@
+#include "../util.h"
+#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::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++;
+ }
+ }
+
+ auto xs = Random::integers<ll>(n*100, -range*n, range*n);
+ sort(all(xs));
+ int i = 0;
+
+ vector<Line> naive;
+
+ Envelope mch;
+ for (int k = 0; k < n; k++) {
+ ll m = ms[k];
+ ll c = cs[k];
+
+ 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) cerr << "got: " << got << ", expected: " << expected << FAIL;
+ queries++;
+ }
+ }
+ }
+ 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::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;
+
+ Envelope mch;
+ 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::integers<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;
+ 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));
+ Envelope 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);
+ stress_test_independent(100);
+ stress_test_independent(1'000);
+ stress_test_independent(1'000'000);
+ performance_test();
+}
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();
+}
diff --git a/test/datastructures/stlRope.cpp b/test/datastructures/stlRope.cpp
new file mode 100644
index 0000000..7405e4e
--- /dev/null
+++ b/test/datastructures/stlRope.cpp
@@ -0,0 +1,6 @@
+#include "../util.h"
+#include <datastructures/stlRope.cpp>
+
+int main() {
+ test();
+}
diff --git a/test/datastructures/stlRope.cpp.awk b/test/datastructures/stlRope.cpp.awk
new file mode 100644
index 0000000..df7c361
--- /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/datastructures/treap.cpp b/test/datastructures/treap.cpp
new file mode 100644
index 0000000..2fc9d63
--- /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" << FAIL;
+ }
+ 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();
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 20:58:14 +0000