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