1 /* 2 * Copyright (C) 2010 Google Inc. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package libcore.java.util; 18 19 import junit.framework.TestCase; 20 21 import java.util.AbstractMap; 22 import java.util.AbstractMap.SimpleEntry; 23 import java.util.Arrays; 24 import java.util.Collection; 25 import java.util.Comparator; 26 import java.util.ConcurrentModificationException; 27 import java.util.HashMap; 28 import java.util.Iterator; 29 import java.util.List; 30 import java.util.Map; 31 import java.util.Map.Entry; 32 import java.util.NavigableMap; 33 import java.util.Set; 34 import java.util.SortedMap; 35 import java.util.Spliterator; 36 import java.util.TreeMap; 37 import libcore.libcore.util.SerializationTester; 38 39 public class TreeMapTest extends TestCase { 40 41 /** 42 * Test that the entrySet() method produces correctly mutable entries. 43 */ 44 public void testEntrySetSetValue() { 45 TreeMap<String, String> map = new TreeMap<String, String>(); 46 map.put("A", "a"); 47 map.put("B", "b"); 48 map.put("C", "c"); 49 50 Iterator<Entry<String, String>> iterator = map.entrySet().iterator(); 51 Entry<String, String> entryA = iterator.next(); 52 assertEquals("a", entryA.setValue("x")); 53 assertEquals("x", entryA.getValue()); 54 assertEquals("x", map.get("A")); 55 Entry<String, String> entryB = iterator.next(); 56 assertEquals("b", entryB.setValue("y")); 57 Entry<String, String> entryC = iterator.next(); 58 assertEquals("c", entryC.setValue("z")); 59 assertEquals("y", entryB.getValue()); 60 assertEquals("y", map.get("B")); 61 assertEquals("z", entryC.getValue()); 62 assertEquals("z", map.get("C")); 63 } 64 65 /** 66 * Test that the entrySet() method of a sub map produces correctly mutable 67 * entries that propagate changes to the original map. 68 */ 69 public void testSubMapEntrySetSetValue() { 70 TreeMap<String, String> map = new TreeMap<String, String>(); 71 map.put("A", "a"); 72 map.put("B", "b"); 73 map.put("C", "c"); 74 map.put("D", "d"); 75 NavigableMap<String, String> subMap = map.subMap("A", true, "C", true); 76 77 Iterator<Entry<String, String>> iterator = subMap.entrySet().iterator(); 78 Entry<String, String> entryA = iterator.next(); 79 assertEquals("a", entryA.setValue("x")); 80 assertEquals("x", entryA.getValue()); 81 assertEquals("x", subMap.get("A")); 82 assertEquals("x", map.get("A")); 83 Entry<String, String> entryB = iterator.next(); 84 assertEquals("b", entryB.setValue("y")); 85 Entry<String, String> entryC = iterator.next(); 86 assertEquals("c", entryC.setValue("z")); 87 assertEquals("y", entryB.getValue()); 88 assertEquals("y", subMap.get("B")); 89 assertEquals("y", map.get("B")); 90 assertEquals("z", entryC.getValue()); 91 assertEquals("z", subMap.get("C")); 92 assertEquals("z", map.get("C")); 93 } 94 95 /** 96 * Test that an Entry given by any method except entrySet() is immutable. 97 */ 98 public void testExceptionsOnSetValue() { 99 TreeMap<String, String> map = new TreeMap<String, String>(); 100 map.put("A", "a"); 101 map.put("B", "b"); 102 map.put("C", "c"); 103 104 assertAllEntryMethodsReturnImmutableEntries(map); 105 } 106 107 /** 108 * Test that an Entry given by any method except entrySet() of a sub map is immutable. 109 */ 110 public void testExceptionsOnSubMapSetValue() { 111 TreeMap<String, String> map = new TreeMap<String, String>(); 112 map.put("A", "a"); 113 map.put("B", "b"); 114 map.put("C", "c"); 115 map.put("D", "d"); 116 117 assertAllEntryMethodsReturnImmutableEntries(map.subMap("A", true, "C", true)); 118 } 119 120 /** 121 * Asserts that each NavigableMap method that returns an Entry (except entrySet()) returns an 122 * immutable one. Assumes that the map contains at least entries with keys "A", "B" and "C". 123 */ 124 private void assertAllEntryMethodsReturnImmutableEntries(NavigableMap<String, String> map) { 125 assertImmutable(map.ceilingEntry("B")); 126 assertImmutable(map.firstEntry()); 127 assertImmutable(map.floorEntry("D")); 128 assertImmutable(map.higherEntry("A")); 129 assertImmutable(map.lastEntry()); 130 assertImmutable(map.lowerEntry("C")); 131 assertImmutable(map.pollFirstEntry()); 132 assertImmutable(map.pollLastEntry()); 133 } 134 135 private void assertImmutable(Entry<String, String> entry) { 136 String initialValue = entry.getValue(); 137 try { 138 entry.setValue("x"); 139 fail(); 140 } catch (UnsupportedOperationException e) { 141 } 142 assertEquals(initialValue, entry.getValue()); 143 } 144 145 public void testConcurrentModificationDetection() { 146 Map<String, String> map = new TreeMap<String, String>(); 147 map.put("A", "a"); 148 map.put("B", "b"); 149 map.put("C", "c"); 150 Iterator<Entry<String,String>> iterator = map.entrySet().iterator(); 151 iterator.next(); 152 iterator.next(); 153 iterator.remove(); 154 map.put("D", "d"); 155 try { 156 iterator.next(); 157 fail(); 158 } catch (ConcurrentModificationException e) { 159 } 160 } 161 162 public void testIteratorRemoves() { 163 Map<String, String> map = new TreeMap<String, String>(); 164 map.put("A", "a"); 165 map.put("B", "b"); 166 map.put("C", "c"); 167 Iterator<Entry<String,String>> iterator = map.entrySet().iterator(); 168 assertEquals("A", iterator.next().getKey()); 169 assertEquals("B", iterator.next().getKey()); 170 iterator.remove(); 171 assertEquals("C", iterator.next().getKey()); 172 iterator.remove(); 173 assertFalse(iterator.hasNext()); 174 } 175 176 /** 177 * Test that entry set contains and removal use the comparator rather than equals. 178 */ 179 public void testEntrySetUsesComparatorOnly() { 180 Map<String,String> map = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER); 181 map.put("ABC", "a"); 182 assertTrue(map.entrySet().contains(new SimpleEntry<String, String>("abc", "a"))); 183 assertTrue(map.entrySet().remove(new SimpleEntry<String, String>("abc", "a"))); 184 assertEquals(0, map.size()); 185 } 186 187 public void testMapConstructorPassingSortedMap() { 188 Map<String,String> source = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER); 189 NavigableMap<String,String> copy = new TreeMap<String, String>(source); 190 assertEquals(null, copy.comparator()); 191 } 192 193 public void testNullsWithNaturalOrder() { 194 HashMap<String, String> copyFrom = new HashMap<String, String>(); 195 copyFrom.put(null, "b"); 196 try { 197 new TreeMap<String, String>(copyFrom); 198 fail(); // the RI doesn't throw if null is the only key 199 } catch (NullPointerException expected) { 200 } 201 202 TreeMap<String,String> map = new TreeMap<String, String>(); 203 try { 204 map.put(null, "b"); 205 fail(); 206 } catch (NullPointerException e) { 207 } 208 209 try { 210 map.descendingMap().put(null, "b"); 211 fail(); 212 } catch (NullPointerException e) { 213 } 214 215 try { 216 map.subMap("a", "z").put(null, "b"); 217 fail(); 218 } catch (NullPointerException e) { 219 } 220 } 221 222 // Tests for naming of TreeMap.TreeMapEntry. Based on similar tests 223 // that exist for LinkedHashMap.LinkedHashMapEntry. 224 /** 225 * Check that {@code TreeMap.Entry} compiles and refers to 226 * {@link java.util.Map.Entry}, which is required for source 227 * compatibility with earlier versions of Android. 228 */ 229 public void test_entryCompatibility_compiletime() { 230 assertEquals(Map.Entry.class, TreeMap.Entry.class); 231 } 232 233 /** 234 * Checks that there is no nested class named 'Entry' in TreeMap. 235 * If {@link #test_entryCompatibility_compiletime()} passes but 236 * this test fails, then the test was probably compiled against a 237 * version of TreeMap that does not have a nested Entry class, 238 * but run against a version that does. 239 */ 240 public void test_entryCompatibility_runtime() { 241 String forbiddenClassName = "java.util.TreeMap$Entry"; 242 try { 243 Class.forName(forbiddenClassName); 244 fail("Class " + forbiddenClassName + " should not exist"); 245 } catch (ClassNotFoundException expected) { 246 } 247 } 248 249 public void testClassCastExceptions() { 250 Map<Object, Object> map = new TreeMap<Object, Object>(); 251 map.put("A", "a"); 252 try { 253 map.get(5); 254 fail(); 255 } catch (ClassCastException e) { 256 } 257 try { 258 map.containsKey(5); 259 fail(); 260 } catch (ClassCastException e) { 261 } 262 try { 263 map.remove(5); 264 fail(); 265 } catch (ClassCastException e) { 266 } 267 } 268 269 public void testClassCastExceptionsOnBounds() { 270 Map<Object, Object> map = new TreeMap<Object, Object>().subMap("a", "z"); 271 try { 272 map.get(5); 273 fail(); 274 } catch (ClassCastException e) { 275 } 276 try { 277 map.containsKey(5); 278 fail(); 279 } catch (ClassCastException e) { 280 } 281 try { 282 map.remove(5); 283 fail(); 284 } catch (ClassCastException e) { 285 } 286 } 287 288 public void testClone() { 289 TreeMap<String, String> map = new TreeMap<String, String>() { 290 @Override public String toString() { 291 return "x:" + super.toString(); 292 } 293 }; 294 295 map.put("A", "a"); 296 map.put("B", "b"); 297 298 @SuppressWarnings("unchecked") 299 TreeMap<String, String> clone = (TreeMap<String, String>) map.clone(); 300 assertEquals(map.getClass(), clone.getClass()); 301 assertEquals("x:{A=a, B=b}", map.toString()); 302 } 303 304 public void testEmptyMapSerialization() { 305 String s = "aced0005737200116a6176612e7574696c2e547265654d61700cc1f63e2d256a" 306 + "e60300014c000a636f6d70617261746f727400164c6a6176612f7574696c2f436" 307 + "f6d70617261746f723b78707077040000000078"; 308 TreeMap<String, String> map = new TreeMap<String, String>(); 309 new SerializationTester<TreeMap<String, String>>(map, s).test(); 310 } 311 312 public void testSerializationWithComparator() { 313 String s = "aced0005737200116a6176612e7574696c2e547265654d61700cc1f63e2d256a" 314 + "e60300014c000a636f6d70617261746f727400164c6a6176612f7574696c2f436" 315 + "f6d70617261746f723b78707372002a6a6176612e6c616e672e537472696e6724" 316 + "43617365496e73656e736974697665436f6d70617261746f7277035c7d5c50e5c" 317 + "e02000078707704000000027400016171007e00057400016271007e000678"; 318 TreeMap<String, String> map = new TreeMap<String, String>( 319 String.CASE_INSENSITIVE_ORDER); 320 map.put("a", "a"); 321 map.put("b", "b"); 322 new SerializationTester<NavigableMap<String, String>>(map, s) { 323 @Override protected void verify(NavigableMap<String, String> deserialized) { 324 assertEquals(0, deserialized.comparator().compare("X", "x")); 325 } 326 }.test(); 327 } 328 329 public void testSubMapSerialization() { 330 // Updated golden value since we have a different serialVersionUID in OpenJDK. 331 String s = "aced0005737200216a6176612e7574696c2e547265654d617024417363656e646" 332 + "96e675375624d61700cab946d1f0fab1c020000787200216a6176612e7574696c2" 333 + "e547265654d6170244e6176696761626c655375624d617026617d4eacdd5933020" 334 + "0075a000966726f6d53746172745a000b6869496e636c75736976655a000b6c6f4" 335 + "96e636c75736976655a0005746f456e644c000268697400124c6a6176612f6c616" 336 + "e672f4f626a6563743b4c00026c6f71007e00024c00016d7400134c6a6176612f7" 337 + "574696c2f547265654d61703b7870000001007400016374000161737200116a617" 338 + "6612e7574696c2e547265654d61700cc1f63e2d256ae60300014c000a636f6d706" 339 + "17261746f727400164c6a6176612f7574696c2f436f6d70617261746f723b78707" 340 + "372002a6a6176612e6c616e672e537472696e672443617365496e73656e7369746" 341 + "97665436f6d70617261746f7277035c7d5c50e5ce0200007870770400000004710" 342 + "07e000671007e00067400016271007e000c71007e000571007e000574000164710" 343 + "07e000d78"; 344 TreeMap<String, String> map = new TreeMap<String, String>( 345 String.CASE_INSENSITIVE_ORDER); 346 map.put("a", "a"); 347 map.put("b", "b"); 348 map.put("c", "c"); 349 map.put("d", "d"); 350 SortedMap<String, String> subMap = map.subMap("a", "c"); 351 new SerializationTester<SortedMap<String, String>>(subMap, s) { 352 @Override protected void verify(SortedMap<String, String> deserialized) { 353 try { 354 deserialized.put("e", "e"); 355 fail(); 356 } catch (IllegalArgumentException expected) { 357 } 358 } 359 }.test(); 360 } 361 362 public void testNavigableSubMapSerialization() { 363 // Updated golden value since we have a different serialVersionUID in OpenJDK. 364 String s = "aced0005737200216a6176612e7574696c2e547265654d617024417363656e646" 365 + "96e675375624d61700cab946d1f0fab1c020000787200216a6176612e7574696c2" 366 + "e547265654d6170244e6176696761626c655375624d617026617d4eacdd5933020" 367 + "0075a000966726f6d53746172745a000b6869496e636c75736976655a000b6c6f4" 368 + "96e636c75736976655a0005746f456e644c000268697400124c6a6176612f6c616" 369 + "e672f4f626a6563743b4c00026c6f71007e00024c00016d7400134c6a6176612f7" 370 + "574696c2f547265654d61703b7870000100007400016374000161737200116a617" 371 + "6612e7574696c2e547265654d61700cc1f63e2d256ae60300014c000a636f6d706" 372 + "17261746f727400164c6a6176612f7574696c2f436f6d70617261746f723b78707" 373 + "372002a6a6176612e6c616e672e537472696e672443617365496e73656e7369746" 374 + "97665436f6d70617261746f7277035c7d5c50e5ce0200007870770400000004710" 375 + "07e000671007e00067400016271007e000c71007e000571007e000574000164710" 376 + "07e000d78"; 377 TreeMap<String, String> map = new TreeMap<String, String>( 378 String.CASE_INSENSITIVE_ORDER); 379 map.put("a", "a"); 380 map.put("b", "b"); 381 map.put("c", "c"); 382 map.put("d", "d"); 383 SortedMap<String, String> subMap = map.subMap("a", false, "c", true); 384 new SerializationTester<SortedMap<String, String>>(subMap, s) { 385 @Override protected void verify(SortedMap<String, String> deserialized) { 386 try { 387 deserialized.put("e", "e"); 388 fail(); 389 } catch (IllegalArgumentException expected) { 390 } 391 } 392 }.test(); 393 } 394 395 public void testDescendingMapSerialization() { 396 // Updated golden value since we have a different serialVersionUID in OpenJDK. 397 String s = "aced0005737200226a6176612e7574696c2e547265654d61702444657363656e6" 398 + "4696e675375624d61700cab946d1f0f9d0c0200014c001172657665727365436f6" 399 + "d70617261746f727400164c6a6176612f7574696c2f436f6d70617261746f723b7" 400 + "87200216a6176612e7574696c2e547265654d6170244e6176696761626c6553756" 401 + "24d617026617d4eacdd59330200075a000966726f6d53746172745a000b6869496" 402 + "e636c75736976655a000b6c6f496e636c75736976655a0005746f456e644c00026" 403 + "8697400124c6a6176612f6c616e672f4f626a6563743b4c00026c6f71007e00034" 404 + "c00016d7400134c6a6176612f7574696c2f547265654d61703b787001010101707" 405 + "0737200116a6176612e7574696c2e547265654d61700cc1f63e2d256ae60300014" 406 + "c000a636f6d70617261746f7271007e000178707372002a6a6176612e6c616e672" 407 + "e537472696e672443617365496e73656e736974697665436f6d70617261746f727" 408 + "7035c7d5c50e5ce02000078707704000000027400016171007e000a74000162710" 409 + "07e000b78737200286a6176612e7574696c2e436f6c6c656374696f6e732452657" 410 + "665727365436f6d70617261746f7232000003fa6c354d510200014c0003636d707" 411 + "1007e0001787071007e0009"; 412 TreeMap<String, String> map = new TreeMap<String, String>( 413 String.CASE_INSENSITIVE_ORDER); 414 map.put("a", "a"); 415 map.put("b", "b"); 416 NavigableMap<String, String> descendingMap = map.descendingMap(); 417 new SerializationTester<NavigableMap<String, String>>(descendingMap, s) { 418 @Override protected void verify(NavigableMap<String, String> deserialized) { 419 assertEquals("b", deserialized.navigableKeySet().first()); 420 } 421 }.test(); 422 } 423 424 public void testJava5SerializationWithComparator() { 425 String s = "aced0005737200116a6176612e7574696c2e547265654d61700cc1f63e2d256a" 426 + "e60300014c000a636f6d70617261746f727400164c6a6176612f7574696c2f436" 427 + "f6d70617261746f723b78707372002a6a6176612e6c616e672e537472696e6724" 428 + "43617365496e73656e736974697665436f6d70617261746f7277035c7d5c50e5c" 429 + "e02000078707704000000027400016171007e00057400016271007e000678"; 430 TreeMap<String, String> map = new TreeMap<String, String>( 431 String.CASE_INSENSITIVE_ORDER); 432 map.put("a", "a"); 433 map.put("b", "b"); 434 new SerializationTester<TreeMap<String, String>>(map, s) { 435 @Override protected void verify(TreeMap<String, String> deserialized) { 436 assertEquals(0, deserialized.comparator().compare("X", "x")); 437 } 438 }.test(); 439 } 440 441 /** 442 * On JDK5, this fails with a NullPointerException after deserialization! 443 */ 444 public void testJava5SubMapSerialization() { 445 String s = "aced0005737200186a6176612e7574696c2e547265654d6170245375624d6170" 446 + "a5818343a213c27f0200055a000966726f6d53746172745a0005746f456e644c0" 447 + "00766726f6d4b65797400124c6a6176612f6c616e672f4f626a6563743b4c0006" 448 + "7468697324307400134c6a6176612f7574696c2f547265654d61703b4c0005746" 449 + "f4b657971007e00017870000074000161737200116a6176612e7574696c2e5472" 450 + "65654d61700cc1f63e2d256ae60300014c000a636f6d70617261746f727400164" 451 + "c6a6176612f7574696c2f436f6d70617261746f723b78707372002a6a6176612e" 452 + "6c616e672e537472696e672443617365496e73656e736974697665436f6d70617" 453 + "261746f7277035c7d5c50e5ce020000787077040000000471007e000471007e00" 454 + "047400016271007e000a7400016371007e000b7400016471007e000c7871007e0" 455 + "00b"; 456 TreeMap<String, String> map = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER); 457 map.put("a", "a"); 458 map.put("b", "b"); 459 map.put("c", "c"); 460 map.put("d", "d"); 461 SortedMap<String, String> subMap = map.subMap("a", "c"); 462 new SerializationTester<SortedMap<String, String>>(subMap, s) { 463 @Override protected void verify(SortedMap<String, String> deserialized) { 464 try { 465 deserialized.put("e", "e"); 466 fail(); 467 } catch (IllegalArgumentException expected) { 468 } 469 } 470 }.test(); 471 } 472 473 /** 474 * Taking a headMap or tailMap (exclusive or inclusive of the bound) of 475 * a TreeMap with unbounded range never throws IllegalArgumentException. 476 */ 477 public void testBounds_fromUnbounded() { 478 applyBound('[', new TreeMap<>()); 479 applyBound(']', new TreeMap<>()); 480 applyBound('(', new TreeMap<>()); 481 applyBound(')', new TreeMap<>()); 482 } 483 484 /** 485 * Taking an exclusive-end submap of a parent map with an exclusive 486 * range is allowed only if the bounds go in the same direction 487 * (if parent and child are either both headMaps or both tailMaps, 488 * but not otherwise). 489 */ 490 public void testBounds_openSubrangeOfOpenRange() { 491 // NavigableMap.{tail,head}Map(T key, boolean inclusive)'s 492 // documentation says that it throws IAE "if this map itself has a 493 // restricted range, and key lies outside the bounds of the range". 494 // Since that documentation doesn't mention the value of inclusive, 495 // one could argue that the following two cases should throw IAE, 496 // but the actual implementation in TreeMap does not. This test 497 // asserts the actual behavior. 498 assertTrue(isWithinBounds(')', ')')); 499 assertTrue(isWithinBounds('(', '(')); 500 501 // The following two tests check that TreeMap's behavior matches 502 // that from earlier versions of Android (from before Android N). 503 // AOSP commit b4105e7f1e3ab24131976f68be4554e694a0e1d4 ensured 504 // that Android N was consistent with earlier versions' behavior. 505 // Specifically, on Android, 506 // new TreeMap<>().headMap(0, false).tailMap(0, false) 507 // and new TreeMap<>().tailMap(0, false).headMap(0, false) 508 // are both not allowed. 509 assertFalse(isWithinBounds(')', '(')); 510 assertFalse(isWithinBounds('(', ')')); 511 } 512 513 /** 514 * Taking a exclusive-end submap of an inclusive-end parent map is not 515 * allowed regardless of the direction of the constraints (headMap 516 * vs. tailMap) because the inclusive bound of the submap is not 517 * contained in the exclusive range of the parent map. 518 */ 519 public void testBounds_closedSubrangeOfOpenRange() { 520 assertFalse(isWithinBounds(']', '(')); 521 assertFalse(isWithinBounds('[', ')')); 522 assertFalse(isWithinBounds(']', ')')); 523 assertFalse(isWithinBounds('[', '(')); 524 } 525 526 /** 527 * Taking an inclusive-end submap of an inclusive-end parent map 528 * is allowed regardless of the direction of the constraints (headMap 529 * vs. tailMap) because the inclusive bound of the submap is 530 * contained in the inclusive range of the parent map. 531 */ 532 public void testBounds_closedSubrangeOfClosedRange() { 533 assertTrue(isWithinBounds(']', '[')); 534 assertTrue(isWithinBounds('[', ']')); 535 assertTrue(isWithinBounds(']', ']')); 536 assertTrue(isWithinBounds('[', '[')); 537 } 538 539 /** 540 * Taking an exclusive-end submap of an inclusive-end parent map 541 * is allowed regardless of the direction of the constraints (headMap 542 * vs. tailMap) because the exclusive bound of the submap is 543 * contained in the inclusive range of the parent map. 544 * 545 * Note that 546 * (a) isWithinBounds(')', '[') == true, while 547 * (b) isWithinBounds('[', ')') == false 548 * means that 549 * {@code new TreeMap<>().tailMap(0, true).headMap(0, false)} 550 * is allowed but 551 * {@code new TreeMap<>().headMap(0, false).tailMap(0, true)} 552 * is not. 553 */ 554 public void testBounds_openSubrangeOfClosedRange() { 555 assertTrue(isWithinBounds(')', '[')); 556 assertTrue(isWithinBounds('(', ']')); 557 assertTrue(isWithinBounds('(', '[')); 558 assertTrue(isWithinBounds(')', ']')); 559 560 // This is allowed: 561 new TreeMap<>().tailMap(0, true).headMap(0, false); 562 563 // This is not: 564 try { 565 new TreeMap<>().headMap(0, false).tailMap(0, true); 566 fail("Should have thrown"); 567 } catch (IllegalArgumentException expected) { 568 // expected 569 } 570 } 571 572 /** 573 * Asserts whether constructing a (head or tail) submap with (inclusive or 574 * exclusive) bound 0 is allowed on a (head or tail) map with (inclusive or 575 * exclusive) bound 0. For example, 576 * 577 * {@code isWithinBounds(')', ']'} is true because the boundary of "0)" 578 * (an infinitesimally small negative value) lies within the range "0]", 579 * but {@code isWithinBounds(']', ')'} is false because 0 does not lie 580 * within the range "0)". 581 */ 582 private static boolean isWithinBounds(char submapBound, char mapBound) { 583 NavigableMap<Integer, Void> m = applyBound(mapBound, new TreeMap<>()); 584 IllegalArgumentException thrownException = null; 585 try { 586 applyBound(submapBound, m); 587 } catch (IllegalArgumentException e) { 588 thrownException = e; 589 } 590 return (thrownException == null); 591 } 592 593 /** 594 * Constructs a submap of the specified map, constrained by the given bound. 595 */ 596 private static<V> NavigableMap<Integer, V> applyBound(char bound, NavigableMap<Integer, V> m) { 597 Integer boundValue = 0; // arbitrary 598 if (isLowerBound(bound)) { 599 return m.tailMap(boundValue, isBoundInclusive(bound)); 600 } else { 601 return m.headMap(boundValue, isBoundInclusive(bound)); 602 } 603 } 604 605 private static boolean isBoundInclusive(char bound) { 606 return bound == '[' || bound == ']'; 607 } 608 609 /** 610 * Returns whether the specified bound corresponds to a tailMap, i.e. a Map whose 611 * range of values has an (exclusive or inclusive) lower bound. 612 */ 613 private static boolean isLowerBound(char bound) { 614 return bound == '[' || bound == '('; 615 } 616 617 public void test_spliterator_keySet() { 618 TreeMap<String, String> treeMap = new TreeMap<>(); 619 // Elements are added out of order to ensure ordering is still preserved. 620 treeMap.put("a", "1"); 621 treeMap.put("i", "9"); 622 treeMap.put("j", "10"); 623 treeMap.put("k", "11"); 624 treeMap.put("l", "12"); 625 treeMap.put("b", "2"); 626 treeMap.put("c", "3"); 627 treeMap.put("d", "4"); 628 treeMap.put("e", "5"); 629 treeMap.put("n", "14"); 630 treeMap.put("o", "15"); 631 treeMap.put("p", "16"); 632 treeMap.put("f", "6"); 633 treeMap.put("g", "7"); 634 treeMap.put("h", "8"); 635 treeMap.put("m", "13"); 636 637 Set<String> keys = treeMap.keySet(); 638 List<String> expectedKeys = Arrays.asList( 639 "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k" , "l", "m", "n", "o", "p"); 640 641 SpliteratorTester.runBasicIterationTests_unordered(keys.spliterator(), expectedKeys, 642 String::compareTo); 643 SpliteratorTester.runBasicSplitTests(keys, expectedKeys); 644 SpliteratorTester.testSpliteratorNPE(keys.spliterator()); 645 assertEquals( 646 Spliterator.DISTINCT | Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SORTED, 647 keys.spliterator().characteristics()); 648 SpliteratorTester.runSortedTests(keys); 649 SpliteratorTester.runOrderedTests(keys); 650 SpliteratorTester.assertSupportsTrySplit(keys); 651 } 652 653 public void test_spliterator_values() { 654 TreeMap<String, String> treeMap = new TreeMap<>(); 655 // Elements are added out of order to ensure ordering is still preserved. 656 treeMap.put("a", "1"); 657 treeMap.put("i", "9"); 658 treeMap.put("j", "10"); 659 treeMap.put("k", "11"); 660 treeMap.put("l", "12"); 661 treeMap.put("b", "2"); 662 treeMap.put("c", "3"); 663 treeMap.put("d", "4"); 664 treeMap.put("e", "5"); 665 treeMap.put("n", "14"); 666 treeMap.put("o", "15"); 667 treeMap.put("p", "16"); 668 treeMap.put("f", "6"); 669 treeMap.put("g", "7"); 670 treeMap.put("h", "8"); 671 treeMap.put("m", "13"); 672 673 Collection<String> values = treeMap.values(); 674 List<String> expectedValues = Arrays.asList("1", "2", "3", "4", "5", "6", "7", "8", "9", 675 "10", "11", "12", "13", "14", "15", "16"); 676 677 SpliteratorTester.runBasicIterationTests_unordered( 678 values.spliterator(), expectedValues, String::compareTo); 679 SpliteratorTester.runBasicSplitTests(values, expectedValues); 680 SpliteratorTester.testSpliteratorNPE(values.spliterator()); 681 682 assertEquals(Spliterator.ORDERED | Spliterator.SIZED, 683 values.spliterator().characteristics()); 684 SpliteratorTester.runSizedTests(values, 16); 685 SpliteratorTester.runOrderedTests(values); 686 SpliteratorTester.assertSupportsTrySplit(values); 687 } 688 689 public void test_spliterator_entrySet() { 690 TreeMap<String, String> treeMap = new TreeMap<>(); 691 // Elements are added out of order to ensure ordering is still preserved. 692 treeMap.put("a", "1"); 693 treeMap.put("i", "9"); 694 treeMap.put("j", "10"); 695 treeMap.put("k", "11"); 696 treeMap.put("l", "12"); 697 treeMap.put("b", "2"); 698 treeMap.put("c", "3"); 699 treeMap.put("d", "4"); 700 treeMap.put("e", "5"); 701 treeMap.put("n", "14"); 702 treeMap.put("o", "15"); 703 treeMap.put("p", "16"); 704 treeMap.put("f", "6"); 705 treeMap.put("g", "7"); 706 treeMap.put("h", "8"); 707 treeMap.put("m", "13"); 708 709 Set<Map.Entry<String, String>> entries = treeMap.entrySet(); 710 List<Map.Entry<String, String>> expectedValues = Arrays.asList( 711 entry("a", "1"), 712 entry("b", "2"), 713 entry("c", "3"), 714 entry("d", "4"), 715 entry("e", "5"), 716 entry("f", "6"), 717 entry("g", "7"), 718 entry("h", "8"), 719 entry("i", "9"), 720 entry("j", "10"), 721 entry("k", "11"), 722 entry("l", "12"), 723 entry("m", "13"), 724 entry("n", "14"), 725 entry("o", "15"), 726 entry("p", "16") 727 ); 728 729 Comparator<Map.Entry<String, String>> comparator = 730 (a, b) -> (a.getKey().compareTo(b.getKey())); 731 732 SpliteratorTester.runBasicIterationTests_unordered(entries.spliterator(), expectedValues, 733 (a, b) -> (a.getKey().compareTo(b.getKey()))); 734 SpliteratorTester.runBasicSplitTests(entries, expectedValues, comparator); 735 SpliteratorTester.testSpliteratorNPE(entries.spliterator()); 736 737 assertEquals( 738 Spliterator.DISTINCT | Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SORTED, 739 entries.spliterator().characteristics()); 740 SpliteratorTester.runSortedTests(entries, (a, b) -> (a.getKey().compareTo(b.getKey()))); 741 SpliteratorTester.runOrderedTests(entries); 742 SpliteratorTester.assertSupportsTrySplit(entries); 743 } 744 745 private static<K, V> Map.Entry<K, V> entry(K key, V value) { 746 return new AbstractMap.SimpleEntry<>(key, value); 747 } 748 749 public void test_replaceAll() throws Exception { 750 TreeMap<String, String> map = new TreeMap<>(); 751 map.put("one", "1"); 752 map.put("two", "2"); 753 map.put("three", "3"); 754 755 TreeMap<String, String> output = new TreeMap<>(); 756 map.replaceAll((k, v) -> k + v); 757 assertEquals("one1", map.get("one")); 758 assertEquals("two2", map.get("two")); 759 assertEquals("three3", map.get("three")); 760 761 try { 762 map.replaceAll(null); 763 fail(); 764 } catch(NullPointerException expected) {} 765 766 try { 767 map.replaceAll((k, v) -> { 768 map.put("foo", v); 769 return v; 770 }); 771 fail(); 772 } catch(ConcurrentModificationException expected) {} 773 } 774 775 public void test_replace$K$V$V() { 776 MapDefaultMethodTester.test_replace$K$V$V(new TreeMap<>(), false /* acceptsNullKey */, 777 true /* acceptsNullValue */); 778 } 779 780 public void test_replace$K$V() { 781 MapDefaultMethodTester.test_replace$K$V(new TreeMap<>(), false /* acceptsNullKey */, 782 true /* acceptsNullValue */); 783 } 784 } 785