| 1 |
|
/* |
| 2 |
< |
* Copyright (C) 2008 The Android Open Source Project |
| 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 |
< |
* Licensed under the Apache License, Version 2.0 (the "License"); |
| 7 |
< |
* you may not use this file except in compliance with the License. |
| 8 |
< |
* You may obtain a copy of the License at |
| 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 |
< |
* http://www.apache.org/licenses/LICENSE-2.0 |
| 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 |
< |
* Unless required by applicable law or agreed to in writing, software |
| 19 |
< |
* distributed under the License is distributed on an "AS IS" BASIS, |
| 20 |
< |
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 21 |
< |
* See the License for the specific language governing permissions and |
| 22 |
< |
* limitations under the License. |
| 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; |
| 87 |
|
private static final int INITIAL_TMP_STORAGE_LENGTH = 256; |
| 88 |
|
|
| 89 |
|
/** |
| 90 |
< |
* Temp storage for merges. |
| 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 |
| 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) { |
| 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 |
< |
@SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"}) |
| 126 |
< |
Object[] newArray = new Object[len < 2 * INITIAL_TMP_STORAGE_LENGTH ? |
| 127 |
< |
len >>> 1 : INITIAL_TMP_STORAGE_LENGTH]; |
| 128 |
< |
tmp = newArray; |
| 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 |
| 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 ? 19 : 40); |
| 154 |
> |
len < 119151 ? 24 : 49); |
| 155 |
|
runBase = new int[stackLen]; |
| 156 |
|
runLen = new int[stackLen]; |
| 157 |
|
} |
| 158 |
|
|
| 159 |
|
/* |
| 160 |
< |
* The next two methods (which are package private and static) constitute |
| 161 |
< |
* the entire API of this class. Each of these methods obeys the contract |
| 133 |
< |
* of the public method with the same signature in java.util.Arrays. |
| 160 |
> |
* The next method (package private and static) constitutes the |
| 161 |
> |
* entire API of this class. |
| 162 |
|
*/ |
| 163 |
|
|
| 164 |
< |
static void sort(Object[] a) { |
| 165 |
< |
sort(a, 0, a.length); |
| 166 |
< |
} |
| 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 |
|
|
| 140 |
– |
static void sort(Object[] a, int lo, int hi) { |
| 141 |
– |
rangeCheck(a.length, lo, hi); |
| 182 |
|
int nRemaining = hi - lo; |
| 183 |
|
if (nRemaining < 2) |
| 184 |
|
return; // Arrays of size 0 and 1 are always sorted |
| 195 |
|
* extending short natural runs to minRun elements, and merging runs |
| 196 |
|
* to maintain stack invariant. |
| 197 |
|
*/ |
| 198 |
< |
ComparableTimSort ts = new ComparableTimSort(a); |
| 198 |
> |
ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen); |
| 199 |
|
int minRun = minRunLength(nRemaining); |
| 200 |
|
do { |
| 201 |
|
// Identify next run |
| 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") |
| 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 |
< |
@SuppressWarnings("unchecked") |
| 210 |
< |
Comparable<Object> pivot = (Comparable) a[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; |
| 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 to make room for pivot. |
| 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 |
| 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}. |
| 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") |
| 312 |
> |
@SuppressWarnings({"unchecked", "rawtypes"}) |
| 313 |
|
private static int countRunAndMakeAscending(Object[] a, int lo, int hi) { |
| 314 |
|
assert lo < hi; |
| 315 |
|
int runHi = lo + 1; |
| 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]) { |
| 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 |
< |
mergeAt(n); |
| 366 |
< |
} else if (runLen[n] <= runLen[n + 1]) { |
| 367 |
< |
mergeAt(n); |
| 368 |
< |
} else { |
| 410 |
> |
} else if (n < 0 || runLen[n] > runLen[n + 1]) { |
| 411 |
|
break; // Invariant is established |
| 412 |
|
} |
| 413 |
+ |
mergeAt(n); |
| 414 |
|
} |
| 415 |
|
} |
| 416 |
|
|
| 648 |
|
* (must be aBase + aLen) |
| 649 |
|
* @param len2 length of second run to be merged (must be > 0) |
| 650 |
|
*/ |
| 651 |
< |
@SuppressWarnings("unchecked") |
| 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); |
| 615 |
– |
System.arraycopy(a, base1, tmp, 0, len1); |
| 658 |
|
|
| 659 |
< |
int cursor1 = 0; // Indexes into tmp array |
| 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++]; |
| 765 |
|
* (must be aBase + aLen) |
| 766 |
|
* @param len2 length of second run to be merged (must be > 0) |
| 767 |
|
*/ |
| 768 |
< |
@SuppressWarnings("unchecked") |
| 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 |
< |
System.arraycopy(a, base2, tmp, 0, 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 = len2 - 1; // Indexes into tmp array |
| 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, 0, a, dest - (len2 - 1), len2); |
| 785 |
> |
System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2); |
| 786 |
|
return; |
| 787 |
|
} |
| 788 |
|
if (len2 == 1) { |
| 840 |
|
if (--len2 == 1) |
| 841 |
|
break outer; |
| 842 |
|
|
| 843 |
< |
count2 = len2 - gallopLeft((Comparable) a[cursor1], tmp, 0, len2, len2 - 1); |
| 843 |
> |
count2 = len2 - gallopLeft((Comparable) a[cursor1], tmp, tmpBase, len2, len2 - 1); |
| 844 |
|
if (count2 != 0) { |
| 845 |
|
dest -= count2; |
| 846 |
|
cursor2 -= count2; |
| 872 |
|
} else { |
| 873 |
|
assert len1 == 0; |
| 874 |
|
assert len2 > 0; |
| 875 |
< |
System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2); |
| 875 |
> |
System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2); |
| 876 |
|
} |
| 877 |
|
} |
| 878 |
|
|
| 885 |
|
* @return tmp, whether or not it grew |
| 886 |
|
*/ |
| 887 |
|
private Object[] ensureCapacity(int minCapacity) { |
| 888 |
< |
if (tmp.length < minCapacity) { |
| 888 |
> |
if (tmpLen < minCapacity) { |
| 889 |
|
// Compute smallest power of 2 > minCapacity |
| 890 |
< |
int newSize = minCapacity; |
| 847 |
< |
newSize |= newSize >> 1; |
| 848 |
< |
newSize |= newSize >> 2; |
| 849 |
< |
newSize |= newSize >> 4; |
| 850 |
< |
newSize |= newSize >> 8; |
| 851 |
< |
newSize |= newSize >> 16; |
| 890 |
> |
int newSize = -1 >>> Integer.numberOfLeadingZeros(minCapacity); |
| 891 |
|
newSize++; |
| 892 |
|
|
| 893 |
|
if (newSize < 0) // Not bloody likely! |
| 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 |
|
|
| 866 |
– |
/** |
| 867 |
– |
* Checks that fromIndex and toIndex are in range, and throws an |
| 868 |
– |
* appropriate exception if they aren't. |
| 869 |
– |
* |
| 870 |
– |
* @param arrayLen the length of the array |
| 871 |
– |
* @param fromIndex the index of the first element of the range |
| 872 |
– |
* @param toIndex the index after the last element of the range |
| 873 |
– |
* @throws IllegalArgumentException if fromIndex > toIndex |
| 874 |
– |
* @throws ArrayIndexOutOfBoundsException if fromIndex < 0 |
| 875 |
– |
* or toIndex > arrayLen |
| 876 |
– |
*/ |
| 877 |
– |
private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) { |
| 878 |
– |
if (fromIndex > toIndex) |
| 879 |
– |
throw new IllegalArgumentException("fromIndex(" + fromIndex + |
| 880 |
– |
") > toIndex(" + toIndex+")"); |
| 881 |
– |
if (fromIndex < 0) |
| 882 |
– |
throw new ArrayIndexOutOfBoundsException(fromIndex); |
| 883 |
– |
if (toIndex > arrayLen) |
| 884 |
– |
throw new ArrayIndexOutOfBoundsException(toIndex); |
| 885 |
– |
} |
| 907 |
|
} |
