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_H
6#define _KERNEL_UTIL_AVL_TREE_H
7
8
9#include <util/AVLTreeBase.h>
10
11
12/*
13	To be implemented by the definition:
14
15	typedef int	Key;
16	typedef Foo	Value;
17
18	AVLTreeNode*		GetAVLTreeNode(Value* value) const;
19	Value*				GetValue(AVLTreeNode* node) const;
20	int					Compare(const Key& a, const Value* b) const;
21	int					Compare(const Value* a, const Value* b) const;
22*/
23
24
25
26template<typename Definition>
27class AVLTree : protected AVLTreeCompare {
28private:
29	typedef typename Definition::Key	Key;
30	typedef typename Definition::Value	Value;
31
32public:
33	class Iterator;
34	class ConstIterator;
35
36public:
37								AVLTree();
38								AVLTree(const Definition& definition);
39	virtual						~AVLTree();
40
41	inline	int					Count() const	{ return fTree.Count(); }
42	inline	bool				IsEmpty() const	{ return fTree.IsEmpty(); }
43	inline	void				Clear();
44
45			Value*				RootNode() const;
46
47			Value*				Previous(Value* value) const;
48			Value*				Next(Value* value) const;
49
50			Value*				LeftMost(Value* value) const;
51			Value*				RightMost(Value* value) const;
52
53	inline	Iterator			GetIterator();
54	inline	ConstIterator		GetIterator() const;
55
56	inline	Iterator			GetIterator(Value* value);
57	inline	ConstIterator		GetIterator(Value* value) const;
58
59			Value*				Find(const Key& key) const;
60			Value*				FindClosest(const Key& key, bool less) const;
61
62			status_t			Insert(Value* value, Iterator* iterator = NULL);
63			Value*				Remove(const Key& key);
64			bool				Remove(Value* key);
65
66			void				CheckTree() const	{ fTree.CheckTree(); }
67
68protected:
69	// AVLTreeCompare
70	virtual	int					CompareKeyNode(const void* key,
71									const AVLTreeNode* node);
72	virtual	int					CompareNodes(const AVLTreeNode* node1,
73									const AVLTreeNode* node2);
74
75	// definition shortcuts
76	inline	AVLTreeNode*		_GetAVLTreeNode(Value* value) const;
77	inline	Value*				_GetValue(const AVLTreeNode* node) const;
78	inline	int					_Compare(const Key& a, const Value* b);
79	inline	int					_Compare(const Value* a, const Value* b);
80
81protected:
82			friend class Iterator;
83			friend class ConstIterator;
84
85			AVLTreeBase			fTree;
86			Definition			fDefinition;
87
88public:
89	// (need to implement it here, otherwise gcc 2.95.3 chokes)
90	class Iterator : public ConstIterator {
91	public:
92		inline Iterator()
93			:
94			ConstIterator()
95		{
96		}
97
98		inline Iterator(const Iterator& other)
99			:
100			ConstIterator(other)
101		{
102		}
103
104		inline void Remove()
105		{
106			if (AVLTreeNode* node = ConstIterator::fTreeIterator.Remove()) {
107				AVLTree<Definition>* parent
108					= const_cast<AVLTree<Definition>*>(
109						ConstIterator::fParent);
110			}
111		}
112
113	private:
114		inline Iterator(AVLTree<Definition>* parent,
115			const AVLTreeIterator& treeIterator)
116			: ConstIterator(parent, treeIterator)
117		{
118		}
119
120		friend class AVLTree<Definition>;
121	};
122};
123
124
125template<typename Definition>
126class AVLTree<Definition>::ConstIterator {
127public:
128	inline ConstIterator()
129		:
130		fParent(NULL),
131		fTreeIterator()
132	{
133	}
134
135	inline ConstIterator(const ConstIterator& other)
136		:
137		fParent(other.fParent),
138		fTreeIterator(other.fTreeIterator)
139	{
140	}
141
142	inline bool HasCurrent() const
143	{
144		return fTreeIterator.Current();
145	}
146
147	inline Value* Current()
148	{
149		if (AVLTreeNode* node = fTreeIterator.Current())
150			return fParent->_GetValue(node);
151		return NULL;
152	}
153
154	inline bool HasNext() const
155	{
156		return fTreeIterator.HasNext();
157	}
158
159	inline Value* Next()
160	{
161		if (AVLTreeNode* node = fTreeIterator.Next())
162			return fParent->_GetValue(node);
163		return NULL;
164	}
165
166	inline Value* Previous()
167	{
168		if (AVLTreeNode* node = fTreeIterator.Previous())
169			return fParent->_GetValue(node);
170		return NULL;
171	}
172
173	inline ConstIterator& operator=(const ConstIterator& other)
174	{
175		fParent = other.fParent;
176		fTreeIterator = other.fTreeIterator;
177		return *this;
178	}
179
180protected:
181	inline ConstIterator(const AVLTree<Definition>* parent,
182		const AVLTreeIterator& treeIterator)
183	{
184		fParent = parent;
185		fTreeIterator = treeIterator;
186	}
187
188	friend class AVLTree<Definition>;
189
190	const AVLTree<Definition>*	fParent;
191	AVLTreeIterator				fTreeIterator;
192};
193
194
195template<typename Definition>
196AVLTree<Definition>::AVLTree()
197	:
198	fTree(this),
199	fDefinition()
200{
201}
202
203
204template<typename Definition>
205AVLTree<Definition>::AVLTree(const Definition& definition)
206	:
207	fTree(this),
208	fDefinition(definition)
209{
210}
211
212
213template<typename Definition>
214AVLTree<Definition>::~AVLTree()
215{
216}
217
218
219template<typename Definition>
220inline void
221AVLTree<Definition>::Clear()
222{
223	fTree.MakeEmpty();
224}
225
226
227template<typename Definition>
228inline typename AVLTree<Definition>::Value*
229AVLTree<Definition>::RootNode() const
230{
231	if (AVLTreeNode* root = fTree.Root())
232		return _GetValue(root);
233	return NULL;
234}
235
236
237template<typename Definition>
238inline typename AVLTree<Definition>::Value*
239AVLTree<Definition>::Previous(Value* value) const
240{
241	if (value == NULL)
242		return NULL;
243
244	AVLTreeNode* node = fTree.Previous(_GetAVLTreeNode(value));
245	return node != NULL ? _GetValue(node) : NULL;
246}
247
248
249template<typename Definition>
250inline typename AVLTree<Definition>::Value*
251AVLTree<Definition>::Next(Value* value) const
252{
253	if (value == NULL)
254		return NULL;
255
256	AVLTreeNode* node = fTree.Next(_GetAVLTreeNode(value));
257	return node != NULL ? _GetValue(node) : NULL;
258}
259
260
261template<typename Definition>
262inline typename AVLTree<Definition>::Value*
263AVLTree<Definition>::LeftMost(Value* value) const
264{
265	if (value == NULL)
266		return NULL;
267
268	AVLTreeNode* node = fTree.LeftMost(_GetAVLTreeNode(value));
269	return node != NULL ? _GetValue(node) : NULL;
270}
271
272
273template<typename Definition>
274inline typename AVLTree<Definition>::Value*
275AVLTree<Definition>::RightMost(Value* value) const
276{
277	if (value == NULL)
278		return NULL;
279
280	AVLTreeNode* node = fTree.RightMost(_GetAVLTreeNode(value));
281	return node != NULL ? _GetValue(node) : NULL;
282}
283
284
285template<typename Definition>
286inline typename AVLTree<Definition>::Iterator
287AVLTree<Definition>::GetIterator()
288{
289	return Iterator(this, fTree.GetIterator());
290}
291
292
293template<typename Definition>
294inline typename AVLTree<Definition>::ConstIterator
295AVLTree<Definition>::GetIterator() const
296{
297	return ConstIterator(this, fTree.GetIterator());
298}
299
300
301template<typename Definition>
302inline typename AVLTree<Definition>::Iterator
303AVLTree<Definition>::GetIterator(Value* value)
304{
305	return Iterator(this, fTree.GetIterator(_GetAVLTreeNode(value)));
306}
307
308
309template<typename Definition>
310inline typename AVLTree<Definition>::ConstIterator
311AVLTree<Definition>::GetIterator(Value* value) const
312{
313	return ConstIterator(this, fTree.GetIterator(_GetAVLTreeNode(value)));
314}
315
316
317template<typename Definition>
318typename AVLTree<Definition>::Value*
319AVLTree<Definition>::Find(const Key& key) const
320{
321	if (AVLTreeNode* node = fTree.Find(&key))
322		return _GetValue(node);
323	return NULL;
324}
325
326
327template<typename Definition>
328typename AVLTree<Definition>::Value*
329AVLTree<Definition>::FindClosest(const Key& key, bool less) const
330{
331	if (AVLTreeNode* node = fTree.FindClosest(&key, less))
332		return _GetValue(node);
333	return NULL;
334}
335
336
337template<typename Definition>
338status_t
339AVLTree<Definition>::Insert(Value* value, Iterator* iterator)
340{
341	AVLTreeNode* node = _GetAVLTreeNode(value);
342	status_t error = fTree.Insert(node);
343	if (error != B_OK)
344		return error;
345
346	if (iterator != NULL)
347		*iterator = Iterator(this, fTree.GetIterator(node));
348
349	return B_OK;
350}
351
352
353template<typename Definition>
354typename AVLTree<Definition>::Value*
355AVLTree<Definition>::Remove(const Key& key)
356{
357	AVLTreeNode* node = fTree.Remove(&key);
358	return node != NULL ? _GetValue(node) : NULL;
359}
360
361
362template<typename Definition>
363bool
364AVLTree<Definition>::Remove(Value* value)
365{
366	return fTree.Remove(_GetAVLTreeNode(value));
367}
368
369
370template<typename Definition>
371int
372AVLTree<Definition>::CompareKeyNode(const void* key,
373	const AVLTreeNode* node)
374{
375	return _Compare(*(const Key*)key, _GetValue(node));
376}
377
378
379template<typename Definition>
380int
381AVLTree<Definition>::CompareNodes(const AVLTreeNode* node1,
382	const AVLTreeNode* node2)
383{
384	return _Compare(_GetValue(node1), _GetValue(node2));
385}
386
387
388template<typename Definition>
389inline AVLTreeNode*
390AVLTree<Definition>::_GetAVLTreeNode(Value* value) const
391{
392	return fDefinition.GetAVLTreeNode(value);
393}
394
395
396template<typename Definition>
397inline typename AVLTree<Definition>::Value*
398AVLTree<Definition>::_GetValue(const AVLTreeNode* node) const
399{
400	return fDefinition.GetValue(const_cast<AVLTreeNode*>(node));
401}
402
403
404template<typename Definition>
405inline int
406AVLTree<Definition>::_Compare(const Key& a, const Value* b)
407{
408	return fDefinition.Compare(a, b);
409}
410
411
412template<typename Definition>
413inline int
414AVLTree<Definition>::_Compare(const Value* a, const Value* b)
415{
416	return fDefinition.Compare(a, b);
417}
418
419
420#endif	// _KERNEL_UTIL_AVL_TREE_H
421