libcore/luni/src/test/java/java/util/TreeMapTest.java

   1 /*
   2  * Copyright (C) 2010 Google Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 package java.util;
  18
  19 import java.util.AbstractMap.SimpleEntry;
  20 import java.util.Map.Entry;
  21 import junit.framework.TestCase;
  22
  23 public class TreeMapTest extends TestCase {
  24
  25     public void testConcurrentModificationDetection() {
  26         Map<String, String> map = new TreeMap<String, String>();
  27         map.put("A", "a");
  28         map.put("B", "b");
  29         map.put("C", "c");
  30         Iterator<Entry<String,String>> iterator = map.entrySet().iterator();
  31         iterator.next();
  32         iterator.next();
  33         iterator.remove();
  34         map.put("D", "d");
  35         try {
  36             iterator.next();
  37             fail();
  38         } catch (ConcurrentModificationException e) {
  39         }
  40     }
  41
  42     public void testIteratorRemoves() {
  43         Map<String, String> map = new TreeMap<String, String>();
  44         map.put("A", "a");
  45         map.put("B", "b");
  46         map.put("C", "c");
  47         Iterator<Entry<String,String>> iterator = map.entrySet().iterator();
  48         assertEquals("A", iterator.next().getKey());
  49         assertEquals("B", iterator.next().getKey());
  50         iterator.remove();
  51         assertEquals("C", iterator.next().getKey());
  52         iterator.remove();
  53         assertFalse(iterator.hasNext());
  54     }
  55
  56     /**
  57      * Test that entry set contains and removal use the comparator rather than equals.
  58      */
  59     public void testEntrySetUsesComparatorOnly() {
  60         Map<String,String> map = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER);
  61         map.put("ABC", "a");
  62         assertTrue(map.entrySet().contains(new SimpleEntry<String, String>("abc", "a")));
  63         assertTrue(map.entrySet().remove(new SimpleEntry<String, String>("abc", "a")));
  64         assertEquals(0, map.size());
  65     }
  66
  67     public void testMapConstructorPassingSortedMap() {
  68         Map<String,String> source = new TreeMap<String, String>(String.CASE_INSENSITIVE_ORDER);
  69         NavigableMap<String,String> copy = new TreeMap<String, String>(source);
  70         assertEquals(null, copy.comparator());
  71     }
  72
  73     public void testNullsWithNaturalOrder() {
  74         HashMap<String, String> copyFrom = new HashMap<String, String>();
  75         copyFrom.put(null, "b");
  76         try {
  77             new TreeMap<String, String>(copyFrom);
  78             fail(); // the RI doesn't throw if null is the only key
  79         } catch (NullPointerException expected) {
  80         }
  81
  82         TreeMap<String,String> map = new TreeMap<String, String>();
  83         try {
  84             map.put(null, "b");
  85             fail();
  86         } catch (NullPointerException e) {
  87         }
  88
  89         try {
  90             map.descendingMap().put(null, "b");
  91             fail();
  92         } catch (NullPointerException e) {
  93         }
  94
  95         try {
  96             map.subMap("a", "z").put(null, "b");
  97             fail();
  98         } catch (NullPointerException e) {
  99         }
 100     }
 101
 102     public void testClassCastExceptions() {
 103         Map<Object, Object> map = new TreeMap<Object, Object>();
 104         map.put("A", "a");
 105         try {
 106             map.get(5);
 107             fail();
 108         } catch (ClassCastException e) {
 109         }
 110         try {
 111             map.containsKey(5);
 112             fail();
 113         } catch (ClassCastException e) {
 114         }
 115         try {
 116             map.remove(5);
 117             fail();
 118         } catch (ClassCastException e) {
 119         }
 120     }
 121
 122     public void testClassCastExceptionsOnBounds() {
 123         Map<Object, Object> map = new TreeMap<Object, Object>().subMap("a", "z");
 124         try {
 125             map.get(5);
 126             fail();
 127         } catch (ClassCastException e) {
 128         }
 129         try {
 130             map.containsKey(5);
 131             fail();
 132         } catch (ClassCastException e) {
 133         }
 134         try {
 135             map.remove(5);
 136             fail();
 137         } catch (ClassCastException e) {
 138         }
 139     }
 140
 141     public void testClone() {
 142         TreeMap<String, String> map = new TreeMap<String, String>() {
 143             @Override public String toString() {
 144                 return "x:" + super.toString();
 145             }
 146         };
 147
 148         map.put("A", "a");
 149         map.put("B", "b");
 150
 151         @SuppressWarnings("unchecked")
 152         TreeMap<String, String> clone = (TreeMap<String, String>) map.clone();
 153         assertEquals(map.getClass(), clone.getClass());
 154         assertEquals("x:{A=a, B=b}", map.toString());
 155     }
 156
 157     public void testEmptyMapSerialization() {
 158         String s = "aced0005737200166578616d706c65732e6a657373652e547265654d61700cc1f"
 159                 + "63e2d256ae60300014c000a636f6d70617261746f727400164c6a6176612f75746"
 160                 + "96c2f436f6d70617261746f723b78707077040000000078";
 161         TreeMap<String, String> map = new TreeMap<String, String>();
 162         new SerializableTester<TreeMap<String, String>>(map, s).test();
 163     }
 164
 165     public void testSerializationWithComparator() {
 166         String s = "aced0005737200116a6176612e7574696c2e547265654d61700cc1f63e2d256a"
 167                 + "e60300014c000a636f6d70617261746f727400164c6a6176612f7574696c2f436"
 168                 + "f6d70617261746f723b78707372002a6a6176612e6c616e672e537472696e6724"
 169                 + "43617365496e73656e736974697665436f6d70617261746f7277035c7d5c50e5c"
 170                 + "e02000078707704000000027400016171007e00057400016271007e000678";
 171         TreeMap<String,String> map = new TreeMap<String, String>(
 172                 String.CASE_INSENSITIVE_ORDER);
 173         map.put("a", "a");
 174         map.put("b", "b");
 175         new SerializableTester<NavigableMap<String, String>>(map, s) {
 176             @Override protected void verify(NavigableMap<String, String> deserialized) {
 177                 assertEquals(0, deserialized.comparator().compare("X", "x"));
 178             }
 179         }.test();
 180     }
 181
 182     public void testSubmapSerialization() {
 183         String s = "aced0005737200216a6176612e7574696c2e547265654d617024417363656e646"
 184                 + "96e675375624d61700cab946d1f0fab1c020000787200216a6176612e7574696c2"
 185                 + "e547265654d6170244e6176696761626c655375624d6170e2d0a70e64210e08020"
 186                 + "0075a000966726f6d53746172745a000b6869496e636c75736976655a000b6c6f4"
 187                 + "96e636c75736976655a0005746f456e644c000268697400124c6a6176612f6c616"
 188                 + "e672f4f626a6563743b4c00026c6f71007e00024c00016d7400134c6a6176612f7"
 189                 + "574696c2f547265654d61703b7870000001007400016374000161737200116a617"
 190                 + "6612e7574696c2e547265654d61700cc1f63e2d256ae60300014c000a636f6d706"
 191                 + "17261746f727400164c6a6176612f7574696c2f436f6d70617261746f723b78707"
 192                 + "372002a6a6176612e6c616e672e537472696e672443617365496e73656e7369746"
 193                 + "97665436f6d70617261746f7277035c7d5c50e5ce0200007870770400000004710"
 194                 + "07e000671007e00067400016271007e000c71007e000571007e000574000164710"
 195                 + "07e000d78";
 196         TreeMap<String,String> map = new TreeMap<String, String>(
 197                 String.CASE_INSENSITIVE_ORDER);
 198         map.put("a", "a");
 199         map.put("b", "b");
 200         map.put("c", "c");
 201         map.put("d", "d");
 202         SortedMap<String, String> submap = map.subMap("a", "c");
 203         new SerializableTester<SortedMap<String, String>>(submap, s) {
 204             @Override protected void verify(SortedMap<String, String> deserialized) {
 205                 try {
 206                     deserialized.put("e", "e");
 207                     fail();
 208                 } catch (IllegalArgumentException e) {
 209                 }
 210             }
 211         }.test();
 212     }
 213
 214     public void testNavigableSubmapSerialization() {
 215         String s = "aced0005737200216a6176612e7574696c2e547265654d617024417363656e646"
 216                 + "96e675375624d61700cab946d1f0fab1c020000787200216a6176612e7574696c2"
 217                 + "e547265654d6170244e6176696761626c655375624d6170e2d0a70e64210e08020"
 218                 + "0075a000966726f6d53746172745a000b6869496e636c75736976655a000b6c6f4"
 219                 + "96e636c75736976655a0005746f456e644c000268697400124c6a6176612f6c616"
 220                 + "e672f4f626a6563743b4c00026c6f71007e00024c00016d7400134c6a6176612f7"
 221                 + "574696c2f547265654d61703b7870000100007400016374000161737200116a617"
 222                 + "6612e7574696c2e547265654d61700cc1f63e2d256ae60300014c000a636f6d706"
 223                 + "17261746f727400164c6a6176612f7574696c2f436f6d70617261746f723b78707"
 224                 + "372002a6a6176612e6c616e672e537472696e672443617365496e73656e7369746"
 225                 + "97665436f6d70617261746f7277035c7d5c50e5ce0200007870770400000004710"
 226                 + "07e000671007e00067400016271007e000c71007e000571007e000574000164710"
 227                 + "07e000d78";
 228         TreeMap<String,String> map = new TreeMap<String, String>(
 229                 String.CASE_INSENSITIVE_ORDER);
 230         map.put("a", "a");
 231         map.put("b", "b");
 232         map.put("c", "c");
 233         map.put("d", "d");
 234         SortedMap<String, String> submap = map.subMap("a", false, "c", true);
 235         new SerializableTester<SortedMap<String, String>>(submap, s) {
 236             @Override protected void verify(SortedMap<String, String> deserialized) {
 237                 try {
 238                     deserialized.put("e", "e");
 239                     fail();
 240                 } catch (IllegalArgumentException e) {
 241                 }
 242             }
 243         }.test();
 244     }
 245
 246     public void testDescendingMapSerialization() {
 247         String s = "aced0005737200226a6176612e7574696c2e547265654d61702444657363656e6"
 248                 + "4696e675375624d61700cab946d1f0f9d0c0200014c001172657665727365436f6"
 249                 + "d70617261746f727400164c6a6176612f7574696c2f436f6d70617261746f723b7"
 250                 + "87200216a6176612e7574696c2e547265654d6170244e6176696761626c6553756"
 251                 + "24d6170e2d0a70e64210e080200075a000966726f6d53746172745a000b6869496"
 252                 + "e636c75736976655a000b6c6f496e636c75736976655a0005746f456e644c00026"
 253                 + "8697400124c6a6176612f6c616e672f4f626a6563743b4c00026c6f71007e00034"
 254                 + "c00016d7400134c6a6176612f7574696c2f547265654d61703b787001010101707"
 255                 + "0737200116a6176612e7574696c2e547265654d61700cc1f63e2d256ae60300014"
 256                 + "c000a636f6d70617261746f7271007e000178707372002a6a6176612e6c616e672"
 257                 + "e537472696e672443617365496e73656e736974697665436f6d70617261746f727"
 258                 + "7035c7d5c50e5ce02000078707704000000027400016171007e000a74000162710"
 259                 + "07e000b78737200286a6176612e7574696c2e436f6c6c656374696f6e732452657"
 260                 + "665727365436f6d70617261746f7232000003fa6c354d510200014c0003636d707"
 261                 + "1007e0001787071007e0009";
 262         TreeMap<String,String> map = new TreeMap<String, String>(
 263                 String.CASE_INSENSITIVE_ORDER);
 264         map.put("a", "a");
 265         map.put("b", "b");
 266         NavigableMap<String, String> descendingMap = map.descendingMap();
 267         new SerializableTester<NavigableMap<String, String>>(descendingMap, s) {
 268             @Override protected void verify(NavigableMap<String, String> deserialized) {
 269                 assertEquals("b", deserialized.navigableKeySet().first());
 270             }
 271         }.test();
 272     }
 273 }
 274