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 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 123 template<typename Definition> 124 class AVLTree<Definition>::ConstIterator { 125 public: 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 178 protected: 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> 194 AVLTree<Definition>::AVLTree() 195 : 196 fTree(this), 197 fDefinition() 198 { 199 } 200 201 202 template<typename Definition> 203 AVLTree<Definition>::AVLTree(const Definition& definition) 204 : 205 fTree(this), 206 fDefinition(definition) 207 { 208 } 209 210 211 template<typename Definition> 212 AVLTree<Definition>::~AVLTree() 213 { 214 } 215 216 217 template<typename Definition> 218 inline void 219 AVLTree<Definition>::Clear() 220 { 221 fTree.MakeEmpty(); 222 } 223 224 225 template<typename Definition> 226 inline typename AVLTree<Definition>::Value* 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* 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* 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* 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* 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* 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* 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 303 AVLTree<Definition>::GetIterator() 304 { 305 return Iterator(this, fTree.GetIterator()); 306 } 307 308 309 template<typename Definition> 310 inline typename AVLTree<Definition>::ConstIterator 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 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 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* 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* 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 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* 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 380 AVLTree<Definition>::Remove(Value* value) 381 { 382 return fTree.Remove(_GetAVLTreeNode(value)); 383 } 384 385 386 template<typename Definition> 387 int 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 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* 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* 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 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 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