1/*
2 * Copyright (C) 2007 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.collect;
18
19import static com.google.common.collect.Maps.transformEntries;
20import static com.google.common.collect.testing.testers.CollectionIteratorTester.getIteratorUnknownOrderRemoveSupportedMethod;
21import static org.junit.contrib.truth.Truth.ASSERT;
22
23import com.google.common.annotations.GwtCompatible;
24import com.google.common.annotations.GwtIncompatible;
25import com.google.common.base.Equivalence;
26import com.google.common.base.Equivalences;
27import com.google.common.base.Function;
28import com.google.common.base.Functions;
29import com.google.common.base.Predicate;
30import com.google.common.base.Predicates;
31import com.google.common.collect.Maps.EntryTransformer;
32import com.google.common.collect.Maps.ValueDifferenceImpl;
33import com.google.common.collect.SetsTest.Derived;
34import com.google.common.collect.testing.MapTestSuiteBuilder;
35import com.google.common.collect.testing.SortedMapInterfaceTest;
36import com.google.common.collect.testing.TestStringMapGenerator;
37import com.google.common.collect.testing.features.CollectionSize;
38import com.google.common.collect.testing.features.MapFeature;
39import com.google.common.testing.EqualsTester;
40import com.google.common.testing.NullPointerTester;
41
42import junit.framework.Test;
43import junit.framework.TestCase;
44import junit.framework.TestSuite;
45
46import java.io.IOException;
47import java.lang.reflect.Field;
48import java.util.Arrays;
49import java.util.Collections;
50import java.util.Comparator;
51import java.util.EnumMap;
52import java.util.Enumeration;
53import java.util.HashMap;
54import java.util.IdentityHashMap;
55import java.util.Iterator;
56import java.util.LinkedHashMap;
57import java.util.List;
58import java.util.Map;
59import java.util.Map.Entry;
60import java.util.Properties;
61import java.util.Set;
62import java.util.SortedMap;
63import java.util.TreeMap;
64import java.util.concurrent.ConcurrentMap;
65
66/**
67 * Unit test for {@code Maps}.
68 *
69 * @author Kevin Bourrillion
70 * @author Mike Bostock
71 * @author Jared Levy
72 */
73@GwtCompatible(emulated = true)
74public class MapsTest extends TestCase {
75
76  private static final Comparator<Integer> SOME_COMPARATOR =
77      Collections.reverseOrder();
78
79  public void testHashMap() {
80    HashMap<Integer, Integer> map = Maps.newHashMap();
81    assertEquals(Collections.emptyMap(), map);
82  }
83
84  public void testHashMapWithInitialMap() {
85    Map<String, Integer> original = new TreeMap<String, Integer>();
86    original.put("a", 1);
87    original.put("b", 2);
88    original.put("c", 3);
89    HashMap<String, Integer> map = Maps.newHashMap(original);
90    assertEquals(original, map);
91  }
92
93  public void testHashMapGeneralizesTypes() {
94    Map<String, Integer> original = new TreeMap<String, Integer>();
95    original.put("a", 1);
96    original.put("b", 2);
97    original.put("c", 3);
98    HashMap<Object, Object> map =
99        Maps.newHashMap((Map<? extends Object, ? extends Object>) original);
100    assertEquals(original, map);
101  }
102
103  public void testCapacityForNegativeSizeFails() {
104    try {
105      Maps.capacity(-1);
106      fail("Negative expected size must result in IllegalArgumentException");
107    } catch (IllegalArgumentException ex) {
108    }
109  }
110
111  /**
112   * Tests that nHMWES makes hash maps large enough that adding the expected
113   * number of elements won't cause a rehash.
114   *
115   * This test may fail miserably on non-OpenJDK environments...
116   */
117  @GwtIncompatible("reflection")
118  public void testNewHashMapWithExpectedSize_wontGrow() throws Exception {
119    for (int size = 0; size < 200; size++) {
120      HashMap<Integer, Void> map1 = Maps.newHashMapWithExpectedSize(size);
121
122      int startSize = sizeOf(map1);
123
124      for (int i = 0; i < size; i++) {
125        map1.put(i, null);
126      }
127      assertEquals("table size after adding " + size + "elements",
128          startSize, sizeOf(map1));
129
130      /*
131       * Something slightly different happens when the entries are added all at
132       * once; make sure that passes too.
133       */
134      HashMap<Integer, Void> map2 = Maps.newHashMapWithExpectedSize(size);
135      map2.putAll(map1);
136      assertEquals("table size after adding " + size + "elements",
137          startSize, sizeOf(map2));
138    }
139  }
140
141  @GwtIncompatible("reflection")
142  private static int sizeOf(HashMap<?, ?> hashMap) throws Exception {
143    Field tableField = HashMap.class.getDeclaredField("table");
144    tableField.setAccessible(true);
145    Object[] table = (Object[]) tableField.get(hashMap);
146    return table.length;
147  }
148
149  public void testCapacityForLargeSizes() {
150    int[] largeExpectedSizes = new int[] {
151      Integer.MAX_VALUE / 2 - 1,
152      Integer.MAX_VALUE / 2,
153      Integer.MAX_VALUE / 2 + 1,
154      Integer.MAX_VALUE - 1,
155      Integer.MAX_VALUE};
156    for (int expectedSize : largeExpectedSizes) {
157      int capacity = Maps.capacity(expectedSize);
158      assertTrue(
159          "capacity (" + capacity + ") must be >= expectedSize (" + expectedSize + ")",
160          capacity >= expectedSize);
161    }
162  }
163
164  public void testLinkedHashMap() {
165    LinkedHashMap<Integer, Integer> map = Maps.newLinkedHashMap();
166    assertEquals(Collections.emptyMap(), map);
167  }
168
169  @SuppressWarnings("serial")
170  public void testLinkedHashMapWithInitialMap() {
171    Map<String, String> map = new LinkedHashMap<String, String>() {{
172      put("Hello", "World");
173      put("first", "second");
174      put("polygene", "lubricants");
175      put("alpha", "betical");
176    }};
177
178    LinkedHashMap<String, String> copy = Maps.newLinkedHashMap(map);
179
180    Iterator<Entry<String, String>> iter = copy.entrySet().iterator();
181    assertTrue(iter.hasNext());
182    Entry<String, String> entry = iter.next();
183    assertEquals("Hello", entry.getKey());
184    assertEquals("World", entry.getValue());
185    assertTrue(iter.hasNext());
186
187    entry = iter.next();
188    assertEquals("first", entry.getKey());
189    assertEquals("second", entry.getValue());
190    assertTrue(iter.hasNext());
191
192    entry = iter.next();
193    assertEquals("polygene", entry.getKey());
194    assertEquals("lubricants", entry.getValue());
195    assertTrue(iter.hasNext());
196
197    entry = iter.next();
198    assertEquals("alpha", entry.getKey());
199    assertEquals("betical", entry.getValue());
200    assertFalse(iter.hasNext());
201  }
202
203  public void testLinkedHashMapGeneralizesTypes() {
204    Map<String, Integer> original = new LinkedHashMap<String, Integer>();
205    original.put("a", 1);
206    original.put("b", 2);
207    original.put("c", 3);
208    HashMap<Object, Object> map
209        = Maps.<Object, Object>newLinkedHashMap(original);
210    assertEquals(original, map);
211  }
212
213  public void testIdentityHashMap() {
214    IdentityHashMap<Integer, Integer> map = Maps.newIdentityHashMap();
215    assertEquals(Collections.emptyMap(), map);
216  }
217
218  public void testConcurrentMap() {
219    ConcurrentMap<Integer, Integer> map = Maps.newConcurrentMap();
220    assertEquals(Collections.emptyMap(), map);
221  }
222
223  public void testTreeMap() {
224    TreeMap<Integer, Integer> map = Maps.newTreeMap();
225    assertEquals(Collections.emptyMap(), map);
226    assertNull(map.comparator());
227  }
228
229  public void testTreeMapDerived() {
230    TreeMap<Derived, Integer> map = Maps.newTreeMap();
231    assertEquals(Collections.emptyMap(), map);
232    map.put(new Derived("foo"), 1);
233    map.put(new Derived("bar"), 2);
234    ASSERT.that(map.keySet()).hasContentsInOrder(
235        new Derived("bar"), new Derived("foo"));
236    ASSERT.that(map.values()).hasContentsInOrder(2, 1);
237    assertNull(map.comparator());
238  }
239
240  public void testTreeMapNonGeneric() {
241    TreeMap<LegacyComparable, Integer> map = Maps.newTreeMap();
242    assertEquals(Collections.emptyMap(), map);
243    map.put(new LegacyComparable("foo"), 1);
244    map.put(new LegacyComparable("bar"), 2);
245    ASSERT.that(map.keySet()).hasContentsInOrder(
246        new LegacyComparable("bar"), new LegacyComparable("foo"));
247    ASSERT.that(map.values()).hasContentsInOrder(2, 1);
248    assertNull(map.comparator());
249  }
250
251  public void testTreeMapWithComparator() {
252    TreeMap<Integer, Integer> map = Maps.newTreeMap(SOME_COMPARATOR);
253    assertEquals(Collections.emptyMap(), map);
254    assertSame(SOME_COMPARATOR, map.comparator());
255  }
256
257  public void testTreeMapWithInitialMap() {
258    SortedMap<Integer, Integer> map = Maps.newTreeMap();
259    map.put(5, 10);
260    map.put(3, 20);
261    map.put(1, 30);
262    TreeMap<Integer, Integer> copy = Maps.newTreeMap(map);
263    assertEquals(copy, map);
264    assertSame(copy.comparator(), map.comparator());
265  }
266
267  public enum SomeEnum { SOME_INSTANCE }
268
269  public void testEnumMap() {
270    EnumMap<SomeEnum, Integer> map = Maps.newEnumMap(SomeEnum.class);
271    assertEquals(Collections.emptyMap(), map);
272    map.put(SomeEnum.SOME_INSTANCE, 0);
273    assertEquals(Collections.singletonMap(SomeEnum.SOME_INSTANCE, 0), map);
274  }
275
276  public void testEnumMapNullClass() {
277    try {
278      Maps.<SomeEnum, Long>newEnumMap((Class<MapsTest.SomeEnum>) null);
279      fail("no exception thrown");
280    } catch (NullPointerException expected) {
281    }
282  }
283
284  public void testEnumMapWithInitialEnumMap() {
285    EnumMap<SomeEnum, Integer> original = Maps.newEnumMap(SomeEnum.class);
286    original.put(SomeEnum.SOME_INSTANCE, 0);
287    EnumMap<SomeEnum, Integer> copy = Maps.newEnumMap(original);
288    assertEquals(original, copy);
289  }
290
291  public void testEnumMapWithInitialEmptyEnumMap() {
292    EnumMap<SomeEnum, Integer> original = Maps.newEnumMap(SomeEnum.class);
293    EnumMap<SomeEnum, Integer> copy = Maps.newEnumMap(original);
294    assertEquals(original, copy);
295    assertNotSame(original, copy);
296  }
297
298  public void testEnumMapWithInitialMap() {
299    HashMap<SomeEnum, Integer> original = Maps.newHashMap();
300    original.put(SomeEnum.SOME_INSTANCE, 0);
301    EnumMap<SomeEnum, Integer> copy = Maps.newEnumMap(original);
302    assertEquals(original, copy);
303  }
304
305  public void testEnumMapWithInitialEmptyMap() {
306    Map<SomeEnum, Integer> original = Maps.newHashMap();
307    try {
308      Maps.newEnumMap(original);
309      fail("Empty map must result in an IllegalArgumentException");
310    } catch (IllegalArgumentException expected) {}
311  }
312
313  @GwtIncompatible("NullPointerTester")
314  public void testNullPointerExceptions() throws Exception {
315    NullPointerTester tester = new NullPointerTester();
316    tester.setDefault(BiMap.class, ImmutableBiMap.of());
317    tester.setDefault(EntryTransformer.class, ALWAYS_NULL);
318    tester.setDefault(Equivalence.class, Equivalences.equals());
319    tester.setDefault(SortedMap.class, Maps.newTreeMap());
320    tester.ignore(Maps.class.getDeclaredMethod("uniqueIndex", Object.class, Function.class));
321    tester.testAllPublicStaticMethods(Maps.class);
322  }
323
324  private static final EntryTransformer<Object, Object, Object> ALWAYS_NULL =
325      new EntryTransformer<Object, Object, Object>() {
326        @Override
327        public Object transformEntry(Object k, Object v1) {
328          return null;
329        }
330      };
331
332  private static final Map<Integer, Integer> EMPTY
333      = Collections.emptyMap();
334  private static final Map<Integer, Integer> SINGLETON
335      = Collections.singletonMap(1, 2);
336
337  public void testMapDifferenceEmptyEmpty() {
338    MapDifference<Integer, Integer> diff = Maps.difference(EMPTY, EMPTY);
339    assertTrue(diff.areEqual());
340    assertEquals(EMPTY, diff.entriesOnlyOnLeft());
341    assertEquals(EMPTY, diff.entriesOnlyOnRight());
342    assertEquals(EMPTY, diff.entriesInCommon());
343    assertEquals(EMPTY, diff.entriesDiffering());
344    assertEquals("equal", diff.toString());
345  }
346
347  public void testMapDifferenceEmptySingleton() {
348    MapDifference<Integer, Integer> diff = Maps.difference(EMPTY, SINGLETON);
349    assertFalse(diff.areEqual());
350    assertEquals(EMPTY, diff.entriesOnlyOnLeft());
351    assertEquals(SINGLETON, diff.entriesOnlyOnRight());
352    assertEquals(EMPTY, diff.entriesInCommon());
353    assertEquals(EMPTY, diff.entriesDiffering());
354    assertEquals("not equal: only on right={1=2}", diff.toString());
355  }
356
357  public void testMapDifferenceSingletonEmpty() {
358    MapDifference<Integer, Integer> diff = Maps.difference(SINGLETON, EMPTY);
359    assertFalse(diff.areEqual());
360    assertEquals(SINGLETON, diff.entriesOnlyOnLeft());
361    assertEquals(EMPTY, diff.entriesOnlyOnRight());
362    assertEquals(EMPTY, diff.entriesInCommon());
363    assertEquals(EMPTY, diff.entriesDiffering());
364    assertEquals("not equal: only on left={1=2}", diff.toString());
365  }
366
367  public void testMapDifferenceTypical() {
368    Map<Integer, String> left = ImmutableMap.of(
369        1, "a", 2, "b", 3, "c", 4, "d", 5, "e");
370    Map<Integer, String> right = ImmutableMap.of(
371        1, "a", 3, "f", 5, "g", 6, "z");
372
373    MapDifference<Integer, String> diff1 = Maps.difference(left, right);
374    assertFalse(diff1.areEqual());
375    assertEquals(ImmutableMap.of(2, "b", 4, "d"), diff1.entriesOnlyOnLeft());
376    assertEquals(ImmutableMap.of(6, "z"), diff1.entriesOnlyOnRight());
377    assertEquals(ImmutableMap.of(1, "a"), diff1.entriesInCommon());
378    assertEquals(ImmutableMap.of(3,
379        ValueDifferenceImpl.create("c", "f"), 5,
380        ValueDifferenceImpl.create("e", "g")),
381        diff1.entriesDiffering());
382    assertEquals("not equal: only on left={2=b, 4=d}: only on right={6=z}: "
383        + "value differences={3=(c, f), 5=(e, g)}", diff1.toString());
384
385    MapDifference<Integer, String> diff2 = Maps.difference(right, left);
386    assertFalse(diff2.areEqual());
387    assertEquals(ImmutableMap.of(6, "z"), diff2.entriesOnlyOnLeft());
388    assertEquals(ImmutableMap.of(2, "b", 4, "d"), diff2.entriesOnlyOnRight());
389    assertEquals(ImmutableMap.of(1, "a"), diff2.entriesInCommon());
390    assertEquals(ImmutableMap.of(3,
391        ValueDifferenceImpl.create("f", "c"), 5,
392        ValueDifferenceImpl.create("g", "e")),
393        diff2.entriesDiffering());
394    assertEquals("not equal: only on left={6=z}: only on right={2=b, 4=d}: "
395        + "value differences={3=(f, c), 5=(g, e)}", diff2.toString());
396  }
397
398  public void testMapDifferenceEquals() {
399    Map<Integer, String> left = ImmutableMap.of(
400        1, "a", 2, "b", 3, "c", 4, "d", 5, "e");
401    Map<Integer, String> right = ImmutableMap.of(
402        1, "a", 3, "f", 5, "g", 6, "z");
403    Map<Integer, String> right2 = ImmutableMap.of(
404        1, "a", 3, "h", 5, "g", 6, "z");
405    MapDifference<Integer, String> original = Maps.difference(left, right);
406    MapDifference<Integer, String> same = Maps.difference(left, right);
407    MapDifference<Integer, String> reverse = Maps.difference(right, left);
408    MapDifference<Integer, String> diff2 = Maps.difference(left, right2);
409
410    new EqualsTester()
411        .addEqualityGroup(original, same)
412        .addEqualityGroup(reverse)
413        .addEqualityGroup(diff2)
414        .testEquals();
415  }
416
417  public void testMapDifferencePredicateTypical() {
418    Map<Integer, String> left = ImmutableMap.of(
419        1, "a", 2, "b", 3, "c", 4, "d", 5, "e");
420    Map<Integer, String> right = ImmutableMap.of(
421        1, "A", 3, "F", 5, "G", 6, "Z");
422
423    // TODO(kevinb): replace with Ascii.caseInsensitiveEquivalence() when it
424    // exists
425    Equivalence<String> caseInsensitiveEquivalence = Equivalences.equals().onResultOf(
426        new Function<String, String>() {
427          @Override public String apply(String input) {
428            return input.toLowerCase();
429          }
430        });
431
432    MapDifference<Integer, String> diff1 = Maps.difference(left, right,
433        caseInsensitiveEquivalence);
434    assertFalse(diff1.areEqual());
435    assertEquals(ImmutableMap.of(2, "b", 4, "d"), diff1.entriesOnlyOnLeft());
436    assertEquals(ImmutableMap.of(6, "Z"), diff1.entriesOnlyOnRight());
437    assertEquals(ImmutableMap.of(1, "a"), diff1.entriesInCommon());
438    assertEquals(ImmutableMap.of(3,
439        ValueDifferenceImpl.create("c", "F"), 5,
440        ValueDifferenceImpl.create("e", "G")),
441        diff1.entriesDiffering());
442    assertEquals("not equal: only on left={2=b, 4=d}: only on right={6=Z}: "
443        + "value differences={3=(c, F), 5=(e, G)}", diff1.toString());
444
445    MapDifference<Integer, String> diff2 = Maps.difference(right, left,
446        caseInsensitiveEquivalence);
447    assertFalse(diff2.areEqual());
448    assertEquals(ImmutableMap.of(6, "Z"), diff2.entriesOnlyOnLeft());
449    assertEquals(ImmutableMap.of(2, "b", 4, "d"), diff2.entriesOnlyOnRight());
450    assertEquals(ImmutableMap.of(1, "A"), diff2.entriesInCommon());
451    assertEquals(ImmutableMap.of(3,
452        ValueDifferenceImpl.create("F", "c"), 5,
453        ValueDifferenceImpl.create("G", "e")),
454        diff2.entriesDiffering());
455    assertEquals("not equal: only on left={6=Z}: only on right={2=b, 4=d}: "
456        + "value differences={3=(F, c), 5=(G, e)}", diff2.toString());
457  }
458
459  private static final SortedMap<Integer, Integer> SORTED_EMPTY = Maps.newTreeMap();
460  private static final SortedMap<Integer, Integer> SORTED_SINGLETON =
461      ImmutableSortedMap.of(1, 2);
462
463  public void testMapDifferenceOfSortedMapIsSorted() {
464    Map<Integer, Integer> map = SORTED_SINGLETON;
465    MapDifference<Integer, Integer> difference = Maps.difference(map, EMPTY);
466    assertTrue(difference instanceof SortedMapDifference);
467  }
468
469  public void testSortedMapDifferenceEmptyEmpty() {
470    SortedMapDifference<Integer, Integer> diff =
471        Maps.difference(SORTED_EMPTY, SORTED_EMPTY);
472    assertTrue(diff.areEqual());
473    assertEquals(SORTED_EMPTY, diff.entriesOnlyOnLeft());
474    assertEquals(SORTED_EMPTY, diff.entriesOnlyOnRight());
475    assertEquals(SORTED_EMPTY, diff.entriesInCommon());
476    assertEquals(SORTED_EMPTY, diff.entriesDiffering());
477    assertEquals("equal", diff.toString());
478  }
479
480  public void testSortedMapDifferenceEmptySingleton() {
481    SortedMapDifference<Integer, Integer> diff =
482        Maps.difference(SORTED_EMPTY, SORTED_SINGLETON);
483    assertFalse(diff.areEqual());
484    assertEquals(SORTED_EMPTY, diff.entriesOnlyOnLeft());
485    assertEquals(SORTED_SINGLETON, diff.entriesOnlyOnRight());
486    assertEquals(SORTED_EMPTY, diff.entriesInCommon());
487    assertEquals(SORTED_EMPTY, diff.entriesDiffering());
488    assertEquals("not equal: only on right={1=2}", diff.toString());
489  }
490
491  public void testSortedMapDifferenceSingletonEmpty() {
492    SortedMapDifference<Integer, Integer> diff =
493        Maps.difference(SORTED_SINGLETON, SORTED_EMPTY);
494    assertFalse(diff.areEqual());
495    assertEquals(SORTED_SINGLETON, diff.entriesOnlyOnLeft());
496    assertEquals(SORTED_EMPTY, diff.entriesOnlyOnRight());
497    assertEquals(SORTED_EMPTY, diff.entriesInCommon());
498    assertEquals(SORTED_EMPTY, diff.entriesDiffering());
499    assertEquals("not equal: only on left={1=2}", diff.toString());
500  }
501
502  public void testSortedMapDifferenceTypical() {
503    SortedMap<Integer, String> left =
504        ImmutableSortedMap.<Integer, String>reverseOrder()
505        .put(1, "a").put(2, "b").put(3, "c").put(4, "d").put(5, "e")
506        .build();
507
508    SortedMap<Integer, String> right =
509        ImmutableSortedMap.of(1, "a", 3, "f", 5, "g", 6, "z");
510
511    SortedMapDifference<Integer, String> diff1 =
512        Maps.difference(left, right);
513    assertFalse(diff1.areEqual());
514    ASSERT.that(diff1.entriesOnlyOnLeft().entrySet()).hasContentsInOrder(
515        Maps.immutableEntry(4, "d"), Maps.immutableEntry(2, "b"));
516    ASSERT.that(diff1.entriesOnlyOnRight().entrySet()).hasContentsInOrder(
517        Maps.immutableEntry(6, "z"));
518    ASSERT.that(diff1.entriesInCommon().entrySet()).hasContentsInOrder(
519        Maps.immutableEntry(1, "a"));
520    ASSERT.that(diff1.entriesDiffering().entrySet()).hasContentsInOrder(
521        Maps.immutableEntry(5, ValueDifferenceImpl.create("e", "g")),
522        Maps.immutableEntry(3, ValueDifferenceImpl.create("c", "f")));
523    assertEquals("not equal: only on left={4=d, 2=b}: only on right={6=z}: "
524        + "value differences={5=(e, g), 3=(c, f)}", diff1.toString());
525
526    SortedMapDifference<Integer, String> diff2 =
527        Maps.difference(right, left);
528    assertFalse(diff2.areEqual());
529    ASSERT.that(diff2.entriesOnlyOnLeft().entrySet()).hasContentsInOrder(
530        Maps.immutableEntry(6, "z"));
531    ASSERT.that(diff2.entriesOnlyOnRight().entrySet()).hasContentsInOrder(
532        Maps.immutableEntry(2, "b"), Maps.immutableEntry(4, "d"));
533    ASSERT.that(diff1.entriesInCommon().entrySet()).hasContentsInOrder(
534        Maps.immutableEntry(1, "a"));
535    assertEquals(ImmutableMap.of(
536            3, ValueDifferenceImpl.create("f", "c"),
537            5, ValueDifferenceImpl.create("g", "e")),
538        diff2.entriesDiffering());
539    assertEquals("not equal: only on left={6=z}: only on right={2=b, 4=d}: "
540        + "value differences={3=(f, c), 5=(g, e)}", diff2.toString());
541  }
542
543  public void testSortedMapDifferenceImmutable() {
544    SortedMap<Integer, String> left = Maps.newTreeMap(
545        ImmutableSortedMap.of(1, "a", 2, "b", 3, "c", 4, "d", 5, "e"));
546    SortedMap<Integer, String> right =
547        Maps.newTreeMap(ImmutableSortedMap.of(1, "a", 3, "f", 5, "g", 6, "z"));
548
549    SortedMapDifference<Integer, String> diff1 =
550        Maps.difference(left, right);
551    left.put(6, "z");
552    assertFalse(diff1.areEqual());
553    ASSERT.that(diff1.entriesOnlyOnLeft().entrySet()).hasContentsInOrder(
554        Maps.immutableEntry(2, "b"), Maps.immutableEntry(4, "d"));
555    ASSERT.that(diff1.entriesOnlyOnRight().entrySet()).hasContentsInOrder(
556        Maps.immutableEntry(6, "z"));
557    ASSERT.that(diff1.entriesInCommon().entrySet()).hasContentsInOrder(
558        Maps.immutableEntry(1, "a"));
559    ASSERT.that(diff1.entriesDiffering().entrySet()).hasContentsInOrder(
560        Maps.immutableEntry(3, ValueDifferenceImpl.create("c", "f")),
561        Maps.immutableEntry(5, ValueDifferenceImpl.create("e", "g")));
562    try {
563      diff1.entriesInCommon().put(7, "x");
564      fail();
565    } catch (UnsupportedOperationException expected) {
566    }
567    try {
568      diff1.entriesOnlyOnLeft().put(7, "x");
569      fail();
570    } catch (UnsupportedOperationException expected) {
571    }
572    try {
573      diff1.entriesOnlyOnRight().put(7, "x");
574      fail();
575    } catch (UnsupportedOperationException expected) {
576    }
577  }
578
579  public void testSortedMapDifferenceEquals() {
580    SortedMap<Integer, String> left =
581        ImmutableSortedMap.of(1, "a", 2, "b", 3, "c", 4, "d", 5, "e");
582    SortedMap<Integer, String> right =
583        ImmutableSortedMap.of(1, "a", 3, "f", 5, "g", 6, "z");
584    SortedMap<Integer, String> right2 =
585        ImmutableSortedMap.of(1, "a", 3, "h", 5, "g", 6, "z");
586    SortedMapDifference<Integer, String> original =
587        Maps.difference(left, right);
588    SortedMapDifference<Integer, String> same =
589        Maps.difference(left, right);
590    SortedMapDifference<Integer, String> reverse =
591        Maps.difference(right, left);
592    SortedMapDifference<Integer, String> diff2 =
593        Maps.difference(left, right2);
594
595    new EqualsTester()
596        .addEqualityGroup(original, same)
597        .addEqualityGroup(reverse)
598        .addEqualityGroup(diff2)
599        .testEquals();
600  }
601
602  private static final BiMap<Integer, String> INT_TO_STRING_MAP =
603      new ImmutableBiMap.Builder<Integer, String>()
604          .put(1, "one")
605          .put(2, "two")
606          .put(3, "three")
607          .build();
608
609  public void testUniqueIndexCollection() {
610    ImmutableMap<Integer, String> outputMap =
611        Maps.uniqueIndex(INT_TO_STRING_MAP.values(),
612            Functions.forMap(INT_TO_STRING_MAP.inverse()));
613    assertEquals(INT_TO_STRING_MAP, outputMap);
614  }
615
616  public void testUniqueIndexIterable() {
617    ImmutableMap<Integer, String> outputMap =
618        Maps.uniqueIndex(new Iterable<String>() {
619          @Override
620          public Iterator<String> iterator() {
621            return INT_TO_STRING_MAP.values().iterator();
622          }
623        },
624        Functions.forMap(INT_TO_STRING_MAP.inverse()));
625    assertEquals(INT_TO_STRING_MAP, outputMap);
626  }
627
628  // NOTE: evil, never do this
629  private abstract static class IterableIterator<T>
630      extends ForwardingIterator<T> implements Iterable<T> {
631    @Override
632    public Iterator<T> iterator() {
633      return this;
634    }
635  }
636
637  @SuppressWarnings("deprecation") // that is the purpose of this test
638  public void testUniqueIndexIterableIterator() {
639    ImmutableMap<Integer, String> outputMap =
640        Maps.uniqueIndex(new IterableIterator<String>() {
641          private final Iterator<String> iterator = INT_TO_STRING_MAP.values().iterator();
642
643          public Iterator<String> delegate() {
644            return iterator;
645          }
646        },
647        Functions.forMap(INT_TO_STRING_MAP.inverse()));
648    assertEquals(INT_TO_STRING_MAP, outputMap);
649  }
650
651  public void testUniqueIndexIterator() {
652    ImmutableMap<Integer, String> outputMap =
653        Maps.uniqueIndex(INT_TO_STRING_MAP.values().iterator(),
654            Functions.forMap(INT_TO_STRING_MAP.inverse()));
655    assertEquals(INT_TO_STRING_MAP, outputMap);
656  }
657
658  /** Can't create the map if more than one value maps to the same key. */
659  public void testUniqueIndexDuplicates() {
660    try {
661      Maps.uniqueIndex(ImmutableSet.of("one", "uno"), Functions.constant(1));
662      fail();
663    } catch (IllegalArgumentException expected) {
664    }
665  }
666
667  /** Null values are not allowed. */
668  public void testUniqueIndexNullValue() {
669    List<String> listWithNull = Lists.newArrayList((String) null);
670    try {
671      Maps.uniqueIndex(listWithNull, Functions.constant(1));
672      fail();
673    } catch (NullPointerException expected) {
674    }
675  }
676
677  /** Null keys aren't allowed either. */
678  public void testUniqueIndexNullKey() {
679    List<String> oneStringList = Lists.newArrayList("foo");
680    try {
681      Maps.uniqueIndex(oneStringList, Functions.constant(null));
682      fail();
683    } catch (NullPointerException expected) {
684    }
685  }
686
687  @GwtIncompatible("Maps.fromProperties")
688  @SuppressWarnings("deprecation") // StringBufferInputStream
689  public void testFromProperties() throws IOException {
690    Properties testProp = new Properties();
691
692    Map<String, String> result = Maps.fromProperties(testProp);
693    assertTrue(result.isEmpty());
694    testProp.setProperty("first", "true");
695
696    result = Maps.fromProperties(testProp);
697    assertEquals("true", result.get("first"));
698    assertEquals(1, result.size());
699    testProp.setProperty("second", "null");
700
701    result = Maps.fromProperties(testProp);
702    assertEquals("true", result.get("first"));
703    assertEquals("null", result.get("second"));
704    assertEquals(2, result.size());
705
706    // Now test values loaded from a stream.
707    String props = "test\n second = 2\n Third item :   a short  phrase   ";
708
709    // TODO: change to StringReader in Java 1.6
710    testProp.load(new java.io.StringBufferInputStream(props));
711
712    result = Maps.fromProperties(testProp);
713    assertEquals(4, result.size());
714    assertEquals("true", result.get("first"));
715    assertEquals("", result.get("test"));
716    assertEquals("2", result.get("second"));
717    assertEquals("item :   a short  phrase   ", result.get("Third"));
718    assertFalse(result.containsKey("not here"));
719
720    // Test loading system properties
721    result = Maps.fromProperties(System.getProperties());
722    assertTrue(result.containsKey("java.version"));
723
724    // Test that defaults work, too.
725    testProp = new Properties(System.getProperties());
726    String override = "test\njava.version : hidden";
727
728    // TODO: change to StringReader in Java 1.6
729    testProp.load(new java.io.StringBufferInputStream(override));
730
731    result = Maps.fromProperties(testProp);
732    assertTrue(result.size() > 2);
733    assertEquals("", result.get("test"));
734    assertEquals("hidden", result.get("java.version"));
735    assertNotSame(System.getProperty("java.version"),
736                  result.get("java.version"));
737  }
738
739  @GwtIncompatible("Maps.fromProperties")
740  @SuppressWarnings("serial") // never serialized
741  public void testFromPropertiesNullKey() {
742    Properties properties = new Properties() {
743      @Override public Enumeration<?> propertyNames() {
744        return Iterators.asEnumeration(
745            Arrays.asList(null, "first", "second").iterator());
746      }
747    };
748    properties.setProperty("first", "true");
749    properties.setProperty("second", "null");
750
751    try {
752      Maps.fromProperties(properties);
753      fail();
754    } catch (NullPointerException expected) {}
755  }
756
757  @GwtIncompatible("Maps.fromProperties")
758  @SuppressWarnings("serial") // never serialized
759  public void testFromPropertiesNonStringKeys() {
760    Properties properties = new Properties() {
761      @Override public Enumeration<?> propertyNames() {
762        return Iterators.asEnumeration(
763            Arrays.<Object>asList(Integer.valueOf(123), "first").iterator());
764      }
765    };
766
767    try {
768      Maps.fromProperties(properties);
769      fail();
770    } catch (ClassCastException expected) {}
771  }
772
773  /**
774   * Constructs a "nefarious" map entry with the specified key and value,
775   * meaning an entry that is suitable for testing that map entries cannot be
776   * modified via a nefarious implementation of equals. This is used for testing
777   * unmodifiable collections of map entries; for example, it should not be
778   * possible to access the raw (modifiable) map entry via a nefarious equals
779   * method.
780   */
781  public static <K, V> Map.Entry<K, V> nefariousEntry(
782      final K key, final V value) {
783    return new AbstractMapEntry<K, V>() {
784        @Override public K getKey() {
785          return key;
786        }
787        @Override public V getValue() {
788          return value;
789        }
790        @Override public V setValue(V value) {
791          throw new UnsupportedOperationException();
792        }
793        @SuppressWarnings("unchecked")
794        @Override public boolean equals(Object o) {
795          if (o instanceof Map.Entry<?, ?>) {
796            Map.Entry<K, V> e = (Map.Entry<K, V>) o;
797            e.setValue(value); // muhahaha!
798          }
799          return super.equals(o);
800        }
801      };
802  }
803
804  public void testUnmodifiableBiMap() {
805    BiMap<Integer, String> mod = HashBiMap.create();
806    mod.put(1, "one");
807    mod.put(2, "two");
808    mod.put(3, "three");
809
810    BiMap<Number, String> unmod = Maps.<Number, String>unmodifiableBiMap(mod);
811
812    /* No aliasing on inverse operations. */
813    assertSame(unmod.inverse(), unmod.inverse());
814    assertSame(unmod, unmod.inverse().inverse());
815
816    /* Unmodifiable is a view. */
817    mod.put(4, "four");
818    assertEquals(true, unmod.get(4).equals("four"));
819    assertEquals(true, unmod.inverse().get("four").equals(4));
820
821    /* UnsupportedOperationException on direct modifications. */
822    try {
823      unmod.put(4, "four");
824      fail("UnsupportedOperationException expected");
825    } catch (UnsupportedOperationException expected) {}
826    try {
827      unmod.forcePut(4, "four");
828      fail("UnsupportedOperationException expected");
829    } catch (UnsupportedOperationException expected) {}
830    try {
831      unmod.putAll(Collections.singletonMap(4, "four"));
832      fail("UnsupportedOperationException expected");
833    } catch (UnsupportedOperationException expected) {}
834
835    /* UnsupportedOperationException on indirect modifications. */
836    BiMap<String, Number> inverse = unmod.inverse();
837    try {
838      inverse.put("four", 4);
839      fail("UnsupportedOperationException expected");
840    } catch (UnsupportedOperationException expected) {}
841    try {
842      inverse.forcePut("four", 4);
843      fail("UnsupportedOperationException expected");
844    } catch (UnsupportedOperationException expected) {}
845    try {
846      inverse.putAll(Collections.singletonMap("four", 4));
847      fail("UnsupportedOperationException expected");
848    } catch (UnsupportedOperationException expected) {}
849    Set<String> values = unmod.values();
850    try {
851      values.remove("four");
852      fail("UnsupportedOperationException expected");
853    } catch (UnsupportedOperationException expected) {}
854    Set<Map.Entry<Number, String>> entries = unmod.entrySet();
855    Map.Entry<Number, String> entry = entries.iterator().next();
856    try {
857      entry.setValue("four");
858      fail("UnsupportedOperationException expected");
859    } catch (UnsupportedOperationException expected) {}
860    @SuppressWarnings("unchecked")
861    Map.Entry<Integer, String> entry2
862        = (Map.Entry<Integer, String>) entries.toArray()[0];
863    try {
864      entry2.setValue("four");
865      fail("UnsupportedOperationException expected");
866    } catch (UnsupportedOperationException expected) {}
867  }
868
869  public void testBiMapEntrySetIteratorRemove() {
870    BiMap<Integer, String> map = HashBiMap.create();
871    map.put(1, "one");
872    Set<Map.Entry<Integer, String>> entries = map.entrySet();
873    Iterator<Map.Entry<Integer, String>> iterator = entries.iterator();
874    Map.Entry<Integer, String> entry = iterator.next();
875    entry.setValue("two"); // changes the iterator's current entry value
876    assertEquals("two", map.get(1));
877    iterator.remove(); // removes the updated entry
878    assertTrue(map.isEmpty());
879  }
880
881  public void testImmutableEntry() {
882    Map.Entry<String, Integer> e = Maps.immutableEntry("foo", 1);
883    assertEquals("foo", e.getKey());
884    assertEquals(1, (int) e.getValue());
885    try {
886      e.setValue(2);
887      fail("UnsupportedOperationException expected");
888    } catch (UnsupportedOperationException expected) {}
889    assertEquals("foo=1", e.toString());
890    assertEquals(101575, e.hashCode());
891  }
892
893  public void testImmutableEntryNull() {
894    Map.Entry<String, Integer> e
895        = Maps.immutableEntry((String) null, (Integer) null);
896    assertNull(e.getKey());
897    assertNull(e.getValue());
898    try {
899      e.setValue(null);
900      fail("UnsupportedOperationException expected");
901    } catch (UnsupportedOperationException expected) {}
902    assertEquals("null=null", e.toString());
903    assertEquals(0, e.hashCode());
904  }
905
906  /** See {@link SynchronizedBiMapTest} for more tests. */
907  public void testSynchronizedBiMap() {
908    BiMap<String, Integer> bimap = HashBiMap.create();
909    bimap.put("one", 1);
910    BiMap<String, Integer> sync = Maps.synchronizedBiMap(bimap);
911    bimap.put("two", 2);
912    sync.put("three", 3);
913    assertEquals(ImmutableSet.of(1, 2, 3), bimap.inverse().keySet());
914    assertEquals(ImmutableSet.of(1, 2, 3), sync.inverse().keySet());
915  }
916
917  private static final Predicate<String> NOT_LENGTH_3
918      = new Predicate<String>() {
919        @Override
920        public boolean apply(String input) {
921          return input == null || input.length() != 3;
922        }
923      };
924
925  private static final Predicate<Integer> EVEN
926      = new Predicate<Integer>() {
927        @Override
928        public boolean apply(Integer input) {
929          return input == null || input % 2 == 0;
930        }
931      };
932
933  private static final Predicate<Entry<String, Integer>> CORRECT_LENGTH
934      = new Predicate<Entry<String, Integer>>() {
935        @Override
936        public boolean apply(Entry<String, Integer> input) {
937          return input.getKey().length() == input.getValue();
938        }
939      };
940
941  public void testFilteredKeysIllegalPut() {
942    Map<String, Integer> unfiltered = Maps.newHashMap();
943    Map<String, Integer> filtered = Maps.filterKeys(unfiltered, NOT_LENGTH_3);
944    filtered.put("a", 1);
945    filtered.put("b", 2);
946    assertEquals(ImmutableMap.of("a", 1, "b", 2), filtered);
947
948    try {
949      filtered.put("yyy", 3);
950      fail();
951    } catch (IllegalArgumentException expected) {}
952
953    try {
954      filtered.putAll(ImmutableMap.of("c", 3, "zzz", 4, "b", 5));
955      fail();
956    } catch (IllegalArgumentException expected) {}
957
958    assertEquals(ImmutableMap.of("a", 1, "b", 2), filtered);
959  }
960
961  public void testFilteredKeysChangeFiltered() {
962    Map<String, Integer> unfiltered = Maps.newHashMap();
963    Map<String, Integer> filtered = Maps.filterKeys(unfiltered, NOT_LENGTH_3);
964    unfiltered.put("two", 2);
965    unfiltered.put("three", 3);
966    unfiltered.put("four", 4);
967    assertEquals(ImmutableMap.of("two", 2, "three", 3, "four", 4), unfiltered);
968    assertEquals(ImmutableMap.of("three", 3, "four", 4), filtered);
969
970    unfiltered.remove("three");
971    assertEquals(ImmutableMap.of("two", 2, "four", 4), unfiltered);
972    assertEquals(ImmutableMap.of("four", 4), filtered);
973
974    unfiltered.clear();
975    assertEquals(ImmutableMap.of(), unfiltered);
976    assertEquals(ImmutableMap.of(), filtered);
977  }
978
979  public void testFilteredKeysChangeUnfiltered() {
980    Map<String, Integer> unfiltered = Maps.newHashMap();
981    Map<String, Integer> filtered = Maps.filterKeys(unfiltered, NOT_LENGTH_3);
982    unfiltered.put("two", 2);
983    unfiltered.put("three", 3);
984    unfiltered.put("four", 4);
985    assertEquals(ImmutableMap.of("two", 2, "three", 3, "four", 4), unfiltered);
986    assertEquals(ImmutableMap.of("three", 3, "four", 4), filtered);
987
988    filtered.remove("three");
989    assertEquals(ImmutableMap.of("two", 2, "four", 4), unfiltered);
990    assertEquals(ImmutableMap.of("four", 4), filtered);
991
992    filtered.clear();
993    assertEquals(ImmutableMap.of("two", 2), unfiltered);
994    assertEquals(ImmutableMap.of(), filtered);
995  }
996
997  public void testFilteredValuesIllegalPut() {
998    Map<String, Integer> unfiltered = Maps.newHashMap();
999    Map<String, Integer> filtered = Maps.filterValues(unfiltered, EVEN);
1000    filtered.put("a", 2);
1001    unfiltered.put("b", 4);
1002    unfiltered.put("c", 5);
1003    assertEquals(ImmutableMap.of("a", 2, "b", 4), filtered);
1004
1005    try {
1006      filtered.put("yyy", 3);
1007      fail();
1008    } catch (IllegalArgumentException expected) {}
1009
1010    try {
1011      filtered.putAll(ImmutableMap.of("c", 4, "zzz", 5, "b", 6));
1012      fail();
1013    } catch (IllegalArgumentException expected) {}
1014
1015    assertEquals(ImmutableMap.of("a", 2, "b", 4), filtered);
1016  }
1017
1018  public void testFilteredValuesIllegalSetValue() {
1019    Map<String, Integer> unfiltered = Maps.newHashMap();
1020    Map<String, Integer> filtered = Maps.filterValues(unfiltered, EVEN);
1021    filtered.put("a", 2);
1022    filtered.put("b", 4);
1023    assertEquals(ImmutableMap.of("a", 2, "b", 4), filtered);
1024
1025    Entry<String, Integer> entry = filtered.entrySet().iterator().next();
1026    try {
1027      entry.setValue(5);
1028      fail();
1029    } catch (IllegalArgumentException expected) {}
1030
1031    assertEquals(ImmutableMap.of("a", 2, "b", 4), filtered);
1032  }
1033
1034  public void testFilteredValuesClear() {
1035    Map<String, Integer> unfiltered = Maps.newHashMap();
1036    unfiltered.put("one", 1);
1037    unfiltered.put("two", 2);
1038    unfiltered.put("three", 3);
1039    unfiltered.put("four", 4);
1040    Map<String, Integer> filtered = Maps.filterValues(unfiltered, EVEN);
1041    assertEquals(ImmutableMap.of("one", 1, "two", 2, "three", 3, "four", 4),
1042        unfiltered);
1043    assertEquals(ImmutableMap.of("two", 2, "four", 4), filtered);
1044
1045    filtered.clear();
1046    assertEquals(ImmutableMap.of("one", 1, "three", 3), unfiltered);
1047    assertTrue(filtered.isEmpty());
1048  }
1049
1050  public void testFilteredEntriesIllegalPut() {
1051    Map<String, Integer> unfiltered = Maps.newHashMap();
1052    unfiltered.put("cat", 3);
1053    unfiltered.put("dog", 2);
1054    unfiltered.put("horse", 5);
1055    Map<String, Integer> filtered
1056        = Maps.filterEntries(unfiltered, CORRECT_LENGTH);
1057    assertEquals(ImmutableMap.of("cat", 3, "horse", 5), filtered);
1058
1059    filtered.put("chicken", 7);
1060    assertEquals(ImmutableMap.of("cat", 3, "horse", 5, "chicken", 7), filtered);
1061
1062    try {
1063      filtered.put("cow", 7);
1064      fail();
1065    } catch (IllegalArgumentException expected) {}
1066    assertEquals(ImmutableMap.of("cat", 3, "horse", 5, "chicken", 7), filtered);
1067
1068    try {
1069      filtered.putAll(ImmutableMap.of("sheep", 5, "cow", 7));
1070      fail();
1071    } catch (IllegalArgumentException expected) {}
1072    assertEquals(ImmutableMap.of("cat", 3, "horse", 5, "chicken", 7), filtered);
1073  }
1074
1075  public void testFilteredEntriesObjectPredicate() {
1076    Map<String, Integer> unfiltered = Maps.newHashMap();
1077    unfiltered.put("cat", 3);
1078    unfiltered.put("dog", 2);
1079    unfiltered.put("horse", 5);
1080    Predicate<Object> predicate = Predicates.alwaysFalse();
1081    Map<String, Integer> filtered
1082        = Maps.filterEntries(unfiltered, predicate);
1083    assertTrue(filtered.isEmpty());
1084  }
1085
1086  public void testFilteredEntriesWildCardEntryPredicate() {
1087    Map<String, Integer> unfiltered = Maps.newHashMap();
1088    unfiltered.put("cat", 3);
1089    unfiltered.put("dog", 2);
1090    unfiltered.put("horse", 5);
1091    Predicate<Entry<?, ?>> predicate = new Predicate<Entry<?, ?>>() {
1092      @Override
1093      public boolean apply(Entry<?, ?> input) {
1094        return "cat".equals(input.getKey())
1095            || Integer.valueOf(2) == input.getValue();
1096      }
1097    };
1098    Map<String, Integer> filtered
1099        = Maps.filterEntries(unfiltered, predicate);
1100    assertEquals(ImmutableMap.of("cat", 3, "dog", 2), filtered);
1101  }
1102
1103  public void testTransformValues() {
1104    Map<String, Integer> map = ImmutableMap.of("a", 4, "b", 9);
1105    Function<Integer, Double> sqrt = new Function<Integer, Double>() {
1106      @Override
1107      public Double apply(Integer in) {
1108        return Math.sqrt(in);
1109      }
1110    };
1111    Map<String, Double> transformed = Maps.transformValues(map, sqrt);
1112
1113    assertEquals(ImmutableMap.of("a", 2.0, "b", 3.0), transformed);
1114  }
1115
1116  public void testTransformValuesSecretlySorted() {
1117    Map<String, Integer> map = ImmutableSortedMap.of("a", 4, "b", 9);
1118    Function<Integer, Double> sqrt = new Function<Integer, Double>() {
1119      @Override
1120      public Double apply(Integer in) {
1121        return Math.sqrt(in);
1122      }
1123    };
1124    Map<String, Double> transformed = Maps.transformValues(map, sqrt);
1125
1126    assertEquals(ImmutableMap.of("a", 2.0, "b", 3.0), transformed);
1127    assertTrue(transformed instanceof SortedMap);
1128  }
1129
1130  public void testTransformEntries() {
1131    Map<String, String> map = ImmutableMap.of("a", "4", "b", "9");
1132    EntryTransformer<String, String, String> concat =
1133        new EntryTransformer<String, String, String>() {
1134          @Override
1135          public String transformEntry(String key, String value) {
1136            return key + value;
1137          }
1138        };
1139    Map<String, String> transformed = Maps.transformEntries(map, concat);
1140
1141    assertEquals(ImmutableMap.of("a", "a4", "b", "b9"), transformed);
1142  }
1143
1144  public void testTransformEntriesSecretlySorted() {
1145    Map<String, String> map = ImmutableSortedMap.of("a", "4", "b", "9");
1146    EntryTransformer<String, String, String> concat =
1147        new EntryTransformer<String, String, String>() {
1148          @Override
1149          public String transformEntry(String key, String value) {
1150            return key + value;
1151          }
1152        };
1153    Map<String, String> transformed = Maps.transformEntries(map, concat);
1154
1155    assertEquals(ImmutableMap.of("a", "a4", "b", "b9"), transformed);
1156    assertTrue(transformed instanceof SortedMap);
1157  }
1158
1159  public void testTransformEntriesGenerics() {
1160    Map<Object, Object> map1 = ImmutableMap.<Object, Object>of(1, 2);
1161    Map<Object, Number> map2 = ImmutableMap.<Object, Number>of(1, 2);
1162    Map<Object, Integer> map3 = ImmutableMap.<Object, Integer>of(1, 2);
1163    Map<Number, Object> map4 = ImmutableMap.<Number, Object>of(1, 2);
1164    Map<Number, Number> map5 = ImmutableMap.<Number, Number>of(1, 2);
1165    Map<Number, Integer> map6 = ImmutableMap.<Number, Integer>of(1, 2);
1166    Map<Integer, Object> map7 = ImmutableMap.<Integer, Object>of(1, 2);
1167    Map<Integer, Number> map8 = ImmutableMap.<Integer, Number>of(1, 2);
1168    Map<Integer, Integer> map9 = ImmutableMap.<Integer, Integer>of(1, 2);
1169    Map<? extends Number, ? extends Number> map0 = ImmutableMap.of(1, 2);
1170
1171    EntryTransformer<Number, Number, Double> transformer =
1172        new EntryTransformer<Number, Number, Double>() {
1173          @Override
1174          public Double transformEntry(Number key, Number value) {
1175            return key.doubleValue() + value.doubleValue();
1176          }
1177        };
1178
1179    Map<Object, Double> objectKeyed;
1180    Map<Number, Double> numberKeyed;
1181    Map<Integer, Double> integerKeyed;
1182
1183    numberKeyed = transformEntries(map5, transformer);
1184    numberKeyed = transformEntries(map6, transformer);
1185    integerKeyed = transformEntries(map8, transformer);
1186    integerKeyed = transformEntries(map9, transformer);
1187
1188    Map<? extends Number, Double> wildcarded = transformEntries(map0, transformer);
1189
1190    // Can't loosen the key type:
1191    // objectKeyed = transformEntries(map5, transformer);
1192    // objectKeyed = transformEntries(map6, transformer);
1193    // objectKeyed = transformEntries(map8, transformer);
1194    // objectKeyed = transformEntries(map9, transformer);
1195    // numberKeyed = transformEntries(map8, transformer);
1196    // numberKeyed = transformEntries(map9, transformer);
1197
1198    // Can't loosen the value type:
1199    // Map<Number, Number> looseValued1 = transformEntries(map5, transformer);
1200    // Map<Number, Number> looseValued2 = transformEntries(map6, transformer);
1201    // Map<Integer, Number> looseValued3 = transformEntries(map8, transformer);
1202    // Map<Integer, Number> looseValued4 = transformEntries(map9, transformer);
1203
1204    // Can't call with too loose a key:
1205    // transformEntries(map1, transformer);
1206    // transformEntries(map2, transformer);
1207    // transformEntries(map3, transformer);
1208
1209    // Can't call with too loose a value:
1210    // transformEntries(map1, transformer);
1211    // transformEntries(map4, transformer);
1212    // transformEntries(map7, transformer);
1213  }
1214
1215  public void testTransformEntriesExample() {
1216    Map<String, Boolean> options =
1217        ImmutableMap.of("verbose", true, "sort", false);
1218    EntryTransformer<String, Boolean, String> flagPrefixer =
1219        new EntryTransformer<String, Boolean, String>() {
1220          @Override
1221          public String transformEntry(String key, Boolean value) {
1222            return value ? key : "no" + key;
1223          }
1224        };
1225    Map<String, String> transformed =
1226        Maps.transformEntries(options, flagPrefixer);
1227    assertEquals("{verbose=verbose, sort=nosort}", transformed.toString());
1228  }
1229
1230  // TestStringMapGenerator uses entries of the form "one=January" and so forth.
1231  // To test the filtered collections, we'll create a map containing the entries
1232  // they ask for, plus some bogus numeric entries. Then our predicates will
1233  // simply filter numeric entries back out.
1234
1235  private static ImmutableMap<String, String> ENTRIES_TO_FILTER_OUT =
1236      new ImmutableMap.Builder<String, String>()
1237          .put("0", "0")
1238          .put("1", "1")
1239          .put("2", "2")
1240          .build();
1241
1242  @GwtIncompatible("suite")
1243  public static class FilteredMapTests extends TestCase {
1244    public static Test suite() {
1245      TestSuite suite = new TestSuite();
1246
1247      suite.addTest(MapTestSuiteBuilder.using(
1248          new TestStringMapGenerator() {
1249            @Override protected Map<String, String> create(
1250                Entry<String, String>[] entries) {
1251              Map<String, String> map = Maps.newHashMap();
1252              for (Entry<String, String> entry : entries) {
1253                map.put(entry.getKey(), entry.getValue());
1254              }
1255              map.putAll(ENTRIES_TO_FILTER_OUT);
1256              return Maps.filterKeys(map, new Predicate<String>() {
1257                @Override
1258                public boolean apply(String input) {
1259                  return input == null
1260                      || (input.charAt(0) >= 'a' && input.charAt(0) <= 'z');
1261                }
1262              });
1263            }
1264          })
1265          .named("Maps.filterKeys")
1266          .withFeatures(
1267              CollectionSize.ANY,
1268              MapFeature.ALLOWS_NULL_KEYS,
1269              MapFeature.ALLOWS_NULL_VALUES,
1270              MapFeature.GENERAL_PURPOSE)
1271          .suppressing(getIteratorUnknownOrderRemoveSupportedMethod())
1272          .createTestSuite());
1273
1274      suite.addTest(MapTestSuiteBuilder.using(
1275          new TestStringMapGenerator() {
1276            @Override protected Map<String, String> create(
1277                Entry<String, String>[] entries) {
1278              Map<String, String> map = Maps.newHashMap();
1279              for (Entry<String, String> entry : entries) {
1280                map.put(entry.getKey(), entry.getValue());
1281              }
1282              map.putAll(ENTRIES_TO_FILTER_OUT);
1283              return Maps.filterValues(map, new Predicate<String>() {
1284                @Override
1285                public boolean apply(String input) {
1286                  return input == null
1287                      || (input.charAt(0) >= 'A' && input.charAt(0) <= 'Z');
1288                }
1289              });
1290            }
1291          })
1292          .named("Maps.filterValues")
1293          .withFeatures(
1294              CollectionSize.ANY,
1295              MapFeature.ALLOWS_NULL_KEYS,
1296              MapFeature.ALLOWS_NULL_VALUES,
1297              MapFeature.GENERAL_PURPOSE)
1298          .suppressing(getIteratorUnknownOrderRemoveSupportedMethod())
1299          .createTestSuite());
1300
1301      suite.addTest(MapTestSuiteBuilder.using(
1302          new TestStringMapGenerator() {
1303            @Override protected Map<String, String> create(
1304                Entry<String, String>[] entries) {
1305              Map<String, String> map = Maps.newHashMap();
1306              for (Entry<String, String> entry : entries) {
1307                map.put(entry.getKey(), entry.getValue());
1308              }
1309              map.putAll(ENTRIES_TO_FILTER_OUT);
1310              return Maps.filterEntries(map,
1311                  new Predicate<Entry<String, String>>() {
1312                    @Override
1313                    public boolean apply(Entry<String, String> entry) {
1314                      String input = entry.getKey();
1315                      return input == null
1316                          || (input.charAt(0) >= 'a' && input.charAt(0) <= 'z');
1317                    }
1318                  });
1319            }
1320          })
1321          .named("Maps.filterEntries")
1322          .withFeatures(
1323              CollectionSize.ANY,
1324              MapFeature.ALLOWS_NULL_KEYS,
1325              MapFeature.ALLOWS_NULL_VALUES,
1326              MapFeature.GENERAL_PURPOSE)
1327          .suppressing(getIteratorUnknownOrderRemoveSupportedMethod())
1328          .createTestSuite());
1329
1330      suite.addTest(MapTestSuiteBuilder.using(
1331          new TestStringMapGenerator() {
1332            @Override protected Map<String, String> create(
1333                Entry<String, String>[] entries) {
1334              Map<String, String> map = Maps.newHashMap();
1335              for (Entry<String, String> entry : entries) {
1336                map.put(entry.getKey(), entry.getValue());
1337              }
1338              map.putAll(ENTRIES_TO_FILTER_OUT);
1339              map.put("", "weird");
1340              Map<String, String> withoutEmptyKey = Maps.filterKeys(map,
1341                  new Predicate<String>() {
1342                    @Override
1343                    public boolean apply(String input) {
1344                      return input == null || input.length() != 0;
1345                    }
1346                  });
1347              return Maps.filterKeys(withoutEmptyKey, new Predicate<String>() {
1348                @Override
1349                public boolean apply(String input) {
1350                  return input == null
1351                      || (input.charAt(0) >= 'a' && input.charAt(0) <= 'z');
1352                }
1353              });
1354              // note: these filters were deliberately chosen so that an
1355              // element somehow getting around the first filter would cause
1356              // an exception in the second
1357            }
1358          })
1359          .named("Maps.filterKeys, chained")
1360          .withFeatures(
1361              CollectionSize.ANY,
1362              MapFeature.ALLOWS_NULL_KEYS,
1363              MapFeature.ALLOWS_NULL_VALUES,
1364              MapFeature.GENERAL_PURPOSE)
1365          .suppressing(getIteratorUnknownOrderRemoveSupportedMethod())
1366          .createTestSuite());
1367
1368      return suite;
1369    }
1370  }
1371
1372  public void testSortedMapTransformValues() {
1373    SortedMap<String, Integer> map = ImmutableSortedMap.of("a", 4, "b", 9);
1374    Function<Integer, Double> sqrt = new Function<Integer, Double>() {
1375      @Override
1376      public Double apply(Integer in) {
1377        return Math.sqrt(in);
1378      }
1379    };
1380    SortedMap<String, Double> transformed =
1381        Maps.transformValues(map, sqrt);
1382
1383    assertEquals(ImmutableSortedMap.of("a", 2.0, "b", 3.0), transformed);
1384  }
1385
1386  public void testSortedMapTransformEntries() {
1387    SortedMap<String, String> map = ImmutableSortedMap.of("a", "4", "b", "9");
1388    EntryTransformer<String, String, String> concat =
1389        new EntryTransformer<String, String, String>() {
1390          @Override
1391          public String transformEntry(String key, String value) {
1392            return key + value;
1393          }
1394        };
1395    SortedMap<String, String> transformed =
1396        Maps.transformEntries(map, concat);
1397
1398    assertEquals(ImmutableSortedMap.of("a", "a4", "b", "b9"), transformed);
1399  }
1400
1401  /*
1402   * Not testing Map methods of Maps.filter*(SortedMap), since the
1403   * implementation doesn't override Maps.FilteredEntryMap, which is already
1404   * tested.
1405   */
1406
1407  public void testSortedMapFilterKeys() {
1408    Comparator<Integer> comparator = Ordering.natural();
1409    SortedMap<Integer, String> unfiltered = Maps.newTreeMap(comparator);
1410    unfiltered.put(1, "one");
1411    unfiltered.put(2, "two");
1412    unfiltered.put(3, "three");
1413    unfiltered.put(4, "four");
1414    unfiltered.put(5, "five");
1415    unfiltered.put(6, "six");
1416    unfiltered.put(7, "seven");
1417    SortedMap<Integer, String> filtered
1418        = Maps.filterKeys(unfiltered, EVEN);
1419    ASSERT.that(filtered.keySet()).hasContentsInOrder(2, 4, 6);
1420    assertSame(comparator, filtered.comparator());
1421    assertEquals((Integer) 2, filtered.firstKey());
1422    assertEquals((Integer) 6, filtered.lastKey());
1423    ASSERT.that(filtered.headMap(5).keySet()).hasContentsInOrder(2, 4);
1424    ASSERT.that(filtered.tailMap(3).keySet()).hasContentsInOrder(4, 6);
1425    ASSERT.that(filtered.subMap(3, 5).keySet()).hasContentsInOrder(4);
1426  }
1427
1428  public void testSortedMapFilterValues() {
1429    Comparator<Integer> comparator = Ordering.natural();
1430    SortedMap<Integer, String> unfiltered = Maps.newTreeMap(comparator);
1431    unfiltered.put(1, "one");
1432    unfiltered.put(2, "two");
1433    unfiltered.put(3, "three");
1434    unfiltered.put(4, "four");
1435    unfiltered.put(5, "five");
1436    unfiltered.put(6, "six");
1437    unfiltered.put(7, "seven");
1438    SortedMap<Integer, String> filtered
1439        = Maps.filterValues(unfiltered, NOT_LENGTH_3);
1440    ASSERT.that(filtered.keySet()).hasContentsInOrder(3, 4, 5, 7);
1441    assertSame(comparator, filtered.comparator());
1442    assertEquals((Integer) 3, filtered.firstKey());
1443    assertEquals((Integer) 7, filtered.lastKey());
1444    ASSERT.that(filtered.headMap(5).keySet()).hasContentsInOrder(3, 4);
1445    ASSERT.that(filtered.tailMap(4).keySet()).hasContentsInOrder(4, 5, 7);
1446    ASSERT.that(filtered.subMap(4, 6).keySet()).hasContentsInOrder(4, 5);
1447  }
1448
1449  private static final Predicate<Map.Entry<Integer, String>>
1450      EVEN_AND_LENGTH_3 = new Predicate<Map.Entry<Integer, String>>() {
1451        @Override public boolean apply(Entry<Integer, String> entry) {
1452          return (entry.getKey() == null || entry.getKey() % 2 == 0)
1453              && (entry.getValue() == null || entry.getValue().length() == 3);
1454        }
1455    };
1456
1457  private static class ContainsKeySafeSortedMap
1458      extends ForwardingSortedMap<Integer, String> {
1459    SortedMap<Integer, String> delegate
1460        = Maps.newTreeMap(Ordering.natural().nullsFirst());
1461
1462    @Override protected SortedMap<Integer, String> delegate() {
1463      return delegate;
1464    }
1465
1466    // Needed by MapInterfaceTest.testContainsKey()
1467    @Override public boolean containsKey(Object key) {
1468      try {
1469        return super.containsKey(key);
1470      } catch (ClassCastException e) {
1471        return false;
1472      }
1473    }
1474  }
1475
1476  public static class FilteredEntriesSortedMapInterfaceTest
1477      extends SortedMapInterfaceTest<Integer, String> {
1478    public FilteredEntriesSortedMapInterfaceTest() {
1479      super(true, true, true, true, true);
1480    }
1481
1482    @Override protected SortedMap<Integer, String> makeEmptyMap() {
1483      SortedMap<Integer, String> unfiltered = new ContainsKeySafeSortedMap();
1484      unfiltered.put(1, "one");
1485      unfiltered.put(3, "three");
1486      unfiltered.put(4, "four");
1487      unfiltered.put(5, "five");
1488      return Maps.filterEntries(unfiltered, EVEN_AND_LENGTH_3);
1489    }
1490
1491    @Override protected SortedMap<Integer, String> makePopulatedMap() {
1492      SortedMap<Integer, String> unfiltered = new ContainsKeySafeSortedMap();
1493      unfiltered.put(1, "one");
1494      unfiltered.put(2, "two");
1495      unfiltered.put(3, "three");
1496      unfiltered.put(4, "four");
1497      unfiltered.put(5, "five");
1498      unfiltered.put(6, "six");
1499      return Maps.filterEntries(unfiltered, EVEN_AND_LENGTH_3);
1500    }
1501
1502    @Override protected Integer getKeyNotInPopulatedMap() {
1503      return 10;
1504    }
1505
1506    @Override protected String getValueNotInPopulatedMap() {
1507      return "ten";
1508    }
1509
1510    // Iterators don't support remove.
1511    @Override public void testEntrySetIteratorRemove() {}
1512    @Override public void testValuesIteratorRemove() {}
1513
1514    // These tests fail on GWT.
1515    // TODO: Investigate why.
1516    @Override public void testEntrySetRemoveAll() {}
1517    @Override public void testEntrySetRetainAll() {}
1518  }
1519}
1520