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