Module org.apache.lucene.core

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.

Field Summary

Fields

Modifier and Type	Field	Description
private final int[]	commonPrefix
private final int[]	histogram
private static final int	HISTOGRAM_SIZE
private static final int	LENGTH_THRESHOLD
private static final int	LEVEL_THRESHOLD
private final int	maxLength

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	computeInitialCommonPrefixLength(int from, int k)
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 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:

• Constant Field Values

HISTOGRAM_SIZE

private static final int HISTOGRAM_SIZE

See Also:

• Constant Field Values

LENGTH_THRESHOLD

private static final int LENGTH_THRESHOLD

See Also:

• Constant Field Values

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:

• buildHistogram(int, int, int, int[])

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.