1 /* 2 * Written by Doug Lea with assistance from members of JCP JSR-166 3 * Expert Group and released to the public domain, as explained at 4 * http://creativecommons.org/publicdomain/zero/1.0/ 5 */ 6 7 package jsr166; 8 9 import junit.framework.*; 10 import java.util.concurrent.ConcurrentNavigableMap; 11 import java.util.concurrent.ConcurrentSkipListMap; 12 import java.util.*; 13 14 public class ConcurrentSkipListSubMapTest extends JSR166TestCase { 15 16 /** 17 * Returns a new map from Integers 1-5 to Strings "A"-"E". 18 */ 19 private static ConcurrentNavigableMap map5() { 20 ConcurrentSkipListMap map = new ConcurrentSkipListMap(); 21 assertTrue(map.isEmpty()); 22 map.put(zero, "Z"); 23 map.put(one, "A"); 24 map.put(five, "E"); 25 map.put(three, "C"); 26 map.put(two, "B"); 27 map.put(four, "D"); 28 map.put(seven, "F"); 29 assertFalse(map.isEmpty()); 30 assertEquals(7, map.size()); 31 return map.subMap(one, true, seven, false); 32 } 33 34 /** 35 * Returns a new map from Integers -5 to -1 to Strings "A"-"E". 36 */ 37 private static ConcurrentNavigableMap dmap5() { 38 ConcurrentSkipListMap map = new ConcurrentSkipListMap(); 39 assertTrue(map.isEmpty()); 40 map.put(m1, "A"); 41 map.put(m5, "E"); 42 map.put(m3, "C"); 43 map.put(m2, "B"); 44 map.put(m4, "D"); 45 assertFalse(map.isEmpty()); 46 assertEquals(5, map.size()); 47 return map.descendingMap(); 48 } 49 50 private static ConcurrentNavigableMap map0() { 51 ConcurrentSkipListMap map = new ConcurrentSkipListMap(); 52 assertTrue(map.isEmpty()); 53 return map.tailMap(one, true); 54 } 55 56 private static ConcurrentNavigableMap dmap0() { 57 ConcurrentSkipListMap map = new ConcurrentSkipListMap(); 58 assertTrue(map.isEmpty()); 59 return map; 60 } 61 62 /** 63 * clear removes all pairs 64 */ 65 public void testClear() { 66 ConcurrentNavigableMap map = map5(); 67 map.clear(); 68 assertEquals(0, map.size()); 69 } 70 71 /** 72 * Maps with same contents are equal 73 */ 74 public void testEquals() { 75 ConcurrentNavigableMap map1 = map5(); 76 ConcurrentNavigableMap map2 = map5(); 77 assertEquals(map1, map2); 78 assertEquals(map2, map1); 79 map1.clear(); 80 assertFalse(map1.equals(map2)); 81 assertFalse(map2.equals(map1)); 82 } 83 84 /** 85 * containsKey returns true for contained key 86 */ 87 public void testContainsKey() { 88 ConcurrentNavigableMap map = map5(); 89 assertTrue(map.containsKey(one)); 90 assertFalse(map.containsKey(zero)); 91 } 92 93 /** 94 * containsValue returns true for held values 95 */ 96 public void testContainsValue() { 97 ConcurrentNavigableMap map = map5(); 98 assertTrue(map.containsValue("A")); 99 assertFalse(map.containsValue("Z")); 100 } 101 102 /** 103 * get returns the correct element at the given key, 104 * or null if not present 105 */ 106 public void testGet() { 107 ConcurrentNavigableMap map = map5(); 108 assertEquals("A", (String)map.get(one)); 109 ConcurrentNavigableMap empty = map0(); 110 assertNull(empty.get(one)); 111 } 112 113 /** 114 * isEmpty is true of empty map and false for non-empty 115 */ 116 public void testIsEmpty() { 117 ConcurrentNavigableMap empty = map0(); 118 ConcurrentNavigableMap map = map5(); 119 assertTrue(empty.isEmpty()); 120 assertFalse(map.isEmpty()); 121 } 122 123 /** 124 * firstKey returns first key 125 */ 126 public void testFirstKey() { 127 ConcurrentNavigableMap map = map5(); 128 assertEquals(one, map.firstKey()); 129 } 130 131 /** 132 * lastKey returns last key 133 */ 134 public void testLastKey() { 135 ConcurrentNavigableMap map = map5(); 136 assertEquals(five, map.lastKey()); 137 } 138 139 /** 140 * keySet returns a Set containing all the keys 141 */ 142 public void testKeySet() { 143 ConcurrentNavigableMap map = map5(); 144 Set s = map.keySet(); 145 assertEquals(5, s.size()); 146 assertTrue(s.contains(one)); 147 assertTrue(s.contains(two)); 148 assertTrue(s.contains(three)); 149 assertTrue(s.contains(four)); 150 assertTrue(s.contains(five)); 151 } 152 153 /** 154 * keySet is ordered 155 */ 156 public void testKeySetOrder() { 157 ConcurrentNavigableMap map = map5(); 158 Set s = map.keySet(); 159 Iterator i = s.iterator(); 160 Integer last = (Integer)i.next(); 161 assertEquals(last, one); 162 while (i.hasNext()) { 163 Integer k = (Integer)i.next(); 164 assertTrue(last.compareTo(k) < 0); 165 last = k; 166 } 167 } 168 169 /** 170 * values collection contains all values 171 */ 172 public void testValues() { 173 ConcurrentNavigableMap map = map5(); 174 Collection s = map.values(); 175 assertEquals(5, s.size()); 176 assertTrue(s.contains("A")); 177 assertTrue(s.contains("B")); 178 assertTrue(s.contains("C")); 179 assertTrue(s.contains("D")); 180 assertTrue(s.contains("E")); 181 } 182 183 /** 184 * keySet.toArray returns contains all keys 185 */ 186 public void testKeySetToArray() { 187 ConcurrentNavigableMap map = map5(); 188 Set s = map.keySet(); 189 Object[] ar = s.toArray(); 190 assertTrue(s.containsAll(Arrays.asList(ar))); 191 assertEquals(5, ar.length); 192 ar[0] = m10; 193 assertFalse(s.containsAll(Arrays.asList(ar))); 194 } 195 196 /** 197 * descendingkeySet.toArray returns contains all keys 198 */ 199 public void testDescendingKeySetToArray() { 200 ConcurrentNavigableMap map = map5(); 201 Set s = map.descendingKeySet(); 202 Object[] ar = s.toArray(); 203 assertEquals(5, ar.length); 204 assertTrue(s.containsAll(Arrays.asList(ar))); 205 ar[0] = m10; 206 assertFalse(s.containsAll(Arrays.asList(ar))); 207 } 208 209 /** 210 * Values.toArray contains all values 211 */ 212 public void testValuesToArray() { 213 ConcurrentNavigableMap map = map5(); 214 Collection v = map.values(); 215 Object[] ar = v.toArray(); 216 ArrayList s = new ArrayList(Arrays.asList(ar)); 217 assertEquals(5, ar.length); 218 assertTrue(s.contains("A")); 219 assertTrue(s.contains("B")); 220 assertTrue(s.contains("C")); 221 assertTrue(s.contains("D")); 222 assertTrue(s.contains("E")); 223 } 224 225 /** 226 * entrySet contains all pairs 227 */ 228 public void testEntrySet() { 229 ConcurrentNavigableMap map = map5(); 230 Set s = map.entrySet(); 231 assertEquals(5, s.size()); 232 Iterator it = s.iterator(); 233 while (it.hasNext()) { 234 Map.Entry e = (Map.Entry) it.next(); 235 assertTrue( 236 (e.getKey().equals(one) && e.getValue().equals("A")) || 237 (e.getKey().equals(two) && e.getValue().equals("B")) || 238 (e.getKey().equals(three) && e.getValue().equals("C")) || 239 (e.getKey().equals(four) && e.getValue().equals("D")) || 240 (e.getKey().equals(five) && e.getValue().equals("E"))); 241 } 242 } 243 244 /** 245 * putAll adds all key-value pairs from the given map 246 */ 247 public void testPutAll() { 248 ConcurrentNavigableMap empty = map0(); 249 ConcurrentNavigableMap map = map5(); 250 empty.putAll(map); 251 assertEquals(5, empty.size()); 252 assertTrue(empty.containsKey(one)); 253 assertTrue(empty.containsKey(two)); 254 assertTrue(empty.containsKey(three)); 255 assertTrue(empty.containsKey(four)); 256 assertTrue(empty.containsKey(five)); 257 } 258 259 /** 260 * putIfAbsent works when the given key is not present 261 */ 262 public void testPutIfAbsent() { 263 ConcurrentNavigableMap map = map5(); 264 map.putIfAbsent(six, "Z"); 265 assertTrue(map.containsKey(six)); 266 } 267 268 /** 269 * putIfAbsent does not add the pair if the key is already present 270 */ 271 public void testPutIfAbsent2() { 272 ConcurrentNavigableMap map = map5(); 273 assertEquals("A", map.putIfAbsent(one, "Z")); 274 } 275 276 /** 277 * replace fails when the given key is not present 278 */ 279 public void testReplace() { 280 ConcurrentNavigableMap map = map5(); 281 assertNull(map.replace(six, "Z")); 282 assertFalse(map.containsKey(six)); 283 } 284 285 /** 286 * replace succeeds if the key is already present 287 */ 288 public void testReplace2() { 289 ConcurrentNavigableMap map = map5(); 290 assertNotNull(map.replace(one, "Z")); 291 assertEquals("Z", map.get(one)); 292 } 293 294 /** 295 * replace value fails when the given key not mapped to expected value 296 */ 297 public void testReplaceValue() { 298 ConcurrentNavigableMap map = map5(); 299 assertEquals("A", map.get(one)); 300 assertFalse(map.replace(one, "Z", "Z")); 301 assertEquals("A", map.get(one)); 302 } 303 304 /** 305 * replace value succeeds when the given key mapped to expected value 306 */ 307 public void testReplaceValue2() { 308 ConcurrentNavigableMap map = map5(); 309 assertEquals("A", map.get(one)); 310 assertTrue(map.replace(one, "A", "Z")); 311 assertEquals("Z", map.get(one)); 312 } 313 314 /** 315 * remove removes the correct key-value pair from the map 316 */ 317 public void testRemove() { 318 ConcurrentNavigableMap map = map5(); 319 map.remove(five); 320 assertEquals(4, map.size()); 321 assertFalse(map.containsKey(five)); 322 } 323 324 /** 325 * remove(key,value) removes only if pair present 326 */ 327 public void testRemove2() { 328 ConcurrentNavigableMap map = map5(); 329 assertTrue(map.containsKey(five)); 330 assertEquals("E", map.get(five)); 331 map.remove(five, "E"); 332 assertEquals(4, map.size()); 333 assertFalse(map.containsKey(five)); 334 map.remove(four, "A"); 335 assertEquals(4, map.size()); 336 assertTrue(map.containsKey(four)); 337 } 338 339 /** 340 * lowerEntry returns preceding entry. 341 */ 342 public void testLowerEntry() { 343 ConcurrentNavigableMap map = map5(); 344 Map.Entry e1 = map.lowerEntry(three); 345 assertEquals(two, e1.getKey()); 346 347 Map.Entry e2 = map.lowerEntry(six); 348 assertEquals(five, e2.getKey()); 349 350 Map.Entry e3 = map.lowerEntry(one); 351 assertNull(e3); 352 353 Map.Entry e4 = map.lowerEntry(zero); 354 assertNull(e4); 355 } 356 357 /** 358 * higherEntry returns next entry. 359 */ 360 public void testHigherEntry() { 361 ConcurrentNavigableMap map = map5(); 362 Map.Entry e1 = map.higherEntry(three); 363 assertEquals(four, e1.getKey()); 364 365 Map.Entry e2 = map.higherEntry(zero); 366 assertEquals(one, e2.getKey()); 367 368 Map.Entry e3 = map.higherEntry(five); 369 assertNull(e3); 370 371 Map.Entry e4 = map.higherEntry(six); 372 assertNull(e4); 373 } 374 375 /** 376 * floorEntry returns preceding entry. 377 */ 378 public void testFloorEntry() { 379 ConcurrentNavigableMap map = map5(); 380 Map.Entry e1 = map.floorEntry(three); 381 assertEquals(three, e1.getKey()); 382 383 Map.Entry e2 = map.floorEntry(six); 384 assertEquals(five, e2.getKey()); 385 386 Map.Entry e3 = map.floorEntry(one); 387 assertEquals(one, e3.getKey()); 388 389 Map.Entry e4 = map.floorEntry(zero); 390 assertNull(e4); 391 } 392 393 /** 394 * ceilingEntry returns next entry. 395 */ 396 public void testCeilingEntry() { 397 ConcurrentNavigableMap map = map5(); 398 Map.Entry e1 = map.ceilingEntry(three); 399 assertEquals(three, e1.getKey()); 400 401 Map.Entry e2 = map.ceilingEntry(zero); 402 assertEquals(one, e2.getKey()); 403 404 Map.Entry e3 = map.ceilingEntry(five); 405 assertEquals(five, e3.getKey()); 406 407 Map.Entry e4 = map.ceilingEntry(six); 408 assertNull(e4); 409 } 410 411 /** 412 * pollFirstEntry returns entries in order 413 */ 414 public void testPollFirstEntry() { 415 ConcurrentNavigableMap map = map5(); 416 Map.Entry e = map.pollFirstEntry(); 417 assertEquals(one, e.getKey()); 418 assertEquals("A", e.getValue()); 419 e = map.pollFirstEntry(); 420 assertEquals(two, e.getKey()); 421 map.put(one, "A"); 422 e = map.pollFirstEntry(); 423 assertEquals(one, e.getKey()); 424 assertEquals("A", e.getValue()); 425 e = map.pollFirstEntry(); 426 assertEquals(three, e.getKey()); 427 map.remove(four); 428 e = map.pollFirstEntry(); 429 assertEquals(five, e.getKey()); 430 try { 431 e.setValue("A"); 432 shouldThrow(); 433 } catch (UnsupportedOperationException success) {} 434 e = map.pollFirstEntry(); 435 assertNull(e); 436 } 437 438 /** 439 * pollLastEntry returns entries in order 440 */ 441 public void testPollLastEntry() { 442 ConcurrentNavigableMap map = map5(); 443 Map.Entry e = map.pollLastEntry(); 444 assertEquals(five, e.getKey()); 445 assertEquals("E", e.getValue()); 446 e = map.pollLastEntry(); 447 assertEquals(four, e.getKey()); 448 map.put(five, "E"); 449 e = map.pollLastEntry(); 450 assertEquals(five, e.getKey()); 451 assertEquals("E", e.getValue()); 452 e = map.pollLastEntry(); 453 assertEquals(three, e.getKey()); 454 map.remove(two); 455 e = map.pollLastEntry(); 456 assertEquals(one, e.getKey()); 457 try { 458 e.setValue("E"); 459 shouldThrow(); 460 } catch (UnsupportedOperationException success) {} 461 e = map.pollLastEntry(); 462 assertNull(e); 463 } 464 465 /** 466 * size returns the correct values 467 */ 468 public void testSize() { 469 ConcurrentNavigableMap map = map5(); 470 ConcurrentNavigableMap empty = map0(); 471 assertEquals(0, empty.size()); 472 assertEquals(5, map.size()); 473 } 474 475 /** 476 * toString contains toString of elements 477 */ 478 public void testToString() { 479 ConcurrentNavigableMap map = map5(); 480 String s = map.toString(); 481 for (int i = 1; i <= 5; ++i) { 482 assertTrue(s.contains(String.valueOf(i))); 483 } 484 } 485 486 // Exception tests 487 488 /** 489 * get(null) of nonempty map throws NPE 490 */ 491 public void testGet_NullPointerException() { 492 try { 493 ConcurrentNavigableMap c = map5(); 494 c.get(null); 495 shouldThrow(); 496 } catch (NullPointerException success) {} 497 } 498 499 /** 500 * containsKey(null) of nonempty map throws NPE 501 */ 502 public void testContainsKey_NullPointerException() { 503 try { 504 ConcurrentNavigableMap c = map5(); 505 c.containsKey(null); 506 shouldThrow(); 507 } catch (NullPointerException success) {} 508 } 509 510 /** 511 * containsValue(null) throws NPE 512 */ 513 public void testContainsValue_NullPointerException() { 514 try { 515 ConcurrentNavigableMap c = map0(); 516 c.containsValue(null); 517 shouldThrow(); 518 } catch (NullPointerException success) {} 519 } 520 521 /** 522 * put(null,x) throws NPE 523 */ 524 public void testPut1_NullPointerException() { 525 try { 526 ConcurrentNavigableMap c = map5(); 527 c.put(null, "whatever"); 528 shouldThrow(); 529 } catch (NullPointerException success) {} 530 } 531 532 /** 533 * putIfAbsent(null, x) throws NPE 534 */ 535 public void testPutIfAbsent1_NullPointerException() { 536 try { 537 ConcurrentNavigableMap c = map5(); 538 c.putIfAbsent(null, "whatever"); 539 shouldThrow(); 540 } catch (NullPointerException success) {} 541 } 542 543 /** 544 * replace(null, x) throws NPE 545 */ 546 public void testReplace_NullPointerException() { 547 try { 548 ConcurrentNavigableMap c = map5(); 549 c.replace(null, "whatever"); 550 shouldThrow(); 551 } catch (NullPointerException success) {} 552 } 553 554 /** 555 * replace(null, x, y) throws NPE 556 */ 557 public void testReplaceValue_NullPointerException() { 558 try { 559 ConcurrentNavigableMap c = map5(); 560 c.replace(null, one, "whatever"); 561 shouldThrow(); 562 } catch (NullPointerException success) {} 563 } 564 565 /** 566 * remove(null) throws NPE 567 */ 568 public void testRemove1_NullPointerException() { 569 try { 570 ConcurrentNavigableMap c = map5(); 571 c.remove(null); 572 shouldThrow(); 573 } catch (NullPointerException success) {} 574 } 575 576 /** 577 * remove(null, x) throws NPE 578 */ 579 public void testRemove2_NullPointerException() { 580 try { 581 ConcurrentNavigableMap c = map5(); 582 c.remove(null, "whatever"); 583 shouldThrow(); 584 } catch (NullPointerException success) {} 585 } 586 587 /** 588 * A deserialized map equals original 589 */ 590 public void testSerialization() throws Exception { 591 NavigableMap x = map5(); 592 NavigableMap y = serialClone(x); 593 594 assertNotSame(x, y); 595 assertEquals(x.size(), y.size()); 596 assertEquals(x.toString(), y.toString()); 597 assertEquals(x, y); 598 assertEquals(y, x); 599 } 600 601 /** 602 * subMap returns map with keys in requested range 603 */ 604 public void testSubMapContents() { 605 ConcurrentNavigableMap map = map5(); 606 SortedMap sm = map.subMap(two, four); 607 assertEquals(two, sm.firstKey()); 608 assertEquals(three, sm.lastKey()); 609 assertEquals(2, sm.size()); 610 assertFalse(sm.containsKey(one)); 611 assertTrue(sm.containsKey(two)); 612 assertTrue(sm.containsKey(three)); 613 assertFalse(sm.containsKey(four)); 614 assertFalse(sm.containsKey(five)); 615 Iterator i = sm.keySet().iterator(); 616 Object k; 617 k = (Integer)(i.next()); 618 assertEquals(two, k); 619 k = (Integer)(i.next()); 620 assertEquals(three, k); 621 assertFalse(i.hasNext()); 622 Iterator j = sm.keySet().iterator(); 623 j.next(); 624 j.remove(); 625 assertFalse(map.containsKey(two)); 626 assertEquals(4, map.size()); 627 assertEquals(1, sm.size()); 628 assertEquals(three, sm.firstKey()); 629 assertEquals(three, sm.lastKey()); 630 assertEquals("C", sm.remove(three)); 631 assertTrue(sm.isEmpty()); 632 assertEquals(3, map.size()); 633 } 634 635 public void testSubMapContents2() { 636 ConcurrentNavigableMap map = map5(); 637 SortedMap sm = map.subMap(two, three); 638 assertEquals(1, sm.size()); 639 assertEquals(two, sm.firstKey()); 640 assertEquals(two, sm.lastKey()); 641 assertFalse(sm.containsKey(one)); 642 assertTrue(sm.containsKey(two)); 643 assertFalse(sm.containsKey(three)); 644 assertFalse(sm.containsKey(four)); 645 assertFalse(sm.containsKey(five)); 646 Iterator i = sm.keySet().iterator(); 647 Object k; 648 k = (Integer)(i.next()); 649 assertEquals(two, k); 650 assertFalse(i.hasNext()); 651 Iterator j = sm.keySet().iterator(); 652 j.next(); 653 j.remove(); 654 assertFalse(map.containsKey(two)); 655 assertEquals(4, map.size()); 656 assertEquals(0, sm.size()); 657 assertTrue(sm.isEmpty()); 658 assertSame(sm.remove(three), null); 659 assertEquals(4, map.size()); 660 } 661 662 /** 663 * headMap returns map with keys in requested range 664 */ 665 public void testHeadMapContents() { 666 ConcurrentNavigableMap map = map5(); 667 SortedMap sm = map.headMap(four); 668 assertTrue(sm.containsKey(one)); 669 assertTrue(sm.containsKey(two)); 670 assertTrue(sm.containsKey(three)); 671 assertFalse(sm.containsKey(four)); 672 assertFalse(sm.containsKey(five)); 673 Iterator i = sm.keySet().iterator(); 674 Object k; 675 k = (Integer)(i.next()); 676 assertEquals(one, k); 677 k = (Integer)(i.next()); 678 assertEquals(two, k); 679 k = (Integer)(i.next()); 680 assertEquals(three, k); 681 assertFalse(i.hasNext()); 682 sm.clear(); 683 assertTrue(sm.isEmpty()); 684 assertEquals(2, map.size()); 685 assertEquals(four, map.firstKey()); 686 } 687 688 /** 689 * headMap returns map with keys in requested range 690 */ 691 public void testTailMapContents() { 692 ConcurrentNavigableMap map = map5(); 693 SortedMap sm = map.tailMap(two); 694 assertFalse(sm.containsKey(one)); 695 assertTrue(sm.containsKey(two)); 696 assertTrue(sm.containsKey(three)); 697 assertTrue(sm.containsKey(four)); 698 assertTrue(sm.containsKey(five)); 699 Iterator i = sm.keySet().iterator(); 700 Object k; 701 k = (Integer)(i.next()); 702 assertEquals(two, k); 703 k = (Integer)(i.next()); 704 assertEquals(three, k); 705 k = (Integer)(i.next()); 706 assertEquals(four, k); 707 k = (Integer)(i.next()); 708 assertEquals(five, k); 709 assertFalse(i.hasNext()); 710 711 Iterator ei = sm.entrySet().iterator(); 712 Map.Entry e; 713 e = (Map.Entry)(ei.next()); 714 assertEquals(two, e.getKey()); 715 assertEquals("B", e.getValue()); 716 e = (Map.Entry)(ei.next()); 717 assertEquals(three, e.getKey()); 718 assertEquals("C", e.getValue()); 719 e = (Map.Entry)(ei.next()); 720 assertEquals(four, e.getKey()); 721 assertEquals("D", e.getValue()); 722 e = (Map.Entry)(ei.next()); 723 assertEquals(five, e.getKey()); 724 assertEquals("E", e.getValue()); 725 assertFalse(i.hasNext()); 726 727 SortedMap ssm = sm.tailMap(four); 728 assertEquals(four, ssm.firstKey()); 729 assertEquals(five, ssm.lastKey()); 730 assertEquals("D", ssm.remove(four)); 731 assertEquals(1, ssm.size()); 732 assertEquals(3, sm.size()); 733 assertEquals(4, map.size()); 734 } 735 736 /** 737 * clear removes all pairs 738 */ 739 public void testDescendingClear() { 740 ConcurrentNavigableMap map = dmap5(); 741 map.clear(); 742 assertEquals(0, map.size()); 743 } 744 745 /** 746 * Maps with same contents are equal 747 */ 748 public void testDescendingEquals() { 749 ConcurrentNavigableMap map1 = dmap5(); 750 ConcurrentNavigableMap map2 = dmap5(); 751 assertEquals(map1, map2); 752 assertEquals(map2, map1); 753 map1.clear(); 754 assertFalse(map1.equals(map2)); 755 assertFalse(map2.equals(map1)); 756 } 757 758 /** 759 * containsKey returns true for contained key 760 */ 761 public void testDescendingContainsKey() { 762 ConcurrentNavigableMap map = dmap5(); 763 assertTrue(map.containsKey(m1)); 764 assertFalse(map.containsKey(zero)); 765 } 766 767 /** 768 * containsValue returns true for held values 769 */ 770 public void testDescendingContainsValue() { 771 ConcurrentNavigableMap map = dmap5(); 772 assertTrue(map.containsValue("A")); 773 assertFalse(map.containsValue("Z")); 774 } 775 776 /** 777 * get returns the correct element at the given key, 778 * or null if not present 779 */ 780 public void testDescendingGet() { 781 ConcurrentNavigableMap map = dmap5(); 782 assertEquals("A", (String)map.get(m1)); 783 ConcurrentNavigableMap empty = dmap0(); 784 assertNull(empty.get(m1)); 785 } 786 787 /** 788 * isEmpty is true of empty map and false for non-empty 789 */ 790 public void testDescendingIsEmpty() { 791 ConcurrentNavigableMap empty = dmap0(); 792 ConcurrentNavigableMap map = dmap5(); 793 assertTrue(empty.isEmpty()); 794 assertFalse(map.isEmpty()); 795 } 796 797 /** 798 * firstKey returns first key 799 */ 800 public void testDescendingFirstKey() { 801 ConcurrentNavigableMap map = dmap5(); 802 assertEquals(m1, map.firstKey()); 803 } 804 805 /** 806 * lastKey returns last key 807 */ 808 public void testDescendingLastKey() { 809 ConcurrentNavigableMap map = dmap5(); 810 assertEquals(m5, map.lastKey()); 811 } 812 813 /** 814 * keySet returns a Set containing all the keys 815 */ 816 public void testDescendingKeySet() { 817 ConcurrentNavigableMap map = dmap5(); 818 Set s = map.keySet(); 819 assertEquals(5, s.size()); 820 assertTrue(s.contains(m1)); 821 assertTrue(s.contains(m2)); 822 assertTrue(s.contains(m3)); 823 assertTrue(s.contains(m4)); 824 assertTrue(s.contains(m5)); 825 } 826 827 /** 828 * keySet is ordered 829 */ 830 public void testDescendingKeySetOrder() { 831 ConcurrentNavigableMap map = dmap5(); 832 Set s = map.keySet(); 833 Iterator i = s.iterator(); 834 Integer last = (Integer)i.next(); 835 assertEquals(last, m1); 836 while (i.hasNext()) { 837 Integer k = (Integer)i.next(); 838 assertTrue(last.compareTo(k) > 0); 839 last = k; 840 } 841 } 842 843 /** 844 * values collection contains all values 845 */ 846 public void testDescendingValues() { 847 ConcurrentNavigableMap map = dmap5(); 848 Collection s = map.values(); 849 assertEquals(5, s.size()); 850 assertTrue(s.contains("A")); 851 assertTrue(s.contains("B")); 852 assertTrue(s.contains("C")); 853 assertTrue(s.contains("D")); 854 assertTrue(s.contains("E")); 855 } 856 857 /** 858 * keySet.toArray returns contains all keys 859 */ 860 public void testDescendingAscendingKeySetToArray() { 861 ConcurrentNavigableMap map = dmap5(); 862 Set s = map.keySet(); 863 Object[] ar = s.toArray(); 864 assertTrue(s.containsAll(Arrays.asList(ar))); 865 assertEquals(5, ar.length); 866 ar[0] = m10; 867 assertFalse(s.containsAll(Arrays.asList(ar))); 868 } 869 870 /** 871 * descendingkeySet.toArray returns contains all keys 872 */ 873 public void testDescendingDescendingKeySetToArray() { 874 ConcurrentNavigableMap map = dmap5(); 875 Set s = map.descendingKeySet(); 876 Object[] ar = s.toArray(); 877 assertEquals(5, ar.length); 878 assertTrue(s.containsAll(Arrays.asList(ar))); 879 ar[0] = m10; 880 assertFalse(s.containsAll(Arrays.asList(ar))); 881 } 882 883 /** 884 * Values.toArray contains all values 885 */ 886 public void testDescendingValuesToArray() { 887 ConcurrentNavigableMap map = dmap5(); 888 Collection v = map.values(); 889 Object[] ar = v.toArray(); 890 ArrayList s = new ArrayList(Arrays.asList(ar)); 891 assertEquals(5, ar.length); 892 assertTrue(s.contains("A")); 893 assertTrue(s.contains("B")); 894 assertTrue(s.contains("C")); 895 assertTrue(s.contains("D")); 896 assertTrue(s.contains("E")); 897 } 898 899 /** 900 * entrySet contains all pairs 901 */ 902 public void testDescendingEntrySet() { 903 ConcurrentNavigableMap map = dmap5(); 904 Set s = map.entrySet(); 905 assertEquals(5, s.size()); 906 Iterator it = s.iterator(); 907 while (it.hasNext()) { 908 Map.Entry e = (Map.Entry) it.next(); 909 assertTrue( 910 (e.getKey().equals(m1) && e.getValue().equals("A")) || 911 (e.getKey().equals(m2) && e.getValue().equals("B")) || 912 (e.getKey().equals(m3) && e.getValue().equals("C")) || 913 (e.getKey().equals(m4) && e.getValue().equals("D")) || 914 (e.getKey().equals(m5) && e.getValue().equals("E"))); 915 } 916 } 917 918 /** 919 * putAll adds all key-value pairs from the given map 920 */ 921 public void testDescendingPutAll() { 922 ConcurrentNavigableMap empty = dmap0(); 923 ConcurrentNavigableMap map = dmap5(); 924 empty.putAll(map); 925 assertEquals(5, empty.size()); 926 assertTrue(empty.containsKey(m1)); 927 assertTrue(empty.containsKey(m2)); 928 assertTrue(empty.containsKey(m3)); 929 assertTrue(empty.containsKey(m4)); 930 assertTrue(empty.containsKey(m5)); 931 } 932 933 /** 934 * putIfAbsent works when the given key is not present 935 */ 936 public void testDescendingPutIfAbsent() { 937 ConcurrentNavigableMap map = dmap5(); 938 map.putIfAbsent(six, "Z"); 939 assertTrue(map.containsKey(six)); 940 } 941 942 /** 943 * putIfAbsent does not add the pair if the key is already present 944 */ 945 public void testDescendingPutIfAbsent2() { 946 ConcurrentNavigableMap map = dmap5(); 947 assertEquals("A", map.putIfAbsent(m1, "Z")); 948 } 949 950 /** 951 * replace fails when the given key is not present 952 */ 953 public void testDescendingReplace() { 954 ConcurrentNavigableMap map = dmap5(); 955 assertNull(map.replace(six, "Z")); 956 assertFalse(map.containsKey(six)); 957 } 958 959 /** 960 * replace succeeds if the key is already present 961 */ 962 public void testDescendingReplace2() { 963 ConcurrentNavigableMap map = dmap5(); 964 assertNotNull(map.replace(m1, "Z")); 965 assertEquals("Z", map.get(m1)); 966 } 967 968 /** 969 * replace value fails when the given key not mapped to expected value 970 */ 971 public void testDescendingReplaceValue() { 972 ConcurrentNavigableMap map = dmap5(); 973 assertEquals("A", map.get(m1)); 974 assertFalse(map.replace(m1, "Z", "Z")); 975 assertEquals("A", map.get(m1)); 976 } 977 978 /** 979 * replace value succeeds when the given key mapped to expected value 980 */ 981 public void testDescendingReplaceValue2() { 982 ConcurrentNavigableMap map = dmap5(); 983 assertEquals("A", map.get(m1)); 984 assertTrue(map.replace(m1, "A", "Z")); 985 assertEquals("Z", map.get(m1)); 986 } 987 988 /** 989 * remove removes the correct key-value pair from the map 990 */ 991 public void testDescendingRemove() { 992 ConcurrentNavigableMap map = dmap5(); 993 map.remove(m5); 994 assertEquals(4, map.size()); 995 assertFalse(map.containsKey(m5)); 996 } 997 998 /** 999 * remove(key,value) removes only if pair present 1000 */ 1001 public void testDescendingRemove2() { 1002 ConcurrentNavigableMap map = dmap5(); 1003 assertTrue(map.containsKey(m5)); 1004 assertEquals("E", map.get(m5)); 1005 map.remove(m5, "E"); 1006 assertEquals(4, map.size()); 1007 assertFalse(map.containsKey(m5)); 1008 map.remove(m4, "A"); 1009 assertEquals(4, map.size()); 1010 assertTrue(map.containsKey(m4)); 1011 } 1012 1013 /** 1014 * lowerEntry returns preceding entry. 1015 */ 1016 public void testDescendingLowerEntry() { 1017 ConcurrentNavigableMap map = dmap5(); 1018 Map.Entry e1 = map.lowerEntry(m3); 1019 assertEquals(m2, e1.getKey()); 1020 1021 Map.Entry e2 = map.lowerEntry(m6); 1022 assertEquals(m5, e2.getKey()); 1023 1024 Map.Entry e3 = map.lowerEntry(m1); 1025 assertNull(e3); 1026 1027 Map.Entry e4 = map.lowerEntry(zero); 1028 assertNull(e4); 1029 } 1030 1031 /** 1032 * higherEntry returns next entry. 1033 */ 1034 public void testDescendingHigherEntry() { 1035 ConcurrentNavigableMap map = dmap5(); 1036 Map.Entry e1 = map.higherEntry(m3); 1037 assertEquals(m4, e1.getKey()); 1038 1039 Map.Entry e2 = map.higherEntry(zero); 1040 assertEquals(m1, e2.getKey()); 1041 1042 Map.Entry e3 = map.higherEntry(m5); 1043 assertNull(e3); 1044 1045 Map.Entry e4 = map.higherEntry(m6); 1046 assertNull(e4); 1047 } 1048 1049 /** 1050 * floorEntry returns preceding entry. 1051 */ 1052 public void testDescendingFloorEntry() { 1053 ConcurrentNavigableMap map = dmap5(); 1054 Map.Entry e1 = map.floorEntry(m3); 1055 assertEquals(m3, e1.getKey()); 1056 1057 Map.Entry e2 = map.floorEntry(m6); 1058 assertEquals(m5, e2.getKey()); 1059 1060 Map.Entry e3 = map.floorEntry(m1); 1061 assertEquals(m1, e3.getKey()); 1062 1063 Map.Entry e4 = map.floorEntry(zero); 1064 assertNull(e4); 1065 } 1066 1067 /** 1068 * ceilingEntry returns next entry. 1069 */ 1070 public void testDescendingCeilingEntry() { 1071 ConcurrentNavigableMap map = dmap5(); 1072 Map.Entry e1 = map.ceilingEntry(m3); 1073 assertEquals(m3, e1.getKey()); 1074 1075 Map.Entry e2 = map.ceilingEntry(zero); 1076 assertEquals(m1, e2.getKey()); 1077 1078 Map.Entry e3 = map.ceilingEntry(m5); 1079 assertEquals(m5, e3.getKey()); 1080 1081 Map.Entry e4 = map.ceilingEntry(m6); 1082 assertNull(e4); 1083 } 1084 1085 /** 1086 * pollFirstEntry returns entries in order 1087 */ 1088 public void testDescendingPollFirstEntry() { 1089 ConcurrentNavigableMap map = dmap5(); 1090 Map.Entry e = map.pollFirstEntry(); 1091 assertEquals(m1, e.getKey()); 1092 assertEquals("A", e.getValue()); 1093 e = map.pollFirstEntry(); 1094 assertEquals(m2, e.getKey()); 1095 map.put(m1, "A"); 1096 e = map.pollFirstEntry(); 1097 assertEquals(m1, e.getKey()); 1098 assertEquals("A", e.getValue()); 1099 e = map.pollFirstEntry(); 1100 assertEquals(m3, e.getKey()); 1101 map.remove(m4); 1102 e = map.pollFirstEntry(); 1103 assertEquals(m5, e.getKey()); 1104 try { 1105 e.setValue("A"); 1106 shouldThrow(); 1107 } catch (UnsupportedOperationException success) {} 1108 e = map.pollFirstEntry(); 1109 assertNull(e); 1110 } 1111 1112 /** 1113 * pollLastEntry returns entries in order 1114 */ 1115 public void testDescendingPollLastEntry() { 1116 ConcurrentNavigableMap map = dmap5(); 1117 Map.Entry e = map.pollLastEntry(); 1118 assertEquals(m5, e.getKey()); 1119 assertEquals("E", e.getValue()); 1120 e = map.pollLastEntry(); 1121 assertEquals(m4, e.getKey()); 1122 map.put(m5, "E"); 1123 e = map.pollLastEntry(); 1124 assertEquals(m5, e.getKey()); 1125 assertEquals("E", e.getValue()); 1126 e = map.pollLastEntry(); 1127 assertEquals(m3, e.getKey()); 1128 map.remove(m2); 1129 e = map.pollLastEntry(); 1130 assertEquals(m1, e.getKey()); 1131 try { 1132 e.setValue("E"); 1133 shouldThrow(); 1134 } catch (UnsupportedOperationException success) {} 1135 e = map.pollLastEntry(); 1136 assertNull(e); 1137 } 1138 1139 /** 1140 * size returns the correct values 1141 */ 1142 public void testDescendingSize() { 1143 ConcurrentNavigableMap map = dmap5(); 1144 ConcurrentNavigableMap empty = dmap0(); 1145 assertEquals(0, empty.size()); 1146 assertEquals(5, map.size()); 1147 } 1148 1149 /** 1150 * toString contains toString of elements 1151 */ 1152 public void testDescendingToString() { 1153 ConcurrentNavigableMap map = dmap5(); 1154 String s = map.toString(); 1155 for (int i = 1; i <= 5; ++i) { 1156 assertTrue(s.contains(String.valueOf(i))); 1157 } 1158 } 1159 1160 // Exception testDescendings 1161 1162 /** 1163 * get(null) of empty map throws NPE 1164 */ 1165 public void testDescendingGet_NullPointerException() { 1166 try { 1167 ConcurrentNavigableMap c = dmap5(); 1168 c.get(null); 1169 shouldThrow(); 1170 } catch (NullPointerException success) {} 1171 } 1172 1173 /** 1174 * containsKey(null) of empty map throws NPE 1175 */ 1176 public void testDescendingContainsKey_NullPointerException() { 1177 try { 1178 ConcurrentNavigableMap c = dmap5(); 1179 c.containsKey(null); 1180 shouldThrow(); 1181 } catch (NullPointerException success) {} 1182 } 1183 1184 /** 1185 * containsValue(null) throws NPE 1186 */ 1187 public void testDescendingContainsValue_NullPointerException() { 1188 try { 1189 ConcurrentNavigableMap c = dmap0(); 1190 c.containsValue(null); 1191 shouldThrow(); 1192 } catch (NullPointerException success) {} 1193 } 1194 1195 /** 1196 * put(null,x) throws NPE 1197 */ 1198 public void testDescendingPut1_NullPointerException() { 1199 try { 1200 ConcurrentNavigableMap c = dmap5(); 1201 c.put(null, "whatever"); 1202 shouldThrow(); 1203 } catch (NullPointerException success) {} 1204 } 1205 1206 /** 1207 * putIfAbsent(null, x) throws NPE 1208 */ 1209 public void testDescendingPutIfAbsent1_NullPointerException() { 1210 try { 1211 ConcurrentNavigableMap c = dmap5(); 1212 c.putIfAbsent(null, "whatever"); 1213 shouldThrow(); 1214 } catch (NullPointerException success) {} 1215 } 1216 1217 /** 1218 * replace(null, x) throws NPE 1219 */ 1220 public void testDescendingReplace_NullPointerException() { 1221 try { 1222 ConcurrentNavigableMap c = dmap5(); 1223 c.replace(null, "whatever"); 1224 shouldThrow(); 1225 } catch (NullPointerException success) {} 1226 } 1227 1228 /** 1229 * replace(null, x, y) throws NPE 1230 */ 1231 public void testDescendingReplaceValue_NullPointerException() { 1232 try { 1233 ConcurrentNavigableMap c = dmap5(); 1234 c.replace(null, m1, "whatever"); 1235 shouldThrow(); 1236 } catch (NullPointerException success) {} 1237 } 1238 1239 /** 1240 * remove(null) throws NPE 1241 */ 1242 public void testDescendingRemove1_NullPointerException() { 1243 try { 1244 ConcurrentNavigableMap c = dmap5(); 1245 c.remove(null); 1246 shouldThrow(); 1247 } catch (NullPointerException success) {} 1248 } 1249 1250 /** 1251 * remove(null, x) throws NPE 1252 */ 1253 public void testDescendingRemove2_NullPointerException() { 1254 try { 1255 ConcurrentNavigableMap c = dmap5(); 1256 c.remove(null, "whatever"); 1257 shouldThrow(); 1258 } catch (NullPointerException success) {} 1259 } 1260 1261 /** 1262 * A deserialized map equals original 1263 */ 1264 public void testDescendingSerialization() throws Exception { 1265 NavigableMap x = dmap5(); 1266 NavigableMap y = serialClone(x); 1267 1268 assertNotSame(x, y); 1269 assertEquals(x.size(), y.size()); 1270 assertEquals(x.toString(), y.toString()); 1271 assertEquals(x, y); 1272 assertEquals(y, x); 1273 } 1274 1275 /** 1276 * subMap returns map with keys in requested range 1277 */ 1278 public void testDescendingSubMapContents() { 1279 ConcurrentNavigableMap map = dmap5(); 1280 SortedMap sm = map.subMap(m2, m4); 1281 assertEquals(m2, sm.firstKey()); 1282 assertEquals(m3, sm.lastKey()); 1283 assertEquals(2, sm.size()); 1284 assertFalse(sm.containsKey(m1)); 1285 assertTrue(sm.containsKey(m2)); 1286 assertTrue(sm.containsKey(m3)); 1287 assertFalse(sm.containsKey(m4)); 1288 assertFalse(sm.containsKey(m5)); 1289 Iterator i = sm.keySet().iterator(); 1290 Object k; 1291 k = (Integer)(i.next()); 1292 assertEquals(m2, k); 1293 k = (Integer)(i.next()); 1294 assertEquals(m3, k); 1295 assertFalse(i.hasNext()); 1296 Iterator j = sm.keySet().iterator(); 1297 j.next(); 1298 j.remove(); 1299 assertFalse(map.containsKey(m2)); 1300 assertEquals(4, map.size()); 1301 assertEquals(1, sm.size()); 1302 assertEquals(m3, sm.firstKey()); 1303 assertEquals(m3, sm.lastKey()); 1304 assertEquals("C", sm.remove(m3)); 1305 assertTrue(sm.isEmpty()); 1306 assertEquals(3, map.size()); 1307 } 1308 1309 public void testDescendingSubMapContents2() { 1310 ConcurrentNavigableMap map = dmap5(); 1311 SortedMap sm = map.subMap(m2, m3); 1312 assertEquals(1, sm.size()); 1313 assertEquals(m2, sm.firstKey()); 1314 assertEquals(m2, sm.lastKey()); 1315 assertFalse(sm.containsKey(m1)); 1316 assertTrue(sm.containsKey(m2)); 1317 assertFalse(sm.containsKey(m3)); 1318 assertFalse(sm.containsKey(m4)); 1319 assertFalse(sm.containsKey(m5)); 1320 Iterator i = sm.keySet().iterator(); 1321 Object k; 1322 k = (Integer)(i.next()); 1323 assertEquals(m2, k); 1324 assertFalse(i.hasNext()); 1325 Iterator j = sm.keySet().iterator(); 1326 j.next(); 1327 j.remove(); 1328 assertFalse(map.containsKey(m2)); 1329 assertEquals(4, map.size()); 1330 assertEquals(0, sm.size()); 1331 assertTrue(sm.isEmpty()); 1332 assertSame(sm.remove(m3), null); 1333 assertEquals(4, map.size()); 1334 } 1335 1336 /** 1337 * headMap returns map with keys in requested range 1338 */ 1339 public void testDescendingHeadMapContents() { 1340 ConcurrentNavigableMap map = dmap5(); 1341 SortedMap sm = map.headMap(m4); 1342 assertTrue(sm.containsKey(m1)); 1343 assertTrue(sm.containsKey(m2)); 1344 assertTrue(sm.containsKey(m3)); 1345 assertFalse(sm.containsKey(m4)); 1346 assertFalse(sm.containsKey(m5)); 1347 Iterator i = sm.keySet().iterator(); 1348 Object k; 1349 k = (Integer)(i.next()); 1350 assertEquals(m1, k); 1351 k = (Integer)(i.next()); 1352 assertEquals(m2, k); 1353 k = (Integer)(i.next()); 1354 assertEquals(m3, k); 1355 assertFalse(i.hasNext()); 1356 sm.clear(); 1357 assertTrue(sm.isEmpty()); 1358 assertEquals(2, map.size()); 1359 assertEquals(m4, map.firstKey()); 1360 } 1361 1362 /** 1363 * headMap returns map with keys in requested range 1364 */ 1365 public void testDescendingTailMapContents() { 1366 ConcurrentNavigableMap map = dmap5(); 1367 SortedMap sm = map.tailMap(m2); 1368 assertFalse(sm.containsKey(m1)); 1369 assertTrue(sm.containsKey(m2)); 1370 assertTrue(sm.containsKey(m3)); 1371 assertTrue(sm.containsKey(m4)); 1372 assertTrue(sm.containsKey(m5)); 1373 Iterator i = sm.keySet().iterator(); 1374 Object k; 1375 k = (Integer)(i.next()); 1376 assertEquals(m2, k); 1377 k = (Integer)(i.next()); 1378 assertEquals(m3, k); 1379 k = (Integer)(i.next()); 1380 assertEquals(m4, k); 1381 k = (Integer)(i.next()); 1382 assertEquals(m5, k); 1383 assertFalse(i.hasNext()); 1384 1385 Iterator ei = sm.entrySet().iterator(); 1386 Map.Entry e; 1387 e = (Map.Entry)(ei.next()); 1388 assertEquals(m2, e.getKey()); 1389 assertEquals("B", e.getValue()); 1390 e = (Map.Entry)(ei.next()); 1391 assertEquals(m3, e.getKey()); 1392 assertEquals("C", e.getValue()); 1393 e = (Map.Entry)(ei.next()); 1394 assertEquals(m4, e.getKey()); 1395 assertEquals("D", e.getValue()); 1396 e = (Map.Entry)(ei.next()); 1397 assertEquals(m5, e.getKey()); 1398 assertEquals("E", e.getValue()); 1399 assertFalse(i.hasNext()); 1400 1401 SortedMap ssm = sm.tailMap(m4); 1402 assertEquals(m4, ssm.firstKey()); 1403 assertEquals(m5, ssm.lastKey()); 1404 assertEquals("D", ssm.remove(m4)); 1405 assertEquals(1, ssm.size()); 1406 assertEquals(3, sm.size()); 1407 assertEquals(4, map.size()); 1408 } 1409 1410 } 1411