forked from facebookarchive/RakNet
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDS_Heap.h
305 lines (273 loc) · 8.9 KB
/
DS_Heap.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
/*
* Copyright (c) 2014, Oculus VR, Inc.
* All rights reserved.
*
* This source code is licensed under the BSD-style license found in the
* LICENSE file in the root directory of this source tree. An additional grant
* of patent rights can be found in the PATENTS file in the same directory.
*
*/
/// \file DS_Heap.h
/// \internal
/// \brief Heap (Also serves as a priority queue)
///
#ifndef __RAKNET_HEAP_H
#define __RAKNET_HEAP_H
#include "RakMemoryOverride.h"
#include "DS_List.h"
#include "Export.h"
#include "RakAssert.h"
#ifdef _MSC_VER
#pragma warning( push )
#endif
/// The namespace DataStructures was only added to avoid compiler errors for commonly named data structures
/// As these data structures are stand-alone, you can use them outside of RakNet for your own projects if you wish.
namespace DataStructures
{
template <class weight_type, class data_type, bool isMaxHeap>
class RAK_DLL_EXPORT Heap
{
public:
struct HeapNode
{
HeapNode() {}
HeapNode(const weight_type &w, const data_type &d) : weight(w), data(d) {}
weight_type weight; // I'm assuming key is a native numerical type - float or int
data_type data;
};
Heap();
~Heap();
void Push(const weight_type &weight, const data_type &data, const char *file, unsigned int line);
/// Call before calling PushSeries, for a new series of items
void StartSeries(void) {optimizeNextSeriesPush=false;}
/// If you are going to push a list of items, where the weights of the items on the list are in order and follow the heap order, PushSeries is faster than Push()
void PushSeries(const weight_type &weight, const data_type &data, const char *file, unsigned int line);
data_type Pop(const unsigned startingIndex);
data_type Peek(const unsigned startingIndex=0) const;
weight_type PeekWeight(const unsigned startingIndex=0) const;
void Clear(bool doNotDeallocateSmallBlocks, const char *file, unsigned int line);
data_type& operator[] ( const unsigned int position ) const;
unsigned Size(void) const;
protected:
unsigned LeftChild(const unsigned i) const;
unsigned RightChild(const unsigned i) const;
unsigned Parent(const unsigned i) const;
void Swap(const unsigned i, const unsigned j);
DataStructures::List<HeapNode> heap;
bool optimizeNextSeriesPush;
};
template <class weight_type, class data_type, bool isMaxHeap>
Heap<weight_type, data_type, isMaxHeap>::Heap()
{
optimizeNextSeriesPush=false;
}
template <class weight_type, class data_type, bool isMaxHeap>
Heap<weight_type, data_type, isMaxHeap>::~Heap()
{
//Clear(true, _FILE_AND_LINE_);
}
template <class weight_type, class data_type, bool isMaxHeap>
void Heap<weight_type, data_type, isMaxHeap>::PushSeries(const weight_type &weight, const data_type &data, const char *file, unsigned int line)
{
if (optimizeNextSeriesPush==false)
{
// If the weight of what we are inserting is greater than / less than in order of the heap of every sibling and sibling of parent, then can optimize next push
unsigned currentIndex = heap.Size();
unsigned parentIndex;
if (currentIndex>0)
{
for (parentIndex = Parent(currentIndex); parentIndex < currentIndex; parentIndex++)
{
#ifdef _MSC_VER
#pragma warning(disable:4127) // conditional expression is constant
#endif
if (isMaxHeap)
{
// Every child is less than its parent
if (weight>heap[parentIndex].weight)
{
// Can't optimize
Push(weight,data,file,line);
return;
}
}
else
{
// Every child is greater than than its parent
if (weight<heap[parentIndex].weight)
{
// Can't optimize
Push(weight,data,file,line);
return;
}
}
}
}
// Parent's subsequent siblings and this row's siblings all are less than / greater than inserted element. Can insert all further elements straight to the end
heap.Insert(HeapNode(weight, data), file, line);
optimizeNextSeriesPush=true;
}
else
{
heap.Insert(HeapNode(weight, data), file, line);
}
}
template <class weight_type, class data_type, bool isMaxHeap>
void Heap<weight_type, data_type, isMaxHeap>::Push(const weight_type &weight, const data_type &data, const char *file, unsigned int line)
{
unsigned currentIndex = heap.Size();
unsigned parentIndex;
heap.Insert(HeapNode(weight, data), file, line);
while (currentIndex!=0)
{
parentIndex = Parent(currentIndex);
#ifdef _MSC_VER
#pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
#endif
if (isMaxHeap)
{
if (heap[parentIndex].weight < weight)
{
Swap(currentIndex, parentIndex);
currentIndex=parentIndex;
}
else
break;
}
else
{
if (heap[parentIndex].weight > weight)
{
Swap(currentIndex, parentIndex);
currentIndex=parentIndex;
}
else
break;
}
}
}
template <class weight_type, class data_type, bool isMaxHeap>
data_type Heap<weight_type, data_type, isMaxHeap>::Pop(const unsigned startingIndex)
{
// While we have children, swap out with the larger of the two children.
// This line will assert on an empty heap
data_type returnValue=heap[startingIndex].data;
// Move the last element to the head, and re-heapify
heap[startingIndex]=heap[heap.Size()-1];
unsigned currentIndex,leftChild,rightChild;
weight_type currentWeight;
currentIndex=startingIndex;
currentWeight=heap[startingIndex].weight;
heap.RemoveFromEnd();
#ifdef _MSC_VER
#pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
#endif
while (1)
{
leftChild=LeftChild(currentIndex);
rightChild=RightChild(currentIndex);
if (leftChild >= heap.Size())
{
// Done
return returnValue;
}
if (rightChild >= heap.Size())
{
// Only left node.
if ((isMaxHeap==true && currentWeight < heap[leftChild].weight) ||
(isMaxHeap==false && currentWeight > heap[leftChild].weight))
Swap(leftChild, currentIndex);
return returnValue;
}
else
{
// Swap with the bigger/smaller of the two children and continue
if (isMaxHeap)
{
if (heap[leftChild].weight <= currentWeight && heap[rightChild].weight <= currentWeight)
return returnValue;
if (heap[leftChild].weight > heap[rightChild].weight)
{
Swap(leftChild, currentIndex);
currentIndex=leftChild;
}
else
{
Swap(rightChild, currentIndex);
currentIndex=rightChild;
}
}
else
{
if (heap[leftChild].weight >= currentWeight && heap[rightChild].weight >= currentWeight)
return returnValue;
if (heap[leftChild].weight < heap[rightChild].weight)
{
Swap(leftChild, currentIndex);
currentIndex=leftChild;
}
else
{
Swap(rightChild, currentIndex);
currentIndex=rightChild;
}
}
}
}
}
template <class weight_type, class data_type, bool isMaxHeap>
inline data_type Heap<weight_type, data_type, isMaxHeap>::Peek(const unsigned startingIndex) const
{
return heap[startingIndex].data;
}
template <class weight_type, class data_type, bool isMaxHeap>
inline weight_type Heap<weight_type, data_type, isMaxHeap>::PeekWeight(const unsigned startingIndex) const
{
return heap[startingIndex].weight;
}
template <class weight_type, class data_type, bool isMaxHeap>
void Heap<weight_type, data_type, isMaxHeap>::Clear(bool doNotDeallocateSmallBlocks, const char *file, unsigned int line)
{
heap.Clear(doNotDeallocateSmallBlocks, file, line);
}
template <class weight_type, class data_type, bool isMaxHeap>
inline data_type& Heap<weight_type, data_type, isMaxHeap>::operator[] ( const unsigned int position ) const
{
return heap[position].data;
}
template <class weight_type, class data_type, bool isMaxHeap>
unsigned Heap<weight_type, data_type, isMaxHeap>::Size(void) const
{
return heap.Size();
}
template <class weight_type, class data_type, bool isMaxHeap>
inline unsigned Heap<weight_type, data_type, isMaxHeap>::LeftChild(const unsigned i) const
{
return i*2+1;
}
template <class weight_type, class data_type, bool isMaxHeap>
inline unsigned Heap<weight_type, data_type, isMaxHeap>::RightChild(const unsigned i) const
{
return i*2+2;
}
template <class weight_type, class data_type, bool isMaxHeap>
inline unsigned Heap<weight_type, data_type, isMaxHeap>::Parent(const unsigned i) const
{
#ifdef _DEBUG
RakAssert(i!=0);
#endif
return (i-1)/2;
}
template <class weight_type, class data_type, bool isMaxHeap>
void Heap<weight_type, data_type, isMaxHeap>::Swap(const unsigned i, const unsigned j)
{
HeapNode temp;
temp=heap[i];
heap[i]=heap[j];
heap[j]=temp;
}
}
#ifdef _MSC_VER
#pragma warning( pop )
#endif
#endif