Package org.apache.solr.util

Class LongPriorityQueue

java.lang.Object
org.apache.solr.util.LongPriorityQueue
public class LongPriorityQueue extends Object
A native long priority queue.
NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected int
    currentCapacity
     
    protected long[]
    heap
     
    protected int
    maxSize
     
    protected final long
    sentinel
     
    protected int
    size
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    LongPriorityQueue(int initialSize, int maxSize, long sentinel)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    long
    add(long element)
    Adds an object to a PriorityQueue in log(size) time.
    void
    addNoCheck(long element)
    Adds an object to a PriorityQueue in log(size) time.
    void
    clear()
    Removes all entries from the PriorityQueue.
    int
    getCurrentCapacity()
     
    long[]
    getInternalArray()
    Returns the array used to hold the heap, with the smallest item at array[1] and the last (but not necessarily largest) at array[size()].
    protected void
    initialize(int sz)
     
    boolean
    insert(long element)
    inserts the element and returns true if this element caused another element to be dropped from the queue.
    long
    insertWithOverflow(long element)
    Adds an object to a PriorityQueue in log(size) time.
    long
    pop()
    Removes and returns the least element of the PriorityQueue in log(size) time.
    void
    resize(int sz)
     
    int
    size()
    Returns the number of elements currently stored in the PriorityQueue.
    long[]
    sort(int n)
    Pops the smallest n items from the heap, placing them in the internal array at arr[size] through arr[size-(n-1)] with the smallest (first element popped) being at arr[size].
    long
    top()
    Returns the least element of the PriorityQueue in constant time.
    long
    updateTop()
    Should be called when the Object at top changes values.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • size

      protected int size

    • currentCapacity

      protected int currentCapacity

    • maxSize

      protected int maxSize

    • heap

      protected long[] heap

    • sentinel

      protected final long sentinel

  • Constructor Details

    • LongPriorityQueue

      public LongPriorityQueue(int initialSize, int maxSize, long sentinel)

  • Method Details

    • initialize

      protected void initialize(int sz)

    • getCurrentCapacity

      public int getCurrentCapacity()

    • resize

      public void resize(int sz)

    • add

      public long add(long element)
      Adds an object to a PriorityQueue in log(size) time. If one tries to add more objects than maxSize from initialize an ArrayIndexOutOfBoundsException is thrown.
      Returns:
      the new 'top' element in the queue.

    • addNoCheck

      public void addNoCheck(long element)
      Adds an object to a PriorityQueue in log(size) time. If one tries to add more objects than the current capacity, an ArrayIndexOutOfBoundsException is thrown.

    • insertWithOverflow

      public long insertWithOverflow(long element)
      Adds an object to a PriorityQueue in log(size) time. It returns the smallest object (if any) that was dropped off the heap because it was full, or the sentinel value.

      This can be the given parameter (in case it is smaller than the full heap's minimum, and couldn't be added), or another object that was previously the smallest value in the heap and now has been replaced by a larger one, or null if the queue wasn't yet full with maxSize elements.

    • insert

      public boolean insert(long element)
      inserts the element and returns true if this element caused another element to be dropped from the queue.

    • top

      public long top()
      Returns the least element of the PriorityQueue in constant time.

    • pop

      public long pop()
      Removes and returns the least element of the PriorityQueue in log(size) time. Only valid if size() > 0.

    • updateTop

      public long updateTop()
      Should be called when the Object at top changes values.
      Returns:
      the new 'top' element.

    • size

      public int size()
      Returns the number of elements currently stored in the PriorityQueue.

    • getInternalArray

      public long[] getInternalArray()
      Returns the array used to hold the heap, with the smallest item at array[1] and the last (but not necessarily largest) at array[size()]. This is *not* fully sorted.

    • sort

      public long[] sort(int n)
      Pops the smallest n items from the heap, placing them in the internal array at arr[size] through arr[size-(n-1)] with the smallest (first element popped) being at arr[size]. The internal array is returned.

    • clear

      public void clear()
      Removes all entries from the PriorityQueue.