Geometry/test_llrb.cpp at main · CyrilSharma/Geometry · GitHub

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
#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "llrb.h"

#include <algorithm>
#include "doctest.h"
#include <iostream>
#include <random>
#include <vector>

using namespace std;

TEST_CASE("Ordered") {
    mt19937 rng(69420);
    for (int sz = 10; sz <= 100; sz++) {
        vector<int> permutation(sz);
        for (int i = 0; i < sz; i++)
            permutation[i] = i;

        shuffle(permutation.begin(), permutation.end(), rng);

        llrb tree;
        for (int i = 0; i < sz; i++)
            tree.insert(permutation[i]);

        for (int i = 0; i < sz; i++)
            CHECK(tree.rank(i) == i+1);
    }
}

TEST_CASE("Black Height") {
    mt19937 rng(69420);
    for (int sz = 10; sz <= 100; sz++) {
        vector<int> permutation(sz);

        for (int i = 0; i < sz; i++)
            permutation[i] = i;

        shuffle(permutation.begin(), permutation.end(), rng);

        llrb tree;
        for (int i = 0; i < sz; i++)
            tree.insert(permutation[i]);

        vector<int> heights;
        using node_ptr = llrb::node_ptr;
        function<void(node_ptr,int)> dfs;
        dfs = [&](node_ptr root, int height) {
            if (root->left) dfs(root->left, height + (root->left->color == BLACK));
            if (root->right) dfs(root->right, height + (root->right->color == BLACK));
            if (!root->left && !root->right)
                heights.push_back(height);
        };
        dfs(tree.root, 0);

        for (int i = 1; i < heights.size(); i++) {
            CHECK(heights[i-1] == heights[i]);
        }
    }
}