1 /* 2 * Copyright (C) 2011 Google Inc. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package libcore.java.util; 18 19 import java.io.Serializable; 20 import java.util.AbstractMap; 21 import java.util.ArrayList; 22 import java.util.Arrays; 23 import java.util.Collection; 24 import java.util.Collections; 25 import java.util.Comparator; 26 import java.util.ConcurrentModificationException; 27 import java.util.Enumeration; 28 import java.util.HashMap; 29 import java.util.HashSet; 30 import java.util.Iterator; 31 import java.util.LinkedHashMap; 32 import java.util.LinkedList; 33 import java.util.List; 34 import java.util.ListIterator; 35 import java.util.Map; 36 import java.util.NavigableMap; 37 import java.util.NavigableSet; 38 import java.util.NoSuchElementException; 39 import java.util.Objects; 40 import java.util.Queue; 41 import java.util.Set; 42 import java.util.SortedMap; 43 import java.util.SortedSet; 44 import java.util.Spliterator; 45 import java.util.TreeMap; 46 import java.util.TreeSet; 47 import java.util.concurrent.LinkedBlockingDeque; 48 49 import junit.framework.AssertionFailedError; 50 import junit.framework.TestCase; 51 52 import dalvik.system.VMRuntime; 53 54 import static java.util.Collections.checkedNavigableMap; 55 import static java.util.Collections.checkedQueue; 56 import static java.util.Collections.synchronizedNavigableMap; 57 import static java.util.Collections.unmodifiableNavigableMap; 58 import static java.util.Spliterator.DISTINCT; 59 import static java.util.Spliterator.ORDERED; 60 import static java.util.Spliterator.SIZED; 61 import static java.util.Spliterator.SUBSIZED; 62 import static libcore.java.util.SpliteratorTester.assertHasCharacteristics; 63 64 public final class CollectionsTest extends TestCase { 65 66 private static final Object NOT_A_STRING = new Object(); 67 private static final Object A_STRING = "string"; 68 69 public void testEmptyEnumeration() { 70 Enumeration<Object> e = Collections.emptyEnumeration(); 71 assertFalse(e instanceof Serializable); 72 assertFalse(e.hasMoreElements()); 73 try { 74 e.nextElement(); 75 fail(); 76 } catch (NoSuchElementException expected) { 77 } 78 } 79 80 public void testEmptyIterator() { 81 testEmptyIterator(Collections.emptyIterator()); 82 testEmptyIterator(Collections.emptyList().iterator()); 83 testEmptyIterator(Collections.emptySet().iterator()); 84 testEmptyIterator(Collections.emptyMap().keySet().iterator()); 85 testEmptyIterator(Collections.emptyMap().entrySet().iterator()); 86 testEmptyIterator(Collections.emptyMap().values().iterator()); 87 } 88 89 private void testEmptyIterator(Iterator<?> i) { 90 assertFalse(i instanceof Serializable); 91 assertFalse(i.hasNext()); 92 try { 93 i.next(); 94 fail(); 95 } catch (NoSuchElementException expected) { 96 } 97 try { 98 i.remove(); 99 fail(); 100 } catch (IllegalStateException expected) { 101 } 102 } 103 104 public void testEmptyListIterator() { 105 testEmptyListIterator(Collections.emptyListIterator()); 106 testEmptyListIterator(Collections.emptyList().listIterator()); 107 testEmptyListIterator(Collections.emptyList().listIterator(0)); 108 } 109 110 private void testEmptyListIterator(ListIterator<?> i) { 111 assertFalse(i instanceof Serializable); 112 assertFalse(i.hasNext()); 113 assertFalse(i.hasPrevious()); 114 assertEquals(0, i.nextIndex()); 115 try { 116 i.next(); 117 fail(); 118 } catch (NoSuchElementException expected) { 119 } 120 assertEquals(-1, i.previousIndex()); 121 try { 122 i.previous(); 123 fail(); 124 } catch (NoSuchElementException expected) { 125 } 126 try { 127 i.add(null); 128 fail(); 129 } catch (UnsupportedOperationException expected) { 130 } 131 try { 132 i.remove(); 133 fail(); 134 } catch (IllegalStateException expected) { 135 } 136 } 137 138 static final class ArrayListInheritor<T> extends ArrayList<T> { 139 private int numSortCalls = 0; 140 public ArrayListInheritor(Collection<T> initialElements) { 141 super(initialElements); 142 } 143 144 @Override 145 public void sort(Comparator<? super T> c) { 146 super.sort(c); 147 numSortCalls++; 148 } 149 150 public int numSortCalls() { 151 return numSortCalls; 152 } 153 } 154 155 /** 156 * Tests that when targetSdk {@code <= 25}, Collections.sort() does not delegate 157 * to List.sort(). 158 */ 159 public void testSort_nougatOrEarlier_doesNotDelegateToListSort() { 160 runOnTargetSdk(25, () -> { // Nougat MR1 / MR2 161 ArrayListInheritor<String> list = new ArrayListInheritor<>( 162 Arrays.asList("a", "c", "b")); 163 assertEquals(0, list.numSortCalls()); 164 Collections.sort(list); 165 assertEquals(0, list.numSortCalls()); 166 }); 167 } 168 169 public void testSort_postNougat_delegatesToListSort() { 170 runOnTargetSdkAtLeast(26, () -> { 171 ArrayListInheritor<String> list = new ArrayListInheritor<>( 172 Arrays.asList("a", "c", "b")); 173 assertEquals(0, list.numSortCalls()); 174 Collections.sort(list); 175 assertEquals(1, list.numSortCalls()); 176 }); 177 } 178 179 public void testSort_modcountUnmodifiedForLinkedList() { 180 runOnTargetSdkAtLeast(26, () -> { 181 LinkedList<String> list = new LinkedList<>(Arrays.asList( 182 "red", "green", "blue", "violet")); 183 Iterator<String> it = list.iterator(); 184 it.next(); 185 Collections.sort(list); 186 it.next(); // does not throw ConcurrentModificationException 187 }); 188 } 189 190 public void testSort_modcountModifiedForArrayListAndSubclasses() { 191 runOnTargetSdkAtLeast(26, () -> { 192 List<String> testData = Arrays.asList("red", "green", "blue", "violet"); 193 194 ArrayList<String> list = new ArrayList<>(testData); 195 Iterator<String> it = list.iterator(); 196 it.next(); 197 Collections.sort(list); 198 try { 199 it.next(); 200 fail(); 201 } catch (ConcurrentModificationException expected) { 202 } 203 204 list = new ArrayListInheritor<>(testData); 205 it = list.iterator(); 206 it.next(); 207 Collections.sort(list); 208 try { 209 it.next(); 210 fail(); 211 } catch (ConcurrentModificationException expected) { 212 } 213 }); 214 } 215 216 /** 217 * Runs the given runnable on this thread with the targetSdkVersion temporarily set 218 * to the specified value, unless the current value is already higher. 219 */ 220 private static void runOnTargetSdkAtLeast(int minimumTargetSdkForTest, Runnable runnable) { 221 int targetSdkForTest = Math.max(minimumTargetSdkForTest, 222 VMRuntime.getRuntime().getTargetSdkVersion()); 223 runOnTargetSdk(targetSdkForTest, runnable); 224 } 225 226 /** 227 * Runs the given runnable on this thread with the targetSdkVersion temporarily set 228 * to the specified value. This helps test behavior that depends on an API level 229 * other than the current one (e.g. between releases). 230 */ 231 private static void runOnTargetSdk(int targetSdkForTest, Runnable runnable) { 232 VMRuntime runtime = VMRuntime.getRuntime(); 233 int targetSdk = runtime.getTargetSdkVersion(); 234 try { 235 runtime.setTargetSdkVersion(targetSdkForTest); 236 runnable.run(); 237 } finally { 238 runtime.setTargetSdkVersion(targetSdk); 239 } 240 } 241 242 /** 243 * A value type whose {@code compareTo} method returns one of {@code 0}, 244 * {@code Integer.MIN_VALUE} and {@code Integer.MAX_VALUE}. 245 */ 246 static final class IntegerWithExtremeComparator 247 implements Comparable<IntegerWithExtremeComparator> { 248 private final int value; 249 250 public IntegerWithExtremeComparator(int value) { 251 this.value = value; 252 } 253 254 @Override 255 public int compareTo(IntegerWithExtremeComparator another) { 256 if (another.value == this.value) { 257 return 0; 258 } else if (another.value > this.value) { 259 return Integer.MIN_VALUE; 260 } else { 261 return Integer.MAX_VALUE; 262 } 263 } 264 } 265 266 // http://b/19749094 267 public void testBinarySearch_comparatorThatReturnsMinAndMaxValue() { 268 ArrayList<Integer> list = new ArrayList<Integer>(16); 269 list.add(4); 270 list.add(9); 271 list.add(11); 272 list.add(14); 273 list.add(16); 274 275 int index = Collections.binarySearch(list, 9, new Comparator<Integer>() { 276 @Override 277 public int compare(Integer lhs, Integer rhs) { 278 final int compare = lhs.compareTo(rhs); 279 if (compare == 0) { 280 return 0; 281 } else if (compare < 0) { 282 return Integer.MIN_VALUE; 283 } else { 284 return Integer.MAX_VALUE; 285 } 286 } 287 }); 288 assertEquals(1, index); 289 290 ArrayList<IntegerWithExtremeComparator> list2 = 291 new ArrayList<IntegerWithExtremeComparator>(); 292 list2.add(new IntegerWithExtremeComparator(4)); 293 list2.add(new IntegerWithExtremeComparator(9)); 294 list2.add(new IntegerWithExtremeComparator(11)); 295 list2.add(new IntegerWithExtremeComparator(14)); 296 list2.add(new IntegerWithExtremeComparator(16)); 297 298 assertEquals(1, Collections.binarySearch(list2, new IntegerWithExtremeComparator(9))); 299 } 300 301 public void testBinarySearch_emptyCollection() { 302 assertEquals(-1, Collections.binarySearch(new ArrayList<Integer>(), 9)); 303 304 assertEquals(-1, Collections.binarySearch(new ArrayList<>(), 9, Integer::compareTo)); 305 } 306 307 public void testSingletonSpliterator() { 308 Spliterator<String> sp = Collections.singletonList("spiff").spliterator(); 309 310 assertEquals(1, sp.estimateSize()); 311 assertEquals(1, sp.getExactSizeIfKnown()); 312 assertNull(sp.trySplit()); 313 assertEquals(true, sp.tryAdvance(value -> assertEquals("spiff", value))); 314 assertEquals(false, sp.tryAdvance(value -> fail())); 315 } 316 317 public void test_checkedNavigableMap_replaceAll() { 318 NavigableMap<String, Integer> map = checkedNavigableMap( 319 new TreeMap<>(createMap("key3", 3, "key1", 1, "key4", 4, "key2", 2)), 320 String.class, Integer.class); 321 map.replaceAll((k, v) -> 5 * v); 322 assertEquals( 323 createMap("key3", 15, "key1", 5, "key4", 20, "key2", 10), 324 map); 325 } 326 327 public void test_checkedNavigableMap_putIfAbsent() { 328 NavigableMap<Integer, Double> map = 329 checkedNavigableMap(new TreeMap<>(), Integer.class, Double.class); 330 MapDefaultMethodTester.test_putIfAbsent(map, 331 false /* acceptsNullKey */, true /* acceptsNullValue */); 332 } 333 334 public void test_checkedNavigableMap_remove() { 335 NavigableMap<Integer, Double> map = 336 checkedNavigableMap(new TreeMap<>(), Integer.class, Double.class); 337 MapDefaultMethodTester.test_remove(map, 338 false /* acceptsNullKey */, true /* acceptsNullValue */); 339 } 340 341 public void test_checkedNavigableMap_replace$K$V() { 342 NavigableMap<Integer, Double> map = 343 checkedNavigableMap(new TreeMap<>(), Integer.class, Double.class); 344 MapDefaultMethodTester.test_replace$K$V$V(map, 345 false /* acceptsNullKey */, true /* acceptsNullValue */); 346 } 347 348 public void test_checkedNavigableMap_replace$K$V$V() { 349 NavigableMap<Integer, Double> map = 350 checkedNavigableMap(new TreeMap<>(), Integer.class, Double.class); 351 MapDefaultMethodTester.test_replace$K$V$V(map, 352 false /* acceptsNullKey */, true /* acceptsNullValue */); 353 } 354 355 public void test_checkedNavigableMap_computeIfAbsent() { 356 NavigableMap<Integer, Double> map = 357 checkedNavigableMap(new TreeMap<>(), Integer.class, Double.class); 358 MapDefaultMethodTester.test_computeIfAbsent(map, 359 false /* acceptsNullKey */, true /* acceptsNullValue */); 360 } 361 362 public void test_checkedNavigableMap_computeIfPresent() { 363 NavigableMap<Integer, Double> map = 364 checkedNavigableMap(new TreeMap<>(), Integer.class, Double.class); 365 MapDefaultMethodTester.test_computeIfPresent(map, false /* acceptsNullKey */); 366 } 367 368 public void test_checkedNavigableMap_compute() { 369 NavigableMap<Integer, Double> map = 370 checkedNavigableMap(new TreeMap<>(), Integer.class, Double.class); 371 MapDefaultMethodTester.test_compute(map, false /* acceptsNullKey */); 372 } 373 374 public void test_checkedNavigableMap_merge() { 375 NavigableMap<Integer, Double> map = 376 checkedNavigableMap(new TreeMap<>(), Integer.class, Double.class); 377 MapDefaultMethodTester.test_merge(map, false /* acceptsNullKey */); 378 } 379 380 public void test_checkedNavigableMap_navigableKeySet() { 381 NavigableMap<String, Integer> map = checkedNavigableMap( 382 new TreeMap<>(createMap("key3", 3, "key1", 1, "key4", 4, "key2", 2)), 383 String.class, Integer.class); 384 check_navigableSet( 385 map.navigableKeySet(), 386 Arrays.asList("key1", "key2", "key3", "key4") /* expectedElementsInOrder */, 387 "absent" /* absentElement */); 388 } 389 390 public void test_checkedNavigableMap_values() { 391 NavigableMap<String, Integer> map = checkedNavigableMap( 392 new TreeMap<>(createMap("key3", 3, "key1", 1, "key4", 4, "key2", 2)), 393 String.class, Integer.class); 394 check_orderedCollection(map.values(), Arrays.asList(1, 2, 3, 4) /* expectedElementsInOrder */); 395 } 396 397 public void test_checkedNavigableMap_isChecked() { 398 NavigableMap<String, Integer> delegate = new TreeMap<>(); 399 delegate.put("present", 1); 400 delegate.put("another key", 2); 401 check_navigableMap_isChecked( 402 checkedNavigableMap(delegate, String.class, Integer.class), 403 "present", 1, "aaa absent", "zzz absent", 42); 404 } 405 406 public void test_checkedNavigableSet() { 407 NavigableSet set = Collections.checkedNavigableSet(new TreeSet<>(), String.class); 408 check_navigableSet(set, Arrays.asList(), "absent element"); 409 410 set.add("element 1"); 411 set.add("element 2"); 412 List<String> elementsInOrder = Arrays.asList("element 1", "element 2"); 413 check_navigableSet(set, elementsInOrder, "absent element"); 414 415 assertEquals(set, new HashSet<>(elementsInOrder)); 416 assertEquals(new HashSet<>(elementsInOrder), set); 417 assertEquals(2, set.size()); 418 assertTrue(set.contains("element 1")); 419 assertTrue(set.contains("element 2")); 420 assertFalse(set.contains("absent element")); 421 } 422 423 public void test_checkedNavigableSet_isChecked() { 424 NavigableSet set = Collections.checkedNavigableSet(new TreeSet<>(), String.class); 425 assertThrowsCce(() -> { set.add(new Object()); }); 426 assertThrowsCce(() -> { set.addAll(Arrays.asList(new Object())); }); 427 } 428 429 public void test_checkedQueue() { 430 Queue queue = checkedQueue(new LinkedBlockingDeque<>(2), CharSequence.class); 431 assertQueueEmpty(queue); 432 // Demonstrate that any implementation of CharSequence works by using two 433 // different ones (StringBuilder and String) as values. 434 StringBuilder firstElement = new StringBuilder("first element"); 435 assertTrue(queue.add(firstElement)); 436 assertFalse(queue.isEmpty()); 437 assertTrue(queue.add("second element")); 438 assertEquals(2, queue.size()); 439 440 assertFalse(queue.offer("third element")); // queue is at capacity 441 try { 442 queue.add("third element"); 443 fail(); 444 } catch (IllegalStateException expected) { 445 } 446 assertThrowsCce(() -> { queue.add(new Object()); }); // fails the type check 447 assertEquals(2, queue.size()); // size is unchanged 448 449 // element() and peek() don't remove the first element 450 assertSame(firstElement, queue.element()); 451 assertSame(firstElement, queue.peek()); 452 453 assertSame(firstElement, queue.poll()); 454 assertSame("second element", queue.poll()); 455 assertQueueEmpty(queue); 456 457 assertThrowsCce(() -> { queue.add(new Object()); }); // fails the type check 458 } 459 460 /** 461 * Asserts properties that should hold for any empty queue. 462 */ 463 private static void assertQueueEmpty(Queue queue) { 464 assertTrue(queue.isEmpty()); 465 assertEquals(0, queue.size()); 466 assertNull(queue.peek()); 467 try { 468 queue.element(); 469 fail(); 470 } catch (NoSuchElementException expected) { 471 } 472 assertNull(queue.poll()); 473 } 474 475 public void test_unmodifiableMap_getOrDefault() { 476 Map<Integer, Double> delegate = new HashMap<>(); 477 delegate.put(2, 12.0); 478 delegate.put(3, null); 479 Map<Integer, Double> m = Collections.unmodifiableMap(delegate); 480 assertEquals(-1.0, m.getOrDefault(1, -1.0)); 481 assertEquals(12.0, m.getOrDefault(2, -1.0)); 482 assertEquals(null, m.getOrDefault(3, -1.0)); 483 } 484 485 public void test_unmodifiableMap_forEach() { 486 Map<Integer, Double> delegate = new HashMap<>(); 487 Map<Integer, Double> replica = new HashMap<>(); 488 delegate.put(1, 10.0); 489 delegate.put(2, 20.0); 490 Collections.unmodifiableMap(delegate).forEach(replica::put); 491 assertEquals(10.0, replica.get(1)); 492 assertEquals(20.0, replica.get(2)); 493 assertEquals(2, replica.size()); 494 } 495 496 public void test_unmodifiableMap_putIfAbsent() { 497 try { 498 Collections.unmodifiableMap(new HashMap<>()).putIfAbsent(1, 5.0); 499 fail(); 500 } catch (UnsupportedOperationException expected) { 501 } 502 503 // For existing key 504 Map<Integer, Double> m = new HashMap<>(); 505 m.put(1, 5.0); 506 try { 507 Collections.unmodifiableMap(m).putIfAbsent(1, 5.0); 508 fail(); 509 } catch (UnsupportedOperationException expected) { 510 } 511 } 512 513 public void test_unmodifiableMap_remove() { 514 try { 515 Collections.unmodifiableMap(new HashMap<>()).remove(1, 5.0); 516 fail(); 517 } catch (UnsupportedOperationException expected) { 518 } 519 520 // For existing key 521 Map<Integer, Double> m = new HashMap<>(); 522 m.put(1, 5.0); 523 try { 524 Collections.unmodifiableMap(m).remove(1, 5.0); 525 fail(); 526 } catch (UnsupportedOperationException expected) { 527 } 528 } 529 530 public void test_unmodifiableMap_replace$K$V$V() { 531 try { 532 Collections.unmodifiableMap(new HashMap<>()).replace(1, 5.0, 1.0); 533 fail(); 534 } catch (UnsupportedOperationException expected) { 535 } 536 537 // For existing key 538 Map<Integer, Double> m = new HashMap<>(); 539 m.put(1, 5.0); 540 try { 541 Collections.unmodifiableMap(m).replace(1, 5.0, 1.0); 542 fail(); 543 } catch (UnsupportedOperationException expected) { 544 } 545 } 546 547 public void test_unmodifiableMap_replace$K$V() { 548 try { 549 Collections.unmodifiableMap(new HashMap<>()).replace(1, 5.0); 550 fail(); 551 } catch (UnsupportedOperationException expected) { 552 } 553 554 // For existing key 555 Map<Integer, Double> m = new HashMap<>(); 556 m.put(1, 5.0); 557 try { 558 Collections.unmodifiableMap(m).replace(1, 5.0); 559 fail(); 560 } catch (UnsupportedOperationException expected) { 561 } 562 } 563 564 public void test_unmodifiableMap_computeIfAbsent() { 565 try { 566 Collections.unmodifiableMap(new HashMap<>()).computeIfAbsent(1, k -> 1.0); 567 fail(); 568 } catch (UnsupportedOperationException expected) { 569 } 570 571 // For existing key 572 Map<Integer, Double> m = new HashMap<>(); 573 m.put(1, 5.0); 574 try { 575 Collections.unmodifiableMap(m).computeIfAbsent(1, k -> 1.0); 576 fail(); 577 } catch (UnsupportedOperationException expected) { 578 } 579 } 580 581 public void test_unmodifiableMap_computeIfPresent() { 582 try { 583 Collections.unmodifiableMap(new HashMap<>()).computeIfPresent(1, (k, v) -> 1.0); 584 fail(); 585 } catch (UnsupportedOperationException expected) { 586 } 587 588 // For existing key 589 Map<Integer, Double> m = new HashMap<>(); 590 m.put(1, 5.0); 591 try { 592 Collections.unmodifiableMap(m).computeIfPresent(1, (k, v) -> 1.0); 593 fail(); 594 } catch (UnsupportedOperationException expected) { 595 } 596 } 597 598 public void test_unmodifiableMap_compute() { 599 try { 600 Collections.unmodifiableMap(new HashMap<>()).compute(1, (k, v) -> 1.0); 601 fail(); 602 } catch (UnsupportedOperationException expected) { 603 } 604 605 // For existing key 606 Map<Integer, Double> m = new HashMap<>(); 607 m.put(1, 5.0); 608 try { 609 Collections.unmodifiableMap(m).compute(1, (k, v) -> 1.0); 610 fail(); 611 } catch (UnsupportedOperationException expected) { 612 } 613 } 614 615 public void test_unmodifiableMap_merge() { 616 try { 617 Collections.unmodifiableMap(new HashMap<>()).merge(1, 2.0, (k, v) -> 1.0); 618 fail(); 619 } catch (UnsupportedOperationException expected) { 620 } 621 622 // For existing key 623 Map<Integer, Double> m = new HashMap<>(); 624 m.put(1, 5.0); 625 try { 626 Collections.unmodifiableMap(m).merge(1, 2.0, (k, v) -> 1.0); 627 fail(); 628 } catch (UnsupportedOperationException expected) { 629 } 630 } 631 632 public void test_unmodifiableNavigableMap_empty() { 633 NavigableMap<String, Integer> map = unmodifiableNavigableMap(new TreeMap<>()); 634 635 check_unmodifiableNavigableMap_defaultMethods(map, 636 Arrays.<String>asList(), 637 Arrays.<Integer>asList(), 638 "absent key", -1 /* absentValue */); 639 640 check_unmodifiableNavigableMap_collectionViews(map, 641 Arrays.<String>asList(), 642 Arrays.<Integer>asList(), 643 "absent key"); 644 } 645 646 public void test_unmodifiableNavigableMap_nonEmpty() { 647 NavigableMap<String, Integer> map = unmodifiableNavigableMap( 648 new TreeMap<>(createMap("key3", 3, "key1", 1, "key4", 4, "key2", 2))); 649 650 check_unmodifiableNavigableMap_defaultMethods(map, 651 Arrays.asList("key1", "key2", "key3", "key4"), 652 Arrays.asList(1, 2, 3, 4), 653 "absent key", -1 /* absentValue */); 654 655 check_unmodifiableNavigableMap_collectionViews(map, 656 Arrays.asList("key1", "key2", "key3", "key4"), 657 Arrays.asList(1, 2, 3, 4), 658 "absent key"); 659 } 660 661 public void test_unmodifiableNavigableSet_empty() { 662 NavigableSet<String> set = Collections.unmodifiableNavigableSet(new TreeSet<>()); 663 check_unmodifiableSet(set, "absent element"); 664 check_navigableSet(set, new ArrayList<>(), "absent element"); 665 } 666 667 public void test_unmodifiableNavigableSet_nonEmpty() { 668 NavigableSet<String> delegate = new TreeSet<>(); 669 NavigableSet<String> set = Collections.unmodifiableNavigableSet(delegate); 670 delegate.add("pear"); 671 delegate.add("banana"); 672 delegate.add("apple"); 673 delegate.add("melon"); 674 675 check_unmodifiableNavigableSet(set, 676 Arrays.asList("apple", "banana", "melon", "pear"), 677 "absent element"); 678 679 assertEquals("pear", set.ceiling("nonexistent")); 680 assertEquals("melon", set.floor("nonexistent")); 681 } 682 683 public void test_synchronizedNavigableMap_replaceAll() { 684 NavigableMap<String, Integer> map = synchronizedNavigableMap( 685 new TreeMap<>(createMap("key3", 3, "key1", 1, "key4", 4, "key2", 2))); 686 map.replaceAll((k, v) -> 5 * v); 687 assertEquals(map, createMap("key3", 15, "key1", 5, "key4", 20, "key2", 10)); 688 } 689 690 public void test_synchronizedNavigableMap_putIfAbsent() { 691 MapDefaultMethodTester.test_putIfAbsent( 692 Collections.synchronizedNavigableMap(new TreeMap<>()), 693 false /* acceptsNullKey */, true /* acceptsNullValue */); 694 } 695 696 public void test_synchronizedNavigableMap_remove() { 697 MapDefaultMethodTester.test_remove( 698 Collections.synchronizedNavigableMap(new TreeMap<>()), 699 false /* acceptsNullKey */, true /* acceptsNullValue */); 700 } 701 702 public void test_synchronizedNavigableMap_replace$K$V$V() { 703 MapDefaultMethodTester.test_replace$K$V$V( 704 Collections.synchronizedNavigableMap(new TreeMap<>()), 705 false /* acceptsNullKey */, true /* acceptsNullValue */); 706 } 707 708 public void test_synchronizedNavigableMap_replace$K$V() { 709 MapDefaultMethodTester.test_replace$K$V( 710 Collections.synchronizedNavigableMap(new TreeMap<>()), 711 false /* acceptsNullKey */, true /* acceptsNullValue */); 712 } 713 714 public void test_synchronizedNavigableMap_computeIfAbsent() { 715 MapDefaultMethodTester.test_computeIfAbsent( 716 Collections.synchronizedNavigableMap(new TreeMap<>()), 717 false /* acceptsNullKey */, true /* acceptsNullValue */); 718 } 719 720 public void test_synchronizedNavigableMap_computeIfPresent() { 721 MapDefaultMethodTester.test_computeIfPresent( 722 Collections.synchronizedNavigableMap(new TreeMap<>()), 723 false /* acceptsNullKey */); 724 } 725 726 public void test_synchronizedNavigableMap_compute() { 727 MapDefaultMethodTester.test_compute( 728 Collections.synchronizedNavigableMap(new TreeMap<>()), 729 false /* acceptsNullKey */); 730 } 731 732 public void test_synchronizedNavigableMap_merge() { 733 MapDefaultMethodTester.test_merge( 734 Collections.synchronizedNavigableMap(new TreeMap<>()), 735 false /* acceptsNullKey */); 736 } 737 738 public void test_synchronizedNavigableMap_keySet() { 739 NavigableMap<String, Integer> map = synchronizedNavigableMap( 740 new TreeMap<>(createMap("key3", 3, "key1", 1, "key4", 4, "key2", 2))); 741 // Note: keySet() returns a Collections$UnmodifiableSet (not instanceof NavigableSet) 742 Set<String> set = map.keySet(); 743 check_orderedSet(set, Arrays.asList("key1", "key2", "key3", "key4")); 744 } 745 746 public void test_synchronizedNavigableMap_navigableKeySet() { 747 NavigableMap<String, Integer> map = synchronizedNavigableMap( 748 new TreeMap<>(createMap("key3", 3, "key1", 1, "key4", 4, "key2", 2))); 749 NavigableSet<String> set = map.navigableKeySet(); 750 check_navigableSet(set, Arrays.asList("key1", "key2", "key3", "key4"), "absent element"); 751 } 752 753 public void test_synchronizedNavigableMap_descendingMap_descendingKeySet() { 754 NavigableMap<String, Integer> map = synchronizedNavigableMap( 755 new TreeMap<>(createMap("key3", 3, "key1", 1, "key4", 4, "key2", 2))); 756 NavigableSet<String> set = map.descendingMap().descendingKeySet(); 757 check_navigableSet(set, Arrays.asList("key1", "key2", "key3", "key4"), "absent element"); 758 } 759 760 public void test_synchronizedNavigableMap_descendingKeySet() { 761 NavigableMap<String, Integer> map = synchronizedNavigableMap( 762 new TreeMap<>(createMap("key3", 3, "key1", 1, "key4", 4, "key2", 2))); 763 NavigableSet<String> set = map.descendingKeySet(); 764 check_navigableSet(set, Arrays.asList("key4", "key3", "key2", "key1"), "absent element"); 765 } 766 767 public void test_synchronizedNavigableMap_descendingMap_keySet() { 768 NavigableMap<String, Integer> map = synchronizedNavigableMap( 769 new TreeMap<>(createMap("key3", 3, "key1", 1, "key4", 4, "key2", 2))); 770 // Note: keySet() returns a Collections$UnmodifiableSet (not instanceof NavigableSet) 771 Set<String> set = map.descendingMap().keySet(); 772 check_orderedSet(set, Arrays.asList("key4", "key3", "key2", "key1")); 773 } 774 775 public void test_synchronizedNavigableMap_descendingMap_navigableKeySet() { 776 NavigableMap<String, Integer> map = synchronizedNavigableMap( 777 new TreeMap<>(createMap("key3", 3, "key1", 1, "key4", 4, "key2", 2))); 778 NavigableSet<String> set = map.descendingMap().navigableKeySet(); 779 check_navigableSet(set, Arrays.asList("key4", "key3", "key2", "key1"), "absent element"); 780 } 781 782 public void test_synchronizedNavigableMap_values() { 783 NavigableMap<String, Integer> map = synchronizedNavigableMap( 784 new TreeMap<>(createMap("key3", 3, "key1", 1, "key4", 4, "key2", 2))); 785 Collection<Integer> values = map.values(); 786 check_orderedCollection(values, Arrays.asList(1, 2, 3, 4)); 787 } 788 789 public void test_synchronizedNavigableMap_descendingMap_values() { 790 NavigableMap<String, Integer> map = synchronizedNavigableMap( 791 new TreeMap<>(createMap("key3", 3, "key1", 1, "key4", 4, "key2", 2))); 792 Collection<Integer> values = map.descendingMap().values(); 793 check_orderedCollection(values, Arrays.asList(4, 3, 2, 1)); 794 } 795 796 public void test_synchronizedNavigableSet_empty() { 797 NavigableSet<String> set = Collections.synchronizedNavigableSet(new TreeSet<>()); 798 check_navigableSet(set, new ArrayList<>(), "absent element"); 799 } 800 801 public void test_synchronizedNavigableSet_nonEmpty() { 802 List<String> elements = Arrays.asList("apple", "banana", "melon", "pear"); 803 NavigableSet<String> set = Collections.synchronizedNavigableSet(new TreeSet<>(elements)); 804 check_navigableSet(set, elements, "absent element"); 805 } 806 807 private static<K,V> void check_unmodifiableNavigableMap_defaultMethods(NavigableMap<K,V> map, 808 List<K> keysInOrder, List<V> valuesInOrder, K absentKey, V absentValue) { 809 check_unmodifiableOrderedMap_defaultMethods(map, keysInOrder, valuesInOrder, 810 absentKey, absentValue); 811 812 List<K> reverseKeys = reverseCopyOf(keysInOrder); 813 List<V> reverseValues = reverseCopyOf(valuesInOrder); 814 815 check_unmodifiableOrderedMap_defaultMethods(map.descendingMap(), reverseKeys, 816 reverseValues, absentKey, absentValue); 817 818 int numEntries = keysInOrder.size(); 819 for (int i = 0; i < numEntries; i++) { 820 K key = keysInOrder.get(i); 821 V value = valuesInOrder.get(i); 822 823 check_unmodifiableOrderedMap_defaultMethods( 824 map.headMap(key), 825 keysInOrder.subList(0, i), 826 valuesInOrder.subList(0, i), 827 absentKey, 828 absentValue); 829 check_unmodifiableOrderedMap_defaultMethods( 830 map.headMap(key, false /* inclusive */), 831 keysInOrder.subList(0, i), 832 valuesInOrder.subList(0, i), 833 absentKey, 834 absentValue); 835 check_unmodifiableOrderedMap_defaultMethods( 836 map.headMap(key, true /* inclusive */), 837 keysInOrder.subList(0, i + 1), 838 valuesInOrder.subList(0, i + 1), 839 absentKey, 840 absentValue); 841 K lowerKey = map.lowerKey(key); 842 if (lowerKey != null) { 843 // headMap inclusive of lowerKey is same as exclusive of key 844 check_unmodifiableOrderedMap_defaultMethods( 845 map.headMap(lowerKey, true /* inclusive */), 846 keysInOrder.subList(0, i), 847 valuesInOrder.subList(0, i), 848 absentKey, 849 absentValue); 850 } 851 852 check_unmodifiableOrderedMap_defaultMethods( 853 map.tailMap(key), 854 keysInOrder.subList(i, numEntries), 855 valuesInOrder.subList(i, numEntries), 856 absentKey, 857 absentValue); 858 check_unmodifiableOrderedMap_defaultMethods( 859 map.tailMap(key, true /* inclusive */), 860 keysInOrder.subList(i, numEntries), 861 valuesInOrder.subList(i, numEntries), 862 absentKey, 863 absentValue); 864 check_unmodifiableOrderedMap_defaultMethods( 865 map.tailMap(key, false /* inclusive */), 866 keysInOrder.subList(i + 1, numEntries), 867 valuesInOrder.subList(i + 1, numEntries), 868 absentKey, 869 absentValue); 870 K higherKey = map.higherKey(key); 871 if (higherKey != null) { 872 // headMap inclusive of higherKey is same as exclusive of key 873 check_unmodifiableOrderedMap_defaultMethods( 874 map.tailMap(higherKey, true /* inclusive */), 875 keysInOrder.subList(i + 1, numEntries), 876 valuesInOrder.subList(i + 1, numEntries), 877 absentKey, 878 absentValue); 879 } 880 881 int headSize = map.headMap(absentKey).size(); 882 check_unmodifiableOrderedMap_defaultMethods( 883 map.headMap(absentKey, true /* inclusive */), 884 keysInOrder.subList(0, headSize), 885 valuesInOrder.subList(0, headSize), 886 absentKey, 887 absentValue); 888 check_unmodifiableOrderedMap_defaultMethods( 889 map.tailMap(absentKey, true /* inclusive */), 890 keysInOrder.subList(headSize, numEntries), 891 valuesInOrder.subList(headSize, numEntries), 892 absentKey, 893 absentValue); 894 895 assertEquals(key, map.floorKey(key)); 896 assertEquals(key, map.ceilingKey(key)); 897 assertEquals(new AbstractMap.SimpleEntry<>(key, value), map.floorEntry(key)); 898 assertEquals(new AbstractMap.SimpleEntry<>(key, value), map.ceilingEntry(key)); 899 } 900 901 K floor = map.floorKey(absentKey); 902 K ceiling = map.ceilingKey(absentKey); 903 if (numEntries == 0) { 904 assertNull(floor); 905 assertNull(ceiling); 906 } else { 907 assertFalse(Objects.equals(floor, ceiling)); 908 assertTrue(floor != null || ceiling != null); 909 assertEquals(ceiling, floor == null ? map.firstKey() : map.higherKey(floor)); 910 assertEquals(floor, ceiling == null ? map.lastKey() : map.lowerKey(ceiling)); 911 } 912 } 913 914 /** 915 * Tests Map's default methods (getOrDefault, forEach, ...) on the given Map. 916 * 917 * @param keysInOrder the expected keys in the map, in iteration order 918 * @param valuesInOrder the expected values in the map, in iteration order 919 * @param absentKey a key that does not occur in the map 920 * @param absentValue a value that does not occur in the map 921 */ 922 private static<K,V> void check_unmodifiableOrderedMap_defaultMethods(Map<K,V> map, 923 List<K> keysInOrder, List<V> valuesInOrder, K absentKey, V absentValue) { 924 if (keysInOrder.size() != valuesInOrder.size()) { 925 throw new IllegalArgumentException(); 926 } 927 Map<K, V> mapCopy = new LinkedHashMap<K, V>(map); 928 929 // getOrDefault 930 int numEntries = keysInOrder.size(); 931 for (int i = 0; i < numEntries; i++) { 932 assertEquals(valuesInOrder.get(i), map.getOrDefault(keysInOrder.get(i), null)); 933 } 934 935 // forEach 936 List<K> keysCopy = new ArrayList<>(); 937 List<V> valuesCopy = new ArrayList<>(); 938 map.forEach((k, v) -> { 939 keysCopy.add(k); 940 valuesCopy.add(v); 941 }); 942 assertEquals(keysInOrder, keysCopy); 943 assertEquals(valuesInOrder, valuesCopy); 944 945 assertThrowsUoe(() -> { map.putIfAbsent(absentKey, absentValue); }); 946 assertThrowsUoe(() -> { map.remove(absentKey); }); 947 assertThrowsUoe(() -> { map.replace(absentKey, absentValue, absentValue); }); 948 assertThrowsUoe(() -> { map.replace(absentKey, absentValue); }); 949 assertThrowsUoe(() -> { map.computeIfAbsent(absentKey, k -> absentValue); }); 950 assertThrowsUoe(() -> { map.computeIfPresent(absentKey, (k, v) -> absentValue); }); 951 assertThrowsUoe(() -> { map.compute(absentKey, (k, v) -> absentValue); }); 952 assertThrowsUoe(() -> { map.merge(absentKey, absentValue, (k, v) -> absentValue); }); 953 954 if (numEntries > 0) { 955 K sampleKey = keysInOrder.get(0); 956 V sampleValue = valuesInOrder.get(0); 957 assertThrowsUoe(() -> { map.putIfAbsent(sampleKey, absentValue); }); 958 assertThrowsUoe(() -> { map.remove(sampleKey); }); 959 assertThrowsUoe(() -> { map.replace(sampleKey, sampleValue, absentValue); }); 960 assertThrowsUoe(() -> { map.replace(sampleKey, absentValue); }); 961 assertThrowsUoe(() -> { map.computeIfAbsent(sampleKey, k -> absentValue); }); 962 assertThrowsUoe(() -> { map.computeIfPresent(sampleKey, (k, v) -> absentValue); }); 963 assertThrowsUoe(() -> { map.compute(sampleKey, (k, v) -> absentValue); }); 964 assertThrowsUoe(() -> { map.merge(sampleKey, sampleValue, (k, v) -> absentValue); }); 965 } 966 967 // Check that map is unchanged 968 assertEquals(mapCopy, map); 969 } 970 971 /** 972 * Tests the various {@code Collection} views of the given Map for contents/ 973 * iteration order consistent with the given expectations. 974 */ 975 private static<K,V> void check_unmodifiableNavigableMap_collectionViews( 976 NavigableMap<K, V> map, List<K> keysInOrder, List<V> valuesInOrder, K absentKey) { 977 List<K> reverseKeys = reverseCopyOf(keysInOrder); 978 979 // keySet 980 check_unmodifiableSet(map.keySet(), absentKey); 981 check_orderedSet(map.keySet(), keysInOrder); 982 983 // navigableKeySet 984 check_unmodifiableNavigableSet(map.navigableKeySet(), keysInOrder, absentKey); 985 986 // descendingMap -> descendingKeySet 987 check_unmodifiableNavigableSet( 988 map.descendingMap().descendingKeySet(), keysInOrder, absentKey); 989 990 // descendingKeySet 991 check_unmodifiableNavigableSet(map.descendingKeySet(), reverseKeys, absentKey); 992 993 // descendingMap -> keySet 994 check_unmodifiableSet(map.descendingMap().keySet(), absentKey); 995 check_orderedSet(map.descendingMap().keySet(), reverseKeys); 996 997 // descendingMap -> navigableKeySet 998 check_unmodifiableNavigableSet( 999 map.descendingMap().navigableKeySet(), reverseKeys, absentKey); 1000 1001 // values 1002 check_unmodifiableOrderedCollection(map.values(), valuesInOrder); 1003 check_orderedCollection(map.values(), valuesInOrder); 1004 1005 // descendingValues 1006 check_unmodifiableOrderedCollection(map.descendingMap().values(), reverseCopyOf(valuesInOrder)); 1007 check_orderedCollection(map.descendingMap().values(), reverseCopyOf(valuesInOrder)); 1008 } 1009 1010 /** 1011 * @param absentKeyHead absent key smaller than {@code presentKey}, under the Map's ordering 1012 * @param absentKeyTail absent key larger than {@code presentKey}, under the Map's ordering 1013 */ 1014 private static<K,V> void check_navigableMap_isChecked(NavigableMap map, 1015 K presentKey, V presentValue, K absentKeyHead, K absentKeyTail, V absentValue) { 1016 check_map_isChecked(map, 1017 presentKey, presentValue, absentKeyHead, absentValue); 1018 check_map_isChecked(map.descendingMap(), 1019 presentKey, presentValue, absentKeyHead, absentValue); 1020 1021 // Need to pass correct absent key since the Map might check for 1022 // range inclusion before checking the type of a value 1023 check_map_isChecked(map.headMap(presentKey, true /* inclusive */), 1024 presentKey, presentValue, absentKeyHead, absentValue); 1025 check_map_isChecked(map.tailMap(presentKey, true /* inclusive */), 1026 presentKey, presentValue, absentKeyTail, absentValue); 1027 } 1028 1029 /** 1030 * Asserts that the given map is checked (rejects keys/values of type Object). 1031 * 1032 * @param map a checked Map that contains the entry (presentKey, preventValue), does not 1033 * contain key absentKey or value absentValue, and rejects keys/types of type Object. 1034 */ 1035 private static<K,V> void check_map_isChecked(Map map, 1036 K presentKey, V presentValue, K absentKey, V absentValue) { 1037 Map copyOfMap = new HashMap(map); 1038 assertEquals(map.get(presentKey), presentValue); 1039 assertFalse(map.containsKey(absentKey)); 1040 assertFalse(map.values().contains(absentValue)); 1041 1042 assertThrowsCce(() -> { map.replaceAll((k, v) -> new Object()); }); 1043 1044 assertThrowsCce(() -> { map.putIfAbsent(presentKey, new Object()); }); 1045 assertThrowsCce(() -> { map.putIfAbsent(absentKey, new Object()); }); 1046 assertThrowsCce(() -> { map.putIfAbsent(new Object(), presentValue); }); 1047 1048 assertThrowsCce(() -> { map.remove(new Object()); }); 1049 1050 assertThrowsCce(() -> { map.replace(new Object(), presentValue); }); 1051 assertThrowsCce(() -> { map.replace(presentKey, new Object()); }); 1052 1053 assertThrowsCce(() -> { map.replace(new Object(), presentValue, absentValue); }); 1054 // doesn't throw, but has no effect since oldValue doesn't match 1055 assertFalse(map.replace(presentKey, new Object(), absentValue)); 1056 assertThrowsCce(() -> { map.replace(presentKey, presentValue, new Object()); }); 1057 1058 assertThrowsCce(() -> { map.computeIfAbsent(new Object(), k -> presentValue); }); 1059 // doesn't throw, but has no effect since presentKey is present 1060 assertEquals(presentValue, map.computeIfAbsent(presentKey, k -> new Object())); 1061 assertThrowsCce(() -> { map.computeIfAbsent(absentKey, k -> new Object()); }); 1062 1063 assertThrowsCce(() -> { map.computeIfPresent(new Object(), (k, v) -> presentValue); }); 1064 assertThrowsCce(() -> { map.computeIfPresent(presentKey, (k, v) -> new Object()); }); 1065 // doesn't throw, but has no effect since absentKey is absent 1066 assertNull(map.computeIfPresent(absentKey, (k, v) -> new Object())); 1067 1068 assertThrowsCce(() -> { map.compute(new Object(), (k, v) -> presentValue); }); 1069 assertThrowsCce(() -> { map.compute(presentKey, (k, v) -> new Object()); }); 1070 assertThrowsCce(() -> { map.compute(absentKey, (k, v) -> new Object()); }); 1071 1072 assertThrowsCce(() -> { map.merge(new Object(), presentValue, (v1, v2) -> presentValue); }); 1073 assertThrowsCce(() -> { map.merge(presentKey, presentValue, (v1, v2) -> new Object()); }); 1074 1075 // doesn't throw, puts (absentKey, absentValue) into the map 1076 map.merge(absentKey, absentValue, (v1, v2) -> new Object()); 1077 assertEquals(absentValue, map.remove(absentKey)); // restore previous state 1078 1079 assertThrowsCce(() -> { map.put(new Object(), absentValue); }); 1080 assertThrowsCce(() -> { map.put(absentKey, new Object()); }); 1081 assertThrowsCce(() -> { map.put(new Object(), presentValue); }); 1082 assertThrowsCce(() -> { map.put(presentKey, new Object()); }); 1083 1084 assertEquals("map should be unchanged", copyOfMap, map); 1085 } 1086 1087 private static <K> void check_unmodifiableNavigableSet(NavigableSet<K> set, 1088 List<K> expectedElementsInOrder, K absentElement) { 1089 check_unmodifiableSet(set, absentElement); 1090 check_unmodifiableSet(set.descendingSet(), absentElement); 1091 check_navigableSet(set, expectedElementsInOrder, absentElement); 1092 if (!expectedElementsInOrder.isEmpty()) { 1093 K sampleElement = expectedElementsInOrder.get(expectedElementsInOrder.size() / 2); 1094 check_unmodifiableSet(set.headSet(sampleElement), absentElement); 1095 check_unmodifiableSet(set.tailSet(sampleElement), absentElement); 1096 } 1097 } 1098 1099 private static <K> void check_navigableSet(NavigableSet<K> set, 1100 List<K> expectedElementsInOrder, K absentElement) { 1101 check_orderedSet(set, expectedElementsInOrder); 1102 check_set(set, absentElement); 1103 1104 int numElements = set.size(); 1105 List<K> reverseOrder = new ArrayList<>(expectedElementsInOrder); 1106 Collections.reverse(reverseOrder); 1107 check_orderedSet(set.descendingSet(), reverseOrder); 1108 1109 for (int i = 0; i < numElements; i++) { 1110 K element = expectedElementsInOrder.get(i); 1111 check_orderedSet( 1112 set.headSet(element), 1113 expectedElementsInOrder.subList(0, i)); 1114 check_orderedSet( 1115 set.headSet(element, false /* inclusive */), 1116 expectedElementsInOrder.subList(0, i)); 1117 check_orderedSet( 1118 set.headSet(element, true /* inclusive */), 1119 expectedElementsInOrder.subList(0, i + 1)); 1120 1121 check_orderedSet( 1122 set.tailSet(element), 1123 expectedElementsInOrder.subList(i, numElements)); 1124 check_orderedSet( 1125 set.tailSet(element, true /* inclusive */), 1126 expectedElementsInOrder.subList(i, numElements)); 1127 check_orderedSet( 1128 set.tailSet(element, false /* inclusive */), 1129 expectedElementsInOrder.subList(i + 1, numElements)); 1130 1131 assertEquals(element, set.floor(element)); 1132 assertEquals(element, set.ceiling(element)); 1133 } 1134 1135 K floor = set.floor(absentElement); 1136 K ceiling = set.ceiling(absentElement); 1137 if (numElements == 0) { 1138 assertNull(floor); 1139 assertNull(ceiling); 1140 } else { 1141 assertFalse(Objects.equals(floor, ceiling)); 1142 assertTrue(floor != null || ceiling != null); 1143 } 1144 } 1145 1146 /** 1147 * Checks a Set that may or may not be instanceof SortedSet / NavigableSet 1148 * for adherence to a specified iteration order. 1149 */ 1150 private static <K> void check_orderedSet( 1151 Set<K> set, List<K> expectedElementsInOrder) { 1152 assertEquals(expectedElementsInOrder, new ArrayList<>(set)); 1153 Set<K> copy = new HashSet<>(expectedElementsInOrder); 1154 assertEquals(copy, set); 1155 assertEquals(copy.hashCode(), set.hashCode()); 1156 1157 int numElements = set.size(); 1158 assertEquals(expectedElementsInOrder.size(), numElements); 1159 Spliterator<K> spliterator = set.spliterator(); 1160 SpliteratorTester.runBasicIterationTests(spliterator, expectedElementsInOrder); 1161 if (spliterator.hasCharacteristics(SIZED)) { 1162 SpliteratorTester.runSizedTests(set, numElements); 1163 } 1164 if (spliterator.hasCharacteristics(SUBSIZED)) { 1165 SpliteratorTester.runSubSizedTests(set, numElements); 1166 } 1167 assertHasCharacteristics(ORDERED | DISTINCT, spliterator); 1168 SpliteratorTester.runOrderedTests(set); 1169 } 1170 1171 private static <K> void check_unmodifiableSet(Set<K> set, K absentElement) { 1172 assertThrowsUoe(() -> { set.remove(null); } ); 1173 assertThrowsUoe(set::clear); 1174 assertThrowsUoe(() -> { set.add(null); } ); 1175 if (set.isEmpty()) { 1176 assertEquals(0, set.size()); 1177 } else { 1178 assertTrue(set.size() > 0); 1179 Iterator<K> iterator = set.iterator(); 1180 K firstElement = iterator.next(); 1181 assertThrowsUoe(() -> { set.remove(firstElement); } ); 1182 assertThrowsUoe(iterator::remove); 1183 } 1184 SpliteratorTester.runDistinctTests(set); 1185 1186 check_set(set, absentElement); 1187 } 1188 1189 private static <K> void check_set(Set<K> set, K absentElement) { 1190 // some basic properties that must hold for all sets (regardless of whether 1191 // they're ordered, strict, support null, ...): 1192 if (!set.isEmpty()) { 1193 K sampleElement = set.iterator().next(); 1194 assertTrue(set.contains(sampleElement)); 1195 } 1196 assertFalse(set.contains(absentElement)); 1197 } 1198 1199 private static <V> void check_unmodifiableOrderedCollection( 1200 Collection<V> values, List<V> elementsInOrder) { 1201 assertThrowsUoe(() -> { values.remove(null); } ); 1202 assertThrowsUoe(values::clear); 1203 assertThrowsUoe(() -> { values.add(null); } ); 1204 1205 Iterator<V> iterator = values.iterator(); 1206 if (!elementsInOrder.isEmpty()) { 1207 iterator.next(); 1208 assertThrowsUoe(iterator::remove); 1209 assertThrowsUoe(() -> { values.remove(elementsInOrder.get(0)); }); 1210 } 1211 check_orderedCollection(values, elementsInOrder); 1212 } 1213 1214 private static <V> void check_orderedCollection( 1215 Collection<V> collection, List<V> elementsInOrder) { 1216 Spliterator<V> spliterator = collection.spliterator(); 1217 SpliteratorTester.runBasicIterationTests(spliterator, elementsInOrder); 1218 if (spliterator.hasCharacteristics(SIZED)) { 1219 SpliteratorTester.runSizedTests(collection, elementsInOrder.size()); 1220 } 1221 if (spliterator.hasCharacteristics(SUBSIZED)) { 1222 SpliteratorTester.runSubSizedTests(collection, elementsInOrder.size()); 1223 } 1224 SpliteratorTester.runOrderedTests(collection); 1225 } 1226 1227 public void test_EmptyMap_getOrDefault() { 1228 Map<Integer, Double> m = Collections.emptyMap(); 1229 assertEquals(-1.0, m.getOrDefault(1, -1.0)); 1230 assertEquals(-1.0, m.getOrDefault(2, -1.0)); 1231 } 1232 1233 public void test_EmptyMap_forEach() { 1234 try { 1235 Collections.emptyMap().forEach(null); 1236 fail(); 1237 } catch (NullPointerException expected) { 1238 } 1239 } 1240 1241 public void test_EmptyMap_putIfAbsent() { 1242 try { 1243 Collections.emptyMap().putIfAbsent(1, 5.0); 1244 fail(); 1245 } catch (UnsupportedOperationException expected) { 1246 } 1247 } 1248 1249 public void test_EmptyMap_remove() { 1250 try { 1251 Collections.emptyMap().remove(1, 5.0); 1252 fail(); 1253 } catch (UnsupportedOperationException expected) { 1254 } 1255 } 1256 1257 public void test_EmptyMap_replace$K$V$V() { 1258 try { 1259 Collections.emptyMap().replace(1, 5.0, 5.0); 1260 fail(); 1261 } catch (UnsupportedOperationException expected) { 1262 } 1263 } 1264 1265 public void test_EmptyMap_replace$K$V() { 1266 try { 1267 Collections.emptyMap().replace(1, 5.0); 1268 fail(); 1269 } catch (UnsupportedOperationException expected) { 1270 } 1271 } 1272 1273 public void test_EmptyMap_computeIfAbsent() { 1274 try { 1275 Collections.emptyMap().computeIfAbsent(1, k -> 5.0); 1276 fail(); 1277 } catch (UnsupportedOperationException expected) { 1278 } 1279 } 1280 1281 public void test_EmptyMap_computeIfPresent() { 1282 try { 1283 Collections.emptyMap().computeIfPresent(1, (k, v) -> 5.0); 1284 fail(); 1285 } catch (UnsupportedOperationException expected) { 1286 } 1287 } 1288 1289 public void test_EmptyMap_compute() { 1290 try { 1291 Collections.emptyMap().compute(1, (k, v) -> 5.0); 1292 fail(); 1293 } catch (UnsupportedOperationException expected) { 1294 } 1295 } 1296 1297 public void test_EmptyMap_merge() { 1298 try { 1299 Collections.emptyMap().merge(1, 5.0, (k, v) -> 5.0); 1300 fail(); 1301 } catch (UnsupportedOperationException expected) { 1302 } 1303 } 1304 1305 public void test_SingletonMap_getOrDefault() { 1306 Map<Integer, Double> m = Collections.singletonMap(1, 11.0); 1307 assertEquals(11.0, m.getOrDefault(1, -1.0)); 1308 assertEquals(-1.0, m.getOrDefault(2, -1.0)); 1309 } 1310 1311 public void test_SingletonMap_forEach() { 1312 Map<Integer, Double> m = new HashMap<>(); 1313 Collections.singletonMap(1, 11.0).forEach(m::put); 1314 assertEquals(11.0, m.getOrDefault(1, -1.0)); 1315 assertEquals(1, m.size()); 1316 } 1317 1318 public void test_SingletonMap_putIfAbsent() { 1319 try { 1320 Collections.singletonMap(1, 11.0).putIfAbsent(1, 5.0); 1321 fail(); 1322 } catch (UnsupportedOperationException expected) { 1323 } 1324 } 1325 1326 public void test_SingletonMap_remove() { 1327 try { 1328 Collections.singletonMap(1, 11.0).remove(1, 5.0); 1329 fail(); 1330 } catch (UnsupportedOperationException expected) { 1331 } 1332 } 1333 1334 public void test_SingletonMap_replace$K$V$V() { 1335 try { 1336 Collections.singletonMap(1, 11.0).replace(1, 5.0, 5.0); 1337 fail(); 1338 } catch (UnsupportedOperationException expected) { 1339 } 1340 } 1341 1342 public void test_SingletonMap_replace$K$V() { 1343 try { 1344 Collections.singletonMap(1, 11.0).replace(1, 5.0); 1345 fail(); 1346 } catch (UnsupportedOperationException expected) { 1347 } 1348 } 1349 1350 public void test_SingletonMap_computeIfAbsent() { 1351 try { 1352 Collections.singletonMap(1, 11.0).computeIfAbsent(1, k -> 5.0); 1353 fail(); 1354 } catch (UnsupportedOperationException expected) { 1355 } 1356 } 1357 1358 public void test_SingletonMap_computeIfPresent() { 1359 try { 1360 Collections.singletonMap(1, 11.0).computeIfPresent(1, (k, v) -> 5.0); 1361 fail(); 1362 } catch (UnsupportedOperationException expected) { 1363 } 1364 } 1365 1366 public void test_SingletonMap_compute() { 1367 try { 1368 Collections.singletonMap(1, 11.0).compute(1, (k, v) -> 5.0); 1369 fail(); 1370 } catch (UnsupportedOperationException expected) { 1371 } 1372 } 1373 1374 public void test_SingletonMap_merge() { 1375 try { 1376 Collections.singletonMap(1, 11.0).merge(1, 5.0, (k, v) -> 5.0); 1377 fail(); 1378 } catch (UnsupportedOperationException expected) { 1379 } 1380 } 1381 1382 public void test_SynchronizedList_replaceAll() { 1383 ListDefaultMethodTester.test_replaceAll(Collections.synchronizedList(new ArrayList<>())); 1384 } 1385 1386 public void test_SynchronizedList_sort() { 1387 ListDefaultMethodTester.test_sort(Collections.synchronizedList(new ArrayList<>())); 1388 } 1389 1390 public void test_CheckedList_replaceAll() { 1391 ListDefaultMethodTester.test_replaceAll(Collections.checkedList(new ArrayList<>(), Integer.class)); 1392 } 1393 1394 public void test_CheckedList_sort() { 1395 ListDefaultMethodTester.test_sort(Collections.checkedList(new ArrayList<>(), Double.class)); 1396 } 1397 1398 public void test_EmptyList_replaceAll() { 1399 Collections.emptyList().replaceAll(k -> 1); 1400 1401 try { 1402 Collections.emptyList().replaceAll(null); 1403 fail(); 1404 } catch (NullPointerException expected) { 1405 } 1406 } 1407 1408 public void test_EmptyList_sort() { 1409 Collections.emptyList().sort((k1, k2) -> 1); 1410 } 1411 1412 public void test_emptyNavigableMap() { 1413 NavigableMap<String, Integer> map = Collections.emptyNavigableMap(); 1414 check_unmodifiableNavigableMap_defaultMethods( 1415 map, 1416 new ArrayList<>() /* keysInOrder */, 1417 new ArrayList<>() /* valuesInOrder */, 1418 "absent key" /* absentKey */, 1419 -1 /* absentValue */ 1420 ); 1421 check_unmodifiableNavigableMap_collectionViews( 1422 map, 1423 new ArrayList<>() /* keysInOrder */, 1424 new ArrayList<>() /* valuesInOrder */, 1425 "absent key" /* absentKey */); 1426 } 1427 1428 public void test_emptyNavigableSet() { 1429 NavigableSet<String> set = Collections.emptyNavigableSet(); 1430 check_unmodifiableNavigableSet(set, new ArrayList<>() /* expectedElementsInOrder */, 1431 "absent element"); 1432 check_navigableSet(set, new ArrayList<>() /* expectedElementsInOrder */, "absent element"); 1433 } 1434 1435 public void test_emptySortedMap() { 1436 SortedMap<String, Integer> map = Collections.emptySortedMap(); 1437 1438 check_unmodifiableOrderedMap_defaultMethods( 1439 map, 1440 new ArrayList<>() /* keysInOrder */, 1441 new ArrayList<>() /* valuesInOrder */, 1442 "absent key" /* absentKey */, 1443 -1 /* absentValue */); 1444 check_unmodifiableSet(map.keySet(), "absent element"); 1445 check_orderedSet(map.keySet(), new ArrayList<>() /* expectedElementsInOrder */); 1446 check_unmodifiableSet(map.entrySet(), new AbstractMap.SimpleEntry<>("absent element", 42)); 1447 check_orderedCollection(map.values(), new ArrayList<>() /* expectedValuesInOrder */); 1448 } 1449 1450 public void test_emptySortedSet() { 1451 SortedSet<String> set = Collections.emptySortedSet(); 1452 check_unmodifiableSet(set, "absent element"); 1453 check_orderedSet(set, new ArrayList<>() /* expectedElementsInOrder */); 1454 } 1455 1456 public void test_unmodifiableList_replaceAll() { 1457 try { 1458 Collections.unmodifiableList(new ArrayList<>()).replaceAll(k -> 1); 1459 fail(); 1460 } catch (UnsupportedOperationException expected) { 1461 } 1462 1463 // with non empty list 1464 1465 try { 1466 ArrayList l = new ArrayList(); 1467 l.add(1); 1468 l.add(2); 1469 Collections.unmodifiableList(l).replaceAll(k -> 1); 1470 fail(); 1471 } catch (UnsupportedOperationException expected) { 1472 } 1473 } 1474 1475 public void test_unmodifiableList_sort() { 1476 try { 1477 Collections.unmodifiableList(new ArrayList<>()).sort((k1, k2) -> 1); 1478 fail(); 1479 } catch (UnsupportedOperationException expected) { 1480 } 1481 1482 // with non empty list 1483 1484 try { 1485 ArrayList l = new ArrayList(); 1486 l.add(1); 1487 l.add(2); 1488 Collections.unmodifiableList(l).sort((k1, k2) -> 1); 1489 fail(); 1490 } catch (UnsupportedOperationException expected) { 1491 } 1492 } 1493 1494 public void test_SingletonList_replaceAll() { 1495 try { 1496 Collections.singletonList(1).replaceAll(k -> 2); 1497 fail(); 1498 } catch (UnsupportedOperationException expected) { 1499 } 1500 } 1501 1502 public void test_SingletonList_sort() { 1503 Collections.singletonList(1).sort((k1, k2) -> 2); 1504 } 1505 1506 public void test_CheckedMap_replaceAll() { 1507 Map<Integer, Integer> map = new HashMap<>(); 1508 Map checkedMap = Collections.checkedMap(map, Integer.class, Integer.class); 1509 checkedMap.put(1, 10); 1510 checkedMap.put(2, 20); 1511 checkedMap.put(3, 30); 1512 checkedMap.replaceAll((k, v) -> (Integer)k + (Integer)v); 1513 assertEquals(11, checkedMap.get(1)); 1514 assertEquals(22, checkedMap.get(2)); 1515 assertEquals(33, checkedMap.get(3)); 1516 assertEquals(3, checkedMap.size()); 1517 } 1518 1519 public void test_CheckedMap_putIfAbsent() { 1520 Map<Integer, Double> map = new HashMap<>(); 1521 Map checkedMap = Collections.checkedMap(map, Integer.class, Double.class); 1522 MapDefaultMethodTester.test_putIfAbsent(checkedMap, true /* acceptsNullKey */, 1523 true /* acceptsNullValue */); 1524 1525 // Without generics to check the typeCheck implementation 1526 Map checkedMap2 = Collections.checkedMap(new HashMap<>(), Integer.class, String.class); 1527 1528 // When key is present 1529 checkedMap2.putIfAbsent(1, A_STRING); 1530 try { 1531 checkedMap2.putIfAbsent(1, NOT_A_STRING); 1532 fail(); 1533 } catch (ClassCastException expected) {} 1534 1535 // When key is absent 1536 checkedMap2.clear(); 1537 try { 1538 checkedMap2.putIfAbsent(1, NOT_A_STRING); 1539 fail(); 1540 } catch (ClassCastException expected) {} 1541 } 1542 1543 public void test_CheckedMap_remove() { 1544 Map<Integer, Double> map = new HashMap<>(); 1545 Map checkedMap = Collections.checkedMap(map, Integer.class, Double.class); 1546 MapDefaultMethodTester.test_remove(checkedMap, true /* acceptsNullKey */, 1547 true /* acceptsNullValue */); 1548 } 1549 1550 public void test_CheckedMap_replace$K$V$V() { 1551 Map<Integer, Double> map = new HashMap<>(); 1552 Map checkedMap = Collections.checkedMap(map, Integer.class, Double.class); 1553 MapDefaultMethodTester.test_replace$K$V$V(checkedMap, true /* acceptsNullKey */, 1554 true /* acceptsNullValue */); 1555 1556 // Without generics to check the typeCheck implementation 1557 Map checkedMap2 = Collections.checkedMap(new HashMap<>(), Integer.class, String.class); 1558 checkedMap2.put(1, A_STRING); 1559 1560 try { 1561 checkedMap2.replace(1, NOT_A_STRING); 1562 fail(); 1563 } catch (ClassCastException expected) {} 1564 } 1565 1566 public void test_CheckedMap_replace$K$V() { 1567 Map<Integer, Double> map = new HashMap<>(); 1568 Map checkedMap = Collections.checkedMap(map, Integer.class, Double.class); 1569 MapDefaultMethodTester.test_replace$K$V(checkedMap, true /* acceptsNullKey */, 1570 true /* acceptsNullValue */); 1571 1572 // Without generics to check the typeCheck implementation 1573 Map checkedMap2 = Collections.checkedMap(new HashMap<>(), Integer.class, String.class); 1574 checkedMap2.put(1, A_STRING); 1575 1576 try { 1577 checkedMap2.replace(1, 1, NOT_A_STRING); 1578 fail(); 1579 } catch (ClassCastException expected) {} 1580 } 1581 1582 public void test_CheckedMap_computeIfAbsent() { 1583 Map<Integer, Double> map = new HashMap<>(); 1584 Map checkedMap = Collections.checkedMap(map, Integer.class, Double.class); 1585 MapDefaultMethodTester.test_computeIfAbsent(checkedMap, true /* acceptsNullKey */, 1586 true /* acceptsNullValue */); 1587 1588 // Without generics to check the typeCheck implementation 1589 Map checkedMap2 = Collections.checkedMap(new HashMap<>(), Integer.class, String.class); 1590 checkedMap2.put(1, A_STRING); 1591 1592 // When key is present, function should not be invoked 1593 assertSame(A_STRING, checkedMap2.computeIfAbsent(1, k -> { 1594 throw new AssertionFailedError("key present: function should not be invoked"); 1595 })); 1596 1597 // When key is absent, computed value's type should be checked 1598 checkedMap2.clear(); 1599 try { 1600 checkedMap2.computeIfAbsent(1, k -> NOT_A_STRING); 1601 fail(); 1602 } catch (ClassCastException expected) {} 1603 } 1604 1605 public void test_CheckedMap_computeIfPresent() { 1606 Map<Integer, Double> map = new HashMap<>(); 1607 Map checkedMap = Collections.checkedMap(map, Integer.class, Double.class); 1608 MapDefaultMethodTester.test_computeIfPresent(checkedMap, true /* acceptsNullKey */); 1609 1610 // Without generics to check the typeCheck implementation 1611 Map m = new HashMap(); 1612 Map checkedMap2 = Collections.checkedMap(m, Integer.class, String.class); 1613 checkedMap2.put(1, A_STRING); 1614 1615 try { 1616 checkedMap2.computeIfPresent(1, (k, v) -> NOT_A_STRING); 1617 fail(); 1618 } catch (ClassCastException expected) {} 1619 } 1620 1621 public void test_CheckedMap_compute() { 1622 Map<Integer, Double> map = new HashMap<>(); 1623 Map checkedMap = Collections.checkedMap(map, Integer.class, Double.class); 1624 MapDefaultMethodTester.test_compute(checkedMap, true /* acceptsNullKey */); 1625 1626 Map checkedMap2 = Collections.checkedMap(new HashMap(), Integer.class, String.class); 1627 checkedMap2.put(1, A_STRING); 1628 try { 1629 checkedMap2.compute(1, (k, v) -> NOT_A_STRING); 1630 fail(); 1631 } catch (ClassCastException expected) {} 1632 } 1633 1634 public void test_CheckedMap_merge() { 1635 Map<Integer, Double> map = new HashMap<>(); 1636 Map checkedMap = Collections.checkedMap(map, Integer.class, Double.class); 1637 MapDefaultMethodTester.test_merge(checkedMap, true /* acceptsNullKey */); 1638 1639 // Without generics to check the typeCheck implementation 1640 Map checkedMap2 = 1641 Collections.checkedMap(new HashMap<>(), Integer.class, String.class); 1642 checkedMap2.put(1, A_STRING); 1643 1644 try { 1645 checkedMap2.merge(1, A_STRING, (v1, v2) -> NOT_A_STRING); 1646 fail(); 1647 } catch (ClassCastException expected) {} 1648 } 1649 1650 private static<K,V> Map<K, V> createMap(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) { 1651 Map<K, V> result = new HashMap<>(); 1652 result.put(k1, v1); 1653 result.put(k2, v2); 1654 result.put(k3, v3); 1655 result.put(k4, v4); 1656 return result; 1657 } 1658 1659 private static void assertThrowsUoe(Runnable runnable) { 1660 try { 1661 runnable.run(); 1662 fail(); 1663 } catch (UnsupportedOperationException expected) { 1664 } 1665 } 1666 1667 private static void assertThrowsCce(Runnable runnable) { 1668 try { 1669 runnable.run(); 1670 fail(); 1671 } catch (ClassCastException expected) { 1672 } 1673 } 1674 1675 private static<T> List<T> reverseCopyOf(List<T> list) { 1676 List<T> result = new LinkedList<>(); 1677 for (T element : list) { 1678 result.add(0, element); 1679 } 1680 return result; 1681 } 1682 } 1683