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