-
Notifications
You must be signed in to change notification settings - Fork 0
/
tests.hpp
91 lines (86 loc) · 3.08 KB
/
tests.hpp
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#ifndef TESTS_HPP
#define TESTS_HPP
#include "rb_tree.hpp"
void test();
template <typename T>
unsigned check_nested(const node_base<T> * nil, const node_base<T> * n) {
if (n == nil) return 0;
// check childes order
if (n->left != nil && n->left->get_value() > n->get_value()) {
std::cout << "Tree is unordered: "
<< n->left->get_value()
<< "is left child of "
<< n->get_value() << std::endl;
throw;
}
if (n->right != nil && n->right->get_value() < n->get_value()) {
std::cout << "Tree is unordered: "
<< n->right->get_value()
<< "is right child of "
<< n->get_value() << std::endl;
throw;
}
// check parents
if (n->left != nil && n->left->parent != n) {
std::cout << "left child of " << n->get_value()
<< " (" << n->left->get_value() << ") "
<< "has wrong parent ";
if (n->left->parent != nil) {
std::cout << n->left->parent->get_value() << std::endl;
} else {
std::cout << "nil" << std::endl;
}
throw;
}
if (n->right != nil && n->right->parent != n) {
std::cout << "right child of " << n->get_value()
<< " (" << n->right->get_value() << ") "
<< "has wrong parent ";
if (n->right->parent != nil) {
std::cout << n->right->parent->get_value() << std::endl;
} else {
std::cout << "nil" << std::endl;
}
throw;
}
// check other properties of red-black tree
if (n->color == red) {
if (n->left != nil && n->left->color == red) {
std::cout << n->get_value() << " is red, but has red child "
<< n->left->get_value() << std::endl;
throw;
}
if (n->right != nil && n->right->color == red) {
std::cout << n->get_value() << " is red, but has red child "
<< n->right->get_value() << std::endl;
throw;
}
}
if (n->left != nil && n->right != nil) {
auto left_black_height = check_nested<T>(nil, n->left);
auto right_black_height = check_nested<T>(nil, n->right);
if (left_black_height != right_black_height) {
std::cout << "there is disbalance below " << n->get_value()
<< " left subtree has " << left_black_height
<< " black nodes to leaf, while right has "
<< right_black_height << std::endl;
throw;
}
}
if (n->left != nil) return check_nested<T>(nil, n->left) + (n->color == black);
if (n->right != nil) return check_nested<T>(nil, n->right) + (n->color == black);
return n->color == black;
}
template <typename T>
void check(const node_base<T> * root) {
if (root->color != black) {
std::cout << "root is not black" << std::endl;
throw;
}
if (root->parent->color != black) {
std::cout << "nil color is not black" << std::endl;
throw;
}
check_nested<T>(root->parent, root);
}
#endif