1 |
/* |
/* |
2 |
* Copyright (c) 2015 Christian Schoenebeck |
* Copyright (c) 2015-2016 Christian Schoenebeck |
3 |
* |
* |
4 |
* http://www.linuxsampler.org |
* http://www.linuxsampler.org |
5 |
* |
* |
15 |
|
|
16 |
#include "RTMath.h" |
#include "RTMath.h" |
17 |
|
|
18 |
|
class RTAVLTreeBase; |
19 |
|
|
20 |
/** |
/** |
21 |
* @brief Base class of RTAVLTree elements. |
* @brief Base class of RTAVLTree elements. |
22 |
* |
* |
40 |
* terminal. |
* terminal. |
41 |
*/ |
*/ |
42 |
class RTAVLNode { |
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: |
protected: |
54 |
/** |
/** |
55 |
* Initialize the members of this node. It is not necessearily required to |
* Initialize the members of this node. It is not necessearily required to |
65 |
prevTwin = nextTwin = this; |
prevTwin = nextTwin = this; |
66 |
balance = 0; |
balance = 0; |
67 |
twinHead = true; |
twinHead = true; |
68 |
|
tree = NULL; |
69 |
} |
} |
70 |
|
|
71 |
/** |
/** |
90 |
RTAVLNode* nextTwin; |
RTAVLNode* nextTwin; |
91 |
int balance; |
int balance; |
92 |
bool twinHead; |
bool twinHead; |
93 |
template<class T_node> friend class RTAVLTree; |
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 |
/** |
/** |
120 |
* implementations, this implementation of an AVL tree provides |
* implementations, this implementation of an AVL tree provides |
121 |
* constant time average complexity for erase operations. |
* 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 |
* @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 |
* 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! |
* explicitly marked as such and must not be used in a real-time context! |
139 |
*/ |
*/ |
140 |
template<class T_node> |
template<class T_node, bool T_SAFE = true> |
141 |
class RTAVLTree { |
class RTAVLTree : public RTAVLTreeBase { |
142 |
public: |
public: |
143 |
enum Dir_t { |
enum Dir_t { |
144 |
LEFT, |
LEFT, |
175 |
* some non-unique keys). |
* some non-unique keys). |
176 |
* |
* |
177 |
* Trying to insert an item that is already part of the tree will be |
* Trying to insert an item that is already part of the tree will be |
178 |
* detected and ignored. Note however, that this detection is limited to |
* detected and ignored. Note however, that if T_SAFE = false then this |
179 |
* unique elements! So better take care to only insert a new element that |
* detection is limited to unique elements! So if T_SAFE = false then better |
180 |
* is not yet member of the tree. |
* 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. |
* This method is real-time safe. |
184 |
* |
* |
187 |
* @param item - new element to be inserted into the tree |
* @param item - new element to be inserted into the tree |
188 |
*/ |
*/ |
189 |
void insert(T_node& item) { |
void insert(T_node& item) { |
190 |
|
if (T_SAFE && item.tree == this) return; |
191 |
|
|
192 |
if (!root) { |
if (!root) { |
193 |
item.reset(); |
item.reset(); |
194 |
|
if (T_SAFE) item.tree = this; |
195 |
root = &item; |
root = &item; |
196 |
++nodesCount; |
++nodesCount; |
197 |
return; |
return; |
209 |
// it is the same key, but different item, so insert the |
// it is the same key, but different item, so insert the |
210 |
// passed item to this twin ring |
// passed item to this twin ring |
211 |
item.reset(); |
item.reset(); |
212 |
|
if (T_SAFE) item.tree = this; |
213 |
node->prevTwin->nextTwin = &item; |
node->prevTwin->nextTwin = &item; |
214 |
item.prevTwin = node->prevTwin; |
item.prevTwin = node->prevTwin; |
215 |
item.nextTwin = node; |
item.nextTwin = node; |
224 |
node = node->children[dir]; |
node = node->children[dir]; |
225 |
} else { |
} else { |
226 |
item.reset(); |
item.reset(); |
227 |
|
if (T_SAFE) item.tree = this; |
228 |
node->children[dir] = &item; |
node->children[dir] = &item; |
229 |
item.parent = node; |
item.parent = node; |
230 |
node = &item; |
node = &item; |
248 |
} |
} |
249 |
|
|
250 |
/** |
/** |
251 |
* Removes the existing element @a item from the tree. It is assumed that |
* Removes the existing element @a item from the tree. |
252 |
* the passed @a item is really a member of this tree when this method is |
* |
253 |
* called. There are some checks which abort the erase operation if the |
* 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 |
* 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 |
* checks do not cover all possible cases and they also require that |
261 |
* RTAVLNode::reset() was called after the element was allocated. So better |
* RTAVLNode::reset() was called after the element was allocated. So better |
262 |
* don't rely on those checks and only call erase() for elements which are |
* don't rely on those checks if T_SAFE = flase and only call erase() in this |
263 |
* really a member of this tree at that point. |
* case for elements which are really a member of this tree at that point. |
264 |
* |
* |
265 |
* This method is real-time safe. |
* This method is real-time safe. |
266 |
* |
* |
269 |
* @param item - element of the tree to be removed from the tree |
* @param item - element of the tree to be removed from the tree |
270 |
*/ |
*/ |
271 |
void erase(T_node& item) { |
void erase(T_node& item) { |
272 |
|
if (T_SAFE && item.tree != this) return; |
273 |
|
|
274 |
if (!root) { |
if (!root) { |
275 |
item.reset(); |
item.reset(); |
276 |
return; |
return; |
532 |
* Removes all elements from this tree. That is size() will return @c 0 |
* Removes all elements from this tree. That is size() will return @c 0 |
533 |
* after calling this method. |
* after calling this method. |
534 |
* |
* |
535 |
* @b IMPORTANT: Note that the current implementation does not reset the |
* @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 |
* 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 |
* 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. |
* 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 |
* Doing so would lead to undefined behavior. Re-inserting the elements to |
544 |
* this or to any other tree with insert() is safe though. |
* 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. |
* This method is real-time safe. |
557 |
* |
* |
558 |
* Complexity: Theta(1). |
* Complexity: Theta(1) if T_SAFE = false, or n log n if T_SAFE = true. |
559 |
*/ |
*/ |
560 |
inline void clear() { |
inline void clear() { |
561 |
|
if (T_SAFE) { |
562 |
|
while (root) erase(*(T_node*)root); |
563 |
|
} |
564 |
root = NULL; |
root = NULL; |
565 |
nodesCount = 0; |
nodesCount = 0; |
566 |
} |
} |