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 junit.framework.TestCase;
20
21import java.util.AbstractMap;
22import java.util.AbstractMap.SimpleEntry;
23import java.util.Arrays;
24import java.util.Collection;
25import java.util.Comparator;
26import java.util.ConcurrentModificationException;
27import java.util.HashMap;
28import java.util.Iterator;
29import java.util.List;
30import java.util.Map;
31import java.util.Map.Entry;
32import java.util.NavigableMap;
33import java.util.Set;
34import java.util.SortedMap;
35import java.util.Spliterator;
36import java.util.TreeMap;
37import libcore.libcore.util.SerializationTester;
38
39public class TreeMapTest extends TestCase {
40
41    /**
42     * Test that the entrySet() method produces correctly mutable entries.
43     */
44    public void testEntrySetSetValue() {
45        TreeMap<String, String> map = new TreeMap<String, String>();
46        map.put("A", "a");
47        map.put("B", "b");
48        map.put("C", "c");
49
50        Iterator<Entry<String, String>> iterator = map.entrySet().iterator();
51        Entry<String, String> entryA = iterator.next();
52        assertEquals("a", entryA.setValue("x"));
53        assertEquals("x", entryA.getValue());
54        assertEquals("x", map.get("A"));
55        Entry<String, String> entryB = iterator.next();
56        assertEquals("b", entryB.setValue("y"));
57        Entry<String, String> entryC = iterator.next();
58        assertEquals("c", entryC.setValue("z"));
59        assertEquals("y", entryB.getValue());
60        assertEquals("y", map.get("B"));
61        assertEquals("z", entryC.getValue());
62        assertEquals("z", map.get("C"));
63    }
64
65    /**
66     * Test that the entrySet() method of a sub map produces correctly mutable
67     * entries that propagate changes to the original map.
68     */
69    public void testSubMapEntrySetSetValue() {
70        TreeMap<String, String> map = new TreeMap<String, String>();
71        map.put("A", "a");
72        map.put("B", "b");
73        map.put("C", "c");
74        map.put("D", "d");
75        NavigableMap<String, String> subMap = map.subMap("A", true, "C", true);
76
77        Iterator<Entry<String, String>> iterator = subMap.entrySet().iterator();
78        Entry<String, String> entryA = iterator.next();
79        assertEquals("a", entryA.setValue("x"));
80        assertEquals("x", entryA.getValue());
81        assertEquals("x", subMap.get("A"));
82        assertEquals("x", map.get("A"));
83        Entry<String, String> entryB = iterator.next();
84        assertEquals("b", entryB.setValue("y"));
85        Entry<String, String> entryC = iterator.next();
86        assertEquals("c", entryC.setValue("z"));
87        assertEquals("y", entryB.getValue());
88        assertEquals("y", subMap.get("B"));
89        assertEquals("y", map.get("B"));
90        assertEquals("z", entryC.getValue());
91        assertEquals("z", subMap.get("C"));
92        assertEquals("z", map.get("C"));
93    }
94
95    /**
96     * Test that an Entry given by any method except entrySet() is immutable.
97     */
98    public void testExceptionsOnSetValue() {
99        TreeMap<String, String> map = new TreeMap<String, String>();
100        map.put("A", "a");
101        map.put("B", "b");
102        map.put("C", "c");
103
104        assertAllEntryMethodsReturnImmutableEntries(map);
105    }
106
107    /**
108     * Test that an Entry given by any method except entrySet() of a sub map is immutable.
109     */
110    public void testExceptionsOnSubMapSetValue() {
111        TreeMap<String, String> map = new TreeMap<String, String>();
112        map.put("A", "a");
113        map.put("B", "b");
114        map.put("C", "c");
115        map.put("D", "d");
116
117        assertAllEntryMethodsReturnImmutableEntries(map.subMap("A", true, "C", true));
118    }
119
120    /**
121     * Asserts that each NavigableMap method that returns an Entry (except entrySet()) returns an
122     * immutable one. Assumes that the map contains at least entries with keys "A", "B" and "C".
123     */
124    private void assertAllEntryMethodsReturnImmutableEntries(NavigableMap<String, String> map) {
125        assertImmutable(map.ceilingEntry("B"));
126        assertImmutable(map.firstEntry());
127        assertImmutable(map.floorEntry("D"));
128        assertImmutable(map.higherEntry("A"));
129        assertImmutable(map.lastEntry());
130        assertImmutable(map.lowerEntry("C"));
131        assertImmutable(map.pollFirstEntry());
132        assertImmutable(map.pollLastEntry());
133    }
134
135    private void assertImmutable(Entry<String, String> entry) {
136        String initialValue = entry.getValue();
137        try {
138            entry.setValue("x");
139            fail();
140        } catch (UnsupportedOperationException e) {
141        }
142        assertEquals(initialValue, entry.getValue());
143    }
144
145    public void testConcurrentModificationDetection() {
146        Map<String, String> map = new TreeMap<String, String>();
147        map.put("A", "a");
148        map.put("B", "b");
149        map.put("C", "c");
150        Iterator<Entry<String,String>> iterator = map.entrySet().iterator();
151        iterator.next();
152        iterator.next();
153        iterator.remove();
154        map.put("D", "d");
155        try {
156            iterator.next();
157            fail();
158        } catch (ConcurrentModificationException e) {
159        }
160    }
161
162    public void testIteratorRemoves() {
163        Map<String, String> map = new TreeMap<String, String>();
164        map.put("A", "a");
165        map.put("B", "b");
166        map.put("C", "c");
167        Iterator<Entry<String,String>> iterator = map.entrySet().iterator();
168        assertEquals("A", iterator.next().getKey());
169        assertEquals("B", iterator.next().getKey());
170        iterator.remove();
171        assertEquals("C", iterator.next().getKey());
172        iterator.remove();
173        assertFalse(iterator.hasNext());
174    }
175
176    /**
177     * Test that entry set contains and removal use the comparator rather than equals.
178     */
179    public void testEntrySetUsesComparatorOnly() {
180        Map<String,String> map = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER);
181        map.put("ABC", "a");
182        assertTrue(map.entrySet().contains(new SimpleEntry<String, String>("abc", "a")));
183        assertTrue(map.entrySet().remove(new SimpleEntry<String, String>("abc", "a")));
184        assertEquals(0, map.size());
185    }
186
187    public void testMapConstructorPassingSortedMap() {
188        Map<String,String> source = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER);
189        NavigableMap<String,String> copy = new TreeMap<String, String>(source);
190        assertEquals(null, copy.comparator());
191    }
192
193    public void testNullsWithNaturalOrder() {
194        HashMap<String, String> copyFrom = new HashMap<String, String>();
195        copyFrom.put(null, "b");
196        try {
197            new TreeMap<String, String>(copyFrom);
198            fail(); // the RI doesn't throw if null is the only key
199        } catch (NullPointerException expected) {
200        }
201
202        TreeMap<String,String> map = new TreeMap<String, String>();
203        try {
204            map.put(null, "b");
205            fail();
206        } catch (NullPointerException e) {
207        }
208
209        try {
210            map.descendingMap().put(null, "b");
211            fail();
212        } catch (NullPointerException e) {
213        }
214
215        try {
216            map.subMap("a", "z").put(null, "b");
217            fail();
218        } catch (NullPointerException e) {
219        }
220    }
221
222    // Tests for naming of TreeMap.TreeMapEntry. Based on similar tests
223    // that exist for LinkedHashMap.LinkedHashMapEntry.
224    /**
225     * Check that {@code TreeMap.Entry} compiles and refers to
226     * {@link java.util.Map.Entry}, which is required for source
227     * compatibility with earlier versions of Android.
228     */
229    public void test_entryCompatibility_compiletime() {
230        assertEquals(Map.Entry.class, TreeMap.Entry.class);
231    }
232
233    /**
234     * Checks that there is no nested class named 'Entry' in TreeMap.
235     * If {@link #test_entryCompatibility_compiletime()} passes but
236     * this test fails, then the test was probably compiled against a
237     * version of TreeMap that does not have a nested Entry class,
238     * but run against a version that does.
239     */
240    public void test_entryCompatibility_runtime() {
241        String forbiddenClassName = "java.util.TreeMap$Entry";
242        try {
243            Class.forName(forbiddenClassName);
244            fail("Class " + forbiddenClassName + " should not exist");
245        } catch (ClassNotFoundException expected) {
246        }
247    }
248
249    public void testClassCastExceptions() {
250        Map<Object, Object> map = new TreeMap<Object, Object>();
251        map.put("A", "a");
252        try {
253            map.get(5);
254            fail();
255        } catch (ClassCastException e) {
256        }
257        try {
258            map.containsKey(5);
259            fail();
260        } catch (ClassCastException e) {
261        }
262        try {
263            map.remove(5);
264            fail();
265        } catch (ClassCastException e) {
266        }
267    }
268
269    public void testClassCastExceptionsOnBounds() {
270        Map<Object, Object> map = new TreeMap<Object, Object>().subMap("a", "z");
271        try {
272            map.get(5);
273            fail();
274        } catch (ClassCastException e) {
275        }
276        try {
277            map.containsKey(5);
278            fail();
279        } catch (ClassCastException e) {
280        }
281        try {
282            map.remove(5);
283            fail();
284        } catch (ClassCastException e) {
285        }
286    }
287
288    public void testClone() {
289        TreeMap<String, String> map = new TreeMap<String, String>() {
290            @Override public String toString() {
291                return "x:" + super.toString();
292            }
293        };
294
295        map.put("A", "a");
296        map.put("B", "b");
297
298        @SuppressWarnings("unchecked")
299        TreeMap<String, String> clone = (TreeMap<String, String>) map.clone();
300        assertEquals(map.getClass(), clone.getClass());
301        assertEquals("x:{A=a, B=b}", map.toString());
302    }
303
304    public void testEmptyMapSerialization() {
305        String s = "aced0005737200116a6176612e7574696c2e547265654d61700cc1f63e2d256a"
306                + "e60300014c000a636f6d70617261746f727400164c6a6176612f7574696c2f436"
307                + "f6d70617261746f723b78707077040000000078";
308        TreeMap<String, String> map = new TreeMap<String, String>();
309        new SerializationTester<TreeMap<String, String>>(map, s).test();
310    }
311
312    public void testSerializationWithComparator() {
313        String s = "aced0005737200116a6176612e7574696c2e547265654d61700cc1f63e2d256a"
314                + "e60300014c000a636f6d70617261746f727400164c6a6176612f7574696c2f436"
315                + "f6d70617261746f723b78707372002a6a6176612e6c616e672e537472696e6724"
316                + "43617365496e73656e736974697665436f6d70617261746f7277035c7d5c50e5c"
317                + "e02000078707704000000027400016171007e00057400016271007e000678";
318        TreeMap<String, String> map = new TreeMap<String, String>(
319                String.CASE_INSENSITIVE_ORDER);
320        map.put("a", "a");
321        map.put("b", "b");
322        new SerializationTester<NavigableMap<String, String>>(map, s) {
323            @Override protected void verify(NavigableMap<String, String> deserialized) {
324                assertEquals(0, deserialized.comparator().compare("X", "x"));
325            }
326        }.test();
327    }
328
329    public void testSubMapSerialization() {
330        // Updated golden value since we have a different serialVersionUID in OpenJDK.
331        String s = "aced0005737200216a6176612e7574696c2e547265654d617024417363656e646"
332                + "96e675375624d61700cab946d1f0fab1c020000787200216a6176612e7574696c2"
333                + "e547265654d6170244e6176696761626c655375624d617026617d4eacdd5933020"
334                + "0075a000966726f6d53746172745a000b6869496e636c75736976655a000b6c6f4"
335                + "96e636c75736976655a0005746f456e644c000268697400124c6a6176612f6c616"
336                + "e672f4f626a6563743b4c00026c6f71007e00024c00016d7400134c6a6176612f7"
337                + "574696c2f547265654d61703b7870000001007400016374000161737200116a617"
338                + "6612e7574696c2e547265654d61700cc1f63e2d256ae60300014c000a636f6d706"
339                + "17261746f727400164c6a6176612f7574696c2f436f6d70617261746f723b78707"
340                + "372002a6a6176612e6c616e672e537472696e672443617365496e73656e7369746"
341                + "97665436f6d70617261746f7277035c7d5c50e5ce0200007870770400000004710"
342                + "07e000671007e00067400016271007e000c71007e000571007e000574000164710"
343                + "07e000d78";
344        TreeMap<String, String> map = new TreeMap<String, String>(
345                String.CASE_INSENSITIVE_ORDER);
346        map.put("a", "a");
347        map.put("b", "b");
348        map.put("c", "c");
349        map.put("d", "d");
350        SortedMap<String, String> subMap = map.subMap("a", "c");
351        new SerializationTester<SortedMap<String, String>>(subMap, s) {
352            @Override protected void verify(SortedMap<String, String> deserialized) {
353                try {
354                    deserialized.put("e", "e");
355                    fail();
356                } catch (IllegalArgumentException expected) {
357                }
358            }
359        }.test();
360    }
361
362    public void testNavigableSubMapSerialization() {
363        // Updated golden value since we have a different serialVersionUID in OpenJDK.
364        String s = "aced0005737200216a6176612e7574696c2e547265654d617024417363656e646"
365                + "96e675375624d61700cab946d1f0fab1c020000787200216a6176612e7574696c2"
366                + "e547265654d6170244e6176696761626c655375624d617026617d4eacdd5933020"
367                + "0075a000966726f6d53746172745a000b6869496e636c75736976655a000b6c6f4"
368                + "96e636c75736976655a0005746f456e644c000268697400124c6a6176612f6c616"
369                + "e672f4f626a6563743b4c00026c6f71007e00024c00016d7400134c6a6176612f7"
370                + "574696c2f547265654d61703b7870000100007400016374000161737200116a617"
371                + "6612e7574696c2e547265654d61700cc1f63e2d256ae60300014c000a636f6d706"
372                + "17261746f727400164c6a6176612f7574696c2f436f6d70617261746f723b78707"
373                + "372002a6a6176612e6c616e672e537472696e672443617365496e73656e7369746"
374                + "97665436f6d70617261746f7277035c7d5c50e5ce0200007870770400000004710"
375                + "07e000671007e00067400016271007e000c71007e000571007e000574000164710"
376                + "07e000d78";
377        TreeMap<String, String> map = new TreeMap<String, String>(
378                String.CASE_INSENSITIVE_ORDER);
379        map.put("a", "a");
380        map.put("b", "b");
381        map.put("c", "c");
382        map.put("d", "d");
383        SortedMap<String, String> subMap = map.subMap("a", false, "c", true);
384        new SerializationTester<SortedMap<String, String>>(subMap, s) {
385            @Override protected void verify(SortedMap<String, String> deserialized) {
386                try {
387                    deserialized.put("e", "e");
388                    fail();
389                } catch (IllegalArgumentException expected) {
390                }
391            }
392        }.test();
393    }
394
395    public void testDescendingMapSerialization() {
396        // Updated golden value since we have a different serialVersionUID in OpenJDK.
397        String s = "aced0005737200226a6176612e7574696c2e547265654d61702444657363656e6"
398                + "4696e675375624d61700cab946d1f0f9d0c0200014c001172657665727365436f6"
399                + "d70617261746f727400164c6a6176612f7574696c2f436f6d70617261746f723b7"
400                + "87200216a6176612e7574696c2e547265654d6170244e6176696761626c6553756"
401                + "24d617026617d4eacdd59330200075a000966726f6d53746172745a000b6869496"
402                + "e636c75736976655a000b6c6f496e636c75736976655a0005746f456e644c00026"
403                + "8697400124c6a6176612f6c616e672f4f626a6563743b4c00026c6f71007e00034"
404                + "c00016d7400134c6a6176612f7574696c2f547265654d61703b787001010101707"
405                + "0737200116a6176612e7574696c2e547265654d61700cc1f63e2d256ae60300014"
406                + "c000a636f6d70617261746f7271007e000178707372002a6a6176612e6c616e672"
407                + "e537472696e672443617365496e73656e736974697665436f6d70617261746f727"
408                + "7035c7d5c50e5ce02000078707704000000027400016171007e000a74000162710"
409                + "07e000b78737200286a6176612e7574696c2e436f6c6c656374696f6e732452657"
410                + "665727365436f6d70617261746f7232000003fa6c354d510200014c0003636d707"
411                + "1007e0001787071007e0009";
412        TreeMap<String, String> map = new TreeMap<String, String>(
413                String.CASE_INSENSITIVE_ORDER);
414        map.put("a", "a");
415        map.put("b", "b");
416        NavigableMap<String, String> descendingMap = map.descendingMap();
417        new SerializationTester<NavigableMap<String, String>>(descendingMap, s) {
418            @Override protected void verify(NavigableMap<String, String> deserialized) {
419                assertEquals("b", deserialized.navigableKeySet().first());
420            }
421        }.test();
422    }
423
424    public void testJava5SerializationWithComparator() {
425        String s = "aced0005737200116a6176612e7574696c2e547265654d61700cc1f63e2d256a"
426                + "e60300014c000a636f6d70617261746f727400164c6a6176612f7574696c2f436"
427                + "f6d70617261746f723b78707372002a6a6176612e6c616e672e537472696e6724"
428                + "43617365496e73656e736974697665436f6d70617261746f7277035c7d5c50e5c"
429                + "e02000078707704000000027400016171007e00057400016271007e000678";
430        TreeMap<String, String> map = new TreeMap<String, String>(
431                String.CASE_INSENSITIVE_ORDER);
432        map.put("a", "a");
433        map.put("b", "b");
434        new SerializationTester<TreeMap<String, String>>(map, s) {
435            @Override protected void verify(TreeMap<String, String> deserialized) {
436                assertEquals(0, deserialized.comparator().compare("X", "x"));
437            }
438        }.test();
439    }
440
441    /**
442     * On JDK5, this fails with a NullPointerException after deserialization!
443     */
444    public void testJava5SubMapSerialization() {
445        String s = "aced0005737200186a6176612e7574696c2e547265654d6170245375624d6170"
446                + "a5818343a213c27f0200055a000966726f6d53746172745a0005746f456e644c0"
447                + "00766726f6d4b65797400124c6a6176612f6c616e672f4f626a6563743b4c0006"
448                + "7468697324307400134c6a6176612f7574696c2f547265654d61703b4c0005746"
449                + "f4b657971007e00017870000074000161737200116a6176612e7574696c2e5472"
450                + "65654d61700cc1f63e2d256ae60300014c000a636f6d70617261746f727400164"
451                + "c6a6176612f7574696c2f436f6d70617261746f723b78707372002a6a6176612e"
452                + "6c616e672e537472696e672443617365496e73656e736974697665436f6d70617"
453                + "261746f7277035c7d5c50e5ce020000787077040000000471007e000471007e00"
454                + "047400016271007e000a7400016371007e000b7400016471007e000c7871007e0"
455                + "00b";
456        TreeMap<String, String> map = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER);
457        map.put("a", "a");
458        map.put("b", "b");
459        map.put("c", "c");
460        map.put("d", "d");
461        SortedMap<String, String> subMap = map.subMap("a", "c");
462        new SerializationTester<SortedMap<String, String>>(subMap, s) {
463            @Override protected void verify(SortedMap<String, String> deserialized) {
464                try {
465                    deserialized.put("e", "e");
466                    fail();
467                } catch (IllegalArgumentException expected) {
468                }
469            }
470        }.test();
471    }
472
473    /**
474     * Taking a headMap or tailMap (exclusive or inclusive of the bound) of
475     * a TreeMap with unbounded range never throws IllegalArgumentException.
476     */
477    public void testBounds_fromUnbounded() {
478        applyBound('[', new TreeMap<>());
479        applyBound(']', new TreeMap<>());
480        applyBound('(', new TreeMap<>());
481        applyBound(')', new TreeMap<>());
482    }
483
484    /**
485     * Taking an exclusive-end submap of a parent map with an exclusive
486     * range is allowed only if the bounds go in the same direction
487     * (if parent and child are either both headMaps or both tailMaps,
488     * but not otherwise).
489     */
490    public void testBounds_openSubrangeOfOpenRange() {
491        // NavigableMap.{tail,head}Map(T key, boolean inclusive)'s
492        // documentation says that it throws IAE "if this map itself has a
493        // restricted range, and key lies outside the bounds of the range".
494        // Since that documentation doesn't mention the value of inclusive,
495        // one could argue that the following two cases should throw IAE,
496        // but the actual implementation in TreeMap does not. This test
497        // asserts the actual behavior.
498        assertTrue(isWithinBounds(')', ')'));
499        assertTrue(isWithinBounds('(', '('));
500
501        // The following two tests check that TreeMap's behavior matches
502        // that from earlier versions of Android (from before Android N).
503        // AOSP commit b4105e7f1e3ab24131976f68be4554e694a0e1d4 ensured
504        // that Android N was consistent with earlier versions' behavior.
505        // Specifically, on Android,
506        //      new TreeMap<>().headMap(0, false).tailMap(0, false)
507        // and  new TreeMap<>().tailMap(0, false).headMap(0, false)
508        // are both not allowed.
509        assertFalse(isWithinBounds(')', '('));
510        assertFalse(isWithinBounds('(', ')'));
511    }
512
513    /**
514     * Taking a exclusive-end submap of an inclusive-end parent map is not
515     * allowed regardless of the direction of the constraints (headMap
516     * vs. tailMap) because the inclusive bound of the submap is not
517     * contained in the exclusive range of the parent map.
518     */
519    public void testBounds_closedSubrangeOfOpenRange() {
520        assertFalse(isWithinBounds(']', '('));
521        assertFalse(isWithinBounds('[', ')'));
522        assertFalse(isWithinBounds(']', ')'));
523        assertFalse(isWithinBounds('[', '('));
524    }
525
526    /**
527     * Taking an inclusive-end submap of an inclusive-end parent map
528     * is allowed regardless of the direction of the constraints (headMap
529     * vs. tailMap) because the inclusive bound of the submap is
530     * contained in the inclusive range of the parent map.
531     */
532    public void testBounds_closedSubrangeOfClosedRange() {
533        assertTrue(isWithinBounds(']', '['));
534        assertTrue(isWithinBounds('[', ']'));
535        assertTrue(isWithinBounds(']', ']'));
536        assertTrue(isWithinBounds('[', '['));
537    }
538
539    /**
540     * Taking an exclusive-end submap of an inclusive-end parent map
541     * is allowed regardless of the direction of the constraints (headMap
542     * vs. tailMap) because the exclusive bound of the submap is
543     * contained in the inclusive range of the parent map.
544     *
545     * Note that
546     * (a) isWithinBounds(')', '[') == true, while
547     * (b) isWithinBounds('[', ')') == false
548     * means that
549     *   {@code new TreeMap<>().tailMap(0, true).headMap(0, false)}
550     * is allowed but
551     *   {@code new TreeMap<>().headMap(0, false).tailMap(0, true)}
552     * is not.
553     */
554    public void testBounds_openSubrangeOfClosedRange() {
555        assertTrue(isWithinBounds(')', '['));
556        assertTrue(isWithinBounds('(', ']'));
557        assertTrue(isWithinBounds('(', '['));
558        assertTrue(isWithinBounds(')', ']'));
559
560        // This is allowed:
561        new TreeMap<>().tailMap(0, true).headMap(0, false);
562
563        // This is not:
564        try {
565            new TreeMap<>().headMap(0, false).tailMap(0, true);
566            fail("Should have thrown");
567        } catch (IllegalArgumentException expected) {
568            // expected
569        }
570    }
571
572    /**
573     * Asserts whether constructing a (head or tail) submap with (inclusive or
574     * exclusive) bound 0 is allowed on a (head or tail) map with (inclusive or
575     * exclusive) bound 0. For example,
576     *
577     * {@code isWithinBounds(')', ']'} is true because the boundary of "0)"
578     * (an infinitesimally small negative value) lies within the range "0]",
579     * but {@code isWithinBounds(']', ')'} is false because 0 does not lie
580     * within the range "0)".
581     */
582    private static boolean isWithinBounds(char submapBound, char mapBound) {
583        NavigableMap<Integer, Void> m = applyBound(mapBound, new TreeMap<>());
584        IllegalArgumentException thrownException = null;
585        try {
586            applyBound(submapBound, m);
587        } catch (IllegalArgumentException e) {
588            thrownException = e;
589        }
590        return (thrownException == null);
591    }
592
593    /**
594     * Constructs a submap of the specified map, constrained by the given bound.
595     */
596    private static<V> NavigableMap<Integer, V> applyBound(char bound, NavigableMap<Integer, V> m) {
597        Integer boundValue = 0; // arbitrary
598        if (isLowerBound(bound)) {
599            return m.tailMap(boundValue, isBoundInclusive(bound));
600        } else {
601            return m.headMap(boundValue, isBoundInclusive(bound));
602        }
603    }
604
605    private static boolean isBoundInclusive(char bound) {
606        return bound == '[' || bound == ']';
607    }
608
609    /**
610     * Returns whether the specified bound corresponds to a tailMap, i.e. a Map whose
611     * range of values has an (exclusive or inclusive) lower bound.
612     */
613    private static boolean isLowerBound(char bound) {
614        return bound == '[' || bound == '(';
615    }
616
617    public void test_spliterator_keySet() {
618        TreeMap<String, String> treeMap = new TreeMap<>();
619        // Elements are added out of order to ensure ordering is still preserved.
620        treeMap.put("a", "1");
621        treeMap.put("i", "9");
622        treeMap.put("j", "10");
623        treeMap.put("k", "11");
624        treeMap.put("l", "12");
625        treeMap.put("b", "2");
626        treeMap.put("c", "3");
627        treeMap.put("d", "4");
628        treeMap.put("e", "5");
629        treeMap.put("n", "14");
630        treeMap.put("o", "15");
631        treeMap.put("p", "16");
632        treeMap.put("f", "6");
633        treeMap.put("g", "7");
634        treeMap.put("h", "8");
635        treeMap.put("m", "13");
636
637        Set<String> keys = treeMap.keySet();
638        List<String> expectedKeys = Arrays.asList(
639                "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k" , "l", "m", "n", "o", "p");
640
641        SpliteratorTester.runBasicIterationTests_unordered(keys.spliterator(), expectedKeys,
642                String::compareTo);
643        SpliteratorTester.runBasicSplitTests(keys, expectedKeys);
644        SpliteratorTester.testSpliteratorNPE(keys.spliterator());
645        assertEquals(
646                Spliterator.DISTINCT | Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SORTED,
647                keys.spliterator().characteristics());
648        SpliteratorTester.runSortedTests(keys);
649        SpliteratorTester.runOrderedTests(keys);
650        SpliteratorTester.assertSupportsTrySplit(keys);
651    }
652
653    public void test_spliterator_values() {
654        TreeMap<String, String> treeMap = new TreeMap<>();
655        // Elements are added out of order to ensure ordering is still preserved.
656        treeMap.put("a", "1");
657        treeMap.put("i", "9");
658        treeMap.put("j", "10");
659        treeMap.put("k", "11");
660        treeMap.put("l", "12");
661        treeMap.put("b", "2");
662        treeMap.put("c", "3");
663        treeMap.put("d", "4");
664        treeMap.put("e", "5");
665        treeMap.put("n", "14");
666        treeMap.put("o", "15");
667        treeMap.put("p", "16");
668        treeMap.put("f", "6");
669        treeMap.put("g", "7");
670        treeMap.put("h", "8");
671        treeMap.put("m", "13");
672
673        Collection<String> values = treeMap.values();
674        List<String> expectedValues = Arrays.asList("1", "2", "3", "4", "5", "6", "7", "8", "9",
675                "10", "11", "12", "13", "14", "15", "16");
676
677        SpliteratorTester.runBasicIterationTests_unordered(
678                values.spliterator(), expectedValues, String::compareTo);
679        SpliteratorTester.runBasicSplitTests(values, expectedValues);
680        SpliteratorTester.testSpliteratorNPE(values.spliterator());
681
682        assertEquals(Spliterator.ORDERED | Spliterator.SIZED,
683                values.spliterator().characteristics());
684        SpliteratorTester.runSizedTests(values, 16);
685        SpliteratorTester.runOrderedTests(values);
686        SpliteratorTester.assertSupportsTrySplit(values);
687    }
688
689    public void test_spliterator_entrySet() {
690        TreeMap<String, String> treeMap = new TreeMap<>();
691        // Elements are added out of order to ensure ordering is still preserved.
692        treeMap.put("a", "1");
693        treeMap.put("i", "9");
694        treeMap.put("j", "10");
695        treeMap.put("k", "11");
696        treeMap.put("l", "12");
697        treeMap.put("b", "2");
698        treeMap.put("c", "3");
699        treeMap.put("d", "4");
700        treeMap.put("e", "5");
701        treeMap.put("n", "14");
702        treeMap.put("o", "15");
703        treeMap.put("p", "16");
704        treeMap.put("f", "6");
705        treeMap.put("g", "7");
706        treeMap.put("h", "8");
707        treeMap.put("m", "13");
708
709        Set<Map.Entry<String, String>> entries = treeMap.entrySet();
710        List<Map.Entry<String, String>> expectedValues = Arrays.asList(
711                entry("a", "1"),
712                entry("b", "2"),
713                entry("c", "3"),
714                entry("d", "4"),
715                entry("e", "5"),
716                entry("f", "6"),
717                entry("g", "7"),
718                entry("h", "8"),
719                entry("i", "9"),
720                entry("j", "10"),
721                entry("k", "11"),
722                entry("l", "12"),
723                entry("m", "13"),
724                entry("n", "14"),
725                entry("o", "15"),
726                entry("p", "16")
727        );
728
729        Comparator<Map.Entry<String, String>> comparator =
730                (a, b) -> (a.getKey().compareTo(b.getKey()));
731
732        SpliteratorTester.runBasicIterationTests_unordered(entries.spliterator(), expectedValues,
733                (a, b) -> (a.getKey().compareTo(b.getKey())));
734        SpliteratorTester.runBasicSplitTests(entries, expectedValues, comparator);
735        SpliteratorTester.testSpliteratorNPE(entries.spliterator());
736
737        assertEquals(
738                Spliterator.DISTINCT | Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SORTED,
739                entries.spliterator().characteristics());
740        SpliteratorTester.runSortedTests(entries, (a, b) -> (a.getKey().compareTo(b.getKey())));
741        SpliteratorTester.runOrderedTests(entries);
742        SpliteratorTester.assertSupportsTrySplit(entries);
743    }
744
745    private static<K, V> Map.Entry<K, V> entry(K key, V value) {
746        return new AbstractMap.SimpleEntry<>(key, value);
747    }
748
749    public void test_replaceAll() throws Exception {
750        TreeMap<String, String> map = new TreeMap<>();
751        map.put("one", "1");
752        map.put("two", "2");
753        map.put("three", "3");
754
755        TreeMap<String, String> output = new TreeMap<>();
756        map.replaceAll((k, v) -> k + v);
757        assertEquals("one1", map.get("one"));
758        assertEquals("two2", map.get("two"));
759        assertEquals("three3", map.get("three"));
760
761        try {
762            map.replaceAll(null);
763            fail();
764        } catch(NullPointerException expected) {}
765
766        try {
767            map.replaceAll((k, v) -> {
768                map.put("foo", v);
769                return v;
770            });
771            fail();
772        } catch(ConcurrentModificationException expected) {}
773    }
774
775    public void test_replace$K$V$V() {
776        MapDefaultMethodTester.test_replace$K$V$V(new TreeMap<>(), false /* acceptsNullKey */,
777                true /* acceptsNullValue */);
778    }
779
780    public void test_replace$K$V() {
781        MapDefaultMethodTester.test_replace$K$V(new TreeMap<>(), false /* acceptsNullKey */,
782                true /* acceptsNullValue */);
783    }
784}
785