Package org.apache.lucene.util

Class IntroSelector

java.lang.Object
org.apache.lucene.util.Selector
org.apache.lucene.util.IntroSelector
public abstract class IntroSelector extends Selector
Adaptive selection algorithm based on the introspective quick select algorithm. The quick select algorithm uses an interpolation variant of Tukey's ninther median-of-medians for pivot, and Bentley-McIlroy 3-way partitioning. For the introspective protection, it shuffles the sub-range if the max recursive depth is exceeded.

This selection algorithm is fast on most data shapes, especially on nearly sorted data, or when k is close to the boundaries. It runs in linear time on average.

NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.

  • Constructor Summary

    Constructors
    Constructor
    Description
    IntroSelector()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    protected int
    compare(int i, int j)
    Compare entries found in slots i and j.
    protected abstract int
    comparePivot(int j)
    Compare the pivot with the slot at j, similarly to compare(i, j).
    final void
    select(int from, int to, int k)
    Reorder elements so that the element at position k is the same as if all elements were sorted and all other elements are partitioned around it: [from, k) only contains elements that are less than or equal to k and (k, to) only contains elements that are greater than or equal to k.
    protected abstract void
    setPivot(int i)
    Save the value at slot i so that it can later be used as a pivot, see comparePivot(int).

    Methods inherited from class org.apache.lucene.util.Selector

    swap

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • IntroSelector

      public IntroSelector()

  • Method Details

    • select

      public final void select(int from, int to, int k)
      Description copied from class: Selector
      Reorder elements so that the element at position k is the same as if all elements were sorted and all other elements are partitioned around it: [from, k) only contains elements that are less than or equal to k and (k, to) only contains elements that are greater than or equal to k.
      Specified by:
      select in class Selector

    • setPivot

      protected abstract void setPivot(int i)
      Save the value at slot i so that it can later be used as a pivot, see comparePivot(int).

    • comparePivot

      protected abstract int comparePivot(int j)
      Compare the pivot with the slot at j, similarly to compare(i, j).

    • compare

      protected int compare(int i, int j)
      Compare entries found in slots i and j. The contract for the returned value is the same as Comparator.compare(Object, Object).