java.lang.Object
org.apache.lucene.util.Sorter
org.apache.lucene.util.TimSorter
- Direct Known Subclasses:
ArrayTimSorter
,CollectionUtil.ListTimSorter
,FreqProxTermsWriter.SortingPostingsEnum.DocOffsetSorter
,Sorter.DocValueSorter
Sorter
implementation based on the TimSort algorithm. It
sorts small arrays with a binary sort.
This algorithm is stable. It's especially good at sorting partially-sorted arrays.
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
FieldsModifier and TypeFieldDescription(package private) final int
(package private) static final int
(package private) int
(package private) static final int
(package private) int[]
(package private) int
(package private) static final int
(package private) static final int
(package private) int
Fields inherited from class org.apache.lucene.util.Sorter
BINARY_SORT_THRESHOLD, INSERTION_SORT_THRESHOLD
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprotected abstract int
compareSaved
(int i, int j) Compare elementi
from the temporary storage with elementj
from the slice to sort, similarly toSorter.compare(int, int)
.protected abstract void
copy
(int src, int dest) Copy data from slotsrc
to slotdest
.(package private) void
doRotate
(int lo, int mid, int hi) (package private) void
(package private) void
(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 lengthlength
.(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 elementj
from the temporary storage into sloti
.(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 slotsi
andi+len
into the temporary storage.(package private) void
setRunEnd
(int i, int runEnd) void
sort
(int from, int to) Sort the slice which starts atfrom
(inclusive) and ends atto
(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, insertionSort, lower, lower2, mergeInPlace, reverse, rotate, setPivot, siftDown, swap, upper, upper2
-
Field Details
-
MINRUN
static final int MINRUN- See Also:
-
THRESHOLD
static final int THRESHOLD- See Also:
-
STACKSIZE
static final int STACKSIZE- See Also:
-
MIN_GALLOP
static final int MIN_GALLOP- See Also:
-
maxTempSlots
final int maxTempSlots -
minRun
int minRun -
to
int to -
stackSize
int stackSize -
runEnds
int[] runEnds
-
-
Constructor Details
-
TimSorter
protected TimSorter(int maxTempSlots) Create a newTimSorter
.- Parameters:
maxTempSlots
- the maximum amount of extra memory to run merges
-
-
Method Details
-
minRun
static int minRun(int length) Minimum run length for an array of lengthlength
. -
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 atfrom
(inclusive) and ends atto
(exclusive). -
doRotate
void doRotate(int lo, int mid, int hi) -
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 slotsrc
to slotdest
. -
save
protected abstract void save(int i, int len) Save all elements between slotsi
andi+len
into the temporary storage. -
restore
protected abstract void restore(int i, int j) Restore elementj
from the temporary storage into sloti
. -
compareSaved
protected abstract int compareSaved(int i, int j) Compare elementi
from the temporary storage with elementj
from the slice to sort, similarly toSorter.compare(int, int)
.
-