From bbec09408867e82fb9dd9b242e6d99014f9534b6 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 5 Aug 2024 20:10:57 +0200 Subject: more tests --- test/datastructures/dynamicConvexHull.cpp | 72 +++++++++++++++++++++++++++++++ 1 file changed, 72 insertions(+) create mode 100644 test/datastructures/dynamicConvexHull.cpp (limited to 'test/datastructures/dynamicConvexHull.cpp') diff --git a/test/datastructures/dynamicConvexHull.cpp b/test/datastructures/dynamicConvexHull.cpp new file mode 100644 index 0000000..e0e56ef --- /dev/null +++ b/test/datastructures/dynamicConvexHull.cpp @@ -0,0 +1,72 @@ +#include "../util.h" +namespace dch { + constexpr ll INF = LL::INF; + #include +} + +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(1, 100); + + vector naive; + + dch::HullDynamic hd; + for (int i = 0; i < n; i++) { + ll m = Random::integer(-range, range); + ll c = Random::integer(-range, range); + hd.add(m, c); + naive.emplace_back(m, c); + + for (int j = 0; j < 100; j++) { + ll x = Random::integer(-range, range); + + ll got = hd.query(x); + ll expected = naive[0](x); + for (auto l : naive) expected = max(expected, l(x)); + + if (got != expected) { + for (auto l : naive) cerr << l.m << "*x+" << l.c << endl; + cerr << x << ": " << got << " " << expected << endl; + } + + 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(-1'000'000'000, 1'000'000'000); + ll c = Random::integer(-1'000'000'000, 1'000'000'000); + ll x = Random::integer(-1'000'000'000, 1'000'000'000); + + t.start(); + hd.add(m, c); + hash += hd.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); + performance_test(); +} -- cgit v1.2.3 From d88debc398f18d4e3d1c53d221dffe3981f35e41 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Tue, 6 Aug 2024 16:14:04 +0200 Subject: add another test --- test/datastructures/dynamicConvexHull.cpp | 5 ---- test/datastructures/dynamicConvexHull.lichao.cpp | 38 ++++++++++++++++++++++++ 2 files changed, 38 insertions(+), 5 deletions(-) create mode 100644 test/datastructures/dynamicConvexHull.lichao.cpp (limited to 'test/datastructures/dynamicConvexHull.cpp') diff --git a/test/datastructures/dynamicConvexHull.cpp b/test/datastructures/dynamicConvexHull.cpp index e0e56ef..f163397 100644 --- a/test/datastructures/dynamicConvexHull.cpp +++ b/test/datastructures/dynamicConvexHull.cpp @@ -31,11 +31,6 @@ void stress_test(ll range) { ll expected = naive[0](x); for (auto l : naive) expected = max(expected, l(x)); - if (got != expected) { - for (auto l : naive) cerr << l.m << "*x+" << l.c << endl; - cerr << x << ": " << got << " " << expected << endl; - } - if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; queries++; } diff --git a/test/datastructures/dynamicConvexHull.lichao.cpp b/test/datastructures/dynamicConvexHull.lichao.cpp new file mode 100644 index 0000000..6ab55f0 --- /dev/null +++ b/test/datastructures/dynamicConvexHull.lichao.cpp @@ -0,0 +1,38 @@ +#include "../util.h" +constexpr ll INF = LL::INF; +constexpr ll inf = LL::INF; +#include +#include + +void stress_test(ll range) { + ll queries = 0; + for (int tries = 0; tries < 1000; tries++) { + int n = Random::integer(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(-range, range); + ll c = Random::integer(-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); +} -- cgit v1.2.3 From 65e5812f5b88989ea3ce4ac232f882004c60cc73 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Thu, 5 Sep 2024 14:20:50 +0200 Subject: more tests --- .gitignore | 2 ++ test/datastructures/dynamicConvexHull.cpp | 2 +- test/datastructures/stlPriorityQueue.cpp | 6 +++++ test/datastructures/stlPriorityQueue.cpp.awk | 37 ++++++++++++++++++++++++++++ test/datastructures/stlRope.cpp | 6 +++++ test/datastructures/stlRope.cpp.awk | 27 ++++++++++++++++++++ test/test.sh | 23 ++++++++++++++--- 7 files changed, 98 insertions(+), 5 deletions(-) create mode 100644 test/datastructures/stlPriorityQueue.cpp create mode 100644 test/datastructures/stlPriorityQueue.cpp.awk create mode 100644 test/datastructures/stlRope.cpp create mode 100644 test/datastructures/stlRope.cpp.awk (limited to 'test/datastructures/dynamicConvexHull.cpp') diff --git a/.gitignore b/.gitignore index 632f1b8..4c03241 100644 --- a/.gitignore +++ b/.gitignore @@ -225,3 +225,5 @@ TSWLatexianTemp* build/* # dont ignore build tcr !tcr.pdf +# ignore build test awk files +test/awk/* diff --git a/test/datastructures/dynamicConvexHull.cpp b/test/datastructures/dynamicConvexHull.cpp index f163397..e0345af 100644 --- a/test/datastructures/dynamicConvexHull.cpp +++ b/test/datastructures/dynamicConvexHull.cpp @@ -55,7 +55,7 @@ void performance_test() { hash += hd.query(x); t.stop(); } - if (t.time > 100) cerr << "too slow: " << t.time << FAIL; + if (t.time > 200) cerr << "too slow: " << t.time << FAIL; cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl; } diff --git a/test/datastructures/stlPriorityQueue.cpp b/test/datastructures/stlPriorityQueue.cpp new file mode 100644 index 0000000..669f4d4 --- /dev/null +++ b/test/datastructures/stlPriorityQueue.cpp @@ -0,0 +1,6 @@ +#include "../util.h" +#include + +int main() { + test(); +} \ No newline at end of file diff --git a/test/datastructures/stlPriorityQueue.cpp.awk b/test/datastructures/stlPriorityQueue.cpp.awk new file mode 100644 index 0000000..99d0fb9 --- /dev/null +++ b/test/datastructures/stlPriorityQueue.cpp.awk @@ -0,0 +1,37 @@ +/auto/ { + print "void test() {" + print "pQueue 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 new file mode 100644 index 0000000..669f4d4 --- /dev/null +++ b/test/datastructures/stlRope.cpp @@ -0,0 +1,6 @@ +#include "../util.h" +#include + +int main() { + test(); +} \ No newline at end of file diff --git a/test/datastructures/stlRope.cpp.awk b/test/datastructures/stlRope.cpp.awk new file mode 100644 index 0000000..e19b8fd --- /dev/null +++ b/test/datastructures/stlRope.cpp.awk @@ -0,0 +1,27 @@ +/rope 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 sub/ { + print "v.push_back(6);" + print "v.push_back(7);" +} +/for\(auto it/ { + print "vector 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/test.sh b/test/test.sh index d34c446..d0ff995 100755 --- a/test/test.sh +++ b/test/test.sh @@ -8,6 +8,15 @@ declare -A cppstandard cppstandard["string/suffixArray.cpp"]="gnu++20" seedmacro="" +process_awk() { + awk_file=$(realpath --relative-to="${PWD}" "${1}") + cpp_file=${awk_file%.awk} + folder=$(dirname $awk_file) + #echo "$awk_file" + mkdir -p "./awk/$folder" + awk -f "$awk_file" < "../content/$cpp_file" > "./awk/$cpp_file" +} + test_file() { file=$(realpath --relative-to="${PWD}" "${1}") echo "$file:" @@ -16,7 +25,7 @@ test_file() { if [[ -v cppstandard[$file] ]]; then std=${cppstandard[$file]} fi - g++ -std=$std "$file" -I ../content/ -O2 -Wall -Wextra -Wshadow -Werror $seedmacro + g++ -std=$std "$file" -I ./awk/ -I ../content/ -O2 -Wall -Wextra -Wshadow -Werror $seedmacro echo "running..." timeout --foreground 60s ./a.out echo "" @@ -25,10 +34,8 @@ test_file() { list_missing() { declare -A ignore - ignore["datastructures/stlPriorityQueue.cpp"]=1 ignore["datastructures/stlRope.cpp"]=1 ignore["other/bitOps.cpp"]=1 - ignore["other/pbs.cpp"]=1 ignore["other/pragmas.cpp"]=1 ignore["other/stuff.cpp"]=1 ignore["other/timed.cpp"]=1 @@ -46,10 +53,18 @@ list_missing() { done } +rm -rf ./awk/ +find . -type f -path '*.awk' -print0 | sort -z | while read -d $'\0' file +do + process_awk "$file" +done + if [ "$#" -ne 0 ]; then for arg in "$@" do - if [[ $arg == "--missing" ]]; then + if [[ $arg == "--awk" ]]; then + echo "processed all awk files" + elif [[ $arg == "--missing" ]]; then list_missing elif [[ $arg == --seed=* ]]; then seedmacro="-DSEED=${arg:7}ll" -- cgit v1.2.3