Package org.apache.lucene.util

Class Sorter

    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      protected Sorter()
      Sole constructor, used for inheritance.

    • Method Summary

      All Methods Static Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) void binarySort​(int from, int to)
      A binary sort implementation.
      (package private) void binarySort​(int from, int to, int i)  
      (package private) void checkRange​(int from, int to)  
      protected abstract int compare​(int i, int j)
      Compare entries found in slots i and j.
      protected int comparePivot​(int j)
      Compare the pivot with the slot at j, similarly to compare(i, j).
      (package private) void doRotate​(int lo, int mid, int hi)  
      (package private) static int heapChild​(int from, int i)  
      (package private) void heapify​(int from, int to)  
      (package private) static int heapParent​(int from, int i)  
      (package private) void heapSort​(int from, int to)
      Use heap sort to sort items between from inclusive and to exclusive.
      (package private) int lower​(int from, int to, int val)  
      (package private) int lower2​(int from, int to, int val)  
      (package private) void mergeInPlace​(int from, int mid, int to)  
      (package private) void reverse​(int from, int to)  
      (package private) void rotate​(int lo, int mid, int hi)  
      protected void setPivot​(int i)
      Save the value at slot i so that it can later be used as a pivot, see comparePivot(int).
      (package private) void siftDown​(int i, int from, int to)  
      abstract void sort​(int from, int to)
      Sort the slice which starts at from (inclusive) and ends at to (exclusive).
      protected abstract void swap​(int i, int j)
      Swap values at slots i and j.
      (package private) int upper​(int from, int to, int val)  
      (package private) int upper2​(int from, int to, int val)  

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • pivotIndex

        private int pivotIndex

    • Constructor Detail

      • Sorter

        protected Sorter()
        Sole constructor, used for inheritance.

    • Method Detail

      • compare

        protected abstract int compare​(int i,
                               int j)
        Compare entries found in slots i and j. The contract for the returned value is the same as Comparator.compare(Object, Object).

      • swap

        protected abstract void swap​(int i,
                             int j)
        Swap values at slots i and j.

      • setPivot

        protected 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 int comparePivot​(int j)
        Compare the pivot with the slot at j, similarly to compare(i, j).

      • sort

        public abstract void sort​(int from,
                          int to)
        Sort the slice which starts at from (inclusive) and ends at to (exclusive).

      • checkRange

        void checkRange​(int from,
                int to)

      • mergeInPlace

        void mergeInPlace​(int from,
                  int mid,
                  int to)

      • lower

        int lower​(int from,
          int to,
          int val)

      • upper

        int upper​(int from,
          int to,
          int val)

      • lower2

        int lower2​(int from,
           int to,
           int val)

      • upper2

        int upper2​(int from,
           int to,
           int val)

      • reverse

        final void reverse​(int from,
                   int to)

      • rotate

        final void rotate​(int lo,
                  int mid,
                  int hi)

      • doRotate

        void doRotate​(int lo,
              int mid,
              int hi)

      • binarySort

        void binarySort​(int from,
                int to)
        A binary sort implementation. This performs O(n*log(n)) comparisons and O(n^2) swaps. It is typically used by more sophisticated implementations as a fall-back when the numbers of items to sort has become less than 20.

      • binarySort

        void binarySort​(int from,
                int to,
                int i)

      • heapSort

        void heapSort​(int from,
              int to)
        Use heap sort to sort items between from inclusive and to exclusive. This runs in O(n*log(n)) and is used as a fall-back by IntroSorter.

      • heapify

        void heapify​(int from,
             int to)

      • siftDown

        void siftDown​(int i,
              int from,
              int to)

      • heapParent

        static int heapParent​(int from,
                      int i)

      • heapChild

        static int heapChild​(int from,
                     int i)