public abstract class RadixSelector extends Selector
This implementation works similarly to a MSB radix sort except that it only recurses into the sub partition that contains the desired value.
Modifier and Type | Field and 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 |
Modifier | Constructor and Description |
---|---|
protected |
RadixSelector(int maxLength)
Sole constructor.
|
Modifier and Type | Method and 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) |
private static final int LEVEL_THRESHOLD
private static final int HISTOGRAM_SIZE
private static final int LENGTH_THRESHOLD
private final int[] histogram
private final int[] commonPrefix
private final int maxLength
protected RadixSelector(int maxLength)
maxLength
- the maximum length of keys, pass Integer.MAX_VALUE
if unknown.protected abstract int byteAt(int i, int k)
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.protected Selector getFallbackSelector(int d)
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.public void select(int from, int to, int k)
Selector
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)
private void radixSelect(int from, int to, int k, int d, int l)
d
- the character number to comparel
- the level of recursionprivate boolean assertHistogram(int commonPrefixLength, int[] histogram)
private int getBucket(int i, int k)
HISTOGRAM_SIZE
.private int computeCommonPrefixLengthAndBuildHistogram(int from, int to, int k, int[] histogram)
bucket
and return a common prefix length for all visited values.buildHistogram(int, int, int, int[])
private void buildHistogram(int from, int to, int k, int[] histogram)
from
and to
, using getBucket(int, int)
.private void partition(int from, int to, int bucket, int bucketFrom, int bucketTo, int d)
bucket
are
between offsets bucketFrom
and bucketTo
.