summaryrefslogtreecommitdiff
path: root/test/datastructures
diff options
context:
space:
mode:
Diffstat (limited to 'test/datastructures')
-rw-r--r--test/datastructures/bitset.cpp6
-rw-r--r--test/datastructures/fenwickTree.cpp58
-rw-r--r--test/datastructures/fenwickTree2.cpp60
-rw-r--r--test/datastructures/lazyPropagation.cpp61
-rw-r--r--test/datastructures/segmentTree.cpp122
-rw-r--r--test/datastructures/sparseTable.cpp51
-rw-r--r--test/datastructures/sparseTableDisjoint.cpp48
-rw-r--r--test/datastructures/unionFind.cpp109
-rw-r--r--test/datastructures/waveletTree.cpp75
9 files changed, 590 insertions, 0 deletions
diff --git a/test/datastructures/bitset.cpp b/test/datastructures/bitset.cpp
new file mode 100644
index 0000000..2ba61a5
--- /dev/null
+++ b/test/datastructures/bitset.cpp
@@ -0,0 +1,6 @@
+#include "../util.h"
+
+int main() {
+ int x = 0;
+ #include <datastructures/bitset.cpp>
+}
diff --git a/test/datastructures/fenwickTree.cpp b/test/datastructures/fenwickTree.cpp
new file mode 100644
index 0000000..f2a490a
--- /dev/null
+++ b/test/datastructures/fenwickTree.cpp
@@ -0,0 +1,58 @@
+#include "../util.h"
+#include <datastructures/fenwickTree.cpp>
+
+//void update(int i, ll val)
+//void init(int n)
+//prefix_sum(int i)
+
+void stress_test() {
+ ll queries = 0;
+ for (int tries = 0; tries < 100; tries++) {
+ int n = Random::integer<int>(10, 100);
+ init(n);
+ vector<ll> naive(n);
+ for (int operations = 0; operations < 1000; operations++) {
+ {
+ int i = Random::integer<int>(0, n);
+ ll x = Random::integer<ll>(-1000, 1000);
+ update(i, x);
+ naive[i] += x;
+ }
+ {
+ queries++;
+ int i = Random::integer<int>(0, n);
+ ll got = prefix_sum(i);
+ ll expected = 0;
+ for (int j = 0; j < i; j++) expected += naive[j];
+ if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+ }
+ }
+ }
+ cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+ timer t;
+ t.start();
+ init(N);
+ t.stop();
+ hash_t hash = 0;
+ for (int operations = 0; operations < N; operations++) {
+ int i = Random::integer<int>(0, N);
+ int j = Random::integer<int>(0, N);
+ ll x = Random::integer<ll>(-1000, 1000);
+
+ t.start();
+ update(i, x);
+ hash ^= prefix_sum(j);
+ 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/fenwickTree2.cpp b/test/datastructures/fenwickTree2.cpp
new file mode 100644
index 0000000..d332dc8
--- /dev/null
+++ b/test/datastructures/fenwickTree2.cpp
@@ -0,0 +1,60 @@
+#include "../util.h"
+#include <datastructures/fenwickTree2.cpp>
+
+//void update(int l, int r, ll val)
+//void init(int n)
+//prefix_sum(int i)
+
+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);
+ init(naive);
+ for (int operations = 0; operations < 1000; operations++) {
+ {
+ auto [i, j] = Random::pair<int>(0, n);
+ ll x = Random::integer<ll>(-1000, 1000);
+ update(i, j, x);
+ for (int k = i; k < j; k++) naive[k] += x;
+ }
+ {
+ queries++;
+ int i = Random::integer<int>(0, n);
+ ll got = prefix_sum(i);
+ ll expected = 0;
+ for (int j = 0; j < i; j++) expected += naive[j];
+ if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+ }
+ }
+ }
+ cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 1'000'000;
+void performance_test() {
+ timer t;
+ vector<ll> tmp = Random::integers<ll>(N, -1000, 1000);
+ t.start();
+ init(tmp);
+ t.stop();
+ hash_t hash = 0;
+ for (int operations = 0; operations < N; operations++) {
+ int i = Random::integer<int>(0, N);
+ int j = Random::integer<int>(0, N);
+ int k = Random::integer<int>(0, N);
+ ll x = Random::integer<ll>(-1000, 1000);
+
+ t.start();
+ update(i, j, x);
+ hash ^= prefix_sum(k);
+ t.stop();
+ }
+ if (t.time > 750) 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/lazyPropagation.cpp b/test/datastructures/lazyPropagation.cpp
new file mode 100644
index 0000000..7b0e448
--- /dev/null
+++ b/test/datastructures/lazyPropagation.cpp
@@ -0,0 +1,61 @@
+#include "../util.h"
+constexpr ll inf = LL::INF;
+#include <datastructures/lazyPropagation.cpp>
+
+constexpr int N = 1000'000;
+
+void stress_test() {
+ ll queries = 0;
+ for (int tries = 0; tries < 100; tries++) {
+ int n = Random::integer<int>(10, 100);
+ vector<ll> naive = Random::integers<ll>(n, -1000, 1000);
+ SegTree tree(naive);
+ for (int operations = 0; operations < 1000; operations++) {
+ {
+ int l = Random::integer<int>(0, n + 1);
+ int r = Random::integer<int>(0, n + 1);
+ //if (l > r) swap(l, r);
+ ll x = Random::integer<ll>(-1000, 1000);
+ tree.update(l, r, x);
+ for (int j = l; j < r; j++) naive[j] = x;
+ }
+ {
+ queries++;
+ int l = Random::integer<int>(0, n + 1);
+ int r = Random::integer<int>(0, n + 1);
+ //if (l > r) swap(l, r);
+ ll got = tree.query(l, r);
+ ll expected = 0;
+ for (int j = l; j < r; j++) expected += naive[j];
+ if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+ }
+ }
+ }
+ cerr << "tested random queries: " << queries << endl;
+}
+
+void performance_test() {
+ timer t;
+ t.start();
+ vector<ll> tmp(N);
+ SegTree tree(tmp);
+ t.stop();
+ hash_t hash = 0;
+ for (int operations = 0; operations < N; operations++) {
+ auto [l1, r1] = Random::pair<int>(0, N + 1);
+ auto [l2, r2] = Random::pair<int>(0, N + 1);
+ ll x1 = Random::integer<ll>(-1000, 1000);
+
+ t.start();
+ tree.update(l1, r1, x1);
+ hash ^= tree.query(l2, r2);
+ t.stop();
+ }
+ if (t.time > 2000) 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/segmentTree.cpp b/test/datastructures/segmentTree.cpp
new file mode 100644
index 0000000..fbac13e
--- /dev/null
+++ b/test/datastructures/segmentTree.cpp
@@ -0,0 +1,122 @@
+#include "../util.h"
+#include <datastructures/segmentTree.cpp>
+
+constexpr int N = 1'000'000;
+
+//void update(int i, ll val)
+//ll query(int l, int r)
+
+//point update + range query
+void stress_test1() {
+ ll queries = 0;
+ for (int tries = 0; tries < 100; tries++) {
+ int n = Random::integer<int>(10, 100);
+ vector<ll> naive = Random::integers<ll>(n, -1000, 1000);
+ SegTree tree(naive);
+ for (int operations = 0; operations < 1000; operations++) {
+ {
+ int i = Random::integer<int>(0, n);
+ ll x = Random::integer<ll>(-1000, 1000);
+ tree.update(i, x);
+ naive[i] = x;//point assignment
+ }
+ {
+ queries++;
+ int l = Random::integer<int>(0, n + 1);
+ int r = Random::integer<int>(0, n + 1);
+ //if (l > r) swap(l, r);
+ ll got = tree.query(l, r);
+ ll expected = 0;
+ for (int j = l; j < r; j++) expected += naive[j];//range sum
+ if (got != expected) cerr << " got: " << got << ", expected: " << expected << FAIL;
+ }
+ }
+ }
+ cerr << " tested random queries: " << queries << endl;
+}
+
+//point update + range query
+void performance_test1() {
+ timer t;
+ t.start();
+ vector<ll> tmp(N);
+ SegTree tree(tmp);
+ t.stop();
+ hash_t hash = 0;
+ for (int operations = 0; operations < N; operations++) {
+ int i = Random::integer<int>(0, N);
+ auto [l, r] = Random::pair<int>(0, N + 1);
+ ll x = Random::integer<ll>(-1000, 1000);
+
+ t.start();
+ tree.update(i, x);
+ hash ^= tree.query(l, r);
+ t.stop();
+ }
+ if (t.time > 1000) cerr << " too slow: " << t.time << FAIL;
+ cerr << " tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+//void modify(int l, int r, T val)
+//ll query(int i)
+
+//range update + point query
+void stress_test2() {
+ ll queries = 0;
+ for (int tries = 0; tries < 100; tries++) {
+ int n = Random::integer<int>(10, 100);
+ vector<ll> naive(n);
+ SegTree tree(naive);
+ naive = Random::integers<ll>(n, -1000, 1000);
+ copy(all(naive), tree.tree.begin() + n);
+ for (int operations = 0; operations < 1000; operations++) {
+ {
+ int l = Random::integer<int>(0, n + 1);
+ int r = Random::integer<int>(0, n + 1);
+ //if (l > r) swap(l, r);
+ ll x = Random::integer<ll>(-1000, 1000);
+ tree.modify(l, r, x);
+ for (int j = l; j < r; j++) naive[j] += x;//range add
+ }
+ {
+ queries++;
+ int i = Random::integer<int>(0, n);
+ ll got = tree.query(i);
+ ll expected = naive[i];//point query
+ if (got != expected) cerr << " got: " << got << ", expected: " << expected << FAIL;
+ }
+ }
+ }
+ cerr << " tested random queries: " << queries << endl;
+}
+
+//range update + point query
+void performance_test2() {
+ timer t;
+ t.start();
+ vector<ll> tmp(N);
+ SegTree tree(tmp);
+ t.stop();
+ hash_t hash = 0;
+ for (int operations = 0; operations < N; operations++) {
+ int i = Random::integer<int>(0, N);
+ auto [l, r] = Random::pair<int>(0, N + 1);
+ ll x = Random::integer<ll>(-1000, 1000);
+
+ t.start();
+ tree.modify(l, r, x);
+ hash ^= tree.query(i);
+ t.stop();
+ }
+ if (t.time > 1000) cerr << " too slow: " << t.time << FAIL;
+ cerr << " tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+ cerr << "point update + range query:" << endl;
+ stress_test1();
+ performance_test1();
+ cerr << "range update + point query" << endl;
+ stress_test2();
+ performance_test2();
+}
diff --git a/test/datastructures/sparseTable.cpp b/test/datastructures/sparseTable.cpp
new file mode 100644
index 0000000..2cfded9
--- /dev/null
+++ b/test/datastructures/sparseTable.cpp
@@ -0,0 +1,51 @@
+#include "../util.h"
+constexpr ll INF = LL::INF;
+#include <datastructures/sparseTable.cpp>
+
+void stress_test() {
+ ll queries = 0;
+ for (int tries = 0; tries < 1000; tries++) {
+ int n = Random::integer<int>(1, 100);
+ vector<ll> naive = Random::integers<ll>(n, -1000, 1000);
+ SparseTable st;
+ st.init(naive);
+ for (int operations = 0; operations < 1000; operations++) {
+ queries++;
+ int l = Random::integer<int>(0, n+1);
+ int r = Random::integer<int>(0, n+1);
+
+ ll got = st.queryIdempotent(l, r);
+ ll expected = r <= l ? -1 : l;
+ for (int j = l; j < r; j++) {
+ if (naive[j] < naive[expected]) expected = j;
+ }
+ if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+ }
+ }
+ cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 1'500'000;
+void performance_test() {
+ timer t;
+ vector<ll> naive = Random::integers<ll>(N, -1000, 1000);
+ t.start();
+ SparseTable st;
+ st.init(naive);
+ t.stop();
+ hash_t hash = 0;
+ for (int operations = 0; operations < N; operations++) {
+ auto [l, r] = Random::pair<int>(0, N+1);
+
+ t.start();
+ hash += st.queryIdempotent(l, r);
+ 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/sparseTableDisjoint.cpp b/test/datastructures/sparseTableDisjoint.cpp
new file mode 100644
index 0000000..258f4db
--- /dev/null
+++ b/test/datastructures/sparseTableDisjoint.cpp
@@ -0,0 +1,48 @@
+#include "../util.h"
+#include <datastructures/sparseTableDisjoint.cpp>
+
+void stress_test() {
+ ll queries = 0;
+ for (int tries = 0; tries < 1000; tries++) {
+ int n = Random::integer<int>(1, 100);
+ vector<ll> naive = Random::integers<ll>(n, -1000, 1000);
+ DisjointST st;
+ st.init(naive);
+ for (int operations = 0; operations < 1000; operations++) {
+ queries++;
+ int l = Random::integer<int>(0, n+1);
+ int r = Random::integer<int>(0, n+1);
+
+ ll got = st.query(l, r);
+ ll expected = 0;
+ for (int j = l; j < r; j++) expected += naive[j];
+ if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+ }
+ }
+ cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 1'250'000;
+void performance_test() {
+ timer t;
+ vector<ll> naive = Random::integers<ll>(N, -1000, 1000);
+ t.start();
+ DisjointST st;
+ st.init(naive);
+ t.stop();
+ hash_t hash = 0;
+ for (int operations = 0; operations < N; operations++) {
+ auto [l, r] = Random::pair<int>(0, N+1);
+
+ t.start();
+ hash += st.query(l, r);
+ 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/unionFind.cpp b/test/datastructures/unionFind.cpp
new file mode 100644
index 0000000..2afdc86
--- /dev/null
+++ b/test/datastructures/unionFind.cpp
@@ -0,0 +1,109 @@
+#include "../util.h"
+struct UF {
+ UF(int n) {init(n);}
+ #include <datastructures/unionFind.cpp>
+};
+
+struct Naive {
+ vector<vector<int>> adj;
+ vector<int> seen;
+ int counter;
+ Naive(int n) : adj(n), seen(n), counter(0) {}
+
+ template<typename F>
+ void dfs(int x, F&& f) {
+ counter++;
+ vector<int> todo = {x};
+ seen[x] = counter;
+ while (!todo.empty()) {
+ x = todo.back();
+ todo.pop_back();
+ f(x);
+ for (ll y : adj[x]) {
+ if (seen[y] != counter) {
+ seen[y] = counter;
+ todo.push_back(y);
+ }
+ }
+ }
+ }
+
+ int findSet(int a) {
+ int res = a;
+ dfs(a, [&](int x){res = min(res, x);});
+ return res;
+ }
+
+ void unionSets(int a, int b) {
+ adj[a].push_back(b);
+ adj[b].push_back(a);
+ }
+
+ int size(int a) {
+ int res = 0;
+ dfs(a, [&](int /**/){res++;});
+ return res;
+ }
+};
+
+void stress_test() {
+ ll queries = 0;
+ for (int tries = 0; tries < 200; tries++) {
+ int n = Random::integer<int>(1, 100);
+ UF uf(n);
+ Naive naive(n);
+ for (int i = 0; i < n; i++) {
+ for (int j = 0; j < 10; j++) {
+ int a = Random::integer<int>(0, n);
+ int b = Random::integer<int>(0, n);
+ uf.unionSets(a, b);
+ naive.unionSets(a, b);
+ }
+ UF tmp = uf;
+ for (int j = 0; j < n; j++) {
+ {
+ auto got = tmp.size(j);
+ auto expected = naive.size(j);
+ if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+ }
+ {
+ int a = Random::integer<int>(0, n);
+ int b = Random::integer<int>(0, n);
+ bool got = tmp.findSet(a) == tmp.findSet(b);
+ bool expected = naive.findSet(a) == naive.findSet(b);
+ if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
+ }
+ }
+ queries += n;
+ }
+ }
+ cerr << "tested random queries: " << queries << endl;
+}
+
+constexpr int N = 2'000'000;
+void performance_test() {
+ timer t;
+ t.start();
+ UF uf(N);
+ t.stop();
+ hash_t hash = 0;
+ for (int operations = 0; operations < N; operations++) {
+ int i = Random::integer<int>(0, N);
+ int j = Random::integer<int>(0, N);
+ int k = Random::integer<int>(0, N);
+ int l = Random::integer<int>(0, N);
+
+ t.start();
+ uf.unionSets(i, j);
+ hash += uf.size(k);
+ hash += uf.size(l);
+ 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/waveletTree.cpp b/test/datastructures/waveletTree.cpp
new file mode 100644
index 0000000..d294835
--- /dev/null
+++ b/test/datastructures/waveletTree.cpp
@@ -0,0 +1,75 @@
+#include "../util.h"
+#include <datastructures/waveletTree.cpp>
+
+constexpr int N = 1000'000;
+
+void stress_test() {
+ ll queries = 0;
+ for (int tries = 0; tries < 100; tries++) {
+ int n = Random::integer<int>(10, 100);
+ vector<ll> naive = Random::integers<ll>(n, -1000, 1000);
+ WaveletTree tree(naive);
+ for (int operations = 0; operations < 1000; operations++) {
+ {
+ queries++;
+ int l = Random::integer<int>(0, n + 1);
+ int r = Random::integer<int>(0, n + 1);
+ //if (l > r) swap(l, r);
+ int x = Random::integer<int>(-1, n);
+ ll got = tree.kth(l, r, x);
+ ll expected = -1;
+ if (x >= 0 && l + x < r) {
+ vector<ll> tmp(naive.begin() + l, naive.begin() + r);
+ std::sort(all(tmp));
+ expected = tmp[x];
+ }
+ if (got != expected) {
+ cerr << "kth, got: " << got << ", expected: " << expected << FAIL;
+ }
+ }
+ {
+ queries++;
+ int l = Random::integer<int>(0, n + 1);
+ int r = Random::integer<int>(0, n + 1);
+ //if (l > r) swap(l, r);
+ ll x = Random::integer<ll>(-1000, 1000);
+ ll got = tree.countSmaller(l, r, x);
+ ll expected = 0;
+ for (int j = l; j < r; j++) {
+ if (naive[j] < x) expected++;
+ }
+ if (got != expected) {
+ cerr << "count, got: " << got << ", expected: " << expected << FAIL;
+ }
+ }
+ }
+ }
+ cerr << "tested random queries: " << queries << endl;
+}
+
+void performance_test() {
+ timer t;
+ vector<ll> tmp = Random::integers<ll>(N, -1000, 1000);
+ t.start();
+ WaveletTree tree(tmp);
+ t.stop();
+ hash_t hash = 0;
+ for (int operations = 0; operations < N; operations++) {
+ auto [l1, r1] = Random::pair<int>(0, N + 1);
+ auto [l2, r2] = Random::pair<int>(0, N + 1);
+ int x1 = Random::integer<ll>(l1, r1 + 1);
+ ll x2 = Random::integer<ll>(-1000, 1000);
+
+ t.start();
+ hash ^= tree.kth(l1, r1, x1);
+ hash ^= tree.countSmaller(l2, r2, x2);
+ t.stop();
+ }
+ if (t.time > 2000) cerr << "too slow: " << t.time << FAIL;
+ cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
+}
+
+int main() {
+ stress_test();
+ performance_test();
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 20:24:35 +0000