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