1 /* 2 * Copyright (c) 2005, 2015, 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 26 * @bug 6207984 6272521 6192552 6269713 6197726 6260652 5073546 4137464 27 * 4155650 4216399 4294891 6282555 6318622 6355327 6383475 6420753 28 * 6431845 4802633 6570566 6570575 6570631 6570924 6691185 6691215 29 * 4802647 7123424 8024709 30 * @summary Run many tests on many Collection and Map implementations 31 * @author Martin Buchholz 32 * @modules java.base/java.util:open 33 * @run main MOAT 34 * @key randomness 35 */ 36 37 /* Mother Of All (Collection) Tests 38 * 39 * Testing of collection classes is often spotty, because many tests 40 * need to be performed on many implementations, but the onus on 41 * writing the tests falls on the engineer introducing the new 42 * implementation. 43 * 44 * The idea of this mega-test is that: 45 * 46 * An engineer adding a new collection implementation could simply add 47 * their new implementation to a list of implementations in this 48 * test's main method. Any general purpose Collection<Integer> or 49 * Map<Integer,Integer> class is appropriate. 50 * 51 * An engineer fixing a regression could add their regression test here and 52 * simultaneously test all other implementations. 53 */ 54 55 import java.io.*; 56 import java.util.*; 57 import java.util.concurrent.*; 58 import static java.util.Collections.*; 59 import java.lang.reflect.*; 60 61 public class MOAT { 62 // Collections under test must not be initialized to contain this value, 63 // and maps under test must not contain this value as a key. 64 // It's used as a sentinel for absent-element testing. 65 static final int ABSENT_VALUE = 778347983; 66 67 static final Integer[] integerArray; 68 static { 69 Integer[] ia = new Integer[20]; 70 // fill with 1..20 inclusive 71 for (int i = 0; i < ia.length; i++) { 72 ia[i] = i + 1; 73 } 74 integerArray = ia; 75 } 76 77 public static void realMain(String[] args) { 78 79 testCollection(new NewAbstractCollection<Integer>()); 80 testCollection(new NewAbstractSet<Integer>()); 81 testCollection(new LinkedHashSet<Integer>()); 82 testCollection(new HashSet<Integer>()); 83 testCollection(new Vector<Integer>()); 84 testCollection(new Vector<Integer>().subList(0,0)); 85 testCollection(new ArrayDeque<Integer>()); 86 testCollection(new ArrayList<Integer>()); 87 testCollection(new ArrayList<Integer>().subList(0,0)); 88 testCollection(new LinkedList<Integer>()); 89 testCollection(new LinkedList<Integer>().subList(0,0)); 90 testCollection(new TreeSet<Integer>()); 91 testCollection(Collections.checkedList(new ArrayList<Integer>(), Integer.class)); 92 testCollection(Collections.synchronizedList(new ArrayList<Integer>())); 93 testCollection(Collections.checkedSet(new HashSet<Integer>(), Integer.class)); 94 testCollection(Collections.checkedSortedSet(new TreeSet<Integer>(), Integer.class)); 95 testCollection(Collections.checkedNavigableSet(new TreeSet<Integer>(), Integer.class)); 96 testCollection(Collections.synchronizedSet(new HashSet<Integer>())); 97 testCollection(Collections.synchronizedSortedSet(new TreeSet<Integer>())); 98 testCollection(Collections.synchronizedNavigableSet(new TreeSet<Integer>())); 99 100 testCollection(new CopyOnWriteArrayList<Integer>()); 101 testCollection(new CopyOnWriteArrayList<Integer>().subList(0,0)); 102 testCollection(new CopyOnWriteArraySet<Integer>()); 103 testCollection(new PriorityQueue<Integer>()); 104 testCollection(new PriorityBlockingQueue<Integer>()); 105 testCollection(new ArrayBlockingQueue<Integer>(20)); 106 testCollection(new LinkedBlockingQueue<Integer>(20)); 107 testCollection(new LinkedBlockingDeque<Integer>(20)); 108 testCollection(new ConcurrentLinkedDeque<Integer>()); 109 testCollection(new ConcurrentLinkedQueue<Integer>()); 110 testCollection(new LinkedTransferQueue<Integer>()); 111 testCollection(new ConcurrentSkipListSet<Integer>()); 112 testCollection(Arrays.asList(new Integer(42))); 113 testCollection(Arrays.asList(1,2,3)); 114 testCollection(nCopies(25,1)); 115 testImmutableList(nCopies(25,1)); 116 117 testMap(new HashMap<Integer,Integer>()); 118 testMap(new LinkedHashMap<Integer,Integer>()); 119 120 // TODO: Add reliable support for WeakHashMap. 121 // This test is subject to very rare failures because the GC 122 // may remove unreferenced-keys from the map at any time. 123 // testMap(new WeakHashMap<Integer,Integer>()); 124 125 testMap(new IdentityHashMap<Integer,Integer>()); 126 testMap(new TreeMap<Integer,Integer>()); 127 testMap(new Hashtable<Integer,Integer>()); 128 testMap(new ConcurrentHashMap<Integer,Integer>(10, 0.5f)); 129 testMap(new ConcurrentSkipListMap<Integer,Integer>()); 130 testMap(Collections.checkedMap(new HashMap<Integer,Integer>(), Integer.class, Integer.class)); 131 testMap(Collections.checkedSortedMap(new TreeMap<Integer,Integer>(), Integer.class, Integer.class)); 132 testMap(Collections.checkedNavigableMap(new TreeMap<Integer,Integer>(), Integer.class, Integer.class)); 133 testMap(Collections.synchronizedMap(new HashMap<Integer,Integer>())); 134 testMap(Collections.synchronizedSortedMap(new TreeMap<Integer,Integer>())); 135 testMap(Collections.synchronizedNavigableMap(new TreeMap<Integer,Integer>())); 136 137 // Unmodifiable wrappers 138 testImmutableSet(unmodifiableSet(new HashSet<>(Arrays.asList(1,2,3)))); 139 testImmutableList(unmodifiableList(Arrays.asList(1,2,3))); 140 testImmutableMap(unmodifiableMap(Collections.singletonMap(1,2))); 141 testCollMutatorsAlwaysThrow(unmodifiableSet(new HashSet<>(Arrays.asList(1,2,3)))); 142 testCollMutatorsAlwaysThrow(unmodifiableSet(Collections.emptySet())); 143 testEmptyCollMutatorsAlwaysThrow(unmodifiableSet(Collections.emptySet())); 144 testListMutatorsAlwaysThrow(unmodifiableList(Arrays.asList(1,2,3))); 145 testListMutatorsAlwaysThrow(unmodifiableList(Collections.emptyList())); 146 testEmptyListMutatorsAlwaysThrow(unmodifiableList(Collections.emptyList())); 147 testMapMutatorsAlwaysThrow(unmodifiableMap(Collections.singletonMap(1,2))); 148 testMapMutatorsAlwaysThrow(unmodifiableMap(Collections.emptyMap())); 149 testEmptyMapMutatorsAlwaysThrow(unmodifiableMap(Collections.emptyMap())); 150 151 // Empty collections 152 final List<Integer> emptyArray = Arrays.asList(new Integer[]{}); 153 testCollection(emptyArray); 154 testEmptyList(emptyArray); 155 THROWS(IndexOutOfBoundsException.class, () -> emptyArray.set(0,1)); 156 THROWS(UnsupportedOperationException.class, () -> emptyArray.add(0,1)); 157 158 List<Integer> noOne = nCopies(0,1); 159 testCollection(noOne); 160 testEmptyList(noOne); 161 testImmutableList(noOne); 162 163 Set<Integer> emptySet = emptySet(); 164 testCollection(emptySet); 165 testEmptySet(emptySet); 166 testEmptySet(EMPTY_SET); 167 testEmptySet(Collections.emptySet()); 168 testEmptySet(Collections.emptySortedSet()); 169 testEmptySet(Collections.emptyNavigableSet()); 170 testImmutableSet(emptySet); 171 172 List<Integer> emptyList = emptyList(); 173 testCollection(emptyList); 174 testEmptyList(emptyList); 175 testEmptyList(EMPTY_LIST); 176 testEmptyList(Collections.emptyList()); 177 testImmutableList(emptyList); 178 179 Map<Integer,Integer> emptyMap = emptyMap(); 180 testMap(emptyMap); 181 testEmptyMap(emptyMap); 182 testEmptyMap(EMPTY_MAP); 183 testEmptyMap(Collections.emptyMap()); 184 testEmptyMap(Collections.emptySortedMap()); 185 testEmptyMap(Collections.emptyNavigableMap()); 186 testImmutableMap(emptyMap); 187 testImmutableMap(Collections.emptyMap()); 188 testImmutableMap(Collections.emptySortedMap()); 189 testImmutableMap(Collections.emptyNavigableMap()); 190 191 // Singleton collections 192 Set<Integer> singletonSet = singleton(1); 193 equal(singletonSet.size(), 1); 194 testCollection(singletonSet); 195 testImmutableSet(singletonSet); 196 197 List<Integer> singletonList = singletonList(1); 198 equal(singletonList.size(), 1); 199 testCollection(singletonList); 200 testImmutableList(singletonList); 201 testImmutableList(singletonList.subList(0,1)); 202 testImmutableList(singletonList.subList(0,1).subList(0,1)); 203 testEmptyList(singletonList.subList(0,0)); 204 testEmptyList(singletonList.subList(0,0).subList(0,0)); 205 206 Map<Integer,Integer> singletonMap = singletonMap(1,2); 207 equal(singletonMap.size(), 1); 208 testMap(singletonMap); 209 testImmutableMap(singletonMap); 210 211 // Immutable List 212 testEmptyList(List.of()); 213 testListMutatorsAlwaysThrow(List.of()); 214 testEmptyListMutatorsAlwaysThrow(List.of()); 215 for (List<Integer> list : Arrays.asList( 216 List.<Integer>of(), 217 List.of(1), 218 List.of(1, 2), 219 List.of(1, 2, 3), 220 List.of(1, 2, 3, 4), 221 List.of(1, 2, 3, 4, 5), 222 List.of(1, 2, 3, 4, 5, 6), 223 List.of(1, 2, 3, 4, 5, 6, 7), 224 List.of(1, 2, 3, 4, 5, 6, 7, 8), 225 List.of(1, 2, 3, 4, 5, 6, 7, 8, 9), 226 List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), 227 List.of(integerArray))) { 228 testCollection(list); 229 testImmutableList(list); 230 testListMutatorsAlwaysThrow(list); 231 } 232 233 // Immutable Set 234 testEmptySet(Set.of()); 235 testCollMutatorsAlwaysThrow(Set.of()); 236 testEmptyCollMutatorsAlwaysThrow(Set.of()); 237 for (Set<Integer> set : Arrays.asList( 238 Set.<Integer>of(), 239 Set.of(1), 240 Set.of(1, 2), 241 Set.of(1, 2, 3), 242 Set.of(1, 2, 3, 4), 243 Set.of(1, 2, 3, 4, 5), 244 Set.of(1, 2, 3, 4, 5, 6), 245 Set.of(1, 2, 3, 4, 5, 6, 7), 246 Set.of(1, 2, 3, 4, 5, 6, 7, 8), 247 Set.of(1, 2, 3, 4, 5, 6, 7, 8, 9), 248 Set.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), 249 Set.of(integerArray))) { 250 testCollection(set); 251 testImmutableSet(set); 252 testCollMutatorsAlwaysThrow(set); 253 } 254 255 // Immutable Map 256 257 @SuppressWarnings("unchecked") 258 Map.Entry<Integer,Integer>[] ea = (Map.Entry<Integer,Integer>[])new Map.Entry<?,?>[20]; 259 for (int i = 0; i < ea.length; i++) { 260 ea[i] = Map.entry(i+1, i+101); 261 } 262 263 testEmptyMap(Map.of()); 264 testMapMutatorsAlwaysThrow(Map.of()); 265 testEmptyMapMutatorsAlwaysThrow(Map.of()); 266 for (Map<Integer,Integer> map : Arrays.asList( 267 Map.<Integer,Integer>of(), 268 Map.of(1, 101), 269 Map.of(1, 101, 2, 202), 270 Map.of(1, 101, 2, 202, 3, 303), 271 Map.of(1, 101, 2, 202, 3, 303, 4, 404), 272 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505), 273 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606), 274 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707), 275 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808), 276 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808, 9, 909), 277 Map.of(1, 101, 2, 202, 3, 303, 4, 404, 5, 505, 6, 606, 7, 707, 8, 808, 9, 909, 10, 1010), 278 Map.ofEntries(ea))) { 279 testMap(map); 280 testImmutableMap(map); 281 testMapMutatorsAlwaysThrow(map); 282 } 283 } 284 285 private static void checkContainsSelf(Collection<Integer> c) { 286 check(c.containsAll(c)); 287 check(c.containsAll(Arrays.asList(c.toArray()))); 288 check(c.containsAll(Arrays.asList(c.toArray(new Integer[0])))); 289 } 290 291 private static void checkContainsEmpty(Collection<Integer> c) { 292 check(c.containsAll(new ArrayList<Integer>())); 293 } 294 295 private static void checkUnique(Set<Integer> s) { 296 for (Integer i : s) { 297 int count = 0; 298 for (Integer j : s) { 299 if (Objects.equals(i,j)) 300 ++count; 301 } 302 check(count == 1); 303 } 304 } 305 306 private static <T> void testEmptyCollection(Collection<T> c) { 307 check(c.isEmpty()); 308 equal(c.size(), 0); 309 equal(c.toString(),"[]"); 310 equal(c.toArray().length, 0); 311 equal(c.toArray(new Object[0]).length, 0); 312 check(c.toArray(new Object[]{42})[0] == null); 313 314 Object[] a = new Object[1]; a[0] = Boolean.TRUE; 315 equal(c.toArray(a), a); 316 equal(a[0], null); 317 testEmptyIterator(c.iterator()); 318 } 319 320 static <T> void testEmptyIterator(final Iterator<T> it) { 321 if (rnd.nextBoolean()) 322 check(! it.hasNext()); 323 324 THROWS(NoSuchElementException.class, () -> it.next()); 325 326 try { it.remove(); } 327 catch (IllegalStateException ignored) { pass(); } 328 catch (UnsupportedOperationException ignored) { pass(); } 329 catch (Throwable t) { unexpected(t); } 330 331 if (rnd.nextBoolean()) 332 check(! it.hasNext()); 333 } 334 335 private static void testEmptyList(List<?> c) { 336 testEmptyCollection(c); 337 equal(c.hashCode(), 1); 338 equal2(c, Collections.<Integer>emptyList()); 339 } 340 341 private static <T> void testEmptySet(Set<T> c) { 342 testEmptyCollection(c); 343 equal(c.hashCode(), 0); 344 equal2(c, Collections.<Integer>emptySet()); 345 if (c instanceof NavigableSet<?>) 346 testEmptyIterator(((NavigableSet<T>)c).descendingIterator()); 347 } 348 349 private static void testImmutableCollection(final Collection<Integer> c) { 350 THROWS(UnsupportedOperationException.class, 351 () -> c.add(99), 352 () -> c.addAll(singleton(99))); 353 if (! c.isEmpty()) { 354 final Integer first = c.iterator().next(); 355 THROWS(UnsupportedOperationException.class, 356 () -> c.clear(), 357 () -> c.remove(first), 358 () -> c.removeAll(singleton(first)), 359 () -> c.retainAll(emptyList())); 360 } 361 } 362 363 private static void testImmutableSet(final Set<Integer> c) { 364 testImmutableCollection(c); 365 } 366 367 private static void testImmutableList(final List<Integer> c) { 368 testList(c); 369 testImmutableCollection(c); 370 THROWS(UnsupportedOperationException.class, 371 () -> c.set(0,42), 372 () -> c.add(0,42), 373 () -> c.addAll(0,singleton(86))); 374 if (! c.isEmpty()) 375 THROWS(UnsupportedOperationException.class, 376 () -> { Iterator<Integer> it = c.iterator(); 377 it.next(); 378 it.remove(); }, 379 () -> { ListIterator<Integer> it = c.listIterator(); 380 it.next(); 381 it.remove(); }); 382 } 383 384 /** 385 * Test that calling a mutator always throws UOE, even if the mutator 386 * wouldn't actually do anything, given its arguments. 387 * 388 * @param c the collection instance to test 389 */ 390 private static void testCollMutatorsAlwaysThrow(Collection<Integer> c) { 391 THROWS(UnsupportedOperationException.class, 392 () -> c.addAll(Collections.emptyList()), 393 () -> c.remove(ABSENT_VALUE), 394 () -> c.removeAll(Collections.emptyList()), 395 () -> c.removeIf(x -> false), 396 () -> c.retainAll(c)); 397 } 398 399 /** 400 * Test that calling a mutator always throws UOE, even if the mutator 401 * wouldn't actually do anything on an empty collection. 402 * 403 * @param c the collection instance to test, must be empty 404 */ 405 private static void testEmptyCollMutatorsAlwaysThrow(Collection<Integer> c) { 406 if (! c.isEmpty()) { 407 fail("collection is not empty"); 408 } 409 THROWS(UnsupportedOperationException.class, 410 () -> c.clear()); 411 } 412 413 /** 414 * As above, for a list. 415 * 416 * @param c the list instance to test 417 */ 418 private static void testListMutatorsAlwaysThrow(List<Integer> c) { 419 testCollMutatorsAlwaysThrow(c); 420 THROWS(UnsupportedOperationException.class, 421 () -> c.addAll(0, Collections.emptyList())); 422 } 423 424 /** 425 * As above, for an empty list. 426 * 427 * @param c the list instance to test, must be empty 428 */ 429 private static void testEmptyListMutatorsAlwaysThrow(List<Integer> c) { 430 if (! c.isEmpty()) { 431 fail("list is not empty"); 432 } 433 testEmptyCollMutatorsAlwaysThrow(c); 434 THROWS(UnsupportedOperationException.class, 435 () -> c.replaceAll(x -> x), 436 () -> c.sort(null)); 437 } 438 439 /** 440 * As above, for a map. 441 * 442 * @param m the map instance to test 443 */ 444 private static void testMapMutatorsAlwaysThrow(Map<Integer,Integer> m) { 445 THROWS(UnsupportedOperationException.class, 446 () -> m.compute(ABSENT_VALUE, (k, v) -> null), 447 () -> m.computeIfAbsent(ABSENT_VALUE, k -> null), 448 () -> m.computeIfPresent(ABSENT_VALUE, (k, v) -> null), 449 () -> m.merge(ABSENT_VALUE, 0, (k, v) -> null), 450 () -> m.putAll(Collections.emptyMap()), 451 () -> m.remove(ABSENT_VALUE), 452 () -> m.remove(ABSENT_VALUE, 0), 453 () -> m.replace(ABSENT_VALUE, 0), 454 () -> m.replace(ABSENT_VALUE, 0, 1)); 455 } 456 457 /** 458 * As above, for an empty map. 459 * 460 * @param map the map instance to test, must be empty 461 */ 462 private static void testEmptyMapMutatorsAlwaysThrow(Map<Integer,Integer> m) { 463 if (! m.isEmpty()) { 464 fail("map is not empty"); 465 } 466 THROWS(UnsupportedOperationException.class, 467 () -> m.clear(), 468 () -> m.replaceAll((k, v) -> v)); 469 } 470 471 private static void clear(Collection<Integer> c) { 472 try { c.clear(); } 473 catch (Throwable t) { unexpected(t); } 474 testEmptyCollection(c); 475 } 476 477 private static <K,V> void testEmptyMap(final Map<K,V> m) { 478 check(m.isEmpty()); 479 equal(m.size(), 0); 480 equal(m.toString(),"{}"); 481 testEmptySet(m.keySet()); 482 testEmptySet(m.entrySet()); 483 testEmptyCollection(m.values()); 484 485 try { check(! m.containsValue(null)); } 486 catch (NullPointerException ignored) { /* OK */ } 487 try { check(! m.containsKey(null)); } 488 catch (NullPointerException ignored) { /* OK */ } 489 check(! m.containsValue(1)); 490 check(! m.containsKey(1)); 491 } 492 493 private static void testImmutableMap(final Map<Integer,Integer> m) { 494 THROWS(UnsupportedOperationException.class, 495 () -> m.put(1,1), 496 () -> m.putAll(singletonMap(1,1))); 497 if (! m.isEmpty()) { 498 final Integer first = m.keySet().iterator().next(); 499 THROWS(UnsupportedOperationException.class, 500 () -> m.remove(first), 501 () -> m.clear()); 502 final Map.Entry<Integer,Integer> me 503 = m.entrySet().iterator().next(); 504 Integer key = me.getKey(); 505 Integer val = me.getValue(); 506 THROWS(UnsupportedOperationException.class, 507 () -> me.setValue(3)); 508 equal(key, me.getKey()); 509 equal(val, me.getValue()); 510 } 511 testImmutableSet(m.keySet()); 512 testImmutableCollection(m.values()); 513 //testImmutableSet(m.entrySet()); 514 } 515 516 private static void clear(Map<?,?> m) { 517 try { m.clear(); } 518 catch (Throwable t) { unexpected(t); } 519 testEmptyMap(m); 520 } 521 522 private static void oneElement(Collection<Integer> c) { 523 clear(c); 524 try { 525 check(c.add(-42)); 526 equal(c.toString(), "[-42]"); 527 if (c instanceof Set) check(! c.add(-42)); 528 } catch (Throwable t) { unexpected(t); } 529 check(! c.isEmpty()); check(c.size() == 1); 530 } 531 532 private static boolean supportsAdd(Collection<Integer> c) { 533 try { check(c.add(ABSENT_VALUE)); } 534 catch (UnsupportedOperationException t) { return false; } 535 catch (Throwable t) { unexpected(t); } 536 537 try { 538 check(c.contains(ABSENT_VALUE)); 539 check(c.remove(ABSENT_VALUE)); 540 } catch (Throwable t) { unexpected(t); } 541 return true; 542 } 543 544 private static boolean supportsRemove(Collection<Integer> c) { 545 try { check(! c.remove(ABSENT_VALUE)); } 546 catch (UnsupportedOperationException t) { return false; } 547 catch (Throwable t) { unexpected(t); } 548 return true; 549 } 550 551 // 6260652: (coll) Arrays.asList(x).toArray().getClass() 552 // should be Object[].class 553 // Fixed in jdk9, but not jdk8 ... 554 static final boolean needToWorkAround6260652 = 555 Arrays.asList("").toArray().getClass() != Object[].class; 556 557 private static void checkFunctionalInvariants(Collection<Integer> c) { 558 try { 559 checkContainsSelf(c); 560 checkContainsEmpty(c); 561 check(c.size() != 0 ^ c.isEmpty()); 562 check(! c.contains(ABSENT_VALUE)); 563 564 { 565 int size = 0; 566 for (Integer i : c) size++; 567 check(c.size() == size); 568 } 569 570 if (c instanceof Set) { 571 checkUnique((Set<Integer>)c); 572 } 573 574 check(c.toArray().length == c.size()); 575 check(c.toArray().getClass() == Object[].class 576 || 577 (needToWorkAround6260652 && 578 c.getClass().getName().equals("java.util.Arrays$ArrayList"))); 579 for (int size : new int[]{0,1,c.size(), c.size()+1}) { 580 Integer[] a = c.toArray(new Integer[size]); 581 check((size > c.size()) || a.length == c.size()); 582 int i = 0; for (Integer j : c) check(a[i++] == j); 583 check((size <= c.size()) || (a[c.size()] == null)); 584 check(a.getClass() == Integer[].class); 585 } 586 587 check(c.equals(c)); 588 if (c instanceof Serializable) { 589 //System.out.printf("Serializing %s%n", c.getClass().getName()); 590 try { 591 Object clone = serialClone(c); 592 equal(c instanceof Serializable, 593 clone instanceof Serializable); 594 equal(c instanceof RandomAccess, 595 clone instanceof RandomAccess); 596 if ((c instanceof List) || (c instanceof Set)) 597 equal(c, clone); 598 else 599 equal(new HashSet<Integer>(c), 600 new HashSet<Integer>(serialClone(c))); 601 } catch (Error xxx) { 602 if (! (xxx.getCause() instanceof NotSerializableException)) 603 throw xxx; 604 } 605 } 606 } 607 catch (Throwable t) { unexpected(t); } 608 } 609 610 //---------------------------------------------------------------- 611 // If add(null) succeeds, contains(null) & remove(null) should succeed 612 //---------------------------------------------------------------- 613 private static void testNullElement(Collection<Integer> c) { 614 615 try { 616 check(c.add(null)); 617 if (c.size() == 1) 618 equal(c.toString(), "[null]"); 619 try { 620 checkFunctionalInvariants(c); 621 check(c.contains(null)); 622 check(c.remove(null)); 623 } 624 catch (Throwable t) { unexpected(t); } 625 } 626 catch (NullPointerException e) { /* OK */ } 627 catch (Throwable t) { unexpected(t); } 628 } 629 630 //---------------------------------------------------------------- 631 // If add("x") succeeds, contains("x") & remove("x") should succeed 632 //---------------------------------------------------------------- 633 @SuppressWarnings("unchecked") 634 private static void testStringElement(Collection<Integer> c) { 635 Collection x = (Collection)c; // Make type-unsafe 636 try { 637 check(x.add("x")); 638 try { 639 check(x.contains("x")); 640 check(x.remove("x")); 641 } catch (Throwable t) { unexpected(t); } 642 } 643 catch (ClassCastException e) { /* OK */ } 644 catch (Throwable t) { unexpected(t); } 645 } 646 647 private static void testConcurrentCollection(Collection<Integer> c) { 648 try { 649 c.add(1); 650 Iterator<Integer> it = c.iterator(); 651 check(it.hasNext()); 652 clear(c); 653 check(it.next() instanceof Integer); // No CME 654 check(c.isEmpty()); 655 } 656 catch (Throwable t) { unexpected(t); } 657 } 658 659 private static void testQueue(Queue<Integer> q) { 660 q.clear(); 661 for (int i = 0; i < 5; i++) { 662 testQueueAddRemove(q, null); 663 testQueueAddRemove(q, 537); 664 q.add(i); 665 } 666 equal(q.size(), 5); 667 checkFunctionalInvariants(q); 668 q.poll(); 669 equal(q.size(), 4); 670 checkFunctionalInvariants(q); 671 if ((q instanceof LinkedBlockingQueue) || 672 (q instanceof LinkedBlockingDeque) || 673 (q instanceof ConcurrentLinkedDeque) || 674 (q instanceof ConcurrentLinkedQueue)) { 675 testQueueIteratorRemove(q); 676 } 677 } 678 679 private static void testQueueAddRemove(final Queue<Integer> q, 680 final Integer e) { 681 final List<Integer> originalContents = new ArrayList<>(q); 682 final boolean isEmpty = q.isEmpty(); 683 final boolean isList = (q instanceof List); 684 final List asList = isList ? (List) q : null; 685 check(!q.contains(e)); 686 try { 687 q.add(e); 688 } catch (NullPointerException npe) { 689 check(e == null); 690 return; // Null elements not supported 691 } 692 check(q.contains(e)); 693 check(q.remove(e)); 694 check(!q.contains(e)); 695 equal(new ArrayList<Integer>(q), originalContents); 696 697 if (q instanceof Deque<?>) { 698 final Deque<Integer> deq = (Deque<Integer>) q; 699 final List<Integer> singleton = Collections.singletonList(e); 700 701 // insert, query, remove element at head 702 if (isEmpty) { 703 THROWS(NoSuchElementException.class, 704 () -> deq.getFirst(), 705 () -> deq.element(), 706 () -> deq.iterator().next()); 707 check(deq.peekFirst() == null); 708 check(deq.peek() == null); 709 } else { 710 check(deq.getFirst() != e); 711 check(deq.element() != e); 712 check(deq.iterator().next() != e); 713 check(deq.peekFirst() != e); 714 check(deq.peek() != e); 715 } 716 check(!deq.contains(e)); 717 check(!deq.removeFirstOccurrence(e)); 718 check(!deq.removeLastOccurrence(e)); 719 if (isList) { 720 check(asList.indexOf(e) == -1); 721 check(asList.lastIndexOf(e) == -1); 722 } 723 switch (rnd.nextInt(isList ? 4 : 3)) { 724 case 0: deq.addFirst(e); break; 725 case 1: check(deq.offerFirst(e)); break; 726 case 2: deq.push(e); break; 727 case 3: asList.add(0, e); break; 728 default: throw new AssertionError(); 729 } 730 check(deq.peekFirst() == e); 731 check(deq.getFirst() == e); 732 check(deq.element() == e); 733 check(deq.peek() == e); 734 check(deq.iterator().next() == e); 735 check(deq.contains(e)); 736 if (isList) { 737 check(asList.get(0) == e); 738 check(asList.indexOf(e) == 0); 739 check(asList.lastIndexOf(e) == 0); 740 check(asList.subList(0, 1).equals(singleton)); 741 } 742 switch (rnd.nextInt(isList ? 11 : 9)) { 743 case 0: check(deq.pollFirst() == e); break; 744 case 1: check(deq.removeFirst() == e); break; 745 case 2: check(deq.remove() == e); break; 746 case 3: check(deq.pop() == e); break; 747 case 4: check(deq.removeFirstOccurrence(e)); break; 748 case 5: check(deq.removeLastOccurrence(e)); break; 749 case 6: check(deq.remove(e)); break; 750 case 7: check(deq.removeAll(singleton)); break; 751 case 8: Iterator it = deq.iterator(); it.next(); it.remove(); break; 752 case 9: asList.remove(0); break; 753 case 10: asList.subList(0, 1).clear(); break; 754 default: throw new AssertionError(); 755 } 756 if (isEmpty) { 757 THROWS(NoSuchElementException.class, 758 () -> deq.getFirst(), 759 () -> deq.element(), 760 () -> deq.iterator().next()); 761 check(deq.peekFirst() == null); 762 check(deq.peek() == null); 763 } else { 764 check(deq.getFirst() != e); 765 check(deq.element() != e); 766 check(deq.iterator().next() != e); 767 check(deq.peekFirst() != e); 768 check(deq.peek() != e); 769 } 770 check(!deq.contains(e)); 771 check(!deq.removeFirstOccurrence(e)); 772 check(!deq.removeLastOccurrence(e)); 773 if (isList) { 774 check(isEmpty || asList.get(0) != e); 775 check(asList.indexOf(e) == -1); 776 check(asList.lastIndexOf(e) == -1); 777 } 778 equal(new ArrayList<Integer>(deq), originalContents); 779 780 // insert, query, remove element at tail 781 if (isEmpty) { 782 check(deq.peekLast() == null); 783 THROWS(NoSuchElementException.class, () -> deq.getLast()); 784 } else { 785 check(deq.peekLast() != e); 786 check(deq.getLast() != e); 787 } 788 switch (rnd.nextInt(isList ? 6 : 4)) { 789 case 0: deq.addLast(e); break; 790 case 1: check(deq.offerLast(e)); break; 791 case 2: check(deq.add(e)); break; 792 case 3: deq.addAll(singleton); break; 793 case 4: asList.addAll(deq.size(), singleton); break; 794 case 5: asList.add(deq.size(), e); break; 795 default: throw new AssertionError(); 796 } 797 check(deq.peekLast() == e); 798 check(deq.getLast() == e); 799 check(deq.contains(e)); 800 if (isList) { 801 ListIterator it = asList.listIterator(asList.size()); 802 check(it.previous() == e); 803 check(asList.get(asList.size() - 1) == e); 804 check(asList.indexOf(e) == asList.size() - 1); 805 check(asList.lastIndexOf(e) == asList.size() - 1); 806 int size = asList.size(); 807 check(asList.subList(size - 1, size).equals(singleton)); 808 } 809 switch (rnd.nextInt(isList ? 8 : 6)) { 810 case 0: check(deq.pollLast() == e); break; 811 case 1: check(deq.removeLast() == e); break; 812 case 2: check(deq.removeFirstOccurrence(e)); break; 813 case 3: check(deq.removeLastOccurrence(e)); break; 814 case 4: check(deq.remove(e)); break; 815 case 5: check(deq.removeAll(singleton)); break; 816 case 6: asList.remove(asList.size() - 1); break; 817 case 7: 818 ListIterator it = asList.listIterator(asList.size()); 819 it.previous(); 820 it.remove(); 821 break; 822 default: throw new AssertionError(); 823 } 824 if (isEmpty) { 825 check(deq.peekLast() == null); 826 THROWS(NoSuchElementException.class, () -> deq.getLast()); 827 } else { 828 check(deq.peekLast() != e); 829 check(deq.getLast() != e); 830 } 831 check(!deq.contains(e)); 832 equal(new ArrayList<Integer>(deq), originalContents); 833 834 // Test operations on empty deque 835 switch (rnd.nextInt(isList ? 4 : 2)) { 836 case 0: deq.clear(); break; 837 case 1: 838 Iterator it = deq.iterator(); 839 while (it.hasNext()) { 840 it.next(); 841 it.remove(); 842 } 843 break; 844 case 2: asList.subList(0, asList.size()).clear(); break; 845 case 3: 846 ListIterator lit = asList.listIterator(asList.size()); 847 while (lit.hasPrevious()) { 848 lit.previous(); 849 lit.remove(); 850 } 851 break; 852 default: throw new AssertionError(); 853 } 854 testEmptyCollection(deq); 855 check(!deq.iterator().hasNext()); 856 if (isList) { 857 check(!asList.listIterator().hasPrevious()); 858 THROWS(NoSuchElementException.class, 859 () -> asList.listIterator().previous()); 860 } 861 THROWS(NoSuchElementException.class, 862 () -> deq.iterator().next(), 863 () -> deq.element(), 864 () -> deq.getFirst(), 865 () -> deq.getLast(), 866 () -> deq.pop(), 867 () -> deq.remove(), 868 () -> deq.removeFirst(), 869 () -> deq.removeLast()); 870 871 check(deq.poll() == null); 872 check(deq.pollFirst() == null); 873 check(deq.pollLast() == null); 874 check(deq.peek() == null); 875 check(deq.peekFirst() == null); 876 check(deq.peekLast() == null); 877 check(!deq.removeFirstOccurrence(e)); 878 check(!deq.removeLastOccurrence(e)); 879 880 check(deq.addAll(originalContents) == !isEmpty); 881 equal(new ArrayList<Integer>(deq), originalContents); 882 check(!deq.addAll(Collections.<Integer>emptyList())); 883 equal(new ArrayList<Integer>(deq), originalContents); 884 } 885 } 886 887 private static void testQueueIteratorRemove(Queue<Integer> q) { 888 System.err.printf("testQueueIteratorRemove %s%n", 889 q.getClass().getSimpleName()); 890 q.clear(); 891 for (int i = 0; i < 5; i++) 892 q.add(i); 893 Iterator<Integer> it = q.iterator(); 894 check(it.hasNext()); 895 for (int i = 3; i >= 0; i--) 896 q.remove(i); 897 equal(it.next(), 0); 898 equal(it.next(), 4); 899 900 q.clear(); 901 for (int i = 0; i < 5; i++) 902 q.add(i); 903 it = q.iterator(); 904 equal(it.next(), 0); 905 check(it.hasNext()); 906 for (int i = 1; i < 4; i++) 907 q.remove(i); 908 equal(it.next(), 1); 909 equal(it.next(), 4); 910 } 911 912 private static void testList(final List<Integer> l) { 913 //---------------------------------------------------------------- 914 // 4802633: (coll) AbstractList.addAll(-1,emptyCollection) 915 // doesn't throw IndexOutOfBoundsException 916 //---------------------------------------------------------------- 917 try { 918 l.addAll(-1, Collections.<Integer>emptyList()); 919 fail("Expected IndexOutOfBoundsException not thrown"); 920 } 921 catch (UnsupportedOperationException ignored) {/* OK */} 922 catch (IndexOutOfBoundsException ignored) {/* OK */} 923 catch (Throwable t) { unexpected(t); } 924 925 // equal(l instanceof Serializable, 926 // l.subList(0,0) instanceof Serializable); 927 if (l.subList(0,0) instanceof Serializable) 928 check(l instanceof Serializable); 929 930 equal(l instanceof RandomAccess, 931 l.subList(0,0) instanceof RandomAccess); 932 933 l.iterator(); 934 l.listIterator(); 935 l.listIterator(0); 936 l.listIterator(l.size()); 937 THROWS(IndexOutOfBoundsException.class, 938 () -> l.listIterator(-1), 939 () -> l.listIterator(l.size() + 1)); 940 941 if (l instanceof AbstractList) { 942 try { 943 int size = l.size(); 944 AbstractList<Integer> abList = (AbstractList<Integer>) l; 945 Method m = AbstractList.class.getDeclaredMethod("removeRange", new Class[] { int.class, int.class }); 946 m.setAccessible(true); 947 m.invoke(abList, new Object[] { 0, 0 }); 948 m.invoke(abList, new Object[] { size, size }); 949 equal(size, l.size()); 950 } 951 catch (UnsupportedOperationException ignored) {/* OK */} 952 catch (Throwable t) { unexpected(t); } 953 } 954 } 955 956 private static void testCollection(Collection<Integer> c) { 957 try { testCollection1(c); } 958 catch (Throwable t) { unexpected(t); } 959 } 960 961 private static void testCollection1(Collection<Integer> c) { 962 963 System.out.println("\n==> " + c.getClass().getName()); 964 965 checkFunctionalInvariants(c); 966 967 if (! supportsAdd(c)) return; 968 //System.out.println("add() supported"); 969 970 if (c instanceof NavigableSet) { 971 System.out.println("NavigableSet tests..."); 972 973 NavigableSet<Integer> ns = (NavigableSet<Integer>)c; 974 testNavigableSet(ns); 975 testNavigableSet(ns.headSet(6, false)); 976 testNavigableSet(ns.headSet(5, true)); 977 testNavigableSet(ns.tailSet(0, false)); 978 testNavigableSet(ns.tailSet(1, true)); 979 testNavigableSet(ns.subSet(0, false, 5, true)); 980 testNavigableSet(ns.subSet(1, true, 6, false)); 981 } 982 983 if (c instanceof Queue) 984 testQueue((Queue<Integer>)c); 985 986 if (c instanceof List) 987 testList((List<Integer>)c); 988 989 check(supportsRemove(c)); 990 991 try { 992 oneElement(c); 993 checkFunctionalInvariants(c); 994 } 995 catch (Throwable t) { unexpected(t); } 996 997 clear(c); testNullElement(c); 998 oneElement(c); testNullElement(c); 999 1000 clear(c); testStringElement(c); 1001 oneElement(c); testStringElement(c); 1002 1003 if (c.getClass().getName().matches(".*concurrent.*")) 1004 testConcurrentCollection(c); 1005 1006 //---------------------------------------------------------------- 1007 // The "all" operations should throw NPE when passed null 1008 //---------------------------------------------------------------- 1009 { 1010 clear(c); 1011 try { 1012 c.removeAll(null); 1013 fail("Expected NullPointerException"); 1014 } 1015 catch (NullPointerException e) { pass(); } 1016 catch (Throwable t) { unexpected(t); } 1017 1018 oneElement(c); 1019 try { 1020 c.removeAll(null); 1021 fail("Expected NullPointerException"); 1022 } 1023 catch (NullPointerException e) { pass(); } 1024 catch (Throwable t) { unexpected(t); } 1025 1026 clear(c); 1027 try { 1028 c.retainAll(null); 1029 fail("Expected NullPointerException"); 1030 } 1031 catch (NullPointerException e) { pass(); } 1032 catch (Throwable t) { unexpected(t); } 1033 1034 oneElement(c); 1035 try { 1036 c.retainAll(null); 1037 fail("Expected NullPointerException"); 1038 } 1039 catch (NullPointerException e) { pass(); } 1040 catch (Throwable t) { unexpected(t); } 1041 1042 oneElement(c); 1043 try { 1044 c.addAll(null); 1045 fail("Expected NullPointerException"); 1046 } 1047 catch (NullPointerException e) { pass(); } 1048 catch (Throwable t) { unexpected(t); } 1049 1050 oneElement(c); 1051 try { 1052 c.containsAll(null); 1053 fail("Expected NullPointerException"); 1054 } 1055 catch (NullPointerException e) { pass(); } 1056 catch (Throwable t) { unexpected(t); } 1057 } 1058 } 1059 1060 //---------------------------------------------------------------- 1061 // Map 1062 //---------------------------------------------------------------- 1063 private static void checkFunctionalInvariants(Map<Integer,Integer> m) { 1064 check(m.keySet().size() == m.entrySet().size()); 1065 check(m.keySet().size() == m.size()); 1066 checkFunctionalInvariants(m.keySet()); 1067 checkFunctionalInvariants(m.values()); 1068 check(m.size() != 0 ^ m.isEmpty()); 1069 check(! m.containsKey(ABSENT_VALUE)); 1070 1071 if (m instanceof Serializable) { 1072 //System.out.printf("Serializing %s%n", m.getClass().getName()); 1073 try { 1074 Object clone = serialClone(m); 1075 equal(m instanceof Serializable, 1076 clone instanceof Serializable); 1077 equal(m, clone); 1078 } catch (Error xxx) { 1079 if (! (xxx.getCause() instanceof NotSerializableException)) 1080 throw xxx; 1081 } 1082 } 1083 } 1084 1085 private static void testMap(Map<Integer,Integer> m) { 1086 System.out.println("\n==> " + m.getClass().getName()); 1087 1088 if (m instanceof ConcurrentMap) 1089 testConcurrentMap((ConcurrentMap<Integer,Integer>) m); 1090 1091 if (m instanceof NavigableMap) { 1092 System.out.println("NavigableMap tests..."); 1093 1094 NavigableMap<Integer,Integer> nm = 1095 (NavigableMap<Integer,Integer>) m; 1096 testNavigableMapRemovers(nm); 1097 testNavigableMap(nm); 1098 testNavigableMap(nm.headMap(6, false)); 1099 testNavigableMap(nm.headMap(5, true)); 1100 testNavigableMap(nm.tailMap(0, false)); 1101 testNavigableMap(nm.tailMap(1, true)); 1102 testNavigableMap(nm.subMap(1, true, 6, false)); 1103 testNavigableMap(nm.subMap(0, false, 5, true)); 1104 } 1105 1106 checkFunctionalInvariants(m); 1107 1108 if (supportsClear(m)) { 1109 try { clear(m); } 1110 catch (Throwable t) { unexpected(t); } 1111 } 1112 1113 if (supportsPut(m)) { 1114 try { 1115 check(m.put(3333, 77777) == null); 1116 check(m.put(9134, 74982) == null); 1117 check(m.get(9134) == 74982); 1118 check(m.put(9134, 1382) == 74982); 1119 check(m.get(9134) == 1382); 1120 check(m.size() == 2); 1121 checkFunctionalInvariants(m); 1122 checkNPEConsistency(m); 1123 } 1124 catch (Throwable t) { unexpected(t); } 1125 } 1126 } 1127 1128 private static boolean supportsPut(Map<Integer,Integer> m) { 1129 // We're asking for .equals(...) semantics 1130 if (m instanceof IdentityHashMap) return false; 1131 1132 try { check(m.put(ABSENT_VALUE,12735) == null); } 1133 catch (UnsupportedOperationException t) { return false; } 1134 catch (Throwable t) { unexpected(t); } 1135 1136 try { 1137 check(m.containsKey(ABSENT_VALUE)); 1138 check(m.remove(ABSENT_VALUE) != null); 1139 } catch (Throwable t) { unexpected(t); } 1140 return true; 1141 } 1142 1143 private static boolean supportsClear(Map<?,?> m) { 1144 try { m.clear(); } 1145 catch (UnsupportedOperationException t) { return false; } 1146 catch (Throwable t) { unexpected(t); } 1147 return true; 1148 } 1149 1150 //---------------------------------------------------------------- 1151 // ConcurrentMap 1152 //---------------------------------------------------------------- 1153 private static void testConcurrentMap(ConcurrentMap<Integer,Integer> m) { 1154 System.out.println("ConcurrentMap tests..."); 1155 1156 try { 1157 clear(m); 1158 1159 check(m.putIfAbsent(18357,7346) == null); 1160 check(m.containsKey(18357)); 1161 check(m.putIfAbsent(18357,8263) == 7346); 1162 try { m.putIfAbsent(18357,null); fail("NPE"); } 1163 catch (NullPointerException t) { } 1164 check(m.containsKey(18357)); 1165 1166 check(! m.replace(18357,8888,7777)); 1167 check(m.containsKey(18357)); 1168 try { m.replace(18357,null,7777); fail("NPE"); } 1169 catch (NullPointerException t) { } 1170 check(m.containsKey(18357)); 1171 check(m.get(18357) == 7346); 1172 check(m.replace(18357,7346,5555)); 1173 check(m.replace(18357,5555,7346)); 1174 check(m.get(18357) == 7346); 1175 1176 check(m.replace(92347,7834) == null); 1177 try { m.replace(18357,null); fail("NPE"); } 1178 catch (NullPointerException t) { } 1179 check(m.replace(18357,7346) == 7346); 1180 check(m.replace(18357,5555) == 7346); 1181 check(m.get(18357) == 5555); 1182 check(m.replace(18357,7346) == 5555); 1183 check(m.get(18357) == 7346); 1184 1185 check(! m.remove(18357,9999)); 1186 check(m.get(18357) == 7346); 1187 check(m.containsKey(18357)); 1188 check(! m.remove(18357,null)); // 6272521 1189 check(m.get(18357) == 7346); 1190 check(m.remove(18357,7346)); 1191 check(m.get(18357) == null); 1192 check(! m.containsKey(18357)); 1193 check(m.isEmpty()); 1194 1195 m.putIfAbsent(1,2); 1196 check(m.size() == 1); 1197 check(! m.remove(1,null)); 1198 check(! m.remove(1,null)); 1199 check(! m.remove(1,1)); 1200 check(m.remove(1,2)); 1201 check(m.isEmpty()); 1202 1203 testEmptyMap(m); 1204 } 1205 catch (Throwable t) { unexpected(t); } 1206 } 1207 1208 private static void throwsConsistently(Class<? extends Throwable> k, 1209 Iterable<Fun> fs) { 1210 List<Class<? extends Throwable>> threw = new ArrayList<>(); 1211 for (Fun f : fs) 1212 try { f.f(); threw.add(null); } 1213 catch (Throwable t) { 1214 check(k.isAssignableFrom(t.getClass())); 1215 threw.add(t.getClass()); 1216 } 1217 if (new HashSet<Object>(threw).size() != 1) 1218 fail(threw.toString()); 1219 } 1220 1221 private static <T> void checkNPEConsistency(final Map<T,Integer> m) { 1222 m.clear(); 1223 final ConcurrentMap<T,Integer> cm = (m instanceof ConcurrentMap) 1224 ? (ConcurrentMap<T,Integer>) m 1225 : null; 1226 List<Fun> fs = new ArrayList<>(); 1227 fs.add(() -> check(! m.containsKey(null))); 1228 fs.add(() -> equal(m.remove(null), null)); 1229 fs.add(() -> equal(m.get(null), null)); 1230 if (cm != null) 1231 fs.add(() -> check(! cm.remove(null,null))); 1232 throwsConsistently(NullPointerException.class, fs); 1233 1234 fs.clear(); 1235 final Map<T,Integer> sm = singletonMap(null,1); 1236 fs.add(() -> { equal(m.put(null,1), null); m.clear();}); 1237 fs.add(() -> { m.putAll(sm); m.clear();}); 1238 if (cm != null) { 1239 fs.add(() -> check(! cm.remove(null,null))); 1240 fs.add(() -> equal(cm.putIfAbsent(null,1), 1)); 1241 fs.add(() -> equal(cm.replace(null,1), null)); 1242 fs.add(() -> equal(cm.replace(null,1, 1), 1)); 1243 } 1244 throwsConsistently(NullPointerException.class, fs); 1245 } 1246 1247 //---------------------------------------------------------------- 1248 // NavigableMap 1249 //---------------------------------------------------------------- 1250 private static void 1251 checkNavigableMapKeys(NavigableMap<Integer,Integer> m, 1252 Integer i, 1253 Integer lower, 1254 Integer floor, 1255 Integer ceiling, 1256 Integer higher) { 1257 equal(m.lowerKey(i), lower); 1258 equal(m.floorKey(i), floor); 1259 equal(m.ceilingKey(i), ceiling); 1260 equal(m.higherKey(i), higher); 1261 } 1262 1263 private static void 1264 checkNavigableSetKeys(NavigableSet<Integer> m, 1265 Integer i, 1266 Integer lower, 1267 Integer floor, 1268 Integer ceiling, 1269 Integer higher) { 1270 equal(m.lower(i), lower); 1271 equal(m.floor(i), floor); 1272 equal(m.ceiling(i), ceiling); 1273 equal(m.higher(i), higher); 1274 } 1275 1276 static final Random rnd = new Random(); 1277 static void equalNext(final Iterator<?> it, Object expected) { 1278 if (rnd.nextBoolean()) 1279 check(it.hasNext()); 1280 equal(it.next(), expected); 1281 } 1282 1283 static void equalMaps(Map m1, Map m2) { 1284 equal(m1, m2); 1285 equal(m2, m1); 1286 equal(m1.size(), m2.size()); 1287 equal(m1.isEmpty(), m2.isEmpty()); 1288 equal(m1.toString(), m2.toString()); 1289 check(Arrays.equals(m1.entrySet().toArray(), m2.entrySet().toArray())); 1290 } 1291 1292 @SuppressWarnings({"unchecked", "rawtypes"}) 1293 static void testNavigableMapRemovers(NavigableMap m) 1294 { 1295 final Map emptyMap = new HashMap(); 1296 1297 final Map singletonMap = new HashMap(); 1298 singletonMap.put(1, 2); 1299 1300 abstract class NavigableMapView { 1301 abstract NavigableMap view(NavigableMap m); 1302 } 1303 1304 NavigableMapView[] views = { 1305 new NavigableMapView() { NavigableMap view(NavigableMap m) { 1306 return m; }}, 1307 new NavigableMapView() { NavigableMap view(NavigableMap m) { 1308 return m.headMap(99, true); }}, 1309 new NavigableMapView() { NavigableMap view(NavigableMap m) { 1310 return m.tailMap(-99, false); }}, 1311 new NavigableMapView() { NavigableMap view(NavigableMap m) { 1312 return m.subMap(-99, true, 99, false); }}, 1313 }; 1314 1315 abstract class Remover { 1316 abstract void remove(NavigableMap m, Object k, Object v); 1317 } 1318 1319 Remover[] removers = { 1320 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1321 equal(m.remove(k), v); }}, 1322 1323 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1324 equal(m.descendingMap().remove(k), v); }}, 1325 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1326 equal(m.descendingMap().headMap(-86, false).remove(k), v); }}, 1327 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1328 equal(m.descendingMap().tailMap(86, true).remove(k), v); }}, 1329 1330 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1331 equal(m.headMap(86, true).remove(k), v); }}, 1332 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1333 equal(m.tailMap(-86, true).remove(k), v); }}, 1334 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1335 equal(m.subMap(-86, false, 86, true).remove(k), v); }}, 1336 1337 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1338 check(m.keySet().remove(k)); }}, 1339 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1340 check(m.navigableKeySet().remove(k)); }}, 1341 1342 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1343 check(m.navigableKeySet().headSet(86, true).remove(k)); }}, 1344 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1345 check(m.navigableKeySet().tailSet(-86, false).remove(k)); }}, 1346 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1347 check(m.navigableKeySet().subSet(-86, true, 86, false) 1348 .remove(k)); }}, 1349 1350 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1351 check(m.descendingKeySet().headSet(-86, false).remove(k)); }}, 1352 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1353 check(m.descendingKeySet().tailSet(86, true).remove(k)); }}, 1354 new Remover() { void remove(NavigableMap m, Object k, Object v) { 1355 check(m.descendingKeySet().subSet(86, true, -86, false) 1356 .remove(k)); }}, 1357 }; 1358 1359 for (NavigableMapView view : views) { 1360 for (Remover remover : removers) { 1361 try { 1362 m.clear(); 1363 equalMaps(m, emptyMap); 1364 equal(m.put(1, 2), null); 1365 equalMaps(m, singletonMap); 1366 NavigableMap v = view.view(m); 1367 remover.remove(v, 1, 2); 1368 equalMaps(m, emptyMap); 1369 } catch (Throwable t) { unexpected(t); } 1370 } 1371 } 1372 } 1373 1374 private static void testNavigableMap(NavigableMap<Integer,Integer> m) 1375 { 1376 clear(m); 1377 checkNavigableMapKeys(m, 1, null, null, null, null); 1378 1379 equal(m.put(1, 2), null); 1380 equal(m.put(3, 4), null); 1381 equal(m.put(5, 9), null); 1382 1383 equal(m.put(1, 2), 2); 1384 equal(m.put(3, 4), 4); 1385 equal(m.put(5, 6), 9); 1386 1387 checkNavigableMapKeys(m, 0, null, null, 1, 1); 1388 checkNavigableMapKeys(m, 1, null, 1, 1, 3); 1389 checkNavigableMapKeys(m, 2, 1, 1, 3, 3); 1390 checkNavigableMapKeys(m, 3, 1, 3, 3, 5); 1391 checkNavigableMapKeys(m, 5, 3, 5, 5, null); 1392 checkNavigableMapKeys(m, 6, 5, 5, null, null); 1393 1394 for (final Iterator<Integer> it : 1395 (Iterator<Integer>[]) 1396 new Iterator<?>[] { 1397 m.descendingKeySet().iterator(), 1398 m.navigableKeySet().descendingIterator()}) { 1399 equalNext(it, 5); 1400 equalNext(it, 3); 1401 equalNext(it, 1); 1402 check(! it.hasNext()); 1403 THROWS(NoSuchElementException.class, () -> it.next()); 1404 } 1405 1406 { 1407 final Iterator<Map.Entry<Integer,Integer>> it 1408 = m.descendingMap().entrySet().iterator(); 1409 check(it.hasNext()); equal(it.next().getKey(), 5); 1410 check(it.hasNext()); equal(it.next().getKey(), 3); 1411 check(it.hasNext()); equal(it.next().getKey(), 1); 1412 check(! it.hasNext()); 1413 THROWS(NoSuchElementException.class, () -> it.next()); 1414 } 1415 1416 prepMapForDescItrTests(m); 1417 checkDescItrRmFirst(m.keySet(), m.navigableKeySet().descendingIterator()); 1418 prepMapForDescItrTests(m); 1419 checkDescItrRmMid(m.keySet(), m.navigableKeySet().descendingIterator()); 1420 prepMapForDescItrTests(m); 1421 checkDescItrRmLast(m.keySet(), m.navigableKeySet().descendingIterator()); 1422 1423 prepMapForDescItrTests(m); 1424 checkDescItrRmFirst(m.keySet(), m.descendingMap().keySet().iterator()); 1425 prepMapForDescItrTests(m); 1426 checkDescItrRmMid(m.keySet(), m.descendingMap().keySet().iterator()); 1427 prepMapForDescItrTests(m); 1428 checkDescItrRmLast(m.keySet(), m.descendingMap().keySet().iterator()); 1429 1430 prepMapForDescItrTests(m); 1431 checkDescItrRmFirst(m.keySet(), m.descendingKeySet().iterator()); 1432 prepMapForDescItrTests(m); 1433 checkDescItrRmMid(m.keySet(), m.descendingKeySet().iterator()); 1434 prepMapForDescItrTests(m); 1435 checkDescItrRmLast(m.keySet(), m.descendingKeySet().iterator()); 1436 1437 prepMapForDescItrTests(m); 1438 checkDescItrRmFirst(m.values(), m.descendingMap().values().iterator()); 1439 prepMapForDescItrTests(m); 1440 checkDescItrRmMid(m.values(), m.descendingMap().values().iterator()); 1441 prepMapForDescItrTests(m); 1442 checkDescItrRmLast(m.values(), m.descendingMap().values().iterator()); 1443 1444 prepMapForDescItrTests(m); 1445 checkDescItrRmFirst((Collection)m.entrySet(), 1446 m.descendingMap().entrySet().iterator()); 1447 prepMapForDescItrTests(m); 1448 checkDescItrRmMid((Collection)m.entrySet(), 1449 m.descendingMap().entrySet().iterator()); 1450 prepMapForDescItrTests(m); 1451 checkDescItrRmLast((Collection)m.entrySet(), 1452 m.descendingMap().entrySet().iterator()); 1453 } 1454 1455 private static void testNavigableSet(NavigableSet<Integer> s) { 1456 clear(s); 1457 checkNavigableSetKeys(s, 1, null, null, null, null); 1458 1459 check(s.add(1)); 1460 check(s.add(3)); 1461 check(s.add(5)); 1462 1463 check(! s.add(1)); 1464 check(! s.add(3)); 1465 check(! s.add(5)); 1466 1467 checkNavigableSetKeys(s, 0, null, null, 1, 1); 1468 checkNavigableSetKeys(s, 1, null, 1, 1, 3); 1469 checkNavigableSetKeys(s, 2, 1, 1, 3, 3); 1470 checkNavigableSetKeys(s, 3, 1, 3, 3, 5); 1471 checkNavigableSetKeys(s, 5, 3, 5, 5, null); 1472 checkNavigableSetKeys(s, 6, 5, 5, null, null); 1473 1474 for (final Iterator<Integer> it : 1475 (Iterator<Integer>[]) 1476 new Iterator<?>[] { 1477 s.descendingIterator(), 1478 s.descendingSet().iterator()}) { 1479 equalNext(it, 5); 1480 equalNext(it, 3); 1481 equalNext(it, 1); 1482 check(! it.hasNext()); 1483 THROWS(NoSuchElementException.class, () -> it.next()); 1484 } 1485 1486 prepSetForDescItrTests(s); 1487 checkDescItrRmFirst(s, s.descendingIterator()); 1488 prepSetForDescItrTests(s); 1489 checkDescItrRmMid(s, s.descendingIterator()); 1490 prepSetForDescItrTests(s); 1491 checkDescItrRmLast(s, s.descendingIterator()); 1492 1493 prepSetForDescItrTests(s); 1494 checkDescItrRmFirst(s, s.descendingSet().iterator()); 1495 prepSetForDescItrTests(s); 1496 checkDescItrRmMid(s, s.descendingSet().iterator()); 1497 prepSetForDescItrTests(s); 1498 checkDescItrRmLast(s, s.descendingSet().iterator()); 1499 } 1500 1501 private static void prepSetForDescItrTests(Set s) { 1502 clear(s); 1503 check(s.add(1)); 1504 check(s.add(3)); 1505 check(s.add(5)); 1506 } 1507 1508 private static void prepMapForDescItrTests(Map m) { 1509 clear(m); 1510 equal(m.put(1, 2), null); 1511 equal(m.put(3, 4), null); 1512 equal(m.put(5, 9), null); 1513 } 1514 1515 //-------------------------------------------------------------------- 1516 // Check behavior of descending iterator when first element is removed 1517 //-------------------------------------------------------------------- 1518 private static <T> void checkDescItrRmFirst(Collection<T> ascColl, 1519 Iterator<T> descItr) { 1520 T[] expected = (T[]) ascColl.toArray(); 1521 int idx = expected.length -1; 1522 1523 equalNext(descItr, expected[idx--]); 1524 descItr.remove(); 1525 while (idx >= 0 && descItr.hasNext()) { 1526 equalNext(descItr, expected[idx--]); 1527 } 1528 equal(descItr.hasNext(), false); 1529 equal(idx, -1); 1530 } 1531 1532 //----------------------------------------------------------------------- 1533 // Check behavior of descending iterator when a middle element is removed 1534 //----------------------------------------------------------------------- 1535 private static <T> void checkDescItrRmMid(Collection<T> ascColl, 1536 Iterator<T> descItr) { 1537 T[] expected = (T[]) ascColl.toArray(); 1538 int idx = expected.length -1; 1539 1540 while (idx >= expected.length / 2) { 1541 equalNext(descItr, expected[idx--]); 1542 } 1543 descItr.remove(); 1544 while (idx >= 0 && descItr.hasNext()) { 1545 equalNext(descItr, expected[idx--]); 1546 } 1547 equal(descItr.hasNext(), false); 1548 equal(idx, -1); 1549 } 1550 1551 //----------------------------------------------------------------------- 1552 // Check behavior of descending iterator when the last element is removed 1553 //----------------------------------------------------------------------- 1554 private static <T> void checkDescItrRmLast(Collection<T> ascColl, 1555 Iterator<T> descItr) { 1556 T[] expected = (T[]) ascColl.toArray(); 1557 int idx = expected.length -1; 1558 1559 while (idx >= 0 && descItr.hasNext()) { 1560 equalNext(descItr, expected[idx--]); 1561 } 1562 equal(idx, -1); 1563 equal(descItr.hasNext(), false); 1564 descItr.remove(); 1565 equal(ascColl.contains(expected[0]), false); 1566 } 1567 1568 //--------------------- Infrastructure --------------------------- 1569 static volatile int passed = 0, failed = 0; 1570 static void pass() { passed++; } 1571 static void fail() { failed++; Thread.dumpStack(); } 1572 static void fail(String msg) { System.out.println(msg); fail(); } 1573 static void unexpected(Throwable t) { failed++; t.printStackTrace(); } 1574 static void check(boolean cond) { if (cond) pass(); else fail(); } 1575 static void equal(Object x, Object y) { 1576 if (x == null ? y == null : x.equals(y)) pass(); 1577 else {System.out.println(x + " not equal to " + y); fail();}} 1578 static void equal2(Object x, Object y) {equal(x, y); equal(y, x);} 1579 public static void main(String[] args) throws Throwable { 1580 try { realMain(args); } catch (Throwable t) { unexpected(t); } 1581 1582 System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed); 1583 if (failed > 0) throw new Exception("Some tests failed"); 1584 } 1585 interface Fun {void f() throws Throwable;} 1586 private static void THROWS(Class<? extends Throwable> k, Fun... fs) { 1587 for (Fun f : fs) 1588 try { f.f(); fail("Expected " + k.getName() + " not thrown"); } 1589 catch (Throwable t) { 1590 if (k.isAssignableFrom(t.getClass())) pass(); 1591 else unexpected(t);}} 1592 static byte[] serializedForm(Object obj) { 1593 try { 1594 ByteArrayOutputStream baos = new ByteArrayOutputStream(); 1595 new ObjectOutputStream(baos).writeObject(obj); 1596 return baos.toByteArray(); 1597 } catch (IOException e) { throw new Error(e); }} 1598 static Object readObject(byte[] bytes) 1599 throws IOException, ClassNotFoundException { 1600 InputStream is = new ByteArrayInputStream(bytes); 1601 return new ObjectInputStream(is).readObject();} 1602 @SuppressWarnings("unchecked") 1603 static <T> T serialClone(T obj) { 1604 try { return (T) readObject(serializedForm(obj)); } 1605 catch (Exception e) { throw new Error(e); }} 1606 private static class NewAbstractCollection<E> extends AbstractCollection<E> { 1607 ArrayList<E> list = new ArrayList<>(); 1608 public boolean remove(Object obj) { 1609 return list.remove(obj); 1610 } 1611 public boolean add(E e) { 1612 return list.add(e); 1613 } 1614 public Iterator<E> iterator() { 1615 return list.iterator(); 1616 } 1617 public int size() { 1618 return list.size(); 1619 } 1620 } 1621 private static class NewAbstractSet<E> extends AbstractSet<E> { 1622 HashSet<E> set = new HashSet<>(); 1623 public boolean remove(Object obj) { 1624 return set.remove(obj); 1625 } 1626 public boolean add(E e) { 1627 return set.add(e); 1628 } 1629 public Iterator<E> iterator() { 1630 return set.iterator(); 1631 } 1632 public int size() { 1633 return set.size(); 1634 } 1635 } 1636 1637 }