1 /*
2 * Copyright (c) 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 /**
25 * @test 8014076 8025067
26 * @summary unit test for Arrays.ParallelPrefix().
27 * @author Tristan Yan
28 * @run testng ParallelPrefix
29 * @key intermittent
30 */
31
32 import java.util.Arrays;
33 import java.util.function.BinaryOperator;
34 import java.util.function.DoubleBinaryOperator;
35 import java.util.function.Function;
36 import java.util.function.IntBinaryOperator;
37 import java.util.function.LongBinaryOperator;
38 import java.util.stream.IntStream;
39 import java.util.stream.LongStream;
40 import static org.testng.Assert.*;
41 import org.testng.annotations.DataProvider;
42 import org.testng.annotations.Test;
43
44 public class ParallelPrefix {
45 //Array size less than MIN_PARTITION
46 private static final int SMALL_ARRAY_SIZE = 1 << 3;
47
48 //Array size equals MIN_PARTITION
49 private static final int THRESHOLD_ARRAY_SIZE = 1 << 4;
50
51 //Array size greater than MIN_PARTITION
52 private static final int MEDIUM_ARRAY_SIZE = 1 << 8;
53
54 //Array size much greater than MIN_PARTITION
55 private static final int LARGE_ARRAY_SIZE = 1 << 14;
56
57 private static final int[] ARRAY_SIZE_COLLECTION = new int[]{
58 SMALL_ARRAY_SIZE,
59 THRESHOLD_ARRAY_SIZE,
60 MEDIUM_ARRAY_SIZE,
61 LARGE_ARRAY_SIZE
62 };
63
64 @DataProvider(name = "intSet")
65 public static Object[][] intSet(){
66 return genericData(size -> IntStream.range(0, size).toArray(),
67 new IntBinaryOperator[]{
68 Integer::sum,
69 Integer::min});
70 }
71
72 @DataProvider(name = "longSet")
73 public static Object[][] longSet(){
74 return genericData(size -> LongStream.range(0, size).toArray(),
75 new LongBinaryOperator[]{
76 Long::sum,
77 Long::min});
78 }
79
80 @DataProvider(name = "doubleSet")
81 public static Object[][] doubleSet(){
82 return genericData(size -> IntStream.range(0, size).mapToDouble(i -> (double)i).toArray(),
83 new DoubleBinaryOperator[]{
84 Double::sum,
85 Double::min});
86 }
87
88 @DataProvider(name = "stringSet")
89 public static Object[][] stringSet(){
90 Function<Integer, String[]> stringsFunc = size ->
91 IntStream.range(0, size).mapToObj(Integer::toString).toArray(String[]::new);
92 BinaryOperator<String> concat = String::concat;
93 return genericData(stringsFunc,
94 (BinaryOperator<String>[]) new BinaryOperator[]{
95 concat });
96 }
97
98 private static <T, OPS> Object[][] genericData(Function<Integer, T> generateFunc, OPS[] ops) {
99 //test arrays which size is equals n-1, n, n+1, test random data
100 Object[][] data = new Object[ARRAY_SIZE_COLLECTION.length * 3 * ops.length][4];
101 for(int n = 0; n < ARRAY_SIZE_COLLECTION.length; n++ ) {
102 for(int testValue = -1 ; testValue <= 1; testValue++) {
103 int array_size = ARRAY_SIZE_COLLECTION[n] + testValue;
104 for(int opsN = 0; opsN < ops.length; opsN++) {
105 int index = n * 3 * ops.length + (testValue + 1) * ops.length + opsN;
106 data[index][0] = generateFunc.apply(array_size);
107 data[index][1] = array_size / 3;
108 data[index][2] = 2 * array_size / 3;
109 data[index][3] = ops[opsN];
110 }
111 }
112 }
113 return data;
114 }
115
116 @Test(dataProvider="intSet")
117 public void testParallelPrefixForInt(int[] data, int fromIndex, int toIndex, IntBinaryOperator op) {
118 int[] sequentialResult = data.clone();
119 for (int index = fromIndex + 1; index < toIndex; index++) {
120 sequentialResult[index ] = op.applyAsInt(sequentialResult[index - 1], sequentialResult[index]);
121 }
122
123 int[] parallelResult = data.clone();
124 Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);
125 assertArraysEqual(parallelResult, sequentialResult);
126
127 int[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
128 Arrays.parallelPrefix(parallelRangeResult, op);
129 assertArraysEqual(parallelRangeResult, Arrays.copyOfRange(sequentialResult, fromIndex, toIndex));
130 }
131
132 @Test(dataProvider="longSet")
133 public void testParallelPrefixForLong(long[] data, int fromIndex, int toIndex, LongBinaryOperator op) {
134 long[] sequentialResult = data.clone();
135 for (int index = fromIndex + 1; index < toIndex; index++) {
136 sequentialResult[index ] = op.applyAsLong(sequentialResult[index - 1], sequentialResult[index]);
137 }
138
139 long[] parallelResult = data.clone();
140 Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);
141 assertArraysEqual(parallelResult, sequentialResult);
142
143 long[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
144 Arrays.parallelPrefix(parallelRangeResult, op);
145 assertArraysEqual(parallelRangeResult, Arrays.copyOfRange(sequentialResult, fromIndex, toIndex));
146 }
147
148 @Test(dataProvider="doubleSet")
149 public void testParallelPrefixForDouble(double[] data, int fromIndex, int toIndex, DoubleBinaryOperator op) {
150 double[] sequentialResult = data.clone();
151 for (int index = fromIndex + 1; index < toIndex; index++) {
152 sequentialResult[index ] = op.applyAsDouble(sequentialResult[index - 1], sequentialResult[index]);
153 }
154
155 double[] parallelResult = data.clone();
156 Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);
157 assertArraysEqual(parallelResult, sequentialResult);
158
159 double[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
160 Arrays.parallelPrefix(parallelRangeResult, op);
161 assertArraysEqual(parallelRangeResult, Arrays.copyOfRange(sequentialResult, fromIndex, toIndex));
162 }
163
164 @Test(dataProvider="stringSet")
165 public void testParallelPrefixForStringr(String[] data , int fromIndex, int toIndex, BinaryOperator<String> op) {
166 String[] sequentialResult = data.clone();
167 for (int index = fromIndex + 1; index < toIndex; index++) {
168 sequentialResult[index ] = op.apply(sequentialResult[index - 1], sequentialResult[index]);
169 }
170
171 String[] parallelResult = data.clone();
172 Arrays.parallelPrefix(parallelResult, fromIndex, toIndex, op);
173 assertArraysEqual(parallelResult, sequentialResult);
174
175 String[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
176 Arrays.parallelPrefix(parallelRangeResult, op);
177 assertArraysEqual(parallelRangeResult, Arrays.copyOfRange(sequentialResult, fromIndex, toIndex));
178 }
179
180 @Test
181 public void testNPEs() {
182 // null array
183 assertThrows( () -> Arrays.parallelPrefix((int[]) null, Integer::max),
184 NullPointerException.class, "should throw NPE");
185 assertThrows( () -> Arrays.parallelPrefix((long []) null, Long::max),
186 NullPointerException.class, "should throw NPE");
187 assertThrows( () -> Arrays.parallelPrefix((double []) null, Double::max),
188 NullPointerException.class, "should throw NPE");
189 assertThrows( () -> Arrays.parallelPrefix((String []) null, String::concat),
190 NullPointerException.class, "should throw NPE");
191
192 // null array w/ range
193 assertThrows( () -> Arrays.parallelPrefix((int[]) null, 0, 0, Integer::max),
194 NullPointerException.class, "should throw NPE");
195 assertThrows( () -> Arrays.parallelPrefix((long []) null, 0, 0, Long::max),
196 NullPointerException.class, "should throw NPE");
197 assertThrows( () -> Arrays.parallelPrefix((double []) null, 0, 0, Double::max),
198 NullPointerException.class, "should throw NPE");
199 assertThrows( () -> Arrays.parallelPrefix((String []) null, 0, 0, String::concat),
200 NullPointerException.class, "should throw NPE");
201
202 // null op
203 assertThrows( () -> Arrays.parallelPrefix(new int[] {}, null),
204 NullPointerException.class, "should throw NPE");
205 assertThrows( () -> Arrays.parallelPrefix(new long[] {}, null),
206 NullPointerException.class, "should throw NPE");
207 assertThrows( () -> Arrays.parallelPrefix(new double[] {}, null),
208 NullPointerException.class, "should throw NPE");
209 assertThrows( () -> Arrays.parallelPrefix(new String[] {}, null),
210 NullPointerException.class, "should throw NPE");
211
212 // null op w/ range
213 assertThrows( () -> Arrays.parallelPrefix(new int[] {}, 0, 0, null),
214 NullPointerException.class, "should throw NPE");
215 assertThrows( () -> Arrays.parallelPrefix(new long[] {}, 0, 0, null),
216 NullPointerException.class, "should throw NPE");
217 assertThrows( () -> Arrays.parallelPrefix(new double[] {}, 0, 0, null),
218 NullPointerException.class, "should throw NPE");
219 assertThrows( () -> Arrays.parallelPrefix(new String[] {}, 0, 0, null),
220 NullPointerException.class, "should throw NPE");
221 }
222
223 @Test
224 public void testIAEs() {
225 assertThrows( () -> Arrays.parallelPrefix(new int[] {}, 1, 0, Integer::max),
226 IllegalArgumentException.class, "should throw IAE");
227 assertThrows( () -> Arrays.parallelPrefix(new long[] {}, 1, 0, Long::max),
228 IllegalArgumentException.class, "should throw IAE");
229 assertThrows( () -> Arrays.parallelPrefix(new double[] {}, 1, 0, Double::max),
230 IllegalArgumentException.class, "should throw IAE");
231 assertThrows( () -> Arrays.parallelPrefix(new String[] {}, 1, 0, String::concat),
232 IllegalArgumentException.class, "should throw IAE");
233 }
234
235 @Test
236 public void testAIOBEs() {
237 // bad "fromIndex"
238 assertThrows( () -> Arrays.parallelPrefix(new int[] {}, -1, 0, Integer::max),
239 ArrayIndexOutOfBoundsException.class, "should throw AIOBE");
240 assertThrows( () -> Arrays.parallelPrefix(new long[] {}, -1, 0, Long::max),
241 ArrayIndexOutOfBoundsException.class, "should throw AIOBE");
242 assertThrows( () -> Arrays.parallelPrefix(new double[] {}, -1, 0, Double::max),
243 ArrayIndexOutOfBoundsException.class, "should throw AIOBE");
244 assertThrows( () -> Arrays.parallelPrefix(new String[] {}, -1, 0, String::concat),
245 ArrayIndexOutOfBoundsException.class, "should throw AIOBE");
246
247 // bad "toIndex"
248 assertThrows( () -> Arrays.parallelPrefix(new int[] {}, 0, 1, Integer::max),
249 ArrayIndexOutOfBoundsException.class, "should throw AIOBE");
250 assertThrows( () -> Arrays.parallelPrefix(new long[] {}, 0, 1, Long::max),
251 ArrayIndexOutOfBoundsException.class, "should throw AIOBE");
252 assertThrows( () -> Arrays.parallelPrefix(new double[] {}, 0, 1, Double::max),
253 ArrayIndexOutOfBoundsException.class, "should throw AIOBE");
254 assertThrows( () -> Arrays.parallelPrefix(new String[] {}, 0, 1, String::concat),
255 ArrayIndexOutOfBoundsException.class, "should throw AIOBE");
256 }
257
258 // "library" code
259
260 public interface Thrower<T extends Throwable> {
261
262 public void run() throws T;
263 }
264
265
266 public static <T extends Throwable> void assertThrows(Thrower<T> thrower, Class<T> throwable) {
267 assertThrows(thrower, throwable, null);
268 }
269
270 public static <T extends Throwable> void assertThrows(Thrower<T> thrower, Class<T> throwable, String message) {
271 Throwable thrown;
272 try {
273 thrower.run();
274 thrown = null;
275 } catch (Throwable caught) {
276 thrown = caught;
277 }
278
279 assertInstance(thrown, throwable,
280 ((null != message) ? message : "") +
281 " Failed to throw " + throwable.getCanonicalName());
282 }
283
284 public static <T extends Throwable> void assertThrows(Class<T> throwable, String message, Thrower<T>... throwers) {
285 for(Thrower<T> thrower : throwers) {
286 assertThrows(thrower, throwable, message);
287 }
288 }
289
290 public static void assertInstance(Object actual, Class<?> expected) {
291 assertInstance(expected.isInstance(actual), null);
292 }
293
294 public static void assertInstance(Object actual, Class<?> expected, String message) {
295 assertTrue(expected.isInstance(actual), message);
296 }
297
298 static void assertArraysEqual(int[] actual, int[] expected) {
299 try {
300 assertEquals(actual, expected, "");
301 } catch (AssertionError x) {
302 throw new AssertionError(String.format("Expected:%s, actual:%s",
303 Arrays.toString(expected), Arrays.toString(actual)), x);
304 }
305 }
306
307 static void assertArraysEqual(long[] actual, long[] expected) {
308 try {
309 assertEquals(actual, expected, "");
310 } catch (AssertionError x) {
311 throw new AssertionError(String.format("Expected:%s, actual:%s",
312 Arrays.toString(expected), Arrays.toString(actual)), x);
313 }
314 }
315
316 static void assertArraysEqual(double[] actual, double[] expected) {
317 try {
318 assertEquals(actual, expected, "");
319 } catch (AssertionError x) {
320 throw new AssertionError(String.format("Expected:%s, actual:%s",
321 Arrays.toString(expected), Arrays.toString(actual)), x);
322 }
323 }
324
325 static void assertArraysEqual(String[] actual, String[] expected) {
326 try {
327 assertEquals(actual, expected, "");
328 } catch (AssertionError x) {
329 throw new AssertionError(String.format("Expected:%s, actual:%s",
330 Arrays.toString(expected), Arrays.toString(actual)), x);
331 }
332 }
333 }
334