Class RadixSelector

java.lang.Object
org.apache.lucene.util.Selector
org.apache.lucene.util.RadixSelector

public abstract class RadixSelector extends Selector
Radix selector.

This implementation works similarly to a MSB radix sort except that it only recurses into the sub partition that contains the desired value.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private final int[]
     
    private final int[]
     
    private static final int
     
    private static final int
     
    private static final int
     
    private final int
     
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    RadixSelector(int maxLength)
    Sole constructor.
  • Method Summary

    Modifier and Type
    Method
    Description
    private boolean
    assertHistogram(int commonPrefixLength, int[] histogram)
     
    private void
    buildHistogram(int from, int to, int k, int[] histogram)
    Build an histogram of the k-th characters of values occurring between offsets from and to, using getBucket(int, int).
    protected abstract int
    byteAt(int i, int k)
    Return the k-th byte of the entry at index i, or -1 if its length is less than or equal to k.
    private int
    computeCommonPrefixLengthAndBuildHistogram(int from, int to, int k, int[] histogram)
    Build a histogram of the number of values per bucket and return a common prefix length for all visited values.
    private int
    computeCommonPrefixLengthAndBuildHistogramPart1(int from, int to, int k, int[] histogram, int commonPrefixLength)
     
    private int
    computeCommonPrefixLengthAndBuildHistogramPart2(int from, int to, int k, int[] histogram, int commonPrefixLength, int i)
     
    private int
     
    private int
    getBucket(int i, int k)
    Return a number for the k-th character between 0 and HISTOGRAM_SIZE.
    protected Selector
    Get a fall-back selector which may assume that the first d bytes of all compared strings are equal.
    private void
    partition(int from, int to, int bucket, int bucketFrom, int bucketTo, int d)
    Reorder elements so that all of them that fall into bucket are between offsets bucketFrom and bucketTo.
    private void
    radixSelect(int from, int to, int k, int d, int l)
     
    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.
    private void
    select(int from, int to, int k, int d, int l)
     

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

    checkArgs, swap

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • LEVEL_THRESHOLD

      private static final int LEVEL_THRESHOLD
      See Also:
    • HISTOGRAM_SIZE

      private static final int HISTOGRAM_SIZE
      See Also:
    • LENGTH_THRESHOLD

      private static final int LENGTH_THRESHOLD
      See Also:
    • histogram

      private final int[] histogram
    • commonPrefix

      private final int[] commonPrefix
    • maxLength

      private final int maxLength
  • Constructor Details

    • RadixSelector

      protected RadixSelector(int maxLength)
      Sole constructor.
      Parameters:
      maxLength - the maximum length of keys, pass Integer.MAX_VALUE if unknown.
  • Method Details

    • byteAt

      protected abstract int byteAt(int i, int k)
      Return the k-th byte of the entry at index i, or -1 if its length is less than or equal to k. This may only be called with a value of k between 0 included and maxLength excluded.
    • getFallbackSelector

      protected Selector getFallbackSelector(int d)
      Get a fall-back selector which may assume that the first d bytes of all compared strings are equal. This fallback selector is used when the range becomes narrow or when the maximum level of recursion has been exceeded.
    • select

      public 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
    • select

      private void select(int from, int to, int k, int d, int l)
    • radixSelect

      private void radixSelect(int from, int to, int k, int d, int l)
      Parameters:
      d - the character number to compare
      l - the level of recursion
    • assertHistogram

      private boolean assertHistogram(int commonPrefixLength, int[] histogram)
    • getBucket

      private int getBucket(int i, int k)
      Return a number for the k-th character between 0 and HISTOGRAM_SIZE.
    • computeCommonPrefixLengthAndBuildHistogram

      private int computeCommonPrefixLengthAndBuildHistogram(int from, int to, int k, int[] histogram)
      Build a histogram of the number of values per bucket and return a common prefix length for all visited values.
      See Also:
    • computeInitialCommonPrefixLength

      private int computeInitialCommonPrefixLength(int from, int k)
    • computeCommonPrefixLengthAndBuildHistogramPart1

      private int computeCommonPrefixLengthAndBuildHistogramPart1(int from, int to, int k, int[] histogram, int commonPrefixLength)
    • computeCommonPrefixLengthAndBuildHistogramPart2

      private int computeCommonPrefixLengthAndBuildHistogramPart2(int from, int to, int k, int[] histogram, int commonPrefixLength, int i)
    • buildHistogram

      private void buildHistogram(int from, int to, int k, int[] histogram)
      Build an histogram of the k-th characters of values occurring between offsets from and to, using getBucket(int, int).
    • partition

      private void partition(int from, int to, int bucket, int bucketFrom, int bucketTo, int d)
      Reorder elements so that all of them that fall into bucket are between offsets bucketFrom and bucketTo.