Package org.apache.solr.util

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

    • Constructor Summary

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

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      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.

    • Field Detail

      • size

        protected int size

      • currentCapacity

        protected int currentCapacity

      • maxSize

        protected int maxSize

      • heap

        protected long[] heap

      • sentinel

        protected final long sentinel

    • Constructor Detail

      • LongPriorityQueue

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

    • Method Detail

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