org.apache.lucene.util
Class IntroSorter

java.lang.Object
  extended by org.apache.lucene.util.Sorter
      extended by org.apache.lucene.util.IntroSorter

public abstract class IntroSorter
extends Sorter

Sorter implementation based on a variant of the quicksort algorithm called introsort: when the recursion level exceeds the log of the length of the array to sort, it falls back to heapsort. This prevents quicksort from running into its worst-case quadratic runtime. Small arrays are sorted with insertion sort.

NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.

Constructor Summary
IntroSorter()
          Create a new IntroSorter.
 
Method Summary
protected abstract  int comparePivot(int j)
          Compare the pivot with the slot at j, similarly to compare(i, j).
protected abstract  void setPivot(int i)
          Save the value at slot i so that it can later be used as a pivot, see comparePivot(int).
 void sort(int from, int to)
          Sort the slice which starts at from (inclusive) and ends at to (exclusive).
 
Methods inherited from class org.apache.lucene.util.Sorter
compare, swap
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

IntroSorter

public IntroSorter()
Create a new IntroSorter.

Method Detail

sort

public final 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

setPivot

protected abstract void setPivot(int i)
Save the value at slot i so that it can later be used as a pivot, see comparePivot(int).


comparePivot

protected abstract int comparePivot(int j)
Compare the pivot with the slot at j, similarly to compare(i, j).



Copyright © 2000-2014 Apache Software Foundation. All Rights Reserved.