Package org.apache.lucene.util

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.

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

  • Constructor Summary

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

  • Method Summary

    Modifier and Type
    Method
    Description
    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.
    protected Selector
    getFallbackSelector(int d)
    Get a fall-back selector which may assume that the first d bytes of all compared strings are equal.
    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.

    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

    • 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