| 1 | void test() { |
| 2 | /* Field testing: UVa 978, UVa 1513, UVa 12049, Kattis turbo */ |
| 3 | |
| 4 | int cnt = 10000, |
| 5 | range = 1000; |
| 6 | |
| 7 | avl_tree<int> t1; |
| 8 | set<int> t2; |
| 9 | |
| 10 | assert_equal(0, t1.size()); |
| 11 | |
| 12 | for (int i = 0; i < cnt; i++) { |
| 13 | int n = rng() % range; |
| 14 | avl_tree<int>::node *p = t1.insert(n); |
| 15 | assert_equal(n, p->item); |
| 16 | t2.insert(n); |
| 17 | assert_equal((int)size(t2), (int)size(t1)); |
| 18 | |
| 19 | int n1 = rng() % range; |
| 20 | avl_tree<int>::node *b = t1.find(n1); |
| 21 | if (b) assert_equal(n1, b->item); |
| 22 | assert_equal(b == NULL, t2.find(n1) == t2.end()); |
| 23 | |
| 24 | int n2 = rng() % range; |
| 25 | t1.erase(n2); |
| 26 | t2.erase(n2); |
| 27 | assert_equal((int)size(t2), (int)size(t1)); |
| 28 | } |
| 29 | |
| 30 | t1.clear(); |
| 31 | t2.clear(); |
| 32 | |
| 33 | assert_equal(0, t1.size()); |
| 34 | |
| 35 | for (int i = 0; i < cnt; i++) { |
| 36 | int n = rng() % range; |
| 37 | avl_tree<int>::node *p = t1.insert(n); |
| 38 | assert_equal(n, p->item); |
| 39 | t2.insert(n); |
| 40 | assert_equal((int)size(t2), (int)size(t1)); |
| 41 | |
| 42 | int n1 = rng() % range; |
| 43 | avl_tree<int>::node *b = t1.find(n1); |
| 44 | if (b) assert_equal(n1, b->item); |
| 45 | assert_equal(b == NULL, t2.find(n1) == t2.end()); |
| 46 | |
| 47 | int n2 = rng() % range; |
| 48 | t1.erase(n2); |
| 49 | t2.erase(n2); |
| 50 | assert_equal((int)size(t2), (int)size(t1)); |
| 51 | } |
| 52 | |
| 53 | for (int i = 0; i < range; i++) { |
| 54 | t1.erase(i); |
| 55 | t2.erase(i); |
| 56 | assert_equal((int)size(t2), (int)size(t1)); |
| 57 | } |
| 58 | |
| 59 | assert_equal(0, t1.size()); |
| 60 | } |