| 55 | }; |
| 56 | |
| 57 | static void checkRbTree(MyRbTree& tree, HighsInt* expectedKeys, |
| 58 | HighsInt numExpectedKeys) { |
| 59 | std::vector<HighsInt> keys; |
| 60 | keys.reserve(numExpectedKeys); |
| 61 | if (tree.root != -1) REQUIRE(tree.nodes[tree.root].links.isBlack()); |
| 62 | |
| 63 | HighsInt x = tree.first(); |
| 64 | while (x != -1) { |
| 65 | keys.push_back(tree.nodes[x].key); |
| 66 | if (tree.nodes[x].links.isRed()) { |
| 67 | HighsInt lChild = tree.nodes[x].links.child[0]; |
| 68 | HighsInt rChild = tree.nodes[x].links.child[1]; |
| 69 | if (lChild != -1) REQUIRE(tree.nodes[lChild].links.isBlack()); |
| 70 | if (rChild != -1) REQUIRE(tree.nodes[rChild].links.isBlack()); |
| 71 | } |
| 72 | x = tree.successor(x); |
| 73 | REQUIRE((HighsInt)keys.size() <= numExpectedKeys); |
| 74 | } |
| 75 | |
| 76 | REQUIRE((HighsInt)keys.size() == numExpectedKeys); |
| 77 | std::sort(expectedKeys, expectedKeys + numExpectedKeys); |
| 78 | bool isOk = std::equal(keys.begin(), keys.end(), expectedKeys); |
| 79 | REQUIRE(isOk); |
| 80 | } |
| 81 | |
| 82 | TEST_CASE("HighsRbTree", "[util]") { |
| 83 | std::vector<HighsInt> keys; |