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) final int
    maxTempSlots
     
    (package private) static final int
    MIN_GALLOP
     
    (package private) int
    minRun
     
    (package private) static final int
    MINRUN
     
    (package private) int[]
    runEnds
     
    (package private) int
    stackSize
     
    (package private) static final int
    STACKSIZE
     
    (package private) static final 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 Details

  • Constructor Details

  • Method Details

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