1/*2 * Licensed to the Apache Software Foundation (ASF) under one3 * or more contributor license agreements. See the NOTICE file4 * distributed with this work for additional information5 * regarding copyright ownership. The ASF licenses this file6 * to you under the Apache License, Version 2.0 (the7 * "License"); you may not use this file except in compliance8 * with the License. You may obtain a copy of the License at9 *10 * http://www.apache.org/licenses/LICENSE-2.011 *12 * Unless required by applicable law or agreed to in writing, software13 * 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 and16 * limitations under the License.17 */1819package org.apache.giraph.types.heaps;
2021import it.unimi.dsi.fastutil.longs.AbstractLong2DoubleMap;
22import it.unimi.dsi.fastutil.longs.Long2DoubleMap;
23import it.unimi.dsi.fastutil.objects.ObjectIterator;
2425import java.io.DataInput;
26import java.io.DataOutput;
27import java.io.IOException;
28import java.util.NoSuchElementException;
2930import org.apache.giraph.function.primitive.pairs.LongDoubleConsumer;
31import org.apache.giraph.function.primitive.pairs.LongDoublePredicate;
3233// AUTO-GENERATED class via class:34// org.apache.giraph.generate.GeneratePrimitiveClasses3536/**37 * Min heap which holds (long key, double value) pairs with38 * the largest values as its elements, up to the given maximum number of39 * elements.40 *41 * When multiple elements with same values are added and there is no space for42 * 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 */46publicclassFixedCapacityLongDoubleMinHeap47implementsLong2DoubleMapEntryIterable {
48/** Keys in the heap */49privatefinallong[] keys;
50/** Values in the heap */51privatefinaldouble[] values;
52/** Number of elements currently in the heap */53privateint size;
54/** Capacity of the heap */55privatefinalint capacity;
56/** Reusable iterator instance */57privatefinalIteratorImpl iterator;
5859/**60 * Initialize the heap with desired capacity61 *62 * @param capacity Capacity63 */64publicFixedCapacityLongDoubleMinHeap(int capacity) {
65 keys = newlong[capacity];
66 values = newdouble[capacity];
67 size = 0;
68this.capacity = capacity;
69 iterator = newIteratorImpl();
70 }
7172/** Clear the heap */73publicvoid clear() {
74 size = 0;
75 }
7677/**78 * Add a key value pair79 *80 * @param key Key81 * @param value Value82 */83publicvoid add(long key, double value) {
84if (capacity == 0 ||
85 (size == capacity && compare(keys[0], values[0], key, value) >= 0)) {
86// If the heap is full and smallest element in it is not smaller87// than value, do nothing88return;
89 }
90int position;
91if (size < capacity) {
92// If the heap is not full, increase its size and find the position for93// new element (up-heap search)94 position = size;
95 size++;
96while (position > 0) {
97int parent = (position - 1) >> 1;
98if (compare(keys[parent], values[parent], key, value) < 0) {
99break;
100 }
101 values[position] = values[parent];
102 keys[position] = keys[parent];
103 position = parent;
104 }
105 } else {
106// If the heap is full, remove element from the root and find the position107// for new element (down-heap search)108 position = removeRootAndFindPosition(key, value);
109 }
110// Fill position with key value pair111 keys[position] = key;
112 values[position] = value;
113 }
114115/**116 * @return Key corresponding to the minimum value currently in the heap117 * @throws NoSuchElementException if the heap is empty.118 */119publiclong getMinKey() {
120if (size() > 0) {
121return keys[0];
122 } else {
123thrownew NoSuchElementException();
124 }
125 }
126127/**128 * @return Minimum value currently in the heap129 * @throws NoSuchElementException if the heap is empty.130 */131publicdouble getMinValue() {
132if (size() > 0) {
133return values[0];
134 } else {
135thrownew NoSuchElementException();
136 }
137 }
138139/**140 * Removes the (key, value) pair that corresponds to the minimum value141 * currently in the heap.142 */143publicvoid removeMin() {
144if (size() > 0) {
145 size--;
146int position = removeRootAndFindPosition(keys[size], values[size]);
147 keys[position] = keys[size];
148 values[position] = values[size];
149 }
150 }
151152/**153 * Comapre two (key, value) entries154 *155 * @param key1 First key156 * @param value1 First value157 * @param key2 Second key158 * @param value2 Second value159 * @return 0 if entries are equal, < 0 if first entry is smaller than the160 * second one, and > 0 if first entry is larger than the second one161 */162protectedint compare(long key1, double value1,
163long key2, double value2) {
164int t = Double.compare(value1, value2);
165return (t == 0) ? Long.compare(key1, key2) : t;
166 }
167168 @Override
169public ObjectIterator<Long2DoubleMap.Entry> iterator() {
170 iterator.reset();
171return iterator;
172 }
173174 @Override
175publicint size() {
176return size;
177 }
178179/**180 * Check if the heap is empty181 *182 * @return True iff the heap is empty183 */184publicboolean isEmpty() {
185return size == 0;
186 }
187188/**189 * Get capacity of the heap190 *191 * @return Heap capacity192 */193publicint getCapacity() {
194return capacity;
195 }
196197/**198 * Serializes an object into data output.199 *200 * @param heap Object instance to serialize201 * @param out Data output202 * @throws java.io.IOException203 */204publicstaticvoid write(FixedCapacityLongDoubleMinHeap heap,
205 DataOutput out) throws IOException {
206 out.writeInt(heap.capacity);
207 out.writeInt(heap.size);
208for (int i = 0; i < heap.size(); i++) {
209 out.writeLong(heap.keys[i]);
210 out.writeDouble(heap.values[i]);
211 }
212 }
213214/**215 * Deserializes an object from data input.216 *217 * @param heap Object to reuse if possible218 * @param in Data input219 * @return FixedCapacityLongDoubleMinHeap deserialized from data input.220 * @throws IOException221 */222publicstaticFixedCapacityLongDoubleMinHeap read(
223FixedCapacityLongDoubleMinHeap heap, DataInput in)
224throws IOException {
225int capacity = in.readInt();
226if (heap == null || heap.capacity != capacity) {
227 heap = newFixedCapacityLongDoubleMinHeap(capacity);
228 } else {
229 heap.clear();
230 }
231 heap.size = in.readInt();
232for (int i = 0; i < heap.size; i++) {
233 heap.keys[i] = in.readLong();
234 heap.values[i] = in.readDouble();
235 }
236return heap;
237 }
238239/**240 * Takes a (key, value) pair, removes the root of the heap, and finds241 * a position where the pair can be inserted.242 *243 * @param key Key244 * @param value Value245 * @return Position in the heap where the (key, value) pair can be inserted246 * while preserving the heap property.247 */248privateint removeRootAndFindPosition(long key, double value) {
249int position = 0;
250while (position < size) {
251// Find the left child252int minChild = (position << 1) + 1;
253// Compare the left and the right child values - find the smaller one254if (minChild + 1 < size &&
255 compare(keys[minChild + 1], values[minChild + 1],
256 keys[minChild], values[minChild]) < 0) {
257 minChild++;
258 }
259if (minChild >= size || compare(keys[minChild], values[minChild],
260 key, value) >= 0) {
261break;
262 }
263 keys[position] = keys[minChild];
264 values[position] = values[minChild];
265 position = minChild;
266 }
267return position;
268 }
269270/**271 * Traverse all elements of the heap, calling given function on each element.272 *273 * @param f Function to call on each element.274 */275publicvoid forEachLongDouble(LongDoubleConsumer f) {
276for (int i = 0; i < size(); ++i) {
277 f.apply(keys[i], values[i]);
278 }
279 }
280281/**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 */289publicboolean forEachWhileLongDouble(LongDoublePredicate f) {
290for (int i = 0; i < size(); ++i) {
291if (!f.apply(keys[i], values[i])) {
292return false;
293 }
294 }
295returntrue;
296 }
297298/** Iterator for FixedCapacityLongDoubleMinHeap */299privateclassIteratorImplimplements ObjectIterator<Long2DoubleMap.Entry> {
300/** Reusable entry */301privatefinalMutableEntry entry = newMutableEntry();
302/** Current index */303privateint index;
304305/** Reset the iterator so it can be reused */306publicvoid reset() {
307 index = -1;
308 }
309310 @Override
311publicboolean hasNext() {
312return index < size - 1;
313 }
314315 @Override
316public Long2DoubleMap.Entry next() {
317if (!hasNext()) {
318thrownew NoSuchElementException();
319 }
320 index++;
321 entry.setLongKey(keys[index]);
322 entry.setDoubleValue(values[index]);
323return entry;
324 }
325326 @Override
327publicvoid remove() {
328thrownew UnsupportedOperationException("remove() shouldn't be called");
329 }
330331 @Override
332publicint skip(int i) {
333thrownew UnsupportedOperationException("skip(int) shouldn't be called");
334 }
335 }
336337/** Helper mutable Entry class */338privatestaticclassMutableEntryextends AbstractLong2DoubleMap.BasicEntry {
339/** Default constructor */340privateMutableEntry() {
341super(0, 0);
342 }
343344/**345 * Set key346 *347 * @param key Key to set348 */349privatevoid setLongKey(long key) {
350this.key = key;
351 }
352353/**354 * Set value355 *356 * @param value Value to set357 */358privatevoid setDoubleValue(double value) {
359this.value = value;
360 }
361 }
362 }