1 /* 2 * Copyright 2013 Haiku, Inc. All rights reserved. 3 * Distributed under the terms of the MIT License. 4 * 5 * Authors: 6 * Paweł Dziepak, pdziepak@quarnos.org 7 */ 8 #ifndef KERNEL_UTIL_MIN_MAX_HEAP_H 9 #define KERNEL_UTIL_MIN_MAX_HEAP_H 10 11 12 #include <debug.h> 13 14 #include <SupportDefs.h> 15 16 17 template<typename Element, typename Key> 18 struct MinMaxHeapLink { 19 MinMaxHeapLink(); 20 21 bool fMinTree; 22 int fIndex; 23 Key fKey; 24 }; 25 26 template<typename Element, typename Key> 27 class MinMaxHeapLinkImpl { 28 private: 29 typedef MinMaxHeapLink<Element, Key> Link; 30 31 public: 32 inline Link* GetMinMaxHeapLink(); 33 34 private: 35 Link fMinMaxHeapLink; 36 }; 37 38 template<typename Element, typename Key> 39 class MinMaxHeapStandardGetLink { 40 private: 41 typedef MinMaxHeapLink<Element, Key> Link; 42 43 public: 44 inline Link* operator()(Element* element) const; 45 }; 46 47 template<typename Element, typename Key, 48 MinMaxHeapLink<Element, Key> Element::*LinkMember> 49 class MinMaxHeapMemberGetLink { 50 private: 51 typedef MinMaxHeapLink<Element, Key> Link; 52 53 public: 54 inline Link* operator()(Element* element) const; 55 }; 56 57 template<typename Key> 58 class MinMaxHeapCompare { 59 public: 60 inline bool operator()(Key a, Key b); 61 }; 62 63 #define MIN_MAX_HEAP_TEMPLATE_LIST \ 64 template<typename Element, typename Key, typename Compare, typename GetLink> 65 #define MIN_MAX_HEAP_CLASS_NAME MinMaxHeap<Element, Key, Compare, GetLink> 66 67 template<typename Element, typename Key, 68 typename Compare = MinMaxHeapCompare<Key>, 69 typename GetLink = MinMaxHeapStandardGetLink<Element, Key> > 70 class MinMaxHeap { 71 public: 72 MinMaxHeap(); 73 MinMaxHeap(int initialSize); 74 ~MinMaxHeap(); 75 76 inline Element* PeekMinimum(int32 index = 0) const; 77 inline Element* PeekMaximum(int32 index = 0) const; 78 79 static const Key& GetKey(Element* element); 80 81 inline void ModifyKey(Element* element, Key newKey); 82 83 inline void RemoveMinimum(); 84 inline void RemoveMaximum(); 85 86 inline status_t Insert(Element* element, Key key); 87 88 private: 89 status_t _GrowHeap(int minimalSize = 0); 90 91 void _MoveUp(MinMaxHeapLink<Element, Key>* link); 92 void _MoveDown(MinMaxHeapLink<Element, Key>* link); 93 bool _ChangeTree(MinMaxHeapLink<Element, Key>* link); 94 95 void _RemoveLast(bool minTree); 96 97 Element** fMinElements; 98 int fMinLastElement; 99 100 Element** fMaxElements; 101 int fMaxLastElement; 102 103 int fSize; 104 105 static Compare sCompare; 106 static GetLink sGetLink; 107 }; 108 109 110 #if KDEBUG 111 template<typename Element, typename Key> 112 MinMaxHeapLink<Element, Key>::MinMaxHeapLink() 113 : 114 fIndex(-1) 115 { 116 } 117 #else 118 template<typename Element, typename Key> 119 MinMaxHeapLink<Element, Key>::MinMaxHeapLink() 120 { 121 } 122 #endif 123 124 125 template<typename Element, typename Key> 126 MinMaxHeapLink<Element, Key>* 127 MinMaxHeapLinkImpl<Element, Key>::GetMinMaxHeapLink() 128 { 129 return &fMinMaxHeapLink; 130 } 131 132 133 template<typename Element, typename Key> 134 MinMaxHeapLink<Element, Key>* 135 MinMaxHeapStandardGetLink<Element, Key>::operator()(Element* element) const 136 { 137 return element->GetMinMaxHeapLink(); 138 } 139 140 141 template<typename Element, typename Key, 142 MinMaxHeapLink<Element, Key> Element::*LinkMember> 143 MinMaxHeapLink<Element, Key>* 144 MinMaxHeapMemberGetLink<Element, Key, LinkMember>::operator()( 145 Element* element) const 146 { 147 return &(element->*LinkMember); 148 } 149 150 151 template<typename Key> 152 bool 153 MinMaxHeapCompare<Key>::operator()(Key a, Key b) 154 { 155 return a < b; 156 } 157 158 159 MIN_MAX_HEAP_TEMPLATE_LIST 160 MIN_MAX_HEAP_CLASS_NAME::MinMaxHeap() 161 : 162 fMinElements(NULL), 163 fMinLastElement(0), 164 fMaxElements(NULL), 165 fMaxLastElement(0), 166 fSize(0) 167 { 168 } 169 170 171 MIN_MAX_HEAP_TEMPLATE_LIST 172 MIN_MAX_HEAP_CLASS_NAME::MinMaxHeap(int initialSize) 173 : 174 fMinElements(NULL), 175 fMinLastElement(0), 176 fMaxElements(NULL), 177 fMaxLastElement(0), 178 fSize(0) 179 { 180 _GrowHeap(initialSize); 181 } 182 183 184 MIN_MAX_HEAP_TEMPLATE_LIST 185 MIN_MAX_HEAP_CLASS_NAME::~MinMaxHeap() 186 { 187 free(fMinElements); 188 } 189 190 191 MIN_MAX_HEAP_TEMPLATE_LIST 192 Element* 193 MIN_MAX_HEAP_CLASS_NAME::PeekMinimum(int32 index) const 194 { 195 if (index < fMinLastElement) 196 return fMinElements[index]; 197 else if (index - fMinLastElement < fMaxLastElement) { 198 return fMaxElements[fMaxLastElement - (index - fMinLastElement) - 1]; 199 } 200 201 return NULL; 202 } 203 204 205 MIN_MAX_HEAP_TEMPLATE_LIST 206 Element* 207 MIN_MAX_HEAP_CLASS_NAME::PeekMaximum(int32 index) const 208 { 209 if (index < fMaxLastElement) 210 return fMaxElements[index]; 211 else if (index - fMaxLastElement < fMinLastElement) { 212 return fMinElements[fMinLastElement - (index - fMaxLastElement) - 1]; 213 } 214 215 return NULL; 216 } 217 218 219 MIN_MAX_HEAP_TEMPLATE_LIST 220 const Key& 221 MIN_MAX_HEAP_CLASS_NAME::GetKey(Element* element) 222 { 223 return sGetLink(element)->fKey; 224 } 225 226 227 MIN_MAX_HEAP_TEMPLATE_LIST 228 void 229 MIN_MAX_HEAP_CLASS_NAME::ModifyKey(Element* element, Key newKey) 230 { 231 MinMaxHeapLink<Element, Key>* link = sGetLink(element); 232 233 Key oldKey = link->fKey; 234 link->fKey = newKey; 235 236 if (!sCompare(newKey, oldKey) && !sCompare(oldKey, newKey)) 237 return; 238 239 if (sCompare(newKey, oldKey) ^ !link->fMinTree) 240 _MoveUp(link); 241 else 242 _MoveDown(link); 243 } 244 245 246 MIN_MAX_HEAP_TEMPLATE_LIST 247 void 248 MIN_MAX_HEAP_CLASS_NAME::RemoveMinimum() 249 { 250 if (fMinLastElement == 0) { 251 ASSERT(fMaxLastElement == 1); 252 RemoveMaximum(); 253 return; 254 } 255 256 #if KDEBUG 257 Element* element = PeekMinimum(); 258 MinMaxHeapLink<Element, Key>* link = sGetLink(element); 259 ASSERT(link->fIndex != -1); 260 link->fIndex = -1; 261 #endif 262 263 _RemoveLast(true); 264 } 265 266 267 MIN_MAX_HEAP_TEMPLATE_LIST 268 void 269 MIN_MAX_HEAP_CLASS_NAME::RemoveMaximum() 270 { 271 if (fMaxLastElement == 0) { 272 ASSERT(fMinLastElement == 1); 273 RemoveMinimum(); 274 return; 275 } 276 277 #if KDEBUG 278 Element* element = PeekMaximum(); 279 MinMaxHeapLink<Element, Key>* link = sGetLink(element); 280 ASSERT(link->fIndex != -1); 281 link->fIndex = -1; 282 #endif 283 284 _RemoveLast(false); 285 } 286 287 288 MIN_MAX_HEAP_TEMPLATE_LIST 289 status_t 290 MIN_MAX_HEAP_CLASS_NAME::Insert(Element* element, Key key) 291 { 292 if (min_c(fMinLastElement, fMaxLastElement) == fSize) { 293 ASSERT(max_c(fMinLastElement, fMaxLastElement) == fSize); 294 status_t result = _GrowHeap(); 295 if (result != B_OK) 296 return result; 297 } 298 299 ASSERT(fMinLastElement < fSize || fMaxLastElement < fSize); 300 301 MinMaxHeapLink<Element, Key>* link = sGetLink(element); 302 303 ASSERT(link->fIndex == -1); 304 305 link->fMinTree = fMinLastElement < fMaxLastElement; 306 307 int& lastElement = link->fMinTree ? fMinLastElement : fMaxLastElement; 308 Element** tree = link->fMinTree ? fMinElements : fMaxElements; 309 310 tree[lastElement] = element; 311 link->fIndex = lastElement++; 312 link->fKey = key; 313 314 if (!_ChangeTree(link)) 315 _MoveUp(link); 316 317 return B_OK; 318 } 319 320 321 MIN_MAX_HEAP_TEMPLATE_LIST 322 status_t 323 MIN_MAX_HEAP_CLASS_NAME::_GrowHeap(int minimalSize) 324 { 325 minimalSize = minimalSize % 2 == 0 ? minimalSize : minimalSize + 1; 326 int newSize = max_c(max_c(fSize * 4, 4), minimalSize); 327 328 size_t arraySize = newSize * sizeof(Element*); 329 Element** newBuffer 330 = reinterpret_cast<Element**>(realloc(fMinElements, arraySize)); 331 if (newBuffer == NULL) 332 return B_NO_MEMORY; 333 fMinElements = newBuffer; 334 335 newBuffer += newSize / 2; 336 if (fMaxLastElement > 0) 337 memcpy(newBuffer, fMinElements + fSize, fSize * sizeof(Element*)); 338 fMaxElements = newBuffer; 339 340 fSize = newSize / 2; 341 return B_OK; 342 } 343 344 345 MIN_MAX_HEAP_TEMPLATE_LIST 346 void 347 MIN_MAX_HEAP_CLASS_NAME::_MoveUp(MinMaxHeapLink<Element, Key>* link) 348 { 349 Element** tree = link->fMinTree ? fMinElements : fMaxElements; 350 while (true) { 351 if (link->fIndex <= 0) 352 break; 353 354 int parent = (link->fIndex - 1) / 2; 355 bool isSmaller = sCompare(link->fKey, sGetLink(tree[parent])->fKey); 356 if (isSmaller ^ !link->fMinTree) { 357 ASSERT(sGetLink(tree[parent])->fIndex == parent); 358 sGetLink(tree[parent])->fIndex = link->fIndex; 359 360 Element* element = tree[link->fIndex]; 361 tree[link->fIndex] = tree[parent]; 362 tree[parent] = element; 363 364 link->fIndex = parent; 365 } else 366 break; 367 } 368 } 369 370 371 MIN_MAX_HEAP_TEMPLATE_LIST 372 void 373 MIN_MAX_HEAP_CLASS_NAME::_MoveDown(MinMaxHeapLink<Element, Key>* link) 374 { 375 int current; 376 377 int lastElement = link->fMinTree ? fMinLastElement : fMaxLastElement; 378 Element** tree = link->fMinTree ? fMinElements : fMaxElements; 379 while (true) { 380 current = link->fIndex; 381 382 int child = 2 * link->fIndex + 1; 383 if (child < lastElement) { 384 bool isSmaller = sCompare(sGetLink(tree[child])->fKey, link->fKey); 385 if (isSmaller ^ !link->fMinTree) 386 current = child; 387 } 388 389 child = 2 * link->fIndex + 2; 390 if (child < lastElement) { 391 bool isSmaller = sCompare(sGetLink(tree[child])->fKey, 392 sGetLink(tree[current])->fKey); 393 if (isSmaller ^ !link->fMinTree) 394 current = child; 395 } 396 397 if (link->fIndex == current) 398 break; 399 400 ASSERT(sGetLink(tree[current])->fIndex == current); 401 sGetLink(tree[current])->fIndex = link->fIndex; 402 403 Element* element = tree[link->fIndex]; 404 tree[link->fIndex] = tree[current]; 405 tree[current] = element; 406 407 link->fIndex = current; 408 } 409 410 if (2 * link->fIndex + 1 >= lastElement) 411 _ChangeTree(link); 412 } 413 414 415 MIN_MAX_HEAP_TEMPLATE_LIST 416 bool 417 MIN_MAX_HEAP_CLASS_NAME::_ChangeTree(MinMaxHeapLink<Element, Key>* link) 418 { 419 int otherLastElement = link->fMinTree ? fMaxLastElement : fMinLastElement; 420 421 Element** currentTree = link->fMinTree ? fMinElements : fMaxElements; 422 Element** otherTree = link->fMinTree ? fMaxElements : fMinElements; 423 424 if (otherLastElement <= 0) { 425 ASSERT(link->fMinTree ? fMinLastElement : fMaxLastElement == 1); 426 return false; 427 } 428 429 ASSERT((link->fIndex - 1) / 2 < otherLastElement); 430 431 Element* predecessor; 432 if (2 * link->fIndex + 1 < otherLastElement) { 433 predecessor = otherTree[2 * link->fIndex + 1]; 434 ASSERT(sGetLink(predecessor)->fIndex == 2 * link->fIndex + 1); 435 } else if (link->fIndex < otherLastElement) { 436 predecessor = otherTree[link->fIndex]; 437 ASSERT(sGetLink(predecessor)->fIndex == link->fIndex); 438 } else { 439 predecessor = otherTree[(link->fIndex - 1) / 2]; 440 ASSERT(sGetLink(predecessor)->fIndex == (link->fIndex - 1) / 2); 441 } 442 MinMaxHeapLink<Element, Key>* predecessorLink = sGetLink(predecessor); 443 444 bool isSmaller = sCompare(predecessorLink->fKey, link->fKey); 445 if (isSmaller ^ !link->fMinTree) { 446 Element* element = currentTree[link->fIndex]; 447 currentTree[link->fIndex] = otherTree[predecessorLink->fIndex]; 448 otherTree[predecessorLink->fIndex] = element; 449 450 int index = link->fIndex; 451 link->fIndex = predecessorLink->fIndex; 452 predecessorLink->fIndex = index; 453 454 predecessorLink->fMinTree = !predecessorLink->fMinTree; 455 link->fMinTree = !link->fMinTree; 456 457 _MoveUp(link); 458 return true; 459 } 460 461 return false; 462 } 463 464 465 MIN_MAX_HEAP_TEMPLATE_LIST 466 void 467 MIN_MAX_HEAP_CLASS_NAME::_RemoveLast(bool minTree) 468 { 469 bool deleteMin = fMaxLastElement < fMinLastElement; 470 471 Element** tree = deleteMin ? fMinElements : fMaxElements; 472 int& lastElement = deleteMin ? fMinLastElement : fMaxLastElement; 473 474 ASSERT(lastElement > 0); 475 lastElement--; 476 if (lastElement == 0 && deleteMin == minTree) 477 return; 478 479 Element* element = tree[lastElement]; 480 481 if (minTree) 482 fMinElements[0] = element; 483 else 484 fMaxElements[0] = element; 485 486 MinMaxHeapLink<Element, Key>* link = sGetLink(element); 487 link->fIndex = 0; 488 link->fMinTree = minTree; 489 _MoveDown(link); 490 } 491 492 493 MIN_MAX_HEAP_TEMPLATE_LIST 494 Compare MIN_MAX_HEAP_CLASS_NAME::sCompare; 495 496 MIN_MAX_HEAP_TEMPLATE_LIST 497 GetLink MIN_MAX_HEAP_CLASS_NAME::sGetLink; 498 499 500 #endif // KERNEL_UTIL_MIN_MAX_HEAP_H 501 502