summaryrefslogtreecommitdiff
path: root/datastructures/test
diff options
context:
space:
mode:
Diffstat (limited to 'datastructures/test')
-rw-r--r--datastructures/test/fenwickTree.cpp26
-rw-r--r--datastructures/test/fenwickTree2.cpp28
-rw-r--r--datastructures/test/lazyPropagation.awk86
-rw-r--r--datastructures/test/lazyPropagation.cpp102
-rw-r--r--datastructures/test/monotonicConvexHull.cpp27
-rw-r--r--datastructures/test/persistent.cpp11
-rw-r--r--datastructures/test/segmentTree.awk74
-rw-r--r--datastructures/test/segmentTree.cpp100
-rw-r--r--datastructures/test/sparseTable.cpp26
-rw-r--r--datastructures/test/sparseTableDisjoint.cpp26
-rw-r--r--datastructures/test/treap2.cpp41
-rw-r--r--datastructures/test/waveletTree.cpp38
12 files changed, 0 insertions, 585 deletions
diff --git a/datastructures/test/fenwickTree.cpp b/datastructures/test/fenwickTree.cpp
deleted file mode 100644
index f9dd619..0000000
--- a/datastructures/test/fenwickTree.cpp
+++ /dev/null
@@ -1,26 +0,0 @@
-#include "../fenwickTree.cpp"
-
-void test(int n) {
- vector<ll> naive(n);
- init(n);
-
- for (int i = 0; i < 1000; i++) {
- int p = util::randint(n);
- ll delta = util::randint();
- update(p, delta);
- naive[p] += delta;
-
- int r = util::randint(n+1);
-
- ll naive_result = 0;
- for (int i = 0; i < r; i++) naive_result += naive[i];
- ll fenwick_result = prefix_sum(r);
- assert(naive_result == fenwick_result);
- }
-}
-
-int main() {
- test(1);
- test(100);
- test(1000);
-}
diff --git a/datastructures/test/fenwickTree2.cpp b/datastructures/test/fenwickTree2.cpp
deleted file mode 100644
index 18ebcb7..0000000
--- a/datastructures/test/fenwickTree2.cpp
+++ /dev/null
@@ -1,28 +0,0 @@
-#include "../fenwickTree2.cpp"
-
-void test(int n) {
- vector<ll> naive(n);
- for (int i = 0; i < n; i++) naive[i] = util::randint();
- init(naive);
-
- for (int i = 0; i < 1000; i++) {
- int l = util::randint(n), r = util::randint(n);
- if (l > r) swap(l, r);
- ll delta = util::randint();
- update(l, r, delta);
- for (int i = l; i < r; i++) naive[i] += delta;
-
- r = util::randint(n+1);
-
- ll naive_result = 0;
- for (int i = 0; i < r; i++) naive_result += naive[i];
- ll fenwick_result = prefix_sum(r);
- assert(naive_result == fenwick_result);
- }
-}
-
-int main() {
- test(1);
- test(100);
- test(1000);
-}
diff --git a/datastructures/test/lazyPropagation.awk b/datastructures/test/lazyPropagation.awk
deleted file mode 100644
index fc39305..0000000
--- a/datastructures/test/lazyPropagation.awk
+++ /dev/null
@@ -1,86 +0,0 @@
-
-/Neutral element for combine/ {
- print "#ifndef SEGTREE_FIRST_NEG"
- print "# ifndef SEGTREE_MAX"
- print
- print "# else"
- tmp = $0
- sub(/0/, "numeric_limits<T>::min()", tmp)
- print tmp
- print "# endif"
- print "#else"
- sub(/0/, "numeric_limits<T>::max()")
- print
- print "#endif"
- next
-}
-
-/Modify this \+ E/ {
- print "#ifndef SEGTREE_FIRST_NEG"
- print "# ifndef SEGTREE_MAX"
- print
- print "# else"
- tmp = $0
- sub(/a \+ b/, "max(a, b)", tmp)
- print tmp
- print "# endif"
- print "#else"
- sub(/a \+ b/, "a < 0 ? a : min(a, b)")
- print
- print "#endif"
- next
-}
-
-/Unused value by updates/ {
- print "#ifndef SEGTREE_FIRST_NEG"
- print
- print "#else"
- sub(/0/, /numeric_limits<U>::max()/)
- print
- print "#endif"
- next
-}
-
-/And this \+ UF/ {
- print
- getline set_tree
- getline set_lazy
- print "#ifndef SEGTREE_MAX"
- print "# ifndef SEGTREE_FIRST_NEG"
- print set_tree
- print "# else"
- tmp = set_tree
- sub(/val \* k\[i\]/, "val", tmp)
- print tmp
- print "# endif"
- print set_lazy
- print "#else"
- sub(/= val \* k\[i\]/, "+= val", set_tree)
- sub(/= val/, "+= val", set_lazy)
- print set_tree
- print set_lazy
- print "#endif"
- next
-}
-
-/Optional/ { print "#ifdef SEGTREE_MAX" }
-/^\};$/ { print "#endif" }
-
-/SegTree\(const vector<T>& a\)/ {
- print "#ifndef SEGTREE_INIT_DEFAULT"
- print
- print "#else"
- getline
- sub(/\/\//, "")
- print
- print "#endif"
- getline
- print
- print "#ifndef SEGTREE_INIT_DEFAULT"
- getline
- print
- print "#endif"
- next
-}
-
-{ print }
diff --git a/datastructures/test/lazyPropagation.cpp b/datastructures/test/lazyPropagation.cpp
deleted file mode 100644
index df97b14..0000000
--- a/datastructures/test/lazyPropagation.cpp
+++ /dev/null
@@ -1,102 +0,0 @@
-#include "lazyPropagation.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++) {
- {
- int l = util::randint(n+1);
- int r = util::randint(n+1);
- if (l > r) swap(l, r);
- ll v = util::randint();
-#ifndef SEGTREE_FIRST_NEG
-# ifndef SEGTREE_MAX
- if (v == 0) v = 1;
-# endif
-#endif
- for (int j = l; j < r; j++) {
-#ifndef SEGTREE_MAX
- a[j] = v;
-#else
- a[j] += v;
-#endif
- }
- seg.update(l, r, v);
- }
- {
- int l = util::randint(n+1);
- int r = util::randint(n+1);
- if (l > r) swap(l, r);
-#ifndef SEGTREE_FIRST_NEG
-# ifndef SEGTREE_MAX
- ll comp = 0;
-# else
- ll comp = numeric_limits<ll>::min();
-# endif
-#else
- ll comp = numeric_limits<ll>::max();
-#endif
- for (int j = l; j < r; j++) {
-#ifndef SEGTREE_FIRST_NEG
-# ifndef SEGTREE_MAX
- comp += a[j];
-# else
- comp = max(comp, a[j]);
-# endif
-#else
- if (comp >= 0 && comp > a[j]) comp = a[j];
-#endif
- }
- assert(seg.query(l, r) == comp);
- }
-#ifdef SEGTREE_MAX
- {
- int l = util::randint(n+1);
- int r = util::randint(n+1);
- if (l > r) swap(l, r);
- ll bound = util::randint();
- int found = -1;
- for (int j = l; j < r; j++) {
- if (a[j] >= bound) {
- found = j;
- break;
- }
- }
- assert(seg.lower_bound(l, r, bound) == found);
- }
-#endif
- }
-}
-
-int main() {
- test(1000);
- test(1);
- {
-#ifndef SEGTREE_INIT_DEFAULT
- vector<ll> a;
- SegTree seg(a);
-#else
- SegTree seg(0);
-#endif
- seg.update(0, 0, util::randint());
-#ifndef SEGTREE_FIRST_NEG
-# ifndef SEGTREE_MAX
- assert(seg.query(0, 0) == 0);
-# else
- assert(seg.query(0, 0) == numeric_limits<ll>::min());
-# endif
-#else
- assert(seg.query(0, 0) == numeric_limits<ll>::max());
-#endif
- }
-}
diff --git a/datastructures/test/monotonicConvexHull.cpp b/datastructures/test/monotonicConvexHull.cpp
deleted file mode 100644
index 08927a2..0000000
--- a/datastructures/test/monotonicConvexHull.cpp
+++ /dev/null
@@ -1,27 +0,0 @@
-#define sz(X) ((int)size(X))
-#include "../monotonicConvexHull.cpp"
-
-int main() {
- {
- Envelope env;
- env.add(10, 0);
- assert(env.query(0) == 0);
- assert(env.query(1) == 10);
- env.add(8, 5);
- assert(env.query(1) == 10);
- assert(env.query(2) == 20);
- assert(env.query(3) == 29);
- env.add(7, 10);
- assert(env.query(10) == 80);
- env.add(0, 0);
- assert(env.query(11) == 0);
- }
-
- {
- Envelope env;
- env.add(1, 0);
- env.add(0, 10);
- env.add(-1, 10);
- assert(env.query(7) == 3);
- }
-}
diff --git a/datastructures/test/persistent.cpp b/datastructures/test/persistent.cpp
deleted file mode 100644
index 5e5f864..0000000
--- a/datastructures/test/persistent.cpp
+++ /dev/null
@@ -1,11 +0,0 @@
-#define all(X) begin(X), end(X)
-#include "../persistent.cpp"
-
-int main() {
- int time = 0;
- persistent<int> p(time, 0);
- p.set(1);
- int t1 = time;
- p.set(2);
- assert(p.get(t1) == 1);
-}
diff --git a/datastructures/test/segmentTree.awk b/datastructures/test/segmentTree.awk
deleted file mode 100644
index e863d4e..0000000
--- a/datastructures/test/segmentTree.awk
+++ /dev/null
@@ -1,74 +0,0 @@
-
-/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
deleted file mode 100644
index 44d99b6..0000000
--- a/datastructures/test/segmentTree.cpp
+++ /dev/null
@@ -1,100 +0,0 @@
-#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);
-# 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
- }
- }
-}
-
-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/sparseTable.cpp b/datastructures/test/sparseTable.cpp
deleted file mode 100644
index 03ef548..0000000
--- a/datastructures/test/sparseTable.cpp
+++ /dev/null
@@ -1,26 +0,0 @@
-#define sz ssize
-#define all(X) begin(X), end(X)
-#include "../sparseTable.cpp"
-
-void test(int n) {
- vector<ll> values(n);
- for (ll &x: values) x = util::randint();
- SparseTable st;
- st.init(values);
- for (int i = 0; i < n; i++) {
- int l = util::randint(n);
- int r = util::randint(n);
- if (l > r) swap(l, r);
- r++;
- assert(
- values[st.queryIdempotent(l, r)]
- ==
- *min_element(values.begin()+l, values.begin()+r)
- );
- }
-}
-
-int main() {
- test(1000);
- test(1);
-}
diff --git a/datastructures/test/sparseTableDisjoint.cpp b/datastructures/test/sparseTableDisjoint.cpp
deleted file mode 100644
index 7ef6483..0000000
--- a/datastructures/test/sparseTableDisjoint.cpp
+++ /dev/null
@@ -1,26 +0,0 @@
-#define sz ssize
-#define all(X) begin(X), end(X)
-#include "../sparseTableDisjoint.cpp"
-
-void test(int n) {
- vector<ll> values(n);
- for (ll &x: values) x = util::randint();
- DisjointST st;
- st.init(values);
- for (int i = 0; i < n; i++) {
- int l = util::randint(n);
- int r = util::randint(n);
- if (l > r) swap(l, r);
- r++;
- assert(
- st.query(l, r)
- ==
- accumulate(values.begin()+l, values.begin()+r, 0ll)
- );
- }
-}
-
-int main() {
- test(1000);
- test(1);
-}
diff --git a/datastructures/test/treap2.cpp b/datastructures/test/treap2.cpp
deleted file mode 100644
index 1a435d3..0000000
--- a/datastructures/test/treap2.cpp
+++ /dev/null
@@ -1,41 +0,0 @@
-#include "../treap2.cpp"
-
-void test(int n) {
- Treap treap;
- vector<ll> dumb;
- for (int i = 0; i < n; i++) {
- assert(treap.getSize(treap.root) == ssize(dumb));
- int j = util::randint(ssize(dumb) + 1);
- ll x = util::randint();
- treap.insert(j, x);
- dumb.insert(begin(dumb) + j, x);
- }
- for (int i = 0; i < 5*n; i++) {
- assert(treap.getSize(treap.root) == ssize(dumb));
- {
- int j = util::randint(ssize(dumb));
- treap.remove(j);
- dumb.erase(begin(dumb) + j);
- }
- {
- int j = util::randint(ssize(dumb) + 1);
- ll x = util::randint();
- treap.insert(j, x);
- dumb.insert(begin(dumb) + j, x);
- }
- }
- for (int i = 0; i < n; i++) {
- assert(treap.getSize(treap.root) == ssize(dumb));
- int j = util::randint(ssize(dumb));
- treap.remove(j);
- dumb.erase(begin(dumb) + j);
- }
- assert(treap.root < 0);
- assert(empty(dumb));
-}
-
-int main() {
- test(1000);
- test(1);
- test(0);
-}
diff --git a/datastructures/test/waveletTree.cpp b/datastructures/test/waveletTree.cpp
deleted file mode 100644
index c5da1d2..0000000
--- a/datastructures/test/waveletTree.cpp
+++ /dev/null
@@ -1,38 +0,0 @@
-#include "../waveletTree.cpp"
-
-void test(int n) {
- vector<ll> values(n);
- for (ll &x: values) x = util::randint();
- vector<ll> backup = values;
- WaveletTree wave(values);
- assert(values == backup);
- for (int i = 0; i < n; i++) {
- int l = util::randint(n+1);
- int r = util::randint(n+1);
- if (l > r) swap(l, r);
- ll bound = util::randint();
- int res = 0;
- for (ll x: values | views::take(r) | views::drop(l)) {
- if (x < bound) res++;
- }
- assert(wave.countSmaller(l, r, bound) == res);
- }
- for (int i = 0; 5*i < n; i++) {
- int l = util::randint(n);
- int m = util::randint(n);
- int r = util::randint(n);
- if (l > m) swap(l, m);
- if (m > r) swap(m, r);
- if (l > m) swap(l, m);
- r++;
- int k = m-l;
- vector<ll> part(values.begin()+l, values.begin()+r);
- ranges::nth_element(part, part.begin() + k);
- assert(wave.kth(l, r, k) == part[k]);
- }
-}
-
-int main() {
- test(1000);
- test(1);
-}
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 22:24:12 +0000