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