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