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

Implementation of the quick select algorithm.

It uses the median of the first, middle and last values as a pivot and falls back to a heap sort when the number of recursion levels exceeds 2 lg(n), as a consequence it runs in linear time on average and in n log(n) time in the worst case.

NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.

Constructor Summary

Constructors

Constructor and Description
IntroSelector()

Method Summary

Modifier and Type	Method and 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).
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.
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).

Methods inherited from class org.apache.lucene.util.Selector

swap

Methods inherited from class java.lang.Object

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

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

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

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