/*

 * Copyright (c) 2011, 2013, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

/* Adapted from test/java/util/Arrays/Sorting.java

 *

 * Where that test checks Arrays.sort against manual quicksort routines,

 * this test checks parallelSort against either Arrays.sort or manual

 * quicksort routines.

 */

/*

 * @test

 * @bug 8003981

 * @run main ParallelSorting -shortrun

 * @summary Exercise Arrays.parallelSort (adapted from test Sorting)

 *

 * @author Vladimir Yaroslavskiy

 * @author Jon Bentley

 * @author Josh Bloch

 */

import java.util.Arrays;

import java.util.Random;

import java.io.PrintStream;

import java.util.Comparator;

public class ParallelSorting {

    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 = {

        1000, 10000, 100000, 1000000 };

    // Array lengths used in a short run

    private static final int[] SHORT_RUN_LENGTHS = {

        5000, 9000, 10000, 12000 };

    // 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 };

    public static void main(String[] args) {

        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("PASSED in %d sec.\n", Math.round((end - start) / 1E3));

    }

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

        testEmptyAndNullIntArray();

        testEmptyAndNullLongArray();

        testEmptyAndNullShortArray();

        testEmptyAndNullCharArray();

        testEmptyAndNullByteArray();

        testEmptyAndNullFloatArray();

        testEmptyAndNullDoubleArray();

        for (int length : lengths) {

            testMergeSort(length);

            testAndCheckRange(length);

            testAndCheckSubArray(length);

        }

