| 51 | |
| 52 | template <class T, class Metric> |
| 53 | std::pair<int, int> IndexedSet<T, Metric>::testonly_assertBalanced(typename IndexedSet<T, Metric>::Node* n, |
| 54 | int depth, |
| 55 | bool checkAVL) { |
| 56 | /* An IndexedSet (sub)tree n has the following invariants: |
| 57 | (1) BST invariant: Every descendant x of n->child[0] has x->data < n->data, and every descendant x of |
| 58 | n->child[1] has x->data > n->data (2) Balance invariant: n->balance is the difference between the height (greatest |
| 59 | distance to a descendant) of n->child[1] and the height of n->child[0] (3) AVL invariant: n->balance is -1, 0 or 1 |
| 60 | (4) Metric invariant: n->total is the sum of the metric value with which n and each of its descendants was |
| 61 | inserted (5) Parent invariant: Every child x of n has x->parent==n |
| 62 | |
| 63 | This function checks all of these for all descendants of n. It assumes that every node was inserted with a metric |
| 64 | of 3 in order to check the metric invariant. If checkAVL==false, it does not check the AVL invariant (since this is |
| 65 | often temporarily broken and then restored during operations, this permits checking invariants e.g. before a |
| 66 | rebalancing operation) |
| 67 | */ |
| 68 | if (!n && depth == 0) |
| 69 | n = root; |
| 70 | |
| 71 | if (!n) { |
| 72 | return std::make_pair(0, 0); |
| 73 | } |
| 74 | bool ok = true; |
| 75 | for (int i = 0; i < 2; i++) { |
| 76 | if (n->child[i] && n->child[i]->parent != n) { |
| 77 | indent(depth); |
| 78 | printf("Parent check failed\n"); |
| 79 | ok = false; |
| 80 | } |
| 81 | } |
| 82 | if (n->child[0] && !(n->child[0]->data < n->data)) { |
| 83 | indent(depth); |
| 84 | printf("Not a binary search tree\n"); |
| 85 | ok = false; |
| 86 | } |
| 87 | if (n->child[1] && !(n->data < n->child[1]->data)) { |
| 88 | indent(depth); |
| 89 | printf("Not a binary search tree\n"); |
| 90 | ok = false; |
| 91 | } |
| 92 | auto lp = testonly_assertBalanced(n->child[0], depth + 1, checkAVL); |
| 93 | auto rp = testonly_assertBalanced(n->child[1], depth + 1, checkAVL); |
| 94 | int lh = lp.first; |
| 95 | int rh = rp.first; |
| 96 | if (n->balance != rh - lh) { |
| 97 | indent(depth); |
| 98 | printf("Balance is incorrect %d %d %d (@%d)\n", n->balance, rh, lh, n->data); |
| 99 | ok = false; |
| 100 | } |
| 101 | if (checkAVL && (n->balance < -1 || n->balance > 1)) { |
| 102 | indent(depth); |
| 103 | printf("AVL invariant broken %d %d %d\n", n->balance, rh, lh); |
| 104 | ok = false; |
| 105 | } |
| 106 | if (n->total != lp.second + rp.second + 3) { |
| 107 | indent(depth); |
| 108 | printf("Metric totals are wrong %d != %d + %d + 3\n", n->total, lp.second, rp.second); |
| 109 | ok = false; |
| 110 | } |
no test coverage detected