Module org.apache.lucene.core

Package org.apache.lucene.util

Class StableMSBRadixSorter

java.lang.Object

org.apache.lucene.util.Sorter

org.apache.lucene.util.MSBRadixSorter

org.apache.lucene.util.StableMSBRadixSorter

public abstract class StableMSBRadixSorter
extends MSBRadixSorter

Stable radix sorter for variable-length strings.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	StableMSBRadixSorter.MergeSorter	A MergeSorter taking advantage of temporary storage.

Field Summary

Fields

Modifier and Type	Field	Description
private final int[]	fixedStartOffsets

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

HISTOGRAM_SIZE, LENGTH_THRESHOLD, LEVEL_THRESHOLD, maxLength

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

BINARY_SORT_THRESHOLD, INSERTION_SORT_THRESHOLD

Constructor Summary

Constructors

Constructor	Description
StableMSBRadixSorter(int maxLength)

Method Summary

Modifier and Type	Method	Description
protected Sorter	getFallbackSorter(int k)	Get a fall-back sorter which may assume that the first k bytes of all compared strings are equal.
protected void	reorder(int from, int to, int[] startOffsets, int[] endOffsets, int k)	Reorder elements in stable way, since Dutch sort does not guarantee ordering for same values.
protected abstract void	restore(int i, int j)	Restore values between i-th and j-th(excluding) in temporary storage into original storage.
protected abstract void	save(int i, int j)	Save the i-th value into the j-th position in temporary storage.

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

buildHistogram, byteAt, compare, getBucket, shouldFallback, sort, sort

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

binarySort, binarySort, checkRange, comparePivot, doRotate, heapChild, heapify, heapParent, heapSort, insertionSort, 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 Details

fixedStartOffsets

private final int[] fixedStartOffsets

Constructor Details

StableMSBRadixSorter

public StableMSBRadixSorter(int maxLength)

Method Details

save

protected abstract void save(int i,
 int j)

Save the i-th value into the j-th position in temporary storage.

restore

protected abstract void restore(int i,
 int j)

Restore values between i-th and j-th(excluding) in temporary storage into original storage.

getFallbackSorter

protected Sorter getFallbackSorter(int k)

Description copied from class: MSBRadixSorter

Get a fall-back sorter which may assume that the first k bytes of all compared strings are equal.

Overrides:

getFallbackSorter in class MSBRadixSorter

reorder

protected void reorder(int from,
 int to,
 int[] startOffsets,
 int[] endOffsets,
 int k)

Reorder elements in stable way, since Dutch sort does not guarantee ordering for same values.

When this method returns, startOffsets and endOffsets are equal.

Overrides:

reorder in class MSBRadixSorter

Parameters:

startOffsets - start offsets per bucket

endOffsets - end offsets per bucket