Mercurial > dedupe

comparison TestRBTree.cpp @ 16:06166d6c083b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add configuration processing. Cache DB values Add a custom RBTree to save space. Track multiple DB connections properly. More testing. Add ValueExistsException.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Tue, 28 Aug 2012 18:58:02 +0200
parents
children 247adcbbaf8b
comparison
equal deleted inserted replaced
15:199fc63c60c1 16:06166d6c083b
1 #include "RBTree.hpp"
2 #include "TestFramework.hpp"
3
4 #include <QtCore/QString>
5
6 BOOST_AUTO_TEST_CASE( TestInsertLeftHeavy )
7 {
8 RBTree<QString> map;
9
10 QString k1 = "9";
11 QString k2 = "8";
12 QString k3 = "7";
13 QString k4 = "6";
14
15 BOOST_REQUIRE(!map.find(k1));
16 BOOST_REQUIRE_EQUAL(map.depth(), 0u);
17 BOOST_REQUIRE_EQUAL(map.total_depth(), 0u);
18 BOOST_REQUIRE_EQUAL(map.size(), 0u);
19 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 0u);
20 map.insert(k1);
21 BOOST_REQUIRE_EQUAL(map.depth(), 1u);
22 BOOST_REQUIRE_EQUAL(map.total_depth(), 1u);
23 BOOST_REQUIRE_EQUAL(map.size(), 1u);
24 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 1u);
25 BOOST_REQUIRE_THROW(map.insert(k1), ValueExistsException);
26 BOOST_REQUIRE(map.find(k1));
27 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
28
29 BOOST_REQUIRE(!map.find(k3));
30 map.insert(k2);
31 BOOST_REQUIRE_EQUAL(map.depth(), 2u);
32 BOOST_REQUIRE_EQUAL(map.total_depth(), 3u);
33 BOOST_REQUIRE_EQUAL(map.size(), 2u);
34 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
35 BOOST_REQUIRE_THROW(map.insert(k2), ValueExistsException);
36 BOOST_REQUIRE(map.find(k1));
37 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
38 BOOST_REQUIRE(map.find(k2));
39 BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
40
41 BOOST_REQUIRE(!map.find(k3));
42 map.insert(k3);
43 BOOST_WARN_EQUAL(map.depth(), 2u);
44 BOOST_WARN_EQUAL(map.total_depth(), 5u);
45 BOOST_REQUIRE_EQUAL(map.size(), 3u);
46 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
47 BOOST_REQUIRE_THROW(map.insert(k3), ValueExistsException);
48 BOOST_REQUIRE(map.find(k1));
49 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
50 BOOST_REQUIRE(map.find(k2));
51 BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
52 BOOST_REQUIRE(map.find(k3));
53 BOOST_REQUIRE_EQUAL(*map.find(k3), k3);
54
55 BOOST_REQUIRE(!map.find(k4));
56 map.insert(k4);
57 BOOST_WARN_EQUAL(map.depth(), 2u);
58 BOOST_WARN_EQUAL(map.total_depth(), 8u);
59 BOOST_REQUIRE_EQUAL(map.size(), 4u);
60 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 3u);
61 BOOST_REQUIRE_THROW(map.insert(k4), ValueExistsException);
62 BOOST_REQUIRE(map.find(k1));
63 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
64 BOOST_REQUIRE(map.find(k2));
65 BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
66 BOOST_REQUIRE(map.find(k4));
67 BOOST_REQUIRE_EQUAL(*map.find(k4), k4);
68 }
69
70 BOOST_AUTO_TEST_CASE( TestInsertRightHeavy )
71 {
72 RBTree<QString> map;
73
74 QString k1 = "5";
75 QString k2 = "6";
76 QString k3 = "7";
77 QString k4 = "8";
78
79 BOOST_REQUIRE(!map.find(k1));
80 BOOST_REQUIRE_EQUAL(map.depth(), 0u);
81 BOOST_REQUIRE_EQUAL(map.total_depth(), 0u);
82 BOOST_REQUIRE_EQUAL(map.size(), 0u);
83 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 0u);
84 map.insert(k1);
85 BOOST_REQUIRE_EQUAL(map.depth(), 1u);
86 BOOST_REQUIRE_EQUAL(map.total_depth(), 1u);
87 BOOST_REQUIRE_EQUAL(map.size(), 1u);
88 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 1u);
89 BOOST_REQUIRE_THROW(map.insert(k1), ValueExistsException);
90 BOOST_REQUIRE(map.find(k1));
91 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
92
93 BOOST_REQUIRE(!map.find(k3));
94 map.insert(k2);
95 BOOST_REQUIRE_EQUAL(map.depth(), 2u);
96 BOOST_REQUIRE_EQUAL(map.total_depth(), 3u);
97 BOOST_REQUIRE_EQUAL(map.size(), 2u);
98 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
99 BOOST_REQUIRE_THROW(map.insert(k2), ValueExistsException);
100 BOOST_REQUIRE(map.find(k1));
101 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
102 BOOST_REQUIRE(map.find(k2));
103 BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
104
105 BOOST_REQUIRE(!map.find(k3));
106 map.insert(k3);
107 BOOST_WARN_EQUAL(map.depth(), 2u);
108 BOOST_WARN_EQUAL(map.total_depth(), 5u);
109 BOOST_REQUIRE_EQUAL(map.size(), 3u);
110 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
111 BOOST_REQUIRE_THROW(map.insert(k3), ValueExistsException);
112 BOOST_REQUIRE(map.find(k1));
113 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
114 BOOST_REQUIRE(map.find(k2));
115 BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
116 BOOST_REQUIRE(map.find(k3));
117 BOOST_REQUIRE_EQUAL(*map.find(k3), k3);
118
119 BOOST_REQUIRE(!map.find(k4));
120 map.insert(k4);
121 BOOST_WARN_EQUAL(map.depth(), 2u);
122 BOOST_WARN_EQUAL(map.total_depth(), 8u);
123 BOOST_REQUIRE_EQUAL(map.size(), 4u);
124 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 3u);
125 BOOST_REQUIRE_THROW(map.insert(k4), ValueExistsException);
126 BOOST_REQUIRE(map.find(k1));
127 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
128 BOOST_REQUIRE(map.find(k2));
129 BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
130 BOOST_REQUIRE(map.find(k4));
131 BOOST_REQUIRE_EQUAL(*map.find(k4), k4);
132 }
133
134 BOOST_AUTO_TEST_CASE( TestInsertBalanced )
135 {
136 RBTree<QString> map;
137
138 QString k1 = "8";
139 QString k2 = "4";
140 QString k3 = "12";
141 QString k4 = "2";
142
143 BOOST_REQUIRE(!map.find(k1));
144 BOOST_REQUIRE_EQUAL(map.depth(), 0u);
145 BOOST_REQUIRE_EQUAL(map.total_depth(), 0u);
146 BOOST_REQUIRE_EQUAL(map.size(), 0u);
147 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 0u);
148 map.insert(k1);
149 BOOST_REQUIRE_EQUAL(map.depth(), 1u);
150 BOOST_REQUIRE_EQUAL(map.total_depth(), 1u);
151 BOOST_REQUIRE_EQUAL(map.size(), 1u);
152 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 1u);
153 BOOST_REQUIRE_THROW(map.insert(k1), ValueExistsException);
154 BOOST_REQUIRE(map.find(k1));
155 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
156
157 BOOST_REQUIRE(!map.find(k3));
158 map.insert(k2);
159 BOOST_REQUIRE_EQUAL(map.depth(), 2u);
160 BOOST_REQUIRE_EQUAL(map.total_depth(), 3u);
161 BOOST_REQUIRE_EQUAL(map.size(), 2u);
162 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
163 BOOST_REQUIRE_THROW(map.insert(k2), ValueExistsException);
164 BOOST_REQUIRE(map.find(k1));
165 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
166 BOOST_REQUIRE(map.find(k2));
167 BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
168
169 BOOST_REQUIRE(!map.find(k3));
170 map.insert(k3);
171 BOOST_WARN_EQUAL(map.depth(), 2u);
172 BOOST_WARN_EQUAL(map.total_depth(), 5u);
173 BOOST_REQUIRE_EQUAL(map.size(), 3u);
174 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
175 BOOST_REQUIRE_THROW(map.insert(k3), ValueExistsException);
176 BOOST_REQUIRE(map.find(k1));
177 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
178 BOOST_REQUIRE(map.find(k2));
179 BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
180 BOOST_REQUIRE(map.find(k3));
181 BOOST_REQUIRE_EQUAL(*map.find(k3), k3);
182
183 BOOST_REQUIRE(!map.find(k4));
184 map.insert(k4);
185 BOOST_WARN_EQUAL(map.depth(), 2u);
186 BOOST_WARN_EQUAL(map.total_depth(), 8u);
187 BOOST_REQUIRE_EQUAL(map.size(), 4u);
188 BOOST_REQUIRE_EQUAL(map.optimal_depth(), 3u);
189 BOOST_REQUIRE_THROW(map.insert(k4), ValueExistsException);
190 BOOST_REQUIRE(map.find(k1));
191 BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
192 BOOST_REQUIRE(map.find(k2));
193 BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
194 BOOST_REQUIRE(map.find(k4));
195 BOOST_REQUIRE_EQUAL(*map.find(k4), k4);
196 }