Package org.apache.lucene.util

Class TimSorter

java.lang.Object

org.apache.lucene.util.Sorter

org.apache.lucene.util.TimSorter

Direct Known Subclasses:

ArrayTimSorter, CollectionUtil.ListTimSorter, FreqProxTermsWriter.SortingDocsEnum.DocFreqSorter, FreqProxTermsWriter.SortingPostingsEnum.DocOffsetSorter, Sorter.DocValueSorter

public abstract class TimSorter
extends Sorter

Sorter implementation based on the TimSort algorithm.

This implementation is especially good at sorting partially-sorted arrays and sorts small arrays with binary sort.

NOTE:There are a few differences with the original implementation:

• The extra amount of memory to perform merges is configurable. This allows small merges to be very fast while large merges will be performed in-place (slightly slower). You can make sure that the fast merge routine will always be used by having maxTempSlots equal to half of the length of the slice of data to sort.
• Only the fast merge routine can gallop (the one that doesn't run in-place) and it only gallops on the longest slice.

Field Summary

Fields

Modifier and Type	Field	Description
(package private) int	maxTempSlots
(package private) static int	MIN_GALLOP
(package private) int	minRun
(package private) static int	MINRUN
(package private) int[]	runEnds
(package private) int	stackSize
(package private) static int	STACKSIZE
(package private) static int	THRESHOLD
(package private) int	to

Fields inherited from class org.apache.lucene.util.Sorter

BINARY_SORT_THRESHOLD

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	TimSorter(int maxTempSlots)	Create a new TimSorter.

Method Summary

Modifier and Type	Method	Description
protected abstract int	compareSaved(int i, int j)	Compare element i from the temporary storage with element j from the slice to sort, similarly to Sorter.compare(int, int).
protected abstract void	copy(int src, int dest)	Copy data from slot src to slot dest.
(package private) void	doRotate(int lo, int mid, int hi)
(package private) void	ensureInvariants()
(package private) void	exhaustStack()
(package private) int	lowerSaved(int from, int to, int val)
(package private) int	lowerSaved3(int from, int to, int val)
(package private) void	merge(int lo, int mid, int hi)
(package private) void	mergeAt(int n)
(package private) void	mergeHi(int lo, int mid, int hi)
(package private) void	mergeLo(int lo, int mid, int hi)
(package private) static int	minRun(int length)	Minimum run length for an array of length length.
(package private) int	nextRun()	Compute the length of the next run, make the run sorted and return its length.
(package private) void	pushRunLen(int len)
(package private) void	reset(int from, int to)
protected abstract void	restore(int i, int j)	Restore element j from the temporary storage into slot i.
(package private) int	runBase(int i)
(package private) int	runEnd(int i)
(package private) int	runLen(int i)
protected abstract void	save(int i, int len)	Save all elements between slots i and i+len into the temporary storage.
(package private) void	setRunEnd(int i, int runEnd)
void	sort(int from, int to)	Sort the slice which starts at from (inclusive) and ends at to (exclusive).
(package private) int	upperSaved(int from, int to, int val)
(package private) int	upperSaved3(int from, int to, int val)

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

binarySort, binarySort, checkRange, compare, comparePivot, heapChild, heapify, heapParent, heapSort, lower, lower2, mergeInPlace, reverse, rotate, setPivot, siftDown, swap, upper, upper2

Methods inherited from class java.lang.Object

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

Field Detail

MINRUN

static final int MINRUN

See Also:

Constant Field Values

THRESHOLD

static final int THRESHOLD

See Also:

Constant Field Values

STACKSIZE

static final int STACKSIZE

See Also:

Constant Field Values

MIN_GALLOP

static final int MIN_GALLOP

See Also:

Constant Field Values

maxTempSlots

final int maxTempSlots

minRun

int minRun

to

int to

stackSize

int stackSize

runEnds

int[] runEnds

Constructor Detail

TimSorter

protected TimSorter(int maxTempSlots)

Create a new TimSorter.

Parameters:

maxTempSlots - the maximum amount of extra memory to run merges

Method Detail

minRun

static int minRun(int length)

Minimum run length for an array of length length.

runLen

int runLen(int i)

runBase

int runBase(int i)

runEnd

int runEnd(int i)

setRunEnd

void setRunEnd(int i,
               int runEnd)

pushRunLen

void pushRunLen(int len)

nextRun

int nextRun()

Compute the length of the next run, make the run sorted and return its length.

ensureInvariants

void ensureInvariants()

exhaustStack

void exhaustStack()

reset

void reset(int from,
           int to)

mergeAt

void mergeAt(int n)

merge

void merge(int lo,
           int mid,
           int hi)

sort

public void sort(int from,
                 int to)

Description copied from class: Sorter

Sort the slice which starts at from (inclusive) and ends at to (exclusive).

Specified by:

sort in class Sorter

doRotate

void doRotate(int lo,
              int mid,
              int hi)

Overrides:

doRotate in class Sorter

mergeLo

void mergeLo(int lo,
             int mid,
             int hi)

mergeHi

void mergeHi(int lo,
             int mid,
             int hi)

lowerSaved

int lowerSaved(int from,
               int to,
               int val)

upperSaved

int upperSaved(int from,
               int to,
               int val)

lowerSaved3

int lowerSaved3(int from,
                int to,
                int val)

upperSaved3

int upperSaved3(int from,
                int to,
                int val)

copy

protected abstract void copy(int src,
                             int dest)

Copy data from slot src to slot dest.

save

protected abstract void save(int i,
                             int len)

Save all elements between slots i and i+len into the temporary storage.

restore

protected abstract void restore(int i,
                                int j)

Restore element j from the temporary storage into slot i.

compareSaved

protected abstract int compareSaved(int i,
                                    int j)

Compare element i from the temporary storage with element j from the slice to sort, similarly to Sorter.compare(int, int).