* Copyright (c) 2009, 2019, Oracle and/or its affiliates. All rights reserved.

 * @compile/module=java.base java/util/SortingHelper.java

 * @bug 6880672 6896573 6899694 6976036 7013585 7018258 8003981 8226297

 * @summary Exercise Arrays.sort, Arrays.parallelSort

import java.io.PrintStream;

import java.util.Comparator;

import java.util.SortingHelper;

        1, 3, 8, 21, 55, 100, 1_000, 10_000, 100_000 };

        1, 8, 55, 100, 10_000 };

    private static final TestRandom[] LONG_RUN_RANDOMS = {

        TestRandom.BABA, TestRandom.DEDA, TestRandom.C0FFEE };

    private static final TestRandom[] SHORT_RUN_RANDOMS = {

        TestRandom.C0FFEE };

    // Constants used in subarray sorting

    private static final int A380 = 0xA380;

    private static final int B747 = 0xB747;

    private final SortingHelper sortingHelper;

    private final TestRandom[] randoms;

    private final int[] lengths;

    private Object[] gold;

    private Object[] test;

        long start = System.currentTimeMillis();

        int[] lengths = shortRun ? SHORT_RUN_LENGTHS : LONG_RUN_LENGTHS;

        TestRandom[] randoms = shortRun ? SHORT_RUN_RANDOMS : LONG_RUN_RANDOMS;

        new Sorting(SortingHelper.DUAL_PIVOT_QUICKSORT, randoms, lengths).testCore();

        new Sorting(SortingHelper.PARALLEL_SORT, randoms, lengths).testCore();

        new Sorting(SortingHelper.HEAP_SORT, randoms, lengths).testBasic();

        new Sorting(SortingHelper.ARRAYS_SORT, randoms, lengths).testAll();

        new Sorting(SortingHelper.ARRAYS_PARALLEL_SORT, randoms, lengths).testAll();

        out.format("PASSED in %d sec.\n", (end - start) / 1000);

    private Sorting(SortingHelper sortingHelper, TestRandom[] randoms, int[] lengths) {

        this.sortingHelper = sortingHelper;

        this.randoms = randoms;

        this.lengths = lengths;

    }

    private void testBasic() {

        testEmptyArray();

            createData(length);

            testBasic(length);

    }

    private void testBasic(int length) {

        for (TestRandom random : randoms) {

            testWithInsertionSort(length, random);

            testWithCheckSum(length, random);

            testWithScrambling(length, random);

    private void testCore() {

        for (int length : lengths) {

            createData(length);

            testCore(length);

        }

    }

    private void testCore(int length) {

        testBasic(length);

        for (TestRandom random : randoms) {

            testMergingSort(length, random);

            testSubArray(length, random);

            testNegativeZero(length, random);

            testFloatingPointSorting(length, random);

    }

    private void testAll() {

        for (int length : lengths) {

            createData(length);

            testAll(length);

        }

    }

    private void testAll(int length) {

        testCore(length);

        for (TestRandom random : randoms) {

            testRange(length, random);

            testStability(length, random);

        }

    private void testEmptyArray() {

        testEmptyAndNullIntArray();

        testEmptyAndNullLongArray();

        testEmptyAndNullByteArray();

        testEmptyAndNullCharArray();

        testEmptyAndNullShortArray();

        testEmptyAndNullFloatArray();

        testEmptyAndNullDoubleArray();

    }

    private void testStability(int length, TestRandom random) {

        printTestName("Test stability", random, length);

        Pair[] a = build(length, random);

        sortingHelper.sort(a);

        checkSorted(a);

        checkStable(a);

        a = build(length, random);

        sortingHelper.sort(a, pairComparator);

        checkSorted(a);

        checkStable(a);

        out.println();

    }

    private void testEmptyAndNullIntArray() {

        sortingHelper.sort(new int[] {});

        sortingHelper.sort(new int[] {}, 0, 0);

            sortingHelper.sort(null);

                sortingHelper.sort(null, 0, 0);

            fail(sortingHelper + "(int[],fromIndex,toIndex) shouldn't " +

        fail(sortingHelper + "(int[]) shouldn't catch null array");

    private void testEmptyAndNullLongArray() {

        sortingHelper.sort(new long[] {});

        sortingHelper.sort(new long[] {}, 0, 0);

            sortingHelper.sort(null);

                sortingHelper.sort(null, 0, 0);

            fail(sortingHelper + "(long[],fromIndex,toIndex) shouldn't " +

        fail(sortingHelper + "(long[]) shouldn't catch null array");

    private void testEmptyAndNullByteArray() {

        sortingHelper.sort(new byte[] {});

        sortingHelper.sort(new byte[] {}, 0, 0);

            sortingHelper.sort(null);

                sortingHelper.sort(null, 0, 0);

            fail(sortingHelper + "(byte[],fromIndex,toIndex) shouldn't " +

        fail(sortingHelper + "(byte[]) shouldn't catch null array");

    private void testEmptyAndNullCharArray() {

        sortingHelper.sort(new char[] {});

        sortingHelper.sort(new char[] {}, 0, 0);

            sortingHelper.sort(null);

                sortingHelper.sort(null, 0, 0);

            fail(sortingHelper + "(char[],fromIndex,toIndex) shouldn't " +

        fail(sortingHelper + "(char[]) shouldn't catch null array");

    private void testEmptyAndNullShortArray() {

        sortingHelper.sort(new short[] {});

        sortingHelper.sort(new short[] {}, 0, 0);

            sortingHelper.sort(null);

                sortingHelper.sort(null, 0, 0);

            } catch (NullPointerException expected2) {

                return;

            }

            fail(sortingHelper + "(short[],fromIndex,toIndex) shouldn't " +

                "catch null array");

        }

        fail(sortingHelper + "(short[]) shouldn't catch null array");

    }

    private void testEmptyAndNullFloatArray() {

        sortingHelper.sort(new float[] {});

        sortingHelper.sort(new float[] {}, 0, 0);

        try {

            sortingHelper.sort(null);

        } catch (NullPointerException expected) {

            try {

                sortingHelper.sort(null, 0, 0);

            fail(sortingHelper + "(float[],fromIndex,toIndex) shouldn't " +

        fail(sortingHelper + "(float[]) shouldn't catch null array");

    private void testEmptyAndNullDoubleArray() {

        sortingHelper.sort(new double[] {});

        sortingHelper.sort(new double[] {}, 0, 0);

        try {

            sortingHelper.sort(null);

        } catch (NullPointerException expected) {

            try {

                sortingHelper.sort(null, 0, 0);

            } catch (NullPointerException expected2) {

                return;

            }

            fail(sortingHelper + "(double[],fromIndex,toIndex) shouldn't " +

                "catch null array");

        }

        fail(sortingHelper + "(double[]) shouldn't catch null array");

    }

    private void testSubArray(int length, TestRandom random) {

        if (length < 4) {

            return;

        }

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

            prepareSubArray((int[]) gold[0], fromIndex, toIndex);

            convertData(length);

            for (int i = 0; i < test.length; i++) {

                printTestName("Test subarray", random, length,

                    ", m = " + m + ", " + getType(i));

                sortingHelper.sort(test[i], fromIndex, toIndex);

                checkSubArray(test[i], fromIndex, toIndex);

    private void testRange(int length, TestRandom random) {

        if (length < 2) {

            return;

        }

        for (int m = 1; m < length; m <<= 1) {

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

                ((int[]) gold[0]) [i - 1] = i % m + m % i;

            }

            convertData(length);

            for (int i = 0; i < test.length; i++) {

                printTestName("Test range check", random, length,

                    ", m = " + m + ", " + getType(i));

                checkRange(test[i], m);

            }

        }

    private void checkSorted(Pair[] a) {

                fail("Array is not sorted at " + i + "-th position: " +

                    a[i].getKey() + " and " + a[i + 1].getKey());

    private void checkStable(Pair[] a) {

                fail("Keys are different " + key1 + ", " + key2 + ", " +

                    key3 + ", " + key4 + " at position " + i);

                fail("Sorting is not stable at position " + i +

                    ". Second values have been changed: " + value1 + ", " +

    private Pair[] build(int length, Random random) {

    private void testWithInsertionSort(int length, TestRandom random) {

        for (int m = 1; m <= length; m <<= 1) {

                builder.build((int[]) gold[0], m, random);

                convertData(length);

                for (int i = 0; i < test.length; i++) {

                    printTestName("Test with insertion sort", random, length,

                        ", m = " + m + ", " + getType(i) + " " + builder);

                    sortingHelper.sort(test[i]);

                    sortByInsertionSort(gold[i]);

                    compare(test[i], gold[i]);

    private void testMergingSort(int length, TestRandom random) {

        if (length < (4 << 10)) { // DualPivotQuicksort.MIN_TRY_MERGE_SIZE

        final int PERIOD = 50;

        for (int m = PERIOD - 2; m <= PERIOD + 2; m++) {

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

                builder.build((int[]) gold[0], m);

                convertData(length);

                for (int i = 0; i < test.length; i++) {

                    printTestName("Test merging sort", random, length,

                        ", m = " + m + ", " +  getType(i) + " " + builder);

                    sortingHelper.sort(test[i]);

                    checkSorted(test[i]);

                }

            }

        }

        out.println();

    }

    private void testWithCheckSum(int length, TestRandom random) {

        for (int m = 1; m <= length; m <<= 1) {

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

                builder.build((int[]) gold[0], m, random);

                convertData(length);

                for (int i = 0; i < test.length; i++) {

                    printTestName("Test with check sum", random, length,

                        ", m = " + m + ", " + getType(i) + " " + builder);

                    sortingHelper.sort(test[i]);

                    checkWithCheckSum(test[i], gold[i]);

    private void testWithScrambling(int length, TestRandom random) {

        for (int m = 1; m <= length; m <<= 1) {

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

                builder.build((int[]) gold[0], m);

                convertData(length);

                for (int i = 0; i < test.length; i++) {

                    printTestName("Test with scrambling", random, length,

                        ", m = " + m + ", " + getType(i) + " " + builder);

                    scramble(test[i], random);

                    sortingHelper.sort(test[i]);

                    compare(test[i], gold[i]);

    private void testNegativeZero(int length, TestRandom random) {

        for (int i = 5; i < test.length; i++) {

            printTestName("Test negative zero -0.0", random, length, " " + getType(i));

            NegativeZeroBuilder builder = NegativeZeroBuilder.values() [i - 5];

            builder.build(test[i], random);

            sortingHelper.sort(test[i]);

            checkNegativeZero(test[i]);

        }

        out.println();

    }

    private void testFloatingPointSorting(int length, TestRandom random) {

        if (length < 2) {

            return;

        }

        final int MAX = 13;

        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 != length) {