* @bug 6880672 6896573 6899694

 *

 * @author Vladimir Yaroslavskiy

 * @author Jon Bentley

 * @author Josh Bloch

    private static final PrintStream out = System.out;

    private static final PrintStream err = System.err;

    // Array lengths used in a long run (default)

    private static final int[] LONG_RUN_LENGTHS = {

        1, 2, 3, 5, 8, 13, 21, 34, 55, 100, 1000, 10000, 100000, 1000000};

    // Array lengths used in a short run

    private static final int[] SHORT_RUN_LENGTHS = { 1, 2, 3, 21, 55, 1000, 10000 };

    // Random initial values used in a long run (default)

    private static final long[] LONG_RUN_RANDOMS = {666, 0xC0FFEE, 999};

    // Random initial values used in a short run

    private static final long[] SHORT_RUN_RANDOMS = {666};

        boolean shortRun = args.length > 0 && args[0].equals("-shortrun");

        long start = System.currentTimeMillis();

        if (shortRun) {

            testAndCheck(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS);

        } else {

            testAndCheck(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS);

        }

        long end = System.currentTimeMillis();

        out.format("PASS in %d sec.\n", Math.round((end - start) / 1E3));

    }

    private static void testAndCheck(int[] lengths, long[] randoms) {

        for (long random : randoms) {

            reset(random);

            for (int len : lengths) {

                testAndCheckWithCheckSum(len, random);

            }

            reset(random);

            for (int len : lengths) {

                testAndCheckWithScrambling(len, random);

            }

            reset(random);

            for (int len : lengths) {

                testAndCheckFloat(len, random);

            }

            reset(random);

            for (int len : lengths) {

                testAndCheckDouble(len, random);

            }

            reset(random);

            for (int len : lengths) {

                testAndCheckRange(len, random);

            }

            reset(random);

            for (int len : lengths) {

                testAndCheckSubArray(len, random);

            }

        }

    }

    private static void testAndCheckSubArray(int len, long random) {

        int[] golden = new int[len];

        for (int m = 1; m < len / 2; m *= 2) {

            int fromIndex = m;

            int toIndex = len - m;

            prepareSubArray(golden, fromIndex, toIndex, m);

            int[] test = golden.clone();

            for (TypeConverter converter : TypeConverter.values()) {

                out.println("Test #6: " + converter +

                   " len = " + len + ", m = " + m);

                Object convertedGolden = converter.convert(golden);

                Object convertedTest = converter.convert(test);

                // outArr(test);

                sortSubArray(convertedTest, fromIndex, toIndex);

                // outArr(test);

                checkSubArray(convertedTest, fromIndex, toIndex, m);

            }

        }

    private static void testAndCheckRange(int len, long random) {

        int[] golden = new int[len];

        for (int m = 1; m < 2 * len; m *= 2) {

            for (int i = 1; i <= len; i++) {

                golden[i - 1] = i % m + m % i;

            }

            for (TypeConverter converter : TypeConverter.values()) {

                out.println("Test #5: " + converter +

                   ", len = " + len + ", m = " + m);

                Object convertedGolden = converter.convert(golden);

                sortRange(convertedGolden, m);

                sortEmpty(convertedGolden);

            }

        }

        out.println();

    }

    private static void testAndCheckWithCheckSum(int len, long random) {

        int[] golden = new int[len];

        for (int m = 1; m < 2 * len; m *= 2) {

            for (UnsortedBuilder builder : UnsortedBuilder.values()) {

                builder.build(golden, m);

                int[] test = golden.clone();

                for (TypeConverter converter : TypeConverter.values()) {

                    out.println("Test #1: " + converter + " " + builder +

                       "random = " +  random + ", len = " + len +

                       ", m = " + m);

                    Object convertedGolden = converter.convert(golden);

                    Object convertedTest = converter.convert(test);

                    sort(convertedTest);

                    checkWithCheckSum(convertedTest, convertedGolden);

                }

            }

        }

        out.println();

    }

    private static void testAndCheckWithScrambling(int len, long random) {

        int[] golden = new int[len];

        for (int m = 1; m <= 7; m++) {

            if (m > len) {

                break;

            }

            for (SortedBuilder builder : SortedBuilder.values()) {

                builder.build(golden, m);

                int[] test = golden.clone();

                scramble(test);

                for (TypeConverter converter : TypeConverter.values()) {

                    out.println("Test #2: " + converter + " " + builder +

                       "random = " +  random + ", len = " + len +

                       ", m = " + m);

                    Object convertedGolden = converter.convert(golden);

                    Object convertedTest = converter.convert(test);

                    sort(convertedTest);

                    compare(convertedTest, convertedGolden);

                }

            }

        }

        out.println();

    }

    private static void testAndCheckFloat(int len, long random) {

        float[] golden = new float[len];

        final int MAX = 10;

        boolean newLine = false;

        for (int a = 0; a <= MAX; a++) {

            for (int g = 0; g <= MAX; g++) {

                for (int z = 0; z <= MAX; z++) {

                    for (int n = 0; n <= MAX; n++) {

                        for (int p = 0; p <= MAX; p++) {

                            if (a + g + z + n + p > len) {

                                continue;

                            }

                            if (a + g + z + n + p < len) {

                                continue;

                            }

                            for (FloatBuilder builder : FloatBuilder.values()) {

                                out.println("Test #3: random = " + random +

                                   ", len = " + len + ", a = " + a + ", g = " + g +

                                   ", z = " + z + ", n = " + n + ", p = " + p);

                                builder.build(golden, a, g, z, n, p);

                                float[] test = golden.clone();

                                scramble(test);

                                // outArr(test);

                                sort(test);

                                // outArr(test);

                                compare(test, golden, a, n, g);

                            }

                            newLine = true;

                        }

        if (newLine) {

            out.println();

        }

    }

    private static void testAndCheckDouble(int len, long random) {

        double[] golden = new double[len];

        final int MAX = 10;

        boolean newLine = false;

        for (int a = 0; a <= MAX; a++) {

            for (int g = 0; g <= MAX; g++) {

                for (int z = 0; z <= MAX; z++) {

                    for (int n = 0; n <= MAX; n++) {

                        for (int p = 0; p <= MAX; p++) {

                            if (a + g + z + n + p > len) {

                                continue;

                            }

                            if (a + g + z + n + p < len) {

                                continue;

                            }

                            for (DoubleBuilder builder : DoubleBuilder.values()) {

                                out.println("Test #4: random = " + random +

                                   ", len = " + len + ", a = " + a + ", g = " + g +

                                   ", z = " + z + ", n = " + n + ", p = " + p);

                                builder.build(golden, a, g, z, n, p);

                                double[] test = golden.clone();

                                scramble(test);

                                // outArr(test);

                                sort(test);

                                // outArr(test);

                                compare(test, golden, a, n, g);

                            }

                            newLine = true;

                        }

                    }

                }

            }

        }

        if (newLine) {

            out.println();

        }

    private static void prepareSubArray(int[] a, int fromIndex, int toIndex, int m) {

        for (int i = 0; i < fromIndex; i++) {

            a[i] = 0xBABA;

        }

        for (int i = fromIndex; i < toIndex; i++) {

            a[i] = -i + m;

        }

        for (int i = toIndex; i < a.length; i++) {

            a[i] = 0xDEDA;

        }

    }

    private static void scramble(int[] a) {

        int length = a.length;

        for (int i = 0; i < length * 7; i++) {

            swap(a, ourRandom.nextInt(length), ourRandom.nextInt(length));

        }

    }

    private static void scramble(float[] a) {

        int length = a.length;

        for (int i = 0; i < length * 7; i++) {

            swap(a, ourRandom.nextInt(length), ourRandom.nextInt(length));

        }

    }

    private static void scramble(double[] a) {

        int length = a.length;

        for (int i = 0; i < length * 7; i++) {

            swap(a, ourRandom.nextInt(length), ourRandom.nextInt(length));

        }

    }

    private static void swap(int[] a, int i, int j) {

        int t = a[i];

        a[i] = a[j];

        a[j] = t;

    }

    private static void swap(float[] a, int i, int j) {

        float t = a[i];

        a[i] = a[j];

        a[j] = t;

    }

    private static void swap(double[] a, int i, int j) {

        double t = a[i];

        a[i] = a[j];

        a[j] = t;

    }

    private static enum TypeConverter {

                return a.clone();

                    b[i] = (long) a[i];

    private static enum FloatBuilder {

        SIMPLE {

            void build(float[] x, int a, int g, int z, int n, int p) {

                int fromIndex = 0;

                float negativeValue = -ourRandom.nextFloat();

                float positiveValue =  ourRandom.nextFloat();

                writeValue(x, negativeValue, fromIndex, n);

                fromIndex += n;

                writeValue(x, -0.0f, fromIndex, g);

                fromIndex += g;

                writeValue(x, 0.0f, fromIndex, z);

                fromIndex += z;

                writeValue(x, positiveValue, fromIndex, p);

                fromIndex += p;

                writeValue(x, Float.NaN, fromIndex, a);

            }

        };

        abstract void build(float[] x, int a, int g, int z, int n, int p);

    }

    private static enum DoubleBuilder {

        SIMPLE {

            void build(double[] x, int a, int g, int z, int n, int p) {

                int fromIndex = 0;

                double negativeValue = -ourRandom.nextFloat();

                double positiveValue =  ourRandom.nextFloat();

                writeValue(x, negativeValue, fromIndex, n);

                fromIndex += n;

                writeValue(x, -0.0d, fromIndex, g);

                fromIndex += g;

                writeValue(x, 0.0d, fromIndex, z);

                fromIndex += z;

                writeValue(x, positiveValue, fromIndex, p);

                fromIndex += p;

                writeValue(x, Double.NaN, fromIndex, a);

            }

        };

        abstract void build(double[] x, int a, int g, int z, int n, int p);

    }

    private static void writeValue(float[] a, float value, int fromIndex, int count) {

        for (int i = fromIndex; i < fromIndex + count; i++) {

            a[i] = value;

        }

    }

    private static void compare(float[] a, float[] b, int numNaN, int numNeg, int numNegZero) {

        for (int i = a.length - numNaN; i < a.length; i++) {

            if (a[i] == a[i]) {

                failed("On position " + i + " must be NaN instead of " + a[i]);

            }

        }

        final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);

        for (int i = numNeg; i < numNeg + numNegZero; i++) {

            if (NEGATIVE_ZERO != Float.floatToIntBits(a[i])) {

                failed("On position " + i + " must be -0.0f instead of " + a[i]);

            }

        }

        for (int i = 0; i < a.length - numNaN; i++) {

            if (a[i] != b[i]) {

                failed(i, "" + a[i], "" + b[i]);

            }

        }

    }

    private static void writeValue(double[] a, double value, int fromIndex, int count) {

        for (int i = fromIndex; i < fromIndex + count; i++) {

            a[i] = value;

        }

    }

    private static void compare(double[] a, double[] b, int numNaN, int numNeg, int numNegZero) {

        for (int i = a.length - numNaN; i < a.length; i++) {

            if (a[i] == a[i]) {

                failed("On position " + i + " must be NaN instead of " + a[i]);

            }

        }

        final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);