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 int[]
commonPrefix
private int[]
histogram
private static int
HISTOGRAM_SIZE
private static int
LENGTH_THRESHOLD
private static int
LEVEL_THRESHOLD
private int
maxLength
-
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 offsetsfrom
andto
, usinggetBucket(int, int)
.protected abstract int
byteAt(int i, int k)
Return the k-th byte of the entry at indexi
, or-1
if its length is less than or equal tok
.private int
computeCommonPrefixLengthAndBuildHistogram(int from, int to, int k, int[] histogram)
Build a histogram of the number of values perbucket
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 andHISTOGRAM_SIZE
.protected Selector
getFallbackSelector(int d)
Get a fall-back selector which may assume that the firstd
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 intobucket
are between offsetsbucketFrom
andbucketTo
.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 positionk
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 tok
and(k, to)
only contains elements that are greater than or equal tok
.private void
select(int from, int to, int k, int d, int l)
-
-
-
Field Detail
-
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
-
-
Method Detail
-
byteAt
protected abstract int byteAt(int i, int k)
Return the k-th byte of the entry at indexi
, or-1
if its length is less than or equal tok
. This may only be called with a value ofi
between0
included andmaxLength
excluded.
-
getFallbackSelector
protected Selector getFallbackSelector(int d)
Get a fall-back selector which may assume that the firstd
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 positionk
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 tok
and(k, to)
only contains elements that are greater than or equal tok
.
-
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 comparel
- 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 andHISTOGRAM_SIZE
.
-
computeCommonPrefixLengthAndBuildHistogram
private int computeCommonPrefixLengthAndBuildHistogram(int from, int to, int k, int[] histogram)
Build a histogram of the number of values perbucket
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 offsetsfrom
andto
, usinggetBucket(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 intobucket
are between offsetsbucketFrom
andbucketTo
.
-
-