1 /*
2 * Copyright 1997-2007 Sun Microsystems, Inc. All Rights Reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Sun designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Sun in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22 * CA 95054 USA or visit www.sun.com if you need additional information or
23 * have any questions.
24 */
25
26 package java.util;
27
28 import java.lang.reflect;
29
30 /**
31 * This class contains various methods for manipulating arrays (such as
32 * sorting and searching). This class also contains a static factory
33 * that allows arrays to be viewed as lists.
34 *
35 * <p>The methods in this class all throw a <tt>NullPointerException</tt> if
36 * the specified array reference is null, except where noted.
37 *
38 * <p>The documentation for the methods contained in this class includes
39 * briefs description of the <i>implementations</i>. Such descriptions should
40 * be regarded as <i>implementation notes</i>, rather than parts of the
41 * <i>specification</i>. Implementors should feel free to substitute other
42 * algorithms, so long as the specification itself is adhered to. (For
43 * example, the algorithm used by <tt>sort(Object[])</tt> does not have to be
44 * a mergesort, but it does have to be <i>stable</i>.)
45 *
46 * <p>This class is a member of the
47 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
48 * Java Collections Framework</a>.
49 *
50 * @author Josh Bloch
51 * @author Neal Gafter
52 * @author John Rose
53 * @since 1.2
54 */
55
56 public class Arrays {
57 // Suppresses default constructor, ensuring non-instantiability.
58 private Arrays() {
59 }
60
61 // Sorting
62
63 /**
64 * Sorts the specified array of longs into ascending numerical order.
65 * The sorting algorithm is a tuned quicksort, adapted from Jon
66 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
67 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
68 * 1993). This algorithm offers n*log(n) performance on many data sets
69 * that cause other quicksorts to degrade to quadratic performance.
70 *
71 * @param a the array to be sorted
72 */
73 public static void sort(long[] a) {
74 sort1(a, 0, a.length);
75 }
76
77 /**
78 * Sorts the specified range of the specified array of longs into
79 * ascending numerical order. The range to be sorted extends from index
80 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
81 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
82 *
83 * <p>The sorting algorithm is a tuned quicksort, adapted from Jon
84 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
85 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
86 * 1993). This algorithm offers n*log(n) performance on many data sets
87 * that cause other quicksorts to degrade to quadratic performance.
88 *
89 * @param a the array to be sorted
90 * @param fromIndex the index of the first element (inclusive) to be
91 * sorted
92 * @param toIndex the index of the last element (exclusive) to be sorted
93 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
94 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
95 * <tt>toIndex > a.length</tt>
96 */
97 public static void sort(long[] a, int fromIndex, int toIndex) {
98 rangeCheck(a.length, fromIndex, toIndex);
99 sort1(a, fromIndex, toIndex-fromIndex);
100 }
101
102 /**
103 * Sorts the specified array of ints into ascending numerical order.
104 * The sorting algorithm is a tuned quicksort, adapted from Jon
105 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
106 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
107 * 1993). This algorithm offers n*log(n) performance on many data sets
108 * that cause other quicksorts to degrade to quadratic performance.
109 *
110 * @param a the array to be sorted
111 */
112 public static void sort(int[] a) {
113 sort1(a, 0, a.length);
114 }
115
116 /**
117 * Sorts the specified range of the specified array of ints into
118 * ascending numerical order. The range to be sorted extends from index
119 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
120 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
121 *
122 * The sorting algorithm is a tuned quicksort, adapted from Jon
123 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
124 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
125 * 1993). This algorithm offers n*log(n) performance on many data sets
126 * that cause other quicksorts to degrade to quadratic performance.
127 *
128 * @param a the array to be sorted
129 * @param fromIndex the index of the first element (inclusive) to be
130 * sorted
131 * @param toIndex the index of the last element (exclusive) to be sorted
132 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
133 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
134 * <tt>toIndex > a.length</tt>
135 */
136 public static void sort(int[] a, int fromIndex, int toIndex) {
137 rangeCheck(a.length, fromIndex, toIndex);
138 sort1(a, fromIndex, toIndex-fromIndex);
139 }
140
141 /**
142 * Sorts the specified array of shorts into ascending numerical order.
143 * The sorting algorithm is a tuned quicksort, adapted from Jon
144 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
145 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
146 * 1993). This algorithm offers n*log(n) performance on many data sets
147 * that cause other quicksorts to degrade to quadratic performance.
148 *
149 * @param a the array to be sorted
150 */
151 public static void sort(short[] a) {
152 sort1(a, 0, a.length);
153 }
154
155 /**
156 * Sorts the specified range of the specified array of shorts into
157 * ascending numerical order. The range to be sorted extends from index
158 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
159 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
160 *
161 * The sorting algorithm is a tuned quicksort, adapted from Jon
162 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
163 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
164 * 1993). This algorithm offers n*log(n) performance on many data sets
165 * that cause other quicksorts to degrade to quadratic performance.
166 *
167 * @param a the array to be sorted
168 * @param fromIndex the index of the first element (inclusive) to be
169 * sorted
170 * @param toIndex the index of the last element (exclusive) to be sorted
171 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
172 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
173 * <tt>toIndex > a.length</tt>
174 */
175 public static void sort(short[] a, int fromIndex, int toIndex) {
176 rangeCheck(a.length, fromIndex, toIndex);
177 sort1(a, fromIndex, toIndex-fromIndex);
178 }
179
180 /**
181 * Sorts the specified array of chars into ascending numerical order.
182 * The sorting algorithm is a tuned quicksort, adapted from Jon
183 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
184 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
185 * 1993). This algorithm offers n*log(n) performance on many data sets
186 * that cause other quicksorts to degrade to quadratic performance.
187 *
188 * @param a the array to be sorted
189 */
190 public static void sort(char[] a) {
191 sort1(a, 0, a.length);
192 }
193
194 /**
195 * Sorts the specified range of the specified array of chars into
196 * ascending numerical order. The range to be sorted extends from index
197 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
198 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
199 *
200 * The sorting algorithm is a tuned quicksort, adapted from Jon
201 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
202 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
203 * 1993). This algorithm offers n*log(n) performance on many data sets
204 * that cause other quicksorts to degrade to quadratic performance.
205 *
206 * @param a the array to be sorted
207 * @param fromIndex the index of the first element (inclusive) to be
208 * sorted
209 * @param toIndex the index of the last element (exclusive) to be sorted
210 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
211 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
212 * <tt>toIndex > a.length</tt>
213 */
214 public static void sort(char[] a, int fromIndex, int toIndex) {
215 rangeCheck(a.length, fromIndex, toIndex);
216 sort1(a, fromIndex, toIndex-fromIndex);
217 }
218
219 /**
220 * Sorts the specified array of bytes into ascending numerical order.
221 * The sorting algorithm is a tuned quicksort, adapted from Jon
222 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
223 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
224 * 1993). This algorithm offers n*log(n) performance on many data sets
225 * that cause other quicksorts to degrade to quadratic performance.
226 *
227 * @param a the array to be sorted
228 */
229 public static void sort(byte[] a) {
230 sort1(a, 0, a.length);
231 }
232
233 /**
234 * Sorts the specified range of the specified array of bytes into
235 * ascending numerical order. The range to be sorted extends from index
236 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
237 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
238 *
239 * The sorting algorithm is a tuned quicksort, adapted from Jon
240 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
241 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
242 * 1993). This algorithm offers n*log(n) performance on many data sets
243 * that cause other quicksorts to degrade to quadratic performance.
244 *
245 * @param a the array to be sorted
246 * @param fromIndex the index of the first element (inclusive) to be
247 * sorted
248 * @param toIndex the index of the last element (exclusive) to be sorted
249 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
250 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
251 * <tt>toIndex > a.length</tt>
252 */
253 public static void sort(byte[] a, int fromIndex, int toIndex) {
254 rangeCheck(a.length, fromIndex, toIndex);
255 sort1(a, fromIndex, toIndex-fromIndex);
256 }
257
258 /**
259 * Sorts the specified array of doubles into ascending numerical order.
260 * <p>
261 * The <code><</code> relation does not provide a total order on
262 * all floating-point values; although they are distinct numbers
263 * <code>-0.0 == 0.0</code> is <code>true</code> and a NaN value
264 * compares neither less than, greater than, nor equal to any
265 * floating-point value, even itself. To allow the sort to
266 * proceed, instead of using the <code><</code> relation to
267 * determine ascending numerical order, this method uses the total
268 * order imposed by {@link Double#compareTo}. This ordering
269 * differs from the <code><</code> relation in that
270 * <code>-0.0</code> is treated as less than <code>0.0</code> and
271 * NaN is considered greater than any other floating-point value.
272 * For the purposes of sorting, all NaN values are considered
273 * equivalent and equal.
274 * <p>
275 * The sorting algorithm is a tuned quicksort, adapted from Jon
276 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
277 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
278 * 1993). This algorithm offers n*log(n) performance on many data sets
279 * that cause other quicksorts to degrade to quadratic performance.
280 *
281 * @param a the array to be sorted
282 */
283 public static void sort(double[] a) {
284 sort2(a, 0, a.length);
285 }
286
287 /**
288 * Sorts the specified range of the specified array of doubles into
289 * ascending numerical order. The range to be sorted extends from index
290 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
291 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
292 * <p>
293 * The <code><</code> relation does not provide a total order on
294 * all floating-point values; although they are distinct numbers
295 * <code>-0.0 == 0.0</code> is <code>true</code> and a NaN value
296 * compares neither less than, greater than, nor equal to any
297 * floating-point value, even itself. To allow the sort to
298 * proceed, instead of using the <code><</code> relation to
299 * determine ascending numerical order, this method uses the total
300 * order imposed by {@link Double#compareTo}. This ordering
301 * differs from the <code><</code> relation in that
302 * <code>-0.0</code> is treated as less than <code>0.0</code> and
303 * NaN is considered greater than any other floating-point value.
304 * For the purposes of sorting, all NaN values are considered
305 * equivalent and equal.
306 * <p>
307 * The sorting algorithm is a tuned quicksort, adapted from Jon
308 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
309 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
310 * 1993). This algorithm offers n*log(n) performance on many data sets
311 * that cause other quicksorts to degrade to quadratic performance.
312 *
313 * @param a the array to be sorted
314 * @param fromIndex the index of the first element (inclusive) to be
315 * sorted
316 * @param toIndex the index of the last element (exclusive) to be sorted
317 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
318 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
319 * <tt>toIndex > a.length</tt>
320 */
321 public static void sort(double[] a, int fromIndex, int toIndex) {
322 rangeCheck(a.length, fromIndex, toIndex);
323 sort2(a, fromIndex, toIndex);
324 }
325
326 /**
327 * Sorts the specified array of floats into ascending numerical order.
328 * <p>
329 * The <code><</code> relation does not provide a total order on
330 * all floating-point values; although they are distinct numbers
331 * <code>-0.0f == 0.0f</code> is <code>true</code> and a NaN value
332 * compares neither less than, greater than, nor equal to any
333 * floating-point value, even itself. To allow the sort to
334 * proceed, instead of using the <code><</code> relation to
335 * determine ascending numerical order, this method uses the total
336 * order imposed by {@link Float#compareTo}. This ordering
337 * differs from the <code><</code> relation in that
338 * <code>-0.0f</code> is treated as less than <code>0.0f</code> and
339 * NaN is considered greater than any other floating-point value.
340 * For the purposes of sorting, all NaN values are considered
341 * equivalent and equal.
342 * <p>
343 * The sorting algorithm is a tuned quicksort, adapted from Jon
344 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
345 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
346 * 1993). This algorithm offers n*log(n) performance on many data sets
347 * that cause other quicksorts to degrade to quadratic performance.
348 *
349 * @param a the array to be sorted
350 */
351 public static void sort(float[] a) {
352 sort2(a, 0, a.length);
353 }
354
355 /**
356 * Sorts the specified range of the specified array of floats into
357 * ascending numerical order. The range to be sorted extends from index
358 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
359 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
360 * <p>
361 * The <code><</code> relation does not provide a total order on
362 * all floating-point values; although they are distinct numbers
363 * <code>-0.0f == 0.0f</code> is <code>true</code> and a NaN value
364 * compares neither less than, greater than, nor equal to any
365 * floating-point value, even itself. To allow the sort to
366 * proceed, instead of using the <code><</code> relation to
367 * determine ascending numerical order, this method uses the total
368 * order imposed by {@link Float#compareTo}. This ordering
369 * differs from the <code><</code> relation in that
370 * <code>-0.0f</code> is treated as less than <code>0.0f</code> and
371 * NaN is considered greater than any other floating-point value.
372 * For the purposes of sorting, all NaN values are considered
373 * equivalent and equal.
374 * <p>
375 * The sorting algorithm is a tuned quicksort, adapted from Jon
376 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
377 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
378 * 1993). This algorithm offers n*log(n) performance on many data sets
379 * that cause other quicksorts to degrade to quadratic performance.
380 *
381 * @param a the array to be sorted
382 * @param fromIndex the index of the first element (inclusive) to be
383 * sorted
384 * @param toIndex the index of the last element (exclusive) to be sorted
385 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
386 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
387 * <tt>toIndex > a.length</tt>
388 */
389 public static void sort(float[] a, int fromIndex, int toIndex) {
390 rangeCheck(a.length, fromIndex, toIndex);
391 sort2(a, fromIndex, toIndex);
392 }
393
394 private static void sort2(double a[], int fromIndex, int toIndex) {
395 final long NEG_ZERO_BITS = Double.doubleToLongBits(-0.0d);
396 /*
397 * The sort is done in three phases to avoid the expense of using
398 * NaN and -0.0 aware comparisons during the main sort.
399 */
400
401 /*
402 * Preprocessing phase: Move any NaN's to end of array, count the
403 * number of -0.0's, and turn them into 0.0's.
404 */
405 int numNegZeros = 0;
406 int i = fromIndex, n = toIndex;
407 while(i < n) {
408 if (a[i] != a[i]) {
409 swap(a, i, --n);
410 } else {
411 if (a[i]==0 && Double.doubleToLongBits(a[i])==NEG_ZERO_BITS) {
412 a[i] = 0.0d;
413 numNegZeros++;
414 }
415 i++;
416 }
417 }
418
419 // Main sort phase: quicksort everything but the NaN's
420 sort1(a, fromIndex, n-fromIndex);
421
422 // Postprocessing phase: change 0.0's to -0.0's as required
423 if (numNegZeros != 0) {
424 int j = binarySearch0(a, fromIndex, n, 0.0d); // posn of ANY zero
425 do {
426 j--;
427 } while (j>=fromIndex && a[j]==0.0d);
428
429 // j is now one less than the index of the FIRST zero
430 for (int k=0; k<numNegZeros; k++)
431 a[++j] = -0.0d;
432 }
433 }
434
435
436 private static void sort2(float a[], int fromIndex, int toIndex) {
437 final int NEG_ZERO_BITS = Float.floatToIntBits(-0.0f);
438 /*
439 * The sort is done in three phases to avoid the expense of using
440 * NaN and -0.0 aware comparisons during the main sort.
441 */
442
443 /*
444 * Preprocessing phase: Move any NaN's to end of array, count the
445 * number of -0.0's, and turn them into 0.0's.
446 */
447 int numNegZeros = 0;
448 int i = fromIndex, n = toIndex;
449 while(i < n) {
450 if (a[i] != a[i]) {
451 swap(a, i, --n);
452 } else {
453 if (a[i]==0 && Float.floatToIntBits(a[i])==NEG_ZERO_BITS) {
454 a[i] = 0.0f;
455 numNegZeros++;
456 }
457 i++;
458 }
459 }
460
461 // Main sort phase: quicksort everything but the NaN's
462 sort1(a, fromIndex, n-fromIndex);
463
464 // Postprocessing phase: change 0.0's to -0.0's as required
465 if (numNegZeros != 0) {
466 int j = binarySearch0(a, fromIndex, n, 0.0f); // posn of ANY zero
467 do {
468 j--;
469 } while (j>=fromIndex && a[j]==0.0f);
470
471 // j is now one less than the index of the FIRST zero
472 for (int k=0; k<numNegZeros; k++)
473 a[++j] = -0.0f;
474 }
475 }
476
477
478 /*
479 * The code for each of the seven primitive types is largely identical.
480 * C'est la vie.
481 */
482
483 /**
484 * Sorts the specified sub-array of longs into ascending order.
485 */
486 private static void sort1(long x[], int off, int len) {
487 // Insertion sort on smallest arrays
488 if (len < 7) {
489 for (int i=off; i<len+off; i++)
490 for (int j=i; j>off && x[j-1]>x[j]; j--)
491 swap(x, j, j-1);
492 return;
493 }
494
495 // Choose a partition element, v
496 int m = off + (len >> 1); // Small arrays, middle element
497 if (len > 7) {
498 int l = off;
499 int n = off + len - 1;
500 if (len > 40) { // Big arrays, pseudomedian of 9
501 int s = len/8;
502 l = med3(x, l, l+s, l+2*s);
503 m = med3(x, m-s, m, m+s);
504 n = med3(x, n-2*s, n-s, n);
505 }
506 m = med3(x, l, m, n); // Mid-size, med of 3
507 }
508 long v = x[m];
509
510 // Establish Invariant: v* (<v)* (>v)* v*
511 int a = off, b = a, c = off + len - 1, d = c;
512 while(true) {
513 while (b <= c && x[b] <= v) {
514 if (x[b] == v)
515 swap(x, a++, b);
516 b++;
517 }
518 while (c >= b && x[c] >= v) {
519 if (x[c] == v)
520 swap(x, c, d--);
521 c--;
522 }
523 if (b > c)
524 break;
525 swap(x, b++, c--);
526 }
527
528 // Swap partition elements back to middle
529 int s, n = off + len;
530 s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
531 s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
532
533 // Recursively sort non-partition-elements
534 if ((s = b-a) > 1)
535 sort1(x, off, s);
536 if ((s = d-c) > 1)
537 sort1(x, n-s, s);
538 }
539
540 /**
541 * Swaps x[a] with x[b].
542 */
543 private static void swap(long x[], int a, int b) {
544 long t = x[a];
545 x[a] = x[b];
546 x[b] = t;
547 }
548
549 /**
550 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
551 */
552 private static void vecswap(long x[], int a, int b, int n) {
553 for (int i=0; i<n; i++, a++, b++)
554 swap(x, a, b);
555 }
556
557 /**
558 * Returns the index of the median of the three indexed longs.
559 */
560 private static int med3(long x[], int a, int b, int c) {
561 return (x[a] < x[b] ?
562 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
563 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
564 }
565
566 /**
567 * Sorts the specified sub-array of integers into ascending order.
568 */
569 private static void sort1(int x[], int off, int len) {
570 // Insertion sort on smallest arrays
571 if (len < 7) {
572 for (int i=off; i<len+off; i++)
573 for (int j=i; j>off && x[j-1]>x[j]; j--)
574 swap(x, j, j-1);
575 return;
576 }
577
578 // Choose a partition element, v
579 int m = off + (len >> 1); // Small arrays, middle element
580 if (len > 7) {
581 int l = off;
582 int n = off + len - 1;
583 if (len > 40) { // Big arrays, pseudomedian of 9
584 int s = len/8;
585 l = med3(x, l, l+s, l+2*s);
586 m = med3(x, m-s, m, m+s);
587 n = med3(x, n-2*s, n-s, n);
588 }
589 m = med3(x, l, m, n); // Mid-size, med of 3
590 }
591 int v = x[m];
592
593 // Establish Invariant: v* (<v)* (>v)* v*
594 int a = off, b = a, c = off + len - 1, d = c;
595 while(true) {
596 while (b <= c && x[b] <= v) {
597 if (x[b] == v)
598 swap(x, a++, b);
599 b++;
600 }
601 while (c >= b && x[c] >= v) {
602 if (x[c] == v)
603 swap(x, c, d--);
604 c--;
605 }
606 if (b > c)
607 break;
608 swap(x, b++, c--);
609 }
610
611 // Swap partition elements back to middle
612 int s, n = off + len;
613 s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
614 s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
615
616 // Recursively sort non-partition-elements
617 if ((s = b-a) > 1)
618 sort1(x, off, s);
619 if ((s = d-c) > 1)
620 sort1(x, n-s, s);
621 }
622
623 /**
624 * Swaps x[a] with x[b].
625 */
626 private static void swap(int x[], int a, int b) {
627 int t = x[a];
628 x[a] = x[b];
629 x[b] = t;
630 }
631
632 /**
633 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
634 */
635 private static void vecswap(int x[], int a, int b, int n) {
636 for (int i=0; i<n; i++, a++, b++)
637 swap(x, a, b);
638 }
639
640 /**
641 * Returns the index of the median of the three indexed integers.
642 */
643 private static int med3(int x[], int a, int b, int c) {
644 return (x[a] < x[b] ?
645 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
646 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
647 }
648
649 /**
650 * Sorts the specified sub-array of shorts into ascending order.
651 */
652 private static void sort1(short x[], int off, int len) {
653 // Insertion sort on smallest arrays
654 if (len < 7) {
655 for (int i=off; i<len+off; i++)
656 for (int j=i; j>off && x[j-1]>x[j]; j--)
657 swap(x, j, j-1);
658 return;
659 }
660
661 // Choose a partition element, v
662 int m = off + (len >> 1); // Small arrays, middle element
663 if (len > 7) {
664 int l = off;
665 int n = off + len - 1;
666 if (len > 40) { // Big arrays, pseudomedian of 9
667 int s = len/8;
668 l = med3(x, l, l+s, l+2*s);
669 m = med3(x, m-s, m, m+s);
670 n = med3(x, n-2*s, n-s, n);
671 }
672 m = med3(x, l, m, n); // Mid-size, med of 3
673 }
674 short v = x[m];
675
676 // Establish Invariant: v* (<v)* (>v)* v*
677 int a = off, b = a, c = off + len - 1, d = c;
678 while(true) {
679 while (b <= c && x[b] <= v) {
680 if (x[b] == v)
681 swap(x, a++, b);
682 b++;
683 }
684 while (c >= b && x[c] >= v) {
685 if (x[c] == v)
686 swap(x, c, d--);
687 c--;
688 }
689 if (b > c)
690 break;
691 swap(x, b++, c--);
692 }
693
694 // Swap partition elements back to middle
695 int s, n = off + len;
696 s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
697 s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
698
699 // Recursively sort non-partition-elements
700 if ((s = b-a) > 1)
701 sort1(x, off, s);
702 if ((s = d-c) > 1)
703 sort1(x, n-s, s);
704 }
705
706 /**
707 * Swaps x[a] with x[b].
708 */
709 private static void swap(short x[], int a, int b) {
710 short t = x[a];
711 x[a] = x[b];
712 x[b] = t;
713 }
714
715 /**
716 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
717 */
718 private static void vecswap(short x[], int a, int b, int n) {
719 for (int i=0; i<n; i++, a++, b++)
720 swap(x, a, b);
721 }
722
723 /**
724 * Returns the index of the median of the three indexed shorts.
725 */
726 private static int med3(short x[], int a, int b, int c) {
727 return (x[a] < x[b] ?
728 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
729 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
730 }
731
732
733 /**
734 * Sorts the specified sub-array of chars into ascending order.
735 */
736 private static void sort1(char x[], int off, int len) {
737 // Insertion sort on smallest arrays
738 if (len < 7) {
739 for (int i=off; i<len+off; i++)
740 for (int j=i; j>off && x[j-1]>x[j]; j--)
741 swap(x, j, j-1);
742 return;
743 }
744
745 // Choose a partition element, v
746 int m = off + (len >> 1); // Small arrays, middle element
747 if (len > 7) {
748 int l = off;
749 int n = off + len - 1;
750 if (len > 40) { // Big arrays, pseudomedian of 9
751 int s = len/8;
752 l = med3(x, l, l+s, l+2*s);
753 m = med3(x, m-s, m, m+s);
754 n = med3(x, n-2*s, n-s, n);
755 }
756 m = med3(x, l, m, n); // Mid-size, med of 3
757 }
758 char v = x[m];
759
760 // Establish Invariant: v* (<v)* (>v)* v*
761 int a = off, b = a, c = off + len - 1, d = c;
762 while(true) {
763 while (b <= c && x[b] <= v) {
764 if (x[b] == v)
765 swap(x, a++, b);
766 b++;
767 }
768 while (c >= b && x[c] >= v) {
769 if (x[c] == v)
770 swap(x, c, d--);
771 c--;
772 }
773 if (b > c)
774 break;
775 swap(x, b++, c--);
776 }
777
778 // Swap partition elements back to middle
779 int s, n = off + len;
780 s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
781 s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
782
783 // Recursively sort non-partition-elements
784 if ((s = b-a) > 1)
785 sort1(x, off, s);
786 if ((s = d-c) > 1)
787 sort1(x, n-s, s);
788 }
789
790 /**
791 * Swaps x[a] with x[b].
792 */
793 private static void swap(char x[], int a, int b) {
794 char t = x[a];
795 x[a] = x[b];
796 x[b] = t;
797 }
798
799 /**
800 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
801 */
802 private static void vecswap(char x[], int a, int b, int n) {
803 for (int i=0; i<n; i++, a++, b++)
804 swap(x, a, b);
805 }
806
807 /**
808 * Returns the index of the median of the three indexed chars.
809 */
810 private static int med3(char x[], int a, int b, int c) {
811 return (x[a] < x[b] ?
812 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
813 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
814 }
815
816
817 /**
818 * Sorts the specified sub-array of bytes into ascending order.
819 */
820 private static void sort1(byte x[], int off, int len) {
821 // Insertion sort on smallest arrays
822 if (len < 7) {
823 for (int i=off; i<len+off; i++)
824 for (int j=i; j>off && x[j-1]>x[j]; j--)
825 swap(x, j, j-1);
826 return;
827 }
828
829 // Choose a partition element, v
830 int m = off + (len >> 1); // Small arrays, middle element
831 if (len > 7) {
832 int l = off;
833 int n = off + len - 1;
834 if (len > 40) { // Big arrays, pseudomedian of 9
835 int s = len/8;
836 l = med3(x, l, l+s, l+2*s);
837 m = med3(x, m-s, m, m+s);
838 n = med3(x, n-2*s, n-s, n);
839 }
840 m = med3(x, l, m, n); // Mid-size, med of 3
841 }
842 byte v = x[m];
843
844 // Establish Invariant: v* (<v)* (>v)* v*
845 int a = off, b = a, c = off + len - 1, d = c;
846 while(true) {
847 while (b <= c && x[b] <= v) {
848 if (x[b] == v)
849 swap(x, a++, b);
850 b++;
851 }
852 while (c >= b && x[c] >= v) {
853 if (x[c] == v)
854 swap(x, c, d--);
855 c--;
856 }
857 if (b > c)
858 break;
859 swap(x, b++, c--);
860 }
861
862 // Swap partition elements back to middle
863 int s, n = off + len;
864 s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
865 s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
866
867 // Recursively sort non-partition-elements
868 if ((s = b-a) > 1)
869 sort1(x, off, s);
870 if ((s = d-c) > 1)
871 sort1(x, n-s, s);
872 }
873
874 /**
875 * Swaps x[a] with x[b].
876 */
877 private static void swap(byte x[], int a, int b) {
878 byte t = x[a];
879 x[a] = x[b];
880 x[b] = t;
881 }
882
883 /**
884 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
885 */
886 private static void vecswap(byte x[], int a, int b, int n) {
887 for (int i=0; i<n; i++, a++, b++)
888 swap(x, a, b);
889 }
890
891 /**
892 * Returns the index of the median of the three indexed bytes.
893 */
894 private static int med3(byte x[], int a, int b, int c) {
895 return (x[a] < x[b] ?
896 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
897 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
898 }
899
900
901 /**
902 * Sorts the specified sub-array of doubles into ascending order.
903 */
904 private static void sort1(double x[], int off, int len) {
905 // Insertion sort on smallest arrays
906 if (len < 7) {
907 for (int i=off; i<len+off; i++)
908 for (int j=i; j>off && x[j-1]>x[j]; j--)
909 swap(x, j, j-1);
910 return;
911 }
912
913 // Choose a partition element, v
914 int m = off + (len >> 1); // Small arrays, middle element
915 if (len > 7) {
916 int l = off;
917 int n = off + len - 1;
918 if (len > 40) { // Big arrays, pseudomedian of 9
919 int s = len/8;
920 l = med3(x, l, l+s, l+2*s);
921 m = med3(x, m-s, m, m+s);
922 n = med3(x, n-2*s, n-s, n);
923 }
924 m = med3(x, l, m, n); // Mid-size, med of 3
925 }
926 double v = x[m];
927
928 // Establish Invariant: v* (<v)* (>v)* v*
929 int a = off, b = a, c = off + len - 1, d = c;
930 while(true) {
931 while (b <= c && x[b] <= v) {
932 if (x[b] == v)
933 swap(x, a++, b);
934 b++;
935 }
936 while (c >= b && x[c] >= v) {
937 if (x[c] == v)
938 swap(x, c, d--);
939 c--;
940 }
941 if (b > c)
942 break;
943 swap(x, b++, c--);
944 }
945
946 // Swap partition elements back to middle
947 int s, n = off + len;
948 s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
949 s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
950
951 // Recursively sort non-partition-elements
952 if ((s = b-a) > 1)
953 sort1(x, off, s);
954 if ((s = d-c) > 1)
955 sort1(x, n-s, s);
956 }
957
958 /**
959 * Swaps x[a] with x[b].
960 */
961 private static void swap(double x[], int a, int b) {
962 double t = x[a];
963 x[a] = x[b];
964 x[b] = t;
965 }
966
967 /**
968 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
969 */
970 private static void vecswap(double x[], int a, int b, int n) {
971 for (int i=0; i<n; i++, a++, b++)
972 swap(x, a, b);
973 }
974
975 /**
976 * Returns the index of the median of the three indexed doubles.
977 */
978 private static int med3(double x[], int a, int b, int c) {
979 return (x[a] < x[b] ?
980 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
981 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
982 }
983
984
985 /**
986 * Sorts the specified sub-array of floats into ascending order.
987 */
988 private static void sort1(float x[], int off, int len) {
989 // Insertion sort on smallest arrays
990 if (len < 7) {
991 for (int i=off; i<len+off; i++)
992 for (int j=i; j>off && x[j-1]>x[j]; j--)
993 swap(x, j, j-1);
994 return;
995 }
996
997 // Choose a partition element, v
998 int m = off + (len >> 1); // Small arrays, middle element
999 if (len > 7) {
1000 int l = off;
1001 int n = off + len - 1;
1002 if (len > 40) { // Big arrays, pseudomedian of 9
1003 int s = len/8;
1004 l = med3(x, l, l+s, l+2*s);
1005 m = med3(x, m-s, m, m+s);
1006 n = med3(x, n-2*s, n-s, n);
1007 }
1008 m = med3(x, l, m, n); // Mid-size, med of 3
1009 }
1010 float v = x[m];
1011
1012 // Establish Invariant: v* (<v)* (>v)* v*
1013 int a = off, b = a, c = off + len - 1, d = c;
1014 while(true) {
1015 while (b <= c && x[b] <= v) {
1016 if (x[b] == v)
1017 swap(x, a++, b);
1018 b++;
1019 }
1020 while (c >= b && x[c] >= v) {
1021 if (x[c] == v)
1022 swap(x, c, d--);
1023 c--;
1024 }
1025 if (b > c)
1026 break;
1027 swap(x, b++, c--);
1028 }
1029
1030 // Swap partition elements back to middle
1031 int s, n = off + len;
1032 s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
1033 s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
1034
1035 // Recursively sort non-partition-elements
1036 if ((s = b-a) > 1)
1037 sort1(x, off, s);
1038 if ((s = d-c) > 1)
1039 sort1(x, n-s, s);
1040 }
1041
1042 /**
1043 * Swaps x[a] with x[b].
1044 */
1045 private static void swap(float x[], int a, int b) {
1046 float t = x[a];
1047 x[a] = x[b];
1048 x[b] = t;
1049 }
1050
1051 /**
1052 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
1053 */
1054 private static void vecswap(float x[], int a, int b, int n) {
1055 for (int i=0; i<n; i++, a++, b++)
1056 swap(x, a, b);
1057 }
1058
1059 /**
1060 * Returns the index of the median of the three indexed floats.
1061 */
1062 private static int med3(float x[], int a, int b, int c) {
1063 return (x[a] < x[b] ?
1064 (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
1065 (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
1066 }
1067
1068
1069 /**
1070 * Sorts the specified array of objects into ascending order, according to
1071 * the {@linkplain Comparable natural ordering}
1072 * of its elements. All elements in the array
1073 * must implement the {@link Comparable} interface. Furthermore, all
1074 * elements in the array must be <i>mutually comparable</i> (that is,
1075 * <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt>
1076 * for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<p>
1077 *
1078 * This sort is guaranteed to be <i>stable</i>: equal elements will
1079 * not be reordered as a result of the sort.<p>
1080 *
1081 * The sorting algorithm is a modified mergesort (in which the merge is
1082 * omitted if the highest element in the low sublist is less than the
1083 * lowest element in the high sublist). This algorithm offers guaranteed
1084 * n*log(n) performance.
1085 *
1086 * @param a the array to be sorted
1087 * @throws ClassCastException if the array contains elements that are not
1088 * <i>mutually comparable</i> (for example, strings and integers).
1089 */
1090 public static void sort(Object[] a) {
1091 Object[] aux = a.clone();
1092 mergeSort(aux, a, 0, a.length, 0);
1093 }
1094
1095 /**
1096 * Sorts the specified range of the specified array of objects into
1097 * ascending order, according to the
1098 * {@linkplain Comparable natural ordering} of its
1099 * elements. The range to be sorted extends from index
1100 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
1101 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.) All
1102 * elements in this range must implement the {@link Comparable}
1103 * interface. Furthermore, all elements in this range must be <i>mutually
1104 * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
1105 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
1106 * <tt>e2</tt> in the array).<p>
1107 *
1108 * This sort is guaranteed to be <i>stable</i>: equal elements will
1109 * not be reordered as a result of the sort.<p>
1110 *
1111 * The sorting algorithm is a modified mergesort (in which the merge is
1112 * omitted if the highest element in the low sublist is less than the
1113 * lowest element in the high sublist). This algorithm offers guaranteed
1114 * n*log(n) performance.
1115 *
1116 * @param a the array to be sorted
1117 * @param fromIndex the index of the first element (inclusive) to be
1118 * sorted
1119 * @param toIndex the index of the last element (exclusive) to be sorted
1120 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1121 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1122 * <tt>toIndex > a.length</tt>
1123 * @throws ClassCastException if the array contains elements that are
1124 * not <i>mutually comparable</i> (for example, strings and
1125 * integers).
1126 */
1127 public static void sort(Object[] a, int fromIndex, int toIndex) {
1128 rangeCheck(a.length, fromIndex, toIndex);
1129 Object[] aux = copyOfRange(a, fromIndex, toIndex);
1130 mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
1131 }
1132
1133 /**
1134 * Tuning parameter: list size at or below which insertion sort will be
1135 * used in preference to mergesort or quicksort.
1136 */
1137 private static final int INSERTIONSORT_THRESHOLD = 7;
1138
1139 /**
1140 * Src is the source array that starts at index 0
1141 * Dest is the (possibly larger) array destination with a possible offset
1142 * low is the index in dest to start sorting
1143 * high is the end index in dest to end sorting
1144 * off is the offset to generate corresponding low, high in src
1145 */
1146 private static void mergeSort(Object[] src,
1147 Object[] dest,
1148 int low,
1149 int high,
1150 int off) {
1151 int length = high - low;
1152
1153 // Insertion sort on smallest arrays
1154 if (length < INSERTIONSORT_THRESHOLD) {
1155 for (int i=low; i<high; i++)
1156 for (int j=i; j>low &&
1157 ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
1158 swap(dest, j, j-1);
1159 return;
1160 }
1161
1162 // Recursively sort halves of dest into src
1163 int destLow = low;
1164 int destHigh = high;
1165 low += off;
1166 high += off;
1167 int mid = (low + high) >>> 1;
1168 mergeSort(dest, src, low, mid, -off);
1169 mergeSort(dest, src, mid, high, -off);
1170
1171 // If list is already sorted, just copy from src to dest. This is an
1172 // optimization that results in faster sorts for nearly ordered lists.
1173 if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
1174 System.arraycopy(src, low, dest, destLow, length);
1175 return;
1176 }
1177
1178 // Merge sorted halves (now in src) into dest
1179 for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
1180 if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
1181 dest[i] = src[p++];
1182 else
1183 dest[i] = src[q++];
1184 }
1185 }
1186
1187 /**
1188 * Swaps x[a] with x[b].
1189 */
1190 private static void swap(Object[] x, int a, int b) {
1191 Object t = x[a];
1192 x[a] = x[b];
1193 x[b] = t;
1194 }
1195
1196 /**
1197 * Sorts the specified array of objects according to the order induced by
1198 * the specified comparator. All elements in the array must be
1199 * <i>mutually comparable</i> by the specified comparator (that is,
1200 * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
1201 * for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<p>
1202 *
1203 * This sort is guaranteed to be <i>stable</i>: equal elements will
1204 * not be reordered as a result of the sort.<p>
1205 *
1206 * The sorting algorithm is a modified mergesort (in which the merge is
1207 * omitted if the highest element in the low sublist is less than the
1208 * lowest element in the high sublist). This algorithm offers guaranteed
1209 * n*log(n) performance.
1210 *
1211 * @param a the array to be sorted
1212 * @param c the comparator to determine the order of the array. A
1213 * <tt>null</tt> value indicates that the elements'
1214 * {@linkplain Comparable natural ordering} should be used.
1215 * @throws ClassCastException if the array contains elements that are
1216 * not <i>mutually comparable</i> using the specified comparator.
1217 */
1218 public static <T> void sort(T[] a, Comparator<? super T> c) {
1219 T[] aux = a.clone();
1220 if (c==null)
1221 mergeSort(aux, a, 0, a.length, 0);
1222 else
1223 mergeSort(aux, a, 0, a.length, 0, c);
1224 }
1225
1226 /**
1227 * Sorts the specified range of the specified array of objects according
1228 * to the order induced by the specified comparator. The range to be
1229 * sorted extends from index <tt>fromIndex</tt>, inclusive, to index
1230 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
1231 * range to be sorted is empty.) All elements in the range must be
1232 * <i>mutually comparable</i> by the specified comparator (that is,
1233 * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
1234 * for any elements <tt>e1</tt> and <tt>e2</tt> in the range).<p>
1235 *
1236 * This sort is guaranteed to be <i>stable</i>: equal elements will
1237 * not be reordered as a result of the sort.<p>
1238 *
1239 * The sorting algorithm is a modified mergesort (in which the merge is
1240 * omitted if the highest element in the low sublist is less than the
1241 * lowest element in the high sublist). This algorithm offers guaranteed
1242 * n*log(n) performance.
1243 *
1244 * @param a the array to be sorted
1245 * @param fromIndex the index of the first element (inclusive) to be
1246 * sorted
1247 * @param toIndex the index of the last element (exclusive) to be sorted
1248 * @param c the comparator to determine the order of the array. A
1249 * <tt>null</tt> value indicates that the elements'
1250 * {@linkplain Comparable natural ordering} should be used.
1251 * @throws ClassCastException if the array contains elements that are not
1252 * <i>mutually comparable</i> using the specified comparator.
1253 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1254 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1255 * <tt>toIndex > a.length</tt>
1256 */
1257 public static <T> void sort(T[] a, int fromIndex, int toIndex,
1258 Comparator<? super T> c) {
1259 rangeCheck(a.length, fromIndex, toIndex);
1260 T[] aux = copyOfRange(a, fromIndex, toIndex);
1261 if (c==null)
1262 mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
1263 else
1264 mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
1265 }
1266
1267 /**
1268 * Src is the source array that starts at index 0
1269 * Dest is the (possibly larger) array destination with a possible offset
1270 * low is the index in dest to start sorting
1271 * high is the end index in dest to end sorting
1272 * off is the offset into src corresponding to low in dest
1273 */
1274 private static void mergeSort(Object[] src,
1275 Object[] dest,
1276 int low, int high, int off,
1277 Comparator c) {
1278 int length = high - low;
1279
1280 // Insertion sort on smallest arrays
1281 if (length < INSERTIONSORT_THRESHOLD) {
1282 for (int i=low; i<high; i++)
1283 for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
1284 swap(dest, j, j-1);
1285 return;
1286 }
1287
1288 // Recursively sort halves of dest into src
1289 int destLow = low;
1290 int destHigh = high;
1291 low += off;
1292 high += off;
1293 int mid = (low + high) >>> 1;
1294 mergeSort(dest, src, low, mid, -off, c);
1295 mergeSort(dest, src, mid, high, -off, c);
1296
1297 // If list is already sorted, just copy from src to dest. This is an
1298 // optimization that results in faster sorts for nearly ordered lists.
1299 if (c.compare(src[mid-1], src[mid]) <= 0) {
1300 System.arraycopy(src, low, dest, destLow, length);
1301 return;
1302 }
1303
1304 // Merge sorted halves (now in src) into dest
1305 for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
1306 if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
1307 dest[i] = src[p++];
1308 else
1309 dest[i] = src[q++];
1310 }
1311 }
1312
1313 /**
1314 * Check that fromIndex and toIndex are in range, and throw an
1315 * appropriate exception if they aren't.
1316 */
1317 private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {
1318 if (fromIndex > toIndex)
1319 throw new IllegalArgumentException("fromIndex(" + fromIndex +
1320 ") > toIndex(" + toIndex+")");
1321 if (fromIndex < 0)
1322 throw new ArrayIndexOutOfBoundsException(fromIndex);
1323 if (toIndex > arrayLen)
1324 throw new ArrayIndexOutOfBoundsException(toIndex);
1325 }
1326
1327 // Searching
1328
1329 /**
1330 * Searches the specified array of longs for the specified value using the
1331 * binary search algorithm. The array must be sorted (as
1332 * by the {@link #sort(long[])} method) prior to making this call. If it
1333 * is not sorted, the results are undefined. If the array contains
1334 * multiple elements with the specified value, there is no guarantee which
1335 * one will be found.
1336 *
1337 * @param a the array to be searched
1338 * @param key the value to be searched for
1339 * @return index of the search key, if it is contained in the array;
1340 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1341 * <i>insertion point</i> is defined as the point at which the
1342 * key would be inserted into the array: the index of the first
1343 * element greater than the key, or <tt>a.length</tt> if all
1344 * elements in the array are less than the specified key. Note
1345 * that this guarantees that the return value will be >= 0 if
1346 * and only if the key is found.
1347 */
1348 public static int binarySearch(long[] a, long key) {
1349 return binarySearch0(a, 0, a.length, key);
1350 }
1351
1352 /**
1353 * Searches a range of
1354 * the specified array of longs for the specified value using the
1355 * binary search algorithm.
1356 * The range must be sorted (as
1357 * by the {@link #sort(long[], int, int)} method)
1358 * prior to making this call. If it
1359 * is not sorted, the results are undefined. If the range contains
1360 * multiple elements with the specified value, there is no guarantee which
1361 * one will be found.
1362 *
1363 * @param a the array to be searched
1364 * @param fromIndex the index of the first element (inclusive) to be
1365 * searched
1366 * @param toIndex the index of the last element (exclusive) to be searched
1367 * @param key the value to be searched for
1368 * @return index of the search key, if it is contained in the array
1369 * within the specified range;
1370 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1371 * <i>insertion point</i> is defined as the point at which the
1372 * key would be inserted into the array: the index of the first
1373 * element in the range greater than the key,
1374 * or <tt>toIndex</tt> if all
1375 * elements in the range are less than the specified key. Note
1376 * that this guarantees that the return value will be >= 0 if
1377 * and only if the key is found.
1378 * @throws IllegalArgumentException
1379 * if {@code fromIndex > toIndex}
1380 * @throws ArrayIndexOutOfBoundsException
1381 * if {@code fromIndex < 0 or toIndex > a.length}
1382 * @since 1.6
1383 */
1384 public static int binarySearch(long[] a, int fromIndex, int toIndex,
1385 long key) {
1386 rangeCheck(a.length, fromIndex, toIndex);
1387 return binarySearch0(a, fromIndex, toIndex, key);
1388 }
1389
1390 // Like public version, but without range checks.
1391 private static int binarySearch0(long[] a, int fromIndex, int toIndex,
1392 long key) {
1393 int low = fromIndex;
1394 int high = toIndex - 1;
1395
1396 while (low <= high) {
1397 int mid = (low + high) >>> 1;
1398 long midVal = a[mid];
1399
1400 if (midVal < key)
1401 low = mid + 1;
1402 else if (midVal > key)
1403 high = mid - 1;
1404 else
1405 return mid; // key found
1406 }
1407 return -(low + 1); // key not found.
1408 }
1409
1410 /**
1411 * Searches the specified array of ints for the specified value using the
1412 * binary search algorithm. The array must be sorted (as
1413 * by the {@link #sort(int[])} method) prior to making this call. If it
1414 * is not sorted, the results are undefined. If the array contains
1415 * multiple elements with the specified value, there is no guarantee which
1416 * one will be found.
1417 *
1418 * @param a the array to be searched
1419 * @param key the value to be searched for
1420 * @return index of the search key, if it is contained in the array;
1421 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1422 * <i>insertion point</i> is defined as the point at which the
1423 * key would be inserted into the array: the index of the first
1424 * element greater than the key, or <tt>a.length</tt> if all
1425 * elements in the array are less than the specified key. Note
1426 * that this guarantees that the return value will be >= 0 if
1427 * and only if the key is found.
1428 */
1429 public static int binarySearch(int[] a, int key) {
1430 return binarySearch0(a, 0, a.length, key);
1431 }
1432
1433 /**
1434 * Searches a range of
1435 * the specified array of ints for the specified value using the
1436 * binary search algorithm.
1437 * The range must be sorted (as
1438 * by the {@link #sort(int[], int, int)} method)
1439 * prior to making this call. If it
1440 * is not sorted, the results are undefined. If the range contains
1441 * multiple elements with the specified value, there is no guarantee which
1442 * one will be found.
1443 *
1444 * @param a the array to be searched
1445 * @param fromIndex the index of the first element (inclusive) to be
1446 * searched
1447 * @param toIndex the index of the last element (exclusive) to be searched
1448 * @param key the value to be searched for
1449 * @return index of the search key, if it is contained in the array
1450 * within the specified range;
1451 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1452 * <i>insertion point</i> is defined as the point at which the
1453 * key would be inserted into the array: the index of the first
1454 * element in the range greater than the key,
1455 * or <tt>toIndex</tt> if all
1456 * elements in the range are less than the specified key. Note
1457 * that this guarantees that the return value will be >= 0 if
1458 * and only if the key is found.
1459 * @throws IllegalArgumentException
1460 * if {@code fromIndex > toIndex}
1461 * @throws ArrayIndexOutOfBoundsException
1462 * if {@code fromIndex < 0 or toIndex > a.length}
1463 * @since 1.6
1464 */
1465 public static int binarySearch(int[] a, int fromIndex, int toIndex,
1466 int key) {
1467 rangeCheck(a.length, fromIndex, toIndex);
1468 return binarySearch0(a, fromIndex, toIndex, key);
1469 }
1470
1471 // Like public version, but without range checks.
1472 private static int binarySearch0(int[] a, int fromIndex, int toIndex,
1473 int key) {
1474 int low = fromIndex;
1475 int high = toIndex - 1;
1476
1477 while (low <= high) {
1478 int mid = (low + high) >>> 1;
1479 int midVal = a[mid];
1480
1481 if (midVal < key)
1482 low = mid + 1;
1483 else if (midVal > key)
1484 high = mid - 1;
1485 else
1486 return mid; // key found
1487 }
1488 return -(low + 1); // key not found.
1489 }
1490
1491 /**
1492 * Searches the specified array of shorts for the specified value using
1493 * the binary search algorithm. The array must be sorted
1494 * (as by the {@link #sort(short[])} method) prior to making this call. If
1495 * it is not sorted, the results are undefined. If the array contains
1496 * multiple elements with the specified value, there is no guarantee which
1497 * one will be found.
1498 *
1499 * @param a the array to be searched
1500 * @param key the value to be searched for
1501 * @return index of the search key, if it is contained in the array;
1502 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1503 * <i>insertion point</i> is defined as the point at which the
1504 * key would be inserted into the array: the index of the first
1505 * element greater than the key, or <tt>a.length</tt> if all
1506 * elements in the array are less than the specified key. Note
1507 * that this guarantees that the return value will be >= 0 if
1508 * and only if the key is found.
1509 */
1510 public static int binarySearch(short[] a, short key) {
1511 return binarySearch0(a, 0, a.length, key);
1512 }
1513
1514 /**
1515 * Searches a range of
1516 * the specified array of shorts for the specified value using
1517 * the binary search algorithm.
1518 * The range must be sorted
1519 * (as by the {@link #sort(short[], int, int)} method)
1520 * prior to making this call. If
1521 * it is not sorted, the results are undefined. If the range contains
1522 * multiple elements with the specified value, there is no guarantee which
1523 * one will be found.
1524 *
1525 * @param a the array to be searched
1526 * @param fromIndex the index of the first element (inclusive) to be
1527 * searched
1528 * @param toIndex the index of the last element (exclusive) to be searched
1529 * @param key the value to be searched for
1530 * @return index of the search key, if it is contained in the array
1531 * within the specified range;
1532 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1533 * <i>insertion point</i> is defined as the point at which the
1534 * key would be inserted into the array: the index of the first
1535 * element in the range greater than the key,
1536 * or <tt>toIndex</tt> if all
1537 * elements in the range are less than the specified key. Note
1538 * that this guarantees that the return value will be >= 0 if
1539 * and only if the key is found.
1540 * @throws IllegalArgumentException
1541 * if {@code fromIndex > toIndex}
1542 * @throws ArrayIndexOutOfBoundsException
1543 * if {@code fromIndex < 0 or toIndex > a.length}
1544 * @since 1.6
1545 */
1546 public static int binarySearch(short[] a, int fromIndex, int toIndex,
1547 short key) {
1548 rangeCheck(a.length, fromIndex, toIndex);
1549 return binarySearch0(a, fromIndex, toIndex, key);
1550 }
1551
1552 // Like public version, but without range checks.
1553 private static int binarySearch0(short[] a, int fromIndex, int toIndex,
1554 short key) {
1555 int low = fromIndex;
1556 int high = toIndex - 1;
1557
1558 while (low <= high) {
1559 int mid = (low + high) >>> 1;
1560 short midVal = a[mid];
1561
1562 if (midVal < key)
1563 low = mid + 1;
1564 else if (midVal > key)
1565 high = mid - 1;
1566 else
1567 return mid; // key found
1568 }
1569 return -(low + 1); // key not found.
1570 }
1571
1572 /**
1573 * Searches the specified array of chars for the specified value using the
1574 * binary search algorithm. The array must be sorted (as
1575 * by the {@link #sort(char[])} method) prior to making this call. If it
1576 * is not sorted, the results are undefined. If the array contains
1577 * multiple elements with the specified value, there is no guarantee which
1578 * one will be found.
1579 *
1580 * @param a the array to be searched
1581 * @param key the value to be searched for
1582 * @return index of the search key, if it is contained in the array;
1583 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1584 * <i>insertion point</i> is defined as the point at which the
1585 * key would be inserted into the array: the index of the first
1586 * element greater than the key, or <tt>a.length</tt> if all
1587 * elements in the array are less than the specified key. Note
1588 * that this guarantees that the return value will be >= 0 if
1589 * and only if the key is found.
1590 */
1591 public static int binarySearch(char[] a, char key) {
1592 return binarySearch0(a, 0, a.length, key);
1593 }
1594
1595 /**
1596 * Searches a range of
1597 * the specified array of chars for the specified value using the
1598 * binary search algorithm.
1599 * The range must be sorted (as
1600 * by the {@link #sort(char[], int, int)} method)
1601 * prior to making this call. If it
1602 * is not sorted, the results are undefined. If the range contains
1603 * multiple elements with the specified value, there is no guarantee which
1604 * one will be found.
1605 *
1606 * @param a the array to be searched
1607 * @param fromIndex the index of the first element (inclusive) to be
1608 * searched
1609 * @param toIndex the index of the last element (exclusive) to be searched
1610 * @param key the value to be searched for
1611 * @return index of the search key, if it is contained in the array
1612 * within the specified range;
1613 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1614 * <i>insertion point</i> is defined as the point at which the
1615 * key would be inserted into the array: the index of the first
1616 * element in the range greater than the key,
1617 * or <tt>toIndex</tt> if all
1618 * elements in the range are less than the specified key. Note
1619 * that this guarantees that the return value will be >= 0 if
1620 * and only if the key is found.
1621 * @throws IllegalArgumentException
1622 * if {@code fromIndex > toIndex}
1623 * @throws ArrayIndexOutOfBoundsException
1624 * if {@code fromIndex < 0 or toIndex > a.length}
1625 * @since 1.6
1626 */
1627 public static int binarySearch(char[] a, int fromIndex, int toIndex,
1628 char key) {
1629 rangeCheck(a.length, fromIndex, toIndex);
1630 return binarySearch0(a, fromIndex, toIndex, key);
1631 }
1632
1633 // Like public version, but without range checks.
1634 private static int binarySearch0(char[] a, int fromIndex, int toIndex,
1635 char key) {
1636 int low = fromIndex;
1637 int high = toIndex - 1;
1638
1639 while (low <= high) {
1640 int mid = (low + high) >>> 1;
1641 char midVal = a[mid];
1642
1643 if (midVal < key)
1644 low = mid + 1;
1645 else if (midVal > key)
1646 high = mid - 1;
1647 else
1648 return mid; // key found
1649 }
1650 return -(low + 1); // key not found.
1651 }
1652
1653 /**
1654 * Searches the specified array of bytes for the specified value using the
1655 * binary search algorithm. The array must be sorted (as
1656 * by the {@link #sort(byte[])} method) prior to making this call. If it
1657 * is not sorted, the results are undefined. If the array contains
1658 * multiple elements with the specified value, there is no guarantee which
1659 * one will be found.
1660 *
1661 * @param a the array to be searched
1662 * @param key the value to be searched for
1663 * @return index of the search key, if it is contained in the array;
1664 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1665 * <i>insertion point</i> is defined as the point at which the
1666 * key would be inserted into the array: the index of the first
1667 * element greater than the key, or <tt>a.length</tt> if all
1668 * elements in the array are less than the specified key. Note
1669 * that this guarantees that the return value will be >= 0 if
1670 * and only if the key is found.
1671 */
1672 public static int binarySearch(byte[] a, byte key) {
1673 return binarySearch0(a, 0, a.length, key);
1674 }
1675
1676 /**
1677 * Searches a range of
1678 * the specified array of bytes for the specified value using the
1679 * binary search algorithm.
1680 * The range must be sorted (as
1681 * by the {@link #sort(byte[], int, int)} method)
1682 * prior to making this call. If it
1683 * is not sorted, the results are undefined. If the range contains
1684 * multiple elements with the specified value, there is no guarantee which
1685 * one will be found.
1686 *
1687 * @param a the array to be searched
1688 * @param fromIndex the index of the first element (inclusive) to be
1689 * searched
1690 * @param toIndex the index of the last element (exclusive) to be searched
1691 * @param key the value to be searched for
1692 * @return index of the search key, if it is contained in the array
1693 * within the specified range;
1694 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1695 * <i>insertion point</i> is defined as the point at which the
1696 * key would be inserted into the array: the index of the first
1697 * element in the range greater than the key,
1698 * or <tt>toIndex</tt> if all
1699 * elements in the range are less than the specified key. Note
1700 * that this guarantees that the return value will be >= 0 if
1701 * and only if the key is found.
1702 * @throws IllegalArgumentException
1703 * if {@code fromIndex > toIndex}
1704 * @throws ArrayIndexOutOfBoundsException
1705 * if {@code fromIndex < 0 or toIndex > a.length}
1706 * @since 1.6
1707 */
1708 public static int binarySearch(byte[] a, int fromIndex, int toIndex,
1709 byte key) {
1710 rangeCheck(a.length, fromIndex, toIndex);
1711 return binarySearch0(a, fromIndex, toIndex, key);
1712 }
1713
1714 // Like public version, but without range checks.
1715 private static int binarySearch0(byte[] a, int fromIndex, int toIndex,
1716 byte key) {
1717 int low = fromIndex;
1718 int high = toIndex - 1;
1719
1720 while (low <= high) {
1721 int mid = (low + high) >>> 1;
1722 byte midVal = a[mid];
1723
1724 if (midVal < key)
1725 low = mid + 1;
1726 else if (midVal > key)
1727 high = mid - 1;
1728 else
1729 return mid; // key found
1730 }
1731 return -(low + 1); // key not found.
1732 }
1733
1734 /**
1735 * Searches the specified array of doubles for the specified value using
1736 * the binary search algorithm. The array must be sorted
1737 * (as by the {@link #sort(double[])} method) prior to making this call.
1738 * If it is not sorted, the results are undefined. If the array contains
1739 * multiple elements with the specified value, there is no guarantee which
1740 * one will be found. This method considers all NaN values to be
1741 * equivalent and equal.
1742 *
1743 * @param a the array to be searched
1744 * @param key the value to be searched for
1745 * @return index of the search key, if it is contained in the array;
1746 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1747 * <i>insertion point</i> is defined as the point at which the
1748 * key would be inserted into the array: the index of the first
1749 * element greater than the key, or <tt>a.length</tt> if all
1750 * elements in the array are less than the specified key. Note
1751 * that this guarantees that the return value will be >= 0 if
1752 * and only if the key is found.
1753 */
1754 public static int binarySearch(double[] a, double key) {
1755 return binarySearch0(a, 0, a.length, key);
1756 }
1757
1758 /**
1759 * Searches a range of
1760 * the specified array of doubles for the specified value using
1761 * the binary search algorithm.
1762 * The range must be sorted
1763 * (as by the {@link #sort(double[], int, int)} method)
1764 * prior to making this call.
1765 * If it is not sorted, the results are undefined. If the range contains
1766 * multiple elements with the specified value, there is no guarantee which
1767 * one will be found. This method considers all NaN values to be
1768 * equivalent and equal.
1769 *
1770 * @param a the array to be searched
1771 * @param fromIndex the index of the first element (inclusive) to be
1772 * searched
1773 * @param toIndex the index of the last element (exclusive) to be searched
1774 * @param key the value to be searched for
1775 * @return index of the search key, if it is contained in the array
1776 * within the specified range;
1777 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1778 * <i>insertion point</i> is defined as the point at which the
1779 * key would be inserted into the array: the index of the first
1780 * element in the range greater than the key,
1781 * or <tt>toIndex</tt> if all
1782 * elements in the range are less than the specified key. Note
1783 * that this guarantees that the return value will be >= 0 if
1784 * and only if the key is found.
1785 * @throws IllegalArgumentException
1786 * if {@code fromIndex > toIndex}
1787 * @throws ArrayIndexOutOfBoundsException
1788 * if {@code fromIndex < 0 or toIndex > a.length}
1789 * @since 1.6
1790 */
1791 public static int binarySearch(double[] a, int fromIndex, int toIndex,
1792 double key) {
1793 rangeCheck(a.length, fromIndex, toIndex);
1794 return binarySearch0(a, fromIndex, toIndex, key);
1795 }
1796
1797 // Like public version, but without range checks.
1798 private static int binarySearch0(double[] a, int fromIndex, int toIndex,
1799 double key) {
1800 int low = fromIndex;
1801 int high = toIndex - 1;
1802
1803 while (low <= high) {
1804 int mid = (low + high) >>> 1;
1805 double midVal = a[mid];
1806
1807 if (midVal < key)
1808 low = mid + 1; // Neither val is NaN, thisVal is smaller
1809 else if (midVal > key)
1810 high = mid - 1; // Neither val is NaN, thisVal is larger
1811 else {
1812 long midBits = Double.doubleToLongBits(midVal);
1813 long keyBits = Double.doubleToLongBits(key);
1814 if (midBits == keyBits) // Values are equal
1815 return mid; // Key found
1816 else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
1817 low = mid + 1;
1818 else // (0.0, -0.0) or (NaN, !NaN)
1819 high = mid - 1;
1820 }
1821 }
1822 return -(low + 1); // key not found.
1823 }
1824
1825 /**
1826 * Searches the specified array of floats for the specified value using
1827 * the binary search algorithm. The array must be sorted
1828 * (as by the {@link #sort(float[])} method) prior to making this call. If
1829 * it is not sorted, the results are undefined. If the array contains
1830 * multiple elements with the specified value, there is no guarantee which
1831 * one will be found. This method considers all NaN values to be
1832 * equivalent and equal.
1833 *
1834 * @param a the array to be searched
1835 * @param key the value to be searched for
1836 * @return index of the search key, if it is contained in the array;
1837 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1838 * <i>insertion point</i> is defined as the point at which the
1839 * key would be inserted into the array: the index of the first
1840 * element greater than the key, or <tt>a.length</tt> if all
1841 * elements in the array are less than the specified key. Note
1842 * that this guarantees that the return value will be >= 0 if
1843 * and only if the key is found.
1844 */
1845 public static int binarySearch(float[] a, float key) {
1846 return binarySearch0(a, 0, a.length, key);
1847 }
1848
1849 /**
1850 * Searches a range of
1851 * the specified array of floats for the specified value using
1852 * the binary search algorithm.
1853 * The range must be sorted
1854 * (as by the {@link #sort(float[], int, int)} method)
1855 * prior to making this call. If
1856 * it is not sorted, the results are undefined. If the range contains
1857 * multiple elements with the specified value, there is no guarantee which
1858 * one will be found. This method considers all NaN values to be
1859 * equivalent and equal.
1860 *
1861 * @param a the array to be searched
1862 * @param fromIndex the index of the first element (inclusive) to be
1863 * searched
1864 * @param toIndex the index of the last element (exclusive) to be searched
1865 * @param key the value to be searched for
1866 * @return index of the search key, if it is contained in the array
1867 * within the specified range;
1868 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1869 * <i>insertion point</i> is defined as the point at which the
1870 * key would be inserted into the array: the index of the first
1871 * element in the range greater than the key,
1872 * or <tt>toIndex</tt> if all
1873 * elements in the range are less than the specified key. Note
1874 * that this guarantees that the return value will be >= 0 if
1875 * and only if the key is found.
1876 * @throws IllegalArgumentException
1877 * if {@code fromIndex > toIndex}
1878 * @throws ArrayIndexOutOfBoundsException
1879 * if {@code fromIndex < 0 or toIndex > a.length}
1880 * @since 1.6
1881 */
1882 public static int binarySearch(float[] a, int fromIndex, int toIndex,
1883 float key) {
1884 rangeCheck(a.length, fromIndex, toIndex);
1885 return binarySearch0(a, fromIndex, toIndex, key);
1886 }
1887
1888 // Like public version, but without range checks.
1889 private static int binarySearch0(float[] a, int fromIndex, int toIndex,
1890 float key) {
1891 int low = fromIndex;
1892 int high = toIndex - 1;
1893
1894 while (low <= high) {
1895 int mid = (low + high) >>> 1;
1896 float midVal = a[mid];
1897
1898 if (midVal < key)
1899 low = mid + 1; // Neither val is NaN, thisVal is smaller
1900 else if (midVal > key)
1901 high = mid - 1; // Neither val is NaN, thisVal is larger
1902 else {
1903 int midBits = Float.floatToIntBits(midVal);
1904 int keyBits = Float.floatToIntBits(key);
1905 if (midBits == keyBits) // Values are equal
1906 return mid; // Key found
1907 else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
1908 low = mid + 1;
1909 else // (0.0, -0.0) or (NaN, !NaN)
1910 high = mid - 1;
1911 }
1912 }
1913 return -(low + 1); // key not found.
1914 }
1915
1916
1917 /**
1918 * Searches the specified array for the specified object using the binary
1919 * search algorithm. The array must be sorted into ascending order
1920 * according to the
1921 * {@linkplain Comparable natural ordering}
1922 * of its elements (as by the
1923 * {@link #sort(Object[])} method) prior to making this call.
1924 * If it is not sorted, the results are undefined.
1925 * (If the array contains elements that are not mutually comparable (for
1926 * example, strings and integers), it <i>cannot</i> be sorted according
1927 * to the natural ordering of its elements, hence results are undefined.)
1928 * If the array contains multiple
1929 * elements equal to the specified object, there is no guarantee which
1930 * one will be found.
1931 *
1932 * @param a the array to be searched
1933 * @param key the value to be searched for
1934 * @return index of the search key, if it is contained in the array;
1935 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1936 * <i>insertion point</i> is defined as the point at which the
1937 * key would be inserted into the array: the index of the first
1938 * element greater than the key, or <tt>a.length</tt> if all
1939 * elements in the array are less than the specified key. Note
1940 * that this guarantees that the return value will be >= 0 if
1941 * and only if the key is found.
1942 * @throws ClassCastException if the search key is not comparable to the
1943 * elements of the array.
1944 */
1945 public static int binarySearch(Object[] a, Object key) {
1946 return binarySearch0(a, 0, a.length, key);
1947 }
1948
1949 /**
1950 * Searches a range of
1951 * the specified array for the specified object using the binary
1952 * search algorithm.
1953 * The range must be sorted into ascending order
1954 * according to the
1955 * {@linkplain Comparable natural ordering}
1956 * of its elements (as by the
1957 * {@link #sort(Object[], int, int)} method) prior to making this
1958 * call. If it is not sorted, the results are undefined.
1959 * (If the range contains elements that are not mutually comparable (for
1960 * example, strings and integers), it <i>cannot</i> be sorted according
1961 * to the natural ordering of its elements, hence results are undefined.)
1962 * If the range contains multiple
1963 * elements equal to the specified object, there is no guarantee which
1964 * one will be found.
1965 *
1966 * @param a the array to be searched
1967 * @param fromIndex the index of the first element (inclusive) to be
1968 * searched
1969 * @param toIndex the index of the last element (exclusive) to be searched
1970 * @param key the value to be searched for
1971 * @return index of the search key, if it is contained in the array
1972 * within the specified range;
1973 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1974 * <i>insertion point</i> is defined as the point at which the
1975 * key would be inserted into the array: the index of the first
1976 * element in the range greater than the key,
1977 * or <tt>toIndex</tt> if all
1978 * elements in the range are less than the specified key. Note
1979 * that this guarantees that the return value will be >= 0 if
1980 * and only if the key is found.
1981 * @throws ClassCastException if the search key is not comparable to the
1982 * elements of the array within the specified range.
1983 * @throws IllegalArgumentException
1984 * if {@code fromIndex > toIndex}
1985 * @throws ArrayIndexOutOfBoundsException
1986 * if {@code fromIndex < 0 or toIndex > a.length}
1987 * @since 1.6
1988 */
1989 public static int binarySearch(Object[] a, int fromIndex, int toIndex,
1990 Object key) {
1991 rangeCheck(a.length, fromIndex, toIndex);
1992 return binarySearch0(a, fromIndex, toIndex, key);
1993 }
1994
1995 // Like public version, but without range checks.
1996 private static int binarySearch0(Object[] a, int fromIndex, int toIndex,
1997 Object key) {
1998 int low = fromIndex;
1999 int high = toIndex - 1;
2000
2001 while (low <= high) {
2002 int mid = (low + high) >>> 1;
2003 Comparable midVal = (Comparable)a[mid];
2004 int cmp = midVal.compareTo(key);
2005
2006 if (cmp < 0)
2007 low = mid + 1;
2008 else if (cmp > 0)
2009 high = mid - 1;
2010 else
2011 return mid; // key found
2012 }
2013 return -(low + 1); // key not found.
2014 }
2015
2016 /**
2017 * Searches the specified array for the specified object using the binary
2018 * search algorithm. The array must be sorted into ascending order
2019 * according to the specified comparator (as by the
2020 * {@link #sort(Object[], Comparator) sort(T[], Comparator)}
2021 * method) prior to making this call. If it is
2022 * not sorted, the results are undefined.
2023 * If the array contains multiple
2024 * elements equal to the specified object, there is no guarantee which one
2025 * will be found.
2026 *
2027 * @param a the array to be searched
2028 * @param key the value to be searched for
2029 * @param c the comparator by which the array is ordered. A
2030 * <tt>null</tt> value indicates that the elements'
2031 * {@linkplain Comparable natural ordering} should be used.
2032 * @return index of the search key, if it is contained in the array;
2033 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
2034 * <i>insertion point</i> is defined as the point at which the
2035 * key would be inserted into the array: the index of the first
2036 * element greater than the key, or <tt>a.length</tt> if all
2037 * elements in the array are less than the specified key. Note
2038 * that this guarantees that the return value will be >= 0 if
2039 * and only if the key is found.
2040 * @throws ClassCastException if the array contains elements that are not
2041 * <i>mutually comparable</i> using the specified comparator,
2042 * or the search key is not comparable to the
2043 * elements of the array using this comparator.
2044 */
2045 public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) {
2046 return binarySearch0(a, 0, a.length, key, c);
2047 }
2048
2049 /**
2050 * Searches a range of
2051 * the specified array for the specified object using the binary
2052 * search algorithm.
2053 * The range must be sorted into ascending order
2054 * according to the specified comparator (as by the
2055 * {@link #sort(Object[], int, int, Comparator)
2056 * sort(T[], int, int, Comparator)}
2057 * method) prior to making this call.
2058 * If it is not sorted, the results are undefined.
2059 * If the range contains multiple elements equal to the specified object,
2060 * there is no guarantee which one will be found.
2061 *
2062 * @param a the array to be searched
2063 * @param fromIndex the index of the first element (inclusive) to be
2064 * searched
2065 * @param toIndex the index of the last element (exclusive) to be searched
2066 * @param key the value to be searched for
2067 * @param c the comparator by which the array is ordered. A
2068 * <tt>null</tt> value indicates that the elements'
2069 * {@linkplain Comparable natural ordering} should be used.
2070 * @return index of the search key, if it is contained in the array
2071 * within the specified range;
2072 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
2073 * <i>insertion point</i> is defined as the point at which the
2074 * key would be inserted into the array: the index of the first
2075 * element in the range greater than the key,
2076 * or <tt>toIndex</tt> if all
2077 * elements in the range are less than the specified key. Note
2078 * that this guarantees that the return value will be >= 0 if
2079 * and only if the key is found.
2080 * @throws ClassCastException if the range contains elements that are not
2081 * <i>mutually comparable</i> using the specified comparator,
2082 * or the search key is not comparable to the
2083 * elements in the range using this comparator.
2084 * @throws IllegalArgumentException
2085 * if {@code fromIndex > toIndex}
2086 * @throws ArrayIndexOutOfBoundsException
2087 * if {@code fromIndex < 0 or toIndex > a.length}
2088 * @since 1.6
2089 */
2090 public static <T> int binarySearch(T[] a, int fromIndex, int toIndex,
2091 T key, Comparator<? super T> c) {
2092 rangeCheck(a.length, fromIndex, toIndex);
2093 return binarySearch0(a, fromIndex, toIndex, key, c);
2094 }
2095
2096 // Like public version, but without range checks.
2097 private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex,
2098 T key, Comparator<? super T> c) {
2099 if (c == null) {
2100 return binarySearch0(a, fromIndex, toIndex, key);
2101 }
2102 int low = fromIndex;
2103 int high = toIndex - 1;
2104
2105 while (low <= high) {
2106 int mid = (low + high) >>> 1;
2107 T midVal = a[mid];
2108 int cmp = c.compare(midVal, key);
2109
2110 if (cmp < 0)
2111 low = mid + 1;
2112 else if (cmp > 0)
2113 high = mid - 1;
2114 else
2115 return mid; // key found
2116 }
2117 return -(low + 1); // key not found.
2118 }
2119
2120
2121 // Equality Testing
2122
2123 /**
2124 * Returns <tt>true</tt> if the two specified arrays of longs are
2125 * <i>equal</i> to one another. Two arrays are considered equal if both
2126 * arrays contain the same number of elements, and all corresponding pairs
2127 * of elements in the two arrays are equal. In other words, two arrays
2128 * are equal if they contain the same elements in the same order. Also,
2129 * two array references are considered equal if both are <tt>null</tt>.<p>
2130 *
2131 * @param a one array to be tested for equality
2132 * @param a2 the other array to be tested for equality
2133 * @return <tt>true</tt> if the two arrays are equal
2134 */
2135 public static boolean equals(long[] a, long[] a2) {
2136 if (a==a2)
2137 return true;
2138 if (a==null || a2==null)
2139 return false;
2140
2141 int length = a.length;
2142 if (a2.length != length)
2143 return false;
2144
2145 for (int i=0; i<length; i++)
2146 if (a[i] != a2[i])
2147 return false;
2148
2149 return true;
2150 }
2151
2152 /**
2153 * Returns <tt>true</tt> if the two specified arrays of ints are
2154 * <i>equal</i> to one another. Two arrays are considered equal if both
2155 * arrays contain the same number of elements, and all corresponding pairs
2156 * of elements in the two arrays are equal. In other words, two arrays
2157 * are equal if they contain the same elements in the same order. Also,
2158 * two array references are considered equal if both are <tt>null</tt>.<p>
2159 *
2160 * @param a one array to be tested for equality
2161 * @param a2 the other array to be tested for equality
2162 * @return <tt>true</tt> if the two arrays are equal
2163 */
2164 public static boolean equals(int[] a, int[] a2) {
2165 if (a==a2)
2166 return true;
2167 if (a==null || a2==null)
2168 return false;
2169
2170 int length = a.length;
2171 if (a2.length != length)
2172 return false;
2173
2174 for (int i=0; i<length; i++)
2175 if (a[i] != a2[i])
2176 return false;
2177
2178 return true;
2179 }
2180
2181 /**
2182 * Returns <tt>true</tt> if the two specified arrays of shorts are
2183 * <i>equal</i> to one another. Two arrays are considered equal if both
2184 * arrays contain the same number of elements, and all corresponding pairs
2185 * of elements in the two arrays are equal. In other words, two arrays
2186 * are equal if they contain the same elements in the same order. Also,
2187 * two array references are considered equal if both are <tt>null</tt>.<p>
2188 *
2189 * @param a one array to be tested for equality
2190 * @param a2 the other array to be tested for equality
2191 * @return <tt>true</tt> if the two arrays are equal
2192 */
2193 public static boolean equals(short[] a, short a2[]) {
2194 if (a==a2)
2195 return true;
2196 if (a==null || a2==null)
2197 return false;
2198
2199 int length = a.length;
2200 if (a2.length != length)
2201 return false;
2202
2203 for (int i=0; i<length; i++)
2204 if (a[i] != a2[i])
2205 return false;
2206
2207 return true;
2208 }
2209
2210 /**
2211 * Returns <tt>true</tt> if the two specified arrays of chars are
2212 * <i>equal</i> to one another. Two arrays are considered equal if both
2213 * arrays contain the same number of elements, and all corresponding pairs
2214 * of elements in the two arrays are equal. In other words, two arrays
2215 * are equal if they contain the same elements in the same order. Also,
2216 * two array references are considered equal if both are <tt>null</tt>.<p>
2217 *
2218 * @param a one array to be tested for equality
2219 * @param a2 the other array to be tested for equality
2220 * @return <tt>true</tt> if the two arrays are equal
2221 */
2222 public static boolean equals(char[] a, char[] a2) {
2223 if (a==a2)
2224 return true;
2225 if (a==null || a2==null)
2226 return false;
2227
2228 int length = a.length;
2229 if (a2.length != length)
2230 return false;
2231
2232 for (int i=0; i<length; i++)
2233 if (a[i] != a2[i])
2234 return false;
2235
2236 return true;
2237 }
2238
2239 /**
2240 * Returns <tt>true</tt> if the two specified arrays of bytes are
2241 * <i>equal</i> to one another. Two arrays are considered equal if both
2242 * arrays contain the same number of elements, and all corresponding pairs
2243 * of elements in the two arrays are equal. In other words, two arrays
2244 * are equal if they contain the same elements in the same order. Also,
2245 * two array references are considered equal if both are <tt>null</tt>.<p>
2246 *
2247 * @param a one array to be tested for equality
2248 * @param a2 the other array to be tested for equality
2249 * @return <tt>true</tt> if the two arrays are equal
2250 */
2251 public static boolean equals(byte[] a, byte[] a2) {
2252 if (a==a2)
2253 return true;
2254 if (a==null || a2==null)
2255 return false;
2256
2257 int length = a.length;
2258 if (a2.length != length)
2259 return false;
2260
2261 for (int i=0; i<length; i++)
2262 if (a[i] != a2[i])
2263 return false;
2264
2265 return true;
2266 }
2267
2268 /**
2269 * Returns <tt>true</tt> if the two specified arrays of booleans are
2270 * <i>equal</i> to one another. Two arrays are considered equal if both
2271 * arrays contain the same number of elements, and all corresponding pairs
2272 * of elements in the two arrays are equal. In other words, two arrays
2273 * are equal if they contain the same elements in the same order. Also,
2274 * two array references are considered equal if both are <tt>null</tt>.<p>
2275 *
2276 * @param a one array to be tested for equality
2277 * @param a2 the other array to be tested for equality
2278 * @return <tt>true</tt> if the two arrays are equal
2279 */
2280 public static boolean equals(boolean[] a, boolean[] a2) {
2281 if (a==a2)
2282 return true;
2283 if (a==null || a2==null)
2284 return false;
2285
2286 int length = a.length;
2287 if (a2.length != length)
2288 return false;
2289
2290 for (int i=0; i<length; i++)
2291 if (a[i] != a2[i])
2292 return false;
2293
2294 return true;
2295 }
2296
2297 /**
2298 * Returns <tt>true</tt> if the two specified arrays of doubles are
2299 * <i>equal</i> to one another. Two arrays are considered equal if both
2300 * arrays contain the same number of elements, and all corresponding pairs
2301 * of elements in the two arrays are equal. In other words, two arrays
2302 * are equal if they contain the same elements in the same order. Also,
2303 * two array references are considered equal if both are <tt>null</tt>.<p>
2304 *
2305 * Two doubles <tt>d1</tt> and <tt>d2</tt> are considered equal if:
2306 * <pre> <tt>new Double(d1).equals(new Double(d2))</tt></pre>
2307 * (Unlike the <tt>==</tt> operator, this method considers
2308 * <tt>NaN</tt> equals to itself, and 0.0d unequal to -0.0d.)
2309 *
2310 * @param a one array to be tested for equality
2311 * @param a2 the other array to be tested for equality
2312 * @return <tt>true</tt> if the two arrays are equal
2313 * @see Double#equals(Object)
2314 */
2315 public static boolean equals(double[] a, double[] a2) {
2316 if (a==a2)
2317 return true;
2318 if (a==null || a2==null)
2319 return false;
2320
2321 int length = a.length;
2322 if (a2.length != length)
2323 return false;
2324
2325 for (int i=0; i<length; i++)
2326 if (Double.doubleToLongBits(a[i])!=Double.doubleToLongBits(a2[i]))
2327 return false;
2328
2329 return true;
2330 }
2331
2332 /**
2333 * Returns <tt>true</tt> if the two specified arrays of floats are
2334 * <i>equal</i> to one another. Two arrays are considered equal if both
2335 * arrays contain the same number of elements, and all corresponding pairs
2336 * of elements in the two arrays are equal. In other words, two arrays
2337 * are equal if they contain the same elements in the same order. Also,
2338 * two array references are considered equal if both are <tt>null</tt>.<p>
2339 *
2340 * Two floats <tt>f1</tt> and <tt>f2</tt> are considered equal if:
2341 * <pre> <tt>new Float(f1).equals(new Float(f2))</tt></pre>
2342 * (Unlike the <tt>==</tt> operator, this method considers
2343 * <tt>NaN</tt> equals to itself, and 0.0f unequal to -0.0f.)
2344 *
2345 * @param a one array to be tested for equality
2346 * @param a2 the other array to be tested for equality
2347 * @return <tt>true</tt> if the two arrays are equal
2348 * @see Float#equals(Object)
2349 */
2350 public static boolean equals(float[] a, float[] a2) {
2351 if (a==a2)
2352 return true;
2353 if (a==null || a2==null)
2354 return false;
2355
2356 int length = a.length;
2357 if (a2.length != length)
2358 return false;
2359
2360 for (int i=0; i<length; i++)
2361 if (Float.floatToIntBits(a[i])!=Float.floatToIntBits(a2[i]))
2362 return false;
2363
2364 return true;
2365 }
2366
2367
2368 /**
2369 * Returns <tt>true</tt> if the two specified arrays of Objects are
2370 * <i>equal</i> to one another. The two arrays are considered equal if
2371 * both arrays contain the same number of elements, and all corresponding
2372 * pairs of elements in the two arrays are equal. Two objects <tt>e1</tt>
2373 * and <tt>e2</tt> are considered <i>equal</i> if <tt>(e1==null ? e2==null
2374 * : e1.equals(e2))</tt>. In other words, the two arrays are equal if
2375 * they contain the same elements in the same order. Also, two array
2376 * references are considered equal if both are <tt>null</tt>.<p>
2377 *
2378 * @param a one array to be tested for equality
2379 * @param a2 the other array to be tested for equality
2380 * @return <tt>true</tt> if the two arrays are equal
2381 */
2382 public static boolean equals(Object[] a, Object[] a2) {
2383 if (a==a2)
2384 return true;
2385 if (a==null || a2==null)
2386 return false;
2387
2388 int length = a.length;
2389 if (a2.length != length)
2390 return false;
2391
2392 for (int i=0; i<length; i++) {
2393 Object o1 = a[i];
2394 Object o2 = a2[i];
2395 if (!(o1==null ? o2==null : o1.equals(o2)))
2396 return false;
2397 }
2398
2399 return true;
2400 }
2401
2402
2403 // Filling
2404
2405 /**
2406 * Assigns the specified long value to each element of the specified array
2407 * of longs.
2408 *
2409 * @param a the array to be filled
2410 * @param val the value to be stored in all elements of the array
2411 */
2412 public static void fill(long[] a, long val) {
2413 for (int i = 0, len = a.length; i < len; i++)
2414 a[i] = val;
2415 }
2416
2417 /**
2418 * Assigns the specified long value to each element of the specified
2419 * range of the specified array of longs. The range to be filled
2420 * extends from index <tt>fromIndex</tt>, inclusive, to index
2421 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2422 * range to be filled is empty.)
2423 *
2424 * @param a the array to be filled
2425 * @param fromIndex the index of the first element (inclusive) to be
2426 * filled with the specified value
2427 * @param toIndex the index of the last element (exclusive) to be
2428 * filled with the specified value
2429 * @param val the value to be stored in all elements of the array
2430 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2431 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2432 * <tt>toIndex > a.length</tt>
2433 */
2434 public static void fill(long[] a, int fromIndex, int toIndex, long val) {
2435 rangeCheck(a.length, fromIndex, toIndex);
2436 for (int i = fromIndex; i < toIndex; i++)
2437 a[i] = val;
2438 }
2439
2440 /**
2441 * Assigns the specified int value to each element of the specified array
2442 * of ints.
2443 *
2444 * @param a the array to be filled
2445 * @param val the value to be stored in all elements of the array
2446 */
2447 public static void fill(int[] a, int val) {
2448 for (int i = 0, len = a.length; i < len; i++)
2449 a[i] = val;
2450 }
2451
2452 /**
2453 * Assigns the specified int value to each element of the specified
2454 * range of the specified array of ints. The range to be filled
2455 * extends from index <tt>fromIndex</tt>, inclusive, to index
2456 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2457 * range to be filled is empty.)
2458 *
2459 * @param a the array to be filled
2460 * @param fromIndex the index of the first element (inclusive) to be
2461 * filled with the specified value
2462 * @param toIndex the index of the last element (exclusive) to be
2463 * filled with the specified value
2464 * @param val the value to be stored in all elements of the array
2465 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2466 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2467 * <tt>toIndex > a.length</tt>
2468 */
2469 public static void fill(int[] a, int fromIndex, int toIndex, int val) {
2470 rangeCheck(a.length, fromIndex, toIndex);
2471 for (int i = fromIndex; i < toIndex; i++)
2472 a[i] = val;
2473 }
2474
2475 /**
2476 * Assigns the specified short value to each element of the specified array
2477 * of shorts.
2478 *
2479 * @param a the array to be filled
2480 * @param val the value to be stored in all elements of the array
2481 */
2482 public static void fill(short[] a, short val) {
2483 for (int i = 0, len = a.length; i < len; i++)
2484 a[i] = val;
2485 }
2486
2487 /**
2488 * Assigns the specified short value to each element of the specified
2489 * range of the specified array of shorts. The range to be filled
2490 * extends from index <tt>fromIndex</tt>, inclusive, to index
2491 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2492 * range to be filled is empty.)
2493 *
2494 * @param a the array to be filled
2495 * @param fromIndex the index of the first element (inclusive) to be
2496 * filled with the specified value
2497 * @param toIndex the index of the last element (exclusive) to be
2498 * filled with the specified value
2499 * @param val the value to be stored in all elements of the array
2500 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2501 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2502 * <tt>toIndex > a.length</tt>
2503 */
2504 public static void fill(short[] a, int fromIndex, int toIndex, short val) {
2505 rangeCheck(a.length, fromIndex, toIndex);
2506 for (int i = fromIndex; i < toIndex; i++)
2507 a[i] = val;
2508 }
2509
2510 /**
2511 * Assigns the specified char value to each element of the specified array
2512 * of chars.
2513 *
2514 * @param a the array to be filled
2515 * @param val the value to be stored in all elements of the array
2516 */
2517 public static void fill(char[] a, char val) {
2518 for (int i = 0, len = a.length; i < len; i++)
2519 a[i] = val;
2520 }
2521
2522 /**
2523 * Assigns the specified char value to each element of the specified
2524 * range of the specified array of chars. The range to be filled
2525 * extends from index <tt>fromIndex</tt>, inclusive, to index
2526 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2527 * range to be filled is empty.)
2528 *
2529 * @param a the array to be filled
2530 * @param fromIndex the index of the first element (inclusive) to be
2531 * filled with the specified value
2532 * @param toIndex the index of the last element (exclusive) to be
2533 * filled with the specified value
2534 * @param val the value to be stored in all elements of the array
2535 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2536 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2537 * <tt>toIndex > a.length</tt>
2538 */
2539 public static void fill(char[] a, int fromIndex, int toIndex, char val) {
2540 rangeCheck(a.length, fromIndex, toIndex);
2541 for (int i = fromIndex; i < toIndex; i++)
2542 a[i] = val;
2543 }
2544
2545 /**
2546 * Assigns the specified byte value to each element of the specified array
2547 * of bytes.
2548 *
2549 * @param a the array to be filled
2550 * @param val the value to be stored in all elements of the array
2551 */
2552 public static void fill(byte[] a, byte val) {
2553 for (int i = 0, len = a.length; i < len; i++)
2554 a[i] = val;
2555 }
2556
2557 /**
2558 * Assigns the specified byte value to each element of the specified
2559 * range of the specified array of bytes. The range to be filled
2560 * extends from index <tt>fromIndex</tt>, inclusive, to index
2561 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2562 * range to be filled is empty.)
2563 *
2564 * @param a the array to be filled
2565 * @param fromIndex the index of the first element (inclusive) to be
2566 * filled with the specified value
2567 * @param toIndex the index of the last element (exclusive) to be
2568 * filled with the specified value
2569 * @param val the value to be stored in all elements of the array
2570 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2571 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2572 * <tt>toIndex > a.length</tt>
2573 */
2574 public static void fill(byte[] a, int fromIndex, int toIndex, byte val) {
2575 rangeCheck(a.length, fromIndex, toIndex);
2576 for (int i = fromIndex; i < toIndex; i++)
2577 a[i] = val;
2578 }
2579
2580 /**
2581 * Assigns the specified boolean value to each element of the specified
2582 * array of booleans.
2583 *
2584 * @param a the array to be filled
2585 * @param val the value to be stored in all elements of the array
2586 */
2587 public static void fill(boolean[] a, boolean val) {
2588 for (int i = 0, len = a.length; i < len; i++)
2589 a[i] = val;
2590 }
2591
2592 /**
2593 * Assigns the specified boolean value to each element of the specified
2594 * range of the specified array of booleans. The range to be filled
2595 * extends from index <tt>fromIndex</tt>, inclusive, to index
2596 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2597 * range to be filled is empty.)
2598 *
2599 * @param a the array to be filled
2600 * @param fromIndex the index of the first element (inclusive) to be
2601 * filled with the specified value
2602 * @param toIndex the index of the last element (exclusive) to be
2603 * filled with the specified value
2604 * @param val the value to be stored in all elements of the array
2605 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2606 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2607 * <tt>toIndex > a.length</tt>
2608 */
2609 public static void fill(boolean[] a, int fromIndex, int toIndex,
2610 boolean val) {
2611 rangeCheck(a.length, fromIndex, toIndex);
2612 for (int i = fromIndex; i < toIndex; i++)
2613 a[i] = val;
2614 }
2615
2616 /**
2617 * Assigns the specified double value to each element of the specified
2618 * array of doubles.
2619 *
2620 * @param a the array to be filled
2621 * @param val the value to be stored in all elements of the array
2622 */
2623 public static void fill(double[] a, double val) {
2624 for (int i = 0, len = a.length; i < len; i++)
2625 a[i] = val;
2626 }
2627
2628 /**
2629 * Assigns the specified double value to each element of the specified
2630 * range of the specified array of doubles. The range to be filled
2631 * extends from index <tt>fromIndex</tt>, inclusive, to index
2632 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2633 * range to be filled is empty.)
2634 *
2635 * @param a the array to be filled
2636 * @param fromIndex the index of the first element (inclusive) to be
2637 * filled with the specified value
2638 * @param toIndex the index of the last element (exclusive) to be
2639 * filled with the specified value
2640 * @param val the value to be stored in all elements of the array
2641 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2642 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2643 * <tt>toIndex > a.length</tt>
2644 */
2645 public static void fill(double[] a, int fromIndex, int toIndex,double val){
2646 rangeCheck(a.length, fromIndex, toIndex);
2647 for (int i = fromIndex; i < toIndex; i++)
2648 a[i] = val;
2649 }
2650
2651 /**
2652 * Assigns the specified float value to each element of the specified array
2653 * of floats.
2654 *
2655 * @param a the array to be filled
2656 * @param val the value to be stored in all elements of the array
2657 */
2658 public static void fill(float[] a, float val) {
2659 for (int i = 0, len = a.length; i < len; i++)
2660 a[i] = val;
2661 }
2662
2663 /**
2664 * Assigns the specified float value to each element of the specified
2665 * range of the specified array of floats. The range to be filled
2666 * extends from index <tt>fromIndex</tt>, inclusive, to index
2667 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2668 * range to be filled is empty.)
2669 *
2670 * @param a the array to be filled
2671 * @param fromIndex the index of the first element (inclusive) to be
2672 * filled with the specified value
2673 * @param toIndex the index of the last element (exclusive) to be
2674 * filled with the specified value
2675 * @param val the value to be stored in all elements of the array
2676 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2677 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2678 * <tt>toIndex > a.length</tt>
2679 */
2680 public static void fill(float[] a, int fromIndex, int toIndex, float val) {
2681 rangeCheck(a.length, fromIndex, toIndex);
2682 for (int i = fromIndex; i < toIndex; i++)
2683 a[i] = val;
2684 }
2685
2686 /**
2687 * Assigns the specified Object reference to each element of the specified
2688 * array of Objects.
2689 *
2690 * @param a the array to be filled
2691 * @param val the value to be stored in all elements of the array
2692 * @throws ArrayStoreException if the specified value is not of a
2693 * runtime type that can be stored in the specified array
2694 */
2695 public static void fill(Object[] a, Object val) {
2696 for (int i = 0, len = a.length; i < len; i++)
2697 a[i] = val;
2698 }
2699
2700 /**
2701 * Assigns the specified Object reference to each element of the specified
2702 * range of the specified array of Objects. The range to be filled
2703 * extends from index <tt>fromIndex</tt>, inclusive, to index
2704 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2705 * range to be filled is empty.)
2706 *
2707 * @param a the array to be filled
2708 * @param fromIndex the index of the first element (inclusive) to be
2709 * filled with the specified value
2710 * @param toIndex the index of the last element (exclusive) to be
2711 * filled with the specified value
2712 * @param val the value to be stored in all elements of the array
2713 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2714 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2715 * <tt>toIndex > a.length</tt>
2716 * @throws ArrayStoreException if the specified value is not of a
2717 * runtime type that can be stored in the specified array
2718 */
2719 public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
2720 rangeCheck(a.length, fromIndex, toIndex);
2721 for (int i = fromIndex; i < toIndex; i++)
2722 a[i] = val;
2723 }
2724
2725
2726 // Cloning
2727 /**
2728 * Copies the specified array, truncating or padding with nulls (if necessary)
2729 * so the copy has the specified length. For all indices that are
2730 * valid in both the original array and the copy, the two arrays will
2731 * contain identical values. For any indices that are valid in the
2732 * copy but not the original, the copy will contain <tt>null</tt>.
2733 * Such indices will exist if and only if the specified length
2734 * is greater than that of the original array.
2735 * The resulting array is of exactly the same class as the original array.
2736 *
2737 * @param original the array to be copied
2738 * @param newLength the length of the copy to be returned
2739 * @return a copy of the original array, truncated or padded with nulls
2740 * to obtain the specified length
2741 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2742 * @throws NullPointerException if <tt>original</tt> is null
2743 * @since 1.6
2744 */
2745 public static <T> T[] copyOf(T[] original, int newLength) {
2746 return (T[]) copyOf(original, newLength, original.getClass());
2747 }
2748
2749 /**
2750 * Copies the specified array, truncating or padding with nulls (if necessary)
2751 * so the copy has the specified length. For all indices that are
2752 * valid in both the original array and the copy, the two arrays will
2753 * contain identical values. For any indices that are valid in the
2754 * copy but not the original, the copy will contain <tt>null</tt>.
2755 * Such indices will exist if and only if the specified length
2756 * is greater than that of the original array.
2757 * The resulting array is of the class <tt>newType</tt>.
2758 *
2759 * @param original the array to be copied
2760 * @param newLength the length of the copy to be returned
2761 * @param newType the class of the copy to be returned
2762 * @return a copy of the original array, truncated or padded with nulls
2763 * to obtain the specified length
2764 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2765 * @throws NullPointerException if <tt>original</tt> is null
2766 * @throws ArrayStoreException if an element copied from
2767 * <tt>original</tt> is not of a runtime type that can be stored in
2768 * an array of class <tt>newType</tt>
2769 * @since 1.6
2770 */
2771 public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
2772 T[] copy = ((Object)newType == (Object)Object[].class)
2773 ? (T[]) new Object[newLength]
2774 : (T[]) Array.newInstance(newType.getComponentType(), newLength);
2775 System.arraycopy(original, 0, copy, 0,
2776 Math.min(original.length, newLength));
2777 return copy;
2778 }
2779
2780 /**
2781 * Copies the specified array, truncating or padding with zeros (if necessary)
2782 * so the copy has the specified length. For all indices that are
2783 * valid in both the original array and the copy, the two arrays will
2784 * contain identical values. For any indices that are valid in the
2785 * copy but not the original, the copy will contain <tt>(byte)0</tt>.
2786 * Such indices will exist if and only if the specified length
2787 * is greater than that of the original array.
2788 *
2789 * @param original the array to be copied
2790 * @param newLength the length of the copy to be returned
2791 * @return a copy of the original array, truncated or padded with zeros
2792 * to obtain the specified length
2793 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2794 * @throws NullPointerException if <tt>original</tt> is null
2795 * @since 1.6
2796 */
2797 public static byte[] copyOf(byte[] original, int newLength) {
2798 byte[] copy = new byte[newLength];
2799 System.arraycopy(original, 0, copy, 0,
2800 Math.min(original.length, newLength));
2801 return copy;
2802 }
2803
2804 /**
2805 * Copies the specified array, truncating or padding with zeros (if necessary)
2806 * so the copy has the specified length. For all indices that are
2807 * valid in both the original array and the copy, the two arrays will
2808 * contain identical values. For any indices that are valid in the
2809 * copy but not the original, the copy will contain <tt>(short)0</tt>.
2810 * Such indices will exist if and only if the specified length
2811 * is greater than that of the original array.
2812 *
2813 * @param original the array to be copied
2814 * @param newLength the length of the copy to be returned
2815 * @return a copy of the original array, truncated or padded with zeros
2816 * to obtain the specified length
2817 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2818 * @throws NullPointerException if <tt>original</tt> is null
2819 * @since 1.6
2820 */
2821 public static short[] copyOf(short[] original, int newLength) {
2822 short[] copy = new short[newLength];
2823 System.arraycopy(original, 0, copy, 0,
2824 Math.min(original.length, newLength));
2825 return copy;
2826 }
2827
2828 /**
2829 * Copies the specified array, truncating or padding with zeros (if necessary)
2830 * so the copy has the specified length. For all indices that are
2831 * valid in both the original array and the copy, the two arrays will
2832 * contain identical values. For any indices that are valid in the
2833 * copy but not the original, the copy will contain <tt>0</tt>.
2834 * Such indices will exist if and only if the specified length
2835 * is greater than that of the original array.
2836 *
2837 * @param original the array to be copied
2838 * @param newLength the length of the copy to be returned
2839 * @return a copy of the original array, truncated or padded with zeros
2840 * to obtain the specified length
2841 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2842 * @throws NullPointerException if <tt>original</tt> is null
2843 * @since 1.6
2844 */
2845 public static int[] copyOf(int[] original, int newLength) {
2846 int[] copy = new int[newLength];
2847 System.arraycopy(original, 0, copy, 0,
2848 Math.min(original.length, newLength));
2849 return copy;
2850 }
2851
2852 /**
2853 * Copies the specified array, truncating or padding with zeros (if necessary)
2854 * so the copy has the specified length. For all indices that are
2855 * valid in both the original array and the copy, the two arrays will
2856 * contain identical values. For any indices that are valid in the
2857 * copy but not the original, the copy will contain <tt>0L</tt>.
2858 * Such indices will exist if and only if the specified length
2859 * is greater than that of the original array.
2860 *
2861 * @param original the array to be copied
2862 * @param newLength the length of the copy to be returned
2863 * @return a copy of the original array, truncated or padded with zeros
2864 * to obtain the specified length
2865 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2866 * @throws NullPointerException if <tt>original</tt> is null
2867 * @since 1.6
2868 */
2869 public static long[] copyOf(long[] original, int newLength) {
2870 long[] copy = new long[newLength];
2871 System.arraycopy(original, 0, copy, 0,
2872 Math.min(original.length, newLength));
2873 return copy;
2874 }
2875
2876 /**
2877 * Copies the specified array, truncating or padding with null characters (if necessary)
2878 * so the copy has the specified length. For all indices that are valid
2879 * in both the original array and the copy, the two arrays will contain
2880 * identical values. For any indices that are valid in the copy but not
2881 * the original, the copy will contain <tt>'\\u000'</tt>. Such indices
2882 * will exist if and only if the specified length is greater than that of
2883 * the original array.
2884 *
2885 * @param original the array to be copied
2886 * @param newLength the length of the copy to be returned
2887 * @return a copy of the original array, truncated or padded with null characters
2888 * to obtain the specified length
2889 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2890 * @throws NullPointerException if <tt>original</tt> is null
2891 * @since 1.6
2892 */
2893 public static char[] copyOf(char[] original, int newLength) {
2894 char[] copy = new char[newLength];
2895 System.arraycopy(original, 0, copy, 0,
2896 Math.min(original.length, newLength));
2897 return copy;
2898 }
2899
2900 /**
2901 * Copies the specified array, truncating or padding with zeros (if necessary)
2902 * so the copy has the specified length. For all indices that are
2903 * valid in both the original array and the copy, the two arrays will
2904 * contain identical values. For any indices that are valid in the
2905 * copy but not the original, the copy will contain <tt>0f</tt>.
2906 * Such indices will exist if and only if the specified length
2907 * is greater than that of the original array.
2908 *
2909 * @param original the array to be copied
2910 * @param newLength the length of the copy to be returned
2911 * @return a copy of the original array, truncated or padded with zeros
2912 * to obtain the specified length
2913 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2914 * @throws NullPointerException if <tt>original</tt> is null
2915 * @since 1.6
2916 */
2917 public static float[] copyOf(float[] original, int newLength) {
2918 float[] copy = new float[newLength];
2919 System.arraycopy(original, 0, copy, 0,
2920 Math.min(original.length, newLength));
2921 return copy;
2922 }
2923
2924 /**
2925 * Copies the specified array, truncating or padding with zeros (if necessary)
2926 * so the copy has the specified length. For all indices that are
2927 * valid in both the original array and the copy, the two arrays will
2928 * contain identical values. For any indices that are valid in the
2929 * copy but not the original, the copy will contain <tt>0d</tt>.
2930 * Such indices will exist if and only if the specified length
2931 * is greater than that of the original array.
2932 *
2933 * @param original the array to be copied
2934 * @param newLength the length of the copy to be returned
2935 * @return a copy of the original array, truncated or padded with zeros
2936 * to obtain the specified length
2937 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2938 * @throws NullPointerException if <tt>original</tt> is null
2939 * @since 1.6
2940 */
2941 public static double[] copyOf(double[] original, int newLength) {
2942 double[] copy = new double[newLength];
2943 System.arraycopy(original, 0, copy, 0,
2944 Math.min(original.length, newLength));
2945 return copy;
2946 }
2947
2948 /**
2949 * Copies the specified array, truncating or padding with <tt>false</tt> (if necessary)
2950 * so the copy has the specified length. For all indices that are
2951 * valid in both the original array and the copy, the two arrays will
2952 * contain identical values. For any indices that are valid in the
2953 * copy but not the original, the copy will contain <tt>false</tt>.
2954 * Such indices will exist if and only if the specified length
2955 * is greater than that of the original array.
2956 *
2957 * @param original the array to be copied
2958 * @param newLength the length of the copy to be returned
2959 * @return a copy of the original array, truncated or padded with false elements
2960 * to obtain the specified length
2961 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2962 * @throws NullPointerException if <tt>original</tt> is null
2963 * @since 1.6
2964 */
2965 public static boolean[] copyOf(boolean[] original, int newLength) {
2966 boolean[] copy = new boolean[newLength];
2967 System.arraycopy(original, 0, copy, 0,
2968 Math.min(original.length, newLength));
2969 return copy;
2970 }
2971
2972 /**
2973 * Copies the specified range of the specified array into a new array.
2974 * The initial index of the range (<tt>from</tt>) must lie between zero
2975 * and <tt>original.length</tt>, inclusive. The value at
2976 * <tt>original[from]</tt> is placed into the initial element of the copy
2977 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2978 * Values from subsequent elements in the original array are placed into
2979 * subsequent elements in the copy. The final index of the range
2980 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2981 * may be greater than <tt>original.length</tt>, in which case
2982 * <tt>null</tt> is placed in all elements of the copy whose index is
2983 * greater than or equal to <tt>original.length - from</tt>. The length
2984 * of the returned array will be <tt>to - from</tt>.
2985 * <p>
2986 * The resulting array is of exactly the same class as the original array.
2987 *
2988 * @param original the array from which a range is to be copied
2989 * @param from the initial index of the range to be copied, inclusive
2990 * @param to the final index of the range to be copied, exclusive.
2991 * (This index may lie outside the array.)
2992 * @return a new array containing the specified range from the original array,
2993 * truncated or padded with nulls to obtain the required length
2994 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2995 * or {@code from > original.length}
2996 * @throws IllegalArgumentException if <tt>from > to</tt>
2997 * @throws NullPointerException if <tt>original</tt> is null
2998 * @since 1.6
2999 */
3000 public static <T> T[] copyOfRange(T[] original, int from, int to) {
3001 return copyOfRange(original, from, to, (Class<T[]>) original.getClass());
3002 }
3003
3004 /**
3005 * Copies the specified range of the specified array into a new array.
3006 * The initial index of the range (<tt>from</tt>) must lie between zero
3007 * and <tt>original.length</tt>, inclusive. The value at
3008 * <tt>original[from]</tt> is placed into the initial element of the copy
3009 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3010 * Values from subsequent elements in the original array are placed into
3011 * subsequent elements in the copy. The final index of the range
3012 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3013 * may be greater than <tt>original.length</tt>, in which case
3014 * <tt>null</tt> is placed in all elements of the copy whose index is
3015 * greater than or equal to <tt>original.length - from</tt>. The length
3016 * of the returned array will be <tt>to - from</tt>.
3017 * The resulting array is of the class <tt>newType</tt>.
3018 *
3019 * @param original the array from which a range is to be copied
3020 * @param from the initial index of the range to be copied, inclusive
3021 * @param to the final index of the range to be copied, exclusive.
3022 * (This index may lie outside the array.)
3023 * @param newType the class of the copy to be returned
3024 * @return a new array containing the specified range from the original array,
3025 * truncated or padded with nulls to obtain the required length
3026 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3027 * or {@code from > original.length}
3028 * @throws IllegalArgumentException if <tt>from > to</tt>
3029 * @throws NullPointerException if <tt>original</tt> is null
3030 * @throws ArrayStoreException if an element copied from
3031 * <tt>original</tt> is not of a runtime type that can be stored in
3032 * an array of class <tt>newType</tt>.
3033 * @since 1.6
3034 */
3035 public static <T,U> T[] copyOfRange(U[] original, int from, int to, Class<? extends T[]> newType) {
3036 int newLength = to - from;
3037 if (newLength < 0)
3038 throw new IllegalArgumentException(from + " > " + to);
3039 T[] copy = ((Object)newType == (Object)Object[].class)
3040 ? (T[]) new Object[newLength]
3041 : (T[]) Array.newInstance(newType.getComponentType(), newLength);
3042 System.arraycopy(original, from, copy, 0,
3043 Math.min(original.length - from, newLength));
3044 return copy;
3045 }
3046
3047 /**
3048 * Copies the specified range of the specified array into a new array.
3049 * The initial index of the range (<tt>from</tt>) must lie between zero
3050 * and <tt>original.length</tt>, inclusive. The value at
3051 * <tt>original[from]</tt> is placed into the initial element of the copy
3052 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3053 * Values from subsequent elements in the original array are placed into
3054 * subsequent elements in the copy. The final index of the range
3055 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3056 * may be greater than <tt>original.length</tt>, in which case
3057 * <tt>(byte)0</tt> is placed in all elements of the copy whose index is
3058 * greater than or equal to <tt>original.length - from</tt>. The length
3059 * of the returned array will be <tt>to - from</tt>.
3060 *
3061 * @param original the array from which a range is to be copied
3062 * @param from the initial index of the range to be copied, inclusive
3063 * @param to the final index of the range to be copied, exclusive.
3064 * (This index may lie outside the array.)
3065 * @return a new array containing the specified range from the original array,
3066 * truncated or padded with zeros to obtain the required length
3067 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3068 * or {@code from > original.length}
3069 * @throws IllegalArgumentException if <tt>from > to</tt>
3070 * @throws NullPointerException if <tt>original</tt> is null
3071 * @since 1.6
3072 */
3073 public static byte[] copyOfRange(byte[] original, int from, int to) {
3074 int newLength = to - from;
3075 if (newLength < 0)
3076 throw new IllegalArgumentException(from + " > " + to);
3077 byte[] copy = new byte[newLength];
3078 System.arraycopy(original, from, copy, 0,
3079 Math.min(original.length - from, newLength));
3080 return copy;
3081 }
3082
3083 /**
3084 * Copies the specified range of the specified array into a new array.
3085 * The initial index of the range (<tt>from</tt>) must lie between zero
3086 * and <tt>original.length</tt>, inclusive. The value at
3087 * <tt>original[from]</tt> is placed into the initial element of the copy
3088 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3089 * Values from subsequent elements in the original array are placed into
3090 * subsequent elements in the copy. The final index of the range
3091 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3092 * may be greater than <tt>original.length</tt>, in which case
3093 * <tt>(short)0</tt> is placed in all elements of the copy whose index is
3094 * greater than or equal to <tt>original.length - from</tt>. The length
3095 * of the returned array will be <tt>to - from</tt>.
3096 *
3097 * @param original the array from which a range is to be copied
3098 * @param from the initial index of the range to be copied, inclusive
3099 * @param to the final index of the range to be copied, exclusive.
3100 * (This index may lie outside the array.)
3101 * @return a new array containing the specified range from the original array,
3102 * truncated or padded with zeros to obtain the required length
3103 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3104 * or {@code from > original.length}
3105 * @throws IllegalArgumentException if <tt>from > to</tt>
3106 * @throws NullPointerException if <tt>original</tt> is null
3107 * @since 1.6
3108 */
3109 public static short[] copyOfRange(short[] original, int from, int to) {
3110 int newLength = to - from;
3111 if (newLength < 0)
3112 throw new IllegalArgumentException(from + " > " + to);
3113 short[] copy = new short[newLength];
3114 System.arraycopy(original, from, copy, 0,
3115 Math.min(original.length - from, newLength));
3116 return copy;
3117 }
3118
3119 /**
3120 * Copies the specified range of the specified array into a new array.
3121 * The initial index of the range (<tt>from</tt>) must lie between zero
3122 * and <tt>original.length</tt>, inclusive. The value at
3123 * <tt>original[from]</tt> is placed into the initial element of the copy
3124 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3125 * Values from subsequent elements in the original array are placed into
3126 * subsequent elements in the copy. The final index of the range
3127 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3128 * may be greater than <tt>original.length</tt>, in which case
3129 * <tt>0</tt> is placed in all elements of the copy whose index is
3130 * greater than or equal to <tt>original.length - from</tt>. The length
3131 * of the returned array will be <tt>to - from</tt>.
3132 *
3133 * @param original the array from which a range is to be copied
3134 * @param from the initial index of the range to be copied, inclusive
3135 * @param to the final index of the range to be copied, exclusive.
3136 * (This index may lie outside the array.)
3137 * @return a new array containing the specified range from the original array,
3138 * truncated or padded with zeros to obtain the required length
3139 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3140 * or {@code from > original.length}
3141 * @throws IllegalArgumentException if <tt>from > to</tt>
3142 * @throws NullPointerException if <tt>original</tt> is null
3143 * @since 1.6
3144 */
3145 public static int[] copyOfRange(int[] original, int from, int to) {
3146 int newLength = to - from;
3147 if (newLength < 0)
3148 throw new IllegalArgumentException(from + " > " + to);
3149 int[] copy = new int[newLength];
3150 System.arraycopy(original, from, copy, 0,
3151 Math.min(original.length - from, newLength));
3152 return copy;
3153 }
3154
3155 /**
3156 * Copies the specified range of the specified array into a new array.
3157 * The initial index of the range (<tt>from</tt>) must lie between zero
3158 * and <tt>original.length</tt>, inclusive. The value at
3159 * <tt>original[from]</tt> is placed into the initial element of the copy
3160 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3161 * Values from subsequent elements in the original array are placed into
3162 * subsequent elements in the copy. The final index of the range
3163 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3164 * may be greater than <tt>original.length</tt>, in which case
3165 * <tt>0L</tt> is placed in all elements of the copy whose index is
3166 * greater than or equal to <tt>original.length - from</tt>. The length
3167 * of the returned array will be <tt>to - from</tt>.
3168 *
3169 * @param original the array from which a range is to be copied
3170 * @param from the initial index of the range to be copied, inclusive
3171 * @param to the final index of the range to be copied, exclusive.
3172 * (This index may lie outside the array.)
3173 * @return a new array containing the specified range from the original array,
3174 * truncated or padded with zeros to obtain the required length
3175 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3176 * or {@code from > original.length}
3177 * @throws IllegalArgumentException if <tt>from > to</tt>
3178 * @throws NullPointerException if <tt>original</tt> is null
3179 * @since 1.6
3180 */
3181 public static long[] copyOfRange(long[] original, int from, int to) {
3182 int newLength = to - from;
3183 if (newLength < 0)
3184 throw new IllegalArgumentException(from + " > " + to);
3185 long[] copy = new long[newLength];
3186 System.arraycopy(original, from, copy, 0,
3187 Math.min(original.length - from, newLength));
3188 return copy;
3189 }
3190
3191 /**
3192 * Copies the specified range of the specified array into a new array.
3193 * The initial index of the range (<tt>from</tt>) must lie between zero
3194 * and <tt>original.length</tt>, inclusive. The value at
3195 * <tt>original[from]</tt> is placed into the initial element of the copy
3196 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3197 * Values from subsequent elements in the original array are placed into
3198 * subsequent elements in the copy. The final index of the range
3199 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3200 * may be greater than <tt>original.length</tt>, in which case
3201 * <tt>'\\u000'</tt> is placed in all elements of the copy whose index is
3202 * greater than or equal to <tt>original.length - from</tt>. The length
3203 * of the returned array will be <tt>to - from</tt>.
3204 *
3205 * @param original the array from which a range is to be copied
3206 * @param from the initial index of the range to be copied, inclusive
3207 * @param to the final index of the range to be copied, exclusive.
3208 * (This index may lie outside the array.)
3209 * @return a new array containing the specified range from the original array,
3210 * truncated or padded with null characters to obtain the required length
3211 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3212 * or {@code from > original.length}
3213 * @throws IllegalArgumentException if <tt>from > to</tt>
3214 * @throws NullPointerException if <tt>original</tt> is null
3215 * @since 1.6
3216 */
3217 public static char[] copyOfRange(char[] original, int from, int to) {
3218 int newLength = to - from;
3219 if (newLength < 0)
3220 throw new IllegalArgumentException(from + " > " + to);
3221 char[] copy = new char[newLength];
3222 System.arraycopy(original, from, copy, 0,
3223 Math.min(original.length - from, newLength));
3224 return copy;
3225 }
3226
3227 /**
3228 * Copies the specified range of the specified array into a new array.
3229 * The initial index of the range (<tt>from</tt>) must lie between zero
3230 * and <tt>original.length</tt>, inclusive. The value at
3231 * <tt>original[from]</tt> is placed into the initial element of the copy
3232 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3233 * Values from subsequent elements in the original array are placed into
3234 * subsequent elements in the copy. The final index of the range
3235 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3236 * may be greater than <tt>original.length</tt>, in which case
3237 * <tt>0f</tt> is placed in all elements of the copy whose index is
3238 * greater than or equal to <tt>original.length - from</tt>. The length
3239 * of the returned array will be <tt>to - from</tt>.
3240 *
3241 * @param original the array from which a range is to be copied
3242 * @param from the initial index of the range to be copied, inclusive
3243 * @param to the final index of the range to be copied, exclusive.
3244 * (This index may lie outside the array.)
3245 * @return a new array containing the specified range from the original array,
3246 * truncated or padded with zeros to obtain the required length
3247 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3248 * or {@code from > original.length}
3249 * @throws IllegalArgumentException if <tt>from > to</tt>
3250 * @throws NullPointerException if <tt>original</tt> is null
3251 * @since 1.6
3252 */
3253 public static float[] copyOfRange(float[] original, int from, int to) {
3254 int newLength = to - from;
3255 if (newLength < 0)
3256 throw new IllegalArgumentException(from + " > " + to);
3257 float[] copy = new float[newLength];
3258 System.arraycopy(original, from, copy, 0,
3259 Math.min(original.length - from, newLength));
3260 return copy;
3261 }
3262
3263 /**
3264 * Copies the specified range of the specified array into a new array.
3265 * The initial index of the range (<tt>from</tt>) must lie between zero
3266 * and <tt>original.length</tt>, inclusive. The value at
3267 * <tt>original[from]</tt> is placed into the initial element of the copy
3268 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3269 * Values from subsequent elements in the original array are placed into
3270 * subsequent elements in the copy. The final index of the range
3271 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3272 * may be greater than <tt>original.length</tt>, in which case
3273 * <tt>0d</tt> is placed in all elements of the copy whose index is
3274 * greater than or equal to <tt>original.length - from</tt>. The length
3275 * of the returned array will be <tt>to - from</tt>.
3276 *
3277 * @param original the array from which a range is to be copied
3278 * @param from the initial index of the range to be copied, inclusive
3279 * @param to the final index of the range to be copied, exclusive.
3280 * (This index may lie outside the array.)
3281 * @return a new array containing the specified range from the original array,
3282 * truncated or padded with zeros to obtain the required length
3283 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3284 * or {@code from > original.length}
3285 * @throws IllegalArgumentException if <tt>from > to</tt>
3286 * @throws NullPointerException if <tt>original</tt> is null
3287 * @since 1.6
3288 */
3289 public static double[] copyOfRange(double[] original, int from, int to) {
3290 int newLength = to - from;
3291 if (newLength < 0)
3292 throw new IllegalArgumentException(from + " > " + to);
3293 double[] copy = new double[newLength];
3294 System.arraycopy(original, from, copy, 0,
3295 Math.min(original.length - from, newLength));
3296 return copy;
3297 }
3298
3299 /**
3300 * Copies the specified range of the specified array into a new array.
3301 * The initial index of the range (<tt>from</tt>) must lie between zero
3302 * and <tt>original.length</tt>, inclusive. The value at
3303 * <tt>original[from]</tt> is placed into the initial element of the copy
3304 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3305 * Values from subsequent elements in the original array are placed into
3306 * subsequent elements in the copy. The final index of the range
3307 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3308 * may be greater than <tt>original.length</tt>, in which case
3309 * <tt>false</tt> is placed in all elements of the copy whose index is
3310 * greater than or equal to <tt>original.length - from</tt>. The length
3311 * of the returned array will be <tt>to - from</tt>.
3312 *
3313 * @param original the array from which a range is to be copied
3314 * @param from the initial index of the range to be copied, inclusive
3315 * @param to the final index of the range to be copied, exclusive.
3316 * (This index may lie outside the array.)
3317 * @return a new array containing the specified range from the original array,
3318 * truncated or padded with false elements to obtain the required length
3319 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3320 * or {@code from > original.length}
3321 * @throws IllegalArgumentException if <tt>from > to</tt>
3322 * @throws NullPointerException if <tt>original</tt> is null
3323 * @since 1.6
3324 */
3325 public static boolean[] copyOfRange(boolean[] original, int from, int to) {
3326 int newLength = to - from;
3327 if (newLength < 0)
3328 throw new IllegalArgumentException(from + " > " + to);
3329 boolean[] copy = new boolean[newLength];
3330 System.arraycopy(original, from, copy, 0,
3331 Math.min(original.length - from, newLength));
3332 return copy;
3333 }
3334
3335
3336 // Misc
3337
3338 /**
3339 * Returns a fixed-size list backed by the specified array. (Changes to
3340 * the returned list "write through" to the array.) This method acts
3341 * as bridge between array-based and collection-based APIs, in
3342 * combination with {@link Collection#toArray}. The returned list is
3343 * serializable and implements {@link RandomAccess}.
3344 *
3345 * <p>This method also provides a convenient way to create a fixed-size
3346 * list initialized to contain several elements:
3347 * <pre>
3348 * List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
3349 * </pre>
3350 *
3351 * @param a the array by which the list will be backed
3352 * @return a list view of the specified array
3353 */
3354 public static <T> List<T> asList(T... a) {
3355 return new ArrayList<T>(a);
3356 }
3357
3358 /**
3359 * @serial include
3360 */
3361 private static class ArrayList<E> extends AbstractList<E>
3362 implements RandomAccess, java.io.Serializable
3363 {
3364 private static final long serialVersionUID = -2764017481108945198L;
3365 private final E[] a;
3366
3367 ArrayList(E[] array) {
3368 if (array==null)
3369 throw new NullPointerException();
3370 a = array;
3371 }
3372
3373 public int size() {
3374 return a.length;
3375 }
3376
3377 public Object[] toArray() {
3378 return a.clone();
3379 }
3380
3381 public <T> T[] toArray(T[] a) {
3382 int size = size();
3383 if (a.length < size)
3384 return Arrays.copyOf(this.a, size,
3385 (Class<? extends T[]>) a.getClass());
3386 System.arraycopy(this.a, 0, a, 0, size);
3387 if (a.length > size)
3388 a[size] = null;
3389 return a;
3390 }
3391
3392 public E get(int index) {
3393 return a[index];
3394 }
3395
3396 public E set(int index, E element) {
3397 E oldValue = a[index];
3398 a[index] = element;
3399 return oldValue;
3400 }
3401
3402 public int indexOf(Object o) {
3403 if (o==null) {
3404 for (int i=0; i<a.length; i++)
3405 if (a[i]==null)
3406 return i;
3407 } else {
3408 for (int i=0; i<a.length; i++)
3409 if (o.equals(a[i]))
3410 return i;
3411 }
3412 return -1;
3413 }
3414
3415 public boolean contains(Object o) {
3416 return indexOf(o) != -1;
3417 }
3418 }
3419
3420 /**
3421 * Returns a hash code based on the contents of the specified array.
3422 * For any two <tt>long</tt> arrays <tt>a</tt> and <tt>b</tt>
3423 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3424 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3425 *
3426 * <p>The value returned by this method is the same value that would be
3427 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3428 * method on a {@link List} containing a sequence of {@link Long}
3429 * instances representing the elements of <tt>a</tt> in the same order.
3430 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3431 *
3432 * @param a the array whose hash value to compute
3433 * @return a content-based hash code for <tt>a</tt>
3434 * @since 1.5
3435 */
3436 public static int hashCode(long a[]) {
3437 if (a == null)
3438 return 0;
3439
3440 int result = 1;
3441 for (long element : a) {
3442 int elementHash = (int)(element ^ (element >>> 32));
3443 result = 31 * result + elementHash;
3444 }
3445
3446 return result;
3447 }
3448
3449 /**
3450 * Returns a hash code based on the contents of the specified array.
3451 * For any two non-null <tt>int</tt> arrays <tt>a</tt> and <tt>b</tt>
3452 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3453 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3454 *
3455 * <p>The value returned by this method is the same value that would be
3456 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3457 * method on a {@link List} containing a sequence of {@link Integer}
3458 * instances representing the elements of <tt>a</tt> in the same order.
3459 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3460 *
3461 * @param a the array whose hash value to compute
3462 * @return a content-based hash code for <tt>a</tt>
3463 * @since 1.5
3464 */
3465 public static int hashCode(int a[]) {
3466 if (a == null)
3467 return 0;
3468
3469 int result = 1;
3470 for (int element : a)
3471 result = 31 * result + element;
3472
3473 return result;
3474 }
3475
3476 /**
3477 * Returns a hash code based on the contents of the specified array.
3478 * For any two <tt>short</tt> arrays <tt>a</tt> and <tt>b</tt>
3479 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3480 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3481 *
3482 * <p>The value returned by this method is the same value that would be
3483 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3484 * method on a {@link List} containing a sequence of {@link Short}
3485 * instances representing the elements of <tt>a</tt> in the same order.
3486 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3487 *
3488 * @param a the array whose hash value to compute
3489 * @return a content-based hash code for <tt>a</tt>
3490 * @since 1.5
3491 */
3492 public static int hashCode(short a[]) {
3493 if (a == null)
3494 return 0;
3495
3496 int result = 1;
3497 for (short element : a)
3498 result = 31 * result + element;
3499
3500 return result;
3501 }
3502
3503 /**
3504 * Returns a hash code based on the contents of the specified array.
3505 * For any two <tt>char</tt> arrays <tt>a</tt> and <tt>b</tt>
3506 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3507 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3508 *
3509 * <p>The value returned by this method is the same value that would be
3510 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3511 * method on a {@link List} containing a sequence of {@link Character}
3512 * instances representing the elements of <tt>a</tt> in the same order.
3513 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3514 *
3515 * @param a the array whose hash value to compute
3516 * @return a content-based hash code for <tt>a</tt>
3517 * @since 1.5
3518 */
3519 public static int hashCode(char a[]) {
3520 if (a == null)
3521 return 0;
3522
3523 int result = 1;
3524 for (char element : a)
3525 result = 31 * result + element;
3526
3527 return result;
3528 }
3529
3530 /**
3531 * Returns a hash code based on the contents of the specified array.
3532 * For any two <tt>byte</tt> arrays <tt>a</tt> and <tt>b</tt>
3533 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3534 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3535 *
3536 * <p>The value returned by this method is the same value that would be
3537 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3538 * method on a {@link List} containing a sequence of {@link Byte}
3539 * instances representing the elements of <tt>a</tt> in the same order.
3540 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3541 *
3542 * @param a the array whose hash value to compute
3543 * @return a content-based hash code for <tt>a</tt>
3544 * @since 1.5
3545 */
3546 public static int hashCode(byte a[]) {
3547 if (a == null)
3548 return 0;
3549
3550 int result = 1;
3551 for (byte element : a)
3552 result = 31 * result + element;
3553
3554 return result;
3555 }
3556
3557 /**
3558 * Returns a hash code based on the contents of the specified array.
3559 * For any two <tt>boolean</tt> arrays <tt>a</tt> and <tt>b</tt>
3560 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3561 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3562 *
3563 * <p>The value returned by this method is the same value that would be
3564 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3565 * method on a {@link List} containing a sequence of {@link Boolean}
3566 * instances representing the elements of <tt>a</tt> in the same order.
3567 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3568 *
3569 * @param a the array whose hash value to compute
3570 * @return a content-based hash code for <tt>a</tt>
3571 * @since 1.5
3572 */
3573 public static int hashCode(boolean a[]) {
3574 if (a == null)
3575 return 0;
3576
3577 int result = 1;
3578 for (boolean element : a)
3579 result = 31 * result + (element ? 1231 : 1237);
3580
3581 return result;
3582 }
3583
3584 /**
3585 * Returns a hash code based on the contents of the specified array.
3586 * For any two <tt>float</tt> arrays <tt>a</tt> and <tt>b</tt>
3587 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3588 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3589 *
3590 * <p>The value returned by this method is the same value that would be
3591 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3592 * method on a {@link List} containing a sequence of {@link Float}
3593 * instances representing the elements of <tt>a</tt> in the same order.
3594 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3595 *
3596 * @param a the array whose hash value to compute
3597 * @return a content-based hash code for <tt>a</tt>
3598 * @since 1.5
3599 */
3600 public static int hashCode(float a[]) {
3601 if (a == null)
3602 return 0;
3603
3604 int result = 1;
3605 for (float element : a)
3606 result = 31 * result + Float.floatToIntBits(element);
3607
3608 return result;
3609 }
3610
3611 /**
3612 * Returns a hash code based on the contents of the specified array.
3613 * For any two <tt>double</tt> arrays <tt>a</tt> and <tt>b</tt>
3614 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3615 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3616 *
3617 * <p>The value returned by this method is the same value that would be
3618 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3619 * method on a {@link List} containing a sequence of {@link Double}
3620 * instances representing the elements of <tt>a</tt> in the same order.
3621 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3622 *
3623 * @param a the array whose hash value to compute
3624 * @return a content-based hash code for <tt>a</tt>
3625 * @since 1.5
3626 */
3627 public static int hashCode(double a[]) {
3628 if (a == null)
3629 return 0;
3630
3631 int result = 1;
3632 for (double element : a) {
3633 long bits = Double.doubleToLongBits(element);
3634 result = 31 * result + (int)(bits ^ (bits >>> 32));
3635 }
3636 return result;
3637 }
3638
3639 /**
3640 * Returns a hash code based on the contents of the specified array. If
3641 * the array contains other arrays as elements, the hash code is based on
3642 * their identities rather than their contents. It is therefore
3643 * acceptable to invoke this method on an array that contains itself as an
3644 * element, either directly or indirectly through one or more levels of
3645 * arrays.
3646 *
3647 * <p>For any two arrays <tt>a</tt> and <tt>b</tt> such that
3648 * <tt>Arrays.equals(a, b)</tt>, it is also the case that
3649 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3650 *
3651 * <p>The value returned by this method is equal to the value that would
3652 * be returned by <tt>Arrays.asList(a).hashCode()</tt>, unless <tt>a</tt>
3653 * is <tt>null</tt>, in which case <tt>0</tt> is returned.
3654 *
3655 * @param a the array whose content-based hash code to compute
3656 * @return a content-based hash code for <tt>a</tt>
3657 * @see #deepHashCode(Object[])
3658 * @since 1.5
3659 */
3660 public static int hashCode(Object a[]) {
3661 if (a == null)
3662 return 0;
3663
3664 int result = 1;
3665
3666 for (Object element : a)
3667 result = 31 * result + (element == null ? 0 : element.hashCode());
3668
3669 return result;
3670 }
3671
3672 /**
3673 * Returns a hash code based on the "deep contents" of the specified
3674 * array. If the array contains other arrays as elements, the
3675 * hash code is based on their contents and so on, ad infinitum.
3676 * It is therefore unacceptable to invoke this method on an array that
3677 * contains itself as an element, either directly or indirectly through
3678 * one or more levels of arrays. The behavior of such an invocation is
3679 * undefined.
3680 *
3681 * <p>For any two arrays <tt>a</tt> and <tt>b</tt> such that
3682 * <tt>Arrays.deepEquals(a, b)</tt>, it is also the case that
3683 * <tt>Arrays.deepHashCode(a) == Arrays.deepHashCode(b)</tt>.
3684 *
3685 * <p>The computation of the value returned by this method is similar to
3686 * that of the value returned by {@link List#hashCode()} on a list
3687 * containing the same elements as <tt>a</tt> in the same order, with one
3688 * difference: If an element <tt>e</tt> of <tt>a</tt> is itself an array,
3689 * its hash code is computed not by calling <tt>e.hashCode()</tt>, but as
3690 * by calling the appropriate overloading of <tt>Arrays.hashCode(e)</tt>
3691 * if <tt>e</tt> is an array of a primitive type, or as by calling
3692 * <tt>Arrays.deepHashCode(e)</tt> recursively if <tt>e</tt> is an array
3693 * of a reference type. If <tt>a</tt> is <tt>null</tt>, this method
3694 * returns 0.
3695 *
3696 * @param a the array whose deep-content-based hash code to compute
3697 * @return a deep-content-based hash code for <tt>a</tt>
3698 * @see #hashCode(Object[])
3699 * @since 1.5
3700 */
3701 public static int deepHashCode(Object a[]) {
3702 if (a == null)
3703 return 0;
3704
3705 int result = 1;
3706
3707 for (Object element : a) {
3708 int elementHash = 0;
3709 if (element instanceof Object[])
3710 elementHash = deepHashCode((Object[]) element);
3711 else if (element instanceof byte[])
3712 elementHash = hashCode((byte[]) element);
3713 else if (element instanceof short[])
3714 elementHash = hashCode((short[]) element);
3715 else if (element instanceof int[])
3716 elementHash = hashCode((int[]) element);
3717 else if (element instanceof long[])
3718 elementHash = hashCode((long[]) element);
3719 else if (element instanceof char[])
3720 elementHash = hashCode((char[]) element);
3721 else if (element instanceof float[])
3722 elementHash = hashCode((float[]) element);
3723 else if (element instanceof double[])
3724 elementHash = hashCode((double[]) element);
3725 else if (element instanceof boolean[])
3726 elementHash = hashCode((boolean[]) element);
3727 else if (element != null)
3728 elementHash = element.hashCode();
3729
3730 result = 31 * result + elementHash;
3731 }
3732
3733 return result;
3734 }
3735
3736 /**
3737 * Returns <tt>true</tt> if the two specified arrays are <i>deeply
3738 * equal</i> to one another. Unlike the {@link #equals(Object[],Object[])}
3739 * method, this method is appropriate for use with nested arrays of
3740 * arbitrary depth.
3741 *
3742 * <p>Two array references are considered deeply equal if both
3743 * are <tt>null</tt>, or if they refer to arrays that contain the same
3744 * number of elements and all corresponding pairs of elements in the two
3745 * arrays are deeply equal.
3746 *
3747 * <p>Two possibly <tt>null</tt> elements <tt>e1</tt> and <tt>e2</tt> are
3748 * deeply equal if any of the following conditions hold:
3749 * <ul>
3750 * <li> <tt>e1</tt> and <tt>e2</tt> are both arrays of object reference
3751 * types, and <tt>Arrays.deepEquals(e1, e2) would return true</tt>
3752 * <li> <tt>e1</tt> and <tt>e2</tt> are arrays of the same primitive
3753 * type, and the appropriate overloading of
3754 * <tt>Arrays.equals(e1, e2)</tt> would return true.
3755 * <li> <tt>e1 == e2</tt>
3756 * <li> <tt>e1.equals(e2)</tt> would return true.
3757 * </ul>
3758 * Note that this definition permits <tt>null</tt> elements at any depth.
3759 *
3760 * <p>If either of the specified arrays contain themselves as elements
3761 * either directly or indirectly through one or more levels of arrays,
3762 * the behavior of this method is undefined.
3763 *
3764 * @param a1 one array to be tested for equality
3765 * @param a2 the other array to be tested for equality
3766 * @return <tt>true</tt> if the two arrays are equal
3767 * @see #equals(Object[],Object[])
3768 * @since 1.5
3769 */
3770 public static boolean deepEquals(Object[] a1, Object[] a2) {
3771 if (a1 == a2)
3772 return true;
3773 if (a1 == null || a2==null)
3774 return false;
3775 int length = a1.length;
3776 if (a2.length != length)
3777 return false;
3778
3779 for (int i = 0; i < length; i++) {
3780 Object e1 = a1[i];
3781 Object e2 = a2[i];
3782
3783 if (e1 == e2)
3784 continue;
3785 if (e1 == null)
3786 return false;
3787
3788 // Figure out whether the two elements are equal
3789 boolean eq;
3790 if (e1 instanceof Object[] && e2 instanceof Object[])
3791 eq = deepEquals ((Object[]) e1, (Object[]) e2);
3792 else if (e1 instanceof byte[] && e2 instanceof byte[])
3793 eq = equals((byte[]) e1, (byte[]) e2);
3794 else if (e1 instanceof short[] && e2 instanceof short[])
3795 eq = equals((short[]) e1, (short[]) e2);
3796 else if (e1 instanceof int[] && e2 instanceof int[])
3797 eq = equals((int[]) e1, (int[]) e2);
3798 else if (e1 instanceof long[] && e2 instanceof long[])
3799 eq = equals((long[]) e1, (long[]) e2);
3800 else if (e1 instanceof char[] && e2 instanceof char[])
3801 eq = equals((char[]) e1, (char[]) e2);
3802 else if (e1 instanceof float[] && e2 instanceof float[])
3803 eq = equals((float[]) e1, (float[]) e2);
3804 else if (e1 instanceof double[] && e2 instanceof double[])
3805 eq = equals((double[]) e1, (double[]) e2);
3806 else if (e1 instanceof boolean[] && e2 instanceof boolean[])
3807 eq = equals((boolean[]) e1, (boolean[]) e2);
3808 else
3809 eq = e1.equals(e2);
3810
3811 if (!eq)
3812 return false;
3813 }
3814 return true;
3815 }
3816
3817 /**
3818 * Returns a string representation of the contents of the specified array.
3819 * The string representation consists of a list of the array's elements,
3820 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
3821 * separated by the characters <tt>", "</tt> (a comma followed by a
3822 * space). Elements are converted to strings as by
3823 * <tt>String.valueOf(long)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
3824 * is <tt>null</tt>.
3825 *
3826 * @param a the array whose string representation to return
3827 * @return a string representation of <tt>a</tt>
3828 * @since 1.5
3829 */
3830 public static String toString(long[] a) {
3831 if (a == null)
3832 return "null";
3833 int iMax = a.length - 1;
3834 if (iMax == -1)
3835 return "[]";
3836
3837 StringBuilder b = new StringBuilder();
3838 b.append('[');
3839 for (int i = 0; ; i++) {
3840 b.append(a[i]);
3841 if (i == iMax)
3842 return b.append(']').toString();
3843 b.append(", ");
3844 }
3845 }
3846
3847 /**
3848 * Returns a string representation of the contents of the specified array.
3849 * The string representation consists of a list of the array's elements,
3850 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
3851 * separated by the characters <tt>", "</tt> (a comma followed by a
3852 * space). Elements are converted to strings as by
3853 * <tt>String.valueOf(int)</tt>. Returns <tt>"null"</tt> if <tt>a</tt> is
3854 * <tt>null</tt>.
3855 *
3856 * @param a the array whose string representation to return
3857 * @return a string representation of <tt>a</tt>
3858 * @since 1.5
3859 */
3860 public static String toString(int[] a) {
3861 if (a == null)
3862 return "null";
3863 int iMax = a.length - 1;
3864 if (iMax == -1)
3865 return "[]";
3866
3867 StringBuilder b = new StringBuilder();
3868 b.append('[');
3869 for (int i = 0; ; i++) {
3870 b.append(a[i]);
3871 if (i == iMax)
3872 return b.append(']').toString();
3873 b.append(", ");
3874 }
3875 }
3876
3877 /**
3878 * Returns a string representation of the contents of the specified array.
3879 * The string representation consists of a list of the array's elements,
3880 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
3881 * separated by the characters <tt>", "</tt> (a comma followed by a
3882 * space). Elements are converted to strings as by
3883 * <tt>String.valueOf(short)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
3884 * is <tt>null</tt>.
3885 *
3886 * @param a the array whose string representation to return
3887 * @return a string representation of <tt>a</tt>
3888 * @since 1.5
3889 */
3890 public static String toString(short[] a) {
3891 if (a == null)
3892 return "null";
3893 int iMax = a.length - 1;
3894 if (iMax == -1)
3895 return "[]";
3896
3897 StringBuilder b = new StringBuilder();
3898 b.append('[');
3899 for (int i = 0; ; i++) {
3900 b.append(a[i]);
3901 if (i == iMax)
3902 return b.append(']').toString();
3903 b.append(", ");
3904 }
3905 }
3906
3907 /**
3908 * Returns a string representation of the contents of the specified array.
3909 * The string representation consists of a list of the array's elements,
3910 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
3911 * separated by the characters <tt>", "</tt> (a comma followed by a
3912 * space). Elements are converted to strings as by
3913 * <tt>String.valueOf(char)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
3914 * is <tt>null</tt>.
3915 *
3916 * @param a the array whose string representation to return
3917 * @return a string representation of <tt>a</tt>
3918 * @since 1.5
3919 */
3920 public static String toString(char[] a) {
3921 if (a == null)
3922 return "null";
3923 int iMax = a.length - 1;
3924 if (iMax == -1)
3925 return "[]";
3926
3927 StringBuilder b = new StringBuilder();
3928 b.append('[');
3929 for (int i = 0; ; i++) {
3930 b.append(a[i]);
3931 if (i == iMax)
3932 return b.append(']').toString();
3933 b.append(", ");
3934 }
3935 }
3936
3937 /**
3938 * Returns a string representation of the contents of the specified array.
3939 * The string representation consists of a list of the array's elements,
3940 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements
3941 * are separated by the characters <tt>", "</tt> (a comma followed
3942 * by a space). Elements are converted to strings as by
3943 * <tt>String.valueOf(byte)</tt>. Returns <tt>"null"</tt> if
3944 * <tt>a</tt> is <tt>null</tt>.
3945 *
3946 * @param a the array whose string representation to return
3947 * @return a string representation of <tt>a</tt>
3948 * @since 1.5
3949 */
3950 public static String toString(byte[] a) {
3951 if (a == null)
3952 return "null";
3953 int iMax = a.length - 1;
3954 if (iMax == -1)
3955 return "[]";
3956
3957 StringBuilder b = new StringBuilder();
3958 b.append('[');
3959 for (int i = 0; ; i++) {
3960 b.append(a[i]);
3961 if (i == iMax)
3962 return b.append(']').toString();
3963 b.append(", ");
3964 }
3965 }
3966
3967 /**
3968 * Returns a string representation of the contents of the specified array.
3969 * The string representation consists of a list of the array's elements,
3970 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
3971 * separated by the characters <tt>", "</tt> (a comma followed by a
3972 * space). Elements are converted to strings as by
3973 * <tt>String.valueOf(boolean)</tt>. Returns <tt>"null"</tt> if
3974 * <tt>a</tt> is <tt>null</tt>.
3975 *
3976 * @param a the array whose string representation to return
3977 * @return a string representation of <tt>a</tt>
3978 * @since 1.5
3979 */
3980 public static String toString(boolean[] a) {
3981 if (a == null)
3982 return "null";
3983 int iMax = a.length - 1;
3984 if (iMax == -1)
3985 return "[]";
3986
3987 StringBuilder b = new StringBuilder();
3988 b.append('[');
3989 for (int i = 0; ; i++) {
3990 b.append(a[i]);
3991 if (i == iMax)
3992 return b.append(']').toString();
3993 b.append(", ");
3994 }
3995 }
3996
3997 /**
3998 * Returns a string representation of the contents of the specified array.
3999 * The string representation consists of a list of the array's elements,
4000 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
4001 * separated by the characters <tt>", "</tt> (a comma followed by a
4002 * space). Elements are converted to strings as by
4003 * <tt>String.valueOf(float)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
4004 * is <tt>null</tt>.
4005 *
4006 * @param a the array whose string representation to return
4007 * @return a string representation of <tt>a</tt>
4008 * @since 1.5
4009 */
4010 public static String toString(float[] a) {
4011 if (a == null)
4012 return "null";
4013 int iMax = a.length - 1;
4014 if (iMax == -1)
4015 return "[]";
4016
4017 StringBuilder b = new StringBuilder();
4018 b.append('[');
4019 for (int i = 0; ; i++) {
4020 b.append(a[i]);
4021 if (i == iMax)
4022 return b.append(']').toString();
4023 b.append(", ");
4024 }
4025 }
4026
4027 /**
4028 * Returns a string representation of the contents of the specified array.
4029 * The string representation consists of a list of the array's elements,
4030 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
4031 * separated by the characters <tt>", "</tt> (a comma followed by a
4032 * space). Elements are converted to strings as by
4033 * <tt>String.valueOf(double)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
4034 * is <tt>null</tt>.
4035 *
4036 * @param a the array whose string representation to return
4037 * @return a string representation of <tt>a</tt>
4038 * @since 1.5
4039 */
4040 public static String toString(double[] a) {
4041 if (a == null)
4042 return "null";
4043 int iMax = a.length - 1;
4044 if (iMax == -1)
4045 return "[]";
4046
4047 StringBuilder b = new StringBuilder();
4048 b.append('[');
4049 for (int i = 0; ; i++) {
4050 b.append(a[i]);
4051 if (i == iMax)
4052 return b.append(']').toString();
4053 b.append(", ");
4054 }
4055 }
4056
4057 /**
4058 * Returns a string representation of the contents of the specified array.
4059 * If the array contains other arrays as elements, they are converted to
4060 * strings by the {@link Object#toString} method inherited from
4061 * <tt>Object</tt>, which describes their <i>identities</i> rather than
4062 * their contents.
4063 *
4064 * <p>The value returned by this method is equal to the value that would
4065 * be returned by <tt>Arrays.asList(a).toString()</tt>, unless <tt>a</tt>
4066 * is <tt>null</tt>, in which case <tt>"null"</tt> is returned.
4067 *
4068 * @param a the array whose string representation to return
4069 * @return a string representation of <tt>a</tt>
4070 * @see #deepToString(Object[])
4071 * @since 1.5
4072 */
4073 public static String toString(Object[] a) {
4074 if (a == null)
4075 return "null";
4076 int iMax = a.length - 1;
4077 if (iMax == -1)
4078 return "[]";
4079
4080 StringBuilder b = new StringBuilder();
4081 b.append('[');
4082 for (int i = 0; ; i++) {
4083 b.append(String.valueOf(a[i]));
4084 if (i == iMax)
4085 return b.append(']').toString();
4086 b.append(", ");
4087 }
4088 }
4089
4090 /**
4091 * Returns a string representation of the "deep contents" of the specified
4092 * array. If the array contains other arrays as elements, the string
4093 * representation contains their contents and so on. This method is
4094 * designed for converting multidimensional arrays to strings.
4095 *
4096 * <p>The string representation consists of a list of the array's
4097 * elements, enclosed in square brackets (<tt>"[]"</tt>). Adjacent
4098 * elements are separated by the characters <tt>", "</tt> (a comma
4099 * followed by a space). Elements are converted to strings as by
4100 * <tt>String.valueOf(Object)</tt>, unless they are themselves
4101 * arrays.
4102 *
4103 * <p>If an element <tt>e</tt> is an array of a primitive type, it is
4104 * converted to a string as by invoking the appropriate overloading of
4105 * <tt>Arrays.toString(e)</tt>. If an element <tt>e</tt> is an array of a
4106 * reference type, it is converted to a string as by invoking
4107 * this method recursively.
4108 *
4109 * <p>To avoid infinite recursion, if the specified array contains itself
4110 * as an element, or contains an indirect reference to itself through one
4111 * or more levels of arrays, the self-reference is converted to the string
4112 * <tt>"[...]"</tt>. For example, an array containing only a reference
4113 * to itself would be rendered as <tt>"[[...]]"</tt>.
4114 *
4115 * <p>This method returns <tt>"null"</tt> if the specified array
4116 * is <tt>null</tt>.
4117 *
4118 * @param a the array whose string representation to return
4119 * @return a string representation of <tt>a</tt>
4120 * @see #toString(Object[])
4121 * @since 1.5
4122 */
4123 public static String deepToString(Object[] a) {
4124 if (a == null)
4125 return "null";
4126
4127 int bufLen = 20 * a.length;
4128 if (a.length != 0 && bufLen <= 0)
4129 bufLen = Integer.MAX_VALUE;
4130 StringBuilder buf = new StringBuilder(bufLen);
4131 deepToString(a, buf, new HashSet<Object[]>());
4132 return buf.toString();
4133 }
4134
4135 private static void deepToString(Object[] a, StringBuilder buf,
4136 Set<Object[]> dejaVu) {
4137 if (a == null) {
4138 buf.append("null");
4139 return;
4140 }
4141 int iMax = a.length - 1;
4142 if (iMax == -1) {
4143 buf.append("[]");
4144 return;
4145 }
4146
4147 dejaVu.add(a);
4148 buf.append('[');
4149 for (int i = 0; ; i++) {
4150
4151 Object element = a[i];
4152 if (element == null) {
4153 buf.append("null");
4154 } else {
4155 Class eClass = element.getClass();
4156
4157 if (eClass.isArray()) {
4158 if (eClass == byte[].class)
4159 buf.append(toString((byte[]) element));
4160 else if (eClass == short[].class)
4161 buf.append(toString((short[]) element));
4162 else if (eClass == int[].class)
4163 buf.append(toString((int[]) element));
4164 else if (eClass == long[].class)
4165 buf.append(toString((long[]) element));
4166 else if (eClass == char[].class)
4167 buf.append(toString((char[]) element));
4168 else if (eClass == float[].class)
4169 buf.append(toString((float[]) element));
4170 else if (eClass == double[].class)
4171 buf.append(toString((double[]) element));
4172 else if (eClass == boolean[].class)
4173 buf.append(toString((boolean[]) element));
4174 else { // element is an array of object references
4175 if (dejaVu.contains(element))
4176 buf.append("[...]");
4177 else
4178 deepToString((Object[])element, buf, dejaVu);
4179 }
4180 } else { // element is non-null and not an array
4181 buf.append(element.toString());
4182 }
4183 }
4184 if (i == iMax)
4185 break;
4186 buf.append(", ");
4187 }
4188 buf.append(']');
4189 dejaVu.remove(a);
4190 }
4191 }
Save This Page