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.

    • 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
      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 getBucket​(int i, int k)
      Return a number for the k-th character between 0 and HISTOGRAM_SIZE.
      protected Selector getFallbackSelector​(int d)
      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 java.lang.Object

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

    • Field Detail

      • histogram

        private final int[] histogram

      • commonPrefix

        private final int[] commonPrefix

      • maxLength

        private final int maxLength

    • 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

      • 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:
        buildHistogram(int, int, int, int[])

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