| 1 |
|
/* |
| 2 |
< |
* Copyright (C) 2008 The Android Open Source Project |
| 3 |
< |
* |
| 4 |
< |
* Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 |
< |
* you may not use this file except in compliance with the License. |
| 6 |
< |
* You may obtain a copy of the License at |
| 7 |
< |
* |
| 8 |
< |
* http://www.apache.org/licenses/LICENSE-2.0 |
| 9 |
< |
* |
| 10 |
< |
* Unless required by applicable law or agreed to in writing, software |
| 11 |
< |
* distributed under the License is distributed on an "AS IS" BASIS, |
| 12 |
< |
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 |
< |
* See the License for the specific language governing permissions and |
| 14 |
< |
* limitations under the License. |
| 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; |
| 112 |
|
private static final int INITIAL_TMP_STORAGE_LENGTH = 256; |
| 113 |
|
|
| 114 |
|
/** |
| 115 |
< |
* Temp storage for merges. |
| 116 |
< |
*/ |
| 117 |
< |
private T[] tmp; // Actual runtime type will be Object[], regardless of T |
| 115 |
> |
* Temp storage for merges. A workspace array may optionally be |
| 116 |
> |
* provided in constructor, and if so will be used as long as it |
| 117 |
> |
* is big enough. |
| 118 |
> |
*/ |
| 119 |
> |
private T[] tmp; |
| 120 |
> |
private int tmpBase; // base of tmp array slice |
| 121 |
> |
private int tmpLen; // length of tmp array slice |
| 122 |
|
|
| 123 |
|
/** |
| 124 |
|
* A stack of pending runs yet to be merged. Run i starts at |
| 139 |
|
* |
| 140 |
|
* @param a the array to be sorted |
| 141 |
|
* @param c the comparator to determine the order of the sort |
| 142 |
+ |
* @param work a workspace array (slice) |
| 143 |
+ |
* @param workBase origin of usable space in work array |
| 144 |
+ |
* @param workLen usable size of work array |
| 145 |
|
*/ |
| 146 |
< |
private TimSort(T[] a, Comparator<? super T> c) { |
| 146 |
> |
private TimSort(T[] a, Comparator<? super T> c, T[] work, int workBase, int workLen) { |
| 147 |
|
this.a = a; |
| 148 |
|
this.c = c; |
| 149 |
|
|
| 150 |
|
// Allocate temp storage (which may be increased later if necessary) |
| 151 |
|
int len = a.length; |
| 152 |
< |
@SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"}) |
| 153 |
< |
T[] newArray = (T[]) new Object[len < 2 * INITIAL_TMP_STORAGE_LENGTH ? |
| 154 |
< |
len >>> 1 : INITIAL_TMP_STORAGE_LENGTH]; |
| 155 |
< |
tmp = newArray; |
| 152 |
> |
int tlen = (len < 2 * INITIAL_TMP_STORAGE_LENGTH) ? |
| 153 |
> |
len >>> 1 : INITIAL_TMP_STORAGE_LENGTH; |
| 154 |
> |
if (work == null || workLen < tlen || workBase + tlen > work.length) { |
| 155 |
> |
@SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"}) |
| 156 |
> |
T[] newArray = (T[])java.lang.reflect.Array.newInstance |
| 157 |
> |
(a.getClass().getComponentType(), tlen); |
| 158 |
> |
tmp = newArray; |
| 159 |
> |
tmpBase = 0; |
| 160 |
> |
tmpLen = tlen; |
| 161 |
> |
} |
| 162 |
> |
else { |
| 163 |
> |
tmp = work; |
| 164 |
> |
tmpBase = workBase; |
| 165 |
> |
tmpLen = workLen; |
| 166 |
> |
} |
| 167 |
|
|
| 168 |
|
/* |
| 169 |
|
* Allocate runs-to-be-merged stack (which cannot be expanded). The |
| 174 |
|
* large) stack lengths for smaller arrays. The "magic numbers" in the |
| 175 |
|
* computation below must be changed if MIN_MERGE is decreased. See |
| 176 |
|
* the MIN_MERGE declaration above for more information. |
| 177 |
+ |
* The maximum value of 49 allows for an array up to length |
| 178 |
+ |
* Integer.MAX_VALUE-4, if array is filled by the worst case stack size |
| 179 |
+ |
* increasing scenario. More explanations are given in section 4 of: |
| 180 |
+ |
* http://envisage-project.eu/wp-content/uploads/2015/02/sorting.pdf |
| 181 |
|
*/ |
| 182 |
|
int stackLen = (len < 120 ? 5 : |
| 183 |
|
len < 1542 ? 10 : |
| 184 |
< |
len < 119151 ? 19 : 40); |
| 184 |
> |
len < 119151 ? 24 : 49); |
| 185 |
|
runBase = new int[stackLen]; |
| 186 |
|
runLen = new int[stackLen]; |
| 187 |
|
} |
| 188 |
|
|
| 189 |
|
/* |
| 190 |
< |
* The next two methods (which are package private and static) constitute |
| 191 |
< |
* the entire API of this class. Each of these methods obeys the contract |
| 160 |
< |
* of the public method with the same signature in java.util.Arrays. |
| 190 |
> |
* The next method (package private and static) constitutes the |
| 191 |
> |
* entire API of this class. |
| 192 |
|
*/ |
| 193 |
|
|
| 194 |
< |
static <T> void sort(T[] a, Comparator<? super T> c) { |
| 195 |
< |
sort(a, 0, a.length, c); |
| 196 |
< |
} |
| 197 |
< |
|
| 198 |
< |
static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c) { |
| 199 |
< |
if (c == null) { |
| 200 |
< |
Arrays.sort(a, lo, hi); |
| 201 |
< |
return; |
| 202 |
< |
} |
| 194 |
> |
/** |
| 195 |
> |
* Sorts the given range, using the given workspace array slice |
| 196 |
> |
* for temp storage when possible. This method is designed to be |
| 197 |
> |
* invoked from public methods (in class Arrays) after performing |
| 198 |
> |
* any necessary array bounds checks and expanding parameters into |
| 199 |
> |
* the required forms. |
| 200 |
> |
* |
| 201 |
> |
* @param a the array to be sorted |
| 202 |
> |
* @param lo the index of the first element, inclusive, to be sorted |
| 203 |
> |
* @param hi the index of the last element, exclusive, to be sorted |
| 204 |
> |
* @param c the comparator to use |
| 205 |
> |
* @param work a workspace array (slice) |
| 206 |
> |
* @param workBase origin of usable space in work array |
| 207 |
> |
* @param workLen usable size of work array |
| 208 |
> |
* @since 1.8 |
| 209 |
> |
*/ |
| 210 |
> |
static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c, |
| 211 |
> |
T[] work, int workBase, int workLen) { |
| 212 |
> |
assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length; |
| 213 |
|
|
| 173 |
– |
rangeCheck(a.length, lo, hi); |
| 214 |
|
int nRemaining = hi - lo; |
| 215 |
|
if (nRemaining < 2) |
| 216 |
|
return; // Arrays of size 0 and 1 are always sorted |
| 227 |
|
* extending short natural runs to minRun elements, and merging runs |
| 228 |
|
* to maintain stack invariant. |
| 229 |
|
*/ |
| 230 |
< |
TimSort<T> ts = new TimSort<T>(a, c); |
| 230 |
> |
TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen); |
| 231 |
|
int minRun = minRunLength(nRemaining); |
| 232 |
|
do { |
| 233 |
|
// Identify next run |
| 305 |
|
* pivot < all in [left, start), so pivot belongs at left. Note |
| 306 |
|
* that if there are elements equal to pivot, left points to the |
| 307 |
|
* first slot after them -- that's why this sort is stable. |
| 308 |
< |
* Slide elements over to make room to make room for pivot. |
| 308 |
> |
* Slide elements over to make room for pivot. |
| 309 |
|
*/ |
| 310 |
|
int n = start - left; // The number of elements to move |
| 311 |
|
// Switch is just an optimization for arraycopy in default case |
| 429 |
|
* This method is called each time a new run is pushed onto the stack, |
| 430 |
|
* so the invariants are guaranteed to hold for i < stackSize upon |
| 431 |
|
* entry to the method. |
| 432 |
+ |
* |
| 433 |
+ |
* Thanks to Stijn de Gouw, Jurriaan Rot, Frank S. de Boer, |
| 434 |
+ |
* Richard Bubel and Reiner Hahnle, this is fixed with respect to |
| 435 |
+ |
* the analysis in "On the Worst-Case Complexity of TimSort" by |
| 436 |
+ |
* Nicolas Auger, Vincent Jug, Cyril Nicaud, and Carine Pivoteau. |
| 437 |
|
*/ |
| 438 |
|
private void mergeCollapse() { |
| 439 |
|
while (stackSize > 1) { |
| 440 |
|
int n = stackSize - 2; |
| 441 |
< |
if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) { |
| 441 |
> |
if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1] || |
| 442 |
> |
n > 1 && runLen[n-2] <= runLen[n] + runLen[n-1]) { |
| 443 |
|
if (runLen[n - 1] < runLen[n + 1]) |
| 444 |
|
n--; |
| 445 |
< |
mergeAt(n); |
| 400 |
< |
} else if (runLen[n] <= runLen[n + 1]) { |
| 401 |
< |
mergeAt(n); |
| 402 |
< |
} else { |
| 445 |
> |
} else if (n < 0 || runLen[n] > runLen[n + 1]) { |
| 446 |
|
break; // Invariant is established |
| 447 |
|
} |
| 448 |
+ |
mergeAt(n); |
| 449 |
|
} |
| 450 |
|
} |
| 451 |
|
|
| 688 |
|
// Copy first run into temp array |
| 689 |
|
T[] a = this.a; // For performance |
| 690 |
|
T[] tmp = ensureCapacity(len1); |
| 691 |
< |
System.arraycopy(a, base1, tmp, 0, len1); |
| 648 |
< |
|
| 649 |
< |
int cursor1 = 0; // Indexes into tmp array |
| 691 |
> |
int cursor1 = tmpBase; // Indexes into tmp array |
| 692 |
|
int cursor2 = base2; // Indexes int a |
| 693 |
|
int dest = base1; // Indexes int a |
| 694 |
+ |
System.arraycopy(a, base1, tmp, cursor1, len1); |
| 695 |
|
|
| 696 |
|
// Move first element of second run and deal with degenerate cases |
| 697 |
|
a[dest++] = a[cursor2++]; |
| 804 |
|
// Copy second run into temp array |
| 805 |
|
T[] a = this.a; // For performance |
| 806 |
|
T[] tmp = ensureCapacity(len2); |
| 807 |
< |
System.arraycopy(a, base2, tmp, 0, len2); |
| 807 |
> |
int tmpBase = this.tmpBase; |
| 808 |
> |
System.arraycopy(a, base2, tmp, tmpBase, len2); |
| 809 |
|
|
| 810 |
|
int cursor1 = base1 + len1 - 1; // Indexes into a |
| 811 |
< |
int cursor2 = len2 - 1; // Indexes into tmp array |
| 811 |
> |
int cursor2 = tmpBase + len2 - 1; // Indexes into tmp array |
| 812 |
|
int dest = base2 + len2 - 1; // Indexes into a |
| 813 |
|
|
| 814 |
|
// Move last element of first run and deal with degenerate cases |
| 815 |
|
a[dest--] = a[cursor1--]; |
| 816 |
|
if (--len1 == 0) { |
| 817 |
< |
System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2); |
| 817 |
> |
System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2); |
| 818 |
|
return; |
| 819 |
|
} |
| 820 |
|
if (len2 == 1) { |
| 873 |
|
if (--len2 == 1) |
| 874 |
|
break outer; |
| 875 |
|
|
| 876 |
< |
count2 = len2 - gallopLeft(a[cursor1], tmp, 0, len2, len2 - 1, c); |
| 876 |
> |
count2 = len2 - gallopLeft(a[cursor1], tmp, tmpBase, len2, len2 - 1, c); |
| 877 |
|
if (count2 != 0) { |
| 878 |
|
dest -= count2; |
| 879 |
|
cursor2 -= count2; |
| 905 |
|
} else { |
| 906 |
|
assert len1 == 0; |
| 907 |
|
assert len2 > 0; |
| 908 |
< |
System.arraycopy(tmp, 0, a, dest - (len2 - 1), len2); |
| 908 |
> |
System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2); |
| 909 |
|
} |
| 910 |
|
} |
| 911 |
|
|
| 918 |
|
* @return tmp, whether or not it grew |
| 919 |
|
*/ |
| 920 |
|
private T[] ensureCapacity(int minCapacity) { |
| 921 |
< |
if (tmp.length < minCapacity) { |
| 921 |
> |
if (tmpLen < minCapacity) { |
| 922 |
|
// Compute smallest power of 2 > minCapacity |
| 923 |
< |
int newSize = minCapacity; |
| 880 |
< |
newSize |= newSize >> 1; |
| 881 |
< |
newSize |= newSize >> 2; |
| 882 |
< |
newSize |= newSize >> 4; |
| 883 |
< |
newSize |= newSize >> 8; |
| 884 |
< |
newSize |= newSize >> 16; |
| 923 |
> |
int newSize = -1 >>> Integer.numberOfLeadingZeros(minCapacity); |
| 924 |
|
newSize++; |
| 925 |
|
|
| 926 |
|
if (newSize < 0) // Not bloody likely! |
| 929 |
|
newSize = Math.min(newSize, a.length >>> 1); |
| 930 |
|
|
| 931 |
|
@SuppressWarnings({"unchecked", "UnnecessaryLocalVariable"}) |
| 932 |
< |
T[] newArray = (T[]) new Object[newSize]; |
| 932 |
> |
T[] newArray = (T[])java.lang.reflect.Array.newInstance |
| 933 |
> |
(a.getClass().getComponentType(), newSize); |
| 934 |
|
tmp = newArray; |
| 935 |
+ |
tmpLen = newSize; |
| 936 |
+ |
tmpBase = 0; |
| 937 |
|
} |
| 938 |
|
return tmp; |
| 939 |
|
} |
| 898 |
– |
|
| 899 |
– |
/** |
| 900 |
– |
* Checks that fromIndex and toIndex are in range, and throws an |
| 901 |
– |
* appropriate exception if they aren't. |
| 902 |
– |
* |
| 903 |
– |
* @param arrayLen the length of the array |
| 904 |
– |
* @param fromIndex the index of the first element of the range |
| 905 |
– |
* @param toIndex the index after the last element of the range |
| 906 |
– |
* @throws IllegalArgumentException if fromIndex > toIndex |
| 907 |
– |
* @throws ArrayIndexOutOfBoundsException if fromIndex < 0 |
| 908 |
– |
* or toIndex > arrayLen |
| 909 |
– |
*/ |
| 910 |
– |
private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) { |
| 911 |
– |
if (fromIndex > toIndex) |
| 912 |
– |
throw new IllegalArgumentException("fromIndex(" + fromIndex + |
| 913 |
– |
") > toIndex(" + toIndex+")"); |
| 914 |
– |
if (fromIndex < 0) |
| 915 |
– |
throw new ArrayIndexOutOfBoundsException(fromIndex); |
| 916 |
– |
if (toIndex > arrayLen) |
| 917 |
– |
throw new ArrayIndexOutOfBoundsException(toIndex); |
| 918 |
– |
} |
| 940 |
|
} |
