0001 /*
0002 * Copyright 1997-2007 Sun Microsystems, Inc. All Rights Reserved.
0003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0004 *
0005 * This code is free software; you can redistribute it and/or modify it
0006 * under the terms of the GNU General Public License version 2 only, as
0007 * published by the Free Software Foundation. Sun designates this
0008 * particular file as subject to the "Classpath" exception as provided
0009 * by Sun in the LICENSE file that accompanied this code.
0010 *
0011 * This code is distributed in the hope that it will be useful, but WITHOUT
0012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0014 * version 2 for more details (a copy is included in the LICENSE file that
0015 * accompanied this code).
0016 *
0017 * You should have received a copy of the GNU General Public License version
0018 * 2 along with this work; if not, write to the Free Software Foundation,
0019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0020 *
0021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
0022 * CA 95054 USA or visit www.sun.com if you need additional information or
0023 * have any questions.
0024 */
0025
0026 package java.util;
0027
0028 import java.lang.reflect.*;
0029
0030 /**
0031 * This class contains various methods for manipulating arrays (such as
0032 * sorting and searching). This class also contains a static factory
0033 * that allows arrays to be viewed as lists.
0034 *
0035 * <p>The methods in this class all throw a <tt>NullPointerException</tt> if
0036 * the specified array reference is null, except where noted.
0037 *
0038 * <p>The documentation for the methods contained in this class includes
0039 * briefs description of the <i>implementations</i>. Such descriptions should
0040 * be regarded as <i>implementation notes</i>, rather than parts of the
0041 * <i>specification</i>. Implementors should feel free to substitute other
0042 * algorithms, so long as the specification itself is adhered to. (For
0043 * example, the algorithm used by <tt>sort(Object[])</tt> does not have to be
0044 * a mergesort, but it does have to be <i>stable</i>.)
0045 *
0046 * <p>This class is a member of the
0047 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
0048 * Java Collections Framework</a>.
0049 *
0050 * @author Josh Bloch
0051 * @author Neal Gafter
0052 * @author John Rose
0053 * @version 1.80, 07/14/07
0054 * @since 1.2
0055 */
0056
0057 public class Arrays {
0058 // Suppresses default constructor, ensuring non-instantiability.
0059 private Arrays() {
0060 }
0061
0062 // Sorting
0063
0064 /**
0065 * Sorts the specified array of longs into ascending numerical order.
0066 * The sorting algorithm is a tuned quicksort, adapted from Jon
0067 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0068 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0069 * 1993). This algorithm offers n*log(n) performance on many data sets
0070 * that cause other quicksorts to degrade to quadratic performance.
0071 *
0072 * @param a the array to be sorted
0073 */
0074 public static void sort(long[] a) {
0075 sort1(a, 0, a.length);
0076 }
0077
0078 /**
0079 * Sorts the specified range of the specified array of longs into
0080 * ascending numerical order. The range to be sorted extends from index
0081 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
0082 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
0083 *
0084 * <p>The sorting algorithm is a tuned quicksort, adapted from Jon
0085 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0086 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0087 * 1993). This algorithm offers n*log(n) performance on many data sets
0088 * that cause other quicksorts to degrade to quadratic performance.
0089 *
0090 * @param a the array to be sorted
0091 * @param fromIndex the index of the first element (inclusive) to be
0092 * sorted
0093 * @param toIndex the index of the last element (exclusive) to be sorted
0094 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
0095 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
0096 * <tt>toIndex > a.length</tt>
0097 */
0098 public static void sort(long[] a, int fromIndex, int toIndex) {
0099 rangeCheck(a.length, fromIndex, toIndex);
0100 sort1(a, fromIndex, toIndex - fromIndex);
0101 }
0102
0103 /**
0104 * Sorts the specified array of ints into ascending numerical order.
0105 * The sorting algorithm is a tuned quicksort, adapted from Jon
0106 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0107 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0108 * 1993). This algorithm offers n*log(n) performance on many data sets
0109 * that cause other quicksorts to degrade to quadratic performance.
0110 *
0111 * @param a the array to be sorted
0112 */
0113 public static void sort(int[] a) {
0114 sort1(a, 0, a.length);
0115 }
0116
0117 /**
0118 * Sorts the specified range of the specified array of ints into
0119 * ascending numerical order. The range to be sorted extends from index
0120 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
0121 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
0122 *
0123 * The sorting algorithm is a tuned quicksort, adapted from Jon
0124 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0125 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0126 * 1993). This algorithm offers n*log(n) performance on many data sets
0127 * that cause other quicksorts to degrade to quadratic performance.
0128 *
0129 * @param a the array to be sorted
0130 * @param fromIndex the index of the first element (inclusive) to be
0131 * sorted
0132 * @param toIndex the index of the last element (exclusive) to be sorted
0133 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
0134 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
0135 * <tt>toIndex > a.length</tt>
0136 */
0137 public static void sort(int[] a, int fromIndex, int toIndex) {
0138 rangeCheck(a.length, fromIndex, toIndex);
0139 sort1(a, fromIndex, toIndex - fromIndex);
0140 }
0141
0142 /**
0143 * Sorts the specified array of shorts into ascending numerical order.
0144 * The sorting algorithm is a tuned quicksort, adapted from Jon
0145 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0146 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0147 * 1993). This algorithm offers n*log(n) performance on many data sets
0148 * that cause other quicksorts to degrade to quadratic performance.
0149 *
0150 * @param a the array to be sorted
0151 */
0152 public static void sort(short[] a) {
0153 sort1(a, 0, a.length);
0154 }
0155
0156 /**
0157 * Sorts the specified range of the specified array of shorts into
0158 * ascending numerical order. The range to be sorted extends from index
0159 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
0160 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
0161 *
0162 * The sorting algorithm is a tuned quicksort, adapted from Jon
0163 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0164 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0165 * 1993). This algorithm offers n*log(n) performance on many data sets
0166 * that cause other quicksorts to degrade to quadratic performance.
0167 *
0168 * @param a the array to be sorted
0169 * @param fromIndex the index of the first element (inclusive) to be
0170 * sorted
0171 * @param toIndex the index of the last element (exclusive) to be sorted
0172 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
0173 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
0174 * <tt>toIndex > a.length</tt>
0175 */
0176 public static void sort(short[] a, int fromIndex, int toIndex) {
0177 rangeCheck(a.length, fromIndex, toIndex);
0178 sort1(a, fromIndex, toIndex - fromIndex);
0179 }
0180
0181 /**
0182 * Sorts the specified array of chars into ascending numerical order.
0183 * The sorting algorithm is a tuned quicksort, adapted from Jon
0184 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0185 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0186 * 1993). This algorithm offers n*log(n) performance on many data sets
0187 * that cause other quicksorts to degrade to quadratic performance.
0188 *
0189 * @param a the array to be sorted
0190 */
0191 public static void sort(char[] a) {
0192 sort1(a, 0, a.length);
0193 }
0194
0195 /**
0196 * Sorts the specified range of the specified array of chars into
0197 * ascending numerical order. The range to be sorted extends from index
0198 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
0199 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
0200 *
0201 * The sorting algorithm is a tuned quicksort, adapted from Jon
0202 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0203 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0204 * 1993). This algorithm offers n*log(n) performance on many data sets
0205 * that cause other quicksorts to degrade to quadratic performance.
0206 *
0207 * @param a the array to be sorted
0208 * @param fromIndex the index of the first element (inclusive) to be
0209 * sorted
0210 * @param toIndex the index of the last element (exclusive) to be sorted
0211 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
0212 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
0213 * <tt>toIndex > a.length</tt>
0214 */
0215 public static void sort(char[] a, int fromIndex, int toIndex) {
0216 rangeCheck(a.length, fromIndex, toIndex);
0217 sort1(a, fromIndex, toIndex - fromIndex);
0218 }
0219
0220 /**
0221 * Sorts the specified array of bytes into ascending numerical order.
0222 * The sorting algorithm is a tuned quicksort, adapted from Jon
0223 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0224 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0225 * 1993). This algorithm offers n*log(n) performance on many data sets
0226 * that cause other quicksorts to degrade to quadratic performance.
0227 *
0228 * @param a the array to be sorted
0229 */
0230 public static void sort(byte[] a) {
0231 sort1(a, 0, a.length);
0232 }
0233
0234 /**
0235 * Sorts the specified range of the specified array of bytes into
0236 * ascending numerical order. The range to be sorted extends from index
0237 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
0238 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)<p>
0239 *
0240 * The sorting algorithm is a tuned quicksort, adapted from Jon
0241 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0242 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0243 * 1993). This algorithm offers n*log(n) performance on many data sets
0244 * that cause other quicksorts to degrade to quadratic performance.
0245 *
0246 * @param a the array to be sorted
0247 * @param fromIndex the index of the first element (inclusive) to be
0248 * sorted
0249 * @param toIndex the index of the last element (exclusive) to be sorted
0250 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
0251 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
0252 * <tt>toIndex > a.length</tt>
0253 */
0254 public static void sort(byte[] a, int fromIndex, int toIndex) {
0255 rangeCheck(a.length, fromIndex, toIndex);
0256 sort1(a, fromIndex, toIndex - fromIndex);
0257 }
0258
0259 /**
0260 * Sorts the specified array of doubles into ascending numerical order.
0261 * <p>
0262 * The <code><</code> relation does not provide a total order on
0263 * all floating-point values; although they are distinct numbers
0264 * <code>-0.0 == 0.0</code> is <code>true</code> and a NaN value
0265 * compares neither less than, greater than, nor equal to any
0266 * floating-point value, even itself. To allow the sort to
0267 * proceed, instead of using the <code><</code> relation to
0268 * determine ascending numerical order, this method uses the total
0269 * order imposed by {@link Double#compareTo}. This ordering
0270 * differs from the <code><</code> relation in that
0271 * <code>-0.0</code> is treated as less than <code>0.0</code> and
0272 * NaN is considered greater than any other floating-point value.
0273 * For the purposes of sorting, all NaN values are considered
0274 * equivalent and equal.
0275 * <p>
0276 * The sorting algorithm is a tuned quicksort, adapted from Jon
0277 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0278 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0279 * 1993). This algorithm offers n*log(n) performance on many data sets
0280 * that cause other quicksorts to degrade to quadratic performance.
0281 *
0282 * @param a the array to be sorted
0283 */
0284 public static void sort(double[] a) {
0285 sort2(a, 0, a.length);
0286 }
0287
0288 /**
0289 * Sorts the specified range of the specified array of doubles into
0290 * ascending numerical order. The range to be sorted extends from index
0291 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
0292 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
0293 * <p>
0294 * The <code><</code> relation does not provide a total order on
0295 * all floating-point values; although they are distinct numbers
0296 * <code>-0.0 == 0.0</code> is <code>true</code> and a NaN value
0297 * compares neither less than, greater than, nor equal to any
0298 * floating-point value, even itself. To allow the sort to
0299 * proceed, instead of using the <code><</code> relation to
0300 * determine ascending numerical order, this method uses the total
0301 * order imposed by {@link Double#compareTo}. This ordering
0302 * differs from the <code><</code> relation in that
0303 * <code>-0.0</code> is treated as less than <code>0.0</code> and
0304 * NaN is considered greater than any other floating-point value.
0305 * For the purposes of sorting, all NaN values are considered
0306 * equivalent and equal.
0307 * <p>
0308 * The sorting algorithm is a tuned quicksort, adapted from Jon
0309 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0310 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0311 * 1993). This algorithm offers n*log(n) performance on many data sets
0312 * that cause other quicksorts to degrade to quadratic performance.
0313 *
0314 * @param a the array to be sorted
0315 * @param fromIndex the index of the first element (inclusive) to be
0316 * sorted
0317 * @param toIndex the index of the last element (exclusive) to be sorted
0318 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
0319 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
0320 * <tt>toIndex > a.length</tt>
0321 */
0322 public static void sort(double[] a, int fromIndex, int toIndex) {
0323 rangeCheck(a.length, fromIndex, toIndex);
0324 sort2(a, fromIndex, toIndex);
0325 }
0326
0327 /**
0328 * Sorts the specified array of floats into ascending numerical order.
0329 * <p>
0330 * The <code><</code> relation does not provide a total order on
0331 * all floating-point values; although they are distinct numbers
0332 * <code>-0.0f == 0.0f</code> is <code>true</code> and a NaN value
0333 * compares neither less than, greater than, nor equal to any
0334 * floating-point value, even itself. To allow the sort to
0335 * proceed, instead of using the <code><</code> relation to
0336 * determine ascending numerical order, this method uses the total
0337 * order imposed by {@link Float#compareTo}. This ordering
0338 * differs from the <code><</code> relation in that
0339 * <code>-0.0f</code> is treated as less than <code>0.0f</code> and
0340 * NaN is considered greater than any other floating-point value.
0341 * For the purposes of sorting, all NaN values are considered
0342 * equivalent and equal.
0343 * <p>
0344 * The sorting algorithm is a tuned quicksort, adapted from Jon
0345 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0346 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0347 * 1993). This algorithm offers n*log(n) performance on many data sets
0348 * that cause other quicksorts to degrade to quadratic performance.
0349 *
0350 * @param a the array to be sorted
0351 */
0352 public static void sort(float[] a) {
0353 sort2(a, 0, a.length);
0354 }
0355
0356 /**
0357 * Sorts the specified range of the specified array of floats into
0358 * ascending numerical order. The range to be sorted extends from index
0359 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
0360 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.)
0361 * <p>
0362 * The <code><</code> relation does not provide a total order on
0363 * all floating-point values; although they are distinct numbers
0364 * <code>-0.0f == 0.0f</code> is <code>true</code> and a NaN value
0365 * compares neither less than, greater than, nor equal to any
0366 * floating-point value, even itself. To allow the sort to
0367 * proceed, instead of using the <code><</code> relation to
0368 * determine ascending numerical order, this method uses the total
0369 * order imposed by {@link Float#compareTo}. This ordering
0370 * differs from the <code><</code> relation in that
0371 * <code>-0.0f</code> is treated as less than <code>0.0f</code> and
0372 * NaN is considered greater than any other floating-point value.
0373 * For the purposes of sorting, all NaN values are considered
0374 * equivalent and equal.
0375 * <p>
0376 * The sorting algorithm is a tuned quicksort, adapted from Jon
0377 * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function",
0378 * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November
0379 * 1993). This algorithm offers n*log(n) performance on many data sets
0380 * that cause other quicksorts to degrade to quadratic performance.
0381 *
0382 * @param a the array to be sorted
0383 * @param fromIndex the index of the first element (inclusive) to be
0384 * sorted
0385 * @param toIndex the index of the last element (exclusive) to be sorted
0386 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
0387 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
0388 * <tt>toIndex > a.length</tt>
0389 */
0390 public static void sort(float[] a, int fromIndex, int toIndex) {
0391 rangeCheck(a.length, fromIndex, toIndex);
0392 sort2(a, fromIndex, toIndex);
0393 }
0394
0395 private static void sort2(double a[], int fromIndex, int toIndex) {
0396 final long NEG_ZERO_BITS = Double.doubleToLongBits(-0.0d);
0397 /*
0398 * The sort is done in three phases to avoid the expense of using
0399 * NaN and -0.0 aware comparisons during the main sort.
0400 */
0401
0402 /*
0403 * Preprocessing phase: Move any NaN's to end of array, count the
0404 * number of -0.0's, and turn them into 0.0's.
0405 */
0406 int numNegZeros = 0;
0407 int i = fromIndex, n = toIndex;
0408 while (i < n) {
0409 if (a[i] != a[i]) {
0410 swap(a, i, --n);
0411 } else {
0412 if (a[i] == 0
0413 && Double.doubleToLongBits(a[i]) == NEG_ZERO_BITS) {
0414 a[i] = 0.0d;
0415 numNegZeros++;
0416 }
0417 i++;
0418 }
0419 }
0420
0421 // Main sort phase: quicksort everything but the NaN's
0422 sort1(a, fromIndex, n - fromIndex);
0423
0424 // Postprocessing phase: change 0.0's to -0.0's as required
0425 if (numNegZeros != 0) {
0426 int j = binarySearch0(a, fromIndex, n, 0.0d); // posn of ANY zero
0427 do {
0428 j--;
0429 } while (j >= fromIndex && a[j] == 0.0d);
0430
0431 // j is now one less than the index of the FIRST zero
0432 for (int k = 0; k < numNegZeros; k++)
0433 a[++j] = -0.0d;
0434 }
0435 }
0436
0437 private static void sort2(float a[], int fromIndex, int toIndex) {
0438 final int NEG_ZERO_BITS = Float.floatToIntBits(-0.0f);
0439 /*
0440 * The sort is done in three phases to avoid the expense of using
0441 * NaN and -0.0 aware comparisons during the main sort.
0442 */
0443
0444 /*
0445 * Preprocessing phase: Move any NaN's to end of array, count the
0446 * number of -0.0's, and turn them into 0.0's.
0447 */
0448 int numNegZeros = 0;
0449 int i = fromIndex, n = toIndex;
0450 while (i < n) {
0451 if (a[i] != a[i]) {
0452 swap(a, i, --n);
0453 } else {
0454 if (a[i] == 0
0455 && Float.floatToIntBits(a[i]) == NEG_ZERO_BITS) {
0456 a[i] = 0.0f;
0457 numNegZeros++;
0458 }
0459 i++;
0460 }
0461 }
0462
0463 // Main sort phase: quicksort everything but the NaN's
0464 sort1(a, fromIndex, n - fromIndex);
0465
0466 // Postprocessing phase: change 0.0's to -0.0's as required
0467 if (numNegZeros != 0) {
0468 int j = binarySearch0(a, fromIndex, n, 0.0f); // posn of ANY zero
0469 do {
0470 j--;
0471 } while (j >= fromIndex && a[j] == 0.0f);
0472
0473 // j is now one less than the index of the FIRST zero
0474 for (int k = 0; k < numNegZeros; k++)
0475 a[++j] = -0.0f;
0476 }
0477 }
0478
0479 /*
0480 * The code for each of the seven primitive types is largely identical.
0481 * C'est la vie.
0482 */
0483
0484 /**
0485 * Sorts the specified sub-array of longs into ascending order.
0486 */
0487 private static void sort1(long x[], int off, int len) {
0488 // Insertion sort on smallest arrays
0489 if (len < 7) {
0490 for (int i = off; i < len + off; i++)
0491 for (int j = i; j > off && x[j - 1] > x[j]; j--)
0492 swap(x, j, j - 1);
0493 return;
0494 }
0495
0496 // Choose a partition element, v
0497 int m = off + (len >> 1); // Small arrays, middle element
0498 if (len > 7) {
0499 int l = off;
0500 int n = off + len - 1;
0501 if (len > 40) { // Big arrays, pseudomedian of 9
0502 int s = len / 8;
0503 l = med3(x, l, l + s, l + 2 * s);
0504 m = med3(x, m - s, m, m + s);
0505 n = med3(x, n - 2 * s, n - s, n);
0506 }
0507 m = med3(x, l, m, n); // Mid-size, med of 3
0508 }
0509 long v = x[m];
0510
0511 // Establish Invariant: v* (<v)* (>v)* v*
0512 int a = off, b = a, c = off + len - 1, d = c;
0513 while (true) {
0514 while (b <= c && x[b] <= v) {
0515 if (x[b] == v)
0516 swap(x, a++, b);
0517 b++;
0518 }
0519 while (c >= b && x[c] >= v) {
0520 if (x[c] == v)
0521 swap(x, c, d--);
0522 c--;
0523 }
0524 if (b > c)
0525 break;
0526 swap(x, b++, c--);
0527 }
0528
0529 // Swap partition elements back to middle
0530 int s, n = off + len;
0531 s = Math.min(a - off, b - a);
0532 vecswap(x, off, b - s, s);
0533 s = Math.min(d - c, n - d - 1);
0534 vecswap(x, b, n - s, s);
0535
0536 // Recursively sort non-partition-elements
0537 if ((s = b - a) > 1)
0538 sort1(x, off, s);
0539 if ((s = d - c) > 1)
0540 sort1(x, n - s, s);
0541 }
0542
0543 /**
0544 * Swaps x[a] with x[b].
0545 */
0546 private static void swap(long x[], int a, int b) {
0547 long t = x[a];
0548 x[a] = x[b];
0549 x[b] = t;
0550 }
0551
0552 /**
0553 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
0554 */
0555 private static void vecswap(long x[], int a, int b, int n) {
0556 for (int i = 0; i < n; i++, a++, b++)
0557 swap(x, a, b);
0558 }
0559
0560 /**
0561 * Returns the index of the median of the three indexed longs.
0562 */
0563 private static int med3(long x[], int a, int b, int c) {
0564 return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
0565 : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
0566 }
0567
0568 /**
0569 * Sorts the specified sub-array of integers into ascending order.
0570 */
0571 private static void sort1(int x[], int off, int len) {
0572 // Insertion sort on smallest arrays
0573 if (len < 7) {
0574 for (int i = off; i < len + off; i++)
0575 for (int j = i; j > off && x[j - 1] > x[j]; j--)
0576 swap(x, j, j - 1);
0577 return;
0578 }
0579
0580 // Choose a partition element, v
0581 int m = off + (len >> 1); // Small arrays, middle element
0582 if (len > 7) {
0583 int l = off;
0584 int n = off + len - 1;
0585 if (len > 40) { // Big arrays, pseudomedian of 9
0586 int s = len / 8;
0587 l = med3(x, l, l + s, l + 2 * s);
0588 m = med3(x, m - s, m, m + s);
0589 n = med3(x, n - 2 * s, n - s, n);
0590 }
0591 m = med3(x, l, m, n); // Mid-size, med of 3
0592 }
0593 int v = x[m];
0594
0595 // Establish Invariant: v* (<v)* (>v)* v*
0596 int a = off, b = a, c = off + len - 1, d = c;
0597 while (true) {
0598 while (b <= c && x[b] <= v) {
0599 if (x[b] == v)
0600 swap(x, a++, b);
0601 b++;
0602 }
0603 while (c >= b && x[c] >= v) {
0604 if (x[c] == v)
0605 swap(x, c, d--);
0606 c--;
0607 }
0608 if (b > c)
0609 break;
0610 swap(x, b++, c--);
0611 }
0612
0613 // Swap partition elements back to middle
0614 int s, n = off + len;
0615 s = Math.min(a - off, b - a);
0616 vecswap(x, off, b - s, s);
0617 s = Math.min(d - c, n - d - 1);
0618 vecswap(x, b, n - s, s);
0619
0620 // Recursively sort non-partition-elements
0621 if ((s = b - a) > 1)
0622 sort1(x, off, s);
0623 if ((s = d - c) > 1)
0624 sort1(x, n - s, s);
0625 }
0626
0627 /**
0628 * Swaps x[a] with x[b].
0629 */
0630 private static void swap(int x[], int a, int b) {
0631 int t = x[a];
0632 x[a] = x[b];
0633 x[b] = t;
0634 }
0635
0636 /**
0637 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
0638 */
0639 private static void vecswap(int x[], int a, int b, int n) {
0640 for (int i = 0; i < n; i++, a++, b++)
0641 swap(x, a, b);
0642 }
0643
0644 /**
0645 * Returns the index of the median of the three indexed integers.
0646 */
0647 private static int med3(int x[], int a, int b, int c) {
0648 return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
0649 : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
0650 }
0651
0652 /**
0653 * Sorts the specified sub-array of shorts into ascending order.
0654 */
0655 private static void sort1(short x[], int off, int len) {
0656 // Insertion sort on smallest arrays
0657 if (len < 7) {
0658 for (int i = off; i < len + off; i++)
0659 for (int j = i; j > off && x[j - 1] > x[j]; j--)
0660 swap(x, j, j - 1);
0661 return;
0662 }
0663
0664 // Choose a partition element, v
0665 int m = off + (len >> 1); // Small arrays, middle element
0666 if (len > 7) {
0667 int l = off;
0668 int n = off + len - 1;
0669 if (len > 40) { // Big arrays, pseudomedian of 9
0670 int s = len / 8;
0671 l = med3(x, l, l + s, l + 2 * s);
0672 m = med3(x, m - s, m, m + s);
0673 n = med3(x, n - 2 * s, n - s, n);
0674 }
0675 m = med3(x, l, m, n); // Mid-size, med of 3
0676 }
0677 short v = x[m];
0678
0679 // Establish Invariant: v* (<v)* (>v)* v*
0680 int a = off, b = a, c = off + len - 1, d = c;
0681 while (true) {
0682 while (b <= c && x[b] <= v) {
0683 if (x[b] == v)
0684 swap(x, a++, b);
0685 b++;
0686 }
0687 while (c >= b && x[c] >= v) {
0688 if (x[c] == v)
0689 swap(x, c, d--);
0690 c--;
0691 }
0692 if (b > c)
0693 break;
0694 swap(x, b++, c--);
0695 }
0696
0697 // Swap partition elements back to middle
0698 int s, n = off + len;
0699 s = Math.min(a - off, b - a);
0700 vecswap(x, off, b - s, s);
0701 s = Math.min(d - c, n - d - 1);
0702 vecswap(x, b, n - s, s);
0703
0704 // Recursively sort non-partition-elements
0705 if ((s = b - a) > 1)
0706 sort1(x, off, s);
0707 if ((s = d - c) > 1)
0708 sort1(x, n - s, s);
0709 }
0710
0711 /**
0712 * Swaps x[a] with x[b].
0713 */
0714 private static void swap(short x[], int a, int b) {
0715 short t = x[a];
0716 x[a] = x[b];
0717 x[b] = t;
0718 }
0719
0720 /**
0721 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
0722 */
0723 private static void vecswap(short x[], int a, int b, int n) {
0724 for (int i = 0; i < n; i++, a++, b++)
0725 swap(x, a, b);
0726 }
0727
0728 /**
0729 * Returns the index of the median of the three indexed shorts.
0730 */
0731 private static int med3(short x[], int a, int b, int c) {
0732 return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
0733 : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
0734 }
0735
0736 /**
0737 * Sorts the specified sub-array of chars into ascending order.
0738 */
0739 private static void sort1(char x[], int off, int len) {
0740 // Insertion sort on smallest arrays
0741 if (len < 7) {
0742 for (int i = off; i < len + off; i++)
0743 for (int j = i; j > off && x[j - 1] > x[j]; j--)
0744 swap(x, j, j - 1);
0745 return;
0746 }
0747
0748 // Choose a partition element, v
0749 int m = off + (len >> 1); // Small arrays, middle element
0750 if (len > 7) {
0751 int l = off;
0752 int n = off + len - 1;
0753 if (len > 40) { // Big arrays, pseudomedian of 9
0754 int s = len / 8;
0755 l = med3(x, l, l + s, l + 2 * s);
0756 m = med3(x, m - s, m, m + s);
0757 n = med3(x, n - 2 * s, n - s, n);
0758 }
0759 m = med3(x, l, m, n); // Mid-size, med of 3
0760 }
0761 char v = x[m];
0762
0763 // Establish Invariant: v* (<v)* (>v)* v*
0764 int a = off, b = a, c = off + len - 1, d = c;
0765 while (true) {
0766 while (b <= c && x[b] <= v) {
0767 if (x[b] == v)
0768 swap(x, a++, b);
0769 b++;
0770 }
0771 while (c >= b && x[c] >= v) {
0772 if (x[c] == v)
0773 swap(x, c, d--);
0774 c--;
0775 }
0776 if (b > c)
0777 break;
0778 swap(x, b++, c--);
0779 }
0780
0781 // Swap partition elements back to middle
0782 int s, n = off + len;
0783 s = Math.min(a - off, b - a);
0784 vecswap(x, off, b - s, s);
0785 s = Math.min(d - c, n - d - 1);
0786 vecswap(x, b, n - s, s);
0787
0788 // Recursively sort non-partition-elements
0789 if ((s = b - a) > 1)
0790 sort1(x, off, s);
0791 if ((s = d - c) > 1)
0792 sort1(x, n - s, s);
0793 }
0794
0795 /**
0796 * Swaps x[a] with x[b].
0797 */
0798 private static void swap(char x[], int a, int b) {
0799 char t = x[a];
0800 x[a] = x[b];
0801 x[b] = t;
0802 }
0803
0804 /**
0805 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
0806 */
0807 private static void vecswap(char x[], int a, int b, int n) {
0808 for (int i = 0; i < n; i++, a++, b++)
0809 swap(x, a, b);
0810 }
0811
0812 /**
0813 * Returns the index of the median of the three indexed chars.
0814 */
0815 private static int med3(char x[], int a, int b, int c) {
0816 return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
0817 : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
0818 }
0819
0820 /**
0821 * Sorts the specified sub-array of bytes into ascending order.
0822 */
0823 private static void sort1(byte x[], int off, int len) {
0824 // Insertion sort on smallest arrays
0825 if (len < 7) {
0826 for (int i = off; i < len + off; i++)
0827 for (int j = i; j > off && x[j - 1] > x[j]; j--)
0828 swap(x, j, j - 1);
0829 return;
0830 }
0831
0832 // Choose a partition element, v
0833 int m = off + (len >> 1); // Small arrays, middle element
0834 if (len > 7) {
0835 int l = off;
0836 int n = off + len - 1;
0837 if (len > 40) { // Big arrays, pseudomedian of 9
0838 int s = len / 8;
0839 l = med3(x, l, l + s, l + 2 * s);
0840 m = med3(x, m - s, m, m + s);
0841 n = med3(x, n - 2 * s, n - s, n);
0842 }
0843 m = med3(x, l, m, n); // Mid-size, med of 3
0844 }
0845 byte v = x[m];
0846
0847 // Establish Invariant: v* (<v)* (>v)* v*
0848 int a = off, b = a, c = off + len - 1, d = c;
0849 while (true) {
0850 while (b <= c && x[b] <= v) {
0851 if (x[b] == v)
0852 swap(x, a++, b);
0853 b++;
0854 }
0855 while (c >= b && x[c] >= v) {
0856 if (x[c] == v)
0857 swap(x, c, d--);
0858 c--;
0859 }
0860 if (b > c)
0861 break;
0862 swap(x, b++, c--);
0863 }
0864
0865 // Swap partition elements back to middle
0866 int s, n = off + len;
0867 s = Math.min(a - off, b - a);
0868 vecswap(x, off, b - s, s);
0869 s = Math.min(d - c, n - d - 1);
0870 vecswap(x, b, n - s, s);
0871
0872 // Recursively sort non-partition-elements
0873 if ((s = b - a) > 1)
0874 sort1(x, off, s);
0875 if ((s = d - c) > 1)
0876 sort1(x, n - s, s);
0877 }
0878
0879 /**
0880 * Swaps x[a] with x[b].
0881 */
0882 private static void swap(byte x[], int a, int b) {
0883 byte t = x[a];
0884 x[a] = x[b];
0885 x[b] = t;
0886 }
0887
0888 /**
0889 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
0890 */
0891 private static void vecswap(byte x[], int a, int b, int n) {
0892 for (int i = 0; i < n; i++, a++, b++)
0893 swap(x, a, b);
0894 }
0895
0896 /**
0897 * Returns the index of the median of the three indexed bytes.
0898 */
0899 private static int med3(byte x[], int a, int b, int c) {
0900 return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
0901 : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
0902 }
0903
0904 /**
0905 * Sorts the specified sub-array of doubles into ascending order.
0906 */
0907 private static void sort1(double x[], int off, int len) {
0908 // Insertion sort on smallest arrays
0909 if (len < 7) {
0910 for (int i = off; i < len + off; i++)
0911 for (int j = i; j > off && x[j - 1] > x[j]; j--)
0912 swap(x, j, j - 1);
0913 return;
0914 }
0915
0916 // Choose a partition element, v
0917 int m = off + (len >> 1); // Small arrays, middle element
0918 if (len > 7) {
0919 int l = off;
0920 int n = off + len - 1;
0921 if (len > 40) { // Big arrays, pseudomedian of 9
0922 int s = len / 8;
0923 l = med3(x, l, l + s, l + 2 * s);
0924 m = med3(x, m - s, m, m + s);
0925 n = med3(x, n - 2 * s, n - s, n);
0926 }
0927 m = med3(x, l, m, n); // Mid-size, med of 3
0928 }
0929 double v = x[m];
0930
0931 // Establish Invariant: v* (<v)* (>v)* v*
0932 int a = off, b = a, c = off + len - 1, d = c;
0933 while (true) {
0934 while (b <= c && x[b] <= v) {
0935 if (x[b] == v)
0936 swap(x, a++, b);
0937 b++;
0938 }
0939 while (c >= b && x[c] >= v) {
0940 if (x[c] == v)
0941 swap(x, c, d--);
0942 c--;
0943 }
0944 if (b > c)
0945 break;
0946 swap(x, b++, c--);
0947 }
0948
0949 // Swap partition elements back to middle
0950 int s, n = off + len;
0951 s = Math.min(a - off, b - a);
0952 vecswap(x, off, b - s, s);
0953 s = Math.min(d - c, n - d - 1);
0954 vecswap(x, b, n - s, s);
0955
0956 // Recursively sort non-partition-elements
0957 if ((s = b - a) > 1)
0958 sort1(x, off, s);
0959 if ((s = d - c) > 1)
0960 sort1(x, n - s, s);
0961 }
0962
0963 /**
0964 * Swaps x[a] with x[b].
0965 */
0966 private static void swap(double x[], int a, int b) {
0967 double t = x[a];
0968 x[a] = x[b];
0969 x[b] = t;
0970 }
0971
0972 /**
0973 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
0974 */
0975 private static void vecswap(double x[], int a, int b, int n) {
0976 for (int i = 0; i < n; i++, a++, b++)
0977 swap(x, a, b);
0978 }
0979
0980 /**
0981 * Returns the index of the median of the three indexed doubles.
0982 */
0983 private static int med3(double x[], int a, int b, int c) {
0984 return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
0985 : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
0986 }
0987
0988 /**
0989 * Sorts the specified sub-array of floats into ascending order.
0990 */
0991 private static void sort1(float x[], int off, int len) {
0992 // Insertion sort on smallest arrays
0993 if (len < 7) {
0994 for (int i = off; i < len + off; i++)
0995 for (int j = i; j > off && x[j - 1] > x[j]; j--)
0996 swap(x, j, j - 1);
0997 return;
0998 }
0999
1000 // Choose a partition element, v
1001 int m = off + (len >> 1); // Small arrays, middle element
1002 if (len > 7) {
1003 int l = off;
1004 int n = off + len - 1;
1005 if (len > 40) { // Big arrays, pseudomedian of 9
1006 int s = len / 8;
1007 l = med3(x, l, l + s, l + 2 * s);
1008 m = med3(x, m - s, m, m + s);
1009 n = med3(x, n - 2 * s, n - s, n);
1010 }
1011 m = med3(x, l, m, n); // Mid-size, med of 3
1012 }
1013 float v = x[m];
1014
1015 // Establish Invariant: v* (<v)* (>v)* v*
1016 int a = off, b = a, c = off + len - 1, d = c;
1017 while (true) {
1018 while (b <= c && x[b] <= v) {
1019 if (x[b] == v)
1020 swap(x, a++, b);
1021 b++;
1022 }
1023 while (c >= b && x[c] >= v) {
1024 if (x[c] == v)
1025 swap(x, c, d--);
1026 c--;
1027 }
1028 if (b > c)
1029 break;
1030 swap(x, b++, c--);
1031 }
1032
1033 // Swap partition elements back to middle
1034 int s, n = off + len;
1035 s = Math.min(a - off, b - a);
1036 vecswap(x, off, b - s, s);
1037 s = Math.min(d - c, n - d - 1);
1038 vecswap(x, b, n - s, s);
1039
1040 // Recursively sort non-partition-elements
1041 if ((s = b - a) > 1)
1042 sort1(x, off, s);
1043 if ((s = d - c) > 1)
1044 sort1(x, n - s, s);
1045 }
1046
1047 /**
1048 * Swaps x[a] with x[b].
1049 */
1050 private static void swap(float x[], int a, int b) {
1051 float t = x[a];
1052 x[a] = x[b];
1053 x[b] = t;
1054 }
1055
1056 /**
1057 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
1058 */
1059 private static void vecswap(float x[], int a, int b, int n) {
1060 for (int i = 0; i < n; i++, a++, b++)
1061 swap(x, a, b);
1062 }
1063
1064 /**
1065 * Returns the index of the median of the three indexed floats.
1066 */
1067 private static int med3(float x[], int a, int b, int c) {
1068 return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
1069 : (x[b] > x[c] ? b : x[a] > x[c] ? c : a));
1070 }
1071
1072 /**
1073 * Sorts the specified array of objects into ascending order, according to
1074 * the {@linkplain Comparable natural ordering}
1075 * of its elements. All elements in the array
1076 * must implement the {@link Comparable} interface. Furthermore, all
1077 * elements in the array must be <i>mutually comparable</i> (that is,
1078 * <tt>e1.compareTo(e2)</tt> must not throw a <tt>ClassCastException</tt>
1079 * for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<p>
1080 *
1081 * This sort is guaranteed to be <i>stable</i>: equal elements will
1082 * not be reordered as a result of the sort.<p>
1083 *
1084 * The sorting algorithm is a modified mergesort (in which the merge is
1085 * omitted if the highest element in the low sublist is less than the
1086 * lowest element in the high sublist). This algorithm offers guaranteed
1087 * n*log(n) performance.
1088 *
1089 * @param a the array to be sorted
1090 * @throws ClassCastException if the array contains elements that are not
1091 * <i>mutually comparable</i> (for example, strings and integers).
1092 */
1093 public static void sort(Object[] a) {
1094 Object[] aux = (Object[]) a.clone();
1095 mergeSort(aux, a, 0, a.length, 0);
1096 }
1097
1098 /**
1099 * Sorts the specified range of the specified array of objects into
1100 * ascending order, according to the
1101 * {@linkplain Comparable natural ordering} of its
1102 * elements. The range to be sorted extends from index
1103 * <tt>fromIndex</tt>, inclusive, to index <tt>toIndex</tt>, exclusive.
1104 * (If <tt>fromIndex==toIndex</tt>, the range to be sorted is empty.) All
1105 * elements in this range must implement the {@link Comparable}
1106 * interface. Furthermore, all elements in this range must be <i>mutually
1107 * comparable</i> (that is, <tt>e1.compareTo(e2)</tt> must not throw a
1108 * <tt>ClassCastException</tt> for any elements <tt>e1</tt> and
1109 * <tt>e2</tt> in the array).<p>
1110 *
1111 * This sort is guaranteed to be <i>stable</i>: equal elements will
1112 * not be reordered as a result of the sort.<p>
1113 *
1114 * The sorting algorithm is a modified mergesort (in which the merge is
1115 * omitted if the highest element in the low sublist is less than the
1116 * lowest element in the high sublist). This algorithm offers guaranteed
1117 * n*log(n) performance.
1118 *
1119 * @param a the array to be sorted
1120 * @param fromIndex the index of the first element (inclusive) to be
1121 * sorted
1122 * @param toIndex the index of the last element (exclusive) to be sorted
1123 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1124 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1125 * <tt>toIndex > a.length</tt>
1126 * @throws ClassCastException if the array contains elements that are
1127 * not <i>mutually comparable</i> (for example, strings and
1128 * integers).
1129 */
1130 public static void sort(Object[] a, int fromIndex, int toIndex) {
1131 rangeCheck(a.length, fromIndex, toIndex);
1132 Object[] aux = copyOfRange(a, fromIndex, toIndex);
1133 mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
1134 }
1135
1136 /**
1137 * Tuning parameter: list size at or below which insertion sort will be
1138 * used in preference to mergesort or quicksort.
1139 */
1140 private static final int INSERTIONSORT_THRESHOLD = 7;
1141
1142 /**
1143 * Src is the source array that starts at index 0
1144 * Dest is the (possibly larger) array destination with a possible offset
1145 * low is the index in dest to start sorting
1146 * high is the end index in dest to end sorting
1147 * off is the offset to generate corresponding low, high in src
1148 */
1149 private static void mergeSort(Object[] src, Object[] dest, int low,
1150 int high, int off) {
1151 int length = high - low;
1152
1153 // Insertion sort on smallest arrays
1154 if (length < INSERTIONSORT_THRESHOLD) {
1155 for (int i = low; i < high; i++)
1156 for (int j = i; j > low
1157 && ((Comparable) dest[j - 1])
1158 .compareTo(dest[j]) > 0; j--)
1159 swap(dest, j, j - 1);
1160 return;
1161 }
1162
1163 // Recursively sort halves of dest into src
1164 int destLow = low;
1165 int destHigh = high;
1166 low += off;
1167 high += off;
1168 int mid = (low + high) >>> 1;
1169 mergeSort(dest, src, low, mid, -off);
1170 mergeSort(dest, src, mid, high, -off);
1171
1172 // If list is already sorted, just copy from src to dest. This is an
1173 // optimization that results in faster sorts for nearly ordered lists.
1174 if (((Comparable) src[mid - 1]).compareTo(src[mid]) <= 0) {
1175 System.arraycopy(src, low, dest, destLow, length);
1176 return;
1177 }
1178
1179 // Merge sorted halves (now in src) into dest
1180 for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
1181 if (q >= high || p < mid
1182 && ((Comparable) src[p]).compareTo(src[q]) <= 0)
1183 dest[i] = src[p++];
1184 else
1185 dest[i] = src[q++];
1186 }
1187 }
1188
1189 /**
1190 * Swaps x[a] with x[b].
1191 */
1192 private static void swap(Object[] x, int a, int b) {
1193 Object t = x[a];
1194 x[a] = x[b];
1195 x[b] = t;
1196 }
1197
1198 /**
1199 * Sorts the specified array of objects according to the order induced by
1200 * the specified comparator. All elements in the array must be
1201 * <i>mutually comparable</i> by the specified comparator (that is,
1202 * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
1203 * for any elements <tt>e1</tt> and <tt>e2</tt> in the array).<p>
1204 *
1205 * This sort is guaranteed to be <i>stable</i>: equal elements will
1206 * not be reordered as a result of the sort.<p>
1207 *
1208 * The sorting algorithm is a modified mergesort (in which the merge is
1209 * omitted if the highest element in the low sublist is less than the
1210 * lowest element in the high sublist). This algorithm offers guaranteed
1211 * n*log(n) performance.
1212 *
1213 * @param a the array to be sorted
1214 * @param c the comparator to determine the order of the array. A
1215 * <tt>null</tt> value indicates that the elements'
1216 * {@linkplain Comparable natural ordering} should be used.
1217 * @throws ClassCastException if the array contains elements that are
1218 * not <i>mutually comparable</i> using the specified comparator.
1219 */
1220 public static <T> void sort(T[] a, Comparator<? super T> c) {
1221 T[] aux = (T[]) a.clone();
1222 if (c == null)
1223 mergeSort(aux, a, 0, a.length, 0);
1224 else
1225 mergeSort(aux, a, 0, a.length, 0, c);
1226 }
1227
1228 /**
1229 * Sorts the specified range of the specified array of objects according
1230 * to the order induced by the specified comparator. The range to be
1231 * sorted extends from index <tt>fromIndex</tt>, inclusive, to index
1232 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
1233 * range to be sorted is empty.) All elements in the range must be
1234 * <i>mutually comparable</i> by the specified comparator (that is,
1235 * <tt>c.compare(e1, e2)</tt> must not throw a <tt>ClassCastException</tt>
1236 * for any elements <tt>e1</tt> and <tt>e2</tt> in the range).<p>
1237 *
1238 * This sort is guaranteed to be <i>stable</i>: equal elements will
1239 * not be reordered as a result of the sort.<p>
1240 *
1241 * The sorting algorithm is a modified mergesort (in which the merge is
1242 * omitted if the highest element in the low sublist is less than the
1243 * lowest element in the high sublist). This algorithm offers guaranteed
1244 * n*log(n) performance.
1245 *
1246 * @param a the array to be sorted
1247 * @param fromIndex the index of the first element (inclusive) to be
1248 * sorted
1249 * @param toIndex the index of the last element (exclusive) to be sorted
1250 * @param c the comparator to determine the order of the array. A
1251 * <tt>null</tt> value indicates that the elements'
1252 * {@linkplain Comparable natural ordering} should be used.
1253 * @throws ClassCastException if the array contains elements that are not
1254 * <i>mutually comparable</i> using the specified comparator.
1255 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
1256 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
1257 * <tt>toIndex > a.length</tt>
1258 */
1259 public static <T> void sort(T[] a, int fromIndex, int toIndex,
1260 Comparator<? super T> c) {
1261 rangeCheck(a.length, fromIndex, toIndex);
1262 T[] aux = (T[]) copyOfRange(a, fromIndex, toIndex);
1263 if (c == null)
1264 mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
1265 else
1266 mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
1267 }
1268
1269 /**
1270 * Src is the source array that starts at index 0
1271 * Dest is the (possibly larger) array destination with a possible offset
1272 * low is the index in dest to start sorting
1273 * high is the end index in dest to end sorting
1274 * off is the offset into src corresponding to low in dest
1275 */
1276 private static void mergeSort(Object[] src, Object[] dest, int low,
1277 int high, int off, Comparator c) {
1278 int length = high - low;
1279
1280 // Insertion sort on smallest arrays
1281 if (length < INSERTIONSORT_THRESHOLD) {
1282 for (int i = low; i < high; i++)
1283 for (int j = i; j > low
1284 && c.compare(dest[j - 1], dest[j]) > 0; j--)
1285 swap(dest, j, j - 1);
1286 return;
1287 }
1288
1289 // Recursively sort halves of dest into src
1290 int destLow = low;
1291 int destHigh = high;
1292 low += off;
1293 high += off;
1294 int mid = (low + high) >>> 1;
1295 mergeSort(dest, src, low, mid, -off, c);
1296 mergeSort(dest, src, mid, high, -off, c);
1297
1298 // If list is already sorted, just copy from src to dest. This is an
1299 // optimization that results in faster sorts for nearly ordered lists.
1300 if (c.compare(src[mid - 1], src[mid]) <= 0) {
1301 System.arraycopy(src, low, dest, destLow, length);
1302 return;
1303 }
1304
1305 // Merge sorted halves (now in src) into dest
1306 for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
1307 if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
1308 dest[i] = src[p++];
1309 else
1310 dest[i] = src[q++];
1311 }
1312 }
1313
1314 /**
1315 * Check that fromIndex and toIndex are in range, and throw an
1316 * appropriate exception if they aren't.
1317 */
1318 private static void rangeCheck(int arrayLen, int fromIndex,
1319 int toIndex) {
1320 if (fromIndex > toIndex)
1321 throw new IllegalArgumentException("fromIndex(" + fromIndex
1322 + ") > toIndex(" + toIndex + ")");
1323 if (fromIndex < 0)
1324 throw new ArrayIndexOutOfBoundsException(fromIndex);
1325 if (toIndex > arrayLen)
1326 throw new ArrayIndexOutOfBoundsException(toIndex);
1327 }
1328
1329 // Searching
1330
1331 /**
1332 * Searches the specified array of longs for the specified value using the
1333 * binary search algorithm. The array must be sorted (as
1334 * by the {@link #sort(long[])} method) prior to making this call. If it
1335 * is not sorted, the results are undefined. If the array contains
1336 * multiple elements with the specified value, there is no guarantee which
1337 * one will be found.
1338 *
1339 * @param a the array to be searched
1340 * @param key the value to be searched for
1341 * @return index of the search key, if it is contained in the array;
1342 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1343 * <i>insertion point</i> is defined as the point at which the
1344 * key would be inserted into the array: the index of the first
1345 * element greater than the key, or <tt>a.length</tt> if all
1346 * elements in the array are less than the specified key. Note
1347 * that this guarantees that the return value will be >= 0 if
1348 * and only if the key is found.
1349 */
1350 public static int binarySearch(long[] a, long key) {
1351 return binarySearch0(a, 0, a.length, key);
1352 }
1353
1354 /**
1355 * Searches a range of
1356 * the specified array of longs for the specified value using the
1357 * binary search algorithm.
1358 * The range must be sorted (as
1359 * by the {@link #sort(long[], int, int)} method)
1360 * prior to making this call. If it
1361 * is not sorted, the results are undefined. If the range contains
1362 * multiple elements with the specified value, there is no guarantee which
1363 * one will be found.
1364 *
1365 * @param a the array to be searched
1366 * @param fromIndex the index of the first element (inclusive) to be
1367 * searched
1368 * @param toIndex the index of the last element (exclusive) to be searched
1369 * @param key the value to be searched for
1370 * @return index of the search key, if it is contained in the array
1371 * within the specified range;
1372 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1373 * <i>insertion point</i> is defined as the point at which the
1374 * key would be inserted into the array: the index of the first
1375 * element in the range greater than the key,
1376 * or <tt>toIndex</tt> if all
1377 * elements in the range are less than the specified key. Note
1378 * that this guarantees that the return value will be >= 0 if
1379 * and only if the key is found.
1380 * @throws IllegalArgumentException
1381 * if {@code fromIndex > toIndex}
1382 * @throws ArrayIndexOutOfBoundsException
1383 * if {@code fromIndex < 0 or toIndex > a.length}
1384 * @since 1.6
1385 */
1386 public static int binarySearch(long[] a, int fromIndex,
1387 int toIndex, long key) {
1388 rangeCheck(a.length, fromIndex, toIndex);
1389 return binarySearch0(a, fromIndex, toIndex, key);
1390 }
1391
1392 // Like public version, but without range checks.
1393 private static int binarySearch0(long[] a, int fromIndex,
1394 int toIndex, long key) {
1395 int low = fromIndex;
1396 int high = toIndex - 1;
1397
1398 while (low <= high) {
1399 int mid = (low + high) >>> 1;
1400 long midVal = a[mid];
1401
1402 if (midVal < key)
1403 low = mid + 1;
1404 else if (midVal > key)
1405 high = mid - 1;
1406 else
1407 return mid; // key found
1408 }
1409 return -(low + 1); // key not found.
1410 }
1411
1412 /**
1413 * Searches the specified array of ints for the specified value using the
1414 * binary search algorithm. The array must be sorted (as
1415 * by the {@link #sort(int[])} method) prior to making this call. If it
1416 * is not sorted, the results are undefined. If the array contains
1417 * multiple elements with the specified value, there is no guarantee which
1418 * one will be found.
1419 *
1420 * @param a the array to be searched
1421 * @param key the value to be searched for
1422 * @return index of the search key, if it is contained in the array;
1423 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1424 * <i>insertion point</i> is defined as the point at which the
1425 * key would be inserted into the array: the index of the first
1426 * element greater than the key, or <tt>a.length</tt> if all
1427 * elements in the array are less than the specified key. Note
1428 * that this guarantees that the return value will be >= 0 if
1429 * and only if the key is found.
1430 */
1431 public static int binarySearch(int[] a, int key) {
1432 return binarySearch0(a, 0, a.length, key);
1433 }
1434
1435 /**
1436 * Searches a range of
1437 * the specified array of ints for the specified value using the
1438 * binary search algorithm.
1439 * The range must be sorted (as
1440 * by the {@link #sort(int[], int, int)} method)
1441 * prior to making this call. If it
1442 * is not sorted, the results are undefined. If the range contains
1443 * multiple elements with the specified value, there is no guarantee which
1444 * one will be found.
1445 *
1446 * @param a the array to be searched
1447 * @param fromIndex the index of the first element (inclusive) to be
1448 * searched
1449 * @param toIndex the index of the last element (exclusive) to be searched
1450 * @param key the value to be searched for
1451 * @return index of the search key, if it is contained in the array
1452 * within the specified range;
1453 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1454 * <i>insertion point</i> is defined as the point at which the
1455 * key would be inserted into the array: the index of the first
1456 * element in the range greater than the key,
1457 * or <tt>toIndex</tt> if all
1458 * elements in the range are less than the specified key. Note
1459 * that this guarantees that the return value will be >= 0 if
1460 * and only if the key is found.
1461 * @throws IllegalArgumentException
1462 * if {@code fromIndex > toIndex}
1463 * @throws ArrayIndexOutOfBoundsException
1464 * if {@code fromIndex < 0 or toIndex > a.length}
1465 * @since 1.6
1466 */
1467 public static int binarySearch(int[] a, int fromIndex, int toIndex,
1468 int key) {
1469 rangeCheck(a.length, fromIndex, toIndex);
1470 return binarySearch0(a, fromIndex, toIndex, key);
1471 }
1472
1473 // Like public version, but without range checks.
1474 private static int binarySearch0(int[] a, int fromIndex,
1475 int toIndex, int key) {
1476 int low = fromIndex;
1477 int high = toIndex - 1;
1478
1479 while (low <= high) {
1480 int mid = (low + high) >>> 1;
1481 int midVal = a[mid];
1482
1483 if (midVal < key)
1484 low = mid + 1;
1485 else if (midVal > key)
1486 high = mid - 1;
1487 else
1488 return mid; // key found
1489 }
1490 return -(low + 1); // key not found.
1491 }
1492
1493 /**
1494 * Searches the specified array of shorts for the specified value using
1495 * the binary search algorithm. The array must be sorted
1496 * (as by the {@link #sort(short[])} method) prior to making this call. If
1497 * it is not sorted, the results are undefined. If the array contains
1498 * multiple elements with the specified value, there is no guarantee which
1499 * one will be found.
1500 *
1501 * @param a the array to be searched
1502 * @param key the value to be searched for
1503 * @return index of the search key, if it is contained in the array;
1504 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1505 * <i>insertion point</i> is defined as the point at which the
1506 * key would be inserted into the array: the index of the first
1507 * element greater than the key, or <tt>a.length</tt> if all
1508 * elements in the array are less than the specified key. Note
1509 * that this guarantees that the return value will be >= 0 if
1510 * and only if the key is found.
1511 */
1512 public static int binarySearch(short[] a, short key) {
1513 return binarySearch0(a, 0, a.length, key);
1514 }
1515
1516 /**
1517 * Searches a range of
1518 * the specified array of shorts for the specified value using
1519 * the binary search algorithm.
1520 * The range must be sorted
1521 * (as by the {@link #sort(short[], int, int)} method)
1522 * prior to making this call. If
1523 * it is not sorted, the results are undefined. If the range contains
1524 * multiple elements with the specified value, there is no guarantee which
1525 * one will be found.
1526 *
1527 * @param a the array to be searched
1528 * @param fromIndex the index of the first element (inclusive) to be
1529 * searched
1530 * @param toIndex the index of the last element (exclusive) to be searched
1531 * @param key the value to be searched for
1532 * @return index of the search key, if it is contained in the array
1533 * within the specified range;
1534 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1535 * <i>insertion point</i> is defined as the point at which the
1536 * key would be inserted into the array: the index of the first
1537 * element in the range greater than the key,
1538 * or <tt>toIndex</tt> if all
1539 * elements in the range are less than the specified key. Note
1540 * that this guarantees that the return value will be >= 0 if
1541 * and only if the key is found.
1542 * @throws IllegalArgumentException
1543 * if {@code fromIndex > toIndex}
1544 * @throws ArrayIndexOutOfBoundsException
1545 * if {@code fromIndex < 0 or toIndex > a.length}
1546 * @since 1.6
1547 */
1548 public static int binarySearch(short[] a, int fromIndex,
1549 int toIndex, short key) {
1550 rangeCheck(a.length, fromIndex, toIndex);
1551 return binarySearch0(a, fromIndex, toIndex, key);
1552 }
1553
1554 // Like public version, but without range checks.
1555 private static int binarySearch0(short[] a, int fromIndex,
1556 int toIndex, short key) {
1557 int low = fromIndex;
1558 int high = toIndex - 1;
1559
1560 while (low <= high) {
1561 int mid = (low + high) >>> 1;
1562 short midVal = a[mid];
1563
1564 if (midVal < key)
1565 low = mid + 1;
1566 else if (midVal > key)
1567 high = mid - 1;
1568 else
1569 return mid; // key found
1570 }
1571 return -(low + 1); // key not found.
1572 }
1573
1574 /**
1575 * Searches the specified array of chars for the specified value using the
1576 * binary search algorithm. The array must be sorted (as
1577 * by the {@link #sort(char[])} method) prior to making this call. If it
1578 * is not sorted, the results are undefined. If the array contains
1579 * multiple elements with the specified value, there is no guarantee which
1580 * one will be found.
1581 *
1582 * @param a the array to be searched
1583 * @param key the value to be searched for
1584 * @return index of the search key, if it is contained in the array;
1585 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1586 * <i>insertion point</i> is defined as the point at which the
1587 * key would be inserted into the array: the index of the first
1588 * element greater than the key, or <tt>a.length</tt> if all
1589 * elements in the array are less than the specified key. Note
1590 * that this guarantees that the return value will be >= 0 if
1591 * and only if the key is found.
1592 */
1593 public static int binarySearch(char[] a, char key) {
1594 return binarySearch0(a, 0, a.length, key);
1595 }
1596
1597 /**
1598 * Searches a range of
1599 * the specified array of chars for the specified value using the
1600 * binary search algorithm.
1601 * The range must be sorted (as
1602 * by the {@link #sort(char[], int, int)} method)
1603 * prior to making this call. If it
1604 * is not sorted, the results are undefined. If the range contains
1605 * multiple elements with the specified value, there is no guarantee which
1606 * one will be found.
1607 *
1608 * @param a the array to be searched
1609 * @param fromIndex the index of the first element (inclusive) to be
1610 * searched
1611 * @param toIndex the index of the last element (exclusive) to be searched
1612 * @param key the value to be searched for
1613 * @return index of the search key, if it is contained in the array
1614 * within the specified range;
1615 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1616 * <i>insertion point</i> is defined as the point at which the
1617 * key would be inserted into the array: the index of the first
1618 * element in the range greater than the key,
1619 * or <tt>toIndex</tt> if all
1620 * elements in the range are less than the specified key. Note
1621 * that this guarantees that the return value will be >= 0 if
1622 * and only if the key is found.
1623 * @throws IllegalArgumentException
1624 * if {@code fromIndex > toIndex}
1625 * @throws ArrayIndexOutOfBoundsException
1626 * if {@code fromIndex < 0 or toIndex > a.length}
1627 * @since 1.6
1628 */
1629 public static int binarySearch(char[] a, int fromIndex,
1630 int toIndex, char key) {
1631 rangeCheck(a.length, fromIndex, toIndex);
1632 return binarySearch0(a, fromIndex, toIndex, key);
1633 }
1634
1635 // Like public version, but without range checks.
1636 private static int binarySearch0(char[] a, int fromIndex,
1637 int toIndex, char key) {
1638 int low = fromIndex;
1639 int high = toIndex - 1;
1640
1641 while (low <= high) {
1642 int mid = (low + high) >>> 1;
1643 char midVal = a[mid];
1644
1645 if (midVal < key)
1646 low = mid + 1;
1647 else if (midVal > key)
1648 high = mid - 1;
1649 else
1650 return mid; // key found
1651 }
1652 return -(low + 1); // key not found.
1653 }
1654
1655 /**
1656 * Searches the specified array of bytes for the specified value using the
1657 * binary search algorithm. The array must be sorted (as
1658 * by the {@link #sort(byte[])} method) prior to making this call. If it
1659 * is not sorted, the results are undefined. If the array contains
1660 * multiple elements with the specified value, there is no guarantee which
1661 * one will be found.
1662 *
1663 * @param a the array to be searched
1664 * @param key the value to be searched for
1665 * @return index of the search key, if it is contained in the array;
1666 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1667 * <i>insertion point</i> is defined as the point at which the
1668 * key would be inserted into the array: the index of the first
1669 * element greater than the key, or <tt>a.length</tt> if all
1670 * elements in the array are less than the specified key. Note
1671 * that this guarantees that the return value will be >= 0 if
1672 * and only if the key is found.
1673 */
1674 public static int binarySearch(byte[] a, byte key) {
1675 return binarySearch0(a, 0, a.length, key);
1676 }
1677
1678 /**
1679 * Searches a range of
1680 * the specified array of bytes for the specified value using the
1681 * binary search algorithm.
1682 * The range must be sorted (as
1683 * by the {@link #sort(byte[], int, int)} method)
1684 * prior to making this call. If it
1685 * is not sorted, the results are undefined. If the range contains
1686 * multiple elements with the specified value, there is no guarantee which
1687 * one will be found.
1688 *
1689 * @param a the array to be searched
1690 * @param fromIndex the index of the first element (inclusive) to be
1691 * searched
1692 * @param toIndex the index of the last element (exclusive) to be searched
1693 * @param key the value to be searched for
1694 * @return index of the search key, if it is contained in the array
1695 * within the specified range;
1696 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1697 * <i>insertion point</i> is defined as the point at which the
1698 * key would be inserted into the array: the index of the first
1699 * element in the range greater than the key,
1700 * or <tt>toIndex</tt> if all
1701 * elements in the range are less than the specified key. Note
1702 * that this guarantees that the return value will be >= 0 if
1703 * and only if the key is found.
1704 * @throws IllegalArgumentException
1705 * if {@code fromIndex > toIndex}
1706 * @throws ArrayIndexOutOfBoundsException
1707 * if {@code fromIndex < 0 or toIndex > a.length}
1708 * @since 1.6
1709 */
1710 public static int binarySearch(byte[] a, int fromIndex,
1711 int toIndex, byte key) {
1712 rangeCheck(a.length, fromIndex, toIndex);
1713 return binarySearch0(a, fromIndex, toIndex, key);
1714 }
1715
1716 // Like public version, but without range checks.
1717 private static int binarySearch0(byte[] a, int fromIndex,
1718 int toIndex, byte key) {
1719 int low = fromIndex;
1720 int high = toIndex - 1;
1721
1722 while (low <= high) {
1723 int mid = (low + high) >>> 1;
1724 byte midVal = a[mid];
1725
1726 if (midVal < key)
1727 low = mid + 1;
1728 else if (midVal > key)
1729 high = mid - 1;
1730 else
1731 return mid; // key found
1732 }
1733 return -(low + 1); // key not found.
1734 }
1735
1736 /**
1737 * Searches the specified array of doubles for the specified value using
1738 * the binary search algorithm. The array must be sorted
1739 * (as by the {@link #sort(double[])} method) prior to making this call.
1740 * If it is not sorted, the results are undefined. If the array contains
1741 * multiple elements with the specified value, there is no guarantee which
1742 * one will be found. This method considers all NaN values to be
1743 * equivalent and equal.
1744 *
1745 * @param a the array to be searched
1746 * @param key the value to be searched for
1747 * @return index of the search key, if it is contained in the array;
1748 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1749 * <i>insertion point</i> is defined as the point at which the
1750 * key would be inserted into the array: the index of the first
1751 * element greater than the key, or <tt>a.length</tt> if all
1752 * elements in the array are less than the specified key. Note
1753 * that this guarantees that the return value will be >= 0 if
1754 * and only if the key is found.
1755 */
1756 public static int binarySearch(double[] a, double key) {
1757 return binarySearch0(a, 0, a.length, key);
1758 }
1759
1760 /**
1761 * Searches a range of
1762 * the specified array of doubles for the specified value using
1763 * the binary search algorithm.
1764 * The range must be sorted
1765 * (as by the {@link #sort(double[], int, int)} method)
1766 * prior to making this call.
1767 * If it is not sorted, the results are undefined. If the range contains
1768 * multiple elements with the specified value, there is no guarantee which
1769 * one will be found. This method considers all NaN values to be
1770 * equivalent and equal.
1771 *
1772 * @param a the array to be searched
1773 * @param fromIndex the index of the first element (inclusive) to be
1774 * searched
1775 * @param toIndex the index of the last element (exclusive) to be searched
1776 * @param key the value to be searched for
1777 * @return index of the search key, if it is contained in the array
1778 * within the specified range;
1779 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1780 * <i>insertion point</i> is defined as the point at which the
1781 * key would be inserted into the array: the index of the first
1782 * element in the range greater than the key,
1783 * or <tt>toIndex</tt> if all
1784 * elements in the range are less than the specified key. Note
1785 * that this guarantees that the return value will be >= 0 if
1786 * and only if the key is found.
1787 * @throws IllegalArgumentException
1788 * if {@code fromIndex > toIndex}
1789 * @throws ArrayIndexOutOfBoundsException
1790 * if {@code fromIndex < 0 or toIndex > a.length}
1791 * @since 1.6
1792 */
1793 public static int binarySearch(double[] a, int fromIndex,
1794 int toIndex, double key) {
1795 rangeCheck(a.length, fromIndex, toIndex);
1796 return binarySearch0(a, fromIndex, toIndex, key);
1797 }
1798
1799 // Like public version, but without range checks.
1800 private static int binarySearch0(double[] a, int fromIndex,
1801 int toIndex, double key) {
1802 int low = fromIndex;
1803 int high = toIndex - 1;
1804
1805 while (low <= high) {
1806 int mid = (low + high) >>> 1;
1807 double midVal = a[mid];
1808
1809 int cmp;
1810 if (midVal < key) {
1811 cmp = -1; // Neither val is NaN, thisVal is smaller
1812 } else if (midVal > key) {
1813 cmp = 1; // Neither val is NaN, thisVal is larger
1814 } else {
1815 long midBits = Double.doubleToLongBits(midVal);
1816 long keyBits = Double.doubleToLongBits(key);
1817 cmp = (midBits == keyBits ? 0 : // Values are equal
1818 (midBits < keyBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
1819 1)); // (0.0, -0.0) or (NaN, !NaN)
1820 }
1821
1822 if (cmp < 0)
1823 low = mid + 1;
1824 else if (cmp > 0)
1825 high = mid - 1;
1826 else
1827 return mid; // key found
1828 }
1829 return -(low + 1); // key not found.
1830 }
1831
1832 /**
1833 * Searches the specified array of floats for the specified value using
1834 * the binary search algorithm. The array must be sorted
1835 * (as by the {@link #sort(float[])} method) prior to making this call. If
1836 * it is not sorted, the results are undefined. If the array contains
1837 * multiple elements with the specified value, there is no guarantee which
1838 * one will be found. This method considers all NaN values to be
1839 * equivalent and equal.
1840 *
1841 * @param a the array to be searched
1842 * @param key the value to be searched for
1843 * @return index of the search key, if it is contained in the array;
1844 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1845 * <i>insertion point</i> is defined as the point at which the
1846 * key would be inserted into the array: the index of the first
1847 * element greater than the key, or <tt>a.length</tt> if all
1848 * elements in the array are less than the specified key. Note
1849 * that this guarantees that the return value will be >= 0 if
1850 * and only if the key is found.
1851 */
1852 public static int binarySearch(float[] a, float key) {
1853 return binarySearch0(a, 0, a.length, key);
1854 }
1855
1856 /**
1857 * Searches a range of
1858 * the specified array of floats for the specified value using
1859 * the binary search algorithm.
1860 * The range must be sorted
1861 * (as by the {@link #sort(float[], int, int)} method)
1862 * prior to making this call. If
1863 * it is not sorted, the results are undefined. If the range contains
1864 * multiple elements with the specified value, there is no guarantee which
1865 * one will be found. This method considers all NaN values to be
1866 * equivalent and equal.
1867 *
1868 * @param a the array to be searched
1869 * @param fromIndex the index of the first element (inclusive) to be
1870 * searched
1871 * @param toIndex the index of the last element (exclusive) to be searched
1872 * @param key the value to be searched for
1873 * @return index of the search key, if it is contained in the array
1874 * within the specified range;
1875 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1876 * <i>insertion point</i> is defined as the point at which the
1877 * key would be inserted into the array: the index of the first
1878 * element in the range greater than the key,
1879 * or <tt>toIndex</tt> if all
1880 * elements in the range are less than the specified key. Note
1881 * that this guarantees that the return value will be >= 0 if
1882 * and only if the key is found.
1883 * @throws IllegalArgumentException
1884 * if {@code fromIndex > toIndex}
1885 * @throws ArrayIndexOutOfBoundsException
1886 * if {@code fromIndex < 0 or toIndex > a.length}
1887 * @since 1.6
1888 */
1889 public static int binarySearch(float[] a, int fromIndex,
1890 int toIndex, float key) {
1891 rangeCheck(a.length, fromIndex, toIndex);
1892 return binarySearch0(a, fromIndex, toIndex, key);
1893 }
1894
1895 // Like public version, but without range checks.
1896 private static int binarySearch0(float[] a, int fromIndex,
1897 int toIndex, float key) {
1898 int low = fromIndex;
1899 int high = toIndex - 1;
1900
1901 while (low <= high) {
1902 int mid = (low + high) >>> 1;
1903 float midVal = a[mid];
1904
1905 int cmp;
1906 if (midVal < key) {
1907 cmp = -1; // Neither val is NaN, thisVal is smaller
1908 } else if (midVal > key) {
1909 cmp = 1; // Neither val is NaN, thisVal is larger
1910 } else {
1911 int midBits = Float.floatToIntBits(midVal);
1912 int keyBits = Float.floatToIntBits(key);
1913 cmp = (midBits == keyBits ? 0 : // Values are equal
1914 (midBits < keyBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
1915 1)); // (0.0, -0.0) or (NaN, !NaN)
1916 }
1917
1918 if (cmp < 0)
1919 low = mid + 1;
1920 else if (cmp > 0)
1921 high = mid - 1;
1922 else
1923 return mid; // key found
1924 }
1925 return -(low + 1); // key not found.
1926 }
1927
1928 /**
1929 * Searches the specified array for the specified object using the binary
1930 * search algorithm. The array must be sorted into ascending order
1931 * according to the
1932 * {@linkplain Comparable natural ordering}
1933 * of its elements (as by the
1934 * {@link #sort(Object[])} method) prior to making this call.
1935 * If it is not sorted, the results are undefined.
1936 * (If the array contains elements that are not mutually comparable (for
1937 * example, strings and integers), it <i>cannot</i> be sorted according
1938 * to the natural ordering of its elements, hence results are undefined.)
1939 * If the array contains multiple
1940 * elements equal to the specified object, there is no guarantee which
1941 * one will be found.
1942 *
1943 * @param a the array to be searched
1944 * @param key the value to be searched for
1945 * @return index of the search key, if it is contained in the array;
1946 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1947 * <i>insertion point</i> is defined as the point at which the
1948 * key would be inserted into the array: the index of the first
1949 * element greater than the key, or <tt>a.length</tt> if all
1950 * elements in the array are less than the specified key. Note
1951 * that this guarantees that the return value will be >= 0 if
1952 * and only if the key is found.
1953 * @throws ClassCastException if the search key is not comparable to the
1954 * elements of the array.
1955 */
1956 public static int binarySearch(Object[] a, Object key) {
1957 return binarySearch0(a, 0, a.length, key);
1958 }
1959
1960 /**
1961 * Searches a range of
1962 * the specified array for the specified object using the binary
1963 * search algorithm.
1964 * The range must be sorted into ascending order
1965 * according to the
1966 * {@linkplain Comparable natural ordering}
1967 * of its elements (as by the
1968 * {@link #sort(Object[], int, int)} method) prior to making this
1969 * call. If it is not sorted, the results are undefined.
1970 * (If the range contains elements that are not mutually comparable (for
1971 * example, strings and integers), it <i>cannot</i> be sorted according
1972 * to the natural ordering of its elements, hence results are undefined.)
1973 * If the range contains multiple
1974 * elements equal to the specified object, there is no guarantee which
1975 * one will be found.
1976 *
1977 * @param a the array to be searched
1978 * @param fromIndex the index of the first element (inclusive) to be
1979 * searched
1980 * @param toIndex the index of the last element (exclusive) to be searched
1981 * @param key the value to be searched for
1982 * @return index of the search key, if it is contained in the array
1983 * within the specified range;
1984 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
1985 * <i>insertion point</i> is defined as the point at which the
1986 * key would be inserted into the array: the index of the first
1987 * element in the range greater than the key,
1988 * or <tt>toIndex</tt> if all
1989 * elements in the range are less than the specified key. Note
1990 * that this guarantees that the return value will be >= 0 if
1991 * and only if the key is found.
1992 * @throws ClassCastException if the search key is not comparable to the
1993 * elements of the array within the specified range.
1994 * @throws IllegalArgumentException
1995 * if {@code fromIndex > toIndex}
1996 * @throws ArrayIndexOutOfBoundsException
1997 * if {@code fromIndex < 0 or toIndex > a.length}
1998 * @since 1.6
1999 */
2000 public static int binarySearch(Object[] a, int fromIndex,
2001 int toIndex, Object key) {
2002 rangeCheck(a.length, fromIndex, toIndex);
2003 return binarySearch0(a, fromIndex, toIndex, key);
2004 }
2005
2006 // Like public version, but without range checks.
2007 private static int binarySearch0(Object[] a, int fromIndex,
2008 int toIndex, Object key) {
2009 int low = fromIndex;
2010 int high = toIndex - 1;
2011
2012 while (low <= high) {
2013 int mid = (low + high) >>> 1;
2014 Comparable midVal = (Comparable) a[mid];
2015 int cmp = midVal.compareTo(key);
2016
2017 if (cmp < 0)
2018 low = mid + 1;
2019 else if (cmp > 0)
2020 high = mid - 1;
2021 else
2022 return mid; // key found
2023 }
2024 return -(low + 1); // key not found.
2025 }
2026
2027 /**
2028 * Searches the specified array for the specified object using the binary
2029 * search algorithm. The array must be sorted into ascending order
2030 * according to the specified comparator (as by the
2031 * {@link #sort(Object[], Comparator) sort(T[], Comparator)}
2032 * method) prior to making this call. If it is
2033 * not sorted, the results are undefined.
2034 * If the array contains multiple
2035 * elements equal to the specified object, there is no guarantee which one
2036 * will be found.
2037 *
2038 * @param a the array to be searched
2039 * @param key the value to be searched for
2040 * @param c the comparator by which the array is ordered. A
2041 * <tt>null</tt> value indicates that the elements'
2042 * {@linkplain Comparable natural ordering} should be used.
2043 * @return index of the search key, if it is contained in the array;
2044 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
2045 * <i>insertion point</i> is defined as the point at which the
2046 * key would be inserted into the array: the index of the first
2047 * element greater than the key, or <tt>a.length</tt> if all
2048 * elements in the array are less than the specified key. Note
2049 * that this guarantees that the return value will be >= 0 if
2050 * and only if the key is found.
2051 * @throws ClassCastException if the array contains elements that are not
2052 * <i>mutually comparable</i> using the specified comparator,
2053 * or the search key is not comparable to the
2054 * elements of the array using this comparator.
2055 */
2056 public static <T> int binarySearch(T[] a, T key,
2057 Comparator<? super T> c) {
2058 return binarySearch0(a, 0, a.length, key, c);
2059 }
2060
2061 /**
2062 * Searches a range of
2063 * the specified array for the specified object using the binary
2064 * search algorithm.
2065 * The range must be sorted into ascending order
2066 * according to the specified comparator (as by the
2067 * {@link #sort(Object[], int, int, Comparator)
2068 * sort(T[], int, int, Comparator)}
2069 * method) prior to making this call.
2070 * If it is not sorted, the results are undefined.
2071 * If the range contains multiple elements equal to the specified object,
2072 * there is no guarantee which one will be found.
2073 *
2074 * @param a the array to be searched
2075 * @param fromIndex the index of the first element (inclusive) to be
2076 * searched
2077 * @param toIndex the index of the last element (exclusive) to be searched
2078 * @param key the value to be searched for
2079 * @param c the comparator by which the array is ordered. A
2080 * <tt>null</tt> value indicates that the elements'
2081 * {@linkplain Comparable natural ordering} should be used.
2082 * @return index of the search key, if it is contained in the array
2083 * within the specified range;
2084 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
2085 * <i>insertion point</i> is defined as the point at which the
2086 * key would be inserted into the array: the index of the first
2087 * element in the range greater than the key,
2088 * or <tt>toIndex</tt> if all
2089 * elements in the range are less than the specified key. Note
2090 * that this guarantees that the return value will be >= 0 if
2091 * and only if the key is found.
2092 * @throws ClassCastException if the range contains elements that are not
2093 * <i>mutually comparable</i> using the specified comparator,
2094 * or the search key is not comparable to the
2095 * elements in the range using this comparator.
2096 * @throws IllegalArgumentException
2097 * if {@code fromIndex > toIndex}
2098 * @throws ArrayIndexOutOfBoundsException
2099 * if {@code fromIndex < 0 or toIndex > a.length}
2100 * @since 1.6
2101 */
2102 public static <T> int binarySearch(T[] a, int fromIndex,
2103 int toIndex, T key, Comparator<? super T> c) {
2104 rangeCheck(a.length, fromIndex, toIndex);
2105 return binarySearch0(a, fromIndex, toIndex, key, c);
2106 }
2107
2108 // Like public version, but without range checks.
2109 private static <T> int binarySearch0(T[] a, int fromIndex,
2110 int toIndex, T key, Comparator<? super T> c) {
2111 if (c == null) {
2112 return binarySearch0(a, fromIndex, toIndex, key);
2113 }
2114 int low = fromIndex;
2115 int high = toIndex - 1;
2116
2117 while (low <= high) {
2118 int mid = (low + high) >>> 1;
2119 T midVal = a[mid];
2120 int cmp = c.compare(midVal, key);
2121
2122 if (cmp < 0)
2123 low = mid + 1;
2124 else if (cmp > 0)
2125 high = mid - 1;
2126 else
2127 return mid; // key found
2128 }
2129 return -(low + 1); // key not found.
2130 }
2131
2132 // Equality Testing
2133
2134 /**
2135 * Returns <tt>true</tt> if the two specified arrays of longs are
2136 * <i>equal</i> to one another. Two arrays are considered equal if both
2137 * arrays contain the same number of elements, and all corresponding pairs
2138 * of elements in the two arrays are equal. In other words, two arrays
2139 * are equal if they contain the same elements in the same order. Also,
2140 * two array references are considered equal if both are <tt>null</tt>.<p>
2141 *
2142 * @param a one array to be tested for equality
2143 * @param a2 the other array to be tested for equality
2144 * @return <tt>true</tt> if the two arrays are equal
2145 */
2146 public static boolean equals(long[] a, long[] a2) {
2147 if (a == a2)
2148 return true;
2149 if (a == null || a2 == null)
2150 return false;
2151
2152 int length = a.length;
2153 if (a2.length != length)
2154 return false;
2155
2156 for (int i = 0; i < length; i++)
2157 if (a[i] != a2[i])
2158 return false;
2159
2160 return true;
2161 }
2162
2163 /**
2164 * Returns <tt>true</tt> if the two specified arrays of ints are
2165 * <i>equal</i> to one another. Two arrays are considered equal if both
2166 * arrays contain the same number of elements, and all corresponding pairs
2167 * of elements in the two arrays are equal. In other words, two arrays
2168 * are equal if they contain the same elements in the same order. Also,
2169 * two array references are considered equal if both are <tt>null</tt>.<p>
2170 *
2171 * @param a one array to be tested for equality
2172 * @param a2 the other array to be tested for equality
2173 * @return <tt>true</tt> if the two arrays are equal
2174 */
2175 public static boolean equals(int[] a, int[] a2) {
2176 if (a == a2)
2177 return true;
2178 if (a == null || a2 == null)
2179 return false;
2180
2181 int length = a.length;
2182 if (a2.length != length)
2183 return false;
2184
2185 for (int i = 0; i < length; i++)
2186 if (a[i] != a2[i])
2187 return false;
2188
2189 return true;
2190 }
2191
2192 /**
2193 * Returns <tt>true</tt> if the two specified arrays of shorts are
2194 * <i>equal</i> to one another. Two arrays are considered equal if both
2195 * arrays contain the same number of elements, and all corresponding pairs
2196 * of elements in the two arrays are equal. In other words, two arrays
2197 * are equal if they contain the same elements in the same order. Also,
2198 * two array references are considered equal if both are <tt>null</tt>.<p>
2199 *
2200 * @param a one array to be tested for equality
2201 * @param a2 the other array to be tested for equality
2202 * @return <tt>true</tt> if the two arrays are equal
2203 */
2204 public static boolean equals(short[] a, short a2[]) {
2205 if (a == a2)
2206 return true;
2207 if (a == null || a2 == null)
2208 return false;
2209
2210 int length = a.length;
2211 if (a2.length != length)
2212 return false;
2213
2214 for (int i = 0; i < length; i++)
2215 if (a[i] != a2[i])
2216 return false;
2217
2218 return true;
2219 }
2220
2221 /**
2222 * Returns <tt>true</tt> if the two specified arrays of chars are
2223 * <i>equal</i> to one another. Two arrays are considered equal if both
2224 * arrays contain the same number of elements, and all corresponding pairs
2225 * of elements in the two arrays are equal. In other words, two arrays
2226 * are equal if they contain the same elements in the same order. Also,
2227 * two array references are considered equal if both are <tt>null</tt>.<p>
2228 *
2229 * @param a one array to be tested for equality
2230 * @param a2 the other array to be tested for equality
2231 * @return <tt>true</tt> if the two arrays are equal
2232 */
2233 public static boolean equals(char[] a, char[] a2) {
2234 if (a == a2)
2235 return true;
2236 if (a == null || a2 == null)
2237 return false;
2238
2239 int length = a.length;
2240 if (a2.length != length)
2241 return false;
2242
2243 for (int i = 0; i < length; i++)
2244 if (a[i] != a2[i])
2245 return false;
2246
2247 return true;
2248 }
2249
2250 /**
2251 * Returns <tt>true</tt> if the two specified arrays of bytes are
2252 * <i>equal</i> to one another. Two arrays are considered equal if both
2253 * arrays contain the same number of elements, and all corresponding pairs
2254 * of elements in the two arrays are equal. In other words, two arrays
2255 * are equal if they contain the same elements in the same order. Also,
2256 * two array references are considered equal if both are <tt>null</tt>.<p>
2257 *
2258 * @param a one array to be tested for equality
2259 * @param a2 the other array to be tested for equality
2260 * @return <tt>true</tt> if the two arrays are equal
2261 */
2262 public static boolean equals(byte[] a, byte[] a2) {
2263 if (a == a2)
2264 return true;
2265 if (a == null || a2 == null)
2266 return false;
2267
2268 int length = a.length;
2269 if (a2.length != length)
2270 return false;
2271
2272 for (int i = 0; i < length; i++)
2273 if (a[i] != a2[i])
2274 return false;
2275
2276 return true;
2277 }
2278
2279 /**
2280 * Returns <tt>true</tt> if the two specified arrays of booleans are
2281 * <i>equal</i> to one another. Two arrays are considered equal if both
2282 * arrays contain the same number of elements, and all corresponding pairs
2283 * of elements in the two arrays are equal. In other words, two arrays
2284 * are equal if they contain the same elements in the same order. Also,
2285 * two array references are considered equal if both are <tt>null</tt>.<p>
2286 *
2287 * @param a one array to be tested for equality
2288 * @param a2 the other array to be tested for equality
2289 * @return <tt>true</tt> if the two arrays are equal
2290 */
2291 public static boolean equals(boolean[] a, boolean[] a2) {
2292 if (a == a2)
2293 return true;
2294 if (a == null || a2 == null)
2295 return false;
2296
2297 int length = a.length;
2298 if (a2.length != length)
2299 return false;
2300
2301 for (int i = 0; i < length; i++)
2302 if (a[i] != a2[i])
2303 return false;
2304
2305 return true;
2306 }
2307
2308 /**
2309 * Returns <tt>true</tt> if the two specified arrays of doubles are
2310 * <i>equal</i> to one another. Two arrays are considered equal if both
2311 * arrays contain the same number of elements, and all corresponding pairs
2312 * of elements in the two arrays are equal. In other words, two arrays
2313 * are equal if they contain the same elements in the same order. Also,
2314 * two array references are considered equal if both are <tt>null</tt>.<p>
2315 *
2316 * Two doubles <tt>d1</tt> and <tt>d2</tt> are considered equal if:
2317 * <pre> <tt>new Double(d1).equals(new Double(d2))</tt></pre>
2318 * (Unlike the <tt>==</tt> operator, this method considers
2319 * <tt>NaN</tt> equals to itself, and 0.0d unequal to -0.0d.)
2320 *
2321 * @param a one array to be tested for equality
2322 * @param a2 the other array to be tested for equality
2323 * @return <tt>true</tt> if the two arrays are equal
2324 * @see Double#equals(Object)
2325 */
2326 public static boolean equals(double[] a, double[] a2) {
2327 if (a == a2)
2328 return true;
2329 if (a == null || a2 == null)
2330 return false;
2331
2332 int length = a.length;
2333 if (a2.length != length)
2334 return false;
2335
2336 for (int i = 0; i < length; i++)
2337 if (Double.doubleToLongBits(a[i]) != Double
2338 .doubleToLongBits(a2[i]))
2339 return false;
2340
2341 return true;
2342 }
2343
2344 /**
2345 * Returns <tt>true</tt> if the two specified arrays of floats are
2346 * <i>equal</i> to one another. Two arrays are considered equal if both
2347 * arrays contain the same number of elements, and all corresponding pairs
2348 * of elements in the two arrays are equal. In other words, two arrays
2349 * are equal if they contain the same elements in the same order. Also,
2350 * two array references are considered equal if both are <tt>null</tt>.<p>
2351 *
2352 * Two floats <tt>f1</tt> and <tt>f2</tt> are considered equal if:
2353 * <pre> <tt>new Float(f1).equals(new Float(f2))</tt></pre>
2354 * (Unlike the <tt>==</tt> operator, this method considers
2355 * <tt>NaN</tt> equals to itself, and 0.0f unequal to -0.0f.)
2356 *
2357 * @param a one array to be tested for equality
2358 * @param a2 the other array to be tested for equality
2359 * @return <tt>true</tt> if the two arrays are equal
2360 * @see Float#equals(Object)
2361 */
2362 public static boolean equals(float[] a, float[] a2) {
2363 if (a == a2)
2364 return true;
2365 if (a == null || a2 == null)
2366 return false;
2367
2368 int length = a.length;
2369 if (a2.length != length)
2370 return false;
2371
2372 for (int i = 0; i < length; i++)
2373 if (Float.floatToIntBits(a[i]) != Float
2374 .floatToIntBits(a2[i]))
2375 return false;
2376
2377 return true;
2378 }
2379
2380 /**
2381 * Returns <tt>true</tt> if the two specified arrays of Objects are
2382 * <i>equal</i> to one another. The two arrays are considered equal if
2383 * both arrays contain the same number of elements, and all corresponding
2384 * pairs of elements in the two arrays are equal. Two objects <tt>e1</tt>
2385 * and <tt>e2</tt> are considered <i>equal</i> if <tt>(e1==null ? e2==null
2386 * : e1.equals(e2))</tt>. In other words, the two arrays are equal if
2387 * they contain the same elements in the same order. Also, two array
2388 * references are considered equal if both are <tt>null</tt>.<p>
2389 *
2390 * @param a one array to be tested for equality
2391 * @param a2 the other array to be tested for equality
2392 * @return <tt>true</tt> if the two arrays are equal
2393 */
2394 public static boolean equals(Object[] a, Object[] a2) {
2395 if (a == a2)
2396 return true;
2397 if (a == null || a2 == null)
2398 return false;
2399
2400 int length = a.length;
2401 if (a2.length != length)
2402 return false;
2403
2404 for (int i = 0; i < length; i++) {
2405 Object o1 = a[i];
2406 Object o2 = a2[i];
2407 if (!(o1 == null ? o2 == null : o1.equals(o2)))
2408 return false;
2409 }
2410
2411 return true;
2412 }
2413
2414 // Filling
2415
2416 /**
2417 * Assigns the specified long value to each element of the specified array
2418 * of longs.
2419 *
2420 * @param a the array to be filled
2421 * @param val the value to be stored in all elements of the array
2422 */
2423 public static void fill(long[] a, long val) {
2424 for (int i = 0, len = a.length; i < len; i++)
2425 a[i] = val;
2426 }
2427
2428 /**
2429 * Assigns the specified long value to each element of the specified
2430 * range of the specified array of longs. The range to be filled
2431 * extends from index <tt>fromIndex</tt>, inclusive, to index
2432 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2433 * range to be filled is empty.)
2434 *
2435 * @param a the array to be filled
2436 * @param fromIndex the index of the first element (inclusive) to be
2437 * filled with the specified value
2438 * @param toIndex the index of the last element (exclusive) to be
2439 * filled with the specified value
2440 * @param val the value to be stored in all elements of the array
2441 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2442 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2443 * <tt>toIndex > a.length</tt>
2444 */
2445 public static void fill(long[] a, int fromIndex, int toIndex,
2446 long val) {
2447 rangeCheck(a.length, fromIndex, toIndex);
2448 for (int i = fromIndex; i < toIndex; i++)
2449 a[i] = val;
2450 }
2451
2452 /**
2453 * Assigns the specified int value to each element of the specified array
2454 * of ints.
2455 *
2456 * @param a the array to be filled
2457 * @param val the value to be stored in all elements of the array
2458 */
2459 public static void fill(int[] a, int val) {
2460 for (int i = 0, len = a.length; i < len; i++)
2461 a[i] = val;
2462 }
2463
2464 /**
2465 * Assigns the specified int value to each element of the specified
2466 * range of the specified array of ints. The range to be filled
2467 * extends from index <tt>fromIndex</tt>, inclusive, to index
2468 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2469 * range to be filled is empty.)
2470 *
2471 * @param a the array to be filled
2472 * @param fromIndex the index of the first element (inclusive) to be
2473 * filled with the specified value
2474 * @param toIndex the index of the last element (exclusive) to be
2475 * filled with the specified value
2476 * @param val the value to be stored in all elements of the array
2477 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2478 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2479 * <tt>toIndex > a.length</tt>
2480 */
2481 public static void fill(int[] a, int fromIndex, int toIndex, int val) {
2482 rangeCheck(a.length, fromIndex, toIndex);
2483 for (int i = fromIndex; i < toIndex; i++)
2484 a[i] = val;
2485 }
2486
2487 /**
2488 * Assigns the specified short value to each element of the specified array
2489 * of shorts.
2490 *
2491 * @param a the array to be filled
2492 * @param val the value to be stored in all elements of the array
2493 */
2494 public static void fill(short[] a, short val) {
2495 for (int i = 0, len = a.length; i < len; i++)
2496 a[i] = val;
2497 }
2498
2499 /**
2500 * Assigns the specified short value to each element of the specified
2501 * range of the specified array of shorts. The range to be filled
2502 * extends from index <tt>fromIndex</tt>, inclusive, to index
2503 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2504 * range to be filled is empty.)
2505 *
2506 * @param a the array to be filled
2507 * @param fromIndex the index of the first element (inclusive) to be
2508 * filled with the specified value
2509 * @param toIndex the index of the last element (exclusive) to be
2510 * filled with the specified value
2511 * @param val the value to be stored in all elements of the array
2512 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2513 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2514 * <tt>toIndex > a.length</tt>
2515 */
2516 public static void fill(short[] a, int fromIndex, int toIndex,
2517 short val) {
2518 rangeCheck(a.length, fromIndex, toIndex);
2519 for (int i = fromIndex; i < toIndex; i++)
2520 a[i] = val;
2521 }
2522
2523 /**
2524 * Assigns the specified char value to each element of the specified array
2525 * of chars.
2526 *
2527 * @param a the array to be filled
2528 * @param val the value to be stored in all elements of the array
2529 */
2530 public static void fill(char[] a, char val) {
2531 for (int i = 0, len = a.length; i < len; i++)
2532 a[i] = val;
2533 }
2534
2535 /**
2536 * Assigns the specified char value to each element of the specified
2537 * range of the specified array of chars. The range to be filled
2538 * extends from index <tt>fromIndex</tt>, inclusive, to index
2539 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2540 * range to be filled is empty.)
2541 *
2542 * @param a the array to be filled
2543 * @param fromIndex the index of the first element (inclusive) to be
2544 * filled with the specified value
2545 * @param toIndex the index of the last element (exclusive) to be
2546 * filled with the specified value
2547 * @param val the value to be stored in all elements of the array
2548 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2549 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2550 * <tt>toIndex > a.length</tt>
2551 */
2552 public static void fill(char[] a, int fromIndex, int toIndex,
2553 char val) {
2554 rangeCheck(a.length, fromIndex, toIndex);
2555 for (int i = fromIndex; i < toIndex; i++)
2556 a[i] = val;
2557 }
2558
2559 /**
2560 * Assigns the specified byte value to each element of the specified array
2561 * of bytes.
2562 *
2563 * @param a the array to be filled
2564 * @param val the value to be stored in all elements of the array
2565 */
2566 public static void fill(byte[] a, byte val) {
2567 for (int i = 0, len = a.length; i < len; i++)
2568 a[i] = val;
2569 }
2570
2571 /**
2572 * Assigns the specified byte value to each element of the specified
2573 * range of the specified array of bytes. The range to be filled
2574 * extends from index <tt>fromIndex</tt>, inclusive, to index
2575 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2576 * range to be filled is empty.)
2577 *
2578 * @param a the array to be filled
2579 * @param fromIndex the index of the first element (inclusive) to be
2580 * filled with the specified value
2581 * @param toIndex the index of the last element (exclusive) to be
2582 * filled with the specified value
2583 * @param val the value to be stored in all elements of the array
2584 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2585 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2586 * <tt>toIndex > a.length</tt>
2587 */
2588 public static void fill(byte[] a, int fromIndex, int toIndex,
2589 byte val) {
2590 rangeCheck(a.length, fromIndex, toIndex);
2591 for (int i = fromIndex; i < toIndex; i++)
2592 a[i] = val;
2593 }
2594
2595 /**
2596 * Assigns the specified boolean value to each element of the specified
2597 * array of booleans.
2598 *
2599 * @param a the array to be filled
2600 * @param val the value to be stored in all elements of the array
2601 */
2602 public static void fill(boolean[] a, boolean val) {
2603 for (int i = 0, len = a.length; i < len; i++)
2604 a[i] = val;
2605 }
2606
2607 /**
2608 * Assigns the specified boolean value to each element of the specified
2609 * range of the specified array of booleans. The range to be filled
2610 * extends from index <tt>fromIndex</tt>, inclusive, to index
2611 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2612 * range to be filled is empty.)
2613 *
2614 * @param a the array to be filled
2615 * @param fromIndex the index of the first element (inclusive) to be
2616 * filled with the specified value
2617 * @param toIndex the index of the last element (exclusive) to be
2618 * filled with the specified value
2619 * @param val the value to be stored in all elements of the array
2620 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2621 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2622 * <tt>toIndex > a.length</tt>
2623 */
2624 public static void fill(boolean[] a, int fromIndex, int toIndex,
2625 boolean val) {
2626 rangeCheck(a.length, fromIndex, toIndex);
2627 for (int i = fromIndex; i < toIndex; i++)
2628 a[i] = val;
2629 }
2630
2631 /**
2632 * Assigns the specified double value to each element of the specified
2633 * array of doubles.
2634 *
2635 * @param a the array to be filled
2636 * @param val the value to be stored in all elements of the array
2637 */
2638 public static void fill(double[] a, double val) {
2639 for (int i = 0, len = a.length; i < len; i++)
2640 a[i] = val;
2641 }
2642
2643 /**
2644 * Assigns the specified double value to each element of the specified
2645 * range of the specified array of doubles. The range to be filled
2646 * extends from index <tt>fromIndex</tt>, inclusive, to index
2647 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2648 * range to be filled is empty.)
2649 *
2650 * @param a the array to be filled
2651 * @param fromIndex the index of the first element (inclusive) to be
2652 * filled with the specified value
2653 * @param toIndex the index of the last element (exclusive) to be
2654 * filled with the specified value
2655 * @param val the value to be stored in all elements of the array
2656 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2657 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2658 * <tt>toIndex > a.length</tt>
2659 */
2660 public static void fill(double[] a, int fromIndex, int toIndex,
2661 double val) {
2662 rangeCheck(a.length, fromIndex, toIndex);
2663 for (int i = fromIndex; i < toIndex; i++)
2664 a[i] = val;
2665 }
2666
2667 /**
2668 * Assigns the specified float value to each element of the specified array
2669 * of floats.
2670 *
2671 * @param a the array to be filled
2672 * @param val the value to be stored in all elements of the array
2673 */
2674 public static void fill(float[] a, float val) {
2675 for (int i = 0, len = a.length; i < len; i++)
2676 a[i] = val;
2677 }
2678
2679 /**
2680 * Assigns the specified float value to each element of the specified
2681 * range of the specified array of floats. The range to be filled
2682 * extends from index <tt>fromIndex</tt>, inclusive, to index
2683 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2684 * range to be filled is empty.)
2685 *
2686 * @param a the array to be filled
2687 * @param fromIndex the index of the first element (inclusive) to be
2688 * filled with the specified value
2689 * @param toIndex the index of the last element (exclusive) to be
2690 * filled with the specified value
2691 * @param val the value to be stored in all elements of the array
2692 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2693 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2694 * <tt>toIndex > a.length</tt>
2695 */
2696 public static void fill(float[] a, int fromIndex, int toIndex,
2697 float val) {
2698 rangeCheck(a.length, fromIndex, toIndex);
2699 for (int i = fromIndex; i < toIndex; i++)
2700 a[i] = val;
2701 }
2702
2703 /**
2704 * Assigns the specified Object reference to each element of the specified
2705 * array of Objects.
2706 *
2707 * @param a the array to be filled
2708 * @param val the value to be stored in all elements of the array
2709 * @throws ArrayStoreException if the specified value is not of a
2710 * runtime type that can be stored in the specified array
2711 */
2712 public static void fill(Object[] a, Object val) {
2713 for (int i = 0, len = a.length; i < len; i++)
2714 a[i] = val;
2715 }
2716
2717 /**
2718 * Assigns the specified Object reference to each element of the specified
2719 * range of the specified array of Objects. The range to be filled
2720 * extends from index <tt>fromIndex</tt>, inclusive, to index
2721 * <tt>toIndex</tt>, exclusive. (If <tt>fromIndex==toIndex</tt>, the
2722 * range to be filled is empty.)
2723 *
2724 * @param a the array to be filled
2725 * @param fromIndex the index of the first element (inclusive) to be
2726 * filled with the specified value
2727 * @param toIndex the index of the last element (exclusive) to be
2728 * filled with the specified value
2729 * @param val the value to be stored in all elements of the array
2730 * @throws IllegalArgumentException if <tt>fromIndex > toIndex</tt>
2731 * @throws ArrayIndexOutOfBoundsException if <tt>fromIndex < 0</tt> or
2732 * <tt>toIndex > a.length</tt>
2733 * @throws ArrayStoreException if the specified value is not of a
2734 * runtime type that can be stored in the specified array
2735 */
2736 public static void fill(Object[] a, int fromIndex, int toIndex,
2737 Object val) {
2738 rangeCheck(a.length, fromIndex, toIndex);
2739 for (int i = fromIndex; i < toIndex; i++)
2740 a[i] = val;
2741 }
2742
2743 // Cloning
2744 /**
2745 * Copies the specified array, truncating or padding with nulls (if necessary)
2746 * so the copy has the specified length. For all indices that are
2747 * valid in both the original array and the copy, the two arrays will
2748 * contain identical values. For any indices that are valid in the
2749 * copy but not the original, the copy will contain <tt>null</tt>.
2750 * Such indices will exist if and only if the specified length
2751 * is greater than that of the original array.
2752 * The resulting array is of exactly the same class as the original array.
2753 *
2754 * @param original the array to be copied
2755 * @param newLength the length of the copy to be returned
2756 * @return a copy of the original array, truncated or padded with nulls
2757 * to obtain the specified length
2758 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2759 * @throws NullPointerException if <tt>original</tt> is null
2760 * @since 1.6
2761 */
2762 public static <T> T[] copyOf(T[] original, int newLength) {
2763 return (T[]) copyOf(original, newLength, original.getClass());
2764 }
2765
2766 /**
2767 * Copies the specified array, truncating or padding with nulls (if necessary)
2768 * so the copy has the specified length. For all indices that are
2769 * valid in both the original array and the copy, the two arrays will
2770 * contain identical values. For any indices that are valid in the
2771 * copy but not the original, the copy will contain <tt>null</tt>.
2772 * Such indices will exist if and only if the specified length
2773 * is greater than that of the original array.
2774 * The resulting array is of the class <tt>newType</tt>.
2775 *
2776 * @param original the array to be copied
2777 * @param newLength the length of the copy to be returned
2778 * @param newType the class of the copy to be returned
2779 * @return a copy of the original array, truncated or padded with nulls
2780 * to obtain the specified length
2781 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2782 * @throws NullPointerException if <tt>original</tt> is null
2783 * @throws ArrayStoreException if an element copied from
2784 * <tt>original</tt> is not of a runtime type that can be stored in
2785 * an array of class <tt>newType</tt>
2786 * @since 1.6
2787 */
2788 public static <T, U> T[] copyOf(U[] original, int newLength,
2789 Class<? extends T[]> newType) {
2790 T[] copy = ((Object) newType == (Object) Object[].class) ? (T[]) new Object[newLength]
2791 : (T[]) Array.newInstance(newType.getComponentType(),
2792 newLength);
2793 System.arraycopy(original, 0, copy, 0, Math.min(
2794 original.length, newLength));
2795 return copy;
2796 }
2797
2798 /**
2799 * Copies the specified array, truncating or padding with zeros (if necessary)
2800 * so the copy has the specified length. For all indices that are
2801 * valid in both the original array and the copy, the two arrays will
2802 * contain identical values. For any indices that are valid in the
2803 * copy but not the original, the copy will contain <tt>(byte)0</tt>.
2804 * Such indices will exist if and only if the specified length
2805 * is greater than that of the original array.
2806 *
2807 * @param original the array to be copied
2808 * @param newLength the length of the copy to be returned
2809 * @return a copy of the original array, truncated or padded with zeros
2810 * to obtain the specified length
2811 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2812 * @throws NullPointerException if <tt>original</tt> is null
2813 * @since 1.6
2814 */
2815 public static byte[] copyOf(byte[] original, int newLength) {
2816 byte[] copy = new byte[newLength];
2817 System.arraycopy(original, 0, copy, 0, Math.min(
2818 original.length, newLength));
2819 return copy;
2820 }
2821
2822 /**
2823 * Copies the specified array, truncating or padding with zeros (if necessary)
2824 * so the copy has the specified length. For all indices that are
2825 * valid in both the original array and the copy, the two arrays will
2826 * contain identical values. For any indices that are valid in the
2827 * copy but not the original, the copy will contain <tt>(short)0</tt>.
2828 * Such indices will exist if and only if the specified length
2829 * is greater than that of the original array.
2830 *
2831 * @param original the array to be copied
2832 * @param newLength the length of the copy to be returned
2833 * @return a copy of the original array, truncated or padded with zeros
2834 * to obtain the specified length
2835 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2836 * @throws NullPointerException if <tt>original</tt> is null
2837 * @since 1.6
2838 */
2839 public static short[] copyOf(short[] original, int newLength) {
2840 short[] copy = new short[newLength];
2841 System.arraycopy(original, 0, copy, 0, Math.min(
2842 original.length, newLength));
2843 return copy;
2844 }
2845
2846 /**
2847 * Copies the specified array, truncating or padding with zeros (if necessary)
2848 * so the copy has the specified length. For all indices that are
2849 * valid in both the original array and the copy, the two arrays will
2850 * contain identical values. For any indices that are valid in the
2851 * copy but not the original, the copy will contain <tt>0</tt>.
2852 * Such indices will exist if and only if the specified length
2853 * is greater than that of the original array.
2854 *
2855 * @param original the array to be copied
2856 * @param newLength the length of the copy to be returned
2857 * @return a copy of the original array, truncated or padded with zeros
2858 * to obtain the specified length
2859 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2860 * @throws NullPointerException if <tt>original</tt> is null
2861 * @since 1.6
2862 */
2863 public static int[] copyOf(int[] original, int newLength) {
2864 int[] copy = new int[newLength];
2865 System.arraycopy(original, 0, copy, 0, Math.min(
2866 original.length, newLength));
2867 return copy;
2868 }
2869
2870 /**
2871 * Copies the specified array, truncating or padding with zeros (if necessary)
2872 * so the copy has the specified length. For all indices that are
2873 * valid in both the original array and the copy, the two arrays will
2874 * contain identical values. For any indices that are valid in the
2875 * copy but not the original, the copy will contain <tt>0L</tt>.
2876 * Such indices will exist if and only if the specified length
2877 * is greater than that of the original array.
2878 *
2879 * @param original the array to be copied
2880 * @param newLength the length of the copy to be returned
2881 * @return a copy of the original array, truncated or padded with zeros
2882 * to obtain the specified length
2883 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2884 * @throws NullPointerException if <tt>original</tt> is null
2885 * @since 1.6
2886 */
2887 public static long[] copyOf(long[] original, int newLength) {
2888 long[] copy = new long[newLength];
2889 System.arraycopy(original, 0, copy, 0, Math.min(
2890 original.length, newLength));
2891 return copy;
2892 }
2893
2894 /**
2895 * Copies the specified array, truncating or padding with null characters (if necessary)
2896 * so the copy has the specified length. For all indices that are valid
2897 * in both the original array and the copy, the two arrays will contain
2898 * identical values. For any indices that are valid in the copy but not
2899 * the original, the copy will contain <tt>'\\u000'</tt>. Such indices
2900 * will exist if and only if the specified length is greater than that of
2901 * the original array.
2902 *
2903 * @param original the array to be copied
2904 * @param newLength the length of the copy to be returned
2905 * @return a copy of the original array, truncated or padded with null characters
2906 * to obtain the specified length
2907 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2908 * @throws NullPointerException if <tt>original</tt> is null
2909 * @since 1.6
2910 */
2911 public static char[] copyOf(char[] original, int newLength) {
2912 char[] copy = new char[newLength];
2913 System.arraycopy(original, 0, copy, 0, Math.min(
2914 original.length, newLength));
2915 return copy;
2916 }
2917
2918 /**
2919 * Copies the specified array, truncating or padding with zeros (if necessary)
2920 * so the copy has the specified length. For all indices that are
2921 * valid in both the original array and the copy, the two arrays will
2922 * contain identical values. For any indices that are valid in the
2923 * copy but not the original, the copy will contain <tt>0f</tt>.
2924 * Such indices will exist if and only if the specified length
2925 * is greater than that of the original array.
2926 *
2927 * @param original the array to be copied
2928 * @param newLength the length of the copy to be returned
2929 * @return a copy of the original array, truncated or padded with zeros
2930 * to obtain the specified length
2931 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2932 * @throws NullPointerException if <tt>original</tt> is null
2933 * @since 1.6
2934 */
2935 public static float[] copyOf(float[] original, int newLength) {
2936 float[] copy = new float[newLength];
2937 System.arraycopy(original, 0, copy, 0, Math.min(
2938 original.length, newLength));
2939 return copy;
2940 }
2941
2942 /**
2943 * Copies the specified array, truncating or padding with zeros (if necessary)
2944 * so the copy has the specified length. For all indices that are
2945 * valid in both the original array and the copy, the two arrays will
2946 * contain identical values. For any indices that are valid in the
2947 * copy but not the original, the copy will contain <tt>0d</tt>.
2948 * Such indices will exist if and only if the specified length
2949 * is greater than that of the original array.
2950 *
2951 * @param original the array to be copied
2952 * @param newLength the length of the copy to be returned
2953 * @return a copy of the original array, truncated or padded with zeros
2954 * to obtain the specified length
2955 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2956 * @throws NullPointerException if <tt>original</tt> is null
2957 * @since 1.6
2958 */
2959 public static double[] copyOf(double[] original, int newLength) {
2960 double[] copy = new double[newLength];
2961 System.arraycopy(original, 0, copy, 0, Math.min(
2962 original.length, newLength));
2963 return copy;
2964 }
2965
2966 /**
2967 * Copies the specified array, truncating or padding with <tt>false</tt> (if necessary)
2968 * so the copy has the specified length. For all indices that are
2969 * valid in both the original array and the copy, the two arrays will
2970 * contain identical values. For any indices that are valid in the
2971 * copy but not the original, the copy will contain <tt>false</tt>.
2972 * Such indices will exist if and only if the specified length
2973 * is greater than that of the original array.
2974 *
2975 * @param original the array to be copied
2976 * @param newLength the length of the copy to be returned
2977 * @return a copy of the original array, truncated or padded with false elements
2978 * to obtain the specified length
2979 * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
2980 * @throws NullPointerException if <tt>original</tt> is null
2981 * @since 1.6
2982 */
2983 public static boolean[] copyOf(boolean[] original, int newLength) {
2984 boolean[] copy = new boolean[newLength];
2985 System.arraycopy(original, 0, copy, 0, Math.min(
2986 original.length, newLength));
2987 return copy;
2988 }
2989
2990 /**
2991 * Copies the specified range of the specified array into a new array.
2992 * The initial index of the range (<tt>from</tt>) must lie between zero
2993 * and <tt>original.length</tt>, inclusive. The value at
2994 * <tt>original[from]</tt> is placed into the initial element of the copy
2995 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
2996 * Values from subsequent elements in the original array are placed into
2997 * subsequent elements in the copy. The final index of the range
2998 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
2999 * may be greater than <tt>original.length</tt>, in which case
3000 * <tt>null</tt> is placed in all elements of the copy whose index is
3001 * greater than or equal to <tt>original.length - from</tt>. The length
3002 * of the returned array will be <tt>to - from</tt>.
3003 * <p>
3004 * The resulting array is of exactly the same class as the original array.
3005 *
3006 * @param original the array from which a range is to be copied
3007 * @param from the initial index of the range to be copied, inclusive
3008 * @param to the final index of the range to be copied, exclusive.
3009 * (This index may lie outside the array.)
3010 * @return a new array containing the specified range from the original array,
3011 * truncated or padded with nulls to obtain the required length
3012 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3013 * or {@code from > original.length}
3014 * @throws IllegalArgumentException if <tt>from > to</tt>
3015 * @throws NullPointerException if <tt>original</tt> is null
3016 * @since 1.6
3017 */
3018 public static <T> T[] copyOfRange(T[] original, int from, int to) {
3019 return copyOfRange(original, from, to, (Class<T[]>) original
3020 .getClass());
3021 }
3022
3023 /**
3024 * Copies the specified range of the specified array into a new array.
3025 * The initial index of the range (<tt>from</tt>) must lie between zero
3026 * and <tt>original.length</tt>, inclusive. The value at
3027 * <tt>original[from]</tt> is placed into the initial element of the copy
3028 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3029 * Values from subsequent elements in the original array are placed into
3030 * subsequent elements in the copy. The final index of the range
3031 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3032 * may be greater than <tt>original.length</tt>, in which case
3033 * <tt>null</tt> is placed in all elements of the copy whose index is
3034 * greater than or equal to <tt>original.length - from</tt>. The length
3035 * of the returned array will be <tt>to - from</tt>.
3036 * The resulting array is of the class <tt>newType</tt>.
3037 *
3038 * @param original the array from which a range is to be copied
3039 * @param from the initial index of the range to be copied, inclusive
3040 * @param to the final index of the range to be copied, exclusive.
3041 * (This index may lie outside the array.)
3042 * @param newType the class of the copy to be returned
3043 * @return a new array containing the specified range from the original array,
3044 * truncated or padded with nulls to obtain the required length
3045 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3046 * or {@code from > original.length}
3047 * @throws IllegalArgumentException if <tt>from > to</tt>
3048 * @throws NullPointerException if <tt>original</tt> is null
3049 * @throws ArrayStoreException if an element copied from
3050 * <tt>original</tt> is not of a runtime type that can be stored in
3051 * an array of class <tt>newType</tt>.
3052 * @since 1.6
3053 */
3054 public static <T, U> T[] copyOfRange(U[] original, int from,
3055 int to, Class<? extends T[]> newType) {
3056 int newLength = to - from;
3057 if (newLength < 0)
3058 throw new IllegalArgumentException(from + " > " + to);
3059 T[] copy = ((Object) newType == (Object) Object[].class) ? (T[]) new Object[newLength]
3060 : (T[]) Array.newInstance(newType.getComponentType(),
3061 newLength);
3062 System.arraycopy(original, from, copy, 0, Math.min(
3063 original.length - from, newLength));
3064 return copy;
3065 }
3066
3067 /**
3068 * Copies the specified range of the specified array into a new array.
3069 * The initial index of the range (<tt>from</tt>) must lie between zero
3070 * and <tt>original.length</tt>, inclusive. The value at
3071 * <tt>original[from]</tt> is placed into the initial element of the copy
3072 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3073 * Values from subsequent elements in the original array are placed into
3074 * subsequent elements in the copy. The final index of the range
3075 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3076 * may be greater than <tt>original.length</tt>, in which case
3077 * <tt>(byte)0</tt> is placed in all elements of the copy whose index is
3078 * greater than or equal to <tt>original.length - from</tt>. The length
3079 * of the returned array will be <tt>to - from</tt>.
3080 *
3081 * @param original the array from which a range is to be copied
3082 * @param from the initial index of the range to be copied, inclusive
3083 * @param to the final index of the range to be copied, exclusive.
3084 * (This index may lie outside the array.)
3085 * @return a new array containing the specified range from the original array,
3086 * truncated or padded with zeros to obtain the required length
3087 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3088 * or {@code from > original.length}
3089 * @throws IllegalArgumentException if <tt>from > to</tt>
3090 * @throws NullPointerException if <tt>original</tt> is null
3091 * @since 1.6
3092 */
3093 public static byte[] copyOfRange(byte[] original, int from, int to) {
3094 int newLength = to - from;
3095 if (newLength < 0)
3096 throw new IllegalArgumentException(from + " > " + to);
3097 byte[] copy = new byte[newLength];
3098 System.arraycopy(original, from, copy, 0, Math.min(
3099 original.length - from, newLength));
3100 return copy;
3101 }
3102
3103 /**
3104 * Copies the specified range of the specified array into a new array.
3105 * The initial index of the range (<tt>from</tt>) must lie between zero
3106 * and <tt>original.length</tt>, inclusive. The value at
3107 * <tt>original[from]</tt> is placed into the initial element of the copy
3108 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3109 * Values from subsequent elements in the original array are placed into
3110 * subsequent elements in the copy. The final index of the range
3111 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3112 * may be greater than <tt>original.length</tt>, in which case
3113 * <tt>(short)0</tt> is placed in all elements of the copy whose index is
3114 * greater than or equal to <tt>original.length - from</tt>. The length
3115 * of the returned array will be <tt>to - from</tt>.
3116 *
3117 * @param original the array from which a range is to be copied
3118 * @param from the initial index of the range to be copied, inclusive
3119 * @param to the final index of the range to be copied, exclusive.
3120 * (This index may lie outside the array.)
3121 * @return a new array containing the specified range from the original array,
3122 * truncated or padded with zeros to obtain the required length
3123 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3124 * or {@code from > original.length}
3125 * @throws IllegalArgumentException if <tt>from > to</tt>
3126 * @throws NullPointerException if <tt>original</tt> is null
3127 * @since 1.6
3128 */
3129 public static short[] copyOfRange(short[] original, int from, int to) {
3130 int newLength = to - from;
3131 if (newLength < 0)
3132 throw new IllegalArgumentException(from + " > " + to);
3133 short[] copy = new short[newLength];
3134 System.arraycopy(original, from, copy, 0, Math.min(
3135 original.length - from, newLength));
3136 return copy;
3137 }
3138
3139 /**
3140 * Copies the specified range of the specified array into a new array.
3141 * The initial index of the range (<tt>from</tt>) must lie between zero
3142 * and <tt>original.length</tt>, inclusive. The value at
3143 * <tt>original[from]</tt> is placed into the initial element of the copy
3144 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3145 * Values from subsequent elements in the original array are placed into
3146 * subsequent elements in the copy. The final index of the range
3147 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3148 * may be greater than <tt>original.length</tt>, in which case
3149 * <tt>0</tt> is placed in all elements of the copy whose index is
3150 * greater than or equal to <tt>original.length - from</tt>. The length
3151 * of the returned array will be <tt>to - from</tt>.
3152 *
3153 * @param original the array from which a range is to be copied
3154 * @param from the initial index of the range to be copied, inclusive
3155 * @param to the final index of the range to be copied, exclusive.
3156 * (This index may lie outside the array.)
3157 * @return a new array containing the specified range from the original array,
3158 * truncated or padded with zeros to obtain the required length
3159 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3160 * or {@code from > original.length}
3161 * @throws IllegalArgumentException if <tt>from > to</tt>
3162 * @throws NullPointerException if <tt>original</tt> is null
3163 * @since 1.6
3164 */
3165 public static int[] copyOfRange(int[] original, int from, int to) {
3166 int newLength = to - from;
3167 if (newLength < 0)
3168 throw new IllegalArgumentException(from + " > " + to);
3169 int[] copy = new int[newLength];
3170 System.arraycopy(original, from, copy, 0, Math.min(
3171 original.length - from, newLength));
3172 return copy;
3173 }
3174
3175 /**
3176 * Copies the specified range of the specified array into a new array.
3177 * The initial index of the range (<tt>from</tt>) must lie between zero
3178 * and <tt>original.length</tt>, inclusive. The value at
3179 * <tt>original[from]</tt> is placed into the initial element of the copy
3180 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3181 * Values from subsequent elements in the original array are placed into
3182 * subsequent elements in the copy. The final index of the range
3183 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3184 * may be greater than <tt>original.length</tt>, in which case
3185 * <tt>0L</tt> is placed in all elements of the copy whose index is
3186 * greater than or equal to <tt>original.length - from</tt>. The length
3187 * of the returned array will be <tt>to - from</tt>.
3188 *
3189 * @param original the array from which a range is to be copied
3190 * @param from the initial index of the range to be copied, inclusive
3191 * @param to the final index of the range to be copied, exclusive.
3192 * (This index may lie outside the array.)
3193 * @return a new array containing the specified range from the original array,
3194 * truncated or padded with zeros to obtain the required length
3195 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3196 * or {@code from > original.length}
3197 * @throws IllegalArgumentException if <tt>from > to</tt>
3198 * @throws NullPointerException if <tt>original</tt> is null
3199 * @since 1.6
3200 */
3201 public static long[] copyOfRange(long[] original, int from, int to) {
3202 int newLength = to - from;
3203 if (newLength < 0)
3204 throw new IllegalArgumentException(from + " > " + to);
3205 long[] copy = new long[newLength];
3206 System.arraycopy(original, from, copy, 0, Math.min(
3207 original.length - from, newLength));
3208 return copy;
3209 }
3210
3211 /**
3212 * Copies the specified range of the specified array into a new array.
3213 * The initial index of the range (<tt>from</tt>) must lie between zero
3214 * and <tt>original.length</tt>, inclusive. The value at
3215 * <tt>original[from]</tt> is placed into the initial element of the copy
3216 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3217 * Values from subsequent elements in the original array are placed into
3218 * subsequent elements in the copy. The final index of the range
3219 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3220 * may be greater than <tt>original.length</tt>, in which case
3221 * <tt>'\\u000'</tt> is placed in all elements of the copy whose index is
3222 * greater than or equal to <tt>original.length - from</tt>. The length
3223 * of the returned array will be <tt>to - from</tt>.
3224 *
3225 * @param original the array from which a range is to be copied
3226 * @param from the initial index of the range to be copied, inclusive
3227 * @param to the final index of the range to be copied, exclusive.
3228 * (This index may lie outside the array.)
3229 * @return a new array containing the specified range from the original array,
3230 * truncated or padded with null characters to obtain the required length
3231 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3232 * or {@code from > original.length}
3233 * @throws IllegalArgumentException if <tt>from > to</tt>
3234 * @throws NullPointerException if <tt>original</tt> is null
3235 * @since 1.6
3236 */
3237 public static char[] copyOfRange(char[] original, int from, int to) {
3238 int newLength = to - from;
3239 if (newLength < 0)
3240 throw new IllegalArgumentException(from + " > " + to);
3241 char[] copy = new char[newLength];
3242 System.arraycopy(original, from, copy, 0, Math.min(
3243 original.length - from, newLength));
3244 return copy;
3245 }
3246
3247 /**
3248 * Copies the specified range of the specified array into a new array.
3249 * The initial index of the range (<tt>from</tt>) must lie between zero
3250 * and <tt>original.length</tt>, inclusive. The value at
3251 * <tt>original[from]</tt> is placed into the initial element of the copy
3252 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3253 * Values from subsequent elements in the original array are placed into
3254 * subsequent elements in the copy. The final index of the range
3255 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3256 * may be greater than <tt>original.length</tt>, in which case
3257 * <tt>0f</tt> is placed in all elements of the copy whose index is
3258 * greater than or equal to <tt>original.length - from</tt>. The length
3259 * of the returned array will be <tt>to - from</tt>.
3260 *
3261 * @param original the array from which a range is to be copied
3262 * @param from the initial index of the range to be copied, inclusive
3263 * @param to the final index of the range to be copied, exclusive.
3264 * (This index may lie outside the array.)
3265 * @return a new array containing the specified range from the original array,
3266 * truncated or padded with zeros to obtain the required length
3267 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3268 * or {@code from > original.length}
3269 * @throws IllegalArgumentException if <tt>from > to</tt>
3270 * @throws NullPointerException if <tt>original</tt> is null
3271 * @since 1.6
3272 */
3273 public static float[] copyOfRange(float[] original, int from, int to) {
3274 int newLength = to - from;
3275 if (newLength < 0)
3276 throw new IllegalArgumentException(from + " > " + to);
3277 float[] copy = new float[newLength];
3278 System.arraycopy(original, from, copy, 0, Math.min(
3279 original.length - from, newLength));
3280 return copy;
3281 }
3282
3283 /**
3284 * Copies the specified range of the specified array into a new array.
3285 * The initial index of the range (<tt>from</tt>) must lie between zero
3286 * and <tt>original.length</tt>, inclusive. The value at
3287 * <tt>original[from]</tt> is placed into the initial element of the copy
3288 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3289 * Values from subsequent elements in the original array are placed into
3290 * subsequent elements in the copy. The final index of the range
3291 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3292 * may be greater than <tt>original.length</tt>, in which case
3293 * <tt>0d</tt> is placed in all elements of the copy whose index is
3294 * greater than or equal to <tt>original.length - from</tt>. The length
3295 * of the returned array will be <tt>to - from</tt>.
3296 *
3297 * @param original the array from which a range is to be copied
3298 * @param from the initial index of the range to be copied, inclusive
3299 * @param to the final index of the range to be copied, exclusive.
3300 * (This index may lie outside the array.)
3301 * @return a new array containing the specified range from the original array,
3302 * truncated or padded with zeros to obtain the required length
3303 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3304 * or {@code from > original.length}
3305 * @throws IllegalArgumentException if <tt>from > to</tt>
3306 * @throws NullPointerException if <tt>original</tt> is null
3307 * @since 1.6
3308 */
3309 public static double[] copyOfRange(double[] original, int from,
3310 int to) {
3311 int newLength = to - from;
3312 if (newLength < 0)
3313 throw new IllegalArgumentException(from + " > " + to);
3314 double[] copy = new double[newLength];
3315 System.arraycopy(original, from, copy, 0, Math.min(
3316 original.length - from, newLength));
3317 return copy;
3318 }
3319
3320 /**
3321 * Copies the specified range of the specified array into a new array.
3322 * The initial index of the range (<tt>from</tt>) must lie between zero
3323 * and <tt>original.length</tt>, inclusive. The value at
3324 * <tt>original[from]</tt> is placed into the initial element of the copy
3325 * (unless <tt>from == original.length</tt> or <tt>from == to</tt>).
3326 * Values from subsequent elements in the original array are placed into
3327 * subsequent elements in the copy. The final index of the range
3328 * (<tt>to</tt>), which must be greater than or equal to <tt>from</tt>,
3329 * may be greater than <tt>original.length</tt>, in which case
3330 * <tt>false</tt> is placed in all elements of the copy whose index is
3331 * greater than or equal to <tt>original.length - from</tt>. The length
3332 * of the returned array will be <tt>to - from</tt>.
3333 *
3334 * @param original the array from which a range is to be copied
3335 * @param from the initial index of the range to be copied, inclusive
3336 * @param to the final index of the range to be copied, exclusive.
3337 * (This index may lie outside the array.)
3338 * @return a new array containing the specified range from the original array,
3339 * truncated or padded with false elements to obtain the required length
3340 * @throws ArrayIndexOutOfBoundsException if {@code from < 0}
3341 * or {@code from > original.length}
3342 * @throws IllegalArgumentException if <tt>from > to</tt>
3343 * @throws NullPointerException if <tt>original</tt> is null
3344 * @since 1.6
3345 */
3346 public static boolean[] copyOfRange(boolean[] original, int from,
3347 int to) {
3348 int newLength = to - from;
3349 if (newLength < 0)
3350 throw new IllegalArgumentException(from + " > " + to);
3351 boolean[] copy = new boolean[newLength];
3352 System.arraycopy(original, from, copy, 0, Math.min(
3353 original.length - from, newLength));
3354 return copy;
3355 }
3356
3357 // Misc
3358
3359 /**
3360 * Returns a fixed-size list backed by the specified array. (Changes to
3361 * the returned list "write through" to the array.) This method acts
3362 * as bridge between array-based and collection-based APIs, in
3363 * combination with {@link Collection#toArray}. The returned list is
3364 * serializable and implements {@link RandomAccess}.
3365 *
3366 * <p>This method also provides a convenient way to create a fixed-size
3367 * list initialized to contain several elements:
3368 * <pre>
3369 * List<String> stooges = Arrays.asList("Larry", "Moe", "Curly");
3370 * </pre>
3371 *
3372 * @param a the array by which the list will be backed
3373 * @return a list view of the specified array
3374 */
3375 public static <T> List<T> asList(T... a) {
3376 return new ArrayList<T>(a);
3377 }
3378
3379 /**
3380 * @serial include
3381 */
3382 private static class ArrayList<E> extends AbstractList<E> implements
3383 RandomAccess, java.io.Serializable {
3384 private static final long serialVersionUID = -2764017481108945198L;
3385 private final E[] a;
3386
3387 ArrayList(E[] array) {
3388 if (array == null)
3389 throw new NullPointerException();
3390 a = array;
3391 }
3392
3393 public int size() {
3394 return a.length;
3395 }
3396
3397 public Object[] toArray() {
3398 return a.clone();
3399 }
3400
3401 public <T> T[] toArray(T[] a) {
3402 int size = size();
3403 if (a.length < size)
3404 return Arrays.copyOf(this .a, size,
3405 (Class<? extends T[]>) a.getClass());
3406 System.arraycopy(this .a, 0, a, 0, size);
3407 if (a.length > size)
3408 a[size] = null;
3409 return a;
3410 }
3411
3412 public E get(int index) {
3413 return a[index];
3414 }
3415
3416 public E set(int index, E element) {
3417 E oldValue = a[index];
3418 a[index] = element;
3419 return oldValue;
3420 }
3421
3422 public int indexOf(Object o) {
3423 if (o == null) {
3424 for (int i = 0; i < a.length; i++)
3425 if (a[i] == null)
3426 return i;
3427 } else {
3428 for (int i = 0; i < a.length; i++)
3429 if (o.equals(a[i]))
3430 return i;
3431 }
3432 return -1;
3433 }
3434
3435 public boolean contains(Object o) {
3436 return indexOf(o) != -1;
3437 }
3438 }
3439
3440 /**
3441 * Returns a hash code based on the contents of the specified array.
3442 * For any two <tt>long</tt> arrays <tt>a</tt> and <tt>b</tt>
3443 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3444 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3445 *
3446 * <p>The value returned by this method is the same value that would be
3447 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3448 * method on a {@link List} containing a sequence of {@link Long}
3449 * instances representing the elements of <tt>a</tt> in the same order.
3450 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3451 *
3452 * @param a the array whose hash value to compute
3453 * @return a content-based hash code for <tt>a</tt>
3454 * @since 1.5
3455 */
3456 public static int hashCode(long a[]) {
3457 if (a == null)
3458 return 0;
3459
3460 int result = 1;
3461 for (long element : a) {
3462 int elementHash = (int) (element ^ (element >>> 32));
3463 result = 31 * result + elementHash;
3464 }
3465
3466 return result;
3467 }
3468
3469 /**
3470 * Returns a hash code based on the contents of the specified array.
3471 * For any two non-null <tt>int</tt> arrays <tt>a</tt> and <tt>b</tt>
3472 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3473 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3474 *
3475 * <p>The value returned by this method is the same value that would be
3476 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3477 * method on a {@link List} containing a sequence of {@link Integer}
3478 * instances representing the elements of <tt>a</tt> in the same order.
3479 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3480 *
3481 * @param a the array whose hash value to compute
3482 * @return a content-based hash code for <tt>a</tt>
3483 * @since 1.5
3484 */
3485 public static int hashCode(int a[]) {
3486 if (a == null)
3487 return 0;
3488
3489 int result = 1;
3490 for (int element : a)
3491 result = 31 * result + element;
3492
3493 return result;
3494 }
3495
3496 /**
3497 * Returns a hash code based on the contents of the specified array.
3498 * For any two <tt>short</tt> arrays <tt>a</tt> and <tt>b</tt>
3499 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3500 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3501 *
3502 * <p>The value returned by this method is the same value that would be
3503 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3504 * method on a {@link List} containing a sequence of {@link Short}
3505 * instances representing the elements of <tt>a</tt> in the same order.
3506 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3507 *
3508 * @param a the array whose hash value to compute
3509 * @return a content-based hash code for <tt>a</tt>
3510 * @since 1.5
3511 */
3512 public static int hashCode(short a[]) {
3513 if (a == null)
3514 return 0;
3515
3516 int result = 1;
3517 for (short element : a)
3518 result = 31 * result + element;
3519
3520 return result;
3521 }
3522
3523 /**
3524 * Returns a hash code based on the contents of the specified array.
3525 * For any two <tt>char</tt> arrays <tt>a</tt> and <tt>b</tt>
3526 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3527 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3528 *
3529 * <p>The value returned by this method is the same value that would be
3530 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3531 * method on a {@link List} containing a sequence of {@link Character}
3532 * instances representing the elements of <tt>a</tt> in the same order.
3533 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3534 *
3535 * @param a the array whose hash value to compute
3536 * @return a content-based hash code for <tt>a</tt>
3537 * @since 1.5
3538 */
3539 public static int hashCode(char a[]) {
3540 if (a == null)
3541 return 0;
3542
3543 int result = 1;
3544 for (char element : a)
3545 result = 31 * result + element;
3546
3547 return result;
3548 }
3549
3550 /**
3551 * Returns a hash code based on the contents of the specified array.
3552 * For any two <tt>byte</tt> arrays <tt>a</tt> and <tt>b</tt>
3553 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3554 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3555 *
3556 * <p>The value returned by this method is the same value that would be
3557 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3558 * method on a {@link List} containing a sequence of {@link Byte}
3559 * instances representing the elements of <tt>a</tt> in the same order.
3560 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3561 *
3562 * @param a the array whose hash value to compute
3563 * @return a content-based hash code for <tt>a</tt>
3564 * @since 1.5
3565 */
3566 public static int hashCode(byte a[]) {
3567 if (a == null)
3568 return 0;
3569
3570 int result = 1;
3571 for (byte element : a)
3572 result = 31 * result + element;
3573
3574 return result;
3575 }
3576
3577 /**
3578 * Returns a hash code based on the contents of the specified array.
3579 * For any two <tt>boolean</tt> arrays <tt>a</tt> and <tt>b</tt>
3580 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3581 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3582 *
3583 * <p>The value returned by this method is the same value that would be
3584 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3585 * method on a {@link List} containing a sequence of {@link Boolean}
3586 * instances representing the elements of <tt>a</tt> in the same order.
3587 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3588 *
3589 * @param a the array whose hash value to compute
3590 * @return a content-based hash code for <tt>a</tt>
3591 * @since 1.5
3592 */
3593 public static int hashCode(boolean a[]) {
3594 if (a == null)
3595 return 0;
3596
3597 int result = 1;
3598 for (boolean element : a)
3599 result = 31 * result + (element ? 1231 : 1237);
3600
3601 return result;
3602 }
3603
3604 /**
3605 * Returns a hash code based on the contents of the specified array.
3606 * For any two <tt>float</tt> arrays <tt>a</tt> and <tt>b</tt>
3607 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3608 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3609 *
3610 * <p>The value returned by this method is the same value that would be
3611 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3612 * method on a {@link List} containing a sequence of {@link Float}
3613 * instances representing the elements of <tt>a</tt> in the same order.
3614 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3615 *
3616 * @param a the array whose hash value to compute
3617 * @return a content-based hash code for <tt>a</tt>
3618 * @since 1.5
3619 */
3620 public static int hashCode(float a[]) {
3621 if (a == null)
3622 return 0;
3623
3624 int result = 1;
3625 for (float element : a)
3626 result = 31 * result + Float.floatToIntBits(element);
3627
3628 return result;
3629 }
3630
3631 /**
3632 * Returns a hash code based on the contents of the specified array.
3633 * For any two <tt>double</tt> arrays <tt>a</tt> and <tt>b</tt>
3634 * such that <tt>Arrays.equals(a, b)</tt>, it is also the case that
3635 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3636 *
3637 * <p>The value returned by this method is the same value that would be
3638 * obtained by invoking the {@link List#hashCode() <tt>hashCode</tt>}
3639 * method on a {@link List} containing a sequence of {@link Double}
3640 * instances representing the elements of <tt>a</tt> in the same order.
3641 * If <tt>a</tt> is <tt>null</tt>, this method returns 0.
3642 *
3643 * @param a the array whose hash value to compute
3644 * @return a content-based hash code for <tt>a</tt>
3645 * @since 1.5
3646 */
3647 public static int hashCode(double a[]) {
3648 if (a == null)
3649 return 0;
3650
3651 int result = 1;
3652 for (double element : a) {
3653 long bits = Double.doubleToLongBits(element);
3654 result = 31 * result + (int) (bits ^ (bits >>> 32));
3655 }
3656 return result;
3657 }
3658
3659 /**
3660 * Returns a hash code based on the contents of the specified array. If
3661 * the array contains other arrays as elements, the hash code is based on
3662 * their identities rather than their contents. It is therefore
3663 * acceptable to invoke this method on an array that contains itself as an
3664 * element, either directly or indirectly through one or more levels of
3665 * arrays.
3666 *
3667 * <p>For any two arrays <tt>a</tt> and <tt>b</tt> such that
3668 * <tt>Arrays.equals(a, b)</tt>, it is also the case that
3669 * <tt>Arrays.hashCode(a) == Arrays.hashCode(b)</tt>.
3670 *
3671 * <p>The value returned by this method is equal to the value that would
3672 * be returned by <tt>Arrays.asList(a).hashCode()</tt>, unless <tt>a</tt>
3673 * is <tt>null</tt>, in which case <tt>0</tt> is returned.
3674 *
3675 * @param a the array whose content-based hash code to compute
3676 * @return a content-based hash code for <tt>a</tt>
3677 * @see #deepHashCode(Object[])
3678 * @since 1.5
3679 */
3680 public static int hashCode(Object a[]) {
3681 if (a == null)
3682 return 0;
3683
3684 int result = 1;
3685
3686 for (Object element : a)
3687 result = 31 * result
3688 + (element == null ? 0 : element.hashCode());
3689
3690 return result;
3691 }
3692
3693 /**
3694 * Returns a hash code based on the "deep contents" of the specified
3695 * array. If the array contains other arrays as elements, the
3696 * hash code is based on their contents and so on, ad infinitum.
3697 * It is therefore unacceptable to invoke this method on an array that
3698 * contains itself as an element, either directly or indirectly through
3699 * one or more levels of arrays. The behavior of such an invocation is
3700 * undefined.
3701 *
3702 * <p>For any two arrays <tt>a</tt> and <tt>b</tt> such that
3703 * <tt>Arrays.deepEquals(a, b)</tt>, it is also the case that
3704 * <tt>Arrays.deepHashCode(a) == Arrays.deepHashCode(b)</tt>.
3705 *
3706 * <p>The computation of the value returned by this method is similar to
3707 * that of the value returned by {@link List#hashCode()} on a list
3708 * containing the same elements as <tt>a</tt> in the same order, with one
3709 * difference: If an element <tt>e</tt> of <tt>a</tt> is itself an array,
3710 * its hash code is computed not by calling <tt>e.hashCode()</tt>, but as
3711 * by calling the appropriate overloading of <tt>Arrays.hashCode(e)</tt>
3712 * if <tt>e</tt> is an array of a primitive type, or as by calling
3713 * <tt>Arrays.deepHashCode(e)</tt> recursively if <tt>e</tt> is an array
3714 * of a reference type. If <tt>a</tt> is <tt>null</tt>, this method
3715 * returns 0.
3716 *
3717 * @param a the array whose deep-content-based hash code to compute
3718 * @return a deep-content-based hash code for <tt>a</tt>
3719 * @see #hashCode(Object[])
3720 * @since 1.5
3721 */
3722 public static int deepHashCode(Object a[]) {
3723 if (a == null)
3724 return 0;
3725
3726 int result = 1;
3727
3728 for (Object element : a) {
3729 int elementHash = 0;
3730 if (element instanceof Object[])
3731 elementHash = deepHashCode((Object[]) element);
3732 else if (element instanceof byte[])
3733 elementHash = hashCode((byte[]) element);
3734 else if (element instanceof short[])
3735 elementHash = hashCode((short[]) element);
3736 else if (element instanceof int[])
3737 elementHash = hashCode((int[]) element);
3738 else if (element instanceof long[])
3739 elementHash = hashCode((long[]) element);
3740 else if (element instanceof char[])
3741 elementHash = hashCode((char[]) element);
3742 else if (element instanceof float[])
3743 elementHash = hashCode((float[]) element);
3744 else if (element instanceof double[])
3745 elementHash = hashCode((double[]) element);
3746 else if (element instanceof boolean[])
3747 elementHash = hashCode((boolean[]) element);
3748 else if (element != null)
3749 elementHash = element.hashCode();
3750
3751 result = 31 * result + elementHash;
3752 }
3753
3754 return result;
3755 }
3756
3757 /**
3758 * Returns <tt>true</tt> if the two specified arrays are <i>deeply
3759 * equal</i> to one another. Unlike the {@link #equals(Object[],Object[])}
3760 * method, this method is appropriate for use with nested arrays of
3761 * arbitrary depth.
3762 *
3763 * <p>Two array references are considered deeply equal if both
3764 * are <tt>null</tt>, or if they refer to arrays that contain the same
3765 * number of elements and all corresponding pairs of elements in the two
3766 * arrays are deeply equal.
3767 *
3768 * <p>Two possibly <tt>null</tt> elements <tt>e1</tt> and <tt>e2</tt> are
3769 * deeply equal if any of the following conditions hold:
3770 * <ul>
3771 * <li> <tt>e1</tt> and <tt>e2</tt> are both arrays of object reference
3772 * types, and <tt>Arrays.deepEquals(e1, e2) would return true</tt>
3773 * <li> <tt>e1</tt> and <tt>e2</tt> are arrays of the same primitive
3774 * type, and the appropriate overloading of
3775 * <tt>Arrays.equals(e1, e2)</tt> would return true.
3776 * <li> <tt>e1 == e2</tt>
3777 * <li> <tt>e1.equals(e2)</tt> would return true.
3778 * </ul>
3779 * Note that this definition permits <tt>null</tt> elements at any depth.
3780 *
3781 * <p>If either of the specified arrays contain themselves as elements
3782 * either directly or indirectly through one or more levels of arrays,
3783 * the behavior of this method is undefined.
3784 *
3785 * @param a1 one array to be tested for equality
3786 * @param a2 the other array to be tested for equality
3787 * @return <tt>true</tt> if the two arrays are equal
3788 * @see #equals(Object[],Object[])
3789 * @since 1.5
3790 */
3791 public static boolean deepEquals(Object[] a1, Object[] a2) {
3792 if (a1 == a2)
3793 return true;
3794 if (a1 == null || a2 == null)
3795 return false;
3796 int length = a1.length;
3797 if (a2.length != length)
3798 return false;
3799
3800 for (int i = 0; i < length; i++) {
3801 Object e1 = a1[i];
3802 Object e2 = a2[i];
3803
3804 if (e1 == e2)
3805 continue;
3806 if (e1 == null)
3807 return false;
3808
3809 // Figure out whether the two elements are equal
3810 boolean eq;
3811 if (e1 instanceof Object[] && e2 instanceof Object[])
3812 eq = deepEquals((Object[]) e1, (Object[]) e2);
3813 else if (e1 instanceof byte[] && e2 instanceof byte[])
3814 eq = equals((byte[]) e1, (byte[]) e2);
3815 else if (e1 instanceof short[] && e2 instanceof short[])
3816 eq = equals((short[]) e1, (short[]) e2);
3817 else if (e1 instanceof int[] && e2 instanceof int[])
3818 eq = equals((int[]) e1, (int[]) e2);
3819 else if (e1 instanceof long[] && e2 instanceof long[])
3820 eq = equals((long[]) e1, (long[]) e2);
3821 else if (e1 instanceof char[] && e2 instanceof char[])
3822 eq = equals((char[]) e1, (char[]) e2);
3823 else if (e1 instanceof float[] && e2 instanceof float[])
3824 eq = equals((float[]) e1, (float[]) e2);
3825 else if (e1 instanceof double[] && e2 instanceof double[])
3826 eq = equals((double[]) e1, (double[]) e2);
3827 else if (e1 instanceof boolean[] && e2 instanceof boolean[])
3828 eq = equals((boolean[]) e1, (boolean[]) e2);
3829 else
3830 eq = e1.equals(e2);
3831
3832 if (!eq)
3833 return false;
3834 }
3835 return true;
3836 }
3837
3838 /**
3839 * Returns a string representation of the contents of the specified array.
3840 * The string representation consists of a list of the array's elements,
3841 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
3842 * separated by the characters <tt>", "</tt> (a comma followed by a
3843 * space). Elements are converted to strings as by
3844 * <tt>String.valueOf(long)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
3845 * is <tt>null</tt>.
3846 *
3847 * @param a the array whose string representation to return
3848 * @return a string representation of <tt>a</tt>
3849 * @since 1.5
3850 */
3851 public static String toString(long[] a) {
3852 if (a == null)
3853 return "null";
3854 int iMax = a.length - 1;
3855 if (iMax == -1)
3856 return "[]";
3857
3858 StringBuilder b = new StringBuilder();
3859 b.append('[');
3860 for (int i = 0;; i++) {
3861 b.append(a[i]);
3862 if (i == iMax)
3863 return b.append(']').toString();
3864 b.append(", ");
3865 }
3866 }
3867
3868 /**
3869 * Returns a string representation of the contents of the specified array.
3870 * The string representation consists of a list of the array's elements,
3871 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
3872 * separated by the characters <tt>", "</tt> (a comma followed by a
3873 * space). Elements are converted to strings as by
3874 * <tt>String.valueOf(int)</tt>. Returns <tt>"null"</tt> if <tt>a</tt> is
3875 * <tt>null</tt>.
3876 *
3877 * @param a the array whose string representation to return
3878 * @return a string representation of <tt>a</tt>
3879 * @since 1.5
3880 */
3881 public static String toString(int[] a) {
3882 if (a == null)
3883 return "null";
3884 int iMax = a.length - 1;
3885 if (iMax == -1)
3886 return "[]";
3887
3888 StringBuilder b = new StringBuilder();
3889 b.append('[');
3890 for (int i = 0;; i++) {
3891 b.append(a[i]);
3892 if (i == iMax)
3893 return b.append(']').toString();
3894 b.append(", ");
3895 }
3896 }
3897
3898 /**
3899 * Returns a string representation of the contents of the specified array.
3900 * The string representation consists of a list of the array's elements,
3901 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
3902 * separated by the characters <tt>", "</tt> (a comma followed by a
3903 * space). Elements are converted to strings as by
3904 * <tt>String.valueOf(short)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
3905 * is <tt>null</tt>.
3906 *
3907 * @param a the array whose string representation to return
3908 * @return a string representation of <tt>a</tt>
3909 * @since 1.5
3910 */
3911 public static String toString(short[] a) {
3912 if (a == null)
3913 return "null";
3914 int iMax = a.length - 1;
3915 if (iMax == -1)
3916 return "[]";
3917
3918 StringBuilder b = new StringBuilder();
3919 b.append('[');
3920 for (int i = 0;; i++) {
3921 b.append(a[i]);
3922 if (i == iMax)
3923 return b.append(']').toString();
3924 b.append(", ");
3925 }
3926 }
3927
3928 /**
3929 * Returns a string representation of the contents of the specified array.
3930 * The string representation consists of a list of the array's elements,
3931 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
3932 * separated by the characters <tt>", "</tt> (a comma followed by a
3933 * space). Elements are converted to strings as by
3934 * <tt>String.valueOf(char)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
3935 * is <tt>null</tt>.
3936 *
3937 * @param a the array whose string representation to return
3938 * @return a string representation of <tt>a</tt>
3939 * @since 1.5
3940 */
3941 public static String toString(char[] a) {
3942 if (a == null)
3943 return "null";
3944 int iMax = a.length - 1;
3945 if (iMax == -1)
3946 return "[]";
3947
3948 StringBuilder b = new StringBuilder();
3949 b.append('[');
3950 for (int i = 0;; i++) {
3951 b.append(a[i]);
3952 if (i == iMax)
3953 return b.append(']').toString();
3954 b.append(", ");
3955 }
3956 }
3957
3958 /**
3959 * Returns a string representation of the contents of the specified array.
3960 * The string representation consists of a list of the array's elements,
3961 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements
3962 * are separated by the characters <tt>", "</tt> (a comma followed
3963 * by a space). Elements are converted to strings as by
3964 * <tt>String.valueOf(byte)</tt>. Returns <tt>"null"</tt> if
3965 * <tt>a</tt> is <tt>null</tt>.
3966 *
3967 * @param a the array whose string representation to return
3968 * @return a string representation of <tt>a</tt>
3969 * @since 1.5
3970 */
3971 public static String toString(byte[] a) {
3972 if (a == null)
3973 return "null";
3974 int iMax = a.length - 1;
3975 if (iMax == -1)
3976 return "[]";
3977
3978 StringBuilder b = new StringBuilder();
3979 b.append('[');
3980 for (int i = 0;; i++) {
3981 b.append(a[i]);
3982 if (i == iMax)
3983 return b.append(']').toString();
3984 b.append(", ");
3985 }
3986 }
3987
3988 /**
3989 * Returns a string representation of the contents of the specified array.
3990 * The string representation consists of a list of the array's elements,
3991 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
3992 * separated by the characters <tt>", "</tt> (a comma followed by a
3993 * space). Elements are converted to strings as by
3994 * <tt>String.valueOf(boolean)</tt>. Returns <tt>"null"</tt> if
3995 * <tt>a</tt> is <tt>null</tt>.
3996 *
3997 * @param a the array whose string representation to return
3998 * @return a string representation of <tt>a</tt>
3999 * @since 1.5
4000 */
4001 public static String toString(boolean[] a) {
4002 if (a == null)
4003 return "null";
4004 int iMax = a.length - 1;
4005 if (iMax == -1)
4006 return "[]";
4007
4008 StringBuilder b = new StringBuilder();
4009 b.append('[');
4010 for (int i = 0;; i++) {
4011 b.append(a[i]);
4012 if (i == iMax)
4013 return b.append(']').toString();
4014 b.append(", ");
4015 }
4016 }
4017
4018 /**
4019 * Returns a string representation of the contents of the specified array.
4020 * The string representation consists of a list of the array's elements,
4021 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
4022 * separated by the characters <tt>", "</tt> (a comma followed by a
4023 * space). Elements are converted to strings as by
4024 * <tt>String.valueOf(float)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
4025 * is <tt>null</tt>.
4026 *
4027 * @param a the array whose string representation to return
4028 * @return a string representation of <tt>a</tt>
4029 * @since 1.5
4030 */
4031 public static String toString(float[] a) {
4032 if (a == null)
4033 return "null";
4034 int iMax = a.length - 1;
4035 if (iMax == -1)
4036 return "[]";
4037
4038 StringBuilder b = new StringBuilder();
4039 b.append('[');
4040 for (int i = 0;; i++) {
4041 b.append(a[i]);
4042 if (i == iMax)
4043 return b.append(']').toString();
4044 b.append(", ");
4045 }
4046 }
4047
4048 /**
4049 * Returns a string representation of the contents of the specified array.
4050 * The string representation consists of a list of the array's elements,
4051 * enclosed in square brackets (<tt>"[]"</tt>). Adjacent elements are
4052 * separated by the characters <tt>", "</tt> (a comma followed by a
4053 * space). Elements are converted to strings as by
4054 * <tt>String.valueOf(double)</tt>. Returns <tt>"null"</tt> if <tt>a</tt>
4055 * is <tt>null</tt>.
4056 *
4057 * @param a the array whose string representation to return
4058 * @return a string representation of <tt>a</tt>
4059 * @since 1.5
4060 */
4061 public static String toString(double[] a) {
4062 if (a == null)
4063 return "null";
4064 int iMax = a.length - 1;
4065 if (iMax == -1)
4066 return "[]";
4067
4068 StringBuilder b = new StringBuilder();
4069 b.append('[');
4070 for (int i = 0;; i++) {
4071 b.append(a[i]);
4072 if (i == iMax)
4073 return b.append(']').toString();
4074 b.append(", ");
4075 }
4076 }
4077
4078 /**
4079 * Returns a string representation of the contents of the specified array.
4080 * If the array contains other arrays as elements, they are converted to
4081 * strings by the {@link Object#toString} method inherited from
4082 * <tt>Object</tt>, which describes their <i>identities</i> rather than
4083 * their contents.
4084 *
4085 * <p>The value returned by this method is equal to the value that would
4086 * be returned by <tt>Arrays.asList(a).toString()</tt>, unless <tt>a</tt>
4087 * is <tt>null</tt>, in which case <tt>"null"</tt> is returned.
4088 *
4089 * @param a the array whose string representation to return
4090 * @return a string representation of <tt>a</tt>
4091 * @see #deepToString(Object[])
4092 * @since 1.5
4093 */
4094 public static String toString(Object[] a) {
4095 if (a == null)
4096 return "null";
4097 int iMax = a.length - 1;
4098 if (iMax == -1)
4099 return "[]";
4100
4101 StringBuilder b = new StringBuilder();
4102 b.append('[');
4103 for (int i = 0;; i++) {
4104 b.append(String.valueOf(a[i]));
4105 if (i == iMax)
4106 return b.append(']').toString();
4107 b.append(", ");
4108 }
4109 }
4110
4111 /**
4112 * Returns a string representation of the "deep contents" of the specified
4113 * array. If the array contains other arrays as elements, the string
4114 * representation contains their contents and so on. This method is
4115 * designed for converting multidimensional arrays to strings.
4116 *
4117 * <p>The string representation consists of a list of the array's
4118 * elements, enclosed in square brackets (<tt>"[]"</tt>). Adjacent
4119 * elements are separated by the characters <tt>", "</tt> (a comma
4120 * followed by a space). Elements are converted to strings as by
4121 * <tt>String.valueOf(Object)</tt>, unless they are themselves
4122 * arrays.
4123 *
4124 * <p>If an element <tt>e</tt> is an array of a primitive type, it is
4125 * converted to a string as by invoking the appropriate overloading of
4126 * <tt>Arrays.toString(e)</tt>. If an element <tt>e</tt> is an array of a
4127 * reference type, it is converted to a string as by invoking
4128 * this method recursively.
4129 *
4130 * <p>To avoid infinite recursion, if the specified array contains itself
4131 * as an element, or contains an indirect reference to itself through one
4132 * or more levels of arrays, the self-reference is converted to the string
4133 * <tt>"[...]"</tt>. For example, an array containing only a reference
4134 * to itself would be rendered as <tt>"[[...]]"</tt>.
4135 *
4136 * <p>This method returns <tt>"null"</tt> if the specified array
4137 * is <tt>null</tt>.
4138 *
4139 * @param a the array whose string representation to return
4140 * @return a string representation of <tt>a</tt>
4141 * @see #toString(Object[])
4142 * @since 1.5
4143 */
4144 public static String deepToString(Object[] a) {
4145 if (a == null)
4146 return "null";
4147
4148 int bufLen = 20 * a.length;
4149 if (a.length != 0 && bufLen <= 0)
4150 bufLen = Integer.MAX_VALUE;
4151 StringBuilder buf = new StringBuilder(bufLen);
4152 deepToString(a, buf, new HashSet());
4153 return buf.toString();
4154 }
4155
4156 private static void deepToString(Object[] a, StringBuilder buf,
4157 Set<Object[]> dejaVu) {
4158 if (a == null) {
4159 buf.append("null");
4160 return;
4161 }
4162 dejaVu.add(a);
4163 buf.append('[');
4164 for (int i = 0; i < a.length; i++) {
4165 if (i != 0)
4166 buf.append(", ");
4167
4168 Object element = a[i];
4169 if (element == null) {
4170 buf.append("null");
4171 } else {
4172 Class eClass = element.getClass();
4173
4174 if (eClass.isArray()) {
4175 if (eClass == byte[].class)
4176 buf.append(toString((byte[]) element));
4177 else if (eClass == short[].class)
4178 buf.append(toString((short[]) element));
4179 else if (eClass == int[].class)
4180 buf.append(toString((int[]) element));
4181 else if (eClass == long[].class)
4182 buf.append(toString((long[]) element));
4183 else if (eClass == char[].class)
4184 buf.append(toString((char[]) element));
4185 else if (eClass == float[].class)
4186 buf.append(toString((float[]) element));
4187 else if (eClass == double[].class)
4188 buf.append(toString((double[]) element));
4189 else if (eClass == boolean[].class)
4190 buf.append(toString((boolean[]) element));
4191 else { // element is an array of object references
4192 if (dejaVu.contains(element))
4193 buf.append("[...]");
4194 else
4195 deepToString((Object[]) element, buf,
4196 dejaVu);
4197 }
4198 } else { // element is non-null and not an array
4199 buf.append(element.toString());
4200 }
4201 }
4202 }
4203 buf.append(']');
4204 dejaVu.remove(a);
4205 }
4206 }
|