Package org.apache.lucene.util

Class 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

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

    • Constructor Detail

      • RadixSelector

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

    • Method Detail

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