2 * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
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.
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).
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.
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
28 import java.lang.reflect.*;
29 import org.apidesign.bck2brwsr.emul.lang.System;
32 * This class contains various methods for manipulating arrays (such as
33 * sorting and searching). This class also contains a static factory
34 * that allows arrays to be viewed as lists.
36 * <p>The methods in this class all throw a {@code NullPointerException},
37 * if the specified array reference is null, except where noted.
39 * <p>The documentation for the methods contained in this class includes
40 * briefs description of the <i>implementations</i>. Such descriptions should
41 * be regarded as <i>implementation notes</i>, rather than parts of the
42 * <i>specification</i>. Implementors should feel free to substitute other
43 * algorithms, so long as the specification itself is adhered to. (For
44 * example, the algorithm used by {@code sort(Object[])} does not have to be
45 * a MergeSort, but it does have to be <i>stable</i>.)
47 * <p>This class is a member of the
48 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
49 * Java Collections Framework</a>.
58 // Suppresses default constructor, ensuring non-instantiability.
62 * Sorting of primitive type arrays.
66 * Sorts the specified array into ascending numerical order.
68 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
69 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
70 * offers O(n log(n)) performance on many data sets that cause other
71 * quicksorts to degrade to quadratic performance, and is typically
72 * faster than traditional (one-pivot) Quicksort implementations.
74 * @param a the array to be sorted
76 public static void sort(int[] a) {
77 DualPivotQuicksort.sort(a);
81 * Sorts the specified range of the array into ascending order. The range
82 * to be sorted extends from the index {@code fromIndex}, inclusive, to
83 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
84 * the range to be sorted is empty.
86 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
87 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
88 * offers O(n log(n)) performance on many data sets that cause other
89 * quicksorts to degrade to quadratic performance, and is typically
90 * faster than traditional (one-pivot) Quicksort implementations.
92 * @param a the array to be sorted
93 * @param fromIndex the index of the first element, inclusive, to be sorted
94 * @param toIndex the index of the last element, exclusive, to be sorted
96 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
97 * @throws ArrayIndexOutOfBoundsException
98 * if {@code fromIndex < 0} or {@code toIndex > a.length}
100 public static void sort(int[] a, int fromIndex, int toIndex) {
101 rangeCheck(a.length, fromIndex, toIndex);
102 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
106 * Sorts the specified array into ascending numerical order.
108 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
109 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
110 * offers O(n log(n)) performance on many data sets that cause other
111 * quicksorts to degrade to quadratic performance, and is typically
112 * faster than traditional (one-pivot) Quicksort implementations.
114 * @param a the array to be sorted
116 public static void sort(long[] a) {
117 DualPivotQuicksort.sort(a);
121 * Sorts the specified range of the array into ascending order. The range
122 * to be sorted extends from the index {@code fromIndex}, inclusive, to
123 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
124 * the range to be sorted is empty.
126 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
127 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
128 * offers O(n log(n)) performance on many data sets that cause other
129 * quicksorts to degrade to quadratic performance, and is typically
130 * faster than traditional (one-pivot) Quicksort implementations.
132 * @param a the array to be sorted
133 * @param fromIndex the index of the first element, inclusive, to be sorted
134 * @param toIndex the index of the last element, exclusive, to be sorted
136 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
137 * @throws ArrayIndexOutOfBoundsException
138 * if {@code fromIndex < 0} or {@code toIndex > a.length}
140 public static void sort(long[] a, int fromIndex, int toIndex) {
141 rangeCheck(a.length, fromIndex, toIndex);
142 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
146 * Sorts the specified array into ascending numerical order.
148 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
149 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
150 * offers O(n log(n)) performance on many data sets that cause other
151 * quicksorts to degrade to quadratic performance, and is typically
152 * faster than traditional (one-pivot) Quicksort implementations.
154 * @param a the array to be sorted
156 public static void sort(short[] a) {
157 DualPivotQuicksort.sort(a);
161 * Sorts the specified range of the array into ascending order. The range
162 * to be sorted extends from the index {@code fromIndex}, inclusive, to
163 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
164 * the range to be sorted is empty.
166 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
167 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
168 * offers O(n log(n)) performance on many data sets that cause other
169 * quicksorts to degrade to quadratic performance, and is typically
170 * faster than traditional (one-pivot) Quicksort implementations.
172 * @param a the array to be sorted
173 * @param fromIndex the index of the first element, inclusive, to be sorted
174 * @param toIndex the index of the last element, exclusive, to be sorted
176 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
177 * @throws ArrayIndexOutOfBoundsException
178 * if {@code fromIndex < 0} or {@code toIndex > a.length}
180 public static void sort(short[] a, int fromIndex, int toIndex) {
181 rangeCheck(a.length, fromIndex, toIndex);
182 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
186 * Sorts the specified array into ascending numerical order.
188 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
189 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
190 * offers O(n log(n)) performance on many data sets that cause other
191 * quicksorts to degrade to quadratic performance, and is typically
192 * faster than traditional (one-pivot) Quicksort implementations.
194 * @param a the array to be sorted
196 public static void sort(char[] a) {
197 DualPivotQuicksort.sort(a);
201 * Sorts the specified range of the array into ascending order. The range
202 * to be sorted extends from the index {@code fromIndex}, inclusive, to
203 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
204 * the range to be sorted is empty.
206 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
207 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
208 * offers O(n log(n)) performance on many data sets that cause other
209 * quicksorts to degrade to quadratic performance, and is typically
210 * faster than traditional (one-pivot) Quicksort implementations.
212 * @param a the array to be sorted
213 * @param fromIndex the index of the first element, inclusive, to be sorted
214 * @param toIndex the index of the last element, exclusive, to be sorted
216 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
217 * @throws ArrayIndexOutOfBoundsException
218 * if {@code fromIndex < 0} or {@code toIndex > a.length}
220 public static void sort(char[] a, int fromIndex, int toIndex) {
221 rangeCheck(a.length, fromIndex, toIndex);
222 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
226 * Sorts the specified array into ascending numerical order.
228 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
229 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
230 * offers O(n log(n)) performance on many data sets that cause other
231 * quicksorts to degrade to quadratic performance, and is typically
232 * faster than traditional (one-pivot) Quicksort implementations.
234 * @param a the array to be sorted
236 public static void sort(byte[] a) {
237 DualPivotQuicksort.sort(a);
241 * Sorts the specified range of the array into ascending order. The range
242 * to be sorted extends from the index {@code fromIndex}, inclusive, to
243 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
244 * the range to be sorted is empty.
246 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
247 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
248 * offers O(n log(n)) performance on many data sets that cause other
249 * quicksorts to degrade to quadratic performance, and is typically
250 * faster than traditional (one-pivot) Quicksort implementations.
252 * @param a the array to be sorted
253 * @param fromIndex the index of the first element, inclusive, to be sorted
254 * @param toIndex the index of the last element, exclusive, to be sorted
256 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
257 * @throws ArrayIndexOutOfBoundsException
258 * if {@code fromIndex < 0} or {@code toIndex > a.length}
260 public static void sort(byte[] a, int fromIndex, int toIndex) {
261 rangeCheck(a.length, fromIndex, toIndex);
262 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
266 * Sorts the specified array into ascending numerical order.
268 * <p>The {@code <} relation does not provide a total order on all float
269 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
270 * value compares neither less than, greater than, nor equal to any value,
271 * even itself. This method uses the total order imposed by the method
272 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
273 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
274 * other value and all {@code Float.NaN} values are considered equal.
276 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
277 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
278 * offers O(n log(n)) performance on many data sets that cause other
279 * quicksorts to degrade to quadratic performance, and is typically
280 * faster than traditional (one-pivot) Quicksort implementations.
282 * @param a the array to be sorted
284 public static void sort(float[] a) {
285 DualPivotQuicksort.sort(a);
289 * Sorts the specified range of the array into ascending order. The range
290 * to be sorted extends from the index {@code fromIndex}, inclusive, to
291 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
292 * the range to be sorted is empty.
294 * <p>The {@code <} relation does not provide a total order on all float
295 * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
296 * value compares neither less than, greater than, nor equal to any value,
297 * even itself. This method uses the total order imposed by the method
298 * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
299 * {@code 0.0f} and {@code Float.NaN} is considered greater than any
300 * other value and all {@code Float.NaN} values are considered equal.
302 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
303 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
304 * offers O(n log(n)) performance on many data sets that cause other
305 * quicksorts to degrade to quadratic performance, and is typically
306 * faster than traditional (one-pivot) Quicksort implementations.
308 * @param a the array to be sorted
309 * @param fromIndex the index of the first element, inclusive, to be sorted
310 * @param toIndex the index of the last element, exclusive, to be sorted
312 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
313 * @throws ArrayIndexOutOfBoundsException
314 * if {@code fromIndex < 0} or {@code toIndex > a.length}
316 public static void sort(float[] a, int fromIndex, int toIndex) {
317 rangeCheck(a.length, fromIndex, toIndex);
318 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
322 * Sorts the specified array into ascending numerical order.
324 * <p>The {@code <} relation does not provide a total order on all double
325 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
326 * value compares neither less than, greater than, nor equal to any value,
327 * even itself. This method uses the total order imposed by the method
328 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
329 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
330 * other value and all {@code Double.NaN} values are considered equal.
332 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
333 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
334 * offers O(n log(n)) performance on many data sets that cause other
335 * quicksorts to degrade to quadratic performance, and is typically
336 * faster than traditional (one-pivot) Quicksort implementations.
338 * @param a the array to be sorted
340 public static void sort(double[] a) {
341 DualPivotQuicksort.sort(a);
345 * Sorts the specified range of the array into ascending order. The range
346 * to be sorted extends from the index {@code fromIndex}, inclusive, to
347 * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
348 * the range to be sorted is empty.
350 * <p>The {@code <} relation does not provide a total order on all double
351 * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
352 * value compares neither less than, greater than, nor equal to any value,
353 * even itself. This method uses the total order imposed by the method
354 * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
355 * {@code 0.0d} and {@code Double.NaN} is considered greater than any
356 * other value and all {@code Double.NaN} values are considered equal.
358 * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
359 * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
360 * offers O(n log(n)) performance on many data sets that cause other
361 * quicksorts to degrade to quadratic performance, and is typically
362 * faster than traditional (one-pivot) Quicksort implementations.
364 * @param a the array to be sorted
365 * @param fromIndex the index of the first element, inclusive, to be sorted
366 * @param toIndex the index of the last element, exclusive, to be sorted
368 * @throws IllegalArgumentException if {@code fromIndex > toIndex}
369 * @throws ArrayIndexOutOfBoundsException
370 * if {@code fromIndex < 0} or {@code toIndex > a.length}
372 public static void sort(double[] a, int fromIndex, int toIndex) {
373 rangeCheck(a.length, fromIndex, toIndex);
374 DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
378 * Sorting of complex type arrays.
382 * Old merge sort implementation can be selected (for
383 * compatibility with broken comparators) using a system property.
384 * Cannot be a static boolean in the enclosing class due to
385 * circular dependencies. To be removed in a future release.
387 static final class LegacyMergeSort {
388 private static final boolean userRequested = false;
392 * If this platform has an optimizing VM, check whether ComparableTimSort
393 * offers any performance benefit over TimSort in conjunction with a
394 * comparator that returns:
395 * {@code ((Comparable)first).compareTo(Second)}.
396 * If not, you are better off deleting ComparableTimSort to
397 * eliminate the code duplication. In other words, the commented
398 * out code below is the preferable implementation for sorting
399 * arrays of Comparables if it offers sufficient performance.
403 // * A comparator that implements the natural ordering of a group of
404 // * mutually comparable elements. Using this comparator saves us
405 // * from duplicating most of the code in this file (one version for
406 // * Comparables, one for explicit Comparators).
408 // private static final Comparator<Object> NATURAL_ORDER =
409 // new Comparator<Object>() {
410 // @SuppressWarnings("unchecked")
411 // public int compare(Object first, Object second) {
412 // return ((Comparable<Object>)first).compareTo(second);
416 // public static void sort(Object[] a) {
417 // sort(a, 0, a.length, NATURAL_ORDER);
420 // public static void sort(Object[] a, int fromIndex, int toIndex) {
421 // sort(a, fromIndex, toIndex, NATURAL_ORDER);
425 * Sorts the specified array of objects into ascending order, according
426 * to the {@linkplain Comparable natural ordering} of its elements.
427 * All elements in the array must implement the {@link Comparable}
428 * interface. Furthermore, all elements in the array must be
429 * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must
430 * not throw a {@code ClassCastException} for any elements {@code e1}
431 * and {@code e2} in the array).
433 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
434 * not be reordered as a result of the sort.
436 * <p>Implementation note: This implementation is a stable, adaptive,
437 * iterative mergesort that requires far fewer than n lg(n) comparisons
438 * when the input array is partially sorted, while offering the
439 * performance of a traditional mergesort when the input array is
440 * randomly ordered. If the input array is nearly sorted, the
441 * implementation requires approximately n comparisons. Temporary
442 * storage requirements vary from a small constant for nearly sorted
443 * input arrays to n/2 object references for randomly ordered input
446 * <p>The implementation takes equal advantage of ascending and
447 * descending order in its input array, and can take advantage of
448 * ascending and descending order in different parts of the the same
449 * input array. It is well-suited to merging two or more sorted arrays:
450 * simply concatenate the arrays and sort the resulting array.
452 * <p>The implementation was adapted from Tim Peters's list sort for Python
453 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
454 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
455 * Sorting and Information Theoretic Complexity", in Proceedings of the
456 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
459 * @param a the array to be sorted
460 * @throws ClassCastException if the array contains elements that are not
461 * <i>mutually comparable</i> (for example, strings and integers)
462 * @throws IllegalArgumentException (optional) if the natural
463 * ordering of the array elements is found to violate the
464 * {@link Comparable} contract
466 public static void sort(Object[] a) {
467 if (LegacyMergeSort.userRequested)
470 ComparableTimSort.sort(a);
473 /** To be removed in a future release. */
474 private static void legacyMergeSort(Object[] a) {
475 Object[] aux = a.clone();
476 mergeSort(aux, a, 0, a.length, 0);
480 * Sorts the specified range of the specified array of objects into
481 * ascending order, according to the
482 * {@linkplain Comparable natural ordering} of its
483 * elements. The range to be sorted extends from index
484 * {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive.
485 * (If {@code fromIndex==toIndex}, the range to be sorted is empty.) All
486 * elements in this range must implement the {@link Comparable}
487 * interface. Furthermore, all elements in this range must be <i>mutually
488 * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a
489 * {@code ClassCastException} for any elements {@code e1} and
490 * {@code e2} in the array).
492 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
493 * not be reordered as a result of the sort.
495 * <p>Implementation note: This implementation is a stable, adaptive,
496 * iterative mergesort that requires far fewer than n lg(n) comparisons
497 * when the input array is partially sorted, while offering the
498 * performance of a traditional mergesort when the input array is
499 * randomly ordered. If the input array is nearly sorted, the
500 * implementation requires approximately n comparisons. Temporary
501 * storage requirements vary from a small constant for nearly sorted
502 * input arrays to n/2 object references for randomly ordered input
505 * <p>The implementation takes equal advantage of ascending and
506 * descending order in its input array, and can take advantage of
507 * ascending and descending order in different parts of the the same
508 * input array. It is well-suited to merging two or more sorted arrays:
509 * simply concatenate the arrays and sort the resulting array.
511 * <p>The implementation was adapted from Tim Peters's list sort for Python
512 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
513 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
514 * Sorting and Information Theoretic Complexity", in Proceedings of the
515 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
518 * @param a the array to be sorted
519 * @param fromIndex the index of the first element (inclusive) to be
521 * @param toIndex the index of the last element (exclusive) to be sorted
522 * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
523 * (optional) if the natural ordering of the array elements is
524 * found to violate the {@link Comparable} contract
525 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
526 * {@code toIndex > a.length}
527 * @throws ClassCastException if the array contains elements that are
528 * not <i>mutually comparable</i> (for example, strings and
531 public static void sort(Object[] a, int fromIndex, int toIndex) {
532 if (LegacyMergeSort.userRequested)
533 legacyMergeSort(a, fromIndex, toIndex);
535 ComparableTimSort.sort(a, fromIndex, toIndex);
538 /** To be removed in a future release. */
539 private static void legacyMergeSort(Object[] a,
540 int fromIndex, int toIndex) {
541 rangeCheck(a.length, fromIndex, toIndex);
542 Object[] aux = copyOfRange(a, fromIndex, toIndex);
543 mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
547 * Tuning parameter: list size at or below which insertion sort will be
548 * used in preference to mergesort.
549 * To be removed in a future release.
551 private static final int INSERTIONSORT_THRESHOLD = 7;
554 * Src is the source array that starts at index 0
555 * Dest is the (possibly larger) array destination with a possible offset
556 * low is the index in dest to start sorting
557 * high is the end index in dest to end sorting
558 * off is the offset to generate corresponding low, high in src
559 * To be removed in a future release.
561 private static void mergeSort(Object[] src,
566 int length = high - low;
568 // Insertion sort on smallest arrays
569 if (length < INSERTIONSORT_THRESHOLD) {
570 for (int i=low; i<high; i++)
571 for (int j=i; j>low &&
572 ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
577 // Recursively sort halves of dest into src
582 int mid = (low + high) >>> 1;
583 mergeSort(dest, src, low, mid, -off);
584 mergeSort(dest, src, mid, high, -off);
586 // If list is already sorted, just copy from src to dest. This is an
587 // optimization that results in faster sorts for nearly ordered lists.
588 if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
589 System.arraycopy(src, low, dest, destLow, length);
593 // Merge sorted halves (now in src) into dest
594 for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
595 if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
603 * Swaps x[a] with x[b].
605 private static void swap(Object[] x, int a, int b) {
612 * Sorts the specified array of objects according to the order induced by
613 * the specified comparator. All elements in the array must be
614 * <i>mutually comparable</i> by the specified comparator (that is,
615 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
616 * for any elements {@code e1} and {@code e2} in the array).
618 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
619 * not be reordered as a result of the sort.
621 * <p>Implementation note: This implementation is a stable, adaptive,
622 * iterative mergesort that requires far fewer than n lg(n) comparisons
623 * when the input array is partially sorted, while offering the
624 * performance of a traditional mergesort when the input array is
625 * randomly ordered. If the input array is nearly sorted, the
626 * implementation requires approximately n comparisons. Temporary
627 * storage requirements vary from a small constant for nearly sorted
628 * input arrays to n/2 object references for randomly ordered input
631 * <p>The implementation takes equal advantage of ascending and
632 * descending order in its input array, and can take advantage of
633 * ascending and descending order in different parts of the the same
634 * input array. It is well-suited to merging two or more sorted arrays:
635 * simply concatenate the arrays and sort the resulting array.
637 * <p>The implementation was adapted from Tim Peters's list sort for Python
638 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
639 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
640 * Sorting and Information Theoretic Complexity", in Proceedings of the
641 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
644 * @param a the array to be sorted
645 * @param c the comparator to determine the order of the array. A
646 * {@code null} value indicates that the elements'
647 * {@linkplain Comparable natural ordering} should be used.
648 * @throws ClassCastException if the array contains elements that are
649 * not <i>mutually comparable</i> using the specified comparator
650 * @throws IllegalArgumentException (optional) if the comparator is
651 * found to violate the {@link Comparator} contract
653 public static <T> void sort(T[] a, Comparator<? super T> c) {
654 if (LegacyMergeSort.userRequested)
655 legacyMergeSort(a, c);
660 /** To be removed in a future release. */
661 private static <T> void legacyMergeSort(T[] a, Comparator<? super T> c) {
664 mergeSort(aux, a, 0, a.length, 0);
666 mergeSort(aux, a, 0, a.length, 0, c);
670 * Sorts the specified range of the specified array of objects according
671 * to the order induced by the specified comparator. The range to be
672 * sorted extends from index {@code fromIndex}, inclusive, to index
673 * {@code toIndex}, exclusive. (If {@code fromIndex==toIndex}, the
674 * range to be sorted is empty.) All elements in the range must be
675 * <i>mutually comparable</i> by the specified comparator (that is,
676 * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
677 * for any elements {@code e1} and {@code e2} in the range).
679 * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
680 * not be reordered as a result of the sort.
682 * <p>Implementation note: This implementation is a stable, adaptive,
683 * iterative mergesort that requires far fewer than n lg(n) comparisons
684 * when the input array is partially sorted, while offering the
685 * performance of a traditional mergesort when the input array is
686 * randomly ordered. If the input array is nearly sorted, the
687 * implementation requires approximately n comparisons. Temporary
688 * storage requirements vary from a small constant for nearly sorted
689 * input arrays to n/2 object references for randomly ordered input
692 * <p>The implementation takes equal advantage of ascending and
693 * descending order in its input array, and can take advantage of
694 * ascending and descending order in different parts of the the same
695 * input array. It is well-suited to merging two or more sorted arrays:
696 * simply concatenate the arrays and sort the resulting array.
698 * <p>The implementation was adapted from Tim Peters's list sort for Python
699 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
700 * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
701 * Sorting and Information Theoretic Complexity", in Proceedings of the
702 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
705 * @param a the array to be sorted
706 * @param fromIndex the index of the first element (inclusive) to be
708 * @param toIndex the index of the last element (exclusive) to be sorted
709 * @param c the comparator to determine the order of the array. A
710 * {@code null} value indicates that the elements'
711 * {@linkplain Comparable natural ordering} should be used.
712 * @throws ClassCastException if the array contains elements that are not
713 * <i>mutually comparable</i> using the specified comparator.
714 * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
715 * (optional) if the comparator is found to violate the
716 * {@link Comparator} contract
717 * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
718 * {@code toIndex > a.length}
720 public static <T> void sort(T[] a, int fromIndex, int toIndex,
721 Comparator<? super T> c) {
722 if (LegacyMergeSort.userRequested)
723 legacyMergeSort(a, fromIndex, toIndex, c);
725 TimSort.sort(a, fromIndex, toIndex, c);
728 /** To be removed in a future release. */
729 private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex,
730 Comparator<? super T> c) {
731 rangeCheck(a.length, fromIndex, toIndex);
732 T[] aux = copyOfRange(a, fromIndex, toIndex);
734 mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
736 mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
740 * Src is the source array that starts at index 0
741 * Dest is the (possibly larger) array destination with a possible offset
742 * low is the index in dest to start sorting
743 * high is the end index in dest to end sorting
744 * off is the offset into src corresponding to low in dest
745 * To be removed in a future release.
747 private static void mergeSort(Object[] src,
749 int low, int high, int off,
751 int length = high - low;
753 // Insertion sort on smallest arrays
754 if (length < INSERTIONSORT_THRESHOLD) {
755 for (int i=low; i<high; i++)
756 for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
761 // Recursively sort halves of dest into src
766 int mid = (low + high) >>> 1;
767 mergeSort(dest, src, low, mid, -off, c);
768 mergeSort(dest, src, mid, high, -off, c);
770 // If list is already sorted, just copy from src to dest. This is an
771 // optimization that results in faster sorts for nearly ordered lists.
772 if (c.compare(src[mid-1], src[mid]) <= 0) {
773 System.arraycopy(src, low, dest, destLow, length);
777 // Merge sorted halves (now in src) into dest
778 for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
779 if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
787 * Checks that {@code fromIndex} and {@code toIndex} are in
788 * the range and throws an appropriate exception, if they aren't.
790 private static void rangeCheck(int length, int fromIndex, int toIndex) {
791 if (fromIndex > toIndex) {
792 throw new IllegalArgumentException(
793 "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
796 throw new ArrayIndexOutOfBoundsException(fromIndex);
798 if (toIndex > length) {
799 throw new ArrayIndexOutOfBoundsException(toIndex);
806 * Searches the specified array of longs for the specified value using the
807 * binary search algorithm. The array must be sorted (as
808 * by the {@link #sort(long[])} method) prior to making this call. If it
809 * is not sorted, the results are undefined. If the array contains
810 * multiple elements with the specified value, there is no guarantee which
813 * @param a the array to be searched
814 * @param key the value to be searched for
815 * @return index of the search key, if it is contained in the array;
816 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
817 * <i>insertion point</i> is defined as the point at which the
818 * key would be inserted into the array: the index of the first
819 * element greater than the key, or <tt>a.length</tt> if all
820 * elements in the array are less than the specified key. Note
821 * that this guarantees that the return value will be >= 0 if
822 * and only if the key is found.
824 public static int binarySearch(long[] a, long key) {
825 return binarySearch0(a, 0, a.length, key);
829 * Searches a range of
830 * the specified array of longs for the specified value using the
831 * binary search algorithm.
832 * The range must be sorted (as
833 * by the {@link #sort(long[], int, int)} method)
834 * prior to making this call. If it
835 * is not sorted, the results are undefined. If the range contains
836 * multiple elements with the specified value, there is no guarantee which
839 * @param a the array to be searched
840 * @param fromIndex the index of the first element (inclusive) to be
842 * @param toIndex the index of the last element (exclusive) to be searched
843 * @param key the value to be searched for
844 * @return index of the search key, if it is contained in the array
845 * within the specified range;
846 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
847 * <i>insertion point</i> is defined as the point at which the
848 * key would be inserted into the array: the index of the first
849 * element in the range greater than the key,
850 * or <tt>toIndex</tt> if all
851 * elements in the range are less than the specified key. Note
852 * that this guarantees that the return value will be >= 0 if
853 * and only if the key is found.
854 * @throws IllegalArgumentException
855 * if {@code fromIndex > toIndex}
856 * @throws ArrayIndexOutOfBoundsException
857 * if {@code fromIndex < 0 or toIndex > a.length}
860 public static int binarySearch(long[] a, int fromIndex, int toIndex,
862 rangeCheck(a.length, fromIndex, toIndex);
863 return binarySearch0(a, fromIndex, toIndex, key);
866 // Like public version, but without range checks.
867 private static int binarySearch0(long[] a, int fromIndex, int toIndex,
870 int high = toIndex - 1;
872 while (low <= high) {
873 int mid = (low + high) >>> 1;
874 long midVal = a[mid];
878 else if (midVal > key)
881 return mid; // key found
883 return -(low + 1); // key not found.
887 * Searches the specified array of ints for the specified value using the
888 * binary search algorithm. The array must be sorted (as
889 * by the {@link #sort(int[])} method) prior to making this call. If it
890 * is not sorted, the results are undefined. If the array contains
891 * multiple elements with the specified value, there is no guarantee which
894 * @param a the array to be searched
895 * @param key the value to be searched for
896 * @return index of the search key, if it is contained in the array;
897 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
898 * <i>insertion point</i> is defined as the point at which the
899 * key would be inserted into the array: the index of the first
900 * element greater than the key, or <tt>a.length</tt> if all
901 * elements in the array are less than the specified key. Note
902 * that this guarantees that the return value will be >= 0 if
903 * and only if the key is found.
905 public static int binarySearch(int[] a, int key) {
906 return binarySearch0(a, 0, a.length, key);
910 * Searches a range of
911 * the specified array of ints for the specified value using the
912 * binary search algorithm.
913 * The range must be sorted (as
914 * by the {@link #sort(int[], int, int)} method)
915 * prior to making this call. If it
916 * is not sorted, the results are undefined. If the range contains
917 * multiple elements with the specified value, there is no guarantee which
920 * @param a the array to be searched
921 * @param fromIndex the index of the first element (inclusive) to be
923 * @param toIndex the index of the last element (exclusive) to be searched
924 * @param key the value to be searched for
925 * @return index of the search key, if it is contained in the array
926 * within the specified range;
927 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
928 * <i>insertion point</i> is defined as the point at which the
929 * key would be inserted into the array: the index of the first
930 * element in the range greater than the key,
931 * or <tt>toIndex</tt> if all
932 * elements in the range are less than the specified key. Note
933 * that this guarantees that the return value will be >= 0 if
934 * and only if the key is found.
935 * @throws IllegalArgumentException
936 * if {@code fromIndex > toIndex}
937 * @throws ArrayIndexOutOfBoundsException
938 * if {@code fromIndex < 0 or toIndex > a.length}
941 public static int binarySearch(int[] a, int fromIndex, int toIndex,
943 rangeCheck(a.length, fromIndex, toIndex);
944 return binarySearch0(a, fromIndex, toIndex, key);
947 // Like public version, but without range checks.
948 private static int binarySearch0(int[] a, int fromIndex, int toIndex,
951 int high = toIndex - 1;
953 while (low <= high) {
954 int mid = (low + high) >>> 1;
959 else if (midVal > key)
962 return mid; // key found
964 return -(low + 1); // key not found.
968 * Searches the specified array of shorts for the specified value using
969 * the binary search algorithm. The array must be sorted
970 * (as by the {@link #sort(short[])} method) prior to making this call. If
971 * it is not sorted, the results are undefined. If the array contains
972 * multiple elements with the specified value, there is no guarantee which
975 * @param a the array to be searched
976 * @param key the value to be searched for
977 * @return index of the search key, if it is contained in the array;
978 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
979 * <i>insertion point</i> is defined as the point at which the
980 * key would be inserted into the array: the index of the first
981 * element greater than the key, or <tt>a.length</tt> if all
982 * elements in the array are less than the specified key. Note
983 * that this guarantees that the return value will be >= 0 if
984 * and only if the key is found.
986 public static int binarySearch(short[] a, short key) {
987 return binarySearch0(a, 0, a.length, key);
991 * Searches a range of
992 * the specified array of shorts for the specified value using
993 * the binary search algorithm.
994 * The range must be sorted
995 * (as by the {@link #sort(short[], int, int)} method)
996 * prior to making this call. If
997 * it is not sorted, the results are undefined. If the range contains
998 * multiple elements with the specified value, there is no guarantee which
1001 * @param a the array to be searched
1002 * @param fromIndex the index of the first element (inclusive) to be
1004 * @param toIndex the index of the last element (exclusive) to be searched
1005 * @param key the value to be searched for
1006 * @return index of the search key, if it is contained in the array
1007 * within the specified range;
1008 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1009 * <i>insertion point</i> is defined as the point at which the
1010 * key would be inserted into the array: the index of the first
1011 * element in the range greater than the key,
1012 * or <tt>toIndex</tt> if all
1013 * elements in the range are less than the specified key. Note
1014 * that this guarantees that the return value will be >= 0 if
1015 * and only if the key is found.
1016 * @throws IllegalArgumentException
1017 * if {@code fromIndex > toIndex}
1018 * @throws ArrayIndexOutOfBoundsException
1019 * if {@code fromIndex < 0 or toIndex > a.length}
1022 public static int binarySearch(short[] a, int fromIndex, int toIndex,
1024 rangeCheck(a.length, fromIndex, toIndex);
1025 return binarySearch0(a, fromIndex, toIndex, key);
1028 // Like public version, but without range checks.
1029 private static int binarySearch0(short[] a, int fromIndex, int toIndex,
1031 int low = fromIndex;
1032 int high = toIndex - 1;
1034 while (low <= high) {
1035 int mid = (low + high) >>> 1;
1036 short midVal = a[mid];
1040 else if (midVal > key)
1043 return mid; // key found
1045 return -(low + 1); // key not found.
1049 * Searches the specified array of chars for the specified value using the
1050 * binary search algorithm. The array must be sorted (as
1051 * by the {@link #sort(char[])} method) prior to making this call. If it
1052 * is not sorted, the results are undefined. If the array contains
1053 * multiple elements with the specified value, there is no guarantee which
1054 * one will be found.
1056 * @param a the array to be searched
1057 * @param key the value to be searched for
1058 * @return index of the search key, if it is contained in the array;
1059 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1060 * <i>insertion point</i> is defined as the point at which the
1061 * key would be inserted into the array: the index of the first
1062 * element greater than the key, or <tt>a.length</tt> if all
1063 * elements in the array are less than the specified key. Note
1064 * that this guarantees that the return value will be >= 0 if
1065 * and only if the key is found.
1067 public static int binarySearch(char[] a, char key) {
1068 return binarySearch0(a, 0, a.length, key);
1072 * Searches a range of
1073 * the specified array of chars for the specified value using the
1074 * binary search algorithm.
1075 * The range must be sorted (as
1076 * by the {@link #sort(char[], int, int)} method)
1077 * prior to making this call. If it
1078 * is not sorted, the results are undefined. If the range contains
1079 * multiple elements with the specified value, there is no guarantee which
1080 * one will be found.
1082 * @param a the array to be searched
1083 * @param fromIndex the index of the first element (inclusive) to be
1085 * @param toIndex the index of the last element (exclusive) to be searched
1086 * @param key the value to be searched for
1087 * @return index of the search key, if it is contained in the array
1088 * within the specified range;
1089 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1090 * <i>insertion point</i> is defined as the point at which the
1091 * key would be inserted into the array: the index of the first
1092 * element in the range greater than the key,
1093 * or <tt>toIndex</tt> if all
1094 * elements in the range are less than the specified key. Note
1095 * that this guarantees that the return value will be >= 0 if
1096 * and only if the key is found.
1097 * @throws IllegalArgumentException
1098 * if {@code fromIndex > toIndex}
1099 * @throws ArrayIndexOutOfBoundsException
1100 * if {@code fromIndex < 0 or toIndex > a.length}
1103 public static int binarySearch(char[] a, int fromIndex, int toIndex,
1105 rangeCheck(a.length, fromIndex, toIndex);
1106 return binarySearch0(a, fromIndex, toIndex, key);
1109 // Like public version, but without range checks.
1110 private static int binarySearch0(char[] a, int fromIndex, int toIndex,
1112 int low = fromIndex;
1113 int high = toIndex - 1;
1115 while (low <= high) {
1116 int mid = (low + high) >>> 1;
1117 char midVal = a[mid];
1121 else if (midVal > key)
1124 return mid; // key found
1126 return -(low + 1); // key not found.
1130 * Searches the specified array of bytes for the specified value using the
1131 * binary search algorithm. The array must be sorted (as
1132 * by the {@link #sort(byte[])} method) prior to making this call. If it
1133 * is not sorted, the results are undefined. If the array contains
1134 * multiple elements with the specified value, there is no guarantee which
1135 * one will be found.
1137 * @param a the array to be searched
1138 * @param key the value to be searched for
1139 * @return index of the search key, if it is contained in the array;
1140 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1141 * <i>insertion point</i> is defined as the point at which the
1142 * key would be inserted into the array: the index of the first
1143 * element greater than the key, or <tt>a.length</tt> if all
1144 * elements in the array are less than the specified key. Note
1145 * that this guarantees that the return value will be >= 0 if
1146 * and only if the key is found.
1148 public static int binarySearch(byte[] a, byte key) {
1149 return binarySearch0(a, 0, a.length, key);
1153 * Searches a range of
1154 * the specified array of bytes for the specified value using the
1155 * binary search algorithm.
1156 * The range must be sorted (as
1157 * by the {@link #sort(byte[], int, int)} method)
1158 * prior to making this call. If it
1159 * is not sorted, the results are undefined. If the range contains
1160 * multiple elements with the specified value, there is no guarantee which
1161 * one will be found.
1163 * @param a the array to be searched
1164 * @param fromIndex the index of the first element (inclusive) to be
1166 * @param toIndex the index of the last element (exclusive) to be searched
1167 * @param key the value to be searched for
1168 * @return index of the search key, if it is contained in the array
1169 * within the specified range;
1170 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1171 * <i>insertion point</i> is defined as the point at which the
1172 * key would be inserted into the array: the index of the first
1173 * element in the range greater than the key,
1174 * or <tt>toIndex</tt> if all
1175 * elements in the range are less than the specified key. Note
1176 * that this guarantees that the return value will be >= 0 if
1177 * and only if the key is found.
1178 * @throws IllegalArgumentException
1179 * if {@code fromIndex > toIndex}
1180 * @throws ArrayIndexOutOfBoundsException
1181 * if {@code fromIndex < 0 or toIndex > a.length}
1184 public static int binarySearch(byte[] a, int fromIndex, int toIndex,
1186 rangeCheck(a.length, fromIndex, toIndex);
1187 return binarySearch0(a, fromIndex, toIndex, key);
1190 // Like public version, but without range checks.
1191 private static int binarySearch0(byte[] a, int fromIndex, int toIndex,
1193 int low = fromIndex;
1194 int high = toIndex - 1;
1196 while (low <= high) {
1197 int mid = (low + high) >>> 1;
1198 byte midVal = a[mid];
1202 else if (midVal > key)
1205 return mid; // key found
1207 return -(low + 1); // key not found.
1211 * Searches the specified array of doubles for the specified value using
1212 * the binary search algorithm. The array must be sorted
1213 * (as by the {@link #sort(double[])} method) prior to making this call.
1214 * If it is not sorted, the results are undefined. If the array contains
1215 * multiple elements with the specified value, there is no guarantee which
1216 * one will be found. This method considers all NaN values to be
1217 * equivalent and equal.
1219 * @param a the array to be searched
1220 * @param key the value to be searched for
1221 * @return index of the search key, if it is contained in the array;
1222 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1223 * <i>insertion point</i> is defined as the point at which the
1224 * key would be inserted into the array: the index of the first
1225 * element greater than the key, or <tt>a.length</tt> if all
1226 * elements in the array are less than the specified key. Note
1227 * that this guarantees that the return value will be >= 0 if
1228 * and only if the key is found.
1230 public static int binarySearch(double[] a, double key) {
1231 return binarySearch0(a, 0, a.length, key);
1235 * Searches a range of
1236 * the specified array of doubles for the specified value using
1237 * the binary search algorithm.
1238 * The range must be sorted
1239 * (as by the {@link #sort(double[], int, int)} method)
1240 * prior to making this call.
1241 * If it is not sorted, the results are undefined. If the range contains
1242 * multiple elements with the specified value, there is no guarantee which
1243 * one will be found. This method considers all NaN values to be
1244 * equivalent and equal.
1246 * @param a the array to be searched
1247 * @param fromIndex the index of the first element (inclusive) to be
1249 * @param toIndex the index of the last element (exclusive) to be searched
1250 * @param key the value to be searched for
1251 * @return index of the search key, if it is contained in the array
1252 * within the specified range;
1253 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1254 * <i>insertion point</i> is defined as the point at which the
1255 * key would be inserted into the array: the index of the first
1256 * element in the range greater than the key,
1257 * or <tt>toIndex</tt> if all
1258 * elements in the range are less than the specified key. Note
1259 * that this guarantees that the return value will be >= 0 if
1260 * and only if the key is found.
1261 * @throws IllegalArgumentException
1262 * if {@code fromIndex > toIndex}
1263 * @throws ArrayIndexOutOfBoundsException
1264 * if {@code fromIndex < 0 or toIndex > a.length}
1267 public static int binarySearch(double[] a, int fromIndex, int toIndex,
1269 rangeCheck(a.length, fromIndex, toIndex);
1270 return binarySearch0(a, fromIndex, toIndex, key);
1273 // Like public version, but without range checks.
1274 private static int binarySearch0(double[] a, int fromIndex, int toIndex,
1276 int low = fromIndex;
1277 int high = toIndex - 1;
1279 while (low <= high) {
1280 int mid = (low + high) >>> 1;
1281 double midVal = a[mid];
1284 low = mid + 1; // Neither val is NaN, thisVal is smaller
1285 else if (midVal > key)
1286 high = mid - 1; // Neither val is NaN, thisVal is larger
1288 long midBits = Double.doubleToLongBits(midVal);
1289 long keyBits = Double.doubleToLongBits(key);
1290 if (midBits == keyBits) // Values are equal
1291 return mid; // Key found
1292 else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
1294 else // (0.0, -0.0) or (NaN, !NaN)
1298 return -(low + 1); // key not found.
1302 * Searches the specified array of floats for the specified value using
1303 * the binary search algorithm. The array must be sorted
1304 * (as by the {@link #sort(float[])} method) prior to making this call. If
1305 * it is not sorted, the results are undefined. If the array contains
1306 * multiple elements with the specified value, there is no guarantee which
1307 * one will be found. This method considers all NaN values to be
1308 * equivalent and equal.
1310 * @param a the array to be searched
1311 * @param key the value to be searched for
1312 * @return index of the search key, if it is contained in the array;
1313 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1314 * <i>insertion point</i> is defined as the point at which the
1315 * key would be inserted into the array: the index of the first
1316 * element greater than the key, or <tt>a.length</tt> if all
1317 * elements in the array are less than the specified key. Note
1318 * that this guarantees that the return value will be >= 0 if
1319 * and only if the key is found.
1321 public static int binarySearch(float[] a, float key) {
1322 return binarySearch0(a, 0, a.length, key);
1326 * Searches a range of
1327 * the specified array of floats for the specified value using
1328 * the binary search algorithm.
1329 * The range must be sorted
1330 * (as by the {@link #sort(float[], int, int)} method)
1331 * prior to making this call. If
1332 * it is not sorted, the results are undefined. If the range contains
1333 * multiple elements with the specified value, there is no guarantee which
1334 * one will be found. This method considers all NaN values to be
1335 * equivalent and equal.
1337 * @param a the array to be searched
1338 * @param fromIndex the index of the first element (inclusive) to be
1340 * @param toIndex the index of the last element (exclusive) to be searched
1341 * @param key the value to be searched for
1342 * @return index of the search key, if it is contained in the array
1343 * within the specified range;
1344 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1345 * <i>insertion point</i> is defined as the point at which the
1346 * key would be inserted into the array: the index of the first
1347 * element in the range greater than the key,
1348 * or <tt>toIndex</tt> if all
1349 * elements in the range are less than the specified key. Note
1350 * that this guarantees that the return value will be >= 0 if
1351 * and only if the key is found.
1352 * @throws IllegalArgumentException
1353 * if {@code fromIndex > toIndex}
1354 * @throws ArrayIndexOutOfBoundsException
1355 * if {@code fromIndex < 0 or toIndex > a.length}
1358 public static int binarySearch(float[] a, int fromIndex, int toIndex,
1360 rangeCheck(a.length, fromIndex, toIndex);
1361 return binarySearch0(a, fromIndex, toIndex, key);
1364 // Like public version, but without range checks.
1365 private static int binarySearch0(float[] a, int fromIndex, int toIndex,
1367 int low = fromIndex;
1368 int high = toIndex - 1;
1370 while (low <= high) {
1371 int mid = (low + high) >>> 1;
1372 float midVal = a[mid];
1375 low = mid + 1; // Neither val is NaN, thisVal is smaller
1376 else if (midVal > key)
1377 high = mid - 1; // Neither val is NaN, thisVal is larger
1379 int midBits = Float.floatToIntBits(midVal);
1380 int keyBits = Float.floatToIntBits(key);
1381 if (midBits == keyBits) // Values are equal
1382 return mid; // Key found
1383 else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
1385 else // (0.0, -0.0) or (NaN, !NaN)
1389 return -(low + 1); // key not found.
1393 * Searches the specified array for the specified object using the binary
1394 * search algorithm. The array must be sorted into ascending order
1396 * {@linkplain Comparable natural ordering}
1397 * of its elements (as by the
1398 * {@link #sort(Object[])} method) prior to making this call.
1399 * If it is not sorted, the results are undefined.
1400 * (If the array contains elements that are not mutually comparable (for
1401 * example, strings and integers), it <i>cannot</i> be sorted according
1402 * to the natural ordering of its elements, hence results are undefined.)
1403 * If the array contains multiple
1404 * elements equal to the specified object, there is no guarantee which
1405 * one will be found.
1407 * @param a the array to be searched
1408 * @param key the value to be searched for
1409 * @return index of the search key, if it is contained in the array;
1410 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1411 * <i>insertion point</i> is defined as the point at which the
1412 * key would be inserted into the array: the index of the first
1413 * element greater than the key, or <tt>a.length</tt> if all
1414 * elements in the array are less than the specified key. Note
1415 * that this guarantees that the return value will be >= 0 if
1416 * and only if the key is found.
1417 * @throws ClassCastException if the search key is not comparable to the
1418 * elements of the array.
1420 public static int binarySearch(Object[] a, Object key) {
1421 return binarySearch0(a, 0, a.length, key);
1425 * Searches a range of
1426 * the specified array for the specified object using the binary
1428 * The range must be sorted into ascending order
1430 * {@linkplain Comparable natural ordering}
1431 * of its elements (as by the
1432 * {@link #sort(Object[], int, int)} method) prior to making this
1433 * call. If it is not sorted, the results are undefined.
1434 * (If the range contains elements that are not mutually comparable (for
1435 * example, strings and integers), it <i>cannot</i> be sorted according
1436 * to the natural ordering of its elements, hence results are undefined.)
1437 * If the range contains multiple
1438 * elements equal to the specified object, there is no guarantee which
1439 * one will be found.
1441 * @param a the array to be searched
1442 * @param fromIndex the index of the first element (inclusive) to be
1444 * @param toIndex the index of the last element (exclusive) to be searched
1445 * @param key the value to be searched for
1446 * @return index of the search key, if it is contained in the array
1447 * within the specified range;
1448 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1449 * <i>insertion point</i> is defined as the point at which the
1450 * key would be inserted into the array: the index of the first
1451 * element in the range greater than the key,
1452 * or <tt>toIndex</tt> if all
1453 * elements in the range are less than the specified key. Note
1454 * that this guarantees that the return value will be >= 0 if
1455 * and only if the key is found.
1456 * @throws ClassCastException if the search key is not comparable to the
1457 * elements of the array within the specified range.
1458 * @throws IllegalArgumentException
1459 * if {@code fromIndex > toIndex}
1460 * @throws ArrayIndexOutOfBoundsException
1461 * if {@code fromIndex < 0 or toIndex > a.length}
1464 public static int binarySearch(Object[] a, int fromIndex, int toIndex,
1466 rangeCheck(a.length, fromIndex, toIndex);
1467 return binarySearch0(a, fromIndex, toIndex, key);
1470 // Like public version, but without range checks.
1471 private static int binarySearch0(Object[] a, int fromIndex, int toIndex,
1473 int low = fromIndex;
1474 int high = toIndex - 1;
1476 while (low <= high) {
1477 int mid = (low + high) >>> 1;
1478 Comparable midVal = (Comparable)a[mid];
1479 int cmp = midVal.compareTo(key);
1486 return mid; // key found
1488 return -(low + 1); // key not found.
1492 * Searches the specified array for the specified object using the binary
1493 * search algorithm. The array must be sorted into ascending order
1494 * according to the specified comparator (as by the
1495 * {@link #sort(Object[], Comparator) sort(T[], Comparator)}
1496 * method) prior to making this call. If it is
1497 * not sorted, the results are undefined.
1498 * If the array contains multiple
1499 * elements equal to the specified object, there is no guarantee which one
1502 * @param a the array to be searched
1503 * @param key the value to be searched for
1504 * @param c the comparator by which the array is ordered. A
1505 * <tt>null</tt> value indicates that the elements'
1506 * {@linkplain Comparable natural ordering} should be used.
1507 * @return index of the search key, if it is contained in the array;
1508 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1509 * <i>insertion point</i> is defined as the point at which the
1510 * key would be inserted into the array: the index of the first
1511 * element greater than the key, or <tt>a.length</tt> if all
1512 * elements in the array are less than the specified key. Note
1513 * that this guarantees that the return value will be >= 0 if
1514 * and only if the key is found.
1515 * @throws ClassCastException if the array contains elements that are not
1516 * <i>mutually comparable</i> using the specified comparator,
1517 * or the search key is not comparable to the
1518 * elements of the array using this comparator.
1520 public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) {
1521 return binarySearch0(a, 0, a.length, key, c);
1525 * Searches a range of
1526 * the specified array for the specified object using the binary
1528 * The range must be sorted into ascending order
1529 * according to the specified comparator (as by the
1530 * {@link #sort(Object[], int, int, Comparator)
1531 * sort(T[], int, int, Comparator)}
1532 * method) prior to making this call.
1533 * If it is not sorted, the results are undefined.
1534 * If the range contains multiple elements equal to the specified object,
1535 * there is no guarantee which one will be found.
1537 * @param a the array to be searched
1538 * @param fromIndex the index of the first element (inclusive) to be
1540 * @param toIndex the index of the last element (exclusive) to be searched
1541 * @param key the value to be searched for
1542 * @param c the comparator by which the array is ordered. A
1543 * <tt>null</tt> value indicates that the elements'
1544 * {@linkplain Comparable natural ordering} should be used.
1545 * @return index of the search key, if it is contained in the array
1546 * within the specified range;
1547 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1548 * <i>insertion point</i> is defined as the point at which the
1549 * key would be inserted into the array: the index of the first
1550 * element in the range greater than the key,
1551 * or <tt>toIndex</tt> if all
1552 * elements in the range are less than the specified key. Note
1553 * that this guarantees that the return value will be >= 0 if
1554 * and only if the key is found.
1555 * @throws ClassCastException if the range contains elements that are not
1556 * <i>mutually comparable</i> using the specified comparator,
1557 * or the search key is not comparable to the
1558 * elements in the range using this comparator.
1559 * @throws IllegalArgumentException
1560 * if {@code fromIndex > toIndex}
1561 * @throws ArrayIndexOutOfBoundsException
1562 * if {@code fromIndex < 0 or toIndex > a.length}
1565 public static <T> int binarySearch(T[] a, int fromIndex, int toIndex,
1566 T key, Comparator<? super T> c) {
1567 rangeCheck(a.length, fromIndex, toIndex);
1568 return binarySearch0(a, fromIndex, toIndex, key, c);
1571 // Like public version, but without range checks.
1572 private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex,
1573 T key, Comparator<? super T> c) {
1575 return binarySearch0(a, fromIndex, toIndex, key);
1577 int low = fromIndex;
1578 int high = toIndex - 1;
1580 while (low <= high) {
1581 int mid = (low + high) >>> 1;
1583 int cmp = c.compare(midVal, key);
1589 return mid; // key found
1591 return -(low + 1); // key not found.
1597 * Returns <tt>true</tt> if the two specified arrays of longs are
1598 * <i>equal</i> to one another. Two arrays are considered equal if both
1599 * arrays contain the same number of elements, and all corresponding pairs
1600 * of elements in the two arrays are equal. In other words, two arrays
1601 * are equal if they contain the same elements in the same order. Also,
1602 * two array references are considered equal if both are <tt>null</tt>.<p>
1604 * @param a one array to be tested for equality
1605 * @param a2 the other array to be tested for equality
1606 * @return <tt>true</tt> if the two arrays are equal
1608 public static boolean equals(long[] a, long[] a2) {
1611 if (a==null || a2==null)
1614 int length = a.length;
1615 if (a2.length != length)
1618 for (int i=0; i<length; i++)
1626 * Returns <tt>true</tt> if the two specified arrays of ints are
1627 * <i>equal</i> to one another. Two arrays are considered equal if both
1628 * arrays contain the same number of elements, and all corresponding pairs
1629 * of elements in the two arrays are equal. In other words, two arrays
1630 * are equal if they contain the same elements in the same order. Also,
1631 * two array references are considered equal if both are <tt>null</tt>.<p>
1633 * @param a one array to be tested for equality
1634 * @param a2 the other array to be tested for equality
1635 * @return <tt>true</tt> if the two arrays are equal
1637 public static boolean equals(int[] a, int[] a2) {
1640 if (a==null || a2==null)
1643 int length = a.length;
1644 if (a2.length != length)
1647 for (int i=0; i<length; i++)
1655 * Returns <tt>true</tt> if the two specified arrays of shorts are
1656 * <i>equal</i> to one another. Two arrays are considered equal if both
1657 * arrays contain the same number of elements, and all corresponding pairs
1658 * of elements in the two arrays are equal. In other words, two arrays
1659 * are equal if they contain the same elements in the same order. Also,
1660 * two array references are considered equal if both are <tt>null</tt>.<p>
1662 * @param a one array to be tested for equality
1663 * @param a2 the other array to be tested for equality
1664 * @return <tt>true</tt> if the two arrays are equal
1666 public static boolean equals(short[] a, short a2[]) {
1669 if (a==null || a2==null)
1672 int length = a.length;
1673 if (a2.length != length)
1676 for (int i=0; i<length; i++)
1684 * Returns <tt>true</tt> if the two specified arrays of chars are
1685 * <i>equal</i> to one another. Two arrays are considered equal if both
1686 * arrays contain the same number of elements, and all corresponding pairs
1687 * of elements in the two arrays are equal. In other words, two arrays
1688 * are equal if they contain the same elements in the same order. Also,
1689 * two array references are considered equal if both are <tt>null</tt>.<p>
1691 * @param a one array to be tested for equality
1692 * @param a2 the other array to be tested for equality
1693 * @return <tt>true</tt> if the two arrays are equal
1695 public static boolean equals(char[] a, char[] a2) {
1698 if (a==null || a2==null)
1701 int length = a.length;
1702 if (a2.length != length)
1705 for (int i=0; i<length; i++)
1713 * Returns <tt>true</tt> if the two specified arrays of bytes are
1714 * <i>equal</i> to one another. Two arrays are considered equal if both
1715 * arrays contain the same number of elements, and all corresponding pairs
1716 * of elements in the two arrays are equal. In other words, two arrays
1717 * are equal if they contain the same elements in the same order. Also,
1718 * two array references are considered equal if both are <tt>null</tt>.<p>
1720 * @param a one array to be tested for equality
1721 * @param a2 the other array to be tested for equality
1722 * @return <tt>true</tt> if the two arrays are equal
1724 public static boolean equals(byte[] a, byte[] a2) {
1727 if (a==null || a2==null)
1730 int length = a.length;
1731 if (a2.length != length)
1734 for (int i=0; i<length; i++)
1742 * Returns <tt>true</tt> if the two specified arrays of booleans are
1743 * <i>equal</i> to one another. Two arrays are considered equal if both
1744 * arrays contain the same number of elements, and all corresponding pairs
1745 * of elements in the two arrays are equal. In other words, two arrays
1746 * are equal if they contain the same elements in the same order. Also,
1747 * two array references are considered equal if both are <tt>null</tt>.<p>
1749 * @param a one array to be tested for equality
1750 * @param a2 the other array to be tested for equality
1751 * @return <tt>true</tt> if the two arrays are equal
1753 public static boolean equals(boolean[] a, boolean[] a2) {
1756 if (a==null || a2==null)
1759 int length = a.length;
1760 if (a2.length != length)
1763 for (int i=0; i<length; i++)
1771 * Returns <tt>true</tt> if the two specified arrays of doubles are
1772 * <i>equal</i> to one another. Two arrays are considered equal if both
1773 * arrays contain the same number of elements, and all corresponding pairs
1774 * of elements in the two arrays are equal. In other words, two arrays
1775 * are equal if they contain the same elements in the same order. Also,
1776 * two array references are considered equal if both are <tt>null</tt>.<p>
1778 * Two doubles <tt>d1</tt> and <tt>d2</tt> are considered equal if:
1779 * <pre> <tt>new Double(d1).equals(new Double(d2))</tt></pre>
1780 * (Unlike the <tt>==</tt> operator, this method considers
1781 * <tt>NaN</tt> equals to itself, and 0.0d unequal to -0.0d.)
1783 * @param a one array to be tested for equality
1784 * @param a2 the other array to be tested for equality
1785 * @return <tt>true</tt> if the two arrays are equal
1786 * @see Double#equals(Object)
1788 public static boolean equals(double[] a, double[] a2) {
1791 if (a==null || a2==null)
1794 int length = a.length;
1795 if (a2.length != length)
1798 for (int i=0; i<length; i++)
1799 if (Double.doubleToLongBits(a[i])!=Double.doubleToLongBits(a2[i]))
1806 * Returns <tt>true</tt> if the two specified arrays of floats are
1807 * <i>equal</i> to one another. Two arrays are considered equal if both
1808 * arrays contain the same number of elements, and all corresponding pairs
1809 * of elements in the two arrays are equal. In other words, two arrays
1810 * are equal if they contain the same elements in the same order. Also,
1811 * two array references are considered equal if both are <tt>null</tt>.<p>
1813 * Two floats <tt>f1</tt> and <tt>f2</tt> are considered equal if:
1814 * <pre> <tt>new Float(f1).equals(new Float(f2))</tt></pre>
1815 * (Unlike the <tt>==</tt> operator, this method considers
1816 * <tt>NaN</tt> equals to itself, and 0.0f unequal to -0.0f.)
1818 * @param a one array to be tested for equality
1819 * @param a2 the other array to be tested for equality
1820 * @return <tt>true</tt> if the two arrays are equal
1821 * @see Float#equals(Object)
1823 public static boolean equals(float[] a, float[] a2) {
1826 if (a==null || a2==null)
1829 int length = a.length;
1830 if (a2.length != length)
1833 for (int i=0; i<length; i++)
1834 if (Float.floatToIntBits(a[i])!=Float.floatToIntBits(a2[i]))
1841 * Returns <tt>true</tt> if the two specified arrays of Objects are
1842 * <i>equal</i> to one another. The two arrays are considered equal if
1843 * both arrays contain the same number of elements, and all corresponding
1844 * pairs of elements in the two arrays are equal. Two objects <tt>e1</tt>
1845 * and <tt>e2</tt> are considered <i>equal</i> if <tt>(e1==null ? e2==null
1846 * : e1.equals(e2))</tt>. In other words, the two arrays are equal if
1847 * they contain the same elements in the same order. Also, two array
1848 * references are considered equal if both are <tt>null</tt>.<p>
1850 * @param a one array to be tested for equality
1851 * @param a2 the other array to be tested for equality
1852 * @return <tt>true</tt> if the two arrays are equal
1854 public static boolean equals(Object[] a, Object[] a2) {
1857 if (a==null || a2==null)
1860 int length = a.length;
1861 if (a2.length != length)
1864 for (int i=0; i<length; i++) {
1867 if (!(o1==null ? o2==null : o1.equals(o2)))
1877 * Assigns the specified long value to each element of the specified array
1880 * @param a the array to be filled
1881 * @param val the value to be stored in all elements of the array
1883 public static void fill(long[] a, long val) {
1884 for (int i = 0, len = a.length; i < len; i++)
1889 * Assigns the specified long value to each element of the specified
1890 * range of the specified array of longs. The range to be filled
1891 * extends from index <tt>fromIndex</tt>, inclusive, to index
1892 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
1893 * range to be filled is empty.)
1895 * @param a the array to be filled
1896 * @param fromIndex the index of the first element (inclusive) to be
1897 * filled with the specified value
1898 * @param toIndex the index of the last element (exclusive) to be
1899 * filled with the specified value
1900 * @param val the value to be stored in all elements of the array
1901 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1902 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1903 * <tt>toIndex > a.length</tt>
1905 public static void fill(long[] a, int fromIndex, int toIndex, long val) {
1906 rangeCheck(a.length, fromIndex, toIndex);
1907 for (int i = fromIndex; i < toIndex; i++)
1912 * Assigns the specified int value to each element of the specified array
1915 * @param a the array to be filled
1916 * @param val the value to be stored in all elements of the array
1918 public static void fill(int[] a, int val) {
1919 for (int i = 0, len = a.length; i < len; i++)
1924 * Assigns the specified int value to each element of the specified
1925 * range of the specified array of ints. The range to be filled
1926 * extends from index <tt>fromIndex</tt>, inclusive, to index
1927 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
1928 * range to be filled is empty.)
1930 * @param a the array to be filled
1931 * @param fromIndex the index of the first element (inclusive) to be
1932 * filled with the specified value
1933 * @param toIndex the index of the last element (exclusive) to be
1934 * filled with the specified value
1935 * @param val the value to be stored in all elements of the array
1936 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1937 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1938 * <tt>toIndex > a.length</tt>
1940 public static void fill(int[] a, int fromIndex, int toIndex, int val) {
1941 rangeCheck(a.length, fromIndex, toIndex);
1942 for (int i = fromIndex; i < toIndex; i++)
1947 * Assigns the specified short value to each element of the specified array
1950 * @param a the array to be filled
1951 * @param val the value to be stored in all elements of the array
1953 public static void fill(short[] a, short val) {
1954 for (int i = 0, len = a.length; i < len; i++)
1959 * Assigns the specified short value to each element of the specified
1960 * range of the specified array of shorts. The range to be filled
1961 * extends from index <tt>fromIndex</tt>, inclusive, to index
1962 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
1963 * range to be filled is empty.)
1965 * @param a the array to be filled
1966 * @param fromIndex the index of the first element (inclusive) to be
1967 * filled with the specified value
1968 * @param toIndex the index of the last element (exclusive) to be
1969 * filled with the specified value
1970 * @param val the value to be stored in all elements of the array
1971 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1972 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1973 * <tt>toIndex > a.length</tt>
1975 public static void fill(short[] a, int fromIndex, int toIndex, short val) {
1976 rangeCheck(a.length, fromIndex, toIndex);
1977 for (int i = fromIndex; i < toIndex; i++)
1982 * Assigns the specified char value to each element of the specified array
1985 * @param a the array to be filled
1986 * @param val the value to be stored in all elements of the array
1988 public static void fill(char[] a, char val) {
1989 for (int i = 0, len = a.length; i < len; i++)
1994 * Assigns the specified char value to each element of the specified
1995 * range of the specified array of chars. The range to be filled
1996 * extends from index <tt>fromIndex</tt>, inclusive, to index
1997 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
1998 * range to be filled is empty.)
2000 * @param a the array to be filled
2001 * @param fromIndex the index of the first element (inclusive) to be
2002 * filled with the specified value
2003 * @param toIndex the index of the last element (exclusive) to be
2004 * filled with the specified value
2005 * @param val the value to be stored in all elements of the array
2006 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2007 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2008 * <tt>toIndex > a.length</tt>
2010 public static void fill(char[] a, int fromIndex, int toIndex, char val) {
2011 rangeCheck(a.length, fromIndex, toIndex);
2012 for (int i = fromIndex; i < toIndex; i++)
2017 * Assigns the specified byte value to each element of the specified array
2020 * @param a the array to be filled
2021 * @param val the value to be stored in all elements of the array
2023 public static void fill(byte[] a, byte val) {
2024 for (int i = 0, len = a.length; i < len; i++)
2029 * Assigns the specified byte value to each element of the specified
2030 * range of the specified array of bytes. The range to be filled
2031 * extends from index <tt>fromIndex</tt>, inclusive, to index
2032 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2033 * range to be filled is empty.)
2035 * @param a the array to be filled
2036 * @param fromIndex the index of the first element (inclusive) to be
2037 * filled with the specified value
2038 * @param toIndex the index of the last element (exclusive) to be
2039 * filled with the specified value
2040 * @param val the value to be stored in all elements of the array
2041 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2042 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2043 * <tt>toIndex > a.length</tt>
2045 public static void fill(byte[] a, int fromIndex, int toIndex, byte val) {
2046 rangeCheck(a.length, fromIndex, toIndex);
2047 for (int i = fromIndex; i < toIndex; i++)
2052 * Assigns the specified boolean value to each element of the specified
2053 * array of booleans.
2055 * @param a the array to be filled
2056 * @param val the value to be stored in all elements of the array
2058 public static void fill(boolean[] a, boolean val) {
2059 for (int i = 0, len = a.length; i < len; i++)
2064 * Assigns the specified boolean value to each element of the specified
2065 * range of the specified array of booleans. The range to be filled
2066 * extends from index <tt>fromIndex</tt>, inclusive, to index
2067 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2068 * range to be filled is empty.)
2070 * @param a the array to be filled
2071 * @param fromIndex the index of the first element (inclusive) to be
2072 * filled with the specified value
2073 * @param toIndex the index of the last element (exclusive) to be
2074 * filled with the specified value
2075 * @param val the value to be stored in all elements of the array
2076 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2077 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2078 * <tt>toIndex > a.length</tt>
2080 public static void fill(boolean[] a, int fromIndex, int toIndex,
2082 rangeCheck(a.length, fromIndex, toIndex);
2083 for (int i = fromIndex; i < toIndex; i++)
2088 * Assigns the specified double value to each element of the specified
2091 * @param a the array to be filled
2092 * @param val the value to be stored in all elements of the array
2094 public static void fill(double[] a, double val) {
2095 for (int i = 0, len = a.length; i < len; i++)
2100 * Assigns the specified double value to each element of the specified
2101 * range of the specified array of doubles. The range to be filled
2102 * extends from index <tt>fromIndex</tt>, inclusive, to index
2103 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2104 * range to be filled is empty.)
2106 * @param a the array to be filled
2107 * @param fromIndex the index of the first element (inclusive) to be
2108 * filled with the specified value
2109 * @param toIndex the index of the last element (exclusive) to be
2110 * filled with the specified value
2111 * @param val the value to be stored in all elements of the array
2112 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2113 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2114 * <tt>toIndex > a.length</tt>
2116 public static void fill(double[] a, int fromIndex, int toIndex,double val){
2117 rangeCheck(a.length, fromIndex, toIndex);
2118 for (int i = fromIndex; i < toIndex; i++)
2123 * Assigns the specified float value to each element of the specified array
2126 * @param a the array to be filled
2127 * @param val the value to be stored in all elements of the array
2129 public static void fill(float[] a, float val) {
2130 for (int i = 0, len = a.length; i < len; i++)
2135 * Assigns the specified float value to each element of the specified
2136 * range of the specified array of floats. The range to be filled
2137 * extends from index <tt>fromIndex</tt>, inclusive, to index
2138 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2139 * range to be filled is empty.)
2141 * @param a the array to be filled
2142 * @param fromIndex the index of the first element (inclusive) to be
2143 * filled with the specified value
2144 * @param toIndex the index of the last element (exclusive) to be
2145 * filled with the specified value
2146 * @param val the value to be stored in all elements of the array
2147 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2148 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2149 * <tt>toIndex > a.length</tt>
2151 public static void fill(float[] a, int fromIndex, int toIndex, float val) {
2152 rangeCheck(a.length, fromIndex, toIndex);
2153 for (int i = fromIndex; i < toIndex; i++)
2158 * Assigns the specified Object reference to each element of the specified
2161 * @param a the array to be filled
2162 * @param val the value to be stored in all elements of the array
2163 * @throws ArrayStoreException if the specified value is not of a
2164 * runtime type that can be stored in the specified array
2166 public static void fill(Object[] a, Object val) {
2167 for (int i = 0, len = a.length; i < len; i++)
2172 * Assigns the specified Object reference to each element of the specified
2173 * range of the specified array of Objects. The range to be filled
2174 * extends from index <tt>fromIndex</tt>, inclusive, to index
2175 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2176 * range to be filled is empty.)
2178 * @param a the array to be filled
2179 * @param fromIndex the index of the first element (inclusive) to be
2180 * filled with the specified value
2181 * @param toIndex the index of the last element (exclusive) to be
2182 * filled with the specified value
2183 * @param val the value to be stored in all elements of the array
2184 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2185 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2186 * <tt>toIndex > a.length</tt>
2187 * @throws ArrayStoreException if the specified value is not of a
2188 * runtime type that can be stored in the specified array
2190 public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
2191 rangeCheck(a.length, fromIndex, toIndex);
2192 for (int i = fromIndex; i < toIndex; i++)
2199 * Copies the specified array, truncating or padding with nulls (if necessary)
2200 * so the copy has the specified length. For all indices that are
2201 * valid in both the original array and the copy, the two arrays will
2202 * contain identical values. For any indices that are valid in the
2203 * copy but not the original, the copy will contain <tt>null</tt>.
2204 * Such indices will exist if and only if the specified length
2205 * is greater than that of the original array.
2206 * The resulting array is of exactly the same class as the original array.
2208 * @param original the array to be copied
2209 * @param newLength the length of the copy to be returned
2210 * @return a copy of the original array, truncated or padded with nulls
2211 * to obtain the specified length
2212 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2213 * @throws NullPointerException if <tt>original</tt> is null
2216 public static <T> T[] copyOf(T[] original, int newLength) {
2217 return (T[]) copyOf(original, newLength, original.getClass());
2221 * Copies the specified array, truncating or padding with nulls (if necessary)
2222 * so the copy has the specified length. For all indices that are
2223 * valid in both the original array and the copy, the two arrays will
2224 * contain identical values. For any indices that are valid in the
2225 * copy but not the original, the copy will contain <tt>null</tt>.
2226 * Such indices will exist if and only if the specified length
2227 * is greater than that of the original array.
2228 * The resulting array is of the class <tt>newType</tt>.
2230 * @param original the array to be copied
2231 * @param newLength the length of the copy to be returned
2232 * @param newType the class of the copy to be returned
2233 * @return a copy of the original array, truncated or padded with nulls
2234 * to obtain the specified length
2235 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2236 * @throws NullPointerException if <tt>original</tt> is null
2237 * @throws ArrayStoreException if an element copied from
2238 * <tt>original</tt> is not of a runtime type that can be stored in
2239 * an array of class <tt>newType</tt>
2242 public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
2243 T[] copy = ((Object)newType == (Object)Object[].class)
2244 ? (T[]) new Object[newLength]
2245 : (T[]) Array.newInstance(newType.getComponentType(), newLength);
2246 System.arraycopy(original, 0, copy, 0,
2247 Math.min(original.length, newLength));
2252 * Copies the specified array, truncating or padding with zeros (if necessary)
2253 * so the copy has the specified length. For all indices that are
2254 * valid in both the original array and the copy, the two arrays will
2255 * contain identical values. For any indices that are valid in the
2256 * copy but not the original, the copy will contain <tt>(byte)0</tt>.
2257 * Such indices will exist if and only if the specified length
2258 * is greater than that of the original array.
2260 * @param original the array to be copied
2261 * @param newLength the length of the copy to be returned
2262 * @return a copy of the original array, truncated or padded with zeros
2263 * to obtain the specified length
2264 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2265 * @throws NullPointerException if <tt>original</tt> is null
2268 public static byte[] copyOf(byte[] original, int newLength) {
2269 byte[] copy = new byte[newLength];
2270 System.arraycopy(original, 0, copy, 0,
2271 Math.min(original.length, newLength));
2276 * Copies the specified array, truncating or padding with zeros (if necessary)
2277 * so the copy has the specified length. For all indices that are
2278 * valid in both the original array and the copy, the two arrays will
2279 * contain identical values. For any indices that are valid in the
2280 * copy but not the original, the copy will contain <tt>(short)0</tt>.
2281 * Such indices will exist if and only if the specified length
2282 * is greater than that of the original array.
2284 * @param original the array to be copied
2285 * @param newLength the length of the copy to be returned
2286 * @return a copy of the original array, truncated or padded with zeros
2287 * to obtain the specified length
2288 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2289 * @throws NullPointerException if <tt>original</tt> is null
2292 public static short[] copyOf(short[] original, int newLength) {
2293 short[] copy = new short[newLength];
2294 System.arraycopy(original, 0, copy, 0,
2295 Math.min(original.length, newLength));
2300 * Copies the specified array, truncating or padding with zeros (if necessary)
2301 * so the copy has the specified length. For all indices that are
2302 * valid in both the original array and the copy, the two arrays will
2303 * contain identical values. For any indices that are valid in the
2304 * copy but not the original, the copy will contain <tt>0</tt>.
2305 * Such indices will exist if and only if the specified length
2306 * is greater than that of the original array.
2308 * @param original the array to be copied
2309 * @param newLength the length of the copy to be returned
2310 * @return a copy of the original array, truncated or padded with zeros
2311 * to obtain the specified length
2312 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2313 * @throws NullPointerException if <tt>original</tt> is null
2316 public static int[] copyOf(int[] original, int newLength) {
2317 int[] copy = new int[newLength];
2318 System.arraycopy(original, 0, copy, 0,
2319 Math.min(original.length, newLength));
2324 * Copies the specified array, truncating or padding with zeros (if necessary)
2325 * so the copy has the specified length. For all indices that are
2326 * valid in both the original array and the copy, the two arrays will
2327 * contain identical values. For any indices that are valid in the
2328 * copy but not the original, the copy will contain <tt>0L</tt>.
2329 * Such indices will exist if and only if the specified length
2330 * is greater than that of the original array.
2332 * @param original the array to be copied
2333 * @param newLength the length of the copy to be returned
2334 * @return a copy of the original array, truncated or padded with zeros
2335 * to obtain the specified length
2336 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2337 * @throws NullPointerException if <tt>original</tt> is null
2340 public static long[] copyOf(long[] original, int newLength) {
2341 long[] copy = new long[newLength];
2342 System.arraycopy(original, 0, copy, 0,
2343 Math.min(original.length, newLength));
2348 * Copies the specified array, truncating or padding with null characters (if necessary)
2349 * so the copy has the specified length. For all indices that are valid
2350 * in both the original array and the copy, the two arrays will contain
2351 * identical values. For any indices that are valid in the copy but not
2352 * the original, the copy will contain <tt>'\\u000'</tt>. Such indices
2353 * will exist if and only if the specified length is greater than that of
2354 * the original array.
2356 * @param original the array to be copied
2357 * @param newLength the length of the copy to be returned
2358 * @return a copy of the original array, truncated or padded with null characters
2359 * to obtain the specified length
2360 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2361 * @throws NullPointerException if <tt>original</tt> is null
2364 public static char[] copyOf(char[] original, int newLength) {
2365 char[] copy = new char[newLength];
2366 System.arraycopy(original, 0, copy, 0,
2367 Math.min(original.length, newLength));
2372 * Copies the specified array, truncating or padding with zeros (if necessary)
2373 * so the copy has the specified length. For all indices that are
2374 * valid in both the original array and the copy, the two arrays will
2375 * contain identical values. For any indices that are valid in the
2376 * copy but not the original, the copy will contain <tt>0f</tt>.
2377 * Such indices will exist if and only if the specified length
2378 * is greater than that of the original array.
2380 * @param original the array to be copied
2381 * @param newLength the length of the copy to be returned
2382 * @return a copy of the original array, truncated or padded with zeros
2383 * to obtain the specified length
2384 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2385 * @throws NullPointerException if <tt>original</tt> is null
2388 public static float[] copyOf(float[] original, int newLength) {
2389 float[] copy = new float[newLength];
2390 System.arraycopy(original, 0, copy, 0,
2391 Math.min(original.length, newLength));
2396 * Copies the specified array, truncating or padding with zeros (if necessary)
2397 * so the copy has the specified length. For all indices that are
2398 * valid in both the original array and the copy, the two arrays will
2399 * contain identical values. For any indices that are valid in the
2400 * copy but not the original, the copy will contain <tt>0d</tt>.
2401 * Such indices will exist if and only if the specified length
2402 * is greater than that of the original array.
2404 * @param original the array to be copied
2405 * @param newLength the length of the copy to be returned
2406 * @return a copy of the original array, truncated or padded with zeros
2407 * to obtain the specified length
2408 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2409 * @throws NullPointerException if <tt>original</tt> is null
2412 public static double[] copyOf(double[] original, int newLength) {
2413 double[] copy = new double[newLength];
2414 System.arraycopy(original, 0, copy, 0,
2415 Math.min(original.length, newLength));
2420 * Copies the specified array, truncating or padding with <tt>false</tt> (if necessary)
2421 * so the copy has the specified length. For all indices that are
2422 * valid in both the original array and the copy, the two arrays will
2423 * contain identical values. For any indices that are valid in the
2424 * copy but not the original, the copy will contain <tt>false</tt>.
2425 * Such indices will exist if and only if the specified length
2426 * is greater than that of the original array.
2428 * @param original the array to be copied
2429 * @param newLength the length of the copy to be returned
2430 * @return a copy of the original array, truncated or padded with false elements
2431 * to obtain the specified length
2432 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2433 * @throws NullPointerException if <tt>original</tt> is null
2436 public static boolean[] copyOf(boolean[] original, int newLength) {
2437 boolean[] copy = new boolean[newLength];
2438 System.arraycopy(original, 0, copy, 0,
2439 Math.min(original.length, newLength));
2444 * Copies the specified range of the specified array into a new array.
2445 * The initial index of the range (<tt>from</tt>) must lie between zero
2446 * and <tt>original.length</tt>, inclusive. The value at
2447 * <tt>original[from]</tt> is placed into the initial element of the copy
2448 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2449 * Values from subsequent elements in the original array are placed into
2450 * subsequent elements in the copy. The final index of the range
2451 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2452 * may be greater than <tt>original.length</tt>, in which case
2453 * <tt>null</tt> is placed in all elements of the copy whose index is
2454 * greater than or equal to <tt>original.length - from</tt>. The length
2455 * of the returned array will be <tt>to - from</tt>.
2457 * The resulting array is of exactly the same class as the original array.
2459 * @param original the array from which a range is to be copied
2460 * @param from the initial index of the range to be copied, inclusive
2461 * @param to the final index of the range to be copied, exclusive.
2462 * (This index may lie outside the array.)
2463 * @return a new array containing the specified range from the original array,
2464 * truncated or padded with nulls to obtain the required length
2465 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2466 * or {@code from > original.length}
2467 * @throws IllegalArgumentException if <tt>from > to</tt>
2468 * @throws NullPointerException if <tt>original</tt> is null
2471 public static <T> T[] copyOfRange(T[] original, int from, int to) {
2472 return copyOfRange(original, from, to, (Class<T[]>) original.getClass());
2476 * Copies the specified range of the specified array into a new array.
2477 * The initial index of the range (<tt>from</tt>) must lie between zero
2478 * and <tt>original.length</tt>, inclusive. The value at
2479 * <tt>original[from]</tt> is placed into the initial element of the copy
2480 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2481 * Values from subsequent elements in the original array are placed into
2482 * subsequent elements in the copy. The final index of the range
2483 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2484 * may be greater than <tt>original.length</tt>, in which case
2485 * <tt>null</tt> is placed in all elements of the copy whose index is
2486 * greater than or equal to <tt>original.length - from</tt>. The length
2487 * of the returned array will be <tt>to - from</tt>.
2488 * The resulting array is of the class <tt>newType</tt>.
2490 * @param original the array from which a range is to be copied
2491 * @param from the initial index of the range to be copied, inclusive
2492 * @param to the final index of the range to be copied, exclusive.
2493 * (This index may lie outside the array.)
2494 * @param newType the class of the copy to be returned
2495 * @return a new array containing the specified range from the original array,
2496 * truncated or padded with nulls to obtain the required length
2497 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2498 * or {@code from > original.length}
2499 * @throws IllegalArgumentException if <tt>from > to</tt>
2500 * @throws NullPointerException if <tt>original</tt> is null
2501 * @throws ArrayStoreException if an element copied from
2502 * <tt>original</tt> is not of a runtime type that can be stored in
2503 * an array of class <tt>newType</tt>.
2506 public static <T,U> T[] copyOfRange(U[] original, int from, int to, Class<? extends T[]> newType) {
2507 int newLength = to - from;
2509 throw new IllegalArgumentException(from + " > " + to);
2510 T[] copy = ((Object)newType == (Object)Object[].class)
2511 ? (T[]) new Object[newLength]
2512 : (T[]) Array.newInstance(newType.getComponentType(), newLength);
2513 System.arraycopy(original, from, copy, 0,
2514 Math.min(original.length - from, newLength));
2519 * Copies the specified range of the specified array into a new array.
2520 * The initial index of the range (<tt>from</tt>) must lie between zero
2521 * and <tt>original.length</tt>, inclusive. The value at
2522 * <tt>original[from]</tt> is placed into the initial element of the copy
2523 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2524 * Values from subsequent elements in the original array are placed into
2525 * subsequent elements in the copy. The final index of the range
2526 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2527 * may be greater than <tt>original.length</tt>, in which case
2528 * <tt>(byte)0</tt> is placed in all elements of the copy whose index is
2529 * greater than or equal to <tt>original.length - from</tt>. The length
2530 * of the returned array will be <tt>to - from</tt>.
2532 * @param original the array from which a range is to be copied
2533 * @param from the initial index of the range to be copied, inclusive
2534 * @param to the final index of the range to be copied, exclusive.
2535 * (This index may lie outside the array.)
2536 * @return a new array containing the specified range from the original array,
2537 * truncated or padded with zeros to obtain the required length
2538 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2539 * or {@code from > original.length}
2540 * @throws IllegalArgumentException if <tt>from > to</tt>
2541 * @throws NullPointerException if <tt>original</tt> is null
2544 public static byte[] copyOfRange(byte[] original, int from, int to) {
2545 int newLength = to - from;
2547 throw new IllegalArgumentException(from + " > " + to);
2548 byte[] copy = new byte[newLength];
2549 System.arraycopy(original, from, copy, 0,
2550 Math.min(original.length - from, newLength));
2555 * Copies the specified range of the specified array into a new array.
2556 * The initial index of the range (<tt>from</tt>) must lie between zero
2557 * and <tt>original.length</tt>, inclusive. The value at
2558 * <tt>original[from]</tt> is placed into the initial element of the copy
2559 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2560 * Values from subsequent elements in the original array are placed into
2561 * subsequent elements in the copy. The final index of the range
2562 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2563 * may be greater than <tt>original.length</tt>, in which case
2564 * <tt>(short)0</tt> is placed in all elements of the copy whose index is
2565 * greater than or equal to <tt>original.length - from</tt>. The length
2566 * of the returned array will be <tt>to - from</tt>.
2568 * @param original the array from which a range is to be copied
2569 * @param from the initial index of the range to be copied, inclusive
2570 * @param to the final index of the range to be copied, exclusive.
2571 * (This index may lie outside the array.)
2572 * @return a new array containing the specified range from the original array,
2573 * truncated or padded with zeros to obtain the required length
2574 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2575 * or {@code from > original.length}
2576 * @throws IllegalArgumentException if <tt>from > to</tt>
2577 * @throws NullPointerException if <tt>original</tt> is null
2580 public static short[] copyOfRange(short[] original, int from, int to) {
2581 int newLength = to - from;
2583 throw new IllegalArgumentException(from + " > " + to);
2584 short[] copy = new short[newLength];
2585 System.arraycopy(original, from, copy, 0,
2586 Math.min(original.length - from, newLength));
2591 * Copies the specified range of the specified array into a new array.
2592 * The initial index of the range (<tt>from</tt>) must lie between zero
2593 * and <tt>original.length</tt>, inclusive. The value at
2594 * <tt>original[from]</tt> is placed into the initial element of the copy
2595 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2596 * Values from subsequent elements in the original array are placed into
2597 * subsequent elements in the copy. The final index of the range
2598 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2599 * may be greater than <tt>original.length</tt>, in which case
2600 * <tt>0</tt> is placed in all elements of the copy whose index is
2601 * greater than or equal to <tt>original.length - from</tt>. The length
2602 * of the returned array will be <tt>to - from</tt>.
2604 * @param original the array from which a range is to be copied
2605 * @param from the initial index of the range to be copied, inclusive
2606 * @param to the final index of the range to be copied, exclusive.
2607 * (This index may lie outside the array.)
2608 * @return a new array containing the specified range from the original array,
2609 * truncated or padded with zeros to obtain the required length
2610 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2611 * or {@code from > original.length}
2612 * @throws IllegalArgumentException if <tt>from > to</tt>
2613 * @throws NullPointerException if <tt>original</tt> is null
2616 public static int[] copyOfRange(int[] original, int from, int to) {
2617 int newLength = to - from;
2619 throw new IllegalArgumentException(from + " > " + to);
2620 int[] copy = new int[newLength];
2621 System.arraycopy(original, from, copy, 0,
2622 Math.min(original.length - from, newLength));
2627 * Copies the specified range of the specified array into a new array.
2628 * The initial index of the range (<tt>from</tt>) must lie between zero
2629 * and <tt>original.length</tt>, inclusive. The value at
2630 * <tt>original[from]</tt> is placed into the initial element of the copy
2631 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2632 * Values from subsequent elements in the original array are placed into
2633 * subsequent elements in the copy. The final index of the range
2634 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2635 * may be greater than <tt>original.length</tt>, in which case
2636 * <tt>0L</tt> is placed in all elements of the copy whose index is
2637 * greater than or equal to <tt>original.length - from</tt>. The length
2638 * of the returned array will be <tt>to - from</tt>.
2640 * @param original the array from which a range is to be copied
2641 * @param from the initial index of the range to be copied, inclusive
2642 * @param to the final index of the range to be copied, exclusive.
2643 * (This index may lie outside the array.)
2644 * @return a new array containing the specified range from the original array,
2645 * truncated or padded with zeros to obtain the required length
2646 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2647 * or {@code from > original.length}
2648 * @throws IllegalArgumentException if <tt>from > to</tt>
2649 * @throws NullPointerException if <tt>original</tt> is null
2652 public static long[] copyOfRange(long[] original, int from, int to) {
2653 int newLength = to - from;
2655 throw new IllegalArgumentException(from + " > " + to);
2656 long[] copy = new long[newLength];
2657 System.arraycopy(original, from, copy, 0,
2658 Math.min(original.length - from, newLength));
2663 * Copies the specified range of the specified array into a new array.
2664 * The initial index of the range (<tt>from</tt>) must lie between zero
2665 * and <tt>original.length</tt>, inclusive. The value at
2666 * <tt>original[from]</tt> is placed into the initial element of the copy
2667 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2668 * Values from subsequent elements in the original array are placed into
2669 * subsequent elements in the copy. The final index of the range
2670 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2671 * may be greater than <tt>original.length</tt>, in which case
2672 * <tt>'\\u000'</tt> is placed in all elements of the copy whose index is
2673 * greater than or equal to <tt>original.length - from</tt>. The length
2674 * of the returned array will be <tt>to - from</tt>.
2676 * @param original the array from which a range is to be copied
2677 * @param from the initial index of the range to be copied, inclusive
2678 * @param to the final index of the range to be copied, exclusive.
2679 * (This index may lie outside the array.)
2680 * @return a new array containing the specified range from the original array,
2681 * truncated or padded with null characters to obtain the required length
2682 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2683 * or {@code from > original.length}
2684 * @throws IllegalArgumentException if <tt>from > to</tt>
2685 * @throws NullPointerException if <tt>original</tt> is null
2688 public static char[] copyOfRange(char[] original, int from, int to) {
2689 int newLength = to - from;
2691 throw new IllegalArgumentException(from + " > " + to);
2692 char[] copy = new char[newLength];
2693 System.arraycopy(original, from, copy, 0,
2694 Math.min(original.length - from, newLength));
2699 * Copies the specified range of the specified array into a new array.
2700 * The initial index of the range (<tt>from</tt>) must lie between zero
2701 * and <tt>original.length</tt>, inclusive. The value at
2702 * <tt>original[from]</tt> is placed into the initial element of the copy
2703 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2704 * Values from subsequent elements in the original array are placed into
2705 * subsequent elements in the copy. The final index of the range
2706 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2707 * may be greater than <tt>original.length</tt>, in which case
2708 * <tt>0f</tt> is placed in all elements of the copy whose index is
2709 * greater than or equal to <tt>original.length - from</tt>. The length
2710 * of the returned array will be <tt>to - from</tt>.
2712 * @param original the array from which a range is to be copied
2713 * @param from the initial index of the range to be copied, inclusive
2714 * @param to the final index of the range to be copied, exclusive.
2715 * (This index may lie outside the array.)
2716 * @return a new array containing the specified range from the original array,
2717 * truncated or padded with zeros to obtain the required length
2718 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2719 * or {@code from > original.length}
2720 * @throws IllegalArgumentException if <tt>from > to</tt>
2721 * @throws NullPointerException if <tt>original</tt> is null
2724 public static float[] copyOfRange(float[] original, int from, int to) {
2725 int newLength = to - from;
2727 throw new IllegalArgumentException(from + " > " + to);
2728 float[] copy = new float[newLength];
2729 System.arraycopy(original, from, copy, 0,
2730 Math.min(original.length - from, newLength));
2735 * Copies the specified range of the specified array into a new array.
2736 * The initial index of the range (<tt>from</tt>) must lie between zero
2737 * and <tt>original.length</tt>, inclusive. The value at
2738 * <tt>original[from]</tt> is placed into the initial element of the copy
2739 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2740 * Values from subsequent elements in the original array are placed into
2741 * subsequent elements in the copy. The final index of the range
2742 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2743 * may be greater than <tt>original.length</tt>, in which case
2744 * <tt>0d</tt> is placed in all elements of the copy whose index is
2745 * greater than or equal to <tt>original.length - from</tt>. The length
2746 * of the returned array will be <tt>to - from</tt>.
2748 * @param original the array from which a range is to be copied
2749 * @param from the initial index of the range to be copied, inclusive
2750 * @param to the final index of the range to be copied, exclusive.
2751 * (This index may lie outside the array.)
2752 * @return a new array containing the specified range from the original array,
2753 * truncated or padded with zeros to obtain the required length
2754 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2755 * or {@code from > original.length}
2756 * @throws IllegalArgumentException if <tt>from > to</tt>
2757 * @throws NullPointerException if <tt>original</tt> is null
2760 public static double[] copyOfRange(double[] original, int from, int to) {
2761 int newLength = to - from;
2763 throw new IllegalArgumentException(from + " > " + to);
2764 double[] copy = new double[newLength];
2765 System.arraycopy(original, from, copy, 0,
2766 Math.min(original.length - from, newLength));
2771 * Copies the specified range of the specified array into a new array.
2772 * The initial index of the range (<tt>from</tt>) must lie between zero
2773 * and <tt>original.length</tt>, inclusive. The value at
2774 * <tt>original[from]</tt> is placed into the initial element of the copy
2775 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2776 * Values from subsequent elements in the original array are placed into
2777 * subsequent elements in the copy. The final index of the range
2778 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2779 * may be greater than <tt>original.length</tt>, in which case
2780 * <tt>false</tt> is placed in all elements of the copy whose index is
2781 * greater than or equal to <tt>original.length - from</tt>. The length
2782 * of the returned array will be <tt>to - from</tt>.
2784 * @param original the array from which a range is to be copied
2785 * @param from the initial index of the range to be copied, inclusive
2786 * @param to the final index of the range to be copied, exclusive.
2787 * (This index may lie outside the array.)
2788 * @return a new array containing the specified range from the original array,
2789 * truncated or padded with false elements to obtain the required length
2790 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
2791 * or {@code from > original.length}
2792 * @throws IllegalArgumentException if <tt>from > to</tt>
2793 * @throws NullPointerException if <tt>original</tt> is null
2796 public static boolean[] copyOfRange(boolean[] original, int from, int to) {
2797 int newLength = to - from;
2799 throw new IllegalArgumentException(from + " > " + to);
2800 boolean[] copy = new boolean[newLength];
2801 System.arraycopy(original, from, copy, 0,
2802 Math.min(original.length - from, newLength));
2809 * Returns a fixed-size list backed by the specified array. (Changes to
2810 * the returned list "write through" to the array.) This method acts
2811 * as bridge between array-based and collection-based APIs, in
2812 * combination with {@link Collection#toArray}. The returned list is
2813 * serializable and implements {@link RandomAccess}.
2815 * <p>This method also provides a convenient way to create a fixed-size
2816 * list initialized to contain several elements:
2818 * List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
2821 * @param a the array by which the list will be backed
2822 * @return a list view of the specified array
2825 public static <T> List<T> asList(T... a) {
2826 return new ArrayList<>(a);
2832 private static class ArrayList<E> extends AbstractList<E>
2833 implements RandomAccess, java.io.Serializable
2835 private static final long serialVersionUID = -2764017481108945198L;
2836 private final E[] a;
2838 ArrayList(E[] array) {
2840 throw new NullPointerException();
2848 public Object[] toArray() {
2852 public <T> T[] toArray(T[] a) {
2854 if (a.length < size)
2855 return Arrays.copyOf(this.a, size,
2856 (Class<? extends T[]>) a.getClass());
2857 System.arraycopy(this.a, 0, a, 0, size);
2858 if (a.length > size)
2863 public E get(int index) {
2867 public E set(int index, E element) {
2868 E oldValue = a[index];
2873 public int indexOf(Object o) {
2875 for (int i=0; i<a.length; i++)
2879 for (int i=0; i<a.length; i++)
2886 public boolean contains(Object o) {
2887 return indexOf(o) != -1;
2892 * Returns a hash code based on the contents of the specified array.
2893 * For any two <tt>long</tt> arrays <tt>a</tt> and <tt>b</tt>
2894 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
2895 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
2897 * <p>The value returned by this method is the same value that would be
2898 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
2899 * method on a {@link List} containing a sequence of {@link Long}
2900 * instances representing the elements of <tt>a</tt> in the same order.
2901 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
2903 * @param a the array whose hash value to compute
2904 * @return a content-based hash code for <tt>a</tt>
2907 public static int hashCode(long a[]) {
2912 for (long element : a) {
2913 int elementHash = (int)(element ^ (element >>> 32));
2914 result = 31 * result + elementHash;
2921 * Returns a hash code based on the contents of the specified array.
2922 * For any two non-null <tt>int</tt> arrays <tt>a</tt> and <tt>b</tt>
2923 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
2924 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
2926 * <p>The value returned by this method is the same value that would be
2927 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
2928 * method on a {@link List} containing a sequence of {@link Integer}
2929 * instances representing the elements of <tt>a</tt> in the same order.
2930 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
2932 * @param a the array whose hash value to compute
2933 * @return a content-based hash code for <tt>a</tt>
2936 public static int hashCode(int a[]) {
2941 for (int element : a)
2942 result = 31 * result + element;
2948 * Returns a hash code based on the contents of the specified array.
2949 * For any two <tt>short</tt> arrays <tt>a</tt> and <tt>b</tt>
2950 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
2951 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
2953 * <p>The value returned by this method is the same value that would be
2954 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
2955 * method on a {@link List} containing a sequence of {@link Short}
2956 * instances representing the elements of <tt>a</tt> in the same order.
2957 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
2959 * @param a the array whose hash value to compute
2960 * @return a content-based hash code for <tt>a</tt>
2963 public static int hashCode(short a[]) {
2968 for (short element : a)
2969 result = 31 * result + element;
2975 * Returns a hash code based on the contents of the specified array.
2976 * For any two <tt>char</tt> arrays <tt>a</tt> and <tt>b</tt>
2977 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
2978 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
2980 * <p>The value returned by this method is the same value that would be
2981 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
2982 * method on a {@link List} containing a sequence of {@link Character}
2983 * instances representing the elements of <tt>a</tt> in the same order.
2984 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
2986 * @param a the array whose hash value to compute
2987 * @return a content-based hash code for <tt>a</tt>
2990 public static int hashCode(char a[]) {
2995 for (char element : a)
2996 result = 31 * result + element;
3002 * Returns a hash code based on the contents of the specified array.
3003 * For any two <tt>byte</tt> arrays <tt>a</tt> and <tt>b</tt>
3004 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3005 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3007 * <p>The value returned by this method is the same value that would be
3008 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3009 * method on a {@link List} containing a sequence of {@link Byte}
3010 * instances representing the elements of <tt>a</tt> in the same order.
3011 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3013 * @param a the array whose hash value to compute
3014 * @return a content-based hash code for <tt>a</tt>
3017 public static int hashCode(byte a[]) {
3022 for (byte element : a)
3023 result = 31 * result + element;
3029 * Returns a hash code based on the contents of the specified array.
3030 * For any two <tt>boolean</tt> arrays <tt>a</tt> and <tt>b</tt>
3031 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3032 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3034 * <p>The value returned by this method is the same value that would be
3035 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3036 * method on a {@link List} containing a sequence of {@link Boolean}
3037 * instances representing the elements of <tt>a</tt> in the same order.
3038 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3040 * @param a the array whose hash value to compute
3041 * @return a content-based hash code for <tt>a</tt>
3044 public static int hashCode(boolean a[]) {
3049 for (boolean element : a)
3050 result = 31 * result + (element ? 1231 : 1237);
3056 * Returns a hash code based on the contents of the specified array.
3057 * For any two <tt>float</tt> arrays <tt>a</tt> and <tt>b</tt>
3058 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3059 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3061 * <p>The value returned by this method is the same value that would be
3062 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3063 * method on a {@link List} containing a sequence of {@link Float}
3064 * instances representing the elements of <tt>a</tt> in the same order.
3065 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3067 * @param a the array whose hash value to compute
3068 * @return a content-based hash code for <tt>a</tt>
3071 public static int hashCode(float a[]) {
3076 for (float element : a)
3077 result = 31 * result + Float.floatToIntBits(element);
3083 * Returns a hash code based on the contents of the specified array.
3084 * For any two <tt>double</tt> arrays <tt>a</tt> and <tt>b</tt>
3085 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3086 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3088 * <p>The value returned by this method is the same value that would be
3089 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3090 * method on a {@link List} containing a sequence of {@link Double}
3091 * instances representing the elements of <tt>a</tt> in the same order.
3092 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3094 * @param a the array whose hash value to compute
3095 * @return a content-based hash code for <tt>a</tt>
3098 public static int hashCode(double a[]) {
3103 for (double element : a) {
3104 long bits = Double.doubleToLongBits(element);
3105 result = 31 * result + (int)(bits ^ (bits >>> 32));
3111 * Returns a hash code based on the contents of the specified array. If
3112 * the array contains other arrays as elements, the hash code is based on
3113 * their identities rather than their contents. It is therefore
3114 * acceptable to invoke this method on an array that contains itself as an
3115 * element, either directly or indirectly through one or more levels of
3118 * <p>For any two arrays <tt>a</tt> and <tt>b</tt> such that
3119 * <tt>Arrays.equals(a, b)</tt>, it is also the case that
3120 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3122 * <p>The value returned by this method is equal to the value that would
3123 * be returned by <tt>Arrays.asList(a).hashCode()</tt>, unless <tt>a</tt>
3124 * is <tt>null</tt>, in which case <tt>0</tt> is returned.
3126 * @param a the array whose content-based hash code to compute
3127 * @return a content-based hash code for <tt>a</tt>
3128 * @see #deepHashCode(Object[])
3131 public static int hashCode(Object a[]) {
3137 for (Object element : a)
3138 result = 31 * result + (element == null ? 0 : element.hashCode());
3144 * Returns a hash code based on the "deep contents" of the specified
3145 * array. If the array contains other arrays as elements, the
3146 * hash code is based on their contents and so on, ad infinitum.
3147 * It is therefore unacceptable to invoke this method on an array that
3148 * contains itself as an element, either directly or indirectly through
3149 * one or more levels of arrays. The behavior of such an invocation is
3152 * <p>For any two arrays <tt>a</tt> and <tt>b</tt> such that
3153 * <tt>Arrays.deepEquals(a, b)</tt>, it is also the case that
3154 * <tt>Arrays.deepHashCode(a) == Arrays.deepHashCode(b)</tt>.
3156 * <p>The computation of the value returned by this method is similar to
3157 * that of the value returned by {@link List#hashCode()} on a list
3158 * containing the same elements as <tt>a</tt> in the same order, with one
3159 * difference: If an element <tt>e</tt> of <tt>a</tt> is itself an array,
3160 * its hash code is computed not by calling <tt>e.hashCode()</tt>, but as
3161 * by calling the appropriate overloading of <tt>Arrays.hashCode(e)</tt>
3162 * if <tt>e</tt> is an array of a primitive type, or as by calling
3163 * <tt>Arrays.deepHashCode(e)</tt> recursively if <tt>e</tt> is an array
3164 * of a reference type. If <tt>a</tt> is <tt>null</tt>, this method
3167 * @param a the array whose deep-content-based hash code to compute
3168 * @return a deep-content-based hash code for <tt>a</tt>
3169 * @see #hashCode(Object[])
3172 public static int deepHashCode(Object a[]) {
3178 for (Object element : a) {
3179 int elementHash = 0;
3180 if (element instanceof Object[])
3181 elementHash = deepHashCode((Object[]) element);
3182 else if (element instanceof byte[])
3183 elementHash = hashCode((byte[]) element);
3184 else if (element instanceof short[])
3185 elementHash = hashCode((short[]) element);
3186 else if (element instanceof int[])
3187 elementHash = hashCode((int[]) element);
3188 else if (element instanceof long[])
3189 elementHash = hashCode((long[]) element);
3190 else if (element instanceof char[])
3191 elementHash = hashCode((char[]) element);
3192 else if (element instanceof float[])
3193 elementHash = hashCode((float[]) element);
3194 else if (element instanceof double[])
3195 elementHash = hashCode((double[]) element);
3196 else if (element instanceof boolean[])
3197 elementHash = hashCode((boolean[]) element);
3198 else if (element != null)
3199 elementHash = element.hashCode();
3201 result = 31 * result + elementHash;
3208 * Returns <tt>true</tt> if the two specified arrays are <i>deeply
3209 * equal</i> to one another. Unlike the {@link #equals(Object[],Object[])}
3210 * method, this method is appropriate for use with nested arrays of
3213 * <p>Two array references are considered deeply equal if both
3214 * are <tt>null</tt>, or if they refer to arrays that contain the same
3215 * number of elements and all corresponding pairs of elements in the two
3216 * arrays are deeply equal.
3218 * <p>Two possibly <tt>null</tt> elements <tt>e1</tt> and <tt>e2</tt> are
3219 * deeply equal if any of the following conditions hold:
3221 * <li> <tt>e1</tt> and <tt>e2</tt> are both arrays of object reference
3222 * types, and <tt>Arrays.deepEquals(e1, e2) would return true</tt>
3223 * <li> <tt>e1</tt> and <tt>e2</tt> are arrays of the same primitive
3224 * type, and the appropriate overloading of
3225 * <tt>Arrays.equals(e1, e2)</tt> would return true.
3226 * <li> <tt>e1 == e2</tt>
3227 * <li> <tt>e1.equals(e2)</tt> would return true.
3229 * Note that this definition permits <tt>null</tt> elements at any depth.
3231 * <p>If either of the specified arrays contain themselves as elements
3232 * either directly or indirectly through one or more levels of arrays,
3233 * the behavior of this method is undefined.
3235 * @param a1 one array to be tested for equality
3236 * @param a2 the other array to be tested for equality
3237 * @return <tt>true</tt> if the two arrays are equal
3238 * @see #equals(Object[],Object[])
3239 * @see Objects#deepEquals(Object, Object)
3242 public static boolean deepEquals(Object[] a1, Object[] a2) {
3245 if (a1 == null || a2==null)
3247 int length = a1.length;
3248 if (a2.length != length)
3251 for (int i = 0; i < length; i++) {
3260 // Figure out whether the two elements are equal
3261 boolean eq = deepEquals0(e1, e2);
3269 static boolean deepEquals0(Object e1, Object e2) {
3272 if (e1 instanceof Object[] && e2 instanceof Object[])
3273 eq = deepEquals ((Object[]) e1, (Object[]) e2);
3274 else if (e1 instanceof byte[] && e2 instanceof byte[])
3275 eq = equals((byte[]) e1, (byte[]) e2);
3276 else if (e1 instanceof short[] && e2 instanceof short[])
3277 eq = equals((short[]) e1, (short[]) e2);
3278 else if (e1 instanceof int[] && e2 instanceof int[])
3279 eq = equals((int[]) e1, (int[]) e2);
3280 else if (e1 instanceof long[] && e2 instanceof long[])
3281 eq = equals((long[]) e1, (long[]) e2);
3282 else if (e1 instanceof char[] && e2 instanceof char[])
3283 eq = equals((char[]) e1, (char[]) e2);
3284 else if (e1 instanceof float[] && e2 instanceof float[])
3285 eq = equals((float[]) e1, (float[]) e2);
3286 else if (e1 instanceof double[] && e2 instanceof double[])
3287 eq = equals((double[]) e1, (double[]) e2);
3288 else if (e1 instanceof boolean[] && e2 instanceof boolean[])
3289 eq = equals((boolean[]) e1, (boolean[]) e2);
3296 * Returns a string representation of the contents of the specified array.
3297 * The string representation consists of a list of the array's elements,
3298 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
3299 * separated by the characters <tt>", "</tt> (a comma followed by a
3300 * space). Elements are converted to strings as by
3301 * <tt>String.valueOf(long)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
3304 * @param a the array whose string representation to return
3305 * @return a string representation of <tt>a</tt>
3308 public static String toString(long[] a) {
3311 int iMax = a.length - 1;
3315 StringBuilder b = new StringBuilder();
3317 for (int i = 0; ; i++) {
3320 return b.append(']').toString();
3326 * Returns a string representation of the contents of the specified array.
3327 * The string representation consists of a list of the array's elements,
3328 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
3329 * separated by the characters <tt>", "</tt> (a comma followed by a
3330 * space). Elements are converted to strings as by
3331 * <tt>String.valueOf(int)</tt>. Returns <tt>"null"</tt> if <tt>a</tt> is
3334 * @param a the array whose string representation to return
3335 * @return a string representation of <tt>a</tt>
3338 public static String toString(int[] a) {
3341 int iMax = a.length - 1;
3345 StringBuilder b = new StringBuilder();
3347 for (int i = 0; ; i++) {
3350 return b.append(']').toString();
3356 * Returns a string representation of the contents of the specified array.
3357 * The string representation consists of a list of the array's elements,
3358 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
3359 * separated by the characters <tt>", "</tt> (a comma followed by a
3360 * space). Elements are converted to strings as by
3361 * <tt>String.valueOf(short)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
3364 * @param a the array whose string representation to return
3365 * @return a string representation of <tt>a</tt>
3368 public static String toString(short[] a) {
3371 int iMax = a.length - 1;
3375 StringBuilder b = new StringBuilder();
3377 for (int i = 0; ; i++) {
3380 return b.append(']').toString();
3386 * Returns a string representation of the contents of the specified array.
3387 * The string representation consists of a list of the array's elements,
3388 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
3389 * separated by the characters <tt>", "</tt> (a comma followed by a
3390 * space). Elements are converted to strings as by
3391 * <tt>String.valueOf(char)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
3394 * @param a the array whose string representation to return
3395 * @return a string representation of <tt>a</tt>
3398 public static String toString(char[] a) {
3401 int iMax = a.length - 1;
3405 StringBuilder b = new StringBuilder();
3407 for (int i = 0; ; i++) {
3410 return b.append(']').toString();
3416 * Returns a string representation of the contents of the specified array.
3417 * The string representation consists of a list of the array's elements,
3418 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements
3419 * are separated by the characters <tt>", "</tt> (a comma followed
3420 * by a space). Elements are converted to strings as by
3421 * <tt>String.valueOf(byte)</tt>. Returns <tt>"null"</tt> if
3422 * <tt>a</tt> is <tt>null</tt>.
3424 * @param a the array whose string representation to return
3425 * @return a string representation of <tt>a</tt>
3428 public static String toString(byte[] a) {
3431 int iMax = a.length - 1;
3435 StringBuilder b = new StringBuilder();
3437 for (int i = 0; ; i++) {
3440 return b.append(']').toString();
3446 * Returns a string representation of the contents of the specified array.
3447 * The string representation consists of a list of the array's elements,
3448 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
3449 * separated by the characters <tt>", "</tt> (a comma followed by a
3450 * space). Elements are converted to strings as by
3451 * <tt>String.valueOf(boolean)</tt>. Returns <tt>"null"</tt> if
3452 * <tt>a</tt> is <tt>null</tt>.
3454 * @param a the array whose string representation to return
3455 * @return a string representation of <tt>a</tt>
3458 public static String toString(boolean[] a) {
3461 int iMax = a.length - 1;
3465 StringBuilder b = new StringBuilder();
3467 for (int i = 0; ; i++) {
3470 return b.append(']').toString();
3476 * Returns a string representation of the contents of the specified array.
3477 * The string representation consists of a list of the array's elements,
3478 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
3479 * separated by the characters <tt>", "</tt> (a comma followed by a
3480 * space). Elements are converted to strings as by
3481 * <tt>String.valueOf(float)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
3484 * @param a the array whose string representation to return
3485 * @return a string representation of <tt>a</tt>
3488 public static String toString(float[] a) {
3492 int iMax = a.length - 1;
3496 StringBuilder b = new StringBuilder();
3498 for (int i = 0; ; i++) {
3501 return b.append(']').toString();
3507 * Returns a string representation of the contents of the specified array.
3508 * The string representation consists of a list of the array's elements,
3509 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
3510 * separated by the characters <tt>", "</tt> (a comma followed by a
3511 * space). Elements are converted to strings as by
3512 * <tt>String.valueOf(double)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
3515 * @param a the array whose string representation to return
3516 * @return a string representation of <tt>a</tt>
3519 public static String toString(double[] a) {
3522 int iMax = a.length - 1;
3526 StringBuilder b = new StringBuilder();
3528 for (int i = 0; ; i++) {
3531 return b.append(']').toString();
3537 * Returns a string representation of the contents of the specified array.
3538 * If the array contains other arrays as elements, they are converted to
3539 * strings by the {@link Object#toString} method inherited from
3540 * <tt>Object</tt>, which describes their <i>identities</i> rather than
3543 * <p>The value returned by this method is equal to the value that would
3544 * be returned by <tt>Arrays.asList(a).toString()</tt>, unless <tt>a</tt>
3545 * is <tt>null</tt>, in which case <tt>"null"</tt> is returned.
3547 * @param a the array whose string representation to return
3548 * @return a string representation of <tt>a</tt>
3549 * @see #deepToString(Object[])
3552 public static String toString(Object[] a) {
3556 int iMax = a.length - 1;
3560 StringBuilder b = new StringBuilder();
3562 for (int i = 0; ; i++) {
3563 b.append(String.valueOf(a[i]));
3565 return b.append(']').toString();
3571 * Returns a string representation of the "deep contents" of the specified
3572 * array. If the array contains other arrays as elements, the string
3573 * representation contains their contents and so on. This method is
3574 * designed for converting multidimensional arrays to strings.
3576 * <p>The string representation consists of a list of the array's
3577 * elements, enclosed in square brackets (<tt>"[]"</tt>). Adjacent
3578 * elements are separated by the characters <tt>", "</tt> (a comma
3579 * followed by a space). Elements are converted to strings as by
3580 * <tt>String.valueOf(Object)</tt>, unless they are themselves
3583 * <p>If an element <tt>e</tt> is an array of a primitive type, it is
3584 * converted to a string as by invoking the appropriate overloading of
3585 * <tt>Arrays.toString(e)</tt>. If an element <tt>e</tt> is an array of a
3586 * reference type, it is converted to a string as by invoking
3587 * this method recursively.
3589 * <p>To avoid infinite recursion, if the specified array contains itself
3590 * as an element, or contains an indirect reference to itself through one
3591 * or more levels of arrays, the self-reference is converted to the string
3592 * <tt>"[...]"</tt>. For example, an array containing only a reference
3593 * to itself would be rendered as <tt>"[[...]]"</tt>.
3595 * <p>This method returns <tt>"null"</tt> if the specified array
3598 * @param a the array whose string representation to return
3599 * @return a string representation of <tt>a</tt>
3600 * @see #toString(Object[])
3603 public static String deepToString(Object[] a) {
3607 int bufLen = 20 * a.length;
3608 if (a.length != 0 && bufLen <= 0)
3609 bufLen = Integer.MAX_VALUE;
3610 StringBuilder buf = new StringBuilder(bufLen);
3611 deepToString(a, buf, new HashSet<Object[]>());
3612 return buf.toString();
3615 private static void deepToString(Object[] a, StringBuilder buf,
3616 Set<Object[]> dejaVu) {
3621 int iMax = a.length - 1;
3629 for (int i = 0; ; i++) {
3631 Object element = a[i];
3632 if (element == null) {
3635 Class eClass = element.getClass();
3637 if (eClass.isArray()) {
3638 if (eClass == byte[].class)
3639 buf.append(toString((byte[]) element));
3640 else if (eClass == short[].class)
3641 buf.append(toString((short[]) element));
3642 else if (eClass == int[].class)
3643 buf.append(toString((int[]) element));
3644 else if (eClass == long[].class)
3645 buf.append(toString((long[]) element));
3646 else if (eClass == char[].class)
3647 buf.append(toString((char[]) element));
3648 else if (eClass == float[].class)
3649 buf.append(toString((float[]) element));
3650 else if (eClass == double[].class)
3651 buf.append(toString((double[]) element));
3652 else if (eClass == boolean[].class)
3653 buf.append(toString((boolean[]) element));
3654 else { // element is an array of object references
3655 if (dejaVu.contains(element))
3656 buf.append("[...]");
3658 deepToString((Object[])element, buf, dejaVu);
3660 } else { // element is non-null and not an array
3661 buf.append(element.toString());