1 | /* |
2 | * Copyright (C) 2008 Apple Inc. All rights reserved. |
3 | * |
4 | * Based on Abstract AVL Tree Template v1.5 by Walt Karas |
5 | * <http://geocities.com/wkaras/gen_cpp/avl_tree.html>. |
6 | * |
7 | * Redistribution and use in source and binary forms, with or without |
8 | * modification, are permitted provided that the following conditions |
9 | * are met: |
10 | * |
11 | * 1. Redistributions of source code must retain the above copyright |
12 | * notice, this list of conditions and the following disclaimer. |
13 | * 2. Redistributions in binary form must reproduce the above copyright |
14 | * notice, this list of conditions and the following disclaimer in the |
15 | * documentation and/or other materials provided with the distribution. |
16 | * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of |
17 | * its contributors may be used to endorse or promote products derived |
18 | * from this software without specific prior written permission. |
19 | * |
20 | * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY |
21 | * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED |
22 | * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
23 | * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY |
24 | * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
25 | * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
26 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND |
27 | * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
28 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
29 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
30 | */ |
31 | |
32 | #ifndef AVL_TREE_H_ |
33 | #define AVL_TREE_H_ |
34 | |
35 | #include "Assertions.h" |
36 | |
37 | namespace WTF { |
38 | |
39 | // Here is the reference class for BSet. |
40 | // |
41 | // class BSet |
42 | // { |
43 | // public: |
44 | // |
45 | // class ANY_bitref |
46 | // { |
47 | // public: |
48 | // operator bool (); |
49 | // void operator = (bool b); |
50 | // }; |
51 | // |
52 | // // Does not have to initialize bits. |
53 | // BSet(); |
54 | // |
55 | // // Must return a valid value for index when 0 <= index < maxDepth |
56 | // ANY_bitref operator [] (unsigned index); |
57 | // |
58 | // // Set all bits to 1. |
59 | // void set(); |
60 | // |
61 | // // Set all bits to 0. |
62 | // void reset(); |
63 | // }; |
64 | |
65 | template<unsigned maxDepth> |
66 | class AVLTreeDefaultBSet { |
67 | public: |
68 | bool& operator[](unsigned i) { ASSERT(i < maxDepth); return m_data[i]; } |
69 | void set() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = true; } |
70 | void reset() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = false; } |
71 | |
72 | private: |
73 | bool m_data[maxDepth]; |
74 | }; |
75 | |
76 | // How to determine maxDepth: |
77 | // d Minimum number of nodes |
78 | // 2 2 |
79 | // 3 4 |
80 | // 4 7 |
81 | // 5 12 |
82 | // 6 20 |
83 | // 7 33 |
84 | // 8 54 |
85 | // 9 88 |
86 | // 10 143 |
87 | // 11 232 |
88 | // 12 376 |
89 | // 13 609 |
90 | // 14 986 |
91 | // 15 1,596 |
92 | // 16 2,583 |
93 | // 17 4,180 |
94 | // 18 6,764 |
95 | // 19 10,945 |
96 | // 20 17,710 |
97 | // 21 28,656 |
98 | // 22 46,367 |
99 | // 23 75,024 |
100 | // 24 121,392 |
101 | // 25 196,417 |
102 | // 26 317,810 |
103 | // 27 514,228 |
104 | // 28 832,039 |
105 | // 29 1,346,268 |
106 | // 30 2,178,308 |
107 | // 31 3,524,577 |
108 | // 32 5,702,886 |
109 | // 33 9,227,464 |
110 | // 34 14,930,351 |
111 | // 35 24,157,816 |
112 | // 36 39,088,168 |
113 | // 37 63,245,985 |
114 | // 38 102,334,154 |
115 | // 39 165,580,140 |
116 | // 40 267,914,295 |
117 | // 41 433,494,436 |
118 | // 42 701,408,732 |
119 | // 43 1,134,903,169 |
120 | // 44 1,836,311,902 |
121 | // 45 2,971,215,072 |
122 | // |
123 | // E.g., if, in a particular instantiation, the maximum number of nodes in a tree instance is 1,000,000, the maximum depth should be 28. |
124 | // You pick 28 because MN(28) is 832,039, which is less than or equal to 1,000,000, and MN(29) is 1,346,268, which is strictly greater than 1,000,000. |
125 | |
126 | template <class Abstractor, unsigned maxDepth = 32, class BSet = AVLTreeDefaultBSet<maxDepth> > |
127 | class AVLTree { |
128 | public: |
129 | |
130 | typedef typename Abstractor::key key; |
131 | typedef typename Abstractor::handle handle; |
132 | typedef typename Abstractor::size size; |
133 | |
134 | enum SearchType { |
135 | EQUAL = 1, |
136 | LESS = 2, |
137 | GREATER = 4, |
138 | LESS_EQUAL = EQUAL | LESS, |
139 | GREATER_EQUAL = EQUAL | GREATER |
140 | }; |
141 | |
142 | |
143 | Abstractor& abstractor() { return abs; } |
144 | |
145 | inline handle insert(handle h); |
146 | |
147 | inline handle search(key k, SearchType st = EQUAL); |
148 | inline handle search_least(); |
149 | inline handle search_greatest(); |
150 | |
151 | inline handle remove(key k); |
152 | |
153 | inline handle subst(handle new_node); |
154 | |
155 | void purge() { abs.root = null(); } |
156 | |
157 | bool is_empty() { return abs.root == null(); } |
158 | |
159 | AVLTree() { abs.root = null(); } |
160 | |
161 | class Iterator { |
162 | public: |
163 | |
164 | // Initialize depth to invalid value, to indicate iterator is |
165 | // invalid. (Depth is zero-base.) |
166 | Iterator() { depth = ~0U; } |
167 | |
168 | void start_iter(AVLTree &tree, key k, SearchType st = EQUAL) |
169 | { |
170 | // Mask of high bit in an int. |
171 | const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1); |
172 | |
173 | // Save the tree that we're going to iterate through in a |
174 | // member variable. |
175 | tree_ = &tree; |
176 | |
177 | int cmp, target_cmp; |
178 | handle h = tree_->abs.root; |
179 | unsigned d = 0; |
180 | |
181 | depth = ~0U; |
182 | |
183 | if (h == null()) |
184 | // Tree is empty. |
185 | return; |
186 | |
187 | if (st & LESS) |
188 | // Key can be greater than key of starting node. |
189 | target_cmp = 1; |
190 | else if (st & GREATER) |
191 | // Key can be less than key of starting node. |
192 | target_cmp = -1; |
193 | else |
194 | // Key must be same as key of starting node. |
195 | target_cmp = 0; |
196 | |
197 | for (;;) { |
198 | cmp = cmp_k_n(k, h); |
199 | if (cmp == 0) { |
200 | if (st & EQUAL) { |
201 | // Equal node was sought and found as starting node. |
202 | depth = d; |
203 | break; |
204 | } |
205 | cmp = -target_cmp; |
206 | } else if (target_cmp != 0) { |
207 | if (!((cmp ^ target_cmp) & MASK_HIGH_BIT)) { |
208 | // cmp and target_cmp are both negative or both positive. |
209 | depth = d; |
210 | } |
211 | } |
212 | h = cmp < 0 ? get_lt(h) : get_gt(h); |
213 | if (h == null()) |
214 | break; |
215 | branch[d] = cmp > 0; |
216 | path_h[d++] = h; |
217 | } |
218 | } |
219 | |
220 | void start_iter_least(AVLTree &tree) |
221 | { |
222 | tree_ = &tree; |
223 | |
224 | handle h = tree_->abs.root; |
225 | |
226 | depth = ~0U; |
227 | |
228 | branch.reset(); |
229 | |
230 | while (h != null()) { |
231 | if (depth != ~0U) |
232 | path_h[depth] = h; |
233 | depth++; |
234 | h = get_lt(h); |
235 | } |
236 | } |
237 | |
238 | void start_iter_greatest(AVLTree &tree) |
239 | { |
240 | tree_ = &tree; |
241 | |
242 | handle h = tree_->abs.root; |
243 | |
244 | depth = ~0U; |
245 | |
246 | branch.set(); |
247 | |
248 | while (h != null()) { |
249 | if (depth != ~0U) |
250 | path_h[depth] = h; |
251 | depth++; |
252 | h = get_gt(h); |
253 | } |
254 | } |
255 | |
256 | handle operator*() |
257 | { |
258 | if (depth == ~0U) |
259 | return null(); |
260 | |
261 | return depth == 0 ? tree_->abs.root : path_h[depth - 1]; |
262 | } |
263 | |
264 | void operator++() |
265 | { |
266 | if (depth != ~0U) { |
267 | handle h = get_gt(h: **this); |
268 | if (h == null()) { |
269 | do { |
270 | if (depth == 0) { |
271 | depth = ~0U; |
272 | break; |
273 | } |
274 | depth--; |
275 | } while (branch[depth]); |
276 | } else { |
277 | branch[depth] = true; |
278 | path_h[depth++] = h; |
279 | for (;;) { |
280 | h = get_lt(h); |
281 | if (h == null()) |
282 | break; |
283 | branch[depth] = false; |
284 | path_h[depth++] = h; |
285 | } |
286 | } |
287 | } |
288 | } |
289 | |
290 | void operator--() |
291 | { |
292 | if (depth != ~0U) { |
293 | handle h = get_lt(h: **this); |
294 | if (h == null()) |
295 | do { |
296 | if (depth == 0) { |
297 | depth = ~0U; |
298 | break; |
299 | } |
300 | depth--; |
301 | } while (!branch[depth]); |
302 | else { |
303 | branch[depth] = false; |
304 | path_h[depth++] = h; |
305 | for (;;) { |
306 | h = get_gt(h); |
307 | if (h == null()) |
308 | break; |
309 | branch[depth] = true; |
310 | path_h[depth++] = h; |
311 | } |
312 | } |
313 | } |
314 | } |
315 | |
316 | void operator++(int) { ++(*this); } |
317 | void operator--(int) { --(*this); } |
318 | |
319 | protected: |
320 | |
321 | // Tree being iterated over. |
322 | AVLTree *tree_; |
323 | |
324 | // Records a path into the tree. If branch[n] is true, indicates |
325 | // take greater branch from the nth node in the path, otherwise |
326 | // take the less branch. branch[0] gives branch from root, and |
327 | // so on. |
328 | BSet branch; |
329 | |
330 | // Zero-based depth of path into tree. |
331 | unsigned depth; |
332 | |
333 | // Handles of nodes in path from root to current node (returned by *). |
334 | handle path_h[maxDepth - 1]; |
335 | |
336 | int cmp_k_n(key k, handle h) { return tree_->abs.compare_key_node(k, h); } |
337 | int cmp_n_n(handle h1, handle h2) { return tree_->abs.compare_node_node(h1, h2); } |
338 | handle get_lt(handle h) { return tree_->abs.get_less(h); } |
339 | handle get_gt(handle h) { return tree_->abs.get_greater(h); } |
340 | handle null() { return tree_->abs.null(); } |
341 | }; |
342 | |
343 | template<typename fwd_iter> |
344 | bool build(fwd_iter p, size num_nodes) |
345 | { |
346 | if (num_nodes == 0) { |
347 | abs.root = null(); |
348 | return true; |
349 | } |
350 | |
351 | // Gives path to subtree being built. If branch[N] is false, branch |
352 | // less from the node at depth N, if true branch greater. |
353 | BSet branch; |
354 | |
355 | // If rem[N] is true, then for the current subtree at depth N, it's |
356 | // greater subtree has one more node than it's less subtree. |
357 | BSet rem; |
358 | |
359 | // Depth of root node of current subtree. |
360 | unsigned depth = 0; |
361 | |
362 | // Number of nodes in current subtree. |
363 | size num_sub = num_nodes; |
364 | |
365 | // The algorithm relies on a stack of nodes whose less subtree has |
366 | // been built, but whose right subtree has not yet been built. The |
367 | // stack is implemented as linked list. The nodes are linked |
368 | // together by having the "greater" handle of a node set to the |
369 | // next node in the list. "less_parent" is the handle of the first |
370 | // node in the list. |
371 | handle less_parent = null(); |
372 | |
373 | // h is root of current subtree, child is one of its children. |
374 | handle h, child; |
375 | |
376 | for (;;) { |
377 | while (num_sub > 2) { |
378 | // Subtract one for root of subtree. |
379 | num_sub--; |
380 | rem[depth] = !!(num_sub & 1); |
381 | branch[depth++] = false; |
382 | num_sub >>= 1; |
383 | } |
384 | |
385 | if (num_sub == 2) { |
386 | // Build a subtree with two nodes, slanting to greater. |
387 | // I arbitrarily chose to always have the extra node in the |
388 | // greater subtree when there is an odd number of nodes to |
389 | // split between the two subtrees. |
390 | |
391 | h = *p; |
392 | p++; |
393 | child = *p; |
394 | p++; |
395 | set_lt(h: child, lh: null()); |
396 | set_gt(h: child, gh: null()); |
397 | set_bf(h: child, bf: 0); |
398 | set_gt(h, gh: child); |
399 | set_lt(h, lh: null()); |
400 | set_bf(h, bf: 1); |
401 | } else { // num_sub == 1 |
402 | // Build a subtree with one node. |
403 | |
404 | h = *p; |
405 | p++; |
406 | set_lt(h, lh: null()); |
407 | set_gt(h, gh: null()); |
408 | set_bf(h, bf: 0); |
409 | } |
410 | |
411 | while (depth) { |
412 | depth--; |
413 | if (!branch[depth]) |
414 | // We've completed a less subtree. |
415 | break; |
416 | |
417 | // We've completed a greater subtree, so attach it to |
418 | // its parent (that is less than it). We pop the parent |
419 | // off the stack of less parents. |
420 | child = h; |
421 | h = less_parent; |
422 | less_parent = get_gt(h); |
423 | set_gt(h, gh: child); |
424 | // num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1 |
425 | num_sub <<= 1; |
426 | num_sub += 1 - rem[depth]; |
427 | if (num_sub & (num_sub - 1)) |
428 | // num_sub is not a power of 2 |
429 | set_bf(h, bf: 0); |
430 | else |
431 | // num_sub is a power of 2 |
432 | set_bf(h, bf: 1); |
433 | } |
434 | |
435 | if (num_sub == num_nodes) |
436 | // We've completed the full tree. |
437 | break; |
438 | |
439 | // The subtree we've completed is the less subtree of the |
440 | // next node in the sequence. |
441 | |
442 | child = h; |
443 | h = *p; |
444 | p++; |
445 | set_lt(h, lh: child); |
446 | |
447 | // Put h into stack of less parents. |
448 | set_gt(h, gh: less_parent); |
449 | less_parent = h; |
450 | |
451 | // Proceed to creating greater than subtree of h. |
452 | branch[depth] = true; |
453 | num_sub += rem[depth++]; |
454 | |
455 | } // end for (;;) |
456 | |
457 | abs.root = h; |
458 | |
459 | return true; |
460 | } |
461 | |
462 | protected: |
463 | |
464 | friend class Iterator; |
465 | |
466 | // Create a class whose sole purpose is to take advantage of |
467 | // the "empty member" optimization. |
468 | struct abs_plus_root : public Abstractor { |
469 | // The handle of the root element in the AVL tree. |
470 | handle root; |
471 | }; |
472 | |
473 | abs_plus_root abs; |
474 | |
475 | |
476 | handle get_lt(handle h) { return abs.get_less(h); } |
477 | void set_lt(handle h, handle lh) { abs.set_less(h, lh); } |
478 | |
479 | handle get_gt(handle h) { return abs.get_greater(h); } |
480 | void set_gt(handle h, handle gh) { abs.set_greater(h, gh); } |
481 | |
482 | int get_bf(handle h) { return abs.get_balance_factor(h); } |
483 | void set_bf(handle h, int bf) { abs.set_balance_factor(h, bf); } |
484 | |
485 | int cmp_k_n(key k, handle h) { return abs.compare_key_node(k, h); } |
486 | int cmp_n_n(handle h1, handle h2) { return abs.compare_node_node(h1, h2); } |
487 | |
488 | handle null() { return abs.null(); } |
489 | |
490 | private: |
491 | |
492 | // Balances subtree, returns handle of root node of subtree |
493 | // after balancing. |
494 | handle balance(handle bal_h) |
495 | { |
496 | handle deep_h; |
497 | |
498 | // Either the "greater than" or the "less than" subtree of |
499 | // this node has to be 2 levels deeper (or else it wouldn't |
500 | // need balancing). |
501 | |
502 | if (get_bf(h: bal_h) > 0) { |
503 | // "Greater than" subtree is deeper. |
504 | |
505 | deep_h = get_gt(h: bal_h); |
506 | |
507 | if (get_bf(h: deep_h) < 0) { |
508 | handle old_h = bal_h; |
509 | bal_h = get_lt(h: deep_h); |
510 | |
511 | set_gt(h: old_h, gh: get_lt(h: bal_h)); |
512 | set_lt(h: deep_h, lh: get_gt(h: bal_h)); |
513 | set_lt(h: bal_h, lh: old_h); |
514 | set_gt(h: bal_h, gh: deep_h); |
515 | |
516 | int bf = get_bf(h: bal_h); |
517 | if (bf != 0) { |
518 | if (bf > 0) { |
519 | set_bf(h: old_h, bf: -1); |
520 | set_bf(h: deep_h, bf: 0); |
521 | } else { |
522 | set_bf(h: deep_h, bf: 1); |
523 | set_bf(h: old_h, bf: 0); |
524 | } |
525 | set_bf(h: bal_h, bf: 0); |
526 | } else { |
527 | set_bf(h: old_h, bf: 0); |
528 | set_bf(h: deep_h, bf: 0); |
529 | } |
530 | } else { |
531 | set_gt(h: bal_h, gh: get_lt(h: deep_h)); |
532 | set_lt(h: deep_h, lh: bal_h); |
533 | if (get_bf(h: deep_h) == 0) { |
534 | set_bf(h: deep_h, bf: -1); |
535 | set_bf(h: bal_h, bf: 1); |
536 | } else { |
537 | set_bf(h: deep_h, bf: 0); |
538 | set_bf(h: bal_h, bf: 0); |
539 | } |
540 | bal_h = deep_h; |
541 | } |
542 | } else { |
543 | // "Less than" subtree is deeper. |
544 | |
545 | deep_h = get_lt(h: bal_h); |
546 | |
547 | if (get_bf(h: deep_h) > 0) { |
548 | handle old_h = bal_h; |
549 | bal_h = get_gt(h: deep_h); |
550 | set_lt(h: old_h, lh: get_gt(h: bal_h)); |
551 | set_gt(h: deep_h, gh: get_lt(h: bal_h)); |
552 | set_gt(h: bal_h, gh: old_h); |
553 | set_lt(h: bal_h, lh: deep_h); |
554 | |
555 | int bf = get_bf(h: bal_h); |
556 | if (bf != 0) { |
557 | if (bf < 0) { |
558 | set_bf(h: old_h, bf: 1); |
559 | set_bf(h: deep_h, bf: 0); |
560 | } else { |
561 | set_bf(h: deep_h, bf: -1); |
562 | set_bf(h: old_h, bf: 0); |
563 | } |
564 | set_bf(h: bal_h, bf: 0); |
565 | } else { |
566 | set_bf(h: old_h, bf: 0); |
567 | set_bf(h: deep_h, bf: 0); |
568 | } |
569 | } else { |
570 | set_lt(h: bal_h, lh: get_gt(h: deep_h)); |
571 | set_gt(h: deep_h, gh: bal_h); |
572 | if (get_bf(h: deep_h) == 0) { |
573 | set_bf(h: deep_h, bf: 1); |
574 | set_bf(h: bal_h, bf: -1); |
575 | } else { |
576 | set_bf(h: deep_h, bf: 0); |
577 | set_bf(h: bal_h, bf: 0); |
578 | } |
579 | bal_h = deep_h; |
580 | } |
581 | } |
582 | |
583 | return bal_h; |
584 | } |
585 | |
586 | }; |
587 | |
588 | template <class Abstractor, unsigned maxDepth, class BSet> |
589 | inline typename AVLTree<Abstractor, maxDepth, BSet>::handle |
590 | AVLTree<Abstractor, maxDepth, BSet>::insert(handle h) |
591 | { |
592 | set_lt(h, lh: null()); |
593 | set_gt(h, gh: null()); |
594 | set_bf(h, bf: 0); |
595 | |
596 | if (abs.root == null()) |
597 | abs.root = h; |
598 | else { |
599 | // Last unbalanced node encountered in search for insertion point. |
600 | handle unbal = null(); |
601 | // Parent of last unbalanced node. |
602 | handle parent_unbal = null(); |
603 | // Balance factor of last unbalanced node. |
604 | int unbal_bf; |
605 | |
606 | // Zero-based depth in tree. |
607 | unsigned depth = 0, unbal_depth = 0; |
608 | |
609 | // Records a path into the tree. If branch[n] is true, indicates |
610 | // take greater branch from the nth node in the path, otherwise |
611 | // take the less branch. branch[0] gives branch from root, and |
612 | // so on. |
613 | BSet branch; |
614 | |
615 | handle hh = abs.root; |
616 | handle parent = null(); |
617 | int cmp; |
618 | |
619 | do { |
620 | if (get_bf(h: hh) != 0) { |
621 | unbal = hh; |
622 | parent_unbal = parent; |
623 | unbal_depth = depth; |
624 | } |
625 | cmp = cmp_n_n(h1: h, h2: hh); |
626 | if (cmp == 0) |
627 | // Duplicate key. |
628 | return hh; |
629 | parent = hh; |
630 | hh = cmp < 0 ? get_lt(h: hh) : get_gt(h: hh); |
631 | branch[depth++] = cmp > 0; |
632 | } while (hh != null()); |
633 | |
634 | // Add node to insert as leaf of tree. |
635 | if (cmp < 0) |
636 | set_lt(h: parent, lh: h); |
637 | else |
638 | set_gt(h: parent, gh: h); |
639 | |
640 | depth = unbal_depth; |
641 | |
642 | if (unbal == null()) |
643 | hh = abs.root; |
644 | else { |
645 | cmp = branch[depth++] ? 1 : -1; |
646 | unbal_bf = get_bf(h: unbal); |
647 | if (cmp < 0) |
648 | unbal_bf--; |
649 | else // cmp > 0 |
650 | unbal_bf++; |
651 | hh = cmp < 0 ? get_lt(h: unbal) : get_gt(h: unbal); |
652 | if ((unbal_bf != -2) && (unbal_bf != 2)) { |
653 | // No rebalancing of tree is necessary. |
654 | set_bf(h: unbal, bf: unbal_bf); |
655 | unbal = null(); |
656 | } |
657 | } |
658 | |
659 | if (hh != null()) |
660 | while (h != hh) { |
661 | cmp = branch[depth++] ? 1 : -1; |
662 | if (cmp < 0) { |
663 | set_bf(h: hh, bf: -1); |
664 | hh = get_lt(h: hh); |
665 | } else { // cmp > 0 |
666 | set_bf(h: hh, bf: 1); |
667 | hh = get_gt(h: hh); |
668 | } |
669 | } |
670 | |
671 | if (unbal != null()) { |
672 | unbal = balance(bal_h: unbal); |
673 | if (parent_unbal == null()) |
674 | abs.root = unbal; |
675 | else { |
676 | depth = unbal_depth - 1; |
677 | cmp = branch[depth] ? 1 : -1; |
678 | if (cmp < 0) |
679 | set_lt(h: parent_unbal, lh: unbal); |
680 | else // cmp > 0 |
681 | set_gt(h: parent_unbal, gh: unbal); |
682 | } |
683 | } |
684 | } |
685 | |
686 | return h; |
687 | } |
688 | |
689 | template <class Abstractor, unsigned maxDepth, class BSet> |
690 | inline typename AVLTree<Abstractor, maxDepth, BSet>::handle |
691 | AVLTree<Abstractor, maxDepth, BSet>::search(key k, typename AVLTree<Abstractor, maxDepth, BSet>::SearchType st) |
692 | { |
693 | const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1); |
694 | |
695 | int cmp, target_cmp; |
696 | handle match_h = null(); |
697 | handle h = abs.root; |
698 | |
699 | if (st & LESS) |
700 | target_cmp = 1; |
701 | else if (st & GREATER) |
702 | target_cmp = -1; |
703 | else |
704 | target_cmp = 0; |
705 | |
706 | while (h != null()) { |
707 | cmp = cmp_k_n(k, h); |
708 | if (cmp == 0) { |
709 | if (st & EQUAL) { |
710 | match_h = h; |
711 | break; |
712 | } |
713 | cmp = -target_cmp; |
714 | } else if (target_cmp != 0) |
715 | if (!((cmp ^ target_cmp) & MASK_HIGH_BIT)) |
716 | // cmp and target_cmp are both positive or both negative. |
717 | match_h = h; |
718 | h = cmp < 0 ? get_lt(h) : get_gt(h); |
719 | } |
720 | |
721 | return match_h; |
722 | } |
723 | |
724 | template <class Abstractor, unsigned maxDepth, class BSet> |
725 | inline typename AVLTree<Abstractor, maxDepth, BSet>::handle |
726 | AVLTree<Abstractor, maxDepth, BSet>::search_least() |
727 | { |
728 | handle h = abs.root, parent = null(); |
729 | |
730 | while (h != null()) { |
731 | parent = h; |
732 | h = get_lt(h); |
733 | } |
734 | |
735 | return parent; |
736 | } |
737 | |
738 | template <class Abstractor, unsigned maxDepth, class BSet> |
739 | inline typename AVLTree<Abstractor, maxDepth, BSet>::handle |
740 | AVLTree<Abstractor, maxDepth, BSet>::search_greatest() |
741 | { |
742 | handle h = abs.root, parent = null(); |
743 | |
744 | while (h != null()) { |
745 | parent = h; |
746 | h = get_gt(h); |
747 | } |
748 | |
749 | return parent; |
750 | } |
751 | |
752 | template <class Abstractor, unsigned maxDepth, class BSet> |
753 | inline typename AVLTree<Abstractor, maxDepth, BSet>::handle |
754 | AVLTree<Abstractor, maxDepth, BSet>::remove(key k) |
755 | { |
756 | // Zero-based depth in tree. |
757 | unsigned depth = 0, rm_depth; |
758 | |
759 | // Records a path into the tree. If branch[n] is true, indicates |
760 | // take greater branch from the nth node in the path, otherwise |
761 | // take the less branch. branch[0] gives branch from root, and |
762 | // so on. |
763 | BSet branch; |
764 | |
765 | handle h = abs.root; |
766 | handle parent = null(), child; |
767 | int cmp, cmp_shortened_sub_with_path = 0; |
768 | |
769 | for (;;) { |
770 | if (h == null()) |
771 | // No node in tree with given key. |
772 | return null(); |
773 | cmp = cmp_k_n(k, h); |
774 | if (cmp == 0) |
775 | // Found node to remove. |
776 | break; |
777 | parent = h; |
778 | h = cmp < 0 ? get_lt(h) : get_gt(h); |
779 | branch[depth++] = cmp > 0; |
780 | cmp_shortened_sub_with_path = cmp; |
781 | } |
782 | handle rm = h; |
783 | handle parent_rm = parent; |
784 | rm_depth = depth; |
785 | |
786 | // If the node to remove is not a leaf node, we need to get a |
787 | // leaf node, or a node with a single leaf as its child, to put |
788 | // in the place of the node to remove. We will get the greatest |
789 | // node in the less subtree (of the node to remove), or the least |
790 | // node in the greater subtree. We take the leaf node from the |
791 | // deeper subtree, if there is one. |
792 | |
793 | if (get_bf(h) < 0) { |
794 | child = get_lt(h); |
795 | branch[depth] = false; |
796 | cmp = -1; |
797 | } else { |
798 | child = get_gt(h); |
799 | branch[depth] = true; |
800 | cmp = 1; |
801 | } |
802 | depth++; |
803 | |
804 | if (child != null()) { |
805 | cmp = -cmp; |
806 | do { |
807 | parent = h; |
808 | h = child; |
809 | if (cmp < 0) { |
810 | child = get_lt(h); |
811 | branch[depth] = false; |
812 | } else { |
813 | child = get_gt(h); |
814 | branch[depth] = true; |
815 | } |
816 | depth++; |
817 | } while (child != null()); |
818 | |
819 | if (parent == rm) |
820 | // Only went through do loop once. Deleted node will be replaced |
821 | // in the tree structure by one of its immediate children. |
822 | cmp_shortened_sub_with_path = -cmp; |
823 | else |
824 | cmp_shortened_sub_with_path = cmp; |
825 | |
826 | // Get the handle of the opposite child, which may not be null. |
827 | child = cmp > 0 ? get_lt(h) : get_gt(h); |
828 | } |
829 | |
830 | if (parent == null()) |
831 | // There were only 1 or 2 nodes in this tree. |
832 | abs.root = child; |
833 | else if (cmp_shortened_sub_with_path < 0) |
834 | set_lt(h: parent, lh: child); |
835 | else |
836 | set_gt(h: parent, gh: child); |
837 | |
838 | // "path" is the parent of the subtree being eliminated or reduced |
839 | // from a depth of 2 to 1. If "path" is the node to be removed, we |
840 | // set path to the node we're about to poke into the position of the |
841 | // node to be removed. |
842 | handle path = parent == rm ? h : parent; |
843 | |
844 | if (h != rm) { |
845 | // Poke in the replacement for the node to be removed. |
846 | set_lt(h, lh: get_lt(h: rm)); |
847 | set_gt(h, gh: get_gt(h: rm)); |
848 | set_bf(h, bf: get_bf(h: rm)); |
849 | if (parent_rm == null()) |
850 | abs.root = h; |
851 | else { |
852 | depth = rm_depth - 1; |
853 | if (branch[depth]) |
854 | set_gt(h: parent_rm, gh: h); |
855 | else |
856 | set_lt(h: parent_rm, lh: h); |
857 | } |
858 | } |
859 | |
860 | if (path != null()) { |
861 | // Create a temporary linked list from the parent of the path node |
862 | // to the root node. |
863 | h = abs.root; |
864 | parent = null(); |
865 | depth = 0; |
866 | while (h != path) { |
867 | if (branch[depth++]) { |
868 | child = get_gt(h); |
869 | set_gt(h, gh: parent); |
870 | } else { |
871 | child = get_lt(h); |
872 | set_lt(h, lh: parent); |
873 | } |
874 | parent = h; |
875 | h = child; |
876 | } |
877 | |
878 | // Climb from the path node to the root node using the linked |
879 | // list, restoring the tree structure and rebalancing as necessary. |
880 | bool reduced_depth = true; |
881 | int bf; |
882 | cmp = cmp_shortened_sub_with_path; |
883 | for (;;) { |
884 | if (reduced_depth) { |
885 | bf = get_bf(h); |
886 | if (cmp < 0) |
887 | bf++; |
888 | else // cmp > 0 |
889 | bf--; |
890 | if ((bf == -2) || (bf == 2)) { |
891 | h = balance(bal_h: h); |
892 | bf = get_bf(h); |
893 | } else |
894 | set_bf(h, bf); |
895 | reduced_depth = (bf == 0); |
896 | } |
897 | if (parent == null()) |
898 | break; |
899 | child = h; |
900 | h = parent; |
901 | cmp = branch[--depth] ? 1 : -1; |
902 | if (cmp < 0) { |
903 | parent = get_lt(h); |
904 | set_lt(h, lh: child); |
905 | } else { |
906 | parent = get_gt(h); |
907 | set_gt(h, gh: child); |
908 | } |
909 | } |
910 | abs.root = h; |
911 | } |
912 | |
913 | return rm; |
914 | } |
915 | |
916 | template <class Abstractor, unsigned maxDepth, class BSet> |
917 | inline typename AVLTree<Abstractor, maxDepth, BSet>::handle |
918 | AVLTree<Abstractor, maxDepth, BSet>::subst(handle new_node) |
919 | { |
920 | handle h = abs.root; |
921 | handle parent = null(); |
922 | int cmp, last_cmp; |
923 | |
924 | /* Search for node already in tree with same key. */ |
925 | for (;;) { |
926 | if (h == null()) |
927 | /* No node in tree with same key as new node. */ |
928 | return null(); |
929 | cmp = cmp_n_n(h1: new_node, h2: h); |
930 | if (cmp == 0) |
931 | /* Found the node to substitute new one for. */ |
932 | break; |
933 | last_cmp = cmp; |
934 | parent = h; |
935 | h = cmp < 0 ? get_lt(h) : get_gt(h); |
936 | } |
937 | |
938 | /* Copy tree housekeeping fields from node in tree to new node. */ |
939 | set_lt(h: new_node, lh: get_lt(h)); |
940 | set_gt(h: new_node, gh: get_gt(h)); |
941 | set_bf(h: new_node, bf: get_bf(h)); |
942 | |
943 | if (parent == null()) |
944 | /* New node is also new root. */ |
945 | abs.root = new_node; |
946 | else { |
947 | /* Make parent point to new node. */ |
948 | if (last_cmp < 0) |
949 | set_lt(h: parent, lh: new_node); |
950 | else |
951 | set_gt(h: parent, gh: new_node); |
952 | } |
953 | |
954 | return h; |
955 | } |
956 | |
957 | } |
958 | |
959 | #endif |
960 | |