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 |
|
} |