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
26 template<typename Definition>
27 class AVLTree : protected AVLTreeCompare {
28 private:
29 typedef typename Definition::Key Key;
30 typedef typename Definition::Value Value;
31
32 public:
33 class Iterator;
34 class ConstIterator;
35
36 public:
37 AVLTree();
38 AVLTree(const Definition& definition);
39 virtual ~AVLTree();
40
Count()41 inline int Count() const { return fTree.Count(); }
IsEmpty()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
CheckTree()68 void CheckTree() const { fTree.CheckTree(); }
69
70 protected:
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
83 protected:
84 friend class Iterator;
85 friend class ConstIterator;
86
87 AVLTreeBase fTree;
88 Definition fDefinition;
89
90 public:
91 // (need to implement it here, otherwise gcc 2.95.3 chokes)
92 class Iterator : public ConstIterator {
93 public:
Iterator()94 inline Iterator()
95 :
96 ConstIterator()
97 {
98 }
99
Iterator(const Iterator & other)100 inline Iterator(const Iterator& other)
101 :
102 ConstIterator(other)
103 {
104 }
105
Remove()106 inline void Remove()
107 {
108 ConstIterator::fTreeIterator.Remove();
109 }
110
111 private:
Iterator(AVLTree<Definition> * parent,const AVLTreeIterator & treeIterator)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
123 template<typename Definition>
124 class AVLTree<Definition>::ConstIterator {
125 public:
ConstIterator()126 inline ConstIterator()
127 :
128 fParent(NULL),
129 fTreeIterator()
130 {
131 }
132
ConstIterator(const ConstIterator & other)133 inline ConstIterator(const ConstIterator& other)
134 :
135 fParent(other.fParent),
136 fTreeIterator(other.fTreeIterator)
137 {
138 }
139
HasCurrent()140 inline bool HasCurrent() const
141 {
142 return fTreeIterator.Current();
143 }
144
Current()145 inline Value* Current()
146 {
147 if (AVLTreeNode* node = fTreeIterator.Current())
148 return fParent->_GetValue(node);
149 return NULL;
150 }
151
HasNext()152 inline bool HasNext() const
153 {
154 return fTreeIterator.HasNext();
155 }
156
Next()157 inline Value* Next()
158 {
159 if (AVLTreeNode* node = fTreeIterator.Next())
160 return fParent->_GetValue(node);
161 return NULL;
162 }
163
Previous()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
178 protected:
ConstIterator(const AVLTree<Definition> * parent,const AVLTreeIterator & treeIterator)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
193 template<typename Definition>
AVLTree()194 AVLTree<Definition>::AVLTree()
195 :
196 fTree(this),
197 fDefinition()
198 {
199 }
200
201
202 template<typename Definition>
AVLTree(const Definition & definition)203 AVLTree<Definition>::AVLTree(const Definition& definition)
204 :
205 fTree(this),
206 fDefinition(definition)
207 {
208 }
209
210
211 template<typename Definition>
~AVLTree()212 AVLTree<Definition>::~AVLTree()
213 {
214 }
215
216
217 template<typename Definition>
218 inline void
Clear()219 AVLTree<Definition>::Clear()
220 {
221 fTree.MakeEmpty();
222 }
223
224
225 template<typename Definition>
226 inline typename AVLTree<Definition>::Value*
RootNode()227 AVLTree<Definition>::RootNode() const
228 {
229 if (AVLTreeNode* root = fTree.Root())
230 return _GetValue(root);
231 return NULL;
232 }
233
234
235 template<typename Definition>
236 inline typename AVLTree<Definition>::Value*
Previous(Value * value)237 AVLTree<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
247 template<typename Definition>
248 inline typename AVLTree<Definition>::Value*
Next(Value * value)249 AVLTree<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
259 template<typename Definition>
260 inline typename AVLTree<Definition>::Value*
LeftMost()261 AVLTree<Definition>::LeftMost() const
262 {
263 AVLTreeNode* node = fTree.LeftMost();
264 return node != NULL ? _GetValue(node) : NULL;
265 }
266
267
268 template<typename Definition>
269 inline typename AVLTree<Definition>::Value*
LeftMost(Value * value)270 AVLTree<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
280 template<typename Definition>
281 inline typename AVLTree<Definition>::Value*
RightMost()282 AVLTree<Definition>::RightMost() const
283 {
284 AVLTreeNode* node = fTree.RightMost();
285 return node != NULL ? _GetValue(node) : NULL;
286 }
287
288
289 template<typename Definition>
290 inline typename AVLTree<Definition>::Value*
RightMost(Value * value)291 AVLTree<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
301 template<typename Definition>
302 inline typename AVLTree<Definition>::Iterator
GetIterator()303 AVLTree<Definition>::GetIterator()
304 {
305 return Iterator(this, fTree.GetIterator());
306 }
307
308
309 template<typename Definition>
310 inline typename AVLTree<Definition>::ConstIterator
GetIterator()311 AVLTree<Definition>::GetIterator() const
312 {
313 return ConstIterator(this, fTree.GetIterator());
314 }
315
316
317 template<typename Definition>
318 inline typename AVLTree<Definition>::Iterator
GetIterator(Value * value)319 AVLTree<Definition>::GetIterator(Value* value)
320 {
321 return Iterator(this, fTree.GetIterator(_GetAVLTreeNode(value)));
322 }
323
324
325 template<typename Definition>
326 inline typename AVLTree<Definition>::ConstIterator
GetIterator(Value * value)327 AVLTree<Definition>::GetIterator(Value* value) const
328 {
329 return ConstIterator(this, fTree.GetIterator(_GetAVLTreeNode(value)));
330 }
331
332
333 template<typename Definition>
334 typename AVLTree<Definition>::Value*
Find(const Key & key)335 AVLTree<Definition>::Find(const Key& key) const
336 {
337 if (AVLTreeNode* node = fTree.Find(&key))
338 return _GetValue(node);
339 return NULL;
340 }
341
342
343 template<typename Definition>
344 typename AVLTree<Definition>::Value*
FindClosest(const Key & key,bool less)345 AVLTree<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
353 template<typename Definition>
354 status_t
Insert(Value * value,Iterator * iterator)355 AVLTree<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
369 template<typename Definition>
370 typename AVLTree<Definition>::Value*
Remove(const Key & key)371 AVLTree<Definition>::Remove(const Key& key)
372 {
373 AVLTreeNode* node = fTree.Remove(&key);
374 return node != NULL ? _GetValue(node) : NULL;
375 }
376
377
378 template<typename Definition>
379 bool
Remove(Value * value)380 AVLTree<Definition>::Remove(Value* value)
381 {
382 return fTree.Remove(_GetAVLTreeNode(value));
383 }
384
385
386 template<typename Definition>
387 int
CompareKeyNode(const void * key,const AVLTreeNode * node)388 AVLTree<Definition>::CompareKeyNode(const void* key,
389 const AVLTreeNode* node)
390 {
391 return _Compare(*(const Key*)key, _GetValue(node));
392 }
393
394
395 template<typename Definition>
396 int
CompareNodes(const AVLTreeNode * node1,const AVLTreeNode * node2)397 AVLTree<Definition>::CompareNodes(const AVLTreeNode* node1,
398 const AVLTreeNode* node2)
399 {
400 return _Compare(_GetValue(node1), _GetValue(node2));
401 }
402
403
404 template<typename Definition>
405 inline AVLTreeNode*
_GetAVLTreeNode(Value * value)406 AVLTree<Definition>::_GetAVLTreeNode(Value* value) const
407 {
408 return fDefinition.GetAVLTreeNode(value);
409 }
410
411
412 template<typename Definition>
413 inline typename AVLTree<Definition>::Value*
_GetValue(const AVLTreeNode * node)414 AVLTree<Definition>::_GetValue(const AVLTreeNode* node) const
415 {
416 return fDefinition.GetValue(const_cast<AVLTreeNode*>(node));
417 }
418
419
420 template<typename Definition>
421 inline int
_Compare(const Key & a,const Value * b)422 AVLTree<Definition>::_Compare(const Key& a, const Value* b)
423 {
424 return fDefinition.Compare(a, b);
425 }
426
427
428 template<typename Definition>
429 inline int
_Compare(const Value * a,const Value * b)430 AVLTree<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