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