Package org.apache.flink.runtime.state.heap

Class HeapPriorityQueueSet<T extends HeapPriorityQueueElement>

java.lang.Object

org.apache.flink.runtime.state.heap.AbstractHeapPriorityQueue<T>

org.apache.flink.runtime.state.heap.HeapPriorityQueue<T>

org.apache.flink.runtime.state.heap.HeapPriorityQueueSet<T>

Type Parameters:

T - type of the contained elements.

All Implemented Interfaces:

InternalPriorityQueue<T>, KeyGroupedInternalPriorityQueue<T>

public class HeapPriorityQueueSet<T extends HeapPriorityQueueElement>
extends HeapPriorityQueue<T>
implements KeyGroupedInternalPriorityQueue<T>

A heap-based priority queue with set semantics, based on HeapPriorityQueue. The heap is supported by hash set for fast contains (de-duplication) and deletes. Object identification happens based on Object.equals(Object).

Possible future improvements:

• We could also implement shrinking for the heap and the deduplication set.
• We could replace the deduplication maps with more efficient custom implementations. In particular, a hash set would be enough if it could return existing elements on unsuccessful adding, etc..

Field Summary

Fields inherited from class org.apache.flink.runtime.state.heap.HeapPriorityQueue

elementPriorityComparator

Fields inherited from class org.apache.flink.runtime.state.heap.AbstractHeapPriorityQueue

queue, size

Constructor Summary

Constructors

Constructor	Description
HeapPriorityQueueSet(PriorityComparator<T> elementPriorityComparator, KeyExtractorFunction<T> keyExtractor, int minimumCapacity, KeyGroupRange keyGroupRange, int totalNumberOfKeyGroups)	Creates an empty HeapPriorityQueueSet with the requested initial capacity.

Method Summary

Modifier and Type	Method	Description
boolean	add(T element)	Adds the element to the queue.
void	clear()	Clears the queue.
Set<T>	getSubsetForKeyGroup(int keyGroupId)	Returns the subset of elements in the priority queue that belongs to the given key-group, within the operator's key-group range.
T	poll()	Retrieves and removes the first element (w.r.t. the order) of this set, or returns null if this set is empty.
boolean	remove(T toRemove)	In contrast to the superclass and to maintain set semantics, removal here is based on comparing the given element via Object.equals(Object).

Methods inherited from class org.apache.flink.runtime.state.heap.HeapPriorityQueue

addInternal, adjustModifiedElement, getHeadElementIndex, removeInternal

Methods inherited from class org.apache.flink.runtime.state.heap.AbstractHeapPriorityQueue

addAll, isEmpty, iterator, moveElementToIdx, peek, resizeForBulkLoad, resizeQueueArray, size, toArray

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.apache.flink.runtime.state.InternalPriorityQueue

addAll, isEmpty, iterator, peek, size

Constructor Detail

HeapPriorityQueueSet

public HeapPriorityQueueSet(@Nonnull
                            PriorityComparator<T> elementPriorityComparator,
                            @Nonnull
                            KeyExtractorFunction<T> keyExtractor,
                            @Nonnegative
                            int minimumCapacity,
                            @Nonnull
                            KeyGroupRange keyGroupRange,
                            @Nonnegative
                            int totalNumberOfKeyGroups)

Creates an empty HeapPriorityQueueSet with the requested initial capacity.

Parameters:

elementPriorityComparator - comparator for the priority of contained elements.

keyExtractor - function to extract a key from the contained elements.

minimumCapacity - the minimum and initial capacity of this priority queue.

keyGroupRange - the key-group range of the elements in this set.

totalNumberOfKeyGroups - the total number of key-groups of the job.

Method Detail

poll

@Nullable
public T poll()

Description copied from interface: InternalPriorityQueue

Retrieves and removes the first element (w.r.t. the order) of this set, or returns null if this set is empty.

NOTE: Correct key (i.e. the key of the polled element) must be set on KeyContext before calling this method.

Specified by:

poll in interface InternalPriorityQueue<T extends HeapPriorityQueueElement>

Overrides:

poll in class AbstractHeapPriorityQueue<T extends HeapPriorityQueueElement>

Returns:

the first element of this ordered set, or null if this set is empty.

add

public boolean add(@Nonnull
                   T element)

Adds the element to the queue. In contrast to the superclass and to maintain set semantics, this happens only if no such element is already contained (determined by Object.equals(Object)).

Specified by:

add in interface InternalPriorityQueue<T extends HeapPriorityQueueElement>

Overrides:

add in class AbstractHeapPriorityQueue<T extends HeapPriorityQueueElement>

Parameters:

element - the element to add to the set.

Returns:

true if the operation changed the head element or if is it unclear if the head element changed. Only returns false iff the head element was not changed by this operation.

remove

public boolean remove(@Nonnull
                      T toRemove)

In contrast to the superclass and to maintain set semantics, removal here is based on comparing the given element via Object.equals(Object).

Specified by:

remove in interface InternalPriorityQueue<T extends HeapPriorityQueueElement>

Overrides:

remove in class AbstractHeapPriorityQueue<T extends HeapPriorityQueueElement>

Parameters:

toRemove - the element to remove.

Returns:

true if the operation changed the head element or if is it unclear if the head element changed. Only returns false iff the head element was not changed by this operation.

clear

public void clear()

Description copied from class: AbstractHeapPriorityQueue

Clears the queue.

Overrides:

clear in class AbstractHeapPriorityQueue<T extends HeapPriorityQueueElement>

getSubsetForKeyGroup

@Nonnull
public Set<T> getSubsetForKeyGroup(int keyGroupId)

Description copied from interface: KeyGroupedInternalPriorityQueue

Returns the subset of elements in the priority queue that belongs to the given key-group, within the operator's key-group range.

Specified by:

getSubsetForKeyGroup in interface KeyGroupedInternalPriorityQueue<T extends HeapPriorityQueueElement>