001/*
002 * Copyright (C) 2007 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkArgument;
020import static com.google.common.base.Preconditions.checkNotNull;
021
022import com.google.common.annotations.Beta;
023import com.google.common.annotations.GwtCompatible;
024import com.google.common.annotations.GwtIncompatible;
025import com.google.common.base.Function;
026import com.google.common.base.Joiner.MapJoiner;
027import com.google.common.base.Objects;
028import com.google.common.base.Predicate;
029import com.google.common.base.Predicates;
030import com.google.common.base.Supplier;
031import com.google.common.collect.MapDifference.ValueDifference;
032import com.google.common.primitives.Ints;
033
034import java.io.Serializable;
035import java.util.AbstractCollection;
036import java.util.AbstractMap;
037import java.util.AbstractSet;
038import java.util.Collection;
039import java.util.Collections;
040import java.util.Comparator;
041import java.util.EnumMap;
042import java.util.Enumeration;
043import java.util.HashMap;
044import java.util.IdentityHashMap;
045import java.util.Iterator;
046import java.util.LinkedHashMap;
047import java.util.Map;
048import java.util.Map.Entry;
049import java.util.Properties;
050import java.util.Set;
051import java.util.SortedMap;
052import java.util.TreeMap;
053import java.util.concurrent.ConcurrentMap;
054
055import javax.annotation.Nullable;
056
057/**
058 * Static utility methods pertaining to {@link Map} instances. Also see this
059 * class's counterparts {@link Lists} and {@link Sets}.
060 *
061 * @author Kevin Bourrillion
062 * @author Mike Bostock
063 * @author Isaac Shum
064 * @author Louis Wasserman
065 * @since 2 (imported from Google Collections Library)
066 */
067@GwtCompatible(emulated = true)
068public final class Maps {
069  private Maps() {}
070
071  /**
072   * Creates a <i>mutable</i>, empty {@code HashMap} instance.
073   *
074   * <p><b>Note:</b> if mutability is not required, use {@link
075   * ImmutableMap#of()} instead.
076   *
077   * <p><b>Note:</b> if {@code K} is an {@code enum} type, use {@link
078   * #newEnumMap} instead.
079   *
080   * @return a new, empty {@code HashMap}
081   */
082  public static <K, V> HashMap<K, V> newHashMap() {
083    return new HashMap<K, V>();
084  }
085
086  /**
087   * Creates a {@code HashMap} instance with enough capacity to hold the
088   * specified number of elements without rehashing.
089   *
090   * @param expectedSize the expected size
091   * @return a new, empty {@code HashMap} with enough capacity to hold {@code
092   *         expectedSize} elements without rehashing
093   * @throws IllegalArgumentException if {@code expectedSize} is negative
094   */
095  public static <K, V> HashMap<K, V> newHashMapWithExpectedSize(
096      int expectedSize) {
097    /*
098     * The HashMap is constructed with an initialCapacity that's greater than
099     * expectedSize. The larger value is necessary because HashMap resizes its
100     * internal array if the map size exceeds loadFactor * initialCapacity.
101     */
102    return new HashMap<K, V>(capacity(expectedSize));
103  }
104
105  /**
106   * Returns an appropriate value for the "capacity" (in reality, "minimum table
107   * size") parameter of a {@link HashMap} constructor, such that the resulting
108   * table will be between 25% and 50% full when it contains {@code
109   * expectedSize} entries, unless {@code expectedSize} is greater than
110   * {@link Integer#MAX_VALUE} / 2.
111   *
112   * @throws IllegalArgumentException if {@code expectedSize} is negative
113   */
114  static int capacity(int expectedSize) {
115    checkArgument(expectedSize >= 0);
116    // Avoid the int overflow if expectedSize > (Integer.MAX_VALUE / 2)
117    return Ints.saturatedCast(Math.max(expectedSize * 2L, 16L));
118  }
119
120  /**
121   * Creates a <i>mutable</i> {@code HashMap} instance with the same mappings as
122   * the specified map.
123   *
124   * <p><b>Note:</b> if mutability is not required, use {@link
125   * ImmutableMap#copyOf(Map)} instead.
126   *
127   * <p><b>Note:</b> if {@code K} is an {@link Enum} type, use {@link
128   * #newEnumMap} instead.
129   *
130   * @param map the mappings to be placed in the new map
131   * @return a new {@code HashMap} initialized with the mappings from {@code
132   *         map}
133   */
134  public static <K, V> HashMap<K, V> newHashMap(
135      Map<? extends K, ? extends V> map) {
136    return new HashMap<K, V>(map);
137  }
138
139  /**
140   * Creates a <i>mutable</i>, empty, insertion-ordered {@code LinkedHashMap}
141   * instance.
142   *
143   * <p><b>Note:</b> if mutability is not required, use {@link
144   * ImmutableMap#of()} instead.
145   *
146   * @return a new, empty {@code LinkedHashMap}
147   */
148  public static <K, V> LinkedHashMap<K, V> newLinkedHashMap() {
149    return new LinkedHashMap<K, V>();
150  }
151
152  /**
153   * Creates a <i>mutable</i>, insertion-ordered {@code LinkedHashMap} instance
154   * with the same mappings as the specified map.
155   *
156   * <p><b>Note:</b> if mutability is not required, use {@link
157   * ImmutableMap#copyOf(Map)} instead.
158   *
159   * @param map the mappings to be placed in the new map
160   * @return a new, {@code LinkedHashMap} initialized with the mappings from
161   *         {@code map}
162   */
163  public static <K, V> LinkedHashMap<K, V> newLinkedHashMap(
164      Map<? extends K, ? extends V> map) {
165    return new LinkedHashMap<K, V>(map);
166  }
167
168  /**
169   * Returns a general-purpose instance of {@code ConcurrentMap}, which supports
170   * all optional operations of the ConcurrentMap interface. It does not permit
171   * null keys or values. It is serializable.
172   *
173   * <p>This is currently accomplished by calling {@link MapMaker#makeMap()}.
174   *
175   * <p>It is preferable to use {@code MapMaker} directly (rather than through
176   * this method), as it presents numerous useful configuration options,
177   * such as the concurrency level, load factor, key/value reference types,
178   * and value computation.
179   *
180   * @return a new, empty {@code ConcurrentMap}
181   * @since 3
182   */
183  public static <K, V> ConcurrentMap<K, V> newConcurrentMap() {
184    return new MapMaker().<K, V>makeMap();
185  }
186
187  /**
188   * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the natural
189   * ordering of its elements.
190   *
191   * <p><b>Note:</b> if mutability is not required, use {@link
192   * ImmutableSortedMap#of()} instead.
193   *
194   * @return a new, empty {@code TreeMap}
195   */
196  @SuppressWarnings("unchecked") // eclipse doesn't like the raw Comparable
197  public static <K extends Comparable, V> TreeMap<K, V> newTreeMap() {
198    return new TreeMap<K, V>();
199  }
200
201  /**
202   * Creates a <i>mutable</i> {@code TreeMap} instance with the same mappings as
203   * the specified map and using the same ordering as the specified map.
204   *
205   * <p><b>Note:</b> if mutability is not required, use {@link
206   * ImmutableSortedMap#copyOfSorted(SortedMap)} instead.
207   *
208   * @param map the sorted map whose mappings are to be placed in the new map
209   *        and whose comparator is to be used to sort the new map
210   * @return a new {@code TreeMap} initialized with the mappings from {@code
211   *         map} and using the comparator of {@code map}
212   */
213  public static <K, V> TreeMap<K, V> newTreeMap(SortedMap<K, ? extends V> map) {
214    return new TreeMap<K, V>(map);
215  }
216
217  /**
218   * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the given
219   * comparator.
220   *
221   * <p><b>Note:</b> if mutability is not required, use {@code
222   * ImmutableSortedMap.orderedBy(comparator).build()} instead.
223   *
224   * @param comparator the comparator to sort the keys with
225   * @return a new, empty {@code TreeMap}
226   */
227  public static <K, V> TreeMap<K, V> newTreeMap(
228      @Nullable Comparator<? super K> comparator) {
229    // Ideally, the extra type parameter "C" shouldn't be necessary. It is a
230    // work-around of a compiler type inference quirk that prevents the
231    // following code from being compiled:
232    // Comparator<Class<?>> comparator = null;
233    // Map<Class<? extends Throwable>, String> map = newTreeMap(comparator);
234    return new TreeMap<K, V>(comparator);
235  }
236
237  /**
238   * Creates an {@code EnumMap} instance.
239   *
240   * @param type the key type for this map
241   * @return a new, empty {@code EnumMap}
242   */
243  public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(Class<K> type) {
244    return new EnumMap<K, V>(checkNotNull(type));
245  }
246
247  /**
248   * Creates an {@code EnumMap} with the same mappings as the specified map.
249   *
250   * @param map the map from which to initialize this {@code EnumMap}
251   * @return a new {@code EnumMap} initialized with the mappings from {@code
252   *         map}
253   * @throws IllegalArgumentException if {@code m} is not an {@code EnumMap}
254   *         instance and contains no mappings
255   */
256  public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(
257      Map<K, ? extends V> map) {
258    return new EnumMap<K, V>(map);
259  }
260
261  /**
262   * Creates an {@code IdentityHashMap} instance.
263   *
264   * @return a new, empty {@code IdentityHashMap}
265   */
266  public static <K, V> IdentityHashMap<K, V> newIdentityHashMap() {
267    return new IdentityHashMap<K, V>();
268  }
269
270  /**
271   * Returns a synchronized (thread-safe) bimap backed by the specified bimap.
272   * In order to guarantee serial access, it is critical that <b>all</b> access
273   * to the backing bimap is accomplished through the returned bimap.
274   *
275   * <p>It is imperative that the user manually synchronize on the returned map
276   * when accessing any of its collection views: <pre>   {@code
277   *
278   *   BiMap<Long, String> map = Maps.synchronizedBiMap(
279   *       HashBiMap.<Long, String>create());
280   *   ...
281   *   Set<Long> set = map.keySet();  // Needn't be in synchronized block
282   *   ...
283   *   synchronized (map) {  // Synchronizing on map, not set!
284   *     Iterator<Long> it = set.iterator(); // Must be in synchronized block
285   *     while (it.hasNext()) {
286   *       foo(it.next());
287   *     }
288   *   }}</pre>
289   *
290   * Failure to follow this advice may result in non-deterministic behavior.
291   *
292   * <p>The returned bimap will be serializable if the specified bimap is
293   * serializable.
294   *
295   * @param bimap the bimap to be wrapped in a synchronized view
296   * @return a sychronized view of the specified bimap
297   */
298  public static <K, V> BiMap<K, V> synchronizedBiMap(BiMap<K, V> bimap) {
299    return Synchronized.biMap(bimap, null);
300  }
301
302  /**
303   * Computes the difference between two maps. This difference is an immutable
304   * snapshot of the state of the maps at the time this method is called. It
305   * will never change, even if the maps change at a later time.
306   *
307   * <p>Since this method uses {@code HashMap} instances internally, the keys of
308   * the supplied maps must be well-behaved with respect to
309   * {@link Object#equals} and {@link Object#hashCode}.
310   *
311   * <p><b>Note:</b>If you only need to know whether two maps have the same
312   * mappings, call {@code left.equals(right)} instead of this method.
313   *
314   * @param left the map to treat as the "left" map for purposes of comparison
315   * @param right the map to treat as the "right" map for purposes of comparison
316   * @return the difference between the two maps
317   */
318  public static <K, V> MapDifference<K, V> difference(
319      Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right) {
320    Map<K, V> onlyOnLeft = newHashMap();
321    Map<K, V> onlyOnRight = new HashMap<K, V>(right); // will whittle it down
322    Map<K, V> onBoth = newHashMap();
323    Map<K, MapDifference.ValueDifference<V>> differences = newHashMap();
324    boolean eq = true;
325
326    for (Entry<? extends K, ? extends V> entry : left.entrySet()) {
327      K leftKey = entry.getKey();
328      V leftValue = entry.getValue();
329      if (right.containsKey(leftKey)) {
330        V rightValue = onlyOnRight.remove(leftKey);
331        if (Objects.equal(leftValue, rightValue)) {
332          onBoth.put(leftKey, leftValue);
333        } else {
334          eq = false;
335          differences.put(
336              leftKey, new ValueDifferenceImpl<V>(leftValue, rightValue));
337        }
338      } else {
339        eq = false;
340        onlyOnLeft.put(leftKey, leftValue);
341      }
342    }
343
344    boolean areEqual = eq && onlyOnRight.isEmpty();
345    return mapDifference(
346        areEqual, onlyOnLeft, onlyOnRight, onBoth, differences);
347  }
348
349  private static <K, V> MapDifference<K, V> mapDifference(boolean areEqual,
350      Map<K, V> onlyOnLeft, Map<K, V> onlyOnRight, Map<K, V> onBoth,
351      Map<K, ValueDifference<V>> differences) {
352    return new MapDifferenceImpl<K, V>(areEqual,
353        Collections.unmodifiableMap(onlyOnLeft),
354        Collections.unmodifiableMap(onlyOnRight),
355        Collections.unmodifiableMap(onBoth),
356        Collections.unmodifiableMap(differences));
357  }
358
359  static class MapDifferenceImpl<K, V> implements MapDifference<K, V> {
360    final boolean areEqual;
361    final Map<K, V> onlyOnLeft;
362    final Map<K, V> onlyOnRight;
363    final Map<K, V> onBoth;
364    final Map<K, ValueDifference<V>> differences;
365
366    MapDifferenceImpl(boolean areEqual, Map<K, V> onlyOnLeft,
367        Map<K, V> onlyOnRight, Map<K, V> onBoth,
368        Map<K, ValueDifference<V>> differences) {
369      this.areEqual = areEqual;
370      this.onlyOnLeft = onlyOnLeft;
371      this.onlyOnRight = onlyOnRight;
372      this.onBoth = onBoth;
373      this.differences = differences;
374    }
375
376    @Override
377    public boolean areEqual() {
378      return areEqual;
379    }
380
381    @Override
382    public Map<K, V> entriesOnlyOnLeft() {
383      return onlyOnLeft;
384    }
385
386    @Override
387    public Map<K, V> entriesOnlyOnRight() {
388      return onlyOnRight;
389    }
390
391    @Override
392    public Map<K, V> entriesInCommon() {
393      return onBoth;
394    }
395
396    @Override
397    public Map<K, ValueDifference<V>> entriesDiffering() {
398      return differences;
399    }
400
401    @Override public boolean equals(Object object) {
402      if (object == this) {
403        return true;
404      }
405      if (object instanceof MapDifference) {
406        MapDifference<?, ?> other = (MapDifference<?, ?>) object;
407        return entriesOnlyOnLeft().equals(other.entriesOnlyOnLeft())
408            && entriesOnlyOnRight().equals(other.entriesOnlyOnRight())
409            && entriesInCommon().equals(other.entriesInCommon())
410            && entriesDiffering().equals(other.entriesDiffering());
411      }
412      return false;
413    }
414
415    @Override public int hashCode() {
416      return Objects.hashCode(entriesOnlyOnLeft(), entriesOnlyOnRight(),
417          entriesInCommon(), entriesDiffering());
418    }
419
420    @Override public String toString() {
421      if (areEqual) {
422        return "equal";
423      }
424
425      StringBuilder result = new StringBuilder("not equal");
426      if (!onlyOnLeft.isEmpty()) {
427        result.append(": only on left=").append(onlyOnLeft);
428      }
429      if (!onlyOnRight.isEmpty()) {
430        result.append(": only on right=").append(onlyOnRight);
431      }
432      if (!differences.isEmpty()) {
433        result.append(": value differences=").append(differences);
434      }
435      return result.toString();
436    }
437  }
438
439  static class ValueDifferenceImpl<V>
440      implements MapDifference.ValueDifference<V> {
441    private final V left;
442    private final V right;
443
444    ValueDifferenceImpl(@Nullable V left, @Nullable V right) {
445      this.left = left;
446      this.right = right;
447    }
448
449    @Override
450    public V leftValue() {
451      return left;
452    }
453
454    @Override
455    public V rightValue() {
456      return right;
457    }
458
459    @Override public boolean equals(@Nullable Object object) {
460      if (object instanceof MapDifference.ValueDifference<?>) {
461        MapDifference.ValueDifference<?> that =
462            (MapDifference.ValueDifference<?>) object;
463        return Objects.equal(this.left, that.leftValue())
464            && Objects.equal(this.right, that.rightValue());
465      }
466      return false;
467    }
468
469    @Override public int hashCode() {
470      return Objects.hashCode(left, right);
471    }
472
473    @Override public String toString() {
474      return "(" + left + ", " + right + ")";
475    }
476  }
477
478  /**
479   * Returns an immutable map for which the {@link Map#values} are the given
480   * elements in the given order, and each key is the product of invoking a
481   * supplied function on its corresponding value.
482   *
483   * @param values the values to use when constructing the {@code Map}
484   * @param keyFunction the function used to produce the key for each value
485   * @return a map mapping the result of evaluating the function {@code
486   *         keyFunction} on each value in the input collection to that value
487   * @throws IllegalArgumentException if {@code keyFunction} produces the same
488   *         key for more than one value in the input collection
489   * @throws NullPointerException if any elements of {@code values} is null, or
490   *         if {@code keyFunction} produces {@code null} for any value
491   */
492  public static <K, V> ImmutableMap<K, V> uniqueIndex(
493      Iterable<V> values, Function<? super V, K> keyFunction) {
494    checkNotNull(keyFunction);
495    ImmutableMap.Builder<K, V> builder = ImmutableMap.builder();
496    for (V value : values) {
497      builder.put(keyFunction.apply(value), value);
498    }
499    return builder.build();
500  }
501
502  /**
503   * Creates an {@code ImmutableMap<String, String>} from a {@code Properties}
504   * instance. Properties normally derive from {@code Map<Object, Object>}, but
505   * they typically contain strings, which is awkward. This method lets you get
506   * a plain-old-{@code Map} out of a {@code Properties}.
507   *
508   * @param properties a {@code Properties} object to be converted
509   * @return an immutable map containing all the entries in {@code properties}
510   * @throws ClassCastException if any key in {@code Properties} is not a {@code
511   *         String}
512   * @throws NullPointerException if any key or value in {@code Properties} is
513   *         null
514   */
515  @GwtIncompatible("java.util.Properties")
516  public static ImmutableMap<String, String> fromProperties(
517      Properties properties) {
518    ImmutableMap.Builder<String, String> builder = ImmutableMap.builder();
519
520    for (Enumeration<?> e = properties.propertyNames(); e.hasMoreElements();) {
521      String key = (String) e.nextElement();
522      builder.put(key, properties.getProperty(key));
523    }
524
525    return builder.build();
526  }
527
528  /**
529   * Returns an immutable map entry with the specified key and value. The {@link
530   * Entry#setValue} operation throws an {@link UnsupportedOperationException}.
531   *
532   * <p>The returned entry is serializable.
533   *
534   * @param key the key to be associated with the returned entry
535   * @param value the value to be associated with the returned entry
536   */
537  @GwtCompatible(serializable = true)
538  public static <K, V> Entry<K, V> immutableEntry(
539      @Nullable K key, @Nullable V value) {
540    return new ImmutableEntry<K, V>(key, value);
541  }
542
543  /**
544   * Returns an unmodifiable view of the specified set of entries. The {@link
545   * Entry#setValue} operation throws an {@link UnsupportedOperationException},
546   * as do any operations that would modify the returned set.
547   *
548   * @param entrySet the entries for which to return an unmodifiable view
549   * @return an unmodifiable view of the entries
550   */
551  static <K, V> Set<Entry<K, V>> unmodifiableEntrySet(
552      Set<Entry<K, V>> entrySet) {
553    return new UnmodifiableEntrySet<K, V>(
554        Collections.unmodifiableSet(entrySet));
555  }
556
557  /**
558   * Returns an unmodifiable view of the specified map entry. The {@link
559   * Entry#setValue} operation throws an {@link UnsupportedOperationException}.
560   * This also has the side-effect of redefining {@code equals} to comply with
561   * the Entry contract, to avoid a possible nefarious implementation of equals.
562   *
563   * @param entry the entry for which to return an unmodifiable view
564   * @return an unmodifiable view of the entry
565   */
566  static <K, V> Entry<K, V> unmodifiableEntry(final Entry<K, V> entry) {
567    checkNotNull(entry);
568    return new AbstractMapEntry<K, V>() {
569      @Override public K getKey() {
570        return entry.getKey();
571      }
572
573      @Override public V getValue() {
574        return entry.getValue();
575      }
576    };
577  }
578
579  /** @see Multimaps#unmodifiableEntries */
580  static class UnmodifiableEntries<K, V>
581      extends ForwardingCollection<Entry<K, V>> {
582    private final Collection<Entry<K, V>> entries;
583
584    UnmodifiableEntries(Collection<Entry<K, V>> entries) {
585      this.entries = entries;
586    }
587
588    @Override protected Collection<Entry<K, V>> delegate() {
589      return entries;
590    }
591
592    @Override public Iterator<Entry<K, V>> iterator() {
593      final Iterator<Entry<K, V>> delegate = super.iterator();
594      return new ForwardingIterator<Entry<K, V>>() {
595        @Override public Entry<K, V> next() {
596          return unmodifiableEntry(super.next());
597        }
598
599        @Override public void remove() {
600          throw new UnsupportedOperationException();
601        }
602
603        @Override protected Iterator<Entry<K, V>> delegate() {
604          return delegate;
605        }
606      };
607    }
608
609    // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
610
611    @Override public boolean add(Entry<K, V> element) {
612      throw new UnsupportedOperationException();
613    }
614
615    @Override public boolean addAll(
616        Collection<? extends Entry<K, V>> collection) {
617      throw new UnsupportedOperationException();
618    }
619
620    @Override public void clear() {
621      throw new UnsupportedOperationException();
622    }
623
624    @Override public boolean remove(Object object) {
625      throw new UnsupportedOperationException();
626    }
627
628    @Override public boolean removeAll(Collection<?> collection) {
629      throw new UnsupportedOperationException();
630    }
631
632    @Override public boolean retainAll(Collection<?> collection) {
633      throw new UnsupportedOperationException();
634    }
635
636    @Override public Object[] toArray() {
637      return standardToArray();
638    }
639
640    @Override public <T> T[] toArray(T[] array) {
641      return standardToArray(array);
642    }
643  }
644
645  /** @see Maps#unmodifiableEntrySet(Set) */
646  static class UnmodifiableEntrySet<K, V>
647      extends UnmodifiableEntries<K, V> implements Set<Entry<K, V>> {
648    UnmodifiableEntrySet(Set<Entry<K, V>> entries) {
649      super(entries);
650    }
651
652    // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
653
654    @Override public boolean equals(@Nullable Object object) {
655      return Sets.equalsImpl(this, object);
656    }
657
658    @Override public int hashCode() {
659      return Sets.hashCodeImpl(this);
660    }
661  }
662
663  /**
664   * Returns an unmodifiable view of the specified bimap. This method allows
665   * modules to provide users with "read-only" access to internal bimaps. Query
666   * operations on the returned bimap "read through" to the specified bimap, and
667   * attemps to modify the returned map, whether direct or via its collection
668   * views, result in an {@code UnsupportedOperationException}.
669   *
670   * <p>The returned bimap will be serializable if the specified bimap is
671   * serializable.
672   *
673   * @param bimap the bimap for which an unmodifiable view is to be returned
674   * @return an unmodifiable view of the specified bimap
675   */
676  public static <K, V> BiMap<K, V> unmodifiableBiMap(
677      BiMap<? extends K, ? extends V> bimap) {
678    return new UnmodifiableBiMap<K, V>(bimap, null);
679  }
680
681  /** @see Maps#unmodifiableBiMap(BiMap) */
682  private static class UnmodifiableBiMap<K, V>
683      extends ForwardingMap<K, V> implements BiMap<K, V>, Serializable {
684    final Map<K, V> unmodifiableMap;
685    final BiMap<? extends K, ? extends V> delegate;
686    transient BiMap<V, K> inverse;
687    transient Set<V> values;
688
689    UnmodifiableBiMap(BiMap<? extends K, ? extends V> delegate,
690        @Nullable BiMap<V, K> inverse) {
691      unmodifiableMap = Collections.unmodifiableMap(delegate);
692      this.delegate = delegate;
693      this.inverse = inverse;
694    }
695
696    @Override protected Map<K, V> delegate() {
697      return unmodifiableMap;
698    }
699
700    @Override
701    public V forcePut(K key, V value) {
702      throw new UnsupportedOperationException();
703    }
704
705    @Override
706    public BiMap<V, K> inverse() {
707      BiMap<V, K> result = inverse;
708      return (result == null)
709          ? inverse = new UnmodifiableBiMap<V, K>(delegate.inverse(), this)
710          : result;
711    }
712
713    @Override public Set<V> values() {
714      Set<V> result = values;
715      return (result == null)
716          ? values = Collections.unmodifiableSet(delegate.values())
717          : result;
718    }
719
720    private static final long serialVersionUID = 0;
721  }
722
723  /**
724   * Returns a view of a map where each value is transformed by a function. All
725   * other properties of the map, such as iteration order, are left intact. For
726   * example, the code: <pre>   {@code
727   *
728   *   Map<String, Integer> map = ImmutableMap.of("a", 4, "b", 9);
729   *   Function<Integer, Double> sqrt =
730   *       new Function<Integer, Double>() {
731   *         public Double apply(Integer in) {
732   *           return Math.sqrt((int) in);
733   *         }
734   *       };
735   *   Map<String, Double> transformed = Maps.transformValues(map, sqrt);
736   *   System.out.println(transformed);}</pre>
737   *
738   * ... prints {@code {a=2.0, b=3.0}}.
739   *
740   * <p>Changes in the underlying map are reflected in this view. Conversely,
741   * this view supports removal operations, and these are reflected in the
742   * underlying map.
743   *
744   * <p>It's acceptable for the underlying map to contain null keys, and even
745   * null values provided that the function is capable of accepting null input.
746   * The transformed map might contain null values, if the function sometimes
747   * gives a null result.
748   *
749   * <p>The returned map is not thread-safe or serializable, even if the
750   * underlying map is.
751   *
752   * <p>The function is applied lazily, invoked when needed. This is necessary
753   * for the returned map to be a view, but it means that the function will be
754   * applied many times for bulk operations like {@link Map#containsValue} and
755   * {@code Map.toString()}. For this to perform well, {@code function} should
756   * be fast. To avoid lazy evaluation when the returned map doesn't need to be
757   * a view, copy the returned map into a new map of your choosing.
758   */
759  public static <K, V1, V2> Map<K, V2> transformValues(
760      Map<K, V1> fromMap, final Function<? super V1, V2> function) {
761    checkNotNull(function);
762    EntryTransformer<K, V1, V2> transformer =
763        new EntryTransformer<K, V1, V2>() {
764          @Override
765          public V2 transformEntry(K key, V1 value) {
766            return function.apply(value);
767          }
768        };
769    return transformEntries(fromMap, transformer);
770  }
771
772  /**
773   * Returns a view of a map whose values are derived from the original map's
774   * entries. In contrast to {@link #transformValues}, this method's
775   * entry-transformation logic may depend on the key as well as the value.
776   *
777   * <p>All other properties of the transformed map, such as iteration order,
778   * are left intact. For example, the code: <pre>   {@code
779   *
780   *   Map<String, Boolean> options =
781   *       ImmutableMap.of("verbose", true, "sort", false);
782   *   EntryTransformer<String, Boolean, String> flagPrefixer =
783   *       new EntryTransformer<String, Boolean, String>() {
784   *         public String transformEntry(String key, Boolean value) {
785   *           return value ? key : "no" + key;
786   *         }
787   *       };
788   *   Map<String, String> transformed =
789   *       Maps.transformEntries(options, flagPrefixer);
790   *   System.out.println(transformed);}</pre>
791   *
792   * ... prints {@code {verbose=verbose, sort=nosort}}.
793   *
794   * <p>Changes in the underlying map are reflected in this view. Conversely,
795   * this view supports removal operations, and these are reflected in the
796   * underlying map.
797   *
798   * <p>It's acceptable for the underlying map to contain null keys and null
799   * values provided that the transformer is capable of accepting null inputs.
800   * The transformed map might contain null values if the transformer sometimes
801   * gives a null result.
802   *
803   * <p>The returned map is not thread-safe or serializable, even if the
804   * underlying map is.
805   *
806   * <p>The transformer is applied lazily, invoked when needed. This is
807   * necessary for the returned map to be a view, but it means that the
808   * transformer will be applied many times for bulk operations like {@link
809   * Map#containsValue} and {@link Object#toString}. For this to perform well,
810   * {@code transformer} should be fast. To avoid lazy evaluation when the
811   * returned map doesn't need to be a view, copy the returned map into a new
812   * map of your choosing.
813   *
814   * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
815   * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
816   * that {@code k2} is also of type {@code K}. Using an {@code
817   * EntryTransformer} key type for which this may not hold, such as {@code
818   * ArrayList}, may risk a {@code ClassCastException} when calling methods on
819   * the transformed map.
820   *
821   * @since 7
822   */
823  @Beta
824  public static <K, V1, V2> Map<K, V2> transformEntries(
825      Map<K, V1> fromMap,
826      EntryTransformer<? super K, ? super V1, V2> transformer) {
827    return new TransformedEntriesMap<K, V1, V2>(fromMap, transformer);
828  }
829
830  /**
831   * A transformation of the value of a key-value pair, using both key and value
832   * as inputs. To apply the transformation to a map, use
833   * {@link Maps#transformEntries(Map, EntryTransformer)}.
834   *
835   * @param <K> the key type of the input and output entries
836   * @param <V1> the value type of the input entry
837   * @param <V2> the value type of the output entry
838   * @since 7
839   */
840  @Beta
841  public interface EntryTransformer<K, V1, V2> {
842    /**
843     * Determines an output value based on a key-value pair. This method is
844     * <i>generally expected</i>, but not absolutely required, to have the
845     * following properties:
846     *
847     * <ul>
848     * <li>Its execution does not cause any observable side effects.
849     * <li>The computation is <i>consistent with equals</i>; that is,
850     *     {@link Objects#equal Objects.equal}{@code (k1, k2) &&}
851     *     {@link Objects#equal}{@code (v1, v2)} implies that {@code
852     *     Objects.equal(transformer.transform(k1, v1),
853     *     transformer.transform(k2, v2))}.
854     * </ul>
855     *
856     * @throws NullPointerException if the key or value is null and this
857     *     transformer does not accept null arguments
858     */
859    V2 transformEntry(@Nullable K key, @Nullable V1 value);
860  }
861
862  static class TransformedEntriesMap<K, V1, V2>
863      extends AbstractMap<K, V2> {
864    final Map<K, V1> fromMap;
865    final EntryTransformer<? super K, ? super V1, V2> transformer;
866
867    TransformedEntriesMap(
868        Map<K, V1> fromMap,
869        EntryTransformer<? super K, ? super V1, V2> transformer) {
870      this.fromMap = checkNotNull(fromMap);
871      this.transformer = checkNotNull(transformer);
872    }
873
874    @Override public int size() {
875      return fromMap.size();
876    }
877
878    @Override public boolean containsKey(Object key) {
879      return fromMap.containsKey(key);
880    }
881
882    // safe as long as the user followed the <b>Warning</b> in the javadoc
883    @SuppressWarnings("unchecked")
884    @Override public V2 get(Object key) {
885      V1 value = fromMap.get(key);
886      return (value != null || fromMap.containsKey(key))
887          ? transformer.transformEntry((K) key, value)
888          : null;
889    }
890
891    // safe as long as the user followed the <b>Warning</b> in the javadoc
892    @SuppressWarnings("unchecked")
893    @Override public V2 remove(Object key) {
894      return fromMap.containsKey(key)
895          ? transformer.transformEntry((K) key, fromMap.remove(key))
896          : null;
897    }
898
899    @Override public void clear() {
900      fromMap.clear();
901    }
902
903    EntrySet entrySet;
904
905    @Override public Set<Entry<K, V2>> entrySet() {
906      EntrySet result = entrySet;
907      if (result == null) {
908        entrySet = result = new EntrySet();
909      }
910      return result;
911    }
912
913    class EntrySet extends AbstractSet<Entry<K, V2>> {
914      @Override public int size() {
915        return TransformedEntriesMap.this.size();
916      }
917
918      @Override public Iterator<Entry<K, V2>> iterator() {
919        final Iterator<Entry<K, V1>> mapIterator =
920            fromMap.entrySet().iterator();
921
922        return new Iterator<Entry<K, V2>>() {
923          @Override
924          public boolean hasNext() {
925            return mapIterator.hasNext();
926          }
927
928          @Override
929          public Entry<K, V2> next() {
930            final Entry<K, V1> entry = mapIterator.next();
931            return new AbstractMapEntry<K, V2>() {
932              @Override public K getKey() {
933                return entry.getKey();
934              }
935
936              @Override public V2 getValue() {
937                return transformer.transformEntry(
938                    entry.getKey(), entry.getValue());
939              }
940            };
941          }
942
943          @Override
944          public void remove() {
945            mapIterator.remove();
946          }
947        };
948      }
949
950      @Override public void clear() {
951        fromMap.clear();
952      }
953
954      @Override public boolean contains(Object o) {
955        if (!(o instanceof Entry)) {
956          return false;
957        }
958        Entry<?, ?> entry = (Entry<?, ?>) o;
959        Object entryKey = entry.getKey();
960        Object entryValue = entry.getValue();
961        V2 mapValue = TransformedEntriesMap.this.get(entryKey);
962        if (mapValue != null) {
963          return mapValue.equals(entryValue);
964        }
965        return entryValue == null && containsKey(entryKey);
966      }
967
968      @Override public boolean remove(Object o) {
969        if (contains(o)) {
970          Entry<?, ?> entry = (Entry<?, ?>) o;
971          Object key = entry.getKey();
972          fromMap.remove(key);
973          return true;
974        }
975        return false;
976      }
977    }
978  }
979
980  /**
981   * Returns a map containing the mappings in {@code unfiltered} whose keys
982   * satisfy a predicate. The returned map is a live view of {@code unfiltered};
983   * changes to one affect the other.
984   *
985   * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
986   * values()} views have iterators that don't support {@code remove()}, but all
987   * other methods are supported by the map and its views. When given a key that
988   * doesn't satisfy the predicate, the map's {@code put()} and {@code putAll()}
989   * methods throw an {@link IllegalArgumentException}.
990   *
991   * <p>When methods such as {@code removeAll()} and {@code clear()} are called
992   * on the filtered map or its views, only mappings whose keys satisfy the
993   * filter will be removed from the underlying map.
994   *
995   * <p>The returned map isn't threadsafe or serializable, even if {@code
996   * unfiltered} is.
997   *
998   * <p>Many of the filtered map's methods, such as {@code size()},
999   * iterate across every key/value mapping in the underlying map and determine
1000   * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1001   * faster to copy the filtered map and use the copy.
1002   *
1003   * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with
1004   * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
1005   * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
1006   * inconsistent with equals.
1007   */
1008  public static <K, V> Map<K, V> filterKeys(
1009      Map<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
1010    checkNotNull(keyPredicate);
1011    Predicate<Entry<K, V>> entryPredicate =
1012        new Predicate<Entry<K, V>>() {
1013          @Override
1014          public boolean apply(Entry<K, V> input) {
1015            return keyPredicate.apply(input.getKey());
1016          }
1017        };
1018    return (unfiltered instanceof AbstractFilteredMap)
1019        ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
1020        : new FilteredKeyMap<K, V>(
1021            checkNotNull(unfiltered), keyPredicate, entryPredicate);
1022  }
1023
1024  /**
1025   * Returns a map containing the mappings in {@code unfiltered} whose values
1026   * satisfy a predicate. The returned map is a live view of {@code unfiltered};
1027   * changes to one affect the other.
1028   *
1029   * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1030   * values()} views have iterators that don't support {@code remove()}, but all
1031   * other methods are supported by the map and its views. When given a value
1032   * that doesn't satisfy the predicate, the map's {@code put()}, {@code
1033   * putAll()}, and {@link Entry#setValue} methods throw an {@link
1034   * IllegalArgumentException}.
1035   *
1036   * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1037   * on the filtered map or its views, only mappings whose values satisfy the
1038   * filter will be removed from the underlying map.
1039   *
1040   * <p>The returned map isn't threadsafe or serializable, even if {@code
1041   * unfiltered} is.
1042   *
1043   * <p>Many of the filtered map's methods, such as {@code size()},
1044   * iterate across every key/value mapping in the underlying map and determine
1045   * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1046   * faster to copy the filtered map and use the copy.
1047   *
1048   * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with
1049   * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
1050   * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
1051   * inconsistent with equals.
1052   */
1053  public static <K, V> Map<K, V> filterValues(
1054      Map<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
1055    checkNotNull(valuePredicate);
1056    Predicate<Entry<K, V>> entryPredicate =
1057        new Predicate<Entry<K, V>>() {
1058          @Override
1059          public boolean apply(Entry<K, V> input) {
1060            return valuePredicate.apply(input.getValue());
1061          }
1062        };
1063    return filterEntries(unfiltered, entryPredicate);
1064  }
1065
1066  /**
1067   * Returns a map containing the mappings in {@code unfiltered} that satisfy a
1068   * predicate. The returned map is a live view of {@code unfiltered}; changes
1069   * to one affect the other.
1070   *
1071   * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
1072   * values()} views have iterators that don't support {@code remove()}, but all
1073   * other methods are supported by the map and its views. When given a
1074   * key/value pair that doesn't satisfy the predicate, the map's {@code put()}
1075   * and {@code putAll()} methods throw an {@link IllegalArgumentException}.
1076   * Similarly, the map's entries have a {@link Entry#setValue} method that
1077   * throws an {@link IllegalArgumentException} when the existing key and the
1078   * provided value don't satisfy the predicate.
1079   *
1080   * <p>When methods such as {@code removeAll()} and {@code clear()} are called
1081   * on the filtered map or its views, only mappings that satisfy the filter
1082   * will be removed from the underlying map.
1083   *
1084   * <p>The returned map isn't threadsafe or serializable, even if {@code
1085   * unfiltered} is.
1086   *
1087   * <p>Many of the filtered map's methods, such as {@code size()},
1088   * iterate across every key/value mapping in the underlying map and determine
1089   * which satisfy the filter. When a live view is <i>not</i> needed, it may be
1090   * faster to copy the filtered map and use the copy.
1091   *
1092   * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with
1093   * equals</i>, as documented at {@link Predicate#apply}.
1094   */
1095  public static <K, V> Map<K, V> filterEntries(
1096      Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
1097    checkNotNull(entryPredicate);
1098    return (unfiltered instanceof AbstractFilteredMap)
1099        ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
1100        : new FilteredEntryMap<K, V>(checkNotNull(unfiltered), entryPredicate);
1101  }
1102
1103  /**
1104   * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when
1105   * filtering a filtered map.
1106   */
1107  private static <K, V> Map<K, V> filterFiltered(AbstractFilteredMap<K, V> map,
1108      Predicate<? super Entry<K, V>> entryPredicate) {
1109    Predicate<Entry<K, V>> predicate =
1110        Predicates.and(map.predicate, entryPredicate);
1111    return new FilteredEntryMap<K, V>(map.unfiltered, predicate);
1112  }
1113
1114  private abstract static class AbstractFilteredMap<K, V>
1115      extends AbstractMap<K, V> {
1116    final Map<K, V> unfiltered;
1117    final Predicate<? super Entry<K, V>> predicate;
1118
1119    AbstractFilteredMap(
1120        Map<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) {
1121      this.unfiltered = unfiltered;
1122      this.predicate = predicate;
1123    }
1124
1125    boolean apply(Object key, V value) {
1126      // This method is called only when the key is in the map, implying that
1127      // key is a K.
1128      @SuppressWarnings("unchecked")
1129      K k = (K) key;
1130      return predicate.apply(Maps.immutableEntry(k, value));
1131    }
1132
1133    @Override public V put(K key, V value) {
1134      checkArgument(apply(key, value));
1135      return unfiltered.put(key, value);
1136    }
1137
1138    @Override public void putAll(Map<? extends K, ? extends V> map) {
1139      for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
1140        checkArgument(apply(entry.getKey(), entry.getValue()));
1141      }
1142      unfiltered.putAll(map);
1143    }
1144
1145    @Override public boolean containsKey(Object key) {
1146      return unfiltered.containsKey(key) && apply(key, unfiltered.get(key));
1147    }
1148
1149    @Override public V get(Object key) {
1150      V value = unfiltered.get(key);
1151      return ((value != null) && apply(key, value)) ? value : null;
1152    }
1153
1154    @Override public boolean isEmpty() {
1155      return entrySet().isEmpty();
1156    }
1157
1158    @Override public V remove(Object key) {
1159      return containsKey(key) ? unfiltered.remove(key) : null;
1160    }
1161
1162    Collection<V> values;
1163
1164    @Override public Collection<V> values() {
1165      Collection<V> result = values;
1166      return (result == null) ? values = new Values() : result;
1167    }
1168
1169    class Values extends AbstractCollection<V> {
1170      @Override public Iterator<V> iterator() {
1171        final Iterator<Entry<K, V>> entryIterator = entrySet().iterator();
1172        return new UnmodifiableIterator<V>() {
1173          @Override
1174          public boolean hasNext() {
1175            return entryIterator.hasNext();
1176          }
1177
1178          @Override
1179          public V next() {
1180            return entryIterator.next().getValue();
1181          }
1182        };
1183      }
1184
1185      @Override public int size() {
1186        return entrySet().size();
1187      }
1188
1189      @Override public void clear() {
1190        entrySet().clear();
1191      }
1192
1193      @Override public boolean isEmpty() {
1194        return entrySet().isEmpty();
1195      }
1196
1197      @Override public boolean remove(Object o) {
1198        Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1199        while (iterator.hasNext()) {
1200          Entry<K, V> entry = iterator.next();
1201          if (Objects.equal(o, entry.getValue()) && predicate.apply(entry)) {
1202            iterator.remove();
1203            return true;
1204          }
1205        }
1206        return false;
1207      }
1208
1209      @Override public boolean removeAll(Collection<?> collection) {
1210        checkNotNull(collection);
1211        boolean changed = false;
1212        Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1213        while (iterator.hasNext()) {
1214          Entry<K, V> entry = iterator.next();
1215          if (collection.contains(entry.getValue()) && predicate.apply(entry)) {
1216            iterator.remove();
1217            changed = true;
1218          }
1219        }
1220        return changed;
1221      }
1222
1223      @Override public boolean retainAll(Collection<?> collection) {
1224        checkNotNull(collection);
1225        boolean changed = false;
1226        Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1227        while (iterator.hasNext()) {
1228          Entry<K, V> entry = iterator.next();
1229          if (!collection.contains(entry.getValue())
1230              && predicate.apply(entry)) {
1231            iterator.remove();
1232            changed = true;
1233          }
1234        }
1235        return changed;
1236      }
1237
1238      @Override public Object[] toArray() {
1239        // creating an ArrayList so filtering happens once
1240        return Lists.newArrayList(iterator()).toArray();
1241      }
1242
1243      @Override public <T> T[] toArray(T[] array) {
1244        return Lists.newArrayList(iterator()).toArray(array);
1245      }
1246    }
1247  }
1248
1249  private static class FilteredKeyMap<K, V> extends AbstractFilteredMap<K, V> {
1250    Predicate<? super K> keyPredicate;
1251
1252    FilteredKeyMap(Map<K, V> unfiltered, Predicate<? super K> keyPredicate,
1253        Predicate<Entry<K, V>> entryPredicate) {
1254      super(unfiltered, entryPredicate);
1255      this.keyPredicate = keyPredicate;
1256    }
1257
1258    Set<Entry<K, V>> entrySet;
1259
1260    @Override public Set<Entry<K, V>> entrySet() {
1261      Set<Entry<K, V>> result = entrySet;
1262      return (result == null)
1263          ? entrySet = Sets.filter(unfiltered.entrySet(), predicate)
1264          : result;
1265    }
1266
1267    Set<K> keySet;
1268
1269    @Override public Set<K> keySet() {
1270      Set<K> result = keySet;
1271      return (result == null)
1272          ? keySet = Sets.filter(unfiltered.keySet(), keyPredicate)
1273          : result;
1274    }
1275
1276    // The cast is called only when the key is in the unfiltered map, implying
1277    // that key is a K.
1278    @Override
1279    @SuppressWarnings("unchecked")
1280    public boolean containsKey(Object key) {
1281      return unfiltered.containsKey(key) && keyPredicate.apply((K) key);
1282    }
1283  }
1284
1285  static class FilteredEntryMap<K, V> extends AbstractFilteredMap<K, V> {
1286    /**
1287     * Entries in this set satisfy the predicate, but they don't validate the
1288     * input to {@code Entry.setValue()}.
1289     */
1290    final Set<Entry<K, V>> filteredEntrySet;
1291
1292    FilteredEntryMap(
1293        Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
1294      super(unfiltered, entryPredicate);
1295      filteredEntrySet = Sets.filter(unfiltered.entrySet(), predicate);
1296    }
1297
1298    Set<Entry<K, V>> entrySet;
1299
1300    @Override public Set<Entry<K, V>> entrySet() {
1301      Set<Entry<K, V>> result = entrySet;
1302      return (result == null) ? entrySet = new EntrySet() : result;
1303    }
1304
1305    private class EntrySet extends ForwardingSet<Entry<K, V>> {
1306      @Override protected Set<Entry<K, V>> delegate() {
1307        return filteredEntrySet;
1308      }
1309
1310      @Override public Iterator<Entry<K, V>> iterator() {
1311        final Iterator<Entry<K, V>> iterator = filteredEntrySet.iterator();
1312        return new UnmodifiableIterator<Entry<K, V>>() {
1313          @Override
1314          public boolean hasNext() {
1315            return iterator.hasNext();
1316          }
1317
1318          @Override
1319          public Entry<K, V> next() {
1320            final Entry<K, V> entry = iterator.next();
1321            return new ForwardingMapEntry<K, V>() {
1322              @Override protected Entry<K, V> delegate() {
1323                return entry;
1324              }
1325
1326              @Override public V setValue(V value) {
1327                checkArgument(apply(entry.getKey(), value));
1328                return super.setValue(value);
1329              }
1330            };
1331          }
1332        };
1333      }
1334    }
1335
1336    Set<K> keySet;
1337
1338    @Override public Set<K> keySet() {
1339      Set<K> result = keySet;
1340      return (result == null) ? keySet = new KeySet() : result;
1341    }
1342
1343    private class KeySet extends AbstractSet<K> {
1344      @Override public Iterator<K> iterator() {
1345        final Iterator<Entry<K, V>> iterator = filteredEntrySet.iterator();
1346        return new UnmodifiableIterator<K>() {
1347          @Override
1348          public boolean hasNext() {
1349            return iterator.hasNext();
1350          }
1351
1352          @Override
1353          public K next() {
1354            return iterator.next().getKey();
1355          }
1356        };
1357      }
1358
1359      @Override public int size() {
1360        return filteredEntrySet.size();
1361      }
1362
1363      @Override public void clear() {
1364        filteredEntrySet.clear();
1365      }
1366
1367      @Override public boolean contains(Object o) {
1368        return containsKey(o);
1369      }
1370
1371      @Override public boolean remove(Object o) {
1372        if (containsKey(o)) {
1373          unfiltered.remove(o);
1374          return true;
1375        }
1376        return false;
1377      }
1378
1379      @Override public boolean removeAll(Collection<?> collection) {
1380        checkNotNull(collection); // for GWT
1381        boolean changed = false;
1382        for (Object obj : collection) {
1383          changed |= remove(obj);
1384        }
1385        return changed;
1386      }
1387
1388      @Override public boolean retainAll(Collection<?> collection) {
1389        checkNotNull(collection); // for GWT
1390        boolean changed = false;
1391        Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
1392        while (iterator.hasNext()) {
1393          Entry<K, V> entry = iterator.next();
1394          if (!collection.contains(entry.getKey()) && predicate.apply(entry)) {
1395            iterator.remove();
1396            changed = true;
1397          }
1398        }
1399        return changed;
1400      }
1401
1402      @Override public Object[] toArray() {
1403        // creating an ArrayList so filtering happens once
1404        return Lists.newArrayList(iterator()).toArray();
1405      }
1406
1407      @Override public <T> T[] toArray(T[] array) {
1408        return Lists.newArrayList(iterator()).toArray(array);
1409      }
1410    }
1411  }
1412
1413  /**
1414   * {@code AbstractMap} extension that implements {@link #isEmpty()} as {@code
1415   * entrySet().isEmpty()} instead of {@code size() == 0} to speed up
1416   * implementations where {@code size()} is O(n), and it delegates the {@code
1417   * isEmpty()} methods of its key set and value collection to this
1418   * implementation.
1419   */
1420  @GwtCompatible
1421  abstract static class ImprovedAbstractMap<K, V> extends AbstractMap<K, V> {
1422    /**
1423     * Creates the entry set to be returned by {@link #entrySet()}. This method
1424     * is invoked at most once on a given map, at the time when {@code entrySet}
1425     * is first called.
1426     */
1427    protected abstract Set<Entry<K, V>> createEntrySet();
1428
1429    private Set<Entry<K, V>> entrySet;
1430
1431    @Override public Set<Entry<K, V>> entrySet() {
1432      Set<Entry<K, V>> result = entrySet;
1433      if (result == null) {
1434        entrySet = result = createEntrySet();
1435      }
1436      return result;
1437    }
1438
1439    private Set<K> keySet;
1440
1441    @Override public Set<K> keySet() {
1442      Set<K> result = keySet;
1443      if (result == null) {
1444        final Set<K> delegate = super.keySet();
1445        keySet = result = new ForwardingSet<K>() {
1446          @Override protected Set<K> delegate() {
1447            return delegate;
1448          }
1449
1450          @Override public boolean isEmpty() {
1451            return ImprovedAbstractMap.this.isEmpty();
1452          }
1453
1454          @Override public boolean remove(Object object) {
1455            if (contains(object)) {
1456              ImprovedAbstractMap.this.remove(object);
1457              return true;
1458            }
1459            return false;
1460          }
1461        };
1462      }
1463      return result;
1464    }
1465
1466    private Collection<V> values;
1467
1468    @Override public Collection<V> values() {
1469      Collection<V> result = values;
1470      if (result == null) {
1471        final Collection<V> delegate = super.values();
1472        values = result = new ForwardingCollection<V>() {
1473          @Override protected Collection<V> delegate() {
1474            return delegate;
1475          }
1476
1477          @Override public boolean isEmpty() {
1478            return ImprovedAbstractMap.this.isEmpty();
1479          }
1480        };
1481      }
1482      return result;
1483    }
1484
1485    /**
1486     * Returns {@code true} if this map contains no key-value mappings.
1487     *
1488     * <p>The implementation returns {@code entrySet().isEmpty()}.
1489     *
1490     * @return {@code true} if this map contains no key-value mappings
1491     */
1492    @Override public boolean isEmpty() {
1493      return entrySet().isEmpty();
1494    }
1495  }
1496
1497  static final MapJoiner STANDARD_JOINER =
1498      Collections2.STANDARD_JOINER.withKeyValueSeparator("=");
1499
1500  /**
1501   * Delegates to {@link Map#get}. Returns {@code null} on {@code
1502   * ClassCastException}.
1503   */
1504  static <V> V safeGet(Map<?, V> map, Object key) {
1505    try {
1506      return map.get(key);
1507    } catch (ClassCastException e) {
1508      return null;
1509    }
1510  }
1511
1512  /**
1513   * Delegates to {@link Map#containsKey}. Returns {@code false} on {@code
1514   * ClassCastException}
1515   */
1516  static boolean safeContainsKey(Map<?, ?> map, Object key) {
1517    try {
1518      return map.containsKey(key);
1519    } catch (ClassCastException e) {
1520      return false;
1521    }
1522  }
1523
1524  /**
1525   * An implementation of {@link Map#entrySet}.
1526   */
1527  static <K, V> Set<Entry<K, V>> entrySetImpl(
1528      Map<K, V> map, Supplier<Iterator<Entry<K, V>>> entryIteratorSupplier) {
1529    return new EntrySetImpl<K, V>(map, entryIteratorSupplier);
1530  }
1531
1532  private static class EntrySetImpl<K, V> extends AbstractSet<Entry<K, V>> {
1533    private final Map<K, V> map;
1534    private final Supplier<Iterator<Entry<K, V>>> entryIteratorSupplier;
1535
1536    EntrySetImpl(
1537        Map<K, V> map, Supplier<Iterator<Entry<K, V>>> entryIteratorSupplier) {
1538      this.map = checkNotNull(map);
1539      this.entryIteratorSupplier = checkNotNull(entryIteratorSupplier);
1540    }
1541
1542    @Override public Iterator<Entry<K, V>> iterator() {
1543      return entryIteratorSupplier.get();
1544    }
1545
1546    @Override public int size() {
1547      return map.size();
1548    }
1549
1550    @Override public void clear() {
1551      map.clear();
1552    }
1553
1554    @Override public boolean contains(Object o) {
1555      if (o instanceof Entry) {
1556        Entry<?, ?> entry = (Entry<?, ?>) o;
1557        Object key = entry.getKey();
1558        if (map.containsKey(key)) {
1559          V value = map.get(entry.getKey());
1560          return Objects.equal(value, entry.getValue());
1561        }
1562      }
1563      return false;
1564    }
1565
1566    @Override public boolean isEmpty() {
1567      return map.isEmpty();
1568    }
1569
1570    @Override public boolean remove(Object o) {
1571      if (contains(o)) {
1572        Entry<?, ?> entry = (Entry<?, ?>) o;
1573        map.remove(entry.getKey());
1574        return true;
1575      }
1576      return false;
1577    }
1578
1579    @Override public int hashCode() {
1580      return map.hashCode();
1581    }
1582  }
1583
1584  /**
1585   * Implements {@code Collection.contains} safely for forwarding collections of
1586   * map entries. If {@code o} is an instance of {@code Map.Entry}, it is
1587   * wrapped using {@link #unmodifiableEntry} to protect against a possible
1588   * nefarious equals method.
1589   *
1590   * <p>Note that {@code c} is the backing (delegate) collection, rather than
1591   * the forwarding collection.
1592   *
1593   * @param c the delegate (unwrapped) collection of map entries
1594   * @param o the object that might be contained in {@code c}
1595   * @return {@code true} if {@code c} contains {@code o}
1596   */
1597  static <K, V> boolean containsEntryImpl(Collection<Entry<K, V>> c, Object o) {
1598    if (!(o instanceof Entry)) {
1599      return false;
1600    }
1601    return c.contains(unmodifiableEntry((Entry<?, ?>) o));
1602  }
1603
1604  /**
1605   * Implements {@code Collection.remove} safely for forwarding collections of
1606   * map entries. If {@code o} is an instance of {@code Map.Entry}, it is
1607   * wrapped using {@link #unmodifiableEntry} to protect against a possible
1608   * nefarious equals method.
1609   *
1610   * <p>Note that {@code c} is backing (delegate) collection, rather than the
1611   * forwarding collection.
1612   *
1613   * @param c the delegate (unwrapped) collection of map entries
1614   * @param o the object to remove from {@code c}
1615   * @return {@code true} if {@code c} was changed
1616   */
1617  static <K, V> boolean removeEntryImpl(Collection<Entry<K, V>> c, Object o) {
1618    if (!(o instanceof Entry)) {
1619      return false;
1620    }
1621    return c.remove(unmodifiableEntry((Entry<?, ?>) o));
1622  }
1623
1624  /**
1625   * An implementation of {@link Map#equals}.
1626   */
1627  static boolean equalsImpl(Map<?, ?> map, Object object) {
1628    if (map == object) {
1629      return true;
1630    }
1631    if (object instanceof Map) {
1632      Map<?, ?> o = (Map<?, ?>) object;
1633      return map.entrySet().equals(o.entrySet());
1634    }
1635    return false;
1636  }
1637
1638  /**
1639   * An implementation of {@link Map#hashCode}.
1640   */
1641  static int hashCodeImpl(Map<?, ?> map) {
1642    return Sets.hashCodeImpl(map.entrySet());
1643  }
1644
1645  /**
1646   * An implementation of {@link Map#toString}.
1647   */
1648  static String toStringImpl(Map<?, ?> map) {
1649    StringBuilder sb
1650        = Collections2.newStringBuilderForCollection(map.size()).append('{');
1651    STANDARD_JOINER.appendTo(sb, map);
1652    return sb.append('}').toString();
1653  }
1654
1655  /**
1656   * An implementation of {@link Map#putAll}.
1657   */
1658  static <K, V> void putAllImpl(
1659      Map<K, V> self, Map<? extends K, ? extends V> map) {
1660    for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
1661      self.put(entry.getKey(), entry.getValue());
1662    }
1663  }
1664
1665  /**
1666   * An implementation of {@link Map#keySet}.
1667   */
1668  static <K, V> Set<K> keySetImpl(final Map<K, V> map) {
1669    return new AbstractMapWrapper<K, V>(map).keySet();
1670  }
1671
1672  /**
1673   * An admittedly inefficient implementation of {@link Map#containsKey}.
1674   */
1675  static boolean containsKeyImpl(Map<?, ?> map, @Nullable Object key) {
1676    for (Entry<?, ?> entry : map.entrySet()) {
1677      if (Objects.equal(entry.getKey(), key)) {
1678        return true;
1679      }
1680    }
1681    return false;
1682  }
1683
1684  /**
1685   * An implementation of {@link Map#values}.
1686   */
1687  static <K, V> Collection<V> valuesImpl(Map<K, V> map) {
1688    return new AbstractMapWrapper<K, V>(map).values();
1689  }
1690
1691  /**
1692   * An implementation of {@link Map#containsValue}.
1693   */
1694  static boolean containsValueImpl(Map<?, ?> map, @Nullable Object value) {
1695    for (Entry<?, ?> entry : map.entrySet()) {
1696      if (Objects.equal(entry.getValue(), value)) {
1697        return true;
1698      }
1699    }
1700    return false;
1701  }
1702
1703  /**
1704   * A wrapper on a map that supplies the {@code ImprovedAbstractMap}
1705   * implementations of {@code keySet()} and {@code values()}.
1706   */
1707  private static final class AbstractMapWrapper<K, V>
1708      extends ImprovedAbstractMap<K, V>{
1709    private final Map<K, V> map;
1710
1711    AbstractMapWrapper(Map<K, V> map) {
1712      this.map = checkNotNull(map);
1713    }
1714
1715    @Override public void clear() {
1716      map.clear();
1717    }
1718
1719    @Override public boolean containsKey(Object key) {
1720      return map.containsKey(key);
1721    }
1722
1723    @Override public V remove(Object key) {
1724      return map.remove(key);
1725    }
1726
1727    @Override public boolean containsValue(Object value) {
1728      return map.containsValue(value);
1729    }
1730
1731    @Override protected Set<Entry<K, V>> createEntrySet() {
1732      return map.entrySet();
1733    }
1734
1735    @Override public boolean isEmpty() {
1736      return map.isEmpty();
1737    }
1738
1739    @Override public int size() {
1740      return map.size();
1741    }
1742  }
1743}