--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/jdk/test/java/util/Arrays/Sorting.java Fri Oct 30 15:06:24 2009 +0000
@@ -0,0 +1,493 @@
+/*
+ * Copyright 2009 Sun Microsystems, Inc. All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ */
+
+/*
+ * @test
+ * @bug 6880672 6896573
+ * @summary Exercise Arrays.sort
+ * @build Sorting
+ * @run main Sorting -shortrun
+ * @author Vladimir Yaroslavskiy, Josh Bloch, Jon Bentley
+ */
+
+import java.util.Arrays;
+import java.util.Random;
+import java.io.PrintStream;
+
+public class Sorting {
+ static final PrintStream out = System.out;
+ static final PrintStream err = System.err;
+
+ // array lengths used in a long run (default)
+ static final int[] LONG_RUN = {
+ 0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000, 100000, 1000000};
+
+ // array lengths used in a short run
+ static final int[] SHORT_RUN = {0, 1, 2, 3, 21, 55, 1000, 10000, 500000};
+
+ public static void main(String[] args) {
+ boolean shortRun = false;
+ if (args.length > 0 && args[0].equals("-shortrun"))
+ shortRun = true;
+
+ long start = System.nanoTime();
+
+ testAndCheck((shortRun) ? SHORT_RUN : LONG_RUN);
+
+ long end = System.nanoTime();
+
+ out.println();
+ out.format("PASS in %ds%n", Math.round((end - start) / 1e9));
+ }
+
+ static void testAndCheck(int[] lengths) {
+ for (int len : lengths) {
+ out.println();
+ ArrayBuilder.reset();
+ int[] golden = new int[len];
+
+ for (int m = 1; m < 2 * len; m *= 2) {
+ for (ArrayBuilder builder : ArrayBuilder.values()) {
+ builder.build(golden, m);
+ int[] test = golden.clone();
+
+ for (Converter converter : Converter.values()) {
+ out.println("Test: " + converter + " " + builder +
+ "len = " + len + ", m = " + m);
+ Object convertedGolden = converter.convert(golden);
+ Object convertedTest = converter.convert(test);
+ sort(convertedTest);
+ checkWithCheckSum(convertedTest, convertedGolden);
+ }
+ }
+ }
+ }
+ }
+
+ static enum Converter {
+ 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);
+
+ @Override public String toString() {
+ String name = name();
+
+ for (int i = name.length(); i < 9; i++) {
+ name += " ";
+ }
+ return name;
+ }
+ }
+
+ static enum ArrayBuilder {
+ 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);
+ }
+
+ static void checkWithCheckSum(Object test, Object golden) {
+ checkSorted(test);
+ checkCheckSum(test, golden);
+ }
+
+ static void failed(String message) {
+ err.format("***FAILED: %s%%n", message);
+ throw new RuntimeException("Test failed - see log file for details");
+ }
+
+ static void failed(int index, String value1, String value2) {
+ failed("Array is not sorted at " + index + "-th position: " + value1 +
+ " and " + value2);
+ }
+
+ static void checkSorted(Object object) {
+ if (object instanceof int[]) {
+ checkSorted((int[]) object);
+ } else if (object instanceof long[]) {
+ checkSorted((long[]) object);
+ } else if (object instanceof short[]) {
+ checkSorted((short[]) object);
+ } else if (object instanceof byte[]) {
+ checkSorted((byte[]) object);
+ } else if (object instanceof char[]) {
+ checkSorted((char[]) object);
+ } else if (object instanceof float[]) {
+ checkSorted((float[]) object);
+ } else if (object instanceof double[]) {
+ checkSorted((double[]) object);
+ } else {
+ failed("Unknow type of array: " + object + " of class " +
+ object.getClass().getName());
+ }
+ }
+
+ static void checkSorted(int[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+ }
+
+ static void checkSorted(long[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+ }
+
+ static void checkSorted(short[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+ }
+
+ static void checkSorted(byte[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+ }
+
+ static void checkSorted(char[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+ }
+
+ static void checkSorted(float[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+ }
+
+ static void checkSorted(double[] a) {
+ for (int i = 0; i < a.length - 1; i++) {
+ if (a[i] > a[i + 1]) {
+ failed(i, "" + a[i], "" + a[i + 1]);
+ }
+ }
+ }
+
+ static void checkCheckSum(Object test, Object golden) {
+ if (checkSum(test) != checkSum(golden)) {
+ failed("Original and sorted arrays seems not identical");
+ }
+ }
+
+ static int checkSum(Object object) {
+ if (object instanceof int[]) {
+ return checkSum((int[]) object);
+ } else if (object instanceof long[]) {
+ return checkSum((long[]) object);
+ } else if (object instanceof short[]) {
+ return checkSum((short[]) object);
+ } else if (object instanceof byte[]) {
+ return checkSum((byte[]) object);
+ } else if (object instanceof char[]) {
+ return checkSum((char[]) object);
+ } else if (object instanceof float[]) {
+ return checkSum((float[]) object);
+ } else if (object instanceof double[]) {
+ return checkSum((double[]) object);
+ } else {
+ failed("Unknow type of array: " + object + " of class " +
+ object.getClass().getName());
+ return -1;
+ }
+ }
+
+ static int checkSum(int[] a) {
+ int checkSum = 0;
+
+ for (int e : a) {
+ checkSum ^= e; // xor
+ }
+ return checkSum;
+ }
+
+ static int checkSum(long[] a) {
+ long checkSum = 0;
+
+ for (long e : a) {
+ checkSum ^= e; // xor
+ }
+ return (int) checkSum;
+ }
+
+ static int checkSum(short[] a) {
+ short checkSum = 0;
+
+ for (short e : a) {
+ checkSum ^= e; // xor
+ }
+ return (int) checkSum;
+ }
+
+ static int checkSum(byte[] a) {
+ byte checkSum = 0;
+
+ for (byte e : a) {
+ checkSum ^= e; // xor
+ }
+ return (int) checkSum;
+ }
+
+ static int checkSum(char[] a) {
+ char checkSum = 0;
+
+ for (char e : a) {
+ checkSum ^= e; // xor
+ }
+ return (int) checkSum;
+ }
+
+ static int checkSum(float[] a) {
+ int checkSum = 0;
+
+ for (float e : a) {
+ checkSum ^= (int) e; // xor
+ }
+ return checkSum;
+ }
+
+ static int checkSum(double[] a) {
+ int checkSum = 0;
+
+ for (double e : a) {
+ checkSum ^= (int) e; // xor
+ }
+ return checkSum;
+ }
+
+ static void sort(Object object) {
+ if (object instanceof int[]) {
+ Arrays.sort((int[]) object);
+ } else if (object instanceof long[]) {
+ Arrays.sort((long[]) object);
+ } else if (object instanceof short[]) {
+ Arrays.sort((short[]) object);
+ } else if (object instanceof byte[]) {
+ Arrays.sort((byte[]) object);
+ } else if (object instanceof char[]) {
+ Arrays.sort((char[]) object);
+ } else if (object instanceof float[]) {
+ Arrays.sort((float[]) object);
+ } else if (object instanceof double[]) {
+ Arrays.sort((double[]) object);
+ } else {
+ failed("Unknow type of array: " + object + " of class " +
+ object.getClass().getName());
+ }
+ }
+}