Package org.apache.lucene.util

Class 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 Description
      SorterTemplate()  

    • Method Summary

      All Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method 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

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