1 /*
2 * Copyright (c) 2012, 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 import java.util.ArrayList;
25 import java.util.Arrays;
26 import java.util.Collections;
27 import java.util.Comparator;
28 import java.util.List;
29 import java.util.LinkedList;
30 import java.util.Stack;
31 import java.util.TreeMap;
32 import java.util.TreeSet;
33 import java.util.Vector;
34 import java.util.concurrent.CopyOnWriteArrayList;
35 import java.util.concurrent.atomic.AtomicBoolean;
36 import java.util.concurrent.atomic.AtomicInteger;
37
38 import org.testng.annotations.DataProvider;
39 import org.testng.annotations.Test;
40
41 import static org.testng.Assert.assertEquals;
42 import static org.testng.Assert.assertFalse;
43 import static org.testng.Assert.assertTrue;
44 import static org.testng.Assert.fail;
45
46 import java.lang.reflect.Constructor;
47 import java.util.ConcurrentModificationException;
48 import java.util.function.Predicate;
49
50 /**
51 * @test
52 * @library testlibrary
53 * @build CollectionAsserts CollectionSupplier
54 * @run testng ListDefaults
55 * @summary Unit tests for extension methods on List
56 */
57 public class ListDefaults {
58
59 private static final String[] LIST_CLASSES = {
60 "java.util.ArrayList",
61 "java.util.LinkedList",
62 "java.util.Vector",
63 "java.util.concurrent.CopyOnWriteArrayList"
64 };
65
66 private static final String[] LIST_CME_CLASSES = {
67 "java.util.ArrayList",
68 "java.util.Vector"
69 };
70
71 private static final Predicate<Integer> pEven = x -> 0 == x % 2;
72 private static final Predicate<Integer> pOdd = x -> 1 == x % 2;
73
74 private static final Comparator<Integer> BIT_COUNT_COMPARATOR =
75 (x, y) -> Integer.bitCount(x) - Integer.bitCount(y);
76
77 private static final Comparator<AtomicInteger> ATOMIC_INTEGER_COMPARATOR =
78 (x, y) -> x.intValue() - y.intValue();
79
80 private static final int SIZE = 100;
81 private static final int SUBLIST_FROM = 20;
82 private static final int SUBLIST_TO = SIZE - 5;
83 private static final int SUBLIST_SIZE = SUBLIST_TO - SUBLIST_FROM;
84
85 private static interface Callback {
86 void call(List<Integer> list);
87 }
88
89 // call the callback for each recursive subList
90 private void trimmedSubList(final List<Integer> list, final Callback callback) {
91 int size = list.size();
92 if (size > 1) {
93 // trim 1 element from both ends
94 final List<Integer> subList = list.subList(1, size - 1);
95 callback.call(subList);
96 trimmedSubList(subList, callback);
97 }
98 }
99
100 @DataProvider(name="listProvider", parallel=true)
101 public static Object[][] listCases() {
102 final List<Object[]> cases = new LinkedList<>();
103 cases.add(new Object[] { new ArrayList<>() });
104 cases.add(new Object[] { new LinkedList<>() });
105 cases.add(new Object[] { new Vector<>() });
106 cases.add(new Object[] { new Stack<>() });
107 cases.add(new Object[] { new CopyOnWriteArrayList<>() });
108
109 cases.add(new Object[] { new ArrayList(){{add(42);}} });
110 cases.add(new Object[] { new LinkedList(){{add(42);}} });
111 cases.add(new Object[] { new Vector(){{add(42);}} });
112 cases.add(new Object[] { new Stack(){{add(42);}} });
113 cases.add(new Object[] { new CopyOnWriteArrayList(){{add(42);}} });
114 return cases.toArray(new Object[0][cases.size()]);
115 }
116
117 @Test(dataProvider = "listProvider")
118 public void testProvidedWithNull(final List<Integer> list) throws Exception {
119 try {
120 list.forEach(null);
121 fail("expected NPE not thrown");
122 } catch (NullPointerException npe) {}
123 try {
124 list.replaceAll(null);
125 fail("expected NPE not thrown");
126 } catch (NullPointerException npe) {}
127 try {
128 list.removeIf(null);
129 fail("expected NPE not thrown");
130 } catch (NullPointerException npe) {}
131 }
132
133 @Test
134 public void testForEach() throws Exception {
135 final CollectionSupplier supplier = new CollectionSupplier(LIST_CLASSES, SIZE);
136 for (final CollectionSupplier.TestCase test : supplier.get()) {
137 final List<Integer> original = ((List<Integer>) test.original);
138 final List<Integer> list = ((List<Integer>) test.collection);
139 }
140 for (final CollectionSupplier.TestCase test : supplier.get()) {
141 final List<Integer> original = ((List<Integer>) test.original);
142 final List<Integer> list = ((List<Integer>) test.collection);
143
144 try {
145 list.forEach(null);
146 fail("expected NPE not thrown");
147 } catch (NullPointerException npe) {}
148 CollectionAsserts.assertContents(list, original);
149
150 final List<Integer> actual = new LinkedList<>();
151 list.forEach(actual::add);
152 CollectionAsserts.assertContents(actual, list);
153 CollectionAsserts.assertContents(actual, original);
154
155 if (original.size() > SUBLIST_SIZE) {
156 final List<Integer> subList = original.subList(SUBLIST_FROM, SUBLIST_TO);
157 final List<Integer> actualSubList = new LinkedList<>();
158 subList.forEach(actualSubList::add);
159 assertEquals(actualSubList.size(), SUBLIST_SIZE);
160 for (int i = 0; i < SUBLIST_SIZE; i++) {
161 assertEquals(actualSubList.get(i), original.get(i + SUBLIST_FROM));
162 }
163 }
164
165 trimmedSubList(list, new Callback() {
166 @Override
167 public void call(final List<Integer> list) {
168 final List<Integer> actual = new LinkedList<>();
169 list.forEach(actual::add);
170 CollectionAsserts.assertContents(actual, list);
171 }
172 });
173 }
174 }
175
176 @Test
177 public void testRemoveIf() throws Exception {
178 final CollectionSupplier supplier = new CollectionSupplier(LIST_CLASSES, SIZE);
179
180 for (final CollectionSupplier.TestCase test : supplier.get()) {
181 final List<Integer> original = ((List<Integer>) test.original);
182 final List<Integer> list = ((List<Integer>) test.collection);
183
184 try {
185 list.removeIf(null);
186 fail("expected NPE not thrown");
187 } catch (NullPointerException npe) {}
188 CollectionAsserts.assertContents(list, original);
189
190 final AtomicInteger offset = new AtomicInteger(1);
191 while (list.size() > 0) {
192 removeFirst(original, list, offset);
193 }
194 }
195
196 for (final CollectionSupplier.TestCase test : supplier.get()) {
197 final List<Integer> original = ((List<Integer>) test.original);
198 final List<Integer> list = ((List<Integer>) test.collection);
199 list.removeIf(pOdd);
200 for (int i : list) {
201 assertTrue((i % 2) == 0);
202 }
203 for (int i : original) {
204 if (i % 2 == 0) {
205 assertTrue(list.contains(i));
206 }
207 }
208 list.removeIf(pEven);
209 assertTrue(list.isEmpty());
210 }
211
212 for (final CollectionSupplier.TestCase test : supplier.get()) {
213 final List<Integer> original = ((List<Integer>) test.original);
214 final List<Integer> list = ((List<Integer>) test.collection);
215 final List<Integer> listCopy = new ArrayList<>(list);
216 if (original.size() > SUBLIST_SIZE) {
217 final List<Integer> subList = list.subList(SUBLIST_FROM, SUBLIST_TO);
218 final List<Integer> subListCopy = new ArrayList<>(subList);
219 listCopy.removeAll(subList);
220 subList.removeIf(pOdd);
221 for (int i : subList) {
222 assertTrue((i % 2) == 0);
223 }
224 for (int i : subListCopy) {
225 if (i % 2 == 0) {
226 assertTrue(subList.contains(i));
227 } else {
228 assertFalse(subList.contains(i));
229 }
230 }
231 subList.removeIf(pEven);
232 assertTrue(subList.isEmpty());
233 // elements outside the view should remain
234 CollectionAsserts.assertContents(list, listCopy);
235 }
236 }
237
238 for (final CollectionSupplier.TestCase test : supplier.get()) {
239 final List<Integer> list = ((List<Integer>) test.collection);
240 trimmedSubList(list, new Callback() {
241 @Override
242 public void call(final List<Integer> list) {
243 final List<Integer> copy = new ArrayList<>(list);
244 list.removeIf(pOdd);
245 for (int i : list) {
246 assertTrue((i % 2) == 0);
247 }
248 for (int i : copy) {
249 if (i % 2 == 0) {
250 assertTrue(list.contains(i));
251 } else {
252 assertFalse(list.contains(i));
253 }
254 }
255 }
256 });
257 }
258 }
259
260 // remove the first element
261 private void removeFirst(final List<Integer> original, final List<Integer> list, final AtomicInteger offset) {
262 final AtomicBoolean first = new AtomicBoolean(true);
263 list.removeIf(x -> first.getAndSet(false));
264 CollectionAsserts.assertContents(original.subList(offset.getAndIncrement(), original.size()), list);
265 }
266
267 @Test
268 public void testReplaceAll() throws Exception {
269 final int scale = 3;
270 final CollectionSupplier supplier = new CollectionSupplier(LIST_CLASSES, SIZE);
271 for (final CollectionSupplier.TestCase test : supplier.get()) {
272 final List<Integer> original = ((List<Integer>) test.original);
273 final List<Integer> list = ((List<Integer>) test.collection);
274
275 try {
276 list.replaceAll(null);
277 fail("expected NPE not thrown");
278 } catch (NullPointerException npe) {}
279 CollectionAsserts.assertContents(list, original);
280
281 list.replaceAll(x -> scale * x);
282 for (int i=0; i < original.size(); i++) {
283 assertTrue(list.get(i) == (scale * original.get(i)), "mismatch at index " + i);
284 }
285
286 if (original.size() > SUBLIST_SIZE) {
287 final List<Integer> subList = list.subList(SUBLIST_FROM, SUBLIST_TO);
288 subList.replaceAll(x -> x + 1);
289 // verify elements in view [from, to) were replaced
290 for (int i = 0; i < SUBLIST_SIZE; i++) {
291 assertTrue(subList.get(i) == ((scale * original.get(i + SUBLIST_FROM)) + 1),
292 "mismatch at sublist index " + i);
293 }
294 // verify that elements [0, from) remain unmodified
295 for (int i = 0; i < SUBLIST_FROM; i++) {
296 assertTrue(list.get(i) == (scale * original.get(i)),
297 "mismatch at original index " + i);
298 }
299 // verify that elements [to, size) remain unmodified
300 for (int i = SUBLIST_TO; i < list.size(); i++) {
301 assertTrue(list.get(i) == (scale * original.get(i)),
302 "mismatch at original index " + i);
303 }
304 }
305 }
306
307 for (final CollectionSupplier.TestCase test : supplier.get()) {
308 final List<Integer> list = ((List<Integer>) test.collection);
309 trimmedSubList(list, new Callback() {
310 @Override
311 public void call(final List<Integer> list) {
312 final List<Integer> copy = new ArrayList<>(list);
313 final int offset = 5;
314 list.replaceAll(x -> offset + x);
315 for (int i=0; i < copy.size(); i++) {
316 assertTrue(list.get(i) == (offset + copy.get(i)), "mismatch at index " + i);
317 }
318 }
319 });
320 }
321 }
322
323 @Test
324 public void testSort() throws Exception {
325 final CollectionSupplier supplier = new CollectionSupplier(LIST_CLASSES, SIZE);
326 for (final CollectionSupplier.TestCase test : supplier.get()) {
327 final List<Integer> original = ((List<Integer>) test.original);
328 final List<Integer> list = ((List<Integer>) test.collection);
329 CollectionSupplier.shuffle(list);
330 list.sort(Integer::compare);
331 CollectionAsserts.assertSorted(list, Integer::compare);
332 if (test.name.startsWith("reverse")) {
333 Collections.reverse(list);
334 }
335 CollectionAsserts.assertContents(list, original);
336
337 CollectionSupplier.shuffle(list);
338 list.sort(null);
339 CollectionAsserts.assertSorted(list, Comparator.<Integer>naturalOrder());
340 if (test.name.startsWith("reverse")) {
341 Collections.reverse(list);
342 }
343 CollectionAsserts.assertContents(list, original);
344
345 CollectionSupplier.shuffle(list);
346 list.sort(Comparator.<Integer>naturalOrder());
347 CollectionAsserts.assertSorted(list, Comparator.<Integer>naturalOrder());
348 if (test.name.startsWith("reverse")) {
349 Collections.reverse(list);
350 }
351 CollectionAsserts.assertContents(list, original);
352
353 CollectionSupplier.shuffle(list);
354 list.sort(Comparator.<Integer>reverseOrder());
355 CollectionAsserts.assertSorted(list, Comparator.<Integer>reverseOrder());
356 if (!test.name.startsWith("reverse")) {
357 Collections.reverse(list);
358 }
359 CollectionAsserts.assertContents(list, original);
360
361 CollectionSupplier.shuffle(list);
362 list.sort(BIT_COUNT_COMPARATOR);
363 CollectionAsserts.assertSorted(list, BIT_COUNT_COMPARATOR);
364 // check sort by verifying that bitCount increases and never drops
365 int minBitCount = 0;
366 int bitCount = 0;
367 for (final Integer i : list) {
368 bitCount = Integer.bitCount(i);
369 assertTrue(bitCount >= minBitCount);
370 minBitCount = bitCount;
371 }
372
373 @SuppressWarnings("unchecked")
374 final Class<? extends List<AtomicInteger>> type =
375 (Class<? extends List<AtomicInteger>>) Class.forName(test.className);
376 final Constructor<? extends List<AtomicInteger>> defaultConstructor = type.getConstructor();
377 final List<AtomicInteger> incomparables = (List<AtomicInteger>) defaultConstructor.newInstance();
378
379 for (int i=0; i < test.original.size(); i++) {
380 incomparables.add(new AtomicInteger(i));
381 }
382 CollectionSupplier.shuffle(incomparables);
383 incomparables.sort(ATOMIC_INTEGER_COMPARATOR);
384 for (int i=0; i < test.original.size(); i++) {
385 assertEquals(i, incomparables.get(i).intValue());
386 }
387
388 if (original.size() > SUBLIST_SIZE) {
389 final List<Integer> copy = new ArrayList<>(list);
390 final List<Integer> subList = list.subList(SUBLIST_FROM, SUBLIST_TO);
391 CollectionSupplier.shuffle(subList);
392 subList.sort(Comparator.<Integer>naturalOrder());
393 CollectionAsserts.assertSorted(subList, Comparator.<Integer>naturalOrder());
394 // verify that elements [0, from) remain unmodified
395 for (int i = 0; i < SUBLIST_FROM; i++) {
396 assertTrue(list.get(i) == copy.get(i),
397 "mismatch at index " + i);
398 }
399 // verify that elements [to, size) remain unmodified
400 for (int i = SUBLIST_TO; i < list.size(); i++) {
401 assertTrue(list.get(i) == copy.get(i),
402 "mismatch at index " + i);
403 }
404 }
405 }
406
407 for (final CollectionSupplier.TestCase test : supplier.get()) {
408 final List<Integer> list = ((List<Integer>) test.collection);
409 trimmedSubList(list, new Callback() {
410 @Override
411 public void call(final List<Integer> list) {
412 final List<Integer> copy = new ArrayList<>(list);
413 CollectionSupplier.shuffle(list);
414 list.sort(Comparator.<Integer>naturalOrder());
415 CollectionAsserts.assertSorted(list, Comparator.<Integer>naturalOrder());
416 }
417 });
418 }
419 }
420
421 @Test
422 public void testForEachThrowsCME() throws Exception {
423 final CollectionSupplier supplier = new CollectionSupplier(LIST_CME_CLASSES, SIZE);
424 for (final CollectionSupplier.TestCase test : supplier.get()) {
425 final List<Integer> list = ((List<Integer>) test.collection);
426 if (list.size() <= 1) {
427 continue;
428 }
429 boolean gotException = false;
430 try {
431 // bad predicate that modifies its list, should throw CME
432 list.forEach((x) -> {list.add(x);});
433 } catch (ConcurrentModificationException cme) {
434 gotException = true;
435 }
436 if (!gotException) {
437 fail("expected CME was not thrown from " + test);
438 }
439 }
440 }
441
442 @Test
443 public void testRemoveIfThrowsCME() throws Exception {
444 final CollectionSupplier supplier = new CollectionSupplier(LIST_CME_CLASSES, SIZE);
445 for (final CollectionSupplier.TestCase test : supplier.get()) {
446 final List<Integer> list = ((List<Integer>) test.collection);
447 if (list.size() <= 1) {
448 continue;
449 }
450 boolean gotException = false;
451 try {
452 // bad predicate that modifies its list, should throw CME
453 list.removeIf((x) -> {return list.add(x);});
454 } catch (ConcurrentModificationException cme) {
455 gotException = true;
456 }
457 if (!gotException) {
458 fail("expected CME was not thrown from " + test);
459 }
460 }
461 }
462
463 @Test
464 public void testReplaceAllThrowsCME() throws Exception {
465 final CollectionSupplier supplier = new CollectionSupplier(LIST_CME_CLASSES, SIZE);
466 for (final CollectionSupplier.TestCase test : supplier.get()) {
467 final List<Integer> list = ((List<Integer>) test.collection);
468 if (list.size() <= 1) {
469 continue;
470 }
471 boolean gotException = false;
472 try {
473 // bad predicate that modifies its list, should throw CME
474 list.replaceAll(x -> {int n = 3 * x; list.add(n); return n;});
475 } catch (ConcurrentModificationException cme) {
476 gotException = true;
477 }
478 if (!gotException) {
479 fail("expected CME was not thrown from " + test);
480 }
481 }
482 }
483
484 @Test
485 public void testSortThrowsCME() throws Exception {
486 final CollectionSupplier supplier = new CollectionSupplier(LIST_CME_CLASSES, SIZE);
487 for (final CollectionSupplier.TestCase test : supplier.get()) {
488 final List<Integer> list = ((List<Integer>) test.collection);
489 if (list.size() <= 1) {
490 continue;
491 }
492 boolean gotException = false;
493 try {
494 // bad predicate that modifies its list, should throw CME
495 list.sort((x, y) -> {list.add(x); return x - y;});
496 } catch (ConcurrentModificationException cme) {
497 gotException = true;
498 }
499 if (!gotException) {
500 fail("expected CME was not thrown from " + test);
501 }
502 }
503 }
504
505 private static final List<Integer> SLICED_EXPECTED = Arrays.asList(0, 1, 2, 3, 5, 6, 7, 8, 9);
506 private static final List<Integer> SLICED_EXPECTED2 = Arrays.asList(0, 1, 2, 5, 6, 7, 8, 9);
507
508 @DataProvider(name="shortIntListProvider", parallel=true)
509 public static Object[][] intListCases() {
510 final Integer[] DATA = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
511 final List<Object[]> cases = new LinkedList<>();
512 cases.add(new Object[] { new ArrayList<>(Arrays.asList(DATA)) });
513 cases.add(new Object[] { new LinkedList<>(Arrays.asList(DATA)) });
514 cases.add(new Object[] { new Vector<>(Arrays.asList(DATA)) });
515 cases.add(new Object[] { new CopyOnWriteArrayList<>(Arrays.asList(DATA)) });
516 return cases.toArray(new Object[0][cases.size()]);
517 }
518
519 @Test(dataProvider = "shortIntListProvider")
520 public void testRemoveIfFromSlice(final List<Integer> list) throws Exception {
521 final List<Integer> sublist = list.subList(3, 6);
522 assertTrue(sublist.removeIf(x -> x == 4));
523 CollectionAsserts.assertContents(list, SLICED_EXPECTED);
524
525 final List<Integer> sublist2 = list.subList(2, 5);
526 assertTrue(sublist2.removeIf(x -> x == 3));
527 CollectionAsserts.assertContents(list, SLICED_EXPECTED2);
528 }
529 }