diff options
Diffstat (limited to 'test')
53 files changed, 2889 insertions, 54 deletions
diff --git a/test/GNUmakefile b/test/GNUmakefile index 10e3b34..5e57930 100644 --- a/test/GNUmakefile +++ b/test/GNUmakefile @@ -1,6 +1,7 @@ -TESTS = $(basename $(shell find . -type f -name '*.cpp')) -CXX = g++ -std=gnu++20 -I ../content/ -O2 -Wall -Wextra -Wshadow -Werror +TESTS = $(basename $(shell find . -path ./awk -prune -o -type f -name '*.cpp' -print)) +AWK = $(basename $(shell find . -type f -name '*.awk')) +CXX = g++ -std=gnu++20 -I awk/ -I ../content/ -O2 -Wall -Wextra -Wshadow -Werror test: $(TESTS:=.ok) @@ -8,11 +9,12 @@ missing: @find ../content -name '*.cpp' | sed 's|^../content/||' \ | while read -r f ; do [ -e "$$f" ] || echo "$$f" ; done \ | sort > missing.tmp - @sort missing.ignore | comm -23 missing.tmp - + @sort missing.ignore | comm -3 missing.tmp - @rm missing.tmp clean: rm -f $(TESTS:=.test) $(TESTS:=.ok) $(TESTS:=.d) + rm -rf awk/ %.ok: %.test timeout --foreground --verbose 60 prlimit -s$$((1<<32)) ./$< @@ -21,10 +23,14 @@ clean: %.test: %.cpp $(CXX) -o $@ $< -%.d: %.cpp +awk/%: %.awk ../content/% + @mkdir -p $(dir $@) + awk -f $*.awk < ../content/$* > $@ + +%.d: %.cpp $(addprefix awk/,$(AWK)) $(CXX) -M -MT '$*.test $*.d' -MF $@ $< .PHONY: test clean -.SECONDARY: $(TESTS:=.test) +.SECONDARY: $(TESTS:=.test) $(addprefix awk/,$(AWK)) include $(TESTS:=.d) 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(); +} diff --git a/test/geometry.h b/test/geometry.h index 7886fe2..0167d5c 100644 --- a/test/geometry.h +++ b/test/geometry.h @@ -1,6 +1,6 @@ -#include <geometry/sortAround.cpp> - namespace details { + #include <geometry/sortAround.cpp> + // Liegt p auf der Strecke a-b? bool pointInLineSegment(pt a, pt b, pt p) { if (cross(a, b, p) != 0) return false; @@ -59,7 +59,7 @@ namespace Random { for (size_t i = 0; i < dirs.size(); i++) { dirs[i] = pt(x[i], y[i]); } - sortAround(0, dirs); + details::sortAround(0, dirs); vector<pt> res = {{0, 0}}; ll maxX = 0; diff --git a/test/geometry/delaunay.cpp b/test/geometry/delaunay.cpp index 7f8ec30..5740b95 100644 --- a/test/geometry/delaunay.cpp +++ b/test/geometry/delaunay.cpp @@ -16,11 +16,11 @@ vector<pt> convexHull(vector<pt> pts){ vector<pt> h(2 * sz(pts)); auto half = [&](auto begin, auto end, int t) { for (auto it = begin; it != end; it++) { - while (k > t && cross(h[k-2], h[k-1], *it) < 0) k--;//allow collinear points! + while (k > t && cross(h[k-2], h[k-1], *it) < 0) k--; //allow collinear points! h[k++] = *it; }}; - half(all(pts), 1);// Untere Hülle. - half(next(pts.rbegin()), pts.rend(), k);// Obere Hülle. + half(all(pts), 1); // Untere Hülle. + half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle. h.resize(k); return h; } diff --git a/test/geometry/formulas3d.cpp b/test/geometry/formulas3d.cpp new file mode 100644 index 0000000..f6c04b7 --- /dev/null +++ b/test/geometry/formulas3d.cpp @@ -0,0 +1,236 @@ +#include "../util.h" +constexpr double EPS = 1e-6; +struct pt3 { + double x, y, z; + pt3 operator-(const pt3 o) const { + return {x-o.x, y-o.y, z-o.z}; + } + pt3 operator+(const pt3 o) const { + return {x+o.x, y+o.y, z+o.z}; + } + + pt3 operator*(double m) const { + return {x*m, y*m, z*m}; + } + + pt3 operator/(double d) const { + return {x/d, y/d, z/d}; + } + + friend ostream& operator<<(ostream& os, pt3 p) { + return os << "(" << p.x << ", " << p.y << ", " << p.z << ")"; + } +}; + +pt3 cross(pt3 a, pt3 b); +double abs(pt3 p); +double distToLine(pt3 a, pt3 b, pt3 p) { + return abs(cross(p - a, b - a)) / abs(b - a); +} + +#include <geometry/formulas3d.cpp> + +namespace Random { + pt3 point3d(ll l, ll r) { + return { + (double)integer<ll>(l, r), + (double)integer<ll>(l, r), + (double)integer<ll>(l, r), + }; + } + + template<size_t C> + std::array<pt3, C> distinct(ll l, ll r) { + std::array<pt3, C> res = {}; + for (size_t i = 0; i < C; i++) { + bool unqiue; + do { + res[i] = point3d(l, r); + unqiue = true; + for (size_t j = 0; j < i; j++) { + unqiue &= res[j].x != res[i].x || + res[j].y != res[i].y || + res[j].z != res[i].z; + } + } while (!unqiue); + } + return res; + } +} + +void test_dot(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto p = Random::point3d(-range, range); + auto q = Random::point3d(-range, range); + + auto expected = p.x*q.x + p.y*q.y + p.z*q.z; + auto got = dot(p, q); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested dot: " << queries << endl; +} + +void test_cross(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto p = Random::point3d(-range, range); + auto q = Random::point3d(-range, range); + + auto expected = pt3{p.y*q.z - p.z*q.y, + p.z*q.x - p.x*q.z, + p.x*q.y - p.y*q.x}; + auto got = cross(p, q); + + if (got.x != expected.x) cerr << "error: x" << FAIL; + if (got.y != expected.y) cerr << "error: y" << FAIL; + if (got.z != expected.z) cerr << "error: z" << FAIL; + queries++; + } + cerr << "tested cross: " << queries << endl; +} + +void test_abs(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto p = Random::point3d(-range, range); + + auto expected = sqrt(p.x*p.x + p.y*p.y + p.z*p.z); + auto got = abs(p); + + if (abs(got - expected) > 1e-6) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested abs: " << queries << endl; +} + +void test_mixed(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto a = Random::point3d(-range, range); + auto b = Random::point3d(-range, range); + auto c = Random::point3d(-range, range); + + auto expected = dot(cross(a, b), c); + auto got = mixed(a, b, c); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested mixed: " << queries << endl; +} + +void test_ccw(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto a = Random::point3d(-range, range); + auto b = Random::point3d(-range, range); + auto c = Random::point3d(-range, range); + auto d = Random::point3d(-range, range); + + ll expected = mixed(b - a, c - a, d - a); + if (expected < 0) expected = -1; + if (expected > 0) expected = 1; + auto got = ccw(a, b, c, d); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested ccw: " << queries << endl; +} + +void test_distToPlane(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [p, q] = Random::distinct<2>(-range, range); + auto [a, b, c] = Random::distinct<3>(-range, range); + + auto norm = cross(a - c, b - c); + norm = norm / abs(norm); + + auto gotA = distToPlane(a, b, c, p); + auto gotB = distToPlane(a, b, c, q); + auto got = ccw(a, b, c, p) * ccw(a, b, c, q) < 0 ? gotA + gotB : abs(gotA - gotB); + + auto expected = abs(dot(norm, p - q)); + + if (abs(got - expected) > 1e-6) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested distToPlane: " << queries << endl; +} + +void stress_pointOnPlane(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto p = Random::point3d(-range, range); + auto [a, b, c] = Random::distinct<3>(-range, range); + + bool expected = ccw(a, b, c, p) == 0; + bool got = pointOnPlane(a, b, c, p); + + if (got != expected) cerr << "error" << FAIL; + queries++; + } + cerr << "tested pointOnPlane: " << queries << endl; +} + +void test_linePlaneIntersection(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [p, q] = Random::distinct<2>(-range, range); + auto [a, b, c] = Random::distinct<3>(-range, range); + + if (abs(dot(p - q, cross(a-c, b-c))) < 1e-6) continue; + + auto got = linePlaneIntersection(p, q, a, b, c); + + if (distToLine(p, q, got) > 1e-6) cerr << "error: 1" << FAIL; + if (distToPlane(a, b, c, got) > 1e-6) cerr << "error: 2" << FAIL; + queries++; + } + cerr << "tested linePlaneIntersection: " << queries << endl; +} + +void test_lineLineDist(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [p, q] = Random::distinct<2>(-range, range); + auto [a, b] = Random::distinct<2>(-range, range); + + double expected = 0; + if (ccw(a, b, p, q) != 0) { + pt3 c = a + p - q; + expected = distToPlane(a, b, c, p); + } + auto got = lineLineDist(p, q, a, b); + + if (abs(got - expected) > 1e-6) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested lineLineDist: " << queries << endl; +} + +int main() { + test_dot(100); + test_dot(1'000'000); + test_cross(100); + test_cross(1'000'000); + test_abs(100); + test_abs(1'000'000); + test_mixed(100); + test_mixed(1'000'000); + test_ccw(100); + test_ccw(1'000'000); + + test_distToPlane(100); + test_distToPlane(1'000'000); + stress_pointOnPlane(100); + stress_pointOnPlane(1'000'000); + test_linePlaneIntersection(100); + test_linePlaneIntersection(1'000);//can be far away + test_lineLineDist(100); + test_lineLineDist(1'000'000); +} diff --git a/test/geometry/hpi.cpp b/test/geometry/hpi.cpp new file mode 100644 index 0000000..a2326bc --- /dev/null +++ b/test/geometry/hpi.cpp @@ -0,0 +1,291 @@ +#include "../util.h" +constexpr ll EPS = 0; +#define double ll +#define polar polar<ll> +#include <geometry/formulas.cpp> +#undef polar +#undef double +#include "../geometry.h" +ll sgn(ll x) { + return (x > 0) - (x < 0); +} +#include <geometry/hpi.cpp> + +//https://cp-algorithms.com/geometry/halfplane-intersection.html +namespace cpalgo { + // Redefine epsilon and infinity as necessary. Be mindful of precision errors. + const long double eps = 1e-9, inf = 1e9; + + // Basic point/vector struct. + struct Point { + + long double x, y; + explicit Point(long double x_ = 0, long double y_ = 0) : x(x_), y(y_) {} + Point(pt p) : x(real(p)), y(imag(p)) {} + + // Addition, substraction, multiply by constant, dot product, cross product. + + friend Point operator + (const Point& p, const Point& q) { + return Point(p.x + q.x, p.y + q.y); + } + + friend Point operator - (const Point& p, const Point& q) { + return Point(p.x - q.x, p.y - q.y); + } + + friend Point operator * (const Point& p, const long double& k) { + return Point(p.x * k, p.y * k); + } + + friend long double dot(const Point& p, const Point& q) { + return p.x * q.x + p.y * q.y; + } + + friend long double cross(const Point& p, const Point& q) { + return p.x * q.y - p.y * q.x; + } + + friend std::ostream& operator<<(std::ostream& os, const Point& p) { + return os << "(" << p.x << ", " << p.y << ")"; + } + + + }; + + // Basic half-plane struct. + struct Halfplane { + + // 'p' is a passing point of the line and 'pq' is the direction vector of the line. + Point p, pq; + long double angle; + + Halfplane() {} + Halfplane(const Point& a, const Point& b) : p(a), pq(b - a) { + angle = atan2l(pq.x, -pq.y);//patched to get same sort + } + Halfplane(array<pt, 2> ps) : Halfplane(ps[0], ps[1]) {} + Halfplane(hp h) : Halfplane(h.from, h.to) {} + + // Check if point 'r' is outside this half-plane. + // Every half-plane allows the region to the LEFT of its line. + bool out(const Point& r) { + return cross(pq, r - p) < -eps; + } + + // Comparator for sorting. + bool operator < (const Halfplane& e) const { + return angle < e.angle; + } + + // Intersection point of the lines of two half-planes. It is assumed they're never parallel. + friend Point inter(const Halfplane& s, const Halfplane& t) { + long double alpha = cross((t.p - s.p), t.pq) / cross(s.pq, t.pq); + return s.p + (s.pq * alpha); + } + + friend std::ostream& operator<<(std::ostream& os, const Halfplane& hp) { + return os << hp.p << " " << hp.p+hp.pq; + } + }; + + // Actual algorithm + vector<Point> hp_intersect(vector<Halfplane>& H) { + + /*Point box[4] = { // Bounding box in CCW order + Point(inf, inf), + Point(-inf, inf), + Point(-inf, -inf), + Point(inf, -inf) + }; + + for(int i = 0; i<4; i++) { // Add bounding box half-planes. + Halfplane aux(box[i], box[(i+1) % 4]); + H.push_back(aux); + }*/ + // Add bounding box half-planes, fixed: + H.push_back({pt( 1e9, 1e9), pt( 1e9-1, 1e9 )}); + H.push_back({pt(-1e9, 1e9), pt(-1e9 , 1e9-1)}); + H.push_back({pt(-1e9, -1e9), pt(-1e9+1, -1e9 )}); + H.push_back({pt( 1e9, -1e9), pt( 1e9 , -1e9+1)}); + + // Sort by angle and start algorithm + sort(H.begin(), H.end()); + deque<Halfplane> dq; + int len = 0; + for(int i = 0; i < int(H.size()); i++) { + + // Remove from the back of the deque while last half-plane is redundant + while (len > 1 && H[i].out(inter(dq[len-1], dq[len-2]))) { + dq.pop_back(); + --len; + } + + // Remove from the front of the deque while first half-plane is redundant + while (len > 1 && H[i].out(inter(dq[0], dq[1]))) { + dq.pop_front(); + --len; + } + + // Special case check: Parallel half-planes + if (len > 0 && fabsl(cross(H[i].pq, dq[len-1].pq)) < eps) { + // Opposite parallel half-planes that ended up checked against each other. + if (dot(H[i].pq, dq[len-1].pq) < 0.0) + return vector<Point>(); + + // Same direction half-plane: keep only the leftmost half-plane. + if (H[i].out(dq[len-1].p)) { + dq.pop_back(); + --len; + } + else continue; + } + + // Add new half-plane + dq.push_back(H[i]); + ++len; + } + + // Final cleanup: Check half-planes at the front against the back and vice-versa + while (len > 2 && dq[0].out(inter(dq[len-1], dq[len-2]))) { + dq.pop_back(); + --len; + } + + while (len > 2 && dq[len-1].out(inter(dq[0], dq[1]))) { + dq.pop_front(); + --len; + } + + // Report empty intersection if necessary + if (len < 3) return vector<Point>(); + + // Reconstruct the convex polygon from the remaining half-planes. + vector<Point> ret(len); + for(int i = 0; i+1 < len; i++) { + ret[i] = inter(dq[i], dq[i+1]); + } + ret.back() = inter(dq[len-1], dq[0]); + return ret; + } +} + +//check if a is dominated by b and c +bool naiveCheck(cpalgo::Halfplane a, cpalgo::Halfplane b, cpalgo::Halfplane c) { + return a.out(inter(b, c)); +} + +void test_check(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto a = Random::line(range); + auto b = Random::line(range); + auto c = b; + while (cross(b[0] - b[1], c[0] - c[1]) == 0) c = Random::line(range); + + bool got = hp(a[0], a[1]).check(hp(b[0], b[1]), hp(c[0], c[1])); + bool expected = naiveCheck(a, b, c); + + if (got != expected) { + cout << tries << endl; + cout << a[0] << " " << a[1] << endl; + cout << b[0] << " " << b[1] << endl; + cout << c[0] << " " << c[1] << endl; + cout << boolalpha << got << " " << expected << endl; + cerr << "error" << FAIL; + } + queries++; + } + cerr << "tested random queries: " << queries << endl; +} + +void stress_test(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto centre = Random::point<ll>(-range / 2, range / 2); + int n = Random::integer<int>(3, 30); + + vector<hp> hps1 = {//+cpalgo bounding box + {pt( 1e9, 1e9), pt(-1e9, 1e9)}, + {pt(-1e9, 1e9), pt(-1e9, -1e9)}, + {pt(-1e9, -1e9), pt( 1e9, -1e9)}, + {pt( 1e9, -1e9), pt( 1e9, 1e9)}, + }; + + vector<cpalgo::Halfplane> hps2; + for (int i = 0; i < n; i++) { + auto [a, b] = Random::line(range); + if (cross(a, b, centre) < 0) swap(a, b); + hps1.emplace_back(a, b); + hps2.emplace_back(a, b); + } + + auto expected = cpalgo::hp_intersect(hps2); + auto gotHp = intersect(hps1); + if (sz(gotHp) == 1) cerr << "WHAT?" << FAIL; + for (hp h : gotHp) { + if (h.dummy()) cerr << "DUMMY!" << FAIL;//we added a bounding box... + } + vector<cpalgo::Point> got; + if (!gotHp.empty()) { + gotHp.push_back(gotHp[0]); + for (int i = 0; i + 1 < sz(gotHp); i++) { + got.push_back(inter(cpalgo::Halfplane(gotHp[i]), cpalgo::Halfplane(gotHp[i + 1]))); + } + } + + bool eq = sz(got) == sz(expected); + for (ll i = 0; eq && i < sz(got); i++) { + eq &= float_error(got[i].x, expected[i].x) < 1e-6; + eq &= float_error(got[i].y, expected[i].y) < 1e-6; + } + + if (!eq) { + cerr << tries << endl; + cerr << setprecision(20) << endl; + for (auto tmp : hps2) cerr << tmp << endl; + cerr << endl; + for (auto tmp : expected) cerr << tmp << endl; + cerr << endl; + for (auto tmp : got) cerr << tmp << endl; + cerr << FAIL; + } + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +/*constexpr int N = 1'000'000; +void performance_test() { + timer t; + hash_t hash = 0; + double maxTime = 0; + + vector<pt> ps; + for (int i = 0; i*i <= N; i++) { + for (int j = 0; j*j <= N; j++) { + ps.emplace_back(i, j); + } + } + t.start(); + hash = shortestDist(ps); + t.stop(); + maxTime = max(maxTime, t.time); + + ps = Random::points<ll>(N, -1'000'000'000, 1'000'000'000); + t.reset(); + t.start(); + hash += shortestDist(ps); + t.stop(); + maxTime = max(maxTime, t.time); + + if (maxTime > 500) cerr << "too slow: " << maxTime << FAIL; + cerr << "tested performance: " << maxTime << "ms (hash: " << hash << ")" << endl; +}*/ + +int main() { + test_check(10); + test_check(100); + stress_test(10); + stress_test(100); + //performance_test(); +} diff --git a/test/geometry/lines.cpp b/test/geometry/lines.cpp new file mode 100644 index 0000000..7b1b99a --- /dev/null +++ b/test/geometry/lines.cpp @@ -0,0 +1,107 @@ +#include "../util.h" +constexpr double EPS = 1e-6; +#define ll double +double gcd(double x, double /**/) {return x;} //hacky +#include <geometry/formulas.cpp> +#undef ll +#include <geometry/linesAndSegments.cpp> +#include <geometry/lines.cpp> + +#include "../geometry.h" + +void stress_pointsToLine(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [a, b] = Random::line(range); + + line gotA(a, b); + if (real(a) != real(b)) { + gotA.a /= gotA.b; + gotA.c /= gotA.b; + gotA.b /= gotA.b; + } else { + gotA.c /= gotA.a; + gotA.a /= gotA.a; + } + line gotB = pointsToLine(a, b); + + if (!same(gotA, gotB)) cerr << "error" << FAIL; + queries++; + } + cerr << "tested pointsToLine: " << queries << endl; +} + +void stress_same(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [a, b] = Random::line(range); + auto [c, d] = Random::line(range); + + line lAB = pointsToLine(a, b); + line lCD = pointsToLine(c, d); + + auto got = same(lAB, lCD); + auto expected = pointOnLine(a, b, c) && pointOnLine(a, b, d); + + if (got != expected) cerr << "error" << FAIL; + queries++; + } + cerr << "tested same: " << queries << endl; +} + +void stress_parallel(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [a, b] = Random::line(range); + auto [c, d] = Random::line(range); + + line lAB = pointsToLine(a, b); + line lCD = pointsToLine(c, d); + + auto got = parallel(lAB, lCD); + auto expected = cross(b-a, d-c) == 0; + + if (got != expected) cerr << "error" << FAIL; + queries++; + } + cerr << "tested parallel: " << queries << endl; +} + +void stress_intersect(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto [a, b] = Random::line(range); + auto [c, d] = Random::line(range); + + line lAB = pointsToLine(a, b); + line lCD = pointsToLine(c, d); + + if (same(lAB, lCD)) continue; + + pt gotPT; + auto got = intersect(lAB, lCD, gotPT); + auto expected = lineIntersection(a, b, c, d); + + if (got != expected) cerr << "error: 1" << FAIL; + if (got) { + pt expectedPt = lineIntersection2(a, b, c, d); + if (float_error(real(gotPT), real(expectedPt)) > 1e-6) cerr << "error: 2" << FAIL; + if (float_error(imag(gotPT), imag(expectedPt)) > 1e-6) cerr << "error: 2" << FAIL; + } + queries++; + } + cerr << "tested intersect: " << queries << endl; +} + +int main() { + stress_pointsToLine(100); + stress_pointsToLine(100'000); + stress_same(10); + stress_same(100); + stress_same(1'000'000'000);//no precision issue since this will alwas be false... + stress_parallel(10); + stress_parallel(100); + stress_parallel(1'000'000'000); + stress_intersect(100); + stress_intersect(1'000'000'000); +} diff --git a/test/geometry/linesAndSegments.cpp b/test/geometry/linesAndSegments.cpp index 2943a67..a2da3ba 100644 --- a/test/geometry/linesAndSegments.cpp +++ b/test/geometry/linesAndSegments.cpp @@ -30,7 +30,7 @@ void stress_lineIntersection(ll range) { auto [c, d] = Random::line(range); if (ccw(a, b, c) == 0 && ccw(a, b, d) == 0) continue; - bool expected = ccw(0, a-b, c-d) == 0; + bool expected = ccw(0, a-b, c-d) != 0; bool got = lineIntersection(a, b, c, d); if (got != expected) cerr << "error" << FAIL; @@ -49,7 +49,7 @@ void stress_lineIntersection2(ll range) { auto got = lineIntersection2(a, b, c, d); if (distToLine(a, b, got) > 1e-6) cerr << "error: 1" << FAIL; - if (distToLine(a, b, got) > 1e-6) cerr << "error: 2" << FAIL; + if (distToLine(c, d, got) > 1e-6) cerr << "error: 2" << FAIL; queries++; } cerr << "tested lineIntersection2: " << queries << endl; @@ -172,7 +172,7 @@ void stress_segmentIntersection2(ll range) { if (!got.empty() != tmp) cerr << "error: 1" << FAIL; for (pt p : got) { if (distToSegment(a, b, p) > 1e-6) cerr << "error: 2" << FAIL; - if (distToSegment(a, b, p) > 1e-6) cerr << "error: 3" << FAIL; + if (distToSegment(c, d, p) > 1e-6) cerr << "error: 3" << FAIL; } if (tmp) { double gotDist = abs(got.front() - got.back()); @@ -220,7 +220,7 @@ int main() { stress_lineIntersection(100); stress_lineIntersection(1'000'000'000); stress_lineIntersection2(100); - stress_lineIntersection2(1'000'000); + stress_lineIntersection2(1'000);//intersection can bet at N^3... stress_distToLine(100); stress_distToLine(1'000'000'000); stress_projectToLine(100); diff --git a/test/geometry/polygon.cpp b/test/geometry/polygon.cpp index 1dd46ca..643ea70 100644 --- a/test/geometry/polygon.cpp +++ b/test/geometry/polygon.cpp @@ -10,7 +10,7 @@ double abs(pt p) { return hypot(real(p), imag(p)); } // Liegt p auf der Strecke a-b? -bool pointOnLineSegment(pt a, pt b, pt p) { +bool pointOnSegment(pt a, pt b, pt p) { if (cross(a, b, p) != 0) return false; auto dist = norm(a - b); return norm(a - p) <= dist && norm(b - p) <= dist; @@ -65,7 +65,7 @@ void test_windingNumber(ll range) { int cur = details::lineSegmentIntersection(p, p + pt(1, 2'000'000'007), ps[j], ps[j+1]); if (ptLess(ps[j], ps[j+1])) expected -= cur; else expected += cur; - onBorder |= pointOnLineSegment(ps[j], ps[j+1], p); + onBorder |= pointOnSegment(ps[j], ps[j+1], p); } if (onBorder) continue; if (area(ps) < 0) expected = -expected; @@ -93,7 +93,7 @@ void test_inside(ll range) { bool onBorder = false; for (int j = 0; j < n; j++) { count += details::lineSegmentIntersection(p, p + pt(1, 2'000'000'007), ps[j], ps[j+1]); - onBorder |= pointOnLineSegment(ps[j], ps[j+1], p); + onBorder |= pointOnSegment(ps[j], ps[j+1], p); } bool expected = (count % 2) && !onBorder; bool got = inside(p, ps); diff --git a/test/geometry/segmentIntersection.cpp b/test/geometry/segmentIntersection.cpp index 9862be5..6d3ddd6 100644 --- a/test/geometry/segmentIntersection.cpp +++ b/test/geometry/segmentIntersection.cpp @@ -14,7 +14,7 @@ bool pointOnLineSegment(pt a, pt b, pt p) { } // Test auf Streckenschnitt zwischen a-b und c-d. -bool lineSegmentIntersection(pt a, pt b, pt c, pt d) { +bool segmentIntersection(pt a, pt b, pt c, pt d) { if (ccw(a, b, c) == 0 && ccw(a, b, d) == 0) return pointOnLineSegment(a,b,c) || pointOnLineSegment(a,b,d) || @@ -42,7 +42,7 @@ vector<seg> randomSegs(int n, ll range) { bool naive(vector<seg>& segs) { for (ll i = 0; i < sz(segs); i++) { for (ll j = 0; j < i; j++) { - if (lineSegmentIntersection(segs[i].a, segs[i].b, segs[j].a, segs[j].b)) return true; + if (segmentIntersection(segs[i].a, segs[i].b, segs[j].a, segs[j].b)) return true; } } return false; @@ -60,7 +60,7 @@ void stress_test(ll range) { if (got != (b >= 0)) cerr << "error: invalid ans" << FAIL; auto expected = naive(segs); if (got != expected) cerr << "error: intersection not found" << FAIL; - if (got && !lineSegmentIntersection(segs[a].a, segs[a].b, segs[b].a, segs[b].b)) cerr << "error: no intersection" << FAIL; + if (got && !segmentIntersection(segs[a].a, segs[a].b, segs[b].a, segs[b].b)) cerr << "error: no intersection" << FAIL; queries += n; intersection += got; notIntersection += !got; diff --git a/test/geometry/spheres.cpp b/test/geometry/spheres.cpp new file mode 100644 index 0000000..16e0ebd --- /dev/null +++ b/test/geometry/spheres.cpp @@ -0,0 +1,28 @@ +#include "../util.h" +constexpr double PI = acos(-1.0); +#pragma GCC diagnostic ignored "-Wshadow" +#include <geometry/spheres.cpp> + +void test_consistent() { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto pLat = Random::real<double>(-180, 180); + auto pLon = Random::real<double>(0, 360); + auto qLat = Random::real<double>(-180, 180); + auto qLon = Random::real<double>(0, 360); + + point p(pLat, pLon); + point q(qLat, qLon); + + auto gotA = gcDist(pLat, pLon, qLat, qLon, 1); + auto gotB = gcDist(p, q); + + if (abs(gotA - gotB) > 1e-6) cerr << "gotA: " << gotA << ", gotB: " << gotB << FAIL; + queries++; + } + cerr << "tested random: " << queries << endl; +} + +int main() { + test_consistent(); +} diff --git a/test/graph/connect.cpp b/test/graph/connect.cpp new file mode 100644 index 0000000..bba8104 --- /dev/null +++ b/test/graph/connect.cpp @@ -0,0 +1,140 @@ +#include "../util.h" +#pragma GCC diagnostic ignored "-Wshadow" +#include "connectMinLCT.h" +constexpr ll INF = 0x3FFF'FFFF; +#include <graph/connect.cpp> + +struct Naive { + vector<multiset<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); + } + } + } + } + + bool connected(int a, int b) { + bool res = false; + dfs(a, [&](int x){res |= x == b;}); + return res; + } + + void addEdge(int a, int b) { + adj[a].insert(b); + adj[b].insert(a); + } + + void eraseEdge(int a, int b) { + adj[a].erase(adj[a].find(b)); + adj[b].erase(adj[b].find(a)); + } +}; + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 2'000; tries++) { + int n = Random::integer<int>(2, 30); + int m = Random::integer<int>(30, 300); + + vector<int> insertOrder(m); + iota(all(insertOrder), 0); + shuffle(all(insertOrder), Random::rng); + vector<pair<int, int>> edges(m, {-1, -1}); + + connect con(n, m); + Naive naive(n); + + int deleted = 0; + for (int i = 0; i < m; i++) { + { + int a = Random::integer<int>(0, n); + int b = a; + while (b == a) b = Random::integer<int>(0, n); + edges[insertOrder[i]] = {a, b}; + + con.addEdge(a, b, insertOrder[i]); + naive.addEdge(a, b); + } + + while (deleted < m && edges[deleted] != pair<int, int>{-1, -1} && Random::integer<int>(2) == 0) { + auto [a, b] = edges[deleted]; + + con.eraseEdge(deleted); + naive.eraseEdge(a, b); + deleted++; + } + + for (int j = 0; j < n; j++) { + int a = Random::integer<int>(0, n); + int b = Random::integer<int>(0, n); + + auto got = con.connected(a, b); + auto expected = naive.connected(a, b); + + if (got != expected) cerr << "error" << FAIL; + } + + queries += n; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 100'000; +constexpr int M = 500'000; +void performance_test() { + timer t; + t.start(); + connect con(N, M); + t.stop(); + + vector<int> insertOrder(M); + iota(all(insertOrder), 0); + shuffle(all(insertOrder), Random::rng); + vector<bool> inserted(M); + + for (int i = 0, j = 0; i < N; i++) { + int a = Random::integer<int>(0, N); + int b = a; + while (b == a) b = Random::integer<int>(0, N); + + t.start(); + con.addEdge(a, b, insertOrder[i]); + t.stop(); + inserted[i] = true; + + while (j < M && inserted[j] && Random::integer<int>(2) == 0) { + t.start(); + con.eraseEdge(j); + t.stop(); + } + } + hash_t hash = 0; + for (int i = 1; i < N; i++) { + t.start(); + hash += con.connected(i - 1, i); + 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(); + performance_test(); +} diff --git a/test/graph/connectMinLCT.h b/test/graph/connectMinLCT.h new file mode 100644 index 0000000..4d509f7 --- /dev/null +++ b/test/graph/connectMinLCT.h @@ -0,0 +1,173 @@ +constexpr ll queryDefault = 0x3FFF'FFFF; +constexpr ll updateDefault = 0; +//modifiable: +ll _modify(ll x, ll y) { + return min(x, y); +} +ll _query(ll x, ll y) { + return min(x, y); +} +ll _update(ll delta, int /*length*/) { + return delta; +} + +//generic: +ll joinValueDelta(ll value, ll delta) { + if (delta == updateDefault) return value; + return _modify(value, delta); +} + +ll joinDeltas(ll delta1, ll delta2) { + if (delta1 == updateDefault) return delta2; + if (delta2 == updateDefault) return delta1; + return _modify(delta1, delta2); +} + +struct LCT { + struct Node { + ll nodeValue, subTreeValue, delta; + bool revert; + int id, size; + Node *left, *right, *parent; + + Node(int id = 0, int val = queryDefault) : + nodeValue(val), subTreeValue(val), delta(updateDefault), + revert(false), id(id), size(1), + left(nullptr), right(nullptr), parent(nullptr) {} + + bool isRoot() { + return !parent || (parent->left != this && + parent->right != this); + } + + void push() { + if (revert) { + revert = false; + swap(left, right); + if (left) left->revert ^= 1; + if (right) right->revert ^= 1; + } + nodeValue = joinValueDelta(nodeValue, delta); + subTreeValue = joinValueDelta(subTreeValue, + _update(delta, size)); + if (left) left->delta = joinDeltas(left->delta, delta); + if (right) right->delta = joinDeltas(right->delta, delta); + delta = updateDefault; + } + + ll getSubtreeValue() { + return joinValueDelta(subTreeValue, _update(delta, size)); + } + + void update() { + subTreeValue = joinValueDelta(nodeValue, delta); + size = 1; + if (left) { + subTreeValue = _query(subTreeValue, + left->getSubtreeValue()); + size += left->size; + } + if (right) { + subTreeValue = _query(subTreeValue, + right->getSubtreeValue()); + size += right->size; + }} + }; + + vector<Node> nodes; + + LCT(int n) : nodes(n) { + for (int i = 0; i < n; i++) nodes[i].id = i; + } + + void connect(Node* ch, Node* p, int isLeftChild) { + if (ch) ch->parent = p; + if (isLeftChild >= 0) { + if (isLeftChild) p->left = ch; + else p->right = ch; + }} + + void rotate(Node* x) { + Node* p = x->parent; + Node* g = p->parent; + bool isRootP = p->isRoot(); + bool leftChildX = (x == p->left); + + connect(leftChildX ? x->right : x->left, p, leftChildX); + connect(p, x, !leftChildX); + connect(x, g, isRootP ? -1 : p == g->left); + p->update(); + } + + void splay(Node* x) { + while (!x->isRoot()) { + Node* p = x->parent; + Node* g = p->parent; + if (!p->isRoot()) g->push(); + p->push(); + x->push(); + if (!p->isRoot()) rotate((x == p->left) == + (p == g->left) ? p : x); + rotate(x); + } + x->push(); + x->update(); + } + + Node* expose(Node* x) { + Node* last = nullptr; + for (Node* y = x; y; y = y->parent) { + splay(y); + y->left = last; + last = y; + } + splay(x); + return last; + } + + void makeRoot(Node* x) { + expose(x); + x->revert ^= 1; + } + + bool connected(Node* x, Node* y) { + if (x == y) return true; + expose(x); + expose(y); + return x->parent; + } + + void link(Node* x, Node* y) { + assert(!connected(x, y)); // not yet connected! + makeRoot(x); + x->parent = y; + } + + void cut(Node* x, Node* y) { + makeRoot(x); + expose(y); + //must be a tree edge! + assert(!(y->right != x || x->left != nullptr)); + y->right->parent = nullptr; + y->right = nullptr; + } + + Node* lca(Node* x, Node* y) { + assert(connected(x, y)); + expose(x); + return expose(y); + } + + ll query(Node* from, Node* to) { + makeRoot(from); + expose(to); + if (to) return to->getSubtreeValue(); + return queryDefault; + } + + void modify(Node* from, Node* to, ll delta) { + makeRoot(from); + expose(to); + to->delta = joinDeltas(to->delta, delta); + } +}; diff --git a/test/graph/dinic.cpp b/test/graph/dinic.cpp new file mode 100644 index 0000000..5af7c6f --- /dev/null +++ b/test/graph/dinic.cpp @@ -0,0 +1,62 @@ +#include "../util.h" +constexpr ll INF = LL::INF; +namespace dinic { +#include <graph/dinic.cpp> +} + +namespace pushRelabel { +#include <graph/pushRelabel.cpp> +} + +void stress_test() { + ll queries = 0; + for (int tries = 0; tries < 20'000; tries++) { + int n = Random::integer<int>(2, 30); + int m = Random::integer<int>(n-1, max<int>(n, min<int>(500, n*(n-1) / 2 + 1))); + + dinic::adj.assign(n, {}); + pushRelabel::adj.assign(n, {}); + + Graph<NoData, true> g(n); + g.erdosRenyi(m); + g.forEdges([](int a, int b){ + ll w = Random::integer<ll>(1, 1'000'000'000'000ll); + dinic::addEdge(a, b, w); + pushRelabel::addEdge(a, b, w); + }); + + ll got = dinic::maxFlow(0, n - 1); + ll expected = pushRelabel::maxFlow(0, n - 1); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries += n; + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 50000; +constexpr int M = 200000; +void performance_test() { + using namespace dinic; + timer t; + Graph<NoData> g(N); + g.erdosRenyi(M); + adj.assign(N, {}); + g.forEdges([](int a, int b){ + ll w1 = Random::integer<ll>(1, 1'000'000'000'000ll); + ll w2 = Random::integer<ll>(1, 1'000'000'000'000ll); + addEdge(a, b, w1); + addEdge(b, a, w2); + }); + + t.start(); + hash_t hash = maxFlow(0, N - 1); + 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/graph/hld.cpp b/test/graph/hld.cpp new file mode 100644 index 0000000..bcd9c8c --- /dev/null +++ b/test/graph/hld.cpp @@ -0,0 +1,83 @@ +#include "../util.h" +#include <graph/hld.cpp> + +struct Seg { // very real segment tree + vector<int> a; + + Seg(int n) : a(n) {} + + void inc(int l, int r) { + for (int i=l; i<r; i++) a[i]++; + } +}; + +void stress_test() { + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer<int>(1, 50); + Graph<NoData> g(n); + g.tree(); + + adj.assign(n, {}); + g.forEdges([&](int a, int b){ + adj[a].push_back(b); + adj[b].push_back(a); + }); + + init(Random::integer(0, n)); + + vector<int> a(n); + auto dfs = [&](auto& self, int u, int p, int t) { + if (u == t) { + a[u]++; + return true; + } + for (int v : adj[u]) if (v != p) { + if (self(self, v, u, t)) { + a[u]++; + return true; + } + } + return false; + }; + + Seg seg(n); + + int Q = Random::integer(1, 50); + for (int q=0; q<Q; q++) { + int u = Random::integer(0, n), v = Random::integer(0, n); + for_intervals(u, v, [&](int l, int r) { seg.inc(l, r); }); + dfs(dfs, u, -1, v); + } + for (int i=0; i<n; i++) { + if (seg.a[in[i]] != a[i]) cerr << "WA: expected " << a[i] << " got " << seg.a[in[i]] << FAIL; + } + } + cerr << "tested random tests: " << 100'000 << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + Graph<NoData> g(N); + g.tree(); + adj.assign(N, {}); + g.forEdges([&](int a, int b){ + adj[a].push_back(b); + adj[b].push_back(a); + }); + vector<pair<int, int>> qu(N); + for (auto& [x, y] : qu) x = Random::integer(0, N), y = Random::integer(0, N); + + ll hash = 0; + t.start(); + init(0); + for (auto [x, y] : qu) for_intervals(x, y, [&](int l, int r){ hash += r-l; }); + 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(); + performance_test(); +} diff --git a/test/graph/reroot.cpp b/test/graph/reroot.cpp new file mode 100644 index 0000000..d5043b4 --- /dev/null +++ b/test/graph/reroot.cpp @@ -0,0 +1,59 @@ +#include "../util.h" +#include <graph/reroot.cpp> + +void stress_test() { + for (int tries = 0; tries < 50'000; tries++) { + int n = Random::integer<int>(1, 50); + Graph<NoData> g(n); + g.tree(); + + adj.assign(n, {}); + g.forEdges([&](int a, int b){ + adj[a].emplace_back(b, Random::integer(0, 10)); + adj[b].emplace_back(a, Random::integer(0, 10)); + }); + + Reroot re; + auto ans = re.solve(); + + auto dfs = [&](auto& self, int u, int p) -> ll { + ll val = 0; + for (auto [v, w] : adj[u]) if (v != p) { + val ^= ((v ^ u) + self(self, v, u)) * w % MOD; + } + return u ^ val; + }; + for (int i=0; i<n; i++) { + if (ans[i] != dfs(dfs, i, -1)) { + cerr << "WA expected " << dfs(dfs, i, -1) << " got " << ans[i] << FAIL; + } + } + } + cerr << "tested random 50'000 tests" << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + Graph<NoData> g(N); + g.tree(); + adj.assign(N, {}); + g.forEdges([&](int a, int b){ + adj[a].emplace_back(b, Random::integer(0, (int)1e9)); + adj[b].emplace_back(a, Random::integer(0, (int)1e9)); + }); + + ll hash = 0; + t.start(); + Reroot re; + auto ans = re.solve(); + hash = accumulate(all(ans), 0LL); + 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(); + performance_test(); +} diff --git a/test/graph/reroot.cpp.awk b/test/graph/reroot.cpp.awk new file mode 100644 index 0000000..37ce8c3 --- /dev/null +++ b/test/graph/reroot.cpp.awk @@ -0,0 +1,7 @@ +BEGIN { print "constexpr ll MOD = 1e9 + 7;" } +{ + sub("W w, T x) {\\}", "W w, T x) { return ((v ^ c) + x) * w % MOD; }") + sub("T x, T y) {\\}", "T x, T y) { return x ^ y; }") + sub("int v, T x) {\\}", "int v, T x) { return v ^ x; }") +} +{ print } diff --git a/test/graph/scc.cpp b/test/graph/scc.cpp index 123050f..9ab7051 100644 --- a/test/graph/scc.cpp +++ b/test/graph/scc.cpp @@ -16,18 +16,6 @@ void stress_test() { }); scc(); - vector<bool> tmp(n); - for (int i = 0; i < sz(sccs); i++) { - for (int x : sccs[i]) { - if (tmp[x]) cerr << "error: duclicate" << FAIL; - if (idx[x] != i) cerr << "error: inconsistent" << FAIL; - tmp[x] = true; - } - } - for (int i = 0; i < n; i++) { - if (!tmp[i]) cerr << "error: missing" << FAIL; - } - init(n); vector<ll> seen(n); int tmpCounter = 0; diff --git a/test/graph/virtualTree.cpp b/test/graph/virtualTree.cpp new file mode 100644 index 0000000..d256760 --- /dev/null +++ b/test/graph/virtualTree.cpp @@ -0,0 +1,95 @@ +#include "../util.h" +int lca(int u, int v); +#include <graph/virtualTree.cpp> + +vector<int> d, par; +void dfs(int u, vector<vector<int>>& adj, int& counter) { + in[u] = counter++; + for (int v : adj[u]) if (v != par[u]) { + d[v] = d[u]+1; + par[v] = u; + dfs(v, adj, counter); + } + out[u] = counter; +} + +int lca(int u, int v) { + if (d[u] < d[v]) swap(u, v); + while (d[u] > d[v]) u = par[u]; + while (u != v) u = par[u], v = par[v]; + return u; +} + +void init(vector<vector<int>>& adj) { + int n = (int)sz(adj); + d.assign(n, 0); + in = par = out = d; + int counter = 0; + dfs(0, adj, counter); +} + +void stress_test() { + for (int tries = 0; tries < 50'000; tries++) { + int n = Random::integer<int>(1, 50); + Graph<NoData> g(n); + g.tree(); + + vector<vector<int>> adj(n); + g.forEdges([&](int a, int b){ + adj[a].push_back(b); + adj[b].push_back(a); + }); + + init(adj); + vector<int> ind = Random::distinct(Random::integer(1, n+1), 0, n); + auto [idk, tree] = virtualTree(ind); + vector<pair<int, int>> edges; + for (int i=0; i<sz(idk); i++) for (int v : tree[i]) { + edges.emplace_back(idk[i], idk[v]); + } + + vector<pair<int, int>> edges2; + vector<bool> used(n); + for (int u : ind) for (int v : ind) used[lca(u, v)] = true; + auto dfs = [&](auto& self, int u, int p, int last) -> void { + if (used[u]) { + if (last != -1) edges2.emplace_back(last, u); + last = u; + } + for (int v : adj[u]) if (v != p) self(self, v, u, last); + }; + dfs(dfs, 0, -1, -1); + + sort(all(edges)), sort(all(edges2)); + if (edges != edges2) cerr << "WA edge list does not match" << FAIL; + } + cerr << "tested random 50'000 tests" << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + Graph<NoData> g(N); + g.tree(); + vector<vector<int>> adj(N); + g.forEdges([&](int a, int b){ + adj[a].push_back(b); + adj[b].push_back(a); + }); + + init(adj); + vector<int> ind = Random::distinct(N/2, 0, N); + + ll hash = 0; + t.start(); + auto [idk, tree] = virtualTree(ind); + hash = accumulate(all(idk), 0LL); + 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(); + performance_test(); +} diff --git a/test/graph/virtualTree.cpp.awk b/test/graph/virtualTree.cpp.awk new file mode 100644 index 0000000..fe4bc62 --- /dev/null +++ b/test/graph/virtualTree.cpp.awk @@ -0,0 +1,7 @@ +/\/\/ v/ { + print "return {ind, tree};" +} +{ + sub("void", "pair<vector<int>, vector<vector<int>>>") +} +{ print } diff --git a/test/math/divSum.cpp b/test/math/divSum.cpp new file mode 100644 index 0000000..1f82387 --- /dev/null +++ b/test/math/divSum.cpp @@ -0,0 +1,48 @@ +#include "../util.h" +#include <math/divSum.cpp> + +ll naive(ll n, ll m, ll a, ll b){ + ll ans = 0; + for(ll i = 0; i < n; i++){ + ans += (a*i+b)/m; + } + return ans; +} + +void stress_test() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer<int>(1, 100); + int m = Random::integer<int>(1, 100); + int a = Random::integer<int>(0, 100); + int b = Random::integer<int>(0, 100); + ll expected = naive(n, m, a, b); + ll got = divSum(n, m, a, b); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll n = Random::integer<ll>(1, 1'000'000'000); + ll m = Random::integer<ll>(1, 1'000'000'000); + ll a = Random::integer<ll>(0, 1'000'000'000); + ll b = Random::integer<ll>(0, 1'000'000'000); + t.start(); + hash += divSum(n, m, a, b); + 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/math/gauss.cpp b/test/math/gauss.cpp index 37bacce..6e4759d 100644 --- a/test/math/gauss.cpp +++ b/test/math/gauss.cpp @@ -14,7 +14,7 @@ vector<vector<double>> inverseMat(const vector<vector<double>>& m) { mat[i].resize(2*n); mat[i][n+i] = 1; } - gauss(n);//the unique cetc. checks are not usefull since we dont solve an lgs... + gauss(n); //the unique cetc. checks are not usefull since we dont solve an lgs... vector<vector<double>> res(m); for (int i = 0; i < n; i++) { res[i] = vector<double>(mat[i].begin() + n, mat[i].end()); diff --git a/test/math/inversionsMerge.cpp b/test/math/inversionsMerge.cpp index 85ab0d2..acdc555 100644 --- a/test/math/inversionsMerge.cpp +++ b/test/math/inversionsMerge.cpp @@ -16,7 +16,7 @@ void stress_test() { for (ll i = 0; i < 100'000; i++) { int n = Random::integer<int>(1, 100); vector<ll> v(n); - for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer<ll>(0, 10000);//values must be unique ): + for (ll j = 0; j < n; j++) v[j] = (j-10) * 100000 + Random::integer<ll>(0, 10000); //values must be unique ): shuffle(all(v), Random::rng); ll expected = naive(v); ll got = mergeSort(v); diff --git a/test/math/linearRecurrence.cpp b/test/math/linearRecurrence.cpp index 21a8a7c..8640980 100644 --- a/test/math/linearRecurrence.cpp +++ b/test/math/linearRecurrence.cpp @@ -1,6 +1,11 @@ #include "../util.h" +vector<ll> mul(const vector<ll>& a, const vector<ll>& b); #include <math/linearRecurrence.cpp> +vector<ll> mul(const vector<ll>& a, const vector<ll>& b) { + return mulSlow(a, b); +} + struct RandomRecurence { vector<ll> f, c, cache; RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {} diff --git a/test/math/linearRecurrence.cpp.awk b/test/math/linearRecurrence.cpp.awk new file mode 100644 index 0000000..902fd4b --- /dev/null +++ b/test/math/linearRecurrence.cpp.awk @@ -0,0 +1,4 @@ +/vector<ll> mul/ { + sub(/mul/, "mulSlow") +} +{ print } diff --git a/test/math/linearRecurrenceNTT.cpp b/test/math/linearRecurrenceNTT.cpp new file mode 100644 index 0000000..e03c27e --- /dev/null +++ b/test/math/linearRecurrenceNTT.cpp @@ -0,0 +1,60 @@ +#include "../util.h" +#include <math/modPowIterativ.cpp> +#include <math/transforms/ntt.cpp> +#include <math/transforms/multiplyNTT.cpp> +#define mod mod2 +#include <math/linearRecurrence.cpp> +#undef mod +static_assert(mod == mod2); + +struct RandomRecurence { + vector<ll> f, c, cache; + RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {} + + ll operator()(ll k){ + while (sz(cache) <= k) { + ll cur = 0; + for (ll i = 0; i < sz(c); i++) { + cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + } + cur %= mod; + cache.push_back(cur); + } + return cache[k]; + } +}; + +void stress_test() { + int queries = 0; + for (int i = 0; i < 1'000; i++) { + int n = Random::integer<int>(1, 10); + RandomRecurence f(n); + for (int j = 0; j < 100; j++) { + ll k = Random::integer<ll>(0, 1000); + + ll got = kthTerm(f.f, f.c, k); + ll expected = f(k); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 100'000; +void performance_test() { + timer t; + RandomRecurence f(N); + t.start(); + hash_t hash = kthTerm(f.f, f.c, 1e18); + t.stop(); + if (t.time > 8000) 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/math/linearRecurrenceOld.cpp b/test/math/linearRecurrenceOld.cpp new file mode 100644 index 0000000..dab2256 --- /dev/null +++ b/test/math/linearRecurrenceOld.cpp @@ -0,0 +1,54 @@ +#include "../util.h" +#include <math/linearRecurrenceOld.cpp> + +struct RandomRecurence { + vector<ll> f, c, cache; + RandomRecurence(int n) : f(Random::integers<ll>(n, 0, mod)), c(Random::integers<ll>(n, 0, mod)), cache(f) {} + + ll operator()(ll k){ + while (sz(cache) <= k) { + ll cur = 0; + for (ll i = 0; i < sz(c); i++) { + cur += (c[i] * cache[sz(cache) - i - 1]) % mod; + } + cur %= mod; + cache.push_back(cur); + } + return cache[k]; + } +}; + +void stress_test() { + int queries = 0; + for (int i = 0; i < 10'000; i++) { + int n = Random::integer<int>(1, 10); + RandomRecurence f(n); + for (int j = 0; j < 100; j++) { + ll k = Random::integer<ll>(0, 1000); + + ll got = kthTerm(f.f, f.c, k); + ll expected = f(k); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + } + cerr << "tested random queries: " << queries << endl; +} + +constexpr int N = 1'000; +void performance_test() { + timer t; + RandomRecurence f(N); + t.start(); + hash_t hash = kthTerm(f.f, f.c, 1e18); + 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/math/minMod.cpp b/test/math/minMod.cpp new file mode 100644 index 0000000..e49da11 --- /dev/null +++ b/test/math/minMod.cpp @@ -0,0 +1,92 @@ +#include "../util.h" +#include <math/shortModInv.cpp> +#include <math/minMod.cpp> + +ll naiveMinMod(ll n, ll m, ll a, ll b){ + ll ans = m; + for(ll i = 0; i < n; i++){ + ans = min(ans, (a*i+b)%m); + } + return ans; +} + +ll naiveFirstVal(ll a, ll m, ll l, ll r){ + for(ll i = 0; i < m; i++){ + ll v = a*i % m; + if(l <= v && v <= r) return v; + } + return -1; +} + +void stress_test_minMod() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int n = Random::integer<int>(1, 100); + int m = Random::integer<int>(1, 100); + int a = Random::integer<int>(0, m); + int b = Random::integer<int>(0, m); + ll expected = naiveMinMod(n, m, a, b); + ll got = minMod(n, m, a, b); + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested queries: " << queries << endl; +} + +void stress_test_firstVal() { + ll queries = 0; + for (ll i = 0; i < 10'000; i++) { + int m = Random::integer<int>(1, 100); + int a = Random::integer<int>(0, m); + int l = Random::integer<int>(0, m); + int r = Random::integer<int>(0, m); + if(l > r) swap(l, r); + ll expected = naiveFirstVal(a, m, l, r); + ll got = firstVal(a, m, l, r); + if (got != expected) cerr << a << " " << m << " " << l << " " << r << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested queries: " << queries << endl; +} + +constexpr int N = 1'000'000; +void performance_test_minMod() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll n = Random::integer<ll>(1, 1'000'000'000); + ll m = Random::integer<ll>(1, 1'000'000'000); + ll a = Random::integer<ll>(0, m); + ll b = Random::integer<ll>(0, m); + t.start(); + hash += minMod(n, m, a, b); + t.stop(); + } + if (t.time > 750) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; +} + +void performance_test_firstVal() { + timer t; + hash_t hash = 0; + for (int operations = 0; operations < N; operations++) { + ll m = Random::integer<ll>(1, 1'000'000'000); + ll a = Random::integer<ll>(1, m); + ll l = Random::integer<ll>(0, m); + ll r = Random::integer<ll>(0, m); + if(l > r) swap(l, r); + t.start(); + hash += firstVal(a, m, l, r); + 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_minMod(); + stress_test_firstVal(); + performance_test_minMod(); + performance_test_firstVal(); +} + diff --git a/test/math/polynomial.cpp b/test/math/polynomial.cpp new file mode 100644 index 0000000..f4a9486 --- /dev/null +++ b/test/math/polynomial.cpp @@ -0,0 +1,153 @@ +#include "../util.h" +#include <math/shortModInv.cpp> +constexpr ll mod = 1'394'633'899; +#include <math/polynomial.cpp> + +poly randomPoly(int deg) { + poly p; + p.data = Random::integers<ll>(deg + 1, 0, mod); + return p; +} + +ll eval(const vector<ll>& p, ll x) { + ll res = 0; + for (ll i = 0, j = 1; i < sz(p); i++, j = (j * x) % mod) { + res += j * p[i]; + res %= mod; + } + return res; +} + +void test_eval() { + int queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int deg = Random::integer<int>(1, 30); + vector<ll> tmp = Random::integers<ll>(deg + 1, 0, mod); + poly p(deg); + for (int i = 0; i <= deg; i++) p[i] = tmp[i]; + + for (int i = 0; i <= deg + 7; i++) { + ll x = Random::integer<ll>(0, mod); + + ll got = p(x); + ll expected = eval(tmp, x); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + queries += deg + 1; + } + cerr << "tested eval: " << queries << endl; +} + +void test_add() { + int queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer<int>(1, 30); + int m = Random::integer<int>(1, 30); + auto a = randomPoly(n); + auto b = randomPoly(m); + + auto c = a; + c += b; + + if (sz(c) > sz(a) && sz(c) > sz(b)) cerr << "error: wrong degree" << FAIL; + + for (int i = 0; i <= n + m + 7; i++) { + ll x = Random::integer<ll>(0, mod); + + ll got = c(x); + ll expected = (a(x) + b(x)) % mod; + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + queries += n + m; + } + cerr << "tested add: " << queries << endl; +} + +void test_mul() { + int queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer<int>(1, 30); + int m = Random::integer<int>(1, 30); + auto a = randomPoly(n); + auto b = randomPoly(m); + + auto c = a * b; + if (sz(c) > sz(a) + sz(b) - 1) cerr << "error: wrong degree" << FAIL; + + for (int i = 0; i <= n + m + 7; i++) { + ll x = Random::integer<ll>(0, mod); + + ll got = c(x); + ll expected = (a(x) * b(x)) % mod; + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + queries += n + m; + } + cerr << "tested mul: " << queries << endl; +} + +void test_shift() { + int queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer<int>(1, 30); + int m = Random::integer<int>(1, 30); + auto a = randomPoly(n); + + auto b = a << m; + if (sz(b) > sz(a)) cerr << sz(a) << " " << sz(b) << endl; + if (sz(b) > sz(a)) cerr << "error: wrong degree" << FAIL; + + for (int i = 0; i <= n + 7; i++) { + ll x = Random::integer<ll>(0, mod); + + ll got = b(x); + ll expected = a((x + m) % mod); + + if (got != expected) { + for (ll y : b.data) cerr << y << " "; + cerr << endl; + } + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + queries += n; + } + cerr << "tested shift: " << queries << endl; +} + +void test_divmod() { + int queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + int n = Random::integer<int>(1, 30); + int m = Random::integer<int>(1, 30); + auto a = randomPoly(n); + auto b = randomPoly(m); + + auto [div, rem] = a.divmod(b); + if (sz(rem) > sz(b)) cerr << "error: wrong degree (rem)" << FAIL; + if (sz(div) > 1 + max<ll>(0, sz(a) - sz(b))) cerr << "error: wrong degree (div)" << FAIL; + + for (int i = 0; i <= n + m; i++) { + ll x = Random::integer<ll>(0, mod); + ll d = multInv(b(x), mod); + + ll got = (div(x) + rem(x) * d) % mod; + ll expected = (a(x) * d) % mod; + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + } + queries += n + m; + } + cerr << "tested divmod: " << queries << endl; +} + +int main() { + test_eval(); + test_add(); + test_mul(); + test_shift(); + test_divmod(); +} + diff --git a/test/math/recover.cpp b/test/math/recover.cpp new file mode 100644 index 0000000..6f89e5a --- /dev/null +++ b/test/math/recover.cpp @@ -0,0 +1,44 @@ +#include "../util.h" +#include <math/recover.cpp> +#include <math/shortModInv.cpp> + +void stress_test() { + ll queries = 0; + timer t; + for (int i = 0; i < 500; i++) { + ll p = Random::prime<ll>(10000); + for (ll j = 0; 2*j*j < p; j++) { + for (ll b = 1; 2*b*b < p; b++) { + if (gcd(j, b) != 1) continue; + for (ll a : {-j, j}) { + ll c = a * multInv(b, p); + + t.start(); + auto [x, y] = recover(c, p); + t.stop(); + + if (a != x || b != y) cerr << "got: " << x << "/" << y << ", expected: " << a << "/" << b << FAIL; + queries++; + } + } + } + for (ll c = 0; c < p; c++) { + t.start(); + auto [x, y] = recover(c, p); + t.stop(); + + if (y < 0) continue; + if (y == 0) cerr << "error: y=0" << FAIL; + ll got = (((x * multInv(y, p)) % p) + p) % p; + if (got != c) cerr << "got: " << got << ", expected: " << c << FAIL; + queries++; + } + } + cerr << "tested random queries: " << queries << endl; + if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + cerr << "tested performance: " << t.time << "ms" << endl; +} + +int main() { + stress_test(); +} diff --git a/test/math/rho.cpp b/test/math/rho.cpp index 5e4792a..941524b 100644 --- a/test/math/rho.cpp +++ b/test/math/rho.cpp @@ -96,17 +96,25 @@ void stress_test() { cerr << "stress tested: " << t.time << "ms" << endl; } -constexpr int N = 2'000; +ll randomHard(ll lim) { + ll root2 = sqrt(lim); + ll root3 = cbrt(lim); + ll a = Random::prime<ll>(root2 / 2 - root3, root2 / 2 + root3); + ll b = Random::prime<ll>(lim / a - root3, lim / a); + return a * b; +} + +constexpr int N = 200; void performance_test() { timer t; hash_t hash = 0; for (int operations = 0; operations < N; operations++) { - ll x = Random::integer<ll>(1e18 / 2, 1e18); + ll x = randomHard(1e18); t.start(); hash += factor(x).size(); t.stop(); } - if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + if (t.time > 750) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/math/transforms/seriesOperations.cpp b/test/math/transforms/seriesOperations.cpp new file mode 100644 index 0000000..ee30e00 --- /dev/null +++ b/test/math/transforms/seriesOperations.cpp @@ -0,0 +1,145 @@ +#include "../../util.h" +#include <math/modPowIterativ.cpp> +#include <math/transforms/ntt.cpp> +#include <math/transforms/multiplyNTT.cpp> +#pragma GCC diagnostic ignored "-Wunused-variable" +#include <math/transforms/seriesOperations.cpp> + +namespace reference {//checked against yosupo + vector<ll> poly_inv(vector<ll> a, int n){ + vector<ll> q = {powMod(a[0], mod-2, mod)}; + for(int len = 1; len < n; len *= 2){ + vector<ll> a2 = a, q2 = q; + a2.resize(2*len), q2.resize(2*len); + ntt(q2); + for(int j = 0; j < 2; j++){ + ntt(a2); + for(int i = 0; i < 2*len; i++) a2[i] = a2[i] * q2[i] % mod; + ntt(a2, true); + for(int i = 0; i < len; i++) a2[i] = 0; + } + for(int i = len; i < min(n, 2*len); i++) q.push_back((mod - a2[i]) % mod); + } + return q; + } + + vector<ll> poly_deriv(vector<ll> a){ + for(int i = 0; i < sz(a)-1; i++) + a[i] = a[i+1] * (i+1) % mod; + a.pop_back(); + return a; + } + + vector<ll> poly_integr(vector<ll> a){ + if(a.empty()) return {0}; + a.push_back(a.back() * powMod(sz(a), mod-2, mod) % mod); + for(int i = sz(a)-2; i > 0; i--) + a[i] = a[i-1] * powMod(i, mod-2, mod) % mod; + a[0] = 0; + return a; + } + + vector<ll> poly_log(vector<ll> a, int n){ + a = mul(poly_deriv(a), poly_inv(a, n)); + a.resize(n-1); + a = poly_integr(a); + return a; + } + + vector<ll> poly_exp(vector<ll> a, int n){ + vector<ll> q = {1}; + for(int len = 1; len < n; len *= 2){ + vector<ll> p = poly_log(q, 2*len); + for(int i = 0; i < 2*len; i++) + p[i] = (mod - p[i] + (i < sz(a) ? a[i] : 0)) % mod; + vector<ll> q2 = q; + q2.resize(2*len); + ntt(p), ntt(q2); + for(int i = 0; i < 2*len; i++) p[i] = p[i] * q2[i] % mod; + ntt(p, true); + for(int i = len; i < min(n, 2*len); i++) q.push_back(p[i]); + } + return q; + } +} + +void test_inv() { + ll queries = 0; + for (ll i = 0; i < 50'000; i++) { + int n = Random::integer<int>(1, 100); + int m = Random::integer<int>(1, 100); + vector<ll> a = Random::integers<ll>(n, 0, mod); + + auto got = poly_inv(a, m); + auto expected = reference::poly_inv(a, m); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested inv: " << queries << endl; +} + +void test_deriv() { + ll queries = 0; + for (ll i = 0; i < 50'000; i++) { + int n = Random::integer<int>(1, 100); + vector<ll> a = Random::integers<ll>(n, 0, mod); + + auto got = poly_deriv(a); + auto expected = reference::poly_deriv(a); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested deriv: " << queries << endl; +} + +void test_integr() { + ll queries = 0; + for (ll i = 0; i < 50'000; i++) { + int n = Random::integer<int>(1, 100); + vector<ll> a = Random::integers<ll>(n, 0, mod); + + auto got = poly_deriv(a); + auto expected = reference::poly_deriv(a); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested integr: " << queries << endl; +} + +void test_log() { + ll queries = 0; + for (ll i = 0; i < 50'000; i++) { + int n = Random::integer<int>(1, 100); + int m = Random::integer<int>(1, 100); + vector<ll> a = Random::integers<ll>(n, 0, mod); + + auto got = poly_log(a, m); + auto expected = reference::poly_log(a, m); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested log: " << queries << endl; +} + +void test_exp() { + ll queries = 0; + for (ll i = 0; i < 50'000; i++) { + int n = Random::integer<int>(1, 100); + int m = Random::integer<int>(1, 100); + vector<ll> a = Random::integers<ll>(n, 0, mod); + + auto got = poly_exp(a, m); + auto expected = reference::poly_exp(a, m); + if (got != expected) cerr << "error" << FAIL; + queries += n; + } + cerr << "tested exp: " << queries << endl; +} + +int main() { + test_inv(); + test_deriv(); + test_integr(); + test_log(); + test_exp(); +} diff --git a/test/missing.ignore b/test/missing.ignore index 0f6956f..c5f97bc 100644 --- a/test/missing.ignore +++ b/test/missing.ignore @@ -1,6 +1,4 @@ -datastructures/stlRope.cpp -other/bitOps.cpp -other/pbs.cpp +datastructures/pbds.cpp other/pragmas.cpp other/stuff.cpp other/timed.cpp diff --git a/test/other/bitOps.cpp b/test/other/bitOps.cpp new file mode 100644 index 0000000..44f6297 --- /dev/null +++ b/test/other/bitOps.cpp @@ -0,0 +1,59 @@ +#include "../util.h" +#include <other/bitOps.cpp> + +void test_subsets() { + int queries = 0; + for (int i = 0; i < 1000'000; i++) { + int mask = 0; + int limBits = Random::integer<int>(1, 15); + for (int j = 0; j < limBits; j++) { + mask |= 1 << Random::integer<int>(0, 31); + } + + int expeced = 1 << __builtin_popcount(mask); + int last = -1; + int seen = 1; + subsets(mask, [&](int active){ + if (active <= 0) cerr << "error active: " << active << FAIL; + if (last >= 0 && active >= last) cerr << "error active: " << active << ", last: " << last << FAIL; + last = active; + seen++; + }); + if (expeced != seen) cerr << "got: " << seen << ", expeced: " << expeced << FAIL; + queries++; + } + cerr << "tested subsets queries: " << queries << endl; +} + +ll naive(ll x) { + vector<ll> bits; + for (ll i = 0; i < 64; i++) { + bits.push_back(x & 1); + x >>= 1; + } + reverse(all(bits)); + next_permutation(all(bits)); + reverse(all(bits)); + x = 0; + for (ll i = 0, j = 1; i < 64; i++, j <<= 1) { + if (bits[i] != 0) x |= j; + } + return x; +} + +void test_nextPerm() { + int queries = 0; + for (int i = 0; i < 1000'000; i++) { + ll x = 4;//Random::integer<ll>(1, LL::INF); + ll got = nextPerm(x); + ll expeced = naive(x); + if (got != expeced) cerr << x << ": got: " << got << ", expeced: " << expeced << FAIL; + queries++; + } + cerr << "tested nextPerm queries: " << queries << endl; +} + +int main() { + test_subsets(); + test_nextPerm(); +}
\ No newline at end of file diff --git a/test/other/bitOps.cpp.awk b/test/other/bitOps.cpp.awk new file mode 100644 index 0000000..f1abcfb --- /dev/null +++ b/test/other/bitOps.cpp.awk @@ -0,0 +1,9 @@ +/for \(int subset/ { + print "template<typename F>" + print "void subsets(int bitmask, F&& f) {" +} +/\/\/ Nächste Permutation/ { + print " {f(subset);}" + print "}" +} +{ print } diff --git a/test/other/divideAndConquer.cpp b/test/other/divideAndConquer.cpp index a6fda9d..6d1b444 100644 --- a/test/other/divideAndConquer.cpp +++ b/test/other/divideAndConquer.cpp @@ -1,5 +1,5 @@ #include "../util.h" -constexpr ll inf = LL::INF; +constexpr ll INF = LL::INF; #include <other/divideAndConquer.cpp> vector<vector<ll>> gen(int n) { @@ -43,7 +43,7 @@ vector<vector<ll>> genQuick(int n) { } /*ll naive(int n, int m) { - vector<vector<ll>> state(m+1, vector<ll>(n+1, inf)); + vector<vector<ll>> state(m+1, vector<ll>(n+1, INF)); state[0][0] = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { @@ -56,9 +56,9 @@ vector<vector<ll>> genQuick(int n) { }*/ vector<ll> naive(int n) { - vector<vector<ll>> state(n+1, vector<ll>(n+1, inf)); + vector<vector<ll>> state(n+1, vector<ll>(n+1, INF)); state[0][0] = 0; - vector<ll> res(n+1, inf); + vector<ll> res(n+1, INF); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= j; k++) { diff --git a/test/other/fastSubsetSum.cpp b/test/other/fastSubsetSum.cpp new file mode 100644 index 0000000..c61b1ea --- /dev/null +++ b/test/other/fastSubsetSum.cpp @@ -0,0 +1,49 @@ +#include "../util.h" +#include <other/fastSubsetSum.cpp> + +int subsetSum(vector<int> w, int t){ + vector<bool> dp(t+1); + dp[0] = true; + for(int x : w){ + for(int i = t; i >= x; i--){ + dp[i] = dp[i] || dp[i-x]; + } + } + int ma = 0; + for(int i = 0; i <= t; i++){ + if(dp[i]) ma = i; + } + return ma; +} + +void stress_test() { + int queries = 0; + for (int test = 0; test < 10'000; test++) { + int n = Random::integer<int>(1, 20); + int t = Random::integer<int>(1, 500); + vector<int> w = Random::integers<int>(n, 0, 50); + int got = fastSubsetSum(w, t); + int expected = subsetSum(w, t); + if(got != expected) cerr << "got: " << got << " expected: " << expected << FAIL; + queries++; + } + cerr << "tested queries: " << queries << endl; +} + +void performance_test() { + timer t; + int n = 10'000, a = 10'000; + vector<int> w = Random::integers<int>(n, 0, a); + int target = 10'000'000; + t.start(); + hash_t hash = fastSubsetSum(w, target); + 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/other/josephus2.cpp b/test/other/josephus2.cpp index d28fe0d..85a9d28 100644 --- a/test/other/josephus2.cpp +++ b/test/other/josephus2.cpp @@ -31,7 +31,7 @@ void performance_test() { hash += rotateLeft(1'000'000'000'000'000'000ll + i); } t.stop(); - if (t.time > 500) cerr << "too slow: " << t.time << FAIL; + if (t.time > 750) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/other/knuth.cpp b/test/other/knuth.cpp index d469ceb..aaf5059 100644 --- a/test/other/knuth.cpp +++ b/test/other/knuth.cpp @@ -1,5 +1,5 @@ #include "../util.h" -constexpr ll inf = LL::INF; +constexpr ll INF = LL::INF; #include <other/knuth.cpp> vector<vector<ll>> gen(int n) { @@ -43,7 +43,7 @@ vector<vector<ll>> genQuick(int n) { } /*ll naive(int n, int m, const vector<vector<ll>>& C) { - vector<vector<ll>> state(m+1, vector<ll>(n+1, inf)); + vector<vector<ll>> state(m+1, vector<ll>(n+1, INF)); state[0][0] = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { @@ -56,9 +56,9 @@ vector<vector<ll>> genQuick(int n) { }*/ vector<ll> naive(int n, const vector<vector<ll>>& C) { - vector<vector<ll>> state(n+1, vector<ll>(n+1, inf)); + vector<vector<ll>> state(n+1, vector<ll>(n+1, INF)); state[0][0] = 0; - vector<ll> res(n+1, inf); + vector<ll> res(n+1, INF); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= j; k++) { diff --git a/test/other/pbs.cpp b/test/other/pbs.cpp new file mode 100644 index 0000000..ba3b9d0 --- /dev/null +++ b/test/other/pbs.cpp @@ -0,0 +1,103 @@ +#include "../util.h" + +struct Union { + vector<int> a; + + Union(int n) : a(n, -1) {} + + int find(int i) { + return a[i] < 0 ? i : a[i] = find(a[i]); + } + + void join(int i, int j) { + i = find(i), j = find(j); + if (i == j) return; + a[j] = i; + } + + bool same(int i, int j) { + return find(i) == find(j); + } +}; + +int n; +Union un(0); +void reset() { + un = Union(n); +} + +vector<pair<int, int>> edges; +void do_step(int i) { + auto [u, v] = edges[i]; + un.join(u, v); +} + +vector<pair<int, int>> queries; +bool test(int i) { + auto [u, v] = queries[i]; + return un.same(u, v); +} + +#include <other/pbs.cpp> +void stress_test() { + for (int it = 0; it < 100'000; it++) { + n = Random::integer(2, 31); + int Q = Random::integer(2, 31); + int MAX_OPERATIONS = n-1; + + edges.clear(); + for (int i=1; i<n; i++) { + edges.emplace_back(Random::integer(0, i), i); + } + shuffle(all(edges), Random::rng); + queries.clear(); + for (int i=0; i<Q; i++) { + auto x = Random::distinct(2, n); + queries.emplace_back(x[0], x[1]); + } + vector<int> ans = pbs(Q, MAX_OPERATIONS); + + vector<int> correct(Q, -1); + Union un2(n); + for (int j=0; j<MAX_OPERATIONS; j++) { + un2.join(edges[j].first, edges[j].second); + for (int k=0; k<Q; k++) if (correct[k] == -1) { + if (un2.same(queries[k].first, queries[k].second)) { + correct[k] = j; + } + } + } + + if (ans != correct) cerr << "Failed stress test" << FAIL; + } +} + +void performance_test() { + n = 300'000; + constexpr int Q = 300'000; + int MAX_OPERATIONS = n-1; + edges.clear(); + for (int i=1; i<n; i++) { + edges.emplace_back(Random::integer(0, i), i); + } + shuffle(all(edges), Random::rng); + queries.clear(); + for (int i=0; i<Q; i++) { + auto x = Random::distinct(2, n); + queries.emplace_back(x[0], x[1]); + } + + timer t; + t.start(); + vector<int> ans = pbs(Q, MAX_OPERATIONS); + t.stop(); + ll hash = accumulate(all(ans), 0LL); + + if (t.time > 700) 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/other/pbs.cpp.awk b/test/other/pbs.cpp.awk new file mode 100644 index 0000000..3084ebd --- /dev/null +++ b/test/other/pbs.cpp.awk @@ -0,0 +1,8 @@ +BEGIN { print "vector<int> pbs(int Q, int MAX_OPERATIONS) {" } +{ + sub(/\/\* requirement already fulfilled \*\//, "test(i)") + sub(/\/\/ simulation step/, "do_step(step);") + sub(/\/\/ reset simulation/, "reset();") +} +{ print } +END { print "return high; }" } diff --git a/test/util.h b/test/util.h index ac0ea74..e123fc2 100644 --- a/test/util.h +++ b/test/util.h @@ -24,7 +24,11 @@ namespace details { } namespace Random { - mt19937_64 rng(3141592653589793238ll); + #ifdef SEED + mt19937_64 rng(SEED); + #else + mt19937_64 rng(3141592653589793238ll); + #endif template<typename T = ll> T integer(T l, T r) { return uniform_int_distribution<T>(l, r-1)(rng); @@ -182,7 +186,7 @@ namespace detail { double t = chrono::duration_cast<chrono::duration<double, milli>>(end - start) .count(); - return 50/t; + return 30/t; } double speed = benchmark(); |