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