Package org.apache.flink.runtime.operators.sort

Class 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 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.