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