--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/test/jdk/java/util/Arrays/SortingNearlySortedPrimitive.java Tue Sep 12 19:03:39 2017 +0200
@@ -0,0 +1,354 @@
+/*
+ * 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;
+ }
+}