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