Package org.apache.lucene.util

Class IntroSelector

java.lang.Object

org.apache.lucene.util.Selector

org.apache.lucene.util.IntroSelector

public abstract class IntroSelector
extends Selector

Adaptive selection algorithm based on the introspective quick select algorithm. The quick select algorithm uses an interpolation variant of Tukey's ninther median-of-medians for pivot, and Bentley-McIlroy 3-way partitioning. For the introspective protection, it shuffles the sub-range if the max recursive depth is exceeded.

This selection algorithm is fast on most data shapes, especially on nearly sorted data, or when k is close to the boundaries. It runs in linear time on average.

Field Summary

Fields

Modifier and Type	Field	Description
private java.util.SplittableRandom	random

Constructor Summary

Constructors

Constructor	Description
IntroSelector()

Method Summary

Modifier and Type	Method	Description
protected int	compare(int i, int j)	Compare entries found in slots i and j.
protected abstract int	comparePivot(int j)	Compare the pivot with the slot at j, similarly to compare(i, j).
private int	max(int i, int j, int k)	Returns the index of the max element among three elements at provided indices.
private int	median(int i, int j, int k)	Copy of IntroSorter#median.
private int	min(int i, int j, int k)	Returns the index of the min element among three elements at provided indices.
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.
(package private) void	select(int from, int to, int k, int maxDepth)
protected abstract void	setPivot(int i)	Save the value at slot i so that it can later be used as a pivot, see comparePivot(int).
private void	shuffle(int from, int to)	Shuffles the entries between from (inclusive) and to (exclusive) with Durstenfeld's algorithm.
private void	sort3(int from)	Sorts 3 entries starting at from (inclusive).

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 Detail

random

private java.util.SplittableRandom random

Constructor Detail

IntroSelector

public IntroSelector()

Method Detail

select

public final 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

void select(int from,
            int to,
            int k,
            int maxDepth)

min

private int min(int i,
                int j,
                int k)

Returns the index of the min element among three elements at provided indices.

max

private int max(int i,
                int j,
                int k)

Returns the index of the max element among three elements at provided indices.

median

private int median(int i,
                   int j,
                   int k)

Copy of IntroSorter#median.

sort3

private void sort3(int from)

Sorts 3 entries starting at from (inclusive). This specialized method is more efficient than calling Sorter.insertionSort(int, int).

shuffle

private void shuffle(int from,
                     int to)

Shuffles the entries between from (inclusive) and to (exclusive) with Durstenfeld's algorithm.

setPivot

protected abstract void setPivot(int i)

Save the value at slot i so that it can later be used as a pivot, see comparePivot(int).

comparePivot

protected abstract int comparePivot(int j)

Compare the pivot with the slot at j, similarly to compare(i, j).

compare

protected int compare(int i,
                      int j)

Compare entries found in slots i and j. The contract for the returned value is the same as Comparator.compare(Object, Object).