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