1 /*

     2  * Copyright 2015 Goldman Sachs.

     3  * Copyright (c) 2015, 2016, Oracle and/or its affiliates. All rights reserved.

     4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     5  *

     6  * This code is free software; you can redistribute it and/or modify it

     7  * under the terms of the GNU General Public License version 2 only, as

     8  * published by the Free Software Foundation.

     9  *

    10  * This code is distributed in the hope that it will be useful, but WITHOUT

    11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    13  * version 2 for more details (a copy is included in the LICENSE file that

    14  * accompanied this code).

    15  *

    16  * You should have received a copy of the GNU General Public License version

    17  * 2 along with this work; if not, write to the Free Software Foundation,

    18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    19  *

    20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

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

    22  * questions.

    23  */

    24 /*

    25  * @test

    26  * @bug 8154049

    27  * @summary Tests the sorting of a large array of sorted primitive values,

    28  *          predominently for cases where the array is nearly sorted. This tests

    29  *          code that detects patterns in the array to determine if it is nearly

    30  *          sorted and if so employs and optimizes merge sort rather than a

    31  *          Dual-Pivot QuickSort.

    32  *

    33  * @run testng SortingNearlySortedPrimitive

    34  */

    35 

    36 import org.testng.annotations.DataProvider;

    37 import org.testng.annotations.Test;

    38 

    39 import java.util.ArrayList;

    40 import java.util.Arrays;

    41 import java.util.List;

    42 import java.util.StringJoiner;

    43 import java.util.function.IntFunction;

    44 import java.util.stream.IntStream;

    45 import java.util.stream.Stream;

    46 

    47 public class SortingNearlySortedPrimitive {

    48 

    49     static final int BASE = 3;

    50     static final int WIDTH = 4;

    51     // Should be > DualPivotQuicksort.QUICKSORT_THRESHOLD

    52     static final int PAD = 300;

    53 

    54     Stream<int[]> createCombinations() {

    55         // Create all combinations for the BASE value and double the WIDTH

    56         // elements

    57         // This is create various combinations of ascending, descending and

    58         // equal runs to exercise the nearly sorted code paths

    59         return IntStream.range(0, (int) Math.pow(BASE, 2 * WIDTH)).

    60                 mapToObj(this::createArray);

    61     }

    62 

    63     // Create an array which at either end is filled with -ve and +ve elements

    64     // according to the base value and padded with zeros in between

    65     int[] createArray(int v) {

    66         int[] a = new int[WIDTH + PAD + WIDTH];

    67 

    68         // Fill head of array

    69         for (int j = 0; j < WIDTH; j++) {

    70             a[j] = (v % BASE) - (BASE / 2);

    71             v /= BASE;

    72         }

    73         // Fill tail of array

    74         for (int j = 0; j < WIDTH; j++) {

    75             a[WIDTH + PAD + j] = (v % BASE) - (BASE / 2);

    76             v /= BASE;

    77         }

    78         return a;

    79     }

    80 

    81     @Test

    82     public void testCombination() {

    83         createCombinations().forEach(a -> {

    84             try {

    85                 // Clone source array to ensure it is not modified

    86                 this.sortAndAssert(a.clone());

    87                 this.sortAndAssert(floatCopyFromInt(a));

    88                 this.sortAndAssert(doubleCopyFromInt(a));

    89                 this.sortAndAssert(longCopyFromInt(a));

    90                 this.sortAndAssert(shortCopyFromInt(a));

    91                 this.sortAndAssert(charCopyFromInt(a));

    92             } catch (AssertionError sae) {

    93                 AssertionError ae = new AssertionError("Sort failed for " + arrayToString(a));

    94                 ae.addSuppressed(sae);

    95                 throw ae;

    96             }

    97         });

    98     }

    99 

   100     String arrayToString(int[] a) {

   101         int[] l = Arrays.copyOfRange(a, 0, WIDTH + 2);

   102         int[] r = Arrays.copyOfRange(a, a.length - (WIDTH + 2), a.length);

   103         StringJoiner sj = new StringJoiner(",", "[", "]");

   104         for (int i : l) {

   105             sj.add(Integer.toString(i));

   106         }

   107         sj.add("...");

   108         for (int i : r) {

   109             sj.add(Integer.toString(i));

   110         }

   111         return sj.toString();

   112     }

   113 

   114 

   115     @DataProvider(name = "shapes")

   116     public Object[][] createShapes() {

   117         Stream<List<Object>> baseCases = Stream.of(

   118                 List.of("hiZeroLowTest", (IntFunction<int[]>) this::hiZeroLowData),

   119                 List.of("endLessThanTest", (IntFunction<int[]>) this::endLessThanData),

   120                 List.of("highFlatLowTest", (IntFunction<int[]>) this::highFlatLowData),

   121                 List.of("identicalTest", (IntFunction<int[]>) this::identicalData),

   122                 List.of("sortedReversedSortedTest", (IntFunction<int[]>) this::sortedReversedSortedData),

   123                 List.of("pairFlipTest", (IntFunction<int[]>) this::pairFlipData),

   124                 List.of("zeroHiTest", (IntFunction<int[]>) this::zeroHiData)

   125         );

   126 

   127         // Ensure the following inequality holds for certain sizes

   128         // DualPivotQuicksort.QUICKSORT_THRESHOLD <= size - 1

   129         //   < DualPivotQuicksort.COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR

   130         // This guarantees that code paths are taken for checking nearly sorted

   131         // arrays for all primitive types

   132         List<Integer> sizes = List.of(100, 1_000, 10_000, 1_000_000);

   133         return baseCases.

   134                 flatMap(l -> sizes.stream().map(s -> append(l, s))).

   135                 toArray(Object[][]::new);

   136     }

   137 

   138     Object[] append(List<Object> l, Object value) {

   139         List<Object> nl = new ArrayList<>(l);

   140         nl.add(value);

   141         return nl.toArray();

   142     }

   143 

   144     @Test(dataProvider = "shapes")

   145     public void testShapes(String testName, IntFunction<int[]> dataMethod, int size) {

   146         int[] intSourceArray = dataMethod.apply(size);

   147 

   148         // Clone source array to ensure it is not modified

   149         this.sortAndAssert(intSourceArray.clone());

   150         this.sortAndAssert(floatCopyFromInt(intSourceArray));

   151         this.sortAndAssert(doubleCopyFromInt(intSourceArray));

   152         this.sortAndAssert(longCopyFromInt(intSourceArray));

   153         this.sortAndAssert(shortCopyFromInt(intSourceArray));

   154         this.sortAndAssert(charCopyFromInt(intSourceArray));

   155     }

   156 

   157     private float[] floatCopyFromInt(int[] src) {

   158         float[] result = new float[src.length];

   159         for (int i = 0; i < result.length; i++) {

   160             result[i] = src[i];

   161         }

   162         return result;

   163     }

   164 

   165     private double[] doubleCopyFromInt(int[] src) {

   166         double[] result = new double[src.length];

   167         for (int i = 0; i < result.length; i++) {

   168             result[i] = src[i];

   169         }

   170         return result;

   171     }

   172 

   173     private long[] longCopyFromInt(int[] src) {

   174         long[] result = new long[src.length];

   175         for (int i = 0; i < result.length; i++) {

   176             result[i] = src[i];

   177         }

   178         return result;

   179     }

   180 

   181     private short[] shortCopyFromInt(int[] src) {

   182         short[] result = new short[src.length];

   183         for (int i = 0; i < result.length; i++) {

   184             result[i] = (short) src[i];

   185         }

   186         return result;

   187     }

   188 

   189     private char[] charCopyFromInt(int[] src) {

   190         char[] result = new char[src.length];

   191         for (int i = 0; i < result.length; i++) {

   192             result[i] = (char) src[i];

   193         }

   194         return result;

   195     }

   196 

   197     private void sortAndAssert(int[] array) {

   198         Arrays.sort(array);

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

   200             if (array[i] < array[i - 1]) {

   201                 throw new AssertionError("not sorted");

   202             }

   203         }

   204     }

   205 

   206     private void sortAndAssert(char[] array) {

   207         Arrays.sort(array);

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

   209             if (array[i] < array[i - 1]) {

   210                 throw new AssertionError("not sorted");

   211             }

   212         }

   213     }

   214 

   215     private void sortAndAssert(short[] array) {

   216         Arrays.sort(array);

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

   218             if (array[i] < array[i - 1]) {

   219                 throw new AssertionError("not sorted");

   220             }

   221         }

   222     }

   223 

   224     private void sortAndAssert(double[] array) {

   225         Arrays.sort(array);

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

   227             if (array[i] < array[i - 1]) {

   228                 throw new AssertionError("not sorted");

   229             }

   230         }

   231     }

   232 

   233     private void sortAndAssert(float[] array) {

   234         Arrays.sort(array);

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

   236             if (array[i] < array[i - 1]) {

   237                 throw new AssertionError("not sorted");

   238             }

   239         }

   240     }

   241 

   242     private void sortAndAssert(long[] array) {

   243         Arrays.sort(array);

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

   245             if (array[i] < array[i - 1]) {

   246                 throw new AssertionError("not sorted");

   247             }

   248         }

   249     }

   250 

   251     private int[] zeroHiData(int size) {

   252         int[] array = new int[size];

   253 

   254         int threeQuarters = (int) (size * 0.75);

   255         for (int i = 0; i < threeQuarters; i++) {

   256             array[i] = 0;

   257         }

   258         int k = 1;

   259         for (int i = threeQuarters; i < size; i++) {

   260             array[i] = k;

   261             k++;

   262         }

   263 

   264         return array;

   265     }

   266 

   267     private int[] hiZeroLowData(int size) {

   268         int[] array = new int[size];

   269 

   270         int oneThird = size / 3;

   271         for (int i = 0; i < oneThird; i++) {

   272             array[i] = i;

   273         }

   274         int twoThirds = oneThird * 2;

   275         for (int i = oneThird; i < twoThirds; i++) {

   276             array[i] = 0;

   277         }

   278         for (int i = twoThirds; i < size; i++) {

   279             array[i] = oneThird - i + twoThirds;

   280         }

   281         return array;

   282     }

   283 

   284     private int[] highFlatLowData(int size) {

   285         int[] array = new int[size];

   286 

   287         int oneThird = size / 3;

   288         for (int i = 0; i < oneThird; i++) {

   289             array[i] = i;

   290         }

   291         int twoThirds = oneThird * 2;

   292         int constant = oneThird - 1;

   293         for (int i = oneThird; i < twoThirds; i++) {

   294             array[i] = constant;

   295         }

   296         for (int i = twoThirds; i < size; i++) {

   297             array[i] = constant - i + twoThirds;

   298         }

   299 

   300         return array;

   301     }

   302 

   303     private int[] identicalData(int size) {

   304         int[] array = new int[size];

   305         int listNumber = 24;

   306 

   307         for (int i = 0; i < size; i++) {

   308             array[i] = listNumber;

   309         }

   310 

   311         return array;

   312     }

   313 

   314     private int[] endLessThanData(int size) {

   315         int[] array = new int[size];

   316 

   317         for (int i = 0; i < size - 1; i++) {

   318             array[i] = 3;

   319         }

   320         array[size - 1] = 1;

   321 

   322         return array;

   323     }

   324 

   325     private int[] sortedReversedSortedData(int size) {

   326         int[] array = new int[size];

   327 

   328         for (int i = 0; i < size / 2; i++) {

   329             array[i] = i;

   330         }

   331         int num = 0;

   332         for (int i = size / 2; i < size; i++) {

   333             array[i] = size - num;

   334             num++;

   335         }

   336 

   337         return array;

   338     }

   339 

   340     private int[] pairFlipData(int size) {

   341         int[] array = new int[size];

   342 

   343         for (int i = 0; i < size; i++) {

   344             array[i] = i;

   345         }

   346         for (int i = 0; i < size; i += 2) {

   347             int temp = array[i];

   348             array[i] = array[i + 1];

   349             array[i + 1] = temp;

   350         }

   351 

   352         return array;

   353     }

   354 }