datastructures/test/treap2.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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);
}