← Back to branch summary

~slub.team/goobi-indexserver/3.x

« back to all changes in this revision

Viewing changes to lucene/src/java/org/apache/lucene/util/SorterTemplate.java

  • Committer: Sebastian Meyer
  • Date: 2012-08-03 09:12:40 UTC
  • Revision ID: sebastian.meyer@slub-dresden.de-20120803091240-x6861b0vabq1xror
https://launchpad.net/bugs/985487
Remove Lucene and Solr source code and add patches instead
Fix Bug #985487: Auto-suggestion for the search interface

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
 
}