Classes in this File | Line Coverage | Branch Coverage | Complexity | ||||
FixedCapacityLongFloatMinHeap |
|
| 2.3333333333333335;2.333 | ||||
FixedCapacityLongFloatMinHeap$1 |
|
| 2.3333333333333335;2.333 | ||||
FixedCapacityLongFloatMinHeap$IteratorImpl |
|
| 2.3333333333333335;2.333 | ||||
FixedCapacityLongFloatMinHeap$MutableEntry |
|
| 2.3333333333333335;2.333 |
1 | /* | |
2 | * Licensed to the Apache Software Foundation (ASF) under one | |
3 | * or more contributor license agreements. See the NOTICE file | |
4 | * distributed with this work for additional information | |
5 | * regarding copyright ownership. The ASF licenses this file | |
6 | * to you under the Apache License, Version 2.0 (the | |
7 | * "License"); you may not use this file except in compliance | |
8 | * with the License. You may obtain a copy of the License at | |
9 | * | |
10 | * http://www.apache.org/licenses/LICENSE-2.0 | |
11 | * | |
12 | * Unless required by applicable law or agreed to in writing, software | |
13 | * distributed under the License is distributed on an "AS IS" BASIS, | |
14 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
15 | * See the License for the specific language governing permissions and | |
16 | * limitations under the License. | |
17 | */ | |
18 | ||
19 | package org.apache.giraph.types.heaps; | |
20 | ||
21 | import it.unimi.dsi.fastutil.longs.AbstractLong2FloatMap; | |
22 | import it.unimi.dsi.fastutil.longs.Long2FloatMap; | |
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.LongFloatConsumer; | |
31 | import org.apache.giraph.function.primitive.pairs.LongFloatPredicate; | |
32 | ||
33 | // AUTO-GENERATED class via class: | |
34 | // org.apache.giraph.generate.GeneratePrimitiveClasses | |
35 | ||
36 | /** | |
37 | * Min heap which holds (long key, float value) pairs with | |
38 | * the largest values as its elements, up to the given maximum number of | |
39 | * elements. | |
40 | * | |
41 | * When multiple elements with same values are added and there is no space for | |
42 | * all of them in the heap, the one with larger keys will be kept in the heap. | |
43 | * | |
44 | * You can remove a pair with the minimum value currently in the heap. | |
45 | */ | |
46 | 0 | public class FixedCapacityLongFloatMinHeap |
47 | implements Long2FloatMapEntryIterable { | |
48 | /** Keys in the heap */ | |
49 | private final long[] keys; | |
50 | /** Values in the heap */ | |
51 | private final float[] values; | |
52 | /** Number of elements currently in the heap */ | |
53 | private int size; | |
54 | /** Capacity of the heap */ | |
55 | private final int capacity; | |
56 | /** Reusable iterator instance */ | |
57 | private final IteratorImpl iterator; | |
58 | ||
59 | /** | |
60 | * Initialize the heap with desired capacity | |
61 | * | |
62 | * @param capacity Capacity | |
63 | */ | |
64 | 0 | public FixedCapacityLongFloatMinHeap(int capacity) { |
65 | 0 | keys = new long[capacity]; |
66 | 0 | values = new float[capacity]; |
67 | 0 | size = 0; |
68 | 0 | this.capacity = capacity; |
69 | 0 | iterator = new IteratorImpl(); |
70 | 0 | } |
71 | ||
72 | /** Clear the heap */ | |
73 | public void clear() { | |
74 | 0 | size = 0; |
75 | 0 | } |
76 | ||
77 | /** | |
78 | * Add a key value pair | |
79 | * | |
80 | * @param key Key | |
81 | * @param value Value | |
82 | */ | |
83 | public void add(long key, float value) { | |
84 | 0 | if (capacity == 0 || |
85 | 0 | (size == capacity && compare(keys[0], values[0], key, value) >= 0)) { |
86 | // If the heap is full and smallest element in it is not smaller | |
87 | // than value, do nothing | |
88 | 0 | return; |
89 | } | |
90 | int position; | |
91 | 0 | if (size < capacity) { |
92 | // If the heap is not full, increase its size and find the position for | |
93 | // new element (up-heap search) | |
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 | // If the heap is full, remove element from the root and find the position | |
107 | // for new element (down-heap search) | |
108 | 0 | position = removeRootAndFindPosition(key, value); |
109 | } | |
110 | // Fill position with key value pair | |
111 | 0 | keys[position] = key; |
112 | 0 | values[position] = value; |
113 | 0 | } |
114 | ||
115 | /** | |
116 | * @return Key corresponding to the minimum value currently in the heap | |
117 | * @throws NoSuchElementException if the heap is empty. | |
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 | * @return Minimum value currently in the heap | |
129 | * @throws NoSuchElementException if the heap is empty. | |
130 | */ | |
131 | public float getMinValue() { | |
132 | 0 | if (size() > 0) { |
133 | 0 | return values[0]; |
134 | } else { | |
135 | 0 | throw new NoSuchElementException(); |
136 | } | |
137 | } | |
138 | ||
139 | /** | |
140 | * Removes the (key, value) pair that corresponds to the minimum value | |
141 | * currently in the heap. | |
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 | * Comapre two (key, value) entries | |
154 | * | |
155 | * @param key1 First key | |
156 | * @param value1 First value | |
157 | * @param key2 Second key | |
158 | * @param value2 Second value | |
159 | * @return 0 if entries are equal, < 0 if first entry is smaller than the | |
160 | * second one, and > 0 if first entry is larger than the second one | |
161 | */ | |
162 | protected int compare(long key1, float value1, | |
163 | long key2, float value2) { | |
164 | 0 | int t = Float.compare(value1, value2); |
165 | 0 | return (t == 0) ? Long.compare(key1, key2) : t; |
166 | } | |
167 | ||
168 | @Override | |
169 | public ObjectIterator<Long2FloatMap.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 | * Check if the heap is empty | |
181 | * | |
182 | * @return True iff the heap is empty | |
183 | */ | |
184 | public boolean isEmpty() { | |
185 | 0 | return size == 0; |
186 | } | |
187 | ||
188 | /** | |
189 | * Get capacity of the heap | |
190 | * | |
191 | * @return Heap capacity | |
192 | */ | |
193 | public int getCapacity() { | |
194 | 0 | return capacity; |
195 | } | |
196 | ||
197 | /** | |
198 | * Serializes an object into data output. | |
199 | * | |
200 | * @param heap Object instance to serialize | |
201 | * @param out Data output | |
202 | * @throws java.io.IOException | |
203 | */ | |
204 | public static void write(FixedCapacityLongFloatMinHeap 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.writeFloat(heap.values[i]); |
211 | } | |
212 | 0 | } |
213 | ||
214 | /** | |
215 | * Deserializes an object from data input. | |
216 | * | |
217 | * @param heap Object to reuse if possible | |
218 | * @param in Data input | |
219 | * @return FixedCapacityLongFloatMinHeap deserialized from data input. | |
220 | * @throws IOException | |
221 | */ | |
222 | public static FixedCapacityLongFloatMinHeap read( | |
223 | FixedCapacityLongFloatMinHeap heap, DataInput in) | |
224 | throws IOException { | |
225 | 0 | int capacity = in.readInt(); |
226 | 0 | if (heap == null || heap.capacity != capacity) { |
227 | 0 | heap = new FixedCapacityLongFloatMinHeap(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.readFloat(); |
235 | } | |
236 | 0 | return heap; |
237 | } | |
238 | ||
239 | /** | |
240 | * Takes a (key, value) pair, removes the root of the heap, and finds | |
241 | * a position where the pair can be inserted. | |
242 | * | |
243 | * @param key Key | |
244 | * @param value Value | |
245 | * @return Position in the heap where the (key, value) pair can be inserted | |
246 | * while preserving the heap property. | |
247 | */ | |
248 | private int removeRootAndFindPosition(long key, float value) { | |
249 | 0 | int position = 0; |
250 | 0 | while (position < size) { |
251 | // Find the left child | |
252 | 0 | int minChild = (position << 1) + 1; |
253 | // Compare the left and the right child values - find the smaller one | |
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 | * Traverse all elements of the heap, calling given function on each element. | |
272 | * | |
273 | * @param f Function to call on each element. | |
274 | */ | |
275 | public void forEachLongFloat(LongFloatConsumer f) { | |
276 | 0 | for (int i = 0; i < size(); ++i) { |
277 | 0 | f.apply(keys[i], values[i]); |
278 | } | |
279 | 0 | } |
280 | ||
281 | /** | |
282 | * Traverse all elements of the heap, calling given function on each element, | |
283 | * or until predicate returns false. | |
284 | * | |
285 | * @param f Function to call on each element. | |
286 | * @return true if the predicate returned true for all elements, | |
287 | * false if it returned false for some element. | |
288 | */ | |
289 | public boolean forEachWhileLongFloat(LongFloatPredicate 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 | /** Iterator for FixedCapacityLongFloatMinHeap */ | |
299 | 0 | private class IteratorImpl implements ObjectIterator<Long2FloatMap.Entry> { |
300 | /** Reusable entry */ | |
301 | 0 | private final MutableEntry entry = new MutableEntry(); |
302 | /** Current index */ | |
303 | private int index; | |
304 | ||
305 | /** Reset the iterator so it can be reused */ | |
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 Long2FloatMap.Entry next() { | |
317 | 0 | if (!hasNext()) { |
318 | 0 | throw new NoSuchElementException(); |
319 | } | |
320 | 0 | index++; |
321 | 0 | entry.setLongKey(keys[index]); |
322 | 0 | entry.setFloatValue(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 | /** Helper mutable Entry class */ | |
338 | 0 | private static class MutableEntry extends AbstractLong2FloatMap.BasicEntry { |
339 | /** Default constructor */ | |
340 | private MutableEntry() { | |
341 | 0 | super(0, 0); |
342 | 0 | } |
343 | ||
344 | /** | |
345 | * Set key | |
346 | * | |
347 | * @param key Key to set | |
348 | */ | |
349 | private void setLongKey(long key) { | |
350 | 0 | this.key = key; |
351 | 0 | } |
352 | ||
353 | /** | |
354 | * Set value | |
355 | * | |
356 | * @param value Value to set | |
357 | */ | |
358 | private void setFloatValue(float value) { | |
359 | 0 | this.value = value; |
360 | 0 | } |
361 | } | |
362 | } |