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