ocrm.bsky.social
the game where you go into mines and start crafting! but for consoles (forked directly from smartcmd's github)
1#include "stdafx.h"
2#include "Node.h"
3#include "System.h"
4#include "BasicTypeContainers.h"
5#include "BinaryHeap.h"
6
7// 4J Jev, add common ctor code.
8void BinaryHeap::_init()
9{
10 heap = NodeArray(1024);
11 sizeVar = 0;
12}
13
14BinaryHeap::BinaryHeap()
15{
16 _init();
17}
18
19BinaryHeap::~BinaryHeap()
20{
21 delete[] heap.data;
22}
23
24Node *BinaryHeap::insert(Node *node)
25{
26 /* if (node->heapIdx >=0) throw new IllegalStateException("OW KNOWS!"); 4J Jev, removed try/catch */
27
28 // Expand if necessary.
29 if (sizeVar == heap.length)
30 {
31 NodeArray newHeap = NodeArray(sizeVar << 1);
32
33 System::arraycopy(heap, 0, &newHeap, 0, sizeVar);
34
35 delete[] heap.data;
36 heap = newHeap;
37 }
38
39 // Insert at end and bubble up.
40 heap[sizeVar] = node;
41 node->heapIdx = sizeVar;
42 upHeap(sizeVar++);
43
44 return node;
45}
46
47void BinaryHeap::clear()
48{
49 sizeVar = 0;
50}
51
52Node *BinaryHeap::peek()
53{
54 return heap[0];
55}
56
57Node *BinaryHeap::pop()
58{
59 Node *popped = heap[0];
60 heap[0] = heap[--sizeVar];
61 heap[sizeVar] = NULL;
62 if (sizeVar > 0) downHeap(0);
63 popped->heapIdx=-1;
64 return popped;
65}
66
67void BinaryHeap::remove(Node *node)
68{
69 // This is what node.heapIdx is for.
70 heap[node->heapIdx] = heap[--sizeVar];
71 heap[sizeVar] = NULL;
72 if (sizeVar > node->heapIdx)
73 {
74 if (heap[node->heapIdx]->f < node->f)
75 {
76 upHeap(node->heapIdx);
77 }
78 else
79 {
80 downHeap(node->heapIdx);
81 }
82 }
83 // Just as a precaution: should make stuff blow up if the node is abused.
84 node->heapIdx = -1;
85}
86
87void BinaryHeap::changeCost(Node *node, float newCost)
88{
89 float oldCost = node->f;
90 node->f = newCost;
91 if (newCost < oldCost)
92 {
93 upHeap(node->heapIdx);
94 }
95 else
96 {
97 downHeap(node->heapIdx);
98 }
99}
100
101int BinaryHeap::size()
102{
103 return sizeVar;
104}
105
106void BinaryHeap::upHeap(int idx)
107{
108 Node *node = heap[idx];
109 float cost = node->f;
110 while (idx > 0)
111 {
112 int parentIdx = (idx - 1) >> 1;
113 Node *parent = heap[parentIdx];
114 if (cost < parent->f)
115 {
116 heap[idx] = parent;
117 parent->heapIdx = idx;
118 idx = parentIdx;
119 }
120 else break;
121 }
122 heap[idx] = node;
123 node->heapIdx = idx;
124}
125
126void BinaryHeap::downHeap(int idx)
127{
128 Node *node = heap[idx];
129 float cost = node->f;
130
131 while (true)
132 {
133 int leftIdx = 1 + (idx << 1);
134 int rightIdx = leftIdx + 1;
135
136 if (leftIdx >= sizeVar) break;
137
138 // We definitely have a left child.
139 Node *leftNode = heap[leftIdx];
140 float leftCost = leftNode->f;
141 // We may have a right child.
142 Node *rightNode;
143 float rightCost;
144
145 if (rightIdx >= sizeVar)
146 {
147 // Only need to compare with left.
148 rightNode = NULL;
149 rightCost = Float::POSITIVE_INFINITY;
150 }
151 else
152 {
153 rightNode = heap[rightIdx];
154 rightCost = rightNode->f;
155 }
156
157 // Find the smallest of the three costs: the corresponding node
158 // should be the parent.
159 if (leftCost < rightCost)
160 {
161 if (leftCost < cost)
162 {
163 heap[idx] = leftNode;
164 leftNode->heapIdx = idx;
165 idx = leftIdx;
166 }
167 else break;
168 }
169 else
170 {
171 if (rightCost < cost)
172 {
173 heap[idx] = rightNode;
174 rightNode->heapIdx = idx;
175 idx = rightIdx;
176 }
177 else break;
178 }
179 }
180
181 heap[idx] = node;
182 node->heapIdx = idx;
183}
184
185bool BinaryHeap::isEmpty()
186{
187 return sizeVar==0;
188}