View Javadoc

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.ints.AbstractInt2LongMap;
22  import it.unimi.dsi.fastutil.ints.Int2LongMap;
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.IntLongConsumer;
31  import org.apache.giraph.function.primitive.pairs.IntLongPredicate;
32  
33  // AUTO-GENERATED class via class:
34  // org.apache.giraph.generate.GeneratePrimitiveClasses
35  
36  /**
37   * Min heap which holds (int key, long 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  public class FixedCapacityIntLongMinHeap
47      implements Int2LongMapEntryIterable {
48    /** Keys in the heap */
49    private final int[] keys;
50    /** Values in the heap */
51    private final long[] 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    public FixedCapacityIntLongMinHeap(int capacity) {
65      keys = new int[capacity];
66      values = new long[capacity];
67      size = 0;
68      this.capacity = capacity;
69      iterator = new IteratorImpl();
70    }
71  
72    /** Clear the heap */
73    public void clear() {
74      size = 0;
75    }
76  
77    /**
78     * Add a key value pair
79     *
80     * @param key   Key
81     * @param value Value
82     */
83    public void add(int key, long value) {
84      if (size == capacity && compare(keys[0], values[0], key, value) >= 0) {
85        // If the heap is full and smallest element in it is not smaller
86        // than value, do nothing
87        return;
88      }
89      int position;
90      if (size < capacity) {
91        // If the heap is not full, increase its size and find the position for
92        // new element (up-heap search)
93        position = size;
94        size++;
95        while (position > 0) {
96          int parent = (position - 1) >> 1;
97          if (compare(keys[parent], values[parent], key, value) < 0) {
98            break;
99          }
100         values[position] = values[parent];
101         keys[position] = keys[parent];
102         position = parent;
103       }
104     } else {
105       // If the heap is full, remove element from the root and find the position
106       // for new element (down-heap search)
107       position = removeRootAndFindPosition(key, value);
108     }
109     // Fill position with key value pair
110     keys[position] = key;
111     values[position] = value;
112   }
113 
114   /**
115    * @return Key corresponding to the minimum value currently in the heap
116    * @throws NoSuchElementException if the heap is empty.
117    */
118   public int getMinKey() {
119     if (size() > 0) {
120       return keys[0];
121     } else {
122       throw new NoSuchElementException();
123     }
124   }
125 
126   /**
127    * @return Minimum value currently in the heap
128    * @throws NoSuchElementException if the heap is empty.
129    */
130   public long getMinValue() {
131     if (size() > 0) {
132       return values[0];
133     } else {
134       throw new NoSuchElementException();
135     }
136   }
137 
138   /**
139    * Removes the (key, value) pair that corresponds to the minimum value
140    * currently in the heap.
141    */
142   public void removeMin() {
143     if (size() > 0) {
144       size--;
145       int position = removeRootAndFindPosition(keys[size], values[size]);
146       keys[position] = keys[size];
147       values[position] = values[size];
148     }
149   }
150 
151   /**
152    * Comapre two (key, value) entries
153    *
154    * @param key1   First key
155    * @param value1 First value
156    * @param key2   Second key
157    * @param value2 Second value
158    * @return 0 if entries are equal, &lt; 0 if first entry is smaller than the
159    * second one, and &gt; 0 if first entry is larger than the second one
160    */
161   protected int compare(int key1, long value1,
162       int key2, long value2) {
163     int t = Long.compare(value1, value2);
164     return (t == 0) ? Integer.compare(key1, key2) : t;
165   }
166 
167   @Override
168   public ObjectIterator<Int2LongMap.Entry> iterator() {
169     iterator.reset();
170     return iterator;
171   }
172 
173   @Override
174   public int size() {
175     return size;
176   }
177 
178   /**
179    * Check if the heap is empty
180    *
181    * @return True iff the heap is empty
182    */
183   public boolean isEmpty() {
184     return size == 0;
185   }
186 
187   /**
188    * Get capacity of the heap
189    *
190    * @return Heap capacity
191    */
192   public int getCapacity() {
193     return capacity;
194   }
195 
196   /**
197    * Serializes an object into data output.
198    *
199    * @param heap Object instance to serialize
200    * @param out  Data output
201    * @throws java.io.IOException
202    */
203   public static void write(FixedCapacityIntLongMinHeap heap,
204       DataOutput out) throws IOException {
205     out.writeInt(heap.capacity);
206     out.writeInt(heap.size);
207     for (int i = 0; i < heap.size(); i++) {
208       out.writeInt(heap.keys[i]);
209       out.writeLong(heap.values[i]);
210     }
211   }
212 
213   /**
214    * Deserializes an object from data input.
215    *
216    * @param heap Object to reuse if possible
217    * @param in   Data input
218    * @return FixedCapacityIntLongMinHeap deserialized from data input.
219    * @throws IOException
220    */
221   public static FixedCapacityIntLongMinHeap read(
222       FixedCapacityIntLongMinHeap heap, DataInput in)
223       throws IOException {
224     int capacity = in.readInt();
225     if (heap == null || heap.capacity != capacity) {
226       heap = new FixedCapacityIntLongMinHeap(capacity);
227     } else {
228       heap.clear();
229     }
230     heap.size = in.readInt();
231     for (int i = 0; i < heap.size; i++) {
232       heap.keys[i] = in.readInt();
233       heap.values[i] = in.readLong();
234     }
235     return heap;
236   }
237 
238   /**
239    * Takes a (key, value) pair, removes the root of the heap, and finds
240    * a position where the pair can be inserted.
241    *
242    * @param key   Key
243    * @param value Value
244    * @return Position in the heap where the (key, value) pair can be inserted
245    * while preserving the heap property.
246    */
247   private int removeRootAndFindPosition(int key, long value) {
248     int position = 0;
249     while (position < size) {
250       // Find the left child
251       int minChild = (position << 1) + 1;
252       // Compare the left and the right child values - find the smaller one
253       if (minChild + 1 < size &&
254           compare(keys[minChild + 1], values[minChild + 1],
255               keys[minChild], values[minChild]) < 0) {
256         minChild++;
257       }
258       if (minChild >= size || compare(keys[minChild], values[minChild],
259           key, value) >= 0) {
260         break;
261       }
262       keys[position] = keys[minChild];
263       values[position] = values[minChild];
264       position = minChild;
265     }
266     return position;
267   }
268 
269   /**
270    * Traverse all elements of the heap, calling given function on each element.
271    *
272    * @param f Function to call on each element.
273    */
274   public void forEachIntLong(IntLongConsumer f) {
275     for (int i = 0; i < size(); ++i) {
276       f.apply(keys[i], values[i]);
277     }
278   }
279 
280   /**
281    * Traverse all elements of the heap, calling given function on each element,
282    * or until predicate returns false.
283    *
284    * @param f Function to call on each element.
285    * @return true if the predicate returned true for all elements,
286    *    false if it returned false for some element.
287    */
288   public boolean forEachWhileIntLong(IntLongPredicate f) {
289     for (int i = 0; i < size(); ++i) {
290       if (!f.apply(keys[i], values[i])) {
291         return false;
292       }
293     }
294     return true;
295   }
296 
297   /** Iterator for FixedCapacityIntLongMinHeap */
298   private class IteratorImpl implements ObjectIterator<Int2LongMap.Entry> {
299     /** Reusable entry */
300     private final MutableEntry entry = new MutableEntry();
301     /** Current index */
302     private int index;
303 
304     /** Reset the iterator so it can be reused */
305     public void reset() {
306       index = -1;
307     }
308 
309     @Override
310     public boolean hasNext() {
311       return index < size - 1;
312     }
313 
314     @Override
315     public Int2LongMap.Entry next() {
316       if (!hasNext()) {
317         throw new NoSuchElementException();
318       }
319       index++;
320       entry.setIntKey(keys[index]);
321       entry.setLongValue(values[index]);
322       return entry;
323     }
324 
325     @Override
326     public void remove() {
327       throw new UnsupportedOperationException("remove() shouldn't be called");
328     }
329 
330     @Override
331     public int skip(int i) {
332       throw new UnsupportedOperationException("skip(int) shouldn't be called");
333     }
334   }
335 
336   /** Helper mutable Entry class */
337   private static class MutableEntry extends AbstractInt2LongMap.BasicEntry {
338     /** Default constructor */
339     private MutableEntry() {
340       super(0, 0);
341     }
342 
343     /**
344      * Set key
345      *
346      * @param key Key to set
347      */
348     private void setIntKey(int key) {
349       this.key = key;
350     }
351 
352     /**
353      * Set value
354      *
355      * @param value Value to set
356      */
357     private void setLongValue(long value) {
358       this.value = value;
359     }
360   }
361 }