headers/private/kernel/util/MinMaxHeap.h

   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