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