1 package org.apache.lucene.util;
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
11 * http://www.apache.org/licenses/LICENSE-2.0
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.
21 * This class was inspired by CGLIB, but provides a better
22 * QuickSort algorithm without additional InsertionSort
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
30 public abstract class SorterTemplate {
32 private static final int MERGESORT_THRESHOLD = 12;
33 private static final int QUICKSORT_THRESHOLD = 7;
35 /** Implement this method, that swaps slots {@code i} and {@code j} in your data */
36 protected abstract void swap(int i, int j);
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);
42 /** Implement this method, that stores the value of slot {@code i} as pivot value */
43 protected abstract void setPivot(int i);
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);
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) {
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) {
67 // from Integer's Javadocs: ceil(log2(x)) = 32 - numberOfLeadingZeros(x - 1)
68 quickSort(lo, hi, (Integer.SIZE - Integer.numberOfLeadingZeros(hi - lo)) << 1);
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);
79 // fall back to merge sort when recursion depth gets too big
80 if (--maxDepth == 0) {
85 final int mid = lo + (diff >>> 1);
87 if (compare(lo, mid) > 0) {
91 if (compare(mid, hi) > 0) {
93 if (compare(lo, mid) > 0) {
103 while (comparePivot(right) < 0)
106 while (left < right && comparePivot(left) >= 0)
117 quickSort(lo, left, maxDepth);
118 quickSort(left + 1, hi, maxDepth);
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);
130 final int mid = lo + (diff >>> 1);
134 merge(lo, mid, hi, mid - lo, hi - mid);
137 private void merge(int lo, int pivot, int hi, int len1, int len2) {
138 if (len1 == 0 || len2 == 0) {
141 if (len1 + len2 == 2) {
142 if (compare(pivot, lo) < 0) {
147 int first_cut, second_cut;
151 first_cut = lo + len11;
152 second_cut = lower(pivot, hi, first_cut);
153 len22 = second_cut - pivot;
156 second_cut = pivot + len22;
157 first_cut = upper(lo, pivot, second_cut);
158 len11 = first_cut - lo;
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);
166 private void rotate(int lo, int mid, int hi) {
172 lot = mid; hit = hi - 1;
176 lot = lo; hit = hi - 1;
182 private int lower(int lo, int hi, int val) {
185 final int half = len >>> 1,
187 if (compare(mid, val) < 0) {
197 private int upper(int lo, int hi, int val) {
200 final int half = len >>> 1,
202 if (compare(val, mid) < 0) {