source: webkit/trunk/JavaScriptCore/wtf/AVLTree.h@ 33973

Last change on this file since 33973 was 33973, checked in by Darin Adler, 17 years ago

2008-05-21 Darin Adler <Darin Adler>

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