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