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