1 |
/* |
2 |
* Copyright (c) 2015-2016 Christian Schoenebeck |
3 |
* |
4 |
* http://www.linuxsampler.org |
5 |
* |
6 |
* This file is part of LinuxSampler and released under the same terms. |
7 |
* See README file for details. |
8 |
*/ |
9 |
|
10 |
#ifndef RTAVLTREE_H |
11 |
#define RTAVLTREE_H |
12 |
|
13 |
#include <vector> |
14 |
#include <string> |
15 |
|
16 |
#include "RTMath.h" |
17 |
|
18 |
class RTAVLTreeBase; |
19 |
|
20 |
/** |
21 |
* @brief Base class of RTAVLTree elements. |
22 |
* |
23 |
* For being able to manage elements with an RTAVLTree, this class must be |
24 |
* derived and the missing methods must be implemented. At least the following |
25 |
* two methods must be implemented in the deriving node class: |
26 |
* @code |
27 |
* bool operator==(const YourNodeType& other) const; |
28 |
* bool operator<(const YourNodeType& other) const; |
29 |
* @endcode |
30 |
* The latter two methods are mandatory and used by the RTAVLTree class to |
31 |
* compare elements with each other for being able to sort them. In case you are |
32 |
* also using one of the testing/debugging methods of the RTAVLTree class, then |
33 |
* the deriving node class also needs to implement the following method: |
34 |
* @code |
35 |
* operator std::string() const; |
36 |
* @endcode |
37 |
* The latter is responsible to convert the value of your node into a string |
38 |
* representation which is i.e. used by RTAVLTree::dumpTree() to print the |
39 |
* current structure of the AVL tree as human readable presentation to the |
40 |
* terminal. |
41 |
*/ |
42 |
class RTAVLNode { |
43 |
public: |
44 |
/** |
45 |
* Returns the current RTAVLTree this node is a member of. |
46 |
* |
47 |
* @b CAUTION: This method must only be used if RTAVLTree's template |
48 |
* parameter was set to T_SAFE = true. Using the result of this method call |
49 |
* with T_SAFE = false may result in undefined behavior! |
50 |
*/ |
51 |
RTAVLTreeBase* rtavlTree() const { return tree; } |
52 |
|
53 |
protected: |
54 |
/** |
55 |
* Initialize the members of this node. It is not necessearily required to |
56 |
* be called by the deriving class (i.e. from the constructor of the |
57 |
* deriving node class), that's because this method is automatically called |
58 |
* by the RTAVLTree class whenever an element is inserted or removed from |
59 |
* the tree. You may however call this method explicitly to initialize nodes |
60 |
* in case you encounter undeterministic behaviors (i.e. crashes) with your |
61 |
* own code. |
62 |
*/ |
63 |
inline void reset() { |
64 |
parent = children[0] = children[1] = NULL; |
65 |
prevTwin = nextTwin = this; |
66 |
balance = 0; |
67 |
twinHead = true; |
68 |
tree = NULL; |
69 |
} |
70 |
|
71 |
/** |
72 |
* Counts and returns the total amount of twins of this node (including |
73 |
* this node). A twin is a node with the exact same key value. If this node |
74 |
* does not have any other twins (that is if this node is unique), then this |
75 |
* method returns 1. |
76 |
* |
77 |
* @b CAUTION: This method is inefficient and should only be used for unit |
78 |
* tests and debugging! This method should @b NOT be used by production code! |
79 |
*/ |
80 |
int countTwins() const { |
81 |
int n = 1; |
82 |
for (RTAVLNode* twin = nextTwin; twin != this; ++n, twin = twin->nextTwin); |
83 |
return n; |
84 |
} |
85 |
|
86 |
protected: |
87 |
RTAVLNode* parent; |
88 |
RTAVLNode* children[2]; |
89 |
RTAVLNode* prevTwin; |
90 |
RTAVLNode* nextTwin; |
91 |
int balance; |
92 |
bool twinHead; |
93 |
RTAVLTreeBase* tree; ///< This is only used by RTAVLTree if T_SAFE = true |
94 |
template<class T_node, bool T_SAFE> friend class RTAVLTree; |
95 |
}; |
96 |
|
97 |
/** |
98 |
* Abstract base class for deriving tempalte class RTAVLTree. This is just |
99 |
* needed for the "tree" pointer member variable in RTAVLNode. |
100 |
*/ |
101 |
class RTAVLTreeBase { |
102 |
public: |
103 |
}; |
104 |
|
105 |
/** |
106 |
* @brief Real-time safe implementation of an AVL tree (with multi-map design). |
107 |
* |
108 |
* An AVL tree (Georgy Maximovich Adelson-Velsky & Yevgeny Mikhaylowich Landis |
109 |
* tree) is a self-balancing binary search tree, thus it is a sorted container |
110 |
* for elements. This particular RTAVLTree class uses a multi-map design. That |
111 |
* means multiple elements with the exact same key may be inserted into the |
112 |
* tree. So it does not require the individual elements to be unique and |
113 |
* inserting such duplicate elements do not replace such existing elements with |
114 |
* equal key. |
115 |
* |
116 |
* This implementation of an AVL tree provides real-time safe operations, that |
117 |
* is tree operations do not allocate or deallocate memory, they are |
118 |
* non-recursive algorithms and thus are not growing the memory stack |
119 |
* (substantially). Additionally, and in contrast to many other AVL tree |
120 |
* implementations, this implementation of an AVL tree provides |
121 |
* constant time average complexity for erase operations. |
122 |
* |
123 |
* @c T_SAFE: this boolean template class parameter defines whether the tree's |
124 |
* algorithm should be more safe but a bit slower or rather fast and less safe. |
125 |
* If T_SAFE = true then additional checks and measures will be performed when |
126 |
* calling insert() or erase(). The latter methods will then check whether the |
127 |
* passed node is already part of the tree and act accordingly to avoid |
128 |
* undefined behavior which could happen if T_SAFE = false. So if you decide to |
129 |
* set T_SAFE = false then it is your responsibility to only insert() elements |
130 |
* to this tree which are not yet members of the tree and to only erase() |
131 |
* nodes which are really members of the tree. The only real performance |
132 |
* penalty that comes with T_SAFE = true is the efficiency of the clear() method |
133 |
* which will be much slower than with T_SAFE = false. See the description of the |
134 |
* clear() method for the precise performance differences regarding T_SAFE. |
135 |
* |
136 |
* @b IMPORTANT: some of the methods of this class are only intended for unit |
137 |
* tests and debugging purposes and are not real-time safe! Those methods are |
138 |
* explicitly marked as such and must not be used in a real-time context! |
139 |
*/ |
140 |
template<class T_node, bool T_SAFE = true> |
141 |
class RTAVLTree : public RTAVLTreeBase { |
142 |
public: |
143 |
enum Dir_t { |
144 |
LEFT, |
145 |
RIGHT |
146 |
}; |
147 |
|
148 |
/** |
149 |
* Constructs an empty RTAVLTree object. |
150 |
*/ |
151 |
RTAVLTree() : root(NULL), nodesCount(0) {} |
152 |
|
153 |
/** |
154 |
* Returns true if there are no elements in this tree (that is if size() |
155 |
* is zero). |
156 |
* |
157 |
* This method is real-time safe. |
158 |
* |
159 |
* Complexity: Theta(1). |
160 |
*/ |
161 |
inline bool isEmpty() const { |
162 |
return !root; |
163 |
} |
164 |
|
165 |
/** |
166 |
* Inserts the new element @a item into the tree. Since this class uses a |
167 |
* multi-map design, it is allowed to insert multiple elements with equal |
168 |
* key. Inserting an element does never replace an existing element. Also, |
169 |
* inserting such duplicate elements into the tree does not grow the |
170 |
* tree structure complexity at all. So no matter how many duplicates are |
171 |
* inserted into the tree, those duplicates have no negative impact on the |
172 |
* efficiency of any tree operation. In other words: a tree with @c n |
173 |
* elements having @c n different (and thus entirely unique) keys is slower |
174 |
* than a tree with @c n elements having less than @c n keys (thus having |
175 |
* some non-unique keys). |
176 |
* |
177 |
* Trying to insert an item that is already part of the tree will be |
178 |
* detected and ignored. Note however, that if T_SAFE = false then this |
179 |
* detection is limited to unique elements! So if T_SAFE = false then better |
180 |
* take care to only insert a new element that is not yet member of the |
181 |
* tree. |
182 |
* |
183 |
* This method is real-time safe. |
184 |
* |
185 |
* Complexity: O(log n) on worst case. |
186 |
* |
187 |
* @param item - new element to be inserted into the tree |
188 |
*/ |
189 |
void insert(T_node& item) { |
190 |
if (T_SAFE && item.tree == this) return; |
191 |
|
192 |
if (!root) { |
193 |
item.reset(); |
194 |
if (T_SAFE) item.tree = this; |
195 |
root = &item; |
196 |
++nodesCount; |
197 |
return; |
198 |
} |
199 |
|
200 |
RTAVLNode* node = root; |
201 |
|
202 |
// walk tree from top down & attach the new item to the tree |
203 |
while (true) { |
204 |
const Relation_t relation = compare(node, &item); |
205 |
if (relation == EQUAL) { |
206 |
// there is already a node with that exact same key (if it is |
207 |
// the same key AND same item, then do nothing) |
208 |
if (node != static_cast<RTAVLNode*>(&item)) { |
209 |
// it is the same key, but different item, so insert the |
210 |
// passed item to this twin ring |
211 |
item.reset(); |
212 |
if (T_SAFE) item.tree = this; |
213 |
node->prevTwin->nextTwin = &item; |
214 |
item.prevTwin = node->prevTwin; |
215 |
item.nextTwin = node; |
216 |
item.twinHead = false; |
217 |
node->prevTwin = &item; |
218 |
++nodesCount; |
219 |
} |
220 |
return; |
221 |
} else { |
222 |
Dir_t dir = (relation == LESS) ? LEFT : RIGHT; |
223 |
if (node->children[dir]) { |
224 |
node = node->children[dir]; |
225 |
} else { |
226 |
item.reset(); |
227 |
if (T_SAFE) item.tree = this; |
228 |
node->children[dir] = &item; |
229 |
item.parent = node; |
230 |
node = &item; |
231 |
++nodesCount; |
232 |
break; |
233 |
} |
234 |
} |
235 |
} |
236 |
|
237 |
int increase = 1; |
238 |
|
239 |
// walk tree from new item's position upwards & re-balance tree |
240 |
while (node->parent && increase) { |
241 |
increase *= relationToParent(node); |
242 |
node = node->parent; |
243 |
node->balance += increase; |
244 |
increase = |
245 |
(node->balance) |
246 |
? (1 - rebalance(node)) : 0; |
247 |
} |
248 |
} |
249 |
|
250 |
/** |
251 |
* Removes the existing element @a item from the tree. |
252 |
* |
253 |
* If T_SAFE = true then calling erase() with a node that is not part of |
254 |
* this tree will simply be ignored. |
255 |
* |
256 |
* If T_SAFE = false then it is assumed that the passed @a item is really |
257 |
* a member of this tree when this method is called. There are some checks |
258 |
* even if T_SAFE = false which abort the erase operation if the |
259 |
* passed element is detected not being part of the tree, however these |
260 |
* checks do not cover all possible cases and they also require that |
261 |
* RTAVLNode::reset() was called after the element was allocated. So better |
262 |
* don't rely on those checks if T_SAFE = flase and only call erase() in this |
263 |
* case for elements which are really a member of this tree at that point. |
264 |
* |
265 |
* This method is real-time safe. |
266 |
* |
267 |
* Complexity: O(log n) on worst case, Theta(1) on average. |
268 |
* |
269 |
* @param item - element of the tree to be removed from the tree |
270 |
*/ |
271 |
void erase(T_node& item) { |
272 |
if (T_SAFE && item.tree != this) return; |
273 |
|
274 |
if (!root) { |
275 |
item.reset(); |
276 |
return; |
277 |
} |
278 |
|
279 |
// if the item is part of a twin ring and not head of the ring, then |
280 |
// just link it out from the twin ring |
281 |
if (!item.twinHead) { |
282 |
item.prevTwin->nextTwin = item.nextTwin; |
283 |
item.nextTwin->prevTwin = item.prevTwin; |
284 |
item.reset(); |
285 |
--nodesCount; |
286 |
return; |
287 |
} else if (item.nextTwin != static_cast<RTAVLNode*>(&item)) { |
288 |
// item is head of a twin ring (and ring has at least 2 twins), so |
289 |
// remove this item from the ring and make next one in the twin ring |
290 |
// head of the twin ring |
291 |
item.nextTwin->parent = item.parent; |
292 |
item.nextTwin->children[0] = item.children[0]; |
293 |
item.nextTwin->children[1] = item.children[1]; |
294 |
item.nextTwin->balance = item.balance; |
295 |
item.nextTwin->twinHead = true; |
296 |
item.prevTwin->nextTwin = item.nextTwin; |
297 |
item.nextTwin->prevTwin = item.prevTwin; |
298 |
if (item.children[0]) |
299 |
item.children[0]->parent = item.nextTwin; |
300 |
if (item.children[1]) |
301 |
item.children[1]->parent = item.nextTwin; |
302 |
*downLinkTo(&item) = item.nextTwin; |
303 |
item.reset(); |
304 |
--nodesCount; |
305 |
return; |
306 |
} |
307 |
|
308 |
RTAVLNode* node = &item; |
309 |
|
310 |
int decrease = 0; |
311 |
|
312 |
if (node->children[LEFT] && node->children[RIGHT]) { // node to be removed has exactly two children ... |
313 |
//TODO: this code branch is currently ALWAYS using the "in-order successor", one might however also pick the "in-order predecessor" in cases where the balancing situation would create a performance benefit (that decision and then using the "in-order predecessor" is not implemented here yet). |
314 |
|
315 |
// walk down to the minimum node of the right subtree ("in-order |
316 |
// successor"), hang it out and replace it with the actual node to |
317 |
// be erased, that is: |
318 |
// node -> right -> left -> left -> ... -> left -> NULL |
319 |
for (node = node->children[RIGHT]; node->children[LEFT]; node = node->children[LEFT]); |
320 |
RTAVLNode* dangling = node; |
321 |
const bool danglingIs1stChild = item.children[RIGHT] == dangling; |
322 |
|
323 |
*downLinkTo(dangling) = dangling->children[RIGHT]; |
324 |
if (dangling->children[RIGHT]) |
325 |
dangling->children[RIGHT]->parent = dangling->parent; |
326 |
|
327 |
// define start node where rebalancing shall be started later on |
328 |
node = (!danglingIs1stChild) ? dangling->parent : dangling; |
329 |
|
330 |
// replace item to be erased by the dangling node |
331 |
if (item.children[LEFT]) |
332 |
item.children[LEFT]->parent = dangling; |
333 |
if (!danglingIs1stChild) |
334 |
dangling->children[RIGHT] = item.children[RIGHT]; |
335 |
if (item.children[RIGHT]) |
336 |
item.children[RIGHT]->parent = dangling; // NOTE: this could assign dangling's parent to itself, thus we assign it next (no branch required) ... |
337 |
dangling->parent = item.parent; |
338 |
dangling->balance = item.balance; |
339 |
dangling->children[LEFT] = item.children[LEFT]; |
340 |
*downLinkTo(&item) = dangling; |
341 |
|
342 |
decrease = 1; |
343 |
for (; true; node = node->parent) { |
344 |
const bool isDangling = node == dangling; |
345 |
decrease *= ((isDangling) ? GREATER : LESS); |
346 |
node->balance -= decrease; |
347 |
if (decrease) |
348 |
decrease = (node->balance) ? rebalance(node) : 1; |
349 |
if (isDangling) break; |
350 |
} |
351 |
} else if (!node->children[LEFT] && !node->children[RIGHT]) { // node to be removed is a leaf ... |
352 |
if (root == &item) { |
353 |
root = NULL; |
354 |
nodesCount = 0; |
355 |
item.reset(); |
356 |
return; |
357 |
} |
358 |
const Dir_t dir = (node->parent->children[LEFT] == node) ? LEFT : RIGHT; |
359 |
node->parent->children[dir] = NULL; |
360 |
decrease = 1; |
361 |
// since we hooked out the node already, we must do one iteration |
362 |
// of the while loop below explicitly, becase relationToParent() |
363 |
// would not work |
364 |
decrease *= (dir == LEFT) ? LESS : GREATER; |
365 |
node = node->parent; |
366 |
node->balance -= decrease; |
367 |
decrease = (node->balance) ? rebalance(node) : 1; |
368 |
} else { // node to be removed is a branch with exactly one child ... |
369 |
RTAVLNode* child = node->children[(node->children[RIGHT]) ? RIGHT : LEFT]; |
370 |
if (node == root) { |
371 |
root = child; |
372 |
} else { |
373 |
if (node->parent->children[LEFT] == node) |
374 |
node->parent->children[LEFT] = child; |
375 |
else |
376 |
node->parent->children[RIGHT] = child; |
377 |
} |
378 |
child->parent = node->parent; |
379 |
node = child; |
380 |
decrease = 1; |
381 |
} |
382 |
|
383 |
// rebalance tree from erased item's position upwards until a tree level |
384 |
// is reached where no rebalancing is required |
385 |
while (node->parent && decrease) { |
386 |
decrease *= relationToParent(node); |
387 |
node = node->parent; |
388 |
node->balance -= decrease; |
389 |
decrease = (node->balance) ? rebalance(node) : 1; |
390 |
} |
391 |
|
392 |
--nodesCount; |
393 |
item.reset(); |
394 |
} |
395 |
|
396 |
/** |
397 |
* Returns the smallest element of this tree (element with the lowest key). |
398 |
* It assumes that this tree is not empty. If you call this method on an |
399 |
* empty tree, then a call to this method will crash. |
400 |
* |
401 |
* Since this class uses a multi-map design, there may be more than one |
402 |
* element with the same lowest key. In this case and with the current |
403 |
* implementation, the first element of those duplicates that was inserted |
404 |
* into the tree is returned. However you should not rely on this and expect |
405 |
* that any one of the duplicates may be returned here. |
406 |
* |
407 |
* This method is real-time safe. |
408 |
* |
409 |
* Complexity: Theta(log n). |
410 |
*/ |
411 |
T_node& lowest() const { |
412 |
if (!root) return *(T_node*)NULL; // crash it baby |
413 |
RTAVLNode* node = root; |
414 |
for (; node->children[LEFT]; node = node->children[LEFT]); |
415 |
return *static_cast<T_node*>(node); |
416 |
} |
417 |
|
418 |
/** |
419 |
* Returns the largest element of this tree (element with the highest key). |
420 |
* It assumes that this tree is not empty. If you call this method on an |
421 |
* empty tree, then a call to this method will crash. |
422 |
* |
423 |
* Since this class uses a multi-map design, there may be more than one |
424 |
* element with the same highest key. In this case and with the current |
425 |
* implementation, the first element of those duplicates that was inserted |
426 |
* into the tree is returned. However you should not rely on this and expect |
427 |
* that any one of the duplicates may be returned here. |
428 |
* |
429 |
* This method is real-time safe. |
430 |
* |
431 |
* Complexity: Theta(log n). |
432 |
*/ |
433 |
T_node& highest() const { |
434 |
if (!root) return *(T_node*)NULL; // crash it baby |
435 |
RTAVLNode* node = root; |
436 |
for (; node->children[RIGHT]; node = node->children[RIGHT]); |
437 |
return *static_cast<T_node*>(node); |
438 |
} |
439 |
|
440 |
/** |
441 |
* Returns successor of @a item in its tree, that is the element with the |
442 |
* next higher key value compared to @a item 's key value. |
443 |
* |
444 |
* Since this class uses a multi-map design, there may be more than one |
445 |
* element with the same key as @a item. In this case this method will |
446 |
* return the next duplicate element of @a item, or if @a item is already |
447 |
* the last duplicate of its key, then the element with the next higher key |
448 |
* value compared to @a item 's key value is returned. |
449 |
* |
450 |
* In other words: you may use this method to forward-iterate over all |
451 |
* elements of the entire tree (including duplicate elements). |
452 |
* |
453 |
* This method is real-time safe. |
454 |
* |
455 |
* Complexity: O(log n) on worst case. |
456 |
* |
457 |
* @param item - element of this tree whose successor is to be searched |
458 |
* @returns successor or NULL if @a item is the largest element of its tree |
459 |
* (and has no further duplicates) |
460 |
*/ |
461 |
static T_node* after(const T_node& item) { |
462 |
RTAVLNode* node = (RTAVLNode*)(&item); |
463 |
|
464 |
if (!node->nextTwin->twinHead) |
465 |
return node->nextTwin; |
466 |
|
467 |
if (node->children[RIGHT]) { |
468 |
for (node = node->children[RIGHT]; node->children[LEFT]; node = node->children[LEFT]); |
469 |
return static_cast<T_node*>(node); |
470 |
} else { |
471 |
while (true) { |
472 |
if (!node->parent) return NULL; |
473 |
if (node->parent->children[LEFT] == node) |
474 |
return static_cast<T_node*>(node->parent); |
475 |
node = node->parent; |
476 |
} |
477 |
} |
478 |
} |
479 |
|
480 |
/** |
481 |
* Returns predecessor of @a item in its tree, that is the element with the |
482 |
* next smaller key value compared to @a item 's key value. |
483 |
* |
484 |
* Since this class uses a multi-map design, there may be more than one |
485 |
* element with the same key as @a item. In this case this method will |
486 |
* return the previous duplicate element of @a item, or if @a item is |
487 |
* already the last duplicate of its key, then the element with the next |
488 |
* smaller key value compared to @a item 's key value is returned. |
489 |
* |
490 |
* In other words: you may use this method to backward-iterate over all |
491 |
* elements of the entire tree (including duplicate elements). |
492 |
* |
493 |
* This method is real-time safe. |
494 |
* |
495 |
* Complexity: O(log n) on worst case. |
496 |
* |
497 |
* @param item - element of this tree whose predecessor is to be searched |
498 |
* @returns predecessor or NULL if @a item is the smallest element of its |
499 |
* tree (and has no further duplicates) |
500 |
*/ |
501 |
static T_node* before(const T_node& item) { |
502 |
RTAVLNode* node = (RTAVLNode*)(&item); |
503 |
|
504 |
if (!node->twinHead) |
505 |
return node->nextTwin; |
506 |
|
507 |
if (node->children[LEFT]) { |
508 |
for (node = node->children[LEFT]; node->children[RIGHT]; node = node->children[RIGHT]); |
509 |
return static_cast<T_node*>(node); |
510 |
} else { |
511 |
while (true) { |
512 |
if (!node->parent) return NULL; |
513 |
if (node->parent->children[RIGHT] == node) |
514 |
return static_cast<T_node*>(node->parent); |
515 |
node = node->parent; |
516 |
} |
517 |
} |
518 |
} |
519 |
|
520 |
/** |
521 |
* Returns the amount of elements in this tree. |
522 |
* |
523 |
* This method is real-time safe. |
524 |
* |
525 |
* Complexity: Theta(1). |
526 |
*/ |
527 |
inline int size() const { |
528 |
return nodesCount; |
529 |
} |
530 |
|
531 |
/** |
532 |
* Removes all elements from this tree. That is size() will return @c 0 |
533 |
* after calling this method. |
534 |
* |
535 |
* @b IMPORTANT: For the precise behavior and efficiency of this method, as |
536 |
* well as saftety of subsequent other method calls, it is important which |
537 |
* value you assigned for template class parameter @c T_SAFE : |
538 |
* |
539 |
* If @c T_SAFE @c = @c false then this method does not reset the |
540 |
* invidual element nodes (for performance reasons). Due to this, after |
541 |
* calling clear(), you @b must @b not pass any of those elements to the |
542 |
* erase() method of this class, nor to any static method of this class. |
543 |
* Doing so would lead to undefined behavior. Re-inserting the elements to |
544 |
* this or to any other tree with insert() is safe though. The advantage on |
545 |
* the other hand is that clear() is extremely fast if T_SAFE = false |
546 |
* (see algorithm complexity below). |
547 |
* |
548 |
* If @c T_SAFE @c = @c true then this method will reset() @b each node of |
549 |
* this tree before removing the nodes and thus clearing the tree. The |
550 |
* advantage is that with T_SAFE = true subsequent method calls on |
551 |
* this tree are way more safe, because guaranteed checks can be performed |
552 |
* whether the respective node is already member of the tree. This safety |
553 |
* comes with the price that clear() calls will be much slower (see |
554 |
* algorithm complexity below). |
555 |
* |
556 |
* This method is real-time safe. |
557 |
* |
558 |
* Complexity: Theta(1) if T_SAFE = false, or n log n if T_SAFE = true. |
559 |
*/ |
560 |
inline void clear() { |
561 |
if (T_SAFE) { |
562 |
while (root) erase(*(T_node*)root); |
563 |
} |
564 |
root = NULL; |
565 |
nodesCount = 0; |
566 |
} |
567 |
|
568 |
/////////////////////////////////////////////////////////////////////// |
569 |
// Methods intended for unit tests & debugging purposes ... |
570 |
|
571 |
/** |
572 |
* Returns the amount of elements in this tree. You do @b NOT want to call |
573 |
* this method! You want to call size() instead! Both methods count() and |
574 |
* size() return the same value, however count() actually traverses the tree |
575 |
* each time this method is called, to really "count" the actual amount of |
576 |
* elements currently contained in the tree, size() returns a buffered |
577 |
* scalar instead. |
578 |
* |
579 |
* @b CAUTION: This method is @b NOT real-time safe! This method is just |
580 |
* intended for unit tests & debugging purposes, do not call this method in |
581 |
* a real-time context! |
582 |
*/ |
583 |
int count() const { |
584 |
int n = 0; |
585 |
count(root, n); |
586 |
return n; |
587 |
} |
588 |
|
589 |
/** |
590 |
* Returns the height of this tree, that is the largest distance between the |
591 |
* root of this tree to any of its leafs (plus one). Or in other words: |
592 |
* the largest amount of elements of this tree from top down when seen from |
593 |
* vertical perspective. |
594 |
* |
595 |
* @b CAUTION: This method is @b NOT real-time safe! This method is just |
596 |
* intended for unit tests & debugging purposes, do not call this method in |
597 |
* a real-time context! |
598 |
*/ |
599 |
int height() const { |
600 |
return height(root); |
601 |
} |
602 |
|
603 |
/** |
604 |
* Returns the width of this tree, that is the largest amount of nodes of |
605 |
* this tree from left to right when seen from horizontal perspective. |
606 |
* |
607 |
* @b CAUTION: This method is @b NOT real-time safe! This method is just |
608 |
* intended for unit tests & debugging purposes, do not call this method in |
609 |
* a real-time context! |
610 |
*/ |
611 |
int width() const { |
612 |
return width(root); |
613 |
} |
614 |
|
615 |
/** |
616 |
* Prints a human-readable graphical representation of the current tree to |
617 |
* the terminal. In case you are using this method, then your RTAVLNode |
618 |
* deriving class must also implement the following method: |
619 |
* @code |
620 |
* operator std::string() const; |
621 |
* @endcode |
622 |
* |
623 |
* @b CAUTION: This method is @b NOT real-time safe! This method is just |
624 |
* intended for unit tests & debugging purposes, do not call this method in |
625 |
* a real-time context! |
626 |
*/ |
627 |
void dumpTree() const { |
628 |
if (!root) { |
629 |
printf("(Empty Tree)\n"); |
630 |
return; |
631 |
} |
632 |
int unused; |
633 |
std::vector<std::string> buffer; |
634 |
dumpTree(root, unused, buffer); |
635 |
for (int l = 0; l < buffer.size(); ++l) |
636 |
printf("%s\n", buffer[l].c_str()); |
637 |
} |
638 |
|
639 |
/** |
640 |
* Checks the integrity of the current tree by checking whether all |
641 |
* individual down- and uplinks between all elements of this tree are equal. |
642 |
* If all bi-directional links between all nodes of this tree are correct, |
643 |
* then this method returns zero. If an inconsistency is found regarding a |
644 |
* bidirectional link between two nodes, then this method returns -1 and the |
645 |
* two arguments @a from and @a to are assigned to the two elements of the |
646 |
* tree which were found to be incorrectly linked. |
647 |
* |
648 |
* @b CAUTION: This method is @b NOT real-time safe! This method is just |
649 |
* intended for unit tests & debugging purposes, do not call this method in |
650 |
* a real-time context! |
651 |
* |
652 |
* @param from - on error, this will be assigned to the source node having |
653 |
* an invalid link |
654 |
* @param from - on error, this will be assigned to the destination node |
655 |
* having an invalid link |
656 |
* @returns 0 if integrity of tree is correct, -1 on errors |
657 |
*/ |
658 |
int assertTreeLinks(T_node*& from, T_node*& to) const { |
659 |
from = to = NULL; |
660 |
return assertTreeLinks(root, from, to); |
661 |
} |
662 |
|
663 |
/** |
664 |
* Checks the integrity of the current tree by recalculating and checking |
665 |
* the AVL balance factor of each individual element of this tree. Each |
666 |
* element of an AVL tree must always have a balance factor between -1 and |
667 |
* +1. The insert() and erase() operations of this AVL tree implementation |
668 |
* are automatically rebalancing the tree in order that the individual |
669 |
* balance factors are always in that range. So if one of the elements is |
670 |
* found by this method to have a balance factor outside that valid value |
671 |
* range, then something is wrong with the currrent tree state and that |
672 |
* would mean there is a bug. |
673 |
* |
674 |
* @b CAUTION: This method is @b NOT real-time safe! This method is just |
675 |
* intended for unit tests & debugging purposes, do not call this method in |
676 |
* a real-time context! |
677 |
* |
678 |
* @returns NULL if integrity of tree is correct, or on errors pointer to |
679 |
* node which was found to have an invalid balance factor |
680 |
*/ |
681 |
T_node* assertTreeBalance() const { |
682 |
return assertTreeBalance(root); |
683 |
} |
684 |
|
685 |
protected: |
686 |
enum Relation_t { |
687 |
LESS = -1, |
688 |
EQUAL = 0, |
689 |
GREATER = 1 |
690 |
}; |
691 |
|
692 |
enum Balance_t { |
693 |
LEFT_HEAVY = -1, |
694 |
BALANCED = 0, |
695 |
RIGHT_HEAVY = 1 |
696 |
}; |
697 |
|
698 |
inline static int LEFT_IMBALANCE(int balance) { |
699 |
return (balance < LEFT_HEAVY); |
700 |
} |
701 |
|
702 |
inline static int RIGHT_IMBALANCE(int balance) { |
703 |
return (balance > RIGHT_HEAVY); |
704 |
} |
705 |
|
706 |
inline static Dir_t opposite(Dir_t dir) { |
707 |
return Dir_t(1 - int(dir)); |
708 |
} |
709 |
|
710 |
inline static Relation_t compare(const RTAVLNode* a, const RTAVLNode* b) { |
711 |
const T_node& A = *(T_node*)a; |
712 |
const T_node& B = *(T_node*)b; |
713 |
if (B == A) return EQUAL; |
714 |
else if (B < A) return LESS; |
715 |
else return GREATER; |
716 |
} |
717 |
|
718 |
private: |
719 |
int rebalance(RTAVLNode*& node) { |
720 |
int heightChange = 0; |
721 |
if (LEFT_IMBALANCE(node->balance)) { |
722 |
if (node->children[LEFT]->balance == RIGHT_HEAVY) |
723 |
heightChange = rotateTwice(node, RIGHT); |
724 |
else |
725 |
heightChange = rotateOnce(node, RIGHT); |
726 |
} else if (RIGHT_IMBALANCE(node->balance)) { |
727 |
if (node->children[RIGHT]->balance == LEFT_HEAVY) |
728 |
heightChange = rotateTwice(node, LEFT); |
729 |
else |
730 |
heightChange = rotateOnce(node, LEFT); |
731 |
} |
732 |
return heightChange; |
733 |
} |
734 |
|
735 |
int rotateOnce(RTAVLNode*& node, Dir_t dir) { |
736 |
const Dir_t otherDir = opposite(dir); |
737 |
RTAVLNode* old = node; |
738 |
|
739 |
const int heightChange = (node->children[otherDir]->balance == 0) ? 0 : 1; |
740 |
|
741 |
node = old->children[otherDir]; |
742 |
*downLinkTo(old) = node; |
743 |
node->parent = old->parent; |
744 |
|
745 |
old->children[otherDir] = node->children[dir]; |
746 |
if (old->children[otherDir]) |
747 |
old->children[otherDir]->parent = old; |
748 |
old->parent = node; |
749 |
node->children[dir] = old; |
750 |
|
751 |
old->balance = -((dir == LEFT) ? --(node->balance) : ++(node->balance)); |
752 |
|
753 |
return heightChange; |
754 |
} |
755 |
|
756 |
int rotateTwice(RTAVLNode*& node, Dir_t dir) { |
757 |
const Dir_t otherDir = opposite(dir); |
758 |
RTAVLNode* x = node; |
759 |
RTAVLNode* z = node->children[otherDir]; |
760 |
RTAVLNode* y = z->children[dir]; |
761 |
|
762 |
node = y; |
763 |
*downLinkTo(x) = y; |
764 |
y->parent = x->parent; |
765 |
|
766 |
x->children[otherDir] = y->children[dir]; |
767 |
if (x->children[otherDir]) |
768 |
x->children[otherDir]->parent = x; |
769 |
y->children[dir] = x; |
770 |
x->parent = y; |
771 |
|
772 |
z->children[dir] = y->children[otherDir]; |
773 |
if (z->children[dir]) |
774 |
z->children[dir]->parent = z; |
775 |
y->children[otherDir] = z; |
776 |
z->parent = y; |
777 |
|
778 |
// update balances |
779 |
node->children[LEFT]->balance = -RTMath::Max(node->balance, 0); |
780 |
node->children[RIGHT]->balance = -RTMath::Min(node->balance, 0); |
781 |
node->balance = 0; |
782 |
|
783 |
// a double rotation always shortens the overall height of the tree |
784 |
return 1; |
785 |
} |
786 |
|
787 |
inline RTAVLNode** downLinkTo(const RTAVLNode* node) const { |
788 |
if (!node) return NULL; |
789 |
if (!node->parent) return (RTAVLNode**) &root; |
790 |
return (node->parent->children[LEFT] == node) |
791 |
? &node->parent->children[LEFT] |
792 |
: &node->parent->children[RIGHT]; |
793 |
} |
794 |
|
795 |
static inline Relation_t relationToParent(const RTAVLNode* node) { |
796 |
if (!node || !node->parent) return EQUAL; |
797 |
const Dir_t dir = uplinkDirFrom(node); |
798 |
return (dir == LEFT) ? LESS : GREATER; |
799 |
} |
800 |
|
801 |
static inline Dir_t uplinkDirFrom(const RTAVLNode* node) { |
802 |
return (node->parent->children[LEFT] == node) ? LEFT : RIGHT; |
803 |
} |
804 |
|
805 |
static int height(const RTAVLNode* node) { |
806 |
if (!node) return 0; |
807 |
return RTMath::Max( |
808 |
height(node->children[LEFT]), |
809 |
height(node->children[RIGHT]) |
810 |
) + 1; |
811 |
} |
812 |
|
813 |
int width(Dir_t dir) const { |
814 |
return width(root, dir); |
815 |
} |
816 |
|
817 |
static int width(const RTAVLNode* node) { |
818 |
if (!node) return 0; |
819 |
return width(node->children[LEFT]) + |
820 |
width(node->children[RIGHT]) + 1; |
821 |
} |
822 |
|
823 |
static int width(const RTAVLNode* node, Dir_t dir) { |
824 |
if (!node) return 0; |
825 |
return width(node->children[dir]); |
826 |
} |
827 |
|
828 |
static int width(const std::vector<std::string>& buffer) { |
829 |
int w = 0; |
830 |
for (int i = 0; i < buffer.size(); ++i) |
831 |
w = RTMath::Max(w, buffer[i].length()); |
832 |
return w; |
833 |
} |
834 |
|
835 |
static int height(const std::vector<std::string>& buffer) { |
836 |
return buffer.size(); |
837 |
} |
838 |
|
839 |
static void resize(std::vector<std::string>& buffer, int width, int height) { |
840 |
buffer.resize(height); |
841 |
for (int i = 0; i < height; ++i) |
842 |
buffer[i].resize(width, ' '); |
843 |
} |
844 |
|
845 |
static void count(const RTAVLNode* node, int& n) { |
846 |
if (!node) return; |
847 |
n += node->countTwins(); |
848 |
count(node->children[LEFT], n); |
849 |
count(node->children[RIGHT], n); |
850 |
} |
851 |
|
852 |
static void dumpTree(const RTAVLNode* node, int& rootX, std::vector<std::string>& buffer) { |
853 |
if (!node) { |
854 |
rootX = 0; |
855 |
return; |
856 |
} |
857 |
|
858 |
T_node& nodeImpl = *(T_node*)node; |
859 |
std::string nodeValue = (std::string)nodeImpl; |
860 |
|
861 |
int childX[2] = {}; |
862 |
std::vector<std::string> bufferChild[2]; |
863 |
if (node->children[LEFT]) |
864 |
dumpTree(node->children[LEFT], childX[LEFT], bufferChild[LEFT]); |
865 |
if (node->children[RIGHT]) |
866 |
dumpTree(node->children[RIGHT], childX[RIGHT], bufferChild[RIGHT]); |
867 |
|
868 |
const int branchSpacing = nodeValue.length(); |
869 |
const int totalW = width(bufferChild[LEFT]) + branchSpacing + width(bufferChild[RIGHT]); |
870 |
const int totalH = RTMath::Max(bufferChild[LEFT].size(), bufferChild[RIGHT].size()) + 1; |
871 |
resize(buffer, totalW, totalH); |
872 |
|
873 |
// merge bufferChild[2] -> buffer |
874 |
{ |
875 |
for (int y = 0; y < bufferChild[LEFT].size(); ++y) { |
876 |
for (int x = 0; x < bufferChild[LEFT][y].length(); ++x) { |
877 |
buffer[y+1][x] = bufferChild[LEFT][y][x]; |
878 |
} |
879 |
} |
880 |
} |
881 |
{ |
882 |
const int xOffset = width(bufferChild[LEFT]) + branchSpacing; |
883 |
for (int y = 0; y < bufferChild[RIGHT].size(); ++y) { |
884 |
for (int x = 0; x < bufferChild[RIGHT][y].length(); ++x) { |
885 |
buffer[y+1][x+xOffset] = bufferChild[RIGHT][y][x]; |
886 |
} |
887 |
} |
888 |
} |
889 |
// print child link lines |
890 |
{ |
891 |
const int from = childX[LEFT]; |
892 |
const int to = |
893 |
(node->children[RIGHT]) ? |
894 |
width(bufferChild[LEFT]) + branchSpacing + childX[RIGHT] : |
895 |
width(bufferChild[LEFT]); |
896 |
for (int x = from; x <= to; ++x) |
897 |
buffer[0][x] = (x == from || x == to) ? '+' : '-'; |
898 |
} |
899 |
// print node value |
900 |
{ |
901 |
const int xOffset = width(bufferChild[LEFT]); |
902 |
for (int i = 0; i < nodeValue.length(); ++i) |
903 |
buffer[0][xOffset+i] = nodeValue[i]; |
904 |
} |
905 |
|
906 |
rootX = width(bufferChild[LEFT]) + nodeValue.length() / 2; |
907 |
} |
908 |
|
909 |
int assertTreeLinks(const RTAVLNode* node, T_node*& from, T_node*& to) const { |
910 |
if (!node) return 0; |
911 |
if (*downLinkTo(node) != node) { |
912 |
from = (T_node*)(node->parent); |
913 |
to = (T_node*)(node); |
914 |
return -1; |
915 |
} |
916 |
if (node->children[LEFT]) { |
917 |
int res = assertTreeLinks(node->children[LEFT], from, to); |
918 |
if (res) return res; |
919 |
} |
920 |
if (node->children[RIGHT]) { |
921 |
int res = assertTreeLinks(node->children[RIGHT], from, to); |
922 |
if (res) return res; |
923 |
} |
924 |
return 0; |
925 |
} |
926 |
|
927 |
static T_node* assertTreeBalance(const RTAVLNode* node) { |
928 |
if (!node) return NULL; |
929 |
int left = height(node->children[LEFT]); |
930 |
int right = height(node->children[RIGHT]); |
931 |
int balance = right - left; |
932 |
if (balance < -1 || balance > 1) |
933 |
return (T_node*)node; |
934 |
T_node* res = assertTreeBalance(node->children[LEFT]); |
935 |
if (res) return res; |
936 |
return assertTreeBalance(node->children[RIGHT]); |
937 |
} |
938 |
|
939 |
private: |
940 |
RTAVLNode* root; |
941 |
int nodesCount; |
942 |
}; |
943 |
|
944 |
#endif // RTAVLTREE_H |