Lucene example source code file (SorterTemplate.java)

This example Lucene source code file (SorterTemplate.java) is included in the DevDaily.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Java - Lucene tags/keywords

mergesort_threshold, mergesort_threshold, quicksort_threshold, quicksort_threshold, sortertemplate, sortertemplate

The Lucene SorterTemplate.java source code

package org.apache.lucene.util;

/**
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/**
 * 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.
 * @lucene.internal
 */
public abstract class SorterTemplate {

  private static final int MERGESORT_THRESHOLD = 12;
  private static final int QUICKSORT_THRESHOLD = 7;

  /** Implement this method, that swaps slots {@code i} and {@code j} in your data */
  protected abstract void swap(int i, int j);
  
  /** Compares slots {@code i} and {@code j} of you data.
   * Should be implemented like <code>valueOf(i).compareTo(valueOf(j)) */
  protected abstract int compare(int i, int j);

  /** Implement this method, that stores the value of slot {@code i} as pivot value */
  protected abstract void setPivot(int i);
  
  /** Implements the compare function for the previously stored pivot value.
   * Should be implemented like <code>pivot.compareTo(valueOf(j)) */
  protected abstract int comparePivot(int j);
  
  /** Sorts via stable in-place InsertionSort algorithm
   *(ideal for small collections which are mostly presorted). */
  public final void insertionSort(int lo, int hi) {
    for (int i = lo + 1 ; i <= hi; i++) {
      for (int j = i; j > lo; j--) {
        if (compare(j - 1, j) > 0) {
          swap(j - 1, j);
        } else {
          break;
        }
      }
    }
  }

  /** Sorts via in-place, but unstable, QuickSort algorithm.
   * For small collections falls back to {@link #insertionSort(int,int)}. */
  public final void quickSort(final int lo, final int hi) {
    if (hi <= lo) return;
    // from Integer's Javadocs: ceil(log2(x)) = 32 - numberOfLeadingZeros(x - 1)
    quickSort(lo, hi, (Integer.SIZE - Integer.numberOfLeadingZeros(hi - lo)) << 1);
  }
  
  private void quickSort(int lo, int hi, int maxDepth) {
    // fall back to insertion when array has short length
    final int diff = hi - lo;
    if (diff <= QUICKSORT_THRESHOLD) {
      insertionSort(lo, hi);
      return;
    }
    
    // fall back to merge sort when recursion depth gets too big
    if (--maxDepth == 0) {
      mergeSort(lo, hi);
      return;
    }
    
    final int mid = lo + (diff >>> 1);
    
    if (compare(lo, mid) > 0) {
      swap(lo, mid);
    }

    if (compare(mid, hi) > 0) {
      swap(mid, hi);
      if (compare(lo, mid) > 0) {
        swap(lo, mid);
      }
    }
    
    int left = lo + 1;
    int right = hi - 1;

    setPivot(mid);
    for (;;) {
      while (comparePivot(right) < 0)
        --right;

      while (left < right && comparePivot(left) >= 0)
        ++left;

      if (left < right) {
        swap(left, right);
        --right;
      } else {
        break;
      }
    }

    quickSort(lo, left, maxDepth);
    quickSort(left + 1, hi, maxDepth);
  }
  
  /** Sorts via stable in-place MergeSort algorithm
   * For small collections falls back to {@link #insertionSort(int,int)}. */
  public final void mergeSort(int lo, int hi) {
    final int diff = hi - lo;
    if (diff <= MERGESORT_THRESHOLD) {
      insertionSort(lo, hi);
      return;
    }
    
    final int mid = lo + (diff >>> 1);
    
    mergeSort(lo, mid);
    mergeSort(mid, hi);
    merge(lo, mid, hi, mid - lo, hi - mid);
  }

  private void merge(int lo, int pivot, int hi, int len1, int len2) {
    if (len1 == 0 || len2 == 0) {
      return;
    }
    if (len1 + len2 == 2) {
      if (compare(pivot, lo) < 0) {
          swap(pivot, lo);
      }
      return;
    }
    int first_cut, second_cut;
    int len11, len22;
    if (len1 > len2) {
      len11 = len1 >>> 1;
      first_cut = lo + len11;
      second_cut = lower(pivot, hi, first_cut);
      len22 = second_cut - pivot;
    } else {
      len22 = len2 >>> 1;
      second_cut = pivot + len22;
      first_cut = upper(lo, pivot, second_cut);
      len11 = first_cut - lo;
    }
    rotate(first_cut, pivot, second_cut);
    final int new_mid = first_cut + len22;
    merge(lo, first_cut, new_mid, len11, len22);
    merge(new_mid, second_cut, hi, len1 - len11, len2 - len22);
  }

  private void rotate(int lo, int mid, int hi) {
    int lot = lo;
    int hit = mid - 1;
    while (lot < hit) {
      swap(lot++, hit--);
    }
    lot = mid; hit = hi - 1;
    while (lot < hit) {
      swap(lot++, hit--);
    }
    lot = lo; hit = hi - 1;
    while (lot < hit) {
      swap(lot++, hit--);
    }
  }

  private int lower(int lo, int hi, int val) {
    int len = hi - lo;
    while (len > 0) {
      final int half = len >>> 1,
        mid = lo + half;
      if (compare(mid, val) < 0) {
        lo = mid + 1;
        len = len - half -1;
      } else {
        len = half;
      }
    }
    return lo;
  }

  private int upper(int lo, int hi, int val) {
    int len = hi - lo;
    while (len > 0) {
      final int half = len >>> 1,
        mid = lo + half;
      if (compare(val, mid) < 0) {
        len = half;
      } else {
        lo = mid + 1;
        len = len - half -1;
      }
    }
    return lo;
  }

}