jaroslav@559
|
1 |
/*
|
jaroslav@559
|
2 |
* Copyright 2009 Google Inc. All Rights Reserved.
|
jaroslav@559
|
3 |
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
|
jaroslav@559
|
4 |
*
|
jaroslav@559
|
5 |
* This code is free software; you can redistribute it and/or modify it
|
jaroslav@559
|
6 |
* under the terms of the GNU General Public License version 2 only, as
|
jaroslav@559
|
7 |
* published by the Free Software Foundation. Oracle designates this
|
jaroslav@559
|
8 |
* particular file as subject to the "Classpath" exception as provided
|
jaroslav@559
|
9 |
* by Oracle in the LICENSE file that accompanied this code.
|
jaroslav@559
|
10 |
*
|
jaroslav@559
|
11 |
* This code is distributed in the hope that it will be useful, but WITHOUT
|
jaroslav@559
|
12 |
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
jaroslav@559
|
13 |
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
jaroslav@559
|
14 |
* version 2 for more details (a copy is included in the LICENSE file that
|
jaroslav@559
|
15 |
* accompanied this code).
|
jaroslav@559
|
16 |
*
|
jaroslav@559
|
17 |
* You should have received a copy of the GNU General Public License version
|
jaroslav@559
|
18 |
* 2 along with this work; if not, write to the Free Software Foundation,
|
jaroslav@559
|
19 |
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
|
jaroslav@559
|
20 |
*
|
jaroslav@559
|
21 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
|
jaroslav@559
|
22 |
* or visit www.oracle.com if you need additional information or have any
|
jaroslav@559
|
23 |
* questions.
|
jaroslav@559
|
24 |
*/
|
jaroslav@559
|
25 |
|
jaroslav@559
|
26 |
package java.util;
|
jaroslav@559
|
27 |
|
jaroslav@568
|
28 |
|
jaroslav@559
|
29 |
/**
|
jaroslav@559
|
30 |
* A stable, adaptive, iterative mergesort that requires far fewer than
|
jaroslav@559
|
31 |
* n lg(n) comparisons when running on partially sorted arrays, while
|
jaroslav@559
|
32 |
* offering performance comparable to a traditional mergesort when run
|
jaroslav@559
|
33 |
* on random arrays. Like all proper mergesorts, this sort is stable and
|
jaroslav@559
|
34 |
* runs O(n log n) time (worst case). In the worst case, this sort requires
|
jaroslav@559
|
35 |
* temporary storage space for n/2 object references; in the best case,
|
jaroslav@559
|
36 |
* it requires only a small constant amount of space.
|
jaroslav@559
|
37 |
*
|
jaroslav@559
|
38 |
* This implementation was adapted from Tim Peters's list sort for
|
jaroslav@559
|
39 |
* Python, which is described in detail here:
|
jaroslav@559
|
40 |
*
|
jaroslav@559
|
41 |
* http://svn.python.org/projects/python/trunk/Objects/listsort.txt
|
jaroslav@559
|
42 |
*
|
jaroslav@559
|
43 |
* Tim's C code may be found here:
|
jaroslav@559
|
44 |
*
|
jaroslav@559
|
45 |
* http://svn.python.org/projects/python/trunk/Objects/listobject.c
|
jaroslav@559
|
46 |
*
|
jaroslav@559
|
47 |
* The underlying techniques are described in this paper (and may have
|
jaroslav@559
|
48 |
* even earlier origins):
|
jaroslav@559
|
49 |
*
|
jaroslav@559
|
50 |
* "Optimistic Sorting and Information Theoretic Complexity"
|
jaroslav@559
|
51 |
* Peter McIlroy
|
jaroslav@559
|
52 |
* SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms),
|
jaroslav@559
|
53 |
* pp 467-474, Austin, Texas, 25-27 January 1993.
|
jaroslav@559
|
54 |
*
|
jaroslav@559
|
55 |
* While the API to this class consists solely of static methods, it is
|
jaroslav@559
|
56 |
* (privately) instantiable; a TimSort instance holds the state of an ongoing
|
jaroslav@559
|
57 |
* sort, assuming the input array is large enough to warrant the full-blown
|
jaroslav@559
|
58 |
* TimSort. Small arrays are sorted in place, using a binary insertion sort.
|
jaroslav@559
|
59 |
*
|
jaroslav@559
|
60 |
* @author Josh Bloch
|
jaroslav@559
|
61 |
*/
|
jaroslav@559
|
62 |
class TimSort<T> {
|
jaroslav@559
|
63 |
/**
|
jaroslav@559
|
64 |
* This is the minimum sized sequence that will be merged. Shorter
|
jaroslav@559
|
65 |
* sequences will be lengthened by calling binarySort. If the entire
|
jaroslav@559
|
66 |
* array is less than this length, no merges will be performed.
|
jaroslav@559
|
67 |
*
|
jaroslav@559
|
68 |
* This constant should be a power of two. It was 64 in Tim Peter's C
|
jaroslav@559
|
69 |
* implementation, but 32 was empirically determined to work better in
|
jaroslav@559
|
70 |
* this implementation. In the unlikely event that you set this constant
|
jaroslav@559
|
71 |
* to be a number that's not a power of two, you'll need to change the
|
jaroslav@559
|
72 |
* {@link #minRunLength} computation.
|
jaroslav@559
|
73 |
*
|
jaroslav@559
|
74 |
* If you decrease this constant, you must change the stackLen
|
jaroslav@559
|
75 |
* computation in the TimSort constructor, or you risk an
|
jaroslav@559
|
76 |
* ArrayOutOfBounds exception. See listsort.txt for a discussion
|
jaroslav@559
|
77 |
* of the minimum stack length required as a function of the length
|
jaroslav@559
|
78 |
* of the array being sorted and the minimum merge sequence length.
|
jaroslav@559
|
79 |
*/
|
jaroslav@559
|
80 |
private static final int MIN_MERGE = 32;
|
jaroslav@559
|
81 |
|
jaroslav@559
|
82 |
/**
|
jaroslav@559
|
83 |
* The array being sorted.
|
jaroslav@559
|
84 |
*/
|
jaroslav@559
|
85 |
private final T[] a;
|
jaroslav@559
|
86 |
|
jaroslav@559
|
87 |
/**
|
jaroslav@559
|
88 |
* The comparator for this sort.
|
jaroslav@559
|
89 |
*/
|
jaroslav@559
|
90 |
private final Comparator<? super T> c;
|
jaroslav@559
|
91 |
|
jaroslav@559
|
92 |
/**
|
jaroslav@559
|
93 |
* When we get into galloping mode, we stay there until both runs win less
|
jaroslav@559
|
94 |
* often than MIN_GALLOP consecutive times.
|
jaroslav@559
|
95 |
*/
|
jaroslav@559
|
96 |
private static final int MIN_GALLOP = 7;
|
jaroslav@559
|
97 |
|
jaroslav@559
|
98 |
/**
|
jaroslav@559
|
99 |
* This controls when we get *into* galloping mode. It is initialized
|
jaroslav@559
|
100 |
* to MIN_GALLOP. The mergeLo and mergeHi methods nudge it higher for
|
jaroslav@559
|
101 |
* random data, and lower for highly structured data.
|
jaroslav@559
|
102 |
*/
|
jaroslav@559
|
103 |
private int minGallop = MIN_GALLOP;
|
jaroslav@559
|
104 |
|
jaroslav@559
|
105 |
/**
|
jaroslav@559
|
106 |
* Maximum initial size of tmp array, which is used for merging. The array
|
jaroslav@559
|
107 |
* can grow to accommodate demand.
|
jaroslav@559
|
108 |
*
|
jaroslav@559
|
109 |
* Unlike Tim's original C version, we do not allocate this much storage
|
jaroslav@559
|
110 |
* when sorting smaller arrays. This change was required for performance.
|
jaroslav@559
|
111 |
*/
|
jaroslav@559
|
112 |
private static final int INITIAL_TMP_STORAGE_LENGTH = 256;
|
jaroslav@559
|
113 |
|
jaroslav@559
|
114 |
/**
|
jaroslav@559
|
115 |
* Temp storage for merges.
|
jaroslav@559
|
116 |
*/
|
jaroslav@559
|
117 |
private T[] tmp; // Actual runtime type will be Object[], regardless of T
|
jaroslav@559
|
118 |
|
jaroslav@559
|
119 |
/**
|
jaroslav@559
|
120 |
* A stack of pending runs yet to be merged. Run i starts at
|
jaroslav@559
|
121 |
* address base[i] and extends for len[i] elements. It's always
|
jaroslav@559
|
122 |
* true (so long as the indices are in bounds) that:
|
jaroslav@559
|
123 |
*
|
jaroslav@559
|
124 |
* runBase[i] + runLen[i] == runBase[i + 1]
|
jaroslav@559
|
125 |
*
|
jaroslav@559
|
126 |
* so we could cut the storage for this, but it's a minor amount,
|
jaroslav@559
|
127 |
* and keeping all the info explicit simplifies the code.
|
jaroslav@559
|
128 |
*/
|
jaroslav@559
|
129 |
private int stackSize = 0; // Number of pending runs on stack
|
jaroslav@559
|
130 |
private final int[] runBase;
|
jaroslav@559
|
131 |
private final int[] runLen;
|
jaroslav@559
|
132 |
|
jaroslav@559
|
133 |
/**
|
jaroslav@559
|
134 |
* Creates a TimSort instance to maintain the state of an ongoing sort.
|
jaroslav@559
|
135 |
*
|
jaroslav@559
|
136 |
* @param a the array to be sorted
|
jaroslav@559
|
137 |
* @param c the comparator to determine the order of the sort
|
jaroslav@559
|
138 |
*/
|
jaroslav@559
|
139 |
private TimSort(T[] a, Comparator<? super T> c) {
|
jaroslav@559
|
140 |
this.a = a;
|
jaroslav@559
|
141 |
this.c = c;
|
jaroslav@559
|
142 |
|
jaroslav@559
|
143 |
// Allocate temp storage (which may be increased later if necessary)
|
jaroslav@559
|
144 |
int len = a.length;
|
jaroslav@559
|
145 |
@SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
|
jaroslav@559
|
146 |
T[] newArray = (T[]) new Object[len < 2 * INITIAL_TMP_STORAGE_LENGTH ?
|
jaroslav@559
|
147 |
len >>> 1 : INITIAL_TMP_STORAGE_LENGTH];
|
jaroslav@559
|
148 |
tmp = newArray;
|
jaroslav@559
|
149 |
|
jaroslav@559
|
150 |
/*
|
jaroslav@559
|
151 |
* Allocate runs-to-be-merged stack (which cannot be expanded). The
|
jaroslav@559
|
152 |
* stack length requirements are described in listsort.txt. The C
|
jaroslav@559
|
153 |
* version always uses the same stack length (85), but this was
|
jaroslav@559
|
154 |
* measured to be too expensive when sorting "mid-sized" arrays (e.g.,
|
jaroslav@559
|
155 |
* 100 elements) in Java. Therefore, we use smaller (but sufficiently
|
jaroslav@559
|
156 |
* large) stack lengths for smaller arrays. The "magic numbers" in the
|
jaroslav@559
|
157 |
* computation below must be changed if MIN_MERGE is decreased. See
|
jaroslav@559
|
158 |
* the MIN_MERGE declaration above for more information.
|
jaroslav@559
|
159 |
*/
|
jaroslav@559
|
160 |
int stackLen = (len < 120 ? 5 :
|
jaroslav@559
|
161 |
len < 1542 ? 10 :
|
jaroslav@559
|
162 |
len < 119151 ? 19 : 40);
|
jaroslav@559
|
163 |
runBase = new int[stackLen];
|
jaroslav@559
|
164 |
runLen = new int[stackLen];
|
jaroslav@559
|
165 |
}
|
jaroslav@559
|
166 |
|
jaroslav@559
|
167 |
/*
|
jaroslav@559
|
168 |
* The next two methods (which are package private and static) constitute
|
jaroslav@559
|
169 |
* the entire API of this class. Each of these methods obeys the contract
|
jaroslav@559
|
170 |
* of the public method with the same signature in java.util.Arrays.
|
jaroslav@559
|
171 |
*/
|
jaroslav@559
|
172 |
|
jaroslav@559
|
173 |
static <T> void sort(T[] a, Comparator<? super T> c) {
|
jaroslav@559
|
174 |
sort(a, 0, a.length, c);
|
jaroslav@559
|
175 |
}
|
jaroslav@559
|
176 |
|
jaroslav@559
|
177 |
static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c) {
|
jaroslav@559
|
178 |
if (c == null) {
|
jaroslav@559
|
179 |
Arrays.sort(a, lo, hi);
|
jaroslav@559
|
180 |
return;
|
jaroslav@559
|
181 |
}
|
jaroslav@559
|
182 |
|
jaroslav@559
|
183 |
rangeCheck(a.length, lo, hi);
|
jaroslav@559
|
184 |
int nRemaining = hi - lo;
|
jaroslav@559
|
185 |
if (nRemaining < 2)
|
jaroslav@559
|
186 |
return; // Arrays of size 0 and 1 are always sorted
|
jaroslav@559
|
187 |
|
jaroslav@559
|
188 |
// If array is small, do a "mini-TimSort" with no merges
|
jaroslav@559
|
189 |
if (nRemaining < MIN_MERGE) {
|
jaroslav@559
|
190 |
int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
|
jaroslav@559
|
191 |
binarySort(a, lo, hi, lo + initRunLen, c);
|
jaroslav@559
|
192 |
return;
|
jaroslav@559
|
193 |
}
|
jaroslav@559
|
194 |
|
jaroslav@559
|
195 |
/**
|
jaroslav@559
|
196 |
* March over the array once, left to right, finding natural runs,
|
jaroslav@559
|
197 |
* extending short natural runs to minRun elements, and merging runs
|
jaroslav@559
|
198 |
* to maintain stack invariant.
|
jaroslav@559
|
199 |
*/
|
jaroslav@559
|
200 |
TimSort<T> ts = new TimSort<>(a, c);
|
jaroslav@559
|
201 |
int minRun = minRunLength(nRemaining);
|
jaroslav@559
|
202 |
do {
|
jaroslav@559
|
203 |
// Identify next run
|
jaroslav@559
|
204 |
int runLen = countRunAndMakeAscending(a, lo, hi, c);
|
jaroslav@559
|
205 |
|
jaroslav@559
|
206 |
// If run is short, extend to min(minRun, nRemaining)
|
jaroslav@559
|
207 |
if (runLen < minRun) {
|
jaroslav@559
|
208 |
int force = nRemaining <= minRun ? nRemaining : minRun;
|
jaroslav@559
|
209 |
binarySort(a, lo, lo + force, lo + runLen, c);
|
jaroslav@559
|
210 |
runLen = force;
|
jaroslav@559
|
211 |
}
|
jaroslav@559
|
212 |
|
jaroslav@559
|
213 |
// Push run onto pending-run stack, and maybe merge
|
jaroslav@559
|
214 |
ts.pushRun(lo, runLen);
|
jaroslav@559
|
215 |
ts.mergeCollapse();
|
jaroslav@559
|
216 |
|
jaroslav@559
|
217 |
// Advance to find next run
|
jaroslav@559
|
218 |
lo += runLen;
|
jaroslav@559
|
219 |
nRemaining -= runLen;
|
jaroslav@559
|
220 |
} while (nRemaining != 0);
|
jaroslav@559
|
221 |
|
jaroslav@559
|
222 |
// Merge all remaining runs to complete sort
|
jaroslav@559
|
223 |
assert lo == hi;
|
jaroslav@559
|
224 |
ts.mergeForceCollapse();
|
jaroslav@559
|
225 |
assert ts.stackSize == 1;
|
jaroslav@559
|
226 |
}
|
jaroslav@559
|
227 |
|
jaroslav@559
|
228 |
/**
|
jaroslav@559
|
229 |
* Sorts the specified portion of the specified array using a binary
|
jaroslav@559
|
230 |
* insertion sort. This is the best method for sorting small numbers
|
jaroslav@559
|
231 |
* of elements. It requires O(n log n) compares, but O(n^2) data
|
jaroslav@559
|
232 |
* movement (worst case).
|
jaroslav@559
|
233 |
*
|
jaroslav@559
|
234 |
* If the initial part of the specified range is already sorted,
|
jaroslav@559
|
235 |
* this method can take advantage of it: the method assumes that the
|
jaroslav@559
|
236 |
* elements from index {@code lo}, inclusive, to {@code start},
|
jaroslav@559
|
237 |
* exclusive are already sorted.
|
jaroslav@559
|
238 |
*
|
jaroslav@559
|
239 |
* @param a the array in which a range is to be sorted
|
jaroslav@559
|
240 |
* @param lo the index of the first element in the range to be sorted
|
jaroslav@559
|
241 |
* @param hi the index after the last element in the range to be sorted
|
jaroslav@559
|
242 |
* @param start the index of the first element in the range that is
|
jaroslav@559
|
243 |
* not already known to be sorted ({@code lo <= start <= hi})
|
jaroslav@559
|
244 |
* @param c comparator to used for the sort
|
jaroslav@559
|
245 |
*/
|
jaroslav@559
|
246 |
@SuppressWarnings("fallthrough")
|
jaroslav@559
|
247 |
private static <T> void binarySort(T[] a, int lo, int hi, int start,
|
jaroslav@559
|
248 |
Comparator<? super T> c) {
|
jaroslav@559
|
249 |
assert lo <= start && start <= hi;
|
jaroslav@559
|
250 |
if (start == lo)
|
jaroslav@559
|
251 |
start++;
|
jaroslav@559
|
252 |
for ( ; start < hi; start++) {
|
jaroslav@559
|
253 |
T pivot = a[start];
|
jaroslav@559
|
254 |
|
jaroslav@559
|
255 |
// Set left (and right) to the index where a[start] (pivot) belongs
|
jaroslav@559
|
256 |
int left = lo;
|
jaroslav@559
|
257 |
int right = start;
|
jaroslav@559
|
258 |
assert left <= right;
|
jaroslav@559
|
259 |
/*
|
jaroslav@559
|
260 |
* Invariants:
|
jaroslav@559
|
261 |
* pivot >= all in [lo, left).
|
jaroslav@559
|
262 |
* pivot < all in [right, start).
|
jaroslav@559
|
263 |
*/
|
jaroslav@559
|
264 |
while (left < right) {
|
jaroslav@559
|
265 |
int mid = (left + right) >>> 1;
|
jaroslav@559
|
266 |
if (c.compare(pivot, a[mid]) < 0)
|
jaroslav@559
|
267 |
right = mid;
|
jaroslav@559
|
268 |
else
|
jaroslav@559
|
269 |
left = mid + 1;
|
jaroslav@559
|
270 |
}
|
jaroslav@559
|
271 |
assert left == right;
|
jaroslav@559
|
272 |
|
jaroslav@559
|
273 |
/*
|
jaroslav@559
|
274 |
* The invariants still hold: pivot >= all in [lo, left) and
|
jaroslav@559
|
275 |
* pivot < all in [left, start), so pivot belongs at left. Note
|
jaroslav@559
|
276 |
* that if there are elements equal to pivot, left points to the
|
jaroslav@559
|
277 |
* first slot after them -- that's why this sort is stable.
|
jaroslav@559
|
278 |
* Slide elements over to make room for pivot.
|
jaroslav@559
|
279 |
*/
|
jaroslav@559
|
280 |
int n = start - left; // The number of elements to move
|
jaroslav@559
|
281 |
// Switch is just an optimization for arraycopy in default case
|
jaroslav@559
|
282 |
switch (n) {
|
jaroslav@559
|
283 |
case 2: a[left + 2] = a[left + 1];
|
jaroslav@559
|
284 |
case 1: a[left + 1] = a[left];
|
jaroslav@559
|
285 |
break;
|
jaroslav@559
|
286 |
default: System.arraycopy(a, left, a, left + 1, n);
|
jaroslav@559
|
287 |
}
|
jaroslav@559
|
288 |
a[left] = pivot;
|
jaroslav@559
|
289 |
}
|
jaroslav@559
|
290 |
}
|
jaroslav@559
|
291 |
|
jaroslav@559
|
292 |
/**
|
jaroslav@559
|
293 |
* Returns the length of the run beginning at the specified position in
|
jaroslav@559
|
294 |
* the specified array and reverses the run if it is descending (ensuring
|
jaroslav@559
|
295 |
* that the run will always be ascending when the method returns).
|
jaroslav@559
|
296 |
*
|
jaroslav@559
|
297 |
* A run is the longest ascending sequence with:
|
jaroslav@559
|
298 |
*
|
jaroslav@559
|
299 |
* a[lo] <= a[lo + 1] <= a[lo + 2] <= ...
|
jaroslav@559
|
300 |
*
|
jaroslav@559
|
301 |
* or the longest descending sequence with:
|
jaroslav@559
|
302 |
*
|
jaroslav@559
|
303 |
* a[lo] > a[lo + 1] > a[lo + 2] > ...
|
jaroslav@559
|
304 |
*
|
jaroslav@559
|
305 |
* For its intended use in a stable mergesort, the strictness of the
|
jaroslav@559
|
306 |
* definition of "descending" is needed so that the call can safely
|
jaroslav@559
|
307 |
* reverse a descending sequence without violating stability.
|
jaroslav@559
|
308 |
*
|
jaroslav@559
|
309 |
* @param a the array in which a run is to be counted and possibly reversed
|
jaroslav@559
|
310 |
* @param lo index of the first element in the run
|
jaroslav@559
|
311 |
* @param hi index after the last element that may be contained in the run.
|
jaroslav@559
|
312 |
It is required that {@code lo < hi}.
|
jaroslav@559
|
313 |
* @param c the comparator to used for the sort
|
jaroslav@559
|
314 |
* @return the length of the run beginning at the specified position in
|
jaroslav@559
|
315 |
* the specified array
|
jaroslav@559
|
316 |
*/
|
jaroslav@559
|
317 |
private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
|
jaroslav@559
|
318 |
Comparator<? super T> c) {
|
jaroslav@559
|
319 |
assert lo < hi;
|
jaroslav@559
|
320 |
int runHi = lo + 1;
|
jaroslav@559
|
321 |
if (runHi == hi)
|
jaroslav@559
|
322 |
return 1;
|
jaroslav@559
|
323 |
|
jaroslav@559
|
324 |
// Find end of run, and reverse range if descending
|
jaroslav@559
|
325 |
if (c.compare(a[runHi++], a[lo]) < 0) { // Descending
|
jaroslav@559
|
326 |
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)
|
jaroslav@559
|
327 |
runHi++;
|
jaroslav@559
|
328 |
reverseRange(a, lo, runHi);
|
jaroslav@559
|
329 |
} else { // Ascending
|
jaroslav@559
|
330 |
while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0)
|
jaroslav@559
|
331 |
runHi++;
|
jaroslav@559
|
332 |
}
|
jaroslav@559
|
333 |
|
jaroslav@559
|
334 |
return runHi - lo;
|
jaroslav@559
|
335 |
}
|
jaroslav@559
|
336 |
|
jaroslav@559
|
337 |
/**
|
jaroslav@559
|
338 |
* Reverse the specified range of the specified array.
|
jaroslav@559
|
339 |
*
|
jaroslav@559
|
340 |
* @param a the array in which a range is to be reversed
|
jaroslav@559
|
341 |
* @param lo the index of the first element in the range to be reversed
|
jaroslav@559
|
342 |
* @param hi the index after the last element in the range to be reversed
|
jaroslav@559
|
343 |
*/
|
jaroslav@559
|
344 |
private static void reverseRange(Object[] a, int lo, int hi) {
|
jaroslav@559
|
345 |
hi--;
|
jaroslav@559
|
346 |
while (lo < hi) {
|
jaroslav@559
|
347 |
Object t = a[lo];
|
jaroslav@559
|
348 |
a[lo++] = a[hi];
|
jaroslav@559
|
349 |
a[hi--] = t;
|
jaroslav@559
|
350 |
}
|
jaroslav@559
|
351 |
}
|
jaroslav@559
|
352 |
|
jaroslav@559
|
353 |
/**
|
jaroslav@559
|
354 |
* Returns the minimum acceptable run length for an array of the specified
|
jaroslav@559
|
355 |
* length. Natural runs shorter than this will be extended with
|
jaroslav@559
|
356 |
* {@link #binarySort}.
|
jaroslav@559
|
357 |
*
|
jaroslav@559
|
358 |
* Roughly speaking, the computation is:
|
jaroslav@559
|
359 |
*
|
jaroslav@559
|
360 |
* If n < MIN_MERGE, return n (it's too small to bother with fancy stuff).
|
jaroslav@559
|
361 |
* Else if n is an exact power of 2, return MIN_MERGE/2.
|
jaroslav@559
|
362 |
* Else return an int k, MIN_MERGE/2 <= k <= MIN_MERGE, such that n/k
|
jaroslav@559
|
363 |
* is close to, but strictly less than, an exact power of 2.
|
jaroslav@559
|
364 |
*
|
jaroslav@559
|
365 |
* For the rationale, see listsort.txt.
|
jaroslav@559
|
366 |
*
|
jaroslav@559
|
367 |
* @param n the length of the array to be sorted
|
jaroslav@559
|
368 |
* @return the length of the minimum run to be merged
|
jaroslav@559
|
369 |
*/
|
jaroslav@559
|
370 |
private static int minRunLength(int n) {
|
jaroslav@559
|
371 |
assert n >= 0;
|
jaroslav@559
|
372 |
int r = 0; // Becomes 1 if any 1 bits are shifted off
|
jaroslav@559
|
373 |
while (n >= MIN_MERGE) {
|
jaroslav@559
|
374 |
r |= (n & 1);
|
jaroslav@559
|
375 |
n >>= 1;
|
jaroslav@559
|
376 |
}
|
jaroslav@559
|
377 |
return n + r;
|
jaroslav@559
|
378 |
}
|
jaroslav@559
|
379 |
|
jaroslav@559
|
380 |
/**
|
jaroslav@559
|
381 |
* Pushes the specified run onto the pending-run stack.
|
jaroslav@559
|
382 |
*
|
jaroslav@559
|
383 |
* @param runBase index of the first element in the run
|
jaroslav@559
|
384 |
* @param runLen the number of elements in the run
|
jaroslav@559
|
385 |
*/
|
jaroslav@559
|
386 |
private void pushRun(int runBase, int runLen) {
|
jaroslav@559
|
387 |
this.runBase[stackSize] = runBase;
|
jaroslav@559
|
388 |
this.runLen[stackSize] = runLen;
|
jaroslav@559
|
389 |
stackSize++;
|
jaroslav@559
|
390 |
}
|
jaroslav@559
|
391 |
|
jaroslav@559
|
392 |
/**
|
jaroslav@559
|
393 |
* Examines the stack of runs waiting to be merged and merges adjacent runs
|
jaroslav@559
|
394 |
* until the stack invariants are reestablished:
|
jaroslav@559
|
395 |
*
|
jaroslav@559
|
396 |
* 1. runLen[i - 3] > runLen[i - 2] + runLen[i - 1]
|
jaroslav@559
|
397 |
* 2. runLen[i - 2] > runLen[i - 1]
|
jaroslav@559
|
398 |
*
|
jaroslav@559
|
399 |
* This method is called each time a new run is pushed onto the stack,
|
jaroslav@559
|
400 |
* so the invariants are guaranteed to hold for i < stackSize upon
|
jaroslav@559
|
401 |
* entry to the method.
|
jaroslav@559
|
402 |
*/
|
jaroslav@559
|
403 |
private void mergeCollapse() {
|
jaroslav@559
|
404 |
while (stackSize > 1) {
|
jaroslav@559
|
405 |
int n = stackSize - 2;
|
jaroslav@559
|
406 |
if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {
|
jaroslav@559
|
407 |
if (runLen[n - 1] < runLen[n + 1])
|
jaroslav@559
|
408 |
n--;
|
jaroslav@559
|
409 |
mergeAt(n);
|
jaroslav@559
|
410 |
} else if (runLen[n] <= runLen[n + 1]) {
|
jaroslav@559
|
411 |
mergeAt(n);
|
jaroslav@559
|
412 |
} else {
|
jaroslav@559
|
413 |
break; // Invariant is established
|
jaroslav@559
|
414 |
}
|
jaroslav@559
|
415 |
}
|
jaroslav@559
|
416 |
}
|
jaroslav@559
|
417 |
|
jaroslav@559
|
418 |
/**
|
jaroslav@559
|
419 |
* Merges all runs on the stack until only one remains. This method is
|
jaroslav@559
|
420 |
* called once, to complete the sort.
|
jaroslav@559
|
421 |
*/
|
jaroslav@559
|
422 |
private void mergeForceCollapse() {
|
jaroslav@559
|
423 |
while (stackSize > 1) {
|
jaroslav@559
|
424 |
int n = stackSize - 2;
|
jaroslav@559
|
425 |
if (n > 0 && runLen[n - 1] < runLen[n + 1])
|
jaroslav@559
|
426 |
n--;
|
jaroslav@559
|
427 |
mergeAt(n);
|
jaroslav@559
|
428 |
}
|
jaroslav@559
|
429 |
}
|
jaroslav@559
|
430 |
|
jaroslav@559
|
431 |
/**
|
jaroslav@559
|
432 |
* Merges the two runs at stack indices i and i+1. Run i must be
|
jaroslav@559
|
433 |
* the penultimate or antepenultimate run on the stack. In other words,
|
jaroslav@559
|
434 |
* i must be equal to stackSize-2 or stackSize-3.
|
jaroslav@559
|
435 |
*
|
jaroslav@559
|
436 |
* @param i stack index of the first of the two runs to merge
|
jaroslav@559
|
437 |
*/
|
jaroslav@559
|
438 |
private void mergeAt(int i) {
|
jaroslav@559
|
439 |
assert stackSize >= 2;
|
jaroslav@559
|
440 |
assert i >= 0;
|
jaroslav@559
|
441 |
assert i == stackSize - 2 || i == stackSize - 3;
|
jaroslav@559
|
442 |
|
jaroslav@559
|
443 |
int base1 = runBase[i];
|
jaroslav@559
|
444 |
int len1 = runLen[i];
|
jaroslav@559
|
445 |
int base2 = runBase[i + 1];
|
jaroslav@559
|
446 |
int len2 = runLen[i + 1];
|
jaroslav@559
|
447 |
assert len1 > 0 && len2 > 0;
|
jaroslav@559
|
448 |
assert base1 + len1 == base2;
|
jaroslav@559
|
449 |
|
jaroslav@559
|
450 |
/*
|
jaroslav@559
|
451 |
* Record the length of the combined runs; if i is the 3rd-last
|
jaroslav@559
|
452 |
* run now, also slide over the last run (which isn't involved
|
jaroslav@559
|
453 |
* in this merge). The current run (i+1) goes away in any case.
|
jaroslav@559
|
454 |
*/
|
jaroslav@559
|
455 |
runLen[i] = len1 + len2;
|
jaroslav@559
|
456 |
if (i == stackSize - 3) {
|
jaroslav@559
|
457 |
runBase[i + 1] = runBase[i + 2];
|
jaroslav@559
|
458 |
runLen[i + 1] = runLen[i + 2];
|
jaroslav@559
|
459 |
}
|
jaroslav@559
|
460 |
stackSize--;
|
jaroslav@559
|
461 |
|
jaroslav@559
|
462 |
/*
|
jaroslav@559
|
463 |
* Find where the first element of run2 goes in run1. Prior elements
|
jaroslav@559
|
464 |
* in run1 can be ignored (because they're already in place).
|
jaroslav@559
|
465 |
*/
|
jaroslav@559
|
466 |
int k = gallopRight(a[base2], a, base1, len1, 0, c);
|
jaroslav@559
|
467 |
assert k >= 0;
|
jaroslav@559
|
468 |
base1 += k;
|
jaroslav@559
|
469 |
len1 -= k;
|
jaroslav@559
|
470 |
if (len1 == 0)
|
jaroslav@559
|
471 |
return;
|
jaroslav@559
|
472 |
|
jaroslav@559
|
473 |
/*
|
jaroslav@559
|
474 |
* Find where the last element of run1 goes in run2. Subsequent elements
|
jaroslav@559
|
475 |
* in run2 can be ignored (because they're already in place).
|
jaroslav@559
|
476 |
*/
|
jaroslav@559
|
477 |
len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c);
|
jaroslav@559
|
478 |
assert len2 >= 0;
|
jaroslav@559
|
479 |
if (len2 == 0)
|
jaroslav@559
|
480 |
return;
|
jaroslav@559
|
481 |
|
jaroslav@559
|
482 |
// Merge remaining runs, using tmp array with min(len1, len2) elements
|
jaroslav@559
|
483 |
if (len1 <= len2)
|
jaroslav@559
|
484 |
mergeLo(base1, len1, base2, len2);
|
jaroslav@559
|
485 |
else
|
jaroslav@559
|
486 |
mergeHi(base1, len1, base2, len2);
|
jaroslav@559
|
487 |
}
|
jaroslav@559
|
488 |
|
jaroslav@559
|
489 |
/**
|
jaroslav@559
|
490 |
* Locates the position at which to insert the specified key into the
|
jaroslav@559
|
491 |
* specified sorted range; if the range contains an element equal to key,
|
jaroslav@559
|
492 |
* returns the index of the leftmost equal element.
|
jaroslav@559
|
493 |
*
|
jaroslav@559
|
494 |
* @param key the key whose insertion point to search for
|
jaroslav@559
|
495 |
* @param a the array in which to search
|
jaroslav@559
|
496 |
* @param base the index of the first element in the range
|
jaroslav@559
|
497 |
* @param len the length of the range; must be > 0
|
jaroslav@559
|
498 |
* @param hint the index at which to begin the search, 0 <= hint < n.
|
jaroslav@559
|
499 |
* The closer hint is to the result, the faster this method will run.
|
jaroslav@559
|
500 |
* @param c the comparator used to order the range, and to search
|
jaroslav@559
|
501 |
* @return the int k, 0 <= k <= n such that a[b + k - 1] < key <= a[b + k],
|
jaroslav@559
|
502 |
* pretending that a[b - 1] is minus infinity and a[b + n] is infinity.
|
jaroslav@559
|
503 |
* In other words, key belongs at index b + k; or in other words,
|
jaroslav@559
|
504 |
* the first k elements of a should precede key, and the last n - k
|
jaroslav@559
|
505 |
* should follow it.
|
jaroslav@559
|
506 |
*/
|
jaroslav@559
|
507 |
private static <T> int gallopLeft(T key, T[] a, int base, int len, int hint,
|
jaroslav@559
|
508 |
Comparator<? super T> c) {
|
jaroslav@559
|
509 |
assert len > 0 && hint >= 0 && hint < len;
|
jaroslav@559
|
510 |
int lastOfs = 0;
|
jaroslav@559
|
511 |
int ofs = 1;
|
jaroslav@559
|
512 |
if (c.compare(key, a[base + hint]) > 0) {
|
jaroslav@559
|
513 |
// Gallop right until a[base+hint+lastOfs] < key <= a[base+hint+ofs]
|
jaroslav@559
|
514 |
int maxOfs = len - hint;
|
jaroslav@559
|
515 |
while (ofs < maxOfs && c.compare(key, a[base + hint + ofs]) > 0) {
|
jaroslav@559
|
516 |
lastOfs = ofs;
|
jaroslav@559
|
517 |
ofs = (ofs << 1) + 1;
|
jaroslav@559
|
518 |
if (ofs <= 0) // int overflow
|
jaroslav@559
|
519 |
ofs = maxOfs;
|
jaroslav@559
|
520 |
}
|
jaroslav@559
|
521 |
if (ofs > maxOfs)
|
jaroslav@559
|
522 |
ofs = maxOfs;
|
jaroslav@559
|
523 |
|
jaroslav@559
|
524 |
// Make offsets relative to base
|
jaroslav@559
|
525 |
lastOfs += hint;
|
jaroslav@559
|
526 |
ofs += hint;
|
jaroslav@559
|
527 |
} else { // key <= a[base + hint]
|
jaroslav@559
|
528 |
// Gallop left until a[base+hint-ofs] < key <= a[base+hint-lastOfs]
|
jaroslav@559
|
529 |
final int maxOfs = hint + 1;
|
jaroslav@559
|
530 |
while (ofs < maxOfs && c.compare(key, a[base + hint - ofs]) <= 0) {
|
jaroslav@559
|
531 |
lastOfs = ofs;
|
jaroslav@559
|
532 |
ofs = (ofs << 1) + 1;
|
jaroslav@559
|
533 |
if (ofs <= 0) // int overflow
|
jaroslav@559
|
534 |
ofs = maxOfs;
|
jaroslav@559
|
535 |
}
|
jaroslav@559
|
536 |
if (ofs > maxOfs)
|
jaroslav@559
|
537 |
ofs = maxOfs;
|
jaroslav@559
|
538 |
|
jaroslav@559
|
539 |
// Make offsets relative to base
|
jaroslav@559
|
540 |
int tmp = lastOfs;
|
jaroslav@559
|
541 |
lastOfs = hint - ofs;
|
jaroslav@559
|
542 |
ofs = hint - tmp;
|
jaroslav@559
|
543 |
}
|
jaroslav@559
|
544 |
assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;
|
jaroslav@559
|
545 |
|
jaroslav@559
|
546 |
/*
|
jaroslav@559
|
547 |
* Now a[base+lastOfs] < key <= a[base+ofs], so key belongs somewhere
|
jaroslav@559
|
548 |
* to the right of lastOfs but no farther right than ofs. Do a binary
|
jaroslav@559
|
549 |
* search, with invariant a[base + lastOfs - 1] < key <= a[base + ofs].
|
jaroslav@559
|
550 |
*/
|
jaroslav@559
|
551 |
lastOfs++;
|
jaroslav@559
|
552 |
while (lastOfs < ofs) {
|
jaroslav@559
|
553 |
int m = lastOfs + ((ofs - lastOfs) >>> 1);
|
jaroslav@559
|
554 |
|
jaroslav@559
|
555 |
if (c.compare(key, a[base + m]) > 0)
|
jaroslav@559
|
556 |
lastOfs = m + 1; // a[base + m] < key
|
jaroslav@559
|
557 |
else
|
jaroslav@559
|
558 |
ofs = m; // key <= a[base + m]
|
jaroslav@559
|
559 |
}
|
jaroslav@559
|
560 |
assert lastOfs == ofs; // so a[base + ofs - 1] < key <= a[base + ofs]
|
jaroslav@559
|
561 |
return ofs;
|
jaroslav@559
|
562 |
}
|
jaroslav@559
|
563 |
|
jaroslav@559
|
564 |
/**
|
jaroslav@559
|
565 |
* Like gallopLeft, except that if the range contains an element equal to
|
jaroslav@559
|
566 |
* key, gallopRight returns the index after the rightmost equal element.
|
jaroslav@559
|
567 |
*
|
jaroslav@559
|
568 |
* @param key the key whose insertion point to search for
|
jaroslav@559
|
569 |
* @param a the array in which to search
|
jaroslav@559
|
570 |
* @param base the index of the first element in the range
|
jaroslav@559
|
571 |
* @param len the length of the range; must be > 0
|
jaroslav@559
|
572 |
* @param hint the index at which to begin the search, 0 <= hint < n.
|
jaroslav@559
|
573 |
* The closer hint is to the result, the faster this method will run.
|
jaroslav@559
|
574 |
* @param c the comparator used to order the range, and to search
|
jaroslav@559
|
575 |
* @return the int k, 0 <= k <= n such that a[b + k - 1] <= key < a[b + k]
|
jaroslav@559
|
576 |
*/
|
jaroslav@559
|
577 |
private static <T> int gallopRight(T key, T[] a, int base, int len,
|
jaroslav@559
|
578 |
int hint, Comparator<? super T> c) {
|
jaroslav@559
|
579 |
assert len > 0 && hint >= 0 && hint < len;
|
jaroslav@559
|
580 |
|
jaroslav@559
|
581 |
int ofs = 1;
|
jaroslav@559
|
582 |
int lastOfs = 0;
|
jaroslav@559
|
583 |
if (c.compare(key, a[base + hint]) < 0) {
|
jaroslav@559
|
584 |
// Gallop left until a[b+hint - ofs] <= key < a[b+hint - lastOfs]
|
jaroslav@559
|
585 |
int maxOfs = hint + 1;
|
jaroslav@559
|
586 |
while (ofs < maxOfs && c.compare(key, a[base + hint - ofs]) < 0) {
|
jaroslav@559
|
587 |
lastOfs = ofs;
|
jaroslav@559
|
588 |
ofs = (ofs << 1) + 1;
|
jaroslav@559
|
589 |
if (ofs <= 0) // int overflow
|
jaroslav@559
|
590 |
ofs = maxOfs;
|
jaroslav@559
|
591 |
}
|
jaroslav@559
|
592 |
if (ofs > maxOfs)
|
jaroslav@559
|
593 |
ofs = maxOfs;
|
jaroslav@559
|
594 |
|
jaroslav@559
|
595 |
// Make offsets relative to b
|
jaroslav@559
|
596 |
int tmp = lastOfs;
|
jaroslav@559
|
597 |
lastOfs = hint - ofs;
|
jaroslav@559
|
598 |
ofs = hint - tmp;
|
jaroslav@559
|
599 |
} else { // a[b + hint] <= key
|
jaroslav@559
|
600 |
// Gallop right until a[b+hint + lastOfs] <= key < a[b+hint + ofs]
|
jaroslav@559
|
601 |
int maxOfs = len - hint;
|
jaroslav@559
|
602 |
while (ofs < maxOfs && c.compare(key, a[base + hint + ofs]) >= 0) {
|
jaroslav@559
|
603 |
lastOfs = ofs;
|
jaroslav@559
|
604 |
ofs = (ofs << 1) + 1;
|
jaroslav@559
|
605 |
if (ofs <= 0) // int overflow
|
jaroslav@559
|
606 |
ofs = maxOfs;
|
jaroslav@559
|
607 |
}
|
jaroslav@559
|
608 |
if (ofs > maxOfs)
|
jaroslav@559
|
609 |
ofs = maxOfs;
|
jaroslav@559
|
610 |
|
jaroslav@559
|
611 |
// Make offsets relative to b
|
jaroslav@559
|
612 |
lastOfs += hint;
|
jaroslav@559
|
613 |
ofs += hint;
|
jaroslav@559
|
614 |
}
|
jaroslav@559
|
615 |
assert -1 <= lastOfs && lastOfs < ofs && ofs <= len;
|
jaroslav@559
|
616 |
|
jaroslav@559
|
617 |
/*
|
jaroslav@559
|
618 |
* Now a[b + lastOfs] <= key < a[b + ofs], so key belongs somewhere to
|
jaroslav@559
|
619 |
* the right of lastOfs but no farther right than ofs. Do a binary
|
jaroslav@559
|
620 |
* search, with invariant a[b + lastOfs - 1] <= key < a[b + ofs].
|
jaroslav@559
|
621 |
*/
|
jaroslav@559
|
622 |
lastOfs++;
|
jaroslav@559
|
623 |
while (lastOfs < ofs) {
|
jaroslav@559
|
624 |
int m = lastOfs + ((ofs - lastOfs) >>> 1);
|
jaroslav@559
|
625 |
|
jaroslav@559
|
626 |
if (c.compare(key, a[base + m]) < 0)
|
jaroslav@559
|
627 |
ofs = m; // key < a[b + m]
|
jaroslav@559
|
628 |
else
|
jaroslav@559
|
629 |
lastOfs = m + 1; // a[b + m] <= key
|
jaroslav@559
|
630 |
}
|
jaroslav@559
|
631 |
assert lastOfs == ofs; // so a[b + ofs - 1] <= key < a[b + ofs]
|
jaroslav@559
|
632 |
return ofs;
|
jaroslav@559
|
633 |
}
|
jaroslav@559
|
634 |
|
jaroslav@559
|
635 |
/**
|
jaroslav@559
|
636 |
* Merges two adjacent runs in place, in a stable fashion. The first
|
jaroslav@559
|
637 |
* element of the first run must be greater than the first element of the
|
jaroslav@559
|
638 |
* second run (a[base1] > a[base2]), and the last element of the first run
|
jaroslav@559
|
639 |
* (a[base1 + len1-1]) must be greater than all elements of the second run.
|
jaroslav@559
|
640 |
*
|
jaroslav@559
|
641 |
* For performance, this method should be called only when len1 <= len2;
|
jaroslav@559
|
642 |
* its twin, mergeHi should be called if len1 >= len2. (Either method
|
jaroslav@559
|
643 |
* may be called if len1 == len2.)
|
jaroslav@559
|
644 |
*
|
jaroslav@559
|
645 |
* @param base1 index of first element in first run to be merged
|
jaroslav@559
|
646 |
* @param len1 length of first run to be merged (must be > 0)
|
jaroslav@559
|
647 |
* @param base2 index of first element in second run to be merged
|
jaroslav@559
|
648 |
* (must be aBase + aLen)
|
jaroslav@559
|
649 |
* @param len2 length of second run to be merged (must be > 0)
|
jaroslav@559
|
650 |
*/
|
jaroslav@559
|
651 |
private void mergeLo(int base1, int len1, int base2, int len2) {
|
jaroslav@559
|
652 |
assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
|
jaroslav@559
|
653 |
|
jaroslav@559
|
654 |
// Copy first run into temp array
|
jaroslav@559
|
655 |
T[] a = this.a; // For performance
|
jaroslav@559
|
656 |
T[] tmp = ensureCapacity(len1);
|
jaroslav@559
|
657 |
System.arraycopy(a, base1, tmp, 0, len1);
|
jaroslav@559
|
658 |
|
jaroslav@559
|
659 |
int cursor1 = 0; // Indexes into tmp array
|
jaroslav@559
|
660 |
int cursor2 = base2; // Indexes int a
|
jaroslav@559
|
661 |
int dest = base1; // Indexes int a
|
jaroslav@559
|
662 |
|
jaroslav@559
|
663 |
// Move first element of second run and deal with degenerate cases
|
jaroslav@559
|
664 |
a[dest++] = a[cursor2++];
|
jaroslav@559
|
665 |
if (--len2 == 0) {
|
jaroslav@559
|
666 |
System.arraycopy(tmp, cursor1, a, dest, len1);
|
jaroslav@559
|
667 |
return;
|
jaroslav@559
|
668 |
}
|
jaroslav@559
|
669 |
if (len1 == 1) {
|
jaroslav@559
|
670 |
System.arraycopy(a, cursor2, a, dest, len2);
|
jaroslav@559
|
671 |
a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
|
jaroslav@559
|
672 |
return;
|
jaroslav@559
|
673 |
}
|
jaroslav@559
|
674 |
|
jaroslav@559
|
675 |
Comparator<? super T> c = this.c; // Use local variable for performance
|
jaroslav@559
|
676 |
int minGallop = this.minGallop; // " " " " "
|
jaroslav@559
|
677 |
outer:
|
jaroslav@559
|
678 |
while (true) {
|
jaroslav@559
|
679 |
int count1 = 0; // Number of times in a row that first run won
|
jaroslav@559
|
680 |
int count2 = 0; // Number of times in a row that second run won
|
jaroslav@559
|
681 |
|
jaroslav@559
|
682 |
/*
|
jaroslav@559
|
683 |
* Do the straightforward thing until (if ever) one run starts
|
jaroslav@559
|
684 |
* winning consistently.
|
jaroslav@559
|
685 |
*/
|
jaroslav@559
|
686 |
do {
|
jaroslav@559
|
687 |
assert len1 > 1 && len2 > 0;
|
jaroslav@559
|
688 |
if (c.compare(a[cursor2], tmp[cursor1]) < 0) {
|
jaroslav@559
|
689 |
a[dest++] = a[cursor2++];
|
jaroslav@559
|
690 |
count2++;
|
jaroslav@559
|
691 |
count1 = 0;
|
jaroslav@559
|
692 |
if (--len2 == 0)
|
jaroslav@559
|
693 |
break outer;
|
jaroslav@559
|
694 |
} else {
|
jaroslav@559
|
695 |
a[dest++] = tmp[cursor1++];
|
jaroslav@559
|
696 |
count1++;
|
jaroslav@559
|
697 |
count2 = 0;
|
jaroslav@559
|
698 |
if (--len1 == 1)
|
jaroslav@559
|
699 |
break outer;
|
jaroslav@559
|
700 |
}
|
jaroslav@559
|
701 |
} while ((count1 | count2) < minGallop);
|
jaroslav@559
|
702 |
|
jaroslav@559
|
703 |
/*
|
jaroslav@559
|
704 |
* One run is winning so consistently that galloping may be a
|
jaroslav@559
|
705 |
* huge win. So try that, and continue galloping until (if ever)
|
jaroslav@559
|
706 |
* neither run appears to be winning consistently anymore.
|
jaroslav@559
|
707 |
*/
|
jaroslav@559
|
708 |
do {
|
jaroslav@559
|
709 |
assert len1 > 1 && len2 > 0;
|
jaroslav@559
|
710 |
count1 = gallopRight(a[cursor2], tmp, cursor1, len1, 0, c);
|
jaroslav@559
|
711 |
if (count1 != 0) {
|
jaroslav@559
|
712 |
System.arraycopy(tmp, cursor1, a, dest, count1);
|
jaroslav@559
|
713 |
dest += count1;
|
jaroslav@559
|
714 |
cursor1 += count1;
|
jaroslav@559
|
715 |
len1 -= count1;
|
jaroslav@559
|
716 |
if (len1 <= 1) // len1 == 1 || len1 == 0
|
jaroslav@559
|
717 |
break outer;
|
jaroslav@559
|
718 |
}
|
jaroslav@559
|
719 |
a[dest++] = a[cursor2++];
|
jaroslav@559
|
720 |
if (--len2 == 0)
|
jaroslav@559
|
721 |
break outer;
|
jaroslav@559
|
722 |
|
jaroslav@559
|
723 |
count2 = gallopLeft(tmp[cursor1], a, cursor2, len2, 0, c);
|
jaroslav@559
|
724 |
if (count2 != 0) {
|
jaroslav@559
|
725 |
System.arraycopy(a, cursor2, a, dest, count2);
|
jaroslav@559
|
726 |
dest += count2;
|
jaroslav@559
|
727 |
cursor2 += count2;
|
jaroslav@559
|
728 |
len2 -= count2;
|
jaroslav@559
|
729 |
if (len2 == 0)
|
jaroslav@559
|
730 |
break outer;
|
jaroslav@559
|
731 |
}
|
jaroslav@559
|
732 |
a[dest++] = tmp[cursor1++];
|
jaroslav@559
|
733 |
if (--len1 == 1)
|
jaroslav@559
|
734 |
break outer;
|
jaroslav@559
|
735 |
minGallop--;
|
jaroslav@559
|
736 |
} while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
|
jaroslav@559
|
737 |
if (minGallop < 0)
|
jaroslav@559
|
738 |
minGallop = 0;
|
jaroslav@559
|
739 |
minGallop += 2; // Penalize for leaving gallop mode
|
jaroslav@559
|
740 |
} // End of "outer" loop
|
jaroslav@559
|
741 |
this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field
|
jaroslav@559
|
742 |
|
jaroslav@559
|
743 |
if (len1 == 1) {
|
jaroslav@559
|
744 |
assert len2 > 0;
|
jaroslav@559
|
745 |
System.arraycopy(a, cursor2, a, dest, len2);
|
jaroslav@559
|
746 |
a[dest + len2] = tmp[cursor1]; // Last elt of run 1 to end of merge
|
jaroslav@559
|
747 |
} else if (len1 == 0) {
|
jaroslav@559
|
748 |
throw new IllegalArgumentException(
|
jaroslav@559
|
749 |
"Comparison method violates its general contract!");
|
jaroslav@559
|
750 |
} else {
|
jaroslav@559
|
751 |
assert len2 == 0;
|
jaroslav@559
|
752 |
assert len1 > 1;
|
jaroslav@559
|
753 |
System.arraycopy(tmp, cursor1, a, dest, len1);
|
jaroslav@559
|
754 |
}
|
jaroslav@559
|
755 |
}
|
jaroslav@559
|
756 |
|
jaroslav@559
|
757 |
/**
|
jaroslav@559
|
758 |
* Like mergeLo, except that this method should be called only if
|
jaroslav@559
|
759 |
* len1 >= len2; mergeLo should be called if len1 <= len2. (Either method
|
jaroslav@559
|
760 |
* may be called if len1 == len2.)
|
jaroslav@559
|
761 |
*
|
jaroslav@559
|
762 |
* @param base1 index of first element in first run to be merged
|
jaroslav@559
|
763 |
* @param len1 length of first run to be merged (must be > 0)
|
jaroslav@559
|
764 |
* @param base2 index of first element in second run to be merged
|
jaroslav@559
|
765 |
* (must be aBase + aLen)
|
jaroslav@559
|
766 |
* @param len2 length of second run to be merged (must be > 0)
|
jaroslav@559
|
767 |
*/
|
jaroslav@559
|
768 |
private void mergeHi(int base1, int len1, int base2, int len2) {
|
jaroslav@559
|
769 |
assert len1 > 0 && len2 > 0 && base1 + len1 == base2;
|
jaroslav@559
|
770 |
|
jaroslav@559
|
771 |
// Copy second run into temp array
|
jaroslav@559
|
772 |
T[] a = this.a; // For performance
|
jaroslav@559
|
773 |
T[] tmp = ensureCapacity(len2);
|
jaroslav@559
|
774 |
System.arraycopy(a, base2, tmp, 0, len2);
|
jaroslav@559
|
775 |
|
jaroslav@559
|
776 |
int cursor1 = base1 + len1 - 1; // Indexes into a
|
jaroslav@559
|
777 |
int cursor2 = len2 - 1; // Indexes into tmp array
|
jaroslav@559
|
778 |
int dest = base2 + len2 - 1; // Indexes into a
|
jaroslav@559
|
779 |
|
jaroslav@559
|
780 |
// Move last element of first run and deal with degenerate cases
|
jaroslav@559
|
781 |
a[dest--] = a[cursor1--];
|
jaroslav@559
|
782 |
if (--len1 == 0) {
|
jaroslav@559
|
783 |
System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2);
|
jaroslav@559
|
784 |
return;
|
jaroslav@559
|
785 |
}
|
jaroslav@559
|
786 |
if (len2 == 1) {
|
jaroslav@559
|
787 |
dest -= len1;
|
jaroslav@559
|
788 |
cursor1 -= len1;
|
jaroslav@559
|
789 |
System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
|
jaroslav@559
|
790 |
a[dest] = tmp[cursor2];
|
jaroslav@559
|
791 |
return;
|
jaroslav@559
|
792 |
}
|
jaroslav@559
|
793 |
|
jaroslav@559
|
794 |
Comparator<? super T> c = this.c; // Use local variable for performance
|
jaroslav@559
|
795 |
int minGallop = this.minGallop; // " " " " "
|
jaroslav@559
|
796 |
outer:
|
jaroslav@559
|
797 |
while (true) {
|
jaroslav@559
|
798 |
int count1 = 0; // Number of times in a row that first run won
|
jaroslav@559
|
799 |
int count2 = 0; // Number of times in a row that second run won
|
jaroslav@559
|
800 |
|
jaroslav@559
|
801 |
/*
|
jaroslav@559
|
802 |
* Do the straightforward thing until (if ever) one run
|
jaroslav@559
|
803 |
* appears to win consistently.
|
jaroslav@559
|
804 |
*/
|
jaroslav@559
|
805 |
do {
|
jaroslav@559
|
806 |
assert len1 > 0 && len2 > 1;
|
jaroslav@559
|
807 |
if (c.compare(tmp[cursor2], a[cursor1]) < 0) {
|
jaroslav@559
|
808 |
a[dest--] = a[cursor1--];
|
jaroslav@559
|
809 |
count1++;
|
jaroslav@559
|
810 |
count2 = 0;
|
jaroslav@559
|
811 |
if (--len1 == 0)
|
jaroslav@559
|
812 |
break outer;
|
jaroslav@559
|
813 |
} else {
|
jaroslav@559
|
814 |
a[dest--] = tmp[cursor2--];
|
jaroslav@559
|
815 |
count2++;
|
jaroslav@559
|
816 |
count1 = 0;
|
jaroslav@559
|
817 |
if (--len2 == 1)
|
jaroslav@559
|
818 |
break outer;
|
jaroslav@559
|
819 |
}
|
jaroslav@559
|
820 |
} while ((count1 | count2) < minGallop);
|
jaroslav@559
|
821 |
|
jaroslav@559
|
822 |
/*
|
jaroslav@559
|
823 |
* One run is winning so consistently that galloping may be a
|
jaroslav@559
|
824 |
* huge win. So try that, and continue galloping until (if ever)
|
jaroslav@559
|
825 |
* neither run appears to be winning consistently anymore.
|
jaroslav@559
|
826 |
*/
|
jaroslav@559
|
827 |
do {
|
jaroslav@559
|
828 |
assert len1 > 0 && len2 > 1;
|
jaroslav@559
|
829 |
count1 = len1 - gallopRight(tmp[cursor2], a, base1, len1, len1 - 1, c);
|
jaroslav@559
|
830 |
if (count1 != 0) {
|
jaroslav@559
|
831 |
dest -= count1;
|
jaroslav@559
|
832 |
cursor1 -= count1;
|
jaroslav@559
|
833 |
len1 -= count1;
|
jaroslav@559
|
834 |
System.arraycopy(a, cursor1 + 1, a, dest + 1, count1);
|
jaroslav@559
|
835 |
if (len1 == 0)
|
jaroslav@559
|
836 |
break outer;
|
jaroslav@559
|
837 |
}
|
jaroslav@559
|
838 |
a[dest--] = tmp[cursor2--];
|
jaroslav@559
|
839 |
if (--len2 == 1)
|
jaroslav@559
|
840 |
break outer;
|
jaroslav@559
|
841 |
|
jaroslav@559
|
842 |
count2 = len2 - gallopLeft(a[cursor1], tmp, 0, len2, len2 - 1, c);
|
jaroslav@559
|
843 |
if (count2 != 0) {
|
jaroslav@559
|
844 |
dest -= count2;
|
jaroslav@559
|
845 |
cursor2 -= count2;
|
jaroslav@559
|
846 |
len2 -= count2;
|
jaroslav@559
|
847 |
System.arraycopy(tmp, cursor2 + 1, a, dest + 1, count2);
|
jaroslav@559
|
848 |
if (len2 <= 1) // len2 == 1 || len2 == 0
|
jaroslav@559
|
849 |
break outer;
|
jaroslav@559
|
850 |
}
|
jaroslav@559
|
851 |
a[dest--] = a[cursor1--];
|
jaroslav@559
|
852 |
if (--len1 == 0)
|
jaroslav@559
|
853 |
break outer;
|
jaroslav@559
|
854 |
minGallop--;
|
jaroslav@559
|
855 |
} while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);
|
jaroslav@559
|
856 |
if (minGallop < 0)
|
jaroslav@559
|
857 |
minGallop = 0;
|
jaroslav@559
|
858 |
minGallop += 2; // Penalize for leaving gallop mode
|
jaroslav@559
|
859 |
} // End of "outer" loop
|
jaroslav@559
|
860 |
this.minGallop = minGallop < 1 ? 1 : minGallop; // Write back to field
|
jaroslav@559
|
861 |
|
jaroslav@559
|
862 |
if (len2 == 1) {
|
jaroslav@559
|
863 |
assert len1 > 0;
|
jaroslav@559
|
864 |
dest -= len1;
|
jaroslav@559
|
865 |
cursor1 -= len1;
|
jaroslav@559
|
866 |
System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);
|
jaroslav@559
|
867 |
a[dest] = tmp[cursor2]; // Move first elt of run2 to front of merge
|
jaroslav@559
|
868 |
} else if (len2 == 0) {
|
jaroslav@559
|
869 |
throw new IllegalArgumentException(
|
jaroslav@559
|
870 |
"Comparison method violates its general contract!");
|
jaroslav@559
|
871 |
} else {
|
jaroslav@559
|
872 |
assert len1 == 0;
|
jaroslav@559
|
873 |
assert len2 > 0;
|
jaroslav@559
|
874 |
System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2);
|
jaroslav@559
|
875 |
}
|
jaroslav@559
|
876 |
}
|
jaroslav@559
|
877 |
|
jaroslav@559
|
878 |
/**
|
jaroslav@559
|
879 |
* Ensures that the external array tmp has at least the specified
|
jaroslav@559
|
880 |
* number of elements, increasing its size if necessary. The size
|
jaroslav@559
|
881 |
* increases exponentially to ensure amortized linear time complexity.
|
jaroslav@559
|
882 |
*
|
jaroslav@559
|
883 |
* @param minCapacity the minimum required capacity of the tmp array
|
jaroslav@559
|
884 |
* @return tmp, whether or not it grew
|
jaroslav@559
|
885 |
*/
|
jaroslav@559
|
886 |
private T[] ensureCapacity(int minCapacity) {
|
jaroslav@559
|
887 |
if (tmp.length < minCapacity) {
|
jaroslav@559
|
888 |
// Compute smallest power of 2 > minCapacity
|
jaroslav@559
|
889 |
int newSize = minCapacity;
|
jaroslav@559
|
890 |
newSize |= newSize >> 1;
|
jaroslav@559
|
891 |
newSize |= newSize >> 2;
|
jaroslav@559
|
892 |
newSize |= newSize >> 4;
|
jaroslav@559
|
893 |
newSize |= newSize >> 8;
|
jaroslav@559
|
894 |
newSize |= newSize >> 16;
|
jaroslav@559
|
895 |
newSize++;
|
jaroslav@559
|
896 |
|
jaroslav@559
|
897 |
if (newSize < 0) // Not bloody likely!
|
jaroslav@559
|
898 |
newSize = minCapacity;
|
jaroslav@559
|
899 |
else
|
jaroslav@559
|
900 |
newSize = Math.min(newSize, a.length >>> 1);
|
jaroslav@559
|
901 |
|
jaroslav@559
|
902 |
@SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"})
|
jaroslav@559
|
903 |
T[] newArray = (T[]) new Object[newSize];
|
jaroslav@559
|
904 |
tmp = newArray;
|
jaroslav@559
|
905 |
}
|
jaroslav@559
|
906 |
return tmp;
|
jaroslav@559
|
907 |
}
|
jaroslav@559
|
908 |
|
jaroslav@559
|
909 |
/**
|
jaroslav@559
|
910 |
* Checks that fromIndex and toIndex are in range, and throws an
|
jaroslav@559
|
911 |
* appropriate exception if they aren't.
|
jaroslav@559
|
912 |
*
|
jaroslav@559
|
913 |
* @param arrayLen the length of the array
|
jaroslav@559
|
914 |
* @param fromIndex the index of the first element of the range
|
jaroslav@559
|
915 |
* @param toIndex the index after the last element of the range
|
jaroslav@559
|
916 |
* @throws IllegalArgumentException if fromIndex > toIndex
|
jaroslav@559
|
917 |
* @throws ArrayIndexOutOfBoundsException if fromIndex < 0
|
jaroslav@559
|
918 |
* or toIndex > arrayLen
|
jaroslav@559
|
919 |
*/
|
jaroslav@559
|
920 |
private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {
|
jaroslav@559
|
921 |
if (fromIndex > toIndex)
|
jaroslav@559
|
922 |
throw new IllegalArgumentException("fromIndex(" + fromIndex +
|
jaroslav@559
|
923 |
") > toIndex(" + toIndex+")");
|
jaroslav@559
|
924 |
if (fromIndex < 0)
|
jaroslav@559
|
925 |
throw new ArrayIndexOutOfBoundsException(fromIndex);
|
jaroslav@559
|
926 |
if (toIndex > arrayLen)
|
jaroslav@559
|
927 |
throw new ArrayIndexOutOfBoundsException(toIndex);
|
jaroslav@559
|
928 |
}
|
jaroslav@559
|
929 |
}
|