Mercurial > dedupe

annotate 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
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
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
4 #include <boost/optional.hpp>
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
5 #include <cmath>
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
6 #include "ValueExistsException.hpp"
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
7
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
8 #include <QtCore/QDebug>
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
9
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
10 #define CONSISTENCY_CHECKING 1
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
11
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
12 #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
13 #define RBTREE_ASSERT(X) assert(X)
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
14 #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
15 #define RBTREE_ASSERT(X)
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
16 #endif
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
17
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
18 #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
19
fcb7a71a22c1 Make it possible to turn off asserting for the RBTree template header.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 17
diff changeset
20
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
21 template<typename Data>
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
22 class RBTree {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
23 private:
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
24 class RBTreeNode {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
25 Data data;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
26 RBTreeNode* left;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
27 RBTreeNode *right;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
28 RBTreeNode *parent;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
29 bool red;
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 enum Color { RED, BLACK };
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
32
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
33 public:
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
34 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
35 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
36 this->data = data;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
37 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
38
17
9a1825df8418 Plug memoryleaks.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 16
diff changeset
39 ~RBTreeNode()
9a1825df8418 Plug memoryleaks.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 16
diff changeset
40 {
9a1825df8418 Plug memoryleaks.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 16
diff changeset
41 delete left;
9a1825df8418 Plug memoryleaks.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 16
diff changeset
42 delete right;
9a1825df8418 Plug memoryleaks.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 16
diff changeset
43 }
9a1825df8418 Plug memoryleaks.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents: 16
diff changeset
44
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
45 void setColor(Color color)
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 red = (color == RED);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
48 }
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 Color color() const
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 return red ? RED : BLACK;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
53 }
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 RBTreeNode* grandparent()
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
56 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
57 if ((this != NULL) && (this->parent != NULL))
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
58 return this->parent->parent;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
59 else
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
60 return NULL;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
61 }
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* uncle()
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
64 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
65 RBTreeNode* g = grandparent();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
66 if (g == NULL)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
67 return NULL; // No grandparent means no uncle
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
68 if (this->parent == g->left)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
69 return g->right;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
70 else
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
71 return g->left;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
72 }
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* getRootNode()
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
75 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
76 RBTreeNode* p = this;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
77 while(p->parent)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
78 p = p->parent;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
79 return p;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
80 }
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 void rotate_left()
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
83 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
84 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
85 RBTREE_ASSERT(Q);
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
86 // Set Q to be the new root.
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
87 if (this->parent) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
88 if (this->parent->left == this) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
89 this->parent->left = Q;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
90 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
91 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
92 RBTREE_ASSERT(this->parent->right == this);
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
93 this->parent->right = Q;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
94 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
95 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
96 this->right = Q->left;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
97 if (this->right)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
98 this->right->parent = this;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
99 Q->left = this;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
100 Q->parent = this->parent;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
101 this->parent = Q;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
102 }
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 void rotate_right()
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
105 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
106 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
107 RBTREE_ASSERT(P);
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
108 //Set P to be the new root.
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
109 if (this->parent) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
110 if (this->parent->left == this) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
111 this->parent->left = P;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
112 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
113 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
114 RBTREE_ASSERT(this->parent->right == this);
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
115 this->parent->right = P;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
116 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
117 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
118 this->left = P->right;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
119 if (this->left)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
120 this->left->parent = this;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
121 P->right = this;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
122 P->parent = this->parent;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
123 this->parent = P;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
124 }
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 void insert_case5()
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
127 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
128 RBTreeNode* g = grandparent();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
129 CONSISTENCY_CHECK(this);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
130 CONSISTENCY_CHECK(g);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
131
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
132 this->parent->setColor(BLACK);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
133 g->setColor(RED);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
134 if (this == this->parent->left)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
135 g->rotate_right();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
136 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
137 RBTREE_ASSERT (this == this->parent->right);
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
138 g->rotate_left();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
139 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
140 }
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 void insert_case4()
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 RBTreeNode* g = grandparent();
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 CONSISTENCY_CHECK(this);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
147
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
148 if (!g)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
149 return;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
150 CONSISTENCY_CHECK(g);
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 RBTreeNode* n = this;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
153
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
154 if ((this == n->parent->right) && (n->parent == g->left)) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
155 n->parent->rotate_left();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
156 n = n->left;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
157 } else if ((n == n->parent->left) && (n->parent == g->right)) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
158 n->parent->rotate_right();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
159 n = n->right;
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 n->insert_case5();
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
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 void insert_case3()
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
166 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
167 RBTreeNode *u = uncle();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
168 CONSISTENCY_CHECK(this);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
169 CONSISTENCY_CHECK(u);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
170
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
171 if ((u != NULL) && (u->color() == RED)) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
172 this->parent->setColor(BLACK);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
173 u->setColor(BLACK);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
174 RBTreeNode* g;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
175 g = grandparent();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
176 g->setColor(RED);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
177 g->insert_case1();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
178 } else {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
179 insert_case4();
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 }
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 void insert_case2()
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
184 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
185 CONSISTENCY_CHECK(this);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
186 if (this->parent->color() == BLACK)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
187 return; /* Tree is still valid */
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
188 else
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
189 insert_case3();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
190 }
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 void insert_case1()
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 CONSISTENCY_CHECK(this);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
195
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
196 if (this->parent == NULL)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
197 this->setColor(BLACK);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
198 else
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
199 insert_case2();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
200 }
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 void insert(const Data& data)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
203 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
204 if (data < this->data) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
205 if (!left) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
206 left = new RBTreeNode(data);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
207 left->parent = this;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
208 left->insert_case1();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
209 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
210 else
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
211 left->insert(data);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
212 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
213 else if (data > this->data) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
214 if (!right) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
215 right = new RBTreeNode(data);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
216 right->parent = this;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
217 right->insert_case1();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
218 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
219 else
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
220 right->insert(data);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
221 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
222 else {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
223 throw ValueExistsException();
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 CONSISTENCY_CHECK(this);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
226 }
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 boost::optional<Data> find(const Data& data)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
229 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
230 if (this->data == data) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
231 return this->data;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
232 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
233 else if (data < this->data) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
234 if (left)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
235 return left->find(data);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
236 else
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
237 return boost::optional<Data>();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
238 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
239 else {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
240 if (right)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
241 return right->find(data);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
242 else
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 return boost::optional<Data>();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
246 }
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 uint size() const
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 return 1 + (left ? left->size() : 0) + (right ? right->size() : 0);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
251 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
252
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
253 uint depth() const
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
254 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
255 return 1 + std::max((left ? left->depth() : 0), (right ? right->depth() : 0));
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
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
258 uint total_depth(uint n) const
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
259 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
260 return n + (left ? left->total_depth(n + 1) : 0) + (right ? right->total_depth(n + 1) : 0);
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
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
263 bool consistent() const
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;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
274
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 }
16
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
286
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
287 bool consistent() const
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 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
307 boost::optional<Data> find(const Data& data)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
308 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
309 if (node) {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
310 return node->find(data);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
311 }
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
312 else
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
313 return boost::optional<Data>();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
314 }
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 uint size() const
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
317 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
318 if (!node)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
319 return 0;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
320 else
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
321 return node->size();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
322 }
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 uint depth() const
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
325 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
326 if (!node)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
327 return 0;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
328 return node->depth();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
329 }
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 float avg_depth() const
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
332 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
333 if (!node)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
334 return 0;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
335 return double(total_depth())/size();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
336 }
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 uint total_depth() const
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
339 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
340 if (!node)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
341 return 0;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
342 return node->total_depth(1);
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
343 }
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 uint optimal_depth() const
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
346 {
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
347 int s = size();
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
348 if (s == 0)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
349 return 0;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
350 int d = s;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
351 int targetlevel = 1;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
352 while (d >>= 1)
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
353 ++targetlevel;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
354 return targetlevel;
06166d6c083b Add configuration processing.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
355 }
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 #endif //RBTREE_HPP