1//************************************ bs::framework - Copyright 2018 Marko Pintera **************************************//
2//*********** Licensed under the MIT license. See LICENSE.md for full terms. This notice is not to be removed. ***********//
3#pragma once
4
5#include "Utility/BsDynArray.h"
6
7namespace bs
8{
9 /** @addtogroup General
10 * @{
11 */
12
13 /** Nodes for the heap. */
14 template <class K, class V>
15 struct HeapNode
16 {
17 K key;
18 V value;
19 UINT32 index;
20 };
21
22 /**
23 * Binary tree where each nodes is less than or equal to the data in its node's children.
24 */
25 template <class K, class V>
26 class MinHeap
27 {
28 public:
29 MinHeap() = default;
30
31 MinHeap(const MinHeap<K, V>& other)
32 {
33 *this = other;
34 }
35
36 MinHeap(UINT32 elements)
37 {
38 resize(elements);
39 }
40
41 MinHeap<K, V>& operator= (const MinHeap<K, V>& other)
42 {
43 mSize = other.mSize;
44 mNode = other.mNode;
45 mPtr.resize(other.mPtr.size());
46
47 for (auto& entry : mNode)
48 mPtr[entry.index] = &entry;
49
50 return *this;
51 }
52
53 HeapNode<K, V> operator[] (UINT32 index) { return mNode[index]; }
54 const HeapNode<K, V> operator[] (UINT32 index) const { return mNode[index]; }
55
56 bool empty() const { return mSize == 0; }
57 UINT32 size() const { return mSize; }
58
59 void minimum(K& key, V& value)
60 {
61 assert(mSize > 0);
62
63 key = mPtr[0]->key;
64 value = mPtr[0]->value;
65 }
66
67 HeapNode<K, V>* insert(const K& key, const V& value)
68 {
69 if (mSize == mNode.size())
70 return nullptr;
71
72 int child = mSize++;
73 HeapNode<K, V>* node = mPtr[child];
74
75 node->key = key;
76 node->value = value;
77
78 while (child > 0)
79 {
80 const int parent = (child - 1) / 2;
81
82 if (mPtr[parent]->value <= value)
83 break;
84
85 mPtr[child] = mPtr[parent];
86 mPtr[child]->index = child;
87
88 mPtr[parent] = node;
89 mPtr[parent]->index = parent;
90
91 child = parent;
92 }
93
94 return mPtr[child];
95 }
96
97 void erase(K& key, V& value)
98 {
99 assert(mSize > 0);
100
101 HeapNode<K, V>* root = mPtr[0];
102 key = root->key;
103 value = root->value;
104
105 const int last = --mSize;
106 HeapNode<K, V>* node = mPtr[last];
107
108 int parent = 0;
109 int child = 1;
110
111 while (child <= last)
112 {
113 if (child < last)
114 {
115 const int child2 = child + 1;
116
117 if (mPtr[child2]->value < mPtr[child]->value)
118 child = child2;
119 }
120
121 if (node->value <= mPtr[child]->value)
122 break;
123
124 mPtr[parent] = mPtr[child];
125 mPtr[parent]->index = parent;
126
127 parent = child;
128 child = 2 * child + 1;
129 }
130
131 mPtr[parent] = node;
132 mPtr[parent]->index = parent;
133
134 mPtr[last] = root;
135 mPtr[last]->index = last;
136 }
137
138 void update(HeapNode<K, V>* node, const V& value)
139 {
140 if (!node)
141 return;
142
143 int parent = 0;
144 int child = 0;
145 int child2 = 0;
146 int maxChild = 0;
147
148 if (node->value < value)
149 {
150 node->value = value;
151 parent = node->index;
152 child = 2 * parent + 1;
153
154 while (child < mSize)
155 {
156 child2 = child + 1;
157 if (child2 < mSize)
158 {
159 if (mPtr[child]->value <= mPtr[child2]->value)
160 maxChild = child;
161 else
162 maxChild = child2;
163 }
164 else
165 maxChild = child;
166
167 if (value <= mPtr[maxChild]->value)
168 break;
169
170 mPtr[parent] = mPtr[maxChild];
171 mPtr[parent]->index = parent;
172
173 mPtr[maxChild] = node;
174 mPtr[maxChild]->index = maxChild;
175
176 parent = maxChild;
177 child = 2 * parent + 1;
178 }
179 }
180 else if (value < node->value)
181 {
182 node->value = value;
183 child = node->index;
184
185 while (child > 0)
186 {
187 parent = (child - 1) / 2;
188
189 if (mPtr[parent]->value <= value)
190 break;
191
192 mPtr[child] = mPtr[parent];
193 mPtr[child]->index = child;
194
195 mPtr[parent] = node;
196 mPtr[parent]->index = parent;
197
198 child = parent;
199 }
200 }
201 }
202
203 void resize(UINT32 elements)
204 {
205 mSize = 0;
206 if (elements > 0)
207 {
208 mNode.resize(elements);
209 mPtr.resize(elements);
210
211 for (UINT32 i = 0; i < elements; ++i)
212 {
213 mPtr[i] = &mNode[i];
214 mPtr[i]->index = i;
215 }
216 }
217 else
218 {
219 mNode.clear();
220 mPtr.clear();
221 }
222 }
223
224 bool valid() const
225 {
226 for (int i = 0; i < (int)mSize; ++i)
227 {
228 int parent = (i - 1) / 2;
229 if (parent > 0)
230 {
231 if (mPtr[i]->value < mPtr[parent]->value ||
232 (int)mPtr[parent]->index != parent)
233 return false;
234 }
235 }
236
237 return true;
238 }
239
240 private:
241 UINT32 mSize;
242 DynArray<HeapNode<K, V>> mNode;
243 DynArray<HeapNode<K, V>*> mPtr;
244 };
245
246 /** @} */
247}