1 /*
2 * Copyright 1997-2008 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 * Old merge sort implementation can be selected (for
1070 * compatibility with broken comparators) using a system property.
1071 * Cannot be a static boolean in the enclosing class due to
1072 * circular dependencies. To be removed in a future release.
1073 */
1074 static final class LegacyMergeSort {
1075 private static final boolean userRequested =
1076 java.security.AccessController.doPrivileged(
1077 new sun.security.action.GetBooleanAction(
1078 "java.util.Arrays.useLegacyMergeSort")).booleanValue();
1079 }
1080
1081 /*
1082 * If this platform has an optimizing VM, check whether ComparableTimSort
1083 * offers any performance benefit over TimSort in conjunction with a
1084 * comparator that returns:
1085 * {@code ((Comparable)first).compareTo(Second)}.
1086 * If not, you are better off deleting ComparableTimSort to
1087 * eliminate the code duplication. In other words, the commented
1088 * out code below is the preferable implementation for sorting
1089 * arrays of Comparables if it offers sufficient performance.
1090 */
1091
1092 // /**
1093 // * A comparator that implements the natural ordering of a group of
1094 // * mutually comparable elements. Using this comparator saves us
1095 // * from duplicating most of the code in this file (one version for
1096 // * Comparables, one for explicit Comparators).
1097 // */
1098 // private static final Comparator<Object> NATURAL_ORDER =
1099 // new Comparator<Object>() {
1100 // @SuppressWarnings("unchecked")
1101 // public int compare(Object first, Object second) {
1102 // return ((Comparable<Object>)first).compareTo(second);
1103 // }
1104 // };
1105 //
1106 // public static void sort(Object[] a) {
1107 // sort(a, 0, a.length, NATURAL_ORDER);
1108 // }
1109 //
1110 // public static void sort(Object[] a, int fromIndex, int toIndex) {
1111 // sort(a, fromIndex, toIndex, NATURAL_ORDER);
1112 // }
1113
1114 /**
1115 * Sorts the specified array of objects into ascending order, according
1116 * to the {@linkplain Comparable natural ordering} of its elements.
1117 * All elements in the array must implement the {@link Comparable}
1118 * interface. Furthermore, all elements in the array must be
1119 * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must
1120 * not throw a {@code ClassCastException} for any elements {@code e1}
1121 * and {@code e2} in the array).
1122 *
1123 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
1124 * not be reordered as a result of the sort.
1125 *
1126 * <p>Implementation note: This implementation is a stable, adaptive,
1127 * iterative mergesort that requires far fewer than n lg(n) comparisons
1128 * when the input array is partially sorted, while offering the
1129 * performance of a traditional mergesort when the input array is
1130 * randomly ordered. If the input array is nearly sorted, the
1131 * implementation requires approximately n comparisons. Temporary
1132 * storage requirements vary from a small constant for nearly sorted
1133 * input arrays to n/2 object references for randomly ordered input
1134 * arrays.
1135 *
1136 * <p>The implementation takes equal advantage of ascending and
1137 * descending order in its input array, and can take advantage of
1138 * ascending and descending order in different parts of the the same
1139 * input array. It is well-suited to merging two or more sorted arrays:
1140 * simply concatenate the arrays and sort the resulting array.
1141 *
1142 * <p>The implementation was adapted from Tim Peters's list sort for Python
1143 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
1144 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
1145 * Sorting and Information Theoretic Complexity", in Proceedings of the
1146 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
1147 * January 1993.
1148 *
1149 * @param a the array to be sorted
1150 * @throws ClassCastException if the array contains elements that are not
1151 * <i>mutually comparable</i> (for example, strings and integers)
1152 * @throws IllegalArgumentException (optional) if the natural
1153 * ordering of the array elements is found to violate the
1154 * {@link Comparable} contract
1155 */
1156 public static void sort(Object[] a) {
1157 if (LegacyMergeSort.userRequested)
1158 legacyMergeSort(a);
1159 else
1160 ComparableTimSort.sort(a);
1161 }
1162
1163 /** To be removed in a future release. */
1164 private static void legacyMergeSort(Object[] a) {
1165 Object[] aux = a.clone();
1166 mergeSort(aux, a, 0, a.length, 0);
1167 }
1168
1169 /**
1170 * Sorts the specified range of the specified array of objects into
1171 * ascending order, according to the
1172 * {@linkplain Comparable natural ordering} of its
1173 * elements. The range to be sorted extends from index
1174 * {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive.
1175 * (If {@code fromIndex==toIndex}, the range to be sorted is empty.) All
1176 * elements in this range must implement the {@link Comparable}
1177 * interface. Furthermore, all elements in this range must be <i>mutually
1178 * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a
1179 * {@code ClassCastException} for any elements {@code e1} and
1180 * {@code e2} in the array).
1181 *
1182 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
1183 * not be reordered as a result of the sort.
1184 *
1185 * <p>Implementation note: This implementation is a stable, adaptive,
1186 * iterative mergesort that requires far fewer than n lg(n) comparisons
1187 * when the input array is partially sorted, while offering the
1188 * performance of a traditional mergesort when the input array is
1189 * randomly ordered. If the input array is nearly sorted, the
1190 * implementation requires approximately n comparisons. Temporary
1191 * storage requirements vary from a small constant for nearly sorted
1192 * input arrays to n/2 object references for randomly ordered input
1193 * arrays.
1194 *
1195 * <p>The implementation takes equal advantage of ascending and
1196 * descending order in its input array, and can take advantage of
1197 * ascending and descending order in different parts of the the same
1198 * input array. It is well-suited to merging two or more sorted arrays:
1199 * simply concatenate the arrays and sort the resulting array.
1200 *
1201 * <p>The implementation was adapted from Tim Peters's list sort for Python
1202 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
1203 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
1204 * Sorting and Information Theoretic Complexity", in Proceedings of the
1205 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
1206 * January 1993.
1207 *
1208 * @param a the array to be sorted
1209 * @param fromIndex the index of the first element (inclusive) to be
1210 * sorted
1211 * @param toIndex the index of the last element (exclusive) to be sorted
1212 * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
1213 * (optional) if the natural ordering of the array elements is
1214 * found to violate the {@link Comparable} contract
1215 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
1216 * {@code toIndex > a.length}
1217 * @throws ClassCastException if the array contains elements that are
1218 * not <i>mutually comparable</i> (for example, strings and
1219 * integers).
1220 */
1221 public static void sort(Object[] a, int fromIndex, int toIndex) {
1222 if (LegacyMergeSort.userRequested)
1223 legacyMergeSort(a, fromIndex, toIndex);
1224 else
1225 ComparableTimSort.sort(a, fromIndex, toIndex);
1226 }
1227
1228 /** To be removed in a future release. */
1229 private static void legacyMergeSort(Object[] a,
1230 int fromIndex, int toIndex) {
1231 rangeCheck(a.length, fromIndex, toIndex);
1232 Object[] aux = copyOfRange(a, fromIndex, toIndex);
1233 mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
1234 }
1235
1236 /**
1237 * Tuning parameter: list size at or below which insertion sort will be
1238 * used in preference to mergesort or quicksort.
1239 * To be removed in a future release.
1240 */
1241 private static final int INSERTIONSORT_THRESHOLD = 7;
1242
1243 /**
1244 * Src is the source array that starts at index 0
1245 * Dest is the (possibly larger) array destination with a possible offset
1246 * low is the index in dest to start sorting
1247 * high is the end index in dest to end sorting
1248 * off is the offset to generate corresponding low, high in src
1249 * To be removed in a future release.
1250 */
1251 private static void mergeSort(Object[] src,
1252 Object[] dest,
1253 int low,
1254 int high,
1255 int off) {
1256 int length = high - low;
1257
1258 // Insertion sort on smallest arrays
1259 if (length < INSERTIONSORT_THRESHOLD) {
1260 for (int i=low; i<high; i++)
1261 for (int j=i; j>low &&
1262 ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
1263 swap(dest, j, j-1);
1264 return;
1265 }
1266
1267 // Recursively sort halves of dest into src
1268 int destLow = low;
1269 int destHigh = high;
1270 low += off;
1271 high += off;
1272 int mid = (low + high) >>> 1;
1273 mergeSort(dest, src, low, mid, -off);
1274 mergeSort(dest, src, mid, high, -off);
1275
1276 // If list is already sorted, just copy from src to dest. This is an
1277 // optimization that results in faster sorts for nearly ordered lists.
1278 if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
1279 System.arraycopy(src, low, dest, destLow, length);
1280 return;
1281 }
1282
1283 // Merge sorted halves (now in src) into dest
1284 for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
1285 if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
1286 dest[i] = src[p++];
1287 else
1288 dest[i] = src[q++];
1289 }
1290 }
1291
1292 /**
1293 * Swaps x[a] with x[b].
1294 */
1295 private static void swap(Object[] x, int a, int b) {
1296 Object t = x[a];
1297 x[a] = x[b];
1298 x[b] = t;
1299 }
1300
1301 /**
1302 * Sorts the specified array of objects according to the order induced by
1303 * the specified comparator. All elements in the array must be
1304 * <i>mutually comparable</i> by the specified comparator (that is,
1305 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
1306 * for any elements {@code e1} and {@code e2} in the array).
1307 *
1308 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
1309 * not be reordered as a result of the sort.
1310 *
1311 * <p>Implementation note: This implementation is a stable, adaptive,
1312 * iterative mergesort that requires far fewer than n lg(n) comparisons
1313 * when the input array is partially sorted, while offering the
1314 * performance of a traditional mergesort when the input array is
1315 * randomly ordered. If the input array is nearly sorted, the
1316 * implementation requires approximately n comparisons. Temporary
1317 * storage requirements vary from a small constant for nearly sorted
1318 * input arrays to n/2 object references for randomly ordered input
1319 * arrays.
1320 *
1321 * <p>The implementation takes equal advantage of ascending and
1322 * descending order in its input array, and can take advantage of
1323 * ascending and descending order in different parts of the the same
1324 * input array. It is well-suited to merging two or more sorted arrays:
1325 * simply concatenate the arrays and sort the resulting array.
1326 *
1327 * <p>The implementation was adapted from Tim Peters's list sort for Python
1328 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
1329 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
1330 * Sorting and Information Theoretic Complexity", in Proceedings of the
1331 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
1332 * January 1993.
1333 *
1334 * @param a the array to be sorted
1335 * @param c the comparator to determine the order of the array. A
1336 * {@code null} value indicates that the elements'
1337 * {@linkplain Comparable natural ordering} should be used.
1338 * @throws ClassCastException if the array contains elements that are
1339 * not <i>mutually comparable</i> using the specified comparator
1340 * @throws IllegalArgumentException (optional) if the comparator is
1341 * found to violate the {@link Comparator} contract
1342 */
1343 public static <T> void sort(T[] a, Comparator<? super T> c) {
1344 if (LegacyMergeSort.userRequested)
1345 legacyMergeSort(a, c);
1346 else
1347 TimSort.sort(a, c);
1348 }
1349
1350 /** To be removed in a future release. */
1351 private static <T> void legacyMergeSort(T[] a, Comparator<? super T> c) {
1352 T[] aux = a.clone();
1353 if (c==null)
1354 mergeSort(aux, a, 0, a.length, 0);
1355 else
1356 mergeSort(aux, a, 0, a.length, 0, c);
1357 }
1358
1359 /**
1360 * Sorts the specified range of the specified array of objects according
1361 * to the order induced by the specified comparator. The range to be
1362 * sorted extends from index {@code fromIndex}, inclusive, to index
1363 * {@code toIndex}, exclusive. (If {@code fromIndex==toIndex}, the
1364 * range to be sorted is empty.) All elements in the range must be
1365 * <i>mutually comparable</i> by the specified comparator (that is,
1366 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
1367 * for any elements {@code e1} and {@code e2} in the range).
1368 *
1369 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
1370 * not be reordered as a result of the sort.
1371 *
1372 * <p>Implementation note: This implementation is a stable, adaptive,
1373 * iterative mergesort that requires far fewer than n lg(n) comparisons
1374 * when the input array is partially sorted, while offering the
1375 * performance of a traditional mergesort when the input array is
1376 * randomly ordered. If the input array is nearly sorted, the
1377 * implementation requires approximately n comparisons. Temporary
1378 * storage requirements vary from a small constant for nearly sorted
1379 * input arrays to n/2 object references for randomly ordered input
1380 * arrays.
1381 *
1382 * <p>The implementation takes equal advantage of ascending and
1383 * descending order in its input array, and can take advantage of
1384 * ascending and descending order in different parts of the the same
1385 * input array. It is well-suited to merging two or more sorted arrays:
1386 * simply concatenate the arrays and sort the resulting array.
1387 *
1388 * <p>The implementation was adapted from Tim Peters's list sort for Python
1389 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
1390 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
1391 * Sorting and Information Theoretic Complexity", in Proceedings of the
1392 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
1393 * January 1993.
1394 *
1395 * @param a the array to be sorted
1396 * @param fromIndex the index of the first element (inclusive) to be
1397 * sorted
1398 * @param toIndex the index of the last element (exclusive) to be sorted
1399 * @param c the comparator to determine the order of the array. A
1400 * {@code null} value indicates that the elements'
1401 * {@linkplain Comparable natural ordering} should be used.
1402 * @throws ClassCastException if the array contains elements that are not
1403 * <i>mutually comparable</i> using the specified comparator.
1404 * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
1405 * (optional) if the comparator is found to violate the
1406 * {@link Comparator} contract
1407 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
1408 * {@code toIndex > a.length}
1409 */
1410 public static <T> void sort(T[] a, int fromIndex, int toIndex,
1411 Comparator<? super T> c) {
1412 if (LegacyMergeSort.userRequested)
1413 legacyMergeSort(a, fromIndex, toIndex, c);
1414 else
1415 TimSort.sort(a, fromIndex, toIndex, c);
1416 }
1417
1418 /** To be removed in a future release. */
1419 private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex,
1420 Comparator<? super T> c) {
1421 rangeCheck(a.length, fromIndex, toIndex);
1422 T[] aux = copyOfRange(a, fromIndex, toIndex);
1423 if (c==null)
1424 mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
1425 else
1426 mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
1427 }
1428
1429 /**
1430 * Src is the source array that starts at index 0
1431 * Dest is the (possibly larger) array destination with a possible offset
1432 * low is the index in dest to start sorting
1433 * high is the end index in dest to end sorting
1434 * off is the offset into src corresponding to low in dest
1435 * To be removed in a future release.
1436 */
1437 private static void mergeSort(Object[] src,
1438 Object[] dest,
1439 int low, int high, int off,
1440 Comparator c) {
1441 int length = high - low;
1442
1443 // Insertion sort on smallest arrays
1444 if (length < INSERTIONSORT_THRESHOLD) {
1445 for (int i=low; i<high; i++)
1446 for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
1447 swap(dest, j, j-1);
1448 return;
1449 }
1450
1451 // Recursively sort halves of dest into src
1452 int destLow = low;
1453 int destHigh = high;
1454 low += off;
1455 high += off;
1456 int mid = (low + high) >>> 1;
1457 mergeSort(dest, src, low, mid, -off, c);
1458 mergeSort(dest, src, mid, high, -off, c);
1459
1460 // If list is already sorted, just copy from src to dest. This is an
1461 // optimization that results in faster sorts for nearly ordered lists.
1462 if (c.compare(src[mid-1], src[mid]) <= 0) {
1463 System.arraycopy(src, low, dest, destLow, length);
1464 return;
1465 }
1466
1467 // Merge sorted halves (now in src) into dest
1468 for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
1469 if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
1470 dest[i] = src[p++];
1471 else
1472 dest[i] = src[q++];
1473 }
1474 }
1475
1476 /**
1477 * Check that fromIndex and toIndex are in range, and throw an
1478 * appropriate exception if they aren't.
1479 */
1480 private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) {
1481 if (fromIndex > toIndex)
1482 throw new IllegalArgumentException("fromIndex(" + fromIndex +
1483 ") > toIndex(" + toIndex+")");
1484 if (fromIndex < 0)
1485 throw new ArrayIndexOutOfBoundsException(fromIndex);
1486 if (toIndex > arrayLen)
1487 throw new ArrayIndexOutOfBoundsException(toIndex);
1488 }
1489
1490 // Searching
1491
1492 /**
1493 * Searches the specified array of longs for the specified value using the
1494 * binary search algorithm. The array must be sorted (as
1495 * by the {@link #sort(long[])} method) prior to making this call. If it
1496 * is not sorted, the results are undefined. If the array contains
1497 * multiple elements with the specified value, there is no guarantee which
1498 * one will be found.
1499 *
1500 * @param a the array to be searched
1501 * @param key the value to be searched for
1502 * @return index of the search key, if it is contained in the array;
1503 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1504 * <i>insertion point</i> is defined as the point at which the
1505 * key would be inserted into the array: the index of the first
1506 * element greater than the key, or <tt>a.length</tt> if all
1507 * elements in the array are less than the specified key. Note
1508 * that this guarantees that the return value will be >= 0 if
1509 * and only if the key is found.
1510 */
1511 public static int binarySearch(long[] a, long key) {
1512 return binarySearch0(a, 0, a.length, key);
1513 }
1514
1515 /**
1516 * Searches a range of
1517 * the specified array of longs for the specified value using the
1518 * binary search algorithm.
1519 * The range must be sorted (as
1520 * by the {@link #sort(long[], int, int)} method)
1521 * prior to making this call. If it
1522 * is not sorted, the results are undefined. If the range contains
1523 * multiple elements with the specified value, there is no guarantee which
1524 * one will be found.
1525 *
1526 * @param a the array to be searched
1527 * @param fromIndex the index of the first element (inclusive) to be
1528 * searched
1529 * @param toIndex the index of the last element (exclusive) to be searched
1530 * @param key the value to be searched for
1531 * @return index of the search key, if it is contained in the array
1532 * within the specified range;
1533 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1534 * <i>insertion point</i> is defined as the point at which the
1535 * key would be inserted into the array: the index of the first
1536 * element in the range greater than the key,
1537 * or <tt>toIndex</tt> if all
1538 * elements in the range are less than the specified key. Note
1539 * that this guarantees that the return value will be >= 0 if
1540 * and only if the key is found.
1541 * @throws IllegalArgumentException
1542 * if {@code fromIndex > toIndex}
1543 * @throws ArrayIndexOutOfBoundsException
1544 * if {@code fromIndex < 0 or toIndex > a.length}
1545 * @since 1.6
1546 */
1547 public static int binarySearch(long[] a, int fromIndex, int toIndex,
1548 long key) {
1549 rangeCheck(a.length, fromIndex, toIndex);
1550 return binarySearch0(a, fromIndex, toIndex, key);
1551 }
1552
1553 // Like public version, but without range checks.
1554 private static int binarySearch0(long[] a, int fromIndex, int toIndex,
1555 long key) {
1556 int low = fromIndex;
1557 int high = toIndex - 1;
1558
1559 while (low <= high) {
1560 int mid = (low + high) >>> 1;
1561 long midVal = a[mid];
1562
1563 if (midVal < key)
1564 low = mid + 1;
1565 else if (midVal > key)
1566 high = mid - 1;
1567 else
1568 return mid; // key found
1569 }
1570 return -(low + 1); // key not found.
1571 }
1572
1573 /**
1574 * Searches the specified array of ints for the specified value using the
1575 * binary search algorithm. The array must be sorted (as
1576 * by the {@link #sort(int[])} method) prior to making this call. If it
1577 * is not sorted, the results are undefined. If the array contains
1578 * multiple elements with the specified value, there is no guarantee which
1579 * one will be found.
1580 *
1581 * @param a the array to be searched
1582 * @param key the value to be searched for
1583 * @return index of the search key, if it is contained in the array;
1584 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1585 * <i>insertion point</i> is defined as the point at which the
1586 * key would be inserted into the array: the index of the first
1587 * element greater than the key, or <tt>a.length</tt> if all
1588 * elements in the array are less than the specified key. Note
1589 * that this guarantees that the return value will be >= 0 if
1590 * and only if the key is found.
1591 */
1592 public static int binarySearch(int[] a, int key) {
1593 return binarySearch0(a, 0, a.length, key);
1594 }
1595
1596 /**
1597 * Searches a range of
1598 * the specified array of ints for the specified value using the
1599 * binary search algorithm.
1600 * The range must be sorted (as
1601 * by the {@link #sort(int[], int, int)} method)
1602 * prior to making this call. If it
1603 * is not sorted, the results are undefined. If the range contains
1604 * multiple elements with the specified value, there is no guarantee which
1605 * one will be found.
1606 *
1607 * @param a the array to be searched
1608 * @param fromIndex the index of the first element (inclusive) to be
1609 * searched
1610 * @param toIndex the index of the last element (exclusive) to be searched
1611 * @param key the value to be searched for
1612 * @return index of the search key, if it is contained in the array
1613 * within the specified range;
1614 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1615 * <i>insertion point</i> is defined as the point at which the
1616 * key would be inserted into the array: the index of the first
1617 * element in the range greater than the key,
1618 * or <tt>toIndex</tt> if all
1619 * elements in the range are less than the specified key. Note
1620 * that this guarantees that the return value will be >= 0 if
1621 * and only if the key is found.
1622 * @throws IllegalArgumentException
1623 * if {@code fromIndex > toIndex}
1624 * @throws ArrayIndexOutOfBoundsException
1625 * if {@code fromIndex < 0 or toIndex > a.length}
1626 * @since 1.6
1627 */
1628 public static int binarySearch(int[] a, int fromIndex, int toIndex,
1629 int key) {
1630 rangeCheck(a.length, fromIndex, toIndex);
1631 return binarySearch0(a, fromIndex, toIndex, key);
1632 }
1633
1634 // Like public version, but without range checks.
1635 private static int binarySearch0(int[] a, int fromIndex, int toIndex,
1636 int key) {
1637 int low = fromIndex;
1638 int high = toIndex - 1;
1639
1640 while (low <= high) {
1641 int mid = (low + high) >>> 1;
1642 int midVal = a[mid];
1643
1644 if (midVal < key)
1645 low = mid + 1;
1646 else if (midVal > key)
1647 high = mid - 1;
1648 else
1649 return mid; // key found
1650 }
1651 return -(low + 1); // key not found.
1652 }
1653
1654 /**
1655 * Searches the specified array of shorts for the specified value using
1656 * the binary search algorithm. The array must be sorted
1657 * (as by the {@link #sort(short[])} method) prior to making this call. If
1658 * it is not sorted, the results are undefined. If the array contains
1659 * multiple elements with the specified value, there is no guarantee which
1660 * one will be found.
1661 *
1662 * @param a the array to be searched
1663 * @param key the value to be searched for
1664 * @return index of the search key, if it is contained in the array;
1665 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1666 * <i>insertion point</i> is defined as the point at which the
1667 * key would be inserted into the array: the index of the first
1668 * element greater than the key, or <tt>a.length</tt> if all
1669 * elements in the array are less than the specified key. Note
1670 * that this guarantees that the return value will be >= 0 if
1671 * and only if the key is found.
1672 */
1673 public static int binarySearch(short[] a, short key) {
1674 return binarySearch0(a, 0, a.length, key);
1675 }
1676
1677 /**
1678 * Searches a range of
1679 * the specified array of shorts for the specified value using
1680 * the binary search algorithm.
1681 * The range must be sorted
1682 * (as by the {@link #sort(short[], int, int)} method)
1683 * prior to making this call. If
1684 * it is not sorted, the results are undefined. If the range contains
1685 * multiple elements with the specified value, there is no guarantee which
1686 * one will be found.
1687 *
1688 * @param a the array to be searched
1689 * @param fromIndex the index of the first element (inclusive) to be
1690 * searched
1691 * @param toIndex the index of the last element (exclusive) to be searched
1692 * @param key the value to be searched for
1693 * @return index of the search key, if it is contained in the array
1694 * within the specified range;
1695 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1696 * <i>insertion point</i> is defined as the point at which the
1697 * key would be inserted into the array: the index of the first
1698 * element in the range greater than the key,
1699 * or <tt>toIndex</tt> if all
1700 * elements in the range are less than the specified key. Note
1701 * that this guarantees that the return value will be >= 0 if
1702 * and only if the key is found.
1703 * @throws IllegalArgumentException
1704 * if {@code fromIndex > toIndex}
1705 * @throws ArrayIndexOutOfBoundsException
1706 * if {@code fromIndex < 0 or toIndex > a.length}
1707 * @since 1.6
1708 */
1709 public static int binarySearch(short[] a, int fromIndex, int toIndex,
1710 short key) {
1711 rangeCheck(a.length, fromIndex, toIndex);
1712 return binarySearch0(a, fromIndex, toIndex, key);
1713 }
1714
1715 // Like public version, but without range checks.
1716 private static int binarySearch0(short[] a, int fromIndex, int toIndex,
1717 short key) {
1718 int low = fromIndex;
1719 int high = toIndex - 1;
1720
1721 while (low <= high) {
1722 int mid = (low + high) >>> 1;
1723 short midVal = a[mid];
1724
1725 if (midVal < key)
1726 low = mid + 1;
1727 else if (midVal > key)
1728 high = mid - 1;
1729 else
1730 return mid; // key found
1731 }
1732 return -(low + 1); // key not found.
1733 }
1734
1735 /**
1736 * Searches the specified array of chars for the specified value using the
1737 * binary search algorithm. The array must be sorted (as
1738 * by the {@link #sort(char[])} method) prior to making this call. If it
1739 * is not sorted, the results are undefined. If the array contains
1740 * multiple elements with the specified value, there is no guarantee which
1741 * one will be found.
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(char[] a, char key) {
1755 return binarySearch0(a, 0, a.length, key);
1756 }
1757
1758 /**
1759 * Searches a range of
1760 * the specified array of chars for the specified value using the
1761 * binary search algorithm.
1762 * The range must be sorted (as
1763 * by the {@link #sort(char[], int, int)} method)
1764 * prior to making this call. If it
1765 * 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.
1768 *
1769 * @param a the array to be searched
1770 * @param fromIndex the index of the first element (inclusive) to be
1771 * searched
1772 * @param toIndex the index of the last element (exclusive) to be searched
1773 * @param key the value to be searched for
1774 * @return index of the search key, if it is contained in the array
1775 * within the specified range;
1776 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1777 * <i>insertion point</i> is defined as the point at which the
1778 * key would be inserted into the array: the index of the first
1779 * element in the range greater than the key,
1780 * or <tt>toIndex</tt> if all
1781 * elements in the range are less than the specified key. Note
1782 * that this guarantees that the return value will be >= 0 if
1783 * and only if the key is found.
1784 * @throws IllegalArgumentException
1785 * if {@code fromIndex > toIndex}
1786 * @throws ArrayIndexOutOfBoundsException
1787 * if {@code fromIndex < 0 or toIndex > a.length}
1788 * @since 1.6
1789 */
1790 public static int binarySearch(char[] a, int fromIndex, int toIndex,
1791 char key) {
1792 rangeCheck(a.length, fromIndex, toIndex);
1793 return binarySearch0(a, fromIndex, toIndex, key);
1794 }
1795
1796 // Like public version, but without range checks.
1797 private static int binarySearch0(char[] a, int fromIndex, int toIndex,
1798 char key) {
1799 int low = fromIndex;
1800 int high = toIndex - 1;
1801
1802 while (low <= high) {
1803 int mid = (low + high) >>> 1;
1804 char midVal = a[mid];
1805
1806 if (midVal < key)
1807 low = mid + 1;
1808 else if (midVal > key)
1809 high = mid - 1;
1810 else
1811 return mid; // key found
1812 }
1813 return -(low + 1); // key not found.
1814 }
1815
1816 /**
1817 * Searches the specified array of bytes for the specified value using the
1818 * binary search algorithm. The array must be sorted (as
1819 * by the {@link #sort(byte[])} method) prior to making this call. If it
1820 * is not sorted, the results are undefined. If the array contains
1821 * multiple elements with the specified value, there is no guarantee which
1822 * one will be found.
1823 *
1824 * @param a the array to be searched
1825 * @param key the value to be searched for
1826 * @return index of the search key, if it is contained in the array;
1827 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1828 * <i>insertion point</i> is defined as the point at which the
1829 * key would be inserted into the array: the index of the first
1830 * element greater than the key, or <tt>a.length</tt> if all
1831 * elements in the array are less than the specified key. Note
1832 * that this guarantees that the return value will be >= 0 if
1833 * and only if the key is found.
1834 */
1835 public static int binarySearch(byte[] a, byte key) {
1836 return binarySearch0(a, 0, a.length, key);
1837 }
1838
1839 /**
1840 * Searches a range of
1841 * the specified array of bytes for the specified value using the
1842 * binary search algorithm.
1843 * The range must be sorted (as
1844 * by the {@link #sort(byte[], int, int)} method)
1845 * prior to making this call. If it
1846 * is not sorted, the results are undefined. If the range contains
1847 * multiple elements with the specified value, there is no guarantee which
1848 * one will be found.
1849 *
1850 * @param a the array to be searched
1851 * @param fromIndex the index of the first element (inclusive) to be
1852 * searched
1853 * @param toIndex the index of the last element (exclusive) to be searched
1854 * @param key the value to be searched for
1855 * @return index of the search key, if it is contained in the array
1856 * within the specified range;
1857 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1858 * <i>insertion point</i> is defined as the point at which the
1859 * key would be inserted into the array: the index of the first
1860 * element in the range greater than the key,
1861 * or <tt>toIndex</tt> if all
1862 * elements in the range are less than the specified key. Note
1863 * that this guarantees that the return value will be >= 0 if
1864 * and only if the key is found.
1865 * @throws IllegalArgumentException
1866 * if {@code fromIndex > toIndex}
1867 * @throws ArrayIndexOutOfBoundsException
1868 * if {@code fromIndex < 0 or toIndex > a.length}
1869 * @since 1.6
1870 */
1871 public static int binarySearch(byte[] a, int fromIndex, int toIndex,
1872 byte key) {
1873 rangeCheck(a.length, fromIndex, toIndex);
1874 return binarySearch0(a, fromIndex, toIndex, key);
1875 }
1876
1877 // Like public version, but without range checks.
1878 private static int binarySearch0(byte[] a, int fromIndex, int toIndex,
1879 byte key) {
1880 int low = fromIndex;
1881 int high = toIndex - 1;
1882
1883 while (low <= high) {
1884 int mid = (low + high) >>> 1;
1885 byte midVal = a[mid];
1886
1887 if (midVal < key)
1888 low = mid + 1;
1889 else if (midVal > key)
1890 high = mid - 1;
1891 else
1892 return mid; // key found
1893 }
1894 return -(low + 1); // key not found.
1895 }
1896
1897 /**
1898 * Searches the specified array of doubles for the specified value using
1899 * the binary search algorithm. The array must be sorted
1900 * (as by the {@link #sort(double[])} method) prior to making this call.
1901 * If it is not sorted, the results are undefined. If the array contains
1902 * multiple elements with the specified value, there is no guarantee which
1903 * one will be found. This method considers all NaN values to be
1904 * equivalent and equal.
1905 *
1906 * @param a the array to be searched
1907 * @param key the value to be searched for
1908 * @return index of the search key, if it is contained in the array;
1909 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1910 * <i>insertion point</i> is defined as the point at which the
1911 * key would be inserted into the array: the index of the first
1912 * element greater than the key, or <tt>a.length</tt> if all
1913 * elements in the array are less than the specified key. Note
1914 * that this guarantees that the return value will be >= 0 if
1915 * and only if the key is found.
1916 */
1917 public static int binarySearch(double[] a, double key) {
1918 return binarySearch0(a, 0, a.length, key);
1919 }
1920
1921 /**
1922 * Searches a range of
1923 * the specified array of doubles for the specified value using
1924 * the binary search algorithm.
1925 * The range must be sorted
1926 * (as by the {@link #sort(double[], int, int)} method)
1927 * prior to making this call.
1928 * If it is not sorted, the results are undefined. If the range contains
1929 * multiple elements with the specified value, there is no guarantee which
1930 * one will be found. This method considers all NaN values to be
1931 * equivalent and equal.
1932 *
1933 * @param a the array to be searched
1934 * @param fromIndex the index of the first element (inclusive) to be
1935 * searched
1936 * @param toIndex the index of the last element (exclusive) to be searched
1937 * @param key the value to be searched for
1938 * @return index of the search key, if it is contained in the array
1939 * within the specified range;
1940 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1941 * <i>insertion point</i> is defined as the point at which the
1942 * key would be inserted into the array: the index of the first
1943 * element in the range greater than the key,
1944 * or <tt>toIndex</tt> if all
1945 * elements in the range are less than the specified key. Note
1946 * that this guarantees that the return value will be >= 0 if
1947 * and only if the key is found.
1948 * @throws IllegalArgumentException
1949 * if {@code fromIndex > toIndex}
1950 * @throws ArrayIndexOutOfBoundsException
1951 * if {@code fromIndex < 0 or toIndex > a.length}
1952 * @since 1.6
1953 */
1954 public static int binarySearch(double[] a, int fromIndex, int toIndex,
1955 double key) {
1956 rangeCheck(a.length, fromIndex, toIndex);
1957 return binarySearch0(a, fromIndex, toIndex, key);
1958 }
1959
1960 // Like public version, but without range checks.
1961 private static int binarySearch0(double[] a, int fromIndex, int toIndex,
1962 double key) {
1963 int low = fromIndex;
1964 int high = toIndex - 1;
1965
1966 while (low <= high) {
1967 int mid = (low + high) >>> 1;
1968 double midVal = a[mid];
1969
1970 if (midVal < key)
1971 low = mid + 1; // Neither val is NaN, thisVal is smaller
1972 else if (midVal > key)
1973 high = mid - 1; // Neither val is NaN, thisVal is larger
1974 else {
1975 long midBits = Double.doubleToLongBits(midVal);
1976 long keyBits = Double.doubleToLongBits(key);
1977 if (midBits == keyBits) // Values are equal
1978 return mid; // Key found
1979 else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
1980 low = mid + 1;
1981 else // (0.0, -0.0) or (NaN, !NaN)
1982 high = mid - 1;
1983 }
1984 }
1985 return -(low + 1); // key not found.
1986 }
1987
1988 /**
1989 * Searches the specified array of floats for the specified value using
1990 * the binary search algorithm. The array must be sorted
1991 * (as by the {@link #sort(float[])} method) prior to making this call. If
1992 * it is not sorted, the results are undefined. If the array contains
1993 * multiple elements with the specified value, there is no guarantee which
1994 * one will be found. This method considers all NaN values to be
1995 * equivalent and equal.
1996 *
1997 * @param a the array to be searched
1998 * @param key the value to be searched for
1999 * @return index of the search key, if it is contained in the array;
2000 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
2001 * <i>insertion point</i> is defined as the point at which the
2002 * key would be inserted into the array: the index of the first
2003 * element greater than the key, or <tt>a.length</tt> if all
2004 * elements in the array are less than the specified key. Note
2005 * that this guarantees that the return value will be >= 0 if
2006 * and only if the key is found.
2007 */
2008 public static int binarySearch(float[] a, float key) {
2009 return binarySearch0(a, 0, a.length, key);
2010 }
2011
2012 /**
2013 * Searches a range of
2014 * the specified array of floats for the specified value using
2015 * the binary search algorithm.
2016 * The range must be sorted
2017 * (as by the {@link #sort(float[], int, int)} method)
2018 * prior to making this call. If
2019 * it is not sorted, the results are undefined. If the range contains
2020 * multiple elements with the specified value, there is no guarantee which
2021 * one will be found. This method considers all NaN values to be
2022 * equivalent and equal.
2023 *
2024 * @param a the array to be searched
2025 * @param fromIndex the index of the first element (inclusive) to be
2026 * searched
2027 * @param toIndex the index of the last element (exclusive) to be searched
2028 * @param key the value to be searched for
2029 * @return index of the search key, if it is contained in the array
2030 * within the specified range;
2031 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
2032 * <i>insertion point</i> is defined as the point at which the
2033 * key would be inserted into the array: the index of the first
2034 * element in the range greater than the key,
2035 * or <tt>toIndex</tt> if all
2036 * elements in the range are less than the specified key. Note
2037 * that this guarantees that the return value will be >= 0 if
2038 * and only if the key is found.
2039 * @throws IllegalArgumentException
2040 * if {@code fromIndex > toIndex}
2041 * @throws ArrayIndexOutOfBoundsException
2042 * if {@code fromIndex < 0 or toIndex > a.length}
2043 * @since 1.6
2044 */
2045 public static int binarySearch(float[] a, int fromIndex, int toIndex,
2046 float key) {
2047 rangeCheck(a.length, fromIndex, toIndex);
2048 return binarySearch0(a, fromIndex, toIndex, key);
2049 }
2050
2051 // Like public version, but without range checks.
2052 private static int binarySearch0(float[] a, int fromIndex, int toIndex,
2053 float key) {
2054 int low = fromIndex;
2055 int high = toIndex - 1;
2056
2057 while (low <= high) {
2058 int mid = (low + high) >>> 1;
2059 float midVal = a[mid];
2060
2061 if (midVal < key)
2062 low = mid + 1; // Neither val is NaN, thisVal is smaller
2063 else if (midVal > key)
2064 high = mid - 1; // Neither val is NaN, thisVal is larger
2065 else {
2066 int midBits = Float.floatToIntBits(midVal);
2067 int keyBits = Float.floatToIntBits(key);
2068 if (midBits == keyBits) // Values are equal
2069 return mid; // Key found
2070 else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
2071 low = mid + 1;
2072 else // (0.0, -0.0) or (NaN, !NaN)
2073 high = mid - 1;
2074 }
2075 }
2076 return -(low + 1); // key not found.
2077 }
2078
2079
2080 /**
2081 * Searches the specified array for the specified object using the binary
2082 * search algorithm. The array must be sorted into ascending order
2083 * according to the
2084 * {@linkplain Comparable natural ordering}
2085 * of its elements (as by the
2086 * {@link #sort(Object[])} method) prior to making this call.
2087 * If it is not sorted, the results are undefined.
2088 * (If the array contains elements that are not mutually comparable (for
2089 * example, strings and integers), it <i>cannot</i> be sorted according
2090 * to the natural ordering of its elements, hence results are undefined.)
2091 * If the array contains multiple
2092 * elements equal to the specified object, there is no guarantee which
2093 * one will be found.
2094 *
2095 * @param a the array to be searched
2096 * @param key the value to be searched for
2097 * @return index of the search key, if it is contained in the array;
2098 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
2099 * <i>insertion point</i> is defined as the point at which the
2100 * key would be inserted into the array: the index of the first
2101 * element greater than the key, or <tt>a.length</tt> if all
2102 * elements in the array are less than the specified key. Note
2103 * that this guarantees that the return value will be >= 0 if
2104 * and only if the key is found.
2105 * @throws ClassCastException if the search key is not comparable to the
2106 * elements of the array.
2107 */
2108 public static int binarySearch(Object[] a, Object key) {
2109 return binarySearch0(a, 0, a.length, key);
2110 }
2111
2112 /**
2113 * Searches a range of
2114 * the specified array for the specified object using the binary
2115 * search algorithm.
2116 * The range must be sorted into ascending order
2117 * according to the
2118 * {@linkplain Comparable natural ordering}
2119 * of its elements (as by the
2120 * {@link #sort(Object[], int, int)} method) prior to making this
2121 * call. If it is not sorted, the results are undefined.
2122 * (If the range contains elements that are not mutually comparable (for
2123 * example, strings and integers), it <i>cannot</i> be sorted according
2124 * to the natural ordering of its elements, hence results are undefined.)
2125 * If the range contains multiple
2126 * elements equal to the specified object, there is no guarantee which
2127 * one will be found.
2128 *
2129 * @param a the array to be searched
2130 * @param fromIndex the index of the first element (inclusive) to be
2131 * searched
2132 * @param toIndex the index of the last element (exclusive) to be searched
2133 * @param key the value to be searched for
2134 * @return index of the search key, if it is contained in the array
2135 * within the specified range;
2136 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
2137 * <i>insertion point</i> is defined as the point at which the
2138 * key would be inserted into the array: the index of the first
2139 * element in the range greater than the key,
2140 * or <tt>toIndex</tt> if all
2141 * elements in the range are less than the specified key. Note
2142 * that this guarantees that the return value will be >= 0 if
2143 * and only if the key is found.
2144 * @throws ClassCastException if the search key is not comparable to the
2145 * elements of the array within the specified range.
2146 * @throws IllegalArgumentException
2147 * if {@code fromIndex > toIndex}
2148 * @throws ArrayIndexOutOfBoundsException
2149 * if {@code fromIndex < 0 or toIndex > a.length}
2150 * @since 1.6
2151 */
2152 public static int binarySearch(Object[] a, int fromIndex, int toIndex,
2153 Object key) {
2154 rangeCheck(a.length, fromIndex, toIndex);
2155 return binarySearch0(a, fromIndex, toIndex, key);
2156 }
2157
2158 // Like public version, but without range checks.
2159 private static int binarySearch0(Object[] a, int fromIndex, int toIndex,
2160 Object key) {
2161 int low = fromIndex;
2162 int high = toIndex - 1;
2163
2164 while (low <= high) {
2165 int mid = (low + high) >>> 1;
2166 Comparable midVal = (Comparable)a[mid];
2167 int cmp = midVal.compareTo(key);
2168
2169 if (cmp < 0)
2170 low = mid + 1;
2171 else if (cmp > 0)
2172 high = mid - 1;
2173 else
2174 return mid; // key found
2175 }
2176 return -(low + 1); // key not found.
2177 }
2178
2179 /**
2180 * Searches the specified array for the specified object using the binary
2181 * search algorithm. The array must be sorted into ascending order
2182 * according to the specified comparator (as by the
2183 * {@link #sort(Object[], Comparator) sort(T[], Comparator)}
2184 * method) prior to making this call. If it is
2185 * not sorted, the results are undefined.
2186 * If the array contains multiple
2187 * elements equal to the specified object, there is no guarantee which one
2188 * will be found.
2189 *
2190 * @param a the array to be searched
2191 * @param key the value to be searched for
2192 * @param c the comparator by which the array is ordered. A
2193 * <tt>null</tt> value indicates that the elements'
2194 * {@linkplain Comparable natural ordering} should be used.
2195 * @return index of the search key, if it is contained in the array;
2196 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
2197 * <i>insertion point</i> is defined as the point at which the
2198 * key would be inserted into the array: the index of the first
2199 * element greater than the key, or <tt>a.length</tt> if all
2200 * elements in the array are less than the specified key. Note
2201 * that this guarantees that the return value will be >= 0 if
2202 * and only if the key is found.
2203 * @throws ClassCastException if the array contains elements that are not
2204 * <i>mutually comparable</i> using the specified comparator,
2205 * or the search key is not comparable to the
2206 * elements of the array using this comparator.
2207 */
2208 public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) {
2209 return binarySearch0(a, 0, a.length, key, c);
2210 }
2211
2212 /**
2213 * Searches a range of
2214 * the specified array for the specified object using the binary
2215 * search algorithm.
2216 * The range must be sorted into ascending order
2217 * according to the specified comparator (as by the
2218 * {@link #sort(Object[], int, int, Comparator)
2219 * sort(T[], int, int, Comparator)}
2220 * method) prior to making this call.
2221 * If it is not sorted, the results are undefined.
2222 * If the range contains multiple elements equal to the specified object,
2223 * there is no guarantee which one will be found.
2224 *
2225 * @param a the array to be searched
2226 * @param fromIndex the index of the first element (inclusive) to be
2227 * searched
2228 * @param toIndex the index of the last element (exclusive) to be searched
2229 * @param key the value to be searched for
2230 * @param c the comparator by which the array is ordered. A
2231 * <tt>null</tt> value indicates that the elements'
2232 * {@linkplain Comparable natural ordering} should be used.
2233 * @return index of the search key, if it is contained in the array
2234 * within the specified range;
2235 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
2236 * <i>insertion point</i> is defined as the point at which the
2237 * key would be inserted into the array: the index of the first
2238 * element in the range greater than the key,
2239 * or <tt>toIndex</tt> if all
2240 * elements in the range are less than the specified key. Note
2241 * that this guarantees that the return value will be >= 0 if
2242 * and only if the key is found.
2243 * @throws ClassCastException if the range contains elements that are not
2244 * <i>mutually comparable</i> using the specified comparator,
2245 * or the search key is not comparable to the
2246 * elements in the range using this comparator.
2247 * @throws IllegalArgumentException
2248 * if {@code fromIndex > toIndex}
2249 * @throws ArrayIndexOutOfBoundsException
2250 * if {@code fromIndex < 0 or toIndex > a.length}
2251 * @since 1.6
2252 */
2253 public static <T> int binarySearch(T[] a, int fromIndex, int toIndex,
2254 T key, Comparator<? super T> c) {
2255 rangeCheck(a.length, fromIndex, toIndex);
2256 return binarySearch0(a, fromIndex, toIndex, key, c);
2257 }
2258
2259 // Like public version, but without range checks.
2260 private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex,
2261 T key, Comparator<? super T> c) {
2262 if (c == null) {
2263 return binarySearch0(a, fromIndex, toIndex, key);
2264 }
2265 int low = fromIndex;
2266 int high = toIndex - 1;
2267
2268 while (low <= high) {
2269 int mid = (low + high) >>> 1;
2270 T midVal = a[mid];
2271 int cmp = c.compare(midVal, key);
2272
2273 if (cmp < 0)
2274 low = mid + 1;
2275 else if (cmp > 0)
2276 high = mid - 1;
2277 else
2278 return mid; // key found
2279 }
2280 return -(low + 1); // key not found.
2281 }
2282
2283
2284 // Equality Testing
2285
2286 /**
2287 * Returns <tt>true</tt> if the two specified arrays of longs are
2288 * <i>equal</i> to one another. Two arrays are considered equal if both
2289 * arrays contain the same number of elements, and all corresponding pairs
2290 * of elements in the two arrays are equal. In other words, two arrays
2291 * are equal if they contain the same elements in the same order. Also,
2292 * two array references are considered equal if both are <tt>null</tt>.<p>
2293 *
2294 * @param a one array to be tested for equality
2295 * @param a2 the other array to be tested for equality
2296 * @return <tt>true</tt> if the two arrays are equal
2297 */
2298 public static boolean equals(long[] a, long[] a2) {
2299 if (a==a2)
2300 return true;
2301 if (a==null || a2==null)
2302 return false;
2303
2304 int length = a.length;
2305 if (a2.length != length)
2306 return false;
2307
2308 for (int i=0; i<length; i++)
2309 if (a[i] != a2[i])
2310 return false;
2311
2312 return true;
2313 }
2314
2315 /**
2316 * Returns <tt>true</tt> if the two specified arrays of ints are
2317 * <i>equal</i> to one another. Two arrays are considered equal if both
2318 * arrays contain the same number of elements, and all corresponding pairs
2319 * of elements in the two arrays are equal. In other words, two arrays
2320 * are equal if they contain the same elements in the same order. Also,
2321 * two array references are considered equal if both are <tt>null</tt>.<p>
2322 *
2323 * @param a one array to be tested for equality
2324 * @param a2 the other array to be tested for equality
2325 * @return <tt>true</tt> if the two arrays are equal
2326 */
2327 public static boolean equals(int[] a, int[] a2) {
2328 if (a==a2)
2329 return true;
2330 if (a==null || a2==null)
2331 return false;
2332
2333 int length = a.length;
2334 if (a2.length != length)
2335 return false;
2336
2337 for (int i=0; i<length; i++)
2338 if (a[i] != a2[i])
2339 return false;
2340
2341 return true;
2342 }
2343
2344 /**
2345 * Returns <tt>true</tt> if the two specified arrays of shorts are
2346 * <i>equal</i> to one another. Two arrays are considered equal if both
2347 * arrays contain the same number of elements, and all corresponding pairs
2348 * of elements in the two arrays are equal. In other words, two arrays
2349 * are equal if they contain the same elements in the same order. Also,
2350 * two array references are considered equal if both are <tt>null</tt>.<p>
2351 *
2352 * @param a one array to be tested for equality
2353 * @param a2 the other array to be tested for equality
2354 * @return <tt>true</tt> if the two arrays are equal
2355 */
2356 public static boolean equals(short[] a, short a2[]) {
2357 if (a==a2)
2358 return true;
2359 if (a==null || a2==null)
2360 return false;
2361
2362 int length = a.length;
2363 if (a2.length != length)
2364 return false;
2365
2366 for (int i=0; i<length; i++)
2367 if (a[i] != a2[i])
2368 return false;
2369
2370 return true;
2371 }
2372
2373 /**
2374 * Returns <tt>true</tt> if the two specified arrays of chars are
2375 * <i>equal</i> to one another. Two arrays are considered equal if both
2376 * arrays contain the same number of elements, and all corresponding pairs
2377 * of elements in the two arrays are equal. In other words, two arrays
2378 * are equal if they contain the same elements in the same order. Also,
2379 * two array references are considered equal if both are <tt>null</tt>.<p>
2380 *
2381 * @param a one array to be tested for equality
2382 * @param a2 the other array to be tested for equality
2383 * @return <tt>true</tt> if the two arrays are equal
2384 */
2385 public static boolean equals(char[] a, char[] a2) {
2386 if (a==a2)
2387 return true;
2388 if (a==null || a2==null)
2389 return false;
2390
2391 int length = a.length;
2392 if (a2.length != length)
2393 return false;
2394
2395 for (int i=0; i<length; i++)
2396 if (a[i] != a2[i])
2397 return false;
2398
2399 return true;
2400 }
2401
2402 /**
2403 * Returns <tt>true</tt> if the two specified arrays of bytes are
2404 * <i>equal</i> to one another. Two arrays are considered equal if both
2405 * arrays contain the same number of elements, and all corresponding pairs
2406 * of elements in the two arrays are equal. In other words, two arrays
2407 * are equal if they contain the same elements in the same order. Also,
2408 * two array references are considered equal if both are <tt>null</tt>.<p>
2409 *
2410 * @param a one array to be tested for equality
2411 * @param a2 the other array to be tested for equality
2412 * @return <tt>true</tt> if the two arrays are equal
2413 */
2414 public static boolean equals(byte[] a, byte[] a2) {
2415 if (a==a2)
2416 return true;
2417 if (a==null || a2==null)
2418 return false;
2419
2420 int length = a.length;
2421 if (a2.length != length)
2422 return false;
2423
2424 for (int i=0; i<length; i++)
2425 if (a[i] != a2[i])
2426 return false;
2427
2428 return true;
2429 }
2430
2431 /**
2432 * Returns <tt>true</tt> if the two specified arrays of booleans are
2433 * <i>equal</i> to one another. Two arrays are considered equal if both
2434 * arrays contain the same number of elements, and all corresponding pairs
2435 * of elements in the two arrays are equal. In other words, two arrays
2436 * are equal if they contain the same elements in the same order. Also,
2437 * two array references are considered equal if both are <tt>null</tt>.<p>
2438 *
2439 * @param a one array to be tested for equality
2440 * @param a2 the other array to be tested for equality
2441 * @return <tt>true</tt> if the two arrays are equal
2442 */
2443 public static boolean equals(boolean[] a, boolean[] a2) {
2444 if (a==a2)
2445 return true;
2446 if (a==null || a2==null)
2447 return false;
2448
2449 int length = a.length;
2450 if (a2.length != length)
2451 return false;
2452
2453 for (int i=0; i<length; i++)
2454 if (a[i] != a2[i])
2455 return false;
2456
2457 return true;
2458 }
2459
2460 /**
2461 * Returns <tt>true</tt> if the two specified arrays of doubles are
2462 * <i>equal</i> to one another. Two arrays are considered equal if both
2463 * arrays contain the same number of elements, and all corresponding pairs
2464 * of elements in the two arrays are equal. In other words, two arrays
2465 * are equal if they contain the same elements in the same order. Also,
2466 * two array references are considered equal if both are <tt>null</tt>.<p>
2467 *
2468 * Two doubles <tt>d1</tt> and <tt>d2</tt> are considered equal if:
2469 * <pre> <tt>new Double(d1).equals(new Double(d2))</tt></pre>
2470 * (Unlike the <tt>==</tt> operator, this method considers
2471 * <tt>NaN</tt> equals to itself, and 0.0d unequal to -0.0d.)
2472 *
2473 * @param a one array to be tested for equality
2474 * @param a2 the other array to be tested for equality
2475 * @return <tt>true</tt> if the two arrays are equal
2476 * @see Double#equals(Object)
2477 */
2478 public static boolean equals(double[] a, double[] a2) {
2479 if (a==a2)
2480 return true;
2481 if (a==null || a2==null)
2482 return false;
2483
2484 int length = a.length;
2485 if (a2.length != length)
2486 return false;
2487
2488 for (int i=0; i<length; i++)
2489 if (Double.doubleToLongBits(a[i])!=Double.doubleToLongBits(a2[i]))
2490 return false;
2491
2492 return true;
2493 }
2494
2495 /**
2496 * Returns <tt>true</tt> if the two specified arrays of floats are
2497 * <i>equal</i> to one another. Two arrays are considered equal if both
2498 * arrays contain the same number of elements, and all corresponding pairs
2499 * of elements in the two arrays are equal. In other words, two arrays
2500 * are equal if they contain the same elements in the same order. Also,
2501 * two array references are considered equal if both are <tt>null</tt>.<p>
2502 *
2503 * Two floats <tt>f1</tt> and <tt>f2</tt> are considered equal if:
2504 * <pre> <tt>new Float(f1).equals(new Float(f2))</tt></pre>
2505 * (Unlike the <tt>==</tt> operator, this method considers
2506 * <tt>NaN</tt> equals to itself, and 0.0f unequal to -0.0f.)
2507 *
2508 * @param a one array to be tested for equality
2509 * @param a2 the other array to be tested for equality
2510 * @return <tt>true</tt> if the two arrays are equal
2511 * @see Float#equals(Object)
2512 */
2513 public static boolean equals(float[] a, float[] a2) {
2514 if (a==a2)
2515 return true;
2516 if (a==null || a2==null)
2517 return false;
2518
2519 int length = a.length;
2520 if (a2.length != length)
2521 return false;
2522
2523 for (int i=0; i<length; i++)
2524 if (Float.floatToIntBits(a[i])!=Float.floatToIntBits(a2[i]))
2525 return false;
2526
2527 return true;
2528 }
2529
2530
2531 /**
2532 * Returns <tt>true</tt> if the two specified arrays of Objects are
2533 * <i>equal</i> to one another. The two arrays are considered equal if
2534 * both arrays contain the same number of elements, and all corresponding
2535 * pairs of elements in the two arrays are equal. Two objects <tt>e1</tt>
2536 * and <tt>e2</tt> are considered <i>equal</i> if <tt>(e1==null ? e2==null
2537 * : e1.equals(e2))</tt>. In other words, the two arrays are equal if
2538 * they contain the same elements in the same order. Also, two array
2539 * references are considered equal if both are <tt>null</tt>.<p>
2540 *
2541 * @param a one array to be tested for equality
2542 * @param a2 the other array to be tested for equality
2543 * @return <tt>true</tt> if the two arrays are equal
2544 */
2545 public static boolean equals(Object[] a, Object[] a2) {
2546 if (a==a2)
2547 return true;
2548 if (a==null || a2==null)
2549 return false;
2550
2551 int length = a.length;
2552 if (a2.length != length)
2553 return false;
2554
2555 for (int i=0; i<length; i++) {
2556 Object o1 = a[i];
2557 Object o2 = a2[i];
2558 if (!(o1==null ? o2==null : o1.equals(o2)))
2559 return false;
2560 }
2561
2562 return true;
2563 }
2564
2565
2566 // Filling
2567
2568 /**
2569 * Assigns the specified long value to each element of the specified array
2570 * of longs.
2571 *
2572 * @param a the array to be filled
2573 * @param val the value to be stored in all elements of the array
2574 */
2575 public static void fill(long[] a, long val) {
2576 for (int i = 0, len = a.length; i < len; i++)
2577 a[i] = val;
2578 }
2579
2580 /**
2581 * Assigns the specified long value to each element of the specified
2582 * range of the specified array of longs. The range to be filled
2583 * extends from index <tt>fromIndex</tt>, inclusive, to index
2584 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2585 * range to be filled is empty.)
2586 *
2587 * @param a the array to be filled
2588 * @param fromIndex the index of the first element (inclusive) to be
2589 * filled with the specified value
2590 * @param toIndex the index of the last element (exclusive) to be
2591 * filled with the specified value
2592 * @param val the value to be stored in all elements of the array
2593 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2594 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2595 * <tt>toIndex > a.length</tt>
2596 */
2597 public static void fill(long[] a, int fromIndex, int toIndex, long val) {
2598 rangeCheck(a.length, fromIndex, toIndex);
2599 for (int i = fromIndex; i < toIndex; i++)
2600 a[i] = val;
2601 }
2602
2603 /**
2604 * Assigns the specified int value to each element of the specified array
2605 * of ints.
2606 *
2607 * @param a the array to be filled
2608 * @param val the value to be stored in all elements of the array
2609 */
2610 public static void fill(int[] a, int val) {
2611 for (int i = 0, len = a.length; i < len; i++)
2612 a[i] = val;
2613 }
2614
2615 /**
2616 * Assigns the specified int value to each element of the specified
2617 * range of the specified array of ints. The range to be filled
2618 * extends from index <tt>fromIndex</tt>, inclusive, to index
2619 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2620 * range to be filled is empty.)
2621 *
2622 * @param a the array to be filled
2623 * @param fromIndex the index of the first element (inclusive) to be
2624 * filled with the specified value
2625 * @param toIndex the index of the last element (exclusive) to be
2626 * filled with the specified value
2627 * @param val the value to be stored in all elements of the array
2628 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2629 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2630 * <tt>toIndex > a.length</tt>
2631 */
2632 public static void fill(int[] a, int fromIndex, int toIndex, int val) {
2633 rangeCheck(a.length, fromIndex, toIndex);
2634 for (int i = fromIndex; i < toIndex; i++)
2635 a[i] = val;
2636 }
2637
2638 /**
2639 * Assigns the specified short value to each element of the specified array
2640 * of shorts.
2641 *
2642 * @param a the array to be filled
2643 * @param val the value to be stored in all elements of the array
2644 */
2645 public static void fill(short[] a, short val) {
2646 for (int i = 0, len = a.length; i < len; i++)
2647 a[i] = val;
2648 }
2649
2650 /**
2651 * Assigns the specified short value to each element of the specified
2652 * range of the specified array of shorts. The range to be filled
2653 * extends from index <tt>fromIndex</tt>, inclusive, to index
2654 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2655 * range to be filled is empty.)
2656 *
2657 * @param a the array to be filled
2658 * @param fromIndex the index of the first element (inclusive) to be
2659 * filled with the specified value
2660 * @param toIndex the index of the last element (exclusive) to be
2661 * filled with the specified value
2662 * @param val the value to be stored in all elements of the array
2663 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2664 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2665 * <tt>toIndex > a.length</tt>
2666 */
2667 public static void fill(short[] a, int fromIndex, int toIndex, short val) {
2668 rangeCheck(a.length, fromIndex, toIndex);
2669 for (int i = fromIndex; i < toIndex; i++)
2670 a[i] = val;
2671 }
2672
2673 /**
2674 * Assigns the specified char value to each element of the specified array
2675 * of chars.
2676 *
2677 * @param a the array to be filled
2678 * @param val the value to be stored in all elements of the array
2679 */
2680 public static void fill(char[] a, char val) {
2681 for (int i = 0, len = a.length; i < len; i++)
2682 a[i] = val;
2683 }
2684
2685 /**
2686 * Assigns the specified char value to each element of the specified
2687 * range of the specified array of chars. The range to be filled
2688 * extends from index <tt>fromIndex</tt>, inclusive, to index
2689 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2690 * range to be filled is empty.)
2691 *
2692 * @param a the array to be filled
2693 * @param fromIndex the index of the first element (inclusive) to be
2694 * filled with the specified value
2695 * @param toIndex the index of the last element (exclusive) to be
2696 * filled with the specified value
2697 * @param val the value to be stored in all elements of the array
2698 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2699 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2700 * <tt>toIndex > a.length</tt>
2701 */
2702 public static void fill(char[] a, int fromIndex, int toIndex, char val) {
2703 rangeCheck(a.length, fromIndex, toIndex);
2704 for (int i = fromIndex; i < toIndex; i++)
2705 a[i] = val;
2706 }
2707
2708 /**
2709 * Assigns the specified byte value to each element of the specified array
2710 * of bytes.
2711 *
2712 * @param a the array to be filled
2713 * @param val the value to be stored in all elements of the array
2714 */
2715 public static void fill(byte[] a, byte val) {
2716 for (int i = 0, len = a.length; i < len; i++)
2717 a[i] = val;
2718 }
2719
2720 /**
2721 * Assigns the specified byte value to each element of the specified
2722 * range of the specified array of bytes. The range to be filled
2723 * extends from index <tt>fromIndex</tt>, inclusive, to index
2724 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2725 * range to be filled is empty.)
2726 *
2727 * @param a the array to be filled
2728 * @param fromIndex the index of the first element (inclusive) to be
2729 * filled with the specified value
2730 * @param toIndex the index of the last element (exclusive) to be
2731 * filled with the specified value
2732 * @param val the value to be stored in all elements of the array
2733 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2734 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2735 * <tt>toIndex > a.length</tt>
2736 */
2737 public static void fill(byte[] a, int fromIndex, int toIndex, byte val) {
2738 rangeCheck(a.length, fromIndex, toIndex);
2739 for (int i = fromIndex; i < toIndex; i++)
2740 a[i] = val;
2741 }
2742
2743 /**
2744 * Assigns the specified boolean value to each element of the specified
2745 * array of booleans.
2746 *
2747 * @param a the array to be filled
2748 * @param val the value to be stored in all elements of the array
2749 */
2750 public static void fill(boolean[] a, boolean val) {
2751 for (int i = 0, len = a.length; i < len; i++)
2752 a[i] = val;
2753 }
2754
2755 /**
2756 * Assigns the specified boolean value to each element of the specified
2757 * range of the specified array of booleans. The range to be filled
2758 * extends from index <tt>fromIndex</tt>, inclusive, to index
2759 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2760 * range to be filled is empty.)
2761 *
2762 * @param a the array to be filled
2763 * @param fromIndex the index of the first element (inclusive) to be
2764 * filled with the specified value
2765 * @param toIndex the index of the last element (exclusive) to be
2766 * filled with the specified value
2767 * @param val the value to be stored in all elements of the array
2768 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2769 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2770 * <tt>toIndex > a.length</tt>
2771 */
2772 public static void fill(boolean[] a, int fromIndex, int toIndex,
2773 boolean val) {
2774 rangeCheck(a.length, fromIndex, toIndex);
2775 for (int i = fromIndex; i < toIndex; i++)
2776 a[i] = val;
2777 }
2778
2779 /**
2780 * Assigns the specified double value to each element of the specified
2781 * array of doubles.
2782 *
2783 * @param a the array to be filled
2784 * @param val the value to be stored in all elements of the array
2785 */
2786 public static void fill(double[] a, double val) {
2787 for (int i = 0, len = a.length; i < len; i++)
2788 a[i] = val;
2789 }
2790
2791 /**
2792 * Assigns the specified double value to each element of the specified
2793 * range of the specified array of doubles. The range to be filled
2794 * extends from index <tt>fromIndex</tt>, inclusive, to index
2795 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2796 * range to be filled is empty.)
2797 *
2798 * @param a the array to be filled
2799 * @param fromIndex the index of the first element (inclusive) to be
2800 * filled with the specified value
2801 * @param toIndex the index of the last element (exclusive) to be
2802 * filled with the specified value
2803 * @param val the value to be stored in all elements of the array
2804 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2805 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2806 * <tt>toIndex > a.length</tt>
2807 */
2808 public static void fill(double[] a, int fromIndex, int toIndex,double val){
2809 rangeCheck(a.length, fromIndex, toIndex);
2810 for (int i = fromIndex; i < toIndex; i++)
2811 a[i] = val;
2812 }
2813
2814 /**
2815 * Assigns the specified float value to each element of the specified array
2816 * of floats.
2817 *
2818 * @param a the array to be filled
2819 * @param val the value to be stored in all elements of the array
2820 */
2821 public static void fill(float[] a, float val) {
2822 for (int i = 0, len = a.length; i < len; i++)
2823 a[i] = val;
2824 }
2825
2826 /**
2827 * Assigns the specified float value to each element of the specified
2828 * range of the specified array of floats. The range to be filled
2829 * extends from index <tt>fromIndex</tt>, inclusive, to index
2830 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2831 * range to be filled is empty.)
2832 *
2833 * @param a the array to be filled
2834 * @param fromIndex the index of the first element (inclusive) to be
2835 * filled with the specified value
2836 * @param toIndex the index of the last element (exclusive) to be
2837 * filled with the specified value
2838 * @param val the value to be stored in all elements of the array
2839 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2840 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2841 * <tt>toIndex > a.length</tt>
2842 */
2843 public static void fill(float[] a, int fromIndex, int toIndex, float val) {
2844 rangeCheck(a.length, fromIndex, toIndex);
2845 for (int i = fromIndex; i < toIndex; i++)
2846 a[i] = val;
2847 }
2848
2849 /**
2850 * Assigns the specified Object reference to each element of the specified
2851 * array of Objects.
2852 *
2853 * @param a the array to be filled
2854 * @param val the value to be stored in all elements of the array
2855 * @throws ArrayStoreException if the specified value is not of a
2856 * runtime type that can be stored in the specified array
2857 */
2858 public static void fill(Object[] a, Object val) {
2859 for (int i = 0, len = a.length; i < len; i++)
2860 a[i] = val;
2861 }
2862
2863 /**
2864 * Assigns the specified Object reference to each element of the specified
2865 * range of the specified array of Objects. The range to be filled
2866 * extends from index <tt>fromIndex</tt>, inclusive, to index
2867 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2868 * range to be filled is empty.)
2869 *
2870 * @param a the array to be filled
2871 * @param fromIndex the index of the first element (inclusive) to be
2872 * filled with the specified value
2873 * @param toIndex the index of the last element (exclusive) to be
2874 * filled with the specified value
2875 * @param val the value to be stored in all elements of the array
2876 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2877 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2878 * <tt>toIndex > a.length</tt>
2879 * @throws ArrayStoreException if the specified value is not of a
2880 * runtime type that can be stored in the specified array
2881 */
2882 public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
2883 rangeCheck(a.length, fromIndex, toIndex);
2884 for (int i = fromIndex; i < toIndex; i++)
2885 a[i] = val;
2886 }
2887
2888
2889 // Cloning
2890 /**
2891 * Copies the specified array, truncating or padding with nulls (if necessary)
2892 * so the copy has the specified length. For all indices that are
2893 * valid in both the original array and the copy, the two arrays will
2894 * contain identical values. For any indices that are valid in the
2895 * copy but not the original, the copy will contain <tt>null</tt>.
2896 * Such indices will exist if and only if the specified length
2897 * is greater than that of the original array.
2898 * The resulting array is of exactly the same class as the original array.
2899 *
2900 * @param original the array to be copied
2901 * @param newLength the length of the copy to be returned
2902 * @return a copy of the original array, truncated or padded with nulls
2903 * to obtain the specified length
2904 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2905 * @throws NullPointerException if <tt>original</tt> is null
2906 * @since 1.6
2907 */
2908 public static <T> T[] copyOf(T[] original, int newLength) {
2909 return (T[]) copyOf(original, newLength, original.getClass());
2910 }
2911
2912 /**
2913 * Copies the specified array, truncating or padding with nulls (if necessary)
2914 * so the copy has the specified length. For all indices that are
2915 * valid in both the original array and the copy, the two arrays will
2916 * contain identical values. For any indices that are valid in the
2917 * copy but not the original, the copy will contain <tt>null</tt>.
2918 * Such indices will exist if and only if the specified length
2919 * is greater than that of the original array.
2920 * The resulting array is of the class <tt>newType</tt>.
2921 *
2922 * @param original the array to be copied
2923 * @param newLength the length of the copy to be returned
2924 * @param newType the class of the copy to be returned
2925 * @return a copy of the original array, truncated or padded with nulls
2926 * to obtain the specified length
2927 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2928 * @throws NullPointerException if <tt>original</tt> is null
2929 * @throws ArrayStoreException if an element copied from
2930 * <tt>original</tt> is not of a runtime type that can be stored in
2931 * an array of class <tt>newType</tt>
2932 * @since 1.6
2933 */
2934 public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
2935 T[] copy = ((Object)newType == (Object)Object[].class)
2936 ? (T[]) new Object[newLength]
2937 : (T[]) Array.newInstance(newType.getComponentType(), newLength);
2938 System.arraycopy(original, 0, copy, 0,
2939 Math.min(original.length, newLength));
2940 return copy;
2941 }
2942
2943 /**
2944 * Copies the specified array, truncating or padding with zeros (if necessary)
2945 * so the copy has the specified length. For all indices that are
2946 * valid in both the original array and the copy, the two arrays will
2947 * contain identical values. For any indices that are valid in the
2948 * copy but not the original, the copy will contain <tt>(byte)0</tt>.
2949 * Such indices will exist if and only if the specified length
2950 * is greater than that of the original array.
2951 *
2952 * @param original the array to be copied
2953 * @param newLength the length of the copy to be returned
2954 * @return a copy of the original array, truncated or padded with zeros
2955 * to obtain the specified length
2956 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2957 * @throws NullPointerException if <tt>original</tt> is null
2958 * @since 1.6
2959 */
2960 public static byte[] copyOf(byte[] original, int newLength) {
2961 byte[] copy = new byte[newLength];
2962 System.arraycopy(original, 0, copy, 0,
2963 Math.min(original.length, newLength));
2964 return copy;
2965 }
2966
2967 /**
2968 * Copies the specified array, truncating or padding with zeros (if necessary)
2969 * so the copy has the specified length. For all indices that are
2970 * valid in both the original array and the copy, the two arrays will
2971 * contain identical values. For any indices that are valid in the
2972 * copy but not the original, the copy will contain <tt>(short)0</tt>.
2973 * Such indices will exist if and only if the specified length
2974 * is greater than that of the original array.
2975 *
2976 * @param original the array to be copied
2977 * @param newLength the length of the copy to be returned
2978 * @return a copy of the original array, truncated or padded with zeros
2979 * to obtain the specified length
2980 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2981 * @throws NullPointerException if <tt>original</tt> is null
2982 * @since 1.6
2983 */
2984 public static short[] copyOf(short[] original, int newLength) {
2985 short[] copy = new short[newLength];
2986 System.arraycopy(original, 0, copy, 0,
2987 Math.min(original.length, newLength));
2988 return copy;
2989 }
2990
2991 /**
2992 * Copies the specified array, truncating or padding with zeros (if necessary)
2993 * so the copy has the specified length. For all indices that are
2994 * valid in both the original array and the copy, the two arrays will
2995 * contain identical values. For any indices that are valid in the
2996 * copy but not the original, the copy will contain <tt>0</tt>.
2997 * Such indices will exist if and only if the specified length
2998 * is greater than that of the original array.
2999 *
3000 * @param original the array to be copied
3001 * @param newLength the length of the copy to be returned
3002 * @return a copy of the original array, truncated or padded with zeros
3003 * to obtain the specified length
3004 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
3005 * @throws NullPointerException if <tt>original</tt> is null
3006 * @since 1.6
3007 */
3008 public static int[] copyOf(int[] original, int newLength) {
3009 int[] copy = new int[newLength];
3010 System.arraycopy(original, 0, copy, 0,
3011 Math.min(original.length, newLength));
3012 return copy;
3013 }
3014
3015 /**
3016 * Copies the specified array, truncating or padding with zeros (if necessary)
3017 * so the copy has the specified length. For all indices that are
3018 * valid in both the original array and the copy, the two arrays will
3019 * contain identical values. For any indices that are valid in the
3020 * copy but not the original, the copy will contain <tt>0L</tt>.
3021 * Such indices will exist if and only if the specified length
3022 * is greater than that of the original array.
3023 *
3024 * @param original the array to be copied
3025 * @param newLength the length of the copy to be returned
3026 * @return a copy of the original array, truncated or padded with zeros
3027 * to obtain the specified length
3028 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
3029 * @throws NullPointerException if <tt>original</tt> is null
3030 * @since 1.6
3031 */
3032 public static long[] copyOf(long[] original, int newLength) {
3033 long[] copy = new long[newLength];
3034 System.arraycopy(original, 0, copy, 0,
3035 Math.min(original.length, newLength));
3036 return copy;
3037 }
3038
3039 /**
3040 * Copies the specified array, truncating or padding with null characters (if necessary)
3041 * so the copy has the specified length. For all indices that are valid
3042 * in both the original array and the copy, the two arrays will contain
3043 * identical values. For any indices that are valid in the copy but not
3044 * the original, the copy will contain <tt>'\\u000'</tt>. Such indices
3045 * will exist if and only if the specified length is greater than that of
3046 * the original array.
3047 *
3048 * @param original the array to be copied
3049 * @param newLength the length of the copy to be returned
3050 * @return a copy of the original array, truncated or padded with null characters
3051 * to obtain the specified length
3052 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
3053 * @throws NullPointerException if <tt>original</tt> is null
3054 * @since 1.6
3055 */
3056 public static char[] copyOf(char[] original, int newLength) {
3057 char[] copy = new char[newLength];
3058 System.arraycopy(original, 0, copy, 0,
3059 Math.min(original.length, newLength));
3060 return copy;
3061 }
3062
3063 /**
3064 * Copies the specified array, truncating or padding with zeros (if necessary)
3065 * so the copy has the specified length. For all indices that are
3066 * valid in both the original array and the copy, the two arrays will
3067 * contain identical values. For any indices that are valid in the
3068 * copy but not the original, the copy will contain <tt>0f</tt>.
3069 * Such indices will exist if and only if the specified length
3070 * is greater than that of the original array.
3071 *
3072 * @param original the array to be copied
3073 * @param newLength the length of the copy to be returned
3074 * @return a copy of the original array, truncated or padded with zeros
3075 * to obtain the specified length
3076 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
3077 * @throws NullPointerException if <tt>original</tt> is null
3078 * @since 1.6
3079 */
3080 public static float[] copyOf(float[] original, int newLength) {
3081 float[] copy = new float[newLength];
3082 System.arraycopy(original, 0, copy, 0,
3083 Math.min(original.length, newLength));
3084 return copy;
3085 }
3086
3087 /**
3088 * Copies the specified array, truncating or padding with zeros (if necessary)
3089 * so the copy has the specified length. For all indices that are
3090 * valid in both the original array and the copy, the two arrays will
3091 * contain identical values. For any indices that are valid in the
3092 * copy but not the original, the copy will contain <tt>0d</tt>.
3093 * Such indices will exist if and only if the specified length
3094 * is greater than that of the original array.
3095 *
3096 * @param original the array to be copied
3097 * @param newLength the length of the copy to be returned
3098 * @return a copy of the original array, truncated or padded with zeros
3099 * to obtain the specified length
3100 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
3101 * @throws NullPointerException if <tt>original</tt> is null
3102 * @since 1.6
3103 */
3104 public static double[] copyOf(double[] original, int newLength) {
3105 double[] copy = new double[newLength];
3106 System.arraycopy(original, 0, copy, 0,
3107 Math.min(original.length, newLength));
3108 return copy;
3109 }
3110
3111 /**
3112 * Copies the specified array, truncating or padding with <tt>false</tt> (if necessary)
3113 * so the copy has the specified length. For all indices that are
3114 * valid in both the original array and the copy, the two arrays will
3115 * contain identical values. For any indices that are valid in the
3116 * copy but not the original, the copy will contain <tt>false</tt>.
3117 * Such indices will exist if and only if the specified length
3118 * is greater than that of the original array.
3119 *
3120 * @param original the array to be copied
3121 * @param newLength the length of the copy to be returned
3122 * @return a copy of the original array, truncated or padded with false elements
3123 * to obtain the specified length
3124 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
3125 * @throws NullPointerException if <tt>original</tt> is null
3126 * @since 1.6
3127 */
3128 public static boolean[] copyOf(boolean[] original, int newLength) {
3129 boolean[] copy = new boolean[newLength];
3130 System.arraycopy(original, 0, copy, 0,
3131 Math.min(original.length, newLength));
3132 return copy;
3133 }
3134
3135 /**
3136 * Copies the specified range of the specified array into a new array.
3137 * The initial index of the range (<tt>from</tt>) must lie between zero
3138 * and <tt>original.length</tt>, inclusive. The value at
3139 * <tt>original[from]</tt> is placed into the initial element of the copy
3140 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3141 * Values from subsequent elements in the original array are placed into
3142 * subsequent elements in the copy. The final index of the range
3143 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3144 * may be greater than <tt>original.length</tt>, in which case
3145 * <tt>null</tt> is placed in all elements of the copy whose index is
3146 * greater than or equal to <tt>original.length - from</tt>. The length
3147 * of the returned array will be <tt>to - from</tt>.
3148 * <p>
3149 * The resulting array is of exactly the same class as the original array.
3150 *
3151 * @param original the array from which a range is to be copied
3152 * @param from the initial index of the range to be copied, inclusive
3153 * @param to the final index of the range to be copied, exclusive.
3154 * (This index may lie outside the array.)
3155 * @return a new array containing the specified range from the original array,
3156 * truncated or padded with nulls to obtain the required length
3157 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3158 * or {@code from > original.length}
3159 * @throws IllegalArgumentException if <tt>from > to</tt>
3160 * @throws NullPointerException if <tt>original</tt> is null
3161 * @since 1.6
3162 */
3163 public static <T> T[] copyOfRange(T[] original, int from, int to) {
3164 return copyOfRange(original, from, to, (Class<T[]>) original.getClass());
3165 }
3166
3167 /**
3168 * Copies the specified range of the specified array into a new array.
3169 * The initial index of the range (<tt>from</tt>) must lie between zero
3170 * and <tt>original.length</tt>, inclusive. The value at
3171 * <tt>original[from]</tt> is placed into the initial element of the copy
3172 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3173 * Values from subsequent elements in the original array are placed into
3174 * subsequent elements in the copy. The final index of the range
3175 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3176 * may be greater than <tt>original.length</tt>, in which case
3177 * <tt>null</tt> is placed in all elements of the copy whose index is
3178 * greater than or equal to <tt>original.length - from</tt>. The length
3179 * of the returned array will be <tt>to - from</tt>.
3180 * The resulting array is of the class <tt>newType</tt>.
3181 *
3182 * @param original the array from which a range is to be copied
3183 * @param from the initial index of the range to be copied, inclusive
3184 * @param to the final index of the range to be copied, exclusive.
3185 * (This index may lie outside the array.)
3186 * @param newType the class of the copy to be returned
3187 * @return a new array containing the specified range from the original array,
3188 * truncated or padded with nulls to obtain the required length
3189 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3190 * or {@code from > original.length}
3191 * @throws IllegalArgumentException if <tt>from > to</tt>
3192 * @throws NullPointerException if <tt>original</tt> is null
3193 * @throws ArrayStoreException if an element copied from
3194 * <tt>original</tt> is not of a runtime type that can be stored in
3195 * an array of class <tt>newType</tt>.
3196 * @since 1.6
3197 */
3198 public static <T,U> T[] copyOfRange(U[] original, int from, int to, Class<? extends T[]> newType) {
3199 int newLength = to - from;
3200 if (newLength < 0)
3201 throw new IllegalArgumentException(from + " > " + to);
3202 T[] copy = ((Object)newType == (Object)Object[].class)
3203 ? (T[]) new Object[newLength]
3204 : (T[]) Array.newInstance(newType.getComponentType(), newLength);
3205 System.arraycopy(original, from, copy, 0,
3206 Math.min(original.length - from, newLength));
3207 return copy;
3208 }
3209
3210 /**
3211 * Copies the specified range of the specified array into a new array.
3212 * The initial index of the range (<tt>from</tt>) must lie between zero
3213 * and <tt>original.length</tt>, inclusive. The value at
3214 * <tt>original[from]</tt> is placed into the initial element of the copy
3215 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3216 * Values from subsequent elements in the original array are placed into
3217 * subsequent elements in the copy. The final index of the range
3218 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3219 * may be greater than <tt>original.length</tt>, in which case
3220 * <tt>(byte)0</tt> is placed in all elements of the copy whose index is
3221 * greater than or equal to <tt>original.length - from</tt>. The length
3222 * of the returned array will be <tt>to - from</tt>.
3223 *
3224 * @param original the array from which a range is to be copied
3225 * @param from the initial index of the range to be copied, inclusive
3226 * @param to the final index of the range to be copied, exclusive.
3227 * (This index may lie outside the array.)
3228 * @return a new array containing the specified range from the original array,
3229 * truncated or padded with zeros to obtain the required length
3230 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3231 * or {@code from > original.length}
3232 * @throws IllegalArgumentException if <tt>from > to</tt>
3233 * @throws NullPointerException if <tt>original</tt> is null
3234 * @since 1.6
3235 */
3236 public static byte[] copyOfRange(byte[] original, int from, int to) {
3237 int newLength = to - from;
3238 if (newLength < 0)
3239 throw new IllegalArgumentException(from + " > " + to);
3240 byte[] copy = new byte[newLength];
3241 System.arraycopy(original, from, copy, 0,
3242 Math.min(original.length - from, newLength));
3243 return copy;
3244 }
3245
3246 /**
3247 * Copies the specified range of the specified array into a new array.
3248 * The initial index of the range (<tt>from</tt>) must lie between zero
3249 * and <tt>original.length</tt>, inclusive. The value at
3250 * <tt>original[from]</tt> is placed into the initial element of the copy
3251 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3252 * Values from subsequent elements in the original array are placed into
3253 * subsequent elements in the copy. The final index of the range
3254 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3255 * may be greater than <tt>original.length</tt>, in which case
3256 * <tt>(short)0</tt> is placed in all elements of the copy whose index is
3257 * greater than or equal to <tt>original.length - from</tt>. The length
3258 * of the returned array will be <tt>to - from</tt>.
3259 *
3260 * @param original the array from which a range is to be copied
3261 * @param from the initial index of the range to be copied, inclusive
3262 * @param to the final index of the range to be copied, exclusive.
3263 * (This index may lie outside the array.)
3264 * @return a new array containing the specified range from the original array,
3265 * truncated or padded with zeros to obtain the required length
3266 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3267 * or {@code from > original.length}
3268 * @throws IllegalArgumentException if <tt>from > to</tt>
3269 * @throws NullPointerException if <tt>original</tt> is null
3270 * @since 1.6
3271 */
3272 public static short[] copyOfRange(short[] original, int from, int to) {
3273 int newLength = to - from;
3274 if (newLength < 0)
3275 throw new IllegalArgumentException(from + " > " + to);
3276 short[] copy = new short[newLength];
3277 System.arraycopy(original, from, copy, 0,
3278 Math.min(original.length - from, newLength));
3279 return copy;
3280 }
3281
3282 /**
3283 * Copies the specified range of the specified array into a new array.
3284 * The initial index of the range (<tt>from</tt>) must lie between zero
3285 * and <tt>original.length</tt>, inclusive. The value at
3286 * <tt>original[from]</tt> is placed into the initial element of the copy
3287 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3288 * Values from subsequent elements in the original array are placed into
3289 * subsequent elements in the copy. The final index of the range
3290 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3291 * may be greater than <tt>original.length</tt>, in which case
3292 * <tt>0</tt> is placed in all elements of the copy whose index is
3293 * greater than or equal to <tt>original.length - from</tt>. The length
3294 * of the returned array will be <tt>to - from</tt>.
3295 *
3296 * @param original the array from which a range is to be copied
3297 * @param from the initial index of the range to be copied, inclusive
3298 * @param to the final index of the range to be copied, exclusive.
3299 * (This index may lie outside the array.)
3300 * @return a new array containing the specified range from the original array,
3301 * truncated or padded with zeros to obtain the required length
3302 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3303 * or {@code from > original.length}
3304 * @throws IllegalArgumentException if <tt>from > to</tt>
3305 * @throws NullPointerException if <tt>original</tt> is null
3306 * @since 1.6
3307 */
3308 public static int[] copyOfRange(int[] original, int from, int to) {
3309 int newLength = to - from;
3310 if (newLength < 0)
3311 throw new IllegalArgumentException(from + " > " + to);
3312 int[] copy = new int[newLength];
3313 System.arraycopy(original, from, copy, 0,
3314 Math.min(original.length - from, newLength));
3315 return copy;
3316 }
3317
3318 /**
3319 * Copies the specified range of the specified array into a new array.
3320 * The initial index of the range (<tt>from</tt>) must lie between zero
3321 * and <tt>original.length</tt>, inclusive. The value at
3322 * <tt>original[from]</tt> is placed into the initial element of the copy
3323 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3324 * Values from subsequent elements in the original array are placed into
3325 * subsequent elements in the copy. The final index of the range
3326 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3327 * may be greater than <tt>original.length</tt>, in which case
3328 * <tt>0L</tt> is placed in all elements of the copy whose index is
3329 * greater than or equal to <tt>original.length - from</tt>. The length
3330 * of the returned array will be <tt>to - from</tt>.
3331 *
3332 * @param original the array from which a range is to be copied
3333 * @param from the initial index of the range to be copied, inclusive
3334 * @param to the final index of the range to be copied, exclusive.
3335 * (This index may lie outside the array.)
3336 * @return a new array containing the specified range from the original array,
3337 * truncated or padded with zeros to obtain the required length
3338 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3339 * or {@code from > original.length}
3340 * @throws IllegalArgumentException if <tt>from > to</tt>
3341 * @throws NullPointerException if <tt>original</tt> is null
3342 * @since 1.6
3343 */
3344 public static long[] copyOfRange(long[] original, int from, int to) {
3345 int newLength = to - from;
3346 if (newLength < 0)
3347 throw new IllegalArgumentException(from + " > " + to);
3348 long[] copy = new long[newLength];
3349 System.arraycopy(original, from, copy, 0,
3350 Math.min(original.length - from, newLength));
3351 return copy;
3352 }
3353
3354 /**
3355 * Copies the specified range of the specified array into a new array.
3356 * The initial index of the range (<tt>from</tt>) must lie between zero
3357 * and <tt>original.length</tt>, inclusive. The value at
3358 * <tt>original[from]</tt> is placed into the initial element of the copy
3359 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3360 * Values from subsequent elements in the original array are placed into
3361 * subsequent elements in the copy. The final index of the range
3362 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3363 * may be greater than <tt>original.length</tt>, in which case
3364 * <tt>'\\u000'</tt> is placed in all elements of the copy whose index is
3365 * greater than or equal to <tt>original.length - from</tt>. The length
3366 * of the returned array will be <tt>to - from</tt>.
3367 *
3368 * @param original the array from which a range is to be copied
3369 * @param from the initial index of the range to be copied, inclusive
3370 * @param to the final index of the range to be copied, exclusive.
3371 * (This index may lie outside the array.)
3372 * @return a new array containing the specified range from the original array,
3373 * truncated or padded with null characters to obtain the required length
3374 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3375 * or {@code from > original.length}
3376 * @throws IllegalArgumentException if <tt>from > to</tt>
3377 * @throws NullPointerException if <tt>original</tt> is null
3378 * @since 1.6
3379 */
3380 public static char[] copyOfRange(char[] original, int from, int to) {
3381 int newLength = to - from;
3382 if (newLength < 0)
3383 throw new IllegalArgumentException(from + " > " + to);
3384 char[] copy = new char[newLength];
3385 System.arraycopy(original, from, copy, 0,
3386 Math.min(original.length - from, newLength));
3387 return copy;
3388 }
3389
3390 /**
3391 * Copies the specified range of the specified array into a new array.
3392 * The initial index of the range (<tt>from</tt>) must lie between zero
3393 * and <tt>original.length</tt>, inclusive. The value at
3394 * <tt>original[from]</tt> is placed into the initial element of the copy
3395 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3396 * Values from subsequent elements in the original array are placed into
3397 * subsequent elements in the copy. The final index of the range
3398 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3399 * may be greater than <tt>original.length</tt>, in which case
3400 * <tt>0f</tt> is placed in all elements of the copy whose index is
3401 * greater than or equal to <tt>original.length - from</tt>. The length
3402 * of the returned array will be <tt>to - from</tt>.
3403 *
3404 * @param original the array from which a range is to be copied
3405 * @param from the initial index of the range to be copied, inclusive
3406 * @param to the final index of the range to be copied, exclusive.
3407 * (This index may lie outside the array.)
3408 * @return a new array containing the specified range from the original array,
3409 * truncated or padded with zeros to obtain the required length
3410 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3411 * or {@code from > original.length}
3412 * @throws IllegalArgumentException if <tt>from > to</tt>
3413 * @throws NullPointerException if <tt>original</tt> is null
3414 * @since 1.6
3415 */
3416 public static float[] copyOfRange(float[] original, int from, int to) {
3417 int newLength = to - from;
3418 if (newLength < 0)
3419 throw new IllegalArgumentException(from + " > " + to);
3420 float[] copy = new float[newLength];
3421 System.arraycopy(original, from, copy, 0,
3422 Math.min(original.length - from, newLength));
3423 return copy;
3424 }
3425
3426 /**
3427 * Copies the specified range of the specified array into a new array.
3428 * The initial index of the range (<tt>from</tt>) must lie between zero
3429 * and <tt>original.length</tt>, inclusive. The value at
3430 * <tt>original[from]</tt> is placed into the initial element of the copy
3431 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3432 * Values from subsequent elements in the original array are placed into
3433 * subsequent elements in the copy. The final index of the range
3434 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3435 * may be greater than <tt>original.length</tt>, in which case
3436 * <tt>0d</tt> is placed in all elements of the copy whose index is
3437 * greater than or equal to <tt>original.length - from</tt>. The length
3438 * of the returned array will be <tt>to - from</tt>.
3439 *
3440 * @param original the array from which a range is to be copied
3441 * @param from the initial index of the range to be copied, inclusive
3442 * @param to the final index of the range to be copied, exclusive.
3443 * (This index may lie outside the array.)
3444 * @return a new array containing the specified range from the original array,
3445 * truncated or padded with zeros to obtain the required length
3446 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3447 * or {@code from > original.length}
3448 * @throws IllegalArgumentException if <tt>from > to</tt>
3449 * @throws NullPointerException if <tt>original</tt> is null
3450 * @since 1.6
3451 */
3452 public static double[] copyOfRange(double[] original, int from, int to) {
3453 int newLength = to - from;
3454 if (newLength < 0)
3455 throw new IllegalArgumentException(from + " > " + to);
3456 double[] copy = new double[newLength];
3457 System.arraycopy(original, from, copy, 0,
3458 Math.min(original.length - from, newLength));
3459 return copy;
3460 }
3461
3462 /**
3463 * Copies the specified range of the specified array into a new array.
3464 * The initial index of the range (<tt>from</tt>) must lie between zero
3465 * and <tt>original.length</tt>, inclusive. The value at
3466 * <tt>original[from]</tt> is placed into the initial element of the copy
3467 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3468 * Values from subsequent elements in the original array are placed into
3469 * subsequent elements in the copy. The final index of the range
3470 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3471 * may be greater than <tt>original.length</tt>, in which case
3472 * <tt>false</tt> is placed in all elements of the copy whose index is
3473 * greater than or equal to <tt>original.length - from</tt>. The length
3474 * of the returned array will be <tt>to - from</tt>.
3475 *
3476 * @param original the array from which a range is to be copied
3477 * @param from the initial index of the range to be copied, inclusive
3478 * @param to the final index of the range to be copied, exclusive.
3479 * (This index may lie outside the array.)
3480 * @return a new array containing the specified range from the original array,
3481 * truncated or padded with false elements to obtain the required length
3482 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3483 * or {@code from > original.length}
3484 * @throws IllegalArgumentException if <tt>from > to</tt>
3485 * @throws NullPointerException if <tt>original</tt> is null
3486 * @since 1.6
3487 */
3488 public static boolean[] copyOfRange(boolean[] original, int from, int to) {
3489 int newLength = to - from;
3490 if (newLength < 0)
3491 throw new IllegalArgumentException(from + " > " + to);
3492 boolean[] copy = new boolean[newLength];
3493 System.arraycopy(original, from, copy, 0,
3494 Math.min(original.length - from, newLength));
3495 return copy;
3496 }
3497
3498
3499 // Misc
3500
3501 /**
3502 * Returns a fixed-size list backed by the specified array. (Changes to
3503 * the returned list "write through" to the array.) This method acts
3504 * as bridge between array-based and collection-based APIs, in
3505 * combination with {@link Collection#toArray}. The returned list is
3506 * serializable and implements {@link RandomAccess}.
3507 *
3508 * <p>This method also provides a convenient way to create a fixed-size
3509 * list initialized to contain several elements:
3510 * <pre>
3511 * List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
3512 * </pre>
3513 *
3514 * @param a the array by which the list will be backed
3515 * @return a list view of the specified array
3516 */
3517 public static <T> List<T> asList(T... a) {
3518 return new ArrayList<T>(a);
3519 }
3520
3521 /**
3522 * @serial include
3523 */
3524 private static class ArrayList<E> extends AbstractList<E>
3525 implements RandomAccess, java.io.Serializable
3526 {
3527 private static final long serialVersionUID = -2764017481108945198L;
3528 private final E[] a;
3529
3530 ArrayList(E[] array) {
3531 if (array==null)
3532 throw new NullPointerException();
3533 a = array;
3534 }
3535
3536 public int size() {
3537 return a.length;
3538 }
3539
3540 public Object[] toArray() {
3541 return a.clone();
3542 }
3543
3544 public <T> T[] toArray(T[] a) {
3545 int size = size();
3546 if (a.length < size)
3547 return Arrays.copyOf(this.a, size,
3548 (Class<? extends T[]>) a.getClass());
3549 System.arraycopy(this.a, 0, a, 0, size);
3550 if (a.length > size)
3551 a[size] = null;
3552 return a;
3553 }
3554
3555 public E get(int index) {
3556 return a[index];
3557 }
3558
3559 public E set(int index, E element) {
3560 E oldValue = a[index];
3561 a[index] = element;
3562 return oldValue;
3563 }
3564
3565 public int indexOf(Object o) {
3566 if (o==null) {
3567 for (int i=0; i<a.length; i++)
3568 if (a[i]==null)
3569 return i;
3570 } else {
3571 for (int i=0; i<a.length; i++)
3572 if (o.equals(a[i]))
3573 return i;
3574 }
3575 return -1;
3576 }
3577
3578 public boolean contains(Object o) {
3579 return indexOf(o) != -1;
3580 }
3581 }
3582
3583 /**
3584 * Returns a hash code based on the contents of the specified array.
3585 * For any two <tt>long</tt> arrays <tt>a</tt> and <tt>b</tt>
3586 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3587 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3588 *
3589 * <p>The value returned by this method is the same value that would be
3590 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3591 * method on a {@link List} containing a sequence of {@link Long}
3592 * instances representing the elements of <tt>a</tt> in the same order.
3593 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3594 *
3595 * @param a the array whose hash value to compute
3596 * @return a content-based hash code for <tt>a</tt>
3597 * @since 1.5
3598 */
3599 public static int hashCode(long a[]) {
3600 if (a == null)
3601 return 0;
3602
3603 int result = 1;
3604 for (long element : a) {
3605 int elementHash = (int)(element ^ (element >>> 32));
3606 result = 31 * result + elementHash;
3607 }
3608
3609 return result;
3610 }
3611
3612 /**
3613 * Returns a hash code based on the contents of the specified array.
3614 * For any two non-null <tt>int</tt> arrays <tt>a</tt> and <tt>b</tt>
3615 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3616 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3617 *
3618 * <p>The value returned by this method is the same value that would be
3619 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3620 * method on a {@link List} containing a sequence of {@link Integer}
3621 * instances representing the elements of <tt>a</tt> in the same order.
3622 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3623 *
3624 * @param a the array whose hash value to compute
3625 * @return a content-based hash code for <tt>a</tt>
3626 * @since 1.5
3627 */
3628 public static int hashCode(int a[]) {
3629 if (a == null)
3630 return 0;
3631
3632 int result = 1;
3633 for (int element : a)
3634 result = 31 * result + element;
3635
3636 return result;
3637 }
3638
3639 /**
3640 * Returns a hash code based on the contents of the specified array.
3641 * For any two <tt>short</tt> arrays <tt>a</tt> and <tt>b</tt>
3642 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3643 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3644 *
3645 * <p>The value returned by this method is the same value that would be
3646 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3647 * method on a {@link List} containing a sequence of {@link Short}
3648 * instances representing the elements of <tt>a</tt> in the same order.
3649 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3650 *
3651 * @param a the array whose hash value to compute
3652 * @return a content-based hash code for <tt>a</tt>
3653 * @since 1.5
3654 */
3655 public static int hashCode(short a[]) {
3656 if (a == null)
3657 return 0;
3658
3659 int result = 1;
3660 for (short element : a)
3661 result = 31 * result + element;
3662
3663 return result;
3664 }
3665
3666 /**
3667 * Returns a hash code based on the contents of the specified array.
3668 * For any two <tt>char</tt> arrays <tt>a</tt> and <tt>b</tt>
3669 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3670 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3671 *
3672 * <p>The value returned by this method is the same value that would be
3673 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3674 * method on a {@link List} containing a sequence of {@link Character}
3675 * instances representing the elements of <tt>a</tt> in the same order.
3676 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3677 *
3678 * @param a the array whose hash value to compute
3679 * @return a content-based hash code for <tt>a</tt>
3680 * @since 1.5
3681 */
3682 public static int hashCode(char a[]) {
3683 if (a == null)
3684 return 0;
3685
3686 int result = 1;
3687 for (char element : a)
3688 result = 31 * result + element;
3689
3690 return result;
3691 }
3692
3693 /**
3694 * Returns a hash code based on the contents of the specified array.
3695 * For any two <tt>byte</tt> arrays <tt>a</tt> and <tt>b</tt>
3696 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3697 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3698 *
3699 * <p>The value returned by this method is the same value that would be
3700 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3701 * method on a {@link List} containing a sequence of {@link Byte}
3702 * instances representing the elements of <tt>a</tt> in the same order.
3703 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3704 *
3705 * @param a the array whose hash value to compute
3706 * @return a content-based hash code for <tt>a</tt>
3707 * @since 1.5
3708 */
3709 public static int hashCode(byte a[]) {
3710 if (a == null)
3711 return 0;
3712
3713 int result = 1;
3714 for (byte element : a)
3715 result = 31 * result + element;
3716
3717 return result;
3718 }
3719
3720 /**
3721 * Returns a hash code based on the contents of the specified array.
3722 * For any two <tt>boolean</tt> arrays <tt>a</tt> and <tt>b</tt>
3723 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3724 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3725 *
3726 * <p>The value returned by this method is the same value that would be
3727 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3728 * method on a {@link List} containing a sequence of {@link Boolean}
3729 * instances representing the elements of <tt>a</tt> in the same order.
3730 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3731 *
3732 * @param a the array whose hash value to compute
3733 * @return a content-based hash code for <tt>a</tt>
3734 * @since 1.5
3735 */
3736 public static int hashCode(boolean a[]) {
3737 if (a == null)
3738 return 0;
3739
3740 int result = 1;
3741 for (boolean element : a)
3742 result = 31 * result + (element ? 1231 : 1237);
3743
3744 return result;
3745 }
3746
3747 /**
3748 * Returns a hash code based on the contents of the specified array.
3749 * For any two <tt>float</tt> arrays <tt>a</tt> and <tt>b</tt>
3750 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3751 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3752 *
3753 * <p>The value returned by this method is the same value that would be
3754 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3755 * method on a {@link List} containing a sequence of {@link Float}
3756 * instances representing the elements of <tt>a</tt> in the same order.
3757 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3758 *
3759 * @param a the array whose hash value to compute
3760 * @return a content-based hash code for <tt>a</tt>
3761 * @since 1.5
3762 */
3763 public static int hashCode(float a[]) {
3764 if (a == null)
3765 return 0;
3766
3767 int result = 1;
3768 for (float element : a)
3769 result = 31 * result + Float.floatToIntBits(element);
3770
3771 return result;
3772 }
3773
3774 /**
3775 * Returns a hash code based on the contents of the specified array.
3776 * For any two <tt>double</tt> arrays <tt>a</tt> and <tt>b</tt>
3777 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3778 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3779 *
3780 * <p>The value returned by this method is the same value that would be
3781 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3782 * method on a {@link List} containing a sequence of {@link Double}
3783 * instances representing the elements of <tt>a</tt> in the same order.
3784 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3785 *
3786 * @param a the array whose hash value to compute
3787 * @return a content-based hash code for <tt>a</tt>
3788 * @since 1.5
3789 */
3790 public static int hashCode(double a[]) {
3791 if (a == null)
3792 return 0;
3793
3794 int result = 1;
3795 for (double element : a) {
3796 long bits = Double.doubleToLongBits(element);
3797 result = 31 * result + (int)(bits ^ (bits >>> 32));
3798 }
3799 return result;
3800 }
3801
3802 /**
3803 * Returns a hash code based on the contents of the specified array. If
3804 * the array contains other arrays as elements, the hash code is based on
3805 * their identities rather than their contents. It is therefore
3806 * acceptable to invoke this method on an array that contains itself as an
3807 * element, either directly or indirectly through one or more levels of
3808 * arrays.
3809 *
3810 * <p>For any two arrays <tt>a</tt> and <tt>b</tt> such that
3811 * <tt>Arrays.equals(a, b)</tt>, it is also the case that
3812 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3813 *
3814 * <p>The value returned by this method is equal to the value that would
3815 * be returned by <tt>Arrays.asList(a).hashCode()</tt>, unless <tt>a</tt>
3816 * is <tt>null</tt>, in which case <tt>0</tt> is returned.
3817 *
3818 * @param a the array whose content-based hash code to compute
3819 * @return a content-based hash code for <tt>a</tt>
3820 * @see #deepHashCode(Object[])
3821 * @since 1.5
3822 */
3823 public static int hashCode(Object a[]) {
3824 if (a == null)
3825 return 0;
3826
3827 int result = 1;
3828
3829 for (Object element : a)
3830 result = 31 * result + (element == null ? 0 : element.hashCode());
3831
3832 return result;
3833 }
3834
3835 /**
3836 * Returns a hash code based on the "deep contents" of the specified
3837 * array. If the array contains other arrays as elements, the
3838 * hash code is based on their contents and so on, ad infinitum.
3839 * It is therefore unacceptable to invoke this method on an array that
3840 * contains itself as an element, either directly or indirectly through
3841 * one or more levels of arrays. The behavior of such an invocation is
3842 * undefined.
3843 *
3844 * <p>For any two arrays <tt>a</tt> and <tt>b</tt> such that
3845 * <tt>Arrays.deepEquals(a, b)</tt>, it is also the case that
3846 * <tt>Arrays.deepHashCode(a) == Arrays.deepHashCode(b)</tt>.
3847 *
3848 * <p>The computation of the value returned by this method is similar to
3849 * that of the value returned by {@link List#hashCode()} on a list
3850 * containing the same elements as <tt>a</tt> in the same order, with one
3851 * difference: If an element <tt>e</tt> of <tt>a</tt> is itself an array,
3852 * its hash code is computed not by calling <tt>e.hashCode()</tt>, but as
3853 * by calling the appropriate overloading of <tt>Arrays.hashCode(e)</tt>
3854 * if <tt>e</tt> is an array of a primitive type, or as by calling
3855 * <tt>Arrays.deepHashCode(e)</tt> recursively if <tt>e</tt> is an array
3856 * of a reference type. If <tt>a</tt> is <tt>null</tt>, this method
3857 * returns 0.
3858 *
3859 * @param a the array whose deep-content-based hash code to compute
3860 * @return a deep-content-based hash code for <tt>a</tt>
3861 * @see #hashCode(Object[])
3862 * @since 1.5
3863 */
3864 public static int deepHashCode(Object a[]) {
3865 if (a == null)
3866 return 0;
3867
3868 int result = 1;
3869
3870 for (Object element : a) {
3871 int elementHash = 0;
3872 if (element instanceof Object[])
3873 elementHash = deepHashCode((Object[]) element);
3874 else if (element instanceof byte[])
3875 elementHash = hashCode((byte[]) element);
3876 else if (element instanceof short[])
3877 elementHash = hashCode((short[]) element);
3878 else if (element instanceof int[])
3879 elementHash = hashCode((int[]) element);
3880 else if (element instanceof long[])
3881 elementHash = hashCode((long[]) element);
3882 else if (element instanceof char[])
3883 elementHash = hashCode((char[]) element);
3884 else if (element instanceof float[])
3885 elementHash = hashCode((float[]) element);
3886 else if (element instanceof double[])
3887 elementHash = hashCode((double[]) element);
3888 else if (element instanceof boolean[])
3889 elementHash = hashCode((boolean[]) element);
3890 else if (element != null)
3891 elementHash = element.hashCode();
3892
3893 result = 31 * result + elementHash;
3894 }
3895
3896 return result;
3897 }
3898
3899 /**
3900 * Returns <tt>true</tt> if the two specified arrays are <i>deeply
3901 * equal</i> to one another. Unlike the {@link #equals(Object[],Object[])}
3902 * method, this method is appropriate for use with nested arrays of
3903 * arbitrary depth.
3904 *
3905 * <p>Two array references are considered deeply equal if both
3906 * are <tt>null</tt>, or if they refer to arrays that contain the same
3907 * number of elements and all corresponding pairs of elements in the two
3908 * arrays are deeply equal.
3909 *
3910 * <p>Two possibly <tt>null</tt> elements <tt>e1</tt> and <tt>e2</tt> are
3911 * deeply equal if any of the following conditions hold:
3912 * <ul>
3913 * <li> <tt>e1</tt> and <tt>e2</tt> are both arrays of object reference
3914 * types, and <tt>Arrays.deepEquals(e1, e2) would return true</tt>
3915 * <li> <tt>e1</tt> and <tt>e2</tt> are arrays of the same primitive
3916 * type, and the appropriate overloading of
3917 * <tt>Arrays.equals(e1, e2)</tt> would return true.
3918 * <li> <tt>e1 == e2</tt>
3919 * <li> <tt>e1.equals(e2)</tt> would return true.
3920 * </ul>
3921 * Note that this definition permits <tt>null</tt> elements at any depth.
3922 *
3923 * <p>If either of the specified arrays contain themselves as elements
3924 * either directly or indirectly through one or more levels of arrays,
3925 * the behavior of this method is undefined.
3926 *
3927 * @param a1 one array to be tested for equality
3928 * @param a2 the other array to be tested for equality
3929 * @return <tt>true</tt> if the two arrays are equal
3930 * @see #equals(Object[],Object[])
3931 * @since 1.5
3932 */
3933 public static boolean deepEquals(Object[] a1, Object[] a2) {
3934 if (a1 == a2)
3935 return true;
3936 if (a1 == null || a2==null)
3937 return false;
3938 int length = a1.length;
3939 if (a2.length != length)
3940 return false;
3941
3942 for (int i = 0; i < length; i++) {
3943 Object e1 = a1[i];
3944 Object e2 = a2[i];
3945
3946 if (e1 == e2)
3947 continue;
3948 if (e1 == null)
3949 return false;
3950
3951 // Figure out whether the two elements are equal
3952 boolean eq;
3953 if (e1 instanceof Object[] && e2 instanceof Object[])
3954 eq = deepEquals ((Object[]) e1, (Object[]) e2);
3955 else if (e1 instanceof byte[] && e2 instanceof byte[])
3956 eq = equals((byte[]) e1, (byte[]) e2);
3957 else if (e1 instanceof short[] && e2 instanceof short[])
3958 eq = equals((short[]) e1, (short[]) e2);
3959 else if (e1 instanceof int[] && e2 instanceof int[])
3960 eq = equals((int[]) e1, (int[]) e2);
3961 else if (e1 instanceof long[] && e2 instanceof long[])
3962 eq = equals((long[]) e1, (long[]) e2);
3963 else if (e1 instanceof char[] && e2 instanceof char[])
3964 eq = equals((char[]) e1, (char[]) e2);
3965 else if (e1 instanceof float[] && e2 instanceof float[])
3966 eq = equals((float[]) e1, (float[]) e2);
3967 else if (e1 instanceof double[] && e2 instanceof double[])
3968 eq = equals((double[]) e1, (double[]) e2);
3969 else if (e1 instanceof boolean[] && e2 instanceof boolean[])
3970 eq = equals((boolean[]) e1, (boolean[]) e2);
3971 else
3972 eq = e1.equals(e2);
3973
3974 if (!eq)
3975 return false;
3976 }
3977 return true;
3978 }
3979
3980 /**
3981 * Returns a string representation of the contents of the specified array.
3982 * The string representation consists of a list of the array's elements,
3983 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
3984 * separated by the characters <tt>", "</tt> (a comma followed by a
3985 * space). Elements are converted to strings as by
3986 * <tt>String.valueOf(long)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
3987 * is <tt>null</tt>.
3988 *
3989 * @param a the array whose string representation to return
3990 * @return a string representation of <tt>a</tt>
3991 * @since 1.5
3992 */
3993 public static String toString(long[] a) {
3994 if (a == null)
3995 return "null";
3996 int iMax = a.length - 1;
3997 if (iMax == -1)
3998 return "[]";
3999
4000 StringBuilder b = new StringBuilder();
4001 b.append('[');
4002 for (int i = 0; ; i++) {
4003 b.append(a[i]);
4004 if (i == iMax)
4005 return b.append(']').toString();
4006 b.append(", ");
4007 }
4008 }
4009
4010 /**
4011 * Returns a string representation of the contents of the specified array.
4012 * The string representation consists of a list of the array's elements,
4013 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
4014 * separated by the characters <tt>", "</tt> (a comma followed by a
4015 * space). Elements are converted to strings as by
4016 * <tt>String.valueOf(int)</tt>. Returns <tt>"null"</tt> if <tt>a</tt> is
4017 * <tt>null</tt>.
4018 *
4019 * @param a the array whose string representation to return
4020 * @return a string representation of <tt>a</tt>
4021 * @since 1.5
4022 */
4023 public static String toString(int[] a) {
4024 if (a == null)
4025 return "null";
4026 int iMax = a.length - 1;
4027 if (iMax == -1)
4028 return "[]";
4029
4030 StringBuilder b = new StringBuilder();
4031 b.append('[');
4032 for (int i = 0; ; i++) {
4033 b.append(a[i]);
4034 if (i == iMax)
4035 return b.append(']').toString();
4036 b.append(", ");
4037 }
4038 }
4039
4040 /**
4041 * Returns a string representation of the contents of the specified array.
4042 * The string representation consists of a list of the array's elements,
4043 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
4044 * separated by the characters <tt>", "</tt> (a comma followed by a
4045 * space). Elements are converted to strings as by
4046 * <tt>String.valueOf(short)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
4047 * is <tt>null</tt>.
4048 *
4049 * @param a the array whose string representation to return
4050 * @return a string representation of <tt>a</tt>
4051 * @since 1.5
4052 */
4053 public static String toString(short[] a) {
4054 if (a == null)
4055 return "null";
4056 int iMax = a.length - 1;
4057 if (iMax == -1)
4058 return "[]";
4059
4060 StringBuilder b = new StringBuilder();
4061 b.append('[');
4062 for (int i = 0; ; i++) {
4063 b.append(a[i]);
4064 if (i == iMax)
4065 return b.append(']').toString();
4066 b.append(", ");
4067 }
4068 }
4069
4070 /**
4071 * Returns a string representation of the contents of the specified array.
4072 * The string representation consists of a list of the array's elements,
4073 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
4074 * separated by the characters <tt>", "</tt> (a comma followed by a
4075 * space). Elements are converted to strings as by
4076 * <tt>String.valueOf(char)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
4077 * is <tt>null</tt>.
4078 *
4079 * @param a the array whose string representation to return
4080 * @return a string representation of <tt>a</tt>
4081 * @since 1.5
4082 */
4083 public static String toString(char[] a) {
4084 if (a == null)
4085 return "null";
4086 int iMax = a.length - 1;
4087 if (iMax == -1)
4088 return "[]";
4089
4090 StringBuilder b = new StringBuilder();
4091 b.append('[');
4092 for (int i = 0; ; i++) {
4093 b.append(a[i]);
4094 if (i == iMax)
4095 return b.append(']').toString();
4096 b.append(", ");
4097 }
4098 }
4099
4100 /**
4101 * Returns a string representation of the contents of the specified array.
4102 * The string representation consists of a list of the array's elements,
4103 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements
4104 * are separated by the characters <tt>", "</tt> (a comma followed
4105 * by a space). Elements are converted to strings as by
4106 * <tt>String.valueOf(byte)</tt>. Returns <tt>"null"</tt> if
4107 * <tt>a</tt> is <tt>null</tt>.
4108 *
4109 * @param a the array whose string representation to return
4110 * @return a string representation of <tt>a</tt>
4111 * @since 1.5
4112 */
4113 public static String toString(byte[] a) {
4114 if (a == null)
4115 return "null";
4116 int iMax = a.length - 1;
4117 if (iMax == -1)
4118 return "[]";
4119
4120 StringBuilder b = new StringBuilder();
4121 b.append('[');
4122 for (int i = 0; ; i++) {
4123 b.append(a[i]);
4124 if (i == iMax)
4125 return b.append(']').toString();
4126 b.append(", ");
4127 }
4128 }
4129
4130 /**
4131 * Returns a string representation of the contents of the specified array.
4132 * The string representation consists of a list of the array's elements,
4133 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
4134 * separated by the characters <tt>", "</tt> (a comma followed by a
4135 * space). Elements are converted to strings as by
4136 * <tt>String.valueOf(boolean)</tt>. Returns <tt>"null"</tt> if
4137 * <tt>a</tt> is <tt>null</tt>.
4138 *
4139 * @param a the array whose string representation to return
4140 * @return a string representation of <tt>a</tt>
4141 * @since 1.5
4142 */
4143 public static String toString(boolean[] a) {
4144 if (a == null)
4145 return "null";
4146 int iMax = a.length - 1;
4147 if (iMax == -1)
4148 return "[]";
4149
4150 StringBuilder b = new StringBuilder();
4151 b.append('[');
4152 for (int i = 0; ; i++) {
4153 b.append(a[i]);
4154 if (i == iMax)
4155 return b.append(']').toString();
4156 b.append(", ");
4157 }
4158 }
4159
4160 /**
4161 * Returns a string representation of the contents of the specified array.
4162 * The string representation consists of a list of the array's elements,
4163 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
4164 * separated by the characters <tt>", "</tt> (a comma followed by a
4165 * space). Elements are converted to strings as by
4166 * <tt>String.valueOf(float)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
4167 * is <tt>null</tt>.
4168 *
4169 * @param a the array whose string representation to return
4170 * @return a string representation of <tt>a</tt>
4171 * @since 1.5
4172 */
4173 public static String toString(float[] a) {
4174 if (a == null)
4175 return "null";
4176 int iMax = a.length - 1;
4177 if (iMax == -1)
4178 return "[]";
4179
4180 StringBuilder b = new StringBuilder();
4181 b.append('[');
4182 for (int i = 0; ; i++) {
4183 b.append(a[i]);
4184 if (i == iMax)
4185 return b.append(']').toString();
4186 b.append(", ");
4187 }
4188 }
4189
4190 /**
4191 * Returns a string representation of the contents of the specified array.
4192 * The string representation consists of a list of the array's elements,
4193 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
4194 * separated by the characters <tt>", "</tt> (a comma followed by a
4195 * space). Elements are converted to strings as by
4196 * <tt>String.valueOf(double)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
4197 * is <tt>null</tt>.
4198 *
4199 * @param a the array whose string representation to return
4200 * @return a string representation of <tt>a</tt>
4201 * @since 1.5
4202 */
4203 public static String toString(double[] a) {
4204 if (a == null)
4205 return "null";
4206 int iMax = a.length - 1;
4207 if (iMax == -1)
4208 return "[]";
4209
4210 StringBuilder b = new StringBuilder();
4211 b.append('[');
4212 for (int i = 0; ; i++) {
4213 b.append(a[i]);
4214 if (i == iMax)
4215 return b.append(']').toString();
4216 b.append(", ");
4217 }
4218 }
4219
4220 /**
4221 * Returns a string representation of the contents of the specified array.
4222 * If the array contains other arrays as elements, they are converted to
4223 * strings by the {@link Object#toString} method inherited from
4224 * <tt>Object</tt>, which describes their <i>identities</i> rather than
4225 * their contents.
4226 *
4227 * <p>The value returned by this method is equal to the value that would
4228 * be returned by <tt>Arrays.asList(a).toString()</tt>, unless <tt>a</tt>
4229 * is <tt>null</tt>, in which case <tt>"null"</tt> is returned.
4230 *
4231 * @param a the array whose string representation to return
4232 * @return a string representation of <tt>a</tt>
4233 * @see #deepToString(Object[])
4234 * @since 1.5
4235 */
4236 public static String toString(Object[] a) {
4237 if (a == null)
4238 return "null";
4239 int iMax = a.length - 1;
4240 if (iMax == -1)
4241 return "[]";
4242
4243 StringBuilder b = new StringBuilder();
4244 b.append('[');
4245 for (int i = 0; ; i++) {
4246 b.append(String.valueOf(a[i]));
4247 if (i == iMax)
4248 return b.append(']').toString();
4249 b.append(", ");
4250 }
4251 }
4252
4253 /**
4254 * Returns a string representation of the "deep contents" of the specified
4255 * array. If the array contains other arrays as elements, the string
4256 * representation contains their contents and so on. This method is
4257 * designed for converting multidimensional arrays to strings.
4258 *
4259 * <p>The string representation consists of a list of the array's
4260 * elements, enclosed in square brackets (<tt>"[]"</tt>). Adjacent
4261 * elements are separated by the characters <tt>", "</tt> (a comma
4262 * followed by a space). Elements are converted to strings as by
4263 * <tt>String.valueOf(Object)</tt>, unless they are themselves
4264 * arrays.
4265 *
4266 * <p>If an element <tt>e</tt> is an array of a primitive type, it is
4267 * converted to a string as by invoking the appropriate overloading of
4268 * <tt>Arrays.toString(e)</tt>. If an element <tt>e</tt> is an array of a
4269 * reference type, it is converted to a string as by invoking
4270 * this method recursively.
4271 *
4272 * <p>To avoid infinite recursion, if the specified array contains itself
4273 * as an element, or contains an indirect reference to itself through one
4274 * or more levels of arrays, the self-reference is converted to the string
4275 * <tt>"[...]"</tt>. For example, an array containing only a reference
4276 * to itself would be rendered as <tt>"[[...]]"</tt>.
4277 *
4278 * <p>This method returns <tt>"null"</tt> if the specified array
4279 * is <tt>null</tt>.
4280 *
4281 * @param a the array whose string representation to return
4282 * @return a string representation of <tt>a</tt>
4283 * @see #toString(Object[])
4284 * @since 1.5
4285 */
4286 public static String deepToString(Object[] a) {
4287 if (a == null)
4288 return "null";
4289
4290 int bufLen = 20 * a.length;
4291 if (a.length != 0 && bufLen <= 0)
4292 bufLen = Integer.MAX_VALUE;
4293 StringBuilder buf = new StringBuilder(bufLen);
4294 deepToString(a, buf, new HashSet<Object[]>());
4295 return buf.toString();
4296 }
4297
4298 private static void deepToString(Object[] a, StringBuilder buf,
4299 Set<Object[]> dejaVu) {
4300 if (a == null) {
4301 buf.append("null");
4302 return;
4303 }
4304 int iMax = a.length - 1;
4305 if (iMax == -1) {
4306 buf.append("[]");
4307 return;
4308 }
4309
4310 dejaVu.add(a);
4311 buf.append('[');
4312 for (int i = 0; ; i++) {
4313
4314 Object element = a[i];
4315 if (element == null) {
4316 buf.append("null");
4317 } else {
4318 Class eClass = element.getClass();
4319
4320 if (eClass.isArray()) {
4321 if (eClass == byte[].class)
4322 buf.append(toString((byte[]) element));
4323 else if (eClass == short[].class)
4324 buf.append(toString((short[]) element));
4325 else if (eClass == int[].class)
4326 buf.append(toString((int[]) element));
4327 else if (eClass == long[].class)
4328 buf.append(toString((long[]) element));
4329 else if (eClass == char[].class)
4330 buf.append(toString((char[]) element));
4331 else if (eClass == float[].class)
4332 buf.append(toString((float[]) element));
4333 else if (eClass == double[].class)
4334 buf.append(toString((double[]) element));
4335 else if (eClass == boolean[].class)
4336 buf.append(toString((boolean[]) element));
4337 else { // element is an array of object references
4338 if (dejaVu.contains(element))
4339 buf.append("[...]");
4340 else
4341 deepToString((Object[])element, buf, dejaVu);
4342 }
4343 } else { // element is non-null and not an array
4344 buf.append(element.toString());
4345 }
4346 }
4347 if (i == iMax)
4348 break;
4349 buf.append(", ");
4350 }
4351 buf.append(']');
4352 dejaVu.remove(a);
4353 }
4354 }