/* * @(#)Arrays.java 1.62 05/06/08 * * Copyright 2004 Sun Microsystems, Inc. All rights reserved. * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. */ package java.util; import java.util.*; // for javadoc import java.lang.reflect.*; /** * This class contains various methods for manipulating arrays (such as * sorting and searching). This class also contains a static factory * that allows arrays to be viewed as lists. * *

The methods in this class all throw a NullPointerException if * the specified array reference is null, except where noted. * *

The documentation for the methods contained in this class includes * briefs description of the implementations. Such descriptions should * be regarded as implementation notes, rather than parts of the * specification. Implementors should feel free to substitute other * algorithms, so long as the specification itself is adhered to. (For * example, the algorithm used by sort(Object[]) does not have to be * a mergesort, but it does have to be stable.) * *

This class is a member of the * * Java Collections Framework. * * @author Josh Bloch * @author Neal Gafter * @author John Rose * @version 1.62, 06/08/05 * @see Comparable * @see Comparator * @since 1.2 */ public class Arrays { // Suppresses default constructor, ensuring non-instantiability. private Arrays() { } // Sorting /** * Sorts the specified array of longs into ascending numerical order. * The sorting algorithm is a tuned quicksort, adapted from Jon * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November * 1993). This algorithm offers n*log(n) performance on many data sets * that cause other quicksorts to degrade to quadratic performance. * * @param a the array to be sorted. */ public static void sort(long[] a) { sort1(a, 0, a.length); } /** * Sorts the specified range of the specified array of longs into * ascending numerical order. The range to be sorted extends from index * fromIndex, inclusive, to index toIndex, exclusive. * (If fromIndex==toIndex, the range to be sorted is empty.) * *

The sorting algorithm is a tuned quicksort, adapted from Jon * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November * 1993). This algorithm offers n*log(n) performance on many data sets * that cause other quicksorts to degrade to quadratic performance. * * @param a the array to be sorted. * @param fromIndex the index of the first element (inclusive) to be * sorted. * @param toIndex the index of the last element (exclusive) to be sorted. * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void sort(long[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); sort1(a, fromIndex, toIndex-fromIndex); } /** * Sorts the specified array of ints into ascending numerical order. * The sorting algorithm is a tuned quicksort, adapted from Jon * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November * 1993). This algorithm offers n*log(n) performance on many data sets * that cause other quicksorts to degrade to quadratic performance. * * @param a the array to be sorted. */ public static void sort(int[] a) { sort1(a, 0, a.length); } /** * Sorts the specified range of the specified array of ints into * ascending numerical order. The range to be sorted extends from index * fromIndex, inclusive, to index toIndex, exclusive. * (If fromIndex==toIndex, the range to be sorted is empty.)

* * The sorting algorithm is a tuned quicksort, adapted from Jon * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November * 1993). This algorithm offers n*log(n) performance on many data sets * that cause other quicksorts to degrade to quadratic performance. * * @param a the array to be sorted. * @param fromIndex the index of the first element (inclusive) to be * sorted. * @param toIndex the index of the last element (exclusive) to be sorted. * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void sort(int[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); sort1(a, fromIndex, toIndex-fromIndex); } /** * Sorts the specified array of shorts into ascending numerical order. * The sorting algorithm is a tuned quicksort, adapted from Jon * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November * 1993). This algorithm offers n*log(n) performance on many data sets * that cause other quicksorts to degrade to quadratic performance. * * @param a the array to be sorted. */ public static void sort(short[] a) { sort1(a, 0, a.length); } /** * Sorts the specified range of the specified array of shorts into * ascending numerical order. The range to be sorted extends from index * fromIndex, inclusive, to index toIndex, exclusive. * (If fromIndex==toIndex, the range to be sorted is empty.)

* * The sorting algorithm is a tuned quicksort, adapted from Jon * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November * 1993). This algorithm offers n*log(n) performance on many data sets * that cause other quicksorts to degrade to quadratic performance. * * @param a the array to be sorted. * @param fromIndex the index of the first element (inclusive) to be * sorted. * @param toIndex the index of the last element (exclusive) to be sorted. * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void sort(short[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); sort1(a, fromIndex, toIndex-fromIndex); } /** * Sorts the specified array of chars into ascending numerical order. * The sorting algorithm is a tuned quicksort, adapted from Jon * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November * 1993). This algorithm offers n*log(n) performance on many data sets * that cause other quicksorts to degrade to quadratic performance. * * @param a the array to be sorted. */ public static void sort(char[] a) { sort1(a, 0, a.length); } /** * Sorts the specified range of the specified array of chars into * ascending numerical order. The range to be sorted extends from index * fromIndex, inclusive, to index toIndex, exclusive. * (If fromIndex==toIndex, the range to be sorted is empty.)

* * The sorting algorithm is a tuned quicksort, adapted from Jon * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November * 1993). This algorithm offers n*log(n) performance on many data sets * that cause other quicksorts to degrade to quadratic performance. * * @param a the array to be sorted. * @param fromIndex the index of the first element (inclusive) to be * sorted. * @param toIndex the index of the last element (exclusive) to be sorted. * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void sort(char[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); sort1(a, fromIndex, toIndex-fromIndex); } /** * Sorts the specified array of bytes into ascending numerical order. * The sorting algorithm is a tuned quicksort, adapted from Jon * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November * 1993). This algorithm offers n*log(n) performance on many data sets * that cause other quicksorts to degrade to quadratic performance. * * @param a the array to be sorted. */ public static void sort(byte[] a) { sort1(a, 0, a.length); } /** * Sorts the specified range of the specified array of bytes into * ascending numerical order. The range to be sorted extends from index * fromIndex, inclusive, to index toIndex, exclusive. * (If fromIndex==toIndex, the range to be sorted is empty.)

* The < relation does not provide a total order on * all floating-point values; although they are distinct numbers * -0.0 == 0.0 is true and a NaN value * compares neither less than, greater than, nor equal to any * floating-point value, even itself. To allow the sort to * proceed, instead of using the < relation to * determine ascending numerical order, this method uses the total * order imposed by {@link Double#compareTo}. This ordering * differs from the < relation in that * -0.0 is treated as less than 0.0 and * NaN is considered greater than any other floating-point value. * For the purposes of sorting, all NaN values are considered * equivalent and equal. *

* The < relation does not provide a total order on * all floating-point values; although they are distinct numbers * -0.0f == 0.0f is true and a NaN value * compares neither less than, greater than, nor equal to any * floating-point value, even itself. To allow the sort to * proceed, instead of using the < relation to * determine ascending numerical order, this method uses the total * order imposed by {@link Float#compareTo}. This ordering * differs from the < relation in that * -0.0f is treated as less than 0.0f and * NaN is considered greater than any other floating-point value. * For the purposes of sorting, all NaN values are considered * equivalent and equal. *

* The sorting algorithm is a tuned quicksort, adapted from Jon * L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", * Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November * 1993). This algorithm offers n*log(n) performance on many data sets * that cause other quicksorts to degrade to quadratic performance. * * @param a the array to be sorted. * @param fromIndex the index of the first element (inclusive) to be * sorted. * @param toIndex the index of the last element (exclusive) to be sorted. * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void sort(float[] a, int fromIndex, int toIndex) { rangeCheck(a.length, fromIndex, toIndex); sort2(a, fromIndex, toIndex); } private static void sort2(double a[], int fromIndex, int toIndex) { final long NEG_ZERO_BITS = Double.doubleToLongBits(-0.0d); /* * The sort is done in three phases to avoid the expense of using * NaN and -0.0 aware comparisons during the main sort. */ /* * Preprocessing phase: Move any NaN's to end of array, count the * number of -0.0's, and turn them into 0.0's. */ int numNegZeros = 0; int i = fromIndex, n = toIndex; while(i < n) { if (a[i] != a[i]) { double swap = a[i]; a[i] = a[--n]; a[n] = swap; } else { if (a[i]==0 && Double.doubleToLongBits(a[i])==NEG_ZERO_BITS) { a[i] = 0.0d; numNegZeros++; } i++; } } // Main sort phase: quicksort everything but the NaN's sort1(a, fromIndex, n-fromIndex); // Postprocessing phase: change 0.0's to -0.0's as required if (numNegZeros != 0) { int j = binarySearch(a, 0.0d, fromIndex, n-1); // posn of ANY zero do { j--; } while (j>=0 && a[j]==0.0d); // j is now one less than the index of the FIRST zero for (int k=0; k=0 && a[j]==0.0f); // j is now one less than the index of the FIRST zero for (int k=0; koff && x[j-1]>x[j]; j--) swap(x, j, j-1); return; } // Choose a partition element, v int m = off + (len >> 1); // Small arrays, middle element if (len > 7) { int l = off; int n = off + len - 1; if (len > 40) { // Big arrays, pseudomedian of 9 int s = len/8; l = med3(x, l, l+s, l+2*s); m = med3(x, m-s, m, m+s); n = med3(x, n-2*s, n-s, n); } m = med3(x, l, m, n); // Mid-size, med of 3 } long v = x[m]; // Establish Invariant: v* (v)* v* int a = off, b = a, c = off + len - 1, d = c; while(true) { while (b <= c && x[b] <= v) { if (x[b] == v) swap(x, a++, b); b++; } while (c >= b && x[c] >= v) { if (x[c] == v) swap(x, c, d--); c--; } if (b > c) break; swap(x, b++, c--); } // Swap partition elements back to middle int s, n = off + len; s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s); s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s); // Recursively sort non-partition-elements if ((s = b-a) > 1) sort1(x, off, s); if ((s = d-c) > 1) sort1(x, n-s, s); } /** * Swaps x[a] with x[b]. */ private static void swap(long x[], int a, int b) { long t = x[a]; x[a] = x[b]; x[b] = t; } /** * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. */ private static void vecswap(long x[], int a, int b, int n) { for (int i=0; i x[c] ? b : x[a] > x[c] ? c : a)); } /** * Sorts the specified sub-array of integers into ascending order. */ private static void sort1(int x[], int off, int len) { // Insertion sort on smallest arrays if (len < 7) { for (int i=off; ioff && x[j-1]>x[j]; j--) swap(x, j, j-1); return; } // Choose a partition element, v int m = off + (len >> 1); // Small arrays, middle element if (len > 7) { int l = off; int n = off + len - 1; if (len > 40) { // Big arrays, pseudomedian of 9 int s = len/8; l = med3(x, l, l+s, l+2*s); m = med3(x, m-s, m, m+s); n = med3(x, n-2*s, n-s, n); } m = med3(x, l, m, n); // Mid-size, med of 3 } int v = x[m]; // Establish Invariant: v* (v)* v* int a = off, b = a, c = off + len - 1, d = c; while(true) { while (b <= c && x[b] <= v) { if (x[b] == v) swap(x, a++, b); b++; } while (c >= b && x[c] >= v) { if (x[c] == v) swap(x, c, d--); c--; } if (b > c) break; swap(x, b++, c--); } // Swap partition elements back to middle int s, n = off + len; s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s); s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s); // Recursively sort non-partition-elements if ((s = b-a) > 1) sort1(x, off, s); if ((s = d-c) > 1) sort1(x, n-s, s); } /** * Swaps x[a] with x[b]. */ private static void swap(int x[], int a, int b) { int t = x[a]; x[a] = x[b]; x[b] = t; } /** * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. */ private static void vecswap(int x[], int a, int b, int n) { for (int i=0; i x[c] ? b : x[a] > x[c] ? c : a)); } /** * Sorts the specified sub-array of shorts into ascending order. */ private static void sort1(short x[], int off, int len) { // Insertion sort on smallest arrays if (len < 7) { for (int i=off; ioff && x[j-1]>x[j]; j--) swap(x, j, j-1); return; } // Choose a partition element, v int m = off + (len >> 1); // Small arrays, middle element if (len > 7) { int l = off; int n = off + len - 1; if (len > 40) { // Big arrays, pseudomedian of 9 int s = len/8; l = med3(x, l, l+s, l+2*s); m = med3(x, m-s, m, m+s); n = med3(x, n-2*s, n-s, n); } m = med3(x, l, m, n); // Mid-size, med of 3 } short v = x[m]; // Establish Invariant: v* (v)* v* int a = off, b = a, c = off + len - 1, d = c; while(true) { while (b <= c && x[b] <= v) { if (x[b] == v) swap(x, a++, b); b++; } while (c >= b && x[c] >= v) { if (x[c] == v) swap(x, c, d--); c--; } if (b > c) break; swap(x, b++, c--); } // Swap partition elements back to middle int s, n = off + len; s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s); s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s); // Recursively sort non-partition-elements if ((s = b-a) > 1) sort1(x, off, s); if ((s = d-c) > 1) sort1(x, n-s, s); } /** * Swaps x[a] with x[b]. */ private static void swap(short x[], int a, int b) { short t = x[a]; x[a] = x[b]; x[b] = t; } /** * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. */ private static void vecswap(short x[], int a, int b, int n) { for (int i=0; i x[c] ? b : x[a] > x[c] ? c : a)); } /** * Sorts the specified sub-array of chars into ascending order. */ private static void sort1(char x[], int off, int len) { // Insertion sort on smallest arrays if (len < 7) { for (int i=off; ioff && x[j-1]>x[j]; j--) swap(x, j, j-1); return; } // Choose a partition element, v int m = off + (len >> 1); // Small arrays, middle element if (len > 7) { int l = off; int n = off + len - 1; if (len > 40) { // Big arrays, pseudomedian of 9 int s = len/8; l = med3(x, l, l+s, l+2*s); m = med3(x, m-s, m, m+s); n = med3(x, n-2*s, n-s, n); } m = med3(x, l, m, n); // Mid-size, med of 3 } char v = x[m]; // Establish Invariant: v* (v)* v* int a = off, b = a, c = off + len - 1, d = c; while(true) { while (b <= c && x[b] <= v) { if (x[b] == v) swap(x, a++, b); b++; } while (c >= b && x[c] >= v) { if (x[c] == v) swap(x, c, d--); c--; } if (b > c) break; swap(x, b++, c--); } // Swap partition elements back to middle int s, n = off + len; s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s); s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s); // Recursively sort non-partition-elements if ((s = b-a) > 1) sort1(x, off, s); if ((s = d-c) > 1) sort1(x, n-s, s); } /** * Swaps x[a] with x[b]. */ private static void swap(char x[], int a, int b) { char t = x[a]; x[a] = x[b]; x[b] = t; } /** * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. */ private static void vecswap(char x[], int a, int b, int n) { for (int i=0; i x[c] ? b : x[a] > x[c] ? c : a)); } /** * Sorts the specified sub-array of bytes into ascending order. */ private static void sort1(byte x[], int off, int len) { // Insertion sort on smallest arrays if (len < 7) { for (int i=off; ioff && x[j-1]>x[j]; j--) swap(x, j, j-1); return; } // Choose a partition element, v int m = off + (len >> 1); // Small arrays, middle element if (len > 7) { int l = off; int n = off + len - 1; if (len > 40) { // Big arrays, pseudomedian of 9 int s = len/8; l = med3(x, l, l+s, l+2*s); m = med3(x, m-s, m, m+s); n = med3(x, n-2*s, n-s, n); } m = med3(x, l, m, n); // Mid-size, med of 3 } byte v = x[m]; // Establish Invariant: v* (v)* v* int a = off, b = a, c = off + len - 1, d = c; while(true) { while (b <= c && x[b] <= v) { if (x[b] == v) swap(x, a++, b); b++; } while (c >= b && x[c] >= v) { if (x[c] == v) swap(x, c, d--); c--; } if (b > c) break; swap(x, b++, c--); } // Swap partition elements back to middle int s, n = off + len; s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s); s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s); // Recursively sort non-partition-elements if ((s = b-a) > 1) sort1(x, off, s); if ((s = d-c) > 1) sort1(x, n-s, s); } /** * Swaps x[a] with x[b]. */ private static void swap(byte x[], int a, int b) { byte t = x[a]; x[a] = x[b]; x[b] = t; } /** * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. */ private static void vecswap(byte x[], int a, int b, int n) { for (int i=0; i x[c] ? b : x[a] > x[c] ? c : a)); } /** * Sorts the specified sub-array of doubles into ascending order. */ private static void sort1(double x[], int off, int len) { // Insertion sort on smallest arrays if (len < 7) { for (int i=off; ioff && x[j-1]>x[j]; j--) swap(x, j, j-1); return; } // Choose a partition element, v int m = off + (len >> 1); // Small arrays, middle element if (len > 7) { int l = off; int n = off + len - 1; if (len > 40) { // Big arrays, pseudomedian of 9 int s = len/8; l = med3(x, l, l+s, l+2*s); m = med3(x, m-s, m, m+s); n = med3(x, n-2*s, n-s, n); } m = med3(x, l, m, n); // Mid-size, med of 3 } double v = x[m]; // Establish Invariant: v* (v)* v* int a = off, b = a, c = off + len - 1, d = c; while(true) { while (b <= c && x[b] <= v) { if (x[b] == v) swap(x, a++, b); b++; } while (c >= b && x[c] >= v) { if (x[c] == v) swap(x, c, d--); c--; } if (b > c) break; swap(x, b++, c--); } // Swap partition elements back to middle int s, n = off + len; s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s); s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s); // Recursively sort non-partition-elements if ((s = b-a) > 1) sort1(x, off, s); if ((s = d-c) > 1) sort1(x, n-s, s); } /** * Swaps x[a] with x[b]. */ private static void swap(double x[], int a, int b) { double t = x[a]; x[a] = x[b]; x[b] = t; } /** * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. */ private static void vecswap(double x[], int a, int b, int n) { for (int i=0; i x[c] ? b : x[a] > x[c] ? c : a)); } /** * Sorts the specified sub-array of floats into ascending order. */ private static void sort1(float x[], int off, int len) { // Insertion sort on smallest arrays if (len < 7) { for (int i=off; ioff && x[j-1]>x[j]; j--) swap(x, j, j-1); return; } // Choose a partition element, v int m = off + (len >> 1); // Small arrays, middle element if (len > 7) { int l = off; int n = off + len - 1; if (len > 40) { // Big arrays, pseudomedian of 9 int s = len/8; l = med3(x, l, l+s, l+2*s); m = med3(x, m-s, m, m+s); n = med3(x, n-2*s, n-s, n); } m = med3(x, l, m, n); // Mid-size, med of 3 } float v = x[m]; // Establish Invariant: v* (v)* v* int a = off, b = a, c = off + len - 1, d = c; while(true) { while (b <= c && x[b] <= v) { if (x[b] == v) swap(x, a++, b); b++; } while (c >= b && x[c] >= v) { if (x[c] == v) swap(x, c, d--); c--; } if (b > c) break; swap(x, b++, c--); } // Swap partition elements back to middle int s, n = off + len; s = Math.min(a-off, b-a ); vecswap(x, off, b-s, s); s = Math.min(d-c, n-d-1); vecswap(x, b, n-s, s); // Recursively sort non-partition-elements if ((s = b-a) > 1) sort1(x, off, s); if ((s = d-c) > 1) sort1(x, n-s, s); } /** * Swaps x[a] with x[b]. */ private static void swap(float x[], int a, int b) { float t = x[a]; x[a] = x[b]; x[b] = t; } /** * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)]. */ private static void vecswap(float x[], int a, int b, int n) { for (int i=0; i x[c] ? b : x[a] > x[c] ? c : a)); } /** * Sorts the specified array of objects into ascending order, according to * the natural ordering of its elements. All elements in the array * must implement the Comparable interface. Furthermore, all * elements in the array must be mutually comparable (that is, * e1.compareTo(e2) must not throw a ClassCastException * for any elements e1 and e2 in the array).

