summaryrefslogtreecommitdiff
path: root/test/datastructures
diff options
context:
space:
mode:
Diffstat (limited to 'test/datastructures')
-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
13 files changed, 19 insertions, 81 deletions
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>
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 23:25:56 +0000