1/* 2 * Copyright (C) 2016 The Android Open Source Project 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.ArrayList; 20import java.util.Arrays; 21import java.util.Collection; 22import java.util.Collections; 23import java.util.ConcurrentModificationException; 24import java.util.HashMap; 25import java.lang.Iterable; 26import java.util.Iterator; 27import java.util.LinkedHashMap; 28import java.util.List; 29import java.util.Locale; 30import java.util.Map; 31import java.util.Objects; 32import java.util.Random; 33import java.util.Set; 34import java.util.Spliterator; 35import java.util.concurrent.atomic.AtomicBoolean; 36import java.util.concurrent.atomic.AtomicInteger; 37 38public class LinkedHashMapTest extends junit.framework.TestCase { 39 40 public void test_getOrDefault() { 41 MapDefaultMethodTester 42 .test_getOrDefault(new LinkedHashMap<>(), true /*acceptsNullKey*/, 43 true /*acceptsNullValue*/, true /*getAcceptsAnyObject*/); 44 45 // Test for access order 46 Map<String, String> m = new LinkedHashMap<String, String>(8, .75f, true); 47 m.put("key", "value"); 48 m.put("key1", "value1"); 49 m.put("key2", "value2"); 50 m.getOrDefault("key1", "value"); 51 Map.Entry<String, String> newest = null; 52 for (Map.Entry<String, String> e : m.entrySet()) { 53 newest = e; 54 } 55 assertEquals("key1", newest.getKey()); 56 assertEquals("value1", newest.getValue()); 57 } 58 59 public void test_forEach() { 60 MapDefaultMethodTester.test_forEach(new LinkedHashMap<>()); 61 } 62 63 public void test_putIfAbsent() { 64 MapDefaultMethodTester.test_putIfAbsent(new LinkedHashMap<>(), true /*acceptsNullKey*/, 65 true /*acceptsNullValue*/); 66 67 // Test for access order 68 Map<String, String> m = new LinkedHashMap<String, String>(8, .75f, true); 69 m.putIfAbsent("key", "value"); 70 m.putIfAbsent("key1", "value1"); 71 m.putIfAbsent("key2", "value2"); 72 Map.Entry<String, String> newest = null; 73 for (Map.Entry<String, String> e : m.entrySet()) { 74 newest = e; 75 } 76 assertEquals("key2", newest.getKey()); 77 assertEquals("value2", newest.getValue()); 78 79 // for existed key 80 m.putIfAbsent("key1", "value1"); 81 for (Map.Entry<String, String> e : m.entrySet()) { 82 newest = e; 83 } 84 assertEquals("key1", newest.getKey()); 85 assertEquals("value1", newest.getValue()); 86 } 87 88 public void test_remove() { 89 MapDefaultMethodTester.test_remove(new LinkedHashMap<>(), true /*acceptsNullKey*/, 90 true /*acceptsNullValue*/); 91 } 92 93 public void test_replace$K$V$V() { 94 MapDefaultMethodTester. 95 test_replace$K$V$V(new LinkedHashMap<>(), true /*acceptsNullKey*/, 96 true /*acceptsNullValue*/); 97 98 // Test for access order 99 Map<String, String> m = new LinkedHashMap<>(8, .75f, true /*accessOrder*/); 100 m.put("key", "value"); 101 m.put("key1", "value1"); 102 m.put("key2", "value2"); 103 m.replace("key1", "value1", "value2"); 104 Map.Entry<String, String> newest = null; 105 for (Map.Entry<String, String> e : m.entrySet()) { 106 newest = e; 107 } 108 assertEquals("key1", newest.getKey()); 109 assertEquals("value2", newest.getValue()); 110 111 // for wrong pair of key and value, last accessed node should 112 // not change 113 m.replace("key2", "value1", "value3"); 114 for (Map.Entry<String, String> e : m.entrySet()) { 115 newest = e; 116 } 117 assertEquals("key1", newest.getKey()); 118 assertEquals("value2", newest.getValue()); 119 } 120 121 public void test_replace$K$V() { 122 MapDefaultMethodTester.test_replace$K$V(new LinkedHashMap<>(), true /*acceptsNullKey*/, 123 true /*acceptsNullValue*/); 124 125 // Test for access order 126 Map<String, String> m = new LinkedHashMap<>(8, .75f, true /*accessOrder*/); 127 m.put("key", "value"); 128 m.put("key1", "value1"); 129 m.put("key2", "value2"); 130 m.replace("key1", "value2"); 131 Map.Entry<String, String> newest = null; 132 for (Map.Entry<String, String> e : m.entrySet()) { 133 newest = e; 134 } 135 assertEquals("key1", newest.getKey()); 136 assertEquals("value2", newest.getValue()); 137 } 138 139 public void test_computeIfAbsent() { 140 MapDefaultMethodTester.test_computeIfAbsent(new LinkedHashMap<>(), true /*acceptsNullKey*/, 141 true /*acceptsNullValue*/); 142 143 // Test for access order 144 Map<String, String> m = new LinkedHashMap<>(8, .75f, true /*accessOrder*/); 145 m.put("key", "value"); 146 m.put("key1", "value1"); 147 m.put("key2", "value2"); 148 m.computeIfAbsent("key1", (k) -> "value3"); 149 Map.Entry<String, String> newest = null; 150 for (Map.Entry<String, String> e : m.entrySet()) { 151 newest = e; 152 } 153 assertEquals("key1", newest.getKey()); 154 assertEquals("value1", newest.getValue()); 155 156 // When value is absent 157 m.computeIfAbsent("key4", (k) -> "value3"); 158 newest = null; 159 for (Map.Entry<String, String> e : m.entrySet()) { 160 newest = e; 161 } 162 assertEquals("key4", newest.getKey()); 163 assertEquals("value3", newest.getValue()); 164 } 165 166 public void test_computeIfPresent() { 167 MapDefaultMethodTester.test_computeIfPresent(new LinkedHashMap<>(), true /*acceptsNullKey*/); 168 169 // Test for access order 170 Map<String, String> m = new LinkedHashMap<>(8, .75f, true /*accessOrder*/); 171 m.put("key", "value"); 172 m.put("key1", "value1"); 173 m.put("key2", "value2"); 174 m.computeIfPresent("key1", (k, v) -> "value3"); 175 Map.Entry<String, String> newest = null; 176 for (Map.Entry<String, String> e : m.entrySet()) { 177 newest = e; 178 } 179 assertEquals("key1", newest.getKey()); 180 assertEquals("value3", newest.getValue()); 181 } 182 183 public void test_compute() { 184 MapDefaultMethodTester.test_compute(new LinkedHashMap<>(), true /*acceptsNullKey*/); 185 186 // Test for access order 187 Map<String, String> m = new LinkedHashMap<>(8, .75f, true /*accessOrder*/); 188 m.put("key", "value"); 189 m.put("key1", "value1"); 190 m.put("key2", "value2"); 191 m.compute("key1", (k, v) -> "value3"); 192 Map.Entry<String, String> newest = null; 193 for (Map.Entry<String, String> e : m.entrySet()) { 194 newest = e; 195 } 196 assertEquals("key1", newest.getKey()); 197 assertEquals("value3", newest.getValue()); 198 199 m.compute("key4", (k, v) -> "value4"); 200 newest = null; 201 for (Map.Entry<String, String> e : m.entrySet()) { 202 newest = e; 203 } 204 assertEquals("key4", newest.getKey()); 205 assertEquals("value4", newest.getValue()); 206 } 207 208 public void test_merge() { 209 MapDefaultMethodTester.test_merge(new LinkedHashMap<>(), true /*acceptsNullKey*/); 210 211 // Test for access order 212 Map<String, String> m = new LinkedHashMap<>(8, .75f, true /*accessOrder*/); 213 m.put("key", "value"); 214 m.put("key1", "value1"); 215 m.put("key2", "value2"); 216 m.merge("key1", "value3", (k, v) -> "value3"); 217 Map.Entry<String, String> newest = null; 218 for (Map.Entry<String, String> e : m.entrySet()) { 219 newest = e; 220 } 221 assertEquals("key1", newest.getKey()); 222 assertEquals("value3", newest.getValue()); 223 } 224 225 // This tests the behaviour is consistent with the RI. 226 // This behaviour is NOT consistent with earlier Android releases up to 227 // and including Android N, see http://b/27929722 228 public void test_removeEldestEntry() { 229 final AtomicBoolean removeEldestEntryReturnValue = new AtomicBoolean(false); 230 final AtomicInteger removeEldestEntryCallCount = new AtomicInteger(0); 231 LinkedHashMap<String, String> m = new LinkedHashMap<String, String>() { 232 @Override 233 protected boolean removeEldestEntry(Entry eldest) { 234 int size = size(); 235 assertEquals(size, iterableSize(entrySet())); 236 assertEquals(size, iterableSize(keySet())); 237 assertEquals(size, iterableSize(values())); 238 assertEquals(size, removeEldestEntryCallCount.get() + 1); 239 removeEldestEntryCallCount.incrementAndGet(); 240 return removeEldestEntryReturnValue.get(); 241 } 242 }; 243 244 assertEquals(0, removeEldestEntryCallCount.get()); 245 m.put("foo", "bar"); 246 assertEquals(1, removeEldestEntryCallCount.get()); 247 m.put("baz", "quux"); 248 assertEquals(2, removeEldestEntryCallCount.get()); 249 250 removeEldestEntryReturnValue.set(true); 251 m.put("foob", "faab"); 252 assertEquals(3, removeEldestEntryCallCount.get()); 253 assertEquals(2, m.size()); 254 assertFalse(m.containsKey("foo")); 255 } 256 257 private static<E> int iterableSize(Iterable<E> iterable) { 258 int result = 0; 259 for (E element : iterable) { 260 result++; 261 } 262 return result; 263 } 264 265 public void test_replaceAll() { 266 LinkedHashMap<String, String> map = new LinkedHashMap<>(); 267 map.put("one", "1"); 268 map.put("two", "2"); 269 map.put("three", "3"); 270 271 map.replaceAll((k, v) -> k + v); 272 assertEquals("one1", map.get("one")); 273 assertEquals("two2", map.get("two")); 274 assertEquals("three3", map.get("three")); 275 assertEquals(3, map.size()); 276 277 try { 278 map.replaceAll((k, v) -> { 279 map.put("foo1", v); 280 return v; 281 }); 282 fail(); 283 } catch(ConcurrentModificationException expected) {} 284 285 try { 286 map.replaceAll(null); 287 fail(); 288 } catch(NullPointerException expected) {} 289 } 290 291 public void test_eldest_empty() { 292 LinkedHashMap<String, String> emptyMap = createMap(); 293 assertNull(eldest(emptyMap)); 294 } 295 296 public void test_eldest_nonempty() { 297 assertEntry("key", "value", eldest(createMap("key", "value"))); 298 assertEntry("A", "1", eldest(createMap("A", "1", "B", "2", "C", "3"))); 299 assertEntry("A", "4", eldest(createMap("A", "1", "B", "2", "C", "3", "A", "4"))); 300 assertEntry("A", "4", eldest(createMap("A", "1", "B", "2", "C", "3", "A", "4", "D", "5"))); 301 } 302 303 public void test_eldest_compatibleWithIterationOrder() { 304 check_eldest_comparibleWithIterationOrder(createMap()); 305 check_eldest_comparibleWithIterationOrder(createMap("key", "value")); 306 check_eldest_comparibleWithIterationOrder(createMap("A", "1", "B", "2")); 307 check_eldest_comparibleWithIterationOrder(createMap("A", "1", "B", "2", "A", "3")); 308 check_eldest_comparibleWithIterationOrder(createMap("A", "1", "A", "2", "A", "3")); 309 310 Random random = new Random(31337); // arbitrary 311 LinkedHashMap<String, String> m = new LinkedHashMap<>(); 312 for (int i = 0; i < 8000; i++) { 313 m.put(String.valueOf(random.nextInt(4000)), String.valueOf(random.nextDouble())); 314 } 315 check_eldest_comparibleWithIterationOrder(m); 316 } 317 318 private void check_eldest_comparibleWithIterationOrder(LinkedHashMap<?, ?> map) { 319 Iterator<? extends Map.Entry<?, ?>> it = map.entrySet().iterator(); 320 if (it.hasNext()) { 321 Map.Entry<?, ?> expected = it.next(); 322 Object expectedKey = expected.getKey(); 323 Object expectedValue = expected.getValue(); 324 assertEntry(expectedKey, expectedValue, eldest(map)); 325 } else { 326 assertNull(eldest(map)); 327 } 328 } 329 330 /** 331 * Check that {@code LinkedHashMap.Entry} compiles and refers to 332 * {@link java.util.Map.Entry}, which is required for source 333 * compatibility with earlier versions of Android. 334 */ 335 public void test_entryCompatibility_compiletime() { 336 assertEquals(Map.Entry.class, LinkedHashMap.Entry.class); 337 } 338 339 /** 340 * Checks that there is no nested class named 'Entry' in LinkedHashMap. 341 * If {@link #test_entryCompatibility_compiletime()} passes but 342 * this test fails, then the test was probably compiled against a 343 * version of LinkedHashMap that does not have a nested Entry class, 344 * but run against a version that does. 345 */ 346 public void test_entryCompatibility_runtime() { 347 String forbiddenClassName = "java.util.LinkedHashMap$Entry"; 348 try { 349 Class.forName(forbiddenClassName); 350 fail("Class " + forbiddenClassName + " should not exist"); 351 } catch (ClassNotFoundException expected) { 352 } 353 } 354 355 public void test_spliterator_keySet() { 356 Map<String, Integer> m = new LinkedHashMap<>(); 357 m.put("a", 1); 358 m.put("b", 2); 359 m.put("c", 3); 360 m.put("d", 4); 361 m.put("e", 5); 362 m.put("f", 6); 363 m.put("g", 7); 364 m.put("h", 8); 365 m.put("i", 9); 366 m.put("j", 10); 367 ArrayList<String> expectedKeys = new ArrayList<>( 368 Arrays.asList("a", "b", "c", "d", "e", "f", "g", "h", "i", "j")); 369 Set<String> keys = m.keySet(); 370 SpliteratorTester.runBasicIterationTests(keys.spliterator(), expectedKeys); 371 SpliteratorTester.runBasicSplitTests(keys, expectedKeys); 372 SpliteratorTester.testSpliteratorNPE(keys.spliterator()); 373 SpliteratorTester.runOrderedTests(keys); 374 SpliteratorTester.runSizedTests(keys.spliterator(), 10); 375 SpliteratorTester.runSubSizedTests(keys.spliterator(), 10); 376 assertEquals( 377 Spliterator.DISTINCT | Spliterator.ORDERED | Spliterator.SIZED 378 | Spliterator.SUBSIZED, 379 keys.spliterator().characteristics()); 380 SpliteratorTester.assertSupportsTrySplit(keys); 381 } 382 383 public void test_spliterator_values() { 384 Map<String, Integer> m = new LinkedHashMap<>(); 385 m.put("a", 1); 386 m.put("b", 2); 387 m.put("c", 3); 388 m.put("d", 4); 389 m.put("e", 5); 390 m.put("f", 6); 391 m.put("g", 7); 392 m.put("h", 8); 393 m.put("i", 9); 394 m.put("j", 10); 395 ArrayList<Integer> expectedValues = new ArrayList<>( 396 Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) 397 ); 398 Collection<Integer> values = m.values(); 399 SpliteratorTester.runBasicIterationTests( 400 values.spliterator(), expectedValues); 401 SpliteratorTester.runBasicSplitTests(values, expectedValues); 402 SpliteratorTester.testSpliteratorNPE(values.spliterator()); 403 SpliteratorTester.runOrderedTests(values); 404 SpliteratorTester.runSizedTests(values, 10); 405 SpliteratorTester.runSubSizedTests(values, 10); 406 assertEquals(Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED, 407 values.spliterator().characteristics()); 408 SpliteratorTester.assertSupportsTrySplit(values); 409 } 410 411 public void test_spliterator_entrySet() { 412 MapDefaultMethodTester 413 .test_entrySet_spliterator_unordered(new LinkedHashMap<>()); 414 415 Map<String, Integer> m = new LinkedHashMap<>(Collections.singletonMap("key", 23)); 416 assertEquals( 417 Spliterator.DISTINCT | Spliterator.ORDERED | Spliterator.SIZED | 418 Spliterator.SUBSIZED, 419 m.entrySet().spliterator().characteristics()); 420 } 421 422 private static Map.Entry<?, ?> eldest(LinkedHashMap<?,?> map) { 423 // Should be the same as: return (map.isEmpty()) ? null : map.entrySet().iterator().next(); 424 return map.eldest(); 425 } 426 427 private static void assertEntry(Object key, Object value, Map.Entry<?, ?> entry) { 428 String msg = String.format(Locale.US, "Expected (%s, %s), got (%s, %s)", 429 key, value, entry.getKey(), entry.getValue()); 430 boolean equal = Objects.equals(key, entry.getKey()) 431 && Objects.equals(value, entry.getValue()); 432 if (!equal) { 433 fail(msg); 434 } 435 } 436 437 private static<T> LinkedHashMap<T, T> createMap(T... keysAndValues) { 438 assertEquals(0, keysAndValues.length % 2); 439 LinkedHashMap<T, T> result = new LinkedHashMap<>(); 440 for (int i = 0; i < keysAndValues.length; i += 2) { 441 result.put(keysAndValues[i], keysAndValues[i+1]); 442 } 443 return result; 444 } 445 446} 447