jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2021, Idan Horowitz <idan.horowitz@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <LibTest/TestCase.h>
8
9#include <AK/Random.h>
10#include <AK/RedBlackTree.h>
11
12TEST_CASE(construct)
13{
14 RedBlackTree<int, int> empty;
15 EXPECT(empty.is_empty());
16 EXPECT(empty.size() == 0);
17}
18
19TEST_CASE(ints)
20{
21 RedBlackTree<int, int> ints;
22 ints.insert(1, 10);
23 ints.insert(3, 20);
24 ints.insert(2, 30);
25 EXPECT_EQ(ints.size(), 3u);
26 EXPECT_EQ(*ints.find(3), 20);
27 EXPECT_EQ(*ints.find(2), 30);
28 EXPECT_EQ(*ints.find(1), 10);
29 EXPECT(!ints.remove(4));
30 EXPECT(ints.remove(2));
31 EXPECT(ints.remove(1));
32 EXPECT(ints.remove(3));
33 EXPECT_EQ(ints.size(), 0u);
34}
35
36TEST_CASE(largest_smaller_than)
37{
38 RedBlackTree<int, int> ints;
39 ints.insert(1, 10);
40 ints.insert(11, 20);
41 ints.insert(21, 30);
42 EXPECT_EQ(ints.size(), 3u);
43 EXPECT_EQ(*ints.find_largest_not_above(3), 10);
44 EXPECT_EQ(*ints.find_largest_not_above(17), 20);
45 EXPECT_EQ(*ints.find_largest_not_above(22), 30);
46 EXPECT_EQ(ints.find_largest_not_above(-5), nullptr);
47}
48
49TEST_CASE(key_ordered_iteration)
50{
51 constexpr auto amount = 10000;
52 RedBlackTree<int, size_t> test;
53 Array<int, amount> keys {};
54
55 // generate random key order
56 for (int i = 0; i < amount; i++) {
57 keys[i] = i;
58 }
59 for (size_t i = 0; i < amount; i++) {
60 swap(keys[i], keys[get_random<size_t>() % amount]);
61 }
62
63 // insert random keys
64 for (size_t i = 0; i < amount; i++) {
65 test.insert(keys[i], keys[i]);
66 }
67
68 // check key-ordered iteration
69 size_t index = 0;
70 for (auto& value : test) {
71 EXPECT(value == index++);
72 }
73
74 // ensure we can remove all of them (aka, tree structure is not destroyed somehow)
75 for (size_t i = 0; i < amount; i++) {
76 EXPECT(test.remove(i));
77 }
78}
79
80TEST_CASE(clear)
81{
82 RedBlackTree<size_t, size_t> test;
83 for (size_t i = 0; i < 1000; i++) {
84 test.insert(i, i);
85 }
86 test.clear();
87 EXPECT_EQ(test.size(), 0u);
88}
89
90TEST_CASE(find_smallest_not_below_iterator)
91{
92 RedBlackTree<size_t, size_t> test;
93
94 for (size_t i = 0; i < 8; i++) {
95 auto above_all = test.find_smallest_not_below_iterator(i);
96 EXPECT(above_all.is_end());
97
98 test.insert(i, i);
99
100 auto only_just_added_i_is_not_below = test.find_smallest_not_below_iterator(i);
101 EXPECT(!only_just_added_i_is_not_below.is_end());
102 EXPECT_EQ(only_just_added_i_is_not_below.key(), i);
103 }
104
105 {
106 auto smallest_not_below_two = test.find_smallest_not_below_iterator(2);
107 EXPECT(!smallest_not_below_two.is_end());
108 EXPECT_EQ(smallest_not_below_two.key(), 2u);
109 }
110
111 test.remove(2);
112
113 {
114 auto smallest_not_below_two_without_two = test.find_smallest_not_below_iterator(2);
115 EXPECT(!smallest_not_below_two_without_two.is_end());
116 EXPECT_EQ(smallest_not_below_two_without_two.key(), 3u);
117 }
118
119 {
120 auto smallest_not_below_one = test.find_smallest_not_below_iterator(1);
121 EXPECT(!smallest_not_below_one.is_end());
122 EXPECT_EQ(smallest_not_below_one.key(), 1u);
123 }
124
125 {
126 auto smallest_not_below_three = test.find_smallest_not_below_iterator(3);
127 EXPECT(!smallest_not_below_three.is_end());
128 EXPECT_EQ(smallest_not_below_three.key(), 3u);
129 }
130}
131
132TEST_CASE(iterators_on_emptied_tree)
133{
134 RedBlackTree<size_t, size_t> test;
135 test.insert(1, 1);
136 test.remove(1);
137 EXPECT_EQ(test.size(), 0u);
138 auto begin_iterator = test.begin();
139 auto end_iterator = test.end();
140 EXPECT(begin_iterator.is_end());
141
142 EXPECT_EQ(begin_iterator, end_iterator);
143 EXPECT(!(begin_iterator != end_iterator));
144}