Replaced primitive sorts with Iaroslavski, Bentley, and Bloch's Dual Pivot Quicksort.
The originals were based on Bentley and McIlroy's "Engineering a Sort Function."
The original floating point sorts suffered from poor performance due to the use
of a naive comparison function. In round numbers, the new version is 1.5x as fast
as the old one on integers and twice as fast on floating point numbers (on the
latest Android build running on Sholes). On some data sets (e.g., nearly sorted data,
the new version is substantially faster.
Now, with added performance tweaks from Jesse and Bob!! With these tweaks, the sort
is 70% faster than the original sort on integers and over twice as fast on doubles.
None of the optimizations are Dalvik-specific, and we may be able to make it even
faster by adding Dalvik-specific optimizations.
Also added beefier tests.
diff --git a/libcore/luni/src/main/java/java/util/Arrays.java b/libcore/luni/src/main/java/java/util/Arrays.java
index b6a4ec5..a864f78 100644
--- a/libcore/luni/src/main/java/java/util/Arrays.java
+++ b/libcore/luni/src/main/java/java/util/Arrays.java
@@ -28,6 +28,9 @@
* @since 1.2
*/
public class Arrays {
+ // BEGIN android-changed
+ // Replaced Bentely-McIlroy-based sort w/ DualPivotQuicksort
+ // BEGIN android-changed
// BEGIN android-removed
/* Specifies when to switch to insertion sort */
@@ -1602,7 +1605,7 @@
* the {@code byte} array to be sorted.
*/
public static void sort(byte[] array) {
- sort(0, array.length, array);
+ DualPivotQuicksort.sort(array);
}
/**
@@ -1620,11 +1623,7 @@
* if {@code start < 0} or {@code end > array.length}.
*/
public static void sort(byte[] array, int start, int end) {
- if (array == null) {
- throw new NullPointerException();
- }
- checkBounds(array.length, start, end);
- sort(start, end, array);
+ DualPivotQuicksort.sort(array, start, end);
}
private static void checkBounds(int arrLength, int start, int end) {
@@ -1643,84 +1642,6 @@
}
}
- private static void sort(int start, int end, byte[] array) {
- byte temp;
- int length = end - start;
- if (length < 7) {
- for (int i = start + 1; i < end; i++) {
- for (int j = i; j > start && array[j - 1] > array[j]; j--) {
- temp = array[j];
- array[j] = array[j - 1];
- array[j - 1] = temp;
- }
- }
- return;
- }
- int middle = (start + end) / 2;
- if (length > 7) {
- int bottom = start;
- int top = end - 1;
- if (length > 40) {
- length /= 8;
- bottom = med3(array, bottom, bottom + length, bottom
- + (2 * length));
- middle = med3(array, middle - length, middle, middle + length);
- top = med3(array, top - (2 * length), top - length, top);
- }
- middle = med3(array, bottom, middle, top);
- }
- byte partionValue = array[middle];
- int a, b, c, d;
- a = b = start;
- c = d = end - 1;
- while (true) {
- while (b <= c && array[b] <= partionValue) {
- if (array[b] == partionValue) {
- temp = array[a];
- array[a++] = array[b];
- array[b] = temp;
- }
- b++;
- }
- while (c >= b && array[c] >= partionValue) {
- if (array[c] == partionValue) {
- temp = array[c];
- array[c] = array[d];
- array[d--] = temp;
- }
- c--;
- }
- if (b > c) {
- break;
- }
- temp = array[b];
- array[b++] = array[c];
- array[c--] = temp;
- }
- length = a - start < b - a ? a - start : b - a;
- int l = start;
- int h = b - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- length = d - c < end - 1 - d ? d - c : end - 1 - d;
- l = b;
- h = end - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- if ((length = b - a) > 0) {
- sort(start, start + length, array);
- }
- if ((length = d - c) > 0) {
- sort(end - length, end, array);
- }
- }
-
/**
* Sorts the specified array in ascending numerical order.
*
@@ -1728,7 +1649,7 @@
* the {@code char} array to be sorted.
*/
public static void sort(char[] array) {
- sort(0, array.length, array);
+ DualPivotQuicksort.sort(array);
}
/**
@@ -1746,89 +1667,7 @@
* if {@code start < 0} or {@code end > array.length}.
*/
public static void sort(char[] array, int start, int end) {
- if (array == null) {
- throw new NullPointerException();
- }
- checkBounds(array.length, start, end);
- sort(start, end, array);
- }
-
- private static void sort(int start, int end, char[] array) {
- char temp;
- int length = end - start;
- if (length < 7) {
- for (int i = start + 1; i < end; i++) {
- for (int j = i; j > start && array[j - 1] > array[j]; j--) {
- temp = array[j];
- array[j] = array[j - 1];
- array[j - 1] = temp;
- }
- }
- return;
- }
- int middle = (start + end) / 2;
- if (length > 7) {
- int bottom = start;
- int top = end - 1;
- if (length > 40) {
- length /= 8;
- bottom = med3(array, bottom, bottom + length, bottom
- + (2 * length));
- middle = med3(array, middle - length, middle, middle + length);
- top = med3(array, top - (2 * length), top - length, top);
- }
- middle = med3(array, bottom, middle, top);
- }
- char partionValue = array[middle];
- int a, b, c, d;
- a = b = start;
- c = d = end - 1;
- while (true) {
- while (b <= c && array[b] <= partionValue) {
- if (array[b] == partionValue) {
- temp = array[a];
- array[a++] = array[b];
- array[b] = temp;
- }
- b++;
- }
- while (c >= b && array[c] >= partionValue) {
- if (array[c] == partionValue) {
- temp = array[c];
- array[c] = array[d];
- array[d--] = temp;
- }
- c--;
- }
- if (b > c) {
- break;
- }
- temp = array[b];
- array[b++] = array[c];
- array[c--] = temp;
- }
- length = a - start < b - a ? a - start : b - a;
- int l = start;
- int h = b - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- length = d - c < end - 1 - d ? d - c : end - 1 - d;
- l = b;
- h = end - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- if ((length = b - a) > 0) {
- sort(start, start + length, array);
- }
- if ((length = d - c) > 0) {
- sort(end - length, end, array);
- }
+ DualPivotQuicksort.sort(array, start, end);
}
/**
@@ -1839,7 +1678,7 @@
* @see #sort(double[], int, int)
*/
public static void sort(double[] array) {
- sort(0, array.length, array);
+ DualPivotQuicksort.sort(array);
}
/**
@@ -1859,89 +1698,7 @@
* @see Double#compareTo(Double)
*/
public static void sort(double[] array, int start, int end) {
- if (array == null) {
- throw new NullPointerException();
- }
- checkBounds(array.length, start, end);
- sort(start, end, array);
- }
-
- private static void sort(int start, int end, double[] array) {
- double temp;
- int length = end - start;
- if (length < 7) {
- for (int i = start + 1; i < end; i++) {
- for (int j = i; j > start && lessThan(array[j], array[j - 1]); j--) {
- temp = array[j];
- array[j] = array[j - 1];
- array[j - 1] = temp;
- }
- }
- return;
- }
- int middle = (start + end) / 2;
- if (length > 7) {
- int bottom = start;
- int top = end - 1;
- if (length > 40) {
- length /= 8;
- bottom = med3(array, bottom, bottom + length, bottom
- + (2 * length));
- middle = med3(array, middle - length, middle, middle + length);
- top = med3(array, top - (2 * length), top - length, top);
- }
- middle = med3(array, bottom, middle, top);
- }
- double partionValue = array[middle];
- int a, b, c, d;
- a = b = start;
- c = d = end - 1;
- while (true) {
- while (b <= c && !lessThan(partionValue, array[b])) {
- if (array[b] == partionValue) {
- temp = array[a];
- array[a++] = array[b];
- array[b] = temp;
- }
- b++;
- }
- while (c >= b && !lessThan(array[c], partionValue)) {
- if (array[c] == partionValue) {
- temp = array[c];
- array[c] = array[d];
- array[d--] = temp;
- }
- c--;
- }
- if (b > c) {
- break;
- }
- temp = array[b];
- array[b++] = array[c];
- array[c--] = temp;
- }
- length = a - start < b - a ? a - start : b - a;
- int l = start;
- int h = b - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- length = d - c < end - 1 - d ? d - c : end - 1 - d;
- l = b;
- h = end - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- if ((length = b - a) > 0) {
- sort(start, start + length, array);
- }
- if ((length = d - c) > 0) {
- sort(end - length, end, array);
- }
+ DualPivotQuicksort.sort(array, start, end);
}
/**
@@ -1952,7 +1709,7 @@
* @see #sort(float[], int, int)
*/
public static void sort(float[] array) {
- sort(0, array.length, array);
+ DualPivotQuicksort.sort(array);
}
/**
@@ -1972,89 +1729,7 @@
* @see Float#compareTo(Float)
*/
public static void sort(float[] array, int start, int end) {
- if (array == null) {
- throw new NullPointerException();
- }
- checkBounds(array.length, start, end);
- sort(start, end, array);
- }
-
- private static void sort(int start, int end, float[] array) {
- float temp;
- int length = end - start;
- if (length < 7) {
- for (int i = start + 1; i < end; i++) {
- for (int j = i; j > start && lessThan(array[j], array[j - 1]); j--) {
- temp = array[j];
- array[j] = array[j - 1];
- array[j - 1] = temp;
- }
- }
- return;
- }
- int middle = (start + end) / 2;
- if (length > 7) {
- int bottom = start;
- int top = end - 1;
- if (length > 40) {
- length /= 8;
- bottom = med3(array, bottom, bottom + length, bottom
- + (2 * length));
- middle = med3(array, middle - length, middle, middle + length);
- top = med3(array, top - (2 * length), top - length, top);
- }
- middle = med3(array, bottom, middle, top);
- }
- float partionValue = array[middle];
- int a, b, c, d;
- a = b = start;
- c = d = end - 1;
- while (true) {
- while (b <= c && !lessThan(partionValue, array[b])) {
- if (array[b] == partionValue) {
- temp = array[a];
- array[a++] = array[b];
- array[b] = temp;
- }
- b++;
- }
- while (c >= b && !lessThan(array[c], partionValue)) {
- if (array[c] == partionValue) {
- temp = array[c];
- array[c] = array[d];
- array[d--] = temp;
- }
- c--;
- }
- if (b > c) {
- break;
- }
- temp = array[b];
- array[b++] = array[c];
- array[c--] = temp;
- }
- length = a - start < b - a ? a - start : b - a;
- int l = start;
- int h = b - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- length = d - c < end - 1 - d ? d - c : end - 1 - d;
- l = b;
- h = end - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- if ((length = b - a) > 0) {
- sort(start, start + length, array);
- }
- if ((length = d - c) > 0) {
- sort(end - length, end, array);
- }
+ DualPivotQuicksort.sort(array, start, end);
}
/**
@@ -2064,7 +1739,7 @@
* the {@code int} array to be sorted.
*/
public static void sort(int[] array) {
- sort(0, array.length, array);
+ DualPivotQuicksort.sort(array);
}
/**
@@ -2082,89 +1757,7 @@
* if {@code start < 0} or {@code end > array.length}.
*/
public static void sort(int[] array, int start, int end) {
- if (array == null) {
- throw new NullPointerException();
- }
- checkBounds(array.length, start, end);
- sort(start, end, array);
- }
-
- private static void sort(int start, int end, int[] array) {
- int temp;
- int length = end - start;
- if (length < 7) {
- for (int i = start + 1; i < end; i++) {
- for (int j = i; j > start && array[j - 1] > array[j]; j--) {
- temp = array[j];
- array[j] = array[j - 1];
- array[j - 1] = temp;
- }
- }
- return;
- }
- int middle = (start + end) / 2;
- if (length > 7) {
- int bottom = start;
- int top = end - 1;
- if (length > 40) {
- length /= 8;
- bottom = med3(array, bottom, bottom + length, bottom
- + (2 * length));
- middle = med3(array, middle - length, middle, middle + length);
- top = med3(array, top - (2 * length), top - length, top);
- }
- middle = med3(array, bottom, middle, top);
- }
- int partionValue = array[middle];
- int a, b, c, d;
- a = b = start;
- c = d = end - 1;
- while (true) {
- while (b <= c && array[b] <= partionValue) {
- if (array[b] == partionValue) {
- temp = array[a];
- array[a++] = array[b];
- array[b] = temp;
- }
- b++;
- }
- while (c >= b && array[c] >= partionValue) {
- if (array[c] == partionValue) {
- temp = array[c];
- array[c] = array[d];
- array[d--] = temp;
- }
- c--;
- }
- if (b > c) {
- break;
- }
- temp = array[b];
- array[b++] = array[c];
- array[c--] = temp;
- }
- length = a - start < b - a ? a - start : b - a;
- int l = start;
- int h = b - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- length = d - c < end - 1 - d ? d - c : end - 1 - d;
- l = b;
- h = end - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- if ((length = b - a) > 0) {
- sort(start, start + length, array);
- }
- if ((length = d - c) > 0) {
- sort(end - length, end, array);
- }
+ DualPivotQuicksort.sort(array, start, end);
}
/**
@@ -2174,7 +1767,7 @@
* the {@code long} array to be sorted.
*/
public static void sort(long[] array) {
- sort(0, array.length, array);
+ DualPivotQuicksort.sort(array);
}
/**
@@ -2192,89 +1785,35 @@
* if {@code start < 0} or {@code end > array.length}.
*/
public static void sort(long[] array, int start, int end) {
- if (array == null) {
- throw new NullPointerException();
- }
- checkBounds(array.length, start, end);
- sort(start, end, array);
+ DualPivotQuicksort.sort(array, start, end);
}
- private static void sort(int start, int end, long[] array) {
- long temp;
- int length = end - start;
- if (length < 7) {
- for (int i = start + 1; i < end; i++) {
- for (int j = i; j > start && array[j - 1] > array[j]; j--) {
- temp = array[j];
- array[j] = array[j - 1];
- array[j - 1] = temp;
- }
- }
- return;
- }
- int middle = (start + end) / 2;
- if (length > 7) {
- int bottom = start;
- int top = end - 1;
- if (length > 40) {
- length /= 8;
- bottom = med3(array, bottom, bottom + length, bottom
- + (2 * length));
- middle = med3(array, middle - length, middle, middle + length);
- top = med3(array, top - (2 * length), top - length, top);
- }
- middle = med3(array, bottom, middle, top);
- }
- long partionValue = array[middle];
- int a, b, c, d;
- a = b = start;
- c = d = end - 1;
- while (true) {
- while (b <= c && array[b] <= partionValue) {
- if (array[b] == partionValue) {
- temp = array[a];
- array[a++] = array[b];
- array[b] = temp;
- }
- b++;
- }
- while (c >= b && array[c] >= partionValue) {
- if (array[c] == partionValue) {
- temp = array[c];
- array[c] = array[d];
- array[d--] = temp;
- }
- c--;
- }
- if (b > c) {
- break;
- }
- temp = array[b];
- array[b++] = array[c];
- array[c--] = temp;
- }
- length = a - start < b - a ? a - start : b - a;
- int l = start;
- int h = b - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- length = d - c < end - 1 - d ? d - c : end - 1 - d;
- l = b;
- h = end - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- if ((length = b - a) > 0) {
- sort(start, start + length, array);
- }
- if ((length = d - c) > 0) {
- sort(end - length, end, array);
- }
+ /**
+ * Sorts the specified array in ascending numerical order.
+ *
+ * @param array
+ * the {@code short} array to be sorted.
+ */
+ public static void sort(short[] array) {
+ DualPivotQuicksort.sort(array);
+ }
+
+ /**
+ * Sorts the specified range in the array in ascending numerical order.
+ *
+ * @param array
+ * the {@code short} array to be sorted.
+ * @param start
+ * the start index to sort.
+ * @param end
+ * the last + 1 index to sort.
+ * @throws IllegalArgumentException
+ * if {@code start > end}.
+ * @throws ArrayIndexOutOfBoundsException
+ * if {@code start < 0} or {@code end > array.length}.
+ */
+ public static void sort(short[] array, int start, int end) {
+ DualPivotQuicksort.sort(array, start, end);
}
// BEGIN android-note
@@ -2447,116 +1986,6 @@
}
/**
- * Sorts the specified array in ascending numerical order.
- *
- * @param array
- * the {@code short} array to be sorted.
- */
- public static void sort(short[] array) {
- sort(0, array.length, array);
- }
-
- /**
- * Sorts the specified range in the array in ascending numerical order.
- *
- * @param array
- * the {@code short} array to be sorted.
- * @param start
- * the start index to sort.
- * @param end
- * the last + 1 index to sort.
- * @throws IllegalArgumentException
- * if {@code start > end}.
- * @throws ArrayIndexOutOfBoundsException
- * if {@code start < 0} or {@code end > array.length}.
- */
- public static void sort(short[] array, int start, int end) {
- if (array == null) {
- throw new NullPointerException();
- }
- checkBounds(array.length, start, end);
- sort(start, end, array);
- }
-
- private static void sort(int start, int end, short[] array) {
- short temp;
- int length = end - start;
- if (length < 7) {
- for (int i = start + 1; i < end; i++) {
- for (int j = i; j > start && array[j - 1] > array[j]; j--) {
- temp = array[j];
- array[j] = array[j - 1];
- array[j - 1] = temp;
- }
- }
- return;
- }
- int middle = (start + end) / 2;
- if (length > 7) {
- int bottom = start;
- int top = end - 1;
- if (length > 40) {
- length /= 8;
- bottom = med3(array, bottom, bottom + length, bottom
- + (2 * length));
- middle = med3(array, middle - length, middle, middle + length);
- top = med3(array, top - (2 * length), top - length, top);
- }
- middle = med3(array, bottom, middle, top);
- }
- short partionValue = array[middle];
- int a, b, c, d;
- a = b = start;
- c = d = end - 1;
- while (true) {
- while (b <= c && array[b] <= partionValue) {
- if (array[b] == partionValue) {
- temp = array[a];
- array[a++] = array[b];
- array[b] = temp;
- }
- b++;
- }
- while (c >= b && array[c] >= partionValue) {
- if (array[c] == partionValue) {
- temp = array[c];
- array[c] = array[d];
- array[d--] = temp;
- }
- c--;
- }
- if (b > c) {
- break;
- }
- temp = array[b];
- array[b++] = array[c];
- array[c--] = temp;
- }
- length = a - start < b - a ? a - start : b - a;
- int l = start;
- int h = b - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- length = d - c < end - 1 - d ? d - c : end - 1 - d;
- l = b;
- h = end - length;
- while (length-- > 0) {
- temp = array[l];
- array[l++] = array[h];
- array[h++] = temp;
- }
- if ((length = b - a) > 0) {
- sort(start, start + length, array);
- }
- if ((length = d - c) > 0) {
- sort(end - length, end, array);
- }
- }
-
- /**
* Creates a {@code String} representation of the {@code boolean[]} passed.
* The result is surrounded by brackets ({@code "[]"}), each
* element is converted to a {@code String} via the
diff --git a/libcore/luni/src/main/java/java/util/DualPivotQuicksort.java b/libcore/luni/src/main/java/java/util/DualPivotQuicksort.java
new file mode 100644
index 0000000..8c3930f
--- /dev/null
+++ b/libcore/luni/src/main/java/java/util/DualPivotQuicksort.java
@@ -0,0 +1,2241 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package java.util;
+
+/**
+ * This class implements the Dual-Pivot Quicksort algorithm by
+ * Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. The algorithm
+ * offers O(n log(n)) performance on many data sets that cause other
+ * quicksorts to degrade to quadratic performance, and is typically
+ * faster than traditional (one-pivot) Quicksort implementations.
+ *
+ * @author Vladimir Yaroslavskiy
+ * @author Jon Bentley
+ * @author Josh Bloch
+ *
+ * @version 2009.11.23 m765.827.12j
+ */
+final class DualPivotQuicksort {
+
+ /**
+ * Prevents instantiation.
+ */
+ private DualPivotQuicksort() {}
+
+ /*
+ * Tuning parameters.
+ */
+
+ /**
+ * If the length of an array to be sorted is less than this
+ * constant, insertion sort is used in preference to Quicksort.
+ */
+ private static final int INSERTION_SORT_THRESHOLD = 32;
+
+ /**
+ * If the length of a byte array to be sorted is greater than
+ * this constant, counting sort is used in preference to Quicksort.
+ */
+ private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 128;
+
+ /**
+ * If the length of a short or char array to be sorted is greater
+ * than this constant, counting sort is used in preference to Quicksort.
+ */
+ private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 32768;
+
+ /*
+ * Sorting methods for 7 primitive types.
+ */
+
+ /**
+ * Sorts the specified array into ascending numerical order.
+ *
+ * @param a the array to be sorted
+ */
+ public static void sort(int[] a) {
+ doSort(a, 0, a.length - 1);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * the range to be sorted is empty.
+ *
+ * @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 {@code fromIndex > toIndex}
+ * @throws ArrayIndexOutOfBoundsException
+ * if {@code fromIndex < 0} or {@code toIndex > a.length}
+ */
+ public static void sort(int[] a, int fromIndex, int toIndex) {
+ rangeCheck(a.length, fromIndex, toIndex);
+ doSort(a, fromIndex, toIndex - 1);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. This
+ * method differs from the public {@code sort} method in that the
+ * {@code right} index is inclusive, and it does no range checking on
+ * {@code left} or {@code right}.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void doSort(int[] a, int left, int right) {
+ // Use insertion sort on tiny arrays
+ if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
+ for (int k = left + 1; k <= right; k++) {
+ int ak = a[k];
+ int j;
+ for (j = k - 1; j >= left && ak < a[j]; j--) {
+ a[j + 1] = a[j];
+ }
+ a[j + 1] = ak;
+ }
+ } else { // Use Dual-Pivot Quicksort on large arrays
+ dualPivotQuicksort(a, left, right);
+ }
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void dualPivotQuicksort(int[] a, int left, int right) {
+ // Compute indices of five evenly spaced elements
+ int sixth = (right - left + 1) / 6;
+ int e1 = left + sixth;
+ int e5 = right - sixth;
+ int e3 = (left + right) >>> 1; // The midpoint
+ int e4 = e3 + sixth;
+ int e2 = e3 - sixth;
+
+ // Sort these elements using a 5-element sorting network
+ int ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+
+ if (ae1 > ae2) { int t = ae1; ae1 = ae2; ae2 = t; }
+ if (ae4 > ae5) { int t = ae4; ae4 = ae5; ae5 = t; }
+ if (ae1 > ae3) { int t = ae1; ae1 = ae3; ae3 = t; }
+ if (ae2 > ae3) { int t = ae2; ae2 = ae3; ae3 = t; }
+ if (ae1 > ae4) { int t = ae1; ae1 = ae4; ae4 = t; }
+ if (ae3 > ae4) { int t = ae3; ae3 = ae4; ae4 = t; }
+ if (ae2 > ae5) { int t = ae2; ae2 = ae5; ae5 = t; }
+ if (ae2 > ae3) { int t = ae2; ae2 = ae3; ae3 = t; }
+ if (ae4 > ae5) { int t = ae4; ae4 = ae5; ae5 = t; }
+
+ a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+
+ /*
+ * Use the second and fourth of the five sorted elements as pivots.
+ * These values are inexpensive approximations of the first and
+ * second terciles of the array. Note that pivot1 <= pivot2.
+ *
+ * The pivots are stored in local variables, and the first and
+ * the last of the sorted elements are moved to the locations
+ * formerly occupied by the pivots. When partitioning is complete,
+ * the pivots are swapped back into their final positions, and
+ * excluded from subsequent sorting.
+ */
+ int pivot1 = ae2; a[e2] = a[left];
+ int pivot2 = ae4; a[e4] = a[right];
+
+ // Pointers
+ int less = left + 1; // The index of first element of center part
+ int great = right - 1; // The index before first element of right part
+
+ boolean pivotsDiffer = pivot1 != pivot2;
+
+ if (pivotsDiffer) {
+ /*
+ * Partitioning:
+ *
+ * left part center part right part
+ * ------------------------------------------------------------
+ * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
+ * ------------------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (left, less) < pivot1
+ * pivot1 <= all in [less, k) <= pivot2
+ * all in (great, right) > pivot2
+ *
+ * Pointer k is the first index of ?-part
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ int ak = a[k];
+ if (ak < pivot1) {
+ if (k != less) {
+ a[k] = a[less];
+ a[less] = ak;
+ }
+ less++;
+ } else if (ak > pivot2) {
+ while (a[great] > pivot2) {
+ if (great-- == k) {
+ break outer;
+ }
+ }
+ if (a[great] < pivot1) {
+ a[k] = a[less];
+ a[less++] = a[great];
+ } else { // pivot1 <= a[great] <= pivot2
+ a[k] = a[great];
+ }
+ a[great--] = ak;
+ }
+ }
+ } else { // Pivots are equal
+ /*
+ * Partition degenerates to the traditional 3-way
+ * (or "Dutch National Flag") partition:
+ *
+ * left part center part right part
+ * -------------------------------------------------
+ * [ < pivot | == pivot | ? | > pivot ]
+ * -------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (left, less) < pivot
+ * all in [less, k) == pivot
+ * all in (great, right) > pivot
+ *
+ * Pointer k is the first index of ?-part
+ */
+ for (int k = less; k <= great; k++) {
+ int ak = a[k];
+ if (ak == pivot1) {
+ continue;
+ }
+ if (ak < pivot1) {
+ if (k != less) {
+ a[k] = a[less];
+ a[less] = ak;
+ }
+ less++;
+ } else { // ak > pivot1
+ /*
+ * We know that pivot1 == a[e3] == pivot2. Thus, we know
+ * that great will still be >= k when the following loop
+ * terminates, even though we don't test for it explicitly.
+ * In other words, a[e3] acts as a sentinel for great.
+ */
+ while (a[great] > pivot1) {
+ great--;
+ }
+ if (a[great] < pivot1) {
+ a[k] = a[less];
+ a[less++] = a[great];
+ } else { // a[great] == pivot1
+ a[k] = pivot1;
+ }
+ a[great--] = ak;
+ }
+ }
+ }
+
+ // Swap pivots into their final positions
+ a[left] = a[less - 1]; a[less - 1] = pivot1;
+ a[right] = a[great + 1]; a[great + 1] = pivot2;
+
+ // Sort left and right parts recursively, excluding known pivot values
+ doSort(a, left, less - 2);
+ doSort(a, great + 2, right);
+
+ /*
+ * If pivot1 == pivot2, all elements from center
+ * part are equal and, therefore, already sorted
+ */
+ if (!pivotsDiffer) {
+ return;
+ }
+
+ /*
+ * If center part is too large (comprises > 2/3 of
+ * the array), swap internal pivot values to ends
+ */
+ if (less < e1 && e5 < great) {
+ while (a[less] == pivot1) {
+ less++;
+ }
+ while (a[great] == pivot2) {
+ great--;
+ }
+
+ /*
+ * Partitioning:
+ *
+ * -------------------------------------------------------------
+ * [ == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 ]
+ * -------------------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (*, less) == pivot1
+ * pivot1 < all in [less, k) < pivot2
+ * all in (great, *) == pivot2
+ *
+ * Pointer k is the first index of ?-part
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ int ak = a[k];
+ if (ak == pivot2) {
+ while (a[great] == pivot2) {
+ if (k == great--) {
+ break outer;
+ }
+ }
+ if (a[great] == pivot1) {
+ a[k] = a[less];
+ a[less++] = pivot1;
+ } else { // pivot1 < a[great] < pivot2
+ a[k] = a[great];
+ }
+ a[great--] = pivot2;
+ } else if (ak == pivot1) {
+ a[k] = a[less];
+ a[less++] = pivot1;
+ }
+ }
+ }
+
+ // Sort center part recursively, excluding known pivot values
+ doSort(a, less, great);
+ }
+
+ /**
+ * Sorts the specified array into ascending numerical order.
+ *
+ * @param a the array to be sorted
+ */
+ public static void sort(long[] a) {
+ doSort(a, 0, a.length - 1);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * the range to be sorted is empty.
+ *
+ * @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 {@code fromIndex > toIndex}
+ * @throws ArrayIndexOutOfBoundsException
+ * if {@code fromIndex < 0} or {@code toIndex > a.length}
+ */
+ public static void sort(long[] a, int fromIndex, int toIndex) {
+ rangeCheck(a.length, fromIndex, toIndex);
+ doSort(a, fromIndex, toIndex - 1);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. This
+ * method differs from the public {@code sort} method in that the
+ * {@code right} index is inclusive, and it does no range checking on
+ * {@code left} or {@code right}.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void doSort(long[] a, int left, int right) {
+ // Use insertion sort on tiny arrays
+ if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
+ for (int k = left + 1; k <= right; k++) {
+ long ak = a[k];
+ int j;
+ for (j = k - 1; j >= left && ak < a[j]; j--) {
+ a[j + 1] = a[j];
+ }
+ a[j + 1] = ak;
+ }
+ } else { // Use Dual-Pivot Quicksort on large arrays
+ dualPivotQuicksort(a, left, right);
+ }
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void dualPivotQuicksort(long[] a, int left, int right) {
+ // Compute indices of five evenly spaced elements
+ int sixth = (right - left + 1) / 6;
+ int e1 = left + sixth;
+ int e5 = right - sixth;
+ int e3 = (left + right) >>> 1; // The midpoint
+ int e4 = e3 + sixth;
+ int e2 = e3 - sixth;
+
+ // Sort these elements using a 5-element sorting network
+ long ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+
+ if (ae1 > ae2) { long t = ae1; ae1 = ae2; ae2 = t; }
+ if (ae4 > ae5) { long t = ae4; ae4 = ae5; ae5 = t; }
+ if (ae1 > ae3) { long t = ae1; ae1 = ae3; ae3 = t; }
+ if (ae2 > ae3) { long t = ae2; ae2 = ae3; ae3 = t; }
+ if (ae1 > ae4) { long t = ae1; ae1 = ae4; ae4 = t; }
+ if (ae3 > ae4) { long t = ae3; ae3 = ae4; ae4 = t; }
+ if (ae2 > ae5) { long t = ae2; ae2 = ae5; ae5 = t; }
+ if (ae2 > ae3) { long t = ae2; ae2 = ae3; ae3 = t; }
+ if (ae4 > ae5) { long t = ae4; ae4 = ae5; ae5 = t; }
+
+ a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+
+ /*
+ * Use the second and fourth of the five sorted elements as pivots.
+ * These values are inexpensive approximations of the first and
+ * second terciles of the array. Note that pivot1 <= pivot2.
+ *
+ * The pivots are stored in local variables, and the first and
+ * the last of the sorted elements are moved to the locations
+ * formerly occupied by the pivots. When partitioning is complete,
+ * the pivots are swapped back into their final positions, and
+ * excluded from subsequent sorting.
+ */
+ long pivot1 = ae2; a[e2] = a[left];
+ long pivot2 = ae4; a[e4] = a[right];
+
+ // Pointers
+ int less = left + 1; // The index of first element of center part
+ int great = right - 1; // The index before first element of right part
+
+ boolean pivotsDiffer = pivot1 != pivot2;
+
+ if (pivotsDiffer) {
+ /*
+ * Partitioning:
+ *
+ * left part center part right part
+ * ------------------------------------------------------------
+ * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
+ * ------------------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (left, less) < pivot1
+ * pivot1 <= all in [less, k) <= pivot2
+ * all in (great, right) > pivot2
+ *
+ * Pointer k is the first index of ?-part
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ long ak = a[k];
+ if (ak < pivot1) {
+ if (k != less) {
+ a[k] = a[less];
+ a[less] = ak;
+ }
+ less++;
+ } else if (ak > pivot2) {
+ while (a[great] > pivot2) {
+ if (great-- == k) {
+ break outer;
+ }
+ }
+ if (a[great] < pivot1) {
+ a[k] = a[less];
+ a[less++] = a[great];
+ } else { // pivot1 <= a[great] <= pivot2
+ a[k] = a[great];
+ }
+ a[great--] = ak;
+ }
+ }
+ } else { // Pivots are equal
+ /*
+ * Partition degenerates to the traditional 3-way
+ * (or "Dutch National Flag") partition:
+ *
+ * left part center part right part
+ * -------------------------------------------------
+ * [ < pivot | == pivot | ? | > pivot ]
+ * -------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (left, less) < pivot
+ * all in [less, k) == pivot
+ * all in (great, right) > pivot
+ *
+ * Pointer k is the first index of ?-part
+ */
+ for (int k = less; k <= great; k++) {
+ long ak = a[k];
+ if (ak == pivot1) {
+ continue;
+ }
+ if (ak < pivot1) {
+ if (k != less) {
+ a[k] = a[less];
+ a[less] = ak;
+ }
+ less++;
+ } else { // ak > pivot1
+ /*
+ * We know that pivot1 == a[e3] == pivot2. Thus, we know
+ * that great will still be >= k when the following loop
+ * terminates, even though we don't test for it explicitly.
+ * In other words, a[e3] acts as a sentinel for great.
+ */
+ while (a[great] > pivot1) {
+ great--;
+ }
+ if (a[great] < pivot1) {
+ a[k] = a[less];
+ a[less++] = a[great];
+ } else { // a[great] == pivot1
+ a[k] = pivot1;
+ }
+ a[great--] = ak;
+ }
+ }
+ }
+
+ // Swap pivots into their final positions
+ a[left] = a[less - 1]; a[less - 1] = pivot1;
+ a[right] = a[great + 1]; a[great + 1] = pivot2;
+
+ // Sort left and right parts recursively, excluding known pivot values
+ doSort(a, left, less - 2);
+ doSort(a, great + 2, right);
+
+ /*
+ * If pivot1 == pivot2, all elements from center
+ * part are equal and, therefore, already sorted
+ */
+ if (!pivotsDiffer) {
+ return;
+ }
+
+ /*
+ * If center part is too large (comprises > 2/3 of
+ * the array), swap internal pivot values to ends
+ */
+ if (less < e1 && e5 < great) {
+ while (a[less] == pivot1) {
+ less++;
+ }
+ while (a[great] == pivot2) {
+ great--;
+ }
+
+ /*
+ * Partitioning:
+ *
+ * -------------------------------------------------------------
+ * [ == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 ]
+ * -------------------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (*, less) == pivot1
+ * pivot1 < all in [less, k) < pivot2
+ * all in (great, *) == pivot2
+ *
+ * Pointer k is the first index of ?-part
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ long ak = a[k];
+ if (ak == pivot2) {
+ while (a[great] == pivot2) {
+ if (k == great--) {
+ break outer;
+ }
+ }
+ if (a[great] == pivot1) {
+ a[k] = a[less];
+ a[less++] = pivot1;
+ } else { // pivot1 < a[great] < pivot2
+ a[k] = a[great];
+ }
+ a[great--] = pivot2;
+ } else if (ak == pivot1) {
+ a[k] = a[less];
+ a[less++] = pivot1;
+ }
+ }
+ }
+
+ // Sort center part recursively, excluding known pivot values
+ doSort(a, less, great);
+ }
+
+ /**
+ * Sorts the specified array into ascending numerical order.
+ *
+ * @param a the array to be sorted
+ */
+ public static void sort(short[] a) {
+ doSort(a, 0, a.length - 1);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * the range to be sorted is empty.
+ *
+ * @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 {@code fromIndex > toIndex}
+ * @throws ArrayIndexOutOfBoundsException
+ * if {@code fromIndex < 0} or {@code toIndex > a.length}
+ */
+ public static void sort(short[] a, int fromIndex, int toIndex) {
+ rangeCheck(a.length, fromIndex, toIndex);
+ doSort(a, fromIndex, toIndex - 1);
+ }
+
+ /** The number of distinct short values. */
+ private static final int NUM_SHORT_VALUES = 1 << 16;
+
+ /**
+ * Sorts the specified range of the array into ascending order. This
+ * method differs from the public {@code sort} method in that the
+ * {@code right} index is inclusive, and it does no range checking on
+ * {@code left} or {@code right}.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void doSort(short[] a, int left, int right) {
+ // Use insertion sort on tiny arrays
+ if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
+ for (int k = left + 1; k <= right; k++) {
+ short ak = a[k];
+ int j;
+ for (j = k - 1; j >= left && ak < a[j]; j--) {
+ a[j + 1] = a[j];
+ }
+ a[j + 1] = ak;
+ }
+ } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
+ // Use counting sort on huge arrays
+ int[] count = new int[NUM_SHORT_VALUES];
+
+ for (int i = left; i <= right; i++) {
+ count[a[i] - Short.MIN_VALUE]++;
+ }
+ for (int i = 0, k = left; i < count.length && k <= right; i++) {
+ short value = (short) (i + Short.MIN_VALUE);
+
+ for (int s = count[i]; s > 0; s--) {
+ a[k++] = value;
+ }
+ }
+ } else { // Use Dual-Pivot Quicksort on large arrays
+ dualPivotQuicksort(a, left, right);
+ }
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void dualPivotQuicksort(short[] a, int left, int right) {
+ // Compute indices of five evenly spaced elements
+ int sixth = (right - left + 1) / 6;
+ int e1 = left + sixth;
+ int e5 = right - sixth;
+ int e3 = (left + right) >>> 1; // The midpoint
+ int e4 = e3 + sixth;
+ int e2 = e3 - sixth;
+
+ // Sort these elements using a 5-element sorting network
+ short ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+
+ if (ae1 > ae2) { short t = ae1; ae1 = ae2; ae2 = t; }
+ if (ae4 > ae5) { short t = ae4; ae4 = ae5; ae5 = t; }
+ if (ae1 > ae3) { short t = ae1; ae1 = ae3; ae3 = t; }
+ if (ae2 > ae3) { short t = ae2; ae2 = ae3; ae3 = t; }
+ if (ae1 > ae4) { short t = ae1; ae1 = ae4; ae4 = t; }
+ if (ae3 > ae4) { short t = ae3; ae3 = ae4; ae4 = t; }
+ if (ae2 > ae5) { short t = ae2; ae2 = ae5; ae5 = t; }
+ if (ae2 > ae3) { short t = ae2; ae2 = ae3; ae3 = t; }
+ if (ae4 > ae5) { short t = ae4; ae4 = ae5; ae5 = t; }
+
+ a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+
+ /*
+ * Use the second and fourth of the five sorted elements as pivots.
+ * These values are inexpensive approximations of the first and
+ * second terciles of the array. Note that pivot1 <= pivot2.
+ *
+ * The pivots are stored in local variables, and the first and
+ * the last of the sorted elements are moved to the locations
+ * formerly occupied by the pivots. When partitioning is complete,
+ * the pivots are swapped back into their final positions, and
+ * excluded from subsequent sorting.
+ */
+ short pivot1 = ae2; a[e2] = a[left];
+ short pivot2 = ae4; a[e4] = a[right];
+
+ // Pointers
+ int less = left + 1; // The index of first element of center part
+ int great = right - 1; // The index before first element of right part
+
+ boolean pivotsDiffer = pivot1 != pivot2;
+
+ if (pivotsDiffer) {
+ /*
+ * Partitioning:
+ *
+ * left part center part right part
+ * ------------------------------------------------------------
+ * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
+ * ------------------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (left, less) < pivot1
+ * pivot1 <= all in [less, k) <= pivot2
+ * all in (great, right) > pivot2
+ *
+ * Pointer k is the first index of ?-part
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ short ak = a[k];
+ if (ak < pivot1) {
+ if (k != less) {
+ a[k] = a[less];
+ a[less] = ak;
+ }
+ less++;
+ } else if (ak > pivot2) {
+ while (a[great] > pivot2) {
+ if (great-- == k) {
+ break outer;
+ }
+ }
+ if (a[great] < pivot1) {
+ a[k] = a[less];
+ a[less++] = a[great];
+ } else { // pivot1 <= a[great] <= pivot2
+ a[k] = a[great];
+ }
+ a[great--] = ak;
+ }
+ }
+ } else { // Pivots are equal
+ /*
+ * Partition degenerates to the traditional 3-way
+ * (or "Dutch National Flag") partition:
+ *
+ * left part center part right part
+ * -------------------------------------------------
+ * [ < pivot | == pivot | ? | > pivot ]
+ * -------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (left, less) < pivot
+ * all in [less, k) == pivot
+ * all in (great, right) > pivot
+ *
+ * Pointer k is the first index of ?-part
+ */
+ for (int k = less; k <= great; k++) {
+ short ak = a[k];
+ if (ak == pivot1) {
+ continue;
+ }
+ if (ak < pivot1) {
+ if (k != less) {
+ a[k] = a[less];
+ a[less] = ak;
+ }
+ less++;
+ } else { // ak > pivot1
+ /*
+ * We know that pivot1 == a[e3] == pivot2. Thus, we know
+ * that great will still be >= k when the following loop
+ * terminates, even though we don't test for it explicitly.
+ * In other words, a[e3] acts as a sentinel for great.
+ */
+ while (a[great] > pivot1) {
+ great--;
+ }
+ if (a[great] < pivot1) {
+ a[k] = a[less];
+ a[less++] = a[great];
+ } else { // a[great] == pivot1
+ a[k] = pivot1;
+ }
+ a[great--] = ak;
+ }
+ }
+ }
+
+ // Swap pivots into their final positions
+ a[left] = a[less - 1]; a[less - 1] = pivot1;
+ a[right] = a[great + 1]; a[great + 1] = pivot2;
+
+ // Sort left and right parts recursively, excluding known pivot values
+ doSort(a, left, less - 2);
+ doSort(a, great + 2, right);
+
+ /*
+ * If pivot1 == pivot2, all elements from center
+ * part are equal and, therefore, already sorted
+ */
+ if (!pivotsDiffer) {
+ return;
+ }
+
+ /*
+ * If center part is too large (comprises > 2/3 of
+ * the array), swap internal pivot values to ends
+ */
+ if (less < e1 && e5 < great) {
+ while (a[less] == pivot1) {
+ less++;
+ }
+ while (a[great] == pivot2) {
+ great--;
+ }
+
+ /*
+ * Partitioning:
+ *
+ * -------------------------------------------------------------
+ * [ == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 ]
+ * -------------------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (*, less) == pivot1
+ * pivot1 < all in [less, k) < pivot2
+ * all in (great, *) == pivot2
+ *
+ * Pointer k is the first index of ?-part
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ short ak = a[k];
+ if (ak == pivot2) {
+ while (a[great] == pivot2) {
+ if (k == great--) {
+ break outer;
+ }
+ }
+ if (a[great] == pivot1) {
+ a[k] = a[less];
+ a[less++] = pivot1;
+ } else { // pivot1 < a[great] < pivot2
+ a[k] = a[great];
+ }
+ a[great--] = pivot2;
+ } else if (ak == pivot1) {
+ a[k] = a[less];
+ a[less++] = pivot1;
+ }
+ }
+ }
+
+ // Sort center part recursively, excluding known pivot values
+ doSort(a, less, great); }
+
+ /**
+ * Sorts the specified array into ascending numerical order.
+ *
+ * @param a the array to be sorted
+ */
+ public static void sort(char[] a) {
+ doSort(a, 0, a.length - 1);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * the range to be sorted is empty.
+ *
+ * @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 {@code fromIndex > toIndex}
+ * @throws ArrayIndexOutOfBoundsException
+ * if {@code fromIndex < 0} or {@code toIndex > a.length}
+ */
+ public static void sort(char[] a, int fromIndex, int toIndex) {
+ rangeCheck(a.length, fromIndex, toIndex);
+ doSort(a, fromIndex, toIndex - 1);
+ }
+
+ /** The number of distinct char values. */
+ private static final int NUM_CHAR_VALUES = 1 << 16;
+
+ /**
+ * Sorts the specified range of the array into ascending order. This
+ * method differs from the public {@code sort} method in that the
+ * {@code right} index is inclusive, and it does no range checking on
+ * {@code left} or {@code right}.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void doSort(char[] a, int left, int right) {
+ // Use insertion sort on tiny arrays
+ if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
+ for (int k = left + 1; k <= right; k++) {
+ char ak = a[k];
+ int j;
+ for (j = k - 1; j >= left && ak < a[j]; j--) {
+ a[j + 1] = a[j];
+ }
+ a[j + 1] = ak;
+ }
+ } else if (right-left+1 > COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR) {
+ // Use counting sort on huge arrays
+ int[] count = new int[NUM_CHAR_VALUES];
+
+ for (int i = left; i <= right; i++) {
+ count[a[i]]++;
+ }
+ for (int i = 0, k = left; i < count.length && k <= right; i++) {
+ for (int s = count[i]; s > 0; s--) {
+ a[k++] = (char) i;
+ }
+ }
+ } else { // Use Dual-Pivot Quicksort on large arrays
+ dualPivotQuicksort(a, left, right);
+ }
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void dualPivotQuicksort(char[] a, int left, int right) {
+ // Compute indices of five evenly spaced elements
+ int sixth = (right - left + 1) / 6;
+ int e1 = left + sixth;
+ int e5 = right - sixth;
+ int e3 = (left + right) >>> 1; // The midpoint
+ int e4 = e3 + sixth;
+ int e2 = e3 - sixth;
+
+ // Sort these elements using a 5-element sorting network
+ char ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+
+ if (ae1 > ae2) { char t = ae1; ae1 = ae2; ae2 = t; }
+ if (ae4 > ae5) { char t = ae4; ae4 = ae5; ae5 = t; }
+ if (ae1 > ae3) { char t = ae1; ae1 = ae3; ae3 = t; }
+ if (ae2 > ae3) { char t = ae2; ae2 = ae3; ae3 = t; }
+ if (ae1 > ae4) { char t = ae1; ae1 = ae4; ae4 = t; }
+ if (ae3 > ae4) { char t = ae3; ae3 = ae4; ae4 = t; }
+ if (ae2 > ae5) { char t = ae2; ae2 = ae5; ae5 = t; }
+ if (ae2 > ae3) { char t = ae2; ae2 = ae3; ae3 = t; }
+ if (ae4 > ae5) { char t = ae4; ae4 = ae5; ae5 = t; }
+
+ a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+
+ /*
+ * Use the second and fourth of the five sorted elements as pivots.
+ * These values are inexpensive approximations of the first and
+ * second terciles of the array. Note that pivot1 <= pivot2.
+ *
+ * The pivots are stored in local variables, and the first and
+ * the last of the sorted elements are moved to the locations
+ * formerly occupied by the pivots. When partitioning is complete,
+ * the pivots are swapped back into their final positions, and
+ * excluded from subsequent sorting.
+ */
+ char pivot1 = ae2; a[e2] = a[left];
+ char pivot2 = ae4; a[e4] = a[right];
+
+ // Pointers
+ int less = left + 1; // The index of first element of center part
+ int great = right - 1; // The index before first element of right part
+
+ boolean pivotsDiffer = pivot1 != pivot2;
+
+ if (pivotsDiffer) {
+ /*
+ * Partitioning:
+ *
+ * left part center part right part
+ * ------------------------------------------------------------
+ * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
+ * ------------------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (left, less) < pivot1
+ * pivot1 <= all in [less, k) <= pivot2
+ * all in (great, right) > pivot2
+ *
+ * Pointer k is the first index of ?-part
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ char ak = a[k];
+ if (ak < pivot1) {
+ if (k != less) {
+ a[k] = a[less];
+ a[less] = ak;
+ }
+ less++;
+ } else if (ak > pivot2) {
+ while (a[great] > pivot2) {
+ if (great-- == k) {
+ break outer;
+ }
+ }
+ if (a[great] < pivot1) {
+ a[k] = a[less];
+ a[less++] = a[great];
+ } else { // pivot1 <= a[great] <= pivot2
+ a[k] = a[great];
+ }
+ a[great--] = ak;
+ }
+ }
+ } else { // Pivots are equal
+ /*
+ * Partition degenerates to the traditional 3-way
+ * (or "Dutch National Flag") partition:
+ *
+ * left part center part right part
+ * -------------------------------------------------
+ * [ < pivot | == pivot | ? | > pivot ]
+ * -------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (left, less) < pivot
+ * all in [less, k) == pivot
+ * all in (great, right) > pivot
+ *
+ * Pointer k is the first index of ?-part
+ */
+ for (int k = less; k <= great; k++) {
+ char ak = a[k];
+ if (ak == pivot1) {
+ continue;
+ }
+ if (ak < pivot1) {
+ if (k != less) {
+ a[k] = a[less];
+ a[less] = ak;
+ }
+ less++;
+ } else { // ak > pivot1
+ /*
+ * We know that pivot1 == a[e3] == pivot2. Thus, we know
+ * that great will still be >= k when the following loop
+ * terminates, even though we don't test for it explicitly.
+ * In other words, a[e3] acts as a sentinel for great.
+ */
+ while (a[great] > pivot1) {
+ great--;
+ }
+ if (a[great] < pivot1) {
+ a[k] = a[less];
+ a[less++] = a[great];
+ } else { // a[great] == pivot1
+ a[k] = pivot1;
+ }
+ a[great--] = ak;
+ }
+ }
+ }
+
+ // Swap pivots into their final positions
+ a[left] = a[less - 1]; a[less - 1] = pivot1;
+ a[right] = a[great + 1]; a[great + 1] = pivot2;
+
+ // Sort left and right parts recursively, excluding known pivot values
+ doSort(a, left, less - 2);
+ doSort(a, great + 2, right);
+
+ /*
+ * If pivot1 == pivot2, all elements from center
+ * part are equal and, therefore, already sorted
+ */
+ if (!pivotsDiffer) {
+ return;
+ }
+
+ /*
+ * If center part is too large (comprises > 2/3 of
+ * the array), swap internal pivot values to ends
+ */
+ if (less < e1 && e5 < great) {
+ while (a[less] == pivot1) {
+ less++;
+ }
+ while (a[great] == pivot2) {
+ great--;
+ }
+
+ /*
+ * Partitioning:
+ *
+ * -------------------------------------------------------------
+ * [ == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 ]
+ * -------------------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (*, less) == pivot1
+ * pivot1 < all in [less, k) < pivot2
+ * all in (great, *) == pivot2
+ *
+ * Pointer k is the first index of ?-part
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ char ak = a[k];
+ if (ak == pivot2) {
+ while (a[great] == pivot2) {
+ if (k == great--) {
+ break outer;
+ }
+ }
+ if (a[great] == pivot1) {
+ a[k] = a[less];
+ a[less++] = pivot1;
+ } else { // pivot1 < a[great] < pivot2
+ a[k] = a[great];
+ }
+ a[great--] = pivot2;
+ } else if (ak == pivot1) {
+ a[k] = a[less];
+ a[less++] = pivot1;
+ }
+ }
+ }
+
+ // Sort center part recursively, excluding known pivot values
+ doSort(a, less, great); }
+
+ /**
+ * Sorts the specified array into ascending numerical order.
+ *
+ * @param a the array to be sorted
+ */
+ public static void sort(byte[] a) {
+ doSort(a, 0, a.length - 1);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * the range to be sorted is empty.
+ *
+ * @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 {@code fromIndex > toIndex}
+ * @throws ArrayIndexOutOfBoundsException
+ * if {@code fromIndex < 0} or {@code toIndex > a.length}
+ */
+ public static void sort(byte[] a, int fromIndex, int toIndex) {
+ rangeCheck(a.length, fromIndex, toIndex);
+ doSort(a, fromIndex, toIndex - 1);
+ }
+
+ /** The number of distinct byte values. */
+ private static final int NUM_BYTE_VALUES = 1 << 8;
+
+ /**
+ * Sorts the specified range of the array into ascending order. This
+ * method differs from the public {@code sort} method in that the
+ * {@code right} index is inclusive, and it does no range checking on
+ * {@code left} or {@code right}.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void doSort(byte[] a, int left, int right) {
+ // Use insertion sort on tiny arrays
+ if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
+ for (int k = left + 1; k <= right; k++) {
+ byte ak = a[k];
+ int j;
+ for (j = k - 1; j >= left && ak < a[j]; j--) {
+ a[j + 1] = a[j];
+ }
+ a[j + 1] = ak;
+ }
+ } else if (right - left + 1 > COUNTING_SORT_THRESHOLD_FOR_BYTE) {
+ // Use counting sort on huge arrays
+ int[] count = new int[NUM_BYTE_VALUES];
+
+ for (int i = left; i <= right; i++) {
+ count[a[i] - Byte.MIN_VALUE]++;
+ }
+ for (int i = 0, k = left; i < count.length && k <= right; i++) {
+ byte value = (byte) (i + Byte.MIN_VALUE);
+
+ for (int s = count[i]; s > 0; s--) {
+ a[k++] = value;
+ }
+ }
+ } else { // Use Dual-Pivot Quicksort on large arrays
+ dualPivotQuicksort(a, left, right);
+ }
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void dualPivotQuicksort(byte[] a, int left, int right) {
+ // Compute indices of five evenly spaced elements
+ int sixth = (right - left + 1) / 6;
+ int e1 = left + sixth;
+ int e5 = right - sixth;
+ int e3 = (left + right) >>> 1; // The midpoint
+ int e4 = e3 + sixth;
+ int e2 = e3 - sixth;
+
+ // Sort these elements using a 5-element sorting network
+ byte ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+
+ if (ae1 > ae2) { byte t = ae1; ae1 = ae2; ae2 = t; }
+ if (ae4 > ae5) { byte t = ae4; ae4 = ae5; ae5 = t; }
+ if (ae1 > ae3) { byte t = ae1; ae1 = ae3; ae3 = t; }
+ if (ae2 > ae3) { byte t = ae2; ae2 = ae3; ae3 = t; }
+ if (ae1 > ae4) { byte t = ae1; ae1 = ae4; ae4 = t; }
+ if (ae3 > ae4) { byte t = ae3; ae3 = ae4; ae4 = t; }
+ if (ae2 > ae5) { byte t = ae2; ae2 = ae5; ae5 = t; }
+ if (ae2 > ae3) { byte t = ae2; ae2 = ae3; ae3 = t; }
+ if (ae4 > ae5) { byte t = ae4; ae4 = ae5; ae5 = t; }
+
+ a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+
+ /*
+ * Use the second and fourth of the five sorted elements as pivots.
+ * These values are inexpensive approximations of the first and
+ * second terciles of the array. Note that pivot1 <= pivot2.
+ *
+ * The pivots are stored in local variables, and the first and
+ * the last of the sorted elements are moved to the locations
+ * formerly occupied by the pivots. When partitioning is complete,
+ * the pivots are swapped back into their final positions, and
+ * excluded from subsequent sorting.
+ */
+ byte pivot1 = ae2; a[e2] = a[left];
+ byte pivot2 = ae4; a[e4] = a[right];
+
+ // Pointers
+ int less = left + 1; // The index of first element of center part
+ int great = right - 1; // The index before first element of right part
+
+ boolean pivotsDiffer = pivot1 != pivot2;
+
+ if (pivotsDiffer) {
+ /*
+ * Partitioning:
+ *
+ * left part center part right part
+ * ------------------------------------------------------------
+ * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
+ * ------------------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (left, less) < pivot1
+ * pivot1 <= all in [less, k) <= pivot2
+ * all in (great, right) > pivot2
+ *
+ * Pointer k is the first index of ?-part
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ byte ak = a[k];
+ if (ak < pivot1) {
+ if (k != less) {
+ a[k] = a[less];
+ a[less] = ak;
+ }
+ less++;
+ } else if (ak > pivot2) {
+ while (a[great] > pivot2) {
+ if (great-- == k) {
+ break outer;
+ }
+ }
+ if (a[great] < pivot1) {
+ a[k] = a[less];
+ a[less++] = a[great];
+ } else { // pivot1 <= a[great] <= pivot2
+ a[k] = a[great];
+ }
+ a[great--] = ak;
+ }
+ }
+ } else { // Pivots are equal
+ /*
+ * Partition degenerates to the traditional 3-way
+ * (or "Dutch National Flag") partition:
+ *
+ * left part center part right part
+ * -------------------------------------------------
+ * [ < pivot | == pivot | ? | > pivot ]
+ * -------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (left, less) < pivot
+ * all in [less, k) == pivot
+ * all in (great, right) > pivot
+ *
+ * Pointer k is the first index of ?-part
+ */
+ for (int k = less; k <= great; k++) {
+ byte ak = a[k];
+ if (ak == pivot1) {
+ continue;
+ }
+ if (ak < pivot1) {
+ if (k != less) {
+ a[k] = a[less];
+ a[less] = ak;
+ }
+ less++;
+ } else { // ak > pivot1
+ /*
+ * We know that pivot1 == a[e3] == pivot2. Thus, we know
+ * that great will still be >= k when the following loop
+ * terminates, even though we don't test for it explicitly.
+ * In other words, a[e3] acts as a sentinel for great.
+ */
+ while (a[great] > pivot1) {
+ great--;
+ }
+ if (a[great] < pivot1) {
+ a[k] = a[less];
+ a[less++] = a[great];
+ } else { // a[great] == pivot1
+ a[k] = pivot1;
+ }
+ a[great--] = ak;
+ }
+ }
+ }
+
+ // Swap pivots into their final positions
+ a[left] = a[less - 1]; a[less - 1] = pivot1;
+ a[right] = a[great + 1]; a[great + 1] = pivot2;
+
+ // Sort left and right parts recursively, excluding known pivot values
+ doSort(a, left, less - 2);
+ doSort(a, great + 2, right);
+
+ /*
+ * If pivot1 == pivot2, all elements from center
+ * part are equal and, therefore, already sorted
+ */
+ if (!pivotsDiffer) {
+ return;
+ }
+
+ /*
+ * If center part is too large (comprises > 2/3 of
+ * the array), swap internal pivot values to ends
+ */
+ if (less < e1 && e5 < great) {
+ while (a[less] == pivot1) {
+ less++;
+ }
+ while (a[great] == pivot2) {
+ great--;
+ }
+
+ /*
+ * Partitioning:
+ *
+ * -------------------------------------------------------------
+ * [ == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 ]
+ * -------------------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (*, less) == pivot1
+ * pivot1 < all in [less, k) < pivot2
+ * all in (great, *) == pivot2
+ *
+ * Pointer k is the first index of ?-part
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ byte ak = a[k];
+ if (ak == pivot2) {
+ while (a[great] == pivot2) {
+ if (k == great--) {
+ break outer;
+ }
+ }
+ if (a[great] == pivot1) {
+ a[k] = a[less];
+ a[less++] = pivot1;
+ } else { // pivot1 < a[great] < pivot2
+ a[k] = a[great];
+ }
+ a[great--] = pivot2;
+ } else if (ak == pivot1) {
+ a[k] = a[less];
+ a[less++] = pivot1;
+ }
+ }
+ }
+
+ // Sort center part recursively, excluding known pivot values
+ doSort(a, less, great); }
+
+ /**
+ * Sorts the specified array into ascending numerical order.
+ *
+ * <p>The {@code <} relation does not provide a total order on all float
+ * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
+ * value compares neither less than, greater than, nor equal to any value,
+ * even itself. This method uses the total order imposed by the method
+ * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
+ * {@code 0.0f} and {@code Float.NaN} is considered greater than any
+ * other value and all {@code Float.NaN} values are considered equal.
+ *
+ * @param a the array to be sorted
+ */
+ public static void sort(float[] a) {
+ sortNegZeroAndNaN(a, 0, a.length - 1);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * the range to be sorted is empty.
+ *
+ * <p>The {@code <} relation does not provide a total order on all float
+ * values: {@code -0.0f == 0.0f} is {@code true} and a {@code Float.NaN}
+ * value compares neither less than, greater than, nor equal to any value,
+ * even itself. This method uses the total order imposed by the method
+ * {@link Float#compareTo}: {@code -0.0f} is treated as less than value
+ * {@code 0.0f} and {@code Float.NaN} is considered greater than any
+ * other value and all {@code Float.NaN} values are considered equal.
+ *
+ * @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 {@code fromIndex > toIndex}
+ * @throws ArrayIndexOutOfBoundsException
+ * if {@code fromIndex < 0} or {@code toIndex > a.length}
+ */
+ public static void sort(float[] a, int fromIndex, int toIndex) {
+ rangeCheck(a.length, fromIndex, toIndex);
+ sortNegZeroAndNaN(a, fromIndex, toIndex - 1);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. The
+ * sort is done in three phases to avoid expensive comparisons in the
+ * inner loop. The comparisons would be expensive due to anomalies
+ * associated with negative zero {@code -0.0f} and {@code Float.NaN}.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void sortNegZeroAndNaN(float[] a, int left, int right) {
+ /*
+ * Phase 1: Count negative zeros and move NaNs to end of array
+ */
+ final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);
+ int numNegativeZeros = 0;
+ int n = right;
+
+ for (int k = left; k <= n; k++) {
+ float ak = a[k];
+ if (ak == 0.0f && NEGATIVE_ZERO == Float.floatToIntBits(ak)) {
+ a[k] = 0.0f;
+ numNegativeZeros++;
+ } else if (ak != ak) { // i.e., ak is NaN
+ a[k--] = a[n];
+ a[n--] = Float.NaN;
+ }
+ }
+
+ /*
+ * Phase 2: Sort everything except NaNs (which are already in place)
+ */
+ doSort(a, left, n);
+
+ /*
+ * Phase 3: Turn positive zeros back into negative zeros as appropriate
+ */
+ if (numNegativeZeros == 0) {
+ return;
+ }
+
+ // Find first zero element
+ int zeroIndex = findAnyZero(a, left, n);
+
+ for (int i = zeroIndex - 1; i >= left && a[i] == 0.0f; i--) {
+ zeroIndex = i;
+ }
+
+ // Turn the right number of positive zeros back into negative zeros
+ for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; i++) {
+ a[i] = -0.0f;
+ }
+ }
+
+ /**
+ * Returns the index of some zero element in the specified range via
+ * binary search. The range is assumed to be sorted, and must contain
+ * at least one zero.
+ *
+ * @param a the array to be searched
+ * @param low the index of the first element, inclusive, to be searched
+ * @param high the index of the last element, inclusive, to be searched
+ */
+ private static int findAnyZero(float[] a, int low, int high) {
+ while (true) {
+ int middle = (low + high) >>> 1;
+ float middleValue = a[middle];
+
+ if (middleValue < 0.0f) {
+ low = middle + 1;
+ } else if (middleValue > 0.0f) {
+ high = middle - 1;
+ } else { // middleValue == 0.0f
+ return middle;
+ }
+ }
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. This
+ * method differs from the public {@code sort} method in three ways:
+ * {@code right} index is inclusive, it does no range checking on
+ * {@code left} or {@code right}, and it does not handle negative
+ * zeros or NaNs in the array.
+ *
+ * @param a the array to be sorted, which must not contain -0.0f or NaN
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void doSort(float[] a, int left, int right) {
+ // Use insertion sort on tiny arrays
+ if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
+ for (int k = left + 1; k <= right; k++) {
+ float ak = a[k];
+ int j;
+ for (j = k - 1; j >= left && ak < a[j]; j--) {
+ a[j + 1] = a[j];
+ }
+ a[j + 1] = ak;
+ }
+ } else { // Use Dual-Pivot Quicksort on large arrays
+ dualPivotQuicksort(a, left, right);
+ }
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void dualPivotQuicksort(float[] a, int left, int right) {
+ // Compute indices of five evenly spaced elements
+ int sixth = (right - left + 1) / 6;
+ int e1 = left + sixth;
+ int e5 = right - sixth;
+ int e3 = (left + right) >>> 1; // The midpoint
+ int e4 = e3 + sixth;
+ int e2 = e3 - sixth;
+
+ // Sort these elements using a 5-element sorting network
+ float ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+
+ if (ae1 > ae2) { float t = ae1; ae1 = ae2; ae2 = t; }
+ if (ae4 > ae5) { float t = ae4; ae4 = ae5; ae5 = t; }
+ if (ae1 > ae3) { float t = ae1; ae1 = ae3; ae3 = t; }
+ if (ae2 > ae3) { float t = ae2; ae2 = ae3; ae3 = t; }
+ if (ae1 > ae4) { float t = ae1; ae1 = ae4; ae4 = t; }
+ if (ae3 > ae4) { float t = ae3; ae3 = ae4; ae4 = t; }
+ if (ae2 > ae5) { float t = ae2; ae2 = ae5; ae5 = t; }
+ if (ae2 > ae3) { float t = ae2; ae2 = ae3; ae3 = t; }
+ if (ae4 > ae5) { float t = ae4; ae4 = ae5; ae5 = t; }
+
+ a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+
+ /*
+ * Use the second and fourth of the five sorted elements as pivots.
+ * These values are inexpensive approximations of the first and
+ * second terciles of the array. Note that pivot1 <= pivot2.
+ *
+ * The pivots are stored in local variables, and the first and
+ * the last of the sorted elements are moved to the locations
+ * formerly occupied by the pivots. When partitioning is complete,
+ * the pivots are swapped back into their final positions, and
+ * excluded from subsequent sorting.
+ */
+ float pivot1 = ae2; a[e2] = a[left];
+ float pivot2 = ae4; a[e4] = a[right];
+
+ // Pointers
+ int less = left + 1; // The index of first element of center part
+ int great = right - 1; // The index before first element of right part
+
+ boolean pivotsDiffer = pivot1 != pivot2;
+
+ if (pivotsDiffer) {
+ /*
+ * Partitioning:
+ *
+ * left part center part right part
+ * ------------------------------------------------------------
+ * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
+ * ------------------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (left, less) < pivot1
+ * pivot1 <= all in [less, k) <= pivot2
+ * all in (great, right) > pivot2
+ *
+ * Pointer k is the first index of ?-part
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ float ak = a[k];
+ if (ak < pivot1) {
+ if (k != less) {
+ a[k] = a[less];
+ a[less] = ak;
+ }
+ less++;
+ } else if (ak > pivot2) {
+ while (a[great] > pivot2) {
+ if (great-- == k) {
+ break outer;
+ }
+ }
+ if (a[great] < pivot1) {
+ a[k] = a[less];
+ a[less++] = a[great];
+ } else { // pivot1 <= a[great] <= pivot2
+ a[k] = a[great];
+ }
+ a[great--] = ak;
+ }
+ }
+ } else { // Pivots are equal
+ /*
+ * Partition degenerates to the traditional 3-way
+ * (or "Dutch National Flag") partition:
+ *
+ * left part center part right part
+ * -------------------------------------------------
+ * [ < pivot | == pivot | ? | > pivot ]
+ * -------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (left, less) < pivot
+ * all in [less, k) == pivot
+ * all in (great, right) > pivot
+ *
+ * Pointer k is the first index of ?-part
+ */
+ for (int k = less; k <= great; k++) {
+ float ak = a[k];
+ if (ak == pivot1) {
+ continue;
+ }
+ if (ak < pivot1) {
+ if (k != less) {
+ a[k] = a[less];
+ a[less] = ak;
+ }
+ less++;
+ } else { // ak > pivot1
+ /*
+ * We know that pivot1 == a[e3] == pivot2. Thus, we know
+ * that great will still be >= k when the following loop
+ * terminates, even though we don't test for it explicitly.
+ * In other words, a[e3] acts as a sentinel for great.
+ */
+ while (a[great] > pivot1) {
+ great--;
+ }
+ if (a[great] < pivot1) {
+ a[k] = a[less];
+ a[less++] = a[great];
+ } else { // a[great] == pivot1
+ a[k] = pivot1;
+ }
+ a[great--] = ak;
+ }
+ }
+ }
+
+ // Swap pivots into their final positions
+ a[left] = a[less - 1]; a[less - 1] = pivot1;
+ a[right] = a[great + 1]; a[great + 1] = pivot2;
+
+ // Sort left and right parts recursively, excluding known pivot values
+ doSort(a, left, less - 2);
+ doSort(a, great + 2, right);
+
+ /*
+ * If pivot1 == pivot2, all elements from center
+ * part are equal and, therefore, already sorted
+ */
+ if (!pivotsDiffer) {
+ return;
+ }
+
+ /*
+ * If center part is too large (comprises > 2/3 of
+ * the array), swap internal pivot values to ends
+ */
+ if (less < e1 && e5 < great) {
+ while (a[less] == pivot1) {
+ less++;
+ }
+ while (a[great] == pivot2) {
+ great--;
+ }
+
+ /*
+ * Partitioning:
+ *
+ * -------------------------------------------------------------
+ * [ == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 ]
+ * -------------------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (*, less) == pivot1
+ * pivot1 < all in [less, k) < pivot2
+ * all in (great, *) == pivot2
+ *
+ * Pointer k is the first index of ?-part
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ float ak = a[k];
+ if (ak == pivot2) {
+ while (a[great] == pivot2) {
+ if (k == great--) {
+ break outer;
+ }
+ }
+ if (a[great] == pivot1) {
+ a[k] = a[less];
+ a[less++] = pivot1;
+ } else { // pivot1 < a[great] < pivot2
+ a[k] = a[great];
+ }
+ a[great--] = pivot2;
+ } else if (ak == pivot1) {
+ a[k] = a[less];
+ a[less++] = pivot1;
+ }
+ }
+ }
+
+ // Sort center part recursively, excluding known pivot values
+ doSort(a, less, great); }
+
+ /**
+ * Sorts the specified array into ascending numerical order.
+ *
+ * <p>The {@code <} relation does not provide a total order on all double
+ * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
+ * value compares neither less than, greater than, nor equal to any value,
+ * even itself. This method uses the total order imposed by the method
+ * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
+ * {@code 0.0d} and {@code Double.NaN} is considered greater than any
+ * other value and all {@code Double.NaN} values are considered equal.
+ *
+ * @param a the array to be sorted
+ */
+ public static void sort(double[] a) {
+ sortNegZeroAndNaN(a, 0, a.length - 1);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. The range
+ * to be sorted extends from the index {@code fromIndex}, inclusive, to
+ * the index {@code toIndex}, exclusive. If {@code fromIndex == toIndex},
+ * the range to be sorted is empty.
+ *
+ * <p>The {@code <} relation does not provide a total order on all double
+ * values: {@code -0.0d == 0.0d} is {@code true} and a {@code Double.NaN}
+ * value compares neither less than, greater than, nor equal to any value,
+ * even itself. This method uses the total order imposed by the method
+ * {@link Double#compareTo}: {@code -0.0d} is treated as less than value
+ * {@code 0.0d} and {@code Double.NaN} is considered greater than any
+ * other value and all {@code Double.NaN} values are considered equal.
+ *
+ * @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 {@code fromIndex > toIndex}
+ * @throws ArrayIndexOutOfBoundsException
+ * if {@code fromIndex < 0} or {@code toIndex > a.length}
+ */
+ public static void sort(double[] a, int fromIndex, int toIndex) {
+ rangeCheck(a.length, fromIndex, toIndex);
+ sortNegZeroAndNaN(a, fromIndex, toIndex - 1);
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. The
+ * sort is done in three phases to avoid expensive comparisons in the
+ * inner loop. The comparisons would be expensive due to anomalies
+ * associated with negative zero {@code -0.0d} and {@code Double.NaN}.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void sortNegZeroAndNaN(double[] a, int left, int right) {
+ /*
+ * Phase 1: Count negative zeros and move NaNs to end of array
+ */
+ final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);
+ int numNegativeZeros = 0;
+ int n = right;
+
+ for (int k = left; k <= n; k++) {
+ double ak = a[k];
+ if (ak == 0.0d && NEGATIVE_ZERO == Double.doubleToLongBits(ak)) {
+ a[k] = 0.0d;
+ numNegativeZeros++;
+ } else if (ak != ak) { // i.e., ak is NaN
+ a[k--] = a[n];
+ a[n--] = Double.NaN;
+ }
+ }
+
+ /*
+ * Phase 2: Sort everything except NaNs (which are already in place)
+ */
+ doSort(a, left, n);
+
+ /*
+ * Phase 3: Turn positive zeros back into negative zeros as appropriate
+ */
+ if (numNegativeZeros == 0) {
+ return;
+ }
+
+ // Find first zero element
+ int zeroIndex = findAnyZero(a, left, n);
+
+ for (int i = zeroIndex - 1; i >= left && a[i] == 0.0d; i--) {
+ zeroIndex = i;
+ }
+
+ // Turn the right number of positive zeros back into negative zeros
+ for (int i = zeroIndex, m = zeroIndex + numNegativeZeros; i < m; i++) {
+ a[i] = -0.0d;
+ }
+ }
+
+ /**
+ * Returns the index of some zero element in the specified range via
+ * binary search. The range is assumed to be sorted, and must contain
+ * at least one zero.
+ *
+ * @param a the array to be searched
+ * @param low the index of the first element, inclusive, to be searched
+ * @param high the index of the last element, inclusive, to be searched
+ */
+ private static int findAnyZero(double[] a, int low, int high) {
+ while (true) {
+ int middle = (low + high) >>> 1;
+ double middleValue = a[middle];
+
+ if (middleValue < 0.0d) {
+ low = middle + 1;
+ } else if (middleValue > 0.0d) {
+ high = middle - 1;
+ } else { // middleValue == 0.0d
+ return middle;
+ }
+ }
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order. This
+ * method differs from the public {@code sort} method in three ways:
+ * {@code right} index is inclusive, it does no range checking on
+ * {@code left} or {@code right}, and it does not handle negative
+ * zeros or NaNs in the array.
+ *
+ * @param a the array to be sorted, which must not contain -0.0d and NaN
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void doSort(double[] a, int left, int right) {
+ // Use insertion sort on tiny arrays
+ if (right - left + 1 < INSERTION_SORT_THRESHOLD) {
+ for (int k = left + 1; k <= right; k++) {
+ double ak = a[k];
+ int j;
+ for (j = k - 1; j >= left && ak < a[j]; j--) {
+ a[j + 1] = a[j];
+ }
+ a[j + 1] = ak;
+ }
+ } else { // Use Dual-Pivot Quicksort on large arrays
+ dualPivotQuicksort(a, left, right);
+ }
+ }
+
+ /**
+ * Sorts the specified range of the array into ascending order by the
+ * Dual-Pivot Quicksort algorithm.
+ *
+ * @param a the array to be sorted
+ * @param left the index of the first element, inclusive, to be sorted
+ * @param right the index of the last element, inclusive, to be sorted
+ */
+ private static void dualPivotQuicksort(double[] a, int left, int right) {
+ // Compute indices of five evenly spaced elements
+ int sixth = (right - left + 1) / 6;
+ int e1 = left + sixth;
+ int e5 = right - sixth;
+ int e3 = (left + right) >>> 1; // The midpoint
+ int e4 = e3 + sixth;
+ int e2 = e3 - sixth;
+
+ // Sort these elements using a 5-element sorting network
+ double ae1 = a[e1], ae2 = a[e2], ae3 = a[e3], ae4 = a[e4], ae5 = a[e5];
+
+ if (ae1 > ae2) { double t = ae1; ae1 = ae2; ae2 = t; }
+ if (ae4 > ae5) { double t = ae4; ae4 = ae5; ae5 = t; }
+ if (ae1 > ae3) { double t = ae1; ae1 = ae3; ae3 = t; }
+ if (ae2 > ae3) { double t = ae2; ae2 = ae3; ae3 = t; }
+ if (ae1 > ae4) { double t = ae1; ae1 = ae4; ae4 = t; }
+ if (ae3 > ae4) { double t = ae3; ae3 = ae4; ae4 = t; }
+ if (ae2 > ae5) { double t = ae2; ae2 = ae5; ae5 = t; }
+ if (ae2 > ae3) { double t = ae2; ae2 = ae3; ae3 = t; }
+ if (ae4 > ae5) { double t = ae4; ae4 = ae5; ae5 = t; }
+
+ a[e1] = ae1; a[e3] = ae3; a[e5] = ae5;
+
+ /*
+ * Use the second and fourth of the five sorted elements as pivots.
+ * These values are inexpensive approximations of the first and
+ * second terciles of the array. Note that pivot1 <= pivot2.
+ *
+ * The pivots are stored in local variables, and the first and
+ * the last of the sorted elements are moved to the locations
+ * formerly occupied by the pivots. When partitioning is complete,
+ * the pivots are swapped back into their final positions, and
+ * excluded from subsequent sorting.
+ */
+ double pivot1 = ae2; a[e2] = a[left];
+ double pivot2 = ae4; a[e4] = a[right];
+
+ // Pointers
+ int less = left + 1; // The index of first element of center part
+ int great = right - 1; // The index before first element of right part
+
+ boolean pivotsDiffer = pivot1 != pivot2;
+
+ if (pivotsDiffer) {
+ /*
+ * Partitioning:
+ *
+ * left part center part right part
+ * ------------------------------------------------------------
+ * [ < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 ]
+ * ------------------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (left, less) < pivot1
+ * pivot1 <= all in [less, k) <= pivot2
+ * all in (great, right) > pivot2
+ *
+ * Pointer k is the first index of ?-part
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ double ak = a[k];
+ if (ak < pivot1) {
+ if (k != less) {
+ a[k] = a[less];
+ a[less] = ak;
+ }
+ less++;
+ } else if (ak > pivot2) {
+ while (a[great] > pivot2) {
+ if (great-- == k) {
+ break outer;
+ }
+ }
+ if (a[great] < pivot1) {
+ a[k] = a[less];
+ a[less++] = a[great];
+ } else { // pivot1 <= a[great] <= pivot2
+ a[k] = a[great];
+ }
+ a[great--] = ak;
+ }
+ }
+ } else { // Pivots are equal
+ /*
+ * Partition degenerates to the traditional 3-way
+ * (or "Dutch National Flag") partition:
+ *
+ * left part center part right part
+ * -------------------------------------------------
+ * [ < pivot | == pivot | ? | > pivot ]
+ * -------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (left, less) < pivot
+ * all in [less, k) == pivot
+ * all in (great, right) > pivot
+ *
+ * Pointer k is the first index of ?-part
+ */
+ for (int k = less; k <= great; k++) {
+ double ak = a[k];
+ if (ak == pivot1) {
+ continue;
+ }
+ if (ak < pivot1) {
+ if (k != less) {
+ a[k] = a[less];
+ a[less] = ak;
+ }
+ less++;
+ } else { // ak > pivot1
+ /*
+ * We know that pivot1 == a[e3] == pivot2. Thus, we know
+ * that great will still be >= k when the following loop
+ * terminates, even though we don't test for it explicitly.
+ * In other words, a[e3] acts as a sentinel for great.
+ */
+ while (a[great] > pivot1) {
+ great--;
+ }
+ if (a[great] < pivot1) {
+ a[k] = a[less];
+ a[less++] = a[great];
+ } else { // a[great] == pivot1
+ a[k] = pivot1;
+ }
+ a[great--] = ak;
+ }
+ }
+ }
+
+ // Swap pivots into their final positions
+ a[left] = a[less - 1]; a[less - 1] = pivot1;
+ a[right] = a[great + 1]; a[great + 1] = pivot2;
+
+ // Sort left and right parts recursively, excluding known pivot values
+ doSort(a, left, less - 2);
+ doSort(a, great + 2, right);
+
+ /*
+ * If pivot1 == pivot2, all elements from center
+ * part are equal and, therefore, already sorted
+ */
+ if (!pivotsDiffer) {
+ return;
+ }
+
+ /*
+ * If center part is too large (comprises > 2/3 of
+ * the array), swap internal pivot values to ends
+ */
+ if (less < e1 && e5 < great) {
+ while (a[less] == pivot1) {
+ less++;
+ }
+ while (a[great] == pivot2) {
+ great--;
+ }
+
+ /*
+ * Partitioning:
+ *
+ * -------------------------------------------------------------
+ * [ == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 ]
+ * -------------------------------------------------------------
+ * ^ ^ ^
+ * | | |
+ * less k great
+ *
+ * Invariants:
+ *
+ * all in (*, less) == pivot1
+ * pivot1 < all in [less, k) < pivot2
+ * all in (great, *) == pivot2
+ *
+ * Pointer k is the first index of ?-part
+ */
+ outer:
+ for (int k = less; k <= great; k++) {
+ double ak = a[k];
+ if (ak == pivot2) {
+ while (a[great] == pivot2) {
+ if (k == great--) {
+ break outer;
+ }
+ }
+ if (a[great] == pivot1) {
+ a[k] = a[less];
+ a[less++] = pivot1;
+ } else { // pivot1 < a[great] < pivot2
+ a[k] = a[great];
+ }
+ a[great--] = pivot2;
+ } else if (ak == pivot1) {
+ a[k] = a[less];
+ a[less++] = pivot1;
+ }
+ }
+ }
+
+ // Sort center part recursively, excluding known pivot values
+ doSort(a, less, great); }
+
+ /**
+ * Checks that {@code fromIndex} and {@code toIndex} are in
+ * the range and throws an appropriate exception, if they aren't.
+ */
+ private static void rangeCheck(int length, int fromIndex, int toIndex) {
+ if (fromIndex > toIndex) {
+ throw new IllegalArgumentException(
+ "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
+ }
+ if (fromIndex < 0) {
+ throw new ArrayIndexOutOfBoundsException(fromIndex);
+ }
+ if (toIndex > length) {
+ throw new ArrayIndexOutOfBoundsException(toIndex);
+ }
+ }
+}
diff --git a/libcore/luni/src/test/java/tests/api/java/util/ArraysTest.java b/libcore/luni/src/test/java/tests/api/java/util/ArraysTest.java
index ac8263e..1b22dba 100644
--- a/libcore/luni/src/test/java/tests/api/java/util/ArraysTest.java
+++ b/libcore/luni/src/test/java/tests/api/java/util/ArraysTest.java
@@ -17,19 +17,18 @@
package tests.api.java.util;
import dalvik.annotation.TestTargetNew;
-import dalvik.annotation.TestTargets;
import dalvik.annotation.TestLevel;
-import dalvik.annotation.TestTargetClass;
+import dalvik.annotation.TestTargetClass;
-import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
+import java.util.Random;
import tests.support.Support_UnmodifiableCollectionTest;
-@TestTargetClass(Arrays.class)
+@TestTargetClass(Arrays.class)
public class ArraysTest extends junit.framework.TestCase {
public static class ReversedIntegerComparator implements Comparator {
@@ -63,7 +62,7 @@
Object[] objectArray;
short[] shortArray;
-
+
/**
* @tests java.util.Arrays#asList(java.lang.Object[])
*/
@@ -487,21 +486,21 @@
assertTrue("Filled elements not in range", !(d[i] == val));
for (int i = 400; i < d.length; i++)
assertTrue("Failed to fill short array correctly", d[i] == val);
-
+
try {
Arrays.fill(d, 10, 0, val);
fail("IllegalArgumentException expected");
} catch (IllegalArgumentException e) {
//expected
}
-
+
try {
Arrays.fill(d, -10, 0, val);
fail("ArrayIndexOutOfBoundsException expected");
} catch (ArrayIndexOutOfBoundsException e) {
//expected
}
-
+
try {
Arrays.fill(d, 10, d.length+1, val);
fail("ArrayIndexOutOfBoundsException expected");
@@ -546,21 +545,21 @@
assertTrue("Filled elements not in range", !(d[i] == val));
for (int i = 400; i < d.length; i++)
assertTrue("Failed to fill char array correctly", d[i] == val);
-
+
try {
Arrays.fill(d, 10, 0, val);
fail("IllegalArgumentException expected");
} catch (IllegalArgumentException e) {
//expected
}
-
+
try {
Arrays.fill(d, -10, 0, val);
fail("ArrayIndexOutOfBoundsException expected");
} catch (ArrayIndexOutOfBoundsException e) {
//expected
}
-
+
try {
Arrays.fill(d, 10, d.length+1, val);
fail("ArrayIndexOutOfBoundsException expected");
@@ -606,21 +605,21 @@
assertTrue("Filled elements not in range", !(d[i] == val));
for (int i = 400; i < d.length; i++)
assertTrue("Failed to fill int array correctly", d[i] == val);
-
+
try {
Arrays.fill(d, 10, 0, val);
fail("IllegalArgumentException expected");
} catch (IllegalArgumentException e) {
//expected
}
-
+
try {
Arrays.fill(d, -10, 0, val);
fail("ArrayIndexOutOfBoundsException expected");
} catch (ArrayIndexOutOfBoundsException e) {
//expected
}
-
+
try {
Arrays.fill(d, 10, d.length+1, val);
fail("ArrayIndexOutOfBoundsException expected");
@@ -666,21 +665,21 @@
for (int i = 400; i < d.length; i++)
assertTrue("Failed to fill long array correctly",
d[i] == Long.MAX_VALUE);
-
+
try {
Arrays.fill(d, 10, 0, Long.MIN_VALUE);
fail("IllegalArgumentException expected");
} catch (IllegalArgumentException e) {
//expected
}
-
+
try {
Arrays.fill(d, -10, 0, Long.MAX_VALUE);
fail("ArrayIndexOutOfBoundsException expected");
} catch (ArrayIndexOutOfBoundsException e) {
//expected
}
-
+
try {
Arrays.fill(d, 10, d.length+1, Long.MAX_VALUE);
fail("ArrayIndexOutOfBoundsException expected");
@@ -725,21 +724,21 @@
assertTrue("Filled elements not in range", !(d[i] == val));
for (int i = 400; i < d.length; i++)
assertTrue("Failed to fill float array correctly", d[i] == val);
-
+
try {
Arrays.fill(d, 10, 0, val);
fail("IllegalArgumentException expected");
} catch (IllegalArgumentException e) {
//expected
}
-
+
try {
Arrays.fill(d, -10, 0, val);
fail("ArrayIndexOutOfBoundsException expected");
} catch (ArrayIndexOutOfBoundsException e) {
//expected
}
-
+
try {
Arrays.fill(d, 10, d.length+1, val);
fail("ArrayIndexOutOfBoundsException expected");
@@ -786,21 +785,21 @@
assertTrue("Filled elements not in range", !(d[i] == val));
for (int i = 400; i < d.length; i++)
assertTrue("Failed to fill double array correctly", d[i] == val);
-
+
try {
Arrays.fill(d, 10, 0, val);
fail("IllegalArgumentException expected");
} catch (IllegalArgumentException e) {
//expected
}
-
+
try {
Arrays.fill(d, -10, 0, val);
fail("ArrayIndexOutOfBoundsException expected");
} catch (ArrayIndexOutOfBoundsException e) {
//expected
}
-
+
try {
Arrays.fill(d, 10, d.length+1, val);
fail("ArrayIndexOutOfBoundsException expected");
@@ -846,21 +845,21 @@
assertTrue("Filled elements not in range", !(d[i] == val));
for (int i = 400; i < d.length; i++)
assertTrue("Failed to fill boolean array correctly", d[i] == val);
-
+
try {
Arrays.fill(d, 10, 0, val);
fail("IllegalArgumentException expected");
} catch (IllegalArgumentException e) {
//expected
}
-
+
try {
Arrays.fill(d, -10, 0, val);
fail("ArrayIndexOutOfBoundsException expected");
} catch (ArrayIndexOutOfBoundsException e) {
//expected
}
-
+
try {
Arrays.fill(d, 10, d.length+1, val);
fail("ArrayIndexOutOfBoundsException expected");
@@ -913,21 +912,21 @@
for (int i = 400; i < d.length; i++)
assertNull("Failed to fill Object array correctly with nulls",
d[i]);
-
+
try {
Arrays.fill(d, 10, 0, val);
fail("IllegalArgumentException expected");
} catch (IllegalArgumentException e) {
//expected
}
-
+
try {
Arrays.fill(d, -10, 0, val);
fail("ArrayIndexOutOfBoundsException expected");
} catch (ArrayIndexOutOfBoundsException e) {
//expected
}
-
+
try {
Arrays.fill(d, 10, d.length+1, val);
fail("ArrayIndexOutOfBoundsException expected");
@@ -1212,7 +1211,7 @@
fail("ArrayIndexOutOfBoundsException expected (2)");
} catch (ArrayIndexOutOfBoundsException ignore) {
}
-
+
//exception order testing
try {
Arrays.sort(new byte[1], startIndex + 1, startIndex);
@@ -1284,7 +1283,7 @@
fail("ArrayIndexOutOfBoundsException expected (1)");
} catch (ArrayIndexOutOfBoundsException ignore) {
}
-
+
try {
Arrays.sort(reversedArray, startIndex, reversedArray.length + 1);
fail("ArrayIndexOutOfBoundsException expected (2)");
@@ -1391,7 +1390,7 @@
fail("ArrayIndexOutOfBoundsException expected (2)");
} catch (ArrayIndexOutOfBoundsException ignore) {
}
-
+
//exception order testing
try {
Arrays.sort(new double[1], startIndex + 1, startIndex);
@@ -1486,13 +1485,13 @@
fail("ArrayIndexOutOfBoundsException expected (1)");
} catch (ArrayIndexOutOfBoundsException ignore) {
}
-
+
try {
Arrays.sort(reversedArray, startIndex, reversedArray.length + 1);
fail("ArrayIndexOutOfBoundsException expected (2)");
} catch (ArrayIndexOutOfBoundsException ignore) {
}
-
+
//exception order testing
try {
Arrays.sort(new float[1], startIndex + 1, startIndex);
@@ -1563,13 +1562,13 @@
fail("ArrayIndexOutOfBoundsException expected (1)");
} catch (ArrayIndexOutOfBoundsException ignore) {
}
-
+
try {
Arrays.sort(reversedArray, startIndex, reversedArray.length + 1);
fail("ArrayIndexOutOfBoundsException expected (2)");
} catch (ArrayIndexOutOfBoundsException ignore) {
}
-
+
//exception order testing
try {
Arrays.sort(new int[1], startIndex + 1, startIndex);
@@ -1647,7 +1646,7 @@
fail("ArrayIndexOutOfBoundsException expected (2)");
} catch (ArrayIndexOutOfBoundsException ignore) {
}
-
+
//exception order testing
try {
Arrays.sort(new long[1], startIndex + 1, startIndex);
@@ -1677,7 +1676,7 @@
Arrays.fill(reversedArray, 0, reversedArray.length/2, "String");
Arrays.fill(reversedArray, reversedArray.length/2, reversedArray.length, new Integer(1));
-
+
try {
Arrays.sort(reversedArray);
fail("ClassCastException expected");
@@ -1724,7 +1723,7 @@
fail("IllegalArgumentException expected");
} catch (IllegalArgumentException ignore) {
}
-
+
try {
Arrays.sort(reversedArray, -1, startIndex);
fail("ArrayIndexOutOfBoundsException expected (1)");
@@ -1736,7 +1735,7 @@
fail("ArrayIndexOutOfBoundsException expected (2)");
} catch (ArrayIndexOutOfBoundsException ignore) {
}
-
+
//exception order testing
try {
Arrays.sort(new Object[1], startIndex + 1, startIndex);
@@ -1746,7 +1745,7 @@
Arrays.fill(reversedArray, 0, reversedArray.length/2, "String");
Arrays.fill(reversedArray, reversedArray.length/2, reversedArray.length, new Integer(1));
-
+
try {
Arrays.sort(reversedArray, reversedArray.length/4, 3*reversedArray.length/4);
fail("ClassCastException expected");
@@ -1790,7 +1789,7 @@
Arrays.fill(originalArray, 0, originalArray.length/2, "String");
Arrays.fill(originalArray, originalArray.length/2, originalArray.length, new Integer(1));
-
+
try {
Arrays.sort(originalArray, startIndex, endIndex, comp);
fail("ClassCastException expected");
@@ -1799,21 +1798,21 @@
}
Arrays.sort(originalArray, endIndex, originalArray.length, comp);
-
+
try {
Arrays.sort(originalArray, endIndex, originalArray.length + 1, comp);
fail("ArrayIndexOutOfBoundsException expected");
} catch(ArrayIndexOutOfBoundsException e) {
//expected
}
-
+
try {
Arrays.sort(originalArray, -1, startIndex, comp);
fail("ArrayIndexOutOfBoundsException expected");
} catch(ArrayIndexOutOfBoundsException e) {
//expected
}
-
+
try {
Arrays.sort(originalArray, originalArray.length, endIndex, comp);
fail("IllegalArgumentException expected");
@@ -1844,7 +1843,7 @@
Arrays.fill(objectArray, 0, objectArray.length/2, "String");
Arrays.fill(objectArray, objectArray.length/2, objectArray.length, new Integer(1));
-
+
try {
Arrays.sort(objectArray, comp);
fail("ClassCastException expected");
@@ -1902,26 +1901,26 @@
for (int counter = endIndex; counter < arraySize; counter++)
assertTrue("Array modified outside of bounds",
reversedArray[counter] == originalReversedArray[counter]);
-
+
//exception testing
try {
Arrays.sort(reversedArray, startIndex + 1, startIndex);
fail("IllegalArgumentException expected");
} catch (IllegalArgumentException ignore) {
}
-
+
try {
Arrays.sort(reversedArray, -1, startIndex);
fail("ArrayIndexOutOfBoundsException expected (1)");
} catch (ArrayIndexOutOfBoundsException ignore) {
}
-
+
try {
Arrays.sort(reversedArray, startIndex, reversedArray.length + 1);
fail("ArrayIndexOutOfBoundsException expected (2)");
} catch (ArrayIndexOutOfBoundsException ignore) {
}
-
+
//exception order testing
try {
Arrays.sort(new short[1], startIndex + 1, startIndex);
@@ -2144,9 +2143,452 @@
// Expected
}
}
-
+
+ // Lenghts of arrays to test in test_sort;
+ private static final int[] LENGTHS = { 0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000 };
+
/**
- * @tests java.util.Arrays#deepEquals(Object[], Object[])
+ * @tests java.util.Arrays#sort()
+ */
+ @TestTargetNew(
+ level = TestLevel.PARTIAL_COMPLETE,
+ notes = "Agressive test of the sort methods for *all* primitive array types",
+ method = "sort"
+ )
+ public void test_sort() {
+ for (int len : LENGTHS) {
+ PrimitiveTypeArrayBuilder.reset();
+ int[] golden = new int[len];
+ for (int m = 1; m < 2 * len; m *= 2) {
+ for (PrimitiveTypeArrayBuilder builder : PrimitiveTypeArrayBuilder.values()) {
+ builder.build(golden, m);
+ int[] test = golden.clone();
+
+ for (PrimitiveTypeConverter converter : PrimitiveTypeConverter.values()) {
+ Object convertedGolden = converter.convert(golden);
+ Object convertedTest = converter.convert(test);
+ sort(convertedTest);
+ checkSorted(convertedTest);
+ assertEquals(checkSum(convertedGolden), checkSum(convertedTest));
+ }
+ }
+ }
+ }
+ }
+
+ private void sort(Object array) {
+ if (array instanceof int[]) {
+ Arrays.sort((int[]) array);
+ }
+ else if (array instanceof long[]) {
+ Arrays.sort((long[]) array);
+ } else if (array instanceof short[]) {
+ Arrays.sort((short[]) array);
+ } else if (array instanceof byte[]) {
+ Arrays.sort((byte[]) array);
+ } else if (array instanceof char[]) {
+ Arrays.sort((char[]) array);
+ } else if (array instanceof float[]) {
+ Arrays.sort((float[]) array);
+ } else if (array instanceof double[]) {
+ Arrays.sort((double[]) array);
+ } else {
+ fail("Unknow type of array: " + array.getClass());
+ }
+ }
+
+ private void checkSorted(Object array) {
+ if (array instanceof int[]) {
+ checkSorted((int[]) array);
+ } else if (array instanceof long[]) {
+ checkSorted((long[]) array);
+ } else if (array instanceof short[]) {
+ checkSorted((short[]) array);
+ } else if (array instanceof byte[]) {
+ checkSorted((byte[]) array);
+ } else if (array instanceof char[]) {
+ checkSorted((char[]) array);
+ } else if (array instanceof float[]) {
+ checkSorted((float[]) array);
+ } else if (array instanceof double[]) {
+ checkSorted((double[]) array);
+ } else {
+ fail("Unknow type of array: " + array.getClass());
+ }
+ }
+
+ private void checkSorted(int[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ orderFail(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+ }
+
+ private void checkSorted(long[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ orderFail(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+ }
+
+ private void checkSorted(short[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ orderFail(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+ }
+
+ private void checkSorted(byte[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ orderFail(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+ }
+
+ private void checkSorted(char[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ orderFail(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+ }
+
+ private void checkSorted(float[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ orderFail(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+ }
+
+ private void checkSorted(double[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ orderFail(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+ }
+
+
+ private void orderFail(int index, String value1, String value2) {
+ fail("Array is not sorted at " + index + "-th position: " + value1 + " and " + value2);
+ }
+
+ private int checkSum(Object array) {
+ if (array instanceof int[]) {
+ return checkSum((int[]) array);
+ } else if (array instanceof long[]) {
+ return checkSum((long[]) array);
+ } else if (array instanceof short[]) {
+ return checkSum((short[]) array);
+ } else if (array instanceof byte[]) {
+ return checkSum((byte[]) array);
+ } else if (array instanceof char[]) {
+ return checkSum((char[]) array);
+ } else if (array instanceof float[]) {
+ return checkSum((float[]) array);
+ } else if (array instanceof double[]) {
+ return checkSum((double[]) array);
+ } else {
+ fail("Unknow type of array: " + array.getClass());
+ }
+ throw new AssertionError(); // Needed to shut up compiler
+ }
+
+ private int checkSum(int[] a) {
+ int checkSum = 0;
+
+ for (int e : a) {
+ checkSum ^= e; // xor
+ }
+ return checkSum;
+ }
+
+ private int checkSum(long[] a) {
+ long checkSum = 0;
+
+ for (long e : a) {
+ checkSum ^= e; // xor
+ }
+ return (int) checkSum;
+ }
+
+ private int checkSum(short[] a) {
+ short checkSum = 0;
+
+ for (short e : a) {
+ checkSum ^= e; // xor
+ }
+ return (int) checkSum;
+ }
+
+ private int checkSum(byte[] a) {
+ byte checkSum = 0;
+
+ for (byte e : a) {
+ checkSum ^= e; // xor
+ }
+ return (int) checkSum;
+ }
+
+ private int checkSum(char[] a) {
+ char checkSum = 0;
+
+ for (char e : a) {
+ checkSum ^= e; // xor
+ }
+ return (int) checkSum;
+ }
+
+ private int checkSum(float[] a) {
+ int checkSum = 0;
+
+ for (float e : a) {
+ checkSum ^= (int) e; // xor
+ }
+ return checkSum;
+ }
+
+ private int checkSum(double[] a) {
+ int checkSum = 0;
+
+ for (double e : a) {
+ checkSum ^= (int) e; // xor
+ }
+ return checkSum;
+ }
+
+ private enum PrimitiveTypeArrayBuilder {
+
+ RANDOM {
+ void build(int[] a, int m) {
+ for (int i = 0; i < a.length; i++) {
+ a[i] = ourRandom.nextInt();
+ }
+ }
+ },
+
+ ASCENDING {
+ void build(int[] a, int m) {
+ for (int i = 0; i < a.length; i++) {
+ a[i] = m + i;
+ }
+ }
+ },
+
+ DESCENDING {
+ void build(int[] a, int m) {
+ for (int i = 0; i < a.length; i++) {
+ a[i] = a.length - m - i;
+ }
+ }
+ },
+
+ ALL_EQUAL {
+ void build(int[] a, int m) {
+ for (int i = 0; i < a.length; i++) {
+ a[i] = m;
+ }
+ }
+ },
+
+ SAW {
+ void build(int[] a, int m) {
+ int incCount = 1;
+ int decCount = a.length;
+ int i = 0;
+ int period = m;
+ m--;
+
+ while (true) {
+ for (int k = 1; k <= period; k++) {
+ if (i >= a.length) {
+ return;
+ }
+ a[i++] = incCount++;
+ }
+ period += m;
+
+ for (int k = 1; k <= period; k++) {
+ if (i >= a.length) {
+ return;
+ }
+ a[i++] = decCount--;
+ }
+ period += m;
+ }
+ }
+ },
+
+ REPEATED {
+ void build(int[] a, int m) {
+ for (int i = 0; i < a.length; i++) {
+ a[i] = i % m;
+ }
+ }
+ },
+
+ DUPLICATED {
+ void build(int[] a, int m) {
+ for (int i = 0; i < a.length; i++) {
+ a[i] = ourRandom.nextInt(m);
+ }
+ }
+ },
+
+ ORGAN_PIPES {
+ void build(int[] a, int m) {
+ int middle = a.length / (m + 1);
+
+ for (int i = 0; i < middle; i++) {
+ a[i] = i;
+ }
+ for (int i = middle; i < a.length ; i++) {
+ a[i] = a.length - i - 1;
+ }
+ }
+ },
+
+ STAGGER {
+ void build(int[] a, int m) {
+ for (int i = 0; i < a.length; i++) {
+ a[i] = (i * m + i) % a.length;
+ }
+ }
+ },
+
+ PLATEAU {
+ void build(int[] a, int m) {
+ for (int i = 0; i < a.length; i++) {
+ a[i] = Math.min(i, m);
+ }
+ }
+ },
+
+ SHUFFLE {
+ void build(int[] a, int m) {
+ for (int i = 0; i < a.length; i++) {
+ a[i] = ourRandom.nextBoolean() ? (ourFirst += 2) : (ourSecond += 2);
+ }
+ }
+ };
+
+ abstract void build(int[] a, int m);
+
+ static void reset() {
+ ourRandom = new Random(666);
+ ourFirst = 0;
+ ourSecond = 0;
+ }
+
+ @Override
+ public String toString() {
+ String name = name();
+
+ for (int i = name.length(); i < 12; i++) {
+ name += " " ;
+ }
+ return name;
+ }
+
+ private static int ourFirst;
+ private static int ourSecond;
+ private static Random ourRandom = new Random(666);
+ }
+
+ private enum PrimitiveTypeConverter {
+
+ INT {
+ Object convert(int[] a) {
+ return a;
+ }
+ },
+
+ LONG {
+ Object convert(int[] a) {
+ long[] b = new long[a.length];
+
+ for (int i = 0; i < a.length; i++) {
+ b[i] = (int) a[i];
+ }
+ return b;
+ }
+ },
+
+ BYTE {
+ Object convert(int[] a) {
+ byte[] b = new byte[a.length];
+
+ for (int i = 0; i < a.length; i++) {
+ b[i] = (byte) a[i];
+ }
+ return b;
+ }
+ },
+
+ SHORT {
+ Object convert(int[] a) {
+ short[] b = new short[a.length];
+
+ for (int i = 0; i < a.length; i++) {
+ b[i] = (short) a[i];
+ }
+ return b;
+ }
+ },
+
+ CHAR {
+ Object convert(int[] a) {
+ char[] b = new char[a.length];
+
+ for (int i = 0; i < a.length; i++) {
+ b[i] = (char) a[i];
+ }
+ return b;
+ }
+ },
+
+ FLOAT {
+ Object convert(int[] a) {
+ float[] b = new float[a.length];
+
+ for (int i = 0; i < a.length; i++) {
+ b[i] = (float) a[i];
+ }
+ return b;
+ }
+ },
+
+ DOUBLE {
+ Object convert(int[] a) {
+ double[] b = new double[a.length];
+
+ for (int i = 0; i < a.length; i++) {
+ b[i] = (double) a[i];
+ }
+ return b;
+ }
+ };
+
+ abstract Object convert(int[] a);
+
+ public String toString() {
+ String name = name();
+
+ for (int i = name.length(); i < 9; i++) {
+ name += " " ;
+ }
+ return name;
+ }
+ }
+
+
+ /**
+ * @tests java.util.Arrays#deepEquals(Object[], Object[])
*/
@TestTargetNew(
level = TestLevel.COMPLETE,
@@ -2159,22 +2601,22 @@
short [] a2 = {0, 1};
Object [] a3 = {new Integer(1), a2};
int [] a4 = {6, 5, 4};
-
+
int [] b1 = {1, 2, 3};
short [] b2 = {0, 1};
Object [] b3 = {new Integer(1), b2};
-
+
Object a [] = {a1, a2, a3};
Object b [] = {b1, b2, b3};
-
+
assertFalse(Arrays.equals(a, b));
assertTrue(Arrays.deepEquals(a,b));
-
+
a[2] = a4;
-
+
assertFalse(Arrays.deepEquals(a, b));
}
-
+
/**
* @tests java.util.Arrays#deepHashCode(Object[])
*/
@@ -2188,20 +2630,20 @@
int [] a1 = {1, 2, 3};
short [] a2 = {0, 1};
Object [] a3 = {new Integer(1), a2};
-
+
int [] b1 = {1, 2, 3};
short [] b2 = {0, 1};
Object [] b3 = {new Integer(1), b2};
-
+
Object a [] = {a1, a2, a3};
Object b [] = {b1, b2, b3};
-
+
int deep_hash_a = Arrays.deepHashCode(a);
int deep_hash_b = Arrays.deepHashCode(b);
-
+
assertEquals(deep_hash_a, deep_hash_b);
}
-
+
/**
* @tests java.util.Arrays#hashCode(boolean[] a)
*/
@@ -2214,8 +2656,8 @@
public void test_hashCode$LZ() {
int listHashCode;
int arrayHashCode;
-
- boolean [] boolArr = {true, false, false, true, false};
+
+ boolean [] boolArr = {true, false, false, true, false};
List listOfBoolean = new LinkedList();
for (int i = 0; i < boolArr.length; i++) {
listOfBoolean.add(new Boolean(boolArr[i]));
@@ -2224,7 +2666,7 @@
arrayHashCode = Arrays.hashCode(boolArr);
assertEquals(listHashCode, arrayHashCode);
}
-
+
/**
* @tests java.util.Arrays#hashCode(int[] a)
*/
@@ -2237,21 +2679,21 @@
public void test_hashCode$LI() {
int listHashCode;
int arrayHashCode;
-
- int [] intArr = {10, 5, 134, 7, 19};
+
+ int [] intArr = {10, 5, 134, 7, 19};
List listOfInteger = new LinkedList();
-
+
for (int i = 0; i < intArr.length; i++) {
- listOfInteger.add(new Integer(intArr[i]));
- }
+ listOfInteger.add(new Integer(intArr[i]));
+ }
listHashCode = listOfInteger.hashCode();
- arrayHashCode = Arrays.hashCode(intArr);
+ arrayHashCode = Arrays.hashCode(intArr);
assertEquals(listHashCode, arrayHashCode);
-
- int [] intArr2 = {10, 5, 134, 7, 19};
+
+ int [] intArr2 = {10, 5, 134, 7, 19};
assertEquals(Arrays.hashCode(intArr2), Arrays.hashCode(intArr));
}
-
+
/**
* @tests java.util.Arrays#hashCode(char[] a)
*/
@@ -2264,8 +2706,8 @@
public void test_hashCode$LC() {
int listHashCode;
int arrayHashCode;
-
- char [] charArr = {'a', 'g', 'x', 'c', 'm'};
+
+ char [] charArr = {'a', 'g', 'x', 'c', 'm'};
List listOfCharacter = new LinkedList();
for (int i = 0; i < charArr.length; i++) {
listOfCharacter.add(new Character(charArr[i]));
@@ -2274,7 +2716,7 @@
arrayHashCode = Arrays.hashCode(charArr);
assertEquals(listHashCode, arrayHashCode);
}
-
+
/**
* @tests java.util.Arrays#hashCode(byte[] a)
*/
@@ -2287,8 +2729,8 @@
public void test_hashCode$LB() {
int listHashCode;
int arrayHashCode;
-
- byte [] byteArr = {5, 9, 7, 6, 17};
+
+ byte [] byteArr = {5, 9, 7, 6, 17};
List listOfByte = new LinkedList();
for (int i = 0; i < byteArr.length; i++) {
listOfByte.add(new Byte(byteArr[i]));
@@ -2297,7 +2739,7 @@
arrayHashCode = Arrays.hashCode(byteArr);
assertEquals(listHashCode, arrayHashCode);
}
-
+
/**
* @tests java.util.Arrays#hashCode(long[] a)
*/
@@ -2310,9 +2752,9 @@
public void test_hashCode$LJ() {
int listHashCode;
int arrayHashCode;
-
+
long [] longArr = {67890234512l, 97587236923425l, 257421912912l,
- 6754268100l, 5};
+ 6754268100l, 5};
List listOfLong = new LinkedList();
for (int i = 0; i < longArr.length; i++) {
listOfLong.add(new Long(longArr[i]));
@@ -2321,7 +2763,7 @@
arrayHashCode = Arrays.hashCode(longArr);
assertEquals(listHashCode, arrayHashCode);
}
-
+
/**
* @tests java.util.Arrays#hashCode(float[] a)
*/
@@ -2334,8 +2776,8 @@
public void test_hashCode$LF() {
int listHashCode;
int arrayHashCode;
-
- float [] floatArr = {0.13497f, 0.268934f, 12e-5f, -3e+2f, 10e-4f};
+
+ float [] floatArr = {0.13497f, 0.268934f, 12e-5f, -3e+2f, 10e-4f};
List listOfFloat = new LinkedList();
for (int i = 0; i < floatArr.length; i++) {
listOfFloat.add(new Float(floatArr[i]));
@@ -2343,11 +2785,11 @@
listHashCode = listOfFloat.hashCode();
arrayHashCode = Arrays.hashCode(floatArr);
assertEquals(listHashCode, arrayHashCode);
-
+
float [] floatArr2 = {0.13497f, 0.268934f, 12e-5f, -3e+2f, 10e-4f};
assertEquals(Arrays.hashCode(floatArr2), Arrays.hashCode(floatArr));
}
-
+
/**
* @tests java.util.Arrays#hashCode(double[] a)
*/
@@ -2360,8 +2802,8 @@
public void test_hashCode$LD() {
int listHashCode;
int arrayHashCode;
-
- double [] doubleArr = {0.134945657, 0.0038754, 11e-150, -30e-300, 10e-4};
+
+ double [] doubleArr = {0.134945657, 0.0038754, 11e-150, -30e-300, 10e-4};
List listOfDouble = new LinkedList();
for (int i = 0; i < doubleArr.length; i++) {
listOfDouble.add(new Double(doubleArr[i]));
@@ -2370,7 +2812,7 @@
arrayHashCode = Arrays.hashCode(doubleArr);
assertEquals(listHashCode, arrayHashCode);
}
-
+
/**
* @tests java.util.Arrays#hashCode(short[] a)
*/
@@ -2383,8 +2825,8 @@
public void test_hashCode$LS() {
int listHashCode;
int arrayHashCode;
-
- short [] shortArr = {35, 13, 45, 2, 91};
+
+ short [] shortArr = {35, 13, 45, 2, 91};
List listOfShort = new LinkedList();
for (int i = 0; i < shortArr.length; i++) {
listOfShort.add(new Short(shortArr[i]));
@@ -2393,7 +2835,7 @@
arrayHashCode = Arrays.hashCode(shortArr);
assertEquals(listHashCode, arrayHashCode);
}
-
+
/**
* @tests java.util.Arrays#hashCode(Object[] a)
*/
@@ -2406,7 +2848,7 @@
public void test_hashCode$Ljava_lang_Object() {
int listHashCode;
int arrayHashCode;
-
+
Object[] objectArr = {new Integer(1), new Float(10e-12f), null};
List listOfObject= new LinkedList();
for (int i = 0; i < objectArr.length; i++) {
@@ -2416,7 +2858,7 @@
arrayHashCode = Arrays.hashCode(objectArr);
assertEquals(listHashCode, arrayHashCode);
}
-
+
/**
* Sets up the fixture, for example, open a network connection. This method
* is called before a test is executed.
@@ -2451,7 +2893,7 @@
booleanArray[counter + 1] = true;
}
}
-
+
/**
* Tears down the fixture, for example, close a network connection. This
* method is called after a test is executed.
