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>
MinMaxHeapLink()112 MinMaxHeapLink<Element, Key>::MinMaxHeapLink()
113 :
114 fIndex(-1)
115 {
116 }
117 #else
118 template<typename Element, typename Key>
MinMaxHeapLink()119 MinMaxHeapLink<Element, Key>::MinMaxHeapLink()
120 {
121 }
122 #endif
123
124
125 template<typename Element, typename Key>
126 MinMaxHeapLink<Element, Key>*
GetMinMaxHeapLink()127 MinMaxHeapLinkImpl<Element, Key>::GetMinMaxHeapLink()
128 {
129 return &fMinMaxHeapLink;
130 }
131
132
133 template<typename Element, typename Key>
134 MinMaxHeapLink<Element, Key>*
operator()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>*
operator()144 MinMaxHeapMemberGetLink<Element, Key, LinkMember>::operator()(
145 Element* element) const
146 {
147 return &(element->*LinkMember);
148 }
149
150
151 template<typename Key>
152 bool
operator()153 MinMaxHeapCompare<Key>::operator()(Key a, Key b)
154 {
155 return a < b;
156 }
157
158
159 MIN_MAX_HEAP_TEMPLATE_LIST
MinMaxHeap()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
MinMaxHeap(int initialSize)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
~MinMaxHeap()185 MIN_MAX_HEAP_CLASS_NAME::~MinMaxHeap()
186 {
187 free(fMinElements);
188 }
189
190
191 MIN_MAX_HEAP_TEMPLATE_LIST
192 Element*
PeekMinimum(int32 index)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*
PeekMaximum(int32 index)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&
GetKey(Element * element)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
ModifyKey(Element * element,Key newKey)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
RemoveMinimum()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
RemoveMaximum()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
Insert(Element * element,Key key)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
_GrowHeap(int minimalSize)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
_MoveUp(MinMaxHeapLink<Element,Key> * link)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
_MoveDown(MinMaxHeapLink<Element,Key> * link)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
_ChangeTree(MinMaxHeapLink<Element,Key> * link)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
_RemoveLast(bool minTree)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