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.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  // AUTO-GENERATED class via class:
34  // org.apache.giraph.generate.GeneratePrimitiveClasses
35  
36  /**
37   * Min heap which holds (long key, double 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 FixedCapacityLongDoubleMinHeap
47      implements Long2DoubleMapEntryIterable {
48    /** Keys in the heap */
49    private final long[] keys;
50    /** Values in the heap */
51    private final double[] 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 FixedCapacityLongDoubleMinHeap(int capacity) {
65      keys = new long[capacity];
66      values = new double[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(long key, double value) {
84      if (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 smaller
87        // than value, do nothing
88        return;
89      }
90      int position;
91      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        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       // If the heap is full, remove element from the root and find the position
107       // for new element (down-heap search)
108       position = removeRootAndFindPosition(key, value);
109     }
110     // Fill position with key value pair
111     keys[position] = key;
112     values[position] = value;
113   }
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     if (size() > 0) {
121       return keys[0];
122     } else {
123       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 double getMinValue() {
132     if (size() > 0) {
133       return values[0];
134     } else {
135       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     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    * 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, &lt; 0 if first entry is smaller than the
160    * second one, and &gt; 0 if first entry is larger than the second one
161    */
162   protected int compare(long key1, double value1,
163       long key2, double value2) {
164     int t = Double.compare(value1, value2);
165     return (t == 0) ? Long.compare(key1, key2) : t;
166   }
167 
168   @Override
169   public ObjectIterator<Long2DoubleMap.Entry> iterator() {
170     iterator.reset();
171     return iterator;
172   }
173 
174   @Override
175   public int size() {
176     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     return size == 0;
186   }
187 
188   /**
189    * Get capacity of the heap
190    *
191    * @return Heap capacity
192    */
193   public int getCapacity() {
194     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(FixedCapacityLongDoubleMinHeap 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.writeDouble(heap.values[i]);
211     }
212   }
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 FixedCapacityLongDoubleMinHeap deserialized from data input.
220    * @throws IOException
221    */
222   public static FixedCapacityLongDoubleMinHeap read(
223       FixedCapacityLongDoubleMinHeap heap, DataInput in)
224       throws IOException {
225     int capacity = in.readInt();
226     if (heap == null || heap.capacity != capacity) {
227       heap = new FixedCapacityLongDoubleMinHeap(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.readDouble();
235     }
236     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, double value) {
249     int position = 0;
250     while (position < size) {
251       // Find the left child
252       int minChild = (position << 1) + 1;
253       // Compare the left and the right child values - find the smaller one
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    * 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 forEachLongDouble(LongDoubleConsumer f) {
276     for (int i = 0; i < size(); ++i) {
277       f.apply(keys[i], values[i]);
278     }
279   }
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 forEachWhileLongDouble(LongDoublePredicate 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   /** Iterator for FixedCapacityLongDoubleMinHeap */
299   private class IteratorImpl implements ObjectIterator<Long2DoubleMap.Entry> {
300     /** Reusable entry */
301     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       index = -1;
308     }
309 
310     @Override
311     public boolean hasNext() {
312       return index < size - 1;
313     }
314 
315     @Override
316     public Long2DoubleMap.Entry next() {
317       if (!hasNext()) {
318         throw new NoSuchElementException();
319       }
320       index++;
321       entry.setLongKey(keys[index]);
322       entry.setDoubleValue(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   /** Helper mutable Entry class */
338   private static class MutableEntry extends AbstractLong2DoubleMap.BasicEntry {
339     /** Default constructor */
340     private MutableEntry() {
341       super(0, 0);
342     }
343 
344     /**
345      * Set key
346      *
347      * @param key Key to set
348      */
349     private void setLongKey(long key) {
350       this.key = key;
351     }
352 
353     /**
354      * Set value
355      *
356      * @param value Value to set
357      */
358     private void setDoubleValue(double value) {
359       this.value = value;
360     }
361   }
362 }