1 |
package ags.utils.dataStructures; |
2 |
|
3 |
import java.util.Arrays; |
4 |
|
5 |
/** |
6 |
* An implementation of an implicit binary interval heap. |
7 |
*/ |
8 |
public class IntervalHeap<T> implements MinHeap<T>, MaxHeap<T> { |
9 |
private static final int defaultCapacity = 64; |
10 |
private Object[] data; |
11 |
private double[] keys; |
12 |
private int capacity; |
13 |
private int size; |
14 |
|
15 |
public IntervalHeap() { |
16 |
this(defaultCapacity); |
17 |
} |
18 |
|
19 |
public IntervalHeap(int capacity) { |
20 |
this.data = new Object[capacity]; |
21 |
this.keys = new double[capacity]; |
22 |
this.capacity = capacity; |
23 |
this.size = 0; |
24 |
} |
25 |
|
26 |
public void offer(double key, T value) { |
27 |
// If move room is needed, double array size |
28 |
if (size >= capacity) { |
29 |
capacity *= 2; |
30 |
data = Arrays.copyOf(data, capacity); |
31 |
keys = Arrays.copyOf(keys, capacity); |
32 |
} |
33 |
|
34 |
// Insert new value at the end |
35 |
size++; |
36 |
data[size-1] = value; |
37 |
keys[size-1] = key; |
38 |
siftInsertedValueUp(); |
39 |
} |
40 |
|
41 |
public void removeMin() { |
42 |
if (size == 0) { |
43 |
throw new IllegalStateException(); |
44 |
} |
45 |
|
46 |
size--; |
47 |
data[0] = data[size]; |
48 |
keys[0] = keys[size]; |
49 |
data[size] = null; |
50 |
siftDownMin(0); |
51 |
} |
52 |
|
53 |
public void replaceMin(double key, T value) { |
54 |
if (size == 0) { |
55 |
throw new IllegalStateException(); |
56 |
} |
57 |
|
58 |
data[0] = value; |
59 |
keys[0] = key; |
60 |
if (size > 1) { |
61 |
// Swap with pair if necessary |
62 |
if (keys[1] < key) { |
63 |
swap(0, 1); |
64 |
} |
65 |
siftDownMin(0); |
66 |
} |
67 |
} |
68 |
|
69 |
public void removeMax() { |
70 |
if (size == 0) { |
71 |
throw new IllegalStateException(); |
72 |
} else if (size == 1) { |
73 |
removeMin(); |
74 |
return; |
75 |
} |
76 |
|
77 |
size--; |
78 |
data[1] = data[size]; |
79 |
keys[1] = keys[size]; |
80 |
data[size] = null; |
81 |
siftDownMax(1); |
82 |
} |
83 |
|
84 |
public void replaceMax(double key, T value) { |
85 |
if (size == 0) { |
86 |
throw new IllegalStateException(); |
87 |
} else if (size == 1) { |
88 |
replaceMin(key, value); |
89 |
return; |
90 |
} |
91 |
|
92 |
data[1] = value; |
93 |
keys[1] = key; |
94 |
// Swap with pair if necessary |
95 |
if (key < keys[0]) { |
96 |
swap(0, 1); |
97 |
} |
98 |
siftDownMax(1); |
99 |
} |
100 |
|
101 |
@SuppressWarnings("unchecked") |
102 |
public T getMin() { |
103 |
if (size == 0) { |
104 |
throw new IllegalStateException(); |
105 |
} |
106 |
|
107 |
return (T) data[0]; |
108 |
} |
109 |
|
110 |
@SuppressWarnings("unchecked") |
111 |
public T getMax() { |
112 |
if (size == 0) { |
113 |
throw new IllegalStateException(); |
114 |
} else if (size == 1) { |
115 |
return (T) data[0]; |
116 |
} |
117 |
|
118 |
return (T) data[1]; |
119 |
} |
120 |
|
121 |
public double getMinKey() { |
122 |
if (size == 0) { |
123 |
throw new IllegalStateException(); |
124 |
} |
125 |
|
126 |
return keys[0]; |
127 |
} |
128 |
|
129 |
public double getMaxKey() { |
130 |
if (size == 0) { |
131 |
throw new IllegalStateException(); |
132 |
} else if (size == 1) { |
133 |
return keys[0]; |
134 |
} |
135 |
|
136 |
return keys[1]; |
137 |
} |
138 |
|
139 |
private int swap(int x, int y) { |
140 |
Object yData = data[y]; |
141 |
double yDist = keys[y]; |
142 |
data[y] = data[x]; |
143 |
keys[y] = keys[x]; |
144 |
data[x] = yData; |
145 |
keys[x] = yDist; |
146 |
return y; |
147 |
} |
148 |
|
149 |
/** |
150 |
* Min-side (u % 2 == 0): |
151 |
* - leftchild: 2u + 2 |
152 |
* - rightchild: 2u + 4 |
153 |
* - parent: (x/2-1)&~1 |
154 |
* |
155 |
* Max-side (u % 2 == 1): |
156 |
* - leftchild: 2u + 1 |
157 |
* - rightchild: 2u + 3 |
158 |
* - parent: (x/2-1)|1 |
159 |
*/ |
160 |
|
161 |
private void siftInsertedValueUp() { |
162 |
int u = size-1; |
163 |
if (u == 0) { |
164 |
// Do nothing if it's the only element! |
165 |
} |
166 |
else if (u == 1) { |
167 |
// If it is the second element, just sort it with it's pair |
168 |
if (keys[u] < keys[u-1]) { // If less than it's pair |
169 |
swap(u, u-1); // Swap with it's pair |
170 |
} |
171 |
} |
172 |
else if (u % 2 == 1) { |
173 |
// Already paired. Ensure pair is ordered right |
174 |
int p = (u/2-1)|1; // The larger value of the parent pair |
175 |
if (keys[u] < keys[u-1]) { // If less than it's pair |
176 |
u = swap(u, u-1); // Swap with it's pair |
177 |
if (keys[u] < keys[p-1]) { // If smaller than smaller parent pair |
178 |
// Swap into min-heap side |
179 |
u = swap(u, p-1); |
180 |
siftUpMin(u); |
181 |
} |
182 |
} else { |
183 |
if (keys[u] > keys[p]) { // If larger that larger parent pair |
184 |
// Swap into max-heap side |
185 |
u = swap(u, p); |
186 |
siftUpMax(u); |
187 |
} |
188 |
} |
189 |
} else { |
190 |
// Inserted in the lower-value slot without a partner |
191 |
int p = (u/2-1)|1; // The larger value of the parent pair |
192 |
if (keys[u] > keys[p]) { // If larger that larger parent pair |
193 |
// Swap into max-heap side |
194 |
u = swap(u, p); |
195 |
siftUpMax(u); |
196 |
} else if (keys[u] < keys[p-1]) { // If smaller than smaller parent pair |
197 |
// Swap into min-heap side |
198 |
u = swap(u, p-1); |
199 |
siftUpMin(u); |
200 |
} |
201 |
} |
202 |
} |
203 |
|
204 |
private void siftUpMin(int c) { |
205 |
// Min-side parent: (x/2-1)&~1 |
206 |
for (int p = (c/2-1)&~1; p >= 0 && keys[c] < keys[p]; c = p, p = (c/2-1)&~1) { |
207 |
swap(c, p); |
208 |
} |
209 |
} |
210 |
|
211 |
private void siftUpMax(int c) { |
212 |
// Max-side parent: (x/2-1)|1 |
213 |
for (int p = (c/2-1)|1; p >= 0 && keys[c] > keys[p]; c = p, p = (c/2-1)|1) { |
214 |
swap(c, p); |
215 |
} |
216 |
} |
217 |
|
218 |
private void siftDownMin(int p) { |
219 |
for (int c = p * 2 + 2; c < size; p = c, c = p * 2 + 2) { |
220 |
if (c + 2 < size && keys[c + 2] < keys[c]) { |
221 |
c += 2; |
222 |
} |
223 |
if (keys[c] < keys[p]) { |
224 |
swap(p, c); |
225 |
// Swap with pair if necessary |
226 |
if (c+1 < size && keys[c+1] < keys[c]) { |
227 |
swap(c, c+1); |
228 |
} |
229 |
} else { |
230 |
break; |
231 |
} |
232 |
} |
233 |
} |
234 |
|
235 |
private void siftDownMax(int p) { |
236 |
for (int c = p * 2 + 1; c <= size; p = c, c = p * 2 + 1) { |
237 |
if (c == size) { |
238 |
// If the left child only has half a pair |
239 |
if (keys[c - 1] > keys[p]) { |
240 |
swap(p, c - 1); |
241 |
} |
242 |
break; |
243 |
} else if (c + 2 == size) { |
244 |
// If there is only room for a right child lower pair |
245 |
if (keys[c + 1] > keys[c]) { |
246 |
if (keys[c + 1] > keys[p]) { |
247 |
swap(p, c + 1); |
248 |
} |
249 |
break; |
250 |
} |
251 |
} else if (c + 2 < size) { |
252 |
// If there is room for a right child upper pair |
253 |
if (keys[c + 2] > keys[c]) { |
254 |
c += 2; |
255 |
} |
256 |
} |
257 |
if (keys[c] > keys[p]) { |
258 |
swap(p, c); |
259 |
// Swap with pair if necessary |
260 |
if (keys[c-1] > keys[c]) { |
261 |
swap(c, c-1); |
262 |
} |
263 |
} else { |
264 |
break; |
265 |
} |
266 |
} |
267 |
} |
268 |
|
269 |
public int size() { |
270 |
return size; |
271 |
} |
272 |
|
273 |
public int capacity() { |
274 |
return capacity; |
275 |
} |
276 |
|
277 |
@Override |
278 |
public String toString() { |
279 |
java.text.DecimalFormat twoPlaces = new java.text.DecimalFormat("0.00"); |
280 |
StringBuffer str = new StringBuffer(IntervalHeap.class.getCanonicalName()); |
281 |
str.append(", size: ").append(size()).append(" capacity: ").append(capacity()); |
282 |
int i = 0, p = 2; |
283 |
while (i < size()) { |
284 |
int x = 0; |
285 |
str.append("\t"); |
286 |
while ((i+x) < size() && x < p) { |
287 |
str.append(twoPlaces.format(keys[i + x])).append(", "); |
288 |
x++; |
289 |
} |
290 |
str.append("\n"); |
291 |
i += x; |
292 |
p *= 2; |
293 |
} |
294 |
return str.toString(); |
295 |
} |
296 |
|
297 |
private boolean validateHeap() { |
298 |
// Validate left-right |
299 |
for (int i = 0; i < size-1; i+= 2) { |
300 |
if (keys[i] > keys[i+1]) return false; |
301 |
} |
302 |
// Validate within parent interval |
303 |
for (int i = 2; i < size; i++) { |
304 |
double maxParent = keys[(i/2-1)|1]; |
305 |
double minParent = keys[(i/2-1)&~1]; |
306 |
if (keys[i] > maxParent || keys[i] < minParent) return false; |
307 |
} |
308 |
return true; |
309 |
} |
310 |
} |