diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | Makefile | 56 | ||||
| -rw-r--r-- | TestMakefile | 54 | ||||
| -rw-r--r-- | datastructures/segmentTree.cpp | 7 | ||||
| -rw-r--r-- | datastructures/test/segmentTree.awk | 74 | ||||
| -rw-r--r-- | datastructures/test/segmentTree.cpp | 80 | ||||
| -rw-r--r-- | datastructures/test/segmentTree2.cpp | 26 | ||||
| -rw-r--r-- | test.h | 2 |
8 files changed, 213 insertions, 87 deletions
@@ -225,3 +225,4 @@ TSWLatexianTemp* *.test *.ok *.tmp.cpp +*.d @@ -1,15 +1,3 @@ -TESTS = \ - datastructures/test/segmentTree.test \ - datastructures/test/segmentTree2.test \ - datastructures/test/fenwickTree.test \ - datastructures/test/fenwickTree2.test \ - datastructures/test/monotonicConvexHull.test \ - datastructures/test/persistent.test \ - datastructures/test/sparseTable.test \ - datastructures/test/sparseTableDisjoint.test \ - graph/test/binary_lifting.test \ - graph/test/LCA_sparse.test \ - math/test/binomial0.test LATEXMK = latexmk -interaction=nonstopmode @@ -23,7 +11,8 @@ tcr-opt.pdf: FORCE all: pdf test -test: $(TESTS:.test=.ok) +test: + +gmake -f TestMakefile clean: cleanpdf cleantest @@ -33,46 +22,7 @@ cleanpdf: rm -f *.thm cleantest: - rm -f $(TESTS) $(TESTS:.test=.ok) \ - datastructures/test/segmentTree.tmp.cpp \ - datastructures/test/segmentTree2.tmp.cpp - -%.ok: %.test - timeout -v 1 ./$< - @touch $@ -%.test: %.cpp test.h - g++ -include test.h -std=gnu++20 -Wall -Wextra -Wpedantic -Werror \ - -fsanitize=address,undefined -g -o $@ $< - -datastructures/test/segmentTree.test: datastructures/test/segmentTree.cpp \ - datastructures/test/segmentTree.tmp.cpp -datastructures/test/segmentTree.tmp.cpp: datastructures/segmentTree.cpp - { sed -e '/OR/,$$d' $< ; echo '};' ; } > $@ -datastructures/test/segmentTree2.test: datastructures/test/segmentTree2.cpp \ - datastructures/test/segmentTree2.tmp.cpp -datastructures/test/segmentTree2.tmp.cpp: datastructures/segmentTree.cpp - sed -e '/void update/,/OR/d' \ - -e '/remove for range/,/}}/{/}}/!d;s/}}/}/}' $< > $@ -datastructures/test/fenwickTree.test: datastructures/test/fenwickTree.cpp \ - datastructures/fenwickTree.cpp -datastructures/test/fenwickTree2.test: datastructures/test/fenwickTree2.cpp \ - datastructures/fenwickTree2.cpp -datastructures/test/monotonicConvexHull.test: \ - datastructures/test/monotonicConvexHull.cpp \ - datastructures/monotonicConvexHull.cpp -datastructures/test/persistent.test: datastructures/test/persistent.cpp \ - datastructures/persistent.cpp -datastructures/test/sparseTable.test: datastructures/test/sparseTable.cpp \ - datastructures/sparseTable.cpp -datastructures/test/sparseTableDisjoint.test: \ - datastructures/test/sparseTableDisjoint.cpp \ - datastructures/sparseTableDisjoint.cpp -graph/test/binary_lifting.test: graph/test/binary_lifting.cpp \ - graph/binary_lifting.cpp graph/test/util.cpp -graph/test/LCA_sparse.test: graph/test/LCA_sparse.cpp \ - graph/LCA_sparse.cpp datastructures/sparseTable.cpp graph/test/util.cpp -math/test/binomial0.test: math/test/binomial0.cpp math/binomial0.cpp \ - math/shortModInv.cpp + +-gmake -f TestMakefile cleantest FORCE: .PHONY: all pdf test clean cleanpdf cleantest FORCE diff --git a/TestMakefile b/TestMakefile new file mode 100644 index 0000000..1be88e2 --- /dev/null +++ b/TestMakefile @@ -0,0 +1,54 @@ +with-defines-subsets = $(if $2,$(call with-defines-subsets,$1,$(call dropfirst,$2)) $(call with-defines-subsets,$1.$(firstword $2),$(call dropfirst,$2)),$1) +dropfirst = $(wordlist 2,$(words $1),$1) + +source = $(dir $*)$(firstword $(subst ., ,$(notdir $*))) +flags = $(call dropfirst,$(subst ., -D,$(notdir $*))) $(CPPFLAGS) +predep = $(patsubst $(source)=%,%,$(filter $(source)=%,$(PREDEPS))) + +TESTS := \ + $(call with-defines-subsets,datastructures/test/segmentTree,SEGTREE_MUL SEGTREE_INIT_DEFAULT SEGTREE_RANGE_UPDATE) \ + $(call with-defines-subsets,datastructures/test/segmentTree.SEGTREE_FIRST_NEG,SEGTREE_INIT_DEFAULT) \ + datastructures/test/lazyPropagation \ + datastructures/test/fenwickTree \ + datastructures/test/fenwickTree2 \ + datastructures/test/monotonicConvexHull \ + datastructures/test/persistent \ + datastructures/test/sparseTable \ + datastructures/test/sparseTableDisjoint \ + graph/test/binary_lifting \ + graph/test/LCA_sparse \ + math/test/binomial0 + +# Dependencies which must be present before generating the .d file. +PREDEPS := \ + datastructures/test/segmentTree=datastructures/test/segmentTree.tmp.cpp + +CPPFLAGS := -include test.h -std=gnu++20 -Wall -Wextra \ + -Werror -fsanitize=address,undefined -fno-sanitize-recover -g + +test: $(TESTS:=.ok) + +cleantest: + rm -f $(TESTS:=.test) $(TESTS:=.ok) $(TESTS:=.d) \ + datastructures/test/segmentTree.tmp.cpp + +%.ok: %.test + timeout -v 2 ./$< + @touch $@ + +.SECONDEXPANSION: +%.test: $$(source).cpp + g++ $(flags) -o $@ $< + +%.d: $$(source).cpp $$(predep) + g++ -MM -MT '$*.test $*.d' -MF '$@' $(flags) $< + +datastructures/test/segmentTree.tmp.cpp: datastructures/segmentTree.cpp \ + datastructures/test/segmentTree.awk + awk -f datastructures/test/segmentTree.awk $< > $@ + +.PHONY: test cleantest +.SECONDARY: $(TESTS:=.test) + +include $(TESTS:=.d) + diff --git a/datastructures/segmentTree.cpp b/datastructures/segmentTree.cpp index 2cbf466..4f75d03 100644 --- a/datastructures/segmentTree.cpp +++ b/datastructures/segmentTree.cpp @@ -4,14 +4,15 @@ struct SegTree { vector<T> tree; static constexpr T E = 0; // Neutral element for combine - SegTree(vector<T>& a) : n(ssize(a)), tree(2 * n) { - //SegTree(int size, T val = E) : n(size), tree(2 * n, val) { + SegTree(vector<T>& a) : n(ssize(a)), tree(2 * n, E) { ranges::copy(a, tree.begin() + n); + //SegTree(int size, T val = E) : n(size), tree(2 * n, E) { + // fill(tree.begin() + n, tree.end(), val); for (int i = n - 1; i > 0; i--) { // remove for range update tree[i] = comb(tree[2 * i], tree[2 * i + 1]); }} - ll comb(T a, T b) {return a + b;} // modify this + neutral + ll comb(T a, T b) { return a + b; } // modify this + neutral void update(int i, T val) { tree[i += n] = val; // apply update code diff --git a/datastructures/test/segmentTree.awk b/datastructures/test/segmentTree.awk new file mode 100644 index 0000000..e863d4e --- /dev/null +++ b/datastructures/test/segmentTree.awk @@ -0,0 +1,74 @@ + +/Neutral element for combine/ { + print "#ifndef SEGTREE_MUL" + print "# ifndef SEGTREE_FIRST_NEG" + print + print "# else" + tmp = $0 + sub(/0/, "numeric_limits<ll>::max()", tmp) + print tmp + print "# endif" + print "#else" + sub(/0/, "1") + print + print "#endif" + next +} + +/modify this \+ neutral/ { + print "#ifndef SEGTREE_MUL" + print "# ifndef SEGTREE_FIRST_NEG" + print + print "# else" + tmp = $0 + sub(/a \+ b/, "a < 0 ? a : min(a, b)", tmp) + print tmp + print "# endif" + print "#else" + sub(/a \+ b/, "a*b % MOD") + print + print "#endif" + next +} + +/SegTree\(vector<T>& a\)/ { + print "#ifndef SEGTREE_INIT_DEFAULT" + print + getline + print + print "#else" + getline + sub(/\/\//, "") + print + getline + sub(/\/\//, "") + print + print "#endif" + next +} + +/remove for range update/ { + print "#ifndef SEGTREE_RANGE_UPDATE" + print + getline + print + getline + print "\t\t}" + print "#endif" + print "\t}" + next +} + +/void update/ { + print "#ifndef SEGTREE_RANGE_UPDATE" +} + +/OR: range update/ { + print "#else" +} + +/^\};$/ { + print "#endif" +} + +{ print } diff --git a/datastructures/test/segmentTree.cpp b/datastructures/test/segmentTree.cpp index 79c16e6..44d99b6 100644 --- a/datastructures/test/segmentTree.cpp +++ b/datastructures/test/segmentTree.cpp @@ -1,25 +1,74 @@ +#ifdef SEGTREE_MUL +constexpr ll MOD = 1'000'000'007; +#endif + #include "segmentTree.tmp.cpp" void test(int n) { +#ifndef SEGTREE_INIT_DEFAULT vector<ll> a(n); for (ll &x: a) x = util::randint(); SegTree seg(a); +#else + ll init = util::randint(); +# ifdef SEGTREE_FIRST_NEG + init = abs(init); +# endif + vector<ll> a(n, init); + SegTree seg(n, init); +#endif for (int i = 0; i < 5*n; i++) { { +#ifndef SEGTREE_RANGE_UPDATE int j = util::randint(n); ll v = util::randint(); a[j] = v; seg.update(j, v); +#else + int l = util::randint(n+1); + int r = util::randint(n+1); + if (l > r) swap(l, r); + ll v = util::randint(); + for (int j = l; j < r; j++) { +# ifndef SEGTREE_MUL + a[j] += v; +# else + a[j] = a[j]*v % MOD; +# endif + } + seg.modify(l, r, v); +#endif } { +#ifndef SEGTREE_RANGE_UPDATE int l = util::randint(n+1); int r = util::randint(n+1); if (l > r) swap(l, r); - assert( - seg.query(l, r) - == - accumulate(a.begin() + l, a.begin() + r, 0ll) - ); +# ifndef SEGTREE_MUL +# ifndef SEGTREE_FIRST_NEG + ll comp = 0; +# else + ll comp = numeric_limits<ll>::max(); +# endif +# else + ll comp = 1; +# endif + for (int j = l; j < r; j++) { +# ifndef SEGTREE_MUL +# ifndef SEGTREE_FIRST_NEG + comp += a[j]; +# else + if (comp >= 0 && comp > a[j]) comp = a[j]; +# endif +# else + comp = comp * a[j] % MOD; +# endif + } + assert(seg.query(l, r) == comp); +#else + int j = util::randint(n); + assert(seg.query(j) == a[j]); +#endif } } } @@ -27,4 +76,25 @@ void test(int n) { int main() { test(1000); test(1); + { +#ifndef SEGTREE_INIT_DEFAULT + vector<ll> a; + SegTree seg(a); +#else + SegTree seg(0); +#endif +#ifndef SEGTREE_RANGE_UPDATE +# ifndef SEGTREE_MUL +# ifndef SEGTREE_FIRST_NEG + assert(seg.query(0, 0) == 0); +# else + assert(seg.query(0, 0) == numeric_limits<ll>::max()); +# endif +# else + assert(seg.query(0, 0) == 1); +# endif +#else + seg.modify(0, 0, util::randint()); +#endif + } } diff --git a/datastructures/test/segmentTree2.cpp b/datastructures/test/segmentTree2.cpp deleted file mode 100644 index f403a1d..0000000 --- a/datastructures/test/segmentTree2.cpp +++ /dev/null @@ -1,26 +0,0 @@ -#include "segmentTree2.tmp.cpp" - -void test(int n) { - vector<ll> a(n); - for (ll &x: a) x = util::randint(); - SegTree seg(a); - for (int i = 0; i < 5*n; i++) { - { - int l = util::randint(n+1); - int r = util::randint(n+1); - if (l > r) swap(l, r); - ll v = util::randint(); - for (int i = l; i < r; i++) a[i] += v; - seg.modify(l, r, v); - } - { - int j = util::randint(n); - assert(seg.query(j) == a[j]); - } - } -} - -int main() { - test(1000); - test(1); -} @@ -1,3 +1,5 @@ +#define _GLIBCXX_DEBUG 1 +#define _GLIBCXX_SANITIZE_VECTOR 1 #include <bits/stdc++.h> using namespace std; using ll = long long; |