AVLTree.h revision 635860845790a19bf50bbc51ba8fb66a96dde068
18e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project/* 28e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Copyright (C) 2008 Apple Inc. All rights reserved. 38e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 48e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Based on Abstract AVL Tree Template v1.5 by Walt Karas 58e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * <http://geocities.com/wkaras/gen_cpp/avl_tree.html>. 68e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 78e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * Redistribution and use in source and binary forms, with or without 88e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * modification, are permitted provided that the following conditions 98e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * are met: 108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 1. Redistributions of source code must retain the above copyright 128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * notice, this list of conditions and the following disclaimer. 138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 2. Redistributions in binary form must reproduce the above copyright 148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * notice, this list of conditions and the following disclaimer in the 158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * documentation and/or other materials provided with the distribution. 168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of 178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * its contributors may be used to endorse or promote products derived 188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * from this software without specific prior written permission. 198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * 208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project */ 318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 32635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project#ifndef AVL_TREE_H_ 33635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project#define AVL_TREE_H_ 348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include "Assertions.h" 368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 37635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Projectnamespace WTF { 388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// Here is the reference class for BSet. 408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// class BSet 428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// { 438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// public: 448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// class ANY_bitref 468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// { 478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// public: 488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// operator bool (); 498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// void operator = (bool b); 508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// }; 518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// // Does not have to initialize bits. 538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// BSet(); 548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// // Must return a valid value for index when 0 <= index < maxDepth 568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// ANY_bitref operator [] (unsigned index); 578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// // Set all bits to 1. 598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// void set(); 608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// // Set all bits to 0. 628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// void reset(); 638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// }; 648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projecttemplate<unsigned maxDepth> 668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectclass AVLTreeDefaultBSet { 678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectpublic: 688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool& operator[](unsigned i) { ASSERT(i < maxDepth); return m_data[i]; } 698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void set() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = true; } 708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void reset() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = false; } 718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectprivate: 738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool m_data[maxDepth]; 748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project}; 758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// How to determine maxDepth: 778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// d Minimum number of nodes 788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 2 2 798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 3 4 808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 4 7 818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 5 12 828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 6 20 838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 7 33 848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 8 54 858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 9 88 868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 10 143 878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 11 232 888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 12 376 898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 13 609 908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 14 986 918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 15 1,596 928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 16 2,583 938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 17 4,180 948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 18 6,764 958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 19 10,945 968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 20 17,710 978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 21 28,656 988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 22 46,367 998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 23 75,024 1008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 24 121,392 1018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 25 196,417 1028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 26 317,810 1038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 27 514,228 1048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 28 832,039 1058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 29 1,346,268 1068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 30 2,178,308 1078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 31 3,524,577 1088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 32 5,702,886 1098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 33 9,227,464 1108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 34 14,930,351 1118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 35 24,157,816 1128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 36 39,088,168 1138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 37 63,245,985 1148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 38 102,334,154 1158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 39 165,580,140 1168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 40 267,914,295 1178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 41 433,494,436 1188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 42 701,408,732 1198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 43 1,134,903,169 1208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 44 1,836,311,902 1218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 45 2,971,215,072 1228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 1238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 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. 1248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 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. 1258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projecttemplate <class Abstractor, unsigned maxDepth = 32, class BSet = AVLTreeDefaultBSet<maxDepth> > 1278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectclass AVLTree { 1288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectpublic: 1298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef typename Abstractor::key key; 1318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef typename Abstractor::handle handle; 1328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef typename Abstractor::size size; 1338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project enum SearchType { 1358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project EQUAL = 1, 1368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project LESS = 2, 1378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project GREATER = 4, 1388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project LESS_EQUAL = EQUAL | LESS, 1398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project GREATER_EQUAL = EQUAL | GREATER 1408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 1418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Abstractor& abstractor() { return abs; } 1448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline handle insert(handle h); 1468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline handle search(key k, SearchType st = EQUAL); 1488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline handle search_least(); 1498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline handle search_greatest(); 1508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline handle remove(key k); 1528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project inline handle subst(handle new_node); 1548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void purge() { abs.root = null(); } 1568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool is_empty() { return abs.root == null(); } 1588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project AVLTree() { abs.root = null(); } 1608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project class Iterator { 1628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 1638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Initialize depth to invalid value, to indicate iterator is 1658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // invalid. (Depth is zero-base.) 1668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Iterator() { depth = ~0U; } 1678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void start_iter(AVLTree &tree, key k, SearchType st = EQUAL) 1698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Mask of high bit in an int. 1718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1); 1728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Save the tree that we're going to iterate through in a 1748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // member variable. 1758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project tree_ = &tree; 1768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int cmp, target_cmp; 1788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle h = tree_->abs.root; 1798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unsigned d = 0; 1808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project depth = ~0U; 1828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (h == null()) 1848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Tree is empty. 1858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return; 1868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (st & LESS) 1888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Key can be greater than key of starting node. 1898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project target_cmp = 1; 1908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else if (st & GREATER) 1918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Key can be less than key of starting node. 1928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project target_cmp = -1; 1938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 1948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Key must be same as key of starting node. 1958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project target_cmp = 0; 1968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (;;) { 1988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cmp = cmp_k_n(k, h); 1998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (cmp == 0) { 2008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (st & EQUAL) { 2018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Equal node was sought and found as starting node. 2028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project depth = d; 2038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project break; 2048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cmp = -target_cmp; 206635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project } else if (target_cmp != 0) { 207635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project if (!((cmp ^ target_cmp) & MASK_HIGH_BIT)) { 2088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // cmp and target_cmp are both negative or both positive. 2098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project depth = d; 210635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project } 2118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 212635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project h = cmp < 0 ? get_lt(h) : get_gt(h); 213635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project if (h == null()) 214635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project break; 215635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project branch[d] = cmp > 0; 216635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project path_h[d++] = h; 2178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 218635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project } 2198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void start_iter_least(AVLTree &tree) 2218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project tree_ = &tree; 2238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle h = tree_->abs.root; 2258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project depth = ~0U; 2278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project branch.reset(); 2298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project while (h != null()) { 2318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (depth != ~0U) 2328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project path_h[depth] = h; 2338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project depth++; 2348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project h = get_lt(h); 2358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void start_iter_greatest(AVLTree &tree) 2398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project tree_ = &tree; 2418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle h = tree_->abs.root; 2438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project depth = ~0U; 2458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project branch.set(); 2478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project while (h != null()) { 2498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (depth != ~0U) 2508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project path_h[depth] = h; 2518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project depth++; 2528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project h = get_gt(h); 2538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle operator*() 2578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (depth == ~0U) 2598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return null(); 2608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return depth == 0 ? tree_->abs.root : path_h[depth - 1]; 2628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void operator++() 2658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (depth != ~0U) { 2678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle h = get_gt(**this); 2688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (h == null()) { 2698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project do { 2708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (depth == 0) { 2718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project depth = ~0U; 2728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project break; 2738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project depth--; 2758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } while (branch[depth]); 2768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 2778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project branch[depth] = true; 2788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project path_h[depth++] = h; 2798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (;;) { 2808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project h = get_lt(h); 2818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (h == null()) 2828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project break; 2838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project branch[depth] = false; 2848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project path_h[depth++] = h; 2858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void operator--() 2918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 2928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (depth != ~0U) { 2938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle h = get_lt(**this); 2948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (h == null()) 2958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project do { 2968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (depth == 0) { 2978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project depth = ~0U; 2988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project break; 2998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project depth--; 3018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } while (!branch[depth]); 3028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else { 3038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project branch[depth] = false; 3048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project path_h[depth++] = h; 3058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (;;) { 3068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project h = get_gt(h); 3078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (h == null()) 3088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project break; 3098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project branch[depth] = true; 3108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project path_h[depth++] = h; 3118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void operator++(int) { ++(*this); } 3178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void operator--(int) { --(*this); } 3188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project protected: 3208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Tree being iterated over. 3228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project AVLTree *tree_; 3238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Records a path into the tree. If branch[n] is true, indicates 3258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // take greater branch from the nth node in the path, otherwise 3268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // take the less branch. branch[0] gives branch from root, and 3278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // so on. 3288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project BSet branch; 3298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Zero-based depth of path into tree. 3318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unsigned depth; 3328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Handles of nodes in path from root to current node (returned by *). 3348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle path_h[maxDepth - 1]; 3358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int cmp_k_n(key k, handle h) { return tree_->abs.compare_key_node(k, h); } 3378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int cmp_n_n(handle h1, handle h2) { return tree_->abs.compare_node_node(h1, h2); } 3388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle get_lt(handle h) { return tree_->abs.get_less(h); } 3398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle get_gt(handle h) { return tree_->abs.get_greater(h); } 3408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle null() { return tree_->abs.null(); } 3418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 3428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<typename fwd_iter> 3448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool build(fwd_iter p, size num_nodes) 3458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 3468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (num_nodes == 0) { 3478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project abs.root = null(); 3488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return true; 3498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Gives path to subtree being built. If branch[N] is false, branch 3528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // less from the node at depth N, if true branch greater. 3538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project BSet branch; 3548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // If rem[N] is true, then for the current subtree at depth N, it's 3568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // greater subtree has one more node than it's less subtree. 3578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project BSet rem; 3588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Depth of root node of current subtree. 3608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unsigned depth = 0; 3618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Number of nodes in current subtree. 3638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project size num_sub = num_nodes; 3648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // The algorithm relies on a stack of nodes whose less subtree has 3668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // been built, but whose right subtree has not yet been built. The 3678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // stack is implemented as linked list. The nodes are linked 3688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // together by having the "greater" handle of a node set to the 3698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // next node in the list. "less_parent" is the handle of the first 3708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // node in the list. 3718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle less_parent = null(); 3728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // h is root of current subtree, child is one of its children. 3748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle h, child; 3758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (;;) { 3778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project while (num_sub > 2) { 3788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Subtract one for root of subtree. 3798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project num_sub--; 3808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project rem[depth] = !!(num_sub & 1); 3818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project branch[depth++] = false; 3828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project num_sub >>= 1; 3838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 3848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (num_sub == 2) { 3868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Build a subtree with two nodes, slanting to greater. 3878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // I arbitrarily chose to always have the extra node in the 3888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // greater subtree when there is an odd number of nodes to 3898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // split between the two subtrees. 3908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project h = *p; 3928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project p++; 3938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project child = *p; 3948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project p++; 3958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_lt(child, null()); 3968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(child, null()); 3978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(child, 0); 3988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(h, child); 3998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_lt(h, null()); 4008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(h, 1); 4018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { // num_sub == 1 4028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Build a subtree with one node. 4038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project h = *p; 4058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project p++; 4068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_lt(h, null()); 4078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(h, null()); 4088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(h, 0); 4098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project while (depth) { 4128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project depth--; 4138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!branch[depth]) 4148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // We've completed a less subtree. 4158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project break; 4168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // We've completed a greater subtree, so attach it to 4188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // its parent (that is less than it). We pop the parent 4198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // off the stack of less parents. 4208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project child = h; 4218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project h = less_parent; 4228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project less_parent = get_gt(h); 4238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(h, child); 4248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1 4258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project num_sub <<= 1; 4268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project num_sub += 1 - rem[depth]; 4278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (num_sub & (num_sub - 1)) 4288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // num_sub is not a power of 2 4298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(h, 0); 4308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 4318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // num_sub is a power of 2 4328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(h, 1); 4338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (num_sub == num_nodes) 4368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // We've completed the full tree. 4378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project break; 4388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // The subtree we've completed is the less subtree of the 4408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // next node in the sequence. 4418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project child = h; 4438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project h = *p; 4448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project p++; 4458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_lt(h, child); 4468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Put h into stack of less parents. 4488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(h, less_parent); 4498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project less_parent = h; 4508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Proceed to creating greater than subtree of h. 4528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project branch[depth] = true; 4538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project num_sub += rem[depth++]; 4548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } // end for (;;) 4568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project abs.root = h; 4588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return true; 4608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 4618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectprotected: 4638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project friend class Iterator; 4658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Create a class whose sole purpose is to take advantage of 4678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // the "empty member" optimization. 4688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project struct abs_plus_root : public Abstractor { 4698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // The handle of the root element in the AVL tree. 4708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle root; 4718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 4728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project abs_plus_root abs; 4748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle get_lt(handle h) { return abs.get_less(h); } 4778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void set_lt(handle h, handle lh) { abs.set_less(h, lh); } 4788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle get_gt(handle h) { return abs.get_greater(h); } 4808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void set_gt(handle h, handle gh) { abs.set_greater(h, gh); } 4818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int get_bf(handle h) { return abs.get_balance_factor(h); } 4838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void set_bf(handle h, int bf) { abs.set_balance_factor(h, bf); } 4848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int cmp_k_n(key k, handle h) { return abs.compare_key_node(k, h); } 4868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int cmp_n_n(handle h1, handle h2) { return abs.compare_node_node(h1, h2); } 4878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle null() { return abs.null(); } 4898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectprivate: 4918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Balances subtree, returns handle of root node of subtree 4938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // after balancing. 4948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle balance(handle bal_h) 4958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 4968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle deep_h; 4978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 4988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Either the "greater than" or the "less than" subtree of 4998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // this node has to be 2 levels deeper (or else it wouldn't 5008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // need balancing). 5018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (get_bf(bal_h) > 0) { 5038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // "Greater than" subtree is deeper. 5048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deep_h = get_gt(bal_h); 5068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (get_bf(deep_h) < 0) { 5088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle old_h = bal_h; 5098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bal_h = get_lt(deep_h); 5108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(old_h, get_lt(bal_h)); 5128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_lt(deep_h, get_gt(bal_h)); 5138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_lt(bal_h, old_h); 5148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(bal_h, deep_h); 5158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int bf = get_bf(bal_h); 5178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (bf != 0) { 5188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (bf > 0) { 5198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(old_h, -1); 5208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(deep_h, 0); 5218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 5228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(deep_h, 1); 5238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(old_h, 0); 5248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(bal_h, 0); 5268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 5278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(old_h, 0); 5288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(deep_h, 0); 5298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 5318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(bal_h, get_lt(deep_h)); 5328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_lt(deep_h, bal_h); 5338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (get_bf(deep_h) == 0) { 5348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(deep_h, -1); 5358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(bal_h, 1); 5368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 5378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(deep_h, 0); 5388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(bal_h, 0); 5398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bal_h = deep_h; 5418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 5438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // "Less than" subtree is deeper. 5448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project deep_h = get_lt(bal_h); 5468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (get_bf(deep_h) > 0) { 5488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle old_h = bal_h; 5498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bal_h = get_gt(deep_h); 5508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_lt(old_h, get_gt(bal_h)); 5518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(deep_h, get_lt(bal_h)); 5528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(bal_h, old_h); 5538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_lt(bal_h, deep_h); 5548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int bf = get_bf(bal_h); 5568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (bf != 0) { 5578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (bf < 0) { 5588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(old_h, 1); 5598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(deep_h, 0); 5608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 5618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(deep_h, -1); 5628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(old_h, 0); 5638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(bal_h, 0); 5658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 5668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(old_h, 0); 5678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(deep_h, 0); 5688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 5708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_lt(bal_h, get_gt(deep_h)); 5718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(deep_h, bal_h); 5728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (get_bf(deep_h) == 0) { 5738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(deep_h, 1); 5748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(bal_h, -1); 5758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 5768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(deep_h, 0); 5778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(bal_h, 0); 5788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bal_h = deep_h; 5808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return bal_h; 5848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 5858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project}; 5878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projecttemplate <class Abstractor, unsigned maxDepth, class BSet> 5898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectinline typename AVLTree<Abstractor, maxDepth, BSet>::handle 5908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source ProjectAVLTree<Abstractor, maxDepth, BSet>::insert(handle h) 5918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project{ 5928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_lt(h, null()); 5938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(h, null()); 5948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(h, 0); 5958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 5968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (abs.root == null()) 5978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project abs.root = h; 5988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else { 5998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Last unbalanced node encountered in search for insertion point. 6008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle unbal = null(); 6018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Parent of last unbalanced node. 6028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle parent_unbal = null(); 6038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Balance factor of last unbalanced node. 6048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int unbal_bf; 6058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Zero-based depth in tree. 6078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unsigned depth = 0, unbal_depth = 0; 6088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Records a path into the tree. If branch[n] is true, indicates 6108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // take greater branch from the nth node in the path, otherwise 6118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // take the less branch. branch[0] gives branch from root, and 6128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // so on. 6138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project BSet branch; 6148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle hh = abs.root; 6168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle parent = null(); 6178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int cmp; 6188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project do { 6208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (get_bf(hh) != 0) { 6218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unbal = hh; 6228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project parent_unbal = parent; 6238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unbal_depth = depth; 6248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cmp = cmp_n_n(h, hh); 6268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (cmp == 0) 6278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Duplicate key. 6288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return hh; 6298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project parent = hh; 6308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project hh = cmp < 0 ? get_lt(hh) : get_gt(hh); 6318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project branch[depth++] = cmp > 0; 6328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } while (hh != null()); 6338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Add node to insert as leaf of tree. 6358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (cmp < 0) 6368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_lt(parent, h); 6378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 6388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(parent, h); 6398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project depth = unbal_depth; 6418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (unbal == null()) 6438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project hh = abs.root; 6448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else { 6458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cmp = branch[depth++] ? 1 : -1; 6468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unbal_bf = get_bf(unbal); 6478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (cmp < 0) 6488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unbal_bf--; 6498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else // cmp > 0 6508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unbal_bf++; 6518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project hh = cmp < 0 ? get_lt(unbal) : get_gt(unbal); 6528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if ((unbal_bf != -2) && (unbal_bf != 2)) { 6538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // No rebalancing of tree is necessary. 6548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(unbal, unbal_bf); 6558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unbal = null(); 6568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (hh != null()) 6608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project while (h != hh) { 6618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cmp = branch[depth++] ? 1 : -1; 6628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (cmp < 0) { 6638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(hh, -1); 6648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project hh = get_lt(hh); 6658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { // cmp > 0 6668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(hh, 1); 6678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project hh = get_gt(hh); 6688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (unbal != null()) { 6728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unbal = balance(unbal); 6738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (parent_unbal == null()) 6748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project abs.root = unbal; 6758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else { 6768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project depth = unbal_depth - 1; 6778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cmp = branch[depth] ? 1 : -1; 6788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (cmp < 0) 6798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_lt(parent_unbal, unbal); 6808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else // cmp > 0 6818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(parent_unbal, unbal); 6828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 6858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return h; 6878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 6888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projecttemplate <class Abstractor, unsigned maxDepth, class BSet> 6908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectinline typename AVLTree<Abstractor, maxDepth, BSet>::handle 6918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source ProjectAVLTree<Abstractor, maxDepth, BSet>::search(key k, typename AVLTree<Abstractor, maxDepth, BSet>::SearchType st) 6928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project{ 6938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1); 6948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int cmp, target_cmp; 6968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle match_h = null(); 6978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle h = abs.root; 6988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 6998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (st & LESS) 7008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project target_cmp = 1; 7018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else if (st & GREATER) 7028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project target_cmp = -1; 7038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 7048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project target_cmp = 0; 7058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project while (h != null()) { 7078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cmp = cmp_k_n(k, h); 7088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (cmp == 0) { 7098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (st & EQUAL) { 7108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project match_h = h; 7118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project break; 7128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 7138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cmp = -target_cmp; 7148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else if (target_cmp != 0) 7158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!((cmp ^ target_cmp) & MASK_HIGH_BIT)) 7168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // cmp and target_cmp are both positive or both negative. 7178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project match_h = h; 7188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project h = cmp < 0 ? get_lt(h) : get_gt(h); 7198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 7208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return match_h; 7228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 7238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projecttemplate <class Abstractor, unsigned maxDepth, class BSet> 7258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectinline typename AVLTree<Abstractor, maxDepth, BSet>::handle 7268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source ProjectAVLTree<Abstractor, maxDepth, BSet>::search_least() 7278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project{ 7288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle h = abs.root, parent = null(); 7298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project while (h != null()) { 7318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project parent = h; 7328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project h = get_lt(h); 7338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 7348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return parent; 7368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 7378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projecttemplate <class Abstractor, unsigned maxDepth, class BSet> 7398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectinline typename AVLTree<Abstractor, maxDepth, BSet>::handle 7408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source ProjectAVLTree<Abstractor, maxDepth, BSet>::search_greatest() 7418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project{ 7428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle h = abs.root, parent = null(); 7438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project while (h != null()) { 7458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project parent = h; 7468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project h = get_gt(h); 7478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 7488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return parent; 7508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 7518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projecttemplate <class Abstractor, unsigned maxDepth, class BSet> 7538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectinline typename AVLTree<Abstractor, maxDepth, BSet>::handle 7548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source ProjectAVLTree<Abstractor, maxDepth, BSet>::remove(key k) 7558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project{ 7568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Zero-based depth in tree. 7578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project unsigned depth = 0, rm_depth; 7588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Records a path into the tree. If branch[n] is true, indicates 7608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // take greater branch from the nth node in the path, otherwise 7618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // take the less branch. branch[0] gives branch from root, and 7628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // so on. 7638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project BSet branch; 7648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle h = abs.root; 7668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle parent = null(), child; 7678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int cmp, cmp_shortened_sub_with_path; 7688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (;;) { 7708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (h == null()) 7718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // No node in tree with given key. 7728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return null(); 7738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cmp = cmp_k_n(k, h); 7748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (cmp == 0) 7758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Found node to remove. 7768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project break; 7778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project parent = h; 7788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project h = cmp < 0 ? get_lt(h) : get_gt(h); 7798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project branch[depth++] = cmp > 0; 7808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cmp_shortened_sub_with_path = cmp; 7818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 7828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle rm = h; 7838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle parent_rm = parent; 7848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project rm_depth = depth; 7858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // If the node to remove is not a leaf node, we need to get a 7878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // leaf node, or a node with a single leaf as its child, to put 7888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // in the place of the node to remove. We will get the greatest 7898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // node in the less subtree (of the node to remove), or the least 7908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // node in the greater subtree. We take the leaf node from the 7918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // deeper subtree, if there is one. 7928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 7938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (get_bf(h) < 0) { 7948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project child = get_lt(h); 7958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project branch[depth] = false; 7968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cmp = -1; 7978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 7988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project child = get_gt(h); 7998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project branch[depth] = true; 8008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cmp = 1; 8018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project depth++; 8038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (child != null()) { 8058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cmp = -cmp; 8068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project do { 8078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project parent = h; 8088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project h = child; 8098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (cmp < 0) { 8108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project child = get_lt(h); 8118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project branch[depth] = false; 8128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 8138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project child = get_gt(h); 8148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project branch[depth] = true; 8158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project depth++; 8178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } while (child != null()); 8188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (parent == rm) 8208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Only went through do loop once. Deleted node will be replaced 8218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // in the tree structure by one of its immediate children. 8228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cmp_shortened_sub_with_path = -cmp; 8238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 8248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cmp_shortened_sub_with_path = cmp; 8258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Get the handle of the opposite child, which may not be null. 827635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project child = cmp > 0 ? get_lt(h) : get_gt(h); 8288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (parent == null()) 8318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // There were only 1 or 2 nodes in this tree. 8328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project abs.root = child; 8338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else if (cmp_shortened_sub_with_path < 0) 8348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_lt(parent, child); 8358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 8368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(parent, child); 8378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // "path" is the parent of the subtree being eliminated or reduced 8398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // from a depth of 2 to 1. If "path" is the node to be removed, we 8408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // set path to the node we're about to poke into the position of the 8418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // node to be removed. 8428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle path = parent == rm ? h : parent; 8438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (h != rm) { 8458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Poke in the replacement for the node to be removed. 846635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project set_lt(h, get_lt(rm)); 847635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project set_gt(h, get_gt(rm)); 8488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(h, get_bf(rm)); 8498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (parent_rm == null()) 8508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project abs.root = h; 8518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else { 8528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project depth = rm_depth - 1; 8538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (branch[depth]) 8548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(parent_rm, h); 8558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 8568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_lt(parent_rm, h); 8578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (path != null()) { 8618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Create a temporary linked list from the parent of the path node 8628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // to the root node. 8638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project h = abs.root; 8648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project parent = null(); 8658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project depth = 0; 8668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project while (h != path) { 8678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (branch[depth++]) { 8688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project child = get_gt(h); 8698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(h, parent); 8708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 8718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project child = get_lt(h); 8728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_lt(h, parent); 8738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project parent = h; 8758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project h = child; 8768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 8788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Climb from the path node to the root node using the linked 8798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // list, restoring the tree structure and rebalancing as necessary. 8808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool reduced_depth = true; 8818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int bf; 8828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cmp = cmp_shortened_sub_with_path; 8838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (;;) { 8848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (reduced_depth) { 8858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bf = get_bf(h); 8868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (cmp < 0) 8878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bf++; 8888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else // cmp > 0 8898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bf--; 8908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if ((bf == -2) || (bf == 2)) { 8918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project h = balance(h); 8928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bf = get_bf(h); 8938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else 8948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(h, bf); 8958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project reduced_depth = (bf == 0); 8968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 8978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (parent == null()) 8988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project break; 8998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project child = h; 9008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project h = parent; 9018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cmp = branch[--depth] ? 1 : -1; 9028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (cmp < 0) { 9038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project parent = get_lt(h); 9048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_lt(h, child); 9058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } else { 9068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project parent = get_gt(h); 9078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(h, child); 9088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 9098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 9108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project abs.root = h; 9118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 9128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return rm; 9148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 9158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projecttemplate <class Abstractor, unsigned maxDepth, class BSet> 9178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectinline typename AVLTree<Abstractor, maxDepth, BSet>::handle 9188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source ProjectAVLTree<Abstractor, maxDepth, BSet>::subst(handle new_node) 9198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project{ 9208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle h = abs.root; 9218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project handle parent = null(); 9228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project int cmp, last_cmp; 9238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project /* Search for node already in tree with same key. */ 9258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (;;) { 9268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (h == null()) 9278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project /* No node in tree with same key as new node. */ 9288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return null(); 9298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project cmp = cmp_n_n(new_node, h); 9308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (cmp == 0) 9318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project /* Found the node to substitute new one for. */ 9328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project break; 9338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project last_cmp = cmp; 9348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project parent = h; 9358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project h = cmp < 0 ? get_lt(h) : get_gt(h); 9368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 9378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project /* Copy tree housekeeping fields from node in tree to new node. */ 939635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project set_lt(new_node, get_lt(h)); 940635860845790a19bf50bbc51ba8fb66a96dde068The Android Open Source Project set_gt(new_node, get_gt(h)); 9418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_bf(new_node, get_bf(h)); 9428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (parent == null()) 9448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project /* New node is also new root. */ 9458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project abs.root = new_node; 9468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else { 9478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project /* Make parent point to new node. */ 9488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (last_cmp < 0) 9498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_lt(parent, new_node); 9508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project else 9518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project set_gt(parent, new_node); 9528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 9538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return h; 9558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 9568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project} 9588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 9598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 960