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 org.mockito.InOrder; 20 21import java.util.ArrayList; 22import java.util.Arrays; 23import java.util.Collection; 24import java.util.Collections; 25import java.util.ConcurrentModificationException; 26import java.util.HashMap; 27import java.util.LinkedHashMap; 28import java.util.Map; 29import java.util.Set; 30import java.util.Spliterator; 31import java.util.TreeMap; 32 33public class HashMapTest extends junit.framework.TestCase { 34 35 public void test_getOrDefault() { 36 MapDefaultMethodTester.test_getOrDefault(new HashMap<>(), true /*acceptsNullKey*/, 37 true /*acceptsNullValue*/, true /*getAcceptsAnyObject*/); 38 } 39 40 public void test_forEach() { 41 MapDefaultMethodTester.test_forEach(new HashMap<>()); 42 } 43 44 public void test_putIfAbsent() { 45 MapDefaultMethodTester.test_putIfAbsent(new HashMap<>(), true /*acceptsNullKey*/, 46 true /*acceptsNullValue*/); 47 } 48 49 public void test_remove() { 50 MapDefaultMethodTester 51 .test_remove(new HashMap<>(), true /*acceptsNullKey*/, true /*acceptsNullValue*/); 52 } 53 54 public void test_replace$K$V$V() { 55 MapDefaultMethodTester 56 .test_replace$K$V$V(new HashMap<>(), true /*acceptsNullKey*/, 57 true /*acceptsNullValue*/); 58 } 59 60 public void test_replace$K$V() { 61 MapDefaultMethodTester.test_replace$K$V(new HashMap<>(), true /*acceptsNullKey*/, 62 true /*acceptsNullValue*/); 63 } 64 65 public void test_computeIfAbsent() { 66 MapDefaultMethodTester.test_computeIfAbsent(new HashMap<>(), true /*acceptsNullKey*/, 67 true /*acceptsNullValue*/); 68 } 69 70 public void test_computeIfPresent() { 71 MapDefaultMethodTester.test_computeIfPresent(new HashMap<>(), true /*acceptsNullKey*/); 72 } 73 74 public void test_compute() { 75 MapDefaultMethodTester 76 .test_compute(new HashMap<>(), true /*acceptsNullKey*/); 77 } 78 79 public void test_merge() { 80 MapDefaultMethodTester 81 .test_merge(new HashMap<>(), true /*acceptsNullKey*/); 82 } 83 84 public void test_spliterator_keySet() { 85 Map<String, Integer> m = new HashMap<>(); 86 m.put("a", 1); 87 m.put("b", 2); 88 m.put("c", 3); 89 m.put("d", 4); 90 m.put("e", 5); 91 m.put("f", 6); 92 m.put("g", 7); 93 m.put("h", 8); 94 m.put("i", 9); 95 m.put("j", 10); 96 ArrayList<String> expectedKeys = new ArrayList<>( 97 Arrays.asList("a", "b", "c", "d", "e", "f", "g", "h", "i", "j")); 98 Set<String> keys = m.keySet(); 99 SpliteratorTester.runBasicIterationTests(keys.spliterator(), expectedKeys); 100 SpliteratorTester.runBasicSplitTests(keys, expectedKeys); 101 SpliteratorTester.testSpliteratorNPE(keys.spliterator()); 102 SpliteratorTester.runSizedTests(keys.spliterator(), 10); 103 assertEquals(Spliterator.DISTINCT | Spliterator.SIZED, 104 keys.spliterator().characteristics()); 105 SpliteratorTester.assertSupportsTrySplit(keys); 106 } 107 108 public void test_spliterator_values() { 109 Map<String, Integer> m = new HashMap<>(); 110 m.put("a", 1); 111 m.put("b", 2); 112 m.put("c", 3); 113 m.put("d", 4); 114 m.put("e", 5); 115 m.put("f", 6); 116 m.put("g", 7); 117 m.put("h", 8); 118 m.put("i", 9); 119 m.put("j", 10); 120 ArrayList<Integer> expectedValues = new ArrayList<>( 121 Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) 122 ); 123 Collection<Integer> values = m.values(); 124 SpliteratorTester.runBasicIterationTests(values.spliterator(), expectedValues); 125 SpliteratorTester.runBasicSplitTests(values, expectedValues); 126 SpliteratorTester.testSpliteratorNPE(values.spliterator()); 127 SpliteratorTester.runSizedTests(values, 10); 128 assertEquals(Spliterator.SIZED, values.spliterator().characteristics()); 129 SpliteratorTester.assertSupportsTrySplit(values); 130 } 131 132 public void test_spliterator_entrySet() { 133 MapDefaultMethodTester.test_entrySet_spliterator_unordered(new HashMap<>()); 134 135 Map<String, Integer> m = new HashMap<>(Collections.singletonMap("key", 42)); 136 assertEquals(Spliterator.DISTINCT | Spliterator.SIZED, 137 m.entrySet().spliterator().characteristics()); 138 } 139 140 /** 141 * Checks that {@code HashMap.entrySet().spliterator().trySplit()} 142 * estimates half of the parents' estimate (rounded down, which 143 * can be an underestimate) but is not itself SIZED. 144 * 145 * These assertions are still stronger than what the documentation 146 * guarantees since un-SIZED Spliterators' size estimates may be off by 147 * an arbitrary amount. 148 */ 149 public void test_entrySet_subsizeEstimates() { 150 Map<String, String> m = new HashMap<>(); 151 assertNull(m.entrySet().spliterator().trySplit()); 152 // For the empty map, the estimates are exact 153 assertEquals(0, m.entrySet().spliterator().estimateSize()); 154 assertEquals(0, m.entrySet().spliterator().getExactSizeIfKnown()); 155 156 m.put("key1", "value1"); 157 assertSubsizeEstimate(m.entrySet().spliterator(), 0); 158 m.put("key2", "value2"); 159 assertSubsizeEstimate(m.entrySet().spliterator(), 1); 160 m.put("key3", "value3"); 161 m.put("key4", "value4"); 162 m.put("key5", "value5"); 163 m.put("key6", "value6"); 164 m.put("key7", "value7"); 165 m.put("key8", "value8"); 166 assertSubsizeEstimate(m.entrySet().spliterator(), 4); 167 168 m.put("key9", "value9"); 169 assertSubsizeEstimate(m.entrySet().spliterator(), 4); 170 assertFalse(m.entrySet().spliterator().trySplit().hasCharacteristics(Spliterator.SIZED)); 171 } 172 173 /** 174 * Checks that HashMap.entrySet()'s spliterator halfs its estimate (rounding down) 175 * for each split, even though this estimate may be inaccurate. 176 */ 177 public void test_entrySet_subsizeEstimates_recursive() { 178 Map<Integer, String> m = new HashMap<>(); 179 for (int i = 0; i < 100; i++) { 180 m.put(i, "value"); 181 } 182 Set<Map.Entry<Integer, String>> entries = m.entrySet(); 183 // Recursive splitting - HashMap will estimate the size halving each split, rounding down. 184 assertSubsizeEstimate(entries.spliterator(), 50); 185 assertSubsizeEstimate(entries.spliterator().trySplit(), 25); 186 assertSubsizeEstimate(entries.spliterator().trySplit().trySplit(), 12); 187 assertSubsizeEstimate(entries.spliterator().trySplit().trySplit().trySplit(), 6); 188 assertSubsizeEstimate(entries.spliterator().trySplit().trySplit().trySplit().trySplit(), 3); 189 assertSubsizeEstimate( 190 entries.spliterator().trySplit().trySplit().trySplit().trySplit().trySplit(), 1); 191 assertSubsizeEstimate(entries.spliterator().trySplit().trySplit().trySplit().trySplit() 192 .trySplit().trySplit(), 0); 193 } 194 195 /** 196 * Checks that HashMap.EntryIterator is SIZED but not SUBSIZED. 197 */ 198 public void test_entrySet_spliterator_sizedButNotSubsized() { 199 Map<String, String> m = new HashMap<>(); 200 assertTrue(m.entrySet().spliterator().hasCharacteristics(Spliterator.SIZED)); 201 assertFalse(m.entrySet().spliterator().hasCharacteristics(Spliterator.SUBSIZED)); 202 m.put("key1", "value1"); 203 m.put("key2", "value2"); 204 assertTrue(m.entrySet().spliterator().hasCharacteristics(Spliterator.SIZED)); 205 assertFalse(m.entrySet().spliterator().hasCharacteristics(Spliterator.SUBSIZED)); 206 Spliterator<Map.Entry<String, String>> parent = m.entrySet().spliterator(); 207 Spliterator<Map.Entry<String, String>> child = parent.trySplit(); 208 assertFalse(parent.hasCharacteristics(Spliterator.SIZED)); 209 assertFalse(child.hasCharacteristics(Spliterator.SIZED)); 210 assertFalse(parent.hasCharacteristics(Spliterator.SUBSIZED)); 211 assertFalse(child.hasCharacteristics(Spliterator.SUBSIZED)); 212 } 213 214 /** 215 * Tests that the given spliterator can be trySplit(), resulting in children that each 216 * estimate the specified size. 217 */ 218 private static<T> void assertSubsizeEstimate(Spliterator<T> spliterator, 219 long expectedEstimate) { 220 Spliterator<T> child = spliterator.trySplit(); 221 assertNotNull(child); 222 assertEquals(expectedEstimate, spliterator.estimateSize()); 223 assertEquals(expectedEstimate, child.estimateSize()); 224 } 225 226 public void test_replaceAll() throws Exception { 227 HashMap<String, String> map = new HashMap<>(); 228 map.put("one", "1"); 229 map.put("two", "2"); 230 map.put("three", "3"); 231 232 map.replaceAll((k, v) -> k + v); 233 assertEquals("one1", map.get("one")); 234 assertEquals("two2", map.get("two")); 235 assertEquals("three3", map.get("three")); 236 assertEquals(3, map.size()); 237 238 try { 239 map.replaceAll((k, v) -> { 240 map.put("foo1", v); 241 return v; 242 }); 243 fail(); 244 } catch(ConcurrentModificationException expected) {} 245 246 try { 247 map.replaceAll(null); 248 fail(); 249 } catch(NullPointerException expected) {} 250 } 251} 252