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_BASE_H 6 #define _KERNEL_UTIL_AVL_TREE_BASE_H 7 8 9 #include <SupportDefs.h> 10 11 12 class AVLTreeIterator; 13 14 15 struct AVLTreeNode { 16 AVLTreeNode* parent; 17 AVLTreeNode* left; 18 AVLTreeNode* right; 19 int balance_factor; 20 }; 21 22 23 class AVLTreeCompare { 24 public: 25 virtual ~AVLTreeCompare(); 26 27 virtual int CompareKeyNode(const void* key, 28 const AVLTreeNode* node) = 0; 29 virtual int CompareNodes(const AVLTreeNode* node1, 30 const AVLTreeNode* node2) = 0; 31 }; 32 33 34 class AVLTreeBase { 35 public: 36 AVLTreeBase(AVLTreeCompare* compare); 37 ~AVLTreeBase(); 38 39 inline int Count() const { return fNodeCount; } 40 inline bool IsEmpty() const { return (fNodeCount == 0); } 41 void MakeEmpty(); 42 43 inline AVLTreeNode* Root() const { return fRoot; } 44 45 AVLTreeNode* LeftMost(AVLTreeNode* node) const; 46 AVLTreeNode* RightMost(AVLTreeNode* node) const; 47 48 AVLTreeNode* Previous(AVLTreeNode* node) const; 49 AVLTreeNode* Next(AVLTreeNode* node) const; 50 51 inline AVLTreeIterator GetIterator() const; 52 inline AVLTreeIterator GetIterator(AVLTreeNode* node) const; 53 54 AVLTreeNode* Find(const void* key) const; 55 AVLTreeNode* FindClosest(const void* key, bool less) const; 56 57 status_t Insert(AVLTreeNode* element); 58 AVLTreeNode* Remove(const void* key); 59 bool Remove(AVLTreeNode* element); 60 61 void CheckTree() const; 62 63 private: 64 enum { 65 NOT_FOUND = -3, 66 DUPLICATE = -2, 67 NO_MEMORY = -1, 68 OK = 0, 69 HEIGHT_CHANGED = 1, 70 71 LEFT = -1, 72 BALANCED = 0, 73 RIGHT = 1, 74 }; 75 76 // rotations 77 void _RotateRight(AVLTreeNode** nodeP); 78 void _RotateLeft(AVLTreeNode** nodeP); 79 80 // insert 81 int _BalanceInsertLeft(AVLTreeNode** node); 82 int _BalanceInsertRight(AVLTreeNode** node); 83 int _Insert(AVLTreeNode* nodeToInsert); 84 85 // remove 86 int _BalanceRemoveLeft(AVLTreeNode** node); 87 int _BalanceRemoveRight(AVLTreeNode** node); 88 int _RemoveRightMostChild(AVLTreeNode** node, 89 AVLTreeNode** foundNode); 90 int _Remove(AVLTreeNode* node); 91 92 int _CheckTree(AVLTreeNode* parent, 93 AVLTreeNode* node, int& _nodeCount) const; 94 95 AVLTreeNode* fRoot; 96 int fNodeCount; 97 AVLTreeCompare* fCompare; 98 }; 99 100 101 // AVLTreeIterator 102 class AVLTreeIterator { 103 public: 104 inline AVLTreeIterator() 105 : 106 fParent(NULL), 107 fCurrent(NULL), 108 fNext(NULL) 109 { 110 } 111 112 inline AVLTreeIterator(const AVLTreeIterator& other) 113 : 114 fParent(other.fParent), 115 fCurrent(other.fCurrent), 116 fNext(other.fNext) 117 { 118 } 119 120 inline AVLTreeNode* Current() const 121 { 122 return fCurrent; 123 } 124 125 inline bool HasNext() const 126 { 127 return fNext; 128 } 129 130 inline AVLTreeNode* Next() 131 { 132 fCurrent = fNext; 133 134 if (fNext) 135 fNext = fParent->Next(fNext); 136 137 return fCurrent; 138 } 139 140 inline AVLTreeNode* Previous() 141 { 142 if (fCurrent) { 143 fNext = fCurrent; 144 fCurrent = fParent->Previous(fCurrent); 145 } else if (fNext) 146 fCurrent = fParent->Previous(fNext); 147 148 return fCurrent; 149 } 150 151 inline AVLTreeNode* Remove() 152 { 153 if (!fCurrent) 154 return NULL; 155 156 AVLTreeNode* node = fCurrent; 157 fCurrent = NULL; 158 159 return (const_cast<AVLTreeBase*>(fParent)->Remove(node) ? node : NULL); 160 } 161 162 inline AVLTreeIterator& operator=(const AVLTreeIterator& other) 163 { 164 fParent = other.fParent; 165 fCurrent = other.fCurrent; 166 fNext = other.fNext; 167 return *this; 168 } 169 170 private: 171 inline AVLTreeIterator(const AVLTreeBase* parent, AVLTreeNode* current, 172 AVLTreeNode* next) 173 : 174 fParent(parent), 175 fCurrent(current), 176 fNext(next) 177 { 178 } 179 180 protected: 181 friend class AVLTreeBase; 182 183 const AVLTreeBase* fParent; 184 AVLTreeNode* fCurrent; 185 AVLTreeNode* fNext; 186 }; 187 188 189 // GetIterator 190 inline AVLTreeIterator 191 AVLTreeBase::GetIterator() const 192 { 193 return AVLTreeIterator(this, NULL, LeftMost(fRoot)); 194 } 195 196 197 // GetIterator 198 inline AVLTreeIterator 199 AVLTreeBase::GetIterator(AVLTreeNode* node) const 200 { 201 return AVLTreeIterator(this, node, Next(node)); 202 } 203 204 205 #endif // _KERNEL_UTIL_AVL_TREE_BASE_H 206