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