Mercurial > dedupe

comparison RBTree.hpp @ 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 9a1825df8418
comparison
equal deleted inserted replaced
15:199fc63c60c1 16:06166d6c083b
1 #ifndef RBTREE_HPP
2 #define RBTREE_HPP
3
4 #include <boost/optional.hpp>
5 #include <cmath>
6 #include "ValueExistsException.hpp"
7
8 #include <QtCore/QDebug>
9
10 #define CONSISTENCY_CHECKING 0
11
12 #if CONSISTENCY_CHECKING
13 #define CONSISTENCY_CHECK(n) assert(!n || (n)->consistent())
14 #else
15 #define CONSISTENCY_CHECK(n)
16 #endif
17
18 template<typename Data>
19 class RBTree {
20 private:
21 class RBTreeNode {
22 Data data;
23 RBTreeNode* left;
24 RBTreeNode *right;
25 RBTreeNode *parent;
26 bool red;
27
28 enum Color { RED, BLACK };
29
30 public:
31 RBTreeNode(const Data& data) : left(0), right(0), parent(0), red(true)
32 {
33 this->data = data;
34 }
35
36 void setColor(Color color)
37 {
38 red = (color == RED);
39 }
40
41 Color color() const
42 {
43 return red ? RED : BLACK;
44 }
45
46 RBTreeNode* grandparent()
47 {
48 if ((this != NULL) && (this->parent != NULL))
49 return this->parent->parent;
50 else
51 return NULL;
52 }
53
54 RBTreeNode* uncle()
55 {
56 RBTreeNode* g = grandparent();
57 if (g == NULL)
58 return NULL; // No grandparent means no uncle
59 if (this->parent == g->left)
60 return g->right;
61 else
62 return g->left;
63 }
64
65 RBTreeNode* getRootNode()
66 {
67 RBTreeNode* p = this;
68 while(p->parent)
69 p = p->parent;
70 return p;
71 }
72
73 void rotate_left()
74 {
75 RBTreeNode* Q = this->right;
76 assert(Q);
77 // Set Q to be the new root.
78 if (this->parent) {
79 if (this->parent->left == this) {
80 this->parent->left = Q;
81 }
82 else {
83 assert(this->parent->right == this);
84 this->parent->right = Q;
85 }
86 }
87 this->right = Q->left;
88 if (this->right)
89 this->right->parent = this;
90 Q->left = this;
91 Q->parent = this->parent;
92 this->parent = Q;
93 }
94
95 void rotate_right()
96 {
97 RBTreeNode* P = this->left;
98 assert(P);
99 //Set P to be the new root.
100 if (this->parent) {
101 if (this->parent->left == this) {
102 this->parent->left = P;
103 }
104 else {
105 assert(this->parent->right == this);
106 this->parent->right = P;
107 }
108 }
109 this->left = P->right;
110 if (this->left)
111 this->left->parent = this;
112 P->right = this;
113 P->parent = this->parent;
114 this->parent = P;
115 }
116
117 void insert_case5()
118 {
119 RBTreeNode* g = grandparent();
120 CONSISTENCY_CHECK(this);
121 CONSISTENCY_CHECK(g);
122
123 this->parent->setColor(BLACK);
124 g->setColor(RED);
125 if (this == this->parent->left)
126 g->rotate_right();
127 else {
128 assert (this == this->parent->right);
129 g->rotate_left();
130 }
131 }
132
133 void insert_case4()
134 {
135 RBTreeNode* g = grandparent();
136
137 CONSISTENCY_CHECK(this);
138
139 if (!g)
140 return;
141 CONSISTENCY_CHECK(g);
142
143 RBTreeNode* n = this;
144
145 if ((this == n->parent->right) && (n->parent == g->left)) {
146 n->parent->rotate_left();
147 n = n->left;
148 } else if ((n == n->parent->left) && (n->parent == g->right)) {
149 n->parent->rotate_right();
150 n = n->right;
151 }
152 n->insert_case5();
153 }
154
155
156 void insert_case3()
157 {
158 RBTreeNode *u = uncle();
159 CONSISTENCY_CHECK(this);
160 CONSISTENCY_CHECK(u);
161
162 if ((u != NULL) && (u->color() == RED)) {
163 this->parent->setColor(BLACK);
164 u->setColor(BLACK);
165 RBTreeNode* g;
166 g = grandparent();
167 g->setColor(RED);
168 g->insert_case1();
169 } else {
170 insert_case4();
171 }
172 }
173
174 void insert_case2()
175 {
176 CONSISTENCY_CHECK(this);
177 if (this->parent->color() == BLACK)
178 return; /* Tree is still valid */
179 else
180 insert_case3();
181 }
182
183 void insert_case1()
184 {
185 CONSISTENCY_CHECK(this);
186
187 if (this->parent == NULL)
188 this->setColor(BLACK);
189 else
190 insert_case2();
191 }
192
193 void insert(const Data& data)
194 {
195 if (data < this->data) {
196 if (!left) {
197 left = new RBTreeNode(data);
198 left->parent = this;
199 left->insert_case1();
200 }
201 else
202 left->insert(data);
203 }
204 else if (data > this->data) {
205 if (!right) {
206 right = new RBTreeNode(data);
207 right->parent = this;
208 right->insert_case1();
209 }
210 else
211 right->insert(data);
212 }
213 else {
214 throw ValueExistsException();
215 }
216 CONSISTENCY_CHECK(this);
217 }
218
219 boost::optional<Data> find(const Data& data)
220 {
221 if (this->data == data) {
222 return this->data;
223 }
224 else if (data < this->data) {
225 if (left)
226 return left->find(data);
227 else
228 return boost::optional<Data>();
229 }
230 else {
231 if (right)
232 return right->find(data);
233 else
234 return boost::optional<Data>();
235 }
236 return boost::optional<Data>();
237 }
238
239 uint size() const
240 {
241 return 1 + (left ? left->size() : 0) + (right ? right->size() : 0);
242 }
243
244 uint depth() const
245 {
246 return 1 + std::max((left ? left->depth() : 0), (right ? right->depth() : 0));
247 }
248
249 uint total_depth(uint n) const
250 {
251 return n + (left ? left->total_depth(n + 1) : 0) + (right ? right->total_depth(n + 1) : 0);
252 }
253
254 bool consistent() const
255 {
256 bool retVal = true;
257 if (left)
258 retVal = retVal && (left->parent == this) && left->consistent();
259 if (right)
260 retVal = retVal && (right->parent == this) && right->consistent();
261 return retVal;
262 }
263
264 friend class RBTree;
265
266 };
267 RBTreeNode* node;
268 public:
269 RBTree() : node(0)
270 {
271 }
272
273 bool consistent() const
274 {
275 if (node == 0)
276 return true;
277 if (node->parent == 0 && node->consistent())
278 return true;
279 return false;
280 }
281
282 void insert(const Data& data)
283 {
284 if (node == 0) {
285 node = new RBTreeNode(data);
286 }
287 else {
288 node->insert(data);
289 }
290 node = node->getRootNode();
291 CONSISTENCY_CHECK(this);
292 }
293 boost::optional<Data> find(const Data& data)
294 {
295 if (node) {
296 return node->find(data);
297 }
298 else
299 return boost::optional<Data>();
300 }
301
302 uint size() const
303 {
304 if (!node)
305 return 0;
306 else
307 return node->size();
308 }
309
310 uint depth() const
311 {
312 if (!node)
313 return 0;
314 return node->depth();
315 }
316
317 float avg_depth() const
318 {
319 if (!node)
320 return 0;
321 return double(total_depth())/size();
322 }
323
324 uint total_depth() const
325 {
326 if (!node)
327 return 0;
328 return node->total_depth(1);
329 }
330
331 uint optimal_depth() const
332 {
333 int s = size();
334 if (s == 0)
335 return 0;
336 int d = s;
337 int targetlevel = 1;
338 while (d >>= 1)
339 ++targetlevel;
340 return targetlevel;
341 }
342 };
343
344 #endif //RBTREE_HPP