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