1 /*

     2  * Copyright (c) 2013, 2017, 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 /**

    25  * @test 8014076 8025067

    26  * @summary unit test for Arrays.ParallelPrefix().

    27  * @author Tristan Yan

    28  * @run testng ParallelPrefix

    29  */

    30 

    31 import java.util.Arrays;

    32 import java.util.function.BinaryOperator;

    33 import java.util.function.DoubleBinaryOperator;

    34 import java.util.function.Function;

    35 import java.util.function.IntBinaryOperator;

    36 import java.util.function.LongBinaryOperator;

    37 import java.util.stream.IntStream;

    38 import java.util.stream.LongStream;

    39 import static org.testng.Assert.*;

    40 import org.testng.annotations.DataProvider;

    41 import org.testng.annotations.Test;

    42 

    43 public class ParallelPrefix {

    44     //Array size less than MIN_PARTITION

    45     private static final int SMALL_ARRAY_SIZE = 1 << 3;

    46 

    47     //Array size equals MIN_PARTITION

    48     private static final int THRESHOLD_ARRAY_SIZE = 1 << 4;

    49 

    50     //Array size greater than MIN_PARTITION

    51     private static final int MEDIUM_ARRAY_SIZE = 1 << 8;

    52 

    53     //Array size much greater than MIN_PARTITION

    54     private static final int LARGE_ARRAY_SIZE = 1 << 14;

    55 

    56     private static final int[] ARRAY_SIZE_COLLECTION  = new int[]{

    57         SMALL_ARRAY_SIZE,

    58         THRESHOLD_ARRAY_SIZE,

    59         MEDIUM_ARRAY_SIZE,

    60         LARGE_ARRAY_SIZE

    61     };

    62 

    63     @DataProvider(name = "intSet")

    64     public static Object[][] intSet(){

    65         return genericData(size -> IntStream.range(0, size).toArray(),

    66                 new IntBinaryOperator[]{

    67                     Integer::sum,

    68                     Integer::min});

    69     }

    70 

    71     @DataProvider(name = "longSet")

    72     public static Object[][] longSet(){

    73         return genericData(size -> LongStream.range(0, size).toArray(),

    74                 new LongBinaryOperator[]{

    75                     Long::sum,

    76                     Long::min});

    77     }

    78 

    79     @DataProvider(name = "doubleSet")

    80     public static Object[][] doubleSet(){

    81         return genericData(size -> IntStream.range(0, size).mapToDouble(i -> (double)i).toArray(),

    82                 new DoubleBinaryOperator[]{

    83                     Double::sum,

    84                     Double::min});

    85     }

    86 

    87     @DataProvider(name = "stringSet")

    88     public static Object[][] stringSet(){

    89         Function<Integer, String[]> stringsFunc = size ->

    90                 IntStream.range(0, size).mapToObj(Integer::toString).toArray(String[]::new);

    91         BinaryOperator<String> concat = String::concat;

    92         return genericData(stringsFunc,

    93                 (BinaryOperator<String>[]) new BinaryOperator[]{

    94                     concat });

    95     }

    96 

    97     private static <T, OPS> Object[][] genericData(Function<Integer, T> generateFunc, OPS[] ops) {

    98         //test arrays which size is equals n-1, n, n+1, test random data

    99         Object[][] data = new Object[ARRAY_SIZE_COLLECTION.length * 3 * ops.length][4];

   100         for(int n = 0; n < ARRAY_SIZE_COLLECTION.length; n++ ) {

   101             for(int testValue = -1 ; testValue <= 1; testValue++) {

   102                 int array_size = ARRAY_SIZE_COLLECTION[n] + testValue;

   103                 for(int opsN = 0; opsN < ops.length; opsN++) {

   104                     int index = n * 3 * ops.length + (testValue + 1) * ops.length + opsN;

   105                     data[index][0] = generateFunc.apply(array_size);

   106                     data[index][1] = array_size / 3;

   107                     data[index][2] = 2 * array_size / 3;

   108                     data[index][3] = ops[opsN];

   109                 }

   110             }

   111         }

   112         return data;

   113     }

   114 

   115     @Test(dataProvider="intSet")

   116     public void testParallelPrefixForInt(int[] data, int fromIndex, int toIndex, IntBinaryOperator op) {

   117         int[] sequentialResult = data.clone();

   118         for (int index = fromIndex + 1; index < toIndex; index++) {

   119             sequentialResult[index ] = op.applyAsInt(sequentialResult[index  - 1], sequentialResult[index]);

   120         }

   121 

   122         int[] parallelResult = data.clone();

   123         Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);

   124         assertArraysEqual(parallelResult, sequentialResult);

   125 

   126         int[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);

   127         Arrays.parallelPrefix(parallelRangeResult, op);

   128         assertArraysEqual(parallelRangeResult, Arrays.copyOfRange(sequentialResult, fromIndex, toIndex));

   129     }

   130 

   131     @Test(dataProvider="longSet")

   132     public void testParallelPrefixForLong(long[] data, int fromIndex, int toIndex, LongBinaryOperator op) {

   133         long[] sequentialResult = data.clone();

   134         for (int index = fromIndex + 1; index < toIndex; index++) {

   135             sequentialResult[index ] = op.applyAsLong(sequentialResult[index  - 1], sequentialResult[index]);

   136         }

   137 

   138         long[] parallelResult = data.clone();

   139         Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);

   140         assertArraysEqual(parallelResult, sequentialResult);

   141 

   142         long[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);

   143         Arrays.parallelPrefix(parallelRangeResult, op);

   144         assertArraysEqual(parallelRangeResult, Arrays.copyOfRange(sequentialResult, fromIndex, toIndex));

   145     }

   146 

   147     @Test(dataProvider="doubleSet")

   148     public void testParallelPrefixForDouble(double[] data, int fromIndex, int toIndex, DoubleBinaryOperator op) {

   149         double[] sequentialResult = data.clone();

   150         for (int index = fromIndex + 1; index < toIndex; index++) {

   151             sequentialResult[index ] = op.applyAsDouble(sequentialResult[index  - 1], sequentialResult[index]);

   152         }

   153 

   154         double[] parallelResult = data.clone();

   155         Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);

   156         assertArraysEqual(parallelResult, sequentialResult);

   157 

   158         double[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);

   159         Arrays.parallelPrefix(parallelRangeResult, op);

   160         assertArraysEqual(parallelRangeResult, Arrays.copyOfRange(sequentialResult, fromIndex, toIndex));

   161     }

   162 

   163     @Test(dataProvider="stringSet")

   164     public void testParallelPrefixForStringr(String[] data , int fromIndex, int toIndex, BinaryOperator<String> op) {

   165         String[] sequentialResult = data.clone();

   166         for (int index = fromIndex + 1; index < toIndex; index++) {

   167             sequentialResult[index ] = op.apply(sequentialResult[index  - 1], sequentialResult[index]);

   168         }

   169 

   170         String[] parallelResult = data.clone();

   171         Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);

   172         assertArraysEqual(parallelResult, sequentialResult);

   173 

   174         String[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);

   175         Arrays.parallelPrefix(parallelRangeResult, op);

   176         assertArraysEqual(parallelRangeResult, Arrays.copyOfRange(sequentialResult, fromIndex, toIndex));

   177     }

   178 

   179     @Test

   180     public void testNPEs() {

   181         // null array

   182         assertThrowsNPE(() -> Arrays.parallelPrefix((int[]) null, Integer::max));

   183         assertThrowsNPE(() -> Arrays.parallelPrefix((long []) null, Long::max));

   184         assertThrowsNPE(() -> Arrays.parallelPrefix((double []) null, Double::max));

   185         assertThrowsNPE(() -> Arrays.parallelPrefix((String []) null, String::concat));

   186 

   187         // null array w/ range

   188         assertThrowsNPE(() -> Arrays.parallelPrefix((int[]) null, 0, 0, Integer::max));

   189         assertThrowsNPE(() -> Arrays.parallelPrefix((long []) null, 0, 0, Long::max));

   190         assertThrowsNPE(() -> Arrays.parallelPrefix((double []) null, 0, 0, Double::max));

   191         assertThrowsNPE(() -> Arrays.parallelPrefix((String []) null, 0, 0, String::concat));

   192 

   193         // null op

   194         assertThrowsNPE(() -> Arrays.parallelPrefix(new int[] {}, null));

   195         assertThrowsNPE(() -> Arrays.parallelPrefix(new long[] {}, null));

   196         assertThrowsNPE(() -> Arrays.parallelPrefix(new double[] {}, null));

   197         assertThrowsNPE(() -> Arrays.parallelPrefix(new String[] {}, null));

   198 

   199         // null op w/ range

   200         assertThrowsNPE(() -> Arrays.parallelPrefix(new int[] {}, 0, 0, null));

   201         assertThrowsNPE(() -> Arrays.parallelPrefix(new long[] {}, 0, 0, null));

   202         assertThrowsNPE(() -> Arrays.parallelPrefix(new double[] {}, 0, 0, null));

   203         assertThrowsNPE(() -> Arrays.parallelPrefix(new String[] {}, 0, 0, null));

   204     }

   205 

   206     @Test

   207     public void testIAEs() {

   208         assertThrowsIAE(() -> Arrays.parallelPrefix(new int[] {}, 1, 0, Integer::max));

   209         assertThrowsIAE(() -> Arrays.parallelPrefix(new long[] {}, 1, 0, Long::max));

   210         assertThrowsIAE(() -> Arrays.parallelPrefix(new double[] {}, 1, 0, Double::max));

   211         assertThrowsIAE(() -> Arrays.parallelPrefix(new String[] {}, 1, 0, String::concat));

   212     }

   213 

   214     @Test

   215     public void testAIOOBEs() {

   216         // bad "fromIndex"

   217         assertThrowsAIOOB(() -> Arrays.parallelPrefix(new int[] {}, -1, 0, Integer::max));

   218         assertThrowsAIOOB(() -> Arrays.parallelPrefix(new long[] {}, -1, 0, Long::max));

   219         assertThrowsAIOOB(() -> Arrays.parallelPrefix(new double[] {}, -1, 0, Double::max));

   220         assertThrowsAIOOB(() -> Arrays.parallelPrefix(new String[] {}, -1, 0, String::concat));

   221 

   222         // bad "toIndex"

   223         assertThrowsAIOOB(() -> Arrays.parallelPrefix(new int[] {}, 0, 1, Integer::max));

   224         assertThrowsAIOOB(() -> Arrays.parallelPrefix(new long[] {}, 0, 1, Long::max));

   225         assertThrowsAIOOB(() -> Arrays.parallelPrefix(new double[] {}, 0, 1, Double::max));

   226         assertThrowsAIOOB(() -> Arrays.parallelPrefix(new String[] {}, 0, 1, String::concat));

   227     }

   228 

   229     // "library" code

   230 

   231     private void assertThrowsNPE(ThrowingRunnable r) {

   232         assertThrows(NullPointerException.class, r);

   233     }

   234 

   235     private void assertThrowsIAE(ThrowingRunnable r) {

   236         assertThrows(IllegalArgumentException.class, r);

   237     }

   238 

   239     private void assertThrowsAIOOB(ThrowingRunnable r) {

   240         assertThrows(ArrayIndexOutOfBoundsException.class, r);

   241     }

   242 

   243     static void assertArraysEqual(int[] actual, int[] expected) {

   244         try {

   245             assertEquals(actual, expected, "");

   246         } catch (AssertionError x) {

   247             throw new AssertionError(String.format("Expected:%s, actual:%s",

   248                     Arrays.toString(expected), Arrays.toString(actual)), x);

   249         }

   250     }

   251 

   252     static void assertArraysEqual(long[] actual, long[] expected) {

   253         try {

   254             assertEquals(actual, expected, "");

   255         } catch (AssertionError x) {

   256             throw new AssertionError(String.format("Expected:%s, actual:%s",

   257                     Arrays.toString(expected), Arrays.toString(actual)), x);

   258         }

   259     }

   260 

   261     static void assertArraysEqual(double[] actual, double[] expected) {

   262         try {

   263             assertEquals(actual, expected, "");

   264         } catch (AssertionError x) {

   265             throw new AssertionError(String.format("Expected:%s, actual:%s",

   266                     Arrays.toString(expected), Arrays.toString(actual)), x);

   267         }

   268     }

   269 

   270     static void assertArraysEqual(String[] actual, String[] expected) {

   271         try {

   272             assertEquals(actual, expected, "");

   273         } catch (AssertionError x) {

   274             throw new AssertionError(String.format("Expected:%s, actual:%s",

   275                     Arrays.toString(expected), Arrays.toString(actual)), x);

   276         }

   277     }

   278 }

   279