Mercurial > dedupe

annotate RBTree.hpp @ 96:c7da835ea912

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Support for prefix in commit.
author Tom Fredrik Blenning Klaussen <bfg@bfgconsult.no>
date Tue, 22 Oct 2013 14:40:08 +0200
parents b9515dc35fe4
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
1 #ifndef RBTREE_HPP
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
2 #define RBTREE_HPP
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
3
28
b2c2c2bf2bbd Refactor Exceptions into a separate directory.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 22
diff changeset
4 #include "Exception/ValueExistsException.hpp"
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
5
40
f711ddb56ae7 Sort up includes.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 34
diff changeset
6 #include <boost/optional.hpp>
31
bf3dce7fedcb Remove all references to QDebug
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 28
diff changeset
7
18
fcb7a71a22c1 Make it possible to turn off asserting for the RBTree template header.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 17
diff changeset
8 #define CONSISTENCY_CHECKING 1
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
9
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
10 #if CONSISTENCY_CHECKING
18
fcb7a71a22c1 Make it possible to turn off asserting for the RBTree template header.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 17
diff changeset
11 #define RBTREE_ASSERT(X) assert(X)
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
12 #else
18
fcb7a71a22c1 Make it possible to turn off asserting for the RBTree template header.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 17
diff changeset
13 #define RBTREE_ASSERT(X)
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
14 #endif
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
15
18
fcb7a71a22c1 Make it possible to turn off asserting for the RBTree template header.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 17
diff changeset
16 #define CONSISTENCY_CHECK(n) RBTREE_ASSERT(!n || (n)->consistent())
fcb7a71a22c1 Make it possible to turn off asserting for the RBTree template header.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 17
diff changeset
17
fcb7a71a22c1 Make it possible to turn off asserting for the RBTree template header.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 17
diff changeset
18
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
19 template<typename Data>
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
20 class RBTree {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
21 private:
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
22 class RBTreeNode {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
23 Data data;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
24 RBTreeNode* left;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
25 RBTreeNode *right;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
26 RBTreeNode *parent;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
27 bool red;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
28
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
29 enum Color { RED, BLACK };
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
30
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
31 public:
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
32 RBTreeNode(const Data& data) : left(0), right(0), parent(0), red(true)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
33 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
34 this->data = data;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
35 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
36
17
9a1825df8418 Plug memoryleaks.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 16
diff changeset
37 ~RBTreeNode()
9a1825df8418 Plug memoryleaks.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 16
diff changeset
38 {
9a1825df8418 Plug memoryleaks.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 16
diff changeset
39 delete left;
9a1825df8418 Plug memoryleaks.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 16
diff changeset
40 delete right;
9a1825df8418 Plug memoryleaks.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 16
diff changeset
41 }
9a1825df8418 Plug memoryleaks.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 16
diff changeset
42
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
43 void setColor(Color color)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
44 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
45 red = (color == RED);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
46 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
47
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
48 Color color() const
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
49 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
50 return red ? RED : BLACK;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
51 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
52
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
53 RBTreeNode* grandparent()
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
54 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
55 if ((this != NULL) && (this->parent != NULL))
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
56 return this->parent->parent;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
57 else
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
58 return NULL;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
59 }
34
fda70a362ed5 Remove whitespace.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 31
diff changeset
60
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
61 RBTreeNode* uncle()
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
62 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
63 RBTreeNode* g = grandparent();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
64 if (g == NULL)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
65 return NULL; // No grandparent means no uncle
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
66 if (this->parent == g->left)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
67 return g->right;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
68 else
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
69 return g->left;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
70 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
71
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
72 RBTreeNode* getRootNode()
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
73 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
74 RBTreeNode* p = this;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
75 while(p->parent)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
76 p = p->parent;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
77 return p;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
78 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
79
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
80 void rotate_left()
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
81 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
82 RBTreeNode* Q = this->right;
18
fcb7a71a22c1 Make it possible to turn off asserting for the RBTree template header.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 17
diff changeset
83 RBTREE_ASSERT(Q);
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
84 // Set Q to be the new root.
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
85 if (this->parent) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
86 if (this->parent->left == this) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
87 this->parent->left = Q;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
88 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
89 else {
18
fcb7a71a22c1 Make it possible to turn off asserting for the RBTree template header.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 17
diff changeset
90 RBTREE_ASSERT(this->parent->right == this);
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
91 this->parent->right = Q;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
92 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
93 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
94 this->right = Q->left;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
95 if (this->right)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
96 this->right->parent = this;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
97 Q->left = this;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
98 Q->parent = this->parent;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
99 this->parent = Q;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
100 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
101
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
102 void rotate_right()
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
103 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
104 RBTreeNode* P = this->left;
18
fcb7a71a22c1 Make it possible to turn off asserting for the RBTree template header.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 17
diff changeset
105 RBTREE_ASSERT(P);
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
106 //Set P to be the new root.
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
107 if (this->parent) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
108 if (this->parent->left == this) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
109 this->parent->left = P;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
110 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
111 else {
18
fcb7a71a22c1 Make it possible to turn off asserting for the RBTree template header.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 17
diff changeset
112 RBTREE_ASSERT(this->parent->right == this);
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
113 this->parent->right = P;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
114 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
115 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
116 this->left = P->right;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
117 if (this->left)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
118 this->left->parent = this;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
119 P->right = this;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
120 P->parent = this->parent;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
121 this->parent = P;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
122 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
123
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
124 void insert_case5()
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
125 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
126 RBTreeNode* g = grandparent();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
127 CONSISTENCY_CHECK(this);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
128 CONSISTENCY_CHECK(g);
34
fda70a362ed5 Remove whitespace.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 31
diff changeset
129
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
130 this->parent->setColor(BLACK);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
131 g->setColor(RED);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
132 if (this == this->parent->left)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
133 g->rotate_right();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
134 else {
18
fcb7a71a22c1 Make it possible to turn off asserting for the RBTree template header.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 17
diff changeset
135 RBTREE_ASSERT (this == this->parent->right);
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
136 g->rotate_left();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
137 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
138 }
34
fda70a362ed5 Remove whitespace.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 31
diff changeset
139
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
140 void insert_case4()
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
141 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
142 RBTreeNode* g = grandparent();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
143
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
144 CONSISTENCY_CHECK(this);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
145
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
146 if (!g)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
147 return;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
148 CONSISTENCY_CHECK(g);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
149
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
150 RBTreeNode* n = this;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
151
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
152 if ((this == n->parent->right) && (n->parent == g->left)) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
153 n->parent->rotate_left();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
154 n = n->left;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
155 } else if ((n == n->parent->left) && (n->parent == g->right)) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
156 n->parent->rotate_right();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
157 n = n->right;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
158 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
159 n->insert_case5();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
160 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
161
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
162
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
163 void insert_case3()
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
164 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
165 RBTreeNode *u = uncle();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
166 CONSISTENCY_CHECK(this);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
167 CONSISTENCY_CHECK(u);
34
fda70a362ed5 Remove whitespace.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 31
diff changeset
168
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
169 if ((u != NULL) && (u->color() == RED)) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
170 this->parent->setColor(BLACK);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
171 u->setColor(BLACK);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
172 RBTreeNode* g;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
173 g = grandparent();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
174 g->setColor(RED);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
175 g->insert_case1();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
176 } else {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
177 insert_case4();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
178 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
179 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
180
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
181 void insert_case2()
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
182 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
183 CONSISTENCY_CHECK(this);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
184 if (this->parent->color() == BLACK)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
185 return; /* Tree is still valid */
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
186 else
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
187 insert_case3();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
188 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
189
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
190 void insert_case1()
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
191 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
192 CONSISTENCY_CHECK(this);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
193
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
194 if (this->parent == NULL)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
195 this->setColor(BLACK);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
196 else
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
197 insert_case2();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
198 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
199
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
200 void insert(const Data& data)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
201 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
202 if (data < this->data) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
203 if (!left) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
204 left = new RBTreeNode(data);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
205 left->parent = this;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
206 left->insert_case1();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
207 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
208 else
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
209 left->insert(data);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
210 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
211 else if (data > this->data) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
212 if (!right) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
213 right = new RBTreeNode(data);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
214 right->parent = this;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
215 right->insert_case1();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
216 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
217 else
34
fda70a362ed5 Remove whitespace.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 31
diff changeset
218 right->insert(data);
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
219 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
220 else {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
221 throw ValueExistsException();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
222 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
223 CONSISTENCY_CHECK(this);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
224 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
225
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
226 boost::optional<Data> find(const Data& data)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
227 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
228 if (this->data == data) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
229 return this->data;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
230 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
231 else if (data < this->data) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
232 if (left)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
233 return left->find(data);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
234 else
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
235 return boost::optional<Data>();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
236 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
237 else {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
238 if (right)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
239 return right->find(data);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
240 else
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
241 return boost::optional<Data>();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
242 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
243 return boost::optional<Data>();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
244 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
245
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
246 uint size() const
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
247 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
248 return 1 + (left ? left->size() : 0) + (right ? right->size() : 0);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
249 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
250
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
251 uint depth() const
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
252 {
64
b9515dc35fe4 Make sure no file has greater linewidth than 80.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 61
diff changeset
253 return 1 + std::max((left ? left->depth() : 0),
b9515dc35fe4 Make sure no file has greater linewidth than 80.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 61
diff changeset
254 (right ? right->depth() : 0));
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
255 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
256
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
257 uint total_depth(uint n) const
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
258 {
64
b9515dc35fe4 Make sure no file has greater linewidth than 80.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 61
diff changeset
259 return n + (left ? left->total_depth(n + 1) : 0)
b9515dc35fe4 Make sure no file has greater linewidth than 80.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 61
diff changeset
260 + (right ? right->total_depth(n + 1) : 0);
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
261 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
262
34
fda70a362ed5 Remove whitespace.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 31
diff changeset
263 bool consistent() const
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
264 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
265 bool retVal = true;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
266 if (left)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
267 retVal = retVal && (left->parent == this) && left->consistent();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
268 if (right)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
269 retVal = retVal && (right->parent == this) && right->consistent();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
270 return retVal;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
271 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
272
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
273 friend class RBTree;
22
d62f708ad88b Cosmetics.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 18
diff changeset
274 };
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
275
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
276 RBTreeNode* node;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
277 public:
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
278 RBTree() : node(0)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
279 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
280 }
17
9a1825df8418 Plug memoryleaks.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 16
diff changeset
281
9a1825df8418 Plug memoryleaks.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 16
diff changeset
282 ~RBTree()
9a1825df8418 Plug memoryleaks.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 16
diff changeset
283 {
9a1825df8418 Plug memoryleaks.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 16
diff changeset
284 delete node;
9a1825df8418 Plug memoryleaks.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 16
diff changeset
285 }
34
fda70a362ed5 Remove whitespace.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 31
diff changeset
286
fda70a362ed5 Remove whitespace.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 31
diff changeset
287 bool consistent() const
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
288 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
289 if (node == 0)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
290 return true;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
291 if (node->parent == 0 && node->consistent())
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
292 return true;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
293 return false;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
294 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
295
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
296 void insert(const Data& data)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
297 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
298 if (node == 0) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
299 node = new RBTreeNode(data);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
300 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
301 else {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
302 node->insert(data);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
303 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
304 node = node->getRootNode();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
305 CONSISTENCY_CHECK(this);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
306 }
22
d62f708ad88b Cosmetics.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 18
diff changeset
307
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
308 boost::optional<Data> find(const Data& data)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
309 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
310 if (node) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
311 return node->find(data);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
312 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
313 else
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
314 return boost::optional<Data>();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
315 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
316
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
317 uint size() const
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
318 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
319 if (!node)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
320 return 0;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
321 else
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
322 return node->size();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
323 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
324
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
325 uint depth() const
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
326 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
327 if (!node)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
328 return 0;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
329 return node->depth();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
330 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
331
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
332 float avg_depth() const
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
333 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
334 if (!node)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
335 return 0;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
336 return double(total_depth())/size();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
337 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
338
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
339 uint total_depth() const
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
340 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
341 if (!node)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
342 return 0;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
343 return node->total_depth(1);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
344 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
345
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
346 uint optimal_depth() const
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
347 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
348 int s = size();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
349 if (s == 0)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
350 return 0;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
351 int d = s;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
352 int targetlevel = 1;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
353 while (d >>= 1)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
354 ++targetlevel;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
355 return targetlevel;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
356 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
357 };
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
358
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
359 #endif //RBTREE_HPP