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 java.util.AbstractMap.SimpleEntry;
20import java.util.ConcurrentModificationException;
21import java.util.HashMap;
22import java.util.Iterator;
23import java.util.Map;
24import java.util.Map.Entry;
25import java.util.NavigableMap;
26import java.util.SortedMap;
27import java.util.TreeMap;
28import junit.framework.TestCase;
29import libcore.util.SerializationTester;
30
31public class TreeMapTest extends TestCase {
32
33    /**
34     * Test that the entrySet() method produces correctly mutable entries.
35     */
36    public void testEntrySetSetValue() {
37        TreeMap<String, String> map = new TreeMap<String, String>();
38        map.put("A", "a");
39        map.put("B", "b");
40        map.put("C", "c");
41
42        Iterator<Entry<String, String>> iterator = map.entrySet().iterator();
43        Entry<String, String> entryA = iterator.next();
44        assertEquals("a", entryA.setValue("x"));
45        assertEquals("x", entryA.getValue());
46        assertEquals("x", map.get("A"));
47        Entry<String, String> entryB = iterator.next();
48        assertEquals("b", entryB.setValue("y"));
49        Entry<String, String> entryC = iterator.next();
50        assertEquals("c", entryC.setValue("z"));
51        assertEquals("y", entryB.getValue());
52        assertEquals("y", map.get("B"));
53        assertEquals("z", entryC.getValue());
54        assertEquals("z", map.get("C"));
55    }
56
57    /**
58     * Test that the entrySet() method of a sub map produces correctly mutable
59     * entries that propagate changes to the original map.
60     */
61    public void testSubMapEntrySetSetValue() {
62        TreeMap<String, String> map = new TreeMap<String, String>();
63        map.put("A", "a");
64        map.put("B", "b");
65        map.put("C", "c");
66        map.put("D", "d");
67        NavigableMap<String, String> subMap = map.subMap("A", true, "C", true);
68
69        Iterator<Entry<String, String>> iterator = subMap.entrySet().iterator();
70        Entry<String, String> entryA = iterator.next();
71        assertEquals("a", entryA.setValue("x"));
72        assertEquals("x", entryA.getValue());
73        assertEquals("x", subMap.get("A"));
74        assertEquals("x", map.get("A"));
75        Entry<String, String> entryB = iterator.next();
76        assertEquals("b", entryB.setValue("y"));
77        Entry<String, String> entryC = iterator.next();
78        assertEquals("c", entryC.setValue("z"));
79        assertEquals("y", entryB.getValue());
80        assertEquals("y", subMap.get("B"));
81        assertEquals("y", map.get("B"));
82        assertEquals("z", entryC.getValue());
83        assertEquals("z", subMap.get("C"));
84        assertEquals("z", map.get("C"));
85    }
86
87    /**
88     * Test that an Entry given by any method except entrySet() is immutable.
89     */
90    public void testExceptionsOnSetValue() {
91        TreeMap<String, String> map = new TreeMap<String, String>();
92        map.put("A", "a");
93        map.put("B", "b");
94        map.put("C", "c");
95
96        assertAllEntryMethodsReturnImmutableEntries(map);
97    }
98
99    /**
100     * Test that an Entry given by any method except entrySet() of a sub map is immutable.
101     */
102    public void testExceptionsOnSubMapSetValue() {
103        TreeMap<String, String> map = new TreeMap<String, String>();
104        map.put("A", "a");
105        map.put("B", "b");
106        map.put("C", "c");
107        map.put("D", "d");
108
109        assertAllEntryMethodsReturnImmutableEntries(map.subMap("A", true, "C", true));
110    }
111
112    /**
113     * Asserts that each NavigableMap method that returns an Entry (except entrySet()) returns an
114     * immutable one. Assumes that the map contains at least entries with keys "A", "B" and "C".
115     */
116    private void assertAllEntryMethodsReturnImmutableEntries(NavigableMap<String, String> map) {
117        assertImmutable(map.ceilingEntry("B"));
118        assertImmutable(map.firstEntry());
119        assertImmutable(map.floorEntry("D"));
120        assertImmutable(map.higherEntry("A"));
121        assertImmutable(map.lastEntry());
122        assertImmutable(map.lowerEntry("C"));
123        assertImmutable(map.pollFirstEntry());
124        assertImmutable(map.pollLastEntry());
125    }
126
127    private void assertImmutable(Entry<String, String> entry) {
128        String initialValue = entry.getValue();
129        try {
130            entry.setValue("x");
131            fail();
132        } catch (UnsupportedOperationException e) {
133        }
134        assertEquals(initialValue, entry.getValue());
135    }
136
137    public void testConcurrentModificationDetection() {
138        Map<String, String> map = new TreeMap<String, String>();
139        map.put("A", "a");
140        map.put("B", "b");
141        map.put("C", "c");
142        Iterator<Entry<String,String>> iterator = map.entrySet().iterator();
143        iterator.next();
144        iterator.next();
145        iterator.remove();
146        map.put("D", "d");
147        try {
148            iterator.next();
149            fail();
150        } catch (ConcurrentModificationException e) {
151        }
152    }
153
154    public void testIteratorRemoves() {
155        Map<String, String> map = new TreeMap<String, String>();
156        map.put("A", "a");
157        map.put("B", "b");
158        map.put("C", "c");
159        Iterator<Entry<String,String>> iterator = map.entrySet().iterator();
160        assertEquals("A", iterator.next().getKey());
161        assertEquals("B", iterator.next().getKey());
162        iterator.remove();
163        assertEquals("C", iterator.next().getKey());
164        iterator.remove();
165        assertFalse(iterator.hasNext());
166    }
167
168    /**
169     * Test that entry set contains and removal use the comparator rather than equals.
170     */
171    public void testEntrySetUsesComparatorOnly() {
172        Map<String,String> map = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER);
173        map.put("ABC", "a");
174        assertTrue(map.entrySet().contains(new SimpleEntry<String, String>("abc", "a")));
175        assertTrue(map.entrySet().remove(new SimpleEntry<String, String>("abc", "a")));
176        assertEquals(0, map.size());
177    }
178
179    public void testMapConstructorPassingSortedMap() {
180        Map<String,String> source = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER);
181        NavigableMap<String,String> copy = new TreeMap<String, String>(source);
182        assertEquals(null, copy.comparator());
183    }
184
185    public void testNullsWithNaturalOrder() {
186        HashMap<String, String> copyFrom = new HashMap<String, String>();
187        copyFrom.put(null, "b");
188        try {
189            new TreeMap<String, String>(copyFrom);
190            fail(); // the RI doesn't throw if null is the only key
191        } catch (NullPointerException expected) {
192        }
193
194        TreeMap<String,String> map = new TreeMap<String, String>();
195        try {
196            map.put(null, "b");
197            fail();
198        } catch (NullPointerException e) {
199        }
200
201        try {
202            map.descendingMap().put(null, "b");
203            fail();
204        } catch (NullPointerException e) {
205        }
206
207        try {
208            map.subMap("a", "z").put(null, "b");
209            fail();
210        } catch (NullPointerException e) {
211        }
212    }
213
214    public void testClassCastExceptions() {
215        Map<Object, Object> map = new TreeMap<Object, Object>();
216        map.put("A", "a");
217        try {
218            map.get(5);
219            fail();
220        } catch (ClassCastException e) {
221        }
222        try {
223            map.containsKey(5);
224            fail();
225        } catch (ClassCastException e) {
226        }
227        try {
228            map.remove(5);
229            fail();
230        } catch (ClassCastException e) {
231        }
232    }
233
234    public void testClassCastExceptionsOnBounds() {
235        Map<Object, Object> map = new TreeMap<Object, Object>().subMap("a", "z");
236        try {
237            map.get(5);
238            fail();
239        } catch (ClassCastException e) {
240        }
241        try {
242            map.containsKey(5);
243            fail();
244        } catch (ClassCastException e) {
245        }
246        try {
247            map.remove(5);
248            fail();
249        } catch (ClassCastException e) {
250        }
251    }
252
253    public void testClone() {
254        TreeMap<String, String> map = new TreeMap<String, String>() {
255            @Override public String toString() {
256                return "x:" + super.toString();
257            }
258        };
259
260        map.put("A", "a");
261        map.put("B", "b");
262
263        @SuppressWarnings("unchecked")
264        TreeMap<String, String> clone = (TreeMap<String, String>) map.clone();
265        assertEquals(map.getClass(), clone.getClass());
266        assertEquals("x:{A=a, B=b}", map.toString());
267    }
268
269    public void testEmptyMapSerialization() {
270        String s = "aced0005737200116a6176612e7574696c2e547265654d61700cc1f63e2d256a"
271                + "e60300014c000a636f6d70617261746f727400164c6a6176612f7574696c2f436"
272                + "f6d70617261746f723b78707077040000000078";
273        TreeMap<String, String> map = new TreeMap<String, String>();
274        new SerializationTester<TreeMap<String, String>>(map, s).test();
275    }
276
277    public void testSerializationWithComparator() {
278        String s = "aced0005737200116a6176612e7574696c2e547265654d61700cc1f63e2d256a"
279                + "e60300014c000a636f6d70617261746f727400164c6a6176612f7574696c2f436"
280                + "f6d70617261746f723b78707372002a6a6176612e6c616e672e537472696e6724"
281                + "43617365496e73656e736974697665436f6d70617261746f7277035c7d5c50e5c"
282                + "e02000078707704000000027400016171007e00057400016271007e000678";
283        TreeMap<String, String> map = new TreeMap<String, String>(
284                String.CASE_INSENSITIVE_ORDER);
285        map.put("a", "a");
286        map.put("b", "b");
287        new SerializationTester<NavigableMap<String, String>>(map, s) {
288            @Override protected void verify(NavigableMap<String, String> deserialized) {
289                assertEquals(0, deserialized.comparator().compare("X", "x"));
290            }
291        }.test();
292    }
293
294    public void testSubMapSerialization() {
295        String s = "aced0005737200216a6176612e7574696c2e547265654d617024417363656e646"
296                + "96e675375624d61700cab946d1f0fab1c020000787200216a6176612e7574696c2"
297                + "e547265654d6170244e6176696761626c655375624d6170e2d0a70e64210e08020"
298                + "0075a000966726f6d53746172745a000b6869496e636c75736976655a000b6c6f4"
299                + "96e636c75736976655a0005746f456e644c000268697400124c6a6176612f6c616"
300                + "e672f4f626a6563743b4c00026c6f71007e00024c00016d7400134c6a6176612f7"
301                + "574696c2f547265654d61703b7870000001007400016374000161737200116a617"
302                + "6612e7574696c2e547265654d61700cc1f63e2d256ae60300014c000a636f6d706"
303                + "17261746f727400164c6a6176612f7574696c2f436f6d70617261746f723b78707"
304                + "372002a6a6176612e6c616e672e537472696e672443617365496e73656e7369746"
305                + "97665436f6d70617261746f7277035c7d5c50e5ce0200007870770400000004710"
306                + "07e000671007e00067400016271007e000c71007e000571007e000574000164710"
307                + "07e000d78";
308        TreeMap<String, String> map = new TreeMap<String, String>(
309                String.CASE_INSENSITIVE_ORDER);
310        map.put("a", "a");
311        map.put("b", "b");
312        map.put("c", "c");
313        map.put("d", "d");
314        SortedMap<String, String> subMap = map.subMap("a", "c");
315        new SerializationTester<SortedMap<String, String>>(subMap, s) {
316            @Override protected void verify(SortedMap<String, String> deserialized) {
317                try {
318                    deserialized.put("e", "e");
319                    fail();
320                } catch (IllegalArgumentException expected) {
321                }
322            }
323        }.test();
324    }
325
326    public void testNavigableSubMapSerialization() {
327        String s = "aced0005737200216a6176612e7574696c2e547265654d617024417363656e646"
328                + "96e675375624d61700cab946d1f0fab1c020000787200216a6176612e7574696c2"
329                + "e547265654d6170244e6176696761626c655375624d6170e2d0a70e64210e08020"
330                + "0075a000966726f6d53746172745a000b6869496e636c75736976655a000b6c6f4"
331                + "96e636c75736976655a0005746f456e644c000268697400124c6a6176612f6c616"
332                + "e672f4f626a6563743b4c00026c6f71007e00024c00016d7400134c6a6176612f7"
333                + "574696c2f547265654d61703b7870000100007400016374000161737200116a617"
334                + "6612e7574696c2e547265654d61700cc1f63e2d256ae60300014c000a636f6d706"
335                + "17261746f727400164c6a6176612f7574696c2f436f6d70617261746f723b78707"
336                + "372002a6a6176612e6c616e672e537472696e672443617365496e73656e7369746"
337                + "97665436f6d70617261746f7277035c7d5c50e5ce0200007870770400000004710"
338                + "07e000671007e00067400016271007e000c71007e000571007e000574000164710"
339                + "07e000d78";
340        TreeMap<String, String> map = new TreeMap<String, String>(
341                String.CASE_INSENSITIVE_ORDER);
342        map.put("a", "a");
343        map.put("b", "b");
344        map.put("c", "c");
345        map.put("d", "d");
346        SortedMap<String, String> subMap = map.subMap("a", false, "c", true);
347        new SerializationTester<SortedMap<String, String>>(subMap, s) {
348            @Override protected void verify(SortedMap<String, String> deserialized) {
349                try {
350                    deserialized.put("e", "e");
351                    fail();
352                } catch (IllegalArgumentException expected) {
353                }
354            }
355        }.test();
356    }
357
358    public void testDescendingMapSerialization() {
359        String s = "aced0005737200226a6176612e7574696c2e547265654d61702444657363656e6"
360                + "4696e675375624d61700cab946d1f0f9d0c0200014c001172657665727365436f6"
361                + "d70617261746f727400164c6a6176612f7574696c2f436f6d70617261746f723b7"
362                + "87200216a6176612e7574696c2e547265654d6170244e6176696761626c6553756"
363                + "24d6170e2d0a70e64210e080200075a000966726f6d53746172745a000b6869496"
364                + "e636c75736976655a000b6c6f496e636c75736976655a0005746f456e644c00026"
365                + "8697400124c6a6176612f6c616e672f4f626a6563743b4c00026c6f71007e00034"
366                + "c00016d7400134c6a6176612f7574696c2f547265654d61703b787001010101707"
367                + "0737200116a6176612e7574696c2e547265654d61700cc1f63e2d256ae60300014"
368                + "c000a636f6d70617261746f7271007e000178707372002a6a6176612e6c616e672"
369                + "e537472696e672443617365496e73656e736974697665436f6d70617261746f727"
370                + "7035c7d5c50e5ce02000078707704000000027400016171007e000a74000162710"
371                + "07e000b78737200286a6176612e7574696c2e436f6c6c656374696f6e732452657"
372                + "665727365436f6d70617261746f7232000003fa6c354d510200014c0003636d707"
373                + "1007e0001787071007e0009";
374        TreeMap<String, String> map = new TreeMap<String, String>(
375                String.CASE_INSENSITIVE_ORDER);
376        map.put("a", "a");
377        map.put("b", "b");
378        NavigableMap<String, String> descendingMap = map.descendingMap();
379        new SerializationTester<NavigableMap<String, String>>(descendingMap, s) {
380            @Override protected void verify(NavigableMap<String, String> deserialized) {
381                assertEquals("b", deserialized.navigableKeySet().first());
382            }
383        }.test();
384    }
385
386    public void testJava5SerializationWithComparator() {
387        String s = "aced0005737200116a6176612e7574696c2e547265654d61700cc1f63e2d256a"
388                + "e60300014c000a636f6d70617261746f727400164c6a6176612f7574696c2f436"
389                + "f6d70617261746f723b78707372002a6a6176612e6c616e672e537472696e6724"
390                + "43617365496e73656e736974697665436f6d70617261746f7277035c7d5c50e5c"
391                + "e02000078707704000000027400016171007e00057400016271007e000678";
392        TreeMap<String, String> map = new TreeMap<String, String>(
393                String.CASE_INSENSITIVE_ORDER);
394        map.put("a", "a");
395        map.put("b", "b");
396        new SerializationTester<TreeMap<String, String>>(map, s) {
397            @Override protected void verify(TreeMap<String, String> deserialized) {
398                assertEquals(0, deserialized.comparator().compare("X", "x"));
399            }
400        }.test();
401    }
402
403    /**
404     * On JDK5, this fails with a NullPointerException after deserialization!
405     */
406    public void testJava5SubMapSerialization() {
407        String s = "aced0005737200186a6176612e7574696c2e547265654d6170245375624d6170"
408                + "a5818343a213c27f0200055a000966726f6d53746172745a0005746f456e644c0"
409                + "00766726f6d4b65797400124c6a6176612f6c616e672f4f626a6563743b4c0006"
410                + "7468697324307400134c6a6176612f7574696c2f547265654d61703b4c0005746"
411                + "f4b657971007e00017870000074000161737200116a6176612e7574696c2e5472"
412                + "65654d61700cc1f63e2d256ae60300014c000a636f6d70617261746f727400164"
413                + "c6a6176612f7574696c2f436f6d70617261746f723b78707372002a6a6176612e"
414                + "6c616e672e537472696e672443617365496e73656e736974697665436f6d70617"
415                + "261746f7277035c7d5c50e5ce020000787077040000000471007e000471007e00"
416                + "047400016271007e000a7400016371007e000b7400016471007e000c7871007e0"
417                + "00b";
418        TreeMap<String, String> map = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER);
419        map.put("a", "a");
420        map.put("b", "b");
421        map.put("c", "c");
422        map.put("d", "d");
423        SortedMap<String, String> subMap = map.subMap("a", "c");
424        new SerializationTester<SortedMap<String, String>>(subMap, s) {
425            @Override protected void verify(SortedMap<String, String> deserialized) {
426                try {
427                    deserialized.put("e", "e");
428                    fail();
429                } catch (IllegalArgumentException expected) {
430                }
431            }
432        }.test();
433    }
434}
435