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.Maps.transformValues;
21import static com.google.common.collect.testing.Helpers.mapEntry;
22import static com.google.common.truth.Truth.assertThat;
23
24import com.google.common.annotations.GwtCompatible;
25import com.google.common.base.Converter;
26import com.google.common.base.Equivalence;
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.testing.EqualsTester;
35import com.google.common.testing.SerializableTester;
36
37import junit.framework.TestCase;
38
39import java.util.Arrays;
40import java.util.Collections;
41import java.util.Comparator;
42import java.util.EnumMap;
43import java.util.HashMap;
44import java.util.IdentityHashMap;
45import java.util.Iterator;
46import java.util.LinkedHashMap;
47import java.util.List;
48import java.util.Map;
49import java.util.Map.Entry;
50import java.util.Set;
51import java.util.SortedMap;
52import java.util.SortedSet;
53import java.util.TreeMap;
54import java.util.concurrent.ConcurrentMap;
55
56/**
57 * Unit test for {@code Maps}.
58 *
59 * @author Kevin Bourrillion
60 * @author Mike Bostock
61 * @author Jared Levy
62 */
63@GwtCompatible(emulated = true)
64public class MapsTest extends TestCase {
65
66  private static final Comparator<Integer> SOME_COMPARATOR =
67      Collections.reverseOrder();
68
69  public void testHashMap() {
70    HashMap<Integer, Integer> map = Maps.newHashMap();
71    assertEquals(Collections.emptyMap(), map);
72  }
73
74  public void testHashMapWithInitialMap() {
75    Map<String, Integer> original = new TreeMap<String, Integer>();
76    original.put("a", 1);
77    original.put("b", 2);
78    original.put("c", 3);
79    HashMap<String, Integer> map = Maps.newHashMap(original);
80    assertEquals(original, map);
81  }
82
83  public void testHashMapGeneralizesTypes() {
84    Map<String, Integer> original = new TreeMap<String, Integer>();
85    original.put("a", 1);
86    original.put("b", 2);
87    original.put("c", 3);
88    HashMap<Object, Object> map =
89        Maps.newHashMap((Map<? extends Object, ? extends Object>) original);
90    assertEquals(original, map);
91  }
92
93  public void testCapacityForNegativeSizeFails() {
94    try {
95      Maps.capacity(-1);
96      fail("Negative expected size must result in IllegalArgumentException");
97    } catch (IllegalArgumentException ex) {
98    }
99  }
100
101  public void testCapacityForLargeSizes() {
102    int[] largeExpectedSizes = new int[] {
103      Integer.MAX_VALUE / 2 - 1,
104      Integer.MAX_VALUE / 2,
105      Integer.MAX_VALUE / 2 + 1,
106      Integer.MAX_VALUE - 1,
107      Integer.MAX_VALUE};
108    for (int expectedSize : largeExpectedSizes) {
109      int capacity = Maps.capacity(expectedSize);
110      assertTrue(
111          "capacity (" + capacity + ") must be >= expectedSize (" + expectedSize + ")",
112          capacity >= expectedSize);
113    }
114  }
115
116  public void testLinkedHashMap() {
117    LinkedHashMap<Integer, Integer> map = Maps.newLinkedHashMap();
118    assertEquals(Collections.emptyMap(), map);
119  }
120
121  @SuppressWarnings("serial")
122  public void testLinkedHashMapWithInitialMap() {
123    Map<String, String> map = new LinkedHashMap<String, String>() {{
124      put("Hello", "World");
125      put("first", "second");
126      put("polygene", "lubricants");
127      put("alpha", "betical");
128    }};
129
130    LinkedHashMap<String, String> copy = Maps.newLinkedHashMap(map);
131
132    Iterator<Entry<String, String>> iter = copy.entrySet().iterator();
133    assertTrue(iter.hasNext());
134    Entry<String, String> entry = iter.next();
135    assertEquals("Hello", entry.getKey());
136    assertEquals("World", entry.getValue());
137    assertTrue(iter.hasNext());
138
139    entry = iter.next();
140    assertEquals("first", entry.getKey());
141    assertEquals("second", entry.getValue());
142    assertTrue(iter.hasNext());
143
144    entry = iter.next();
145    assertEquals("polygene", entry.getKey());
146    assertEquals("lubricants", entry.getValue());
147    assertTrue(iter.hasNext());
148
149    entry = iter.next();
150    assertEquals("alpha", entry.getKey());
151    assertEquals("betical", entry.getValue());
152    assertFalse(iter.hasNext());
153  }
154
155  public void testLinkedHashMapGeneralizesTypes() {
156    Map<String, Integer> original = new LinkedHashMap<String, Integer>();
157    original.put("a", 1);
158    original.put("b", 2);
159    original.put("c", 3);
160    HashMap<Object, Object> map
161        = Maps.<Object, Object>newLinkedHashMap(original);
162    assertEquals(original, map);
163  }
164
165  public void testIdentityHashMap() {
166    IdentityHashMap<Integer, Integer> map = Maps.newIdentityHashMap();
167    assertEquals(Collections.emptyMap(), map);
168  }
169
170  public void testConcurrentMap() {
171    ConcurrentMap<Integer, Integer> map = Maps.newConcurrentMap();
172    assertEquals(Collections.emptyMap(), map);
173  }
174
175  public void testTreeMap() {
176    TreeMap<Integer, Integer> map = Maps.newTreeMap();
177    assertEquals(Collections.emptyMap(), map);
178    assertNull(map.comparator());
179  }
180
181  public void testTreeMapDerived() {
182    TreeMap<Derived, Integer> map = Maps.newTreeMap();
183    assertEquals(Collections.emptyMap(), map);
184    map.put(new Derived("foo"), 1);
185    map.put(new Derived("bar"), 2);
186    assertThat(map.keySet()).has().exactly(
187        new Derived("bar"), new Derived("foo")).inOrder();
188    assertThat(map.values()).has().exactly(2, 1).inOrder();
189    assertNull(map.comparator());
190  }
191
192  public void testTreeMapNonGeneric() {
193    TreeMap<LegacyComparable, Integer> map = Maps.newTreeMap();
194    assertEquals(Collections.emptyMap(), map);
195    map.put(new LegacyComparable("foo"), 1);
196    map.put(new LegacyComparable("bar"), 2);
197    assertThat(map.keySet()).has().exactly(
198        new LegacyComparable("bar"), new LegacyComparable("foo")).inOrder();
199    assertThat(map.values()).has().exactly(2, 1).inOrder();
200    assertNull(map.comparator());
201  }
202
203  public void testTreeMapWithComparator() {
204    TreeMap<Integer, Integer> map = Maps.newTreeMap(SOME_COMPARATOR);
205    assertEquals(Collections.emptyMap(), map);
206    assertSame(SOME_COMPARATOR, map.comparator());
207  }
208
209  public void testTreeMapWithInitialMap() {
210    SortedMap<Integer, Integer> map = Maps.newTreeMap();
211    map.put(5, 10);
212    map.put(3, 20);
213    map.put(1, 30);
214    TreeMap<Integer, Integer> copy = Maps.newTreeMap(map);
215    assertEquals(copy, map);
216    assertSame(copy.comparator(), map.comparator());
217  }
218
219  public enum SomeEnum { SOME_INSTANCE }
220
221  public void testEnumMap() {
222    EnumMap<SomeEnum, Integer> map = Maps.newEnumMap(SomeEnum.class);
223    assertEquals(Collections.emptyMap(), map);
224    map.put(SomeEnum.SOME_INSTANCE, 0);
225    assertEquals(Collections.singletonMap(SomeEnum.SOME_INSTANCE, 0), map);
226  }
227
228  public void testEnumMapNullClass() {
229    try {
230      Maps.<SomeEnum, Long>newEnumMap((Class<MapsTest.SomeEnum>) null);
231      fail("no exception thrown");
232    } catch (NullPointerException expected) {
233    }
234  }
235
236  public void testEnumMapWithInitialEnumMap() {
237    EnumMap<SomeEnum, Integer> original = Maps.newEnumMap(SomeEnum.class);
238    original.put(SomeEnum.SOME_INSTANCE, 0);
239    EnumMap<SomeEnum, Integer> copy = Maps.newEnumMap(original);
240    assertEquals(original, copy);
241  }
242
243  public void testEnumMapWithInitialEmptyEnumMap() {
244    EnumMap<SomeEnum, Integer> original = Maps.newEnumMap(SomeEnum.class);
245    EnumMap<SomeEnum, Integer> copy = Maps.newEnumMap(original);
246    assertEquals(original, copy);
247    assertNotSame(original, copy);
248  }
249
250  public void testEnumMapWithInitialMap() {
251    HashMap<SomeEnum, Integer> original = Maps.newHashMap();
252    original.put(SomeEnum.SOME_INSTANCE, 0);
253    EnumMap<SomeEnum, Integer> copy = Maps.newEnumMap(original);
254    assertEquals(original, copy);
255  }
256
257  public void testEnumMapWithInitialEmptyMap() {
258    Map<SomeEnum, Integer> original = Maps.newHashMap();
259    try {
260      Maps.newEnumMap(original);
261      fail("Empty map must result in an IllegalArgumentException");
262    } catch (IllegalArgumentException expected) {}
263  }
264
265  public void testToStringImplWithNullKeys() throws Exception {
266    Map<String, String> hashmap = Maps.newHashMap();
267    hashmap.put("foo", "bar");
268    hashmap.put(null, "baz");
269
270    assertEquals(hashmap.toString(), Maps.toStringImpl(hashmap));
271  }
272
273  public void testToStringImplWithNullValues() throws Exception {
274    Map<String, String> hashmap = Maps.newHashMap();
275    hashmap.put("foo", "bar");
276    hashmap.put("baz", null);
277
278    assertEquals(hashmap.toString(), Maps.toStringImpl(hashmap));
279  }
280
281  private static final Map<Integer, Integer> EMPTY
282      = Collections.emptyMap();
283  private static final Map<Integer, Integer> SINGLETON
284      = Collections.singletonMap(1, 2);
285
286  public void testMapDifferenceEmptyEmpty() {
287    MapDifference<Integer, Integer> diff = Maps.difference(EMPTY, EMPTY);
288    assertTrue(diff.areEqual());
289    assertEquals(EMPTY, diff.entriesOnlyOnLeft());
290    assertEquals(EMPTY, diff.entriesOnlyOnRight());
291    assertEquals(EMPTY, diff.entriesInCommon());
292    assertEquals(EMPTY, diff.entriesDiffering());
293    assertEquals("equal", diff.toString());
294  }
295
296  public void testMapDifferenceEmptySingleton() {
297    MapDifference<Integer, Integer> diff = Maps.difference(EMPTY, SINGLETON);
298    assertFalse(diff.areEqual());
299    assertEquals(EMPTY, diff.entriesOnlyOnLeft());
300    assertEquals(SINGLETON, diff.entriesOnlyOnRight());
301    assertEquals(EMPTY, diff.entriesInCommon());
302    assertEquals(EMPTY, diff.entriesDiffering());
303    assertEquals("not equal: only on right={1=2}", diff.toString());
304  }
305
306  public void testMapDifferenceSingletonEmpty() {
307    MapDifference<Integer, Integer> diff = Maps.difference(SINGLETON, EMPTY);
308    assertFalse(diff.areEqual());
309    assertEquals(SINGLETON, diff.entriesOnlyOnLeft());
310    assertEquals(EMPTY, diff.entriesOnlyOnRight());
311    assertEquals(EMPTY, diff.entriesInCommon());
312    assertEquals(EMPTY, diff.entriesDiffering());
313    assertEquals("not equal: only on left={1=2}", diff.toString());
314  }
315
316  public void testMapDifferenceTypical() {
317    Map<Integer, String> left = ImmutableMap.of(
318        1, "a", 2, "b", 3, "c", 4, "d", 5, "e");
319    Map<Integer, String> right = ImmutableMap.of(
320        1, "a", 3, "f", 5, "g", 6, "z");
321
322    MapDifference<Integer, String> diff1 = Maps.difference(left, right);
323    assertFalse(diff1.areEqual());
324    assertEquals(ImmutableMap.of(2, "b", 4, "d"), diff1.entriesOnlyOnLeft());
325    assertEquals(ImmutableMap.of(6, "z"), diff1.entriesOnlyOnRight());
326    assertEquals(ImmutableMap.of(1, "a"), diff1.entriesInCommon());
327    assertEquals(ImmutableMap.of(3,
328        ValueDifferenceImpl.create("c", "f"), 5,
329        ValueDifferenceImpl.create("e", "g")),
330        diff1.entriesDiffering());
331    assertEquals("not equal: only on left={2=b, 4=d}: only on right={6=z}: "
332        + "value differences={3=(c, f), 5=(e, g)}", diff1.toString());
333
334    MapDifference<Integer, String> diff2 = Maps.difference(right, left);
335    assertFalse(diff2.areEqual());
336    assertEquals(ImmutableMap.of(6, "z"), diff2.entriesOnlyOnLeft());
337    assertEquals(ImmutableMap.of(2, "b", 4, "d"), diff2.entriesOnlyOnRight());
338    assertEquals(ImmutableMap.of(1, "a"), diff2.entriesInCommon());
339    assertEquals(ImmutableMap.of(3,
340        ValueDifferenceImpl.create("f", "c"), 5,
341        ValueDifferenceImpl.create("g", "e")),
342        diff2.entriesDiffering());
343    assertEquals("not equal: only on left={6=z}: only on right={2=b, 4=d}: "
344        + "value differences={3=(f, c), 5=(g, e)}", diff2.toString());
345  }
346
347  public void testMapDifferenceEquals() {
348    Map<Integer, String> left = ImmutableMap.of(
349        1, "a", 2, "b", 3, "c", 4, "d", 5, "e");
350    Map<Integer, String> right = ImmutableMap.of(
351        1, "a", 3, "f", 5, "g", 6, "z");
352    Map<Integer, String> right2 = ImmutableMap.of(
353        1, "a", 3, "h", 5, "g", 6, "z");
354    MapDifference<Integer, String> original = Maps.difference(left, right);
355    MapDifference<Integer, String> same = Maps.difference(left, right);
356    MapDifference<Integer, String> reverse = Maps.difference(right, left);
357    MapDifference<Integer, String> diff2 = Maps.difference(left, right2);
358
359    new EqualsTester()
360        .addEqualityGroup(original, same)
361        .addEqualityGroup(reverse)
362        .addEqualityGroup(diff2)
363        .testEquals();
364  }
365
366  public void testMapDifferencePredicateTypical() {
367    Map<Integer, String> left = ImmutableMap.of(
368        1, "a", 2, "b", 3, "c", 4, "d", 5, "e");
369    Map<Integer, String> right = ImmutableMap.of(
370        1, "A", 3, "F", 5, "G", 6, "Z");
371
372    // TODO(kevinb): replace with Ascii.caseInsensitiveEquivalence() when it
373    // exists
374    Equivalence<String> caseInsensitiveEquivalence = Equivalence.equals().onResultOf(
375        new Function<String, String>() {
376          @Override public String apply(String input) {
377            return input.toLowerCase();
378          }
379        });
380
381    MapDifference<Integer, String> diff1 = Maps.difference(left, right,
382        caseInsensitiveEquivalence);
383    assertFalse(diff1.areEqual());
384    assertEquals(ImmutableMap.of(2, "b", 4, "d"), diff1.entriesOnlyOnLeft());
385    assertEquals(ImmutableMap.of(6, "Z"), diff1.entriesOnlyOnRight());
386    assertEquals(ImmutableMap.of(1, "a"), diff1.entriesInCommon());
387    assertEquals(ImmutableMap.of(3,
388        ValueDifferenceImpl.create("c", "F"), 5,
389        ValueDifferenceImpl.create("e", "G")),
390        diff1.entriesDiffering());
391    assertEquals("not equal: only on left={2=b, 4=d}: only on right={6=Z}: "
392        + "value differences={3=(c, F), 5=(e, G)}", diff1.toString());
393
394    MapDifference<Integer, String> diff2 = Maps.difference(right, left,
395        caseInsensitiveEquivalence);
396    assertFalse(diff2.areEqual());
397    assertEquals(ImmutableMap.of(6, "Z"), diff2.entriesOnlyOnLeft());
398    assertEquals(ImmutableMap.of(2, "b", 4, "d"), diff2.entriesOnlyOnRight());
399    assertEquals(ImmutableMap.of(1, "A"), diff2.entriesInCommon());
400    assertEquals(ImmutableMap.of(3,
401        ValueDifferenceImpl.create("F", "c"), 5,
402        ValueDifferenceImpl.create("G", "e")),
403        diff2.entriesDiffering());
404    assertEquals("not equal: only on left={6=Z}: only on right={2=b, 4=d}: "
405        + "value differences={3=(F, c), 5=(G, e)}", diff2.toString());
406  }
407
408  private static final SortedMap<Integer, Integer> SORTED_EMPTY = Maps.newTreeMap();
409  private static final SortedMap<Integer, Integer> SORTED_SINGLETON =
410      ImmutableSortedMap.of(1, 2);
411
412  public void testMapDifferenceOfSortedMapIsSorted() {
413    Map<Integer, Integer> map = SORTED_SINGLETON;
414    MapDifference<Integer, Integer> difference = Maps.difference(map, EMPTY);
415    assertTrue(difference instanceof SortedMapDifference);
416  }
417
418  public void testSortedMapDifferenceEmptyEmpty() {
419    SortedMapDifference<Integer, Integer> diff =
420        Maps.difference(SORTED_EMPTY, SORTED_EMPTY);
421    assertTrue(diff.areEqual());
422    assertEquals(SORTED_EMPTY, diff.entriesOnlyOnLeft());
423    assertEquals(SORTED_EMPTY, diff.entriesOnlyOnRight());
424    assertEquals(SORTED_EMPTY, diff.entriesInCommon());
425    assertEquals(SORTED_EMPTY, diff.entriesDiffering());
426    assertEquals("equal", diff.toString());
427  }
428
429  public void testSortedMapDifferenceEmptySingleton() {
430    SortedMapDifference<Integer, Integer> diff =
431        Maps.difference(SORTED_EMPTY, SORTED_SINGLETON);
432    assertFalse(diff.areEqual());
433    assertEquals(SORTED_EMPTY, diff.entriesOnlyOnLeft());
434    assertEquals(SORTED_SINGLETON, diff.entriesOnlyOnRight());
435    assertEquals(SORTED_EMPTY, diff.entriesInCommon());
436    assertEquals(SORTED_EMPTY, diff.entriesDiffering());
437    assertEquals("not equal: only on right={1=2}", diff.toString());
438  }
439
440  public void testSortedMapDifferenceSingletonEmpty() {
441    SortedMapDifference<Integer, Integer> diff =
442        Maps.difference(SORTED_SINGLETON, SORTED_EMPTY);
443    assertFalse(diff.areEqual());
444    assertEquals(SORTED_SINGLETON, diff.entriesOnlyOnLeft());
445    assertEquals(SORTED_EMPTY, diff.entriesOnlyOnRight());
446    assertEquals(SORTED_EMPTY, diff.entriesInCommon());
447    assertEquals(SORTED_EMPTY, diff.entriesDiffering());
448    assertEquals("not equal: only on left={1=2}", diff.toString());
449  }
450
451  public void testSortedMapDifferenceTypical() {
452    SortedMap<Integer, String> left =
453        ImmutableSortedMap.<Integer, String>reverseOrder()
454        .put(1, "a").put(2, "b").put(3, "c").put(4, "d").put(5, "e")
455        .build();
456
457    SortedMap<Integer, String> right =
458        ImmutableSortedMap.of(1, "a", 3, "f", 5, "g", 6, "z");
459
460    SortedMapDifference<Integer, String> diff1 =
461        Maps.difference(left, right);
462    assertFalse(diff1.areEqual());
463    assertThat(diff1.entriesOnlyOnLeft().entrySet()).has().exactly(
464        Maps.immutableEntry(4, "d"), Maps.immutableEntry(2, "b")).inOrder();
465    assertThat(diff1.entriesOnlyOnRight().entrySet()).has().item(
466        Maps.immutableEntry(6, "z"));
467    assertThat(diff1.entriesInCommon().entrySet()).has().item(
468        Maps.immutableEntry(1, "a"));
469    assertThat(diff1.entriesDiffering().entrySet()).has().exactly(
470        Maps.immutableEntry(5, ValueDifferenceImpl.create("e", "g")),
471        Maps.immutableEntry(3, ValueDifferenceImpl.create("c", "f"))).inOrder();
472    assertEquals("not equal: only on left={4=d, 2=b}: only on right={6=z}: "
473        + "value differences={5=(e, g), 3=(c, f)}", diff1.toString());
474
475    SortedMapDifference<Integer, String> diff2 =
476        Maps.difference(right, left);
477    assertFalse(diff2.areEqual());
478    assertThat(diff2.entriesOnlyOnLeft().entrySet()).has().item(
479        Maps.immutableEntry(6, "z"));
480    assertThat(diff2.entriesOnlyOnRight().entrySet()).has().exactly(
481        Maps.immutableEntry(2, "b"), Maps.immutableEntry(4, "d")).inOrder();
482    assertThat(diff1.entriesInCommon().entrySet()).has().item(
483        Maps.immutableEntry(1, "a"));
484    assertEquals(ImmutableMap.of(
485            3, ValueDifferenceImpl.create("f", "c"),
486            5, ValueDifferenceImpl.create("g", "e")),
487        diff2.entriesDiffering());
488    assertEquals("not equal: only on left={6=z}: only on right={2=b, 4=d}: "
489        + "value differences={3=(f, c), 5=(g, e)}", diff2.toString());
490  }
491
492  public void testSortedMapDifferenceImmutable() {
493    SortedMap<Integer, String> left = Maps.newTreeMap(
494        ImmutableSortedMap.of(1, "a", 2, "b", 3, "c", 4, "d", 5, "e"));
495    SortedMap<Integer, String> right =
496        Maps.newTreeMap(ImmutableSortedMap.of(1, "a", 3, "f", 5, "g", 6, "z"));
497
498    SortedMapDifference<Integer, String> diff1 =
499        Maps.difference(left, right);
500    left.put(6, "z");
501    assertFalse(diff1.areEqual());
502    assertThat(diff1.entriesOnlyOnLeft().entrySet()).has().exactly(
503        Maps.immutableEntry(2, "b"), Maps.immutableEntry(4, "d")).inOrder();
504    assertThat(diff1.entriesOnlyOnRight().entrySet()).has().item(
505        Maps.immutableEntry(6, "z"));
506    assertThat(diff1.entriesInCommon().entrySet()).has().item(
507        Maps.immutableEntry(1, "a"));
508    assertThat(diff1.entriesDiffering().entrySet()).has().exactly(
509        Maps.immutableEntry(3, ValueDifferenceImpl.create("c", "f")),
510        Maps.immutableEntry(5, ValueDifferenceImpl.create("e", "g"))).inOrder();
511    try {
512      diff1.entriesInCommon().put(7, "x");
513      fail();
514    } catch (UnsupportedOperationException expected) {
515    }
516    try {
517      diff1.entriesOnlyOnLeft().put(7, "x");
518      fail();
519    } catch (UnsupportedOperationException expected) {
520    }
521    try {
522      diff1.entriesOnlyOnRight().put(7, "x");
523      fail();
524    } catch (UnsupportedOperationException expected) {
525    }
526  }
527
528  public void testSortedMapDifferenceEquals() {
529    SortedMap<Integer, String> left =
530        ImmutableSortedMap.of(1, "a", 2, "b", 3, "c", 4, "d", 5, "e");
531    SortedMap<Integer, String> right =
532        ImmutableSortedMap.of(1, "a", 3, "f", 5, "g", 6, "z");
533    SortedMap<Integer, String> right2 =
534        ImmutableSortedMap.of(1, "a", 3, "h", 5, "g", 6, "z");
535    SortedMapDifference<Integer, String> original =
536        Maps.difference(left, right);
537    SortedMapDifference<Integer, String> same =
538        Maps.difference(left, right);
539    SortedMapDifference<Integer, String> reverse =
540        Maps.difference(right, left);
541    SortedMapDifference<Integer, String> diff2 =
542        Maps.difference(left, right2);
543
544    new EqualsTester()
545        .addEqualityGroup(original, same)
546        .addEqualityGroup(reverse)
547        .addEqualityGroup(diff2)
548        .testEquals();
549  }
550
551  private static final Function<String, Integer> LENGTH_FUNCTION =
552      new Function<String, Integer>() {
553        @Override
554        public Integer apply(String input) {
555          return input.length();
556        }
557      };
558
559  public void testAsMap() {
560    Set<String> strings = ImmutableSet.of("one", "two", "three");
561    Map<String, Integer> map = Maps.asMap(strings, LENGTH_FUNCTION);
562    assertEquals(ImmutableMap.of("one", 3, "two", 3, "three", 5), map);
563    assertEquals(Integer.valueOf(5), map.get("three"));
564    assertNull(map.get("five"));
565    assertThat(map.entrySet()).has().exactly(
566        mapEntry("one", 3),
567        mapEntry("two", 3),
568        mapEntry("three", 5)).inOrder();
569  }
570
571  public void testAsMapReadsThrough() {
572    Set<String> strings = Sets.newLinkedHashSet();
573    Collections.addAll(strings, "one", "two", "three");
574    Map<String, Integer> map = Maps.asMap(strings, LENGTH_FUNCTION);
575    assertEquals(ImmutableMap.of("one", 3, "two", 3, "three", 5), map);
576    assertNull(map.get("four"));
577    strings.add("four");
578    assertEquals(ImmutableMap.of("one", 3, "two", 3, "three", 5, "four", 4), map);
579    assertEquals(Integer.valueOf(4), map.get("four"));
580  }
581
582  public void testAsMapWritesThrough() {
583    Set<String> strings = Sets.newLinkedHashSet();
584    Collections.addAll(strings, "one", "two", "three");
585    Map<String, Integer> map = Maps.asMap(strings, LENGTH_FUNCTION);
586    assertEquals(ImmutableMap.of("one", 3, "two", 3, "three", 5), map);
587    assertEquals(Integer.valueOf(3), map.remove("two"));
588    assertThat(strings).has().exactly("one", "three").inOrder();
589  }
590
591  public void testAsMapEmpty() {
592    Set<String> strings = ImmutableSet.of();
593    Map<String, Integer> map = Maps.asMap(strings, LENGTH_FUNCTION);
594    assertThat(map.entrySet()).isEmpty();
595    assertTrue(map.isEmpty());
596    assertNull(map.get("five"));
597  }
598
599  private static class NonNavigableSortedSet
600      extends ForwardingSortedSet<String> {
601    private final SortedSet<String> delegate = Sets.newTreeSet();
602
603    @Override
604    protected SortedSet<String> delegate() {
605      return delegate;
606    }
607  }
608
609  public void testAsMapReturnsSortedMapForSortedSetInput() {
610    Set<String> set = new NonNavigableSortedSet();
611    assertTrue(Maps.asMap(set, Functions.identity()) instanceof SortedMap);
612  }
613
614  public void testAsMapSorted() {
615    SortedSet<String> strings = new NonNavigableSortedSet();
616    Collections.addAll(strings, "one", "two", "three");
617    SortedMap<String, Integer> map = Maps.asMap(strings, LENGTH_FUNCTION);
618    assertEquals(ImmutableMap.of("one", 3, "two", 3, "three", 5), map);
619    assertEquals(Integer.valueOf(5), map.get("three"));
620    assertNull(map.get("five"));
621    assertThat(map.entrySet()).has().exactly(
622        mapEntry("one", 3),
623        mapEntry("three", 5),
624        mapEntry("two", 3)).inOrder();
625    assertThat(map.tailMap("onea").entrySet()).has().exactly(
626        mapEntry("three", 5),
627        mapEntry("two", 3)).inOrder();
628    assertThat(map.subMap("one", "two").entrySet()).has().exactly(
629        mapEntry("one", 3),
630        mapEntry("three", 5)).inOrder();
631  }
632
633  public void testAsMapSortedReadsThrough() {
634    SortedSet<String> strings = new NonNavigableSortedSet();
635    Collections.addAll(strings, "one", "two", "three");
636    SortedMap<String, Integer> map = Maps.asMap(strings, LENGTH_FUNCTION);
637    assertNull(map.comparator());
638    assertEquals(ImmutableSortedMap.of("one", 3, "two", 3, "three", 5), map);
639    assertNull(map.get("four"));
640    strings.add("four");
641    assertEquals(
642        ImmutableSortedMap.of("one", 3, "two", 3, "three", 5, "four", 4),
643        map);
644    assertEquals(Integer.valueOf(4), map.get("four"));
645    SortedMap<String, Integer> headMap = map.headMap("two");
646    assertEquals(
647        ImmutableSortedMap.of("four", 4, "one", 3, "three", 5),
648        headMap);
649    strings.add("five");
650    strings.remove("one");
651    assertEquals(
652        ImmutableSortedMap.of("five", 4, "four", 4, "three", 5),
653        headMap);
654    assertThat(map.entrySet()).has().exactly(
655        mapEntry("five", 4),
656        mapEntry("four", 4),
657        mapEntry("three", 5),
658        mapEntry("two", 3)).inOrder();
659  }
660
661  public void testAsMapSortedWritesThrough() {
662    SortedSet<String> strings = new NonNavigableSortedSet();
663    Collections.addAll(strings, "one", "two", "three");
664    SortedMap<String, Integer> map = Maps.asMap(strings, LENGTH_FUNCTION);
665    assertEquals(ImmutableMap.of("one", 3, "two", 3, "three", 5), map);
666    assertEquals(Integer.valueOf(3), map.remove("two"));
667    assertThat(strings).has().exactly("one", "three").inOrder();
668  }
669
670  public void testAsMapSortedSubViewKeySetsDoNotSupportAdd() {
671    SortedMap<String, Integer> map = Maps.asMap(
672        new NonNavigableSortedSet(), LENGTH_FUNCTION);
673    try {
674      map.subMap("a", "z").keySet().add("a");
675      fail();
676    } catch (UnsupportedOperationException expected) {
677    }
678    try {
679      map.tailMap("a").keySet().add("a");
680      fail();
681    } catch (UnsupportedOperationException expected) {
682    }
683    try {
684      map.headMap("r").keySet().add("a");
685      fail();
686    } catch (UnsupportedOperationException expected) {
687    }
688    try {
689      map.headMap("r").tailMap("m").keySet().add("a");
690      fail();
691    } catch (UnsupportedOperationException expected) {
692    }
693  }
694
695  public void testAsMapSortedEmpty() {
696    SortedSet<String> strings = new NonNavigableSortedSet();
697    SortedMap<String, Integer> map = Maps.asMap(strings, LENGTH_FUNCTION);
698    assertThat(map.entrySet()).isEmpty();
699    assertTrue(map.isEmpty());
700    assertNull(map.get("five"));
701  }
702
703  public void testToMap() {
704    Iterable<String> strings = ImmutableList.of("one", "two", "three");
705    ImmutableMap<String, Integer> map = Maps.toMap(strings, LENGTH_FUNCTION);
706    assertEquals(ImmutableMap.of("one", 3, "two", 3, "three", 5), map);
707    assertThat(map.entrySet()).has().exactly(
708        mapEntry("one", 3),
709        mapEntry("two", 3),
710        mapEntry("three", 5)).inOrder();
711  }
712
713  public void testToMapIterator() {
714    Iterator<String> strings = ImmutableList.of("one", "two", "three").iterator();
715    ImmutableMap<String, Integer> map = Maps.toMap(strings, LENGTH_FUNCTION);
716    assertEquals(ImmutableMap.of("one", 3, "two", 3, "three", 5), map);
717    assertThat(map.entrySet()).has().exactly(
718        mapEntry("one", 3),
719        mapEntry("two", 3),
720        mapEntry("three", 5)).inOrder();
721  }
722
723  public void testToMapWithDuplicateKeys() {
724    Iterable<String> strings = ImmutableList.of("one", "two", "three", "two", "one");
725    ImmutableMap<String, Integer> map = Maps.toMap(strings, LENGTH_FUNCTION);
726    assertEquals(ImmutableMap.of("one", 3, "two", 3, "three", 5), map);
727    assertThat(map.entrySet()).has().exactly(
728        mapEntry("one", 3),
729        mapEntry("two", 3),
730        mapEntry("three", 5)).inOrder();
731  }
732
733  public void testToMapWithNullKeys() {
734    Iterable<String> strings = Arrays.asList("one", null, "three");
735    try {
736      Maps.toMap(strings, Functions.constant("foo"));
737      fail();
738    } catch (NullPointerException expected) {
739    }
740  }
741
742  public void testToMapWithNullValues() {
743    Iterable<String> strings = ImmutableList.of("one", "two", "three");
744    try {
745      Maps.toMap(strings, Functions.constant(null));
746      fail();
747    } catch (NullPointerException expected) {
748    }
749  }
750
751  private static final BiMap<Integer, String> INT_TO_STRING_MAP =
752      new ImmutableBiMap.Builder<Integer, String>()
753          .put(1, "one")
754          .put(2, "two")
755          .put(3, "three")
756          .build();
757
758  public void testUniqueIndexCollection() {
759    ImmutableMap<Integer, String> outputMap =
760        Maps.uniqueIndex(INT_TO_STRING_MAP.values(),
761            Functions.forMap(INT_TO_STRING_MAP.inverse()));
762    assertEquals(INT_TO_STRING_MAP, outputMap);
763  }
764
765  public void testUniqueIndexIterable() {
766    ImmutableMap<Integer, String> outputMap =
767        Maps.uniqueIndex(new Iterable<String>() {
768          @Override
769          public Iterator<String> iterator() {
770            return INT_TO_STRING_MAP.values().iterator();
771          }
772        },
773        Functions.forMap(INT_TO_STRING_MAP.inverse()));
774    assertEquals(INT_TO_STRING_MAP, outputMap);
775  }
776
777  public void testUniqueIndexIterator() {
778    ImmutableMap<Integer, String> outputMap =
779        Maps.uniqueIndex(INT_TO_STRING_MAP.values().iterator(),
780            Functions.forMap(INT_TO_STRING_MAP.inverse()));
781    assertEquals(INT_TO_STRING_MAP, outputMap);
782  }
783
784  /** Can't create the map if more than one value maps to the same key. */
785  public void testUniqueIndexDuplicates() {
786    try {
787      Maps.uniqueIndex(ImmutableSet.of("one", "uno"), Functions.constant(1));
788      fail();
789    } catch (IllegalArgumentException expected) {
790    }
791  }
792
793  /** Null values are not allowed. */
794  public void testUniqueIndexNullValue() {
795    List<String> listWithNull = Lists.newArrayList((String) null);
796    try {
797      Maps.uniqueIndex(listWithNull, Functions.constant(1));
798      fail();
799    } catch (NullPointerException expected) {
800    }
801  }
802
803  /** Null keys aren't allowed either. */
804  public void testUniqueIndexNullKey() {
805    List<String> oneStringList = Lists.newArrayList("foo");
806    try {
807      Maps.uniqueIndex(oneStringList, Functions.constant(null));
808      fail();
809    } catch (NullPointerException expected) {
810    }
811  }
812
813  public void testAsConverter_nominal() throws Exception {
814    ImmutableBiMap<String, Integer> biMap = ImmutableBiMap.of(
815        "one", 1,
816        "two", 2);
817    Converter<String, Integer> converter = Maps.asConverter(biMap);
818    for (Entry<String, Integer> entry : biMap.entrySet()) {
819      assertSame(entry.getValue(), converter.convert(entry.getKey()));
820    }
821  }
822
823  public void testAsConverter_inverse() throws Exception {
824    ImmutableBiMap<String, Integer> biMap = ImmutableBiMap.of(
825        "one", 1,
826        "two", 2);
827    Converter<String, Integer> converter = Maps.asConverter(biMap);
828    for (Entry<String, Integer> entry : biMap.entrySet()) {
829      assertSame(entry.getKey(), converter.reverse().convert(entry.getValue()));
830    }
831  }
832
833  public void testAsConverter_noMapping() throws Exception {
834    ImmutableBiMap<String, Integer> biMap = ImmutableBiMap.of(
835        "one", 1,
836        "two", 2);
837    Converter<String, Integer> converter = Maps.asConverter(biMap);
838    try {
839      converter.convert("three");
840      fail();
841    } catch (IllegalArgumentException expected) {
842    }
843  }
844
845  public void testAsConverter_nullConversions() throws Exception {
846    ImmutableBiMap<String, Integer> biMap = ImmutableBiMap.of(
847        "one", 1,
848        "two", 2);
849    Converter<String, Integer> converter = Maps.asConverter(biMap);
850    assertNull(converter.convert(null));
851    assertNull(converter.reverse().convert(null));
852  }
853
854  public void testAsConverter_isAView() throws Exception {
855    BiMap<String, Integer> biMap = HashBiMap.create();
856    biMap.put("one", 1);
857    biMap.put("two", 2);
858    Converter<String, Integer> converter = Maps.asConverter(biMap);
859
860    assertSame(1, converter.convert("one"));
861    assertSame(2, converter.convert("two"));
862    try {
863      converter.convert("three");
864      fail();
865    } catch (IllegalArgumentException expected) {
866    }
867
868    biMap.put("three", 3);
869
870    assertSame(1, converter.convert("one"));
871    assertSame(2, converter.convert("two"));
872    assertSame(3, converter.convert("three"));
873  }
874
875  public void testAsConverter_withNullMapping() throws Exception {
876    BiMap<String, Integer> biMap = HashBiMap.create();
877    biMap.put("one", 1);
878    biMap.put("two", 2);
879    biMap.put("three", null);
880    try {
881      Maps.asConverter(biMap).convert("three");
882      fail();
883    } catch (IllegalArgumentException expected) {
884    }
885  }
886
887  public void testAsConverter_toString() {
888    ImmutableBiMap<String, Integer> biMap = ImmutableBiMap.of(
889        "one", 1,
890        "two", 2);
891    Converter<String, Integer> converter = Maps.asConverter(biMap);
892    assertEquals("Maps.asConverter({one=1, two=2})", converter.toString());
893  }
894
895  public void testAsConverter_serialization() {
896    ImmutableBiMap<String, Integer> biMap = ImmutableBiMap.of(
897        "one", 1,
898        "two", 2);
899    Converter<String, Integer> converter = Maps.asConverter(biMap);
900    SerializableTester.reserializeAndAssert(converter);
901  }
902
903  public void testUnmodifiableBiMap() {
904    BiMap<Integer, String> mod = HashBiMap.create();
905    mod.put(1, "one");
906    mod.put(2, "two");
907    mod.put(3, "three");
908
909    BiMap<Number, String> unmod = Maps.<Number, String>unmodifiableBiMap(mod);
910
911    /* No aliasing on inverse operations. */
912    assertSame(unmod.inverse(), unmod.inverse());
913    assertSame(unmod, unmod.inverse().inverse());
914
915    /* Unmodifiable is a view. */
916    mod.put(4, "four");
917    assertEquals(true, unmod.get(4).equals("four"));
918    assertEquals(true, unmod.inverse().get("four").equals(4));
919
920    /* UnsupportedOperationException on direct modifications. */
921    try {
922      unmod.put(4, "four");
923      fail("UnsupportedOperationException expected");
924    } catch (UnsupportedOperationException expected) {}
925    try {
926      unmod.forcePut(4, "four");
927      fail("UnsupportedOperationException expected");
928    } catch (UnsupportedOperationException expected) {}
929    try {
930      unmod.putAll(Collections.singletonMap(4, "four"));
931      fail("UnsupportedOperationException expected");
932    } catch (UnsupportedOperationException expected) {}
933
934    /* UnsupportedOperationException on indirect modifications. */
935    BiMap<String, Number> inverse = unmod.inverse();
936    try {
937      inverse.put("four", 4);
938      fail("UnsupportedOperationException expected");
939    } catch (UnsupportedOperationException expected) {}
940    try {
941      inverse.forcePut("four", 4);
942      fail("UnsupportedOperationException expected");
943    } catch (UnsupportedOperationException expected) {}
944    try {
945      inverse.putAll(Collections.singletonMap("four", 4));
946      fail("UnsupportedOperationException expected");
947    } catch (UnsupportedOperationException expected) {}
948    Set<String> values = unmod.values();
949    try {
950      values.remove("four");
951      fail("UnsupportedOperationException expected");
952    } catch (UnsupportedOperationException expected) {}
953    Set<Map.Entry<Number, String>> entries = unmod.entrySet();
954    Map.Entry<Number, String> entry = entries.iterator().next();
955    try {
956      entry.setValue("four");
957      fail("UnsupportedOperationException expected");
958    } catch (UnsupportedOperationException expected) {}
959    @SuppressWarnings("unchecked")
960    Map.Entry<Integer, String> entry2
961        = (Map.Entry<Integer, String>) entries.toArray()[0];
962    try {
963      entry2.setValue("four");
964      fail("UnsupportedOperationException expected");
965    } catch (UnsupportedOperationException expected) {}
966  }
967
968  public void testImmutableEntry() {
969    Map.Entry<String, Integer> e = Maps.immutableEntry("foo", 1);
970    assertEquals("foo", e.getKey());
971    assertEquals(1, (int) e.getValue());
972    try {
973      e.setValue(2);
974      fail("UnsupportedOperationException expected");
975    } catch (UnsupportedOperationException expected) {}
976    assertEquals("foo=1", e.toString());
977    assertEquals(101575, e.hashCode());
978  }
979
980  public void testImmutableEntryNull() {
981    Map.Entry<String, Integer> e
982        = Maps.immutableEntry((String) null, (Integer) null);
983    assertNull(e.getKey());
984    assertNull(e.getValue());
985    try {
986      e.setValue(null);
987      fail("UnsupportedOperationException expected");
988    } catch (UnsupportedOperationException expected) {}
989    assertEquals("null=null", e.toString());
990    assertEquals(0, e.hashCode());
991  }
992
993  /** See {@link SynchronizedBiMapTest} for more tests. */
994  public void testSynchronizedBiMap() {
995    BiMap<String, Integer> bimap = HashBiMap.create();
996    bimap.put("one", 1);
997    BiMap<String, Integer> sync = Maps.synchronizedBiMap(bimap);
998    bimap.put("two", 2);
999    sync.put("three", 3);
1000    assertEquals(ImmutableSet.of(1, 2, 3), bimap.inverse().keySet());
1001    assertEquals(ImmutableSet.of(1, 2, 3), sync.inverse().keySet());
1002  }
1003
1004  private static final Predicate<String> NOT_LENGTH_3
1005      = new Predicate<String>() {
1006        @Override
1007        public boolean apply(String input) {
1008          return input == null || input.length() != 3;
1009        }
1010      };
1011
1012  private static final Predicate<Integer> EVEN
1013      = new Predicate<Integer>() {
1014        @Override
1015        public boolean apply(Integer input) {
1016          return input == null || input % 2 == 0;
1017        }
1018      };
1019
1020  private static final Predicate<Entry<String, Integer>> CORRECT_LENGTH
1021      = new Predicate<Entry<String, Integer>>() {
1022        @Override
1023        public boolean apply(Entry<String, Integer> input) {
1024          return input.getKey().length() == input.getValue();
1025        }
1026      };
1027
1028  private static final Function<Integer, Double> SQRT_FUNCTION = new Function<Integer, Double>() {
1029      @Override
1030      public Double apply(Integer in) {
1031        return Math.sqrt(in);
1032      }
1033    };
1034
1035  public static class FilteredMapTest extends TestCase {
1036    Map<String, Integer> createUnfiltered() {
1037      return Maps.newHashMap();
1038    }
1039
1040    public void testFilteredKeysIllegalPut() {
1041      Map<String, Integer> unfiltered = createUnfiltered();
1042      Map<String, Integer> filtered = Maps.filterKeys(unfiltered, NOT_LENGTH_3);
1043      filtered.put("a", 1);
1044      filtered.put("b", 2);
1045      assertEquals(ImmutableMap.of("a", 1, "b", 2), filtered);
1046
1047      try {
1048        filtered.put("yyy", 3);
1049        fail();
1050      } catch (IllegalArgumentException expected) {}
1051    }
1052
1053    public void testFilteredKeysIllegalPutAll() {
1054      Map<String, Integer> unfiltered = createUnfiltered();
1055      Map<String, Integer> filtered = Maps.filterKeys(unfiltered, NOT_LENGTH_3);
1056      filtered.put("a", 1);
1057      filtered.put("b", 2);
1058      assertEquals(ImmutableMap.of("a", 1, "b", 2), filtered);
1059
1060      try {
1061        filtered.putAll(ImmutableMap.of("c", 3, "zzz", 4, "b", 5));
1062        fail();
1063      } catch (IllegalArgumentException expected) {}
1064
1065      assertEquals(ImmutableMap.of("a", 1, "b", 2), filtered);
1066    }
1067
1068    public void testFilteredKeysFilteredReflectsBackingChanges() {
1069      Map<String, Integer> unfiltered = createUnfiltered();
1070      Map<String, Integer> filtered = Maps.filterKeys(unfiltered, NOT_LENGTH_3);
1071      unfiltered.put("two", 2);
1072      unfiltered.put("three", 3);
1073      unfiltered.put("four", 4);
1074      assertEquals(ImmutableMap.of("two", 2, "three", 3, "four", 4), unfiltered);
1075      assertEquals(ImmutableMap.of("three", 3, "four", 4), filtered);
1076
1077      unfiltered.remove("three");
1078      assertEquals(ImmutableMap.of("two", 2, "four", 4), unfiltered);
1079      assertEquals(ImmutableMap.of("four", 4), filtered);
1080
1081      unfiltered.clear();
1082      assertEquals(ImmutableMap.of(), unfiltered);
1083      assertEquals(ImmutableMap.of(), filtered);
1084    }
1085
1086    public void testFilteredValuesIllegalPut() {
1087      Map<String, Integer> unfiltered = createUnfiltered();
1088      Map<String, Integer> filtered = Maps.filterValues(unfiltered, EVEN);
1089      filtered.put("a", 2);
1090      unfiltered.put("b", 4);
1091      unfiltered.put("c", 5);
1092      assertEquals(ImmutableMap.of("a", 2, "b", 4), filtered);
1093
1094      try {
1095        filtered.put("yyy", 3);
1096        fail();
1097      } catch (IllegalArgumentException expected) {}
1098      assertEquals(ImmutableMap.of("a", 2, "b", 4), filtered);
1099    }
1100
1101    public void testFilteredValuesIllegalPutAll() {
1102      Map<String, Integer> unfiltered = createUnfiltered();
1103      Map<String, Integer> filtered = Maps.filterValues(unfiltered, EVEN);
1104      filtered.put("a", 2);
1105      unfiltered.put("b", 4);
1106      unfiltered.put("c", 5);
1107      assertEquals(ImmutableMap.of("a", 2, "b", 4), filtered);
1108
1109      try {
1110        filtered.putAll(ImmutableMap.of("c", 4, "zzz", 5, "b", 6));
1111        fail();
1112      } catch (IllegalArgumentException expected) {}
1113      assertEquals(ImmutableMap.of("a", 2, "b", 4), filtered);
1114    }
1115
1116    public void testFilteredValuesIllegalSetValue() {
1117      Map<String, Integer> unfiltered = createUnfiltered();
1118      Map<String, Integer> filtered = Maps.filterValues(unfiltered, EVEN);
1119      filtered.put("a", 2);
1120      filtered.put("b", 4);
1121      assertEquals(ImmutableMap.of("a", 2, "b", 4), filtered);
1122
1123      Entry<String, Integer> entry = filtered.entrySet().iterator().next();
1124      try {
1125        entry.setValue(5);
1126        fail();
1127      } catch (IllegalArgumentException expected) {}
1128
1129      assertEquals(ImmutableMap.of("a", 2, "b", 4), filtered);
1130    }
1131
1132    public void testFilteredValuesClear() {
1133      Map<String, Integer> unfiltered = createUnfiltered();
1134      unfiltered.put("one", 1);
1135      unfiltered.put("two", 2);
1136      unfiltered.put("three", 3);
1137      unfiltered.put("four", 4);
1138      Map<String, Integer> filtered = Maps.filterValues(unfiltered, EVEN);
1139      assertEquals(ImmutableMap.of("one", 1, "two", 2, "three", 3, "four", 4),
1140          unfiltered);
1141      assertEquals(ImmutableMap.of("two", 2, "four", 4), filtered);
1142
1143      filtered.clear();
1144      assertEquals(ImmutableMap.of("one", 1, "three", 3), unfiltered);
1145      assertTrue(filtered.isEmpty());
1146    }
1147
1148    public void testFilteredEntriesIllegalPut() {
1149      Map<String, Integer> unfiltered = createUnfiltered();
1150      unfiltered.put("cat", 3);
1151      unfiltered.put("dog", 2);
1152      unfiltered.put("horse", 5);
1153      Map<String, Integer> filtered
1154          = Maps.filterEntries(unfiltered, CORRECT_LENGTH);
1155      assertEquals(ImmutableMap.of("cat", 3, "horse", 5), filtered);
1156
1157      filtered.put("chicken", 7);
1158      assertEquals(ImmutableMap.of("cat", 3, "horse", 5, "chicken", 7), filtered);
1159
1160      try {
1161        filtered.put("cow", 7);
1162        fail();
1163      } catch (IllegalArgumentException expected) {}
1164      assertEquals(ImmutableMap.of("cat", 3, "horse", 5, "chicken", 7), filtered);
1165    }
1166
1167    public void testFilteredEntriesIllegalPutAll() {
1168      Map<String, Integer> unfiltered = createUnfiltered();
1169      unfiltered.put("cat", 3);
1170      unfiltered.put("dog", 2);
1171      unfiltered.put("horse", 5);
1172      Map<String, Integer> filtered
1173          = Maps.filterEntries(unfiltered, CORRECT_LENGTH);
1174      assertEquals(ImmutableMap.of("cat", 3, "horse", 5), filtered);
1175
1176      filtered.put("chicken", 7);
1177      assertEquals(ImmutableMap.of("cat", 3, "horse", 5, "chicken", 7), filtered);
1178
1179      try {
1180        filtered.putAll(ImmutableMap.of("sheep", 5, "cow", 7));
1181        fail();
1182      } catch (IllegalArgumentException expected) {}
1183      assertEquals(ImmutableMap.of("cat", 3, "horse", 5, "chicken", 7), filtered);
1184    }
1185
1186    public void testFilteredEntriesObjectPredicate() {
1187      Map<String, Integer> unfiltered = createUnfiltered();
1188      unfiltered.put("cat", 3);
1189      unfiltered.put("dog", 2);
1190      unfiltered.put("horse", 5);
1191      Predicate<Object> predicate = Predicates.alwaysFalse();
1192      Map<String, Integer> filtered
1193          = Maps.filterEntries(unfiltered, predicate);
1194      assertTrue(filtered.isEmpty());
1195    }
1196
1197    public void testFilteredEntriesWildCardEntryPredicate() {
1198      Map<String, Integer> unfiltered = createUnfiltered();
1199      unfiltered.put("cat", 3);
1200      unfiltered.put("dog", 2);
1201      unfiltered.put("horse", 5);
1202      Predicate<Entry<?, ?>> predicate = new Predicate<Entry<?, ?>>() {
1203        @Override
1204        public boolean apply(Entry<?, ?> input) {
1205          return "cat".equals(input.getKey())
1206              || Integer.valueOf(2) == input.getValue();
1207        }
1208      };
1209      Map<String, Integer> filtered
1210          = Maps.filterEntries(unfiltered, predicate);
1211      assertEquals(ImmutableMap.of("cat", 3, "dog", 2), filtered);
1212    }
1213  }
1214
1215  public static class FilteredSortedMapTest extends FilteredMapTest {
1216    @Override
1217    SortedMap<String, Integer> createUnfiltered() {
1218      return Maps.newTreeMap();
1219    }
1220
1221    public void testFilterKeysIdentifiesSortedMap() {
1222      SortedMap<String, Integer> map = createUnfiltered();
1223      assertTrue(Maps.filterKeys((Map<String, Integer>) map, NOT_LENGTH_3)
1224          instanceof SortedMap);
1225    }
1226
1227    public void testFilterValuesIdentifiesSortedMap() {
1228      SortedMap<String, Integer> map = createUnfiltered();
1229      assertTrue(Maps.filterValues((Map<String, Integer>) map, EVEN)
1230          instanceof SortedMap);
1231    }
1232
1233    public void testFilterEntriesIdentifiesSortedMap() {
1234      SortedMap<String, Integer> map = createUnfiltered();
1235      assertTrue(Maps.filterEntries((Map<String, Integer>) map, CORRECT_LENGTH)
1236          instanceof SortedMap);
1237    }
1238
1239    public void testFirstAndLastKeyFilteredMap() {
1240      SortedMap<String, Integer> unfiltered = createUnfiltered();
1241      unfiltered.put("apple", 2);
1242      unfiltered.put("banana", 6);
1243      unfiltered.put("cat", 3);
1244      unfiltered.put("dog", 5);
1245
1246      SortedMap<String, Integer> filtered = Maps.filterEntries(unfiltered, CORRECT_LENGTH);
1247      assertEquals("banana", filtered.firstKey());
1248      assertEquals("cat", filtered.lastKey());
1249    }
1250
1251    public void testHeadSubTailMap_FilteredMap() {
1252      SortedMap<String, Integer> unfiltered = createUnfiltered();
1253      unfiltered.put("apple", 2);
1254      unfiltered.put("banana", 6);
1255      unfiltered.put("cat", 4);
1256      unfiltered.put("dog", 3);
1257      SortedMap<String, Integer> filtered = Maps.filterEntries(unfiltered, CORRECT_LENGTH);
1258
1259      assertEquals(ImmutableMap.of("banana", 6), filtered.headMap("dog"));
1260      assertEquals(ImmutableMap.of(), filtered.headMap("banana"));
1261      assertEquals(ImmutableMap.of("banana", 6, "dog", 3), filtered.headMap("emu"));
1262
1263      assertEquals(ImmutableMap.of("banana", 6), filtered.subMap("banana", "dog"));
1264      assertEquals(ImmutableMap.of("dog", 3), filtered.subMap("cat", "emu"));
1265
1266      assertEquals(ImmutableMap.of("dog", 3), filtered.tailMap("cat"));
1267      assertEquals(ImmutableMap.of("banana", 6, "dog", 3), filtered.tailMap("banana"));
1268    }
1269  }
1270
1271  public static class FilteredBiMapTest extends FilteredMapTest {
1272    @Override
1273    BiMap<String, Integer> createUnfiltered() {
1274      return HashBiMap.create();
1275    }
1276
1277    public void testFilterKeysIdentifiesBiMap() {
1278      BiMap<String, Integer> map = createUnfiltered();
1279      assertTrue(Maps.filterKeys((Map<String, Integer>) map, NOT_LENGTH_3)
1280          instanceof BiMap);
1281    }
1282
1283    public void testFilterValuesIdentifiesBiMap() {
1284      BiMap<String, Integer> map = createUnfiltered();
1285      assertTrue(Maps.filterValues((Map<String, Integer>) map, EVEN)
1286          instanceof BiMap);
1287    }
1288
1289    public void testFilterEntriesIdentifiesBiMap() {
1290      BiMap<String, Integer> map = createUnfiltered();
1291      assertTrue(Maps.filterEntries((Map<String, Integer>) map, CORRECT_LENGTH)
1292          instanceof BiMap);
1293    }
1294  }
1295
1296  public void testTransformValues() {
1297    Map<String, Integer> map = ImmutableMap.of("a", 4, "b", 9);
1298    Map<String, Double> transformed = transformValues(map, SQRT_FUNCTION);
1299
1300    assertEquals(ImmutableMap.of("a", 2.0, "b", 3.0), transformed);
1301  }
1302
1303  public void testTransformValuesSecretlySorted() {
1304    Map<String, Integer> map =
1305        sortedNotNavigable(ImmutableSortedMap.of("a", 4, "b", 9));
1306    Map<String, Double> transformed = transformValues(map, SQRT_FUNCTION);
1307
1308    assertEquals(ImmutableMap.of("a", 2.0, "b", 3.0), transformed);
1309    assertTrue(transformed instanceof SortedMap);
1310  }
1311
1312  public void testTransformEntries() {
1313    Map<String, String> map = ImmutableMap.of("a", "4", "b", "9");
1314    EntryTransformer<String, String, String> concat =
1315        new EntryTransformer<String, String, String>() {
1316          @Override
1317          public String transformEntry(String key, String value) {
1318            return key + value;
1319          }
1320        };
1321    Map<String, String> transformed = transformEntries(map, concat);
1322
1323    assertEquals(ImmutableMap.of("a", "a4", "b", "b9"), transformed);
1324  }
1325
1326  public void testTransformEntriesSecretlySorted() {
1327    Map<String, String> map = ImmutableSortedMap.of("a", "4", "b", "9");
1328    EntryTransformer<String, String, String> concat =
1329        new EntryTransformer<String, String, String>() {
1330          @Override
1331          public String transformEntry(String key, String value) {
1332            return key + value;
1333          }
1334        };
1335    Map<String, String> transformed = transformEntries(map, concat);
1336
1337    assertEquals(ImmutableMap.of("a", "a4", "b", "b9"), transformed);
1338    assertTrue(transformed instanceof SortedMap);
1339  }
1340
1341  @SuppressWarnings("unused")
1342  public void testTransformEntriesGenerics() {
1343    Map<Object, Object> map1 = ImmutableMap.<Object, Object>of(1, 2);
1344    Map<Object, Number> map2 = ImmutableMap.<Object, Number>of(1, 2);
1345    Map<Object, Integer> map3 = ImmutableMap.<Object, Integer>of(1, 2);
1346    Map<Number, Object> map4 = ImmutableMap.<Number, Object>of(1, 2);
1347    Map<Number, Number> map5 = ImmutableMap.<Number, Number>of(1, 2);
1348    Map<Number, Integer> map6 = ImmutableMap.<Number, Integer>of(1, 2);
1349    Map<Integer, Object> map7 = ImmutableMap.<Integer, Object>of(1, 2);
1350    Map<Integer, Number> map8 = ImmutableMap.<Integer, Number>of(1, 2);
1351    Map<Integer, Integer> map9 = ImmutableMap.<Integer, Integer>of(1, 2);
1352    Map<? extends Number, ? extends Number> map0 = ImmutableMap.of(1, 2);
1353
1354    EntryTransformer<Number, Number, Double> transformer =
1355        new EntryTransformer<Number, Number, Double>() {
1356          @Override
1357          public Double transformEntry(Number key, Number value) {
1358            return key.doubleValue() + value.doubleValue();
1359          }
1360        };
1361
1362    Map<Object, Double> objectKeyed;
1363    Map<Number, Double> numberKeyed;
1364    Map<Integer, Double> integerKeyed;
1365
1366    numberKeyed = transformEntries(map5, transformer);
1367    numberKeyed = transformEntries(map6, transformer);
1368    integerKeyed = transformEntries(map8, transformer);
1369    integerKeyed = transformEntries(map9, transformer);
1370
1371    Map<? extends Number, Double> wildcarded = transformEntries(map0, transformer);
1372
1373    // Can't loosen the key type:
1374    // objectKeyed = transformEntries(map5, transformer);
1375    // objectKeyed = transformEntries(map6, transformer);
1376    // objectKeyed = transformEntries(map8, transformer);
1377    // objectKeyed = transformEntries(map9, transformer);
1378    // numberKeyed = transformEntries(map8, transformer);
1379    // numberKeyed = transformEntries(map9, transformer);
1380
1381    // Can't loosen the value type:
1382    // Map<Number, Number> looseValued1 = transformEntries(map5, transformer);
1383    // Map<Number, Number> looseValued2 = transformEntries(map6, transformer);
1384    // Map<Integer, Number> looseValued3 = transformEntries(map8, transformer);
1385    // Map<Integer, Number> looseValued4 = transformEntries(map9, transformer);
1386
1387    // Can't call with too loose a key:
1388    // transformEntries(map1, transformer);
1389    // transformEntries(map2, transformer);
1390    // transformEntries(map3, transformer);
1391
1392    // Can't call with too loose a value:
1393    // transformEntries(map1, transformer);
1394    // transformEntries(map4, transformer);
1395    // transformEntries(map7, transformer);
1396  }
1397
1398  public void testTransformEntriesExample() {
1399    Map<String, Boolean> options =
1400        ImmutableMap.of("verbose", true, "sort", false);
1401    EntryTransformer<String, Boolean, String> flagPrefixer =
1402        new EntryTransformer<String, Boolean, String>() {
1403          @Override
1404          public String transformEntry(String key, Boolean value) {
1405            return value ? key : "no" + key;
1406          }
1407        };
1408    Map<String, String> transformed = transformEntries(options, flagPrefixer);
1409    assertEquals("{verbose=verbose, sort=nosort}", transformed.toString());
1410  }
1411
1412  // Logically this would accept a NavigableMap, but that won't work under GWT.
1413  private static <K, V> SortedMap<K, V> sortedNotNavigable(
1414      final SortedMap<K, V> map) {
1415    return new ForwardingSortedMap<K, V>() {
1416      @Override protected SortedMap<K, V> delegate() {
1417        return map;
1418      }
1419    };
1420  }
1421
1422  public void testSortedMapTransformValues() {
1423    SortedMap<String, Integer> map =
1424        sortedNotNavigable(ImmutableSortedMap.of("a", 4, "b", 9));
1425    SortedMap<String, Double> transformed =
1426        transformValues(map, SQRT_FUNCTION);
1427
1428    /*
1429     * We'd like to sanity check that we didn't get a NavigableMap out, but we
1430     * can't easily do so while maintaining GWT compatibility.
1431     */
1432    assertEquals(ImmutableSortedMap.of("a", 2.0, "b", 3.0), transformed);
1433  }
1434
1435  public void testSortedMapTransformEntries() {
1436    SortedMap<String, String> map =
1437        sortedNotNavigable(ImmutableSortedMap.of("a", "4", "b", "9"));
1438    EntryTransformer<String, String, String> concat =
1439        new EntryTransformer<String, String, String>() {
1440          @Override
1441          public String transformEntry(String key, String value) {
1442            return key + value;
1443          }
1444        };
1445    SortedMap<String, String> transformed = transformEntries(map, concat);
1446
1447    /*
1448     * We'd like to sanity check that we didn't get a NavigableMap out, but we
1449     * can't easily do so while maintaining GWT compatibility.
1450     */
1451    assertEquals(ImmutableSortedMap.of("a", "a4", "b", "b9"), transformed);
1452  }
1453}
1454
1455