summaryrefslogtreecommitdiff
path: root/test
diff options
context:
space:
mode:
Diffstat (limited to 'test')
-rw-r--r--test/GNUmakefile36
-rw-r--r--test/datastructures/fenwickTree.cpp4
-rw-r--r--test/datastructures/fenwickTree2.cpp4
-rw-r--r--test/datastructures/lazyPropagation.cpp2
-rw-r--r--test/datastructures/monotonicConvexHull.cpp12
-rw-r--r--test/datastructures/pbds.cpp11
-rw-r--r--test/datastructures/sparseTable.cpp6
-rw-r--r--test/datastructures/sparseTableDisjoint.cpp6
-rw-r--r--test/datastructures/stlHashMap.cpp4
-rw-r--r--test/datastructures/stlPriorityQueue.cpp6
-rw-r--r--test/datastructures/stlPriorityQueue.cpp.awk37
-rw-r--r--test/datastructures/stlRope.cpp4
-rw-r--r--test/datastructures/stlRope.cpp.awk2
-rw-r--r--test/datastructures/stlTree.cpp2
-rwxr-xr-xtest/fuzz.sh14
-rw-r--r--test/math/cycleDetection.cpp1
-rw-r--r--test/math/inversions.cpp1
-rw-r--r--test/math/kthperm.cpp1
-rw-r--r--test/math/kthperm_permIndex.cpp1
-rw-r--r--test/math/linearRecurrence.cpp1
-rw-r--r--test/math/permIndex.cpp1
-rw-r--r--test/missing.ignore7
-rwxr-xr-xtest/test.sh114
-rw-r--r--test/util.h35
24 files changed, 95 insertions, 217 deletions
diff --git a/test/GNUmakefile b/test/GNUmakefile
new file mode 100644
index 0000000..5e57930
--- /dev/null
+++ b/test/GNUmakefile
@@ -0,0 +1,36 @@
+
+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)
+
+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 -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)) ./$<
+ @touch $@
+
+%.test: %.cpp
+ $(CXX) -o $@ $<
+
+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) $(addprefix awk/,$(AWK))
+
+include $(TESTS:=.d)
diff --git a/test/datastructures/fenwickTree.cpp b/test/datastructures/fenwickTree.cpp
index c1ef6bf..f2a490a 100644
--- a/test/datastructures/fenwickTree.cpp
+++ b/test/datastructures/fenwickTree.cpp
@@ -23,7 +23,7 @@ void stress_test() {
int i = Random::integer<int>(0, n);
ll got = prefix_sum(i);
ll expected = 0;
- for (int j = 0; j <= i; j++) expected += naive[j];
+ for (int j = 0; j < i; j++) expected += naive[j];
if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
}
}
@@ -42,7 +42,7 @@ void performance_test() {
int i = Random::integer<int>(0, N);
int j = Random::integer<int>(0, N);
ll x = Random::integer<ll>(-1000, 1000);
-
+
t.start();
update(i, x);
hash ^= prefix_sum(j);
diff --git a/test/datastructures/fenwickTree2.cpp b/test/datastructures/fenwickTree2.cpp
index 89d5b0f..bc0753f 100644
--- a/test/datastructures/fenwickTree2.cpp
+++ b/test/datastructures/fenwickTree2.cpp
@@ -23,7 +23,7 @@ void stress_test() {
int i = Random::integer<int>(0, n);
ll got = prefix_sum(i);
ll expected = 0;
- for (int j = 0; j <= i; j++) expected += naive[j];
+ for (int j = 0; j < i; j++) expected += naive[j];
if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL;
}
}
@@ -44,7 +44,7 @@ void performance_test() {
int j = Random::integer<int>(0, N);
int k = Random::integer<int>(0, N);
ll x = Random::integer<ll>(-1000, 1000);
-
+
t.start();
update(i, j, x);
hash ^= prefix_sum(k);
diff --git a/test/datastructures/lazyPropagation.cpp b/test/datastructures/lazyPropagation.cpp
index feb07f0..3030e1c 100644
--- a/test/datastructures/lazyPropagation.cpp
+++ b/test/datastructures/lazyPropagation.cpp
@@ -45,7 +45,7 @@ void performance_test() {
auto [l1, r1] = Random::pair<int>(0, N + 1);
auto [l2, r2] = Random::pair<int>(0, N + 1);
ll x1 = Random::integer<ll>(-1000, 1000);
-
+
t.start();
tree.update(l1, r1, x1);
hash ^= tree.query(l2, r2);
diff --git a/test/datastructures/monotonicConvexHull.cpp b/test/datastructures/monotonicConvexHull.cpp
index 0415068..3ae7c4d 100644
--- a/test/datastructures/monotonicConvexHull.cpp
+++ b/test/datastructures/monotonicConvexHull.cpp
@@ -1,7 +1,5 @@
#include "../util.h"
-struct MCH {
- #include <datastructures/monotonicConvexHull.cpp>
-};
+#include <datastructures/monotonicConvexHull.cpp>
struct Line {
ll m, c;
@@ -32,7 +30,7 @@ void stress_test(ll range) {
vector<Line> naive;
- MCH mch;
+ Envelope mch;
for (int k = 0; k < n; k++) {
ll m = ms[k];
ll c = cs[k];
@@ -74,7 +72,7 @@ void stress_test_independent(ll range) {
vector<Line> naive;
- MCH mch;
+ Envelope mch;
for (int i = 0; i < n; i++) {
ll m = ms[i];
ll c = cs[i];
@@ -106,14 +104,14 @@ void performance_test() {
sort(all(ms), greater<>{});
auto xs = Random::distinct<ll>(N, -1'000'000'000, 1'000'000'000);
sort(all(xs));
- MCH mch;
+ Envelope mch;
hash_t hash = 0;
for (int operations = 0; operations < N; operations++) {
ll c = Random::integer<ll>(-1'000'000'000, 1'000'000'000);
ll m = ms[operations];
ll x = xs[operations];
-
+
t.start();
mch.add(m, c);
hash += mch.query(x);
diff --git a/test/datastructures/pbds.cpp b/test/datastructures/pbds.cpp
deleted file mode 100644
index 9080332..0000000
--- a/test/datastructures/pbds.cpp
+++ /dev/null
@@ -1,11 +0,0 @@
-#include "../util.h"
-#include <datastructures/pbds.cpp>
-
-int main() {
- Tree<int> t1, t2;
- swap(t1, t2);
- hashSet<int> s1, s2;
- swap(s1, s2);
- hashMap<int, int> m1, m2;
- swap(m1, m2);
-} \ No newline at end of file
diff --git a/test/datastructures/sparseTable.cpp b/test/datastructures/sparseTable.cpp
index 7577694..2cfded9 100644
--- a/test/datastructures/sparseTable.cpp
+++ b/test/datastructures/sparseTable.cpp
@@ -8,7 +8,7 @@ void stress_test() {
int n = Random::integer<int>(1, 100);
vector<ll> naive = Random::integers<ll>(n, -1000, 1000);
SparseTable st;
- st.init(&naive);
+ st.init(naive);
for (int operations = 0; operations < 1000; operations++) {
queries++;
int l = Random::integer<int>(0, n+1);
@@ -31,12 +31,12 @@ void performance_test() {
vector<ll> naive = Random::integers<ll>(N, -1000, 1000);
t.start();
SparseTable st;
- st.init(&naive);
+ st.init(naive);
t.stop();
hash_t hash = 0;
for (int operations = 0; operations < N; operations++) {
auto [l, r] = Random::pair<int>(0, N+1);
-
+
t.start();
hash += st.queryIdempotent(l, r);
t.stop();
diff --git a/test/datastructures/sparseTableDisjoint.cpp b/test/datastructures/sparseTableDisjoint.cpp
index 77bb005..258f4db 100644
--- a/test/datastructures/sparseTableDisjoint.cpp
+++ b/test/datastructures/sparseTableDisjoint.cpp
@@ -7,7 +7,7 @@ void stress_test() {
int n = Random::integer<int>(1, 100);
vector<ll> naive = Random::integers<ll>(n, -1000, 1000);
DisjointST st;
- st.init(&naive);
+ st.init(naive);
for (int operations = 0; operations < 1000; operations++) {
queries++;
int l = Random::integer<int>(0, n+1);
@@ -28,12 +28,12 @@ void performance_test() {
vector<ll> naive = Random::integers<ll>(N, -1000, 1000);
t.start();
DisjointST st;
- st.init(&naive);
+ st.init(naive);
t.stop();
hash_t hash = 0;
for (int operations = 0; operations < N; operations++) {
auto [l, r] = Random::pair<int>(0, N+1);
-
+
t.start();
hash += st.query(l, r);
t.stop();
diff --git a/test/datastructures/stlHashMap.cpp b/test/datastructures/stlHashMap.cpp
deleted file mode 100644
index 77976fd..0000000
--- a/test/datastructures/stlHashMap.cpp
+++ /dev/null
@@ -1,4 +0,0 @@
-#include "../util.h"
-#include <datastructures/stlHashMap.cpp>
-
-int main() {} \ No newline at end of file
diff --git a/test/datastructures/stlPriorityQueue.cpp b/test/datastructures/stlPriorityQueue.cpp
deleted file mode 100644
index 669f4d4..0000000
--- a/test/datastructures/stlPriorityQueue.cpp
+++ /dev/null
@@ -1,6 +0,0 @@
-#include "../util.h"
-#include <datastructures/stlPriorityQueue.cpp>
-
-int main() {
- test();
-} \ No newline at end of file
diff --git a/test/datastructures/stlPriorityQueue.cpp.awk b/test/datastructures/stlPriorityQueue.cpp.awk
deleted file mode 100644
index 99d0fb9..0000000
--- a/test/datastructures/stlPriorityQueue.cpp.awk
+++ /dev/null
@@ -1,37 +0,0 @@
-/auto/ {
- print "void test() {"
- print "pQueue<ll> pq, pq2;"
- print "pq.push(1);"
- print "pq.push(5);"
- print "pq.push(7);"
- print "pq2.push(2);"
- print "pq2.push(4);"
- print "pq2.push(8);"
-}
-END {
- print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
- print "if (pq.top() != 8) cerr << \"error, got: \" << pq.top() << \", expected: 8\" << FAIL;"
- print "pq.pop();"
- print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
- print "if (pq.top() != 7) cerr << \"error, got: \" << pq.top() << \", expected: 7\" << FAIL;"
- print "pq.pop();"
- print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
- print "if (pq.top() != 6) cerr << \"error, got: \" << pq.top() << \", expected: 6\" << FAIL;"
- print "pq.pop();"
- print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
- print "if (pq.top() != 5) cerr << \"error, got: \" << pq.top() << \", expected: 5\" << FAIL;"
- print "pq.pop();"
- print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
- print "if (pq.top() != 4) cerr << \"error, got: \" << pq.top() << \", expected: 4\" << FAIL;"
- print "pq.pop();"
- print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
- print "if (pq.top() != 2) cerr << \"error, got: \" << pq.top() << \", expected: 2\" << FAIL;"
- print "pq.pop();"
- print "if (pq.empty()) cerr << \"error: empty\" << FAIL;"
- print "if (pq.top() != 1) cerr << \"error, got: \" << pq.top() << \", expected: 1\" << FAIL;"
- print "pq.pop();"
- print "if (!pq.empty()) cerr << \"error, got: \" << pq.top() << \", expected: empty\" << FAIL;"
- print "cerr << \"testes example\" << endl;"
- print "}"
-}
-{ print }
diff --git a/test/datastructures/stlRope.cpp b/test/datastructures/stlRope.cpp
index 669f4d4..7405e4e 100644
--- a/test/datastructures/stlRope.cpp
+++ b/test/datastructures/stlRope.cpp
@@ -1,6 +1,6 @@
#include "../util.h"
-#include <datastructures/stlPriorityQueue.cpp>
+#include <datastructures/stlRope.cpp>
int main() {
test();
-} \ No newline at end of file
+}
diff --git a/test/datastructures/stlRope.cpp.awk b/test/datastructures/stlRope.cpp.awk
index e19b8fd..df7c361 100644
--- a/test/datastructures/stlRope.cpp.awk
+++ b/test/datastructures/stlRope.cpp.awk
@@ -20,7 +20,7 @@
print "vector<int> got, expected = {0,1,6,2,3,4,5,7};"
}
END {
- print " got.push_back(*it)"
+ print " got.push_back(*it);"
print "if (got != expected) cerr << \"error\" << endl;"
print "}"
}
diff --git a/test/datastructures/stlTree.cpp b/test/datastructures/stlTree.cpp
deleted file mode 100644
index 7bacbee..0000000
--- a/test/datastructures/stlTree.cpp
+++ /dev/null
@@ -1,2 +0,0 @@
-#include "../util.h"
-#include <datastructures/stlTree.cpp>
diff --git a/test/fuzz.sh b/test/fuzz.sh
deleted file mode 100755
index c166506..0000000
--- a/test/fuzz.sh
+++ /dev/null
@@ -1,14 +0,0 @@
-#!/bin/bash
-set -e
-cd "$(dirname "$0")"
-
-while true
-do
- seed="0"
- while [[ $seed == 0* ]]; do
- seed=$(tr -dc '0-9' </dev/random | head -c 18)
- done
- echo "Fuzz using seed: $seed"
- echo
- ./test.sh --seed=$seed "$@"
-done
diff --git a/test/math/cycleDetection.cpp b/test/math/cycleDetection.cpp
index bf57aed..1694589 100644
--- a/test/math/cycleDetection.cpp
+++ b/test/math/cycleDetection.cpp
@@ -1,5 +1,4 @@
#include "../util.h"
-#include <datastructures/pbds.cpp>
#include <math/cycleDetection.cpp>
pair<ll, ll> naive(ll x0, function<ll(ll)> f) {
diff --git a/test/math/inversions.cpp b/test/math/inversions.cpp
index d2a54b7..bd362eb 100644
--- a/test/math/inversions.cpp
+++ b/test/math/inversions.cpp
@@ -1,5 +1,4 @@
#include "../util.h"
-#include <datastructures/pbds.cpp>
#include <math/inversions.cpp>
ll naive(const vector<ll>& v) {
diff --git a/test/math/kthperm.cpp b/test/math/kthperm.cpp
index 16691b9..8115356 100644
--- a/test/math/kthperm.cpp
+++ b/test/math/kthperm.cpp
@@ -1,5 +1,4 @@
#include "../util.h"
-#include <datastructures/pbds.cpp>
#include <math/kthperm.cpp>
void stress_test() {
diff --git a/test/math/kthperm_permIndex.cpp b/test/math/kthperm_permIndex.cpp
index d84524e..5e05c73 100644
--- a/test/math/kthperm_permIndex.cpp
+++ b/test/math/kthperm_permIndex.cpp
@@ -1,5 +1,4 @@
#include "../util.h"
-#include <datastructures/pbds.cpp>
#include <math/kthperm.cpp>
#include <math/permIndex.cpp>
diff --git a/test/math/linearRecurrence.cpp b/test/math/linearRecurrence.cpp
index f0ebe76..8640980 100644
--- a/test/math/linearRecurrence.cpp
+++ b/test/math/linearRecurrence.cpp
@@ -6,7 +6,6 @@ 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/permIndex.cpp b/test/math/permIndex.cpp
index 61d34c8..6c77d74 100644
--- a/test/math/permIndex.cpp
+++ b/test/math/permIndex.cpp
@@ -1,5 +1,4 @@
#include "../util.h"
-#include <datastructures/pbds.cpp>
#include <math/permIndex.cpp>
void stress_test() {
diff --git a/test/missing.ignore b/test/missing.ignore
new file mode 100644
index 0000000..c5f97bc
--- /dev/null
+++ b/test/missing.ignore
@@ -0,0 +1,7 @@
+datastructures/pbds.cpp
+other/pragmas.cpp
+other/stuff.cpp
+other/timed.cpp
+tests/gcc5bug.cpp
+tests/precision.cpp
+tests/whitespace.cpp
diff --git a/test/test.sh b/test/test.sh
deleted file mode 100755
index 6609f1a..0000000
--- a/test/test.sh
+++ /dev/null
@@ -1,114 +0,0 @@
-#!/bin/bash
-set -e
-cd "$(dirname "$0")"
-ulimit -s 4000000
-export MALLOC_PERTURB_="$((2#01011001))"
-shopt -s lastpipe
-
-declare -A cppstandard
-cppstandard["string/suffixArray.cpp"]="gnu++20"
-cppstandard["other/pbs.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:"
- echo "compiling..."
- std="gnu++17"
- if [[ -v cppstandard[$file] ]]; then
- std=${cppstandard[$file]}
- fi
- g++ -std=$std "$file" -I ./awk/ -I ../content/ -O2 -Wall -Wextra -Wshadow -Werror $seedmacro
- echo "running..."
- timeout --foreground 60s ./a.out
- echo ""
- rm ./a.out
-}
-
-list_missing() {
- declare -A ignore
- ignore["other/bitOps.cpp"]=1
- ignore["other/pragmas.cpp"]=1
- ignore["other/stuff.cpp"]=1
- ignore["other/timed.cpp"]=1
- ignore["tests/gcc5bug.cpp"]=1
- ignore["tests/precision.cpp"]=1
- ignore["tests/whitespace.cpp"]=1
-
- total=0
- missing=0
-
- if [[ ! -v $1 ]]; then
- echo "missing tests:"
- fi
- find ../content/ -type f -name '*.cpp' -print0 | sort -z | while read -d $'\0' file
- do
- total=$((total+1))
- file=${file#../content/}
- if [ ! -f "$file" ] && [[ ! -v ignore["$file"] ]]; then
- missing=$((missing+1))
- if [[ ! -v $1 ]]; then
- echo " $file"
- fi
- fi
- done
- if [[ -v $1 ]]; then
- covered=$((total-missing))
- coverage=$((100*covered/total))
- echo "REQUIRED=$(( total < 4 ? 0 : total - 4 ))"
- echo "TOTAL=$total"
- echo "COVERED=$covered"
- echo "MISSING=$missing"
- fi
-}
-
-coverage() {
- list_missing 1
-}
-
-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 == "--awk" ]]; then
- echo "processed all awk files"
- elif [[ $arg == "--missing" ]]; then
- list_missing
- elif [[ $arg == "--coverage" ]]; then
- coverage
- 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" -not -path './awk/*' -print0 | sort -z | while read -d $'\0' file
- do
- test_file "$file"
- done
- elif [ -f "$arg" ]; then
- test_file "$arg"
- else
- echo "did not recognize: $arg"
- fi
- done
-else
- find . -type f -path '*.cpp' -not -path './awk/*' -print0 | sort -z | while read -d $'\0' file
- do
- test_file "$file"
- done
- list_missing
-fi
-
diff --git a/test/util.h b/test/util.h
index 6f23b82..e123fc2 100644
--- a/test/util.h
+++ b/test/util.h
@@ -168,6 +168,30 @@ namespace Random {
exit(1);
}
+namespace detail {
+ double benchmark() {
+ mt19937 rng(734820734);
+ vector<unsigned> a(10000000);
+ for (unsigned &x: a) x = rng();
+ chrono::steady_clock::time_point start = chrono::steady_clock::now();
+ vector<unsigned> dp(ssize(a)+1, numeric_limits<unsigned>::max());
+ int res = 0;
+ for (unsigned x: a) {
+ auto it = ranges::upper_bound(dp, x);
+ res = max(res, (int)(it - begin(dp)));
+ *it = x;
+ }
+ chrono::steady_clock::time_point end = chrono::steady_clock::now();
+ assert(res == 6301);
+ double t =
+ chrono::duration_cast<chrono::duration<double, milli>>(end - start)
+ .count();
+ return 30/t;
+ }
+
+ double speed = benchmark();
+}
+
struct timer {
bool running = false;
double time = 0;
@@ -183,7 +207,7 @@ struct timer {
auto end = chrono::steady_clock::now();
if (!running) cerr << "timer not running!" << FAIL;
running = false;
- time += chrono::duration_cast<chrono::duration<double, milli>>(end - begin).count();
+ time += chrono::duration_cast<chrono::duration<double, milli>>(end - begin).count() * detail::speed;
}
void reset() {
@@ -208,7 +232,7 @@ namespace c20 {
return {{a[I]...}};
}
}
-
+
template<class T, std::size_t N>
constexpr std::array<std::remove_cv_t<T>, N> to_array(T (&a)[N]) {
return c20::detail::to_array_impl(a, std::make_index_sequence<N>{});
@@ -413,3 +437,10 @@ ld float_error(ld given, ld expected) {
}
return numeric_limits<ld>::infinity();
}
+
+#include <ext/pb_ds/assoc_container.hpp>
+template<typename T>
+using Tree = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>,
+ __gnu_pbds::rb_tree_tag,
+ __gnu_pbds::tree_order_statistics_node_update>;
+
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 14:15:08 +0000