summaryrefslogtreecommitdiff
path: root/test
diff options
context:
space:
mode:
Diffstat (limited to 'test')
-rw-r--r--test/GNUmakefile30
-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/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/stlTree.cpp2
-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.cpp (renamed from test/math/linearRecurence.cpp)2
-rw-r--r--test/math/permIndex.cpp1
-rw-r--r--test/missing.ignore9
-rwxr-xr-xtest/test.sh70
-rw-r--r--test/util.h35
18 files changed, 84 insertions, 106 deletions
diff --git a/test/GNUmakefile b/test/GNUmakefile
new file mode 100644
index 0000000..10e3b34
--- /dev/null
+++ b/test/GNUmakefile
@@ -0,0 +1,30 @@
+
+TESTS = $(basename $(shell find . -type f -name '*.cpp'))
+CXX = g++ -std=gnu++20 -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 -23 missing.tmp -
+ @rm missing.tmp
+
+clean:
+ rm -f $(TESTS:=.test) $(TESTS:=.ok) $(TESTS:=.d)
+
+%.ok: %.test
+ timeout --foreground --verbose 60 prlimit -s$$((1<<32)) ./$<
+ @touch $@
+
+%.test: %.cpp
+ $(CXX) -o $@ $<
+
+%.d: %.cpp
+ $(CXX) -M -MT '$*.test $*.d' -MF $@ $<
+
+.PHONY: test clean
+.SECONDARY: $(TESTS:=.test)
+
+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 aa99576..d332dc8 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 7002061..7b0e448 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/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/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/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/linearRecurence.cpp b/test/math/linearRecurrence.cpp
index a5290e5..21a8a7c 100644
--- a/test/math/linearRecurence.cpp
+++ b/test/math/linearRecurrence.cpp
@@ -1,5 +1,5 @@
#include "../util.h"
-#include <math/linearRecurence.cpp>
+#include <math/linearRecurrence.cpp>
struct RandomRecurence {
vector<ll> f, c, cache;
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..0f6956f
--- /dev/null
+++ b/test/missing.ignore
@@ -0,0 +1,9 @@
+datastructures/stlRope.cpp
+other/bitOps.cpp
+other/pbs.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 0ca230b..0000000
--- a/test/test.sh
+++ /dev/null
@@ -1,70 +0,0 @@
-#!/bin/bash
-set -e
-cd "$(dirname "$0")"
-ulimit -s 4000000
-export MALLOC_PERTURB_="$((2#01011001))"
-
-declare -A cppstandard
-cppstandard["string/suffixArray.cpp"]="gnu++20"
-
-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 ../content/ -O2 -Wall -Wextra -Wshadow -Werror
- echo "running..."
- timeout --foreground 60s ./a.out
- echo ""
- rm ./a.out
-}
-
-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
- ignore["tests/gcc5bug.cpp"]=1
- ignore["tests/precision.cpp"]=1
- ignore["tests/whitespace.cpp"]=1
-
- echo "missing tests:"
- find ../content/ -type f -name '*.cpp' -print0 | sort -z | while read -d $'\0' file
- do
- file=${file#../content/}
- if [ ! -f "$file" ] && [[ ! -v ignore["$file"] ]]; then
- echo " $file"
- fi
- done
-}
-
-if [ "$#" -ne 0 ]; then
- for arg in "$@"
- do
- if [[ "$arg" == "--missing" ]]; then
- list_missing
- elif [ -d "$arg" ]; then
- dir=$(realpath --relative-to="${PWD}" "$arg")
- find . -type f -path "./${dir}/*.cpp" -print0 | sort -z | while read -d $'\0' file
- do
- test_file "$file"
- done
- elif [ -f "$arg" ]; then
- test_file "$arg"
- fi
- done
-else
- find . -type f -path '*.cpp' -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 bfa35d8..ac0ea74 100644
--- a/test/util.h
+++ b/test/util.h
@@ -164,6 +164,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 50/t;
+ }
+
+ double speed = benchmark();
+}
+
struct timer {
bool running = false;
double time = 0;
@@ -179,7 +203,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() {
@@ -204,7 +228,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>{});
@@ -409,3 +433,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:13:53 +0000