org.apache.giraph.types.heaps

Class FixedCapacityLongDoubleMinHeap

java.lang.Object

org.apache.giraph.types.heaps.FixedCapacityLongDoubleMinHeap

All Implemented Interfaces:

it.unimi.dsi.fastutil.objects.ObjectIterable<it.unimi.dsi.fastutil.longs.Long2DoubleMap.Entry>, Iterable<it.unimi.dsi.fastutil.longs.Long2DoubleMap.Entry>, Long2DoubleMapEntryIterable

public class FixedCapacityLongDoubleMinHeap
extends Object
implements Long2DoubleMapEntryIterable

Min heap which holds (long 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.

Constructor Summary

Constructors

Constructor and Description
FixedCapacityLongDoubleMinHeap(int capacity) Initialize the heap with desired capacity

Method Summary

Modifier and Type	Method and Description
void	add(long key, double value) Add a key value pair
void	clear() Clear the heap
protected int	compare(long key1, double value1, long key2, double value2) Comapre two (key, value) entries
void	forEachLongDouble(LongDoubleConsumer f) Traverse all elements of the heap, calling given function on each element.
boolean	forEachWhileLongDouble(LongDoublePredicate f) Traverse all elements of the heap, calling given function on each element, or until predicate returns false.
int	getCapacity() Get capacity of the heap
long	getMinKey()
double	getMinValue()
boolean	isEmpty() Check if the heap is empty
it.unimi.dsi.fastutil.objects.ObjectIterator<it.unimi.dsi.fastutil.longs.Long2DoubleMap.Entry>	iterator() Get the iterator.
static FixedCapacityLongDoubleMinHeap	read(FixedCapacityLongDoubleMinHeap heap, DataInput in) Deserializes an object from data input.
void	removeMin() Removes the (key, value) pair that corresponds to the minimum value currently in the heap.
int	size() Get the size of this iterable
static void	write(FixedCapacityLongDoubleMinHeap heap, DataOutput out) Serializes an object into data output.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

FixedCapacityLongDoubleMinHeap

public FixedCapacityLongDoubleMinHeap(int capacity)

Initialize the heap with desired capacity

Parameters:

capacity - Capacity

Method Detail

clear

public void clear()

Clear the heap

add

public void add(long key,
                double value)

Add a key value pair

Parameters:

key - Key

value - Value

getMinKey

public long getMinKey()

Returns:

Key corresponding to the minimum value currently in the heap

Throws:

NoSuchElementException - if the heap is empty.

getMinValue

public double getMinValue()

Returns:

Minimum value currently in the heap

Throws:

NoSuchElementException - if the heap is empty.

removeMin

public void removeMin()

Removes the (key, value) pair that corresponds to the minimum value currently in the heap.

compare

protected int compare(long key1,
                      double value1,
                      long key2,
                      double value2)

Comapre two (key, value) entries

Parameters:

key1 - First key

value1 - First value

key2 - Second key

value2 - Second value

Returns:

0 if entries are equal, < 0 if first entry is smaller than the second one, and > 0 if first entry is larger than the second one

iterator

public it.unimi.dsi.fastutil.objects.ObjectIterator<it.unimi.dsi.fastutil.longs.Long2DoubleMap.Entry> iterator()

Description copied from interface: Long2DoubleMapEntryIterable

Get the iterator. Not thread-safe and reuses iterator object, so you can't have several iterators at the same time.

Specified by:

iterator in interface it.unimi.dsi.fastutil.objects.ObjectIterable<it.unimi.dsi.fastutil.longs.Long2DoubleMap.Entry>

Specified by:

iterator in interface Iterable<it.unimi.dsi.fastutil.longs.Long2DoubleMap.Entry>

Specified by:

iterator in interface Long2DoubleMapEntryIterable

Returns:

Iterator

size

public int size()

Description copied from interface: Long2DoubleMapEntryIterable

Get the size of this iterable

Specified by:

size in interface Long2DoubleMapEntryIterable

Returns:

Size

isEmpty

public boolean isEmpty()

Check if the heap is empty

Returns:

True iff the heap is empty

getCapacity

public int getCapacity()

Get capacity of the heap

Returns:

Heap capacity

write

public static void write(FixedCapacityLongDoubleMinHeap heap,
                         DataOutput out)
                  throws IOException

Serializes an object into data output.

Parameters:

heap - Object instance to serialize

out - Data output

Throws:

IOException

read

public static FixedCapacityLongDoubleMinHeap read(FixedCapacityLongDoubleMinHeap heap,
                                                  DataInput in)
                                           throws IOException

Deserializes an object from data input.

Parameters:

heap - Object to reuse if possible

in - Data input

Returns:

FixedCapacityLongDoubleMinHeap deserialized from data input.

Throws:

IOException

forEachLongDouble

public void forEachLongDouble(LongDoubleConsumer f)

Traverse all elements of the heap, calling given function on each element.

Parameters:

f - Function to call on each element.

forEachWhileLongDouble

public boolean forEachWhileLongDouble(LongDoublePredicate f)

Traverse all elements of the heap, calling given function on each element, or until predicate returns false.

Parameters:

f - Function to call on each element.

Returns:

true if the predicate returned true for all elements, false if it returned false for some element.