Mercurial > dedupe

comparison RBTree.hpp @ 34:fda70a362ed5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Remove whitespace.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Thu, 06 Sep 2012 21:33:24 +0200
parents bf3dce7fedcb
children f711ddb56ae7
comparison
equal deleted inserted replaced
33:44a3c32dd0cb 34:fda70a362ed5
57 if ((this != NULL) && (this->parent != NULL)) 57 if ((this != NULL) && (this->parent != NULL))
58 return this->parent->parent; 58 return this->parent->parent;
59 else 59 else
60 return NULL; 60 return NULL;
61 } 61 }
62 62
63 RBTreeNode* uncle() 63 RBTreeNode* uncle()
64 { 64 {
65 RBTreeNode* g = grandparent(); 65 RBTreeNode* g = grandparent();
66 if (g == NULL) 66 if (g == NULL)
67 return NULL; // No grandparent means no uncle 67 return NULL; // No grandparent means no uncle
126 void insert_case5() 126 void insert_case5()
127 { 127 {
128 RBTreeNode* g = grandparent(); 128 RBTreeNode* g = grandparent();
129 CONSISTENCY_CHECK(this); 129 CONSISTENCY_CHECK(this);
130 CONSISTENCY_CHECK(g); 130 CONSISTENCY_CHECK(g);
131 131
132 this->parent->setColor(BLACK); 132 this->parent->setColor(BLACK);
133 g->setColor(RED); 133 g->setColor(RED);
134 if (this == this->parent->left) 134 if (this == this->parent->left)
135 g->rotate_right(); 135 g->rotate_right();
136 else { 136 else {
137 RBTREE_ASSERT (this == this->parent->right); 137 RBTREE_ASSERT (this == this->parent->right);
138 g->rotate_left(); 138 g->rotate_left();
139 } 139 }
140 } 140 }
141 141
142 void insert_case4() 142 void insert_case4()
143 { 143 {
144 RBTreeNode* g = grandparent(); 144 RBTreeNode* g = grandparent();
145 145
146 CONSISTENCY_CHECK(this); 146 CONSISTENCY_CHECK(this);
165 void insert_case3() 165 void insert_case3()
166 { 166 {
167 RBTreeNode *u = uncle(); 167 RBTreeNode *u = uncle();
168 CONSISTENCY_CHECK(this); 168 CONSISTENCY_CHECK(this);
169 CONSISTENCY_CHECK(u); 169 CONSISTENCY_CHECK(u);
170 170
171 if ((u != NULL) && (u->color() == RED)) { 171 if ((u != NULL) && (u->color() == RED)) {
172 this->parent->setColor(BLACK); 172 this->parent->setColor(BLACK);
173 u->setColor(BLACK); 173 u->setColor(BLACK);
174 RBTreeNode* g; 174 RBTreeNode* g;
175 g = grandparent(); 175 g = grandparent();
215 right = new RBTreeNode(data); 215 right = new RBTreeNode(data);
216 right->parent = this; 216 right->parent = this;
217 right->insert_case1(); 217 right->insert_case1();
218 } 218 }
219 else 219 else
220 right->insert(data); 220 right->insert(data);
221 } 221 }
222 else { 222 else {
223 throw ValueExistsException(); 223 throw ValueExistsException();
224 } 224 }
225 CONSISTENCY_CHECK(this); 225 CONSISTENCY_CHECK(this);
258 uint total_depth(uint n) const 258 uint total_depth(uint n) const
259 { 259 {
260 return n + (left ? left->total_depth(n + 1) : 0) + (right ? right->total_depth(n + 1) : 0); 260 return n + (left ? left->total_depth(n + 1) : 0) + (right ? right->total_depth(n + 1) : 0);
261 } 261 }
262 262
263 bool consistent() const 263 bool consistent() const
264 { 264 {
265 bool retVal = true; 265 bool retVal = true;
266 if (left) 266 if (left)
267 retVal = retVal && (left->parent == this) && left->consistent(); 267 retVal = retVal && (left->parent == this) && left->consistent();
268 if (right) 268 if (right)
281 281
282 ~RBTree() 282 ~RBTree()
283 { 283 {
284 delete node; 284 delete node;
285 } 285 }
286 286
287 bool consistent() const 287 bool consistent() const
288 { 288 {
289 if (node == 0) 289 if (node == 0)
290 return true; 290 return true;
291 if (node->parent == 0 && node->consistent()) 291 if (node->parent == 0 && node->consistent())
292 return true; 292 return true;