Package org.apache.lucene.util
Class MSBRadixSorter
java.lang.Object
org.apache.lucene.util.Sorter
org.apache.lucene.util.MSBRadixSorter
- Direct Known Subclasses:
StableMSBRadixSorter
Radix sorter for variable-length strings. This class sorts based on the most significant byte
first and falls back to
IntroSorter
when the size of the buckets to sort becomes small.
This algorithm is NOT stable. Worst-case memory usage is about 2.3 KB
.
- NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.
-
Field Summary
Modifier and TypeFieldDescriptionprotected static final int
protected final int
-
Constructor Summary
-
Method Summary
Modifier and TypeMethodDescriptionprotected abstract int
byteAt
(int i, int k) Return the k-th byte of the entry at indexi
, or-1
if its length is less than or equal tok
.protected final int
compare
(int i, int j) Compare entries found in slotsi
andj
.protected int
getBucket
(int i, int k) Return a number for the k-th character between 0 andHISTOGRAM_SIZE
.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 based on start/end offsets for each bucket.void
sort
(int from, int to) Sort the slice which starts atfrom
(inclusive) and ends atto
(exclusive).protected void
sort
(int from, int to, int k, int l) Methods inherited from class org.apache.lucene.util.Sorter
comparePivot, setPivot, swap
-
Field Details
-
HISTOGRAM_SIZE
protected static final int HISTOGRAM_SIZE- See Also:
-
maxLength
protected final int maxLength
-
-
Constructor Details
-
MSBRadixSorter
protected MSBRadixSorter(int maxLength) Sole constructor.- Parameters:
maxLength
- the maximum length of keys, passInteger.MAX_VALUE
if unknown.
-
-
Method Details
-
byteAt
protected abstract int byteAt(int i, int k) Return the k-th byte of the entry at indexi
, or-1
if its length is less than or equal tok
. This may only be called with a value ofi
between0
included andmaxLength
excluded. -
getFallbackSorter
Get a fall-back sorter which may assume that the first k bytes of all compared strings are equal. -
compare
protected final int compare(int i, int j) Description copied from class:Sorter
Compare entries found in slotsi
andj
. The contract for the returned value is the same asComparator.compare(Object, Object)
. -
sort
public void sort(int from, int to) Description copied from class:Sorter
Sort the slice which starts atfrom
(inclusive) and ends atto
(exclusive). -
sort
protected void sort(int from, int to, int k, int l) -
getBucket
protected int getBucket(int i, int k) Return a number for the k-th character between 0 andHISTOGRAM_SIZE
. -
reorder
protected void reorder(int from, int to, int[] startOffsets, int[] endOffsets, int k) Reorder based on start/end offsets for each bucket. When this method returns, startOffsets and endOffsets are equal.- Parameters:
startOffsets
- start offsets per bucketendOffsets
- end offsets per bucket
-