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