java/util/Arrays.java

110      * Checks that {@code fromIndex} and {@code toIndex} are in
113     static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
114         if (fromIndex > toIndex) {
116                     "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
118         if (fromIndex < 0) {
119             throw new ArrayIndexOutOfBoundsException(fromIndex);
151      * to be sorted extends from the index {@code fromIndex}, inclusive, to
152      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
162      * @param fromIndex the index of the first element, inclusive, to be sorted
165      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
167      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
169     public static void sort(int[] a, int fromIndex, int toIndex) {
170         rangeCheck(a.length, fromIndex, toIndex);
171         DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
191      * to be sorted extends from the index {@code fromIndex}, inclusive, to
192      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
202      * @param fromIndex the index of the first element, inclusive, to be sorted
205      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
207      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
209     public static void sort(long[] a, int fromIndex, int toIndex) {
210         rangeCheck(a.length, fromIndex, toIndex);
211         DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
231      * to be sorted extends from the index {@code fromIndex}, inclusive, to
232      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
242      * @param fromIndex the index of the first element, inclusive, to be sorted
245      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
247      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
249     public static void sort(short[] a, int fromIndex, int toIndex) {
250         rangeCheck(a.length, fromIndex, toIndex);
251         DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
271      * to be sorted extends from the index {@code fromIndex}, inclusive, to
272      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
282      * @param fromIndex the index of the first element, inclusive, to be sorted
285      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
287      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
289     public static void sort(char[] a, int fromIndex, int toIndex) {
290         rangeCheck(a.length, fromIndex, toIndex);
291         DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
311      * to be sorted extends from the index {@code fromIndex}, inclusive, to
312      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
322      * @param fromIndex the index of the first element, inclusive, to be sorted
325      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
327      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
329     public static void sort(byte[] a, int fromIndex, int toIndex) {
330         rangeCheck(a.length, fromIndex, toIndex);
331         DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
359      * to be sorted extends from the index {@code fromIndex}, inclusive, to
360      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
378      * @param fromIndex the index of the first element, inclusive, to be sorted
381      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
383      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
385     public static void sort(float[] a, int fromIndex, int toIndex) {
386         rangeCheck(a.length, fromIndex, toIndex);
387         DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
415      * to be sorted extends from the index {@code fromIndex}, inclusive, to
416      * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
434      * @param fromIndex the index of the first element, inclusive, to be sorted
437      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
439      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
441     public static void sort(double[] a, int fromIndex, int toIndex) {
442         rangeCheck(a.length, fromIndex, toIndex);
443         DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
478      * The range to be sorted extends from the index {@code fromIndex},
480      * {@code fromIndex == toIndex}, the range to be sorted is empty.
494      * @param fromIndex the index of the first element, inclusive, to be sorted
497      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
499      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
503     public static void parallelSort(byte[] a, int fromIndex, int toIndex) {
504         rangeCheck(a.length, fromIndex, toIndex);
505         int n = toIndex - fromIndex, p, g;
508             DualPivotQuicksort.sort(a, fromIndex, toIndex - 1);
511                 (null, a, new byte[n], fromIndex, n, 0,
548      * The range to be sorted extends from the index {@code fromIndex},
550      * {@code fromIndex == toIndex}, the range to be sorted is empty.
564      * @param fromIndex the index of the first element, inclusive, to be sorted
567      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
569      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
573     public static void parallelSort(char[] a, int fromIndex, int toIndex) {
574         rangeCheck(a.length, fromIndex, toIndex);
575         int n = toIndex - fromIndex, p, g;
578             DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
581                 (null, a, new char[n], fromIndex, n, 0,
618      * The range to be sorted extends from the index {@code fromIndex},
620      * {@code fromIndex == toIndex}, the range to be sorted is empty.
634      * @param fromIndex the index of the first element, inclusive, to be sorted
637      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
639      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
643     public static void parallelSort(short[] a, int fromIndex, int toIndex) {
644         rangeCheck(a.length, fromIndex, toIndex);
645         int n = toIndex - fromIndex, p, g;
648             DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
651                 (null, a, new short[n], fromIndex, n, 0,
688      * The range to be sorted extends from the index {@code fromIndex},
690      * {@code fromIndex == toIndex}, the range to be sorted is empty.
704      * @param fromIndex the index of the first element, inclusive, to be sorted
707      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
709      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
713     public static void parallelSort(int[] a, int fromIndex, int toIndex) {
714         rangeCheck(a.length, fromIndex, toIndex);
715         int n = toIndex - fromIndex, p, g;
718             DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
721                 (null, a, new int[n], fromIndex, n, 0,
758      * The range to be sorted extends from the index {@code fromIndex},
760      * {@code fromIndex == toIndex}, the range to be sorted is empty.
774      * @param fromIndex the index of the first element, inclusive, to be sorted
777      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
779      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
783     public static void parallelSort(long[] a, int fromIndex, int toIndex) {
784         rangeCheck(a.length, fromIndex, toIndex);
785         int n = toIndex - fromIndex, p, g;
788             DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
791                 (null, a, new long[n], fromIndex, n, 0,
836      * The range to be sorted extends from the index {@code fromIndex},
838      * {@code fromIndex == toIndex}, the range to be sorted is empty.
860      * @param fromIndex the index of the first element, inclusive, to be sorted
863      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
865      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
869     public static void parallelSort(float[] a, int fromIndex, int toIndex) {
870         rangeCheck(a.length, fromIndex, toIndex);
871         int n = toIndex - fromIndex, p, g;
874             DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
877                 (null, a, new float[n], fromIndex, n, 0,
922      * The range to be sorted extends from the index {@code fromIndex},
924      * {@code fromIndex == toIndex}, the range to be sorted is empty.
946      * @param fromIndex the index of the first element, inclusive, to be sorted
949      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
951      *     if {@code fromIndex < 0} or {@code toIndex > a.length}
955     public static void parallelSort(double[] a, int fromIndex, int toIndex) {
956         rangeCheck(a.length, fromIndex, toIndex);
957         int n = toIndex - fromIndex, p, g;
960             DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
963                 (null, a, new double[n], fromIndex, n, 0,
1021      * {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive.
1022      * (If {@code fromIndex==toIndex}, the range to be sorted is empty.)  All
1045      * @param fromIndex the index of the first element (inclusive) to be
1048      * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
1051      * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
1061     void parallelSort(T[] a, int fromIndex, int toIndex) {
1062         rangeCheck(a.length, fromIndex, toIndex);
1063         int n = toIndex - fromIndex, p, g;
1066             TimSort.sort(a, fromIndex, toIndex, NaturalOrder.INSTANCE, null, 0, 0);
1071                  fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
1127      * sorted extends from index {@code fromIndex}, inclusive, to index
1128      * {@code toIndex}, exclusive.  (If {@code fromIndex==toIndex}, the
1150      * @param fromIndex the index of the first element (inclusive) to be
1156      * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
1159      * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
1168     public static <T> void parallelSort(T[] a, int fromIndex, int toIndex,
1170         rangeCheck(a.length, fromIndex, toIndex);
1173         int n = toIndex - fromIndex, p, g;
1176             TimSort.sort(a, fromIndex, toIndex, cmp, null, 0, 0);
1181                  fromIndex, n, 0, ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
1262      * {@code fromIndex}, inclusive, to index {@code toIndex}, exclusive.
1263      * (If {@code fromIndex==toIndex}, the range to be sorted is empty.)  All
1297      * @param fromIndex the index of the first element (inclusive) to be
1300      * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
1303      * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
1309     public static void sort(Object[] a, int fromIndex, int toIndex) {
1310         rangeCheck(a.length, fromIndex, toIndex);
1312             legacyMergeSort(a, fromIndex, toIndex);
1314             ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
1319                                         int fromIndex, int toIndex) {
1320         Object[] aux = copyOfRange(a, fromIndex, toIndex);
1321         mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
1456      * sorted extends from index {@code fromIndex}, inclusive, to index
1457      * {@code toIndex}, exclusive.  (If {@code fromIndex==toIndex}, the
1491      * @param fromIndex the index of the first element (inclusive) to be
1499      * @throws IllegalArgumentException if {@code fromIndex > toIndex} or
1502      * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
1505     public static <T> void sort(T[] a, int fromIndex, int toIndex,
1508             sort(a, fromIndex, toIndex);
1510             rangeCheck(a.length, fromIndex, toIndex);
1512                 legacyMergeSort(a, fromIndex, toIndex, c);
1514                 TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
1519     private static <T> void legacyMergeSort(T[] a, int fromIndex, int toIndex,
1521         T[] aux = copyOfRange(a, fromIndex, toIndex);
1523             mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
1525             mergeSort(aux, a, fromIndex, toIndex, -fromIndex, c);
1606      * @param fromIndex the index of the first element, inclusive
1610      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1612      *     if {@code fromIndex < 0} or {@code toIndex > array.length}
1616     public static <T> void parallelPrefix(T[] array, int fromIndex,
1619         rangeCheck(array.length, fromIndex, toIndex);
1620         if (fromIndex < toIndex)
1622                     (null, op, array, fromIndex, toIndex).invoke();
1651      * @param fromIndex the index of the first element, inclusive
1655      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1657      *     if {@code fromIndex < 0} or {@code toIndex > array.length}
1661     public static void parallelPrefix(long[] array, int fromIndex,
1664         rangeCheck(array.length, fromIndex, toIndex);
1665         if (fromIndex < toIndex)
1667                     (null, op, array, fromIndex, toIndex).invoke();
1699      * @param fromIndex the index of the first element, inclusive
1703      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1705      *     if {@code fromIndex < 0} or {@code toIndex > array.length}
1709     public static void parallelPrefix(double[] array, int fromIndex,
1712         rangeCheck(array.length, fromIndex, toIndex);
1713         if (fromIndex < toIndex)
1715                     (null, op, array, fromIndex, toIndex).invoke();
1744      * @param fromIndex the index of the first element, inclusive
1748      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
1750      *     if {@code fromIndex < 0} or {@code toIndex > array.length}
1754     public static void parallelPrefix(int[] array, int fromIndex,
1757         rangeCheck(array.length, fromIndex, toIndex);
1758         if (fromIndex < toIndex)
1760                     (null, op, array, fromIndex, toIndex).invoke();
1800      * @param fromIndex the index of the first element (inclusive) to be
1815      *         if {@code fromIndex > toIndex}
1817      *         if {@code fromIndex < 0 or toIndex > a.length}
1820     public static int binarySearch(long[] a, int fromIndex, int toIndex,
1822         rangeCheck(a.length, fromIndex, toIndex);
1823         return binarySearch0(a, fromIndex, toIndex, key);
1827     private static int binarySearch0(long[] a, int fromIndex, int toIndex,
1829         int low = fromIndex;
1881      * @param fromIndex the index of the first element (inclusive) to be
1896      *         if {@code fromIndex > toIndex}
1898      *         if {@code fromIndex < 0 or toIndex > a.length}
1901     public static int binarySearch(int[] a, int fromIndex, int toIndex,
1903         rangeCheck(a.length, fromIndex, toIndex);
1904         return binarySearch0(a, fromIndex, toIndex, key);
1908     private static int binarySearch0(int[] a, int fromIndex, int toIndex,
1910         int low = fromIndex;
1962      * @param fromIndex the index of the first element (inclusive) to be
1977      *         if {@code fromIndex > toIndex}
1979      *         if {@code fromIndex < 0 or toIndex > a.length}
1982     public static int binarySearch(short[] a, int fromIndex, int toIndex,
1984         rangeCheck(a.length, fromIndex, toIndex);
1985         return binarySearch0(a, fromIndex, toIndex, key);
1989     private static int binarySearch0(short[] a, int fromIndex, int toIndex,
1991         int low = fromIndex;
2043      * @param fromIndex the index of the first element (inclusive) to be
2058      *         if {@code fromIndex > toIndex}
2060      *         if {@code fromIndex < 0 or toIndex > a.length}
2063     public static int binarySearch(char[] a, int fromIndex, int toIndex,
2065         rangeCheck(a.length, fromIndex, toIndex);
2066         return binarySearch0(a, fromIndex, toIndex, key);
2070     private static int binarySearch0(char[] a, int fromIndex, int toIndex,
2072         int low = fromIndex;
2124      * @param fromIndex the index of the first element (inclusive) to be
2139      *         if {@code fromIndex > toIndex}
2141      *         if {@code fromIndex < 0 or toIndex > a.length}
2144     public static int binarySearch(byte[] a, int fromIndex, int toIndex,
2146         rangeCheck(a.length, fromIndex, toIndex);
2147         return binarySearch0(a, fromIndex, toIndex, key);
2151     private static int binarySearch0(byte[] a, int fromIndex, int toIndex,
2153         int low = fromIndex;
2207      * @param fromIndex the index of the first element (inclusive) to be
2222      *         if {@code fromIndex > toIndex}
2224      *         if {@code fromIndex < 0 or toIndex > a.length}
2227     public static int binarySearch(double[] a, int fromIndex, int toIndex,
2229         rangeCheck(a.length, fromIndex, toIndex);
2230         return binarySearch0(a, fromIndex, toIndex, key);
2234     private static int binarySearch0(double[] a, int fromIndex, int toIndex,
2236         int low = fromIndex;
2298      * @param fromIndex the index of the first element (inclusive) to be
2313      *         if {@code fromIndex > toIndex}
2315      *         if {@code fromIndex < 0 or toIndex > a.length}
2318     public static int binarySearch(float[] a, int fromIndex, int toIndex,
2320         rangeCheck(a.length, fromIndex, toIndex);
2321         return binarySearch0(a, fromIndex, toIndex, key);
2325     private static int binarySearch0(float[] a, int fromIndex, int toIndex,
2327         int low = fromIndex;
2402      * @param fromIndex the index of the first element (inclusive) to be
2419      *         if {@code fromIndex > toIndex}
2421      *         if {@code fromIndex < 0 or toIndex > a.length}
2424     public static int binarySearch(Object[] a, int fromIndex, int toIndex,
2426         rangeCheck(a.length, fromIndex, toIndex);
2427         return binarySearch0(a, fromIndex, toIndex, key);
2431     private static int binarySearch0(Object[] a, int fromIndex, int toIndex,
2433         int low = fromIndex;
2502      * @param fromIndex the index of the first element (inclusive) to be
2524      *         if {@code fromIndex > toIndex}
2526      *         if {@code fromIndex < 0 or toIndex > a.length}
2529     public static <T> int binarySearch(T[] a, int fromIndex, int toIndex,
2531         rangeCheck(a.length, fromIndex, toIndex);
2532         return binarySearch0(a, fromIndex, toIndex, key, c);
2536     private static <T> int binarySearch0(T[] a, int fromIndex, int toIndex,
2539             return binarySearch0(a, fromIndex, toIndex, key);
2541         int low = fromIndex;
3360      * extends from index {@code fromIndex}, inclusive, to index
3361      * {@code toIndex}, exclusive.  (If {@code fromIndex==toIndex}, the
3365      * @param fromIndex the index of the first element (inclusive) to be
3370      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
3371      * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
3374     public static void fill(long[] a, int fromIndex, int toIndex, long val) {
3375         rangeCheck(a.length, fromIndex, toIndex);
3376         for (int i = fromIndex; i < toIndex; i++)
3395      * extends from index {@code fromIndex}, inclusive, to index
3396      * {@code toIndex}, exclusive.  (If {@code fromIndex==toIndex}, the
3400      * @param fromIndex the index of the first element (inclusive) to be
3405      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
3406      * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
3409     public static void fill(int[] a, int fromIndex, int toIndex, int val) {
3410         rangeCheck(a.length, fromIndex, toIndex);
3411         for (int i = fromIndex; i < toIndex; i++)
3430      * extends from index {@code fromIndex}, inclusive, to index
3431      * {@code toIndex}, exclusive.  (If {@code fromIndex==toIndex}, the
3435      * @param fromIndex the index of the first element (inclusive) to be
3440      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
3441      * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
3444     public static void fill(short[] a, int fromIndex, int toIndex, short val) {
3445         rangeCheck(a.length, fromIndex, toIndex);
3446         for (int i = fromIndex; i < toIndex; i++)
3465      * extends from index {@code fromIndex}, inclusive, to index
3466      * {@code toIndex}, exclusive.  (If {@code fromIndex==toIndex}, the
3470      * @param fromIndex the index of the first element (inclusive) to be
3475      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
3476      * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
3479     public static void fill(char[] a, int fromIndex, int toIndex, char val) {
3480         rangeCheck(a.length, fromIndex, toIndex);
3481         for (int i = fromIndex; i < toIndex; i++)
3500      * extends from index {@code fromIndex}, inclusive, to index
3501      * {@code toIndex}, exclusive.  (If {@code fromIndex==toIndex}, the
3505      * @param fromIndex the index of the first element (inclusive) to be
3510      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
3511      * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
3514     public static void fill(byte[] a, int fromIndex, int toIndex, byte val) {
3515         rangeCheck(a.length, fromIndex, toIndex);
3516         for (int i = fromIndex; i < toIndex; i++)
3535      * extends from index {@code fromIndex}, inclusive, to index
3536      * {@code toIndex}, exclusive.  (If {@code fromIndex==toIndex}, the
3540      * @param fromIndex the index of the first element (inclusive) to be
3545      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
3546      * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
3549     public static void fill(boolean[] a, int fromIndex, int toIndex,
3551         rangeCheck(a.length, fromIndex, toIndex);
3552         for (int i = fromIndex; i < toIndex; i++)
3571      * extends from index {@code fromIndex}, inclusive, to index
3572      * {@code toIndex}, exclusive.  (If {@code fromIndex==toIndex}, the
3576      * @param fromIndex the index of the first element (inclusive) to be
3581      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
3582      * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
3585     public static void fill(double[] a, int fromIndex, int toIndex,double val){
3586         rangeCheck(a.length, fromIndex, toIndex);
3587         for (int i = fromIndex; i < toIndex; i++)
3606      * extends from index {@code fromIndex}, inclusive, to index
3607      * {@code toIndex}, exclusive.  (If {@code fromIndex==toIndex}, the
3611      * @param fromIndex the index of the first element (inclusive) to be
3616      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
3617      * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
3620     public static void fill(float[] a, int fromIndex, int toIndex, float val) {
3621         rangeCheck(a.length, fromIndex, toIndex);
3622         for (int i = fromIndex; i < toIndex; i++)
3643      * extends from index {@code fromIndex}, inclusive, to index
3644      * {@code toIndex}, exclusive.  (If {@code fromIndex==toIndex}, the
3648      * @param fromIndex the index of the first element (inclusive) to be
3653      * @throws IllegalArgumentException if {@code fromIndex > toIndex}
3654      * @throws ArrayIndexOutOfBoundsException if {@code fromIndex < 0} or
3659     public static void fill(Object[] a, int fromIndex, int toIndex, Object val) {
3660         rangeCheck(a.length, fromIndex, toIndex);
3661         for (int i = fromIndex; i < toIndex; i++)