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