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