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 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 68 protected: 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 81 protected: 82 friend class Iterator; 83 friend class ConstIterator; 84 85 AVLTreeBase fTree; 86 Definition fDefinition; 87 88 public: 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 125 template<typename Definition> 126 class AVLTree<Definition>::ConstIterator { 127 public: 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 180 protected: 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 195 template<typename Definition> 196 AVLTree<Definition>::AVLTree() 197 : 198 fTree(this), 199 fDefinition() 200 { 201 } 202 203 204 template<typename Definition> 205 AVLTree<Definition>::AVLTree(const Definition& definition) 206 : 207 fTree(this), 208 fDefinition(definition) 209 { 210 } 211 212 213 template<typename Definition> 214 AVLTree<Definition>::~AVLTree() 215 { 216 } 217 218 219 template<typename Definition> 220 inline void 221 AVLTree<Definition>::Clear() 222 { 223 fTree.MakeEmpty(); 224 } 225 226 227 template<typename Definition> 228 inline typename AVLTree<Definition>::Value* 229 AVLTree<Definition>::RootNode() const 230 { 231 if (AVLTreeNode* root = fTree.Root()) 232 return _GetValue(root); 233 return NULL; 234 } 235 236 237 template<typename Definition> 238 inline typename AVLTree<Definition>::Value* 239 AVLTree<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 249 template<typename Definition> 250 inline typename AVLTree<Definition>::Value* 251 AVLTree<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 261 template<typename Definition> 262 inline typename AVLTree<Definition>::Value* 263 AVLTree<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 273 template<typename Definition> 274 inline typename AVLTree<Definition>::Value* 275 AVLTree<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 285 template<typename Definition> 286 inline typename AVLTree<Definition>::Iterator 287 AVLTree<Definition>::GetIterator() 288 { 289 return Iterator(this, fTree.GetIterator()); 290 } 291 292 293 template<typename Definition> 294 inline typename AVLTree<Definition>::ConstIterator 295 AVLTree<Definition>::GetIterator() const 296 { 297 return ConstIterator(this, fTree.GetIterator()); 298 } 299 300 301 template<typename Definition> 302 inline typename AVLTree<Definition>::Iterator 303 AVLTree<Definition>::GetIterator(Value* value) 304 { 305 return Iterator(this, fTree.GetIterator(_GetAVLTreeNode(value))); 306 } 307 308 309 template<typename Definition> 310 inline typename AVLTree<Definition>::ConstIterator 311 AVLTree<Definition>::GetIterator(Value* value) const 312 { 313 return ConstIterator(this, fTree.GetIterator(_GetAVLTreeNode(value))); 314 } 315 316 317 template<typename Definition> 318 typename AVLTree<Definition>::Value* 319 AVLTree<Definition>::Find(const Key& key) const 320 { 321 if (AVLTreeNode* node = fTree.Find(&key)) 322 return _GetValue(node); 323 return NULL; 324 } 325 326 327 template<typename Definition> 328 typename AVLTree<Definition>::Value* 329 AVLTree<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 337 template<typename Definition> 338 status_t 339 AVLTree<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 353 template<typename Definition> 354 typename AVLTree<Definition>::Value* 355 AVLTree<Definition>::Remove(const Key& key) 356 { 357 AVLTreeNode* node = fTree.Remove(&key); 358 return node != NULL ? _GetValue(node) : NULL; 359 } 360 361 362 template<typename Definition> 363 bool 364 AVLTree<Definition>::Remove(Value* value) 365 { 366 return fTree.Remove(_GetAVLTreeNode(value)); 367 } 368 369 370 template<typename Definition> 371 int 372 AVLTree<Definition>::CompareKeyNode(const void* key, 373 const AVLTreeNode* node) 374 { 375 return _Compare(*(const Key*)key, _GetValue(node)); 376 } 377 378 379 template<typename Definition> 380 int 381 AVLTree<Definition>::CompareNodes(const AVLTreeNode* node1, 382 const AVLTreeNode* node2) 383 { 384 return _Compare(_GetValue(node1), _GetValue(node2)); 385 } 386 387 388 template<typename Definition> 389 inline AVLTreeNode* 390 AVLTree<Definition>::_GetAVLTreeNode(Value* value) const 391 { 392 return fDefinition.GetAVLTreeNode(value); 393 } 394 395 396 template<typename Definition> 397 inline typename AVLTree<Definition>::Value* 398 AVLTree<Definition>::_GetValue(const AVLTreeNode* node) const 399 { 400 return fDefinition.GetValue(const_cast<AVLTreeNode*>(node)); 401 } 402 403 404 template<typename Definition> 405 inline int 406 AVLTree<Definition>::_Compare(const Key& a, const Value* b) 407 { 408 return fDefinition.Compare(a, b); 409 } 410 411 412 template<typename Definition> 413 inline int 414 AVLTree<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