lucene-java-3.5.0/lucene/src/java/org/apache/lucene/util/SorterTemplate.java

   1 package org.apache.lucene.util;
   2
   3 /**
   4  * Licensed to the Apache Software Foundation (ASF) under one or more
   5  * contributor license agreements.  See the NOTICE file distributed with
   6  * this work for additional information regarding copyright ownership.
   7  * The ASF licenses this file to You under the Apache License, Version 2.0
   8  * (the "License"); you may not use this file except in compliance with
   9  * the License.  You may obtain a copy of the License at
  10  *
  11  *     http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  */
  19
  20 /**
  21  * This class was inspired by CGLIB, but provides a better
  22  * QuickSort algorithm without additional InsertionSort
  23  * at the end.
  24  * To use, subclass and override the four abstract methods
  25  * which compare and modify your data.
  26  * Allows custom swap so that two arrays can be sorted
  27  * at the same time.
  28  * @lucene.internal
  29  */
  30 public abstract class SorterTemplate {
  31
  32   private static final int MERGESORT_THRESHOLD = 12;
  33   private static final int QUICKSORT_THRESHOLD = 7;
  34
  35   /** Implement this method, that swaps slots {@code i} and {@code j} in your data */
  36   protected abstract void swap(int i, int j);
  37
  38   /** Compares slots {@code i} and {@code j} of you data.
  39    * Should be implemented like <code><em>valueOf(i)</em>.compareTo(<em>valueOf(j)</em>)</code> */
  40   protected abstract int compare(int i, int j);
  41
  42   /** Implement this method, that stores the value of slot {@code i} as pivot value */
  43   protected abstract void setPivot(int i);
  44
  45   /** Implements the compare function for the previously stored pivot value.
  46    * Should be implemented like <code>pivot.compareTo(<em>valueOf(j)</em>)</code> */
  47   protected abstract int comparePivot(int j);
  48
  49   /** Sorts via stable in-place InsertionSort algorithm
  50    *(ideal for small collections which are mostly presorted). */
  51   public final void insertionSort(int lo, int hi) {
  52     for (int i = lo + 1 ; i <= hi; i++) {
  53       for (int j = i; j > lo; j--) {
  54         if (compare(j - 1, j) > 0) {
  55           swap(j - 1, j);
  56         } else {
  57           break;
  58         }
  59       }
  60     }
  61   }
  62
  63   /** Sorts via in-place, but unstable, QuickSort algorithm.
  64    * For small collections falls back to {@link #insertionSort(int,int)}. */
  65   public final void quickSort(final int lo, final int hi) {
  66     if (hi <= lo) return;
  67     // from Integer's Javadocs: ceil(log2(x)) = 32 - numberOfLeadingZeros(x - 1)
  68     quickSort(lo, hi, (Integer.SIZE - Integer.numberOfLeadingZeros(hi - lo)) << 1);
  69   }
  70
  71   private void quickSort(int lo, int hi, int maxDepth) {
  72     // fall back to insertion when array has short length
  73     final int diff = hi - lo;
  74     if (diff <= QUICKSORT_THRESHOLD) {
  75       insertionSort(lo, hi);
  76       return;
  77     }
  78
  79     // fall back to merge sort when recursion depth gets too big
  80     if (--maxDepth == 0) {
  81       mergeSort(lo, hi);
  82       return;
  83     }
  84
  85     final int mid = lo + (diff >>> 1);
  86
  87     if (compare(lo, mid) > 0) {
  88       swap(lo, mid);
  89     }
  90
  91     if (compare(mid, hi) > 0) {
  92       swap(mid, hi);
  93       if (compare(lo, mid) > 0) {
  94         swap(lo, mid);
  95       }
  96     }
  97
  98     int left = lo + 1;
  99     int right = hi - 1;
 100
 101     setPivot(mid);
 102     for (;;) {
 103       while (comparePivot(right) < 0)
 104         --right;
 105
 106       while (left < right && comparePivot(left) >= 0)
 107         ++left;
 108
 109       if (left < right) {
 110         swap(left, right);
 111         --right;
 112       } else {
 113         break;
 114       }
 115     }
 116
 117     quickSort(lo, left, maxDepth);
 118     quickSort(left + 1, hi, maxDepth);
 119   }
 120
 121   /** Sorts via stable in-place MergeSort algorithm
 122    * For small collections falls back to {@link #insertionSort(int,int)}. */
 123   public final void mergeSort(int lo, int hi) {
 124     final int diff = hi - lo;
 125     if (diff <= MERGESORT_THRESHOLD) {
 126       insertionSort(lo, hi);
 127       return;
 128     }
 129
 130     final int mid = lo + (diff >>> 1);
 131
 132     mergeSort(lo, mid);
 133     mergeSort(mid, hi);
 134     merge(lo, mid, hi, mid - lo, hi - mid);
 135   }
 136
 137   private void merge(int lo, int pivot, int hi, int len1, int len2) {
 138     if (len1 == 0 || len2 == 0) {
 139       return;
 140     }
 141     if (len1 + len2 == 2) {
 142       if (compare(pivot, lo) < 0) {
 143           swap(pivot, lo);
 144       }
 145       return;
 146     }
 147     int first_cut, second_cut;
 148     int len11, len22;
 149     if (len1 > len2) {
 150       len11 = len1 >>> 1;
 151       first_cut = lo + len11;
 152       second_cut = lower(pivot, hi, first_cut);
 153       len22 = second_cut - pivot;
 154     } else {
 155       len22 = len2 >>> 1;
 156       second_cut = pivot + len22;
 157       first_cut = upper(lo, pivot, second_cut);
 158       len11 = first_cut - lo;
 159     }
 160     rotate(first_cut, pivot, second_cut);
 161     final int new_mid = first_cut + len22;
 162     merge(lo, first_cut, new_mid, len11, len22);
 163     merge(new_mid, second_cut, hi, len1 - len11, len2 - len22);
 164   }
 165
 166   private void rotate(int lo, int mid, int hi) {
 167     int lot = lo;
 168     int hit = mid - 1;
 169     while (lot < hit) {
 170       swap(lot++, hit--);
 171     }
 172     lot = mid; hit = hi - 1;
 173     while (lot < hit) {
 174       swap(lot++, hit--);
 175     }
 176     lot = lo; hit = hi - 1;
 177     while (lot < hit) {
 178       swap(lot++, hit--);
 179     }
 180   }
 181
 182   private int lower(int lo, int hi, int val) {
 183     int len = hi - lo;
 184     while (len > 0) {
 185       final int half = len >>> 1,
 186         mid = lo + half;
 187       if (compare(mid, val) < 0) {
 188         lo = mid + 1;
 189         len = len - half -1;
 190       } else {
 191         len = half;
 192       }
 193     }
 194     return lo;
 195   }
 196
 197   private int upper(int lo, int hi, int val) {
 198     int len = hi - lo;
 199     while (len > 0) {
 200       final int half = len >>> 1,
 201         mid = lo + half;
 202       if (compare(val, mid) < 0) {
 203         len = half;
 204       } else {
 205         lo = mid + 1;
 206         len = len - half -1;
 207       }
 208     }
 209     return lo;
 210   }
 211
 212 }