org.apache.lucene.util

Class SorterTemplate

java.lang.Object

org.apache.lucene.util.SorterTemplate

public abstract class SorterTemplate
extends Object

This class was inspired by CGLIB, but provides a better QuickSort algorithm without additional InsertionSort at the end. To use, subclass and override the four abstract methods which compare and modify your data. Allows custom swap so that two arrays can be sorted at the same time.

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

Constructor Summary

Constructors

Constructor and Description
SorterTemplate()

Method Summary

Methods

Modifier and Type	Method and Description
protected abstract int	compare(int i, int j) Compares slots i and j of you data.
protected abstract int	comparePivot(int j) Implements the compare function for the previously stored pivot value.
void	insertionSort(int lo, int hi) Sorts via stable in-place InsertionSort algorithm (ideal for small collections which are mostly presorted).
void	mergeSort(int lo, int hi) Sorts via stable in-place MergeSort algorithm For small collections falls back to insertionSort(int,int).
void	quickSort(int lo, int hi) Sorts via in-place, but unstable, QuickSort algorithm.
protected abstract void	setPivot(int i) Implement this method, that stores the value of slot i as pivot value
protected abstract void	swap(int i, int j) Implement this method, that swaps slots i and j in your data

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SorterTemplate

public SorterTemplate()

Method Detail

swap

protected abstract void swap(int i,
        int j)

Implement this method, that swaps slots i and j in your data

compare

protected abstract int compare(int i,
          int j)

Compares slots i and j of you data. Should be implemented like valueOf(i).compareTo(valueOf(j))

setPivot

protected abstract void setPivot(int i)

Implement this method, that stores the value of slot i as pivot value

comparePivot

protected abstract int comparePivot(int j)

Implements the compare function for the previously stored pivot value. Should be implemented like pivot.compareTo(valueOf(j))

insertionSort

public final void insertionSort(int lo,
                 int hi)

Sorts via stable in-place InsertionSort algorithm (ideal for small collections which are mostly presorted).

quickSort

public final void quickSort(int lo,
             int hi)

Sorts via in-place, but unstable, QuickSort algorithm. For small collections falls back to insertionSort(int,int).

mergeSort

public final void mergeSort(int lo,
             int hi)

Sorts via stable in-place MergeSort algorithm For small collections falls back to insertionSort(int,int).