1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/compact/src/main/java/java/util/Arrays.java Tue Feb 26 16:54:16 2013 +0100
1.3 @@ -0,0 +1,3670 @@
1.4 +/*
1.5 + * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation. Oracle designates this
1.11 + * particular file as subject to the "Classpath" exception as provided
1.12 + * by Oracle in the LICENSE file that accompanied this code.
1.13 + *
1.14 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.15 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.16 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.17 + * version 2 for more details (a copy is included in the LICENSE file that
1.18 + * accompanied this code).
1.19 + *
1.20 + * You should have received a copy of the GNU General Public License version
1.21 + * 2 along with this work; if not, write to the Free Software Foundation,
1.22 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.23 + *
1.24 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.25 + * or visit www.oracle.com if you need additional information or have any
1.26 + * questions.
1.27 + */
1.28 +
1.29 +package java.util;
1.30 +
1.31 +import java.lang.reflect.*;
1.32 +
1.33 +/**
1.34 + * This class contains various methods for manipulating arrays (such as
1.35 + * sorting and searching). This class also contains a static factory
1.36 + * that allows arrays to be viewed as lists.
1.37 + *
1.38 + * <p>The methods in this class all throw a {@code NullPointerException},
1.39 + * if the specified array reference is null, except where noted.
1.40 + *
1.41 + * <p>The documentation for the methods contained in this class includes
1.42 + * briefs description of the <i>implementations</i>. Such descriptions should
1.43 + * be regarded as <i>implementation notes</i>, rather than parts of the
1.44 + * <i>specification</i>. Implementors should feel free to substitute other
1.45 + * algorithms, so long as the specification itself is adhered to. (For
1.46 + * example, the algorithm used by {@code sort(Object[])} does not have to be
1.47 + * a MergeSort, but it does have to be <i>stable</i>.)
1.48 + *
1.49 + * <p>This class is a member of the
1.50 + * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.51 + * Java Collections Framework</a>.
1.52 + *
1.53 + * @author Josh Bloch
1.54 + * @author Neal Gafter
1.55 + * @author John Rose
1.56 + * @since 1.2
1.57 + */
1.58 +public class Arrays {
1.59 +
1.60 + // Suppresses default constructor, ensuring non-instantiability.
1.61 + private Arrays() {}
1.62 +
1.63 + /*
1.64 + * Sorting of primitive type arrays.
1.65 + */
1.66 +
1.67 + /**
1.68 + * Sorts the specified array into ascending numerical order.
1.69 + *
1.70 + * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
1.71 + * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
1.72 + * offers O(n log(n)) performance on many data sets that cause other
1.73 + * quicksorts to degrade to quadratic performance, and is typically
1.74 + * faster than traditional (one-pivot) Quicksort implementations.
1.75 + *
1.76 + * @param a the array to be sorted
1.77 + */
1.78 + public static void sort(int[] a) {
1.79 + DualPivotQuicksort.sort(a);
1.80 + }
1.81 +
1.82 + /**
1.83 + * Sorts the specified range of the array into ascending order. The range
1.84 + * to be sorted extends from the index {@code fromIndex}, inclusive, to
1.85 + * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
1.86 + * the range to be sorted is empty.
1.87 + *
1.88 + * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
1.89 + * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
1.90 + * offers O(n log(n)) performance on many data sets that cause other
1.91 + * quicksorts to degrade to quadratic performance, and is typically
1.92 + * faster than traditional (one-pivot) Quicksort implementations.
1.93 + *
1.94 + * @param a the array to be sorted
1.95 + * @param fromIndex the index of the first element, inclusive, to be sorted
1.96 + * @param toIndex the index of the last element, exclusive, to be sorted
1.97 + *
1.98 + * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1.99 + * @throws ArrayIndexOutOfBoundsException
1.100 + * if {@code fromIndex < 0} or {@code toIndex > a.length}
1.101 + */
1.102 + public static void sort(int[] a, int fromIndex, int toIndex) {
1.103 + rangeCheck(a.length, fromIndex, toIndex);
1.104 + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
1.105 + }
1.106 +
1.107 + /**
1.108 + * Sorts the specified array into ascending numerical order.
1.109 + *
1.110 + * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
1.111 + * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
1.112 + * offers O(n log(n)) performance on many data sets that cause other
1.113 + * quicksorts to degrade to quadratic performance, and is typically
1.114 + * faster than traditional (one-pivot) Quicksort implementations.
1.115 + *
1.116 + * @param a the array to be sorted
1.117 + */
1.118 + public static void sort(long[] a) {
1.119 + DualPivotQuicksort.sort(a);
1.120 + }
1.121 +
1.122 + /**
1.123 + * Sorts the specified range of the array into ascending order. The range
1.124 + * to be sorted extends from the index {@code fromIndex}, inclusive, to
1.125 + * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
1.126 + * the range to be sorted is empty.
1.127 + *
1.128 + * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
1.129 + * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
1.130 + * offers O(n log(n)) performance on many data sets that cause other
1.131 + * quicksorts to degrade to quadratic performance, and is typically
1.132 + * faster than traditional (one-pivot) Quicksort implementations.
1.133 + *
1.134 + * @param a the array to be sorted
1.135 + * @param fromIndex the index of the first element, inclusive, to be sorted
1.136 + * @param toIndex the index of the last element, exclusive, to be sorted
1.137 + *
1.138 + * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1.139 + * @throws ArrayIndexOutOfBoundsException
1.140 + * if {@code fromIndex < 0} or {@code toIndex > a.length}
1.141 + */
1.142 + public static void sort(long[] a, int fromIndex, int toIndex) {
1.143 + rangeCheck(a.length, fromIndex, toIndex);
1.144 + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
1.145 + }
1.146 +
1.147 + /**
1.148 + * Sorts the specified array into ascending numerical order.
1.149 + *
1.150 + * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
1.151 + * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
1.152 + * offers O(n log(n)) performance on many data sets that cause other
1.153 + * quicksorts to degrade to quadratic performance, and is typically
1.154 + * faster than traditional (one-pivot) Quicksort implementations.
1.155 + *
1.156 + * @param a the array to be sorted
1.157 + */
1.158 + public static void sort(short[] a) {
1.159 + DualPivotQuicksort.sort(a);
1.160 + }
1.161 +
1.162 + /**
1.163 + * Sorts the specified range of the array into ascending order. The range
1.164 + * to be sorted extends from the index {@code fromIndex}, inclusive, to
1.165 + * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
1.166 + * the range to be sorted is empty.
1.167 + *
1.168 + * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
1.169 + * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
1.170 + * offers O(n log(n)) performance on many data sets that cause other
1.171 + * quicksorts to degrade to quadratic performance, and is typically
1.172 + * faster than traditional (one-pivot) Quicksort implementations.
1.173 + *
1.174 + * @param a the array to be sorted
1.175 + * @param fromIndex the index of the first element, inclusive, to be sorted
1.176 + * @param toIndex the index of the last element, exclusive, to be sorted
1.177 + *
1.178 + * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1.179 + * @throws ArrayIndexOutOfBoundsException
1.180 + * if {@code fromIndex < 0} or {@code toIndex > a.length}
1.181 + */
1.182 + public static void sort(short[] a, int fromIndex, int toIndex) {
1.183 + rangeCheck(a.length, fromIndex, toIndex);
1.184 + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
1.185 + }
1.186 +
1.187 + /**
1.188 + * Sorts the specified array into ascending numerical order.
1.189 + *
1.190 + * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
1.191 + * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
1.192 + * offers O(n log(n)) performance on many data sets that cause other
1.193 + * quicksorts to degrade to quadratic performance, and is typically
1.194 + * faster than traditional (one-pivot) Quicksort implementations.
1.195 + *
1.196 + * @param a the array to be sorted
1.197 + */
1.198 + public static void sort(char[] a) {
1.199 + DualPivotQuicksort.sort(a);
1.200 + }
1.201 +
1.202 + /**
1.203 + * Sorts the specified range of the array into ascending order. The range
1.204 + * to be sorted extends from the index {@code fromIndex}, inclusive, to
1.205 + * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
1.206 + * the range to be sorted is empty.
1.207 + *
1.208 + * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
1.209 + * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
1.210 + * offers O(n log(n)) performance on many data sets that cause other
1.211 + * quicksorts to degrade to quadratic performance, and is typically
1.212 + * faster than traditional (one-pivot) Quicksort implementations.
1.213 + *
1.214 + * @param a the array to be sorted
1.215 + * @param fromIndex the index of the first element, inclusive, to be sorted
1.216 + * @param toIndex the index of the last element, exclusive, to be sorted
1.217 + *
1.218 + * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1.219 + * @throws ArrayIndexOutOfBoundsException
1.220 + * if {@code fromIndex < 0} or {@code toIndex > a.length}
1.221 + */
1.222 + public static void sort(char[] a, int fromIndex, int toIndex) {
1.223 + rangeCheck(a.length, fromIndex, toIndex);
1.224 + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
1.225 + }
1.226 +
1.227 + /**
1.228 + * Sorts the specified array into ascending numerical order.
1.229 + *
1.230 + * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
1.231 + * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
1.232 + * offers O(n log(n)) performance on many data sets that cause other
1.233 + * quicksorts to degrade to quadratic performance, and is typically
1.234 + * faster than traditional (one-pivot) Quicksort implementations.
1.235 + *
1.236 + * @param a the array to be sorted
1.237 + */
1.238 + public static void sort(byte[] a) {
1.239 + DualPivotQuicksort.sort(a);
1.240 + }
1.241 +
1.242 + /**
1.243 + * Sorts the specified range of the array into ascending order. The range
1.244 + * to be sorted extends from the index {@code fromIndex}, inclusive, to
1.245 + * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
1.246 + * the range to be sorted is empty.
1.247 + *
1.248 + * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
1.249 + * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
1.250 + * offers O(n log(n)) performance on many data sets that cause other
1.251 + * quicksorts to degrade to quadratic performance, and is typically
1.252 + * faster than traditional (one-pivot) Quicksort implementations.
1.253 + *
1.254 + * @param a the array to be sorted
1.255 + * @param fromIndex the index of the first element, inclusive, to be sorted
1.256 + * @param toIndex the index of the last element, exclusive, to be sorted
1.257 + *
1.258 + * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1.259 + * @throws ArrayIndexOutOfBoundsException
1.260 + * if {@code fromIndex < 0} or {@code toIndex > a.length}
1.261 + */
1.262 + public static void sort(byte[] a, int fromIndex, int toIndex) {
1.263 + rangeCheck(a.length, fromIndex, toIndex);
1.264 + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
1.265 + }
1.266 +
1.267 + /**
1.268 + * Sorts the specified array into ascending numerical order.
1.269 + *
1.270 + * <p>The {@code <} relation does not provide a total order on all float
1.271 + * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
1.272 + * value compares neither less than, greater than, nor equal to any value,
1.273 + * even itself. This method uses the total order imposed by the method
1.274 + * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
1.275 + * {@code 0.0f} and {@code Float.NaN} is considered greater than any
1.276 + * other value and all {@code Float.NaN} values are considered equal.
1.277 + *
1.278 + * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
1.279 + * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
1.280 + * offers O(n log(n)) performance on many data sets that cause other
1.281 + * quicksorts to degrade to quadratic performance, and is typically
1.282 + * faster than traditional (one-pivot) Quicksort implementations.
1.283 + *
1.284 + * @param a the array to be sorted
1.285 + */
1.286 + public static void sort(float[] a) {
1.287 + DualPivotQuicksort.sort(a);
1.288 + }
1.289 +
1.290 + /**
1.291 + * Sorts the specified range of the array into ascending order. The range
1.292 + * to be sorted extends from the index {@code fromIndex}, inclusive, to
1.293 + * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
1.294 + * the range to be sorted is empty.
1.295 + *
1.296 + * <p>The {@code <} relation does not provide a total order on all float
1.297 + * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
1.298 + * value compares neither less than, greater than, nor equal to any value,
1.299 + * even itself. This method uses the total order imposed by the method
1.300 + * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
1.301 + * {@code 0.0f} and {@code Float.NaN} is considered greater than any
1.302 + * other value and all {@code Float.NaN} values are considered equal.
1.303 + *
1.304 + * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
1.305 + * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
1.306 + * offers O(n log(n)) performance on many data sets that cause other
1.307 + * quicksorts to degrade to quadratic performance, and is typically
1.308 + * faster than traditional (one-pivot) Quicksort implementations.
1.309 + *
1.310 + * @param a the array to be sorted
1.311 + * @param fromIndex the index of the first element, inclusive, to be sorted
1.312 + * @param toIndex the index of the last element, exclusive, to be sorted
1.313 + *
1.314 + * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1.315 + * @throws ArrayIndexOutOfBoundsException
1.316 + * if {@code fromIndex < 0} or {@code toIndex > a.length}
1.317 + */
1.318 + public static void sort(float[] a, int fromIndex, int toIndex) {
1.319 + rangeCheck(a.length, fromIndex, toIndex);
1.320 + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
1.321 + }
1.322 +
1.323 + /**
1.324 + * Sorts the specified array into ascending numerical order.
1.325 + *
1.326 + * <p>The {@code <} relation does not provide a total order on all double
1.327 + * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
1.328 + * value compares neither less than, greater than, nor equal to any value,
1.329 + * even itself. This method uses the total order imposed by the method
1.330 + * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
1.331 + * {@code 0.0d} and {@code Double.NaN} is considered greater than any
1.332 + * other value and all {@code Double.NaN} values are considered equal.
1.333 + *
1.334 + * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
1.335 + * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
1.336 + * offers O(n log(n)) performance on many data sets that cause other
1.337 + * quicksorts to degrade to quadratic performance, and is typically
1.338 + * faster than traditional (one-pivot) Quicksort implementations.
1.339 + *
1.340 + * @param a the array to be sorted
1.341 + */
1.342 + public static void sort(double[] a) {
1.343 + DualPivotQuicksort.sort(a);
1.344 + }
1.345 +
1.346 + /**
1.347 + * Sorts the specified range of the array into ascending order. The range
1.348 + * to be sorted extends from the index {@code fromIndex}, inclusive, to
1.349 + * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
1.350 + * the range to be sorted is empty.
1.351 + *
1.352 + * <p>The {@code <} relation does not provide a total order on all double
1.353 + * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
1.354 + * value compares neither less than, greater than, nor equal to any value,
1.355 + * even itself. This method uses the total order imposed by the method
1.356 + * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
1.357 + * {@code 0.0d} and {@code Double.NaN} is considered greater than any
1.358 + * other value and all {@code Double.NaN} values are considered equal.
1.359 + *
1.360 + * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
1.361 + * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
1.362 + * offers O(n log(n)) performance on many data sets that cause other
1.363 + * quicksorts to degrade to quadratic performance, and is typically
1.364 + * faster than traditional (one-pivot) Quicksort implementations.
1.365 + *
1.366 + * @param a the array to be sorted
1.367 + * @param fromIndex the index of the first element, inclusive, to be sorted
1.368 + * @param toIndex the index of the last element, exclusive, to be sorted
1.369 + *
1.370 + * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1.371 + * @throws ArrayIndexOutOfBoundsException
1.372 + * if {@code fromIndex < 0} or {@code toIndex > a.length}
1.373 + */
1.374 + public static void sort(double[] a, int fromIndex, int toIndex) {
1.375 + rangeCheck(a.length, fromIndex, toIndex);
1.376 + DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
1.377 + }
1.378 +
1.379 + /*
1.380 + * Sorting of complex type arrays.
1.381 + */
1.382 +
1.383 + /**
1.384 + * Old merge sort implementation can be selected (for
1.385 + * compatibility with broken comparators) using a system property.
1.386 + * Cannot be a static boolean in the enclosing class due to
1.387 + * circular dependencies. To be removed in a future release.
1.388 + */
1.389 + static final class LegacyMergeSort {
1.390 + private static final boolean userRequested = false;
1.391 + }
1.392 +
1.393 + /*
1.394 + * If this platform has an optimizing VM, check whether ComparableTimSort
1.395 + * offers any performance benefit over TimSort in conjunction with a
1.396 + * comparator that returns:
1.397 + * {@code ((Comparable)first).compareTo(Second)}.
1.398 + * If not, you are better off deleting ComparableTimSort to
1.399 + * eliminate the code duplication. In other words, the commented
1.400 + * out code below is the preferable implementation for sorting
1.401 + * arrays of Comparables if it offers sufficient performance.
1.402 + */
1.403 +
1.404 +// /**
1.405 +// * A comparator that implements the natural ordering of a group of
1.406 +// * mutually comparable elements. Using this comparator saves us
1.407 +// * from duplicating most of the code in this file (one version for
1.408 +// * Comparables, one for explicit Comparators).
1.409 +// */
1.410 +// private static final Comparator<Object> NATURAL_ORDER =
1.411 +// new Comparator<Object>() {
1.412 +// @SuppressWarnings("unchecked")
1.413 +// public int compare(Object first, Object second) {
1.414 +// return ((Comparable<Object>)first).compareTo(second);
1.415 +// }
1.416 +// };
1.417 +//
1.418 +// public static void sort(Object[] a) {
1.419 +// sort(a, 0, a.length, NATURAL_ORDER);
1.420 +// }
1.421 +//
1.422 +// public static void sort(Object[] a, int fromIndex, int toIndex) {
1.423 +// sort(a, fromIndex, toIndex, NATURAL_ORDER);
1.424 +// }
1.425 +
1.426 + /**
1.427 + * Sorts the specified array of objects into ascending order, according
1.428 + * to the {@linkplain Comparable natural ordering} of its elements.
1.429 + * All elements in the array must implement the {@link Comparable}
1.430 + * interface. Furthermore, all elements in the array must be
1.431 + * <i>mutually comparable</i> (that is, {@code e1.compareTo(e2)} must
1.432 + * not throw a {@code ClassCastException} for any elements {@code e1}
1.433 + * and {@code e2} in the array).
1.434 + *
1.435 + * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
1.436 + * not be reordered as a result of the sort.
1.437 + *
1.438 + * <p>Implementation note: This implementation is a stable, adaptive,
1.439 + * iterative mergesort that requires far fewer than n lg(n) comparisons
1.440 + * when the input array is partially sorted, while offering the
1.441 + * performance of a traditional mergesort when the input array is
1.442 + * randomly ordered. If the input array is nearly sorted, the
1.443 + * implementation requires approximately n comparisons. Temporary
1.444 + * storage requirements vary from a small constant for nearly sorted
1.445 + * input arrays to n/2 object references for randomly ordered input
1.446 + * arrays.
1.447 + *
1.448 + * <p>The implementation takes equal advantage of ascending and
1.449 + * descending order in its input array, and can take advantage of
1.450 + * ascending and descending order in different parts of the the same
1.451 + * input array. It is well-suited to merging two or more sorted arrays:
1.452 + * simply concatenate the arrays and sort the resulting array.
1.453 + *
1.454 + * <p>The implementation was adapted from Tim Peters's list sort for Python
1.455 + * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
1.456 + * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
1.457 + * Sorting and Information Theoretic Complexity", in Proceedings of the
1.458 + * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
1.459 + * January 1993.
1.460 + *
1.461 + * @param a the array to be sorted
1.462 + * @throws ClassCastException if the array contains elements that are not
1.463 + * <i>mutually comparable</i> (for example, strings and integers)
1.464 + * @throws IllegalArgumentException (optional) if the natural
1.465 + * ordering of the array elements is found to violate the
1.466 + * {@link Comparable} contract
1.467 + */
1.468 + public static void sort(Object[] a) {
1.469 + if (LegacyMergeSort.userRequested)
1.470 + legacyMergeSort(a);
1.471 + else
1.472 + ComparableTimSort.sort(a);
1.473 + }
1.474 +
1.475 + /** To be removed in a future release. */
1.476 + private static void legacyMergeSort(Object[] a) {
1.477 + Object[] aux = a.clone();
1.478 + mergeSort(aux, a, 0, a.length, 0);
1.479 + }
1.480 +
1.481 + /**
1.482 + * Sorts the specified range of the specified array of objects into
1.483 + * ascending order, according to the
1.484 + * {@linkplain Comparable natural ordering} of its
1.485 + * elements. The range to be sorted extends from index
1.486 + * {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive.
1.487 + * (If {@code fromIndex==toIndex}, the range to be sorted is empty.) All
1.488 + * elements in this range must implement the {@link Comparable}
1.489 + * interface. Furthermore, all elements in this range must be <i>mutually
1.490 + * comparable</i> (that is, {@code e1.compareTo(e2)} must not throw a
1.491 + * {@code ClassCastException} for any elements {@code e1} and
1.492 + * {@code e2} in the array).
1.493 + *
1.494 + * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
1.495 + * not be reordered as a result of the sort.
1.496 + *
1.497 + * <p>Implementation note: This implementation is a stable, adaptive,
1.498 + * iterative mergesort that requires far fewer than n lg(n) comparisons
1.499 + * when the input array is partially sorted, while offering the
1.500 + * performance of a traditional mergesort when the input array is
1.501 + * randomly ordered. If the input array is nearly sorted, the
1.502 + * implementation requires approximately n comparisons. Temporary
1.503 + * storage requirements vary from a small constant for nearly sorted
1.504 + * input arrays to n/2 object references for randomly ordered input
1.505 + * arrays.
1.506 + *
1.507 + * <p>The implementation takes equal advantage of ascending and
1.508 + * descending order in its input array, and can take advantage of
1.509 + * ascending and descending order in different parts of the the same
1.510 + * input array. It is well-suited to merging two or more sorted arrays:
1.511 + * simply concatenate the arrays and sort the resulting array.
1.512 + *
1.513 + * <p>The implementation was adapted from Tim Peters's list sort for Python
1.514 + * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
1.515 + * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
1.516 + * Sorting and Information Theoretic Complexity", in Proceedings of the
1.517 + * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
1.518 + * January 1993.
1.519 + *
1.520 + * @param a the array to be sorted
1.521 + * @param fromIndex the index of the first element (inclusive) to be
1.522 + * sorted
1.523 + * @param toIndex the index of the last element (exclusive) to be sorted
1.524 + * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
1.525 + * (optional) if the natural ordering of the array elements is
1.526 + * found to violate the {@link Comparable} contract
1.527 + * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
1.528 + * {@code toIndex > a.length}
1.529 + * @throws ClassCastException if the array contains elements that are
1.530 + * not <i>mutually comparable</i> (for example, strings and
1.531 + * integers).
1.532 + */
1.533 + public static void sort(Object[] a, int fromIndex, int toIndex) {
1.534 + if (LegacyMergeSort.userRequested)
1.535 + legacyMergeSort(a, fromIndex, toIndex);
1.536 + else
1.537 + ComparableTimSort.sort(a, fromIndex, toIndex);
1.538 + }
1.539 +
1.540 + /** To be removed in a future release. */
1.541 + private static void legacyMergeSort(Object[] a,
1.542 + int fromIndex, int toIndex) {
1.543 + rangeCheck(a.length, fromIndex, toIndex);
1.544 + Object[] aux = copyOfRange(a, fromIndex, toIndex);
1.545 + mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
1.546 + }
1.547 +
1.548 + /**
1.549 + * Tuning parameter: list size at or below which insertion sort will be
1.550 + * used in preference to mergesort.
1.551 + * To be removed in a future release.
1.552 + */
1.553 + private static final int INSERTIONSORT_THRESHOLD = 7;
1.554 +
1.555 + /**
1.556 + * Src is the source array that starts at index 0
1.557 + * Dest is the (possibly larger) array destination with a possible offset
1.558 + * low is the index in dest to start sorting
1.559 + * high is the end index in dest to end sorting
1.560 + * off is the offset to generate corresponding low, high in src
1.561 + * To be removed in a future release.
1.562 + */
1.563 + private static void mergeSort(Object[] src,
1.564 + Object[] dest,
1.565 + int low,
1.566 + int high,
1.567 + int off) {
1.568 + int length = high - low;
1.569 +
1.570 + // Insertion sort on smallest arrays
1.571 + if (length < INSERTIONSORT_THRESHOLD) {
1.572 + for (int i=low; i<high; i++)
1.573 + for (int j=i; j>low &&
1.574 + ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
1.575 + swap(dest, j, j-1);
1.576 + return;
1.577 + }
1.578 +
1.579 + // Recursively sort halves of dest into src
1.580 + int destLow = low;
1.581 + int destHigh = high;
1.582 + low += off;
1.583 + high += off;
1.584 + int mid = (low + high) >>> 1;
1.585 + mergeSort(dest, src, low, mid, -off);
1.586 + mergeSort(dest, src, mid, high, -off);
1.587 +
1.588 + // If list is already sorted, just copy from src to dest. This is an
1.589 + // optimization that results in faster sorts for nearly ordered lists.
1.590 + if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
1.591 + System.arraycopy(src, low, dest, destLow, length);
1.592 + return;
1.593 + }
1.594 +
1.595 + // Merge sorted halves (now in src) into dest
1.596 + for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
1.597 + if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
1.598 + dest[i] = src[p++];
1.599 + else
1.600 + dest[i] = src[q++];
1.601 + }
1.602 + }
1.603 +
1.604 + /**
1.605 + * Swaps x[a] with x[b].
1.606 + */
1.607 + private static void swap(Object[] x, int a, int b) {
1.608 + Object t = x[a];
1.609 + x[a] = x[b];
1.610 + x[b] = t;
1.611 + }
1.612 +
1.613 + /**
1.614 + * Sorts the specified array of objects according to the order induced by
1.615 + * the specified comparator. All elements in the array must be
1.616 + * <i>mutually comparable</i> by the specified comparator (that is,
1.617 + * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
1.618 + * for any elements {@code e1} and {@code e2} in the array).
1.619 + *
1.620 + * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
1.621 + * not be reordered as a result of the sort.
1.622 + *
1.623 + * <p>Implementation note: This implementation is a stable, adaptive,
1.624 + * iterative mergesort that requires far fewer than n lg(n) comparisons
1.625 + * when the input array is partially sorted, while offering the
1.626 + * performance of a traditional mergesort when the input array is
1.627 + * randomly ordered. If the input array is nearly sorted, the
1.628 + * implementation requires approximately n comparisons. Temporary
1.629 + * storage requirements vary from a small constant for nearly sorted
1.630 + * input arrays to n/2 object references for randomly ordered input
1.631 + * arrays.
1.632 + *
1.633 + * <p>The implementation takes equal advantage of ascending and
1.634 + * descending order in its input array, and can take advantage of
1.635 + * ascending and descending order in different parts of the the same
1.636 + * input array. It is well-suited to merging two or more sorted arrays:
1.637 + * simply concatenate the arrays and sort the resulting array.
1.638 + *
1.639 + * <p>The implementation was adapted from Tim Peters's list sort for Python
1.640 + * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
1.641 + * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
1.642 + * Sorting and Information Theoretic Complexity", in Proceedings of the
1.643 + * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
1.644 + * January 1993.
1.645 + *
1.646 + * @param a the array to be sorted
1.647 + * @param c the comparator to determine the order of the array. A
1.648 + * {@code null} value indicates that the elements'
1.649 + * {@linkplain Comparable natural ordering} should be used.
1.650 + * @throws ClassCastException if the array contains elements that are
1.651 + * not <i>mutually comparable</i> using the specified comparator
1.652 + * @throws IllegalArgumentException (optional) if the comparator is
1.653 + * found to violate the {@link Comparator} contract
1.654 + */
1.655 + public static <T> void sort(T[] a, Comparator<? super T> c) {
1.656 + if (LegacyMergeSort.userRequested)
1.657 + legacyMergeSort(a, c);
1.658 + else
1.659 + TimSort.sort(a, c);
1.660 + }
1.661 +
1.662 + /** To be removed in a future release. */
1.663 + private static <T> void legacyMergeSort(T[] a, Comparator<? super T> c) {
1.664 + T[] aux = a.clone();
1.665 + if (c==null)
1.666 + mergeSort(aux, a, 0, a.length, 0);
1.667 + else
1.668 + mergeSort(aux, a, 0, a.length, 0, c);
1.669 + }
1.670 +
1.671 + /**
1.672 + * Sorts the specified range of the specified array of objects according
1.673 + * to the order induced by the specified comparator. The range to be
1.674 + * sorted extends from index {@code fromIndex}, inclusive, to index
1.675 + * {@code toIndex}, exclusive. (If {@code fromIndex==toIndex}, the
1.676 + * range to be sorted is empty.) All elements in the range must be
1.677 + * <i>mutually comparable</i> by the specified comparator (that is,
1.678 + * {@code c.compare(e1, e2)} must not throw a {@code ClassCastException}
1.679 + * for any elements {@code e1} and {@code e2} in the range).
1.680 + *
1.681 + * <p>This sort is guaranteed to be <i>stable</i>: equal elements will
1.682 + * not be reordered as a result of the sort.
1.683 + *
1.684 + * <p>Implementation note: This implementation is a stable, adaptive,
1.685 + * iterative mergesort that requires far fewer than n lg(n) comparisons
1.686 + * when the input array is partially sorted, while offering the
1.687 + * performance of a traditional mergesort when the input array is
1.688 + * randomly ordered. If the input array is nearly sorted, the
1.689 + * implementation requires approximately n comparisons. Temporary
1.690 + * storage requirements vary from a small constant for nearly sorted
1.691 + * input arrays to n/2 object references for randomly ordered input
1.692 + * arrays.
1.693 + *
1.694 + * <p>The implementation takes equal advantage of ascending and
1.695 + * descending order in its input array, and can take advantage of
1.696 + * ascending and descending order in different parts of the the same
1.697 + * input array. It is well-suited to merging two or more sorted arrays:
1.698 + * simply concatenate the arrays and sort the resulting array.
1.699 + *
1.700 + * <p>The implementation was adapted from Tim Peters's list sort for Python
1.701 + * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
1.702 + * TimSort</a>). It uses techiques from Peter McIlroy's "Optimistic
1.703 + * Sorting and Information Theoretic Complexity", in Proceedings of the
1.704 + * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
1.705 + * January 1993.
1.706 + *
1.707 + * @param a the array to be sorted
1.708 + * @param fromIndex the index of the first element (inclusive) to be
1.709 + * sorted
1.710 + * @param toIndex the index of the last element (exclusive) to be sorted
1.711 + * @param c the comparator to determine the order of the array. A
1.712 + * {@code null} value indicates that the elements'
1.713 + * {@linkplain Comparable natural ordering} should be used.
1.714 + * @throws ClassCastException if the array contains elements that are not
1.715 + * <i>mutually comparable</i> using the specified comparator.
1.716 + * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
1.717 + * (optional) if the comparator is found to violate the
1.718 + * {@link Comparator} contract
1.719 + * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
1.720 + * {@code toIndex > a.length}
1.721 + */
1.722 + public static <T> void sort(T[] a, int fromIndex, int toIndex,
1.723 + Comparator<? super T> c) {
1.724 + if (LegacyMergeSort.userRequested)
1.725 + legacyMergeSort(a, fromIndex, toIndex, c);
1.726 + else
1.727 + TimSort.sort(a, fromIndex, toIndex, c);
1.728 + }
1.729 +
1.730 + /** To be removed in a future release. */
1.731 + private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex,
1.732 + Comparator<? super T> c) {
1.733 + rangeCheck(a.length, fromIndex, toIndex);
1.734 + T[] aux = copyOfRange(a, fromIndex, toIndex);
1.735 + if (c==null)
1.736 + mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
1.737 + else
1.738 + mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
1.739 + }
1.740 +
1.741 + /**
1.742 + * Src is the source array that starts at index 0
1.743 + * Dest is the (possibly larger) array destination with a possible offset
1.744 + * low is the index in dest to start sorting
1.745 + * high is the end index in dest to end sorting
1.746 + * off is the offset into src corresponding to low in dest
1.747 + * To be removed in a future release.
1.748 + */
1.749 + private static void mergeSort(Object[] src,
1.750 + Object[] dest,
1.751 + int low, int high, int off,
1.752 + Comparator c) {
1.753 + int length = high - low;
1.754 +
1.755 + // Insertion sort on smallest arrays
1.756 + if (length < INSERTIONSORT_THRESHOLD) {
1.757 + for (int i=low; i<high; i++)
1.758 + for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
1.759 + swap(dest, j, j-1);
1.760 + return;
1.761 + }
1.762 +
1.763 + // Recursively sort halves of dest into src
1.764 + int destLow = low;
1.765 + int destHigh = high;
1.766 + low += off;
1.767 + high += off;
1.768 + int mid = (low + high) >>> 1;
1.769 + mergeSort(dest, src, low, mid, -off, c);
1.770 + mergeSort(dest, src, mid, high, -off, c);
1.771 +
1.772 + // If list is already sorted, just copy from src to dest. This is an
1.773 + // optimization that results in faster sorts for nearly ordered lists.
1.774 + if (c.compare(src[mid-1], src[mid]) <= 0) {
1.775 + System.arraycopy(src, low, dest, destLow, length);
1.776 + return;
1.777 + }
1.778 +
1.779 + // Merge sorted halves (now in src) into dest
1.780 + for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
1.781 + if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
1.782 + dest[i] = src[p++];
1.783 + else
1.784 + dest[i] = src[q++];
1.785 + }
1.786 + }
1.787 +
1.788 + /**
1.789 + * Checks that {@code fromIndex} and {@code toIndex} are in
1.790 + * the range and throws an appropriate exception, if they aren't.
1.791 + */
1.792 + private static void rangeCheck(int length, int fromIndex, int toIndex) {
1.793 + if (fromIndex > toIndex) {
1.794 + throw new IllegalArgumentException(
1.795 + "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
1.796 + }
1.797 + if (fromIndex < 0) {
1.798 + throw new ArrayIndexOutOfBoundsException(fromIndex);
1.799 + }
1.800 + if (toIndex > length) {
1.801 + throw new ArrayIndexOutOfBoundsException(toIndex);
1.802 + }
1.803 + }
1.804 +
1.805 + // Searching
1.806 +
1.807 + /**
1.808 + * Searches the specified array of longs for the specified value using the
1.809 + * binary search algorithm. The array must be sorted (as
1.810 + * by the {@link #sort(long[])} method) prior to making this call. If it
1.811 + * is not sorted, the results are undefined. If the array contains
1.812 + * multiple elements with the specified value, there is no guarantee which
1.813 + * one will be found.
1.814 + *
1.815 + * @param a the array to be searched
1.816 + * @param key the value to be searched for
1.817 + * @return index of the search key, if it is contained in the array;
1.818 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.819 + * <i>insertion point</i> is defined as the point at which the
1.820 + * key would be inserted into the array: the index of the first
1.821 + * element greater than the key, or <tt>a.length</tt> if all
1.822 + * elements in the array are less than the specified key. Note
1.823 + * that this guarantees that the return value will be >= 0 if
1.824 + * and only if the key is found.
1.825 + */
1.826 + public static int binarySearch(long[] a, long key) {
1.827 + return binarySearch0(a, 0, a.length, key);
1.828 + }
1.829 +
1.830 + /**
1.831 + * Searches a range of
1.832 + * the specified array of longs for the specified value using the
1.833 + * binary search algorithm.
1.834 + * The range must be sorted (as
1.835 + * by the {@link #sort(long[], int, int)} method)
1.836 + * prior to making this call. If it
1.837 + * is not sorted, the results are undefined. If the range contains
1.838 + * multiple elements with the specified value, there is no guarantee which
1.839 + * one will be found.
1.840 + *
1.841 + * @param a the array to be searched
1.842 + * @param fromIndex the index of the first element (inclusive) to be
1.843 + * searched
1.844 + * @param toIndex the index of the last element (exclusive) to be searched
1.845 + * @param key the value to be searched for
1.846 + * @return index of the search key, if it is contained in the array
1.847 + * within the specified range;
1.848 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.849 + * <i>insertion point</i> is defined as the point at which the
1.850 + * key would be inserted into the array: the index of the first
1.851 + * element in the range greater than the key,
1.852 + * or <tt>toIndex</tt> if all
1.853 + * elements in the range are less than the specified key. Note
1.854 + * that this guarantees that the return value will be >= 0 if
1.855 + * and only if the key is found.
1.856 + * @throws IllegalArgumentException
1.857 + * if {@code fromIndex > toIndex}
1.858 + * @throws ArrayIndexOutOfBoundsException
1.859 + * if {@code fromIndex < 0 or toIndex > a.length}
1.860 + * @since 1.6
1.861 + */
1.862 + public static int binarySearch(long[] a, int fromIndex, int toIndex,
1.863 + long key) {
1.864 + rangeCheck(a.length, fromIndex, toIndex);
1.865 + return binarySearch0(a, fromIndex, toIndex, key);
1.866 + }
1.867 +
1.868 + // Like public version, but without range checks.
1.869 + private static int binarySearch0(long[] a, int fromIndex, int toIndex,
1.870 + long key) {
1.871 + int low = fromIndex;
1.872 + int high = toIndex - 1;
1.873 +
1.874 + while (low <= high) {
1.875 + int mid = (low + high) >>> 1;
1.876 + long midVal = a[mid];
1.877 +
1.878 + if (midVal < key)
1.879 + low = mid + 1;
1.880 + else if (midVal > key)
1.881 + high = mid - 1;
1.882 + else
1.883 + return mid; // key found
1.884 + }
1.885 + return -(low + 1); // key not found.
1.886 + }
1.887 +
1.888 + /**
1.889 + * Searches the specified array of ints for the specified value using the
1.890 + * binary search algorithm. The array must be sorted (as
1.891 + * by the {@link #sort(int[])} method) prior to making this call. If it
1.892 + * is not sorted, the results are undefined. If the array contains
1.893 + * multiple elements with the specified value, there is no guarantee which
1.894 + * one will be found.
1.895 + *
1.896 + * @param a the array to be searched
1.897 + * @param key the value to be searched for
1.898 + * @return index of the search key, if it is contained in the array;
1.899 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.900 + * <i>insertion point</i> is defined as the point at which the
1.901 + * key would be inserted into the array: the index of the first
1.902 + * element greater than the key, or <tt>a.length</tt> if all
1.903 + * elements in the array are less than the specified key. Note
1.904 + * that this guarantees that the return value will be >= 0 if
1.905 + * and only if the key is found.
1.906 + */
1.907 + public static int binarySearch(int[] a, int key) {
1.908 + return binarySearch0(a, 0, a.length, key);
1.909 + }
1.910 +
1.911 + /**
1.912 + * Searches a range of
1.913 + * the specified array of ints for the specified value using the
1.914 + * binary search algorithm.
1.915 + * The range must be sorted (as
1.916 + * by the {@link #sort(int[], int, int)} method)
1.917 + * prior to making this call. If it
1.918 + * is not sorted, the results are undefined. If the range contains
1.919 + * multiple elements with the specified value, there is no guarantee which
1.920 + * one will be found.
1.921 + *
1.922 + * @param a the array to be searched
1.923 + * @param fromIndex the index of the first element (inclusive) to be
1.924 + * searched
1.925 + * @param toIndex the index of the last element (exclusive) to be searched
1.926 + * @param key the value to be searched for
1.927 + * @return index of the search key, if it is contained in the array
1.928 + * within the specified range;
1.929 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.930 + * <i>insertion point</i> is defined as the point at which the
1.931 + * key would be inserted into the array: the index of the first
1.932 + * element in the range greater than the key,
1.933 + * or <tt>toIndex</tt> if all
1.934 + * elements in the range are less than the specified key. Note
1.935 + * that this guarantees that the return value will be >= 0 if
1.936 + * and only if the key is found.
1.937 + * @throws IllegalArgumentException
1.938 + * if {@code fromIndex > toIndex}
1.939 + * @throws ArrayIndexOutOfBoundsException
1.940 + * if {@code fromIndex < 0 or toIndex > a.length}
1.941 + * @since 1.6
1.942 + */
1.943 + public static int binarySearch(int[] a, int fromIndex, int toIndex,
1.944 + int key) {
1.945 + rangeCheck(a.length, fromIndex, toIndex);
1.946 + return binarySearch0(a, fromIndex, toIndex, key);
1.947 + }
1.948 +
1.949 + // Like public version, but without range checks.
1.950 + private static int binarySearch0(int[] a, int fromIndex, int toIndex,
1.951 + int key) {
1.952 + int low = fromIndex;
1.953 + int high = toIndex - 1;
1.954 +
1.955 + while (low <= high) {
1.956 + int mid = (low + high) >>> 1;
1.957 + int midVal = a[mid];
1.958 +
1.959 + if (midVal < key)
1.960 + low = mid + 1;
1.961 + else if (midVal > key)
1.962 + high = mid - 1;
1.963 + else
1.964 + return mid; // key found
1.965 + }
1.966 + return -(low + 1); // key not found.
1.967 + }
1.968 +
1.969 + /**
1.970 + * Searches the specified array of shorts for the specified value using
1.971 + * the binary search algorithm. The array must be sorted
1.972 + * (as by the {@link #sort(short[])} method) prior to making this call. If
1.973 + * it is not sorted, the results are undefined. If the array contains
1.974 + * multiple elements with the specified value, there is no guarantee which
1.975 + * one will be found.
1.976 + *
1.977 + * @param a the array to be searched
1.978 + * @param key the value to be searched for
1.979 + * @return index of the search key, if it is contained in the array;
1.980 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.981 + * <i>insertion point</i> is defined as the point at which the
1.982 + * key would be inserted into the array: the index of the first
1.983 + * element greater than the key, or <tt>a.length</tt> if all
1.984 + * elements in the array are less than the specified key. Note
1.985 + * that this guarantees that the return value will be >= 0 if
1.986 + * and only if the key is found.
1.987 + */
1.988 + public static int binarySearch(short[] a, short key) {
1.989 + return binarySearch0(a, 0, a.length, key);
1.990 + }
1.991 +
1.992 + /**
1.993 + * Searches a range of
1.994 + * the specified array of shorts for the specified value using
1.995 + * the binary search algorithm.
1.996 + * The range must be sorted
1.997 + * (as by the {@link #sort(short[], int, int)} method)
1.998 + * prior to making this call. If
1.999 + * it is not sorted, the results are undefined. If the range contains
1.1000 + * multiple elements with the specified value, there is no guarantee which
1.1001 + * one will be found.
1.1002 + *
1.1003 + * @param a the array to be searched
1.1004 + * @param fromIndex the index of the first element (inclusive) to be
1.1005 + * searched
1.1006 + * @param toIndex the index of the last element (exclusive) to be searched
1.1007 + * @param key the value to be searched for
1.1008 + * @return index of the search key, if it is contained in the array
1.1009 + * within the specified range;
1.1010 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.1011 + * <i>insertion point</i> is defined as the point at which the
1.1012 + * key would be inserted into the array: the index of the first
1.1013 + * element in the range greater than the key,
1.1014 + * or <tt>toIndex</tt> if all
1.1015 + * elements in the range are less than the specified key. Note
1.1016 + * that this guarantees that the return value will be >= 0 if
1.1017 + * and only if the key is found.
1.1018 + * @throws IllegalArgumentException
1.1019 + * if {@code fromIndex > toIndex}
1.1020 + * @throws ArrayIndexOutOfBoundsException
1.1021 + * if {@code fromIndex < 0 or toIndex > a.length}
1.1022 + * @since 1.6
1.1023 + */
1.1024 + public static int binarySearch(short[] a, int fromIndex, int toIndex,
1.1025 + short key) {
1.1026 + rangeCheck(a.length, fromIndex, toIndex);
1.1027 + return binarySearch0(a, fromIndex, toIndex, key);
1.1028 + }
1.1029 +
1.1030 + // Like public version, but without range checks.
1.1031 + private static int binarySearch0(short[] a, int fromIndex, int toIndex,
1.1032 + short key) {
1.1033 + int low = fromIndex;
1.1034 + int high = toIndex - 1;
1.1035 +
1.1036 + while (low <= high) {
1.1037 + int mid = (low + high) >>> 1;
1.1038 + short midVal = a[mid];
1.1039 +
1.1040 + if (midVal < key)
1.1041 + low = mid + 1;
1.1042 + else if (midVal > key)
1.1043 + high = mid - 1;
1.1044 + else
1.1045 + return mid; // key found
1.1046 + }
1.1047 + return -(low + 1); // key not found.
1.1048 + }
1.1049 +
1.1050 + /**
1.1051 + * Searches the specified array of chars for the specified value using the
1.1052 + * binary search algorithm. The array must be sorted (as
1.1053 + * by the {@link #sort(char[])} method) prior to making this call. If it
1.1054 + * is not sorted, the results are undefined. If the array contains
1.1055 + * multiple elements with the specified value, there is no guarantee which
1.1056 + * one will be found.
1.1057 + *
1.1058 + * @param a the array to be searched
1.1059 + * @param key the value to be searched for
1.1060 + * @return index of the search key, if it is contained in the array;
1.1061 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.1062 + * <i>insertion point</i> is defined as the point at which the
1.1063 + * key would be inserted into the array: the index of the first
1.1064 + * element greater than the key, or <tt>a.length</tt> if all
1.1065 + * elements in the array are less than the specified key. Note
1.1066 + * that this guarantees that the return value will be >= 0 if
1.1067 + * and only if the key is found.
1.1068 + */
1.1069 + public static int binarySearch(char[] a, char key) {
1.1070 + return binarySearch0(a, 0, a.length, key);
1.1071 + }
1.1072 +
1.1073 + /**
1.1074 + * Searches a range of
1.1075 + * the specified array of chars for the specified value using the
1.1076 + * binary search algorithm.
1.1077 + * The range must be sorted (as
1.1078 + * by the {@link #sort(char[], int, int)} method)
1.1079 + * prior to making this call. If it
1.1080 + * is not sorted, the results are undefined. If the range contains
1.1081 + * multiple elements with the specified value, there is no guarantee which
1.1082 + * one will be found.
1.1083 + *
1.1084 + * @param a the array to be searched
1.1085 + * @param fromIndex the index of the first element (inclusive) to be
1.1086 + * searched
1.1087 + * @param toIndex the index of the last element (exclusive) to be searched
1.1088 + * @param key the value to be searched for
1.1089 + * @return index of the search key, if it is contained in the array
1.1090 + * within the specified range;
1.1091 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.1092 + * <i>insertion point</i> is defined as the point at which the
1.1093 + * key would be inserted into the array: the index of the first
1.1094 + * element in the range greater than the key,
1.1095 + * or <tt>toIndex</tt> if all
1.1096 + * elements in the range are less than the specified key. Note
1.1097 + * that this guarantees that the return value will be >= 0 if
1.1098 + * and only if the key is found.
1.1099 + * @throws IllegalArgumentException
1.1100 + * if {@code fromIndex > toIndex}
1.1101 + * @throws ArrayIndexOutOfBoundsException
1.1102 + * if {@code fromIndex < 0 or toIndex > a.length}
1.1103 + * @since 1.6
1.1104 + */
1.1105 + public static int binarySearch(char[] a, int fromIndex, int toIndex,
1.1106 + char key) {
1.1107 + rangeCheck(a.length, fromIndex, toIndex);
1.1108 + return binarySearch0(a, fromIndex, toIndex, key);
1.1109 + }
1.1110 +
1.1111 + // Like public version, but without range checks.
1.1112 + private static int binarySearch0(char[] a, int fromIndex, int toIndex,
1.1113 + char key) {
1.1114 + int low = fromIndex;
1.1115 + int high = toIndex - 1;
1.1116 +
1.1117 + while (low <= high) {
1.1118 + int mid = (low + high) >>> 1;
1.1119 + char midVal = a[mid];
1.1120 +
1.1121 + if (midVal < key)
1.1122 + low = mid + 1;
1.1123 + else if (midVal > key)
1.1124 + high = mid - 1;
1.1125 + else
1.1126 + return mid; // key found
1.1127 + }
1.1128 + return -(low + 1); // key not found.
1.1129 + }
1.1130 +
1.1131 + /**
1.1132 + * Searches the specified array of bytes for the specified value using the
1.1133 + * binary search algorithm. The array must be sorted (as
1.1134 + * by the {@link #sort(byte[])} method) prior to making this call. If it
1.1135 + * is not sorted, the results are undefined. If the array contains
1.1136 + * multiple elements with the specified value, there is no guarantee which
1.1137 + * one will be found.
1.1138 + *
1.1139 + * @param a the array to be searched
1.1140 + * @param key the value to be searched for
1.1141 + * @return index of the search key, if it is contained in the array;
1.1142 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.1143 + * <i>insertion point</i> is defined as the point at which the
1.1144 + * key would be inserted into the array: the index of the first
1.1145 + * element greater than the key, or <tt>a.length</tt> if all
1.1146 + * elements in the array are less than the specified key. Note
1.1147 + * that this guarantees that the return value will be >= 0 if
1.1148 + * and only if the key is found.
1.1149 + */
1.1150 + public static int binarySearch(byte[] a, byte key) {
1.1151 + return binarySearch0(a, 0, a.length, key);
1.1152 + }
1.1153 +
1.1154 + /**
1.1155 + * Searches a range of
1.1156 + * the specified array of bytes for the specified value using the
1.1157 + * binary search algorithm.
1.1158 + * The range must be sorted (as
1.1159 + * by the {@link #sort(byte[], int, int)} method)
1.1160 + * prior to making this call. If it
1.1161 + * is not sorted, the results are undefined. If the range contains
1.1162 + * multiple elements with the specified value, there is no guarantee which
1.1163 + * one will be found.
1.1164 + *
1.1165 + * @param a the array to be searched
1.1166 + * @param fromIndex the index of the first element (inclusive) to be
1.1167 + * searched
1.1168 + * @param toIndex the index of the last element (exclusive) to be searched
1.1169 + * @param key the value to be searched for
1.1170 + * @return index of the search key, if it is contained in the array
1.1171 + * within the specified range;
1.1172 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.1173 + * <i>insertion point</i> is defined as the point at which the
1.1174 + * key would be inserted into the array: the index of the first
1.1175 + * element in the range greater than the key,
1.1176 + * or <tt>toIndex</tt> if all
1.1177 + * elements in the range are less than the specified key. Note
1.1178 + * that this guarantees that the return value will be >= 0 if
1.1179 + * and only if the key is found.
1.1180 + * @throws IllegalArgumentException
1.1181 + * if {@code fromIndex > toIndex}
1.1182 + * @throws ArrayIndexOutOfBoundsException
1.1183 + * if {@code fromIndex < 0 or toIndex > a.length}
1.1184 + * @since 1.6
1.1185 + */
1.1186 + public static int binarySearch(byte[] a, int fromIndex, int toIndex,
1.1187 + byte key) {
1.1188 + rangeCheck(a.length, fromIndex, toIndex);
1.1189 + return binarySearch0(a, fromIndex, toIndex, key);
1.1190 + }
1.1191 +
1.1192 + // Like public version, but without range checks.
1.1193 + private static int binarySearch0(byte[] a, int fromIndex, int toIndex,
1.1194 + byte key) {
1.1195 + int low = fromIndex;
1.1196 + int high = toIndex - 1;
1.1197 +
1.1198 + while (low <= high) {
1.1199 + int mid = (low + high) >>> 1;
1.1200 + byte midVal = a[mid];
1.1201 +
1.1202 + if (midVal < key)
1.1203 + low = mid + 1;
1.1204 + else if (midVal > key)
1.1205 + high = mid - 1;
1.1206 + else
1.1207 + return mid; // key found
1.1208 + }
1.1209 + return -(low + 1); // key not found.
1.1210 + }
1.1211 +
1.1212 + /**
1.1213 + * Searches the specified array of doubles for the specified value using
1.1214 + * the binary search algorithm. The array must be sorted
1.1215 + * (as by the {@link #sort(double[])} method) prior to making this call.
1.1216 + * If it is not sorted, the results are undefined. If the array contains
1.1217 + * multiple elements with the specified value, there is no guarantee which
1.1218 + * one will be found. This method considers all NaN values to be
1.1219 + * equivalent and equal.
1.1220 + *
1.1221 + * @param a the array to be searched
1.1222 + * @param key the value to be searched for
1.1223 + * @return index of the search key, if it is contained in the array;
1.1224 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.1225 + * <i>insertion point</i> is defined as the point at which the
1.1226 + * key would be inserted into the array: the index of the first
1.1227 + * element greater than the key, or <tt>a.length</tt> if all
1.1228 + * elements in the array are less than the specified key. Note
1.1229 + * that this guarantees that the return value will be >= 0 if
1.1230 + * and only if the key is found.
1.1231 + */
1.1232 + public static int binarySearch(double[] a, double key) {
1.1233 + return binarySearch0(a, 0, a.length, key);
1.1234 + }
1.1235 +
1.1236 + /**
1.1237 + * Searches a range of
1.1238 + * the specified array of doubles for the specified value using
1.1239 + * the binary search algorithm.
1.1240 + * The range must be sorted
1.1241 + * (as by the {@link #sort(double[], int, int)} method)
1.1242 + * prior to making this call.
1.1243 + * If it is not sorted, the results are undefined. If the range contains
1.1244 + * multiple elements with the specified value, there is no guarantee which
1.1245 + * one will be found. This method considers all NaN values to be
1.1246 + * equivalent and equal.
1.1247 + *
1.1248 + * @param a the array to be searched
1.1249 + * @param fromIndex the index of the first element (inclusive) to be
1.1250 + * searched
1.1251 + * @param toIndex the index of the last element (exclusive) to be searched
1.1252 + * @param key the value to be searched for
1.1253 + * @return index of the search key, if it is contained in the array
1.1254 + * within the specified range;
1.1255 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.1256 + * <i>insertion point</i> is defined as the point at which the
1.1257 + * key would be inserted into the array: the index of the first
1.1258 + * element in the range greater than the key,
1.1259 + * or <tt>toIndex</tt> if all
1.1260 + * elements in the range are less than the specified key. Note
1.1261 + * that this guarantees that the return value will be >= 0 if
1.1262 + * and only if the key is found.
1.1263 + * @throws IllegalArgumentException
1.1264 + * if {@code fromIndex > toIndex}
1.1265 + * @throws ArrayIndexOutOfBoundsException
1.1266 + * if {@code fromIndex < 0 or toIndex > a.length}
1.1267 + * @since 1.6
1.1268 + */
1.1269 + public static int binarySearch(double[] a, int fromIndex, int toIndex,
1.1270 + double key) {
1.1271 + rangeCheck(a.length, fromIndex, toIndex);
1.1272 + return binarySearch0(a, fromIndex, toIndex, key);
1.1273 + }
1.1274 +
1.1275 + // Like public version, but without range checks.
1.1276 + private static int binarySearch0(double[] a, int fromIndex, int toIndex,
1.1277 + double key) {
1.1278 + int low = fromIndex;
1.1279 + int high = toIndex - 1;
1.1280 +
1.1281 + while (low <= high) {
1.1282 + int mid = (low + high) >>> 1;
1.1283 + double midVal = a[mid];
1.1284 +
1.1285 + if (midVal < key)
1.1286 + low = mid + 1; // Neither val is NaN, thisVal is smaller
1.1287 + else if (midVal > key)
1.1288 + high = mid - 1; // Neither val is NaN, thisVal is larger
1.1289 + else {
1.1290 + long midBits = Double.doubleToLongBits(midVal);
1.1291 + long keyBits = Double.doubleToLongBits(key);
1.1292 + if (midBits == keyBits) // Values are equal
1.1293 + return mid; // Key found
1.1294 + else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
1.1295 + low = mid + 1;
1.1296 + else // (0.0, -0.0) or (NaN, !NaN)
1.1297 + high = mid - 1;
1.1298 + }
1.1299 + }
1.1300 + return -(low + 1); // key not found.
1.1301 + }
1.1302 +
1.1303 + /**
1.1304 + * Searches the specified array of floats for the specified value using
1.1305 + * the binary search algorithm. The array must be sorted
1.1306 + * (as by the {@link #sort(float[])} method) prior to making this call. If
1.1307 + * it is not sorted, the results are undefined. If the array contains
1.1308 + * multiple elements with the specified value, there is no guarantee which
1.1309 + * one will be found. This method considers all NaN values to be
1.1310 + * equivalent and equal.
1.1311 + *
1.1312 + * @param a the array to be searched
1.1313 + * @param key the value to be searched for
1.1314 + * @return index of the search key, if it is contained in the array;
1.1315 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.1316 + * <i>insertion point</i> is defined as the point at which the
1.1317 + * key would be inserted into the array: the index of the first
1.1318 + * element greater than the key, or <tt>a.length</tt> if all
1.1319 + * elements in the array are less than the specified key. Note
1.1320 + * that this guarantees that the return value will be >= 0 if
1.1321 + * and only if the key is found.
1.1322 + */
1.1323 + public static int binarySearch(float[] a, float key) {
1.1324 + return binarySearch0(a, 0, a.length, key);
1.1325 + }
1.1326 +
1.1327 + /**
1.1328 + * Searches a range of
1.1329 + * the specified array of floats for the specified value using
1.1330 + * the binary search algorithm.
1.1331 + * The range must be sorted
1.1332 + * (as by the {@link #sort(float[], int, int)} method)
1.1333 + * prior to making this call. If
1.1334 + * it is not sorted, the results are undefined. If the range contains
1.1335 + * multiple elements with the specified value, there is no guarantee which
1.1336 + * one will be found. This method considers all NaN values to be
1.1337 + * equivalent and equal.
1.1338 + *
1.1339 + * @param a the array to be searched
1.1340 + * @param fromIndex the index of the first element (inclusive) to be
1.1341 + * searched
1.1342 + * @param toIndex the index of the last element (exclusive) to be searched
1.1343 + * @param key the value to be searched for
1.1344 + * @return index of the search key, if it is contained in the array
1.1345 + * within the specified range;
1.1346 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.1347 + * <i>insertion point</i> is defined as the point at which the
1.1348 + * key would be inserted into the array: the index of the first
1.1349 + * element in the range greater than the key,
1.1350 + * or <tt>toIndex</tt> if all
1.1351 + * elements in the range are less than the specified key. Note
1.1352 + * that this guarantees that the return value will be >= 0 if
1.1353 + * and only if the key is found.
1.1354 + * @throws IllegalArgumentException
1.1355 + * if {@code fromIndex > toIndex}
1.1356 + * @throws ArrayIndexOutOfBoundsException
1.1357 + * if {@code fromIndex < 0 or toIndex > a.length}
1.1358 + * @since 1.6
1.1359 + */
1.1360 + public static int binarySearch(float[] a, int fromIndex, int toIndex,
1.1361 + float key) {
1.1362 + rangeCheck(a.length, fromIndex, toIndex);
1.1363 + return binarySearch0(a, fromIndex, toIndex, key);
1.1364 + }
1.1365 +
1.1366 + // Like public version, but without range checks.
1.1367 + private static int binarySearch0(float[] a, int fromIndex, int toIndex,
1.1368 + float key) {
1.1369 + int low = fromIndex;
1.1370 + int high = toIndex - 1;
1.1371 +
1.1372 + while (low <= high) {
1.1373 + int mid = (low + high) >>> 1;
1.1374 + float midVal = a[mid];
1.1375 +
1.1376 + if (midVal < key)
1.1377 + low = mid + 1; // Neither val is NaN, thisVal is smaller
1.1378 + else if (midVal > key)
1.1379 + high = mid - 1; // Neither val is NaN, thisVal is larger
1.1380 + else {
1.1381 + int midBits = Float.floatToIntBits(midVal);
1.1382 + int keyBits = Float.floatToIntBits(key);
1.1383 + if (midBits == keyBits) // Values are equal
1.1384 + return mid; // Key found
1.1385 + else if (midBits < keyBits) // (-0.0, 0.0) or (!NaN, NaN)
1.1386 + low = mid + 1;
1.1387 + else // (0.0, -0.0) or (NaN, !NaN)
1.1388 + high = mid - 1;
1.1389 + }
1.1390 + }
1.1391 + return -(low + 1); // key not found.
1.1392 + }
1.1393 +
1.1394 + /**
1.1395 + * Searches the specified array for the specified object using the binary
1.1396 + * search algorithm. The array must be sorted into ascending order
1.1397 + * according to the
1.1398 + * {@linkplain Comparable natural ordering}
1.1399 + * of its elements (as by the
1.1400 + * {@link #sort(Object[])} method) prior to making this call.
1.1401 + * If it is not sorted, the results are undefined.
1.1402 + * (If the array contains elements that are not mutually comparable (for
1.1403 + * example, strings and integers), it <i>cannot</i> be sorted according
1.1404 + * to the natural ordering of its elements, hence results are undefined.)
1.1405 + * If the array contains multiple
1.1406 + * elements equal to the specified object, there is no guarantee which
1.1407 + * one will be found.
1.1408 + *
1.1409 + * @param a the array to be searched
1.1410 + * @param key the value to be searched for
1.1411 + * @return index of the search key, if it is contained in the array;
1.1412 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.1413 + * <i>insertion point</i> is defined as the point at which the
1.1414 + * key would be inserted into the array: the index of the first
1.1415 + * element greater than the key, or <tt>a.length</tt> if all
1.1416 + * elements in the array are less than the specified key. Note
1.1417 + * that this guarantees that the return value will be >= 0 if
1.1418 + * and only if the key is found.
1.1419 + * @throws ClassCastException if the search key is not comparable to the
1.1420 + * elements of the array.
1.1421 + */
1.1422 + public static int binarySearch(Object[] a, Object key) {
1.1423 + return binarySearch0(a, 0, a.length, key);
1.1424 + }
1.1425 +
1.1426 + /**
1.1427 + * Searches a range of
1.1428 + * the specified array for the specified object using the binary
1.1429 + * search algorithm.
1.1430 + * The range must be sorted into ascending order
1.1431 + * according to the
1.1432 + * {@linkplain Comparable natural ordering}
1.1433 + * of its elements (as by the
1.1434 + * {@link #sort(Object[], int, int)} method) prior to making this
1.1435 + * call. If it is not sorted, the results are undefined.
1.1436 + * (If the range contains elements that are not mutually comparable (for
1.1437 + * example, strings and integers), it <i>cannot</i> be sorted according
1.1438 + * to the natural ordering of its elements, hence results are undefined.)
1.1439 + * If the range contains multiple
1.1440 + * elements equal to the specified object, there is no guarantee which
1.1441 + * one will be found.
1.1442 + *
1.1443 + * @param a the array to be searched
1.1444 + * @param fromIndex the index of the first element (inclusive) to be
1.1445 + * searched
1.1446 + * @param toIndex the index of the last element (exclusive) to be searched
1.1447 + * @param key the value to be searched for
1.1448 + * @return index of the search key, if it is contained in the array
1.1449 + * within the specified range;
1.1450 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.1451 + * <i>insertion point</i> is defined as the point at which the
1.1452 + * key would be inserted into the array: the index of the first
1.1453 + * element in the range greater than the key,
1.1454 + * or <tt>toIndex</tt> if all
1.1455 + * elements in the range are less than the specified key. Note
1.1456 + * that this guarantees that the return value will be >= 0 if
1.1457 + * and only if the key is found.
1.1458 + * @throws ClassCastException if the search key is not comparable to the
1.1459 + * elements of the array within the specified range.
1.1460 + * @throws IllegalArgumentException
1.1461 + * if {@code fromIndex > toIndex}
1.1462 + * @throws ArrayIndexOutOfBoundsException
1.1463 + * if {@code fromIndex < 0 or toIndex > a.length}
1.1464 + * @since 1.6
1.1465 + */
1.1466 + public static int binarySearch(Object[] a, int fromIndex, int toIndex,
1.1467 + Object key) {
1.1468 + rangeCheck(a.length, fromIndex, toIndex);
1.1469 + return binarySearch0(a, fromIndex, toIndex, key);
1.1470 + }
1.1471 +
1.1472 + // Like public version, but without range checks.
1.1473 + private static int binarySearch0(Object[] a, int fromIndex, int toIndex,
1.1474 + Object key) {
1.1475 + int low = fromIndex;
1.1476 + int high = toIndex - 1;
1.1477 +
1.1478 + while (low <= high) {
1.1479 + int mid = (low + high) >>> 1;
1.1480 + Comparable midVal = (Comparable)a[mid];
1.1481 + int cmp = midVal.compareTo(key);
1.1482 +
1.1483 + if (cmp < 0)
1.1484 + low = mid + 1;
1.1485 + else if (cmp > 0)
1.1486 + high = mid - 1;
1.1487 + else
1.1488 + return mid; // key found
1.1489 + }
1.1490 + return -(low + 1); // key not found.
1.1491 + }
1.1492 +
1.1493 + /**
1.1494 + * Searches the specified array for the specified object using the binary
1.1495 + * search algorithm. The array must be sorted into ascending order
1.1496 + * according to the specified comparator (as by the
1.1497 + * {@link #sort(Object[], Comparator) sort(T[], Comparator)}
1.1498 + * method) prior to making this call. If it is
1.1499 + * not sorted, the results are undefined.
1.1500 + * If the array contains multiple
1.1501 + * elements equal to the specified object, there is no guarantee which one
1.1502 + * will be found.
1.1503 + *
1.1504 + * @param a the array to be searched
1.1505 + * @param key the value to be searched for
1.1506 + * @param c the comparator by which the array is ordered. A
1.1507 + * <tt>null</tt> value indicates that the elements'
1.1508 + * {@linkplain Comparable natural ordering} should be used.
1.1509 + * @return index of the search key, if it is contained in the array;
1.1510 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.1511 + * <i>insertion point</i> is defined as the point at which the
1.1512 + * key would be inserted into the array: the index of the first
1.1513 + * element greater than the key, or <tt>a.length</tt> if all
1.1514 + * elements in the array are less than the specified key. Note
1.1515 + * that this guarantees that the return value will be >= 0 if
1.1516 + * and only if the key is found.
1.1517 + * @throws ClassCastException if the array contains elements that are not
1.1518 + * <i>mutually comparable</i> using the specified comparator,
1.1519 + * or the search key is not comparable to the
1.1520 + * elements of the array using this comparator.
1.1521 + */
1.1522 + public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c) {
1.1523 + return binarySearch0(a, 0, a.length, key, c);
1.1524 + }
1.1525 +
1.1526 + /**
1.1527 + * Searches a range of
1.1528 + * the specified array for the specified object using the binary
1.1529 + * search algorithm.
1.1530 + * The range must be sorted into ascending order
1.1531 + * according to the specified comparator (as by the
1.1532 + * {@link #sort(Object[], int, int, Comparator)
1.1533 + * sort(T[], int, int, Comparator)}
1.1534 + * method) prior to making this call.
1.1535 + * If it is not sorted, the results are undefined.
1.1536 + * If the range contains multiple elements equal to the specified object,
1.1537 + * there is no guarantee which one will be found.
1.1538 + *
1.1539 + * @param a the array to be searched
1.1540 + * @param fromIndex the index of the first element (inclusive) to be
1.1541 + * searched
1.1542 + * @param toIndex the index of the last element (exclusive) to be searched
1.1543 + * @param key the value to be searched for
1.1544 + * @param c the comparator by which the array is ordered. A
1.1545 + * <tt>null</tt> value indicates that the elements'
1.1546 + * {@linkplain Comparable natural ordering} should be used.
1.1547 + * @return index of the search key, if it is contained in the array
1.1548 + * within the specified range;
1.1549 + * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1.1550 + * <i>insertion point</i> is defined as the point at which the
1.1551 + * key would be inserted into the array: the index of the first
1.1552 + * element in the range greater than the key,
1.1553 + * or <tt>toIndex</tt> if all
1.1554 + * elements in the range are less than the specified key. Note
1.1555 + * that this guarantees that the return value will be >= 0 if
1.1556 + * and only if the key is found.
1.1557 + * @throws ClassCastException if the range contains elements that are not
1.1558 + * <i>mutually comparable</i> using the specified comparator,
1.1559 + * or the search key is not comparable to the
1.1560 + * elements in the range using this comparator.
1.1561 + * @throws IllegalArgumentException
1.1562 + * if {@code fromIndex > toIndex}
1.1563 + * @throws ArrayIndexOutOfBoundsException
1.1564 + * if {@code fromIndex < 0 or toIndex > a.length}
1.1565 + * @since 1.6
1.1566 + */
1.1567 + public static <T> int binarySearch(T[] a, int fromIndex, int toIndex,
1.1568 + T key, Comparator<? super T> c) {
1.1569 + rangeCheck(a.length, fromIndex, toIndex);
1.1570 + return binarySearch0(a, fromIndex, toIndex, key, c);
1.1571 + }
1.1572 +
1.1573 + // Like public version, but without range checks.
1.1574 + private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex,
1.1575 + T key, Comparator<? super T> c) {
1.1576 + if (c == null) {
1.1577 + return binarySearch0(a, fromIndex, toIndex, key);
1.1578 + }
1.1579 + int low = fromIndex;
1.1580 + int high = toIndex - 1;
1.1581 +
1.1582 + while (low <= high) {
1.1583 + int mid = (low + high) >>> 1;
1.1584 + T midVal = a[mid];
1.1585 + int cmp = c.compare(midVal, key);
1.1586 + if (cmp < 0)
1.1587 + low = mid + 1;
1.1588 + else if (cmp > 0)
1.1589 + high = mid - 1;
1.1590 + else
1.1591 + return mid; // key found
1.1592 + }
1.1593 + return -(low + 1); // key not found.
1.1594 + }
1.1595 +
1.1596 + // Equality Testing
1.1597 +
1.1598 + /**
1.1599 + * Returns <tt>true</tt> if the two specified arrays of longs are
1.1600 + * <i>equal</i> to one another. Two arrays are considered equal if both
1.1601 + * arrays contain the same number of elements, and all corresponding pairs
1.1602 + * of elements in the two arrays are equal. In other words, two arrays
1.1603 + * are equal if they contain the same elements in the same order. Also,
1.1604 + * two array references are considered equal if both are <tt>null</tt>.<p>
1.1605 + *
1.1606 + * @param a one array to be tested for equality
1.1607 + * @param a2 the other array to be tested for equality
1.1608 + * @return <tt>true</tt> if the two arrays are equal
1.1609 + */
1.1610 + public static boolean equals(long[] a, long[] a2) {
1.1611 + if (a==a2)
1.1612 + return true;
1.1613 + if (a==null || a2==null)
1.1614 + return false;
1.1615 +
1.1616 + int length = a.length;
1.1617 + if (a2.length != length)
1.1618 + return false;
1.1619 +
1.1620 + for (int i=0; i<length; i++)
1.1621 + if (a[i] != a2[i])
1.1622 + return false;
1.1623 +
1.1624 + return true;
1.1625 + }
1.1626 +
1.1627 + /**
1.1628 + * Returns <tt>true</tt> if the two specified arrays of ints are
1.1629 + * <i>equal</i> to one another. Two arrays are considered equal if both
1.1630 + * arrays contain the same number of elements, and all corresponding pairs
1.1631 + * of elements in the two arrays are equal. In other words, two arrays
1.1632 + * are equal if they contain the same elements in the same order. Also,
1.1633 + * two array references are considered equal if both are <tt>null</tt>.<p>
1.1634 + *
1.1635 + * @param a one array to be tested for equality
1.1636 + * @param a2 the other array to be tested for equality
1.1637 + * @return <tt>true</tt> if the two arrays are equal
1.1638 + */
1.1639 + public static boolean equals(int[] a, int[] a2) {
1.1640 + if (a==a2)
1.1641 + return true;
1.1642 + if (a==null || a2==null)
1.1643 + return false;
1.1644 +
1.1645 + int length = a.length;
1.1646 + if (a2.length != length)
1.1647 + return false;
1.1648 +
1.1649 + for (int i=0; i<length; i++)
1.1650 + if (a[i] != a2[i])
1.1651 + return false;
1.1652 +
1.1653 + return true;
1.1654 + }
1.1655 +
1.1656 + /**
1.1657 + * Returns <tt>true</tt> if the two specified arrays of shorts are
1.1658 + * <i>equal</i> to one another. Two arrays are considered equal if both
1.1659 + * arrays contain the same number of elements, and all corresponding pairs
1.1660 + * of elements in the two arrays are equal. In other words, two arrays
1.1661 + * are equal if they contain the same elements in the same order. Also,
1.1662 + * two array references are considered equal if both are <tt>null</tt>.<p>
1.1663 + *
1.1664 + * @param a one array to be tested for equality
1.1665 + * @param a2 the other array to be tested for equality
1.1666 + * @return <tt>true</tt> if the two arrays are equal
1.1667 + */
1.1668 + public static boolean equals(short[] a, short a2[]) {
1.1669 + if (a==a2)
1.1670 + return true;
1.1671 + if (a==null || a2==null)
1.1672 + return false;
1.1673 +
1.1674 + int length = a.length;
1.1675 + if (a2.length != length)
1.1676 + return false;
1.1677 +
1.1678 + for (int i=0; i<length; i++)
1.1679 + if (a[i] != a2[i])
1.1680 + return false;
1.1681 +
1.1682 + return true;
1.1683 + }
1.1684 +
1.1685 + /**
1.1686 + * Returns <tt>true</tt> if the two specified arrays of chars are
1.1687 + * <i>equal</i> to one another. Two arrays are considered equal if both
1.1688 + * arrays contain the same number of elements, and all corresponding pairs
1.1689 + * of elements in the two arrays are equal. In other words, two arrays
1.1690 + * are equal if they contain the same elements in the same order. Also,
1.1691 + * two array references are considered equal if both are <tt>null</tt>.<p>
1.1692 + *
1.1693 + * @param a one array to be tested for equality
1.1694 + * @param a2 the other array to be tested for equality
1.1695 + * @return <tt>true</tt> if the two arrays are equal
1.1696 + */
1.1697 + public static boolean equals(char[] a, char[] a2) {
1.1698 + if (a==a2)
1.1699 + return true;
1.1700 + if (a==null || a2==null)
1.1701 + return false;
1.1702 +
1.1703 + int length = a.length;
1.1704 + if (a2.length != length)
1.1705 + return false;
1.1706 +
1.1707 + for (int i=0; i<length; i++)
1.1708 + if (a[i] != a2[i])
1.1709 + return false;
1.1710 +
1.1711 + return true;
1.1712 + }
1.1713 +
1.1714 + /**
1.1715 + * Returns <tt>true</tt> if the two specified arrays of bytes are
1.1716 + * <i>equal</i> to one another. Two arrays are considered equal if both
1.1717 + * arrays contain the same number of elements, and all corresponding pairs
1.1718 + * of elements in the two arrays are equal. In other words, two arrays
1.1719 + * are equal if they contain the same elements in the same order. Also,
1.1720 + * two array references are considered equal if both are <tt>null</tt>.<p>
1.1721 + *
1.1722 + * @param a one array to be tested for equality
1.1723 + * @param a2 the other array to be tested for equality
1.1724 + * @return <tt>true</tt> if the two arrays are equal
1.1725 + */
1.1726 + public static boolean equals(byte[] a, byte[] a2) {
1.1727 + if (a==a2)
1.1728 + return true;
1.1729 + if (a==null || a2==null)
1.1730 + return false;
1.1731 +
1.1732 + int length = a.length;
1.1733 + if (a2.length != length)
1.1734 + return false;
1.1735 +
1.1736 + for (int i=0; i<length; i++)
1.1737 + if (a[i] != a2[i])
1.1738 + return false;
1.1739 +
1.1740 + return true;
1.1741 + }
1.1742 +
1.1743 + /**
1.1744 + * Returns <tt>true</tt> if the two specified arrays of booleans are
1.1745 + * <i>equal</i> to one another. Two arrays are considered equal if both
1.1746 + * arrays contain the same number of elements, and all corresponding pairs
1.1747 + * of elements in the two arrays are equal. In other words, two arrays
1.1748 + * are equal if they contain the same elements in the same order. Also,
1.1749 + * two array references are considered equal if both are <tt>null</tt>.<p>
1.1750 + *
1.1751 + * @param a one array to be tested for equality
1.1752 + * @param a2 the other array to be tested for equality
1.1753 + * @return <tt>true</tt> if the two arrays are equal
1.1754 + */
1.1755 + public static boolean equals(boolean[] a, boolean[] a2) {
1.1756 + if (a==a2)
1.1757 + return true;
1.1758 + if (a==null || a2==null)
1.1759 + return false;
1.1760 +
1.1761 + int length = a.length;
1.1762 + if (a2.length != length)
1.1763 + return false;
1.1764 +
1.1765 + for (int i=0; i<length; i++)
1.1766 + if (a[i] != a2[i])
1.1767 + return false;
1.1768 +
1.1769 + return true;
1.1770 + }
1.1771 +
1.1772 + /**
1.1773 + * Returns <tt>true</tt> if the two specified arrays of doubles are
1.1774 + * <i>equal</i> to one another. Two arrays are considered equal if both
1.1775 + * arrays contain the same number of elements, and all corresponding pairs
1.1776 + * of elements in the two arrays are equal. In other words, two arrays
1.1777 + * are equal if they contain the same elements in the same order. Also,
1.1778 + * two array references are considered equal if both are <tt>null</tt>.<p>
1.1779 + *
1.1780 + * Two doubles <tt>d1</tt> and <tt>d2</tt> are considered equal if:
1.1781 + * <pre> <tt>new Double(d1).equals(new Double(d2))</tt></pre>
1.1782 + * (Unlike the <tt>==</tt> operator, this method considers
1.1783 + * <tt>NaN</tt> equals to itself, and 0.0d unequal to -0.0d.)
1.1784 + *
1.1785 + * @param a one array to be tested for equality
1.1786 + * @param a2 the other array to be tested for equality
1.1787 + * @return <tt>true</tt> if the two arrays are equal
1.1788 + * @see Double#equals(Object)
1.1789 + */
1.1790 + public static boolean equals(double[] a, double[] a2) {
1.1791 + if (a==a2)
1.1792 + return true;
1.1793 + if (a==null || a2==null)
1.1794 + return false;
1.1795 +
1.1796 + int length = a.length;
1.1797 + if (a2.length != length)
1.1798 + return false;
1.1799 +
1.1800 + for (int i=0; i<length; i++)
1.1801 + if (Double.doubleToLongBits(a[i])!=Double.doubleToLongBits(a2[i]))
1.1802 + return false;
1.1803 +
1.1804 + return true;
1.1805 + }
1.1806 +
1.1807 + /**
1.1808 + * Returns <tt>true</tt> if the two specified arrays of floats are
1.1809 + * <i>equal</i> to one another. Two arrays are considered equal if both
1.1810 + * arrays contain the same number of elements, and all corresponding pairs
1.1811 + * of elements in the two arrays are equal. In other words, two arrays
1.1812 + * are equal if they contain the same elements in the same order. Also,
1.1813 + * two array references are considered equal if both are <tt>null</tt>.<p>
1.1814 + *
1.1815 + * Two floats <tt>f1</tt> and <tt>f2</tt> are considered equal if:
1.1816 + * <pre> <tt>new Float(f1).equals(new Float(f2))</tt></pre>
1.1817 + * (Unlike the <tt>==</tt> operator, this method considers
1.1818 + * <tt>NaN</tt> equals to itself, and 0.0f unequal to -0.0f.)
1.1819 + *
1.1820 + * @param a one array to be tested for equality
1.1821 + * @param a2 the other array to be tested for equality
1.1822 + * @return <tt>true</tt> if the two arrays are equal
1.1823 + * @see Float#equals(Object)
1.1824 + */
1.1825 + public static boolean equals(float[] a, float[] a2) {
1.1826 + if (a==a2)
1.1827 + return true;
1.1828 + if (a==null || a2==null)
1.1829 + return false;
1.1830 +
1.1831 + int length = a.length;
1.1832 + if (a2.length != length)
1.1833 + return false;
1.1834 +
1.1835 + for (int i=0; i<length; i++)
1.1836 + if (Float.floatToIntBits(a[i])!=Float.floatToIntBits(a2[i]))
1.1837 + return false;
1.1838 +
1.1839 + return true;
1.1840 + }
1.1841 +
1.1842 + /**
1.1843 + * Returns <tt>true</tt> if the two specified arrays of Objects are
1.1844 + * <i>equal</i> to one another. The two arrays are considered equal if
1.1845 + * both arrays contain the same number of elements, and all corresponding
1.1846 + * pairs of elements in the two arrays are equal. Two objects <tt>e1</tt>
1.1847 + * and <tt>e2</tt> are considered <i>equal</i> if <tt>(e1==null ? e2==null
1.1848 + * : e1.equals(e2))</tt>. In other words, the two arrays are equal if
1.1849 + * they contain the same elements in the same order. Also, two array
1.1850 + * references are considered equal if both are <tt>null</tt>.<p>
1.1851 + *
1.1852 + * @param a one array to be tested for equality
1.1853 + * @param a2 the other array to be tested for equality
1.1854 + * @return <tt>true</tt> if the two arrays are equal
1.1855 + */
1.1856 + public static boolean equals(Object[] a, Object[] a2) {
1.1857 + if (a==a2)
1.1858 + return true;
1.1859 + if (a==null || a2==null)
1.1860 + return false;
1.1861 +
1.1862 + int length = a.length;
1.1863 + if (a2.length != length)
1.1864 + return false;
1.1865 +
1.1866 + for (int i=0; i<length; i++) {
1.1867 + Object o1 = a[i];
1.1868 + Object o2 = a2[i];
1.1869 + if (!(o1==null ? o2==null : o1.equals(o2)))
1.1870 + return false;
1.1871 + }
1.1872 +
1.1873 + return true;
1.1874 + }
1.1875 +
1.1876 + // Filling
1.1877 +
1.1878 + /**
1.1879 + * Assigns the specified long value to each element of the specified array
1.1880 + * of longs.
1.1881 + *
1.1882 + * @param a the array to be filled
1.1883 + * @param val the value to be stored in all elements of the array
1.1884 + */
1.1885 + public static void fill(long[] a, long val) {
1.1886 + for (int i = 0, len = a.length; i < len; i++)
1.1887 + a[i] = val;
1.1888 + }
1.1889 +
1.1890 + /**
1.1891 + * Assigns the specified long value to each element of the specified
1.1892 + * range of the specified array of longs. The range to be filled
1.1893 + * extends from index <tt>fromIndex</tt>, inclusive, to index
1.1894 + * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
1.1895 + * range to be filled is empty.)
1.1896 + *
1.1897 + * @param a the array to be filled
1.1898 + * @param fromIndex the index of the first element (inclusive) to be
1.1899 + * filled with the specified value
1.1900 + * @param toIndex the index of the last element (exclusive) to be
1.1901 + * filled with the specified value
1.1902 + * @param val the value to be stored in all elements of the array
1.1903 + * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1.1904 + * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1.1905 + * <tt>toIndex > a.length</tt>
1.1906 + */
1.1907 + public static void fill(long[] a, int fromIndex, int toIndex, long val) {
1.1908 + rangeCheck(a.length, fromIndex, toIndex);
1.1909 + for (int i = fromIndex; i < toIndex; i++)
1.1910 + a[i] = val;
1.1911 + }
1.1912 +
1.1913 + /**
1.1914 + * Assigns the specified int value to each element of the specified array
1.1915 + * of ints.
1.1916 + *
1.1917 + * @param a the array to be filled
1.1918 + * @param val the value to be stored in all elements of the array
1.1919 + */
1.1920 + public static void fill(int[] a, int val) {
1.1921 + for (int i = 0, len = a.length; i < len; i++)
1.1922 + a[i] = val;
1.1923 + }
1.1924 +
1.1925 + /**
1.1926 + * Assigns the specified int value to each element of the specified
1.1927 + * range of the specified array of ints. The range to be filled
1.1928 + * extends from index <tt>fromIndex</tt>, inclusive, to index
1.1929 + * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
1.1930 + * range to be filled is empty.)
1.1931 + *
1.1932 + * @param a the array to be filled
1.1933 + * @param fromIndex the index of the first element (inclusive) to be
1.1934 + * filled with the specified value
1.1935 + * @param toIndex the index of the last element (exclusive) to be
1.1936 + * filled with the specified value
1.1937 + * @param val the value to be stored in all elements of the array
1.1938 + * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1.1939 + * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1.1940 + * <tt>toIndex > a.length</tt>
1.1941 + */
1.1942 + public static void fill(int[] a, int fromIndex, int toIndex, int val) {
1.1943 + rangeCheck(a.length, fromIndex, toIndex);
1.1944 + for (int i = fromIndex; i < toIndex; i++)
1.1945 + a[i] = val;
1.1946 + }
1.1947 +
1.1948 + /**
1.1949 + * Assigns the specified short value to each element of the specified array
1.1950 + * of shorts.
1.1951 + *
1.1952 + * @param a the array to be filled
1.1953 + * @param val the value to be stored in all elements of the array
1.1954 + */
1.1955 + public static void fill(short[] a, short val) {
1.1956 + for (int i = 0, len = a.length; i < len; i++)
1.1957 + a[i] = val;
1.1958 + }
1.1959 +
1.1960 + /**
1.1961 + * Assigns the specified short value to each element of the specified
1.1962 + * range of the specified array of shorts. The range to be filled
1.1963 + * extends from index <tt>fromIndex</tt>, inclusive, to index
1.1964 + * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
1.1965 + * range to be filled is empty.)
1.1966 + *
1.1967 + * @param a the array to be filled
1.1968 + * @param fromIndex the index of the first element (inclusive) to be
1.1969 + * filled with the specified value
1.1970 + * @param toIndex the index of the last element (exclusive) to be
1.1971 + * filled with the specified value
1.1972 + * @param val the value to be stored in all elements of the array
1.1973 + * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1.1974 + * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1.1975 + * <tt>toIndex > a.length</tt>
1.1976 + */
1.1977 + public static void fill(short[] a, int fromIndex, int toIndex, short val) {
1.1978 + rangeCheck(a.length, fromIndex, toIndex);
1.1979 + for (int i = fromIndex; i < toIndex; i++)
1.1980 + a[i] = val;
1.1981 + }
1.1982 +
1.1983 + /**
1.1984 + * Assigns the specified char value to each element of the specified array
1.1985 + * of chars.
1.1986 + *
1.1987 + * @param a the array to be filled
1.1988 + * @param val the value to be stored in all elements of the array
1.1989 + */
1.1990 + public static void fill(char[] a, char val) {
1.1991 + for (int i = 0, len = a.length; i < len; i++)
1.1992 + a[i] = val;
1.1993 + }
1.1994 +
1.1995 + /**
1.1996 + * Assigns the specified char value to each element of the specified
1.1997 + * range of the specified array of chars. The range to be filled
1.1998 + * extends from index <tt>fromIndex</tt>, inclusive, to index
1.1999 + * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
1.2000 + * range to be filled is empty.)
1.2001 + *
1.2002 + * @param a the array to be filled
1.2003 + * @param fromIndex the index of the first element (inclusive) to be
1.2004 + * filled with the specified value
1.2005 + * @param toIndex the index of the last element (exclusive) to be
1.2006 + * filled with the specified value
1.2007 + * @param val the value to be stored in all elements of the array
1.2008 + * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1.2009 + * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1.2010 + * <tt>toIndex > a.length</tt>
1.2011 + */
1.2012 + public static void fill(char[] a, int fromIndex, int toIndex, char val) {
1.2013 + rangeCheck(a.length, fromIndex, toIndex);
1.2014 + for (int i = fromIndex; i < toIndex; i++)
1.2015 + a[i] = val;
1.2016 + }
1.2017 +
1.2018 + /**
1.2019 + * Assigns the specified byte value to each element of the specified array
1.2020 + * of bytes.
1.2021 + *
1.2022 + * @param a the array to be filled
1.2023 + * @param val the value to be stored in all elements of the array
1.2024 + */
1.2025 + public static void fill(byte[] a, byte val) {
1.2026 + for (int i = 0, len = a.length; i < len; i++)
1.2027 + a[i] = val;
1.2028 + }
1.2029 +
1.2030 + /**
1.2031 + * Assigns the specified byte value to each element of the specified
1.2032 + * range of the specified array of bytes. The range to be filled
1.2033 + * extends from index <tt>fromIndex</tt>, inclusive, to index
1.2034 + * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
1.2035 + * range to be filled is empty.)
1.2036 + *
1.2037 + * @param a the array to be filled
1.2038 + * @param fromIndex the index of the first element (inclusive) to be
1.2039 + * filled with the specified value
1.2040 + * @param toIndex the index of the last element (exclusive) to be
1.2041 + * filled with the specified value
1.2042 + * @param val the value to be stored in all elements of the array
1.2043 + * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1.2044 + * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1.2045 + * <tt>toIndex > a.length</tt>
1.2046 + */
1.2047 + public static void fill(byte[] a, int fromIndex, int toIndex, byte val) {
1.2048 + rangeCheck(a.length, fromIndex, toIndex);
1.2049 + for (int i = fromIndex; i < toIndex; i++)
1.2050 + a[i] = val;
1.2051 + }
1.2052 +
1.2053 + /**
1.2054 + * Assigns the specified boolean value to each element of the specified
1.2055 + * array of booleans.
1.2056 + *
1.2057 + * @param a the array to be filled
1.2058 + * @param val the value to be stored in all elements of the array
1.2059 + */
1.2060 + public static void fill(boolean[] a, boolean val) {
1.2061 + for (int i = 0, len = a.length; i < len; i++)
1.2062 + a[i] = val;
1.2063 + }
1.2064 +
1.2065 + /**
1.2066 + * Assigns the specified boolean value to each element of the specified
1.2067 + * range of the specified array of booleans. The range to be filled
1.2068 + * extends from index <tt>fromIndex</tt>, inclusive, to index
1.2069 + * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
1.2070 + * range to be filled is empty.)
1.2071 + *
1.2072 + * @param a the array to be filled
1.2073 + * @param fromIndex the index of the first element (inclusive) to be
1.2074 + * filled with the specified value
1.2075 + * @param toIndex the index of the last element (exclusive) to be
1.2076 + * filled with the specified value
1.2077 + * @param val the value to be stored in all elements of the array
1.2078 + * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1.2079 + * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1.2080 + * <tt>toIndex > a.length</tt>
1.2081 + */
1.2082 + public static void fill(boolean[] a, int fromIndex, int toIndex,
1.2083 + boolean val) {
1.2084 + rangeCheck(a.length, fromIndex, toIndex);
1.2085 + for (int i = fromIndex; i < toIndex; i++)
1.2086 + a[i] = val;
1.2087 + }
1.2088 +
1.2089 + /**
1.2090 + * Assigns the specified double value to each element of the specified
1.2091 + * array of doubles.
1.2092 + *
1.2093 + * @param a the array to be filled
1.2094 + * @param val the value to be stored in all elements of the array
1.2095 + */
1.2096 + public static void fill(double[] a, double val) {
1.2097 + for (int i = 0, len = a.length; i < len; i++)
1.2098 + a[i] = val;
1.2099 + }
1.2100 +
1.2101 + /**
1.2102 + * Assigns the specified double value to each element of the specified
1.2103 + * range of the specified array of doubles. The range to be filled
1.2104 + * extends from index <tt>fromIndex</tt>, inclusive, to index
1.2105 + * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
1.2106 + * range to be filled is empty.)
1.2107 + *
1.2108 + * @param a the array to be filled
1.2109 + * @param fromIndex the index of the first element (inclusive) to be
1.2110 + * filled with the specified value
1.2111 + * @param toIndex the index of the last element (exclusive) to be
1.2112 + * filled with the specified value
1.2113 + * @param val the value to be stored in all elements of the array
1.2114 + * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1.2115 + * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1.2116 + * <tt>toIndex > a.length</tt>
1.2117 + */
1.2118 + public static void fill(double[] a, int fromIndex, int toIndex,double val){
1.2119 + rangeCheck(a.length, fromIndex, toIndex);
1.2120 + for (int i = fromIndex; i < toIndex; i++)
1.2121 + a[i] = val;
1.2122 + }
1.2123 +
1.2124 + /**
1.2125 + * Assigns the specified float value to each element of the specified array
1.2126 + * of floats.
1.2127 + *
1.2128 + * @param a the array to be filled
1.2129 + * @param val the value to be stored in all elements of the array
1.2130 + */
1.2131 + public static void fill(float[] a, float val) {
1.2132 + for (int i = 0, len = a.length; i < len; i++)
1.2133 + a[i] = val;
1.2134 + }
1.2135 +
1.2136 + /**
1.2137 + * Assigns the specified float value to each element of the specified
1.2138 + * range of the specified array of floats. The range to be filled
1.2139 + * extends from index <tt>fromIndex</tt>, inclusive, to index
1.2140 + * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
1.2141 + * range to be filled is empty.)
1.2142 + *
1.2143 + * @param a the array to be filled
1.2144 + * @param fromIndex the index of the first element (inclusive) to be
1.2145 + * filled with the specified value
1.2146 + * @param toIndex the index of the last element (exclusive) to be
1.2147 + * filled with the specified value
1.2148 + * @param val the value to be stored in all elements of the array
1.2149 + * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1.2150 + * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1.2151 + * <tt>toIndex > a.length</tt>
1.2152 + */
1.2153 + public static void fill(float[] a, int fromIndex, int toIndex, float val) {
1.2154 + rangeCheck(a.length, fromIndex, toIndex);
1.2155 + for (int i = fromIndex; i < toIndex; i++)
1.2156 + a[i] = val;
1.2157 + }
1.2158 +
1.2159 + /**
1.2160 + * Assigns the specified Object reference to each element of the specified
1.2161 + * array of Objects.
1.2162 + *
1.2163 + * @param a the array to be filled
1.2164 + * @param val the value to be stored in all elements of the array
1.2165 + * @throws ArrayStoreException if the specified value is not of a
1.2166 + * runtime type that can be stored in the specified array
1.2167 + */
1.2168 + public static void fill(Object[] a, Object val) {
1.2169 + for (int i = 0, len = a.length; i < len; i++)
1.2170 + a[i] = val;
1.2171 + }
1.2172 +
1.2173 + /**
1.2174 + * Assigns the specified Object reference to each element of the specified
1.2175 + * range of the specified array of Objects. The range to be filled
1.2176 + * extends from index <tt>fromIndex</tt>, inclusive, to index
1.2177 + * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
1.2178 + * range to be filled is empty.)
1.2179 + *
1.2180 + * @param a the array to be filled
1.2181 + * @param fromIndex the index of the first element (inclusive) to be
1.2182 + * filled with the specified value
1.2183 + * @param toIndex the index of the last element (exclusive) to be
1.2184 + * filled with the specified value
1.2185 + * @param val the value to be stored in all elements of the array
1.2186 + * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1.2187 + * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1.2188 + * <tt>toIndex > a.length</tt>
1.2189 + * @throws ArrayStoreException if the specified value is not of a
1.2190 + * runtime type that can be stored in the specified array
1.2191 + */
1.2192 + public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
1.2193 + rangeCheck(a.length, fromIndex, toIndex);
1.2194 + for (int i = fromIndex; i < toIndex; i++)
1.2195 + a[i] = val;
1.2196 + }
1.2197 +
1.2198 + // Cloning
1.2199 +
1.2200 + /**
1.2201 + * Copies the specified array, truncating or padding with nulls (if necessary)
1.2202 + * so the copy has the specified length. For all indices that are
1.2203 + * valid in both the original array and the copy, the two arrays will
1.2204 + * contain identical values. For any indices that are valid in the
1.2205 + * copy but not the original, the copy will contain <tt>null</tt>.
1.2206 + * Such indices will exist if and only if the specified length
1.2207 + * is greater than that of the original array.
1.2208 + * The resulting array is of exactly the same class as the original array.
1.2209 + *
1.2210 + * @param original the array to be copied
1.2211 + * @param newLength the length of the copy to be returned
1.2212 + * @return a copy of the original array, truncated or padded with nulls
1.2213 + * to obtain the specified length
1.2214 + * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
1.2215 + * @throws NullPointerException if <tt>original</tt> is null
1.2216 + * @since 1.6
1.2217 + */
1.2218 + public static <T> T[] copyOf(T[] original, int newLength) {
1.2219 + return (T[]) copyOf(original, newLength, original.getClass());
1.2220 + }
1.2221 +
1.2222 + /**
1.2223 + * Copies the specified array, truncating or padding with nulls (if necessary)
1.2224 + * so the copy has the specified length. For all indices that are
1.2225 + * valid in both the original array and the copy, the two arrays will
1.2226 + * contain identical values. For any indices that are valid in the
1.2227 + * copy but not the original, the copy will contain <tt>null</tt>.
1.2228 + * Such indices will exist if and only if the specified length
1.2229 + * is greater than that of the original array.
1.2230 + * The resulting array is of the class <tt>newType</tt>.
1.2231 + *
1.2232 + * @param original the array to be copied
1.2233 + * @param newLength the length of the copy to be returned
1.2234 + * @param newType the class of the copy to be returned
1.2235 + * @return a copy of the original array, truncated or padded with nulls
1.2236 + * to obtain the specified length
1.2237 + * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
1.2238 + * @throws NullPointerException if <tt>original</tt> is null
1.2239 + * @throws ArrayStoreException if an element copied from
1.2240 + * <tt>original</tt> is not of a runtime type that can be stored in
1.2241 + * an array of class <tt>newType</tt>
1.2242 + * @since 1.6
1.2243 + */
1.2244 + public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
1.2245 + T[] copy = ((Object)newType == (Object)Object[].class)
1.2246 + ? (T[]) new Object[newLength]
1.2247 + : (T[]) Array.newInstance(newType.getComponentType(), newLength);
1.2248 + System.arraycopy(original, 0, copy, 0,
1.2249 + Math.min(original.length, newLength));
1.2250 + return copy;
1.2251 + }
1.2252 +
1.2253 + /**
1.2254 + * Copies the specified array, truncating or padding with zeros (if necessary)
1.2255 + * so the copy has the specified length. For all indices that are
1.2256 + * valid in both the original array and the copy, the two arrays will
1.2257 + * contain identical values. For any indices that are valid in the
1.2258 + * copy but not the original, the copy will contain <tt>(byte)0</tt>.
1.2259 + * Such indices will exist if and only if the specified length
1.2260 + * is greater than that of the original array.
1.2261 + *
1.2262 + * @param original the array to be copied
1.2263 + * @param newLength the length of the copy to be returned
1.2264 + * @return a copy of the original array, truncated or padded with zeros
1.2265 + * to obtain the specified length
1.2266 + * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
1.2267 + * @throws NullPointerException if <tt>original</tt> is null
1.2268 + * @since 1.6
1.2269 + */
1.2270 + public static byte[] copyOf(byte[] original, int newLength) {
1.2271 + byte[] copy = new byte[newLength];
1.2272 + System.arraycopy(original, 0, copy, 0,
1.2273 + Math.min(original.length, newLength));
1.2274 + return copy;
1.2275 + }
1.2276 +
1.2277 + /**
1.2278 + * Copies the specified array, truncating or padding with zeros (if necessary)
1.2279 + * so the copy has the specified length. For all indices that are
1.2280 + * valid in both the original array and the copy, the two arrays will
1.2281 + * contain identical values. For any indices that are valid in the
1.2282 + * copy but not the original, the copy will contain <tt>(short)0</tt>.
1.2283 + * Such indices will exist if and only if the specified length
1.2284 + * is greater than that of the original array.
1.2285 + *
1.2286 + * @param original the array to be copied
1.2287 + * @param newLength the length of the copy to be returned
1.2288 + * @return a copy of the original array, truncated or padded with zeros
1.2289 + * to obtain the specified length
1.2290 + * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
1.2291 + * @throws NullPointerException if <tt>original</tt> is null
1.2292 + * @since 1.6
1.2293 + */
1.2294 + public static short[] copyOf(short[] original, int newLength) {
1.2295 + short[] copy = new short[newLength];
1.2296 + System.arraycopy(original, 0, copy, 0,
1.2297 + Math.min(original.length, newLength));
1.2298 + return copy;
1.2299 + }
1.2300 +
1.2301 + /**
1.2302 + * Copies the specified array, truncating or padding with zeros (if necessary)
1.2303 + * so the copy has the specified length. For all indices that are
1.2304 + * valid in both the original array and the copy, the two arrays will
1.2305 + * contain identical values. For any indices that are valid in the
1.2306 + * copy but not the original, the copy will contain <tt>0</tt>.
1.2307 + * Such indices will exist if and only if the specified length
1.2308 + * is greater than that of the original array.
1.2309 + *
1.2310 + * @param original the array to be copied
1.2311 + * @param newLength the length of the copy to be returned
1.2312 + * @return a copy of the original array, truncated or padded with zeros
1.2313 + * to obtain the specified length
1.2314 + * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
1.2315 + * @throws NullPointerException if <tt>original</tt> is null
1.2316 + * @since 1.6
1.2317 + */
1.2318 + public static int[] copyOf(int[] original, int newLength) {
1.2319 + int[] copy = new int[newLength];
1.2320 + System.arraycopy(original, 0, copy, 0,
1.2321 + Math.min(original.length, newLength));
1.2322 + return copy;
1.2323 + }
1.2324 +
1.2325 + /**
1.2326 + * Copies the specified array, truncating or padding with zeros (if necessary)
1.2327 + * so the copy has the specified length. For all indices that are
1.2328 + * valid in both the original array and the copy, the two arrays will
1.2329 + * contain identical values. For any indices that are valid in the
1.2330 + * copy but not the original, the copy will contain <tt>0L</tt>.
1.2331 + * Such indices will exist if and only if the specified length
1.2332 + * is greater than that of the original array.
1.2333 + *
1.2334 + * @param original the array to be copied
1.2335 + * @param newLength the length of the copy to be returned
1.2336 + * @return a copy of the original array, truncated or padded with zeros
1.2337 + * to obtain the specified length
1.2338 + * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
1.2339 + * @throws NullPointerException if <tt>original</tt> is null
1.2340 + * @since 1.6
1.2341 + */
1.2342 + public static long[] copyOf(long[] original, int newLength) {
1.2343 + long[] copy = new long[newLength];
1.2344 + System.arraycopy(original, 0, copy, 0,
1.2345 + Math.min(original.length, newLength));
1.2346 + return copy;
1.2347 + }
1.2348 +
1.2349 + /**
1.2350 + * Copies the specified array, truncating or padding with null characters (if necessary)
1.2351 + * so the copy has the specified length. For all indices that are valid
1.2352 + * in both the original array and the copy, the two arrays will contain
1.2353 + * identical values. For any indices that are valid in the copy but not
1.2354 + * the original, the copy will contain <tt>'\\u000'</tt>. Such indices
1.2355 + * will exist if and only if the specified length is greater than that of
1.2356 + * the original array.
1.2357 + *
1.2358 + * @param original the array to be copied
1.2359 + * @param newLength the length of the copy to be returned
1.2360 + * @return a copy of the original array, truncated or padded with null characters
1.2361 + * to obtain the specified length
1.2362 + * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
1.2363 + * @throws NullPointerException if <tt>original</tt> is null
1.2364 + * @since 1.6
1.2365 + */
1.2366 + public static char[] copyOf(char[] original, int newLength) {
1.2367 + char[] copy = new char[newLength];
1.2368 + System.arraycopy(original, 0, copy, 0,
1.2369 + Math.min(original.length, newLength));
1.2370 + return copy;
1.2371 + }
1.2372 +
1.2373 + /**
1.2374 + * Copies the specified array, truncating or padding with zeros (if necessary)
1.2375 + * so the copy has the specified length. For all indices that are
1.2376 + * valid in both the original array and the copy, the two arrays will
1.2377 + * contain identical values. For any indices that are valid in the
1.2378 + * copy but not the original, the copy will contain <tt>0f</tt>.
1.2379 + * Such indices will exist if and only if the specified length
1.2380 + * is greater than that of the original array.
1.2381 + *
1.2382 + * @param original the array to be copied
1.2383 + * @param newLength the length of the copy to be returned
1.2384 + * @return a copy of the original array, truncated or padded with zeros
1.2385 + * to obtain the specified length
1.2386 + * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
1.2387 + * @throws NullPointerException if <tt>original</tt> is null
1.2388 + * @since 1.6
1.2389 + */
1.2390 + public static float[] copyOf(float[] original, int newLength) {
1.2391 + float[] copy = new float[newLength];
1.2392 + System.arraycopy(original, 0, copy, 0,
1.2393 + Math.min(original.length, newLength));
1.2394 + return copy;
1.2395 + }
1.2396 +
1.2397 + /**
1.2398 + * Copies the specified array, truncating or padding with zeros (if necessary)
1.2399 + * so the copy has the specified length. For all indices that are
1.2400 + * valid in both the original array and the copy, the two arrays will
1.2401 + * contain identical values. For any indices that are valid in the
1.2402 + * copy but not the original, the copy will contain <tt>0d</tt>.
1.2403 + * Such indices will exist if and only if the specified length
1.2404 + * is greater than that of the original array.
1.2405 + *
1.2406 + * @param original the array to be copied
1.2407 + * @param newLength the length of the copy to be returned
1.2408 + * @return a copy of the original array, truncated or padded with zeros
1.2409 + * to obtain the specified length
1.2410 + * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
1.2411 + * @throws NullPointerException if <tt>original</tt> is null
1.2412 + * @since 1.6
1.2413 + */
1.2414 + public static double[] copyOf(double[] original, int newLength) {
1.2415 + double[] copy = new double[newLength];
1.2416 + System.arraycopy(original, 0, copy, 0,
1.2417 + Math.min(original.length, newLength));
1.2418 + return copy;
1.2419 + }
1.2420 +
1.2421 + /**
1.2422 + * Copies the specified array, truncating or padding with <tt>false</tt> (if necessary)
1.2423 + * so the copy has the specified length. For all indices that are
1.2424 + * valid in both the original array and the copy, the two arrays will
1.2425 + * contain identical values. For any indices that are valid in the
1.2426 + * copy but not the original, the copy will contain <tt>false</tt>.
1.2427 + * Such indices will exist if and only if the specified length
1.2428 + * is greater than that of the original array.
1.2429 + *
1.2430 + * @param original the array to be copied
1.2431 + * @param newLength the length of the copy to be returned
1.2432 + * @return a copy of the original array, truncated or padded with false elements
1.2433 + * to obtain the specified length
1.2434 + * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
1.2435 + * @throws NullPointerException if <tt>original</tt> is null
1.2436 + * @since 1.6
1.2437 + */
1.2438 + public static boolean[] copyOf(boolean[] original, int newLength) {
1.2439 + boolean[] copy = new boolean[newLength];
1.2440 + System.arraycopy(original, 0, copy, 0,
1.2441 + Math.min(original.length, newLength));
1.2442 + return copy;
1.2443 + }
1.2444 +
1.2445 + /**
1.2446 + * Copies the specified range of the specified array into a new array.
1.2447 + * The initial index of the range (<tt>from</tt>) must lie between zero
1.2448 + * and <tt>original.length</tt>, inclusive. The value at
1.2449 + * <tt>original[from]</tt> is placed into the initial element of the copy
1.2450 + * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
1.2451 + * Values from subsequent elements in the original array are placed into
1.2452 + * subsequent elements in the copy. The final index of the range
1.2453 + * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
1.2454 + * may be greater than <tt>original.length</tt>, in which case
1.2455 + * <tt>null</tt> is placed in all elements of the copy whose index is
1.2456 + * greater than or equal to <tt>original.length - from</tt>. The length
1.2457 + * of the returned array will be <tt>to - from</tt>.
1.2458 + * <p>
1.2459 + * The resulting array is of exactly the same class as the original array.
1.2460 + *
1.2461 + * @param original the array from which a range is to be copied
1.2462 + * @param from the initial index of the range to be copied, inclusive
1.2463 + * @param to the final index of the range to be copied, exclusive.
1.2464 + * (This index may lie outside the array.)
1.2465 + * @return a new array containing the specified range from the original array,
1.2466 + * truncated or padded with nulls to obtain the required length
1.2467 + * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
1.2468 + * or {@code from > original.length}
1.2469 + * @throws IllegalArgumentException if <tt>from > to</tt>
1.2470 + * @throws NullPointerException if <tt>original</tt> is null
1.2471 + * @since 1.6
1.2472 + */
1.2473 + public static <T> T[] copyOfRange(T[] original, int from, int to) {
1.2474 + return copyOfRange(original, from, to, (Class<T[]>) original.getClass());
1.2475 + }
1.2476 +
1.2477 + /**
1.2478 + * Copies the specified range of the specified array into a new array.
1.2479 + * The initial index of the range (<tt>from</tt>) must lie between zero
1.2480 + * and <tt>original.length</tt>, inclusive. The value at
1.2481 + * <tt>original[from]</tt> is placed into the initial element of the copy
1.2482 + * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
1.2483 + * Values from subsequent elements in the original array are placed into
1.2484 + * subsequent elements in the copy. The final index of the range
1.2485 + * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
1.2486 + * may be greater than <tt>original.length</tt>, in which case
1.2487 + * <tt>null</tt> is placed in all elements of the copy whose index is
1.2488 + * greater than or equal to <tt>original.length - from</tt>. The length
1.2489 + * of the returned array will be <tt>to - from</tt>.
1.2490 + * The resulting array is of the class <tt>newType</tt>.
1.2491 + *
1.2492 + * @param original the array from which a range is to be copied
1.2493 + * @param from the initial index of the range to be copied, inclusive
1.2494 + * @param to the final index of the range to be copied, exclusive.
1.2495 + * (This index may lie outside the array.)
1.2496 + * @param newType the class of the copy to be returned
1.2497 + * @return a new array containing the specified range from the original array,
1.2498 + * truncated or padded with nulls to obtain the required length
1.2499 + * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
1.2500 + * or {@code from > original.length}
1.2501 + * @throws IllegalArgumentException if <tt>from > to</tt>
1.2502 + * @throws NullPointerException if <tt>original</tt> is null
1.2503 + * @throws ArrayStoreException if an element copied from
1.2504 + * <tt>original</tt> is not of a runtime type that can be stored in
1.2505 + * an array of class <tt>newType</tt>.
1.2506 + * @since 1.6
1.2507 + */
1.2508 + public static <T,U> T[] copyOfRange(U[] original, int from, int to, Class<? extends T[]> newType) {
1.2509 + int newLength = to - from;
1.2510 + if (newLength < 0)
1.2511 + throw new IllegalArgumentException(from + " > " + to);
1.2512 + T[] copy = ((Object)newType == (Object)Object[].class)
1.2513 + ? (T[]) new Object[newLength]
1.2514 + : (T[]) Array.newInstance(newType.getComponentType(), newLength);
1.2515 + System.arraycopy(original, from, copy, 0,
1.2516 + Math.min(original.length - from, newLength));
1.2517 + return copy;
1.2518 + }
1.2519 +
1.2520 + /**
1.2521 + * Copies the specified range of the specified array into a new array.
1.2522 + * The initial index of the range (<tt>from</tt>) must lie between zero
1.2523 + * and <tt>original.length</tt>, inclusive. The value at
1.2524 + * <tt>original[from]</tt> is placed into the initial element of the copy
1.2525 + * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
1.2526 + * Values from subsequent elements in the original array are placed into
1.2527 + * subsequent elements in the copy. The final index of the range
1.2528 + * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
1.2529 + * may be greater than <tt>original.length</tt>, in which case
1.2530 + * <tt>(byte)0</tt> is placed in all elements of the copy whose index is
1.2531 + * greater than or equal to <tt>original.length - from</tt>. The length
1.2532 + * of the returned array will be <tt>to - from</tt>.
1.2533 + *
1.2534 + * @param original the array from which a range is to be copied
1.2535 + * @param from the initial index of the range to be copied, inclusive
1.2536 + * @param to the final index of the range to be copied, exclusive.
1.2537 + * (This index may lie outside the array.)
1.2538 + * @return a new array containing the specified range from the original array,
1.2539 + * truncated or padded with zeros to obtain the required length
1.2540 + * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
1.2541 + * or {@code from > original.length}
1.2542 + * @throws IllegalArgumentException if <tt>from > to</tt>
1.2543 + * @throws NullPointerException if <tt>original</tt> is null
1.2544 + * @since 1.6
1.2545 + */
1.2546 + public static byte[] copyOfRange(byte[] original, int from, int to) {
1.2547 + int newLength = to - from;
1.2548 + if (newLength < 0)
1.2549 + throw new IllegalArgumentException(from + " > " + to);
1.2550 + byte[] copy = new byte[newLength];
1.2551 + System.arraycopy(original, from, copy, 0,
1.2552 + Math.min(original.length - from, newLength));
1.2553 + return copy;
1.2554 + }
1.2555 +
1.2556 + /**
1.2557 + * Copies the specified range of the specified array into a new array.
1.2558 + * The initial index of the range (<tt>from</tt>) must lie between zero
1.2559 + * and <tt>original.length</tt>, inclusive. The value at
1.2560 + * <tt>original[from]</tt> is placed into the initial element of the copy
1.2561 + * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
1.2562 + * Values from subsequent elements in the original array are placed into
1.2563 + * subsequent elements in the copy. The final index of the range
1.2564 + * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
1.2565 + * may be greater than <tt>original.length</tt>, in which case
1.2566 + * <tt>(short)0</tt> is placed in all elements of the copy whose index is
1.2567 + * greater than or equal to <tt>original.length - from</tt>. The length
1.2568 + * of the returned array will be <tt>to - from</tt>.
1.2569 + *
1.2570 + * @param original the array from which a range is to be copied
1.2571 + * @param from the initial index of the range to be copied, inclusive
1.2572 + * @param to the final index of the range to be copied, exclusive.
1.2573 + * (This index may lie outside the array.)
1.2574 + * @return a new array containing the specified range from the original array,
1.2575 + * truncated or padded with zeros to obtain the required length
1.2576 + * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
1.2577 + * or {@code from > original.length}
1.2578 + * @throws IllegalArgumentException if <tt>from > to</tt>
1.2579 + * @throws NullPointerException if <tt>original</tt> is null
1.2580 + * @since 1.6
1.2581 + */
1.2582 + public static short[] copyOfRange(short[] original, int from, int to) {
1.2583 + int newLength = to - from;
1.2584 + if (newLength < 0)
1.2585 + throw new IllegalArgumentException(from + " > " + to);
1.2586 + short[] copy = new short[newLength];
1.2587 + System.arraycopy(original, from, copy, 0,
1.2588 + Math.min(original.length - from, newLength));
1.2589 + return copy;
1.2590 + }
1.2591 +
1.2592 + /**
1.2593 + * Copies the specified range of the specified array into a new array.
1.2594 + * The initial index of the range (<tt>from</tt>) must lie between zero
1.2595 + * and <tt>original.length</tt>, inclusive. The value at
1.2596 + * <tt>original[from]</tt> is placed into the initial element of the copy
1.2597 + * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
1.2598 + * Values from subsequent elements in the original array are placed into
1.2599 + * subsequent elements in the copy. The final index of the range
1.2600 + * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
1.2601 + * may be greater than <tt>original.length</tt>, in which case
1.2602 + * <tt>0</tt> is placed in all elements of the copy whose index is
1.2603 + * greater than or equal to <tt>original.length - from</tt>. The length
1.2604 + * of the returned array will be <tt>to - from</tt>.
1.2605 + *
1.2606 + * @param original the array from which a range is to be copied
1.2607 + * @param from the initial index of the range to be copied, inclusive
1.2608 + * @param to the final index of the range to be copied, exclusive.
1.2609 + * (This index may lie outside the array.)
1.2610 + * @return a new array containing the specified range from the original array,
1.2611 + * truncated or padded with zeros to obtain the required length
1.2612 + * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
1.2613 + * or {@code from > original.length}
1.2614 + * @throws IllegalArgumentException if <tt>from > to</tt>
1.2615 + * @throws NullPointerException if <tt>original</tt> is null
1.2616 + * @since 1.6
1.2617 + */
1.2618 + public static int[] copyOfRange(int[] original, int from, int to) {
1.2619 + int newLength = to - from;
1.2620 + if (newLength < 0)
1.2621 + throw new IllegalArgumentException(from + " > " + to);
1.2622 + int[] copy = new int[newLength];
1.2623 + System.arraycopy(original, from, copy, 0,
1.2624 + Math.min(original.length - from, newLength));
1.2625 + return copy;
1.2626 + }
1.2627 +
1.2628 + /**
1.2629 + * Copies the specified range of the specified array into a new array.
1.2630 + * The initial index of the range (<tt>from</tt>) must lie between zero
1.2631 + * and <tt>original.length</tt>, inclusive. The value at
1.2632 + * <tt>original[from]</tt> is placed into the initial element of the copy
1.2633 + * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
1.2634 + * Values from subsequent elements in the original array are placed into
1.2635 + * subsequent elements in the copy. The final index of the range
1.2636 + * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
1.2637 + * may be greater than <tt>original.length</tt>, in which case
1.2638 + * <tt>0L</tt> is placed in all elements of the copy whose index is
1.2639 + * greater than or equal to <tt>original.length - from</tt>. The length
1.2640 + * of the returned array will be <tt>to - from</tt>.
1.2641 + *
1.2642 + * @param original the array from which a range is to be copied
1.2643 + * @param from the initial index of the range to be copied, inclusive
1.2644 + * @param to the final index of the range to be copied, exclusive.
1.2645 + * (This index may lie outside the array.)
1.2646 + * @return a new array containing the specified range from the original array,
1.2647 + * truncated or padded with zeros to obtain the required length
1.2648 + * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
1.2649 + * or {@code from > original.length}
1.2650 + * @throws IllegalArgumentException if <tt>from > to</tt>
1.2651 + * @throws NullPointerException if <tt>original</tt> is null
1.2652 + * @since 1.6
1.2653 + */
1.2654 + public static long[] copyOfRange(long[] original, int from, int to) {
1.2655 + int newLength = to - from;
1.2656 + if (newLength < 0)
1.2657 + throw new IllegalArgumentException(from + " > " + to);
1.2658 + long[] copy = new long[newLength];
1.2659 + System.arraycopy(original, from, copy, 0,
1.2660 + Math.min(original.length - from, newLength));
1.2661 + return copy;
1.2662 + }
1.2663 +
1.2664 + /**
1.2665 + * Copies the specified range of the specified array into a new array.
1.2666 + * The initial index of the range (<tt>from</tt>) must lie between zero
1.2667 + * and <tt>original.length</tt>, inclusive. The value at
1.2668 + * <tt>original[from]</tt> is placed into the initial element of the copy
1.2669 + * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
1.2670 + * Values from subsequent elements in the original array are placed into
1.2671 + * subsequent elements in the copy. The final index of the range
1.2672 + * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
1.2673 + * may be greater than <tt>original.length</tt>, in which case
1.2674 + * <tt>'\\u000'</tt> is placed in all elements of the copy whose index is
1.2675 + * greater than or equal to <tt>original.length - from</tt>. The length
1.2676 + * of the returned array will be <tt>to - from</tt>.
1.2677 + *
1.2678 + * @param original the array from which a range is to be copied
1.2679 + * @param from the initial index of the range to be copied, inclusive
1.2680 + * @param to the final index of the range to be copied, exclusive.
1.2681 + * (This index may lie outside the array.)
1.2682 + * @return a new array containing the specified range from the original array,
1.2683 + * truncated or padded with null characters to obtain the required length
1.2684 + * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
1.2685 + * or {@code from > original.length}
1.2686 + * @throws IllegalArgumentException if <tt>from > to</tt>
1.2687 + * @throws NullPointerException if <tt>original</tt> is null
1.2688 + * @since 1.6
1.2689 + */
1.2690 + public static char[] copyOfRange(char[] original, int from, int to) {
1.2691 + int newLength = to - from;
1.2692 + if (newLength < 0)
1.2693 + throw new IllegalArgumentException(from + " > " + to);
1.2694 + char[] copy = new char[newLength];
1.2695 + System.arraycopy(original, from, copy, 0,
1.2696 + Math.min(original.length - from, newLength));
1.2697 + return copy;
1.2698 + }
1.2699 +
1.2700 + /**
1.2701 + * Copies the specified range of the specified array into a new array.
1.2702 + * The initial index of the range (<tt>from</tt>) must lie between zero
1.2703 + * and <tt>original.length</tt>, inclusive. The value at
1.2704 + * <tt>original[from]</tt> is placed into the initial element of the copy
1.2705 + * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
1.2706 + * Values from subsequent elements in the original array are placed into
1.2707 + * subsequent elements in the copy. The final index of the range
1.2708 + * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
1.2709 + * may be greater than <tt>original.length</tt>, in which case
1.2710 + * <tt>0f</tt> is placed in all elements of the copy whose index is
1.2711 + * greater than or equal to <tt>original.length - from</tt>. The length
1.2712 + * of the returned array will be <tt>to - from</tt>.
1.2713 + *
1.2714 + * @param original the array from which a range is to be copied
1.2715 + * @param from the initial index of the range to be copied, inclusive
1.2716 + * @param to the final index of the range to be copied, exclusive.
1.2717 + * (This index may lie outside the array.)
1.2718 + * @return a new array containing the specified range from the original array,
1.2719 + * truncated or padded with zeros to obtain the required length
1.2720 + * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
1.2721 + * or {@code from > original.length}
1.2722 + * @throws IllegalArgumentException if <tt>from > to</tt>
1.2723 + * @throws NullPointerException if <tt>original</tt> is null
1.2724 + * @since 1.6
1.2725 + */
1.2726 + public static float[] copyOfRange(float[] original, int from, int to) {
1.2727 + int newLength = to - from;
1.2728 + if (newLength < 0)
1.2729 + throw new IllegalArgumentException(from + " > " + to);
1.2730 + float[] copy = new float[newLength];
1.2731 + System.arraycopy(original, from, copy, 0,
1.2732 + Math.min(original.length - from, newLength));
1.2733 + return copy;
1.2734 + }
1.2735 +
1.2736 + /**
1.2737 + * Copies the specified range of the specified array into a new array.
1.2738 + * The initial index of the range (<tt>from</tt>) must lie between zero
1.2739 + * and <tt>original.length</tt>, inclusive. The value at
1.2740 + * <tt>original[from]</tt> is placed into the initial element of the copy
1.2741 + * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
1.2742 + * Values from subsequent elements in the original array are placed into
1.2743 + * subsequent elements in the copy. The final index of the range
1.2744 + * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
1.2745 + * may be greater than <tt>original.length</tt>, in which case
1.2746 + * <tt>0d</tt> is placed in all elements of the copy whose index is
1.2747 + * greater than or equal to <tt>original.length - from</tt>. The length
1.2748 + * of the returned array will be <tt>to - from</tt>.
1.2749 + *
1.2750 + * @param original the array from which a range is to be copied
1.2751 + * @param from the initial index of the range to be copied, inclusive
1.2752 + * @param to the final index of the range to be copied, exclusive.
1.2753 + * (This index may lie outside the array.)
1.2754 + * @return a new array containing the specified range from the original array,
1.2755 + * truncated or padded with zeros to obtain the required length
1.2756 + * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
1.2757 + * or {@code from > original.length}
1.2758 + * @throws IllegalArgumentException if <tt>from > to</tt>
1.2759 + * @throws NullPointerException if <tt>original</tt> is null
1.2760 + * @since 1.6
1.2761 + */
1.2762 + public static double[] copyOfRange(double[] original, int from, int to) {
1.2763 + int newLength = to - from;
1.2764 + if (newLength < 0)
1.2765 + throw new IllegalArgumentException(from + " > " + to);
1.2766 + double[] copy = new double[newLength];
1.2767 + System.arraycopy(original, from, copy, 0,
1.2768 + Math.min(original.length - from, newLength));
1.2769 + return copy;
1.2770 + }
1.2771 +
1.2772 + /**
1.2773 + * Copies the specified range of the specified array into a new array.
1.2774 + * The initial index of the range (<tt>from</tt>) must lie between zero
1.2775 + * and <tt>original.length</tt>, inclusive. The value at
1.2776 + * <tt>original[from]</tt> is placed into the initial element of the copy
1.2777 + * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
1.2778 + * Values from subsequent elements in the original array are placed into
1.2779 + * subsequent elements in the copy. The final index of the range
1.2780 + * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
1.2781 + * may be greater than <tt>original.length</tt>, in which case
1.2782 + * <tt>false</tt> is placed in all elements of the copy whose index is
1.2783 + * greater than or equal to <tt>original.length - from</tt>. The length
1.2784 + * of the returned array will be <tt>to - from</tt>.
1.2785 + *
1.2786 + * @param original the array from which a range is to be copied
1.2787 + * @param from the initial index of the range to be copied, inclusive
1.2788 + * @param to the final index of the range to be copied, exclusive.
1.2789 + * (This index may lie outside the array.)
1.2790 + * @return a new array containing the specified range from the original array,
1.2791 + * truncated or padded with false elements to obtain the required length
1.2792 + * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
1.2793 + * or {@code from > original.length}
1.2794 + * @throws IllegalArgumentException if <tt>from > to</tt>
1.2795 + * @throws NullPointerException if <tt>original</tt> is null
1.2796 + * @since 1.6
1.2797 + */
1.2798 + public static boolean[] copyOfRange(boolean[] original, int from, int to) {
1.2799 + int newLength = to - from;
1.2800 + if (newLength < 0)
1.2801 + throw new IllegalArgumentException(from + " > " + to);
1.2802 + boolean[] copy = new boolean[newLength];
1.2803 + System.arraycopy(original, from, copy, 0,
1.2804 + Math.min(original.length - from, newLength));
1.2805 + return copy;
1.2806 + }
1.2807 +
1.2808 + // Misc
1.2809 +
1.2810 + /**
1.2811 + * Returns a fixed-size list backed by the specified array. (Changes to
1.2812 + * the returned list "write through" to the array.) This method acts
1.2813 + * as bridge between array-based and collection-based APIs, in
1.2814 + * combination with {@link Collection#toArray}. The returned list is
1.2815 + * serializable and implements {@link RandomAccess}.
1.2816 + *
1.2817 + * <p>This method also provides a convenient way to create a fixed-size
1.2818 + * list initialized to contain several elements:
1.2819 + * <pre>
1.2820 + * List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
1.2821 + * </pre>
1.2822 + *
1.2823 + * @param a the array by which the list will be backed
1.2824 + * @return a list view of the specified array
1.2825 + */
1.2826 + @SafeVarargs
1.2827 + public static <T> List<T> asList(T... a) {
1.2828 + return new ArrayList<>(a);
1.2829 + }
1.2830 +
1.2831 + /**
1.2832 + * @serial include
1.2833 + */
1.2834 + private static class ArrayList<E> extends AbstractList<E>
1.2835 + implements RandomAccess, java.io.Serializable
1.2836 + {
1.2837 + private static final long serialVersionUID = -2764017481108945198L;
1.2838 + private final E[] a;
1.2839 +
1.2840 + ArrayList(E[] array) {
1.2841 + if (array==null)
1.2842 + throw new NullPointerException();
1.2843 + a = array;
1.2844 + }
1.2845 +
1.2846 + public int size() {
1.2847 + return a.length;
1.2848 + }
1.2849 +
1.2850 + public Object[] toArray() {
1.2851 + return a.clone();
1.2852 + }
1.2853 +
1.2854 + public <T> T[] toArray(T[] a) {
1.2855 + int size = size();
1.2856 + if (a.length < size)
1.2857 + return Arrays.copyOf(this.a, size,
1.2858 + (Class<? extends T[]>) a.getClass());
1.2859 + System.arraycopy(this.a, 0, a, 0, size);
1.2860 + if (a.length > size)
1.2861 + a[size] = null;
1.2862 + return a;
1.2863 + }
1.2864 +
1.2865 + public E get(int index) {
1.2866 + return a[index];
1.2867 + }
1.2868 +
1.2869 + public E set(int index, E element) {
1.2870 + E oldValue = a[index];
1.2871 + a[index] = element;
1.2872 + return oldValue;
1.2873 + }
1.2874 +
1.2875 + public int indexOf(Object o) {
1.2876 + if (o==null) {
1.2877 + for (int i=0; i<a.length; i++)
1.2878 + if (a[i]==null)
1.2879 + return i;
1.2880 + } else {
1.2881 + for (int i=0; i<a.length; i++)
1.2882 + if (o.equals(a[i]))
1.2883 + return i;
1.2884 + }
1.2885 + return -1;
1.2886 + }
1.2887 +
1.2888 + public boolean contains(Object o) {
1.2889 + return indexOf(o) != -1;
1.2890 + }
1.2891 + }
1.2892 +
1.2893 + /**
1.2894 + * Returns a hash code based on the contents of the specified array.
1.2895 + * For any two <tt>long</tt> arrays <tt>a</tt> and <tt>b</tt>
1.2896 + * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
1.2897 + * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
1.2898 + *
1.2899 + * <p>The value returned by this method is the same value that would be
1.2900 + * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
1.2901 + * method on a {@link List} containing a sequence of {@link Long}
1.2902 + * instances representing the elements of <tt>a</tt> in the same order.
1.2903 + * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
1.2904 + *
1.2905 + * @param a the array whose hash value to compute
1.2906 + * @return a content-based hash code for <tt>a</tt>
1.2907 + * @since 1.5
1.2908 + */
1.2909 + public static int hashCode(long a[]) {
1.2910 + if (a == null)
1.2911 + return 0;
1.2912 +
1.2913 + int result = 1;
1.2914 + for (long element : a) {
1.2915 + int elementHash = (int)(element ^ (element >>> 32));
1.2916 + result = 31 * result + elementHash;
1.2917 + }
1.2918 +
1.2919 + return result;
1.2920 + }
1.2921 +
1.2922 + /**
1.2923 + * Returns a hash code based on the contents of the specified array.
1.2924 + * For any two non-null <tt>int</tt> arrays <tt>a</tt> and <tt>b</tt>
1.2925 + * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
1.2926 + * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
1.2927 + *
1.2928 + * <p>The value returned by this method is the same value that would be
1.2929 + * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
1.2930 + * method on a {@link List} containing a sequence of {@link Integer}
1.2931 + * instances representing the elements of <tt>a</tt> in the same order.
1.2932 + * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
1.2933 + *
1.2934 + * @param a the array whose hash value to compute
1.2935 + * @return a content-based hash code for <tt>a</tt>
1.2936 + * @since 1.5
1.2937 + */
1.2938 + public static int hashCode(int a[]) {
1.2939 + if (a == null)
1.2940 + return 0;
1.2941 +
1.2942 + int result = 1;
1.2943 + for (int element : a)
1.2944 + result = 31 * result + element;
1.2945 +
1.2946 + return result;
1.2947 + }
1.2948 +
1.2949 + /**
1.2950 + * Returns a hash code based on the contents of the specified array.
1.2951 + * For any two <tt>short</tt> arrays <tt>a</tt> and <tt>b</tt>
1.2952 + * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
1.2953 + * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
1.2954 + *
1.2955 + * <p>The value returned by this method is the same value that would be
1.2956 + * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
1.2957 + * method on a {@link List} containing a sequence of {@link Short}
1.2958 + * instances representing the elements of <tt>a</tt> in the same order.
1.2959 + * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
1.2960 + *
1.2961 + * @param a the array whose hash value to compute
1.2962 + * @return a content-based hash code for <tt>a</tt>
1.2963 + * @since 1.5
1.2964 + */
1.2965 + public static int hashCode(short a[]) {
1.2966 + if (a == null)
1.2967 + return 0;
1.2968 +
1.2969 + int result = 1;
1.2970 + for (short element : a)
1.2971 + result = 31 * result + element;
1.2972 +
1.2973 + return result;
1.2974 + }
1.2975 +
1.2976 + /**
1.2977 + * Returns a hash code based on the contents of the specified array.
1.2978 + * For any two <tt>char</tt> arrays <tt>a</tt> and <tt>b</tt>
1.2979 + * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
1.2980 + * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
1.2981 + *
1.2982 + * <p>The value returned by this method is the same value that would be
1.2983 + * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
1.2984 + * method on a {@link List} containing a sequence of {@link Character}
1.2985 + * instances representing the elements of <tt>a</tt> in the same order.
1.2986 + * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
1.2987 + *
1.2988 + * @param a the array whose hash value to compute
1.2989 + * @return a content-based hash code for <tt>a</tt>
1.2990 + * @since 1.5
1.2991 + */
1.2992 + public static int hashCode(char a[]) {
1.2993 + if (a == null)
1.2994 + return 0;
1.2995 +
1.2996 + int result = 1;
1.2997 + for (char element : a)
1.2998 + result = 31 * result + element;
1.2999 +
1.3000 + return result;
1.3001 + }
1.3002 +
1.3003 + /**
1.3004 + * Returns a hash code based on the contents of the specified array.
1.3005 + * For any two <tt>byte</tt> arrays <tt>a</tt> and <tt>b</tt>
1.3006 + * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
1.3007 + * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
1.3008 + *
1.3009 + * <p>The value returned by this method is the same value that would be
1.3010 + * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
1.3011 + * method on a {@link List} containing a sequence of {@link Byte}
1.3012 + * instances representing the elements of <tt>a</tt> in the same order.
1.3013 + * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
1.3014 + *
1.3015 + * @param a the array whose hash value to compute
1.3016 + * @return a content-based hash code for <tt>a</tt>
1.3017 + * @since 1.5
1.3018 + */
1.3019 + public static int hashCode(byte a[]) {
1.3020 + if (a == null)
1.3021 + return 0;
1.3022 +
1.3023 + int result = 1;
1.3024 + for (byte element : a)
1.3025 + result = 31 * result + element;
1.3026 +
1.3027 + return result;
1.3028 + }
1.3029 +
1.3030 + /**
1.3031 + * Returns a hash code based on the contents of the specified array.
1.3032 + * For any two <tt>boolean</tt> arrays <tt>a</tt> and <tt>b</tt>
1.3033 + * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
1.3034 + * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
1.3035 + *
1.3036 + * <p>The value returned by this method is the same value that would be
1.3037 + * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
1.3038 + * method on a {@link List} containing a sequence of {@link Boolean}
1.3039 + * instances representing the elements of <tt>a</tt> in the same order.
1.3040 + * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
1.3041 + *
1.3042 + * @param a the array whose hash value to compute
1.3043 + * @return a content-based hash code for <tt>a</tt>
1.3044 + * @since 1.5
1.3045 + */
1.3046 + public static int hashCode(boolean a[]) {
1.3047 + if (a == null)
1.3048 + return 0;
1.3049 +
1.3050 + int result = 1;
1.3051 + for (boolean element : a)
1.3052 + result = 31 * result + (element ? 1231 : 1237);
1.3053 +
1.3054 + return result;
1.3055 + }
1.3056 +
1.3057 + /**
1.3058 + * Returns a hash code based on the contents of the specified array.
1.3059 + * For any two <tt>float</tt> arrays <tt>a</tt> and <tt>b</tt>
1.3060 + * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
1.3061 + * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
1.3062 + *
1.3063 + * <p>The value returned by this method is the same value that would be
1.3064 + * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
1.3065 + * method on a {@link List} containing a sequence of {@link Float}
1.3066 + * instances representing the elements of <tt>a</tt> in the same order.
1.3067 + * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
1.3068 + *
1.3069 + * @param a the array whose hash value to compute
1.3070 + * @return a content-based hash code for <tt>a</tt>
1.3071 + * @since 1.5
1.3072 + */
1.3073 + public static int hashCode(float a[]) {
1.3074 + if (a == null)
1.3075 + return 0;
1.3076 +
1.3077 + int result = 1;
1.3078 + for (float element : a)
1.3079 + result = 31 * result + Float.floatToIntBits(element);
1.3080 +
1.3081 + return result;
1.3082 + }
1.3083 +
1.3084 + /**
1.3085 + * Returns a hash code based on the contents of the specified array.
1.3086 + * For any two <tt>double</tt> arrays <tt>a</tt> and <tt>b</tt>
1.3087 + * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
1.3088 + * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
1.3089 + *
1.3090 + * <p>The value returned by this method is the same value that would be
1.3091 + * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
1.3092 + * method on a {@link List} containing a sequence of {@link Double}
1.3093 + * instances representing the elements of <tt>a</tt> in the same order.
1.3094 + * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
1.3095 + *
1.3096 + * @param a the array whose hash value to compute
1.3097 + * @return a content-based hash code for <tt>a</tt>
1.3098 + * @since 1.5
1.3099 + */
1.3100 + public static int hashCode(double a[]) {
1.3101 + if (a == null)
1.3102 + return 0;
1.3103 +
1.3104 + int result = 1;
1.3105 + for (double element : a) {
1.3106 + long bits = Double.doubleToLongBits(element);
1.3107 + result = 31 * result + (int)(bits ^ (bits >>> 32));
1.3108 + }
1.3109 + return result;
1.3110 + }
1.3111 +
1.3112 + /**
1.3113 + * Returns a hash code based on the contents of the specified array. If
1.3114 + * the array contains other arrays as elements, the hash code is based on
1.3115 + * their identities rather than their contents. It is therefore
1.3116 + * acceptable to invoke this method on an array that contains itself as an
1.3117 + * element, either directly or indirectly through one or more levels of
1.3118 + * arrays.
1.3119 + *
1.3120 + * <p>For any two arrays <tt>a</tt> and <tt>b</tt> such that
1.3121 + * <tt>Arrays.equals(a, b)</tt>, it is also the case that
1.3122 + * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
1.3123 + *
1.3124 + * <p>The value returned by this method is equal to the value that would
1.3125 + * be returned by <tt>Arrays.asList(a).hashCode()</tt>, unless <tt>a</tt>
1.3126 + * is <tt>null</tt>, in which case <tt>0</tt> is returned.
1.3127 + *
1.3128 + * @param a the array whose content-based hash code to compute
1.3129 + * @return a content-based hash code for <tt>a</tt>
1.3130 + * @see #deepHashCode(Object[])
1.3131 + * @since 1.5
1.3132 + */
1.3133 + public static int hashCode(Object a[]) {
1.3134 + if (a == null)
1.3135 + return 0;
1.3136 +
1.3137 + int result = 1;
1.3138 +
1.3139 + for (Object element : a)
1.3140 + result = 31 * result + (element == null ? 0 : element.hashCode());
1.3141 +
1.3142 + return result;
1.3143 + }
1.3144 +
1.3145 + /**
1.3146 + * Returns a hash code based on the "deep contents" of the specified
1.3147 + * array. If the array contains other arrays as elements, the
1.3148 + * hash code is based on their contents and so on, ad infinitum.
1.3149 + * It is therefore unacceptable to invoke this method on an array that
1.3150 + * contains itself as an element, either directly or indirectly through
1.3151 + * one or more levels of arrays. The behavior of such an invocation is
1.3152 + * undefined.
1.3153 + *
1.3154 + * <p>For any two arrays <tt>a</tt> and <tt>b</tt> such that
1.3155 + * <tt>Arrays.deepEquals(a, b)</tt>, it is also the case that
1.3156 + * <tt>Arrays.deepHashCode(a) == Arrays.deepHashCode(b)</tt>.
1.3157 + *
1.3158 + * <p>The computation of the value returned by this method is similar to
1.3159 + * that of the value returned by {@link List#hashCode()} on a list
1.3160 + * containing the same elements as <tt>a</tt> in the same order, with one
1.3161 + * difference: If an element <tt>e</tt> of <tt>a</tt> is itself an array,
1.3162 + * its hash code is computed not by calling <tt>e.hashCode()</tt>, but as
1.3163 + * by calling the appropriate overloading of <tt>Arrays.hashCode(e)</tt>
1.3164 + * if <tt>e</tt> is an array of a primitive type, or as by calling
1.3165 + * <tt>Arrays.deepHashCode(e)</tt> recursively if <tt>e</tt> is an array
1.3166 + * of a reference type. If <tt>a</tt> is <tt>null</tt>, this method
1.3167 + * returns 0.
1.3168 + *
1.3169 + * @param a the array whose deep-content-based hash code to compute
1.3170 + * @return a deep-content-based hash code for <tt>a</tt>
1.3171 + * @see #hashCode(Object[])
1.3172 + * @since 1.5
1.3173 + */
1.3174 + public static int deepHashCode(Object a[]) {
1.3175 + if (a == null)
1.3176 + return 0;
1.3177 +
1.3178 + int result = 1;
1.3179 +
1.3180 + for (Object element : a) {
1.3181 + int elementHash = 0;
1.3182 + if (element instanceof Object[])
1.3183 + elementHash = deepHashCode((Object[]) element);
1.3184 + else if (element instanceof byte[])
1.3185 + elementHash = hashCode((byte[]) element);
1.3186 + else if (element instanceof short[])
1.3187 + elementHash = hashCode((short[]) element);
1.3188 + else if (element instanceof int[])
1.3189 + elementHash = hashCode((int[]) element);
1.3190 + else if (element instanceof long[])
1.3191 + elementHash = hashCode((long[]) element);
1.3192 + else if (element instanceof char[])
1.3193 + elementHash = hashCode((char[]) element);
1.3194 + else if (element instanceof float[])
1.3195 + elementHash = hashCode((float[]) element);
1.3196 + else if (element instanceof double[])
1.3197 + elementHash = hashCode((double[]) element);
1.3198 + else if (element instanceof boolean[])
1.3199 + elementHash = hashCode((boolean[]) element);
1.3200 + else if (element != null)
1.3201 + elementHash = element.hashCode();
1.3202 +
1.3203 + result = 31 * result + elementHash;
1.3204 + }
1.3205 +
1.3206 + return result;
1.3207 + }
1.3208 +
1.3209 + /**
1.3210 + * Returns <tt>true</tt> if the two specified arrays are <i>deeply
1.3211 + * equal</i> to one another. Unlike the {@link #equals(Object[],Object[])}
1.3212 + * method, this method is appropriate for use with nested arrays of
1.3213 + * arbitrary depth.
1.3214 + *
1.3215 + * <p>Two array references are considered deeply equal if both
1.3216 + * are <tt>null</tt>, or if they refer to arrays that contain the same
1.3217 + * number of elements and all corresponding pairs of elements in the two
1.3218 + * arrays are deeply equal.
1.3219 + *
1.3220 + * <p>Two possibly <tt>null</tt> elements <tt>e1</tt> and <tt>e2</tt> are
1.3221 + * deeply equal if any of the following conditions hold:
1.3222 + * <ul>
1.3223 + * <li> <tt>e1</tt> and <tt>e2</tt> are both arrays of object reference
1.3224 + * types, and <tt>Arrays.deepEquals(e1, e2) would return true</tt>
1.3225 + * <li> <tt>e1</tt> and <tt>e2</tt> are arrays of the same primitive
1.3226 + * type, and the appropriate overloading of
1.3227 + * <tt>Arrays.equals(e1, e2)</tt> would return true.
1.3228 + * <li> <tt>e1 == e2</tt>
1.3229 + * <li> <tt>e1.equals(e2)</tt> would return true.
1.3230 + * </ul>
1.3231 + * Note that this definition permits <tt>null</tt> elements at any depth.
1.3232 + *
1.3233 + * <p>If either of the specified arrays contain themselves as elements
1.3234 + * either directly or indirectly through one or more levels of arrays,
1.3235 + * the behavior of this method is undefined.
1.3236 + *
1.3237 + * @param a1 one array to be tested for equality
1.3238 + * @param a2 the other array to be tested for equality
1.3239 + * @return <tt>true</tt> if the two arrays are equal
1.3240 + * @see #equals(Object[],Object[])
1.3241 + * @see Objects#deepEquals(Object, Object)
1.3242 + * @since 1.5
1.3243 + */
1.3244 + public static boolean deepEquals(Object[] a1, Object[] a2) {
1.3245 + if (a1 == a2)
1.3246 + return true;
1.3247 + if (a1 == null || a2==null)
1.3248 + return false;
1.3249 + int length = a1.length;
1.3250 + if (a2.length != length)
1.3251 + return false;
1.3252 +
1.3253 + for (int i = 0; i < length; i++) {
1.3254 + Object e1 = a1[i];
1.3255 + Object e2 = a2[i];
1.3256 +
1.3257 + if (e1 == e2)
1.3258 + continue;
1.3259 + if (e1 == null)
1.3260 + return false;
1.3261 +
1.3262 + // Figure out whether the two elements are equal
1.3263 + boolean eq = deepEquals0(e1, e2);
1.3264 +
1.3265 + if (!eq)
1.3266 + return false;
1.3267 + }
1.3268 + return true;
1.3269 + }
1.3270 +
1.3271 + static boolean deepEquals0(Object e1, Object e2) {
1.3272 + assert e1 != null;
1.3273 + boolean eq;
1.3274 + if (e1 instanceof Object[] && e2 instanceof Object[])
1.3275 + eq = deepEquals ((Object[]) e1, (Object[]) e2);
1.3276 + else if (e1 instanceof byte[] && e2 instanceof byte[])
1.3277 + eq = equals((byte[]) e1, (byte[]) e2);
1.3278 + else if (e1 instanceof short[] && e2 instanceof short[])
1.3279 + eq = equals((short[]) e1, (short[]) e2);
1.3280 + else if (e1 instanceof int[] && e2 instanceof int[])
1.3281 + eq = equals((int[]) e1, (int[]) e2);
1.3282 + else if (e1 instanceof long[] && e2 instanceof long[])
1.3283 + eq = equals((long[]) e1, (long[]) e2);
1.3284 + else if (e1 instanceof char[] && e2 instanceof char[])
1.3285 + eq = equals((char[]) e1, (char[]) e2);
1.3286 + else if (e1 instanceof float[] && e2 instanceof float[])
1.3287 + eq = equals((float[]) e1, (float[]) e2);
1.3288 + else if (e1 instanceof double[] && e2 instanceof double[])
1.3289 + eq = equals((double[]) e1, (double[]) e2);
1.3290 + else if (e1 instanceof boolean[] && e2 instanceof boolean[])
1.3291 + eq = equals((boolean[]) e1, (boolean[]) e2);
1.3292 + else
1.3293 + eq = e1.equals(e2);
1.3294 + return eq;
1.3295 + }
1.3296 +
1.3297 + /**
1.3298 + * Returns a string representation of the contents of the specified array.
1.3299 + * The string representation consists of a list of the array's elements,
1.3300 + * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
1.3301 + * separated by the characters <tt>", "</tt> (a comma followed by a
1.3302 + * space). Elements are converted to strings as by
1.3303 + * <tt>String.valueOf(long)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
1.3304 + * is <tt>null</tt>.
1.3305 + *
1.3306 + * @param a the array whose string representation to return
1.3307 + * @return a string representation of <tt>a</tt>
1.3308 + * @since 1.5
1.3309 + */
1.3310 + public static String toString(long[] a) {
1.3311 + if (a == null)
1.3312 + return "null";
1.3313 + int iMax = a.length - 1;
1.3314 + if (iMax == -1)
1.3315 + return "[]";
1.3316 +
1.3317 + StringBuilder b = new StringBuilder();
1.3318 + b.append('[');
1.3319 + for (int i = 0; ; i++) {
1.3320 + b.append(a[i]);
1.3321 + if (i == iMax)
1.3322 + return b.append(']').toString();
1.3323 + b.append(", ");
1.3324 + }
1.3325 + }
1.3326 +
1.3327 + /**
1.3328 + * Returns a string representation of the contents of the specified array.
1.3329 + * The string representation consists of a list of the array's elements,
1.3330 + * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
1.3331 + * separated by the characters <tt>", "</tt> (a comma followed by a
1.3332 + * space). Elements are converted to strings as by
1.3333 + * <tt>String.valueOf(int)</tt>. Returns <tt>"null"</tt> if <tt>a</tt> is
1.3334 + * <tt>null</tt>.
1.3335 + *
1.3336 + * @param a the array whose string representation to return
1.3337 + * @return a string representation of <tt>a</tt>
1.3338 + * @since 1.5
1.3339 + */
1.3340 + public static String toString(int[] a) {
1.3341 + if (a == null)
1.3342 + return "null";
1.3343 + int iMax = a.length - 1;
1.3344 + if (iMax == -1)
1.3345 + return "[]";
1.3346 +
1.3347 + StringBuilder b = new StringBuilder();
1.3348 + b.append('[');
1.3349 + for (int i = 0; ; i++) {
1.3350 + b.append(a[i]);
1.3351 + if (i == iMax)
1.3352 + return b.append(']').toString();
1.3353 + b.append(", ");
1.3354 + }
1.3355 + }
1.3356 +
1.3357 + /**
1.3358 + * Returns a string representation of the contents of the specified array.
1.3359 + * The string representation consists of a list of the array's elements,
1.3360 + * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
1.3361 + * separated by the characters <tt>", "</tt> (a comma followed by a
1.3362 + * space). Elements are converted to strings as by
1.3363 + * <tt>String.valueOf(short)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
1.3364 + * is <tt>null</tt>.
1.3365 + *
1.3366 + * @param a the array whose string representation to return
1.3367 + * @return a string representation of <tt>a</tt>
1.3368 + * @since 1.5
1.3369 + */
1.3370 + public static String toString(short[] a) {
1.3371 + if (a == null)
1.3372 + return "null";
1.3373 + int iMax = a.length - 1;
1.3374 + if (iMax == -1)
1.3375 + return "[]";
1.3376 +
1.3377 + StringBuilder b = new StringBuilder();
1.3378 + b.append('[');
1.3379 + for (int i = 0; ; i++) {
1.3380 + b.append(a[i]);
1.3381 + if (i == iMax)
1.3382 + return b.append(']').toString();
1.3383 + b.append(", ");
1.3384 + }
1.3385 + }
1.3386 +
1.3387 + /**
1.3388 + * Returns a string representation of the contents of the specified array.
1.3389 + * The string representation consists of a list of the array's elements,
1.3390 + * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
1.3391 + * separated by the characters <tt>", "</tt> (a comma followed by a
1.3392 + * space). Elements are converted to strings as by
1.3393 + * <tt>String.valueOf(char)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
1.3394 + * is <tt>null</tt>.
1.3395 + *
1.3396 + * @param a the array whose string representation to return
1.3397 + * @return a string representation of <tt>a</tt>
1.3398 + * @since 1.5
1.3399 + */
1.3400 + public static String toString(char[] a) {
1.3401 + if (a == null)
1.3402 + return "null";
1.3403 + int iMax = a.length - 1;
1.3404 + if (iMax == -1)
1.3405 + return "[]";
1.3406 +
1.3407 + StringBuilder b = new StringBuilder();
1.3408 + b.append('[');
1.3409 + for (int i = 0; ; i++) {
1.3410 + b.append(a[i]);
1.3411 + if (i == iMax)
1.3412 + return b.append(']').toString();
1.3413 + b.append(", ");
1.3414 + }
1.3415 + }
1.3416 +
1.3417 + /**
1.3418 + * Returns a string representation of the contents of the specified array.
1.3419 + * The string representation consists of a list of the array's elements,
1.3420 + * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements
1.3421 + * are separated by the characters <tt>", "</tt> (a comma followed
1.3422 + * by a space). Elements are converted to strings as by
1.3423 + * <tt>String.valueOf(byte)</tt>. Returns <tt>"null"</tt> if
1.3424 + * <tt>a</tt> is <tt>null</tt>.
1.3425 + *
1.3426 + * @param a the array whose string representation to return
1.3427 + * @return a string representation of <tt>a</tt>
1.3428 + * @since 1.5
1.3429 + */
1.3430 + public static String toString(byte[] a) {
1.3431 + if (a == null)
1.3432 + return "null";
1.3433 + int iMax = a.length - 1;
1.3434 + if (iMax == -1)
1.3435 + return "[]";
1.3436 +
1.3437 + StringBuilder b = new StringBuilder();
1.3438 + b.append('[');
1.3439 + for (int i = 0; ; i++) {
1.3440 + b.append(a[i]);
1.3441 + if (i == iMax)
1.3442 + return b.append(']').toString();
1.3443 + b.append(", ");
1.3444 + }
1.3445 + }
1.3446 +
1.3447 + /**
1.3448 + * Returns a string representation of the contents of the specified array.
1.3449 + * The string representation consists of a list of the array's elements,
1.3450 + * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
1.3451 + * separated by the characters <tt>", "</tt> (a comma followed by a
1.3452 + * space). Elements are converted to strings as by
1.3453 + * <tt>String.valueOf(boolean)</tt>. Returns <tt>"null"</tt> if
1.3454 + * <tt>a</tt> is <tt>null</tt>.
1.3455 + *
1.3456 + * @param a the array whose string representation to return
1.3457 + * @return a string representation of <tt>a</tt>
1.3458 + * @since 1.5
1.3459 + */
1.3460 + public static String toString(boolean[] a) {
1.3461 + if (a == null)
1.3462 + return "null";
1.3463 + int iMax = a.length - 1;
1.3464 + if (iMax == -1)
1.3465 + return "[]";
1.3466 +
1.3467 + StringBuilder b = new StringBuilder();
1.3468 + b.append('[');
1.3469 + for (int i = 0; ; i++) {
1.3470 + b.append(a[i]);
1.3471 + if (i == iMax)
1.3472 + return b.append(']').toString();
1.3473 + b.append(", ");
1.3474 + }
1.3475 + }
1.3476 +
1.3477 + /**
1.3478 + * Returns a string representation of the contents of the specified array.
1.3479 + * The string representation consists of a list of the array's elements,
1.3480 + * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
1.3481 + * separated by the characters <tt>", "</tt> (a comma followed by a
1.3482 + * space). Elements are converted to strings as by
1.3483 + * <tt>String.valueOf(float)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
1.3484 + * is <tt>null</tt>.
1.3485 + *
1.3486 + * @param a the array whose string representation to return
1.3487 + * @return a string representation of <tt>a</tt>
1.3488 + * @since 1.5
1.3489 + */
1.3490 + public static String toString(float[] a) {
1.3491 + if (a == null)
1.3492 + return "null";
1.3493 +
1.3494 + int iMax = a.length - 1;
1.3495 + if (iMax == -1)
1.3496 + return "[]";
1.3497 +
1.3498 + StringBuilder b = new StringBuilder();
1.3499 + b.append('[');
1.3500 + for (int i = 0; ; i++) {
1.3501 + b.append(a[i]);
1.3502 + if (i == iMax)
1.3503 + return b.append(']').toString();
1.3504 + b.append(", ");
1.3505 + }
1.3506 + }
1.3507 +
1.3508 + /**
1.3509 + * Returns a string representation of the contents of the specified array.
1.3510 + * The string representation consists of a list of the array's elements,
1.3511 + * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
1.3512 + * separated by the characters <tt>", "</tt> (a comma followed by a
1.3513 + * space). Elements are converted to strings as by
1.3514 + * <tt>String.valueOf(double)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
1.3515 + * is <tt>null</tt>.
1.3516 + *
1.3517 + * @param a the array whose string representation to return
1.3518 + * @return a string representation of <tt>a</tt>
1.3519 + * @since 1.5
1.3520 + */
1.3521 + public static String toString(double[] a) {
1.3522 + if (a == null)
1.3523 + return "null";
1.3524 + int iMax = a.length - 1;
1.3525 + if (iMax == -1)
1.3526 + return "[]";
1.3527 +
1.3528 + StringBuilder b = new StringBuilder();
1.3529 + b.append('[');
1.3530 + for (int i = 0; ; i++) {
1.3531 + b.append(a[i]);
1.3532 + if (i == iMax)
1.3533 + return b.append(']').toString();
1.3534 + b.append(", ");
1.3535 + }
1.3536 + }
1.3537 +
1.3538 + /**
1.3539 + * Returns a string representation of the contents of the specified array.
1.3540 + * If the array contains other arrays as elements, they are converted to
1.3541 + * strings by the {@link Object#toString} method inherited from
1.3542 + * <tt>Object</tt>, which describes their <i>identities</i> rather than
1.3543 + * their contents.
1.3544 + *
1.3545 + * <p>The value returned by this method is equal to the value that would
1.3546 + * be returned by <tt>Arrays.asList(a).toString()</tt>, unless <tt>a</tt>
1.3547 + * is <tt>null</tt>, in which case <tt>"null"</tt> is returned.
1.3548 + *
1.3549 + * @param a the array whose string representation to return
1.3550 + * @return a string representation of <tt>a</tt>
1.3551 + * @see #deepToString(Object[])
1.3552 + * @since 1.5
1.3553 + */
1.3554 + public static String toString(Object[] a) {
1.3555 + if (a == null)
1.3556 + return "null";
1.3557 +
1.3558 + int iMax = a.length - 1;
1.3559 + if (iMax == -1)
1.3560 + return "[]";
1.3561 +
1.3562 + StringBuilder b = new StringBuilder();
1.3563 + b.append('[');
1.3564 + for (int i = 0; ; i++) {
1.3565 + b.append(String.valueOf(a[i]));
1.3566 + if (i == iMax)
1.3567 + return b.append(']').toString();
1.3568 + b.append(", ");
1.3569 + }
1.3570 + }
1.3571 +
1.3572 + /**
1.3573 + * Returns a string representation of the "deep contents" of the specified
1.3574 + * array. If the array contains other arrays as elements, the string
1.3575 + * representation contains their contents and so on. This method is
1.3576 + * designed for converting multidimensional arrays to strings.
1.3577 + *
1.3578 + * <p>The string representation consists of a list of the array's
1.3579 + * elements, enclosed in square brackets (<tt>"[]"</tt>). Adjacent
1.3580 + * elements are separated by the characters <tt>", "</tt> (a comma
1.3581 + * followed by a space). Elements are converted to strings as by
1.3582 + * <tt>String.valueOf(Object)</tt>, unless they are themselves
1.3583 + * arrays.
1.3584 + *
1.3585 + * <p>If an element <tt>e</tt> is an array of a primitive type, it is
1.3586 + * converted to a string as by invoking the appropriate overloading of
1.3587 + * <tt>Arrays.toString(e)</tt>. If an element <tt>e</tt> is an array of a
1.3588 + * reference type, it is converted to a string as by invoking
1.3589 + * this method recursively.
1.3590 + *
1.3591 + * <p>To avoid infinite recursion, if the specified array contains itself
1.3592 + * as an element, or contains an indirect reference to itself through one
1.3593 + * or more levels of arrays, the self-reference is converted to the string
1.3594 + * <tt>"[...]"</tt>. For example, an array containing only a reference
1.3595 + * to itself would be rendered as <tt>"[[...]]"</tt>.
1.3596 + *
1.3597 + * <p>This method returns <tt>"null"</tt> if the specified array
1.3598 + * is <tt>null</tt>.
1.3599 + *
1.3600 + * @param a the array whose string representation to return
1.3601 + * @return a string representation of <tt>a</tt>
1.3602 + * @see #toString(Object[])
1.3603 + * @since 1.5
1.3604 + */
1.3605 + public static String deepToString(Object[] a) {
1.3606 + if (a == null)
1.3607 + return "null";
1.3608 +
1.3609 + int bufLen = 20 * a.length;
1.3610 + if (a.length != 0 && bufLen <= 0)
1.3611 + bufLen = Integer.MAX_VALUE;
1.3612 + StringBuilder buf = new StringBuilder(bufLen);
1.3613 + deepToString(a, buf, new HashSet<Object[]>());
1.3614 + return buf.toString();
1.3615 + }
1.3616 +
1.3617 + private static void deepToString(Object[] a, StringBuilder buf,
1.3618 + Set<Object[]> dejaVu) {
1.3619 + if (a == null) {
1.3620 + buf.append("null");
1.3621 + return;
1.3622 + }
1.3623 + int iMax = a.length - 1;
1.3624 + if (iMax == -1) {
1.3625 + buf.append("[]");
1.3626 + return;
1.3627 + }
1.3628 +
1.3629 + dejaVu.add(a);
1.3630 + buf.append('[');
1.3631 + for (int i = 0; ; i++) {
1.3632 +
1.3633 + Object element = a[i];
1.3634 + if (element == null) {
1.3635 + buf.append("null");
1.3636 + } else {
1.3637 + Class eClass = element.getClass();
1.3638 +
1.3639 + if (eClass.isArray()) {
1.3640 + if (eClass == byte[].class)
1.3641 + buf.append(toString((byte[]) element));
1.3642 + else if (eClass == short[].class)
1.3643 + buf.append(toString((short[]) element));
1.3644 + else if (eClass == int[].class)
1.3645 + buf.append(toString((int[]) element));
1.3646 + else if (eClass == long[].class)
1.3647 + buf.append(toString((long[]) element));
1.3648 + else if (eClass == char[].class)
1.3649 + buf.append(toString((char[]) element));
1.3650 + else if (eClass == float[].class)
1.3651 + buf.append(toString((float[]) element));
1.3652 + else if (eClass == double[].class)
1.3653 + buf.append(toString((double[]) element));
1.3654 + else if (eClass == boolean[].class)
1.3655 + buf.append(toString((boolean[]) element));
1.3656 + else { // element is an array of object references
1.3657 + if (dejaVu.contains(element))
1.3658 + buf.append("[...]");
1.3659 + else
1.3660 + deepToString((Object[])element, buf, dejaVu);
1.3661 + }
1.3662 + } else { // element is non-null and not an array
1.3663 + buf.append(element.toString());
1.3664 + }
1.3665 + }
1.3666 + if (i == iMax)
1.3667 + break;
1.3668 + buf.append(", ");
1.3669 + }
1.3670 + buf.append(']');
1.3671 + dejaVu.remove(a);
1.3672 + }
1.3673 +}