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