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