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