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 */
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 final static int SMALL_ARRAY_SIZE = 1 << 3;
46
47 //Array size equals MIN_PARTITION
48 private final static int THRESHOLD_ARRAY_SIZE = 1 << 4;
49
50 //Array size greater than MIN_PARTITION
51 private final static int MEDIUM_ARRAY_SIZE = 1 << 8;
52
53 //Array size much greater than MIN_PARTITION
54 private final static int LARGE_ARRAY_SIZE = 1 << 12;
55
56 private final static 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
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
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
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
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 assertEquals(parallelResult, sequentialResult);
125
126 int[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
127 Arrays.parallelPrefix(parallelRangeResult, op);
128 assertEquals(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 assertEquals(parallelResult, sequentialResult);
141
142 long[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
143 Arrays.parallelPrefix(parallelRangeResult, op);
144 assertEquals(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 assertEquals(parallelResult, sequentialResult);
157
158 double[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
159 Arrays.parallelPrefix(parallelRangeResult, op);
160 assertEquals(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 assertEquals(parallelResult, sequentialResult);
173
174 String[] parallelRangeResult = Arrays.copyOfRange(data, fromIndex, toIndex);
175 Arrays.parallelPrefix(parallelRangeResult, op);
176 assertEquals(parallelRangeResult, Arrays.copyOfRange(sequentialResult, fromIndex, toIndex));
177 }
178
179 @Test
180 public void testNPEs() {
181 // null array
182 assertThrows( () -> Arrays.parallelPrefix((int[]) null, Integer::max),
183 NullPointerException.class, "should throw NPE");
184 assertThrows( () -> Arrays.parallelPrefix((long []) null, Long::max),
185 NullPointerException.class, "should throw NPE");
186 assertThrows( () -> Arrays.parallelPrefix((double []) null, Double::max),
187 NullPointerException.class, "should throw NPE");
188 assertThrows( () -> Arrays.parallelPrefix((String []) null, String::concat),
189 NullPointerException.class, "should throw NPE");
190
191 // null array w/ range
192 assertThrows( () -> Arrays.parallelPrefix((int[]) null, 0, 0, Integer::max),
193 NullPointerException.class, "should throw NPE");
194 assertThrows( () -> Arrays.parallelPrefix((long []) null, 0, 0, Long::max),
195 NullPointerException.class, "should throw NPE");
196 assertThrows( () -> Arrays.parallelPrefix((double []) null, 0, 0, Double::max),
197 NullPointerException.class, "should throw NPE");
198 assertThrows( () -> Arrays.parallelPrefix((String []) null, 0, 0, String::concat),
199 NullPointerException.class, "should throw NPE");
200
201 // null op
202 assertThrows( () -> Arrays.parallelPrefix(new int[] {}, null),
203 NullPointerException.class, "should throw NPE");
204 assertThrows( () -> Arrays.parallelPrefix(new long[] {}, null),
205 NullPointerException.class, "should throw NPE");
206 assertThrows( () -> Arrays.parallelPrefix(new double[] {}, null),
207 NullPointerException.class, "should throw NPE");
208 assertThrows( () -> Arrays.parallelPrefix(new String[] {}, null),
209 NullPointerException.class, "should throw NPE");
210
211 // null op w/ range
212 assertThrows( () -> Arrays.parallelPrefix(new int[] {}, 0, 0, null),
213 NullPointerException.class, "should throw NPE");
214 assertThrows( () -> Arrays.parallelPrefix(new long[] {}, 0, 0, null),
215 NullPointerException.class, "should throw NPE");
216 assertThrows( () -> Arrays.parallelPrefix(new double[] {}, 0, 0, null),
217 NullPointerException.class, "should throw NPE");
218 assertThrows( () -> Arrays.parallelPrefix(new String[] {}, 0, 0, null),
219 NullPointerException.class, "should throw NPE");
220 }
221
222 @Test
223 public void testIAEs() {
224 assertThrows( () -> Arrays.parallelPrefix(new int[] {}, 1, 0, Integer::max),
225 IllegalArgumentException.class, "should throw IAE");
226 assertThrows( () -> Arrays.parallelPrefix(new long[] {}, 1, 0, Long::max),
227 IllegalArgumentException.class, "should throw IAE");
228 assertThrows( () -> Arrays.parallelPrefix(new double[] {}, 1, 0, Double::max),
229 IllegalArgumentException.class, "should throw IAE");
230 assertThrows( () -> Arrays.parallelPrefix(new String[] {}, 1, 0, String::concat),
231 IllegalArgumentException.class, "should throw IAE");
232 }
233
234 @Test
235 public void testAIOBEs() {
236 // bad "fromIndex"
237 assertThrows( () -> Arrays.parallelPrefix(new int[] {}, -1, 0, Integer::max),
238 ArrayIndexOutOfBoundsException.class, "should throw AIOBE");
239 assertThrows( () -> Arrays.parallelPrefix(new long[] {}, -1, 0, Long::max),
240 ArrayIndexOutOfBoundsException.class, "should throw AIOBE");
241 assertThrows( () -> Arrays.parallelPrefix(new double[] {}, -1, 0, Double::max),
242 ArrayIndexOutOfBoundsException.class, "should throw AIOBE");
243 assertThrows( () -> Arrays.parallelPrefix(new String[] {}, -1, 0, String::concat),
244 ArrayIndexOutOfBoundsException.class, "should throw AIOBE");
245
246 // bad "toIndex"
247 assertThrows( () -> Arrays.parallelPrefix(new int[] {}, 0, 1, Integer::max),
248 ArrayIndexOutOfBoundsException.class, "should throw AIOBE");
249 assertThrows( () -> Arrays.parallelPrefix(new long[] {}, 0, 1, Long::max),
250 ArrayIndexOutOfBoundsException.class, "should throw AIOBE");
251 assertThrows( () -> Arrays.parallelPrefix(new double[] {}, 0, 1, Double::max),
252 ArrayIndexOutOfBoundsException.class, "should throw AIOBE");
253 assertThrows( () -> Arrays.parallelPrefix(new String[] {}, 0, 1, String::concat),
254 ArrayIndexOutOfBoundsException.class, "should throw AIOBE");
255 }
256
257 // "library" code
258
259 public interface Thrower<T extends Throwable> {
260
261 public void run() throws T;
262 }
263
264
265 public static <T extends Throwable> void assertThrows(Thrower<T> thrower, Class<T> throwable) {
266 assertThrows(thrower, throwable, null);
267 }
268
269 public static <T extends Throwable> void assertThrows(Thrower<T> thrower, Class<T> throwable, String message) {
270 Throwable thrown;
271 try {
272 thrower.run();
273 thrown = null;
274 } catch (Throwable caught) {
275 thrown = caught;
276 }
277
278 assertInstance(thrown, throwable,
279 ((null != message) ? message : "") +
280 " Failed to throw " + throwable.getCanonicalName());
281 }
282
283 public static <T extends Throwable> void assertThrows(Class<T> throwable, String message, Thrower<T>... throwers) {
284 for(Thrower<T> thrower : throwers) {
285 assertThrows(thrower, throwable, message);
286 }
287 }
288
289 public static void assertInstance(Object actual, Class<?> expected) {
290 assertInstance(expected.isInstance(actual), null);
291 }
292
293 public static void assertInstance(Object actual, Class<?> expected, String message) {
294 assertTrue(expected.isInstance(actual), message);
295 }
296 }
297