125294551SIngo Weinhold/*
2a54549a8SIngo Weinhold * Copyright 2003-2009, Ingo Weinhold <ingo_weinhold@gmx.de>.
325294551SIngo Weinhold * Distributed under the terms of the MIT License.
425294551SIngo Weinhold */
525294551SIngo Weinhold
6a54549a8SIngo Weinhold
7a54549a8SIngo Weinhold#include <util/AVLTreeBase.h>
8a54549a8SIngo Weinhold
99f9ba0bdShyche#ifndef FS_SHELL
109f9ba0bdShyche#	include <algorithm>
119f9ba0bdShyche#	include <KernelExport.h>
13a54549a8SIngo Weinhold
14a54549a8SIngo Weinhold#ifdef _KERNEL_MODE
15a54549a8SIngo Weinhold#	define CHECK_FAILED(message...)	panic(message)
16a54549a8SIngo Weinhold#else
179f9ba0bdShyche#	ifndef FS_SHELL
189f9ba0bdShyche#		include <stdio.h>
199f9ba0bdShyche#		include <OS.h>
209f9ba0bdShyche#		define CHECK_FAILED(message...)					\
219f9ba0bdShyche			do {										\
229f9ba0bdShyche				fprintf(stderr, message);				\
239f9ba0bdShyche				fprintf(stderr, "\n");					\
249f9ba0bdShyche				debugger("AVLTreeBase check failed");	\
259f9ba0bdShyche			} while (false)
269f9ba0bdShyche#	else
279f9ba0bdShyche#		define CHECK_FAILED(message...) dprintf(message)
289f9ba0bdShyche#	endif
29a54549a8SIngo Weinhold#endif
30a54549a8SIngo Weinhold
31a54549a8SIngo Weinhold
32a54549a8SIngo Weinhold// maximal height of a tree
33a54549a8SIngo Weinholdstatic const int kMaxAVLTreeHeight = 32;
3425294551SIngo Weinhold
3525294551SIngo Weinhold
3625294551SIngo Weinhold// #pragma mark - AVLTreeCompare
3725294551SIngo Weinhold
3825294551SIngo Weinhold
3925294551SIngo WeinholdAVLTreeCompare::~AVLTreeCompare()
4025294551SIngo Weinhold{
4125294551SIngo Weinhold}
4225294551SIngo Weinhold
4325294551SIngo Weinhold
44a54549a8SIngo Weinhold// #pragma mark - AVLTreeBase
4525294551SIngo Weinhold
4625294551SIngo Weinhold
47a54549a8SIngo WeinholdAVLTreeBase::AVLTreeBase(AVLTreeCompare* compare)
4825294551SIngo Weinhold	: fRoot(NULL),
4925294551SIngo Weinhold	  fNodeCount(0),
5025294551SIngo Weinhold	  fCompare(compare)
5125294551SIngo Weinhold{
5225294551SIngo Weinhold}
5325294551SIngo Weinhold
5425294551SIngo Weinhold
55a54549a8SIngo WeinholdAVLTreeBase::~AVLTreeBase()
5625294551SIngo Weinhold{
5725294551SIngo Weinhold}
5825294551SIngo Weinhold
5925294551SIngo Weinhold
6025294551SIngo Weinholdvoid
61a54549a8SIngo WeinholdAVLTreeBase::MakeEmpty()
6225294551SIngo Weinhold{
6325294551SIngo Weinhold	fRoot = NULL;
6425294551SIngo Weinhold	fNodeCount = 0;
6525294551SIngo Weinhold}
6625294551SIngo Weinhold
6725294551SIngo Weinhold
6825294551SIngo WeinholdAVLTreeNode*
69a54549a8SIngo WeinholdAVLTreeBase::LeftMost(AVLTreeNode* node) const
7025294551SIngo Weinhold{
7125294551SIngo Weinhold	if (node) {
7225294551SIngo Weinhold		while (node->left)
7325294551SIngo Weinhold			node = node->left;
7425294551SIngo Weinhold	}
7525294551SIngo Weinhold
7625294551SIngo Weinhold	return node;
7725294551SIngo Weinhold}
7825294551SIngo Weinhold
7925294551SIngo Weinhold
8025294551SIngo WeinholdAVLTreeNode*
81a54549a8SIngo WeinholdAVLTreeBase::RightMost(AVLTreeNode* node) const
8225294551SIngo Weinhold{
8325294551SIngo Weinhold	if (node) {
8425294551SIngo Weinhold		while (node->right)
8525294551SIngo Weinhold			node = node->right;
8625294551SIngo Weinhold	}
8725294551SIngo Weinhold
8825294551SIngo Weinhold	return node;
8925294551SIngo Weinhold}
9025294551SIngo Weinhold
9125294551SIngo Weinhold
9225294551SIngo WeinholdAVLTreeNode*
93a54549a8SIngo WeinholdAVLTreeBase::Previous(AVLTreeNode* node) const
9425294551SIngo Weinhold{
9525294551SIngo Weinhold	if (node) {
9625294551SIngo Weinhold		// The previous node cannot be in the right subtree.
9725294551SIngo Weinhold		if (node->left) {
9825294551SIngo Weinhold			// We have a left subtree, so go to the right-most node.
9925294551SIngo Weinhold			node = node->left;
10025294551SIngo Weinhold			while (node->right)
10125294551SIngo Weinhold				node = node->right;
10225294551SIngo Weinhold		} else {
10325294551SIngo Weinhold			// No left subtree: Backtrack our path and stop, where we
10425294551SIngo Weinhold			// took the right branch.
10525294551SIngo Weinhold			AVLTreeNode* previous;
10625294551SIngo Weinhold			do {
10725294551SIngo Weinhold				previous = node;
10825294551SIngo Weinhold				node = node->parent;
10925294551SIngo Weinhold			} while (node && previous == node->left);
11025294551SIngo Weinhold		}
11125294551SIngo Weinhold	}
11225294551SIngo Weinhold
11325294551SIngo Weinhold	return node;
11425294551SIngo Weinhold}
11525294551SIngo Weinhold
11625294551SIngo Weinhold
11725294551SIngo WeinholdAVLTreeNode*
118a54549a8SIngo WeinholdAVLTreeBase::Next(AVLTreeNode* node) const
11925294551SIngo Weinhold{
12025294551SIngo Weinhold	if (node) {
12125294551SIngo Weinhold		// The next node cannot be in the left subtree.
12225294551SIngo Weinhold		if (node->right) {
12325294551SIngo Weinhold			// We have a right subtree, so go to the left-most node.
12425294551SIngo Weinhold			node = node->right;
12525294551SIngo Weinhold			while (node->left)
12625294551SIngo Weinhold				node = node->left;
12725294551SIngo Weinhold		} else {
12825294551SIngo Weinhold			// No right subtree: Backtrack our path and stop, where we
12925294551SIngo Weinhold			// took the left branch.
13025294551SIngo Weinhold			AVLTreeNode* previous;
13125294551SIngo Weinhold			do {
13225294551SIngo Weinhold				previous = node;
13325294551SIngo Weinhold				node = node->parent;
13425294551SIngo Weinhold			} while (node && previous == node->right);
13525294551SIngo Weinhold		}
13625294551SIngo Weinhold	}
13725294551SIngo Weinhold
13825294551SIngo Weinhold	return node;
13925294551SIngo Weinhold}
14025294551SIngo Weinhold
14125294551SIngo Weinhold
14225294551SIngo WeinholdAVLTreeNode*
143a54549a8SIngo WeinholdAVLTreeBase::Find(const void* key) const
14425294551SIngo Weinhold{
14525294551SIngo Weinhold	AVLTreeNode* node = fRoot;
14625294551SIngo Weinhold
14725294551SIngo Weinhold	while (node) {
14825294551SIngo Weinhold		int cmp = fCompare->CompareKeyNode(key, node);
14925294551SIngo Weinhold		if (cmp == 0)
15025294551SIngo Weinhold			return node;
15125294551SIngo Weinhold
15225294551SIngo Weinhold		if (cmp < 0)
15325294551SIngo Weinhold			node = node->left;
15425294551SIngo Weinhold		else
15525294551SIngo Weinhold			node = node->right;
15625294551SIngo Weinhold	}
15725294551SIngo Weinhold
15825294551SIngo Weinhold	return NULL;
15925294551SIngo Weinhold}
16025294551SIngo Weinhold
16125294551SIngo Weinhold
16225294551SIngo WeinholdAVLTreeNode*
163a54549a8SIngo WeinholdAVLTreeBase::FindClosest(const void* key, bool less) const
16425294551SIngo Weinhold{
16525294551SIngo Weinhold	AVLTreeNode* node = fRoot;
16625294551SIngo Weinhold	AVLTreeNode* parent = NULL;
16725294551SIngo Weinhold
16825294551SIngo Weinhold	while (node) {
16925294551SIngo Weinhold		int cmp = fCompare->CompareKeyNode(key, node);
17025294551SIngo Weinhold		if (cmp == 0)
17125294551SIngo Weinhold			break;
17225294551SIngo Weinhold
17325294551SIngo Weinhold		parent = node;
17425294551SIngo Weinhold		if (cmp < 0)
17525294551SIngo Weinhold			node = node->left;
17625294551SIngo Weinhold		else
17725294551SIngo Weinhold			node = node->right;
17825294551SIngo Weinhold	}
17925294551SIngo Weinhold
18025294551SIngo Weinhold	// not found: try to get close
18125294551SIngo Weinhold	if (!node && parent) {
18225294551SIngo Weinhold		node = parent;
18325294551SIngo Weinhold		int expectedCmp = (less ? 1 : -1);
18425294551SIngo Weinhold		int cmp = fCompare->CompareKeyNode(key, node);
18525294551SIngo Weinhold		if (cmp != expectedCmp) {
18625294551SIngo Weinhold			// The node's value is less although we were asked for a greater
18725294551SIngo Weinhold			// value, or the other way around. We need to iterate to the next
18825294551SIngo Weinhold			// node in the respective direction. If there is no node, we fail.
18925294551SIngo Weinhold			if (less)
19025294551SIngo Weinhold				return Previous(node);
19125294551SIngo Weinhold			return Next(node);
19225294551SIngo Weinhold		}
19325294551SIngo Weinhold	}
19425294551SIngo Weinhold
19525294551SIngo Weinhold	return node;
19625294551SIngo Weinhold}
19725294551SIngo Weinhold
19825294551SIngo Weinhold
199a54549a8SIngo Weinholdstatus_t
200a54549a8SIngo WeinholdAVLTreeBase::Insert(AVLTreeNode* nodeToInsert)
201a54549a8SIngo Weinhold{
202a54549a8SIngo Weinhold	int result = _Insert(nodeToInsert);
203a54549a8SIngo Weinhold	switch (result) {
204a54549a8SIngo Weinhold		case OK:
205a54549a8SIngo Weinhold		case HEIGHT_CHANGED:
206a54549a8SIngo Weinhold			return B_OK;
207a54549a8SIngo Weinhold		case NO_MEMORY:
208a54549a8SIngo Weinhold			return B_NO_MEMORY;
209a54549a8SIngo Weinhold		case DUPLICATE:
210a54549a8SIngo Weinhold		default:
211a54549a8SIngo Weinhold			return B_BAD_VALUE;
212a54549a8SIngo Weinhold	}
213a54549a8SIngo Weinhold}
214a54549a8SIngo Weinhold
215a54549a8SIngo Weinhold
216a54549a8SIngo WeinholdAVLTreeNode*
217a54549a8SIngo WeinholdAVLTreeBase::Remove(const void* key)
218a54549a8SIngo Weinhold{
219a54549a8SIngo Weinhold	// find node
220a54549a8SIngo Weinhold	AVLTreeNode* node = fRoot;
221a54549a8SIngo Weinhold	while (node) {
222a54549a8SIngo Weinhold		int cmp = fCompare->CompareKeyNode(key, node);
223a54549a8SIngo Weinhold		if (cmp == 0)
224a54549a8SIngo Weinhold			break;
225a54549a8SIngo Weinhold		else {
226a54549a8SIngo Weinhold			if (cmp < 0)
227a54549a8SIngo Weinhold				node = node->left;
228a54549a8SIngo Weinhold			else
229a54549a8SIngo Weinhold				node = node->right;
230a54549a8SIngo Weinhold		}
231a54549a8SIngo Weinhold	}
232a54549a8SIngo Weinhold
233a54549a8SIngo Weinhold	// remove it
234a54549a8SIngo Weinhold	if (node)
235a54549a8SIngo Weinhold		_Remove(node);
236a54549a8SIngo Weinhold
237a54549a8SIngo Weinhold	return node;
238a54549a8SIngo Weinhold}
239a54549a8SIngo Weinhold
240a54549a8SIngo Weinhold
241a54549a8SIngo Weinholdbool
242a54549a8SIngo WeinholdAVLTreeBase::Remove(AVLTreeNode* node)
243a54549a8SIngo Weinhold{
244a54549a8SIngo Weinhold	switch (_Remove(node)) {
245a54549a8SIngo Weinhold		case OK:
246a54549a8SIngo Weinhold		case HEIGHT_CHANGED:
247a54549a8SIngo Weinhold			return true;
248a54549a8SIngo Weinhold		case NOT_FOUND:
249a54549a8SIngo Weinhold		default:
250a54549a8SIngo Weinhold			return false;
251a54549a8SIngo Weinhold	}
252a54549a8SIngo Weinhold}
253a54549a8SIngo Weinhold
254a54549a8SIngo Weinhold
25525294551SIngo Weinholdvoid
256a54549a8SIngo WeinholdAVLTreeBase::CheckTree() const
257a54549a8SIngo Weinhold{
258a54549a8SIngo Weinhold	int nodeCount = 0;
259a54549a8SIngo Weinhold	_CheckTree(NULL, fRoot, nodeCount);
260a54549a8SIngo Weinhold	if (nodeCount != fNodeCount) {
261a54549a8SIngo Weinhold		CHECK_FAILED("AVLTreeBase::CheckTree(): node count mismatch: %d vs %d",
262a54549a8SIngo Weinhold			nodeCount, fNodeCount);
263a54549a8SIngo Weinhold	}
264a54549a8SIngo Weinhold}
265a54549a8SIngo Weinhold
266a54549a8SIngo Weinhold
267a54549a8SIngo Weinholdvoid
268a54549a8SIngo WeinholdAVLTreeBase::_RotateRight(AVLTreeNode** nodeP)
26925294551SIngo Weinhold{
27025294551SIngo Weinhold	// rotate the nodes
27125294551SIngo Weinhold	AVLTreeNode* node = *nodeP;
27225294551SIngo Weinhold	AVLTreeNode* left = node->left;
27325294551SIngo Weinhold
27425294551SIngo Weinhold	*nodeP = left;
27525294551SIngo Weinhold
27625294551SIngo Weinhold	left->parent = node->parent;
27725294551SIngo Weinhold	node->left = left->right;
27825294551SIngo Weinhold	if (left->right)
27925294551SIngo Weinhold		left->right->parent = node;
28025294551SIngo Weinhold	left->right = node;
28125294551SIngo Weinhold	node->parent = left;
28225294551SIngo Weinhold
28325294551SIngo Weinhold	// adjust the balance factors
28425294551SIngo Weinhold	// former pivot
28525294551SIngo Weinhold	if (left->balance_factor >= 0)
28625294551SIngo Weinhold		node->balance_factor++;
28725294551SIngo Weinhold	else
28825294551SIngo Weinhold		node->balance_factor += 1 - left->balance_factor;
28925294551SIngo Weinhold
29025294551SIngo Weinhold	// former left
29125294551SIngo Weinhold	if (node->balance_factor <= 0)
29225294551SIngo Weinhold		left->balance_factor++;
29325294551SIngo Weinhold	else
29425294551SIngo Weinhold		left->balance_factor += node->balance_factor + 1;
29525294551SIngo Weinhold}
29625294551SIngo Weinhold
29725294551SIngo Weinhold
29825294551SIngo Weinholdvoid
299a54549a8SIngo WeinholdAVLTreeBase::_RotateLeft(AVLTreeNode** nodeP)
30025294551SIngo Weinhold{
30125294551SIngo Weinhold	// rotate the nodes
30225294551SIngo Weinhold	AVLTreeNode* node = *nodeP;
30325294551SIngo Weinhold	AVLTreeNode* right = node->right;
30425294551SIngo Weinhold
30525294551SIngo Weinhold	*nodeP = right;
30625294551SIngo Weinhold
30725294551SIngo Weinhold	right->parent = node->parent;
30825294551SIngo Weinhold	node->right = right->left;
30925294551SIngo Weinhold	if (right->left)
31025294551SIngo Weinhold		right->left->parent = node;
31125294551SIngo Weinhold	right->left = node;
31225294551SIngo Weinhold	node->parent = right;
31325294551SIngo Weinhold
31425294551SIngo Weinhold	// adjust the balance factors
31525294551SIngo Weinhold	// former pivot
31625294551SIngo Weinhold	if (right->balance_factor <= 0)
31725294551SIngo Weinhold		node->balance_factor--;
31825294551SIngo Weinhold	else
31925294551SIngo Weinhold		node->balance_factor -= right->balance_factor + 1;
32025294551SIngo Weinhold
32125294551SIngo Weinhold	// former right
32225294551SIngo Weinhold	if (node->balance_factor >= 0)
32325294551SIngo Weinhold		right->balance_factor--;
32425294551SIngo Weinhold	else
32525294551SIngo Weinhold		right->balance_factor += node->balance_factor - 1;
32625294551SIngo Weinhold}
32725294551SIngo Weinhold
32825294551SIngo Weinhold
32925294551SIngo Weinholdint
330a54549a8SIngo WeinholdAVLTreeBase::_BalanceInsertLeft(AVLTreeNode** node)
33125294551SIngo Weinhold{
33225294551SIngo Weinhold	if ((*node)->balance_factor < LEFT) {
33325294551SIngo Weinhold		// tree is left heavy
33425294551SIngo Weinhold		AVLTreeNode** left = &(*node)->left;
33525294551SIngo Weinhold		if ((*left)->balance_factor == LEFT) {
33625294551SIngo Weinhold			// left left heavy
33725294551SIngo Weinhold			_RotateRight(node);
33825294551SIngo Weinhold		} else {
33925294551SIngo Weinhold			// left right heavy
34025294551SIngo Weinhold			_RotateLeft(left);
34125294551SIngo Weinhold			_RotateRight(node);
34225294551SIngo Weinhold		}
34325294551SIngo Weinhold		return OK;
34425294551SIngo Weinhold	}
34525294551SIngo Weinhold
34625294551SIngo Weinhold	if ((*node)->balance_factor == BALANCED)
34725294551SIngo Weinhold		return OK;
34825294551SIngo Weinhold
34925294551SIngo Weinhold	return HEIGHT_CHANGED;
35025294551SIngo Weinhold}
35125294551SIngo Weinhold
35225294551SIngo Weinhold
35325294551SIngo Weinholdint
354a54549a8SIngo WeinholdAVLTreeBase::_BalanceInsertRight(AVLTreeNode** node)
35525294551SIngo Weinhold{
35625294551SIngo Weinhold	if ((*node)->balance_factor > RIGHT) {
35725294551SIngo Weinhold		// tree is right heavy
35825294551SIngo Weinhold		AVLTreeNode** right = &(*node)->right;
35925294551SIngo Weinhold		if ((*right)->balance_factor == RIGHT) {
36025294551SIngo Weinhold			// right right heavy
36125294551SIngo Weinhold			_RotateLeft(node);
36225294551SIngo Weinhold		} else {
36325294551SIngo Weinhold			// right left heavy
36425294551SIngo Weinhold			_RotateRight(right);
36525294551SIngo Weinhold			_RotateLeft(node);
36625294551SIngo Weinhold		}
36725294551SIngo Weinhold		return OK;
36825294551SIngo Weinhold	}
36925294551SIngo Weinhold
37025294551SIngo Weinhold	if ((*node)->balance_factor == BALANCED)
37125294551SIngo Weinhold		return OK;
37225294551SIngo Weinhold
37325294551SIngo Weinhold	return HEIGHT_CHANGED;
37425294551SIngo Weinhold}
37525294551SIngo Weinhold
37625294551SIngo Weinhold
37725294551SIngo Weinholdint
378a54549a8SIngo WeinholdAVLTreeBase::_Insert(AVLTreeNode* nodeToInsert)
37925294551SIngo Weinhold{
38025294551SIngo Weinhold	struct node_info {
38125294551SIngo Weinhold		AVLTreeNode**	node;
38225294551SIngo Weinhold		bool			left;
38325294551SIngo Weinhold	};
38425294551SIngo Weinhold
38525294551SIngo Weinhold	node_info stack[kMaxAVLTreeHeight];
38625294551SIngo Weinhold	node_info* top = stack;
38725294551SIngo Weinhold	const node_info* const bottom = stack;
38825294551SIngo Weinhold	AVLTreeNode** node = &fRoot;
38925294551SIngo Weinhold
39025294551SIngo Weinhold	// find insertion point
39125294551SIngo Weinhold	while (*node) {
39225294551SIngo Weinhold		int cmp = fCompare->CompareNodes(nodeToInsert, *node);
39325294551SIngo Weinhold		if (cmp == 0)	// duplicate node
39425294551SIngo Weinhold			return DUPLICATE;
39525294551SIngo Weinhold		else {
39625294551SIngo Weinhold			top->node = node;
39725294551SIngo Weinhold			if (cmp < 0) {
39825294551SIngo Weinhold				top->left = true;
39925294551SIngo Weinhold				node = &(*node)->left;
40025294551SIngo Weinhold			} else {
40125294551SIngo Weinhold				top->left = false;
40225294551SIngo Weinhold				node = &(*node)->right;
40325294551SIngo Weinhold			}
40425294551SIngo Weinhold			top++;
40525294551SIngo Weinhold		}
40625294551SIngo Weinhold	}
40725294551SIngo Weinhold
40825294551SIngo Weinhold	// insert node
40925294551SIngo Weinhold	*node = nodeToInsert;
41025294551SIngo Weinhold	nodeToInsert->left = NULL;
41125294551SIngo Weinhold	nodeToInsert->right = NULL;
41225294551SIngo Weinhold	nodeToInsert->balance_factor = BALANCED;
41325294551SIngo Weinhold	fNodeCount++;
41425294551SIngo Weinhold
41525294551SIngo Weinhold	if (top == bottom)
41625294551SIngo Weinhold		nodeToInsert->parent = NULL;
41725294551SIngo Weinhold	else
41825294551SIngo Weinhold		(*node)->parent = *top[-1].node;
41925294551SIngo Weinhold
42025294551SIngo Weinhold	// do the balancing
42125294551SIngo Weinhold	int result = HEIGHT_CHANGED;
42225294551SIngo Weinhold	while (result == HEIGHT_CHANGED && top != bottom) {
42325294551SIngo Weinhold		top--;
42425294551SIngo Weinhold		node = top->node;
42525294551SIngo Weinhold		if (top->left) {
42625294551SIngo Weinhold			// left
42725294551SIngo Weinhold			(*node)->balance_factor--;
42825294551SIngo Weinhold			result = _BalanceInsertLeft(node);
42925294551SIngo Weinhold		} else {
43025294551SIngo Weinhold			// right
43125294551SIngo Weinhold			(*node)->balance_factor++;
43225294551SIngo Weinhold			result = _BalanceInsertRight(node);
43325294551SIngo Weinhold		}
43425294551SIngo Weinhold	}
43525294551SIngo Weinhold
43625294551SIngo Weinhold	return result;
43725294551SIngo Weinhold}
43825294551SIngo Weinhold
43925294551SIngo Weinhold
44025294551SIngo Weinholdint
441a54549a8SIngo WeinholdAVLTreeBase::_BalanceRemoveLeft(AVLTreeNode** node)
44225294551SIngo Weinhold{
44325294551SIngo Weinhold	int result = HEIGHT_CHANGED;
44425294551SIngo Weinhold
44525294551SIngo Weinhold	if ((*node)->balance_factor > RIGHT) {
44625294551SIngo Weinhold		// tree is right heavy
44725294551SIngo Weinhold		AVLTreeNode** right = &(*node)->right;
44825294551SIngo Weinhold		if ((*right)->balance_factor == RIGHT) {
44925294551SIngo Weinhold			// right right heavy
45025294551SIngo Weinhold			_RotateLeft(node);
45125294551SIngo Weinhold		} else if ((*right)->balance_factor == BALANCED) {
45225294551SIngo Weinhold			// right none heavy
45325294551SIngo Weinhold			_RotateLeft(node);
45425294551SIngo Weinhold			result = OK;
45525294551SIngo Weinhold		} else {
45625294551SIngo Weinhold			// right left heavy
45725294551SIngo Weinhold			_RotateRight(right);
45825294551SIngo Weinhold			_RotateLeft(node);
45925294551SIngo Weinhold		}
46025294551SIngo Weinhold	} else if ((*node)->balance_factor == RIGHT)
46125294551SIngo Weinhold		result = OK;
46225294551SIngo Weinhold
46325294551SIngo Weinhold	return result;
46425294551SIngo Weinhold}
46525294551SIngo Weinhold
46625294551SIngo Weinhold
46725294551SIngo Weinholdint
468a54549a8SIngo WeinholdAVLTreeBase::_BalanceRemoveRight(AVLTreeNode** node)
46925294551SIngo Weinhold{
47025294551SIngo Weinhold	int result = HEIGHT_CHANGED;
47125294551SIngo Weinhold
47225294551SIngo Weinhold	if ((*node)->balance_factor < LEFT) {
47325294551SIngo Weinhold		// tree is left heavy
47425294551SIngo Weinhold		AVLTreeNode** left = &(*node)->left;
47525294551SIngo Weinhold		if ((*left)->balance_factor == LEFT) {
47625294551SIngo Weinhold			// left left heavy
47725294551SIngo Weinhold			_RotateRight(node);
47825294551SIngo Weinhold		} else if ((*left)->balance_factor == BALANCED) {
47925294551SIngo Weinhold			// left none heavy
48025294551SIngo Weinhold			_RotateRight(node);
48125294551SIngo Weinhold			result = OK;
48225294551SIngo Weinhold		} else {
48325294551SIngo Weinhold			// left right heavy
48425294551SIngo Weinhold			_RotateLeft(left);
48525294551SIngo Weinhold			_RotateRight(node);
48625294551SIngo Weinhold		}
48725294551SIngo Weinhold	} else if ((*node)->balance_factor == LEFT)
48825294551SIngo Weinhold		result = OK;
48925294551SIngo Weinhold
49025294551SIngo Weinhold	return result;
49125294551SIngo Weinhold}
49225294551SIngo Weinhold
49325294551SIngo Weinhold
49425294551SIngo Weinholdint
495a54549a8SIngo WeinholdAVLTreeBase::_RemoveRightMostChild(AVLTreeNode** node, AVLTreeNode** foundNode)
49625294551SIngo Weinhold{
49725294551SIngo Weinhold	AVLTreeNode** stack[kMaxAVLTreeHeight];
49825294551SIngo Weinhold	AVLTreeNode*** top = stack;
49925294551SIngo Weinhold	const AVLTreeNode* const* const* const bottom = stack;
50025294551SIngo Weinhold
50125294551SIngo Weinhold	// find the child
50225294551SIngo Weinhold	while ((*node)->right) {
50325294551SIngo Weinhold		*top = node;
50425294551SIngo Weinhold		top++;
50525294551SIngo Weinhold		node = &(*node)->right;
50625294551SIngo Weinhold	}
50725294551SIngo Weinhold
50825294551SIngo Weinhold	// found the rightmost child: remove it
50925294551SIngo Weinhold	// the found node might have a left child: replace the node with the
51025294551SIngo Weinhold	// child
51125294551SIngo Weinhold	*foundNode = *node;
51225294551SIngo Weinhold	AVLTreeNode* left = (*node)->left;
51325294551SIngo Weinhold	if (left)
51425294551SIngo Weinhold		left->parent = (*node)->parent;
51525294551SIngo Weinhold	*node = left;
51625294551SIngo Weinhold	(*foundNode)->left = NULL;
51725294551SIngo Weinhold	(*foundNode)->parent = NULL;
51825294551SIngo Weinhold
51925294551SIngo Weinhold	// balancing
52025294551SIngo Weinhold	int result = HEIGHT_CHANGED;
52125294551SIngo Weinhold	while (result == HEIGHT_CHANGED && top != bottom) {
52225294551SIngo Weinhold		top--;
52325294551SIngo Weinhold		node = *top;
52425294551SIngo Weinhold		(*node)->balance_factor--;
52525294551SIngo Weinhold		result = _BalanceRemoveRight(node);
52625294551SIngo Weinhold	}
52725294551SIngo Weinhold
52825294551SIngo Weinhold	return result;
52925294551SIngo Weinhold}
53025294551SIngo Weinhold
53125294551SIngo Weinhold
53225294551SIngo Weinholdint
533a54549a8SIngo WeinholdAVLTreeBase::_Remove(AVLTreeNode* node)
53425294551SIngo Weinhold{
53525294551SIngo Weinhold	if (!node)
53625294551SIngo Weinhold		return NOT_FOUND;
53725294551SIngo Weinhold
53825294551SIngo Weinhold	// remove node
53925294551SIngo Weinhold	AVLTreeNode* parent = node->parent;
54025294551SIngo Weinhold	bool isLeft = (parent && parent->left == node);
54125294551SIngo Weinhold	AVLTreeNode** nodeP
54225294551SIngo Weinhold		= (parent ? (isLeft ? &parent->left : &parent->right) : &fRoot);
54325294551SIngo Weinhold	int result = HEIGHT_CHANGED;
54425294551SIngo Weinhold	AVLTreeNode* replace = NULL;
54525294551SIngo Weinhold
54625294551SIngo Weinhold	if (node->left && node->right) {
54725294551SIngo Weinhold		// node has two children
54825294551SIngo Weinhold		result = _RemoveRightMostChild(&node->left, &replace);
54925294551SIngo Weinhold		replace->parent = parent;
55025294551SIngo Weinhold		replace->left = node->left;
55125294551SIngo Weinhold		replace->right = node->right;
55225294551SIngo Weinhold		if (node->left)	// check necessary, if node->left == replace
55325294551SIngo Weinhold			node->left->parent = replace;
55425294551SIngo Weinhold		node->right->parent = replace;
55525294551SIngo Weinhold		replace->balance_factor = node->balance_factor;
55625294551SIngo Weinhold		*nodeP = replace;
55725294551SIngo Weinhold
55825294551SIngo Weinhold		if (result == HEIGHT_CHANGED) {
55925294551SIngo Weinhold			replace->balance_factor++;
56025294551SIngo Weinhold			result = _BalanceRemoveLeft(nodeP);
56125294551SIngo Weinhold		}
56225294551SIngo Weinhold	} else if (node->left) {
56325294551SIngo Weinhold		// node has only left child
56425294551SIngo Weinhold		replace = node->left;
56525294551SIngo Weinhold		replace->parent = parent;
56625294551SIngo Weinhold		replace->balance_factor = node->balance_factor + 1;
56725294551SIngo Weinhold		*nodeP = replace;
56825294551SIngo Weinhold	} else if (node->right) {
56925294551SIngo Weinhold		// node has only right child
57025294551SIngo Weinhold		replace = node->right;
57125294551SIngo Weinhold		replace->parent = node->parent;
57225294551SIngo Weinhold		replace->balance_factor = node->balance_factor - 1;
57325294551SIngo Weinhold		*nodeP = replace;
57425294551SIngo Weinhold	} else {
57525294551SIngo Weinhold		// node has no child
57625294551SIngo Weinhold		*nodeP = NULL;
57725294551SIngo Weinhold	}
57825294551SIngo Weinhold
57925294551SIngo Weinhold	fNodeCount--;
58025294551SIngo Weinhold
58125294551SIngo Weinhold	// do the balancing
58225294551SIngo Weinhold	while (result == HEIGHT_CHANGED && parent) {
58325294551SIngo Weinhold		node = parent;
58425294551SIngo Weinhold		parent = node->parent;
58525294551SIngo Weinhold		bool oldIsLeft = isLeft;
58625294551SIngo Weinhold		isLeft = (parent && parent->left == node);
58725294551SIngo Weinhold		nodeP = (parent ? (isLeft ? &parent->left : &parent->right) : &fRoot);
58825294551SIngo Weinhold		if (oldIsLeft) {
58925294551SIngo Weinhold			// left
59025294551SIngo Weinhold			node->balance_factor++;
59125294551SIngo Weinhold			result = _BalanceRemoveLeft(nodeP);
59225294551SIngo Weinhold		} else {
59325294551SIngo Weinhold			// right
59425294551SIngo Weinhold			node->balance_factor--;
59525294551SIngo Weinhold			result = _BalanceRemoveRight(nodeP);
59625294551SIngo Weinhold		}
59725294551SIngo Weinhold	}
59825294551SIngo Weinhold
59925294551SIngo Weinhold	return result;
60025294551SIngo Weinhold}
601a54549a8SIngo Weinhold
602a54549a8SIngo Weinhold
603a54549a8SIngo Weinholdint
604a54549a8SIngo WeinholdAVLTreeBase::_CheckTree(AVLTreeNode* parent, AVLTreeNode* node,
605a54549a8SIngo Weinhold	int& _nodeCount) const
606a54549a8SIngo Weinhold{
607a54549a8SIngo Weinhold	if (node == NULL) {
608a54549a8SIngo Weinhold		_nodeCount = 0;
609a54549a8SIngo Weinhold		return 0;
610a54549a8SIngo Weinhold	}
611a54549a8SIngo Weinhold
612a54549a8SIngo Weinhold	if (parent != node->parent) {
613a54549a8SIngo Weinhold		CHECK_FAILED("AVLTreeBase::_CheckTree(): node %p parent mismatch: "
614a54549a8SIngo Weinhold			"%p vs %p", node, parent, node->parent);
615a54549a8SIngo Weinhold	}
616a54549a8SIngo Weinhold
617a54549a8SIngo Weinhold	int leftNodeCount;
618a54549a8SIngo Weinhold	int leftDepth = _CheckTree(node, node->left, leftNodeCount);
619a54549a8SIngo Weinhold
620a54549a8SIngo Weinhold	int rightNodeCount;
621a54549a8SIngo Weinhold	int rightDepth = _CheckTree(node, node->right, rightNodeCount);
622a54549a8SIngo Weinhold
623a54549a8SIngo Weinhold	int balance = rightDepth - leftDepth;
624a54549a8SIngo Weinhold	if (balance < LEFT || balance > RIGHT) {
625a54549a8SIngo Weinhold		CHECK_FAILED("AVLTreeBase::_CheckTree(): unbalanced subtree: %p", node);
626a54549a8SIngo Weinhold	} else if (balance != node->balance_factor) {
627a54549a8SIngo Weinhold		CHECK_FAILED("AVLTreeBase::_CheckTree(): subtree %p balance mismatch: "
628a54549a8SIngo Weinhold			"%d vs %d", node, balance, node->balance_factor);
629a54549a8SIngo Weinhold	}
630a54549a8SIngo Weinhold
631a54549a8SIngo Weinhold	_nodeCount = leftNodeCount + rightNodeCount + 1;
632a54549a8SIngo Weinhold	return std::max(leftDepth, rightDepth) + 1;
633a54549a8SIngo Weinhold}