1// TwoKeyAVLTree.h 2// 3// Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de) 4// 5// Permission is hereby granted, free of charge, to any person obtaining a 6// copy of this software and associated documentation files (the "Software"), 7// to deal in the Software without restriction, including without limitation 8// the rights to use, copy, modify, merge, publish, distribute, sublicense, 9// and/or sell copies of the Software, and to permit persons to whom the 10// Software is furnished to do so, subject to the following conditions: 11// 12// The above copyright notice and this permission notice shall be included in 13// all copies or substantial portions of the Software. 14// 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 21// DEALINGS IN THE SOFTWARE. 22// 23// Except as contained in this notice, the name of a copyright holder shall 24// not be used in advertising or otherwise to promote the sale, use or other 25// dealings in this Software without prior written authorization of the 26// copyright holder. 27 28#ifndef TWO_KEY_AVL_TREE_H 29#define TWO_KEY_AVL_TREE_H 30 31#include "AVLTree.h" 32 33// TwoKeyAVLTreeKey 34template<typename PrimaryKey, typename SecondaryKey> 35class TwoKeyAVLTreeKey { 36public: 37 inline TwoKeyAVLTreeKey(const PrimaryKey &primary, 38 const SecondaryKey &secondary) 39 : primary(primary), 40 secondary(secondary), 41 use_secondary(true) 42 { 43 } 44 45 inline TwoKeyAVLTreeKey(const PrimaryKey *primary) 46 : primary(primary), 47 secondary(NULL), 48 use_secondary(false) 49 { 50 } 51 52 PrimaryKey primary; 53 SecondaryKey secondary; 54 bool use_secondary; 55}; 56 57// TwoKeyAVLTreeKeyCompare 58template<typename PrimaryKey, typename SecondaryKey, 59 typename PrimaryKeyCompare, typename SecondaryKeyCompare> 60class TwoKeyAVLTreeKeyCompare { 61private: 62 typedef TwoKeyAVLTreeKey<PrimaryKey, SecondaryKey> Key; 63 64public: 65 inline TwoKeyAVLTreeKeyCompare(const PrimaryKeyCompare &primary, 66 const SecondaryKeyCompare &secondary) 67 : fPrimaryKeyCompare(primary), fSecondaryKeyCompare(secondary) {} 68 69 inline int operator()(const Key &a, const Key &b) const 70 { 71 int result = fPrimaryKeyCompare(a.primary, b.primary); 72 if (result == 0 && a.use_secondary && b.use_secondary) 73 result = fSecondaryKeyCompare(a.secondary, b.secondary); 74 return result; 75 } 76 77private: 78 PrimaryKeyCompare fPrimaryKeyCompare; 79 SecondaryKeyCompare fSecondaryKeyCompare; 80}; 81 82// TwoKeyAVLTreeGetKey 83template<typename Value, typename PrimaryKey, typename SecondaryKey, 84 typename GetPrimaryKey, typename GetSecondaryKey> 85class TwoKeyAVLTreeGetKey 86{ 87private: 88 typedef TwoKeyAVLTreeKey<PrimaryKey, SecondaryKey> Key; 89 90public: 91 TwoKeyAVLTreeGetKey(const GetPrimaryKey &getPrimary, 92 const GetSecondaryKey &getSecondary) 93 : fGetPrimaryKey(getPrimary), 94 fGetSecondaryKey(getSecondary) 95 { 96 } 97 98 inline Key operator()(const Value &a) const 99 { 100 return Key(fGetPrimaryKey(a), fGetSecondaryKey(a)); 101 } 102 103private: 104 GetPrimaryKey fGetPrimaryKey; 105 GetSecondaryKey fGetSecondaryKey; 106}; 107 108// for convenience 109#define TWO_KEY_AVL_TREE_TEMPLATE_LIST template<typename Value, \ 110 typename PrimaryKey, typename PrimaryKeyCompare, \ 111 typename GetPrimaryKey, typename SecondaryKey, typename Node, \ 112 typename SecondaryKeyCompare, typename GetSecondaryKey, \ 113 typename NodeAllocator, typename GetValue> 114#define TWO_KEY_AVL_TREE_CLASS_NAME TwoKeyAVLTree<Value, PrimaryKey, \ 115 PrimaryKeyCompare, GetPrimaryKey, SecondaryKey, Node, \ 116 SecondaryKeyCompare, GetSecondaryKey, NodeAllocator, GetValue> 117 118// TwoKeyAVLTree 119template<typename Value, typename PrimaryKey, 120 typename PrimaryKeyCompare, typename GetPrimaryKey, 121 typename SecondaryKey = Value, 122 typename Node = AVLTreeStandardNode<Value>, 123 typename SecondaryKeyCompare = AVLTreeStandardCompare<SecondaryKey>, 124 typename GetSecondaryKey = AVLTreeStandardGetKey<Value, SecondaryKey>, 125 typename NodeAllocator = AVLTreeStandardNodeAllocator<Value, Node>, 126 typename GetValue = AVLTreeStandardGetValue<Value, Node> > 127class TwoKeyAVLTree : private AVLTree<Value, 128 TwoKeyAVLTreeKey<PrimaryKey, SecondaryKey>, Node, 129 TwoKeyAVLTreeKeyCompare<PrimaryKey, SecondaryKey, PrimaryKeyCompare, 130 SecondaryKeyCompare>, 131 TwoKeyAVLTreeGetKey<Value, PrimaryKey, SecondaryKey, GetPrimaryKey, 132 GetSecondaryKey>, 133 NodeAllocator, GetValue> { 134private: 135 typedef TwoKeyAVLTreeKey<PrimaryKey, SecondaryKey> Key; 136 typedef TwoKeyAVLTreeKeyCompare<PrimaryKey, SecondaryKey, 137 PrimaryKeyCompare, SecondaryKeyCompare> 138 KeyCompare; 139 typedef TwoKeyAVLTreeGetKey<Value, PrimaryKey, SecondaryKey, GetPrimaryKey, 140 GetSecondaryKey> 141 GetKey; 142 typedef AVLTree<Value, Key, Node, KeyCompare, GetKey, NodeAllocator, 143 GetValue> BaseClass; 144public: 145 typedef typename BaseClass::Iterator Iterator; 146 147public: 148 TwoKeyAVLTree(); 149 TwoKeyAVLTree(const PrimaryKeyCompare &primaryCompare, 150 const GetPrimaryKey &getPrimary, 151 const SecondaryKeyCompare &secondaryCompare, 152 const GetSecondaryKey &getSecondary, 153 const NodeAllocator &allocator, 154 const GetValue &getValue); 155 ~TwoKeyAVLTree(); 156 157 inline int CountItems() const { return BaseClass::CountItems(); } 158 159 Value *FindFirst(const PrimaryKey &key, Iterator *iterator = NULL); 160 Value *FindLast(const PrimaryKey &key, Iterator *iterator = NULL); 161 inline Value *Find(const PrimaryKey &primaryKey, 162 const SecondaryKey &secondaryKey, 163 Iterator *iterator = NULL); 164 165 inline void GetIterator(Iterator *iterator, bool reverse = false); 166 167 inline status_t Insert(const Value &value, Iterator *iterator = NULL); 168 inline status_t Remove(const PrimaryKey &primaryKey, 169 const SecondaryKey &secondaryKey); 170 inline void Remove(Iterator &iterator); 171 172private: 173 PrimaryKeyCompare fPrimaryKeyCompare; 174 GetPrimaryKey fGetPrimaryKey; 175}; 176 177 178// constructor 179TWO_KEY_AVL_TREE_TEMPLATE_LIST 180TWO_KEY_AVL_TREE_CLASS_NAME::TwoKeyAVLTree() 181 : BaseClass(KeyCompare(PrimaryKeyCompare(), SecondaryKeyCompare()), 182 GetKey(GetPrimaryKey(), GetSecondaryKey()), 183 NodeAllocator(), GetValue()) 184{ 185} 186 187// constructor 188TWO_KEY_AVL_TREE_TEMPLATE_LIST 189TWO_KEY_AVL_TREE_CLASS_NAME::TwoKeyAVLTree( 190 const PrimaryKeyCompare &primaryCompare, const GetPrimaryKey &getPrimary, 191 const SecondaryKeyCompare &secondaryCompare, 192 const GetSecondaryKey &getSecondary, const NodeAllocator &allocator, 193 const GetValue &getValue) 194 : BaseClass(KeyCompare(primaryCompare, secondaryCompare), 195 GetKey(getPrimary, getSecondary), 196 allocator, getValue), 197 fPrimaryKeyCompare(primaryCompare), 198 fGetPrimaryKey(getPrimary) 199 200{ 201} 202 203// destructor 204TWO_KEY_AVL_TREE_TEMPLATE_LIST 205TWO_KEY_AVL_TREE_CLASS_NAME::~TwoKeyAVLTree() 206{ 207} 208 209// FindFirst 210TWO_KEY_AVL_TREE_TEMPLATE_LIST 211Value * 212TWO_KEY_AVL_TREE_CLASS_NAME::FindFirst(const PrimaryKey &key, 213 Iterator *iterator) 214{ 215 Node *node = BaseClass::fRoot; 216 while (node) { 217 int cmp = fPrimaryKeyCompare(key, fGetPrimaryKey(fGetValue(node))); 218 if (cmp == 0) { 219 // found a matching node, now get the left-most node with that key 220 while (node->left && fPrimaryKeyCompare(key, 221 fGetPrimaryKey(fGetValue(node->left))) == 0) { 222 node = node->left; 223 } 224 if (iterator) 225 _InitIterator(iterator, node); 226 return &fGetValue(node); 227 } 228 if (cmp < 0) 229 node = node->left; 230 else 231 node = node->right; 232 } 233 return NULL; 234} 235 236// FindLast 237TWO_KEY_AVL_TREE_TEMPLATE_LIST 238Value * 239TWO_KEY_AVL_TREE_CLASS_NAME::FindLast(const PrimaryKey &key, 240 Iterator *iterator) 241{ 242 Node *node = BaseClass::fRoot; 243 while (node) { 244 int cmp = fPrimaryKeyCompare(key, fGetPrimaryKey(fGetValue(node))); 245 if (cmp == 0) { 246 // found a matching node, now get the right-most node with that key 247 while (node->right && fPrimaryKeyCompare(key, 248 fGetPrimaryKey(fGetValue(node->right))) == 0) { 249 node = node->right; 250 } 251 if (iterator) 252 _InitIterator(iterator, node); 253 return &fGetValue(node); 254 } 255 if (cmp < 0) 256 node = node->left; 257 else 258 node = node->right; 259 } 260 return NULL; 261} 262 263// Find 264TWO_KEY_AVL_TREE_TEMPLATE_LIST 265Value * 266TWO_KEY_AVL_TREE_CLASS_NAME::Find(const PrimaryKey &primaryKey, 267 const SecondaryKey &secondaryKey, 268 Iterator *iterator) 269{ 270 return BaseClass::Find(Key(primaryKey, secondaryKey), iterator); 271} 272 273// GetIterator 274TWO_KEY_AVL_TREE_TEMPLATE_LIST 275void 276TWO_KEY_AVL_TREE_CLASS_NAME::GetIterator(Iterator *iterator, bool reverse) 277{ 278 BaseClass::GetIterator(iterator, reverse); 279} 280 281// Insert 282TWO_KEY_AVL_TREE_TEMPLATE_LIST 283status_t 284TWO_KEY_AVL_TREE_CLASS_NAME::Insert(const Value &value, Iterator *iterator) 285{ 286 return BaseClass::Insert(value, iterator); 287} 288 289// Remove 290TWO_KEY_AVL_TREE_TEMPLATE_LIST 291status_t 292TWO_KEY_AVL_TREE_CLASS_NAME::Remove(const PrimaryKey &primaryKey, 293 const SecondaryKey &secondaryKey) 294{ 295 return BaseClass::Remove(Key(primaryKey, secondaryKey)); 296} 297 298// Remove 299TWO_KEY_AVL_TREE_TEMPLATE_LIST 300void 301TWO_KEY_AVL_TREE_CLASS_NAME::Remove(Iterator &iterator) 302{ 303 BaseClass::Remove(iterator); 304} 305 306#endif // TWO_KEY_AVL_TREE_H 307