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