1 | |
|
2 | |
|
3 | |
|
4 | |
|
5 | |
|
6 | |
|
7 | |
|
8 | |
|
9 | |
|
10 | |
|
11 | |
|
12 | |
|
13 | |
|
14 | |
|
15 | |
|
16 | |
|
17 | |
|
18 | |
|
19 | |
package org.apache.giraph.types.heaps; |
20 | |
|
21 | |
import it.unimi.dsi.fastutil.longs.AbstractLong2DoubleMap; |
22 | |
import it.unimi.dsi.fastutil.longs.Long2DoubleMap; |
23 | |
import it.unimi.dsi.fastutil.objects.ObjectIterator; |
24 | |
|
25 | |
import java.io.DataInput; |
26 | |
import java.io.DataOutput; |
27 | |
import java.io.IOException; |
28 | |
import java.util.NoSuchElementException; |
29 | |
|
30 | |
import org.apache.giraph.function.primitive.pairs.LongDoubleConsumer; |
31 | |
import org.apache.giraph.function.primitive.pairs.LongDoublePredicate; |
32 | |
|
33 | |
|
34 | |
|
35 | |
|
36 | |
|
37 | |
|
38 | |
|
39 | |
|
40 | |
|
41 | |
|
42 | |
|
43 | |
|
44 | |
|
45 | |
|
46 | 0 | public class FixedCapacityLongDoubleMinHeap |
47 | |
implements Long2DoubleMapEntryIterable { |
48 | |
|
49 | |
private final long[] keys; |
50 | |
|
51 | |
private final double[] values; |
52 | |
|
53 | |
private int size; |
54 | |
|
55 | |
private final int capacity; |
56 | |
|
57 | |
private final IteratorImpl iterator; |
58 | |
|
59 | |
|
60 | |
|
61 | |
|
62 | |
|
63 | |
|
64 | 0 | public FixedCapacityLongDoubleMinHeap(int capacity) { |
65 | 0 | keys = new long[capacity]; |
66 | 0 | values = new double[capacity]; |
67 | 0 | size = 0; |
68 | 0 | this.capacity = capacity; |
69 | 0 | iterator = new IteratorImpl(); |
70 | 0 | } |
71 | |
|
72 | |
|
73 | |
public void clear() { |
74 | 0 | size = 0; |
75 | 0 | } |
76 | |
|
77 | |
|
78 | |
|
79 | |
|
80 | |
|
81 | |
|
82 | |
|
83 | |
public void add(long key, double value) { |
84 | 0 | if (capacity == 0 || |
85 | 0 | (size == capacity && compare(keys[0], values[0], key, value) >= 0)) { |
86 | |
|
87 | |
|
88 | 0 | return; |
89 | |
} |
90 | |
int position; |
91 | 0 | if (size < capacity) { |
92 | |
|
93 | |
|
94 | 0 | position = size; |
95 | 0 | size++; |
96 | 0 | while (position > 0) { |
97 | 0 | int parent = (position - 1) >> 1; |
98 | 0 | if (compare(keys[parent], values[parent], key, value) < 0) { |
99 | 0 | break; |
100 | |
} |
101 | 0 | values[position] = values[parent]; |
102 | 0 | keys[position] = keys[parent]; |
103 | 0 | position = parent; |
104 | 0 | } |
105 | |
} else { |
106 | |
|
107 | |
|
108 | 0 | position = removeRootAndFindPosition(key, value); |
109 | |
} |
110 | |
|
111 | 0 | keys[position] = key; |
112 | 0 | values[position] = value; |
113 | 0 | } |
114 | |
|
115 | |
|
116 | |
|
117 | |
|
118 | |
|
119 | |
public long getMinKey() { |
120 | 0 | if (size() > 0) { |
121 | 0 | return keys[0]; |
122 | |
} else { |
123 | 0 | throw new NoSuchElementException(); |
124 | |
} |
125 | |
} |
126 | |
|
127 | |
|
128 | |
|
129 | |
|
130 | |
|
131 | |
public double getMinValue() { |
132 | 0 | if (size() > 0) { |
133 | 0 | return values[0]; |
134 | |
} else { |
135 | 0 | throw new NoSuchElementException(); |
136 | |
} |
137 | |
} |
138 | |
|
139 | |
|
140 | |
|
141 | |
|
142 | |
|
143 | |
public void removeMin() { |
144 | 0 | if (size() > 0) { |
145 | 0 | size--; |
146 | 0 | int position = removeRootAndFindPosition(keys[size], values[size]); |
147 | 0 | keys[position] = keys[size]; |
148 | 0 | values[position] = values[size]; |
149 | |
} |
150 | 0 | } |
151 | |
|
152 | |
|
153 | |
|
154 | |
|
155 | |
|
156 | |
|
157 | |
|
158 | |
|
159 | |
|
160 | |
|
161 | |
|
162 | |
protected int compare(long key1, double value1, |
163 | |
long key2, double value2) { |
164 | 0 | int t = Double.compare(value1, value2); |
165 | 0 | return (t == 0) ? Long.compare(key1, key2) : t; |
166 | |
} |
167 | |
|
168 | |
@Override |
169 | |
public ObjectIterator<Long2DoubleMap.Entry> iterator() { |
170 | 0 | iterator.reset(); |
171 | 0 | return iterator; |
172 | |
} |
173 | |
|
174 | |
@Override |
175 | |
public int size() { |
176 | 0 | return size; |
177 | |
} |
178 | |
|
179 | |
|
180 | |
|
181 | |
|
182 | |
|
183 | |
|
184 | |
public boolean isEmpty() { |
185 | 0 | return size == 0; |
186 | |
} |
187 | |
|
188 | |
|
189 | |
|
190 | |
|
191 | |
|
192 | |
|
193 | |
public int getCapacity() { |
194 | 0 | return capacity; |
195 | |
} |
196 | |
|
197 | |
|
198 | |
|
199 | |
|
200 | |
|
201 | |
|
202 | |
|
203 | |
|
204 | |
public static void write(FixedCapacityLongDoubleMinHeap heap, |
205 | |
DataOutput out) throws IOException { |
206 | 0 | out.writeInt(heap.capacity); |
207 | 0 | out.writeInt(heap.size); |
208 | 0 | for (int i = 0; i < heap.size(); i++) { |
209 | 0 | out.writeLong(heap.keys[i]); |
210 | 0 | out.writeDouble(heap.values[i]); |
211 | |
} |
212 | 0 | } |
213 | |
|
214 | |
|
215 | |
|
216 | |
|
217 | |
|
218 | |
|
219 | |
|
220 | |
|
221 | |
|
222 | |
public static FixedCapacityLongDoubleMinHeap read( |
223 | |
FixedCapacityLongDoubleMinHeap heap, DataInput in) |
224 | |
throws IOException { |
225 | 0 | int capacity = in.readInt(); |
226 | 0 | if (heap == null || heap.capacity != capacity) { |
227 | 0 | heap = new FixedCapacityLongDoubleMinHeap(capacity); |
228 | |
} else { |
229 | 0 | heap.clear(); |
230 | |
} |
231 | 0 | heap.size = in.readInt(); |
232 | 0 | for (int i = 0; i < heap.size; i++) { |
233 | 0 | heap.keys[i] = in.readLong(); |
234 | 0 | heap.values[i] = in.readDouble(); |
235 | |
} |
236 | 0 | return heap; |
237 | |
} |
238 | |
|
239 | |
|
240 | |
|
241 | |
|
242 | |
|
243 | |
|
244 | |
|
245 | |
|
246 | |
|
247 | |
|
248 | |
private int removeRootAndFindPosition(long key, double value) { |
249 | 0 | int position = 0; |
250 | 0 | while (position < size) { |
251 | |
|
252 | 0 | int minChild = (position << 1) + 1; |
253 | |
|
254 | 0 | if (minChild + 1 < size && |
255 | 0 | compare(keys[minChild + 1], values[minChild + 1], |
256 | |
keys[minChild], values[minChild]) < 0) { |
257 | 0 | minChild++; |
258 | |
} |
259 | 0 | if (minChild >= size || compare(keys[minChild], values[minChild], |
260 | |
key, value) >= 0) { |
261 | 0 | break; |
262 | |
} |
263 | 0 | keys[position] = keys[minChild]; |
264 | 0 | values[position] = values[minChild]; |
265 | 0 | position = minChild; |
266 | 0 | } |
267 | 0 | return position; |
268 | |
} |
269 | |
|
270 | |
|
271 | |
|
272 | |
|
273 | |
|
274 | |
|
275 | |
public void forEachLongDouble(LongDoubleConsumer f) { |
276 | 0 | for (int i = 0; i < size(); ++i) { |
277 | 0 | f.apply(keys[i], values[i]); |
278 | |
} |
279 | 0 | } |
280 | |
|
281 | |
|
282 | |
|
283 | |
|
284 | |
|
285 | |
|
286 | |
|
287 | |
|
288 | |
|
289 | |
public boolean forEachWhileLongDouble(LongDoublePredicate f) { |
290 | 0 | for (int i = 0; i < size(); ++i) { |
291 | 0 | if (!f.apply(keys[i], values[i])) { |
292 | 0 | return false; |
293 | |
} |
294 | |
} |
295 | 0 | return true; |
296 | |
} |
297 | |
|
298 | |
|
299 | 0 | private class IteratorImpl implements ObjectIterator<Long2DoubleMap.Entry> { |
300 | |
|
301 | 0 | private final MutableEntry entry = new MutableEntry(); |
302 | |
|
303 | |
private int index; |
304 | |
|
305 | |
|
306 | |
public void reset() { |
307 | 0 | index = -1; |
308 | 0 | } |
309 | |
|
310 | |
@Override |
311 | |
public boolean hasNext() { |
312 | 0 | return index < size - 1; |
313 | |
} |
314 | |
|
315 | |
@Override |
316 | |
public Long2DoubleMap.Entry next() { |
317 | 0 | if (!hasNext()) { |
318 | 0 | throw new NoSuchElementException(); |
319 | |
} |
320 | 0 | index++; |
321 | 0 | entry.setLongKey(keys[index]); |
322 | 0 | entry.setDoubleValue(values[index]); |
323 | 0 | return entry; |
324 | |
} |
325 | |
|
326 | |
@Override |
327 | |
public void remove() { |
328 | 0 | throw new UnsupportedOperationException("remove() shouldn't be called"); |
329 | |
} |
330 | |
|
331 | |
@Override |
332 | |
public int skip(int i) { |
333 | 0 | throw new UnsupportedOperationException("skip(int) shouldn't be called"); |
334 | |
} |
335 | |
} |
336 | |
|
337 | |
|
338 | 0 | private static class MutableEntry extends AbstractLong2DoubleMap.BasicEntry { |
339 | |
|
340 | |
private MutableEntry() { |
341 | 0 | super(0, 0); |
342 | 0 | } |
343 | |
|
344 | |
|
345 | |
|
346 | |
|
347 | |
|
348 | |
|
349 | |
private void setLongKey(long key) { |
350 | 0 | this.key = key; |
351 | 0 | } |
352 | |
|
353 | |
|
354 | |
|
355 | |
|
356 | |
|
357 | |
|
358 | |
private void setDoubleValue(double value) { |
359 | 0 | this.value = value; |
360 | 0 | } |
361 | |
} |
362 | |
} |