        for (long seed : randoms) {

            for (int length : lengths) {

                testAndCheckWithInsertionSort(length, new MyRandom(seed));

                testAndCheckWithCheckSum(length, new MyRandom(seed));

                testAndCheckWithScrambling(length, new MyRandom(seed));

                testAndCheckFloat(length, new MyRandom(seed));

                testAndCheckDouble(length, new MyRandom(seed));

                testStable(length, new MyRandom(seed));

            }

        }

    }

    private static void testEmptyAndNullIntArray() {

        ourDescription = "Check empty and null array";

        Arrays.parallelSort(new int[]{});

        Arrays.parallelSort(new int[]{}, 0, 0);

        try {

            Arrays.parallelSort((int[]) null);

        } catch (NullPointerException expected) {

            try {

                Arrays.parallelSort((int[]) null, 0, 0);

            } catch (NullPointerException expected2) {

                return;

            }

            failed("Arrays.parallelSort(int[],fromIndex,toIndex) shouldn't " +

                "catch null array");

        }

        failed("Arrays.parallelSort(int[]) shouldn't catch null array");

    }

    private static void testEmptyAndNullLongArray() {

        ourDescription = "Check empty and null array";

        Arrays.parallelSort(new long[]{});

        Arrays.parallelSort(new long[]{}, 0, 0);

        try {

            Arrays.parallelSort((long[]) null);

        } catch (NullPointerException expected) {

            try {

                Arrays.parallelSort((long[]) null, 0, 0);

            } catch (NullPointerException expected2) {

                return;

            }

            failed("Arrays.parallelSort(long[],fromIndex,toIndex) shouldn't " +

                "catch null array");

        }

        failed("Arrays.parallelSort(long[]) shouldn't catch null array");

    }

    private static void testEmptyAndNullShortArray() {

        ourDescription = "Check empty and null array";

        Arrays.parallelSort(new short[]{});

        Arrays.parallelSort(new short[]{}, 0, 0);

        try {

            Arrays.parallelSort((short[]) null);

        } catch (NullPointerException expected) {

            try {

                Arrays.parallelSort((short[]) null, 0, 0);

            } catch (NullPointerException expected2) {

                return;

            }

            failed("Arrays.parallelSort(short[],fromIndex,toIndex) shouldn't " +

                "catch null array");

        }

        failed("Arrays.parallelSort(short[]) shouldn't catch null array");

    }

    private static void testEmptyAndNullCharArray() {

        ourDescription = "Check empty and null array";

        Arrays.parallelSort(new char[]{});

        Arrays.parallelSort(new char[]{}, 0, 0);

        try {

            Arrays.parallelSort((char[]) null);

        } catch (NullPointerException expected) {

            try {

                Arrays.parallelSort((char[]) null, 0, 0);

            } catch (NullPointerException expected2) {

                return;

            }

            failed("Arrays.parallelSort(char[],fromIndex,toIndex) shouldn't " +

                "catch null array");

        }

        failed("Arrays.parallelSort(char[]) shouldn't catch null array");

    }

    private static void testEmptyAndNullByteArray() {

        ourDescription = "Check empty and null array";

        Arrays.parallelSort(new byte[]{});

        Arrays.parallelSort(new byte[]{}, 0, 0);

        try {

            Arrays.parallelSort((byte[]) null);

        } catch (NullPointerException expected) {

            try {

                Arrays.parallelSort((byte[]) null, 0, 0);

            } catch (NullPointerException expected2) {

                return;

            }

            failed("Arrays.parallelSort(byte[],fromIndex,toIndex) shouldn't " +

                "catch null array");

        }

        failed("Arrays.parallelSort(byte[]) shouldn't catch null array");

    }

    private static void testEmptyAndNullFloatArray() {

        ourDescription = "Check empty and null array";

        Arrays.parallelSort(new float[]{});

        Arrays.parallelSort(new float[]{}, 0, 0);

        try {

            Arrays.parallelSort((float[]) null);

        } catch (NullPointerException expected) {

            try {

                Arrays.parallelSort((float[]) null, 0, 0);

            } catch (NullPointerException expected2) {

                return;

            }

            failed("Arrays.parallelSort(float[],fromIndex,toIndex) shouldn't " +

                "catch null array");

        }

        failed("Arrays.parallelSort(float[]) shouldn't catch null array");

    }

    private static void testEmptyAndNullDoubleArray() {

        ourDescription = "Check empty and null array";

        Arrays.parallelSort(new double[]{});

        Arrays.parallelSort(new double[]{}, 0, 0);

        try {

            Arrays.parallelSort((double[]) null);

        } catch (NullPointerException expected) {

            try {

                Arrays.parallelSort((double[]) null, 0, 0);

            } catch (NullPointerException expected2) {

                return;

            }

            failed("Arrays.parallelSort(double[],fromIndex,toIndex) shouldn't " +

                "catch null array");

        }

        failed("Arrays.parallelSort(double[]) shouldn't catch null array");

    }

    private static void testAndCheckSubArray(int length) {

        ourDescription = "Check sorting of subarray";

        int[] golden = new int[length];

        boolean newLine = false;

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

            newLine = true;

            int fromIndex = m;

            int toIndex = length - m;

            prepareSubArray(golden, fromIndex, toIndex, m);

            int[] test = golden.clone();

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

                out.println("Test 'subarray': " + converter +

                   " length = " + length + ", m = " + m);

                Object convertedGolden = converter.convert(golden);

                Object convertedTest = converter.convert(test);

                sortSubArray(convertedTest, fromIndex, toIndex);

                checkSubArray(convertedTest, fromIndex, toIndex, m);

            }

        }

        if (newLine) {

            out.println();

        }

    }

    private static void testAndCheckRange(int length) {

        ourDescription = "Check range check";

        int[] golden = new int[length];

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

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

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

            }

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

                out.println("Test 'range': " + converter +

                   ", length = " + length + ", m = " + m);

                Object convertedGolden = converter.convert(golden);

                checkRange(convertedGolden, m);

            }

        }

        out.println();

    }

    private static void testStable(int length, MyRandom random) {

        ourDescription = "Check if sorting is stable";

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

        out.println("Test 'stable': " + "random = " + random.getSeed() +

            ", length = " + length);

        Arrays.parallelSort(a);

        checkSorted(a);

        checkStable(a);

        out.println();

        a = build(length, random);

        out.println("Test 'stable' comparator: " + "random = " + random.getSeed() +

            ", length = " + length);

        Arrays.parallelSort(a, pairCmp);

        checkSorted(a);

        checkStable(a);

        out.println();

    }

    private static void checkSorted(Pair[] a) {

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

            if (a[i].getKey() > a[i + 1].getKey()) {

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

            }

        }

    }

    private static void checkStable(Pair[] a) {

        for (int i = 0; i < a.length / 4; ) {

            int key1 = a[i].getKey();

            int value1 = a[i++].getValue();

            int key2 = a[i].getKey();

            int value2 = a[i++].getValue();

            int key3 = a[i].getKey();

            int value3 = a[i++].getValue();

            int key4 = a[i].getKey();

            int value4 = a[i++].getValue();

            if (!(key1 == key2 && key2 == key3 && key3 == key4)) {

                failed("On position " + i + " keys are different " +

                    key1 + ", " + key2 + ", " + key3 + ", " + key4);

            }

            if (!(value1 < value2 && value2 < value3 && value3 < value4)) {

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

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

                    value2 + ", " + value3 + ", " + value4);

            }

        }

    }

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

        Pair[] a = new Pair[length * 4];

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

            int key = random.nextInt();

            a[i++] = new Pair(key, 1);

            a[i++] = new Pair(key, 2);

            a[i++] = new Pair(key, 3);

            a[i++] = new Pair(key, 4);

        }

        return a;

    }

    private static Comparator<Pair> pairCmp = new Comparator<Pair>() {

        public int compare(Pair p1, Pair p2) {

            return p1.compareTo(p2);

        }

    };

    private static final class Pair implements Comparable<Pair> {

        Pair(int key, int value) {

            myKey = key;

            myValue = value;

        }

        int getKey() {

            return myKey;

        }

        int getValue() {

            return myValue;

        }

        public int compareTo(Pair pair) {

            if (myKey < pair.myKey) {

                return -1;

            }

            if (myKey > pair.myKey) {

                return 1;

            }

            return 0;

        }

        @Override

        public String toString() {

            return "(" + myKey + ", " + myValue + ")";

        }

        private int myKey;

        private int myValue;

    }

    private static void testAndCheckWithInsertionSort(int length, MyRandom random) {

        if (length > 1000) {

            return;

        }

        ourDescription = "Check sorting with insertion sort";

        int[] golden = new int[length];

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

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

                builder.build(golden, m, random);

                int[] test = golden.clone();

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

                    out.println("Test 'insertion sort': " + converter +

                        " " + builder + "random = " + random.getSeed() +

                        ", length = " + length + ", m = " + m);

                    Object convertedGolden = converter.convert(golden);

                    Object convertedTest1 = converter.convert(test);

                    Object convertedTest2 = converter.convert(test);

                    sort(convertedTest1);

                    sortByInsertionSort(convertedTest2);

                    compare(convertedTest1, convertedTest2);

                }

            }

        }

        out.println();

    }

    private static void testMergeSort(int length) {

        if (length < 1000) {

            return;

        }

        ourDescription = "Check merge sorting";

        int[] golden = new int[length];

        int period = 67; // java.util.DualPivotQuicksort.MAX_RUN_COUNT

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

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

                builder.build(golden, m);

                int[] test = golden.clone();

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

                    out.println("Test 'merge sort': " + converter + " " +

                        builder + "length = " + length + ", m = " + m);

                    Object convertedGolden = converter.convert(golden);

                    sort(convertedGolden);

                    checkSorted(convertedGolden);

                }

            }

        }

        out.println();

    }

    private static void testAndCheckWithCheckSum(int length, MyRandom random) {

        ourDescription = "Check sorting with check sum";

        int[] golden = new int[length];

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

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

                builder.build(golden, m, random);

                int[] test = golden.clone();

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

                    out.println("Test 'check sum': " + converter +

                        " " + builder + "random = " + random.getSeed() +

                        ", length = " + length + ", m = " + m);

                    Object convertedGolden = converter.convert(golden);

                    Object convertedTest = converter.convert(test);

                    sort(convertedTest);

                    checkWithCheckSum(convertedTest, convertedGolden);

                }

            }

        }

        out.println();

    }

    private static void testAndCheckWithScrambling(int length, MyRandom random) {

        ourDescription = "Check sorting with scrambling";

        int[] golden = new int[length];

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

            if (m > length) {

                break;

            }

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

                builder.build(golden, m);

                int[] test = golden.clone();

                scramble(test, random);

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

                    out.println("Test 'scrambling': " + converter +

                       " " + builder + "random = " + random.getSeed() +

                       ", length = " + length + ", m = " + m);

                    Object convertedGolden = converter.convert(golden);

                    Object convertedTest = converter.convert(test);

                    sort(convertedTest);

                    compare(convertedTest, convertedGolden);

                }

            }

        }

        out.println();

    }

    private static void testAndCheckFloat(int length, MyRandom random) {

        ourDescription = "Check float sorting";

        float[] golden = new float[length];

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

                                continue;

                            }

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

                                continue;

                            }

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

                                out.println("Test 'float': random = " + random.getSeed() +

                                   ", length = " + length + ", a = " + a + ", g = " +

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

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

                                float[] test = golden.clone();

                                scramble(test, random);

                                sort(test);

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

                            }

                            newLine = true;

                        }

                    }

                }

            }

        }

        if (newLine) {

            out.println();

        }

    }