1 /*

     2  * Copyright (c) 2011, 2013, Oracle and/or its affiliates. All rights reserved.

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

     4  *

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

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

     7  * published by the Free Software Foundation.

     8  *

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

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

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

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

    13  * accompanied this code).

    14  *

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

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

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

    18  *

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

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

    21  * questions.

    22  */

    23 

    24 /* Adapted from test/java/util/Arrays/Sorting.java

    25  *

    26  * Where that test checks Arrays.sort against manual quicksort routines,

    27  * this test checks parallelSort against either Arrays.sort or manual

    28  * quicksort routines.

    29  */

    30 

    31 /*

    32  * @test

    33  * @bug 8003981

    34  * @run main ParallelSorting -shortrun

    35  * @summary Exercise Arrays.parallelSort (adapted from test Sorting)

    36  *

    37  * @author Vladimir Yaroslavskiy

    38  * @author Jon Bentley

    39  * @author Josh Bloch

    40  */

    41 

    42 import java.util.Arrays;

    43 import java.util.Random;

    44 import java.io.PrintStream;

    45 import java.util.Comparator;

    46 

    47 public class ParallelSorting {

    48     private static final PrintStream out = System.out;

    49     private static final PrintStream err = System.err;

    50 

    51     // Array lengths used in a long run (default)

    52     private static final int[] LONG_RUN_LENGTHS = {

    53         1000, 10000, 100000, 1000000 };

    54 

    55     // Array lengths used in a short run

    56     private static final int[] SHORT_RUN_LENGTHS = {

    57         5000, 9000, 10000, 12000 };

    58 

    59     // Random initial values used in a long run (default)

    60     private static final long[] LONG_RUN_RANDOMS = { 666, 0xC0FFEE, 999 };

    61 

    62     // Random initial values used in a short run

    63     private static final long[] SHORT_RUN_RANDOMS = { 666 };

    64 

    65     public static void main(String[] args) {

    66         boolean shortRun = args.length > 0 && args[0].equals("-shortrun");

    67         long start = System.currentTimeMillis();

    68 

    69         if (shortRun) {

    70             testAndCheck(SHORT_RUN_LENGTHS, SHORT_RUN_RANDOMS);

    71         } else {

    72             testAndCheck(LONG_RUN_LENGTHS, LONG_RUN_RANDOMS);

    73         }

    74         long end = System.currentTimeMillis();

    75 

    76         out.format("PASSED in %d sec.\n", Math.round((end - start) / 1E3));

    77     }

    78 

    79     private static void testAndCheck(int[] lengths, long[] randoms) {

    80         testEmptyAndNullIntArray();

    81         testEmptyAndNullLongArray();

    82         testEmptyAndNullShortArray();

    83         testEmptyAndNullCharArray();

    84         testEmptyAndNullByteArray();

    85         testEmptyAndNullFloatArray();

    86         testEmptyAndNullDoubleArray();

    87 

    88         for (int length : lengths) {

    89             testMergeSort(length);

    90             testAndCheckRange(length);

    91             testAndCheckSubArray(length);

    92         }

    93         for (long seed : randoms) {

    94             for (int length : lengths) {

    95                 testAndCheckWithInsertionSort(length, new MyRandom(seed));

    96                 testAndCheckWithCheckSum(length, new MyRandom(seed));

    97                 testAndCheckWithScrambling(length, new MyRandom(seed));

    98                 testAndCheckFloat(length, new MyRandom(seed));

    99                 testAndCheckDouble(length, new MyRandom(seed));

   100                 testStable(length, new MyRandom(seed));

   101             }

   102         }

   103     }

   104 

   105     private static void testEmptyAndNullIntArray() {

   106         ourDescription = "Check empty and null array";

   107         Arrays.parallelSort(new int[]{});

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

   109 

   110         try {

   111             Arrays.parallelSort((int[]) null);

   112         } catch (NullPointerException expected) {

   113             try {

   114                 Arrays.parallelSort((int[]) null, 0, 0);

   115             } catch (NullPointerException expected2) {

   116                 return;

   117             }

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

   119                 "catch null array");

   120         }

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

   122     }

   123 

   124     private static void testEmptyAndNullLongArray() {

   125         ourDescription = "Check empty and null array";

   126         Arrays.parallelSort(new long[]{});

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

   128 

   129         try {

   130             Arrays.parallelSort((long[]) null);

   131         } catch (NullPointerException expected) {

   132             try {

   133                 Arrays.parallelSort((long[]) null, 0, 0);

   134             } catch (NullPointerException expected2) {

   135                 return;

   136             }

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

   138                 "catch null array");

   139         }

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

   141     }

   142 

   143     private static void testEmptyAndNullShortArray() {

   144         ourDescription = "Check empty and null array";

   145         Arrays.parallelSort(new short[]{});

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

   147 

   148         try {

   149             Arrays.parallelSort((short[]) null);

   150         } catch (NullPointerException expected) {

   151             try {

   152                 Arrays.parallelSort((short[]) null, 0, 0);

   153             } catch (NullPointerException expected2) {

   154                 return;

   155             }

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

   157                 "catch null array");

   158         }

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

   160     }

   161 

   162     private static void testEmptyAndNullCharArray() {

   163         ourDescription = "Check empty and null array";

   164         Arrays.parallelSort(new char[]{});

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

   166 

   167         try {

   168             Arrays.parallelSort((char[]) null);

   169         } catch (NullPointerException expected) {

   170             try {

   171                 Arrays.parallelSort((char[]) null, 0, 0);

   172             } catch (NullPointerException expected2) {

   173                 return;

   174             }

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

   176                 "catch null array");

   177         }

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

   179     }

   180 

   181     private static void testEmptyAndNullByteArray() {

   182         ourDescription = "Check empty and null array";

   183         Arrays.parallelSort(new byte[]{});

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

   185 

   186         try {

   187             Arrays.parallelSort((byte[]) null);

   188         } catch (NullPointerException expected) {

   189             try {

   190                 Arrays.parallelSort((byte[]) null, 0, 0);

   191             } catch (NullPointerException expected2) {

   192                 return;

   193             }

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

   195                 "catch null array");

   196         }

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

   198     }

   199 

   200     private static void testEmptyAndNullFloatArray() {

   201         ourDescription = "Check empty and null array";

   202         Arrays.parallelSort(new float[]{});

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

   204 

   205         try {

   206             Arrays.parallelSort((float[]) null);

   207         } catch (NullPointerException expected) {

   208             try {

   209                 Arrays.parallelSort((float[]) null, 0, 0);

   210             } catch (NullPointerException expected2) {

   211                 return;

   212             }

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

   214                 "catch null array");

   215         }

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

   217     }

   218 

   219     private static void testEmptyAndNullDoubleArray() {

   220         ourDescription = "Check empty and null array";

   221         Arrays.parallelSort(new double[]{});

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

   223 

   224         try {

   225             Arrays.parallelSort((double[]) null);

   226         } catch (NullPointerException expected) {

   227             try {

   228                 Arrays.parallelSort((double[]) null, 0, 0);

   229             } catch (NullPointerException expected2) {

   230                 return;

   231             }

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

   233                 "catch null array");

   234         }

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

   236     }

   237 

   238     private static void testAndCheckSubArray(int length) {

   239         ourDescription = "Check sorting of subarray";

   240         int[] golden = new int[length];

   241         boolean newLine = false;

   242 

   243         for (int m = 1; m < length / 2; m *= 2) {

   244             newLine = true;

   245             int fromIndex = m;

   246             int toIndex = length - m;

   247 

   248             prepareSubArray(golden, fromIndex, toIndex, m);

   249             int[] test = golden.clone();

   250 

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

   252                 out.println("Test 'subarray': " + converter +

   253                    " length = " + length + ", m = " + m);

   254                 Object convertedGolden = converter.convert(golden);

   255                 Object convertedTest = converter.convert(test);

   256                 sortSubArray(convertedTest, fromIndex, toIndex);

   257                 checkSubArray(convertedTest, fromIndex, toIndex, m);

   258             }

   259         }

   260         if (newLine) {

   261             out.println();

   262         }

   263     }

   264 

   265     private static void testAndCheckRange(int length) {

   266         ourDescription = "Check range check";

   267         int[] golden = new int[length];

   268 

   269         for (int m = 1; m < 2 * length; m *= 2) {

   270             for (int i = 1; i <= length; i++) {

   271                 golden[i - 1] = i % m + m % i;

   272             }

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

   274                 out.println("Test 'range': " + converter +

   275                    ", length = " + length + ", m = " + m);

   276                 Object convertedGolden = converter.convert(golden);

   277                 checkRange(convertedGolden, m);

   278             }

   279         }

   280         out.println();

   281     }

   282 

   283     private static void testStable(int length, MyRandom random) {

   284         ourDescription = "Check if sorting is stable";

   285         Pair[] a = build(length, random);

   286 

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

   288             ", length = " + length);

   289         Arrays.parallelSort(a);

   290         checkSorted(a);

   291         checkStable(a);

   292         out.println();

   293 

   294         a = build(length, random);

   295 

   296         out.println("Test 'stable' comparator: " + "random = " + random.getSeed() +

   297             ", length = " + length);

   298         Arrays.parallelSort(a, pairCmp);

   299         checkSorted(a);

   300         checkStable(a);

   301         out.println();

   302 

   303     }

   304 

   305     private static void checkSorted(Pair[] a) {

   306         for (int i = 0; i < a.length - 1; i++) {

   307             if (a[i].getKey() > a[i + 1].getKey()) {

   308                 failedSort(i, "" + a[i].getKey(), "" + a[i + 1].getKey());

   309             }

   310         }

   311     }

   312 

   313     private static void checkStable(Pair[] a) {

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

   315             int key1 = a[i].getKey();

   316             int value1 = a[i++].getValue();

   317             int key2 = a[i].getKey();

   318             int value2 = a[i++].getValue();

   319             int key3 = a[i].getKey();

   320             int value3 = a[i++].getValue();

   321             int key4 = a[i].getKey();

   322             int value4 = a[i++].getValue();

   323 

   324             if (!(key1 == key2 && key2 == key3 && key3 == key4)) {

   325                 failed("On position " + i + " keys are different " +

   326                     key1 + ", " + key2 + ", " + key3 + ", " + key4);

   327             }

   328             if (!(value1 < value2 && value2 < value3 && value3 < value4)) {

   329                 failed("Sorting is not stable at position " + i +

   330                     ". Second values have been changed: " +  value1 + ", " +

   331                     value2 + ", " + value3 + ", " + value4);

   332             }

   333         }

   334     }

   335 

   336     private static Pair[] build(int length, Random random) {

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

   338 

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

   340             int key = random.nextInt();

   341             a[i++] = new Pair(key, 1);

   342             a[i++] = new Pair(key, 2);

   343             a[i++] = new Pair(key, 3);

   344             a[i++] = new Pair(key, 4);

   345         }

   346         return a;

   347     }

   348 

   349     private static Comparator<Pair> pairCmp = new Comparator<Pair>() {

   350         public int compare(Pair p1, Pair p2) {

   351             return p1.compareTo(p2);

   352         }

   353     };

   354 

   355     private static final class Pair implements Comparable<Pair> {

   356         Pair(int key, int value) {

   357             myKey = key;

   358             myValue = value;

   359         }

   360 

   361         int getKey() {

   362             return myKey;

   363         }

   364 

   365         int getValue() {

   366             return myValue;

   367         }

   368 

   369         public int compareTo(Pair pair) {

   370             if (myKey < pair.myKey) {

   371                 return -1;

   372             }

   373             if (myKey > pair.myKey) {

   374                 return 1;

   375             }

   376             return 0;

   377         }

   378 

   379         @Override

   380         public String toString() {

   381             return "(" + myKey + ", " + myValue + ")";

   382         }

   383 

   384         private int myKey;

   385         private int myValue;

   386     }

   387 

   388 

   389     private static void testAndCheckWithInsertionSort(int length, MyRandom random) {

   390         if (length > 1000) {

   391             return;

   392         }

   393         ourDescription = "Check sorting with insertion sort";

   394         int[] golden = new int[length];

   395 

   396         for (int m = 1; m < 2 * length; m *= 2) {

   397             for (UnsortedBuilder builder : UnsortedBuilder.values()) {

   398                 builder.build(golden, m, random);

   399                 int[] test = golden.clone();

   400 

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

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

   403                         " " + builder + "random = " + random.getSeed() +

   404                         ", length = " + length + ", m = " + m);

   405                     Object convertedGolden = converter.convert(golden);

   406                     Object convertedTest1 = converter.convert(test);

   407                     Object convertedTest2 = converter.convert(test);

   408                     sort(convertedTest1);

   409                     sortByInsertionSort(convertedTest2);

   410                     compare(convertedTest1, convertedTest2);

   411                 }

   412             }

   413         }

   414         out.println();

   415     }

   416 

   417     private static void testMergeSort(int length) {

   418         if (length < 1000) {

   419             return;

   420         }

   421         ourDescription = "Check merge sorting";

   422         int[] golden = new int[length];

   423         int period = 67; // java.util.DualPivotQuicksort.MAX_RUN_COUNT

   424 

   425         for (int m = period - 2; m <= period + 2; m++) {

   426             for (MergeBuilder builder : MergeBuilder.values()) {

   427                 builder.build(golden, m);

   428                 int[] test = golden.clone();

   429 

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

   431                     out.println("Test 'merge sort': " + converter + " " +

   432                         builder + "length = " + length + ", m = " + m);

   433                     Object convertedGolden = converter.convert(golden);

   434                     sort(convertedGolden);

   435                     checkSorted(convertedGolden);

   436                 }

   437             }

   438         }

   439         out.println();

   440     }

   441 

   442     private static void testAndCheckWithCheckSum(int length, MyRandom random) {

   443         ourDescription = "Check sorting with check sum";

   444         int[] golden = new int[length];

   445 

   446         for (int m = 1; m < 2 * length; m *= 2) {

   447             for (UnsortedBuilder builder : UnsortedBuilder.values()) {

   448                 builder.build(golden, m, random);

   449                 int[] test = golden.clone();

   450 

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

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

   453                         " " + builder + "random = " + random.getSeed() +

   454                         ", length = " + length + ", m = " + m);

   455                     Object convertedGolden = converter.convert(golden);

   456                     Object convertedTest = converter.convert(test);

   457                     sort(convertedTest);

   458                     checkWithCheckSum(convertedTest, convertedGolden);

   459                 }

   460             }

   461         }

   462         out.println();

   463     }

   464 

   465     private static void testAndCheckWithScrambling(int length, MyRandom random) {

   466         ourDescription = "Check sorting with scrambling";

   467         int[] golden = new int[length];

   468 

   469         for (int m = 1; m <= 7; m++) {

   470             if (m > length) {

   471                 break;

   472             }

   473             for (SortedBuilder builder : SortedBuilder.values()) {

   474                 builder.build(golden, m);

   475                 int[] test = golden.clone();

   476                 scramble(test, random);

   477 

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

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

   480                        " " + builder + "random = " + random.getSeed() +

   481                        ", length = " + length + ", m = " + m);

   482                     Object convertedGolden = converter.convert(golden);

   483                     Object convertedTest = converter.convert(test);

   484                     sort(convertedTest);

   485                     compare(convertedTest, convertedGolden);

   486                 }

   487             }

   488         }

   489         out.println();

   490     }

   491 

   492     private static void testAndCheckFloat(int length, MyRandom random) {

   493         ourDescription = "Check float sorting";

   494         float[] golden = new float[length];

   495         final int MAX = 10;

   496         boolean newLine = false;

   497 

   498         for (int a = 0; a <= MAX; a++) {

   499             for (int g = 0; g <= MAX; g++) {

   500                 for (int z = 0; z <= MAX; z++) {

   501                     for (int n = 0; n <= MAX; n++) {

   502                         for (int p = 0; p <= MAX; p++) {

   503                             if (a + g + z + n + p > length) {

   504                                 continue;

   505                             }

   506                             if (a + g + z + n + p < length) {

   507                                 continue;

   508                             }

   509                             for (FloatBuilder builder : FloatBuilder.values()) {

   510                                 out.println("Test 'float': random = " + random.getSeed() +

   511                                    ", length = " + length + ", a = " + a + ", g = " +

   512                                    g + ", z = " + z + ", n = " + n + ", p = " + p);

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

   514                                 float[] test = golden.clone();

   515                                 scramble(test, random);

   516                                 sort(test);

   517                                 compare(test, golden, a, n, g);

   518                             }

   519                             newLine = true;

   520                         }

   521                     }

   522                 }

   523             }

   524         }

   525         if (newLine) {

   526             out.println();

   527         }

   528     }

   529 

   530     private static void testAndCheckDouble(int length, MyRandom random) {

   531         ourDescription = "Check double sorting";

   532         double[] golden = new double[length];

   533         final int MAX = 10;

   534         boolean newLine = false;

   535 

   536         for (int a = 0; a <= MAX; a++) {

   537             for (int g = 0; g <= MAX; g++) {

   538                 for (int z = 0; z <= MAX; z++) {

   539                     for (int n = 0; n <= MAX; n++) {

   540                         for (int p = 0; p <= MAX; p++) {

   541                             if (a + g + z + n + p > length) {

   542                                 continue;

   543                             }

   544                             if (a + g + z + n + p < length) {

   545                                 continue;

   546                             }

   547                             for (DoubleBuilder builder : DoubleBuilder.values()) {

   548                                 out.println("Test 'double': random = " + random.getSeed() +

   549                                    ", length = " + length + ", a = " + a + ", g = " +

   550                                    g + ", z = " + z + ", n = " + n + ", p = " + p);

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

   552                                 double[] test = golden.clone();

   553                                 scramble(test, random);

   554                                 sort(test);

   555                                 compare(test, golden, a, n, g);

   556                             }

   557                             newLine = true;

   558                         }

   559                     }

   560                 }

   561             }

   562         }

   563         if (newLine) {

   564             out.println();

   565         }

   566     }

   567 

   568     private static void prepareSubArray(int[] a, int fromIndex, int toIndex, int m) {

   569         for (int i = 0; i < fromIndex; i++) {

   570             a[i] = 0xDEDA;

   571         }

   572         int middle = (fromIndex + toIndex) >>> 1;

   573         int k = 0;

   574 

   575         for (int i = fromIndex; i < middle; i++) {

   576             a[i] = k++;

   577         }

   578         for (int i = middle; i < toIndex; i++) {

   579             a[i] = k--;

   580         }

   581         for (int i = toIndex; i < a.length; i++) {

   582             a[i] = 0xBABA;

   583         }

   584     }

   585 

   586     private static void scramble(int[] a, Random random) {

   587         for (int i = 0; i < a.length * 7; i++) {

   588             swap(a, random.nextInt(a.length), random.nextInt(a.length));

   589         }

   590     }

   591 

   592     private static void scramble(float[] a, Random random) {

   593         for (int i = 0; i < a.length * 7; i++) {

   594             swap(a, random.nextInt(a.length), random.nextInt(a.length));

   595         }

   596     }

   597 

   598     private static void scramble(double[] a, Random random) {

   599         for (int i = 0; i < a.length * 7; i++) {

   600             swap(a, random.nextInt(a.length), random.nextInt(a.length));

   601         }

   602     }

   603 

   604     private static void swap(int[] a, int i, int j) {

   605         int t = a[i];

   606         a[i] = a[j];

   607         a[j] = t;

   608     }

   609 

   610     private static void swap(float[] a, int i, int j) {

   611         float t = a[i];

   612         a[i] = a[j];

   613         a[j] = t;

   614     }

   615 

   616     private static void swap(double[] a, int i, int j) {

   617         double t = a[i];

   618         a[i] = a[j];

   619         a[j] = t;

   620     }

   621 

   622     private static enum TypeConverter {

   623         INT {

   624             Object convert(int[] a) {

   625                 return a.clone();

   626             }

   627         },

   628         LONG {

   629             Object convert(int[] a) {

   630                 long[] b = new long[a.length];

   631 

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

   633                     b[i] = (long) a[i];

   634                 }

   635                 return b;

   636             }

   637         },

   638         BYTE {

   639             Object convert(int[] a) {

   640                 byte[] b = new byte[a.length];

   641 

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

   643                     b[i] = (byte) a[i];

   644                 }

   645                 return b;

   646             }

   647         },

   648         SHORT {

   649             Object convert(int[] a) {

   650                 short[] b = new short[a.length];

   651 

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

   653                     b[i] = (short) a[i];

   654                 }

   655                 return b;

   656             }

   657         },

   658         CHAR {

   659             Object convert(int[] a) {

   660                 char[] b = new char[a.length];

   661 

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

   663                     b[i] = (char) a[i];

   664                 }

   665                 return b;

   666             }

   667         },

   668         FLOAT {

   669             Object convert(int[] a) {

   670                 float[] b = new float[a.length];

   671 

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

   673                     b[i] = (float) a[i];

   674                 }

   675                 return b;

   676             }

   677         },

   678         DOUBLE {

   679             Object convert(int[] a) {

   680                 double[] b = new double[a.length];

   681 

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

   683                     b[i] = (double) a[i];

   684                 }

   685                 return b;

   686             }

   687         },

   688         INTEGER {

   689             Object convert(int[] a) {

   690                 Integer[] b = new Integer[a.length];

   691 

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

   693                     b[i] = new Integer(a[i]);

   694                 }

   695                 return b;

   696             }

   697         };

   698 

   699         abstract Object convert(int[] a);

   700 

   701         @Override public String toString() {

   702             String name = name();

   703 

   704             for (int i = name.length(); i < 9; i++) {

   705                 name += " ";

   706             }

   707             return name;

   708         }

   709     }

   710 

   711     private static enum FloatBuilder {

   712         SIMPLE {

   713             void build(float[] x, int a, int g, int z, int n, int p, Random random) {

   714                 int fromIndex = 0;

   715                 float negativeValue = -random.nextFloat();

   716                 float positiveValue =  random.nextFloat();

   717 

   718                 writeValue(x, negativeValue, fromIndex, n);

   719                 fromIndex += n;

   720 

   721                 writeValue(x, -0.0f, fromIndex, g);

   722                 fromIndex += g;

   723 

   724                 writeValue(x, 0.0f, fromIndex, z);

   725                 fromIndex += z;

   726 

   727                 writeValue(x, positiveValue, fromIndex, p);

   728                 fromIndex += p;

   729 

   730                 writeValue(x, Float.NaN, fromIndex, a);

   731             }

   732         };

   733 

   734         abstract void build(float[] x, int a, int g, int z, int n, int p, Random random);

   735     }

   736 

   737     private static enum DoubleBuilder {

   738         SIMPLE {

   739             void build(double[] x, int a, int g, int z, int n, int p, Random random) {

   740                 int fromIndex = 0;

   741                 double negativeValue = -random.nextFloat();

   742                 double positiveValue =  random.nextFloat();

   743 

   744                 writeValue(x, negativeValue, fromIndex, n);

   745                 fromIndex += n;

   746 

   747                 writeValue(x, -0.0d, fromIndex, g);

   748                 fromIndex += g;

   749 

   750                 writeValue(x, 0.0d, fromIndex, z);

   751                 fromIndex += z;

   752 

   753                 writeValue(x, positiveValue, fromIndex, p);

   754                 fromIndex += p;

   755 

   756                 writeValue(x, Double.NaN, fromIndex, a);

   757             }

   758         };

   759 

   760         abstract void build(double[] x, int a, int g, int z, int n, int p, Random random);

   761     }

   762 

   763     private static void writeValue(float[] a, float value, int fromIndex, int count) {

   764         for (int i = fromIndex; i < fromIndex + count; i++) {

   765             a[i] = value;

   766         }

   767     }

   768 

   769     private static void compare(float[] a, float[] b, int numNaN, int numNeg, int numNegZero) {

   770         for (int i = a.length - numNaN; i < a.length; i++) {

   771             if (a[i] == a[i]) {

   772                 failed("On position " + i + " must be NaN instead of " + a[i]);

   773             }

   774         }

   775         final int NEGATIVE_ZERO = Float.floatToIntBits(-0.0f);

   776 

   777         for (int i = numNeg; i < numNeg + numNegZero; i++) {

   778             if (NEGATIVE_ZERO != Float.floatToIntBits(a[i])) {

   779                 failed("On position " + i + " must be -0.0 instead of " + a[i]);

   780             }

   781         }

   782         for (int i = 0; i < a.length - numNaN; i++) {

   783             if (a[i] != b[i]) {

   784                 failedCompare(i, "" + a[i], "" + b[i]);

   785             }

   786         }

   787     }

   788 

   789     private static void writeValue(double[] a, double value, int fromIndex, int count) {

   790         for (int i = fromIndex; i < fromIndex + count; i++) {

   791             a[i] = value;

   792         }

   793     }

   794 

   795     private static void compare(double[] a, double[] b, int numNaN, int numNeg, int numNegZero) {

   796         for (int i = a.length - numNaN; i < a.length; i++) {

   797             if (a[i] == a[i]) {

   798                 failed("On position " + i + " must be NaN instead of " + a[i]);

   799             }

   800         }

   801         final long NEGATIVE_ZERO = Double.doubleToLongBits(-0.0d);

   802 

   803         for (int i = numNeg; i < numNeg + numNegZero; i++) {

   804             if (NEGATIVE_ZERO != Double.doubleToLongBits(a[i])) {

   805                 failed("On position " + i + " must be -0.0 instead of " + a[i]);

   806             }

   807         }

   808         for (int i = 0; i < a.length - numNaN; i++) {

   809             if (a[i] != b[i]) {

   810                 failedCompare(i, "" + a[i], "" + b[i]);

   811             }

   812         }

   813     }

   814 

   815     private static enum SortedBuilder {

   816         REPEATED {

   817             void build(int[] a, int m) {

   818                 int period = a.length / m;

   819                 int i = 0;

   820                 int k = 0;

   821 

   822                 while (true) {

   823                     for (int t = 1; t <= period; t++) {

   824                         if (i >= a.length) {

   825                             return;

   826                         }

   827                         a[i++] = k;

   828                     }

   829                     if (i >= a.length) {

   830                         return;

   831                     }

   832                     k++;

   833                 }

   834             }

   835         },

   836         ORGAN_PIPES {

   837             void build(int[] a, int m) {

   838                 int i = 0;

   839                 int k = m;

   840 

   841                 while (true) {

   842                     for (int t = 1; t <= m; t++) {

   843                         if (i >= a.length) {

   844                             return;

   845                         }

   846                         a[i++] = k;

   847                     }

   848                 }

   849             }

   850         };

   851 

   852         abstract void build(int[] a, int m);

   853 

   854         @Override public String toString() {

   855             String name = name();

   856 

   857             for (int i = name.length(); i < 12; i++) {

   858                 name += " ";

   859             }

   860             return name;

   861         }

   862     }

   863 

   864     private static enum MergeBuilder {

   865         ASCENDING {

   866             void build(int[] a, int m) {

   867                 int period = a.length / m;

   868                 int v = 1, i = 0;

   869 

   870                 for (int k = 0; k < m; k++) {

   871                     v = 1;

   872                     for (int p = 0; p < period; p++) {

   873                         a[i++] = v++;

   874                     }

   875                 }

   876                 for (int j = i; j < a.length - 1; j++) {

   877                     a[j] = v++;

   878                 }

   879                 a[a.length - 1] = 0;

   880             }

   881         },

   882         DESCENDING {

   883             void build(int[] a, int m) {

   884                 int period = a.length / m;

   885                 int v = -1, i = 0;

   886 

   887                 for (int k = 0; k < m; k++) {

   888                     v = -1;

   889                     for (int p = 0; p < period; p++) {

   890                         a[i++] = v--;

   891                     }

   892                 }

   893                 for (int j = i; j < a.length - 1; j++) {

   894                     a[j] = v--;

   895                 }

   896                 a[a.length - 1] = 0;

   897             }

   898         };

   899 

   900         abstract void build(int[] a, int m);

   901 

   902         @Override public String toString() {

   903             String name = name();

   904 

   905             for (int i = name.length(); i < 12; i++) {

   906                 name += " ";

   907             }

   908             return name;

   909         }

   910     }

   911 

   912     private static enum UnsortedBuilder {

   913         RANDOM {

   914             void build(int[] a, int m, Random random) {

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

   916                     a[i] = random.nextInt();

   917                 }

   918             }

   919         },

   920         ASCENDING {

   921             void build(int[] a, int m, Random random) {

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

   923                     a[i] = m + i;

   924                 }

   925             }

   926         },

   927         DESCENDING {

   928             void build(int[] a, int m, Random random) {

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

   930                     a[i] = a.length - m - i;

   931                 }

   932             }

   933         },

   934         ALL_EQUAL {

   935             void build(int[] a, int m, Random random) {

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

   937                     a[i] = m;

   938                 }

   939             }

   940         },

   941         SAW {

   942             void build(int[] a, int m, Random random) {

   943                 int incCount = 1;

   944                 int decCount = a.length;

   945                 int i = 0;

   946                 int period = m--;

   947 

   948                 while (true) {

   949                     for (int k = 1; k <= period; k++) {

   950                         if (i >= a.length) {

   951                             return;

   952                         }

   953                         a[i++] = incCount++;

   954                     }

   955                     period += m;

   956 

   957                     for (int k = 1; k <= period; k++) {

   958                         if (i >= a.length) {

   959                             return;

   960                         }

   961                         a[i++] = decCount--;

   962                     }

   963                     period += m;

   964                 }

   965             }

   966         },

   967         REPEATED {

   968             void build(int[] a, int m, Random random) {

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

   970                     a[i] = i % m;

   971                 }

   972             }

   973         },

   974         DUPLICATED {

   975             void build(int[] a, int m, Random random) {

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

   977                     a[i] = random.nextInt(m);

   978                 }

   979             }

   980         },

   981         ORGAN_PIPES {

   982             void build(int[] a, int m, Random random) {

   983                 int middle = a.length / (m + 1);

   984 

   985                 for (int i = 0; i < middle; i++) {

   986                     a[i] = i;

   987                 }

   988                 for (int i = middle; i < a.length; i++) {

   989                     a[i] = a.length - i - 1;

   990                 }

   991             }

   992         },

   993         STAGGER {

   994             void build(int[] a, int m, Random random) {

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

   996                     a[i] = (i * m + i) % a.length;

   997                 }

   998             }

   999         },

  1000         PLATEAU {

  1001             void build(int[] a, int m, Random random) {

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

  1003                     a[i] = Math.min(i, m);

  1004                 }

  1005             }

  1006         },

  1007         SHUFFLE {

  1008             void build(int[] a, int m, Random random) {

  1009                 int x = 0, y = 0;

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

  1011                     a[i] = random.nextBoolean() ? (x += 2) : (y += 2);

  1012                 }

  1013             }

  1014         };

  1015 

  1016         abstract void build(int[] a, int m, Random random);

  1017 

  1018         @Override public String toString() {

  1019             String name = name();

  1020 

  1021             for (int i = name.length(); i < 12; i++) {

  1022                 name += " ";

  1023             }

  1024             return name;

  1025         }

  1026     }

  1027 

  1028     private static void checkWithCheckSum(Object test, Object golden) {

  1029         checkSorted(test);

  1030         checkCheckSum(test, golden);

  1031     }

  1032 

  1033     private static void failed(String message) {

  1034         err.format("\n*** TEST FAILED - %s.\n\n%s.\n\n", ourDescription, message);

  1035         throw new RuntimeException("Test failed - see log file for details");

  1036     }

  1037 

  1038     private static void failedSort(int index, String value1, String value2) {

  1039         failed("Array is not sorted at " + index + "-th position: " +

  1040             value1 + " and " + value2);

  1041     }

  1042 

  1043     private static void failedCompare(int index, String value1, String value2) {

  1044         failed("On position " + index + " must be " + value2 + " instead of " + value1);

  1045     }

  1046 

  1047     private static void compare(Object test, Object golden) {

  1048         if (test instanceof int[]) {

  1049             compare((int[]) test, (int[]) golden);

  1050         } else if (test instanceof long[]) {

  1051             compare((long[]) test, (long[]) golden);

  1052         } else if (test instanceof short[]) {

  1053             compare((short[]) test, (short[]) golden);

  1054         } else if (test instanceof byte[]) {

  1055             compare((byte[]) test, (byte[]) golden);

  1056         } else if (test instanceof char[]) {

  1057             compare((char[]) test, (char[]) golden);

  1058         } else if (test instanceof float[]) {

  1059             compare((float[]) test, (float[]) golden);

  1060         } else if (test instanceof double[]) {

  1061             compare((double[]) test, (double[]) golden);

  1062         } else if (test instanceof Integer[]) {

  1063             compare((Integer[]) test, (Integer[]) golden);

  1064         } else {

  1065             failed("Unknow type of array: " + test + " of class " +

  1066                 test.getClass().getName());

  1067         }

  1068     }

  1069 

  1070     private static void compare(int[] a, int[] b) {

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

  1072             if (a[i] != b[i]) {

  1073                 failedCompare(i, "" + a[i], "" + b[i]);

  1074             }

  1075         }

  1076     }

  1077 

  1078     private static void compare(long[] a, long[] b) {

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

  1080             if (a[i] != b[i]) {

  1081                 failedCompare(i, "" + a[i], "" + b[i]);

  1082             }

  1083         }

  1084     }

  1085 

  1086     private static void compare(short[] a, short[] b) {

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

  1088             if (a[i] != b[i]) {

  1089                 failedCompare(i, "" + a[i], "" + b[i]);

  1090             }

  1091         }

  1092     }

  1093 

  1094     private static void compare(byte[] a, byte[] b) {

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

  1096             if (a[i] != b[i]) {

  1097                 failedCompare(i, "" + a[i], "" + b[i]);

  1098             }

  1099         }

  1100     }

  1101 

  1102     private static void compare(char[] a, char[] b) {

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

  1104             if (a[i] != b[i]) {

  1105                 failedCompare(i, "" + a[i], "" + b[i]);

  1106             }

  1107         }

  1108     }

  1109 

  1110     private static void compare(float[] a, float[] b) {

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

  1112             if (a[i] != b[i]) {

  1113                 failedCompare(i, "" + a[i], "" + b[i]);

  1114             }

  1115         }

  1116     }

  1117 

  1118     private static void compare(double[] a, double[] b) {

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

  1120             if (a[i] != b[i]) {

  1121                 failedCompare(i, "" + a[i], "" + b[i]);

  1122             }

  1123         }

  1124     }

  1125 

  1126     private static void compare(Integer[] a, Integer[] b) {

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

  1128             if (a[i].compareTo(b[i]) != 0) {

  1129                 failedCompare(i, "" + a[i], "" + b[i]);

  1130             }

  1131         }

  1132     }

  1133 

  1134     private static void checkSorted(Object object) {