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 17package libcore.java.util; 18 19import java.util.AbstractMap.SimpleEntry; 20import java.util.ConcurrentModificationException; 21import java.util.HashMap; 22import java.util.Iterator; 23import java.util.Map; 24import java.util.Map.Entry; 25import java.util.NavigableMap; 26import java.util.SortedMap; 27import java.util.TreeMap; 28import junit.framework.TestCase; 29import libcore.util.SerializationTester; 30 31public class TreeMapTest extends TestCase { 32 33 /** 34 * Test that the entrySet() method produces correctly mutable entries. 35 */ 36 public void testEntrySetSetValue() { 37 TreeMap<String, String> map = new TreeMap<String, String>(); 38 map.put("A", "a"); 39 map.put("B", "b"); 40 map.put("C", "c"); 41 42 Iterator<Entry<String, String>> iterator = map.entrySet().iterator(); 43 Entry<String, String> entryA = iterator.next(); 44 assertEquals("a", entryA.setValue("x")); 45 assertEquals("x", entryA.getValue()); 46 assertEquals("x", map.get("A")); 47 Entry<String, String> entryB = iterator.next(); 48 assertEquals("b", entryB.setValue("y")); 49 Entry<String, String> entryC = iterator.next(); 50 assertEquals("c", entryC.setValue("z")); 51 assertEquals("y", entryB.getValue()); 52 assertEquals("y", map.get("B")); 53 assertEquals("z", entryC.getValue()); 54 assertEquals("z", map.get("C")); 55 } 56 57 /** 58 * Test that the entrySet() method of a sub map produces correctly mutable 59 * entries that propagate changes to the original map. 60 */ 61 public void testSubMapEntrySetSetValue() { 62 TreeMap<String, String> map = new TreeMap<String, String>(); 63 map.put("A", "a"); 64 map.put("B", "b"); 65 map.put("C", "c"); 66 map.put("D", "d"); 67 NavigableMap<String, String> subMap = map.subMap("A", true, "C", true); 68 69 Iterator<Entry<String, String>> iterator = subMap.entrySet().iterator(); 70 Entry<String, String> entryA = iterator.next(); 71 assertEquals("a", entryA.setValue("x")); 72 assertEquals("x", entryA.getValue()); 73 assertEquals("x", subMap.get("A")); 74 assertEquals("x", map.get("A")); 75 Entry<String, String> entryB = iterator.next(); 76 assertEquals("b", entryB.setValue("y")); 77 Entry<String, String> entryC = iterator.next(); 78 assertEquals("c", entryC.setValue("z")); 79 assertEquals("y", entryB.getValue()); 80 assertEquals("y", subMap.get("B")); 81 assertEquals("y", map.get("B")); 82 assertEquals("z", entryC.getValue()); 83 assertEquals("z", subMap.get("C")); 84 assertEquals("z", map.get("C")); 85 } 86 87 /** 88 * Test that an Entry given by any method except entrySet() is immutable. 89 */ 90 public void testExceptionsOnSetValue() { 91 TreeMap<String, String> map = new TreeMap<String, String>(); 92 map.put("A", "a"); 93 map.put("B", "b"); 94 map.put("C", "c"); 95 96 assertAllEntryMethodsReturnImmutableEntries(map); 97 } 98 99 /** 100 * Test that an Entry given by any method except entrySet() of a sub map is immutable. 101 */ 102 public void testExceptionsOnSubMapSetValue() { 103 TreeMap<String, String> map = new TreeMap<String, String>(); 104 map.put("A", "a"); 105 map.put("B", "b"); 106 map.put("C", "c"); 107 map.put("D", "d"); 108 109 assertAllEntryMethodsReturnImmutableEntries(map.subMap("A", true, "C", true)); 110 } 111 112 /** 113 * Asserts that each NavigableMap method that returns an Entry (except entrySet()) returns an 114 * immutable one. Assumes that the map contains at least entries with keys "A", "B" and "C". 115 */ 116 private void assertAllEntryMethodsReturnImmutableEntries(NavigableMap<String, String> map) { 117 assertImmutable(map.ceilingEntry("B")); 118 assertImmutable(map.firstEntry()); 119 assertImmutable(map.floorEntry("D")); 120 assertImmutable(map.higherEntry("A")); 121 assertImmutable(map.lastEntry()); 122 assertImmutable(map.lowerEntry("C")); 123 assertImmutable(map.pollFirstEntry()); 124 assertImmutable(map.pollLastEntry()); 125 } 126 127 private void assertImmutable(Entry<String, String> entry) { 128 String initialValue = entry.getValue(); 129 try { 130 entry.setValue("x"); 131 fail(); 132 } catch (UnsupportedOperationException e) { 133 } 134 assertEquals(initialValue, entry.getValue()); 135 } 136 137 public void testConcurrentModificationDetection() { 138 Map<String, String> map = new TreeMap<String, String>(); 139 map.put("A", "a"); 140 map.put("B", "b"); 141 map.put("C", "c"); 142 Iterator<Entry<String,String>> iterator = map.entrySet().iterator(); 143 iterator.next(); 144 iterator.next(); 145 iterator.remove(); 146 map.put("D", "d"); 147 try { 148 iterator.next(); 149 fail(); 150 } catch (ConcurrentModificationException e) { 151 } 152 } 153 154 public void testIteratorRemoves() { 155 Map<String, String> map = new TreeMap<String, String>(); 156 map.put("A", "a"); 157 map.put("B", "b"); 158 map.put("C", "c"); 159 Iterator<Entry<String,String>> iterator = map.entrySet().iterator(); 160 assertEquals("A", iterator.next().getKey()); 161 assertEquals("B", iterator.next().getKey()); 162 iterator.remove(); 163 assertEquals("C", iterator.next().getKey()); 164 iterator.remove(); 165 assertFalse(iterator.hasNext()); 166 } 167 168 /** 169 * Test that entry set contains and removal use the comparator rather than equals. 170 */ 171 public void testEntrySetUsesComparatorOnly() { 172 Map<String,String> map = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER); 173 map.put("ABC", "a"); 174 assertTrue(map.entrySet().contains(new SimpleEntry<String, String>("abc", "a"))); 175 assertTrue(map.entrySet().remove(new SimpleEntry<String, String>("abc", "a"))); 176 assertEquals(0, map.size()); 177 } 178 179 public void testMapConstructorPassingSortedMap() { 180 Map<String,String> source = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER); 181 NavigableMap<String,String> copy = new TreeMap<String, String>(source); 182 assertEquals(null, copy.comparator()); 183 } 184 185 public void testNullsWithNaturalOrder() { 186 HashMap<String, String> copyFrom = new HashMap<String, String>(); 187 copyFrom.put(null, "b"); 188 try { 189 new TreeMap<String, String>(copyFrom); 190 fail(); // the RI doesn't throw if null is the only key 191 } catch (NullPointerException expected) { 192 } 193 194 TreeMap<String,String> map = new TreeMap<String, String>(); 195 try { 196 map.put(null, "b"); 197 fail(); 198 } catch (NullPointerException e) { 199 } 200 201 try { 202 map.descendingMap().put(null, "b"); 203 fail(); 204 } catch (NullPointerException e) { 205 } 206 207 try { 208 map.subMap("a", "z").put(null, "b"); 209 fail(); 210 } catch (NullPointerException e) { 211 } 212 } 213 214 public void testClassCastExceptions() { 215 Map<Object, Object> map = new TreeMap<Object, Object>(); 216 map.put("A", "a"); 217 try { 218 map.get(5); 219 fail(); 220 } catch (ClassCastException e) { 221 } 222 try { 223 map.containsKey(5); 224 fail(); 225 } catch (ClassCastException e) { 226 } 227 try { 228 map.remove(5); 229 fail(); 230 } catch (ClassCastException e) { 231 } 232 } 233 234 public void testClassCastExceptionsOnBounds() { 235 Map<Object, Object> map = new TreeMap<Object, Object>().subMap("a", "z"); 236 try { 237 map.get(5); 238 fail(); 239 } catch (ClassCastException e) { 240 } 241 try { 242 map.containsKey(5); 243 fail(); 244 } catch (ClassCastException e) { 245 } 246 try { 247 map.remove(5); 248 fail(); 249 } catch (ClassCastException e) { 250 } 251 } 252 253 public void testClone() { 254 TreeMap<String, String> map = new TreeMap<String, String>() { 255 @Override public String toString() { 256 return "x:" + super.toString(); 257 } 258 }; 259 260 map.put("A", "a"); 261 map.put("B", "b"); 262 263 @SuppressWarnings("unchecked") 264 TreeMap<String, String> clone = (TreeMap<String, String>) map.clone(); 265 assertEquals(map.getClass(), clone.getClass()); 266 assertEquals("x:{A=a, B=b}", map.toString()); 267 } 268 269 public void testEmptyMapSerialization() { 270 String s = "aced0005737200116a6176612e7574696c2e547265654d61700cc1f63e2d256a" 271 + "e60300014c000a636f6d70617261746f727400164c6a6176612f7574696c2f436" 272 + "f6d70617261746f723b78707077040000000078"; 273 TreeMap<String, String> map = new TreeMap<String, String>(); 274 new SerializationTester<TreeMap<String, String>>(map, s).test(); 275 } 276 277 public void testSerializationWithComparator() { 278 String s = "aced0005737200116a6176612e7574696c2e547265654d61700cc1f63e2d256a" 279 + "e60300014c000a636f6d70617261746f727400164c6a6176612f7574696c2f436" 280 + "f6d70617261746f723b78707372002a6a6176612e6c616e672e537472696e6724" 281 + "43617365496e73656e736974697665436f6d70617261746f7277035c7d5c50e5c" 282 + "e02000078707704000000027400016171007e00057400016271007e000678"; 283 TreeMap<String, String> map = new TreeMap<String, String>( 284 String.CASE_INSENSITIVE_ORDER); 285 map.put("a", "a"); 286 map.put("b", "b"); 287 new SerializationTester<NavigableMap<String, String>>(map, s) { 288 @Override protected void verify(NavigableMap<String, String> deserialized) { 289 assertEquals(0, deserialized.comparator().compare("X", "x")); 290 } 291 }.test(); 292 } 293 294 public void testSubMapSerialization() { 295 String s = "aced0005737200216a6176612e7574696c2e547265654d617024417363656e646" 296 + "96e675375624d61700cab946d1f0fab1c020000787200216a6176612e7574696c2" 297 + "e547265654d6170244e6176696761626c655375624d6170e2d0a70e64210e08020" 298 + "0075a000966726f6d53746172745a000b6869496e636c75736976655a000b6c6f4" 299 + "96e636c75736976655a0005746f456e644c000268697400124c6a6176612f6c616" 300 + "e672f4f626a6563743b4c00026c6f71007e00024c00016d7400134c6a6176612f7" 301 + "574696c2f547265654d61703b7870000001007400016374000161737200116a617" 302 + "6612e7574696c2e547265654d61700cc1f63e2d256ae60300014c000a636f6d706" 303 + "17261746f727400164c6a6176612f7574696c2f436f6d70617261746f723b78707" 304 + "372002a6a6176612e6c616e672e537472696e672443617365496e73656e7369746" 305 + "97665436f6d70617261746f7277035c7d5c50e5ce0200007870770400000004710" 306 + "07e000671007e00067400016271007e000c71007e000571007e000574000164710" 307 + "07e000d78"; 308 TreeMap<String, String> map = new TreeMap<String, String>( 309 String.CASE_INSENSITIVE_ORDER); 310 map.put("a", "a"); 311 map.put("b", "b"); 312 map.put("c", "c"); 313 map.put("d", "d"); 314 SortedMap<String, String> subMap = map.subMap("a", "c"); 315 new SerializationTester<SortedMap<String, String>>(subMap, s) { 316 @Override protected void verify(SortedMap<String, String> deserialized) { 317 try { 318 deserialized.put("e", "e"); 319 fail(); 320 } catch (IllegalArgumentException expected) { 321 } 322 } 323 }.test(); 324 } 325 326 public void testNavigableSubMapSerialization() { 327 String s = "aced0005737200216a6176612e7574696c2e547265654d617024417363656e646" 328 + "96e675375624d61700cab946d1f0fab1c020000787200216a6176612e7574696c2" 329 + "e547265654d6170244e6176696761626c655375624d6170e2d0a70e64210e08020" 330 + "0075a000966726f6d53746172745a000b6869496e636c75736976655a000b6c6f4" 331 + "96e636c75736976655a0005746f456e644c000268697400124c6a6176612f6c616" 332 + "e672f4f626a6563743b4c00026c6f71007e00024c00016d7400134c6a6176612f7" 333 + "574696c2f547265654d61703b7870000100007400016374000161737200116a617" 334 + "6612e7574696c2e547265654d61700cc1f63e2d256ae60300014c000a636f6d706" 335 + "17261746f727400164c6a6176612f7574696c2f436f6d70617261746f723b78707" 336 + "372002a6a6176612e6c616e672e537472696e672443617365496e73656e7369746" 337 + "97665436f6d70617261746f7277035c7d5c50e5ce0200007870770400000004710" 338 + "07e000671007e00067400016271007e000c71007e000571007e000574000164710" 339 + "07e000d78"; 340 TreeMap<String, String> map = new TreeMap<String, String>( 341 String.CASE_INSENSITIVE_ORDER); 342 map.put("a", "a"); 343 map.put("b", "b"); 344 map.put("c", "c"); 345 map.put("d", "d"); 346 SortedMap<String, String> subMap = map.subMap("a", false, "c", true); 347 new SerializationTester<SortedMap<String, String>>(subMap, s) { 348 @Override protected void verify(SortedMap<String, String> deserialized) { 349 try { 350 deserialized.put("e", "e"); 351 fail(); 352 } catch (IllegalArgumentException expected) { 353 } 354 } 355 }.test(); 356 } 357 358 public void testDescendingMapSerialization() { 359 String s = "aced0005737200226a6176612e7574696c2e547265654d61702444657363656e6" 360 + "4696e675375624d61700cab946d1f0f9d0c0200014c001172657665727365436f6" 361 + "d70617261746f727400164c6a6176612f7574696c2f436f6d70617261746f723b7" 362 + "87200216a6176612e7574696c2e547265654d6170244e6176696761626c6553756" 363 + "24d6170e2d0a70e64210e080200075a000966726f6d53746172745a000b6869496" 364 + "e636c75736976655a000b6c6f496e636c75736976655a0005746f456e644c00026" 365 + "8697400124c6a6176612f6c616e672f4f626a6563743b4c00026c6f71007e00034" 366 + "c00016d7400134c6a6176612f7574696c2f547265654d61703b787001010101707" 367 + "0737200116a6176612e7574696c2e547265654d61700cc1f63e2d256ae60300014" 368 + "c000a636f6d70617261746f7271007e000178707372002a6a6176612e6c616e672" 369 + "e537472696e672443617365496e73656e736974697665436f6d70617261746f727" 370 + "7035c7d5c50e5ce02000078707704000000027400016171007e000a74000162710" 371 + "07e000b78737200286a6176612e7574696c2e436f6c6c656374696f6e732452657" 372 + "665727365436f6d70617261746f7232000003fa6c354d510200014c0003636d707" 373 + "1007e0001787071007e0009"; 374 TreeMap<String, String> map = new TreeMap<String, String>( 375 String.CASE_INSENSITIVE_ORDER); 376 map.put("a", "a"); 377 map.put("b", "b"); 378 NavigableMap<String, String> descendingMap = map.descendingMap(); 379 new SerializationTester<NavigableMap<String, String>>(descendingMap, s) { 380 @Override protected void verify(NavigableMap<String, String> deserialized) { 381 assertEquals("b", deserialized.navigableKeySet().first()); 382 } 383 }.test(); 384 } 385 386 public void testJava5SerializationWithComparator() { 387 String s = "aced0005737200116a6176612e7574696c2e547265654d61700cc1f63e2d256a" 388 + "e60300014c000a636f6d70617261746f727400164c6a6176612f7574696c2f436" 389 + "f6d70617261746f723b78707372002a6a6176612e6c616e672e537472696e6724" 390 + "43617365496e73656e736974697665436f6d70617261746f7277035c7d5c50e5c" 391 + "e02000078707704000000027400016171007e00057400016271007e000678"; 392 TreeMap<String, String> map = new TreeMap<String, String>( 393 String.CASE_INSENSITIVE_ORDER); 394 map.put("a", "a"); 395 map.put("b", "b"); 396 new SerializationTester<TreeMap<String, String>>(map, s) { 397 @Override protected void verify(TreeMap<String, String> deserialized) { 398 assertEquals(0, deserialized.comparator().compare("X", "x")); 399 } 400 }.test(); 401 } 402 403 /** 404 * On JDK5, this fails with a NullPointerException after deserialization! 405 */ 406 public void testJava5SubMapSerialization() { 407 String s = "aced0005737200186a6176612e7574696c2e547265654d6170245375624d6170" 408 + "a5818343a213c27f0200055a000966726f6d53746172745a0005746f456e644c0" 409 + "00766726f6d4b65797400124c6a6176612f6c616e672f4f626a6563743b4c0006" 410 + "7468697324307400134c6a6176612f7574696c2f547265654d61703b4c0005746" 411 + "f4b657971007e00017870000074000161737200116a6176612e7574696c2e5472" 412 + "65654d61700cc1f63e2d256ae60300014c000a636f6d70617261746f727400164" 413 + "c6a6176612f7574696c2f436f6d70617261746f723b78707372002a6a6176612e" 414 + "6c616e672e537472696e672443617365496e73656e736974697665436f6d70617" 415 + "261746f7277035c7d5c50e5ce020000787077040000000471007e000471007e00" 416 + "047400016271007e000a7400016371007e000b7400016471007e000c7871007e0" 417 + "00b"; 418 TreeMap<String, String> map = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER); 419 map.put("a", "a"); 420 map.put("b", "b"); 421 map.put("c", "c"); 422 map.put("d", "d"); 423 SortedMap<String, String> subMap = map.subMap("a", "c"); 424 new SerializationTester<SortedMap<String, String>>(subMap, s) { 425 @Override protected void verify(SortedMap<String, String> deserialized) { 426 try { 427 deserialized.put("e", "e"); 428 fail(); 429 } catch (IllegalArgumentException expected) { 430 } 431 } 432 }.test(); 433 } 434} 435