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