Coverage Report

 /*
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */
 
 package org.apache.giraph.types.heaps;
 
 import it.unimi.dsi.fastutil.ints.AbstractInt2DoubleMap;
 import it.unimi.dsi.fastutil.ints.Int2DoubleMap;
 import it.unimi.dsi.fastutil.objects.ObjectIterator;
 
 import java.io.DataInput;
 import java.io.DataOutput;
 import java.io.IOException;
 import java.util.NoSuchElementException;
 
 import org.apache.giraph.function.primitive.pairs.IntDoubleConsumer;
 import org.apache.giraph.function.primitive.pairs.IntDoublePredicate;
 
 // AUTO-GENERATED class via class:
 // org.apache.giraph.generate.GeneratePrimitiveClasses
 
 /**
  * Min heap which holds (int key, double value) pairs with
  * the largest values as its elements, up to the given maximum number of
  * elements.
  *
  * When multiple elements with same values are added and there is no space for
  * all of them in the heap, the one with larger keys will be kept in the heap.
  *
  * You can remove a pair with the minimum value currently in the heap.
  */
 public class FixedCapacityIntDoubleMinHeap
     implements Int2DoubleMapEntryIterable {
   /** Keys in the heap */
   private final int[] keys;
   /** Values in the heap */
   private final double[] values;
   /** Number of elements currently in the heap */
   private int size;
   /** Capacity of the heap */
   private final int capacity;
   /** Reusable iterator instance */
   private final IteratorImpl iterator;
 
   /**
    * Initialize the heap with desired capacity
    *
    * @param capacity Capacity
    */
   public FixedCapacityIntDoubleMinHeap(int capacity) {
     keys = new int[capacity];
     values = new double[capacity];
     size = 0;
     this.capacity = capacity;
     iterator = new IteratorImpl();
   }
 
   /** Clear the heap */
   public void clear() {
     size = 0;
   }
 
   /**
    * Add a key value pair
    *
    * @param key   Key
    * @param value Value
    */
   public void add(int key, double value) {
     if (capacity == 0 ||
         (size == capacity && compare(keys[0], values[0], key, value) >= 0)) {
       // If the heap is full and smallest element in it is not smaller
       // than value, do nothing
       return;
     }
     int position;
     if (size < capacity) {
       // If the heap is not full, increase its size and find the position for
       // new element (up-heap search)
       position = size;
       size++;
       while (position > 0) {
         int parent = (position - 1) >> 1;
         if (compare(keys[parent], values[parent], key, value) < 0) {
           break;
         }
         values[position] = values[parent];
         keys[position] = keys[parent];
         position = parent;
       }
     } else {
       // If the heap is full, remove element from the root and find the position
       // for new element (down-heap search)
       position = removeRootAndFindPosition(key, value);
     }
     // Fill position with key value pair
     keys[position] = key;
     values[position] = value;
   }
 
   /**
    * @return Key corresponding to the minimum value currently in the heap
    * @throws NoSuchElementException if the heap is empty.
    */
   public int getMinKey() {
     if (size() > 0) {
       return keys[0];
     } else {
       throw new NoSuchElementException();
     }
   }
 
   /**
    * @return Minimum value currently in the heap
    * @throws NoSuchElementException if the heap is empty.
    */
   public double getMinValue() {
     if (size() > 0) {
       return values[0];
     } else {
       throw new NoSuchElementException();
     }
   }
 
   /**
    * Removes the (key, value) pair that corresponds to the minimum value
    * currently in the heap.
    */
   public void removeMin() {
     if (size() > 0) {
       size--;
       int position = removeRootAndFindPosition(keys[size], values[size]);
       keys[position] = keys[size];
       values[position] = values[size];
     }
   }
 
   /**
    * Comapre two (key, value) entries
    *
    * @param key1   First key
    * @param value1 First value
    * @param key2   Second key
    * @param value2 Second value
    * @return 0 if entries are equal, &lt; 0 if first entry is smaller than the
    * second one, and &gt; 0 if first entry is larger than the second one
    */
   protected int compare(int key1, double value1,
       int key2, double value2) {
     int t = Double.compare(value1, value2);
     return (t == 0) ? Integer.compare(key1, key2) : t;
   }
 
   @Override
   public ObjectIterator<Int2DoubleMap.Entry> iterator() {
     iterator.reset();
     return iterator;
   }
 
   @Override
   public int size() {
     return size;
   }
 
   /**
    * Check if the heap is empty
    *
    * @return True iff the heap is empty
    */
   public boolean isEmpty() {
     return size == 0;
   }
 
   /**
    * Get capacity of the heap
    *
    * @return Heap capacity
    */
   public int getCapacity() {
     return capacity;
   }
 
   /**
    * Serializes an object into data output.
    *
    * @param heap Object instance to serialize
    * @param out  Data output
    * @throws java.io.IOException
    */
   public static void write(FixedCapacityIntDoubleMinHeap heap,
       DataOutput out) throws IOException {
     out.writeInt(heap.capacity);
     out.writeInt(heap.size);
     for (int i = 0; i < heap.size(); i++) {
       out.writeInt(heap.keys[i]);
       out.writeDouble(heap.values[i]);
     }
   }
 
   /**
    * Deserializes an object from data input.
    *
    * @param heap Object to reuse if possible
    * @param in   Data input
    * @return FixedCapacityIntDoubleMinHeap deserialized from data input.
    * @throws IOException
    */
   public static FixedCapacityIntDoubleMinHeap read(
       FixedCapacityIntDoubleMinHeap heap, DataInput in)
       throws IOException {
     int capacity = in.readInt();
     if (heap == null || heap.capacity != capacity) {
       heap = new FixedCapacityIntDoubleMinHeap(capacity);
     } else {
       heap.clear();
     }
     heap.size = in.readInt();
     for (int i = 0; i < heap.size; i++) {
       heap.keys[i] = in.readInt();
       heap.values[i] = in.readDouble();
     }
     return heap;
   }
 
   /**
    * Takes a (key, value) pair, removes the root of the heap, and finds
    * a position where the pair can be inserted.
    *
    * @param key   Key
    * @param value Value
    * @return Position in the heap where the (key, value) pair can be inserted
    * while preserving the heap property.
    */
   private int removeRootAndFindPosition(int key, double value) {
     int position = 0;
     while (position < size) {
       // Find the left child
       int minChild = (position << 1) + 1;
       // Compare the left and the right child values - find the smaller one
       if (minChild + 1 < size &&
           compare(keys[minChild + 1], values[minChild + 1],
               keys[minChild], values[minChild]) < 0) {
         minChild++;
       }
       if (minChild >= size || compare(keys[minChild], values[minChild],
           key, value) >= 0) {
         break;
       }
       keys[position] = keys[minChild];
       values[position] = values[minChild];
       position = minChild;
     }
     return position;
   }
 
   /**
    * Traverse all elements of the heap, calling given function on each element.
    *
    * @param f Function to call on each element.
    */
   public void forEachIntDouble(IntDoubleConsumer f) {
     for (int i = 0; i < size(); ++i) {
       f.apply(keys[i], values[i]);
     }
   }
 
   /**
    * Traverse all elements of the heap, calling given function on each element,
    * or until predicate returns false.
    *
    * @param f Function to call on each element.
    * @return true if the predicate returned true for all elements,
    *    false if it returned false for some element.
    */
   public boolean forEachWhileIntDouble(IntDoublePredicate f) {
     for (int i = 0; i < size(); ++i) {
       if (!f.apply(keys[i], values[i])) {
         return false;
       }
     }
     return true;
   }
 
   /** Iterator for FixedCapacityIntDoubleMinHeap */
   private class IteratorImpl implements ObjectIterator<Int2DoubleMap.Entry> {
     /** Reusable entry */
     private final MutableEntry entry = new MutableEntry();
     /** Current index */
     private int index;
 
     /** Reset the iterator so it can be reused */
     public void reset() {
       index = -1;
     }
 
     @Override
     public boolean hasNext() {
       return index < size - 1;
     }
 
     @Override
     public Int2DoubleMap.Entry next() {
       if (!hasNext()) {
         throw new NoSuchElementException();
       }
       index++;
       entry.setIntKey(keys[index]);
       entry.setDoubleValue(values[index]);
       return entry;
     }
 
     @Override
     public void remove() {
       throw new UnsupportedOperationException("remove() shouldn't be called");
     }
 
     @Override
     public int skip(int i) {
       throw new UnsupportedOperationException("skip(int) shouldn't be called");
     }
   }
 
   /** Helper mutable Entry class */
   private static class MutableEntry extends AbstractInt2DoubleMap.BasicEntry {
     /** Default constructor */
     private MutableEntry() {
       super(0, 0);
     }
 
     /**
      * Set key
      *
      * @param key Key to set
      */
     private void setIntKey(int key) {
       this.key = key;
     }
 
     /**
      * Set value
      *
      * @param value Value to set
      */
     private void setDoubleValue(double value) {
       this.value = value;
     }
   }
 }

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.AbstractInt2DoubleMap;
22		import it.unimi.dsi.fastutil.ints.Int2DoubleMap;
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.IntDoubleConsumer;
31		import org.apache.giraph.function.primitive.pairs.IntDoublePredicate;
32
33		// AUTO-GENERATED class via class:
34		// org.apache.giraph.generate.GeneratePrimitiveClasses
35
36		/**
37		* Min heap which holds (int 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	0	public class FixedCapacityIntDoubleMinHeap
47		implements Int2DoubleMapEntryIterable {
48		/** Keys in the heap */
49		private final int[] 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	0	public FixedCapacityIntDoubleMinHeap(int capacity) {
65	0	keys = new int[capacity];
66	0	values = new double[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(int key, double 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 int 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 double 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(int key1, double value1,
163		int key2, double value2) {
164	0	int t = Double.compare(value1, value2);
165	0	return (t == 0) ? Integer.compare(key1, key2) : t;
166		}
167
168		@Override
169		public ObjectIterator<Int2DoubleMap.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(FixedCapacityIntDoubleMinHeap 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.writeInt(heap.keys[i]);
210	0	out.writeDouble(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 FixedCapacityIntDoubleMinHeap deserialized from data input.
220		* @throws IOException
221		*/
222		public static FixedCapacityIntDoubleMinHeap read(
223		FixedCapacityIntDoubleMinHeap heap, DataInput in)
224		throws IOException {
225	0	int capacity = in.readInt();
226	0	if (heap == null \|\| heap.capacity != capacity) {
227	0	heap = new FixedCapacityIntDoubleMinHeap(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.readInt();
234	0	heap.values[i] = in.readDouble();
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(int key, double 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 forEachIntDouble(IntDoubleConsumer 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 forEachWhileIntDouble(IntDoublePredicate 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 FixedCapacityIntDoubleMinHeap */
299	0	private class IteratorImpl implements ObjectIterator<Int2DoubleMap.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 Int2DoubleMap.Entry next() {
317	0	if (!hasNext()) {
318	0	throw new NoSuchElementException();
319		}
320	0	index++;
321	0	entry.setIntKey(keys[index]);
322	0	entry.setDoubleValue(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 AbstractInt2DoubleMap.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 setIntKey(int key) {
350	0	this.key = key;
351	0	}
352
353		/**
354		* Set value
355		*
356		* @param value Value to set
357		*/
358		private void setDoubleValue(double value) {
359	0	this.value = value;
360	0	}
361		}
362		}