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() 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 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() 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 206 MIN_MAX_HEAP_TEMPLATE_LIST 207 Element* 208 MIN_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 221 MIN_MAX_HEAP_TEMPLATE_LIST 222 const Key& 223 MIN_MAX_HEAP_CLASS_NAME::GetKey(Element* element) 224 { 225 return sGetLink(element)->fKey; 226 } 227 228 229 MIN_MAX_HEAP_TEMPLATE_LIST 230 void 231 MIN_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 248 MIN_MAX_HEAP_TEMPLATE_LIST 249 void 250 MIN_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 269 MIN_MAX_HEAP_TEMPLATE_LIST 270 void 271 MIN_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 290 MIN_MAX_HEAP_TEMPLATE_LIST 291 status_t 292 MIN_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 323 MIN_MAX_HEAP_TEMPLATE_LIST 324 status_t 325 MIN_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 347 MIN_MAX_HEAP_TEMPLATE_LIST 348 void 349 MIN_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 373 MIN_MAX_HEAP_TEMPLATE_LIST 374 void 375 MIN_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 417 MIN_MAX_HEAP_TEMPLATE_LIST 418 bool 419 MIN_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 467 MIN_MAX_HEAP_TEMPLATE_LIST 468 void 469 MIN_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 495 MIN_MAX_HEAP_TEMPLATE_LIST 496 Compare MIN_MAX_HEAP_CLASS_NAME::sCompare; 497 498 MIN_MAX_HEAP_TEMPLATE_LIST 499 GetLink MIN_MAX_HEAP_CLASS_NAME::sGetLink; 500 501 502 #endif // KERNEL_UTIL_MIN_MAX_HEAP_H 503 504