#ifndef AVL_TREE_H_
#define AVL_TREE_H_
#include "Assertions.h"
namespace WTF {
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:
bool m_data[maxDepth];
};
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:
Iterator() { depth = ~0U; }
void start_iter(AVLTree &tree, key k, SearchType st = EQUAL)
{
const int MASK_HIGH_BIT = (int) ~ ((~ (unsigned) 0) >> 1);
tree_ = &tree;
int cmp, target_cmp;
handle h = tree_->abs.root;
unsigned d = 0;
depth = ~0U;
if (h == null())
return;
if (st & LESS)
target_cmp = 1;
else if (st & GREATER)
target_cmp = -1;
else
target_cmp = 0;
for (;;) {
cmp = cmp_k_n(k, h);
if (cmp == 0) {
if (st & EQUAL) {
depth = d;
break;
}
cmp = -target_cmp;
} else if (target_cmp != 0) {
if (!((cmp ^ target_cmp) & MASK_HIGH_BIT)) {
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:
AVLTree *tree_;
BSet branch;
unsigned depth;
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;
}
BSet branch;
BSet rem;
unsigned depth = 0;
size num_sub = num_nodes;
handle less_parent = null();
handle h, child;
for (;;) {
while (num_sub > 2) {
num_sub--;
rem[depth] = !!(num_sub & 1);
branch[depth++] = false;
num_sub >>= 1;
}
if (num_sub == 2) {
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 {
h = *p;
p++;
set_lt(h, null());
set_gt(h, null());
set_bf(h, 0);
}
while (depth) {
depth--;
if (!branch[depth])
break;
child = h;
h = less_parent;
less_parent = get_gt(h);
set_gt(h, child);
num_sub <<= 1;
num_sub += 1 - rem[depth];
if (num_sub & (num_sub - 1))
set_bf(h, 0);
else
set_bf(h, 1);
}
if (num_sub == num_nodes)
break;
child = h;
h = *p;
p++;
set_lt(h, child);
set_gt(h, less_parent);
less_parent = h;
branch[depth] = true;
num_sub += rem[depth++];
}
abs.root = h;
return true;
}
protected:
friend class Iterator;
struct abs_plus_root : public Abstractor {
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:
handle balance(handle bal_h)
{
handle deep_h;
if (get_bf(bal_h) > 0) {
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 {
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 {
handle unbal = null();
handle parent_unbal = null();
int unbal_bf;
unsigned depth = 0, unbal_depth = 0;
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)
return hh;
parent = hh;
hh = cmp < 0 ? get_lt(hh) : get_gt(hh);
branch[depth++] = cmp > 0;
} while (hh != null());
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 unbal_bf++;
hh = cmp < 0 ? get_lt(unbal) : get_gt(unbal);
if ((unbal_bf != -2) && (unbal_bf != 2)) {
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 { 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 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))
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)
{
unsigned depth = 0, rm_depth;
BSet branch;
handle h = abs.root;
handle parent = null(), child;
int cmp, cmp_shortened_sub_with_path;
for (;;) {
if (h == null())
return null();
cmp = cmp_k_n(k, h);
if (cmp == 0)
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 (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)
cmp_shortened_sub_with_path = -cmp;
else
cmp_shortened_sub_with_path = cmp;
child = cmp > 0 ? get_lt(h) : get_gt(h);
}
if (parent == null())
abs.root = child;
else if (cmp_shortened_sub_with_path < 0)
set_lt(parent, child);
else
set_gt(parent, child);
handle path = parent == rm ? h : parent;
if (h != rm) {
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()) {
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;
}
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 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;
for (;;) {
if (h == null())
return null();
cmp = cmp_n_n(new_node, h);
if (cmp == 0)
break;
last_cmp = cmp;
parent = h;
h = cmp < 0 ? get_lt(h) : get_gt(h);
}
set_lt(new_node, get_lt(h));
set_gt(new_node, get_gt(h));
set_bf(new_node, get_bf(h));
if (parent == null())
abs.root = new_node;
else {
if (last_cmp < 0)
set_lt(parent, new_node);
else
set_gt(parent, new_node);
}
return h;
}
}
#endif