1/*
2 * Copyright 2003-2009, Ingo Weinhold <ingo_weinhold@gmx.de>.
3 * Distributed under the terms of the MIT License.
4 */
5#ifndef _KERNEL_UTIL_AVL_TREE_BASE_H
6#define _KERNEL_UTIL_AVL_TREE_BASE_H
7
8
9#ifndef FS_SHELL
10#	include <SupportDefs.h>
11#else
12#	include <algorithm>
13#	include "fssh_api_wrapper.h"
14#endif
15
16
17class AVLTreeIterator;
18
19
20struct AVLTreeNode {
21	AVLTreeNode*	parent;
22	AVLTreeNode*	left;
23	AVLTreeNode*	right;
24	int				balance_factor;
25};
26
27
28class AVLTreeCompare {
29public:
30	virtual						~AVLTreeCompare();
31
32	virtual	int					CompareKeyNode(const void* key,
33									const AVLTreeNode* node) = 0;
34	virtual	int					CompareNodes(const AVLTreeNode* node1,
35									const AVLTreeNode* node2) = 0;
36};
37
38
39class AVLTreeBase {
40public:
41								AVLTreeBase(AVLTreeCompare* compare);
42								~AVLTreeBase();
43
44	inline	int					Count() const	{ return fNodeCount; }
45	inline	bool				IsEmpty() const	{ return (fNodeCount == 0); }
46			void				MakeEmpty();
47
48	inline	AVLTreeNode*		Root() const	{ return fRoot; }
49
50			AVLTreeNode*		LeftMost(AVLTreeNode* node) const;
51			AVLTreeNode*		RightMost(AVLTreeNode* node) const;
52
53			AVLTreeNode*		Previous(AVLTreeNode* node) const;
54			AVLTreeNode*		Next(AVLTreeNode* node) const;
55
56	inline	AVLTreeIterator		GetIterator() const;
57	inline	AVLTreeIterator		GetIterator(AVLTreeNode* node) const;
58
59			AVLTreeNode*		Find(const void* key) const;
60			AVLTreeNode*		FindClosest(const void* key, bool less) const;
61
62			status_t			Insert(AVLTreeNode* element);
63			AVLTreeNode*		Remove(const void* key);
64			bool				Remove(AVLTreeNode* element);
65
66			void				CheckTree() const;
67
68private:
69			enum {
70				NOT_FOUND		= -3,
71				DUPLICATE		= -2,
72				NO_MEMORY		= -1,
73				OK				= 0,
74				HEIGHT_CHANGED	= 1,
75
76				LEFT			= -1,
77				BALANCED		= 0,
78				RIGHT			= 1,
79			};
80
81			// rotations
82			void				_RotateRight(AVLTreeNode** nodeP);
83			void				_RotateLeft(AVLTreeNode** nodeP);
84
85			// insert
86			int					_BalanceInsertLeft(AVLTreeNode** node);
87			int					_BalanceInsertRight(AVLTreeNode** node);
88			int					_Insert(AVLTreeNode* nodeToInsert);
89
90			// remove
91			int					_BalanceRemoveLeft(AVLTreeNode** node);
92			int					_BalanceRemoveRight(AVLTreeNode** node);
93			int					_RemoveRightMostChild(AVLTreeNode** node,
94									AVLTreeNode** foundNode);
95			int					_Remove(AVLTreeNode* node);
96
97			int					_CheckTree(AVLTreeNode* parent,
98									AVLTreeNode* node, int& _nodeCount) const;
99
100			AVLTreeNode*		fRoot;
101			int					fNodeCount;
102			AVLTreeCompare*		fCompare;
103};
104
105
106// AVLTreeIterator
107class AVLTreeIterator {
108public:
109	inline AVLTreeIterator()
110		:
111		fParent(NULL),
112		fCurrent(NULL),
113		fNext(NULL)
114	{
115	}
116
117	inline AVLTreeIterator(const AVLTreeIterator& other)
118		:
119		fParent(other.fParent),
120		fCurrent(other.fCurrent),
121		fNext(other.fNext)
122	{
123	}
124
125	inline AVLTreeNode* Current() const
126	{
127		return fCurrent;
128	}
129
130	inline bool HasNext() const
131	{
132		return fNext;
133	}
134
135	inline AVLTreeNode* Next()
136	{
137		fCurrent = fNext;
138
139		if (fNext)
140			fNext = fParent->Next(fNext);
141
142		return fCurrent;
143	}
144
145	inline AVLTreeNode* Previous()
146	{
147		if (fCurrent) {
148			fNext = fCurrent;
149			fCurrent = fParent->Previous(fCurrent);
150		} else if (fNext)
151			fCurrent = fParent->Previous(fNext);
152
153		return fCurrent;
154	}
155
156	inline AVLTreeNode* Remove()
157	{
158		if (!fCurrent)
159			return NULL;
160
161		AVLTreeNode* node = fCurrent;
162		fCurrent = NULL;
163
164		return (const_cast<AVLTreeBase*>(fParent)->Remove(node) ? node : NULL);
165	}
166
167	inline AVLTreeIterator& operator=(const AVLTreeIterator& other)
168	{
169		fParent = other.fParent;
170		fCurrent = other.fCurrent;
171		fNext = other.fNext;
172		return *this;
173	}
174
175private:
176	inline AVLTreeIterator(const AVLTreeBase* parent, AVLTreeNode* current,
177			AVLTreeNode* next)
178		:
179		fParent(parent),
180		fCurrent(current),
181		fNext(next)
182	{
183	}
184
185protected:
186	friend class AVLTreeBase;
187
188	const AVLTreeBase*	fParent;
189	AVLTreeNode*		fCurrent;
190	AVLTreeNode*		fNext;
191};
192
193
194// GetIterator
195inline AVLTreeIterator
196AVLTreeBase::GetIterator() const
197{
198	return AVLTreeIterator(this, NULL, LeftMost(fRoot));
199}
200
201
202// GetIterator
203inline AVLTreeIterator
204AVLTreeBase::GetIterator(AVLTreeNode* node) const
205{
206	return AVLTreeIterator(this, node, Next(node));
207}
208
209
210#endif	// _KERNEL_UTIL_AVL_TREE_BASE_H
211