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 34 template<typename PrimaryKey, typename SecondaryKey> 35 class TwoKeyAVLTreeKey { 36 public: 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 58 template<typename PrimaryKey, typename SecondaryKey, 59 typename PrimaryKeyCompare, typename SecondaryKeyCompare> 60 class TwoKeyAVLTreeKeyCompare { 61 private: 62 typedef TwoKeyAVLTreeKey<PrimaryKey, SecondaryKey> Key; 63 64 public: 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 77 private: 78 PrimaryKeyCompare fPrimaryKeyCompare; 79 SecondaryKeyCompare fSecondaryKeyCompare; 80 }; 81 82 // TwoKeyAVLTreeGetKey 83 template<typename Value, typename PrimaryKey, typename SecondaryKey, 84 typename GetPrimaryKey, typename GetSecondaryKey> 85 class TwoKeyAVLTreeGetKey 86 { 87 private: 88 typedef TwoKeyAVLTreeKey<PrimaryKey, SecondaryKey> Key; 89 90 public: 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 103 private: 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 119 template<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> > 127 class 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> { 134 private: 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; 144 145 public: 146 TwoKeyAVLTree(); 147 TwoKeyAVLTree(const PrimaryKeyCompare &primaryCompare, 148 const GetPrimaryKey &getPrimary, 149 const SecondaryKeyCompare &secondaryCompare, 150 const GetSecondaryKey &getSecondary, 151 const NodeAllocator &allocator, 152 const GetValue &getValue); 153 ~TwoKeyAVLTree(); 154 155 inline int CountItems() const { return BaseClass::CountItems(); } 156 157 Value *FindFirst(const PrimaryKey &key, Iterator *iterator = NULL); 158 Value *FindLast(const PrimaryKey &key, Iterator *iterator = NULL); 159 inline Value *Find(const PrimaryKey &primaryKey, 160 const SecondaryKey &secondaryKey, 161 Iterator *iterator = NULL); 162 163 inline void GetIterator(Iterator *iterator, bool reverse = false); 164 165 inline status_t Insert(const Value &value, Iterator *iterator = NULL); 166 inline status_t Remove(const PrimaryKey &primaryKey, 167 const SecondaryKey &secondaryKey); 168 inline void Remove(Iterator &iterator); 169 170 private: 171 PrimaryKeyCompare fPrimaryKeyCompare; 172 GetPrimaryKey fGetPrimaryKey; 173 }; 174 175 176 // constructor 177 TWO_KEY_AVL_TREE_TEMPLATE_LIST 178 TWO_KEY_AVL_TREE_CLASS_NAME::TwoKeyAVLTree() 179 : BaseClass(KeyCompare(PrimaryKeyCompare(), SecondaryKeyCompare()), 180 GetKey(GetPrimaryKey(), GetSecondaryKey()), 181 NodeAllocator(), GetValue()) 182 { 183 } 184 185 // constructor 186 TWO_KEY_AVL_TREE_TEMPLATE_LIST 187 TWO_KEY_AVL_TREE_CLASS_NAME::TwoKeyAVLTree( 188 const PrimaryKeyCompare &primaryCompare, const GetPrimaryKey &getPrimary, 189 const SecondaryKeyCompare &secondaryCompare, 190 const GetSecondaryKey &getSecondary, const NodeAllocator &allocator, 191 const GetValue &getValue) 192 : BaseClass(KeyCompare(primaryCompare, secondaryCompare), 193 GetKey(getPrimary, getSecondary), 194 allocator, getValue), 195 fPrimaryKeyCompare(primaryCompare), 196 fGetPrimaryKey(getPrimary) 197 198 { 199 } 200 201 // destructor 202 TWO_KEY_AVL_TREE_TEMPLATE_LIST 203 TWO_KEY_AVL_TREE_CLASS_NAME::~TwoKeyAVLTree() 204 { 205 } 206 207 // FindFirst 208 TWO_KEY_AVL_TREE_TEMPLATE_LIST 209 Value * 210 TWO_KEY_AVL_TREE_CLASS_NAME::FindFirst(const PrimaryKey &key, 211 Iterator *iterator) 212 { 213 Node *node = fRoot; 214 while (node) { 215 int cmp = fPrimaryKeyCompare(key, fGetPrimaryKey(fGetValue(node))); 216 if (cmp == 0) { 217 // found a matching node, now get the left-most node with that key 218 while (node->left && fPrimaryKeyCompare(key, 219 fGetPrimaryKey(fGetValue(node->left))) == 0) { 220 node = node->left; 221 } 222 if (iterator) 223 _InitIterator(iterator, node); 224 return &fGetValue(node); 225 } 226 if (cmp < 0) 227 node = node->left; 228 else 229 node = node->right; 230 } 231 return NULL; 232 } 233 234 // FindLast 235 TWO_KEY_AVL_TREE_TEMPLATE_LIST 236 Value * 237 TWO_KEY_AVL_TREE_CLASS_NAME::FindLast(const PrimaryKey &key, 238 Iterator *iterator) 239 { 240 Node *node = fRoot; 241 while (node) { 242 int cmp = fPrimaryKeyCompare(key, fGetPrimaryKey(fGetValue(node))); 243 if (cmp == 0) { 244 // found a matching node, now get the right-most node with that key 245 while (node->right && fPrimaryKeyCompare(key, 246 fGetPrimaryKey(fGetValue(node->right))) == 0) { 247 node = node->right; 248 } 249 if (iterator) 250 _InitIterator(iterator, node); 251 return &fGetValue(node); 252 } 253 if (cmp < 0) 254 node = node->left; 255 else 256 node = node->right; 257 } 258 return NULL; 259 } 260 261 // Find 262 TWO_KEY_AVL_TREE_TEMPLATE_LIST 263 Value * 264 TWO_KEY_AVL_TREE_CLASS_NAME::Find(const PrimaryKey &primaryKey, 265 const SecondaryKey &secondaryKey, 266 Iterator *iterator) 267 { 268 return BaseClass::Find(Key(primaryKey, secondaryKey), iterator); 269 } 270 271 // GetIterator 272 TWO_KEY_AVL_TREE_TEMPLATE_LIST 273 void 274 TWO_KEY_AVL_TREE_CLASS_NAME::GetIterator(Iterator *iterator, bool reverse) 275 { 276 BaseClass::GetIterator(iterator, reverse); 277 } 278 279 // Insert 280 TWO_KEY_AVL_TREE_TEMPLATE_LIST 281 status_t 282 TWO_KEY_AVL_TREE_CLASS_NAME::Insert(const Value &value, Iterator *iterator) 283 { 284 return BaseClass::Insert(value, iterator); 285 } 286 287 // Remove 288 TWO_KEY_AVL_TREE_TEMPLATE_LIST 289 status_t 290 TWO_KEY_AVL_TREE_CLASS_NAME::Remove(const PrimaryKey &primaryKey, 291 const SecondaryKey &secondaryKey) 292 { 293 return BaseClass::Remove(Key(primaryKey, secondaryKey)); 294 } 295 296 // Remove 297 TWO_KEY_AVL_TREE_TEMPLATE_LIST 298 void 299 TWO_KEY_AVL_TREE_CLASS_NAME::Remove(Iterator &iterator) 300 { 301 BaseClass::Remove(iterator); 302 } 303 304 #endif // TWO_KEY_AVL_TREE_H 305