Mercurial > dedupe

comparison RBTree.hpp @ 18:fcb7a71a22c1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Make it possible to turn off asserting for the RBTree template header.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Wed, 29 Aug 2012 20:04:05 +0200
parents 9a1825df8418
children d62f708ad88b
comparison
equal deleted inserted replaced
17:9a1825df8418 18:fcb7a71a22c1
5 #include <cmath> 5 #include <cmath>
6 #include "ValueExistsException.hpp" 6 #include "ValueExistsException.hpp"
7 7
8 #include <QtCore/QDebug> 8 #include <QtCore/QDebug>
9 9
10 #define CONSISTENCY_CHECKING 0 10 #define CONSISTENCY_CHECKING 1
11 11
12 #if CONSISTENCY_CHECKING 12 #if CONSISTENCY_CHECKING
13 #define CONSISTENCY_CHECK(n) assert(!n || (n)->consistent()) 13 #define RBTREE_ASSERT(X) assert(X)
14 #else 14 #else
15 #define CONSISTENCY_CHECK(n) 15 #define RBTREE_ASSERT(X)
16 #endif 16 #endif
17
18 #define CONSISTENCY_CHECK(n) RBTREE_ASSERT(!n || (n)->consistent())
19
17 20
18 template<typename Data> 21 template<typename Data>
19 class RBTree { 22 class RBTree {
20 private: 23 private:
21 class RBTreeNode { 24 class RBTreeNode {
77 } 80 }
78 81
79 void rotate_left() 82 void rotate_left()
80 { 83 {
81 RBTreeNode* Q = this->right; 84 RBTreeNode* Q = this->right;
82 assert(Q); 85 RBTREE_ASSERT(Q);
83 // Set Q to be the new root. 86 // Set Q to be the new root.
84 if (this->parent) { 87 if (this->parent) {
85 if (this->parent->left == this) { 88 if (this->parent->left == this) {
86 this->parent->left = Q; 89 this->parent->left = Q;
87 } 90 }
88 else { 91 else {
89 assert(this->parent->right == this); 92 RBTREE_ASSERT(this->parent->right == this);
90 this->parent->right = Q; 93 this->parent->right = Q;
91 } 94 }
92 } 95 }
93 this->right = Q->left; 96 this->right = Q->left;
94 if (this->right) 97 if (this->right)
99 } 102 }
100 103
101 void rotate_right() 104 void rotate_right()
102 { 105 {
103 RBTreeNode* P = this->left; 106 RBTreeNode* P = this->left;
104 assert(P); 107 RBTREE_ASSERT(P);
105 //Set P to be the new root. 108 //Set P to be the new root.
106 if (this->parent) { 109 if (this->parent) {
107 if (this->parent->left == this) { 110 if (this->parent->left == this) {
108 this->parent->left = P; 111 this->parent->left = P;
109 } 112 }
110 else { 113 else {
111 assert(this->parent->right == this); 114 RBTREE_ASSERT(this->parent->right == this);
112 this->parent->right = P; 115 this->parent->right = P;
113 } 116 }
114 } 117 }
115 this->left = P->right; 118 this->left = P->right;
116 if (this->left) 119 if (this->left)
129 this->parent->setColor(BLACK); 132 this->parent->setColor(BLACK);
130 g->setColor(RED); 133 g->setColor(RED);
131 if (this == this->parent->left) 134 if (this == this->parent->left)
132 g->rotate_right(); 135 g->rotate_right();
133 else { 136 else {
134 assert (this == this->parent->right); 137 RBTREE_ASSERT (this == this->parent->right);
135 g->rotate_left(); 138 g->rotate_left();
136 } 139 }
137 } 140 }
138 141
139 void insert_case4() 142 void insert_case4()