org.apache.flink.runtime.operators.sort

Class PartialOrderPriorityQueue<T>

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractQueue<T>

org.apache.flink.runtime.operators.sort.PartialOrderPriorityQueue<T>

All Implemented Interfaces:

Iterable<T>, Collection<T>, Queue<T>

public class PartialOrderPriorityQueue<T>
extends AbstractQueue<T>
implements Queue<T>

This class implements a priority-queue, which maintains a partial ordering of its elements such that the least element can always be found in constant time. Put()'s and pop()'s require log(size) time.

Constructor Summary

Constructors

Constructor and Description
PartialOrderPriorityQueue(Comparator<T> comparator, int capacity)

Method Summary

Modifier and Type	Method and Description
void	adjustTop() Should be called when the Object at top changes values.
void	clear() Removes all entries from the PriorityQueue.
Iterator<T>	iterator()
boolean	offer(T element) Adds element to the PriorityQueue in log(size) time if either the PriorityQueue is not full, or not lessThan(element, top()).
T	peek() Returns the least element of the PriorityQueue in constant time, but does not remove it from the priority queue.
T	poll() Removes and returns the least element of the PriorityQueue in log(size) time.
void	put(T element) Adds a buffer to a PriorityQueue in log(size) time.
int	remainingCapacity() Returns the remaining capacity of the backing array.
int	size() Returns the number of elements currently stored in the PriorityQueue.

Methods inherited from class java.util.AbstractQueue

add, addAll, element, remove

Methods inherited from class java.util.AbstractCollection

contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Queue

add, element, remove

Methods inherited from interface java.util.Collection

addAll, contains, containsAll, equals, hashCode, isEmpty, parallelStream, remove, removeAll, removeIf, retainAll, spliterator, stream, toArray, toArray

Methods inherited from interface java.lang.Iterable

forEach

Constructor Detail

PartialOrderPriorityQueue

public PartialOrderPriorityQueue(Comparator<T> comparator,
                                 int capacity)

Method Detail

remainingCapacity

public int remainingCapacity()

Returns the remaining capacity of the backing array.

Returns:

The remaining capacity of the backing array.

put

public final void put(T element)

Adds a buffer to a PriorityQueue in log(size) time. If one tries to add more objects than maxSize from initialize a RuntimeException (ArrayIndexOutOfBound) is thrown.

offer

public boolean offer(T element)

Adds element to the PriorityQueue in log(size) time if either the PriorityQueue is not full, or not lessThan(element, top()).

Specified by:

offer in interface Queue<T>

Parameters:

element - The element to insert,

Returns:

True, if element is added, false otherwise.

peek

public final T peek()

Returns the least element of the PriorityQueue in constant time, but does not remove it from the priority queue.

Specified by:

peek in interface Queue<T>

Returns:

The least element.

poll

public final T poll()

Removes and returns the least element of the PriorityQueue in log(size) time.

Specified by:

poll in interface Queue<T>

Returns:

The least element.

adjustTop

public final void adjustTop()

Should be called when the Object at top changes values. Still log(n) worst case, but it's at least twice as fast to

 {
        pq.top().change();
        pq.adjustTop();
 }
 

instead of

 {
        o = pq.pop();
        o.change();
        pq.push(o);
 }
 

size

public final int size()

Returns the number of elements currently stored in the PriorityQueue.

Specified by:

size in interface Collection<T>

Specified by:

size in class AbstractCollection<T>

Returns:

The number of elements in the queue.

clear

public final void clear()

Removes all entries from the PriorityQueue.

Specified by:

clear in interface Collection<T>

Overrides:

clear in class AbstractQueue<T>

iterator

public Iterator<T> iterator()

Specified by:

iterator in interface Iterable<T>

Specified by:

iterator in interface Collection<T>

Specified by:

iterator in class AbstractCollection<T>