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, 585 insertions, 0 deletions
diff --git a/datastructures/test/fenwickTree.cpp b/datastructures/test/fenwickTree.cpp
new file mode 100644
index 0000000..f9dd619
--- /dev/null
+++ b/datastructures/test/fenwickTree.cpp
@@ -0,0 +1,26 @@
+#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
new file mode 100644
index 0000000..18ebcb7
--- /dev/null
+++ b/datastructures/test/fenwickTree2.cpp
@@ -0,0 +1,28 @@
+#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
new file mode 100644
index 0000000..fc39305
--- /dev/null
+++ b/datastructures/test/lazyPropagation.awk
@@ -0,0 +1,86 @@
+
+/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
new file mode 100644
index 0000000..df97b14
--- /dev/null
+++ b/datastructures/test/lazyPropagation.cpp
@@ -0,0 +1,102 @@
+#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
new file mode 100644
index 0000000..08927a2
--- /dev/null
+++ b/datastructures/test/monotonicConvexHull.cpp
@@ -0,0 +1,27 @@
+#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
new file mode 100644
index 0000000..5e5f864
--- /dev/null
+++ b/datastructures/test/persistent.cpp
@@ -0,0 +1,11 @@
+#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
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
new file mode 100644
index 0000000..44d99b6
--- /dev/null
+++ b/datastructures/test/segmentTree.cpp
@@ -0,0 +1,100 @@
+#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
new file mode 100644
index 0000000..03ef548
--- /dev/null
+++ b/datastructures/test/sparseTable.cpp
@@ -0,0 +1,26 @@
+#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
new file mode 100644
index 0000000..7ef6483
--- /dev/null
+++ b/datastructures/test/sparseTableDisjoint.cpp
@@ -0,0 +1,26 @@
+#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
new file mode 100644
index 0000000..1a435d3
--- /dev/null
+++ b/datastructures/test/treap2.cpp
@@ -0,0 +1,41 @@
+#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
new file mode 100644
index 0000000..c5da1d2
--- /dev/null
+++ b/datastructures/test/waveletTree.cpp
@@ -0,0 +1,38 @@
+#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 18:33:59 +0000