001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package org.apache.harmony.luni.tests.java.util;
019:
020: import java.io.Serializable;
021: import java.text.CollationKey;
022: import java.text.Collator;
023: import java.util.AbstractMap;
024: import java.util.Collection;
025: import java.util.Comparator;
026: import java.util.HashMap;
027: import java.util.Iterator;
028: import java.util.Map;
029: import java.util.Set;
030: import java.util.SortedMap;
031: import java.util.TreeMap;
032:
033: import org.apache.harmony.testframework.serialization.SerializationTest;
034:
035: import tests.support.Support_MapTest2;
036: import tests.support.Support_UnmodifiableCollectionTest;
037:
038: public class TreeMapTest extends junit.framework.TestCase {
039:
040: public static class ReversedComparator implements Comparator {
041: public int compare(Object o1, Object o2) {
042: return -(((Comparable) o1).compareTo(o2));
043: }
044:
045: public boolean equals(Object o1, Object o2) {
046: return (((Comparable) o1).compareTo(o2)) == 0;
047: }
048: }
049:
050: // Regression for Harmony-1026
051: public static class MockComparator<T extends Comparable<T>>
052: implements Comparator<T>, Serializable {
053:
054: public int compare(T o1, T o2) {
055: if (o1 == o2) {
056: return 0;
057: }
058: if (null == o1 || null == o2) {
059: return -1;
060: }
061: T c1 = o1;
062: T c2 = o2;
063: return c1.compareTo(c2);
064: }
065: }
066:
067: // Regression for Harmony-1161
068: class MockComparatorNullTolerable implements Comparator<String> {
069:
070: public int compare(String o1, String o2) {
071: if (o1 == o2) {
072: return 0;
073: }
074: if (null == o1) {
075: return -1;
076: }
077: if (null == o2) { // comparator should be symmetric
078: return 1;
079: }
080: return o1.compareTo(o2);
081: }
082: }
083:
084: TreeMap tm;
085:
086: Object objArray[] = new Object[1000];
087:
088: /**
089: * @tests java.util.TreeMap#TreeMap()
090: */
091: public void test_Constructor() {
092: // Test for method java.util.TreeMap()
093: new Support_MapTest2(new TreeMap()).runTest();
094:
095: assertTrue("New treeMap non-empty", new TreeMap().isEmpty());
096: }
097:
098: /**
099: * @tests java.util.TreeMap#TreeMap(java.util.Comparator)
100: */
101: public void test_ConstructorLjava_util_Comparator() {
102: // Test for method java.util.TreeMap(java.util.Comparator)
103: Comparator comp = new ReversedComparator();
104: TreeMap reversedTreeMap = new TreeMap(comp);
105: assertTrue("TreeMap answered incorrect comparator",
106: reversedTreeMap.comparator() == comp);
107: reversedTreeMap.put(new Integer(1).toString(), new Integer(1));
108: reversedTreeMap.put(new Integer(2).toString(), new Integer(2));
109: assertTrue(
110: "TreeMap does not use comparator (firstKey was incorrect)",
111: reversedTreeMap.firstKey().equals(
112: new Integer(2).toString()));
113: assertTrue(
114: "TreeMap does not use comparator (lastKey was incorrect)",
115: reversedTreeMap.lastKey().equals(
116: new Integer(1).toString()));
117:
118: }
119:
120: /**
121: * @tests java.util.TreeMap#TreeMap(java.util.Map)
122: */
123: public void test_ConstructorLjava_util_Map() {
124: // Test for method java.util.TreeMap(java.util.Map)
125: TreeMap myTreeMap = new TreeMap(new HashMap(tm));
126: assertTrue("Map is incorrect size",
127: myTreeMap.size() == objArray.length);
128: for (Object element : objArray) {
129: assertTrue("Map has incorrect mappings", myTreeMap.get(
130: element.toString()).equals(element));
131: }
132: }
133:
134: /**
135: * @tests java.util.TreeMap#TreeMap(java.util.SortedMap)
136: */
137: public void test_ConstructorLjava_util_SortedMap() {
138: // Test for method java.util.TreeMap(java.util.SortedMap)
139: Comparator comp = new ReversedComparator();
140: TreeMap reversedTreeMap = new TreeMap(comp);
141: reversedTreeMap.put(new Integer(1).toString(), new Integer(1));
142: reversedTreeMap.put(new Integer(2).toString(), new Integer(2));
143: TreeMap anotherTreeMap = new TreeMap(reversedTreeMap);
144: assertTrue("New tree map does not answer correct comparator",
145: anotherTreeMap.comparator() == comp);
146: assertTrue(
147: "TreeMap does not use comparator (firstKey was incorrect)",
148: anotherTreeMap.firstKey().equals(
149: new Integer(2).toString()));
150: assertTrue(
151: "TreeMap does not use comparator (lastKey was incorrect)",
152: anotherTreeMap.lastKey().equals(
153: new Integer(1).toString()));
154:
155: }
156:
157: /**
158: * @tests java.util.TreeMap#clear()
159: */
160: public void test_clear() {
161: // Test for method void java.util.TreeMap.clear()
162: tm.clear();
163: assertEquals("Cleared map returned non-zero size", 0, tm.size());
164: }
165:
166: /**
167: * @tests java.util.TreeMap#clone()
168: */
169: public void test_clone() {
170: // Test for method java.lang.Object java.util.TreeMap.clone()
171: TreeMap clonedMap = (TreeMap) tm.clone();
172: assertTrue("Cloned map does not equal the original map",
173: clonedMap.equals(tm));
174: assertTrue(
175: "Cloned map is the same reference as the original map",
176: clonedMap != tm);
177: for (Object element : objArray) {
178: assertTrue("Cloned map contains incorrect elements",
179: clonedMap.get(element.toString()) == tm.get(element
180: .toString()));
181: }
182:
183: TreeMap map = new TreeMap();
184: map.put("key", "value");
185: // get the keySet() and values() on the original Map
186: Set keys = map.keySet();
187: Collection values = map.values();
188: assertEquals("values() does not work", "value", values
189: .iterator().next());
190: assertEquals("keySet() does not work", "key", keys.iterator()
191: .next());
192: AbstractMap map2 = (AbstractMap) map.clone();
193: map2.put("key", "value2");
194: Collection values2 = map2.values();
195: assertTrue("values() is identical", values2 != values);
196: // values() and keySet() on the cloned() map should be different
197: assertEquals("values() was not cloned", "value2", values2
198: .iterator().next());
199: map2.clear();
200: map2.put("key2", "value3");
201: Set key2 = map2.keySet();
202: assertTrue("keySet() is identical", key2 != keys);
203: assertEquals("keySet() was not cloned", "key2", key2.iterator()
204: .next());
205: }
206:
207: /**
208: * @tests java.util.TreeMap#comparator()
209: */
210: public void test_comparator() {
211: // Test for method java.util.Comparator java.util.TreeMap.comparator()\
212: Comparator comp = new ReversedComparator();
213: TreeMap reversedTreeMap = new TreeMap(comp);
214: assertTrue("TreeMap answered incorrect comparator",
215: reversedTreeMap.comparator() == comp);
216: reversedTreeMap.put(new Integer(1).toString(), new Integer(1));
217: reversedTreeMap.put(new Integer(2).toString(), new Integer(2));
218: assertTrue(
219: "TreeMap does not use comparator (firstKey was incorrect)",
220: reversedTreeMap.firstKey().equals(
221: new Integer(2).toString()));
222: assertTrue(
223: "TreeMap does not use comparator (lastKey was incorrect)",
224: reversedTreeMap.lastKey().equals(
225: new Integer(1).toString()));
226: }
227:
228: /**
229: * @tests java.util.TreeMap#containsKey(java.lang.Object)
230: */
231: public void test_containsKeyLjava_lang_Object() {
232: // Test for method boolean
233: // java.util.TreeMap.containsKey(java.lang.Object)
234: assertTrue("Returned false for valid key", tm.containsKey("95"));
235: assertTrue("Returned true for invalid key", !tm
236: .containsKey("XXXXX"));
237: }
238:
239: /**
240: * @tests java.util.TreeMap#containsValue(java.lang.Object)
241: */
242: public void test_containsValueLjava_lang_Object() {
243: // Test for method boolean
244: // java.util.TreeMap.containsValue(java.lang.Object)
245: assertTrue("Returned false for valid value", tm
246: .containsValue(objArray[986]));
247: assertTrue("Returned true for invalid value", !tm
248: .containsValue(new Object()));
249: }
250:
251: /**
252: * @tests java.util.TreeMap#entrySet()
253: */
254: public void test_entrySet() {
255: // Test for method java.util.Set java.util.TreeMap.entrySet()
256: Set anEntrySet = tm.entrySet();
257: Iterator entrySetIterator = anEntrySet.iterator();
258: assertTrue("EntrySet is incorrect size",
259: anEntrySet.size() == objArray.length);
260: Map.Entry entry;
261: while (entrySetIterator.hasNext()) {
262: entry = (Map.Entry) entrySetIterator.next();
263: assertTrue("EntrySet does not contain correct mappings", tm
264: .get(entry.getKey()) == entry.getValue());
265: }
266: }
267:
268: /**
269: * @tests java.util.TreeMap#firstKey()
270: */
271: public void test_firstKey() {
272: // Test for method java.lang.Object java.util.TreeMap.firstKey()
273: assertEquals("Returned incorrect first key", "0", tm.firstKey());
274: }
275:
276: /**
277: * @tests java.util.TreeMap#get(java.lang.Object)
278: */
279: public void test_getLjava_lang_Object() {
280: // Test for method java.lang.Object
281: // java.util.TreeMap.get(java.lang.Object)
282: Object o = new Object();
283: tm.put("Hello", o);
284: assertTrue("Failed to get mapping", tm.get("Hello") == o);
285:
286: }
287:
288: /**
289: * @tests java.util.TreeMap#headMap(java.lang.Object)
290: */
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: try {
368: sub.lastKey();
369: fail("java.util.NoSuchElementException should be thrown");
370: } catch (java.util.NoSuchElementException e) {
371: }
372:
373: size = 256;
374: intMap = new TreeMap<Integer, Integer>();
375: for (int i = 0; i < size; i++) {
376: intMap.put(i, i);
377: }
378: sub = intMap.headMap(-1);
379: assertEquals("size should be zero", sub.size(), 0);
380: assertTrue("submap should be empty", sub.isEmpty());
381: try {
382: sub.firstKey();
383: fail("java.util.NoSuchElementException should be thrown");
384: } catch (java.util.NoSuchElementException e) {
385: }
386:
387: try {
388: sub.lastKey();
389: fail("java.util.NoSuchElementException should be thrown");
390: } catch (java.util.NoSuchElementException e) {
391: }
392:
393: }
394:
395: /**
396: * @tests java.util.TreeMap#keySet()
397: */
398: public void test_keySet() {
399: // Test for method java.util.Set java.util.TreeMap.keySet()
400: Set ks = tm.keySet();
401: assertTrue("Returned set of incorrect size",
402: ks.size() == objArray.length);
403: for (int i = 0; i < tm.size(); i++) {
404: assertTrue("Returned set is missing keys", ks
405: .contains(new Integer(i).toString()));
406: }
407: }
408:
409: /**
410: * @tests java.util.TreeMap#lastKey()
411: */
412: public void test_lastKey() {
413: // Test for method java.lang.Object java.util.TreeMap.lastKey()
414: assertTrue("Returned incorrect last key", tm.lastKey().equals(
415: objArray[objArray.length - 1].toString()));
416: }
417:
418: /**
419: * @tests java.util.TreeMap#put(java.lang.Object, java.lang.Object)
420: */
421: public void test_putLjava_lang_ObjectLjava_lang_Object() {
422: // Test for method java.lang.Object
423: // java.util.TreeMap.put(java.lang.Object, java.lang.Object)
424: Object o = new Object();
425: tm.put("Hello", o);
426: assertTrue("Failed to put mapping", tm.get("Hello") == o);
427:
428: // regression for Harmony-780
429: tm = new TreeMap();
430: assertNull(tm.put(new Object(), new Object()));
431: try {
432: tm.put(new Integer(1), new Object());
433: fail("should throw ClassCastException");
434: } catch (ClassCastException e) {
435: // expected
436: }
437:
438: tm = new TreeMap();
439: assertNull(tm.put(new Integer(1), new Object()));
440:
441: // regression for Harmony-2474
442: tm = new TreeMap();
443: tm.remove(o);
444: }
445:
446: /**
447: * @tests java.util.TreeMap#putAll(java.util.Map)
448: */
449: public void test_putAllLjava_util_Map() {
450: // Test for method void java.util.TreeMap.putAll(java.util.Map)
451: TreeMap x = new TreeMap();
452: x.putAll(tm);
453: assertTrue("Map incorrect size after put", x.size() == tm
454: .size());
455: for (Object element : objArray) {
456: assertTrue("Failed to put all elements", x.get(
457: element.toString()).equals(element));
458: }
459: }
460:
461: /**
462: * @tests java.util.TreeMap#remove(java.lang.Object)
463: */
464: public void test_removeLjava_lang_Object() {
465: // Test for method java.lang.Object
466: // java.util.TreeMap.remove(java.lang.Object)
467: tm.remove("990");
468: assertTrue("Failed to remove mapping", !tm.containsKey("990"));
469:
470: }
471:
472: /**
473: * @tests java.util.TreeMap#size()
474: */
475: public void test_size() {
476: // Test for method int java.util.TreeMap.size()
477: assertEquals("Returned incorrect size", 1000, tm.size());
478: }
479:
480: /**
481: * @tests java.util.TreeMap#subMap(java.lang.Object, java.lang.Object)
482: */
483: public void test_subMapLjava_lang_ObjectLjava_lang_Object() {
484: // Test for method java.util.SortedMap
485: // java.util.TreeMap.subMap(java.lang.Object, java.lang.Object)
486: SortedMap subMap = tm.subMap(objArray[100].toString(),
487: objArray[109].toString());
488: assertEquals("subMap is of incorrect size", 9, subMap.size());
489: for (int counter = 100; counter < 109; counter++) {
490: assertTrue("SubMap contains incorrect elements", subMap
491: .get(objArray[counter].toString()).equals(
492: objArray[counter]));
493: }
494:
495: try {
496: tm.subMap(objArray[9].toString(), objArray[1].toString());
497: fail("end key less than start key should throw IllegalArgumentException");
498: } catch (IllegalArgumentException e) {
499: // Expected
500: }
501:
502: // Regression for Harmony-1161
503: TreeMap<String, String> treeMapWithNull = new TreeMap<String, String>(
504: new MockComparatorNullTolerable());
505: treeMapWithNull.put("key1", "value1"); //$NON-NLS-1$ //$NON-NLS-2$
506: treeMapWithNull.put(null, "value2"); //$NON-NLS-1$
507: SortedMap<String, String> subMapWithNull = treeMapWithNull
508: .subMap(null, "key1"); //$NON-NLS-1$
509: assertEquals(
510: "Size of subMap should be 1:", 1, subMapWithNull.size()); //$NON-NLS-1$
511:
512: // Regression test for typo in lastKey method
513: SortedMap<String, String> map = new TreeMap<String, String>();
514: map.put("1", "one"); //$NON-NLS-1$ //$NON-NLS-2$
515: map.put("2", "two"); //$NON-NLS-1$ //$NON-NLS-2$
516: map.put("3", "three"); //$NON-NLS-1$ //$NON-NLS-2$
517: assertEquals("3", map.lastKey());
518: SortedMap<String, String> sub = map.subMap("1", "3"); //$NON-NLS-1$ //$NON-NLS-2$
519: assertEquals("2", sub.lastKey()); //$NON-NLS-1$
520: }
521:
522: /**
523: * @tests java.util.TreeMap#tailMap(java.lang.Object)
524: */
525: public void test_tailMapLjava_lang_Object() {
526: // Test for method java.util.SortedMap
527: // java.util.TreeMap.tailMap(java.lang.Object)
528: Map tail = tm.tailMap(objArray[900].toString());
529: assertTrue("Returned map of incorrect size : " + tail.size(),
530: tail.size() == (objArray.length - 900) + 9);
531: for (int i = 900; i < objArray.length; i++) {
532: assertTrue("Map contains incorrect entries", tail
533: .containsValue(objArray[i]));
534: }
535:
536: // Regression for Harmony-1066
537: assertTrue(tail instanceof Serializable);
538:
539: SortedMap<Integer, Integer> intMap, sub;
540: int size = 16;
541: intMap = new TreeMap<Integer, Integer>();
542: for (int i = 0; i < size; i++) {
543: intMap.put(i, i);
544: }
545: sub = intMap.tailMap(size);
546: assertEquals("size should be zero", sub.size(), 0);
547: assertTrue("submap should be empty", sub.isEmpty());
548: try {
549: sub.firstKey();
550: fail("java.util.NoSuchElementException should be thrown");
551: } catch (java.util.NoSuchElementException e) {
552: }
553:
554: try {
555: sub.lastKey();
556: fail("java.util.NoSuchElementException should be thrown");
557: } catch (java.util.NoSuchElementException e) {
558: }
559:
560: size = 256;
561: intMap = new TreeMap<Integer, Integer>();
562: for (int i = 0; i < size; i++) {
563: intMap.put(i, i);
564: }
565: sub = intMap.tailMap(size);
566: assertEquals("size should be zero", sub.size(), 0);
567: assertTrue("submap should be empty", sub.isEmpty());
568: try {
569: sub.firstKey();
570: fail("java.util.NoSuchElementException should be thrown");
571: } catch (java.util.NoSuchElementException e) {
572: }
573:
574: try {
575: sub.lastKey();
576: fail("java.util.NoSuchElementException should be thrown");
577: } catch (java.util.NoSuchElementException e) {
578: }
579:
580: }
581:
582: /**
583: * @tests java.util.TreeMap#values()
584: */
585: public void test_values() {
586: // Test for method java.util.Collection java.util.TreeMap.values()
587: Collection vals = tm.values();
588: vals.iterator();
589: assertTrue("Returned collection of incorrect size",
590: vals.size() == objArray.length);
591: for (Object element : objArray) {
592: assertTrue("Collection contains incorrect elements", vals
593: .contains(element));
594: }
595:
596: TreeMap myTreeMap = new TreeMap();
597: for (int i = 0; i < 100; i++) {
598: myTreeMap.put(objArray[i], objArray[i]);
599: }
600: Collection values = myTreeMap.values();
601: new Support_UnmodifiableCollectionTest(
602: "Test Returned Collection From TreeMap.values()",
603: values).runTest();
604: values.remove(new Integer(0));
605: assertTrue(
606: "Removing from the values collection should remove from the original map",
607: !myTreeMap.containsValue(new Integer(0)));
608: }
609:
610: /**
611: * @tests java.util.TreeMap#SerializationTest()
612: */
613: // Regression for Harmony-1066
614: public void test_SubMap_Serializable() throws Exception {
615: TreeMap<Integer, Double> map = new TreeMap<Integer, Double>();
616: map.put(1, 2.1);
617: map.put(2, 3.1);
618: map.put(3, 4.5);
619: map.put(7, 21.3);
620: SortedMap<Integer, Double> headMap = map.headMap(3);
621: assertTrue(headMap instanceof Serializable);
622: assertFalse(headMap instanceof TreeMap);
623: assertTrue(headMap instanceof SortedMap);
624:
625: assertFalse(headMap.entrySet() instanceof Serializable);
626: assertFalse(headMap.keySet() instanceof Serializable);
627: assertFalse(headMap.values() instanceof Serializable);
628:
629: // This assertion will fail on RI. This is a bug of RI.
630: SerializationTest.verifySelf(headMap);
631: }
632:
633: /**
634: * Tests equals() method.
635: * Tests that no ClassCastException will be thrown in all cases.
636: * Regression test for HARMONY-1639.
637: */
638: public void test_equals() throws Exception {
639: // comparing TreeMaps with different object types
640: Map m1 = new TreeMap();
641: Map m2 = new TreeMap();
642: m1.put("key1", "val1");
643: m1.put("key2", "val2");
644: m2.put(new Integer(1), "val1");
645: m2.put(new Integer(2), "val2");
646: assertFalse("Maps should not be equal 1", m1.equals(m2));
647: assertFalse("Maps should not be equal 2", m2.equals(m1));
648:
649: // comparing TreeMap with HashMap
650: m1 = new TreeMap();
651: m2 = new HashMap();
652: m1.put("key", "val");
653: m2.put(new Object(), "val");
654: assertFalse("Maps should not be equal 3", m1.equals(m2));
655: assertFalse("Maps should not be equal 4", m2.equals(m1));
656:
657: // comparing TreeMaps with not-comparable objects inside
658: m1 = new TreeMap();
659: m2 = new TreeMap();
660: m1.put(new Object(), "val1");
661: m2.put(new Object(), "val1");
662: assertFalse("Maps should not be equal 5", m1.equals(m2));
663: assertFalse("Maps should not be equal 6", m2.equals(m1));
664: }
665:
666: /**
667: * Sets up the fixture, for example, open a network connection. This method
668: * is called before a test is executed.
669: */
670: @Override
671: protected void setUp() {
672: tm = new TreeMap();
673: for (int i = 0; i < objArray.length; i++) {
674: Object x = objArray[i] = new Integer(i);
675: tm.put(x.toString(), x);
676: }
677: }
678:
679: }
|