util/Arrays/SortingNearlySortedPrimitive.java

/*
 * Copyright 2015 Goldman Sachs.
 * Copyright (c) 2015, 2016, 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
 * @bug 8154049
 * @summary Tests the sorting of a large array of sorted primitive values,
 *          predominently for cases where the array is nearly sorted. This tests
 *          code that detects patterns in the array to determine if it is nearly
 *          sorted and if so employs and optimizes merge sort rather than a
 *          Dual-Pivot QuickSort.
 *
 * @run testng SortingNearlySortedPrimitive
 */

import org.testng.annotations.DataProvider;
import org.testng.annotations.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringJoiner;
import java.util.function.IntFunction;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class SortingNearlySortedPrimitive {

    static final int BASE = 3;
    static final int WIDTH = 4;
    // Should be > DualPivotQuicksort.QUICKSORT_THRESHOLD
    static final int PAD = 300;

    Stream<int[]> createCombinations() {
        // Create all combinations for the BASE value and double the WIDTH
        // elements
        // This is create various combinations of ascending, descending and
        // equal runs to exercise the nearly sorted code paths
        return IntStream.range(0, (int) Math.pow(BASE, 2 * WIDTH)).
                mapToObj(this::createArray);
    }

    // Create an array which at either end is filled with -ve and +ve elements
    // according to the base value and padded with zeros in between
    int[] createArray(int v) {
        int[] a = new int[WIDTH + PAD + WIDTH];

        // Fill head of array
        for (int j = 0; j < WIDTH; j++) {
            a[j] = (v % BASE) - (BASE / 2);
            v /= BASE;
        }
        // Fill tail of array
        for (int j = 0; j < WIDTH; j++) {
            a[WIDTH + PAD + j] = (v % BASE) - (BASE / 2);
            v /= BASE;
        }
        return a;
    }

    @Test
    public void testCombination() {
        createCombinations().forEach(a -> {
            try {
                // Clone source array to ensure it is not modified
                this.sortAndAssert(a.clone());
                this.sortAndAssert(floatCopyFromInt(a));
                this.sortAndAssert(doubleCopyFromInt(a));
                this.sortAndAssert(longCopyFromInt(a));
                this.sortAndAssert(shortCopyFromInt(a));
                this.sortAndAssert(charCopyFromInt(a));
            } catch (AssertionError sae) {
                AssertionError ae = new AssertionError("Sort failed for " + arrayToString(a));
                ae.addSuppressed(sae);
                throw ae;
            }
        });
    }

    String arrayToString(int[] a) {
        int[] l = Arrays.copyOfRange(a, 0, WIDTH + 2);
        int[] r = Arrays.copyOfRange(a, a.length - (WIDTH + 2), a.length);
        StringJoiner sj = new StringJoiner(",", "[", "]");
        for (int i : l) {
            sj.add(Integer.toString(i));
        }
        sj.add("...");
        for (int i : r) {
            sj.add(Integer.toString(i));
        }
        return sj.toString();
    }


    @DataProvider(name = "shapes")
    public Object[][] createShapes() {
        Stream<List<Object>> baseCases = Stream.of(
                List.of("hiZeroLowTest", (IntFunction<int[]>) this::hiZeroLowData),
                List.of("endLessThanTest", (IntFunction<int[]>) this::endLessThanData),
                List.of("highFlatLowTest", (IntFunction<int[]>) this::highFlatLowData),
                List.of("identicalTest", (IntFunction<int[]>) this::identicalData),
                List.of("sortedReversedSortedTest", (IntFunction<int[]>) this::sortedReversedSortedData),
                List.of("pairFlipTest", (IntFunction<int[]>) this::pairFlipData),
                List.of("zeroHiTest", (IntFunction<int[]>) this::zeroHiData)
        );

        // Ensure the following inequality holds for certain sizes
        // DualPivotQuicksort.QUICKSORT_THRESHOLD <= size - 1
        //   < DualPivotQuicksort.COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR
        // This guarantees that code paths are taken for checking nearly sorted
        // arrays for all primitive types
        List<Integer> sizes = List.of(100, 1_000, 10_000, 1_000_000);
        return baseCases.
                flatMap(l -> sizes.stream().map(s -> append(l, s))).
                toArray(Object[][]::new);
    }

    Object[] append(List<Object> l, Object value) {
        List<Object> nl = new ArrayList<>(l);
        nl.add(value);
        return nl.toArray();
    }

    @Test(dataProvider = "shapes")
    public void testShapes(String testName, IntFunction<int[]> dataMethod, int size) {
        int[] intSourceArray = dataMethod.apply(size);

        // Clone source array to ensure it is not modified
        this.sortAndAssert(intSourceArray.clone());
        this.sortAndAssert(floatCopyFromInt(intSourceArray));
        this.sortAndAssert(doubleCopyFromInt(intSourceArray));
        this.sortAndAssert(longCopyFromInt(intSourceArray));
        this.sortAndAssert(shortCopyFromInt(intSourceArray));
        this.sortAndAssert(charCopyFromInt(intSourceArray));
    }

    private float[] floatCopyFromInt(int[] src) {
        float[] result = new float[src.length];
        for (int i = 0; i < result.length; i++) {
            result[i] = src[i];
        }
        return result;
    }

    private double[] doubleCopyFromInt(int[] src) {
        double[] result = new double[src.length];
        for (int i = 0; i < result.length; i++) {
            result[i] = src[i];
        }
        return result;
    }

    private long[] longCopyFromInt(int[] src) {
        long[] result = new long[src.length];
        for (int i = 0; i < result.length; i++) {
            result[i] = src[i];
        }
        return result;
    }

    private short[] shortCopyFromInt(int[] src) {
        short[] result = new short[src.length];
        for (int i = 0; i < result.length; i++) {
            result[i] = (short) src[i];
        }
        return result;
    }

    private char[] charCopyFromInt(int[] src) {
        char[] result = new char[src.length];
        for (int i = 0; i < result.length; i++) {
            result[i] = (char) src[i];
        }
        return result;
    }

    private void sortAndAssert(int[] array) {
        Arrays.sort(array);
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1]) {
                throw new AssertionError("not sorted");
            }
        }
    }

    private void sortAndAssert(char[] array) {
        Arrays.sort(array);
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1]) {
                throw new AssertionError("not sorted");
            }
        }
    }

    private void sortAndAssert(short[] array) {
        Arrays.sort(array);
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1]) {
                throw new AssertionError("not sorted");
            }
        }
    }

    private void sortAndAssert(double[] array) {
        Arrays.sort(array);
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1]) {
                throw new AssertionError("not sorted");
            }
        }
    }

    private void sortAndAssert(float[] array) {
        Arrays.sort(array);
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1]) {
                throw new AssertionError("not sorted");
            }
        }
    }

    private void sortAndAssert(long[] array) {
        Arrays.sort(array);
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1]) {
                throw new AssertionError("not sorted");
            }
        }
    }

    private int[] zeroHiData(int size) {
        int[] array = new int[size];

        int threeQuarters = (int) (size * 0.75);
        for (int i = 0; i < threeQuarters; i++) {
            array[i] = 0;
        }
        int k = 1;
        for (int i = threeQuarters; i < size; i++) {
            array[i] = k;
            k++;
        }

        return array;
    }

    private int[] hiZeroLowData(int size) {
        int[] array = new int[size];

        int oneThird = size / 3;
        for (int i = 0; i < oneThird; i++) {
            array[i] = i;
        }
        int twoThirds = oneThird * 2;
        for (int i = oneThird; i < twoThirds; i++) {
            array[i] = 0;
        }
        for (int i = twoThirds; i < size; i++) {
            array[i] = oneThird - i + twoThirds;
        }
        return array;
    }

    private int[] highFlatLowData(int size) {
        int[] array = new int[size];

        int oneThird = size / 3;
        for (int i = 0; i < oneThird; i++) {
            array[i] = i;
        }
        int twoThirds = oneThird * 2;
        int constant = oneThird - 1;
        for (int i = oneThird; i < twoThirds; i++) {
            array[i] = constant;
        }
        for (int i = twoThirds; i < size; i++) {
            array[i] = constant - i + twoThirds;
        }

        return array;
    }

    private int[] identicalData(int size) {
        int[] array = new int[size];
        int listNumber = 24;

        for (int i = 0; i < size; i++) {
            array[i] = listNumber;
        }

        return array;
    }

    private int[] endLessThanData(int size) {
        int[] array = new int[size];

        for (int i = 0; i < size - 1; i++) {
            array[i] = 3;
        }
        array[size - 1] = 1;

        return array;
    }

    private int[] sortedReversedSortedData(int size) {
        int[] array = new int[size];

        for (int i = 0; i < size / 2; i++) {
            array[i] = i;
        }
        int num = 0;
        for (int i = size / 2; i < size; i++) {
            array[i] = size - num;
            num++;
        }

        return array;
    }

    private int[] pairFlipData(int size) {
        int[] array = new int[size];

        for (int i = 0; i < size; i++) {
            array[i] = i;
        }
        for (int i = 0; i < size; i += 2) {
            int temp = array[i];
            array[i] = array[i + 1];
            array[i + 1] = temp;
        }

        return array;
    }
}