headers/private/kernel/util/AVLTree.h

   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