1 /*
2  *  Licensed to the Apache Software Foundation (ASF) under one or more
3  *  contributor license agreements.  See the NOTICE file distributed with
4  *  this work for additional information regarding copyright ownership.
5  *  The ASF licenses this file to You under the Apache License, Version 2.0
6  *  (the "License"); you may not use this file except in compliance with
7  *  the License.  You may obtain a copy of the License at
8  *
9  *     http://www.apache.org/licenses/LICENSE-2.0
10  *
11  *  Unless required by applicable law or agreed to in writing, software
12  *  distributed under the License is distributed on an "AS IS" BASIS,
13  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  *  See the License for the specific language governing permissions and
15  *  limitations under the License.
16  */
17 
18 package org.apache.harmony.tests.java.util;
19 
20 import org.apache.harmony.testframework.serialization.SerializationTest;
21 import tests.support.Support_MapTest2;
22 import tests.support.Support_UnmodifiableCollectionTest;
23 import java.io.Serializable;
24 import java.text.CollationKey;
25 import java.text.Collator;
26 import java.util.AbstractMap;
27 import java.util.Collection;
28 import java.util.ConcurrentModificationException;
29 import java.util.Comparator;
30 import java.util.HashMap;
31 import java.util.HashSet;
32 import java.util.Iterator;
33 import java.util.LinkedList;
34 import java.util.List;
35 import java.util.Map;
36 import java.util.Map.Entry;
37 import java.util.NavigableMap;
38 import java.util.NavigableSet;
39 import java.util.NoSuchElementException;
40 import java.util.Set;
41 import java.util.SortedMap;
42 import java.util.TreeMap;
43 
44 public class TreeMapTest extends junit.framework.TestCase {
45 
46     public static class ReversedComparator implements Comparator {
compare(Object o1, Object o2)47         public int compare(Object o1, Object o2) {
48             return -(((Comparable) o1).compareTo(o2));
49         }
50 
equals(Object o1, Object o2)51         public boolean equals(Object o1, Object o2) {
52             return (((Comparable) o1).compareTo(o2)) == 0;
53         }
54     }
55 
56     // Regression for Harmony-1026
57     public static class MockComparator<T extends Comparable<T>> implements
58             Comparator<T>, Serializable {
59 
compare(T o1, T o2)60         public int compare(T o1, T o2) {
61             if (o1 == o2) {
62                 return 0;
63             }
64             if (null == o1 || null == o2) {
65                 return -1;
66             }
67             T c1 = o1;
68             T c2 = o2;
69             return c1.compareTo(c2);
70         }
71     }
72 
73     // Regression for Harmony-1161
74     class MockComparatorNullTolerable implements Comparator<String> {
75 
compare(String o1, String o2)76         public int compare(String o1, String o2) {
77             if (o1 == o2) {
78                 return 0;
79             }
80             if (null == o1) {
81                 return -1;
82             }
83             if (null == o2) { // comparator should be symmetric
84                 return 1;
85             }
86             return o1.compareTo(o2);
87         }
88     }
89 
90     TreeMap tm;
91 
92     Object objArray[] = new Object[1000];
93 
94     /**
95      * java.util.TreeMap#TreeMap()
96      */
test_Constructor()97     public void test_Constructor() {
98         // Test for method java.util.TreeMap()
99         new Support_MapTest2(new TreeMap()).runTest();
100 
101         assertTrue("New treeMap non-empty", new TreeMap().isEmpty());
102     }
103 
104     /**
105      * java.util.TreeMap#TreeMap(java.util.Comparator)
106      */
test_ConstructorLjava_util_Comparator()107     public void test_ConstructorLjava_util_Comparator() {
108         // Test for method java.util.TreeMap(java.util.Comparator)
109         Comparator comp = new ReversedComparator();
110         TreeMap reversedTreeMap = new TreeMap(comp);
111         assertTrue("TreeMap answered incorrect comparator", reversedTreeMap
112                 .comparator() == comp);
113         reversedTreeMap.put(new Integer(1).toString(), new Integer(1));
114         reversedTreeMap.put(new Integer(2).toString(), new Integer(2));
115         assertTrue("TreeMap does not use comparator (firstKey was incorrect)",
116                 reversedTreeMap.firstKey().equals(new Integer(2).toString()));
117         assertTrue("TreeMap does not use comparator (lastKey was incorrect)",
118                 reversedTreeMap.lastKey().equals(new Integer(1).toString()));
119 
120     }
121 
122     /**
123      * java.util.TreeMap#TreeMap(java.util.Map)
124      */
test_ConstructorLjava_util_Map()125     public void test_ConstructorLjava_util_Map() {
126         // Test for method java.util.TreeMap(java.util.Map)
127         TreeMap myTreeMap = new TreeMap(new HashMap(tm));
128         assertTrue("Map is incorrect size", myTreeMap.size() == objArray.length);
129         for (Object element : objArray) {
130             assertTrue("Map has incorrect mappings", myTreeMap.get(
131                     element.toString()).equals(element));
132         }
133     }
134 
135     /**
136      * java.util.TreeMap#TreeMap(java.util.SortedMap)
137      */
test_ConstructorLjava_util_SortedMap()138     public void test_ConstructorLjava_util_SortedMap() {
139         // Test for method java.util.TreeMap(java.util.SortedMap)
140         Comparator comp = new ReversedComparator();
141         TreeMap reversedTreeMap = new TreeMap(comp);
142         reversedTreeMap.put(new Integer(1).toString(), new Integer(1));
143         reversedTreeMap.put(new Integer(2).toString(), new Integer(2));
144         TreeMap anotherTreeMap = new TreeMap(reversedTreeMap);
145         assertTrue("New tree map does not answer correct comparator",
146                 anotherTreeMap.comparator() == comp);
147         assertTrue("TreeMap does not use comparator (firstKey was incorrect)",
148                 anotherTreeMap.firstKey().equals(new Integer(2).toString()));
149         assertTrue("TreeMap does not use comparator (lastKey was incorrect)",
150                 anotherTreeMap.lastKey().equals(new Integer(1).toString()));
151 
152     }
153 
154     /**
155      * java.util.TreeMap#clear()
156      */
test_clear()157     public void test_clear() {
158         // Test for method void java.util.TreeMap.clear()
159         tm.clear();
160         assertEquals("Cleared map returned non-zero size", 0, tm.size());
161     }
162 
163     /**
164      * java.util.TreeMap#clone()
165      */
test_clone()166     public void test_clone() {
167         // Test for method java.lang.Object java.util.TreeMap.clone()
168         TreeMap clonedMap = (TreeMap) tm.clone();
169         assertTrue("Cloned map does not equal the original map", clonedMap
170                 .equals(tm));
171         assertTrue("Cloned map is the same reference as the original map",
172                 clonedMap != tm);
173         for (Object element : objArray) {
174             assertTrue("Cloned map contains incorrect elements", clonedMap
175                     .get(element.toString()) == tm.get(element.toString()));
176         }
177 
178         TreeMap map = new TreeMap();
179         map.put("key", "value");
180         // get the keySet() and values() on the original Map
181         Set keys = map.keySet();
182         Collection values = map.values();
183         assertEquals("values() does not work", "value", values.iterator()
184                 .next());
185         assertEquals("keySet() does not work", "key", keys.iterator().next());
186         AbstractMap map2 = (AbstractMap) map.clone();
187         map2.put("key", "value2");
188         Collection values2 = map2.values();
189         assertTrue("values() is identical", values2 != values);
190         // values() and keySet() on the cloned() map should be different
191         assertEquals("values() was not cloned", "value2", values2.iterator()
192                 .next());
193         map2.clear();
194         map2.put("key2", "value3");
195         Set key2 = map2.keySet();
196         assertTrue("keySet() is identical", key2 != keys);
197         assertEquals("keySet() was not cloned", "key2", key2.iterator().next());
198     }
199 
200     /**
201      * java.util.TreeMap#comparator()
202      */
test_comparator()203     public void test_comparator() {
204         // Test for method java.util.Comparator java.util.TreeMap.comparator()\
205         Comparator comp = new ReversedComparator();
206         TreeMap reversedTreeMap = new TreeMap(comp);
207         assertTrue("TreeMap answered incorrect comparator", reversedTreeMap
208                 .comparator() == comp);
209         reversedTreeMap.put(new Integer(1).toString(), new Integer(1));
210         reversedTreeMap.put(new Integer(2).toString(), new Integer(2));
211         assertTrue("TreeMap does not use comparator (firstKey was incorrect)",
212                 reversedTreeMap.firstKey().equals(new Integer(2).toString()));
213         assertTrue("TreeMap does not use comparator (lastKey was incorrect)",
214                 reversedTreeMap.lastKey().equals(new Integer(1).toString()));
215     }
216 
217     /**
218      * java.util.TreeMap#containsKey(java.lang.Object)
219      */
test_containsKeyLjava_lang_Object()220     public void test_containsKeyLjava_lang_Object() {
221         // Test for method boolean
222         // java.util.TreeMap.containsKey(java.lang.Object)
223         assertTrue("Returned false for valid key", tm.containsKey("95"));
224         assertTrue("Returned true for invalid key", !tm.containsKey("XXXXX"));
225     }
226 
227     /**
228      * java.util.TreeMap#containsValue(java.lang.Object)
229      */
test_containsValueLjava_lang_Object()230     public void test_containsValueLjava_lang_Object() {
231         // Test for method boolean
232         // java.util.TreeMap.containsValue(java.lang.Object)
233         assertTrue("Returned false for valid value", tm
234                 .containsValue(objArray[986]));
235         assertTrue("Returned true for invalid value", !tm
236                 .containsValue(new Object()));
237     }
238 
239     /**
240      * java.util.TreeMap#entrySet()
241      */
test_entrySet()242     public void test_entrySet() {
243         // Test for method java.util.Set java.util.TreeMap.entrySet()
244         Set anEntrySet = tm.entrySet();
245         Iterator entrySetIterator = anEntrySet.iterator();
246         assertTrue("EntrySet is incorrect size",
247                 anEntrySet.size() == objArray.length);
248         Map.Entry entry;
249         while (entrySetIterator.hasNext()) {
250             entry = (Map.Entry) entrySetIterator.next();
251             assertTrue("EntrySet does not contain correct mappings", tm
252                     .get(entry.getKey()) == entry.getValue());
253         }
254     }
255 
256     /**
257      * java.util.TreeMap#firstKey()
258      */
test_firstKey()259     public void test_firstKey() {
260         // Test for method java.lang.Object java.util.TreeMap.firstKey()
261         assertEquals("Returned incorrect first key", "0", tm.firstKey());
262     }
263 
264     /**
265      * java.util.TreeMap#get(java.lang.Object)
266      */
test_getLjava_lang_Object()267     public void test_getLjava_lang_Object() {
268         // Test for method java.lang.Object
269         // java.util.TreeMap.get(java.lang.Object)
270         Object o = new Object();
271         tm.put("Hello", o);
272         assertTrue("Failed to get mapping", tm.get("Hello") == o);
273 
274         // Test for the same key & same value
275         tm = new TreeMap();
276         Object o2 = new Object();
277         Integer key1 = 1;
278         Integer key2 = 2;
279         assertNull(tm.put(key1, o));
280         assertNull(tm.put(key2, o));
281         assertEquals(2, tm.values().size());
282         assertEquals(2, tm.keySet().size());
283         assertSame(tm.get(key1), tm.get(key2));
284         assertSame(o, tm.put(key1, o2));
285         assertSame(o2, tm.get(key1));
286     }
287 
288     /**
289      * java.util.TreeMap#headMap(java.lang.Object)
290      */
test_headMapLjava_lang_Object()291     public void test_headMapLjava_lang_Object() {
292         // Test for method java.util.SortedMap
293         // java.util.TreeMap.headMap(java.lang.Object)
294         Map head = tm.headMap("100");
295         assertEquals("Returned map of incorrect size", 3, head.size());
296         assertTrue("Returned incorrect elements", head.containsKey("0")
297                 && head.containsValue(new Integer("1"))
298                 && head.containsKey("10"));
299 
300         // Regression for Harmony-1026
301         TreeMap<Integer, Double> map = new TreeMap<Integer, Double>(
302                 new MockComparator());
303         map.put(1, 2.1);
304         map.put(2, 3.1);
305         map.put(3, 4.5);
306         map.put(7, 21.3);
307         map.put(null, null);
308 
309         SortedMap<Integer, Double> smap = map.headMap(null);
310         assertEquals(0, smap.size());
311 
312         Set<Integer> keySet = smap.keySet();
313         assertEquals(0, keySet.size());
314 
315         Set<Map.Entry<Integer, Double>> entrySet = smap.entrySet();
316         assertEquals(0, entrySet.size());
317 
318         Collection<Double> valueCollection = smap.values();
319         assertEquals(0, valueCollection.size());
320 
321         // Regression for Harmony-1066
322         assertTrue(head instanceof Serializable);
323 
324         // Regression for ill-behaved collator
325         Collator c = new Collator() {
326             @Override
327             public int compare(String o1, String o2) {
328                 if (o1 == null) {
329                     return 0;
330                 }
331                 return o1.compareTo(o2);
332             }
333 
334             @Override
335             public CollationKey getCollationKey(String string) {
336                 return null;
337             }
338 
339             @Override
340             public int hashCode() {
341                 return 0;
342             }
343         };
344 
345         TreeMap<String, String> treemap = new TreeMap<String, String>(c);
346         assertEquals(0, treemap.headMap(null).size());
347 
348         treemap = new TreeMap();
349         SortedMap<String, String> headMap = treemap.headMap("100");
350         headMap.headMap("100");
351 
352         SortedMap<Integer, Integer> intMap, sub;
353         int size = 16;
354         intMap = new TreeMap<Integer, Integer>();
355         for (int i = 0; i < size; i++) {
356             intMap.put(i, i);
357         }
358         sub = intMap.headMap(-1);
359         assertEquals("size should be zero", sub.size(), 0);
360         assertTrue("submap should be empty", sub.isEmpty());
361         try {
362             sub.firstKey();
363             fail("java.util.NoSuchElementException should be thrown");
364         } catch (java.util.NoSuchElementException e) {
365         }
366 
367         TreeMap t = new TreeMap();
368         try {
369             SortedMap th = t.headMap(null);
370             fail("Should throw a NullPointerException");
371         } catch (NullPointerException npe) {
372             // expected
373         }
374 
375         try {
376             sub.lastKey();
377             fail("java.util.NoSuchElementException should be thrown");
378         } catch (java.util.NoSuchElementException e) {
379         }
380 
381         size = 256;
382         intMap = new TreeMap<Integer, Integer>();
383         for (int i = 0; i < size; i++) {
384             intMap.put(i, i);
385         }
386         sub = intMap.headMap(-1);
387         assertEquals("size should be zero", sub.size(), 0);
388         assertTrue("submap should be empty", sub.isEmpty());
389         try {
390             sub.firstKey();
391             fail("java.util.NoSuchElementException should be thrown");
392         } catch (java.util.NoSuchElementException e) {
393         }
394 
395         try {
396             sub.lastKey();
397             fail("java.util.NoSuchElementException should be thrown");
398         } catch (java.util.NoSuchElementException e) {
399         }
400 
401     }
402 
403     /**
404      * java.util.TreeMap#keySet()
405      */
test_keySet()406     public void test_keySet() {
407         // Test for method java.util.Set java.util.TreeMap.keySet()
408         Set ks = tm.keySet();
409         assertTrue("Returned set of incorrect size",
410                 ks.size() == objArray.length);
411         for (int i = 0; i < tm.size(); i++) {
412             assertTrue("Returned set is missing keys", ks.contains(new Integer(
413                     i).toString()));
414         }
415     }
416 
417     /**
418      * java.util.TreeMap#lastKey()
419      */
test_lastKey()420     public void test_lastKey() {
421         // Test for method java.lang.Object java.util.TreeMap.lastKey()
422         assertTrue("Returned incorrect last key", tm.lastKey().equals(
423                 objArray[objArray.length - 1].toString()));
424         assertNotSame(objArray[objArray.length - 1].toString(), tm.lastKey());
425         assertEquals(objArray[objArray.length - 2].toString(), tm
426                 .headMap("999").lastKey());
427         assertEquals(objArray[objArray.length - 1].toString(), tm
428                 .tailMap("123").lastKey());
429         assertEquals(objArray[objArray.length - 2].toString(), tm.subMap("99",
430                 "999").lastKey());
431     }
432 
test_lastKey_after_subMap()433     public void test_lastKey_after_subMap() {
434         TreeMap<String, String> tm = new TreeMap<String, String>();
435         tm.put("001", "VAL001");
436         tm.put("003", "VAL003");
437         tm.put("002", "VAL002");
438         SortedMap<String, String> sm = tm;
439         String firstKey = (String) sm.firstKey();
440         String lastKey = "";
441         for (int i = 1; i <= tm.size(); i++) {
442             try {
443                 lastKey = (String) sm.lastKey();
444             } catch (NoSuchElementException excep) {
445                 fail("NoSuchElementException thrown when there are elements in the map");
446             }
447             sm = sm.subMap(firstKey, lastKey);
448         }
449     }
450 
451     /**
452      * java.util.TreeMap#put(java.lang.Object, java.lang.Object)
453      */
test_remove_throwsWhenNotComparable()454     public void test_remove_throwsWhenNotComparable() {
455         // Test for method java.lang.Object
456         // java.util.TreeMap.put(java.lang.Object, java.lang.Object)
457         Object o = new Object();
458         tm = new TreeMap();
459         try {
460             tm.remove(o);
461             fail("should throw ClassCastException");
462         } catch (ClassCastException e) {
463             //expected
464         }
465     }
466 
467     /**
468      * java.util.TreeMap#putAll(java.util.Map)
469      */
test_putAllLjava_util_Map()470     public void test_putAllLjava_util_Map() {
471         // Test for method void java.util.TreeMap.putAll(java.util.Map)
472         TreeMap x = new TreeMap();
473         x.putAll(tm);
474         assertTrue("Map incorrect size after put", x.size() == tm.size());
475         for (Object element : objArray) {
476             assertTrue("Failed to put all elements", x.get(element.toString())
477                     .equals(element));
478         }
479     }
480 
481     /**
482      * java.util.TreeMap#remove(java.lang.Object)
483      */
test_removeLjava_lang_Object()484     public void test_removeLjava_lang_Object() {
485         // Test for method java.lang.Object
486         // java.util.TreeMap.remove(java.lang.Object)
487         tm.remove("990");
488         assertTrue("Failed to remove mapping", !tm.containsKey("990"));
489 
490     }
491 
492     /**
493      * java.util.TreeMap#size()
494      */
test_size()495     public void test_size() {
496         // Test for method int java.util.TreeMap.size()
497         assertEquals("Returned incorrect size", 1000, tm.size());
498         assertEquals("Returned incorrect size", 447, tm.headMap("500").size());
499         assertEquals("Returned incorrect size", 1000, tm.headMap("null").size());
500         assertEquals("Returned incorrect size", 0, tm.headMap("").size());
501         assertEquals("Returned incorrect size", 448, tm.headMap("500a").size());
502         assertEquals("Returned incorrect size", 553, tm.tailMap("500").size());
503         assertEquals("Returned incorrect size", 0, tm.tailMap("null").size());
504         assertEquals("Returned incorrect size", 1000, tm.tailMap("").size());
505         assertEquals("Returned incorrect size", 552, tm.tailMap("500a").size());
506         assertEquals("Returned incorrect size", 111, tm.subMap("500", "600")
507                 .size());
508         try {
509             tm.subMap("null", "600");
510             fail("Should throw an IllegalArgumentException");
511         } catch (IllegalArgumentException e) {
512             // expected
513         }
514         assertEquals("Returned incorrect size", 1000, tm.subMap("", "null")
515                 .size());
516     }
517 
518     /**
519      * java.util.TreeMap#subMap(java.lang.Object, java.lang.Object)
520      */
test_subMapLjava_lang_ObjectLjava_lang_Object()521     public void test_subMapLjava_lang_ObjectLjava_lang_Object() {
522         // Test for method java.util.SortedMap
523         // java.util.TreeMap.subMap(java.lang.Object, java.lang.Object)
524         SortedMap subMap = tm.subMap(objArray[100].toString(), objArray[109]
525                 .toString());
526         assertEquals("subMap is of incorrect size", 9, subMap.size());
527         for (int counter = 100; counter < 109; counter++) {
528             assertTrue("SubMap contains incorrect elements", subMap.get(
529                     objArray[counter].toString()).equals(objArray[counter]));
530         }
531 
532         try {
533             tm.subMap(objArray[9].toString(), objArray[1].toString());
534             fail("end key less than start key should throw IllegalArgumentException");
535         } catch (IllegalArgumentException e) {
536             // Expected
537         }
538 
539         // Regression for Harmony-1161
540         TreeMap<String, String> treeMapWithNull = new TreeMap<String, String>(
541                 new MockComparatorNullTolerable());
542         treeMapWithNull.put("key1", "value1"); //$NON-NLS-1$ //$NON-NLS-2$
543         treeMapWithNull.put(null, "value2"); //$NON-NLS-1$
544         SortedMap<String, String> subMapWithNull = treeMapWithNull.subMap(null,
545                 "key1"); //$NON-NLS-1$
546         assertEquals("Size of subMap should be 1:", 1, subMapWithNull.size()); //$NON-NLS-1$
547 
548         // Regression test for typo in lastKey method
549         SortedMap<String, String> map = new TreeMap<String, String>();
550         map.put("1", "one"); //$NON-NLS-1$ //$NON-NLS-2$
551         map.put("2", "two"); //$NON-NLS-1$ //$NON-NLS-2$
552         map.put("3", "three"); //$NON-NLS-1$ //$NON-NLS-2$
553         assertEquals("3", map.lastKey());
554         SortedMap<String, String> sub = map.subMap("1", "3"); //$NON-NLS-1$ //$NON-NLS-2$
555         assertEquals("2", sub.lastKey()); //$NON-NLS-1$
556 
557         // NOTE: The contract of this method allows us to throw either
558         // an NPE or a class cast exception.
559         TreeMap t = new TreeMap();
560         try {
561             t.subMap(null, new Object());
562             fail("Should throw a ClassCastException");
563         } catch (ClassCastException cce) {
564             // expected
565         } catch (NullPointerException npe) {
566             // expected
567         }
568     }
569 
570 
571     /**
572      * java.util.TreeMap#subMap(java.lang.Object, java.lang.Object)
573      */
test_subMap_Iterator()574     public void test_subMap_Iterator() {
575         TreeMap<String, String> map = new TreeMap<String, String>();
576 
577         String[] keys = { "1", "2", "3" };
578         String[] values = { "one", "two", "three" };
579         for (int i = 0; i < keys.length; i++) {
580             map.put(keys[i], values[i]);
581         }
582 
583         assertEquals(3, map.size());
584 
585         Map subMap = map.subMap("", "test");
586         assertEquals(3, subMap.size());
587 
588         Set entrySet = subMap.entrySet();
589         Iterator iter = entrySet.iterator();
590         int size = 0;
591         while (iter.hasNext()) {
592             Map.Entry<String, String> entry = (Map.Entry<String, String>) iter
593                     .next();
594             assertTrue(map.containsKey(entry.getKey()));
595             assertTrue(map.containsValue(entry.getValue()));
596             size++;
597         }
598         assertEquals(map.size(), size);
599 
600         Set<String> keySet = subMap.keySet();
601         iter = keySet.iterator();
602         size = 0;
603         while (iter.hasNext()) {
604             String key = (String) iter.next();
605             assertTrue(map.containsKey(key));
606             size++;
607         }
608         assertEquals(map.size(), size);
609     }
610 
611 
612     /**
613      * java.util.TreeMap#tailMap(java.lang.Object)
614      */
test_tailMapLjava_lang_Object()615     public void test_tailMapLjava_lang_Object() {
616         // Test for method java.util.SortedMap
617         // java.util.TreeMap.tailMap(java.lang.Object)
618         Map tail = tm.tailMap(objArray[900].toString());
619         assertTrue("Returned map of incorrect size : " + tail.size(), tail
620                 .size() == (objArray.length - 900) + 9);
621         for (int i = 900; i < objArray.length; i++) {
622             assertTrue("Map contains incorrect entries", tail
623                     .containsValue(objArray[i]));
624         }
625 
626         // Regression for Harmony-1066
627         assertTrue(tail instanceof Serializable);
628 
629         SortedMap<Integer, Integer> intMap, sub;
630         int size = 16;
631         intMap = new TreeMap<Integer, Integer>();
632         for (int i = 0; i < size; i++) {
633             intMap.put(i, i);
634         }
635         sub = intMap.tailMap(size);
636         assertEquals("size should be zero", sub.size(), 0);
637         assertTrue("submap should be empty", sub.isEmpty());
638         try {
639             sub.firstKey();
640             fail("java.util.NoSuchElementException should be thrown");
641         } catch (java.util.NoSuchElementException e) {
642         }
643 
644         TreeMap t = new TreeMap();
645         try {
646             SortedMap th = t.tailMap(null);
647             fail("Should throw a NullPointerException");
648         } catch (NullPointerException npe) {
649             // expected
650         }
651 
652         try {
653             sub.lastKey();
654             fail("java.util.NoSuchElementException should be thrown");
655         } catch (java.util.NoSuchElementException e) {
656         }
657 
658         size = 256;
659         intMap = new TreeMap<Integer, Integer>();
660         for (int i = 0; i < size; i++) {
661             intMap.put(i, i);
662         }
663         sub = intMap.tailMap(size);
664         assertEquals("size should be zero", sub.size(), 0);
665         assertTrue("submap should be empty", sub.isEmpty());
666         try {
667             sub.firstKey();
668             fail("java.util.NoSuchElementException should be thrown");
669         } catch (java.util.NoSuchElementException e) {
670         }
671 
672         try {
673             sub.lastKey();
674             fail("java.util.NoSuchElementException should be thrown");
675         } catch (java.util.NoSuchElementException e) {
676         }
677 
678     }
679 
680     /**
681      * java.util.TreeMap#values()
682      */
test_values()683     public void test_values() {
684         // Test for method java.util.Collection java.util.TreeMap.values()
685         Collection vals = tm.values();
686         vals.iterator();
687         assertTrue("Returned collection of incorrect size",
688                 vals.size() == objArray.length);
689         for (Object element : objArray) {
690             assertTrue("Collection contains incorrect elements", vals
691                     .contains(element));
692         }
693         assertEquals(1000, vals.size());
694         int j = 0;
695         for (Iterator iter = vals.iterator(); iter.hasNext(); ) {
696             Object element = (Object) iter.next();
697             j++;
698         }
699         assertEquals(1000, j);
700 
701         vals = tm.descendingMap().values();
702         vals.iterator();
703         assertTrue("Returned collection of incorrect size",
704                 vals.size() == objArray.length);
705         for (Object element : objArray) {
706             assertTrue("Collection contains incorrect elements", vals
707                     .contains(element));
708         }
709         assertEquals(1000, vals.size());
710         j = 0;
711         for (Iterator iter = vals.iterator(); iter.hasNext(); ) {
712             Object element = (Object) iter.next();
713             j++;
714         }
715         assertEquals(1000, j);
716 
717         TreeMap myTreeMap = new TreeMap();
718         for (int i = 0; i < 100; i++) {
719             myTreeMap.put(objArray[i], objArray[i]);
720         }
721         Collection values = myTreeMap.values();
722         new Support_UnmodifiableCollectionTest(
723                 "Test Returned Collection From TreeMap.values()", values)
724                 .runTest();
725         values.remove(new Integer(0));
726         assertTrue(
727                 "Removing from the values collection should remove from the original map",
728                 !myTreeMap.containsValue(new Integer(0)));
729         assertEquals(99, values.size());
730         j = 0;
731         for (Iterator iter = values.iterator(); iter.hasNext(); ) {
732             Object element = (Object) iter.next();
733             j++;
734         }
735         assertEquals(99, j);
736 
737     }
738 
739     /**
740      * java.util.TreeMap the values() method in sub maps
741      */
test_subMap_values_size()742     public void test_subMap_values_size() {
743         TreeMap myTreeMap = new TreeMap();
744         for (int i = 0; i < 1000; i++) {
745             myTreeMap.put(i, objArray[i]);
746         }
747         // Test for method values() in subMaps
748         Collection vals = myTreeMap.subMap(200, 400).values();
749         assertTrue("Returned collection of incorrect size", vals.size() == 200);
750         for (int i = 200; i < 400; i++) {
751             assertTrue("Collection contains incorrect elements" + i, vals
752                     .contains(objArray[i]));
753         }
754         assertEquals(200, vals.toArray().length);
755         vals.remove(objArray[300]);
756         assertTrue(
757                 "Removing from the values collection should remove from the original map",
758                 !myTreeMap.containsValue(objArray[300]));
759         assertTrue("Returned collection of incorrect size", vals.size() == 199);
760         assertEquals(199, vals.toArray().length);
761 
762         myTreeMap.put(300, objArray[300]);
763         // Test for method values() in subMaps
764         vals = myTreeMap.headMap(400).values();
765         assertEquals("Returned collection of incorrect size", vals.size(), 400);
766         for (int i = 0; i < 400; i++) {
767             assertTrue("Collection contains incorrect elements " + i, vals
768                     .contains(objArray[i]));
769         }
770         assertEquals(400, vals.toArray().length);
771         vals.remove(objArray[300]);
772         assertTrue(
773                 "Removing from the values collection should remove from the original map",
774                 !myTreeMap.containsValue(objArray[300]));
775         assertTrue("Returned collection of incorrect size", vals.size() == 399);
776         assertEquals(399, vals.toArray().length);
777 
778         myTreeMap.put(300, objArray[300]);
779         // Test for method values() in subMaps
780         vals = myTreeMap.tailMap(400).values();
781         assertEquals("Returned collection of incorrect size", vals.size(), 600);
782         for (int i = 400; i < 1000; i++) {
783             assertTrue("Collection contains incorrect elements " + i, vals
784                     .contains(objArray[i]));
785         }
786         assertEquals(600, vals.toArray().length);
787         vals.remove(objArray[600]);
788         assertTrue(
789                 "Removing from the values collection should remove from the original map",
790                 !myTreeMap.containsValue(objArray[600]));
791         assertTrue("Returned collection of incorrect size", vals.size() == 599);
792         assertEquals(599, vals.toArray().length);
793 
794 
795         myTreeMap.put(600, objArray[600]);
796         // Test for method values() in subMaps
797         vals = myTreeMap.descendingMap().headMap(400).values();
798         assertEquals("Returned collection of incorrect size", vals.size(), 599);
799         for (int i = 401; i < 1000; i++) {
800             assertTrue("Collection contains incorrect elements " + i, vals
801                     .contains(objArray[i]));
802         }
803         assertEquals(599, vals.toArray().length);
804         vals.remove(objArray[600]);
805         assertTrue(
806                 "Removing from the values collection should remove from the original map",
807                 !myTreeMap.containsValue(objArray[600]));
808         assertTrue("Returned collection of incorrect size", vals.size() == 598);
809         assertEquals(598, vals.toArray().length);
810 
811         myTreeMap.put(600, objArray[600]);
812         // Test for method values() in subMaps
813         vals = myTreeMap.descendingMap().tailMap(400).values();
814         assertEquals("Returned collection of incorrect size", vals.size(), 401);
815         for (int i = 0; i <= 400; i++) {
816             assertTrue("Collection contains incorrect elements " + i, vals
817                     .contains(objArray[i]));
818         }
819         assertEquals(401, vals.toArray().length);
820         vals.remove(objArray[300]);
821         assertTrue(
822                 "Removing from the values collection should remove from the original map",
823                 !myTreeMap.containsValue(objArray[300]));
824         assertTrue("Returned collection of incorrect size", vals.size() == 400);
825         assertEquals(400, vals.toArray().length);
826 
827     }
828 
829     /**
830      * java.util.TreeMap#subMap()
831      */
test_subMap_Iterator2()832     public void test_subMap_Iterator2() {
833         TreeMap<String, String> map = new TreeMap<String, String>();
834 
835         String[] keys = { "1", "2", "3" };
836         String[] values = { "one", "two", "three" };
837         for (int i = 0; i < keys.length; i++) {
838             map.put(keys[i], values[i]);
839         }
840 
841         assertEquals(3, map.size());
842 
843         Map subMap = map.subMap("", "test");
844         assertEquals(3, subMap.size());
845 
846         Set entrySet = subMap.entrySet();
847         Iterator iter = entrySet.iterator();
848         int size = 0;
849         while (iter.hasNext()) {
850             Map.Entry<String, String> entry = (Map.Entry<String, String>) iter
851                     .next();
852             assertTrue(map.containsKey(entry.getKey()));
853             assertTrue(map.containsValue(entry.getValue()));
854             size++;
855         }
856         assertEquals(map.size(), size);
857 
858         Set<String> keySet = subMap.keySet();
859         iter = keySet.iterator();
860         size = 0;
861         while (iter.hasNext()) {
862             String key = (String) iter.next();
863             assertTrue(map.containsKey(key));
864             size++;
865         }
866         assertEquals(map.size(), size);
867     }
868 
869     /**
870      * java.util.TreeMap#SerializationTest()
871      */
872     // Regression for Harmony-1066
test_SubMap_Serializable()873     public void test_SubMap_Serializable() throws Exception {
874         TreeMap<Integer, Double> map = new TreeMap<Integer, Double>();
875         map.put(1, 2.1);
876         map.put(2, 3.1);
877         map.put(3, 4.5);
878         map.put(7, 21.3);
879         SortedMap<Integer, Double> headMap = map.headMap(3);
880         assertTrue(headMap instanceof Serializable);
881         assertFalse(headMap instanceof TreeMap);
882         assertTrue(headMap instanceof SortedMap);
883 
884         assertFalse(headMap.entrySet() instanceof Serializable);
885         assertFalse(headMap.keySet() instanceof Serializable);
886         assertFalse(headMap.values() instanceof Serializable);
887 
888         // This assertion will fail on RI. This is a bug of RI.
889         SerializationTest.verifySelf(headMap);
890     }
891 
892     /**
893      * {@link java.util.TreeMap#firstEntry()}
894      */
test_firstEntry()895     public void test_firstEntry() throws Exception {
896         Integer testint = new Integer(-1);
897         Integer testint10000 = new Integer(-10000);
898         Integer testint9999 = new Integer(-9999);
899         assertEquals(objArray[0].toString(), tm.firstEntry().getKey());
900         assertEquals(objArray[0], tm.firstEntry().getValue());
901         tm.put(testint.toString(), testint);
902         assertEquals(testint.toString(), tm.firstEntry().getKey());
903         assertEquals(testint, tm.firstEntry().getValue());
904         tm.put(testint10000.toString(), testint10000);
905         assertEquals(testint.toString(), tm.firstEntry().getKey());
906         assertEquals(testint, tm.firstEntry().getValue());
907         tm.put(testint9999.toString(), testint9999);
908         assertEquals(testint.toString(), tm.firstEntry().getKey());
909         Entry entry = tm.firstEntry();
910         assertEquals(testint, entry.getValue());
911         assertEntry(entry);
912         tm.clear();
913         assertNull(tm.firstEntry());
914     }
915 
916     /**
917      * {@link java.util.TreeMap#lastEntry()
918      */
test_lastEntry()919     public void test_lastEntry() throws Exception {
920         Integer testint10000 = new Integer(10000);
921         Integer testint9999 = new Integer(9999);
922         assertEquals(objArray[999].toString(), tm.lastEntry().getKey());
923         assertEquals(objArray[999], tm.lastEntry().getValue());
924         tm.put(testint10000.toString(), testint10000);
925         assertEquals(objArray[999].toString(), tm.lastEntry().getKey());
926         assertEquals(objArray[999], tm.lastEntry().getValue());
927         tm.put(testint9999.toString(), testint9999);
928         assertEquals(testint9999.toString(), tm.lastEntry().getKey());
929         Entry entry = tm.lastEntry();
930         assertEquals(testint9999, entry.getValue());
931         assertEntry(entry);
932         tm.clear();
933         assertNull(tm.lastEntry());
934     }
935 
936     /**
937      * {@link java.util.TreeMap#pollFirstEntry()
938      */
test_pollFirstEntry()939     public void test_pollFirstEntry() throws Exception {
940         Integer testint = new Integer(-1);
941         Integer testint10000 = new Integer(-10000);
942         Integer testint9999 = new Integer(-9999);
943         assertEquals(objArray[0].toString(), tm.pollFirstEntry().getKey());
944         assertEquals(objArray[1], tm.pollFirstEntry().getValue());
945         assertEquals(objArray[10], tm.pollFirstEntry().getValue());
946         tm.put(testint.toString(), testint);
947         tm.put(testint10000.toString(), testint10000);
948         assertEquals(testint.toString(), tm.pollFirstEntry().getKey());
949         assertEquals(testint10000, tm.pollFirstEntry().getValue());
950         tm.put(testint9999.toString(), testint9999);
951         assertEquals(testint9999.toString(), tm.pollFirstEntry().getKey());
952         Entry entry = tm.pollFirstEntry();
953         assertEntry(entry);
954         assertEquals(objArray[100], entry.getValue());
955         tm.clear();
956         assertNull(tm.pollFirstEntry());
957     }
958 
959     /**
960      * {@link java.util.TreeMap#pollLastEntry()
961      */
test_pollLastEntry()962     public void test_pollLastEntry() throws Exception {
963         Integer testint10000 = new Integer(10000);
964         Integer testint9999 = new Integer(9999);
965         assertEquals(objArray[999].toString(), tm.pollLastEntry().getKey());
966         assertEquals(objArray[998], tm.pollLastEntry().getValue());
967         assertEquals(objArray[997], tm.pollLastEntry().getValue());
968         tm.put(testint10000.toString(), testint10000);
969         assertEquals(objArray[996], tm.pollLastEntry().getValue());
970         tm.put(testint9999.toString(), testint9999);
971         assertEquals(testint9999.toString(), tm.pollLastEntry().getKey());
972         Entry entry = tm.pollLastEntry();
973         assertEquals(objArray[995], entry.getValue());
974         assertEntry(entry);
975         tm.clear();
976         assertNull(tm.pollLastEntry());
977     }
978 
979     /**
980      * {@link java.util.TreeMap#lowerEntry(Object)
981      */
test_lowerEntry()982     public void test_lowerEntry() throws Exception {
983         Integer testint10000 = new Integer(10000);
984         Integer testint9999 = new Integer(9999);
985         assertEquals(objArray[999], tm.lowerEntry(testint9999.toString())
986                 .getValue());
987         assertEquals(objArray[100], tm.lowerEntry(testint10000.toString())
988                 .getValue());
989         tm.put(testint10000.toString(), testint10000);
990         tm.put(testint9999.toString(), testint9999);
991         assertEquals(objArray[999], tm.lowerEntry(testint9999.toString())
992                 .getValue());
993         Entry entry = tm.lowerEntry(testint10000.toString());
994         assertEquals(objArray[100], entry.getValue());
995         assertEntry(entry);
996         try {
997             tm.lowerEntry(testint10000);
998             fail("should throw ClassCastException");
999         } catch (ClassCastException e) {
1000             // expected
1001         }
1002         try {
1003             tm.lowerEntry(null);
1004             fail("should throw NullPointerException");
1005         } catch (NullPointerException e) {
1006             // expected
1007         }
1008         tm.clear();
1009         assertNull(tm.lowerEntry(testint9999.toString()));
1010     }
1011 
1012     /**
1013      * {@link java.util.TreeMap#lowerKey(Object)
1014      */
test_lowerKey()1015     public void test_lowerKey() throws Exception {
1016         Integer testint10000 = new Integer(10000);
1017         Integer testint9999 = new Integer(9999);
1018         assertEquals(objArray[999].toString(), tm.lowerKey(testint9999
1019                 .toString()));
1020         assertEquals(objArray[100].toString(), tm.lowerKey(testint10000
1021                 .toString()));
1022         tm.put(testint10000.toString(), testint10000);
1023         tm.put(testint9999.toString(), testint9999);
1024         assertEquals(objArray[999].toString(), tm.lowerKey(testint9999
1025                 .toString()));
1026         assertEquals(objArray[100].toString(), tm.lowerKey(testint10000
1027                 .toString()));
1028         try {
1029             tm.lowerKey(testint10000);
1030             fail("should throw ClassCastException");
1031         } catch (ClassCastException e) {
1032             // expected
1033         }
1034         try {
1035             tm.lowerKey(null);
1036             fail("should throw NullPointerException");
1037         } catch (NullPointerException e) {
1038             // expected
1039         }
1040         tm.clear();
1041         assertNull(tm.lowerKey(testint9999.toString()));
1042     }
1043 
1044     /**
1045      * {@link java.util.TreeMap#floorEntry(Object)
1046      */
test_floorEntry()1047     public void test_floorEntry() throws Exception {
1048         Integer testint10000 = new Integer(10000);
1049         Integer testint9999 = new Integer(9999);
1050         assertEquals(objArray[999], tm.floorEntry(testint9999.toString())
1051                 .getValue());
1052         assertEquals(objArray[100], tm.floorEntry(testint10000.toString())
1053                 .getValue());
1054         tm.put(testint10000.toString(), testint10000);
1055         tm.put(testint9999.toString(), testint9999);
1056         assertEquals(testint9999, tm.floorEntry(testint9999.toString())
1057                 .getValue());
1058         Entry entry = tm.floorEntry(testint10000.toString());
1059         assertEquals(testint10000, entry.getValue());
1060         assertEntry(entry);
1061         try {
1062             tm.floorEntry(testint10000);
1063             fail("should throw ClassCastException");
1064         } catch (ClassCastException e) {
1065             // expected
1066         }
1067         try {
1068             tm.floorEntry(null);
1069             fail("should throw NullPointerException");
1070         } catch (NullPointerException e) {
1071             // expected
1072         }
1073         tm.clear();
1074         assertNull(tm.floorEntry(testint9999.toString()));
1075     }
1076 
1077     /**
1078      * {@link java.util.TreeMap#floorKey(Object)
1079      */
test_floorKey()1080     public void test_floorKey() throws Exception {
1081         Integer testint10000 = new Integer(10000);
1082         Integer testint9999 = new Integer(9999);
1083         assertEquals(objArray[999].toString(), tm.floorKey(testint9999
1084                 .toString()));
1085         assertEquals(objArray[100].toString(), tm.floorKey(testint10000
1086                 .toString()));
1087         tm.put(testint10000.toString(), testint10000);
1088         tm.put(testint9999.toString(), testint9999);
1089         assertEquals(testint9999.toString(), tm
1090                 .floorKey(testint9999.toString()));
1091         assertEquals(testint10000.toString(), tm.floorKey(testint10000
1092                 .toString()));
1093         try {
1094             tm.floorKey(testint10000);
1095             fail("should throw ClassCastException");
1096         } catch (ClassCastException e) {
1097             // expected
1098         }
1099         try {
1100             tm.floorKey(null);
1101             fail("should throw NullPointerException");
1102         } catch (NullPointerException e) {
1103             // expected
1104         }
1105         tm.clear();
1106         assertNull(tm.floorKey(testint9999.toString()));
1107     }
1108 
1109     /**
1110      * {@link java.util.TreeMap#ceilingEntry(Object)
1111      */
test_ceilingEntry()1112     public void test_ceilingEntry() throws Exception {
1113         Integer testint100 = new Integer(100);
1114         Integer testint = new Integer(-1);
1115         assertEquals(objArray[0], tm.ceilingEntry(testint.toString())
1116                 .getValue());
1117         assertEquals(objArray[100], tm.ceilingEntry(testint100.toString())
1118                 .getValue());
1119         tm.put(testint.toString(), testint);
1120         tm.put(testint100.toString(), testint);
1121         assertEquals(testint, tm.ceilingEntry(testint.toString()).getValue());
1122         Entry entry = tm.ceilingEntry(testint100.toString());
1123         assertEquals(testint, entry.getValue());
1124         assertEntry(entry);
1125         try {
1126             tm.ceilingEntry(testint100);
1127             fail("should throw ClassCastException");
1128         } catch (ClassCastException e) {
1129             // expected
1130         }
1131         try {
1132             tm.ceilingEntry(null);
1133             fail("should throw NullPointerException");
1134         } catch (NullPointerException e) {
1135             // expected
1136         }
1137         tm.clear();
1138         assertNull(tm.ceilingEntry(testint.toString()));
1139     }
1140 
1141     /**
1142      * {@link java.util.TreeMap#ceilingKey(Object)
1143      */
test_ceilingKey()1144     public void test_ceilingKey() throws Exception {
1145         Integer testint100 = new Integer(100);
1146         Integer testint = new Integer(-1);
1147         assertEquals(objArray[0].toString(), tm.ceilingKey(testint.toString()));
1148         assertEquals(objArray[100].toString(), tm.ceilingKey(testint100
1149                 .toString()));
1150         tm.put(testint.toString(), testint);
1151         tm.put(testint100.toString(), testint);
1152         assertEquals(testint.toString(), tm.ceilingKey(testint.toString()));
1153         assertEquals(testint100.toString(), tm
1154                 .ceilingKey(testint100.toString()));
1155         try {
1156             tm.ceilingKey(testint100);
1157             fail("should throw ClassCastException");
1158         } catch (ClassCastException e) {
1159             // expected
1160         }
1161         try {
1162             tm.ceilingKey(null);
1163             fail("should throw NullPointerException");
1164         } catch (NullPointerException e) {
1165             // expected
1166         }
1167         tm.clear();
1168         assertNull(tm.ceilingKey(testint.toString()));
1169     }
1170 
1171     /**
1172      * {@link java.util.TreeMap#higherEntry(Object)
1173      */
test_higherEntry()1174     public void test_higherEntry() throws Exception {
1175         Integer testint9999 = new Integer(9999);
1176         Integer testint10000 = new Integer(10000);
1177         Integer testint100 = new Integer(100);
1178         Integer testint = new Integer(-1);
1179         assertEquals(objArray[0], tm.higherEntry(testint.toString()).getValue());
1180         assertEquals(objArray[101], tm.higherEntry(testint100.toString())
1181                 .getValue());
1182         assertEquals(objArray[101], tm.higherEntry(testint10000.toString())
1183                 .getValue());
1184         tm.put(testint9999.toString(), testint);
1185         tm.put(testint100.toString(), testint);
1186         tm.put(testint10000.toString(), testint);
1187         assertEquals(objArray[0], tm.higherEntry(testint.toString()).getValue());
1188         assertEquals(testint, tm.higherEntry(testint100.toString()).getValue());
1189         Entry entry = tm.higherEntry(testint10000.toString());
1190         assertEquals(objArray[101], entry.getValue());
1191         assertEntry(entry);
1192         assertNull(tm.higherEntry(testint9999.toString()));
1193         try {
1194             tm.higherEntry(testint100);
1195             fail("should throw ClassCastException");
1196         } catch (ClassCastException e) {
1197             // expected
1198         }
1199         try {
1200             tm.higherEntry(null);
1201             fail("should throw NullPointerException");
1202         } catch (NullPointerException e) {
1203             // expected
1204         }
1205         tm.clear();
1206         assertNull(tm.higherEntry(testint.toString()));
1207     }
1208 
1209     /**
1210      * {@link java.util.TreeMap#higherKey(Object)
1211      */
test_higherKey()1212     public void test_higherKey() throws Exception {
1213         Integer testint9999 = new Integer(9999);
1214         Integer testint10000 = new Integer(10000);
1215         Integer testint100 = new Integer(100);
1216         Integer testint = new Integer(-1);
1217         assertEquals(objArray[0].toString(), tm.higherKey(testint.toString()));
1218         assertEquals(objArray[101].toString(), tm.higherKey(testint100
1219                 .toString()));
1220         assertEquals(objArray[101].toString(), tm.higherKey(testint10000
1221                 .toString()));
1222         tm.put(testint9999.toString(), testint);
1223         tm.put(testint100.toString(), testint);
1224         tm.put(testint10000.toString(), testint);
1225         assertEquals(objArray[0].toString(), tm.higherKey(testint.toString()));
1226         assertEquals(testint10000.toString(), tm.higherKey(testint100
1227                 .toString()));
1228         assertEquals(objArray[101].toString(), tm.higherKey(testint10000
1229                 .toString()));
1230         assertNull(tm.higherKey(testint9999.toString()));
1231         try {
1232             tm.higherKey(testint100);
1233             fail("should throw ClassCastException");
1234         } catch (ClassCastException e) {
1235             // expected
1236         }
1237         try {
1238             tm.higherKey(null);
1239             fail("should throw NullPointerException");
1240         } catch (NullPointerException e) {
1241             // expected
1242         }
1243         tm.clear();
1244         assertNull(tm.higherKey(testint.toString()));
1245     }
1246 
test_navigableKeySet()1247     public void test_navigableKeySet() throws Exception {
1248         Integer testint9999 = new Integer(9999);
1249         Integer testint10000 = new Integer(10000);
1250         Integer testint100 = new Integer(100);
1251         Integer testint0 = new Integer(0);
1252         NavigableSet set = tm.navigableKeySet();
1253         assertFalse(set.contains(testint9999.toString()));
1254         tm.put(testint9999.toString(), testint9999);
1255         assertTrue(set.contains(testint9999.toString()));
1256         tm.remove(testint9999.toString());
1257         assertFalse(set.contains(testint9999.toString()));
1258         try {
1259             set.add(new Object());
1260             fail("should throw UnsupportedOperationException");
1261         } catch (UnsupportedOperationException e) {
1262             // expected
1263         }
1264         try {
1265             set.add(null);
1266             fail("should throw UnsupportedOperationException");
1267         } catch (UnsupportedOperationException e) {
1268             // expected
1269         }
1270         try {
1271             set.addAll(null);
1272             fail("should throw UnsupportedOperationException");
1273         } catch (NullPointerException e) {
1274             // expected
1275         }
1276         Collection collection = new LinkedList();
1277         set.addAll(collection);
1278         try {
1279             collection.add(new Object());
1280             set.addAll(collection);
1281             fail("should throw UnsupportedOperationException");
1282         } catch (UnsupportedOperationException e) {
1283             // expected
1284         }
1285         set.remove(testint100.toString());
1286         assertFalse(tm.containsKey(testint100.toString()));
1287         assertTrue(tm.containsKey(testint0.toString()));
1288         Iterator iter = set.iterator();
1289         iter.next();
1290         iter.remove();
1291         assertFalse(tm.containsKey(testint0.toString()));
1292         collection.add(new Integer(200).toString());
1293         set.retainAll(collection);
1294         assertEquals(1, tm.size());
1295         set.removeAll(collection);
1296         assertEquals(0, tm.size());
1297         tm.put(testint10000.toString(), testint10000);
1298         assertEquals(1, tm.size());
1299         set.clear();
1300         assertEquals(0, tm.size());
1301     }
1302 
assertEntry(Entry entry)1303     private void assertEntry(Entry entry) {
1304         try {
1305             entry.setValue(new Object());
1306             fail("should throw UnsupportedOperationException");
1307         } catch (UnsupportedOperationException e) {
1308             // expected
1309         }
1310         assertEquals((entry.getKey() == null ? 0 : entry.getKey().hashCode())
1311                 ^ (entry.getValue() == null ? 0 : entry.getValue().hashCode()),
1312                 entry.hashCode());
1313         assertEquals(entry.toString(), entry.getKey() + "=" + entry.getValue());
1314     }
1315 
1316     /**
1317      * java.util.TreeMap#subMap(java.lang.Object, boolean,
1318      *java.lang.Object, boolean)
1319      */
test_subMapLjava_lang_ObjectZLjava_lang_ObjectZ()1320     public void test_subMapLjava_lang_ObjectZLjava_lang_ObjectZ() {
1321         // normal case
1322         SortedMap subMap = tm.subMap(objArray[100].toString(), true,
1323                 objArray[109].toString(), true);
1324         assertEquals("subMap is of incorrect size", 10, subMap.size());
1325         subMap = tm.subMap(objArray[100].toString(), true, objArray[109]
1326                 .toString(), false);
1327         assertEquals("subMap is of incorrect size", 9, subMap.size());
1328         for (int counter = 100; counter < 109; counter++) {
1329             assertTrue("SubMap contains incorrect elements", subMap.get(
1330                     objArray[counter].toString()).equals(objArray[counter]));
1331         }
1332         subMap = tm.subMap(objArray[100].toString(), false, objArray[109]
1333                 .toString(), true);
1334         assertEquals("subMap is of incorrect size", 9, subMap.size());
1335         assertNull(subMap.get(objArray[100].toString()));
1336 
1337         // Exceptions
1338         try {
1339             tm.subMap(objArray[9].toString(), true, objArray[1].toString(),
1340                     true);
1341             fail("should throw IllegalArgumentException");
1342         } catch (IllegalArgumentException e) {
1343             // expected
1344         }
1345         try {
1346             tm.subMap(objArray[9].toString(), false, objArray[1].toString(),
1347                     false);
1348             fail("should throw IllegalArgumentException");
1349         } catch (IllegalArgumentException e) {
1350             // expected
1351         }
1352         try {
1353             tm.subMap(null, true, null, true);
1354             fail("should throw NullPointerException");
1355         } catch (NullPointerException e) {
1356             // expected
1357         }
1358         try {
1359             tm.subMap(null, false, objArray[100], true);
1360             fail("should throw NullPointerException");
1361         } catch (NullPointerException e) {
1362             // expected
1363         }
1364         try {
1365             tm.subMap(new LinkedList(), false, objArray[100], true);
1366             fail("should throw ClassCastException");
1367         } catch (ClassCastException e) {
1368             // expected
1369         }
1370 
1371         // use integer elements to test
1372         TreeMap<Integer, String> treeMapInt = new TreeMap<Integer, String>();
1373         assertEquals(0, treeMapInt.subMap(new Integer(-1), true,
1374                 new Integer(100), true).size());
1375         for (int i = 0; i < 100; i++) {
1376             treeMapInt.put(new Integer(i), new Integer(i).toString());
1377         }
1378         SortedMap<Integer, String> result = treeMapInt.subMap(new Integer(-1),
1379                 true, new Integer(100), true);
1380         assertEquals(100, result.size());
1381         result.put(new Integer(-1), new Integer(-1).toString());
1382         assertEquals(101, result.size());
1383         assertEquals(101, treeMapInt.size());
1384         result = treeMapInt
1385                 .subMap(new Integer(50), true, new Integer(60), true);
1386         assertEquals(11, result.size());
1387         try {
1388             result.put(new Integer(-2), new Integer(-2).toString());
1389             fail("should throw IllegalArgumentException");
1390         } catch (IllegalArgumentException e) {
1391             // expected
1392         }
1393         assertEquals(11, result.size());
1394         treeMapInt.remove(new Integer(50));
1395         assertEquals(100, treeMapInt.size());
1396         assertEquals(10, result.size());
1397         result.remove(new Integer(60));
1398         assertEquals(99, treeMapInt.size());
1399         assertEquals(9, result.size());
1400         SortedMap<Integer, String> result2 = null;
1401         try {
1402             result2 = result.subMap(new Integer(-2), new Integer(100));
1403             fail("should throw IllegalArgumentException");
1404         } catch (IllegalArgumentException e) {
1405             // expected
1406         }
1407         result2 = result.subMap(new Integer(50), new Integer(60));
1408         assertEquals(9, result2.size());
1409 
1410         // sub map of sub map
1411         NavigableMap<Integer, Object> mapIntObj = new TreeMap<Integer, Object>();
1412         for (int i = 0; i < 10; ++i) {
1413             mapIntObj.put(i, new Object());
1414         }
1415         mapIntObj = mapIntObj.subMap(5, false, 9, true);
1416         assertEquals(4, mapIntObj.size());
1417         mapIntObj = mapIntObj.subMap(5, false, 9, true);
1418         assertEquals(4, mapIntObj.size());
1419         mapIntObj = mapIntObj.subMap(5, false, 6, false);
1420         assertEquals(0, mapIntObj.size());
1421 
1422         // a special comparator dealing with null key
1423         tm = new TreeMap(new Comparator() {
1424             public int compare(Object o1, Object o2) {
1425                 if (o1 == null) {
1426                     return -1;
1427                 }
1428                 if (o2 == null) {
1429                     return 1;
1430                 }
1431                 return ((String) o1).compareTo((String) o2);
1432             }
1433         });
1434         tm.put(null, -1);
1435         tm.put(new String("1st"), 1);
1436         tm.put(new String("2nd"), 2);
1437         tm.put(new String("3rd"), 3);
1438         SortedMap s = tm.subMap(null, "3rd");
1439         assertEquals(3, s.size());
1440         assertTrue(s.containsValue(-1));
1441         assertTrue(s.containsValue(1));
1442         assertTrue(s.containsValue(2));
1443         assertFalse(s.containsKey(null));
1444 
1445         s = tm.descendingMap();
1446         s = s.subMap("3rd", null);
1447         assertFalse(s.containsKey(null));
1448         assertTrue(s.containsKey("1st"));
1449         assertTrue(s.containsKey("2nd"));
1450         assertTrue(s.containsKey("3rd"));
1451     }
1452 
test_subMap_NullTolerableComparator()1453     public void test_subMap_NullTolerableComparator() {
1454         // Null Tolerable Comparator
1455         TreeMap<String, String> treeMapWithNull = new TreeMap<String, String>(
1456                 new MockComparatorNullTolerable());
1457         treeMapWithNull.put("key1", "value1"); //$NON-NLS-1$ //$NON-NLS-2$
1458         treeMapWithNull.put(null, "value2"); //$NON-NLS-1$
1459         SortedMap<String, String> subMapWithNull = treeMapWithNull.subMap(null,
1460                 true, "key1", true); //$NON-NLS-1$
1461 
1462         // RI fails here
1463         assertEquals("Size of subMap should be 2:", 2, subMapWithNull.size()); //$NON-NLS-1$
1464         assertEquals("value1", subMapWithNull.get("key1"));
1465         assertEquals("value2", subMapWithNull.get(null));
1466         treeMapWithNull.put("key0", "value2");
1467         treeMapWithNull.put("key3", "value3");
1468         treeMapWithNull.put("key4", "value4");
1469         treeMapWithNull.put("key5", "value5");
1470         treeMapWithNull.put("key6", "value6");
1471         assertEquals("Size of subMap should be 3:", 3, subMapWithNull.size()); //$NON-NLS-1$
1472         subMapWithNull = treeMapWithNull.subMap(null, false, "key1", true); //$NON-NLS-1$
1473         assertEquals("Size of subMap should be 2:", 2, subMapWithNull.size()); //$NON-NLS-1$
1474     }
1475 
1476 
1477     /**
1478      * java.util.TreeMap#headMap(java.lang.Object, boolea)
1479      */
test_headMapLjava_lang_ObjectZL()1480     public void test_headMapLjava_lang_ObjectZL() {
1481         // normal case
1482         SortedMap subMap = tm.headMap(objArray[100].toString(), true);
1483         assertEquals("subMap is of incorrect size", 4, subMap.size());
1484         subMap = tm.headMap(objArray[109].toString(), true);
1485         assertEquals("subMap is of incorrect size", 13, subMap.size());
1486         for (int counter = 100; counter < 109; counter++) {
1487             assertTrue("SubMap contains incorrect elements", subMap.get(
1488                     objArray[counter].toString()).equals(objArray[counter]));
1489         }
1490         subMap = tm.headMap(objArray[100].toString(), false);
1491         assertEquals("subMap is of incorrect size", 3, subMap.size());
1492         assertNull(subMap.get(objArray[100].toString()));
1493 
1494         // Exceptions
1495         assertEquals(0, tm.headMap("", true).size());
1496         assertEquals(0, tm.headMap("", false).size());
1497 
1498         try {
1499             tm.headMap(null, true);
1500             fail("should throw NullPointerException");
1501         } catch (NullPointerException e) {
1502             // expected
1503         }
1504         try {
1505             tm.headMap(null, false);
1506             fail("should throw NullPointerException");
1507         } catch (NullPointerException e) {
1508             // expected
1509         }
1510         try {
1511             tm.headMap(new Object(), true);
1512             fail("should throw ClassCastException");
1513         } catch (ClassCastException e) {
1514             // expected
1515         }
1516         try {
1517             tm.headMap(new Object(), false);
1518             fail("should throw ClassCastException");
1519         } catch (ClassCastException e) {
1520             // expected
1521         }
1522 
1523         // use integer elements to test
1524         TreeMap<Integer, String> treeMapInt = new TreeMap<Integer, String>();
1525         assertEquals(0, treeMapInt.headMap(new Integer(-1), true).size());
1526         for (int i = 0; i < 100; i++) {
1527             treeMapInt.put(new Integer(i), new Integer(i).toString());
1528         }
1529         SortedMap<Integer, String> result = treeMapInt
1530                 .headMap(new Integer(101));
1531         assertEquals(100, result.size());
1532         try {
1533             result.put(new Integer(101), new Integer(101).toString());
1534             fail("should throw IllegalArgumentException");
1535         } catch (IllegalArgumentException e) {
1536             // expected
1537         }
1538         assertEquals(100, result.size());
1539         assertEquals(100, treeMapInt.size());
1540         result = treeMapInt.headMap(new Integer(50), true);
1541         assertEquals(51, result.size());
1542         result.put(new Integer(-1), new Integer(-1).toString());
1543         assertEquals(52, result.size());
1544 
1545         treeMapInt.remove(new Integer(40));
1546         assertEquals(100, treeMapInt.size());
1547         assertEquals(51, result.size());
1548         result.remove(new Integer(30));
1549         assertEquals(99, treeMapInt.size());
1550         assertEquals(50, result.size());
1551         SortedMap<Integer, String> result2 = null;
1552         try {
1553             result.subMap(new Integer(-2), new Integer(100));
1554             fail("should throw IllegalArgumentException");
1555         } catch (IllegalArgumentException e) {
1556             // expected
1557         }
1558         try {
1559             result.subMap(new Integer(1), new Integer(100));
1560             fail("should throw IllegalArgumentException");
1561         } catch (IllegalArgumentException e) {
1562             // expected
1563         }
1564         result2 = result.subMap(new Integer(-2), new Integer(48));
1565         assertEquals(47, result2.size());
1566 
1567         result2 = result.subMap(new Integer(40), new Integer(50));
1568         assertEquals(9, result2.size());
1569 
1570         // Null Tolerable Comparator
1571         TreeMap<String, String> treeMapWithNull = new TreeMap<String, String>(
1572                 new MockComparatorNullTolerable());
1573         treeMapWithNull.put("key1", "value1"); //$NON-NLS-1$ //$NON-NLS-2$
1574         treeMapWithNull.put(null, "value2"); //$NON-NLS-1$
1575         SortedMap<String, String> subMapWithNull = treeMapWithNull.headMap(
1576                 null, true); //$NON-NLS-1$
1577         assertEquals("Size of subMap should be 1:", 1, subMapWithNull.size()); //$NON-NLS-1$
1578         assertEquals(null, subMapWithNull.get("key1"));
1579         assertEquals("value2", subMapWithNull.get(null));
1580         treeMapWithNull.put("key0", "value2");
1581         treeMapWithNull.put("key3", "value3");
1582         treeMapWithNull.put("key4", "value4");
1583         treeMapWithNull.put("key5", "value5");
1584         treeMapWithNull.put("key6", "value6");
1585         assertEquals("Size of subMap should be 1:", 1, subMapWithNull.size()); //$NON-NLS-1$
1586         subMapWithNull = treeMapWithNull.subMap(null, false, "key1", true); //$NON-NLS-1$
1587         assertEquals("Size of subMap should be 2:", 2, subMapWithNull.size()); //$NON-NLS-1$
1588 
1589         // head map of head map
1590         NavigableMap<Integer, Object> original = new TreeMap<Integer, Object>();
1591         for (int i = 0; i < 10; ++i) {
1592             original.put(i, new Object());
1593         }
1594         NavigableMap<Integer, Object> mapIntObj = original.headMap(5, false);
1595         assertEquals(5, mapIntObj.size());
1596         mapIntObj = mapIntObj.headMap(5, false);
1597         assertEquals(5, mapIntObj.size());
1598         try {
1599             mapIntObj = mapIntObj.tailMap(5, false);
1600             fail("IllegalArgumentException expected: key falls outside restricted range");
1601         } catch (IllegalArgumentException expected) {
1602         }
1603 
1604         assertEquals(0, original.headMap(0, false).size());
1605     }
1606 
1607     /**
1608      * java.util.TreeMap#tailMap(java.lang.Object, boolea)
1609      */
test_tailMapLjava_lang_ObjectZL()1610     public void test_tailMapLjava_lang_ObjectZL() {
1611         // normal case
1612         SortedMap subMap = tm.tailMap(objArray[100].toString(), true);
1613         assertEquals("subMap is of incorrect size", 997, subMap.size());
1614         subMap = tm.tailMap(objArray[109].toString(), true);
1615         assertEquals("subMap is of incorrect size", 988, subMap.size());
1616         for (int counter = 119; counter > 110; counter--) {
1617             assertTrue("SubMap contains incorrect elements", subMap.get(
1618                     objArray[counter].toString()).equals(objArray[counter]));
1619         }
1620         subMap = tm.tailMap(objArray[100].toString(), false);
1621         assertEquals("subMap is of incorrect size", 996, subMap.size());
1622         assertNull(subMap.get(objArray[100].toString()));
1623 
1624         // Exceptions
1625         assertEquals(1000, tm.tailMap("", true).size());
1626         assertEquals(1000, tm.tailMap("", false).size());
1627 
1628         try {
1629             tm.tailMap(null, true);
1630             fail("should throw NullPointerException");
1631         } catch (NullPointerException e) {
1632             // expected
1633         }
1634         try {
1635             tm.tailMap(null, false);
1636             fail("should throw NullPointerException");
1637         } catch (NullPointerException e) {
1638             // expected
1639         }
1640         try {
1641             tm.tailMap(new Object(), true);
1642             fail("should throw ClassCastException");
1643         } catch (ClassCastException e) {
1644             // expected
1645         }
1646         try {
1647             tm.tailMap(new Object(), false);
1648             fail("should throw ClassCastException");
1649         } catch (ClassCastException e) {
1650             // expected
1651         }
1652 
1653         // use integer elements to test
1654         TreeMap<Integer, String> treeMapInt = new TreeMap<Integer, String>();
1655         assertEquals(0, treeMapInt.tailMap(new Integer(-1), true).size());
1656         for (int i = 0; i < 100; i++) {
1657             treeMapInt.put(new Integer(i), new Integer(i).toString());
1658         }
1659         SortedMap<Integer, String> result = treeMapInt.tailMap(new Integer(1));
1660         assertEquals(99, result.size());
1661         try {
1662             result.put(new Integer(-1), new Integer(-1).toString());
1663             fail("should throw IllegalArgumentException");
1664         } catch (IllegalArgumentException e) {
1665             // expected
1666         }
1667         assertEquals(99, result.size());
1668         assertEquals(100, treeMapInt.size());
1669         result = treeMapInt.tailMap(new Integer(50), true);
1670         assertEquals(50, result.size());
1671         result.put(new Integer(101), new Integer(101).toString());
1672         assertEquals(51, result.size());
1673 
1674         treeMapInt.remove(new Integer(60));
1675         assertEquals(100, treeMapInt.size());
1676         assertEquals(50, result.size());
1677         result.remove(new Integer(70));
1678         assertEquals(99, treeMapInt.size());
1679         assertEquals(49, result.size());
1680         SortedMap<Integer, String> result2 = null;
1681         try {
1682             result2 = result.subMap(new Integer(-2), new Integer(100));
1683             fail("should throw IllegalArgumentException");
1684         } catch (IllegalArgumentException e) {
1685             // expected
1686         }
1687         result2 = result.subMap(new Integer(60), new Integer(70));
1688         assertEquals(9, result2.size());
1689 
1690         // Null Tolerable Comparator
1691         TreeMap<String, String> treeMapWithNull = new TreeMap<String, String>(
1692                 new MockComparatorNullTolerable());
1693         treeMapWithNull.put("key1", "value1"); //$NON-NLS-1$ //$NON-NLS-2$
1694         treeMapWithNull.put(null, "value2"); //$NON-NLS-1$
1695         SortedMap<String, String> subMapWithNull = treeMapWithNull.tailMap(
1696                 "key1", true); //$NON-NLS-1$
1697         assertEquals("Size of subMap should be 1:", 1, subMapWithNull.size()); //$NON-NLS-1$
1698         assertEquals("value1", subMapWithNull.get("key1"));
1699         assertEquals(null, subMapWithNull.get(null));
1700         treeMapWithNull.put("key0", "value2");
1701         treeMapWithNull.put("key3", "value3");
1702         treeMapWithNull.put("key4", "value4");
1703         treeMapWithNull.put("key5", "value5");
1704         treeMapWithNull.put("key6", "value6");
1705         assertEquals("Size of subMap should be 5:", 5, subMapWithNull.size()); //$NON-NLS-1$
1706         subMapWithNull = treeMapWithNull.subMap(null, false, "key1", true); //$NON-NLS-1$
1707         assertEquals("Size of subMap should be 2:", 2, subMapWithNull.size()); //$NON-NLS-1$
1708 
1709         // tail map of tail map
1710         NavigableMap<Integer, Object> original = new TreeMap<Integer, Object>();
1711         for (int i = 0; i < 10; ++i) {
1712             original.put(i, new Object());
1713         }
1714         NavigableMap<Integer, Object> mapIntObj = original.tailMap(5, false);
1715         assertEquals(4, mapIntObj.size());
1716         mapIntObj = mapIntObj.tailMap(5, false);
1717         assertEquals(4, mapIntObj.size());
1718         try {
1719             mapIntObj = mapIntObj.headMap(5, false);
1720             fail("IllegalArgumentException expected: key falls outside restricted range");
1721         } catch (IllegalArgumentException expected) {
1722         }
1723 
1724         assertEquals(0, original.headMap(0, false).size());
1725     }
1726 
test_descendingMap_subMap()1727     public void test_descendingMap_subMap() throws Exception {
1728         TreeMap<Integer, Object> tm = new TreeMap<Integer, Object>();
1729         for (int i = 0; i < 10; ++i) {
1730             tm.put(i, new Object());
1731         }
1732         NavigableMap<Integer, Object> descMap = tm.descendingMap();
1733         assertEquals(7, descMap.subMap(8, true, 1, false).size());
1734         assertEquals(4, descMap.headMap(6, true).size());
1735         assertEquals(2, descMap.tailMap(2, false).size());
1736 
1737         // sub map of sub map of descendingMap
1738         NavigableMap<Integer, Object> mapIntObj = new TreeMap<Integer, Object>();
1739         for (int i = 0; i < 10; ++i) {
1740             mapIntObj.put(i, new Object());
1741         }
1742         mapIntObj = mapIntObj.descendingMap();
1743         NavigableMap<Integer, Object> subMapIntObj = mapIntObj.subMap(9, true,
1744                 5, false);
1745         assertEquals(4, subMapIntObj.size());
1746         subMapIntObj = subMapIntObj.subMap(9, true, 5, false);
1747         assertEquals(4, subMapIntObj.size());
1748         subMapIntObj = subMapIntObj.subMap(6, false, 5, false);
1749         assertEquals(0, subMapIntObj.size());
1750 
1751         subMapIntObj = mapIntObj.headMap(5, false);
1752         assertEquals(4, subMapIntObj.size());
1753         subMapIntObj = subMapIntObj.headMap(5, false);
1754         assertEquals(4, subMapIntObj.size());
1755         try {
1756             subMapIntObj = subMapIntObj.tailMap(5, false);
1757             fail("IllegalArgumentException expected: key falls outside restricted range");
1758         } catch (IllegalArgumentException expected) {
1759         }
1760 
1761         subMapIntObj = mapIntObj.tailMap(5, false);
1762         assertEquals(5, subMapIntObj.size());
1763         subMapIntObj = subMapIntObj.tailMap(5, false);
1764         assertEquals(5, subMapIntObj.size());
1765         try {
1766             subMapIntObj = subMapIntObj.headMap(5, false);
1767             fail("IllegalArgumentException expected: key falls outside restricted range");
1768         } catch (IllegalArgumentException expected) {
1769         }
1770     }
1771 
illegalFirstNullKeyMapTester(NavigableMap<String, String> map)1772     private void illegalFirstNullKeyMapTester(NavigableMap<String, String> map) {
1773         try {
1774             map.get(null);
1775             fail("Should throw NullPointerException");
1776         } catch (NullPointerException e) {
1777             // expected
1778         }
1779         try {
1780             map.put("NormalKey", "value");
1781             fail("Should throw NullPointerException");
1782         } catch (NullPointerException e) {
1783             // expected
1784         }
1785         Set<String> keySet = map.keySet();
1786         assertTrue(!keySet.isEmpty());
1787         assertEquals(1, keySet.size());
1788         for (String key : keySet) {
1789             assertEquals(key, null);
1790             try {
1791                 map.get(key);
1792                 fail("Should throw NullPointerException");
1793             } catch (NullPointerException e) {
1794                 // ignore
1795             }
1796         }
1797         Set<Entry<String, String>> entrySet = map.entrySet();
1798         assertTrue(!entrySet.isEmpty());
1799         assertEquals(1, entrySet.size());
1800         for (Entry<String, String> entry : entrySet) {
1801             assertEquals(null, entry.getKey());
1802             assertEquals("NullValue", entry.getValue());
1803         }
1804         Collection<String> values = map.values();
1805         assertTrue(!values.isEmpty());
1806         assertEquals(1, values.size());
1807         for (String value : values) {
1808             assertEquals("NullValue", value);
1809         }
1810 
1811         try {
1812             map.headMap(null, true);
1813             fail("Should throw NullPointerException");
1814         } catch (NullPointerException e) {
1815             // ignore
1816         }
1817         try {
1818             map.headMap(null, false);
1819             fail("Should throw NullPointerException");
1820         } catch (NullPointerException e) {
1821             // ignore
1822         }
1823 
1824         try {
1825             map.subMap(null, false, null, false);
1826             fail("Should throw NullPointerException");
1827         } catch (NullPointerException e) {
1828             // ignore
1829         }
1830         try {
1831             map.subMap(null, true, null, true);
1832             fail("Should throw NullPointerException");
1833         } catch (NullPointerException e) {
1834             // ignore
1835         }
1836         try {
1837             map.tailMap(null, true);
1838             fail("Should throw NullPointerException");
1839         } catch (NullPointerException e) {
1840             // ignore
1841         }
1842         try {
1843             map.tailMap(null, false);
1844             fail("Should throw NullPointerException");
1845         } catch (NullPointerException e) {
1846             // ignore
1847         }
1848     }
1849 
1850     /**
1851      * Tests equals() method.
1852      * Tests that no ClassCastException will be thrown in all cases.
1853      * Regression test for HARMONY-1639.
1854      */
test_equals()1855     public void test_equals() throws Exception {
1856         // comparing TreeMaps with different object types
1857         Map m1 = new TreeMap();
1858         Map m2 = new TreeMap();
1859         m1.put("key1", "val1");
1860         m1.put("key2", "val2");
1861         m2.put(new Integer(1), "val1");
1862         m2.put(new Integer(2), "val2");
1863         assertFalse("Maps should not be equal 1", m1.equals(m2));
1864         assertFalse("Maps should not be equal 2", m2.equals(m1));
1865 
1866         // comparing TreeMap with HashMap
1867         m1 = new TreeMap();
1868         m2 = new HashMap();
1869         m1.put("key", "val");
1870         m2.put(new Object(), "val");
1871         assertFalse("Maps should not be equal 3", m1.equals(m2));
1872         assertFalse("Maps should not be equal 4", m2.equals(m1));
1873     }
1874 
test_invalidKeys()1875     public void test_invalidKeys() throws Exception {
1876         // comparing TreeMaps with not-comparable objects inside
1877         TreeMap m1 = new TreeMap();
1878         try {
1879             m1.put(new Object(), "val1");
1880             fail("ClassCastException expected");
1881         } catch (ClassCastException expected) {
1882 
1883         }
1884     }
1885 
test_remove_from_iterator()1886     public void test_remove_from_iterator() throws Exception {
1887         Set set = tm.keySet();
1888         Iterator iter = set.iterator();
1889         iter.next();
1890         iter.remove();
1891         try {
1892             iter.remove();
1893             fail("should throw IllegalStateException");
1894         } catch (IllegalStateException e) {
1895             // expected
1896         }
1897     }
1898 
1899     /**
1900      * Tests entrySet().contains() method behaviour with respect to entries
1901      * with null values.
1902      * Regression test for HARMONY-5788.
1903      */
test_entrySet_contains()1904     public void test_entrySet_contains() throws Exception {
1905         TreeMap master = new TreeMap<String, String>();
1906         TreeMap test_map = new TreeMap<String, String>();
1907 
1908         master.put("null", null);
1909         Object[] entry = master.entrySet().toArray();
1910         assertFalse("Empty map should not contain the null-valued entry",
1911                 test_map.entrySet().contains(entry[0]));
1912 
1913         Map<String, String> submap = test_map.subMap("a", "z");
1914         entry = master.entrySet().toArray();
1915         assertFalse("Empty submap should not contain the null-valued entry",
1916                 submap.entrySet().contains(entry[0]));
1917 
1918         test_map.put("null", null);
1919         assertTrue("entrySet().containsAll(...) should work with null values",
1920                 test_map.entrySet().containsAll(master.entrySet()));
1921 
1922         master.clear();
1923         master.put("null", '0');
1924         entry = master.entrySet().toArray();
1925         assertFalse("Null-valued entry should not equal non-null-valued entry",
1926                 test_map.entrySet().contains(entry[0]));
1927     }
1928 
test_iterator_next_()1929     public void test_iterator_next_() {
1930         Map m = tm.subMap("0", "1");
1931         Iterator it = m.entrySet().iterator();
1932         assertEquals("0=0", it.next().toString());
1933         while (it.hasNext()) {
1934         }
1935         try {
1936             it.next();
1937             fail("should throw java.util.NoSuchElementException");
1938         } catch (Exception e) {
1939             assertTrue(e instanceof java.util.NoSuchElementException);
1940         }
1941     }
1942 
test_empty_subMap()1943     public void test_empty_subMap() throws Exception {
1944         TreeMap<Float, List<Integer>> tm = new TreeMap<Float, List<Integer>>();
1945         SortedMap<Float, List<Integer>> sm = tm.tailMap(1.1f);
1946         assertTrue(sm.values().size() == 0);
1947     }
1948 
1949     public static TreeMap treeMap = new TreeMap();
1950 
test_values_1()1951     public void test_values_1() {
1952         treeMap.put("firstKey", "firstValue");
1953         treeMap.put("secondKey", "secondValue");
1954         treeMap.put("thirdKey", "thirdValue");
1955         Object firstKey = treeMap.firstKey();
1956         SortedMap subMap = ((SortedMap) treeMap).subMap(firstKey, firstKey);
1957         Iterator iter = subMap.values().iterator();
1958     }
1959 
test_forEach()1960     public void test_forEach() throws Exception {
1961         TreeMap<String, String> map = new TreeMap<>();
1962         map.put("one", "1");
1963         map.put("two", "2");
1964         map.put("three", "3");
1965 
1966         TreeMap<String, String> output = new TreeMap<>();
1967         map.forEach((k, v) -> output.put(k,v));
1968         assertEquals(map, output);
1969 
1970         HashSet<String> setOutput = new HashSet<>();
1971         map.keySet().forEach((k) -> setOutput.add(k));
1972         assertEquals(map.keySet(), setOutput);
1973 
1974         setOutput.clear();
1975         map.values().forEach((v) -> setOutput.add(v));
1976         assertEquals(new HashSet<>(map.values()), setOutput);
1977 
1978         HashSet<Map.Entry<String,String>> entrySetOutput = new HashSet<>();
1979         map.entrySet().forEach((v) -> entrySetOutput.add(v));
1980         assertEquals(map.entrySet(), entrySetOutput);
1981     }
1982 
test_forEach_NPE()1983     public void test_forEach_NPE() throws Exception {
1984         TreeMap<String, String> map = new TreeMap<>();
1985         try {
1986             map.forEach(null);
1987             fail();
1988         } catch(NullPointerException expected) {}
1989 
1990         try {
1991             map.keySet().forEach(null);
1992             fail();
1993         } catch(NullPointerException expected) {}
1994 
1995         try {
1996             map.values().forEach(null);
1997             fail();
1998         } catch(NullPointerException expected) {}
1999 
2000         try {
2001             map.entrySet().forEach(null);
2002             fail();
2003         } catch(NullPointerException expected) {}
2004     }
2005 
test_forEach_CME()2006     public void test_forEach_CME() throws Exception {
2007         TreeMap<String, String> map = new TreeMap<>();
2008         map.put("one", "1");
2009         map.put("two", "2");
2010         try {
2011             map.forEach(new java.util.function.BiConsumer<String, String>() {
2012                     @Override
2013                     public void accept(String k, String v) {map.put("foo", v);}
2014                 });
2015             fail();
2016         } catch(ConcurrentModificationException expected) {}
2017 
2018         try {
2019             map.keySet().forEach(new java.util.function.Consumer<String>() {
2020                     @Override
2021                     public void accept(String k) {map.put("foo2", "boo");}
2022                 });
2023             fail();
2024         } catch(ConcurrentModificationException expected) {}
2025 
2026         try {
2027             map.values().forEach(new java.util.function.Consumer<String>() {
2028                     @Override
2029                     public void accept(String k) {map.put("foo3", "boo");}
2030                 });
2031             fail();
2032         } catch(ConcurrentModificationException expected) {}
2033 
2034         try {
2035             map.entrySet().forEach(new java.util.function.Consumer<Map.Entry<String,String>>() {
2036                     @Override
2037                     public void accept(Map.Entry<String,String> k) {map.put("foo4", "boo");}
2038                 });
2039             fail();
2040         } catch(ConcurrentModificationException expected) {}
2041     }
2042 
2043     /**
2044      * Sets up the fixture, for example, open a network connection. This method
2045      * is called before a test is executed.
2046      */
2047     @Override
setUp()2048     protected void setUp() {
2049         tm = new TreeMap();
2050         for (int i = 0; i < objArray.length; i++) {
2051             Object x = objArray[i] = new Integer(i);
2052             tm.put(x.toString(), x);
2053         }
2054     }
2055 }
2056