blob: f2f82e17063068ce5ba9f1827ada904dd1b9390a [file] [log] [blame]
/*
* Copyright (C) 2008 Apple Inc. All rights reserved.
*
* Based on Abstract AVL Tree Template v1.5 by Walt Karas
* <http://geocities.com/wkaras/gen_cpp/avl_tree.html>.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of
* its contributors may be used to endorse or promote products derived
* from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef AVL_TREE_H_
#define AVL_TREE_H_
#include <wtf/Assertions.h>
#include <wtf/FixedArray.h>
namespace WTF {
// Here is the reference class for BSet.
//
// class BSet
// {
// public:
//
// class ANY_bitref
// {
// public:
// operator bool ();
// void operator = (bool b);
// };
//
// // Does not have to initialize bits.
// BSet();
//
// // Must return a valid value for index when 0 <= index < maxDepth
// ANY_bitref operator [] (unsigned index);
//
// // Set all bits to 1.
// void set();
//
// // Set all bits to 0.
// void reset();
// };
template<unsigned maxDepth>
class AVLTreeDefaultBSet {
public:
bool& operator[](unsigned i) { ASSERT(i < maxDepth); return m_data[i]; }
void set() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = true; }
void reset() { for (unsigned i = 0; i < maxDepth; ++i) m_data[i] = false; }
private:
FixedArray<bool, maxDepth> m_data;
};
// How to determine maxDepth:
// d Minimum number of nodes
// 2 2
// 3 4
// 4 7
// 5 12
// 6 20
// 7 33
// 8 54
// 9 88
// 10 143
// 11 232
// 12 376
// 13 609
// 14 986
// 15 1,596
// 16 2,583
// 17 4,180
// 18 6,764
// 19 10,945
// 20 17,710
// 21 28,656
// 22 46,367
// 23 75,024
// 24 121,392
// 25 196,417
// 26 317,810
// 27 514,228
// 28 832,039
// 29 1,346,268
// 30 2,178,308
// 31 3,524,577
// 32 5,702,886
// 33 9,227,464
// 34 14,930,351
// 35 24,157,816
// 36 39,088,168
// 37 63,245,985
// 38 102,334,154
// 39 165,580,140
// 40 267,914,295
// 41 433,494,436
// 42 701,408,732
// 43 1,134,903,169
// 44 1,836,311,902
// 45 2,971,215,072
//
// 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.
// 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.
template <class Abstractor, unsigned maxDepth = 32, class BSet = AVLTreeDefaultBSet<maxDepth> >
class AVLTree {
public:
typedef typename Abstractor::key key;
typedef typename Abstractor::handle handle;
typedef typename Abstractor::size size;
enum SearchType {
EQUAL = 1,
LESS = 2,
GREATER = 4,
LESS_EQUAL = EQUAL | LESS,
GREATER_EQUAL = EQUAL | GREATER
};
Abstractor& abstractor() { return abs; }
inline handle insert(handle h);
inline handle search(key k, SearchType st = EQUAL);
inline handle search_least();
inline handle search_greatest();
inline handle remove(key k);
inline handle subst(handle new_node);
void purge() { abs.root = null(); }
bool is_empty() { return abs.root == null(); }
AVLTree() { abs.root = null(); }
class Iterator {
public:
// Initialize depth to invalid value, to indicate iterator is
// invalid. (Depth is zero-base.)
Iterator() { depth = ~0U; }
void start_iter(AVLTree &tree, key k, SearchType st = EQUAL)
{
// Mask of high bit in an int.
const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);
// Save the tree that we're going to iterate through in a
// member variable.
tree_ = &tree;
int cmp, target_cmp;
handle h = tree_->abs.root;
unsigned d = 0;
depth = ~0U;
if (h == null())
// Tree is empty.
return;
if (st & LESS)
// Key can be greater than key of starting node.
target_cmp = 1;
else if (st & GREATER)
// Key can be less than key of starting node.
target_cmp = -1;
else
// Key must be same as key of starting node.
target_cmp = 0;
for (;;) {
cmp = cmp_k_n(k, h);
if (cmp == 0) {
if (st & EQUAL) {
// Equal node was sought and found as starting node.
depth = d;
break;
}
cmp = -target_cmp;
} else if (target_cmp != 0) {
if (!((cmp ^ target_cmp) & MASK_HIGH_BIT)) {
// cmp and target_cmp are both negative or both positive.
depth = d;
}
}
h = cmp < 0 ? get_lt(h) : get_gt(h);
if (h == null())
break;
branch[d] = cmp > 0;
path_h[d++] = h;
}
}
void start_iter_least(AVLTree &tree)
{
tree_ = &tree;
handle h = tree_->abs.root;
depth = ~0U;
branch.reset();
while (h != null()) {
if (depth != ~0U)
path_h[depth] = h;
depth++;
h = get_lt(h);
}
}
void start_iter_greatest(AVLTree &tree)
{
tree_ = &tree;
handle h = tree_->abs.root;
depth = ~0U;
branch.set();
while (h != null()) {
if (depth != ~0U)
path_h[depth] = h;
depth++;
h = get_gt(h);
}
}
handle operator*()
{
if (depth == ~0U)
return null();
return depth == 0 ? tree_->abs.root : path_h[depth - 1];
}
void operator++()
{
if (depth != ~0U) {
handle h = get_gt(**this);
if (h == null()) {
do {
if (depth == 0) {
depth = ~0U;
break;
}
depth--;
} while (branch[depth]);
} else {
branch[depth] = true;
path_h[depth++] = h;
for (;;) {
h = get_lt(h);
if (h == null())
break;
branch[depth] = false;
path_h[depth++] = h;
}
}
}
}
void operator--()
{
if (depth != ~0U) {
handle h = get_lt(**this);
if (h == null())
do {
if (depth == 0) {
depth = ~0U;
break;
}
depth--;
} while (!branch[depth]);
else {
branch[depth] = false;
path_h[depth++] = h;
for (;;) {
h = get_gt(h);
if (h == null())
break;
branch[depth] = true;
path_h[depth++] = h;
}
}
}
}
void operator++(int) { ++(*this); }
void operator--(int) { --(*this); }
protected:
// Tree being iterated over.
AVLTree *tree_;
// Records a path into the tree. If branch[n] is true, indicates
// take greater branch from the nth node in the path, otherwise
// take the less branch. branch[0] gives branch from root, and
// so on.
BSet branch;
// Zero-based depth of path into tree.
unsigned depth;
// Handles of nodes in path from root to current node (returned by *).
handle path_h[maxDepth - 1];
int cmp_k_n(key k, handle h) { return tree_->abs.compare_key_node(k, h); }
int cmp_n_n(handle h1, handle h2) { return tree_->abs.compare_node_node(h1, h2); }
handle get_lt(handle h) { return tree_->abs.get_less(h); }
handle get_gt(handle h) { return tree_->abs.get_greater(h); }
handle null() { return tree_->abs.null(); }
};
template<typename fwd_iter>
bool build(fwd_iter p, size num_nodes)
{
if (num_nodes == 0) {
abs.root = null();
return true;
}
// Gives path to subtree being built. If branch[N] is false, branch
// less from the node at depth N, if true branch greater.
BSet branch;
// If rem[N] is true, then for the current subtree at depth N, it's
// greater subtree has one more node than it's less subtree.
BSet rem;
// Depth of root node of current subtree.
unsigned depth = 0;
// Number of nodes in current subtree.
size num_sub = num_nodes;
// The algorithm relies on a stack of nodes whose less subtree has
// been built, but whose right subtree has not yet been built. The
// stack is implemented as linked list. The nodes are linked
// together by having the "greater" handle of a node set to the
// next node in the list. "less_parent" is the handle of the first
// node in the list.
handle less_parent = null();
// h is root of current subtree, child is one of its children.
handle h, child;
for (;;) {
while (num_sub > 2) {
// Subtract one for root of subtree.
num_sub--;
rem[depth] = !!(num_sub & 1);
branch[depth++] = false;
num_sub >>= 1;
}
if (num_sub == 2) {
// Build a subtree with two nodes, slanting to greater.
// I arbitrarily chose to always have the extra node in the
// greater subtree when there is an odd number of nodes to
// split between the two subtrees.
h = *p;
p++;
child = *p;
p++;
set_lt(child, null());
set_gt(child, null());
set_bf(child, 0);
set_gt(h, child);
set_lt(h, null());
set_bf(h, 1);
} else { // num_sub == 1
// Build a subtree with one node.
h = *p;
p++;
set_lt(h, null());
set_gt(h, null());
set_bf(h, 0);
}
while (depth) {
depth--;
if (!branch[depth])
// We've completed a less subtree.
break;
// We've completed a greater subtree, so attach it to
// its parent (that is less than it). We pop the parent
// off the stack of less parents.
child = h;
h = less_parent;
less_parent = get_gt(h);
set_gt(h, child);
// num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1
num_sub <<= 1;
num_sub += 1 - rem[depth];
if (num_sub & (num_sub - 1))
// num_sub is not a power of 2
set_bf(h, 0);
else
// num_sub is a power of 2
set_bf(h, 1);
}
if (num_sub == num_nodes)
// We've completed the full tree.
break;
// The subtree we've completed is the less subtree of the
// next node in the sequence.
child = h;
h = *p;
p++;
set_lt(h, child);
// Put h into stack of less parents.
set_gt(h, less_parent);
less_parent = h;
// Proceed to creating greater than subtree of h.
branch[depth] = true;
num_sub += rem[depth++];
} // end for (;;)
abs.root = h;
return true;
}
protected:
friend class Iterator;
// Create a class whose sole purpose is to take advantage of
// the "empty member" optimization.
struct abs_plus_root : public Abstractor {
// The handle of the root element in the AVL tree.
handle root;
};
abs_plus_root abs;
handle get_lt(handle h) { return abs.get_less(h); }
void set_lt(handle h, handle lh) { abs.set_less(h, lh); }
handle get_gt(handle h) { return abs.get_greater(h); }
void set_gt(handle h, handle gh) { abs.set_greater(h, gh); }
int get_bf(handle h) { return abs.get_balance_factor(h); }
void set_bf(handle h, int bf) { abs.set_balance_factor(h, bf); }
int cmp_k_n(key k, handle h) { return abs.compare_key_node(k, h); }
int cmp_n_n(handle h1, handle h2) { return abs.compare_node_node(h1, h2); }
handle null() { return abs.null(); }
private:
// Balances subtree, returns handle of root node of subtree
// after balancing.
handle balance(handle bal_h)
{
handle deep_h;
// Either the "greater than" or the "less than" subtree of
// this node has to be 2 levels deeper (or else it wouldn't
// need balancing).
if (get_bf(bal_h) > 0) {
// "Greater than" subtree is deeper.
deep_h = get_gt(bal_h);
if (get_bf(deep_h) < 0) {
handle old_h = bal_h;
bal_h = get_lt(deep_h);
set_gt(old_h, get_lt(bal_h));
set_lt(deep_h, get_gt(bal_h));
set_lt(bal_h, old_h);
set_gt(bal_h, deep_h);
int bf = get_bf(bal_h);
if (bf != 0) {
if (bf > 0) {
set_bf(old_h, -1);
set_bf(deep_h, 0);
} else {
set_bf(deep_h, 1);
set_bf(old_h, 0);
}
set_bf(bal_h, 0);
} else {
set_bf(old_h, 0);
set_bf(deep_h, 0);
}
} else {
set_gt(bal_h, get_lt(deep_h));
set_lt(deep_h, bal_h);
if (get_bf(deep_h) == 0) {
set_bf(deep_h, -1);
set_bf(bal_h, 1);
} else {
set_bf(deep_h, 0);
set_bf(bal_h, 0);
}
bal_h = deep_h;
}
} else {
// "Less than" subtree is deeper.
deep_h = get_lt(bal_h);
if (get_bf(deep_h) > 0) {
handle old_h = bal_h;
bal_h = get_gt(deep_h);
set_lt(old_h, get_gt(bal_h));
set_gt(deep_h, get_lt(bal_h));
set_gt(bal_h, old_h);
set_lt(bal_h, deep_h);
int bf = get_bf(bal_h);
if (bf != 0) {
if (bf < 0) {
set_bf(old_h, 1);
set_bf(deep_h, 0);
} else {
set_bf(deep_h, -1);
set_bf(old_h, 0);
}
set_bf(bal_h, 0);
} else {
set_bf(old_h, 0);
set_bf(deep_h, 0);
}
} else {
set_lt(bal_h, get_gt(deep_h));
set_gt(deep_h, bal_h);
if (get_bf(deep_h) == 0) {
set_bf(deep_h, 1);
set_bf(bal_h, -1);
} else {
set_bf(deep_h, 0);
set_bf(bal_h, 0);
}
bal_h = deep_h;
}
}
return bal_h;
}
};
template <class Abstractor, unsigned maxDepth, class BSet>
inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
AVLTree<Abstractor, maxDepth, BSet>::insert(handle h)
{
set_lt(h, null());
set_gt(h, null());
set_bf(h, 0);
if (abs.root == null())
abs.root = h;
else {
// Last unbalanced node encountered in search for insertion point.
handle unbal = null();
// Parent of last unbalanced node.
handle parent_unbal = null();
// Balance factor of last unbalanced node.
int unbal_bf;
// Zero-based depth in tree.
unsigned depth = 0, unbal_depth = 0;
// Records a path into the tree. If branch[n] is true, indicates
// take greater branch from the nth node in the path, otherwise
// take the less branch. branch[0] gives branch from root, and
// so on.
BSet branch;
handle hh = abs.root;
handle parent = null();
int cmp;
do {
if (get_bf(hh) != 0) {
unbal = hh;
parent_unbal = parent;
unbal_depth = depth;
}
cmp = cmp_n_n(h, hh);
if (cmp == 0)
// Duplicate key.
return hh;
parent = hh;
hh = cmp < 0 ? get_lt(hh) : get_gt(hh);
branch[depth++] = cmp > 0;
} while (hh != null());
// Add node to insert as leaf of tree.
if (cmp < 0)
set_lt(parent, h);
else
set_gt(parent, h);
depth = unbal_depth;
if (unbal == null())
hh = abs.root;
else {
cmp = branch[depth++] ? 1 : -1;
unbal_bf = get_bf(unbal);
if (cmp < 0)
unbal_bf--;
else // cmp > 0
unbal_bf++;
hh = cmp < 0 ? get_lt(unbal) : get_gt(unbal);
if ((unbal_bf != -2) && (unbal_bf != 2)) {
// No rebalancing of tree is necessary.
set_bf(unbal, unbal_bf);
unbal = null();
}
}
if (hh != null())
while (h != hh) {
cmp = branch[depth++] ? 1 : -1;
if (cmp < 0) {
set_bf(hh, -1);
hh = get_lt(hh);
} else { // cmp > 0
set_bf(hh, 1);
hh = get_gt(hh);
}
}
if (unbal != null()) {
unbal = balance(unbal);
if (parent_unbal == null())
abs.root = unbal;
else {
depth = unbal_depth - 1;
cmp = branch[depth] ? 1 : -1;
if (cmp < 0)
set_lt(parent_unbal, unbal);
else // cmp > 0
set_gt(parent_unbal, unbal);
}
}
}
return h;
}
template <class Abstractor, unsigned maxDepth, class BSet>
inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
AVLTree<Abstractor, maxDepth, BSet>::search(key k, typename AVLTree<Abstractor, maxDepth, BSet>::SearchType st)
{
const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);
int cmp, target_cmp;
handle match_h = null();
handle h = abs.root;
if (st & LESS)
target_cmp = 1;
else if (st & GREATER)
target_cmp = -1;
else
target_cmp = 0;
while (h != null()) {
cmp = cmp_k_n(k, h);
if (cmp == 0) {
if (st & EQUAL) {
match_h = h;
break;
}
cmp = -target_cmp;
} else if (target_cmp != 0)
if (!((cmp ^ target_cmp) & MASK_HIGH_BIT))
// cmp and target_cmp are both positive or both negative.
match_h = h;
h = cmp < 0 ? get_lt(h) : get_gt(h);
}
return match_h;
}
template <class Abstractor, unsigned maxDepth, class BSet>
inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
AVLTree<Abstractor, maxDepth, BSet>::search_least()
{
handle h = abs.root, parent = null();
while (h != null()) {
parent = h;
h = get_lt(h);
}
return parent;
}
template <class Abstractor, unsigned maxDepth, class BSet>
inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
AVLTree<Abstractor, maxDepth, BSet>::search_greatest()
{
handle h = abs.root, parent = null();
while (h != null()) {
parent = h;
h = get_gt(h);
}
return parent;
}
template <class Abstractor, unsigned maxDepth, class BSet>
inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
AVLTree<Abstractor, maxDepth, BSet>::remove(key k)
{
// Zero-based depth in tree.
unsigned depth = 0, rm_depth;
// Records a path into the tree. If branch[n] is true, indicates
// take greater branch from the nth node in the path, otherwise
// take the less branch. branch[0] gives branch from root, and
// so on.
BSet branch;
handle h = abs.root;
handle parent = null(), child;
int cmp, cmp_shortened_sub_with_path = 0;
for (;;) {
if (h == null())
// No node in tree with given key.
return null();
cmp = cmp_k_n(k, h);
if (cmp == 0)
// Found node to remove.
break;
parent = h;
h = cmp < 0 ? get_lt(h) : get_gt(h);
branch[depth++] = cmp > 0;
cmp_shortened_sub_with_path = cmp;
}
handle rm = h;
handle parent_rm = parent;
rm_depth = depth;
// If the node to remove is not a leaf node, we need to get a
// leaf node, or a node with a single leaf as its child, to put
// in the place of the node to remove. We will get the greatest
// node in the less subtree (of the node to remove), or the least
// node in the greater subtree. We take the leaf node from the
// deeper subtree, if there is one.
if (get_bf(h) < 0) {
child = get_lt(h);
branch[depth] = false;
cmp = -1;
} else {
child = get_gt(h);
branch[depth] = true;
cmp = 1;
}
depth++;
if (child != null()) {
cmp = -cmp;
do {
parent = h;
h = child;
if (cmp < 0) {
child = get_lt(h);
branch[depth] = false;
} else {
child = get_gt(h);
branch[depth] = true;
}
depth++;
} while (child != null());
if (parent == rm)
// Only went through do loop once. Deleted node will be replaced
// in the tree structure by one of its immediate children.
cmp_shortened_sub_with_path = -cmp;
else
cmp_shortened_sub_with_path = cmp;
// Get the handle of the opposite child, which may not be null.
child = cmp > 0 ? get_lt(h) : get_gt(h);
}
if (parent == null())
// There were only 1 or 2 nodes in this tree.
abs.root = child;
else if (cmp_shortened_sub_with_path < 0)
set_lt(parent, child);
else
set_gt(parent, child);
// "path" is the parent of the subtree being eliminated or reduced
// from a depth of 2 to 1. If "path" is the node to be removed, we
// set path to the node we're about to poke into the position of the
// node to be removed.
handle path = parent == rm ? h : parent;
if (h != rm) {
// Poke in the replacement for the node to be removed.
set_lt(h, get_lt(rm));
set_gt(h, get_gt(rm));
set_bf(h, get_bf(rm));
if (parent_rm == null())
abs.root = h;
else {
depth = rm_depth - 1;
if (branch[depth])
set_gt(parent_rm, h);
else
set_lt(parent_rm, h);
}
}
if (path != null()) {
// Create a temporary linked list from the parent of the path node
// to the root node.
h = abs.root;
parent = null();
depth = 0;
while (h != path) {
if (branch[depth++]) {
child = get_gt(h);
set_gt(h, parent);
} else {
child = get_lt(h);
set_lt(h, parent);
}
parent = h;
h = child;
}
// Climb from the path node to the root node using the linked
// list, restoring the tree structure and rebalancing as necessary.
bool reduced_depth = true;
int bf;
cmp = cmp_shortened_sub_with_path;
for (;;) {
if (reduced_depth) {
bf = get_bf(h);
if (cmp < 0)
bf++;
else // cmp > 0
bf--;
if ((bf == -2) || (bf == 2)) {
h = balance(h);
bf = get_bf(h);
} else
set_bf(h, bf);
reduced_depth = (bf == 0);
}
if (parent == null())
break;
child = h;
h = parent;
cmp = branch[--depth] ? 1 : -1;
if (cmp < 0) {
parent = get_lt(h);
set_lt(h, child);
} else {
parent = get_gt(h);
set_gt(h, child);
}
}
abs.root = h;
}
return rm;
}
template <class Abstractor, unsigned maxDepth, class BSet>
inline typename AVLTree<Abstractor, maxDepth, BSet>::handle
AVLTree<Abstractor, maxDepth, BSet>::subst(handle new_node)
{
handle h = abs.root;
handle parent = null();
int cmp, last_cmp;
/* Search for node already in tree with same key. */
for (;;) {
if (h == null())
/* No node in tree with same key as new node. */
return null();
cmp = cmp_n_n(new_node, h);
if (cmp == 0)
/* Found the node to substitute new one for. */
break;
last_cmp = cmp;
parent = h;
h = cmp < 0 ? get_lt(h) : get_gt(h);
}
/* Copy tree housekeeping fields from node in tree to new node. */
set_lt(new_node, get_lt(h));
set_gt(new_node, get_gt(h));
set_bf(new_node, get_bf(h));
if (parent == null())
/* New node is also new root. */
abs.root = new_node;
else {
/* Make parent point to new node. */
if (last_cmp < 0)
set_lt(parent, new_node);
else
set_gt(parent, new_node);
}
return h;
}
}
#endif