* * This sort is guaranteed to be stable: equal elements will * not be reordered as a result of the sort.

* * The sorting algorithm is a modified mergesort (in which the merge is * omitted if the highest element in the low sublist is less than the * lowest element in the high sublist). This algorithm offers guaranteed * n*log(n) performance. * * @param a the array to be sorted. * @param fromIndex the index of the first element (inclusive) to be * sorted. * @param toIndex the index of the last element (exclusive) to be sorted. * @param c the comparator to determine the order of the array. A * null value indicates that the elements' natural * ordering should be used. * @throws ClassCastException if the array contains elements that are not * mutually comparable using the specified comparator. * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length * @see Comparator */ public static void sort(T[] a, int fromIndex, int toIndex, Comparator c) { rangeCheck(a.length, fromIndex, toIndex); T[] aux = (T[])copyOfRange(a, fromIndex, toIndex); if (c==null) mergeSort(aux, a, fromIndex, toIndex, -fromIndex); else mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c); } /** * Src is the source array that starts at index 0 * Dest is the (possibly larger) array destination with a possible offset * low is the index in dest to start sorting * high is the end index in dest to end sorting * off is the offset into src corresponding to low in dest */ private static void mergeSort(Object[] src, Object[] dest, int low, int high, int off, Comparator c) { int length = high - low; // Insertion sort on smallest arrays if (length < INSERTIONSORT_THRESHOLD) { for (int i=low; ilow && c.compare(dest[j-1], dest[j])>0; j--) swap(dest, j, j-1); return; } // Recursively sort halves of dest into src int destLow = low; int destHigh = high; low += off; high += off; int mid = (low + high) >> 1; mergeSort(dest, src, low, mid, -off, c); mergeSort(dest, src, mid, high, -off, c); // If list is already sorted, just copy from src to dest. This is an // optimization that results in faster sorts for nearly ordered lists. if (c.compare(src[mid-1], src[mid]) <= 0) { System.arraycopy(src, low, dest, destLow, length); return; } // Merge sorted halves (now in src) into dest for(int i = destLow, p = low, q = mid; i < destHigh; i++) { if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0) dest[i] = src[p++]; else dest[i] = src[q++]; } } /** * Check that fromIndex and toIndex are in range, and throw an * appropriate exception if they aren't. */ private static void rangeCheck(int arrayLen, int fromIndex, int toIndex) { if (fromIndex > toIndex) throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex+")"); if (fromIndex < 0) throw new ArrayIndexOutOfBoundsException(fromIndex); if (toIndex > arrayLen) throw new ArrayIndexOutOfBoundsException(toIndex); } // Searching /** * Searches the specified array of longs for the specified value using the * binary search algorithm. The array must be sorted (as * by the sort method, above) prior to making this call. If it * is not sorted, the results are undefined. If the array contains * multiple elements with the specified value, there is no guarantee which * one will be found. * * @param a the array to be searched. * @param key the value to be searched for. * @return index of the search key, if it is contained in the array; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length, if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @see #sort(long[]) */ public static int binarySearch(long[] a, long key) { int low = 0; int high = a.length-1; while (low <= high) { int mid = (low + high) >> 1; long midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } /** * Searches the specified array of ints for the specified value using the * binary search algorithm. The array must be sorted (as * by the sort method, above) prior to making this call. If it * is not sorted, the results are undefined. If the array contains * multiple elements with the specified value, there is no guarantee which * one will be found. * * @param a the array to be searched. * @param key the value to be searched for. * @return index of the search key, if it is contained in the array; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length, if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @see #sort(int[]) */ public static int binarySearch(int[] a, int key) { int low = 0; int high = a.length-1; while (low <= high) { int mid = (low + high) >> 1; int midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } /** * Searches the specified array of shorts for the specified value using * the binary search algorithm. The array must be sorted * (as by the sort method, above) prior to making this call. If * it is not sorted, the results are undefined. If the array contains * multiple elements with the specified value, there is no guarantee which * one will be found. * * @param a the array to be searched. * @param key the value to be searched for. * @return index of the search key, if it is contained in the array; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length, if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @see #sort(short[]) */ public static int binarySearch(short[] a, short key) { int low = 0; int high = a.length-1; while (low <= high) { int mid = (low + high) >> 1; short midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } /** * Searches the specified array of chars for the specified value using the * binary search algorithm. The array must be sorted (as * by the sort method, above) prior to making this call. If it * is not sorted, the results are undefined. If the array contains * multiple elements with the specified value, there is no guarantee which * one will be found. * * @param a the array to be searched. * @param key the value to be searched for. * @return index of the search key, if it is contained in the array; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length, if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @see #sort(char[]) */ public static int binarySearch(char[] a, char key) { int low = 0; int high = a.length-1; while (low <= high) { int mid = (low + high) >> 1; char midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } /** * Searches the specified array of bytes for the specified value using the * binary search algorithm. The array must be sorted (as * by the sort method, above) prior to making this call. If it * is not sorted, the results are undefined. If the array contains * multiple elements with the specified value, there is no guarantee which * one will be found. * * @param a the array to be searched. * @param key the value to be searched for. * @return index of the search key, if it is contained in the array; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length, if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @see #sort(byte[]) */ public static int binarySearch(byte[] a, byte key) { int low = 0; int high = a.length-1; while (low <= high) { int mid = (low + high) >> 1; byte midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } /** * Searches the specified array of doubles for the specified value using * the binary search algorithm. The array must be sorted * (as by the sort method, above) prior to making this call. If * it is not sorted, the results are undefined. If the array contains * multiple elements with the specified value, there is no guarantee which * one will be found. This method considers all NaN values to be * equivalent and equal. * * @param a the array to be searched. * @param key the value to be searched for. * @return index of the search key, if it is contained in the array; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length, if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @see #sort(double[]) */ public static int binarySearch(double[] a, double key) { return binarySearch(a, key, 0, a.length-1); } private static int binarySearch(double[] a, double key, int low,int high) { while (low <= high) { int mid = (low + high) >> 1; double midVal = a[mid]; int cmp; if (midVal < key) { cmp = -1; // Neither val is NaN, thisVal is smaller } else if (midVal > key) { cmp = 1; // Neither val is NaN, thisVal is larger } else { long midBits = Double.doubleToLongBits(midVal); long keyBits = Double.doubleToLongBits(key); cmp = (midBits == keyBits ? 0 : // Values are equal (midBits < keyBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN) 1)); // (0.0, -0.0) or (NaN, !NaN) } if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } /** * Searches the specified array of floats for the specified value using * the binary search algorithm. The array must be sorted * (as by the sort method, above) prior to making this call. If * it is not sorted, the results are undefined. If the array contains * multiple elements with the specified value, there is no guarantee which * one will be found. This method considers all NaN values to be * equivalent and equal. * * @param a the array to be searched. * @param key the value to be searched for. * @return index of the search key, if it is contained in the array; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length, if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @see #sort(float[]) */ public static int binarySearch(float[] a, float key) { return binarySearch(a, key, 0, a.length-1); } private static int binarySearch(float[] a, float key, int low,int high) { while (low <= high) { int mid = (low + high) >> 1; float midVal = a[mid]; int cmp; if (midVal < key) { cmp = -1; // Neither val is NaN, thisVal is smaller } else if (midVal > key) { cmp = 1; // Neither val is NaN, thisVal is larger } else { int midBits = Float.floatToIntBits(midVal); int keyBits = Float.floatToIntBits(key); cmp = (midBits == keyBits ? 0 : // Values are equal (midBits < keyBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN) 1)); // (0.0, -0.0) or (NaN, !NaN) } if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } /** * Searches the specified array for the specified object using the binary * search algorithm. The array must be sorted into ascending order * according to the natural ordering of its elements (as by * Sort(Object[]), above) prior to making this call. If it is * not sorted, the results are undefined. * (If the array contains elements that are not mutually comparable (for * example,strings and integers), it cannot be sorted according * to the natural order of its elements, hence results are undefined.) * If the array contains multiple * elements equal to the specified object, there is no guarantee which * one will be found. * * @param a the array to be searched. * @param key the value to be searched for. * @return index of the search key, if it is contained in the array; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length, if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @throws ClassCastException if the search key in not comparable to the * elements of the array. * @see Comparable * @see #sort(Object[]) */ public static int binarySearch(Object[] a, Object key) { int low = 0; int high = a.length-1; while (low <= high) { int mid = (low + high) >> 1; Comparable midVal = (Comparable)a[mid]; int cmp = midVal.compareTo(key); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } /** * Searches the specified array for the specified object using the binary * search algorithm. The array must be sorted into ascending order * according to the specified comparator (as by the Sort(Object[], * Comparator) method, above), prior to making this call. If it is * not sorted, the results are undefined. * If the array contains multiple * elements equal to the specified object, there is no guarantee which one * will be found. * * @param a the array to be searched. * @param key the value to be searched for. * @param c the comparator by which the array is ordered. A * null value indicates that the elements' natural * ordering should be used. * @return index of the search key, if it is contained in the array; * otherwise, (-(insertion point) - 1). The * insertion point is defined as the point at which the * key would be inserted into the array: the index of the first * element greater than the key, or a.length, if all * elements in the array are less than the specified key. Note * that this guarantees that the return value will be >= 0 if * and only if the key is found. * @throws ClassCastException if the array contains elements that are not * mutually comparable using the specified comparator, * or the search key in not mutually comparable with the * elements of the array using this comparator. * @see Comparable * @see #sort(Object[], Comparator) */ public static int binarySearch(T[] a, T key, Comparator c) { if (c==null) { return binarySearch(a, key); } int low = 0; int high = a.length-1; while (low <= high) { int mid = (low + high) >> 1; T midVal = a[mid]; int cmp = c.compare(midVal, key); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } // Equality Testing /** * Returns true if the two specified arrays of longs are * equal to one another. Two arrays are considered equal if both * arrays contain the same number of elements, and all corresponding pairs * of elements in the two arrays are equal. In other words, two arrays * are equal if they contain the same elements in the same order. Also, * two array references are considered equal if both are null.

