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