diff options
Diffstat (limited to 'test/datastructures')
21 files changed, 110 insertions, 115 deletions
diff --git a/test/datastructures/LCT.cpp b/test/datastructures/LCT.cpp index 58d76d7..68a952c 100644 --- a/test/datastructures/LCT.cpp +++ b/test/datastructures/LCT.cpp @@ -73,13 +73,13 @@ struct Naive { } }; dfs_comp(dfs_comp, x); - return seen[Random::integer<int>(sz(seen))]; + return seen[Random::integer<int>(ssize(seen))]; } int randomAdj(int x) { if (adj[x].empty()) return -1; - vector<int> seen(all(adj[x])); - return seen[Random::integer<int>(sz(seen))]; + vector<int> seen(begin(adj[x]), end(adj[x])); + return seen[Random::integer<int>(ssize(seen))]; } }; @@ -179,7 +179,7 @@ void performance_test() { 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]); diff --git a/test/datastructures/dynamicConvexHull.cpp b/test/datastructures/dynamicConvexHull.cpp index e0345af..02e50f4 100644 --- a/test/datastructures/dynamicConvexHull.cpp +++ b/test/datastructures/dynamicConvexHull.cpp @@ -29,7 +29,7 @@ void stress_test(ll range) { ll got = hd.query(x); ll expected = naive[0](x); - for (auto l : naive) expected = max(expected, l(x)); + for (auto l : naive) expected = min(expected, l(x)); if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; queries++; @@ -49,7 +49,7 @@ void performance_test() { 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); diff --git a/test/datastructures/dynamicConvexHull.lichao.cpp b/test/datastructures/dynamicConvexHull.lichao.cpp index d50ca60..f692e92 100644 --- a/test/datastructures/dynamicConvexHull.lichao.cpp +++ b/test/datastructures/dynamicConvexHull.lichao.cpp @@ -8,7 +8,7 @@ void stress_test(ll range) { for (int tries = 0; tries < 1000; tries++) { int n = Random::integer<int>(1, 100); xs = Random::distinct(n, -range, range); - sort(all(xs)); + ranges::sort(xs); HullDynamic hd; Lichao lichao; @@ -16,11 +16,11 @@ void stress_test(ll range) { ll m = Random::integer<ll>(-range, range); ll c = Random::integer<ll>(-range, range); hd.add(m, c); - lichao.insert({-m, -c}); + lichao.insert({m, c}); for (ll x : xs) { ll gotA = hd.query(x); - ll gotB = -lichao.query(x); + ll gotB = lichao.query(x); if (gotA != gotB) cerr << "gotA: " << gotA << ", gotB: " << gotB << FAIL; queries++; diff --git a/test/datastructures/fenwickTree.cpp b/test/datastructures/fenwickTree.cpp index c1ef6bf..f2a490a 100644 --- a/test/datastructures/fenwickTree.cpp +++ b/test/datastructures/fenwickTree.cpp @@ -23,7 +23,7 @@ void stress_test() { 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]; + for (int j = 0; j < i; j++) expected += naive[j]; if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; } } @@ -42,7 +42,7 @@ void performance_test() { 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); diff --git a/test/datastructures/fenwickTree2.cpp b/test/datastructures/fenwickTree2.cpp index 89d5b0f..bc0753f 100644 --- a/test/datastructures/fenwickTree2.cpp +++ b/test/datastructures/fenwickTree2.cpp @@ -23,7 +23,7 @@ void stress_test() { 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]; + for (int j = 0; j < i; j++) expected += naive[j]; if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; } } @@ -44,7 +44,7 @@ void performance_test() { 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); diff --git a/test/datastructures/lazyPropagation.cpp b/test/datastructures/lazyPropagation.cpp index feb07f0..16db945 100644 --- a/test/datastructures/lazyPropagation.cpp +++ b/test/datastructures/lazyPropagation.cpp @@ -34,6 +34,39 @@ void stress_test() { cerr << "tested random queries: " << queries << endl; } +void stress_test_binary_search() { + ll queries = 0; + for (int tries = 0; tries < 100; tries++) { + int n = Random::integer<int>(10, 100); + vector<ll> naive = Random::integers<ll>(n, 0, 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>(0, 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); + ll x = Random::integer<ll>(0, 10000); + //if (l > r) swap(l, r); + int got = tree.binary_search(l, r, [x](ll v) { return v >= x; }); + ll sum; + int j; + for (j = l, sum = 0; j < r && sum < x; j++) sum += naive[j]; + int expected = sum >= x ? j : -1; + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + } + } + cerr << "tested random binary searches: " << queries << endl; +} + void performance_test() { timer t; t.start(); @@ -45,7 +78,7 @@ void performance_test() { 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); @@ -55,7 +88,31 @@ void performance_test() { cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } +void performance_test_binary_search() { + 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>(0, 1000); + ll x2 = Random::integer<ll>(0, 1000 * N); + + t.start(); + tree.update(l1, r1, x1); + hash ^= tree.binary_search(l2, r2, [x2](ll v) { return v >= 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(); + stress_test_binary_search(); performance_test(); + performance_test_binary_search(); } diff --git a/test/datastructures/lichao.cpp b/test/datastructures/lichao.cpp index f4b797b..1639b3d 100644 --- a/test/datastructures/lichao.cpp +++ b/test/datastructures/lichao.cpp @@ -7,7 +7,7 @@ void stress_test(ll range) { for (int tries = 0; tries < 1000; tries++) { int n = Random::integer<int>(1, 100); xs = Random::distinct<ll>(n, -range, range); - sort(all(xs)); + ranges::sort(xs); vector<ll> naive(n, INF); Lichao tree; @@ -42,7 +42,7 @@ 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)); + ranges::sort(xs); t.start(); Lichao tree; diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp index 0415068..98d74f8 100644 --- a/test/datastructures/monotonicConvexHull.cpp +++ b/test/datastructures/monotonicConvexHull.cpp @@ -1,7 +1,5 @@ #include "../util.h" -struct MCH { - #include <datastructures/monotonicConvexHull.cpp> -}; +#include <datastructures/monotonicConvexHull.cpp> struct Line { ll m, c; @@ -14,12 +12,12 @@ void stress_test(ll range) { 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<>{}); + ranges::sort(ms | views::reverse); 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<>{}); + ranges::sort(tmp | views::reverse); for (int c : tmp) { cs[l] = c; l++; @@ -27,12 +25,12 @@ void stress_test(ll range) { } auto xs = Random::integers<ll>(n*100, -range*n, range*n); - sort(all(xs)); + ranges::sort(xs); int i = 0; vector<Line> naive; - MCH mch; + Envelope mch; for (int k = 0; k < n; k++) { ll m = ms[k]; ll c = cs[k]; @@ -60,12 +58,12 @@ void stress_test_independent(ll range) { 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<>{}); + ranges::sort(ms | views::reverse); 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<>{}); + ranges::sort(tmp | views::reverse); for (int c : tmp) { cs[l] = c; l++; @@ -74,7 +72,7 @@ void stress_test_independent(ll range) { vector<Line> naive; - MCH mch; + Envelope mch; for (int i = 0; i < n; i++) { ll m = ms[i]; ll c = cs[i]; @@ -83,7 +81,7 @@ void stress_test_independent(ll range) { naive.emplace_back(m, c); auto xs = Random::integers<ll>(100, -range, range); - sort(all(xs)); + ranges::sort(xs); auto tmp = mch; for (auto x : xs) { @@ -103,17 +101,17 @@ 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<>{}); + ranges::sort(ms | views::reverse); auto xs = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000); - sort(all(xs)); - MCH mch; + ranges::sort(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); diff --git a/test/datastructures/pbds.cpp b/test/datastructures/pbds.cpp deleted file mode 100644 index 9080332..0000000 --- a/test/datastructures/pbds.cpp +++ /dev/null @@ -1,11 +0,0 @@ -#include "../util.h" -#include <datastructures/pbds.cpp> - -int main() { - Tree<int> t1, t2; - swap(t1, t2); - hashSet<int> s1, s2; - swap(s1, s2); - hashMap<int, int> m1, m2; - swap(m1, m2); -}
\ No newline at end of file diff --git a/test/datastructures/persistentArray.cpp b/test/datastructures/persistentArray.cpp index 6712089..ef8e52b 100644 --- a/test/datastructures/persistentArray.cpp +++ b/test/datastructures/persistentArray.cpp @@ -24,19 +24,19 @@ void stress_test() { 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)); + if (ssize(expected) < 1) continue; + int j = Random::integer<int>(0, ssize(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)); + if (ssize(expected) < 1) continue; + int j = Random::integer<int>(0, ssize(expected)); got.reset(expected[j].first); expected.resize(j + 1); cur = expected.back().second; } - + } queries += n; } diff --git a/test/datastructures/segmentTree.cpp b/test/datastructures/segmentTree.cpp index fbac13e..2473724 100644 --- a/test/datastructures/segmentTree.cpp +++ b/test/datastructures/segmentTree.cpp @@ -47,7 +47,7 @@ void performance_test1() { 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); @@ -68,7 +68,7 @@ void stress_test2() { vector<ll> naive(n); SegTree tree(naive); naive = Random::integers<ll>(n, -1000, 1000); - copy(all(naive), tree.tree.begin() + n); + ranges::copy(naive, tree.tree.begin() + n); for (int operations = 0; operations < 1000; operations++) { { int l = Random::integer<int>(0, n + 1); @@ -102,7 +102,7 @@ void performance_test2() { 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); diff --git a/test/datastructures/sparseTable.cpp b/test/datastructures/sparseTable.cpp index 7577694..843e962 100644 --- a/test/datastructures/sparseTable.cpp +++ b/test/datastructures/sparseTable.cpp @@ -8,13 +8,13 @@ void stress_test() { int n = Random::integer<int>(1, 100); vector<ll> naive = Random::integers<ll>(n, -1000, 1000); SparseTable st; - st.init(&naive); + 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 got = st.query(l, r); ll expected = r <= l ? -1 : l; for (int j = l; j < r; j++) { if (naive[j] < naive[expected]) expected = j; @@ -31,14 +31,14 @@ void performance_test() { vector<ll> naive = Random::integers<ll>(N, -1000, 1000); t.start(); SparseTable st; - st.init(&naive); + 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); + hash += st.query(l, r); t.stop(); } if (t.time > 500) cerr << "too slow: " << t.time << FAIL; diff --git a/test/datastructures/sparseTableDisjoint.cpp b/test/datastructures/sparseTableDisjoint.cpp index 77bb005..258f4db 100644 --- a/test/datastructures/sparseTableDisjoint.cpp +++ b/test/datastructures/sparseTableDisjoint.cpp @@ -7,7 +7,7 @@ void stress_test() { int n = Random::integer<int>(1, 100); vector<ll> naive = Random::integers<ll>(n, -1000, 1000); DisjointST st; - st.init(&naive); + st.init(naive); for (int operations = 0; operations < 1000; operations++) { queries++; int l = Random::integer<int>(0, n+1); @@ -28,12 +28,12 @@ void performance_test() { vector<ll> naive = Random::integers<ll>(N, -1000, 1000); t.start(); DisjointST st; - st.init(&naive); + 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(); diff --git a/test/datastructures/stlHashMap.cpp b/test/datastructures/stlHashMap.cpp deleted file mode 100644 index 77976fd..0000000 --- a/test/datastructures/stlHashMap.cpp +++ /dev/null @@ -1,4 +0,0 @@ -#include "../util.h" -#include <datastructures/stlHashMap.cpp> - -int main() {}
\ No newline at end of file diff --git a/test/datastructures/stlPriorityQueue.cpp b/test/datastructures/stlPriorityQueue.cpp deleted file mode 100644 index 669f4d4..0000000 --- a/test/datastructures/stlPriorityQueue.cpp +++ /dev/null @@ -1,6 +0,0 @@ -#include "../util.h" -#include <datastructures/stlPriorityQueue.cpp> - -int main() { - test(); -}
\ No newline at end of file diff --git a/test/datastructures/stlPriorityQueue.cpp.awk b/test/datastructures/stlPriorityQueue.cpp.awk deleted file mode 100644 index 99d0fb9..0000000 --- a/test/datastructures/stlPriorityQueue.cpp.awk +++ /dev/null @@ -1,37 +0,0 @@ -/auto/ { - print "void test() {" - print "pQueue<ll> pq, pq2;" - print "pq.push(1);" - print "pq.push(5);" - print "pq.push(7);" - print "pq2.push(2);" - print "pq2.push(4);" - print "pq2.push(8);" -} -END { - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 8) cerr << \"error, got: \" << pq.top() << \", expected: 8\" << FAIL;" - print "pq.pop();" - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 7) cerr << \"error, got: \" << pq.top() << \", expected: 7\" << FAIL;" - print "pq.pop();" - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 6) cerr << \"error, got: \" << pq.top() << \", expected: 6\" << FAIL;" - print "pq.pop();" - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 5) cerr << \"error, got: \" << pq.top() << \", expected: 5\" << FAIL;" - print "pq.pop();" - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 4) cerr << \"error, got: \" << pq.top() << \", expected: 4\" << FAIL;" - print "pq.pop();" - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 2) cerr << \"error, got: \" << pq.top() << \", expected: 2\" << FAIL;" - print "pq.pop();" - print "if (pq.empty()) cerr << \"error: empty\" << FAIL;" - print "if (pq.top() != 1) cerr << \"error, got: \" << pq.top() << \", expected: 1\" << FAIL;" - print "pq.pop();" - print "if (!pq.empty()) cerr << \"error, got: \" << pq.top() << \", expected: empty\" << FAIL;" - print "cerr << \"testes example\" << endl;" - print "}" -} -{ print } diff --git a/test/datastructures/stlRope.cpp b/test/datastructures/stlRope.cpp index 669f4d4..7405e4e 100644 --- a/test/datastructures/stlRope.cpp +++ b/test/datastructures/stlRope.cpp @@ -1,6 +1,6 @@ #include "../util.h" -#include <datastructures/stlPriorityQueue.cpp> +#include <datastructures/stlRope.cpp> int main() { test(); -}
\ No newline at end of file +} diff --git a/test/datastructures/stlRope.cpp.awk b/test/datastructures/stlRope.cpp.awk index e19b8fd..df7c361 100644 --- a/test/datastructures/stlRope.cpp.awk +++ b/test/datastructures/stlRope.cpp.awk @@ -20,7 +20,7 @@ print "vector<int> got, expected = {0,1,6,2,3,4,5,7};" } END { - print " got.push_back(*it)" + print " got.push_back(*it);" print "if (got != expected) cerr << \"error\" << endl;" print "}" } diff --git a/test/datastructures/stlTree.cpp b/test/datastructures/stlTree.cpp deleted file mode 100644 index 7bacbee..0000000 --- a/test/datastructures/stlTree.cpp +++ /dev/null @@ -1,2 +0,0 @@ -#include "../util.h" -#include <datastructures/stlTree.cpp> diff --git a/test/datastructures/treap.cpp b/test/datastructures/treap.cpp index 2fc9d63..d93e0f4 100644 --- a/test/datastructures/treap.cpp +++ b/test/datastructures/treap.cpp @@ -26,14 +26,14 @@ void stress_test(int T, int n) { if (a.empty()) is_ins = true; if (is_ins) { - int ind = Random::integer<int>(0, (int)sz(a)+1); + int ind = Random::integer<int>(0, (int)ssize(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)})); + int ind = Random::integer<int>(0, (int)ssize(a)); + int cnt = Random::integer<int>(1, 1 + min<int>({(int)ssize(a)-ind, rem, (int)sqrt(n)})); t.remove(ind, cnt); a.erase(a.begin() + ind, a.begin() + ind + cnt); rem -= cnt; diff --git a/test/datastructures/waveletTree.cpp b/test/datastructures/waveletTree.cpp index d294835..e70d57b 100644 --- a/test/datastructures/waveletTree.cpp +++ b/test/datastructures/waveletTree.cpp @@ -20,7 +20,7 @@ void stress_test() { ll expected = -1; if (x >= 0 && l + x < r) { vector<ll> tmp(naive.begin() + l, naive.begin() + r); - std::sort(all(tmp)); + ranges::sort(tmp); expected = tmp[x]; } if (got != expected) { @@ -59,7 +59,7 @@ void performance_test() { 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); |