* * @param a one array to be tested for equality. * @param a2 the other array to be tested for equality. * @return true if the two arrays are equal. */ public static boolean equals(long[] a, long[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; itrue if the two specified arrays of ints are * equal to one another. Two arrays are considered equal if both * arrays contain the same number of elements, and all corresponding pairs * of elements in the two arrays are equal. In other words, two arrays * are equal if they contain the same elements in the same order. Also, * two array references are considered equal if both are null.

* * @param a one array to be tested for equality. * @param a2 the other array to be tested for equality. * @return true if the two arrays are equal. */ public static boolean equals(int[] a, int[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; itrue if the two specified arrays of shorts are * equal to one another. Two arrays are considered equal if both * arrays contain the same number of elements, and all corresponding pairs * of elements in the two arrays are equal. In other words, two arrays * are equal if they contain the same elements in the same order. Also, * two array references are considered equal if both are null.

* * @param a one array to be tested for equality. * @param a2 the other array to be tested for equality. * @return true if the two arrays are equal. */ public static boolean equals(short[] a, short a2[]) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; itrue if the two specified arrays of chars are * equal to one another. Two arrays are considered equal if both * arrays contain the same number of elements, and all corresponding pairs * of elements in the two arrays are equal. In other words, two arrays * are equal if they contain the same elements in the same order. Also, * two array references are considered equal if both are null.

* * @param a one array to be tested for equality. * @param a2 the other array to be tested for equality. * @return true if the two arrays are equal. */ public static boolean equals(char[] a, char[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; itrue if the two specified arrays of bytes are * equal to one another. Two arrays are considered equal if both * arrays contain the same number of elements, and all corresponding pairs * of elements in the two arrays are equal. In other words, two arrays * are equal if they contain the same elements in the same order. Also, * two array references are considered equal if both are null.

* * @param a one array to be tested for equality. * @param a2 the other array to be tested for equality. * @return true if the two arrays are equal. */ public static boolean equals(byte[] a, byte[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; itrue if the two specified arrays of booleans are * equal to one another. Two arrays are considered equal if both * arrays contain the same number of elements, and all corresponding pairs * of elements in the two arrays are equal. In other words, two arrays * are equal if they contain the same elements in the same order. Also, * two array references are considered equal if both are null.

* * @param a one array to be tested for equality. * @param a2 the other array to be tested for equality. * @return true if the two arrays are equal. */ public static boolean equals(boolean[] a, boolean[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; itrue if the two specified arrays of doubles are * equal to one another. Two arrays are considered equal if both * arrays contain the same number of elements, and all corresponding pairs * of elements in the two arrays are equal. In other words, two arrays * are equal if they contain the same elements in the same order. Also, * two array references are considered equal if both are null.

* * Two doubles d1 and d2 are considered equal if: *

    new Double(d1).equals(new Double(d2))

* (Unlike the == operator, this method considers * NaN equals to itself, and 0.0d unequal to -0.0d.) * * @param a one array to be tested for equality. * @param a2 the other array to be tested for equality. * @return true if the two arrays are equal. * @see Double#equals(Object) */ public static boolean equals(double[] a, double[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; itrue if the two specified arrays of floats are * equal to one another. Two arrays are considered equal if both * arrays contain the same number of elements, and all corresponding pairs * of elements in the two arrays are equal. In other words, two arrays * are equal if they contain the same elements in the same order. Also, * two array references are considered equal if both are null.

* * Two floats f1 and f2 are considered equal if: *

    new Float(f1).equals(new Float(f2))

* (Unlike the == operator, this method considers * NaN equals to itself, and 0.0f unequal to -0.0f.) * * @param a one array to be tested for equality. * @param a2 the other array to be tested for equality. * @return true if the two arrays are equal. * @see Float#equals(Object) */ public static boolean equals(float[] a, float[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; itrue if the two specified arrays of Objects are * equal to one another. The two arrays are considered equal if * both arrays contain the same number of elements, and all corresponding * pairs of elements in the two arrays are equal. Two objects e1 * and e2 are considered equal if (e1==null ? e2==null * : e1.equals(e2)). In other words, the two arrays are equal if * they contain the same elements in the same order. Also, two array * references are considered equal if both are null.

* * @param a one array to be tested for equality. * @param a2 the other array to be tested for equality. * @return true if the two arrays are equal. */ public static boolean equals(Object[] a, Object[] a2) { if (a==a2) return true; if (a==null || a2==null) return false; int length = a.length; if (a2.length != length) return false; for (int i=0; ifromIndex, inclusive, to index * toIndex, exclusive. (If fromIndex==toIndex, the * range to be filled is empty.) * * @param a the array to be filled. * @param fromIndex the index of the first element (inclusive) to be * filled with the specified value. * @param toIndex the index of the last element (exclusive) to be * filled with the specified value. * @param val the value to be stored in all elements of the array. * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void fill(long[] a, int fromIndex, int toIndex, long val) { rangeCheck(a.length, fromIndex, toIndex); for (int i=fromIndex; ifromIndex, inclusive, to index * toIndex, exclusive. (If fromIndex==toIndex, the * range to be filled is empty.) * * @param a the array to be filled. * @param fromIndex the index of the first element (inclusive) to be * filled with the specified value. * @param toIndex the index of the last element (exclusive) to be * filled with the specified value. * @param val the value to be stored in all elements of the array. * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void fill(int[] a, int fromIndex, int toIndex, int val) { rangeCheck(a.length, fromIndex, toIndex); for (int i=fromIndex; ifromIndex, inclusive, to index * toIndex, exclusive. (If fromIndex==toIndex, the * range to be filled is empty.) * * @param a the array to be filled. * @param fromIndex the index of the first element (inclusive) to be * filled with the specified value. * @param toIndex the index of the last element (exclusive) to be * filled with the specified value. * @param val the value to be stored in all elements of the array. * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void fill(short[] a, int fromIndex, int toIndex, short val) { rangeCheck(a.length, fromIndex, toIndex); for (int i=fromIndex; ifromIndex, inclusive, to index * toIndex, exclusive. (If fromIndex==toIndex, the * range to be filled is empty.) * * @param a the array to be filled. * @param fromIndex the index of the first element (inclusive) to be * filled with the specified value. * @param toIndex the index of the last element (exclusive) to be * filled with the specified value. * @param val the value to be stored in all elements of the array. * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void fill(char[] a, int fromIndex, int toIndex, char val) { rangeCheck(a.length, fromIndex, toIndex); for (int i=fromIndex; ifromIndex, inclusive, to index * toIndex, exclusive. (If fromIndex==toIndex, the * range to be filled is empty.) * * @param a the array to be filled. * @param fromIndex the index of the first element (inclusive) to be * filled with the specified value. * @param toIndex the index of the last element (exclusive) to be * filled with the specified value. * @param val the value to be stored in all elements of the array. * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void fill(byte[] a, int fromIndex, int toIndex, byte val) { rangeCheck(a.length, fromIndex, toIndex); for (int i=fromIndex; ifromIndex, inclusive, to index * toIndex, exclusive. (If fromIndex==toIndex, the * range to be filled is empty.) * * @param a the array to be filled. * @param fromIndex the index of the first element (inclusive) to be * filled with the specified value. * @param toIndex the index of the last element (exclusive) to be * filled with the specified value. * @param val the value to be stored in all elements of the array. * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void fill(boolean[] a, int fromIndex, int toIndex, boolean val) { rangeCheck(a.length, fromIndex, toIndex); for (int i=fromIndex; ifromIndex, inclusive, to index * toIndex, exclusive. (If fromIndex==toIndex, the * range to be filled is empty.) * * @param a the array to be filled. * @param fromIndex the index of the first element (inclusive) to be * filled with the specified value. * @param toIndex the index of the last element (exclusive) to be * filled with the specified value. * @param val the value to be stored in all elements of the array. * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void fill(double[] a, int fromIndex, int toIndex,double val){ rangeCheck(a.length, fromIndex, toIndex); for (int i=fromIndex; ifromIndex, inclusive, to index * toIndex, exclusive. (If fromIndex==toIndex, the * range to be filled is empty.) * * @param a the array to be filled. * @param fromIndex the index of the first element (inclusive) to be * filled with the specified value. * @param toIndex the index of the last element (exclusive) to be * filled with the specified value. * @param val the value to be stored in all elements of the array. * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void fill(float[] a, int fromIndex, int toIndex, float val) { rangeCheck(a.length, fromIndex, toIndex); for (int i=fromIndex; ifromIndex, inclusive, to index * toIndex, exclusive. (If fromIndex==toIndex, the * range to be filled is empty.) * * @param a the array to be filled. * @param fromIndex the index of the first element (inclusive) to be * filled with the specified value. * @param toIndex the index of the last element (exclusive) to be * filled with the specified value. * @param val the value to be stored in all elements of the array. * @throws IllegalArgumentException if fromIndex > toIndex * @throws ArrayIndexOutOfBoundsException if fromIndex < 0 or * toIndex > a.length */ public static void fill(Object[] a, int fromIndex, int toIndex, Object val) { rangeCheck(a.length, fromIndex, toIndex); for (int i=fromIndex; inull. * Such indices will exist if and only if the specified length * is greater than that of the original array. * The resulting array is of exactly the same class as the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with nulls * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @since 1.6 */ public static T[] copyOf(T[] original, int newLength) { return (T[]) copyOf(original, newLength, original.getClass()); } /** * Copies the specified array, truncating or padding with nulls (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain null. * Such indices will exist if and only if the specified length * is greater than that of the original array. * The resulting array is of the class newType. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @param newType the class of the copy to be returned * @return a copy of the original array, truncated or padded with nulls * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @throws ArrayStoreException if an element copied from * original is not of a runtime type that can be stored in * an array of class newType. * @since 1.6 */ public static T[] copyOf(U[] original, int newLength, Class newType) { T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } /** * Copies the specified array, truncating or padding with zeros (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain (byte)0. * Such indices will exist if and only if the specified length * is greater than that of the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with zeros * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @since 1.6 */ public static byte[] copyOf(byte[] original, int newLength) { byte[] copy = new byte[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } /** * Copies the specified array, truncating or padding with zeros (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain (short)0. * Such indices will exist if and only if the specified length * is greater than that of the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with zeros * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @since 1.6 */ public static short[] copyOf(short[] original, int newLength) { short[] copy = new short[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } /** * Copies the specified array, truncating or padding with zeros (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain 0. * Such indices will exist if and only if the specified length * is greater than that of the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with zeros * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @since 1.6 */ public static int[] copyOf(int[] original, int newLength) { int[] copy = new int[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } /** * Copies the specified array, truncating or padding with zeros (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain 0L. * Such indices will exist if and only if the specified length * is greater than that of the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with zeros * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @since 1.6 */ public static long[] copyOf(long[] original, int newLength) { long[] copy = new long[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } /** * Copies the specified array, truncating or padding with null characters (if necessary) * so the copy has the specified length. For all indices that are valid * in both the original array and the copy, the two arrays will contain * identical values. For any indices that are valid in the copy but not * the original, the copy will contain '\\u000'. Such indices * will exist if and only if the specified length is greater than that of * the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with null characters * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @since 1.6 */ public static char[] copyOf(char[] original, int newLength) { char[] copy = new char[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } /** * Copies the specified array, truncating or padding with zeros (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain 0f. * Such indices will exist if and only if the specified length * is greater than that of the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with zeros * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @since 1.6 */ public static float[] copyOf(float[] original, int newLength) { float[] copy = new float[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } /** * Copies the specified array, truncating or padding with zeros (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain 0d. * Such indices will exist if and only if the specified length * is greater than that of the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with zeros * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @since 1.6 */ public static double[] copyOf(double[] original, int newLength) { double[] copy = new double[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } /** * Copies the specified array, truncating or padding with false (if necessary) * so the copy has the specified length. For all indices that are * valid in both the original array and the copy, the two arrays will * contain identical values. For any indices that are valid in the * copy but not the original, the copy will contain false. * Such indices will exist if and only if the specified length * is greater than that of the original array. * * @param original the array to be copied * @param newLength the length of the copy to be returned * @return a copy of the original array, truncated or padded with false elements * to obtain the specified length * @throws NegativeArraySizeException if newLength is negative * @throws NullPointerException if original is null * @since 1.6 */ public static boolean[] copyOf(boolean[] original, int newLength) { boolean[] copy = new boolean[newLength]; System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * null is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. *

* The resulting array is of exactly the same class as the original array. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @return a new array containing the specified range from the original array, * truncated or padded with nulls to obtain the required length * @throws ArrayIndexOutOfBoundsException if from < 0 * or from > original.length() * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @since 1.6 */ public static T[] copyOfRange(T[] original, int from, int to) { return copyOfRange(original, from, to, (Class) original.getClass()); } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * null is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. * The resulting array is of the class newType. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @param newType the class of the copy to be returned * @return a new array containing the specified range from the original array, * truncated or padded with nulls to obtain the required length * @throws ArrayIndexOutOfBoundsException if from < 0 * or from > original.length() * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @throws ArrayStoreException if an element copied from * original is not of a runtime type that can be stored in * an array of class newType. * @since 1.6 */ public static T[] copyOfRange(U[] original, int from, int to, Class newType) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * (byte)0 is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @return a new array containing the specified range from the original array, * truncated or padded with zeros to obtain the required length * @throws ArrayIndexOutOfBoundsException if from < 0 * or from > original.length() * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @since 1.6 */ public static byte[] copyOfRange(byte[] original, int from, int to) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); byte[] copy = new byte[newLength]; System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * (short)0 is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @return a new array containing the specified range from the original array, * truncated or padded with zeros to obtain the required length * @throws ArrayIndexOutOfBoundsException if from < 0 * or from > original.length() * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @since 1.6 */ public static short[] copyOfRange(short[] original, int from, int to) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); short[] copy = new short[newLength]; System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * 0 is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @return a new array containing the specified range from the original array, * truncated or padded with zeros to obtain the required length * @throws ArrayIndexOutOfBoundsException if from < 0 * or from > original.length() * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @since 1.6 */ public static int[] copyOfRange(int[] original, int from, int to) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); int[] copy = new int[newLength]; System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * 0L is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @return a new array containing the specified range from the original array, * truncated or padded with zeros to obtain the required length * @throws ArrayIndexOutOfBoundsException if from < 0 * or from > original.length() * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @since 1.6 */ public static long[] copyOfRange(long[] original, int from, int to) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); long[] copy = new long[newLength]; System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * '\\u000' is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @return a new array containing the specified range from the original array, * truncated or padded with null characters to obtain the required length * @throws ArrayIndexOutOfBoundsException if from < 0 * or from > original.length() * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @since 1.6 */ public static char[] copyOfRange(char[] original, int from, int to) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); char[] copy = new char[newLength]; System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * 0f is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @return a new array containing the specified range from the original array, * truncated or padded with zeros to obtain the required length * @throws ArrayIndexOutOfBoundsException if from < 0 * or from > original.length() * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @since 1.6 */ public static float[] copyOfRange(float[] original, int from, int to) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); float[] copy = new float[newLength]; System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * 0d is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @return a new array containing the specified range from the original array, * truncated or padded with zeros to obtain the required length * @throws ArrayIndexOutOfBoundsException if from < 0 * or from > original.length() * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @since 1.6 */ public static double[] copyOfRange(double[] original, int from, int to) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); double[] copy = new double[newLength]; System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } /** * Copies the specified range of the specified array into a new array. * The initial index of the range (from) must lie between zero * and original.length, inclusive. The value at * original[from] is placed into the initial element of the copy * (unless from == original.length or from == to). * Values from subsequent elements in the original array are placed into * subsequent elements in the copy. The final index of the range * (to), which must be greater than or equal to from, * may be greater than original.length, in which case * false is placed in all elements of the copy whose index is * greater than or equal to original.length - from. The length * of the returned array will be to - from. * * @param original the array from which a range is to be copied * @param from the initial index of the range to be copied, inclusive * @param to the final index of the range to be copied, exclusive. * (This index may lie outside the array.) * @return a new array containing the specified range from the original array, * truncated or padded with false elements to obtain the required length * @throws ArrayIndexOutOfBoundsException if from < 0 * or from > original.length() * @throws IllegalArgumentException if from > to * @throws NullPointerException if original is null * @since 1.6 */ public static boolean[] copyOfRange(boolean[] original, int from, int to) { int newLength = to - from; if (newLength < 0) throw new IllegalArgumentException(from + " > " + to); boolean[] copy = new boolean[newLength]; System.arraycopy(original, from, copy, 0, Math.min(original.length - from, newLength)); return copy; } // Misc /** * Returns a fixed-size list backed by the specified array. (Changes to * the returned list "write through" to the array.) This method acts * as bridge between array-based and collection-based APIs, in * combination with Collection.toArray. The returned list is * serializable and implements {@link RandomAccess}. * *

This method also provides a convenient way to create a fixed-size * list initialized to contain several elements: *

     *     List stooges = Arrays.asList("Larry", "Moe", "Curly");
     *

* * @param a the array by which the list will be backed. * @return a list view of the specified array. * @see Collection#toArray() */ public static List asList(T... a) { return new ArrayList(a); } /** * @serial include */ private static class ArrayList extends AbstractList implements RandomAccess, java.io.Serializable { private static final long serialVersionUID = -2764017481108945198L; private Object[] a; ArrayList(E[] array) { if (array==null) throw new NullPointerException(); a = array; } public int size() { return a.length; } public Object[] toArray() { return (Object[])a.clone(); } public E get(int index) { return (E)a[index]; } public E set(int index, E element) { Object oldValue = a[index]; a[index] = element; return (E)oldValue; } public int indexOf(Object o) { if (o==null) { for (int i=0; ilong arrays a and b * such that Arrays.equals(a, b), it is also the case that * Arrays.hashCode(a) == Arrays.hashCode(b). * *

The value returned by this method is the same value that would be * obtained by invoking the {@link List#hashCode() hashCode} * method on a {@link List} containing a sequence of {@link Long} * instances representing the elements of a in the same order. * If a is null, this method returns 0. * * @param a the array whose hash value to compute * @return a content-based hash code for a * @since 1.5 */ public static int hashCode(long a[]) { if (a == null) return 0; int result = 1; for (long element : a) { int elementHash = (int)(element ^ (element >>> 32)); result = 31 * result + elementHash; } return result; } /** * Returns a hash code based on the contents of the specified array. * For any two non-null int arrays a and b * such that Arrays.equals(a, b), it is also the case that * Arrays.hashCode(a) == Arrays.hashCode(b). * *

The value returned by this method is the same value that would be * obtained by invoking the {@link List#hashCode() hashCode} * method on a {@link List} containing a sequence of {@link Integer} * instances representing the elements of a in the same order. * If a is null, this method returns 0. * * @param a the array whose hash value to compute * @return a content-based hash code for a * @since 1.5 */ public static int hashCode(int a[]) { if (a == null) return 0; int result = 1; for (int element : a) result = 31 * result + element; return result; } /** * Returns a hash code based on the contents of the specified array. * For any two short arrays a and b * such that Arrays.equals(a, b), it is also the case that * Arrays.hashCode(a) == Arrays.hashCode(b). * *

The value returned by this method is the same value that would be * obtained by invoking the {@link List#hashCode() hashCode} * method on a {@link List} containing a sequence of {@link Short} * instances representing the elements of a in the same order. * If a is null, this method returns 0. * * @param a the array whose hash value to compute * @return a content-based hash code for a * @since 1.5 */ public static int hashCode(short a[]) { if (a == null) return 0; int result = 1; for (short element : a) result = 31 * result + element; return result; } /** * Returns a hash code based on the contents of the specified array. * For any two char arrays a and b * such that Arrays.equals(a, b), it is also the case that * Arrays.hashCode(a) == Arrays.hashCode(b). * *

The value returned by this method is the same value that would be * obtained by invoking the {@link List#hashCode() hashCode} * method on a {@link List} containing a sequence of {@link Character} * instances representing the elements of a in the same order. * If a is null, this method returns 0. * * @param a the array whose hash value to compute * @return a content-based hash code for a * @since 1.5 */ public static int hashCode(char a[]) { if (a == null) return 0; int result = 1; for (char element : a) result = 31 * result + element; return result; } /** * Returns a hash code based on the contents of the specified array. * For any two byte arrays a and b * such that Arrays.equals(a, b), it is also the case that * Arrays.hashCode(a) == Arrays.hashCode(b). * *

The value returned by this method is the same value that would be * obtained by invoking the {@link List#hashCode() hashCode} * method on a {@link List} containing a sequence of {@link Byte} * instances representing the elements of a in the same order. * If a is null, this method returns 0. * * @param a the array whose hash value to compute * @return a content-based hash code for a * @since 1.5 */ public static int hashCode(byte a[]) { if (a == null) return 0; int result = 1; for (byte element : a) result = 31 * result + element; return result; } /** * Returns a hash code based on the contents of the specified array. * For any two boolean arrays a and b * such that Arrays.equals(a, b), it is also the case that * Arrays.hashCode(a) == Arrays.hashCode(b). * *

The value returned by this method is the same value that would be * obtained by invoking the {@link List#hashCode() hashCode} * method on a {@link List} containing a sequence of {@link Boolean} * instances representing the elements of a in the same order. * If a is null, this method returns 0. * * @param a the array whose hash value to compute * @return a content-based hash code for a * @since 1.5 */ public static int hashCode(boolean a[]) { if (a == null) return 0; int result = 1; for (boolean element : a) result = 31 * result + (element ? 1231 : 1237); return result; } /** * Returns a hash code based on the contents of the specified array. * For any two float arrays a and b * such that Arrays.equals(a, b), it is also the case that * Arrays.hashCode(a) == Arrays.hashCode(b). * *

The value returned by this method is the same value that would be * obtained by invoking the {@link List#hashCode() hashCode} * method on a {@link List} containing a sequence of {@link Float} * instances representing the elements of a in the same order. * If a is null, this method returns 0. * * @param a the array whose hash value to compute * @return a content-based hash code for a * @since 1.5 */ public static int hashCode(float a[]) { if (a == null) return 0; int result = 1; for (float element : a) result = 31 * result + Float.floatToIntBits(element); return result; } /** * Returns a hash code based on the contents of the specified array. * For any two double arrays a and b * such that Arrays.equals(a, b), it is also the case that * Arrays.hashCode(a) == Arrays.hashCode(b). * *

The value returned by this method is the same value that would be * obtained by invoking the {@link List#hashCode() hashCode} * method on a {@link List} containing a sequence of {@link Double} * instances representing the elements of a in the same order. * If a is null, this method returns 0. * * @param a the array whose hash value to compute * @return a content-based hash code for a * @since 1.5 */ public static int hashCode(double a[]) { if (a == null) return 0; int result = 1; for (double element : a) { long bits = Double.doubleToLongBits(element); result = 31 * result + (int)(bits ^ (bits >>> 32)); } return result; } /** * Returns a hash code based on the contents of the specified array. If * the array contains other arrays as elements, the hash code is based on * their identities rather than their contents. It is therefore * acceptable to invoke this method on an array that contains itself as an * element, either directly or indirectly through one or more levels of * arrays. * *

For any two arrays a and b such that * Arrays.equals(a, b), it is also the case that * Arrays.hashCode(a) == Arrays.hashCode(b). * *

The value returned by this method is equal to the value that would * be returned by Arrays.asList(a).hashCode(), unless a * is null, in which case 0 is returned. * * @param a the array whose content-based hash code to compute * @return a content-based hash code for a * @see #deepHashCode(Object[]) * @since 1.5 */ public static int hashCode(Object a[]) { if (a == null) return 0; int result = 1; for (Object element : a) result = 31 * result + (element == null ? 0 : element.hashCode()); return result; } /** * Returns a hash code based on the "deep contents" of the specified * array. If the array contains other arrays as elements, the * hash code is based on their contents and so on, ad infinitum. * It is therefore unacceptable to invoke this method on an array that * contains itself as an element, either directly or indirectly through * one or more levels of arrays. The behavior of such an invocation is * undefined. * *

For any two arrays a and b such that * Arrays.deepEquals(a, b), it is also the case that * Arrays.deepHashCode(a) == Arrays.deepHashCode(b). * *

The computation of the value returned by this method is similar to * that of the value returned by {@link List#hashCode()} on a list * containing the same elements as a in the same order, with one * difference: If an element e of a is itself an array, * its hash code is computed not by calling e.hashCode(), but as * by calling the appropriate overloading of Arrays.hashCode(e) * if e is an array of a primitive type, or as by calling * Arrays.deepHashCode(e) recursively if e is an array * of a reference type. If a is null, this method * returns 0. * * @param a the array whose deep-content-based hash code to compute * @return a deep-content-based hash code for a * @see #hashCode(Object[]) * @since 1.5 */ public static int deepHashCode(Object a[]) { if (a == null) return 0; int result = 1; for (Object element : a) { int elementHash = 0; if (element instanceof Object[]) elementHash = deepHashCode((Object[]) element); else if (element instanceof byte[]) elementHash = hashCode((byte[]) element); else if (element instanceof short[]) elementHash = hashCode((short[]) element); else if (element instanceof int[]) elementHash = hashCode((int[]) element); else if (element instanceof long[]) elementHash = hashCode((long[]) element); else if (element instanceof char[]) elementHash = hashCode((char[]) element); else if (element instanceof float[]) elementHash = hashCode((float[]) element); else if (element instanceof double[]) elementHash = hashCode((double[]) element); else if (element instanceof boolean[]) elementHash = hashCode((boolean[]) element); else if (element != null) elementHash = element.hashCode(); result = 31 * result + elementHash; } return result; } /** * Returns true if the two specified arrays are deeply * equal to one another. Unlike the {@link #equals(Object[],Object[])} * method, this method is appropriate for use with nested arrays of * arbitrary depth. * *

Two array references are considered deeply equal if both * are null, or if they refer to arrays that contain the same * number of elements and all corresponding pairs of elements in the two * arrays are deeply equal. * *

Two possibly null elements e1 and e2 are * deeply equal if any of the following conditions hold: *

e1 and e2 are both arrays of object reference * types, and Arrays.deepEquals(e1, e2) would return true *
e1 and e2 are arrays of the same primitive * type, and the appropriate overloading of * Arrays.equals(e1, e2) would return true. *
e1 == e2 *
e1.equals(e2) would return true. *

* Note that this definition permits null elements at any depth. * *

If either of the specified arrays contain themselves as elements * either directly or indirectly through one or more levels of arrays, * the behavior of this method is undefined. * * @param a1 one array to be tested for equality * @param a2 the other array to be tested for equality * @return true if the two arrays are equal * @see #equals(Object[],Object[]) * @since 1.5 */ public static boolean deepEquals(Object[] a1, Object[] a2) { if (a1 == a2) return true; if (a1 == null || a2==null) return false; int length = a1.length; if (a2.length != length) return false; for (int i = 0; i < length; i++) { Object e1 = a1[i]; Object e2 = a2[i]; if (e1 == e2) continue; if (e1 == null) return false; // Figure out whether the two elements are equal boolean eq; if (e1 instanceof Object[] && e2 instanceof Object[]) eq = deepEquals ((Object[]) e1, (Object[]) e2); else if (e1 instanceof byte[] && e2 instanceof byte[]) eq = equals((byte[]) e1, (byte[]) e2); else if (e1 instanceof short[] && e2 instanceof short[]) eq = equals((short[]) e1, (short[]) e2); else if (e1 instanceof int[] && e2 instanceof int[]) eq = equals((int[]) e1, (int[]) e2); else if (e1 instanceof long[] && e2 instanceof long[]) eq = equals((long[]) e1, (long[]) e2); else if (e1 instanceof char[] && e2 instanceof char[]) eq = equals((char[]) e1, (char[]) e2); else if (e1 instanceof float[] && e2 instanceof float[]) eq = equals((float[]) e1, (float[]) e2); else if (e1 instanceof double[] && e2 instanceof double[]) eq = equals((double[]) e1, (double[]) e2); else if (e1 instanceof boolean[] && e2 instanceof boolean[]) eq = equals((boolean[]) e1, (boolean[]) e2); else eq = e1.equals(e2); if (!eq) return false; } return true; } /** * Returns a string representation of the contents of the specified array. * The string representation consists of a list of the array's elements, * enclosed in square brackets ("[]"). Adjacent elements are * separated by the characters ", " (a comma followed by a * space). Elements are converted to strings as by * String.valueOf(long). Returns "null" if a * is null. * * @param a the array whose string representation to return * @return a string representation of a * @since 1.5 */ public static String toString(long[] a) { if (a == null) return "null"; if (a.length == 0) return "[]"; StringBuilder buf = new StringBuilder(); buf.append('['); buf.append(a[0]); for (int i = 1; i < a.length; i++) { buf.append(", "); buf.append(a[i]); } buf.append("]"); return buf.toString(); } /** * Returns a string representation of the contents of the specified array. * The string representation consists of a list of the array's elements, * enclosed in square brackets ("[]"). Adjacent elements are * separated by the characters ", " (a comma followed by a * space). Elements are converted to strings as by * String.valueOf(int). Returns "null" if a is * null. * * @param a the array whose string representation to return * @return a string representation of a * @since 1.5 */ public static String toString(int[] a) { if (a == null) return "null"; if (a.length == 0) return "[]"; StringBuilder buf = new StringBuilder(); buf.append('['); buf.append(a[0]); for (int i = 1; i < a.length; i++) { buf.append(", "); buf.append(a[i]); } buf.append("]"); return buf.toString(); } /** * Returns a string representation of the contents of the specified array. * The string representation consists of a list of the array's elements, * enclosed in square brackets ("[]"). Adjacent elements are * separated by the characters ", " (a comma followed by a * space). Elements are converted to strings as by * String.valueOf(short). Returns "null" if a * is null. * * @param a the array whose string representation to return * @return a string representation of a * @since 1.5 */ public static String toString(short[] a) { if (a == null) return "null"; if (a.length == 0) return "[]"; StringBuilder buf = new StringBuilder(); buf.append('['); buf.append(a[0]); for (int i = 1; i < a.length; i++) { buf.append(", "); buf.append(a[i]); } buf.append("]"); return buf.toString(); } /** * Returns a string representation of the contents of the specified array. * The string representation consists of a list of the array's elements, * enclosed in square brackets ("[]"). Adjacent elements are * separated by the characters ", " (a comma followed by a * space). Elements are converted to strings as by * String.valueOf(char). Returns "null" if a * is null. * * @param a the array whose string representation to return * @return a string representation of a * @since 1.5 */ public static String toString(char[] a) { if (a == null) return "null"; if (a.length == 0) return "[]"; StringBuilder buf = new StringBuilder(); buf.append('['); buf.append(a[0]); for (int i = 1; i < a.length; i++) { buf.append(", "); buf.append(a[i]); } buf.append("]"); return buf.toString(); } /** * Returns a string representation of the contents of the specified array. * The string representation consists of a list of the array's elements, * enclosed in square brackets ("[]"). Adjacent elements * are separated by the characters ", " (a comma followed * by a space). Elements are converted to strings as by * String.valueOf(byte). Returns "null" if * a is null. * * @param a the array whose string representation to return * @return a string representation of a * @since 1.5 */ public static String toString(byte[] a) { if (a == null) return "null"; if (a.length == 0) return "[]"; StringBuilder buf = new StringBuilder(); buf.append('['); buf.append(a[0]); for (int i = 1; i < a.length; i++) { buf.append(", "); buf.append(a[i]); } buf.append("]"); return buf.toString(); } /** * Returns a string representation of the contents of the specified array. * The string representation consists of a list of the array's elements, * enclosed in square brackets ("[]"). Adjacent elements are * separated by the characters ", " (a comma followed by a * space). Elements are converted to strings as by * String.valueOf(boolean). Returns "null" if * a is null. * * @param a the array whose string representation to return * @return a string representation of a * @since 1.5 */ public static String toString(boolean[] a) { if (a == null) return "null"; if (a.length == 0) return "[]"; StringBuilder buf = new StringBuilder(); buf.append('['); buf.append(a[0]); for (int i = 1; i < a.length; i++) { buf.append(", "); buf.append(a[i]); } buf.append("]"); return buf.toString(); } /** * Returns a string representation of the contents of the specified array. * The string representation consists of a list of the array's elements, * enclosed in square brackets ("[]"). Adjacent elements are * separated by the characters ", " (a comma followed by a * space). Elements are converted to strings as by * String.valueOf(float). Returns "null" if a * is null. * * @param a the array whose string representation to return * @return a string representation of a * @since 1.5 */ public static String toString(float[] a) { if (a == null) return "null"; if (a.length == 0) return "[]"; StringBuilder buf = new StringBuilder(); buf.append('['); buf.append(a[0]); for (int i = 1; i < a.length; i++) { buf.append(", "); buf.append(a[i]); } buf.append("]"); return buf.toString(); } /** * Returns a string representation of the contents of the specified array. * The string representation consists of a list of the array's elements, * enclosed in square brackets ("[]"). Adjacent elements are * separated by the characters ", " (a comma followed by a * space). Elements are converted to strings as by * String.valueOf(double). Returns "null" if a * is null. * * @param a the array whose string representation to return * @return a string representation of a * @since 1.5 */ public static String toString(double[] a) { if (a == null) return "null"; if (a.length == 0) return "[]"; StringBuilder buf = new StringBuilder(); buf.append('['); buf.append(a[0]); for (int i = 1; i < a.length; i++) { buf.append(", "); buf.append(a[i]); } buf.append("]"); return buf.toString(); } /** * Returns a string representation of the contents of the specified array. * If the array contains other arrays as elements, they are converted to * strings by the {@link Object#toString} method inherited from * Object, which describes their identities rather than * their contents. * *

The value returned by this method is equal to the value that would * be returned by Arrays.asList(a).toString(), unless a * is null, in which case "null" is returned. * * @param a the array whose string representation to return * @return a string representation of a * @see #deepToString(Object[]) * @since 1.5 */ public static String toString(Object[] a) { if (a == null) return "null"; if (a.length == 0) return "[]"; StringBuilder buf = new StringBuilder(); for (int i = 0; i < a.length; i++) { if (i == 0) buf.append('['); else buf.append(", "); buf.append(String.valueOf(a[i])); } buf.append("]"); return buf.toString(); } /** * Returns a string representation of the "deep contents" of the specified * array. If the array contains other arrays as elements, the string * representation contains their contents and so on. This method is * designed for converting multidimensional arrays to strings. * *

The string representation consists of a list of the array's * elements, enclosed in square brackets ("[]"). Adjacent * elements are separated by the characters ", " (a comma * followed by a space). Elements are converted to strings as by * String.valueOf(Object), unless they are themselves * arrays. * *

If an element e is an array of a primitive type, it is * converted to a string as by invoking the appropriate overloading of * Arrays.toString(e). If an element e is an array of a * reference type, it is converted to a string as by invoking * this method recursively. * *

To avoid infinite recursion, if the specified array contains itself * as an element, or contains an indirect reference to itself through one * or more levels of arrays, the self-reference is converted to the string * "[...]". For example, an array containing only a reference * to itself would be rendered as "[[...]]". * *

This method returns "null" if the specified array * is null. * * @param a the array whose string representation to return * @return a string representation of a * @see #toString(Object[]) * @since 1.5 */ public static String deepToString(Object[] a) { if (a == null) return "null"; int bufLen = 20 * a.length; if (a.length != 0 && bufLen <= 0) bufLen = Integer.MAX_VALUE; StringBuilder buf = new StringBuilder(bufLen); deepToString(a, buf, new HashSet()); return buf.toString(); } private static void deepToString(Object[] a, StringBuilder buf, Set dejaVu) { if (a == null) { buf.append("null"); return; } dejaVu.add(a); buf.append('['); for (int i = 0; i < a.length; i++) { if (i != 0) buf.append(", "); Object element = a[i]; if (element == null) { buf.append("null"); } else { Class eClass = element.getClass(); if (eClass.isArray()) { if (eClass == byte[].class) buf.append(toString((byte[]) element)); else if (eClass == short[].class) buf.append(toString((short[]) element)); else if (eClass == int[].class) buf.append(toString((int[]) element)); else if (eClass == long[].class) buf.append(toString((long[]) element)); else if (eClass == char[].class) buf.append(toString((char[]) element)); else if (eClass == float[].class) buf.append(toString((float[]) element)); else if (eClass == double[].class) buf.append(toString((double[]) element)); else if (eClass == boolean[].class) buf.append(toString((boolean[]) element)); else { // element is an array of object references if (dejaVu.contains(element)) buf.append("[...]"); else deepToString((Object[])element, buf, dejaVu); } } else { // element is non-null and not an array buf.append(element.toString()); } } } buf.append("]"); dejaVu.remove(a); } }