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