summaryrefslogtreecommitdiff
path: root/test
diff options
context:
space:
mode:
Diffstat (limited to 'test')
-rw-r--r--test/datastructures/dynamicConvexHull.cpp2
-rw-r--r--test/datastructures/stlPriorityQueue.cpp6
-rw-r--r--test/datastructures/stlPriorityQueue.cpp.awk37
-rw-r--r--test/datastructures/stlRope.cpp6
-rw-r--r--test/datastructures/stlRope.cpp.awk27
-rw-r--r--test/other/bitOps.cpp59
-rw-r--r--test/other/bitOps.cpp.awk9
-rw-r--r--test/other/josephus2.cpp2
-rw-r--r--test/other/recover.cpp44
-rwxr-xr-xtest/test.sh28
10 files changed, 211 insertions, 9 deletions
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 <datastructures/stlPriorityQueue.cpp>
+
+int main() {
+ test();
+} \ No newline at end of file
diff --git a/test/datastructures/stlPriorityQueue.cpp.awk b/test/datastructures/stlPriorityQueue.cpp.awk
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<ll> pq, pq2;"
+ print "pq.push(1);"
+ print "pq.push(5);"
+ print "pq.push(7);"
+ print "pq2.push(2);"
+ print "pq2.push(4);"
+ print "pq2.push(8);"
+}
+END {
+ print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
+ print "if (pq.top() != 8) cerr << \"error, got: \" << pq.top() << \", expected: 8\" << FAIL;"
+ print "pq.pop();"
+ print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
+ print "if (pq.top() != 7) cerr << \"error, got: \" << pq.top() << \", expected: 7\" << FAIL;"
+ print "pq.pop();"
+ print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
+ print "if (pq.top() != 6) cerr << \"error, got: \" << pq.top() << \", expected: 6\" << FAIL;"
+ print "pq.pop();"
+ print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
+ print "if (pq.top() != 5) cerr << \"error, got: \" << pq.top() << \", expected: 5\" << FAIL;"
+ print "pq.pop();"
+ print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
+ print "if (pq.top() != 4) cerr << \"error, got: \" << pq.top() << \", expected: 4\" << FAIL;"
+ print "pq.pop();"
+ print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
+ print "if (pq.top() != 2) cerr << \"error, got: \" << pq.top() << \", expected: 2\" << FAIL;"
+ print "pq.pop();"
+ print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
+ print "if (pq.top() != 1) cerr << \"error, got: \" << pq.top() << \", expected: 1\" << FAIL;"
+ print "pq.pop();"
+ print "if (!pq.empty()) cerr << \"error, got: \" << pq.top() << \", expected: empty\" << FAIL;"
+ print "cerr << \"testes example\" << endl;"
+ print "}"
+}
+{ print }
diff --git a/test/datastructures/stlRope.cpp b/test/datastructures/stlRope.cpp
new file mode 100644
index 0000000..669f4d4
--- /dev/null
+++ b/test/datastructures/stlRope.cpp
@@ -0,0 +1,6 @@
+#include "../util.h"
+#include <datastructures/stlPriorityQueue.cpp>
+
+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<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/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/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/recover.cpp b/test/other/recover.cpp
new file mode 100644
index 0000000..72853e5
--- /dev/null
+++ b/test/other/recover.cpp
@@ -0,0 +1,44 @@
+#include "../util.h"
+#include <other/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/test.sh b/test/test.sh
index d34c446..3cb5c9c 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,7 @@ 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,16 +52,24 @@ 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"
elif [ -d "$arg" ]; then
dir=$(realpath --relative-to="${PWD}" "$arg")
- find . -type f -path "./${dir}/*.cpp" -print0 | sort -z | while read -d $'\0' file
+ find . -type f -path "./${dir}/*.cpp" -not -path './awk/*' -print0 | sort -z | while read -d $'\0' file
do
test_file "$file"
done
@@ -66,7 +80,7 @@ if [ "$#" -ne 0 ]; then
fi
done
else
- find . -type f -path '*.cpp' -print0 | sort -z | while read -d $'\0' file
+ find . -type f -path '*.cpp' -not -path './awk/*' -print0 | sort -z | while read -d $'\0' file
do
test_file "$file"
done
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 23:25:58 +0000