/*

 * Copyright (c) 2009, 2010, 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.

 */

/*

 * @test

 * @summary Exercise Arrays.sort

 * @build Sorting

 * @run main Sorting -shortrun

 *

 * @author Vladimir Yaroslavskiy

 * @author Jon Bentley

 * @author Josh Bloch

 */

import java.util.Arrays;

import java.util.Random;

import java.io.PrintStream;

public class Sorting {

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

    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("\nPASSED 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 (long random : randoms) {

            reset(random);

            for (int length : lengths) {

                testAndCheckWithInsertionSort(length, random);

            }

            reset(random);

            for (int length : lengths) {

                testAndCheckWithCheckSum(length, random);

            }

            reset(random);

            for (int length : lengths) {

                testAndCheckWithScrambling(length, random);

            }

            reset(random);

            for (int length : lengths) {

                testAndCheckFloat(length, random);

            }

            reset(random);

            for (int length : lengths) {

                testAndCheckDouble(length, random);

            }

            reset(random);

            for (int length : lengths) {

                testAndCheckRange(length, random);

            }

            reset(random);

            for (int length : lengths) {

                testAndCheckSubArray(length, random);

            }

            reset(random);

            for (int length : lengths) {

                testStable(length, random);

            }

        }

    }

    private static void testEmptyAndNullIntArray() {

        ourDescription = "Check empty and null array";

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

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

        try {

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

        } catch (NullPointerException expected) {

            try {

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

            } catch (NullPointerException expected2) {

                return;

            }

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

                "catch null array");

        }

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

    }

    private static void testEmptyAndNullLongArray() {

        ourDescription = "Check empty and null array";

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

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

        try {

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

        } catch (NullPointerException expected) {

            try {

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

            } catch (NullPointerException expected2) {

                return;

            }

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

                "catch null array");

        }

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

    }

    private static void testEmptyAndNullShortArray() {

        ourDescription = "Check empty and null array";

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

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

        try {

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

        } catch (NullPointerException expected) {

            try {

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

            } catch (NullPointerException expected2) {

                return;

            }

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

                "catch null array");

        }

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

    }

    private static void testEmptyAndNullCharArray() {

        ourDescription = "Check empty and null array";

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

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

        try {

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

        } catch (NullPointerException expected) {

            try {

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

            } catch (NullPointerException expected2) {

                return;

            }

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

                "catch null array");

        }

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

    }

    private static void testEmptyAndNullByteArray() {

        ourDescription = "Check empty and null array";

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

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

        try {

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

        } catch (NullPointerException expected) {

            try {

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

            } catch (NullPointerException expected2) {

                return;

            }

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

                "catch null array");

        }

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

    }

    private static void testEmptyAndNullFloatArray() {

        ourDescription = "Check empty and null array";

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

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

        try {

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

        } catch (NullPointerException expected) {

            try {

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

            } catch (NullPointerException expected2) {

                return;

            }

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

                "catch null array");

        }

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

    }

    private static void testEmptyAndNullDoubleArray() {

        ourDescription = "Check empty and null array";

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

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

        try {

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

        } catch (NullPointerException expected) {

            try {

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

            } catch (NullPointerException expected2) {

                return;

            }

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

                "catch null array");

        }

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

    }

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

        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, long random) {

        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, long random) {

        ourDescription = "Check if sorting is stable";

        Pair[] a = build(length);

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

            ", length = " + length);

        Arrays.sort(a);

        checkSorted(a);

        checkStable(a);

    }

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

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

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

            int key = ourRandom.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 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, long 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);

                int[] test = golden.clone();

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

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

                        builder + "random = " +  random + ", 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 testAndCheckWithCheckSum(int length, long 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);

                int[] test = golden.clone();

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

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

                        builder + "random = " +  random + ", 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, long 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);

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

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

                       builder + "random = " +  random + ", 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, long 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 +

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

                                   ", g = " + g + ", z = " + z + ", n = " + n +

                                   ", p = " + p);

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

                                float[] test = golden.clone();