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